剪枝是树类算法防止过拟合的重要方法，而且其思想非常有启发，可以在其他算法中参考使用。而且，（树的）过拟合本身就是重要的内容，所以单列出来。不过这里简单一说思路即可。
剪枝
在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，这时就有可能把训练样本学习的太好，以至于把训练集的某一些特点当做是所有数据都具有的一般性质，这时就发生了过拟合。因此可以通过主动去掉一些分支来降低过拟合的风险。剪枝是决策树学习算法对付“过拟合”的主要手段。
决策树剪枝的基本策略有两种： （1）预剪枝 ：预剪枝是在决策树生成过程中，对每个结点在划分前先进行评估，如果当前结点的划分不能带来决策树泛化能力的提升，则停止划分并将当前结点标记为叶结点。
（注释：需要单列一个验证集，这里也让我对验证集的作用增加更多理解。主要思想就是，先分割，然后在验证集上看看分割好不好，如果不好就算了。这里的问题在于，有可能这一步分割的效果不怎么样，但是他的子步骤可能分割的效果很好，这可能会导致欠拟合，当然具体差别多大也要看具体的数据集。）
（2） 后剪枝：先从训练集生成一颗完整的决策树，然后自底向上地对非叶结点进行考察，如果将该结点对应的子树替换为叶结点能带来决策树泛化能力的提升，则将该子树替换为叶结点。
（注释：还需要单列一个验证集。主要就是从叶子往回溯，逐渐的去掉叶子节点，查看是否在验证集合上效果更好。这个效果好一些，但是时间很长）
我们使用一定的性能评估方法来判断决策树泛化性能是否有提升。
评估方法：使用一个测试集来测试学习器对新样本的判别能力，然后在测试集上的“测试误差”作为泛化误差的近似，需要注意的是测试集要与训练集互斥，即测试样本不在训练集中出现、使用。
留出法：直接将数据集D划分为两个互斥的集合，其中一个集合作为训练集，另一个作为测试集。需要注意的是，训练/测试集的划分要尽可能保持数据分布的一致性，避免因数据划分过程引入额外的偏差而对最终结果产生影响。
