局部網格動態聚類算法

王瑋琪 萬仁霞 周方祥

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

關鍵詞： 網格; 局部密度; 聚類算法; 密集網格; 稀疏網格; 簇邊界

中圖分類號： TN911.1?34; TP311 ? ? ? ? ? ? ? ? ? 文獻標識碼： A ? ? ? ? ? ? ? ? ? ?文章編號： 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 ?引 ?言

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

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

經典網格聚類算法存在很多問題，如：

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

2） 固定網格結構劃分不能體現數據的流動性，對流數據的處理能力較弱[11]。

3） 聚類質量受網格劃分粒度影響較大，網格粒度劃分過大，則會降低聚類質量，網格粒度劃分過小，則會降低聚類效率[12]。

針對上述問題，本文提出局部網格動態聚類算法（Dclu_LG），引入維度半徑對網格進行動態劃分，充分體現數據的流動性，引入判定網格質心距的方法處理簇邊界[13]，為了進一步提高聚類精度提出了全新簇邊界處理方法，即通過局部網格劃分體現數據的局部密集性，算法保證聚類精度的同時又提高了聚類效率。

1 ?局部網格動態聚類算法

1.1 ?基本概念

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

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

定義1：維度半徑：以數據點[xij]為中心的網格劃分[[xij-r，xij+r]]，[r]為維度半徑。

定義2：網格相對密度：網格所包含數據點的個數[s]與網格體積[v]的比值，即[sv]。

定義3：密集格：網格相對密度大于給定閾值[ρ0]的網格即為密集格，即[sv>ρ0]。

定義4：局部網格：在稀疏網格中，以數據點重心為中心，以重心到網格邊界的最短距離為半徑劃分得到的新網格稱為局部網格。顯然，重心到網格邊界的最短距離不會超過原網格的半徑。

定義5：局部網格密度：局部網格包含的數據點個數[s]與局部網格體積[v]的比值，即[sv]。

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

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

定義8：格間距：兩個網格單元內數據點重心的距離。

對于任意兩個網格[g1]和[g2]，格間距表示為[d（g1，g2）]（文中若無特殊說明，所出現的距離計算方式為歐氏距離）。

定義9：鄰接網格：對于網格[g1]和[g2]，若存在公共邊或公共頂點，則稱為鄰接網格。

Dclu_LG算法框架為：

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

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

1.讀取數據集[D={x1，x2，…，xn}];

2.while數據集不為空

3. ?根據給定維度半徑[r]，在每一維上動態劃分網格;

4. ?if密集格相連

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

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

7. ? ?歸并稀疏網格;

8. ?elseif非空稀疏網格相連

9. ? ?劃分稀疏格，產生局部網格;

10. ? 間距小于[r]的局部網格，歸并局部網格;

11. endif

12. 聚類形成最終簇;

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

14.endwhile

1.2 ?初始簇形成

Dclu_LG算法對于每一個網格使用一個六元組進行刻畫[（CF1，CF2，T2，T，s，v）]，其中，[CF1]與[CF2]分別表示對應網格中數據點在各維上的算數和與平方和;[T2]與[T]分別表示對應網格數據點到達時間的算數和與平方和;[s]表示網格中數據點的個數;[v]表示網格的體積。

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

對已產生的網格結構進行聚類形成初始簇。一個聚類就是相連的網格相對密度大于閾值[ρ0]的網格組成的最大集，對相連密集格進行聚類，動態網格聚類結果為[C={C′1，C′2，…，C′h}]。

1.3 ?Merge_SG算法

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

輸入：網格結構[G={g1，g2，…}]，[C={C′1，C′2，…，C′h}]

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

1.讀取網格結構[G={g1，g2，…}];

2.[Temp_G=C];

3.while [G≠][?];

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

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

6. ? ?對于每一個稀疏網格[g]，考察其所有鄰接網格單元;

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

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

