局部網(wǎng)格動(dòng)態(tài)聚類算法

王瑋琪 萬(wàn)仁霞 周方祥

摘 ?要： 針對(duì)傳統(tǒng)網(wǎng)格聚類算法聚類精度較低，處理流數(shù)據(jù)效率較低等問(wèn)題進(jìn)行改進(jìn)。提出局部網(wǎng)格動(dòng)態(tài)聚類算法，算法引入維度半徑概念進(jìn)行增量動(dòng)態(tài)網(wǎng)格劃分，通過(guò)采用新的簇邊界判定方法對(duì)簇邊界進(jìn)行判定，依據(jù)稀疏網(wǎng)格與其鄰接密集網(wǎng)格的質(zhì)心距離，將稀疏網(wǎng)格歸并到相應(yīng)網(wǎng)格簇中，對(duì)于不能歸并的稀疏網(wǎng)格則采用局部網(wǎng)格劃分方法對(duì)稀疏網(wǎng)格再次進(jìn)行劃分聚類，避免簇邊界的誤刪，在一定程度上提高了聚類精確度。通過(guò)對(duì)比實(shí)驗(yàn)結(jié)果表明提出的算法具有更好的聚類時(shí)效性和聚類精度。

關(guān)鍵詞： 網(wǎng)格; 局部密度; 聚類算法; 密集網(wǎng)格; 稀疏網(wǎng)格; 簇邊界

中圖分類號(hào)： TN911.1?34; TP311 ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ? ?文章編號(hào)： 1004?373X（2020）01?0102?05

Dynamic clustering algorithm based on local grid

WANG Weiqi， WAN Renxia， ZHOU Fangxiang

Abstract： A dynamic clustering algorithm based on local grid is proposed to deal with the facts of low clustering accuracy and low efficiency in processing streaming data in the traditional grid clustering algorithm. In this algorithm， the concept of dimension radius is introduced for incremental dynamic grid division， and a new judgment method of cluster boundary is adopted to determine the boundary of clusters. In addition， the sparse grids are merged into the corresponding grid clusters according to the centroid distances from sparse grids to their neighboring dense grids. As for those who cannot be merged， the local grid division method is adopted to divide and cluster them again， so as to avoid mistaken deletion of cluster boundaries and improve the clustering accuracy to a certain extent. The comparative experiment results show that the proposed algorithm has better clustering timeliness and accuracy.

Keywords： grid; local density; clustering algorithm; density grid; sparse grid; cluster boundary

0 ?引 ?言

聚類分析是數(shù)據(jù)挖掘中的一類重要技術(shù)，其目的是將數(shù)據(jù)進(jìn)行分組，使得同一個(gè)組內(nèi)的數(shù)據(jù)盡可能相似而不同組內(nèi)的數(shù)據(jù)盡可能不同[1]。目前主要的聚類分析算法大致可以分為五類：基于劃分的方法、基于層次的方法、基于密度的方法、基于網(wǎng)格的方法以及基于模型的方法等[2?6]。

基于網(wǎng)格的聚類技術(shù)的基本原理是：通過(guò)維分割將數(shù)據(jù)空間分成不相交的網(wǎng)格單元，后續(xù)的聚類操作就可以在網(wǎng)格單元上進(jìn)行。網(wǎng)格單元恰當(dāng)劃分可以使同一單元中的點(diǎn)屬于同一類的可能性大大增加，這樣，落入同一網(wǎng)格中的點(diǎn)便可被作為一個(gè)對(duì)象進(jìn)行處理。這種方法的主要優(yōu)點(diǎn)是處理速度快，處理時(shí)間獨(dú)立于數(shù)據(jù)對(duì)象數(shù)，而僅依賴于量化空間中每一維上的單元數(shù)。具有代表性的基于網(wǎng)格的聚類算法有：STING算法[7]、WaveCluster算法[8]、CLIQUE算法[9]。

經(jīng)典網(wǎng)格聚類算法存在很多問(wèn)題，如：

1） 單一密度閾值易造成低密度聚類的丟失[10]。

2） 固定網(wǎng)格結(jié)構(gòu)劃分不能體現(xiàn)數(shù)據(jù)的流動(dòng)性，對(duì)流數(shù)據(jù)的處理能力較弱[11]。

