（通信与信息系统专业论文）数据挖掘在电信经营分析系统中针对客户流失分析的应用.pdf

数据挖掘在电信经营分析系统中 针对客户流失分析的应用 专业：通信与信息系统 硕士生：张翔 指导教师：王朝晖 摘要 随着数据挖掘技术在各行各业中的不断应用和发展，其重要性己经被越来越 多的人所认同，它能够利用积累的历史数据，通过建立和分析数学模型的方法找 出隐藏的业务规律。客户流失分析是通过对以往流失客户历史数据进行分析，找 出可能离网用户的特征，以便及时采取相应的措旌，调整运营决策，从而减少客 户流失。这项工作做得好可以降低运营成本，提高经营业绩，对电信行业有着重 要意义。 本文的研究就是将数据挖掘技术运用到电信行业的客户流失分析中，以某省 电信的历史数据为研究对象，利用数据挖掘技术建立客户流失预测模型，主要包 括了： 1 介绍了数据挖掘理论，特别是聚类算法、决策树算法、人工神经网络算法。 2 介绍了数据挖掘过程和常用的数据挖掘工具( s p s s 公司的c l e m e n t i n e ) 。 3 详细阐述了电信客户流失模型的建立过程，并对模型进行了全面评估。 本文取得以下成果： 1 对电信历史数据的特征进行了全面的分析和总结。 2 在数据预处理过程中，引入了改进的基于隐马尔可夫链的聚类算法。 3 在成功分析数据特征的基础上建立了客户流失预测模型。 相信随着数据挖掘技术的不断深入和发展，我国电信行业应用这一技术将能 发现更多有价值的关于客户信息及其消费模式方面的规律，从而更加有效地制定 各种经营决策，为国内经济建设作出贡献。 关键词： 数据挖掘，客户流失，隐马尔可夫链，决策树，神经网络 a b s l l 耻岍 t h ea p p l l c a t l 0 no ft h ed a t am l n l n gt e c h n o l o g yi n t e l e c o m m u nic a t10 nc h u r na n a l y sis m a j o r ：c o m m u n i c a t i o na n di n f o r m a t i o ns y s t e m a u t h o r ：z h a n gx i a n g s u p e r v i s o r ；w a n gc h a o h u i a b s t r a c t t h ea p p l i c a t i o no ft h ed a t am i n i n gt e c h n o l o g yi nd i f f e r e n ti n d u s t r i e sh a sb c c n g r o w i n g w ec a nu s et h eh i s t o r i c a ld a t at od i s c o v e rt h eh i d d e nb u s i n e s sr u l e sb y b u i l d i n ga n da n a l y z i n gm a t h e m a t i c a lm o d e l s i nt h et e l e c o m m u n i c a t i o n si n d u s t r y , d a t am i n i n gh a sb e e n u s e di nv a r i o u sa r e a si n c l u d i n gc h u ma n a l y s i s ，c u s t o m e r r e l a t i o n s m a n a g e m e n t , c u s t o m e re x p e n s e m o d e l a n a l y s i s , c h e a t i n ga n a l y s i s , p r o m o t i n ga n a l y s i s ，e t c n o wt h ed o m e s t i ct e l e c o m m u n i c a t i o n so p e r a t o r sp a ym o r e a n dm o r ea t t e n t i o nt od a t am i n i n gt e c h n o l o g y , a n dt h ec u s t o m e rc h u r na n a l y s i sh a s b e c o m eah o ts p o t b ys t u d y i n gt h eh i s t o r i c a ld a t ao ft h el e f tc u s t o m e r s , c h u m a n a l y s i si st of i n do u tt h e i rc h a r a c t e r i s t i c sa n dt oh e l pt a k i n gc o r r e s p o n d i n gm e a s u r e s f o rr e d u c i n gt h ec u s t o m e rc h u r nr a t e t h i sc a nr e m a r k a b l yr e d u c et h eo p e r a t i o nc o s t a n de n h a n c et h em a n a g e m e n ta c h i e v e m e n ， t h i st h e s i s sr e s e a r c hg o a li st ou t i l i z et h ed a t am i n i n gt e c h n o l o g yi nt h e c u s t o m e rc h u m a n a l y s i so ft h et e l e c o m m u n i c a t i o n si n d u s t r i e s s o m e r e a lo p e r a t i o n s d a t ai su s e dt og e n e r a t et h ec u s “ m c fc h u mf o r e c a s tm o d e lb a s e do nt h ed a t am i n i n g t e c h n o l o g y i tm a i n l yi n c l u d e st h ef o l l o w i n g c o n t e n t 1 i n t r o d u c e st h eb a s i ct h e o r yo fd a t am i n i n g , d i s c u s s e ss o m en o r m a la l g o r i t h m s s u c ha st h ec l u s t e r i n ga l g o r i t h m ，t h ed i c i s i o n - t r e ea l g o r i t h ma n dt h ea r t i f i c i a l n e u r a ln e t w o r k sa l g o r i t h m i nt h ed a t ap r e p a r a t i o ns t a g e ，ac l u s t e r i n ga l g o r i t h m b a s e d0 1 1h m m ( h i d d e nm a r k o vm o d e l ) i si n t r o d u c e da n dab e t t e re f f e c ti s o b t a i n e d 2 i n t r o d u c e st h ed a t am i n i n gp r o c e s s , d i s c u s s e st h ec o m m o nd a t am i n i n gt o o l s ： s p s sc o r p o r a t i o n sc l e m e n t i n e - 3 e l a b o r a t e st h eb u i d i n gp r o c e s so ft h et e l e c o mc u s t o m e rc h u r nm o d e l ，a n d e v a l u a t e st h em o d e lf r o md i f f e r e n tp o i n to fv i e w s n ef i r s ta c h i e v e m e n to ft h et h e s i si st h ec o m p r e h e n s i v ea n a l y s i sa n ds u m m a r y o nt h et e l e c o mh i s t o r i c a ld a t ac h a r a c t e r i s t i c s t h es e c o n da c h i e v e m e n ti st h en e w c l u s t e r i n g a l g o r i t l u nb a s e do nh m m i nt h ed a t ap r e p a r a t i o np r o c e s s n et h i r d a c h i e v e m e n ti st h ee s t a b l i s h m e n to ft h ec u s t o m e rc h u r nf o r e c a s tm o d e lb a s e do nt h e d a t ac h a r a c t e r i s t i ca n a l y s i s w i t ht h ed 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 y , t h e d o m e s t i ct e l e c o mi n d u s t r i e s w i l l f i n dm o r ev a l u a b l er u l e so u to ft h ec u s t o m e r i n f o r m a t i o na n dt h e i re x p e n s em o d e l sb ya p p l y i n gt h i st e c h n o l o g y , t h u sw i l l e f f e c t i v e l y i n s t r u c tt h ed e c i s i o n m a k i n gp r o c e s s 1b e l i e v ei tw i l lm a k em o t e c o n t r i b u t i o nf o rt h ed o m e s t i ce c o n o m i cd e v e l o p m e n t k e yw o r d s ：d a t am i n i n g ，c u s t o m e rc h u r n ，h 删( h i d d e nm a r k o vm o d e l ) ， d e e i s i o nt r e e ，n e u r a ln e t w o r k 第1 章引言 第1 章引言 1 1 我国电信行业现状 目前，我国电信业的主体是由中国电信、中国网通、中国移动、中国联通、 中国卫星、铁通公司6 家主要基础电信运营商以及上千家增值电信企业组成的。 2 0 0 1 年我国加入w t 0 ，5 年多来，我国电信业一直保持着良好发展，电信运营市场 近年来呈现平稳发展态势，业务收入不断提高。2 0 0 1 年新经济泡沫破灭之后，世 界电信业务收入大约保持在每年3 的增长速度，而中国的电信收入增长一直维持 两位数的高速增长，在全球是一枝独秀。2 0 0 6 年，我国电信业务收入6 4 8 3 亿元， 较2 0 0 5 年增长1 1 7 。在基础电信领域，各大运营商的用户份额和业务收入份 额基本保持稳定。中国移动的业务收入份额仍居首位，其次为中国电信、中国网 通、中国联通和中国铁通。 根据2 0 0 6 年全国通信业发展统计公报统计：2 0 0 6 年全国电话用户总数超过8 亿户，其中，固定电话用户新增1 7 3 6 7 ) 户，总数达盈j 3 6 7 8 1 2 万户；无线市话 用户新增5 8 2 7 ) 户，总数达至1 j 9 1 1 2 7 ) 户；公用电话用户新增3 0 1 1 万部，总数 达到2 9 8 2 3 万部；移动电话用户新增6 7 6 7 7 ) 户，总数达到4 6 1 0 8 。2 万户。固定 电话普及率和移动电话普及率分别达到2 8 1 部百人和3 5 3 百人。中国信息 产业部副部长奚国华4 月2 4 日接受记者采访时指出，最近几年，中国每年新增的 电话用户大约在8 0 0 0 万户一9 0 0 0 万户。目前，中国电话用户总数已达8 5 亿户，其 中，固定电话用户3 7 户，移动电话用户4 8 亿户“1 。纵观整个2 0 0 6 年，中国移动， 中国电信，中国网通和中国联通四大运营商盈利高达1 0 6 3 亿元，发展前景一片大 好。同时，随着电信运营领域市场竟争的引入和不断加剧，电信运营企业也在不 断调整经营理念和策略：一方面各电信运营企业都积极致力于业务和服务的创 新，完善商业模式，探索新的增长点，促使行业服务水平不断提高。另一方面， 日趋激烈的市场竞争以及经营业绩的压力也促使企业的投资行为更加趋于理性。 中山大学硕士论文 1 2 我国电信行业客户流失情况 参考目前主流的客户流失分析，我们不难发现，它们有一个相似的结论：1 5 的客户选择离开是为了更低的价格，1 5 是因为更好的产品，而高达7 0 的客户离 开是源于糟糕的服务。1 。就国内电信业而言，由于近年来几大电信企业的变更重 组、整个电信体制的激烈变革，不断加剧的激烈竞争使得各电信企业忙于开拓市 场、发展客户，而对已有客户的流失管理要么重视不够；要么注意到了问题所在 却苦于没有好的对策。一方面企业投入大量人力、物力去发展新客户，另一方面 因客户流失管理的不完善导致已有客户不断流失。忽视现有客户的保持，只注重 发展新客户，长此以往，电信企业将会出现“增量不增收”的局面，即每月用户 人数不断增加，但用户每月人均话费收入a p r u 值却在下降”1 。 这么多年来，我国电信运营商在业务支撑系统( b o s s ) 的建设中，积累了丰富 的业务数据。这些数据涉及到用户话单、通信计费、客户缴费、市场营销、业务 收入、客户服务、销售渠道、网络优化等许多方面。从数据挖掘技术的角度来看， 这些数据无异于一座座宝库，其中蕴含了巨大的潜在有用信息。如何有效的利用 它们，发掘对电信运营商有用的信息，已经成为国内电信企业的当务之急。 近年来，随着竞争的加剧，国内电信企业纷纷打出了“保存量、激增量”的 经营方向，提出了“精确营销”的观念。“保存量”就是对客户流失进行预警， 加强客户流失管理理念。于是，客户流失管理作为一套专门的管理理论和技术， 开始走进了国内电信企业的视野，很多顾问公司和软件厂商也纷纷提出各自的解 决方案。 1 3 客户流失管理的必要性 未来几年，随着国内电信企业可能会进一步拆分，市场竞争必定会日趋激烈。 对客户而言，选择余地会越来越大。因而各电信企业之间对客户的争夺也必然会 越来越激烈。据调查机构的分析表明：每年有高达1 3 左右的客户流失到竞争对 手那里，而争取、吸引一个新客户的费用是保住现有客户费用的5 1 5 倍”1 。由此 可见，客户流失已经成为各电信企业最值得关注的问题之一。 从电信企业所处的外部环境来看，随着市场竞争的激烈化，客户流失管理的 第1 章引吉 重要性日益凸显。在社会经济发展、科技进步的影响之下，我国的电信市场不断 壮大，对各种电信业务的需求量也不断增长。这一大环境无疑对电信市场的新运 营商充满了诱人的引力，同时也不断激发着运营商们的竞争积极性。于是客户流 失管理纷纷被各大运营商提上了日程。 从电信运营商内部自身的角度来看，客户流失管理是它们生存发展的需要。 根据公认的统计结论”： 1 客户忠诚度下降5 ，则企业利润下降2 5 ； 2 向新客户推销产品的成功率是1 5 ，然而，向现有客户推销产品的成功率是 5 0 ： 3 如果将每年的客户关系保持率增加5 个百分点，可能使利润增长8 5 ； 4 向新客户进行推销的花费是向现有客户推销花费的6 倍； 5 如果公司对服务过失给予快速关注，7 0 对服务不满的客户还会继续与其进行 商业合作； 6 6 0 9 6 的新客户来自现有客户的推荐； 7 一个对服务不满的客户会将他的不满经历告诉其他8 - 1 0 个人，而一位满意的 客户只会将他的满意经历告诉2 - 3 人； 以上结论都说明客户才是目前商业活动的中心，衡量一个企业是否成功的标 准将不再仅仅是企业的投资收益率和市场份额，而是该企业的客户流失率、客户 份额及客户资产收益率等与客户息息相关的指标。于是，客户的忠诚度便与增加 企业的盈利、降低企业的成本以及提高企业的竞争力紧密的联系起来。甚至于在 保持固有与开辟新生之间，保持更加重要，因为保持才能发展。 所以面对当前的市场状况，电信企业必须在发展新客户的同时，着手进行客 户保持管理的研究，以有效的客户关系管理来提高客户的挽留力度，留住有价值 的客户，支持企业经济效益的不断增长。而对客户价值的判定一方面要分析客户 利润贡献度，通过对客户收入和客户成本的严格定义和分类，以一套完整的核算 体系计量出某客户或客户组群在某时段内为企业带来的利润；另一方面也要分析 客户终身价值，从客户整个生命周期的角度计量其贡献的净现金流量。也就是说， 在短期内要留住客户利润贡献度高的客户，在长期内要留住客户终身价值高的客 户【4 】o 中山大学硕士论文 1 4 传统问题与应对办法 当前，国内针对电信业的客户流失管理已经进行了大量的研究，不少企业都 有了自己的产品，但真正应用时，往往结果并不理想。这主要是因为： 1 对挖掘对象的数据理解、准备不够充分，在选择挖掘楣关变量属性方面存在 缺少或无用属性冗余的情况； 2 没有针对预测数据找到最优的挖掘算法。 针对以上情况，我以某电信历史数据为对象，对其客户流失进行了应用研究。 在具体研究中，我加强了对数据的理解分析，尤其重视了数据预处理，并引入了改 进的基于h 删的聚类算法来改进其效果。 1 5 本文的章节结构 本论文共分为六章： 第一章：介绍了我国电信行业发展现状、客户流失情况及对客户流失进行管理的 必要性，明确本文研究的目的、对象和范围。 第二章：介绍了数据挖掘的定义、技术分类、算法分类和应用中面临的问题：详 细介绍了数据挖掘技术中的决策树、神经网络和聚类算法。 第三章：介绍了c r i s p - d m 数据挖掘过程参考模型及基于c r i s p 一咖标准的 c l e m e n t i n e 数据挖掘软件。 第四章：作为全文的重点之一，详细叙述了数据挖掘的过程。其中包括： 1 数据的理解和准备工作，它涉及到对数据的清洗、抽取、转化、聚合等，其 中重点对数据的属性进行了探索，选择适用于建模的属性。并提出了基于h m m 的新型时间序列聚类算法，应用于聚合过程中。 2 建立模型，为使预测模型更加准确，采用了两种算法建立了三个模型。 第五章：对建立的模型进行评估，以测试数据为对象，用建立的预测模型进行挖 掘，最后给出挖掘结果，并对三个模型进行了比较。 第六章：给出了本研究课题的后继工作以及展望。 第2 章数据挖掘理论介绍 第2 章数据挖掘理论介绍 2 1 数据挖掘的定义 数据挖掘( d a t am i n i n g ) 作为数据库知识发现的核心技术，就是从大量的、 不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不 知道的但又是潜在有用的信息或知识的过程，提取的知识一般可表示为概念、规 则、规律、模式等形式。确切地说，数据挖掘过程是一种决策支持过程，主要基 于人工智能、机器学习、统计学等技术，高度自动化地分析生产业务中原有的数 据，做出归纳性的推理，从中挖掘出潜在的模式，预测客户的行为，帮助企业的 决策者调整市场策略，减少风险，做出正确的决策。 2 2 数据挖掘技术分类 数据挖掘技术基本上分为两大类：描述型数据挖掘和预测型数据挖掘吲”。 2 2 1 描述型数据挖掘 “描述型数据挖掘”包括一系列在预先未知任何现有模式的情况下，在数据 内查找模式的技术。下面是描述型挖掘技术的一些术语。 分群：该技术尝试根据数据记录的相似性对其进行归组，使群与群之间差 别很明显，而同一个群之间的数据尽量相似。比如，数据记录中可能包含对每个 顾客的描述。这种情况下，分群将把类似的顾客归组到一起，同时最大程度地体 现按此方式组成的不同顾客组之间的差异。分群与分类不同，分群在聚集之前不 知道要把数据分为几个组，也不知道怎么分；而分类是在分类之前己经知道要把 数据分成哪几类，每个类的发生是什么。分群技术有很多，针对不同的数据群集， 每种技术都有自己的方法“3 。 关联分析：该技术是用来描述确定数据记录间关联的一系列技术。最为人 熟知的关联分析类型是超市购物筐分析：数据记录是顾客在同一次事务中购买的 物品。由于此技术源于超市数据分析，因此称这些物品在同一个购物筐中。超市 中山大学硕士论文 购物筐分析可发现不同顾客所购买的物品组合，通过相互联系( 或链接) ，可以总 结出哪些类型的产品是在一起购买的。关联分析不仅限于超市购物筐分析，如果 将超市购物筐看作是一组数据记录，那么在任何情况下只要存在大量数据记录， 就可以使用该技术，比如说应用到电信企业的各种分析主题。文献6 1 中作者就用 关联分析的a p r i o r i 算法对电信客户新业务量和装宽带a d s l 的关系进行了分析。 2 2 2 预测型数据挖掘 “预测型数据挖掘”包括一系列在数据中查找特定变量( 称为“目标变量”) 与其他变量之间关系的技术。下面是预测型挖掘技术的一些术语。 分类：要解决的问题是为一个事件或对象归类，是指将数据记录分配到预 先定义的类别中。在使用上，既可以用此模型分析已有的数据，也可以用它来预 测未来的数据。例如，将顾客分配到市场区。这种情况下，目标变量就是类别， 该技术发现其他变量和类别之间的关系。当对新的记录归类时，该技术可确定类 别和记录属于该类别的可能性。分类技术包括决策树、神经网络和径向基函数 ( r b f ) 分类挖掘“。 预测：指的是根据数据记录中的其他变量预测某个连续变量的值。例如， 根据顾客的年龄、性别和收入组来预测他的大概支出。最常用的数值预测技术包 括线性和多项式回归，数据挖掘将这些技术扩展到其他技术，比如神经元和r b f 值预测。 2 3 数据挖掘常见问题 在数据挖掘技术的应用中，往往对数据挖掘缺少正确的认识，认为数据挖掘 毫无用处，结果不可靠；或者认为数据挖掘是万能的，从数据中可以发现想要的 任何知识和信息。这两种观点都是不正确的，应该避免走极端，客观地认识数据 挖掘。数据挖掘的实施需要花费很长的时间和较高的费用，在一些公司或行业不 一定会产生较好的经济效益，因此，盲目地运用数据挖掘，也可能给公司带来包 袱和负担。在实际应用中，应该注意数据质量、算法选取、结果评价和界面友好 等问题“”。 第2 章数据挖掘理论介绍 2 3 1 挖掘工具 在数据挖掘的应用中，由于各种技术方法具有不同的特点和功能，应该针对 挖掘的主题和目标，选择合适的技术和算法。例如，运用贝叶斯网络预测发生频 率较低的事件，其结果的可靠性较差；对于大量较复杂的数据对象，使用决策树 方法是不理想的，而结合神经网络和遗传算法则可能获得满意的结果。因此，选 择市场上的数据挖掘工具时，应该了解系统的功能特点和使用的技术算法。 2 3 2 数据质量 数据挖掘中涉及到大量的数据，不可避免地会出现一些错误的、冗余的数据。 例如数据的缺值现象会造成不能客观地反映数据的属性和特征；含噪声的数据会 影响抽取模式的准确性；超大数据量也给知识发现带来很大的麻烦。在对数据进 行取样时，应该根据用户挖掘的主题，选择有效的数据集，并对数据进行清理、 归并和转换等操作，以保证数据的代表性和客观性。 2 3 3 数据可视化 由于数据库中的数据量非常巨大，很容易使分析员不知所措，尤其是数据维 数较高的时候，因此数据可视化变得尤为重要。我们可以用图象、曲线、二维图 形、三维体和动画来显示数据，并对其模式和相互关系进行可视化分析 3 1 】。 2 3 4 结果的验证与评估 结果的验证和评估是数据挖掘中不可缺少的环节。这是一个反复实验的过 程，运用其他的样品进行验证，也可以选择新的样品集进行评价，直到得出用户 满意的挖掘结果为止。数据挖掘的结果不一定是确切的答案，可能是一些有用的 规则、模式或模型，这与数据分析师和管理决策入员的知识背景与经验有一定的 关系。数据挖掘是一个动态的、交互的过程，需要不断地改进和完善，不断地运 用新的技术方法，提高挖掘性能和有效性”“。 中山大学硕士论文 2 3 5 信息分析的要求 信息分析要求研究团队具有丰富的领域知识、很强的调查能力和创造性。创 造性允许分析员试验各种知识发现技术，以便发现大量潜在的模式和关系，然后 分析并了解它，最后生成预测模型，并按易理解的形式发布埘。 2 4 数据挖掘算法分类 数据挖掘中的算法较多，可分为传统统计型方法、机器学习方法、神经网络 方法和数据库方法刀1 ”。 1 统计学的方法是数据挖掘的经典方法。统计方法中包括回归分析( 多元回归、 自回归等) 、判别分析( 贝叶斯判别、费歇尔判别、非参数判别等) 、聚类分 析( 系统聚类、动态聚类等) 、探索性分析( 主元分析法、相关分析法等) 。 2 机器学习中包括归纳学习方法( 决策树、规则归纳等) 、基于范例学习、遗传 算法、粗糙集等。粗糙集能够对不确定、不完整信息的进行处理，而遗传算 法具有全局最优搜索的能力。 3 神经网络方法具有处理非线性数据和含噪声数据的能力。神经网络的常用算 法包括前向神经网络( r b f ，b p 算法) 、自组织神经网络( 自组织特征映射、竞 争学习) 等。 4 数据库方法主要是多维数据分析或o l a p 方法。o l a p 系统的数据库为高效存储 静态数据构建。其存储结构的设计是为了高效检索数据，尤其是聚合数据， 比如求总和或是其它运算。 其中的大部分算法都不是专为解决某个问题而特制的，算法之间也并不互相 排斥，不能说一个问题一定要采用某种算法，别的就不行。一般来说并不存在所 谓的最好的算法，在最终决定选取那种模型或算法之前，各种模型都试一下，然 后再选取一个挖掘结果较好的。各种算法在不同的数据环境中，优劣会有所不同。 如神经网络为解决大复杂度问题提供了一种相对来说比较有效的简单方法，神经 网络可以很容易的解决具有上百个参数的问题，但挖出的结果却很难解释，挖掘 时所耗的资源也是最大的：而决策树相对来说，其结构和规则推理的过程是开放 的、清楚的，可浏览的。 第2 章数据挖掘理论介绍 数据挖掘的应用中，最终的目标都是发现有价值的知识和信息，有共同的思 路和步骤，但也存在很大的差异和区别。由于各种方法都有自身的功能特点以及 应用领域( 见表2 一1 ) 1 3 2 数据挖掘技术的选择将影响最后结果的质量和效果，通 常是将多种技术结合使用，形成优势互补。 表2 - i 数据挖掘常用算法对比 算法名称算法功能和特点应用行业 统计分析聚类：结果精确，容易理解金融，制造，医学 关联分析聚类，分类零售，制造，保险 支持向量机分类：误差较小金融，电信，医学 决策树归纳分类：容易理解 零售，电信，医学 神经网络聚类，优化：高效金融，保险，农业 贝叶斯网络聚类，分类，预测：解释性差电信，保险，制造 粗糙集不确定性分类金融，制造，零售 遗传算法聚类，优化：高效金融，保险，农业 数据挖掘的算法较多，下面主要针对我们涉及到的算法作些介绍。 2 5 决策树算法 决策树分类算法是应用最广的归纳推理算法之一。它是一种逼近离散值函数 的方法，对噪声数据有很好的健壮性并且能够学习析取表达式在这种方法中学 习到的函数被表示为一棵决策树。学习得到的决策树也能再被表示为多个 i f - t h e n 的规则，该算法己经被成功应用到医疗诊断和商业智能等各个领域。 决策树是一个类似于流程图的树型结构，其中每个内部节点表示在一个属性 上的测试。每个分枝代表一个测试输出，而每个叶子节点代表类或类的分布。树 的最顶层节点是根节点。如图2 - i 所示，就是一个贷款申请的决策树模型，从中 我们可以看到决策树的基本组成部分：决策节点、分支和叶子。 中山大学硕士论文 2 5 1 决策树的建立 图2 - 1 简单决策树示例 建立决策树的过程，即树的生长过程是不断的把数据进行切分的过程，每次 切分对应一个问题，也对应着一个节点。对每个切分都要求分成的组之间的“差 异”最大。 决策树的建立过程通常分为两个阶段：建树和剪枝。决策树归纳的基本算法 是贪心算法，它以自顶向下递归的各个击破方式构造判定树。下面就是由训练样 本归纳判定树的著名的i d 3 版本的基本算法嘲。 算法：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 el i s 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 e l 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 ； 7 ) 标记节点n 为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 j ； 9 ) 由节点n 长出一个条件为t e s ta t t r ib u t e = q 的分枝； 1 0 ) 设是是函p l e s 中t e s t _ a t t r i b u t e = 4 的样本的集合； 第2 章数据挖掘理论介绍 1 1 ) i fj 2 为空t h e n ； 1 2 ) 加上一个树叶，标记为s a m p l e s 中最普通的类； 1 3 ) e l s e 加上一个 a g e n e r a t e _ d e c i s i o n _ t r e e ( 。1 ，a t t r i b u t el i s t t e s t _ a t t r i b u t e ) 。 剪枝的目的是降低由于训练集的噪声而产生的起伏。算法的基本策略如下m ： 树以代表训练样本的单个节点开始( 步骤1 ) 。 如果样本都在同一个类，则该节点成为树叶，井用该类标记( 步骤2 和3 ) 。 否则，算法使用称为信息增益的基于熵的度量作为启发信息，选择能够最好 地将样本分类的属性( 步骤6 ) 。该属性成为该节点的“测试”或“判定”属 性( 步骤7 ) 。在算法的这个版本中，所有的属性都是分类的，即取离散值的。 连续值的属性必须离散化。 对测试属性的每个己知的值，创建一个分枝，并据此划分样本( 步骤8 1 0 ) 。 算法使用同样的过程，递归地形成每个划分上的样本判定树。一旦一个属性 出现在一个节点上，就不必考虑该节点的任何后代上( 步骤1 3 ) 。 递归划分步骤仅当下列条件之一成立时停止： ( a ) 给定节点的所有样本属于同一类( 步骤2 和3 ) 。 ( b ) 没有剩余属性可以用来进一步划分样本( 步骤4 ) 。在此情况下，使用多 数表决( 步骤5 ) 。这涉及将给定的节点转换成树叶，并用s a m p l e s 中的多数 所在的类标记它。换一种方式，可以存放节点样本的类分布。 ( c ) 分枝t e s t at t r i b u t e = a ；没有样本( 步骤11 ) 。在这种情况下，以s a m p l e s 中的多数类创建一个树叶( 步骤1 2 ) 。 2 5 2 属性划分的度量方法 2 5 2 1 信息增益叫 算法i d 3 和c 4 5 使用信息增益作为选择属性对节点进行划分的指标。信息增 益最高的划分将被作为分裂方案。1 9 4 8 年，香农提出了信息论，对信息量 ( i n f o r m a t i o n ) 和熵( e n t r o p y ) 定义为： i n f o r m a t i o n = 一l 0 9 2a( 2 1 ) 中山大学硕十论文 e n t r o p y = 一z p fl 092pi(2-2) 1 数据集s 划分前的熵： 设数据集s 有a 。，a 2 ，a 。，c 共n + 1 个属性。其中分类属性c 有m 个不同的 离散属性值c 。c ：，c 。即数据集s 中的记录可分成m 个类别设数据集s 中全 部的记录数为s ，分类属性值为c 。，c ：，c 。，的记录数分别为s l ，s2 ，s ， 那么划分之前，数据集s 的总熵为： e ( s 1 j ，s 2 ，s 玎) = 一 o2p i ( 2 3 ) 其中，是s中任意一个记录属于类别，的,善概p率i，1用gp c s ，j 估计。容易看出，数 据集s 的总熵在划分之前是属于不同类别的记录的信息量的加权平均。 2 数据集s 划分后的熵： 设属性a 具有v 个不同的离散属性值，可使用属性a 把数据集s 划分成v 个子集 j ，s ：，s ，) 。设子集s ，中全部的记录数为5 ，其中分类属性值为 c l ，c2 ，c 。的记录数分别为s lj ，s 2 ，s 。子集sj 的熵为： e ( s 1 ，s 2 ，s f ) = 一p fl 0 9 2p o(2-4) 其中乃是s ，中任意一个记录属于类别q 的概率，用墨产口估计使用属性a 把数 据集s 划分成v 个子集 s ，岛，s ) 后，数据集s 的总熵为v 各自的墒的加权平均。 数据集s 划分后的熵为： g 伽f ( s ) = ( 争木g 伽f ( s 。) + 木g 觑f ( s o ( 2 - 5 ) 3 数据集s 划分前与划分后的熵差： 信息增益：表示系统由于分类获得的信息量。由系统熵的减少值定量描述。 将数据集s 用属性a 划分后的信息增益为数据集s 划分前后得熵差： g a i n 口) = e ( s 1 ，s 2 ，s r n ) 一e 口) 选择属性对节点进行划分的标准：划分属性应具有最高信息增益。熵是一个 衡量信息混乱程度的统计量。熵越大，表示系统越混乱。分类的目的是提取系统 信息，使系统向更加有序，有规则组织的方向发展。所以，最佳的划分方案是使 第2 章数据挖掘理论介绍 熵减少量最大的划分方案。划分后熵的减少量就是信息增益，所以，选择属性对 节点进行划分的标准就是选取信息增益最大的属性。通常，决策树是“贪心算法 + 深度优先搜索”得到的。 2 5 2 2 增益比率n 町 信息增益度量存在一个内在偏置，他偏祖具有较多值的属性。避免这个不足 的一种方法是用其他度量而不是信息增益来选择决策属性。一个可以选择的度量 标准是增益比率。增益比率通过加入一个被称作分裂信息的项来衡量属性分裂数 印厅帅瑚酬脚一妻酗：斟 其中，墨到足是c 个值的属性a 分割s 而形成的c 个样例子集。注意分裂信息 实际上就是s 关于属性a 的各值的熵。 增益比率度量是用前面的增益度量和这里的分裂信息度量来共同定义的， g a i n r a t i o ( s ，彳) 一面五五瓦g 鬲a 另i n ：( s 磊, 历a 丽) ( 2 7 ) 使用增益比率代替增益来选择属性产生的一个实际问题是，当某个s 使 i s ，j _ i si 时，分母可能为。或非常小。若某个属性对于s 的所有样例有几乎同样 的值，这样要么导致增益比率未定义，要么增益比率非常大。为了避免选择这种 属性可以采用一些启发式规则，比如先计算每个属性的增益，然后仅对那些增益 高过平均值的属性应用增益比率测试。算法c 5 0 采用了这种方法。 2 5 2 3 基尼指数叫 如果决策树是二叉树，常用基尼指数作为划分的标准。c a r t 算法首先采用了 基尼指数作为选择属性对节点进行划分的标准。数据集s 的分类属性c 有m 个不同 的离散属性值c 。，c ：，c 。，即s 中的记录有m 个类别，那么其基尼指数就是： 中山大学硕十论文 g f ，z z ( s ) = 1 一p ?( 2 8 ) 其中只是类别q 出现的频率。如果用属性a 将数据集s 分成两部分墨 q l s z 。那 么这个划分的基尼指数就是： g 加f ) = ( 鲁) 木g 咖f ( s ) + ( 争串g 砌f ( s ：) ( 2 9 ) 选择基尼指数最小的属性对节点数据进行划分。决策树是二叉树时，设离散 型属性a 有v 个属性值，则属性a 可有种划分数据集s 的方法，其中一个划分方 法的基尼指数最小，称之为属性a 的最佳划分方法。在选择节点最佳划分时，首 先找出每个属性的最佳划分方法，再比较所有属性的最佳划分方法，从中选出基 尼指数最小者，最后选出节点的最佳划分。 2 5 2 4 用数值型属性划分节点方法1 在分类应用中，分类属性必须是离散型属性。其他属性也可以为数值型属性。 决策树算法中如何应用数值型属性划分节点昵? 设a 为数值型属性，a 最多可能有n 个属性值( n 为数据集s 的全部记录数) 。数 值型属性a 将数据集s 划分为两组。对应的条件为a a 。如何选择a 呢? 可以先对数据集s 按字段a 递增排序，设a 的属性值排序后的结果为 ，。，1 ，：， ，。，从d , n 大依次取不同的分裂点，取信息增益最大( 基尼指数最小) 的一个就是a 的最佳划分。若屹为最佳分裂点，通常取4 。【v ，+ ”一彳。建树 ，厶 时，在每个节点上都需要对数值型字段排序以便计算信息增益( 或基尼指数) 。 2 5 3 剪枝啪嘲 在建树过程中，由于训练集中的噪声，孤立点以及某个节点的数据量太小， 决策树的许多分枝反映出训练集中的异常。这就是决策树的过拟合( 0 v e r f i t t i n g ) 问题。它表现为用某些分类规则对训练集预测十分准确，而对测试集预测却误差 极大。过分适应问题是影响决策树准确率的关键问题，剪去决策树的冗余分枝是 解决过分适应问题的重要方法。剪枝常常利用统计学方法，去掉最不可靠，可能 第2 章数据挖掘理论介绍 是噪音的一些分枝。 2 5 3 1 剪枝的分类 在构建决策树的过程中，对决策树进行剪枝是非常有必要的。通常情况下， 剪枝方法可以分为两大类： 1 事前修前( p r e - p r u n i n g ) 该方法通过提前停止分枝生成过程。即通过在当前节点上就判断是否需要继 续划分该节点所含训练样本集来实现。一旦停止分枝，当前节点就成为一个叶节 点。该叶节点中可能包含多个不同类别的训练样本。 在建造一棵决策树时，可以利用统计上的重要检测x ，或信息增益等来对分 枝生成情况( 优劣) 进行评估。如果在一个节点上划分样本集时，会导致( 所产生 的) 节点中样本数少于指定的阐值，那么就要停止继续分解样本集合。但确定这 样一个合理的闭值常常比较困难。阐值过大会导致决策树过于简单化，而闰值过 小时又会导致多余树枝无法修剪。 2 事后修剪( p o s t p r u n i n g ) 先建树，后修剪。让树“完全生长”，然后采用一定的标准评估每个内部节 点下的分枝是否冗余分枝。剪掉冗余分枝使内部节点成为一个最有可能的叶节 点。 2 5 3 2 事后剪枝算法介绍 事前剪枝和事后剪枝这两类中，后者应用得较广泛。事后剪枝算法又可以分 为两类，一类是把训练数据集分成树生长集和树剪枝集；另一类算法则在树生长 和树剪技阶段都使用同一训练数据集。事前剪枝的缺点是使树的生长可能过早停 止，因此应用较少，这里我们对事后剪枝算法特点和存在的问题进行分析n 5 1 。 1 c c p ( c o s t c o m p l e x i t yp r u n i n g ) 方法 c c p 方法主要包含两个步骤： a 从原始决策树瓦开始生成一个子树序列瓦，瓦，l ，其中，互+ 。从五产生， 互为根节点。 b 从上一步产生的予树序列中，根据树的真实误差估计选择最佳决策树。在步 中山大学硕士论文 骤1 中，生成子树序列 t o ，t i ，l 的基本思想是从瓦开始，裁剪l 中关于训 练数据集误差增加最小的分枝来得到王+ i o 实际上，当一棵树t 在节点t 处剪枝时， 它的误差增加直观上认为是r ( f ) 一r ( t ) ，其中，r ( f ) 为在节点t 的子树被裁剪 后节点t 的误差，r 为在节点t 的子树没被裁剪时子树z 的误差。然而，剪枝后，t 的叶子数减少了l l f f , ) i - 1 ，其中，陋( z ) i 为子树王的叶子数，也就是说，t 的复杂 性减少了。因此，考虑树的复杂性因素，树分枝被裁剪后误差增加率由下式决定： 一篙l f f , 帮) - 1 ( 2 - 1 0 )li 霉+ 。就是选择霉中具有最小口值所对应的剪枝树。 如何从第1 步产生的子树序列l ，互，t ：二中选择出一棵最佳决策树是c c p 方法第2 步的关键。通常采用的方法有两种，一种是v 番交叉验证 ( v f o l d c r o s s v a l i d a t i o n ) ，另一种是基于独立剪枝数据集。 在c cp ：y 法中利用v