李淋淋，倪建成，曹 博，于蘋蘋，姚彬修

(1.曲阜師范大學(xué) 信息科學(xué)與工程學(xué)院，山東 日照 276826；2.曲阜師范大學(xué) 軟件學(xué)院，山東 曲阜 273100)

基于Spark框架的并行聚類算法

李淋淋1，倪建成2，曹 博1，于蘋蘋1，姚彬修1

(1.曲阜師范大學(xué) 信息科學(xué)與工程學(xué)院，山東 日照 276826；2.曲阜師范大學(xué) 軟件學(xué)院，山東 曲阜 273100)

針對傳統(tǒng)K-means算法在處理海量數(shù)據(jù)時存在距離計算瓶頸及因迭代計算次數(shù)增加導(dǎo)致內(nèi)存不足的問題，提出了一種基于Spark框架的SBTICK-means(SparkBasedTriangleInequalityCanopy-K-means)并行聚類算法。為了更好地解決K值選取的盲目性和隨機性的問題，該算法利用Canopy進行預(yù)處理得到初始聚類中心點和K值；在K-means迭代計算過程中進一步利用距離三角不等式定理減少冗余計算、加快聚類速度，結(jié)合Spark框架實現(xiàn)算法的并行化，充分利用Spark的內(nèi)存計算優(yōu)勢提高數(shù)據(jù)的處理速度，縮減算法的整體運行時間。實驗結(jié)果表明，SBTICK-means算法在保證準(zhǔn)確率的同時大大提高了聚類效率，與傳統(tǒng)的K-means算法、Canopy-K-means算法和基于MapReduce框架下的該算法相比，在加速比、擴展比以及運行速率上都有一定的提高，從而更適合應(yīng)用于海量數(shù)據(jù)的聚類研究。

K-means；Spark；大數(shù)據(jù)；Hadoop；MapReduce

0 引 言

K-means聚類算法因其執(zhí)行簡單、快速、易于并行化，并可以提供直觀結(jié)果等優(yōu)點而成為數(shù)據(jù)挖掘和非監(jiān)督式學(xué)習(xí)中的流行算法[1]，但它也存在以下問題[2]：K值(簇數(shù))是人為確定的，在對數(shù)據(jù)不了解的情況下很難給出合理的K值；初始中心點的選擇是隨機的，若選擇到較為孤立的點，會嚴(yán)重影響聚類結(jié)果；算法在每次迭代時都需要進行大量的距離計算來確定新的聚類中心，然而其中許多計算都是冗余的；傳統(tǒng)的串行K-means算法在處理大規(guī)模數(shù)據(jù)集時運行效率非常低。

針對以上問題，學(xué)者們不斷地進行研究和優(yōu)化。例如，張石磊等[3]提出使用Hadoop平臺下的MapReduce框架實現(xiàn)K-means的分布式聚類，提高了聚類速度；衣治安等[4]提出在MapReduce框架的基礎(chǔ)上利用Canopy算法進行優(yōu)化，提高了聚類的準(zhǔn)確率；王永貴等[5]提出基于MapReduce的隨機抽樣K-means算法，通過對數(shù)據(jù)集進行多次隨機采樣，優(yōu)化初始聚類中心，增強了聚類的穩(wěn)定性；毛典輝[6]提出了一種基于MapReduce的Canopy-K-means優(yōu)化算法，采用“最大最小原則”對該算法進行改進，避免了Canopy算法選取的盲目性，進一步提高了聚類的準(zhǔn)確率和“抗噪”的能力。

