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

鞏樹鳳　　　張巖峰

(東北大學計算機科學與工程學院　沈陽　110819)(shidashufeng@163.com)

?

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

鞏樹鳳張巖峰

(東北大學計算機科學與工程學院沈陽110819)(shidashufeng@163.com)

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

關鍵詞密度中心；數據聚類；Voronoi分割；MapReduce；大數據

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

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

相對于諸多傳統聚類算法，密度中心聚類算法具有3個優點：

1) 交互性.不同于k-means等聚類算法，要求用戶在算法執行前指定聚類的個數k.密度中心聚類算法在計算出每個點的密度值ρ和斥群值δ之后，由用戶根據ρ值和δ值來確定聚類的個數.

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

3) 無數據分布依賴性.算法的聚類形狀沒有偏倚，可以適用于多種環境下數據的聚類[1].

盡管密度中心聚類算法有以上諸多優點，但是計算密度值ρ和斥群值δ需要測量數據集中任意2點之間的歐氏距離，復雜度為O(N2).當處理海量高維數據時，算法的實現涉及到大量的高維歐氏距離計算，造成大量的計算開銷，使其無法在單機環境下運行，嚴重影響了算法的實用性.

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

本文的主要貢獻如下：

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

2) 針對ρ值計算，設計了一種數據復制模型；針對δ值計算，設計了2種數據過濾模型，從而減少了數據對象的復制量和距離計算量，提高了算法的執行效率.

3) 在多個真實數據集上對分布式密度中心聚類算法進行了實驗和性能評估，實驗結果驗證了該算法的高效性.

1相關工作

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

1.1密度中心聚類算法介紹

密度中心聚類算法[8]基于數據點的密度值ρ和斥群值δ來對數據集進行聚類.

數據點i的密度值ρi為

(1)

其中，χ(x)是一個函數，當x< 0時，χ(x)=1，否則χ(x)=0；dij是點j到點i的距離；dc是一個距離臨界值.也就是說，ρi為與點i的距離小于dc的點的個數.

點i的斥群值δi為

(2)

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

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

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

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

1.2基于Voronoi圖的分割法

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

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

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

1.3MapReduce與Hadoop

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

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

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

Hadoop是一個實現了MapReduce編程模型的開源框架.在Hadoop上的數據默認存儲在分布式文件系統HDFS上.本文將基于MapReduce模型設計高效的分布式密度中心聚類算法.

2密度中心聚類在Hadoop上的簡單實現

本節基于MapReduce框架實現基本的分布式密度中心聚類算法SDDPC.

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

2.1預處理：尋找合適dc

距離閾值dc在密度中心聚類算法的實現過程中是一個非常重要的參數，如式(1)所示該參數用來計算每個點的密度值ρ.文獻[1]給出了一個dc的經驗估計方法，即所有點對距離從大到小排序后的1%～2%處，因此本文參考該方法來選取dc值.

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

2.2計算ρ值

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

由于在方法2中需要將數據分塊，因此需要1個MapReduce作業來完成數據的分塊，但是仍然比方法1效率高，尤其是當n?N時，shuffle開銷會急劇減少.在方法2中每個分塊與其他n-1塊運算，分塊中的每個對象o就會得到n個ρ值，因此需要1個MapReduce作業來合并每個對象o的ρ值.

2.3計算δ值

δ值需要根據式(2)計算.算法實現步驟和計算ρ值時相似，需要2個MapReduce作業來完成δ值的計算，第1個MapReduce作業結束之后，每個對象會得到n個δ值，第2個MapReduce作業從這n個值中選出最小的一個值作為δ值.shuffle開銷是O(n×N)，計算開銷是O(N2).

2.4繪制決策圖并聚類

將得到的ρ值集合和δ值集合匯集到1臺機器上(ρ值集合和δ值集合的大小遠小于點數據集S)，并基于得到的ρ值和δ值繪制決策圖.用戶根據ρ值和δ值的分布情況選出繪制在決策圖中右上角的部分數據點作為聚類中心，每個點根據計算δ值時得到的依附關系，由聚類中心點反推出每個數據點的所屬聚類.

3基于Voronoi分割和數據點復制過濾的高效分布式密度中心聚類算法

雖然我們設計了簡單的分布式密度中心聚類算法SDDPC，彌補了單機運行時的缺陷，但是由于存在大量的shuffle開銷和計算開銷，因此并不是一種高效的方法.本節基于Voronoi數據分割提出了一種高效分布式密度中心聚類算法EDDPC.該算法包括1個預處理階段和2個完整的MapReduce作業.EDDPC算法將數據分組后，各分組中的數據對象獨立并行執行于集群中的各節點中，在分組內部局部計算ρ值和δ值，避免因計算所有對象間的距離而造成的大量開銷.

