基于Spark框架的改進(jìn)并行K-means算法研究

鄧 青， 楊 寧

(1 山西輕工職業(yè)技術(shù)學(xué)院， 太原 030006； 2 山西云時代技術(shù)有限公司， 太原 030003)

引言

隨著互聯(lián)網(wǎng)海量數(shù)據(jù)的出現(xiàn)，對處理數(shù)據(jù)能力的要求也在不斷提高。當(dāng)計算量超出單機(jī)的處理能力極限時，并行計算是一種有效的解決辦法。傳統(tǒng)的并行計算方法有HPC集群并行計算、MPI、網(wǎng)格計算等，這些技術(shù)存在價格高昂、開發(fā)過程復(fù)雜、擴(kuò)展性差等問題，無法滿足日益增長的大規(guī)模數(shù)據(jù)處理的需求[1]。

在此背景下，基于云環(huán)境下的并行計算模式也相繼興起，并吸引了學(xué)界的關(guān)注重視。當(dāng)前流行的Spark是一種基于內(nèi)存的并行計算框架，除了具備MapReduce的優(yōu)秀并行特點，Spark中間輸出結(jié)果可以保存在內(nèi)存中，能夠基礎(chǔ)性縮減在頻繁迭代過程中的批量I/O操作，提高運行效率。RDD(彈性分布數(shù)據(jù)集)作為Spark的核心機(jī)制，是一種抽象數(shù)據(jù)結(jié)構(gòu)類型[2]，在集群計算中將數(shù)據(jù)分布緩存在各節(jié)點的內(nèi)存中，減少了對磁盤的反復(fù)讀寫，大大縮短訪問延遲。

K-means是一種基于劃分的聚類算法，可將基于樣本之間的歐式距離作為劃分依據(jù)，能以快捷收斂速度優(yōu)勢處理樣本數(shù)目可觀的數(shù)據(jù)。但傳統(tǒng)的K-means算法的聚類效果很大程度上依賴于初始聚類中心的選擇[3]。

基于此，本文則設(shè)計提出了一種基于Spark框架的K-means并行算法，通過在單機(jī)環(huán)境下對比傳統(tǒng)K-means算法和改進(jìn)K-means算法的聚類性能指標(biāo)，并在單機(jī)和Spark框架下對改進(jìn)K-means算法的運行時間提供了仿真對照，實驗結(jié)果證明了改進(jìn)的并行算法的優(yōu)越性。

1 改進(jìn)K-means算法及Spark并行化

1.1 原始K-means算法原理

K-means算法，也稱為K平均[4]。算法的主要思想是選用樣本點之間的歐式距離作為判定依據(jù)，通過迭代將不同的點劃分到不同的簇中，使得評價聚類性能的準(zhǔn)則函數(shù)達(dá)到最優(yōu)，從而使生成的每個聚類內(nèi)的點相似度盡可能趨于最高，簇與簇之間獨立性較好。算法的原理流程表述如下：

(1)假定樣本集D中樣本數(shù)為n，從中任意選擇k個點作為初始聚類中心，記為Ci(i=1,2,…,k)。

(2)對剩余的每個樣本Xj，計算各樣本到k個聚類中心的歐式距離dji，數(shù)學(xué)公式如下所示：

dji=‖Xj-Ci‖

(1)

(2)

其中，Ni表示第i類中包含樣本的數(shù)目。

(3)重復(fù)執(zhí)行步驟(2)，直到準(zhǔn)則函數(shù)E不再發(fā)生明顯變化。準(zhǔn)則函數(shù)E的數(shù)學(xué)表述如式(3)所示：

(3)

1.2 改進(jìn)K-means算法

原始K-means算法初始聚類中心的選擇是隨機(jī)的，導(dǎo)致迭代過程不能獲得較好的聚類效果，甚至容易陷入局部最優(yōu)。為了盡可能減小隨機(jī)選擇初始聚類中心對聚類結(jié)果造成的影響，通過i次取樣(i次選取樣本數(shù)之和等于原始樣本數(shù))，對每次取樣樣本采用K-means算法聚類產(chǎn)生一組中心，再計算i組聚類中心的準(zhǔn)則函數(shù)值，選擇具有最小準(zhǔn)則函數(shù)的對應(yīng)聚類中心作為初始聚類中心。