為了進一步減少數(shù)據(jù)聚類迭代過程中的冗余計算，加快聚類速度，提高聚類準(zhǔn)確率，故綜合以上聚類優(yōu)化算法的各種優(yōu)點，結(jié)合Spark計算框架，提出了SBTICK-means并行聚類算法。通過Spark框架的內(nèi)存迭代計算優(yōu)勢[7]提高了數(shù)據(jù)處理的速度，利用Canopy算法解決了K-means算法初始中心點的預(yù)選取和孤立點處理問題，利用距離三角不等式定理[8-9]解決了聚類過程中距離冗余計算的問題。以UCI標(biāo)準(zhǔn)數(shù)據(jù)集進行測試，并與MapReduce框架[10]下的結(jié)果進行比較、分析，以此驗證SBTICK-means算法具有較好的聚類質(zhì)量和較快的聚類速度，更適合應(yīng)用于海量數(shù)據(jù)的聚類分析中。

1 相關(guān)工作

1.1 Spark框架

Spark是一套開源的、基于內(nèi)存的，可以運行在分布式集群上的并行計算框架[11-12]，與MapReduce相比，有以下幾點優(yōu)勢[13]：

(1)中間結(jié)果不輸出到磁盤上，而是使用有向無環(huán)圖將各階段的任務(wù)串聯(lián)起來或者并行執(zhí)行。

(2)使用RDD作為分布式索引來對數(shù)據(jù)進行分區(qū)和處理。

(3)MapReduce在數(shù)據(jù)Shuffle時每次都花費大量時間來排序，而Spark任務(wù)在Shuffle中不是所有情況都需要排序。

1.2 基本概念

定理1(三角不等式定理)：假設(shè)空間中任意三個數(shù)據(jù)點x,y,z,如果d(y,z)≥2d(x,y)，則d(x,z)≥d(x,y)。

推論1：由定理1可以得出，對于數(shù)據(jù)點x，數(shù)據(jù)聚類中心點Q1,Q2，如果d(Q1,Q2)≥2d(x,Q1)，則數(shù)據(jù)點x被標(biāo)記到Q1所屬的類中。

2 SBTICK-means并行聚類算法

2.1 算法思想

該算法首先利用Canopy算法對K-means算法進行優(yōu)化，得到初始聚類中心點和K值，然后在K-means聚類過程中引入三角不等式定理進行“精”聚類，最后使用Spark框架實現(xiàn)該算法的并行化。因此，基于Spark框架的SBTICK-means算法主要分為兩個階段，其流程如圖1所示。

圖1 SBTICK-means并行聚類算法流程

階段一為Canopy算法在Spark框架中的執(zhí)行過程：

(1)從分布式文件系統(tǒng)HDFS[14-15]上讀取原始數(shù)據(jù)集D生成RDD，并通過map操作將數(shù)據(jù)集格式化為向量。

(2)在每個子節(jié)點分別map計算數(shù)據(jù)點與Canopy中心點間的歐氏距離。

(3)根據(jù)Canopy算法規(guī)則對每個數(shù)據(jù)點進行標(biāo)記，直到數(shù)據(jù)集D為空時結(jié)束，得出局部Canopy中心點。

(4)將各子節(jié)點得出的Canopy中心點通過reduce匯總得出全局的Canopy中心點。

階段二為基于三角不等式定理的K-means聚類算法在Spark框架中的執(zhí)行過程：

(1)將第一階段計算得出的Canopy中心點作為初始聚類中心。

(2)啟動各子節(jié)點的map任務(wù)，分別計算各數(shù)據(jù)點與聚類中心點的距離、各聚類中心點彼此間的距離。

(3)按照三角不等式定理對每個滿足條件的數(shù)據(jù)點進行相應(yīng)簇的劃分，對不滿足條件的數(shù)據(jù)點按照最短距離原則進行相應(yīng)簇的劃分。

(4)由Combine合并中間結(jié)果，并通過Reduce進行局部聚類中心點的更新和匯總。

(5)判斷結(jié)果是否收斂，若收斂則算法結(jié)束，否則返回步驟(2)。

2.2 基于Spark框架的SBTICK-means算法并行化實現(xiàn)

2.2.1 Canopy算法的并行化實現(xiàn)

