飛蛾撲火優(yōu)化算法在聚類分析中的應(yīng)用

李志明

(廣西科技師范學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，廣西 來賓 546199)

0 引 言

聚類[1]是一種流行的數(shù)據(jù)分析和數(shù)據(jù)挖掘技術(shù)。聚類分析是一種無監(jiān)督的學(xué)習(xí)過程，它的任務(wù)是將類似的對象分組成多個類組。簡單的說，聚類分析問題的任務(wù)就是把一些對象按照某種規(guī)則分成不同的組，分組完成之后，每個組里面的對象具有較高的相似度，而不同組之間的對象具有較高的相異性。聚類算法是基于樣本之間距離或相似性的自動分類，且聚類技術(shù)已經(jīng)成功應(yīng)用于諸多實(shí)際的問題當(dāng)中，如數(shù)據(jù)挖掘[2]、模式識別[3]、圖像分割[4-5]等。分組聚類方法是指通過優(yōu)化某些標(biāo)準(zhǔn)將數(shù)據(jù)劃分成預(yù)定數(shù)量的簇。K-means是最流行的分組聚類方法[6-7]，不過K-means高度依賴于初始狀態(tài)，并且容易陷入局部最優(yōu)。

為了有效地解決聚類分析問題，國內(nèi)外一些學(xué)者嘗試用新興的群智能算法來求解這類問題。2011年，Hatamlou等采用了一個大爆炸算法進(jìn)行數(shù)據(jù)聚類[8]；2014年，陳信等提出一種改進(jìn)型猴群算法，并將其應(yīng)用到聚類分析中，取得了比K-means等更好的性能[9]；2015年，張森等將新型灰狼優(yōu)化算法應(yīng)用于聚類分析中，取得了良好的成績[10]；2016年，王睿將基于蜜蜂傳粉策略的花授粉算法用于求解聚類分析問題，均取得了很好的成績[11]；2019年，凌靜等提出結(jié)合模擬退火算法的K-means聚類方法，其聚類準(zhǔn)確性比一般K-means方法和遺傳K-means方法都要高[12]。

1 飛蛾撲火優(yōu)化算法

飛蛾撲火優(yōu)化算法(moth-flame optimization，MFO)是由學(xué)者M(jìn)irjalili于2015年提出的一種新型群智能優(yōu)化算法，其靈感來源于一種特殊的導(dǎo)航機(jī)制——橫向定位導(dǎo)航機(jī)制[13-14]。飛蛾在晚上飛行時(shí)，因其與月亮相距較遠(yuǎn)，所以飛蛾與月亮保持固定的角度即可保證自己沿直線飛行。

然而在現(xiàn)實(shí)中，飛蛾與火焰相距很近，當(dāng)飛蛾看到火焰發(fā)出的光時(shí)，便會試圖與其保持固定的角度飛行，而由于這些人造光相比月亮光距離很近，所以，飛蛾仍然保持與人造光的固定角度不變飛行時(shí)，飛蛾便會最終向人造光處收斂。

在MFO算法中飛蛾是候選解，飛蛾的集合用矩陣M表示，OM存儲相對應(yīng)的適應(yīng)度值。算法中另外一個核心組件火焰用F表示，OF存儲相對應(yīng)的適應(yīng)度值，并且矩陣M和F具有相同的維數(shù)。在MFO算法中，飛蛾或火焰都是解，它們的不同就在于每一次迭代過程中更新方式的不同。飛蛾在搜索空間里是實(shí)際的搜索主體，而火焰為當(dāng)前獲取的最佳位置。因此，每個飛蛾都會搜索一個火焰，在找到更好的解的情況下進(jìn)行標(biāo)記并更新，通過這種機(jī)制，飛蛾永遠(yuǎn)不會失去它的最優(yōu)解。

MFO算法用全局最佳的三元組表示如下：

MFO=(I,P,T)

(1)

通過函數(shù)I隨機(jī)產(chǎn)生一個飛蛾種群及相應(yīng)的適應(yīng)度值，其模型如下：

I:φ→{M,OM}

(2)

