一種基于密度峰值的高效分布式聚類算法

何仝 徐蔚鴻 馬紅華 曾水玲

摘 ? 要：基于密度峰值的聚類算法（DPC）是最近提出的一種高效密度聚類算法。該算法可以對非球形分布的數據聚類，有待調節參數少、聚類速度快等優點，但在計算每個數據對象的密度值和高密度最鄰近距離時，需要進行距離度量，其時間復雜度為 。在大數據時代，尤其是處理海量高維數據時，該算法的效率會受到很大的影響。為了提高該算法的效率和擴展性，利用 Spark 在內存計算以及迭代計算上的優勢，提出一種高效的基于E2LSH分區的聚類算法ELSDPC（an efficient distributed density peak clustering algorithm based on E2LSH partition with spark）。算法利用DPC算法的局部特性，引入局部敏感哈希算法LSH實現將鄰近點集劃分到一個區域。通過實驗分析表明：該算法可在滿足較高準確率的同時有效提高聚類算法的擴展性和時間效率。

關鍵詞：聚類;密度峰值;大數據;局部敏感哈希;Spark

中圖分類號： TP311.1 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼：A

An Efficient Distributed Clustering Algorithm Based on Peak Density

HE Tong1，2？覮，XU Wei-hong1，2，MA Hong-hua2，ZENG Shui-ling3

（1. School of Computer and Communication Engineering，Changsha University of Science

and Technology，Changsha，Hunan 440114，China;

2. Hunan Provincial Key Laboratory of Intelligent Processing of Big Data on Transportation，

Changsha University of Science and Technology，Changsha，Hunan 440114，China;

3. Zixing City Science Bureau，Chenzhou，Hunan 23400，China;）

Abstract：The density peak clustering algorithm （DPC） is a recently proposed efficient density clustering algorithm. The algorithm can cluster the data of non-spherical distribution，which needs less adjustment parameters and fast clustering speed. But when calculating the density and exclusion value of each data object，the distance measure needs to be measured，and its time complexity is . When dealing with big data，especially high-dimension data ，the efficiency of the algorithm will be greatly affected. In order to improve the efficiency and scalability of the algorithm，take the advantages of Spark in memory calculation and iterative computing，we propose an efficient clustering algorithm based on E2LSH partition-ELSDPC. Using the local characteristics of the DPC algorithm，the LSH implementation is introduced to divide the adjacent point set into a region. The experimental analysis shows that the algorithm can effectively improve the scalability and time efficiency of the clustering algorithm while satisfying the high accuracy.

Key words：clustering;density peak;big data;LSH;Spark

聚類是被稱為模式識別的無監督學習方法[1]。它將數據樣本分成若干個類或簇，使得同一個類或簇中樣本相似度較高，不同類或簇中的樣本相似度較低，從而發現數據元素間的潛在聯系，挖掘感興趣的知識。2014年Alex和Anlessandro在Science上發表了自動確定類簇數和類簇中心的聚類算法DPC（Clustering by Fast Search and Find of Density Peaks）[2]，利用數據集的密度峰值點，該算法能快速發現任意形狀數據集的類簇中心，并高效進行樣本點歸類和離群點剔除，處理大規模數據時性能良好。相對于諸多傳統聚類算法，DPC具有用戶交互性、無迭代性、能識別任意形狀的簇等優點，但是計算局部密度ρ和高密度最鄰近距離δ需要測量數據集中任意兩點之間的歐氏距離，復雜度為O（N2）。當處理海量高維數據時，算法的實現涉及到大量的高維歐氏距離計算，造成大量的計算開銷，使其無法在單機環境下運行，嚴重影響了算法的實用性。

分布式 DPC 的挑戰，在基于MapReduced的簡單分布式密度中心聚類算法SDDPC[3]，SDDPC計算了兩個后續MapReduce作業中的ρ和δ值。這兩個工作有相似的計算程序： Map和shuffle階段主要用于發送和準備輸入數據，而Reduce階段分別執行ρ和δ的實際計算。然而，該算法必須將每一點都洗牌到其他點，計算出所有對點的距離，產生平方次計算和通信開銷。對于擁有數百萬點的大型數據集來說，這樣的代價將是非常高昂的，而百萬千萬的數據集在大數據時代，是越來越普遍了。SDPC[4]利用Spark GraphX優化了SDDPC的實現方式。MRDPC[5]采用簡單的幾何空間劃分對數據進行分塊處理，提出了獨立計算單元和獨立計算塊的概念，在進行獨立計算塊中的局部密度計算的過程中，降低了通信開銷，但聚類的準確率有所下降。EDDPC[3]是最近提出的并行 DPC 算法，它利用Voronoi圖和數據復制/過濾模型，大量減少距離測量和shuffle成本。

