基于决策树的算法问题解惑：ID3、C4.5 、CART树

ID3算法

ID3算法就是用信息增益来判断当前节点应该用什么特征来构建决策树。信息增益大，则越适合用来分类。

它计算每一个特征的信息增益，增益最大的特征作为分裂特征，该特征每一个值都是一个子节点，这样所有样本就被分到了子节点上，然后对每一个子节点上的样本再分裂，之前已经分裂的特征就丢弃了，也不起作用了。

它的缺点：

• a)ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。万一这个特征每个值都是不一样的，这个特征就可以把所有样本分类完，其他特征不需要了。也就过拟合了。
• b)ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值，各为1/2，另一个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大。
• c) ID3算法对于缺失值的情况没有做考虑。
• d) 没有考虑过拟合的问题。过拟合问题上面有讲到。

C4.5算法

C4.5算法解决了上述的四个问题，我们看下是如何解决的：

• 1、连续特征的

  对于样本某个特征，根据特征值排序，C4.5取相邻值的平均数，小于这个平均值的归一类，大于或等于的归一类，这样就分为了两类样本，但是这里要计算每个平均数的信息增益，取信息增益最大的值作为切割点，这样样本就被分成了两类，同时这个特征可以用于后续子树的分裂中。

• 2、特征值多造成优先选择的问题

  提出信息增益比，它是信息增益和特征熵的比值。特征数越多的特征对应的特征熵越大，它作为分母，可以校正信息增益容易偏向于取值较多的特征的问题。

• 3、缺失值问题

  将缺失特征值分为一类，其他作为另一类，在计算时还会计算占比，防止因为缺失值比较多导致计算信息增益偏小。乘上一个系数，这个系数是无特征A缺失的样本加权后所占加权总样本的比例。比如100个样本，其中40个样本有A特征的值，另外60个特征A特征的值缺失。那么我们就只用这40个样本来计算信息A特征对应的信息增益比，计算完毕后乘以0.4即可。

• 4、过拟合问题

  正则化系数进行初步的剪枝，错误率降低剪枝REP，悲观错误剪枝PEP，代价复杂度剪枝CCP，基于错误的剪枝EBP。

缺点：

• 1)由于决策树算法非常容易过拟合，因此对于生成的决策树必须要进行剪枝。剪枝的算法有非常多，C4.5的剪枝方法有优化的空间。思路主要是两种，一种是预剪枝，即在生成决策树的时候就决定是否剪枝。另一个是后剪枝，即先生成决策树，再通过交叉验证来剪枝。后面在下篇讲CART树的时候我们会专门讲决策树的减枝思路，主要采用的是后剪枝加上交叉验证选择最合适的决策树。
• 2)C4.5生成的是多叉树，即一个父节点可以有多个节点。很多时候，在计算机中二叉树模型会比多叉树运算效率高。如果采用二叉树，可以提高效率。这里肯定大家有些疑惑，连续值不是做二分法了吗？为啥还是多叉树？这里主要是因为如果离散特征值多于两个，那么C4.5会在节点上根据特征值划分出多叉树。
• 3)C4.5只能用于分类，如果能将决策树用于回归的话可以扩大它的使用范围。
• 4)C4.5由于使用了熵模型，里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算。如果能够加以模型简化可以减少运算强度但又不牺牲太多准确性的话，那就更好了。

CART树

针对上述问题，CART树，有什么改动优化吗？我们来看下

• 大量的对数运算。能不能简化模型同时也不至于完全丢失熵模型的优点呢？

  CART分类树算法使用基尼系数来代替信息增益比，基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。

  G i n i ( p ) = ∑ k = 1 K p k ( 1 − p k ) = 1 − ∑ k = 1 K p k 2 Gini(p)=\sum_{k=1}^{K}p_k(1-p_k)=1-\sum_{k=1}^{K}p_{k}^2 Gini(p)=k=1∑K​pk​(1−pk​)=1−k=1∑K​pk2​

  p k p_k pk​表示是离散值占样本的数的比例。如果从样本角度来表达这个公式，则：

