基于記憶傳遞旗魚優化的K均值混合迭代聚類

黃 鶴， 熊 武， 吳 琨， 王會峰， 茹 鋒， 王 珺

(長安大學 a. 西安市智慧高速公路信息融合與控制重點實驗室;b. 電子與控制工程學院， 西安 710064)

聚類分析是統計學習領域的重要組成部分[1-2]，可以針對不同的對象分析異同，根據數據之間的內在特征，將特征相似度較大的數據樣本劃分到同一簇.簇內數據相似度和簇間數據的差異性可以反映聚類算法的優劣.K-means聚類(KMC)是使用最廣泛的聚類分析算法之一[3]，但在實際應用中KMC初始點比較敏感，選取不當會導致聚類結果誤差較大[4].針對此問題，K-means++在一定程度上解決了KMC初始化方面的算法缺陷.另一方面，KMC的優化路徑過于簡單，存在算法早熟的問題.目前常用解決方案是將模擬退火、遺傳算法(GA)和群體智能等啟發式算法與K-means相結合，解決局部最優的問題[5-6].群體智能方法是一類仿生物行為計算技術，通過模擬蟻群、飛蛾等生物群體行為搜索最優解.基于群體智能的聚類優化是目前的研究熱點，廣受研究學者的關注[7-8].文獻[7]將改進飛蛾撲火算法與KMC算法交叉迭代實現聚類，由于引入樣條插值對飛蛾撲火的改進存在一定的局限，插值結果在很多情況下無法對算法結果進行有效優化，導致算法收斂速度變慢.旗魚優化器(SFO)是于2019年提出的一種新型優化算法[9]，具有尋優能力強、收斂快的優點，其靈感來自旗魚捕食沙丁魚的過程.SFO根據生物行為構建數學模型，模型由兩部分組成：一是對目前為止群體最佳個體的搜索，二是生成多樣的沙丁魚種群.SFO通過多次迭代更新旗魚和沙丁魚位置求解最優解.兩種魚的更新方式模擬了仿生學路徑，實現捕獵中的快速和高精度搜索，優化效果較好.

本文在改進SFO的基礎上，與KMC算法混合迭代，提出了一種基于記憶傳遞旗魚優化的K均值混合迭代聚類(MTSFO-HIKMC)算法.首先采用最大最小距離積對KMC進行初始化，解決了傳統聚類方法的隨機性，減少了聚類初始化耗時.同時，設計了自適應記憶傳遞優化策略，提出一種記憶傳遞旗魚優化方法，有效提升了收斂速度和搜索精度，同時避免陷入局部最優.

1 KMC算法的不足

KMC可以將數據集按照不同的類別劃分成多個子集，具體步驟如下：① 從n個數據中選取k個對象作為初始聚類中心{Ci};② 計算每個數據到k個初始聚類中心的歐氏距離，根據距離最小原則重新分類數據；③ 計算聚類簇的各個維度平均值，得到新的中心.重復步驟②和③，直到聚類中心不再發生改變或聚類中心發生偏移的距離均小于設定閾值，輸出該數據集的聚類中心.

從聚類過程可知，初始聚類中心選擇不當會陷入局部最優.聚類中心Cj的計算公式為

(1)

聚類中心Cj與樣本數據xi的歐氏距離計算為

(2)

式中：d為聚類中心個數.

因此，KMC的初始化具有隨機性，可能會將噪聲或異值作為初始中心，導致每次聚類結果相差較大，算法魯棒性較差[10].同時，簡單的更新過程會導致KMC陷入局部最優.

2 MTSFO算法

2.1 SFO算法

2.1.1初始化 SFO的初始化是在給定的搜索空間內隨機初始化，包括旗魚和沙丁魚的初始化.旗魚種群和沙丁魚種群分別用XSF和XF表示.XBSF和XBS是初始化后適應度值最好的旗魚和沙丁魚個體.在一個搜索空間內，隨機初始化沙丁魚和旗魚的比例可以根據數據集的選擇進行一定程度的調整，并按照優化函數進行適應度排序，得到最優種群.