3） 聚類質(zhì)量受網(wǎng)格劃分粒度影響較大，網(wǎng)格粒度劃分過(guò)大，則會(huì)降低聚類質(zhì)量，網(wǎng)格粒度劃分過(guò)小，則會(huì)降低聚類效率[12]。

針對(duì)上述問(wèn)題，本文提出局部網(wǎng)格動(dòng)態(tài)聚類算法（Dclu_LG），引入維度半徑對(duì)網(wǎng)格進(jìn)行動(dòng)態(tài)劃分，充分體現(xiàn)數(shù)據(jù)的流動(dòng)性，引入判定網(wǎng)格質(zhì)心距的方法處理簇邊界[13]，為了進(jìn)一步提高聚類精度提出了全新簇邊界處理方法，即通過(guò)局部網(wǎng)格劃分體現(xiàn)數(shù)據(jù)的局部密集性，算法保證聚類精度的同時(shí)又提高了聚類效率。

1 ?局部網(wǎng)格動(dòng)態(tài)聚類算法

1.1 ?基本概念

為了便于描述算法，引入如下定義。

假設(shè)[D={x1，x2，…，xn}]為[d]維空間[S]上的一個(gè)數(shù)據(jù)集，[xij]表示數(shù)據(jù)點(diǎn)[xi]在第[j]維的值。

定義1：維度半徑：以數(shù)據(jù)點(diǎn)[xij]為中心的網(wǎng)格劃分[[xij-r，xij+r]]，[r]為維度半徑。

定義2：網(wǎng)格相對(duì)密度：網(wǎng)格所包含數(shù)據(jù)點(diǎn)的個(gè)數(shù)[s]與網(wǎng)格體積[v]的比值，即[sv]。

定義3：密集格：網(wǎng)格相對(duì)密度大于給定閾值[ρ0]的網(wǎng)格即為密集格，即[sv>ρ0]。

定義4：局部網(wǎng)格：在稀疏網(wǎng)格中，以數(shù)據(jù)點(diǎn)重心為中心，以重心到網(wǎng)格邊界的最短距離為半徑劃分得到的新網(wǎng)格稱為局部網(wǎng)格。顯然，重心到網(wǎng)格邊界的最短距離不會(huì)超過(guò)原網(wǎng)格的半徑。

定義5：局部網(wǎng)格密度：局部網(wǎng)格包含的數(shù)據(jù)點(diǎn)個(gè)數(shù)[s]與局部網(wǎng)格體積[v]的比值，即[sv]。

定義6： 網(wǎng)格公共面：對(duì)于[d]維網(wǎng)格[g1]和[g2]，若[d-1]維上具有相同的區(qū)域，在剩下的那一維上，[g1]與[g2]劃分的區(qū)域相互鄰接，則稱[g1]與[g2]有一個(gè)網(wǎng)格公共面。

定義7： 網(wǎng)格相連：當(dāng)兩個(gè)網(wǎng)格[g1]和[g2]有一個(gè)網(wǎng)格公共面或存在另一個(gè)網(wǎng)格[g3]，使得[g1]與[g3]之間有一個(gè)網(wǎng)格公共面，[g2]與[g3]之間有一個(gè)網(wǎng)格公共面，則稱網(wǎng)格[g1]與[g2]是相連的。

定義8：格間距：兩個(gè)網(wǎng)格單元內(nèi)數(shù)據(jù)點(diǎn)重心的距離。

對(duì)于任意兩個(gè)網(wǎng)格[g1]和[g2]，格間距表示為[d（g1，g2）]（文中若無(wú)特殊說(shuō)明，所出現(xiàn)的距離計(jì)算方式為歐氏距離）。

定義9：鄰接網(wǎng)格：對(duì)于網(wǎng)格[g1]和[g2]，若存在公共邊或公共頂點(diǎn)，則稱為鄰接網(wǎng)格。

Dclu_LG算法框架為：

輸入：數(shù)據(jù)集[D={x1，x2，…，xn}]，維度半徑[r={r1，r2，…，rn}]

輸出：聚類結(jié)果[C={C1，C2，…，Ck}]