8. ? ? ?計算[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 ?局部網格劃分

Dclu_LG算法第9行是對稀疏網格再劃分，并據此產生局部網格，其主要過程有：

在稀疏網格中，確定數據點重心[xij]，度量數據點重心到原網格邊界的最短距離，以各邊界的最短距離[l（l

局部網格形成的算法如下：

輸入：網格結構[G={g1，g2，…}]

輸出：局部網格結構[G={g′1，g′2，…}]，網格結構[G={g1，g2，…}]

1.讀取網格結構[G={g1，g2，…}];

2.[G=][?];

3.while [G≠][?]

4. ?從[G]中任取網格[g];

5. ?確定網格[g]內數據點質心[x=（x（1），x（2），…，x（d））];

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

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

8. ?if [x]在網格中心

9. ? ?不進行局部網格劃分;

10. ?endif

11. ?[G=G?g];

12. ? [G=G-g];

13.endwhile

1.5 ?局部網格歸并

對于劃分出的局部網格，搜索其所在網格的所有鄰接網格內的局部網格，若局部網格格間距小于[r]，則進行局部網格合并，若合并后的網格為密集網格，則調用Merge_SG算法歸并其周圍的稀疏局部網格。局部網格聚類算法描述如下：

輸入：局部網格結構[G={g′1，g′2，…}]，相對密度閾值[ρ0]

輸出：局部網格聚類結果[C={C″1，C″2，…，C″m}]

1.讀取局部網格結構[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. ? ? ?調用Merge_SG算法：[C″m]歸并周圍的局部網格，并更新[C″m]和[G];

18. ? ?endif

19. ?endwhile

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

21.endwhile

1.6 ?最終簇形成

Dclu_LG算法經過動態網格聚類以及局部網格聚類后，產生了兩組微簇，微簇的總個數通常要比最終要求簇數多得多，為此，需要將這兩組簇合并處理。本算法中，為了將上述兩類簇合并，采用微簇近鄰聚類法，為此，本文定義了兩個微簇距離如下：

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

對于兩次聚類所產生的微簇將會做進一步的聚類，算法如下：

輸入：動態網格聚類結果[C={C′1，C′2，…，C′h}]

局部網格聚類結果[C={C″1，C″2，…，C″m}]

輸出：聚類結果[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 ?實驗與結果分析

為了測試Dclu_LG的性能，實驗在Win 7?64位操作系統、Inter Core i5?4210M 2.6 GHz CPU，4 GB內存，Matlab R2012a環境下進行。

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

在實驗中，采用KDD?CUP99網絡入侵數據集對IGrid算法[14]、文獻[15]算法以及Dclu_LG算法進行聚類質量對比，該數據集共包含494 020個樣本，每個樣本包含41個屬性，其中，34個為數值屬性，7個為分類屬性，在本實驗中僅考慮數值屬性，實驗結果如圖1所示。

可以看出，Dclu_LG的聚類質量要高于IGrid以及文獻[15]算法，尤其是數據點較多時，Dclu_LG的聚類質量優勢表現明顯。

為了進一步測試算法的執行效率，本文利用UCI機器學習庫中的Wine數據集、Iris數據集、Glass數據集與D31人工數據集以及S1人工數據集進行測試。實驗中使用的數據集相關信息如表1所示。

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

分別使用IGrid算法、文獻[15]算法以及Dclu_LG算法運行上述數據集，運行100次統計平均運行時間和平均錯誤率，運行結果如表2所示，圖2，圖3給出人工數據集運行結果對比，其中，黑點數據代表未能識別的數據點。

3 ?結 ?語

本文研究了數據流聚類問題，提出了局部網格動態聚類算法，解決了傳統網格聚類算法聚類精度較低，處理流數據效率較低等問題。Dclu_LG算法可以根據數據流數據點不斷增加的情況動態劃分網格結構，并且對其進行增量調整，又通過判定網格質心距以及局部網格再次劃分的新的簇邊界判定方法解決了網格聚類簇邊界丟失問題，通過多組對比實驗表明提出的算法具有較高的聚類效率。

參考文獻

[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] 印桂生，于翔，寧慧.一種基于網格的增量聚類算法[J].計算機應用研究，2009，26（6）：2038?2040.

[14] 萬新貴，李玲娟.基于質心距離和密度網格的數據流聚類算法[J].南京郵電大學學報，2017，37（1）：97?73.

[15] 楊潔，王國胤，王飛.基于密度峰值的網格聚類算法[J].計算機應用，2017，37（11）：3080?3084.

作者簡介：王瑋琪（1994—），男，內蒙古烏蘭浩特人，碩士研究生，研究方向為數據挖掘。

萬仁霞（1975—），男，江西南昌人，博士，副教授，主要研究方向為數據挖掘與模式識別。

周方祥（1991—），男，廣東茂名人，碩士研究生，研究方向為數據挖掘。