基于密度峰值的網格聚類算法

楊 潔, 王國胤, 王 飛

(1.計算智能重慶市重點實驗室(重慶郵電大學), 重慶400065； 2.遵義師范學院 物理與電子科學學院, 貴州 遵義 563002)

基于密度峰值的網格聚類算法

楊 潔1,2, 王國胤1*, 王 飛1

(1.計算智能重慶市重點實驗室(重慶郵電大學), 重慶400065； 2.遵義師范學院 物理與電子科學學院, 貴州 遵義 563002)

2014年提出的密度峰值聚類算法，思想簡潔新穎，所需參數少，不需要進行迭代求解，而且具有可擴展性。基于密度峰值聚類算法提出了一種網格聚類算法，能夠高效地對大規模數據進行處理。首先，將N維空間粒化為不相交的長方形網格單元；然后，統計單元空間的信息，利用密度峰值聚類尋找中心點的思想確定中心單元，即中心網格單元被一些低局部密度的數據單元包圍，而且與比自身局部密度高的網格單元的距離相對較大；最后，合并與中心網格單元相近網格單元，從而得出聚類結果。在UCI人工數據集上的仿真實驗結果表明，所提算法能夠較快得出聚類中心，有效處理大規模數據的聚類問題，具有較高的效率，與原始的密度峰值聚類算法相比，在不同數據集上時間損耗降低至原來的1/100～1/10，而精度損失維持在5% ～ 8%。

密度峰值；網格粒化；大規模數據; 聚類

0 引言

作為數據挖掘和人工智能領域的重要研究內容，聚類是一種無監督模式識別方法，即在沒有任何先驗信息的指導下，從一個數據集中發現潛在的相似模式，對數據集進行分組，以使得同一類內的相似性盡可能大，同時不同類之間的差異性盡可能大。近年來，數據挖掘在許多領域有廣泛的應用，例如：圖像[1]、醫藥[2]、航空[3]等領域。近年來，從衛星、影像和其他資源中獲取的巨大的空間數據急速增長。由于巨大的數據數量級和數據類型的復雜度，提升數據挖掘的效率成為數據挖掘的重要挑戰。隨著數據規模和維度的增長，傳統的聚類算法不能滿足實際應用的要求。對于大規模數據來說，如何在聚類過程中快速尋找聚類中心以及如何合理合并子劃分數據，從而得到高效、準確的聚類結果，是目前大規模數據乃至大數據聚類算法存在的問題之一[4-6]。

由于自頂向下的網格劃分方法采取分而治之的策略，根據數據的分布對空間進行劃分，受到數據空間維度的影響較小，可以快速地將大型高維數據集中的簇分隔開，使問題規模不斷減小。基于網格的聚類算法包括：統計信息網格法(Statistical Information Grid, STING)[7]、小波聚類(WaveCluster)[8]、查詢聚類(Clustering in Quest, CLIQUE)[9], 以及其他改進的網格聚類算法(Statistical Information Grid+, STING+)[10]、基于層次方法的平衡迭代規約和聚類(Balanced Iterative Reducing and Clustering Using Hierarchies, BIRCH)[11-12]等算法。其中STING算法利用存儲在網格單元中的統計信息聚類；WaveCluster利用一種小波轉換方法來聚類；CLIQUE是一種在高緯數據空間中基于網格和密度的聚類方法。通常聚類使用的數據集中，各個類的密度差別很大，網格聚類中通常使用密度閾值來控制網格劃分的大小，從而導致網格聚類對于不同密度的數據聚類的效果不理想。

近年來，在《Science》上發表的密度峰值聚類(Density Peak Clustering, DPC)算法能夠有效、快速地發現任意形狀的簇[13]。該方法同時具有K中心點算法(K-medoids)[14-16]、基于密度的空間聚類(Density-Based Spatial Clustering of Applications with Noise, DBSCAN)算法[17-18]和均值漂移(Mean-Shift)[19]聚類的特點，簡潔新穎。DPC的核心思想在于對聚類中心點的計算，聚類中心點具有本身密度大和與其他密度更大的數據點之間的距離相對更大的特點。但密度峰值聚類算法是個典型的密度聚類算法，無法處理大規模數據集。

