预剪枝

「预剪枝」是一种决策树剪枝方法，指在决策树生成过程中面对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能提升，则停止划分并将当前节点作为叶节点。

如何判断决策树泛化性能是否提升？

采用「留出法」预留一部分数据用作「验证集」进行评估。以西瓜数据集为例，我们将西瓜数据集划分为训练集合验证集，在接下来的例子中，我们采用训练集训练模型，用验证集评估模型的性能。如果通过某种方式（如属性划分）提升了模型在验证集上的性能（如验证集准确率等），我们则认为该方法使模型的性能得到了提升。

比如对于数据集

编号	色泽	根蒂	敲声	纹理	脐部	触感	好瓜
1	青绿	蜷缩	浊响	清晰	凹陷	硬滑	是
2	乌黑	蜷缩	沉闷	清晰	凹陷	硬滑	是
3	乌黑	蜷缩	浊响	清晰	凹陷	硬滑	是
6	青绿	稍蜷	浊响	清晰	稍凹	软粘	是
7	乌黑	稍蜷	浊响	稍糊	稍凹	软粘	是
10	青绿	硬挺	清脆	清晰	平坦	软粘	否
14	浅白	稍蜷	沉闷	稍糊	凹陷	硬滑	否
15	乌黑	稍蜷	浊响	清晰	稍凹	软粘	否
16	浅白	蜷缩	浊响	模糊	平坦	硬滑	否
17	青绿	蜷缩	沉闷	稍糊	稍凹	硬滑	否

由此得到的决策树为

img-2024-03-12 22-34-46.png

基于验证集

编号	色泽	根蒂	敲声	纹理	脐部	触感	好瓜
4	青绿	蜷缩	沉闷	清晰	凹陷	硬滑	是
5	浅白	蜷缩	浊响	清晰	凹陷	硬滑	是
8	乌黑	稍蜷	浊响	清晰	稍凹	硬滑	是
9	乌黑	稍蜷	沉闷	清晰	稍凹	硬滑	否
11	浅白	硬挺	清脆	稍糊	平坦	硬滑	否
12	浅白	蜷缩	浊响	模糊	平坦	软粘	否
13	青绿	稍蜷	浊响	稍糊	凹陷	硬滑	否

我们对训练集的生成的未剪枝决策树采用预剪枝方式进行剪枝：我们首先判断脐部

不划分时：决策树只有一个节点，作为叶节点，以情形 (2) 标记为训练样例数目最多的类别“好瓜”，验证集 7 个样本中 4，5，8 正确，验证集精度为
划分时：分成（凹陷），（稍凹），（平坦）三个节点。标记为好瓜，标记为坏瓜。验证集精度为，因此得出结论，应该进行划分。

继续与同样划分节点即可。注意，“色泽” 结点被划分后，验证集数据 5 倍错误分类为坏瓜，而根蒂节点的划分对验证集分类结果没有影响。故两个节点都不进行划分。最终得到的决策树如图所示

img-2024-03-12 22-37-23.png

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