基于Levy飛行的螢火蟲(chóng)模糊聚類(lèi)算法

劉曉明 沈明玉 侯整風(fēng)

摘 要：針對(duì)模糊C均值（FCM）聚類(lèi)算法易受初始聚類(lèi)中心影響而陷入局部最優(yōu)問(wèn)題，提出了一種基于Levy飛行的螢火蟲(chóng)模糊聚類(lèi)算法（LFAFCM）。該算法改變螢火蟲(chóng)算法的隨機(jī)移動(dòng)策略，以平衡算法局部搜索和全局搜索能力;螢火蟲(chóng)位置更新過(guò)程中引入Levy飛行機(jī)制，以提高全局尋優(yōu)能力;根據(jù)迭代次數(shù)和螢火蟲(chóng)位置動(dòng)態(tài)調(diào)整每個(gè)螢火蟲(chóng)的尺度系數(shù)，以限制Levy飛行可搜索范圍，并加快算法收斂速度。利用5個(gè)UCI數(shù)據(jù)集對(duì)算法進(jìn)行實(shí)驗(yàn)驗(yàn)證，實(shí)驗(yàn)結(jié)果表明，該算法有效避免了陷入局部最優(yōu)并具有較快的收斂速度。

關(guān)鍵詞：Levy飛行;尺度系數(shù);螢火蟲(chóng)算法;模糊C均值聚類(lèi)算法;動(dòng)態(tài)調(diào)整

中圖分類(lèi)號(hào)：TP301.6

文獻(xiàn)標(biāo)志碼：A

Firefly fuzzy clustering algorithm based on Levy flight

LIU Xiaoming*， SHEN Mingyu， HOU Zhengfeng

School of Computer and Information， Hefei University of Technology， Hefei Anhui 230009， China

Abstract：

Fuzzy CMeans （FCM） clustering algorithm is sensitive to the initial clustering center and is easy to fall into local optimum. Therefore， a Firefly Fuzzy CMeans clustering Algorithm based on Levy flight （LFAFCM） was proposed. In LFAFCM， the random movement strategy of firefly algorithm was changed to balance the algorithms local search and global search capabilities， the Levy flight mechanism was introduced during the firefly position update process to improve the global optimization ability， and the scale coefficient of each firefly was dynamically adjusted according to the number of iterations and the firefly position to limit the searchable range of Levy flight and speed up the convergence of the algorithm. The algorithm was validated by using five UCI datasets. The experimental results show that the algorithm avoids the local optimum and has a fast convergence speed.

Key words：

Levy flight; scale factor; Firefly Algorithm （FA）; Fuzzy CMeans （FCM） clustering algorithm; dynamic adjustment

0?引言

聚類(lèi)是將數(shù)據(jù)集分成多個(gè)不同的類(lèi)別，使得類(lèi)中數(shù)據(jù)盡量相似，類(lèi)間數(shù)據(jù)差別較大。聚類(lèi)作為一種數(shù)據(jù)分析技術(shù)，廣泛應(yīng)用于數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)等領(lǐng)域[1]。聚類(lèi)分為硬聚類(lèi)和模糊聚類(lèi)，硬聚類(lèi)中某個(gè)對(duì)象只能?chē)?yán)格屬于某一類(lèi)，各類(lèi)之間界限分明。而現(xiàn)實(shí)世界中大多數(shù)事物并不是非此即彼的關(guān)系，事物之間存在不確定性。模糊聚類(lèi)通過(guò)隸屬度描述事物屬于某個(gè)類(lèi)的程度，更適合描述現(xiàn)實(shí)世界事物間的不確定性[2]。模糊C均值（Fuzzy CMeans， FCM）[3]聚類(lèi)是一種經(jīng)典的模糊聚類(lèi)算法，該算法簡(jiǎn)單，且局部搜索能力強(qiáng)，但對(duì)初始值敏感，易陷入局部最優(yōu)。針對(duì)這一問(wèn)題，一些學(xué)者采用群智算法對(duì)FCM進(jìn)行優(yōu)化，文獻(xiàn)[4]中提出基于遺傳算法（Genetic Algorithm， GA）的GAFCM（Fuzzy CMeans clustering algorithm based on GA），利用遺產(chǎn)變異操作對(duì)聚類(lèi)中心進(jìn)行優(yōu)化;文獻(xiàn)[5]提出基于粒子群優(yōu)化（Particle Swarm Optimization， PSO）算法的PSOFCM（Fuzzy CMeans clustering algorithm based on PSO），利用粒子群優(yōu)化算法的記憶搜索提高全局尋優(yōu)能力;但由于粒子群算法和遺傳算法收斂速度慢，PSOFCM和GAFCM在單極值數(shù)據(jù)集上效果均較差，無(wú)法得到精確的全局最優(yōu)解。文獻(xiàn)[6]里利用模糊聚類(lèi)算法生成PSOFCM的初始解，降低初始解的隨機(jī)性，優(yōu)化了粒子群演化的方向;文獻(xiàn)[7]將Agnes層次聚類(lèi)與GAFCM結(jié)合，利用層次聚類(lèi)優(yōu)化初始聚類(lèi)中心的選取，克服FCM初始值敏感的缺陷;但這些方法均存在參數(shù)設(shè)置復(fù)雜、收斂速度較慢的缺點(diǎn)。

