基于Spark的K-means快速聚類算法的優(yōu)化

王全民，胡德程

(北京工業(yè)大學(xué)信息學(xué)部，北京100022)

1 引言

K-means[1]算法(K-means algorithm)是一種無監(jiān)督聚類算法，主要是解決無標(biāo)簽數(shù)據(jù)聚類問題。如信息檢索、文本挖掘等各個領(lǐng)域都有廣泛應(yīng)用。隨著信息時代的到來，各領(lǐng)域的數(shù)據(jù)在速度、體積以及多樣性都急劇上升，普通的數(shù)據(jù)規(guī)模達到了TB級甚至PB級。在海量數(shù)據(jù)背景下，對K-means算法性能要求也越來越高，故傳統(tǒng)K-means算法越來越難適應(yīng)海量數(shù)據(jù)。針對標(biāo)準K-means算法依賴初始K個質(zhì)心點，若選擇的初始中心點不恰當(dāng)以及更新中心點的冗余計算，往往會得到不理想的全局最優(yōu)中心點和執(zhí)行效率。

如何優(yōu)化初始聚類中心點[2]的選擇，提升K均值法的收斂速度和準確率是本文的主要研究方向。文獻[3]通過將粒子群優(yōu)化PSO與K均值法結(jié)合，采用PSO來得到初始聚類質(zhì)心，以此提高K均值法的全局搜索能力。文獻[4]利用近鄰圖來完成K-means算法的初始中心點的選擇，避免隨機選擇初始點而帶來的局部最優(yōu)解問題。文獻[5]利用hash抽樣函數(shù)和MapReduce[6]計算框架來處理數(shù)據(jù)聚類，提高K均值算法的執(zhí)行效率。本文使用最大距離算法優(yōu)化初始中心點的選取，采用形態(tài)學(xué)相似距離提高準確率，網(wǎng)格空間減少冗余計算。

本文在Spark[7]并行計算框架下對K-means算法進行優(yōu)化和實現(xiàn)，提高對海量數(shù)據(jù)的處理能力。采用的數(shù)據(jù)集是UCI網(wǎng)站上的glass，abalone，Aggregation，實現(xiàn)SMGK-means算法來驗證其準確性，有效性以及加速性。

2 相關(guān)研究

2.1 Spark計算框架

本文選擇Spark實現(xiàn)SMGK-means算法而非MapReduce即MR[8]，主要是Spark擴展了MR計算模型，具有MR的優(yōu)點；與MR相比SparkJob[9]計算的中間結(jié)果RDD[10]可保存在節(jié)點內(nèi)存中，無需從HDFS或者磁盤上讀取數(shù)據(jù)，故Spark能很好地適用于迭代式的MR算法。Spark的系統(tǒng)架構(gòu)如圖1所示。

圖1 Spark并行框架結(jié)構(gòu)

Spark處理數(shù)據(jù)比MR快的原因如下。首先，Spark是基于內(nèi)存迭代式計算；其次，Spark的數(shù)據(jù)結(jié)構(gòu)是分布式數(shù)據(jù)集RDD[10](Resilient Distributed Dataset)，RDD將數(shù)據(jù)存儲在節(jié)點executor內(nèi)存中，通過劃分分區(qū)優(yōu)化數(shù)據(jù)分布。最后，Spark的DAG計算模型和惰性求值。Spark的算子操作分為兩種即Transformation和Action，調(diào)用Transformation操作時如Map，flatMap，并不會立即執(zhí)行，而在內(nèi)部記錄操作，形成DAG計算模型，當(dāng)遇到Action操作時，會立即執(zhí)行相應(yīng)的Transformation操作。Spark Job的邏輯執(zhí)行如圖2所示。

圖2 Spark Job的邏輯執(zhí)行圖

2.2 K-means算法

