为什么C4.5决策树能处理连续特征，ID3树不能处理连续特征？ 第1页

先回答题主第一个问题：为什么C4.5决策树能处理连续特征，ID3树不能处理连续特征？

答：这是因为ID3在设计的时候根本就没考虑过要处理连续特征，所以它自然就不能处理连续特征。

那为什么ID3不考虑连续特征？这是因为任何研究都是循循渐进的，每一个研究只会将精力放在当前最重要的研究点之上。ID3与C4.5都是Quinlan 的作品，而ID3的研究重点是如何设计高效的节点分裂方法来生长决策树，因此它并不太在意如何去处理连续特征。为此，ID3提出了使用信息增益来衡量一次节点分裂的优劣，它是第一个成功将信息论相关理论使用到决策树算法中的，从这点来看它的时代意义比较重要。因此从学术贡献来看，它确实也没有必要再去处理一些琐碎而简单的问题了。

而C4.5的重点则是将ID3的成果工程化，让决策树能真正解决实际中的复杂问题，所以C4.5设计了详细的连续特征处理方法和剪枝算法。

以现在的眼光来看，只要你愿意，可以很容易地将ID3改造为有能力处理连续特征的决策树。

第二个问题，ID3、C4.5和CART的比较。

先说前二者。C4.5是ID3的续作。

按照作者Quinlan 的说法，C4.5是指一系列决策树算法。而现在我们一般只把它看作为一个特定的决策树算法。C4.5在评估节点划分的优劣时，不再只使用信息增益，会同时使用信息增益和信息增益率。注意，是同时使用信息增益和信息增益率，而不是只使用信息增益率。很多书籍和博客错误理解了这一点。

我们首先分析一下信息增益有什么问题。很多文章会说：信息增益会偏向于变量取值更多的离散特征。不管其对错，先看如下信息熵的公式：

假设我们有数据集D，它包含12个样本，其中有6个正样本和6个负样本。再假设两种划分，第一种划分使用特征a把数据集D划分成了两份：

D1，Pos 4 : Neg 2 （4个正样本，2个负样本）

D2，Pos 2 : Neg 4（2个正样本，4个负样本）

容易计算，数据集D1和D2的信息熵都为：

（1）

所以它们的加权熵也等于（1）式。

再来看第二种划分，使用特征b把数据集D划分成了四份

D1，Pos 2 : Neg 1 （2个正样本，1个负样本）

D2，Pos 2 : Neg 1（2个正样本，1个负样本）

D3，Pos 1 : Neg 2 （1个正样本，2个负样本）

D4，Pos 1 : Neg 2（1个正样本，2个负样本）

容易计算，这四个数据集的加权熵也等于（1）式。所以用特征a和用特征b对数据集划分得到的信息熵是一致的，这也符合我们的直觉，因为它们划分出来的结果差不多。我们看到，这样一个简单的例子其实说明“信息增益会偏向于变量取值更多的离散特征”这个结论是靠不住的，一个反例足以。那么信息增益真正的问题在哪？

继续上面的例子。刚才说了，从直觉上，用特征a对数据集划分得到的结果与用特征b对数据集进行划分得到的结果是差不多的。但从机器学习的角度来看，此时特征a的划分可能更好。原因是b迅速地将样本空间划分的过小了，从而增加了过拟合的风险。例如，我们要估计落入每个节点的正样本的真实比例（真实分布，非数据经验分布），此时我们可以用训练时数据在节点上的分布来作估计值。用特征a的划分，在D1上它的估计值是2/3；用特征b的划分，在D1上它的估计值也是2/3。但区别在于特征a的划分用了6个样本在估计，而特征b的划分只用了3个样本。所以用特征a的划分进行估计时可能更加准确。

综上所述，当面临差不多的两种划分时，我们应该要避免选择划分分支更多的那一种，因为它会将样本空间划分的更小，从而会导致在其中的统计量的可靠性变差。而信息增益在面临此种选择时，不会偏向任何一方。

所以C4.5提出了信息增益率。上面如果读懂了，此时就应该非常容易猜到信息增益率设计的动机是什么。既然要让指标偏向于划分少的，而信息增益本身并不能办到这一点，那么可以设计出一个factor，让信息增益去乘以这个factor，并且划分越多，这个factor要越小。

于是C4.5中的split info就出现了，它完全满足这样的要求（实际是它的倒数）。例如，上面的例子中，用特征a划分得到的split info为-log(0.5)，而特征b划分得到的split info为-log(0.25)。后者显然大于前者，这就达到了让指标倾向于划分结果少的划分的目的。

通过上述分析，可以看出信息增益仍然是更加直接的评价指标，它能直接评估一次分裂是否能够将数据划分的更加纯净。而信息增益仅仅是一个“相对”指标。C4.5与ID3的最大区别在于，ID3仅仅追求每次节点划分能够带来最大的“收益”，而C4.5算法强调的是在保证足够收益的情况下，寻求最大“收益代价比”（将split info看作代价）。

C4.5寻找最优划分的真实方法是：1）计算所有划分的平均信息增益t；2）从所有信息增益大于t的划分中寻找信息增益率最大的划分，该划分就是最优划分。

另外，C4.5在对连续特征计算最优分割点时，只使用了信息增益，而不考虑信息增益率。这进一步暗示了信息增益才是对划分优劣更直接的评价指标。

ID3在印象中是没有剪枝的。而Quinlan 介绍的C4.5剪枝算法其实比较复杂，它主要用了针对极小样本的二项分布参数的估计方法。题主有兴趣我再追答。

最后来说CART，它与ID3和C4.5的最大区别就是在评估划分好坏时，它用了基尼系数。另外CART树一定是二分结构，及对取多个离散值的离散变量来说，它也会将它划分为二叉结构，其中一条分支表示一个值，另一条分支表示另外其它所有值。二叉的好处是不会遇到ID3使用信息增益的那种问题。所以要避免ID3的信息增益问题，另一种做法是将其改为二叉树结构。

CART的剪枝与C4.5区别也较大。简单来说，它考虑了决策树自身的规模，而C4.5并没有显示地考虑（但隐含着有类似的思想）。