NO.43.tip： 决策树剪枝

背景

剪枝是机器学习和搜索算法中的一种数据压缩技术，通过去除树上非关键和冗余的部分来减少决策树的复杂度。剪枝降低了最终分类器的复杂度，通过减少过拟合来提高预测精度。

采用严格的停止标准往往会产生对训练集过拟合的大决策树。采用宽松的停止标准往往会产生小的、拟合度不足的决策树。为了解决这一难题，Breiman 等人在 1984 年开发了一种允许决策树对训练集过拟合的过程，然后通过删除对泛化精度无贡献的子分支，将过拟合的树剪成一棵较小的树。多种研究中已经表明，剪枝方法可以提高决策树的泛化性能。

剪枝的另一个关键动机是 Bratko 和 Bohanec 提出的“用准确性换取简单性”。当目标是产生一个足够准确、紧凑的概念描述时，剪枝是非常有用的。因为在这个过程中，初始决策树被看作一个完全准确的决策树，所以修剪后的决策树的准确性表明了它与初始树的接近程度。剪枝应该减少树的大小，且不降低交叉验证集所测量的预测精度。有多种剪枝技术，它们在优化决策树性能方面有所不同。大多数剪枝技术对节点进行自上而下或自下而上的遍历。如果剪枝操作提高了某个标准，那么某个节点就会被修剪。

Breiman 和 Gelfand 等人认为剪枝算法在决策树的建立中处于最重要的位置。1984 年，Breiman 在 CART 决策树中使用代价复杂度剪枝（Cost-Complexity Pruning，CCP）方法，该方法将目标函数加入复杂度的衡量标准，然而其复杂度过高。随后，1986 年，Quinlan 提出错误率降低剪枝（Reduced Error Pruning，REP）和悲观错误剪枝（Pessimistic Error Pruning，PEP）算法。REP 和 PEP 算法是自下而上进行的，它基于训练数据的误差评估，因此不用单独找剪枝数据集，但训练数据也会使错分误差偏向于训练集，因此需要加入修正值 $1/2$。同年，Niblett 和 Bratko I. 提出最小错误剪枝（Minimum Error Pruning，MEP）算法，MEP 算法是自下而上进行的，它与 PEP 方法相近，但是对类的计数处理是不同的。然而，这些剪枝算法并不能解决决策树中的生成规则。规则可以提供强大的生成规则。规则可以提供高度非线性函数，2008 年提出的 RuleFit 的算法就是从树木中提取规则。随着系数学习和优化算法的发展，2017 年，决策树的各种决策树剪枝算法的成熟，2016 年 Jonathan 等人提出了一种最优剪枝方法，从一系列剪枝方法进行剪枝后得到的树的集合里，找出最优剪枝的决策树。

剪枝过程大致可以分为两种类型：

• 预剪枝（pre-pruning）：通过替换决策树生成算法中的停止准则（例如，最大树深度或信息增益大于某一阈值）来实现树的简化。预剪枝方法被认为是更高效的方法，因为它们不会反映整个数据集，而是从一开始就保持小树。预剪枝方法有一个共同的问题，即视界限制效应。一般不希望停止准则过早终止诱导。
• 后剪枝（post-pruning）：是简化树的常见方法，用叶子代替中间节点和子树以提高复杂度。后剪枝不仅可以显著减小树的大小，还可以提高未见过的样本数据的分类精度。可能会出现在测试集上的预测准确率变差的问题，但树的分类准确率总体上会提高。

源与流

代价复杂度剪枝

CCP 算法的基本原理

代价复杂度剪枝方法在 1984 年 Breiman 的经典 CART 算法中首次提到并使用，是一种后剪枝方法。

假设对于一棵 CART 决策树，$R(T)$ 是决策树误差（代价），$f(T)$ 是一个返回树 $T$ 的叶子集合的函数。$\alpha$ 是一个正则化参数，表示两者的平衡系数，其值越大，树越小，反之树越大。

一棵树的好坏用下式衡量：

$$R_{\alpha }(T)=R(T)+\alpha |f(T)|\text{\hspace{1em}(1)}$$

$$R(T)=\sum _{t\in f(T)}r(t)\cdot p(t)=\sum _{t\in f(T)}R(t)\text{\hspace{1em}(2)}$$