本文的貢獻如下：1）利用DPC算法的區域特性，提出適合DPC的分區方法;2）充分考慮分布式計算的因素，緊密結合RDD計算過程，在spark分布式平臺上實現了所提出的算法.

1 ? 相關工作

1.1 ? DPC

DPC是一類給定數據集S = {x1，x2，…，xn}，快速搜索密度峰值點的聚類算法。假設聚類中心對應某些具有局部極大密度估計值的樣本點，這些樣本點可以看作由低密度樣本點所包圍的“高密度峰值點”，距離其他高密度近鄰樣本相對較遠。算法通過快速搜索和發現代表聚類中心的“高密度峰值點”，將每個非中心樣本點沿著密度估計值遞增的最近鄰方向迭代移動到相應的聚類中心，實現數據劃分。這里涉及兩個基本概念：局部密度估計和高密度最近鄰距離。

式中：χ（d）表示核密度估計的核函數，常見的有兩種核函數形態，相應的密度估計公式如下：

1）截斷核估計

2）高斯核估計

式中： d（i，j）為樣本點xi、xj間的距離，采用滿足三角不等式的距離度量，如歐氏距離;dc > 0是預先指定的密度估計參數，相當于核函數的窗寬。由文獻[6]可知當數據量比較大時截斷核計算簡便且性能優于高斯核函數，當數據量較少時而高斯核估計則具有更好的魯棒性。因此本文采用適合海量數據處理的截斷核函數。

離群值δi則定義為到具有更大密度估計值的最近鄰樣本點的距離，即

1.2 ? Spark 平臺

Spark[7]由美國加州大學的伯克利分校的 AMP 實驗室首次提出的類HadoopMapReduce的基于內存計算的大數據并行計算框架。Spark 不同于MapReduce的是 job 的中間結果不需要再寫入本地的 HDFS，而是直接在內存中完成，可以更好的適用于機器學習以及數據挖掘的多次迭代的計算。Spark 最主要的創新點是提出了彈性分布式數據集RDD[8]（Resilient Distributed Dataset）。 RDD 本質上是一種只讀的分布式共享內存模型 ，它具備像MapReduce等數據流模型的容錯特性，并且允許開發人員在大型集群上執行內存的計算。對于數據分區來說 Spark 支持用戶自主確定分區策略，Hadoop的MapReduce在執行 Map 后一般需要花費大量的時間進行排序操作，這個主要由 shuffle 執行。Spark 雖然也有 shuffle 操作，但是 Spark 的 shuffle 不是在所有場景下都是必須的，因此可以很大程度地減輕開銷。

1.3 ? E2LSH

LSH[9]（Locality Sensitive Hashing）算法由Gionis提出的一種針對海量高維數據的快速最近鄰查找算法，它將原始數據從歐氏空間的準則下轉換到Hamming空間下便于進行局部敏感哈希運算，E2LSH[10]是基于p-stable分布的LSH方法的一種實現。

對一個實數集上的分布D，如果存在P≥0，對任何n個實數r1，r2，…，rn和n個滿足D分布的n個獨立同分布隨機變量X1，X2，…，Xn，∑i ri·Xi和（∑i |ri|p）（1/p） X）有相同的分布，其中X是服從D分布的一個隨機變量，則D分布被稱為一個p-stable分布[10]。對于任何p∈（0，2）存在穩定分布，當p = 2時是高斯分布，概率密度函數為：

p-stable分布具有如下性質：若兩個變量都服從p-stable分布，則其線性組合也服從p-stable分布[10]。

根據穩定分布性質，隨機變量a·v具有和（∑i |vi|p）（1/p） X）一樣的分布，其中隨機變量a中的每一維都是隨機的、獨立的從p-stable分布中產生的，因此可以用a·v對向量v來進行降維，并可以用它來估算‖v‖p[12]，很容易看出這個過程是可以線性組合的，也就是說a·（v1 - v2） = a·v1 - a·v2當p = 2時，兩個向量v1和v2的映射距離a·v1 - a·v2和

‖v1 - v2‖p X的分布是一樣的，此時對應的距離計算方式為歐氏距離。

