数据挖掘中的聚类算法综述

・10・计算机应用研究2007年

数据挖掘中的聚类算法综述

贺　玲, 吴玲达, 蔡益朝

3

(国防科学技术大学信息系统与管理学院, 湖南长沙410073)

摘　要:聚类是数据挖掘中用来发现数据分布和隐含模式的一项重要技术。全面总结了数据挖掘中聚类算法的研究现状, 分析比较了它们的性能差异和各自存在的优点及问题, 并结合多媒体领域的应用需求指出了其今后的发展趋势。

关键词:数据挖掘; 聚类; 聚类算法

中图法分类号:TP391　　　文献标识码:A 　　　文章编号:100123695(2007) 0120010204

Survey of Clustering A s HE L ing, (College of Infor m ation Syste m N U Technology, Changsha Hunan 410073, China )

Abstract:in M ining (DM ) f or the discovery of data distributi on and latent data

pattern . r survey of current clustering algorith m s in DM at first, then it makes a comparis on a mong the m, the merits existing in the m, and identifies the p r oblem s t o be s olved and the ne w directi ons in the fu 2ture according t o the app licati on require ments in multi m edia domain . Key works:Data M ining; Clustering; Clustering A lgorith m

聚合聚类:Single 2L ink, Comp lete 2L ink, Average 2L ink 分解聚类

基于密度的聚类基于网格的聚类

基于图论的聚类

基于平方误差的迭代重分配聚类:概率聚类、最近邻

聚类、K 2medoids 、K 2means

人工神经网络方法

:模拟退火、遗传算法子空间聚类

联合聚类

1　引言

随着信息技术和计算机技术的迅猛发展, 人们面临着越来越多的文本、图像、视频以及音频数据, 为帮助用户从这些大量数据中分析出其间所蕴涵的有价值的知识, 数据挖掘(Data

M ining, DM ) 技术应运而生。所谓数据挖掘, 就是从大量无序

的数据中发现隐含的、有效的、有价值的、可理解的模式, 进而发现有用的知识, 并得出时间的趋向和关联, 为用户提供问题求解层次的决策支持能力。与此同时, 聚类作为数据挖掘的主要方法之一, 也越来越引起人们的关注。

本文比较了数据挖掘中现有聚类算法的性能, 分析了它们各自的优缺点并指出了其今后的发展趋势。

图1　聚类算法分类示意图

211　层次聚类算法

层次聚类算法通过将数据组织成若干组并形成一个相应的树状图来进行聚类, 它又可以分为两类, 即自底向上的聚合层次聚类和自顶向下的分解层次聚类。聚合聚类的策略是先将每个对象各自作为一个原子聚类, 然后对这些原子聚类逐层进行聚合, 直至满足一定的终止条件; 后者则与前者相反, 它先将所有的对象都看成一个聚类, 然后将其不断分解直至满足终止条件。

对于聚合聚类算法来讲, 根据度量两个子类的相似度时所依据的距离不同, 又可将其分为基于Single 2L ink, Comp lete 2L ink 和Average 2L ink 的聚合聚类。Single 2L ink 在这三者中应用最为广泛, 它根据两个聚类中相隔最近的两个点之间的距离来评价这两个类之间的相似程度, 而后两者则分别依据两类中数据点之间的最远距离和平均距离来进行相似度评价。

CURE, ROCK 和CHAME LE ON 算法是聚合聚类中最具代

2　DM 中现有的聚类算法

聚类是一种常见的数据分析工具, 其目的是把大量数据点的集合分成若干类, 使得每个类中的数据之间最大程度地相似, 而不同类中的数据最大程度地不同。在多媒体信息检索及数据挖掘的过程中, 聚类处理对于建立高效的数据库索引、实现快速准确的信息检索具有重要的理论和现实意义。

本文以聚类算法所采用的基本思想为依据将它们分为五类, 即层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法以及用于高维数据的聚类算法, 如图1所示。

表性的三个方法。

Guha 等人在1998年提出了C URE 算法

[1]

。该方法不用

收稿日期:2006201204; 修返日期:2006203219基金项目:国家自然科学基金资助项目(60473117)

