鞏樹鳳　　　張巖峰

(東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院　沈陽(yáng)　110819)(shidashufeng@163.com)

?

EDDPC：一種高效的分布式密度中心聚類算法

鞏樹鳳張巖峰

(東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院沈陽(yáng)110819)(shidashufeng@163.com)

摘要聚類分析是數(shù)據(jù)挖掘中經(jīng)常用到的一種分析數(shù)據(jù)之間關(guān)系的方法.它把數(shù)據(jù)對(duì)象集合劃分成多個(gè)不同的組或簇，每個(gè)簇內(nèi)的數(shù)據(jù)對(duì)象之間的相似性要高于與其他簇內(nèi)的對(duì)象的相似性.密度中心聚類算法是一個(gè)最近發(fā)表在《Science》上的新型聚類算法，它通過(guò)評(píng)估每個(gè)數(shù)據(jù)對(duì)象的2個(gè)屬性值(密度值ρ和斥群值δ)來(lái)進(jìn)行聚類.相對(duì)于其他傳統(tǒng)聚類算法，它的優(yōu)越性體現(xiàn)在交互性、無(wú)迭代性、無(wú)數(shù)據(jù)分布依賴性等方面.但是密度中心聚類算法在計(jì)算每個(gè)數(shù)據(jù)對(duì)象的密度值和斥群值時(shí)，需要O(N2)復(fù)雜度的距離計(jì)算，當(dāng)處理海量高維數(shù)據(jù)時(shí)，該算法的效率會(huì)受到很大的影響.為了提高該算法的效率和擴(kuò)展性，提出一種高效的分布式密度中心聚類算法EDDPC (efficient distributed density peaks clustering)，它利用Voronoi分割與合理的數(shù)據(jù)復(fù)制及過(guò)濾，避免了大量無(wú)用的距離計(jì)算開銷和數(shù)據(jù)傳輸開銷.實(shí)驗(yàn)結(jié)果顯示:與簡(jiǎn)單的MapReduce分布式實(shí)現(xiàn)比較，EDDPC可以達(dá)到40倍左右的性能提升.

關(guān)鍵詞密度中心；數(shù)據(jù)聚類；Voronoi分割；MapReduce；大數(shù)據(jù)

聚類在很多應(yīng)用中是一種基礎(chǔ)的數(shù)據(jù)分析方法，例如社會(huì)網(wǎng)絡(luò)分析、智能商務(wù)、圖像模式識(shí)別、Web搜索和生物學(xué)等.當(dāng)前存在很多聚類算法[1]，這其中包括基于劃分的方法(如k-medoids[2]，k-means[3])、基于層次的方法(如AGNES[4])、基于密度的方法(如DBASCAN[5])、基于網(wǎng)格的方法(如STING[6])，還有面向大數(shù)據(jù)的快速自適應(yīng)同步聚類算法FAKCS[7]等.

密度中心聚類算法[8]是由Alex和Alessandro最近在《Science》上提出的一個(gè)新型聚類算法.它區(qū)別于其他聚類算法，基于2點(diǎn)假設(shè)進(jìn)行設(shè)計(jì)：1)聚類中心點(diǎn)的密度不低于它附近點(diǎn)的密度；2)聚類中心點(diǎn)與密度比它大的點(diǎn)(另一個(gè)聚類中的點(diǎn))的距離非常遠(yuǎn).在該算法的設(shè)計(jì)中每個(gè)點(diǎn)有2個(gè)屬性: 1)密度值ρ；2)斥群值δ(與密度值比自己大的點(diǎn)的距離的最小值).密度值ρ越大說(shuō)明該點(diǎn)越有可能是聚類中心，斥群值δ越大說(shuō)明該點(diǎn)越有可能代表一個(gè)新的聚類，而只有當(dāng)密度值ρ和斥群值δ都較大時(shí)，該點(diǎn)才更可能是某一個(gè)聚類的密度中心.算法根據(jù)這2個(gè)值的大小來(lái)選擇密度中心點(diǎn).

相對(duì)于諸多傳統(tǒng)聚類算法，密度中心聚類算法具有3個(gè)優(yōu)點(diǎn)：

1) 交互性.不同于k-means等聚類算法，要求用戶在算法執(zhí)行前指定聚類的個(gè)數(shù)k.密度中心聚類算法在計(jì)算出每個(gè)點(diǎn)的密度值ρ和斥群值δ之后，由用戶根據(jù)ρ值和δ值來(lái)確定聚類的個(gè)數(shù).

2) 無(wú)迭代性.與其他算法(例如EM clustering和k-means)相比，該算法只需要遍歷1次數(shù)據(jù)集即可完成，不需要多次迭代.

3) 無(wú)數(shù)據(jù)分布依賴性.算法的聚類形狀沒(méi)有偏倚，可以適用于多種環(huán)境下數(shù)據(jù)的聚類[1].

盡管密度中心聚類算法有以上諸多優(yōu)點(diǎn)，但是計(jì)算密度值ρ和斥群值δ需要測(cè)量數(shù)據(jù)集中任意2點(diǎn)之間的歐氏距離，復(fù)雜度為O(N2).當(dāng)處理海量高維數(shù)據(jù)時(shí)，算法的實(shí)現(xiàn)涉及到大量的高維歐氏距離計(jì)算，造成大量的計(jì)算開銷，使其無(wú)法在單機(jī)環(huán)境下運(yùn)行，嚴(yán)重影響了算法的實(shí)用性.

針對(duì)以上問(wèn)題，為了提高算法執(zhí)行效率，本文基于MapReduce[9]實(shí)現(xiàn)了簡(jiǎn)單分布式密度中心聚類(simple distributed density peaks clustering, SDDPC)算法，該算法雖然可以利用多臺(tái)節(jié)點(diǎn)分布式執(zhí)行算法，但是仍然需要大量的距離計(jì)算開銷和數(shù)據(jù)傳輸開銷.我們把它作為待比較的基準(zhǔn)方法，并提出了一種高效的分布式密度中心聚類(efficient distributed density peaks clustering, EDDPC)算法.它首先利用Voronoi分割將數(shù)據(jù)集分成幾個(gè)互不相交的組，由于對(duì)象的密度值ρ和斥群值δ的計(jì)算可能會(huì)用到其他組中的數(shù)據(jù)，本文提出了高效的數(shù)據(jù)復(fù)制過(guò)濾模型，將一少部分滿足特定條件的數(shù)據(jù)在分組間復(fù)制，過(guò)濾掉無(wú)用數(shù)據(jù).各分組并行地根據(jù)分配數(shù)據(jù)和部分復(fù)制數(shù)據(jù)，在分組內(nèi)局部計(jì)算各點(diǎn)的密度值ρ和斥群值δ，并從理論上保證結(jié)果的正確性，從而大大提高了算法的執(zhí)行效率和可擴(kuò)展性.