1.讀取數(shù)據(jù)集[D={x1，x2，…，xn}];

2.while數(shù)據(jù)集不為空

3. ?根據(jù)給定維度半徑[r]，在每一維上動(dòng)態(tài)劃分網(wǎng)格;

4. ?if密集格相連

5. ? ?相連密集格聚類形成初始簇;

6. ?elseif非空稀疏格與密集格相連

7. ? ?歸并稀疏網(wǎng)格;

8. ?elseif非空稀疏網(wǎng)格相連

9. ? ?劃分稀疏格，產(chǎn)生局部網(wǎng)格;

10. ? 間距小于[r]的局部網(wǎng)格，歸并局部網(wǎng)格;

11. endif

12. 聚類形成最終簇;

13. 輸出聚類結(jié)果[C={C1，C2，…，Ck}];

14.endwhile

1.2 ?初始簇形成

Dclu_LG算法對(duì)于每一個(gè)網(wǎng)格使用一個(gè)六元組進(jìn)行刻畫(huà)[（CF1，CF2，T2，T，s，v）]，其中，[CF1]與[CF2]分別表示對(duì)應(yīng)網(wǎng)格中數(shù)據(jù)點(diǎn)在各維上的算數(shù)和與平方和;[T2]與[T]分別表示對(duì)應(yīng)網(wǎng)格數(shù)據(jù)點(diǎn)到達(dá)時(shí)間的算數(shù)和與平方和;[s]表示網(wǎng)格中數(shù)據(jù)點(diǎn)的個(gè)數(shù);[v]表示網(wǎng)格的體積。

對(duì)數(shù)據(jù)點(diǎn)[D={x1，x2，…，xn}]，按順序依次對(duì)數(shù)據(jù)點(diǎn)[xi={xi1，xi2，…，xid}]在其相應(yīng)的每一維上劃分網(wǎng)格空間。具體步驟如下：對(duì)于數(shù)據(jù)點(diǎn)[xi]在第[j]維上的值[xij]，若[j]維上已存在的劃分不包含[xij]，則由第[j]維的維度半徑可以得到劃分，稱[xij-rj]為該劃分的前部，[xij+rj]為該劃分的后部，若新增劃分與某已存在的劃分后部相交（設(shè)已存在的劃分為[[xkj-rj，xkj+rj]]），則調(diào)整新增劃分為[[xkj+rj，xij+rj]];若新增劃分與某已存在的劃分前部相交，則調(diào)整新增劃分為[[xij-rj，xkj-rj]]。若新增劃分與某已存在的劃分前部后部都相交（設(shè)已存在劃分為[[xmj-rj，xmj+rj]]和[[xnj-rj，xnj+rj]]），則調(diào)整新增劃分為[[xmj+rj，xnj-rj]]或[[xnj+rj，xmj-rj]]。

對(duì)已產(chǎn)生的網(wǎng)格結(jié)構(gòu)進(jìn)行聚類形成初始簇。一個(gè)聚類就是相連的網(wǎng)格相對(duì)密度大于閾值[ρ0]的網(wǎng)格組成的最大集，對(duì)相連密集格進(jìn)行聚類，動(dòng)態(tài)網(wǎng)格聚類結(jié)果為[C={C′1，C′2，…，C′h}]。

1.3 ?Merge_SG算法

Dclu_LG算法第7行，需要根據(jù)格間距將稀疏網(wǎng)格并入密集格，歸并稀疏網(wǎng)格的算法Merge_SG如下：

輸入：網(wǎng)格結(jié)構(gòu)[G={g1，g2，…}]，[C={C′1，C′2，…，C′h}]

輸出：聚類結(jié)果[C={C′1，C′2，…，C′h}]

1.讀取網(wǎng)格結(jié)構(gòu)[G={g1，g2，…}];

2.[Temp_G=C];

3.while [G≠][?];

4. ?從[G]中取[g];

5. ?if[（g?sg?v）<ρ0]

6. ? ?對(duì)于每一個(gè)稀疏網(wǎng)格[g]，考察其所有鄰接網(wǎng)格單元;

7. ? if[?q1∈Temp_G.C′k1，q2∈Temp_G.C′k2，q3∈Temp_G.C′k3…]

