摘要:針對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)。