解决决策树的过拟合

之前我们已经比较详细的介绍啦决策树的相关知识，如ID3（Machine Learning -- ID3算法）和C4.5（Machine learning -- C4.5算法详解及Python实现）.

本文章介绍决策树学习的实际问题包括确定决策树增长的深度；处理连续值的属性；选择一个适当的属性筛选度量标准；处理属性值不完整的训练数据；处理不同代价的属性；以及提高计算效率。下面我们讨论每一个问题，并针对这些问题扩展基本的ID3算法。事实上，为了解决其中多数的问题， ID3算法已经被扩展了，扩展后的系统被改名为C4.5（Quinlan 1993）.

1,避免过拟合问题

表1描述的算法增长树的每一个分支的深度，直到恰好能对训练样例完美地分类。然而这个策略并非总是行得通的，事实上，当数据中有噪声，或训练样例的数量太少以至于不能产生目标函数的有代表性的采样时，这个策略便会遇到困难。在以上任一种情况发生时，这个简单的算法产生的树会过度拟合训练样例。

表1 专用于学习布尔函数的ID3算法概要

ID3是一种自顶向下增长树的贪婪算法，在每个结点选取能最好地分类样例的属性。继续这个过程直到这棵树能完美分类训练样例，或所有的属性都使用过了。

对于一个假设，当存在其他的假设对训练样例的拟合比它差，但事实上在实例的整个分布（也就是包含训练集合以外的实例）上表现的却更好时，我们说这个假设过度拟合（overfit）训练样例。

定义： 给定一个假设空间H，一个假设h∈H，如果存在其他的假设h´∈H，使得在训练样例上h的错误率比h´小，但在整个实例分布上h´的错误率比h小，那么就说假设h过度拟合（overfit）训练数据。

图1-1画出了在决策树学习的一个典型应用中过度拟合的影响。在这个例子中，ID3算法用来学习哪一个病人患有某种糖尿病。这幅图的横轴表示在决策树创建过程中树的结点总数，纵轴表示决策树作出的预测的精度。实线显示决策树在训练样例上的精度，虚线显示在一套独立的测试样例（没有被包括在训练样例中）上测量出的精度。可以看出，随着树的增长，在训练样例上的精度是单调上升的。然而，在独立的测试样例上测出的精度先上升后下降。如图所示，当树超过大约25个结点时，对树进一步精细化尽管可以提高它在训练数据上的精度，却降低了它在测试样例上的精度。

图1-1 决策树学习中的过度拟合。

随着ID3算法增加新的结点增长决策树，在训练样例上的精度是单调上升的。然而，在独立于训练样例的测试样例上，精度先上升，然后下降。实验这个图所需的软件和数据可以通过网址http://www.cs.cmu.edu/~tom/mlbook.html得到。

表2 目标概念PlayTennis的训练样例

是什么原因导致h比h′更好地拟合训练样例，但对于后来的实例却表现更差呢？这种情况发生的一种可能原因是训练样例含有随机错误或噪声。举例说明，考虑在表2的本来正确的样例中加入一条训练正例，但却被误标示为反例，如下：

<Outlook=Sunny，Temperature=Hot，Humidity=Normal，Wind=Strong，PlayTennis=No>

对于本来没有错误的数据，ID3生成图3-2表示的决策树。然而，增加这个不正确的样例导致ID3建立一个更复杂的树。确切地讲，新的样例会被排列到图3-2表示的树的左起第二个叶子结点，与以前的正例D9和D11排在一起。因为新的样例被标记为反例，所以ID3会在这个结点下面进一步搜索更多的细节。当然只要新的错误样例与原来这个结点的两个样例有任何差异，ID3会成功找到一个新的决策属性来把新的样例从以前的两个正例中分开。这样的结果是ID3会输出一个决策树(h)，它比图3-2中原来的树（h´）更复杂。当然，h会完美地拟合训练样例集，而较简单的h´不会。然而，由于新的决策结点只是拟合训练样例中噪声的结果，我们可以断定在取自同一实例分布的后续数据上，h´会胜过h。

