基于最優(yōu)類中心擾動的螢火蟲聚類算法*

趙 杰，雷秀娟，吳振強

(陜西師范大學(xué)計算機(jī)科學(xué)學(xué)院，陜西 西安 710062)

1 引言

聚類是一種常用的數(shù)據(jù)分析和數(shù)據(jù)挖掘方法。隨著聚類分析在數(shù)據(jù)挖掘、模式識別、機(jī)器學(xué)習(xí)、統(tǒng)計學(xué)等領(lǐng)域應(yīng)用的不斷擴(kuò)展，相關(guān)領(lǐng)域的學(xué)者越來越重視對聚類算法的研究。傳統(tǒng)聚類算法大致可以分為以下幾個類別：基于劃分的方法和基于層次的方法、基于密度的方法、基于網(wǎng)格的方法、基于模型的方法[1,2]。群智能優(yōu)化算法是近十幾年發(fā)展起來的受動物群體智能啟發(fā)的算法，由于具有簡單性、分布式、魯棒性、良好的可擴(kuò)展性、廣泛的適用性等特點[1]，受到越來越多學(xué)者的關(guān)注和研究，被廣泛應(yīng)用于聚類算法中，如遺傳算法[3]、蟻群算法[4]、人工蜂群優(yōu)化算法[5]、人工魚群優(yōu)化算法[6]、粒子群優(yōu)化算法[7]，成為聚類的一類新興方法。

螢火蟲算法FA(Firefly Algorithm)是受自然界中螢火蟲之間通過發(fā)光相互溝通、進(jìn)行信息交流這種生物學(xué)特性的啟發(fā)，由劍橋?qū)W者Yang Xin-she在2008年提出[8,9]，是比較新的一種群智能優(yōu)化算法，已成功應(yīng)用到優(yōu)化問題[10,11]、圖像處理[12,13]、路徑規(guī)劃[14]、旅行商問題[15]、聚類[16～18]等多個領(lǐng)域。

用FA聚類過程中，發(fā)現(xiàn)存在收斂速度較慢、容易在局部最優(yōu)值或者全局最優(yōu)值附近反復(fù)振蕩的問題，據(jù)此，本文對螢火蟲的移動方式和隨機(jī)擾動方式做了改進(jìn)，基于最優(yōu)類中心擾動提出了一種改進(jìn)螢火蟲算法IFA(Improved Firefly Algorithm)的聚類算法，選擇三個標(biāo)準(zhǔn)UCI數(shù)據(jù)集做聚類，驗證了該算法的可行性及有效性。和K均值(K-means)、粒子群優(yōu)化PSO(Particle Swarm Optimization)算法、FA聚類結(jié)果比較的結(jié)果表明，基于最優(yōu)類中心擾動的螢火蟲聚類算法能找到更好的解，有更好的收斂效果。

2 FA的基本理論

2.1 FA的仿生原理

螢火蟲通過熒光素發(fā)生的復(fù)雜生化反應(yīng)進(jìn)行發(fā)光，借助發(fā)光捕食、求偶、警示以及相互交流等，螢火蟲算法就是模擬螢火蟲的發(fā)光行為提出的啟發(fā)式隨機(jī)優(yōu)化算法。在該算法中，有兩個重要的參數(shù)：螢火蟲的亮度和吸引度。為了簡易描述FA算法，通常遵循下面三個理想化的規(guī)則[8]：

(1) 螢火蟲不分雌雄，它們之間相互吸引與性別無關(guān)；

(2) 吸引度與亮度成正比，亮度低的螢火蟲被吸引向亮度高的螢火蟲移動，亮度最大的螢火蟲隨機(jī)移動，吸引度和亮度與距離成反比，隨著距離的增大吸引度和亮度減??；

(3) 螢火蟲的亮度由具體的求解問題的目標(biāo)函數(shù)值決定。