由于K-means算法中的K值選取具有一定的盲目性和隨機性，因此使用Canopy算法對其進行優(yōu)化，以確定K-means的初始聚類中心點和K值。該算法可以高效地將數(shù)據(jù)劃分為幾個可重疊子集(即canopy)，從而避免聚類過程中局部最優(yōu)的出現(xiàn)，有效提高了大規(guī)模數(shù)據(jù)的處理效率。該階段主要實現(xiàn)Canopy算法的并行化，其具體實現(xiàn)的偽代碼如下所示：

Input：待處理數(shù)據(jù)集D(d1,d2,…,dn)，參數(shù)T1，T2(T1>T2，采用交叉檢驗方式獲得)

Output：Canopy中心點集合Q(Q1,Q2,…,Qn)

1)If(Q=Null)

2)任選一數(shù)據(jù)點作為Canopy中心點，并從D中刪除

3)While(D!=Null)

4)遍歷D，計算每個數(shù)據(jù)點到Q中點的距離

5)If(dist[i]

6)ElseIf(dist[i]>T1) 將該點加入Q中，并從D中刪除

7)Else將該點加入Q中此點所屬的Canopy

8)EndIf

9)EndWhile

2.2.2 基于三角不等式定理的K-means算法并行化實現(xiàn)

該階段主要實現(xiàn)K-means算法的并行化，利用預(yù)處理得到的Canopy中心點作為初始中心點完成“精”聚類。此外，為進一步加快聚類速度，引入三角不等式定理。由推論可知，通過三角不等式定理的判定，可以有效減少迭代過程中不必要的距離計算，將各數(shù)據(jù)點快速劃入所屬簇中，從而大大加快了聚類速度。其具體實現(xiàn)的偽代碼如下所示：

Map函數(shù)：

Input：Canopy中心點集合List(c1,c2,…,cn)，K值，數(shù)據(jù)集D(d1,d2,…,dn)

Output：聚類中心點集合W'

1)While(W!=List)

2)計算List任意兩點間的距離d(c,c')

3)將最短距離S(c)=min(d(c,c'))保存到數(shù)組Array1

4)依次計算D中每一個數(shù)據(jù)點到List中各點的距離dist'[i]

5)If2dist'[i]≤S記錄此點屬于第i個Canopy中心點的簇，然后從D中刪掉此點，并對不滿足條件的數(shù)據(jù)點，將其到該中心點的距離保存到數(shù)組Array2

6)EndIf

7)If(D!=Null)

8)將上述不滿足條件的數(shù)據(jù)點，根據(jù)計算的點到中心點的距離，將其劃分給距離最小的簇心并進行標(biāo)記

9)EndIf

10)重新計算所有被標(biāo)記點的新簇心W'

11)IfW=W'Break

12)Else返回2)

13)EndWhile

Combine函數(shù)：

Input：D中數(shù)據(jù)點所對應(yīng)下標(biāo)key，key值所屬

Output：D中數(shù)據(jù)點所對應(yīng)下標(biāo)key，每個簇中已被標(biāo)記的所有數(shù)據(jù)點的各維累加值，key值所屬

解析各維坐標(biāo)值，求出各維累加值和，并保存到對應(yīng)列表中

Reduce函數(shù)：

Input：D中數(shù)據(jù)點所對應(yīng)下標(biāo)key，key值所屬

Output：D中數(shù)據(jù)點所屬簇的下標(biāo)key，最終簇心W'

1)While(D.hasNext())

2)初始化num=0記錄所屬簇內(nèi)數(shù)據(jù)點的數(shù)目

3)解析D.next()中的各維下標(biāo)值，計算num

4)計算各維下標(biāo)值累加和并存儲到對應(yīng)列表中

5)num++

6)EndWhile

7)匯總得出最終簇心W'，并返回生成全局結(jié)果