傳統(tǒng)K均值法是無監(jiān)督聚類算法，輸入樣本中只有特征而沒有標(biāo)簽，從待聚類的原始Dataset中隨機選取K個數(shù)據(jù)點作為初始聚類質(zhì)心，隨后按照特定的度量標(biāo)準計算非質(zhì)心點到聚類質(zhì)心的距離，進行聚類劃分。最后計算每個聚類的數(shù)據(jù)點到質(zhì)心的平均距離，并依此調(diào)整質(zhì)心，經(jīng)過多次迭代計算，每個類簇中的樣本點相似度較高，類簇間的相似度較低。

傳統(tǒng)K-means算法過程如下：

輸入：待聚類初始Dataset，聚類中心的初始質(zhì)心個數(shù)K。

輸出：聚類結(jié)果即K個類簇。

具體的算法步驟：

步驟1：從待聚類的初始Dataset中隨機選擇K個樣本點作為初始聚類質(zhì)心。

步驟2：計算非中心點到聚類中心的距離，將其分配到與自己最近的中心點。

步驟3：當(dāng)所有點都歸類完畢后，調(diào)整中心點：把中心點重新設(shè)置成該類別中所有數(shù)據(jù)點的中心位置，將每個類簇中的距離平均值作為新的聚類質(zhì)心。

步驟4：根據(jù)每個非中心點到質(zhì)心點的相似度(這里指距離越短相似度越大)對數(shù)據(jù)集進行重新聚類。

步驟5：重復(fù)步驟3，步驟4，直到類簇不再變化，或者達到設(shè)定的迭代次數(shù)即可結(jié)束算法。

傳統(tǒng)K-means算法的主要缺點：時間復(fù)雜度為O(nkm)，其中n為原始數(shù)據(jù)集的個數(shù)，K為聚類中心個數(shù)，m為迭代次數(shù)。傳統(tǒng)K-means算法時間復(fù)雜度高，隨迭代次數(shù)m、類簇數(shù)k值、初始數(shù)據(jù)集的增加而增大，因此傳統(tǒng)K-means算法在處理海量數(shù)據(jù)時綜合性能較低。另外K均值算法過于依賴初始聚類中心點的選取，選擇不同的初始聚類中心點，其最后的聚類結(jié)果也相差較大。

2.3 K-means++算法

因為標(biāo)準的K-means分類結(jié)果會受到初始質(zhì)心點的選取而產(chǎn)生差異，因此提出對傳統(tǒng)K-means算法進行優(yōu)化即K-means++算法，K-means++聚類算法主要是對初始質(zhì)心點的選取進行改進，主要優(yōu)化方法是初始的聚類質(zhì)心之間的距離要盡量大，這樣可以保證樣本點會盡可能的分配到聚類中心中。

K-means++算法雖然能增加聚類準確率，但是沒有減少冗余計算，而且在選取初始中心點增加額外計算以及第n個聚類質(zhì)心的選擇依賴于前n個聚類質(zhì)心。

3 SMGK-means算法及在Spark上的并行化實現(xiàn)

3.1 改進K-means算法措施

通過形態(tài)學(xué)相似距離，最大距離距離準則以及建立聚類中心與數(shù)據(jù)點的位置關(guān)系來優(yōu)化標(biāo)準K-means算法。

3.1.1 形態(tài)學(xué)相似距離MSD

相似度測量標(biāo)準一般由明可夫斯基距離推導(dǎo)出，主要應(yīng)用有歐氏距離，曼哈頓距離。

定義1：明可夫斯基距離

(1)

其中(1)式中：Yqi為向量q的第i個屬性值，Xji是向量j的第i個屬性值，m為向量維度，|Xji-Yqi|表示點與點再屬性i上的距離。當(dāng)p=2時，表示歐氏距離；p=1時表示曼哈頓距離。

定義2：形態(tài)學(xué)相似距離MSD(morphological similarity distance)

DMSD=(2-ASD/SAD)×ED

(2)

(3)

其中(2)式中：SAD表示曼哈頓距離，ED表示歐氏距離。(3)式表示兩個向量屬性差值之和的絕對值，Xji是向量j的第i個屬性值，Yqi為向量q的第i個屬性值m表示特征維度。表1表示了向量間的距離計算示例。