為避免因適應(yīng)準(zhǔn)則函數(shù)導(dǎo)致的簇過度劃分，可以設(shè)定初始聚類中心數(shù)M大于K值，有利于展開全面搜索，防止陷于局部最優(yōu)值。K-means算法判定準(zhǔn)則函數(shù)達(dá)到收斂后得到的M個初始聚類中心，合并距離靠近的簇，直到數(shù)量減少到指定的K值為止。

1.3 改進(jìn)算法的并行化設(shè)計

利用Spark并行實現(xiàn)K-means算法，初始點選擇分為Map和Reduce兩個過程[5]。Map過程在多個datanode上并行完成，通過i次取樣，得到多個聚類中心，作為初始聚類中心的候選集。Reduce過程，合并相似性高的簇，得到K個初始聚類中心。獲得初始點后，需要進(jìn)行算法迭代，又可以分為Map和Reduce兩個階段。其中，Map階段計算所有樣本和中心點距離根據(jù)條件歸類標(biāo)記，Reduce階段對新的劃分求出均值，計算新的中心點，啟動再一次的劃分。基于Spark框架的并行過程和基于Hadoop的過程類似，但全部中心點的所有次迭代運算都在內(nèi)存中對RDD操作實現(xiàn)，無需反復(fù)讀寫磁盤，節(jié)省了I/O的時間[6]。整個過程首先從HDFS文件系統(tǒng)獲取樣本數(shù)據(jù)，并形成RDD對象，因這些數(shù)據(jù)在不同階段都會用到，故讀入后的RDD數(shù)據(jù)將保存到本地緩存。之后轉(zhuǎn)入Map操作，對本地數(shù)據(jù)進(jìn)行聚類并標(biāo)記，Reduce操作匯總、又計算各處聚類結(jié)果，得到全局聚類劃分。聚類算法的并行化執(zhí)行由Spark框架提供模式支持，自動將數(shù)據(jù)集及執(zhí)行任務(wù)分配到不同工作節(jié)點，并行推進(jìn)聚類計算的規(guī)劃實施。算法的整體設(shè)計流程如圖1所示。

圖1 并行算法流程圖Fig. 1 Parallel algorithm flow chart

2 實驗結(jié)果與分析

為了驗證改進(jìn)算法的有效性，對原始算法和改進(jìn)算法設(shè)計構(gòu)建了對比實驗。本實驗平臺的集群由1個控制節(jié)點(namenode)和5個計算節(jié)點(datanode)組成，所有節(jié)點具有相同硬件條件。即：4核CPU、8 GB內(nèi)存和80 GB硬盤，控制節(jié)點和計算節(jié)點間以千兆以太網(wǎng)互聯(lián)。Hadoop的版本為1.2.1， Spark的版本為1.2.0， JDK版本1.7.0。實驗數(shù)據(jù)使用UCI標(biāo)準(zhǔn)測試數(shù)據(jù)集中的Iris和Wine數(shù)據(jù)集[7]。Iris數(shù)據(jù)共有150個樣本，4個屬性，可分3類；Wine數(shù)據(jù)集，有13個屬性，178個樣本數(shù)據(jù)，可分3類。

實驗首先在單機(jī)上對傳統(tǒng)K-means算法和改進(jìn)的算法在聚類效果性能上進(jìn)行對比，具體結(jié)果可見表1。從結(jié)果對比發(fā)現(xiàn)，改進(jìn)算法在Iris和Wine數(shù)據(jù)集上準(zhǔn)確率方面都優(yōu)于傳統(tǒng)K-means算法。

表1 傳統(tǒng)K-means和改進(jìn)算法在2類數(shù)據(jù)集聚類效果比較Tab. 1 Comparison of clustering effect with traditional K-means and improved algorithms in two types data sets

