一種協作的螢火蟲算法在聚類問題上的應用

莫愿斌 馬彥追 鄭巧燕

(1.廣西民族大學,南寧 530006；2.廣西混雜計算與集成電路設計分析重點實驗室,南寧 530006)

在對化工過程的分析與控制過程中，通常面臨大量的數據處理問題。對數據集進行精確合理的聚類分析是數據處理的一個有效步驟，因此，在化工過程的建模、分析與控制中，數據的聚類分析廣受關注[1～3]。

聚類分析是數據挖掘領域中的一個重要組成部分，是最重要的數據分析方法之一。它是根據數據集中數據之間的相關性，按照特定的準則，將其分為若干類的過程，其目的是使屬于同一類的元素特性相似度較大，而不同種類元素之間的差異性較大。關于聚類分析的研究已有了很長的歷史，其重要性越來越受到人們的關注。作為非監督學習的方法，聚類分析能夠識別研究對象特征數據的內在關系，是一種非常有效的信息處理方法。目前已經有很多種聚類的算法，文獻[4]提出了一種基于擴展的多密度網格聚類算法，具有較高的聚類精度，但聚類結果對參數的設置較為敏感；文獻[5]把傳統的模糊C均值聚類算法與自適應策略結合起來，形成了新的模糊聚類算法，該算法有較快的收斂速度，但是選擇一個合適的模糊指數較為困難；文獻[6]提出一種改進的最小生成樹自適應分層聚類算法，對于形狀比較簡單的聚類能夠得到較好的聚類結果，但不能發現形狀比較復雜的聚類；最經典的聚類算法是K-均值算法，近些年來，K-均值聚類算法已應用到許多領域，但該算法存在對初始值敏感及容易陷入局部最優值等不足。隨著智能算法的快速發展，許多學者把智能算法應用于聚類問題中，文獻[7]提出了一種基于改進粒子群算法的聚類算法；文獻[8]通過分析螞蟻聚類算法和K-均值算法的基本思想，將兩種算法結合得到混合聚類算法；文獻[9]把蜂群算法應用到聚類問題中。雖然這些算法取得了一定的效果，但是容易陷入局部最優，算法的收斂性和穩健性方面還有待改進。

螢火蟲算法(Firefly Algorithm，FA)是2008年由英國劍橋學者Yang X S提出的一種啟發式智能優化算法[10]，該算法一經提出，受到國內外許多學者的關注和研究，并且已經成功應用于組合優化[11]、路徑規劃、圖像處理[12]及經濟調度[13]等領域。但螢火蟲算法也存在著易陷入局部最優及求解精度低等不足。筆者將協作搜索機制加入到FA中，提出了一種協作的螢火蟲算法(CFA)，并將改進的算法應用到聚類問題中。通過對多個UCI數據集進行仿真，實驗結果表明：該算法具有更好的全局收斂能力，聚類質量良好。

1 基于協作的螢火蟲算法①

1.1 基本螢火蟲算法

螢火蟲算法是模擬螢火蟲發光的生物學特性表現出來的社會性行為而設計的隨機優化算法，螢火蟲在搜索區域內移向位置更優的同伴，實現位置的更新。在螢火蟲算法中存在兩個關鍵的要素：自身亮度和吸引度。自身亮度反映了螢火蟲位置的優劣，亮度小的螢火蟲會被亮度大的吸引，并向亮度大的螢火蟲方向移動；吸引度影響著螢火蟲所要移動的距離。通過螢火蟲的移動，每個個體自身亮度和吸引度得到不斷更新，最終實現目標優化的目的。一個螢火蟲在坐標為X的位置，其亮度I可以取為I(X)=f(X)，X的位置越好，它的亮度就越大，吸引度的大小和亮度的大小是成正比的，且隨著它們之間距離的增加而變小，在熒光傳輸的過程中吸引度的大小還和介質吸收因子有關。因此，一個螢火蟲對距離其r處的亮度I(相對亮度)可以表示為:

I(r)=I0e-γrij

(1)

式中I0——螢火蟲對距離其r=0處的熒光亮度；

rij——螢火蟲i到螢火蟲j的歐式距離；

γ——介質吸收因子。

螢火蟲的吸引度β被定義為:

β=βmin+(β0-βmin)e-γr2

(2)

式中β0——螢火蟲對距離其r=0處的吸引度；

βmin——最小吸引度，βmin=0.2。

螢火蟲i被螢火蟲j吸引的移動公式為:

(3)

式中xi、xj——螢火蟲i和j的位置；

rand——區間[0,1]上服從均勻分布的隨機因子；

α——步長因子。

1.2 協作搜索策略

在螢火蟲算法中，每個螢火蟲個體都是一個D維向量，它們的目標都是產生最好的解。對于一個D維向量，它的某一維在一次迭代中可能找到了最優的值，但是此個體的適應值是通過D維向量計算的，因此，很有可能此個體不是最優的結果，而此個體找到的某一維的最優值也將被舍去，希望通過每個個體的協作找到向量中每一個元素的最優值，進而得到更優的解。筆者把協作搜索策略應用到FA中，提出了一種協作的螢火蟲算法(CFA)，種群中所有個體通過自身信息的交流協作，找到最優解。在CFA中，最優位置為gbest，f(x)為目標函數。分別用每個螢火蟲個體的第j(1,…,D)維代替gbest中相應的元素變成newgbest，代入目標函數計算適應值，如果f(newgbest)優于f(gbest)，則用newgbest代替gbest，從而找出第j維的最優值。