FA算法仿生原理是：用搜索空間中的點模擬螢火蟲個體，將搜索和優(yōu)化過程模擬成螢火蟲個體之間相互吸引和移動的過程，用求解問題的目標(biāo)函數(shù)值來衡量螢火蟲所處位置的優(yōu)劣，將個體的適者生存過程類比為搜索和優(yōu)化過程中用好的可行解取代較差可行解的迭代過程[19]。

2.2 FA算法的描述

螢火蟲的亮度和目標(biāo)函數(shù)值相關(guān)，體現(xiàn)了螢火蟲所處位置的優(yōu)劣，位置越佳目標(biāo)值越好，亮度越高，亮度高的螢火蟲吸引亮度低的螢火蟲向自己移動，移動的大小由吸引度來衡量，可見，亮度決定移動方向，吸引度決定移動大小。

在算法的實現(xiàn)過程有以下幾個定義[8,11]：

定義1熒光亮度:

I∝f(xi), 1≤i≤n

(1)

I=I0×e-γ rij

(2)

其中，xi表示第i個螢火蟲的位置，f(xi)代表具體問題的目標(biāo)函數(shù)值；I0為螢火蟲的最大熒光亮度，即自身(r=0處)的熒光亮度，與目標(biāo)函數(shù)值相關(guān)；γ為光強吸收系數(shù)，因為熒光會隨著距離的增加和傳播媒介吸收逐漸減弱，所以設(shè)置光強吸收系數(shù)體現(xiàn)此特性，可設(shè)為常數(shù)，rij為螢火蟲i和j之間的距離：

(3)

其中，d表示數(shù)據(jù)維度，xi,k表示螢火蟲i的第k個數(shù)據(jù)分量。

定義2吸引度:

(4)

其中，β0為最大吸引度，即光源處(r=0)的吸引度；γ、rij意義同上。

定義3螢火蟲i被吸引向螢火蟲j移動的位置更新:

(5)

其中，xi、xj表示螢火蟲i和j的位置；α為隨機(jī)化參數(shù)，是[0,1]上的常數(shù)；εi是服從高斯分布或均勻分布的隨機(jī)因子，通常簡單地用rand-0.5來表示，rand為[0,1]上服從均勻分布的隨機(jī)數(shù)；αεi是擾動項，避免算法過早陷入局部最優(yōu)。目前最亮的螢火蟲xbest，沒有螢火蟲能夠吸引它，它的位置更新就變成了：

xbest=xbest+αεi

(6)

其中，xbest代表當(dāng)前最亮的螢火蟲所處位置，α含義同上。

文獻(xiàn)[8]中詳細(xì)描述了FA算法，算法偽代碼描述如下：

初始化目標(biāo)函數(shù)f(x),x=(x1,…,xd)T;

初始化螢火蟲種群xi(i=1,2,…,n)，n為螢火蟲種群數(shù)目;

螢火蟲i在xi處的亮度Ii由f(xi)決定;

初始化算法其他參數(shù)：最大吸引度β0、光強吸收系數(shù)γ、步長因子α。

while(未到最大迭代次數(shù))

for i=1:n

for j=1:n

