决策树：ID3和C4.5
目录
1 决策树简介
决策树是一种分类算法，是通过对数据的处理，利用归纳算法，生成一些列规则，类似于if-else，然后根据这些规则对新的数据做决策。本质上就是学习规则，在利用规则做分类的过程。具体来说，就是首先根据数据的特征，决定每个树的节点使用哪一个特征做为分类依据，以及使用这个特征的哪个指作为分类界限，这就是一棵树的构造过程。
决策树的优点：
- 推理过程容易理解，决策过程可以表示成if-else
- 推理过程完全依赖于属性变量的取值特点
- 可自动忽略目标变量没有贡献 的属性变量，也为判断属性变量的重要性、减少变量数目提供参考。
2 前置信息论知识
2.1 熵的概念
熵是对信息不确定程度的度量， 信息越不确定，熵就越大，反之熵就越小。熵的数学解释：
假设是一个取有限值的随机变量，其概率分布为：
则对于随机变量的熵的定义为：
其中代表
的
种不同的离散取值，
代表了
取值为
的概率，对数以2为底或者以自然地鼠e为底，这时熵的单位称作比特（bit）或纳特（nat），熵只依赖于
的分布，与
的取值无关。
2.2 条件熵
条件熵是也是熵，表示信息在确定了一部分信息之后，剩下的信息的熵，类似于条件概率的概念，条件熵的表达式如下：
对于这部分可以理解为，假设有一个信息X，包含两个特征Y和Z，现在已经知道了Y，Y已经成为了一个确定的信息，所以特征Y已经不具有不确定性，于是去掉了Y的不确定性的熵就是上面的条件熵，如上面的公式。条件熵往往比信息原来的熵要小，因为减少了不确定性。
2.3 信息增益
信息增益就是用信息原来的熵对给定特征的条件下的条件熵做差，差值的部分就是信息增益。用原来的熵与条件熵做差就可以得到减少的这部分不确定性所减少的熵是多少，也就表示了减少了多少不确定性。对于给定一个特征减少的熵越多，表示这个特征对整体信息的不确定性影响越大，也就是表示这个信息越重要。
特征A对训练数据集D的信息增益定义为，集合的D的熵与特征A给定的条件下D的经验熵与条件熵做差，即信息增益的表达式如下：
2.4 信息增益比
在信息增益的基础上，提出了信息增益比。当某个特征的属性熵本身较大的时候，自然更有可能使得信息增益也较大，此时单纯的大小比较就没有意义，因此引出了信息增益比，就是对信息增益归一化，变为百分比来比较大小。
其中，是属性熵，计算方式可以参考这个公式：
其中n为特征A的类别数，为特征A的第i个取值对应的概率（频率）。计算方式和熵的计算方式几乎一样，只不过是针对特征来计算，而不是针对随机变量来计算。
2.5 举例说明
这里有一张贷款申请样本数据表，其中有四个特征，年龄、有工作、有自己房子、信贷情况，暂时称为A1，A2，A3，A4，总的信息熵如下：
在给定特征A1的条件下，信息增益如下：
在给定特征A2的条件下，信息增益如下：
以此类推，后面就不罗列了。
3 ID3算法
3.1 ID3算法解释
根据上面对决策树与信息熵的介绍，构建一棵决策树只需要知道：每个树的节点使用哪一个特征做为分类依据，以及使用这个特征的哪个指作为分类界限，就可以了。最好的办法就是把越重要的特征作为越重要分类依据，按重要程度依次分类。而信息熵与信系增益可以计算出那哪个特征更重要，因此就选用信息增益来表示每个特征的重要程度，然后每次都贪心的选择最重要的特征作为下一次分类的节点，然后以每个离散的特征值作为下一个节点的分支。
对于具体的算法描述借鉴了统计学习方法一书中的描述：
3.2 ID3算法不足
- 没有考虑连续的特征，只能对离散特征进行分类。
- 没有考虑过拟合。
- 没有考虑缺失值的问题，在假设没有缺失值的情况下，在每个节点对样本按照当前节点的分类依据特征，以特征值进行分类，如果一些样本的特征存在缺失值，没有进行处理。
- ID3的特征选择依据是按照信息增益最大，这就导致一个问题，ID3更倾向选择特征值数量较多的特征，因为节点的分支数量越多，在相同条件下，信息增益就越大，但是这并不代表这两个特征谁更具有不确定性。
4 C4.5算法
4.1 采用信息增益比作为特征选择标准
为解决ID3更倾向选择特征值数量较多的特征，C4.5将特征选择的标准改为了信息增益比。信息增益比 = 信息增益 / 属性熵，上面也有公式介绍。当某个特征属性值多的时候，信息增益较大，同时属性熵也较大，所以信息增益比会维持一个正常状态。
4.2 处理连续特征
为解决ID3中不能处理连续特征的问题，C4.5做了改进，对连续的属性进行离散化的处理。取相邻两样本值的平均数，会得到一定数量（样本数-1）的划分点，分别计算以每个划分点作为二元分类点时的信息增益。选择信息增益最大的点作为该连续特征的二元离散分类点。
4.3 缺失值处理
对于缺失值处理的问题，主要需要解决的是两个问题，一是在样本某些特征缺失的情况下选择划分的属性，二是选定了划分属性，对于在该属性上缺失特征的样本的处理。
对于第一个子问题，对于某一个有缺失特征值的特征A。C4.5的思路是将数据分成两部分，对每个样本设置一个权重（初始可以都为1），然后划分数据，一部分是有特征值A的数据D1，另一部分是没有特征A的数据D2. 然后对于没有缺失特征A的数据集D1来和对应的A特征的各个特征值一起计算加权重后的信息增益比，最后乘上一个系数，这个系数是无特征A缺失的样本加权后所占加权总样本的比例。
对于第二个子问题，可以将缺失特征的样本同时划分入所有的子节点，不过将该样本的权重按各个子节点样本的数量比例来分配。比如缺失特征A的样本a之前权重为1，特征A有3个特征值A1,A2,A3。 3个特征值对应的无缺失A特征的样本个数为2,3,4.则a同时划分入A1，A2，A3。对应权重调节为2/9,3/9, 4/9。
5 总结
- ID3 对缺失数据和噪声敏感
- ID3在分类时倾向于选择属性值多的特征
- ID3不能处理连续特征
- C4.5对ID3以上三点进行了改进但是同样容易过拟合，对于过拟合问题可以采用悲观剪枝等手段降低过拟合
- 多叉树在计算机中的效率不如二叉树高，同时熵的计算效率过低，由此引出了后续的CART树