一種基于螢火蟲算法的模糊聚類方法

林睦綱，劉芳菊，童小嬌

1.衡陽師范學院計算機科學系，湖南衡陽 421008

2.南華大學計算機科學與技術學院，湖南衡陽 421001

一種基于螢火蟲算法的模糊聚類方法

林睦綱1，劉芳菊2，童小嬌1

1.衡陽師范學院計算機科學系，湖南衡陽 421008

2.南華大學計算機科學與技術學院，湖南衡陽 421001

針對模糊C-均值聚類對初始值敏感、容易陷入局部最優的缺陷，提出了一種基于螢火蟲算法的模糊聚類方法。該方法結合螢火蟲算法良好的全局尋優能力和模糊C-均值算法的較強的局部搜索特性，用螢火蟲算法優化搜索FCM的聚類中心，利用FCM進行聚類，有效地克服了模糊C-均值聚類的不足，同時增強了螢火蟲算法的局部搜索能力。實驗結果表明，該算法具有很好的全局尋優能力和較快的收斂速度，能有效地收斂于全局最優解，具有較好的聚類效果。

螢火蟲算法；模糊聚類；模糊C-均值聚類

1 引言

聚類分析是指按照事物間的相似程度對事物進行區分和分類的過程，使得同一類簇的數據相似性盡量大，不同類簇之間的數據相似性盡量小。它是數據挖掘、模式識別和圖像處理等研究的一種重要分析工具，已經廣泛應用于數據分析、機器學習、圖像分割、市場研究等領域中。聚類可分為硬聚類和模糊聚類，由于模糊聚類使用模糊隸屬度來描述數據對象隸屬各個類的不確定性，能夠比較客觀地反映現實世界；而且算法簡便易行，具有較好聚類效果，因而在許多實際問題中獲得廣泛的運用。模糊C-均值聚類（Fuzzy C-Means clustering，FCM）算法是模糊聚類分析中非常有效的一種算法，算法簡單，收斂速度快，局部搜索能力強。但它屬于一種局部搜索算法，隨機地選取聚類中心，以致其對初值和噪聲較為敏感，容易陷入局部最優，而得不到全局最優解，從而限制了該算法應用[1]。近年來，隨著各種群智能優化算法的提出和研究，許多學者運用蟻群算法[2-3]、微粒群算法[4-5]等來優化模糊聚類，克服FCM聚類算法的不足，取得較好的效果。

螢火蟲算法（Firefly Algorithm，FA）是英國劍橋大學學者Yang Xin-she在2008年根據自然界中螢火蟲通過發光吸引同伴的生物學特性行為而提出一種新的元啟發式群智能算法[6-7]。算法有效地刻畫了螢火蟲發光亮度的變化和吸引度的大小，模擬了螢火蟲根據同伴的亮度與吸引度大小進行搜索和移動、尋找同伴的原理，有效地實現了優化目標的目的。螢火蟲算法自提出以來，已經受到越來越多學者的關注和研究，文獻[7]利用螢火蟲算法求解多模態優化問題，文獻[8]應用螢火蟲算法求解連續約束優化問題，文獻[7-8]得出相同的結論：螢火蟲算法在性能上優于遺傳算法與粒子群算法。螢火蟲算法不僅原理簡單、參數少、易于實現；而且具有良好的全局尋優能力和一定的局部尋優能力，能快速地收斂于最優解的特點，目前已成功應用于路徑規劃[9]、工業優化[10-12]、經濟調度[13-14]、圖像處理[15]等領域。

本文嘗試在模糊C-均值聚類算法中引入螢火蟲算法，運用螢火蟲算法優化搜索FCM算法的聚類中心，充分發揮螢火蟲算法良好的全局尋優能力和模糊C-均值算法的較強的局部搜索特性，提出了一種基于螢火蟲算法的模糊聚類算法。算法有效地克服了模糊C-均值聚類對初始值敏感、容易陷入局部最優的缺陷，同時也進一步增強了螢火蟲算法的局部搜索能力。最后把新算法與傳統的FCM算法和粒子群聚類算法通過數值實驗進行比較，來驗證算法的有效性。

