剪枝处理的作用及策略

## **1 概述**

**剪枝处理**是决策树学习算法用来解决**过拟合**问题的一种办法。

在决策树算法中，为了尽可能正确分类训练样本，节点划分过程不断重复，有时候会造成决策树分支过多，以至于将训练样本集自身特点当做泛化特点，而导致过拟合。因此可以采用剪枝处理去掉一些分支来降低过拟合的风险。

## 2 分类

剪枝的基本策略有**预剪枝（pre-pruning）** 和 **后剪枝（post-pruning）** 两种。

### 2.1 预剪枝

预剪枝是在构建决策树的同时进行剪枝工作，当发现分类有偏差时就及早停止，一旦停止，该节点就成为了叶子节点。

#### 2.1.1 方法

预剪枝的方法主要有以下几个方面：

1. 提前设定决策树的高度，当达到这个高度时，就停止构建决策树。
2. 当达到某节点的实例具有相同的特征向量，也可以停止树的生长。
3. 提前设定某个阈值，当达到某个节点的样例个数小于该阈值到的时候便可以停止树的生长，但这种方法的缺点是对数据量要求极大，无法处理数据量较小的训练样例。
4. 同样是设定某个阈值，每次扩展决策树后都计算其对系统性能的增益，若小于该阈值，则让它停止生长。

#### 2.1.2 缺点

预剪枝的显著缺点是视野效果。

* 因为剪枝是伴随着构建决策树同时进行的，构建者无法预知下一步可能会发生的事，会出现某种情况，在相同标准下，当前决策树不满足要求最开始的构建要求，构建者进行了剪枝，但实际上若进行进一步构建后，决策树又满足了要求。
* 这种情况下，预剪枝会过早停止决策树的生长。

### 2.2 后剪枝

* 后剪枝是人们普遍关注的决策树剪枝策略，与预剪枝恰好相反，后剪枝的执行步骤是先构造完成完整的决策树，再通过某些条件遍历树进行剪枝。
* 其主要思路是通过删除节点的分支并用树叶节点替换，剪去完全生长的树的子树，这个节点所标识的类别通过大多数原则（Majority Class Criterion）（既将一些子树删除而用叶子节点代替，这个叶节点所表示的类别用这棵子树中的大多数训练样本所属类别来进行标识）确定。

#### 2.2.1 分类

目前主要应用的后剪枝方法有四种，分别是：

1. **错误率降低剪枝（Reduced-Error Pruning，REP）**
2. **悲观错误剪枝（Pessimistic Error Pruning，PEP）**
3. **代价复杂度剪枝（Cost-Complexity Pruning，CCP）**

##### 2.2.1.1 错误率降低剪枝-REP

* **错误率降低剪枝法**是通过一个**新的验证集**来纠正树的**过拟合**问题。
* 对于决策树中的**每一个非叶子节点的子树**，我们将他**替换成一个叶子节点**，该叶子节点的类别用大多数原则来确定，这样就产生了一个新的相对简化决策树，然后比较这两个决策树在验证集中的表现。
  * 如果新的决策树在验证集中的正确率高，那么该子树就可以替换成叶子节点，从而达到决策树剪枝的目的。
* 该算法是**从下往上**依次遍历所有的子树，直至没有任何子树可以替换使得在验证集上的表现得以改进时，算法就可以终止。

实例如下：

![20190217164246269.png (840×407)](/media/202104/2021-04-01_173217.png)

假设上图是我们生成的决策树，我们要对其进行剪枝，使用**REP**算法。

1. 将节点 4 删掉替换成 8 和 9，测试在验证集上的表现：
   1. 若表现更好，则将节点 4 删掉并替换成 8 和 9 的并集。
   2. 若表现不好，则保留原树的形状。
2. 将节点 2 删掉替换成 8、9 和 5，测试在验证集上的表现。
3. 将节点 3 删掉替换成 6 和 7，测试其在验证集上的表现。

##### 2.2.1.2 悲观错误剪枝-PEP

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

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

具体的计算过程如下：

1. 对于一个叶节点它覆盖了 $N$ 个样本，其中有 $E$ 个错误，那么该叶节点的错误率为 $\frac{E+0.5}N$，这个 0.5 就是惩罚因子。
2. 对于一棵树，他有 $L$ 个叶子节点，那么该子树的**误判率**估计为

$$
p=\frac{{\displaystyle\sum_{i=1}^L}E_i+0.5L}{{\displaystyle\sum_{i=1}^L}N_i}
$$

