基于Flink的鯨魚優化K-Means算法

摘要：針對K-Means聚類算法依賴于初始聚類中心選擇的問題，利用鯨魚優化算法易于獲取全局最優解及快速收斂性的優勢，結合分布式框架的并行優勢，提出了一種基于Flink的鯨魚優化K-Means聚類算法。通過鯨魚優化算法對領頭鯨迭代更新、優化位置，用算法的最優解作為聚類中心替代K-Means算法的隨機聚類中心，改進后的算法聚類效果較好、收斂速度快，有效結合了智能算法及分布式框架的優勢。

關鍵詞：聚類算法；K-Means；鯨魚優化；Flink

引言

互聯網時代，海量數據的不斷產生和指數級增長催生了大數據技術。當前大數據領域的研究中，聚類作為數據分析的基本組成部分，是無監督學習最重要的問題之一，它依據相似度劃分數據對象，分析數據樣本的特點和數據之間的差異，是人們挖掘和分析數據間內在聯系的有效方法。聚類既可以作為一種分析手段，對數據進行分類來提取有價值的信息，也可作為一種數據預處理方法，將處理結果提供給其它算法進行進一步處理。

K-Means是Hartigan（1975）提出的一種聚類算法[1]，基本原理是提前構建目標函數、人工設定簇的個數和聚類中心，隨著迭代過程的進行，使目標函數無限接近收斂狀態，最終獲得聚類結果。這種基于劃分型的聚類算法原理易于理解、時間復雜度低、執行效率高，適用于中小規模的凸性數據集。缺點是需要手動指定聚類數目，對初始值的選擇敏感，對噪聲點和離群數據敏感。為了彌補這些缺點，更好地發揮聚類算法的性能，研究者將其它領域的方法如智能算法融合到聚類算法中。

近年來，群智能優化算法吸引了諸多研究，這類算法模擬自然界中生物群體間協作行為的優化方法，通常結構清晰、步驟簡單、全局收斂性好，具有較高自組織性、高效并行性、強魯棒性和普適性，被廣泛應用于解決各類大規模復雜問題。為了有效結合群智能算法與聚類分析，進一步提高群智能優化算法的收斂精度與收斂速度，提高聚類算法的聚類精度，學者們相繼提出了很多新算法與模型。文獻【2】基于獅群優化對改進K-Means算法進行了研究，提升了聚類精度和收斂速度；文獻【3】引入混沌PSO進行智能加權，對于復雜數據集中展現了良好的聚類性能；文獻【4】基于人工蜂群優化對K-Means算法進行改進研究，提升了聚類結果的穩定性，但是對復雜數據集的聚類性能不足。

群智能優化算法所模擬的生物界群體間的協作行為具有顯著的并行特征，因此可以將群智能優化算法應用于分布式大數據框架，進行分布式改進優化。文獻【5】基于Spark平臺進行了K-Means算法的快速聚類優化改進，文獻【6】基于Spark框架對K-Means算法減少冗余計算，進行了并行化優化，有效降低了聚類時間、提升了計算效率，但限于Spark的批計算本質，無法更好地適應流計算環境。針對上述問題，提出一種基于Flink平臺的鯨魚優化K-Means聚類算法，該方法首先基于鯨魚優化的尋優策略以及適應度結構，基于Flink分布式計算框架實現；其次，通過優化并行操作算子的性能引入分布式廣播變量，優化算法，能有效解決單機鯨魚優化算法尋優效率低的問題，提高模型的訓練效率。

1. Apache Flink 分布式平臺

Flink是Apache的頂級開源分布式處理框架，核心是用Java和Scala編寫的分布式流數據處理引擎，支持精確的流處理，能同時滿足各種規模下對高吞吐、低延遲、高性能的要求，全球很多不同行業的企業如阿里巴巴、滴滴等都在使用Flink支撐大規模核心業務，自2015年發布穩定版以來，用戶及貢獻者群體不斷發展，已逐漸成為最先進的分布式框架之一。

Flink功能強大，支持開發運行多種類的應用程序，它的競爭力特性有：（1）批流一體化；（2）精密的狀態管理；（3）同時支持事件時間和處理時間語義，前者能對無序事件提供精確一致的結果，后者能勝任極低的延遲需求；（4）精確一次的狀態一致性保障；（5）每秒處理數百萬條事件的同時保持毫秒級延遲，可以擴展數千核心；（6）分層API，最底層次的抽象，滿足高表達能力兼顧易用性；（7）支持高可用性配置（無單點失效），如Kafka以及HDFS等。

2. 技術概念和原理

2.1 K-Means算法