設魚群矩陣M大小為(a,w)，則有

(3)

式中：f11為第1只旗魚在第1維變量空間的位置；w為搜索空間的特征數，即搜索空間的維數；a為旗魚和沙丁魚的總數.假設旗魚和沙丁魚的種群比例為3∶7，則旗魚數量為0.3a，沙丁魚數量為0.7a.

旗魚的適應度矩陣FSF大小為(0.3a, 1)，表示為

(4)

式中：fsfp為第p只旗魚的適應度值.

沙丁魚的適應度矩陣FS大小為(0.7n, 1)，表示為

(5)

式中：sq為第q只沙丁魚的適應度值.FSF和FS矩陣為兩種魚群適應度排序之后的結果，這說明沙丁魚s1是魚群M在當前迭代搜索中的最優解.

2.1.2旗魚位置更新機制 更新機制主要可分為旗魚的追捕過程和沙丁魚的逃脫引起的位置更新.

(1) 圍獵追捕過程.設適應度最好的個體為頭魚，旗魚依據旗魚頭魚和沙丁魚頭魚位置進行空間位置更新，向兩種頭魚漸進靠攏，聽從頭魚指揮不斷更新位置.定義旗魚位置更新機制為

XNSFi=XBSFi-λi×

(6)

式中：XNSFi為更新后的旗魚位置；λi為每次更新的步長大小；XBSFi為當前迭代i次時旗魚頭魚的位置；XBSi為當前迭代i次時沙丁魚頭魚的位置；XOSFi為上次迭代時的旗魚位置.步長定義為

λi=2rand(0, 1)PD-PD

(7)

式中：PD為獵物群的密度，表示為

(8)

式中：NSF和NS分別為旗魚和沙丁魚的數量.

(2) 沙丁魚的位置更新.沙丁魚的位置更新表達式為

XNSi=r(XBSFi-XOSi+AP)

(9)

式中：XNSi為更新后的沙丁魚位置；r為步長系數；XOSi為在當前迭代次數時沙丁魚的最佳位置；AP為旗魚的攻擊力度，計算方式為

AP=A(1-2ie)

(10)

式中：A為力度系數，控制旗魚攻擊力度，A從最大值線性遞減到0；e為方向系數，調整旗魚前進方向.當AP≥0.5時，利用式(9)更新沙丁魚全部位置；當AP<0.5時，更新沙丁部分位置，定義為

α=NSAP

(11)

β=dAP

(12)

式中：α為本次迭代需要更新的沙丁魚數量；β為本次迭代需要更新的維度數量.

SFO算法流程如下.

(1) 初始化種群和參數.

(2) 計算旗魚和沙丁魚的適應度值，并記錄最優適應度值和位置.

(3) 分別更新旗魚、沙丁魚位置.如果攻擊力度A<0.5，計算α，β的值，并且更新部分沙丁魚位置；否則，更新全部沙丁魚位置.

(4) 沙丁魚、旗魚位置替換.

(5) 計算所有適應度值，并更新記錄最優適應度值和位置.

(6) 判斷是否滿足迭代停止條件，如果滿足則輸出結果，否則重復流程(2)～(6).

2.2 改進算法

SFO受限于線性的搜索路徑，因此搜索精度有限[6].借鑒生物繁衍進化的基本邏輯，提出一種基于記憶傳遞旗魚優化算法，設計自適應記憶傳遞修正策略優化SFO的搜索路徑，以加快其收斂速度，提高聚類精度.

