决策树的剪枝技术：理论与实践

决策树生成算法递归地产生决策树，直到不能继续下去为止。这样产生的树往往对训练数据的分类很准确，但对未知的测试数据的分类没有那么准确，即出现过拟合现象。过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。解决这个问题的办法是考虑决策树的复杂度，对已生成的决策树进行简化。在决策树学习中将已生成的树进行简化的过程称为剪枝。具体地，剪枝就是从已生成的树上裁掉一些子树或叶结点，并将其根结点或父结点作为新的叶结点，从而简化分类树模型。

本节介绍一种简单的决策树学习的剪枝算法。决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。设树T的叶结点个数为｜T｜，t是树T的叶结点，该叶结点有Nt个样本点，其中k类的样本点有Ntk个(k＝1，2，…，K)，Ht(T)为叶结点t上的经验熵，α≥0为参数，则决策树学习的损失函数可以定义为

其中经验熵为

在损失函数式(4.10)中，将等号右端的第一项记为

则

式中:C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度；表示模型复杂度；参数α≥0控制两者之间的影响，较大的α促使选择较简单的模型(树)，较小的α促使选择较复杂的模型(树)，α＝0意味着只考虑模型与训练数据的拟合程度，不考虑模型的复杂度。

剪枝就是当α确定时，选择损失函数最小的模型，即损失函数最小的子树。当α值确定时，子树越大往往与训练数据的拟合越好，模型的复杂度也越高；相反，子树越小模型的复杂度就越低，但是往往与训练数据的拟合不好。损失函数正好表示了对两者的平衡。

可以看出，决策树生成只考虑了通过提高信息增益(或信息增益比)对训练数据进行更好的拟合，而决策树剪枝通过优化损失函数并考虑了减小模型复杂度。决策树生成学习局部的模型，而决策树剪枝学习整体的模型。(www.xing528.com)

式(4.10)定义的损失函数的极小化等价于正则化的极大似然估计。所以，利用损失函数最小原则进行剪枝就是用正则化的极大似然估计进行模型选择。图4－4所示为决策树剪枝过程的示意图。

图4－4　决策树的剪枝

算法4.4　树的剪枝算法

输入:生成算法产生的整个树T、参数α；

输出:修剪后的子树Tα。

(1)计算每个结点的经验熵。

(2)递归地从树的叶结点向上回缩:

设一组叶结点回缩到其父结点之前与之后的整体树分别为TB和TA，其对应的损失函数数值分别是Cα(TB)与Cα(TA)，如果

Cα(TA)≤Cα(TB)

则进行剪枝，即将父结点变为新的叶结点。

(3)返回步骤(2)，直至不能继续为止，得到损失函数最小的子树Tα。