单个中心或对象来代表一个聚类, 而是选择数据空间中固定数目的、具有代表性的一些点共同来代表相应的类, 这样就可以

第1期贺　玲等:数据挖掘中的聚类算法综述

21214　基于平方误差的迭代重分配聚类

　　　・11・

识别具有复杂形状和不同大小的聚类, 从而能很好地过滤孤立点。ROCK 算法[2]是对C URE 的改进, 除了具有CURE 算法的一些优良特性之外, 它还适用于类别属性的数据。CHAME 2

LE ON 算法

[3]

基于平方误差的重分配聚类方法的主要思想是逐步对聚类结果进行优化、不断将目标数据集向各个聚类中心进行重新分配以获得最优解(判断是否是最优解的目标函数通常通过平方误差计算法得到) 。此类方法又可进一步分为概率聚类算法、考虑了最近邻影响的最近邻聚类算法以及K 2medoids 算法和K 2means 算法。

(1) 概率聚类算法的重要代表是M itchell 等人于1997年

是Karyp is 等人于1999年提出来的, 它在聚合聚

类的过程中利用了动态建模的技术。

212　分割聚类算法

分割聚类算法是另外一种重要的聚类方法。它先将数据点集分为k 个划分, 然后从这k 个初始划分开始, 通过重复的控制策略使某个准则最优化以达到最终的结果。这类方法又可分为基于密度的聚类、基于网格的聚类、基于图论的聚类和基于平方误差的迭代重分配聚类。

21211　基于密度的聚类

提出的期望最大化算法(Expectati on Maxi m izati on, E M ) [11]。它除了能处理异构数据之外, 还具有另外几个重要的特性:①能处理具有复杂结构的记录; ②能够连续处理成批的数据; ③具有在线处理能力; ④产生的聚类结果易于解释。

(2) ,

基于密度的聚类算法从数据对象的分布密度出发, 将密度足够大的相邻区域连接起来, 从而可以发现具有任意形状的聚类, 并能有效处理异常数据。它主要用于对空间数据的聚类。

DBSCAN 是一个典型的基于密度的聚类方法, [4]

。共享最近邻算法) 12ROCK 算法的思想结合起来K 个最近邻居从而简化了相似矩阵, , 但是其时间复杂度也提高到了O (N 2) (N 为数据点个数) 。

(3) K 2medoids 方法用类中的某个点来代表该聚类, 这种

定义为一组密度连接的点集, 区域来进行聚类。DE 5]密度来进行聚类小。此外, Ankerst 等人提出的OPTI CS, Xu 等人提出的DB 2

C LAS D 和马帅等人提出的CURD 算法也采用了基于密度的聚

方法能有效处理异常数据。它的两个最早版本是P AM 和

C LARA 算法

[13]

, 此后又有CLARANS

[14]

及其一系列的扩展算

类思想, 它们均针对数据在空间中呈现的不同密度分布对DB 2

SCAN 作了相应的改进。21212　基于网格的聚类

法。这类方法具有两个优点:它能处理任意类型的属性; 它对异常数据不敏感。

(4) K 2means 算法是目前为止应用最为广泛的一种聚类方

基于网格的聚类从对数据空间划分的角度出发, 利用属性空间的多维网格数据结构, 将空间划分为有限数目的单元以构成一个可以进行聚类分析的网格结构。该方法的主要特点是处理时间与数据对象的数目无关, 但与每维空间所划分的单元数相关; 而且, 基于其间接的处理步骤(数据→网格数据→空间划分→数据划分) , 该方法还与数据的输入顺序无关。与基于密度的聚类只能处理数值属性的数据所不同的是, 基于网格的聚类可以处理任意类型的数据, 但以降低聚类的质量和准确性为代价。

STI N G 是一个基于网格多分辨率的聚类方法, 它将空间

[6]

法, 其每个类别均用该类中所有数据的平均值(或加权平均) 来表示, 这个平均值即被称作聚类中心。该方法虽然不能用于类别属性的数据, 但对于数值属性的数据, 它能很好地体现聚类在几何和统计学上的意义。但是, 原始K 2means 算法也存在如下缺陷:①聚类结果的好坏依赖于对初始聚类中心的选择; ②容易陷入局部最优解; ③对K 值的选择没有准则可依循; ④对异常数据较为敏感; ⑤只能处理数值属性的数据; ⑥聚类结果可能不平衡。