本文基于密度峰值聚類快速尋找中心的思想，提出一種網格粒化的聚類算法，通過網格對數據進行粒化，采用網格內樣本點的頻度作為每個網格的密度，避免了局部密度公式帶來的選取中心點失效的問題。由于采用網格化對數據進行統計頻度，即可以看成是將每一個網格內的樣本點進行粒化，因此適合于處理大規模數據。

1 相關定義

1.1 DPC聚類算法

密度峰值聚類算法的思想簡單新穎，首先計算每個點的兩個變量：局部密度和與高密度點之間的距離。對于聚類中心的選取是基于兩個基本假設：1)聚類中心的密度高于其鄰近的樣本點的密度；2)聚類中心與比其密度還高的聚類中心的距離相對較大。顯然，聚類中心點是局部密度和與高密度點之間的距離均較大的點，聚類過程中的聚類中心的數目可以很直觀地選取。在這樣的模型中，密度峰值聚類主要有兩個需要計算的量：局部密度ρ和相對距離δ。局部密度和相對距離的定義分別如下：

定義1[7]樣本點i的局部密度定義如下:

(1)

定義2[7]樣本點i的相對距離:

(2)

圖1(a)所示，為二維散點圖，其中樣本點編號代表自身的局部密度，不同的顏色代表不同的類。圖1(b)為以局部密度ρ為橫坐標和相對距離δ為縱坐標產生的圖1(a)的數據集對應的決策圖，決策圖為本文提供了一種手動選取聚類中心的啟發式方法。在圖1(b)中選擇同時具有較大局部密度和相對距離的點(矩形虛線框內的點)，由于這些點的密度較大，鄰域中的鄰居點較多，并且與比它密度更大的點的距離較遠，所以將這些點標記聚類中心。密度峰值聚類算法具體步驟如下。

算法1 密度峰值聚類算法[13]。

輸入 數據樣本集，樣本點之間的距離矩陣；

輸出 聚類個數M，Ck(k=1,2,…,M)。

1)輸入距離矩陣；

2)初始化參數dc；

3)計算每個點的局部密度ρ，相對距離δ以及鄰居點；

4)輸出決策圖，并選取聚類中心；

5)將非聚類中心進行歸類；

6)將剩下數據分為cluster core和cluster halos，并檢測噪聲點。

圖1 中心點選取例子Fig. 1 Example of choosing centers

由于算法在計算局部密度時，需要計算距離矩陣，假設有個N個數據樣本點，則計算和存儲這些距離的時空復雜度均為O(N2)；隨著數據量的增長，僅就計算和存儲距離矩陣而導致的巨大時空復雜度就變得難以接受，導致了該算法不適用于大規模數據。

1.2 STING網格聚類

STING聚類算法是一種典型的基于網格的聚類算法。文獻[7]將數據空間劃分為層次結構，也就是使用一個多級多層次的空間結構。空間的頂層是第一層，它的下一層是第二層，依此類推。第i層中的一個單元與它的第i+1層的子空間單元的集合保持一致。除了底層網格都有4個子空間單元，而子空間單元都是父單元的1/4。如圖2所示，為STING網絡結構，其頂層網格單元與全局數據空間的信息相一致。底層網格的大小依賴于網格數據的密度。根據經驗來選擇的尺寸，例如數據的平均數目，但是每個單元存在的數據數目從幾十到上千不等。此外，數據空間的層數可以改變，通過修改上一層單元的數目。除非特殊情況下，將使用4作為默認參數。文獻[7]假設空間為兩維空間，因為這樣比較容易推廣到高維模型層次結構。

