1.剪枝处理

剪枝操作是决策树中应对过拟合的一个主要手段，有时候会造成分支过多，这时候说明训练样本学习的太好了，导致了过拟合的存在，因此我们可以主动的去掉一些分支降低过拟合的风险。

剪枝操作基本有预剪枝和后剪枝两个，预剪枝是说在决策树生成过程中，对每一个节点在划分前进行估计，若当前节点的划分不能带来决策树泛化性能提升，则停止划分，并将当前节点标记为叶子节点。后剪枝操作是指在训练完后，生成一个完整的决策树，在这个树的基础上从底部到上，对非叶子节点进行考察，若将该节点对应的子树换成叶子节点，可以使得决策树泛化能力进一步提升，则将该子树替换成叶子节点。

不过我们怎么评价决策树的泛化能力呢？怎么知道剪枝之后泛化能力是否有提升呢？我们本次使用的方法是留出法。我们预留出一部分数据将其作为验证集，进行性能评估。

假设我们使用信息增益来进行特征选择的话（只计算训练集）和上一篇文章中决策树形状不同，我们会生成这样一棵决策树。

2.预剪枝

我们首先看一下预剪枝部分。我们基于信息增益方法选取脐部来对训练集进行划分。产生三个分支，然而是否应该按照这个进行划分呢？我们预剪枝就可以对划分前后泛化性能进行估计。

在划分之前，所有样例集中在根节点。其标记类别记为样例中最多的类别，假设将这个叶子节点标记为好瓜。用验证集验证这个单节点决策，则458这三个样例正确分类，其余4个样例错误。精度为3/7=42.9%，在用这个脐部节点划分之后

 

3.后剪枝

 

4.决策树各种算法中剪枝处理的实现

4.1 ID3、C4.5决策树剪枝 

 

 

4.2 CART决策树剪枝处理