为克服原始K 2means 算法存在的不足, 研究者从各自不同的角度提出了一系列K 2means 的变体, 如B radley 和Fayyad 等人从降低聚类结果对初始聚类中心的依赖程度入手对它作了改进, 同时也使该算法能适用于大规模的数据集[15]; Dhill on 等人则通过调整迭代过程中重新计算聚类中心的方法使其性能得到了提高[16]; Zhang 等人利用权值对数据点进行软分配以调整其迭代优化过程[17]; Pelleg 等人提出了一个新的X 2means 算法来加速其迭代过程[18]; Sarafis 则将遗传算法应用于K 2means 的目标函数构建中, 并提出了一个新的聚类算法[19]; 为了得到平衡的聚类结果, 文献[20]利用图论的划分思想对K 2means 作了改进; 文献[21]则将原始算法中的目标函数对应于一个各向同性的高斯混合模型; Berkhin 等人[22]将K 2means 的应用扩展到了分布式聚类。

213　基于约束的聚类算法

划分为方形单元, 不同层次的方形单元对应不同层次的分辨率。STI N G +

[7]

则对其进行了改进以用于处理动态进化的空

[8]

间数据。CL I Q UE 也是一个基于网格的聚类算法, 它结合了

网格聚类与密度聚类的思想, 对于处理大规模高维数据具有较好的效果。除这些算法以外, 以信号处理思想为基础的W ave 2

Cluster 算法也属基于网格聚类的范畴。21213　基于图论的聚类

[9]

基于图论的方法是把聚类转换为一个组合优化问题, 并利用图论和相关的启发式算法来解决该问题。其做法一般是先构造数据集的最小生成树(M ini m al Spanning Tree,MST ) , 然后逐步删除M ST 中具有最大长度的那些边, 从而形成更多的聚类。基于超图的划分和基于光谱的图划分方法[10]是这类算法的两个主要应用形式。该方法的一个优点在于它不需要进行一些相似度的计算, 就能把聚类问题映射为图论中的一个组合优化问题。

真实世界中的聚类问题往往是具备多种约束条件的, 然而由于在处理过程中不能准确表达相应的约束条件、不能很好地利用约束知识进行推理以及不能有效利用动态的约束条件, 使

・12・计算机应用研究2007年

得这一方法无法得到广泛的推广和应用。这里的约束可以是对个体对象的约束, 也可以是对聚类参数的约束, 它们均来自相关领域的经验知识。该方法的一个重要应用在于对存在障碍数据的二维空间数据进行聚类。C OD (Clustering with Ob 2

structed D istance )

[23]

的应用领域中均表现出了不同的性能, 也就是说, 很少有一种算法能同时适用于若干个不同的应用背景。

总体来说, 分割聚类算法的应用最为广泛, 其收敛速度快, 且能够扩展以用于大规模的数据集; 缺点在于它倾向于识别凸形分布、大小相近、密度相近的聚类, 而不能发现形状比较复杂的聚类, 并且初始聚类中心的选择和噪声数据会对聚类结果产生较大的影响。层次聚类方法不仅适用于任意属性和任意形状的数据集, 还可以灵活控制不同层次的聚类粒度, 因此具有较强的聚类能力, 但它大大延长了算法的执行时间; 此外, 对层次聚类算法中已经形成的聚类结构不能进行回溯处理。基于约束的聚类通常只用于处理某些特定应用领域中的特定需求。机器学习中的人工神经网络和模拟退火等方法虽然能利用相, 但其计算复杂度往往较高, 取, 虽然, , 因此, 寻求这类算法在聚类质量和算法时间复杂度之间的折中也是一个重要的问题。

本文选取聚类算法所处理的目标数据的属性(数值型N /类别型C ) 、算法的时间复杂度、能否处理大规模数据集、能否处理异常数据(噪声数据) 、能否处理高维数据、能否发现复杂的聚类形状、是否受初始聚类中心影响以及是否受数据输入顺序影响这八个参数, 总结比较了一些有代表性的算法的性能, 如表1所示。