2 FCM聚類分析

給定數據集X={x1，x2，…，xn}，其中xi是包含d個屬性的數據對象（元素）(1≤i≤n)。聚類的目的就是將這n個對象劃分為c個以V=(v1，v2，…，vc)為聚類中心的模糊聚類簇(2≤c≤n-1)。uij表示數據對象xi隸屬于以vj為中心的類簇的隸屬度，模糊聚類問題的目標函數[16]可表示為：

式中uij∈[0，1]；i=1，2，…，n；j=1，2，…，c，U=(uij)為隸屬度矩陣，m是模糊權重系數，用來控制分類矩陣的模糊程度，一般取m≥1。

對于式（1）的優化問題結合式（2）的約束條件，應用Lagrange乘數法求解，可以得到uij和vj的取值公式為：

FCM算法就是求出使目標函數Jm(U，V)達到最小值的(U，V)。其基本思想是通過迭代更新(U，V)，使得目標函數最小。FCM算法的基本步驟可以描述如下：

步驟1設置參數與初始化，給定聚類數c和模糊權重系數m，設定迭代停止閾值ε，初始化聚類中心V。

步驟2根據式（3）計算隸屬度U。

步驟3根據式（4）更新聚類中心V。

步驟4如更新后的聚類中心與原聚類中心距離小于或等于設定的迭代停止閾值ε，則算法停止并輸出隸屬度U和聚類中心V，否則，轉向步驟2。

模糊C-均值算法是一種無監督的聚類方法，它通過在迭代過程中，不斷使目標函數減少來達到最優的，迭代過程在本質上是用梯度下降的方法搜索最優解，它在很大的程度上依賴聚類中心的初始值，如果初始值選擇不好，算法可能陷入局部最優解。因此它是一種局部搜索算法，存在對初始值和干擾敏感，易陷入局部最優等缺點。

3 螢火蟲算法

自然界中，螢火蟲利用其物種特有的閃光信號來定位并吸引異性，實現求偶交配和繁殖的目的。Yang Xin-she在文獻[6]中根據螢火蟲這種發光行為首次提出了一種隨機優化的螢火蟲算法，算法舍棄了螢火蟲發光的一些生物學意義，基于下面三個理想的規則[6-7]：

（1）所有的螢火蟲都是單性的，所以螢火蟲吸引同伴，與性別無關。

（2）吸引力的大小跟發光的亮度成正比，對于任意兩只螢火蟲，亮度小的螢火蟲被亮度大的螢火蟲吸引而向亮度大的螢火蟲方向移動。亮度和吸引度與螢火蟲之間的距離成反比，隨著距離的增加而減小。在一群螢火蟲中，沒有別的螢火蟲的亮度比其明亮時，則該螢火蟲將隨機移動。

（3）螢火蟲的亮度由給定問題的目標函數決定。

在螢火蟲算法中，亮度和吸引度是兩個關鍵要素。對于最大優化問題，最簡單的情況下，特定位置s的螢火蟲的亮度I(s)與目標函數f(s)成正比；對于最小化問題，亮度函數I(s)可取與遺傳算法中適應度函數的方式相同。螢火蟲的吸引度是相對的，它隨著螢火蟲i與螢火蟲j的距離的變化而變化，同時吸引度也與吸收因子有關，由于光傳輸媒介對光的吸收，因而光的亮度隨著與光源的距離增大而變小。吸引度β可定義為：

式中β0是最大吸引度，即r=0時的吸引度，γ是光的吸收因子。

螢火蟲i被比其明亮的螢火蟲j的吸引移動，其移動的位置由下式決定：

式中，si、sj為螢火蟲i和j在解空間的位置；α為步長因子，它是區間[0，1]上的常數；rand為隨機因子，它在區間[0，1]上服從均勻分布。式（6）右邊的第一部分表示螢火蟲當前位置，第二部分表示由于受其他螢火蟲吸引而引起的位置變化量，體現了算法的全局尋優能力，第三部分表示螢火蟲的局部隨機搜索移動，體現了算法的局部尋優能力，因此螢火蟲算法既具有較好的全局尋優能力，又具有一定的局部尋優能力。

