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

何仝 徐蔚鴻 馬紅華 曾水玲

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

關(guān)鍵詞：聚類;密度峰值;大數(shù)據(jù);局部敏感哈希;Spark

中圖分類號(hào)： TP311.1 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：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

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

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

本文的貢獻(xiàn)如下：1）利用DPC算法的區(qū)域特性，提出適合DPC的分區(qū)方法;2）充分考慮分布式計(jì)算的因素，緊密結(jié)合RDD計(jì)算過程，在spark分布式平臺(tái)上實(shí)現(xiàn)了所提出的算法.

1 ? 相關(guān)工作

1.1 ? DPC

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

式中：χ（d）表示核密度估計(jì)的核函數(shù)，常見的有兩種核函數(shù)形態(tài)，相應(yīng)的密度估計(jì)公式如下：

1）截?cái)嗪斯烙?jì)

2）高斯核估計(jì)

式中： d（i，j）為樣本點(diǎn)xi、xj間的距離，采用滿足三角不等式的距離度量，如歐氏距離;dc > 0是預(yù)先指定的密度估計(jì)參數(shù)，相當(dāng)于核函數(shù)的窗寬。由文獻(xiàn)[6]可知當(dāng)數(shù)據(jù)量比較大時(shí)截?cái)嗪擞?jì)算簡(jiǎn)便且性能優(yōu)于高斯核函數(shù)，當(dāng)數(shù)據(jù)量較少時(shí)而高斯核估計(jì)則具有更好的魯棒性。因此本文采用適合海量數(shù)據(jù)處理的截?cái)嗪撕瘮?shù)。

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

1.2 ? Spark 平臺(tái)

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

1.3 ? E2LSH

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

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

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

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

‖v1 - v2‖p X的分布是一樣的，此時(shí)對(duì)應(yīng)的距離計(jì)算方式為歐氏距離。

2 ? ELSDPC

在DPC算法中鄰近點(diǎn)在計(jì)算中起著十分重要的作用。因此本文提出利用E2LSH來劃分?jǐn)?shù)據(jù)，將距離較近的點(diǎn)分配到同一個(gè)分區(qū)。

2.1 ? 分區(qū)策略

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

式中w表示窗口的大小b表示[0，w]之間的隨機(jī)變量。顯然通過這種分區(qū)方式能保證邊界點(diǎn)的鄰近節(jié)點(diǎn)會(huì)被分到同一個(gè)區(qū)域，能夠更準(zhǔn)確地估計(jì)邊界區(qū)域中對(duì)象的局部密度。

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

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

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

在 map 階段，我們實(shí)現(xiàn)了多個(gè) LSH 分區(qū)布局。對(duì)每一個(gè)對(duì)象pi進(jìn)行L次G映射，并與pi進(jìn)行組合得到L個(gè)鍵值對(duì)〈G1（pi），pi〉，〈G2（pi），pi〉，…，〈GM（pi），pi〉，每一個(gè)reduce（）函數(shù)都會(huì)收到一個(gè)特定E2LSH分區(qū)布局下的子集Slm。

2.2 ? ρ的近似估計(jì)

對(duì)于一個(gè)確定的E2LSH分區(qū)布局pi（S），它的一個(gè)子集Slm將會(huì)發(fā)送給一個(gè)reduce（）函數(shù)。reduce（）函數(shù)的第一步工作就是計(jì)算子集 中任意兩點(diǎn)之間的距離。然后計(jì)算每一個(gè)點(diǎn)i的局部密度 mi =

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

引理1 ? 給定一個(gè)點(diǎn)pi和一個(gè)E2LSH函數(shù)

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

證明完畢。

2.3 ? δ的近似估計(jì)

在一種特定E2LSH的分區(qū)布局的一塊分區(qū)子集Slm中設(shè)計(jì)一種reduce（）函數(shù)來計(jì)算Slm中任意

兩個(gè)對(duì)象之間的距離，然后用{ i|j∈Pmk}估計(jì)

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

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

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

引理3.給定一個(gè)點(diǎn)pi和一個(gè)E2LSH的hash函數(shù)，d（i，σi）表示pi和它的真實(shí)依附點(diǎn)σ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）高斯分布的隨機(jī)變量的分布函數(shù)。

