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

楊 潔, 王國(guó)胤, 王 飛

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

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

楊 潔1,2, 王國(guó)胤1*, 王 飛1

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

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

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

0 引言

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

由于自頂向下的網(wǎng)格劃分方法采取分而治之的策略，根據(jù)數(shù)據(jù)的分布對(duì)空間進(jìn)行劃分，受到數(shù)據(jù)空間維度的影響較小，可以快速地將大型高維數(shù)據(jù)集中的簇分隔開，使問(wèn)題規(guī)模不斷減小?；诰W(wǎng)格的聚類算法包括：統(tǒng)計(jì)信息網(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算法利用存儲(chǔ)在網(wǎng)格單元中的統(tǒng)計(jì)信息聚類；WaveCluster利用一種小波轉(zhuǎn)換方法來(lái)聚類；CLIQUE是一種在高緯數(shù)據(jù)空間中基于網(wǎng)格和密度的聚類方法。通常聚類使用的數(shù)據(jù)集中，各個(gè)類的密度差別很大，網(wǎng)格聚類中通常使用密度閾值來(lái)控制網(wǎng)格劃分的大小，從而導(dǎo)致網(wǎng)格聚類對(duì)于不同密度的數(shù)據(jù)聚類的效果不理想。

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

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

1 相關(guān)定義

1.1 DPC聚類算法

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

定義1[7]樣本點(diǎn)i的局部密度定義如下:

(1)

定義2[7]樣本點(diǎn)i的相對(duì)距離:

(2)

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

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

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

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

1)輸入距離矩陣；

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

3)計(jì)算每個(gè)點(diǎn)的局部密度ρ，相對(duì)距離δ以及鄰居點(diǎn)；

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

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

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

圖1 中心點(diǎn)選取例子Fig. 1 Example of choosing centers

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

1.2 STING網(wǎng)格聚類

STING聚類算法是一種典型的基于網(wǎng)格的聚類算法。文獻(xiàn)[7]將數(shù)據(jù)空間劃分為層次結(jié)構(gòu)，也就是使用一個(gè)多級(jí)多層次的空間結(jié)構(gòu)?？臻g的頂層是第一層，它的下一層是第二層，依此類推。第i層中的一個(gè)單元與它的第i+1層的子空間單元的集合保持一致。除了底層網(wǎng)格都有4個(gè)子空間單元，而子空間單元都是父單元的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)驗(yàn)來(lái)選擇的尺寸，例如數(shù)據(jù)的平均數(shù)目，但是每個(gè)單元存在的數(shù)據(jù)數(shù)目從幾十到上千不等。此外，數(shù)據(jù)空間的層數(shù)可以改變，通過(guò)修改上一層單元的數(shù)目。除非特殊情況下，將使用4作為默認(rèn)參數(shù)。文獻(xiàn)[7]假設(shè)空間為兩維空間，因?yàn)檫@樣比較容易推廣到高維模型層次結(jié)構(gòu)。

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

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

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

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

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

首先利用如算法2所示的STING網(wǎng)格劃分對(duì)數(shù)據(jù)進(jìn)行?；?，以網(wǎng)格單元數(shù)據(jù)的統(tǒng)計(jì)信息代替原始的數(shù)據(jù)點(diǎn)，從而達(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)計(jì)算劃分的尺度參數(shù)ε，使用式(3)求出，并使用式(4)進(jìn)行維度劃分，進(jìn)而進(jìn)行數(shù)據(jù)空間的網(wǎng)格劃分；

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

其中參數(shù)ε為網(wǎng)格劃分尺度。網(wǎng)格劃分的粒度不同會(huì)影響數(shù)據(jù)聚類的效果，不能太大也不能太小: 太大會(huì)丟失大多網(wǎng)格單元的數(shù)據(jù)，導(dǎo)致精確度不夠；網(wǎng)格單元太小，會(huì)導(dǎo)致每個(gè)網(wǎng)格密度相似，不能區(qū)分稠密網(wǎng)格單元，同時(shí)，網(wǎng)格太小，如每個(gè)網(wǎng)格一個(gè)數(shù)據(jù)，就會(huì)導(dǎo)致跟原數(shù)據(jù)處理效果類似，達(dá)不到快速處理數(shù)據(jù)的目的。參數(shù)ε根據(jù)數(shù)據(jù)空間中的數(shù)據(jù)個(gè)數(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ù)點(diǎn)的個(gè)數(shù)，k是數(shù)據(jù)空間維度的個(gè)數(shù)(數(shù)據(jù)屬性的個(gè)數(shù)),則每個(gè)維度被分為ε等分，所以每個(gè)維度劃分為：

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

(8)

2.2 中心單元的計(jì)算

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

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

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

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

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

(9)

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

distab=

(10)

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

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

例1 如圖3所示，通過(guò)網(wǎng)格?；?，大部分?jǐn)?shù)據(jù)點(diǎn)(除中心網(wǎng)格單元)重合在一起。這是因?yàn)榉侵行木W(wǎng)格單元離它們最近的網(wǎng)格單元一般為相鄰網(wǎng)格，這就導(dǎo)致許多網(wǎng)格單元重合在一起，這也方便我們選取中心網(wǎng)格單元。圖4為利用密度峰值的思想，得到的網(wǎng)格單元對(duì)應(yīng)的決策圖，很明顯，有7個(gè)中心網(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)一量綱，本文對(duì)數(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ù)點(diǎn)分配到相應(yīng)的網(wǎng)格單元中，并統(tǒng)計(jì)各個(gè)網(wǎng)格單元的密度信息；

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

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

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

3 算法分析

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

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

(11)

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

4 實(shí)驗(yàn)仿真

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

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

圖5 4個(gè)數(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分別給出了本文提出的聚類算法與原始密度峰值算法的時(shí)間和準(zhǔn)確率對(duì)比情況。

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

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

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

實(shí)驗(yàn)2將采用大規(guī)模的數(shù)據(jù)集來(lái)測(cè)試本文算法在處理大規(guī)模數(shù)據(jù)上的性能。

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

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

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

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

5 結(jié)語(yǔ)

基于密度峰值聚類算法可以發(fā)現(xiàn)任意簇且可以快速尋找聚類中心點(diǎn)的優(yōu)點(diǎn)，本文提出了一種改進(jìn)的網(wǎng)格聚類方法，既有DPC算法的優(yōu)點(diǎn)，也具有網(wǎng)格聚類可以處理大規(guī)模數(shù)據(jù)的優(yōu)點(diǎn)，同時(shí)在滿足一定的時(shí)限約束條件下，本文算法取得了較滿意的效果，初步實(shí)現(xiàn)了一種快速處理大規(guī)模數(shù)據(jù)的聚類算法模型。下一步工作需要研究在不同網(wǎng)格粒度對(duì)聚類結(jié)果的影響，以及結(jié)合Spark平臺(tái)將算法推廣到處理大數(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] 馬箐, 謝娟英. 基于粒計(jì)算的K-medoids聚類算法[J]. 計(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ì)算機(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é)報(bào), 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。

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

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

1001- 9081(2017)11- 3080- 05

10.11772/j.issn.1001- 9081.2017.11.3080

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

TP311

A