黃 鶴， 熊 武， 吳 琨， 王會(huì)峰， 茹 鋒， 王 珺

(長(zhǎng)安大學(xué) a. 西安市智慧高速公路信息融合與控制重點(diǎn)實(shí)驗(yàn)室;b. 電子與控制工程學(xué)院， 西安 710064)

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

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

1 KMC算法的不足

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

從聚類(lèi)過(guò)程可知，初始聚類(lèi)中心選擇不當(dāng)會(huì)陷入局部最優(yōu).聚類(lèi)中心Cj的計(jì)算公式為

(1)

聚類(lèi)中心Cj與樣本數(shù)據(jù)xi的歐氏距離計(jì)算為

(2)

式中：d為聚類(lèi)中心個(gè)數(shù).

因此，KMC的初始化具有隨機(jī)性，可能會(huì)將噪聲或異值作為初始中心，導(dǎo)致每次聚類(lèi)結(jié)果相差較大，算法魯棒性較差[10].同時(shí)，簡(jiǎn)單的更新過(guò)程會(huì)導(dǎo)致KMC陷入局部最優(yōu).

2 MTSFO算法

2.1 SFO算法

2.1.1初始化 SFO的初始化是在給定的搜索空間內(nèi)隨機(jī)初始化，包括旗魚(yú)和沙丁魚(yú)的初始化.旗魚(yú)種群和沙丁魚(yú)種群分別用XSF和XF表示.XBSF和XBS是初始化后適應(yīng)度值最好的旗魚(yú)和沙丁魚(yú)個(gè)體.在一個(gè)搜索空間內(nèi)，隨機(jī)初始化沙丁魚(yú)和旗魚(yú)的比例可以根據(jù)數(shù)據(jù)集的選擇進(jìn)行一定程度的調(diào)整，并按照優(yōu)化函數(shù)進(jìn)行適應(yīng)度排序，得到最優(yōu)種群.

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

(3)

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

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

(4)

式中：fsfp為第p只旗魚(yú)的適應(yīng)度值.

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

(5)

式中：sq為第q只沙丁魚(yú)的適應(yīng)度值.FSF和FS矩陣為兩種魚(yú)群適應(yīng)度排序之后的結(jié)果，這說(shuō)明沙丁魚(yú)s1是魚(yú)群M在當(dāng)前迭代搜索中的最優(yōu)解.

2.1.2旗魚(yú)位置更新機(jī)制 更新機(jī)制主要可分為旗魚(yú)的追捕過(guò)程和沙丁魚(yú)的逃脫引起的位置更新.

(1) 圍獵追捕過(guò)程.設(shè)適應(yīng)度最好的個(gè)體為頭魚(yú)，旗魚(yú)依據(jù)旗魚(yú)頭魚(yú)和沙丁魚(yú)頭魚(yú)位置進(jìn)行空間位置更新，向兩種頭魚(yú)漸進(jìn)靠攏，聽(tīng)從頭魚(yú)指揮不斷更新位置.定義旗魚(yú)位置更新機(jī)制為

XNSFi=XBSFi-λi×

(6)

式中：XNSFi為更新后的旗魚(yú)位置；λi為每次更新的步長(zhǎng)大??；XBSFi為當(dāng)前迭代i次時(shí)旗魚(yú)頭魚(yú)的位置；XBSi為當(dāng)前迭代i次時(shí)沙丁魚(yú)頭魚(yú)的位置；XOSFi為上次迭代時(shí)的旗魚(yú)位置.步長(zhǎng)定義為

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

(7)

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

(8)

式中：NSF和NS分別為旗魚(yú)和沙丁魚(yú)的數(shù)量.

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

XNSi=r(XBSFi-XOSi+AP)

(9)

式中：XNSi為更新后的沙丁魚(yú)位置；r為步長(zhǎng)系數(shù)；XOSi為在當(dāng)前迭代次數(shù)時(shí)沙丁魚(yú)的最佳位置；AP為旗魚(yú)的攻擊力度，計(jì)算方式為

AP=A(1-2ie)

(10)

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

α=NSAP

(11)

β=dAP

(12)

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

SFO算法流程如下.

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

(2) 計(jì)算旗魚(yú)和沙丁魚(yú)的適應(yīng)度值，并記錄最優(yōu)適應(yīng)度值和位置.

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

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

(5) 計(jì)算所有適應(yīng)度值，并更新記錄最優(yōu)適應(yīng)度值和位置.

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

2.2 改進(jìn)算法

SFO受限于線性的搜索路徑，因此搜索精度有限[6].借鑒生物繁衍進(jìn)化的基本邏輯，提出一種基于記憶傳遞旗魚(yú)優(yōu)化算法，設(shè)計(jì)自適應(yīng)記憶傳遞修正策略?xún)?yōu)化SFO的搜索路徑，以加快其收斂速度，提高聚類(lèi)精度.

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

(1) 確定記憶傳遞算子產(chǎn)生的子代魚(yú)苗的數(shù)量和魚(yú)苗群的半徑，表達(dá)式為

(13)

(14)

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

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