表1 向量間的距離計算

可以看出，若SAD/ASD=1，即ASD距離等于曼哈頓距離時，MSD距離就是歐式距離。

3.1.2 最大距離準則選擇初始質(zhì)心點

Max-distinece算法是由最大最小距離算法改進而來，根據(jù)其最大距離原則選取初始的聚類質(zhì)心。

算法過程如下：

步驟1：從數(shù)據(jù)集中任意選取靠近邊界點(不是邊界點)，作為聚類質(zhì)心C1，同時記C為聚類中心集合

步驟2：選擇聚類質(zhì)心C1最遠的數(shù)據(jù)點作為第2個聚類質(zhì)心C2；

步驟3：計算其它數(shù)據(jù)點與C1，C2之間的距離，并且計算出它們中的最小值，即式(1)、(2)

dxy=‖nx-ny‖，y=1，2

(4)

dx=min[dx1，dx2]，x=1，2，…n

(5)

步驟4：如果(θ為規(guī)定的參數(shù))

dl=maxx[min[dx1，dx2] ]>θ*‖n1-n2‖

(6)

則相應(yīng)的樣本nl作為第3個聚類中心C3，然后繼續(xù)判斷next聚類質(zhì)心；

步驟5：如果存在k(k！=K)個聚類中心，計算各個樣本點到聚類質(zhì)心的距離dxy，并計算出：

dl=maxx[min[dxy，dxz] ]>θ*‖ny-nz‖

(7)

其中y！=z且y，z∈C

步驟6：已經(jīng)求出K個初始聚類中心點，將其保存記為C

3.1.3 數(shù)據(jù)集的空間位置信息減少冗余計算

為減少K-means算法冗余計算量，引入數(shù)據(jù)點與聚類中心的空間位置關(guān)系[11]，基本做法是，對于初始數(shù)據(jù)集中的任意點，若能知道它與K個類簇質(zhì)心的空間位置關(guān)系，就可能判斷出離它最近的聚類質(zhì)心是哪一個，這樣就無需執(zhí)行k次計算，只需將數(shù)據(jù)點分配到相應(yīng)的類簇中去。

如何建立數(shù)據(jù)集與聚類中心的空間位置信息，以三維數(shù)據(jù)為例，對于一個在空間直角坐標(biāo)系任意數(shù)據(jù)點s(x，y，z)，假設(shè)x所在維度最大值為maxx，最小值為minx，網(wǎng)格在這一維上所劃的分段數(shù)為xNum。假設(shè)y所在維度最大值為maxy，最小值為miny，網(wǎng)格在這一維上所劃的分段數(shù)為yNum。假設(shè)z所在維度最大值為maxz，最小值為minz，網(wǎng)格在這一維上所劃的分段數(shù)為zNum。根據(jù)數(shù)據(jù)集中點的坐標(biāo)，可以按照式(8)，(9)，(10)快速定位點s的網(wǎng)格位置(x′，y′，z′)

(8)

(9)

(10)

其中α為正的小數(shù)。

由上述數(shù)據(jù)點s所在網(wǎng)格與k個聚類質(zhì)心的關(guān)系即可確定點s與類簇的關(guān)系，即點s所可能歸屬的聚類質(zhì)心有哪些。那么就可以有效地減少點s與聚類質(zhì)心之間的計算量。

3.2 肘部法則確定K值

對于肘部法則[12]確定類簇個數(shù)K而言，其中誤差平方和SSE和距離度量標(biāo)準如下

(11)

其中x，y表示不同的兩個樣本，n表示樣本的維度即特征數(shù)量

(12)