2 ? ELSDPC

在DPC算法中鄰近點在計算中起著十分重要的作用。因此本文提出利用E2LSH來劃分數據，將距離較近的點分配到同一個分區。

2.1 ? 分區策略

本文并不用‖a·v‖p，來估算‖v‖p，而是使用它對每一個特征向量v賦予一個hash值。對于兩個向量v1和v2，如果它們之間的距離很近（‖v1-v2‖較小），它們將以很高的概率發生碰撞（hash值相同），如果它們之間的距離很遠，則沖突的概率將會很小。E2LSH中的hash數定義如下：

式中w表示窗口的大小b表示[0，w]之間的隨機變量。顯然通過這種分區方式能保證邊界點的鄰近節點會被分到同一個區域，能夠更準確地估計邊界區域中對象的局部密度。

LSH 的距離保持特性允許我們根據它們的哈希值對點集進行分區。如果兩個點 i 和 j 被散列到同一個桶，我們可以相信i 和 j是非常接近的。因此，我們可以將它們分配到相同的分區。然而，根據公式（7）有可能發生兩個距離較遠的點被哈希到同一個桶，即positive false[9]。為了減少positive false，可采用k個hash函數的組合G = {h1，h2，…，hk}來作為分區id。只有兩個點的k個hash值都分別有相同的值才會被分到同一個分區。產生的數據分區結果稱為E2LSH 分區布局p，定義如下：

定義1 給定一個數據點集合S，一組hash函數G = {h1，h2，…，hk}，通過對每一個點pi∈S使用G映射到一組k維向量G（pi） = {h1（pi），h2（pi），…，hk（pi）}表示的分區上。集合S也因此分為多個互不相交的子集，即P（S） = S1∪S2∪…，且？坌 m≠n，Sm∩Sn = ？準。

然而，也有可能是接近的點被hash到不同的分區，特別是當k比較大時，容易導致negtive false[9].為了減少negtive false的數量，我們采用了L個G函數{G1，G2，…，GL}.假設通過采用一個hash組函數Gl，可以得到一種E2LSH分區Pl（S） = Sl1∪Sl2∪…，Slm≠Sln，？坌 m≠n，Sm∩Sn = ？準，通過使用L個G函數，就可以的得到L種分區布局。如圖2所示展示了兩種分區方式。

在 map 階段，我們實現了多個 LSH 分區布局。對每一個對象pi進行L次G映射，并與pi進行組合得到L個鍵值對〈G1（pi），pi〉，〈G2（pi），pi〉，…，〈GM（pi），pi〉，每一個reduce（）函數都會收到一個特定E2LSH分區布局下的子集Slm。

2.2 ? ρ的近似估計

對于一個確定的E2LSH分區布局pi（S），它的一個子集Slm將會發送給一個reduce（）函數。reduce（）函數的第一步工作就是計算子集 中任意兩點之間的距離。然后計算每一個點i的局部密度 mi =

如圖1所示對象p2在布局1中位于分區S1和S2的邊界，因此 ?12< ρ，但是在布局2中對象p2的dc領域內的對象都在同一個分區，能得到 ?22= ρ，因此通過多個布局，然后取每個對象的最大值，能夠很大概率得到或者十分接近每個對象的局部密度。下面我們分析 li的概率Pr（ li = ρ）。

引理1 ? 給定一個點pi和一個E2LSH函數

證明：給定一個d維的隨機向量a，a的每一維都是獨立的隨機的從高斯分布N（0，1）（高斯分布是p取2時的穩定分布）中選取的變量，由p-stable分布的概率特性可知a·pi - a·pj 的分布和d（i，j）x的分布是一樣的，x是服從標準高斯隨機變量的絕對值，令yi = a·pi + b，因此對任意pj，d（i，j）≤dc有maxjyi - yj = maxja·pi - a·pj≤dc x，對任意一個位于特定槽內的yi，需要保證yi和它的dc領域內的點都位于同一個槽內，則yi需要滿足yi ∈[αw + dc w，（α + 1）w - dc]，如圖2所示，yi留在這個區域內概率為 ?= 1 - ?，而服從標準高斯分布的變量的絕對值的概率密度函數為

證明完畢。

2.3 ? δ的近似估計

在一種特定E2LSH的分區布局的一塊分區子集Slm中設計一種reduce（）函數來計算Slm中任意

