（计算机软件与理论专业论文）基于决策树的数据挖掘算法及在贷款风险分类的应用.pdf

基于决策树的数据挖掘算法及在贷款风险分类的应用 摘要 专业：计算机软件与理论 申请人：朱华鑫 导师：金京林副教授 数据库蕴含着大量信息，可以用来作出各种智能的商务决策。作为新兴的知 识发现技术数据挖掘以及辅助决策工具决策支持系统已越来越受到人 们的关注，它们为人们从大量数据中获取感兴趣的、有用的信息提供了便捷之道。 随着数据挖掘技术以及人工智能技术的不断发展，智能决策技术在许多领域 得到研究和应用，并发挥着越来越重要的作用。本文就是基于数据挖掘和决策支 持系统领域的相关知识和技术，针对商业银行的信贷业务中的关键环节贷款 风险分类，进行了理论和方法上的研究。 在数据挖掘的众多功能中，分类是其中一项非常重要的任务，它通过找出描 述并区分数据类或概念的模型，以便能够使用模型预测类标号未知的对象类。决 策树算法是以实例为基础的归纳学习算法，以其易于提取显式规则、计算量相对 较小、可以显示重要的决策属性和较高的分类准确率等优点而得到广泛的应用。 据统计，目前决策树算法是利用最广泛的数据挖掘算法之一。 基于银行的i t 现状，笔者将改进的决策树算法应用于银行智能决策系统的 信贷分析系统，用决策树的技术来实现银行贷款风险分类，以提高银行降低不良 贷款比例的能力。为此，本文主要进行了以下几个方面的工作： 1 、数据挖掘基本知识的深入研究及探讨。介绍了数据挖掘技术的基本理论， 数据挖掘基本概念、功能和过程，并对数据挖掘常用技术进行了分析。 2 、决策树技术的分析与研究。通过第三章，对c 4 5 算法及其基本思想进行 了归纳、分析和研究，分析了其优缺点，并引入了粒子群算法来改进c 4 5 算法。 3 针对传统决策支持系统的局限性，介绍了基于数据仓库的决策支持系统， 并分析了数据挖掘技术在决策支持系统中的地位与作用。并提出了银行智能决策 系统总体解决方案。 4 、介绍了决策树技术在银行贷款风险分类中的应用。利用改进的c 4 5 算 法生成决簧树模型，并由此产生了分类规则。 关键词：数据挖掘，决策树，粒子群算法，贷款风险分类 i i a b s t r a c t d a t aminin ga l g o rlt h mb a s e do n t h ed e cis10 nt r e ea n dit sa p p l ic a t10 n inl o a nris kc l a s s ific a tio n m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：z h uh u a x i n s u p e r v i s o r ：j i nj i n g l i n t h ed a t a b a s ei sc o n t a i n i n gt h em a s s i v ei n f o r m a t i o nt h a tc a nb eu s e dt om a k e s m a r tb u s i n e s sd e c i s i o n s a sar e s u l t ，m o r ea n dm o r ep e o p l ef o c u sd a t am i n i n ga n d d e c i s i o ns u p p o r ts y s t e m ，a sab u r g e o n i n gk n o w l e d g ed i s c o v e r yt e c h n o l o g ya n da n a s s i s t a n td e c i s i o n - m a k i n gt o o lr e s p e c t i v e l y a l o n gw i t ht h ec o n t i n u a ld e v e l o p m e n to fd a t am i n i n gt e c h n o l o g ya n d a r t i f i c i a l i n t e l l i g e n c et e c h n o l o g y , i n t e l l i g e n td e c i s i o n m a k i n gt e c h n o l o g yh a sb e e n i n v e s t i g a t e da n da p p l i e dt om a n yf i e l d s ，a n dp l a y sam o r ea n dm o r ei m p o r t a n tr o l e o nt h eb a s i so fc o r r e l a t i v e k n o w l e d g e a n dt e c h n o l o g yi na r t i f i c i a li n t e l l i g e n c e a n dd e c i s i o n m a k i n gs y s t e md o m a i n ，t h i sp a p e rc a r r yt h o u g ht h es t u d yo f t h e o r ya n d m e a n sa i m i n ga tl o a nr i s kc l a s s i f i c a t i o n ，w h i c hi st h ek e yl i n ko fc r e d i to p e r a t i o n i n c o m m e r c i a lb a n k i nd a t am i n i n g sn u m e r o u sf u n c t i o n s ，t h ec l a s s i f i c a t i o ni sa v e r yv i t a ld u t y , a n di td i s c o v e r s 、d e s c r i b e sa n dd i f f e r e n t i a t e st h ed a t ac l a s so rt h ec o n c e p tm o d e l ，i n o r d e rt ou s et h em o d e lf o r e c a s tc l a s sm a r k i n gu n k n o w no b j e c tc l a s s t h ed e c i s i o n t r e ec l a s s i f i c a t i o na l g o r i t h mb a s e so nt h ei n s t a n c e sa m o n g s tt h e s ei sw i d e l yu s e dw i t h i i i i t s a d v a n t a g e s o fc o n v e n i e n c ef o rg e t t i n ga p p a r e n tr u l e s ，s m a l l e rc a l c u l a t i o n w o r k l o a d ，s h o w i n gi m p o r t a n t d e c i s i o nc h a r a c t e r i s t i c s ，h i g h e rc l a s s i f i c a t i o n c o r r e c t n e s se t c d e c i s i o nt r e ea l g o r i t h mi sc u r r e n t l yo n eo ft h em o s tp o p u l a ri nd a t a m i n i n ga l g o r i t h m sa c c o r d i n g t or e l a t e ds t a t i s t i c s b a s e do nt h ei tr e s e a r c hb a c k g r o u n do ft h eb a n k ，t h ei m p r o v e dd e c i s i o n t r e ea l g o r i t h mw a sa p p l i e di nt h eb a n ki n t e l l i g e n c ed e c i s i o ns y s t e m sc r e d i ta n a l y s i s s y s t e m ，a n di t r e a l i z e dt h eb a n kl o a nc l a s s i f i c a t i o no fr i s kw i t hd e c i s i o nt r e e s t e c h n o l o g ya n de n h a n c e dt h eb a n kt or e d u c e t h en o n p e r f o r m i n gl o a np r o p o r t i o n a b i l i t y t h e r e f o r e ，t h i sa r t i c l eh a sm a i n l yc a r r i e do nt h ef o l l o w i n gs e v e r a la s p e c t w o r k s ： 1 t h er e s e a r c ha n dd i s c u s s i n go ft h eb a s i ck n o w l e d g eo fd a t am i n i n g i n t r o d u c e dt h ed a t am i n i n gt e c h n o l o g y se l e m e n t a r yt h e o r y , t h ed a t am i n i n gb a s i c c o n c e p t ，t h ef u n c t i o na n dt h ep r o c e s s ，a n dh a v ec a r r i e do nt h ea n a l y s i st ot h ed a t a m i n i n gc o m m o n l yu s e dt e c h n o l o g y 2 t h et e c h n o l o g yo fd e c i s i o nt r e ei sd i s c u s s e dd e m i l e d i nt h et h i r d c h a p t e r , w eh a v ec a r r i e do nt h ei n d u c t i o n ，t h ea n a l y s i sa n dt h er e s e a r c ht ot h ec 4 5 a l g o r i t h ma n dt h eb a s i cp h i l o s o p h y , a n da n a l y z e di t sg o o da n db a dp o i n t s a n dt h e d a t am i n i n gc o m m o n l yu s e dt e c h n o l o g yh a sa n a l y z e d 3 i nv i e w o ft h et r a d i t i o nd e c i s i o n s u p p o r ts y s t e m s l i m i t a t i o n ，w e i n t r o d u c e dt h ed e c i s i o ns u p p o r ts y s t e mb a s e do nd a t aw a r e h o u s e ，a n da n a l y z e dt h e d a t am i n i n gt e c h n o l o g yi nd e c i s i o ns u p p o r ts y s t e m ss t a t u sa n dt h ef u n c t i o n a n dt h e b a n ki n t e l l i g e n c ed e c i s i o ns y s t e mo v e r a l ls o l u t i o ni sp r o p o s e d 4 i n t r o d u c e dt h ed e c i s i o nt r e et e c h n o l o g yi nt h eb a n kl o a nc l a s s i f i c a t i o no f r i s ka p p l i c a t i o n u s i n gi m p r o v e m e n tc 4 5a l g o r i t h mp r o d u c t i o nd e c i s i o nt r e em o d e l ， w eh a v eh a dt h ec l a s s i f y i n gr u l ef r o mt h i s k e yw o r d s ：d a t am i n i n g ，d e c i s i o nt r e e ，p a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m ，l o a n r i s kc l a s s i f i c a t i o n i v 华南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确的方式标明。 本人完全意识到此声明的法律结果由本人承担。 论文作者签名：李哮瓮、 日期：矽好年历月4e l 学位论文使用授权声明 本人完全了解华南师范大学有关收集、保留和使用学位论文的规 定，即：研究生在校攻读学位期间论文工作的知识产权单位属华南师 范大学。学校有权保留并向国家主管部门或其指定机构送交论文的电 子版和纸质版，允许学位论文被检索、查阅和借阅。学校可以公布学 位论文的全部或部分内容，可以允许采用影印、缩印、数字化或其他 复制手段保存、汇编学位论文。( 保密的论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密范围，在年后解密适用 本授权书。非保密论文注释：本学位论文不属于保密范围，适用本授权 书。 导师签名： 令务犯 日期：必年厂月垆日 1 1 研究背景 第1 章绪论 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的 数据越来越多，迅速增长的数据背后隐藏着许多重要的信息。人们希望能够对其 进行更高层次的分析，以便更好的利用这些数据。目前的数据库系统可以高效地 实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，无 法根据现有的数据预测未来的发展趋势，缺乏挖掘数据背后隐藏知识的手段，导 致了“数据爆炸但知识贫乏 的现象。人们开始考虑如何从海量的信息中发现有 用的知识，提高信息的利用率。面对这一挑战，数据挖掘( d a t am i n i n g 简称d m ) 和知识发现技术应运而生，并得以蓬勃发展，越来越显示出其强大的生命力。 越来越多的计算机公司开始重视数据挖掘的开发应用，m e t a g r o u p 曾做出 这样的评论：“全球重要的企业、组织会发现，2 1 世纪数据挖掘技术将是他们商 业成功与否的至关重要的影响因素 。i b m 和微软都成立了相应的研究中心进行 这方面的工作，其中i b m 公司还发布了基于标准的数据挖掘技术i b md b 2 智能挖掘器积分服务，可用于个性化的解决方案。两大统计软件公司s a s 和s p s s 也推出了各自的数据挖掘工具e n t e r p r i s em i n e r 和c l e m e n t i n e 。比较有影响的数 据挖掘系统还有s g i 公司的s e t m i n e r , s y b a s e 公司的w a r e h o u s es t u d i o r u l e q u e s t r e s e a r c h 公司的s e e s 、以及c o v e r s t o r y , e x p l o r a 。k n o w l e d g ed i s c o v e r y w o r k b e n c h d b m i n e r , q u e s t 等。这些数据挖掘商业软件工具不断产生和完善，同 时面向领域的数据挖掘技术应用以及数据挖据系统的开发不断地为各行业提供 各种成功的解决方案。其用户主要集中在大型银行、保险公司、电信公司和销售 业。 数据库中蕴含的大量信息，可以用来作出各种智能的商务决策。在数据挖掘 的众多功能中，分类是其中一项非常重要的任务，它通过找出描述并区分数据类 或概念的模型，以便能够使用模型预测类标号未知的对象类。 目前，针对分类问题已有若干不同领域方法的算法，其中从机器学习中引出 的决策树方法是一种较为通用并深入研究的分类函数逼近法。它是一种常用于预 测模型的算法，它通过将大量数据有目的的分类，从中找到一些具有价值的、潜 在的信息。由于基于决策树的分类模型方法结构简单，便于人们理解效率高，适 合大数据量，通常不需要训练数据外的知识等优点被人们广泛使用。目前，已有 多种决策树算法，如c l s ，i d 3 ，c h a i d ，c a r t , f a c t , s l i q ，s p r i n t 等。 可以说，把数据挖掘技术应用于商业智能决策系统，已经成为当前计算机技 术应用研究热点之一。 1 2 本文的研究内容 目前，随着中国银行业改革的急剧深化，银行企业将面临一个充满激烈竞争 的市场，如何加速企业模式的更新，更深地挖掘内在的资源以及有效提升对市场 的驾驭能力? 最根本最有效的途径是深化银行信息化建设的进程。 商业智能应用系统采用当今最先进的信息技术和数学方法，特别是数据仓库 和数据挖掘技术，对银行企业的内部和外部数据进行多层次、多角度、全方位的 分析和挖掘，揭示金融市场销的内在规律。科学地、快速地指出存在的问题、隐 患并能发现对于企业至关重要的变化趋势，形成极具决策价值的战略信息。 本文介绍数据挖掘技术特别是决策树分类技术，对最常用的决策树算法i d 3 和c 4 5 算法u 1 作了简单的介绍。同时，结合人工智能的粒子群算法思想，采用 自适应变异的粒子群优化算法( a m p s o ) 对决策树算法c 4 5 算法进行了改进。 针对中国商业银行的i t 现状，提出了建立基于数据仓库、o l a p 技术和d a t a m i n i n g 技术的银行智能决策系统的设计方案，如图1 1 。 由于我国直到2 0 0 2 年五级贷款分类在中国银行业才得以全面实施，而国外 对贷款分类的研究已有一定时间，但由于国内与国外在基本的贷款分类体系上存 在较大差异，因此截止目前在国内，银行信贷管理决策过程的真正应用智能化方 面还处于一项实践技术上的空白，贷款决策过程还基本由人脑来实现。本文尝试 使用决策树的数据挖掘技术对银行贷款风险分类，为银行信贷管理提供决策支持 3 2 1 幸1 霉j k t 冈毋、 警：受葺 一生 黛蔗叠渔。翼? i 聚类il 决策树il 预测模型i 一 、 峨幽固、 多维分析ii 报表、e i si i即席查询i 回国固够 曩熏璺恻 a 、 转换、清洗、装 u 卜 载 霹囊 l ，一一芦_ ，ji 抽取jl 躺数圳固固国 图1 1 商业智能解决方案基础架构 1 3 本文的组织结构 全文的组织结构安排如下： 第1 章绪论。论述选题的研究背景、意义和内容。 第2 章数据挖掘与决策树分类方法。介绍数据挖掘技术的基本理论，数据挖 掘基本概念、功能和过程。然后介绍了数据挖掘的分类技术概念，着重介绍了决 策树分类技术，总结了评估分类模型的尺度和方法。 第3 章决策树算法研究。对决策树算法c 4 5 算法作了比较详尽的论述，分 析了它的优缺点，并引入了粒子群算法来改进c 4 5 算法。 第4 章数据挖掘在决策支持系统中的应用。针对传统决策支持系统的局限 性，介绍了基于数据仓库的决策支持系统，并分析了数据挖掘技术在决策支持系 统中的地位与作用。 第5 章银行智能决策系统总体解决方案。根据中国商业银行的i t 现状，提 出了银行智能决策系统总体解决方案，并指出这是一个“整体规划，分阶段实施， 循序渐进”不断循环、反馈而使系统不断增长与完善的过程。 第6 章决策树技术在银行贷款风险分类中的设计与实现。主要介绍银行决策 支持系统中的信贷分析系统，用决策树的技术来实现银行贷款风险分类。 第7 章总结与展望。总结已做的研究工作，展望未来，提出了今后的工作方 向。 最后是参考文献，致谢。 4 第2 章数据挖掘与决策树分类方法 2 1 数据挖掘理论基础 近年来出现的数据挖掘技术之所以被目前认为具有令人兴奋的研究前景，是 因为它能够获得广泛的应用。如用于支持企业关键性决策，市场策略的制定等等。 面对汹涌而来的大量数据，企业对数据挖掘应用形成极大的需求，将使这一技术 迅速得到发展和完善。国内外，在大型商业、金融业、保险业、民航等大型企业 都开始得到应用。 2 1 1 数据挖掘的定义 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用 数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识 的过程。 长期以来，在知识发现领域，“知识发现”与“数据挖掘”这两个术语的范 畴和使用界限一直不很清晰，直到1 9 9 6 年的k d d 国际会议上，f a y y d 等对这两 个术语进行了定义：k d d 是从数据中辨别有效的、新颖的、潜在有用的、最终可理 解的模式的过程，指的是数据库中知识发现的全过程，而数据挖掘只是k d d 过程 中的一个特定步骤，它一般分为五个阶段：选择目标数据、预处理数据、转化数 据、进行数据挖掘以提取模式和关系、解释并评价发现的结构，如图2 1 所示曲。 i- iiil ii k 一数据准备沫- 擞据挖掘+ k 结果评价一 ii 图2 1 知识发现的步骤 5 从图中可以看出，数据挖掘只是k d d 中的一个步骤，它主要是利用某些特定 的知识发现算法，在一定的运算效率的限制内，从数据中发现有关的知识。目前 大多数的研究都集中在数据挖掘算法和应用上，人们往往不严格区分数据挖掘和 数据库中的知识发现，把两者混淆使用。一般在科研领域中称为k d d ，而在工程 领域则称为数据挖掘。 人们把原始数据看作是形成知识的源泉，就像从矿石中采矿一样。原始数据 可以是结构化的，如关系数据库中的数据，也可以是半结构化，如文本、图形、 图像数据，甚至是分布在网络上的异构数据。发现知识的方法可以是数学的，也 可以是非数学的；可以是演绎的，也可以是归纳的。发现了的知识可以被用于信 息管理、查询优化、决策支持、过程控制等，还可以用于数据自身的维护。因此， 数据挖掘是一门交叉型学科，涉及数据库、数理统计、人工智能、数据可视化技 术、机器学习、神经网络、模式识别、归纳推理、高性能并行等多个领域，其研 究内容十分广泛口1 。 2 1 2 数据挖掘的分类 从不同的视角看，数据挖掘技术有以下几种分类方法怕。： 1 、根据采用的挖掘技术分类 根据所采用的挖掘技术，数据挖掘可以分为：规则归纳、决策树、神经网络、 遗传算法、可视化等。 2 、根据发现知识的种类分类 这种分类就是根据数据挖掘任务或数据挖掘功能进行分类，可以分为：概化 知识、关联知识、分类和聚类知识、分类和聚类知识、预测型知识。 3 、根据挖掘的数据库分类 数据挖掘可以在数据库、数据仓库或其他类型的信息库上进行。数据库根据 基于的数据模型，可以分为关系数据库、面向对象数据库、对象一关系数据库、 演绎数据库等。根据面向的应用领域，可以分为事务数据库、空间数据库、时间 数据库、多媒体数据库等。 不同的数据库有不同的特征，数据挖掘采用的技术，发现的知识以及挖掘的 6 难易可能因此而异。此外，数据仓库由于可以将多个站点的异种数据源数据在单 个站点以统一模式存储，并提供从不同角度、不同层次汇总、分析数据的联机分 析处理，成为目前的数据库研究的热点，其上的数据挖掘也被广泛研究。 2 1 3 数据挖掘的过程 数据挖掘的过程可粗略地分为确定挖掘对象、数据收集和预处理、数据挖掘 算法执行以及结果的解释和评估。如图2 2 所示，整个挖掘过程是一个不断反馈 的过程，如果用户对挖掘结果评估不满意，需要重复先前的过程，甚至重新开始。 图2 2 数据挖掘过程示意图 1 确定挖掘对象 清晰地定义数据挖掘的对象，认清数据挖掘的目的是数据挖掘的重要一 步。挖掘的最后结构是不可预测的，但要探索的问题应是有预见的，为了数据 挖掘而数据挖掘则带有盲目性，是不会成功的。 2 数据准备 ( 1 ) 数据的选择 搜索所有与业务对象有关的内部和外部数据信息，并从中选择出适用于数 据挖掘应用的数据。 ( 2 ) 数据的预处理 研究数据的质量，为进一步的分析作准备。并确定将要进行的挖掘操作的 类型。 ( 3 ) 数据的转换 将数据转换成一个分析模型。这个分析模型是针对挖掘算法建立的，建 立一个真正适合挖掘算法的分析模型是数据挖掘成功的关键。 3 、挖掘知识和信息 对知识和信息的挖掘是数据挖掘技术的核心，主要根据系统要实现的功能 7 和任务来确定挖掘的类型，并选择合适的挖掘技术及算法，在净化和转换过的 数据集上进行反复迭代的搜索，从中产生一个特定的感兴趣的模式或一个特定 的数据集。 4 、模式的解释和评价 对数据挖掘发现的模式或数据集进行解释和评价，过滤出有用的知识。包 括消除无关的、多余的模式，过滤出要呈现给用户的信息：利用可视化技术将 有意义的模式以图形或逻辑可视化的形式表示，转化成用户可理解的语言。但 数据挖掘阶段发现出的模式也可能不满足用户要求，这时需要整个发现过程回 退到前一阶段，重新进行。 2 2 决策树分类技术 人类认识事物的过程是从分类开始的，分类能力是人类智能的基础，在从大 规模数据库获得知识的过程中必然涉及到数据的分类问题。分类是数据挖掘中的 一项非常重要的任务，目前在商业领域应用的最多，也一直是k d d 领域的研究点 之一。分类的主要目标是提出一个分类模型或分类器，所得的这个分类模型能够 将数据库中的数据项映射到给定类别中的某一个。 2 2 1 分类的概念与分类模型准确性的评估 1 分类概念 分类和聚类不同，聚类是在特定的类标示下寻求新元素属于哪个类，而分类 是已知现存的类别，要建立类别的描述规则，并对新例的观察值判别归类。数据 分类是数据挖掘中的一个重要问题，是一种有效的k d d 分析方法。数据分类通 过分析训练集中的数据，对类建立分类模型，然后利用这个分类模型来预测类标 记未知的对象类。在机器学习中聚类被称为无指导学习，分类被称为有指导学习 c 6 】 o 分类的目的是构建和利用分类函数或分类模型( 分类器) ，该模型能把数据库 中的数据映射到给定类别中的某一个。而本文研究的决策树算法是通过构造一棵 决策树分类器，并根据决策树生成的规则对新的实例进行分类。为了更好的理解 8 分类的概念，下面给出分类器的一般定义。 定义2 1 给出一个数据库d = t 。，t 2 ，t 。) 和一组类c = c l ，c ：，c m ， 分类问题是去确定一个f ：d c ，每个分组t ；被分配到一个类中。一个类c j 包含 映射到该类中的所有元组，即c j = t ilf ( t i ) = c j ，l i n ，而且t i d 1 。 一般来说分类分为建模和分类两个步骤。如图2 3 所示： 图2 3 分类的两个步骤 第一步：建模，构建分类器，找到合适的训练函数h ：f ( x ) 一c 的表示模型来 描述预定的数据类集或概念集。构造的主要方法有决策树、贝叶斯网、神经网络 等。 第二步：使用上一步训练完成的函数模型预测数据的类别，或利用该函数模 型，对数据集中的每一类别进行描述，形成分类预测。 2 分类模型准确性的评估 分类器评价或比较尺度主要有三种： 预测准确度预测准确度是用得最多的一种比较尺度，特别是对于预测型分 类任务，目前公认的方法是分层交叉验证法。 计算复杂度计算复杂度依赖于具体的实现细节和硬件环境，在数据挖掘 中，由于操作对象是巨量的数据库，因此空间和时间的复杂度问题将是非常重要 的一个环节。 模型描述的简洁度对于描述型的分类任务，模型描述越简洁越受欢迎；例 如，采用规则表示的分类器构造法就比较简单，而神经网络方法产生的结果就难 9 以理解。 2 2 2 决策树分类技术 决策树( d e c i s i o nt r e e ) 是用于分类和预测的主要技术，决策树学习是以 实例为基础的归纳学习算法，通过一组无次序、无规则的实例中推理出决策树。 决策树是一个类似于流程图的树结构。一般讲，一个决策树有一个根节点， 一组内部节点和一些叶节点组成。其中每个内部节点表示在一个属性上的测试， 每个分枝代表一个测试输出，而每个叶节点代表类或类分布，树的最顶层节点是 根节点。更明确的说，决策树是通过根节点到叶节点的顺序对实例进行分类，其 中，每个节点代表一个属性，每个分枝代表它所连接的上节点在其属性上的可能 取值。在决策树的基本结构图中，中间节点常用矩形表示，叶子节点用椭圆形表 示。 用决策树进行分类主要包含两步。第一步是利用训练数据集构造一棵决策树 模型。这个过程实际上是一个从数据中获取知识，进行机器学习的过程。第二步 是利用已经生成的决策树模型对未知输入的数据样本进行分类。对输入的记录， 从根节点依次测试记录的属性值，直到到达某个叶子节点，从而找到该记录所在 的类。 如图2 3 所示的决策树是判断顾客是否购买计算机的分类模型，根节点表示 在属性年龄上的测试，“3 0 4 0 ”分支表示测试输出“年龄- - 3 0 ，- - - 4 0 ”之间，该 分支的叶节点表示顾客购买计算机，即当顾客的年龄在“3 0 ，- - 4 0 之间时，他购 买计算机。通过为从根节点到叶节点的每条路径创建一条规则，决策树可以方便 地转换为分类规则，利用分类规则可以对新对象进行分类，所以决策树分类的关 键是利用决策树算法建立决策树。 1 0 图2 3 判断顾客是否购买计算机的决策树分类模型 2 2 3 决策树生成 1 决策树建立的常规算法及描述 决策树分类算法通过分析训练数据集递归地建立决策树，其基本思想是：首 先，在整个训练数据集s 、所有描述属性a 。，a ：，a m 上递归地建立决策树。即 将s 作为根节点；如果s 中的记录属于同一类别，则将s 作为叶节点并用其中的 类标号标识，决策树建立完成；否则在s 上计算当a k ( 1 k m ) 时类标属性c 的信息增益g ( c ，a k ) ，选择信息增益最大的a i 作为根节点的测试属性；如果 a i 的取值个数为v ( 取值记为a 。，a z ，a v ) ，则a i 将s 划分为v 个子集s 。， s 2 ，s ，( s j ( 1 j v ) ( 为s 中a i = 的记录集合) ，同时根节点产生v 个分支 与之对应。其次，分别在训练数据子集s t ，s z ，s ，剩余描述属性a l ，一，a t 山 a t + l ，a i 上采用相同方法递归地建立决策树子树。 当决策树分类算法递归地建立决策树时，某节点对应的训练数据( 子) 集由 整个训练数据集中满足从根节点到该节点路径上所有属性测试的训练样本组成。 某节点对应的( 剩余) 描述属性是去除从根节点到该节点路径上所有已选描述属 性后的描述属性。也就是决策树( 予树) 的建立是局部于相应的训练数据( 子) 集，( 剩余) 描述属性，同一层内部节点选择的测试属性可能相同也可能不同。 此外，可能出现如下情况，也需要停止建立决策树( 子树) 地递归过程。 1 ) 某节点对应地训练数据( 子) 集为空。此时，该节点作为叶节点并用父 节点中占多数的记录类别标识。 2 ) 某节点没有对应的( 剩余) 描述属性。此时，该节点作为叶节点并用该 节点占多数地记录类别标识。 建立决策树的算法如下： 算法：g e n e r a t e d e c i s i o n t r e e 由给定的训练数据产生一棵判定树。 输入：训练样本s a m p l e s ，由离散值属性表示；候选属性的集合 a t t r i b u t e lis t 。 输出：一棵判定树。 方法： ( 1 ) 创建节点n ； ( 2 ) i fs a m p l e s 都在同一个类ct h e n ( 3 ) 返回n 作为叶节点，以类c 标记； ( 4 ) i fa t t r i b u t el i s t 为空，t h e n ( 5 ) 返回n 作为叶节点，标记为s a m p l e s 中最普通的类； ( 6 ) 选择a t t r i b u t e l i s t 中具有最高信息增益的属性t e s t _ a t t r i b u t e ： 信息增益的解释见下文1 5 页3 1 1 节。 ( 7 ) 标记节点为t e s t a t t r i b u t e ； ( 8 ) f o re a c ht e s ta t t r i b u t e 中的已知值a i ； ( 9 ) 由节点n 长出一个条件为t e s t _ a t t r i b u t e = a i 的分枝； ( 1 0 ) 设s i 是s a m p l e s 中t e s t _ a t t r i b u t e = a i 的样本的集合： ( 11 ) i fs i 为空，t h e n ( 1 2 ) 加上一个树叶，标记为s a m p l e s 中最普通的类； ( 1 3 ) e 1s e 加上一个由g e n a r a te d e cisio n t r e e ( si ， a t t r i b u t e lis t t e s t _ a t t r i b u t e ) 返回的节点 2 决策树算法的主要研究内容 ( 1 ) 数据预处理技术 1 2 决策树算法无论是在训练阶段、测试阶段还是在应用阶段都是以数据为基础 的。在训练阶段数据质量的高低会影响生成的决策树的形式，在测试阶段数据质 量的高低会影响对决策树性能的评估，在应用阶段数据质量的高低会影响对象类 别的判定。在决策树算法中，影响数据质量的因素主要有两个：数据缺失和数据 噪声阳】。 数据缺失在训练集中存在数据缺失是一种很普遍的现象。数据缺失主要是 由两个原因造成的，一是数据的偶然丢失；二是数据属性间的约束关系导致某些 属性不存在符合逻辑的值。 数据噪声在前面的讨论中都假定训练集中的数据是完全精确的，但事实 上，由于数据来源于现实世界中的实际问题，因此数据不可能是完全精确的。具 体来讲，一方面属性值可能是基于测量的或者基于主观判断的，这种情况下出现 错误的值往往是不可避免的，另一方面在数据集中有些对象的类别也可能是错误 的。 鉴于此问题，在生成决策树前数据进行数据清洗、相关分析和数据变换等常 用的预处理技术，可以帮助提高生成结果的准确性、效率和可扩展性。一般来说， 决策树优化算法主要方面就是对数据的预处理进行研究，提出一些数据清洗和相 关分析的方法。 ( 2 ) 决策树属性选择度量 上述决策树算法使用信息论中的信息增益度量来选择属性。可以说，决策树 算法的核心就是确定分枝准则，如何从众多的属性变量中选择一个最佳的分裂属 性。这也是我们研究决策树算法的主要方面。 在决策树领域，属性选取标准总的可以分为以下两类。 属性间相互独立的选择策略。在评估每个属性时忽略其它属性的影响，认为 属性之间是相互独立的。它的优点是运算效率高，而且能满足很多问题的实际需 求。这种选择策略的典型代表是信息增益标准和索引标准。 属性间相互关联的选择策略。在评估每个属性时需要考虑其它属性的影响。 与属性问相互独立的选择策略相比，这种方法的运算比较复杂，运算效率比较低， 但往往能够发现属性间潜在的依赖关系。这种策略的典型代表是r e l i e f 算法引。 1 3 ( 3 ) 决策树剪枝 决策树剪枝，就是通过删除决策树的某些分支，来减小决策树的尺寸。它的 目的是为了防止决策树过度复杂。以下就对决策树修剪技术的相关知识进行介 绍。 寻找最小决策树是n p 完全问题，所以在现实中不可能找到绝对最小决策树。 只能通过分析那些使得决策树变得过于庞大的原因，来寻找一些技术来对决策树 实施剪枝，决策树剪枝的方法很多，最常用的技术有预剪枝和后剪枝。 预剪枝：在完全j f 确分类训练集之前，通过一定的法则较早地停止树的生长。 由于预剪枝不必生成整棵决策树，且算法相对简单，效率很高，适合解决大规模 问题，所以这种方法得到广泛的应用。 后剪枝：在树的生成过程之后再进行剪枝的方法。后剪枝方法最初由 b r e i m a n 等人提出，主要是通过不断的修改子树为叶节点。目前，后剪枝方法己 经得到了广泛的讨论，并在实际中得到成功的应用。 2 2 4 决策树的使用 所谓决策树的使用是指给定一个未知类别的数据对象，通过决策树转换的分 类规则判定其类别。 首先要根据构建的决策树，生成i f t h e n 格式的分类规则，再把待判断的 数据对象的属性取值与分类规则的前提相比较，如果它与某一规则的前提相吻 合，则这条规则的分类就是该数据对象的类别。 2 3 小结 本章首先主要介绍数据挖掘技术的基本理论，介绍了数据挖掘基本概念、功 能和过程。然后介绍了数据挖掘的分类技术概念，着重介绍了决策树分类技术， 总结了评估分类模型的尺度和方法。 本章从宏观上介绍了数据挖掘和分类技术的基本理论，目的是为后面研究决 策树算法奠定理论基础。 1 4 第3 章决策树算法研究 基于决策树的分类算法自提出至今，种类不下几十种。各种算法在执行速度、 可扩展性、输出结果的可理解性，分类预测的准确性等方面各有千秋。c l s 、i d 3 、 c a r t 、p u b l i c 、s l i q 、s p r i n t 算法极具代表性的决策树算法，它们在关键 技术的使用各自不同，本文主要研究c 4 。5 算法，因为c 4 5 算法分类准确率高而 且是速度最快的优点。 3 1c 4 5 算法 在决策树学习算法中，最有影响力的是q u i n l a n 提出的i d 3 算法。但由于其 在学习简单逻辑表达式方面的能力较差而受到很多攻击，且不能在算法中直接处 理连续型属性，不能处理属性值空缺的样本，生成的决策树分枝较多、规模较大。 为改进这些不足，产生了c 4 5 算法。 c 4 5 算法是q u i n l a n 于1 9 9 3 年提出的n6 1 7 1 ，是对i d 3 算法的改进，也成为 以后诸多决策树算法的基础。该算法继承了i d 3 的全部优点，它是一种归纳学习 算法，先从所有的事例中选取一部分构造决策树，再用的剩下的事例测试决策树 并对它进行调整。c 4 5 算法分类准确率高而且是速度最快的。它不仅可以处理 连续值类型的属性，还可以对属性的取值集合进行等价类划分，划分在同一类的 属性值判断时走向同一分支，对属性值空缺情况的处理和对树剪枝也有了较成熟 的方法。但c 4 5 难以获得全局的最优解。 3 1 1c 4 5 算法概述 c 4 5 算法在i d 3 的基础上增加了对连续型属性和属性值空缺情况的处理， 对树剪枝和生成规则也有了较成熟的方法。与i d 3 不同，c 4 5 采用基于信息增 益率的方法选择测试属性。信息增益率等于信息增益对分割信息量的比值。 在介绍信息增益率以前，现简单介绍一下信息增益。 1 信息增益 信息增益标准是1 9 7 9 年q u i n l a n 提出了以信息熵的下降速度作为选择测试 属性的方法。它以s h a n n o n 的信息论为基础，选择具有最高信息增益的属性作为 当前节点的分割属性。该属性使得对结果划分中的样本分类所需的信息量最小。 这种方法使得对一个对象分类所需的期望测试数目达到最小，并确保找到一棵简 单的( 但不一定是最简单的) 决策树。 设s 是s 个数据样本的集合。假定类标号属性具有m 个不同值，定义m 个不 同类c ；( i = 1 ，2 ，m ) 。设s ；是类c ；中的样本数。对一个给定的样本分类所 需的期望信息由下式给出： j ( s 。，s 2 ，s 。) = 一l o g ( 只) ( 3 1 ) i = 1 其中p i - - s ；s 是任意样本属于c i 的概率。注意，对数函数以2 为底，其原 因是信息用二进制编码。 设属性a 具有v 个不同值 a 。，a 。，a ，) 。可以用属性a 将s 划分为v 个子 集 s 。，s ：，s 。) ，其中s j 中的样本在属性a 上具有相同的值a j ( j = l ，2 ， v ) 。 设s ；j 是子集s j 中类c t 的样本数。由a 划分成子集的熵或信息期望为： 刚) _ - 壹j = l 坠学( s | j 4 - s 2 j - i - 4 - s m j ) ( 3 - 2 ) 熵值越小，子集划分的纯度越高。对于给定的子集s j ，其信息期望由公式为 i ( s s io ，s 肌_ ，) = 一乞l o g ( p u ) ( 3 - 3 ) i = i 其中p i j = s i j is ji 是s j 中样本属于c 的概率。在属性a 上分支获得的信息 增益为： g a i n ( a ) = i ( s l ，s 2 ，s 册) 一e ( a ) ( 3 4 ) 2 信息增益率 i d 3 利用信息增益作为分类评价函数来选取最优属性，这将导致该算法容易 倾向于选择取值较多的属性。针对这种缺陷，c 4 5 算法修改了分类评价函数， 用信息增益率( i n f