郭 璐，許 哲，黃 鶴，張少帥，陳永安

（1.西北工業(yè)大學(xué)無人機(jī)系統(tǒng)國家工程研究中心，西安 710072；2.西安愛生技術(shù)集團(tuán)公司，西安 710065；3.中國電子科技集團(tuán)公司第二十研究所，西安 710068；4.長安大學(xué)電子與控制工程學(xué)院，西安 710064）

0 引言

聚類分析是統(tǒng)計(jì)學(xué)習(xí)領(lǐng)域的重要組成部分，可以針對不同的對象分析差異，并且能夠根據(jù)某種特定的規(guī)則進(jìn)行模式分類。聚類的應(yīng)用廣泛，擁有很好的發(fā)展前景。隨著社會(huì)發(fā)展對數(shù)據(jù)精度要求的不斷提高，如何提高算法的聚類精度是廣大學(xué)者一直以來的研究熱點(diǎn)［1］。經(jīng)典K-means 聚類（K-means Clustering，KMC）算法存在易受初始聚類中心和異常數(shù)據(jù)影響的缺陷［2］，研究人員提出利用特征關(guān)聯(lián)度對傳統(tǒng)K-means 算法的初始聚類中心進(jìn)行優(yōu)化［3］和基于自適應(yīng)權(quán)重的聚類算法［4］。

群智能優(yōu)化算法作為新興的演化計(jì)算技術(shù)取得了高速發(fā)展。2015 年Mirjalili 根據(jù)飛蛾總是圍繞火焰做對數(shù)螺旋曲線軌跡的行為提出了一種飛蛾捕焰算法（Moth-flame Optimization，MFO）［5-6］。目前，MFO 算法已經(jīng)在網(wǎng)絡(luò)［7］、電力［8］、以及加工制造［9］等方面有了具體的應(yīng)用，并在此基礎(chǔ)上結(jié)合其他算法進(jìn)行了設(shè)計(jì)。文獻(xiàn)［10］將粒子群優(yōu)化算法的速度更新方式與MFO 算法的位置更新方式相結(jié)合，使飛蛾群向歷史最優(yōu)解和全局最優(yōu)解快速收斂，避免了陷入局部最優(yōu)解的目的。文獻(xiàn)［11］將MFO 算法位置更新的方式和Lévy 飛行搜索策略結(jié)合，達(dá)到增強(qiáng)局部搜索能力的目的，使得收斂速度和求解精度大幅度提高。文獻(xiàn)［12］提出了一種縱橫交叉混沌捕焰優(yōu)化算法，采用縱橫交叉機(jī)制，將火焰之間以及火焰不同維度之間相互結(jié)合，同時(shí)引入混沌算子，進(jìn)一步提高了算法精確度和跳出局部最優(yōu)能力［10］。目前，針對MFO 算法本身改進(jìn)的文獻(xiàn)并不多，MFO算法的收斂速度和精度并沒有充分得到提升。同時(shí)，MFO 算法得自身特點(diǎn)非常適用于聚類，可以使求解的聚類中心更加精確，但目前并沒有研究者將MFO 算法設(shè)計(jì)在聚類的應(yīng)用中。

因此，本文提出一種快速的飛蛾捕焰（Rapid Moth-flame Optimization，RMFO）算法，解決了經(jīng)典MFO 算法求解復(fù)雜函數(shù)時(shí)收斂速度慢與精度較低等問題。同時(shí)，設(shè)計(jì)了一種基于改進(jìn)飛蛾捕焰算法的K 均值交叉迭代聚類方法，提升MFO 算法的全局收斂能力和收斂速度，并且能夠改善聚類性能。

1 飛蛾捕焰優(yōu)化算法

MFO 算法是根據(jù)飛蛾圍繞火焰做對數(shù)螺旋曲線運(yùn)動(dòng)的生物學(xué)原理構(gòu)建數(shù)學(xué)模型，經(jīng)過多次位置更新迭代之后求解得到最優(yōu)火焰解。在飛蛾捕焰優(yōu)化算法中，矩陣M 表示飛蛾（Moth）的集合，矩陣F表示火焰（Flame）的集合。與之對應(yīng)的是，矩陣OM表示飛蛾集合M 的適應(yīng)度值，矩陣OF 表示火焰集合F 的適應(yīng)度值。飛蛾和火焰都是算法的解，不同的是飛蛾是在搜索空間中的實(shí)際搜索的主體，而火焰則是用來存儲(chǔ)飛蛾搜索的最優(yōu)解［13］。

