决策树的剪枝：REP/PEP/CCP算法

当我们输入的原始数据有较多的变量时，通过决策树算法生成的决策树可能会非常的庞大。这样的一颗决策树在训练集上有很好的表现，但是在测试集上的表现往往不甚理想，这样的问题也被叫做过拟合问题。面对这样的问题，我们一般所采用的方法是对决策树进行剪枝操作。

本文详细介绍了三种剪枝算法，并配以计算实例。

文章目录

• 决策树的过拟合问题
• 决策树的剪枝
• 预剪枝
• 后剪枝
• 常见的后剪枝算法
• 错误率降低剪枝法
• 悲观剪枝法
• 代价复杂度剪枝法

决策树的过拟合问题

决策树算法生成的决策树非常庞大，每个变量都被详细地考虑过。在每一个叶节点上，只要继续分支会有信息增益的情况，不管信息增益有多大，都会进行分支操作。最终所达到的目的是决策树的叶节点所覆盖的训练样本都属于同一类。

如果我们用这个决策树来对训练集进行分类的话，那么这颗树的表现非常好。但是在测试集上的表现就远没有在训练集上的表现好，这就是过拟合问题。

决策树的剪枝

顾名思义，树的剪枝就是剪掉树的一些枝叶，考虑大决策树的枝代表着逻辑判断，也代表着分类后的子集。决策树的剪枝就是删掉一些不必要的逻辑判断，并且将子集合并。这样确实会造成在训练集上子集不纯的现象，但是因为我们最终目标是模型在测试集上的效果，所以牺牲在训练集上的效果换取解决测试集的过拟合问题这样的做法也是值得的。决策树剪枝可以分为两类，一类是预剪枝，一类是后剪枝。

预剪枝

预剪枝就是在生成决策树的同时进行剪枝。正常决策树的生成是只要有信息增益就要进行分支。预剪枝就是设定一个阈值，只有在信息增益大于这个阈值的时候（也即是在分类后的信息混乱程度减小程度大于一定标准的时候）才进行分类。如果在信息增益过小的情况下，即使存在信息增益的现象，也不会对其进行分支。预剪枝的思想比较简单，但在实际应用中，预剪枝的表现并不是很好。所以，目前我们基本都是使用后剪枝方法。

后剪枝

后剪枝就是在决策树构造完成后进行剪枝。剪枝的过程是对拥有相同父节点的一组节点进行检查，如果将其合并，熵增小于某一阈值，那么这一组节点可以合并一个节点。如果将其合并后熵增大于这个阈值，那么说明将其分枝是合理的。后剪枝就是删除一些子树，然后用其叶节点代替。这个叶节点代表的子集不一定都是“纯”的。那么，这个叶子节点所标识的类别通过大多数原则确定。大多数原则就是指这个叶节点所代表的子集中大多数的类别来表示这个叶节点。

常见的后剪枝算法

错误率降低剪枝法

错误率降低剪枝法(Reduced-Error Pruning)简称REP方法。

REP方法是通过一个新的验证集来纠正树的过拟合问题。对于决策树中的每一个非叶子节点的子树，我们将它替换成一个叶子节点，该叶子节点的类别用大多数原则来确定，这样就产生了一个新的相对简化决策树，然后比较这两个决策树在验证集中的表现。

如果新的决策树在验证集中的正确率较高，那么该子树就可以替换成叶子节点，从而达到决策树剪枝的目的。

该算法是从下往上依次遍历所有的子树，直至没有任何子树可以替换使得在验证集上的表现得以改进时，算法就可以终止。

实例：
假设上图是我们生成的决策树，我们要对其进行剪枝，使用REP算法。
Step 1： 将节点4删掉替换成8和9，测试在验证集上的表现，若表现更好，则将节点4删掉并替换成8和9的并集，若表现不好则保留原树的形状。
Step 2： 将节点2删掉替换成8、9和5，测试在验证集上的表现
Step 3： 将节点3删掉替换成6和7，测试在验证集上的表现

悲观剪枝法

悲观剪枝法(Pessimistic Error Pruning)简称PEP方法。

上文的REP方法思想简单且易于使用，不过最大的问题在于它需要一个新的验证集来修正我们的决策树。在PEP方法中，我们不需要新的验证集。

PEP方法也是根据剪枝前后的错误率来决定是否剪枝。和REP不同之处在于：PEP不需要新的验证集，并且PEP是自上而下剪枝的。由于我们还是用生成决策树时相同的训练样本，那么对于每个节点剪枝后的错分率一定是会上升的，因此在计算错分率时需要加一个惩罚因子0.5。

对于一叶节点，它覆盖了N个样本，其中有E个错误，那么该叶子节点的错误率为（E+0.5）/N。这个0.5就是惩罚因子，那么一颗子树，它有L个叶子节点，那么该子树的误判率估计为：
$p =\dfrac{\sum_{i=1}^{L}E_i+0.5L}{\sum_{i=1}^{L}N_i}$p=∑i=1L​Ni​∑i=1L​Ei​+0.5L​
我们假设在子树中每一个样本的误判服从一个二项分布$B(N,p)$B(N,p)，其中N表示子树所包含的所有样本个数。

