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

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

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

引言

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

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

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

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

1. Apache Flink 分布式平臺

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

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

2. 技術(shù)概念和原理

2.1 K-Means算法

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

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

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

（1）包圍獵物

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

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

（3）獵物搜索

2.3 啟發(fā)式概率

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

K-Means算法容易陷入局部最優(yōu)解，而啟發(fā)式優(yōu)化算法因?yàn)椴恍枰荻认嚓P(guān)信息，能在一定程度上避免陷入局部最優(yōu)解。鯨魚優(yōu)化算法具有優(yōu)秀的全局搜索能力，因此把兩者結(jié)合起來，利用Flink分布式框架對鯨魚優(yōu)化算法各個(gè)計(jì)算模型重新編程，把算法數(shù)據(jù)封裝到DataStream并行計(jì)算。基于Flink的鯨魚優(yōu)化K-Means算法的設(shè)計(jì)如下：

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

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

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

算法步驟如下：

結(jié)語

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

參考文獻(xiàn)：

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

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

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

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

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

[6]王法玉，劉志強(qiáng).Spark框架下分布式K-means算法優(yōu)化方法[J].計(jì)算機(jī)工程與設(shè)計(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í)驗(yàn)師。研究方向：大數(shù)據(jù)技術(shù)、智能信息處理。

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