（电路与系统专业论文）基于粗糙集理论的决策树生成与剪枝方法[电路与系统专业优秀论文].pdf

摘要 数据挖掘，也称之为数据库中知识发现是一个可以从海量数据中智能地和自动地抽 取些有用的、可信的、有效的和可以理解的模式的过程。分类是数据挖掘的重要研究 内容之一。目前，分类己广泛应用于医疗诊断、天气预测、信用证实、顾客区分、欺诈 甄别等许多领域。 决策树是一种常用的分类模型，与其他分类模型相比，决策树简洁易懂，容易转换 成规则，而且具有与其他分类模型同样的，甚至是更好的分类准确性。 粗糙集理论是由波兰数学家z p a w l a k 教授提出的一种处理模糊，不精确，不完整 和不确定数据的有效工具，现已经过了2 0 多年的发展，在理论和应用上都取得了丰硕 的成果。 本文主要研究了基于粗糙集理论的决策树生成和剪枝方法，具体如下： 1 ) 对决策树生成方法进行研究。p a w l a k 粗糙集理论由于其分类过于精确的特性而 无法很好的处理含有噪声的数据，基于p a w l a k 粗糙集理论构造的决策树也因此而不能 很好的对噪声进行抑制，易产生过匹配训练数据的缺陷，从而不能很好的指导决策。本 文在变精度粗集理论的基础上，对原有的基于p a w l a k 粗糙集理论的决策树生成方法进 行了改进，提出基于变精度粗糙集理论的决策树生成方法。变精度粗糙集理论在将等价 类划归近似区间时允许一定程度的误差存在，这使得生成方法可以很好的抑制噪声数 据，因此这种方法相对于前者来说，具有定的优越性。 2 ) 对决策树剪枝方法迸行研究。为增强决策树的泛化能力，需要对生成的决策树进 行剪枝。根据v a p n i k 结构风险最小化的理论，一个性能较好的模型应在模型的复杂度 与模型的正确率之间取一折中。基于这一理论的指导，本文提出了一种基于粗糙集理论 的决策树剪枝算法。新算法同时考虑了树的复杂度和树的分类精度，力求在二者之间达 到平衡，即在保证一定正确率的前提下，得到尽可能简单的决策树。本文提出两个概念： 深度拟合率和错误率，并将这两个概念作为剪枝的标准。 关键词：数据挖掘；决策树；粗糙集理论 a b s t r a e t d a t am i n i n g ( i e k n o w l e d g ed i s c o v e r yf r o md a t a b a s e ) i sap r o c e s st om i n ea v a i l a b l e ， c r e d i b l e ，v a l i da n dc o m p r e h e n s i b l ep a t t e mf r o ml a r g e s c a l e d a t ai na n i n t e l l i g e n t a n d a u t o m a t i cw a y c l a s s i f i c a t i o ni so n eo ft h em o s ti m p o r t a n td i r e c t i o n si nd a t am i n i n ga n dh a s b e e nw i d e l yu s e di nm a n yf i e l d ss u c ha sm e d i c a ld i a g n o s i s ，c l i m a t ep r e d i c t ，c r e d i tv a l i d a t e ， c l i e n td i s t i n g u i s h ，f r a u dd i s c r i m i n a t ea n ds oo n d e c i s i o nt r e ei sar e g u l a rc l a s s i f i c a t i o nm o d e l c o m p a r i n gw i t ho t h e rc l a s s i f i c a t i o n m o d e l s ，i ti sc o n c i s ea n dc o n v e n i e n tt ob et r a n s f o r m e di n t or u l e s ，w h i c ha r es i m p l ef o rp e o p l e t ou n d e r s t a n d a n dt h ec l a s s i f i c a t i o na c c u r a c yo fd e c i s i o nt r e ei sb e r e ro rn o tw o r s et h a no t h e r m o d e l s d u et oa l lt h e s ea d v a n t a g e s ，d e c i s i o nt r e eh a sg o t c e naw i d ea p p l i c a t i o n r o u g hs e tt h e o r yp r o p o s e db yp r o f e s s o rz p a w l a ki s a ne f f e c t i v et o o lt od e a lw i t h v a g u e n e s s ，i m p r e c i s e ，i n c o m p l e t ea n du n c e r t a i nd a t a ，w h i c hi t h a sg a i n e df r u i t f u lp r o g r e s s a f t e r2 0 y e a r s d e v e l o p m e n t t h ew h o l ew o r ko ft h i sd i s s e r t a t i o ni sm a i n l yo nt h ea p p r o a c ho fc o n s t r u c t i n ga n d p r u n i n gd e c i s i o nt r e eb a s e d o nr o u g hs e tt h e o r y ： 1 ) r e s e a r c ho nt h ei n d u c i n ga p p r o a c ho f d e c i s i o nt r e e p a w l a kr o u g hs e tt h e o r yc a n td e a l w e l lw i t hn o i s yd a t af o ri t sp r o p e r t yo f r i g o r o u sp r e c i s i o n ，a n dn e i t h e rd o e st h ed e c i s i o nt r e e i n d u c t i o na p p r o a c hb a s e do ni t t h et r e ec o n s t r u c t e db yp a w l a kr o u g hs e tt h e o r yi se a s yt o o v e r f i tt h et r a i n i n gd a t aa n dc a n ti n s t r u c tp r e d i c t i o ne f f e c t i v e l y t h i sp a p e ri m p r o v e dt h e p a w l a k r o u g hs e tt h e o r yb a s e dd e c i s i o nt r e e i n d u c i n ga p p r o a c ha c c o r d i n gt o v a r i a b l e p r e c i s i o nr o u g hs e tt h e o r y v a r i a b l ep r e c i s i o nr o u g hs e tt h e o r yp e r m i te q u i v a l e n c ec l a s s e st o b ec l a s s i f i e di n t ot h ea p p r o x i m a t i o ns p a c ew r o n g l yi ns o m ee x t e n t ，w h i c hi n s u r e st h et r e e c o n s t r u c t e db yi tc a l lp r o h i b i tt h en o i s yd a t ap e r f e c t l yc o m p a r i n gw i t ht h eo n ec o n s t r u c t e db y p a w l a kr o u g hs e tt h e o r y , 2 ) r e s e a r c ho nt h ep r u n i n ga p p r o a c ho f d e c i s i o nt r e e i ti si m p o r t a n t t op r u n et h ed e c i s i o n t r e ef o re n h a n c i n gt h eg e n e r a l i z ep r o p e r t yo fi t a c c o r d i n gt ov a p n i k st h e o r yo fm i n i m u m s t r u c t u r er i s k ，am o d e lw i t hg o o dp e r f o r m a n c es h o u l ds p l i tt h ed i f f e r e n c eb e t w e e nm o d e l s c o m p l e x i t ya n di t s e r r o r u n d e rt h ei n s t r u c t i o no ft h et h e o r y , t h i sp a p e rp r o p o s e san e w d e c i s i o nt r e ep r u n i n ga p p r o a c hb a s e do nr o u g hs e tt h e o r y t h en e w a p p r o a c hb o t hc o n s i d e r s t h et r e e sc o m p l e x i t ya n dt r e e sc l a s s i f i c a t i o na c c u r a c yi nt h ep r u n i n gp r o c e s s ，a n dt r i e st o m a k eab a l a n c eb e t w e e nt h et w oa s p e c t s t w oc o n c e p t so f d e p t h f i t t i n gr a t i oa n d e r r o rr a t i o h a v eb e e np r o p o s e da st h ec r i t e r i o nf o rp r u n i n g k e y w o r d s ：d a t a m i n i n g ；d e c i s i o nt r e e ；r o u g hs e tt h e o r y 1 i 独创性声明 本人声明所呈交的学位沦文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得东北师范大学或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在沦文中作了明确的说明并表示谢意。 学位论文作者签名：至，丕叠日期；皿篮辜上超蝴 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即； 东北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权东北师范大学可以将学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编学 位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 r 期 三星扔 ) 艘区r 埴日 学位论文作者毕业后去向 ： 作单位：奎缝鲑坐基逝丑笠趣西瞎 通讯地址：扭趁业太暨吐露扭西席 指导教师签名 日期 电话： f 纽2 鲤斗2 y 篮 邮编： f 妞争p 引言 随着计算机技术的迅速发展，企业信息化程度的提高，科学研究和政府部门中信息 化事务处理技术的运用，数据收集工具和技术的多元化以及互联网的发展为我们带来了 海量的数据和信息。但存储在各种数据媒介中的海量的数据，在缺乏强有力的工具的情 况卜- ，已经远远超出了人的理解和概括的能力，从而导致了“数据爆炸但知识匮乏”的 现象。我们已经被淹没在数据和信息的汪洋大海之中，存储数据的爆炸性增长对数据的 处理技术和工具提出了更高的要求。在这种情况下，传统的知识获取技术已经疆的无能 为力，如何从大量的，杂乱无章的，强干扰的数据中挖掘潜在的，有利用价值的信息， 给人类的智能信息处理能力提出了前所未有的挑战，由此产生了人工智能研究的一个崭 新领域数据挖掘( d a t am i n g ，简记为d m ) 。 数据挖掘，简单地说就是从大量数据中提取或“挖掘”知识的过程，定义为：从大 型数据库中识别出有效的、新颖的、潜在有用的和最终可理解模式的高级处理过程。数 掘挖掘是一门交叉学科，涉及的学科领域包括：数据库技术、人工智能、机器学习、人 工神经网络、统计学、模式识别、知识库系统、知识获取、信息检索、高性能计算和数 据可视化等。 1 可挖掘的模式 数据挖掘的任务是从数据中发现有趣的模型。模型是用语言l 来表示的一个表达式 e ，可用来描述数据集f 中数据的特性，e 所描述的数据是集合f 的一个子集f e 。e 作 为一个模型要求它比列举数据子集f e 中所有元素的描述方法简单。模型有多种分类， 下面作。简要的介绍： 按功能模型可分为两大类：描述型( d e s c r i p t i v e ) 模型和预测型( p r e d i c t i v e ) 模型： 1 ) 描述型模型：运用所掌握的信息，对问题进行尽可能充分和全面的认识。 2 ) 预测型模型：掌握问题中蕴涵的规律，对未来系统做出准确的预见。 在实际应用中，往往根据模型的实际应用细分为以下6 种： 1 ) 关联模型 挖掘数据中项集之间有趣的关联或相关联系，首先找出频繁项集，然后产牛形如 a 斗b 的关联规则1 1 - 3 ，这些规则要受到最小置信度和最小支持度阈值的约束，关联规 则广泛应用丁：购物篮或事务数据分析。 2 ) 分类模型 分类用于对有监督数掘进行分析，通过对训练数据集数据进行分析，归纳出能够区 分各数据对象类标识的模型，如i f t h e n 规则、决策树、数学表达式或神经网络等，并 利用得出的模型对未知数据进行预测。 i 3 ) 回归模型 凹i 1 1 模型的函数定义与分类模型相似，其差别在于分类模型的预测值是离散的，而 回归模型的预测值是连续的。 4 ) 聚类模型 聚类是把数据按照相似性归纳成若干类别，同一类中的数据彼此相似，不同类中的 数据彼此相异。与分类不同，用于聚类分析的训练数据一般不提供类标识。聚类分析根 据最大化类内的相似性，最小化类间的相似性的原则将数据对象分组成多个类或簇。所 形成的每个簇都可以看出一个对象类，由它来导出规则。 5 ) 孤立点分析模型 数据库中常包含一些数据对象，它们与数据的一般行为或模型不一致，这就是所谓 的孤立点。大部分数据挖掘方法将孤立点视为噪声或异常数据而丢弃。然而在一些应用 中，如欺诈甄别，这些事件可能比正常出现的更有趣，对孤立点数据所做的分析称为孤 立点挖掘( o u t l i e r m i n i n g ) 。 6 ) 时间序列模型 时间序列模型根据数据随时问变化的趋势，发现某一时间段内数据的相关模型，预 测将来可能出现的值的分布。 其中，分类模型挖掘技术作为数据挖掘的重要分支可对电信、银行、保险、零售和 医疗等诸多行业提供决策支持，对未来商业和人们的生活将产生深远的影响。例如，某 信用卡公司的数据库中保存着所有持卡人的记录，公司根据信誉程度，将持 人记录分 成- z 类：良好、一般、较差，并且将这三种类别分别赋给数据库中的各个记录。挖掘分 类模型就是分析该数据库的记录数据，提取出客户属性和客户所属类别的关系，形成分 类规则，如“年收入在5 万元以上，年龄在4 0 5 0 之间的客户信誉良好”。对信用 公 司的数据库进行分类规则挖掘，提取出有用的分类规则，可以使公司有选择地提供服务， 提高了公司的运营效率。 用于挖掘分类模型的方法很多，如决策树方法、贝叶斯统计方法、遗传算法、k 最 近邻方法等。其中决策树方法由于在构建模型的时候不需要除数据集以外的其它信息， 并且具有构建速度快、准确率高、容易为人理解等优点而倍受人们青睐。 决策树，又称判定树，是一种类似于二叉或多叉的树结构，通过对数据对象进行分 类分析，从中归纳出一些具有价值的、潜在有用的信息。树中的每个非叶节点( 包括根 节点) 对应于训练数据集中一个条件属性，这些条件属性的每一个取值都会生成一个分 支，每个叶节点代表一个类或分布。从根节点到叶节点的每一条路径都对应一条分类规 则。决策树可以很方便地转化为分类规则，是一种非常直观的分类模型表示形式。决策 树方法自产生至今，先后产生了多种算法。 1 9 6 6 年，h u n t 等人1 4 1 提出了第一个可用于构造决策树的概念学习系统c l s ，自从 那以来，产生了不少的决策树系统，如q u i n l a n 分别于1 9 8 3 年和1 9 9 3 年研制的i d 3 【5 l 和c 4 5 1 6j 算法，以及r i c h a r do l s h e n h e 和c h a r l e ss t o n e 等人于1 9 8 4 年研制的c a r l l 算 法”。 w e ij i n m a o 8 。o 】将粗糙集理论引入树的构造过程，根据粗糙集理论中近似区间的概 念，每次选择能明确分类实例个数最多或者不能明确分类实例个数最少的属性作为当前 分支的节点。 理想的决策树分为3 种：( 1 ) 叶结点数最少：( 2 ) 叶子结点深度最小；( 3 ) 叶结点 数最少且叶子结点深度最小。在评价一棵决策树时，除去分类的精度应放在第一位产以 考虑外，分类的复杂度也是另一个需要考虑的重要因素。因此，许多学者致力于寻找更 优的启发式函数和评价函数。洪家荣【1 1 1 、t up e r l e r 1 2 j 等人分别证明了要找到这种最优的 决策树是非常困难的，它是一个n p 难题。因此，人们为寻找较优的解，不得不寻求各 种启发式方法。 1 9 9 2 年a h adw 1 1 3 1 和k i r ak 【1 4 j 等人分别对属性集的选择进行了细致的研究。同年 o l i v e rj 1 1 5 i 扩充了决策树，形成决策图。 19 91 年w o nc h a n j u n g 等人 1 6 1 采用的优化算法很简单，其基本思想是：首先用i d 3 选择属性f l ，建立树t l ，左右子树的属性分别为f 2 ，f 3 ，再以f 2 ，f 3 为根，重建树t 2 ， t 3 ；比较树t l ，t 2 ，t 3 的结点个数，选择结点最少的树。对于选定树的儿子结点采用同 样的方法，递归建树。尽管作者用一个实验证明能够建立理想的决策树，但算法有较大 的弱点：时间开销太大，因为每选择一个新的属性，算法需要建立3 棵决策树，并从中 选优。 1 9 8 7 年j r q u i n l a n 【l7 】对决策树剪枝问题进行了深入的研究，1 9 9 7 年f l o r i a n a e s p o s i t o 等人【1 8 j 对比较流行的六种剪枝算法进行实验对比，分析了各种算法的特性。 本文也将决策树这一重要的分类挖掘技术作为研究的对象。 2 本文的主要研究工作 本文的研究重点放在决策树的生成和剪技过程，并提出了自己的改进意见和新的设 想。 1 ) 对基于p a w l a k 粗糙集理论的决策树生成方法进行改进。p a w l a k 粗糙集理论对等价 类的划分是完全精确的，而没有某种程度上的包含，这种精确性很容易受到噪声的影响， 在对含有噪声的数据进行建模时，不能对噪声进行很好的抑制，降低了模型的预测能力。 变精度粗糙集理论在划分近似区间的时候引入了误差因子，当等价类中大部分实例属于 某区问时，就将此等价类划归入此区间，从而弱化了等价类中噪声的影响，使得生成的 模型能更好地表征系统的特性。本文基于变精度粗糙集理论对p a w l a k 粗糙集理论构造 决策树的方法进行了改进，提出了变精度粗糙集的决策树生成方法。 2 ) 提出基于粗糙集理论的决策树剪枝方法。由 二训练数据中不可避免的会存在噪声， 住建市决策树的过程中，决策树将既对正确数据建模同时也对噪声数据建模，为降低噪 声的影响，需要对决策树进行剪枝。按照v a p n i k 结构风险最小化的理论， 个性能好 的模型应该在保证精确度的前提下，尽量降低模型的规模，在精度和模型的复杂度之间 取一折中。新剪枝策略即是在这种思想的启发下设计出来的。新策略同时考虑了决策树 的分类精度和决策树的复杂度，力求在保证决策树具有较高的分类精度的前提下- ，构造 简单的决策树。 本文的主要内容安排如下： 引言：介绍了课题的来源和背景。简述数据挖掘的概念及意义，分析了数据挖掘可 挖掘的几种模型，分析分类模型挖掘的重要性，并由此引出决策树一种重要的分类挖掘 技术决策树。 第一章：决策树生成算法。简要阐述数据挖掘中的决策树技术，并对目前应用比较 成熟的几种决策树生成算法进行了详尽的分析。 第二章：基于粗糙集理论的决策树生成方法的改进。简要介绍了粗糙集理论的研究 背景和基本原理，详尽介绍了基于粗糙集理论的决策树生成方法，并针对其中存在的缺 陷提出了基于变精度粗糙集理论的改进方法。 第三章：决策树剪枝方法。分析了各种简化决策树的策略，在v a p n i k 结构风险最小 化理论的指引下，提出了一种基于粗糙集理论的决策树剪枝策略，在剪枝的过程中，除 了考虑决策树的分类精度外，将树的复杂程度也考虑了进去。 结论：对全文作一总结，并对下一步的工作进行大体的展望。 第一章、决策树生成算法 人类认识事物从分类丌始，分类能力是人类智能的基础。在数据挖掘中，分类的目 的是提出一个分类函数或分类模型( 也常称为分类器) ，通过分类模型把数据库中的数 据项映射到给定类别中的某一个。 一般情况下，数据集被分为两部分，一部分作为训练集，用于生成分类模型，另一 部分作为测试集，用以对生成的模型进行评估，满足一定标准的模型才会被用于对未知 数据进行预测。训练集和测试集都是有监督的数据集，其中的属性包括条件属性和决策 属性，决策属性中的每个属性值都表示一个类别，集合中的每个实例都被映射到一个确 定的类别。一般情况下，测试集和训练集是相互独立的。 1 创建分类模型2 模型评估和预测 图1 分类步骤 f i g 1t h es t e pf o rc l a s s i f i c a t i o n 如 ：图所示，分类问题分为两步： 1 )创建分类模型：这是一个机器学习过程，通过某种分类算法对训练集进行训 练，得到分类模型。 2 )使用模型预测：使用分类模型前先用测试集评估分类模型的准确率。满足一 定精度的分类模型可以用来对类别未知的数据集进行预测。 多年来，围绕分类问题进行了积极的研究并取得了许多成果，主要集中在知识的模 型表示上，如决策树、贝叶斯网络、神经网络、概念格和粗糙集合等【悍。2 3 1 。其中决策树 【2 4 l 足种常用的分类模型。与其它分类模型相比，在构造决策树的过程中，不需要除训 练数据集之外的任何额外信息，训练速度比较快，生成的决策树的分类精度比较高，且 容易被人理解，因此决策树在实际中得到了广泛的应用1 2 5 - 2 8 i 。 1 1 决策树技术 决策树是一种倒立的树型结构，从一组无次序、无规则的事例中推理出树状形式表 示的分类规则。它采用自顶向下的递归方式，根据一定标准选取属性作为决策树的内部 节点，并根据该属性的不同取值构造不同的分支，在树的叶结点得到结论，所以从根节 点到叶结点的每一条路径就对应一条规则。 图2 决镱树示例 f i 9 2 a ne x a m p l ef o rd e c i s i o nt r e e 例如，图2 是从某银行的借贷业务中得到的决策树。其中，圆圈代表非叶节点，方 块代表叶子节点。从图中共可得到三条分类规则：规则l ：年薪低于2 万且学历为本科 的同意受理其借贷请求；规则2 ：年薪低于2 万且学历不是本科的拒绝其借贷请求；规 则3 ：年薪超过2 万的同意其借贷请求。 总的来说，决策树的构造是一种自上而下、分而治之的归纳过程，本质上是一种贪 心算法。决策树上的各个分支是在对数据不断分组的过程中逐渐生长出来的。首先，选 择一个属性作为根节点，然后把该属性的每一个可能的值作为子节点，这样就把整个训 练集分成了几个子集，根节点属性的每个取值都对应着一个子集，然后递归应用到每个 子树卜进行进步划分，直到对所有数据的继续分组不再有意义时，决策树的生k 过程 宦告结束，此时便生成了一棵完整的决策树。其中，测试属性的选择是构建决策树的关 键环节，不同的决策树算法在此使用的技术都不尽相同。 建立决策树的伪代码如下： 算法：b u i l d t r e e ( s ) 输入： s ：训练样本集； a ：测试属性集 输出： t ：一棵决策树 用样本集s 创建节点n i f a 为空t h e n 返回n 为叶节点 i f n 为纯t h e n 返回n 为叶节点 e l s e 6 f o r 每一个属性a 根据某一评价标准选取属性a 作为当前节点 根据a 的取值将s 分裂为 s ，并对决策树分叉 对每一个s i fs 为空，则返回叶节点 e l s eb u i l d y r e e ( s ) 在实际应用中，数据中不可避免的会存在噪声和异常，决策树在建模的过程中将既 对l 卜确数据建模，同时也对这些噪声和异常数据建模，为消除噪声和异常数据对决策树 的影响，需要对生成的决策树进行剪枝。剪枝按照实施时间的不同分为预剪枝和后剪枝。 预剪枝在决策树的构建过程中对每一个节点进行判断，如果符合某种预剪枝的标准，就 停j h 树的构造，生成叶节点。后剪枝则是待决策树完全生成后，运用特定的剪枝算法对 整棵决策树进行修剪。 在本章中我们介绍几种典型的决策树生成算法，决策树的剪枝算法将在第三章进行 详细的介绍。 1 2 决策树生成算法 1 9 6 6 年，h u n t 等人提出了第一个可用于构造决策树的概念学习系统c l s ，a 从那 以来，产生了小少的决策树系统，如q u i n l a a 分别于1 9 8 3 年和1 9 9 3 年研制的i d 3 和c 4 5 算法，以及r i c h a r do l s h e n h e 和c h a r l e ss t o n e 于1 9 8 4 年研制的c a r t 算法。下面对这些 算法作一介绍。 1 2 1c l s 学习算法 c l s 学习算法是1 9 6 6 年由h u n t 等人提出的，它是早期的决策树学习算法，后来的 许多决策树学习算法都可以看作是c l s 算法的改进与更新。 c l s 算法的主要思想是从一个空的决策树出发，通过添加新的节点柬完善原来的决 策树，直至该决策树能够正确地分类训练实例为止。 算法： 1 ) 令决策树t 的初始状态只含有一个树根( x ，q ) ，其中x 是全体训练实例的集合， 0 是伞体测试属性的集合。 2 ) 若t 的所有节点( ，q ) 都有如下状态：或者第一个分量x 中的训练实例部属于 同一个类，或者第二个分量o 为空，则停止执行学习算法，学习的结果为t 3 ) 否则，选取一个不具有步骤2 ) 所描述状态的节点( x ，q ) 4 ) 对于q ，按照一定规则选取测试属性b ，设x 被b 的不同取值分为m 个不相交 的子集x ，1 i m ，从( x ，q ) 伸出n 1 个分叉，每个分叉代表b 的一个不同取 值，从而形成1 1 1 个新的节点( k ，q b ) ，l i m 。 从c l s 算法的描述过程可以看出，决策树的构造过程也就是假设特化的过程，所以 c l s 算法可以看作是只带个操作符的学习算法，此操作符可以表示为：通过添加一个 新的判定条件( 新的判定节点) ，特化当前假设。c l s 算法递归调用这个操作符，作用 在每个节点，来构造决策树。 在c l s 算法中，并未明确给出测试属性的选取标准，所以c l s 算法有很大的改进空 间。 1 2 2i d 3 学习算法 在c l s 算法基础上发展起来的决策树的学习算法当中，最有影响的是q u i n l a n 在 1 9 7 9 年提出的以信息熵的下降速度作为选取测试属性标准的i d 3 算法。i d 3 名称的由来 是闵为它是一系列的“交互式二分法”程序的第3 版( i n t e r a c t i v ed i c h o t o m i z e r - 3 ) 。 信息论简介 1 9 4 8 年s h a n n o n 提出并发展了信息论【2 9 1 ，从数学的观点来思维并度量信息，信息沦 对通信后信源中各种符号出现的不确定程度进行分析，并由此度量信息量的大小。 i ) 自信息量：设 x 1 ，x ：，x 。) 为信源发出的信号，在收到x 。之前，收信荐对信源 发j h 信号的不确定性定义为信息符号的自信息量t ( x ) 。即： i ( x 、) = 一l o g p ( x ) 其中p ( x ) 为信源发出x 的概率。 2 ) 信息熵：自信息量只能反映出某个符号的不确定性，而信息熵可以用来度量整 个信源x 整体的不确定性，定义如下： i ( x 。) = 一p f x ) l o g p ( x ) ，i 1 ，n 】 l = l 其中n 为信源x 所有可能的符号数，即用信源每发一个符号所提供的平均自信息量 来定义信息熵( 平均信息量) 。在本文中，l o g 均表示以2 为底的对数。 3 ) 条件熵：如果随机变量x 与随机变量y 不是相互独立的，假设收信者收到了y ， 那么用条件熵h ( x y ) 来度量收信者在收到随机变量y 之后，对随机变量x 仍然存在的 小确定性。设x 对应信源符号x 。，y 对应信源符号y ，p ( x 。y j ) 为当y 为y j 时x 为x 的概率，则有： h ( x y ) = 一p ( x 。y ，) l o g p ( x 。y ，) ，i 1 ，n 】，j 【l ，m 】 4 ) 平均互信息量：用它来表示信号y 所能提供的关于x 的信息量的大小，用i ( x ；y ) 表示： i ( x ；y ) = h ( ) ( ) 一h ( x y ) 信息论在决策树中的意义和应用 在丌始学习的时候，决策树只是一棵空树，并不知道如何根据属性将实例进行分类， 我们所要作的就是根据训练实例集来构造决策树。设此时i ) t l 练实例集为x ，我们的目的 足将训练实例分为n 类。设属于第i 类的训练实例个数是c 。，x 中总的训练实例个数为 i x l ，若记个实例属于第i 类的概率为p ( c ) ，则有： p ( c i ) = 熹 在给定分布 p ( c 。) ，p ( c ：) ，p ( c 。) 的情况下，蕴涵在此分布内的信息定义为： h ( x ，c ) = - p ( c ) l o g p ( c 。) 一般在无混淆的情况下将h ( x ，c ) 简记为h ( x ) ，h ( x ) 表征了系统的不确定程度。 决策树学习过程就是不断选择节点来降低系统的不确定性程度的过程。若选择测试 属性a 进行测试，在得知a = a 。的情况下属于第i 类的实例个数为c 日个，记： p ( c j ；a 毡) = 熹 即p ( c ，；a = a 。) 为测试属性a 的取值为a ，时它属于第i 类的概率。以x 。表示以属性 a 取值为a ，时在训练实例集x 上的映射，即x 中属性a 取值为a 。时的所有实例所形 成的集合，此时实例子集x 对分类的不确定性程度为： h ( x ，) = 一p ( c a = a ，) l o g p ( c 。a = a ) 9 选择测试属性a 后，系统的不确定程度定义为： h ( x a ) = 一p ( a = a ，) h ( x ，) 】 = 一p ( a = a ) p ( c 。a = aj ) l o g p ( c 。a = aj ) i j 属性a 对分类所作出的贡献，即选择属性a 后系统不确定性的下降程度，也即属性 a 的信息增益( i n f o r m a t i o ng a i n ) 定义为： i ( x ；a ) = h ( x ) h ( x a ) 属性a 的信息增益越大，说明它对于分类提供的信息越多，选择a 之后系统的不确 定性程度将降低越多。 由于决策树的结构越简单越能从本质的层次上概括事物的规律，我们于是期望非叶 节点到达后代节点的平均路径最短，即生成的决策树的平均深度最小。这就要求在每个 节点选择好的划分。香农的信息论表明，系统的不确定性越小，信息的传递就越充分。 i d 3 算法根据信息理论，采用划分后样本集的不确定性作为衡量划分好坏的标准，用信 息增益值度量这种1 ；确定性：信息增益值越大，不确定性越小。因此，算法在每个非叶 节点选择信息增益最大的属性作为测试属性。然后根据此测试属性的取值划分样本集， 测试属性有多少不同取值就将样本划分为多少予样本集。 算法：i d 3 f o r m t r e e ( s1 输入： s ：训练样本集 a ：测试属性集 输出： t ：一棵决策树 用样本集s 创建节点n i r a 为窄 返回n 为叶节点，标记为s 中多数实例对应的类 i f n 为纯 返回n 为叶节点，标记为所有实例对应的类 e l s e f o r 每一个属性a 估计选择a 作节点的信息增益 选出信息增益最大的属性a f 作为当前节点 根据a 的取值将s 分裂为 s ) ，并对决策树分又 对每一个s ， 1 n i fs ，为空，则返回叶节点 e l s e 执行i d 3 f o r m t r e e ( s 。) ) i d 3 算法存在一个弊端：偏向于选择取值较多的属性。但在实际中取值较多的属性 不一定是最佳的属性，举一个极端的例子：设属性a 的取值是随机的，且a 的可能值如 此之多，以至于任何两个待分类对象都不可能有相同的取值。所以第一个测试属性应当 选取a ，将使得熵值下降最快，但是由于a 的取值是随机的，所以对a 进行分类将得不 到任何信息，这说明a 的选择足不恰当的。而且，i d 3 算法不能直接处理连续型属性， 不能处理属性值空缺的样本。为改进这些不足，产生了c 4 5 算法。 1 2 3c 4 5 学习算法 c 4 5 算法是q u i n l a n 在1 9 9 3 年提出的，在i d 3 算法的基础上，加进了对连续型属性、 属性值空缺情况的处理，对树剪枝也有了较成熟的方法【3 0 1 。 劈分准则 在i d 3 算法中，只考虑了实例分类过程中的变化，但是有时为了获得一个实例关于 属性a 的取值，需要做实验、进行计算等，这是需要付出一定代价的。设属性a 有k 个 不同的取值，这些取值对应的实例个数为n i , n ：，n k ，1 1 。+ n 2 + n k = n ，其中n 为训练 实例的总数。q u i n l a n 利用属性a 的熵值来表示为了获取实例关于属性a 的取值所需要 付出的代价，定义为对属性a 的分割信息量。 叫i t c 妒一喜谢l 0 9 2 斟 在属性a 提供相同的信息量g a i n ( a ) 的同时，s p l i t ( a ) 的取值越小越好，其值越小说 明为了获取关于a 的耿值所需付出的代价也就越小。q u i n l a n 定义了另外一种测试属性 的选取标准： 2 a i n r a t i o ：g m n ( a ) 。 s p l i t ( a ) 即每次选取使得信息增益率最大的属性作为测试属性。 此选取标准能够有效地克服偏向取值多的属性的毛病，但是也存在缺点，它更偏向 丁选择对属性值取值比较集中的属性( 即熵值最小的属性) ，而并不定是对分类贡献 最人最重要的属性。另外，当属性a 只有一个属性值，或者训练实例对属性a 只有一个 墩值时，s p l i t ( 舢的取值为零，此时或者使得信息增益率无意义( 为无穷大) ，或者使得 决策树进行次没有意义的分类( 即决策树的这个内节点只有个子节点) 。 对连续属性值的处理 c 4 5 对离散属性的处理同i d 3 ，根据属性取值的多少将样本集划分为相应的了集。 对于连续属性a ，按照属性的信息增益率将其划分为两个不同的了集：属性值大于 分割点和属性值小于分割点。c 4 5 寻找最优的分割点的方法是： 1 ) 首先将样本集s 按属性a 的取值从4 , n 大排序，一般用快速排序法。 2 ) 假定排好后属性的取值序列为v ，v ：，v 。，则每两个连续值的中点v = 土三二卫， z i 【1 ，m 1 】就有可能是一个分割点，每个分割点都可将样本划分为两个子集 s i = v iv ，茎v ) 和s ；= ( v iv ， v ) ，划分后所得的信息增益为g a i n 。线性的扫描 v ，v 2 ，v 。，找出v ，使得g a i n ，最大，在序列v 1 ，v2 ，一。找到的最接近但又不超过局部 阈值v 1 的取值v 。成为当自u 节点在属性a 上的分割闺值。按照上述方法求出当前候选属性 集中所有属性的信息增益率，选出信息增益率最高的属性。然后按照该属性的分割闽值， 将当前样本集分为两个子样本集。对子样本集采用同样的方法继续分割直到不能再分割 或达到停止条件为止。 对缺省值的处理 c 4 5 处理空缺属性值的方法是：在计算系统整体的不确定性时，只根据那些已知测 试属性值的样本来计算。在计算根据某属性划分后的信息熵时，把那些丢失测试属性值 的样本作为一个新的子样本集，单独计算这些样本的期望信息熵。在划分训练集时，先 将不含空缺属性值的样本按照一定的算法划分成几个子集，然后把那些丢失测试属性值 的样本按照一定的概率分布到各个子集中，子集中含有空缺测试属性值的样本与有测试 属性值的样本保持一个比例关系。在对含有空缺测试属性值的未知实例进行分类时， c 4 5 将该实例通过所有的分支，然后将结果进行合并，使它成为在类上的概率分布而彳i 是某1 个类，然后选择具有最大概率的类作为最终的分类结果。 剪枝策略 生成决策树是c 4 5 算法的第一阶段，之后，c 4 5 随机计算每个节点的分类错误率， 考虑对决策树进行剪枝。对每个叶节点，分类错误为该节点中不属于该节点所表示类别 的样本的取值之和；对于非叶节点，分类错误为它的各个孩子节点的分类错误之和。如 果子树t 的分类错误大于将该子树剪技为叶节点后的分类错误，则将该了树剪枝为叶节 点，并用i 中多数实例所表示的类来标识。c 4 5 算法采用e b p 剪枝算法对决策树进行 剪枝，该算法将在第三章进行详细介绍。 相对于1 d 3 算法，c 4 5 算法在功能七有了很人的提高，不仅可以直接处理连续型属 性，还可以允许训练样本集中出现属性空缺的样本。生成的决策树的分支也比较少。c 4 5 是 d 3 的改进算法，分割样本时采用的仍然是信息论的原理。下面我们介绍一种基于距 离的决策树生成算法c a r t 算法。 】， 1 2 4c a r t 学习算法 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 ，分类回归树) 算法是一种非参数化的 方法，采用一种_ 二分递归分割的技术，每次都会将当前样本集分割为两个子样本集，使 得牛成的决策树的每个非叶节点都有两个分支，因此，c a r t 算法生成的决策树是结构 简单的二叉树，容易为人理解和解释。在c a r t 算法中，也含有处理连续型属性、窀缺 属性值和剪枝的机制。其中，对连续属性值的处理同c 4 ，5 ，c a r t 算法与c 4 5 算法的 本质区别在于劈分准则和对缺损模式的处理上。c a r t 算法在训练过程中，为侮个“主 分支”属性提供了“替代分支”属性集，而在c 4 5 中并未对后继的缺损模式的分类提供 号门的考虑，没有提前计算替代分支。币因为c 4 5 没有替代分支的概念，因而也没有必 要存储它们，因此如果很关心算法的空间复杂度时，c 4 5 算法要比c a r t 优越得多。 劈分准则 考虑训练样本中的实例，从构造树的根节点开始，每一步都将当前节点分成两个分 支。算法按照使得生成的两个孩子节点的平均纯度最大的原则选取最优的划分，最常用 的分割算法是g i n i 算法和t w o i n g 算法。这里我们介绍g i n i 生成算法。 设数据集s 的测试属性c 用m 个不同的离散属性值c 。，c ：，c 。，那么其g i n i 指数就 是： g i n i ( s ) = 1 一p i l - 其中p t 是s 中样本取值c ，的概率。如果用属性c 将数据集s 分为两部分s ，s ：， 那么这个划分的g i n i 指数就是： g i n i ( s ) = 鲁xg i n i ( s 1 ) - i - i s 2 x g i n i ( s ：) 在建树的过程中，每次都选择g i n i 指数最小的属性对数据进行划分。设离散型属性 c 共有m 个属性值，则可有2 “种划分数据集的方法。在选择节点划分时，首先找出每 个属性的最佳划分，再比较所有属性的