模型算法基础——决策树剪枝算法（一）

在决策树生成以后，常常出现过拟合的问题。这是因为如果决策树过于复杂，训练样本的每个属性（变量）都被详细的加以考虑，决策树的每个叶节点所覆盖的样本都是或接近“纯”的。这种情况下，决策树往往对训练样本拟合的很好，但是拟合验证样本时效果却大打折扣。

举一个栗子可以加深对过拟合的理解：在上学的时候，有一些同学准备考试的方法是“背题”，仅仅靠背解题过程却无法掌握其中规律性的的东西，如果题目都押中了这类同学就可以考得很好，但是对于大多数情况他们却以失败告终；还有一些同学，他们擅长在题目中寻找规律，即使题目千变万化他们也能得到高分。模型也是一样，我们更希望它能够体现规律性的东西，而不是训练样本中的细节。

这时，对决策树进行剪枝就成为了一个必不可少的步骤。其实对决策树而言，相对于树的生成过程，剪枝的过程更为重要。今天介绍一种后剪枝算法——误差降低剪枝(Reduced Error Pruning/REP)。

误差降低剪枝是最简单粗暴的剪枝方法。首先用训练样本生成决策树后，自下而上对于每个节点决定是否修剪该节点。先假设我们要删除该节点下的子树使其成为叶子节点并赋予训练样本最常见的分类，再用验证样本比较修剪前后的错分率，当修剪后的错分率不比修剪前的高时便真正删除该节点下的子树。

举个栗子，假设有个训练样本产生的决策树长这样（目标变量可分类为1或）：

其中T4节点中13和7表示该节点覆盖的样本中目标变量为1和的个数。再假设用这个决策树拟合验证样本后的结果长这样：

自下而上，按照T5、T6、T4的顺序来决定每个节点是否需要被修剪：

在判断T4是否修剪前，T7、T8节点已被删除，T5成为新的叶子节点。可以看到最终T4节点下的全部子树都被删除。

误差降低剪枝使用了和训练样本独立的验证样本，由于验证样本没有参与决策树的生成过程，因此一定程度上可以解决过拟合问题，但也可能会产生过剪枝的问题。