可變網格優化的K-means聚類方法

萬 靜,張 超,何云斌,李 松

(哈爾濱理工大學 計算機科學與技術學院,哈爾濱 150080)

1 引 言

聚類分析是數據挖掘的重要組成部分,已經被廣泛地應用到了很多領域,包括web搜索,圖像分割[1],生物學[2]等.聚類是一種無監督學習,即沒有提供類標號信息.到目前為止,主要的聚類方法分如下幾類:基于劃分的方法,基于層次的方法,基于密度的方法,基于網格的方法,基于模型的方法等.

k-means聚類算法是數據挖掘中最經典的算法之一,該聚類算法操作簡單,對高維數據集[3],大數據集的處理上有較高的伸縮性,而且速度快.但是傳統的k-means算法也存在一些缺點:

1)需要人為指定聚類數k,這需要有一定的經驗.

2)對聚類初始中心的選取比較敏感,容易受到噪聲的影響,也容易收斂到局部最優解.

3)只能發現球狀簇.針對以上的不足,國內外許多學者從不同的角度對k-means算法進行了改進.

在對最佳聚類數的獲取方面,文獻[4]提出一種基于k-means和粒度原理的改進的模糊C均值算法,提高了聚類的有效性,但是對大數據的處理效率比較低.文獻[5]提出了一種最小最大k-means算法,該算法通過給聚類分配權重與迭代,解決了聚類初始化問題,但是容易受到噪音的影響.文獻[6]根據傳統的k-means算法和核函數,解決了非凸問題,從而得到了最佳聚類數,時間復雜度較低,對處理大規模數據集更高效.文獻[7]提出一種快速生成最小樹算法,所提出的算法采用分而治之方法,該算法提高了聚類質量,不足之處是算法復雜度較高.

此外,在對初始中心點的選取方面,文獻[8]提出一種新的初始簇中心迭代算法,啟發式地選擇簇初始中心,得到了較好的聚類結果,有很好的穩定性,但處理高維數據集效果欠佳.文獻[9]用Hilbert空間和Tikhonov正則理論結合k-means算法來減小數據的維度,得到了較好的效果.文獻[10]提出一種改進初始聚類中心選擇的算法,該算法利用距離最大的兩個數據對象作為開始的聚類中心對該聚類進行分裂,如此反復,直到得到指定聚類中心個數,對處理大數據集效果不好.

針對k-means算法選取聚類中心點不具有代表性的缺點,同時為了彌補k-means算法只能發現球狀簇的不足,為此,本文提出了基于可變網格劃分的k-means聚類方法.

2 基于可變網格的k-means聚類算法

所謂可變網格劃分就是對原始數據集的每一維進行等深劃分,然后計算相鄰區間段的密度,對密度相似的區間段進行合并,形成可變的網格劃分.在劃分后的網格中,每一維上的區間段個數不相同,而且區間段的長度也不一定相同.可變網格劃分克服了固定網格劃分在處理高維數據集時的缺點,可變網格劃分根據數據分布的特點進行靈活劃分,極大的減少了網格數量,增加了效率.

2.1 相關定義

定義1.(相鄰區間段)網格劃分中,有共同邊界的區間段稱為相鄰區間段.

定義2.(等深劃分)已知k維數據集D包含N個數據點,設第i維被分為q個區間,則劃分結果為每個區間段包含[N/q]個數據點.

定義3.(區間段密度)[11]已知每個區間段包含相同數目的數據點,第i維的第j段區間段表示為:Sij=(d(i)([N/q]*(j-1)+1),d(i)([N/q]*j)),d(i)(j)表示第i維的第j個元素值.則區間段密度可以用區間段的長度來衡量,即|Sij|=(d(i)([N/q]*j)-d(i)([N/q]*(j-1)+1)).

定義4.(高密度網格與低密度網格)如果一個網格區間段密度大于給定的密度閾值,則稱這個網格為高密度網格,否則稱為低密度網格.

定義5.(噪聲數據)如果一個網格與它相鄰的網格都是低密度網格,則可以把它看成噪聲數據.

定義6.(相鄰區間段的密度相似性ρ)[11]已知第i維的第j段區間段密度|Sij|與其相鄰的第j+1段區間段密度|Si(j+1)|.若|Sij|<|Si(j+1)|,則ρ=|Sij|/|Si(j+1)|,否則,ρ=|Si(j+1)|/|Sij|,其中,0<ρ<1.

