（计算机应用技术专业论文）分支合并对决策树归纳学习的影响.pdf

摘要 摘要 决策捌归纳学习算法是目i j 订商业数据挖掘工具中使用最为广泛的算法之一，因 其形状像树且应用于决策而得名。它是一种逼近离散值目标函数的归纳推理方法， 在这种方法中学习到的函数被表示为一棵决策树。这个决策树模型能够表示发现描 述类别的模式，用于完成预测任务。决策树是目前用于预测和分类的主要技术，特 别是商用领域，已经被成功地应月j 到从学习医疗诊断到学习评估贷款申请的信用风 险的广阔领域。简而言之，决策树能够将数据转换成知识。 传统的决策树构建方法，山于其选择扩展属性时的归纳偏置，导致属性值较多 的属性总会被优先选择，从而导致树的规模过大，并且泛化能力下降，因此需对其 进行简化。剪枝是简化的一种，主要分为预剪枝和后剪枝。本文针对预剪枝中的分 支合并进行研究。分支合并就是在树的产生过程中，将当前扩展属性的两个( 或多 个) 属性值所在分支合并成一个分支，然后继续树的卜长。本文中提出了两种分支 合并算法，基于j 下例比的分支合并算法( s s i d ) 和基于s v m 中m a r g i n 的分支合 并算法( m i d ) 。随后又基于信息增益讨论了分支合并的可行性，提出了基于最大信 息补偿的分支合并算法( m c i d ) 。实验结果表明，几种分支合并算法在树的规模、 泛化能力等方面要优于利用s e e 5 构建的决策树。 关键词决策树归纳；归纳偏置；后剪枝；预剪枝；分支合并；信息补偿 a b s t r a c l a b s t r a c t d e c i s i o nt r e ei so n eo ft h em o s tw i d e l yu s e da l g o r i t h m si nc o m m e r c i a ld a t am i n i n g t o o l s a n dw en a m ei td e c i s i o nt r e eb e c a u s ei ti sat r e ea n di su s e dt od os o m ed e c i s i o n s i t sam e t h o df o ra p p r o x i m a t i n gd i s c r e t e - v a l u e dt a r g e tf u n c t i o n s ，i nw h i c ht h el e a r n e d f u n c t i o ni s r e p r e s e n t e db yad e c i s i o nt r e e t h i sm o d e lc a nd e n o t et h ep a t t e r no f d e s c r i b i n gc l a s s i f i c a t i o n ，a n db eu s e dt oa c c o m p l i s hp r e d i c t i o nt a s k s a tp r e s e n td e c i s i o n t r e ei st h em a i nt e c h n i q u ei nt h ep r e d i c t i o na n dc l a s s i f i c a t i o n ，e s p e c i a l l yi nc o m m e r c i a l f i e l d s ，w h i c hh a sb e e ns u c c e s s f u l l ya p p l i e dt oab r o a dr a n g eo ft a s k sf r o ml e a r n i n gt o d i a g n o s em e d i c a lc a s et ol e a r n i n gt oa s s e s sc r e d i tr i s ko fl o a na p p l i c a n t s i ns h o r t ， d e c i s i o nt r e ec a nh e l py o ut r a n s f o r md a t ai n t ok n o w l e d g e s i n c ei n d u c t i v eb i a se x i s td u r i n gt h ep r o c e s so fs e l e c t i o no fe x p a n d e da t t r i b u t e s ， a t t r i b u t ew i t hm o r ev a l u e sa r eu s u a l l yp r e f e r r e dt ob es e l e c t e d i tc o n s e q u e n t l yr e s u l ti sa d e c i s i o nt r e ew i t hl a r g es c a l ea n dw i t hp o o rg e n e r a l i z a t i o nc a p a b i l i t y t h e r e f o r ei ti s n e c e s s a r yt os i m p l i f yt h ed e c i s i o nt r e ei n c l u d i n gp r e p r u n i n ga n dp o s t - p r u n i n g t i f f s p a p e rw i l lf o c u so nt h ep r e p r t m i n g an e 订s t r a t e g y ( m e r g i n gb r a n c h e s ) o fp r e 。p r u n i n gi s g i v e n ，t h a ti s ，a tt h ep r o c e s so ft r e eg r o w t h ，t w ob r a n c h e s ( o rm o r e ) f r o mt h es a m en o d e m e r g ei n t oo n eb r a n c ha n dt h e nt h et r e eg r o w t hp r o c e s sc o n t i n u e s f i n a l l y ，t h e r ei sv e r y g r e a td i s p a r i t yb e t w e e nt h et r e e sw i t ha n dw i t h o u tm e r g i n gi na s p e c to ft h es t r u c t u r e ，s i z e ， c o m p l e x i t ya n dt h ea c c u r a c y w ep r o p o s e dt w oa l g o r i t h m so fm e r g i n gb r a n c h e sf i r s t l y ： s s i d ( b a s e do nt h ep r o p o r t i o no fp o s i t i v es a m p l e s ) a n dm i d ( b a s e do nt h em a r g i n e n l a r g e m e n to fs v m ) a n dt h e nb a s e do nt h ei n f o r m a t i o ng a i n ，t h i sp a p e rt h e o r e t i c a l l y a n a l y z e st h ec o m p l e x i t yo fad e c i s i o nt r e eb e f o r ea n da f t e rm e r g i n gb r a n c h e s ，a n d d e s i g n s o n ea l g o r i t h mo f m e r g i n gb r a n c h e sm c i d ( b a s e do n t h em o s t g a i n c o m p e n s a t i o n ) e x p e r i m e n t a lr e s u l t ss h o wt h a tw i t hr e s p e c tt ot h ec o m p r e h e n s i b i l i t ya n d t h e g e n e r a l i z a t i o nc a p a b i l i t y , t h et h r e ea l g o r i t h m sa r es i g n i f i c a n t l ys u p e r i o rt ot h e f r e q u e n t l yu s e ds e e5s y s t e m ( t h ei m p r o v e dv e r s i o no fc 4 5 ) k e yw o r d sd e c i s i o nt r e ei n d u c t i o n ；i n d u c t i o n b i a s ；p r e p r u n i n g ；p o s t p r u n i n g ； m e r g i n gb r a n c h e s ；i n f o r m a t i o ng a i nc o m p e n s a t i o n 河北大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得河北大学 或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了致谢。 作者签名：褪墨堕作者签名：生之丞! ! 筮 日期：尘王年月上闩 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他 复制手段保存论文。 本学位论文属于 l 、保密口，在年月同解密后适用本授权声明。 2 、不保密囤。 ( 请在以上相应方格内打“4 ” ) 作者签名：垄墨墨墅日期 导师签名：乏丝 ：2 丑年上月上f |：丑年l 月上同 日期：旦亚年上月生同 第l 章绪论 i 1 研究背景与意义 第1 章绪论 随着数掘挖掘技术越来越广泛的应用，决策树作为数据挖掘技术中一利，分类问题的 解决方法也受到重视，f 在被广泛的研究。约二十多年前，决策树这种数据挖掘技术的 形式就已经和现在非常相似了，算法的早期版本可以追溯到二十世纪六十年代。以后决 策树归纳学习算法被广泛应用到许多进行分类识别的应用领域。这类算法无需相关领域 知识，归纳的学习与分类识i i l , j 操作处理速度都相当快。决策树也是分析消耗、发现交 叉销售机会、进行促销、信用风险或破产分析和发觉欺诈行为的得力工具。采用决策树， 可以将数据规则可视化，也不需要长时f u j 的构造过程，输出结果容易理解，精度较高， 因此决策树住知彭 发现系统中应用比较广泛。 决策树因其形状像树且用于决策而得名。从技术上讲，一个决策树山一系列节点和 分支组成，丽节点和予节点之间7 髟成分支，节点代表着决策过程中所考虑的属性，丽不 周属性值形成不同分支。为了利用决策树对某一事例做出l 决策，可以利用这一事例的属 性值并山树根向下搜索直至叶节点，叶节点j - l l 包含着决策结果。构建决策树的算法有 很多，比较流行的有i d 3 ，c 4 5 ，c a r t 和c h a i d 等，虽然它们在某些方面各有不同，但 祚：攮于信息论技术构造决策树上却是一致的。构造决策树的算法通过测试对象的属性来 决定它们的分类。决策树的构建是出上至下的贪心选择过程。在树的每个节点都有个 属性被测试。测试结果被用来划分对象集。反复进行上述过程直至某一子树中的集合相 对分类标准而言是同类的，这一集合就成为f j 节点。在每一节点，被测试的属性是根据 信息论标准来选择的。这一标准就是寻找具有最大信息增益属性【2 8 2 9 。随着决策树技术 的不断发展，又出现了很多新的构建决策树的算法，比如斜决策树，模糊决策树等! d 叫i 。 本文主要对i d 3 进行研究改进。 随着决策树技术的不断发展，人们在使用决策树技术的过程q ，逐渐发现它某些不 方便的地方。比如许多决策树山于对训练数据的过度拟合和选择- t 。展属性时的归纳偏 河北人学j ：学硕十学位论文 置，导致构建的决策树往往过于庞大，节点过多，泛化精度降低，不利于人们理解等等。 因此，大量的专家学者致力于对决策树进行改进优化【4 6 ，4 1 。 1 2 本课题的国内外发展现状 决策树归纳学习算法提出以后，至今已经有浩瀚的文献研究其算法的改进及在具体 领域的应用。这些算法改进的研究主要集中在( 1 ) 展开结点时新的启发式信息的探索： ( 2 ) 决策树的优化或产生式规则的简化：( 3 ) 决策树的抗噪音能力：( 4 ) 与其它归纳 学习策略的比较。这些算法改进研究的主要目标基本上都是增强决策树的可理解性、减 少决策树生成算法的计算复杂性、以及提高树的泛化精度。一个好的归纳学习算法应该 在这三个方面达成一个合理的折衷 3 0 , 3 1 】。 决策树的优化问题有很多。本文只对树的剪枝进行研究。对树进行剪枝( 修剪) 有 多种算法，一般人们将其分为五大类方法 1 2 , 1 4 1 。最常用的是直接控制树大小的一类方法， 通过预剪枝( 前期修剪，即在树扩展过程中强行增加一个停止规则) ，或后剪枝( 后期 修剪，在树生成后剪掉子树) 完成，或逐渐调整树的大小。再一类方法主要是扩展测试 集，首先按特征构成是数据驱动还是假设驱动( 即借助于以前建立的树预测构件特征) 的差别，将建立的特征组合分割，然后在此基础上引进多变量测试集。这些方法在调整 树表达时有效地扩展了树集。第三类，包括选择不同的测试集评价函数，通过改善连续 特征的描述，或修改搜索算法本身实现。第四类，数据库约束，即通过削减数据库或事 例描述特征集来简化树。第五类，将树转换成另一种数据结构( 如决策表或决策图) 。 这些方法通常可以在同一种算法中相互结合，进而增强各自的功能。简化决策树的最常 用方法是在树建立过程中控制其大小，包括预剪枝( 前期修剪) 和后剪枝( 后期修剪) 【1 2 ，1 4 ，1 6 ，2 2 o 后剪枝是人们普遍关注的树简化方法，后剪枝算法输入一个未修剪的树7 1 ，输出修 剪了丁中一个或多个子树后获得的树丁。算法并非搜索每个可能的t ，而是借助于启发 式搜索。修剪将子树转化为叶，进而用叶节点替代内部节点。与预剪枝不同的是，后剪 枝没有使用一个消除细节的函数，而是直接采用默认的同质暂停规则。当树相对训练集 冗余时( 即噪声参与了建模) ，修剪将非常有效地提高精确度。例如，给定训练集m ， 假设包含训练集刀的叶节点类标签为多数满足胛玎，则替代错误率为( ，7 一门) ， ，低 第1 章绪论 层叶节点对替代精确度的影响最小，因而被最先修剪。后剪枝方法借助于多种评价函数， 川以确定修剪一个节点是削弱还是增强了事例集的精确度。恰当的修剪可以提高分类精 度。尤其是当训练集噪声级别比较高时，修剪相当有效1 8 m 14 | 。 有些后剪枝方法将训练集分为两个子集1 37 1 。一个用于生成树，另一个用于后j f 月修剪。 不妨称之为生成集和修剪集。生成集常用于生成一个树，然后，按修剪变量生成树集s ， 修剪集将从s 中选择一个最佳的榭引。例外情况是减小错误率修剪( r e p ) ，即修剪集对 倒进行修蓟，而不单单是选择。修剪集方法的优势在于生成树集，而非一个树。尤其是 当领域专家算法对选择的树不满意时，可以从树集中进行人为挑选，树集归纳可以提高 预测的精确度；：l 哿i l l 练集分为两个子集的不足之处在于，设计决策受人为影l 悃，小的训 练集可能产生一个很小的树，因为低层部分被勇掉，但这恰恰是应该选择个尽可能大 的i ) l l 练集的i 4 盘t - 的理山，减小训练集的大d , k h 当于增加了修剪预测精确度的不确定性 1 1 7 1 。后剪枝有多种算法【3 3 j ，如m c c p 、r e p 、m e p 、c v p 、p e p 、e b p 等，虽然它们各 自的简化程度和精确度各不相同，却都可以非常有效的在树的精确度和简易性问作出均 衡，使清晰决策树在保持较高分类精度的同时，树的舰模尽可能的小，即 艮好的体现出 实施后剪枝方法所要达到的目标。 预剪枝阻止决策树按默认的同质暂停规则生成一个“完全”的树，要作到这一点， 需在树生成进程巾加入另一个暂停规则。自由限制树的简易修剪形式非常适用，然而， 通常暂停规则将评价树继续扩展的效应，如果效用为零( 或很小) ，则停止扩展。或者 晚此后的处理对树的输出形念影i 哟不大。约束暂停规则往往同时过滤掉相关和无关测试 集，而且，当选择测试集和修剪时使用对某个节点是局部的同一个测试约束时会出现问 题，因为约束的绝对值往往囚样本的大小不同而变化。预剪枝会引起树在不完全成熟之 前停止，即树可能在不应停j l f j j t l - j 候而停止扩展，或称之为h o r i z o n 效应f j i 3 引。即使这 样，预剪枝对大规模的实际应用还是值得研究的。 本文研究了在决策树的产生过程中相当于预剪枝的分支合并策略对决策树归纳学 习的影响，目d 玎尚未发现有关的完整的讨论【4 6 - 1 4 j 。分支合并就是在树的构建过程中， 当6 订节点选择完扩展属性后，将节点按照扩展属性的取值展开分支，然后根据某种策略 将该节点的两个或多个分支合并成一个，然后继续树的构建。迄今关于分支合并的参考 文献很少，现简要综述如下：洪家荣于1 9 9 5 年在【2 7 h ，最早提出：i d 3 及其它已有的决策 树算法只是试图减少树的深度，而忽略了对决策树叶子数目的研究，然而丁f 是后者对决 1 洞，i 匕人学j ：学硕十学位论文 策树的精度起主要作用，因而提出一种基于属性聚类方法的决策树分支合并算法；而后 王熙照，洪家荣于【2 0 】继续了 2 7 的工作将此分支合并策略推广到了模糊决策树以及相 应的优化问题：毕建东，杨桂芳于【2 6 】提出了一种基于熵的分支合并算法，即计算当日订 节点的扩展属性中每个属性值所在分支的分类信息熵，将熵相等的属性值所在分支合并 为一个分支；最近，吴宣为，史斌宁在 3 4 】，一种新的简化i d 3 决策树的算法中提出了一 种属性层次互换的分支合并算法，z e n g c h a n gq i n 署l l o n a t h a nl a w r y 在 2 5 】中研究了一种 基于语义的向前分支合并算法。 1 3 本课题研究的主要内容 本文研究了一般的分支合并策略对决策树归纳学习的影响。具体讨论了在决策树的 产生过程中，选择适当的分支合并策略能否增强树的可理解性，减少树的复杂程度，提 高树的泛化精度。基于信息增益，文章理论分析了分支合并后树的复杂程度，设计实现 了基于正例比的分支合并算法s s i d ，基于s v m 中m a r g i n 的分支合并算法m i d ，实验 证明这两种算法得到的决策树在可理解性和泛化精度方面优于s e e 5 构件的决策树。 我们分析了合并后的决策树，发现在进行分支合并后的属性，其信息增益会减少， 我们称之为增益丢失，用g l o s s ( g a i nl o s s ) 表示。在某种程度上这与q u i n l a n 禾l j 用信息增 益最大来选择扩展属性的原则有些背离。我们提出了一个增益补偿的概念，即为合并后 的分支继续选择扩展属性得到一个信息增益，减去不进行合并该两个分支继续选择扩展 属性得到的信息增益的加权和，即为增益补偿，用g c o m ( g a i nc o m p e n s a t i o n ) 表示。为 了使增益补偿最大，我们提出了基于最大增益补偿的分支合并算法m c i d 。实验表明通 过m c i d 构建的决策树在可理解性和泛化精度方面也优于s e e 5 构件的决策树。 1 4 本文组织 全文的组织结构概括如下： 第l 章绪论。 第2 章决策树归纳学习算法介绍。主要介绍了利用i d 3 算法构建决策树的过程，以 及决策树的适用问题，及构建中的常见问题。 第3 章分支合并及其对决策树归纳学习的影响。这一章介绍了几种分支合并算法： - 4 筇1 章绪论 基于币例比的分支合并算法( s s d ) ：基于s v mt f lm a r g i n 的分支合并算法 ( m i d ) ；基于最大信息补偿的分支合并算法( m c i d ) 。并通过实验和定理分 析了迸行分支合并对决策树归纳学习的影响，论汪了分支合并的可行性。 第4 章总结与展望。对本文所做工作及创新点进行了总结，并对后续于i ：展的工作进 行了展望。 河北人学1 ：学硕十学何论文 2 1 简介 第2 章决策树归纳学习算法介绍 人工智能已经发展了多种技术来建造分类模型，其中基于归纳的学习是比较流行的 方法之一。归纳在已知信息中寻找模式以推导合理的结论，归纳而来的分类模型可以是 一系列规则，也可以是决策树。 决策树曾在相当长的时间内是一种非常流行的人工智能技术。2 0 世纪8 0 年代，它是 构建人工智能系统的主要方法之一。2 0 世纪9 0 年代初，这一技术随着人工智能遭遇低潮 而逐渐不为人所注意。然而，2 0 世纪9 0 年代后期，随着数据挖掘技术的兴起，决策树作 为一个构建决策系统的强有力的技术而重新浮出水面。随着数据挖掘技术在商业智能等 方而的应用，决策树技术将在未来发挥越来越强大的作用【1 4 , 3 5 , 3 6 。 2 2 决策树表示法 决策树通过把实例从根结点排列( s o r t ) 到某个叶子结点来分类实例，叶子结点即 为实例所属的分类。树上的每一个结点指定了对实例的某个属性( a t t r i b u t e ) 的测试， 并且该结点的每一个后继分支对应于该属性的一个可能值。分类实例的方法是从这棵树 的根结点开始，测试这个结点指定的属性，然后按照给定实例的该属性值对应的树枝向 下移动。这个过程再在以新结点为根的子树上重复。 分类一个样例的方法是，将其沿根结点排列到合适的叶子结点，然后返回与这个叶 子结点关联的分类( 本例中为p 或n ) 。图2 1 画出了一棵典型的学习到的决策树。这棵决 策树根据天气情况分类“星期六上午是香适合打网球”。例如，下面的实例： 将被沿着这棵决策树的最左分支向下排列，因而被评定为反例( 也就是这棵树预测这个 实例p l a y t e n n i s 2 n ) 。 通常决策树代表实例属性值约束的合取( c o n j u n c t i o n ) 的析取式( d i s j u n c t i o n ) 。从 6 第2 章决策树i j l 纳学习算法介宝“ 树根到树叶的每一条路径对应组属性测试的合取，树本身对应这些合取的析取。例如， 图2 1 表示的决策树剥。应于以下表达式4 击1 4 】： ( o u t l o o k = s u n n yah l i m i d j i y = n o r m a l ) v ( o u t l o o k = o v e r c a s t ) v ( o u t l o o k = r a i n w i n d = f a l s e ) j ( p l a y t e n n i s = p ) ( o u t l o o k = s u n n yah u m i d i t y = h i g h ) v ( o u t o o k = r a i naw i n d = t r u e ) = ，( p l a y t e n n i s = n ) 图2 1 打网球天气情况的决策树 2 2 基本的决策树学习算法 上而提到了决策树可以用来进行决策，那么如何构建决策树呢? 构建决策树的方法 有很多，比较流行的有i d 3 ，c a 5 ，c a r t 和c h a l d 等。虽然它们在某些方面各有不同， 但在基于信息论技术构造决策树上却是一致的，都是采用白顶向下的贪婪搜索遍历可能 的决策树空问。下面以i d 3 为例介绍一下基于信息增益的决策树构建方法。 i d 3 算法的核心问题是选取在树的每个结点要测试的属性，然后根据属性的取值为 分支展开该节点。我们希望在每个节点选择的属性都是最有助于分类实例的属性，即所 谓最佳的属性。那么衡量属性价值的一个好的定量标准是什么呢? 这晕将定义个统计 属r e ，称为“信息增益( i n f o r m a t i o ng a i n ) ”，用柬衡量给定的属性区分训练样例的能力。 i d 3 算法在增长树的每一步使用这个信息增益标准从候选属性巾选择属性。 河北人学f ：学硕十学何论文 设e = 2 d 2 p ，是投维有穷向量空阳1 ，其中b 是有穷离散符号集，互中的元 素p = ( 1 ，l ，屹，) 为样例，其中_ 2 ( f = 1 ，2 ，卅) 。设p e 矛nn e d 的两个子集，分别 叫做正例集和反例集【2 7 】。 为了精确地定义信息增益，我们先定义信息论中广泛使用的一个度量标准，称为熵 ( e n t r o p y ) ，它刻画了任意样例集的纯度。 定义2 1 ： 如果一个结点e 中含有p 个正例和玎个反例，则此结点e 的分类信息熵 ( 简称熵) 定义为： l ( p ， ) = 一南l o 。o z - p - p 万- 一万nl 0 9 2 p + i ( 2 - 1 ) 定义2 2 ： 如果属性a 有历个属性值： 4 ，4 ，a 。) ，它将结点e 分割成聊个子集 互，最，e ，) 。假设其中e 中含有只个f 例和啊个反例，那么属性a 的分割信息熵为： e l a ) ：艺攀j ( n t ) ( 2 - 2 ) p + ，7 定义2 3 ：以a 为为扩展属性展开一个结点时，其信息增益定义为： g a i n a ) = l ( p 7 ) 一e ( a )l 2 - 3 、) 基于信息增益的l d 3 算法可简要捕述如下： 对给定的叶结点标准： w h i l e 当存在非叶子结点时，按某种策略挑选一个作为当自订结点 d o 在当前结点的所有候选属性中挑选一个信息增益最大的属性，按其属性值将此 结点展开，并根据叶节点产生标准标识每个分支。 这里的叶结点标准会根据不同的算法而有所不同，一般为： 1 ) 到达节点的样例个数为0 ； 2 ) 到达节点的样例类别属性相同； 3 ) 到达节点的样例集合中某类样例所占比例超过设定的阈值； 4 、) 候选属性集合为空。 ， 则对下面的数据集合利用i d 3 算法构建的决策树见图2 1 ( 数据集合来源于【1 4 】) 。 8 第2 章决策树门纳学习算法介 “ 表2 1 打网球天气情况的事例集 属。性 编号 p l a y t e n n i s o u t l o o k t e m p e r a t u r e h u m i d i t y w i n d y 1 s u n n y h o t h i g h f a l s en 2 s u n n y h o t h i g h t r u en 30 v e r c a s th o t h i g h f a l s ep 4r a i nm i l d h i g h f a l s ep 5r a i nc o o ln o r m a lf a l s ep 6r a i nc o o ln o m l a lt r u en 70 v e r c a s tc o o ln o r m a lt r u ep 8 s u n n y m i l d h i g h f a l s en 9 s u n n y c 0 0 ln o r m a lf a l s ep 1 0 r a i n m i l dn o r m a lf a l s ep 1 1 s u n n y m i l dn o r m a lt r u ep l20 v e r c a s tm i l d h i g h t l u ep 13o v e r c a s th o tn o r m a lf a l s ep 14r a i nm i l d h i g h t r u en 2 。3 决策树学习的适用问题 上面介绍了构建决策树的i d 3 算法。那么决策树学习角莩决的川题通常具有什么样的 特征呢? 实例足山“属性值”列( p a i r ) 表示的。实例足用一系列固定的属性( 例如， t e m p e r a t u r e ) 和它们的值( 例如，h o t ) 来描述的。最简单的决策树学习中，每 一个属性取少数的离散的值( 例如，h o t 、m i l d 、c o l d ) 。然而，扩展的算法也 允许处理值域为实数的属性( 例如，数字表示的温度) 。 目标函数具有离散的输出值。图2 1 的决策树给每个实例赋予一个布尔型的分 类( 例如，p 或n ) 。决策树方法很容易扩展到学习有两个以上输出值的函数。 一种更强有力的扩展算法允诈：学习具有实数值输出的函数，尽管决策树在这种 情况下的应用不太常见。 河北人学1 ：学硕十学传论文 可能需要析取的描述( d i s j u n c t i v ed e s c r i p t i o n ) 。如上面指出的，决策树 艮自然 地代表了析取表达式。 训练数据可以包含错误( 噪音) 。决策树学习对错误有很好的鲁棒性，无论是 训练样例所属的分类错误还是描述这些样例的属性值错误。 训练数据可以包含缺少属性值的实例。决策树学习甚至可以在有未知属性值的 训练样例中使用( 例如，仅有一部分训练样例知道当天的湿度) 。这个问题将 在后面的章节中讨论。 已经发现很多实际的问题符合这些特征，所以决策树学习已经被应用到很多问题 中。例如根据疾病分类患者；根据起因分类设备故障；根据拖欠支付的可能性分类贷款 申请。对于这些问题，核心任务都是要把样例分类到各可能的离散值对应的类别 ( c a t e g o r y ) 中，因此经常被称为分类问题( c l a s s i f i c a t i o np r o b l e m ) 。 2 4 决策树学习的常见问题 决策树学习的实际问题包括确定决策树增长的深度；处理连续值的属性；选择一个 适当的属性筛选度量标准；处理属性值不完整的训练数据；处理不同代价的属性：以及 提高计算效率等等。下面我们简单讨论其中的几个问题。 2 4 1 避免过度拟合( o v e r - f it tin g ) 数据 图2 1 中的决策树，恰好能对训练样例完美地分类。然而这个策略并非总是行得通 的，事实上，当数据中有噪声，或训练样例的数量太少以至于不能产生目标函数的有代 表性的采样时，这个策略便会遇到困难。在以上任一利，情况发生时，这个简单的算法产 生的树会过度拟合训练样例。 对于一个假设，当存在其他的假设对训练样例的拟合比它差，但事实上在实例的整 个分布( 也就是包含训练集合以外的实例) 上表现的却更好时，我们说这个假设过度拟 合训练样例。 定义2 4 ：给定一个假设空间h ，一个假设h ，如果存在其他的假设h h ，使 得在训练样例上h 的错误率比h7 小，但在整个实例分布上h 的错误率比h 小，那么就说 假设h 过度拟合训练数据。 1 n 第2 章决策树门纳学习算法介呈“ 是什么原因导致h 比h7 更好地拟合训练样例，但对于后来的实例却表现更差呢? 这 种情况发生的一种可能原因是训练样例含有随机错误或噪声。举例说明，考虑在表2 1 中本来f 确的样例中加入一条训练正例，但却被误标记为反例，如下： 对于本来没有错误的数据，i d 3 生成图2 1 表示的决策树。然而，增加这个不证确 的样例导致i d 3 建立一个更复杂的树。确切地讲，新的样例会被排列到图2 1 表示的树 的左起第二个叶子结点。因为新的样例被标汜为反例，所以i d 3 会在这个结点下面进一 步搜索更多的细节。当然只要新的错误样例与原来这个结点的两个样例有任何差异，i d 3 会成功找到一个新的决策属性来把新的样例从以f i 的两个正例中分开。这样的结果是 i d 3 会输出一个决策树( h ) ，它比图2 1 中原来的树( h ) 更复杂。当然，h 会完美地拟 合训练样例集，而较简单的h7 不会。然而，由于新的决策结点只是拟合训练样例r - l 噪声 的结果，我们可以断定在取自同一实例分析i 的后续数据上，h7 会胜过h 。 事实上，当训练数据没有噪声寸，过度拟合也有可能发生，特别是当少量的样例被 关联到叶子结点时。这种情况下，很可z 匕1 u j a i f 现巧合的规律性，使得一些属性恰巧可以很 好地分割样例，但却与实际的目标函数并无关系。一旦这样巧合的舰律性存在，就有过 度拟合的j x l 险。 有几种途径用来避免决策树学习巾的过度拟合。它们可被分为两类： 1 ) 预剪枝( 6 玎期修剪) ，在i d 3 算法完美分类i ) t i 练数据之6 订停止增长树； 2 ) 后剪技( 后期修剪) ，即允许树过度拟合数据，然后对这个树后修剪。 在第三章将会详细介绍预剪枝。 2 4 。2 合并连续值属性 我们最初的i d 3 定义限制为取离散值的属性。首先，学习到的决策树要预测的目标 属性必须是离散的。其次，树的决策结点的属性也必须是离散的。可以简单地删除第二 个限制，以及数据集合的所有属性必须使离散的。对于连续值属性，可以通过动态地定 义新的离散值属性来实现，即先把连续值属性的值域分割为离散的区问集合。例如，对 1 ：连续值的属性a ，算法呵动念地创建一个新的斫j 尔属性彳f ，如果a 5 4 和t e m p e r a t u r e 8 5 的信息增益，并选择 最好的( t e m p e r a t u r e 5 4 ) 。现在这个动态创建的命尔属性便可以和其他候选的离散值属 性一同“竞争9 9 1 1 以用于增长决策树。f a y y a d & i r a n i ( 1 9 9 3 ) 讨论了这种方法的一个扩 展，即把连续的属性分割成多个区问，而不是基于单一阂值的两个区问。在本论文第三 章中数据预处理采用的是k o h o n e n 算法进行离散化。 2 4 3 属性选择的其他度量标准 信息增益度量存在一个内在偏置，它偏袒具有较多值的属性。举一个极端的例子， 考虑属性d a t e ，它有大量的可能值( 例如m a r c h4 ，1 9 7 9 ) 。要是我们把这个属性加到表 2 1 的数据中，它会在所有属性中有最大的信息增益。这是因为单独d a t e 就可以完全预 测训练数据的目标属性。于是这个属性会被选作树的根结点的决策属性并形成一棵深度 为一级但却非常宽的树，这棵树可以理想地分类训练数据。然而，这个决策树对于后来 数据的性能会相当差，因为尽管它完美地分割了训练数据，但它不是一个好的预测器 ( p r e d i c a t o r ) 。 属性d a t e 出了什么问题了昵? 简单地讲，是因为它太多的可能值必然把训练样例 分割成非常小的空问。因此，相对训练样例，它会有非常高的信息增益，尽管对于未见 实例它是一个非常差的目标函数预测器。 第2 章决策树门纳学习贸：法介 “ u l_i i 避免这个不足的一种方法是用其它度量，而不是信息增益，来选择决策属性。一个 可以选择的度量标准是增益比率( g a i nr a t i o ) ( q u i n l a n1 9 8 6 ) ( 详细介绍请参考【4 也1 4 】) 。 l o p e zd em a n t a r a s ( 1 9 9 1 ) 介绍了另一种直接针对上述问题而设计的度量，它是基于距 离的( d i s t a n c e b a s e d ) 。这个度量标准基于所定义的一个数据划分i r , j 的距离尺度。每个 属性的评估根据它产生的划分与理想划分( 也就是完美分类训练数据的划分) 间的距离。 然后选择划分最接近完美划分的属性。l o p e zd em a n t a r a s ( 1 9 9 1 ) 定义了这个距离度量， l j e i j 了它不偏向有大量值的属性，并报告了其实验研究，说明这种方法产生的决策树的 预测精度与增益法和增益比率法得到的没有明显的差别。而且这种距离度量避免了增益 比率度量的实际团难，在他的实验中，对于属性值个数差异非常大的数据集，这种方法 产生了效果很好的较小的树。 此外，学者们还提出了多种属性选择度量( 例如，b r e i m a ne ta 1 19 8 4 ；m i n g e r s1 9 8 9 a ： k e a r n s & m a n s o u r1 9 9 6 ；d i e t t e r i c he ta 1 1 9 9 6 ) 。m i n g e r s ( 1 9 8 9 a ) 提供了实验分析，比 较了钏对不同问题的几种选择度量的有效度。他报告了使用不同属性选择度量产生的未 修剪决策树的大小的显著差异。然丽在他的实验巾，不同的属性选择度量对最终精度的 影响小于后剪枝的程度和方法对最终精度的影l l 向。 2 4 ，4 处理缺少属性值白, - i j l l 练样例 在某些情况下，可供使用的数据可能缺少某些属性的值。例如，在医学领域我们希 望根= l ：l j 多项化验指标预测患者的结果，然而可能仅有部分患者具有验j f 结果。在这种情 况下，经常需要根据此属性值已知的其他实例，来估计这个缺少的属性值。 考虑以下情况，为了评估属性a 是否是决策当前结点的最佳测试属性，要汁算决策 树在该结点的信息增益g ( ，砌似) 。假定样例p = ( v i ，v 2 ，v ，) 中属性a 的值v 未知。 处理缺少属性值的一种策略是赋给它训练样例【1 1 该属性的最常见值( 第三章巾的数 据预处理采用该方法) 。另一种策略是可以赋给它被分类为v ，的训练样例中该属性的最 常见值。然后使用这个估计值的训练样例就可以被现有的决策树学习算法使用了。 m i n g e r s ( 1 9 8 9 a ) 中分析了这个策略。 第二种稍微复杂的策略是为彳的每个可能值赋与一个概率，而不是简单地将最常见 的值赋给，。根据结点样例上a 的不同值的出现频率，这些概率可以被再次估计。例如， i3 河北人学：学硕十学付论文 给定个布尔属性4 ，如果当前结点包含6 个已知么= l 和6 个a = o 的样例，那么，。= 1 的概率是0 6 ，2 0 的概率是0 4 。于是，样例p = ( h ，v 2 ，) 的6 0 被分配到a = 1 的 分支，4 0 被分配到另一个分支。这些片段样例( f r a c t i o n a le x a m p l e s ) 的目的是计算信 息增益，另外，如果有第二个缺少值的属性必须被测试，这些样例可以在后继的树分支 被进一步细分。上述的样例的片段也可以在学习之后使用，用来分类缺少属性的新实例。 在这科- 情况下，新实例的分类就是最可能的分类，计算的方法是通过在树的叶结点对按 不同方式分类的实例片段的加权求和。 第3 章分支合行及其对决策树l j 7 f lj , 学习的影响 第3 章分支合并及其对决策树归纳学习的影响 3 1 分支合并介绍 基于i d 3 算法产生的决策树的规模( 中问结点和叶子结点的个数) 和结点的熵有着 直接的关系。虽然这个关系迄今尚未有一个确定的或概率的表示，但人们普遍认为结点 的熵越大其子树的规模将越大。基于这种考虑，i d 3 算法在展开一个非叶结点时选择了 信息增益( 即父结点的熵减去儿子结点熵的加权平均) 最大作为标准。 在树的产生过程中，如果一个结点的两个( 或多个) 儿予结点合并为一个分支( 简 称分支合并) 并继续树的生长，则最终产生的树与t f j m 结点没有合并所产，土的树，从结 构、规模、复杂性、精度等方面上将有很火区别。问题是分支合并后的决策树能否在整 体上( 或在某些指标上) 优于原来的决策树? 如果答案肯定，如何选择合适的分支合并策 皤? 首先给出j 个例子来简单说明一下分支合并。考虑表3 1 所示的一个简单分类问题： 表3 1 一纽小的训练样例 样例属性a属性b属性c类别属性 la 1 b 1 c lp 2a