机器学习 | 决策树：预剪枝与后剪枝

如果一个人连死都不怕的话，那么他害怕的事情就太多了。

机器学习 | 决策树：预剪枝与后剪枝

剪枝（pruning）是决策树学习算法对付“过拟合”的主要手段。决策树剪枝的基本策略有“预剪枝”（prepruning）和“后剪枝”（postpruning）。

• 预剪枝：在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能的提升，则停止划分并将当前结点标记为叶结点。
• 后剪枝：先从训练集生成一棵完整的决策树，然后自底上向地对非叶结点进行考察，若将该结点对应的子树替换为叶结点可以带来决策树泛化性能的提升，则将该子树替换为叶结点。

那么，如何判断泛化性能是否提升呢？采用“留出法”，即将数据集分为训练集和验证集，利用训练集构造决策树，利用验证集来评估剪枝前、后的验证集精度。

1 预剪枝

1.1 预剪枝过程

具体地，根据信息增益准则选择一个最优划分属性作为当前结点时，若这个结点：

• 假设停止划分，那么该结点将被标记为叶结点（其类别为划分到该结点的所有训练样本中占比最多的类别），然后将根据决策树把划分到该结点的验证集样本的预测正确率记为 ；
• 假设进行划分，那么该内部结点下的所有样本将根据不同的属性值，被划分到不同的分支并标记为叶结点，验证集样本将被划分到不同分支，其预测正确率记为 ；

若划分后验证集精度不大于划分前验证集精度（ ），则停止继续划分，否则进行划分。

1.2 预剪枝特点

• 优点：预剪枝使得决策树的很多分支都没有“展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销；
• 缺点：有些分支的当前划分虽然不能提升泛化性能，但在其基础上进行的后续划分却有可能导致性能的显著提高，预剪枝基于“贪心”的本质禁止这些分支展开，给预剪枝决策树带来了欠拟合的风险。

2 后剪枝

2.1 后剪枝过程

后剪枝自底向上的判断每一个非叶结点在剪枝前、后的验证集的精度，（剪枝后该非叶结点变为叶子结点，其类别为划分到该结点的所有训练样本中占比最多的类别），若剪枝后验证集在决策树上的精度大于剪枝前的精度，那么该非叶结点应该进行剪枝，否则予以保留。

2.2 后剪枝特点

• 优点：后剪枝决策树通常比预剪枝决策树保留了更多的分支，欠拟合风险很小，泛化性能往往优于预剪枝决策树；
• 缺点：后剪枝是在生成完整决策树之后进行的，且需要对每一个非叶结点进行考察，其训练时间开销比预剪枝决策树大得多。

参考资料：周志华《机器学习》，赵赵赵颖^[1]。

参考资料

[1]

赵赵赵颖: https://blog.csdn.net/leaf_zizi