在每一次Reduce執(zhí)行完成后，比較新簇心與前一次的簇心，如果不發(fā)生變化(即收斂)則算法結(jié)束，否則繼續(xù)執(zhí)行上述過程直到收斂。最后集群上每個節(jié)點的數(shù)據(jù)點都被劃分到對應(yīng)的簇中，主節(jié)點匯總信息得出最終聚類結(jié)果。

SBTICK-means并行聚類算法在保持較高聚類準(zhǔn)確率的前提下，不僅解決了聚類中心預(yù)選取和減少迭代冗余計算的問題，而且將其成功應(yīng)用于Spark框架中，充分利用其內(nèi)存計算優(yōu)勢，大大提高了聚類速度。與基于MapReduce的框架相比，該算法在處理海量數(shù)據(jù)時，運行時間更短，因此所提出的SBTICK-means算法更適合應(yīng)用于大數(shù)據(jù)的聚類分析中。

3 實 驗

3.1 實驗環(huán)境、測試數(shù)據(jù)集及評價指標(biāo)

實驗平臺是在Hadoop2.6.0的YARN基礎(chǔ)上部署Spark框架，在Vcenter中創(chuàng)建6臺虛擬機，包含1個Master節(jié)點和5個Slave節(jié)點。操作系統(tǒng)版本均為Ubuntu 14.04.3-Server-amd64，Hadoop版本為2.6.0，Spark版本為1.4.0，Java開發(fā)包版本為jdk1.7.0_79，程序開發(fā)工具為Eclipse Mars.1 Release (4.5.1)，算法使用Java實現(xiàn)。

實驗測試數(shù)據(jù)集利用UCI數(shù)據(jù)集下的Iris(數(shù)據(jù)對象150，屬性4)、Wine(數(shù)據(jù)對象178，屬性13)及Balance Scale(數(shù)據(jù)對象625，屬性4)來驗證算法的有效性。同時將數(shù)據(jù)集Poker-hand-testing(數(shù)據(jù)對象1025010，屬性11)按照數(shù)據(jù)集的形式隨機生成大小不同的5個數(shù)據(jù)樣本，D1(100萬個樣本點)、D2(200萬個樣本點)、D3(500萬個樣本點)、D4(800萬個樣本點)、D5(1 000萬個樣本點)，來驗證算法加速比和擴展比，并與MapReduce框架下的結(jié)果進行比較。

為了測試SBTICK-means算法的整體性能，采用以下幾個評價指標(biāo)：準(zhǔn)確率、Sizeup、Scaleup以及與MapReduce框架下的運行時間比。

3.2 實驗結(jié)果及分析

為了驗證SBTICK-means算法的有效性，使用實驗平臺中的3個節(jié)點，利用UCI數(shù)據(jù)集，對K-means算法[7]、Canopy-K-means算法[4]與SBTICK-means算法的有效性(準(zhǔn)確率%)進行比較，結(jié)果如表1所示。

由表1結(jié)果可以看出，SBTICK-means算法、Canopy-K-means算法分別與K-means算法相比，在準(zhǔn)確率上都有一定的提高，說明使用Canopy算法進行預(yù)處理可以有效提高聚類的準(zhǔn)確率，同時也驗證了SBTICK-means算法的聚類有效性。

另一方面，為了驗證SBTICK-means算法的可擴展性，測試不同大小的數(shù)據(jù)集D1、D2、D3、D4、D5在不同節(jié)點數(shù)下的加速比和擴展比，實驗結(jié)果如圖2、圖3所示。

由圖2、圖3可知，該算法在處理少量數(shù)據(jù)時，隨著節(jié)點數(shù)的增加，加速比呈線性增長。但當(dāng)節(jié)點數(shù)增加到3個后，加速比曲線趨向平緩或逐漸下降，擴展比也隨之下降。這是因為當(dāng)數(shù)據(jù)集的規(guī)模較小時，隨著子節(jié)點數(shù)目的增加，集群運行時間、任務(wù)調(diào)度時間、數(shù)據(jù)通信時間的增加，降低了計算速度。而D5數(shù)據(jù)樣本的加速比基本呈線性增長，并在6個節(jié)點時達(dá)到最大值5.6，擴展比變化趨勢也較平緩，在5個節(jié)點時才稍有下降。這說明，樣本規(guī)模越大，SBTICK-means算法的處理效率越高，聚類效果越明顯。

