解决决策树的过拟合

参看书籍:Machine Learning(Tom Mitchell)

之前我们已经比较详细的介绍啦决策树的相关知识,如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章讨论了统计有效的预测均值和置信区间的方法。

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

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

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

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

本文分享自微信公众号 - 机器学习算法与Python学习(guodongwei1991)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2016-10-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法channel

从 n-gram 到 RNN 做的那些优化改进

39840
来自专栏数据派THU

一文读懂卷积神经网络CNN(学习笔记)

来源:机器学习算法与自然语言处理 作者:白雪峰 本文为图文结合,建议阅读10分钟。 本文为大家解读如何简单明了的解释卷积,并且分享了学习中的一些方法案例。 首...

35160
来自专栏AI研习社

用python 6步搞定从照片到名画,你学你也可以(附视频)

近年来,机器学习的进步使我们仅用几行代码就能生成惊为天人的艺术作品。如果可以将艺术作品的原型设计速度提高100倍,让用户真正地与创作媒介合为一体,效果会怎么样呢...

41650
来自专栏华章科技

你是合格的机器学习数据科学家吗?来挑战这40题吧!(附解答)

目前机器学习是最抢手的技能之一。如果你是一名数据科学家,那就需要对机器学习很擅长,而不只是三脚猫的功夫。作为 DataFest 2017 的一部分,Analyt...

12020
来自专栏机器之心

学界 | 新型循环神经网络IndRNN:可构建更长更深的RNN(附GitHub实现)

选自arXiv 作者:Shuai Li等 机器之心编译 参与:张倩、黄小天 近日,澳大利亚伍伦贡大学联合电子科技大学提出一种新型的循环神经网络 IndRNN,不...

38050
来自专栏机器人网

最全机器学习算法汇总

本文是对机器学习算法的一个概览,以及个人的学习小结。通过阅读本文,可以快速地对机器学习算法有一个比较清晰的了解。本文承诺不会出现任何数学公式及推导,适合茶余饭后...

45750
来自专栏智能算法

主成分分析到底怎么分析?

PCA(Principal Component Analysis)是一种常用的数据分析方法。PCA通过线性变换将原始数据变换为一组各维度线性无关的表示,可用于提...

355100
来自专栏Pytorch实践

Pytorch实现LSTM时间序列预测

摘要:本文主要基于Pytorch深度学习框架,实现LSTM神经网络模型,用于时间序列的预测。 开发环境说明: Python 35 Pytorch 0.2 CP...

1.7K70
来自专栏深度学习思考者

深入浅出——搞懂卷积神经网络的过拟合、梯度弥散、batchsize的影响的问题(二)

  上一篇主要是对卷积神经网络的整个训练过程中公式以及误差的推导给出详细的分析。   博客地址:https://cloud.tencent.com/deve...

47290
来自专栏机器之心

资源 | 如何只用NumPy码一个神经网络

注:本文将包含大量用 Python 编写的代码片段。希望读起来不会太无聊。:)所有源代码都可以在作者的 GitHub 上找到。链接:https://github...

9720

扫码关注云+社区

领取腾讯云代金券