1. 前言

上一篇文章介绍了决策树的生成详细过程，由于决策树生成算法过多地考虑如何提高对训练数据的正确分类，从而构建过于复杂的决策树，这样产生的决策树往往对训练数据的分类很准确，却对未知的测试数据的分类没有那么准确，即出现过拟合现象。我们需要对已生成的决策树进行简化，这个简化的过程我们称之为剪枝(pruning)。

具体就是剪掉一些不重要的子树或叶结点，并将其根结点或父结点作为新的叶结点，从而简化分类树模型，得到最优的决策树模型。保证模型对预测数据的泛化能力。

决策树的剪枝往往通过极小化决策树整体的损失函数(loss funtion)或代价函数(cost funtion)来实现。

2.剪枝算法

2.1 为什么要剪枝

现象

接上一次讲的生成决策树，下面给出一张图。

• 横轴表示在决策树创建过程中树的结点总数，纵轴表示决策树的预测精度。
• 实线显示的是决策树在训练集上的精度，虚线显示的则是在一个独立的测试集上测量出来的精度。

可以看出随着树的增长， 在训练样集上的精度是单调上升的， 然而在独立的测试样例上测出的精度先上升后下降。

原因

• 原因1：噪声、样本冲突，即错误的样本数据。
• 原因2：特征即属性不能完全作为分类标准。
• 原因3：巧合的规律性，数据量不够大。

这个时候，就需要对生成树进行修剪，也就是剪枝。

2.2 如何进行剪枝

预剪枝

预剪枝就是在完全正确分类训练集之前，较早地停止树的生长。 具体在什么时候停止决策树的生长有多种不同的方法:
(1) 一种最为简单的方法就是在决策树到达一定高度的情况下就停止树的生长。
(2) 到达此结点的实例具有相同的特征向量，而不必一定属于同一类， 也可停止生长。
(3) 到达此结点的实例个数小于某一个阈值也可停止树的生长。

(4) 还有一种更为普遍的做法是计算每次扩张对系统性能的增益，如果这个增益值小于某个阈值则不进行扩展。

优点&缺点

• 由于预剪枝不必生成整棵决策树，且算法相对简单， 效率很高， 适合解决大规模问题。但是尽管这一方法看起来很直接， 但是【怎样精确地估计何时停止树的增长是相当困难的】。

• 预剪枝有一个缺点， 即视野效果问题 。 也就是说在相同的标准下，也许当前的扩展会造成过度拟合训练数据，但是更进一步的扩展能够满足要求，也有可能准确地拟合训练数据。这将使得算法过早地停止决策树的构造。

后剪枝

后剪枝，在已生成过拟合决策树上进行剪枝，可以得到简化版的剪枝决策树。

这里主要介绍四种：

• REP-错误率降低剪枝
• PEP-悲观剪枝
• CCP-代价复杂度剪枝
• MEP-最小错误剪枝

REP(Reduced Error Pruning)方法

对于决策树T 的每棵非叶子树S , 用叶子替代这棵子树. 如果 S 被叶子替代后形成的新树关于D 的误差等于或小于S 关于 D 所产生的误差, 则用叶子替代子树S

优点：

• REP 是当前最简单的事后剪枝方法之一。
• 它的计算复杂性是线性的。
• 和原始决策树相比，修剪后的决策树对未来新事例的预测偏差较小。

缺点：

• 但在数据量较少的情况下很少应用. REP方法趋于过拟合( overfitting) , 这是因为训练数据集中存在的特性在剪枝过程中都被忽略了, 当剪枝数据集比训练数据集小得多时 , 这个问题特别值得注意.

PEP(Pessimistic Error Pruning)方法

为了克服 R EP 方法需要独立剪枝数据集的缺点而提出的, 它不需要分离的剪枝数据集，为了提高对未来事例的预测可靠性, PEP 方法对误差估计增加了连续性校正(continuity correction)。关于PEP方法的数据解释待后续开专题梳理。

优点：

• PEP方法被认为是当前决策树事后剪枝方法中精度较高的算法之一
• PEP 方法不需要分离的剪枝数据集, 这对于事例较少的问题非常有利
• 它的计算时间复杂性也只和未剪枝树的非叶节点数目成线性关系 .

缺点：

PEP是唯一使用自顶向下剪枝策略的事后剪枝方法, 这种策略会带来与事前剪枝方法出现的同样问题, 那就是树的某个节点会在该节点的子孙根据同样准则不需要剪裁时也会被剪裁。

TIPS：

个人认为，其实以时间复杂度和空间复杂度为代价，PEP是可以自下而上的，这并不是必然的。

MEP(Minimum Error Pruning)方法