[（k1，k2，k3，…∈{1，2，…，h}）]

8. ? ? ?計(jì)算[g]與[qi]之間的格間距[d（g，qi）];

9. ? ?endif

10. ? ?選取[d（g，qk1）=mini=1，2，…d（g，qi）]

11. ? ?if[（d（g，qk1）≤r）]

12. ? ?[C′h=C′h_G?{g}];

13. ? ?[G=G-{g}];

14. ? ?endif

15. ?endif

16.endwhile

1.4 ?局部網(wǎng)格劃分

Dclu_LG算法第9行是對(duì)稀疏網(wǎng)格再劃分，并據(jù)此產(chǎn)生局部網(wǎng)格，其主要過(guò)程有：

在稀疏網(wǎng)格中，確定數(shù)據(jù)點(diǎn)重心[xij]，度量數(shù)據(jù)點(diǎn)重心到原網(wǎng)格邊界的最短距離，以各邊界的最短距離[l（l

局部網(wǎng)格形成的算法如下：

輸入：網(wǎng)格結(jié)構(gòu)[G={g1，g2，…}]

輸出：局部網(wǎng)格結(jié)構(gòu)[G={g′1，g′2，…}]，網(wǎng)格結(jié)構(gòu)[G={g1，g2，…}]

1.讀取網(wǎng)格結(jié)構(gòu)[G={g1，g2，…}];

2.[G=][?];

3.while [G≠][?]

4. ?從[G]中任取網(wǎng)格[g];

5. ?確定網(wǎng)格[g]內(nèi)數(shù)據(jù)點(diǎn)質(zhì)心[x=（x（1），x（2），…，x（d））];

6. ?以[x]為中心確定到網(wǎng)格邊界的最短距離[l];

7. ?基于劃分[[x（i）-l，x（i）+l]i=1，2，…，d]產(chǎn)生網(wǎng)格[g];

8. ?if [x]在網(wǎng)格中心

9. ? ?不進(jìn)行局部網(wǎng)格劃分;

10. ?endif

11. ?[G=G?g];

12. ? [G=G-g];

13.endwhile

1.5 ?局部網(wǎng)格歸并

對(duì)于劃分出的局部網(wǎng)格，搜索其所在網(wǎng)格的所有鄰接網(wǎng)格內(nèi)的局部網(wǎng)格，若局部網(wǎng)格格間距小于[r]，則進(jìn)行局部網(wǎng)格合并，若合并后的網(wǎng)格為密集網(wǎng)格，則調(diào)用Merge_SG算法歸并其周圍的稀疏局部網(wǎng)格。局部網(wǎng)格聚類算法描述如下：

輸入：局部網(wǎng)格結(jié)構(gòu)[G={g′1，g′2，…}]，相對(duì)密度閾值[ρ0]

輸出：局部網(wǎng)格聚類結(jié)果[C={C″1，C″2，…，C″m}]

1.讀取局部網(wǎng)格結(jié)構(gòu)[G={g′1，g′2，…}];

2.[m=0];

3.while [G≠][?]

4. ?[G=][?]

5. ?從[G]中任取[g];

6. ?[G=G-{g}];

7. ?[Temp_C={g}];

8. ?[m++];

9. ?[C″m=][?];

10. ?while [G≠][?]

11. ? ?任取[g∈G（min d（g，g）≤r，?g∈Temp_C）];

12. ? ?[Temp_C=Temp_C?{g}];

13. ? ?if [Temp_C.s/Temp_C.v>ρ0]

14. ? ? ?[C″m=C″m?Temp_C];

15. ? ? ?[G=G-{g}];

16. ? ? ?[G=G-{g}];

17. ? ? ?調(diào)用Merge_SG算法：[C″m]歸并周圍的局部網(wǎng)格，并更新[C″m]和[G];

18. ? ?endif

19. ?endwhile

20. ?[G=G-{g}];

21.endwhile

1.6 ?最終簇形成

Dclu_LG算法經(jīng)過(guò)動(dòng)態(tài)網(wǎng)格聚類以及局部網(wǎng)格聚類后，產(chǎn)生了兩組微簇，微簇的總個(gè)數(shù)通常要比最終要求簇?cái)?shù)多得多，為此，需要將這兩組簇合并處理。本算法中，為了將上述兩類簇合并，采用微簇近鄰聚類法，為此，本文定義了兩個(gè)微簇距離如下：

