（计算机科学与技术专业论文）一种基于最大团的群体客户流失预测算法.pdf

一种基于最大团的群体客户流失预测算法 摘要 当前，在我国迅速发展的移动通信市场中，中国移动，中国联通 等几大电信运营商正在展开激烈的市场竞争，而客户是这场竞争中的 焦点。客户流失是每个通信企业中都普遍存在的一个严重问题，它使 得客户的生命周期不断缩短，严重影响了企业的发展，不仅给运营商 的收入造成损失，也给企业的经营带来压力。在这种形势下，如何防 止客户流失，完善客户挽留工作，越来越成为运营商工作的重点。如 何根据客户的消费行为预测客户的流失，并结合竞争环境的变化制定 有效的客户挽留和赢回策略，是通信企业市场经营的重要任务，也是 通信客户研究咨询领域的一个重要课题。 客户流失，作为客户生命周期管理的个重要阶段，一直是学术 界和工业界的研究热点，并已经成为客户关系管理的一个重要研究方 向。客户流失问题包括流失产生原因，流失分类，流失预测，客户挽 留等多个方面，而其中如何准确地对客户流失进行预测，则是客户流 失分析的核心问题。相关工作表明，传统的客户流失预测算法大多是 将历史通话记录，用户资料，通话费用等多类数据归纳为用户属性， 利用决策树，神经网络等分类算法，进行客户流失的预测分析，然而， 这些方法具有一定的局限性。首先，为了进行分类算法的需要，必须 事先进行大量的多维数据准备，复杂的数据准备可能占用了整个分析 过程的大部分工作，这对于海量的电信数据而言，可能具有很大的难 度。其次，这些方法大多是将每个用户作为一个孤立的个体进行考虑， 并没有考虑到客户之间的相互联系，然而客户之间的相互联系对于客 户流失预测分析来说是一种非常有价值的信息，不应该被忽视。 本文侧重于从客户的相互联系出发，提出了一种新颖的客户流失 预测算法。通过利用客户之间的相互通话联系，结合客户的历史流失 记录，运用最大团的相关知识，进行客户通话行为的时间序列分析， 从客户的通话趋势预测潜在的流失客户。这种新方法的数据准备仅仅 需要所有的历史通话记录，而不需要进行客户资料，通话时长，通话 费用的处理，大大简化了数据准备的工作。并且，我4 1 n 用了用户间 的相互联系进行预测分析，将用户间的相互联系通过最大团的信息进 行数量化衡量，较好的提高了客户流失预测的效果。我们将这一算法 应用于某市的实际客户流失分析中，取得了较好的预测效果，验证了 算法的正确性和有效性。 关键词：客户流失，群体流失，流失预测，群体关系，最大团 ag r o u pc u s t o m e rc h u r np r e d i c t i o na l g o r i t h m b a s e do nm a x i m u m c l i q u e a b s t r a c t n o w a d a y s ，t e l e c o mc o m p a n i e ss u c ha sc h i n am o b i l ea n dc h i n a u n i c o r na r ef a c i n gad r a s t i c c o m p e t i t i o ni nt h e m a r k e to fm o b i l e ，a n da m o n gt h i sc o m p e t i t i o nc u s t o m e ri st h ef o c u s c u s t o m e r c h u r ni sav e r ys e r i o u sp r o b l e mw h i c ha l m o s te v e r yt e l e c o mc o m p a n ym u s tf a c en o w c h u m m a k e sc u s t o m e r s l i f ec y c l es h o r t ，w h i c hr e s t r i c t sc o m p a n i e s d e v e l o p m e n tg r e a t l y i tn o to n l y b r i n g sl o s st o t h ec o m p a n i e s i n c o m e ，b u ta l s og r e a tp r e s s u r et ot h ec o m p a n i e s m a n a g e m e n t u n d e rt h i s s i t u a t i o n ，h o wt op r e v e n tc u s t o m e rc h u r na n dp e r f e c t t h ew o r ko fc u s t o m e r s d e t a i n m e n ti sb e c o m i n gm o r ea n dm o r ei m p o r t a n tt ot h et e l e c o mc o m p a n i e s i th a sb e c o m eak e y t a s kh o wt op r e d i c tc u s t o m e r s c h u mb a s e do nt h e i rb e h a v i o r sa n dm a k ee f f e c t i v ec u s t o m e r s d e t a i n m e n ts t r a t e g i e sa c c o r d i n gt ot h ev a r i a t i o no fc o m p e t i t i o ne n v i r o n m e n t t h i st a s ki sa l s oa n i m p o r t a n ts u b j e c to f t e l e c o m c u s t o m e rr e s e a r c ha n dc o n s u l t a t i o n a sa ni m p o r t a n tp h r a s eo f t h em a n a g e m e n to f c u s t o m e rl i f ec y c l e c u s t o m e rc h u mi sa l w a y s t h er e s e a r c hh o t s p mo ft h ea c a d e m i aa sw e l la st h ei n d u s t r y f u r t h e r m o r e t h es t u d yo f c u s t o m e r c h u mh a sb e c o m eav i t a lr e s e a r c hd i r e c t i o no fc 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 eq u e s t i o no f c u s t o m e rc h u mi n c l u d e ss e v e r a l p a r t s ，s u c h a sc h u mr e a s o n s ，c h u mc l a s s i f i c a t i o n ，c h u r n p r e d i c t i o n ，c u s t o m e rd e t a i n m e n ta n ds oo n b e s i d e s ，h o wt om a k ep r e c i s ep r e d i c t i o no nc u s t o m e r c h u r ni st h ec o r ep r o b l e mo ft h ea n a l y s i so ft h ec u s t o m e rc h u m r e l a t e dw o r ks h o w sm o s t t r a d i t i o n a lc h u m p r e d i c t i o na l g o r i t h m sf i r s t l y s u m m a r i z eh i s t o r i c a lc a l l r e c o r d ，c u s t o m e r i n f o r m a t i o na n dc a l lf e e st os e v e r a ln e wc u s t o m e ra t t r i b u t e s ，t h e nm a k ec h u r np r e d i c t i o nb ys o m e d a t am i n i n gm e t h o d so fd e c i s i o nt r e ea n dn e u t r a ln e t w o r k h o w e v e r , t h e s em e t h o d sh a v es o m e l i m i t a t i o n s ，f i r s t l y ，b e f o r et h ec l a s s i f i c a t i o na l g o r i t h m sa r ea p p l i e d ，w em u s tm a k em u c hd a t a p r e p a r a t i o no nt h em u l t i - d i m e n s i o n st e l e c o md a t a t h i sc o m p l i c a t e dd a t ap r e p a r a t i o nm a yb ea g r e a tp a r to f t h ew h o l ea n a l y s i sw o r k i ti sp r o b a b l yv e r yd i f f i c u l ta n dl i m i t e dt ot h eh u g et e l e c o m d a t a s e c o n d l y , t h e s em e t h o d s m o s tt a k ee a c hc u s t o m e ra sa ni n d i v i d u a la n dd o n tt a k et h em u t u a l i n f o r m a t i o nb e t w e e nc u s t o m e r si n t oa c c o u n t h o w e v e r , t h er e l a t i o na m o n gd i f f e r e n tc u s t o m e r si s v e r yv a l u a b l ei n f o r m a t i o n ，a n ds h o u l d n e v e rb eo v e r l o o k e d t h i s p a p e re m p h a s i z e s o nt h em u t u a lr e l a t i o na m o n gc u s t o m e r s ，a n dp r e s e n t san o v e l p r e d i c t i o na l g o r i t h m o nt h ec u s t o m e rc h u mp r o b l e m w eu t i l i z et h em u t u a lc u s t o m e rr e l a t i o n sa n d i n t e g r a t eh i s t o r i c a lc a l lr e c o r d s ，a n dt h e nm a k eas i m p l et i m e s e r i e sa n a l y s i so ne a c hc u s t o m e r s c a l lb e h a v i o l a s t l yw ep r e d i c tt h el a t e n tc h u mc u s t o m e rf r o mt h ec u s t o m e r sc a l lt r e n d d a t a p r e p a r a t i o n o f t h i sn e wm e t h o d so n l yn e e d sh i s t o r i c a lc a l lr e c o r d ，a n dn e e d n tc o s tt o om u c ht i m e o nt h ep r o c e s so f c u s t o m e ri n f o r m a t i o n ，c a l lt i m ea n df e e s ，w h i c hs i m p l i f i e st h ed a t ap r e p a r a t i o n g r e a t l y w ea p p l yt h em u t u a lc u s t o m e ri n f o r m a t i o ni n t h ec h u r np r e d i c t i o n ，a n dc a l c u l a t et h e m u t u a lc u s t o m e ri n f o r m a t i o nf r o mt h ek n o w l e d g eo fm a x i m u mc l i q u e m o r e o v e r , w ea p p l yt h i s n e wc u s t o m e rc h u r np r e d i c t i o na l g o r n h mi nar e a lc u s t o m e rc h u r np r o b l e m ，a n dg e tag o o d e v a l u a t i o nr e s u l t t h ee x p e r i m e n t a lr e s u l t sp r o v e dt h ec 0 1 t c c t n e s sa n dv a l i d i t yo f o u r a l g o r i t h m k e yw o r d s ：c u s t o m e r c h u m ，g r o u pc h u m ，c h u mp r e d i c t i o n ，g r o u pr e l a t i o n ，m a x i m u me l i q c e 独创性( 或刨新性) 声明 本人声明所呈交的论文足本人在导师指导下进行的研究工作及耿得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谫 意。 中请学能论文与资料若有不实之处，本人承担一切相关责任。 本人签名茎：熏生 日期：坠过：! ! 垒 芙于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即；研究生在校 攻读学何期间论文t 作的知识产权单位属北京邮电大学。学校有权保留并向国家有关部门或 机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅：学校可以公布学位论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学位论文。( 保密的学位 论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论文注释：本 学位论文不属于 本人签名 导师签名 书。 日期： 日期： 叶、如 五遮0 冷 种基于最大团的群体客户流失预测算法 1 1 论文背景 第一章绪论 随着我国移动通信市场的进一步放开，市场竞争日趋激烈，通信企业投入大 量时涮和人力、物力去发展新客户。然而中国移动通信市场在经过连续几年的高 速发展之后，移动通信普及率已经超过2 0 ，移动通信市场已经逐步步入一个缓 慢增长期，即在大量客户入网的同时，又有大批客户离网流失；每月注册客户数 与在网活动客户数相差悬殊；涌现大批零次话务客户；业务与收入总量增长相对 趋缓，出现“增量不增收”。因此，分析客户流失原因，吸引潜在客户入网，增 加现有客户满意度，减少客户流失几率，提高客户平均消费水平，充分占有市场， 是移动通信企业在激烈市场竞争中制胜的关键。 客户流失一直是学术界和工业界的研究热点，客户流失问题包括流失产生原 因，流失分类，流失预测，客户挽回等多个方面，而其中如何准确地对客户流失 进行预测，则是客户流失分析的核心问题。相关工作表明，传统的客户流失预测 大多是基于数据挖掘的一些方法，他们首先将历史通话记录，用户资料，通话费 用等多类数据归纳为用户属性，然后利用决策树，神经网络等数据挖掘算法，进 行客户流失的预测分析。然而，这些方法具有一定的局限性，它们不仅需要复杂 的数据预处理工作，而且忽视了用户之间的相互联系信息。 本文侧重于从客户的相互联系出发，提出了一种新颖的客户流失预测算法， 通过利用客户之间的相互通话联系，结合客户的历史通话记录，运用最大团的相 关知识，进行了客户通话行为的时间序列分析，从客户的通话趋势预测潜在的流 失客户。 1 2 工作内容 1 2 1 研究目标 本课题的研究目标是电信业广泛面临的客户流失问题，分析现有客户流失预 北京邮电大学硕士学位论文1 一种基于晟大团的群体客户流失预测算法 测方法，结合最大团的相关知识，提出一利晰颖的基于最大团的群体客户流失预 测算法。 1 22 工作内窨 基于上述研究目标，本论文主要展开以下几方面的工作： 1 ) 对电信业普遍存在的客户流失问题进行深入的研究和调查。 2 ) 对群体关系数据挖掘和晟大团发现算法等相关工作进行研究。 3 ) 提出基于最大团的群体客户流失预测算法，并将其应用于实际的客户流 失预测，评估算法的性能。 1 3 论文结构 本论文按以下章节组织： 第一章是绪论部分，简要介绍了本论文的相关背景，工作内容以及论文结构。 第二章介绍了客户流失问题，从客户流失的背景，移动客户流失的定义，流 失的分类，流失客户的细分，客户流失的控制，流失的典型案例分析，传统客户 流失预测的方法及其局限性等多个方面详细阐述客户流失这个电信业广泛存在 的问题。 第三章介绍群体关系数据挖掘的相关知识，从群体关系数据挖掘的背景，定 义，应用前景，分支以及群体关系数据挖掘中的个重要方向，最大团的发现等 多个方向详细阐述了群体关系数据挖掘这一当前数据挖掘的热点。 第四章详细介绍了基于最大团的群体客户流失的预测算法，我们首先从两个 典型的群体流失案例出发，总结出一些群体流失的基本规律，然后利用这些规律 提出算法的详细描述，进而进行算法的一些相关分析，在制定出三个用于算法评 价的指标之后，我们将算法应用于实际某市的客户流失预测，并对结果进行了细 致的分析。 第五章分析了一些当前算法的一些不足，并提出下一步的工作方向。 第六章作为附加的一章，简单介绍了研究生阶段的另一项工作群体欺诈 的发现，希望能够与群体流失分析相结合，探索群体关系数据挖掘应用的新方向。 第七章是本文的结束语部分。 文章的最后是参考文献，附录和致谢。 北京邮电大学硕l 学位论立2 一种基于最大团的群体客户流失预测算法 2 1 客户流失的背景 第二章客户流失 在电信市场激烈的竞争环境下，即使是满意的客户，也有可能随时“背叛” 一家公司，“投靠”公司的竞争对手。目前，许多企业都面临着客户流失的问题， 以中国联通福建分公司为例，其g 网用户的数据统计表明：截止到2 0 0 2 年1 1 月底，在网正常开机的用户为二百二十多刀，而各种退网用户有一百多万。虽然 这是一个累计值，但是也表明客户流失是值得重视的问题。此外，有统计表明， 吸引一个新客户需要花费的成本是保留一个老客户所需成本的5 1 0 倍。所以， 在注重发展和吸引新客户的同时，更要重视保留住现有的客户。而保留住现有客 户的前提是了解现有客户，发现有价值的可能流失的客户，也就是预测客户流失 可能性。然后，针对高可能流失的高价值客户采取相应的客户挽留措施，预防客 户流失，从而提高企业的经营效益。这就是进行客户流失分析的意义。 2 2 移动客户流失的定义 客户流失是指客户因某种原因与移动运营商解除服务合同的行为。移动通信 领域的客户流失有三方面的含义： 1 ) 指客户从本移动运营商转网到其他电信运营商，这是流失分析的重点。 2 ) 二是指客户使用的手机品牌发生改变，从本移动运营商的高价值品牌转 向低价值品牌，如中国移动的用户从全球通客户转为神州行客户。 3 ) 三是指客户削诤u ( 指用户每月平均消费量) 降低，从高价值客户成为 低价值客户。 2 3 客户流失的分类 北京邮电大学硕士学位论文 一种基于最大团的群体客户流失预测算法 客户解除服务合同的原因是多种多样的，我们可以根据客户流失原因，对客 户的流失行为进行分类。 23 1 主动流失和被动流失 根据流失产生的主导因素的不同，我们可以将流失分成：主动流失和被动流 失。 主动流失是指由于客户自身原因自愿与运营商解除服务合同，也称为自愿流 失。造成客户主动流失的原因有很多种，根据目前运营商的市场经营的现状和对 流失客户的走访调查来看，客户资源流失的主要是由业务竞争造成的。不同运营 商之间的业务资费差异，服务质量水平，品牌形象定位都会影响客户对运营商服 务的选择，成为客户流失的诱因。此外，客户资源流失还包括一些客观因素造成 的服务合同解除，例如，客户工作地点的变更，经济收入下降等原因。 被动流失是指通信运营企业由于某种原因而决定中止向客户提供服务，也称 为非自愿流失，客户被动流失主要是由于客户恶意欠费或信用问题造成的。 2 32 内部流失与外部流失 根据客户解除合同后的流向，我们可以将流失分成：内部流失与外部流失 内部流失是指客户解除合同后，继续选择了本企业提供的其他产品和服务。 如果客户新的选择的业务品牌优于原有的品牌，对企业来说，这种流失带来的是 客户价值的提升，属于优向流失。如果客户放弃高端品牌选择了低端品牌，就属 于劣向流失，这种流失是企业应该尽量避免的。 外部流失是指客户解除服务合同后转向竞争对手，是电信运营企业最不愿意 看到的一种流失，也是企业客户流失分析的重点。 2 4 流失客户的细分 客户流失分析旨在提取流失客户的行为特征，但是不同的客户群体的消费行 为特征有较大的差别，因此对于各种类型的客户流失情况进行整体预测会降低预 测的准确性。在客户流失分析之前对流失客户加以细分，可以使预测能力最大化， 从而使通信企业客户轮流失分析更具意义。 北京邮电大学硕士学位论文4 一种基于最大团的群体客户流失预测算法 24 1 根据客户资料的完整性细分 客户资料包括客户的基本属性、状态属性、帐务属性、行为属性等，在进行 客户流失分析时，在进行客户流失分析时，需要根据这些属性提取流失客户的特 征，这就需求企业拥有的完整的、真实的客户资料。目前通信企业掌握的客户资 料并不完整，以中国移动为例，其神州行客户的背景资料是不完整的，即使对其 分析流失原因也很难推出由针对性的营销策略。因此，在进行流失分析时，我们 需要根据客户资料的完整性对客户加以区分。 2 ，4 2 根据客户的流失类型细分 主动流失的客户通常是信用较好、财务状况也较好的客户，并对市场活动有 所反应，相对其他客户来说，他们比较稳定和有价值，这样的客户也是运营企业 需要保持的客户。被动流失的客户，信用低，财务状况也较差，因此挽留价值较 低。 24 3 根据客户的价值进行细分 客户流失分析的目的是通过预测来挽留客户，增大业务收入，从而给企业带 来更高的利润。因此，通信企业在进行客户流失分析时，就不能不考虑客户的服 务成本。服务成本的高低与客户能为企业带来的价值相关联，而且不同价值的客 户在消费行为上也会有很大差异，所以在制定客户挽留策略时，对不同价值的客 户进行区分十分必要。 2 5 客户流失的控制 客户流失控制阶段的主要工作是进行客户流失原因的分析，制定相应的客户 挽留和赢回策略，并对营销活动进行后评估。客户流失控制工作具体包括以下几 个方面。 2 5 1 流失影响因素分析 根据流失预测模型的输出结果，结合企业外部竞争环境的变化寻找影响客户 流失的环境原因。通信企业从深入分析预测模型结果，收集企业外部竞争情报和 对己流失客户一对一沟通等方面入手，将数据分析和环境分析相结合，找出造成 客户流失的原因。 北京邮电大学硕士学位论文5 一种基于最大团的群体客户流失预测算法 2 52 营销策略制定 针对客户流失原因，选择带挽回目标客户和赢回目标客户，制定客户挽留策 略和客户赢回策略。 2 53 营销活动后评估 实旋营销方案，并对方案的实施效果进行跟踪和评估。 需要指出的是，在实施目标活动后，要根据市场环境的变化和客户行为的新 特点修正客户流失预测新模型。因此，整个客户流失流程应该是一个往复的循环 过程。 2 6 流失案例分析 客户流失的方式有很多，在这里我们列举对于电信运营商造成很大损失的两 种特殊案例。 2 61 客户集体离网 这类客户群通常是一个企业移动虚拟网( v p m n ) 客户群。 虚拟专用移动网业务是利用电话网( 固定和移动) 的资源向某些企业，集团 提供一个逻辑上的专用网，可以为申请了此业务的集团内的移动用户提供类似公 用固定电话网中小交换机( p b x ) 的专用网络业务。 v p m n 业务允许v p m n 用户进行网内呼叫、网问呼叫、专用编号、缩位拨 号，并对集团、企业给予一定程度的话费优惠，v p m n 业务的实现可以为运营 商和业务使用用户带来如下好处： 1 )将移动电话、办公电话组成移动虚拟专网，可以给工作带来极大的方便， 而且可以在有效地利用移动电话的基础上合理地控制话费，方便管理。 2 )对于办公地点分散，甚至跨省、跨国的大公司来说，通过v p m n 业务， 公司可以自己确定分配号码的方法，而且只需拨专用号码就可以拨通被叫 进行通话，为企业用户提供了很大方便。 3 )可以设置多组网内或网外号码组，无论您的内部通信管理还是外部业务联 系，都显的更加轻松。 北京邮电大学硕士学位论文6 一种基于最大团的群体客户流失预测算法 但是在竞争对手更优惠的条件下，v p m n 用户有可能集体转网。转网初期， 作呼叫转移到其他运营商号码，对公月账单话费下降剧烈，呼叫转移次数与通话 比率增大明显。 这种客户集体离网现象对于运营商造成的直接收入损失和间接的信誉降低 都有很大的影响，建议运营商采取多种形式进行预防。 26 2 大客户转网 大客户是竞争对手积极争夺的对象，根据统计，占客户总数的3 0 的大客户 贡献了话务总量的7 0 。目前，许多运营商对大客户采取主动营销，加上门服务， 赠送手机，话费打折和积分等优惠政策。 大客户分类方式多种多样，根据社会影响和消费高低，可分为党政军人士， 社会名人，各类明星，各企业高级管理人员，个人高话务量客户等。大客户通常 对话务质量和业务服务水平要求高，对资费敏感性差，喜欢使用高价值品牌。但 部分大客户在运营商赠送手机和s i m 卡等优惠条件下，将会同时拥有多个运营 商号码。从分析月详单可以看出，这类客户接听来话比例高，打出电话比例低。 二者相差悬殊，这是因为客户在非商业等一般情况下使用了资费低的号码。从统 计数据看，某些地区移动联通电信小灵通入网用户总数比人口普查所得到的人 口总数还多也证明了一人多卡的现象普遍存在。 由于大客户贡献了运营商大部分的通话业务和收入保障，具有很高的价值， 因而对于如何避免这类大客户的离网，提高大客户的客户忠诚度，对于电信运营 商具有非常重要的意义。 2 7 客户流失预测的意义 通过以上两个流失案例的分析，很显然建立客户流失预测模型，帮助企业对 有流失风险的顾客提前采取相应营销措施，准确找出易流失客户人群，并制定相 应的挽回方案，最大程度地保持住老客户，对于避免企业经营损失，提高企业信 誉度，吸引更多新用户入网，有着重大的发展战略意义。 北京邮电大学硕士学位论文 一种基于最大团的群体客户流失预测算法 2 8 传统客户流失预测的方法 从实质上说，客户流失分析研究的是如何利用通信运营企业拥有的客户的数 据来预测客户流失的可能性，其中的基本假设是流失的客户在流失前都会出现一 些显而易见的行为特征。 客户流失预测是客户关系管理( c i t m ：) 工作的重要组成部分，传统的客户 流失预测方法大多是利用数据挖掘技术，通过对客户的消费行为和用户属性等消 息进行分析，通过分析已流失客户的行为特征，建立客户流失预测的数据挖掘模 型，实现客户高流失概率预警。 数据挖掘算法的选择是客户流失预测模型建立构成中主要的步骤。目前市场 上大多数综合性数据挖掘产品都能够提供决策树，神经网络，回归分析，关联规 则，聚类等多种建模方法，其中有些数据挖掘方法适用于流失预测的分析。通常 情况下，一般采用分类和值预测的算法，如决策树、神经网络、回归法等。 2 8 1 决策树 决策树( d e c i s i o n t r e e ) 是一个类似于流程图的树形结构，其中每个内部结点 表示在一个属性上的测试，每个分支代表一个测试输出，而每个树叶结点代表类 和类分布。树的最顶层结点是根节点。 一棵典型的决策树如图2 - 8 1 所示，它表示根据用户的年龄，职业，信用卡 信誉等属性来预测该用户是否会购买计算机的行为。内部结点用矩形表示，而树 叶节点用椭圆表示。为了对未知样本进行分类，样本的属性值在决策树上进行测 试，路径由根到存放该样本预测的叶结点。决策树很容易转换成分类规则。 决策树的输出结果是一种代表着决策集的树形结构，提供了一种类似在什么 条件下会得到什么值这类规则的方法。它是利用信息论中的信息增益寻找数据库 中具有最大信息量的字段，建立决策树的个节点，再根据字段的不同取值建立 树的分支。在每个分支子集中，重复建立树的下层节点和分支的过程，即可建立 决策树。 阱0 邱义堂提出了一种新型的运用c 4 5 决策树归纳技术，配合多专家决策分类 方法进行分析研究，并在输出的1 0 0 3 的全体客户中，平均可预测出5 0 6 4 的 流失客户；在选取的2 9 0 0 的输出名单中平均可预测出6 8 6 2 的流失客户。 北京邮电大学硕士学位论文 一种基于最大团的群体客户流失预测算法 图2 - 8 一l 决策树 28 2 神经网络 神经网络为解决大复杂度问题提供了一种相对来说比较有效的简单方法。神 经网络可以很容易的解决具有上百个参数的问题( 当然实际生物体中存在的神经 网络要比我们这里所说的程序模拟的神经网络要复杂的多) 。神经网络常用于两 类问题：分类和回归。 在结构上，可以把一个神经网络划分为输入层、输出层和隐含层。输入层的 每个节点对应一个个的预测变量。输出层的节点对应目标变量，可有多个。在输 入层和输出层之间是隐含层( 对神经网络使用者来说不可见) ，隐含层的层数和 每层节点的个数决定了神经网络的复杂度。 神经网络是一种仿照生理神经网络结构的非线形预测模型，通过学习进行模 式识别。其工作原理是获取输入值并在网络中传递这些输入值，而使之从初始值 转换成一个或多个结果值。训练期间，在构建网络的地方，将随着错误的不断发 现与解决而不断调整并改进网络。但是，神经网络不生成可简化解释的规则，并 对输入数据提出特殊要求。图2 - 8 2 表示了一个多层前馈神经网络的模型。 北京邮电大学硕士学位论文 一种基于最大团的群体客户流失预测算法 臣圈匪垂习臣困 图2 - 8 2 神经网络 28 3 回归法 回归分析是一种传统的统计方法，用于推导变量和需预测值之问关系的函 数。这类方法与神经网络一样，常使用数字输入，必须对数字进行预处理。实际 应用中有大量各不相同的回归方法，最常用的是多项式回归和逻辑回归两种。 回归是通过具有已知值的变量来预测其他变量的值。在最简单的情况下，回 归采用的是像线性回归这样的标准统计技术。但在大多数现实世界中的问题是不 能用简单的线性回归所能预测的。如商品的销售量、股票价格、产品合格率等， 很难找到简单有效的方法来预测，因为要描：述这些事件的变化所需的变量以上百 计，且这些变量本身往往都是非线性的。为此人们又发明了许多新的手段来试图 解决这个问题，如逻辑回归等。 2 9 传统客户流失预测的方法的局限 如上节所述，传统的客户流失预测方法大多是基于分类，预测的数据挖掘方 法，它们都具有一定的局限和弊端，对于海：量的电信数据挖掘而言具有高复杂度 的特点。 2 g 1 复杂的数据准备 首先，为了进行分类算法建模的需要，必须事先进行大量的多维数据准备， 北京邮电大学硕士学位论文1 0 一种基于最大团的群体客户流失预测算法 而这- 一工作对于具有海量，异构，分散的电信数据而言，可能具有很大的难度和 局限，复杂的数据准备往往占用了整个分析过程的大部分工作。 2 9 2 忽视群体之间的联系 其次，无论是分类还是预测算法，都是将客户作为一个孤立的个体来看待， 去分析该用户的通话和消费行为，大多数分类算法都是将用户的通话时长，费用， 次数等等属性汇总成为一张宽表，进而进行数据挖掘预测模型的建立。对于这样 的方法而言，对于群体之间的相互联系信息重视不够，忽视了很多有价值的信息， 然而这些用户之间的相互联系可能蕴含着很多个体属性所不能反应得信息，例 如，对于流失预测来说，如果一个用户与潜在的流失用户联系占据了日常通话的 大部分份额时，一旦这些潜在流失用户真正流失，那么这个用户也有很大可能选 择流失，进而和已经流失的用户选择相同的运营商。可是，这样和流失用户联系 的比例是传统基于数据挖掘方法所不能体现出来的。 北京邮电大学硬士学位论文 种基于最大团的群体客户流失预测算法 第三章群体关系数据挖掘 3 1 群体关系数据挖掘的背景 目前，一般的k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 算法大多侧重于单一 实体属性的数据挖掘，这往往忽略了实体间关系结构模式的提取，而且由多关系 表整理单实体属性的过程极为复杂且容易丢失可用信息和背景知识。更值得一提 的是，由于传统的k d d 算法没有将实体处于一个复杂系统中进行分析，因而发现 的许多知识不是常识性浅层知识，就是在分析专家进行数据处理时已经目标锁定 的并不太新颖的知识。而在数据丰富且增长迅速的应用领域如生物信息、互联网、 金融和电信等领域对实体间关系、结构及背：翳等深层次的知识发现需求越来越强 烈，传统k d d 算法的缺陷影响了k d d 的实际应用。由此，针对群体关系的数据挖 掘研究将成为知识发现研究领域的一个新兴课题。 3 2 群体关系数据挖掘的定义 群体关系数据挖掘涵盖了从由复杂或结构化对象组成的数据中发现知识的 众多研究方向。它着重以复杂系统的观点研究大量实体间关系的结构模式以及结 构模式与实体属性的关联。群体关系数据挖掘研究目标在于融合新兴的多关系数 据挖掘、基于图的数据挖掘以及复杂系统理论的研究成果，开发新的群体关系数 据挖掘技术，以及这些技术的实际应用。 3 3 群体关系数据挖掘应用前景 目前，群体关系数据挖掘有广泛的应用前景。 331 社群网络 社群网络分析关注于对社会各角色关系分析，这是多实体关系结构分析在社 北京邮电大学硕士学位论文 1 2 种基于虽大团的群体客户流失预测算法 会领域应用的根本。随着社群网络建模数据的快速增长，原来属于社会学、人类 学等社会科学领域的社群网络分析也从定性概念性分析扩展到定量的挖掘性分 析，成为群体关系结构研究极富前景的应用领域。 3 32 犯罪预防 经过9 11 事件，有关部门已经将关联分析等数据挖掘技术应用于反恐等情 报分析中，e e l d 就是d a r p a ( 美国国防部高级研究计划局) 专门针对犯罪预防的联 系发现( l i n kd i s c o v e r y ) 数据挖掘项目。从众多交往网络中找到可疑的实体关系 结构，追踪可疑网络并揭露其它未知的网络，分析其旅行资料、银行交易、电话 呼叫和互联网的使用可以发现发生类似重大事件的时机，进而预防犯罪的发生。 3 3 3 病毒营销 即通过人们的口碑宣传，信息被快速复制，像病毒一样迅速向用户传播和扩 散。病毒营销借助网络效应已经成为传统营销方式的一个补充，而且在一些网络 性市场领域，公司的未来越来越确定于有效的病毒营销策划。而成功的策划依赖 于对客户间交互关系模型分析以及客户属性和产品特征等群体关联的分析。 3 3 4 基于w e b 的信息获取 w e b 结构挖掘是w e b 挖掘中一项重要内容，以页面为实体，挖掘页面间链接 关系结构可以改善搜索引擎的性能；作为下一代互联网演进模式的易于机器理解 的语义网更是注重网页结构的可理解性，而且从互联网的大量文本等非结构化数 据中获得信息的突破点还在于文本内容中各实体的关系结构的分析，这些都是群 体关系数据挖掘研究的应用范围。 3 3 5 知识管理 对企业、机构的知识共享网络的研究可以促进相关组织的知识管理。通过研 究共享网络中的意识、存取、约定和安全的作用，影响网络发展的个人、组织和 组织干涉的用途，个人网络的发展和重要性，可以改进知识管理的组织结构，提 升组织效率。 3 3 6 计算生物学 多实体关系结构分析在分子生物学中有大量应用，如预测致癌基因等。更重 要的是，生物学正在从研究单个基因和蛋白质快速演进为对活细胞内这些分子相 互作用的研究。群体关系研究可以应用于对这些分子交互作用的建模和可视化以 北京邮电大学硕士学位论文1 3 一种基于最人团的群体客户流失预测算法 及参与活动的分子特征的研究。 群体关系数据挖掘基本技术已经渗透到越来越多的领域，从商业数据分析、 生物信息学( 包括全基因分析) 和药理学( 药物设计) 到w e b 挖掘( 从文本和 w e b 资源中提取信息) ，以及知识管理、社群网络分析、迷漫计算等。因此，群 体关系数据挖掘研究具有重要研究意义。 3 4 群体关系数据挖掘的分支 群体关系数据挖掘涉及知识发现近年十分活跃的两个研究领域：以一阶逻辑 为基础源于归纳逻辑程序设计i l p ( i n d u c t i v el o g i cp r o g r a m m i n g ) 的多关系数 据挖掘m r d m ( m u l t i r e l a t i o n a ld a t am i n i n g ) 和以图论为基础的基于图的数 据挖掘g b d m ( g r a p h b a s e dd a t am i n i n g ) ，并将复杂系统理论引入知识发现， 从系统的角度研究数据挖掘。 3 4 1 多关系数据挖掘 关于多关系数据挖掘，2 0 0 1 年m r d m 开始在知识发现国际会议有专门讨论小 组，2 0 0 2 和2 0 0 3 a c m s i g k d d 年会继续两届举办了m r d m 专题会议，s i g k d d e x p l o r a t i o n s2 0 0 3 ( 5 ) 也设专辑介绍了m r d m 。m r d m 致力于从包含多个表的关 系数据库中寻找模式，研究的技术和方法主要集中在i l p 领域，其中i l p 方法 使用的语言主要是逻辑程序设计的语言( 一阶逻辑演算的子集) 。传统的i l p 研 究致力于在逻辑程序的框架下从例子和背景知识中进行归纳推理。这种原始的 i l p 任务被看作概念学习( 归纳出两类分类的分类器) ，同时也被看作学习关系 的逻辑( 内涵式) 定义。多关系数据挖掘就是将i l p 扩展到主要的数据挖掘任 务，如分类、回归、聚类、和关联分析等，并将用于单表数据挖掘方法的模式语 言扩展到适用于多表的情况，此时的关系模式语言包括关系关联规则、关系分类 规则、和关系决策树等。如d e b a s p e 发表的多关系关联规则的学习系统w a r m r 就是i l p 在关联规则分析上的扩展。目前m r d m 在伸缩性、i l p 收敛性和不确定 性( 概率推理学习) 等研究方面取得了一些进展，但是结构依赖性分析、时变结构 分析、与数据库技术和传统k d d 方法融合、处理多源信息和背景知识以及结果可 理解性仍然是m r d m 面临挑战的领域。 北京邮电大学硬士学位论文1 4 一种基于最大团的群体客户流失预测算法 3 4 2 基于图的数据挖掘 基于图的数据挖掘g b d m 方面，2 0 0 1 年g d m 相关文献在s i g m o d ，s i g k d d ， i j c a i a a a i ，i c m l ，e c m l p k d d 和i e e ei c d m 中大约有1 0 篇，2 0 0 2 年增加了 近一倍，2 0 0 3 年8 月a c mk d d 大会也收录了如分析艾滋病药物结构为应用背景 挖掘闭合频繁图模式( c l o s e df r e q u e n tg r o u pp a t t e r n ) 、从文献作者关联数据 分析社群网络和网络结点( 人物) 影响度等多篇g b d m 文献。虽然基于图的数据 挖掘提出时间并不长，但是由于图论作为数学的一个研究领域已经有很长的研究 历史，因而g b d m 有丰富的理论基础。这些理论包括图的分类、图的同构以及图 的特征表示等。基于图的数据挖掘按图的同构搜索策略可分为启发式和完全搜 索，按图的结构学习策略可分有导师学习和无导师学习。g b d m 主要方法有基于 贪心搜索方法、基于i l p 方法、基于归纳数据库方法、基于图论的方法和支持向 量机核函数( s v m ) 方法等。d j c o o ka n dl - b h o l d e r 提出的s u b d u e 是运用最 小描述长度原则( m i n i m u md e s c r i p t i o nl e n g t hm d l ) 典型的基于贪心搜索的有导 师学习系统。由于图的结构的复杂性，算法可伸缩性研究以及类似社群网络的不 易分割的多结点关系图的分析是g b d m 的前沿研究课题。 m r d m 和g b d m 不仅吸引了不少多年研究