决策树剪枝是机器学习中的一种技术，通过移除决策树中预测能力较低的部分来减小树的规模。其主要目标是通过降低复杂度和缓解过拟合来提升模型在未见数据上的泛化能力，同时增强可解释性并减少训练和推理时间。
剪枝之所以必要，是因为完全生长的决策树往往过度拟合训练数据，捕捉到噪声和异常值，导致在新数据上表现不佳。通过简化树结构，剪枝以训练误差的少量增加换取验证误差的更大减少，从而得到更稳健的模型。
剪枝类型
剪枝方法分为两大类：预剪枝（也称前向剪枝）和后剪枝（后向剪枝）。
预剪枝在树构建过程中满足特定条件时停止生长。常见条件包括最大深度、每个叶节点的最小样本数、最小信息增益阈值或分裂的统计显著性检验。预剪枝简单高效，但可能过早停止生长，遗漏重要交互。早期决策树文献中对此有所讨论，包括伯纳德·威德罗在20世纪60年代关于自适应系统的工作，但正式概念更多与后来的算法相关。
后剪枝先构建完整树，然后移除分支。这种方法通常更有效，因为它考虑了整体树结构。技术包括代价复杂度剪枝（也称最小代价复杂度剪枝）和基于误差的剪枝。后剪枝通常使用独立的验证集或交叉验证来决定移除哪些分支。
最著名的后剪枝算法是代价复杂度剪枝，由Breiman等人在1984年的CART著作中提出。它根据误差率和叶节点数量为每个子树分配代价，然后选择最小化权衡的子树。这通过超参数alpha实现，该参数惩罚树的大小。
一个关键参考是克里斯托弗·毕晓普在1995年出版的《神经网络模式识别》一书中的工作，他在书中讨论了神经网络背景下的剪枝，但相同原理适用于决策树。在决策树文献中，J. Ross Quinlan为C4.5算法（1993年）开发了基于误差的剪枝，Quinlan还在早期工作中引入了减少误差剪枝。
算法与实现
在实践中，ID3、C4.5、CART及其后继者C5.0等算法都包含各种剪枝方法。对于代价复杂度剪枝，标准实现包括以下步骤：
- 生长完整树。
- 计算每个节点的alpha值。
- 依次剪除alpha值最小的节点。
- 选择最小化代价复杂度分数的子树。
在Python库scikit-learn中，代价复杂度剪枝通过ccp_alpha参数实现。此外，XGBoost和LightGBM等库使用各自的启发式方法进行后剪枝，许多现代库同时支持预剪枝（通过max_depth等参数）和后剪枝。在卡内基梅隆大学的开源项目和SambaNova的机器学习环境中，剪枝通常集成到分布式训练流水线中。
剪枝与其他技术
决策树剪枝在概念上与模型剪枝相关，后者是人工智能中用于减小符号模型规模的更广泛术语。与深度模型中的参数剪枝（移除权重）不同，树剪枝移除整个分支或子树。此外，丢弃和正则化是替代方法，尽管不直接适用于树，但服务于相同目的。
大多数从业者将剪枝与数据增强等其他技术结合使用，以进一步提升泛化能力。与神经网络背景下的剪枝（通常降低推理计算成本）不同，树剪枝主要提升泛化能力和可解释性。
应用与影响
决策树剪枝在模型可解释性至关重要的领域具有显著实际影响，如医疗诊断、信用评分和欺诈检测。例如，医疗专家需要透明模型来向患者证明决策的合理性，而患者不会接触黑盒模型。通过移除不必要分支，临床医生可以专注于最关键规则。在金融领域，监管机构通常要求决策解释可验证且可解释。
在性能方面，剪枝加速推理，因为生成的树更小且更易执行。这在部署于亚马逊云服务或三星电子等边缘设备的实时系统中尤为重要，因为延迟至关重要。此外，在生成式人工智能领域，模型规模较大，剪枝不如基于树的方法常用，但为模型简化提供了知识和思路。
挑战与最佳实践
评估的一个关键挑战是选择良好的剪枝标准。过度激进的剪枝可能导致欠拟合，而剪枝不足仍会留下过拟合。使用独立验证集调整剪枝水平是标准做法；alpha选择通常通过交叉验证完成。建议在构建最优树后有效使用后剪枝，并在重视计算预算时使用预剪枝。
另一个挑战是处理具有多个水平的分类变量：剪枝可能消除覆盖罕见但重要组的分支。在实践中，剪枝应与领域期望相平衡，例如在医疗或金融领域，有时必须保留罕见分支，因为其临床重要性，即使它不减少误差。
在项目开发中，建议在模型验证后使用无偏测试集执行剪枝阶段。许多软件库的默认参数包含预剪枝和后剪枝方法；理解其交互并非易事，需要经验性测试。
截至2020年代，决策树剪枝仍是标准实践，并集成在谷歌云和甲骨文云等大型技术提供商支持的众多工具中，以及开源发行版中。尽管出现了其他技术，但没有任何方法能像移除噪声对象那样简单有效，因为树表示被如此简化。