后剪枝是什么？先让决策树长满，再从底部往上修剪

后剪枝（Post-pruning）是决策树防止过拟合的一种剪枝策略：先不加限制地让决策树完整地生长出来，然后再从下往上地考察树中的各个节点，把那些对提升模型效果没有帮助的分支剪掉，用一个叶子节点来代替。与之相对的是预剪枝，它在树生长的过程中就提前停止划分。

为什么需要后剪枝

一棵完整生长的决策树，会不断地把训练数据划分得越来越细，直到每个叶子节点中的样本几乎都属于同一个类别。这样的树在训练数据上的准确率很高，但它很可能把训练数据中的噪声和偶然的规律也学了进去，在新的数据上表现很差，这就是过拟合。剪枝就是要去掉那些只是在拟合噪声的分支，让决策树变得更简单、泛化能力更好。

后剪枝的过程

一种直观的做法是借助一个验证集，这叫错误率降低剪枝：先用训练集生成一棵完整的决策树；然后从最底层的非叶子节点开始，逐个地考察：如果把这个节点下面的整棵子树剪掉，用一个叶子节点代替它，叶子节点的类别是这个节点中样本最多的那个类别，模型在验证集上的准确率会不会提高或者至少不下降？如果会，就进行剪枝；否则就保留这棵子树。这样自底向上地考察完所有的节点，就得到了剪枝之后的决策树。

其他经典的后剪枝方法

代价复杂度剪枝：CART 决策树使用的方法，由 Leo Breiman 等人在 1984 年提出。它定义了一个综合考虑误差和树的复杂度的指标，也就是误差加上一个系数乘以叶子节点的数量。随着这个系数从零逐渐增大，可以依次剪掉那些“性价比”最低的分支，得到一系列从大到小的子树，最后用交叉验证从中选出效果最好的那一棵。scikit-learn 中的决策树就提供了这种剪枝方式。悲观剪枝：C4.5 决策树使用的方法，它不需要单独的验证集，而是直接在训练数据上，对每个节点的误差进行一个“悲观”的修正，以此来估计它在新数据上的误差，再据此决定是否剪枝。

后剪枝与预剪枝的比较

预剪枝在树生长的过程中就提前停止，训练的速度快，但它有一个问题：有些划分在当时看起来并不能提升效果，但继续往下划分，后续的分支却可能带来明显的提升。预剪枝因为“目光短浅”，可能会过早地停止，导致欠拟合。后剪枝是在看到完整的树之后再决定剪掉什么，能够考虑到更深层的划分所带来的效果，因此通常能保留更多有用的分支，欠拟合的风险更小，泛化能力往往也更好。它的缺点是需要先生成完整的树，再逐个考察大量的节点，训练的时间开销比预剪枝和不剪枝都要大得多。

在集成模型中

值得一提的是，在随机森林中，单棵决策树通常不进行剪枝，因为多棵树的投票平均本身就能有效地降低过拟合的风险。而在梯度提升树中，通常通过限制树的深度和叶子节点的数量来控制每棵树的复杂度，XGBoost 等实现也会在树生长完成之后，剪掉那些带来的增益低于阈值的分裂。