針對大規(guī)模數(shù)據(jù)可以利用肘部法則來確定類簇數(shù)K。肘部法則的計算思想是代價函數(shù)，代價函數(shù)是取類簇數(shù)為k時所求的SSE，若類簇內(nèi)部的數(shù)據(jù)點之間越緊湊則SSE越小，反之，若內(nèi)部的數(shù)據(jù)點之間越分散則SSE越大。在選擇類簇個數(shù)而言，肘部法則會把不同k值聚類所得到的SSE畫成關(guān)系圖。隨著k值的增大，SSE值就會越來越小，每個類簇中所包含的樣本數(shù)會減少，數(shù)據(jù)點離其聚類質(zhì)心會更近。但是，隨著k值的增加，誤差平方和SSE值下降的幅度就會變得緩慢。在k值上升過程中，SSE下降幅度最快位置所對應(yīng)的值就是肘部。

3.3 算法改進步驟

在上述2.2節(jié)和2.3節(jié)中分析了K均值法和K-means++的主要缺點，下面對如何選擇初始中心點，減少冗余計算量以及并行化提出了解決辦法。首先此文中的測量距離據(jù)使用形態(tài)學(xué)相似距離MSD。優(yōu)化算法的步驟如下：設(shè)原始數(shù)據(jù)集Dataset={x1，x2，x3，…，xn}，并且xi屬于Rd，其中n為原始數(shù)據(jù)集的個數(shù)，xi表示為d維向量。先預(yù)設(shè)K值范圍如[n1，n2]，依此取n1與n2之間的整數(shù)K；對于所取的每一個K值，首先根據(jù)Max-distance距離算法選擇K個初始中心點；然后利用數(shù)據(jù)點與K個類簇中心的位置關(guān)系將數(shù)據(jù)點歸屬到與其最近的中心中，其次更新K個類簇中心和網(wǎng)格空間信息，重復(fù)此過程，直到簇類中心不再變化或者達到規(guī)定的迭代次數(shù)；最后處理得到對應(yīng)K值的SSE，然后在直角坐標(biāo)系中繪制K-SSE關(guān)系圖，此圖類似于手肘的形狀，此時這個拐點所對應(yīng)的k值就是數(shù)據(jù)集的實際聚類數(shù)即最優(yōu)K值。

3.4 基于Spark的SMGK-means算法的并行實現(xiàn)

為了能有效地提高K-means算法的并行計算能力，本文提出了基于Spark的SMGK-means算法，主要是圍繞ShuffleMapTask和ResultTask兩個任務(wù)進行的。算法流程圖如圖3所示。

圖3 基于Spark的SMGK-means算法

在每次迭代計算過程中，先對每個RDD分區(qū)進行mapPartitions操作，mapPartitions與map操作不同，是針對RDD中每個分區(qū)的迭代器，每次處理分區(qū)中的所有數(shù)據(jù)，且執(zhí)行一次，提高了計算效率。之后對數(shù)據(jù)點進行聚類。通過數(shù)據(jù)坐標(biāo)得到的對應(yīng)網(wǎng)格，利用類簇和網(wǎng)格的關(guān)系確定數(shù)據(jù)點可能歸屬的類簇，最后從可能的聚類質(zhì)心中查找最近的類簇，以此來減少冗余的計算。將所有點分配完成后，再將不同executor中的簇類中心進行reduceByKey操作匯總，得到新的K個聚類質(zhì)心，同時對網(wǎng)格和類簇的空間關(guān)系進行更新。迭代結(jié)束后，通過肘部法則來確定最終的k值和類簇結(jié)果。

SMGK-means算法流程大致可以劃分為以下數(shù)據(jù)分區(qū)，聚合和驗證三個階段。其算法代碼如圖4所示。

圖4 程序代碼

改進策略的要點如下：先使用MSD替換傳統(tǒng)的距離度量如歐式距離，然后利用最大距離準則選擇最優(yōu)的初始中心點，提高K-means算法的全局搜索能力。其次使用網(wǎng)格結(jié)構(gòu)保存數(shù)據(jù)點與聚類中心的空間位置關(guān)系，得到數(shù)據(jù)點所歸屬的可能類簇。最后利用Spark框架中的廣播變量，把K個中心點所組成的集合廣播到集群中每個節(jié)點的executor進程中，然后進行相應(yīng)的算子操作，從而減少數(shù)據(jù)點在節(jié)點中的移動次數(shù)。通過以上改進策略能很好得提高算法的效率和性能。