其中，$\sum R(t)$ 表示每个叶子节点所产生的错误分类的误差之和。$p(t)=\frac{n(t)}{n}$，$n(t)$ 表示叶子节点 $t$ 所处理的样本记录数，$n$ 表示总的样本记录数。$r(t)=1-{\max }_{i}p(C_i|t)$ 表示误分类比例。

对一棵子树 $T_1$ 进行剪枝的过程如图 3.1 所示。对于待剪枝的决策树 $T$，将一棵以节点 $t$ 为根节点的子树 $T_t$ 替换为一个叶子节点，得到子树 $T-T_t$，那么 $R_{\alpha }(T-T_t)-R_{\alpha }(T)$ 就是剪枝节点为子树 $T_t$ 替换为一个叶子节点，得到子树 $T-T_t$ 降低决策树复杂度的同时带来的代价变化。

从式（1）和式（2）可以得出：

$$\begin{array}{rl}{R}_{\alpha }(T-T_t)-R_{\alpha }(T)& =R(T-T_t)-R(T)+\alpha (|f(T-T_t)|-|f(T)|)\\ & =R(t)-R(T_t)+\alpha (1-|f(T_t)|)\end{array}$$

令 ${\alpha }^{\prime }=\frac{R(t)-R(T_t)}{|f(T_t)|-1}$，则

$$\alpha =\frac{R(t)-R(T_t)}{|f(T_t)|-1}=\frac{R_{\alpha }(T-T_t)-R_{\alpha }(T)}{|f(T)|-1}={\alpha }^{\prime }+\frac{R_{\alpha }(T-T_t)-R_{\alpha }(T)}{|f(T_t)|-1}$$

也就是说，如果误差增加，${\alpha }^{\prime }$ 也随之增加。

CCP 算法的完整流程如下。

假设 ${\alpha }^{\prime }=0$，CART 算法构建的原始决策树为 $T^{\prime }$ 且已经使 $R(T)$ 最小化。

1. 初始化。
2. 步骤 1：从决策树 $T^i$ 选择分支节点 $t\in T^i$，将以分支节点 $t$ 为根节点的子树替换为叶子节点之后的决策树记为 $T_i^{\prime }$，通过评估子树 $R(t)$ 和决策树 $R(T_i^{\prime })$ 的误差，选择使下式最小化的分支节点 $t$：

$$g_i(t)=\frac{R(t)-R(T_i^{\prime })}{|f(T_i^{\prime })|-1}\text{\hspace{1em}(3)}$$

3. 步骤 2：假设选出的分支节点为 $t_1$，那么 ${\alpha }^2=\max \{{\alpha }^1,g_1(t_1)\}$，新得到的决策树为 $T^2=T^1-T_{t_1}$。
4. 步骤 3：从决策树 $T^i$ 选择分支节点 $t\in T^i$，将以分支节点 $t$ 为根节点的子树替换为叶子节点之后的决策树记为 $T_i^{\prime }$，最小化下式：

$$g_i(t)=\frac{R(t)-R(T_i^2)}{|f(T_i^2)|-1}\text{\hspace{1em}(4)}$$

这样，每一个步骤都会生成一个剪枝后的决策树和对应的 $\alpha$ 值。即一系列的决策树 $T^1$，且有 $T^1\supseteq T^2\supseteq \cdots \supseteq T^k\supseteq \cdots \supseteq \{\text{root}\}$。一系列的 ${\alpha }^i$ 值，且有 ${\alpha }^1⩽{\alpha }^2⩽\cdots ⩽{\alpha }^k⩽\cdots$。

错误率降低剪枝

REP 算法的基本原理

错误率降低剪枝法属于后剪枝算法，由 Quinlan 提出，是一种简单的剪枝方法。

在该方法中，可用的数据被分成两个样例集合：一个训练集用来形成学习到的决策树，一个分离的验证集用来评估这个决策树在后续数据上的精度，确切地说是用来评估修剪决策树的效果。这种方法的动机是：即使学习器可能会被训练集中的随机错误和巧合规律所误导，但验证集不大可能表现出同样的随机波动，所以验证集可以用来对过拟合训练集中的虚假特征提供防护检验。