[d（C，C）=min1≤i≤C，1≤j≤Cd（g′i，g″j），g′i∈C，g″j∈C]

對(duì)于兩次聚類所產(chǎn)生的微簇將會(huì)做進(jìn)一步的聚類，算法如下：

輸入：動(dòng)態(tài)網(wǎng)格聚類結(jié)果[C={C′1，C′2，…，C′h}]

局部網(wǎng)格聚類結(jié)果[C={C″1，C″2，…，C″m}]

輸出：聚類結(jié)果[C={C1，C2，…，Ck}]

1.讀取[C]和[C];

2.[Temp_C=C?C];

3.while [|Temp_C|≠k]

4. ?任取[C′a，C″b∈Temp_C];

5. ?if [d（C′a，C″b）=minC′i，C″j∈Temp_Cd（C′i，C″j）];

6. ? ?[Temp_C=Temp_C-{C′a}-{C″b}];

7. ? ?[Temp_C=Temp_C?{C′a?C″b}];

8. ?endif

9.endwhile

10.[C=Temp_C];

11.輸出[C];

2 ?實(shí)驗(yàn)與結(jié)果分析

為了測(cè)試Dclu_LG的性能，實(shí)驗(yàn)在Win 7?64位操作系統(tǒng)、Inter Core i5?4210M 2.6 GHz CPU，4 GB內(nèi)存，Matlab R2012a環(huán)境下進(jìn)行。

算法參數(shù)設(shè)置：維度半徑[r=]2.5，密度閾值[ρ0]=0.64，數(shù)據(jù)流速[v=]1 000條/s 。

在實(shí)驗(yàn)中，采用KDD?CUP99網(wǎng)絡(luò)入侵?jǐn)?shù)據(jù)集對(duì)IGrid算法[14]、文獻(xiàn)[15]算法以及Dclu_LG算法進(jìn)行聚類質(zhì)量對(duì)比，該數(shù)據(jù)集共包含494 020個(gè)樣本，每個(gè)樣本包含41個(gè)屬性，其中，34個(gè)為數(shù)值屬性，7個(gè)為分類屬性，在本實(shí)驗(yàn)中僅考慮數(shù)值屬性，實(shí)驗(yàn)結(jié)果如圖1所示。

可以看出，Dclu_LG的聚類質(zhì)量要高于IGrid以及文獻(xiàn)[15]算法，尤其是數(shù)據(jù)點(diǎn)較多時(shí)，Dclu_LG的聚類質(zhì)量?jī)?yōu)勢(shì)表現(xiàn)明顯。

為了進(jìn)一步測(cè)試算法的執(zhí)行效率，本文利用UCI機(jī)器學(xué)習(xí)庫(kù)中的Wine數(shù)據(jù)集、Iris數(shù)據(jù)集、Glass數(shù)據(jù)集與D31人工數(shù)據(jù)集以及S1人工數(shù)據(jù)集進(jìn)行測(cè)試。實(shí)驗(yàn)中使用的數(shù)據(jù)集相關(guān)信息如表1所示。

表1中，算法參數(shù)設(shè)置：維度半徑[r=]2.2，密度閾值[ρ0=]0.57。

分別使用IGrid算法、文獻(xiàn)[15]算法以及Dclu_LG算法運(yùn)行上述數(shù)據(jù)集，運(yùn)行100次統(tǒng)計(jì)平均運(yùn)行時(shí)間和平均錯(cuò)誤率，運(yùn)行結(jié)果如表2所示，圖2，圖3給出人工數(shù)據(jù)集運(yùn)行結(jié)果對(duì)比，其中，黑點(diǎn)數(shù)據(jù)代表未能識(shí)別的數(shù)據(jù)點(diǎn)。

3 ?結(jié) ?語(yǔ)