2008年Yang等[8]提出了螢火蟲(chóng)群智優(yōu)化算法（Firefly Algorithm， FA），F(xiàn)A模仿自然界螢火蟲(chóng)通過(guò)發(fā)光來(lái)吸引同伴的特性，將搜索和優(yōu)化的過(guò)程模擬成螢火蟲(chóng)吸引和移動(dòng)的過(guò)程。FA比GA和PSO具有更好的尋優(yōu)能力，且思路簡(jiǎn)單明了、參數(shù)較少，廣泛應(yīng)用于路徑規(guī)劃、圖像處理、目標(biāo)跟蹤等眾多領(lǐng)域[9-11]。文獻(xiàn)[12]中提出基于螢火蟲(chóng)算法的FAFCM（Fuzzy CMeans clustering algorithm based on FA），利用FA對(duì)模糊聚類(lèi)的目標(biāo)函數(shù)進(jìn)行優(yōu)化，提高模糊聚類(lèi)的全局收斂性; 然而，同其他啟發(fā)式算法一樣，F(xiàn)A后期也存在收斂速度較慢和易陷入局部最優(yōu)等不足。文獻(xiàn)[13]將混沌理論與螢火蟲(chóng)算法結(jié)合，利用混沌運(yùn)動(dòng)的隨機(jī)性、遍歷性、規(guī)律性增強(qiáng)隨機(jī)搜索性能。文獻(xiàn)[14]將螢火蟲(chóng)種群分為不同參數(shù)的多個(gè)子群，各子群螢火蟲(chóng)構(gòu)建相互學(xué)習(xí)機(jī)制，實(shí)現(xiàn)子群間信息交流。文獻(xiàn)[15]將遺傳算法中的變異操作引入螢火蟲(chóng)算法中，提高種群的多樣性。上述方法通過(guò)改善搜索方式在一定程度上增強(qiáng)了螢火蟲(chóng)算法的全局收斂性，但增加了算法的復(fù)雜程度。

Levy飛行模式是自然界中的生物在未知環(huán)境中尋找食物的常用方式，果蠅的覓食路徑[16]、人類(lèi)行為中的Ju/hoansi狩獵模式[17]都表現(xiàn)出Levy飛行的特征。Levy飛行具有頻繁短距離搜索和偶爾長(zhǎng)距離搜索的特性[8]，能夠避免局部最優(yōu)。然而，Levy飛行的短距離搜索在算法初期收斂速度較慢，后期由于多數(shù)解都集中在最優(yōu)解附近，大范圍搜索易偏離最優(yōu)解，對(duì)全局收斂不起作用。

本文提出基于Levy飛行的螢火蟲(chóng)模糊聚類(lèi)算法（Firefly Fuzzy CMeans clustering Algorithm based on Levy flight， LFAFCM），通過(guò)改變螢火蟲(chóng)隨機(jī)移動(dòng)策略，在位置更新過(guò)程中引入Levy飛行機(jī)制，平衡算法的局部和全局搜索能力。頻繁短距離搜索可提高局部搜索性能;偶爾長(zhǎng)距離搜索能夠擴(kuò)大螢火蟲(chóng)搜索范圍，增強(qiáng)全局搜索能力。此外，本文算法根據(jù)螢火蟲(chóng)位置和迭代次數(shù)動(dòng)態(tài)改變每個(gè)螢火蟲(chóng)的尺度系數(shù)，控制算法不同時(shí)期Levy飛行的搜索范圍，提高算法初期發(fā)現(xiàn)近似全局最優(yōu)解的效率，同時(shí)避免后期長(zhǎng)距離搜索導(dǎo)致偏離最優(yōu)解問(wèn)題，提高算法的收斂速度。

1?相關(guān)算法

1.1?模糊C均值聚類(lèi)算法

對(duì)于數(shù)據(jù)集X={x1，x2，…，xn}，其中包含n個(gè)對(duì)象，每個(gè)對(duì)象含d個(gè)屬性，聚類(lèi)就是將這n個(gè)對(duì)象劃分到c個(gè)簇中（2≤c≤n），簇的聚類(lèi)中心為V={v1，v2，…，vc}，F(xiàn)CM的目標(biāo)函數(shù)定義[2]為：