在預處理階段需要完成的任務是選擇Voronoi分割時所需要的種子.2個MapReduce作業分別用來計算ρ值和δ值.由于對數據分組之后，在某分組中計算某些對象的ρ值和δ值時需要其他分組的部分對象，因此各分組獨立地直接計算ρ值和δ值將得到錯誤的結果.例如，對于某數據對象o∈Pi，在計算ρo時，|o,q|

3.1種子選擇并且計算dc

EDDPC算法應用了1.2節提到的基于Voronoi圖的分組方法.該分組方法使用點之間的距離關系來進行分組，是一個非常有效的空間分組方法，尤其是在高維空間上.

該分組方法根據種子對象進行分組，因此在分組之前需要先挑選出合適的種子對象.在挑選種子時使用2.1節中選擇dc值時使用的水塘采樣算法.在挑選種子對象的同時也能夠得到dc值，無需額外的MapReduce作業.

3.2計算ρ值及其復制模型

經過預處理階段的操作，可以得到Voronoi分組需要的種子對象集，然后創建1個MapReduce作業對數據集分組并計算ρ值.首先根據選出的種子對象進行分組，每個對象o與種子對象集中的每個對象pi計算距離，得到對象o到每個種子對象pi的距離dopi，比較對象o到每個種子對象的距離，選出距離o最近的種子對象pj，將對象o分配到pj所在的分組Pj中.

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

Fig. 3　Example of replication.圖3　數據復制示例

為了得到正確的ρo值需要將分組區域B中的3個點復制到區域A中.據此可以推出每個分組Si中的點不僅僅要包含由Voronoi分組后點集Pi，也要包含本組中的所有對象的鄰居集合Ro.即

(3)

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

在分組之前無法得到對象o的dc鄰居集合Ro包含哪些對象，但是根據Ro的定義可知，當q∈Ro時，|o,q|

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

定理1. ?o∈Pj，那么對象o可能成為Pi中某個對象的Ro點而被復制到的Pi中的條件為

(4)

(5)

當|o,l|

證畢.

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

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

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

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

3.3復制過濾計算δ值

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

Fig. 5　δ value of object o.圖5　對象o的δ值

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

引理1. ?q∈Pj，則對象q可能成為分組Pi中某個對象的依附點σo的條件為

ρq>minρ(Pi),

(6)

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

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

為了計算組Pi中每個對象的δ值，經過復制后的分組Si不僅包含原始分組對象集Pi同時也應該含有每個對象的σo點，即：

(7)

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

|o,σo|≤δ′.

(8)

3.3.1普通對象的依附點過濾模型

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

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

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

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

(9)

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

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

證畢.

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

推論1. ?o∈S，o?Pi，則對象o可能成為Pi中某對象的σo點而被復制到Pi中的條件為

(10)

以上過濾模型沒有復制分組中密度最大對象的依附點，接下來我們提出分組中最大密度對象的σo過濾模型.

3.3.2局部最大密度對象的依附點過濾模型

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

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

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

(11)

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

證明. 根據三角不等式可知，|pi,σm|≤|pi,m|+|m,σm|，由σm的定義可得|m,σm|≤min {|m,u|}，所以|pi,σm|≤|m,pi|+min {|m,u|}，又因為|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，則對象o可能成為Pi中局部最大密度對象m的依附點σm而被復制到分組Pi中的條件為

(12)

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

在2個復制模型中涉及到每個分組內的次大δ′值smaxδ(Pi) (最大δ′值應該是無窮大)、組內的最大ρ值maxρ(Pi)、組內最小ρ值minρ(Pi)、組內局部最大ρ值對象m到種子對象的距離|m,pi|和距離該組的種子對象最遠的點的距離B(Pi)，這些數據是在完成第1個MapReduce作業后需要收集的一些關于分組的信息.

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

對每個對象決定是否要發送到分組Pi中，都要與pi做1次距離計算.因此，當P中的對象非常多時，開銷也會變大，為此本文給出了一種剪枝的策略.

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

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

證畢.

因此當|o,pj|>|pj,pi|-θ時，不必計算o到pi的距離，而直接過濾.

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

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

4實驗

我們在本地集群和Amazon EC2云平臺上應用3個真實數據集對分布式密度中心算法SDDPC和優化的EDDPC算法進行了對比實驗分析.

4.1實驗環境

Hadoop本地集群包括4臺slave機器、1臺master機器，每臺機器配有Intel I5-4690 3.3 GHz 4Core處理器、1000 Mbps以太網卡、1 TB 7200rm普通硬盤、4 GB運行內存.Amazon EC2集群包括17個m1.medium節點.操作系統為64位Ubuntu 14.04 LTS，JDK版本為Java1.7，Hadoop版本為Hadoop1.2.1.

