后剪枝指决策树生成后进行的剪枝操作,这种方法基于完整的决策树,且允许树过度拟合训练数据,对于置信度不够的结点字,子树会用叶子结点代替,该叶子的类标号用该结点子树中最频繁的类标记。
后剪枝的过程是对拥有同样父节点的一组节点进行检查,判断如果将其合并,熵的增加量是否小于某一阈值,在阈值较小的情况下,一组节点可以合并为一个,其中包含了所有可能的结果。
后剪枝的方法
基于已有树进行测试数据的切分:
- 若存在任一子集是树,则在该子集递归剪枝过程;
- 计算不合并的误差;
- 若合并会降低误差,那么就合并叶节点。
后剪枝算法列举
1)错误率降低剪枝 REP(Reduced-Error Pruning);
2)悲观剪枝代价 EBP(Error-Based Pruning);
3)复杂度剪枝 CCP(Cost-Complexity Pruning);
4)基于错误的剪枝 PEP(Pesimistic-Error Pruning)。
前剪枝和后剪枝对比
前阈值的设定很敏感,微小的变动会引起整棵树的变动,相比之下,后剪枝方案得到的结果会比较好。
后剪枝保留更多的分支,且相较于预剪枝有更小的欠拟合风险,但是后剪枝基于训练完成的决策树,采用自下向上逐层扫描的判定方式,因此训练的时间和开销较预剪枝更大。
相较于前剪枝,后剪枝方案更为常有,主要是因为前剪枝方法中精确估计何时停止树增长会比较困难。
父级词:剪枝
关联词:预剪枝