基于仿生優(yōu)化算法的聚類改進(jìn)算法

覃承友, 謝曉蘭, 王悅悅, 郭 楊

(桂林理工大學(xué) a.廣西嵌入式技術(shù)與智能系統(tǒng)重點實驗室; b.信息科學(xué)與工程學(xué)院, 廣西 桂林 541006)

聚類, 是數(shù)據(jù)挖掘中一個重要的組成部分, 其目的為按照設(shè)定的特定標(biāo)準(zhǔn)把物理或抽象的對象集合分割成不同類或簇的小集合, 這些小集合中的對象彼此相似, 并與其他類或簇的對象有所差異, 即聚類產(chǎn)生的同一類數(shù)據(jù)對象盡可能聚合在一起, 不同的數(shù)據(jù)對象盡可能分離[1]。k均值聚類算法(k-means clustering algorithm, 簡稱k-means)在聚類算法中有著舉足輕重的地位, 雖然其邏輯理論簡單、可高效實現(xiàn), 應(yīng)用十分廣泛, 在故障檢測[2]、無人機(jī)應(yīng)急[3]、隱私保護(hù)[4]等方面都有著廣泛的應(yīng)用，但是k-means算法本身也存在著一定缺陷, 如對初始聚類中心非常敏感, 且在迭代過程中容易陷入局部最優(yōu)等問題。針對這些問題, 對于k-means算法的改進(jìn)方法有很多, 其中仿生優(yōu)化算法作為當(dāng)今研究的熱門領(lǐng)域, 和k-means進(jìn)行結(jié)合使用是一個可行的方法, 其模擬了昆蟲、獸群、鳥群和魚群等群體的行為, 群體中每個成員通過學(xué)習(xí)自身和其他成員的經(jīng)驗不斷優(yōu)化搜索, 可以有效地找出全局最優(yōu)解。如在文獻(xiàn)[5]中提出了基于改進(jìn)人工蜂群算法的k均值聚類算法, 使用最大最小距離初始化蜂群, 構(gòu)造出一種基于全局引導(dǎo)的位置更新策略, 提高了迭代尋優(yōu)的效率; 文獻(xiàn)[6]提出了基于改進(jìn)粒子群算法的k均值聚類算法, 使用加入混沌搜索過程的粒子群算法增加粒子的多樣性, 為k-means有效地找到了較好的初始中心; 文獻(xiàn)[7]提出了基于云計算平臺的仿生優(yōu)化聚類數(shù)據(jù)挖掘算法, 通過利用相似聚類和狼群優(yōu)化算法, 以頭狼的位置確定聚類中心, 在不斷的狼群優(yōu)化以及相似聚類中實現(xiàn)了在云計算平臺對數(shù)據(jù)樣本大且高維的數(shù)據(jù)聚類, 并提升了收斂速度。上述算法在改進(jìn)k-means中側(cè)重點各有不同, 對于k-means對初始聚類中心的敏感和易陷入局部最優(yōu)的問題并沒有得到很好的解決或達(dá)到很好的聚類效果。

本文在研究k-means聚類算法及仿生優(yōu)化算法上, 將屬于仿生優(yōu)化算法中的果蠅優(yōu)化算法(fruit fly optimization algorithm, FOA)與k-means進(jìn)行結(jié)合以達(dá)到更好的聚類效果。用改進(jìn)的果蠅優(yōu)化算法改良k-means的聚類中心, 解決k-means易陷入局部最優(yōu)及其初始聚類中心敏感的問題?？紤]到不同算法模型在不同數(shù)據(jù)集上的效果有所差異, 為了實驗的嚴(yán)謹(jǐn)以及準(zhǔn)確性, 本方法選擇不同UCI的標(biāo)準(zhǔn)數(shù)據(jù)集進(jìn)行實驗對比分析。

1 相關(guān)算法

1.1 k-means聚類算法

對于給定數(shù)據(jù)集X=(X1,X2,…,Xn)其中包含n個成員對象,k-means的任務(wù)就是將這n個對象根據(jù)某種距離或某種相似性劃分到k個簇中(C1,C2, …,Ck, 2≤k≤n), 簇的聚類中心稱為質(zhì)心, 并使得這k個簇的聚類均值達(dá)到總體誤差最小, 即損失函數(shù)達(dá)到最小,k-means的損失函數(shù)為

(1)

其中:x表示數(shù)據(jù)樣本點;Ci表示第i個簇;k表示劃分的簇數(shù);φi為簇Ci的質(zhì)心, 表示為