表1 不同算法20次隨機實驗的測試結(jié)果平均值

圖2 SBTICK-means算法的加速比

圖3 SBTICK-means算法的擴展比

為進一步驗證該算法的性能優(yōu)勢以及在Spark框架的計算優(yōu)勢，利用實驗平臺中的6個節(jié)點，測試在不同大小的數(shù)據(jù)樣本下，SBTICK-means算法與Canopy-K-means算法的平均運行時間(ms)，結(jié)果如圖4所示。

由圖4可以看出，兩種算法對不同大小的數(shù)據(jù)樣本的執(zhí)行時間是不同的，SBTICK-means算法具有更短的運行時間，與Canopy-K-means算法相比平均可縮短18%，并且數(shù)據(jù)樣本越大，優(yōu)勢越明顯。原因是在迭代計算過程中引入三角不等式原理，減少了迭代計算次數(shù)，從而加快了聚類速度。

圖4 兩種算法運行時間的對比

另外還測試了在處理相同大小的數(shù)據(jù)樣本D5時，該算法分別在Spark框架和MapReduce框架下的運行時間(ms)，結(jié)果如圖5所示。

圖5 兩種框架運行時間的對比

由圖5可以看出，Spark的性能要優(yōu)于MapReduce，在6個節(jié)點時運行效率最高可提高1.261倍。這是因為Spark使用RDD進行迭代計算的特點，不需要將中間數(shù)據(jù)存在磁盤中，從而大大減少了運行時間，提高了聚類速度。

4 結(jié)束語

針對傳統(tǒng)K-means算法在處理海量數(shù)據(jù)時存在距離計算瓶頸及因迭代計算次數(shù)增加導(dǎo)致內(nèi)存不足的問題，對傳統(tǒng)K-means算法進行了改進，將其與Canopy算法、三角形不等式定理相結(jié)合，并應(yīng)用于Spark框架中，提出了一種優(yōu)化的SBTICK-means算法，提高了原算法的整體性能。實驗結(jié)果表明，該算法具有較高的聚類準(zhǔn)確率和較快的聚類速度，并且在加速比、擴展比上都有所提高，更適合應(yīng)用于大數(shù)據(jù)的聚類研究中。

[1]JainAK.Dataclustering:areview[J].ACMComputingSurveys,1999,31(3):264-323.

[2] 孫吉貴,劉 杰,趙連宇.聚類算法研究[J].軟件學(xué)報,2008,19(1):48-61.

[3] 張石磊,武 裝.一種基于Hadoop云計算平臺的聚類算法優(yōu)化的研究[J].計算機科學(xué),2012,39(S2):115-118.

[4] 衣治安,王 月.基于MapReduce的K-means并行算法及改進[J].計算機系統(tǒng)應(yīng)用,2015,24(6):188-192.

[5] 王永貴,武 超,戴 偉,等.基于MapReduce的隨機抽樣K-means算法[J].計算機工程與應(yīng)用,2016,52(8):74-79.

[6] 毛典輝.基于MapReduce的Canopy-Kmeans改進算法[J].計算機工程與應(yīng)用,2012,48(27):22-26.

[7] 梁 彥.基于分布式平臺Spark和YARN的數(shù)據(jù)挖掘算法的并行化研究[D].廣州:中山大學(xué),2014.

[8] 張順龍,庫 濤,周 浩.針對多聚類中心大數(shù)據(jù)集的加速K-means聚類算法[J].計算機應(yīng)用研究,2016,33(2):413-416.

[9]ElkanC.Usingthetriangleinequalitytoacceleratek-means[C]//ICML.[s.l.]:[s.n.],2003:147-153.