if(Ii

螢火蟲i按照式(5)向螢火蟲j移動;

end if

按照式(4)更新吸引度，按照公式(2)更新亮度;

end for j

end for i

對螢火蟲進(jìn)行排序，找出當(dāng)前全局最優(yōu)解;

end while

結(jié)果處理;

3 基于最優(yōu)類中心擾動的螢火蟲聚類算法

3.1 基于最優(yōu)類中心擾動的螢火蟲聚類算法思想

本文對螢火蟲的移動方式和隨機(jī)擾動方式做了改進(jìn)，提出了一種基于最優(yōu)類中心擾動的螢火蟲聚類算法，算法的基本思路是：用螢火蟲的位置代表聚類中心，通過螢火蟲之間的相互吸引和移動來尋找最優(yōu)的聚類中心，從而找到最優(yōu)的聚類，目標(biāo)是使所有樣本到相應(yīng)聚類中心的距離之和最小，聚類準(zhǔn)則函數(shù)[1]為：

(7)

其中，m為聚類數(shù)目，Zk代表第k個聚類的中心，d(Xi,Zk)為樣本Xi到對應(yīng)聚類中心的距離。

d(Xi,Zk)=‖Xi-Zk‖

(8)

螢火蟲生物特性在改進(jìn)FA聚類算法中所起作用的對應(yīng)關(guān)系見表1。

Table 1 Corresponding relation of fireflies biologicalcharacteristics in improved FA clustering algorithm

3.2 基于最優(yōu)類中心擾動的螢火蟲聚類算法改進(jìn)之處

改進(jìn)1用聚類準(zhǔn)則函數(shù)Jc的值代表螢火蟲亮度I，即:

I=Jc

(9)

螢火蟲的亮度和目標(biāo)函數(shù)值相關(guān)，體現(xiàn)了螢火蟲所處位置的優(yōu)劣，位置越佳目標(biāo)值越好，亮度越高[8,19]。式(2)能夠滿足上述條件，但計算量較大，因此本文提出的基于改進(jìn)FA的聚類算法中直接用聚類準(zhǔn)則函數(shù)Jc的值來代表亮度，滿足條件的同時降低算法的復(fù)雜性。

改進(jìn)2對螢火蟲位置更新式(5)進(jìn)行了改進(jìn)：

α*rand*(cc-xi)

(10)

其中，cc為目前最優(yōu)聚類的類中心，β0、γ、α、rand意義同公式(5)。

(11)

其中，ni是第Γi聚類中的數(shù)據(jù)個數(shù)，y代表數(shù)據(jù)數(shù)值。

在基本FA算法中，螢火蟲被吸引向比較亮的螢火蟲移動，擾動項α(rand-0.5)加大了算法搜索區(qū)域，避免過早陷入局部最優(yōu)，增加了算法的局部尋優(yōu)能力，但導(dǎo)致算法整體收斂速度較慢，穩(wěn)定性比較差，當(dāng)待處理問題目標(biāo)函數(shù)值比較大的時候，擾動作用不明顯，容易使算法在局部最優(yōu)值附近波動。本文將擾動項改進(jìn)為α*rand*(cc-xi)，基于最優(yōu)類中心隨機(jī)擾動。實驗結(jié)果表明，改進(jìn)之后，算法收斂速度和穩(wěn)定性明顯改善。

改進(jìn)3最亮的螢火蟲按照式(12)進(jìn)行移動:

xbest=xbest+α*rand*(cc-xbest)

(12)

其中，xbest代表目前最亮的螢火蟲所處位置，cc含義同上。

在FA算法中，最亮的螢火蟲隨機(jī)移動，容易導(dǎo)致算法在局部最優(yōu)值或全局最優(yōu)值附近反復(fù)振蕩、收斂速度較慢、優(yōu)化精度降低，按照式(12)改進(jìn)之后，能有效地避免上述現(xiàn)象。

3.3 基于最優(yōu)類中心擾動的螢火蟲聚類算法步驟

步驟1設(shè)置算法參數(shù)：聚類個數(shù)C、螢火蟲個數(shù)N、最大吸引度β0、光強吸收系數(shù)γ、步長因子α、最大迭代次數(shù)maxiter；

步驟2初始化螢火蟲的位置(從數(shù)據(jù)集中隨機(jī)選出C個作為初始螢火蟲位置)，按照式(8)計算每個樣本點到各個聚類中心的距離，依此將樣本點劃分到離它最近的那個聚類中心所在的類中；

步驟3根據(jù)步驟2初始聚類的結(jié)果，利用式(9)計算螢火蟲的亮度，找出并記錄最亮螢火蟲的亮度、位置和聚類結(jié)果；

步驟4比較螢火蟲的亮度，如果Ii>Ij，表示螢火蟲j的聚類準(zhǔn)則函數(shù)值較小，所處位置較好，吸引螢火蟲i向自己移動，按照式(4)計算螢火蟲j對螢火蟲i的吸引度，按照式(10)和式(12)來更新螢火蟲i的位置；

步驟5螢火蟲位置更新完成后，重新進(jìn)行聚類，并更新螢火蟲的亮度，找出并記錄最亮螢火蟲的亮度、位置和聚類結(jié)果；

步驟6達(dá)到最大迭代次數(shù)則停止算法，否則轉(zhuǎn)到步驟3；

步驟7輸出結(jié)果。

4 仿真實驗及評價

為檢驗上述算法的正確性和有效性，在Matlab平臺上對其進(jìn)行了仿真實驗(Matlab 2011b、內(nèi)存4 GB、CPU為3.10 GHz)。

4.1 參數(shù)設(shè)置

文獻(xiàn)[10]對螢火蟲算法中的參數(shù)做了實驗對比，本文中β0、γ的取值采用文獻(xiàn)[10]中的結(jié)果，即β0=1，γ=0.8；最大迭代次數(shù)maxiter=150。

對參數(shù)α的取值，文獻(xiàn)[10]中的取值為0.01，在實驗過程中發(fā)現(xiàn)，α=0.01時算法的收斂效果不是很好，找到的最優(yōu)解不是很理想，因此，本文對α的取值重新做了實驗比較，用IRIS數(shù)據(jù)集，運行20次取平均值，分析結(jié)果如圖1所示。

Figure 1 Value of clustering criterion function for varying step factor圖1 步長因子對應(yīng)的聚類準(zhǔn)則函數(shù)值

由圖1可以看出，當(dāng)α=0.06時，聚類準(zhǔn)則函數(shù)的最小值和平均值均達(dá)到最優(yōu)，因此在仿真實驗過程中步長因子的取值為0.06。

4.2 收斂性分析

為了驗證基于IFA的聚類算法的可行性、有效性和收斂性，把基于IFA的聚類算法和FA算法、K-means算法、PSO算法做了對比，圖2、圖3和圖4分別顯示了在IRIS數(shù)據(jù)集上四種方法聚類的收斂曲線、基于IFA和K-means算法聚類準(zhǔn)則函數(shù)最優(yōu)值比較以及基于IFA、FA聚類后IRIS數(shù)據(jù)集樣本分布圖。由圖2可以看出，基于IFA的聚類算法收斂快而且比較平穩(wěn)，求解出的聚類準(zhǔn)則函數(shù)值明顯優(yōu)于FA和PSO聚類方法。K-means聚類算法[20～22]是一種比較經(jīng)典的聚類算法，圖2中IFA算法和K-means算法的收斂曲線比較接近，因此進(jìn)一步比較了二者的最優(yōu)值，使用IRIS數(shù)據(jù)集，程序運行20次，運行結(jié)果如圖3所示；從圖3a可以看出，K-means聚類算法由于對初始聚類中心比較敏感，導(dǎo)致其穩(wěn)定性較差，求出的最優(yōu)值波動比較明顯，從圖3b可以看出，基于IFA算法的聚類算法比較穩(wěn)定，求得的最優(yōu)值優(yōu)于K-means聚類算法。

Figure 2 Convergence curve of clustering for IRIS data set圖2 IRIS數(shù)據(jù)集聚類收斂曲線

Figure 3 Comparison of optimum values between IFA and K-means圖3 IFA和K-means聚類準(zhǔn)則函數(shù)最優(yōu)值比較

為了更好地對比基于IFA的聚類算法和基于FA的聚類算法的聚類效果，繪制了基于IFA(圖4a)、FA(圖4b)聚類后IRIS數(shù)據(jù)集樣本分布圖。由于IRIS數(shù)據(jù)集樣本具有四個屬性，因此在繪圖之前，先對IRIS數(shù)據(jù)集數(shù)據(jù)進(jìn)行了PCA處理，提取兩個主要成分進(jìn)行繪圖，效果如圖4所示。由圖4可以看出，改進(jìn)之后，聚類錯誤個數(shù)明顯減少，聚類效果優(yōu)于改進(jìn)之前。

Figure 4 Sample distribution of clustering for IRIS data set based on IFA and FA圖4 基于IFA、FA聚類后IRIS數(shù)據(jù)集樣本分布圖

4.3 聚類結(jié)果分析

本文從UCI標(biāo)準(zhǔn)數(shù)據(jù)集中選出了三個數(shù)據(jù)集IRIS(表2)、SONAR(表3)、WINE(表4)做了實驗。IRIS數(shù)據(jù)集包括三類共150個樣本，每個樣本有四個屬性；SONAR數(shù)據(jù)集包括兩類共208個樣本，每個樣本有60個屬性；WINE數(shù)據(jù)集包括三類共178個樣本，每個樣本有13個屬性。K-means和PSO的數(shù)據(jù)來自文獻(xiàn)[17]，F(xiàn)A和IFA數(shù)據(jù)為程序運行20次的平均值。

Table 2 Comparison of clustering criterion function andclustering error between different methods for IRIS data set

Table 3 Comparison of clustering criterion function andclustering error between different methods for SONAR data set

Table 4 Comparison of clustering criterion function andclustering error between different methods for WINE data set

由表2～表4可以看出，基于IFA的聚類算法能夠找到較好的聚類準(zhǔn)則函數(shù)值，平均值和最優(yōu)值相差比較小，說明算法比較穩(wěn)定，錯誤率和K-means、PSO、FA三種方法相比也明顯降低；K-means聚類算法由于對初始聚類中心比較敏感，導(dǎo)致算法不夠穩(wěn)定，最優(yōu)值波動比較明顯，其平均值和錯誤率普遍偏高；基本PSO算法和FA算法都屬于群智能優(yōu)化算法，具有群體智能和較好的全局尋優(yōu)能力，求出的最優(yōu)值和錯誤率也比K-means的要好，但是由于算法本身存在不足，導(dǎo)致求出的最優(yōu)值和錯誤率比IFA算法要差。同時，從表中也可以看出，同一種聚類方法在不同的數(shù)據(jù)集上聚類產(chǎn)生的效果也不全相同，也就是說，聚類結(jié)果和數(shù)據(jù)類型及維度也存在一定的關(guān)系，因此，在進(jìn)行聚類評價的時候要綜合考慮聚類準(zhǔn)則函數(shù)、錯誤率以及數(shù)據(jù)特點等各方面因素。

5 結(jié)束語

本文提出了基于最優(yōu)類中心擾動的螢火蟲聚類算法，有效地克服了FA算法收斂較慢、易于在局部最優(yōu)值或全局最優(yōu)值附近反復(fù)振動的缺陷，通過對三個標(biāo)準(zhǔn)數(shù)據(jù)集進(jìn)行聚類以及和FA、K-means、基本PSO算法進(jìn)行比較，仿真結(jié)果表明，基于最優(yōu)類中心擾動的螢火蟲聚類算法具有較好的收斂性和穩(wěn)定性，聚類效果較好。但是，在實驗中，光強吸收系數(shù)和步長因子都是設(shè)定的常數(shù)，把基于最優(yōu)類中心擾動的螢火蟲聚類算法應(yīng)用到不同規(guī)模的問題中時，算法表現(xiàn)出的全局搜索能力和穩(wěn)定性還有一定的差異，因此這兩個系數(shù)的自適應(yīng)特性還有待進(jìn)一步研究。

[1] Lei Xiu-juan. Swarm intelligent optimization algorithms and their applications[M]. Beijing:Science Press, 2012. (in Chinese)

[2] Sun Ji-gui, Liu Jie, Zhao Lian-yu. Clustering algorithms research[J]. Journal of Software, 2008, 19(1):48-61. (in Chinese)

[3] Maulik U, Bandyopadhyay S. Genetic algorithm-based clustering technique[J]. Pattern Recognition, 2000, 33(9):1455-1465.

[4] Kao Y, Cheng K. An ACO-based clustering algorithm[C]∥Proc of the 5th International Workshop on Ant Colony Optimization and Swarm Intelligence, 2006:340-347.

[5] Karaboga D, Ozturk C. A novel clustering approach:Artificial bee colony (ABC) algorithm[J]. Applied Soft Computing, 2011, 11(1):652-657.

[6] Yongming C, Mingyan J, Dongfeng Y. Novel clustering algorithms based on improved artificial fish swarm algorithm[C]∥Proc of the 6th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD’09), 2009:141-145.