魚(yú)苗個(gè)數(shù)取決于父代旗魚(yú)個(gè)體基因?qū)Νh(huán)境的適應(yīng)性，對(duì)環(huán)境適應(yīng)更好的個(gè)體產(chǎn)生更多的子代個(gè)體.魚(yú)苗位置在空間上服從均勻分布，記憶傳遞規(guī)則定義為

(15)

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

(16)

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

圖2 改進(jìn)旗魚(yú)算法流程圖Fig.2 Flow chart of improved sailfish algorithm

MTSFO算法偽代碼：

輸入: 數(shù)據(jù)集、聚類(lèi)數(shù)目

輸出：聚類(lèi)中心、分類(lèi)結(jié)果、適應(yīng)度值

初始化參數(shù)

While 不滿(mǎn)足終止條件

更新沙丁魚(yú)群和旗魚(yú)魚(yú)群

判斷魚(yú)群超出邊界:

將樣本邊界外的值設(shè)置為邊界值.

結(jié)束判斷

旗魚(yú)遍歷

計(jì)算適應(yīng)度值

結(jié)束遍歷

沙丁魚(yú)遍歷

計(jì)算適應(yīng)度值

結(jié)束遍歷

按照適應(yīng)度值對(duì)旗魚(yú)和沙丁魚(yú)進(jìn)行排序

XBSF= 最優(yōu)適應(yīng)度旗魚(yú)

XBS= 最優(yōu)適應(yīng)度沙丁魚(yú)

更新旗魚(yú)位置

更新沙丁魚(yú)位置

Bp=XBSF

用過(guò)適應(yīng)度值計(jì)算S和A1的值

While 迭代次數(shù)小于S

根據(jù)Bp的位置產(chǎn)生旗魚(yú)后代.

判斷后代個(gè)體的適應(yīng)度值優(yōu)于Bp

由相應(yīng)后代個(gè)體取代Bp的位置.

結(jié)束判斷

End while

End while

輸出：聚類(lèi)中心、分類(lèi)結(jié)果、適應(yīng)度值

2.2.2適應(yīng)度函數(shù)選擇 適應(yīng)度函數(shù)決定了優(yōu)化群體進(jìn)化的方向，直接影響種群算法的優(yōu)化效果和解的質(zhì)量[11-12].為使MTSFO更好地優(yōu)化聚類(lèi)中心，提升聚類(lèi)效果，本文采用的適應(yīng)度函數(shù)為文獻(xiàn)[7]采用的適應(yīng)度函數(shù)的變體形式，不再以某一類(lèi)適應(yīng)度作為評(píng)價(jià)指標(biāo)，采用不同簇內(nèi)適應(yīng)度總和作為全局適應(yīng)度去指導(dǎo)算法收斂，適應(yīng)度函數(shù)為

(17)

(18)

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

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

3.1 最大最小距離積優(yōu)化

采用最大最小距離積方法對(duì)KMC進(jìn)行優(yōu)化，選取密度較大且分布較稀疏的初始點(diǎn)代替原始算法隨機(jī)選取初始點(diǎn)，避免初始點(diǎn)選取不當(dāng)造成的聚類(lèi)誤差[13-14]，改進(jìn)初始化的步驟如下.

(1) 從數(shù)據(jù)集M中隨機(jī)選取1個(gè)樣本點(diǎn)作為第1個(gè)初始點(diǎn)Z1，加入集合Z并從M中刪除.

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

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

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

通過(guò)以上步驟可以完成最大最小距離積的初始化，得到的初始聚類(lèi)中心避免了隨機(jī)初始化引起的初始誤差過(guò)大問(wèn)題，有效減少聚類(lèi)耗時(shí).

3.2 混合迭代

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

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

(1) 輸入數(shù)據(jù)集M，根據(jù)數(shù)據(jù)集類(lèi)別的個(gè)數(shù)確定該數(shù)據(jù)集中類(lèi)的個(gè)數(shù)k.

(2) 用最大最小距離積法初始化每個(gè)類(lèi)的中心點(diǎn).

(3) 計(jì)算數(shù)據(jù)集M中的每個(gè)樣本點(diǎn)到各個(gè)聚類(lèi)中心的歐氏距離，按數(shù)值大小進(jìn)行排序，將樣本點(diǎn)所屬類(lèi)別歸于最小歐氏距離的聚類(lèi)中心.

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

(5) 在每個(gè)類(lèi)別的魚(yú)群中通過(guò)MTSFO進(jìn)行尋優(yōu)操作，得到新的聚類(lèi)中心.若新得到的聚類(lèi)中心適應(yīng)度優(yōu)于上次迭代的聚類(lèi)中心，用新的聚類(lèi)中心代替歷史聚類(lèi)中心.判斷當(dāng)前迭代是否達(dá)到結(jié)束條件，若未達(dá)到結(jié)束條件則執(zhí)行步驟 (4) ，否則循環(huán)結(jié)束，輸出尋優(yōu)結(jié)果，結(jié)束程序.

4 實(shí)驗(yàn)結(jié)果分析與應(yīng)用