定義7.(密度閾值)設數據集D,總共有m個網格,第i個網格的密度為Dens(xi),則網格的密度閾值為

(1)

2.2 基于可變網格的k-means聚類算法描述

基于可變網格的k-means聚類算法主要思想為:首先用可變網格方法劃分數據集,并與密度閾值相比較,選出大于密度閾值的網格,消除了孤立點的影響,然后對大于密度閾值的網格進行k-means聚類,最后根據距離越遠聚類效果越好的原則選出最優的聚類結果.

基于可變網格的k-means聚類算法的具體過程為:首先將數據集D的每一維用快速排序法進行升序排序,再等深劃分各維數據,計算相鄰區間段的相似度ρ并與相似度閾值v進行比較,如果ρ>v,則相鄰區間段進行合并,否則不合并,遍歷所有區間段,得到合并后的結果.然后,根據|Sij|=(d(i)([N/q]*j)-d(i)([N/q]*(j-1)+1))計算合并后網格的密度并將結果記錄到集合c中,根據網格密度,計算網格密度閾值t,并將大于密度閾值的網格密度結果放入集合d中,對d中的網格用k-means聚類方法進行網格聚類,輸出最優的聚類結果.

基于以上討論,給出基于可變網格的k-means聚類算法,具體算法如算法1所示.

算法1.VGOk-means()(基于可變網格的k-means聚類)

輸入:含N個對象的數據集D,期望劃分的聚類數k,相似度閾值v;

輸出:最優聚類結果;

Begin

1.初始集合c={},d={},e={};

2.for(j=1 toi){

3.Dj←Sorting(Dj)};/*對數據的每一維采用快速排序法排序*/

4.Mj←Divide(Dj);/*等深劃分各維數據*/

5.|Sij|←Computer_dens(d(i)([n/q]*j)-d(i)([n/q]*(j-1)+1));/*計算區間段密度*/

6.ρ←Computer_similarity(|Sij|/|Si(j+1)|);/*計算各維相鄰區間相似度*/

7.If (ρ>v){

8.Mi←Merge(Mi,Mi+1);}/*將滿足條件的相鄰區間段進行合并*/

9.Mi←iterate over _merge(Dj);/*循環遍歷數據集D的每一維,將滿足條件的區間合并*/

10.Dens(Mi)←Computer_dens[Dens(Mi)];/*根據(2)式,計算合并后網格的密度*/

11.c=c∪Dens(Mi);/*將計算的網格密度放入集合c中*/

12.Computer_min_DensThreshold(t);/*根據③式,計算最小密度閾值*/

13.If(Dens(Mi)>t){

14.d=d∪Mi;}/*將大于密度閾值的類簇放入集合d中*/

15.e←Use_k-means(d);/*用k-means聚類方法對d中高密度網格進行聚類,結果放入集合e中*/

16.Output cluster(e);/*輸出最優聚類結果*/

End

3 基于最大網格密度不唯一的k-means算法

本節研究最大密度不唯一時的網格中心點選取方法.本節提出的新方法結合密度的概念,選取高密度網格中的代表點作為初始中心點,用網格中數據點數比網格的長度來計算網格的密度.在k個高密度網格中分別選擇一個代表點作為初始中心點.這樣選擇有利于消除孤立點被選為初始中心點的可能,降低了孤立點對聚類的影響.

3.1 相關定義和規則

定義8.(網格類簇的密度)設n維數據集D,對于每一維數據,用網格中數據點數比區間段長度表示最終網格類簇的密度,即:

Dens(xi)=Ni/Li

(2)

其中,Ni表示該網格中數據的總個數,Li表示該網格的長度.

定義9.(最小密度閾值minDens)為了消除孤立點的影響和減少算法的計算,設定了最小密度閾值,

(3)

該值為類簇選取的下界值,除去了密度較低的點,保證選取的類具有代表性.

規則1.(最大密度不唯一網格選取規則)當網格的最大密度不唯一時,則對每一個最大密度網格進行聚類,最后比較聚類中心點距離之和,選出距離和最大的一組為最優聚類結果.

3.2 基于最大網格密度不唯一的k-means算法描述

基于最大網格密度不唯一的k-means算法的主要思想為:首先根據可變網格劃分對數據進行網格劃分處理,然后用k-means方法進行聚類,當出現最大網格密度不唯一的情況,分別對每個最大密度網格進行聚類,找到與之對應的一組最優聚類,最后比較各組類簇的距離之和,輸出最優的聚類結果.

