基于Flink 框架的K-means 算法優化及并行計算策略?

李召鑫 孟祥印 肖世德 胡鍇灃 賴煥杰

（西南交通大學機械工程學院 成都 610031）

1 引言

進入到新世紀以來，伴隨著科學技術的飛速發展，在各個領域每時每刻都在產生成千上萬的數據，如何能高效地從這些海量數據中提取出有應用價值的信息已成為當前的研究熱點。K-means 是數據挖掘技術中解決海量數據聚類問題的經典算法［1］，因其存在執行快速、易于并行化等優點故在許多領域都得到了廣泛的應用。但同時存在一些不足：需指定聚類中心數；初始聚類中心的選取策略是完全隨機，這可能會影響到最終聚類結果的準確率及計算速度。這兩種缺點嚴重限制了K-means算法聚類效果和計算效率的提高。

針對傳統K-means算法存在的不足，許多研究人員都提出了各種改進算法，主要是對于聚類中心數的確定及聚類中心的選擇策略的優化。杜佳穎等［2］提出了一種基于K-means++算法優化初始中心點選擇的改進算法，通過計算平均輪廓系數來指定K 值，該算法有效提高了計算效率；李淋淋等［3］提出了一種基于Spark 平臺的SBTICK-means 算法，針對傳統K-means算法在大規模數據計算時存在的瓶頸，引入Canopy 算法和三角形不等式定理，顯著提高了聚類結果速度及準確率，并具有良好的擴展性；梁彥［4］提出了一種基于Spark 平臺的并行K-means算法和Canopy K-means算法，該算法并行化后具有較好的聚類效果，相比于Hadoop 平臺，具有更高的效率；許明杰等［5］提出一種Spark 并行化的PSOK-means 算法，將PSO 算法與K-means 算法相結合，利用改進后的PSO 算法提高K-means的全局搜索能力，并在Spark框架上進行了實現，通過疾病檢測數據進行聚類實驗來驗證所提出算法的效率；王義武等［6］提出了一種OCC K-means 算法，采用最大最小距離算法和UPGMA 來篩選初始中心，并基于Spark 框架進行實現，有效提高了聚類精度及和計算速度。王美琪等［7］提出一種APMMD 算法，通過近鄰傳播算法獲取候選中心點，然后利用最大最小距離算法再選取k 個初始中心點，該算法有效減少了迭代次數。

Apache Flink［8～11］是近年來新興的一個大數據處理框架，與Hadoop不同，Flink是一個集批處理和流處理于一體的計算框架，具有同時支持高吞吐、低延遲、高性能的優點，現在的絕大部分聚類算法并行化研究大都基于批處理框架，如Hadoop、Spark［12～13］等，而基于Flink 實現的聚類算法研究較少?；谝陨项A研究，本文綜合上述聚類優化算法的優點，充分利用Flink框架在計算方面的優勢，提出一種基于Flink 框架對K-means 優化算法進行并行化加速的方案，有效提升了K-means算法的聚類速度。

2 相關理論和技術

2.1 K-means算法

K-means 算法［14］（又稱為K-均值算法）是Mac-Queen在1967年提出的一種基于劃分的聚類算法，因其算法思想簡單且易于實現被廣泛應用于數據挖掘領域。該算法的作用將數據集S中的n個點劃分到K 個類中，具體操作步驟如下：先從數據集S中隨機抽取K 個點作為初始聚類中心C（C1，C2，…，Ck），然后計算數據集中每個樣本點X 到每個聚類中心的距離（一般采用歐式距離［15］式（1）作為度量）。

其中：d 表示兩個樣本點間的距離，n 為數據集的維度數量。

以此作為分類依據，按照最近距離公式將數據集中的各個樣本點X 分配給距離最近的聚類中心C（C1，C2，…，Ck），隨即更新每個聚類中心的值，設為其類別所有樣本的平均值，這個過程會不斷迭代直到達到迭代次數或聚類算法的誤差達到設定的閾值。