STING聚類可以快速查詢網格區域的信息，包括相應區域的密度、面積、數據個數等。一般在空間數據集中，數據挖掘和知識發現是對隱藏知識、空間關系、那些并不明顯的興趣特征和模型的發掘。不管是理解空間數據，還是捕獲空間和非空間數據的本質問題，STING算法都具有很好的效果。此外，這種關系發現能以簡單的方式去展示數據，通過重組數據空間來認識數據含義，使算法達到高效的表現。

圖2 STING網格結構Fig. 2 Grid structure of STING

2 基于密度峰值的網格聚類

基于當前對大規模數據進行聚類存在的問題，本文基于密度峰值聚類快速尋找中心的思想，提出一種新的網格聚類思想，用于處理大規模數據。該思想主要分為以下3個方面。

2.1 數據空間的網格粒化

首先利用如算法2所示的STING網格劃分對數據進行粒化，以網格單元數據的統計信息代替原始的數據點，從而達到數據壓縮的目的。

算法2 STING網格劃分。

輸入 數據樣本集X={x1,x2,…,xn}。

輸出 網格單元集合G={g1,g2,…，gn}。

1)歸一化到D={d1,d2,…,dk}維數據空間中，使得[0,1]d?D，其中d是D的維度；

2)計算劃分的尺度參數ε，使用式(3)求出，并使用式(4)進行維度劃分，進而進行數據空間的網格劃分；

3)掃描整個數據集，把數據集中的每個點都放入網格劃分后的數據空間中，并記錄網格單元的信息(如：網格空間的數據點個數等)，記錄網格單元的個數為n。

其中參數ε為網格劃分尺度。網格劃分的粒度不同會影響數據聚類的效果，不能太大也不能太小: 太大會丟失大多網格單元的數據，導致精確度不夠；網格單元太小，會導致每個網格密度相似，不能區分稠密網格單元，同時，網格太小，如每個網格一個數據，就會導致跟原數據處理效果類似，達不到快速處理數據的目的。參數ε根據數據空間中的數據個數求得:

ε=N/k

(3)

(4)

(5)

(6)

(7)

假設數據集為X={x1,x2,…,xN}是在D={d1,d2,…,dk}維空間的數據，其中N是數據集合中數據點的個數，k是數據空間維度的個數(數據屬性的個數),則每個維度被分為ε等分，所以每個維度劃分為：

di={c1,c2,…,cε}

(8)

2.2 中心單元的計算

該步驟的目的是在粒化后的所有網格單元中快速找出符合假設條件的中心點。首先，掃描整個數據集，即將網格單元中數據點的個數作為網格單元的頻度；然后，利用聚類中心網格單元與其他聚類中心網格單元的距離大，而與其網格單元類簇中其他網格單元的距離小的思路，求出各個網格單元的相對距離。算法步驟如下。

算法3 快速尋找中心單元算法。

輸入 網格單元集合G={g1,g2,…,gn}。

輸出 中心單元Centerk(k=1,2, …,M)。

1)計算網格單元的密度ρi，即網格單元i中的數據點個數。

(9)

其中distqiqj代表網格單元qi和qj的歐氏距離。公式如下：

distab=

(10)

其中：a、b分別為兩個網格空間單元；di為空間單元的維度。

3)得出決策圖，并選擇中心單元。

例1 如圖3所示，通過網格粒化后，大部分數據點(除中心網格單元)重合在一起。這是因為非中心網格單元離它們最近的網格單元一般為相鄰網格，這就導致許多網格單元重合在一起，這也方便我們選取中心網格單元。圖4為利用密度峰值的思想，得到的網格單元對應的決策圖，很明顯，有7個中心網格單元。

圖3 網格粒化后的數據分布Fig. 3 Data distribution by grid granulation

圖4 網格單元的決策圖Fig. 4 Decision diagram of grid cells

2.3 網格單元的歸類

算法4 基于密度峰值的網格聚類。

輸入 數據樣本集X={x1,x2,…，xn}。

輸出 聚類結果。