P是使飛蛾在搜索空間里移動的主函數(shù)，它接受矩陣M，并返回更新后的值。

P:M→M

(3)

當(dāng)滿足終止準(zhǔn)則時(shí)，T函數(shù)為真；如果不滿足，則T函數(shù)為假。

T:M→{true,false}

(4)

I函數(shù)初始化之后，P函數(shù)迭代運(yùn)行直到T函數(shù)返回真。為了精確地模擬飛蛾的行為，可使用下式對飛蛾相對于火焰的位置進(jìn)行更新。

Mi=S(Mi,Fj)

(5)

其中，Mi為第i只飛蛾，F(xiàn)j為第j個火焰，S為螺旋形函數(shù)。

選取對數(shù)螺旋線作為飛蛾的主要更新機(jī)制，其對數(shù)螺線描述如下：

S(Mi,Fj)=Di·ebt·cos(2πt)+Fj

(6)

其中，Di為第i個飛蛾與第j個火焰的距離，b為定義對數(shù)螺旋線形狀的常數(shù)，t為區(qū)間[-1，1]上的隨機(jī)數(shù)。其中D由式(7)計(jì)算求得。

Di=|Fj-Mi|

(7)

式(6)模擬了飛蛾的移動路徑，并可以確定飛蛾的下一個位置。參數(shù)t定義為飛蛾在下一個位置應(yīng)當(dāng)接近火焰的程度(t=-1是最接近火焰的位置，t=1為距離火焰最遠(yuǎn)的位置)。在式(6)中僅僅需要飛蛾朝向火焰移動，卻也容易使MFO算法陷入局部最優(yōu)。為了避免這種情況，每個飛蛾必須使用式(6)中的火焰來更新它們的位置。每次更新火焰列表后，火焰便會根據(jù)它們的適應(yīng)度值來排序，然后飛蛾更新它們相對于相應(yīng)火焰的位置。第一只飛蛾總是更新相對于最優(yōu)火焰的位置，而最后一只飛蛾更新列表中相對于最差火焰的位置。

針對在搜索空間中相對于n個不同位置飛蛾的位置更新，有可能降低了最有希望解的開采，提出一種適合于火焰數(shù)量的自適應(yīng)機(jī)制。使用式(8)使火焰數(shù)量在迭代過程中自適應(yīng)減少：

(8)

其中，l為當(dāng)前迭代次數(shù)，N為火焰數(shù)量的最大值，T為最大迭代次數(shù)。

2 基于單純形法的飛蛾撲火優(yōu)化算法流程

單純形法又稱為可變多面體搜索法，它具有計(jì)算量小、搜索速度快等優(yōu)點(diǎn)，是一種傳統(tǒng)的處理無約束最優(yōu)化問題的方法。在標(biāo)準(zhǔn)飛蛾撲火優(yōu)化算法的基礎(chǔ)上使用單純形法搜索策略，可以增強(qiáng)算法的種群多樣性，使算法尋找到更好的位置。SMMFO算法的簡易流程如下：

Initialize the position of moths

While(Iteration<=Max_iteration)

Update flame no using Eq.(8)

OM=FitnessFunction(M);

if iteration==1

F=sort(M);

OF=sort(OM);

else

F=sort(Mt-1,Mt);

OF=sort(Mt-1,Mt);

end

for i = 1:n

for j=1:d

Update r and t

Calculate D using Eq.(7) with respect to the corresponding moth

Update M(i,j) using Eqs.(5) and (6) with respect to the corresponding moth

end

for each search agent

Update the position of the current search agent using Simplex Method

end

end

3 仿真實(shí)驗(yàn)

3.1 仿真環(huán)境

為了驗(yàn)證SMMFO在解決聚類分析問題上的有效性，選取了8個常見的數(shù)據(jù)集，其中包括2個人工數(shù)據(jù)集和6個現(xiàn)實(shí)數(shù)據(jù)集[11]。

