1700534632
1700534633
1700534634
．
1700534635
1700534636
（3.25）
1700534637
1700534638
在得到Ti后，我们每步选择α最小的结点进行相应剪枝。
1700534639
1700534640
用一个例子简单地介绍生成子树序列的方法。假设把场景中的问题进行一定扩展，女孩需要对80个人进行见或不见的分类。假设根据某种规则，已经得到了一棵CART决策树T0，如图3.15所示。
1700534641
1700534642
此时共5个内部结点可供考虑，其中
1700534643
1700534644
1700534645
，
1700534646
1700534647
1700534648
，
1700534649
1700534650
1700534651
，
1700534652
1700534653
1700534654
，
1700534655
1700534656
1700534657
．
1700534658
1700534659
可见α（t3）最小，因此对t3进行剪枝，得到新的子树T1，如图3.16所示。
1700534660
1700534661
1700534662
1700534663
1700534664
图3.15 初始决策树T0
1700534665
1700534666
1700534667
1700534668
1700534669
图3.16 对初始决策树T0的t3结点剪枝得到新的子树T1
1700534670
1700534671
而后继续计算所有结点对应的误差增加率，分别为α(t1)=3，α(t2)=3，α(t4)=4。因此对t1进行剪枝，得到T2，如图3.17所示。此时α(t0)=6.5，α(t2)=3，选择t2进行剪枝，得到T3。于是只剩下一个内部结点，即根结点，得到T4。
1700534672
1700534673
在步骤（2）中，我们需要从子树序列中选出真实误差最小的决策树。CCP给出了两种常用的方法：一种是基于独立剪枝数据集，该方法与REP类似，但由于其只能从子树序列{T0,T1,T2,…,Tn}中选择最佳决策树，而非像REP能在所有可能的子树中寻找最优解，因此性能上会有一定不足。另一种是基于k折交叉验证，将数据集分成k份，前k−1份用于生成决策树，最后一份用于选择最优的剪枝树。重复进行N次，再从这N个子树中选择最优的子树。
1700534674
1700534675
1700534676
1700534677
1700534678
图3.17 对T1中t1结点剪枝得到新的子树T2
1700534679
1700534680
代价复杂度剪枝使用交叉验证策略时，不需要测试数据集，精度与REP差不多，但形成的树复杂度小。而从算法复杂度角度，由于生成子树序列的时间复杂度与原始决策树的非叶结点个数呈二次关系，导致算法相比REP、PEP、MEP等线性复杂度的后剪枝方法，运行时间开销更大。
1700534681