數據集采用BigCross[13]，facial[14]，kdd[15]，其中BigCross數據集包含11 620 300個點，實驗過程中只截取了50萬個點，每條記錄的維度是57；facial數據集包含27 936個點，每個點300維；kdd數據集包含145 751個點，每個點74維.

本文所有實驗中SDDPC算法以200個點作為1個分塊，EDDPC算法為避免因選擇到的種子不同造成分組狀態不同，從而導致實驗結果不同而對實驗效果造成影響，所以2種算法均采用3次實驗取平均值作為最終結果.

4.2實驗結果與分析

4.2.1整體性能評估

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

Fig. 7　Running time comparison on three data sets.圖7　3種數據集下運行時間比較

4.2.2數據集大小的影響

為了測試數據集大小變化對算法性能的影響，我們從BigCross數據集中分別隨機截取了10萬、20萬、30萬、40萬、50萬個數據對象，分別構成了5個大小不同的數據集.如圖8顯示了EDDPC和SDDPC算法在這5個數據集上運行時間的對比，可以看出改進的EDDPC算法時間增長比較緩慢，而SDDPC算法以接近平方的速度增長.

Fig. 8　Running time comparison when varying data size.圖8　不同數據集大小情況下的運行時間比較

為了分析造成運行時間差距的原因，本文還統計了這2種算法在Hadoop框架上執行時的通信量(shuffling cost)、每個點的副本個數和點之間距離計算的次數.

圖9顯示了在計算ρ值和δ值時EDDPC和SDDPC算法執行過程中每個點的平均副本數量.其中EDDPC算法的副本數量由程序統計而得，并多次統計取平均值；SDDPC算法的副本數量根據Nn計算得到，其中N指數據集中點的個數，n指每個分塊中包含的點的個數.

Fig. 9　Comparison of number of points replicas.圖9　點副本數比較

圖10顯示了在輸入數據為10萬～50萬時EDDPC和SDDPC算法在Hadoop上執行過程中的通信量.

圖11顯示了數據從100×103～500×103時，EDDPC和SDDPC算法在Hadoop集群上執行過程中計算2點之間距離的計算次數，EDDPC算法由程序統計，SDDPC算法根據公式2N×(N-1)計算.

通過分析圖9可以看到，EDDPC算法在計算ρ值和δ值的過程中平均每個點的副本數量比SDDPC算法要少，因此Hadoop集群中各節點之間的通信量機會變少，如圖10所示.同時由于副本數量的減少和組內各點局部計算距離，從而減少距離計算的次數，如圖11所示.

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

Fig. 11　Comparison of distance measurements.圖11　距離計算次數比較

4.2.3分組種子數量的影響

為了探究EDDPC算法中種子數量對算法執行效率的影響，本文設計了在相同數據量的點集中相同數據集(facial)下不同種子數量對實驗結果造成的影響.

Fig. 12　Running time of EDDPC when varying numberof Voronoi partitions.圖12　EDDPC中Voronoi分組數量不同時的運行時間

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

由圖12可以看出，在一定范圍內，隨種子對象的增多運行時間先變少然后增大.種子對象在15～25時運行時間最少.由于種子對象的選取可能造成運行時間波動，但是大致趨勢仍然是先變小后變大.

我們對圖12所示現象做如下的分析：當種子對象增多時，數據分組變多，分組內部的數據會減少，因此在計算ρ值時分組內部距離計算的開銷就會減少.而在計算δ值時，隨著分組的增多，U(Pi)和mU(Pi)的值會變小，每個分組內部被復制添加進來的數據對象會減少，因此總體運行時間會減少.但是隨著種子對象的持續增加，分組數量增多，map和reduce的線程數量就會增加，加大了系統的開銷.同時分組的增多也會使每個對象被復制到其他組的概率變大，因此通信開銷也會隨之增長,導致運行時間變長.

4.2.4集群數量的影響

我們在Amazon EC2集群上，分別利用2,4,8,16個計算節點運行EDDPC算法來評估算法擴展性能.采用BigCross數據集中截取的50萬條數據作為輸入數據，實驗結果如圖13所示.我們以2節點運行時間為基準，畫出了一條理論最優的擴展性能曲線.從圖13可以看出,EDDPC算法具有不錯的擴展性能，雖然性能加速比略低于理論最優的加速比，但是從4節點到16節點的運行時間幾乎是隨著節點數量的增加呈線性遞減.

Fig. 13　Running time of EDDPC when varying number of nodes.圖13　節點不同時的EDDPC運行時間

5結論

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

參考文獻

[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)(應文豪, 許敏, 王士同, 等. 在大規模數據集上進行快速自適應同步聚類[J]. 計算機研究與發展, 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ρandδ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

基金項目：國家自然科學基金項目(61300023,61528203,61272179)；中央高校基本科研業務費專項資金項目(N141605001,N120816001)

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

中圖法分類號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)