兩個對象之間的距離，然后用{ i|j∈Pmk}估計

li = min j|j∈ ， i > ?jd（i，j），i∈Pmk，對于Slm中密度最大的點i = arg max i|i∈ ， i，令 li = ∞。

雖然 i很可能完全等價于的ρi，但是由于 li的計算是在子集中進行的。如圖1a所示p2的依附點與p2不在同一個分區，將本地的 li作為δi的近似時會得到錯誤的結果，將i的依附點定位到另外一顆密度樹中。如圖1b所示在另一種分區布局方式下，p2的依附點和p2在同一個分區則可以得到正確的 δ2和依附點σ2。將兩者結果進行適當合并則可以得到正確的結果。

假設 i = ρi，利用p-stable分布的性質，可得到引理3，通過下面的引理得到Pr[ li = δi] 。

引理3.給定一個點pi和一個E2LSH的hash函數，d（i，σi）表示pi和它的真實依附點σi（如果存在）的距離，則

Pδi（d（i，σi），w） = Pr[h（pi） = h（pσi）]

= ?fp 1- dx

= 2F -1- 1-e ?（10）

F（）表示密度為N（0，1）高斯分布的隨機變量的分布函數。

引理4.在一個擁有k個hash函數的特定E2LSH分區布局中，如果對象 的真實依附點存在，則Pr[ li = δi]=P δi（d（i，σi），w）k。

證明：對每一對象 ?，在L種不同的分區布局中可以得到L個近似值（ 1i， 2i，…， Li），通過公式（2）可知越小的高密度最鄰近距離越可能是真實的δi，因此令 i = minm ?mi，和ρ的估計類似，δi= i的條件是找到的 i就是σi，即需要對象i和其真實依賴點σi經過k次hash時，每次hash都會分到同一個區域，可得到概率Pr[ li = δi]=P δi（d（i，σi），w）k。證明完畢。

定理2.在L種E2LSH分區布局中，如果對象i的依附點存在則Pr[ i=δi]≥1-[1-P δi（d（i，σi），w）k]L。

2.4 ? 的進一步修改

如圖2和定理2所示，絕大多數點的δi，即d（i，σi）是比較小的，Pr[ i = δi]也能取得較大的值，但是當i和它的依附點的距離較大時，則容易出錯。顯然，能夠近似估計較小的δ，對較大的 則不能夠準確估計。顯然，密度峰值點通常有較大的 ，通過局部敏感hash函數很難被映射到同一個桶中，本地的密度峰值點很可能被選為全局的密度峰值點，導致過多的點被選為密度峰值點，形成過多的類。

為了糾正δ，需要找到容易被錯誤估計的點，根據定理2的結論，我們可以設定一個精確度閾值 ？撰δ，令

Pr[ i = δi] = 1 - [1 - P δi （d（i，σi），wk]L ≥？撰δ （11）

w，L，k會在聚類前確定，因此在式（12）中 是唯一的變量，我們可以得到滿足精確度閾值的d（i，σi）最小值γ。當d（i， i）≥d（i，σi）≥γ，δi的近似值很可能是錯誤的，需要進一步糾正。然而，精確地校正這些 i需要計算點i的到所有密度更高的點的距離。這將導致大量的計算和通信成本。相反，我們依靠粗略的矯正，考慮到δi計算只考慮到更高密度點的距離，我們對 較大的點進行采樣。點的密度越高，則采樣點的概率越高。在校正δi值時，只有這些采樣點作為距離測量的候選點。雖然這方法簡單，但實驗結果表明它是足夠有效的。

2.5 ? ELSDPC算法設計

算法1介紹了ELSDPC算法的主要流程，先使用spark入口函數讀取待聚類的數據集生成初始RDD集合，并進行持久化操作，采用算法2對數據進行分區。基于positive false 的影響，重復L-1次對初始RDD對分區，然后計算各自分區布局下的 ρ值，對各種分區布局下得到的ρ值進行處理得到最接近于關于各個數據項真實ρ的 值集合。對于 的處理，與ρ類似，不過需要對 進行進一步矯正，矯正后，重新選擇密度峰值點，并根據密度峰值點對對象進行分配。

算法1：ELSDPC算法

輸入：待聚類數據集，布局數量L，每種布局中函數個數k

輸出：（i，δi，σi）

1）指定分區數，若不指定分區數，默認為文件block數

2）sc=SparkContext（），指定spark程序的入口。