[10] 孟海東,任敬佩.基于云計算平臺的聚類算法[J].計算機工程與設(shè)計,2015,36(11):2990-2994.

[11]MengX,BradleyJ,YuvazB,etal.MLlib:machinelearninginapachespark[J].JMLR,2016,17(34):1-7.

[12]ArmbrustM,DasT,DavidsonA,etal.Scalingsparkintherealworld:performanceandusability[J].ProceedingsoftheVLDBEndowment,2015,8(12):1840-1843.

[13]ArmbrustM,XinRS,LianC,etal.Sparksql:relationaldataprocessinginspark[C]//Proceedingsofthe2015ACMSIGMODinternationalconferenceonmanagementofdata.[s.l.]:ACM,2015:1383-1394.

[14] 廖 彬，于 炯，張 陶,等.基于分布式文件系統(tǒng)HDFS的節(jié)能算法[J].計算機學(xué)報，2013，36(5)：1047-1064.

[15]WuJ,HongB.Multicast-basedreplicationforHadoopHDFS[C]//IEEE/ACISinternationalconferenceonsoftwareengineering,artificialintelligence,networkingandparallel/distributedcomputing.[s.l.]:IEEE,2015:1-6.

勘 誤

我刊于2017年第27卷第4期刊載張明輝的論文《基于FCM的無檢測器交叉口短時交通流量預(yù)測》因作者人數(shù)有誤，現(xiàn)更正為：張明輝，宗智嵩，王夏黎。特此更正。

Parallel Clustering Algorithm with Spark Framework

LI Lin-lin1,NI Jian-cheng2,CAO Bo1,YU Ping-ping1,YAO Bin-xiu1

(1.College of Information Science and Engineering,Qufu Normal University,Rizhao 276826,China;2.College of Software,Qufu Normal University,Qufu 273100,China)

In view of the issues that when processing massive data,traditionalK-meansalgorithmhasthebottlenecksofdistancecomputationandcausesmemoryoverflowduetoincreaseofiterativecalculation,theSBTICK-means(SparkBasedTriangleInequalityCanopy-K-means)parallelclusteringalgorithmbasedonSparkframeworkhasbeenproposed.InordertobettersolvetheproblemofblindnessandrandomnessaboutKvalue’sselection,initialclustercentersandKvaluehavebeenpreprocessedbyCanopy.DuringK-meansiterativecalculation,redundantcomputationhasbeenreducedandclusteringspeedhasbeenacceleratedbythetriangleinequalitytheorem.CombinedwithSparkframeworkandmadefulluseofmemorycomputingadvantages,thedataprocessingspeedhasbeenimprovedandtheoverallrunningtimeofthisalgorithmhasbeendecreased.Experimentalresultsshowthattheproposedalgorithmhasimprovedclusteringefficiencywhileensuringtheaccuracyrate,andthatatthesametime,thesize-uprate,scale-uprateandoperatingspeedhavebeenimprovedcomparedwiththetraditionalK-meansalgorithmandCanopy-K-meansandthisalgorithmbasedonMapReduceframework.Thereforeitcanbemoresuitableforclusteringresearchofmassivedata.

K-means;Spark;bigdata;Hadoop;MapReduce

2016-06-29

2016-10-12 網(wǎng)絡(luò)出版時間：2017-03-07

國家自然科學(xué)基金(青年基金)(61402258);山東省本科高校教學(xué)改革研究項目(2015M102);校級教學(xué)改革研究項目(jg05021*)

李淋淋(1991-)，女，碩士研究生，CCF會員，研究方向為并行與分布式計算、數(shù)據(jù)挖掘；倪建成，博士，教授，CCF會員，研究方向為分布式計算、機器學(xué)習(xí)。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170307.0922.096.html

TP

A

1673-629X(2017)05-0097-05

10.3969/j.issn.1673-629X.2017.05.021