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

1、数据挖掘中聚类算法的综述3胡庆林叶念渝朱明富(华中科技大学控制科学与工程系武汉430074摘要聚类算法是数据挖掘领域中非常重要的技术。本综述按照聚类算法的分类,对每一类中具有代表性的算法进行了介绍,分析和评价。最后从发现聚类形状、所适用的数据库和输入数据顺序的敏感性等方面进行了算法推荐,供大家在选择聚类算法时参考。关键词数据挖掘聚类分析聚类算法中图分类号TP301.61引言数据挖掘(Data M ining:是从大量的、不完全的、有噪声的、模糊的、随机的数据中,提取隐含在其中的、人们事先不知道的、但又是潜在有用信息和知识的过程。当人们使用数据挖掘工具对数据中的模型和关系进行辨识的时候,通常第一

2、个步骤就是聚类。因此根据实际科研情况,选择一个好的聚类算法对后续的研究工作是非常关键的。聚类的定义:聚类是将数据划分成群组的过程。通过确定数据之间在预先制定的属性上的相似性来完成聚类任务,这样最相似的数据就聚集成簇。聚类与分类的不同点:聚类的类别取决于数据本身;而分类的类别是由数据分析人员预先定义好的。聚类算法的分类:一般可分为基于层次的,基于划分的,基于密度的,基于网格的和基于模型的五种。2基于层次的聚类算法层次的聚类算法对给定数据对象进行层次上的分解。根据层次分解的顺序是自下向上的还是自上向下的,可分为凝聚算法(自下向上的和分裂算法(自上向下。2.1凝聚算法思想该算法的主要思想是发现最大连

3、通子图,如果至少存在一条连接两个簇的边,并且两点之间的最短距离小于或等于给定的阀值,则合并这两个簇。该算法寻找的是一个团,而不是连通的分量,一个团是一个最大的图,其中任意两个顶点之间都存在一个条边。如果两个簇中的点之间的距离小于距离阀值,则合并这两个簇。如果在两个目标簇中,一个簇中的所有成员与另一个簇中的所有成员之间的平均距离小于距离阀值,则合并这两个簇。评论:以上三个算法的复杂度都是O(n2, (其中n是数据成员的个数,因此他们的效率不高。而且在单连接算法中存在链式效应(chain effect,影响了凝聚算法的实际应用。链式效应是指:当两个簇中只要存在两个相近的点,这两个簇就合并了,完全不

4、管这两个簇中还可能存在其他相距很远的点。因此合并后的簇中可能存在一些根本就互不相关点。Clustering using H ierarchies算法B I RCH是一个综合性的层次聚类方法。它用聚类特征和聚类特征树(CF来描述聚类过程。CF树是一个平衡树,它有两个参数:分支因子和阈值,它存储了层次聚类的聚类特征。分支因子定义为每个非叶节点孩子的最大数目,而阈值是指71第35卷(2007第2期计算机与数字工程3收到本文时间:2006年4月7日作者简介:胡庆林,男,在读硕士,主要研究方向:数据挖掘,电子商务。叶念瑜,女,教授,主要研究方向:计算机控制与管理一体化。朱明富,男,副教授。主要研究方向:

5、决策支持系统,企业信息工程、控制管理一体化。存储在树的叶子节点中的子聚类的最大直径。一个数据项总是被插入到最近的叶子条目(子聚类中。如果在插入后,使得该叶子节点中的子聚类的直径大于阈值,则该叶子节点或其他节点很有可能被分裂。在新数据插入后,关于该数据的信息会向树根传递。我们可以通过改变阈值来修改CF树的大小,从而控制其占内存容量;另外,CF树可以动态地构造,因此不要求所有的数据一次性地读入内存,故存储在外存上的数据项可以逐个地被读入。B I RCH算法通过一次扫描就可以进行较好的聚类,该算法的计算复杂度是O(n,其中n是对象的数目。评论:优点:B I RCH算法通过聚类特征可以方便地进行中心、

6、半径、直径及类内、类间距离的运算。算法具有对象数目的线性易伸缩性,及良好的聚类质量。缺点:由于受CF树节点大小的限制, CF树节点并不总是与用户所认为的自然聚类相对应。而且,如果簇不是球形,B I RCH算法则不能很好地工作。2.2分裂算法思想初始的时候,所有的数据成员都包含在一个簇中,是一个簇,然后将上层的簇重复地分裂为两个下层簇,直到每一个成员都组成一个单独的簇为止。代表算法:基于单连接算法MST。其分裂过程为:将最小生成树的边从最长到最短依次进行剪切。该算法将产生与凝聚方法完全相同的簇集,只是产生过程的次序完全相反。层次的聚类算法评论:层次聚类方法的前提条件是假设数据是一次性提供的,因此

7、都不是增量算法。其缺陷在于,一旦一个步骤(合并或分裂完成,它就不能被撤消,因而不能更正错误的决定。改进层次方法的聚类质量的一个有希望的方向是将层次聚类和其他聚类技术进行集成,例如上面的B I RCH算法。3划分的聚类算法将一个有N个样本的数据库,分为K个划分(KN,每个划分表示一个簇,并同时满足以下两个条件的过程,称为划分算法。(1每个簇至少包含一个样本;(2每个样本必须属于且仅属于一个簇。其具体代表算法有:P AM算法,CLARA算法, CLARANS算法等等。3.1P AM(Partiti oning A r ound Medoids算法该算法也称作K-中心点算法,是指用中心点来代表一个簇

8、。利用中心点这个概念能够很好地处理异常点。初始时,将N个成员中的K个随机成员设置为中心点集合,然后在每一步中,对输入数据集中目前还不是中心点的成员进行逐个检验,看是否可成为中心点。评论:该算法将判定是否存在一个成员,可以取代已存在的一个中心点。通过检验所有的中心点与非中心点组成的对,PAM算法将选择最能提高聚类效果的对。该方法的聚类效果的度量是簇中的非中心点到簇的中心点的所有距离之和。由于在每次迭代过程中需要确定出K (N-K个交换对,在每个交换对中又要计算N -K个非中心点到簇的中心点距离之和的变化,故每次迭代的总的复杂度是O(K(N-K2。所以该算法的复杂性太高。但其算法逻辑较简单,适合小

9、型的数据库。3.2CLARA(Clustering LARge App licati ons算法通过数据库抽样,改进了P AM的时间复杂性。其基本思想是首先对数据库进行抽样,然后将利用P AM算法在抽样后的数据上进行聚类,得到的中心点就是整个数据库的中心点,最后将数据库中所有成员分配到离自身距离最近的中心点所代表的簇中。评论:为了提高CLARA的精度,可以分别进行几组抽样,然后在每组抽样上都应用P AM算法,最后将最好的聚类结果作为最终的聚类结果。由于使用了抽样技术,对于大型数据库而言,CLARA比P AM更有效率,但其效果则取决于样本规模。有研究结果2表明,样本规模为40+2K的数据库,进行

10、5次抽样会得到较好的结果。3.3CLARANS(Clustering Large App licati ons basedupon Random ized Search算法CLARANS通过利用多次不同抽样来改进CLARA。除了需要与P AM一样的输入外,CLAR2 ANS还需要输入两个参数:maxneighbor和num l o2 cal。maxneighbor表示一个节点可以与任意特定节点(邻居进行比较的数目。随着maxneighbor的增长,CLARANS与P AM更加相近,这是由于所有节点都可能被检验。Num l ocal表示抽样次数。评论:由于在每个样本上都要进行新的聚类,所以nu

11、m l ocal也表示需要进行聚类的次数。研究结果3表明当nu m l ocal=2和maxneighbor=max (0.01253K(N-K,250时,聚类效果较好。对于任意规模的数据集,CLARANS比CLARA和P AM效率要高。3.4CURE(Clustering U sing REp resentatives算法81胡庆林等:数据挖掘中聚类算法的综述第35卷CURE算法中即有层次部分,也有划分部分,所以CURE是一个综合性的聚类算法。CURE算法过程,首先从每个簇中选择c(常数个点,然后通过应用收缩因子a,这些分散的点将向簇的质心方向收缩。当a为1的时候,所有点都收缩成一点,即质心

12、。由这些点代表的簇,要比单个点更具有代表性。通过多个有代表性的点,簇的形状可以更好地被表示出来。这一步完成后,再使用层次聚类算法中的凝聚算法。在凝聚算法中的每一步,距离最近的代表性点所对应的簇将被合并。它们之间的距离被定义为两个簇中代表性点之间距离的最小值。评价:该算法优点:它回避用所有点或单个质心来表示一个簇的传统方法,将一个簇用多个具有代表性的点来表示,使C URE可以适应非球形的几何形状。另外,收缩因子降底了噪音对聚类的影响,从而使CURE对孤立点的处理更加健壮,而且能识别非球形和大小变化比较大的簇。对于大型数据库具有良好的伸缩性。缺点:参数设置对聚类结果有很大的影响,CURE算法不能处

13、理分类属性。C URE的复杂度是O(n,其中n是对象的数目。划分的聚类算法评论:划分聚类方法对在中小规模的数据库中发现球状簇很适用。为了对大规模的数据集进行聚类,以及处理复杂形状的聚类,基于划分的方法有待进一步的扩展。4基于密度的算法提出基于密度的聚类方法是为了发现任意形状的聚类结果。其主要思想是:只要临近区域的密度超过某个阈值,就继续聚类。这样的方法可以用来过滤“噪声”孤立点数据,发现任意形状的簇。代表算法:DBSCAN(Density-Based Spatial Cluste2 ring with Noise。4.1DBSCAN算法可以将足够高密度的区域划分为簇,并可以在带有“噪声”的空间

14、数据库中发现任意形状的聚类。该算法定义簇为密度相连的点的最大集合。DBSCAN通过检查数据库中每个点的邻域来寻找聚类。如果一个点p的邻域中包含数据项的个数多于最小阀值,则创建一个以p作为核心对象的新簇。然后反复地寻找从这些核心对象直接密度可达的对象,当没有新的点可以被添加到任何簇时,该过程结束。不被包含在任何簇中的对象被认为是“噪声”。如果采用空间索引,DBSCAN的计算复杂度是O(n l og n,这里n是数据库中对象数目。否则,计算复杂度是O(n2。评价:DBSCAN算法具有很多优点:能够发现空间数据库中任意形状的密度连通集;在给定合适的参数条件下,能很好地处理噪声点;对用户领域知识要求较

15、少;对数据的输入顺序不太敏感;适用于大型数据库。其缺点:DBSCAN算法要求事先指定领域和阈值;具体使用的参数依赖于应用的目的。5基于网格的算法这种算法首先将数据空间划分成为有限个单元的网格结构,所有的处理都是以单个的单元为对象的。处理速度通常与目标数据库中记录的个数无关,它只与单元的个数有关,故这种算法的一个突出优点就是处理速度很快。代表算法有:STI N G (Statistical I nf or mati on Grid based method算法。STI N G算法将空间区域划分为矩形单元。针对不同级别的分辨率,通常存在多个级别的矩形单元,这些单元形成了一个层次结构:高层的每个单元

16、被划分为多个低一层的单元。高层单元的统计参数可以很容易地从低层单元的计算得到。这些参数包括:属性无关的参数count;属性相关的参数m(平均值,s(标准偏差,m in(最小值,max(最大值,以及该单元中属性值遵循的分布(distribu2 ti on类型。STI N G扫描数据库一次来计算单元的统计信息,因此产生聚类的时间复杂度是O(n,其中n是对象的数目。在层次结构建立后,查询处理时间是O(g,g是最低层风格单元的数目,通常远远小于n。评价:优点是:效率高,且利于并行处理和增量更新。缺点:STI N G算法中,如果数据粒度比较细,处理的代价会明显增加;而且该算法没有考虑子单元和其他相邻单元

17、之间的关系。尽管该算法处理速度较快,但是可能会降低簇的质量和精确性。6基于模型的算法基于模型的方法为每个簇都假定了一个模型,并寻找数据对给定模型的最佳拟合。该算法通过构建反映数据点空间分布的密度函数来实现聚类。这种聚类方法试图优化给定的数据和某些数学模型之间的适应性。其代表算法:COBW EB算法。COBW EB算法以一个分类树的形式创建层次聚类,它的输入对象用“分类属性”-“值”对来描述。其工作流程是:在给定一个新的对象后,COB2 W E B沿一条适当的路径向下,修改计数,以寻找可91第35卷(2007第2期计算机与数字工程以分类该对象的最好节点。该判定基于将对象临时置于每个节点,并计算结

18、果划分的分类效用。产生最高分类效用的位置应当是对象节点的一个好的选择。给定一个新的对象,COBW EB沿一条适当的路径向下,修改计数,寻找可以分类该对象的最好节点。在该过程中,将对象临时置于每个节点上,并计算划分的分类效用结果。产生最高分类效用的位置是对象节点的一个好的选择。评价:优点:COBW EB可以自动修正划分中类的数目;不需要用户提供输入参数。缺点:COB2 W EB基于这样一个假设:在每个属性上的概率分布是彼此独立的。但这个假设并不总是成立。分类树对于偏斜的输入数据不是高度平衡的,它可能导致时间和空间复杂性的剧烈变化。COBW E B不适用于聚类大型数据库的数据。7综合结论通过以上的

19、分析得知,没有一种算法是十全十美的,建议使用者根据实际情况(例如发现聚类的形状、数据输入顺序是否敏感、适用数据库的大小或者算法效率来选择聚类算法。一般情况下有以下结论:目标数据库如果比较大,建议使用综合性的聚类算法,如:B I RCH、CURE、DBSCAN和STI N G 等,以提高算法效率。如果聚类的形状是球形或者凸形,B I RCH和CLARANS比较适合。一般而言,聚类算法对数据输入的顺序都比较敏感。如果希望不敏感,可以选用基于网格的STI N G算法。将不同类型的聚类算法相互结合(例如B I RCH算法和CURE算法,综合各自的优点,以满足不同的聚类要求。是今后聚类算法的一个重要发展

20、方向。参考文献1M argaret H.Dunha m著,郭崇慧等译.数据挖掘教程M.清华大学出版社,20052L.Kauf man and P.J Rousseeu w.Finding Gr oup s in Data:An I ntr oducti on t o Cluster AnalysisM.Ne w York:John W iley&Sons,19903Ray mond T.Ng and J ia wei Han.Efficient and effectiveclustering methods f or s patial data m iningR.Pr oceed2 ings

21、of the internati onal Very Large Databases Conference, 1994:1441554汤效琴,戴汝源.数据挖掘中聚类分析的技术方法S.微计算机信息,20035范明,孟小峰译.数据挖掘:概念与技术聚类分析M.北京:机械工业出版社,2001:2232586钱锋等.知识发现中的聚类分析及其应用J.杭州师范学院学报,2001(2:3437(上接第10页文件和相连接的三角网文件,整个三角网不管是哪部分都将按需要以文件地址标号形式存入RAM 中,这将大大减少占用存储空间。6结束语本文提出了一种快速、有效的散乱点集Dealu2 any三角剖分算法,算法适用于大

22、数量点集的Delaunay三角剖分,已对数百万个点进行了三角网的构建,实际应用的效果很好。而且格子划分灵活,大小随点云情况而定,网格的宽度适应点的疏密变化;点及三角网的文件管理较方便。本算法具有简便实用,生成速度快,点集划分和三角网格构建时间复杂度与点数目成近优线性关系,可靠性高等特点。该算法具有很大的实用价值和应用前景。参考文献1杜立彬,高晓辉,王昊等.逆向工程各关键技术的研究进展J.机械制造,2004,(6:41452曲利岩,吴建华,陈永校.有限元网格的自动生成及快速实现J.电机与控制学报,2002,6(1:34383武晓波,王世新,肖春生.Delaunay三角网的生成算法研究J.测绘学报

23、,1999,28(1:28354Sap idis N,Perucchi o R.Delaunay triangulati on of arbitrarilyshaped p lanar domainsJ.CAG D,1991,(8:421437 5Bor ouchaki H,Lo S H.Fast Delaunay triangulati on in thethree di m ensi onsJ.Computer M ethods App l.M ech.En2 grg,1995,128(2:1531676周培德.计算几何2算法分析与设计M.北京:清华大学出版社,20017T.M idtbi

24、.Spatial Modeling by Delaunay Net w orks of T woand Three D i m ensi onsM.Doct oral Thesis,University of Tr ondhei m,199302数据挖掘中聚类算法的综述第35卷Key wordshe l m e t-m o un te d d isp l ays,SU SAN,cu rve fitti ng,sub-p i xe l(Page:14Survey of C luster Ana lysis i n Da t a M i n i n g byHu Q inglinAbstractC

25、 l u ste r a rithm e ti c is a ve ry i m po rtan t techno l o2 gy i n the a rea o f da ta m i n i ng.The rep re se n ted c l u s te r a2 rithm e ti c is i n tr o duced and ana l yzed i n th is a rti c l e.Fo r yo u r re fe re nce,som e sugge s ti o n s a re lis te d a t the e nd. Key wordsda ta m i

26、n i ng,c l u s te r ana l ysis,c l u ste r a rithm e2 ti c(Page:17O pti m i za ti on Stra tegy for Aud i o Processi n g Ar ith m eti c Used i n M PEG-1Layer3Ba sed on T M S320C6000Ch i pbyD ai D andanAbstractTh is p ap e r dea ls w ith the op ti m i za ti o n o f the key a l go rithm s i n the M PEG

27、-1l aye r3s tanda rdpo l y2 p ha se filte r bank,m o d i fi ed and d isc re te co s i ne Tran s2 fo r m,quan ti za ti o n,p hycho aco u sti c m o de l and b it o r no ise a ll o ca ti o n.O p ti m i za ti o n ba sed o n the T M S320C6000D SP p l a tfo r m w ith C6711c ited is a lso d is2 cu s sed.Th

28、e e xe cu ti o n o f l aye r3deco de r p r o g ram is g rea tl y acce l e ra te d th r o ugh the se m e tho d s.La s tl y,the p ap e r co nc l ude s and p u ts fo r w a rd ne ed no ti c i ng p r o b2 l em s.Key wordspo l yp ha se filte r bank,m o d i fi ed d isc re te co2 s i ne tran sfo r m,p e rce

29、p tua l co d i ng,p hycho aco u s ti c m o d2 e l,quan ti za ti o n(Page:21D esi gn and Ana lysis of Eff i c i ency for the Recursi on A lgo2 r ith m byYuan J insongAbstractThe recu rs i o n a l go rithm is a ki nd o f p r o g ram de s i gn m e tho d,w h i ch is p rac ti ca l and u se d fre quen tl

30、y.I ts effi c i e ncy que s ti o n is w o rth s tudyi ng.Th is a rti c l e p re se n ts the gene ra lity m e tho d to ana l yze re cu rs i o n a l go2 rithm:the re cu rsi ve e xp re s s i o n com p u ta ti o n m e tho d and the recu rs i o n tran sfe r tre e m e tho d,and p e rfo r m s them th r o u

31、gh e xam p l e s.Key wordsrecu rsi o n,com p li cacy o f ti m e,re cu rs i ve e xp re s s i o n(Page:25Research on Da t a I n tegra ti on Ba sed on X ML and W eb Serv i ce byCui W eiAbstractD ue to the ub i qu ity o f i nfo r m a ti o n is l and s and the he te r o ge neo u s system s am o ng en te

32、r p rise,da ta comm un i ca ti o n and da ta sha ri ng i n and be t w e en en te r2 p rise a re b l o cked.Fr om the vi ew po i n t o f s l o vi ng da ta i n2 te g ra ti o n fo r en te r p rise,th is a rti c l e s i m p l y sum s up and ana l yse s the p re se n t techno l o g i e s fo r da ta i n t

33、e g ra ti o n, and g i ve s a schem e w h i ch is ba se d o n X M L and W e b se rvi ce fo r bu il d i ng a h i gh effi c i e n t and un i fo r m e n te r p rise da ta i n te g ra ti o n.Key wordsX M L,W eb se rvi ce,da ta i n te g ra ti o n(Page:27 On tology Ba sed A ssoc i a ti on RulesM i n i n g

34、 byChen X iaAbstractTh is p ap e r p re sen ts an o n to l o gy-ba sed a s so2 c i a ti o n ru l e s m i n i ng m e tho d.It is to bu il d o n to l o gy o n som e dom a i n and the n ba se it to l e ad the m i n i ng p r o ce ss w h i ch w ill fa sten the p r o ce s s and i m p r o ve the effi c i e

35、ncy and qua lity.A lso it i nc l ude s the va l ue m e a su rem en ts o f a sso c i a ti o n ru l e s.Key wordso n to l o gy,a s so c i a ti o n ru l e s,da ta m i n i ng,se2 m an ti c W e b(Page:32Research on V isua li za ti on i n Lake D redg i n g Up Ba sed on O penGL byKang L ingAbstractThe re s

36、ea rch ba sed o n O p e nGL m ake s the p r o ce s s o f l ake d re dg i ng up vis i b l e.Th r o ugh B ezi e r su r2 face fitti ng,it rep re se n ts su rface o f unde r w a te r silt by sam p li ng po i n ts.Acco rd i ng to sam p li ng po i n ts,it co n2 s truc ts the cu rve abo u t th i ckne s s o f s ilt hvo l um e Q by l e a s t squa re m e tho d.I t adop ts o f O p enG L