四、剪枝算法

1. 决策树生成算法生成的树往往对于训练数据拟合很准确，但是对于未知的测试数据分类却没有那么准确。即出现过拟合现象。

   过拟合产生得原因是决策树太复杂。解决的办法是：对决策树剪枝，即对生成的决策树进行简化。

2. 决策树的剪枝是从已生成的树上裁掉一些子树或者叶结点，并将根结点或者其父结点作为新的叶结点。

   剪枝的依据是：极小化决策树的整体损失函数或者代价函数。

3. 决策树生成算法是学习局部的模型，决策树剪枝是学习整体的模型。即：生成算法仅考虑局部最优，而剪枝算法考虑全局最优。

4.1 原理

1. 设树 的叶结点个数为 。设 为树的叶结点，该叶结点有 个样本点，其中属于 类的样本点有 个， 。

   这意味着： 。

   令 为叶结点 上的经验熵，令 为参数，则决策树 的损失函数定义为：

   

   其中： 。

   • 叶结点个数越多，表示决策树越复杂，则损失函数越大。
   • 叶结点经验熵越大，表示叶结点的样本类别分布很分散，则损失函数越大。
   • 叶结点经验熵还需要加权，权重为叶结点大小。即：越大的叶结点，其分类错误的影响越大。

2. 令 ，则： 。

   其中 为正则化项， 表示预测误差。

3. 意味着 ，即每个结点 内的样本都是纯的，即单一的分类。

   决策树划分得越细致，则 的叶子结点越多。当叶结点的数量等于样本集的数量时，树 的每个叶子结点只有一个样本点。此时每个叶结点内的样本都是纯的，从而 。

   这样的决策树其实是没有什么实用价值的，所以必须使用正则化项来约束决策树的复杂程度。

4. 参数 控制预测误差与模型复杂度之间的关系。

   • 较大的 会选择较简单的模型 。
   • 较小的 会选择较复杂的模型。
   • 只考虑对训练集的拟合，不考虑模型复杂度。
5. 决策树剪枝的准则是：考虑当 确定时， 最小化。这等价于正则化的极大似然估计。

4.2 算法

1. 决策树的剪枝算法：

   • 输入：

     • 生成算法产生的决策树
     • 参数

   • 输出： 修剪后的决策树

   • 算法步骤：

     • 对树 每个结点 ，计算其经验熵 。

     • 递归地从树的叶结点向上回退：

       设一组叶结点回退到父结点之前与之后的整棵树分别为 与 ，对应的损失函数值分别为 与 。若 ， 则进行剪枝，将父结点变成新的叶结点。

     • 递归回退直到不能继续为止，得到损失函数最小的子树 。