决策树剪枝

为什么要剪枝
一颗完全生长的决策树难免会遇到过拟合的情况。因此，我们需要对决策树进行剪枝，提升模型的泛化能力。
决策树的剪枝操作通常有两种方法，预剪枝与后剪枝。

预剪枝
预剪枝的核心思想是在树中节点进行扩展之前，先计算当前的划分是否能带来模型泛化能力的提升，如果不能，则不再继续生长子树。此时可能存在不同类别的样本同时存于节点中，可以按照多数投票的原则判断该节点所属类别。预剪枝对于何时停止决策树的生长有以下几种方法：
(1) 当树达到一定深度的时候，停止树的生长；
(2) 当到达当前节点的样本数量小于某个阈值的时候，停止树的生长；
(3) 计算每次分裂对测试集的准确度的提升，当小于某个阈值的时候，不再继续生长。
预剪枝具有思想直接、算法简单、效率高等特点，适合解决大规模数据的问题。但是，对于上述阈值，需要经验判断。此外，预剪枝有欠拟合的风险，因为，虽然当前的划分会导致测试集准确率降低或提升不高，但在之后的划分中，准确率可能会有显著提升。

后剪枝
后剪枝的核心思想是让算法生成一颗完全生长的决策树，然后自底向上计算是否剪枝。剪枝过程将子树删除，有一个叶子节点替代，该节点的类别同样用投票决定。同样，后剪枝也可以通过在测试集上的准确率来判断，如果剪枝过后准确率有所提升，则进行剪枝。相比于预剪枝，后剪枝的泛化能力更强，但是计算开销会更大。

**后剪枝方法：**错误率降低剪枝(Reduced Error Pruning,REP)、悲观剪枝(Pessimistic Error Pruning,PEP)、代价复杂度剪枝(Cost Complexity Pruning,CCP)、最小误差剪枝(Minimum Error Pruning,MEP)、CVP(Critical Value Pruning)、OPP(Optimal Pruning)等。

CCP代价复杂度剪枝：
(1) 从完整决策树$T_0$开始，生成一个子树序列$\{T_0,T_1,T_2,...,T_n\}$，其中$T_{i+1}$由$T_i$生成。$T_n$为树的根节点（剪到最后只剩根节点）。
(2) 在子树序列中，根据真实误差选择最佳的决策树。
详细剪枝步骤：
步骤(1)从${T_0}$开始，剪枝$T_i$中关于训练数据集合误差增加最小的分支以得到$T_{i+1}$。具体的，当一棵树$T$在节点$t$处剪枝时，它的误差增加可以用$R(t)-R(T_t)$表示，其中$R(t)$表示进行剪枝之后的该节点误差，$R(T_t)$表示未进行剪枝时子树$T_t$的误差。考虑到树的复杂性因素，我们用$|L(T_t)|$表示子树$T_t$的叶子节点个数，则树在节点$t$处剪枝后的误差增加率为$\alpha = \frac{R(t)-R(T_t)} {|L(T_t)|-1}$ 在得到$T_t$后，我们每一步选择$\alpha$最小的节点进行剪枝。

步骤(2),我们需要从子树序列中选出真实误差最小的决策树。CCP给出了两种常用的方法：一种是基于独立剪枝数据集，该方法与REP类似，但是由于只能从子树序列$\{T_0,T_1,T_2,...,T_n\}$中选择最佳决策树，而非像REP能在所有可能的子树中寻求最优解，因此模型效果上会有一定的不足。另一只方案是采取K折交叉验证来选取最优决策树。

总结
代价复杂度剪枝使用交叉验证策略的时候，不需要用到测试数据集，精度与REP差不多，但形成的树复杂度小。但是，由于生成子树序列的时间复杂度与原始决策树的非叶子节点个数呈现二次关系，导致算法相比REP、PEP、MEP等线性复杂度的后剪枝方法运行时间更大。

剪枝过程在决策树模型中占据着极其重要的地位，有很多研究表明，剪枝比树的生成更为关键。对于不同划分标准生成的过拟合决策树，在经过剪枝之后都能保留最重要的属性划分，因此最终的性能差距并不大。