决策树

作者: Zaker_cook | 来源:发表于2019-12-12 00:02 被阅读0次

问题：

1. 决策树节点是如何确定？

2. 决策树构建流程是怎么样？

3. 决策树都有哪些优缺点？

4. 决策树缺点部分该如何进行优化？

1. 决策树节点的确定

决策树的节点，是依据特征的“纯度”来确定。”纯度“是用 信息熵 / 信息增益 / 信息增益率 / 基尼系数 表示。

信息熵公式：

$H(X) = \sum_{i=1}^n - p(x_i)\log_2 p(x_i)$ p是某一特征值的概率

信息增益公式：(偏向值较多的特征属性)

$IG(X) = H(Y) - H(Y|X)$

其中 H(Y|X) 是条件熵，指的是在X特征发生的条件下Y的信息熵

$H(Y|X) = \sum_{j=1}^n p(x_j) H(Y | x_j)$ n是特征X中去重后值的个数

信息增益率公式：(偏向值较少的特征属性)

$G_r (X)= \frac{IG(X)}{H(X)}$

基尼系数公式：(表示类别不一致的概率)

$Gini(X) = 1 - \sum_{i=1}^n p(x_i)$

基尼增益公式：

$IGini(X) = Gini(Y) - Gini(Y|X)$

其中 Gini(Y | X) 是条件基尼系数

$Gini(Y|X) = \sum_{i=1}^n p(x_i)Gini(Y|x_i)$

基尼增益率公式：

$G_r = \frac{IGini(X)}{Gini(X)}$

纯度越纯，信息熵，基尼系数越小，信息增益，信息增益率越大。

纯度越不纯，信息熵，基尼系数越大，信息增益，信息增益率越小。

2. 决策树构建流程

a. 将所有特征作为一个节点 —— 计算 $H(Y)$

b. 遍历当前特征，找到最优的分割点，将数据分为不同的子节点 —— 计算 $H(x_i)$ 和 $IG(X)$

c. 选择 $IG(X)$ 最大的特征作为子节点

d. 循环执行 b 和 c ，直到最终的每个子节点都足够“纯” 或是满足其他停止划分条件

参考流程图

参考代码实现

图例说明

图例数据

a. 在不知道任何条件下，计算数据本身的信息熵

$H(Y) = - \frac{9}{14}log_2 \frac{9}{14}-\frac{5}{14}log_2\frac{5}{14}=0.940$

b. 计算每个特征作为节点的信息熵

每个特征作为节点的划分

以天气为例，天气有三个特征属性值

当 outlook = sunny时， $H(x) = -\frac{2}{5}log_2\frac{2}{5}-\frac{3}{5}log_2\frac{3}{5}$

当 outlook = overcast时， $H(x) = 0$

当 outlook = rainy时， $H(x) = 0.971$

当天气作为节点时， $H(Y|X) = \frac{5}{14}*0.971+\frac{4}{14}*0+\frac{5}{14}*0.971 = 0.693$

信息增益 $IG(X=天气) = H(Y) - H(Y|X) = 0.940-0.693 = 0.247$

同理

$IG(X=温度) =0.029$

$IG(X=湿度)=0.152$

$IG(X=风)=0.048$

因此，选择天气作为节点，再依据这些步骤，递归选择其他节点

3. 决策树优缺点

优点：决策树构建速度快，比较容易实现，并能够处理缺失值和不相关的特征

缺点：决策树容易过拟合，而在类别数据不一致时，各判定节点的方法会有不同的属性偏向

4. 决策树缺点优化

a. 对决策树进行剪枝，剪枝分为前剪枝与后剪枝

b. 采用交叉验证或正则化的方法

c. 使用基于 Bagging思想的随机森林算法等

5. 决策树常用算法

ID3、C4.5、CART之间的区别

ID3，内部使用信息熵以及信息增益进行构建，每次迭代选择信息增益最大的特征属性作为分割属性。它只支持离散特征属性，不支持连续特征属性。

优点：实现比较简单，构建速度快

缺点：依赖特征值数目较多的特征，不会考虑特征之间的关系，以及抗噪性比较差

C4.5，它使用信息增益率进行构建，在树构建中会进行剪枝操作优化，并能自动完成对连续属性离散化处理。

优点：准确率高，易于理解

缺点：对数据集多次顺序扫描和排序，效率较低

CART，它使用Gini增益率作为分割属性的标准，可以用于分类和回归，构造的是二叉树

三种算法总结：

a. 均只适合在小规模数据集上使用，数据集需在内存中

b. 属性取值较多时，考虑C4.5

c. CART 是最常用的决策树算法，sklearn仅支持CART

d. CART构建的一定是二叉树，ID3和C4.5构建的不一定是二叉树

e. 对当前树评价标准不同，ID3使用信息增益、C4.5使用信息增益率、CART使用基尼系数

网友评论

本文标题：决策树

本文链接：https://www.haomeiwen.com/subject/mqmogctx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

决策树

问题：