改進(jìn)的聚類分析算法及其性能分析(1)

1、Computer Era No.820100引言K-均值是目前應(yīng)用最為廣泛的聚類分析算法之一,是解決聚類問題的經(jīng)典算法,然而K-均值具有人為確定k值、過分依賴k初始聚類中心點(diǎn)的缺點(diǎn),而且運(yùn)算量大,效率不高。目前對(duì)于K-均值算法的改進(jìn)也有很多種,比如基于遺傳算法的K-均值1、引入懲罰因子的K-均值2、PBKP算法3等。網(wǎng)格聚類算法的效率非常高,而且可以發(fā)現(xiàn)任意形狀的簇,但是網(wǎng)格聚類也存在種種的缺陷,比如依賴于密度閥值的選擇等。目前對(duì)于網(wǎng)格聚類的改進(jìn)算法也有很多,比如二分網(wǎng)格聚類4、自適應(yīng)網(wǎng)格聚類5、GCHL6等。本文針對(duì)上述算法的缺點(diǎn),結(jié)合他們的優(yōu)點(diǎn)提出一種改進(jìn)的聚類分析算法融合聚類分析算法。1

2、融合聚類分析算法1.1算法的基本概念設(shè)A=(D1,D2,D n是n個(gè)有界定義域,S=D1×D2××D n是一個(gè)n維空間,我們將D1,D2,D n看成是S的維。算法的輸入則是一個(gè)n維空間的點(diǎn)集,設(shè)為V=v1,v2,v n,其中v1=v i1,v i2,v in代表第i個(gè)點(diǎn),v ijD j表示第i個(gè)點(diǎn)的第j維的分量。定義1網(wǎng)格單元:不妨設(shè)第i維上的分布點(diǎn)取值在區(qū)間l i,h i中,i=1,2,n,將每一維分成p個(gè)不相交的左閉右開的等長(zhǎng)區(qū)間,這些區(qū)間就稱為網(wǎng)格單元。這樣,數(shù)據(jù)空間被分割成p n個(gè)網(wǎng)格單元,網(wǎng)格單元在第i 維上的長(zhǎng)度為,第i維上的第j 個(gè)區(qū)間段可由式得出。

3、定義2網(wǎng)格單元密度:網(wǎng)格單元C i的密度Den(C i定義為該網(wǎng)格單元中的數(shù)據(jù)點(diǎn)的個(gè)數(shù)。定義3密集單元與自由數(shù)據(jù):設(shè)定密度閥值為Minpts,將密度大于密度閥值Minpts的網(wǎng)格定義為密集單元,將密度小于密度閥值的單元中的數(shù)據(jù)稱為自由數(shù)據(jù)。定義4聚類重心:給定簇K i=(t i1,t i2,t im,則其均值即聚類 重心定義為其中n i為簇K i中對(duì)象的個(gè)數(shù),x,y為簇K i中的兩兩不同的對(duì)象。定義5中間聚類:對(duì)樣本空間進(jìn)行劃分,定義單元網(wǎng)格集,計(jì)算網(wǎng)格單元的密度,將密度密集的單元進(jìn)行網(wǎng)格聚類,這一過程叫中間聚類。中間聚類只包含分布比較密集的點(diǎn),并不包含全部的聚集對(duì)象,中間聚類生成的簇叫中間聚

4、類簇。定義6后聚類:中間聚類結(jié)束后,計(jì)算每個(gè)中間聚類簇的中心作為初始中心點(diǎn),然后對(duì)剩余的自由數(shù)據(jù)進(jìn)行k-means聚類,這一過程叫做后聚類,所產(chǎn)生的簇叫做后聚類簇。1.2算法的基本思想首先基于網(wǎng)格聚類分析的思想,對(duì)樣本空間進(jìn)行劃分定義網(wǎng)格單元集,將對(duì)象映射到相應(yīng)的網(wǎng)格單元中,計(jì)算網(wǎng)格單元的密度,標(biāo)記密度大于密度閥值的單元和密度小于密度閥值的數(shù)據(jù),由鄰近的密集單元合并形成“中間聚類簇”(中間聚改進(jìn)的聚類分析算法及其性能分析郭書杰,吳小欣,黃杰(91550部隊(duì)指控中心,遼寧大連116023摘要:提出了一種改進(jìn)的聚類分析算法,該算法采用類似中間聚類與最終聚類分布的思想,先對(duì)密集區(qū)域進(jìn)行聚類,形成了K

5、個(gè)聚類,然后再對(duì)相對(duì)分散的自由數(shù)據(jù)進(jìn)行K-means聚類,使聚類分析在迭代過程中始終沿著最優(yōu)的方向進(jìn)行,減小了迭代次數(shù),提高了收斂速度。該算法融合了網(wǎng)格聚類與K-均值聚類的優(yōu)點(diǎn),并且引入了一種新的劃分網(wǎng)格的算法和新的計(jì)算密度閥值的函數(shù)。理論分析以及實(shí)驗(yàn)證明,改進(jìn)算法的聚類過程達(dá)到了令人滿意的效果。關(guān)鍵詞:聚類分析;K-均值算法;網(wǎng)格聚類;融合聚類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計(jì)算機(jī)時(shí)代2010年第8期類簇并不包含比較離

9、散的自由數(shù)據(jù);計(jì)算中間聚類簇的重心作為初始聚類中心點(diǎn),計(jì)算自由數(shù)據(jù)到每個(gè)聚類中心的距離,將自由數(shù)據(jù)分配到最近的中間聚類中,形成“后聚類簇”;重新計(jì)算每個(gè)后聚類的初始聚類中心,若無變化則算法終止,若有變化則重新進(jìn)行聚類,直到滿足條件完成聚類。網(wǎng)格定義本身就是一個(gè)難題,網(wǎng)格大小與放置對(duì)于聚類的結(jié)果具有很大的影響,如何劃分網(wǎng)格對(duì)于算法非常重要。在融合算法中,引入了一種新的函數(shù)用于網(wǎng)格的劃分:式中,l i 為第i 分量的長(zhǎng)度,i=1,2,n。同時(shí),基于網(wǎng)格的聚類非常依賴于密度閥值的選擇,過大或者過小都會(huì)影響算法的性能。在融合算法中,對(duì)于密度閥值的確定,提出了一種新的算法: 式中Den(C i ,i=1

10、,2,N 為密度最高的N 個(gè)密集單元的密度值,N 的值視具體的數(shù)據(jù)而定。一般情況下將Den(C i 降序排列,如果Den(C i 與Den(C i+1發(fā)生明顯跳變,則N=i。1.3算法的步驟根據(jù)1.2節(jié)算法基本思想的描述,算法的基本步驟如下。step 1:將數(shù)據(jù)空間劃分為m 個(gè)不相交、等長(zhǎng)的網(wǎng)格單元,定義網(wǎng)格單元集;step 2:將對(duì)象指派到合適的單元中;step 3:計(jì)算每個(gè)單元的密度;step 4:將密度大于密度閥值Minpts 的網(wǎng)格標(biāo)記為“密集單元”,將密度小于密度閥值的單元中的數(shù)據(jù)標(biāo)記為“自由數(shù)據(jù)”;step 5:反復(fù)任選一未被聚類的密集單元,將其和與之相鄰的密集單元合并為一簇,直至

11、所有密集單元均被聚類,形成K 個(gè)“中間聚類”;step 6:計(jì)算這K個(gè)中間聚類的重心,作為初始聚類中心; step 7:反復(fù)任選一自由數(shù)據(jù)對(duì)象,計(jì)算其與k 個(gè)初始聚類中心的距離dis(x,C i ,其中x 為自由數(shù)據(jù)對(duì)象,C i 為第i 個(gè)類,若dis(x,C i 最小,則xC i ,直至不再存在自由數(shù)據(jù),形成“后聚類”;step 8:重新計(jì)算后聚類的重心,若 則聚類結(jié)束,否則繼續(xù)進(jìn)行K-均值聚類,直到完 成聚類。2融合聚類算法的性能檢驗(yàn)與分析2.1時(shí)間復(fù)雜度分析在本算法中,定義網(wǎng)格、將數(shù)據(jù)的對(duì)象映射到網(wǎng)格中并且計(jì)算網(wǎng)格密度,這一過程的時(shí)間復(fù)雜度為O(n,n 為點(diǎn)的個(gè)數(shù);對(duì)于每個(gè)密集單元,檢查

12、所有與它相關(guān)聯(lián)的密集單元生成簇,假設(shè)密集單元的總個(gè)數(shù)為m',與一個(gè)密集單元相關(guān)聯(lián)的單元數(shù)最大值為2d,則這個(gè)過程的時(shí)間復(fù)雜度為O(2d×m'。后聚類的時(shí)間復(fù)雜度為O(k×t×n',其中t 是迭代次數(shù),n'是自由數(shù)據(jù)的個(gè)數(shù)。在本算法中,由于已經(jīng)對(duì)數(shù)據(jù)集進(jìn)行了基于密度和網(wǎng)格的中間聚類處理,使得中間聚類中心與最終聚類中心分布類似,這樣對(duì)于自由數(shù)據(jù)進(jìn)行K-均值聚類,需要的迭代次數(shù)就會(huì)很小,相對(duì)的時(shí)間也會(huì)大大縮短。從以上的分析來看融合算法總的時(shí)間復(fù)雜度最大時(shí)為O(n+O(2d ×m'+O(k×t×n,整個(gè)

13、聚類過程所需要的時(shí)間與數(shù)據(jù)集中的數(shù)據(jù)點(diǎn)數(shù)成線性關(guān)系,與維數(shù)成指數(shù)關(guān)系,總體來講融合聚類在時(shí)間上是高效的。2.2試驗(yàn)結(jié)果對(duì)比實(shí)驗(yàn)的樣本數(shù)據(jù)使用了著名的鳶尾花(Iris 數(shù)據(jù)集,該數(shù)據(jù)集可以從加州大學(xué)歐文分校的機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中得到。該數(shù)據(jù)集包括3類花的4個(gè)特性:萼片寬度、萼片長(zhǎng)度、花瓣寬度、花瓣長(zhǎng)度,共150條紀(jì)錄。首先,對(duì)比融合算法與網(wǎng)格聚類算法的聚類結(jié)果。使用GB 算法對(duì)數(shù)據(jù)進(jìn)行聚類,得到的結(jié)果如圖1所示。1GB 的聚類結(jié)果從圖1我們可以看出,網(wǎng)格聚類的結(jié)果丟失了很多點(diǎn),聚類結(jié)果不能令人滿意。這是由于基于網(wǎng)格的聚類只處理高密度區(qū)域,低密度區(qū)域會(huì)被丟棄,造成簇的丟失。但是使用融合聚類得到的結(jié)果(

14、如圖2所示要比網(wǎng)格聚類的結(jié)果好很多。2融合的聚類結(jié)果接下來,對(duì)比融合聚類算法的聚類結(jié)果與K-均值聚類算法的聚類結(jié)果。利用融合聚類算法進(jìn)行多次試驗(yàn),聚類的過程經(jīng)歷了中間聚類、后聚類、1次迭代后便結(jié)束聚類,共得到3類。每個(gè)類的初始中心在每個(gè)聚類階段的值如表1所示。··5Computer Era No.82010表1融合聚類結(jié)果類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給出了該次聚類過程中聚類中心變化的折線圖。圖中每個(gè)類的聚類中心在每個(gè)階段變化都不大,且迅速地收斂,這說明融合聚類算法得出的密集單元很好地模擬了數(shù)據(jù)集合中密集區(qū)域的分布,很快地確定了K 個(gè)初始聚類中心點(diǎn),然后又利用K

16、-均值聚類將自由數(shù)據(jù)重新聚類,可以快速有效地完成聚類。3融合的初始聚類中心利用K-均值聚類對(duì)Iris 數(shù)據(jù)進(jìn)行多次實(shí)驗(yàn)得到的結(jié)果,從初始聚類中心到最終聚類中心變化都很大。如圖4所示,在該次聚類過程中,K-均值算法很隨機(jī)地抽取了3個(gè)點(diǎn)作為初始聚類中心,由于不能很好地捕獲自然聚類的中心,算法不斷地尋找更優(yōu)的初始聚類中心,總是不斷變化著聚類中心,使得算法不能很快收斂,算法的迭代次數(shù)也明顯增加到11次。4K-means 的初始聚類中心綜上所述,我們可以看出,基于凝聚度和分離度的簇的性能評(píng)估,融合算法要優(yōu)于K-means 算法。3結(jié)束語本文所提出的融合聚類分析算法,取得了很好的實(shí)驗(yàn)結(jié)果。但算法仍然存在著

17、不足之處,比如合適的密度閥值的選擇比較困難等,這些因素會(huì)影響到算法的性能,這也是今后需要我們繼續(xù)研究和改進(jìn)的地方。參考文獻(xiàn):1王敞,陳增強(qiáng),袁著祉.基于遺傳算法的K-均值聚類分析J.計(jì)算機(jī)科學(xué),2003.30(2:1631642王紅睿,趙黎明,裴劍.均衡化的改進(jìn)均值聚類法J.吉林大學(xué)學(xué)報(bào)(信息科學(xué)版,2006.24(2:1711763Yanjun Li,Soon M.Chung.Parallel bisecting k-means with prediction clustering algorithmJ.Journal of Grid Computing,2007.39:19374岳士弘,王

18、正友.二分網(wǎng)格聚類方法及有效性J.計(jì)算機(jī)研究與發(fā)展,2005.42(9:150515105曾蒙福,馬亨冰.一種自適應(yīng)網(wǎng)格聚類算法的研究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 以保證數(shù)據(jù)的一致性,是數(shù)據(jù)庫(kù)系統(tǒng)可靠性的基石。數(shù)據(jù)庫(kù)的增刪改都會(huì)通過事務(wù)方式來完成。在混合引擎中,應(yīng)很好地將事務(wù)機(jī)制與倒排列表的修改融合起來,使得對(duì)文本倒排索引的修改是可控的且結(jié)構(gòu)化數(shù)據(jù)保持一致。對(duì)于關(guān)鍵任務(wù)的應(yīng)用來說,容錯(cuò)與恢復(fù)也是很重要的特性。這也對(duì)IR 中倒排索引的更新與修改提出了更高的要求。事務(wù)失