本文的主要貢獻(xiàn)如下：

1) 提出了一種基于MapReduce的高效分布式密度中心聚類算法EDDPC，并且在開源的Hadoop框架上實(shí)現(xiàn)了該算法.

2) 針對(duì)ρ值計(jì)算，設(shè)計(jì)了一種數(shù)據(jù)復(fù)制模型；針對(duì)δ值計(jì)算，設(shè)計(jì)了2種數(shù)據(jù)過(guò)濾模型，從而減少了數(shù)據(jù)對(duì)象的復(fù)制量和距離計(jì)算量，提高了算法的執(zhí)行效率.

3) 在多個(gè)真實(shí)數(shù)據(jù)集上對(duì)分布式密度中心聚類算法進(jìn)行了實(shí)驗(yàn)和性能評(píng)估，實(shí)驗(yàn)結(jié)果驗(yàn)證了該算法的高效性.

1相關(guān)工作

本節(jié)首先簡(jiǎn)單介紹一下密度中心聚類算法，然后介紹用到的MapReduce編程模型和Voronoi圖數(shù)據(jù)分割法.

1.1密度中心聚類算法介紹

密度中心聚類算法[8]基于數(shù)據(jù)點(diǎn)的密度值ρ和斥群值δ來(lái)對(duì)數(shù)據(jù)集進(jìn)行聚類.

數(shù)據(jù)點(diǎn)i的密度值ρi為

(1)

其中，χ(x)是一個(gè)函數(shù)，當(dāng)x< 0時(shí)，χ(x)=1，否則χ(x)=0；dij是點(diǎn)j到點(diǎn)i的距離；dc是一個(gè)距離臨界值.也就是說(shuō)，ρi為與點(diǎn)i的距離小于dc的點(diǎn)的個(gè)數(shù).

點(diǎn)i的斥群值δi為

(2)

它代表與密度值比自己大的點(diǎn)的距離的最小值.假設(shè)密度比ρi大的點(diǎn)中，點(diǎn)j距離點(diǎn)i最近，那么δi=dij，而點(diǎn)j就是點(diǎn)i的依附點(diǎn)σi，

說(shuō)明點(diǎn)i可以依附點(diǎn)j，歸屬于點(diǎn)j所屬聚類.斥群值δi越小，點(diǎn)i距離點(diǎn)j越近，這種依附可能性越大，代表點(diǎn)i越有可能歸屬于點(diǎn)j所屬的聚類；斥群值δi越大，點(diǎn)i距離點(diǎn)j越遠(yuǎn)依附性越小，說(shuō)明點(diǎn)i很有可能是離群點(diǎn)或者是屬于另一個(gè)聚類.當(dāng)某個(gè)點(diǎn)m的密度值ρm是所有點(diǎn)中密度最大值，那么點(diǎn)m的斥群值δm=maxj(dmj).

密度中心聚類算法將每個(gè)數(shù)據(jù)點(diǎn)的ρ值和δ值表示在一個(gè)2維決策圖(decision graph)上.如圖1(a)展示了一個(gè)數(shù)據(jù)集的分布情況；圖1(b)是根據(jù)圖1(a)中每個(gè)點(diǎn)的ρ值和δ值繪制成的決策圖.用戶根據(jù)決策圖中數(shù)據(jù)點(diǎn)的分布情況，圈出ρ值和δ值都很大的數(shù)據(jù)點(diǎn)作為密度中心，即決策圖中右上角的部分?jǐn)?shù)據(jù)點(diǎn).由于在計(jì)算δ值時(shí)已經(jīng)記錄了每個(gè)數(shù)據(jù)點(diǎn)的依附點(diǎn)，可以根據(jù)數(shù)據(jù)點(diǎn)的依附關(guān)系并由用戶選取的密度中心反推出每個(gè)數(shù)據(jù)點(diǎn)的所屬聚類.

Fig. 1　Density peaks clustering.圖1　密度中心聚類算法

1.2基于Voronoi圖的分割法

Voronoi圖，又叫泰森多邊形或Dirichlet圖，是一個(gè)關(guān)于空間劃分的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu).基于Voronoi圖的劃分是指在給定的數(shù)據(jù)對(duì)象集S上，選擇M個(gè)對(duì)象作為種子對(duì)象，這M個(gè)種子對(duì)象按照2點(diǎn)之間連線的垂直平分線將數(shù)據(jù)集S分割成M個(gè)互不相交的組，這M個(gè)分組稱為“Voronoi cells”.數(shù)據(jù)集S中的每個(gè)元素按照距離被劃分到距離自己最近的種子對(duì)象所在的分組中.

Voronoi圖分割法在并行計(jì)算中應(yīng)用非常廣泛，文獻(xiàn)[10]以Voronoi圖分割為基礎(chǔ)使用MapReduce框架解決在大數(shù)據(jù)情況下的范圍搜索和KNN查詢，如圖2顯示了一個(gè)Voronoi圖將數(shù)據(jù)集分割成8個(gè)組的實(shí)例.文獻(xiàn)[11]用Voronoi圖分割法設(shè)計(jì)出了一種高效的分布式KNN連接算法.受此啟發(fā)，本文提出的EDDPC算法應(yīng)用Voronoi圖分割法對(duì)數(shù)據(jù)集分割，使分割后的數(shù)據(jù)集分組能夠在集群中的節(jié)點(diǎn)上局部計(jì)算密度值和斥群值.為方便以后敘述做如下定義：Voronoi圖分割種子對(duì)象集合為，Pi表示種子對(duì)象pi所在的分組.

Fig. 2　An example of Voronoi.圖2　Voronoi圖示例

1.3MapReduce與Hadoop

MapReduce是一個(gè)當(dāng)前流行的分布式編程模型.MapReduce提供了2個(gè)主要函數(shù)map和reduce.函數(shù)map和函數(shù)reduce由用戶自己定義，函數(shù)map根據(jù)用戶自定義的功能處理輸入數(shù)據(jù)，并且以〈key,value〉的形式輸出.MapReduce自動(dòng)收集具有相同key值的value，并且以〈key,list(value)〉的形式作為reduce的輸入，reduce根據(jù)用戶定義的功能進(jìn)行處理，最終以〈key,value〉的格式輸出.MapReduce的大致工作流程為

map(k1,v1)→list(k2,v2)，

reduce(k2,list(v2))→list(k3,v3).