所以，在剪枝前，其期望的误判数为：
$E(剪枝前误判数) = N*p$E(剪枝前误判数)=N∗p
其误判的标准差为：
$std(剪枝前误判数) = \sqrt{N*p*(1-p)}$std(剪枝前误判数)=N∗p∗(1−p)​
在剪枝之后，把子树替换成叶节点后，该叶子的误判次数也是一个伯努利分布，其概率误判率e为(E+0.5)/N，因此叶节点的误判次数均值为:
$E(剪枝后误判数) = N*e$E(剪枝后误判数)=N∗e

当子树的误判个数大于对应叶节点的误判个数一个标准差之后，就决定剪枝。剪枝条件为：$E(剪枝后误判数) -std(剪枝前误判数)&lt;E(剪枝前误判数)$E(剪枝后误判数)−std(剪枝前误判数)<E(剪枝前误判数)

实例：（实例出处见水印）

对于节点T4而言，剪枝前后的计算过程如下：
$E(T7)=0$E(T7)=0 ；$E(T8) = 2$E(T8)=2；$E(T9) = 1$E(T9)=1；$E(T10) = 1$E(T10)=1
$E(T4) = 7$E(T4)=7
所以，剪枝前的误判概率为：$p = \dfrac{(0+2+1+1)+4*0.5}{20} = 0.3$p=20(0+2+1+1)+4∗0.5​=0.3所以：$E(剪枝前误判数) =20*0.3=6$E(剪枝前误判数)=20∗0.3=6 $std(剪枝前误判数) = \sqrt{20*0.3*0.7}=2.05$std(剪枝前误判数)=20∗0.3∗0.7​=2.05

在我们对T4进行剪枝后，即将T4直接作为叶节点，剪枝后的误判概率$e = \dfrac{7+0.5}{20}=0.375$e=207+0.5​=0.375剪枝后的误判期望数为：$E(剪枝后误判数) = 20*0.375 = 7.5$E(剪枝后误判数)=20∗0.375=7.5

剪枝条件为：
$7.5 - 2.05 &lt; 6$7.5−2.05<6
因此满足条件，所以我们将把T4节点剪枝。

代价复杂度剪枝法

代价复杂度算法(Cost-Complexity Pruning)简称为CCP算法。

CCP算法为子树$T_t$Tt​定义了代价和复杂度，以及一个衡量代价与复杂度之间关系的参数α。

代价指的是在剪枝过程中因子树$T_t$Tt​被叶节点替代而增加的错分样本;
复杂度表示剪枝后子树$T_t$Tt​减少的叶结点数;
α则表示剪枝后树的复杂度降低程度与代价间的关系，定义为:
$\alpha = \dfrac{R(t)-R(T_t)}{|N|-1}$α=∣N∣−1R(t)−R(Tt​)​
其中，$R(t)$R(t)表示节点t的错误代价，$R(t) = r(t)*p(t)$R(t)=r(t)∗p(t)
$r(t)$r(t)表示节点t的错分样本率；
$p(t)$p(t)表示节点t中样本占全部样本的比例
$|N|$∣N∣表示子树$T_t$Tt​中的叶节点数

CCP算法可以分为两个步骤，
Step 1： 按照上述公式从下到上计算每一个非叶节点的$\alpha$α值，然后每一次都剪掉具有最小$\alpha$α值的子树。从而得到一个集合$\left\lbrace T_0,T_1,T_2,...,T_M\right\rbrace${T0​,T1​,T2​,...,TM​} ，其中，$T_0$T0​表示完整的决策树，$T_M$TM​表示根节点
Step 2： 根据真实的错误率在集合$\left\lbrace T_0,T_1,T_2,...,T_M\right\rbrace${T0​,T1​,T2​,...,TM​} 选出一个最好的决策树

实例：（实例出处见水印）

假设数据有100条，从下往上，首先计算$T_5$T5​的$\alpha$α值，
$R(T_5) = \dfrac{2}{12}*\dfrac{12}{100} = 0.02$R(T5​)=122​∗10012​=0.02
$R(T_5t) = \sum_i(R_i) = \dfrac{0}{6}*\dfrac{6}{100}+\dfrac{2}{6}*\dfrac{6}{100} =0.02$R(T5​t)=i∑​(Ri​)=60​∗1006​+62​∗1006​=0.02
$\alpha = \dfrac{0.02-0.02}{2-1} =0$α=2−10.02−0.02​=0
同理，$T_6$T6​的$\alpha$α为0.03，由于$0&lt;0.03$0<0.03，此时，我们将$T_5$T5​剪掉而得到一颗新树。