(2)

算法的具體步驟為:

步驟1: 給定需要聚類產(chǎn)生的簇數(shù)k, 在數(shù)據(jù)集中隨機(jī)抽取k個點作為初始質(zhì)心, 給定迭代次數(shù)和聚類效果閾值。

步驟2: 按照式(3)計算給定數(shù)據(jù)集中所有對象與各個質(zhì)心的歐氏距離

(3)

其中:dist(x,y)表示每個對象的歐氏距離;xi、yi表示對象的坐標(biāo);n表示每個簇中的對象總數(shù)。

步驟3: 根據(jù)簇中所有的對象, 根據(jù)式(2)重新計算質(zhì)心。

步驟 4: 判斷是否達(dá)到迭代次數(shù)或滿足聚類效果閾值, 若是, 停止算法, 保存質(zhì)心與各個聚類的對象; 若否, 重復(fù)步驟2、3和4。

1.2 果蠅優(yōu)化算法

果蠅優(yōu)化算法[8]的核心在于果蠅個體利用自身的嗅覺獲取食物源的濃度值, 并向周圍的其他果蠅個體發(fā)送氣味信息, 再利用視覺飛向濃度值最高的果蠅位置, 飛行的半徑取決于食物源的濃度值大小。標(biāo)準(zhǔn)的果蠅優(yōu)化算法流程如下[9-10]。

步驟1:初始種群規(guī)模sizepop, 最大迭代次數(shù)maxgen, 維度dim和果蠅個體的飛行半徑L, 并初始化果蠅種群的位置, 其對應(yīng)的初始位置信息定義為

(4)

步驟2:每一個果蠅個體根據(jù)賦予的飛行半徑和方向, 開始更新自身的位置, 更新公式如下

(5)

步驟3:由于初始食物源的方向和距離是未知的, 因此每一個果蠅個體根據(jù)式(6)計算距離原點的距離dist, 并根據(jù)式(7)作為其對于食物源的濃度值判定Si, 同時利用式(8)計算每一個果蠅個體的味道濃度值Smelli

(6)

Si=1/disti；

(7)

Smelli=fitness(Si)。

(8)

式中：Xaxis、Yaxis表示初始種群坐標(biāo); rand()表示隨機(jī)分布數(shù);Xi、Yi為更新坐標(biāo);i表示第i個果蠅個體; fitness()表示味道濃度值的判斷函數(shù), 即適應(yīng)度函數(shù)。

步驟4:記錄當(dāng)前群體中最優(yōu)味道濃度值的果蠅位置信息, 并將其具體信息存入最優(yōu)群體Smellbest。

步驟5: 根據(jù)最優(yōu)味道濃度值和記錄的位置信息bestSmell,果蠅群體的所有個體都往這個方向飛去。

步驟6:判斷是否達(dá)到迭代次數(shù)maxgen, 否, 則重復(fù)步驟2～6；是, 則輸出最優(yōu)值, 結(jié)束循環(huán)。

通過以上迭代步驟可知, FOA的搜索策略是基于全局搜索的, 并根據(jù)每次迭代的最優(yōu)解指導(dǎo)下一次迭代的方向與位置, 能夠使種群以當(dāng)前最優(yōu)解繼續(xù)開展隨機(jī)搜索, 從而朝著更優(yōu)的方向搜索前進(jìn)。

2 基于果蠅優(yōu)化算法的k-means算法

2.1 基于F分布的果蠅飛行半徑更新策略

F分布式是一種非對稱分布[11], 其有兩個自由度, 且位置不可置換, 設(shè)X服從自由度為n1的卡方分布,Y服從自由度為n2的卡方分布, 且X、Y獨立, 則稱隨機(jī)變量F=(X/n1)/(Y/n2)服從自由度為(n1,n2)的F分布記為F～F(n1,n2), 其概率密度表達(dá)式為

(9)

(10)

其中:n1為第一自由度;n2為第二自由度。對于自由度不同的F分布如圖1所示。

圖1 不同自由度的F分布曲線對比