1)數據預處理，為了統一量綱，本文對數據集進行歸一化處理[0,1]，得出歸一化后的數據集Data={x1,x2,…,xN};

2)調用算法2，根據網格劃分技術，將數據空間劃分為均勻的網格空間;

3)掃描數據集X={x1,x2,…，xN}，將數據點分配到相應的網格單元中，并統計各個網格單元的密度信息；

4)設置密度閾值τ把噪聲網格單元剔除，網格密度小于τ的網格單元標記為無效網格單元；

5)調用算法3計算網格中心單元，得出決策圖并選取出中心單元：

6)分配各個網格單元到各個類簇中，掃描整個數據空間，將網格單元中的數據點標記為相應的類別。

3 算法分析

本文提出算法的時間開銷包括計算網格粒化、網格單元的統計信息、網格單元的相對距離和分配到各個類簇中。其中花銷最大的就是求網格單元的距離。 STING劃分網格時間復雜度為O(n)，其行為花銷在于統計數據集中數據點的個數。求網格單元的統計信息的時間花銷也僅僅在于掃描一次數據，更新每個網格單元的統計信息，其時間復雜度也為O(n)。將網格單元的分配到各個類簇中僅與網格單元的個數相關，需要掃描整個網格空間，得到網格單元到每個聚類中心的距離，然后分配到相離最近的中心網格單元，其時間復雜度僅為O(R),其中R為網格單元個數。本算法最大的開銷在于求網格單元之間的距離，根據網格的個數，求除網格單元之間的距離，時間復雜度為O((n/ε)2)，其中n為數據點數，ε為劃分網格的參數。因此，算法的總的時間復開銷為：

Tall=O(n)+O(n)+O(n/ε)+O(n/ε)2

(11)

由式(4)可以看出，本文算法的時間復雜度為O((n/ε)2)。而DPC卻需要求出整個點與點之間的距離，其時間復雜度為O(n2)。同理，由文獻[13]可知，由于DPC的空間復雜度為O(n2)，而本文算法空間復雜度只跟網格單元的個數相關，因此其空間復雜度為O((n/ε)2)。

4 實驗仿真

本文實驗所采用的計算機硬件配置為Intel Core i5處理器(主頻3.3 GHz)、8 GB內存；實驗的軟件環境為Windows10操作系統，采用Matlab編譯環境。為了證明相對于DPC本文算法具有優越性，設計了實驗1來進行對比驗證。因為在DPC中，Matlab所處理的數據不能超過7 000條，因此本文采用小規模數據集來與DPC進行對比實驗。

實驗1 采用UCI上面的4個人工數據集(Aggregation、Compound、Flame和Moons)進行實驗，其中圖5分別為4個數據集的數據分布。

圖5 4個數據集的數據分布Fig. 5 Data distribution of four data sets

圖6為網格粒化后的數據分布，由圖6可以看出，聚類結果基本符合圖5中的數據分布情況。

圖6 網格粒化后的數據分布Fig. 6 Data distribution by grid granulation

表1分別給出了本文提出的聚類算法與原始密度峰值算法的時間和準確率對比情況。

表1本文與原始密度峰值算法性能對比

Tab. 1 Performance comparison of the proposed and original density clustering algorithms

通過表1可知，本文算法雖然時間上遠少于DPC聚類算法，但是精確度卻比DPC差，根本原因是本文算法通過網格粒化減小數據規模的同時也減小網格分辨率，從而降低了精度，即通過犧牲精度來換取時間的減少。相對于STING聚類來說，在圖5的4個數據集上本文算法的時間較少，在Aggregation、Compound、Flame三個數據集上準確率相對較高，而且由表1可知，STING聚類算法穩定性較差。綜合考慮，本文算法雖然精確度有所不足，但在粗粒度情形下可以處理大型數據集，處理速度快。而DPC不能處理大型數據集，處理速度緩慢成為它致命的缺點。因此，在對精確度要求不太高的情況下，本文算法還是有一定的價值。

