Daaang

V1

2022/11/09阅读:25主题:默认主题

机器学习---决策树CART算法

决策树之 CART 算法

问题引入

题:如下图是调查是否

目标:是通过一些属性信息(是否有房、婚姻状况、年收入等)来推测这个人买不买电脑。

解题策略

CART 算法用基尼(Gini)系数最小化准则来进行特征选择并生成二叉树。决策树的生成就是递归地构建二叉决策树的过程。

解题思路

  1. 根据三种不同的方式构建相应的决策表

  2. 判断属性情况

  • 该属性的类别为 2
  • 该属性的类别为 3
  • 该属性的类别连续
  1. 根据不同的属性采用相应的计算方法计算出 Gini 值
  • 第 1 种情况该属性的类别为 2 计算方法[1]
  • 第 2 种情况该属性的类别为 3 或以上的计算方法[2]
  • 第 3 种情况该属性的类别连续的计算方法[3]
  1. 取Gini 系数最小的属性类别作为二叉树的左子树
  2. 取Gini 系数最小的同属性剩余类别作为二叉树的右子树
  3. 分别判断各子树子表的 class 属性是否完成一致
    • 若一致则直接将该属性值作为叶子节点
    • 若不一致则进行以下计算得出叶子节点
  4. 根据各子表算出新的 Gini 系数,回到第 2 步直到所有属性算完。

公式

定义 1:

  1. P_i 为一个目标类别出现的概率 有定理
  2. m 为目标类别的总数 如 buys 中只有 2 类所以 m 恒为 2 n 为当前计算属性的类别数
  3. D 为一个属性的所有类别 如 age 中的(youth,middle_age,senior)
  4. Gini(D)为基尼系数

所以有公式 1

公式 1:Gini系数的计算

例1:

结果

代码 Python

Graphviz的安装可以参考以下这篇博客[4]

python中GraphViz's executables not found的解决方法以及决策树可视化

import numpy as np
from  sklearn import tree
import os
os.environ["PATH"] += os.pathsep + 'D:/anaconda3/Lib/site-packages/graphviz/bin'
data = np.genfromtxt("exercise.csv",delimiter=",")
x_data = data[1:,1:-1]
y_data = data[1:,-1]
print(x_data)
dtree = tree.DecisionTreeClassifier()
dtree.fit(x_data,y_data)
print(dtree.score(x_data, y_data))

import graphviz

dot_data = tree.export_graphviz(dtree,
                                out_file=None,
                                feature_names=['house_yes','house_no','single','married','divorced','income'],
                                class_names=['no','yes'],
                                filled=True,
                                rounded=True,
                                special_characters=True)
graph = graphviz.Source(dot_data)
graph.render('computer', view=True)

csv数据集如下:

参考资料

[1]

CART算法: https://zhuanlan.zhihu.com/p/32003259

[2]

CART算法: https://zhuanlan.zhihu.com/p/32003259

[3]

CART算法: https://zhuanlan.zhihu.com/p/32003259

[4]

python中GraphViz's executables not found的解决方法以及决策树可视化: https://www.cnblogs.com/wbyixx/p/12323647.html

分类:

后端

标签:

后端

作者介绍

Daaang
V1