[7] Van Der Merwe D W, Engelbrecht A P. Data clustering using particle swarm optimization[C]∥Proc of 2003 Congress on Evolutionary Computation(CEC’03), 2003:215-220.

[8] Yang X S.Nature-inspired metaheuristic algorithms[M]. Beckington:Luniver Press, 2008.

[9] Zang H, Zhang S, Hapeshi K. A review of nature-inspired algorithms[J]. Journal of Bionic Engineering, 2010, Supplement:232-237.

[10] Lukasik S, Zak S. Firefly algorithm for continuous constrained optimization tasks[C]∥Proc of the 1st International Conference on Computational Collective Intelligence (ICCCI 2009), 2009:97-106.

[11] Tilahun S L,Ong H C.Modified firefly algorithm[J]. Journal of Applied Mathematics, 2012, 12:1-12,doi:10.1155/2012/467631.

[12] Hassanzadeh T, Vojodi H, Moghadam A M E. An image segmentation approach based on maximum variance intra-cluster method and firefly algorithm[C]∥Proc of the 7th International Conference on Natural Computation (ICNC), 2011:1817-1821.

[13] Horng M H. Vector quantization using the firefly algorithm for image compression[J]. Expert Systems with Applications, 2012, 39(1):1078-1091.

[14] Christensen A L, O'Grady R,Dorigo M.From fireflies to fault-tolerant swarms of robots[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(4):754-766.