2.2.1自適應記憶傳遞修正策略 群體智能優化中引入樣條插值是目前的研究熱點[1]，利用歷史最優結果進行插值預測，得到優化路徑上的未來最優點，并與更新群體智能得到的最優點進行比較，加快迭代速度.然而，考慮到歷史最優點受到復雜搜索路徑帶來的隨機性影響，插值結果與真實優化路徑通常相差較大，在高維度時尤其明顯，預測結果往往不能對最優點進行有效更新.因此，提出一種自適應記憶傳遞修正策略，修正策略基本過程分為種群繁衍和自然選擇.種群繁衍過程為種群遵循父代優秀基因，產生大量攜帶有優秀基因的個體；自然選擇過程為通過人為設計的自然規律淘汰基因不夠優秀的個體，篩選出具有最優基因的子代.結合SFO的特點，設計記憶因子使旗魚群產生子代，以子代個體適應度函數作為衡量旗魚子代基因優劣的唯一標準， 從中選拔出最優子代，比較最優子代和父代頭魚之間的基因優劣，通過二次擇優得到新的旗魚種群，修正策略步驟如下.

(1) 確定記憶傳遞算子產生的子代魚苗的數量和魚苗群的半徑，表達式為

(13)

(14)

式中：N為種群數量；fk為魚群個體；fmax和fmin分別為當前魚群適應度最好和適應度最差的個體；m為種群繁衍能力，決定了一個種群產生有效個體的數量，在本文中特指最優父代個體產生子代的數量；σ為記憶因子遺傳過程中產生基因變異的劇烈幅度.σ越大，子代與父代個體相似性越小，算法的全局搜索能力越強；σ越小，子代個體與父代個體相似性越大，算法搜索精度越高.父代最優基因個體產生魚苗的過程是通過在各個維度產生服從均勻分布的隨機偏移量獲得新的魚苗，增加算法的多樣性.圖1為記憶傳遞算子產生魚苗示意圖.SFO在產生的不同魚苗之間跳躍，尋找最優子代，對當前旗魚魚群進行修正，達到二次優化的效果.其中，Fmax為當前迭代過程中旗魚個體；Fr為以父代旗魚個體作為中心點通過記憶傳遞算子產生的魚苗位置.

圖1 記憶傳遞算子Fig.1 Memory transfer operator

魚苗個數取決于父代旗魚個體基因對環境的適應性，對環境適應更好的個體產生更多的子代個體.魚苗位置在空間上服從均勻分布，記憶傳遞規則定義為

(15)

式中：μ為Fmax的向量表示.為了平衡算法的搜索能力和搜索精度，采用自適應的σ定義不同迭代時期的變異劇烈程度，計算方式定義為

(16)

式中：imax為最大迭代次數；h為記憶算子初始階段的變異幅度.記憶因子可以有效增強SFO的全局搜索能力和局部搜索精度，具體流程如圖2所示.

圖2 改進旗魚算法流程圖Fig.2 Flow chart of improved sailfish algorithm

MTSFO算法偽代碼：

輸入: 數據集、聚類數目

輸出：聚類中心、分類結果、適應度值

初始化參數

While 不滿足終止條件

更新沙丁魚群和旗魚魚群

判斷魚群超出邊界:

將樣本邊界外的值設置為邊界值.

結束判斷

旗魚遍歷

計算適應度值

結束遍歷

沙丁魚遍歷

計算適應度值

結束遍歷

按照適應度值對旗魚和沙丁魚進行排序

XBSF= 最優適應度旗魚

XBS= 最優適應度沙丁魚

更新旗魚位置

更新沙丁魚位置

Bp=XBSF

用過適應度值計算S和A1的值

While 迭代次數小于S

根據Bp的位置產生旗魚后代.

判斷后代個體的適應度值優于Bp

由相應后代個體取代Bp的位置.

結束判斷

End while

End while

輸出：聚類中心、分類結果、適應度值

2.2.2適應度函數選擇 適應度函數決定了優化群體進化的方向，直接影響種群算法的優化效果和解的質量[11-12].為使MTSFO更好地優化聚類中心，提升聚類效果，本文采用的適應度函數為文獻[7]采用的適應度函數的變體形式，不再以某一類適應度作為評價指標，采用不同簇內適應度總和作為全局適應度去指導算法收斂，適應度函數為

