（计算机应用技术专业论文）决策树算法研究及在查询接口发现中的应用.pdf

苏州大学学位论文使用授权声明 本人完全了解苏州大学关于收集、保存和使用学位论文的规定， 即：学位论文著作权归属苏州大学。本学位论文电子文档的内容和纸 质论文的内容相一致。苏州大学有权向国家图书馆、中国社科院文献 信息情报中心、中国科学技术信息研究所( 含万方数据电子出版社) 、 中国学术期刊( 光盘版) 电子杂志社送交本学位论文的复印件和电子 文档，允许论文被查阅和借阅，可以采用影印、缩印或其他复制手段 保存和汇编学位论文，可以将学位论文的全部或部分内容编入有关数 据库进行检索。 涉密论文口 本学位论文属 在年一月解密后适用本规定。 非涉密论文口 论文作者签名：熏旦蓬藿!e l 导师签名： 决策树算法研究及在查询接口发现中的应用中文摘要 中文摘要 本文针对决策树学习过程中存在的多值偏向问题，提出两种改进方法，从不同的 角度来解决i d 3 算法的缺陷并优化决策树学习算法。同时，在算法优化的基础上，以 e c l i p s e 为开发平台，设计实现了决策树算法演示软件，将其作为算法的实验平台， 并使用u c i 机器学习数据集作为实验数据，对相应的算法进行实验效果的验证。同 时又将决策树学习算法应用到d e e p w e b 查询接口发现中，更好的对查询接口进行分 类与发现。 本文的主要研究成果概括为以下四个方面： ( 1 ) 分析研究决策树构建过程中存在的多值偏向问题，并在此基础上提出了一种 基于等预测能力的决策树分支合并算法，采用预剪枝的策略对非叶子节点中 分类预测能力相等的分支进行合并。 ( 2 ) 针对经典i d 3 算法中采用信息增益作为选择标准存在多值偏向问题，引入均 欧氏距离作为启发信息，提出了一种基于均欧氏距离的决策树优化算法，通 过理论分析，该算法可以有效的克服多值偏向问题。 ( 3 ) 以决策树算法演示软件作为实验平台，将上述方法应用于其中，分析各个算 法的优劣和各类参数的性能比较，并提出可以进一步改进实验效果的若干思 想。 ( 4 ) 以d e e pw - e b 为应用平台，将改进的决策树优化算法应用于d e e pw r e b 查询接 口发现中，改善了过去查询接口发现中分类准确率较低，时间开销较大的问 题。 关键词：决策树，等预测能力，均欧氏距离，多值偏向，查询接口 作者：胡道京 指导老师：刘全( 教授) a b s t r a c tr e s e a r c h e so nd e c i s i o nt r e ea l g o r i t h ma n di t sa p p l i c a t i o nt od i s c o v e r yo fq u e r yi n t e r f a c e r e s e a r c h e so nd e c i s i o nt r e ea l g o r i t h ma n di t s a p p l i c a t i o nt od i s c o v e r yo fq u e r y i n t e r f a c e a b s t r a c t t h ev a r i e t yb i a sp r o b l e m w h i c hm e a n st h ea t t r i b u t e sw i t hm o r ev a l u e sa r eu s u a l l y p r e f e r r e dt ob es e l e c t e dd 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 ，i sa l l i m p o r t a n tp r o b l e mi nt h ed e c i s i o nt r e ea l g o r i t h m t w om e t h o d sa r ep r o p o s e dt os o l v et h e v a r i e t yb i a sp r o b l e ma n do p t i m i z et h et r a d i t i o n a ld e c i s i o nt r e ea l g o r i t h mf r o mt w od i f f e r e n t p o i n t s o fv i e w m e a n w h i l e ，o nt h eb a s i so ft h e o r i e sm e n t i o n e da b o v ea n dt h ej a v a t e c h n i q u ei ne c l i p s e ，ad e m o n s t r a t i o ns o f t w a r eo fd e c i s i o nt r e ea l g o r i t h mi sd e v e l o p e da s a ne x p e r i m e n tp l a t f o r mt ov a l i d a t et h ec o r r e s p o n d i n gm e t h o d s t h e nt h ei m p r o v e dd e c i s i o n t r e et h e o r i e sa r ea p p l i e dt ot h ed i s c o v e r yo fq u e r yi n t e r f a c ei nd e e pw e bt oi m p r o v et h e p e r f o r m a n c eo f t h ed i s c o v e r ya n dc l a s s i f i c a t i o n t h em a i nr e s e a r c hr e s u l t sa r ec o n c l u d e da sf o l l o w s ： i an e w m e r g i n gb r a n c h e sa l g o r i t h mb a s e do ne q u a lp r e d i c t a b i l i t yi nd e c i s i o nt r e e i sp r o p o s e do nt h ea n a l y s i so ft h ev a r i e t yb i a sp r o b l e mi nt r a d i t i o n a ld e c i s i o nt r e e a l g o r i t h m t h ea l g o r i t h mu s e st h ep r e - p r u n i n gs t r a t e g y , a n dm e r g e st h en o n - l e a f b r a n c h e sw h i c hh a v et h ee q u a lp r e d i c t a b i l i t y i i i no r d e rt os o l v et h ev a r i e t yb i a sp r o b l e mi ni d 3a l g o r i t h mw h i c hs e l e c t e dt h e i n f o r m a t i o ng a i na st h eas t a n d a r do fe x p a n d i n ga t t r i b u t e s ，ak i n do fa e d a l g o r i t h mb a s e do na v e r a g ee u c l i d e a nd i s t a n c ei nd e c i s i o nt r e ei sp r o p o s e di nt h i s p a p e r t h ea l g o r i t h m u s e st h ea v e r a g ee u c l i d e a nd i s t a n c ea sh e u r i s t i ci n f o r m a t i o n t h ee x p e r i m e n tr e s u l t ss h o wt h a tt h ei m p r o v e da e da l g o r i t h mc a na v o i dt h e v a r i e t yb i a so fl d 3a l g o r i t h m i i i a p p l yb o t ho ft h em e t h o d st ot h ed e c i s i o nt r e ed e m o n s t r a t i o ns o f t w a r ea sa n e x p e r i m e n tp l a t f o r ma n d t h er e s u l t sh a v eb e e na n a l y z e dt oj u d g et h ee f f i c i e n c yo f t h e s ea l g o r i t h m s a l lt h ep e r f o r m a n c e sw i t hd i f f e r e n tp a r a m e t e r sa r ec o m p a r e dt o u r e s e a r c h e so nd e c i s i o nt r e ea l g o r i t h ma n di t sa p p l i c a t i o nt od i s c o v e r yo f q u e r yi n t e r f a c e a b s t r a c t a d v a n c et h ep o s s i b l ei m p r o v e m e n ti ne x p e r i m e n tr e s u l t s i v o nt h eb a s i so fd e e pw e b ，t h ec o r r e s p o n d i n gd e c i s i o nt r e ea l g o r i t h m sa r ea p p l i e d t ot h ed i s c o v e r yo ft h eq u e r yi n t e r f a c e ，w h i c hs o l v e dm a n yp r o b l e m si nd e e p w e bs u c ha sd i s c o v e r ye f f i c i e n c y , c l a s s i f i c a t i o np r e c i s i o na n dt i m ec o s t k e yw o r d s ：d e c i s i o nt r e e ，e q u a lp r e d i c t a b i l i t y , a v e r a g ee u c l i d e a nd i s t a n c e ，v a r i e t yb i a s ， q u e r yi n t e r f a c e i i i w r i t t e nb y ：d a o j i n gh u s u p e r v i s e db y ：q u a n l i u 目录 中文摘要i a l ；s t r a c t i i 第一章引言。1 1 1 选题背景与意义1 1 2 国内外研究现状2 1 2 1 国内研究现状2 1 2 2 国外研究现状3 1 3 论文主要研究内容4 1 4 文章内容安排4 第二章理论基础6 2 1 决策树简介6 2 2 决策树发展历史7 2 3 决策树理论基础9 2 4 决策树主要算法11 2 4 1c 4 5 算法1 1 2 4 2c a r t 算法13 2 4 3s l i q 算法1 4 2 4 4p u b l i c 算法15 2 5 本章小结1 6 第三章一种基于等预测能力的决策树分支合并方法1 7 3 1 剪枝方法1 7 3 1 1 后剪枝1 8 3 1 2 预剪枝1 8 3 2 基于等预测能力的分支合并算法1 9 3 2 1 等预测能力1 9 3 2 2 基于等预测能力的分支合并算法2 0 3 3 实验结果和分析2 2 3 4 本章小结2 7 第四章一种基于均欧氏距离的决策树优化算法。2 8 4 1 均欧氏距离2 8 4 2a e d 算法基本思想2 9 4 3t l e d 算法描述2 9 4 4 多值偏向分析3 0 4 5 实验以及结果分析3 2 4 6 本章小结3 5 第五章决策树在查询接口发现中的应用。3 7 5 1d e e pw e b 查询接口3 7 5 1 1 d e e pw e b 概述3 7 5 1 2d e e pw e b 查询接口表示3 8 5 1 3 查询接口表单特征4 0 5 1 4 查询接口发现方法4 1 5 2 决策树在d e e pw e b 查询接口发现中的应用4 2 5 2 1 数据的选取与预处理4 2 5 2 2 查询接口发现算法4 3 5 2 3e p m i d 算法分类查询接口4 4 5 2 4a e d 算法分类查询接口4 4 5 3 实验以及结果分析4 5 5 4 本章小结4 6 第六章总结与展望。4 7 6 1 本文工作总结4 7 6 2 工作展望4 8 参考文献：4 9 攻读硕士期间发表( 录用) 的论文和参加的科研项目5 4 i 改谢5 5 决策树算法研究及在查询接口发现中的应用第一章引言 1 1 选题背景与意义 第一章引言 随着信息技术的发展，特别是互联网的快速发展和信息量的爆炸性增长，使得信 息的重要性与日俱增。如何在数量庞大的数据中获取有价值的信息和知识，如何利用 这些数据进行科学研究、系统优化、数据分类以及发现数据间的关系，已经成为商业 界普遍关注的问题。数据挖掘为解决这些问题而提出，并引起了学术界的广泛关注， 成为学术研究的热点，并在众多领域中得到了广泛的应用【l 。3 1 。 分类是数据挖掘中的一个重要分支，它可用于提取描述重要数据的模型或预测未 来的数据模型，能够为各个行业提供良好的决策支持。分类的主要目标是提出一个分 类函数或分类模型( 或分类器) ，然后通过得到的模型把数据库中的数据项映射到给 定类别中的某一个。分类研究在国外发展快速，已有很多成型的算法和模型，而在国 内的发展却相对滞后。数据挖掘中用于分类的技术有很多种，如决策树、神经网络、 遗传算法、贝叶斯方法、支持向量机等。由于决策树具有分类速度快、精度高、易于 理解等优点，现己成为了一种广为应用的分类方法。 决策树学习是一种逼近离散值目标函数的方法，这种方法将从一组训练样本中学 习到的函数表示为一棵决策树。决策树的叶子为类别名，其它的节点由实体的属性组 成，每个属性的不同取值对应一个分支。若要对一个实体分类，从树根开始进行测试， 按属性的取值向下进入新节点，对新节点进行测试，过程一直进行到叶节点，实体被 判为属于该叶子节点所标记的类别。决策树学习中最基本且最经典的算法是i d 3 算 法，该算法引入信息论中的信息熵的概念，采用信息增益作为选择测试属性的标准。 其基本思想是从根节点开始，自顶向下构造决策树，对于分裂的每个子树递归调用该 算法，直到叶节点为止。后来的c 4 5 、c a r t 算法等都是在i d 3 的基础上提出来的。 由于i d 3 算法在分类过程中存在多值偏向的问题，即算法偏向于选择属性取值个 数较多的属性。然而在现实世界中，取值较多的属性并不一定是最优的选择。目前对 于决策树算法的优化方法主要有剪枝、改变属性选择标准以及与机器学习中的其它分 类技术结合等。 第一章引言决策树算法研究及在查询接口发现中的应用 本文提出两种方法从不同的角度来解决决策树算法中存在的多值偏向问题，优化 决策树经典算法。实验方面，本文以e c l i p s e 为开发平台，设计实现了决策树算法演 示软件，并将其作为各种算法的实验平台，从而对相应的算法进行实验效果的验证。 最后，本文将决策树算法应用于d e e pw 曲查询接口发现中，将改进的决策树算 法应用于查询接口的发现与分类中，相应的实验结果也验证了改进算法性能的提高和 进步。 1 2 国内外研究现状 1 2 1 国内研究现状 近年来，国内许多学者从各个不同的层面、采用不同的方法和技术对决策树的相 关课题进行了研究，并发表了大量的文章。洪家荣等认为i d 3 等早期的算法只是试图 减少树的深度而忽略了对决策树叶子数目的研究，而后者对决策树的精度起主要作 用，从而提出了一种基于属性聚类方法的决策树分支合并算法1 4 j 。吴宣为等在一种新 的简化i d 3 决策树的算法的基础上，提出了一种基于属性层次关系的分支合并算法【5 j 。 王熙照等在研究分支合并理论的基础上，提出了一种基于正例比的分支合并算法和一 种基于最大增益补偿的分支合并算法 6 1 。亓常松等基于信息系统中的条件属性集离散 度，提出了基于离散度的决策树构造方法【_ 7 1 ，选择对样本空间分类一致性程度最高的 条件属性。陆秋等根据知识粒度的定义，提出了基于属性相似度的决策树算法1 8 j 。韩 松来等提出的基于关联度函数的决策树分类算法【9 】，虽然在一定程度上解决了多值偏 向问题，但并不能保证具有比i d 3 更好的准确率。屈志毅等在讨论了i d 3 算法倾向于 取值较多属性的缺点后，引入了无关度的概念，对i d 3 算法进行改进【lo 】。叶明全等 在用户兴趣度的基础上，提出了一种基于灰色关联度的决策树改进算法【1 1 1 ，这种算法 用灰色关联度取代用户关联度来修正属性的信息增益，解决了i d 3 算法中的多值偏向 问题，但在实际问题中，灰色关联度的取值很难确定，并不能很好的解决实际问题。 y e n l i a n gc h e n 等人主要处理分层结构的数据【l2 1 ，从这些数据中构建决策树，并兼顾 考虑分类的准确率与特征化( a c c u r a c ya n ds p e c i f i c i t y ) 。 除了上述内容之外，许多学者还将机器学习中的多种方法与决策树学习结合起 2 决策树算法研究及在查询接口发现中的应用第一章引言 来，并以此克服决策树学习的弱点。如王熙照等则将模糊理论的思想与决策树学习方 法结合以解决相应的问题【1 3 - 1 5 】。国内的许多专家学者则将决策树与遗传算法、神经网 络、支持向量机等理论结合在一起，在这个方面投入了大量精力进行研究，目前已经 建立了一定的理论基础【1 铊o 】并在很多领域得到了应用2 1 之3 1 。 1 2 2 国外研究现状 决策树学习研究在国外的发展比较早。从最初被提出至今，经过众多专家学者的 研究与探索，已经出现了很多重要的算法与理论。由于决策树学习方法有很多的优点， 因此对于决策树算法的改进越来越受到重视。q u i n l a n 在i d 3 算法的基础上提出了 c 4 5 算法1 2 4 1 ，用增益比率来代替信息增益作为选择扩展属性的标准。a p p a v u 等在基 于知识系统的文本分类中提出了一种新的i d 6 n b 算法，结合朴素贝叶斯算法并使用 a l p h a 和b e t a 规则进行剪枝【2 5 1 。k a n g 等在c 4 5 算法的基础上提出了一种新的决策树 学习器p a t - d t l ，用用p a t 替代a v t ，并分别采用j k l 分歧，j s 分歧和算术几何分 歧作为扩展属性的标准【2 6 】。s r u g g i e r i 提出了c 4 5 的改进算法高效c 4 5 ( e c 4 5 ： e f f i c i e n tc 4 5 ) 算、法【2 7 1 ，该算法采用二分搜索取代线性搜索，还提出了几种不同的寻找 连续属性局部阈值的改进策略。i l y e sj e n h a n i 等人提出的决策树模型主要处理具有可 能性分布的不完美数据，扩展节点时可以选择不只一个属性【2 8 】。s h i h c h i e hc h o u 等人 提出了一种多值多标签的决策树模型，主要处理具有多值多标签类型的数据【2 圳。 m i n g y uz h o n g 等人提出了一种有效的k - n o r m 修剪算法【3 0 1 ，着重考虑分类错误率的最 小化，不但计算错误率的预期值并且计算错误率的相关可靠性，理论明确并易于实现， 同时也取得了良好的实验结果。 除此以外，还有很多的专家和研究人员对决策树相关问题进行了研究，为了更好 的对决策树算法进行优化与改进奠定了基础。 尽管国内外很多专家都在对决策树学习理论，尤其是对如何解决多值偏向等问题 进行讨论和研究，同时也取得了一定的成绩，但是在决策树学习方法上，还有很多地 方值得付出更多的努力和研究以取得更大的进步。 第一章引言 决策树算法研究及在查询接口发现中的应用 1 3 论文主要研究内容 本文针对决策树学习中存在的多值偏向问题等缺陷进行了研究和分析，主要目的 是提出能在一定程度或角度上解决该问题的方法。并以决策树算法演示软件为实验平 台验证了所提方法的正确性和有效性。本文的主要研究成果归纳如下： ( 1 ) 分析研究决策树构建过程中存在的多值偏向问题，并在此基础上提出了一 种基于等预测能力的决策树分支合并算法，采用预剪枝的策略对非叶子节点中分类预 测能力相等的分支进行合并。实验结果表明改进后的决策树算法，明显减少了决策树 的宽度和叶子节点数，在时间空间复杂度和测试精度等方面都要优于i d 3 算法。 ( 2 ) 针对经典i d 3 算法中采用信息熵作为选择标准存在多值偏向问题，引入均 欧氏距离作为启发信息，提出了一种基于均欧氏距离的决策树优化算法，通过理论分 析与证明，该算法可以克服多值偏向问题。实验结果表明，改进后的算法在保持较高 分类准确率的基础上，能够有效地节省决策树的生成时间。 ( 3 ) 以决策树算法演示软件为实验平台，将上述方法应用于其中，分析各个算 法的优劣和各类参数的性能比较。既对本文所提出的算法进行了验证和分析，同时也 对实验过程中出现的问题进行分析，从而提出可以进一步提高算法性能和实验效果的 若干思想。 ( 4 ) 以d e e pw e b 为应用平台，将改进的决策树学习算法应用于d e e pw e b 查询 接口发现中，来改善过去查询接口发现中分类准确率较低，误差较大的问题。 1 4 文章内容安排 本文围绕决策树学习和决策树算法中存在的多值偏向问题，分别提出了两种不同 的解决方案，并将这两种方案应用到决策树算法演示软件的实验平台上，进行具体的 分析和研究。同时又将决策树学习理论应用到d e e pw e b 查询接口发现中。在理论和 实验结果上都取得了一定的成果，详细的论文结构安排如下： 第一章引言。本章简单地描述了决策树学习以及决策树学习中存在的缺陷，同 时阐述了国内外的相关研究状况。 第二章理论基础。本章详细地说明了有关决策树学习的一些理论基础，以及后 4 决策树算法研究及在查询接口发现中的应用 第一章引言 面所提出的方法的相关理论基础，为后面将要讨论的方法做好铺垫。 第三章提出了一种基于等预测能力的决策树分支合并算法。同时，介绍了相应 的实验以及分析结果，在选取不同数据集的同时，分析和研究了算法在数据集中的性 能、优劣性以及算法的时间复杂度。 第四章为了能够从根本上解决经典决策树算法中存在的多值偏向问题，引入均 欧氏距离替代信息增益，提出了一种基于均欧氏距离的决策树优化算法。并用理论证 明该方法可以避免多值偏向问题。同时，介绍了相应的实验以及分析结果，在选取不 同数据集的同时，分析和研究了算法在数据集中的性能、优劣性以及算法的时间复杂 度。 第五章提出了将改进的决策树学习算法应用到d e e pw e b 查询接口发现中，改 善过去查询接口发现中分类准确率较低，误差较大的问题。综合提高了查询接口发现 的性能和质量。 第六章总结与展望。在对全文进行总结的基础上，提出下一步工作可能的研究 方向，并对未来工作进行展望。 第二章理论基础 决策树算法研究及在查询接口发现中的应用 2 1 决策树简介 第二章理论基础 决策树( d e c i s i o nt r e e ) 学习方法自2 0 世纪6 0 年代以来，在分类、预测、规则提取 等领域有着广泛的应用，特别是q u i n l a n 于1 9 8 6 年提出i d 3 算法以后，在机器学习、 数据挖掘领域得到了广泛的应用与发展。在机器学习范畴内，根据反馈的不同，学习 技术可以分为监督学y - - - j ( s u p e r v i s e dl e a r n i n g ) 、非监督学y j ( u n s u p e r v i s e dl e a r n i n g ) 和强 化学( r e i n f o r c e m e ml e a r n i n g ) - - - 大类。决策树学习属于监督学习，是一种有指导的 学习方法。决策树是一种类似于流程图的树型结构，树中的节点可以分为两类：内部 节点( i n t e m a ln o d e ) 和叶节点( 1 e a f n o d e ) 。它的每一个叶节点对应着某一类另l j ( c l a s s ) ；树 的每个内部节点对应着一个属性( a t t r i b u t e ) 的划分，将该节点对应的样本集划分成若干 个子集，每个子集对应一个节点。从根节点到叶节点的一条路径形成一条分类规则。 决策树可以很方便的转化为分类规则，是一种非常直观的分类模式表示形式。 图2 1 给出了一颗典型的学习到的决策树【l 】。这棵决策树根据天气情况分类“星 期六上午是否适合打网球”。 s h i 曲 n o n o r m a l y e s y e s n 0 图2 1 典型的决策树示例图 用决策树进行分类分为两步，首先是利用训练样本生成一棵决策树，建立决策树 模型。这个过程实际上是一个从数据中获取知识，进行机器学习的过程。然后再利用 建立的决策树对输入的数据进行分类。对于输入的记录，从根节点开始依次进行判断， 6 决策树算法研究及在查询接口发现中的应用第二章理论基础 直到达到叶节点，找到该记录的类别。 决策树采用自顶向下、分而治之的递归方式，本质上是贪心算法。从根节点开始， 对数据样本进行测试，根据不同的结果将数据样本划分成不同的样本子集，每个样本 子集构成一个子节点或子树( s u bt r e e ) 。对每个子节点再进行划分，生成新的子节点。 不断反复，直至达到特定的终止准则，生成的决策树每个叶节点对应一个分类。对于 生成的决策树，可以从根节点开始，自顶向下，提取规则；也可以对新的数据集进行 分类或预测。对一个样本进行分类时，从树的根节点开始，根据每个节点对应的划分 将其归到相应的子节点，直至叶节点，叶节点所对应的类别就是该样本对应的分类。 构建决策树分为两个步骤：建树( t r e eb u i l d i n g ) 和剪枝( t r e ep r u n i n g ) 。剪枝的目的 是为了减少样本数据中的异常或噪声。 决策树学习主要适合于具有以下特征的问题中： ( 1 ) 实例是由“属性值”对表示的，实例是用一系列固定的属性和它们的值来描 述的。 ( 2 ) 目标函数具有离散的输出值，决策树给每个实例赋予一个布尔型的分类( 如 y e s 或n o ) 。决策树方法很容易扩展到学习有两个以上输出值的函数。 ( 3 ) 可能需要析取的描述，决策树能够很容易的转化成析取表达式。 ( 4 ) 训练数据可以包含错误或缺失属性，决策树学习对训练数据有很好的健壮性。 因此对于符合这些特征的问题都可以用决策树很好的解决，如根据疾病分类患 者，根据拖欠支付的可能性分类贷款申请，根据起因分类设备故障等等【l 】。决策树已 经被应用到很多现实问题中。 2 2 决策树发展历史 决策树学习是人工智能领域中比较重要的一个课题。最早的决策树学习系统要追 溯到h u n t 等人于1 9 6 6 年研制的第一个概念学习系统【3 u ( c l s ：c o n c e p tl e a r n i n g s y s t e m ) ，该系统第一次提出使用决策树进行概念学习，是许多决策树学习算法的基 础。国际上最早最有影响的决策树方法是q u i n l a n 于1 9 8 6 年提出的迭代分类器( i d 3 ： i t e r a t i v ed i c h o t o m i z e r3 ) 算法【3 1 1 ，该算法引入了信息论中熵的概念，采用分治策略， 在决策树选择各级节点上选择属性时，采用信息增益作为属性的选择标准，以便在每 第二章理论基础 决策树算法研究及在查询接口发现中的应用 一个非叶子节点上进行测试时，能获得关于被测试记录最大的类别信息。由于i d 3 不能处理属性值缺失和连续属性( 属性值为实数值) 的情况，q u i n l a n 在1 9 9 3 年又提 出了另一种分类算法c 4 5 【2 4 1 ，该算法可以看作是i d 3 算法的一个扩展，它有效地弥 补了i d 3 算法的缺点。c 4 5 和i d 3 最终生成多叉树。1 9 8 4 年l b r e i m a n 等人提出了 分类回归树( c a r t ：c l a s s i f i c a t i o na n dr e g r e s s i o nt r e e ) 算法【3 2 1 ，该方法的原理和i d 3 类似，与i d 3 不同的是，它选择具有最小g i n i 系数值的属性作为测试属性，最终生 成二叉树，再利用重采样技术能进误差估计和剪枝( 基于最小代价复杂性) ，然后选 择最优的作为最终构建的决策树。这些算法均要求训练集全部或一部分在分类的过程 中一直驻留在内存中。i b m 的m e h t a 和a g r a w a l 等人提出了一种高速可伸缩的有监 督的寻找学习( s l i q ：s u p e r v i s e dl e a r n i n gi nq u e s t ) 分类方法【3 3 】，它针对数据量远大于 内存容量的情况采用了类表和属性表等数据结构，利用换入换出策略处理大数据量。 同时s l i q 算法还解决了数据集的一次扫描问题，另外在建树阶段，对连续属性采取 预排序技术与广度优先相结合的策略生成树，对离散属性采取快速的求子集算法确定 划分条件。但由于s l i q 的类表必须驻留在内存中，所以可以处理的数据量仍然有限。 1 9 9 6 年，s h a f e r 和a g r a w a l 等人提出了可伸缩并行归纳决策树( s p r i n t ：s c a l a b l e p a r a u e l i z a b l ei n d u c t i o no f d e c i s i o n1 r e e ) 分类方法【3 4 。，继s l i q 分类方法后提出的又一 种规模可变的、支持并行计算的分类方法。s p r i n t 分类方法通过属性表和类直方图 两种数据结构对s l i q 能够处理的数据容量进行了进一步的扩充，可以真正处理超大 型数据库的数据，它最大的优点是可以避免内存空间的限制，利用多个并行处理器构 造一个稳定的、分类准确率很高的决策树，具有很好的可伸缩性与扩容性，但该算法 因使用属性列表，使得存储代价大大增加。1 9 9 8 年，r a s t o g i 和s h i m 提出了一种将 建树和修剪相结合( p u b l i c ：ad e c i s i o nt r e et h a ti n t e g r a t e sb u i l d i n ga n dp r t m i n g ) 分类 算法【3 5 】，该算法提出了节点代价的目标函数，利用该函数计算节点代价的估计，估计 该节点在将来调整阶段是否被删除。如果该节点将被删除，则不对该节点进行扩张， 否则，扩展该节点。从而将建树和修剪阶段结合成为一个阶段，而不是依次执行这两 个阶段，提高了决策树的执行效率。g e h r k e 和r a m a k r i s h n a n 等人提出了雨林 ( r a i n f o r e s t ) 分类算、法【3 6 】，它是一种针对大规模数据集，快速构造决策树的分类框架， 提出了a v c 表( a t t r i b u t e v a l u e ，c l a s sl a b e l ，属性值和类标签) 指示每个属性的分布。 近年来，随着理论的不断发展，以及新问题的提出，决策树学习中的研究热点也 决策树算法研究及在查询接口发现中的应用 第二章理论基础 开始转变【3 7 4 0 1 。专家研究的方向开始更加细化：如多值多标签问题、缺失属性值的处 理问题、决策树分支合并问题以及与其它分类技术结合等问题，在这些方面也都取得 了一定的成果。 2 3 决策树理论基础 决策树方法是数据挖掘中很有效的方法。决策树是用样本的属性作为节点，用属 性的取值作为分支的树型结构。它是利用信息论原理对大量样本的属性进行分析和归 纳而产生的。决策树的根节点是所有样本中信息量最大的属性。树的中间节点是以该 节点为根的子树所包含的样本子集中信息量最大的属性。决策树的叶节点是样本的类 别值。决策树用于对新样本的分类，即通过决策树对新样本属性值的测试，从树的根 节点开始，按照样本属性的取值，逐渐沿着决策树向下，直到树的叶节点，该叶节点 表示的类别就是新样本的类别。决策树构建算法的一般性描述如算法2 1 所示。 算法2 1决策树构建算法 算法：决策树构建算法g e n e r a t e _ d e c i s i o n _ t r e e ( d a ，c ) 输入：训练数据集d ，测试属性集a ，类别属性c 输出：一棵决策树 1 ) 创建树的根节点r o o t 2 ) 如果所有样本属于同一类别c ，则该节点是d t + 节点，标记为c ，返回r o o t 3 ) 如果测试属性集a 为空，则返回单节点r o o t 4 ) 否则计算测试属性集a 中的每一个测试属性的分类能力。 5 ) 选择分类能力最人的测试属性a ，作为划分属性。 幻r o o t - - - a 把属性a 作为根节点的决策属性 b ) 对于属性a 的每一个可能取值创建一个新的分支b r a n c h ( a ，) ，该分支的样本集合 中属性a 的值为a 。 6 ) 对于每个分支节点b r a n c h ( a ，) ： a ) 如果所有的样本都属于同一类别，则为该分支创建该类别的时节点 b ) 如果样本集为空，则为该分支创建样本集中最普遍的类别的叶节点 c ) 否则，递归调用g e n e r a t ed e c i s i o n _ t r e e ( d ，a 一 a ，c ) 7 ) 结束 9 第二章理论摹础决策树算法研究及在查询接i s l 发现中的应用 算法递归操作的终止条件是： ( 1 ) 给定节点的所有样本属于同一类( 步骤2 ) 。 ( 2 ) 没有剩余的属性可以进行下一步的划分( 步骤3 ) 。 ( 3 ) 没有样本满足属性a 的值为a ，( 步骤6 - b ) 。 为了能够对样本进行最优的划分，需要寻找某种函数来衡量哪些属性的分类能力 最强，这是决策树分类算法中的一个核心问题。在决策树中经典的i d 3 算法中引入了 一个称为“信息增益 ( i n f o r m a t i o ng a i n ) 的概念，用来衡量给定的属性划分样本的能 力。 1 9 4 8 年，香农( c e s h a n n o n ) 提出了信息论。假设s 是训练样本集，它包含n 个类 别的样本，这些类别分别用c l ，c 2 ，g 表示。信息论中对于信息量( i n f o r m a t i o n ) 并1 熵 ( e n t r o p y ) 的定义为： i n f o r m a t i o n = 一l 0 9 2 只 ( 2 1 ) e n t r o p y ( s ) = 一p ，l o g 2p f ( 2 2 ) 其中，p ，是表示类c ，的概率。熵实际上是系统信息量的加权平均值，也就是系统 的平均信息量。为了更好的理解熵的概念，我们来举例说明：假设s 是是一个关于某 布尔概念的有5 个样例的集合，它包括2 个正例和3 个反例，我们采用记号【2 + ，3 】 来概括这样的数据样例，那么s 相对于这个布尔分类的熵为： e n t r o p y ( 2 + ，3 - ) = - ( 2 5 ) i 0 9 2 ( 2 5 ) 一( 3 5 ) 1 0 9 2 ( 3 5 ) = o 9 71 ( 2 3 ) 如果s 的所有成员都属于一类，那么s 的熵为0 ；当集合中正反例的数量相等时， 熵为1 。如果集合中正反例的数量不等时，熵介于0 和1 之间。可见，样本的概率分 布越均衡，它的信息量( 熵) 越大，样本集的混杂程度也越高。因此，熵可以作为训 练样本集的不纯度( i m p u r i t y ) m - - 个度量。熵越大，不纯度越高；反之越低。决策树 的划分原则就是使划分后的样本的子集越纯越好，即它们的熵越小越好。 有了熵作为衡量训练样本集合纯度的标准，就可以定义属性分类训练数据的能力 的度量标准，这个标准就是信息增益。一个属性的信息增益就是由于使用这个属性分 割样本导致的期望熵的降低。 设属性a 将训练样本集s 划分为n 份，根据属性彳划分出的子集的熵或期望信息 为： 1 0 g a i n ( s ，彳) 是指因为知道属性彳的值后导致的熵的期望值减少。g a i n ( s ，么) 越大说 明属性彳提供的分类信息越多，分类能力越强。由于熵越小划分后的样本子集的纯度 越高，根据信息增益的定义，信息增益越大，熵的减少值越大，节点的纯度越高。 i d 3 算法计算样本的每个属性，选择信息增益最大的属性作为测试属性。信息增 益越大，说明该属性对分类提供的信息越多，分类能力越强。 i d 3 算法的主要优点是：( 1 ) i d 3 算法中的假设空间是一个完整的空间，包含所 有的决策树，不存在无解的情况；( 2 ) 全盘使用训练样本集，可以利用所有训练样本 的统计性质进行决策，对噪音数据有很好的健壮性；( 3 ) 可以很容易的转化为易于理 解的分类规则，能够直观、清晰的表达逻辑要求；( 4 ) 可以处理连续和离散字段，相 对而言，更擅长处理离散数据；( 5 ) 计算的数据量相对来说不是很大，计算速度相对 较快。但i d 3 算法也存在很多不足之处：( 1 ) i d 3 算法存在多值偏向问题，往往偏向 于选择取值较多的属性，然而取值较多的属性并不一定是最优的属性；( 2 ) 可能收敛 于局部最优解而丢失全局最优解；( 3 ) 连续性的字段比较难预测，当类别过多时，错 误增加的比较快；( 4 ) 在构造树