决策树学习的剪枝方法

王晓

摘要：决策树学习是应用最广的归纳推理算法之一。它是一种逼近离散值函数的方法，对噪音数据有很好的健壮性且能够学习浅析表达式。本论文主要介绍决策树学习的剪枝方法以及评价一棵决策树优劣的标准。

关键词：决策树学习 决策树学习的剪枝方法

1 简述

在决策树的生成过程中，如果对每一个分支都一直增长到恰好对训练样例完美地分类，这个策略并非总行的通的。事实上，当数据中有噪音或训练样例的数量太少以至于不能产生目标函数的有代表性的采样时，这个策略会遇到困难。

对于一个假设，当存在其他的假设对训练样例的拟合比它差，但事实上在实例的整个分布上却表现的更好时，我们说这个假设过度拟合训练样例。

图1描述了决策树学习的一个典型应用中过度拟合的影响。在这个例子中，ID3算法用来学习哪一种病人患有糖尿病。这副图的横轴表示决策树建造中树的结点总数，纵轴表示决策树做出的预测精度。实线表示决策树在训练样例上的精度，虚线表示在一套独立测试样例（没有被包含在训练样例中）上测量出的精度。可以看出，随着树的增长，在训练样例上的精度是单调上升的，然而，在独立的测试样例上测出的精度先上升后下降。说明对树的进一步精化尽管可以提高它在训练数据上的精度，却降低了它在测试样例上的精度。

过度拟合对于决策树學习和其他一些学习算法是一个重要的实践难题，在决策树学习中解决这个问题的途径主要是对决策树进行修剪，有两种修剪方法：预修剪和后修剪。

2 决策树的后修剪学习算法

后修剪算法已经得到了广泛的应用，在这个算法中输入为一个未经修剪的决策树，输出为对它剪枝之后的决策树，这棵树是将原树中一个或几个子树删除所得的结果。剪枝过程中，将一些子树删除用一些叶结点来代替，这个叶结点所属的类用这棵子树中大多数训练实例所属的类代替，并且在相应的叶子上标记出所属这个类的训练实例所占的比例。

经过剪枝的决策树，对训练样例的错误率已经不为0，但由于在这种剪枝算法当中位于底层的子树将被优先剪掉，这些结点包含的实例很少，所以这种方法将减少噪音对决策树构造的影响。

后修剪算法有两种可能的剪枝策略，一种是自上而下的，一种是自下而上的。自下而上的算法是首先在最低层的内结点开始剪枝，剪去那些满足一定标准的内结点，生成新的决策树，然后在新的决策树上递归调用这个算法，直到没有新的结点可以剪枝为止。而与之相反，自上而下的算法是从根结点开始向下逐个考虑每个结点是否应该被剪枝。

后修剪的算法很多，这儿介绍两种比较常用的方法：错误率降低后修剪和规则后修剪。

（1） 错误率降低后修剪

错误率降低后修剪是一种自上而下的修剪方法，修剪过程由以下步骤组成：删除以此结点为根的子树；使它成为叶结点；把和该结点关联的训练样例的最常见分类赋给它。仅当修剪后的树对于验证集合的性能不比原树差时才删除该结点。

如果有大量的数据可供使用，那么使用分离的数据集合来引导修剪是一个有效的方法.这个方法的主要缺点是当数据有限时，从中保留一部分用作验证集进一步减少了训练可以使用的样例。下面的这种方法在数据有限的许多实际情形下，也是有效的。

（2） 规则后修剪

规则后修剪是实践中一种发现高精度假设的非常成功的方法，这种方法的一个变体被成功的应用到C4.5系统中。规则后修剪包括下面的步骤：

1）从训练集合推导出决策树，增长决策树直到尽可能好地拟合训练数据，允许过度拟合发生；

2）将决策树转化为等价的规则集，方法是从根结点到叶结点的每一条路径创建一条规则；

3）通过删除任何能导致估计精度提高的前件来修剪每一条规则；

