基于Spark Streaming的并行K-means改進算法研究

宋國興，張清偉，鄭明釗，杜飛，陳彬

（中國移動通信集團設計院有限公司山東分公司（華北二區），濟南250101）

0 引言

在“大網絡”、“新基建”等政策背景下[1]，網絡化信息時代逐步進入大數據的爆發期，海量數據隨著人們日常交流、購物、學習等生活的方方面面爆炸式產生，這也就對從海量數據中獲取實時性信息提出了挑戰[2]。傳統機器學習算法已經無法滿足從動態數據中快速獲取實時信息的要求，特別是聚類等被廣泛應用的算法，需要進行實時性優化改進。

K-means聚類算法是一種經典的數據挖掘聚類算法[3]，算法過程主要依賴數據點分配階段和聚類中心點更新階段兩個步驟迭代進行。但是對于實時數據進行聚類時，由于輸入的數據是以實時數據流的形式[4]，隨著時間的推移，數據量會不斷增加，導致傳統K-means算法無法快速聚類。本文重點對傳統K-means聚類算法采用Spark Streaming框架進行并行優化之后高效地完成對流式數據分析處理進行研究。

1 優化改進的K-means算法

基于Spark平臺的K-means聚類，對輸入的樣本數據進行RDD數據塊劃分，然后將數據塊分配到不同的集群節點。集群節點通過SparkContext的廣播函數[5]共享聚類中心，map函數進行數據點分配，reduce函數完成聚類中心點的更新。在平臺并行化處理大數據量時，使用KD樹對迭代過程進行二次優化，避免在數據點分配過程中與所有的聚類中心進行比較。

對數據點分配階段和聚類中心點更新階段的并行化處理如圖1。

圖1聚類模型并行優化

圖1 聚類并行優化對應的算法偽代碼如下：

輸入：原始數據集，初始化數據聚類中心個數K輸出：聚類模型

步驟：

1、輸入原始數據集，將數據分成RDD數據塊并分發到集群節點

2、基于隨機方法或者Canopy等方法初始化聚類中心個數K

3、迭代運行步驟4至步驟9，直到模型收斂

4、把聚類中心廣播分發到集群節點

5、針對每個RDD數據塊，計算每個數據點x i到最近聚類中心u j對應的距離：

2 算法衡量指標

本文對K-means聚類算法[7]改進優化的目的在于使其適應實時數據聚類的要求，所以本文把收斂性、每輪迭代所需要的時間和吞吐量等方面作為衡量指標，著重從優化改進后算法的收斂準確率和時間效率兩個方面進行算法的評價。前者主要考察算法優化的合理性、并行設計的科學性、迭代收斂的準確性[8]，后者主要驗證并行化之后效率的提升情況。

本文從以下幾個具體的指標進行平臺性能的綜合評估。

平均運行時間：在算法參數收斂之前，需要對原始數據進行訓練、迭代，整個過程需要消耗大量的運行時間，把每一輪迭代的平均運行時間作為基本衡量指標，來衡量算法收斂的時間效率。

吞吐量：單位時間內系統所處理的任務總數。在通常情況下，隨著任務數量的增加，平臺中排隊等待的任務數會增加，這將導致系統的任務處理能力不會隨著輸入的任務數的增加而提高。本文設計的平臺采用了Spark Streaming流式處理的方式[9]，由于流式處理的邏輯通常比較簡單，實時性處理能力優越，會在相當大的程度上彌補這個不足。

收斂準確率：算法在迭代過程中達到設定的迭代次數閾值時，被準確聚類的數據點個數占數據點總個數的比值[10]，用來衡量算法收斂之后得到的聚類結果的準確性。

3 算法性能試驗驗證

3.1 試驗環境

本文搭建包含6個節點的Spark集群進行試驗，節點具體配置如表1和表2。

表1 節點硬件配置

表2 節點參數配置

集群環境安裝Hadoop 2.6版本，Spark 2.4版本，JDK 1.8版本。Hadoop并行化最大map數為16，最大reduce數為2，每個任務可以使用4G內存，Spark每個節點的計算內存為20G，用于數據計算和RDD數據塊間的調度和關系依賴加載。

3.2 試驗結果對比

實驗從平均運行時間、吞吐量和收斂準確率三個指標，對單機版的K-means聚類算法、Spark平臺集成的算法和Spark Streaming優化后的算法三種狀況下進行對比。實驗數據為某購物平臺的真實數據，選取的數據對（樣本數，特征數）為（1w,100）、（1w,1k）、（10w,100）、（10w,1k）、（100w,100）、（100w,1k）。

（1）平均運行時間

從待測數據輸入測試環境到得到收斂后的算法模型為一個運行周期，每種算法用六組數據進行獨立測試，測試結果如圖2。

圖2 平均運行時間對比

由圖2測試結果可以看出，在數據量較小時單機模式和SparkStreaming模式都能取得較好的運行速度，SparkStreaming模式和Spark模式需要不斷的進行節點間的信息傳輸和調度，但是SparkStreaming模式通過流式處理和并行優化，降低了節點間數據傳輸帶來的時間消耗，而Spark模式由于需要節點間數據傳輸，所以會比單機模式消耗時間多。隨著數據量和特征數量的增多，單機模式會越來越無法承受大數據量的迭代計算，時間消耗會成倍增加，SparkStreaming模式和Spark模式由于是采用分布式模式，處理大數據量數據較單機模式有明顯優勢，SparkStreaming模式的優化處理，即便是數據量增加，所消耗的時間不會增加太多。

（2）吞吐量

本實驗選取10秒內在三種環境下處理的任務數（即迭代次數，并保留整數位）進行對比。為了盡可能模擬現實場景下的實時處理，測試數據以數據流的方式輸入到測試系統，并且數據流以并發的形式從多個節點同時輸入。在實驗中，數據流生成間隔設定為0.5秒，滑動窗口為2秒。測試結果如圖3。

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

圖3 吞吐量對比

（3）收斂準確性對比

本實驗的聚類算法屬于無監督的機器學習范疇，無法用某一個標準聚類結果作為參考，所以，在驗證收斂準確性時，SparkStreaming模式和Spark模式的聚類結果與單機版模式做比較，用三者的偏差作為衡量標準。具體衡量指標為：同一聚類中包含的數據點個數和單機版模式下對應聚類中數據點個數的差值與單機版模式對應聚類中數據點總個數的比值。實驗結果如圖4。

圖4 收斂準確率對比

由圖4實驗結果可以發現，在六組數據上的測試結果偏差很小，說明基于Spark Streaming的并行K-means改進算法在聚類準確性方面可以滿足要求。

綜上實驗結果，基于Spark Streaming的并行K-means改進算法在聚類準確性較高的情況下，在收斂速率方面又明顯的優勢，可以滿足實時性數據聚類的要求。

4 結語

為了解決經典的K-means聚類算法無法滿足大數據背景下對實時聚類的要求，本文基于Spark Streaming流數據處理框架對K-means聚類算法進行改進，通過SparkContext的廣播函數共享聚類中心、KD樹對迭代過程進行二次優化、以滑動窗口作為數據的輸入單元動態調整批量數據的輸入時間間隔和聚類中心的更新頻率等優化策略，使得改進算法在滿足聚類準確性的同時能夠很好地處理實時數據。后續工作將繼續針對不同的應用場景對改進算法進行定向優化。