本文研究了數(shù)據(jù)流聚類問(wèn)題，提出了局部網(wǎng)格動(dòng)態(tài)聚類算法，解決了傳統(tǒng)網(wǎng)格聚類算法聚類精度較低，處理流數(shù)據(jù)效率較低等問(wèn)題。Dclu_LG算法可以根據(jù)數(shù)據(jù)流數(shù)據(jù)點(diǎn)不斷增加的情況動(dòng)態(tài)劃分網(wǎng)格結(jié)構(gòu)，并且對(duì)其進(jìn)行增量調(diào)整，又通過(guò)判定網(wǎng)格質(zhì)心距以及局部網(wǎng)格再次劃分的新的簇邊界判定方法解決了網(wǎng)格聚類簇邊界丟失問(wèn)題，通過(guò)多組對(duì)比實(shí)驗(yàn)表明提出的算法具有較高的聚類效率。

參考文獻(xiàn)

[1] HUANG J H， HONG Y D， ZHAO Z M. An energy?efficient multi?hop routing protocol based on grid clustering for wireless sensor networks [J]. Cluster computing， 2017， 20（4）： 3071?3083.

[2] RODRIGUEZ A， LAIO A. Clustering by fast search and find of density peaks [J]. Science， 2014， 344（6191）： 1492?1496.

[3] SON L H， TIEN N D. Tune up fuzzy C?means for big data： some novel hybrid clustering algorithms based on initial selection and incremental clustering [J]. International journal of fuzzy systems， 2017， 19（5）： 1585?1602.

[4] CHOUBIN B， SOLAIMANI K， ROSHAN M H， et al. Watershed classification by remote sensing indices： a fuzzy C?means clustering approach [J]. Journal of mountain science， 2017， 14（10）： 2053?2063.

[5] XU X， DING S， DU M， et al. DPCG： an efficient density peaks clustering algorithm based on grid [J]. International journal of machine learning and cybernetics， 2016， 9（5）： 1?12.

[6] LALITHA K， THANGARAJAN R， UDGATA S K， et al. GCCR： an efficient grid based clustering and combinational routing in wireless sensor networks [J]. Wireless personal communications， 2017， 97（1）： 1075?1095.

[7] DONG S Q， LIU J J， LIU Y H， et al. Clustering based on grid and local density with priority?based expansion for multi?density data [J]. Information sciences， 2018， 468： 103?116.

[8] CHEN X Q. Clustering based on a near neighbor graph and a grid cell graph [J]. Journal of intelligent information systems， 2013， 40（3）： 529?544.

[9] FAHAD A， ALSHATRI N， TARI Z， et al. A survey of clustering algorithms for big data： taxonomy and empirical analysis [J]. IEEE transactions on emerging topics in computing， 2014， 2（3）： 267?279.

[10] JOSEPH S， ABDU J E. Real?time retail price determination in smart grid from real?time load profiles [J]. International transactions on electrical energy systems， 2018， 28（3）： 2509?2515.

[11] SARMAH S， BHATTACHARYYA D K. A grid?density based technique for finding clusters in satellite image [J]. Pattern recognition letters， 2012， 33（5）： 589?604.

[12] WANG Y W， ZHOU Y C， LIU Y， et al. A grid?based clustering algorithm for wild bird distribution [J]. Frontiers of computer science， 2013， 7（4）： 475?485.

[13] 印桂生，于翔，寧慧.一種基于網(wǎng)格的增量聚類算法[J].計(jì)算機(jī)應(yīng)用研究，2009，26（6）：2038?2040.

[14] 萬(wàn)新貴，李玲娟.基于質(zhì)心距離和密度網(wǎng)格的數(shù)據(jù)流聚類算法[J].南京郵電大學(xué)學(xué)報(bào)，2017，37（1）：97?73.

[15] 楊潔，王國(guó)胤，王飛.基于密度峰值的網(wǎng)格聚類算法[J].計(jì)算機(jī)應(yīng)用，2017，37（11）：3080?3084.

作者簡(jiǎn)介：王瑋琪（1994—），男，內(nèi)蒙古烏蘭浩特人，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘。

萬(wàn)仁霞（1975—），男，江西南昌人，博士，副教授，主要研究方向?yàn)閿?shù)據(jù)挖掘與模式識(shí)別。

周方祥（1991—），男，廣東茂名人，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘。