第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有很高的时
2.1 算法的基本思想
我们提出基于部分重叠划分POP(PartiallyOverlappingPar2titioning)的改进HAC算法。下面来具体分析一下基于POP的一种新算法———两阶段算法。两阶段算法:在POP基础上对HAC算法提出一个新的两阶段算法。第一个阶段,数据被分配到P个重叠的单元,这个重叠的区域称作δ区域,其中δ是分离的距离。对于质心点算法来讲,每个簇都用单一的代表点表示,如果一个簇的代表点落在δ区域,那么每一个受影响的单元都可捕获它并保存,否则,只有一个单元可以获取到它。基于POP的思想,在每一次迭代过程中,从已发现的全部最近点对中为每个单元找出最接近的点对。如果所有这些最近点对的距离小于δ,那么合并这些点对,并且更新被包含单元中的优先队列。如果最接近点对或合并的簇在δ区内,那么所有受影响的单元都会更新其优先队列。当最远点对距离超出δ时,每一阶段终止。第二个阶段利用传统的聚类算法合并第一阶段余下的簇。这样就以得到一个谱系图。
明β+1对于所有测试数据集而言是小的,它小于2。
原始的质心点算法采用互异矩阵代替了优先队列,并且还没有保留最近邻居。它的时间复杂度为O(N3),空间复杂度为O(N2),如果采用两阶段算法,那么时间复杂度就会变为:O((N-3
)3(β+1)3(n/p+|δ|)2)+O(k′),空间复杂度为O(p3k′
2
(N/p)+|δ|2)或O(k′)或者两者中较大的。注意,在这个例子中,受影响单元的平均数不是因子,这是因为全部的复杂度是由于需要通过互异矩阵进行搜索需要二次的时间量。经过简化(没
)时间复杂度为O(N3p3(N2/p2)),即O(N3/有考虑|δ|与k′
2
p),获取因子为p。空间复杂度为O((N/p))(获取因子为p)。
2.2 改进算法的实现及时空复杂度
这个算法如下所示。通过对距离图中转折点的最近距离对设置δ,可以在第一阶段合并大量的簇,在第二阶段利用传统HAC算法合并剩余的小量的簇。
Input:Data(N,M),p,δOutput:Dendrogram/3第一阶段3/
按照Anderberg[6]的分类法,上面两种算法都采用矩阵存储的形式,传统的数据存储形式为最近邻居数组,它的时空复杂度分别为:O(a3N2),O(N),其中a是每次迭代更新次数。但是,当使用两阶段算法去存储数据时,它的时间复杂度为:O((β
2
)3a3((N/p)+|δ|))+O(a3k′),简化之后+1)3(N-k′
的时间复杂度为O((β+1)3a3(N2/p)),获取因子为:(p/β+
)简化后为O1),空间复杂度为O(p3(N/p)3)|δ|)或O(k′
(N),获取因子为1。如表1所示。
表1 相似矩阵
O(N3)
2
获取因子
O(N3/p)
2
pp/(β+1)
将数据分配到Do
优先队列O(NlogN)((β+1)3(N/p)log(N/p)log(N/p)N3P/(β+1)存储数据O(a3N2)O((β+1)3a3(N2/p))
空间复杂度存储矩阵相似矩阵优先队列存储数据
O(N2)O(N2)O(N)
O((N2/p))O((N2/p))O(N)
pp1
,确定全部的最接近点对(C1,C2)Ifdist(C1,C2)
合并C1和C2同时更新相应的P队列;更新所有受影响单元的P队列While(dist(C1,C2)>δ)
/3第二阶段3/
利用传统聚类算法合并第一阶段剩余的簇
Return谱系图
3 结束语
实验表明,利用改进的HAC算法可以有效地减少传统HAC算法的时空复杂度。应用改进的HAC算法可以发现自然的簇,一般的HAC算法通常不能发现自然的簇,这就像文献
[7]
[7]所指出的那样。Chameleon是基于内部对象间的互连性和近似度一致类似性的算法,它也是一个两阶段的算法,在每阶段,数据被分到很小的簇中,第二阶段利用一致相似性合并这些小簇。一般而言,合并簇所需时间要小于分裂簇所需时间[8],利用改进的HAC算法,我们可以决定在距离图转折点上何时终止合并过程,在那些点上的簇,可以作为Chameleon算法第二阶段的输入,以利于发现更自然的簇。
2.3 改进算法的分析
精确性分析 关于第一阶段使用POP能够确保任意小于δ的距离对都能保留在至少一个单元中,第二阶段使用传统聚类算法,两阶段算法能够保证正确的谱系图。
复杂性分析 为简化这个分析,先假设每个单元有相同的单元大小,相同的δ域大小。|δ|主要是用来表明任意特殊单元δ域中的簇数。最初由Day和Edelshrunner[5]提出的优先队列算法的时间复杂度为:O(n2logN),O(N2),相反,所提出的两阶段算
)3(β+1)3(n/p+|δ|))。log法,它的时间复杂度为O((N-k′
(n/p+|δ|)要远远大于P,并且β是在每次迭代中受影响单元
2
)或的平均数。空间复杂度是:O(p3(n/p+|δ|)2)或者O(k′
是两者中较大的。如果δ设置为距离图中转折点的最近对距离,那么|δ|和k′都是非常小的,因此,如果没有考虑|δ|与k′,时间复杂度就变为:O(N3(β+1)3(N/p)log(N/p)),即O((β+
2
β+1)),空1)3(N/p)log(N/p))(获取因子为log(N/p)N3(P/
间复杂度为:O(p3(N23p2)),即O((N2/p))(获取因子为p)。
容器中所包含受影响单元的平均数为β+1,这个值主要依赖于数据是如何分配的:在最坏情况下,对于M维数据而言,每次聚类受影响单元的最大可能数为2M,在最好情况下,每次聚类受影响的仅仅是容器本身中的单元,那么这个值仅为1。经验表
参
2232260.
考文献
[1]范明,孟小峰,等.数据挖掘概念与技术.机械工业出版社,2001:[2]郭崇慧,田凤占,靳晓明,等.数据挖掘教程.清华大学出版社,
2005:1072138.
[3]ZhangT,RamakrishnanR,LivnyM.BIRCH:Anefficientdatacluste2
ringmethodforverylargedatabases.In:ProceedingsofACMSIGMODConferenceonManagementofData,Montreal,Canada,June1996:1032114.
(下转第268页)
第12个小块发生了变化
。
网络具有快速处理某些任务的潜在能力。而对于这种基于两层前馈网络的分组密码体制来说,其加密网络和解密网络的结构基本相同,可以采用相同的神经网络芯片同时实现加/解密功能。随着神经网络芯片的进一步研究和大规模应用,该分组密码的加/解密处理速度将大大加快,系统的成本也将随之降低。可见该分组密码体制也是易于用硬件实现的。
6 结 论
作为信息安全技术的核心技术,密码技术在保密通信中发
图7 加密密钥K2E对密文C的扩散程度
挥着不可替代的重要作用。本文基于多层前馈神经网络的特性和分组密码的设计原则,设计了一种分组密码体制,并用一个两层前馈网络具体实现了该分组密码体制。通过仿真,说明了该分组密码体制是可行的;理论分析和实验结果说明了该分组密码体制具有较高的安全性,具有很好的混乱特性和扩散特性;与
DES的比较进一步表明该分组密码体制具有较高的安全性,并
综上所述,从总体上说,这种分组密码体制的扩散特征比较明显。
5 该分组密码体制与DES的比较
尽管DES已经走完它的生命历程,但它作为分组密码的成功范例,在密码学的发展史上仍然具有十分重要的地位,下面将该分组密码体制与DES进行比较。
易于实现。
.[J].通信学报,2002,
[]FE.OnNeurocrytology[C].ParallelArchitecturesandNeural
Networks.ThirdItalianWorkshop.WorldScientic,Singapore,1990(5):3372343.
[3]LauriaFE.Non2linguisticNeurocrytologyandtheShannontheorem
[M].M.Marinaro&G.Scarpettaeds.,Structures:fromPhysicstoGeneralSystems[J].WorldSc,1992(2):2382244.
[4]杜生辉,阮传概.用感知器构造分组密码[J].密码与信息,1994
(1):24231.
[5]章照止,杨义先,马晓敏.信息理论密码学的新进展及研究问题
[J].电子学报,1998(7):9218.
[6]齐锐,张大力,阎平凡.基于神经网络的对称密码系统[J].清华大
5.1 加密强度的比较
DES的密钥长度为56位,位,2机软、能力和Internet用穷尽密钥搜索攻击方法破译DES已成为可能。出于安全性的考虑,美国的国家标准与技术研究所于2001年11月26日正式公布了新标准AES,其密钥长度为128/193/256位,具有更大的穷举密钥空间。由此可见,密钥的长度对密码体制的安全性有重要的影响。
在1.3.2中,讨论了这种基于两层前馈网络的分组密码体制的加密强度,从理论上说,该体制对于穷尽密钥搜索攻击是无条件安全的。在实际应用中,加密密钥K2E中的元素ki,j(i,j=0,
1,…,N-1)可以都取整数(即ki,j∈Z),通过对参数M和N设
学学报:自然科学版,2001,41(9):89293.
[7]ShannonCE.CommunicationTheoryofSecrecySystems[J].BellSys2
temTechnicalJournal,1949,28(4):6562715.
置不同的值,来达到不同的加密强度以满足不同的需求。例如,当M=4,N=5时,密钥KE和KE的总长度为120位;当M=4,N
=6时,密钥总长度为168位;当M=4,N=8时,密钥总长度为288位。随着M和N的增大,密钥总长度也随之增加,造成理
1
2
(上接第244页)
[4]GuhaS,RastogiR,ShimK.CURE:Anefficientclusteringalgorithm
forlargedatabases.In:ProceedingsoftheACMSIGMODInternationalConferenceonManagementofData,1998:73284.
[5]DayWHE,EdelsbrunnerH.Efficientalgorithmsforagglomerativehi2
erarchicalclusteringmethods.JournalofClassification,1984(1):7224.
[6]AnderbergMR.ClusterAnalysisforApplications.AcademicPress,
NewYork,1973.
[7]KarypisG,HanEH,KumarV.CHAMELEON:ahierarchicalclustering
algorithmusingdynamicmodeling.IEEEComputer,1999,32:68275.[8]DudaRO,HartPE.PatternClassificationandSceneAnalysis,chap2
ter:UnsupervisedLearningandClustering.JohnWiley&Sons,1973.[9]DashM,HuanL,ScheuermannP,TanKL.Fasthierarchicalclustering
anditsvalidation.Data&KnowledgeEngineering,2003,44:1092138.
论上的穷举密钥空间也越来越大。
5.2 功能实现的比较
由于DES属于成熟的分组密码算法,所以有大量的实现
DES的高效硬件和软件。
如果用软件实现,这种基于两层前馈网络的分组密码体制可以使用子块和简单的运算。通过对参数M和N设置不同的值,使得分组(或分组中的子块)的长度能自然地适应软件编程,比如8、16和32比特等。子块上进行的运算(比如加法、乘法等)也都是一些标准处理器所具有的基本指令。可见该分组密码体制是易于用软件实现的。
再考虑用硬件实现的情况。神经网络的大规模并行性使得它很适合用VLSI技术实现,VLSI的一个特殊优点是提供一个以高度分层的方式捕捉真实复杂性行为的方法,这就使得神经