层次聚类算法的改进及分析

层次聚类

第25卷第6期　　　2008年6月　　计算机应用与软件

ComputerApplicationsandSoftwareVol125No.6Jun.2008

层次聚类算法的改进及分析

郭晓娟　刘晓霞　李晓玲

12

112

(西北大学　陕西西安710127)

(中国地质大学　湖北武汉430074)

摘　要　　层次凝聚算法是一个非常有用的聚类算法,它在迭代地凝聚每次接近对直到所有的数据都属于同一个簇。但层次聚类

也存在着几个缺点,如聚类时的时空复杂性高;聚类的簇效率低、误差较大等。经验研究表明,大部分HAC算法都有这样一个趋势:除了在谱系图的顶层,所有低层聚类的簇都是比较小的并且很接近于其他的簇,提出了一种改进算法能够减小时空复杂性并能验证其正确性,分析与实验都证明这种方法是非常有效的。关键词　　聚类　层次聚类　谱系图　簇　POP

ONIMPROVEMENTANDANALYSISOFHIERARCHICALCLUSTERIALGORITHM

GuoXiaojuan　LiuLi12

1(NorthwestUniversity,XiChina)

(ChinaUofuhan)

Abstract　　Aprominentandisomerativeclustering(HAC)whichiterativelyagglomeratestheclo2sestpareuntilallHACmethodshaveseveraldrawbacks,suchashightimeandmemorycomplex2itieswheninaccurateclustervalidation,etc.EmpiricalstudyshowsthatmostHACalgorithmsfollowatrendwhere,exceptforanuoftoplevelsofthedendrogram,alllowerlevelagglomerateclustersareverysmallinsizeandcloseinproximitytootherclusters.Methodsareproposedtoreducethetimeandmemorycomplexitiessignificantlyandtomakevalidationveryefficientandac2curate.Analysisandexperimentsallprovetheeffectivenessoftheproposedmethod.Keywords　　Clustering　HAC　Dendrogram　Cluster　POP

0　引　言

随着数据挖掘研究领域技术的发展,作为数据挖掘主要方法之一的聚类算法,也越来越受到人们的关注。数据挖掘(DataMining)又称知识发现(KDD),其实是知识发现过程的一个步骤.它是从数据库、数据仓库或其他信息库中便捷地抽取出以前未知的、隐含的、有用的信息,所挖掘出来的知识可应用于信息管理、决策支持、过程控制和其它许多应用。所谓聚类(Clustering),就是把大量的d维数据样本(n个)聚集成k个类(k,n),使同一类内样本的相似性最大,而不同类中样本的相似性最小。聚类分析作为数据挖掘中的一种分析方法,它可以作为一个单独的工具以发现数据库中数据分布的一些深入的信息。并且概括出每一类的特点,或者把注意力放在某一个特定的类上以作进一步的分析;聚类分析也可以作为数据挖掘算法中其他分析算法的一个预处理步骤。目前已经提出很多的聚类算法[1]。

空复杂性,例如,对于质心点算法(优先队列法),其时间复杂性为:O(N2logN),虽然可以将HAC应用于大量数据中,一些技术被用到诸如BIRCH[3]和CURE[4],但它们都不能加快传统的HAC算法,在使用最近点且保证正确性前提条件下减少计算量。2)用谱系图获得簇的有效性是有限的。簇的有效性主要用来决定在大型数据量中最优簇的数目。并且,很多有效性方法对谱系图的低层显示出转移模式,这就会导致评估不出不精确的最优簇数。

2　改进算法及其分析过程

经验表明,除了谱系图的一些高层,所有低层聚类的簇既小而且与其他簇也非常接近。我们可称此特性为90-10规则,它难以被很小距离分开的小簇合并。基于90-10规则,我们提出了快速HAC算法,它能有效地减少已存在HAC算法的时空复杂性。在本文中,90-10规则用来改进已存在簇方法的有效性与正确性。90-10规则就是能有效地丢弃不需要的层,聚集潜在的层。所以它能减少计算量,改进被转移模式所避免的正确性。

收稿日期:2006-07-21。郭晓娟,硕士生,主研领域:网络信息处理,数据挖掘。

1　传统的层次凝聚算法

[2]

及其局限性

HAC算法在簇对象中是很简单的,它能用类似的方法找出

不同形状的簇,但HAC也存在着一些缺点:1)HAC有很高的时