MEP 方法的基本思路是采用自底向上的方式, 对于树中每个非叶节点, 首先计算该节点的误差 Er(t) . 然后, 计算该节点每个分枝的误差Er(Tt) , 并且加权相加, 权为每个分枝拥有的训练样本比例. 如果 Er(t) 大于 Er(Tt) , 则保留该子树; 否则, 剪裁它。

优点：

• MEP方法不需要独立的剪枝数据集, 无论是初始版本, 还是改进版本, 在剪枝过程中, 使用的信息都来自于训练样本集.
• 它的计算时间复杂性也只和未剪枝树的非叶节点数目成线性关系 .

缺点：

类别平均分配的前提假设现实几率不大&对K太过敏感

对此，也有改进算法，我没有深入研究。

CCP(Cost-Complexity Pruning)方法

CCP 方法就是著名的CART(Classificationand Regression Trees)剪枝算法，它包含两个步骤:
(1) 自底向上，通过对原始决策树中的修剪得到一系列的树 {T0,T1,T2,…,Tt}， 其中Tia 是由Ti中的一个或多个子树被替换所得到的，T0为未经任何修剪的原始树，几为只有一个结点的树。

​ (2) 评价这些树，根据真实误差率来选择一个最优秀的树作为最后被剪枝的树。

缺点：

生成子树序列 T ( α) 所需要的时间和原决策树非叶节点的关系是二次的, 这就意味着如果非叶节点的数目随着训练例子记录数目线性增加, 则CCP方法的运行时间和训练数据记录数的关系也是二次的 . 这就比本文中将要介绍的其它剪枝方法所需要的时间长得多, 因为其它剪枝方法的运行时间和非叶节点的关系是线性的.

对比四种方法

① MEP比PEP不准确，且树大。两者都不需要额外数据集，故当数据集小的时候可以用。对比公式，如果类（Label）多，则用MEP；PEP在数据集uncertain时错误多，不使用。

② REP最简单且精度高，但需要额外数据集；CCP精度和REP差不多，但树小。

③ 如果数据集多（REP&CCP←复杂但树小）

④ 如果数据集小（MEP←不准确树大&PEP←不稳定）

3.总结

决策树是机器学习算法中比较容易受影响的，从而导致过拟合，有效的剪枝能够减少过拟合发生的概率。

剪枝主要分为两种：预剪枝(early stopping)，后剪枝，一般说剪枝都是指后剪枝，预剪枝一般叫做early stopping，后剪枝决策树在数学上更加严谨，得到的树至少是和early stopping得到的一样好。

预剪枝：

预剪枝的核心思想是在对每一个节点划分之前先进行计算，如果当前节点的划分并不能够带来模型泛化能力的提升就不再进行划分，对于未能够区分的样本种类（此时可能存在不同的样本类别同时存在于节点中），按照投票（少数服从多数）的原则进行判断。

简单一点的方法可以通过测试集判断划分过后的测试集准确度能否得到提升进行确定，如果准确率不提升变不再进行节点划分。

这样做的好处是在降低过拟合风险的同时减少了训练时间的开销，但是可能会出现欠拟合的风险：虽然一次划分可能会导致准确率的降低，但是再进行几次划分后，可能会使得准确率显著提升。

后剪枝：

后剪枝的核心思想是让算法生成一个完全决策树，然后从最低层向上计算决定是否剪枝。

同样的，方法可以通过在测试集上的准确率进行判断，如果剪枝后准确率有所提升，则进行剪枝。

后剪枝的泛化能力往往高于预剪枝，但是时间花销相对较大。

剪枝方法的选择

如果不在乎计算量的问题，后剪枝策略一般更加常用，更加有效。

后剪枝中REP和CCP通常需要训练集和额外的验证集，计算量更大。

有研究表明，通常reduced error pruning是效果最好的，但是也不会比其他的好太多。

经验表明，限制节点的最小样本个数对防止过拟合很重要，输的最大depth的设置往往要依赖于问题的复杂度，另外树的叶节点总个数和最大depth是相关的，所以有些设置只会要求指定其中一个参数。

无论是预剪枝还是后剪枝都是为了减少决策树过拟合的情况，在实际运用中，我使用了python中的sklearn库中的函数。

函数中的max_depth参数可以控制树的最大深度，即最多产生几层节点

函数中的min_samples_split参数可以控制最小划分样本，即当节点样本数大于阈值时才进行下一步划分。

函数中min_samples_leaf参数可以控制最后的叶子中最小的样本数量，即最后的分类中的样本需要高于阈值

上述几个参数的设置均可以从控制过拟合的方面进行理解，通过控制树的层数、节点划分样本数量以及每一个分类的样本数可以在一定程度上减少对于样本个性的关注。具体设置需要根据实际情况进行设置