Jm=∑ni=1umij‖xi-vj‖2 （1）

其中，m為模糊加權(quán)指數(shù)，控制模糊矩陣的分類(lèi)程度，一般取m=2，U=[uij]c×n是隸屬度矩陣，uij∈[0，1]，表示第j對(duì)象隸屬于第i個(gè)簇的程度，‖xi-vj‖2表示第j對(duì)象與第i個(gè)聚類(lèi)中心的歐氏距離。FCM算法就是通過(guò)不斷迭代優(yōu)化目標(biāo)函數(shù)，當(dāng)目標(biāo)函數(shù)最小時(shí)即得到最優(yōu)的聚類(lèi)結(jié)果。算法的基本步驟如下：

步驟1?設(shè)置初始聚類(lèi)數(shù)目c和模糊加權(quán)系數(shù)m，隨機(jī)初始化c個(gè)聚類(lèi)中心v（0）i（1≤i≤c），設(shè)置閾值ε作為算法的結(jié)束條件。

步驟2?計(jì)算隸屬度矩陣：

uij=1∑ck=1‖xi-vj‖‖xi-vk‖2m-1; 1≤i≤c，1≤j≤n （2）

步驟3?更新聚類(lèi)中心V：

vj=∑ni=1umijxi/∑ni=1umij; 1≤j≤c （3）

步驟4?當(dāng)更新后的聚類(lèi)中心與原聚類(lèi)中心的距離小于給定的閾值ε，算法停止，輸出聚類(lèi)中心和隸屬度矩陣;否則，轉(zhuǎn)步驟2。

模糊C均值聚類(lèi)算法通過(guò)不斷迭代計(jì)算聚類(lèi)中心和隸屬度矩陣得到最優(yōu)的聚類(lèi)結(jié)果，這是一種基于梯度下降的搜索方法，收斂速度快，局部搜索能力強(qiáng)。但FCM非常依賴(lài)初始聚類(lèi)中心的選取，較差的初始聚類(lèi)中心易導(dǎo)致算法陷入局部最優(yōu)。

1.2?螢火蟲(chóng)算法

1.2.1?算法原理

自然界中的螢火蟲(chóng)通過(guò)發(fā)光吸引異性進(jìn)行信息交流。文獻(xiàn)[8]中根據(jù)螢火蟲(chóng)的這種發(fā)光特性提出了螢火蟲(chóng)優(yōu)化算法，該算法的基本思想是每個(gè)螢火蟲(chóng)代表一個(gè)目標(biāo)函數(shù)的解，螢火蟲(chóng)的亮度表示目標(biāo)函數(shù)解的好壞程度，亮度小的螢火蟲(chóng)向亮度大的螢火蟲(chóng)移動(dòng)，然后更新自己的亮度，螢火蟲(chóng)個(gè)體不斷移動(dòng)的過(guò)程即為目標(biāo)函數(shù)的優(yōu)化過(guò)程，通過(guò)位置和亮度的不斷迭代，最終得到目標(biāo)函數(shù)的最優(yōu)值。

算法的迭代過(guò)程遵循下面3個(gè)基本規(guī)則：

1）所有的螢火蟲(chóng)不以性別區(qū)分，任何一只螢火蟲(chóng)都會(huì)被其他的螢火蟲(chóng)吸引。

2）螢火蟲(chóng)會(huì)被比自己亮的個(gè)體吸引，最亮的個(gè)體隨機(jī)改變自己的位置。兩只螢火蟲(chóng)之間距離越近，相互之間的吸引度越高。

3）螢火蟲(chóng)的亮度根據(jù)所求解問(wèn)題的目標(biāo)函數(shù)定義。

1.2.2?算法的數(shù)學(xué)描述

算法中的兩個(gè)要素是亮度和吸引度，螢火蟲(chóng)位置越優(yōu)，亮度越大，吸引亮度小的螢火蟲(chóng)向自己移動(dòng);螢火蟲(chóng)之間距離越近，吸引度越大，移動(dòng)距離越長(zhǎng)。

算法的相關(guān)描述如下：

1）螢火蟲(chóng)亮度：

Ii∝1J（xi）; 1≤i≤n（4）

其中：Ii為第i只螢火蟲(chóng)的亮度，xi為第i只螢火蟲(chóng)的位置，J（xi）為第i只螢火蟲(chóng)對(duì)應(yīng)的目標(biāo)函數(shù)的值。

2）螢火蟲(chóng)之間的相對(duì)吸引度：

β=β0×e-γrij（5）

其中：β是螢火蟲(chóng)i和螢火蟲(chóng)j之間的相對(duì)吸引度，β0是最大吸引度，即r=0時(shí)的吸引度，γ是光強(qiáng)吸收因子（通常設(shè)置常數(shù)）。rij為螢火蟲(chóng)i和螢火蟲(chóng)j之間的距離，計(jì)算方式為：