其次，在單機(jī)和Spark環(huán)境下驗證改進(jìn)算法的執(zhí)行時間方面的差異，通過加速比來核查驗證改進(jìn)算法的并行優(yōu)越性。加速比等于串行算法運行時間與并行算法運行時間的比值。加速比越大，表明并行計算消耗的相對時間越少，并行效率和性能提升越高。實驗結(jié)果如圖2所示。

圖2 2種數(shù)據(jù)集上實驗加速比Fig. 2 Experimental speedup on two data sets

研究發(fā)現(xiàn)在樣本數(shù)據(jù)集較小的情況下，如Iris數(shù)據(jù)集，加速比較小，接近1，且隨著節(jié)點數(shù)的增加在逐漸增大；隨著樣本數(shù)據(jù)量的增加，如Wine數(shù)據(jù)集，加速比同樣也是隨節(jié)點數(shù)增加而增大，且明顯大于相同節(jié)點數(shù)的小樣本。實驗結(jié)果證明了Spark環(huán)境下的并行改進(jìn)算法具有較好的加速比，尤其適用于數(shù)據(jù)樣本量較多的情況。

3 結(jié)束語

隨著大數(shù)據(jù)時代的到來，數(shù)據(jù)種類多、數(shù)據(jù)量大、實時性要求高、數(shù)據(jù)蘊藏的價值大等特點,對聚類算法的性能要求也日趨升級。K-means算法是典型的基于原型的目標(biāo)函數(shù)聚類方法,容易陷入局部最優(yōu)的特點,不能滿足海量數(shù)據(jù)的并行化處理要求。基于內(nèi)存計算的并行計算框架Spark，繼承了Hadoop分布式存儲的優(yōu)點之外,摒棄了Hadoop抽象層次低、表達(dá)力欠缺、時延高的弊端，有效提高算法的并行處理效率，因此適合未來大規(guī)模數(shù)據(jù)挖掘及其它需要內(nèi)存實時計算數(shù)據(jù)處理課題內(nèi)容[8]。本文提出基于Spark平臺下K-means改進(jìn)算法，不僅適用于海量數(shù)據(jù)的并行化和實時處理，同時還可以有效降低對異常值的敏感性，初始化聚類中心的隨機(jī)性，在更大程度上克服了數(shù)據(jù)集劃分不均造成的數(shù)據(jù)傾斜問題。通過對標(biāo)準(zhǔn)化數(shù)據(jù)集進(jìn)行對比實驗，本算法與傳統(tǒng)K-means算法相比，在初始聚類中心及聚類收斂性方面獲得了較好的改進(jìn)，進(jìn)一步提高了聚類準(zhǔn)確度，在運行時間方面，收斂效率更高。

[1] 朱明． 數(shù)據(jù)挖掘[M]． 合肥：中國科學(xué)技術(shù)大學(xué)出版社，2002．

[2] 錢線，黃萱菁，吳立德． 初始化K-means的譜方法[J]． 自動化學(xué)報，2007，33(4)：342-346.

[3] 汪中，劉貴全，陳恩紅． 一種優(yōu)化初始中心點的K-means算法[J]． 模式識別與人工智能，2009，22(2)：299-304.

[4] QUINN M J. MPI與Open MP并行程序設(shè)計—C語言版[M]. 陳文光，武永衛(wèi)，等譯. 北京：清華大學(xué)出版社,2004.

[5] 江小平，李成華，向文，等． K-means聚類算法的MapReduce并行化實現(xiàn)[J]． 華中科技大學(xué)學(xué)報(自然科學(xué)版)，2011，39(S1):120-124.

[6] 劉鵬． 實戰(zhàn)Hadoop—開啟通向云計算的捷徑[M]． 北京：電子工業(yè)出版社，2011．

[7] 李軍華． 云計算及若干數(shù)據(jù)挖掘算法的MapReduce化研究[D]． 成都:電子科技大學(xué)，2010.

[8] 陳虹君． 基于Spark框架的聚類算法研究[J]． 電腦知識與技術(shù)，2015,11(4)：56-57,60．