8個數(shù)據(jù)集描述如下(數(shù)據(jù)集中數(shù)據(jù)項(xiàng)個數(shù)為N，每條數(shù)據(jù)的屬性數(shù)為d，數(shù)據(jù)集要分類的數(shù)目為K)。人工數(shù)據(jù)集1(N=250，d=3，K=5)中的每個屬性值都服從均勻分布，即分別服從(85,100)、(70,85)、(55,70)、(40,55)和(25,40)上的均勻分布。人工數(shù)據(jù)集2(N=600，d=2，K=4)，其中的600條數(shù)據(jù)項(xiàng)中的屬性值均服從二維隨機(jī)分布。Iris數(shù)據(jù)集(N=150，d=4，K=3)來自于150個隨機(jī)樣本，每條數(shù)據(jù)由四個屬性構(gòu)成。Wine數(shù)據(jù)集(N=178，d=13，K=3)取自于對意大利相同地區(qū)的三種不同品種的酒進(jìn)行化學(xué)分析，共有178條數(shù)據(jù)項(xiàng)，每個數(shù)據(jù)項(xiàng)有13個屬性。Seeds數(shù)據(jù)集(N=210，d=7，K=3)，共有210個數(shù)據(jù)項(xiàng)，每項(xiàng)數(shù)據(jù)包含7個屬性，并且可分為3類，每類各含有70條數(shù)據(jù)集。Heart數(shù)據(jù)集(N=270，d=13，K=2)包含270個數(shù)據(jù)項(xiàng)，每個數(shù)據(jù)項(xiàng)包含13個屬性，該Heart數(shù)據(jù)集來源于心臟病數(shù)據(jù)庫，不過采用了不同的表達(dá)形式。Balance Scale數(shù)據(jù)集(N=625，d=4，K=3)根據(jù)平衡性分為向左傾斜、向右傾斜和平衡居中3類，每條數(shù)據(jù)項(xiàng)有l(wèi)eft weight，left distance，right weight，right distance等4個屬性，根據(jù)兩個比重left weight×left distance和right weight×right distance的大小對數(shù)據(jù)項(xiàng)進(jìn)行分類，若前者大，則該數(shù)據(jù)項(xiàng)為向左傾斜，若后者大，數(shù)據(jù)項(xiàng)為向右傾斜，否則數(shù)據(jù)項(xiàng)被歸到平衡居中里。Contraceptive Method Choice (CMC)數(shù)據(jù)集(N=1 473，d=10，K=3)為避孕方法選擇集，該數(shù)據(jù)集源自于1987年印度尼西亞進(jìn)行的全國避孕患病率調(diào)查的一個樣本，目的是預(yù)測當(dāng)前的避孕方法是無效的、短期有效的還是長期有效的。

以上8個數(shù)據(jù)集均有自己的特點(diǎn)，因此，對它們的實(shí)驗(yàn)結(jié)果數(shù)據(jù)能充分反映算法的性能。另外，還選取了PSO[15]、ABC[16]、GGSA[17]、CS[18]等算法作為比較算法。

3.2 實(shí)驗(yàn)結(jié)果與分析

各實(shí)驗(yàn)結(jié)果如表1～表8所示，記錄了每個算法取得的最優(yōu)值、最差值、平均值、標(biāo)準(zhǔn)差。從各表可以看出，在求解這8個測試集時(shí)，SMMFO均表現(xiàn)出了較好的性能。

表1 人工數(shù)據(jù)集1的20次獨(dú)立運(yùn)行實(shí)驗(yàn)結(jié)果

表2 人工數(shù)據(jù)集2的20次獨(dú)立運(yùn)行實(shí)驗(yàn)結(jié)果

表3 Iris數(shù)據(jù)集的20次獨(dú)立運(yùn)行實(shí)驗(yàn)結(jié)果

表4 Wine數(shù)據(jù)集的20次獨(dú)立運(yùn)行實(shí)驗(yàn)結(jié)果

表5 Seeds數(shù)據(jù)集的20次獨(dú)立運(yùn)行實(shí)驗(yàn)結(jié)果

表6 Heart數(shù)據(jù)集的20次獨(dú)立運(yùn)行實(shí)驗(yàn)結(jié)果

表7 Balance Scale數(shù)據(jù)集的20次獨(dú)立運(yùn)行實(shí)驗(yàn)結(jié)果

