​
 ​​ ​决策树后剪枝算法（一）代价复杂度剪枝CPP
 ​​ ​决策树后剪枝算法（二）错误率降低剪枝REP
 ​​ ​决策树后剪枝算法（三）悲观错误剪枝PEP
 ​​ ​决策树后剪枝算法（四）最小错误剪枝MEP
 
  剪枝，是一个“用准确性换取简单性”的思想。它允许决策树对训练集过拟合，再通过删除对泛化精度无贡献的子分支，从而修剪出一颗较小的树。以下列出几种较常见的后剪枝算法，及其机制对比：

	CCP	REP	PEP	MEP
剪枝方式	自底向上	自底向上	自顶向下	自底向上
计算复杂度	$O(n^2)$	$O(n)$	$O(n)$	$O(n)$
误差估计	标准误差	剪枝集上误差	连续性矫正	概率估计
是否需要额外剪枝集	否	是	否	否

（2）错误率剪枝（REP）

  错误率剪枝算法相对较简单朴素，同时也具备速度快的优点，但容易过度修剪。主要思路为划分训练集 - 验证集：训练集用形成学习到的决策树；验证集用来评估修剪决策树。大致流程可描述为：对于训练集上构建的过拟合决策树，自底向上遍历所有子树进行剪枝，直到针对交叉验证数据集无法进一步降低错误率为止。

  

（2.1）数学推导

 评价标准：
$$\begin{gathered} R_{test}(T_t)vs{R}_{test}(t) \\ {R}_{test}(T)=\frac{e_{test}(T)}{n_{test}(T)} \end{gathered}$$
 解读：

• $R_{test}(T)$表示错误率，用来比较剪枝前后好坏。
• $n_{test}(T)$为$T$节点分到的测试集样本数, $e_{test}(T)$为$T$节点对测试集分类错误样本数。
• 因测试集固定，$n_{test}(T)$为定值，评价标准可简化为$e_{test}(T)$。

  补充说明，每个节点的类别确定方法，为多数表决。即在训练决策树时，对每个节点分到的训练样本进行多数表决，为每个节点贴上类别标签。以便后续验证集评估剪枝前后，错误样本数进行比较。

 

（2.2）算法流程

  考虑决策树上每个分支节点作为剪枝候选对象，自底向上遍历，判断是否剪枝步骤如下：

• （1）删除以此节点为根的子树，使其成为叶子结点。
• （2）根据多数表决法，赋予该节点关联的训练数据类别。
• （3）比较删除前后错误样本数，判断是否剪枝该节点。

 

（2.3）例题计算

  需注意的是，该例题为突出剪枝过程，巧妙设计为每个内部节点均可剪枝。实际应用中根据比较结果判断。

  数据集

  训练集生成决策树

  进行多数表决类别打标签

  基于测试集剪枝

  (1)第四层 纹理

  剪枝前：错误2 / 剪枝后：错误1

  剪枝后错误数下降，故剪枝替换为单节点。

  (2)第三层 色泽

  剪枝前：错误1 / 剪枝后：错误1

  剪枝后错误率未下降，根据奥卡姆剃刀原则，等错误率选复杂度低的树，故剪枝替换为单节点。

  (3)第二层 色泽

  剪枝前：错误2 / 剪枝后：错误1

  剪枝后错误数下降，故剪枝替换为单节点。

  (4)第二层 根蒂

  剪枝前：错误1 / 剪枝后：错误1

  剪枝后错误率未下降，根据奥卡姆剃刀原则，等错误率选复杂度低的树，故剪枝替换为单节点。

  (5)第一层 脐部

  剪枝前：错误2 / 剪枝后：错误4

  剪枝后，错误数明显上升，故不能剪枝。

  (6)最终结果

  

（1.4）代码实现

 C4.5算法及REP剪枝手写实现

链接：https://pan.baidu.com/s/1gl4TzGfVQWbqgKTZwQqXeQ?pwd=uof6 
提取码：uof6

 代码参考:http://www.hzcourse.com/web/refbook/detail/9970/226

————————————————————————————————————————————————————————————

参考资料：

[1] 现代决策树模型及其编程实践 黄智濒 编著

[2] 统计学习方法(第二版) 李航 著

[3] https://zhuanlan.zhihu.com/p/548186344