Hadoop是一個(gè)實(shí)現(xiàn)了MapReduce編程模型的開源框架.在Hadoop上的數(shù)據(jù)默認(rèn)存儲(chǔ)在分布式文件系統(tǒng)HDFS上.本文將基于MapReduce模型設(shè)計(jì)高效的分布式密度中心聚類算法.

2密度中心聚類在Hadoop上的簡(jiǎn)單實(shí)現(xiàn)

本節(jié)基于MapReduce框架實(shí)現(xiàn)基本的分布式密度中心聚類算法SDDPC.

在1.1節(jié)已經(jīng)介紹過(guò)，密度中心聚類算法的主要步驟是計(jì)算每個(gè)點(diǎn)的密度值ρ和斥群值δ，因此分布式密度中心聚類算法的重點(diǎn)是分布式地計(jì)算ρ值和δ值.在得到每個(gè)數(shù)據(jù)點(diǎn)的ρ值和δ值后，可以將其收集到1臺(tái)機(jī)器上繪出決策圖進(jìn)行聚類.接下來(lái)描述密度中心聚類算法的4個(gè)基本計(jì)算步驟：1)選擇dc長(zhǎng)度的預(yù)處理階段(使用MapReduce);2)計(jì)算ρ值;3)根據(jù)ρ值計(jì)算出δ值;4)繪制決策圖并對(duì)數(shù)據(jù)對(duì)象聚類.

2.1預(yù)處理：尋找合適dc

距離閾值dc在密度中心聚類算法的實(shí)現(xiàn)過(guò)程中是一個(gè)非常重要的參數(shù)，如式(1)所示該參數(shù)用來(lái)計(jì)算每個(gè)點(diǎn)的密度值ρ.文獻(xiàn)[1]給出了一個(gè)dc的經(jīng)驗(yàn)估計(jì)方法，即所有點(diǎn)對(duì)距離從大到小排序后的1%～2%處，因此本文參考該方法來(lái)選取dc值.

在大規(guī)模數(shù)據(jù)集下估計(jì)dc值是一個(gè)開銷非常大的任務(wù)，即使在分布式環(huán)境中，對(duì)數(shù)據(jù)排序也是一個(gè)復(fù)雜的工作.因此，在本文中應(yīng)用了采樣的理念來(lái)對(duì)dc值進(jìn)行估計(jì).由于數(shù)據(jù)量大，因此我們基于MapReduce進(jìn)行采樣，函數(shù)map基于水塘采樣(reservoir sampling)方法[12]對(duì)任意2點(diǎn)的距離進(jìn)行分布式采樣，由于樣本數(shù)據(jù)少，所以可以將采集后的數(shù)據(jù)發(fā)送到單個(gè)reduce，由其進(jìn)行距離計(jì)算并排序，然后選擇出合適的dc值.

2.2計(jì)算ρ值

正如式(1)所示，ρo的計(jì)算需要知道對(duì)象o到其余每個(gè)點(diǎn)j∈S之間的距離doj.對(duì)象之間距離的計(jì)算在MapReduce中可以實(shí)現(xiàn)，有2種實(shí)現(xiàn)方法.在方法1中，函數(shù)map選出1個(gè)對(duì)象，然后將其發(fā)送給其他每個(gè)對(duì)象(假設(shè)總共有N個(gè)對(duì)象)；函數(shù)reduce收集每個(gè)對(duì)象上由map發(fā)過(guò)來(lái)的對(duì)象，計(jì)算該對(duì)象與它們之間的距離，并且根據(jù)式(1)計(jì)算出ρ值.顯然這種簡(jiǎn)單的實(shí)現(xiàn)需要很大的開銷，由于每個(gè)對(duì)象都需復(fù)制到其他對(duì)象所在機(jī)器進(jìn)行距離計(jì)算，因此shuffle開銷是O(N2)，計(jì)算開銷也是O(N2).

由于在方法2中需要將數(shù)據(jù)分塊，因此需要1個(gè)MapReduce作業(yè)來(lái)完成數(shù)據(jù)的分塊，但是仍然比方法1效率高，尤其是當(dāng)n?N時(shí)，shuffle開銷會(huì)急劇減少.在方法2中每個(gè)分塊與其他n-1塊運(yùn)算，分塊中的每個(gè)對(duì)象o就會(huì)得到n個(gè)ρ值，因此需要1個(gè)MapReduce作業(yè)來(lái)合并每個(gè)對(duì)象o的ρ值.

2.3計(jì)算δ值

δ值需要根據(jù)式(2)計(jì)算.算法實(shí)現(xiàn)步驟和計(jì)算ρ值時(shí)相似，需要2個(gè)MapReduce作業(yè)來(lái)完成δ值的計(jì)算，第1個(gè)MapReduce作業(yè)結(jié)束之后，每個(gè)對(duì)象會(huì)得到n個(gè)δ值，第2個(gè)MapReduce作業(yè)從這n個(gè)值中選出最小的一個(gè)值作為δ值.shuffle開銷是O(n×N)，計(jì)算開銷是O(N2).

2.4繪制決策圖并聚類

將得到的ρ值集合和δ值集合匯集到1臺(tái)機(jī)器上(ρ值集合和δ值集合的大小遠(yuǎn)小于點(diǎn)數(shù)據(jù)集S)，并基于得到的ρ值和δ值繪制決策圖.用戶根據(jù)ρ值和δ值的分布情況選出繪制在決策圖中右上角的部分?jǐn)?shù)據(jù)點(diǎn)作為聚類中心，每個(gè)點(diǎn)根據(jù)計(jì)算δ值時(shí)得到的依附關(guān)系，由聚類中心點(diǎn)反推出每個(gè)數(shù)據(jù)點(diǎn)的所屬聚類.

3基于Voronoi分割和數(shù)據(jù)點(diǎn)復(fù)制過(guò)濾的高效分布式密度中心聚類算法

雖然我們?cè)O(shè)計(jì)了簡(jiǎn)單的分布式密度中心聚類算法SDDPC，彌補(bǔ)了單機(jī)運(yùn)行時(shí)的缺陷，但是由于存在大量的shuffle開銷和計(jì)算開銷，因此并不是一種高效的方法.本節(jié)基于Voronoi數(shù)據(jù)分割提出了一種高效分布式密度中心聚類算法EDDPC.該算法包括1個(gè)預(yù)處理階段和2個(gè)完整的MapReduce作業(yè).EDDPC算法將數(shù)據(jù)分組后，各分組中的數(shù)據(jù)對(duì)象獨(dú)立并行執(zhí)行于集群中的各節(jié)點(diǎn)中，在分組內(nèi)部局部計(jì)算ρ值和δ值，避免因計(jì)算所有對(duì)象間的距離而造成的大量開銷.