在聚類算法中，我們通常使用SSE（The sum of squares due to error）即誤差平方和來表示聚類的誤差大小，根據此值的大小來決定迭代是否結束。其公式如下：

其中：K 為聚類類別數，X 為數據集中的一個數據點，p為一個聚類中心。

2.2 Aphche Flink

Flink是Apache基金會旗下的一個開源的分布式計算框架，可同時支持流處理和批數據處理。Flink 和Spark 在架構上有一定的相似性，都是基于Master-Slave 架構，并且支持內存計算。Flink 的數據流執行圖包含以下三個階段（如圖1 所示）：Source、Transformation 和Sink。其中，Source 階段的作用是用來加載數據集，Transformation階段的作用是利用各種算子對數據流進行相應處理，主要包括map、flatMap、keyBy、reduce 等算子，Source 和Transformation 的并行度可以通過setParallelism 函數進行自定義設置。Sink 階段負責數據處理結果的輸出，其并行度為1。

圖1 Flink框架工作架構圖

3 基于Flink 的K-means 算法優化策略

3.1 聚類類別K值的確定

K-means 算法需要指定聚類類別數K，K 的取值將直接影響到最終的聚類結果及準確率，所以預先得到合適的K 值顯得尤為重要。Canopy 算法［16］是McCallum 在2000 年提出的一種聚類算法，該算法目的是將整個數據集粗略地劃分為不同的類別，優點是不用預先設定K值就可以完成粗聚類，因此可用于K-means聚類之前，將粗聚類結果的結果作為K-means 的參照，避免了K 值選擇的盲目性，從而提高聚類速度。其流程如圖2所示。

圖2 Canopy算法確定K值流程圖

3.2 初始聚類中心的確定

初始聚類中心的理想狀態是分布盡量分散，這樣可以降低聚類結果陷入局部最優的概率，而且可以提高計算效率。本文關于聚類中心的指定是基于最大距離算法進行實現的，其基本思想如下，先輸入數據集和類別數量K，然后隨機選取一個數據點作為聚類中心，在選取剩下的K-1 個聚類中心時，通過比較數據集中的數據與已被選取的聚類中心的距離來找到最大距離dmax所對應的數據點，然后將該點加入聚類中心，最終得到所有的聚類中心。這種方法可以解決K-means 算法隨機選取聚類中心時聚類中心過于鄰近的問題，從而減少迭代次數，有效提高算法效率。算法流程如圖3所示。

土地深松作業效果顯著。從2011年開始，河南省農機深松整地工作由點到面，穩步推進。目前，全省累計開展農機深松整地8300多萬畝，其中安排作業補助資金近7億元，累計補助作業面積2700余萬畝。各地農機部門在技術模式、保障手段、監督管理等方面開展了有益探索。通過示范帶動，調動了廣大農民的土地深松積極性；通過技術培訓，培養了一大批掌握農機深松整地作業技術、帶頭實施深松作業的農機人員；經過試驗研究，建立了適應河南土壤特點、種植結構的農機深松整地作業技術模式和機具配置模式；根據基層實際，探索總結了組織作業、面積確認、質量管控和資金兌付的行之有效的工作措施。

圖3 最大距離算法確定聚類中心流程圖

3.3 基于Flink的K-means優化算法并行化實現

Flink 計算框架本身支持并行計算，其并行度指的是同時運行的線程的個數，通常一個Flink 程序由多個任務組成，這根據用戶設定的分組及并行度來確定。Flink 集群中的每個TaskManager 都包括多個slot，每個TaskManager 所擁有的slot 數量代表了該TaskManager 具有的并發執行能力，此參數可以通過taskmanager.numberOfTaskSlots 參數來進行設置，通常與該節點CPU 可用核數成正比。Flink 在某些條件下可以減少節點之間通信的開銷，是基于一種叫做任務鏈的技術來進行實現的，當多個算子設置了相同的并行度，而且是one to one 操作，這樣相連的算子可以鏈接在一起形成一個task，算子之間通過本地轉發（local forward）進行連接，其邏輯視圖、并行化視圖、優化后視圖如圖4所示。