3.5 每個K值下SMGK-means算法時間復(fù)雜度分析

改進的算法時間復(fù)雜度得到明顯的降低，如果合理的選擇網(wǎng)格劃分寬度，能在很大程度上保證絕大多數(shù)網(wǎng)格都只會屬于一個聚類中心，只有少量網(wǎng)格的可能歸屬類簇為兩個及以上。因此對于大多數(shù)的數(shù)據(jù)點都只需執(zhí)行一次距離計算，而非K次。若排除選取初始聚類質(zhì)心所消耗的時間，SMGK-means算法的時間復(fù)雜度為O(nm)，其中n為數(shù)據(jù)點個數(shù)，m為迭代次數(shù)。

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

本文基于Spark分布式集群實現(xiàn)SMGK-means算法，實驗環(huán)境由五臺虛擬機組成，其中包括一臺master主節(jié)點，負責(zé)driver程序的運行和管理，剩下四臺work從節(jié)點作為執(zhí)行節(jié)點。

硬件配置：每臺虛擬機CPU雙核1.8GHz，內(nèi)存2GB，磁盤容量20GB。操作系統(tǒng)是64位的Ubuntu16.04。

軟件配置：每臺虛擬機上裝有jdk1.8.0＿191，scala-2.11，hadoop-2.9.1，spark-2.4.3。采用具有面向?qū)ο箫L(fēng)格和函數(shù)式編程特性的Scala語言，同時為驗證SMGK-means算法的有效性，采用Spark ML[13]中標(biāo)準K-means算法、K-means++算法以及文獻[14]中算法作為對比試驗。測試數(shù)據(jù)集為UCI數(shù)據(jù)集庫中的abalone，Aggregation，glass三種不同量級的數(shù)據(jù)樣本。為了方便驗證實驗，對相關(guān)數(shù)據(jù)集進行預(yù)處理(刪除和增加相應(yīng)的數(shù)據(jù))，處理后數(shù)據(jù)集如表2所示。

表2 數(shù)據(jù)集

針對上述三種數(shù)據(jù)集，修改數(shù)據(jù)集中每條記錄的聚類中心，然后提取其中的特征另存為train.txt上傳到HDFS上，隨后模型讀取的數(shù)據(jù)就是HDFS上的train.txt。實驗結(jié)束所保存的數(shù)據(jù)也在HDFS上。

1)算法運行時間比較。本文利用執(zhí)行時間衡量SMGK-means算法執(zhí)行效率。圖5是上述四種算法在不同數(shù)據(jù)集的執(zhí)行時間，可以看到SMGK-means算法比另外三種算法減少了聚類時間。因為SMGK-means算法采用網(wǎng)格表示數(shù)據(jù)點與聚類質(zhì)心的位置關(guān)系，降低聚類計算的次數(shù)，提升了收斂速度；同時利用spark中broadcast將每次更新的中心點廣播到各個執(zhí)行節(jié)點中，將作業(yè)粒度轉(zhuǎn)變成節(jié)點粒度，執(zhí)行節(jié)點每次從本地內(nèi)存中讀取聚類中心，節(jié)省執(zhí)行節(jié)點間的通信開銷。圖6比較并行環(huán)境下不同數(shù)據(jù)集在不同數(shù)量節(jié)點上使用SMGK-means算法的聚類時間，體現(xiàn)出隨節(jié)點worker的增加，SMGK-means算法的運行時間逐漸減少，最后趨于平緩。平緩的原因是由于worker間的通信開銷抵消了并行化帶來的增益。

圖5 4個節(jié)點下各算法的運行時間

圖6 不同節(jié)點個數(shù)SMGK-means算法所消耗的時間