3）讀入數據生成RDD集合rddini = {（1，p1），（2，p1）}，…，（n，pn）}，同時用水塘采樣法對數據進行采樣，計算dc。

4）通過算法2對數據進行分區，得到RDD集合rddiniky，集合元素為

5）對rddiniky集合進行規約化操作，計算兩兩對象間的距離d（i，j），計算出ρ值，得到集合rddly，plist，元素為集合listp（）中的元素為（i，pi，ρi）

6）重復步驟（4），（5）L次，得到L個rddly，plist

7）計算ρ，對第一個rddly，plist進行處理得到rddly1，p，元素為對剩余L-1個rddly，plist進行處理得到rddly1，p，元素為，將rddly1，p和L-1個rddly，plist依次進行join連接，然后取出最大ρi作為每個對象的近似估計 i。

8）計算 ，方法與計算ρ雷同。

9）畫出決策圖，用戶依據自己的經驗和專業知識選擇ρpeak，δpeak，得到集合Dpeak={pi | ?i>ρpeak， i>δpeak }。

10）指定精確度閾值 得到滿足精確度閾值的 的d（i，σi）最小值，令γ = d（i，σi）min，，采用并行計算從RDD集合rddρ，δ的分區區中過濾出 i > γ的對象，作為待糾正對象rddtocorr，同時對數據進行采樣，如果 ?≥ ρpeak則以 的概率進行采樣，如果 ? < ρpeak則以β 的概率進行采樣，β是給定的采樣率。

11）計算需要被糾正的點到更高密度點的距離，如果找到一個更小的 i則對其進行更新。

12）重新選擇密度峰值點，并根據密度峰值點對對象進行重新分配。

算法2：分區算法

輸入：函數個數k，RDD集合rddini = {（1，p1），（2，p1）}，…，（n，pn）}

輸出：RDD集合rddiniky，集合元素為

1）隨機生成一組hash函數簇G={h1，h2，…，hk}

2）將pi分別與h1，h2，…，hk相乘，得到G（pi）={h1（pi），h2（pi），…，hk（pi）}

3）以作為集合元素輸出

3 ? 時間復雜度

3.1 ? shuffle成本

通過Spark的內存計算特性，適當的轉化操作和持久化操作能夠從分區中獲益，使得shuffle成本大大減少，使得shuffle的消耗主要集中在算法1的step7中。假設數據集的維度為，則shuffle成本可以被近似定義為[3]：

Cs（w，k，L） = 2[（L - 1）·N + di·N] ?（12）

di表示數據的維度。類似的，SDDPC、EDDPC也采取最主要shuffle消耗進行計算，假設SDDPC每個分區可處理n個數據，SDDPC的shuffle成本可以定義為di·（N）2/n，EDDPC采用復制/過濾模型降低了shuffle成本，但十分依賴數據集的實際分布，在極端情況下shuffle成本仍舊可能接近di·（N）2/n。顯然，當數據量越大，ELSDPS相較與SDDPC和EDDPC的shuffle成本的優化越明顯。

3.2 ? 計算成本

計算發生在E2LSH分區、距離計算ρ、δ的近似估計，其中距離計算是最主要的計算成本。因為在特定布局的一個分區Slm中都會計算一個距離矩陣 Dlm，Dlm中的元素表示Slm中任意兩個對象的距離，大小為Nlm × Nlm（Nlm表示Slm中對象的個數）。因此本文使用距離計算的次數作為計算成本的估計，定義如下[3]：

