改进的聚类分析算法及其性能分析(1)

1、Computer Era No.820100引言K-均值是目前应用最为广泛的聚类分析算法之一,是解决聚类问题的经典算法,然而K-均值具有人为确定k值、过分依赖k初始聚类中心点的缺点,而且运算量大,效率不高。目前对于K-均值算法的改进也有很多种,比如基于遗传算法的K-均值1、引入惩罚因子的K-均值2、PBKP算法3等。网格聚类算法的效率非常高,而且可以发现任意形状的簇,但是网格聚类也存在种种的缺陷,比如依赖于密度阀值的选择等。目前对于网格聚类的改进算法也有很多,比如二分网格聚类4、自适应网格聚类5、GCHL6等。本文针对上述算法的缺点,结合他们的优点提出一种改进的聚类分析算法融合聚类分析算法。1

2、融合聚类分析算法1.1算法的基本概念设A=(D1,D2,D n是n个有界定义域,S=D1×D2××D n是一个n维空间,我们将D1,D2,D n看成是S的维。算法的输入则是一个n维空间的点集,设为V=v1,v2,v n,其中v1=v i1,v i2,v in代表第i个点,v ijD j表示第i个点的第j维的分量。定义1网格单元:不妨设第i维上的分布点取值在区间l i,h i中,i=1,2,n,将每一维分成p个不相交的左闭右开的等长区间,这些区间就称为网格单元。这样,数据空间被分割成p n个网格单元,网格单元在第i 维上的长度为,第i维上的第j 个区间段可由式得出。

3、定义2网格单元密度:网格单元C i的密度Den(C i定义为该网格单元中的数据点的个数。定义3密集单元与自由数据:设定密度阀值为Minpts,将密度大于密度阀值Minpts的网格定义为密集单元,将密度小于密度阀值的单元中的数据称为自由数据。定义4聚类重心:给定簇K i=(t i1,t i2,t im,则其均值即聚类 重心定义为其中n i为簇K i中对象的个数,x,y为簇K i中的两两不同的对象。定义5中间聚类:对样本空间进行划分,定义单元网格集,计算网格单元的密度,将密度密集的单元进行网格聚类,这一过程叫中间聚类。中间聚类只包含分布比较密集的点,并不包含全部的聚集对象,中间聚类生成的簇叫中间聚

4、类簇。定义6后聚类:中间聚类结束后,计算每个中间聚类簇的中心作为初始中心点,然后对剩余的自由数据进行k-means聚类,这一过程叫做后聚类,所产生的簇叫做后聚类簇。1.2算法的基本思想首先基于网格聚类分析的思想,对样本空间进行划分定义网格单元集,将对象映射到相应的网格单元中,计算网格单元的密度,标记密度大于密度阀值的单元和密度小于密度阀值的数据,由邻近的密集单元合并形成“中间聚类簇”(中间聚改进的聚类分析算法及其性能分析郭书杰,吴小欣,黄杰(91550部队指控中心,辽宁大连116023摘要:提出了一种改进的聚类分析算法,该算法采用类似中间聚类与最终聚类分布的思想,先对密集区域进行聚类,形成了K

5、个聚类,然后再对相对分散的自由数据进行K-means聚类,使聚类分析在迭代过程中始终沿着最优的方向进行,减小了迭代次数,提高了收敛速度。该算法融合了网格聚类与K-均值聚类的优点,并且引入了一种新的划分网格的算法和新的计算密度阀值的函数。理论分析以及实验证明,改进算法的聚类过程达到了令人满意的效果。关键词:聚类分析;K-均值算法;网格聚类;融合聚类Improved Clustering Analysis Algorithm and Its Performance AnalysisGUO Shu-jie,WU Xiao-xin,HUANG Jie(Command and Control Cente

6、r of Army91550,Dalian,Liaoning116023,ChinaAbstract:An improved clustering analysis algorithm is proposed.Using the idea similar to half-finished clustering and final clustering distribution,the algorithm firstly clusters concentrated regions to get K clusters,and then clusters relatively scattered f

7、reedata in K-means,which makes clustering analysis always follow optimal direction in iterative process,reduces iteration times and improves convergence speed.The algorithm integrates the advantages of grid-based clustering and K-means clustering,and introduces a new algorithm of partitioning grid a

8、nd new function of computing density threshold.The theoretical analysis and experiments prove that the clustering process of the improved algorithm achieves satisfactory results.Key words:clustering analysis;K-means algorithm;grid-based clustering;fusion clustering··4计算机时代2010年第8期类簇并不包含比较离

9、散的自由数据;计算中间聚类簇的重心作为初始聚类中心点,计算自由数据到每个聚类中心的距离,将自由数据分配到最近的中间聚类中,形成“后聚类簇”;重新计算每个后聚类的初始聚类中心,若无变化则算法终止,若有变化则重新进行聚类,直到满足条件完成聚类。网格定义本身就是一个难题,网格大小与放置对于聚类的结果具有很大的影响,如何划分网格对于算法非常重要。在融合算法中,引入了一种新的函数用于网格的划分:式中,l i 为第i 分量的长度,i=1,2,n。同时,基于网格的聚类非常依赖于密度阀值的选择,过大或者过小都会影响算法的性能。在融合算法中,对于密度阀值的确定,提出了一种新的算法: 式中Den(C i ,i=1

10、,2,N 为密度最高的N 个密集单元的密度值,N 的值视具体的数据而定。一般情况下将Den(C i 降序排列,如果Den(C i 与Den(C i+1发生明显跳变,则N=i。1.3算法的步骤根据1.2节算法基本思想的描述,算法的基本步骤如下。step 1:将数据空间划分为m 个不相交、等长的网格单元,定义网格单元集;step 2:将对象指派到合适的单元中;step 3:计算每个单元的密度;step 4:将密度大于密度阀值Minpts 的网格标记为“密集单元”,将密度小于密度阀值的单元中的数据标记为“自由数据”;step 5:反复任选一未被聚类的密集单元,将其和与之相邻的密集单元合并为一簇,直至

11、所有密集单元均被聚类,形成K 个“中间聚类”;step 6:计算这K个中间聚类的重心,作为初始聚类中心; step 7:反复任选一自由数据对象,计算其与k 个初始聚类中心的距离dis(x,C i ,其中x 为自由数据对象,C i 为第i 个类,若dis(x,C i 最小,则xC i ,直至不再存在自由数据,形成“后聚类”;step 8:重新计算后聚类的重心,若 则聚类结束,否则继续进行K-均值聚类,直到完 成聚类。2融合聚类算法的性能检验与分析2.1时间复杂度分析在本算法中,定义网格、将数据的对象映射到网格中并且计算网格密度,这一过程的时间复杂度为O(n,n 为点的个数;对于每个密集单元,检查

12、所有与它相关联的密集单元生成簇,假设密集单元的总个数为m',与一个密集单元相关联的单元数最大值为2d,则这个过程的时间复杂度为O(2d×m'。后聚类的时间复杂度为O(k×t×n',其中t 是迭代次数,n'是自由数据的个数。在本算法中,由于已经对数据集进行了基于密度和网格的中间聚类处理,使得中间聚类中心与最终聚类中心分布类似,这样对于自由数据进行K-均值聚类,需要的迭代次数就会很小,相对的时间也会大大缩短。从以上的分析来看融合算法总的时间复杂度最大时为O(n+O(2d ×m'+O(k×t×n,整个

13、聚类过程所需要的时间与数据集中的数据点数成线性关系,与维数成指数关系,总体来讲融合聚类在时间上是高效的。2.2试验结果对比实验的样本数据使用了著名的鸢尾花(Iris 数据集,该数据集可以从加州大学欧文分校的机器学习数据库中得到。该数据集包括3类花的4个特性:萼片宽度、萼片长度、花瓣宽度、花瓣长度,共150条纪录。首先,对比融合算法与网格聚类算法的聚类结果。使用GB 算法对数据进行聚类,得到的结果如图1所示。1GB 的聚类结果从图1我们可以看出,网格聚类的结果丢失了很多点,聚类结果不能令人满意。这是由于基于网格的聚类只处理高密度区域,低密度区域会被丢弃,造成簇的丢失。但是使用融合聚类得到的结果(

14、如图2所示要比网格聚类的结果好很多。2融合的聚类结果接下来,对比融合聚类算法的聚类结果与K-均值聚类算法的聚类结果。利用融合聚类算法进行多次试验,聚类的过程经历了中间聚类、后聚类、1次迭代后便结束聚类,共得到3类。每个类的初始中心在每个聚类阶段的值如表1所示。··5Computer Era No.82010表1融合聚类结果类0类1类2中间聚类6.6333333333.1666666675.4799999552.2399999784.9818181883.3863636471.4749999970.245454556.2733333272.6933333564.5333333

15、651.406666644后聚类6.8405413.0783785.7513512.1135135.0078433.41.4941180.2607845.9354842.7548394.4322581.424194最终聚类6.853.0736845.7421052.0710535.0063.4181.4640.2445.9016132.7483874.3935481.433871图3给出了该次聚类过程中聚类中心变化的折线图。图中每个类的聚类中心在每个阶段变化都不大,且迅速地收敛,这说明融合聚类算法得出的密集单元很好地模拟了数据集合中密集区域的分布,很快地确定了K 个初始聚类中心点,然后又利用K

16、-均值聚类将自由数据重新聚类,可以快速有效地完成聚类。3融合的初始聚类中心利用K-均值聚类对Iris 数据进行多次实验得到的结果,从初始聚类中心到最终聚类中心变化都很大。如图4所示,在该次聚类过程中,K-均值算法很随机地抽取了3个点作为初始聚类中心,由于不能很好地捕获自然聚类的中心,算法不断地寻找更优的初始聚类中心,总是不断变化着聚类中心,使得算法不能很快收敛,算法的迭代次数也明显增加到11次。4K-means 的初始聚类中心综上所述,我们可以看出,基于凝聚度和分离度的簇的性能评估,融合算法要优于K-means 算法。3结束语本文所提出的融合聚类分析算法,取得了很好的实验结果。但算法仍然存在着

17、不足之处,比如合适的密度阀值的选择比较困难等,这些因素会影响到算法的性能,这也是今后需要我们继续研究和改进的地方。参考文献:1王敞,陈增强,袁著祉.基于遗传算法的K-均值聚类分析J.计算机科学,2003.30(2:1631642王红睿,赵黎明,裴剑.均衡化的改进均值聚类法J.吉林大学学报(信息科学版,2006.24(2:1711763Yanjun Li,Soon M.Chung.Parallel bisecting k-means with prediction clustering algorithmJ.Journal of Grid Computing,2007.39:19374岳士弘,王

18、正友.二分网格聚类方法及有效性J.计算机研究与发展,2005.42(9:150515105曾蒙福,马亨冰.一种自适应网格聚类算法的研究J.福建电脑,2006.3:1051066Pilevar,A.H.Sukumar.A grid-clustering algorithm for high-dimen-sional very large spatial data basesJ.M.Pattern Recognition Letters,2005.26(7:9991011 以保证数据的一致性,是数据库系统可靠性的基石。数据库的增删改都会通过事务方式来完成。在混合引擎中,应很好地将事务机制与倒排列表的修改融合起来,使得对文本倒排索引的修改是可控的且结构化数据保持一致。对于关键任务的应用来说,容错与恢复也是很重要的特性。这也对IR 中倒排索引的更新与修改提出了更高的要求。事务失