打字猴:1.700534609e+09

1700534609 预剪枝的核心思想是在树中结点进行扩展之前，先计算当前的划分是否能带来模型泛化能力的提升，如果不能，则不再继续生长子树。此时可能存在不同类别的样本同时存于结点中，按照多数投票的原则判断该结点所属类别。预剪枝对于何时停止决策树的生长有以下几种方法。

1700534610

1700534611 （1）当树到达一定深度的时候，停止树的生长。

1700534612

1700534613 （2）当到达当前结点的样本数量小于某个阈值的时候，停止树的生长。

1700534614

1700534615 （3）计算每次分裂对测试集的准确度提升，当小于某个阈值的时候，不再继续扩展。

1700534616

1700534617 预剪枝具有思想直接、算法简单、效率高等特点，适合解决大规模问题。但如何准确地估计何时停止树的生长（即上述方法中的深度或阈值），针对不同问题会有很大差别，需要一定经验判断。且预剪枝存在一定局限性，有欠拟合的风险，虽然当前的划分会导致测试集准确率降低，但在之后的划分中，准确率可能会有显著上升。

1700534618

1700534619 ■ 后剪枝

1700534620

1700534621 后剪枝的核心思想是让算法生成一棵完全生长的决策树，然后从最底层向上计算是否剪枝。剪枝过程将子树删除，用一个叶子结点替代，该结点的类别同样按照多数投票的原则进行判断。同样地，后剪枝也可以通过在测试集上的准确率进行判断，如果剪枝过后准确率有所提升，则进行剪枝。相比于预剪枝，后剪枝方法通常可以得到泛化能力更强的决策树，但时间开销会更大。

1700534622

1700534623 常见的后剪枝方法包括错误率降低剪枝（Reduced Error Pruning，REP）、悲观剪枝（Pessimistic Error Pruning，PEP）、代价复杂度剪枝（Cost Complexity Pruning，CCP）、最小误差剪枝（Minimum Error Pruning，MEP）、CVP（Critical Value Pruning）、OPP（Optimal Pruning）等方法，这些剪枝方法各有利弊，关注不同的优化角度，本文选取著名的CART剪枝方法CCP进行介绍。

1700534624

1700534625 代价复杂剪枝主要包含以下两个步骤。

1700534626

1700534627 （1）从完整决策树T0开始，生成一个子树序列{T0,T1,T2,…,Tn}，其中Ti+1由Ti生成，Tn为树的根结点。

1700534628

1700534629 （2）在子树序列中，根据真实误差选择最佳的决策树。

1700534630

1700534631 步骤（1）从T0开始，裁剪Ti中关于训练数据集合误差增加最小的分支以得到Ti+1。具体地，当一棵树T在结点t处剪枝时，它的误差增加可以用R(t)−R(Tt)表示，其中R(t)表示进行剪枝之后的该结点误差，R(Tt)表示未进行剪枝时子树Tt的误差。考虑到树的复杂性因素，我们用|L(Tt)|表示子树Tt的叶子结点个数，则树在结点t处剪枝后的误差增加率为

1700534632

1700534633