實驗2將采用大規模的數據集來測試本文算法在處理大規模數據上的性能。

實驗2 如圖7(a)所示，為本文實驗采用的測試數據集，使用人工生成的Moons數據集，共100萬條數據。

圖7(b)為網格粒化后的數據分布，由圖8可以看出，聚類結果基本符合圖7中的數據分布情況。

圖7 100萬條Moons數據分布及其聚類結果Fig. 7 Distribution of one million Moons data and its clustering results

通過仿真發現，本文提出的基于密度峰值的網格粒化算法在100萬條數據的Moons數據集上總運行時間為15.435 665 s，準確率為92.5%。由實驗2可以發現，本文算法對處理大規模數據有著明顯的優勢，但是因為基于網格的算法，準確率會有明顯下降的趨勢。

5 結語

基于密度峰值聚類算法可以發現任意簇且可以快速尋找聚類中心點的優點，本文提出了一種改進的網格聚類方法，既有DPC算法的優點，也具有網格聚類可以處理大規模數據的優點，同時在滿足一定的時限約束條件下，本文算法取得了較滿意的效果，初步實現了一種快速處理大規模數據的聚類算法模型。下一步工作需要研究在不同網格粒度對聚類結果的影響，以及結合Spark平臺將算法推廣到處理大數據上。

References)

[1] KITAMOTO A. Data mining for typhoon image collection[C]// Proceedings of the 2nd International Workshop on Multimedia Data Mining. New York: ACM, 2002: 68-77.

[2] BELLAZZI R, ZUPAN B. Predictive data mining in clinical medicine: current issues and guidelines[J]. International Journal of Medical Informatics, 2008, 77(2): 81-97.

[3] MATTHEWS B, DAS S, BHADURI K, et al. Discovering anomalous aviation safety events using scalable data mining algorithms[J]. Journal of Aerospace Computing Information and Communication, 2014, 11(7):482-482.

[4] TAKIZAWA H, KOBAYASHI H. Hierarchical parallel processing of large scale data clustering on a PC cluster with GPU co-processing[J]. Journal of Supercomputing, 2006, 36(3): 219-234.

[5] CUI X, CHARLES J S, POTOK T E. The GPU enhanced parallel computing for large scale data clustering[J]. Future Generation Computer Systems, 2013, 29(7):1736-1741.

[6] LI Y, YANG G, HE H, et al. A study of large-scale data clustering based on fuzzy clustering[J]. Soft Computing, 2016, 20(8):3231-3242.

[7] WANG W, YANG J, MUNTZ R R. STING: a statistical information grid approach to spatial data mining[C]// Proceedings of the 23rd International Conference on Very Large Data Bases. San Francisco, CA: Morgan Kaufmann, 1997: 186-195.

[8] CHEN L, YU T, CHIRKOVA R. Wave cluster with differential privacy[C]// Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. New York: ACM, 2015:1011-1020.

[9] DUAN D, LI Y, LI R, et al. Incremental K-clique clustering in dynamic social networks[J]. Artificial Intelligence Review, 2012, 38(2):129-147.

[10] WANG W, YANG J, MUNTZ R. STING+: an approach to active spatial data mining[C]// Proceedings of the 15th International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 1999:116.

[11] ZHANG T, RAMAKRISHNAN R, LIVNY M. BIRCH: an efficient data clustering method for very large databases[J]. ACM SIGMOD Record, 1996, 25(2): 103-114.

[12] HODGE V J, AUSTIN J. A survey of outlier detection methodologies[J]. Artificial Intelligence Review, 2004, 22(2):85-126.

[13] RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J].Science, 2014, 344(6191)：1492-1496.

[14] PARK H, JUN C. A simple and fast algorithm forK-medoids clustering[J]. Expert Systems with Applications, 2009, 36(2):3336-3341.

