剪枝(pruning)是决策树学习算法对付"过拟合"的主要手段。在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，这时就可能因训练样本学得"太好"了，以致于把训练集自身的一些特点当做所有数据都具有的一般性质而导致过拟合。因此，可通过主动去掉一些分支来降低过拟合的风险。

决策树叶剪枝的基本策略有"预剪枝"(prepruning)和"后剪枝"(postpruning)。预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。

举个例子：

西瓜数据集

上图是西瓜数据集，只不过分为了两部分，上半部分是训练集，下半部分是验证集。

重点解释下面这张图。

首先，按照脐部对训练集进行划分，分成了三部分：

凹陷，稍凹，平坦。

对应的训练集样本分别为:{1,2,3,14}，{6,7,15,17}，{10,16}

观察下图，发现凹陷的训练集样本都划分为了好瓜，但是14号很明显是坏瓜，为什么也划分为好瓜呢？

这是因为，只要好瓜的比例大于等于50%，就把该样本集都归类为好瓜。

那么凹陷对应的验证集为:{4,5,13}。这几个样本也被分为好瓜，但是13号很明显被分错了。

同理，稍凹中，验证集{8,9}也都被分为好瓜，很明显9号被分错了。

同理，平坦中，验证集{11,12}都被分为坏瓜，这次不错，都分对了。

所以验证集精度为：*100% = 71.4%。

脐部划分

我们继续对凹陷这一个分支进行划分。

基于信息增益准则将挑选出划分属性为：色泽。

如下图所示，按照色泽，将训练集样本{1,2,3,14}划分为了三部分：

青绿、乌黑、浅白

对应的训练集样本进一步被细分为：{1}，{2,3}，{14}

对应的验证集进一步被细分为：{4,13}，{}，{5}

其中青绿对应的训练集为好瓜，那么验证集也被分成了好瓜，但是很明显13号被分错了。

乌黑对应的训练集为好瓜，那么验证集也被分为了好瓜，但此时验证集为空，没影响。

浅白对应的训练集为坏瓜，那么验证集也被分为了坏瓜，但是很明显5号被分错了。

所以呢，用色泽去划分，导致验证集中的13和5号都被分错。

所以，综合脐部划分和色泽划分，目前有三个验证集中的样本被分错，分别是：13、5、9。

所以，验证集的精度为：*100% = 57.1%。

色泽划分

发现没有，用色泽进一步划分，竟然导致精度下降。

所以，直接把色泽划分去掉，这就是预剪枝。