Peter教你谈情说AI | 08决策树(中)—既能回归又能分类的模型

C4.5算法对ID3算法的改进

开门见山，我们先来看看C4.5算法是怎么弥补ID3算法不足的。对于上节提到的ID3算法不足的第一个问题，不能处理连续特征， C4.5的思路是将连续的特征离散化。比如m个样本的连续特征A有m个，从小到大排列为a1,a2,...,am，则C4.5取相邻两样本值的平均数，一共取得m-1个划分点，其中第i个划分点Ti表示为：

。对于这m-1个点，分别计算以该点作为二元分类点时的信息增益。选择信息增益最大的点作为该连续特征的二元离散分类点。比如取到的增益最大的点为at,则小于at的值为类别1，大于at的值为类别2，这样我们就做到了连续特征的离散化。要注意的是，与离散属性不同的是，如果当前节点为连续属性，则该属性后面还可以参与子节点的产生选择过程。

对于第二个问题，信息增益作为标准容易偏向于取值较多的特征的问题。我们引入一个信息增益比的变量，它是信息增益和特征熵的比值。表达式如下：

其中D为样本特征输出的集合，A为样本特征。特征数越多的特征对应的特征熵越大，它作为分母，可以校正信息增益容易偏向于取值较多的特征的问题。

对于第三个缺失值处理的问题，主要需要解决的是两个问题，一是在样本某些特征缺失的情况下选择划分的属性，二是选定了划分属性，对于在该属性上缺失特征的样本的处理。

对于第一个子问题，对于某一个有缺失特征值的特征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。

对于第4个问题，C4.5引入了正则化系数进行初步的剪枝。

C4.5算法的不足

C4.5虽然改进或者改善了ID3算法的几个主要的问题，仍然有优化的空间。

1. 由于决策树算法非常容易过拟合，因此对于生成的决策树必须要进行剪枝。C4.5的剪枝思路主要是两种，一种是预剪枝，即在生成决策树的时候就决定是否剪枝。另一个是后剪枝，即先生成决策树，再通过交叉验证来剪枝。
2. C4.5生成的是多叉树，即一个父节点可以有多个节点。很多时候，在计算机中二叉树模型会比多叉树运算效率高。如果采用二叉树，可以提高效率。
3. C4.5只能用于分类，如果能将决策树用于回归的话可以扩大它的使用范围。
4. C4.5由于使用了熵模型，里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算。如果能够加以模型简化可以减少运算强度但又不牺牲太多准确性的话，那就更好了。

CART算法对C4.5算法的改进

CART算法的全称是： Classification and Regression Tree 分类和回归树。从这个名字一望可知，它不仅可以用来做分类，还可以用来做回归。

CART 算法的运行过程和 ID3 及 C4.5 大致相同，不同之处在于：

1. CART 的特征选取依据不是增益量或者增益率，而是 Gini 系数（Gini Coefficient）。每次选择 Gini 系数最小的特征作为最优切分点。
2. CART 是一棵严格二叉树。每次分裂只做二分。

这里面要特别提到概念：Gini 系数（Gini Coefficient）。Gini 系数原本是一个统计学概念，20世纪初由意大利学者科拉多·基尼提出，是用来判断年收入分配公平程度的指标。Gini 系数本身是一个比例数，取值在0到1之间。

当 Gini 系数用于评判一个国家的民众收入时，取值越小，说明年收入分配越平均，反之则越集中。当 Gini 系数为0时，说明这一个国家的年收入在所有国民中平均分配，而当 Gini 系数为1时，则说明该国该年所有收入都集中在一个人手里，其余的国民没有收入。

在 Gini 系数出现之前，美国经济学家马克斯·劳伦茨提出了“收入分配的曲线”（又称劳伦茨曲线）的概念。下图就是一条劳伦茨曲线：

图中横轴为人口累计百分比，纵轴为该部分人的收入占全部人口总收入的百分比，红色线段表示人口收入分配处于绝对平均状态，而橘色曲线就是劳伦茨曲线，表现的是实际的收入分配情况。

我们可以看出，横轴75%处，如果依据红色线段，对应的纵轴也是75%，但是按照橘色曲线，则对应纵轴只有不到40%。

A 是红色线段和橘色曲线所夹部分面积，而 B 是橘色曲线下部分的面积。Gini 系数实际上就是

的比值。

Gini 系数的计算方法是：

对于二分类问题，若样本属于第一类的概率是 p ，则：

这时，如果 p = 0.5， 则 Gini 系数为0.5；如果 p = 0.9， 则 Gini 系数为0.18。0.18 < 0.5，根据 CART 的原则，当 p=0.9 时，这个特征更容易被选中作为分裂特征。

由此可见，对二分类问题中，两种可能性的概率越不平均，则越可能是更佳优越的切分点。

上面的例子虽然用的是二分类，但实际上，对于多分类，趋势是一样的，那些概率分布在不同可能性之间越不平均的特征，越容易成为分裂特征。

到了这里，可能有读者会误会 CART 只能做分类。但是实际上，无论是做分类还是做回归，都是一样的。

回归树和分类树的区别在于最终的输出值到底是连续的还是离散的，每个特征——也就是分裂点决策条件——无论特征值本身是连续的还是离散的，都要被当作离散的来处理，而且都是被转化为二分类特征，来进行处理：

• 如果对应的分裂特征是连续的，处理与 C4.5 算法相似；
• 如果特征是离散的，而该特征总共有 k 个取值，则将这一个特征转化为 k 个特征，对每一个新特征按照是不是取这个值来分 Yes 和 No。

相信看到这里，你已经对决策树有所了解，下一课我们动手做一个如何用决策树判断物体，并附有源代码和模型剪枝优化过程。