rij=‖xi-xj‖=∑dk=1（xik-xjk）2（6）

其中d為所求解問(wèn)題的維數(shù)。

3）螢火蟲(chóng)i被比其明亮的螢火蟲(chóng)j吸引而移動(dòng)，其位置更新公式為：

xk+1i=xi+β（xj-xi）+αεi（7）

其中：xt+1i是螢火蟲(chóng)更新后的位置;xi、xj分別表示螢火蟲(chóng)i和螢火蟲(chóng)j的位置;αεi是擾動(dòng)項(xiàng)，目的是增強(qiáng)全局搜索能力，α是尺度系數(shù)，εi是服從高斯分布的隨機(jī)數(shù)。

2?基于Levy飛行的螢火蟲(chóng)模糊聚類(lèi)

2.1?Levy飛行機(jī)制

Levy飛行的隨機(jī)步長(zhǎng)服從Levy分布，Levy分布比高斯分布和柯西分布的尾翼更為寬大（如圖1所示），具有更強(qiáng)的擾動(dòng)作用，Levy分布冪次形式的表達(dá)式[18]如下：

Levy（λ）～|s|-λ; 1<λ<3 （8）

其中：s是隨機(jī)步長(zhǎng)，λ是指數(shù)參數(shù)。

Levy飛行的隨機(jī)步長(zhǎng)一般采用Mantegna[19]提出的計(jì)算公式：

s=μ/|v|1/λ; 0<λ<2（9）

其中：s即為L(zhǎng)evy飛行的步長(zhǎng)，參數(shù)λ一般取值為1.5;參數(shù)μ，v為服從式（10）所示的正態(tài)分布的隨機(jī)數(shù)：

μ～N（0，δ2μ）

v～N（0，δ2v）（10）

式中δμ、δv定義為：

δu={Γ（1 + λ）sin（πλ/2）2（λ-1）/2Γ[（（1 + λ）/2）]}1/λ

δv=1（11）

其中Γ是標(biāo)準(zhǔn)Gamma函數(shù)。

2.2?基于Levy飛行的螢火蟲(chóng)模糊聚類(lèi)

傳統(tǒng)的螢火蟲(chóng)算法在螢火蟲(chóng)位置更新過(guò)程中，采用隨機(jī)的擾動(dòng)方式，存在易陷入局部最優(yōu)的問(wèn)題，本文提出基于Levy飛行的螢火蟲(chóng)模糊聚類(lèi)算法（LFAFCM），改變螢火蟲(chóng)算法的隨機(jī)移動(dòng)策略，平衡局部和全局搜索能力，彌補(bǔ)模糊C均值聚類(lèi)易陷入局部最優(yōu)的不足，同時(shí)減少算法的迭代次數(shù)。

LFAFCM在螢火蟲(chóng)位置更新過(guò)程中引入Levy飛行機(jī)制，以提高算法的全局尋優(yōu)能力，并通過(guò)動(dòng)態(tài)尺度系數(shù)限制不同時(shí)期Levy飛行的搜索范圍，以加快算法的收斂速度，LFAFCM中螢火蟲(chóng)的位置更新公式如下：

xk+1i=xi+β·（xj-xi）+

α（t）·sign（rand）·Levy（λ）（12）

其中：Levy（λ）為L(zhǎng)evy飛行產(chǎn)生的步長(zhǎng)，sign（rand）為L(zhǎng)evy飛行的搜索方向，rand是[0，1]上均勻分布的隨機(jī)數(shù)：

sign（rand）=

1，rand≥1/2

-1，rand < 1/2;

0≤rand≤1 （13）

與式（7）相比，式（12）具有如下兩個(gè)優(yōu)點(diǎn)：

1）避免局部最優(yōu)。

螢火蟲(chóng)算法位置更新式（6）中的擾動(dòng)項(xiàng)αεi，εi是服從高斯分布的隨機(jī)數(shù)，所以擾動(dòng)項(xiàng)產(chǎn)生的是近似布朗運(yùn)動(dòng)，布朗運(yùn)動(dòng)的方差與時(shí)間成線性關(guān)系：δ2（t）～t;Levy飛行的方差與時(shí)間呈指數(shù)關(guān)系：δ2（t）～t4-λ（1<λ<3）， 比布朗運(yùn)動(dòng)的方差增長(zhǎng)得更快，擾動(dòng)范圍大，搜索空間更廣。

圖2所示為L(zhǎng)evy飛行軌跡，Levy飛行表現(xiàn)出頻繁短距離搜索和偶爾長(zhǎng)距離搜索的特性，短距離搜索能在當(dāng)前解附近尋優(yōu)，增強(qiáng)局部搜索能力;長(zhǎng)距離搜索能在當(dāng)前解較遠(yuǎn)處尋優(yōu)，從而擴(kuò)大了搜索范圍。