(17)

(18)

式中：AD為全局適應度；Lj為一個種群的適應度；d(xi,Cj)為第j簇內的全體樣本到該簇聚類中心的距離之和；Nj為第j簇中的樣本數量.從適應度函數可知，當前聚類結果的適應度不僅與每個類別所有樣本點到該簇聚類中心有關，也與該類樣本數有關，反映的是該簇所有樣本點到該聚類中心歐氏距離的均值大小.

3 MTSFO算法與KMC算法的混合迭代

3.1 最大最小距離積優化

采用最大最小距離積方法對KMC進行優化，選取密度較大且分布較稀疏的初始點代替原始算法隨機選取初始點，避免初始點選取不當造成的聚類誤差[13-14]，改進初始化的步驟如下.

(1) 從數據集M中隨機選取1個樣本點作為第1個初始點Z1，加入集合Z并從M中刪除.

(2) 計算更新后M中所有元素到Z1的距離，選取距離Z1最大的元素為Z2.

(3) 將Z2加入集合Z并從M中刪除.

(4) 分別計算更新后M中元素到Z中各個元素的距離，并存入距離矩陣DTemp中.

通過以上步驟可以完成最大最小距離積的初始化，得到的初始聚類中心避免了隨機初始化引起的初始誤差過大問題，有效減少聚類耗時.

3.2 混合迭代

KMC算法通過迭代求各個維度均值的方法獲得聚類中心，其不足在于更新方法過于簡單，容易陷入局部最優，導致優化精度過低.利用MTSFO的優化路徑替代KMC的優化路徑，實現MTSFO與KMC的混合迭代，擴大尋優范圍，避免陷入局部最優的同時提高搜索精度.實驗證明，此方法能較大提高算法優化效率，主程序流程圖如圖3所示，算法的基本步驟描述如下.

圖3 主程序流程圖Fig.3 Flow chart of main program

(1) 輸入數據集M，根據數據集類別的個數確定該數據集中類的個數k.

(2) 用最大最小距離積法初始化每個類的中心點.

(3) 計算數據集M中的每個樣本點到各個聚類中心的歐氏距離，按數值大小進行排序，將樣本點所屬類別歸于最小歐氏距離的聚類中心.

(4) 使用KMC算法確定每個樣本的類別.

(5) 在每個類別的魚群中通過MTSFO進行尋優操作，得到新的聚類中心.若新得到的聚類中心適應度優于上次迭代的聚類中心，用新的聚類中心代替歷史聚類中心.判斷當前迭代是否達到結束條件，若未達到結束條件則執行步驟 (4) ，否則循環結束，輸出尋優結果，結束程序.

4 實驗結果分析與應用

硬件實驗平臺為i5-6300HQ處理器、GTX-960顯卡、12 GB內存的計算機，軟件平臺為VS Code.

4.1 算法性能評價

為評價MTSFO-HIKMC的改進效果，將MTSFO-HIKMC與IMFO-KMC[7]、K-means++[15]和模糊C均值算法[16]應用到國際標準數據集Iris、Seeds、CMC和Wine中比較性能優劣.算法參數設置如下：每種聚類算法的最大迭代次數都取30次，旗魚魚群大小設置為30，旗魚與沙丁魚的數量比例設置為7∶3，模糊C均值聚類中的權重指數取2.0.Iris、Seeds、CMC和Wine這4種UCI國際通用測試數據庫中的數據集主要特征如表1所示.

表1 標準數據集特征Tab.1 Characteristics of standard data set

MTSFO-HIKMC改進方法分為初始化算法改進和搜索路徑優化.為體現不同改進思路對算法起到的作用，利用消融實驗分別對算法不同層面的改進進行測試，并與其他算法進行比較，以體現不同改進方法對算法產生的影響.