使用基于F分布的果蠅飛行半徑更新策略能有效優(yōu)化果蠅優(yōu)化算法中的飛行機(jī)制。在原始的果蠅優(yōu)化算法中, 每次的飛行半徑是固定的, 這就影響了算法在迭代中的尋優(yōu)能力：如設(shè)置過大的飛行半徑，雖然在算法迭代前期能很好地擴(kuò)大搜索范圍, 并有效避免陷入局部最優(yōu), 但是在算法迭代后期卻容易在最優(yōu)解附近產(chǎn)生震蕩, 難以有效接近最優(yōu)解; 若設(shè)置過小的飛行半徑，則容易在算法迭代前期過早的陷入局部最優(yōu), 難以搜索最優(yōu)解。因此，選擇一個合適的飛行半徑對于果蠅優(yōu)化算法十分重要, 使用本文基于F分布的飛行半徑, 能有效規(guī)避以上兩個問題。由圖1可知, 在F分布的曲線中, 概率密度的變化曲線是非對稱的, 算法設(shè)置每迭代一次,F分布的自變量x增加0.05, 其對應(yīng)的概率密度即為算法變化步長。以基于F分布的變化飛行半徑, 算法能在開始迭代的時候能很好地擴(kuò)大搜索范圍, 迭代到最后能避免震蕩并找到全局最優(yōu)解, 有效提升果蠅優(yōu)化算法的尋優(yōu)效率。

2.2 基于精英保留機(jī)制的果蠅種群優(yōu)化

精英保留機(jī)制, 是一種高效的全局搜索機(jī)制, 近年來在仿生優(yōu)化算法的改進(jìn)中運用十分廣泛, 其主要思想是針對一個問題求出所有可行解, 通過可行解求出反向解, 并對原解和反向解進(jìn)行評估比較, 從而選擇較優(yōu)的解作為精英解保留為下一代。

反向解的求解取決于反向點, 設(shè)有n個二維空間點的集合S=(S1,S2, …,Sn),Sa和Sb為集合的最大值和最小值, 則對于點Si的反向點定義為Si′, 其表達(dá)式為

Si′=Sa+Sb-Si。

(11)

通過比較原始解和反向解, 選擇其中的最優(yōu)解作為精英解。設(shè)點Si為果蠅的原始解, 則Si′為反向解, 設(shè)f(S)為目標(biāo)函數(shù), 當(dāng)f(Si)≥f(Si′)時, 稱為Si精英解; 當(dāng)f(Si)

由于精英解是比較原始解和反向解得來的, 因此能及時避免對劣質(zhì)果蠅個體的繼續(xù)搜索, 讓種群向著更優(yōu)的區(qū)域搜索。使用精英解對果蠅種群的改進(jìn), 能有效擴(kuò)大種群的搜索范圍, 避免陷入局部最優(yōu)。

2.3 改進(jìn)的k-means算法

本文基于以上兩點改進(jìn)策略提出了基于改進(jìn)果蠅優(yōu)化算法的k-means聚類算法BFOA-K。該算法的基本思想是:通過改進(jìn)的果蠅優(yōu)化算法進(jìn)行一次迭代搜索最優(yōu)值, 將得到的最優(yōu)值的位置信息作為k-means聚類的初始質(zhì)心并開始一次聚類分析, 再利用聚類得到新的質(zhì)心, 將新的質(zhì)心的位置信息返回更新果蠅種群, 反復(fù)交替迭代執(zhí)行FOA和k-means直到滿足最大迭代次數(shù)結(jié)束算法。改進(jìn)的BFOA-K算法的流程如下:

步驟 1:初始果蠅種群規(guī)模sizepop, 維度dim最大迭代次數(shù)maxgen, 利用F分布定義果蠅飛行半徑L和初始化果蠅種群的位置, 并給定聚類的簇數(shù)k。

步驟2: 利用式(11)重新定義果蠅個體的位置信息, 比較它們的最優(yōu)值來定義精英群體, 同時每一個果蠅個體根據(jù)賦予的飛行半徑和方向, 開始更新自身的位置。

步驟3: 由于初始食物源的方向和距離是未知的, 因此先計算每一個果蠅個體距離原點的距離dist, 并根據(jù)式(7)作為其對于食物源的濃度值判定Si, 根據(jù)式(8)計算每一個果蠅個體的味道濃度值Smelli。

步驟 4: 記錄當(dāng)前群體中最優(yōu)味道濃度值的果蠅位置信息, 并將其具體信息存入最優(yōu)群體Smellbest。

步驟5:根據(jù)記錄的最優(yōu)個體的位置信息bestSmell, 將其作為聚類的初始質(zhì)心, 并執(zhí)行如下操作:

a.根據(jù)歐氏距離利用式(3)計算數(shù)據(jù)集中每個對象所隸屬的質(zhì)心;