在預(yù)處理階段需要完成的任務(wù)是選擇Voronoi分割時(shí)所需要的種子.2個(gè)MapReduce作業(yè)分別用來(lái)計(jì)算ρ值和δ值.由于對(duì)數(shù)據(jù)分組之后，在某分組中計(jì)算某些對(duì)象的ρ值和δ值時(shí)需要其他分組的部分對(duì)象，因此各分組獨(dú)立地直接計(jì)算ρ值和δ值將得到錯(cuò)誤的結(jié)果.例如，對(duì)于某數(shù)據(jù)對(duì)象o∈Pi，在計(jì)算ρo時(shí)，|o,q|

3.1種子選擇并且計(jì)算dc

EDDPC算法應(yīng)用了1.2節(jié)提到的基于Voronoi圖的分組方法.該分組方法使用點(diǎn)之間的距離關(guān)系來(lái)進(jìn)行分組，是一個(gè)非常有效的空間分組方法，尤其是在高維空間上.

該分組方法根據(jù)種子對(duì)象進(jìn)行分組，因此在分組之前需要先挑選出合適的種子對(duì)象.在挑選種子時(shí)使用2.1節(jié)中選擇dc值時(shí)使用的水塘采樣算法.在挑選種子對(duì)象的同時(shí)也能夠得到dc值，無(wú)需額外的MapReduce作業(yè).

3.2計(jì)算ρ值及其復(fù)制模型

經(jīng)過(guò)預(yù)處理階段的操作，可以得到Voronoi分組需要的種子對(duì)象集，然后創(chuàng)建1個(gè)MapReduce作業(yè)對(duì)數(shù)據(jù)集分組并計(jì)算ρ值.首先根據(jù)選出的種子對(duì)象進(jìn)行分組，每個(gè)對(duì)象o與種子對(duì)象集中的每個(gè)對(duì)象pi計(jì)算距離，得到對(duì)象o到每個(gè)種子對(duì)象pi的距離dopi，比較對(duì)象o到每個(gè)種子對(duì)象的距離，選出距離o最近的種子對(duì)象pj，將對(duì)象o分配到pj所在的分組Pj中.

分組后，整個(gè)數(shù)據(jù)集分成若干個(gè)互不相交的組，因此，在計(jì)算對(duì)象o密度值ρo時(shí)，可能得到的是一個(gè)錯(cuò)誤的值.如圖3(a)所示,o靠近分組的邊緣線時(shí)計(jì)算得到ρo=8，而實(shí)際值ρo=11.

Fig. 3　Example of replication.圖3　數(shù)據(jù)復(fù)制示例

為了得到正確的ρo值需要將分組區(qū)域B中的3個(gè)點(diǎn)復(fù)制到區(qū)域A中.據(jù)此可以推出每個(gè)分組Si中的點(diǎn)不僅僅要包含由Voronoi分組后點(diǎn)集Pi，也要包含本組中的所有對(duì)象的鄰居集合Ro.即

(3)

