（计算机软件与理论专业论文）基于密度的聚类算法研究及其在电信客户细分中的应用.pdf

硕士学位论文 摘要 伴随着电信市场的迅速发展，电信客户逐渐呈现出细分化、多元化的特征， 电信企业的竞争焦点和发展机遇将更多的集中到各细分市场中。运营商要保持市 场的领先地位以及不断提升客户价值，必须主动进行客户细分。因此如何有效地 利用数据挖掘方法对客户进行细分是目前数据挖掘应用的一个非常热门且具有 重要应用价值的研究课题。 论文对数据挖掘基本方法之一的聚类技术进行了较全面的比较研究，并利用 改进的聚类算法来细分电信业客户，从而达到可识别具有相似特征的客户群，成 为分析客户和形成市场策略的基础。本文主要研究工作与特色有： 1 ) 针对基于密度的聚类方法不能发现密度分布不均的数据样本的缺陷，提 出了一种基于代表点和点密度的聚类算法( c b r d ) 。算法以代表点的平均密度 作为类密度，代表点的k 近邻为代表区域，根据类密度，将满足密度阈值的代表 区域中的点选为代表点，再利用选出的代表点调整类密度，如此反复的寻找出所 有代表点和代表区域。所有区域相连的代表点及其代表区域将构成一个聚类，不 在任何一类中的点则被作为噪声数据。实验结果显示，该方法可以发现任意形状 的密度分布不均的类。 2 ) 提出的c b r d 算法虽然能够发现任意形状的聚类，但是在数据量大的时 候需要较多的内存和i o 消耗，导致其在客户细分中不能取得好的应用。因此， 在c b r d 聚类算法思想的基础上，本文提出了一种基于数据交叠分区的高效密 度聚类算法，算法继承了c b r d 聚类算法可以发现任意形状的密度分布不均的 类的优点，同时还具有较高的运行效率。 3 ) 将改进后的密度聚类算法应用于电信客户细分，可以使企业更好的掌握 市场动态以及对潜在客户挖掘提供有力的技术支持。实验结果证实了该聚类算法 的有效性。 关键词：数据挖掘；客户细分；聚类；密度；交叠分区 基于密度的聚类算法研究及其在电信客户细分中的应用 a b s t r a c t a l o n gw i t h t h e r a p i dd e v e l o p m e n t o ft h et e l e c o m m u n i c a t i o n s m a r k e t ， t e l e c o m m u n i c a t i o n ss e r v i c e sa r ep o p u l a ra m o n gc o n s u m e r s ，a n dt e l e c o m m u n i c a t i o n s i s g r a d u a l l ys h o w i n gf e a t u r e s o f s u b d i v i s i o na n dd i v e r s i f i e d t om a i n t a i nt h e l e a d e r s h i pp o s i t i o n i nt h em a r k e ta n d c o n t i n u o u s l yu p g r a d ec u s t o m e rv a l u e ， o p e r a t o r sm u s tt a k et h ei n i t i a t i v et oc o n d u c tc u s t o m e rs e g m e n t a t i o n s 0h o w t om a k e e f f e c t i v eu s eo fd a t am i n i n gm e t h o d so nc u s t o m e rs e g m e n th a sav e r yp o p u l a ra n d i m p o r t a n ta p p l i c a t i o nv a l u eo ft h er e s e a r c ht o p i co fd a t am i n i n ga p p l i c a t i o n t h i sp a p e rc a r r i e sac o m p r e h e n s i v ec o m p a r a t i v es t u d yo nc l u s t e r i n gt e c h n o l o g y ， 0 n eo ft h eb a s i cm e t h o do fd a t am i n i n g ，a n du s e st h ei m p r o v e dc l u s t e r i n ga l g o r i t h m t os e g m e n tt h et e l e c o m m u n i c a t i o nc u s t o m e r sw i t ht h ep u r p o s eo fi d e n t i f y i n gt h e c u s t o m e r sh a v i n gs i m i l a rc h a r a c t e r i s t i c sa n db e i n gt h eb a s ef o u n d a t i o no fm a r k e t a n a l y s i sa n dm a r k e ts t r a t e g yf o r m a t i o n i nt h i sp a p e r ，t h er e s e a r c h e sa n dc h a r a c t e r i s t i c sa r e ： 1 ) a i m e dt os o l v et h ep r o b l e mt h a tt h ed e n s i t y _ b a s e dc l u s t e r i n ga l g o r i t h md o s e n o tw o r kw e uw h e nd a t ad i s t r i b u t i o ni sn o te v e n ，an e wc l u s t e r i n ga l g o r i t h mb a s e d o nr e p r e s e n t a t i v e sa n dp o i n td e n s i t yi sp r o v i d e d t h ea l g o r i t h ms e t st h ec l u s t e r d e n s i t yw i t ht h ea v e r a g ed e n s i t yo fr e p r e s e n t a t i v ep o i n t sa n ds e t st h ekn e i g h b o r s0 f r e p r e s e n t a t i v e p o i n t sa sf e p r e s e n t a t i v er e g i o n u n d e rt h ed e n s i t yo fc l u s t e r ，t h e p o i n t si nt h er e p r e s e n t a t i v er e g i o nw h i c hm e e t st h ed e n s i t yt h r e s h o l dw i l lb es e l e c t e d a s r e p r e s e n t a t i v ep o i n ta n db er e u s e d t oa d ju s tt h ed e n s i t yo fc l u s t e r a n ds o r e p e a t e d l yf i n d0 u ta l lt h er e p r e s e n t a t i v ep o i n t sa n dr e g i o n s a l lt h er e g i o n l i n k e d r e p r e s e n t a t i v ep o i n t sa n dr e g i o n sw i l lf o r mac l u s t e r ，a n da n yp o i n t si nn oc l u s t e r s a r en o i s e s t h ee x p e r i m e n t a lr e s u l t sr e v e a l e dt h a tt h ea l g o r i t h mc a nf i n da n ys h a p e a n du n e v e nd i s t r i b u t i o no ft h ed e n s i t yo fc l u s t e r s ， 2 ) a 1 t h o u g ht h ec b r da l g o r i t h mc a nd e t e c ta n ys h a p eo fc l u s t e r s ，b u ti tn e e d s l o t so fm e m o r ya n di oc o n s u m p t i o nw h e nt h ed a t ah a sal a r g ea m o u n t ，r e s u l t i n gn o g o o da p p l i c a t i o ni nc u s t o m e rc l u s t e r i n g t h e r e f o r e ，b a s e do nt h ec b r da l g o r i t h m ， a ne f f i c i e n tc l u s t e r i n ga l g o r i t h mb a s e do nd a t ao v e r l a pi sc a r r i e di nt h i sp a p e r t h i s a l g o r i t h mi n h e r i t st h ec b r dc l u s t e r i n ga l g o r i t h ma n dc a nf i n da n ys h a p eu n e v e n d i s t f i b u t i o no ft h ed e n s i t yo fc l u s t e r s ，a l s oh a sah i g ho p e r a t i n ge f f i c i e n c y 3 )s u c c e s s f u l l y t o a p p l i c a n tt h ei m p r o v e dd e n s i t yc l u s t e r i n ga l g o r i t h m i n t e l e c o m m u n i c a t i o n sc u s t o m e rc l u s t e r i n g ， s ot h a t e n t e r p r i s e sc a nb e t t e rg r a s po f 硕士学位论文 m a r k e td y n a m i c sa n dg i v ee f f e c t i v e t e c h n i c a ls u p p o r tf o rm i n i n gt h ep o t e n t i a l c u s t o m e r s t h ee x p e r i m e n t a lr e s u l tc o n f i r m st h ev a l i d i t yo ft h ec l u s t e r i n ga l g o r i t h m k e yw o r d s ：d a t am i n i n g ；c u s t o m e rc l u s t e r ；c l u s t e r ；d e n s i t y ；o v e r l a p p i n gd i v i s i o n 基于密度的聚类算法研究及其在电信客户细分中的应用 插图索引 图3 1 排序4 d i s t 图1 7 图3 2 原始数据2 2 图3 3c b r d 算法在d a t a s e t l 上的聚类结果2 4 图3 4d b s c a n 算法在d a t a s e t l 上的聚类结果2 4 图3 5d b s c a n 算法在d a t a s e t 2 上的聚类结果一2 4 图3 6c b r d 算法在d a t a s e t 2 上的聚类结果2 4 图4 1 邻域重叠的点的聚类2 8 图4 2p d b r d 聚类结果一3 0 图4 3 算法执行效率对比3 2 图4 4 不同节点数的执行效率3 3 图5 1c r i s p d m 数据挖掘过程3 6 v 硕士学位论文 附表索引 表2 1 二元变量的可能性表一9 表4 1 职，川，聃，刚，的意义一3 1 表4 2 聚类结果比较3 2 表5 1 数据分区表一4 0 表5 2 聚类结果输出4 1 表5 3 各类客户群特征描述4 1 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均己在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：啄囡阂日期：毋。昭年岁月0 6 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“ ) 作者签名：锦i 虱阂 导师签名：脚匆 日期：0 口鹏年箩月6 日 日期：2 汐矿易年 月动日 硕士学位论文 1 1 研究背景及意义 第1 章绪论 近年来，数据挖掘( d a t am i n i n g ) 引起了信息产业界的极大关注，其主要 原因是存在大量数据可以使用，并且迫切需要将这些数据转换成有用的信息和知 识。数据的丰富带来了对强有力的数据分析工具的需求，大量的数据被描述为“数 据丰富，但信息贫乏”。快速增长的海量数据收集、存放在大型和大量数据库中， 没有数据挖掘这个工具，理解它们已经远远超出了人的能力。数据挖掘的研究是 信息技术发展的必然要求【l 】。 目前，中国移动通信业的竞争非常激烈。为了在越来越激烈的市场竞争中保 持优势，所有的电信运营商都面临着如何提高客户的忠诚度，以减少客户流失的 巨大压力。价格战不是保留客户的唯一方法。移动运营商以个性化、差异化服务 为顾客创造价值的理念推出的一系列服务，是另外一种竞争手段。我国现有移动 用户己超过3 亿，将来还会增长，如此庞大的用户群由于背景、收入、年龄、教 育程度、行为特征等的不同，对移动通信服务的需求也呈现多层次、个性化、差 异化的趋势。单一的价格战无法满足更多客户的独特需求，业务战和品牌战将是 未来竞争的主要内容。 进行客户细分是运营商急需解决的问题【纠。客户细分是客户关系由“大统一 向“个性化营销和服务转变的基础，是现代营销的关键所在。客户细分的意义 在于： 1 、获取潜在客户：根据对现有客户分析，识别潜在客户，提高市场反应速 度，优化销售渠道结构，提供差异化产品。 2 、减少客户流失：了解流失率较高的客户群特征，特别是获利较多客户的 个性特征，通过客户综合分析监控具有类似个性特征的客户发展动态，提高客户 流失预测准确率，提前预防客户流失。 3 、降低服务成本，提高企业的运营效率：通过细致地分析用于各个用户群 的服务成本，用最优投资方案定位于目标市场，设计出针对各个综合分析市场的 目标策略。例如将呼叫转移功能与非高峰时段服务进行捆绑就可以满足那些相对 固定在办公室上班的用户的基本产品消费需求。 4 、提升客户价值：客户综合分析带来了更精准的营销信息传递，更好的渠 道策略，更多的捆绑服务及打包服务，更及时的产品需求变化，更好的合作、服 务策略及其管理，提高了增值和交叉销售的可能性。 5 、提高满意度：监控每个客户群的产品使用和获利情况，建立不同的销售 渠道，根据客户需求定制个性化服务产品，及时洞悉客户的产品使用情况，提高 基于密度的聚类算法研究及其在电信客户细分中的应用 客户产品使用满意度。 6 、制定精确化营销策略：通过熟悉各个综合分析客户群的特征，为其定制 专门的价格、渠道、促销和个性化产品。 在电信行业中，传统的客户细分大多是通过主观方法，按照客户的基本属性， 采用固定报表或者较为先进的o l a p 方法，通过钻取、旋转、切片等操作，了 解客户构成、消费特征等相关信息。采用这类方法，共同点在于是通过先前的业 务经验，预先确定数据的展现模式，模型简单、易于理解，但是视角固定，难以 发现客户的潜在消费模式、根据客户消费行为提供有效的营销决策依据。当运营 商着眼于更广泛的消费者行为分析时，这种主观定义的细分方法就显得“力不从 心 。基于数据挖掘技术的客户细分方法相比于传统方法显得更加有效，能够及 时、客观地描述不断变化的客户消费行为，增强了辅助营销效果。基于数据挖掘 的客户细分开始得到国内电信企业的重视。 1 2 研究现状 1 2 1 聚类算法的研究 目前，聚类分析技术正蓬勃发展，它对数据挖掘、统计学、机器学习、市场 营销等领域都做出了贡献并已经成为数据挖掘研究领域中一个非常活跃的研究 课题。聚类分析将大量数据划分为性质相似的子类，这样便于了解数据的分布情 况，从而从中提取有用的知识。聚类分析作为数据挖掘的重要组成部分，现在已 广泛的应用于各个领域。目前的聚类算法很多，但不同的算法有各自的特点：基 于划分的算法适用于类数固定、偏好球形的聚类；基于层次的算法能得到不同粒 度上的多层次聚类结构：基于密度的聚类算法可以在含“噪声 数据库中发现形 状任意以及不同规模的聚类；基于网格的聚类算法处理速度快，处理时间独立于 数据对象的数目；基于模型的方法则适用于数据分布已知的聚类。因此，在实际 应用中可以根据不同的应用、数据类型和目的，选择使用最好的聚类方法。同时， 新数据形式的产生和广泛应用对传统的聚类算法提出了挑战，聚类分析将随着应 用的需求及新技术的出现而得到很大的发展。 1 2 2 客户细分的应用研究 在基于数据挖掘技术的客户细分研究中，z a k r z e w s k a 和m u r l e w s k i f 3 】基于银 行客户数据，比较了d b s c a n 、k m e a n s 和两阶段聚类方法的实证效果，研究 结果表明k m e a n s 算法对大数据集十分有效，但对于噪声数据的敏感性较强； 而两阶段聚类算法虽然对噪声不敏感，但不适宜对大数据集的计算；同时 d b s c a n 对输入参数的要求过高，使得模型应用的代价过大。b 0 0 n e 【4 】针对零售 硕士学位论文 行业同益积累的海量客户数据，采用基于h o p f i e l d 网络的人工神经网络技术， 对客户进行了细分，研究结果表明该方法相比k m e a n s 算法，对初始条件的敏 感性大大降低。s h i n 和s o h n 【5 l 采用k m e a n s 、s o m 和模糊k m e a n s 三种方法对 股票交易客户进行细分，发现模糊k m e a n s 明显要比其他两种方法稳健。大多 学者都比较了不同聚类算法在具体行业应用中的实证效果，但对于算法本身的不 足，通常只是试图寻求一种替代方法，没有结合实际问题对算法进行改进。 针对电信行业所进行的客户细分研究也比较多，文献f 6 1 利用数据挖掘中的 误差平方和准则函数的k m e a n s 聚类算法，建立了客户细分分析模型，为企业 进一步制定营销策略提供依据；文献f 7 1 针对现有的数据挖掘模型解决客户不确 定性行为的不足，提出了基于云模型的动态客户细分分类模型。该模型将云模型 理论中关于动态概念描述的思想引入到对分类状态集的后处理过程中，以隶属度 高的类别被选中的概率大的程序设计原则实现了分类器处理过程的动态性。经实 验验证，该模型能够更加客观地描述客户行为的非确定性和随机性特征，具有良 好的分类效果。 文献【8 】结合通信行业的实际情况，通过研究数据挖掘的聚类方法，提出了 用k m e a n s 聚类算法实现通信行业客户细分，解决了通信行业缺乏客户细分手 段的问题，提高了通信企业的效益和竞争力。 a b a s c a l 等【9 】从定性研究和定量研究相结合的角度出发，应用基于多因素分 析( m f a ) 的多准则聚类技术，对国外某电信公司数据仓库中的数据进行分析，建 立了性能较为优越的电信客户细分模型。 文献【1 0 】应用聚类分析技术解决电信行业中的客户细分问题，并结合实际数 据建立了相应的客户细分模型；文献f 1 1 1 分析了中国移动市场现状，结合k m e a n s 聚类算法和客户行为细分方法，提出基于k m e a n s 算法的中国移动市场动态客 户行为细分模型，并进行了实证研究。 1 3 客户细分中存在的问题 目前，电信行业的客户关系管理及数据挖掘技术的应用在理论界和企业界都 是研究的热点。这些研究成果或从理论角度进行了深入的探讨，或从电信c r m 系统的相关应用角度研究了分析、设计与实施等关键步骤，或提出了一些相对成 熟的数据挖掘工具以及解决具体商业问题的数据挖掘模型和方法。可以说，这些 研究成果极大的推动了数据挖掘在实际应用中的应用，但从应用现状来看，还存 在一些值得改进的地方： ( 1 ) 从数据挖掘工具的开发上，目前仍然以横向的、通用性的挖掘工具为主， 面向行业的纵向数据挖掘工具较少。从国内情况看，尚未出现行业版的数据挖掘 工具，但数据挖掘的行业应用是未来发展的一大趋势。如何将普适性的数据挖掘 基于密度的聚类算法研究及其在电信客户细分中的应用 方法和模型应用于具体行业问题，是摆在大家面前的一个重要课题。 ( 2 ) 目前的一些研究只是从某个角度或是某个层面上对问题进行分散和孤立 的研究，同时在现有的研究中，着重于算法的应用，而缺乏从企业的生产经营系 统分析、数据抽取、数据预处理、模型构建与评价等一整套完整的解决方案。对 模型所获得的结果的自然语言表示过程也比较缺乏。 ( 3 ) 基于数据挖掘技术的电信客户细分，一般都应用现有的聚类算法，如 k m e a n s 、s o m 、b i r c h 等算法，但在分析过程中很少提到聚类数目的确定与聚 类效果的评价。 1 4 本文的研究内容 在实际应用中主要利用数据挖掘中的聚类算法实现客户细分。目前已存在的 聚类算法大体上可以划分为如下几类：划分方法、层次方法、基于密度的方法、 基于网格的方法、基于模型的方法等【1 1 。但由于这些聚类方法采用欧氏距离、均 值、方差等概念，从而导致类的数据样本分布适合于超球形【1 2 】，而对于螺旋线、 椭圆甚至不具有任何形状的非规则分布数据集合则比较欠缺。为了发现任意形状 的聚类结果，提出了基于密度的聚类方法。d b s c a n ( d e n s i t y b a s e ds p a t i a l c l u s t e r i n go f a p p l i c a t i o n sw i t hn o i s e ) 是一种基于密度的典型聚类方法【1 3 】，该算 法有效地解决了非规则样本数据分布的问题，并得到较为广泛的研究。但由于算 法采用全局变量和m i n p t s ，导致不同的参数产生不同的聚类结果。对于真实的 高维数据集合而言，参数的设置通常是依靠经验，难以确定。设置的细微不同可 能导致差别很大的聚类结果，而且，真实的高维数据集合经常分布不均，全局密 度参数不能刻画其内在的聚类结构。而本文正是针对这些问题，试图提出一种新 的基于密度的聚类算法，并将其应用于电信客户细分。 所做的研究工作有： 首先，针对已有的密度聚类算法不能很好的处理数据点密度分布不均的聚类 难题，提出了一种新的基于代表点和点密度的聚类算法( c b r d ) ，该算法可以 发现任意形状的密度分布不均的聚类。 其次，虽然新算法具有发现任意形状的密度分布不均的聚类的优点，但是不 适合于大规模数据库聚类，不能够很好的应用于客户细分。因此在c b r d 算法 的基础上，提出了一种基于数据交叠分区的高效密度聚类算法，该算法不仅可以 发现任意形状的密度分布不均的聚类，而且具有较高的运行效率。 最后，成功地将本文所提出的算法应用于电信客户细分，验证了算法的有效 性。 4 - 硕士学位论文 1 5 本文组织结构 各章的主要内容如下： 第一章：介绍了课题的研究背景和意义、聚类算法和客户细分的研究现状， 以及客户细分中存在的问题，最后介绍了论文的研究内容和组织结构。 第二章：主要介绍了聚类分析的相关概念、聚类分析中的数据结构和数据类 型、聚类算法性能衡量指标、聚类算法的划分，并对常用的聚类算法进行比较。 第三章：详细分析了密度聚类算法中的d b s c a n 算法，并提出了一种新的 密度聚类算法，通过实验验证其正确性。 第四章：在第三章算法的基础上，提出了一种能够处理大规模数据的高效密 度聚类算法，并通过实验验证其正确性。 第五章：将第四章提出的新算法应用于电信业客户细分中。 最后总结全文，指出新算法需要继续完善的地方。 基于密度的聚类算法研究及其在电信客户细分中的成用 第2 章数据挖掘中的聚类分析 本章简要介绍了聚类算法的基本概念和一些常用的聚类算法。聚类分析研究 有很长的历史，几十年来，其重要性以及与其他研究方向的交叉特性得到人们的 肯定。聚类是数据挖掘、模式识别等研究方向的重要研究内容之一，在识别数据 的内在结构方面具有极其重要的作用。聚类分析在许多领域都得到了广泛应用， 如市场或客户细分、模式识别、生物学研究、空间数据分析、w 曲文档分类等。 聚类分析可以作为一个独立的数据挖掘工具，用来了解数据分布情况，也可以作 为其他数据挖掘算法的预处理步骤。 2 1 聚类分析的定义 聚类分析( c l u s t e r a n a l v s i s ) 【1 4 l 是一个将数据集划分为若干组或类的过程， 并使得同一个组内的数据对象具有较高的相似度；而不同组中的数据对象是不相 似的。相似或不相似的描述是基于数据属性的取值来确定的，常利用( 各对象间) 距离来表示。 将一组物理的或抽象的对象，根据它们之间的相似程度，分成若干组；其中 相似的对象构成一组，这一过程称为聚类过程。聚类和分类有不同之处，在分类 问题中，是在知道训练样本的分类属性的情况下，将数据对象分到不同的已知类 中；而在聚类问题中，是在划分的类未知的情况下，将数据对象分组成不同类， 需在样本中找到这个分类属性。 2 2 聚类分析中的数据结构和数据类型 2 2 1 数据结构 大多数聚类算法采用如下两种具有代表性的数据结构。 ( 一) 数据矩阵 数据矩阵( d a t am a t r i x ) 是一个对象一属性结构。它是由，1 个对象组成，是 利用p 个属性来进行，1 个对象的描述。数据矩阵采用以p 矩阵来表示，如下： 五1五2 而1 砀 x nx p 2 五。 恐。 ： ( 二) 相异度矩阵 相异度矩阵( d i s s i m i l a r i t ym a t r i x ) 是一个对象一对象结构。它存放所有，1 个 硕士学位论文 对象两两之间所形成的差异性( 相似性) 。相异度矩阵采用刀刀矩阵来表示，如 下： o d ( 2 ，1 ) 0 ： d ( 甩，1 ) d ( 一，2 ) 0 其中，d ( f ，) 是对象f 和对象f 之间的相异性的量化表示，通常为一个非负数， d ( f ，j ) = d ( j ，f ) ，d ( f ，f ) 一o 。对象f 和对象j 越相似或彼此越“接近”时，该数值d ( f ，j ) 越接近0 ；对象f 和对象f 差异越大，该数值d ( f ，f ) 越大。 数据矩阵的行和列含义不同，行与列代表不同的实体，有时也称为二模矩阵； 而相异度矩阵的行与列代表相同的实体，有时也称为单模矩阵。许多聚类算法以 相异度矩阵为基础。如果数据以数据矩阵形式给出，则往往需将数据矩阵转换成 相异度矩阵，相异度矩阵可用距离公式计算得到。相异度有时也称为距离。 2 2 2 数据类型 聚类分析中常用的数据类型有区间标量变量、二元变量、标称型变量、序数 型变量、比例标度型变量和混合类型的变量。相异度d ( f ，) 的具体计算会因所使 用的数据类型的不同而异。 ( 一) 区间标度变量 区间标度度量是一个粗略线性标度的连续度量，比如重量、高度、温度等。 选用的度量单位将直接影响聚类分析的结果，一般而言，度量单位越小，变量的 取值范围越大，对聚类效果的影响就越大。为减小度量单位的选择对聚类效果的 影响，需要实现度量值的标难化，将原来的值转化为无单位的值。 给定一个变量厂的度量值，可使用以下转化： 1 计算平均的绝对偏差 其计算公式如下： s ，一言( 1 五，一所，l + i 恐，一朋，i + + i 一肌，i ) ( 2 1 ) 其中m ，一丢( 葺，+ 屯，”+ 两) 。 2 计算标准化的度量值( z s c o r e ) 其计算公式如下： 基于密度的聚类算法研究及其在电信客户细分中的应用 7 x 叮一m f 乙i ( 2 2 ) 使用平均的绝对偏差往往比使用标准差更具有健壮性。与其他偏差的度量方 法相比，孤立点的z s c o r e 值不会太小，容易被发现。 在对数据进行标化处理后，对象间的相似度和相异度是基于两个对象间的距 离来计算的。常用的距离度量公式有欧几里得( e u c l i d e a n ) 距离公式和曼哈顿 ( m a n h a t t a n ) 距离公式以及闽可夫斯基( m i n k o w s k i ) 距离公式。 欧几里得距离： 俐) ；石i 阿i 可i i 可 ( 2 3 ) 其中，f 一 。，五：，) 和j 一( t 。，工j ：，) 是两个p 维的数据对象。 曼哈顿距离： d ( f ，_ ) 一i 。一x 口| + | 毛：一x ，：i + - + k 一j ( 2 4 ) 闵可夫斯基距离是欧几里得距离和曼哈顿距离的概化，闵可夫斯基距离： 俐) ；石i 阿i 可i 再可 ( 2 5 ) 上式中，q 为正整数，如果口；1 表示曼哈顿距离，如果口一2 则表示欧几里得 距离。 距离公式有如下特性： d ( f ，j f ) 芝0 ； d ( f ，j ) = o ； d ( f ，j ) 一d ( j ，f ) ； d ( f ，歹) sd o ， ) + d ( ，j ) 。 ( 二) 二元变量 一个二元变量只有两个状态，取o 或l 值；其中o 代表( 变量所表示的) 状 态下不存在；而1 则代表相应的状态存在。 表2 1 给出二元变量的可能性，每个对象有p 变量，p = 口+ 6 + c + d ，口表示 对象f 和对象f 的值都为1 的变量的数目，d 表示对象i 和对象7 的值都为o 的变 量的数目，6 表示对象f 为1 、对象f 的值为0 的变量数目，c 表示对象f 为0 、对 象，的值为1 的变量数目。一个二值变量取o 或1 所表示的两个状态同等重要， 也就是取值o 或1 没有优先权，那么该二值变量就是对称的；一个二值变量取0 或1 所表示的内容的重要性不一样的，那么该二值变量就是非对称的。 硕士学位论文 对于对称的二元变量，用简单匹配系数来评价两个对象之间的相异度，公式 如下： 蚓) = 志 ( 2 6 ) 口+ d + c + 口 对于非对称的二元变量，用j a c c a r d 系数来评价两个对象之间的相异度，公 式如下： 删) 一羔 ( 2 7 ) 口+ d + c ( 三) 标称型变量 标称型变量是二元变量的一个扩展。标称型变量可以对两个以上的状态进行 描述。对标称型变量，其对象之间的相异度用以下两种方法来计算： ( 1 ) 简单匹配方法，其计算公式如下： m _ ) ，旦旦( 2 8 ) 其中，肌表示对象f 和对象f 取同样状态的变量个数( 匹配数) ；p 为所有变 量的个数。 ( 2 ) 用二元变量为每一个状态创建一个新的二元变量，对于具有给定状态 的一个对象，代表这一状态的二值变量设为1 ；而其他的二值变量设为0 。用非 对称的二元变量来编码标称型变量，将标称型变量的相异度的计算转化为二元变 量的相异度计算。 ( 四) 序数型变量 一个序数型变量可以是连续的，也可以是离散的。离散的序数型变量与标称 型变量相似。连续的序数型变量看上去就像一组未知范围的连续数据，类似于区 间标度变量，但它没有单位，值的相对位置要比它的实际数值有意义得多。对序 数型变量相异度的计算与区间标度变量的计算相类似。将连续的序数型变量值划 分为有限个区间，从而将其值离散化。这些区间用有限个有序状态表示，可定义 为一个排列1 ，2 ，m ，在此m ，是状态的个数。若变量的值落在第，个区间内， 且哳 1 ，2 ，m ，) ，则称0 为该值对应的秩。假设变量厂为一组描述，1 个对象序 摹于密度的聚类算法研究及其在电信客户细分中的应用 数型变量中的一个。变量厂的相异程度计算方法用如下策略： ( 1 ) 第f 个对象的厂变量值标记为而，将两用对应的秩0 代替。 ( 2 ) 用乃替代膏，将每个顺序变量的取值范围映射到f 0 ，1 1 区间，以使每个 变量的权重相同。 乃= 为 ( 2 9 ) ( 3 ) 用乃替换第f 个对象中的变量厂值，用区间标度变量的任一种距离公式来 计算相异度。 ( 五) 比例标度型变量 比例标度型变量是在非线性的标度上取正的测量值，诸如指数比例，a 矿或 a e 一，( a 和曰为正的常数) 。目前有三种方法计算比例标度型变量的相异度。 ( 1 ) 将比例标度型变量当作区间标度变量来进行计算处理，但这不是一个 好方法，因为标度可能被扭曲了。 ( 2 ) 利用对数转换方法对比例标度型变量的值进行转换，然后将转换后得 到的值，采用与处理区间标度变量相同的方法计算相异度。 ( 3 ) 将比例标度型变量当作连续的序数型变量，即将其顺序值( 秩) 作为 区间标度的值来进行相应的计算处理。 选择所使用的方法与相应的应用相关，但后两个方法比较有效。 ( 六) 混合型的变量 在实际数据库中，数据对象往往是用复合数据类型来描述；而且它们常常同 时包含上述几种数据类型。 混合类型的变量对象间的相异度的描述相对要复杂一些。一个可取的方法就 是将所有不同类型的变量放在一起进行处理，一次性完成聚类分析。将不同类型 变量( 值) 组合在同一个差异矩阵中，结合所有有意义的变量，将它们的值域全部 映射到f 0 ，1 1 区间内，对象f 和对象_ 之间的距离d ( f ，_ ) 就可以表示为： 岁6 ；n 彤 d ( f ，j ) 一上 一 ( 2 1 0 ) 弩6 1 厂 角” 其中，p 为对象中变量的个数，如果勺或b 为数据不存在( 对象l 或对象歹无 变量厂的测量值) ；或= h = o ，且变量厂为非对称二元变量，那么，标记6 5 ，= o ； 否则醚，一1 。变量厂对对象f 和对象j 之间相异度的计算方法与厂的具体类型有 关。 ( 1 ) 若变量厂为二元变量或标称型变量，则如果b = 勤，那么，掣- o ，； 硕士学位论文 否则衫= 1 。 li ( 2 ) 若变量厂为区间标度变量，则彤；上t ! 掣一，其中 遍取变量 1 n a x 研一l m i l 研 厂的所有非空缺对象。 ( 3 ) 若变量厂为序数型变量或比例标度型变量，则计算顺序值( 秩) 白和 乃。者若，并将z i ，当作区间标度变量来进行计算处理。 综上所述，即使描述对象的变量是不同类型，每两个对象间的相异度也能够 计算出来。 2 3 算法性能衡量指标 通常情况下，对于同一个问题可以用几种不同的算法来解决，衡量算法性能 的指标有： ( 1 ) 可伸缩性。如果一个算法既适用于小数据集合，又在大型数据库上进 行聚类不会导致有偏差的结果，这个算法具有高度的可伸缩性。 ( 2 ) 处理不同类型属性的能力。有的算法只能用来聚类数值型的数据，但 是，在某些应用中要求聚类非数值型数据。 ( 3 ) 发现任意形状的聚类。许多基于距离的算法只能发现具有相近尺度和 密度的球状簇。而算法能否发现任意形状的簇很重要，如螺旋型。 ( 4 ) 最少的参数和确定参数值的领域知识。许多聚类算法要求用户输入一 定的参数，如希望产生的簇的数目。聚类结果对输入参数十分敏感，输入参数又 给用户增加了负担，因此应尽量避免。 ( 5 ) 处理噪声数据的能力。多数数据库中都包含孤立点、空缺、未知数据 或错误的数据，算法应尽量降低这些数据的影响。 ( 6 ) 对于输入记录的顺序不敏感。算法能否与集合的输入顺序无关。 ( 7 ) 高维性。算法在应付低维数据的同时能否处理高维数据。例如高维空 间的非常稀疏、高度偏斜的数据。 ( 8 ) 基于约束的聚类。现实世界的应用可能需要在各种约束条件下进行聚 类。 ( 9 ) 可解释性和可用性。用户希望聚类结果是可解释的、可理解和可用的。 2 4 聚类分析划分 目前在文献中存在大量的聚类算法。算法的选择取决于数据的类型、聚类的 目的和应用。如果聚类分析被用作描述或探查的工具，可以对同样的数据尝试多 基于密度的聚类算法研究及其在电信客户细分中的应用 种算法，以发现数据可能揭示的结果。 大体上，主要的聚类算法按其采用的方法可以划分为如下几类：划分方法、 层次的方法、基于密度的方法、基于网格的方法、基于模型的方法。 2 4 1 基于划分的聚类方法 给定一个包含n 个数据对象的数据库，以及要生成的簇的数目k ，一个划分 类的算法将数据对象组织为k 个划分( 七s 万) ，其中每个划分代表一个簇【1 5 】。通 常会采用一个划分准则( 经常称为相似度函数) ，例如距离，以便在同一个簇中 的对象是“相似的”，而不同簇中的对象是“相异的”。最著名与最常用的划分方 法是k 平均，k 中心点和它们的变种。这些聚类方法在对中小规模的数据库中发 现球状簇很适用。为了对大规模的数据集进行聚类，基于划分的方法需要进一步 的扩展【1 6 j 。 2 4 2 基于层次的聚类方法 层次聚类方法是创建一个层次以分解给定的数据集，递归地对对象进行合并 或者分裂，直到满足某一终止条件为止【1 1 7 1 。根据层次的分解如何形成，层次聚 类方法可分为凝聚的和分裂的两种【1 8 】。典型的层次方法有：b i r c h 、c u b e 、 r o c k 、c h e m a l o e n 、a g n e s 、d i a n a 等。层次聚类的优点在于算法能得到 不同粒度上的多层次聚类结构，缺点在于一旦一个步聚( 合并或分裂) 完成，它就 不能被撤消，因此不能更正错误的决定。改进层次方法聚类质量的一个有希望的 方向是将层次聚类和其他聚类技术集成，形成多阶段聚类。 2 4 3 基于密度的聚类方法 大部分划分方法基于对象之间的距离进行聚类，只能发现球状的簇，而不能 发现任意形状的簇，为了发现任意形状的簇，提出了基于密度的聚类方法。其主 要思想是：只要临近区域的密度( 对象或数据点的数目) 超过某个阈值，就继续聚 类，即对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数 目的点。典型的基于密度的聚类算法包括：d b s c a n 、o p t i c s 、d e n c l u e 、 d b c l s d 、g d b s c a n 等。 2 4 4 基于网格的聚类方法 基于网格的聚类算法【1 9 】是采用一个多分辨率的网格数据结构，将数据空间 量化为若干单元，形成一个网格结构，所有的聚类操作都在此网格上进行。这个 方法的主要优点是处理速度很快，其处理时间独立于数据对象的数目，只与量化 硕十学位论文 空间中每一维的单元数目相关。典型的基于网格的聚类方法有s t i n g 、 w a v e c l u s t e r 和c l i q u e 等。 2 4 5 基于模型的方法 基于模型的方法【2 0 l 为每个簇假定了一个模型，寻找数据对给定模型的最佳 拟合。一个基于模型的算法可以通过构建反映数据点空间分布的密度函数来定位 聚类，它也基于标准的统计数字自动决定聚类的数目，考虑“噪声”数据或孤立 点，从而产生健壮的聚类方法。典型的基于模型的聚类方法包括统计学方法f 如 c o b w e b 、c l a s s i t 和a u t o c l a s s ) 或神经网络方法( 例如s o m 、a r t 、l v q ) 。 2 5常用聚类算法的比较 1 、k r o t o t y p e s 算法( 基于距离的划分方法) 【2 1 】 该算法综合了k m e a n s 方法和k m o d e s 方法的特点，能够处理数值类型和 符号类型的数据。数值类型用欧式距离测量相似性，符号类型用海明距离测量相 似性，将两部分综合起来构造评价函数，是