b.根據(jù)分配的簇中的對象, 根據(jù)式(2)重新計算每個簇的質(zhì)心;

記錄每個質(zhì)心的位置信息和聚類結(jié)果, 并將質(zhì)心位置重新作為果蠅種群的個體, 根據(jù)最優(yōu)味道濃度值和記錄的位置信息, 果蠅群體的每一個個體都往這個方向飛去。

步驟6: 判斷是否達(dá)到迭代次數(shù)maxgen。否, 重復(fù)步驟2～6；是, 則輸出最優(yōu)值, 結(jié)束循環(huán)。

本文的算法流程如圖2所示。

圖2 本文算法流程圖

3 仿真結(jié)果及分析

3.1 實驗分析

為了驗證本文算法的有效性, 使用4組算法實驗作為對比, 分別為傳統(tǒng)k-means聚類算法[12]、IABC算法[5]、基于自適應(yīng)參數(shù)改進(jìn)的密度聚類算法KANN-DBSCAN[13]、無改進(jìn)果蠅優(yōu)化k-means聚類算法FOA-K和本文提出的基于改進(jìn)果蠅優(yōu)化算法的k-means聚類算法BFOA-K。為了驗證算法的多樣性, 將采用多組數(shù)據(jù)集進(jìn)行實驗, 數(shù)據(jù)集采用UCI上的Iris、Wine、WDBC和Yeast 4個標(biāo)準(zhǔn)數(shù)據(jù)集。本文實驗環(huán)境為Windows 10 操作系統(tǒng), CPU參數(shù)為Xeon(R)E-2124G@3.40 GHz, 16 GB內(nèi)存, Matlab R2018b, Python 3.7。各個數(shù)據(jù)集的詳細(xì)信息見表1。

表1 各數(shù)據(jù)集詳細(xì)信息

3.2 結(jié)果與分析

聚類的目的是將特征屬性相近的劃分成同一個簇, 在聚類劃分簇中有很多的評價指標(biāo), 本文評價指標(biāo)采用調(diào)整蘭德指數(shù)(ARI)衡量數(shù)據(jù)分布的吻合程度

(12)

其中:RI表示蘭德指數(shù); E(RI)表示蘭德指數(shù)的期望; max(RI)表示最大蘭德指數(shù)。

采用聚類精確度(ACC)比較獲得標(biāo)簽和數(shù)據(jù)提供的真實標(biāo)簽

ACC=NAC/N,

(13)

其中:N表示樣本總數(shù);NAC表示聚類正確的數(shù)量。

采用標(biāo)準(zhǔn)化互信息(NMI)度量聚類結(jié)果的相近程度

(14)

其中:U表示真實標(biāo)簽向量;V表示預(yù)測標(biāo)簽向量;MI(U,V)表示互信息;H(U)和H(V)表示信息熵。

由于4個數(shù)據(jù)集的屬性各不相同, 因此在選擇F分布的自由度時也不同, Iris、Wine、WDBC和Yeast選擇的F分布的自由度依次是(5, 5)、(10, 5)、(5, 50)和(10, 50), 算法對比將在每個數(shù)據(jù)集上重復(fù)運行100次, 計算每個評價指標(biāo)的平均值。上述評價指標(biāo)設(shè)置為值越大表示效果越好。實驗結(jié)果如表2～表5所示。

表2 5種算法在Iris數(shù)據(jù)集上的比較

表3 5種算法在Wine數(shù)據(jù)集上的比較

表4 5種算法在WDBC數(shù)據(jù)集上的比較

表5 5種算法在Yeast數(shù)據(jù)集上的比較

在4個數(shù)據(jù)集的測試中, 加入改進(jìn)果蠅優(yōu)化算法的k-means聚類算法在各方面都能達(dá)到更好的聚類效果。BFOA-K相較于傳統(tǒng)k-means算法,ARI平均提升了20.81%,ACC平均提升了23.56%,NMI平均提升了29.75%, 較于其他對比算法平均也有12.67%的提升。在樣本數(shù)量及屬性數(shù)不大的情況下, 5種算法在各種評價指標(biāo)下都有很好的聚類效果, 但總體還是本文提出的算法要優(yōu)于其他對比算法; 而當(dāng)樣本數(shù)量及屬性數(shù)增加時, 5種算法的性能都有所下降, 但本文算法還是稍微優(yōu)于其他對比算法, 其主要原因是BFOA-K算法不僅在果蠅飛行半徑上使用了可變的F分布, 動態(tài)調(diào)整果蠅搜索半徑, 而且在果蠅的種群優(yōu)化上使用了精英策略, 使得果蠅擴(kuò)大了搜索范圍, 增加了果蠅的多樣性。但是在高維度和高樣本量的數(shù)據(jù)集中, 尤其是在Yeast數(shù)據(jù)集下每個算法表現(xiàn)都不好, 這主要是因為涉及高維高樣本的數(shù)據(jù)集中需要進(jìn)行一定的降維或特征提取, 所以會丟失一定的信息量, 導(dǎo)致聚類效果不明顯, 改進(jìn)數(shù)據(jù)集降維方法將是以后的研究重點。

