1. 决策树算法简介
决策树思想来源非常朴素，程序设计中的条件分支结构就是if-else结构，最早的决策树就是利用这类结构分割数据的一种分类方法。
决策树：是一种树形结构，每个节点表示一个属性上的判断，每个分支代表一个输出的判断结果，最后每个叶子结点代表分类结果，本质是一颗由多个判单节点组成的树。
2. 决策树分类原理
2.1 熵
2.1.1 概念
物理学上，熵Entropy是“混乱”程度的度量。
系统越有序，熵值越低；系统越混乱，熵值越高。
- 信息理论：
- 从信息的完整性上进行描述：
当系统的有序状态一致时，数据越集中的地方熵值越小，数据越分散的地方熵值越大 - 从信息的有序上进行描述：
当数据量一致时，系统越有序，熵值越低，系统越混乱或者越分散，熵值越高。
信息熵（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）每个节点所包含的最小样本数目，例如，当节点样本总数小于10时，则不再分。
（2）指定树的高度或者深度，例如树的最大深度为4.
（3）指定节点的熵小于某个值，不再划分。随着树的增长，在训练集上的精度是单调上升的，然而在独立的测试样例上测出的精度先上升后下降。
2.后剪枝
（1）后剪枝，在已生成过拟合决策树上进行剪枝，可以得到简化版的剪枝决策树。
4.思考
4.1 决策树构建方法
- 开始将所有记录看成一个节点
- 遍历每个变量的每一种分割方式，找到最好的分割点
- 分割成两个节点N1和N2
- 对N1和N2分别继续执行2-3步，知道每个节点足够优秀为止