[15] 馬箐, 謝娟英. 基于粒計算的K-medoids聚類算法[J]. 計算機應用, 2012, 32(7):1973-1977.(MA Q, XIE J Y. NewK-medoids clustering algorithm based on granular computing[J]. Journal of Computer Applications, 2012, 32(7): 1973-1977.)

[16] 張雪萍, 龔康莉, 趙廣才. 基于MapReduce的K-Medoids并行算法[J]. 計算機應用, 2013, 33(4):1023-1025. (ZHANG X P, GONG K L, ZHAO G C. ParallelK-Medoids algorithm based on MapReduce[J]. Journal of Computer Applications, 2013, 33(4):1023-1025.)

[17] ESTER B, KRIEGEL H, SANDER J, et al. A density based algorithm for discovering clusters in large spatial databases[C]// Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. Menlo Park, CA: AAAI Press, 1996: 226-231.

[18] 周水庚, 周傲英, 金文,等. FDBSCAN:一種快速 DBSCAN算法[J]. 軟件學報, 2000, 15(6):735-744.(ZHOU S G, ZHOU A Y, JIN W, et al. FDBSCAN: a fast DBSCAN algorithm[J]. Journal of Software, 2000, 15(6): 735-744.)

[19] SARAGIH J, LUCEY S, COHN J F. Deformable model fitting by regularized landmark mean-shift[J]. International Journal of Computer Vision, 2011, 91(2):200-215.

This work is partially supported by the National Natural Science Foundation of China (61572091), the Chongqing Postgraduate Scientific Research and Innovation Project (CYB16106), the High-end Talent Project (RC2016005), the Key Discipline Project of Guizhou Province (QXWB[2013]18).

YANGJie, born in 1987, Ph. D. candidate. His research interests include granular computing, rough set, data mining.

WANGGuoyin, born in 1970, Ph. D., professor. His research interests include granular computing, soft computing, cognitive computing.

WANGFei, born in 1989, M.S. candidate. His research interests include data mining, granular computing.

Gridclusteringalgorithmbasedondensitypeaks

YANG Jie1,2, WANG Guoyin1*, WANG Fei1

(1.ChongqingKeyLaboratoryofComputationalIntelligence(ChongqingUniversityofPostsandTelecommunications),Chongqing400065,China;2.SchoolofPhysicsandElectronics,ZunyiNormalUniversity,ZunyiGuizhou563002,China)

The Density Peak Clustering (DPC) algorithm which required few parameters and no iteration was proposed in 2014, it was simple and novel. In this paper, a grid clustering algorithm which could efficiently deal with large-scale data was proposed based on DPC. Firstly, theNdimensional space was divided into disjoint rectangular units, and the unit space information was counted. Then the central cells of space was found based on DPC, namely, the central cells were surrounded by other grid cells of low local density, and the distance with grid cells of high local density was relatively large. Finally, the grid cells adjacent to their central cells were merged to obtain the clustering results. The experimental results on UCI artificial data set show that the proposed algorithm can quickly find the clustering centers, and effectively deal with the clustering problem of large-scale data, which has a higher efficiency compared with the original density peak clustering algorithm on different data sets, reducing the loss of time 10 to 100 times, and maintaining the loss of accuracy at 5% to 8%.

density peak; grid granulation; large-scale data; clustering

2017- 05- 16;

2017- 06- 14。

國家自然科學基金資助項目(61572091);重慶市研究生科研創新項目(CYB16106);高端人才項目 (RC2016005);貴州省級重點學科(黔學位辦[2013]18號)。

楊潔(1987—)，男，貴州遵義人，博士研究生，主要研究方向：粒計算、粗糙集、數據挖掘； 王國胤(1970—)，男，重慶人，教授，博士，CCF會員，主要研究方向：粒計算、軟計算、認知計算； 王飛(1989—)，男，河南開封人，碩士研究生，主要研究方向：數據挖掘、粒計算。

1001- 9081(2017)11- 3080- 05

10.11772/j.issn.1001- 9081.2017.11.3080

(*通信作者電子郵箱wanggy@ieee.org)

TP311

A