算法的具體過程為:首先根據可變網格劃分將數據每一維進行等深劃分,計算各相鄰區間的相似度,如果相似度大于給定閾值,相鄰區間進行合并,否則不合并,直到遍歷完所有的維.然后計算合并后的網格密度,將大于最小密度閾值的網格放入一個集合中,從密度最大的網格開始,尋找離它最遠的類,以此類推,直到找到k個類為止.如果最大密度網格不止一個,則將這些最大網格密度放入另一個集合中,分別以這些最大密度網格為中心聚類,最后比較各聚類的距離之和,距離之和最大的一類即為最優聚類結果.

基于最大網格密度不唯一的k-means算法的算法描述如算法2所示:

算法2.NMGDk-means()(基于最大網格密度不唯一的k-means算法)

輸入:包含n個樣本的數據集D,期望劃分的聚類個數k,相似度閾值V;

輸出:k個最優類簇;

Begin

1.令集合h={},g={},l={},m={},s={};

2.for(j=1 toi){

3.Dj←Sorting(Dj);}/*對數據的每一維采用快速排序法排序*/

4.M←Divide(Dj);/*將每一維進行等深劃分,每個區間段包含[n/q]個數據點*/

5.|Sij|←Computer_density(d(i)([n/q]*j)-d(i)([n/q]*(j-1)+1));/*計算區間段密度*/

6.ρ←Computer_similarity(|Sij|/|Si(j+1)|);/*計算各維相鄰區間相似度*/

7.If (ρ>v){

8.Mi←Merge(Mi,Mi+1);}/*將滿足條件的相鄰區間段進行合并*/

9.Mi←iterate over _merge(Dj);/*循環遍歷數據集D的每一維,將滿足條件的區間合并*/

10.Dens(Mi)←Computer_dens[Dens(Mi)];/*根據(2)式,計算合并后網格的密度*/

11.h=h∪Dens(Mi);/*將計算的網格密度放入集合h中*/

12.Computer_min_DensThreshold(t);/*根據(3)式,計算最小密度閾值*/

13.If(Dens(Mi)>t){

14.g=g∪Mi;}/*將大于密度閾值的類簇放入集合g中*/

15.s←Use_k-means(g);/*用k-means聚類方法對g中高密度網格進行聚類*/

16.l=l∪max{Mi∈s∣Dens(Mi)},i=i+j;/*將有相同最大密度值的類簇放入集合l中,并記錄l中的個數,記為i*/

17.If(|i|=1){

18.D1←maxDens(Mi);}

19.D←Computer_MaxDistance(D1,D2);

20.m=m∪{i=1 tok|Di};

21.until Cluster.number=k;/*在集合g中,計算離D1距離最遠的類簇并記為D2,將D1,D2放入集合m中,直到m中有k個類簇*/

22.C←Computer_SumDist[Dist(Di,Di+1)];/*根據定義7計算類間距離之和*/

23.If(|i|>1){

24. forMi∈lDo

25.Ci←Computer_SumDist(Di,Di+1);}/*對每一個Mi,根據18-22步求出k個類簇,并求出Mi對應類簇的距離之和Ci*/

26.s←Computer_Max(Ci);/*計算出距離和最大的一組即為所求*/

27.Output Cluster;/*輸出最優聚類結果*/

End

3.3 對動態增量數據的聚類

本節在3.2節論述的基礎上進一步提出了動態增量聚類方法,該方法可用于對動態增量式數據進行聚類.所提方法的主要思想:在可變網格k-means聚類基礎上進行更新操作,當有數據到來時,只關心數據影響到的網格和類.因此該算法有較好的伸縮性和高效的效率.

算法具體過程:首先根據可變網格劃分規則對初始樣本集進行動態劃分,形成初始網格,然后對新加入的樣本集進行分配操作,如果該樣本屬于已有的網格,則直接把該樣本加入到對應網格中,并進行記錄,如果該樣本不屬于已有的網格,則創建一個新的網格,加入該樣本并進行記錄,對每個樣本都進行上述操作,經過時間t,對相似度高的相鄰網格進行合并,并且重新計算密度閾值,最后,對高密度網格進行k-means聚類操作,輸出最終的聚類結果.基于以上討論,動態增量聚類算法的具體算法如算法3所示.

算法3.GDIk-means()(基于網格的動態增量k-means聚類)

輸入:初始樣本集D,期望劃分聚類數K,相似度閾值V,時間間隔t;

輸出:最優聚類結果;

Begin

1.令集合d={},g={},s={};