硬件實(shí)驗(yàn)平臺(tái)為i5-6300HQ處理器、GTX-960顯卡、12 GB內(nèi)存的計(jì)算機(jī)，軟件平臺(tái)為VS Code.

4.1 算法性能評(píng)價(jià)

為評(píng)價(jià)MTSFO-HIKMC的改進(jìn)效果，將MTSFO-HIKMC與IMFO-KMC[7]、K-means++[15]和模糊C均值算法[16]應(yīng)用到國(guó)際標(biāo)準(zhǔn)數(shù)據(jù)集Iris、Seeds、CMC和Wine中比較性能優(yōu)劣.算法參數(shù)設(shè)置如下：每種聚類(lèi)算法的最大迭代次數(shù)都取30次，旗魚(yú)魚(yú)群大小設(shè)置為30，旗魚(yú)與沙丁魚(yú)的數(shù)量比例設(shè)置為7∶3，模糊C均值聚類(lèi)中的權(quán)重指數(shù)取2.0.Iris、Seeds、CMC和Wine這4種UCI國(guó)際通用測(cè)試數(shù)據(jù)庫(kù)中的數(shù)據(jù)集主要特征如表1所示.

表1 標(biāo)準(zhǔn)數(shù)據(jù)集特征Tab.1 Characteristics of standard data set

MTSFO-HIKMC改進(jìn)方法分為初始化算法改進(jìn)和搜索路徑優(yōu)化.為體現(xiàn)不同改進(jìn)思路對(duì)算法起到的作用，利用消融實(shí)驗(yàn)分別對(duì)算法不同層面的改進(jìn)進(jìn)行測(cè)試，并與其他算法進(jìn)行比較，以體現(xiàn)不同改進(jìn)方法對(duì)算法產(chǎn)生的影響.

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

圖4 實(shí)驗(yàn)一中不同算法在4種數(shù)據(jù)集上的運(yùn)行結(jié)果Fig.4 Running results of different algorithms on 4 data sets (Experiment 1)

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

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

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

表2 各類(lèi)算法在不同數(shù)據(jù)集上的適應(yīng)度Tab.2 Adaptability of different algorithms on different data sets

為更客觀評(píng)價(jià)MTSFO-HIKMC改進(jìn)效果，采用Acc、ARI和NMI共3種評(píng)價(jià)指標(biāo)對(duì)不同聚類(lèi)算法進(jìn)行評(píng)估[18-19].其中，Acc表示聚類(lèi)的準(zhǔn)確率，即比較聚類(lèi)結(jié)果是否和真實(shí)結(jié)果的一致性；ARI為調(diào)整蘭德系數(shù)，用于衡量?jī)蓚€(gè)數(shù)據(jù)分布的吻合程度，值越大表示計(jì)算結(jié)果與真實(shí)值更相似；NMI為歸一化互信息，用來(lái)表示兩組數(shù)據(jù)之間的關(guān)聯(lián)程度.

表3列出了3種算法實(shí)驗(yàn)得到的評(píng)價(jià)指標(biāo)，該數(shù)據(jù)由10次獨(dú)立實(shí)驗(yàn)數(shù)據(jù)求均值得到.從表中可知，MTSFO-HIKMC在Iris數(shù)據(jù)集上測(cè)得的Acc指標(biāo)和IMFO-KMC相等且高于K-means++和FCM算法.在Wine數(shù)據(jù)集測(cè)得Acc指標(biāo)高于其他3種算法.在Seeds和Wine數(shù)據(jù)集中，MTSFO-HIKMC的ARI指標(biāo)相較于其他算法均有不同程度提升.可見(jiàn)，MTSFO-HIKMC相較于另外3種算法，在聚類(lèi)精確度和聚類(lèi)結(jié)果與真實(shí)情況的吻合程度方面具有一定優(yōu)勢(shì).

表3 不同算法在4個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Tab.3 Experimental results of different algorithms on 4 data sets

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

表4 各類(lèi)算法在不同數(shù)據(jù)集單次迭代時(shí)間Tab.4 Single iteration time of different algorithms in different data sets

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

4.2 測(cè)試函數(shù)上的性能指標(biāo)

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

圖6 測(cè)試函數(shù)Fig.6 Test function

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

圖7 5類(lèi)測(cè)試函數(shù)的運(yùn)行結(jié)果Fig.7 Running results of 5 types of test functions

表5為MTSFO-HIKMC算法在5個(gè)測(cè)試函數(shù)上的收斂精度，數(shù)據(jù)為30次實(shí)驗(yàn)取得的均值.其中，MTSFO-HIKMC在高維數(shù)據(jù)和多峰函數(shù)搜索精度較高，尤其是在具有多個(gè)局部最優(yōu)解的Bukin函數(shù)上，搜索精度依然非常高.可知，自適應(yīng)記憶傳遞優(yōu)化策略針對(duì)跳出局部最優(yōu)的性能較強(qiáng).

表5 MTSFO-HIKMC在5類(lèi)測(cè)試函數(shù)上的精度Tab.5 Accuracy of MTSFO-HIKMC on 5 types of test functions

5 結(jié)語(yǔ)

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