為了驗證本文算法的收斂速度及收斂程度, 選取了樣本屬性都有一定差異的Iris和Yeast兩個數(shù)據(jù)集進(jìn)行比較, 兩個數(shù)據(jù)集隨迭代次數(shù)的目標(biāo)函數(shù)適應(yīng)值變化曲線如圖3、圖4所示。

圖3 5種算法在Iris數(shù)據(jù)集迭代圖

圖4 5種算法在Yeast數(shù)據(jù)集迭代圖

可以看出，本文提出的BFOA-K算法在兩個數(shù)據(jù)集的測試中, 收斂速度和程度都優(yōu)于傳統(tǒng)k-means聚類算法；盡管IABC算法在Iris數(shù)據(jù)集的迭代過程有更好的適應(yīng)度, 因BFOA-K在聚類過程中注重的是聚類效果和收斂速度的平衡, 所以BFOA-K的聚類效果與IABC差距并不大, 且BFOA-K的收斂速度明顯快于IABC。在樣本數(shù)量和屬性數(shù)均不多的Iris數(shù)據(jù)集中, 5個算法的性能都極為相近, 但是加入F分布變化步長的BFOA-K在改變飛行半徑的情況下, 收斂速度和收斂程度都略優(yōu)于其他算法。而在樣本數(shù)量和屬性數(shù)與Iris數(shù)據(jù)集差異明顯的Yeast數(shù)據(jù)集的測試中, 無論是收斂速度還是收斂程度, BFOA-K的目標(biāo)函數(shù)適應(yīng)值都要優(yōu)于其他算法, 這主要得益于精英策略對果蠅種群搜索范圍的優(yōu)化和F分布的飛行半徑的雙重影響。在樣本數(shù)量不高和維度較低的數(shù)據(jù)集中,F分布能發(fā)揮大部分的作用, 在高維高數(shù)據(jù)樣本的數(shù)據(jù)集中, 兩個改進(jìn)策略則能共同發(fā)揮作用, 改善聚類效果。通過Iris和Yeast兩個數(shù)據(jù)集的對比實驗, 證明了本文算法能在不同數(shù)據(jù)集上在更短的時間內(nèi)擁有更好的聚類效果, 證明了算法性能的有效性。

4 結(jié)束語

本文針對k-means聚類算法對于初始質(zhì)心的敏感和容易陷入局部最優(yōu)的問題, 提出了基于改進(jìn)果蠅優(yōu)化算法的k-means算法(BFOA-K)。通過分析k-means算法和FOA算法的特點, 在融合算法的同時改進(jìn)了FOA, 通過加入F分布, 利用其特性作為動態(tài)調(diào)整果蠅的飛行半徑; 利用精英果蠅, 拓展了果蠅的搜索范圍；利用種群的多樣性提升了算法的穩(wěn)定性。采用4個UCI的標(biāo)準(zhǔn)數(shù)據(jù)集進(jìn)行仿真實驗, 將本文算法與多種算法進(jìn)行比較, 結(jié)果顯示, 在各個評價指標(biāo)中本文提出的算法都有良好的聚類效果, 證明了算法的有效性，并用兩個對比數(shù)據(jù)集進(jìn)行測試, 結(jié)果表明無論在收斂速度還是收斂程度本文的BFOA-K算法都有著優(yōu)異的表現(xiàn), 有效證明了算法的穩(wěn)定性。

本文算法在針對高維和高數(shù)據(jù)樣本的數(shù)據(jù)集中聚類效果沒有體現(xiàn)出明顯的優(yōu)異性, 今后需要結(jié)合其他改進(jìn)策略, 對算法進(jìn)行更進(jìn)一步的研究, 得到更加完善的結(jié)果。