2）減少迭代次數(shù)。

LFAFC通過(guò)式（12）來(lái)進(jìn)行螢火蟲(chóng)的位置更新，利用Levy飛行的間歇搜索避免陷入局部最優(yōu)，式中的尺度系數(shù)α（t）控制Levy飛行的搜索范圍。算法初期若搜索范圍過(guò)小，長(zhǎng)距離搜索效果不明顯，易使得搜索過(guò)程緩慢;算法后期，螢火蟲(chóng)亮度接近，一般都在最優(yōu)解附近，此時(shí)長(zhǎng)距離產(chǎn)生的大范圍搜索易偏離最優(yōu)解，導(dǎo)致迭代次數(shù)增加。因此，LFAFCM按照以下兩個(gè)策略動(dòng)態(tài)調(diào)整尺度系數(shù)α（t）：

①每個(gè)螢火蟲(chóng)的尺度系數(shù)隨著迭代次數(shù)的增加非線性減小，使得前期擁有較大搜索范圍，能夠以較大的步長(zhǎng)進(jìn)行搜索;后期搜索范圍較小，避免長(zhǎng)距離的搜索，使得能夠以較小的步長(zhǎng)逐步逼近最優(yōu)解。

②螢火蟲(chóng)移動(dòng)時(shí)計(jì)算與當(dāng)前最亮螢火蟲(chóng)的亮度差值，若亮度相差較大，則當(dāng)前解較劣，使用較大的尺度系數(shù)α（t），以擴(kuò)大搜索范圍;當(dāng)亮度接近最亮螢火蟲(chóng)時(shí)，則當(dāng)前解較優(yōu)，使用較小的尺度系數(shù)，使得在當(dāng)前解附近仔細(xì)搜索。

動(dòng)態(tài)尺度系數(shù)公式為：

α（t）=αinit·exp（-t/（Igbest-Ipresent）（14）

式中：t表示當(dāng)前迭代次數(shù)，αinit表示初始的尺度系數(shù)，Igbest表示最亮的螢火蟲(chóng)亮度，Ipresent表示當(dāng)前螢火蟲(chóng)的亮度。這樣在算法初期，Levy飛行范圍較大，有利于擴(kuò)大搜索范圍，找到近似的全局最優(yōu)解，后期種群趨于穩(wěn)定時(shí)，減小Levy飛行的搜索范圍，防止算法在最優(yōu)值附近震蕩，以盡快逼近最優(yōu)解。

2.3?LFAFCM算法步驟

步驟1?設(shè)置簇的數(shù)目c，最大吸引度β0，光的吸收因子γ，初始尺度系數(shù)αinit，模糊加權(quán)指數(shù)m，算法最大迭代次數(shù)maxIter，當(dāng)前迭代次數(shù)k，閾值limit，螢火蟲(chóng)的種群規(guī)模N。

步驟2?初始化每個(gè)螢火蟲(chóng)i的位置xi（0

步驟3?根據(jù)式（4）計(jì)算每個(gè)螢火蟲(chóng)i的亮度Ii。

步驟4?按照亮度對(duì)螢火蟲(chóng)種群排序，記錄最亮螢火蟲(chóng)的亮度Ibest和位置xbest。

步驟5?每個(gè)螢火蟲(chóng)根據(jù)式（14）更新尺度系數(shù)，再將尺度系數(shù)代入式（12）中更新自己的位置。

步驟6?更新每個(gè)螢火蟲(chóng)的亮度，更新最亮螢火蟲(chóng)的亮度Ibest和位置xbest。

步驟7?將最亮螢火蟲(chóng)的位置xbest作為初始聚類(lèi)中心，進(jìn)行如下操作：

1）根據(jù)式（2）得到隸屬度矩陣。

2）根據(jù)式（3）得到新的聚類(lèi)中心，更新為xbest。

3）根據(jù)式（1）計(jì)算目標(biāo)函數(shù)的值，若與初始聚類(lèi)中心差值大于給定閾值limit，轉(zhuǎn)操作1）。

步驟8?若k

LFAFCM算法流程如圖3所示，其中J表示目標(biāo)函數(shù)值，t表示梯度下降法中的迭代計(jì)數(shù)。

2.4?時(shí)空復(fù)雜度分析

2.4.1?時(shí)間復(fù)雜度分析