1.1 初始化種群

設(shè)飛蛾種群集合M 的大小為n×d，如式（1）所示，n 表示飛蛾總數(shù)，d 表示一個(gè)樣本的特征數(shù)或是待尋優(yōu)變量的個(gè)數(shù)（維度）。

其中，Mi=［mi1，mi2，…，mid］代表的是第i 只（i=1，2，…，n）飛蛾的狀態(tài)，Mij代表的是第i 只飛蛾在第j（j=1，2，…，d）維變量空間中所處的位置。

飛蛾的適應(yīng)度值OM 的大小為n×1，如式（2）所示。

其中，OMi=［omi］表示第i 只（i=1，2，…，n）飛蛾的適應(yīng)度值，是由Mi通過相應(yīng)的適應(yīng)度函數(shù)（尋優(yōu)目標(biāo)函數(shù)）得到的。

設(shè)火焰集合F 的大小與飛蛾M 的大小相同，為n×d。如式（3）所示。

其中，F(xiàn)i=［fi1，fi2，…，fid］表示第i 個(gè)（i=1，2，…，n）火焰的狀態(tài)，F(xiàn)ij表示第i 個(gè)火焰在第j（j=1，2，…，d）維變量空間中所處的位置。

火焰的適應(yīng)度值OF 的大小同樣為n×1，如式（4）所示。

其中，OFi=［ofi］表示第i（i=1，2，…，n）個(gè)火焰的適應(yīng)度值。OF 矩陣是OM 矩陣中每個(gè)量排序之后的結(jié)果，所以F 矩陣是M 矩陣根據(jù)OF 矩陣的排序得到的結(jié)果，這說明火焰F 是飛蛾M 在當(dāng)前迭代搜索中的最優(yōu)解。

1.2 捕焰過程

飛蛾在圍繞火焰做對數(shù)螺旋曲線運(yùn)動(dòng)時(shí)的位置更新機(jī)制可以分為兩個(gè)過程：飛蛾捕焰、飛蛾棄焰。

1）飛蛾捕焰：飛蛾Mi在搜索空間中尋找火焰的位置時(shí)，飛蛾會(huì)根據(jù)自己的趨光生物特性來尋找與它距離最近的火焰Fi，然后在每一次的位置更新迭代中圍繞火焰做對數(shù)螺旋曲線運(yùn)動(dòng)，如圖1 所示，螺旋線的起點(diǎn)為飛蛾初始化位置，螺旋線的終點(diǎn)即為最優(yōu)解。

圖1 飛蛾運(yùn)動(dòng)軌跡圖

定義對數(shù)螺旋曲線如式（5）所示：

2）飛蛾棄焰：為了提高算法尋優(yōu)的收斂速度并且使得所有的飛蛾盡可能收斂于一個(gè)最優(yōu)火焰解中，所以應(yīng)該使火焰的數(shù)目自適應(yīng)地減少，讓飛蛾舍棄適應(yīng)度值差的火焰。這樣也可以避免飛蛾丟失最優(yōu)解的情況?；鹧孀赃m應(yīng)減少如式（6）所示：

其中，flameno 為當(dāng)前火焰的數(shù)量，N 為飛蛾種群的總數(shù)量，l 為當(dāng)前的迭代次數(shù)，T 為規(guī)定的最大迭代次數(shù)。

2 K 均值聚類算法

K 均值聚類的目的是將給定的數(shù)據(jù)集X={X1，X2，…，Xn}劃分成K 個(gè)類的子集{C1，C2，…，Ck}，執(zhí)行過程中初始聚類中心的選取很重要，直接影響聚類的結(jié)果，導(dǎo)致結(jié)果陷入局部最優(yōu)解。聚類中心Cj的計(jì)算式如式（7）所示：