引理4.在一個(gè)擁有k個(gè)hash函數(shù)的特定E2LSH分區(qū)布局中，如果對(duì)象 的真實(shí)依附點(diǎn)存在，則Pr[ li = δi]=P δi（d（i，σi），w）k。

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

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

2.4 ? 的進(jìn)一步修改

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

為了糾正δ，需要找到容易被錯(cuò)誤估計(jì)的點(diǎn)，根據(jù)定理2的結(jié)論，我們可以設(shè)定一個(gè)精確度閾值 ？撰δ，令

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

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

2.5 ? ELSDPC算法設(shè)計(jì)

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

算法1：ELSDPC算法

輸入：待聚類數(shù)據(jù)集，布局?jǐn)?shù)量L，每種布局中函數(shù)個(gè)數(shù)k

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

1）指定分區(qū)數(shù)，若不指定分區(qū)數(shù)，默認(rèn)為文件block數(shù)

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

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

4）通過算法2對(duì)數(shù)據(jù)進(jìn)行分區(qū)，得到RDD集合rddiniky，集合元素為

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

6）重復(fù)步驟（4），（5）L次，得到L個(gè)rddly，plist

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

8）計(jì)算 ，方法與計(jì)算ρ雷同。

9）畫出決策圖，用戶依據(jù)自己的經(jīng)驗(yàn)和專業(yè)知識(shí)選擇ρpeak，δpeak，得到集合Dpeak={pi | ?i>ρpeak， i>δpeak }。

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

11）計(jì)算需要被糾正的點(diǎn)到更高密度點(diǎn)的距離，如果找到一個(gè)更小的 i則對(duì)其進(jìn)行更新。

12）重新選擇密度峰值點(diǎn)，并根據(jù)密度峰值點(diǎn)對(duì)對(duì)象進(jìn)行重新分配。

算法2：分區(qū)算法

輸入：函數(shù)個(gè)數(shù)k，RDD集合rddini = {（1，p1），（2，p1）}，…，（n，pn）}

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

1）隨機(jī)生成一組hash函數(shù)簇G={h1，h2，…，hk}

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

3）以作為集合元素輸出

3 ? 時(shí)間復(fù)雜度

3.1 ? shuffle成本

通過Spark的內(nèi)存計(jì)算特性，適當(dāng)?shù)霓D(zhuǎn)化操作和持久化操作能夠從分區(qū)中獲益，使得shuffle成本大大減少，使得shuffle的消耗主要集中在算法1的step7中。假設(shè)數(shù)據(jù)集的維度為，則shuffle成本可以被近似定義為[3]：

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

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

3.2 ? 計(jì)算成本

計(jì)算發(fā)生在E2LSH分區(qū)、距離計(jì)算ρ、δ的近似估計(jì)，其中距離計(jì)算是最主要的計(jì)算成本。因?yàn)樵谔囟ú季值囊粋€(gè)分區(qū)Slm中都會(huì)計(jì)算一個(gè)距離矩陣 Dlm，Dlm中的元素表示Slm中任意兩個(gè)對(duì)象的距離，大小為Nlm × Nlm（Nlm表示Slm中對(duì)象的個(gè)數(shù)）。因此本文使用距離計(jì)算的次數(shù)作為計(jì)算成本的估計(jì)，定義如下[3]：

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

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

3.3 ? 參數(shù)調(diào)節(jié)-L，k，w的選取

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

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

（14）

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

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

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

組N個(gè)對(duì)象，然后對(duì)這h組對(duì)象分別執(zhí)行E2LSH分區(qū)法，得到h個(gè)E2LSH布局，即可得到 h個(gè)

∑ ? ? m=1（N′m）2，計(jì)算其均值，并通過放大 ?倍來估計(jì)計(jì)算成本即∑ ? ? ?m=1（Nlm）2≈ ?· 。同時(shí)，通過貪婪啟發(fā)算法來尋找最優(yōu)化參數(shù)集。

首先，先將L，k固定為L(zhǎng)0，k0，通過給定的準(zhǔn)確度？撰求得w的最小值w0，然后通過L0，k0，

∑ ? ? ?m（Nlm）2的預(yù)測(cè)值得到總的時(shí)間消耗T0。