其中,Ro={q|?q∈S,|q,o|

在分組之前無(wú)法得到對(duì)象o的dc鄰居集合Ro包含哪些對(duì)象，但是根據(jù)Ro的定義可知，當(dāng)q∈Ro時(shí)，|o,q|

我們提出保證分組正確計(jì)算ρ值的對(duì)象復(fù)制方案.如圖3(b)所示，將所有距離邊緣點(diǎn)小于dc的點(diǎn)全部發(fā)送到相鄰的分組中，并由定理1保證其正確性.

定理1. ?o∈Pj，那么對(duì)象o可能成為Pi中某個(gè)對(duì)象的Ro點(diǎn)而被復(fù)制到的Pi中的條件為

(4)

(5)

當(dāng)|o,l|

證畢.

Fig. 4　An example of equation (5).圖4　式(5)示例

式(5)中的|o,pi|，|o,pj|在對(duì)數(shù)據(jù)對(duì)象o進(jìn)行分組時(shí)已經(jīng)得出，|pi,pj|在種子選擇時(shí)算出，由于種子對(duì)象數(shù)據(jù)量少，因此所有種子間的距離計(jì)算可以單機(jī)完成，并在分布式計(jì)算時(shí)加載使用.

根據(jù)定理1可在分組的同時(shí)對(duì)數(shù)據(jù)進(jìn)行復(fù)制，分組完成后每個(gè)組內(nèi)的數(shù)據(jù)會(huì)包含2種數(shù)據(jù)對(duì)象:一種是由Voronoi數(shù)據(jù)分割方法分組后在每個(gè)Voronoi cell里的對(duì)象集Pi，該集合中的對(duì)象稱之為原始對(duì)象;另一種是為了計(jì)算原始對(duì)象的密度值ρ而將其他組中的數(shù)據(jù)復(fù)制進(jìn)來(lái)的對(duì)象集Si-Pi，該集合中的對(duì)象稱之為復(fù)制對(duì)象.

MapReduce實(shí)現(xiàn)：函數(shù)map首先加載事先采樣得到的Voronoi種子對(duì)象集合，然后計(jì)算每個(gè)對(duì)象o到所有種子對(duì)象pi∈的距離|o,pi|，將該對(duì)象發(fā)送到距離最近的種子所在的分組中，即對(duì)象o所屬的Voronoi分組.同時(shí)，函數(shù)map根據(jù)式(5)把滿足復(fù)制條件的對(duì)象發(fā)送到鄰居分組中.函數(shù)reduce負(fù)責(zé)某個(gè)Voronoi分組，根據(jù)式(1)計(jì)算每個(gè)原始對(duì)象的ρ值(無(wú)須計(jì)算復(fù)制對(duì)象的ρ值).假設(shè)α是復(fù)制因子，代表平均每個(gè)點(diǎn)的副本數(shù)量，如果共產(chǎn)生n個(gè)Voronoi分組，那么計(jì)算密度值ρ需要復(fù)制α×N個(gè)對(duì)象，所以shuffle開銷是O(α×N)，而所需的距離計(jì)算開銷是O(α×N2n) .

3.3復(fù)制過(guò)濾計(jì)算δ值

在得到密度值ρ之后，可以根據(jù)組內(nèi)每個(gè)對(duì)象的ρ值和式(2)計(jì)算每個(gè)對(duì)象的δ值.只在分組內(nèi)部計(jì)算δ值會(huì)有一定的局限性，算出的δ值并不是實(shí)際的δ值，而是一個(gè)不小于實(shí)際δ值的局部δ值，記為δ′.如圖5所示，由于對(duì)象p2不在對(duì)象o所在的分組中，因此對(duì)象o在分組內(nèi)部將p1點(diǎn)作為δ值依附點(diǎn)，最終算出的δ′就比實(shí)際的δ值大.

Fig. 5　δ value of object o.圖5　對(duì)象o的δ值

為了能夠求出精確的斥群值δ需要第2個(gè)MapReduce作業(yè).如圖5所示，為得到對(duì)象o的實(shí)際δ值，需要將組外的p2復(fù)制到對(duì)象o所在的分組中.因此為了計(jì)算每個(gè)組中對(duì)象的斥群值δ需要將一些組外的對(duì)象復(fù)制到本組中.由式(2)可知，對(duì)象o的斥群值δ是o與密度比自己大的對(duì)象的最小距離，若某對(duì)象的密度值大于分組Pi中對(duì)象密度的最小值，它便有可能成為Pi中某對(duì)象o的依附點(diǎn)σo.所以我們有如下引理：

引理1. ?q∈Pj，則對(duì)象q可能成為分組Pi中某個(gè)對(duì)象的依附點(diǎn)σo的條件為

ρq>minρ(Pi),

(6)

其中minρ(Pi)=min{ρo|?o∈Pi}.

在整個(gè)數(shù)據(jù)集S中符合式(6)的對(duì)象可能非常多，當(dāng)Pi中含有整個(gè)數(shù)據(jù)集S中密度最小的對(duì)象時(shí)，需要將整個(gè)數(shù)據(jù)集全部復(fù)制到分組Pi中.但是，在所有滿足式(6)的對(duì)象中也有很多對(duì)象是冗余的，這些冗余的對(duì)象導(dǎo)致一些額外數(shù)據(jù)復(fù)制開銷和距離計(jì)算開銷.因此，為了減少數(shù)據(jù)的復(fù)制量，需要將不必要的對(duì)象過(guò)濾.

為了計(jì)算組Pi中每個(gè)對(duì)象的δ值，經(jīng)過(guò)復(fù)制后的分組Si不僅包含原始分組對(duì)象集Pi同時(shí)也應(yīng)該含有每個(gè)對(duì)象的σo點(diǎn)，即：

(7)

在計(jì)算出ρ值之后，對(duì)本組內(nèi)的原始對(duì)象根據(jù)ρ值進(jìn)行局部δ′值計(jì)算.由于該分組未必包含原始對(duì)象o的依附點(diǎn)對(duì)象σo(最近的密度大于ρo的對(duì)象)，所以得到的δ′值是一個(gè)比實(shí)際值大的數(shù)值.但是這個(gè)值可以作為對(duì)象的斥群值δ的一個(gè)范圍值，δ≤δ′.因此得到：

|o,σo|≤δ′.

(8)

3.3.1普通對(duì)象的依附點(diǎn)過(guò)濾模型

拋開分組內(nèi)部的最大ρ值對(duì)象(局部密度中心點(diǎn))，只考慮剩余普通對(duì)象的δ值的計(jì)算.

在第1個(gè)MapReduce作業(yè)中可以計(jì)算出普通對(duì)象的δ′值，它可以作為實(shí)際δ值的上界.在分組Pi中密度最大的對(duì)象的δ′值為無(wú)窮大，我們記次大的δ′為smaxδ(Pi)，則Pi中除局部密度中心點(diǎn)之外所有對(duì)象的依附點(diǎn)σo與分組種子的距離滿足如下定理:

定理2. ?o∈Pi，ρo≠maxρ(Pi)，記U(Pi)為集合Pi中的所有普通對(duì)象的δ值依附點(diǎn)σo到種子對(duì)象pi的距離最大值，那么U(Pi)滿足不等式：

U(Pi)≤B(Pi)+smaxδ(Pi)，

(9)

其中,B(Pi)=max{|o,pi|,?o∈Pi}.

證明. ?o∈Pi，由于smaxδ(Pi)是除最大ρ值對(duì)象以外最大的δ′值，因此組內(nèi)任何普通點(diǎn)的δ值不可能大于該值，所以|o,σo|≤smaxδ(Pi) ，又因?yàn)锽(Pi)=max{|o,pi|,?o∈Pi}，所以|pi,o|≤B(Pi)，由三角不等式|σo,pi|≤|pi,o|+|o,σo|,所以U(Pi)≤B(Pi)+smaxδ(Pi).

證畢.

式(9)說(shuō)明了，Pi組內(nèi)除最大ρ值對(duì)象的所有普通對(duì)象的依附點(diǎn)σo與該組的種子對(duì)象pi的距離上限為B(Pi)+smaxδ(Pi).由此我們得到如下的推論:

推論1. ?o∈S，o?Pi，則對(duì)象o可能成為Pi中某對(duì)象的σo點(diǎn)而被復(fù)制到Pi中的條件為

(10)

以上過(guò)濾模型沒(méi)有復(fù)制分組中密度最大對(duì)象的依附點(diǎn)，接下來(lái)我們提出分組中最大密度對(duì)象的σo過(guò)濾模型.

3.3.2局部最大密度對(duì)象的依附點(diǎn)過(guò)濾模型

局部最大密度對(duì)象的依附點(diǎn)過(guò)濾模型同樣要找到一個(gè)指導(dǎo)對(duì)象的依附點(diǎn)復(fù)制到組Pi的取值范圍mU(Pi)，該取值范圍不同于普通對(duì)象依附點(diǎn)過(guò)濾模型中的取值范圍U(Pi).我們首先給出如下定理：

定理3. 給定1個(gè)分組Pi，對(duì)象m為該分組的局部最大密度對(duì)象，即ρm=maxρ(Pi)，假設(shè)其依附點(diǎn)為σm，則：

|pi,σm|≤min {2|m,pi|+|pj,u|+|pi,pj|}，

(11)

其中u∈Pj且ρu>ρm，pj≠pi，pj∈P.

證明. 根據(jù)三角不等式可知，|pi,σm|≤|pi,m|+|m,σm|，由σm的定義可得|m,σm|≤min {|m,u|}，所以|pi,σm|≤|m,pi|+min {|m,u|}，又因?yàn)閨m,u|≤|m,pi|+|pi,u|，|pi,u|≤|pi,pj|+|pj,u|.所以|pi,Dm|≤min {2|m,pi|+|pj,u|+|pi,pj|}.

證畢.

由此得出如下推論：

推論2. ?o∈S，o?Pi，則對(duì)象o可能成為Pi中局部最大密度對(duì)象m的依附點(diǎn)σm而被復(fù)制到分組Pi中的條件為

(12)

