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

宋國(guó)興，張清偉，鄭明釗，杜飛，陳彬

（中國(guó)移動(dòng)通信集團(tuán)設(shè)計(jì)院有限公司山東分公司（華北二區(qū)），濟(jì)南250101）

0 引言

在“大網(wǎng)絡(luò)”、“新基建”等政策背景下[1]，網(wǎng)絡(luò)化信息時(shí)代逐步進(jìn)入大數(shù)據(jù)的爆發(fā)期，海量數(shù)據(jù)隨著人們?nèi)粘＝涣?、?gòu)物、學(xué)習(xí)等生活的方方面面爆炸式產(chǎn)生，這也就對(duì)從海量數(shù)據(jù)中獲取實(shí)時(shí)性信息提出了挑戰(zhàn)[2]。傳統(tǒng)機(jī)器學(xué)習(xí)算法已經(jīng)無(wú)法滿足從動(dòng)態(tài)數(shù)據(jù)中快速獲取實(shí)時(shí)信息的要求，特別是聚類等被廣泛應(yīng)用的算法，需要進(jìn)行實(shí)時(shí)性優(yōu)化改進(jìn)。

K-means聚類算法是一種經(jīng)典的數(shù)據(jù)挖掘聚類算法[3]，算法過(guò)程主要依賴數(shù)據(jù)點(diǎn)分配階段和聚類中心點(diǎn)更新階段兩個(gè)步驟迭代進(jìn)行。但是對(duì)于實(shí)時(shí)數(shù)據(jù)進(jìn)行聚類時(shí)，由于輸入的數(shù)據(jù)是以實(shí)時(shí)數(shù)據(jù)流的形式[4]，隨著時(shí)間的推移，數(shù)據(jù)量會(huì)不斷增加，導(dǎo)致傳統(tǒng)K-means算法無(wú)法快速聚類。本文重點(diǎn)對(duì)傳統(tǒng)K-means聚類算法采用Spark Streaming框架進(jìn)行并行優(yōu)化之后高效地完成對(duì)流式數(shù)據(jù)分析處理進(jìn)行研究。

1 優(yōu)化改進(jìn)的K-means算法

基于Spark平臺(tái)的K-means聚類，對(duì)輸入的樣本數(shù)據(jù)進(jìn)行RDD數(shù)據(jù)塊劃分，然后將數(shù)據(jù)塊分配到不同的集群節(jié)點(diǎn)。集群節(jié)點(diǎn)通過(guò)SparkContext的廣播函數(shù)[5]共享聚類中心，map函數(shù)進(jìn)行數(shù)據(jù)點(diǎn)分配，reduce函數(shù)完成聚類中心點(diǎn)的更新。在平臺(tái)并行化處理大數(shù)據(jù)量時(shí)，使用KD樹(shù)對(duì)迭代過(guò)程進(jìn)行二次優(yōu)化，避免在數(shù)據(jù)點(diǎn)分配過(guò)程中與所有的聚類中心進(jìn)行比較。

對(duì)數(shù)據(jù)點(diǎn)分配階段和聚類中心點(diǎn)更新階段的并行化處理如圖1。

圖1聚類模型并行優(yōu)化

圖1 聚類并行優(yōu)化對(duì)應(yīng)的算法偽代碼如下：

輸入：原始數(shù)據(jù)集，初始化數(shù)據(jù)聚類中心個(gè)數(shù)K輸出：聚類模型

步驟：

1、輸入原始數(shù)據(jù)集，將數(shù)據(jù)分成RDD數(shù)據(jù)塊并分發(fā)到集群節(jié)點(diǎn)

2、基于隨機(jī)方法或者Canopy等方法初始化聚類中心個(gè)數(shù)K

3、迭代運(yùn)行步驟4至步驟9，直到模型收斂

4、把聚類中心廣播分發(fā)到集群節(jié)點(diǎn)

5、針對(duì)每個(gè)RDD數(shù)據(jù)塊，計(jì)算每個(gè)數(shù)據(jù)點(diǎn)x i到最近聚類中心u j對(duì)應(yīng)的距離：

2 算法衡量指標(biāo)

本文對(duì)K-means聚類算法[7]改進(jìn)優(yōu)化的目的在于使其適應(yīng)實(shí)時(shí)數(shù)據(jù)聚類的要求，所以本文把收斂性、每輪迭代所需要的時(shí)間和吞吐量等方面作為衡量指標(biāo)，著重從優(yōu)化改進(jìn)后算法的收斂準(zhǔn)確率和時(shí)間效率兩個(gè)方面進(jìn)行算法的評(píng)價(jià)。前者主要考察算法優(yōu)化的合理性、并行設(shè)計(jì)的科學(xué)性、迭代收斂的準(zhǔn)確性[8]，后者主要驗(yàn)證并行化之后效率的提升情況。