3. 我们假设在子树中，每一个样本的误判服从一个二项分布 $B(N,p)$，其中 $N$ 表示子树所包含的所有样本个数。
4. 所以，在剪枝前，其期望的误判数为：

$$
E(剪枝前误判数)=N*p
$$

其误判的标准差为：

$$
STD(剪枝前误判数)=\sqrt{N*p*(1-p)}
$$

5. 在剪枝之后把子树替换为叶子节点后，该叶子的误判次数也是一个伯努利分布，其概率误判率 $e$ 为 $(E+0.5)/N$，因此叶节点的误判次数均值为：

$$
E(剪枝后误判数)=N*e
$$

6. 当子树的误判个数大于对应节点的误判个数一个标准差之后，就决定剪枝，即剪枝条件为：

$$
E(剪枝后误判数)-STD(剪枝前误判数)<E(剪之前误判数)
$$

具体实例如下：

![20190218003206717.png (771×399)](/media/202104/2021-04-02_115820.png)

1. 对于 $T4$ 节点而言，剪枝剪枝前后的计算过程如下：

$$
E(T7)=0\\E(T8)=2\\E(T9)=1\\E(T10)=1\\E(T4)=7
$$

> 上面的 E(T8)=2 并不代表期望，只代表错误的个数：
>
> 比如 T8 这个叶节点，类 1 有 4 个，类 2 有两个，那么他就代表类 1（因为肯定取个数多的那个类作为该节点的所有分类）。因此对于训练集，这个 T8 节点分错的就 2 个，即他把类 2 的两个样本分成了类 1，也就是分错了两个。

所以，剪枝前的误判概率为：

$$
p=\frac{(0+2+1+1)+4*0.5}{20}=0.3
$$

2. 所以：

$$
E(剪枝前误判数)=20*0.3=6
$$

$$
STD(剪枝前误判数)=\sqrt{20*0.3*0.7}=2.05
$$

3. 在我们对 T4 进行剪枝后，即 T4 直接作为叶节点，剪枝后的我误判概率为：

$$
e=\frac{7+0.5}{20}=0.375
$$

剪枝后的误判期望数为：

$$
E(剪枝后误判数)=20*0.375=7.5
$$

剪枝条件为：

$$
7.5-2.05<6
$$

满足剪枝条件，因此我们需要对 T4 进行剪枝。

##### 2.2.1.3 代价复杂度剪枝-CCP

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

* **代价**指的是在剪枝过程中因子树 $T_t$ 被叶节点替代而增加的错分样本。
* **复杂度**表示剪枝后子树 $T_t$ 减少的叶节点数。
* $\alpha$ 则表示剪枝后树的复杂度降低程度与代价间的关系，定义为：

$$
  \alpha=\frac{R(t)-R(T_t)}{|N|-1}
  $$

* $R(t)$ 表示节点 $t$ 的错误代价，$R(t)=r(t) \ast p(t)$
    * $r(t)$ 表示节点 $t$ 的错分样本率。
    * $p(t)$ 表示节点 $t$ 中样本占全部样本的比例。
    * $|N|$ 表示子树 $T_t$ 中的叶节点数。

CCP算法可以分为下面两个步骤：

1. 按照上述公式**从下到上**计算每一个非叶节点的$\alpha$值，然后每一次都**剪掉具有最小$\alpha$值的子树**，从而得到一个集合$\{T_0,T_1,T_2,...,T_m\}$，其中，$T_0$表示完整的决策树，$T_m$表示根节点。
2. 按照**真实的错误率**在集合$\{T_0,T_1,T_2,...,T_m\}$中选出一个最好的决策树。

具体实例如下：

![20190218110859320.png (771×399)](/media/202104/2021-04-02_145643.png)

1. 假设数据有100条，从下往上，首先计算$T_5$的$\alpha$值：

$$
R(T_5)=\frac2{12} \ast \frac{12}{100}=0.02
$$

$$
R(T_5t)=\sum_i(R_i)= \frac06 \ast \frac6{100} + \frac26 \ast \frac6{100}=0.02
$$

$$
\alpha=\frac{0.02-0.02}{2-1}=0
$$

2. 同理，$T_6$的$\alpha$为0.03，由于0<0.03，所以，我们将$T_5$剪掉就可以得到一棵新树。

### 3 参考文献

1. [C4.5 算法剪枝 1](https://zhuanlan.zhihu.com/p/165647069)。
2. [决策树的剪枝：REP/PEP/CCP 算法](https://blog.csdn.net/weixin_43216017/article/details/87534496)。