螢火蟲算法基本過程為：首先螢火蟲群體隨機分布在問題的解空間，每只螢火蟲代表問題的一個可行解，螢火蟲的亮度決定了解的優劣，螢火蟲間的相對吸引度決定了螢火蟲的移動方向和更新。比較螢火蟲的亮度，亮度小的螢火蟲被亮度大的螢火蟲吸引，而向亮度大的螢火蟲移動，按式（6）更新自己的位置，這樣不斷循環，尋找更優解，從而達到目標最優。

4 基于螢火蟲算法的模糊聚類方法

由于FCM聚類算法采用的梯度下降的方法尋找目標函數的最優解，如果算法的初始值選擇不當，算法會陷入局部最優，而不能逃離局部最優點。針對模糊C-均值聚類算法對初始值和干擾敏感，易陷入局部最優等不足，結合螢火蟲算法良好的全局尋優能力和較強的局部尋優能力，收斂速度較快等優點。為此，本文把螢火蟲算法與模糊C-均值聚類方法結合起來，提出了一種基于螢火蟲算法的模糊聚類方法（FAFCM）。該算法的思路是：利用螢火蟲算法尋找聚類中心，然后根據聚類中心進行模糊聚類，從而克服傳統FCM算法對初始值敏感，易于陷入局部最優等缺陷。

在基于螢火蟲算法的模糊聚類方法中，每一只螢火蟲的位置用聚類中心表示，其位置為向量V=(v1，v2，…，vc)，其中vi為第i個類簇中心。螢火蟲的亮度由模糊聚類的目標函數決定，根據螢火蟲算法的特點，可定義螢火蟲的亮度函數為：

式中xi(1≤i≤n)是數據集X={x1，x2，…，xn}的第i個的數據對象。

基于螢火蟲算法的模糊聚類算法的基本步驟如下：

步驟1設置算法參數及初始化螢火蟲群，設置螢火蟲群的規模即螢火蟲群中螢火蟲數目N，最大吸引度β0，光的吸收因子γ，步長因子α，聚類簇數c，最大迭代次數maxT，以及k，m；初始化群中螢火蟲的位置V1，V2，…，VN。

步驟2對于每個Vi根據式（3）計算隸屬度矩陣Ui，然后根據亮度函數式（7）計算群中每只螢火蟲的亮度I(Vi)；并根據亮度對群中的螢火蟲進行升序排序。

步驟4輸出最優解。

5 數值實驗與分析

為了驗證與分析本文算法（FAFCM）的有效性與可行性，選取UCI標準數據庫中IRIS、Glass Identification兩個數據集對算法進行測試，并且把實驗結果與標準FCM算法、基于粒子群算法的模糊聚類（PSOFCM）進行比較。Iris數據集包括3類樣本，共150個樣本組成，每個樣本包含4個屬性，每類樣本均為50個。Glass數據集包括6類樣本，共214個樣本組成，每個樣本包含9個屬性。文獻[5]經過1 000次實驗發現，IRIS數據集聚類問題目標函數是單極值的，而Glass數據集聚類問題目標函數有兩個極值，是多極值的，因而選擇這兩個數據集進行數值實驗具有代表性。在實驗時，為避免每維數據幅值對聚類結果的影響，對這兩個數據集的數據進行線性歸一化預處理，使每一維數據的范圍為[0，1]。

為了衡量聚類結果，在實驗中主要比較下面三個指標：

（1）模糊聚類的目標函數

對模糊聚類來說，目標函數越小越好，聚類越精確，誤差越??；劃分系數和劃分熵是常用的衡量聚類有效性函數，劃分系數越大，聚類結果越好；劃分熵越小，聚類效果越好。