圖4 Flink任務鏈示意圖

本文算法所采取并行化策略如下，首先，在JobManager節點獲取到數據集之后，將其廣播到每個TaskManager 節點，采用最大距離算法逐次選取K 個初始聚類中心，再通過withBroadcastSet 函數將初始聚類中心的信息廣播到各個TaskManager 節點，在節點上迭代執行K-means 算法，最后根據設置的迭代次數或者損失函數SSE 來判斷是否結束聚類過程。Flink 程序分為Source、Transformation、Sink三個階段，其中Source和Transformation階段是可以實現并行化的，通過并行化來減少數據加載及數據計算的過程，從而提高Flink 程序整體的運行速度。JobManager主節點的作用是獲取數據集，并通過廣播分發至每個TaskManager，然后TaskManager迭代計算聚類中心到數據集中每個點的距離，將每一個數據點都歸類到一個類別，最后將計算結果返回給JobManager，完成聚類結果的輸出。

4 實驗環境與結果分析

4.1 實驗環境與數據集

本文實驗平臺采用開源Flink 分布式框架，分別安裝在5 臺虛擬機上，由一臺JobManager 和4 臺TaskManager 組成。每一臺機器的配置都是：內存2GB，硬盤20G，操作系統均為Centos 7.4。每一臺機器的軟件環境如表1所示。

表1 集群主要軟件環境詳情

本文實驗采用的數據集是從加州大學UCI 實驗室提供的機器學習數據庫中下載的iris、glass 和wine數據集，數據集詳情如表2所示。

表2 數據集相關信息

4.2 實驗結果分析

4.2.1 準確率實驗

為了對比傳統K-means 算法和本文算法的準確率，本文通過對3 個不同屬性的數據集進行聚類測試（對每種算法進行20 次隨機實驗取平均值），并統計聚類效果，聚類結果如表3 和表4 所示。從表3 和表4 可以看出，本文改進算法在求解iris、glass 和wine 數據集時相比傳統K-means 算法的準確率都有一定的提升，這表明本文基于Canopy 算法和最大距離算法的K-means 優化算法減少了聚類過程的迭代次數，對計算效率有一定的提升。

表3 K-means算法與本文改進算法準確率對比

表4 K-means算法與本文改進算法迭代次數對比

加速比是衡量并行化程序性能好壞的重要指標，該指標指的是同一個計算任務在單機環境和并行環境運行消耗時間的比值，一般來說，加速比的值越大，代表算法并行加速的性能越好。為了測試本文算法在Flink 框架下的并行化能力，本文采用了synthetic_control數據集來進行實驗驗證，該數據集含有600 個樣本點，因為原數據集數據量較少，所以本文對原數據集進行了擴展，分別生成了含有3×10^5、3×10^6 和3×10^7 個樣本點的數據集，測試了不同節點數的加速比，實驗結果如圖5所示。

圖5 基于Flink框架的改進K-means算法的加速比

由圖5 可以看出，當數據量比較小時，隨著節點數的增加，加速比折線趨于平緩，因為當數據集的規模較小時，計算時間比較短，如果節點數增加到一定數量后，會使得節點間的數據傳輸和任務調度等其他方面的時間開銷變大，進而降低算法效率。相反，當數據集達到一定規模后，加速比與節點數近似呈線性關系，實驗可以表明本文算法在處理大規模的數據時具有較高的計算效率。

5 結語

本文針對傳統K-means 算法在處理海量數據的過程中在選取初始聚類中心時存在的易陷入局部最優解和計算速度較慢等問題，提出一種基于Flink 框架并行化的K-means 優化算法。該算法采取Canopy 算法來計算K-means 算法輸入所必需的K 值，并利用最大距離算法優化初始聚類中心的選擇，最后，基于Flink并行計算框架進行實現。實驗結果表明，相比原算法，本文算法在聚類準確率和計算效率方面都有一定程度的提升，并且驗證了在大規模數據背景下并行化實現的高效性。