图3-2 决策树

上面的例子演示了训练样例中的随机噪声如何导致过度拟合。事实上，当训练数据没有噪声时，过度拟合也有可能发生，特别是当少量的样例被关联到叶子结点时。这种情况下，很可能出现巧合的规律性，使得一些属性恰巧可以很好地分割样例，但却与实际的目标函数并无关系。一旦这样的巧合的规律性存在，就有过度拟合的风险。

过度拟合对于决策树学习和其他很多学习算法是一个重要的实践困难。例如，在一次关于ID3算法的实验研究中（Mingers 1989b），对于5种带有噪声和不确定数据的不同学习任务，人们发现在多数问题中过度拟合使决策树的精度降低了10-25%。

有几种途径用来避免决策树学习中的过度拟合。它们可被分为两类：

? 及早停止增长树法，在ID3算法完美分类训练数据之前停止增长树；

? 后修剪法（post-prune），即允许树过度拟合数据，然后对这个树后修剪。

尽管第一种方法可能看起来更直接，但是对过度拟合的树进行后修剪的第二种方法被证明在实践中更成功。这是因为在第一种方法中精确地估计何时停止增长树很困难。无论是通过及早停止还是后修剪来得到正确大小的树，一个关键的问题是使用什么样的准则来确定最终正确树的大小。解决这个问题的方法包括：

? 使用与训练样例截然不同的一套分离的样例，来评估通过后修剪方法从树上修剪结点的效用。

? 使用所有可用数据进行训练，但进行统计测试来估计扩展（或修剪）一个特定的结点是否有可能改善在训练集合外的实例上的性能。例如，Quinlan （1986）使用一种卡方（chi-square）测试来估计进一步扩展结点是否能改善在整个实例分布上的性能，还是仅仅改善了在当前的训练数据上的性能。

? 使用一个明确的标准来衡量训练样例和决策树编码的复杂度，当这个编码的长度最小时停止增长树。这个方法基于一种启发式规则，被称为最小描述长度（Minimum Description Length）的准则。Quinlan & Rivest（1989）和Mehta et al.（1995）也讨论了这种方法。

上面的第一种方法是最普通的，它常被称为训练和验证集（training and validation set）法。下面我们讨论这种方法的两个主要变种。这种方法中，可用的数据被分成两个样例集合：一个训练集合用来形成学习到的假设，一个分离的验证集合用来评估这个假设在后续数据上的精度，确切地说是用来评估修剪这个假设的影响。这个方法的动机是：即使学习器可能会被训练集合中的随机错误和巧合规律性所误导，但验证集合不大可能表现出同样的随机波动。所以，验证集合可以用来对过度拟合训练集中的虚假特征提供一个防护检验。当然，很重要的一点，验证集合应该足够大，以便它本身可提供具有统计意义的实例样本。一种常见的做法是取出可用样例的三分之一用作验证集合，使用另外三分之二用作训练集合。

2.错误率降低修剪

使用验证集合来防止过度拟合的确切方法是什么？一种称为“错误率降低修剪（error-reduced pruning）”的方法（Quinlan 1987）是考虑将树上的每一个结点作为修剪的候选对象。修剪一个结点由以下步骤组成：删除以此结点为根的子树；使它成为叶子结点；把和该结点关联的训练样例的最常见分类赋给它。仅当修剪后的树对于验证集合的性能不差于原来的树时才删除该结点。这样便使因为训练集合的巧合规律性而加入的结点很可能被删除，因为同样的巧合不大会发生在验证集合中。反复地修剪结点，每次总是选取它的删除可以最大提高决策树在验证集合上的精度的结点。继续修剪结点直到进一步的修剪是有害的（也就是降低了在验证集合上的精度）。

图3-3 决策树学习中错误率降低修剪的效果

