（管理科学与工程专业论文）基于聚类技术的客户细分研究与应用.pdf

南京邮电大学硕士研究生论文摘要 摘要 近年来，随着手机终端价格和移动通信业务资费的大幅降低，我国移动通信客户数持 续高速增长，至2 0 0 6 年底，移动电话客户规模达到4 6 亿；与此同时，随着通信技术的日 新月异，客户对移动通信产品的消费需求也愈趋复杂多样。显然，面对规模庞大的移动通 信客户群体以及巨大的消费需求差别，传统基于人口统计数据的客户细分方法已经难以深 入了解客户需求和有效识别高价值的客户。而基于聚类技术的客户细分是通过对蕴含客户 消费行为模式的运营数据进行多维分析，可以深入刻画客户消费特征、清晰显示客户消费 的差别。该细分方法已经引起市场研究人员的广为认同。 在大量有关基于聚类技术的客户细分的论文中，k 均值算法由于原理简单，具有可伸 缩性，应用最为普遍。然而，传统k 均值算法存在一些缺陷，主要是需人为指定聚类个数、 距离度量测度单一和聚类结果易受初始质心的影响等缺陷。这些缺陷严重影响了算法的实 际使用效果。基于此，本文首先对k 均值聚类算法进行了研究。以k 均值算法的三个缺陷 为切入点尝试做相应的改进，具体包括尝试利用w a r d 氏层次聚类算法确定簇个数的方法 以及基于四分位相对离差系数的加权方法提高聚类质量；在前人研究初始质心思路的基础 上设计实现了二分k 均值降低聚类结果易受初始质心的影响，并通过实验数据验证改进效 果；在改进方法的基础上提出了一套完整的聚类分析方法流程b k w w ( b i s e c t i n gk 玉，l e a n s b a s e do nw e i g h ta n dw a r d s ) 。然后，本文以移动通信行业为背景，收集了江西某地移动公 司的客户资料和消费数据，应用b k w w 聚类方法分别对在网和离网客户进行了细分，并 将聚类细分结果与传统k 均值聚类结果通过凝聚分离系数进行了效果比较，结果表明 b k w w 聚类方法有效地提高了聚类效果。 南京邮电大学硕士研究生学位论文 a b s t r a c t w i t ht h ep r i c eo fm o b i l ep h o n et e r m i n a l sa n dm o b i l eb u s i n e s sl a r g e l yr e d u c e d ，t h en u m b e r o fm o b i l ep h o n ec u s t o m e r sh a sg r o w na th i g hs p e e df o rt h ep a s tt w oy e a r s t h en u m b e ro fm o b i l e p h o n ec u s t o m e r sh a ss c a l e dt o4 6 0m i l l i o na tt h ee n do f2 0 0 6 m e a n w h i l e ，w i t l lt h er a p i d d e v e l o p m e n to fc o m m u n i c a t i o nt e c h n o l o g y , c u s t o m e rd e m a n d so fm o b i l ec o m m u n i c a t i o n p r o d u c t sa r eb e c o m i n gm o r ec o m p l e xa n dd i v e r s e f a c e dw i t hal a r g eg r o u po fc u s t o m e r sa n d h u g ed i f f e r e n c e si nc u s t o m e rd e m a n d s ，c e n s u sd a t as e g m e n t a t i o nm e t h o di sd i f f i c u l tt oo b t a i n g o o dr e s u l t s t h es e g m e n t a t i o ns t i l lr e m a i n st h el e v e lo fr o u g hs e g m e n t a t i o n c u s t o m e rs e g m e n t a t i o n w i t hc l u s t e r i n gt e c h n i q u e sa u t o m a t i c a l l yc o n d u c t sm u l t i d i m e n s i n a la n a l y s i sa b o u tc u s t o m e r s d a t at o o b t a i nt h ec u s t o m e rb e h a v i o rp a r e r n i tc o n t r i b u t e st oc h a r a c t e r i z i n gc u s t o m e rb e h a v i o ra n d u n d e r s t a n d sc u s t o m e rd e m a n d s oc u s t o m e rs e g m e n t a t i o nw i t hc l u s t e r i n gt e c h n i q u eh a sb e e n w i d e l yr e c o g n i z e db ym a r k e t i n gr e s e a r c h e r s k m e a r l sa l g o r i t h mi sac l a s s i ca l g o r i t h m t h ep r i n c i p l ei ss i m p l ea n ds a c a l e d s ok j v l e a n s h a su n i v e r s a la p p l i c a t i o n n e v e r t h e l e s s ，k j v i e a n sh a st h r e ed e f e c t s i n c l u d i n gs u b j e c t i v e d e t e r m i n a t i o no fc l u s t e r sn u m b e r ，s i n g l ea t t r i b u t er o l e ，a n dc l u s t e rg r e a t l ya f f e c t e db yi n i t i a l c e n 仃o i d s t h i sp a p e ra t t e m p t st oi m p r o v et h ed e f e c t s t h ei m p r o v e m e n t si n c l u d ea p p l y i n gw a r d s h i e r a r c h i c a lc l u s t e r i n gi n t od e t e r m i n i n gt h en u m b e ro fc l u s t e r ，w e i g h t e da t t r i b u t e si m p r o v et h e q u a l i t yo fc l u s t e r ，a n db i s e c t i n gk m e a n sa l g o r i t h mr e d u c e st h ee f f e c to fi n i t i a lc e n t r o i d s t h i s p a p e rd e v e l o p san e wc l u s t e r i n gt e c h n i q u eb a s e do nt h r e ei m p r o v e m e n t t h et e c h n i q u ei sc a l l e d b i s e c t i n gk l v e a n sb a s e do nw e i g h ta n dw a r d s t h e nt h ep a p e ra p p l i e sb k w wc l u s t e r i n g t e c h n i q u e i n t o b u i l d i n gm o d e lo fc u s t o m e rs e g m e n t a t i o n 、而t h m o b i l ec o m m u n i c a t i o n b a c k g r o u n da n dm a k e st h em a r k e t i n ge x p l a n a t i o na b o u tt h em o d e l t h ep a p e rc o m p a r e sb k w w m o d e l 、杭t l lk 1 v l e a n sm o d e lb ye v a l u a t i o nf u n c t i o n sa p p l i c a t i o n t h ee v a l u a t i o ns h o w st h e b k w wm e t h o di m p r o v e sk 1 v l e a n sc l u s t e r i n gq u a l i t y i i 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：缢吼j v 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：_ 乏，磁赫师签名：日期：以6 矿 南京邮电大学 硕士学位论文摘要 学科、专业：管理学管理科学与工程 研究方向： 企业集成管理与企业信息化 作2 0 0 4 级研究生毛晓晨指导教师郑惠莉 题目：基于聚类技术的客户细分研究与应用 英文题目：c u s t o m e rs e g m e n t a t i o nb a s e do nc l u s t e r i n gt e c h n i q u e s r e s e a r c h & a p p l i c a t i o n 主题词：聚类分析k 均值二分k 均值w a r d 氏聚类 客户细分移动通信市场 k e y w o r d s ：c l u s t e r i n ga n a l y s i s k m e a n s b i s e c t i n gk m e a n s w a r d sc l u s t e r i n gc u s t o m e rs e g m e n t a t i o n m o b i l ec o m m u n i c a t i o nm a r k e t 南京邮电大学硕士研究生学位论文第一章绪论 1 1 研究背景 第一章绪论 近年来，随着手机终端价格和移动业务资费的大幅降低，移动手机客户数持续高速增 长。至2 0 0 6 年底，移动电话客户数规模达到4 6 亿。规模庞大的客户群体覆盖了各个年 龄段、职业种类和收入层次。客户背景的巨大差别造成了其需求、偏好也存在着巨大差异。 而这样的差异往往表现在消费行为模式上。如果缺少对不同客户的认识和细分，采用“大 一统 的营销方式，不仅造成了高额的营销成本，而且难以收得明显的营销效果。客户细 分辅助营销的重要性已成为各大运营商的共识。 、 当前，各大通信运营商运用的客户细分方法以人口统计细分和心理细分为主，通常按 照客户一维或二维的自然属性进行客户分群来帮助企业识别客户的消费需求、合理配置服 务资源。这种细分依靠人工手段，多以一维、二维的维度，细分粒度较粗，划分为同一群 体客户的需求往往存在很大偏差，进而造成根据细分方法制定的营销方案的效果大打折 扣。为了以更深入的视角细分客户群，相关研究人员尝试基于客户消费行为的细分方法。 基于客户消费行为的细分方法主要分析反映客户消费行为的数据。这些数据多是电信 行业各类业务系统( b s s 、o s s 等) 积累的事务型数据。这些数据规模大、维度高。传统 分析技术面对这些数据已经显得“力不从心一。而聚类技术对大量运营数据自动化地多维 分析，发现数据中蕴含的客户消费模式，辅助企业制定针对性的营销方案。因此，基于聚 类技术的客户细分的研究日益受到国内研究人员的重视。电信行业相关的研究人员纷纷开 展基于聚类技术的研究与应用。如范英等人采用k j e a i l $ 算法分析通信客户的消费帐单进 行细分【2 l ；王军在s p s sc e l e m e n t i n e 的平台上利用t w o s t e p 算法分析客户使用各种通信服 务的行为数据p j 。 在聚类技术中，k 均值算法是聚类算法中的经典算法。其原理简单，具有可伸缩性。 在大量有关基于聚类技术的客户细分研究的论文中，k 均值( k m e a n s ) 算法应用最为普遍。 但k 均值算法本身具有许多缺点，如：需要人为指定聚类个数、度量测度采用单一的距离 公式、聚类结果易受初始质心的影响等。直接应用k 均值算法进行客户细分会严重影响聚 类效果。 本文的工作正是基于这样一个背景下开展的。首先针对细分方法中所用k 均值聚类技 l 南京邮电大学硕士研究生学位论文第一章绪论 术的多个不足，提出相应的改进方法并验证改进效果。在若干个改进方法的基础上，提出 一个完整的聚类方法b k w w ( b i s e c t i n gk m e a l l sb a s e d o nw e i g h ta n dw 莉s ) 。然后，以移 动通信行业为背景，收集江西某地移动公司客户的基本资料、消费数据，应用聚类方法流 程建立在网、离网客户细分模型，解释细分后客户群体之间的差异并与传统的k 均值聚类 模型进行比较。 1 2 国内外相关研究与应用现状 1 2 1 客户细分理论研究 市场细分是由美国市场营销学家w e n d e l ls m i t h 【4 】于2 0 世纪5 0 年代中期首次提出来的。 所谓市场细分是指按照消费者欲望与需求把一个总体市场( 总体市场通常太大以致企业很 难为之服务) 划分成若干具有共同特征的子市场的过程。因此，分属于同一细分市场的消费 者，他们的需要和欲望极为相似；分属于不同细分市场的消费者对同一产品的需要和欲望 存在着明显的差别。 自从市场细分的概念被提出以来，大量的学者和实践人员加入到有关的研究中来。他 们依据所处的时代和行业提出相应的市场细分方法。这些方法依据两种不同的市场理念产 生了两个分支：以产品为导向的细分和以客户为导向的细分。以产品为导向的细分主要为 营销实践人员所采用，他们根据不同营销决策目标( 产品定位、定价、广告定位等) ，围 绕产品或品牌的特定消费情境对客户细分，细分变量包括产品使用率、消费态度、追求的 利益，目的是要了解消费者对产品或品牌的心理需求和消费行为差异，选择最有利的目标 客户群以及恰当的营销策略：以客户导向的细分，主要为营销研究人员所采用，他们以顾 客总体特征为细分维度对消费者分群，运用分析解剖方法论，从个体心理、社会文化环境 和行为决策过程等三个不同侧面对消费者进行细分。随着从关注产品到关注客户的理念转 换使得后者更具吸引力【5 】。通常谈到的客户细分概念主要来源于以消费者为导向的市场细 分。 以客户为视角的各种细分方法其基本的维度范围主要包括：人口特征、行为特征和心 理特征。具体的说，人口特征包含了客户展现出来的外部特征，行为因素则表现为客户的 具体购买行为，心理特征则反映客户行为决策中的兴趣和态度。依据维度的不同，细分方 法分为人口统计细分、行为细分和心理细分三类。 1 、人口统计细分：人口统计细分方法的理论以人口特征、地理特征与客户需求之间 2 南京邮电大学硕士研究生学位论文 第一章绪论 具有一定的联系的前提。细分方法主要从地理区域、人口统计( 性别、年龄、职业、收入 等) 外部特征对潜在客户细分。这种方法的细分粒度较粗，并且许多实践表明，具有相同 人口地理特征的消费群在面对相同的营销时反应不一，因此目前人口统计细分方法很少单 独使用，更多的是跟其他细分方法综合使用。 2 、心理细分：对客户心理细分的研究源于一种假设客户购买决策表现的心理因 素决定客户购买行为。细分方法根据客户所处的社会阶层、生活方式、个性特点等心理因 素细分客户总体。由于客户购买决策表现的心理与客户购买情景相关，心理因素易受情景 发生变化难以把握，因此细分效果往往大打折扣。 3 、行为细分：行为细分的理论假设是根据客户以往和现在的行为可以预测将来的行 为。细分方法通过统计和r r 工具分析数据库中蕴含已有客户的消费行为模式将客户分类。 随着信息化不断地深入，不少企业积累了大量蕴含客户消费行为模式的数据，为客户行为 细分提供广阔的平台。近些年该领域吸引了越来越多的来自各个背景的研究人员。他们结 合自己本身的理论背景( 统计、数据挖掘等) 提出许多定量的行为细分技术。主要包括r f m 技术、客户价值矩阵分析、数据挖掘方法。 ( 1 ) r f m 分析 h u g h e s 在1 9 9 4 年提出的r f m 分析是以三个行为变量来描述和区分客户 6 1 。 r ( r e c e n c y ) ，指上次购买到现在的时间间隔，f ( f r e q u e n c y ) 为某一期间内购买的次数，m ( m o n e t a r y ) 是某一期间购买的金额。r f m 分析针对每个客户的每个指标打分，然后计算 三个指标的乘积，再按所得结果排序，在此基础上将所有的客户按照2 0 、6 0 、2 0 分 类，最后对不同类型的客户实施不同的策略。r f m 分析的因素都是行为方面的，这些数据 对拥有数据库的公司比较容易得到，但是其分析过程复杂，非常耗时，且细分结果中的客 户群过多。 ( 2 ) 客户价值矩阵分析 为了回避r f m 分析的缺点，m a r c u s 在1 9 9 8 年提出用购买次数f 与平均购买额a 构 造二维的客户价值矩阵模型用来修正r f m 方法【7 1 。该矩阵需要的信息包括客户代码、购买 日期、日购买额。购买次数由不同购买日期的数目来确定，平均购买额等于在指定时间间 隔内总购买额( 日购买额的总和) 与购买次数的比值。最终所以客户都分散在事先确定的 二维矩阵的四个象限中，针对每一个客户群或跨越客户群产生不同的营销战术。 ( 3 ) 数据挖掘方法 数据挖掘是从海量、不完全的、有噪声的数据中利用数据挖掘算法挖据出隐含的、未 知的、用户可能感兴趣的和对决策有潜在价值的知识和规则f 引。当前数据挖掘广泛、深入 3 南京邮电大学硕士研究生学位论文 第一苹绪论 地应用到客户细分、客户保持和交叉销售等方面的分析，为市场营销、客户关系管理提供 有力的支持。数据挖掘技术典型的分析手段有分类、聚类、关联等。每类方法有很多不同 特点的算法，如分类方法有决策树算法、神经网络算法，聚类算法有划分聚类算法、分层 聚类算法等。在客户细分中，聚类技术是最为常用的技术。由于能够处理高维度和类型复 杂的数据且自动化地产生各个类，聚类技术可以更加深入、全面地细分客户。 1 2 2 基于聚类技术的客户细分研究 聚类分析是数据挖掘中最重要的方法之一。聚类分析将一组数据分类，使其具有最大 的簇内相似性和最小的簇间相似性，即分析结果达到不同簇中的数据尽可能地不同，而同 一簇中的数据尽可能地相似。聚类分析的思想与客户细分的思想非常吻合。因此聚类分析 在商业上应用地非常广泛。比如在电信领域从市话、长途、漫游、短信等多个维度细分客 户消费行为，帮助企业了解客户需求的差异，识别高价值的客户【9 1 。在金融领域聚类分析 不仅用于细分客户，还用于侦测客户欺诈。欺诈客户在众多客户中只是极个别，在大量的 交易数据中与其他数据明显不同，表现为数值明显不符现实或与普通客户差异很大。聚类 分析在划分各个类的同时，也能够发现异常对象。这些异常对象有可能是欺诈者【l 们。 有关基于聚类技术的客户细分研究在国外已经有了一定的发展，比如m e l o d yy k i a n g 等采用s o m ( s e l f - o r g a n i z i n gm a p ) 聚类算法细分电信客户f l l l ；g e o r g i o sp p a p a m i c h a i l 等采 用k m e a n $ 划分聚类算法结合空间数据结构对购物网站用户的浏览网页和搜索数据进行细 分【1 2 1 ；p a w a nl i n g r a s 等结合模糊集理论改进s o m 聚类算法，并将其应用到研究超市各个 顾客群特征以2 4 个星期为时间段中的周期变化1 1 3 】。 相对来说国内有关这方面的研究还处于起步阶段，主要是使用典型的聚类算法分析。 范英等采用k m e a n $ 分析通信客户的消费帐单进行细分【2 】；刘群采用模糊聚类从分析银行 个人客户的基本属性和r f m 指标入手细分银行个人客户i l 卅；陈伯成等将s o m 算法分析客 户r f m 指标，根据综合指标的计算和各个指标的相对学习结果变化趋势将客户分类1 1 5 】。 当前，基于聚类技术的客户细分研究大致思路是：根据所分析的主题和所在行业，确 定细分指标。然后探索指标数据集的特点，依据算法的适用范围确定合适的聚类算法。由 于典型的聚类算法存在一定的缺陷，需要针对处理数据集特点和建模中的问题进行改进。 有时也会综合应用多个聚类算法，比如分阶段应用将前一个聚类算法分析结果作为下一个 聚类算法的分析基础。在建立客户细分模型之后，分析人员研究每个细分客户群的特征以 及相互间的差异，制定针对各个客户群的营销方案。聚类具有自动化处理高维、大规模数 4 南京邮电大学硕士研究生学位论文第一章绪论 据集的优势使基于聚类的客户细分可以综合利用多方面的指标、大规模的数据来定量化得 描述细分市场的特征和差异性，从而便于设计针对性的营销方案。因此，聚类细分方法更 多地应用在拥有大量客户属性和消费数据的行业，如电信业、银行业等。 1 2 3 基于聚类的客户细分在我国电信行业的应用 客户细分在我国电信行业的应用从9 0 年代末就已经开始了，主要是定性的角度。采 用的方法主要是人口统计细分、心理细分。2 0 0 2 年中国移动建设经营分析系统，基于聚类 的客户细分开始逐渐引起了研究和实践人员的关注【1 6 1 7 1 。 近两年，国内研究人员纷纷开展聚类技术在电信客户细分中的应用，尝试应用各种聚 类算法进行细分。如范英等采用k m e a l l s 分析通信客户的消费帐单进行细分1 2 1 ：王军在s p s s c e l e m e n t i n e 的平台上利用t w o s t e p 分析客户使用各种通信服务的行为数据【3 】；郭明则采用 基于混合高斯分布的e m 算法分析离网客户离网前一时间段的平均消费行为数据【1 8 】。k 均 值算法是聚类算法中的经典算法，原理简单，具有可伸缩性。很多著名的商用数据挖掘软 件实现该算法，比如s p s s 公司的c l e m e n t i n e 、i b m 公司的i n t e l l i g e n tm i n e r 。在大量相关 论文中，k 均值( k m e a n s ) 算法应用最为普遍。但k 均值算法本身具有许多缺点，其中 包括聚类结果易受初始质心的影响。一般采用多次试验运行算法来避免较差的聚类结果出 现。这种方法在一定程度上可以减少随机化初始质心的影响，但付出相当大的代价。特别 是对大规模数据集，多次运行必然带来巨大的开销。并且多次运行仍具有随机性，不能有 效减小影响。另外，k 均值算法需要人为指定聚类个数。前人多是通过多次设置簇个数的 试验以及自身分析经验确定，这无疑影响了细分的科学性。 从行业应用的角度来看，国内研究人员多以在网客户作为细分对象，主要从在网客户 若干个月的平均各项消费费用入手进行细分 2 , 3 , 1 s 】。有关离网客户细分的研究不是很多。有 关离网客户细分的研究中，郭明、石永华以在网客户细分的静态视角看待离网客户，细分 客户离网前若干个月的平均费用1 8 】【1 9 1 。另外，在确定分析离网前的哪几个月( 时间窗1 ：2 ) 上，研究人员主要通过经验选取。如石永华选取离网前3 个月消费的平均值。这样主观地 选取处于较粗的层面，掩盖了一些客户在离网前波动行为特征，难以深入地刻画客户群之 间的波动差异。 1 3 研究内容与结构安排 结合以上选题背景和国内外相关领域的研究现状，本文将关注基于聚类技术的客户细 5 南京邮电大学硕士研究生学位论文 第一章绪论 分研究和应用为主题，对聚类技术进行系统、深入研究，并结合应用主题的特点，选择适 合主题分析的聚类算法，分别建立在网客户和离网客户的细分模型。 文章的主要思路如下：首先对典型的聚类技术作系统全面地介绍，包括划分聚类k 均 值、层次聚类、时序聚类。然后深入研究应用最为普遍的k 均值算法，详细分析其算法的 优缺点。针对有关人为指定聚类个数、度量测度采用单一的距离公式、聚类结果易受初始 质心的影响等问题提出改进方法。接着在k 均值多个改进方法的基础上形成b k w w ( b i s e c t i n gk i x , l e a n sb a s e do nw e i g h ta n dw a r d s ) 聚类方法。最后根据分析主题，制定相应 的细分流程，应用b k w w 聚类方法建立在网、离网客户细分模型，并评价和比较b k w w 聚类模型和传统k 均值模型。 论文由六部分组成： 第一章，概述本文的研究背景、研究目的以及总体的研究思路。 第二章，概述聚类技术基本理论以及聚类算法原理，主要涉及聚类相关概念、算法类 型、簇的类型以及k 均值、层次聚类、时序聚类等算法的原理。 第三章，首先深入研究k 均值算法初始质心、属性加权以及聚类数目的问题。针对聚 类结果易受初试质心的问题，在前人研究思路的基础上设计并实现验证t - - 分k 均值算法。 接着，分析属性在聚类中的作用，提出采用四分位相对离差系数作为属性权值。然后分析 w a r d 法凝聚聚类和k 均值原理的相似点，提出利用w a r d 凝聚聚类确定聚类数目。最后在 前面研究的基础上提出基于k 均值的b k w w 聚类方法。 第四章，建立在网客户细分模型。首先介绍数据挖掘标准流程，制定在网客户细分流 程。应用b k w w 聚类方法建立细分模型。最后解释聚类结果制定针对性营销方案并通过 凝聚分离系数比较b k w w 聚类模型和传统k 均值聚类模型。 第五章，建立离网客户细分模型。首先比较离网客户与在网客户细分的区别，制定离 网客户细分流程。然后通过基于滑动窗口的时序聚类确定离网客户的分析窗口选取客户细 分指标。最后应用b k w w 聚类方法建模，解释模型。 第六章，对全文进行总结，并且根据自己切身实践感受，提出有关基于聚类技术的客 户细分研究及应用的建议，以及本文研究的局限和进一步的工作。 本文的重点在第三、四、五章。 6 南京邮电大学硕士研究生学位论文第二章聚类技术概述 2 1 聚类分析的概念 第二章聚类技术概述 “物以类聚，人以群分 ，聚类分析是人类一项最基本的认识活动。聚类分析将一组 数据分组，使其具有最大的组内相似性和最小的组间相似性，即分析结果达到不同聚类中 的数据尽可能地不同，而同一聚类中的数据尽可能地相似。 2 2 常用聚类算法的类型 聚类算法的类型种类很多，本章主要介绍典型的聚类算法类型：层次与划分，互斥与 模糊、完全与部分，增量与非增量。 2 2 1 层次与划分 层次与划分是聚类分析中两种最为典型的对立的聚类类型。划分聚类( p a r t i t i o n a l c l u s t e r i n g ) 简单地将数据对象集划分成不重叠的子集，使得每个数据对象有且仅有一个 子集。层次聚类( h i e r a r c h i c a lc l u s t e r i n g ) 对给定的数据对象集合进行层次的分解。它 通过将数据对象组织为若干组并形成一个相应的树来进行聚类的。根据层次分解是自顶向 下还是自底向上形成，层次的聚类方法进一步分为凝聚的和分裂的层次聚类。 2 2 2 互斥与模糊 大部分聚类技术属于互斥聚类( h a r dc l u s t e r i n g ) 。互斥聚类在算法处理和输出始终 将每个对象分配到唯一个子集。模糊聚类( f u z z yc l u s t e r i n g ) 计算每个对象与每个簇的 隶属权值。隶属权值的范围从0 ( 绝对不属于) 到1 ( 绝对属于) 。模糊聚类施加一个约束 条件，每个对象的权值之和必须等于l 。类似地，概率聚类( p r o b i l i t yc l u s t e r i n g ) 计 算每个点属于每个簇的概率，且这些概率的和必须为1 。模糊聚类和概率聚类的优点是有 效避免了像其他聚类算法随意将某接近多个簇的对象随意指派到其中一个簇。模糊聚类通 过将每个对象指派到其最大隶属权值的簇，可以转化为互斥聚类。 2 2 3 完全与部分 完全聚类( c o m p l e t ec l u s t e r i n g ) 处理所有的对象，将每个对象指派到一个簇，而 部分聚类( p a r t i a lc l u s t e r i n g ) 只指派其中一部分。部分聚类主要用在数据集的某些对 7 南京邮电大学硕士研究生学位论文第二章聚类技术概述 象可能不属于明确定义的簇。这些对象可能代表噪声、离群点或“无兴趣”对象。 2 2 4 增量与非增量 这种分法适合在聚类的对象集规模很大，受时间和空间限制。早期的聚类算法处理的 数据集规模不是很大。在数据挖掘领域，处理的数据规模海量，每次进行聚类的时间较长， 而有的时候要进行聚类计算时数据比上一次聚类变化不大，如果重新进行聚类所需时间太 长，而且原来的聚类结果难以利用就产生了增量聚类。增量聚类建立数据更新表和簇表， 进行监控，在适当的时候进行增量更新。 2 3 常见簇的类型 聚类的目的是发现有用的对象组( 簇) ，有用的标准由聚类分析的目标定义。反映现 实的数据集存在许多不同的簇概念，而这些簇也是有用的。为了以可视方式说明这些簇类 型之间的差别，同常使用二维数据点作为处理的数据对象，如图2 1 所示。 ( a ) 明显分离的簇。每个点到同簇 中任意点的距离比到不同簇中所有 点的距离更近 ( b ) 基于中心的簇。每个点到其 簇中心的距离比到任何其他簇中 心的距离更近。 ( c ) 基于邻近的簇。每个点到该簇中至少一个点的距离比到不同簇中任意点的距离更近。 ( d ) 基于密度的簇。簇是被低 密度区域分开的高密度区域。 ( e ) 概念簇。簇中的点具有有整个点集 导出的某种一般共同性质。 图2 一l 用二维点集图示的不同簇类型 8 南京邮电大学硕士研究生学位论文 第二章聚类技术概述 1 明显分离的簇：簇是对象的集合，其中每个对象到同簇中每个对象的距离比到不 同簇中任意对象的聚类更近( 或更加相似) 。有时，使用一个阀值来具体说明簇中所有对 象相互之间必须充分接近( 或相似) 。仅当数据包含相互远离的自然簇时，簇的这种理想 定义才能满足。图2 1 ( a ) 给出一个由二维空间的两组点组成的明显分离的簇的例子。不同 组中的任意两点之间的距离都大于组内任意两点之间的距离。明显分离的簇不一定是球形 的，可以具有任意形状。 2 基于原型的簇：簇是对象的集合，其中每个对象到定义该簇的原型的距离比到其 他簇的原型的距离更近( 或更加相似) 。对于具有连续属性的数据，簇的原型通常是质心， 即簇中所有点的平均值。当质心没有意义时( 例如当数据具有分类属性时) ，原型通常是 中心点，即簇中最有代表性的点。对于许多数据类型，原型可以视为最靠近中心的点；在 这种情况下，通常把基于原型的簇看作基于中心的簇。在聚类过程中，每个对象都被指派 到最邻近的中心，因此得到簇趋向于呈球状。图2 1 ( b ) 给出一个基于中心的簇的例子。 3 基于图的簇：如果数据用图表示，其中图中的点代表对象，而边代表对象之间的 联系，则簇可以定义位连通分支，即互相连通但不与组对象连通的对象组。基于图的簇的 一个重要例子是基于邻近的簇，其中两个对象是相连的，比到不同簇中任意点的距离更近。 以二维点的形式给出这种簇的例子。当簇不规则或缠绕时，簇的这种定义是可用的。但是， 当数据具有噪声时就可能出现问题，因为如图2 1 ( c ) 两个球形簇所示，一个小的点桥就 可能合并两个不同的簇。 4 基于密度的簇：点的密度是指以空间中的一点，单位体积内点的个数。直观的 看，簇的内部点的密度较大，而簇边界上点的密度较小。簇是由具有相似密度的相邻的点 作为一个聚类。图2 - 1 ( d ) 显示的是基于密度的簇。当簇不规则或互相交叉，并且有噪声和 离群点时，常常使用基于密度的簇定义。 5 基于共性的簇( 概念簇) ：更一般地，把簇定义为有某种共同性质的对象的集合。 这个定义包括前面的所有簇定义；例如，基于中心的簇中的对象都具有共同的性质：各个 簇都离相同的质心或中心点的距离最近。除了这个测量标准，共同性质的方法还包含新的 簇类型。图2 - 1 ( e ) 所示的簇是环形区域以及被其包围的矩形区域。在这种情况下，聚类算 法都需要非常具体的簇概念来成功地检测出这些簇。发现这样的簇的过程称为概念聚类。 9 南京邮电大学硕士研究生学位论文第二章聚类技术概述 2 4 典型聚类算法的性能分析 2 4 1 划分聚类 对于一组数据集合，给定聚类数目和目标函数，划分聚类( p a r t i t i o n a lc l u s t e r i n g ) 把数据集划分为给定数目的簇，使得目标函数在此划分下达到最优【2 l 】。划分算法把聚类问 题转化成一个组合优化问题，通常从一个初始划分或者一个初始聚点集合开始，利用迭代 控制策略优化目标。这种聚类技术很多，最典型的是基于原型的k 均值( k m e a n s ) 和k 中心点( k m e d o i d s ) 。k 均值用质心定义原型，其中质心是一组点的均值。通常，k 均值 聚类用于n 维连续空间中的对象。k 中心点使用中心点定义原型，其中中心点是一组点中 最有代表性的点。k 中心点聚类可以用于广泛的数据，因为它只需要对象之间的邻近性度 量。质心不对应实际的数据点；中心点根据定义必须是实际数据点。 1 聊e a n s 算法描速 l q e a n s 数学定义： ( 1 ) 对象集合x = x 。，x 。，x - ) 集合元素x ，表示对象，x 。( v 。，v 2 ，v 。) ，v j 表示对 象的属性。 ( 2 ) 聚类得到的簇集用c 表示，c = c l ，c 2 ，c k ，集合的元素c i ( i = l ，2 ，k ) 是各个簇，由于划分算法是互斥的，所以c 。uc 。u uc k = x ， c 。nc ：n nc w = 0 k 均值算法描述 输入：簇的数目k 和包含m 个对象的数据库 输出：k 个簇。使平方误差准则最小 l ： a s s i g ni n i t i a lv a l u ef o rm e a n 5 ： ，任意选择k 个对象作为初始的簇中心 2 ：r e p e a t 3 ： f o n j = 1t o m d o 4 ： a s s i g ne a c h 筠t ot h ec l u s t e rw h i c hh a st h ec l o s e s tm e a n ；根据簇中对象的平均值，将每个对象指派 到最近的簇 5 ：f o r i = lt o k d 0 6 ： i = x ic fl ；，更新簇的平均值，即计算每个对象簇中对象的平均值 x e c j 七 7 ： c o m p u t e s s e = x lx 一蜀1 2 i - im g 8 ：u n t i ls s eh a sc o n v e r g e d3 l o ； ， 计算目标函数s s e ，s s e 不再发生明显地变化 南京邮电大学硕士研究生学位论文第二章聚类技术概述 k 均值算法原理比较简单。首先，选择k 个初始质心，其中k 是用户指定的参数，即 所期望簇的个数( 行1 ) 。每个点指派到最近的质心( 邻近度最大) ，指派到一个质心的点 集为一个簇( 行3 、4 ) 。然后，根据指派到簇的点，更新每个簇的质心( 行5 、6 ) 。重复 指派和更新步骤，直到簇不发生变化，目标函数收敛( 行7 ) 。 对于邻近性函数和质心类型的某些组合，k 均值总是收敛到一个解；即k 均值到达一 种状态，其中所有点都不会从一个簇转移到另一个，因此质心不再改变。然而，由于大部 分收敛都发生在早期阶段，经过前面的多次迭代，后面是较少的簇边界上的点发生变动。 因此通常用较弱的条件替换算法迭代终止条件，比如将簇的点不变动的数目比例达到某一 阀值作为终止条件。 上面算法描述中的邻近度定义为两个对象的欧式距离。目标函数定义为误差的平方和 s s e ( s u mo f t h es q u a r e de r r o r ) 。k 均值算法步骤4 和步骤5 试图直接最小化s s e 。步骤4 通 过将点指派到最近的质心形成簇，最小化关于给定质心集的s s e ；而步骤4 重新计算质心， 进一步最小化s s e 。然而，k 均值的步骤3 和步骤4 只能确保找到关于s s e 的局部最优， 因为它们是对选定的质心和簇，而不是对所有可能的选择来优化s s e 。 2 时间复杂性和空间复杂性 k 均值的空间需求是适度的，因为只需要存放数据点和质心。具体，所需要的存储量 为p ( ( 耐幻而，其中2 7 1 是点数，刀是属性数。k 均值的时间需求也是适度的基本上 与数据点个数线性相关。具体，所需要的时间为o ( i x l x m x 刀) ，其中，是收敛所需要的 迭代次数。如前所述，通常很小，可以是有界的，因为大部分变化通常出现在前几次迭 代。因此，只要簇个数k 显著小于数据点个数历，则k 均值的计算时间与历线性相关，具 有可伸缩性。 2 4 2 层次聚类 层次聚类( h i e r a r c h i c a lc l u s t e f i n g ) 递归地对对象进行凝聚或者分裂，直到满足某一终 止条件为止。层次聚类的结果可以用一个谱系图或二分树表示，树中的每个结点都是一个 聚类。下层的聚类是上层聚类的嵌套，每一层结点构成一组划分。 根据谱系图生成的顺序，可以把层次聚类方法分为凝聚型( a g g l o m e r a t i v e ) 层次聚类 和分解型( d i v i s i v e ) 层次聚类两种。凝聚型层次聚类是一种自底向上的方法，将每一个对 象看作一个簇，把他们逐渐合并成越来越大的簇，直到所有的对象都在一个簇中，或者某 个终结条件被满足，绝大多数层次聚类方法属于这一类，只是在簇间相似度的定义上有所 l l 南京邮电大学硕士研究生学位论文第二章聚类技术概述 不同。分解型则与凝聚型的聚类过程相反，采用自顶向下的策略，首先将所有对象助于一 个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达到了某一终结条 件【2 2 1 。图2 2 是两种类型聚类过程的示意图。 0s t e p1s t e p2s t e p3s t 印4s t e p 凝聚型 4s t e p 3s t e p2s t e pls t e i )0s e p 分解型 图2 2层次聚类示意图 1 凝聚型层次聚类原理 算法描述 给定1 1 个对象的数据集合d ，凝聚型层次聚类得到d 的一系列划分：p n ，艮l ，p 1 其中p n 有1 1 个但成员簇，p 1 只有1 个包含所有对象的簇。 输入：包含n 个对象的数据库d ，终止条件簇的数目k 输出：k 个簇，达到终止条件规定的簇的数目 ( 1 ) 如果需要，计算邻近度矩阵： ( 2 ) l 比p e a t ( 3 ) 合并最接近的两个簇； ( 4 ) 更新邻近性矩阵，以反映新的簇与原来的簇之间的邻近性 ( 5 ) u n t i l 达到定义的簇的数目； 各种凝聚型层次聚类算法的基本步骤相同，差别在于簇间邻近度的定义不同。两个簇 间的邻近度计算方法主要有：( 单个聚类用历，另表示) ( 1 ) 最小距离( 或称单链) ：图2 3 ( a ) 所示邻近度以簇间的最小距离来度量。簇间的 最小距离定义为分别属于两个簇的最近对象间的距离，即刃( “，c j ) = m i n ( 以p ，彩) p c i 。q c j 1 2 南京邮电大学硕士研究生学位论文 第二苹聚荚技术概述 ( 2 )最大距离( 或称全链) ：图2 3 ( b ) 所示邻近度以簇间的最大距离来度量。簇间的 最大距离定义为分别属于两个簇的最远对象间的距离，即刃阪，c q = m a x ( d ( p ，d ) p e c , q c | ( 3 ) 簇平均距离( 或称平均链) ：图2 - 3 ( c ) 所示邻近度以簇平均距离来度量。簇间的 类平均距离定义为分别属于两个簇的对象间的平均距离，即刃( g ，0 = 二d ( p ，g ) 刀i 刀，p 。e c i q 。e c i ，7 尸l c ，l ，胪l c 一 ( 4 ) w a r d 氏方法：图2 - 3 ( d ) 所示邻近度以两个簇凝聚时导致的平方误差s s e 增量来 度量。若记历= ( p 一明，) ( p - m 。)