其中，mU(Pi)=min {2|m,pi|+|pj,u|+|pi,pj|}.

在2個(gè)復(fù)制模型中涉及到每個(gè)分組內(nèi)的次大δ′值smaxδ(Pi) (最大δ′值應(yīng)該是無(wú)窮大)、組內(nèi)的最大ρ值maxρ(Pi)、組內(nèi)最小ρ值minρ(Pi)、組內(nèi)局部最大ρ值對(duì)象m到種子對(duì)象的距離|m,pi|和距離該組的種子對(duì)象最遠(yuǎn)的點(diǎn)的距離B(Pi)，這些數(shù)據(jù)是在完成第1個(gè)MapReduce作業(yè)后需要收集的一些關(guān)于分組的信息.

2個(gè)過(guò)濾模型中的式(10)和式(12)都以|o,pi|≤θ的形式出現(xiàn)，其中θ=U(Pi)或θ=mU(Pi).

對(duì)每個(gè)對(duì)象決定是否要發(fā)送到分組Pi中，都要與pi做1次距離計(jì)算.因此，當(dāng)P中的對(duì)象非常多時(shí)，開銷也會(huì)變大，為此本文給出了一種剪枝的策略.

定理4. ?o∈Pj，|o,pi|<θ，則|o,pj|>|pj,pi|-θ.

證明. 如圖6所示，由直角三角形斜邊大于直角邊可知|pi,k|<θ，|pj,k|>|pj,pi|-θ，又因?yàn)閨o,pj|>|pj,k|，|pj,k|>|pj,pi|-θ，所以|o,pj|>|pj,pi|-θ.

證畢.

因此當(dāng)|o,pj|>|pj,pi|-θ時(shí)，不必計(jì)算o到pi的距離，而直接過(guò)濾.

Fig. 6　An example of theorem 4.圖6　定理4示例

MapReduce實(shí)現(xiàn)：在第2個(gè)MapReduce作業(yè)中，函數(shù)map根據(jù)以上2個(gè)模型，將滿足推論1和推論2的對(duì)象進(jìn)行相應(yīng)的復(fù)制和發(fā)送.這里需要注意一點(diǎn)，如果某一對(duì)象同時(shí)滿足2個(gè)條件，為了避免重復(fù)計(jì)算，只將數(shù)據(jù)對(duì)象復(fù)制發(fā)送1次即可.在reduce階段，只需要比較組內(nèi)原始對(duì)象的密度與復(fù)制對(duì)象的密度，當(dāng)密度比自己密度大時(shí)計(jì)算距離，選擇最小距離作為δ值，同時(shí)記錄δ值的依附點(diǎn).假設(shè)β是復(fù)制因子，代表平均每個(gè)點(diǎn)的副本數(shù)量，如果共產(chǎn)生n個(gè)Voronoi分組，那么計(jì)算斥群值δ需要復(fù)制β×N個(gè)對(duì)象，所以shuffle開銷是O(β×N)，而所需的距離計(jì)算開銷是O(β×N2n).

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

我們?cè)诒镜丶汉虯mazon EC2云平臺(tái)上應(yīng)用3個(gè)真實(shí)數(shù)據(jù)集對(duì)分布式密度中心算法SDDPC和優(yōu)化的EDDPC算法進(jìn)行了對(duì)比實(shí)驗(yàn)分析.

4.1實(shí)驗(yàn)環(huán)境

Hadoop本地集群包括4臺(tái)slave機(jī)器、1臺(tái)master機(jī)器，每臺(tái)機(jī)器配有Intel I5-4690 3.3 GHz 4Core處理器、1000 Mbps以太網(wǎng)卡、1 TB 7200rm普通硬盤、4 GB運(yùn)行內(nèi)存.Amazon EC2集群包括17個(gè)m1.medium節(jié)點(diǎn).操作系統(tǒng)為64位Ubuntu 14.04 LTS，JDK版本為Java1.7，Hadoop版本為Hadoop1.2.1.

數(shù)據(jù)集采用BigCross[13]，facial[14]，kdd[15]，其中BigCross數(shù)據(jù)集包含11 620 300個(gè)點(diǎn)，實(shí)驗(yàn)過(guò)程中只截取了50萬(wàn)個(gè)點(diǎn)，每條記錄的維度是57；facial數(shù)據(jù)集包含27 936個(gè)點(diǎn)，每個(gè)點(diǎn)300維；kdd數(shù)據(jù)集包含145 751個(gè)點(diǎn)，每個(gè)點(diǎn)74維.

本文所有實(shí)驗(yàn)中SDDPC算法以200個(gè)點(diǎn)作為1個(gè)分塊，EDDPC算法為避免因選擇到的種子不同造成分組狀態(tài)不同，從而導(dǎo)致實(shí)驗(yàn)結(jié)果不同而對(duì)實(shí)驗(yàn)效果造成影響，所以2種算法均采用3次實(shí)驗(yàn)取平均值作為最終結(jié)果.

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

4.2.1整體性能評(píng)估

圖7展示了在BigCross(隨機(jī)截取20萬(wàn)個(gè)點(diǎn))，facial，kdd數(shù)據(jù)集上SDDPC，EDDPC和原始的密度中心聚類(density peak clustering, DP_Clustering)算法運(yùn)行時(shí)間的比較.EDDPC種子選取比例為3‰，運(yùn)行時(shí)間不包括繪制決策圖時(shí)間.總體上從圖7可以看出,EDDPC算法的運(yùn)行時(shí)間明顯要少于SDDPC算法，尤其在數(shù)據(jù)量比較大的BigCross和kdd數(shù)據(jù)集上.在kdd數(shù)據(jù)集上表現(xiàn)最為明顯，產(chǎn)生kdd運(yùn)行時(shí)間差距的原因是kdd數(shù)據(jù)集中只有1個(gè)聚類簇，因此在計(jì)算δ值時(shí)shuffle開銷和計(jì)算開銷大大減少.原始DP_Clustering算法在單機(jī)環(huán)境下運(yùn)行，由于沒(méi)有Hadoop啟動(dòng)時(shí)間和多次讀文件的時(shí)間，因此原始DP_Clustering算法在數(shù)據(jù)量比較小的情況下會(huì)比SDDPC算法的運(yùn)行時(shí)間快；而在數(shù)據(jù)量比較大的情況下，原始DP_Clustering算法由于是在單機(jī)環(huán)境下執(zhí)行，會(huì)造成內(nèi)存溢出，從而無(wú)法執(zhí)行DP_Clustering算法.

Fig. 7　Running time comparison on three data sets.圖7　3種數(shù)據(jù)集下運(yùn)行時(shí)間比較

