基于Flink的鯨魚優(yōu)化K-Means算法

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

關鍵詞：聚類算法；K-Means；鯨魚優(yōu)化；Flink

引言

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

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

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

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

1. Apache Flink 分布式平臺

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

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

2. 技術概念和原理

2.1 K-Means算法

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

2.2 鯨魚優(yōu)化算法

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

（1）包圍獵物

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

（2）發(fā)泡網(wǎng)攻擊

（3）獵物搜索

2.3 啟發(fā)式概率

3. 基于Flink的鯨魚優(yōu)化K-Means算法

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

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

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

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

算法步驟如下：

結語

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

參考文獻：

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

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

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

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

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

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

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

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

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