表1　部分聚类算法性能总结与比较

目标数聚类算法

据属性CURE DBS CAN W ave 2Cluster

N N N 或C

就是处理这类问题的典型算法, 其主要思

想是用两点之间的障碍距离取代了一般的欧氏距离来计算其间的最小距离。更多关于这一聚类算法的总结可参考文献

[24]。

214　机器学习中的聚类算法

机器学习中的聚类算法是指与机器学习相关、采用了某些机器学习理论的聚类方法, 它主要包括人工神经网络方法以及基于进化理论的方法。

[25]

自组织映射(Self 2O rganizing Map, S OM ) 是利用人工神经网络进行聚类的较早尝试, 它也是向量量化方法的典型代表之一。该方法具有两个主要特点:①它是一种递增的方法, 即所有的数据点是逐一进行处理的; ②一个二维的平面上, 从而实现可视化, [26]很好的性能。

, 模拟退火的应用较为广泛, SI N I CC 算法

[27]

就是其中之一。在模拟退火中经常使用到

微扰因子, 其作用等同于把一个点从当前的聚类重新分配到一个随机选择的新类别中, 这与K 2means 中采用的机制有些类似。遗传算法也可以用于聚类处理, 它主要通过选择、交叉和变异这三种遗传算子的运算以不断优化可选方案从而得到最终的聚类结果。

利用进化理论进行聚类的缺陷在于它依赖于一些经验参数的选取, 并且具有较高的计算复杂度。为了克服上述不足之处, 有研究者尝试组合利用多种策略, 如将遗传算法与K 2means 结合起来, 并且使用变长基因编码, 这样不仅能提高K 2means 算法的效率, 还能运行多个K 2means 算法以确定合适的K 值

215　用于高维数据的聚类算法

[28]

能否能否能否能否发是否受

是否受数据

处理处理处理现复杂初始聚

输入顺序的

大数异常高维形状的类中心

影响

据集点数据聚类的影响

O (n 2能能否能否否) O (n l og n ) 能能否能是是时间复杂度

O (n ) O (n ) O (n 2) O (n ) O (n 2)

能能能能否能

能能能否能能

能能否否能否

能否能否能能

否否否是否是

否否否是否是

。

Hy per 2

N 或C

graphic

C N 或C K 2means S NN G A

N N 或C N

高维数据聚类是目前多媒体数据挖掘领域面临的重大挑战之一。对高维数据聚类的困难主要来源于以下两个因素:①高维属性空间中那些无关属性的出现使得数据失去了聚类趋势; ②高维使数据之间的区分界限变得模糊。除了降维这一最直接的方法之外, 对高维数据的聚类处理还包括子空间聚类以及联合聚类技术等。

CACT US

[29]

与适应度

函数相关

　　表1中, 算法的时间复杂度都是针对低维数据而言的, K 2

means 和G A 也均为原始的标准算法; n 为目标数据的数目, 对

于CURE 算法来讲, 由于它的执行依赖于对样本集(Sa mp le ) 的选择, 所以其时间复杂度由样本集的数据数目来决定。

从表1中反映出来的一个最突出的问题在于, 这些算法绝大多数不适用于高维数据, 而那些少数可以用于高维数据的算法, 其时间复杂度也往往会随着维度的升高而显著增高。

总之, 虽然一些算法相对其他方法在某些方面的性能有了一定程度的提高, 但它不可能在任何应用背景下均具有很好的结果, 即几乎没有一个算法能同时在表1中所示的八个方面都具有优良的性能。因此对于它们的改进还有一个相当大的空间。

采用了子空间聚类的思想, 它基于对原始空间

在二维平面上的一个投影处理。C L I Q UE 也是用于数值属性数据的一个简单的子空间聚类方法, 它不仅同时结合了基于密度和基于网格的聚类思想, 还借鉴了Ap ri ori 算法, 并利用MDL

(M ini m u m Descri p ti on Length ) 原理选择合适的子空间。

联合聚类对数据点和它们的属性同时进行聚类。以文本为例, 文献[30]中提出了文本联合聚类中一种基于双向划分图及其最小分割的代数学方法, 并揭示了联合聚类与图论划分之间的关系。