接下來，令L+x=L0+x，L-x=L0-x（x表示步長(zhǎng)，且x∈A+），同時(shí)固定k0，計(jì)算出T+x，T-x，我們選擇擁有較小時(shí)間成本的L并固定，然后令k+y=k0+y，k-y=k0-y，同樣選擇導(dǎo)致時(shí)間成本較小的k。通過調(diào)節(jié)L，k不斷重復(fù)上述過程直到時(shí)間成本T不在隨著 L，k的變化而減少，這時(shí)候?qū)ⅲ↙，k，w）作為結(jié)果返回。

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

4.1 ? 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)集

實(shí)驗(yàn)環(huán)境為L(zhǎng)inux操作系統(tǒng)，spark本地集群，包括一臺(tái)master機(jī)器和4臺(tái)slave機(jī)器，各節(jié)點(diǎn)虛擬機(jī)處理器配置為Intel Xeon CPU E5-2650 v2，內(nèi)存4GB。表1中列出了我們采用的數(shù)據(jù)集[13]，包括1個(gè)小規(guī)模的2D 數(shù)據(jù)集，四個(gè)大中型高維數(shù)據(jù)集，使用2D 數(shù)據(jù)集來可視化聚類結(jié)果，大中型數(shù)據(jù)集以評(píng)估本地集群的效率和有效性。

4.2 ? ELSDPC算法的有效性

在 ELSDPC中，根據(jù)3.3.2節(jié)所示，將參數(shù)設(shè)置為？撰 = 0.99，L = 5，k = 3。

為了使聚類結(jié)果可視化，在小型2D 數(shù)據(jù)集s2上運(yùn)行了DPC 和 ELSDPC。如圖3所示DPC和ELSDPC的聚類結(jié)果幾乎是相同的。差異僅存在于邊界點(diǎn)和決定一組點(diǎn)是否應(yīng)以更細(xì)的粒度聚集。

4.3 ? ELSDPC算法的效率

Facial，KDD，3Dspatia，BigCross500K四個(gè)數(shù)據(jù)集上依次分別運(yùn)行SDDPC ，ELSDPC算法。ELSDPC參數(shù)設(shè)置為？撰 = 0.99，L = 5，k = 3，SDDPC每個(gè)分區(qū)處理2000個(gè)數(shù)據(jù)集。

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

（a）運(yùn)行時(shí)間

（b）shuffle成本

（c）計(jì)算成本

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

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

表2中，我們可以看到，盡管相比EDDPC，ELSDPC需要更多的計(jì)算次數(shù)，但通過更少的shuffle成本，比起EDDPC仍只需要更少的運(yùn)行時(shí)間;MRDPC采用立方體進(jìn)行切割，并將立方體與周圍的立方體內(nèi)的數(shù)據(jù)，進(jìn)行距離計(jì)算和shuffle，ELSDPC的計(jì)算次數(shù)和shuffle消耗明顯優(yōu)于MRDPC，同時(shí)MRDPC的立體幾何劃分方式?jīng)]有考慮DPC算法中鄰近點(diǎn)的不規(guī)則性，導(dǎo)致算法的準(zhǔn)確率也遠(yuǎn)遠(yuǎn)低與ELSDPC。

4.4 ? 參數(shù)L K的影響

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

5 ? 結(jié) ? 論

提出了一種分布式聚類算法EDDPC，根據(jù)LSH對(duì)數(shù)據(jù)集進(jìn)行劃分，然后提出多次hash對(duì)分區(qū)后的計(jì)算結(jié)果進(jìn)行修正，保證聚類的質(zhì)量;同時(shí)在Spark分布式平臺(tái)上，利用RDD實(shí)現(xiàn)了算法。文中使用UCI的數(shù)據(jù)集對(duì)改進(jìn)算法進(jìn)行了一系列實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，使用ELSDPC聚類算法在能保證良好聚類結(jié)果的精度的同時(shí)表現(xiàn)出良好的數(shù)據(jù)伸縮率和可擴(kuò)展性，算法具有處理海量高維數(shù)據(jù)的能力。

參考文獻(xiàn)

[1] ? ?HAN Jia-wei，INEKAMER M. 數(shù)據(jù)挖掘：概念與技術(shù)[M]. 機(jī)械工業(yè)出版社，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]. 長(zhǎng)春：吉林大學(xué)，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，F(xiàn)RANKLIN 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.