在Matlab2011b平臺下實現運行算法，算法的參數設置如下：模糊權重系數m=2，ISIR數據集聚類數為3類，最大迭代次數maxT=50，Glass數據集聚類數為6類，最大迭代次數maxT=300；對于FAFCM算法β0=1.0，γ=0.9，α=0.1，k=2。對于PSOFCM算法，慣性權重w=0.2，學習因子c1=c2=2.0。在測試中，FCM算法、PSOFCM算法與FAFCM算法分別運行30次最好的結果，實驗結果如表1所示，迭代過程如圖1，2所示。

表1 三種算法聚類有效性比較結果

圖1 三種算法對IRIS數據集的聚類迭代過程

圖2 三種算法對Glass數據集的聚類迭代過程

三種算法對每個數據集取不同的初始聚類中心分別運行30次，結果如表1所示，對于IRIS數據集，三種算法均能達到相同的結果；但對于Glass數據集，FCM算法選擇不同的初始聚類中心，得到不同的目標函數值，而另外兩種算法均得到相同的結果。從圖1，2可以發現，FCM算法具有較快的收斂速度，FAFCM算法在收斂速度上比FCM算法略慢，但比PSOFCM算法要快很多。分析其原因是因為FAFCM算法和PSOFCM算法是一種隨機搜索算法，具有較好的全局搜索能力，其能逃離局部極值而達到全局最優；而FCM算法用最速梯度下降的方法搜索，局部搜索能力較好，全局搜索能力較差，具有較快收斂速度。對于多極值問題，一旦陷入局部極值點，就無法跳出局部極值，而陷入局部最優。對于IRIS數據集聚類是單極值的，FCM算法不存在陷入局部收斂的情況，三種算法都能收斂到全局最優；而對于Glass數據集，FCM算法易陷入局部最優。FAFCM算法與PSOFCM算法比較，由于在螢火蟲算法中，每個螢火蟲幾乎是相互獨立的，而粒子群算法中的粒子之間有一定的依賴性，因此在最優解附近，螢火蟲算法仍然有較好的尋優能力。綜上所述，FAFCM算法不僅有較強的全局搜索能力，而且有較快的收斂速度，具有較好的綜合性能。

6 結束語

本文結合螢火蟲算法具有較好的全局搜索能力，較快的收斂速度等優點，提出基于螢火蟲算法的模糊聚類算法。算法用螢火蟲算法迭代搜索聚類中心進行模糊聚類，有效地克服了FCM算法對初始值敏感，易于陷入局部最優的缺陷。通過對具體標準數據集進行測試以及與標準FCM算法、PSO-FCM算法的比較，實驗結果表明，基于螢火蟲算法的模糊聚類算法能有效地收斂于全局最優解，具有較好的聚類效果，算法有效可行。但在實驗中，也發現在設置螢火蟲算法的步長因子、吸收因子和最大吸引度等參數時，由于設置為固定的常數，對算法全局搜索能力與局部搜索能力的平衡有一定影響，因此螢火蟲算法參數自適應調整還有待進一步研究。

[1]Peng J M，Xia Y.A new theoretical framework for K-means clustering[C]//Chu Wesley，Lin TsauYoung.Foundation and Recent Advances in Data Mining.Berlin：Springer-Verlag，2005：79-96.

[2]Fei Wang，Dexian Zhang，Na Bao.Fuzzy document clustering based on ant colony algorithm[C]//Proceedings of the 6th International Symposium on Neural Networks：Advances in Neural Networks-Part II，2009：709-716.

[3]Runkler T A.Ant colony optimization of clustering moels[J]. International Journal of Intelligent Systems，2005，20（12）：1233-1261.

[4]Izakian H，Abraham A.Fuzzy C-means and fuzzy swarm for fuzzy clustering problem[J].Expert Systems with Applications，2011，38（3）：1835-1838.

[5]Li Chaoshun，Zhou Jianzhong，Kou Pangao，et al.A novel chaotic particle swarm optimization based fuzzy clustering algorithm[J].Neurocomputing，2012，83（4）：98-109.

[6]Yang Xinshe.Nature-inspired metaheuristic algorithms[M]. [S.l.]：Luniver Press，2008：83-96.