2 聚類問題的數學描述

(4)

其中Zl為第l個聚類的中心，‖Xi-Zl‖是樣本Xi到聚類中心Zl的歐式距離。J的值越小，則表明聚類效果越好[7,8]。

3 基于協作的螢火蟲聚類算法

3.1 螢火蟲編碼

在基于協作的螢火蟲算法的聚類算法中，螢火蟲的位置采用基于聚類中心的實數編碼方式，假設要求把數據樣本分為K類，數據維數為d，每個螢火蟲是由K個聚類的中心組成的向量。這樣，螢火蟲的位置為Zi(Ci1,Ci2,…，Cij,…,CiK),其中Cij表示第i個螢火蟲的第j個聚類中心的坐標向量，每個聚類中心是d維向量，所以每只螢火蟲的位置是K×d維向量。

3.2 基于協作的螢火蟲聚類算法的實施步驟

基于協作的螢火蟲聚類算法實施的具體步驟為：

a. 初始化算法的參數。螢火蟲數目m，步長因子α0，最大吸引度β0，最小吸引度βmin，介質吸收因子γ，最大迭代次數maxT。讀入數據集，隨機初始化m個螢火蟲的位置Zi(Ci1,Ci2，…,Cij,…,CiK)(i=1,…,m),初始化的每個螢火蟲是數據集中隨機的K個數據樣本組成的向量。

b. 利用式(4)計算各自的目標值作為自己的最大亮度I0，記錄最優位置gbest。

c. 根據式(1)、(2)計算各個螢火蟲之間的相對亮度I和吸引度β，依照I的大小確定螢火蟲的移動方向。利用式(3)對螢火蟲的位置進行更新。隨機擾動處在最好位置的螢火蟲。

d. 進行協作搜索策略，得到newgbest。重新計算更新后螢火蟲的亮度。

e. 判斷是否滿足結束條件，若是，轉到步驟f，否則轉到步驟c，進入下一次搜索。

f. 輸出最優位置和最優解。

4 仿真實驗與實驗結果分析

實驗采用了UCI機器學習庫中的6個數據集，分別為Iris、Glass、Wine、Lenses、Hayes-Roth和Liver Disorders，這些數據集的信息統計見表1。

表1 數據集信息統計

實驗環境如下：

處理器 AMD Phenom(tm)8400

主頻 1.05GHz

內存 1.75GB

操作系統 Windows XP

集成開發環境 Matlab2012a

在CFA中，設定種群規模為N=20，步長因子α=0.5，最大吸引度β0=1，最小吸引度βmin=0.2，介質吸收因子γ=1，最大迭代次數為100。對每個數據集獨立運行20次，表2列出了20次實驗得到的最優值、最差值、平均值和標準差，并與K-均值算法、ABC和PSO進行比較，給出了數據集適應度函數的收斂效果圖，如圖1～6所示。

表2 不同算法的聚類性能比較

圖1 Iris的收斂效果

圖2 Glass的收斂效果

圖3 Wine的收斂效果

圖4 Lenses的收斂效果

圖5 Hayes-Roth的收斂效果

圖6 Liver Disorders的收斂效果

從表2的數據結果可以看出，CFA得到的結果明顯比其他算法得到的結果更優，聚類質量更高。對于數據集Iris，CFA得到的最優值、最差值和平均值都是幾個聚類算法中的最小值，說明CFA的聚類質量最高，并且標準差的精度達到了10-5，具有很強的魯棒性。對于數據集Glass，CFA的最優值最小，最差值也要優于FA、PSO的最優值，平均值和標準差也是幾個算法中的最小值，ABC的結果次優。對于數據集Wine，CFA的聚類效果最好，ABC、PSO的最優值很接近CFA的最優值，從平均值和標準差來看，PSO的結果要優于ABC，而CFA的結果最優，K-均值算法的聚類效果最差。對于數據集Lenses，CFA得到的最優值、最差值、平均值和標準差都比其他算法的結果要小，聚類效果最優，PSO的結果與ABC的結果相差不大。對于數據集Hayes-Roth，CFA相比較其他算法，能夠得到更優的值，FA的結果是最大的，效果最差。對于數據集Liver Disorders，ABC得到的最優值和平均值要優于CFA的結果，但CFA的最差值和標準差優于ABC的結果，CFA比ABC有更強的魯棒性，FA的聚類效果優于PSO和K-均值算法的聚類效果。從圖1～6可以看出，CFA相比較其他算法來說，能夠在較少的迭代次數下找到較好的適應度值。

5 結束語

數據的聚類分析是化工過程分析、控制及建模等的重要環節。目前各種不同的聚類算法均存在一定的不足，提出了一種基于協作的螢火蟲聚類算法(CFA)，該算法是將協作搜索機制加入到螢火蟲算法中，并應用到聚類問題中，通過對6個UCI數據集的仿真實驗，結果證明：算法是有效的，達到了較好的聚類效果，CFA的聚類性能優于PSO、ABC和K-均值算法。