表8 CMC數(shù)據(jù)集的20次獨(dú)立運(yùn)行實(shí)驗(yàn)結(jié)果

由表1可知，對于人工數(shù)據(jù)集1，SMMFO所取得的平均值為1 985.13，僅次于CS的185.017，而且SMMFO的最優(yōu)值是148.254，均優(yōu)于其他算法。同樣在人工數(shù)據(jù)集2中，SMMFO與PSO，GGSA均取得了513.903 5的較好成績，而且其標(biāo)準(zhǔn)差也是比較小的。對于Iris測試集，由表3可知SMMFO在最優(yōu)值、最差值和平均值方面都是96.655 48，而且標(biāo)準(zhǔn)差達(dá)到了9.392 8e-10，這表明改進(jìn)型SMMFO具有較強(qiáng)的魯棒性，雖然PSO與GGSA給出的最優(yōu)解也達(dá)到了和SMMFO一樣的成績，但是SMMFO在最差值、平均值和標(biāo)準(zhǔn)差方面均優(yōu)于PSO與GGSA。表4給出了Wine測試集的結(jié)果，其中SMMFO取得的最優(yōu)值、最差值、平均值和標(biāo)準(zhǔn)差分別是16 292.18，16 294.17，16 292.92和0.843 7，這比PSO、ABC、GGSA、CS、MFO和K-means得出的結(jié)果都要優(yōu)秀。對于Seeds測試集，SMMFO的最優(yōu)值、最差值、平均值均取得了311.121 1這個不錯的成績，而且其標(biāo)準(zhǔn)差為2.1e-11，這是比其他算法都要優(yōu)秀的，雖然GGSA在最優(yōu)值方面也取得了311.121 1，但是在其他方面卻要比SMMFO遜色很多。對于Heart測試集，SMMFO取得的最優(yōu)值、最差值和平均值分別為10 622.98，10 623.18，10 623.00，這樣的結(jié)果比其他算法都要好，在標(biāo)準(zhǔn)差方面，SMMFO的標(biāo)準(zhǔn)差為0.061 56，在這些算法中也是最優(yōu)秀的。對于Balance Scale測試集，SMMFO所得到的最優(yōu)值和平均值分別是1 423.820和1 424.354，這兩個結(jié)果是要優(yōu)于其他算法的，并且SMMFO取得的標(biāo)準(zhǔn)差也是小于其他算法的。對于測試集Contraceptive Method Choice (CMC)，SMMFO得到的最優(yōu)值、最差值和平均值均為523.54，這一結(jié)果是優(yōu)于其他算法的，而且其標(biāo)準(zhǔn)差達(dá)到了6.04e-12，這個結(jié)果更是比其他算法要優(yōu)秀很多。通過以上數(shù)據(jù)分析可知，改進(jìn)型SMMFO算法具有較強(qiáng)的搜索能力，并且在聚類分析方面是具有優(yōu)勢的。

圖1是SMMFO算法對人工數(shù)據(jù)集2的聚類結(jié)果，從圖中可以看出，新算法取得了比較理想的成績。

圖1 人工數(shù)據(jù)集2聚類結(jié)果

4 結(jié)束語

針對飛蛾撲火優(yōu)化算法容易陷入局部最優(yōu)及由種群多樣性低導(dǎo)致的全局尋優(yōu)能力不足等缺陷，提出了基于單純形法的飛蛾撲火優(yōu)化算法，即在飛蛾撲火優(yōu)化算法的基礎(chǔ)上，加入了一種經(jīng)典的傳統(tǒng)優(yōu)化方法——單純形法。改進(jìn)后的SMMFO算法不僅了提高了種群多樣性，而且加強(qiáng)了算法的局部搜索能力，并使其收斂速度大大加快。通過與其他六個算法的對比實(shí)驗(yàn)可知，SMMFO不僅在全局搜索方面表現(xiàn)不俗，更是在局部搜索方面表現(xiàn)出了良好的性能，所以，改進(jìn)型SMMFO是一種非常有效和實(shí)用的方法。