G i n i ( D ) = 1 − ∑ k = 1 K ( ∣ D k ∣ ∣ D ∣ ) 2 Gini(D)=1-\sum_{k=1}^{K}(\frac{|D_k|}{|D|})^2 Gini(D)=1−k=1∑K​(∣D∣∣Dk​∣​)2

如果一个特征值把数据集划分了两类，那么这两类的计算公式为：

G i n i ( D , A ) = D 1 D G i n i ( D 1 ) + D 2 D G i n i ( D 2 ) Gini(D,A)=\frac{D_1}{D}Gini(D_1)+\frac{D_2}{D}Gini(D_2) Gini(D,A)=DD1​​Gini(D1​)+DD2​​Gini(D2​)

对于连续值，我们通过值切分为两类，这样计算更加方便。

• 对连续特征和离散特征都离散化

  连续特征离散比较简单，就是根据值划分，大于这个值作为一类，小于这个值作为一类，计算基尼系数，离散值同样处理，这样CART树构建的就是一个二叉树。

建立一棵树的逻辑都差不多，没什么特殊的问题。如果遇到一个子树结构里很多样本是不同的结果的，怎么处理预测值？分类树是采用分类最多的类别作为分类结果的。

CART回归树建立算法

什么是回归树，什么是分类树。两者的区别在于样本输出，如果样本输出是离散值，那么这是一颗分类树。如果果样本输出是连续值，那么那么这是一颗回归树。除了概念的不同，CART回归树和CART分类树的建立和预测的区别主要有下面两点：

• 1)连续值的处理方法不同
• 2)决策树建立后做预测的方式不同

我们看一下回归模型中的不同点：

• 回归模型使用了常见的和方差的度量方式，CART回归树的度量目标是，对于任意划分特征A，对应的任意划分点s两边划分成的数据集D1和D2，求出使D1和D2各自集合的均方差最小，同时D1和D2的均方差之和最小所对应的特征和特征值划分点。这里就采用了mse 计算误差，从而作为切分节点的依据。
• 回归树输出不是类别，它采用的是用最终叶子的均值或者中位数来预测输出结果

剪枝

主要参考：1. CART分类树算法的最优特征选择方法

由于决策树容易过拟合，需要剪枝算法来防止过拟合，类似于线性回归的正则化，来增加决策树的泛化能力。但是，有很多的剪枝方法，我们应该这么选择呢？CART采用的办法是后剪枝法，即先生成决策树，然后产生所有可能的剪枝后的CART树，然后使用交叉验证来检验各种剪枝的效果，选择泛化能力最好的剪枝策略。

评估剪枝的损失函数如下：

C a ( T 1 ) = C a ( T 1 ) + a ∣ T 1 ∣ C_a(T_1) = C_a(T_1) + a|T_1| Ca​(T1​)=Ca​(T1​)+a∣T1​∣

其中 C a ( T 1 ) C_a(T_1) Ca​(T1​)表示树 T 1 T_1 T1​的损失函数，回归树为均方差，分类树为基尼系数。正常来说，剪枝之后误差更大了，因为不剪枝，子树将样本划分的更精细化，分类越准确，误差就越小，所以利用两者差来做分析，得到 a a a系数，这样利用这个值来进行剪枝。

具体的算法流程就参考上面的链接吧。

剪枝疑问

• 什么时候需要剪枝呢？

  就是子树不剪枝的损失比剪枝的损失大，即满足：

  C a ( T 1 ) > C a ( T ) C a ( T 1 ) + a ∣ T 1 ∣ > C a ( T ) + a a > C a ( T ) − C a ( T 1 ) ∣ T 1 ∣ − 1 C_a(T_1) >C_a(T) \\ C_a(T_1) + a|T_1| > C_a(T)+a\\ a>\frac{C_a(T)-C_a(T_1)}{|T_1| -1} Ca​(T1​)>Ca​(T)Ca​(T1​)+a∣T1​∣>Ca​(T)+aa>∣T1​∣−1Ca​(T)−Ca​(T1​)​

  所以对于每个节点，满足不等式的就剪枝，也就是说如果我们给定一个a值，小于这个a值的节点需要剪枝。