E[Cc（w，k，L）]=E[ ?（Nlm）2=L· N2m （13）

其中M表示分區數。類似的，SDDPC的計算成本可以定義為N2 = （ （Nm）2），EDDPC也根據最主要的計算消耗將計算成本定義為 N2m。

3.3 ? 參數調節-L，k，w的選取

ELSDPC算法主要是根據 對數據集進行聚類，對象 被分配到正確類簇的概率為Pr[ li = ρi]·Pr[ li = δi]，然而根據定理二可知 i的準確度十分依賴于真實的δi，不能夠在實驗前得到，因此通過分析 ?的準確度，來定義準確度閾值：

？撰（w，k，L） = ？撰ρ（w，k，L） = 1-[1-Pρ（w，dc）k]M

（14）

假定shuffle一個字節的時間和計算一對對象的距離的時間比例為μ，則優化目標可以描述為滿足1-[1-Pρ（w，dc）k]M≥？撰且使得μ·2[（L-1）·N+S] + 2L·∑M ? ? ?m=1（Nm）2能夠取得最小值的參數求解問題。

從定理1可知隨著L，w的增加，k的減少都會提高準確度。而shuffle成本和計算成本則都隨著 L的增加而增加。計算成本同時受到∑M ? ? ?m=1（Nlm）2的影響，而∑M ? ? ?m=1（Nlm）2也會受到w，k的影響，w變小，k變大都會導致產生更多較小的Nm，從而可能得到較小的∑M ? ? ?m=1（Nlm）2。因此L，w，k三個參數對準確度和時間效率的作用是相反的。

綜上所述，需要在保證給定精度要求下調整L，w，k來獲得最小化運行時間。由于計算成本 （主要由∑M ? ? ?m=1（Nlm）2決定） ，不僅僅取決于 E2LSH 參數L，w，k，還依賴數據的分布，最優化的問題不能在沒有數據知識的情況下解決。通過采樣數據點來調整離線參數。通過分布式水塘采樣法采樣得到h

組N個對象，然后對這h組對象分別執行E2LSH分區法，得到h個E2LSH布局，即可得到 h個

∑ ? ? m=1（N′m）2，計算其均值，并通過放大 ?倍來估計計算成本即∑ ? ? ?m=1（Nlm）2≈ ?· 。同時，通過貪婪啟發算法來尋找最優化參數集。

首先，先將L，k固定為L0，k0，通過給定的準確度？撰求得w的最小值w0，然后通過L0，k0，

∑ ? ? ?m（Nlm）2的預測值得到總的時間消耗T0。

接下來，令L+x=L0+x，L-x=L0-x（x表示步長，且x∈A+），同時固定k0，計算出T+x，T-x，我們選擇擁有較小時間成本的L并固定，然后令k+y=k0+y，k-y=k0-y，同樣選擇導致時間成本較小的k。通過調節L，k不斷重復上述過程直到時間成本T不在隨著 L，k的變化而減少，這時候將（L，k，w）作為結果返回。

4 ? 實驗與結果分析

4.1 ? 實驗環境和數據集

實驗環境為Linux操作系統，spark本地集群，包括一臺master機器和4臺slave機器，各節點虛擬機處理器配置為Intel Xeon CPU E5-2650 v2，內存4GB。表1中列出了我們采用的數據集[13]，包括1個小規模的2D 數據集，四個大中型高維數據集，使用2D 數據集來可視化聚類結果，大中型數據集以評估本地集群的效率和有效性。

4.2 ? ELSDPC算法的有效性

在 ELSDPC中，根據3.3.2節所示，將參數設置為？撰 = 0.99，L = 5，k = 3。

為了使聚類結果可視化，在小型2D 數據集s2上運行了DPC 和 ELSDPC。如圖3所示DPC和ELSDPC的聚類結果幾乎是相同的。差異僅存在于邊界點和決定一組點是否應以更細的粒度聚集。

4.3 ? ELSDPC算法的效率

Facial，KDD，3Dspatia，BigCross500K四個數據集上依次分別運行SDDPC ，ELSDPC算法。ELSDPC參數設置為？撰 = 0.99，L = 5，k = 3，SDDPC每個分區處理2000個數據集。

①shuffle成本，圖5b比較了SDDPC和ELSDPC在數據混洗過程中的shuffle成本，在SDDPC中需要將所有點都復制到其他分區中，而在ELSDPC中主要將ELSDPC分區計算的結果進行shuffle，避免了平方次通信的消耗。如圖5b所示，相比SDDPC，ELSDPC可以達到5-87x的收益，隨著數據量和增大，收益越明顯。

（a）運行時間

（b）shuffle成本

（c）計算成本

②計算成本，圖5c展示了兩種算法中距離計算的次數，SDDPC的計算成本呈平方式增長，ELSDPC則呈線性增長趨勢，如圖5c所示，隨著數據量的增大，ELSDPC相比SDDPC的計算成本能獲得收益更加明顯。

表2 ? BigCross500K不同算法下聚類效率表

表2中，我們可以看到，盡管相比EDDPC，ELSDPC需要更多的計算次數，但通過更少的shuffle成本，比起EDDPC仍只需要更少的運行時間;MRDPC采用立方體進行切割，并將立方體與周圍的立方體內的數據，進行距離計算和shuffle，ELSDPC的計算次數和shuffle消耗明顯優于MRDPC，同時MRDPC的立體幾何劃分方式沒有考慮DPC算法中鄰近點的不規則性，導致算法的準確率也遠遠低與ELSDPC。

4.4 ? 參數L K的影響

本節主要研究參數L，k的影響。通過在在本地機器集群上使用運用ELSDPC算法對BigCross500K 數據集進行聚類，設置？撰 = 0.99。通過離線參數調節（第3.3.2節） 方法返回L = 5和k = 3。我們進一步變化的L和k，圖6a和圖7顯示了參數L，k對運行時間和準確度的影響。如圖6a所示，當k = 3 時，運行時間隨著L的增加而增加;但是當k很大時，情況則有所不用，當k = 20，趨勢實際上在逆轉，這是因為當L較小而k很大時，會發生嚴重的工作負載傾斜，從而導致性能下降。圖6b顯示了參數L，k的選擇對準確率的影響。當L小于5時，準確率異常低，這可能會降低群集結果的質量。另一方面，當L大于 5時，準確率十分穩定，幾乎所有情況下準確率都達到了99%。考慮參數對運行效率和準確率的影響，本文建議設置L = [5，20] 和k = [3，10]。

5 ? 結 ? 論

提出了一種分布式聚類算法EDDPC，根據LSH對數據集進行劃分，然后提出多次hash對分區后的計算結果進行修正，保證聚類的質量;同時在Spark分布式平臺上，利用RDD實現了算法。文中使用UCI的數據集對改進算法進行了一系列實驗，實驗結果表明，使用ELSDPC聚類算法在能保證良好聚類結果的精度的同時表現出良好的數據伸縮率和可擴展性，算法具有處理海量高維數據的能力。

參考文獻

[1] ? ?HAN Jia-wei，INEKAMER M. 數據挖掘：概念與技術[M]. 機械工業出版社，2007.

[2] ? ?RODRIGUEZ A，LAIO A. Clustering by fast search and find of density peaks[J]. Science，2014，344（6191）：1492.

[3] ? GONG S，ZHANG Y. EDDPC：an efficient distributed density peaks clustering algorithm[J]. Journal of Computer Research & Development，2016，6（53）：1400—1409.

[4] ? ?LIU R，LI X，DU L，et al. Parallel implementation of density peaks clustering algorithm based on spark[J]. Procedia Computer Science，2017，107（C）：442—447.

[5] ? WANG Y，PENG T，HAN J Y，et al. Density-based distributed clustering method[D]. 長春：吉林大學，2017.

[6] ? ?HOU J，LIU W. Evaluating the density parameter in density peak based clustering[C]// Seventh International Conference on Intelligent Control and Information Processing. IEEE，2017：68—72.

[7] ? ZAHARIA M，CHOWDHURY M，FRANKLIN M J，et al. Spark： cluster computing with working sets[C]// Usenix Conference on Hot Topics in Cloud Computing. USENIX Association，2010：10—10.

[8] ? ZAHARIA M，CHOWDHURY M，DAS T，et al. Resilient distributed datasets： a fault-tolerant abstraction for in-memory cluster computing[C]// Usenix Conference on Networked Systems Design and Implementation. USENIX Association，2012：2—2.

[9] ? ?INDYK P. Approximate nearest neighbors： towards removing the curse of dimensionality[C]// ACM Symposium on Theory of Computing. 1998：604—613.

[10] ?DATAR M，IMMORLICA N，INDYK P，et al. Locality-sensitive hashing scheme based on p-stable distributions[C]// Proc. Symposium on Computational Geometry. 2004：253—262.

[11] ?ESREADA R，RUIZ I.The language： scala[M]. Big Data SMACK：Apress，Berkeley，CA，2016.

[12] ?LAHA R G. Book review： one-dimensional stable distributions[J]. Bulletin of the American Mathematical Society，1989，20（2）：270—278.

[13] ?LICHMAN M. UCI machine learning repository[EB/CD]. http：//archive.ics.uci.edu/ml，2013.

[14] ?VINH N X，EPPS J，BAILEY J. Information theoretic measures for clusterings comparison： is a correction for chance necessary？[C]// International Conference on Machine Learning. ACM，2009：1073—1080.

[15] ?HE Y，TAN H，LUO W，et al. MR-DBSCAN： an efficient parallel density-Based clustering algorithm using mapreduce[C]// IEEE，International Conference on Parallel and Distributed Systems. IEEE，2012：473—480.