4.1.1實驗一：初始化改進效果評價 為評估最大最小距離積對算法起到的優化效果，采取消融實驗分別對初始化優化和搜索路徑優化進行實驗以驗證效果.圖4為本文使用的適應度函數來評價IMFO-KMC、K-means++、FCM和結合最大最小距離積的旗魚K均值混合迭代(SFO-HIKMC)算法的實驗結果.從損失衰減數據可知，最大最小距離積法在初始化聚類算法方面有較好的優勢，初始點的損失遠低于未經過初始化優化的FCM算法，使得優化算法節約起始階段的迭代次數，對聚類效率有較為明顯的提升.從圖4可知，適應度衰減曲線明顯沒有達到最優，尤其在對高維數據集CMC和Wine進行聚類時，最終適應度遠高于經典的FCM算法，聚類結果距離數據集最優解還有較遠的距離，分析原因是搜索路徑單一，聚類結果陷入局部最優導致.

圖4 實驗一中不同算法在4種數據集上的運行結果Fig.4 Running results of different algorithms on 4 data sets (Experiment 1)

4.1.2實驗二：搜索路徑改進效果評價 分析上述實驗結果可知，通過最大最小距離積改進的算法能夠在一個適應度較低的位置開始收斂，使算法能夠通過更少的迭代次數收斂到全局最優.但是容易陷入局部最優解，優化精度不足，這與算法本身的搜索路徑單一、沒有足夠能量沖出局部低洼地帶有關[17].在實驗一的基礎上通過自適應記憶傳遞優化算法對原始搜索路徑進行優化得到MTSFO-HIKMC 算法，并與其他幾種算法進行對比實驗，以驗證自適應記憶傳遞優化策略對聚類算法的優化效果.圖5所示為IMFO-KMC、K-means++、FCM和MTSFO-HIKMC算法對不同數據集進行聚類的適應度衰減曲線.由圖5可知，在實驗一已經陷入局部的SFO-HIKMC算法可以多次跳出局部最優，達到更高的聚類精度.

圖5 實驗二中不同算法在4種數據集上的運行結果Fig.5 Running results of different algorithms on 4 data sets (Experiment 2)

表2為搜索路徑改進前后的算法最終適應度.可知，改進后的算法相較于改進前的算法適應度均有大幅度下降，證明本文改進思路具有實用性.

表2 各類算法在不同數據集上的適應度Tab.2 Adaptability of different algorithms on different data sets

為更客觀評價MTSFO-HIKMC改進效果，采用Acc、ARI和NMI共3種評價指標對不同聚類算法進行評估[18-19].其中，Acc表示聚類的準確率，即比較聚類結果是否和真實結果的一致性；ARI為調整蘭德系數，用于衡量兩個數據分布的吻合程度，值越大表示計算結果與真實值更相似；NMI為歸一化互信息，用來表示兩組數據之間的關聯程度.

表3列出了3種算法實驗得到的評價指標，該數據由10次獨立實驗數據求均值得到.從表中可知，MTSFO-HIKMC在Iris數據集上測得的Acc指標和IMFO-KMC相等且高于K-means++和FCM算法.在Wine數據集測得Acc指標高于其他3種算法.在Seeds和Wine數據集中，MTSFO-HIKMC的ARI指標相較于其他算法均有不同程度提升.可見，MTSFO-HIKMC相較于另外3種算法，在聚類精確度和聚類結果與真實情況的吻合程度方面具有一定優勢.

表3 不同算法在4個數據集上的實驗結果Tab.3 Experimental results of different algorithms on 4 data sets

表4為4種算法在不同數據集單次迭代所需時間.其中，K-means++和FCM算法單次迭代時間優于MTSFO-HIKMC，而MTSFO-HIKMC消耗的時間成本相較于IMFO-KMC算法在4種測試數據集都有不同程度提升.在數據集CMC和Iris中，MTSFO-HIKMC的單次迭代時間相較于IMFO-KMC算法分別節省了7.82%和6.27%.可見，自適應記憶傳遞優化策略在提高搜索精度、增強全局搜索能力的同時，造成一定程度上時間成本的增加，但相較于收斂精度相似的IMFO-KMC算法，仍具有一定優勢.

