【机器学习】决策树的剪枝处理
简介
剪枝是决策树学习算法应对过拟合的主要手段。学习过程中的节点划分过程有时会造成决策树分支过多，以至于把训练集自身的一些特点当作所有数据都具有的一般性质导致过拟合。
决策树剪枝的基本策略有“预剪枝”和“后剪枝”，二者都需要对于决策树泛化能力是否提升进行判断。所以采用留出法从数据集中划分出验证集。
下表是演示剪枝原理使用的数据集：
下图是未剪枝的决策树:
预剪枝
预剪枝是指生成过程中对每个节点划分前先进行估计，如果当前节点划分不能提升决策树泛化能力，则停止划分，当前节点标记为叶节点
计算相关的信息增益之后，我们会选择“脐部”这一属性对训练集划分，根据上表，可以分成三个分支。我们需要进行预剪枝，所以要用验证集进行判断：
假设不使用“脐部”进行划分，那么决策树就是一个叶节点，标记为“好瓜”，这时候验证集的正确率为：
在使用”脐部“进行划分后，图中②、③、④节点分别包含的训练样本是、、,所以分支的3个节点被标记为“好瓜”、“好瓜”、“坏瓜”。这是用验证集进行验证，编号为的样本分类正确。这时候验证集的正确率为：，所以应该使用“脐部”进行划分。
此后的节点使用类似的方法剪枝，最终可以得到“脐部”划分出的三个节点均不能继续划分。最终得到的决策树如下图：
对比两个决策树可以看出预剪枝显著减少了时间开销，并且降低了过拟合的风险。但是预剪枝基于贪心本质禁止分支展开，也带来了欠拟合的风险。
后剪枝
后剪枝是先生成决策树，然后自底向上的考察非叶节点，若将该节点对应的子树替换为叶节点能提升决策树泛化能力，则将该子树换为叶节点。
未剪枝的决策树验证集accuracy为42.9%，先考察把⑥节点替换为叶节点，该节点包括两个样本，因此将节点标记为“好瓜”，此时验证集精度提高到57.1%
类似的继续考察其他节点（如果验证集精度保持不变根据奥卡姆剃刀准则需要剪枝，但原书为了画图方便选择不剪枝），最终得到决策树如下图，验证集精度为71.4%
可以看出后剪枝保留了更多分支，欠拟合风险很小，且泛化性能往往优于预剪枝，但是该过程在决策树完全生成之后，且要注意考察非叶节点，因此时间开销要大得多。
参考
周志华《机器学习》