纯概念，了解即可，没啥卵用
决策树思想的来源非常朴素，程序设计中的条件分支结构就是if-else结构，最早的决策树就是利用这类结构分割数据的一种分类学习方法
决策树：
- 是一种树形结构，本质是一颗由多个判断节点组成的树
- 其中每个内部节点表示一个属性上的判断，
- 每个分支代表一个判断结果的输出，
- 最后每个叶节点代表一种分类结果。
熵
物理学上，熵 Entropy 是“混乱”程度的量度。
系统越有序，熵值越低；系统越混乱或者分散，熵值越高。
信息熵
- 信息理论：
1、从信息的完整性上进行的描述:
当系统的有序状态一致时，数据越集中的地方熵值越小，数据越分散的地方熵值越大。
2、从信息的有序性上进行的描述:
当数据量一致时，系统越有序，熵值越低；系统越混乱或者分散，熵值越高。
决策树的划分依据一—-信息增益
信息增益：以某特征划分数据集前后的熵的差值。熵可以表示样本集合的不确定性，熵越大，样本的不确定性就越大。因此可以使用划分前后集合熵的差值来衡量使用当前特征对于样本集合D划分效果的好坏。
信息增益 = entroy(前) – entroy(后)
决策树的划分依据二—-信息增益率
信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，著名的 C4.5 决策树算法 [Quinlan， 1993J 不直接使用信息增益，而是使用”增益率” (gain ratio) 来选择最优划分属性.
增益率：增益率是用前面的信息增益Gain(D, a)和属性a对应的”固有值”(intrinsic value) [Quinlan , 1993J的比值来共同定义的。
总结一下C4.5的算法流程
while(当前节点"不纯")：
1.计算当前节点的类别熵(以类别取值计算)
2.计算当前阶段的属性熵(按照属性取值吓得类别取值计算)
3.计算信息增益
4.计算各个属性的分裂信息度量
5.计算各个属性的信息增益率
end while
当前阶段设置为叶子节点
为什么使用C4.5要好
1.用信息增益率来选择属性
克服了用信息增益来选择属性时偏向选择值多的属性的不足。
2.采用了一种后剪枝方法
避免树的高度无节制的增长，避免过度拟合数据
3.对于缺失值的处理
在某些情况下，可供使用的数据可能缺少某些属性的值。假如〈x，c(x)〉是样本集S中的一个训练实例，但是其属性A的值A(x)未知。
处理缺少属性值的一种策略是赋给它结点n所对应的训练实例中该属性的最常见值；
另外一种更复杂的策略是为A的每个可能值赋予一个概率。
例如，给定一个布尔属性A，如果结点n包含6个已知A=1和4个A=0的实例，那么A(x)=1的概率是0.6，而A(x)=0的概率是0.4。于是，实例x的60%被分配到A=1的分支，40%被分配到另一个分支。
C4.5就是使用这种方法处理缺少的属性值。
决策树的划分依据三 —-基尼值和基尼指数
基尼值Gini（D）：从数据集D中随机抽取两个样本，其类别标记不一致的概率。故，Gini（D）值越小，数据集D的纯度越高。
常见决策树的启发函数比较
多变量决策树(multi-variate decision tree)
无论是ID3, C4.5还是CART,在做特征选择的时候都是选择最优的一个特征来做分类决策，但是大多数，分类决策不应该是由某一个特征决定的，而是应该由一组特征决定的。这样决策得到的决策树更加准确。这个决策树叫做多变量决策树(multi-variate decision tree)。在选择最优特征的时候，多变量决策树不是选择某一个最优特征，而是选择最优的一个特征线性组合来做决策。这个算法的代表是OC1
决策树变量的两种类型：
- 数字型（Numeric）：变量类型是整数或浮点数，如前面例子中的“年收入”。用“>=”，“>”,“<”或“<=”作为分割条件（排序后，利用已有的分割情况，可以优化分割算法的时间复杂度）。
- 名称型（Nominal）：类似编程语言中的枚举类型，变量只能从有限的选项中选取，比如前面例子中的“婚姻情况”，只能是“单身”，“已婚”或“离婚”，使用“=”来分割。
如何评估分割点的好坏？
如果一个分割点可以将当前的所有节点分为两类，使得每一类都很“纯”，也就是同一类的记录较多，那么就是一个好分割点。
比如上面的例子，“拥有房产”，可以将记录分成了两类，“是”的节点全部都可以偿还债务，非常“纯”；“否”的节点，可以偿还贷款和无法偿还贷款的人都有，不是很“纯”，但是两个节点加起来的纯度之和与原始节点的纯度之差最大，所以按照这种方法分割。
构建决策树采用贪心算法，只考虑当前纯度差最大的情况作为分割点。