4.2.2數(shù)據(jù)集大小的影響

為了測(cè)試數(shù)據(jù)集大小變化對(duì)算法性能的影響，我們從BigCross數(shù)據(jù)集中分別隨機(jī)截取了10萬(wàn)、20萬(wàn)、30萬(wàn)、40萬(wàn)、50萬(wàn)個(gè)數(shù)據(jù)對(duì)象，分別構(gòu)成了5個(gè)大小不同的數(shù)據(jù)集.如圖8顯示了EDDPC和SDDPC算法在這5個(gè)數(shù)據(jù)集上運(yùn)行時(shí)間的對(duì)比，可以看出改進(jìn)的EDDPC算法時(shí)間增長(zhǎng)比較緩慢，而SDDPC算法以接近平方的速度增長(zhǎng).

Fig. 8　Running time comparison when varying data size.圖8　不同數(shù)據(jù)集大小情況下的運(yùn)行時(shí)間比較

為了分析造成運(yùn)行時(shí)間差距的原因，本文還統(tǒng)計(jì)了這2種算法在Hadoop框架上執(zhí)行時(shí)的通信量(shuffling cost)、每個(gè)點(diǎn)的副本個(gè)數(shù)和點(diǎn)之間距離計(jì)算的次數(shù).

圖9顯示了在計(jì)算ρ值和δ值時(shí)EDDPC和SDDPC算法執(zhí)行過(guò)程中每個(gè)點(diǎn)的平均副本數(shù)量.其中EDDPC算法的副本數(shù)量由程序統(tǒng)計(jì)而得，并多次統(tǒng)計(jì)取平均值；SDDPC算法的副本數(shù)量根據(jù)Nn計(jì)算得到，其中N指數(shù)據(jù)集中點(diǎn)的個(gè)數(shù)，n指每個(gè)分塊中包含的點(diǎn)的個(gè)數(shù).

Fig. 9　Comparison of number of points replicas.圖9　點(diǎn)副本數(shù)比較

圖10顯示了在輸入數(shù)據(jù)為10萬(wàn)～50萬(wàn)時(shí)EDDPC和SDDPC算法在Hadoop上執(zhí)行過(guò)程中的通信量.

圖11顯示了數(shù)據(jù)從100×103～500×103時(shí)，EDDPC和SDDPC算法在Hadoop集群上執(zhí)行過(guò)程中計(jì)算2點(diǎn)之間距離的計(jì)算次數(shù)，EDDPC算法由程序統(tǒng)計(jì)，SDDPC算法根據(jù)公式2N×(N-1)計(jì)算.

通過(guò)分析圖9可以看到，EDDPC算法在計(jì)算ρ值和δ值的過(guò)程中平均每個(gè)點(diǎn)的副本數(shù)量比SDDPC算法要少，因此Hadoop集群中各節(jié)點(diǎn)之間的通信量機(jī)會(huì)變少，如圖10所示.同時(shí)由于副本數(shù)量的減少和組內(nèi)各點(diǎn)局部計(jì)算距離，從而減少距離計(jì)算的次數(shù)，如圖11所示.

Fig. 10　Shuffling cost comparison.圖10　Shuffle通信量比較

Fig. 11　Comparison of distance measurements.圖11　距離計(jì)算次數(shù)比較

4.2.3分組種子數(shù)量的影響

為了探究EDDPC算法中種子數(shù)量對(duì)算法執(zhí)行效率的影響，本文設(shè)計(jì)了在相同數(shù)據(jù)量的點(diǎn)集中相同數(shù)據(jù)集(facial)下不同種子數(shù)量對(duì)實(shí)驗(yàn)結(jié)果造成的影響.

Fig. 12　Running time of EDDPC when varying numberof Voronoi partitions.圖12　EDDPC中Voronoi分組數(shù)量不同時(shí)的運(yùn)行時(shí)間

圖12顯示了在種子數(shù)量在5～95范圍內(nèi)變化時(shí)EDDPC算法的運(yùn)行時(shí)間，由于選取到的種子不同，造成運(yùn)行時(shí)間不同，因此本實(shí)驗(yàn)取3次實(shí)驗(yàn)的平均值作為本實(shí)驗(yàn)的結(jié)果值.

由圖12可以看出，在一定范圍內(nèi)，隨種子對(duì)象的增多運(yùn)行時(shí)間先變少然后增大.種子對(duì)象在15～25時(shí)運(yùn)行時(shí)間最少.由于種子對(duì)象的選取可能造成運(yùn)行時(shí)間波動(dòng)，但是大致趨勢(shì)仍然是先變小后變大.

我們對(duì)圖12所示現(xiàn)象做如下的分析：當(dāng)種子對(duì)象增多時(shí)，數(shù)據(jù)分組變多，分組內(nèi)部的數(shù)據(jù)會(huì)減少，因此在計(jì)算ρ值時(shí)分組內(nèi)部距離計(jì)算的開銷就會(huì)減少.而在計(jì)算δ值時(shí)，隨著分組的增多，U(Pi)和mU(Pi)的值會(huì)變小，每個(gè)分組內(nèi)部被復(fù)制添加進(jìn)來(lái)的數(shù)據(jù)對(duì)象會(huì)減少，因此總體運(yùn)行時(shí)間會(huì)減少.但是隨著種子對(duì)象的持續(xù)增加，分組數(shù)量增多，map和reduce的線程數(shù)量就會(huì)增加，加大了系統(tǒng)的開銷.同時(shí)分組的增多也會(huì)使每個(gè)對(duì)象被復(fù)制到其他組的概率變大，因此通信開銷也會(huì)隨之增長(zhǎng),導(dǎo)致運(yùn)行時(shí)間變長(zhǎng).

4.2.4集群數(shù)量的影響

我們?cè)贏mazon EC2集群上，分別利用2,4,8,16個(gè)計(jì)算節(jié)點(diǎn)運(yùn)行EDDPC算法來(lái)評(píng)估算法擴(kuò)展性能.采用BigCross數(shù)據(jù)集中截取的50萬(wàn)條數(shù)據(jù)作為輸入數(shù)據(jù)，實(shí)驗(yàn)結(jié)果如圖13所示.我們以2節(jié)點(diǎn)運(yùn)行時(shí)間為基準(zhǔn)，畫出了一條理論最優(yōu)的擴(kuò)展性能曲線.從圖13可以看出,EDDPC算法具有不錯(cuò)的擴(kuò)展性能，雖然性能加速比略低于理論最優(yōu)的加速比，但是從4節(jié)點(diǎn)到16節(jié)點(diǎn)的運(yùn)行時(shí)間幾乎是隨著節(jié)點(diǎn)數(shù)量的增加呈線性遞減.

