决策树算法

1. 决策树算法简介

决策树思想来源非常朴素，程序设计中的条件分支结构就是if-else结构，最早的决策树就是利用这类结构分割数据的一种分类方法。
决策树：是一种树形结构，每个节点表示一个属性上的判断，每个分支代表一个输出的判断结果，最后每个叶子结点代表分类结果，本质是一颗由多个判单节点组成的树。

2. 决策树分类原理

2.1 熵

2.1.1 概念

物理学上，熵Entropy是“混乱”程度的度量。
系统越有序，熵值越低；系统越混乱，熵值越高。

• 信息理论：

1. 从信息的完整性上进行描述：
   当系统的有序状态一致时，数据越集中的地方熵值越小，数据越分散的地方熵值越大
2. 从信息的有序上进行描述：
   当数据量一致时，系统越有序，熵值越低，系统越混乱或者越分散，熵值越高。
   信息熵（Entropy）
   捕获.PNG

2.2 决策树的划分依据——信息增益

2.2.1概念

信息增益：某特征划分数据集前后的熵的差值。熵可以表示样本合集的不确定性，熵越大，样本的不确定性越大。
因此，使用划分前后集合熵的差值来衡量使用当前特征对于样本集合D划分效果的好坏。
信息增益 = entroy（前）-entroy（后）

捕获.PNG

2.3 决策树的划分依据二——信息增益率

增益率：增益比率是用前面的增益度量Gain(S,A)和所分离信息度量SplitInformation的比值来共同定义的。

2.4 决策树的划分依据三——基尼值和基尼指数

2.4.1 概念

基尼值
基尼指数：一般，选择使划分后基尼指数最小的属性作为最优划分属性。基尼指数最大的属性为决策树的根节点属性。

3 常见决策树类型比较

3.1 ID3决策树算法

存在的缺点
（1）在选择根节点和各内部节点中的分支属性时，采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多的属性，在有些情况下这类属性可能不会提供太多有价值的信息。
（2）只能对描述属性为离散型属性的数据集构造决策树。

3.2 C4.5决策树算法

改进
（1）用信息增益率来选择属性
（2）可以用来处理连续数值型属性
（3）采用了一种后剪枝方法
（4）对于缺失值的处理
优点
产生的分类规则易于理解，准确率较高。
缺点
在构造的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法低效。只适用于能够存储在内存中的数据量，当训练集大到内存中无法容纳时，该算法失效

3.3 CART决策树算法

采用简化的二叉树模型，同时特征选择采用近似的基尼指数。

3.3.1 常用剪枝方法

1. 预剪枝
   （1）每个节点所包含的最小样本数目，例如，当节点样本总数小于10时，则不再分。
   （2）指定树的高度或者深度，例如树的最大深度为4.
   （3）指定节点的熵小于某个值，不再划分。随着树的增长，在训练集上的精度是单调上升的，然而在独立的测试样例上测出的精度先上升后下降。
   2.后剪枝
   （1）后剪枝，在已生成过拟合决策树上进行剪枝，可以得到简化版的剪枝决策树。

4.思考

4.1 决策树构建方法

1. 开始将所有记录看成一个节点
2. 遍历每个变量的每一种分割方式，找到最好的分割点
3. 分割成两个节点N1和N2
4. 对N1和N2分别继续执行2-3步，知道每个节点足够优秀为止