其思路是自底向上，从已经构建好的完全决策树中找出一个子树，然后用子树的根节点代替这棵子树，作为新的叶子节点。叶子节点所表示的类别通过大多数原则确定，这样就构建出一个简化版决策树。然后使用交叉验证数据集来测试简化版本的决策树，看其错误率是不是降低了。如果错误率降低了，则可以用这个简化版的决策树来代替完全决策树，否则还采用原来的决策树。遍历所有的子树，直到针对交叉验证数据集无法进一步降低错误率为止。这虽然是一种有点朴素的修剪方法，但其具有速度快和简单的优点。

该剪枝方法考虑将决策树上的每个分支节点作为修剪的候选对象，决定是否修剪这个分支节点由如下步骤组成：

1. 删除以此节点为根的子树；
2. 使其成为叶子节点；
3. 赋予该叶子节点关联的训练数据的类别为属于此叶子节点的所有样本数据中最常见的分类；
4. 当修剪后的树对于验证集合的性能不会比原来的树差时，才真正删除该节点。

训练集合的过拟合使得验证集合数据能够对其进行修正，反复进行上面的操作，自底向上地处理节点，删除那些能够最大限度地提高验证集合的精度的节点，直到进一步修剪有害为止（有害是指修剪会降低验证集合的精度）。

REP 是最简单的后剪枝方法之一，不过由于使用了独立的测试集，与原始决策树相比，修改后的决策树可能偏向于过度修剪，这是因为训练数据集中存在的特性在剪枝过程中都被忽略了，当剪枝数据集比训练数据集小得多时，这个问题特别值得注意。尽管 REP 有这个缺点，不过 REP 仍然可作为一种基准来评价其他剪枝算法的性能。由于验证集合没有参与决策树的创建，所以用 REP 剪枝后的决策树对于测试样例的偏差要好很多，能够解决一定程度的过拟合问题。

悲观错误剪枝

PEP 算法的基本原理

悲观错误剪枝（PEP）是 Quinlan 为了克服 REP 方法需要独立剪枝数据集的缺点而提出的一种后剪枝算法，也属于后剪枝的一种。最小错误剪枝算法的主要思想是通过分别计算剪枝前与剪枝后的期望错误率 $E_k$，若剪枝后的 $E_k$ 变小，则剪枝，否则不进行剪枝。这里介绍了从一棵错误率分离的剪枝数据集。（1997 年 Floriana Esposito 对 PEP 算法做了适当修改，这里介〔？〕悲观错误剪枝根据剪枝前后的错误率来判定子树的修剪。由于我们还是用生成决策树时的训练样本，因此对于每个节点剪枝后的错误分类率一定是会上升的。该方法引入了统计学上连续修正（continuity correction）的概念来弥补 REP 中的缺陷，在评价子树的训练错误公式中添加了一个常数，以提高对未来样本数据的预测可靠性。

用 $n(t)$ 表示节点 $t$ 覆盖的样本总数，即 $t$ 中不属于节点 $t$ 所标识类别的样本数。以节点 $t$ 为根的子树 $T_t$ 覆盖了 $n(t)$ 个样本，节点 $t$ 中类别 $i$ 的样本个数为 $n_i(t)$，用 $e(t)$ 表示节点 $t$ 覆盖的错误样本个数，$T_1$ 为子树 $T$ 的所有内部节点（非叶子节点）的集合，$T_2$ 为子树 $T$ 的所有叶子节点的集合，$T_3=T_1\cup T_2$。假设 $r(T_t)$ 表示子树 $T_t$ 引起的分类错误，$r(t)$ 表示只由节点 $t$ 构成子树时的分类错误率，即节点 $t$ 作为叶子节点时的分类错误率，则

$$r(t)=\frac{e(t)}{n(t)}$$

表示节点 $t$ 上的分类错误率，也就是对以节点 $t$ 为根的子树 $T_t$ 进行剪枝后所得的分类错误率。$r(T_t)$ 表示子树 $T_t$ 上的分类错误率，计算方式如下：

$$r(T_t)=\frac{{\sum }_{s\in T_2}e(s)}{{\sum }_{s\in T_2}n(s)}\text{\hspace{1em}(5)}$$

把一棵子树（具有多个叶子节点）的分类用一个叶子节点来替代的话，在训练集上的错误分类率肯定会上升，但是在新数据上则不一定。于是我们需要为子树的误判计算加上一个经验性的惩罚因子。对于叶子节点 $t$，它覆盖了 $n(t)$ 个样本，其中有 $e(t)$ 个错误，那么该叶子节点的错误率为

