决策树算法的比较

前面我们一一介绍了决策树算法的实现过程，现在对ID3、CART、C4.5几种算法进行比较。

ID3的不足

• ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。
• ID3偏好选择取值多的特征做分支，ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值，各为1/2，另一个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大。
  直白解释：取值比较多的特征，就可以分叉出更多的分支，分支更多，每个分支的纯度必然更高！
• ID3算法对于缺失值的情况没有做考虑
• 没有考虑过拟合的问题，即没有剪枝处理

C4.5算法

C4.5与ID3算法为同一作者，C4.5是ID3的改进，其建书思路基本一致，主要是改进是ID3的四点不足之处。

• 对与 ID3没有考虑连续特征

C4.5的思路是将连续的特征离散化。比如mm个样本的连续特征AA有mm个，从小到大排列为a1,a2,…,ama1,a2,…,am,则C4.5取相邻两样本值的中位数，一共取得m−1m−1个划分点，其中第ii个划分点TiTi表示为：Ti=ai+ai+12Ti=ai+ai+12。对于这m−1m−1个点，分别计算以该点作为二元分类点时的信息增益。选择信息增益最大的点作为该连续特征的二元离散分类点。比如取到的增益最大的点atat,则小于atat的值为类别1，大于atat的值为类别2，这样我们就做到了连续特征的离散化。要注意的是，与离散属性不同的是，如果当前节点为连续属性，则该属性后面还可以参与子节点的产生选择过程。

• 对与 ID3偏好选择取值多的特征做分支

改用信息增益率作为分支指标，因为特征数越多的特征对应的特征熵越大，它作为分母，可以校正信息增益容易偏向于取值较多的特征的问题。

• 对与ID3算法对于缺失值的情况没有做考虑

主要需要解决的是两个问题，一是在样本某些特征缺失的情况下选择划分的属性，二是选定了划分属性，对于在该属性上缺失特征的样本的处理。
对于第一个子问题，对于某一个有缺失特征值的特征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。

• 对与ID3没有考虑过拟合的问题

C4.5引入了正则化系数进行初步的剪枝。

C4.5的不足

• 由于决策树算法非常容易过拟合，因此对于生成的决策树必须要进行剪枝。剪枝的算法有非常多，C4.5的剪枝方法有优化的空间。思路主要是两种，一种是预剪枝，即在生成决策树的时候就决定是否剪枝。另一个是后剪枝，即先生成决策树，再通过交叉验证来剪枝。
• C4.5生成的是多叉树，即一个父节点可以有多个节点，效率低（二叉数效率才高）。
• C4.5只能用于分类。
• C4.5由于使用了熵模型，里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算。

CART算法

CART算法相比C4.5算法的分类方法，采用了简化的二叉树模型，同时特征选择采用了近似的基尼系数来简化计算。当然CART树最大的好处是还可以做回归模型，这个C4.5没有。

看起来CART算法高大上，那么CART算法还有没有什么缺点呢？有！主要的缺点如下：

1）应该大家有注意到，无论是ID3, C4.5还是CART,在做特征选择的时候都是选择最优的一个特征来做分类决策，但是大多数，分类决策不应该是由某一个特征决定的，而是应该由一组特征决定的。这样绝息到的决策树更加准确。这个决策树叫做多变量决策树(multi-variate decision tree)。在选择最优特征的时候，多变量决策树不是选择某一个最优特征，而是选择最优的一个特征线性组合来做决策。这个算法的代表是OC1，这里不多介绍。

2）如果样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习里面的随机森林之类的方法解决。

比较

算法	树结构	特征选择	连续值处理	缺失值处理	剪枝
ID3	多叉树	信息增益	不支持	不支持	不支持
C4.5	多叉树	信息增益比	支持	支持	支持
CART	二叉树	基尼系数，均方差	支持	支持	支持

参考资料

决策树-ID3、C4.5

决策树算法原理(下)