（计算机软件与理论专业论文）数据挖掘在电信客户流失中的应用研究.pdf

摘要 随着数据挖掘技术的发展，数据挖掘的重要性已经被越来越多的人认可， 它是利用己知的数据通过建立数学模型的方法找出隐含的业务规则。在国外很 多的行业己经具有成功的应用。例如，电信行业的应用领域主要有客户关系管 理，客户欺诈分析，客户流失分析，客户消费模式分析，市场推广分析等。在 国内随着对数据挖掘技术的重视，数据挖掘技术的应用研究也越来越广，其中 对电信行业的客户流失分析就是一大热点。客户流失分析是通过对以往流失客 户的历史数据进行分析，找出可能离网用户的特征。及时采取相应的措施，减 少客户流失的发生。这对企业降低运营成本，提高经营业绩有着极为重要的意 义。 本课题的目的就是研究数据挖掘的实现技术，将此技术运用到防止电信行 业的客户流失中。本文以四川省电信的无线市话小灵通的历史数据为对象，基 于数据挖掘技术，建立客户流失预测模型，主要内容包括： 1 介绍了数据挖掘的基础理论，对数据挖掘算法中的决策树算法、人工神 经网络算法进行的详细的分析和研究。 2 讨论和介绍了数据挖掘过程模型、目前流行的数据挖掘工具软件以及 s p s s 公司的c l e m e n t i n e 数据挖掘工具。 3 以数据挖掘过程为线索，详细阐述了对电信无线市话小灵通客户流失模 型的建立过程。 本课题的第一个成果是对无线市话小灵通的数据特征进行了全面的分析和 总结；第二个成果是在成功分析数据特征的基础上建立了客户流失预测模型。 随着数据挖掘技术的不断发展，电信运营商将会越来越多地发现大量有价 值的客户信息和消费模式，从而能够更有效地指导其经营决策工作。 关键词：数据挖掘。客户流失。决策树，神经网络 a b s t r a c t a b s t r a c t w i 也t h ep r o g r e s so fd a t am i n i n gt e c h n o l o g y , t h ei m p o r t a n c eo ft h ed a t am i n i n g i sa p p r o v e db ym o r ea n dm o r ep e r s o n i tm a k eu s eo fp a s s e dd a t at of i n do u tt h e u n d e r l i n gb u s i n e s sr u l eb yt h ew a y o ft h ee s t a b l i s h i n gm a t h e m a t i c sm o d e l i no t h e r c o u n t r y sm a n yf i e l d sh a v es u c c e s s f u la p p l i c a t i o n sw i t ht h ed a t am i l l i n g f o re x a m p l e ， i nt h et e l e c o m m u n i c a t i o nf i e l d st h e r ea r et h ec u s t o m e rr e l a t i o nm a n a g e m e n t ，t h e c u s t o m e rc h e a t sa n a l y s i s ，t h ec u s t o m e rl o s ea n a l y s i s ，t h ec u s t o m e rc o n s u m ea n a l y s i s ， t h em a r k e te x p a n d sa n a l y s i se t c i no u rc o u n t r yw i t l lt h ef o c u so fd a t am i n i n g d a t a m i n i n g sa p p l i c a t i o na n dr e s e a r c hw i l lb em o r e 谢d c 皿ep r e d i c t i o no fc u s t o m e r c h u r ni nt e l e c o m m u n i c a t i o ni sab i th o t t h ea n a l y s i so ft h ep r e d i c t i o no fc u s t o m e r c h u r ni st oa n a l y s et h el o s e dc u s t o m e r sh i s t o r yd a t at of i n do u tt h e i rc h a r a c t e r sf o r l e a v i n gw h i c hh e l pt h et e l e c o m m u n i c a t i o nc o m p a yt oe a r l ya d o p tm e a s u r e ，t h e n r e d u c ec u s t o m e rc h u r n i n g i th a s i m p o r t a n tm e a n i n gf o r t h et e l e c o m m u n i c a t i o n c o m p a y t h e p u r p o s e o ft h i s t o p i c i s t o p r e d i c t t h ec u s t o m e r c h u r n i n g i n t e l e e o m m u n i c a i t o nb yt h ed a t am i n i n gt e c h n o l o g y t h i sp a p e rm a k eu s eo ft h ep h s s h s t o r yd a t at oe s t a b l i s ha nc u s t o m e rc h u r n i n gm o d e n em a i nc o n t e n t si n c l u d e ： 1 i n t r o d u c e dt h et h e o r i e so fd a t am i n i n gt e c h n o l o g y a n a l y s ea n dm s c a r c ht h e d e c i s i o nt r e e sa r i t h m e t i ca n dt h ea r t i f i e i a ln e r v en e t w o r k sa r i t h m e t i c 2 d i s c u s s e dt h ep r o c e s sm o d e lo fd a t am i n i n g ，t h es o f t w a r eu s i n gi nd a t am i n i n g a n a l y s i s ，a n dt h ec l e m e n t i n es o f t w a r eo fs p s sc o m p a n y 3 d e s c r i b ei nd e t a i l st h ep r o c e s so fe s t a b l i s ht h em o d e lo ft h ep r e d i c a t i o no f c u s t o m e rc h u r n i n go f p h s ( p e r s o n a lh a n d yp h o n es y s t e m ) 。 髓ef i r s tr e s u l to f t h i st o p i ci st oa n a l y s et h ep h s sd a t ac h a r a c t e r i s t i c 7 西es e c o n d r e s u l ti ss u c c e e dt oe s t a b l i s ht h ed a t am o d e l ib e l i e v et h a tw i t ht h ep r o g r e s so fd a t am i n i n gt e c h n o l o g ym o r ea n dm o r e v a l u a b l ec u s t o m e r si n f o r m a t i o nw i l lb ef o u n d ，a n dd i r e c tt h et e l e c o m m u n i c a t i o n c o m p a yt om a k eb u s i n e s sd e c i s i o n k e y w o r d ：d a t am i n i n g ，c u s t o m e rc h u r n ，d e c i s i o nt r e e ，n e u r a ln e t w o r k i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：整：垒磊日期：础月日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：丛导师签名： 日期：三护舌年，月g 日 第章引言 第一章引言 1 1 我国电信行业的发展现状 我国经过对电信行业及电信运营企业的深化改革与重组，已成为全球电信业的一 支独秀。目前，我国电信业的市场格局是由中国电信、中国网通、中国移动、中 国联通、中国卫星、铁通公司6 家主要基础电信运营商以及4 0 0 0 多家增值电信企 业组成的。经历多年的高速发展，我国电信运营市场近年来呈现平稳发展态势， 电信业务收入不断提高，但增长速度开始放缓。2 0 0 5 年上半年，电信业务收入同 比增长1 1 ，略高于同期国内生产总值的增长速度，而低于去年同期电信业务收 入增长水平。在基础电信领域，各大运营商的用户份额和业务收入份额基本保持 稳定。中国移动的业务收入份额仍居首位，其次为中国电信、中国网通、中国联 通和中国铁通【l j 。 2 0 0 5 年上半年，我国电信运营市场呈现三个亮点：一是电话用户数迅速发展， 截至6 月末，全国电话用户总数超过7 亿户，其中移动电话用户比例为5 2 ，固 定电话用户比例为4 8 。累计新增电话用户5 4 0 2 6 万，其中移动电话新增用户比 重达5 2 6 。；二是累计新增电话用户5 4 0 2 6 万户，移动电话新增用户所占比例 仍最大，而无线市话的同比增长速度仍最快；三是全国宽带接入用户达到3 1 6 5 1 万，同比增长7 8 5 ，宽带用户数与窄带接入用户数的差距越来越小吲。 另外，截至2 0 0 5 年上半年，我国移动电话用户已达3 6 3 1 6 8 万户，超过固定 电话用户2 5 7 3 万户，累计新增2 8 3 4 4 万户。但移动电话用户的增长速度已经出 现了同比下降的趋势。从业务量看，无论是移动话音业务量还是移动短信业务量， 都呈现出较快的增长速度。2 0 0 5 年上半年移动电话通话时长达到5 8 4 5 7 亿分钟， 同比增长3 4 2 。移动短信业务量1 3 9 2 5 亿条，比去年同期增长3 9 8 f 2 】。 从上面的统计数字来看，随着电信运营领域市场竞争的引入和不断加剧，促 使电信运营企业不断调整经营理念和策略。一方面各电信运营企业都积极致力于 业务和服务的创新，完善商业模式，探索新的增长点，促使行业服务水平不断提 电子科技大学硕士学位论文 高。另一方面，日趋激烈的市场竞争以及经营业绩的压力也促使企业的投资行为 更加趋于理性。 1 2 我国电信行业的客户流失现状 所有客户流失分析都得出了同样的结论：1 5 的客户选择离开是为了更低的价 格，1 5 是因为更好的产品，而高达7 0 的客户离开是源于糟糕的服务 3 1 。对于国 内电信行业，由于近年来国内电信行业的分割、电信体制的激烈变革，竞争的急 速加剧使得各电信企业忙于开拓市场、发展客户，而对已有客户的流失管理似乎 大部分都重视不够；或者是注意到了又找不到好的方法，显得有点无能为力。一 方面企业投入大量时间、人力、财力去发展新客户，另一方面因客户流失管理的 不完善导致现有客户由于不满意而流失。所以，忽视现有客户的保持，只注重发 展新客户，长此以往，电信企业将会出现“增量不增收”的局面，即每月用户人 数不断增加，但用户每月人均话费收入a p r u 值却在下降【4 】。 我国电信运营商在多年的业务支撑系统( b o s s ) 建设中，积累了大量的原始业 务数据。这些数据涉及到用户话单、通信计费、客户缴费、市场营销、业务收入、 客户服务、销售渠道、网络优化等各个方面，这些历史数据每季度都按时转存到 磁带文件中。从数据挖掘技术的观点来看，这些大量的历史数据中存储了巨大的 潜在有用信息。如何有效的利用这些已有的数据，发现对电信运营商有用的知识 并急时的采取决策，已经摆到了国内电信运营商的议事日程上。 在当前电信业发展的背景之下，国内电信企业打出了“保存量、激增量”的经 营方向，提出了“精确营销”的观念。“保存量”就是对客户流失进行预警，提出客 户流失管理理念。客户流失管理作为一套专门的管理理论和技术，开始走进了国 内电信企业，很多顾问公司和软件厂商也提出自己的解决方案。但是，在具体如 何实施客户流失管理的技术细节上，却是八仙过海、各显神通，没有统一的定论。 1 3 客户流失管理的必要性分析 随着中国电信企业的进一步拆分，市场竞争日趋激烈，客户选择电信产品及 电信企业的余地越来越大，电信企业之间对客户的争夺也越来越激烈。国外调查 2 第一章引言 机构的分析表明：每年有高达1 3 左右的客户流失到竞争对手那里，而争取、吸 引一个新客户的费用是保住现有客户费用的5 1 5 倍【5 】。客户流失已经成为电信企 业最关注的问题之一。 从电信企业所处的外部环境来看，客户流失管理是进行市场竞争的需要。在 社会经济发展、科技进步的影响之下，我国的电信市场逐渐扩大，电信业务的需 求量不断增长。由此大大吸引了电信市场新运营商的进入，更激发了新的市场进 入者的竞争积极性。这时候客户流失管理的重要性就在竞争中凸现出来。 从电信运营商自身的角度来看，客户流失管理是企业生存发展的需要。有关 的数据显示： ( 1 ) 客户忠诚度下降5 ，则企业利润下降2 5 ； ( 2 ) 向新客户推销产品的成功率是1 5 ，然而，向现有客户推销产品的成功 率是5 0 ； ( 3 ) 如果将每年的客户关系保持率增加5 个百分点，可能使利润增长8 5 ； ( 4 ) 向新客户进行推销的花费是向现有客户推销花费的6 倍； ( 5 ) 如果公司对服务过失给予快速关注，7 0 对服务不满的客户还会继续与其 进行商业合作； ( 6 ) 6 0 的新客户来自现有客户的推荐： ( 7 ) 一个对服务不满的客户会将他的不满经历告诉其他8 1 0 个人，而一位满 意的客户则会将他的满意经历告诉2 3 人； ( 8 ) 电信市场的二次性决定于这样的特点：客户加入的时间越长，对电信运营 商的价值越高。 以上数据充分说明，客户是目前商业活动的中心，衡量一个企业是否成功的 标准将不再仅仅是企业的投资收益率和市场份额，而是该企业的客户流失率、客 户份额及客户资产收益率等指标。可见，客户挽留，即忠诚客户的价值体现在增 加企业的盈利、降低企业的成本以及提高企业的竞争力等方面。在保持固有与开 辟新生之间，保持显得愈加重要，可以说：保持就是发展。 所以面对当前的市场状况，电信企业必须在发展新客户的同时，着手进行客 户保持管理的研究，以有效的客户关系管理来提高客户的挽留力度，留住有价值 的客户，支持企业经济效益的不断增长。而对客户价值的判定一方面要分析客户 电子科技大学硕士学位论文 利润贡献度，通过对客户收入和客户成本的严格定义和分娄，以一套完整的核算 体系计量出某客户或客户组群在某时段内为企业带来的利润：另一方面也要分析 窖户终身价值，从客户整个生命周期的角度计量其贡献的净现金流量。也就是说， 在短期内要留住客户利润贡献度高的客户，在长期内要留住客户终身价值高的客 户嗍。 1 4 本文的工作以及思路 当前，国内针对电信业的客户流失管理进行了大量的研究也产生了大量的文 献资料，也有的企业对电信业的客户流失管理有了自己的产品。但这些理论和产 品真正应用到电信行业的客户流失预警实践时，往往预测出的结果有所偏差，以 至不是很理想。本人认为产生这种情况的主要原因是： ( 1 ) 对挖掘对象的数据理解、准备不够充分，在选择挖掘相关变量属性方面 存在缺少或无用属性冗余的情况； ( 2 ) 没有针对预测数据找到最优的挖掘算法； 针对以上情况，根据四川省电信经营分析人员的建议及其提出的必要性，本 人咀电信无线市话小灵通历史数据为对象，对无线市话的客户流失进行了应用研 究。 本论文共分为六章： 第一章：主要阐述了我国电信行业的发展现状、客户流失现状及对客户流失 进行管理的必要性，明确论文的研究目的、研究对象和研究范围。 第二章：概括阐述了数据挖掘的定义、技术分类、算法分类和应用中面临的 问题；详细介绍数据挖掘技术中的决策树算法和人工神经网络算法。 第三章：介绍了c r i s p d m 数据挖掘过程参考模型及基于c r i s p d m 标准的 c l e m e r l tjt 1 0 数据挖掘软件。 第四章：这章全文的重点之一，详细叙述了数据挖掘的过程。其中包括： 1 ) 对数据的理解和准各工作，它涉及到对数据的清洗、抽取、转化等， 其中重点对无线市话的属性进行了探索，选择出用于建模的属性。 2 ) 建立模型，为了使预测模型更加准确，采用了两种决策树算法对训练 2 ) 建立模型，为了使预测模型更加准确，采用了两种决策树算法对训练 第一章引言 数据进行建模。 第五章：这章也是重点之一，对建立的模型进行评估。以测试数据为对象， 用建立的预测模型进行挖掘，最后给出了挖掘结果，并对两种模型进行 了比较。 第六章：给出了全文的总结、后继工作及展望。 电子科技大学硕士学位论文 2 1 数据挖掘定义 第二章数据挖掘理论背景 数据挖掘( d a t am i n i n g ) 作为数据库知识发现的核心技术，就是从大量的、不 完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知 道的但又是潜在有用的信息或知识的过程，提取的知识一般可表示为概念、规则、 规律、模式等形式。确切地说，数据挖掘过程是一种决策支持过程，主要基于人 工智能、机器学习、统计学等技术，高度自动化地分析生产业务中原有的数据， 做出归纳性的推理，从中挖掘出潜在的模式，预测客户的行为，帮助企业的决策 者调整市场策略，减少风险，做出正确的决策 6 1 1 7 。 2 2 数据挖掘技术分类 数据挖掘技术基本上分为两大类：描述型数据挖掘和预测型数据挖掘，下面 就这两种挖掘类型进行说明7 】【2 5 】。 2 2 1 描述型数据挖掘 “描述型数据挖掘“包括一系列在预先未知任何现有模式的情况下，在数据 内查找模式的技术。下面是描述型挖掘技术的一些术语。 分群：该技术尝试根据数据记录的相似性对其进行归组，使群与群之间差别 很明显，而同一个群之间的数据尽量相似。比如，数据记录中可能包含对每个顾 客的描述。这种情况下，分群将把类似的顾客归组到一起，同时最大程度地体现 按此方式组成的不同顾客组之间的差异。分群与分类不同，分群在聚集之前不知 道要把数据分为几个组，也不知道怎么分；而分类是在分类之前已经知道要把数 据分成哪几类，每个类的发生是什么。分群技术有很多，针对不同的数据群集， 每种技术都有自己的方法【1 7 】。 关联分析：该技术是用来描述确定数据记录间关联的一系列技术。最熟知的 第二章数据挖掘理论背景 关联分析类型是市场购物篮分析。该情况下数据记录是顾客在同一次事务中购买 的物品，由于该技术来源于超市数据的分析，因此称这些物品在同一个购物篮中。 市场购物篮分析可发现不同顾客所购买的物品组合，通过相互联系f 或链接) ，可以 总结出哪些类型的产品是在一起购买的。关系分析不仅限于市场购物篮分析，如 果将市场购物篮看作是一组数据记录，那么在任何情况下只要存在大量数据记录， 就可以使用该技术。例如，电信企业的各种分析主题中。文献【6 】中作者就用关联 分析的a p r i o r i 算法对电信客户新业务量和装宽带a d s l 的关系进行了分析。 2 2 2 预测型数据挖掘 “预测型数据挖掘”包括一系列在数据中查找特定变量( 称为“目标变量”) 与其他变量之间关系的技术。下面是预测型挖掘技术的一些术语。 分类：要解决的问题是为一个事件或对象归类，是指将数据记录分配到预先 定义的类别中。在使用上，既可以用此模型分析已有的数据，也可以用它来预测 未来的数据。例如，将顾客分配到市场区。这种情况下，目标变量就是类别，该 技术发现其他变量和类别之间的关系。当对新的记录归类时，该技术可确定类别 和记录属于该类别的可能性。分类技术包括决策树、神经网络和径向基函数( r b f ) 分类挖掘【”】。 预测：指的是根据数据记录中的其他变量预测某个连续变量的值。例如，根 据顾客的年龄、性别和收入组来预测他的大概支出。最常用的数值预测技术包括 线性和多项式回归，数据挖掘将这些技术扩展到其他技术，比如神经元和r b f 值预 测。 2 3 数据挖掘在应用中的几个问题 在数据挖掘技术的应用中，往往对数据挖掘缺少正确的认识，认为数据挖掘 毫无用处，结果不可靠：或者认为数据挖掘是万能的，从数据中可以发现想要的 任何知识和信息。这两种观点都是不正确的，应该避免走极端，客观地认识数据 挖掘。数据挖掘的实施需要花费很长的时间和较高的费用，在一些公司或行业不 一定会产生较好的经济效益，因此，盲目地运用数据挖掘，也可能给公司带来包 7 电子科技大学硕士学位论文 袱和负担。在实际应用中，应该注意数据质量、算法选取、结果评价和界面友好 等问题【7 】口7 1 。 1 ) 技术方法的选取问题： 在数据挖掘的应用中，由于各种技术方法具有不同的特点和功能，应该针对 挖掘的主题和目标，选择合适的技术和算法。例如，运用贝叶斯网络预测发生频 率较低的事件，其结果的可靠性较差；对于大量较复杂的数据对象，使用决策树 方法是不理想的，而结合神经网络和遗传算法则可能获得满意的结果。因此，选 择市场上的数据挖掘工具时，应该了解系统的功能特点和使用的技术算法。 2 ) 数据质量的问题： 数据挖掘中涉及到大量的数据，不可避免地会出现一些错误的、冗余的数据。 例如，数据的缺值现象，则不能客观地反映数据的属性和特征；含噪声的数据会 影响抽取模式的准确性；对于超大数据量，也给知识发现带来很大的麻烦。在对 数据进行取样时，应该根据用户挖掘的主题，选择有效的数据集，并对数据进行 清理、归并和转换等操作，保证数据的代表性和客观性。 3 ) 数据可视化问题： 由于数据库中的数据量非常巨大，很容易使分析员变得不知所措，尤其是数 据维数较高的时候，因此数据可视化变得尤为重要，它有助于分析员增加人们的 视觉能力。数据挖掘可通过设定富有成效的探索的始点并按恰当的隐喻来表示数 据给予帮助。 4 ) 结果的验证与评价问题： 结果的验证和评价是数据挖掘中不可缺少的环节。这是一个反复实验的过程， 运用其他的样品进行验证，也可以选择新的样品集进行评价，直到得出用户满意 的挖掘结果为止。数据挖掘的结果不一定是确切的答案，可能是一些有用的规则、 模式或模型，这与数据分析师和管理决策人员的知识背景与经验有一定的关系。 数据挖掘是一个动态的、交互的过程，需要不断地改进和完善，不断地运用新的 技术方法，提高挖掘性能和效率。 5 ) 信息分析员的技能【8 j 信息分析需要丰富的领域知识，并具有很强的调查能力，同时还应用创造性。 创造性允许分析员试验各种知识发现技术，以便发现大量潜在的模式和关系，然 第二章数据挖掘理论背景 后分析并了解它，最后生成预测模型，并按易理解的形式发布。 2 4 数据挖掘算法分类 数据挖掘中的算法较多，可分为传统统计型方法、机器学习方法、神经网络 方法和数据库方法【刀。 i ) 统计学的方法是数据挖掘的经典方法。统计方法中包括回归分析( 多元回归、 自回归等) 、判别分析( 贝叶斯判别、费歇尔判别、非参数判别等) 、聚类分析( 系 统聚类、动态聚类等) 、探索性分析( 主元分析法、相关分析法等) 。 2 ) 机器学习中包括归纳学习方法( 决策树、规则归纳等) 、基于范例学习、遗传算 法、粗糙集等。粗糙集能够对不确定、不完整信息的进行处理，而遗传算法具有 全局最优搜索的能力。 3 ) 神经网络方法具有处理非线性数据和含噪声数据的能力。神经网络的常用算法 包括前向神经网络( r b f 、b p 算法等) 、自组织神经网络( 自组织特征映射、竞争 学习等) 等。 4 ) 数据库方法主要是多维数据分析或o l a p 方法。o l a p 系统的数据库为高效存储 静态数据构建。其存储结构的设计是为了高效检索数据，尤其是聚合数据，比如 求总和或是其它运算。 其中的大部分算法都不是专为解决某个问题而特制的，算法之间也并不互相 排斥，不能说一个问题一定要采用某种算法，别的就不行。一般来说并不存在所 谓的最好的算法，在最终决定选取那种模型或算法之前，各种模型都试一下，然 后再选取一个挖掘结果较好的。各种算法在不同的数据环境中，优劣会有所不同。 如神经网络为解决大复杂度问题提供了一种相对来说比较有效的简单方法，神经 网络可以很容易的解决具有上百个参数的问题，但挖出的结果却很难解释，挖掘 时所耗的资源也是最大的；而决策树相对来说，其结构和规则推理的过程是开放 的、清楚的，可浏览的。 数据挖掘的应用中，最终的目标都是发现有价值的知识和信息，有共同的思 路和步骤，但也存在很大的差异和区别。由于各种方法都有自身的功能特点以及 应用领域( 见表2 1 ) 【6 2 7 】，数据挖掘技术的选择将影响最后结果的质量和效果，通 电子科技大学硕士学位论文 常是将多种技术结合使用，形成优势互补。 表2 - 1 数据挖掘的主要技术方法对比 技术方法主要功能及特点应用领域 决策树归纳分类；可理解电信、医学和零 性售业等 遗传算法聚类、优化；高效金融业、保险业 性和农业等 粗糙集不确定性分类零售业、金融业 和制造业等 神经网络预测、分类和聚电信业、保险业 类；解释性差和制造业等 贝叶斯网络分类、聚类和预医学、制造业和 测；易理解电信等 关联规则分类、聚类零售业、保险业 和制造业等 统计分析聚类；结果精确、金融业、制造业 易理解和医学等 支持向量机分类；误差小医学、电信和金 融业等 数据挖掘的算法较多，在这主要针对我们使用到的算法作些介绍。 2 5 决策树算法 决策树分类算法是应用最广的归纳推理算法之一。它是一种逼近离散值函数 的方法，对噪声数据有很好的健壮性并且能够学习析取表达式在这种方法中学 习到的函数被表示为一棵决策树。学习得到的决策树也能再被表示为多个 i f - t h e n 的规则，该算法已经被成功应用到医疗诊断和商业智能等各个领域。 决策树是一个类似于流程图的树型结构，其中每个内部节点表示在一个属性 l o 第二章数据挖掘理论背景 上的测试。每个分枝代表一个测试输出，而每个叶子节点代表类或类的分布。树 的最顶层节点是根节点。如图2 一l 一个简单决策树所示，就是一个贷款申请的决 策树模型，从中我们可以看到决策树的基本组成部分：决策节点、分支和叶子。 2 5 1 决策树的建立 图2 - 1 一个简单决策树 建立决策树的过程，即树的生长过程是不断的把数据进行切分的过程，每次 切分对应一个问题，也对应着一个节点。对每个切分都要求分成的组之间的“差 异”最大。 决策树的建立过程通常分为两个阶段：建树和剪枝。决策树归纳的基本算法 是贪心算法，它以自顶向下递归的各个击破方式构造判定树。图2 2 描述了由训 练样本归纳判定树的著名的i d 3 版本的基本算法【”。 电子科技大学硕士学位论文 建树算法：g e n e r a t e _ d e c i s i o n _ t r e e 由给定的训练数据产生一棵判定树。 i 输入：训练样本s a m p l e s ，由离散值属性表示；候选属性的集合a t t r i b u t el i s t 。j i 输出：一棵决策树。l i 方法：j f 1 ) 创建节点n ；i f 2 ) i fs a m p l e s 都在同一个类ct h e n ；i j 3 ) 返回n 作为叶节点，以类c 标记；l j 4 ) i fa t t r i b u t el i s t 为空，t h e n ；i 5 ) 返回n 作为叶节点，标记为s a m p l e s 中的最普通的类：f l 6 ) 选择a t t r i b u t e _ l i s t 中具有最高信息增益的属性t e s ta t t r i b u t e ；i l 7 ) 标记节点n 为t e s t _ a t t r l b u t e ；l i 8 ) f o re a c ht e s ta t t r i b u t e 中的已知值e l ；f 9 ) p h 节点n 长出一个条件为t e s t _ a t t r i b u t e = a i 的分枝；i i 1 0 ) 设s 2 是s a m p l e s 中t e s t _ a t t r i b u t e = a 的样本的集合；i i 1 1 ) i fs 2 为空* h e n ；l i 1 2 ) 加上一个树叶。标记为s a m p l e s 中最普通的类；l l 1 3 ) e l s e 加上一个f g e n e r a t e d e c i s i o n _ t r e e ( s l ，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 ) 。i 图2 - 2 由训练样本归纳判定树的基本算法 剪枝的目的是降低由于训练集的噪声而产生的起伏。算法的基本策略如下闭： 树以代表训练样本的单个节点开始( 步骤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 _ a t t r i b u t e = a i 没有样本( 步骤1 1 ) 。在这种情况下，以s a m p l e s 中的多数类创建一个树叶( 步骤1 2 ) 2 5 2 属- 眭划分的度量方法 1 信息增益 9 】 算法i d 3 和c 4 5 使用信息增益作为选择属性对节点进行划分的指标。信息增 益最高的划分将被作为分裂方案。1 9 4 8 年，c e s h a n n o n 提出了信息论，对信息 量( 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 2p i e n t r o p y = 一p 。l 0 9 2p i 1 ) 数据集s 划分前的熵： 设数据集s 有a 。，a 2 ，& ，c 共n + l 个属性。其中分类属性c 有m 个不同 的离散属性值c 。，c ：。，c 。即数据集s 中的记录可分成m 个类别设数据集s 中全部的记录数为s ，分类属性值为c ，c 。，c 。，的记录数分别为s 。，s 。， s 。那么划分之前，数据集s 的总熵为： e ( s l j ，s z ，s ，j ) = 一p i l 0 9 2 b l - 1 其中p ，是s 中任意一个记录属于类别c 。的概率，用s ；s 估计。容易看出，数据 集s 的总熵在划分之前是属于不同类别的记录的信息量的加权平均。 2 ) 数据集s 划分后的熵： 设属性a 具有v 个不同的离散属性值，可使用属性a 把数据集s 划分成v 个 子集 s 。，s ：，s 0 。设子集s ，中全部的记录数为s ，其中分类属性值为c ， c 。，c 。的记录数分别为s 1 j s ：。，s 。，。子集sj 的熵为： 电子科技大学硕士学位论文 e ( 吣，s 2 ，勺) = 功l o g ：岛 其中p ，是s ，中任意一个记录属于类别c ；的概率，用s t ，sj j 估计。使用属性a 把数据集s 划分成v 个子集 s 。，s 。，s ，) 后，数据集s 的总熵为v 各自的墒的 加权平均。数据集s 划分后的熵为： g i n 僻+ g i n 瞄) + + 锄 其中w ，是第j 个子集的权用s i s 估计。 3 ) 数据集s 划分前与划分后的熵差： 引入一个量：信息增益：表示系统由于分类获得的信息量。由系统熵的减少 值定量描述。将数据集s 用属性a 划分后的信息增益为数据集s 划分前后得熵差： g a i n ( a ) = e ( s 。，s ”，s ) 一e ( a ) 选择属性对节点进行划分的标准：划分属性应具有最高信息增益。熵是一个衡量 信息混乱程度的统计量。嫡越大，表示系统越混乱。分类的目的是提取系统信息， 使系统向更加有序，有规则组织的方向发展。所以，最佳的划分方案是使熵减少 量最大的划分方案。划分后熵的减少量就是信息增益，所以，选择属性对节点进 行划分的标准就是选取信息增益最大的属性。通常，决策树是“贪心算法+ 深度 优先搜索”得到的。 2 增益比率 9 l 信息增益度量存在一个内在偏置，他偏袒具有较多值的属性。避免这个不足的 一种方法是用其他度量而不是信息增益来选择决策属性。一个可以选择的度量标 准是增益比率。增益比率通过加入一个被称作分裂信息的项来衡量属性分裂数据 的广度和均匀性： 跚蚴r m a t i o n c 跗卜喜哥l 0 9 2 斜 其中，s 。到s 。是c 个值的属性a 分割s 而形成的c 个样例子集。注意分裂信息实 际上就是s 关于属性a 的各值的熵。 增益比率度量是用前面的增益度量和这里的分裂信息度量来共同定义的，即： 第二章数据挖掘理论背景 g a i n r a t i o ( s , a ) = 面丽g 丙a i n 忑( s , 丽a ) 使用增益比率代替增益来选择属性产生的一个实际问题是，当某个s t 使l s t l = i s l 时，分母可能为0 或非常小。若某个属性对于s 的所有样例有几乎同样的值，这 样要么导致增益比率未定义，要么增益比率非常大。为了避免选择这种属性可以 采用些启发式规则，比如先计算每个属性的增益，然后仅对那些增益高过平均 值的属性应用增益比率测试。算法c 5 0 采用了这种方法。 3 基尼指数【9 】 如果决策树是二叉树，常用基尼指数作为划分的标准。c a r t 算法首先采用了 基尼指数作为选择属性对节点进行划分的标准。数据集s 的分类属性c 有i 2 1 个不 同的离散属性值c ，c ：，c 。即s 中的记录有m 个类别，那么其基尼指数就 是： g i n i ( s ) = 1 - 霄 其中p ：是类别c ；出现的频率。如果用属性a 将数据集s 分成两部分s 。，s ：。 那么这个划分的基尼指数就是： g i n 酗) ：+ g i n 鹕) + e ) + g i n 妈) 选择基尼指数最小的属性对节点数据进行划分。决策树是二叉树时，设离散型属 性a 有v 个属性值，则属性a 可有2 种划分数据集s 的方法，其中一个划分方法 的基尼指数最小，称之为属性a 的最佳划分方法。在选择节点最佳划分时，首先 找出每个属性的最佳划分方法，再比较所有属性的最佳划分方法，从中选出基尼 指数最小者，最后选出节点的最佳划分。 4 用数值型属性划分节点方法1 9 在分类应用中，分类属性必须是离散型属性。其他属性也可以为数值型属性。 决策树算法中如何应用数值型属性划分节点呢? 设a 为数值型属性，a 最多可能有n 个属性值( n 为数据集s 的全部记录数) 。 数值型属性a 将数据集s 划分为两组。对应的条件为a a 。如何选择a 呢? 可以先对数据集s 按字段a 递增排序，设a 的属性值排序后的结果为v ，v 。 电子科技大学硕士学位论文 v 。，从小到大依次取不同的分裂点，取信息增益最大( 基尼指数最小) 的一个就 是a 的最佳划分。若v ；为最佳分裂点，通常取a _ ( v 。+ v 。一。) 2 。建树时，在每个节 点上都需要对数值型字段排序以便计算信息增益( 或基尼指数) 。 2 5 3 剪枝 在建树过程中，由于训练集中的噪声，孤立点以及某个节点的数据量太小， 决策树的许多分枝反映出训练集中的异常。这就是决策树的过拟合( o v e r f i t t i n g ) 问题。它表现为用某些分类规则对训练集预测十分准确，而对测试集预测却误差 极大。过分适应问题是影响决策树准确率的关键问题，剪去决策树的冗余分枝是 解决过分适应问题的重要方法。剪枝常常利用统计学方法，去掉最不可靠，可能 是噪音的一些分枝。 2 5 3 1 剪枝的分类 在构建决策树的过程中，对决策树进行剪枝是非常有必要的。通常情况下， 剪枝方法可以分为两大类： 1 ) 事前修前( p r e - p r u n i n g ) 该方法通过提前停止分枝生成过程。即通过在当前节点上就判断是否需要继 续划分该节点所含训练样本集来实现。一旦停止分枝，当前节点就成为一个叶节 点。该叶节点中可能包含多个不同类别的训练样本。 在建造一棵决策树时，可以利用统计上的重要检测x 2 或信息增益等来对分枝 生成情况( 优劣) 进行评估。如果在一个节点上划分样本集时，会导致( 所产生 的) 节点中样本数少于指定的阈值，那么就要停止继续分解样本集合。但确定这 样一个合理的闽值常常比较困难。阈值过大会导致决策树过于简单化，而阈值过 小时又会导致多余树枝无法修剪。 2 ) 事后修剪( p o s t p r u n i n g ) 先建树，后修剪。让树“完全生长”，然后采用一定的标准评估每个内部节点 下的分枝是否冗余分枝。剪掉冗余分枝使内部节点成为一个最有可能的叶节点。 2 5 3 2 事后剪枝算法介绍 事前剪枝和事后剪枝这两类中，后者应用得较广泛。事后剪枝算法又可以分 1 6 第二章数据挖掘理论背景 为两类，一类是把训练数据集分成树生长集和树剪枝集i 另一类算法则在树生长 和树剪枝阶段都使用同一训练数据集。事前剪枝的缺点是使树的生长可能过早停 止，因此应用较少，这里我们对事后剪枝算法特点和存在的问题进行分析“： 1 ) c c p ( c o s tc o m p l e x i t yp r u n i n g ) 方法 c c p 方法主要包含两个步骤： ( 1 ) 从原始决策树t o 开始生成一个子树序列t 0 ，t 1 “t h 。其中，t 。从t i 产生， t 。为根节点。 ( 2 ) 从第1 步产生的子树序列中，根据树的真实误差估计选择最佳决策树。 在步骤1 中，生成子树序列 t 。，t 。，t ) 的基本思想是从t o 开始，裁剪t 。 中关于训练数据集误差增加最小的分枝来得到t 。实际上，当一棵树t 在节点 t 处剪枝时，它的误差增加直观上认为是r ( t ) - r ( t 。) ，其中，r ( t ) 为在节点t 的 子树被裁剪后节点t 的误差，r 为在节点t 的子树没被裁剪时子树t i 的误差。然 而，剪枝后，t 的叶子数减少了i l ( t 。) 卜_ l ，其中，i l ( t ；) i 为子树t ，的叶子数，也 就是说，t 的复杂性减少了。因此，考虑树的复杂性因素，树分枝被裁剪后误差 增加率由下式决定： 月0 ) 一r ( z ) “= 一 i 三( z ) i 一1 t 。就是选择t ；中具有最小口值所对应的剪枝树。 如何从第1 步产生的子树序列t 。，t 。，t 2 中选择出一棵最佳决策树是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 c p 方法中利用v 番交叉验证方法，首先需要将训练数据集d 划分为v 个 子集d 1 ，d 2 ，d o 然后，从d d 1 ( i = l ，2 ，v ) 中生成v 个子树t 1 ，t 2 ，t 7 。t ( 峨) 的真实误差就是利用丁1 ( q 吼+ 。) ，r ( 呸q 。) 的平均值来衡量的。但这种方 法成立的前提是t ( 嘶) ，t i ( 匆口。) ，r ( 辑口。) 具有相同真实误差率。事 实上，使用自顶向下的决策树算法在小数据集情况下，认为t