2.gi←Computer_gridPartition(Di);/*劃分網格,形成初始網格*/

g←join_NewDataSet(X);/*加入新的樣本集X={x1,x2,…,xn},其中,xi=(xi1,xi2,…,xid),xij表示d維空間的樣本對象*/

3.If(xi∈gi){

4.gi←Add_data(xi);

5.d←Computer_density(gi);}/*xi屬于已存在的網格單元,把xi加入到該網格,重新計算網格密度并記錄*/

6.else{

7.gj←Create_NewGrid(xi);

8.d←Computer_density(gj);}/*xi不屬于已存在的網格單元,則創建一個新的網格放入該數據并記錄*/

9.set_time(t);

10.gi←Merge(gi,gi+1);

11.v←Update_DensThreshold(v);/*設置一個時間間隔t,每隔t時間對網格進行一次合并,并更新密度閾值一次*/

12.If(Dens(gi)

13.delect(gi);}/*對小于密度閾值的網格進行剪枝刪除操作*/

14.s←Use_k-means(g);/*對高密度網格進行k-means聚類*/

15.Output cluster(s);/*輸出聚類結果*/

End

4 基于網格優化的k-means聚類和聚類有效性指標的k值優化

在空間聚類中,有效性指標對最佳聚類數k有確定性作用.計算最佳聚類數主要思想是;首先在聚類數的搜索范圍內[kmin,kmax]內,根據確定的k值對樣本數據集進行聚類,其次利用有效性指標對聚類結果進行測試,最優聚類結果所對應的k值就是最佳聚類數,記為kopt.

算法4.VGOk_BWP_k-means()(基于VGOk-means和BWP指標的優化算法)

輸入:含n個樣本的數據集D,相似度閾值v;

輸出:BWP指標最大時對應的最佳聚類數kopt;

Begin

1.令集合c={},g={},s={};

3.Fork=kmintokmaxDo

4.c←Chose_initialCenterPoint(ci);/*根據基于最大網格密度不唯一的k-means算法,選出k個初始中心點*/

5.s←Use_VGOK-means(D);/*根據網格優化的k-means聚類方法對樣本進行聚類*/

6.g←Computer_argBWP(s);/*對每個聚類結果計算平均BWP指標值,并進行記錄*/

7.Fori=kmintokmaxDo

8.if(argBWP(si)

9.argBWP(si)=argBWP(si+1);

10.i++;}

11.kopt←Chose_MaxBWP(si);/*比較計算的BWP指標值,平均值最大所對應的k為最佳聚類數kopt*/

12.Output Cluster(kopt);/*輸出最佳聚類數kopt*/

End

5 實驗結果與分析

5.1 基于網格優化的k-means聚類算法實驗分析

