楊 潔, 王國胤, 王 飛

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

基于密度峰值的網(wǎng)格聚類算法

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

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

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

密度峰值；網(wǎng)格粒化；大規(guī)模數(shù)據(jù); 聚類

0 引言

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

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

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

本文基于密度峰值聚類快速尋找中心的思想，提出一種網(wǎng)格?；木垲愃惴?，通過網(wǎng)格對數(shù)據(jù)進(jìn)行粒化，采用網(wǎng)格內(nèi)樣本點的頻度作為每個網(wǎng)格的密度，避免了局部密度公式帶來的選取中心點失效的問題。由于采用網(wǎng)格化對數(shù)據(jù)進(jìn)行統(tǒng)計頻度，即可以看成是將每一個網(wǎng)格內(nèi)的樣本點進(jìn)行?；?，因此適合于處理大規(guī)模數(shù)據(jù)。

1 相關(guān)定義

1.1 DPC聚類算法

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

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

(1)

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

(2)

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

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

輸入 數(shù)據(jù)樣本集，樣本點之間的距離矩陣；

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

1)輸入距離矩陣；

2)初始化參數(shù)dc；

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

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

5)將非聚類中心進(jìn)行歸類；

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

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

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

1.2 STING網(wǎng)格聚類

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

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

圖2 STING網(wǎng)格結(jié)構(gòu)Fig. 2 Grid structure of STING

2 基于密度峰值的網(wǎng)格聚類

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

2.1 數(shù)據(jù)空間的網(wǎng)格?；?/h3>

首先利用如算法2所示的STING網(wǎng)格劃分對數(shù)據(jù)進(jìn)行?；跃W(wǎng)格單元數(shù)據(jù)的統(tǒng)計信息代替原始的數(shù)據(jù)點，從而達(dá)到數(shù)據(jù)壓縮的目的。

算法2 STING網(wǎng)格劃分。

輸入 數(shù)據(jù)樣本集X={x1,x2,…,xn}。

輸出 網(wǎng)格單元集合G={g1,g2,…，gn}。

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

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

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

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

ε=N/k

(3)

(4)

(5)

(6)

(7)

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

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

(8)

2.2 中心單元的計算

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

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

輸入 網(wǎng)格單元集合G={g1,g2,…,gn}。

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

1)計算網(wǎng)格單元的密度ρi，即網(wǎng)格單元i中的數(shù)據(jù)點個數(shù)。

(9)

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

distab=

(10)

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

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

例1 如圖3所示，通過網(wǎng)格?；螅蟛糠?jǐn)?shù)據(jù)點(除中心網(wǎng)格單元)重合在一起。這是因為非中心網(wǎng)格單元離它們最近的網(wǎng)格單元一般為相鄰網(wǎng)格，這就導(dǎo)致許多網(wǎng)格單元重合在一起，這也方便我們選取中心網(wǎng)格單元。圖4為利用密度峰值的思想，得到的網(wǎng)格單元對應(yīng)的決策圖，很明顯，有7個中心網(wǎng)格單元。

圖3 網(wǎng)格?；蟮臄?shù)據(jù)分布Fig. 3 Data distribution by grid granulation

圖4 網(wǎng)格單元的決策圖Fig. 4 Decision diagram of grid cells

2.3 網(wǎng)格單元的歸類

算法4 基于密度峰值的網(wǎng)格聚類。

輸入 數(shù)據(jù)樣本集X={x1,x2,…，xn}。

輸出 聚類結(jié)果。

1)數(shù)據(jù)預(yù)處理，為了統(tǒng)一量綱，本文對數(shù)據(jù)集進(jìn)行歸一化處理[0,1]，得出歸一化后的數(shù)據(jù)集Data={x1,x2,…,xN};

2)調(diào)用算法2，根據(jù)網(wǎng)格劃分技術(shù)，將數(shù)據(jù)空間劃分為均勻的網(wǎng)格空間;

3)掃描數(shù)據(jù)集X={x1,x2,…，xN}，將數(shù)據(jù)點分配到相應(yīng)的網(wǎng)格單元中，并統(tǒng)計各個網(wǎng)格單元的密度信息；

4)設(shè)置密度閾值τ把噪聲網(wǎng)格單元剔除，網(wǎng)格密度小于τ的網(wǎng)格單元標(biāo)記為無效網(wǎng)格單元；

5)調(diào)用算法3計算網(wǎng)格中心單元，得出決策圖并選取出中心單元：

6)分配各個網(wǎng)格單元到各個類簇中，掃描整個數(shù)據(jù)空間，將網(wǎng)格單元中的數(shù)據(jù)點標(biāo)記為相應(yīng)的類別。

3 算法分析

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

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

(11)

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

4 實驗仿真

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

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

圖5 4個數(shù)據(jù)集的數(shù)據(jù)分布Fig. 5 Data distribution of four data sets

圖6為網(wǎng)格?；蟮臄?shù)據(jù)分布，由圖6可以看出，聚類結(jié)果基本符合圖5中的數(shù)據(jù)分布情況。

圖6 網(wǎng)格粒化后的數(shù)據(jù)分布Fig. 6 Data distribution by grid granulation

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

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

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

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

實驗2將采用大規(guī)模的數(shù)據(jù)集來測試本文算法在處理大規(guī)模數(shù)據(jù)上的性能。

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

圖7(b)為網(wǎng)格?；蟮臄?shù)據(jù)分布，由圖8可以看出，聚類結(jié)果基本符合圖7中的數(shù)據(jù)分布情況。

圖7 100萬條Moons數(shù)據(jù)分布及其聚類結(jié)果Fig. 7 Distribution of one million Moons data and its clustering results

通過仿真發(fā)現(xiàn)，本文提出的基于密度峰值的網(wǎng)格粒化算法在100萬條數(shù)據(jù)的Moons數(shù)據(jù)集上總運行時間為15.435 665 s，準(zhǔn)確率為92.5%。由實驗2可以發(fā)現(xiàn)，本文算法對處理大規(guī)模數(shù)據(jù)有著明顯的優(yōu)勢，但是因為基于網(wǎng)格的算法，準(zhǔn)確率會有明顯下降的趨勢。

5 結(jié)語

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

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]. 計算機(jī)應(yīng)用, 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]. 計算機(jī)應(yīng)用, 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]. 軟件學(xué)報, 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。

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

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

1001- 9081(2017)11- 3080- 05

10.11772/j.issn.1001- 9081.2017.11.3080

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

TP311

A