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

摘要 随着电信业业务重组改革的进行，电信业内各家运营商开始开展多种电信组合业 务，中国电信已在运营组合的业务套餐，中国联通也推出了相似组合业务。面对多种可 选业务，消费者会不断去评价并选择适合自己的类型。与先前使用单一业务相比，使用 综合业务客户的a r p u ( a v e r a g er e v e n u ep e ru s e r ，每用户平均收入) 值升高的更多， 客户离网造成的影响也更大。电信业业务正在不断进行着整合和发展，组合形式的业务 必然是今后的趋势，因此客户离网模式分析也是运营商必须要做的工作。 电信客户离网分析系统是用于管理电信客户关系的一个辅助分析系统，利用数据 挖掘领域的学习算法对用户的历史消费行为数据学习建模，获取历史消费数据内含的模 式规则。业务分析人员借助规则对现有客户进行分类分析，找到有离网倾向的用户并实 施客户挽留行动，延长客户在网时间，确保高值客户的在网率；获得的模型规则也用于 新业务的制定和已有业务的调整，以确保电信企业客户群的保持率，增强电信企业的综 合竞争力。 本文针对电信客户离网问题的特点，实施了数据挖掘分类算法的改进研究和应用， 并改进系统的设计。重点做了以下几方面的工作： 1 ) 介绍了应用领域中分类算法取得的发展和改进； 2 ) 分析处理不平衡数据集的常用策略和电信领域客户分类所使用算法的特点； 3 ) 提出级联结构分类算法的改进策略，并进行生产数据的实验验证。 4 ) 将改进后的算法策略应用于现有系统，进行应用测试。 本文提出了基于不平衡数据集的级联结构组合分类算法，并将新的算法策略引入电 信客户流失分析系统中，改进了原有系统的性能，为未来客户离网分析方式的研究提供 了一定的借鉴作用。 关键词决策树，级联结构，客户离网 a b s t r a c t w i t ht h er e o r g a n i z a t i o na n dr e f o r mo 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 y , t h et e l e c o m o p e r a t o r ss t a r to p e r a t i n gaw i d er a n g eo ft e l e c o m m u n i c a t i o ns e r v i c e s a tp r e s e n t ，c h i n a t e l e c o mh a v es e tu pa l lf o r m so fb u s i n e s sc o m b i n a t i o n ，c h i n au n i c o ma l s oh a v eas i m i l a r c o m b i n a t i o no fb u s i n e s s f a c i n gw i t han u m b e ro ft e l e c o m m u n i c a t i o n se n t e r p r i s e si na v a r i e t yo fb u s i n e s s ，c o n s u m e r sw i l le v a l u a t ea n ds e l e c tt h em o s ts u i t a b l eo n e t h eu s eo f c o m b i n a t i o no fb u s i n e s sn o tas i n g l eb u s i n e s s ，c u s t o m e r sw o u l dp r o d u c eah i g h e ra r p u ( a v e r a g er e v e n u e p e ru s e r ) v a l u e ，t h eb e h a v i o ro fc o n s u m e r s c h u r n i n gc a nc a u s et h eg r e a t e r l o s s e s n o w , t 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 sa r eb e i n gi n t e g r a t e d ，c o m b i n a t i o no fb u s i n e s s i sa ni n e v i t a b l et r e n d ，a n a l y s i so ft e l e c o mc u s t o m e rc h u r n i n gi sa l s ot h ei n e v i t a b l ew o r ki n f u t u r e t e l e c o mc u s t o m e rc h u ms y s t e mi sas e c o n d a r ya n a l y s i s s y s t e mo fc u s t o m e r r e l a t i o n s h i pm a n a g e m e n t ；i ts t u d i e sc o n s u m e r s c o m m u n i c a t i o nb e h a v i o rf r o mt h eh i s t o r y d a t aa n dm o d e l st h ep o t e n t i a lr u l e b u s i n e s sa n a l y s t sc l a s s i f yt h ee x i s t i n gc u s t o m e rb yu s i n g m o d e lr u l e s ，i d e n t i f yp o s s i b l ec h u r n i n gc u s t o m e r sf r o mn o r m a lc u s t o m e r sa n di m p l e m e n t c u s t o m e rc a r eo p e r a t i o n s ，i no r d e rt oe x t e n dt h es e r v i c eo fc u s t o m e r sa n de n s u r et h a t h i g h - v a l u ec u s t o m e r sc o n t i n u et ou s es e l e c t e db u s i n e s s m o d e lr u l e sc a nb eu s e df o rt h e d e v e l o p m e n t o fn e wb u s i n e s sa n dt h e a d j u s t m e n t o fe x i s t i n gb u s i n e s s ，a n dt h e n t e l e c o m m u n i c a t i o n sc o m p a n i e sh a v et h eh i g h e rr a t eo fo n - l i n ec u s t o m e ra n ds t r e n g t h e nt h e c o m p e t i t i v e n e s s t h em a i nc o n t e n t so ft h i st h e s i sa r ed a t am i n i n gr e s e a r c ha n da p p l i c a t i o no fm o d e la b o u t c u s t o m e r s c h u r n i n g ，e s p e c i a l l yi m p r o v e dc a s c a d ea l g o r i t h mb a s e do nu n b a l a n c e dd a t as e t s t h et h e s i sh a sd o n et h ew o r ko ft h ef o l l o w i n ga s p e c t s ： 1 ) d e v e l o p m e n ta n di m p r o v e m e n to ft h ec l a s s i f i c a t i o na l g o r i t h m su s e di nt h ec u r r e n t a p p l i c a t i o n 2 ) s t r a t e g i e so fd e a l i n gw i t hu n b a l a n c e dd a t as e t sa n dc l a s s i f i c a t i o na l g o r i t h m sb e i n g u s e di nt e l e c o mc u s t o m e r sc h u ma n a l y s i ss y s t e m 3 ) p r o p o s et h er e v i s e dc a s c a d ed e c i s i o n - t r e ea l g o r i t h mb a s e do nu n b a l a n c e dd a t as e t s a n dv e r i f yt h ep e r f o r m a n c eo fi m p r o v e da l g o r i t h m i i i 4 ) r e v i s et h es y s t e mo ft e l e c o mc u s t o m e rc h u r n i n ga n a l y s i su s i n gt h en e wa l g o r i t h m a n dt e s tt h et r i a lv e r s i o n a b o v em 1 _ a u t h o rp r o p o s et h er e v i s e dc a s c a d ed e c i s i o n - t r e ea l g o r i t h mb a s e d o n u n b a l a n c e dd a t as e t ，r e v i s et h es y s t e mo ft e l e c o mc u s t o m e rc h u ma n a l y s i su s i n gt h el l e w a l g o r i t h ma n di m p r o v et h ep e r f o r m a n c eo ft h eo r i g i n a ls y s t e m t h et h e s i sp r o v i d e s t h e r e f e r e n c ef o rf u t u r er e s e a r c h k e yw o r d s ：d e c i s i o nt r e e ，c a s c a d es t r u c t u r e , c u s t o m e rc h u r n 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版。本人允许 论文被查阅和借阅。本人授权西北大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。同时授权中国科学技术信息研究所等机构将本学位论 文收录到中国学位论文全文数据库或其它相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名：驺牝指导教师签名： 2 9 年莎月z o 日沙7 年护z o h 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，本 论文不包含其它人已经发表或撰写过的研究成果，也不包含为获得西北大 学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：勤瀚 7 年6 月2 。日 西北大学硕士学位论文 第一章绪论 1 1 电信客户离网研究的背景与意义 尽管全球经济危机持续了近一年，但中国经济仍保持着快速发展。中国电信业的改 革重组，国家工信部提出了具体的方案，每一家运营商由原来单一的业务模式向综合业 务模式发展( 即固话或移动业务向固话移动网络综合发展的3 g 时代) ，那么未来几年里， 中国电信事业将迎来又一次飞跃。目前，国内电信企业运营机制处于全面调整阶段，单 一业务优势在国内的独家垄断局面已经被打破，竞争将随着综合业务模式领域的发展与 完善越加激烈。 在综合业务迅速扩张的电信市场，运营商所关注的仍然是业务收入，而影响业务收 入的最基本因素是客户群。鉴于电信市场由多家运营商参与的情况，他们的收入也受制 于各自所占有的客户群比例，因此客户关系管理是各个运营商要关注的重点之一。综合 业务模式下，客户的消费业务将涉及到固话、移动通信、网络等方面，那么一个客户的 转网给运营商带来的影响将大大超过单一业务模式运营的时代，客户流失管理在客户关 系管理中将变得更加重要。由于综合业务模式还处在准备阶段，目前的研究则仍然建立 在单一业务运营模式下。 在单一业务体制运营期间，各运营商已经寻找各种方法维护客户关系，以此来保留 和竞争优质客户。通过树立客户管理理念、加强客户营销和服务、提高客户忠诚度和满 意度，提升企业盈利能力，成为运营商的战略性任务之一。由于固话和小灵通在移动方 面的劣势，通信成本的下降限度，在通信价格方面的竞争力低下，出现了客户离网行为 的加剧现象( 见图1 ) 。 面临如此大量的客户离网现象，如何挽留住客户并保持客户拥有量，如何提升每一 个客户的a r p u 值【1 1 ，客户离网行为分析则成了电信企业参与竞争必须处理的一个重要 问题。由于通信市场竞争的加剧，可选的业务类型的增多，大量客户的离网行为给运营 商带来的影响越来越大，直接造成收入下降，同时使得运供应商业务的市场占有率降低， 增加了运营商营销成本；另一方面，客户恶意离网行为造成的恶意欠费，电信运营商将 遭受不必要的经济损失。为了在竞争中争取到优势，客户离网分析在各大运营商实施的 业务系统中所占据的份额越来越大。有关的数据显示2 4 】： 1 ) 客户忠诚度下降5 ，则企业利润下降2 5 ； 1 第一章绪论 2 ) 向新客户推销产品的成功率是1 5 ，然而，向现有客户推销产品的成功率是 5 0 ： 图12 0 0 7 年8 月2 0 0 8 年8 月中国电信固话用户流失数量走势 3 ) 如果将每年的客户关系保持率增加5 个百分点，可能使利润增长8 5 ； 4 ) 向新客户进行推销的花费是向现有客户推销花费的6 倍； 5 ) 如果公司对服务过失给予快速关注，7 0 对服务不满的客户还会继续与其进行 商业合作； 6 ) 6 0 的新客户来自现有客户的推荐； 7 ) 一个对服务不满的客户会将他的不满经历告诉其他8 1 0 个人，而一位满意的客 户则会将他的满意经历告诉2 3 人； 8 ) 电信市场的二次性决定于这样的特点：客户加入的时间越长，对电信运营商的价 值越高。 所以面对当前的市场状况，电信企业必须在发展新客户的同时，着手进行客户保持 的研究，以有效的客户关系管理来提高客户的挽留力度，留住有价值的客户，保持企业 经济效益的不断增长【4 1 。而客户价值的判定一方面要分析客户利润贡献度，通过对客户 收入和客户成本严格定义和分类，以完整的核算体系计量出某客户或客户群在某时段内 为企业带来的利润4 】；另一方面也要分析客户终身价值，从客户整个生命周期的角度计 量其贡献的净现金流量。也就是说，在短期内要留住利润贡献度高的客户，在长期内要 留住客户终身价值高的客户。 1 2 电信业数据挖掘的研究现状 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，电信行业积累的数据 2 西北大学硕上学位论文 越来越多。激增的数据背后隐藏着许多重要的信息，为了对其进行更高层次的分析，运 营商直接或间接采取了多种策略来分析这些数据。通过传统的关系型数据库系统高效地 实现了数据的录入、查询、统计等功能，这种方式简洁、有效、直接，但对于数据中存 在的间接关系和规则，无法从数据库或数据库管理系统中直接获得。进入九十年代后， 为支持管理决策，出现了一种数据库结构称为数据仓库，它是将多个数据源在单个站点 以统一模式组织的数据存储【引。数据仓库技术包括数据清理、数据集成和联机分析处理 ( o l a p ) ，其中数据清理和数据集成是基础，联机分析是目的。o l a p 是一种分析技术， 具有汇总、合并和聚集功能，支持多维分析和决策，以及从不同角度观察信息的能力， 在发现海量数据隐藏的知识方面做出了不错的成绩【3 】；但对于深层次的分析功能，如数 据分类、聚类和发现数据随时间变化的特征方面，仍然不能满足实际的要求，这就促使 人们寻找其他分析工具，于是研究多年的以专家系统为代表的数据挖掘走进了人们的视 野。 数据挖掘的最初形象是专家系统技术，它需要用户或领域专家人工地将知识输入知 识库，然后根据知识库进行模糊匹配，这一过程常有偏差和失误，耗时长且费用高。随 着实际生产需求的不断深入，专家系统的进化版本也在发展，1 9 8 9 年8 月在美国底特律 召开的第1 1 届国际人工智能联合会议的专题讨论会上首次出现了k d d ( k n o w l e d g e d i s c o v e r yi nd a t a b a s e s ，数据库中知识发现) 这个术语【3 ，4 】。随后在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年都举行了k d d 专题讨论会，汇集了来自各个领域的研究人员和应用开发者，集中讨 论数据统计、海量数据分析算法、知识表示、知识运用等问题。随着参与人员的不断增 多，k d d 国际会议发展成为年会。k d d 系统包括数据预处理、数据选择、数据变换、 知识学习、模式评估、知识表示等多个阶段，其中知识学习阶段被称为“数据挖掘 ( d a t a m i n i n g ，d m ) ，它的算法是k d d 系统的核心【3 ，4 1 。1 9 9 8 年在美国纽约举行的第四届知识 发现与数据挖掘国际学术会议不仅进行了学术讨论，并且有3 0 多家软件公司展示了他 们的数据挖掘软件产品，其中不少软件已在北美、欧洲的多国得到应用，重要的决定开 始借助数据库中丰富的数据【3 1 。在我国，许多大学和研究机构已经进行了较长时间的数 据挖掘技术研究并在某些方面取得了较好的试验效果【】。 在银行业和电信业中，由于其信息化程度较高，已经具备了实施数据挖掘的应用条 件。在客户关系管理方面一些先进省份的电信公司( 中国电信、中国移动和中国联通) 或 通过咨询公司或通过软件系统已经来实施辅助决策并积累了一定的经验。多年来电信领 域的运营商为了对自身拥有的客户群体实施关怀行动，在客户群体的分类分析、业务的 3 第一章绪论 交叉销售、客户盈利能力分析、特别是客户流失预警分析等多个方面开展了尝试工作。 针对电信离网客户的分析一般采取两种手段：一是通过客户消费数据的多维分析 ( o l a p ) t 2 1 来总结其群体消费特征，这种方式直观快捷，发现的现象明显，易于判断总体 规律，但找到的规律深度不够，难于看到隐藏在数据背后的规则；另一种即采用数据挖 掘方式，通过特定算法提取离网行为模型，分析出具有较大离网概率客户，从而有针对 性对这些客户采取关怀工作，减少客户流失可能带来的损失；通过离网行为模型产生的 预警用户派单，可以提高挽留高危离网客户的成功率，降低客户离网率，减少由于客户 离网带来的收入损失；同时由离网行为模型获得的离网客户的群体特征也可以为今后定 制综合业务、分析群体消费行为积累经验、总结规律【3 ，4 】。 数据挖掘在工业应用中主要用于解决分类分析、预测、关联分析、聚类分析、时序 模式和偏差分析等方面的问题。在电信客户关系领域中使用较多的是分类分析和聚类分 析，而处理客户流失主要采用分类分析，用于分类分析的算法有多种：判定树、神经网 络、支持向量机、贝叶斯网络等。在已有的研究和应用中各个分类算法都曾经在电信的 c r m ( c u s t o m e r r e l a t i o n s h i pm a n a g e m e n t ) 中出现，并显示了一定的分类效果，但是和 实际的业务执行对比后发现，单一算法的效果不能很好的满足于实际应用。其中神经网 络的训练的模型效果相对较好，但是其模型规则很难提取，而判定树算法在精心准备后 可以获得良好的模型效果，其简明、易懂的模型规则很受业务分析人员的推崇，因此在 较多场合中采用【5 】。由于算法自身局限性，单一决策树算法总不能达到实际生产的要求， 但是单一算法在某个方面的优势又是其他算法无法替代的。在理想算法没有出现的之 前，多个算法的组合形式【6 】得到了较多的发展，并取得了优于单一算法的效果。 1 3 数据挖掘分类算法的应用现状 在各行业的业务系统中，因为决策树算法产生的模型规则清晰易懂、层次明确，受 到很多非软件行业业务分析人员的青睐。决策树算法是数据挖掘中众多分类算法中最有 代表性的一种，它由最初的判定树算法，发展到i d 3 、c 4 5 、随即森林、c a r t 、c 5 0 等，其功能不断完善、健壮性不断增强，它们在某些特定领域中对相应的数据集产生了 良好的分类效果、并提取出良好的分类模型。但是在另一些实际应用领域中产生的效果 则不能让人满意，因此其改进形式得到了较大的发展。f r e u n d 和s c h a p i r o 提出 a d a b o o s t ( a d a p t i v eb o o s t i n g ) 算法，r o b e r tes 的进一步推理弱学习算法提升为强学习算法 研究【7 】 t h o m a sg d 对算法的性能给予了验证证吲8 】；张志刚等提出的基于度量的决策 西北大学硕十学位论文 树( m b d t ) 以马氏距离来区分不同特征数据集的分类能力达到了优于传统决策树的分类 效果【9 】；苏晓影等将神经网络与决策树进行集成的组合算法，利用神经网络算法来预处 理训练样本、c 4 5 算法来构建的分类模型，其分类的泛化能力得到了提高，但运行的效 率还需要改进【l 川；黄泽宇等通过组合急切式和懒惰式学习策略采用双重分裂属性标准来 选择最佳的分裂属性【】；韩松来等在决策树基础上结合了关联度函数的思想以解决多值 的偏向问题【1 2 】；殷天石等则在文本分类中将s v m 进行改进，提出了树形结构的s v m 多类组合分类器【13 】；陈健美等在处理医学图像分类时采取了组合贝叶斯和神经网络的方 式获得了较好的分类效梨1 4 】；旷海兰等则以粗糙集理论来构造神经网络的组合分类器以 及不相关分类器的组合问题【l5 】：张春芬等则在分类医学图像时将贝叶斯、神经网络和决 策树算法的组合分类器应用到肝脏图像的分类中，提高了分类模型的准确性和稳定性 1 6 j 。类似的算法改进和算法组合还有很多，它们组合后产生的模型或者关注数据集的处 理、或者关注模型的构建。这两个方向经过进一步发展，关注于数据集预处理的研究， 基本上是以多数类欠抽样和少数类过抽样的操作，有的则通过计算少数类的决策边界并 派生出新样本来参与抽样操作：关注于模型构建的研究则主要进行分类算法的组合工 作，即在原始算法的基础上进行改进或组合，使得改进后的算法在一定程度上适应当前 的数据集，产生更可用的模型规则、更可信的分类结果。 数据挖掘分类算法的可组合形式多种多样，但是组合后的泛化能力都存在着不足， 每一种组合形式只能在相应的领域中实现一定的效果。组合算法根据改进策略一般分为 四类【1 7 】：样本集划分、属性选取、模型组合、多类问题。其组合形式有的是同种分类算 法的组合，有的则是不同种分类算法的组合；有的是并行方式，有的则是串行方式；有 的是两层算法的组合，有的则是多层算法的组合。在数据挖掘组合算法的研究和发展方 面，理论界和工业界将主要方向放在了多种分类算法的组合工作上，通过组合分类算法 保留各个单一算法的优点，摒弃它们某方面的缺点，获取最终可用的分类模型来挖掘数 据背后的潜在规则、用以辅助决策的制定。算法的各种组合形式应用在电信、银行、医 学、机械等多种领域。 在电信客户关系管理系统中，决策树参与其各种经营业务的分析也得到了较多的研 究和应用，但是基本上都没有将研究的重点放在算法的构建之上，而是以挖掘应用为目 的使用通用挖掘软件来构建挖掘业务和挖掘数据预处理。对这样构建的挖掘系统实施后 的效果跟踪表明，对于客户的挽留和保持没有多大作用，因此由模型提取的规则可用的 价值性就大打折扣。就在电信业的挖掘出现无法深入之时，分类算法在其它应用中的研 5 第一章绪论 究也在如火如荼的进行，算法应用的改进研究有了多方位的发展。k i m 等针对韩国移动 客户数据，采用l o g i s t i c 回归分析客户流失预测，确定用户流失和客户忠诚度的相关性 【1 8 】；r o s s e t 等通过引入客户价值，使用l o g i s t i c 回归模型建立客户流失分析模型，较大 的改善了提升率【1 9 】；c a r d e l i n 等采用决策树t e e d n e t 对电信公司的客户分析流失行为， 获得了较高的命中率和客户流失规则【2 0 】；例如夏国恩将核主成分分析( k p c a ) 引入到客 户流失预测中，将k p c a 与l o g i s t i c 回归结合，设计了电信客户流失预测模型和相应的特 征提取算法【2 1 】：骆盈盈等将递增式学习的c a r t 算法引入了电信客户管理中【2 2 1 ；亓呈 明等将模糊决策树引入建立决策树的过程中来处理多值属性和连续属性问题并将其应 用于滑坡研究【2 3 】；冯力力等将决策树和神经网络结合来对不平衡数据集进行抽样，利用 r o c 曲线来评价模型的性能并有效验证了竞赛数据【2 4 1 ；王勇等通过级联多个分类器形 成的分级结构来解决网络入侵检测问题【2 5 】；李闯等将级联结构的a d a b o o s t 算法应用到 了计算机视觉领域实现了图像文字检测方面的性能改进【2 6 1 。这些改进的决策树分类算法 在相应领域中的研究与应用得到了更好的准确率和性能。电信领域的客户离网检测在不 断尝试各种单一算法后收到的效果并不能让业务分析人员满意，本文将就决策树组合算 法在离网分析建模方面的应用展开研究。 1 4 本文主要内容 本文首先对数据挖掘决策树分类算法的基础理论，算法构造模型的性能评价方法， 实施算法组合的常用策略以及决策树算法组合的角度和应用领域进行了总结性概述；其 次对数据挖掘领域中遇到的数据预处理基础理论给予介绍，并对数据的不平衡分布问题 以及在数据层和算法层的处理方式方法进行总结，并分析处理不平衡数据集的策略；重 点对分类算法的新分支级联结构组合算法在数据层、算法层的特点进行了详细的研 究，并提出针对不平衡数据集的级联结构分类算法，将改进后的算法使用电信客户离网 数据进行实验验证；最后章节将级联结构分类器算法的实现融合进已有的电信客户流失 系统中进行试运行，获得更准确的分类结果和较为抽象的分类规则。 本文将目标检测领域中的级联结构分类算法进行不平衡数据集的适应性改进，并将 其应用于分析电信客户离网问题，为处理客户离网问题引进新的改进策略提供了一定的 借鉴作用。 6 西北大学硕士学位论文 1 5 主要组织结构 本文从算法的组合角度，以数据的不平衡分布处理为关注点，着重以数据挖掘算法 适用于电信客户离网分析应用为目标，研究组合算法在电信客户离网应用中的改进。全 文内容共分为六章，具体结构如下： 第一章：绪论。介绍了客户离网分析实施挖掘的研究背景、研究现状以及分类算法 在应用领域中的现状。 第二章：决策树算法研究。介绍了基本的决策树发展进程、评价分类算法模型性能 的方法、算法组合策略和决策树的组合应用。 第三章：不平衡数据集的处理研究。对数据分析和数据挖掘中有关数据的性能指标 给予介绍，对数据的分布处理从数据层和算法层两个角度进行研究。 第四章：基于不平衡数据集的级联结构算法改进。将级联结构的分类算法特点进行 了数据层和模型层的分析，根据客户离网分析业务特点，提出基于不平衡数据集的决策 树改进算法。 第五章：级联结构算法在离网分析系统中的实现。概述离网分析业务处理的思想， 介绍实施离网分析业务的执行流程，并将级联结构分类算法应用于在运行的系统。 7 西北大学硕上学位论文 2 1 常见决策树算法 第二章决策树算法研究 决策树算法是一种用于分类和预测的算法，它通过将大量数据有目的的进行分类， 从中找到一些有价值的、潜在的可以用于分类的信息。决策树算法产生的模型容易理解 并能很好地映射到一组产生式规则，分类速度快；不需要对数据的性质做预先的假设并 已经成功的应用于某些现实问题。最有影响的决策树算法是由q u i n l a n 提出的著名的基 于信息熵的i d 3 算法，它是一种非递增学习算法，通过单变量属性的信息熵来进行分支 节点的判决；i d 3 算法只能对离散变量计算信息增益，不能很好的处理连续值的属性。 因此i d 3 算法在实际应用中就有很大的局限性，于是q u i l a n 提出了c 4 5 算法，严格上 说c 4 5 只是i d 3 的一个改进算法，并且c 4 5 只适合于能够驻留于内存的数据集。i d 3 算法、c 4 5 算法和后来出现的决策树算法都是采用贪心策略，在选择划分数据的属性时， 采取的是局部最优决策构造决策树模型。c l s 算法也是这种类型的算法，是1 9 6 6 年由 h u n t 、m a r t i n e 和s t o n e 提出的决策树学习算法，后来的许多决策树学习算法都是它的改 进与更新，包括i d 3 、c 4 5 等。 2 1 1c l s 算法 在c l s 算法中，通过将训练记录相继划分成较纯的子集，从一个空的决策树出发， 以递归方式建立决策树，不断添加新的判定结点来改进已建的决策树，直至该决策树能 够正确地将训练实例分类为止。 c l s 算法【1 7 1 的主要步骤如下： 设数据集d 。是与树节点t 相关联的训练记录集，而y = y 1 ，y 2 9 - 9 y o 是类标号，c l s 算法的递归定义如下： 1 ) 如果d 。中所有记录都属于同一个类y t ，则t 是叶节点，用y t 标记。 2 ) 如果d 。中包含属于多个类的记录，则选择一个属性测试条件，将记录划分成较 小的子集。对于测试条件的每个输出，创建一个子女节点，并根据测试结果将 d 。中的记录分布到子女节点中。然后，对于每个子女节点，递归地调用该算法。 从c l s 算法的构建思想可以看出，决策树的构造过程就是对假设特化的过程，通 过添加一个新的判定条件( 新的判定结点) ，特化当前假设，c l s 算法递归执行添加判定 条件，并作用于每个子结点，来构造决策树。 9 第二章决策树算法研究 2 1 2i d 3 算法 i d 3 ( i t e r a t i v ed i c h o t o m i s e r3 迭代- - x 树3 代) 算法【2 7 1 是19 7 9 年由澳大利亚研究者 j r o s sq u i l a n 将c l s 算法改良提出的一个典型决策树学习系统，它是基于信息熵的决策 树算法，根据属性集的取值进行分类。i d 3 算法运用信息熵理论，选择当前样本集中具 有最大信息增益值的属性作为测试属性。样本集的划分则依据测试属性的取值进行，测 试属性有多少不同取值就将样本集划分为多少子样本集。 i d 3 算法的思想如下： 设e = d 1 x d 2 x d 是n 维有穷向量空间，其中d i 是有穷离散符号集，e 中的元素 e = n q 做样本，其中v je d ，j = 1 ，2 ，n 设p 。和n 。是e 的两个子集，分别 为正例集和反例集。假设向量空间e 中的正例集p 。和反例集n e 的大小分别为p 和i l ， i d 3 基于下列两个假设： 1 ) 在向量空间e 上的一棵正确决策树对任意例子的分类概率同e 中正反例的概率 一致； 2 ) 一棵决策树能对一个例子作出正确类别判断所需的信息量为： i ( p ，恻f 兰1 0 9 ：土+ 圭1 0 9 ：圭l ( 2 1 ) l p + np + np + 甩p + n 如果以属性d j 作为决策树的根，d 具有v 个值 v 1 ，v 2 ，v v ) ，它将e 分为v 个 子集 e l ，e 2 ，b ) ，假设e i 中含有p i 个正例和n i 个反例，那么子集e 所需的信息期望 是i ( p i ，n o ，以属性d j 为根所需的期望信息是： 。 剐) 2 喜等( p 硼d ( 2 2 ) 因此以d j 为根的信息增益是：g a i n ( a ) = i ( p ，n ) 一e ( a ) ，i d 3 选择使g a i n ( a ) 最大的 属性d 作为根节点，对d 的不同取值对应的e 的v 个子集e t 递归调用上述过程生成 d + 的子节点b l ，b 2 ，b v 。 i d 3 算法用信息增益作为属性选择标准，使得在每个非叶节点上进行测试时，能获 得关于被测试子集最大的类别信息，使用该属性将数据集分成子集后，系统的熵值最小， 期望该非叶节点到达各后代叶节点的平均深度较小。该算法采用自顶向下的策略，搜索 全部空间的一部分，它确保所作的测试次数较少，因而分类速度也较快。 1 0 两北大学硕上学位论文 i d 3 算法是一个很有实用价值的示例学习算法，它的基础理论清晰，算法较简单。 但也存在着一些不足： 1 ) 算法往往偏向于选择取值较多的属性，而在很多情况下属性值较多的属性并 不总是最优的属性，即按照使熵值最小的原则被i d 3 算法列为应该首先判断 的属性在现实情况中却并不那么重要。 2 ) 建树时，每个结点仅含一个特征，是一种单变量的算法，特征间的相关性不 大。虽然在一棵树上连在一起，但联系还是松散的。 3 ) i d 3 对噪声比较敏感，不容易除去噪声。即属性特征值错误或样本类别给错时 模型也错。 4 ) 当训练集样本增加时，i d 3 决策树随之变化。在建树过程中，各特征的相互信 息会随例子的增加而改变，决策树也随之变化，对于变化的数据集学习获得 的模型稳定性就难以保证。 5 ) i d 3 算法虽然理论清晰，在学习和训练数据集的过程中机器内存占用率比较 大，比较耗费资源，影响数据学习的时间和成本。 由于i d 3 算法的不完善性能，并且生产实践中需要处理连续型属性、空缺的属性值 样本，模型规模适中、分支合理的决策树等问题，促使了c 4 5 算法的实现。 2 1 3c 4 5 算法 c 4 5 算法【2 7 1 同样是是由澳大利亚研究者j r o s sq u i l a n 在1 9 9 3 年提出的，它是i d 3 算法的后继，也成为以后诸多决策树算法的基础。c 4 5 算法在i d 3 基础上融入了对连续 型属性、空缺属性值情况的处理，对树剪枝也有了较成熟的方法。应用于单机的决策树 算法中，c 4 5 算法不仅分类准确率高而且是速度较快的。 c 4 5 算法构建原理： 由于c 4 5 算法是i d 3 算法的改进，而且改进的策略主要在于分别属性的计算方式， 而建树的流程仍然遵循i d 3 算法的原则，因此c 4 5 算法的执行流程和i d 3 、c l s 算法 基本是一致的。c 4 5 算法采用基于信息增益比( i n f og a i nr a t i o ) 的方法递归地形成决策树， 信息增益比的计算方式也是通过评估不确定性的平均信息量即信息熵的方式来计算的。 类似于i d 3 信息量计算的方式，信息量的计算： 埘 地l ，s 2 ，砌) = p i l 0 9 2 ( p i ) ( 2 3 ) 第二章决策树算法研究 其中p i 是任意样本属于c i 的概率，用s j s 表示。s 是s 个数据样本的集合，假定类别属 性具有m 个不同值，定义m 个不同类c i ( 译l ，2 ，i n ) 。设s i 是类c i 中的样本数。利用属 性a 划分当前样本集合所需的信息熵e ( a ，s ) 计算如下： e ( 彳，s ) = 羔型竺攀( 跚烨一，s 功 ( 2 4 ) 若属性a 具有m 个不同值 a l ，s 2 ，a m ，利用a 将s 划分为m 个子集 s 1 ，s 2 ，s m ) ，其 中s j 为s 中在a 上具有值a j 的样本，其中嘞是子集s j 中类c i 的样本数。 声( 么，s ) = ，( s 1 ，s 2 ，s m ) 一e ( a ，s ) ( 2 5 ) c 4 5 算法采用信息增益比来描述属性对分类的贡献，用以消除偏向具有大量属性值 属性的偏差，其中确定属性a 本身需要的信息熵，即分裂信息公式如下： 刎一一喜斟崦2 斟 眨6 ， 其中s i - 一s m 是m 个值的属性a 分割s 而形成的m 个样本子集。实际上分裂信息是s 关于属性a 各值的熵。增益比是衡量属性分裂数据的广度和均匀性。信息增益比如下： 知( 郴) = 器 ( 2 7 ) 采用信息增益比分割属性得到的决策树，其中每个节点根据具有最大信息增益比的属性 生成。 c 4 5 算法有如下特点：产生的分类规则易于理解，准确率较高，计算量相对来说不 是很大，可以处理连续和类别字段。其缺点是：在构造树的过程中，需要对数据集进行 多次的顺序扫描和排序，因而导致算法的低效。此外，c 4 5 只适合于能够驻留于内存的 数据集，当训练集大得无法在内存容纳时程序则无法运行。 与i d 3 算法相比，c 4 5 算法在效率上有了很大的提高。不仅可以直接处理连续型属 性，还允许训练样本集中出现空缺的属性值，生成的决策树的分枝也较少。但是c 4 5 算法在选择测试属性，分割样本集上所采用的技术仍然存在一定偏向，生成的决策树仍 然是多叉树。如果想生成更为简洁和高效的决策树，必须对c 4 5 算法进行改进。 2 1 4c 5 0 算法 c 5 0 算法【2 8 1 是商业挖掘软件c l e m e n t i n e 中建立决策树模型所使用的算法，它是在 澳大利亚研究者j r o s sq u i l a n 提出的i d 3 算法与c 4 5 算法基础上进行演化的决策树算 西北大学硕士学位论文 法最新版本。c 5 0 算法是c 4 5 算法应用于大数据集上的分类算法，主要在执行效率和内 存使用方面进行了改进，拆分样本生成节点的判决标准是能够带来最大信息增益 ( i n f o r m a t i o ng a i n ) 的字段。 c 5 0 算法在处理数据遗漏和输入字段等问题时非常稳健，通常不需要很多的训练次 数进行估计，比一些其他类型的模型易于理解，模型推出的规则有非常直观的解释，c 5 0 也提供强大的增强技术以提高分类的精度。 由于其本身是c 4 5 算法的改进版本在商业软件中的应用，因此对于硬件环境的支 持和时空性能的效率都有了更稳健的提升，在后续的改进中c 5 0 算法已经趋向于多个 弱分类器性能的组合【2 8 1 。 2 1 5c a r t 算法 c a r t 算法【2 2 2 9 ，3 1 ( 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 ，即分类与回归树) 是19 8 4 年由l e o b r e i m a n 、j e r o m ef r i e d m a n 、r i c h a r do l s h e n 和c h a r l e ss t o n e 提出的一种数据分类和预测 算法。它采用g i n i 系数分裂准则从众多的预测属性( 模型的输入属性) 中选择一个属性或 多个属性的组合，作为树节点的分裂变量，把样本分到各个分枝中，重复该过程建立一 棵充分大的分类树，然后用剪枝算法对该充分大的树进行剪枝，得到一系列嵌套的分类 树，最后用测试数据对该系列分类树进行测试，从中选择最优的分类树【3 1 1 。c a r t 算法 是决策树模型的典型代表，可以同时处理连续变量和分类变量，如果目标变量是分类变 量，则c a r t 生成分类决策树；如果目标变量是连续变量，则c a r t 变量生成回归决策 树。 c a r t 算法构建原理： c a r t 算法首先要确定一个最佳的分支预测变量以及该预测变量的最佳分支阈值 点，然后将性质相同的样本分在同一个节点中，并且同一个父节点的两个子节点间具有 显著的差异性。节点选择准则是使节点的不纯度尽可能小，即尽可能大的降低不纯度， 由于度量节点的不纯度比度量纯度更有利于分类，则采取不纯度作为分类的指标，c a r t 使用的度量指标主要是：g i n i 系数( 即方差不纯度) ，一个两类问题的方差不纯度为。 i mp ( ) = 尸( 国1 ) 尸( 国2 ) ( 2 8 ) 当处理多类问题时，计算如下： i m p ( n ) = p ( 锨) 渤) = 1 - 尸2 ( 坳) ( 2 9 ) 江jj 1 3 第二章决策树算法研究 即g i n i 不纯度。在通过不纯度选择属性时，不纯度的下降使用下式计算： al mp ( s ) = i m p ( n ) - p k l mp ( n o ( 2 1 0 ) 血= l 其中等号右边的第一部分表示父节点的不纯度，第二部分表示子节点不纯度之和，当所 计算的值最大时，不纯度的下降也最大。每次选取使得不纯度下降最大的那个属性来分 割数据集、并构建节点的分支节点，完成后迭代执行分支节点的构建，最终完成整个决 策树【2 2 1 。 c a r t 树除了具有一般决策树的高效性、易解释、易用性、强鲁棒性等特点外，还 具有其自身的一些特点。c a r t 算法在生成树时的分支部分可以是分类变量和连续变量 的组合；可以对空