（管理科学与工程专业论文）客户价值分析中规则发现方法及其应用研究.pdf

摘要 目前激烈的行业竞争中，要求企业的核心经营理念从“以产品为中心”转向 “以客户为中心”。客户关系管理( c r m ) 为实现“以客户为中心”的经营模式提供 了解决方案。c r m 的核心在于对两种不同流向的价值流交互创造过程的管理， 种价值流是从企业流向客户，另外一种是从客户流向企业。从后者考虑，那么 c r m 的最终目的即是最大化客户价值。如何实现客户价值最大化，这就要进行客 户价值分析。本文把数据挖掘技术应用于基于客户价值矩阵的客户价值细分中， 建立各类价值客户的分类模型。 本文按照客户价值分析中规则发现过程的思路展开。首先研究了聚类分析原 理与算法，分析比较了目前比较流行的几种算法，介绍了一种k m e a n s 改进算法 一f l ( m 。然后研究了分类原理与算法，介绍了各种分类算法，重点阐述了本文客 户价值分析中采用的c 4 5 算法。接着研究了客户价值理论，阐述了客户价值分 析的中心环节，即客户价值细分，分析比较了目前客户价值细分的几种方法。最 后，把改进聚类算法和c 4 5 算法应用于基于客户价值矩阵的客户价值细分中， 并进行移动公司客户价值分析，用样本进行了实验，比较了采用的聚类算法的性 能，得出客户的分类规则。 关键词：聚类，分类，客户价值分析，客户价值矩阵 a b s t r a c t t h ec u r r e n ti m e n s em d u s t r ) rc o m p c 廿t i o nr e q u i r c sc o m p a n i e st oc o n v e r tt l l e i rc o r e r u 如i n gp 面c i p l ef 如mf o c u s i n go np r o d u c tt of o c u s 抽go nc u s t o m e r s t h ec u s t o m e r f e l a t i o n s 嫩pm a n 8 9 e m e 硅t ( c 王洲) p r o v i 如ss o l u t i o n st oh o wt oi m p l e m e n t 搬e 删鹕 m o d eo ff o c u s i n go nc u s t o m e r s t h ec o r eo fc r mi sm ep f o c e s sm a n a g e m e mo f m u t i l a lc r e a t i o no ft h et 、v ot y p e so fv a l u en o w 、v i t hd i 仃e r e n td i r e c t i o n s o n ei sn d m c o m p a n yt oc u s t o m e r ，也eo m c ri sf o r mc u s t o m e rt oc o 黼p a n y f r o mt h ea n g l eo fm e l a 托墨t h ef i n a la i mo fc r mi st om a x 妇l i z et h ec u s l o m e rv a l u e 。王t e q u i r e sc 8 r r y i n g o u tc u s t o m o rv a l u ea n a l y s i st om a x i m i z et h ec u s t o m e rv a l u e t l l i st 1 1 e s i s 印p l i e sd a t a m i i l i n gt e c m q u e st oc u s t o m e rs e g m e n t a t i o nb a s e do nc u s t o m e rv a l u em a 讯xa 1 1 d b 疽l 蠡t h ec l a s s i f i c a d o nm o d e lo f c u s t o m e f 弼t 圭ld i 矮醯e n tv a l u e 。 n l i s 也e s i si s 幽l d e da c c o r d i n gt o 髓1 ei d e ao fd i s c o v e r j n gp r o c e s so fn 王l e si n 也c c u s t o m e rv a l u ea n a l y s i s f i r s t l y ，i t 曲d u c e sc l u s t e r i n gc o n c e p ta i l da i g o r i t h r n ， c o i n p a r e st h ec u 艄l tp o p u l a r 矗1 9 0 r i m m sa 1 1 dp u t sf o n a r dam o d i f i e da l g o r i 血mo f k m e a n s ，l k m s e c o n d l y ，i ti n 钒蝴l 】c e s 歉e l a s s i 蠡c a t i o nc o 硅c e p t8 n da l g o 西t 弧l sa n d e x p a t i a t e sc 4 5w i t he m p h a s i sw h i c hi sa d o p t e di ni t sc u s t o m e r 州u ea i l 砒y s i sm o d e l t h i r d l y ，i ta n a l y z e st h ec o r m o t a t i o no fc u s t o m e rv a l u e ，b r i n g sf o r w a r dt h eg e n e r a l p r o c e s sa n dc o r et a c h eo fc u 咖m e rv 越u ea i 】a l y s i sa n dc o i n p a r e s 诹ec u r r e n ts e v e 翻 m e t b o d so fc u s t o m e rs e g m e n t a l i o nb a s e do nc l l s t o m e rv a l u e 。l a s t l y ，呈ta p p l i e sm e i n n o v a t e dc l u s t e r 主n ga l g o r i 出ma n dc 4 5t oc u s t o m e rv a l u ea n a l y s i s ，b r i n g sf o r w a r da c u s t o m e rv a l u ea i l a l y s i sm o d e lb a s e do nc u s t o m e rv a l u em a t r i x ，i m p l e m e m sm e c u s 耋o m e rv 越u e 觚窿y s i so f 撒o b i l ec 咖雌a n ya n dm a b se x p e 国n e n t st oc o m p a r e 龇 缸l c t i o n0 fc l u s t e r i n ga l g o r i m 咀柚dg e t 也ec l a s s i f i c a t i o nr u l e so fc u s t o m e r so f d i f f j r e n tv a h 】e k e yw o r d s ：c l u s t e “n g ，c l a s s i 母i n g ，c u s t o m e rv a l u ea n a l y s i s ，c u s t o m e rv a l u em a t 淑 l l 漂刨性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加_ 以标注和致谢 的地方外，论文中不包含葜他人已经发表或撰写过豹研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：弦丕塑 日期：融年卫月吕 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，印：学校 有权保留学位论文，允许学位论文被查阅和借阅：学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文：学校可根据凿家或潮商省有关部门翘定送交学位论文。 作者签名：导师签名 ，2 2 年一月一目 硕士学位论文第一章综述 1 1 引言 1 1 1 问题的提出 第一章综述 基于i n t e r n e t 技术的电子商务正在改变着社会经济中各个行业的传统经营 模式，尤其彻底地改变了企业与客户之间的关系。在激烈的行业竞争中，要求企 业的核心经营理念从“以产品为中心”转向“以客户为中心”，即谁能把握住客 户的需求并以最快的速度做出反应，谁能吸引新客户、保持老客户，谁就能取得 最终的胜利。那么，如何实现“以客户为中心”的经营模式呢? 客户关系管理( c 刚) 为这个问题提供了解决方案。客户关系管理的核心在于对两种不同流向的价值流 的交互创造的过程管理，一种价值流是从企业流向客户，另外一种是从客户流向 企业n 1 。这两种价值流实际上是相辅相成的，企业为客户创造、提供优厚的价值， 客户回报企业以利润和发展的潜力乜3 。从给企业直接带来价值的客户流向企业的 价值角度考虑问题，那么客户关系管理的最终目的即是最大化客户价值。如何实 现客户价值最大化，这就要进行客户价值分析，找出最有价僮客户，开展特别的 促销活动，提供更个性化的服务，设法保持这类客户，使企业以最少的投入获得 最大的回报。 目前，传统的信息系统产生大量的客户特征信息和客户行为信息，但是这些 信息仅仅局限于表象的记载，缺少深层次的分析，运用聚类分析等数据挖掘方法 进行数据挖掘，发现数据里面的规则和知识，可以为企业决策提供实质上的建议 和指导。聚类分析是种出现很早的数据分析统计方法。近年来，由于数据挖掘的 兴起，聚类分析得到了更广泛的应用和研究，不仅原有的算法得以不断的改进创 新，而且新的性能更好的算法也不断被发现。采用更好更新的聚类分析技术应用 于客户价值分析也是研究的热点。 客户价值分析就要进行客户价值细分，找出高价值客户和无价值客户进行分 析，发现他们的特征，并根据这些特征提供个性化服务，从而以最少的资源创造 最大的价值。进行客户细分有分类方法和聚类方法，由于客户价值标准的难以衡 量性，所以一般采用聚类方法先对客户进行聚类，然后用分类的方法进行分类， 发现规则和知识。 本文在上述基础上研究了目前流行的聚类和分类方法，介绍了几种改进算 法，并把其应用于客户价值分析过程中，以发现各类客户的特征。 硕士学位论文 第章综述 1 1 2 本文研究的背景 本文研究的背景如下： 1 计算机以及网络迅速发展 自从第一台电子计算机发明以来，计算机硬件发展迅速，性能和数量都成几 何级数增长，现在各行各业都在使用计算机，企业的业务几乎都是依赖于计算机 工作。 硬件的发展促进了软件发展。现在，计算机软件各种各样，广泛应用于公司 和个人的生产、生活中。由于数据共享的需要，计算机被连成网络，使信息和数 据能够充分共享。世界上最大的网络是因特网，其用户已达几亿人。网络已成为 信息的载体，能提供最为便捷的信息共享。 2 c 砌v i 的广泛应用 客户关系管理c r ( 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 ) 最早由美国g a r t n e r g r o u p 提出。自1 9 9 7 年开始，经过几年的发展，全球的c r m 市场一直处于爆炸 性的快速增长之中。1 9 9 9 年全球的c 跚市场收益约为7 6 亿美元。据市场分析专 家预测，2 0 0 4 年全球c r m 市场收益将达到6 7 0 亿美元。年增长率将一直保持在 5 0 以上。目前，我国的c r m 市场也己开始启动。像以往的e r p 、电子商务等新 理念一样，c r m 在国内的发展经历了从概念传入到市场启动这样一个过程，而这 些新理念对推动我国信息化建设将发挥积极的作用。 3 数据挖掘技术的不断发展 传统管理信息系统产生了大量的数据，企业需要对这些数据进行开发利用， 发掘知识以指导管理决策。数据挖掘技术，特别是聚类和分类技术，迎合了这一 需求，近年来已得到迅速发展，不仅原有的技术得以更广泛的应用，而且新的挖 掘技术不断出现，应用领域也越来越广。 1 2 国内外研究现状 聚类分析最初是作为一种统计分析工具出现。随着数据挖掘技术的兴起，作 为一种主要数据挖掘技术的聚类分析得到更深入的研究和更广泛的应用。目前， 聚类分析的研究主要集中在算法的研究，包括新算法的发现和旧算法的改进，聚 类效果的评价、算法的性能比较以及聚类分析技术的应用领域等。 目前文献中有大量聚类算法，概括起来，可以分为四类n ： 1 划分聚类( p a r t i t i o n i n gm e t h o d ) 。有代表性的方法包括k m e a n s 、 k m e d o i d s 等。 2 基于密度的方法( d e n s i t y _ b a s e dm e t h o d ) 。主要算法包括d b s c a n 、o p t i c s 、 硕士学位论文 第一壹综述 d e n c l 旺、d b c l a s d 等。 3 层次的方法( h i e r a r c h i c a lm e t h o d ) 。常用的系统聚类就属于该方法， b i r c h 、c u r e 、c h a 皿e l e o n 也都属于层次的方法。 4 基于网格的方法( g r i d _ b a s e dm e t h o d ) 。s t i n g 是基于网格的一个典型例 子，另外还出现一种改逆算法s t i n g + 。 除了上面四类典型算法外，还有有序样本聚类、图论聚类、模镢聚类、基于 模型聚类等聚类算法。 聚类分析中的算法并不都是万能的，并非可适应于任何数据集。因此人们在 不断的探讨改送算法，佼其性能更加完善。文n 1 提出一种快运的能够处理大量分 类数据的算法。文l 提出一种k m e a n s 算法的改进版本，该算法采用一种建立在 点对称理论基础上的距离测量标准哺1 。外文文献中的改进算法还有很多。 实际应用中传统的k m e a n 媾法因为其执行效率高、简单、容易实现，所以 得以广泛应慝。但是对算法性能的追求是无止境的，而且k m e a n s 算法还有不能 处理噪声、会产生空簇等缺点，对k - m e a n s 算法改进，以更菇完或挖掘任务是本 文探讨的一个方面： 如何评价聚类效果也是一个研究热点。一般来说，有两个通晕标准用于聚类 的评价：簇座的紧凑性和簇问的间隔性一1 。在此基础上，很多文献提出了一些评 价指标。文阳提出一种聚类有效性指标来评价簇内紧凑度与簇间相隔度。对于模 糊聚类，b e z d e k 提出了分区系数和分类熵的概念。在文j t l ：u 。中还有一些其他的 模糊聚类有效性标准。但是这些指标在实际中很少得到使用，而且缺少一种普遍 适合所有算法的有效性测量指标卫1 ，本文也拟对聚类有效性评价指标进行了探 t 讨。 聚类的应用领域越来越广，近年来，由于客户关系管莲系统的兴起，客户关 系管理成为聚类分析的一个典型应用领域，其中聚类分析广泛应用于客户细分、 客户行为模式识别、客户流失分析等方面。 国内对聚类分析的研究主要集中在算法的改进上。文j l 提出一种不需要输入 任何参数的等密度线算法。文献_ 柚提出一种适合于大规模数据的、快速高效的递 增聚类方法，它采用了聚类特性( c l u s t e r i n gf e a t u r e ，c f ) 结构来表示聚类，能 更有效地保留和利用聚类信息。文n 钉提出一种基于密度的快速聚类算法，该算法 以核心对象氧域中所有对象的代表对象为种子对象来扩展类，从而减少区域查询 次数，降低l o 开错，实现快速聚类，对二维空间数据测试表明：快速算法能够 有效地对大规模数据库逆行聚类，速度上数倍于已有d b s c 心算法。文n t 提出一 种新颖、高效的慝于可分类数据的聚类算法w e i s c ，该算法具有好的精确性， 适合大规模数据库中数据的聚类。文n t 在属性均值聚类算法和、+ o o d b u d r 算法的 硕士学位论文第一章综述 基础上，综合考虑稳态函数和模式样本取值的概率分布，对目标泛函进行改进， 得到属性一统计混合聚类算法。中文文献中的改进算法还有很多。 对于客户价值的研究主要集中在两方面，一方面是客户价值的度量，另一方 面是客户价值分析的方法研究。 罗杰卡特怀特提出“客户终生价值”的概念，认为客户的终生价值存在累 加效应n 引。罗兰t 拉斯特( r o l a n d t r u s t ) 等则进一步提出了客户终生价值的 计算方法n 引。罗伯特布拉特伯格和约翰丹顿提出了“客户资产”概念，认为企 业的客户资产就是企业所有客户终生价值的折现现值的总和心0 j 。罗伯特韦兰和 宝罗科尔也提出了客户关系价值的概念，认为客户关系价值就是客户权益，即 为获取、发展和保有客户价值所支付的成本差，并系统的进行了研究心0 1 。目前， 国外对客户价值的评价，主要是沿用弗雷德里克莱希赫尔德的净现值评价体系。 这种评价体系的依据，是基于弗雷德里克莱希赫尔德的忠诚客户对企业收益增 长因素分析的生命周期模型乜。莱希赫尔德和他的工作组经过对多个行业的长期 数据分析，发现基本利润( b a s ep r o f i t ) 、购买收益增加( r e v e 叫eg r o 埘h ) 、成本节 约( c o s ts a v i n g ) 、推荐( r e f e r r a i s ) 以及价格贴水( p r i c ep r e m i u m ) 是客户在长期的购 买过程中为企业创造利润的主要因素。对于客户价值分析的方法，主要的方法有 i 心m 分析、客户价值矩阵分析方法和h k 分析方法等。 文豫纠介绍了一种客户价值衡量标准一客户全生命周期利润说尸，指出口尸 由客户当前价值和客户增值潜力组成，客户的当前价值表示如果公司将客户关系 维持在现有水平上时，可望从该客户处获得的未来总利润，客户的增值潜力取决 于客户增量购买( u p - b u y i n g ) 、交叉购买( c r o s s _ b u y i n g ) 和推荐新客户( r e f e ra n e w c u s t o m e r ) 的可能性和大小，并在c 职基础上提出一种客户价值细分的方法。 文提出了在各种情况下的客户终生价值模型，并分析了几个模型的可操作性和 有效性。文心钉认为客户价值主要表现在利润性、形象性、稳定性、壁垒性、战略 同盟性等几个方面。文乜副在弗雷德里克莱希赫尔德的净现值评价体系基础上提 出了考虑销售额与客户弹性的充分价值客户一企业评价体系。 基于数据挖掘技术的客户价值分析是目前分析型c 跳中的重要内容，几乎每 种c r m 产品都会有客户价值分析模块。如何把先进的数据挖掘技术与客户价值分 析方法相结合，以更好地完成客户价值分析任务，是目前分析型c r m 研究的重点， 这也是本文研究的重点。 4 硕+ 学位论文第一章综述 1 3 研究内容 1 3 1 研究思路 采用理论研究与实证分析相结合的方法。首先进行理论分析，理论分析按照 客户价值分析中规则发现过程这个思路展开，先研究了聚类分析原理和技术，并 详细介绍了本文所用的聚类算法，然后研究分类原理与算法，重点介绍本文所用 的分类算法一决策树。分析目前客户价值评价体系和客户价值分析方法，并在此 基础上提出创新的客户价值分析模型。最后，理论回归实践，通过移动客户资料 的收集与分析，运用前面介绍的方法和技术，进行移动公司客户价值分析，并运 用数据进行实验，比较介绍的改进算法与原有算法的性能，获得了客户价值的分 类规则。 1 3 2 主要内容 首先本文提出研究背景，即：数据挖掘技术的兴起，要求更好的聚类和分类 技术；客户价值为客户关系管理研究的重点，客户价值分析的方法有待研究。 其次本文深入分析聚类分析技术。从聚类分析技术原理入手，介绍聚类分析 中的主要数据类型、相关性分析和聚类效果评价方法，粗略介绍了各利- 聚类算法， 并从运行效率等角度对它们进行比较分析，最后介绍一种k m e a n s 算法的改进 算法_ f l 删，把它与k m 算法进行了比较。 然后介绍分类原理及算法，先介绍分类的概念、分类前的数据预处理和分类 方法评价标准，然后介绍各种分类算法，重点介绍本文客户价值分析中应用的算 法决策树，最后介绍评价分类准确率指标。 接着研究客户价值理论。首先介绍客户价值的内涵，然后介绍客户价值分析 的一般过程和中心环节，即基于价值的客户细分。详细介绍目前客户细分方法并 进行分析比较。 最后把聚类和分类技术应用于客户价值分析，并进行移动公司客户价值分 析，通过实验验证算法的有效性，发现各类价值客户的特征与规则。 1 4 本文结构安排 本文的行文结构如下： 第一章，分析国内外聚类与分类技术以及客户价值理论的研究现状，在 此基础上提出本文的研究内容。 硕+ 学位论文第一章综述 第二章，研究聚类分析技术的概念原理，效果评价指标，数据挖掘对聚类的 要求。分析目前常用的聚类分析算法，并进行分析比较，并在此基础上介绍种 k m e a n s 改进算法f k m 。 第三章，研究分类算法的原理、分类自订的数据预处理，分析各种分类算法， 重点介绍决策树算法。 第四章，阐述客户价值的内涵、客户价值分析的目的与意义以及其一般过程 和中心环节。分析比较日| ；j 基于价值的客户细分的方法。 第五章，提出一种融合聚类分类技术和客户价值矩阵的客户价值分析流程。 将提出的客户价值分析方法应用于实践，实现移动公司客户价值分析，并用数据 进行了实验，发现规则。 第六章，总结本文所做的工作，指出需要进一步改进的地方。 6 硕士学位论文第二章聚类分析原理与算法 第二章聚类分析原理与算法 聚类分析是数据挖掘中一门非常有用的技术，可以用于从大量数据中寻找 隐含的数据分布和模式。数据挖掘，也可以称为数据库中的知识发现 ( k d d ：k o w l e d g ed i s c o v e 叫i nd a t a b a s e ) ，是一种决策支持过程，它主要基于人 工智能( m ：a n i f i c i a li n t e l l i g e n c e ) 、机器学习、统计学等技术，对数据库中的数 据进行一定的处理，从而获得其中隐含的、事先未知的而又可能极为有用的信 息。 2 1 聚类分析原理及其应用现状 2 1 1 聚类分析原理 聚类分析是把一组物理或抽象对象按相似性归为若干类别，也称为“无指 导分类”。聚类分析的输入集是一组未标定记录，即输入的记录还未被进行任何 分类。其目的是根据一定的规则，合理的划分记录集合，使同类别中的记录 间的距离尽可能小，而不同类别中对象的距离尽可能大，并用显式或隐式的方 法描述不同的类别。而所依据的这些规则由聚类分析工具定义。由于聚类分析 可采用不用的算法，所以对于相同记录集合可能有不同的划分。 聚类分析是多元统计分析的重要组成部分，在传统的统计分析中已有多种 算法，并得到了广泛的应用。近年来，随着数据挖掘技术、数据库等信息技术 的发展，又有许多种新的算法被提出，并得到了更加广泛的应用。 2 1 2 聚类分析作用及应用现状 聚类分析正在蓬勃发展，有贡献的研究领域包括数据挖掘，统计学，机器 学习，空间数据库技术，生物学，以及市场营销等。由于传统的信息系统中收 集了大量的数据，在这些数据基础上的聚类分析已经成为数据挖掘研究领域的 一个非常活跃的研究课题。聚类分析从大量数据中寻找隐含的数据分布与模式。 目前，在商务上，聚类能帮助市场分析人员从客户基本库中发现不同的客 户群，并用购买模式来刻画不同的客户群的特征。在生物学上，聚类能用于推 导植物和动物的分类，对基因进行分类，获得对种群中固有结构的认识。聚类 7 额士学锭论文 第= 章凝类分辑缀壤与箕法 褒地球观测数掇露中樱戳地嚣酌确定，汽攀傈除罄掩膏赣的分缀，以及壤撼房 子熊类型、徐髓翘地理使藿对个城市中房趱於分缀上也可以发挥 髻矮。聚黉 也能瘸予辩w e b 上的文撩进行分类，戳靛现键感。 爨：井，豢囊分援邋可爝予对孤立点麴蓬测。宥辩滋符浆炎不跫为了将对象 聚集程一鼹两是为了鼹容易逸健巢个对裂从其绝对象中分离出来。例如，在意 蕊秘疆尼鞭酌一家商场鹃掰商努瑶都在镝售男式服装，涂一黎分痞辨，所肖的 其他分店献销馁辩始耀馁蓬少肖1 0 0 的收入增长。涮惩浆类分繇缀察舄将这一 家努臻分凑出采，经遥努褥袭臻，这塞努痦怒遴遭妖啬糗徽煞广毒，霹其德分 唐粥愚通遗电槛馓的广毒。 安际痰霸中，聚类分辑酾结染势不怒最终秘鹪。人们遵过聚类分析，将数 掭愆分魏箸干类，然瑟才在每一类中寻找模式戒备荦孛潜程酶肖鹰信怒。这辩。 数瓣撼擒瓣箕德技术梅鬟于聚必分褥靛终暴之上。 2 2 数攘挖撼霭聚类势毒嚣的蒸鳖鋈求 农数瓣挖掘锈域，骚究王 睾穗缝粲中雀为太整数据鬻鹣有效黎蜜嚣豹凝类 分爨善筏逶当瓣方法。活跃熬繇究未遂繁孛嶷黎粪方法戆毯枣缭往，方法对蒙 类炙杂澎拣帮类爨黥数糖瓣簿效整，褰壤聚类分褥技术，疆及耱对大羹数攥瘁 孛潼窘数毽鼗分类数掇鹣黎娄方法。 聚类蹩拿褰寒秽酸瞧麴羲秀炎鬏竣，宅懿港程蹙援爨窭了各鑫特殊鼹要浓。 数据懿据辩蒙撰戆葵蘩蘩浓鬈下瓣1 ： ，终绥瞧：许多浆类算法在枣子2 0 0 令数攥对象教书数据繁翕上z 佟簿缀 簿；懿愚，一个太栽耩数攥黪露携毽会见匿万个瓣豢，在这榉麓大数掇祭套样 本上逡行装类霹蕤会磐致骞璃差鹣终暴。数攥攘镶嚣蘩矮套裹凌 枣绫瞧熬聚类 爨法。 2 楚遵不浔类型鼷淫懿戴力；诲多葵法被设诗愆寒綮类数德类爨骢数撰， 毽楚，连建霹熊要求繁类其毯襟黧熬数据，魏二元类鍪( b i 撞a f ￥) ，分焱，耩髂类 壁( e 嬲罐跨f i l 糠。黻i n 采) ，序数壁( o 掇l n a l ) ，娥尝这魏数攥炎型熬潺会。 3 。发瑷髓意形状熬聚类：诲多爨类算法蕊予欧尼爨薅i 曩灏或豢爨哈篷耀亵 魔鼙浓凌定聚类。萋予这样豁距离凌爱国算法憩羯予笈浚其富鼹运尺度秘鬻壤 熬球状簇。稳是，一个簇可熊怒任意澎状熬。掇出黥袋溪任忽形状熬舞法怒缀 羹要鲶。 4 。瘸予凌定竣入参数茨镶域疑谈疆小恁：诲雾豢类蘩法在蒙类努掇孛蘩慕 硕士学位论文第二章聚类分析原理与算法 用户输入一定的参数，例如希望产生的簇的数据。聚类结果对于输入参数十分 敏感。参数通常很难确定，特别是对于包含高维对象的数据集来说，更是如此。 要求用户输入参数不仅加重了用户的负担，也使得聚类的质量难以控制。 5 处理噪声数据的能力：绝大多数现实世界中的数据库都包含了孤立点， 空缺，未知数据或者错误的数据。一些聚类算法对于这样的数据敏感，可能导 致低质量的聚类结果。 6 高维性：一个数据库或者数据仓库可能包含若干维或者属性。许多算法 擅长处理低维的数据，可能只涉及两到三维。人类最多在三维的情况下能够很 好地判断聚类的质量。在高维空间中聚类数据对象是非常有挑战性的，特别是 考虑到这样的数据可能非常稀疏，而且高度偏斜。 7 可解释性和可用性：用户希望聚类结果是可解释的，可理解的和可用的。 也就是说，聚类可能需要和特定的语义解释和应用相联系。应用目标如何影响 聚类方法的选择也是一个重要的研究课题。 2 3 聚类分析中的数据类型及其相异度计算晴6 3 在进行聚类分析之前，需要对搜集到的数掘进行预处理。目前聚类分析中 所使用的数据结构大多为下面两利，： 1 数据矩阵( d a t am a t r i x ) 。它用所个变量来表现，2 个对象。这种数据结 构是关系表的形式，或者可以看成甩朋的矩阵： 卜x ：” l x lx m _ j 2 相异度矩阵( d i s s i m i l a r i t ) rm 棚x ) 。描述，z 个对象之间的相异性( 或相似 性) ，用一个胛门维距阵表示： 0 d ( 2 ，1 ) 0 d ( 3 ，1 )d ( 3 ，2 ) 0 1iio d ( 门，1 ) d ( 刀，2 ) 0 其中，d ( f ，) 表示第f 个对象与第个对象之间的相异性( 或相似性) 的度量。 常用的相异性度量有：距离( t h ed i s t a n c eb e t w e e n t 、op o i n t s ) 、向量夹角( t h e a n 9 1 e b e t w e e nt w 0 v e c t o r s ) 、匹配比率( 1 1 1 e n u m b e ro ff e a t u r e si nc o m m o n ) 等等。 9 硕十学位论文第二章聚类分析原理与算法 根据变景性质的不同，相异度的计算方法也不同，大致可以分为以下几种 情况： 1 区闻标度交量( 1 n 把r v a l s 酬e dv a r i 曲l e s ) 。度量萃镦的选取对于聚炎结 果有很大影响。假如将身高的单德从米变为尺，将体熏的单位从公厅变为磅将 直接影响聚类的结果。为了避免出现这种情况，必须将数据标准化。 常用的标准化的方法是减去其均值褥除以其标准蓑，即： z f ：堑羔 。 盯， 此外，还有一种方法可供选择： ：翌立 。 s f ( 公式2 + 2 ) 其中5 ，= 二( i 一，一x ，f + i x 2r x ，1 十 + f 工刖一z ，i ) 为平均差。它比除以标准差有 更好的稳健性。闲为在计算平均绝对偏差时，度量值与平均僵的偏差( 到 lx ，一x ，1 ) 没有被平方，因此孤立点的影响在一定程度上被减小了。 对于这一类型的变鼍，通常使用距离来衡量两个对象问的差异。最常用的 是欧氏距离 = 、肝了了币了i i 可丽 治式2 3 此外还有曼哈顿距离和明考夫斯基( m i n k o w s k i ) 距离等。它们都满足距离公理： d ( f ，) o ，d ( f ，f ) = o ，d ( f ，) = d ( 工f ) ，d ( f ，_ ，) s d ( f ，厅) + 0 ( 南，) 2 。二值变量 。这罩唪交霪麓二值瓷嚣酶蕹广，它可黻其有多子两 个的状态，比如变詹c o i o r 可以有r e d ，”l l o w b i u e ，g r e e n 阏种状态。这种必型的 交避 蠡是翳篱萃嚣辩方法柬诗算瓣瓣象之闻豹辖髯度： 蛳，j ) ：芝旦 p 其中p 为黛部变爨瓣数耳，牌是鞭配豹数鹭。 ( 公炎2 6 ) 4 ，廖数型变爨( 0 磁n 鑫1 ) 。一个彦数裂变量霹数是裹数懿也瑶墩是连续豹。 离敞的序数型变鹫类似予标称变徽，除了它的州个状态憩以有意义的序列排序 兹，魄强驳嚣；逡续静痔数鍪交爨类经予区藏标度变量，但是它没枣肇谯，燕 的相对顺序是必瑟的，丽其实际大小并不重要。对于遮糖类型的变量先骤按下 述变换将其变换刘( o ，1 ) 区阕上： ( 公式2 7 ) 其中。为第f 个对象第，个变量的秩，埘，为第，个变量暇值鼗释。然后，蒋使 用距离来街量两对象间的捆异度。 5 。魄侧标波毅变羹 r a i o - s c 昧畦v a a b l e ) 。魄俩标发鍪交爨在；# 线性的檬 度取正的波壁值，例如指数标度，近似地遵循如下的公式 爿g 杏霉宅蠢。一疗( 公螽：2 8 ) 这里名和占怒难的常数。计算比例标发型变爨擒述的对象之闯的棚异度有三 秘方法： ( 1 ) 采朗与处理区闻橼发变爨嗣样的方法。但是，这种作法涎常不是个好 靛选择，鞠为标庭可髓被箍穗了。 ( 2 ) 对比例橼度墅变搬进行对数交换，侧如对象珀q 厂变量的值工r 被燮换为 鞠，y 扩= l o x j ，) 。变换褥甏懿妇f 爵塔采熏楚趱区藏橼度变羹酌方法。 ( 3 ) 将看住连续的序数型数据，将其作为嚣问标鹰的值来看待。 6 。溢仑鍪交爨。在囊实兹数攒库中，对象往往是谈灞台类型鹣交叠按述懿。 般来说，一个数据库霹能包括上面列出的全部六种交糖类型。一种方法是将 交鲞按类挺努缀，薅每释类型鞠嶷量避行擎穗魏聚类努耩。魏纂这婆努辑褥臻 兼容的结果，这种方法是可行的。但是实际应用中，这种情况不大可能的。一 ! o o 一吩 i 和 硕士学位论文第二章聚类分析原理与算法 个更可取的方法是将所有的变篓 一起处理，只进行一次聚类分析。一种技术将 不同类型的变量组合在单个相异度矩阵中，把所有有意义的变量转换到共同的 值域区间 oo ，lo 】上。用以下公式计算对象之间的楣昴度 = 攀铲 蔟中，p 为对象中的交量个数。如果畅或x 旷缺失( 邳对象f 或对象，没有变量 的值) ，或者x ，= z f o ，且变量，是不对称的二值变量，则指示项毛7 = o ；否则 j 。7 = l 。变量，对衍日之间相异度的计算方式与其具体类型有关： ( 1 ) 如果，是二元变量或标称变量：如果x 。r = x ，= 1 。 ( 2 ) 如果，是区间标度变量：坚立二生，这里的矗遍取变量 i i l a xh x 赴r m l i ihx 炒 的所有非空缺对象。 ( 3 ) 如果，是序数型或者比例标度型变量：计算秩。和勺2 者j ，并将z f 作为区间标度变量值对待。 这样，当描述对象的变量是不同类型时，对象之间的相辩度也能够进行训 襞。 2 4 相关性分析 确定哪些属性应当包含在对象特征分拆中不是l 牛简单的事馈。数据关系 通常包含很多属性，对于有效的聚类，应当选择哪些属性或维，用户所知甚少。 用户可能在分析中包含的属性太少，另一方面，用户也可能包含太多属性，都 会造成聚类结果的不准确。 应当弓| 进一些方法进行彝性( 或维) 相关性分析，以过滤搏绫计上不相关 或弱相关的属性，而保留对手头挖掘任务最相关的属性。 直观地，对于给定的类，如果个属性或维的值可能用于区分该类与其他 类，该属性或维被认为是高度檑关的。例如，客户的身高对客户为公司创造豹 价值爨没什么影响，即不能用来区分离输值客户帮低价俊客户。即使在同一个 维内，对于区分一个类与其他类，不同屡的概念也可能有很不相同的能力。例 如在b i r n ld a t e 维，b i n hd a v 和b i 劬m o n t h 与客户的价值不相关，然而， b i r t hd e c a d e ( 帮年龄区问) 可能与客户价值是态度裾关豹。这意昧着相关分橱 硕士学位论文第二章聚类分析原理与算法 应当在多个属性层次进行，并且只有那些最相关的维层次应当包含在分析中。 既然，属性的相关性要根据属性区分一个类与其他类的能力来评估，因此， 进行相关性分析时，要根据聚类任务，确定目标类和对比类，然后根据属性对 两类的区分能力来决定此属性的选择。 属性相关性分析的基本思想是计算某种度量，用于量化属性对不同类别的 区分能力。这种度量包括信息增益、g i n i 索引、不确定性和相关系数等。本文 介绍一种方法，它将信息增益分析技术和基于多维数据分析的方法集成在一起。 该方法可以很好的量化属性相关性，删除信息量较少的属性，收集信息量较多 的属性，在第五章移动公司客户价值分析中我们采用了此方法，以用来选择进 行客户价值分析的客户属性集。 计算信息增益的过程如下：设s 是训练样本的集合，其中每个样本的类标号 是已知的。假定有刀1 个类。设s 包含s 。个c 。类样本，f _ 1 ，m 。一个任意样本 属于类c ，的可能性是s 。s ，其中s 是集合s 中对象的总数。对于一个给定的样本 分类所需的期望信息是 胁一嚣l o g ：詈 ( 公式2 1 0 ) 具有值 口。，口：，口，) 的属性4 可以用来将s 划分为子集 s 。，s ：，s 。) ，其中， s ，包含s 中彳值为口，的那些样本。设s ，包含类c ，的s ；i 个样本。根据4 的这利- 划 分的期望信息称为4 的熵。它是加权平均： e ( 彳) = 里玛( s 。，+ 。， ，) ( 公式2 - 1 1 ) j = l j a 上划分获得的信息增益定义为 g 口加( 彳) = ，( ，s 2 s 。) 一e ( 彳)( 公式2 一1 2 ) 在这种相关分析方法中，可以计算s 中样本的每个属性的信息增益。具有最 高信息增益的属性是给定集合中具有最高区分度的属性。通过计算信息增益， 可以得到属性的秩评定。这种评定可用于相关分析，选择相关度高的属性。 通过上述分析，给出相关性分析的执行步骤： 1 数据收集：通过查询处理，收集要比较类的数据。比如对客户价值影响 的属性相关分析中，可以根据经验选择两类数据，一类为高价值客户数据，一 类为低价值客户数据。 2 使用保守的a o i 乜6 1 进行预相关分析：这一步识别属性和维的集合，选择 的相关性度量用于它们。通过删除或概化具有大量不同值的属性，面向属性的 归纳( a o i ) 可以用来进行一些预相关分析。一般来说，具有大量的不同值的属 硕士学位论文第二章聚类分析原理与算法 性多半没有意义。保守一点，这里进行的a o i 使用的属性分析阕值要合理地大， 使得更多的属性在选定度量的进一步相关分析中被考虑。 3 使用选定的相关分析度量删除不相关和弱相关属性：使用选定的相关分 析度量，评估侯选关系中的每个属性。根据计算结果，对属性排序。然后删除 不相关或弱相关的属性。可以设置一个阕值来定义“弱相关”。 2 5 聚类效果的评价 由于聚类分析是一种无指导的数据挖掘方法，再加上各种算法的差异，因 此最终的聚类结果需要评价以证明其有效性。一般来说，聚类的有效性验证涉 及到三个方面的问题：一是聚类的质量，二是聚类方法是否适合特定的数据， 三是簇的最优数量。 概括的说，有两种标准来进行聚类评价以及聚类方案的选择。 1 同簇内对象之间的紧凑性。簇内对象之问的距离应该尽可能的小，一般 用方差来衡量，应该使方差达到最小。 2 不同簇之间的距离尽可能大。分别以簇重心点、雨簇最远的点、雨簇最 近的点为代表点有两簇重心点的距离、两簇最远点的距离和两簇最近点的距离 三种常用的衡量标准。 建立在上述标准基础上，文乜 提出一种方法，经理论推导和实证分析证明 可以按照上面两个标准进行有效的聚类结果评价。而且此方法容易实现，适用 于我们客户价值分析中所采用的聚类算法，故介绍如下： 用表示数据集x 中数据的数量，t 为簇i 中的数据数量，k 为簇的数量， y ，为簇f 的中心点，p 为数据k 的第p 维值，i l 以i l = o r x ) 2 。使用某种聚类 算法已经把x 聚类成c 个簇。 定义l ：数据集x 的方差。仃( x ) 表示x 的方差。其第p 维值定义如下： 其中更p 为i 的第p 维值。 盯? = 去喜( x f 一更，) 2 ( 公式2 1 3 ) 一 1o x 2 i 乙x 。 ，l 七= i ( 公式2 1 4 ) 定义2 ：簇，的方差。仃( v ，) 表示簇i 的方差。其第p 维值定义如下： 1 4 硕士学位论文第二章聚类分析原理与算法 ( z f v 玎 ( 公式2 1 5 ) 盯f = 旦 ，j 数据集整体方差之和为仃= 盯( u ) i - l c 个簇的平均紧凑度用c d ，印表示，定义如下： c d ，妒= i | 仃l l c ( 公式2 1 6 ) ( 公式2 1 7 ) 则最终c 个簇的紧凑度可以用如下公式表示： 黝f c d _ ，妒= c d 唧l i 仃( x ) l i ( 公式2 - 1 8 ) 聚类结果越紧凑，则s c 口f c d 唧越小，聚类方案越好。簇间距离可以用每簇间 的距离的平均值来衡量。定义如下： d = 叫， f = l = l c ( c 1 ) ( 公式2 1 9 ) d 越大，则簇间距离越大。根据上面的定义，可以得到一种聚类质量的综合衡量 指标： c d = 口f _ c o 叩7 d ( 公式2 2 0 ) c d 的值越小，聚类方案越好。 2 6 主要聚类算法及其分析比较啪3 目前文献中存在大量的聚类算法。算法的选择取决于数据的类型、聚类的 目的和应用。如果聚类分析被用作描述或探查的工具，可以对同样的数据尝试 多种算法，以发现数据可能揭示的结果。主要的聚类算法大体上可以分为划分 聚类、层次聚类、基于密度聚类、基于网格聚类、模糊聚类、有序样本聚类、 图论聚类、基于模型、概念聚类等。下面介绍前四类聚类算法，给出每类中的 一种典型算法，并且进行分析比较，后面几种不再详尽介绍。 硕士学位论文第二章聚类分析原理与算法 2 6 1 划分聚类 划分聚类是给定一个门个对象或元组的数据库构建k 个划分的方法。每个划 分为一个聚簇，并且k 以。该方法将数据划分为k 个簇，每个簇至少有一个对 象，每个对象必须属于而只能属于一个组( 在有的模糊划分技术中对此要求不 很严格) 。该方法的划分采用给定的k 个划分要求，先给出一个初始的划分，再 用迭代重定位技术，通过对象在划分之间的移动来改进划分。 为达到划分的全局最优，划分的聚类可能穷举所有可能的划分。但实际操 作中，因为数据量的庞大，往往最终结果为局部最优解。这类聚类方法最早最 有代表性的是k m p 口门s 算法。基本步骤是：l 把对象粗略分成k 个初始类；2 进行修改，逐个分派对象到其最近均值的类中去，重新计算接受新对象的类和 失去对象的类的均值；3 重复第2 步，直到各类无对象进出。 随着聚类分析技术的发展，出现了许多k m p 删峦的改进算法。比较典型的 有能够处理符号属性的k m o d p 5 方法和结合了k 一所p 口，博和k m o d e s 的 k p ，。d ，d 卸p 5 算法。k p 加f d 卯e s 算法如下： 1 z 】，其属性为4 l ，4 ；，4 ；，彳；小爿：，其中属性彳l r ，4 ，彳；为数值属性， 4 ；小，彳三为符号属性，则测量它们不相似性的度量如下： p d ( x ，j ，) = ( x ，一j ，) 2 + y