• 剪枝过程

  剪枝过程就是选取a的值，从树的下方往上，不停的剪枝，每次取a的值建议都是在之前已经剪枝的树上继续剪枝，这样每一个a都对应一颗剪枝的树，CART剪枝算法是递归算法，即从下往上开始剪枝，直到根结点，从而每次剪枝时由alpha产生的g(t)，下层要小于上层，上层不存在更小的g(t)，这点在理论上应该成立，不然剪枝会发生混乱。

• 这个 a m i n a_{min} amin​在剪枝选择的过程中不断减少。可以减少后面算法中一些无谓的剪枝决策。不使用它也是可以的，不过算法中M的集合就会变大，多很多没有意义的计算。

• 为什么要遍历所有的 a k a_k ak​

  每遍历一次，就会对树做剪枝，对应得到一个剪枝后的树，但是我们不清楚那个 a k a_k ak​最好，所以遍历一次，得到多有 a k a_k ak​的对应子树，这样可以得到做交叉验证。

• 假如 有4个变量，每个变量有10个值(连续变量)，那么去计算每个变量的每个划分点的均方误差来选择优先的变量和划分点，其实就是去计算4*9 = 36次

• 预测树的节点值

  我猜 你说的是sklearn里面预测prob是怎么来的，这个sklearn官方文档里面已经有解释了，也就是在该叶子节点里，最终确定的类别对应的训练样本数占划分到该叶子节点所有训练样本数的比例。

  比如该叶子节点用训练样本建立决策树时候，划分到5个样本，4个类别0, 1个类别1的。那么我们用投票法确定该叶子节点类别为0.当有一个需要预测的样本在走了一遍决策树后划分到了该叶子节点，那么它的prob就是0.8。

• 剪枝的Gini计算

  剪枝了T就是叶子节点，那么所有的样本都在该节点，自然可以计算该节点的基尼系数，或者说基尼不纯度。如果没有剪枝，则T是内部节点，它下面有若干叶子区域节点，可以分别计算各个叶子节点区域的基尼系数，最后按各个叶子节点的样本数量占比来加权求和，计算该内部节点的基尼系数。

• 根据 a a a剪枝的时候

  每次的迭代是基于剪枝的决策树再剪枝。其实这也是优化的结果，因为完整的树结构，就又要重新剪裁一下，浪费了时间。

优点

首先我们看看决策树算法的优点：

• 1）简单直观，生成的决策树很直观。
• 2）基本不需要预处理，不需要提前归一化，处理缺失值。
• 3）使用决策树预测的代价是𝑂(𝑙𝑜𝑔2𝑚)。 m为样本数。
• 4）既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。
• 5）可以处理多维度输出的分类问题。
• 6）相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以得到很好的解释
• 7）可以交叉验证的剪枝来选择模型，从而提高泛化能力。
• 8） 对于异常点的容错能力好，健壮性高。

缺点

• 1）应该大家有注意到，无论是ID3, C4.5还是CART,在做特征选择的时候都是选择最优的一个特征来做分类决策，但是大多数，分类决策不应该是由某一个特征决定的，而是应该由一组特征决定的。这样决策得到的决策树更加准确。这个决策树叫做多变量决策树(multi-variate decision tree)。在选择最优特征的时候，多变量决策树不是选择某一个最优特征，而是选择最优的一个特征线性组合来做决策。这个算法的代表是OC1。
• 2）如果样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习里面的随机森林之类的方法解决。
• 3）决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
• 4）寻找最优的决策树是一个NP难的问题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善。
• 5）有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。
• 6）如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。

参考文档

1. CART分类树算法的最优特征选择方法