4）按照修剪过的规则的估计精度对它们进行排序，并按照这样的顺序应用这些规则来分类后来的实例。

为什么修剪以前要把决策树转化成规则集呢？这样做主要有三个好处：

1）转化为规则集可以区分决策结点使用的不同上下文。因为贯穿决策结点的每条不同路径产生一条不同的规则，所以对于不同路径，关于一个属性测试的修剪决策可以不同。相反如果直接修剪树本身，只有两个选择，要么完全删除决策结点，要么保留它的本来状态。

2）转化为规则集消除了根结点附近的属性测试和叶结点附件的属性测试的区别。于是避免了凌乱的记录问题，比如，若是根结点被修剪了保留它下面的部分子树时如何保留它下面的部分子树时如何重新组织这棵树。

3）转化为规则集可以提高可读性。对人来说规则总是更容易理解的。

3 决策树预修剪学习算法

在生成一棵完整决策树的算法中都要求每一个叶结点中的训练实例都属于同一个类或者已经没有属性可供选择作为算法停止条件。然而在预修剪算法中，并不使用这个标准，而是在这个标准得到满足之前就停止继续扩展决策树。具体在什么时候停止决策树的扩张就成为这种方法的主要研究内容。

一种最为简单的方法就是在决策树达到一定高度的情况下就停止决策树的扩张，这种停止标准在一定情况下能够取得比较好的效果。更为普遍的做法是计算每次扩张对系统性能的增益，如果这个增益值小于某个阈值则不进行扩展，即使叶结点的实例不属于同一类。一般情况下，作为判断是否停止扩张决策树的增益的选择标准，与每次扩展时选择测试属性的标准相同。

如何寻找停止决策树扩张的标准一直是决策树预修剪学习算法的一个难点问题，它限制了这种方法的广泛应用，同时与信息增益进行比较的那个阈值需要人为的确定，这就需要人们的先验知识和专家领域知识。这样就降低了学习过程的智能性，况且有时这些先验知识是很难获得或者根本不能获取的。

4 决策树学习算法的评价

决策树的各种学习算法各有优缺点，它们的优缺点又是怎么评价的呢？下面给出几种评价决策树的一些量化的评价标准[6]。

（1） 过学习

过学习也就是前面提到的学习过程中的过度拟合问题。一个好的算法生成的决策树应该出现过学习现象的程度比较小。

（2） 有效性

最为直接的估计一棵决策树在测试实例集合上的性能的方法是，将它在测试实例集合上进行测试，但这是不现实的。一般采用训练实例集本身来估计训练算法的有效性，一种最简单的方法是用训练集的一部分（例如2/3的训练实例）对决策树进行训练，而用另一部分（例如1/3的训练实例）对决策树检测其有效性。但这样往往减小训练实例空间，而增大了学习中过度拟合的可能性。一般采用下面两种方法来评测一个决策树学习系统的有效性。

（3） 交叉有效性

在此方法中，我们将训练实例T分为互不相交且大小相等的k个子集T1，T2， ……， Tk。对任意子集Ti，用T-Ti训练决策树，用对生成的决策树进行测试，得到错误率ei，然后估计整个算法的错误率：

.

（4） 余一有效性

这种有效性的度量与交叉有效性类似，不同之处在于将每个Ti的大小定为1。假设|T|=n，则整个算法的错误率为：

.

（5） 决策树的复杂程度

决策树的复杂程度也是度量决策树学习效果的一个重要标准。如果决策树是单变量的，那么决策树的复杂程度主要由树的结点个数决定；如果是多变量的，则主要由结点中属性的总个数决定。

综合上面的5种评价标准，前面的4个标准可以用测试错误率或者测试正确率来体现，这样我们可以把衡量决策树性能的标准总结为两个：决策树的测试错误率（或者测试正确率）以及决策树的复杂程度。

5 总结

本论文主要从决策树学习的修剪方法介绍了决策树学习算法的工作过程，然后给出了评价一棵决策树优劣的标准。

参考文献

[1]史忠植，知识发现[M].北京：清华大学出版社，2012.