浅谈C5.0与CART算法的比较–理论理解

一、决策树的发展

决策树是目前比较流行的一种分类算法，实质上是一种自上而下的归纳学习算法。该算法最早由Quinlan在1986年提出，当时称为ID3算法，该算法是基于信息增益进行节点变量的选择，但该选择方法会倾向于属性值比较多的那些变量（如省份字段有31个水平，性别有2个水平，信息增益首选会考虑选择省份作为特征节点）；而且该算法在构造树的时候不能很好的处理连续的自变量，导致该算法的扩展性比较弱；随后的1993年，Quinlan又提出了C4.5算法，改进了ID3的缺点，即使用信息增益率进行特征节点的选择，避免了偏袒的可能性，而且该算法对自变量不作任何的限制，但是最大的缺点是该算法的运行效率比较低；为了解决效率的问题，基于C4.5提出了商业版的C5.0，可惜的是C5.0并没有公布算法的更多细节，但其主要核心部分还是和C4.5一致的。与此同时，1984年Brieman等人提出了CART算法，该算法拥有一个非常完整的体系，包括树的生长过程（采用基尼指数选择树的节点）、剪枝过程等，而且该算法还可以解决回归问题。接下来就针对C5.0和CART算法做一个简要的对比。

二、C5.0与CART的比较

C5.0算法

1、C5.0是一种多叉树（即如果根节点或中间节点存在连续型的自变量，则该变量会一分为二的展开两个分支；如果根节点或中间节点存在离散的自变量，则该变量会根据离散变量的水平数分开多个分支），就会导致某个变量一旦被使用，后面的节点将不会再启用该变量。

2、C5.0决策树的生长过程采用的是最大信息增益率原则进行节点选择和分裂点的选择，具体可从下方的理论中理解：

信息熵反应的是信息杂乱程度，信息越杂乱（越不纯），则信息熵越大；反之，信息熵越小。其数学公式为：

其中-log2(pj)反应的是信息量，即某随机事件发生的概率越小，则信息量越大；反之概率越大，则信息量越小。所以信息熵就是指事件发生的概率（pj）乘以其对应的信息量（-log2(pj)），然后再加总。

信息增益的计算为：

其中，Info为Y变量的信息熵，InfoA为自变量A对Y变量分割的信息熵，

接下来举个例子，也许你就能够明白。

Y变量为是否相亲，不妨我们计算学历这个变量对Y变量的分割信息增益值。

Y变量的信息熵：

学历对Y变量的分割信息熵：

学历对Y变量的分割信息增益：

在非叶节点的特征选择时，我们要求信息增益最大化，但考虑信息增益最大化会带来一个问题，就是特征的选择会倾向于那些离散水平多的变量。例如两种极端情况：一种是ID变量（当作离散变量处理），该变量对Y变量的分割信息增益就等于Y变量的信息熵，达到最大；另一种是单一值变量，如国籍，该变量对Y变量的分割信息增益就等于0，达到最小，所以节点变量很可能会选择ID变量。但这样做其实是对那些水平比较少的离散变量的一种不公平处理。于是就提出了信息增益率的概念，即：

SI为分割信息，说白了就是计算自变量A的信息熵；信息增益率就是在信息增益的基础上除以自变量A的信息熵。仍然接着上面的学历例子：

学历变量的信息熵：

学历对Y变量的分割信息增益率：

通过这样的一个变换就可以解决信息增益存在的偏袒弊端。

3、剪枝采用“减少-误差”法和“减少-损失”法技术

“减少–误差”法：其核心思想是对比剪枝前后的误差率，如果剪枝后的误差率比剪枝前的误差率要低，则剪枝，否则不剪枝。关于误差率的计算：如果第i个节点中包含N个样本，其中预测错误的样本量为M，则该节点的错误率为f=M/N，根据正态分布假设，该观测错误率的置信区间为：

所以得到悲观的真实错误率为：

该剪枝方法所设定的默认alpha值为0.25，所以，alpha（置信水平）越小，则1-alpha（置信度）就越大，就越可能执行剪枝，使得真实错误率越小，模型的泛化能力越大。

“减少–损失”法：该方法结合损失矩阵对树进行剪枝，核心思想是比较剪枝前后损失量，如果剪枝后的损失要小于剪枝前的损失，则剪枝，否则不剪枝。有关损失的计算如下：

其中，k为待剪子树中叶节点的个数，pi为第i个叶节点所含样本量占子树所含样本量的比例，ei为第i个叶节点的估计误差，oi为第i个叶节点的错判损失，e为父节点的估计误差，o为父节点的错判损失。

4、C5.0算法只能解决分类问题。

CART算法

1、是一个二叉树，即每一个非叶节点只能引伸出两个分支，所以当某个非叶节点是多水平(2个以上)的离散变量时，该变量就有可能被多次使用。举个例子也许能够明白：如果年龄段可分为{青年，中年，老年}，则其子集可以是{青年，中年，老年}、{青年，中年}、{青年，老年}、{中年，老年}、{青年}、{中年}、{老年}、{}。其中{青年，中年，老年}和空集{}为无意义的分割，所以最终有2^3-2=6种组合，形成3对对立的组合，如{青年，中年}与{老年}可以分出两个分支。

2、CART决策树的生长过程采用的是最大基尼增益指数原则进行节点选择和分裂点的选择，具体可从下方的理论中理解：

对于分类问题

Y变量的基尼指数：

自变量A对Y变量的分割基尼增益指数：

我们仍然拿上面的相亲数据为例，计算学历的各个水平对Y变量的分割基尼增益指数：

Y变量的基尼指数：

{大专}与{本科、硕士}二叉树的基尼指数：

所以，大专与非大专的分割基尼增益指数为0.486-0.483=0.003。

{本科}与{大专、硕士}二叉树的基尼指数：

所以，本科与非本科的分割基尼增益指数为0.486-0.438=0.048。

{硕士}与{大专、本科}二叉树的基尼指数：

所以，硕士与非硕士的分割基尼增益指数为0.486-0.419=0.067。

对于回归问题

非叶结点的特征选择及分割点选择使用最小二乘偏差：

Y变量的最小二乘偏差：

其中，yi为实际的连续值，ri为预测的连续值；ri的是由某个叶节点中样本均值来衡量。

自变量A对Y变量的分割最小二乘偏差增益：

其中，beta为连续变量的某个分割点，基于这个分割点可以将数据分成两组。

3、剪枝采用“最小代价复杂度”法和“损失矩阵”法技术

最小代价复杂度说白了就是某个中间节点中往叶节点发展的过程中，其大错误率是否下降的明显，如果不明显，则剪枝，否则不减枝。具体数学公式如下：

举个例子也许你就明白了：

上图反应了一个简单的树，根节点有100个样本，两个中间节点T1，T2和4个叶节点。则中间节点T1，T2误差率增益值α分别为：

可通过设置一个阈值，当误差率增益值α低于阈值时可以考虑剪枝。

损失矩阵的思想与C5.0的类似，这里就不在赘述。

4、CART算法既可以解决分类问题（Y变量为离散变量），也能够很好的处理预测问题（Y变量为连续变量）。

关于两个算法的理论比较我们今天就讲到这里，主要是从算法的几叉树？如何选择节点特征、分割点？树的剪枝技术？和各自解决的问题做了梳理。在下一期我们将针对这两个算法如何通过R语言实现落地，并通过案例完成两个算法的较量。

END.

本文已获得原作者授权

原文始发于微信公众号（PPV课数据科学社区）：浅谈C5.0与CART算法的比较–理论理解