3 改進(jìn)的飛蛾捕焰算法

本文針對經(jīng)典MFO 算法的不足，提出了一種RMFO 算法，分別將飛蛾種群的初始化和飛蛾的適應(yīng)度函數(shù)進(jìn)行改進(jìn)，通過設(shè)計(jì)最大最小距離積法初始化飛蛾種群，可以克服原始飛蛾捕焰算法初始化的隨機(jī)性，避免算法陷入局部最優(yōu)解。同時(shí)，結(jié)合飛蛾捕焰迭代搜索過程以及KMC 算法思想，提出一種新的適應(yīng)度函數(shù)。

3.1 最大最小距離積法初始化

飛蛾捕焰算法的搜索起點(diǎn)是飛蛾群的初始位置，所以選取尤為重要。經(jīng)典飛蛾捕焰算法的初始飛蛾群采用隨機(jī)初始化易導(dǎo)致算法陷入局部最優(yōu)解。同時(shí)，飛蛾種群的個(gè)體解往往會(huì)遠(yuǎn)離最優(yōu)解，使得算法收斂速度變慢，收斂效率變低，增加了算法的時(shí)間復(fù)雜度。針對這一問題，本文設(shè)計(jì)了最大最小距離積法對飛蛾群進(jìn)行初始化，不僅可以解決飛蛾群初始化的隨機(jī)性，而且也可以在K 均值聚類中降低對初始點(diǎn)的敏感性。通過最大最小距離積法得到k 個(gè)初始飛蛾的步驟描述如下：

1）從飛蛾種群集合M 中隨機(jī)選取一只飛蛾作為第一個(gè)初始點(diǎn)Z1，將其加入集合Z 并從集合M 中刪除；

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

3）將Z2加入集合Z 并從集合M 中刪除；

4）分別計(jì)算更新后M 中元素到Z 中各個(gè)元素的距離并存入Temp 中；

5）計(jì)算M 中每個(gè)元素對應(yīng)的Temp 的最大值與最小值的乘積，取該值最大對應(yīng)的元素存入集合Z 中并從集合M 中刪除。若Z 中元素個(gè)數(shù)小于k，則轉(zhuǎn)到步驟3；若Z 中元素個(gè)數(shù)大于k，則初始點(diǎn)選取結(jié)束，輸出包含k 個(gè)初始點(diǎn)的集合Z，即為得到的初始點(diǎn)。

其中，k 是規(guī)定的聚類個(gè)數(shù)或是給定的初始點(diǎn)個(gè)數(shù)，Z 初始時(shí)是空集，存儲(chǔ)等待加入的k 個(gè)初始點(diǎn)的集合，Temp 是存儲(chǔ)Z 中各個(gè)元素到M 中各個(gè)元素距離的數(shù)組。

從以上步驟可以看出，最大最小距離積法將M中每個(gè)元素對應(yīng)的Temp 最大值與最小值乘積中的最大值為初始點(diǎn)，不但能夠使初始點(diǎn)的分布比較稀疏，而且可以選取到點(diǎn)密度比較大的點(diǎn)。

3.2 新的適應(yīng)度函數(shù)

適應(yīng)度函數(shù)將引導(dǎo)群體進(jìn)化的方向，直接決定了群體的進(jìn)化行為、迭代的次數(shù)和解的質(zhì)量，不同的適應(yīng)度函數(shù)會(huì)得出不同優(yōu)劣程度的解［14］。本文提出一種新的適應(yīng)度函數(shù)，如式（9）所示。

從式（8）可以看出適應(yīng)度越小，所解出的聚類中心點(diǎn)與該類中其他點(diǎn)的歐式距離的差值之和越小，也就是求解出的聚類中心越精確。

4 RMFO 優(yōu)化KMC 算法

本文提出了基于RMFO 優(yōu)化的KMC 算法，主要過程是：通過RMFO 算法先進(jìn)行一次迭代，得到新的聚類中心作為KMC 算法的初始聚類中心，再將KMC 運(yùn)行的結(jié)果作為改進(jìn)MFO 算法的初始點(diǎn)。兩種算法交叉迭代進(jìn)行，最終找到最優(yōu)聚類中心以及最優(yōu)解。