本文從以下幾個(gè)具體的指標(biāo)進(jìn)行平臺(tái)性能的綜合評(píng)估。

平均運(yùn)行時(shí)間：在算法參數(shù)收斂之前，需要對(duì)原始數(shù)據(jù)進(jìn)行訓(xùn)練、迭代，整個(gè)過(guò)程需要消耗大量的運(yùn)行時(shí)間，把每一輪迭代的平均運(yùn)行時(shí)間作為基本衡量指標(biāo)，來(lái)衡量算法收斂的時(shí)間效率。

吞吐量：?jiǎn)挝粫r(shí)間內(nèi)系統(tǒng)所處理的任務(wù)總數(shù)。在通常情況下，隨著任務(wù)數(shù)量的增加，平臺(tái)中排隊(duì)等待的任務(wù)數(shù)會(huì)增加，這將導(dǎo)致系統(tǒng)的任務(wù)處理能力不會(huì)隨著輸入的任務(wù)數(shù)的增加而提高。本文設(shè)計(jì)的平臺(tái)采用了Spark Streaming流式處理的方式[9]，由于流式處理的邏輯通常比較簡(jiǎn)單，實(shí)時(shí)性處理能力優(yōu)越，會(huì)在相當(dāng)大的程度上彌補(bǔ)這個(gè)不足。

收斂準(zhǔn)確率：算法在迭代過(guò)程中達(dá)到設(shè)定的迭代次數(shù)閾值時(shí)，被準(zhǔn)確聚類的數(shù)據(jù)點(diǎn)個(gè)數(shù)占數(shù)據(jù)點(diǎn)總個(gè)數(shù)的比值[10]，用來(lái)衡量算法收斂之后得到的聚類結(jié)果的準(zhǔn)確性。

3 算法性能試驗(yàn)驗(yàn)證

3.1 試驗(yàn)環(huán)境

本文搭建包含6個(gè)節(jié)點(diǎn)的Spark集群進(jìn)行試驗(yàn)，節(jié)點(diǎn)具體配置如表1和表2。

表1 節(jié)點(diǎn)硬件配置

表2 節(jié)點(diǎn)參數(shù)配置

集群環(huán)境安裝Hadoop 2.6版本，Spark 2.4版本，JDK 1.8版本。Hadoop并行化最大map數(shù)為16，最大reduce數(shù)為2，每個(gè)任務(wù)可以使用4G內(nèi)存，Spark每個(gè)節(jié)點(diǎn)的計(jì)算內(nèi)存為20G，用于數(shù)據(jù)計(jì)算和RDD數(shù)據(jù)塊間的調(diào)度和關(guān)系依賴加載。

3.2 試驗(yàn)結(jié)果對(duì)比

實(shí)驗(yàn)從平均運(yùn)行時(shí)間、吞吐量和收斂準(zhǔn)確率三個(gè)指標(biāo)，對(duì)單機(jī)版的K-means聚類算法、Spark平臺(tái)集成的算法和Spark Streaming優(yōu)化后的算法三種狀況下進(jìn)行對(duì)比。實(shí)驗(yàn)數(shù)據(jù)為某購(gòu)物平臺(tái)的真實(shí)數(shù)據(jù)，選取的數(shù)據(jù)對(duì)（樣本數(shù)，特征數(shù)）為（1w,100）、（1w,1k）、（10w,100）、（10w,1k）、（100w,100）、（100w,1k）。

（1）平均運(yùn)行時(shí)間

從待測(cè)數(shù)據(jù)輸入測(cè)試環(huán)境到得到收斂后的算法模型為一個(gè)運(yùn)行周期，每種算法用六組數(shù)據(jù)進(jìn)行獨(dú)立測(cè)試，測(cè)試結(jié)果如圖2。

圖2 平均運(yùn)行時(shí)間對(duì)比