表4 各類算法在不同數據集單次迭代時間Tab.4 Single iteration time of different algorithms in different data sets

分析上述實驗結果可知，KMC算法思路簡單、聚類精度低、初始聚類中心的隨機選取導致算法穩定性差；FCM算法中引入模糊控制的概念，使用模糊聚類算法，使得迭代曲線趨于平滑.但是仍舊存在初始點選取隨機性的問題，不僅增加了算法達到全局最優解的迭代次數，而且得到的聚類中心精度不高.IMFO-KMC受限于改進方法，收斂速度提高有限，相較于MTSFO-HIKMC需要更多次迭代去收斂才能達到足夠精度；而MTSFO-HIKMC通過最大最小距離積的初始化，減少了到達最優位置的迭代次數，實驗一和實驗二也證明了自適應記憶傳遞優化策略使得聚類算法具有較強的全局搜索能力，使聚類算法不易陷入局部最優解，穩定性較強.由表4可知，MTSFO-HIKMC單次迭代算法相較于類似算法具有一定的先進性.由此，可以得出以下結論：MTSFO-HIKMC聚類精度高于傳統K-means++算法和FCM算法，在高維數據聚類精度高于IMFO-KMC算法，而在低維數據聚類效果與IMFO-KMC算法接近.在迭代次數和單次迭代所花費的時間成本小于IMFO-KMC算法.本文改進算法具有一定的優越性，在預處理高維數據和實時性要求較高的場合具有較高的實用性.

4.2 測試函數上的性能指標

為了對MTSFO-HIKMC的收斂性有一個更加清晰、直觀的了解，分別采用Sphere、Ackley、Three-hump camel、Levy和Bukin函數對MTSFO-HIKMC算法進行測試，并繪制其收斂曲線以直觀反映其收斂性能.其中，Sphere和Ackley函數選擇在30個維度下進行收斂測試，以反映其高維適應能力，而Three-hump camel、Levy和Bukin這3個函數具有多個局部最優[20]，用以測試MTSFO-HIKMC算法跳出局部最優的能力.圖6為各收斂函數在三維可視化圖像.

圖6 測試函數Fig.6 Test function

圖7為MTSFO-HIKMC在5個測試函數迭代60次的收斂情況.可知，在多峰函數上優化算法較早脫離局部最優，在6次迭代完成均已收斂到全局最優；在高維情況下的表現也較好，在30維的Ackley函數上出現3次跳出局部最優的情況，最終收斂于全局最優.由此可知，MTSFO-HIKMC算法在全局尋優能力有較好的表現.

圖7 5類測試函數的運行結果Fig.7 Running results of 5 types of test functions

表5為MTSFO-HIKMC算法在5個測試函數上的收斂精度，數據為30次實驗取得的均值.其中，MTSFO-HIKMC在高維數據和多峰函數搜索精度較高，尤其是在具有多個局部最優解的Bukin函數上，搜索精度依然非常高.可知，自適應記憶傳遞優化策略針對跳出局部最優的性能較強.

表5 MTSFO-HIKMC在5類測試函數上的精度Tab.5 Accuracy of MTSFO-HIKMC on 5 types of test functions

5 結語

提出一種基于記憶傳遞旗魚優化的K均值混合迭代聚類方法.首先通過最大最小距離積進行初始化KMC，然后利用自適應記憶傳遞修正策略改進SFO算法，提升了全局尋優能力和搜索精度，減少了由于SFO初始化誤差較大造成的初始階段多余的迭代次數，最后設計了MTSFO算法與KMC算法的混合迭代，提高了聚類精度，加快了收斂速度，應用價值明顯.