由圖3可知，LFAFCM算法的主要部分在步驟5～7，此部分包括兩個(gè)循環(huán)，外循環(huán)最大迭代次數(shù)為maxIter;內(nèi)循環(huán)設(shè)置閾值limit，無(wú)準(zhǔn)確迭代次數(shù)，設(shè)內(nèi)層的平均迭代次數(shù)為avgIter;步驟5中每個(gè)螢火蟲(chóng)都要向更亮的個(gè)體進(jìn)行移動(dòng)，由于螢火蟲(chóng)種群規(guī)模為N，要進(jìn)行（N2-N）/2次移動(dòng)。所以經(jīng)過(guò)所有步驟后，算法的時(shí)間復(fù)雜度近似為O（maxIter×avgIter×N2）。

2.4.2?空間復(fù)雜度分析

設(shè)LFAFCM算法螢火蟲(chóng)規(guī)模為N，簇的數(shù)目為c，迭代次數(shù)為maxIter。算法運(yùn)行過(guò)程中，X[C][N]存儲(chǔ)螢火蟲(chóng)的自身位置，L[N]存儲(chǔ)每個(gè)螢火蟲(chóng)的亮度，隸屬度矩陣大小U[C][N]，每次迭代后的最亮螢火蟲(chóng)位置保存在B[maxIter]中。因此，LFAFCM算法空間復(fù)雜度為2×O（CN）+O（N）+O（maxIter）。

3?實(shí)驗(yàn)

實(shí)驗(yàn)環(huán)境?操作系統(tǒng)Windows 10，語(yǔ)言Python 3.5.5，軟件Visual Studio Code 1.28，Matlab R2016b，CUP Inter Core i5，內(nèi)存 8GB。

實(shí)驗(yàn)?zāi)康?驗(yàn)證LFAFCM算法的聚類(lèi)效果和效率。

數(shù)據(jù)集?本文選取了UCI數(shù)據(jù)庫(kù)中的Iris、Wine、Ecoli、Glass、D31五個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，5個(gè)數(shù)據(jù)集的樣本數(shù)、屬性數(shù)、類(lèi)別數(shù)如表1所示。

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

1）數(shù)據(jù)集的極值。

為了分析LFAFCM算法得到的解是否是全局最優(yōu)解，先進(jìn)行實(shí)驗(yàn)測(cè)試每個(gè)數(shù)據(jù)集的極值，通過(guò)在每個(gè)數(shù)據(jù)集上執(zhí)行1-000次FCM，得到各數(shù)據(jù)集的極值如表2所示。根據(jù)數(shù)據(jù)集的極值數(shù)量，將數(shù)據(jù)集分成單極值數(shù)據(jù)集和多極值數(shù)據(jù)集。

2）LFAFCM聚類(lèi)效果。

LFAFCM參數(shù)設(shè)置為γ=1.0，αinit=1.0，β=1.0，模糊權(quán)重系數(shù)m=2，最大迭代次數(shù)maxIter=100，種群規(guī)模N=20;GAFCM的N=20，maxIter=100，交差概率pc=0.9，變異概率pm=0.001;PSOFCM的N=20，maxIter=100，慣性權(quán)重ω=1，學(xué)習(xí)因子c1=c2=2;FAFCM中N=20，maxIter=100，β=1.0，γ=0.9，α=0.1，k=2。

算法在每個(gè)數(shù)據(jù)集上重復(fù)運(yùn)行50次，計(jì)算目標(biāo)函數(shù)的平均值和標(biāo)準(zhǔn)差，實(shí)驗(yàn)結(jié)果如表3所示（其中GAFCM、PSOFCM部分實(shí)驗(yàn)數(shù)據(jù)源于文獻(xiàn)[20]）。

從表3可以看出，LFAFCM與PSOFCM、GAFCM相比，在各數(shù)據(jù)集上目標(biāo)函數(shù)都具有更小的平均值和標(biāo)準(zhǔn)差，表明LFAFCM的聚類(lèi)準(zhǔn)確度和穩(wěn)定性均優(yōu)于PSOFCM和GAFCM;LFAFCM與FAFCM相比，在單極值數(shù)據(jù)集Iris、Wine平均值和標(biāo)準(zhǔn)差無(wú)明顯差異，

但在多極值數(shù)據(jù)集Ecoli、Glass、D31上，LFAFCM的平均值小于FAFCM，LFAFCM表現(xiàn)出比FAFCM更好的收斂效果，并且LFAFCM的標(biāo)準(zhǔn)差遠(yuǎn)小于FAFCM，表明LFAFCM穩(wěn)定性遠(yuǎn)高于FAFCM。對(duì)比表2中數(shù)據(jù)集的極值，LFAFCM的目標(biāo)函數(shù)平均值與各數(shù)據(jù)集的最小極值接近，且LFAFCM的目標(biāo)函數(shù)值的標(biāo)準(zhǔn)差極小，表明LFAFCM無(wú)論在單極值數(shù)據(jù)集還是多極值數(shù)據(jù)集都能穩(wěn)定得到較好的聚類(lèi)效果。

