（控制理论与控制工程专业论文）随机森林在电信行业客户流失预测中的应用.pdf

摘要 随着通讯工具的同益普及，电信行业之间争取客户、扩大市场份额的竞争日 益激烈。按照最新电信行业成本结构核算，流失一个已有客户的代价是发展一个 新客户所带来利润的5 倍。因此在日趋饱和的客户市场中，如何预测客户的流失 成为工作的重中之重。 电信行业的数据具有海量且随时间递增的特点，而随机森林( r f ，r a n d o m f o r e s t ) 能有效地处理大数据集，且具有容噪性较好的特点。因此，本课题将其 引入福建移动某地区分公司的客户流失预测中。 本文首先利用随机森林算法建立电信行业客户流失预测的初步模型。在原始 数据预处理方面，我们利用r f 算法定义的异常样本度量尺度来检测异常样本， 并通过和其他两种主流异常样本检测方法的对比，来说明随机森林提供的异样样 本检测方法的优越性。利用这个方法剔除电信行业客户数据中部分明显异常的样 本，然后利用r f 算法建立初步的流失预测模型，并与移动经营分析系统自身提 供的模型进行对比，证明r f 算法的良好性能。 本文还利用r f 提供的用于衡量样本问相似程度的相似性矩阵( p r o x i m i t y m a t r i x ) 进行特征映射，进而得到每个样本基于该矩阵的放缩坐标，并用该坐标 来近似表示样本集所包含的信息。结合转导推理思想，本文提出了一种基于随机 森林坐标放缩的降维转导方法。对于标准数据库的实验表明，这样的降维转导方 法简单有效，并且能够较大程度地表达出样本间信息，是一种良好的维归约方法。 在此基础上，通过引入基于马氏距离的超椭球k 均值聚类( h c k m e a n i n r f ) 算法，我们进一步改进客户流失预测模型的性能。大量的仿真结果表明，改进的 流失预测模型具有较好的预测准确率、以及针对预测结果的部分可解释性。新模 型的预测结果可以进行解释分析，能针对不同类型的可能流失客户给出相应的挽 留措施，从而有望成为电信行业客户流失预测研究领域的一种强有力的备选方 案。 关键词：客户流失预测；随机森林；转导推理 a b s tr a c t i ti sb e c o m i n gf i e r c e ra n df i e r c e rt h a tt h ec o m p e t i t i o no ft e l e c o me n t e r p r i s e si n a b s t r a c t i n gc u s t o m e r sa n de x p a n d i n gm a r k e t , w i t ht h eg r o w i n gp o p u l a r i t yo f c o m m u n i c a t i o nt e r m i n a l s a c c o r d i n gt ot h el a t e s tc o s ta c c o u n t i n gs t r u c t u r eo ft e l e c o m i n d u s t r y , t h ec o s to fl o s i n ga ne x i s t i n gc u s t o m e ri s5t i m e sa sm u c ha st h ep r o f i tt h a ta n e wc u s t o m e rc a nb r i n ga b o u t t h e r e f o r e ，c u s t o m e rc h u r np r e d i c t i o nb e c o m e st h e m o s ti m p o r t a n tt a s ki ns u c ha ni n c r e a s i n g l ys a t u r a t e dm a n e t t h ed a t ao ft e l e c o mi n d u s t r i e sa r ea l w a y sn u m e m u sa n di n c r e a s i n gt i m e l y a s r a n d o mf o r e s tm e t h o dc a nd e a lw i t hh u g ed a t as e t se f f e c t i v e l ya n dh a v eag o o d p e r f o r m a n c eo fn o i s et o l e r a n c e ，w ei n t r o d u c et h i sm e t h o di n t ot h ec o n s t r u c t i o no ft h e c h u mp r e d i c t i o nm o d e li nt h i sp a p e r ，f o rt h er e g i o n a lb r a n c ho ff u j i a nm o b i l e f i r s t l y , w eb u i l dar a wc h u mp r e d i c t i o nm o d e lu s i n gr fm e t h o d d u r i n gt h ed a t a p r o c e s s i n g , w e u t i l i z et h ed e t e c t i o nm e t h o dp r o v i d e db yr fm e t h o dt od e t e c tt h e a b n o r m a ls a m p l e s c o m p a r e dt ot h eo t h e rc o m m o l l l yu s e da l g o r i t h m s ，t h em e t h o d b a s e do nt h er fa l g o r i t h mi sp r o v e dt ob em o l ee f f e c t i v ea n dl e s st i m ec o n s u m i n g a f t e rp i c k i n gt h ea b n o r m a lo n e so u to ft h ew h o l ec u s t o m e rs a m p l e s ，w eb u i l da r a n d o mf o r e s tt op r e d i c tt h ec h u r np o s s i b i l i t yo fc u s t o m e r s c o m p a r e dt oo t h e r e x i s t i n gm o d e l s ，t h er fm o d e lt u r no u tt ob em o r ea c c u r a t e f u r t h e r m o r e ，w i t ht h ep r o x i m i t ym a t r i xo fs a m p l e sp r o v i d e db yr f , w e c a no b t a i n t h es c a l i n gc o o r d i n a t e so fe a c hs a m p l et h r o u g ht h i sc h a r a c t e r i s t i cm a p p i n g c o m b i n e d w i t ht r a n s d u c t i o ni n f e r e n c e ，t h i st h e s i sp r o p o s e sa p r o j e c t i n gm e t h o db a s e do n t h e t r a n s d u c t i o ni n f e r e n c ea n dc o o r d i n a t e ss c a l i n gu n d e rt h ef r a m e w o r ko fr f e x p e r i m e n t sd e m o n s t r a t et h ee f f e c t i v e n e s sa n ds i m p l e n e s so ft h ep r o p o s e dm e t h o df o r d i m e n s i o nr e d u c t i o n ，a n da l s oi n d i c a t et h a ti ti sc a p a b l eo fm o d e l i n gi n f o r m a t i o no f s a m p l e s f u r t h e r m o r e ，w ec o m b i n eas u p e r - e l l i p s o i dk m e a n sc l u s t e r i n ga l g o r i t h m ，w h i c hi s b a s e do nt h em a h a l a n o b i sd i s t a n c e ，w i t ht h ea b o v ew o r k ( s h o r tf o rh c k m e a n - i n - r f ) ， t oi m p r o v et h eg e n e r a l i z a t i o n e r r o ro fc u s t o m e rc h u r np r e d i c t i o nm o d e l e x p e r i m e n t s s h o wt h a tt h ei m p r o v e dm o d e li sp m v e dt og e tab e t t e ra c c u r a c ya n d e x p l a n a t o r y a c c o r d i n g t ot h ea n a l y s e so fp r e d i c t i o nr e s u l t so fa d v a n c e dm o d e l ，w eg i v ed i f f e r e n t s u g g e s t i o n si nt e r m so f d i f f e r e n tk i n d so fc u s t o m e r s t h e r e f o r e ，i ti se x p e c t e dt h a tt h ep r o p o s e da d v a n c e dc h u mp r e d i c t i o nm o d e lw i l lb e a p p l i e da sas t r o n gc a n d i d a t et oc u s t o m e rc h u mp r e d i c t i o ni nt e l e c o m i n d u s t r i e s k e y w o r d s ：c u s t o m e rc h u mp r e d i c t i o n ；r a n d o mf o r e s t s ( r f ) ；t r a n s d u c t i o n 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成 果。本人在论文写作中参考的其他个人或集体的研究成果，均在 文中以明确方式标明。本人依法享有和承担由此论文产生的权利 和责任。 声明人( 签名) ：可p一哥 夕o d 岔年石月欲日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦门大 学有权保留并向国家主管部门或其指定机构送交论文的纸质版和电 子版，有权将学位论文用于非赢利目的的少量复制并允许论文进入学 校图书馆被查阅，有权将学位论文的内容编入有关数据库进行检索， 有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后适 用本规定。 本学位论文属于 1 保密() ，在年解密后适用本授权书。 2 不保密( ) ( 请在以上相应括号内打“4 ) 作者签名：面p 竹日期：夕d 0 9 年 作者签名：沙杪什日期：夕d 0 9 年 导师签名 翌：嬲年 6 耳2 乏e t 怎月 前言 _ j - 刖吾 随着移动通信行业市场的渗透率日趋提高，各地移动通信市场移动、联通、 电信小灵通“三国演义愈演愈烈。近两年来，中国的移动运营商一方面饱尝“价 格战”之痛，另一方面也面临着不断攀高的营销成本支出。因而各地移动运营商 都开始考虑，如何从追求规模为主的发展模式向规模效益兼顾的发展模式转变。 而实现这一转变的关键就是对用户流失率的控制，有效控制用户流失率是实现发 展模式转变的关键。有效控制用户流失率不仅可以避免新一轮价格战的发生，还 可以降低营销成本支出，并且带来更多的营销效益。经过测算，以在网用户a r p u ( 每月平均消费额) 为1 0 0 计算，新增用户的a r p u 仅为1 9 ，而流失用户的a r p u 则为9 3 ，而挽留老用户的成本只有开拓新用户成本的1 5 。从投入产出方面而言， 将营销成本后移，在用户流失控制方面投入更多的预算与资源，必然会带来更多 的投资收益。 控制用户流失率的一个有效策略是预警挽留。用户离网流失前的行为是有一 定规律可循的。利用数据挖掘技术，建立用户流失预测模型，定期产生可能流失 的高危用户名单，并通过分析这些用户的移动通信消费行为特点，深层次的把握 其需求，设计针对性的挽留政策，并通过客户经理、外呼人员等进行一对一的客 户关怀和预警挽留活动，对于挽留客户、降低流失率具有十分积极的意义。由于 预警挽留采取一对一的沟通方式，针对性比较强，也提高了挽留的成功率。 本课题是福建省移动通信公司某下属单位的合作项目，数据来源于该分公司 的经营分析系统。本文将数据挖掘领域的新技术随机森林应用于建立电信行 业客户流失预测模型，并在随机森林的框架下，提出基于k 均值聚类算法的改 进模型。研究结果表明，所建立的模型能够较好的容忍噪声，具有更高的分类准 确率，且模型的预测结果具有一定的可解释性。 本文的内容具体组织如下： 第一章介绍选题的背景及意义以及电信行业客户流失预测研究的现状，指 明各种方法的优缺点及其适用性。 第二章对随机森林算法做了较完整的描述，并介绍了随机森林的泛化误差 的刻画。 随机森林臼：电信行业客户流失预测中的应用 第三章介绍了利用随机森林建立流失预测初步模型的过程，并重点说明了 基于该方法的异常样本检测方法、以及对于类不平衡数据的处理。 第四章研究了随机森林框架下的坐标放缩，提出了随机森林框架下的超椭 球k 均值聚类算法，并建立了客户流失预测的改进模型。 第五章总结了本课题的研究工作，分析了存在的问题，以及将来可以继续 深入的方向。 第一章电信行业客户流失预测 第一章电信行业客户流失预测 1 1 选题的背景及意义 电信行业是全球经济中增长最快的行业，同时也是竞争最激烈的行业。随着 全球经济一体化进程的推进，电信行业的竞争格局发生了重大改变，由原来少数 几个电信企业在局部市场的竞争，转变为众多电信企业对全球市场的争夺，因而 竞争也变得空前的残酷。面对来自国内外强大竞争对手的压力，积累多年的客户 资源成为电信运营商最大的竞争优势。电信企业应以客户为中心，深入的了解客 户、引导客户、留住客户。按最新电信行业成本结构核算，流失一个已有客户的 代价是发展一个新客户所带来利润的五倍。因此在注重吸引和发展新客户的同 时，更要重视留住现有的客户。留住现有客户的前提是了解现有客户，发现有价 值的可能流失的客户，也就是预测客户流失的可能性，然后进一步针对流失可能 性大的有价值客户采取相应的客户挽留措施，预防客户流失，从而提高企业的经 营效益。 我国的移动通信企业经过前几年的高速发展，目前正步入缓慢增长期。因此 分析客户流失原因、增加现有客户满意度、减少客户流失机率、充分占有市场是 移动通信企业在激烈市场竞争中制胜的关键。目前各电信运营商拥有庞大的客户 群体，但面对大量客户流失或束手无策，或仅根据目前客户数据库中可见的特征 一简单分析，无法有效地控制客户流失。 移动通信市场的客户流失( c h u r n ) t 1 j 是这一行业运营商面对的重要问题。 c h u r n 是无线电信行业的术语，是指客户取消无线通讯公司的某项服务，而接受 竞争者提供的类似的服务。客户流失这一名词在移动电话业中是指客户从一个运 营商转向另一个运营商。由于高度不稳定发展的电信市场和有限制的竞争，许多 客户从原来运营商流失到新的运营商那里，经常是为了得到成为新客户而得到的 更好的利益，例如得到最新最好的移动电话和便宜的话费等。 传统上i l j 国外移动运管商认为新客户在最初两个月内流失的概率最大，大约 为1 0 左右，所以运营商会建立一个呼叫中心，在客户使用移动电话一个月左右 后，主动和客户联系，但是这样的方法是不合算的。再后来有一些运营商开始用 随机森林在电信行业客户流失预测中的应用 传统的数理统计模型来分析客户资料，希望能够发现一些规律，但是效果不好。 因为统计学是- f 7 比较保守的学科，现代统计学是以模型为主导地位，符合一定 的概率分布。然而需要挖掘出来的可能流失的客户往往是小部分人，不可能符合 统计上的大数定律，所以统计学很难解决预测客户流失问题。为了保留客户，运 营商还会用一些经济方法，像折扣、返回费用等。总之没有一个系统的方法来预 防客户的流失。 如何才能预防、减少客户的流失? 数据挖掘【2 】技术的蓬勃发展为解决这一类 问题指明了方向。利用数据挖掘技术分析己发生流失的客户在流失前的通话行 为，找出引起流失的一些规律性知识，电信企业可以根据这些规律有针对性的制 定相应的策略，在客户流失之前预先采取行动，来减少或消除这些客户发生流失 的可能性。 经过几年的发展。电信企业内部已建立起相对完善的客户数据库，积累了大 量的数据，这些激增的数据背后隐藏着许多重要的信息【3 1 。将数据挖掘技术这个 目前数据仓库领域最为强大的数据分析手段有效运用于电信企业客户流失预测 中【4 l ，将为企业解决这一难题。本文所作的工作，正是在上述课题背景的驱动下 建立和实施的。 1 2 电信行业客户流失预测研究的现状 电信业客户流失预测研究开始于上世纪9 0 年代。我国学者在本世纪初开始 研究电信业客户流失预测方法。经过十几年的发展，电信业客户流失预测研究技 术取得了很大进步。通过对目前客户流失预测方法研究发现，目前主要把电信业 客户流失预测看作分类问题。这时客户流失预测的提法是：根据已知所属类别的 若干个客户的n 个特征指标，去判别一个未知类别的客户属于两个( 或多个) 不同 类别中的哪一类别。根据智能化程度的高低，其研究的方法可分为传统分类方法 和人工智能分类方法。传统分类方法【5 】包括：决策树1 6 l 【7 1 、l o g i s t i c 回归( l d 西s t i c r e g r e s s i o n ) 引、贝叶斯分类器( n a j f 、，eb a y e s i a nc l a s s i f i e r ) 9 l 【1 0 】和聚类( c l u s t e r i n 曲【1 1 1 。 该类方法的主要特点可以对定类和连续性的客户数据进行处理，且对于所构建的 第一章电信行业客户流失预测 模型有较强的可解释性。随着客户流失预测研究的深入，上述研究方法的不足就 逐渐暴露出来，主要体现在以下三个方面： ( 1 ) 真实的电信业数据中的客户类别是非对称的，传统分类方法无法通过自 身的完善来对样本进行加权，因此在进行预测时，只有假设数据类别是对称的或 采用过抽样等方法，这极大地影响了预测效果。 ( 2 ) 在处理大规模、高维度、含有非线性关系、呈非正态分布、有时间顺序 的客户数据时，其效果不理想。 ( 3 ) 不能保证学习和泛化能力，缺乏灵活性。 后面两个问题的产生促使了人们考虑在电信行业客户流失预测中引入人工 智能技术，以改善预测模型的性能和提高识别准确率。人工智能分类方法包括： 人工神经网络( a n i f i e i a ln e u r a ln e t w o r k ，a n n ) 1 1 2 1 1 1 3 l 、自组织映射( s e l for j 萨i 此i 1 1 9 m a p s ，s o m ) 1 1 4 1 、进化学习( e v o l u t i o n a r yl e a n i n g ，e l ) 算、法1 1 5 】、支持向量机【1 6 】等。 在引入上述人工智能技术后，尽管客户流失研究者做了不少工作，取得了一些研 究成果，但这些方法均存在这样或那样的不足，或者说在电信业客户流失预测中 还存在着一些迄待解决的问题，这些不足或问题主要集中在以下几个方面： ( 1 ) 这些方法不能从理论上保证预测模型的泛化能力，这使得对于经过训练 后的预测模型，对于新的客户数据集没有稳定的预测效果。 ( 2 ) 这些方法主要依靠的是经验风险最小化原则，其重要的缺点为：利用经 验风险代替期望风险来选择决策函数，并没有经过严格的证明与充分的论证，只 是一种认为合理的方法；容易产生“过学习”问题，这是盲目追求小误差而导 致泛化能力的下降的必然结果。 ( 3 ) 电信行业积累的数据集由于各种因素包含较多的噪声，各种研究算法无 法根本的克服噪声的影响。 电信业客户流失研究的整个发展过程来看，国外从上世纪九十年代中期就开 始了客户流失预测和影响因素分析的研究。从有关文献和报告中可以了解到，我 国对电信业客户流失预测和影响因素分析水平与美国等发达国家还有较大差距。 导致目前这种现状的根本原因在于我国缺乏电信业客户流失预测和影响因素分 析的系统理论研究，缺乏能有效支持电信业客户流失预测和影响因素分析的理论 依据。 随机森林打i 电信行业客户流失预测中的廊用 国外电信企业的成功经验表明：在信息经济快速发展的当今社会，能否及时 发掘并运用大量的信息是企业能否成功的关键之一。中国电信行业面临着国际化 的竞争，而电信行业采用的计算机处理系统已有十多年，企业拥有大量详实且丰 富的数据，如计费数据、客户数据和网管数据等，这为数据挖掘提供了基础。在 国内各大电信运营商中数据挖掘应用的研究正在广泛的开展。中国移动通信集团 公司作为国内最大的电信运营商，目前正在构建各省公司的经营分析系统，已成 为全球最大的两级数据仓库系统，形成系统容量1 6 1 6 t b 、数据容量8 4 2 t b 的规 模。系统采用了数据仓库和数据挖掘技术进行数据的深层次研究，取得了较好的 效果，具体应用集中在客户挽留和营销案评估的专题应用上。 尽管国内的电信行业数据挖掘应用的研究已经取得了比较明显的进展，在某 些领域得到初步的实际应用。但距离实用型研究还有一段距离。各种数据挖掘技 术在数据仓库基础上进行的数据分析仍较为基础。例如中国移动公司的移动经营 分析系统经过几年的不断发展，已经形成强大的数据存储查询能力，但其在客户 流失预测分析方面仍使用较为简单的分类学习器，例如决策树、神经网络算法等。 这些基础算法均存在上述各种问题，且模型准确率仅维持在6 0 左右。因此客户 流失预测模型领域的实际应用研究急需引入更加强大的算法。 基于以上所述的研究需求，本文引入一种能较好容忍噪声，能同时处理连续 属性和类别属性，并且具有较强鲁棒性的新型组合分类算法一一随机森林 ( r a n d o mf o r e s t s ，r f ) ，并在后续的章节中应用于电信行业的客户流失预测中。 第二章分类问题和随机森林算法简介 第二章分类问题和随机森林算法简介 客户流失预测是根据电信企业得到的有关客户信息，即包含各种属性的数 据，预测客户可能的流失离网行为，实质是一个分类问题。我们的工作是，根据 电信企业提供的有关客户数据，利用分类学习算法，建立分类预测模型。 2 1 分类问题、分类器和分类器组合 2 1 1 分类问题和分类器 分类问题是学习问题中一种较为简单的情形。学习问题是指依据经验数据选 取所期望的数据间的依赖关系。基于实例学习的一般模型包括3 个组成部分，如 图2 1 所示： ( 1 ) 数据( 实例的发生器g ) ( 2 ) 目标算子s ( 有时也称为训练器或训练器算子) ( 3 ) 学习机器( 圳) 图2 1 基于实例学习的模型 发生器g 是源头，它确定了训练器和学习机器工作的环境。本文考察最为 简单的环境：g 依据某一未知( 但固定) 的概率分布函数f o ) 独立同分布地产 生向量x x ，这里xc r “是输入空间。这些输入向量输入到目标算子( 训练器) ， 目标算子返回输出值y 。这里，将向量x 变换成y 的目标算子是客观存在但未知 的。 随机森林舀i 电信行业客户流失预测中的应用 学习机器观测到n 个点对( 训练集) ： ( _ ，y 。) ，( ，儿) ) ，它包含输入向 量x 和i ) j l 练器响应y 。在学习阶段，学习机器构造一个算子，用于预测向量薯对 应的响应咒，即对目标算子构造一个适当的逼近。 分类问题可表述如下：训练器观测到所出现的事件，并确定每个观测事件属 于k 类中的哪一类；我们需要构造一个机器，它在观测y i ) j l 练器的分类情况后， 能以与训练器近似的方式完成分类工作。 在分类问题中，通常假设样本( 点对) “，咒) x x y 是依据某一未知但固 定的联合分布d 产生的， 这里y f f i 1 , 2 ，七 是类别空间( y 也可为数值响应) 。 当k = 2 时，称为两分类( b i n a r yc l a s s i f i c a t i o n ) 问题：当k 2 时，称为多类分类 ( m u l t i c l a s sc l a s s i f i c a t i o n ) 问题。两分类问题通常取y 一 + 1 ，一耐或y 一 0 ，1 。设 学习机器对目标算子的逼近为，：x _ y ，厂称为分类预测函数，也即通过学习 得到的分类器( c l a s s i f i e r ) 。分类器对输入向量的响应可能是类别标号，也可能 是该输入向量属于某一类别的后验概率或其它数值响应。 首先，学习算法利用训练样本集s “，y 。) ，h ) ) 中包含的信息，学习 7 得到一个分类器，：x _ y ；然后，再使用分类器，对新样本( 即未被学习算法 使用过的样本) 的类别进行判别。记昂( ，o ) 一y ) 为在联合分布d 下分类器厂对 样本错判的概率，分类学习算法的目标就是构造一个，使得昂( ， ) 一y ) 较小。 定义2 1 分类器，的泛化误差( g e n e r a l i z a t i o ne r r o r ) 为： g e r r o r 一弓( ，o ) - y ) 定义2 2设s 一 “，y 。) ，) ) 为某一样本集，分类器，在该样本集上 的分类误差为： e r r o r 。万1 。而嘉1 肘见， 第二章分类问题和随机森林算法简介 其中n 为样本集规模( 样本总数) ；1 i ，而，啊 为指示函数，当，( ) - y i 为真 时，1 ) - ，j l 值为1 ，反之为0 。 分类器在训练样本集上的分类误差称为训练误差( t r a i n i n ge r r o r ) 。 2 1 2 分类器组合 分类器组合方法的结构框图如图2 2 所示。图2 2 中的分类器1 历是在给 定数据集上学习得到的m 个单体分类器，我们称之为“分量分类器”( c o m p o n e n t c l a s s i f i e r ) 。训练分量分类器所用的学习算法称之为“元学习算法”( m e t a 1 e a r n i n g a l g o r i t h m ) 。 图2 2 中，最终的分类结果由各分量分类器的输出按照一定的方式( 组合规 则) 进行组合得到。由分量分类器集合和组合规则构成的分类系统称为组合分类 器( c l a s s i f i e rc o m b i n a t i o n ) 。 ，j 分类器l 分 输 数 勿髅靴心 类 入 据器最 向预组终 量处 ； a 结口 j 理规果 1 分类器腕r 则 图2 2 分类器组合方法的结构框架 随机森林是一个组合分类器算法，它的元学习算法采用分类回归树( c a r t ) ， 并由b a g 舀n g 方法产生各个不同的训练集，用以生成各分量分类器，最后通过简 单多数投票决定最终分类结果。下面简要介绍决策树和b a g g i n g 方法的相关理 论。 随机森林4 ：电信行业客户流失预测中的应用 2 2 决策树 决策树( d e c i s i o nt r e e ) 是树型分类器，由根节点，内部节点，树干和叶节 点组成；根据内部节点不同的分裂方法，可将决策树分为两大类：基于信息熵的 决策树( 如：i d 3 、c 4 5 等) 和基于基尼指数的决策树( 如：c a r t ) 。 2 2 1 决策树方法简介 决策树方法就是利用训练集生成一个测试函数，根据信息论中的信息增益寻 找示例数据中具有最大信息量的属性字段，建立决策树的一个节点，再根据该属 性字段的不同取值建立树的分支；在每个分支子集中重复建立下层节点和分支， 这样便生成一棵决策树；然后对决策树进行剪枝处理，最后把决策树转化为规则， 利用这些规则可以对新样本进行分类。决策树作为一种非参数的识别技术，具有 许多优点，具体表现在：可以自动进行变量选择，降低维数；充分利用先验信息 处理数据间非同质的关系；分类结果表达形式简单易懂。 国际上比较有影响的决策树方法有i d 3 算法和c a r t 算法。i d 3 算法n 7 1 是 q u i n l a n 于1 9 7 9 年提出的，该算法是基于信息熵的决策树分类算法，它采用自 顶向下不回溯策略，以信息熵的下降速度作为选取测试属性的标准，根据属性集 的取值选择实例的类别。算法c 4 5 【1 8 】是i d 3 的扩展，它将分类领域从类别属性 扩展到数值型属性。 c a r t 算法【1 9 】是由b r e i m a n 等人于1 9 8 4 年提出的，该算法以基尼指数作为 内部节点的分裂标准。 美联储在对e q u a l c r e d i to p p o r t u n i t ya c t 的解释中i 冽，称决策树方法是在信 用系统中经过实证检验、并且在统计意义上完美的方法。而现行各电信企业经营 分析系统中客户流失预测方法的内核算法均采用决策树算法。 2 2 2 分类回归树( c a r t ) c a r t 由分类树( c l a s s i f i c a t i o nt r e e ) 和回归树( r e g r e s s i o nt r e e ) 两部分组成；分 类树用于结果变量是类别变量的数据分析，回归树则用于结果变量是连续变量的 数据分析。c a r t 以基尼指数作为分裂标准，能够将降低数据无序度的属性挑选 第二章分类问题和随机森林算法简介 出来。在建立c a r t 树时，每个分裂属性的选择是根据它在不同预测下对样本数 据划分的好坏程度来进行的。 基尼指数1 2 1 】是一种不纯度分裂方法，它能适用于类别、二进制、连续数值等 类型的字段，具体算法思想是：假设集合丁包含k 个类别的记录，那么其g i n i 指 标为： a i n i ( t ) 小善l f ) 】2 ( 2 - 1 ) p ( ji t ) 为类别j 在t 节点处的概率，当g i n i ( t ) 最小为0 时，即在此节点处 所有记录都属于同一类别，表示能得到最大的有用信息；当此节点中的所有记录 对于类别字段来说均匀分布时，g i n i ( t ) 最大，表示能得到最小的有用信息。如果 集合分成z 个部分，那么进行这个分割的g i n i 指数就是： 锄阶套鲁锄秭 ( 2 - 2 ) 其中，是子节点的个数，n i 是在子节点f 处的样本数，刀是在母节点处的样本 数。基尼指数的基本思想就是：对于每个属性都要遍历所有可以的分割方法，若 能提供最小的g 伽，就被选择作为此节点处分裂的标准；此时再按对应的属性 值来分裂，并且根据每一个属性值创建树枝；进一步向下划分样本，直到满足停 止条件。通常是给定叶节点纯度的一个阈值，大于等于该阈值时停止划分。 根据给定的样本集s 构建分类树由以下三步组成：( 1 ) 使用s 构建最大树 l 一使得树中每一个叶节点要么很小( 节点内部所包含样本个数小于给定值) ， 要么是纯节点( 节点内部样本属于同一类) ，要么不再存在属性可以作为分支属 性；( 2 ) 使用修剪算法构建一个有限的、节点数目递减的有序子树序列；( 3 ) 使 用评估算法从子树序列中选出一棵最优树，作为最终的决策树。 2 3b a g g i n g 方法 b a g g i n g 算法1 2 2 】由b r e i m a n 于1 9 9 6 年提出，是一种通过操作训练样本集来 生成各异的分量分类器的算法。 随机森林在i 乜信行业客户流失预测中的膨用 b a g g i n g 算法的基础是自助抽样法( b o o t s t r a ps a m p l i n g ) ，即从原始样本集s 中有放回地随机抽取训练样本集 s e t ，t s e t 中的样本个数与s 相同。b a g g i n g 算法的主要思想是：给定一个元学习算法和一个原始样本集s ，让该学习算法训 练多轮，每轮的训练集rs e t 是通过上述的自助抽样法从原始样本集s 得到的， 这样一个初始样本在某轮的训练集中可能出现多次或根本不出现。 在使用b o o t s t r a p 方法对s 进行抽样时，5 中每个样本未被抽取的概率为 ( 1 1 n ) ，这里为原始样本集s 中样本的个数。当足够大时， ( 1 1 n ) 一0 3 6 8 ，这表明原始s 中接近3 7 的样本不会出现在r _ s e t 中。b a g g i n g 方法通过构造不同的训练集增加了分类器之间的差异，从而提高组合分类器的泛 化能力。通过丁轮训练，得到一个分类器序y i j a ，厶，厂r ) ，再用它们构成一个 多分类器系统，该系统的最终分类结果采用简单多数投票法或简单平均法得到。 b r e i m a n 指出，元学习算法的稳定性对于b a g g i n g 能否提高总体预测准确率 是关键的。b a g g i n g 对不稳定的元学习算法能提高预测的准确率，而对稳定的元 学习算法效果不明显，有时甚至会使预测精度降低。学习算法的不稳定性，是指 当训练集有较小变化时，学习算法产生的分类预测函数将发生较大的变化，以及 预测准确率也发生较大的变化。b r e i m a n 指出，分类树、神经网络是不稳定的， 而缸近邻、n a i v eb a y e s 方法是稳定的。 b r e i m a n 还从偏差( b i a s ) 和方差( v a r i a n c e ) 的角度对b a g g i n g 的泛化误差 进行了分析。他指出，不稳定预测函数的偏差较小，而方差较大。b a g g i n g 正是 通过减小方差来减小泛化误差的。 随机森林是分类树的组合，用b a g g i n g 方法产生各异的训练集，由于分类树 是不稳定的算法，因此分类树与b a g g i n g 方法结合能有效减小方差，从而减小组 合分类器的泛化误差。 2 4 随机森林 随机森林【2 3 1 ( r a n d o mf o r e s t s ，r f ) 是b r e i m a n 于2 0 0 1 年提出的一个新的组 合分类器算法。他采用分类回归树( c a r t ) 作为元分类器，用b a g g i n g 方法制 造有差异的训练样本集，并且在构建单棵树时，随机地选择特征对内部节点进行 第二章分类问题和随机森林算法简介 属性分裂。b a g g i n g 方法和c a r t 算法的结合，再加上随机选择特征进行属性分 裂，使得r f 能较好容忍噪声，并具有较好的分类性能。 2 4 1 随机森林的定义 随机森林是树型分类器伽似，o k ) ，七= 1 ，) 的集合，元分类器h ( x ，吼) 是用 c a r t 算法构建的没有剪枝的分类回归树；x 是输入向量， 嚷) 是独立同分布的 随机向量，随机向量吼决定单棵树的生长过程：采用简单多数投票法( 针对分类) 、 或单棵树输出结果的简单平均( 针对回归) 得到r f 的最终输出。 2 4 2 随机森林算法 在传统的c a r t 算法中，每个内部节点都是原始数据集的子集，根节点包含 了所有的原始数据；而在每个内部节点处，从所有属性中找出最好的分裂方式进 行分裂；然后对后续节点依次进行分裂，直到叶子节点；最后通过剪枝使测试误 差最小。与c a r t 算法不同，随机森林中单棵树的生长可概括为以下几点1 2 4 】： ( 1 ) 使用b a g g i n g 方法形成各异的训练集：假设原始训练集中的样本数为 ，从中有放回地随机选取个样本形成一个新的训练集，以此生成一棵分类 树。 ( 2 ) 随机选择特征对分类回归树的内部节点进行分裂：假设共有膨个特征， 指定一个正整数m t r y c 肘；在每个内部节点，从m 个特征中随机抽取m t r y 个 特征作为候选特征，选择这r n t r y 个特征上最好的分裂方式对节点进行分裂。在 整个森林的生长过程中，m t r y 的值保持不变。 ( 3 ) 每棵树任其生长，不进行剪枝。 随机森林的输出组合方法有简单多数投票法( 针对分类) ，和单棵树输出结 果的平均( 针对回归) 。 随机森林的泛化误差依赖于以下两个因素( 详细证明见2 4 3 ) ： ( 1 ) 森林中任意两棵树的相关度( c o r r e l a t i o n ) 。减小不同树之间的相关度可 以减小森林的总体误差率。 随机森林相：i 也信行业客户流失颅测中的膨用 ( 2 ) 森林中单棵树的分类效能( s t r e n g t h ) 。具有低误差率的分类树为强分 类器，增加单棵树的分类效能能够降低森林的总体误差。 为提高r f 的预测准确率，应减小树与树之间的相关度，而增大单棵树的分 类效能。使用b a g g i n g 方法形成新的训练集和随机选择特征进行分裂，使得随机 森林能较好地容忍噪声，并且能降低单棵树之间的相关性；单棵树不剪枝能得到 低的偏差，保证了分类树的分类效能。b r e i m a n 在文【2 5 1 中通过实验证明：在标 准数据集上，随机森林模型明显优于单个分类回归树模型。 2 4 3 随机森林的泛化误差 一个分类器能证确分类训练集之外数据的能力称为泛化性，这正是各学习算 法要优化的目标。泛化误差即分类器对训练集之外数据的误分率。b r e i m a n 通过 定义随机森林的间隔函数，以大数定律为理论基础证明得到1 2 4 j ：随着森林中树 的数目的增大，r f 的泛化误差趋向一个有限上界。 1 、随机森林的收敛性【2 4 】 对于给定的分类器讹o ) ，h 2 0 ) ，h o ) ) ，输入向量石和其对应的输出_ ) ，定 义样本点( x ，y ) 的间隔函数如下： m 9 0 ，y ) a v k l ( ，吐 ) - ) ，) 一m a x a v f l ( o ) - j ) - ， 上式中，( ) 为指示函数，a v e ( ) 为取平均值。间隔m g ( x ，y ) 衡量了分类器集 合将特定样本z 分对的平均票数，与将其错分为其它类的平均票数之最小差值； 这个间隔越大，分类器的性能越好。 分类器的泛化误差可表示为： p e tb y ( m g ( x ，y ) o ) ( 2 - 3 ) ( 2 3 ) 式中的脚标x ，y 表明概率是在x ，】，空间上求得的。 在随机森林中，吃o ) - h ( x ，吼) ，当森林中树的个数足够大时，( 2 - 3 ) 式遵 循强大数定律。 定理2 1 随着森林中树的增多，在所有序列岛上，咫几乎处处收敛于： 第二章分类问题和随机森林算法简介 b y ( ( 乓q o ，0 ) 一y ) - m 锻p o ( o ，0 ) 。脚 0 ) 其中，矽是对应单棵决策树的随机向量，h ( x ，0 ) 为基于x 和0 的分类器的输 出。 定理2 1 解释了当森林中树的数目增多时，随机森林为什么不会过拟合，而 是得到一个有限的泛化误差值。 2 、分类效能和相关度 随机森林的泛化误差上界可以看作依赖于两个参数：单棵树的分类效能和树 与树之间的相关度。这两个参数的相互作用为我们理解随机森林的工作原理提供 了理论基础。 定义2 3 随机森林对于样本( x ，y ) 的间隔函数为： m r ，y ) 。p o 伪g ，0 ) 一y ) 一m 硼晶q 0 ，0 ) 一j ) j a y 分类器集合伽 ，口) ) 的分类效能为： s b y m r 0 ，y ) 假设s 之0 ，由契比雪夫不等式可知： p e sv 缸m r ) s 2( 2 4 ) ( 2 4 ) 式中的v a r ( m r ) 是随机森林的间隔函数m r ( x ，y ) 的方差。下面的推导中， 将给出v a r ( m r ) 的一个更为直观的表达。 设j o ，y ) - 缸g m 御出q o ，日) 一j ) ，此时， i c y 胁， ，y ) 一p o ( o ，0 ) 一y ) 一b ( j l ，0 ) = j ( x ，) ，) ) 1 e o 1 ( h ( x ，臼) 1y ) 一1 ( h ( x ，日) 一，o ，y ) ) 】 定义2 4 元分类器的间隔函数为： r m g ( o ，x ，y ) 一l ( h ( x ，口) - y ) 一1 ( h ( x ，口) 。j ( x ，y ) ) 因此，m r ( x ，y ) 是朋g ( 口，x ，y ) 在e 上的期望值。 随机森林稍! 电信行业客户流失预测中的腑用 对于任意的函数厂，有以下恒等式： 【e ，( p ) 】