这幅图显示了与图3-6同样的在训练集和测试集上的精度曲线。另外，它显示了“错误率降低修剪”对ID3算法产生的树的影响。注意随着树结点的剪除，决策树在测试集合上的精度上升。这里，供修剪用的验证集合与训练和测试集合都是完全不同的。

“错误率降低修剪”对决策树精度的影响被画在图3-3中。和图3-1一样，图3-3显示了在训练样例和测试样例上的决策树精度。图3-3中另外一条线显示的是随着树的修剪，它在测试样例上的精度变化。当修剪开始时，树的规模最大，并且它在测试样例上的精度最小。随着修剪的进行，结点的数量下降，但在测试集合上的精度上升。这里，可供使用的数据已经被分成3个子集：训练样例、供修剪树用的验证样例和一个测试样例集合。测试样例用来提供在未来的未见实例上的精度的无偏估计。图中显示了在训练集和测试集上的精度。在用作修剪的验证集合上的精度没有画出来。

如果有大量的数据可供使用，那么使用分离的数据集合来引导修剪是一个有效的方法。这个方法的主要缺点是当数据有限时，从中保留一部分用作验证集合进一步减少了训练可以使用的样例。下一节给出了另一种修剪方法，在数据有限的许多实际情形下，这种方法很有效。人们还提出了许多其他的技术。例如，以不同的方式多次分割可供使用的数据，然后平均得到的结果。Mingers（1989b）和Malerba et al.（1995）中报告了对不同树修剪方法的经验评估。

3.规则后修剪

实践中，一种用来发现高精度假设的非常成功的方法为“规则后修剪（rule post-pruning）”。这种修剪方法的一个变体被用在C4.5中（Quinlan 1993），C4.5是从原始的ID3算法的派生出来的。规则后修剪包括下面的步骤：

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

(2). 将决策树转化为等价的规则集合，方法是为从根结点到叶子结点的每一条路径创建一条规则。

(3). 通过删除任何能导致估计精度提高的前件（preconditions）来修剪（泛化）每一条规则。

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

为了演示以上过程，再次考虑图3-2中的决策树。在“规则后修剪”算法中，为树中的每个叶子结点产生一条规则。从根结点到叶子结点路径上的每一个属性测试成为一个规则先行词（即前件），叶子结点的分类称为规则的结论（即后件）。例如，图3-1中树的最左一条路径被转换成规则：

IF （Outlook=Sunny）Λ（Humidity=High）

THEN PlayTennis=No

接下来，通过删除不会降低估计精度的先行词来修剪每一个规则。例如对于上面的规则，规则后修剪算法会考虑删除先行词（Outlook=Sunny）和（Humidity=High）。它会选择这些修剪步骤中使估计精度有最大提升的步骤，然后考虑修剪第二个前件作为进一步的修剪步骤。如果某个修剪步骤降低了估计精度，那么这个步骤不会被执行。

如同前面提出的，估计规则精度的一种方法是使用与训练集和不相交的验证集合。另一种被C4.5使用的方法是基于训练集合本身评估性能，但使用一种保守估计（pessimistic estimate）来弥补训练数据有利于当前规则的估计偏置。更准确地讲，C4.5通过以下方法计算保守估计，先计算规则在它应用的训练样例上的精度，然后假定此估计精度为二项分布，并计算它的标准差（standard deviation）。对于一个给定的置信区间，采用下界估计作为规则性能的度量（例如，对于一个95%的置信区间，规则精度被保守估计为：在训练集合上的观察精度减去1.96乘估计的标准差）。这样做的效果是，对于大的数据集，保守预测非常接近观察精度（也就是标准差非常小），然而随着数据集合的减小，它开始离观察精度越来越远。虽然这种启发式方法不是统计有效（statistically valid）的，但是已经发现它在实践中是有用的。第5章讨论了统计有效的预测均值和置信区间的方法。

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

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

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

? 转化为规则提高了可读性。对于人来说规则总是更容易理解的。