（计算机软件与理论专业论文）聚类算法及其在客户行为分析中的应用研究.pdf

北京邮电人学硕士研究生学位论文 聚类算法及其在客户行为分析中的应用研究 聚类算法及其在客户行为分析中的应用研究 摘要 聚类分析是数据挖掘中一项重要的技术。聚类的任务是把数据集 中的对象组成多个有意义的子类，在同一子类中的对象彼此相似，不 同子类中的对象不相似。本文重点研究了聚类分析中的两项关键技 术：聚类中心点初始化和孤立点检测，同时探讨了它们在客户行为分 析中的应用。 本文分析了聚类中心点初始化的必要性，以及现有的三类聚类中 心点初始化算法。在此基础上，融合了基于网格的聚类算法和基于密 度的聚类算法的基本思想，提出了基于动态网格生成技术的聚类中心 点初始化算法d g i c c 。该算法采用动态网格的生成技术，通过计算连 通密集区域的重心来生成初始的聚类中心。仿真实验表明，与现有的 算法相比，d g i c c 能更有效减少k - m e a n s 算法的迭代次数，获得较为 理想的聚类精度。同时随着数据集实例数、维度的增加，算法的时间 复杂度呈近似线性增加。 同时，在分析了现有的几类孤立点检测方法的基础上，针对其对 高维数据处理的不足，本文提出了基于转换聚类的孤立点检测算法 o d c c 。该算法将孤立点问题定位在转换空间中，通过考察距离分布差 异获取孤立点。实验结果表明，与现有的孤立点检测算法相比，新算 法在孤立点的寻找能力和时间复杂度方面均有较优表现。 北京邮电大学硕十研究生学位论文聚类算法及其在客户行为分析中的应用研究 本文最后探讨了聚类分析技术在客户行为分析中的应用，并给出 了一个聚类技术在电信账务数据上的分析和挖掘实例。该实例融合了 本文所提出的新算法：基于动态网格生成技术的聚类中心点初始化算 法d g i c c 和基于转换聚类的孤立点检测算法o d c c 。 关键词：聚类分析、聚类中心、孤立点检测、客户行为分析 i i 北京邮电人学硕士研究生学位论文聚类算法及其在客户行为分析中的应用研究 r e s e a r c ho nc l u s t e r i n ga l g o r i t 删m 巾i t sa p p l i c a t l 0 n s i nc u s t o m e rb e h a v i o r 趾忱l y si s a b s t r a c t c l u s t e r i n ga n a l y s i sh a sb e c o m eah i g h l ya c t i v et o p i ci nt h ed a t a m i n i n gr e s e a r c h i t st a s ki st h ep r o c e s so fg r o u p i n gt h ed a t ai n t oc l a s s e so r c l u s t e r ss ot h a tt h eo b j e c t sw i t h i nac l u s t e rh a v eh i g hs i m i l a r i t yi n c o m p a r i s o nt oo n ea n o t h e r , b u ta r ev e r yd i s s i m i l a rt oo b j e c t si no t h e r c l u s t e r s t h i st h e s i sf o c u s e so nt w ok e yt e c h n i q u e so fc l u s t e ra n a l y s i sa n d t h e i ra p p l i c a t i o n si nc u s t o m e rb e h a v i o ra n a l y s i s t h et w ok e yt e c h n i q u e s i n c l u d ei n i t i a l i z i n gc l u s t e rc e n t e r sa n do u t l i e rd e t e c t i o n t h et h e s i ss t u d i e st h er e q u i r e m e n t so fc l u s t e rc e n t e r si n i t i a l i z a t i o n a n dt h ec u r r e n t a l g o r i t h m s t h e n a d y n a m i cg r i dg e n e r a t i o n t e c h n o l o g y - b a s e da l g o r i t h mf o ri n i t i a l i z i n gc l u s t e rc e n t e r si sp r o p o s e d ， w h i c hi n t e g r a t eb o t hg i r d - b a s e da n dd 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 m t h i sm e t h o du s e st h et e c h n o l o g yo fd y n a s t y g r i dg e n e r a t i o na n dg e n e r a t e s t h ei n i t i a lc l u s t e rc e n t e rb yc a l c u l a t i n gt h ec e n t e ro fg r a v i t yo fi n t e n s i v e r e g i o n a lc o n n e c t i v i t y t h es i m u l a t i o nr e s u l t ss h o wt h a t ，c o m p a r e dw i t h i i ! 北京邮电大学硕十研究生学位论文 聚类算法及其在客户行为分析中的应用研究 t h ee x i s t i n ga l g o r i t h m ，d g i c ci sa b l et oe f f e c t i v e l yd e c r e a s et h en u m b e r o fk m e a n si t e r a t i o n sa n di m p r o v ec l u s t e r i n gp r e c i s i o n m o r e o v e r , t h e r u n n i n gt i m eo fd g i c c i sn e a r l ya p p r o x i m a t e l yl i n e a rw i t hr e s p e c tt ot h e i n c r e a s ei nt h en u m b e ro fi n s t a n c e sa n dd i m e n s i o n s a tt h es a m et i m e ，b a s e do nt h ea n a l y s i so ft h ee x i s t i n go u t l i e r d e t e c t i o na l g o r i t h ma n dt h es h o r t f a l lo fd e a l i n gw i t hh i g h - d i m e n s i o n a l d a t a , a no u t l i e rd e t e c t i o na l g o r i t h mb a s e do nc o n v e r t i n gc l u s t e r i s p r o p o s e d t h i s m e t h o dr e d e f i n e st h e p r o b l e mb yc l u s t e r i n g i nt h e d i s t r i b u t i o nd i f f e r e n c es p a c er a t h e rt h a nt h eo r i g i n a lf e a t u r es p a c e t h e s i m u l a t i o nr e s u l t ss h o wt h a tt h en e wa l g o r i t h mh a sb e t t e rr e s u l t si n f i n d i n go u t l i e r sa n dt h er u n n i n gt i m et h a nt h ee x i s t i n go u t l i e rd e t e c t i o n a l g o r i t h m s ， b a s e do nt h en e wa l g o r i t h m si nt h i st h e s i s ，t h ep a p e rf o c u s e so nt h e a p p l i c a t i o n s o fc l u s t e r a n a l y s i s i nc u s t o m e rb e h a v i o ra n a l y s i sa n d p r e s e n t sac l u s t e r i n gt e c h n o l o g yi nt h et e l e c o m m u n i c a t i o n sa c c o u n t sd a t a a n a l y s i sa n dm i n i n g k e yw o r d s ：d a t am i n i n g ，c l u s t e ra n a l y s i s ，c l u s t e rc e n t e r ，o u t l i e r d e t e c t i o n ，c u s t o m e rb e h a v i o ra n a l y s i s 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：至趣煎日期：呈里里星：三：堑 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 本学位论文不属于保密范围，适用本授权书。 本人签名：至亟董： 日期： 圣塑：墨：兰星 导师签名：，吁们朋 北京邮电大学硕士研究生学位论文聚类算法及其在客户行为分析中的应用研究 第一章绪论 1 1 课题研究的背景和意义 在人类从工业社会向信息社会演进的今天，知识正在成为创新的核心，知识 创新成为知识经济发展的最主要的动力源泉。从数据到信息，从信息到知识已经 成为耳熟能详的格言。数据是事务、概念或指令的一种形式化的表示形式，以适 用于人工或自然方式进行通信、解释或处理；信息是根据表示数据所用的约定， 赋予数据的意义；而知识是人类在实践的基础上产生的又经过实践检验的对客观 实际的可靠反应。信息革命产生了大量数据，为了获得数据属性的内在关系和隐 含的信息( 即重要的知识) 一种新的数据分析技术数据库中的知识发现 ( 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 ) 从八十年代末逐渐发展起来。在 1 9 8 9 年8 月美国底特律召开的第十一届人工智能联合会议的专题讨论会上首次 出现了k d d 这个术语，f a y y a d 指出“k d d 是从数据集中识别出有效的、新颖 的、潜在有用的，以及最终可理解的模式的非平凡过程” 1 1 。 k d d 包含很多内容，其核心部分就是数据挖掘( d a t am i n i n g ) 。k d d 被认 为是从数据中发现有用知识的整个过程，知识即意味着数据元素之间的关系和模 式。数据挖掘被认为是k d d 过程中的一个特定步骤，它应用具体算法从数据中 提取模式和知谢z 一。 聚类是数据挖掘中的一项重要技术，是分析数据并从中发现有用信息的一种 有效手段【3 】。基于“物以类聚的朴素思想，它将数据对象分组成为若干个类或 簇，使得在同一个类中的对象之间具有较高的相似度，而不同的类中对象差别很 大。通过聚类，人们能够认识密集和稀疏的区域，发现全局的分布模式以及数据 属性之间有趣的相互关系。聚类分析在客户分类、基因识别、文本分类、空间数 据处理、卫星照片分析、医疗图像自动检测等领域有着广泛的应用，而其本身的 研究也是一个蓬勃发展的领域。数据挖掘、统计学、机器学习、空间数据库技术、 生物学和市场学的发展推动着聚类分析研究的进展，使它已成为数据挖掘研究中 的一个热点。与其它数据挖掘方法不同，在进行聚类分析前用户一般都不知道数 据集的特征。因此，从某种角度看，聚类分析是一种无监督的学习过程，是基于 观察的学习而不是基于实例的学习。 作为数据挖掘中的一个模块，聚类分析可以作为一个独立的工具来获取数据 分布的情况，观察每个类的特点，集中对特定的某些类做进一步分析。如在商务 第1 页共4 6 页 北京邮电大学硕上研究生学位论文聚类算法及其在客户行为分析中的应用研究 上，聚类分析可以帮助市场分析人员从客户基本库中发现不同的客户群，并且用 购买模式来刻画不同的客户群的特征。聚类分析也可以作为数据挖掘中其他算法 ( 如特征和分类等) 的预处理步骤，这些算法再在生成的类上进行处理。此外它 还可以完成孤立点挖掘。许多数据挖掘算法试图使孤立点影响最小化，或者排除 它们。然而孤立点本身可能是非常有用的，如在欺诈探测中，孤立点有可能预示 着欺诈行为。迄今为止，人们提出了大量的聚类算法，算法的选取取决于数据的 类型、聚类的目的和应用。如果聚类分析用于描述或探索的工具，可以对同样的 数据尝试多种算法，以便发现数据可能隐含的规律与结果。 1 2 本文研究的主要内容 1 2 1 聚类分析 本文将在第二章详细介绍关于聚类分析的相关概念、主要算法、研究现状以 及聚类的应用。 1 2 2 聚类中心初始化方法 作为一种典型的分割聚类算法，k m e a n s 算法在处理大数据集时具有相对的 可伸缩性和高效性，是一种被广泛应用的无监督学习方法。k m e a n s 算法首先随 机选取k 个对象，对剩余的每个对象，根据其与各个簇中心的距离，将它赋给最 近的簇，然后重新计算每个簇的平均值。不断的重复这个过程，直到准则函数收 敛为止。m a c q u e 饥运用随机过程的方法给出了k m e a n s 算法的收敛性证明，因 此它是理论上可靠、应用上高效的算法。然而，包括k m e a n s 算法在内的许多 基于局部最优的聚类算法有一个共同的缺点，它们往往对初始聚类中心点的选取 非常敏感。对于给定的聚类块数k ，不同的初始化聚类中心很可能会导致截然不 同的聚类结果。因此，选取合适的初始化聚类中心，不仅能够提高此类算法的聚 类精度，而且可以减少算法达到收敛所需要的迭代次数，降低算法的运行时间。 本文将在第三章介绍聚类中心初始化的背景，然后引出一种新的聚类中心初 始化算法：基于动态网格生成技术的聚类中心初始化算法d g i c c 。 1 2 3 孤立点检测 孤立点检测是一项重要的数据挖掘活动，它用来发现数据集中明显与其它数 据不同的对象。对孤立点的挖掘在电信及信用卡的欺诈、信贷信用、医药研究、 天气预测、财务、市场营销及客户分段等领域中有大量的应用。然而现有的孤立 点检测算法往往只适用于较低维度的数据。当数据维度增加时，孤立点检测算法 第2 页共4 6 页 北京邮电大学硕士研究生学位论文聚类算法及其在客户行为分析中的应用研究 的性能会迅速下降。更进一步，由于高维数据空间的稀疏性以及近邻特性，按照 以前对孤立点的定义，每个数据点都几乎是孤立点，这样孤立点的概念就失去意 义。另一方面，现有的孤立点检测算法对背景知识的依赖较为严重，它们通常都 具有对输入参数敏感的特点，这极大程度上限制了算法在真实世界中的应用。 本文将在第四章提出一种新的孤立点检测算法：基于转换聚类的孤立点检测 算法o d c c 。 1 2 4 聚类在客户行为分析中的应用 作为一种数据挖掘技术，聚类分析在客户关系管理( c i 洲) 方面有着广泛的应 用。客户行为分析是客户关系管理的研究热点之一。广义上，客户关系管理是指 对企业和客户交互活动进行管理的过程，客户关系管理使这种交互过程自动化。 按照其研究内容可划分为两个分支：整体行为分析和群体行为分析整体行为分 析是指发现所有客户的行为规律，但这样还不够，对于企业客户，群体行为分析 是指发现不同群体客户的行为规律通过深入了解客户的行为方式，营销专家可 以及时地制定相应的经营决策。 然而，对大规模高维数据进行分析具有相当的复杂性。随着市场竞争的日益 激烈以及数据收集技术的快速发展，基于市场调查和人口统计学特征的市场细分 方法已经不能满足营销策划的需要。基于聚类分析的市场细分方法正是在这种背 景下产生。 本文将在第五章介绍一个聚类技术在电信账务数据上的分析和挖掘实例。 1 3 本文组织结构 本论文分为六章，各章内容如下： 第一章：绪论 本章给出了课题背景、研究内容及论文结构。 第二章：聚类分析算法综述 本章阐述了聚类分析的基本概念、主要算法、研究现状以及聚类应用。 第三章：基于动态网格生成技术的聚类中心初始化算法 本章介绍了聚类中心初始化的背景，并对基于动态网格生成技术的聚类中心 初始化算法d g i c c 进行了详细的描述。 第四章：基于转换聚类的孤立点检测算法 本章提出一种新的孤立点检测算法：基于转换聚类的孤立点检测算法 o d c c 。 第3 页共4 6 页 北京邮电人学硕十研究生学位论文聚类算法及其在客户行为分析中的应用研究 第五章：聚类技术在客户行为分析中的应用 本章介绍了一个聚类技术在电信账务数据上的分析和挖掘实例。 第六章：结束语 本章总结全文，并提出展望。 第4 页共4 6 页 北京邮电大学硕士研究生学位论文 聚类算法及其在客户行为分析中的应用研究 第二章聚类分析算法综述 在数据挖掘技术中，聚类分析是其中一种基本的模式。聚类( c l u s t e r i n g ) 就是 将数据对象分组成为多个类或簇，在同一个簇中对象之间具有较高的相似度，而 不同簇中的对象之间差别较大。相似或不相似的度量是基于数据对象描述属性的 取值来确定的，通常就是利用各对象间的距离来进行描述。聚类算法经过多年来 的研究发展，被分成了5 个大类：划分方法、层次方法、基于密度的方法、基于 网格的方法和基于模型的方法。一些聚类算法结合了多种聚类方法的思想，所以 有时将某个给定的算法划分为属于某种聚类方法是很困难的。 2 1 聚类分析的基本概念 2 1 1 聚类定义 聚类可以定义如下 4 j ：在数据空间彳中，数据集x 由许多数据点( 或数据对 象) 组成，数据点= ( j n ，妇) a ，而的每个属性( 或特征、或维度) 嘞既可以 是数值型的，也可以是枚举型的。数据集x 相当于是一个n x d 矩阵。假设数据 集x 中有个个对象( f = l ，n ) 。聚类的最终目的是把数据集x 划分为k 个 分割g ( 聊= 1 ，k ) ，也可能有些对象不属于任何一个分割，这些就是噪声。所 有这些分割与噪声的并集就是数据集x 并且这些分割之间没有交集，即： x = c - u u c , u c 。，q n q = 矽( f ) ( 2 1 ) 这些分割q 就是聚类。 2 1 2 聚类有效性的评价 聚类有效性的评价是指对聚类效果的度量，通常需要结合具体的应用场景， 但是仍然存在一些客观的评价聚类效果的标准。聚类的质量受到如下因素的影 响：初始值的选择、聚类数量的选择以及聚类方法的选择等【2 1 。下面介绍三种常 用的评价标准： ( 1 ) 分离系数 刑囊) 2 吉善善( 2 q - 2 假设q 为所有聚类结果，则k 的最优选择由下式给出： 堡坚 巴坚，( 【，后) ) ，k = 2 ，3 ，n l ( 2 3 ) k v 一、l v 一 、。 第5 页共4 6 页 北京邮电人学硕上研究生学位论文聚类算法及其在客户行为分析中的应用研究 分离系数描述了所有输入样本相对于簇心的接近程度。如果每个样本仅属于 一类，且此时”廿较大，则数据的不确定性较小。 ( 2 ) 分离熵 1 1k“ h ( u ，七) = 一 “口l o g ( u | ) ( 2 - 4 ) ”i = l = l 假设q 为所有聚类结果，则k 的最优选择由下式给出： 磐坚 m 坚日( u ，尼) ) ，k = 2 ，3 ，r 一1 ( 2 5 ) l ，- j 、k ，j 、 7 ko 若所有的“。接近0 或l ，则熵指较小，所给出的聚类结果就好；反之，若”。 接近于0 5 ，则聚类模糊程度就高，熵就越大，聚类结果就差。 ( 3 ) 紧致与分离性效果函数 三“抽飞1 2 s ( u ，七) = 生业_ 厂 ( 2 6 ) m h l n l x , 一c j | j ， 假设q 为所有聚类结果，则k 的最优选择由下式给出： 里墼( 望骛s ( ，七) ) ，k = 2 ，3 ，t 一i ( 2 7 ) l _ 、l p j 、 kq s ( u ，k ) 是输入样本与它们相应的聚类中心距离的平均值与聚类中心最小间 距的比值。一个好的聚类方案应使得聚类中心的间距尽可能大，而样本与其聚类 中心的间距尽可能小。由于紧致与分离性函数综合考虑了紧致性与分离性这两个 方面，因此s ( u ，k ) 函数的性能最好。 2 1 3 对聚类分析算法的典型要求 聚类分析是一个具有很强挑战性的领域，它的一些潜在的应用对分析算法提 出了各自特殊的要求，数据挖掘对聚类算法的典型要求如下【3 】： ( 1 )可伸缩性：许多聚类算法对于小于2 0 0 个数据对象的较小数据集能够 很好地进行聚类，但是，一个大型数据集中可能包含有几百万、几千万乃至更多 的对象。虽然通过抽样可以减少要处理的数据量，但是抽样会对聚类的结果带来 影响甚至会产生错误的结果。因此，我们需要具有高度可伸缩性的聚类算法。 ( 2 ) 处理混合型数据的能力：许多算法是设计来对数值型数据进行聚类的。 然而，在许多应用中待聚类的数据可能是二值型、枚举型、序数型，或者这些数 据类型的混合。聚类算法需要具有处理这些数据类型的能力。 ( 3 ) 发现任意形状的聚类的能力：很多聚类算法采用基于欧几里德距离 或曼哈坦距离的相似性度量方法来确定聚类，而这类算法发现的聚类通常是球状 第6 页共4 6 页 北京邮电大学硕上研究生学位论文 聚类算法及其在客户行为分析中的应用研究 的、大小和密度相近的。然而，聚类可能是各种形状的，如线形、坏形、凹形以 及其他各种复杂不规则形状。这就要求聚类算法能够发现任意形状的聚类。 ( 4 ) 输入参数对领域知识的弱依赖性：许多聚类算法要求用户输入一定的 参数，如需要发现的聚类数、结果的支持度及置信度等。而聚类结果通常对这些 输入的参数非常敏感。但另一方面，这些参数往往很难确定，尤其对于高维数据 集更是如此。这不仅对用户带来了难题，而且还使聚类的结果难以控制。一个好 的聚类算法应该对此给出一个好的解决方法。 ( 5 ) 处理噪音数据的能力：现实世界的很多数据中都包含一些异常数据或 错误数据，有些聚类算法对这些数据非常敏感，并可能会产生错误的聚类结果。 ( 6 ) 对输入顺序不敏感：有些聚类算法对数据的输入顺序非常敏感，例如， 对于同一个数据集，用不同的顺序输入到某个算法中，就可能会产生完全不同的 聚类结果，这是我们不希望的。 ( 7 ) 对高维数据的处理能力：数据库或数据仓库中的数据可以有几十乃至 成百上千个维度或属性。许多聚类算法只擅长处理低维数据，如二维或三维数据。 在高维数据空间中，数据可能非常稀疏并且高度扭曲。因此，高维空间中数据的 聚类是一个很大的挑战。 ( 8 ) 增加约束条件后的聚类分析能力：在现实世界中的一些应用中，可能 需要在一些约束条件下来进行聚类分析。例如要在一个城市中为给定数目的自动 提款机选择安放位置，可以对住宅区进行聚类，同时考虑城市的河流、公路网以 及每个地区的客户要求等情况。我们希望聚类算法可以在考虑这些约束条件的情 况下，仍有较好的表现。 ( 9 ) 结果的可解释性和可用性：用户希望聚类结果是可解释的，可理解的 和可用的。也就是说，聚类可能需要和特定的语义解释和应用相联系。应用目标 如何影响聚类方法的选择也是一个重要的研究课题。 2 2 主要的聚类算法 现有的主要聚类算法可以大致分为以下几种【3 1 ：划分方法、层次方法、基于密 度的方法、基于网格的方法以及基于模型的方法。下面对这些主要的聚类算法一 一进行介绍，并进行简单的分析和比较。 2 2 1 划分方法 对于一个给定的n 个数据对象的数据集，采用目标函数最小化的策略，通过 把数据分成k 个组，每个组为一个簇，这就是划分方法。可以看出，这种聚类方 第7 页共4 6 页 北京邮电大学硕上研究生学位论文聚类算法及其在客户行为分析中的应用研究 法同时满足以下两个条件：( 1 ) 每个组至少包含一个数据对象：( 2 ) 每个数据对象必 须属于且仅属于一个组。当然，在有些情况下，如模糊聚类，条件( 2 ) 可以放宽 要求。最著名与最常用的划分聚类算法是k - 平均( k m e a n s ) 【5 朋算法和k 中心点 ( k - m e d o i d s ) 算法，其他划分方法大都是这两种方法的变种。 2 2 2 层次方法 层次聚类算法按数据分层建立簇，形成一棵以簇为节点的树。如果按自底向 上进行层次分解，则称为凝聚的( a g g l o m e r a t i v e ) 层次聚类；而按自顶向下的进行 层次分解，则称为分裂法( d i v i s i v e ) 层次聚类【。丌。 凝聚的层次聚类首先将每个对象作为一个簇，然后逐渐合并这些簇形成较大 的簇，直到所有的对象都在同一个簇中，或者满足某个终止条件。分裂的层次聚 类与之相反，它首先将所有的对象置于一个簇中，然后逐渐划分为越来越小的簇， 直到每个对象自成一簇，或者达到了某个终止条件，例如达到了某个希望的簇数 目，或两个最近的簇之间的距离超过了某个m 值。 层次方法可以在不同粒度水平上对数据进行探测，而且容易实现相似度量或 距离度量。但是，单纯的层次聚类算法的终止条件含糊，而且执行合并或分裂簇 的操作不可修正，这很可能导致聚类结果质量很低。另外，由于需要检查和估算 大量的对象或簇才能决定簇的合并或分裂，所以这种方法的可扩展性较差。因此， 通常在解决实际聚类问题时要把层次方法与其他方法结合起来。层次方法和其他 聚类方法的有效结合可以形成多阶段聚类，能够改善聚类质量。这类方法包括 b i r c h 8 1 ，c u r e 9 1 ，r o c k 10 1 ，c h a m e l e o n 11 】算法等。 2 2 3 基于密度的方法 很多算法中都使用距离来描述数据之间的相似性，但是对于非球状数据集， 只用距离来描述是不够的。对于这种情况，要用密度来取代相似性，这就是基于 密度的聚类算法。基于密度的算法从数据对象的分布密度出发，把密度聚类分析 算法及应用足够大的区域连接起来，从而可以发现任意形状的簇。此类算法除了 可以发现任意形状的簇，还能够有效去除噪声。常见的基于密度的聚类算法有 d b s c a n 1 2 1 ，o p t i c s 13 1 ，d e n c l u e 1 4 】等。 2 2 4 基于网格的方法 基于网格的聚类算法，把空间量化为有限个单元，然后对量化后的空间进行 聚类。此类算法具有很快的处理速度，缺点是只能发现边界是水平或垂直的聚类， 而不能检测到斜边界。基于网格的聚类算法的时间复杂度一般由网格单元的数目 第8 页共4 6 页 北京邮电大学硕十研究生学位论文聚类算法及其在客户行为分析中的应用研究 决定，而与数据集的大小无关。此外，聚类的精度取决于网格单元的大小。此类 算法不适用于高维情况，因为网格单元的数目随着维数的增加而成指数增长。 所有基于网格的聚类算法都存在下列问题：一是如何选择合适的单元大小和 数目，单元数目太少时，精度就会很低，而单元数目太多时算法的复杂度就会变 大；二是如何对每个单元中对象的信息进行汇总。 有代表性的基于网格的聚类算法包括：s t 玳d 15 1 ，w a v e c l u s t e r t l 6 1 c l i q u e 1 7 】 等。 2 2 5 基于模型的方法 基于模型的聚类方法建立在数据符合潜在的概率分布这一假设基础之上。这 类方法试图优化给定数据与某些数学模型之间的拟合。基于模型的聚类方法主要 有e m t l 引、概念聚类方法【1 9 】和神经网络方法【冽等。 2 2 6 孤立点分析 孤立点是数据集中不符合一般模型的那些对象，即和其它的数据有着不同的 性质。它可能是度量或执行错误所导致的，也可能是固有数据变异的结果。例如， 一个人的年龄为负值，这是一个由于执行错误而产生的孤立点；一个公司的首席 执行官的工资远远高于其他的员工，而成为一个孤立点，这是一个固有的数据变 异的结果。 孤立点的研究非常重要，主要是由于：( 1 ) 它对数据分析的结果有很大的影 响；( 2 ) 虽然它通常是测量、记录错误，但有些可能代表应用领域中感兴趣的、 有意义的知识；( 3 ) 确定孤立点经常导致发现新的知识。 孤立点检测有着广泛的应用领域。在信用卡欺诈探测中发现的孤立点可能预 示着欺诈行为，而及时发现这种信用卡欺诈行为对商业银行而言相当重要，可以 避免重要的经济损失。在市场分析中，可用于确定极低或极高收入的客户的消费 行为。在医疗分析中，可用于对多种治疗方式的不同寻常的反映等。 孤立点检测一般包括两个步骤：第一步是给出孤立点的定义，也就是说，在 数据空间中界定具有什么性质或者满足什么条件的数据点为孤立点；第二步是根 据第一步中所定义的孤立点定义在数据空间中寻找孤立点。在孤立点检测算法 中，孤立点的定义是非常重要的，h a w k i n s 2 1 】给出的描述几乎成为被广泛接受的 定义：“孤立点是在数据集中偏离大部分数据的数据，使人怀疑这些数据的偏离 并非由随机因数产生，而是产生于完全不同的机制 现有的孤立点算法根据孤立点定义的角度不同，分为五种不同的类型：基于 统计的算法、基于深度的算法、基于偏差的算法、基于距离的算法和基于密度的 第9 页共4 6 页 北京邮电大学硕士研究生学位论文聚类算法及其在客户行为分析中的应用研究 算法。 根据应用场景的不同，不同的孤立点检测算法能够发挥不同的作用。最早出 现的孤立点检测算法是基于统计的方法，它给数据空间中的数据分布假设一种类 型，例如为高斯分布。不满足分布条件的点被认为是孤立点。这种算法在实际应 用中出现了问题，这是因为，真实世界中的数据集合通常并不服从简单的特定的 分布类型。基于深度的算法是根据数据的概念层次的不同，给数据集合中的点划 分不同的层次，在较深层次中的点具有较小的孤立点可能性，而在较浅层次中的 点具有较大的孤立点可能性。基于偏差的算法的基本思路如下：通过扫描数据集， 当发现一个数据点明显不同于前面的序列，这样的点就被认为是孤立点数据。这 类算法的复杂度与数据集大小呈线性关系，获得了良好的计算性能。但是序列异 常在概念上有很多缺陷，遗漏了不少真正的孤立点。基于距离的算法根据某个距 离函数计算数据对象之间的距离，那些与所有其他的数据对象相比有更高距离的 数据对象即为孤立点。这些算法目的是解决在早期算法中所遇到的扩展性问题。 但是基于距离的方法存在着时间复杂度高，距离参数以及孤立点之间的强弱难以 确定的问题。基于密度的孤立点算法关注一个对象周围的密度( 最近邻居数) 。具 有高密度邻域的数据对象不是孤立点，而低密度邻域的数据对象可能就是孤立 点。在决定孤立点方面，基于密度的孤立点挖掘技术更注重对象的局部性。然而 该方法通常只适用于较低维度的数据。 2 2 6 1 基于统计的算法 对给定的数据集合假定了一个分布或概率模型，然后根据模型采用不一致性 检验来确定孤立点，该检验要求知道数据集参数( 数据分布等) 、分布参数和预期 的孤立点数目【2 2 1 。这种方法必须事先知道数据的分布特征，但在多情况下，数 据分布可能是未知的，这就限制了它的应用范围。 2 2 6 2 基于深度的算法 r u t s 和r o u s s e 宅u w 提出了基于深度的算法【2 3 1 。根据算法，每一个数据被映 射为k 维数据空间上的一个点，并且每个点都被赋予一个特定意义的“深度”。 根据不同的深度，数据被划分为不同层次，孤立点往往存在于较“浅”的层次中， 而存在于较“深 层次中的可能性较小瞰，2 5 1 。 2 2 6 3基于偏差的算法 a r g r a w a l 和r a g a r a n 在1 9 9 6 年提出过“序列异常 ( s e q u e n t i a le x p c e p t i o n ) 的概念【2 6 1 。他们采用这一机制，通过扫描数据集，当发现一个数据点明显不同 第l o 页共4 6 页 北京邮电大学硕士研究生学位论文聚类算法及其在客户行为分析中的应用研究 于前面的序列时，就将该点标定为孤立点。这个算法复杂度与数据集大小呈线性 关系，获得了很好的性能。但是序列异常在概念上有缺陷，使得算法常常遗漏许 多真正的孤立点。 2 2 6 4 基于距离的算法 基于距离孤立点挖掘算法【2 7 。2 9 1 根据某个距离函数计算数据对象之间的距离。 孤立点是那些与所有其他的数据对象相比有更高距离的数据对象。这些算法目的 是解决在早期算法中所遇到的扩展性问题。探测偏离异常的技术称为异常检测， 它依赖于数据集内部的相异性。这个算法不需要像在许多聚类算法中使用的任何 距离函数，但需要一个提供数据集中的某个对象而产生数据集相异性增加程度的 函数。然而，奇异( e x a c te x c e p t i o n ) 实际上与由k n o r r 提出的基于距离方法不一样 奇异算法把这样的对象集作为孤立点，即如果把这些对象去掉使集合中的其它对 象更同态。而基于距离算法把孤立点定义为比所有别的数据点有更高距离的数据 对象是孤立点。 孤立点是那些相对于所有其它的对象有更高距离的对象。如果数据集s 中至 少有p 部分对象与对象0 的距离大于d ，则对象o 是一个带参数p 和d 的基于距 离的孤立点，即d b ( p ，d ) 。换句话说，我们可以将基于距离的孤立点看作是那 些没有“足够多邻居的对象。这罩的邻居是基于与给定对象的距离来定义的。 基于距离的孤立点检测方法可以在未知数据分布状态下对多维数据进行分 析，避免了过多的计算，而大量的计算正是使观察到的分布拟合某个标准分布， 及选择不一致性检验所需要的。 目前己经提出了若干个高效的基于距离的孤立点的算法，主要有：基于索引 的算法、嵌套一循环算法、基于单元的算法等。 ( 1 ) 基于索引的算法：给定一个数据集，基于索引的算法采用多维索引结构 ( 如r 树或k - d 树) 来查找每个对象。在半径d 范围内的邻居。设m 是一个孤立点 的d 邻域内允许包含的点最大数目，如果发现某个对象o 的d 邻域内有第m + 1 个邻居，则认为0 不是孤立点。这个算法在最坏情况下的复杂度为o ( g n 2 ) ，这 里k 是维数，n 是数据集合中对象的数目。当数据集的维数增加时，基于索引的 算法具有良好的扩展性。但是，复杂度估算只考虑了搜索时间，即使建造索引的 任务本身就是计算密集的。 ( 2 ) 嵌套循环算法：与基于索引的算法相比，嵌套循环算法具有相同的计 算复杂度，但不需要构建索引结构，试图最小化f o 的次数。它把内存的缓冲空 间分为两半，把数据集合分为若干个逻辑块。通过精心选择逻辑块装入缓冲区域 的顺序，f o 效率能够改善。 第1 1 页共4 6 页 北京邮电人学硕士研究生学位论文聚类算法及其在客户行为分析中的应用研究 ( 3 ) 基于单元的算法：与前两种方法相比，基于单元的算法的时间复杂度较 小。该方法把k 维数据空间划分为边长为d 2 x f k 的单元，每个单元有两层围绕 着，第一层的厚度为一个单元，第二层的厚度为2 七一l 。该方法统计单元中对 象的数目、单元与第一层中对象的数目之和、单元与两个层次中对象的数目之和 等三个统计数据。我们把他们分别记为cc o u n t 、clc o u n t 、c2c o u n t 。设m 是 一个孤立点的d 邻域内允许包含的点最大数目。某个单元中的对象0 被认为是孤 立点的充要条件是cc o u n t 小于等于m 。如果某个单元中。clc o u n t 大于m ， 那么，该单元中的所有点都不是孤立点。如果某个单元中c2c o u n t 小于等于m ， 那么，该单元中的所有点都是孤立点。如果某个单元中c2c o u n t 大于m ，那么， 该单元中可能存在孤立点，为了寻找这些孤立点，需要对每个对象逐个进行处理。 基于距离的孤立点探测要求用户设置参数p 和d ，而寻找这些参数的合适设 置可能会涉及多次试探和错误。 基于距离的方法存在三个主要缺陷。嵌套一循环算法和基于索引的算法都有 d ( 埘2 ) 时间复杂度，与维数k 是线性关系，与数据大小n 是平方关系。当数据 集很大时，使得它们很不适用。数据挖掘应用的数据集规模异常大，这两个算法 很难测量。其次，算法为了挖掘孤立点它需要用户提供最小的可接受距离d ，根 据这个距离d 才能说明这个对象是不是孤立点，这个距离d 很难正确地猜到。 为了挖掘出合适的孤立点，指定j 下确的d 非常重要，因为如果d 选择太小， 几乎所有对象都是孤立点：如果d 选择太大，没有一个数据对象是孤立点。最后 一个问题是基于距离的孤立点挖掘方法对挖掘出的孤立点不区分强孤立点和弱 孤立点，即不排列大小，要区分孤立点之间的强弱很困难。 2 2 6 5 基于密度的算法 基于密度的孤立点算法【3 0 。4 】关注一个对象周围的密度( 最近邻居数) 。具有高 密度邻域的数据对象不是孤立点，然而，低密度邻域的数据对象可能就是孤立点。 在决定孤立点方面，基于密度的孤立点挖掘技术更注重对象的局部性。现有算法 计算局部孤立因子( l o f ) 并把那些具有很高l o f 值的数据对象作为孤立点。也就 是说，l o f 表示了一个对象对于它的邻居来说孤立的程度。 b r e u n i n g 等认为成为孤立点并不是像基于距离的孤立点挖掘概念那样仅仅 是一个二分属性，即：数据对象不能仅被分成是孤立点或者不是孤立点，而是每 个对象有某个孤立度。他们认为，在许多情况下，对每个对象赋予孤立点的度更 正确。这个度就是局部孤立因子( l o f l 因为这个度依赖于该对象关于它周围邻居 的遥远程度。孤立点就是有高l o f 值的对象。为了挖掘局部孤立点提出的算法 称为局部孤立因子( l o f ) 。l o f 能够探测所有形式的孤立点，包括那些不能被早 第1 2 页共4 6 页 北京邮电大学硕士研究生学位论文聚类算法及其在客户行为分析中的应用研究 期( 基于距离的，基于分布的和基于偏离的) 算法探测到的孤立点。 在挖掘孤立点方面，早期算法的问题是对整个数据集带有一个“全局观点， 因此产生的孤立点也是“全局”孤立点。然而，在多维数据集中数据结构一般都 很复杂，往往有一些数据对于它们的邻居来说可能是孤立点，但是在整个数据集 中将不是孤立点。任何一个“全局的 孤立点探测算法不能识别出这些孤立点。 用下面的图2 1 也许能更好的解释这个问题。 图2 1 一个二维数据集 从图2 1 上可以看出，c 1 和c ，是两个类，q 和d ，是类外面的两个数据对 象。根据h a w k i n s 的定义( “孤立点是在数据集中偏离大部分数据的数据，使人 怀疑这些数据的偏离并非由随机因数产生，而是产生于完全不同的机制 ) ，对 象q 和q 是孤立点，然而在c l ，c 中的对象就不是孤立点。l o f 也将对象a ， d 2 标记为孤立点，但是基于距离的孤立点方法，只有d l 是合理的孤立点，由于d 和它最近邻居的距离将小于类g 中的一些距离。所以，l o f 能识别所有像上图 所示，那些不能被基于距离的孤立点算法识别的孤立点。基于距离的算法不能识 别像上图所示的孤立点主要是由于基于距离的孤立点概念的定义所致而不是某 个基于距离算法本身的效果。 2 3 聚类分析研究现状 目前，聚类分析技术正在蓬勃发展，它对数据挖掘、统计学、机器学习、市 场营销等领域都做出了贡献并已经成为数据挖掘研究领域中一个非常活跃的研 究课题。聚类分析将大量数据划分为性质相似的子类，这样便于了解数据的分布 情况，从而从中提取有用的知识。聚类分析作为数据挖掘的重要组成部分，现已 广泛的应用于各个领域。目前的聚类算法很多，但不同的算法有各自的特点：基 第1 3 页共4 6 页 北京邮电大学硕士研究生学位论文聚类算法及其在客户行为分析中的应用研究 于划分的算法适用于类数固定、偏好球形的聚类；基于层次的算法能得到不同粒 度上的多层次聚类结构；基于密度的算法可以在含“噪声 数据库中发现形状任 意以及不同规模的聚类；基于网格的聚类算法处理速度快，处理时间独立于数据 对象的数目；基于模型的方法则适用于数据分布已知的聚类。因此，在实际应用 中可以根据不同的应用、数据类型和目的，选择使用最好的聚类方法。同时，新 数据形式的产生和广泛应用对传统的聚类算法提出了挑战，聚类分析将随着应用 的需求及新技术的出现而得到很大的