3　现有聚类算法的性能比较

从上面的分析介绍不难看出, 这些现有的聚类算法在不同

4　总结与展望

聚类算法的研究具有广泛的应用前景, 其今后的发展也面

第1期贺　玲等:数据挖掘中的聚类算法综述

439.

　　　・13・

临着越来越多的挑战。以其在多媒体领域中的应用为例, 鉴于多媒体特征数据本身所具备的高维性、复杂性、动态性以及容易达到大规模的特性, 对多媒体数据聚类算法的设计还应该更多地考虑以下几个方面的内容:

(1) 融合不同的聚类思想形成新的聚类算法, 从而综合利

[10]Chris D ing . A Tut orial on Spectral Clustering[C ].I C ML, 2004. [11]M itchell T . Machine Learning[M].Ne w York:McGra w 2H ill, 1997. [12]Ert oz L, Steinbach M , Kumar V. Finding Clusters of D ifferent Sizes,

Shapes, and Densities in Noisy, H igh D i m ensi onal Data [R ].M inneapolis:University of M innes ota, 2002.

[13]Kauf man L, Rousseeuw P . Finding Gr oup s in Data:An I ntr oducti on

t o Cluster Analysis[M].New York:John W iley and Sons, 1990. [14]Ng R, Han J. Efficient and Effective Clustering Methods f or Spatial

Data M ining[C ].Santiago:Pr oceedings of the 20th Conference on VLDB, 1994. 1442155.

[15]B radley P, Fayyad U. Refining I nitial Points for K 2means Clustering

[C ].Madis on:Pr oceedings of the 15th I C ML, 1998. 91299. [16]Dhill on I, Guan Y, Kogan J. Refining Clusters in H igh D i m ensi onal

Data[C ].A rlingt on:The 2nd SI A M I , Workshop on Clustering H igh D i m onal Data, 2002.

[17B. Dynam ic W eighting of Da 2

in ].oceedings of the 1st SI 2, []X 2means:Extending K 2means with Efficient Esti 2

of the Number of the Clusters[C ].Pr oceedings of the 17th I C 2ML, 2000.

[19]Sarafis I, Zalzala A M S, Trinder P W. A Genetic Rule 2based Data

Clustering Toolkit[C ].Honolulu:Congress on Evoluti onary Compu 2

tati on (CEC ) , 2002.

[20]Strehl A, Ghosh J. A Scalable App r oach t o Balanced, H igh 2di m en 2

si onal Clustering of Market Baskets[C ].Pr oceedings of the 17th I n 2ternati onal Conference on H igh Perfor mance Computing, Bangal ore:Sp ringer LNCS, 2000. 5252536.

[21]Banerjee A, Ghosh J. On Scaling up Balanced Clustering A lgorithm s

[C ].A rlingt on:Pr oceedings of the 2nd SI A M I CDM , 2002.

[22]Berkhin P, Becher J. Learning Si m p le Relati ons:Theory and App lica 2

ti ons[C ].A rlingt on:Pr oceedings of the 2nd SI A M I CDM, 2002. 3332349.

[23]Tung A K H, Hou J, Han J. Spatial Clustering in the Presence of Ob 2

stacles[C ].Heidelberg:Pr oceedings of the 17th I CDE, 2001. 3592367.

[24]Han J, KamberM , Tung A K H. Spatial ClusteringMethods in Data

M ining:A Survey[C ].Geographic Data M ining and Knowledge D is 2covery, 2001.

[25]Kohonen T . Self 2O rganizing Map s[M].Sp ringer Series in I nf or ma 2

ti on Sciences, 2001. 30.

[26]Yongqiang Cao, J ianhongW u . Dyna m ics of Pr ojective Adap tive Res o 2

nance Theory Model:The Foundati on of P ART A lgorithm [J ].I EEE Transacti ons on Neural Net w ork, 2004, 15(2) :2452260.

[27]B r own D, Huntley C . A Practical App licati on of Si m ulated Annealing

t o Clustering[R ].University of V irginia, 1991.

[28]Crist ofor D, Si m ovici D A. An I nfor mati on 2theoretical App r oach t o