$$\frac{e(t)+0.5}{n(t)}$$

这个 0.5 就是惩罚因子，对于子树 $T_t$，如果它有 $L$ 个叶子节点（即 $|T_t|=L$），那么该子树的错误分类率估计为

$$\frac{{\sum }_{i=1}^{L}e(i)+0.5L}{{\sum }_{i=1}^{L}n(i)}\text{\hspace{1em}(6)}$$

可以看到，一棵子树虽然具有多个子节点，但由于加上了惩罚因子，所以子树的错误分类率未必能占到便宜。剪枝后分支节点变成了叶子节点，其误判个数 $e(t)$ 也需要加上一个惩罚因子，变成 $e(t)+0.5$。值 0.5 称为二项概率分布近似的连续性修正因子，变成 $e(t)+0.5$。值 0.5 称为二项概率分布近似的连续性修正因子，〔？〕则可以参考文献 [13]。

假设 $\mathrm{SE}(e(T_t))$ 表示子树 $T_t$ 的错误分类率的标准差。由于可将误差近似看成二项式分布，根据 $\mu =np,{\sigma }^2=npq$（其中 $p$ 为每次实验成功的概率，$q=1-p$），可得

$$\mathrm{SE}(e(T_t))=\sqrt{\frac{({\sum }_{i=1}^{L}e(i)+0.5L)(n(t)-{\sum }_{i=1}^{L}e(i)-0.5L)}{n(t)}}\text{\hspace{1em}(7)}$$

如果

$$\sum _{i=1}^{L}e(i)+0.5L+\mathrm{SE}(e(T_t))⩾e(t)+0.5$$

则子树 $T_t$ 就会被剪掉。式（7）就是剪枝的标准。当然并不一定非要大于一个标准差，也可以给定任意的置信区间，通过设定一定的显著性因子，就可以估算出错误分类次数的上下界。

最小错误剪枝

MEP 算法的基本原理

1986 年 Niblett 和 Bratko 提出了最小错误剪枝算法。最小错误剪枝采用自底向上的方式对决策树进行剪枝，也属于后剪枝的一种。最小错误剪枝的主要思想是通过分别计算剪枝前与剪枝后的期望错误率 $E_k$，若剪枝后的 $E_k$ 变小，则剪枝，否则不进行剪枝。Niblett 与 Bratko 所提出的期望错误率 $E_k$ 的计算方法如下：

$$E_k=\frac{n-n_k+k-1}{n+k}\text{\hspace{1em}(8)}$$

其中，$n$ 为样本数，$k$ 为决策树分类的类别总数，$n$ 个样本中假设属于类 $c$ 的样本数目最大，设其样本数为 $n_c$。但需要注意的是，这个公式需要假设每个类别的概率是相等的。

剪枝的流程如下：

1. 对于树中的每个中间节点，计算对它进行剪枝后，即该节点成为叶子节点后的期望错误率 $E$；
2. 若该节点未被剪枝，则计算该节点下的加权期望错误率 $E_k^{\prime }$；
3. 比较 $E_k$ 与 $E_k^{\prime }$，若 $E_k⩾E_k^{\prime }$，则不进行剪枝；若 $E_k<E_k'$，则需要进行剪枝。

以上剪枝算法的特点

上面介绍的四种剪枝算法是常用的剪枝算法，它们的特点如下：

• 是否需要独立剪枝集：CCP 使用交叉验证方式而不需要独立剪枝集，REP、PEP、MEP 均需要独立剪枝集。
• 剪枝方式：CCP、REP 和 MEP 采取自底向上的剪枝方式，而 PEP 则采取自顶向下的剪枝方式。
• 误差估计：CCP 的误差估计使用交叉验证或标准误差，REP 利用剪枝集，PEP 使用连续性校正，MEP 采用基于 $m$ 的概率估计。
• 计算复杂度（假设 $n$ 表示非叶子节点数）：CCP 为 $O(n^2)$，REP 为 $O(n)$，PEP 为 $O(n)$，MEP 为 $O(n)$。

事实上，上述剪枝算法的误差估计都是基于期望错误率最小原则，选择期望错误率最小的子树剪枝。对树中的内部节点计算其剪枝/不剪枝可能出现的期望错误率，比较后加以取舍。