（应用数学专业论文）基于决策树的属性约简方法研究.pdf

摘要 摘要 分类是数据挖掘的项核心任务，而分类的依据常常是所关心的问题的某些方 面的特征( 通常称之为属性) 。由于数据库中的数据往往与给定的属性集中的某些属性 的状态( 即取值) 无关或关联不大，直接采用给定的属性集来挖掘知识将增大数据挖掘 的难度，特别，对于巨型数据库而言，可能会导致相关数据挖掘算法的失效，因而， 如何精练数据挖掘的属性集( 称之为属性约简) ，是数据挖掘的一个关键环节。 目前的属性约简算法大都是以波兰数学家z p a w l a k 于1 9 8 2 年提出的粗糙集作为 理论基础，其主要思想就是在保持分类能力不变的前提下，通过约简，导出问题的 决策或分类规则。虽然这些算法均具有良好的理论基础，但它们的空间复杂度和时 间复杂度都较高，不能有效地处理大型数据库的属性约简问题。 决策树算法是目前机器学习领域中最为成熟的内容，其优点为：1 、) 决策树方法 结构简单，无需了解很多的背景知识；2 ) 决策树模型效率较高，对训练样本集数据 量较大的情况尤为适合；3 ) 决策树算法的计算量相对较小；4 ) 决策树方法具有较高 的分类精确度。 因此，本文结合决策树算法操作简单、分类速度快的特点，通过将知识库抽象 为规则族及规则族之间的相似性比较，建立了一种基于决策树的属性约简方法( 简记 为b d r e d ) ，具体工作如下：1 ) 建立了规则的形式化描述模式；2 ) 从结构化的角 度讨论了规则族之间的相似性度量的构建问题；3 ) 给出了b d r e d 的具体实施原则； 4 ) 结合具体实例分析了b d r e d 的特征和性能。结果表明，b d r e d 具有良好的结 构特征和较强的可操作性，可以有效地实现不同决策理念下的属性约简，适合不同 类型的大规模数据库的属性约简。 最后，我们提出了改进的i d 3 算法( c i d 3 算法) ，本文针对归纳学习所依赖的示 例存在缺失值的情况，先对数据库做一个初步的可信度计算，然后结合i d 3 算法作 出决策树，该算法生成的规则更精确，而且还能根据具体需要得到合适的规则。理 论分析和试验仿真都表明，该方法不仅具有较强的可操作性，而且能够提高所得知 识的精确度。 关键词数据挖掘；属性约简；决策树；粗糙集；c i d 3 算法；规则；信息增益；节 点纯度；可信度；相似度量 河北科技大学硕士学位论文 j i = | 自；目i | = = = 自j = = = = = = = = = = = = = 自= = 目= = = = = = = = = = = = ；= = = = = = = = = = = = = = = = = = = ：； = = = ：= a b s t r a c t c l a s s i f i c a t i o ni sac o r et a s ko fd a t am i n i n g ，a n dt h eb a s i so fw h i c hi st h ec h a r a c t e r i s t i c s o fs o m ec o n c e m s ( u s u a l l yc a l l e d a t t r i b u t e s ) a st h ed a t ai n t h ed a t a b a s ei s u s u a l l y u n r e l a t e dt oo rh a v es m a l lr e l a t i o nw i t hs t a t e s ( t h a ti s ，v a l u e ) o fs o m ea t t r i b u t e so fa g i v e n a t t r i b u t es e t ，u s i n gt h eg i v e na t t r i b u t es e td i r e c t l yt om i n ek n o w l e d g ew i l li n c r e a s et h e d i f f i c u l t yo fd a t am i m n g i np a r t i c u l a r , f o rt h eh u g ed a t a b a s e ，i tm a yr e s u l ti nf a i l u r et o d a t am i n i n ga l g o r i t h m t h e r e f o r e ，h o wt o s i m p l i f ya t t r i b u t es e t ( k n o w na st h ea t t r i b u t e r e d u c t i o n ) i sak e yl i n ko fd a t am i n i n g a tp r e s e n t ，t h e o r e t i c a lf o u n d a t i o no ft h ea t t r i b u t er e d u c t i o na l g o r i t h mi sb a s e dm o s t l y o nr o u g hs e tb yap o l i s hm a t h e m a t i c i a nn a m e dz p a w l a ki n19 8 2 u n d e rt h ep r e m i s eo f k e e p i n gt h ec o n s t a n ta b i l i t yo fc a t e g o r i z e ，t h em a i ni d e ao ft h et h e o r yi st oo u t p u tt h e d e c i s i o no ft h ep r o b l e mo rt h ec a t e g o r i z e dr u l e t h r o u g ht h er e d u c t i o no fk n o w l e d g e a l t h o u g ha l lt h e s ea l g o r i t h m sh a v eg o o dt h e o r e t i c a lb a s e ，t h e yh a v eac o m m o nw e a k n e s s ， t h a ti s ，f o rt h eh u g ed a t a b a s e ，t h ec o m p l e x i t yo f s p a c ea n dt i m ei sh i g h e r a tp r e s e n t ，d e c i s i o nt r e ea l g o r i t h mi st h em o s ts o p h i s t i c a t e dc o n t e n t si nt h ef i e l do f m a c h i n el e a r n i n g ，i t sa d v a n t a g e sa r e ：1 ) b e c a u s ed e c i s i o nt r e em e t h o dh a ss i m p l es t r u c t u r e ， w ed o e sn o tn e e dk n o wm u c hb a c k g r o u n dk n o w l e d g e ；2 、d e c i s i o nt r e em o d e lh a sh i g h e r e f f i c i e n c y , a n di ti ss u i t a b l ef o rt r a i ns a m p l e ss e tw i t hl a r g e s i z ed a t a ；3 ) t h ec o m p u t a t i o n o fd e c i s i o nt r e e a l g o r i t h m i s r e l a t i v e l ys m a l l ；4 ) d e c i s i o nt r e em e t h o dh a sh i g h e r c l a s s i f i c a t i o na c c u r a c y b a s e do nt h ea b o v ea n a l y s i s ，i nt h i sp a p e r , b yc o m b i n i n gt h ef e a t u r e so fe a s yo p e r a t i o n a n ds w i f tc l a s s i f i c a t i o no fd e c i s i o nt r e ea n df o r m a l i z e dd e s c r i p t i o no ft h ek n o w l e d g eb a s e ， w ee s t a b l i s h e sak i n do fa t t r i b u t er e d u c t i o nm e t h o d ( d e n o t e di t b yb d r e df o rs h o r t 、 b a s e do nd e c i s i o nt r e e a n do u rm a i nc o n t r i b u t i o n sa r ea sf o l l o w s ：l 、w ee s t a b l i s ha f o r m a l i z e dd e s c r i p t i o nm o d e lo ft h er u l e s ；2 ) w ed i s c u s st h es i m i l a r i t ym e a s u r eb e t w e e n t h er u l e sf a m i l i e sf r o mt h es t r u c t u r a l a s p e c t ；3 ) w eg i v et h ec o n c r e t ei m p l e m e n t i n g p r i n c i p l eo fb d r e d ；4 ) w ea n a l y z et h ep e r f o r m a n c eo fb d - r e dt h r o u g hac o n c r e t e e x a m p l e l a s t e l y , i nt h ei n d u c t i v el e a r n i n g ，i fe x a m p l eb a n kh a sn o i s e ，i ti sh a r dt oo b t a i n d e c i s i o nt r e e sw i t hh i g hp r e c i s i o n ，t h a ti s ，i ti sh a r dt oo b t a i nk n o w l e d g ew i t hh i g h c r e d i b i l i t y s o ，t h i sp a p e rp u t sf o r w a r dc i d 3a l g o r i t h m ，b yw h i c hw ec o m p u t ec o n f i d e n c e l e v e lo fe x a m p l eb a n kf i r s t l y , a n df u r t h e rg e tak i n do fd e c i s i o nt r e eo nt h eb a s i so f i i a b s t r a c t t r a d i t i o n a li d 3a n dt h ec r e d i b i l i t yo b t a i n e d a l lt h et h e o r ya n a l y s i sa n ds i m u l a t i o ni n d i c a t e t h a tt h i sm e t h o dp o s s e si n t e r e s t i n gf e a t u r eo fs t r o n go p e r a b i l i t y , a n di ta l s oc a ni m p r o v e t h er e l i a b i l i t yo fk n o w l e d g eo b t a i n e d k e yw o r d s d a t am i n i n g ；a t t r i b u t er e d u c t i o n ；d e c i s i o nt r e e ；r o u g hs e t ；c - i d 3 a l g o r i t h m ；r u l e s ；i n f o r m a t i o ng a i n ；n o d e sp u r i t y ；c r e d i b i l i t y ；s i m i l a r i t y i i i 河北科技大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工 作所取得的成果。对本文的研究做出重要贡献的个人和集体，均己在文中以明确方 式标明。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发 表或撰写过的作品或成果。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：耋许 叫年多月舻 指导教师签名： 尝嘲 。蛔f 年月撕 河北科技大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权河北科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 口保密，在一年解密后适用本授权书。 本学位论文属于 哜保密。 ( 请在以上方框内打“”) 一繇杰青 钞印年岁月啦 i 指导教师签名： 锄硝 2 扩f 年岁月2 铂 第1 章绪论 第1 章绪论 1 1 背景知识 1 1 1 数据挖掘的社会需求 随着信息技术的发展，采用信息化手段来管理、监测和记录生产活动是社会发 展的必然趋势，各行各业在不同的层面上积累了大量的数据资料。这些数据不仅可 以理解为过去的活动记录，而且可以认为是某种试验结果的积累，当其积累到一定 程度时，必然会反映出规律性的东西，因此，堆积如山的数据无异于一个巨大的宝 库。如何发现隐藏在数据中的知识( 简称为数据挖掘【1 3 1 ) ，并将之运用到社会活动中， 是当今人工智能领域的一个重要研究内容。 然而数据库中的数据往往含有大量冗余或不必要的属性，严重降低了数据挖掘 算法的时间效率和算法质量，因此删除数据的冗余属性或无关属性( 属性约简) 是数据 预处理过程中的主要任务。所谓属性约简，就是在保持知识库的分类能力或决策能 力不变的条件下，删除其中不相关或不重要的知识【1 2 1 。通过属性约简，剔除了决策 表中不必要的属性，在不丢失决策表基本信息的前提下，简化了知识的表示，进而 做出正确而简洁的决策，提高决策速度。 1 1 2 数据挖掘的定义 数据挖掘m ，d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随 机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在的有用信息和知 识的过程。与数据挖掘意义相近的术语有：从数据库中发现知识( k d d ) 、模式分析、 商业智能、数据融合、决策支持和信息收割等。现在普遍采用的术语主要是数据挖 掘和数据库中的知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 。 从数据库中发现知识( k d d ) h 1 一词首次出现是在1 9 8 9 年举行的第十一届国际联 合人工智能学术会议上。到目前为止，由美国人工智能协会主办的k d d 国际研讨会 已经召开了8 次，规模由原来的专题讨论会发展到现在大规模的国际学术大会，研 究重点也逐渐从发现方法转向了系统应用方面，注重多种发现策略和技术的集成， 以及多种学科之间的相互渗透。1 9 9 9 年，亚太地区在北京召开的第三届p a k d d 会 议收到1 5 8 篇论文，空前热烈。i e e e 的k n o w l e d g ea n dd a t ae n g i n e e r i n g 会刊率先在 1 9 9 3 年出版了k d d 技术专刊。并行计算、计算机网络和信息工程等其他领域的国 际学会、学刊也把数据挖掘和知识发现列为专题和专刊讨论，甚至到了脍炙人口的 程度。 河北科技大学硕士学位论文 1 1 3 数据挖掘的研究内容和本质 随着d m k d 研究逐步走向深入，数据挖掘和知识发现的研究已经形成了三根强 大的技术支柱：数据库、人工智能和数理统计。因此，k d d 大会程序委员会曾经由 这三个学科的权威人物同时来任主席。目前d m k d 的主要研究内容包括基础理论、 发现算法、数据仓库、可视化技术、定性定量互换模型、知识表示方法、发现知识 的维护和再利用、半结构化和非结构化数据中的知识发现以及网上数据挖掘等。 数据挖掘所发现的知识最常见的有以下四类： 广义知识，指类别特征的概括性描述知识。根据数据的微观特性发现其表征的、 带有普遍性的、较高层次概念的、中观和宏观的知识，反映同类事物共同性质，是 对数据的概括、精炼和抽象。 关联知识，反映事物之间依赖或关联关系的知识，最为著名的关联规则发现方 法是r a g r a w a l 提出的a p r i o r i 算法1 5 j 。 分类知识，它反映同类事物共同性质的特征型知识和不同事物之间的差异型特 征知识。最为典型的分类方法是基于决策树的分类方法。数据分类还有统计、粗糙 集( r o u g hs e t ) 等方法。最近也有人研究使用神经网络方法在数据库中进行分类和规则 提取。 预测型知识，它根据时间序列型数据，由历史的和当前的数据去推测未来的数 据，也可以认为是以时间为关键属性的关联知识。目前，时间序列预测方法有经典 的统计方法、神经网络和机器学习等。 此外，还可以发现其他类型的知识，如偏差型知识，它是对差异和极端特例的 描述，揭示事物偏离常规的异常现象。 1 1 4 数据挖掘的功能 数据挖掘的目标是从数据库中发现隐含的、有意义的知识，主要有五类功能： 自动预测趋势和行为，数据挖掘自动在大型数据库中进行分类和预测，寻找预 测性信息，自动地提出描述重要数据类的模型或预测未来的数据趋势。 关联分析，是指如果两个或多个事物之间存在一定的关联关系，那么其中一个 事物就能通过其他事物进行预测，它的目的是为了挖掘隐藏在数据间的相互关系， 包括简单关联、时序关联和因果关联等。 聚类，是根据数据的不同特征，将其划分为不同的数据类。它的目的是使得属 于同一类别的个体之间的距离尽可能的小，而不同类别上的个体间的距离尽可能的 大。聚类方法包括统计方法、机器学习方法、神经网络方法和面向数据库的方法。 概念描述，就是对某类对象的内涵进行描述，并概括这类对象的有关特征。概 念描述分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者描述不 2 第1 章绪论 同类对象之间的区别，如决策树方法、遗传算法等。 偏差分析，是探测数据现状、历史纪录或标准之间的显著变化和偏离，偏差包 括很大一类潜在的有趣知识。如观测结果与期望的偏离、分类中的反常示例、模式 的例外等。偏差分析的一个重要特征就是它可以有效地过滤大量不感兴趣的模式。 1 1 5 数据挖掘常用技术 人工神经网络【6 】：它模拟人脑神经元结构，以m p 模型和h e b b 学习规则为基础， 建立了三大类神经网络模型：前馈式网络、反馈式网络和自组织网络。 决策树【7 】：利用信息论中的互信息( 信息增益) 寻找出数据集中具有最大信息的字 段，建立决策树中的每一个节点，再根据字段的不同取值建立树分支的过程，即建 立决策树。 遗传算法【s 】：基于进化理论，并采用遗传结合、遗传变异、以及自然选择等设计 方法的优化技术。 粗糙集方法【9 】：粗糙集理论是八十年代初z p a w l a k 针对边界域思想提出的，基 于给定训练数据内部的等价类的建立，用一对上下近似集合来逼近数据库中的精确 概念。该理论是一种处理不确定性、不精确和模糊知识的数学工具【1 , 1 0 , 1 1 】。 近邻算法【1 2 1 ：将数据集合中每一个记录进行分类的方法。 规则推导【1 3 j ：从统计意义上对数据中的“如果那么 规则进行寻找和推导。 1 1 6 数据挖掘的过程 数据挖掘过程【1 4 】从宏观上看，主要由数据准备、数据挖掘阶段和结果解释及评 价三部分组成。 数据准备又分为三个子步骤：数据选取、数据预处理和数据变换。数据选取的 目的是确定发现任务的操作对象，即目标数据。它是根据用户的需要从原始数据库 中抽取的一组数据。数据预处理一般包括消除噪声、推导计算缺值数据、消除重复 记录、完成数据类型转换等。数据变换的主要目的是消减数据维数或降维，即从初 始特征中找出真正有用的特征以减少数据开采时要考虑的特征或变量个数。 数据挖掘算法执行阶段首先根据问题的定义明确挖掘的任务或目的，如分类、 聚类、关联规则发现或序列模式发现等。然后根据数据库的特点和用户的要求选择 实现算法。 结果解释和评价：解释并评估结果其使用的分析方法一般应视数据挖掘操作而 定，通常会用到可视化技术。 1 2 决策树的特点和研究状况 决策树起源于概念学习系统c l s t l 5 ( c o n c e p tl e a r n i n gs y s t e m ) ，最早由e b h u n t 3 河北科技大学硕士学位论文 等人于1 9 6 6 年提出，并首次用决策树进行概念学习，后来的许多决策树学习算法都 可以看作是c l s 算法的改进与更新。c l s 的主要思想是从一个空的决策树出发，通 过添加新的判定节点来完善原有的决策树，直到新的决策树能够正确地将训练示例 分类为止。 2 0 世纪6 0 年代诞生的决策树技术曾在相当长的时间内是一个非常流行的人工智 能技术，是构建人工智能系统的主要方法之一。然而随着人工智能遭遇低潮，这一 技术逐渐不为人所注意。近十几年以来，伴随着数据挖掘技术的兴起，决策树作为 数据挖掘技术中种分类问题的解决方法再一次受到重视，并且被广泛的研究。 1 9 8 6 年，q u i n l a n 在c l s 算法的基础上以信息增益作为启发策略，提出了著名 的i d 3 1 6 】算法。随后，在i d 3 算法的基础上，又演化出1 1 3 3 的增量版本1 1 3 4 1 7 】和1 1 ) 5 1 1 8 】 等。1 9 9 3 年，q u i n l a n 提出了改进决策树归纳包( c 4 5 ) ，c 4 5 是一个能处理连续属 性的算法。著名的决策树方法还有c a r t 2 0 i 、s l i q 2 1 1 、s p r i n t l 2 2 1 、r a i n f o r e s t 2 3 1 和p u b l i c 2 4 】等。 决策树算法是目前机器学习领域中最为成熟的内容，其优点为：决策树方法结 构简单，无需了解很多的背景知识；决策树模型效率较高，对训练样本集数据量较 大的情况尤为适合；决策树算法的计算量相对较小：决策树擅长处理非数值型数据， 与神经网络只能处理数值型数据相比起来，免去了很多数据预处理工作；决策树方 法具有较高的分类精确度。据统计，目前决策树算法利用率高达1 9 【2 5 1 。 决策树学习方法是目前分类算法中重点研究的方向，研究成果较多，并且已经 有了广泛的应用和许多成熟的系统，如语音识别，医疗诊断，客户关系管理，模式 识别，专家系统等。决策树的各种算法都不是万能的，他们都有各自的优缺点，在 实际工作中，必须根据数据类型的特点及数据集的大小，选择合适的算法。 决策树方法尽管一直都受到广泛关注，但还有许多方面需要进一步研究。例如， 扩充决策树属性的取值范围及改进选择分离属性的选择：扩充决策树，形成决策图； 提高决策树的构造效率削减数据库遍历次数，减少f o 操作；优化决策树，简化决策 树输出：将遗传算法、神经网络技术以及粗糙集理论引入决策树算法；处理复杂类 型的数据。我们面临的数据集是多样化的，因此，除了能处理结构化的数据外，对 半结构化、结构化以及异种数据库进行挖掘也对决策树提出了挑战。 1 3 论文背景及研究内容 由上面的论述可知，目前数据挖掘研究越来越受到学者的重视，而决策树方法 作为一种数据挖掘工具有着它不可替代的优点，受到研究学者的广泛关注。因此研 究决策树方法有着极其重要的理论意义和现实意义。 分类是数据挖掘的一项核心任务，而分类的依据常常是所关心的问题的某些方 4 第1 章绪论 面的特征( 通常称之为属性) 。由于数据库中的数据往往与给定的属性集中的某些属性 的状态( 即取值) 无关或关联不大，直接采用给定的属性集来挖掘知识将增大数据挖掘 的难度，特别，对于巨型数据库而言，可能会导致相关数据挖掘算法的失效，因而， 如何精练数据挖掘的属性集( 称之为属性约简) ，是数据挖掘的一个关键环节。 针对该问题，众多学者进行了许多有益的探讨，取得了许多重要的理论和应用 成果，比如：文献 2 6 1 给出了基于数据分析的属性约简算法；文献 2 7 - 2 9 以属性重要 性为启发式策略，讨论了基于正区域的属性约简算法；文献 3 0 】以遗传算法为启发式 策略，提出了基于遗传算法的属性约简方法；文献 3 1 3 6 以差别矩阵为启发式策略， 给出了基于差别矩阵的属性约简算法；文献 3 7 3 9 】以信息熵作为启发式策略，给出 了基于信息熵的属性约简方法。虽然这些算法均具有良好的理论基础，但它们的空 间复杂度和时间复杂度都较高，不能有效地处理大型数据库的属性约简问题。 基于上面的分析，本文结合决策树算法操作简单、分类速度快的特点，通过将 知识库抽象为规则族及规则族之间的相似性比较，建立了一种基于决策树的属性约 简方法( 简记为b d r e d ) ，具体工作如下：1 ) 建立了规则的形式化描述模式；2 ) 从 结构化的角度讨论了规则族之间的相似性度量的构建问题；3 ) 给出了b d r e d 的具 体实施原则；4 ) 结合具体实例分析了b d r e d 的特征和性能。 本文的研究受到了国家自然科学基金( 7 0 6 7 1 0 3 4 ) 河北省博士基金 ( 0 5 5 4 7 0 0 4 d 2 ，b 2 0 0 4 5 0 9 ) 录1 河北省自然科学基金( f 2 0 0 6 0 0 0 3 4 6 ) 的资助。 1 4 论文的组织与结构 本文结合决策树算法操作简单、分类速度快的特点，在规范知识的形式化描述 的基础上，利用知识库之间的相似度量，提出了一种基于决策树的属性约简方法( 简 记为b d r e d ) 。并且讨论了b d r e d 的基本特征，最后结合实例分析了b d r e d 的 性能，本文的组织如下： 第1 章：绪论。主要概述了数据挖掘的研究现状和特点，决策树的研究现状和 特点，论文的研究背景和工作内容。 第2 章：决策树基本算法。本章详细介绍了决策树的几个非常典型的算法，如： i d 3 算法，c 4 5 算法和c a r t 算法。并且概述了其它决策树分类算法，分析了他们 的优缺点。 第3 章：基于决策树的属性约简方法。本章通过知识的规则化描述以及规则族 之间的相似性比较，建立了一种基于决策树的属性约简方法( 简记为b d r e d ) ，并且 讨论了规则族之间的相似性度量的可释化构建问题，给出了b d r e d 的具体实施策 略，并结合实例分析了b d r e d 的性能。结果表明，b d r e d 具有良好的结构特征 和较强的可操作性，可以有效地实现不同决策理念下的属性约简，适合不同类型的 5 河北科技大学硕士学位论文 大规模数据库的属性约简。 第4 章：基于可信度的决策树研究与应用。本文针对归纳学习所依赖的示例存 在缺失值的情况，先对数据库做一个初步的可信度计算，然后结合i d 3 算法作出决 策树，该算法生成的规则更精确，而且还能根据具体需要得到合适的规则。理论分 析和试验仿真都表明，该方法不仅具有较强的可操作性，而且能够提高所得知识的 精确度。 6 第2 章决策树基本算法概述 第2 章决策树基本算法概述 2 1归纳分类 分类在数据挖掘中是一项非常重要的任务，目前在商业上应用最多。分类可描 述为：给定一训练样本集n 丁中的每一个示例都由若干个属性描述。当属性的值域 为连续型时，该属性称为连续型属性，否则称为离散型属性。令c = c 1 ，c ：，c 。) 是条件属性集，c i 的取值范围为y ( e ) = q 。，c j ：，) ，f = 1 ，2 ，s ；d 表示决策属 性，d 的取值范围为以d ) = d ，d ：，d 。 ，那么，丁就隐含地确定了一个从条件属性 集c 到决策属性d 的映射函数h ：f ( c ) 一d 。分类的目的就是学会一个分类函数或 分类模型( 也常常称作分类器) ，该模型能把数据库中的数据项映射到给定类别中的某 一个。 分类器的构造方法有统计方法、机器学习方法、神经网络方法等。统计方法包 括贝叶斯法和非参数法，对应的知识表示为判别函数和原型事例。机器学习方法包 括决策树法和规则归纳法，前者对应的表示为决策树或判别树，后者则一般为产生 式规则。神经网络方法主要是b p 算法，它的模型表示为前向反馈神经网络模型， b p 算法本质上是一种非线性判别函数。另外，最近又兴起了一种新的方法：粗糙集 ( r o u g hs e t ) ，其知识表示为产生式规则。 分类器评价的比较尺度有三种：预测准确度，预测准确度是用得最多的一种比 较尺度，特别是对于预测型分类任务，目前公认的方法是1 0 折分层交叉验证法；计 算复杂度，计算复杂度依赖于具体的实现细节和硬件环境，在数据挖掘中，由于操 作对象是巨量的数据库，因此空间和时间的复杂度问题将是非常重要的一个环节； 模型描述的简洁度，对于描述型的分类任务，模型描述越简洁越受欢迎，例如，采 用规则表示的分类器构造法就更有用，而神经网络方法产生的结果就难以理解。 2 2 决策树学习 决策树分类算法是以示例为基础的归纳学习算法。它从一组无次序、无规则的 元组中推理出决策树表示形式的分类规则。它采用自顶向下的递归方式，在决策树 的内部节点进行属性值的比较，并根据不同的属性值从该节点向下分支，叶节点就 是要学习划分的类。所以从根到叶节点的一条路径就对应着一条合取规则，整个决 策树就对应着一组析取表达式规则。基于决策树的学习算法的一个最大的优点就是 它在学习过程中不需要使用者了解很多背景知识，只要训练例子能够用“属性结论” 式的方式表达出来，就能使用该算法来学习。 7 河北科技大学硕士学位论文 一棵决策树的内部节点是属性或属性的集合，叶节点是所要学习划分的类，下 面将内节点的属性称为扩展属性。经过训练样本集的训练产生一棵决策树，决策树 可以根据属性的取值对一个未知示例集进行分类。使用决策树对示例进行分类的时 候，由树根开始对该对象的属性逐渐测试其值，并且顺着分支向下走，直至到达某 个叶节点，此叶节点代表的类即为该对象所处的类。 例如，图2 1 所示即为一棵决策树，它将整个示例空间分为三类，当属性么的 取值为口2 ，属性b 的取值为b 2 ，属性c 的取值为c l 时，它属于第一类。 图2 1 一棵决策树示例 f i g 2 - 1 a ne x a m p l eo f d e c i s i o nt r e e 根据决策树的各种不同属性，有以下几种各种不同的决策树： 1 ) 决策树的内节点的扩展属性可能是单变量的，即每个内节点只包含一个属性。 也可能是多变量的，即存在包含多个属性的的内节点。 2 1 根据扩展属性的不同属性值的个数，可能使得每个内节点有两个或多个分支。 如果每个内节点只有两个分支，则称之为二叉决策树。 3 ) 每个属性可能是值类型，也可能是枚举类型( - - 叉决策树既可以被看作是前 者，也可以被看作是后者) 。 4 1 分类结果既可能是两类，也有可能是多类，如果二叉决策树的结果只能有两 类，则称之为布尔决策树。 由于本文的篇幅所限与侧重点的不同，本章只介绍传统的决策树学习算法，即 h u n t 所提出的的c l s 学习算法，q u i n l a n 的i d 3 算法和c 4 5 算法等。 2 3c l s 学习算法 c l s 学习算法是1 9 6 6 年由h u n t 等人提出的，它是早期的决策树学习算法，后 来的许多决策树学习算法都可以看作是c l s 算法的改进与更新。c l s 的主要思想是 8 第2 章决策树基本算法概述 从一个空的决策树出发，通过添加新的判定节点来完善原有的决策树，直到新的决 策树能够正确地将训练示例分类为止。 算法2 1c l s 学习算法 步骤1 ：令决策树t 的初始状态只含有个树根( r ，c ) ，其中丁是全体训练示例 的样本集，c 是全体扩展属性的集合； 步骤2 ：若t 的全体叶节点( r ，c ) 都有如下状态：或者，中的示例都属于同一 个类，或者c 为空，则停止执行学习算法，学习的结果为t ； 步骤3 ：否则，选取一个不具有步骤2 所述状态的叶节点( r ，c ) ； 步骤4 ：对于丁，按照一定规则选取扩展属性彳，设彳被的不同取值分为s 个不 相交的子集死n ，1 f s ，伸出j 个分叉，每个分叉代表4 的一个不同取值，从而 形成j 个新的叶节点( 乃n ，c 7 一 彳 ) ，1 f s ； 步骤5 ：转步骤2 。 在算法的步骤4 中，并未明确给出扩展属性的选取标准，所以c l s 有很大的改 进空间。 2 4 决策树i d 3 算法 2 4 1i d 3 算法 在算法2 1 中并未给出如何选取扩展属性a ，h u n t 曾经提出几种选择标准，但在 决策树学习的各种算法当中，最有影响力的是q u i n l a n 于1 9 7 9 年提出的以信息熵的 下降速度作为选取扩展属性的标准的i d 3 算法【4 0 1 。信息熵的下降也就是信息不确定 性的下降。 定义2 1 设训练样本集为f ，类属性d 有m 个取值，f = 互，乏，乙) 是按照 类属性d 的取值所形成的划分，izi 表示z 中元素个数，此时决策树对划分r 的不确 定程度为 配耻一2 。斜l 0 9 2 斜 ( 2 1 ) 称式( 2 1 ) 为t 关于r 的分类信息熵。以后在无混淆的情况下，将e ( t ，f ) 简记为e ( t ) 。 对于属性a ，如果巧n ，巧孙，z 5 为按照彳的属性值所形成的t 的划分，则属性彳 对于分类的信息熵为 e ( t a ) = 二。箐xe ( 叩，r n 掣) ( 2 - 2 ) 决策树学习过程就是使得决策树对划分的不确定程度逐渐减小的过程。对于属 性么，称 9 河北科技大学硕士学位论文 g ( t ，f ，么) = e ( d e ( 引4 )( 2 - 3 ) 为属性彳关于i 的分类信息增益。以后在无混淆的情况下，将g ( t ，f ，a ) 简记为 g ( t ，4 ) 。 式( 2 2 ) 值越小，式( 2 3 ) 值的值越大，这说明选择的扩展属性彳对于分类提供的 信息越大，选择么之后对于分类的不确定程度越小。q u i n l a n 的i d 3 算法就是选择具 有最大信息增益的属性( 使得式( 2 3 ) 值最大的属性) 作为扩展属性，即选则使得式( 2 2 ) 值最小的属性。 利用式( 2 1 ) ( 2 - 2 ) ( 2 - 3 ) ，i d 3 算法的执行步骤如下： 步骤1 ：选取所有条件属性中分类信息增益最大的属性作为根节点。 步骤2 ：1 ) 如果节点上的每个分支中，所包含的示例具有相同的决策属性值， 则产生叶节点；2 ) 如果节点的每个分支所包含的示例具有基本相同的决策属性值， 即分类误差在允许的范围之内，则产生叶节点；3 ) 如果在节点及节点的上层，所有 条件属性都被使用过，则产生叶节点。 步骤3 ：否则，选取该节点即其上层未用过的具有最大信息增益的属性作为扩展 属性，并按照扩展属性的取值对当前节点进行分支( 划分) ；重复步骤2 和步骤3 ，直 至不能再进行分支为止。 步骤4 ：将产生的树转换成产生式规则。 2 4 2i d 3 算法应用举例 表2 1 给出了一个可能带有噪音的数据集合。它有四个属性：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 。它被分为两类：p 与n ，分别为正例和反例。我们 所要做的就是构造决策树将数据进行分类。 表2 1 训练样本集t t a b l e 2 - 1t r a i n i n gs a m p l es e tt 1 0 第2 章决策树基本算法概述 因为初始时刻属于p 类与n 类的实例个数均为1 2 个，所以初始时刻的熵值为： e c 丁，= 一罢。g 昙一罢- 。g 昙= 如果选取o u t l o o k 属性作为扩展属性，则根据式( 2 2 ) ，此时的信息熵为 e ( r o 砒嘲= 西9 ( 一扣万4 一三9 。g 丢( 一扣* t 。g 争 + 云c 一扣若l 0 9 6 ) = 0 5 5 2 8 同理，如果选取t e m p e r a t u r e 属性作为扩展属性，则有 e ( t t e m p e r a t u r e ) = 0 6 7 3 9 如果选取h u m i d i t y 属性作为扩展属性，则有 e ( t h u m i d i t y l = o 918 3 如果选取w i n d y 属性作为扩展属性，则有 根据式( 2 3 ) ，以上各属性的信息增益分别为： g ( t ，o u d o o k ) = e ( t ) - e ( t o u d o o k ) = 1 - 0 5 5 2 8 = 0 4 4 7 2 河北科技大学硕士学位论文 g ( 7 t e m p e r a t u e ) = 1 0 6 7 3 9 = 0 4 2 6 1 g ( t ，h u m i d i t y ) = 1 - 0 9 1 8 3 = o 0 8 1 7 g ( t ，w n a y ) = 1 - 1 = 0 由此可以看出g ( r ，o u t l o o k ) 最大，即有关o u t l o o k 的信息对于分类有最大的帮 助，提供最大的信息量，即e ( t o u d o o k ) 最小，所以应该选择o u t l o o k 作为根节点。 并且也可以看出g ( t ，w n a y ) = 0 ，有关w i n d y 的信息不能提供任何分类信息。选择 o u t l o o k 作为根节点之后，将样本集分为三个子集，生成三个叶节点，对每个叶节点 依次利用上面过程生成如图2 2 所示的决策树。 oo 图2 - 2 表2 - 2 所训练生成的决策树一1 j f i g 2 2 ad e c i s i o nt r e eg e n e r a t e db yt a b l e2 - 2 i d 3 算法具有理论清晰，方法简单，学习能力较强，分类速度快，适合于大规模 数据的处理的优点。但是i d 3 算法只能处理离散型的属性，计算中偏袒具有较多取 值的属性。对i d 3 算法的早期改进算法主要是i d 3 的增量版i d 4 、i d 5 及c 4 5 和 c h a i d 4 1 1 等算法。后期的改进算法主要有q u e s t t 4 2 1 和p u b l i c 。 2 5c 4 5 算法 c 4 5 算法是i d 3 算法的一种扩展，除了拥有i d 3 算法的功能外，c 4 5 增加的功 能如下：1 ) 用信息增益率的概念；2 ) 通过使用不同的修剪技术以避免树的不平衡； 3 ) 合并具有连续值的属性；4 ) 可以处理缺少属性值的训练样本：5 ) k 次迭代交叉验 证；6 ) 规则的产生。c 4 5 算法挑选具有最高信息增益率的属性作为扩展属性。 1 2 第2 章决策树基本算法概述 定义2 2 设f = 互，乙) 是有限样本集丁的一个划分，l = 巧n ，z 乱， ，z ) 是按属性彳的取值所形成的丁的划分，称 g r ( 丁，f ，彳) ：堡( 三：! ：丝2 ( 2 - 4 ) e ( t ，i - ) 为彳对丁进行划分的信息增益率。 利用式( 2 4 ) ，c 4 5 算法的执行步骤如下： 步骤1 ：对数据源进行数据预处理，将连续型的属性变量进行离散化处理形成决 策树的训练集( 如果没有连续取值的属性则忽略) ； 步骤2 ：计算每个属性的信息增益和信息增益率，选出根节点； 步骤3 ：根节点属性每一个可能的取值对应一个子集，对样本子集递归地执行以 上步骤2 过程，直到划分的每个子集中的观测数据在分类属性上取值都相同，生成 决策树。 步骤4 ：根据构造的决策树提取分类规则，对新的数据集进行分类。 2 5c a r t 算法 c a r t 是c l a s s i f i c a t i o n a n d r e g r e s s i o n t r e e 的简称，既可以处理离散型的属性值， 也可处理连续型的属性值。当决策属性值为连续型时，称为回归树；当决策属性值 为离散型时，称为分类树。该模型使用二叉树将样本集递归地划分为若干子集，决 策属性值在这些子集上的分布是均匀的。树中的叶节点对应着划分的不同区域，划 分是由与每个内部节点相关的分支规则确定的。 根据给定的样本集丁构建分类树有以下三步构成：1 ) 使用样本集丁构建最大二 叉树，使得树中每一个叶节点要么很小( 节点内部所含样本个数小于给定值) ，要么是 纯节点( 节点内部样本的决策属性