Clustering Categorical Databases U sing Genetic A lgorithm s[C ].A r 2lingt on:The 2nd SI A M I CDM, Workshop on Clustering H igh D i m en 2si onal Data, 2002.

[29]Ganti V, Gehrke J, Ra makrishna R. CACT US 2Clustering Categorical

Data U sing Summaries[C ].San D iego:Pr oceedings of the 5th AC M SI GK DD , 1999. 73283.

[30]Dhill on I . Co 2clustering Documents and Words U sing B i partite Spec 2

tral Graph Partiti oning [C ].San Francis o:Pr oceedings of the 7th AC M SI GK DD, 2001. 2692274.

用不同聚类算法的优点。

(2) 处理大规模数据和高维数据的能力, 这是多媒体数据

挖掘中聚类算法必须解决的关键问题。

(3) 对聚类的结果进行准确评价, 以判断是否达到最优解, 这也自然要求聚类结果具有可解释性。

(4) 选取合适的聚类类别数, 这是一个重要的参数。它的确定应更多地依赖于相关的经验知识以及对目标数据集所进行的必要的预处理。

(5) 对数据进行合理的预处理。该过程包括对高维数据

以及对大规模数据建立索引等, 它不仅是实现(4) 的前提之一, 也为获得更准确的聚类结果提供了一个重要的手段。

(6) 作用。

(7) 、选择合适的聚类算法, 还能使以上很多方面的问题都能得到合理的解决, 从而提高相应的聚类算法的性能。

在多媒体数据聚类的应用中, 对原始数据如图像等进行特征提取, 并用这些特征数据代替原始数据进行聚类, 均体现了领域知识的融合。参考文献:

[1]Guha S, Rast ogi R, Shi m K . CURE:An Efficient Clustering A lgo 2

rithm f or Large Databases[C ].Seattle:Pr oceedings of the AC M SI G 2MOD Conference, 1998. 73284.

[2]Guha S, Rast ogi R, Shi m K . ROCK:A Robust Clustering A lgorithm

for Categorical A ttributes[C ].Sydney:Pr oceedings of the 15th I C 2DE, 1999. 5122521.

[3]Karyp is G, Han E 2H, Kumar V. CHAMELEON:A H ierarchical

Clustering A lgorithm U sing Dyna m ic Modeling [J ].I EEE Computer,

1999, 32(8) :68275.

[4]EsterM , Kriegel H 2P, Sander J, et al . A Density 2based A lgorithm

for D iscovering Clusters in Large Spatial Databases with Noise [C ].Portland:Pr oceedings of the 2nd AC M SI GK DD, 1996. 2262231. [5]

H inneburg A, Kei m D. An Efficient App r oach t o Clustering Large Multi m edia Databases with Noise[C ].New York:Pr oceedings of the 4th AC M SI GK DD, 1998. 58265.

[6]W ang W , Yang J, Muntz R. STI N G:A Statistical I nfor mati on Grid

App r oach t o Spatial Data M ining [C ].A thens:Pr oceedings of the 23rd Conference on VLDB, 1997. 1862195.

[7]W ang W , Yang J, Muntz R R. STI N G +:An App r oach t o Active

Spatial Data M ining [C ].Sydney:Pr oceedings of the 15th I CDE, 1999. 1162125. [8]

Agrawal R, Gehrke J, Gunopul os D, et al . Aut omatic Subs pace Clustering of H igh D i m ensi onal Data for Data M ining App licati ons [C ].Seattle:Pr oceedings of the AC M SI G MOD Conference, 1998. 942105.

[9]Sheikholesla m i G, Chatterjee S, Zhang A. W aveCluster:A Multires o 2

luti on Clustering App r oach f or Very Large Spatial Databases [C ].Ne w York:Pr oceedings of the 24th Conference on VLDB, 1998. 4282

作者简介:

贺玲(19762) , 女, 博士研究生, 主要研究方向为多媒体信息系统、多媒

体数据挖掘; 吴玲达, 女, 教授, 博导, 主要研究方向为多媒体信息系统与虚拟现实技术; 蔡益朝(19762) , 主要研究方向为智能决策。