Fig. 13　Running time of EDDPC when varying number of nodes.圖13　節(jié)點(diǎn)不同時(shí)的EDDPC運(yùn)行時(shí)間

5結(jié)論

本文發(fā)現(xiàn)了密度中心聚類算法的運(yùn)行效率問(wèn)題，并基于MapReduce簡(jiǎn)單實(shí)現(xiàn)了分布式密度中心聚類算法——SDDPC.為了進(jìn)一步提高SDDPC算法的性能，本文基于Voronoi圖分割的方法提出一種高效的分布式密度中心聚類算法——EDDPC.為了正確計(jì)算ρ值和δ值，本文分別給出了一個(gè)數(shù)據(jù)對(duì)象復(fù)制模型和2個(gè)數(shù)據(jù)對(duì)象過(guò)濾模型，將部分其他分組內(nèi)的必要對(duì)象復(fù)制到本分組內(nèi)，這保證了EDDPC算法可以在各獨(dú)立分組內(nèi)分布式執(zhí)行ρ值和δ值的計(jì)算.提出的高效數(shù)據(jù)復(fù)制過(guò)濾模型不僅能保證算法執(zhí)行過(guò)程中能夠精確計(jì)算每個(gè)對(duì)象的ρ值和δ值，從而得到與原始DP_Clustering算法相等的結(jié)果，同時(shí)大大減少了數(shù)據(jù)對(duì)象的副本數(shù)量和shuffling的開銷，進(jìn)而減少了計(jì)算量，使EDDPC算法能夠在分布式情況下高效率執(zhí)行.

參考文獻(xiàn)

[1]Xu Rui, Wunsch D Ⅱ. Survey of clustering algorithms[J]. IEEE Trans on Neural Networks, 2005, 16(3): 645-678

[2]Kaufman L, Peter R. Clustering by Means of Medoids[G] //Statistical Data Analysis Based on the L1 Norm and Related Methods. North-Holland: North-Holland Press, 1987: 405-416

[3] MacQueen J. Some methods for classification and analysis of multivariate observations[C] //Proc of the 5th Berkeley Symp on Mathematical Statistics and Probability. Berkeley, CA: University of California Press, 1967: 281-297

[4]Zhang W, Wang X, Zhao D, et al. Graph Degree Linkage: Agglomerative Clustering on a Directed Graph[M] . Berlin: Springer, 2012: 428-441

[5] Ester M, Kriegel H P, Sander J, et al. A density-based algorithm for discovering clusters in large spatial databases with noise[C] //Proc of ACM KDD’96. New York: ACM, 1996: 226-231

[6]Wang W, Jiong Y, Muntz R. STING: A statistical information grid approach to spatial data mining[C] //Proc of VLDB’97. San Francisco, CA: Morgan Kaufmann, 1997: 186-195

[7]Ying Wenhao, Xu Min, Wang Shitong, et al. Fast adaptive clustering by synchronization on large scale datasets[J].

Journal of Computer Research and Development, 2014, 51(4): 707-720 (in Chinese)(應(yīng)文豪, 許敏, 王士同, 等. 在大規(guī)模數(shù)據(jù)集上進(jìn)行快速自適應(yīng)同步聚類[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 51(4): 707-720)

[8]Alex R, Alessandro L. Clustering by fast search and find of density peaks [J]. Science, 2014, 344(1492):1492-1496

[9]Jeffrey D, Sanjay G. MapReduce: Simplified data processing on large clusters[J]. Communications of the ACM, 2004, 51(1): 107-113

[10]Akdogan A, Demiryurek U, Banaei-Kashani F, et al. Voronoi-based geospatial query processing with MapReduce[C] //Proc of CloudCom ’10. Piscataway, NJ: IEEE, 2010: 9-16

[11]Lu Wei, Shen Yanyan, Chen Su, etc. Efficient processing ofknearest neighbor joins using MapReduce [J]. VLDB Endowment, 2012, 5(10): 1016-1027

[12]Jeffery S V. Random sampling with a reservoir [J]. ACM Trans on Mathematical Software, 1985, 11(1): 37-57

[13]Shindler M, Wong A, Meyerson A W. Fast and accuratek-means for large datasets[C] //Proc of NIPS’11. New York: Curran Associates Press, 2011: 2375-2383

[14]Freitas F A, Peres S M, Lima C A M, et al. Grammatical facial expressions recognition with machine learning[C] //Proc of FLAIRS’14. Menlo Park, CA: AAAI Press, 2014: 180-185

[15]Caruana R, Joachims T. Kddcup 04 biology dataset[EB/OL]. 2008 [2015-05-10]. http://kodiak.cs.cornell.edu/kddcup/datasets.html

Gong Shufeng, born in 1991. Master candidate. His main research interests include big data and cloud computing.

Zhang Yanfeng, born in 1982. Associate professor. Member of China Computer Federation. His main research interests include big data and cloud computing.

EDDPC: An Efficient Distributed Density Peaks Clustering Algorithm

Gong Shufeng and Zhang Yanfeng

(CollegeofComputerScienceandEngineering,NortheasternUniversity,Shenyang110819)

AbstractClustering is a commonly used method for data relationship analytics in data mining. The clustering algorithm divides a set of objects into several groups (clusters), and the data objects in the same group are more similar to each other than to those in other groups. Density peaks clustering is a recently proposed clustering algorithm published in Science magazine, which performs clustering in terms of each data object’sρvalue andδvalue. It exhibits its superiority over the other traditional clustering algorithms in interactivity, non-iterative process, and non-assumption on data distribution. However, computing each data object’sρa(bǔ)ndδvalue requires to measure distance between any pair of objects with high computational cost ofO(N2). This limits the practicability of this algorithm when clustering high-volume and high-dimensional data set. In order to improve efficiency and scalability, we propose an efficient distributed density peaks clustering algorithm—EDDPC, which leverages Voronoi diagram and careful data replication?filtering to reduce huge amount of useless distance measurement cost and data shuffle cost. Our results show that our EDDPC algorithm can improve the performance significantly (up to 40x) compared with naive MapReduce implementation.

Key wordsdensity peaks; data clustering; Voronoi partition; MapReduce; big data

收稿日期：2015-06-30；修回日期：2015-10-29

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(61300023,61528203,61272179)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(N141605001,N120816001)

通信作者：張巖峰(zhangyf@cc.neu.edu.cn)

中圖法分類號(hào)TP301.6

This work was supported by the National Natural Science Foundation of China (61300023,61528203,61272179) and the Fundamental Research Funds for the Central Universities (N141605001,N120816001)