為更直觀地對(duì)比算法的聚類(lèi)結(jié)果，選取數(shù)據(jù)集D31上各算法50次實(shí)驗(yàn)中目標(biāo)函數(shù)值最小的聚類(lèi)結(jié)果，如圖4所示，每個(gè)聚簇用不同的顏色表示。可以看出，圖（a）～（c）中均存在聚簇重疊和明顯的分類(lèi)不合理的地方，而圖（d）中沒(méi)有明顯的聚簇錯(cuò)誤，基本上可以認(rèn)為達(dá)到了全局最優(yōu)解。

4）LFAFCM收斂速度。

GAFCM、PSOFCM、FAFCM、LFAFCM在五個(gè)數(shù)據(jù)集上目標(biāo)函數(shù)隨迭代次數(shù)的變化曲線，如圖5所示。

由圖5可知，LFAFCM與FAFCM相比，在單極值數(shù)據(jù)集Iris、Wine上，具有相似迭代變化曲線;在多極值數(shù)據(jù)集Ecoli、Glass、D31上，LFAFCM目標(biāo)函數(shù)值隨迭代次數(shù)下降更快，表明LFAFCM比FAFCM具有更快的收斂速度。而LFAFCM與PSOFCM、GAFCM相比，無(wú)論在單極值數(shù)據(jù)集還是多極值數(shù)據(jù)集上，LFAFCM都表現(xiàn)出更快的收斂速度。

在各數(shù)據(jù)集的50次實(shí)驗(yàn)中，GAFCM、PSOFCM、FAFCM、LFAFCM達(dá)到收斂時(shí)的平均迭代次數(shù)如表4所示。

在數(shù)據(jù)集Iris、Wine、Glass上，LFAFCM的迭代次數(shù)與FAFCM相差不大，但明顯少于PSOFCM、GAFCM。在Ecoli、D31數(shù)據(jù)集上，LFAFCM的迭代次數(shù)均遠(yuǎn)小于其他三種算法。

4?結(jié)語(yǔ)

本文針對(duì)模糊C均值聚類(lèi)算法全局搜索能力較差、易陷入局部最優(yōu)的問(wèn)題，提出一種基于Levy飛行的螢火蟲(chóng)模糊聚類(lèi)算法，在螢火蟲(chóng)算法中引入Levy飛行機(jī)制，改變螢火蟲(chóng)算法的擾動(dòng)方式，利用Levy飛行的長(zhǎng)短間歇搜索模式增強(qiáng)算法的全局搜索性能。為避免Levy飛行在算法后期飛行范圍較大導(dǎo)致收斂速度緩慢，提出動(dòng)態(tài)的尺度系數(shù)策略，根據(jù)螢火蟲(chóng)的迭代次數(shù)和位置動(dòng)態(tài)改變尺度系數(shù)，提高算法的收斂速度。通過(guò)UCI數(shù)據(jù)庫(kù)中五個(gè)數(shù)據(jù)集上的測(cè)試，并將本文算法與GAFCM、PSOFCM、FAFCM進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果表明，本文提出的基于Levy飛行的螢火蟲(chóng)模糊聚類(lèi)無(wú)論是在單極值數(shù)據(jù)集還是多極值數(shù)據(jù)集上都表現(xiàn)了較強(qiáng)的尋優(yōu)能力，有效防止了算法陷入局部最優(yōu)，且運(yùn)行效率高。

參考文獻(xiàn) （References）

[1]AGGARWAL C C， REDDY C K . Data Clustering： Algorithms and Applications[M]. [S.l.]： Chapman & Hall/CRC， 2013：30-31.

[2]耿嘉藝，錢(qián)雪忠，周世兵. 新模糊聚類(lèi)有效性指標(biāo)[J]. 計(jì)算機(jī)應(yīng)用研究， 2019， 36（4）： 1001-1005. （GENG J Y， QIAN X Z， ZHOU S B， New fuzzy clustering validity index[J]. Application Research of Computers，2019，36（4）： 1001-1005.）

[3]DUNN J C. A fuzzy relative of the ISODATA process andit is use in detecting compact well separated cluster[J]. Journal of Cybernetics， 1973， 3（3）： 32-57.

[4]HALL L O， OZYURT I B， BEZDEK J C. Clustering with a genetically optimized approach[J]. IEEE Transactions on Evolutionary Computation， 1999， 3（2）：103-112.

[5]DE FALCO I， CIOPPA A D， TARANTINO E. Facing classification problems with particle swarm optimization[J]. Applied Soft Computing， 2007， 7（3）：652-658.

[6]耿宗科，王長(zhǎng)賓，張振國(guó). 基于模糊Cmeans與自適應(yīng)粒子群優(yōu)化的模糊聚類(lèi)算法[J]. 計(jì)算機(jī)科學(xué)， 2016， 43（8）：267-272. （GENG Z K， WANG C B， ZHANG Z G. Fuzzy Cmeans and adaptive PSO based fuzzy clustering algorithm[J]. Computer Science， 2016， 43（8）： 267-272.）