K-Means算法把數據分為若干個簇，先隨機指定K個數據點作為初始的聚類中心，然后計算各數據點的歐氏距離作為相似度，根據相似度最大（最小歐氏距離）原則對數據點分類，然后更新聚類中心，重新計算各數據點的相似度，重新分類。算法迭代上述步驟，直到聚類中心與前一次計算結果之間的變化量小于給定的閾值，或達到迭代次數上限時，算法終止并輸出聚類結果。算法流程如圖1所示。

2.2 鯨魚優化算法

鯨魚優化算法（Whale Optimization Algorithm，WOA）是新型智能優化算法[7]，2016年由Mirjalili提出。算法的思想靈感源自座頭鯨捕食的行為。座頭鯨在捕食時通常會先將獵物保持在水面，通過氣泡將獵物包圍起來。在捕食時，座頭鯨從比獵物深的地方搜索，然后螺旋上升靠近并吐出許多氣泡網將獵物包圍。算法的特點就是用隨機個體或最優個體來模擬座頭鯨的捕獵行為，用螺旋線來模擬座頭鯨的氣泡網攻擊機制，其步驟主要有包圍獵物、發泡網攻擊、搜索捕食。

（1）包圍獵物

鯨魚發現獵物時會圍繞獵物進行包圍，模擬過程中，獵物是算法需要求得的最優解，其位置是未知的，所以算法在這個階段先把最優的個體位置作為獵物位置，鯨魚種群的個體會向著此獵物目標位置的方向更新自己的位置，公式如下：

（2）發泡網攻擊

（3）獵物搜索

2.3 啟發式概率

3. 基于Flink的鯨魚優化K-Means算法

K-Means算法容易陷入局部最優解，而啟發式優化算法因為不需要梯度相關信息，能在一定程度上避免陷入局部最優解。鯨魚優化算法具有優秀的全局搜索能力，因此把兩者結合起來，利用Flink分布式框架對鯨魚優化算法各個計算模型重新編程，把算法數據封裝到DataStream并行計算。基于Flink的鯨魚優化K-Means算法的設計如下：

（1）鯨魚優化算法是多次迭代以尋找最優鯨魚個體，每次迭代中，根據最好的適應度去更新最優鯨魚個體的位置，而更新后的位置又是下一次迭代的重要參數。所以，采用廣播策略，把最優鯨魚個體位置和適應度的更新傳遞到Flink分布式集群的全部下游并行算子。

（2）采用流處理思想，在數據讀入的同時進行處理，數據預處理信息放入TaskManager1，啟動Action算子，依據隨機方式初始化產生的K個鯨魚群形成TaskManager2，依據公式計算鯨魚個體的適應度形成TaskManager3，TaskManager3啟動join算子，將更新的最優鯨魚個體位置聚類到TaskManager4的同一簇，啟動reduce算子計算出新的最優鯨魚個體，然后進行迭代或者輸出結果。

（3）鯨魚優化算法迭代過程中，同一個TaskManager內，尋找最優鯨魚個體的行為是獨立的，因此根據Flink平臺的應用轉換操作，對鯨魚優化的適應度尋優進行重構，如Filter及滾動聚合。

算法步驟如下：

結語

融合群智能優化算法改進了K-Means算法，克服了單種算法的缺點，融合兩種算法的優勢實現了信息增值，提升了算法整體的優化性能。與傳統聚類算法相比，改進后的算法聚類效果較好、收斂速度快。結合Flink分布式框架的優勢后，進一步有效解決了單機鯨魚優化算法尋優效率低的問題，提升了聚類結果的正確率和穩定性，增強了分析數據之間相似性、相關性、差異性的能力，擴展了算法的適應性。

參考文獻：

[1]HARTIGAN J A.Clustering algorithms［M］.NewYork：JohnWiley＆Sons Inc.，1975.

[2]胡嘯，王玲燕，張浩宇，等，基于獅群優化的改進K-Means聚類算法研究[J].控制工程，2022，29（11）：1996-2002.

[3]劉洪基.基于混沌PSO的大數據智能加權K均值聚類算法[J].計算機應用與軟件，2022，（4）：311-319.

[4]葉廷宇，葉軍，王暉，等.結合人工蜂群優化的粗糙K-means聚類算法[J].計算機科學與探索，2022，16（8）：1923-192.

[5]王全民，胡德程.基于Spark的K-means快速聚類算法的優化[J].計算機仿真，2022，39（3）：344-349.

[6]王法玉，劉志強.Spark框架下分布式K-means算法優化方法[J].計算機工程與設計，2019，40（6）：1595-1600.

[7]Mirjalili S，Lewis A.The whale optimization algorithm[J].Advances in Engineering Software，2016，95：51-67.

作者簡介：于志良，碩士研究生，實驗師。研究方向：大數據技術、智能信息處理。

基金項目：陜西省教育廳專項科研項目（編號：19JK0176）。