由圖2測(cè)試結(jié)果可以看出，在數(shù)據(jù)量較小時(shí)單機(jī)模式和SparkStreaming模式都能取得較好的運(yùn)行速度，SparkStreaming模式和Spark模式需要不斷的進(jìn)行節(jié)點(diǎn)間的信息傳輸和調(diào)度，但是SparkStreaming模式通過(guò)流式處理和并行優(yōu)化，降低了節(jié)點(diǎn)間數(shù)據(jù)傳輸帶來(lái)的時(shí)間消耗，而Spark模式由于需要節(jié)點(diǎn)間數(shù)據(jù)傳輸，所以會(huì)比單機(jī)模式消耗時(shí)間多。隨著數(shù)據(jù)量和特征數(shù)量的增多，單機(jī)模式會(huì)越來(lái)越無(wú)法承受大數(shù)據(jù)量的迭代計(jì)算，時(shí)間消耗會(huì)成倍增加，SparkStreaming模式和Spark模式由于是采用分布式模式，處理大數(shù)據(jù)量數(shù)據(jù)較單機(jī)模式有明顯優(yōu)勢(shì)，SparkStreaming模式的優(yōu)化處理，即便是數(shù)據(jù)量增加，所消耗的時(shí)間不會(huì)增加太多。

（2）吞吐量

本實(shí)驗(yàn)選取10秒內(nèi)在三種環(huán)境下處理的任務(wù)數(shù)（即迭代次數(shù)，并保留整數(shù)位）進(jìn)行對(duì)比。為了盡可能模擬現(xiàn)實(shí)場(chǎng)景下的實(shí)時(shí)處理，測(cè)試數(shù)據(jù)以數(shù)據(jù)流的方式輸入到測(cè)試系統(tǒng)，并且數(shù)據(jù)流以并發(fā)的形式從多個(gè)節(jié)點(diǎn)同時(shí)輸入。在實(shí)驗(yàn)中，數(shù)據(jù)流生成間隔設(shè)定為0.5秒，滑動(dòng)窗口為2秒。測(cè)試結(jié)果如圖3。

由圖3實(shí)驗(yàn)結(jié)果可以看出，三種處理模式的吞吐量都會(huì)隨著數(shù)據(jù)量的增多而降低，但是由于本文的改進(jìn)算法同時(shí)采用Spark的流數(shù)據(jù)框架和滑動(dòng)窗口策略，在大數(shù)據(jù)量的聚類狀態(tài)下仍然能保持較高的效率。

圖3 吞吐量對(duì)比

（3）收斂準(zhǔn)確性對(duì)比

本實(shí)驗(yàn)的聚類算法屬于無(wú)監(jiān)督的機(jī)器學(xué)習(xí)范疇，無(wú)法用某一個(gè)標(biāo)準(zhǔn)聚類結(jié)果作為參考，所以，在驗(yàn)證收斂準(zhǔn)確性時(shí)，SparkStreaming模式和Spark模式的聚類結(jié)果與單機(jī)版模式做比較，用三者的偏差作為衡量標(biāo)準(zhǔn)。具體衡量指標(biāo)為：同一聚類中包含的數(shù)據(jù)點(diǎn)個(gè)數(shù)和單機(jī)版模式下對(duì)應(yīng)聚類中數(shù)據(jù)點(diǎn)個(gè)數(shù)的差值與單機(jī)版模式對(duì)應(yīng)聚類中數(shù)據(jù)點(diǎn)總個(gè)數(shù)的比值。實(shí)驗(yàn)結(jié)果如圖4。

圖4 收斂準(zhǔn)確率對(duì)比

由圖4實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，在六組數(shù)據(jù)上的測(cè)試結(jié)果偏差很小，說(shuō)明基于Spark Streaming的并行K-means改進(jìn)算法在聚類準(zhǔn)確性方面可以滿足要求。

綜上實(shí)驗(yàn)結(jié)果，基于Spark Streaming的并行K-means改進(jìn)算法在聚類準(zhǔn)確性較高的情況下，在收斂速率方面又明顯的優(yōu)勢(shì)，可以滿足實(shí)時(shí)性數(shù)據(jù)聚類的要求。

4 結(jié)語(yǔ)

為了解決經(jīng)典的K-means聚類算法無(wú)法滿足大數(shù)據(jù)背景下對(duì)實(shí)時(shí)聚類的要求，本文基于Spark Streaming流數(shù)據(jù)處理框架對(duì)K-means聚類算法進(jìn)行改進(jìn)，通過(guò)SparkContext的廣播函數(shù)共享聚類中心、KD樹(shù)對(duì)迭代過(guò)程進(jìn)行二次優(yōu)化、以滑動(dòng)窗口作為數(shù)據(jù)的輸入單元?jiǎng)討B(tài)調(diào)整批量數(shù)據(jù)的輸入時(shí)間間隔和聚類中心的更新頻率等優(yōu)化策略，使得改進(jìn)算法在滿足聚類準(zhǔn)確性的同時(shí)能夠很好地處理實(shí)時(shí)數(shù)據(jù)。后續(xù)工作將繼續(xù)針對(duì)不同的應(yīng)用場(chǎng)景對(duì)改進(jìn)算法進(jìn)行定向優(yōu)化。