决策树如何进行剪枝？
分为预剪枝和后剪枝。
预剪枝的思想是在树中结点进行扩展之前，先计算当前的划分是否带来模型泛化能力的提升，如果不能，则不再继续生长子树。预剪枝对何时停止决策树的生长有几种方法
- 当树达到一定深度时，停止树的生长
- 当达到当前结点的样本数量小于某个阈值的时候，停止树的生长
- 计算每次分裂时对测试机的准确率提升，当小于某个阈值的时候，不再继续扩展
后剪枝的思想是让算法生成一颗完全生长的决策树，然背后从最底层向上计算是否剪枝。剪枝过程将子树删除，用一个叶子结点替代。相比于预剪枝，后剪枝方法通常可以得到泛化能力更强的决策树，但时间开销更大。常见的后剪枝方法有
- 代价复杂度剪枝（CCP）
- 错误率降低剪枝（REP）
- 悲观剪枝（PEP）
- 最小误差剪枝（MEP）
- CVP（Critical Value Pruning）
- OPP（Optimal Pruning）