[15] Jati G K, Suyanto. Evolutionary discrete firefly algorithm for travelling salesman problem[C]∥Proc of the 2nd International Conference on Adaptive and Intelligent Systems, 2011:393-403.

[16] Senthilnath J, Omkar S N, Mani V. Clustering using firefly algorithm:Performance study[J]. Swarm and Evolutionary Computation, 2011, 1(3):164-171.

[17] Hassanzadeh T, Meybodi M R. A new hybrid approach for data clustering using firefly algorithm andK-means[C]∥Proc of the 16th CSI International Symposium on Artificial Intelligence and Signal Processing (AISP2012), 2012:7-11.

[18] Abshouri A A, Bakhtiary. A new clustering method based on firefly and KHM[J]. Journal of Communication and Computer, 2012, 9(4):387-391.

[19] Liu Chang-ping, Ye Chun-ming. Novel bioinspired swarm intelligence optimization algorithm:Firefly algorithm [J].Application Research of Computers, 2011, 28(9):3295-3297. (in Chinese)

[20] Chen Su-rong, Zhu Xiao-hui. Research ofK-means algorithm by fuzzy logic[J]. Computer Engineering & Science, 2012, 34(12):155-159. (in Chinese)

[21] Jiang Sheng-yi, Li Qing-hua. An enhancedk-means clustering algorithm[J]. Computer Engineering & Science, 2006, 28(11):56-59. (in Chinese)

[22] Kanungo T, Mount D M, Netanyahu N S, et al. An efficientk-means clustering algorithm:Analysis and implementation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002,24(7):881-892.

附中文參考文獻(xiàn)：

[1] 雷秀娟. 群智能優(yōu)化算法及其應(yīng)用[M].北京:科學(xué)出版社, 2012.

[2] 孫吉貴, 劉杰, 趙連宇. 聚類算法研究[J].軟件學(xué)報,2008,19(1):48-61.

[19] 劉長平, 葉春明. 一種新穎的仿生群智能優(yōu)化算法:螢火蟲算法[J].計算機(jī)應(yīng)用研究,2011, 28(9):3295-3297.

[20] 陳蘇蓉, 朱曉輝. 基于模糊邏輯的K-means算法研究[J].計算機(jī)工程與科學(xué), 2012, 34(12):155-159.

[21] 蔣盛益, 李慶華. 一種增強的k-means聚類算法[J].計算機(jī)工程與科學(xué), 2006, 28(11):56-59.