（计算机应用技术专业论文）基于集成学习的演化决策树方法研究.pdf

中困科学拙术人学删! l ：学位论义 摘监 摘要 分类问题足数掘挖掘领域的一个重要研究方向。其中的决策树方法于具有 易于型u 解，准确度较高等优点，直足国内外研究者的研究重点。如何构造精度 高、规模小的决策树足决策树算法的核心内容。传统决策树算法，如单变量和 多变量决策树算法，由于搜索空间过大，一般都是使用启发式的贪心搜索策8 ， 容易陷入局部最优。近年来，随着演化算法的蓬勃发展，演化算法与传统机器学 习方法的结合r 益广泛。目前已经有一些演化决策树算法，从不同角度增加决策 树算法的全局搜索能力。但是，如何进一步提高演化决策树算法的分类准确度、 加快算法的收敛速度仍然是一个值得研究的问题。本文提出了一种演化决策树算 法，并将其与集成学习框架相结合，以提高演化决策树的泛化能力和稳定性。本 文的主要工作和特色如下： 在对现有的决策树算法和演化决策树算法研究的基础上，设计了一利，树 型结构的演化决锛树算法。基于分类准确度、演化决策树的高度和演化代数等， 提出了一种适应度函数。针对树型结构的特点，改进了遗传算法的遗传算子，并 设计了一种剪技算子。 将我们提出的演化决策树算法和集成学习框架进行结合，分别设计和实 现了b a g g i n g 演化决策树和a d a b o o s t 演化决策树算法。实验表明，相对于基本 的演化决策树算法，基于集成学习的演化决策树算法能在较短的演化代数内达到 较高的分类精度。 对集成学习进行了较深入的研究，分析了b a g g i n g 和b o o s t i n g 方法的理 论依据。在此基础上，设计了一种基于混合集成学习的演化决策树方法。该方法 混合使用b a g g i n g 和a d a b o o s t 方法，并且在数据重采样划分时使用了数据的水 s p 和垂直划分。实验结果表明该方法是有效的。 关键词：数据挖掘，分类，决策树，演化算法，集成学习 中周科学技术人学瑚l 学位论文 a b s t r a c i a b s t r a c t c l a s s i f i c a t i o ni sa ni m p o r tr e s e a r c ha r e ai nd a t am i n i n g t h ed e c i s i o nt r e e ，w h i c h i sab r a n c ho fc l a s s i f i c a t i o n ，h a sa t t r a c t e dt h er e s e a r c h e r sa l lt h et i m eb e c a u s eo fi t s s i m p l i c i t ya n dh i g ha c c u r a c y t h ek e yo f d e c i s i o nt r e em e t h o di sh o wt oc o n s t r u c ta d e c i s i o nt r e ew i t hh i g ha c c u r a c ya n ds m a l ls c a l e t h es e a r c hs p a c eo fd e c i s i o nt r e e m a y b ev e r yl a r g e ，s ot h ec o n v e n t i o n a ld e c i s i o nt r e ea l g o r i t h m s ，e g ，u n i v a r i a t ea n d m u l t i v a r i a t ed e c i s i o nt r e e s ，g e n e r a l l yu s et h eh e u r i s t i cg r e e d ys e a r c hs t r a t e g y b u tt h e y o f t e nf a l li n t ol o c a lo p t i m u m w i t ht h ed e v e l o p m e n to fe v o l u t i o n a r ya l g o r i t h m s ，t h e c o m b i n a t i o no fe v o l u t i o n a r ya l g o r i t h m sa n dc o n v e n t i o n a lm a c h i n el e a r n i n gm e t h o d s a r e i n c r e a s i n g l yw i d e p r e s e n t l y t h e r ea r es e v e r a l e v o l u t i o n a r y d e c i s i o nt r e e a l g o r i t h m sw h i c he n h a n c et h eg l o b a ls e a r c h i n ga b i l i t y o fd e c i s i o nt r e e s h o w e v e r ， h o wt oa c h i e v eh i g hc l a s s i f i c a t i o na c c u r a c yi nas h o r tt i m ei sw o r t hs t u d y i n g t h i s p a p e rp r o p o s e s a n e v o l u t i o n a r yd e c i s i o nt r e ea l g o r i t h m i no r d e r t o i m p r o v et h e g e n e r a l i z a t i o na b i l i t ya n ds t a b i l i t y , w ec o m b i n ei t w i t ht h ef r a m e w o r ko fe n s e m b l e l e a r n i n g t h em a j o rt a s ka n di n n o v a t i o n sa r e ： b a s e do nt h er e s e a r c ho nc u r r e n te x i s t i n gd e c i s i o nt r e ea n de v o l u t i o n a r y d e c i s i o nt r e ea l g o r i t h m ，w ed e s i g na ne v o l u t i o n a r yd e c i s i o nt r e ea l g o r i t h mw i t ht h e t r e es t r u c t u r e i nc o n s i d e r a t i o no ft h ec l a s s i f i c a t i o na c c u r a c nt h ed e p t ho fd e c i s i o n t r e ea n dt h ee v o l u t i o ng e n e r a t i o n s ，af i t n e s sf u n c t i o ni sp r o p o s e d w ea l s oi m p r o v et h e g e n e t i co p e r a t o r sa n dd e s i g na n o v e lp r u n i n g o p e r a t o r w e c o m b i n et h ee v o l u t i o n a r yd e c i s i o nt r e ea l g o r i t h ma n dt h ef r a m e w o r ko f e n s e m b l e l e a r n i n g ，d e s i g n a n di m p l e m e n tt w o a l g o r i t h m s ，b a g g i n ge v o l u t i o n a r y d e c i s i o nt r e ea n da d a b o o s te v o l u t i o n a r yd e c i s i o nt r e e t h ee x p e r i m e n t a lr e s u l ts h o w s t h a tt h ee v o l u t i o n a r yd e c i s i o nt r e ea l g o r i t h mb a s e do ne n s e m b l el e a r n i n ge a r lo b t a i n h i g h e rc l a s s i f i c a t i o na c c u r a c yi ns h o r t e re v o l u t i o ng e n e r a t i o n s w eh a v ea n a l y z e dt h et h e o r e t i c a lb a s i so fe n s e m b l el e a r n i n g b a s e do nt h e l e a r n i n go nb a g g i n ga n db o o s t i n g ，w ed e s i g na ne v o l u t i o n a r yd e c i s i o nt r e ea l g o r i t h m b a s e do nh y br i de n s e m b l el e a r n i n g t h i sa l g o r i t h mu s e sb a g g i n ga n da d a b o o s ti na 中m 科学拙术人学倾l “学位论义 h y b r i dw a y , a n dr e s a m p l e st h et r a i n i n gs e tu s i n gt h eh o r i z o n t a la n d v e r t i c a lp a r t i t i o na t t h es a m et i m e t h e e x p e r i m e n t a lr e s u l td e m o n s t r a t e st h ea l g o r i t h mi se f f e c t i v e k e y w o r d s ：d a t am i n i n g ，c l a s s if i c a t i o n ，d e c i s i o nt r e e ，e v o l u t i o n a r yc o m p u t i n g ， e n s e m b l el e a r n i n g 中田科! 学技术大学坝j j 学位论史 2 f ；1 亭绪论 第1 章绪论 本章概述本文的选题背景。首先阐述了本文涉及到的一些方法的背景知识， 包括分类问题、决策树、演化算法和集成学习。接着，我们对演化决策树算法的 研究和应用的现状进行了介绍。在本章最后，介绍了本文的研究工作和内窬安排。 1 1 选题背景 1 1 1 分类问题 分类是数据挖掘中的一种分析方法，它通过训练构造一个分类模型，该模型 能够把数拥映射到某个给定类别中，从而可以应用于数据预测。分类具有广泛的 应用，如医疗诊断、商业分析等。 数据分类主要包含两个步骤： 第一步、建立一个分类模型，描述给定的数据类集或者概念集。 对于分类，一个训练样本的表示形式为( v l ，v 2 ，v 。；c ) ，其中v 。表示属 性值，c 表示类别。具体到数据库中，训练集是包含些属性的一个数据库表， 而其中的一个属性被定为类别属性。数掘属性的类型可以是离敞的或者连续的， 但类别属性的类型必须是离散的，且类别属性的可能值的数目越少越好，这样构 造出来的分类器的错误率较低。 通常分类学习所获得的模型可以表示为分类规则、决策树等多利，形式。 第二步、利用所获得的分类模型进行分类操作。 利用所获得的模型对未知数据进行预测之前。首先要对所获得模型的准确率 进行评估，如果一个分类模型的准确率经测试被认为是可以接受的，那么就可以 使用这一模型对数据集中的未知数据进行分类预测。 分类器的构造方法有统计方法、机器学习方法、神经网络方法、遗传算法等。 j 巾统计方法包括贝叶斯方法、最近邻学习、支持向量机等；机器学习方法包括 决策树方法和舰则归纳法，阿者由决策树表示，后者则有决策表和产生舰则两种 表示形式：神经网络方法主要是b p 算法，它的模型表示是前向反馈神经网络模 型，其本质足一种非线性判别函数；遗传算法足一种基了二达尔文的进化论思想的 中闽科学技术人学坝i j 学位论文第l 章鲭论 全 0 最优算法，兜服了传统贪心算法容易陷入局部最优的缺点；此外还有近几年 兴起的 f i 糙集方法，山产生规则表示。 e j 前主要柯二种分类器的评价t 度： ( 1 ) 预测准确度预测准确度是使_ i 最多的一种评价尺度，特别是对于预测 ，h 分类问题目时一般使用1 0 层交叉验证法( 1 0 - f o l dc r o s s v a l i d a t i o n ) 。 ( 2 ) 计算复杂度计算复杂度依赖于算法的实现细节，出于数据挖掘的对象 常常是海量数据库中的数据，因此空自j 和时间复杂度问题是非常重要的环节。 ( 3 ) 模型的简洁度模型的简洁程度决定了算法的可理解性和易用性。目 j f ， 分类规则、决策树等方法的简洁度较高而神经网络、遗传算法等方法则不易理 解。 1 1 2 决策树方法 决策树又称判定树，是一种使用树型结构模型对未知数据进行预测的分类方 法。l 于其具有准确度较高易于理解等优点，近年柬，决策树方法广泛应用于 专家系统、模式识别、医疗诊断、入侵检测等领域。 决策树一l 的结点可分为内部结点和叶结点。其中的每个内部结点代表对属性 的次测试，一条边代表一个测试结果，叶结点代表某个类或者类的分布。未知 数据从根结点丌始，使用某个或某些属性进行测试，并根据测试结果选择相应的 分支。这个过程不断重复，直到到达叶结点。叶结点所对应的类别就是预测结果。 对一个分类问题或规则问题，决策树的生成是一个从上至下、分而治之的过 程。这种方法在数据处理的过程中，将数据按照树状结构分成若干分支，每个 分支包含数据的类别属性，这样可从每个分支中提取有用信息，形成分类规则。 图1 1 足一棵简单的决策树表示根据天气情况决定是否适合进行网球比赛。 从中可以提取以下规则： o u t l o o k ：s u n n y , h u m i d i t y ：h i g h o u t l o o k ：s u n n y , h u m i d i t y ：n o r m a l o u t l o o k ：o v e r c a s t o u t l o o k ：r a i n ，w i n d ：s t r o n g o u t l o o k ：r a i n ，w i n d ：w e a k n o t p l a y - - ) p l a y - - ) p l a y n o ip l a y - - ) p l a y 中周科学投术人学碳i j 学位论文 第1 尊绪论 h l h n o n o r t r t a l 、 y e , f 0 w ，n l y e s w e a k 、 y f s 囤1 - 1 一棵简单的决策树 决策树方法主要是通过构造决策树来发现数据中蕴涌的分类规则，如何构造 精度高、规模小的决策树是决策树算法的核心内容。 根掘不同的标准，决策树可以如下分类2 】： 1 、按! ( ( 所属类型的数日来分： 如果数据分为两类，如p l a y 和n o tp l a y ，称为二叉决策树； 如果数据可分为多类，称为多分类器决策树。 2 、按照属性的类型来分： 屈性是名义的，如s u n n y 、o v e r c a s t 、r a i n 等； 属性足数值的，如年龄可为2 0 7 0 之问。 3 、按j ! c l 构造过程来分： 贪心法，传统方法，尽可能的在某种度量标准上达到局部最优化： 演化法，采用演化算法的思想，搜索全局最优解。 4 、按照在内部结点的判断方法上： 单变量，在内部结点的判断时只使用一种属性； 多变量，使用多种属性进行判断。 目前，内部结点的判断是最主要的判断标准。 1 1 3 演化算法 演化算法是美国m i c h i g a n 大学的j h h o l l a n d 教授于1 9 7 5 年首先提出的! 。 其基本思想基于d a r w i n 的进化论和m e n d e l 的遗传学说，根据适者! l 存、优胜劣 汰的进化原则，对可能包含解的种群反复使用遗传进化的基本操作不断生成新的 咻 胁 中困科学技术人学坝l j 学位论义 铺l 常绵i = c = 种群，使物种不断进化。作为一刊，全局搜索的工具，演化算法具有简单、通f j 、 自组织性、自适应性和本质并行性等特性，特别适合处理那些用传统搜索方法难 以有效解决、甚至无法解决的问题。因此近年束，基于演化算法的研究成果在许 多领域得到了j “泛的应用。 在对演化算法的研究上，大致有三种类似的方法：遗传算法( g e n e t i c a l g o r i t h m ) 及其变种遗传编程( g e n e t i c p r o g r a m m i n g ) 和学习分类器系统 ( l e a r n i n g c l a s s i f i e r s y s t e m ) 、演化策略( e v o l u t i o n s t r a t e g y ) 和演化编程 ( e v o l u t i o n a r yp r o g r a m m i n g ) 。本文所研究的演化决策树主要是遗传算法在决策树 方法中的应用。下面简单介绍遗传算法的相关内容。 标准遗传算法求解优化问题的算法框架描述如下： ( 1 ) 髓奄t 生成一个枷始静辞： ( 2 ) 确定每一个体的适应鏖： ( 3 ) 棱选择机翻选出父 奉 “) r e p e a t 以概率p c 杂交： 以 f f 率 p m 变异； 计算个体适应瘦： 按选择机蕞9 选出父体： u n t i l 终止条件 遗传算法是一种群体型操作，浚操作以种群中的所有个体为对象。选择 ( s e l e c t i o n ) 、交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) 是遗传算法的三个主要操作 算子，它们构成了遗传操作，使遗传算法具有了其它传统方法所没有的特性。 遗传算法中包含了如下5 个基本要素1 4 ： 参数编码 有二一进制编码、实数编码和结构化编码等多剃t 形式。 蕾u 盘 j 种群的设定 遗传算法种群中的个体一般是随机产生的。 适应度函数的设计 适应度函数评估是选择操作的依据，适应度函数的设计将直接影响到遗传算 法的性能。一般在设计适应度函数时，会考虑到算法的关键指标，如分类器的分 类准确度等。 中周科学技术人学硕1 1 学位论史 笫i 章绪论 遗传操作设计 标准的遗传算法的遗传操作包括以下三个基本遗传算子：选择、交叉和变异。 遗传算法中，交叉算予阕其全局搜索能力而作为二1 ：要算子，变异算予阅其局 部搜索能力而作为辅助算予。遗传算法通过这对桐互配台又桐一：竞争的操作而 使其具备兼顾全局和局部的均衡搜索能力。空f l 似有效的配合适用交义和变异操 作，是目前遗传算法的一个重要研究内容。 控制参数设定 主要是指种群大小、演化代数和遗传操作的概率等。 1 i 4 集成学习 集成学习( e n s e m b l el e a r n i n g ) 是一利，新的分类学习框架，集成体( e n s e m b l e ) 通过将多个算法学习的结果以某种方式集成，来提高预测的准确度。与单个算法 相比，集成学习不易出现过度拟合的现象。山于集成学习可以显著地提高学习系 统的泛化能力，最近几年，机器学习、神经网络、统计学等领域的很多研究者都 投入到集成学习的研究中，使得该领域成为了一个相对活跃的研究热点，并被认 为是近年来机器学习领域的4 大研究方向之【6 i 。虽然集成学习的方法有很多， 但是目前对于集成学习的研究主要集中在通过改变样本结构来学习的方式上，比 如b a g g i n g l 7 1 和b o o s t i n g f 8 1 9 博法就是通过改变学习样本进行集成学习的代表性算 法。这两种算法分别由b r e i m a n 和s c h a p i r e 提出，是月前应用比较广泛的算法， 它们的共同之处在于使用重采样方法为每个分类器提供不同的训练数掘。 1 1 5 演化决策树算法的研究现状 构造决策树时，存在的一个难题足如何选择较好的属性集。传统的决策树算 法通常是启发式的，即基于信息增益、增益系数等度量值的贪心算法，如i d 3 、 c 4 5 等。但山于它们贪心算法的木质，往往会陷入局部最优，无法在全局空m 找到最优解。 出于演化算法全局搜索的优点，近些年来，演化算法越来越多的与传统的机 器学习方法相结合。自从k o z a 最早将遗传编程应用于决策树分类后，演化决策 树算法得到了迅速的发展。舟f 倚关于演化决策树算法的研究，主要集f l 在以下疗 m i ： 中罔科学披术人学坝l 学位论艾 第l 常绪论 1 、演化决策树本身的设计 演化算法的编码方式、适应度函数的设计、初始种群的生成以及遗传操作算 子等一直是演化算法的核心内容。研究者们基于演化决策树的特点，在这些方 进行了深入的研究。 在编码方式方面，k o z a b o l 使用l i s p 表达式表示决策树的分类规则，最早将 遗传编裎应用于决燕树算法。但这种编码方式不易理解，分类效果也并不刚j 显。 s r o u w h o r s t 等】提出了一种b g p 演化决策树算法使用树型结构编码方式，并 将交叉和变异算予直接应用于树型个体上。在与c 4 5 和c n 2 的比较实验中，b g p 算法表现出了较优的性能。j a n d r a s 和d d u m i t r e s c u 等1 2 】1 1 2 1 使用多表达式编码 ( m e p ) ，提出了m e p d t i 算法，在模拟实验中取得了优于c 4 5 的结果。 适应度函数体现了算法的主要评价标准，因此演化决策树的适应度函数的设 计一般都以分类准确度作为主要部分。t u r n e y l l 3 1 在他的i c e t 算法中，设计适应 度函数时加入了分类代价的概念。既包括进行属性测试和计算度量值的代价，又 包括了由于错误分类引起的代价。在a p a p a g e l i s 和d k a l l e s 1 4 1 的g a t r e e 的设计 中，提出了一种有限错误适应度函数( l e f ) ，当个体在计算适应度时，如果错 误分类数超过了给定的闽值，则剩下的测试样本直接认为被分类错误。使用这种 j j ，法，g a t r e e 在准确率下降不多的同时，大大提高了演化速度。 演化算法中初始种群一般是随机生成的。而在演化决策树算法中，如果初始 种群选择不好，可能会影响算法的性能和效率，并容易陷入局部最优。研究者们 使辟j 各种算法为演化决策树提供初始种群，期望能生成艄对于随机方法较好的初 始个体。如e s p i n d o l a 和e b e c k e n 等旧使用一种模糊决策树方法生成初始种群： s h i n i c h io k a 等【”i 使用c 4 5 初始化种群。 在遗传算子的研究上，e g g e r m o n t 等i 盯1 设计了一种删除算子，删除演化决策 树中的无用部分( 也被称为i n l r o n 即那些对分类结果影响较小的分支) 。他们 通过实验证明，删除i n t r o n 后，演化决策树在不损失太多精度的同时提高了可 理解性和效率。 2 、混合使用演化算法和决策树算法 山于演化算法使用全局搜索策略，能解决其它局部搜索算法无法解决的一些 问题，因此。经常与决策树算法混合使用。如b a l a j 等【博1 利用遗传算法选择较 优的属性子集再使用i d 3 算法生成决策树，得到了g a i d 3 算法。c a r v a l h o 等 1 19 1 1 2 0 j 为了发现那些只覆盖一小部分样本的小析取项规则( s m a l l d i s j u n c tr u l e s ) ， 巾田科学技术人学顺l 学位论史 第1 帮绪论 混合使用c 4 5 和遗传算法。先使用c 4 5 牛成决策树，再使用遗传算法存决策树 中搜索小析取项规则。 由于演化决策树适用于那些传统的决策树算法难以解决的问题，它在许多领 域中得到了广泛的应用。s i e g e l l 2 1 】殴计了一种演化决策树算法，在树型编码方式 巾嵌入化字符串，应用- j 二自然语言理解巾的单词二义惟问题。a e k a r t 和a m a r k u s l 2 2 1 结合了遗传编程和决策树算法以解决四杆机构问题。p o d g o r e l e c 等口列 设计了种医疗诊断演化决策树，改进了医疗决策过程。 1 2 本文研究工作和内容安排 1 2 1 研究工作 本文以演化决策树算法为主要的研究内容。在分析了传统的演化决策树算法 的原理及其不足后，提出了一种演化决策树算法。为了提高算法的性能，将演化 决策树算法与集成学习框架进行了结合。本文的主要研究内容如下： 传统的演化决策树算法出于其贪心算法的本质，容易陷入局部最优。本 文设计了一种演化决策树算法，对问题空问进行全局搜索。算法使用树型结构表 示，比二进制、实数等编码方式更为直观。我们同时考虑了分类准确度、树的高 度、存活时间等因素，设计了一种新的适应度函数。基二j ：决策树的结构特点，本 文改进了传统的遗传算子，并提出了一种剪枝算子，以消除演化过程中的冗余情 况。 基本的演化决策树算法的分类准确度不是很高同时需要较长的演化代 数。本文将演化决策树算法与集成学习框架相结合分别设计并实现了b a g g i n g 演化决策树和a d a b o o s t 演化决策树，通过训练数据重采样生成多个演化决策树 分类器并采用投票方式综合它们的结果。实验结果表明集成学习演化决策树相 对于基本的演化决策树。能在较短的演化代数内得到较高的分类准确度。 本文对集成学习方法进行了理论分析，得出了提高集成学习效果的两个 关键因素：集成体的多样性和单个分类器的分类精度。基于这两个因素，本文提 出了一种基于混合型集成学习的演化决策树算法。我们将集成体的构造扩展为两 层，同时使用b a g g i n g 和a d a b o o s t 方法。同时，对数据重采样的方法也进 于了 修改，综合使用了数据的水平和乖直划分。实验结果表明了算法的有效州：。 中困科学技术人学烦i 学位论文 第l 帝绪论 1 2 2 内容安排 第一章中，对本文研究的工作背景进行了阐述，简单描述了决策树算法、演 化算法、集成学习的背景知识，并介绍了演化决策树算法的研究现状，最后给 h 了本文的主要丁作。 第二章中，对演化决策树算法进行了具体研究。首先从传统决策树算法出发， 介绍了 d 3 、c 4 ，5 等经典决策树算法的思想及其优缺点。针对传统决策树算法的 不足，将演化算法与决策树算法相结合，引入了演化决策树算法。我们深入分析 了几种具体的演化决策树算法。展后，给出了目前演化决策树算法主要的不足之 处。 将集成学习与演化决策树算法相结合是第三章的主要内容。在这一章! 醴，我 们首先介绍了本文所使用的演化决策树的设计，分别从编码方式、适应度函数、 卡，j 始群体和遗传算予等方面加以描述。接着，将集成学习与演化决策树算法相结 合，分别设计和实现了b a g g i n g 演化决策树和a d a b o o s t 演化决策树算法。最后， 在u c i 数据集上进行了模拟实验，并对集成学习演化决策树、普通演化决策树 和c 4 5 决策树的分类性能进行了比较。 为了进步提高演化决策树的分类准确度和收敛速度，第四章里，我们对集 成学习进行了深入的研究。我们以两种最常用的集成学习方法b a g g i n g 和 b o o s t i n g 为例，分析了它们的理论依掘。以此为基础，为了提高集成学习的性能， 我们研究了集成体的构成方式和数据采样方法，提出了两个问题。一是将b a g g i n g 和a d a b o o s t 两种构成方式相结合二是重采样数据的水平划分和垂直划分问题。 基于这两个问题，我们提出了一种新的基于混合型集成学习的演化决策树算法。 最后在u c i 数据集上进行了实验，表明混合型集成学习演化决策树的性能要 优于集成学习演化决策树和c 4 5 决策树。 最后，我们对本文所做的研究工作进行了总结，分析了存在的问题，并提出 了下一步的研究方向。 中困科学技术人学倾l 学位论立 第2 章演化决策树方址研究 第2 章演化决策树方法研究 本章的主要内容是演化决策树方法的研究。首先介绍了传统决策树算法，分 别阐述了一些代表性算法的设计原理、优缺点及适用范围。接着针对传统决策树 算法的不足，引入了演化决策树算法。在对几种演化决策树方法进行了分析之后， 指出了现有演化决策树方法的不足。 2 1 传统决策树算法 早期的决策树算法是1 9 6 6 年山h u n t 等2 4 提出的概念学习系统( c l s ) ，后 来的许多决策树算法都可以看作是c l s 的改进或更新。c l s 算法尝试构造一棵 在进行分类时代价最小的决策树。它的主要思想是从一个空的决策树出发，通过 添加新的决策结点来改善原来的决策树，直至决策树能正确地将训练样本分类为 止。由于c l s 算法中并未明确给出测试属性的选取标准，它具有很大的改进空 问。 此后的决策树算法，按照在内部结点的判断方法上，主要可以分为单变量决 策树和多变匮决策树。 2 1 1 单变量决策树 长期以来，对决策树方法的研究一直集中在单变量决策树上。单变量决策树 在内部结点的测试时只使用一种属性，采用贪心法，试图在某个度量值上达到局 部最优。采用这种方法得到的决策树，通常与人的思维方式一致，因此易_ 丁理解。 但如何选择最优属性是一个n p h a r d 问题，目前多采用信息学理论的度量值， 如信息增益、增益系数等。著名的单变量算法有 d 3 及其后续版本c 4 5 等。 l 、i d 3 算法 1 9 7 9 年q u i n l a n 提出了以信息增益( i n f o r m a t i o n g a i n ) 为度量值，选取能够 最好地将训练集分类的测试届性的i d 3 算法f 2 ”。在i d 3 算法中，决策树的德个 决策结点使用信息增益度量选择测试属性。这种度量称作属性选择度量或分裂的 优良性度量，即选择具有最高信息增益( 或最大熵) 的属性作为当前结点的测试 属性。该属性使得对结果划分中的样本分类所需的信息量最小。这种测试属性的 中田科学投术人学硕i 学位论义第2 章演化决镱树方法研究 选取方法使得对个对象进行分类所需的期望测试数目达到最小，并确保找到一 棵简单的( 但不必是最简单的) 决策树。该算法的计算时问是例子个数、属性个 数、结点个数之积的线性函数。 i d 3 算法的优点在于选择属性时利刚了信息增益的概念算法的基础理论清 晰，使得算法较简单，学习能力强。缺点在于信息增益的计算依赖于属性耿值数 目较多的属性，这样不太合理，一种简单的办法是对属性进行分解。i d 3 算法在 构造决策树时，每个结点仪含一个属性，属性问的相关性强调不够。i d 3 算法对 噪卢比较敏感。另外，当训练集增加时，i d 3 决策树会随之变化。在建树过程中， 各属性的信息增益会随样本的增加而改变，从而使决策树也发生变化，这对在线 学习( 即训练样本不断增加的情况) 是很不方便的。 2 、c 4 5 算法 q u i n l a n 于1 9 9 3 年提出了c 45 算法t 2 ”，它既是i d 3 算法的后继版本，也成 为以后诸多决策树算法的基础。在应用于单机的内存驻留决策树算法中，c 4 5 不仅分类准确度高，而且速度最快。 c 4 5 引入了增益系数( g a i nr a t i o ) 来克服i d 3 算法中的最大增益偏向于多 值属性的特点。此外c 4 5 算法使用一种悲观估计来补偿由于i d 3 算法对分类器 的准确率的乐观估计造成的偏差。换句话说，c 4 5 算法使用一组独立于训练样 本的测试样本来评估分类器的准确性，而不像i d 3 算法直接使用训练样本进行评 估。最为重要的是，c 4 5 算法克服了i d 3 算法只能处理离散型属性的缺点，对 连续型属性、属性值存在空缺等情况也能处理。另外，对剪枝步骤，c 4 5 也有 了较为成熟的方法。 3 、其它算法 无论是i d 3 算法还是c 4 5 算法，对于相对较小的数据集还是很有效的，但 对于些大型数据库进行数据挖掘时其有效性和可伸缩性就出现了不足。这是 凶为i d 3 和c 4 5 都是一种内存驻留算法，限制了算法的可伸缩性和效率。在这 种情况下，产生了对大型数据集进行决策树分类的算法s l i q t 2 7 增口s p r i n t 2 8 1 。 它们使用预排序技术，对非常大而不能装入内存的驻留磁盘的数据进行预排序， j f ：定义了新的驻留内存的数据结构，以利于决策树的构造。此外，还有将多维数 掘立乃体方法和而向属性的归纳( a o i ) 与决策树算法集成，刘大型数据库进行 交互的多层次挖掘的方法等。 4 、单变量决策树算法的不足 中国科学技术大学顾l 学位论义帮2 帝演化决策树方洼研究 单变鞋决策树算法在迸行决策结点测试时，般只测试单个属性。由于这棚 当于使用平行l 丁| 属性空阳j 的某个轴的超平m i 进行划分，冈此单变量决策树也被称 为j 下交决策树。这种单变量的测试很容易进行，结果也易于被领域专家所理解， 因此得到了广泛的应用。但当训i 练样本更适合用不与属性轴平行的超平面进行划 分时，单变量决策树算法就可能会产生非常复杂的并且不准确的决策树。出此， 产生了多变量决策树算法。 2 1 2 多变量决策树 上节指出，当训练样本的属性空恻不适合使用平行予属性轴的超平面划分时 ( 如图2 一l 所示) ，单变量决策树将不再适用。顾名恩义，多变量决策树与单变 量决策树不同，它在进行结点测试时，同时使用多个属性，即使用不与属性轴平 行的超平面进行划分，因此，也被称为倾斜决策树。在一些情况下，多变量决策 树算法会产生规模更小且更精确的决策树。但多变量决策树算法的研究应用并不 如单变量决策树算法那样广泛，这有两个方面的原因。一是多变量决策捌算法的 构造过程比较复杂，不易理解；二是多变量决策树往往需要更多的计算资源。 u 0 1 uz】 口4 0b0 6 口， obo 1 图2 - 1 更适合多变量决策树的属性空间 多变量决策树算法可分为线性联合算法和非线性联合算法。 1 、线性联合算法 线性联合算法的目标是找出属性变鞋的多元一次式，其过程包括两方面的内 1 f 中周科学技术人学硕i ：学位论文第2 帝演化决镶树方法研究 容：确定变摄的系数和选择属性。由于扩展属性集可能很大，这类算法一般采用 启发式方法限制搜索空问，找出相对最佳的扩展属性。较典型的算法有c a r t - l c 和o c l 等。 c a r t - l c _ 算法 b r e i m a n 提山的c a r t - l c l 2 9 1 是c a r t 算法的扩展，用米构造倾斜决策树。 该算法使用爬山搜索方法优化系数。c a r t - l c 存以f 缺点：i 、c a r t - l c 是完 仝决定性的，没有机制来避免局部最优：2 、c a r t - l c 有时会做出不纯度增加的 调整，并且在决策树任意结点处花费的时叫没有一巴界。c a r t - l c 仅当干扰变化 不大于s 时爿+ 会停止，但是刁i 纯度可能会增加或减少，因此该算法在某一结j i i 处 可能花费较长时阳j 。 l m d t 线性机器决策树( l i n e a rm a c h i n ed e c i s i o nt r e e ) 【3 0 1 是感知树方法的继承。 每棵l m d t 决策树的内部结点都是一个线性机器。在每个结点处，训练算法重 复地提供例予，直到线性机器收敛。因为是否收敛是不可证明的，l m d t 使用启 发式方法决定何时结点稳定。为了即使训练样本不是线性独立时结点也是稳定 的，l m d t 采用了热训练方法( t h e r m a lt r a i n i n g ) ，它类似于模拟退火方法。 s a d t 模拟退火决策树( s i m u l a t e d a n n e a l i n g o f d e c i s i o nt r e e s ) 3 q 使用模拟退火的 方法优化超平面的系数。s a d t 首先把超平面放在个规范的位置，再用个小 的随机数交互地扰动系数。最初，当温度参数很高时，s a d t 几乎接受超平面的 所有扰动：但当温度参数降低时，s a d t 只接受那些会提高超平面性能的系数。 尽管s a d t 采用随机技术有效地避免了局部最优，但损失了一些效率，有时为 了在个结点处结束退火，需要考虑成千上万个超平面。 o c l o c l l 3 2 i 扩展了c a r t 和s a d t 方法，它首先使用确定的策略单个地干扰联 合属性的每个系数，为了避免局部最优，采用随机干扰系数的方法重复这个过程， 它可以在多项式时间内找出相对最佳的系数。 2 、非线性联合算法 非线性联合算法的目标是找出属性变量的多冗多次式，它不仅涉及变量的系 数和个数还要考虑变量的幂次数，因此构造起来更加复杂。i t t n e r 和s c h l o s s e r 提出了一种构造非线性决策树的方法f 3 3 | 。首先构造出商次方的新属性( 幽原始 巾同科学技术人学硕j j 学位论义笫2 章演化决策树方法研究 榭性变量通过相乘、乘方等方式构成) ，并把它们看成是描述实例的属性，然后 再使用线性联合算法找出最优属性。 3 、多变量决策树的不足 使用多变量方法构造出来的决策树一般规模较小，并能体现出属性问的相关 性精度椰对单变量决策树较高，同时能够有效地克服了树复制问题。但多变量 决策树也存在突出的问题，即构造算法复杂，速度较慢，同时不易理解。这类筇 法适合于描述事例的属性叫相关性较强，以连续型属性为主的数掘集。 2 1 3 传统决策树方法的不足 当问题规模较大时，传统决策树的搜索空问过大。h y a f i l 证明1 3 4 i ，构造棵 壤优的- - - x 决策树是n p h a r d 的。g o o d r i c h 通过研究得出结论( 3 s 】。甚至在三维 时，构造棵最优的倾斜决策树也是一个n p h a r d 问题。因此，无论足单变量 决策树还是多变量决策树它们进行搜索时，都采用了局部搜索策略，无法保汪 找到的结果是全局最优的。 2 。2 演化决策树方法的研究 由于传统决策树算法采用贪心思想，容易陷入局部最优，研究者们考虑使用 新的解决思路。演化算法基于其自身的特点，逐渐与决策树算法相集合，j 髟成了 演化决策树算法。演化决策树算法是一种将演化框架与传统的决策树算法相结合 的算法。它主要是利用演化算法全局搜索的优点为决策树算法服务。 图2 2 表示了一种树型结构的演化决策树的演化过程。 瓴q ，拿毒，璺 ，一、：、匕二， 7 | 4t 。碍 图2 - 2 演化决策树的演化过程 目前比较有代表性的演化决策树算法有q i a n g f uz h a o 等提出的演化b d t 算 法【3 6 1 和j a n d r a s 等基于m e p 编码方式的m e p d t i 算法【2 】。下面我们分别对这几 r 】闲科学技术人学硕f 。学位论文筘2 帝演化决镱树方法研究 种算法加以详纲介绍和分析。 2 2 1 演化b d t 算法 q i a n g f uz h a o 将二叉决策树( b d t ) 的每个结点定义为一个7 元组： n o d e = t ，l a b e l ，p ，l ，r ，c ，s i z e 其中，t 足结点序号( 根结点的t = 0 ) ；l a b e l 是叶结点的类别；p 表示父结点； l 和r 分别表示左右子结点；c 为属性测试信息，c o 】n 为属性的序号，c 1 卜a 为属性的阈值，通过表达式属性。 a 的真假决定访问左结点或者右结点；s i z e 表示以该结点为子树的结点数，代表子树的舰模。 种群中的缚个个体都足一裸b d t ，个体使用大于i 的s i z e 进行初始化。 适应度函数定义为 f i t n e s s = n c o r r c c l n t oe “ 其中，n 。一。表示正确分类的样本数目，n 。1 表示总的训练样本数。 演化b d t 算法的交叉和变异算子均使用标准遗传算法的遗传算子并加入 了一种删除算予，一定的概率删除某棵子树。另外，选择算子的设计除了适应度 函数外，还考虑了树的s i z e 信息，倾向于选择那些s i z e 较小的个体。 演化b d t 算法通过简单的模式识别实验证明了其有效性，但还没有进行过 有效的分类实验的检验。同时，它的设计思想还足比较简单，除了分类准确率外， 只考虑到树的规模的因素。因此，还有很大的改进空间。 2 2 2m e p d t i 算法 m e p d t i 算法采用了m e p 编码方式”7 1 1 3 8 1 。m e p 使用