决策树算法 ID3 C4.5 CART

一种树形结构,其中每个内部节点表示一个属性上的判断,每个分支代表一个判断结果的输出,最后每个叶节点代表一种分类结构,本质是一颗由多个判断节点组成的树

1. 原理

   系统的混乱程度,系统越混乱或者分散,熵值越高,反之越低

   • 从信息的完整性上:

     • 数据越集中的地方熵值越小,数据越分散的地方熵值越大

   • 从信息的有序上

     • 系统越有序,熵值越低,系统越混乱或分散熵值越大

   • 信息熵的定义
     
     Ent(D)的值越小,则D的纯度越高

2. 决策树划分的依据-----信息增益(ID3算法)

   信息增益 = 集合的整体信息熵 - 给定特征a条件下D的信息条件熵

集合的整体信息熵:

给定特征a条件下D的信息条件熵:

Dv 表示a属性中第v个分支节点包含的样本数

Ckv 表示a属性中第v个分支节点包含的样本数中，第k个类别下包含的样本数

总结: 一般而言,信息增益越大,则意味着使用属性a来进行划分所获的"纯度提升"越大.所以我们可以使用ID3(Iterative Dichotomiser 迭代二分器)决策树学习算法来以信息增益划分属性

下面的案例可以很好的诠释这个问题

3. 决策树划分依据-----信息增益率(C4.5算法)

   ​

   1. 信息增益率 = 信息增益/属性a对应的"固有值"
      
      ​ 属性 a 的可能取值数目越多(即 V 越大)，则 IV(a) 的值通常会越大.

   ​ 下面的案例很好的诠释这个公式
   
   1.计算整体类别信息熵

   类别信息熵表示的是所有样本中各种类别出现的不确定性之和。根据熵的概念，熵越大，不确定性就越大，把事情搞清楚所需要的信息量就越多。

2.计算每个属性的信息熵(例如天气和 温度)

属性的信息熵相当于条件熵

3.计算信息增益(这是ID3算法的特征选取指标)

4.计算属性分裂信息度量

用分裂信息度量来考虑某种属性进行分裂时分支的数量信息和尺寸信息，我们把这些信息称为属性的内在信息（instrisic information）。信息增益率用信息增益/内在信息，会导致属性的重要性随着内在信息的增大而减小**（也就是说，如果这个属性本身不确定性就很大，那我就越不倾向于选取它）**，这样算是对单纯用信息增益有所补偿。

5.计算信息增益率

6.C4.5的算法流程

 while(当前节点"不纯")：
    1.计算当前节点的类别熵(以类别取值计算)
    2.计算当前阶段的属性熵(按照属性取值吓得类别取值计算)
    3.计算信息增益
    4.计算各个属性的分裂信息度量
    5.计算各个属性的信息增益率
end while
当前阶段设置为叶子节点
   

4. 决策树的划分依据-----基尼值和基尼系数(CART算法)

   ​ 基尼值Gini:从数据集中个随机抽取两个样本,其类别标 记不一致的概率, Gini值越小,数据集的纯度越高

   ​ 基尼值的度量:
   
   ​ pk=DCk, D为样本的所有数量，Ck为第k类样本的数量

   ​ 基尼指数Gini_index:一般,选择使划分后基尼系数最 小的属性作为最优划分属性

​ 下面的这个案例很好的诠释了上面的算法

1.对数据集非序列标号属性{是否有房，婚姻状况，年收入}分别计算它们的Gini指数，取Gini指数最小的属性作为决策树的根节点属性

2.最终选取根节点 根节点的Gini值为:

​

3.当根据是否有房来进行划分时，Gini指数计算过程为

4.如果按照婚姻状况属性来划分,则由三种情况取值(married, signle,disvorced)分别计算Gini系数

​

对比结果可知,取Gini指数最小的married来作为划分结果

5.同上可得年收入Gini,所以首先需要对数据进行升序排序,然后从小到大依次用相邻值的中间值作为分隔将样本划分为两组。例如当面对年收入为60和70这两个值时，我们算得其中间值为65。以中间值65作为分割点求出Gini指数

根据计算知道，三个属性划分根节点的指数最小的有两个：年收入属性和婚姻状况，他们的指数都为0.3。此时，选取首先出现的属性【married】作为第一次划分

6.采取同样的方法,分别计算剩下属性,其中根节点的Gini系数为（此时是否拖欠贷款的各有3个records）

​
7.对于是否有房属性

8.对于年收入属性有

9.最终得到决策树

10.CART算法的流程

while(当前节点"不纯")：
    1.遍历每个变量的每一种分割方式，找到最好的分割点
    2.分割成两个节点N1和N2
end while
每个节点足够“纯”为止

5. 总结

   算法名称	分支方式	优势
   ID3	信息增益	ID3只能对离散属性的数据集构成决策树
   C4.5	信息增益率	优化了解决了ID3分支过程中总喜欢偏向选择值较多的属性
   CART	Gini系数	可以进行分类和回归,可以处理离散属性,也可以处理连续属性

   ID3:

   • 缺点:
     • 倾向选取特征值多的属性,有些情况下这些属性却不能提供有价值的信息
     • ID3算法只能对描述属性为离散属性的数据集构造决策树

   C4.5:

   对ID3做出了改进

   1.用信息增益来选择属性

   2.可以处理连续数值型属性

   3.采用了一种后剪枝方法

   4.对于缺失值的处理

   • 优点:
     • 产生的分类易于理解,准确率较高
   • 缺点:
     • 在构造决策树的过程中,需要对数据集进行多次的顺序扫和排序,因而导致算法的低效
     • C4.5只适合能够驻留在内存的数据集,当训练集大的无法在内存容纳时程序就会崩掉

   CART:

   相比C4.5算法的分类方法,采用了简化的二叉树模型,同时特征选择采用了近似的基尼系数来简化计算

   C4.5不一定时二叉树,但是CART一定时二叉树

6. 多变量决策树

   通过上面的一些算法我们得知,不管时ID3,C4.5,CART他们都是针对一个特征而言的,但是我们大多数遇到的情况时却是有多个特征决定的 这个时候我们就要采用OC1算法来处理了

7. 决策树变量的两种类型

   1.数字型(刚才我们求基尼系数用的"年收入")

   2.名称型

8. cart剪枝
   

   横轴表示在决策树创建过程中树的结点总数，纵轴表示决策树的预测精度。

   出现这种情况的原因:

   ​ 1:噪声,样本冲突,即错误的严格不能数据

   ​ 2:特征即属性不能完全作为分类标准

   ​ 3:巧合的规律性,数据量不够大

   常用的剪枝方法

   ​ 2.1 预剪枝

   ​ 1.每一个节点所包含的最小样本数目,例如10,则该节 点总样本数小于10时,则不再分

   ​ 2.指定树的高度或者深度,例如树的最大深度为4

   ​ 3.指定节点的熵小于某个值,不再划分.随着树的增长, 在训练样集的精度时单调上升的,然而在独立的测试 样例上测出的精度先上升后下降

   ​ 2.2 后剪枝

   ​ 后剪枝，在已生成过拟合决策树上进行剪枝，可以 得到简化版的剪枝决策树。