2)準確率對比。算法準確率指類簇劃分正確記錄的個數(shù)與數(shù)據(jù)集中總記錄個數(shù)的比值。表3給出三種不同的數(shù)據(jù)集在五個節(jié)點下，SMGK-means算法與K-means、K-means++以及文獻14算法的準確率。由表3可知本文的SMGK-means算法相比于其它三種算法準確率有顯著的提高。因為SMGK-means算法利用最大距離算法、網(wǎng)格空間結(jié)構(gòu)優(yōu)化了標(biāo)準K-means算法，提高了全局搜索能力。

表3 SMGK-means與其它三種算法的準確率

3)加速比的對比。算法加速比[15]是衡量程序性能、并行性能的重要指標(biāo)。其定義是同一個job在并行中與串行中執(zhí)行時間比值的倒數(shù)，計算公式為Rate=Js/Jp，其中Js為單機下的運行時間，Jp為分布式集群下執(zhí)行時間，Rate越大表示算法在單機環(huán)境下執(zhí)行時間越大，在分布式集群下運行時間越小。為驗證SMGK-means算法并行性能，實驗依然是基于上述三種不同量級的數(shù)據(jù)集，圖6給出三種不同數(shù)據(jù)集在不同節(jié)點個數(shù)下的運行時間。得到SMGK-means算法加速比如圖7所示。從圖7橫向比較得到SMGK-means算法的加速比隨執(zhí)行節(jié)點個數(shù)增加而增加。但隨著節(jié)點個數(shù)的增加，其加速比趨于平緩，其原因是節(jié)點之間的通信開銷。縱向比較得在相同節(jié)點個數(shù)下，隨記錄個數(shù)的增加，其加速比也隨之增大。

圖7 基于SMGK-means的加速比

4)手肘法確定K值。上述1)2)3)的對比實驗結(jié)果均是在K最優(yōu)情況下進行的，而對于K值未知的數(shù)據(jù)集利用手肘法確定K值。先預(yù)測最優(yōu)K值范圍，每取K值執(zhí)行一次SMGK-means算法，即可得到類簇內(nèi)的數(shù)據(jù)點到其簇類中心的距離平方和SSE，并繪制K與SSE的關(guān)系圖；然后利用肘部法則確定K值和對應(yīng)的聚類結(jié)果。圖8表示數(shù)據(jù)集alalone的K與SSE的關(guān)系圖，由圖8可知，隨K值不斷逼近真實類簇數(shù)時，SSE的下降趨勢加快，而當(dāng)設(shè)定的K值超過實際類簇數(shù)時，SSE下降態(tài)勢會趨于緩慢。K-SSE的關(guān)系圖中的拐點即為最優(yōu)的K值，與表1數(shù)據(jù)集中alalone的類簇數(shù)相同。

圖8 K與SSE的關(guān)系圖

綜合1)2)3)得到，SMGK-means算法與上述三種算法相比減少了執(zhí)行時間，且其準確率平均提高了6.73%；從加速比上分析SMGK-means算法具有良好的并行計算性能；而對于無法提前確定K值的數(shù)據(jù)集利用肘部法則也能得到正確的聚類簇數(shù)。故總體而言本文的SMGK-means算法相較于其它三種算法有了較大的提升。

5 結(jié)語

本文針對標(biāo)準K-means算法的初始中心點選擇和冗余計算等問題，提出SMGK-means算法。此算法以MSD為相似度度量標(biāo)準，利用最大距離算法優(yōu)化初始中心點選取，采用網(wǎng)格數(shù)據(jù)結(jié)構(gòu)保存數(shù)據(jù)點位置關(guān)系，減少冗余計算。通過手肘法確定最優(yōu)K值。實驗表明SMGK-means算法顯著提高了聚類的準確率，減少了執(zhí)行時間，且在分布式集群下有較高的性能。在下一步研究中，筆者準備提高數(shù)據(jù)集和集群規(guī)模，以此驗證SMMK-means算法的魯棒性。