[7]Yang Xinshe.Firefly algorithms for multimodal optimization[C]//Proc of the 5th International Conference on Stochastic Algorithms：Foundations and Applications.Berlin：Springer-Verlag，2009：169-178.

[8]?ukasik S，?ak S.Firefly algorithm for continuous constrained optimization tasks[M]//Computational Collective Intelligence,Semantic Web，Social Networks and Multiagent Systems.Berlin Heidelberg：Springer，2009：97-106.

[9]劉鵬，劉弘，鄭向偉，等.基于改進螢火蟲算法的動態自動聚集路徑規劃方法[J].計算機應用研究，2011，28（11）：4146-4149.

[10]劉長平，葉春明.一種新穎的仿生群智能優化算法：螢火蟲算法[J].計算機應用研究，2011，28（9）：3295-3297.

[11]Aungkulanon P，Chaiead N，Luangpaiboon P.Simulated manufacturing process improvement via particle swarm optimization and firefly algorithms[C]//Proceedings of the International MultiConference of Engineers and Computer Scientists，Hong Kong，2011：1123-1128.

[12]Yousif A，Abdullanh A H，Nor S M，et al.Scheduling jobs on grid computing using firefly algorithm[J].Journal of Theoretical and Applied Information Technology，2011，33（2）：155-164.

[13]楊嬌，葉春明.應用新型螢火蟲算法求解Job-shop調度問題[J].計算機工程與應用，2013，49（11）：213-215.

[14]Apostolopoulos T，Vlachos A.Application of the firefly algorithm for solving the economic emissions load dispatch problem[J].International Journal of Combinatorics，2010，2011（9）：1-23.

[15]Tahereh H，Hakimeh V，Fariborz M.Non-linear grayscale image enhancement based on firefly algorithm[C]//Bijaya P，Swagatam D.Swarm，Evolutionary，and Memetic Computing.Berlin：Springer，2011：174-178.

[16]Bezdeck J C，Ehrlich R，Full W.FCM：the Fuzzy C-Means clustering algorithm[J].Computers and Geoscience，1984，23（2）：16-20.

LIN Mugang1,LIU Fangju2,TONG Xiaojiao1

1.Department of Computer Science,Hengyang Normal University,Hengyang,Hunan 421008,China
2.School of Computer Science and Technology,University of South China,Hengyang,Hunan 421001,China

For local optimum and initial sensitive problems with fuzzy C-means clustering,a new fuzzy clustering algorithm based on firefly algorithm is proposed.By incorporating the capacities of local and global search of firefly algorithm and FCM,taking the optimal clustering center of firefly algorithm as the initialized value of the FCM,and then clustering analysis is processed by FCM.The new algorithm overcomes FCM trapped local optimum and being sensitive to initial value effectively,and enhances the capacity of local search of firefly algorithm.The experimental results show that the new algorithm not only has better global search capacity and faster convergence speed but also has better clustering efficiency.

firefly algorithm;fuzzy clustering;fuzzy C-means clustering

A

TP391

10.3778/j.issn.1002-8331.1212-0004

LIN Mugang,LIU Fangju,TONG Xiaojiao.Fuzzy clustering algorithm based on firefly algorithm.Computer Engineering and Applications,2014,50（21）：35-38.

國家自然科學基金（No.11171095）；湖南省自然科學衡陽聯合基金項目（No.10JJ8008）；湖南省科技計劃項目（No.2010FJ4077）；湖南省重點學科建設項目（運籌學與控制論）；湖南省衡陽市科技發展計劃項目（No.2014KJ21）。

林睦綱（1972—），男，博士研究生，講師，CCF學生會員，研究方向為智能計算，計算機算法；劉芳菊（1974—），女，講師，研究方向為智能計算，網絡安全；童小嬌（1962—），女，博士，教授，博士生導師，研究方向為最優化理論與計算方法，電力市場。E-mail：linmu710@163.com

2012-12-03

2013-03-11

1002-8331（2014）21-0035-04

CNKI出版日期：2013-03-19，http://www.cnki.net/kcms/detail/11.2127.TP.20130319.1424.005.html