算法的具體步驟描述如下：

1）輸入標(biāo)準(zhǔn)數(shù)據(jù)集即飛蛾種群集合M，根據(jù)數(shù)據(jù)集類別的個(gè)數(shù)確定該數(shù)據(jù)集中類的個(gè)數(shù)k；

2）根據(jù)最大最小距離積法確定每個(gè)類的初始聚類中心點(diǎn)；

3）計(jì)算飛蛾群中的某個(gè)點(diǎn)到每個(gè)初始聚類中心的距離，當(dāng)該點(diǎn)與某一初始聚類中心的距離最小時(shí)，則把該點(diǎn)與這個(gè)初始聚類歸并為一類，依此將所有的點(diǎn)歸并到相應(yīng)的初始聚類中；

4）使用MFO 算法確定步驟3）中歸并之后的每個(gè)類的新聚類中心；

5）利用步驟4）得到的新的聚類中心對飛蛾群進(jìn)行K 均值迭代聚類，根據(jù)其他點(diǎn)與聚類中心點(diǎn)的歐式距離再次進(jìn)行聚類劃分，用每一類的新的聚類中心再次更新當(dāng)前的飛蛾群，當(dāng)?shù)螖?shù)沒有達(dá)到設(shè)定的迭代次數(shù)時(shí)，轉(zhuǎn)向步驟3），直到達(dá)到設(shè)定的迭代次數(shù)，結(jié)束。

主程序流程圖如圖2 所示。

圖2 主程序流程圖

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

實(shí)驗(yàn)平臺(tái)采用CPU 為Intel Core i5 2.60 GHz、內(nèi)存為4 GB 的計(jì)算機(jī)，操作系統(tǒng)為Windows 7，編譯軟件為Matlab R2014a。選擇的數(shù)據(jù)集為UCI 國際通用測試數(shù)據(jù)庫，是專門用來聚類算法的國際的通用的數(shù)據(jù)庫。實(shí)驗(yàn)采用Iris、Wine 和Glass 3 種數(shù)據(jù)集，主要特征如表1 所示。

表1 標(biāo)準(zhǔn)數(shù)據(jù)集特征

5.1 RMFO 算法性能測試

對RMFO 算法進(jìn)行性能測試比較，分別在3 種數(shù)據(jù)集上使用MFO 算法和RMFO 算法進(jìn)行聚類，對比聚類效果并進(jìn)行數(shù)據(jù)分析。兩種算法的參數(shù)設(shè)置如下：在Glass、Iris 最大迭代次數(shù)為200 次，在Wine 數(shù)據(jù)集上最大迭代次數(shù)為100 次，飛蛾種群的規(guī)模為30，數(shù)據(jù)集中的聚類數(shù)目如表1 所示。采用適應(yīng)度來評價(jià)改進(jìn)算法的性能，則兩種算法在3 種數(shù)據(jù)集上聚類的實(shí)驗(yàn)結(jié)果圖如下頁圖3 所示?？梢钥闯觯倪M(jìn)的RMFO 算法的適應(yīng)度值比經(jīng)典MFO算法的適應(yīng)度值要小，收斂速度更快。RMFO 算法在初始值的選取上使用最大最小距離積法，避免了初始值的隨機(jī)性，不易使算法陷入局部最優(yōu)解，得到的最優(yōu)解更加精確。RMFO 算法確實(shí)比MFO 算法在求解的最優(yōu)解方面更有優(yōu)勢。但從圖3（c）中看出，兩種算法很有可能陷入局部最優(yōu)解，所以需要將RMFO 算法和K 均值算法進(jìn)行混合迭代。

圖3 RMFO 實(shí)驗(yàn)結(jié)果

5.2 基于RMFO 優(yōu)化的KMC 算法性能評價(jià)