[7]唐成華，劉鵬程，湯申生，等. 基于特征選擇的模糊聚類(lèi)異常入侵行為檢測(cè)[J]. 計(jì)算機(jī)研究與發(fā)展， 2015， 52（3）：718-728. （TANG C H， LIU P C， TANG S S， et al. Anomaly intrusion behavior detection based on fuzzy clustering and features selection[J]. Journal of Computer Research and Development， 2015， 52（3）： 718-728.）

[8]YANG X. Firefly algorithms for multimodal optimization[C]// Proceedings of the 5th International Conference on Stochastic Algorithms， LNCS 5792. Berlin： Springer， 2009：169-178.

[9]王曄嬌，周暉. 基于混合螢火蟲(chóng)算法的RFID網(wǎng)絡(luò)多目標(biāo)規(guī)劃[J]. 計(jì)算機(jī)應(yīng)用研究， 2018， 35（10）：3003-3006. （WANG Y J， ZHOU H. Hybridized firefly algorithm based RFID network multiobjective planning[J]. Application Research of Computers， 2018， 35（10）： 3003-3006.）

[10]HE L， HUANG S. Modified firefly algorithm based multilevel thresholding for color image segmentation[J]. Neurocomputing， 2017， 240：152-174.

[11]de LIMA VARELA V P， OLIVEIRA A， RODRIGUES P， et al. qFA： an optimized basedtracking approach using firefly algorithm[C]// Proceedings of the IEEE 7th Brazilian Conference on Intelligent Systems. Piscataway： IEEE， 2018：302-306.

[12]林睦綱，劉芳菊，童小嬌. 一種基于螢火蟲(chóng)算法的模糊聚類(lèi)算法[J].計(jì)算機(jī)工程與應(yīng)用， 2014， 50（21）：35-38， 73. （LIN M G， LIU F J， TONG X J. Fuzzy clustering algorithm based on firefly algorithm [J]. Computer Engineering and Applications， 2014， 50（21）： 35-38， 73.）

[13]張亞楠，劉升. 一種基于混沌云模型的人工螢火蟲(chóng)優(yōu)化算法[J]. 小型微型計(jì)算機(jī)系統(tǒng)， 2015， 36（11）：2609-2613. （ZHANG Y N， LIU S. Glowworm swarm optimization algorithm based on chaos cloud model[J]. Journal of Chinese Computer Systems， 2015， 36（11）： 2609-2613.）

[14]符強(qiáng)，童楠，趙一鳴. 一種基于多種群學(xué)習(xí)機(jī)制的螢火蟲(chóng)優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究， 2013， 30（12） ：3600-3602. （FU Q， TONG N， ZHAO Y M. Firefly algorithm based on multigroup learning mechanism[J]. Application Research of Computers， 2013， 30（12） ：3600-3602.）

[15]杜曉昕，張劍飛，孫明. 基于自適應(yīng)t分布混合變異的人工螢火蟲(chóng)算法[J]. 計(jì)算機(jī)應(yīng)用， 2013， 33（7）：1922-1925. （DU X X， ZHANG J F， SUN M. Artificial glowworm swarm optimization algorithm based on adaptive t distribution mixed mutation[J]. Journal of Computer Applications， 2013， 33（7）： 1922-1925.）

[16]REYNOLDS A M， FRYE M A. Freeflight odor tracking in drosophila is consistent with an optimal intermittent scalefree search[J]. PloS One， 2007， 2（4）： No.e354.

[17]BROWN C T， LIEBOVITCH L S， GLENDON R. Lévy flights in Dobe Ju/ foraging patterns[J]. Human Ecology， 2007， 35（1）： 129-138.

[18]VISWANATHAN G M， AFANASYEV V， BULDYREV S V， et al. Lévy flights search patterns of biological organisms[J]. Physica A： Statistical Mechanics and its Applications， 2001， 295（1/2）： 85-88.

[19]MANTEGNA R N. Fast accurate algorithm for numerical simulation of Levy stable stochastic processes[J]. Physical Review E， 1994， 49（5）： 4677-4683.

[20]LI C， ZHOU J， KOU P， et al. A novel chaotic particle swarm optimization based fuzzy clustering algorithm[J]. Neurocomputing， 2012， 83：98-109.

This work is partially supported by the National Natural Science Foundation of China （61572167）.

LIU Xiaoming， born in 1994， M. S. candidate. His research interests include network communication and security.

SHEN Mingyu， born in 1962， Ph. D.， associate professor. His research interests include network and information security.

HOU Zhengfeng，born in 1958， M. S.， professor. His research interests include threshold secret sharing， network security.