首先,為了測試基于網格優化的k-means聚類算法的有效性,采用數據集為UCI中的Balance Scale、University、Japanese vowels數據集,數據來源(http://archive.ics.uci.edu/ml/).

數據集詳情描述如表1所示.

表1 樣本數據集
Table 1 Sample data set

數據集樣本個數屬性個數類別個數BalanceScale62544University285175Japanesevowels640128

對基于網格優化的k-means聚類算法與傳統的k-means聚類算法在準確率與時間花費上性能進行分析,本實驗對上述UCI中的Balance Scale、University、Japanese vowels數據集進行聚類,并對結果進行了記錄與分析,實驗結果如表2所示.

表2 實驗結果分析
Table 2 Analysis of experimental results

數據集本文方法傳統的k?means方法正確率/%時間/ms正確率/%時間/msBalanceScale93．2514289．17110University88．537676．3662Japanesevowels82．6716373．45127

從表2對比可以看出,本文提出的基于網格優化的k-means聚類算法比傳統的k-means算法正確率有了明顯提高,表明基于網格優化的k-means聚類算法是有效的.

5.2 基于可變網格優化的k-means算法及BWP指標的k值選取分析

此實驗首先用基于可變網格優化的k-means算法選出k個簇,其次對聚類結果用BWP指標進行評估,并展示結果.本實驗使用的人工數據集ID1與ID2.

表3 樣本數據集
Table 3 Sample data set

數據集維數樣本數類數ID121864ID23963

基于不唯一最大網格密度算法的聚類數k與其BWP指標關系如圖1,圖2所示.BWP指標的取值范圍為[-1,1].BWP指標越接近于1,說明聚類效果越好.所以,BWP最大時所對應的聚類數是最佳聚類數.圖1所示:當k=4時,BWP指標的平均值avg(4)=0.684.此時的BWP最大,所以k=4時是最佳聚類數.同理,圖2中,k=3時,BWP指標的平均值avg(3)=0.634,此時的BWP指標最大,由此可得k=3時是最佳聚類數.

圖1 ID1聚類數k與BWP指標關系Fig．1 ID1clusternumberkandBWPindexrelations圖2 ID2聚類數k與BWP指標關系Fig．2 ID2clusternumberkandBWPindexrelations

最后,根據上面得到的最佳聚類數kopt對ID1和ID2數據集進行聚類,得到了最優的聚類結果,如圖3,圖4所示.

圖3 數據集ID1的聚類結果Fig．3 DatasetID1clusteringresults圖4 數據集ID2的聚類結果Fig．4 DatasetID2clusteringresults

實驗結果說明:基于可變網格優化的k-means聚類和BWP指標的結合能得到正確的聚類數,并且提高了聚類的準確率和結果的有效性.

6 結束語

傳統的k-means聚類算法通過隨機選取k個初始中心進行聚類,對聚類結果的影響比較大,而且容易陷入局部最優解.針對以上不足,本文提出了基于可變網格優化的k-means聚類算法,結合BWP指標得到了最佳的聚類數,提高了聚類算法的有效性.實驗結果表明,基于可變網格優化的k-means聚類算法能夠高質量的選取聚類中心,并且準確率有了很大程度的提高,實驗結果證明了算法的有效性.

[1] Dhanachandra N,Manglem K,Chanu Y J.Image segmentation using k-means clustering algorithm and subtractive clustering algorithm [J].Procedia Computer Science,2015,54:764-771.

[2] Tang Dong-ming,Zhu Qing-xin,Yang Fan,et al.An efficient cluster analysis method for protein sequences[J].Journal of Software,2011,22(8):1827-1837.

[3] Tang Ying-jun,Huang Shu-ying,Yang Yong，et al.Adaptive k-means to high dimensional feature of image [J].Journal of Chinese Computer Systems,2016,37 (8):1854-1856.

[4] Lu W J,Yan Z Z.Improved FCM Algorithm based on k-means and granular computing [J].Journal of Intelligent Systems,2015,24(2):215-222.

[5] Tzortzis G,Likas A,Tzortzis G.The MinMax k-Means clustering algorithm[J].Pattern Recognition,2014,47 (7):2505-2516.

[6] Yu S,Tranchevent L C,Moor B D,et al.Optimized data fusion for kernel k-means clustering[J].IEEE Transactions on Software Engineering,2012,34(5):1031-1039.

[7] Zhong C,Malinen M,Miao D,et al.A fast minimum spanning tree algorithm based on K-means[J].Information Sciences,2015,295(C):1-19.

[8] Cai Yu-hao,Liang Yong-quan,Fan Jian-cong,et al.Optimizing initial cluster centroids by weighted local variance in k-means algorithm [J].Journal of Frontiers of Computer Science and Technology,2016,10(5):732-741.

[9] García M L L,García-Ródenas R,Gómez A G.K-means algorithms for functional data[J].Neurocomputing,2015,151:231-245.

[10] Chen Guang-ping,Wang Wen-peng,Huang Jun,et al.Improved initial clustering center selection method for k-means algorithm [J].Journal of Chinese Computer Systems,2012,33(6):1320-1323.

[11] Sheng Kai-yuan,Qian Xue-zhong,Wu Qin,et al.Density biased sampling algorithm based on variable grid division[J].Journal of Computer Applications,2013,33(9):2419-2422.

附中文參考文獻：

[2] 唐東明,朱清新,楊 凡,等.一種有效的蛋白質序列聚類分析方法[J].軟件學報,2011,22(8):1827-1837.

[3] 唐穎軍,黃淑英,楊 勇,等.圖像高維數據的K-means自適應聚類算法[J].小型微型計算機系統,2016,37(8):1854-1856.

[8] 蔡宇浩,梁永全,樊建聰,等.加權局部方差優化初始簇中心的K-means算法[J].計算機科學與探索,2016,10(5):732-741.

[10] 陳光平,王文鵬,黃 俊,等.一種改進初始聚類中心選擇的 K-means算法[J].小型微型計算機系統,2012,33(6):1320-1323.

[11] 盛開元,錢雪忠,吳 秦,等.基于可變網格劃分的密度偏差抽樣算法[J].計算機應用,2013,33(9):2419-2422.