將KMC 算法、基于RMFO 優(yōu)化的KMC 算法和文獻(xiàn)［15］算法分別對3 種數(shù)據(jù)集進(jìn)行聚類分析。其中基于RMFO 優(yōu)化的KMC 算法參數(shù)設(shè)置為：飛蛾種群的規(guī)模為30，算法在3 種數(shù)據(jù)集上聚類的最大迭代次數(shù)都為100 次。圖3 和圖4 是基于RMFO 優(yōu)化的KMC 算法在3 種數(shù)據(jù)集的運(yùn)行結(jié)果，可以看出，算法能夠很快迭代到最優(yōu)解的位置，適應(yīng)度值變化幅度不大。圖3 還可以看出算法能夠很好地避免局部最優(yōu)解，這與MFO 算法本身的飛蛾棄焰行為和基于RMFO 優(yōu)化的KMC 算法混合迭代每一次聚類的重新劃分有很大關(guān)系。對比實(shí)驗(yàn)表明，本文算法迭代次數(shù)更少，聚類過程中的收斂速度快，能夠很好地跳出局部最優(yōu)解尋找出全局最優(yōu)解，適應(yīng)度變化幅度不大，穩(wěn)定性更強(qiáng)。

圖4 在Iris 和Glass 數(shù)據(jù)集上的結(jié)果

圖5 在Wine 數(shù)據(jù)集上的運(yùn)行結(jié)果

采用KMC 算法、基于RMFO 優(yōu)化的KMC 算法、文獻(xiàn)［15］算法，分別對3 種數(shù)據(jù)集進(jìn)行聚類分析，實(shí)驗(yàn)結(jié)果如表2～表4 所示?？梢钥闯鯧MC 需要的迭代次數(shù)過多，算法達(dá)到穩(wěn)定狀態(tài)耗時(shí)過長。同時(shí)，由于KMC 算法依賴初始點(diǎn)的選取，所以很容易陷入局部最優(yōu)解，使所得適應(yīng)度值并不是最優(yōu)解，全局搜索能力較差。文獻(xiàn)［15］在聚類算法中引入模糊控制的概念，使用模糊聚類算法，使得迭代曲線趨于平滑，相比KMC 算法，文獻(xiàn)［15］的迭代次數(shù)較少，但由于初始點(diǎn)選取的隨機(jī)性，仍未達(dá)到全局最優(yōu)解，使所得聚類中心點(diǎn)不夠準(zhǔn)確。本文算法改進(jìn)了MFO 算法的初始化和適應(yīng)度公式構(gòu)造方法，并通過與KMC 算法混合迭代使收斂速度加快，迭代次數(shù)減少，適應(yīng)度值最小，具有跳出局部最優(yōu)解的能力，全局搜索能力較佳，解得的聚類中心更加精準(zhǔn)。

表2 不同算法在Glass 數(shù)據(jù)集上的對比結(jié)果

表3 不同算法在Iris 數(shù)據(jù)集上的對比結(jié)果

表4 不同算法在Wine 數(shù)據(jù)集上的對比結(jié)果

6 結(jié)論

1）本文從飛蛾群的初始化以及適應(yīng)度函數(shù)兩個(gè)方面對MFO 算法進(jìn)行了改進(jìn)，提出了RMFO 算法，克服了原始飛蛾捕焰算法初始化的隨機(jī)性，解決了飛蛾的個(gè)別解較差和容易陷入局部最優(yōu)解等問題。

2）將RMFO 算法和KMC 算法進(jìn)行交叉迭代，構(gòu)建新的基于RMFO 優(yōu)化的KMC 算法，克服了KMC 算法由于初始化的隨機(jī)性使得初始點(diǎn)敏感，使KMC 算法的迭代次數(shù)大大減少，避免了陷入局部最優(yōu)解。

3）對比結(jié)果表明了本文算法的有效性，通過引入改進(jìn)的飛蛾捕焰算法，提升K 均值聚類算法全局搜索能力，提高了算法的魯棒性，并且解決了KMC算法由于初始化的隨機(jī)性使得初始點(diǎn)敏感的問題。

4）保證聚類效果的條件下，效率當(dāng)然是越高越好。如何進(jìn)一步降低基于RMFO 優(yōu)化的KMC 算法復(fù)雜度將是本文下一步研究方向。