1-3 决策树的剪枝

决策树的剪枝这件事，只需记住一点：千万别把它想复杂了。

在1-1中介绍了决策树节点划分的三个终止条件，在1-2中介绍了决策树节点划分的特征选择的三个依据。这就已经掌握了用一个样本集生成一棵决策树的几乎全部姿势。那么剪枝用来解决什么问题？

前面0-1中说到把数据集划分成训练集测试集验证集等等的几种方法。解决过拟合的基本操作，就是搞个验证集或测试集，训练集训出来的模型去验证集上验一验是不是过拟合了，如果是的话要想办法修正一下。而剪枝本质上就是在干这么一件事：简化模型，防止过拟合。具体的策略则有预剪枝和后剪枝两种。

1. 预剪枝

设想我们正在使用一个训练集生成一个决策树，此时此刻正在某个节点上选取了某个特征对该节点进行进一步的划分。不管我们使用信息增益、信息增益比还是基尼系数，此时我们选定了这个特征进行划分，划分后的树对训练集的区分能力肯定是变好了。but wait，这个变好有可能是模型进一步学到了数据的真实规律，也有可能是在训练集上的过拟合导致的。怎么办？拿去到验证集上验一验。我们事先定一个性能指标，比如准确率什么的（具体可以参考0-2），然后对比前面所说的节点划分前后，模型在验证集上的性能指标是上升还是下降了，如果上升了，OK，那就划分。如果不升反降，或者至少没有提升，那就算了，不要划了，到此为止吧。这就叫预剪枝。

2. 后剪枝

理解了剪枝的本质，则不管是预剪枝还是后剪枝都是简单明了的了。后剪枝的意思就是先不管验证集，先在训练集上一顿划分，生成一棵可能特别深的树，然后拿这棵树去验证集验证，从最深的子节点开始往上屡，对比的还是节点划分前后树在验证集上的表现，如果划分后表现变差，说明这次划分是对训练集的过拟合，那就剪掉，把子树合并成叶节点。