莫愿斌 馬彥追 鄭巧燕

(1.廣西民族大學(xué),南寧 530006；2.廣西混雜計算與集成電路設(shè)計分析重點(diǎn)實(shí)驗(yàn)室,南寧 530006)

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

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

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

1 基于協(xié)作的螢火蟲算法①

1.1 基本螢火蟲算法

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

I(r)=I0e-γrij

(1)

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

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

γ——介質(zhì)吸收因子。

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

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

(2)

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

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

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

(3)

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

rand——區(qū)間[0,1]上服從均勻分布的隨機(jī)因子；

α——步長因子。

1.2 協(xié)作搜索策略

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

2 聚類問題的數(shù)學(xué)描述

(4)

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

3 基于協(xié)作的螢火蟲聚類算法

3.1 螢火蟲編碼

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

3.2 基于協(xié)作的螢火蟲聚類算法的實(shí)施步驟

基于協(xié)作的螢火蟲聚類算法實(shí)施的具體步驟為：

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

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

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

d. 進(jìn)行協(xié)作搜索策略，得到newgbest。重新計算更新后螢火蟲的亮度。

e. 判斷是否滿足結(jié)束條件，若是，轉(zhuǎn)到步驟f，否則轉(zhuǎn)到步驟c，進(jìn)入下一次搜索。

f. 輸出最優(yōu)位置和最優(yōu)解。

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

實(shí)驗(yàn)采用了UCI機(jī)器學(xué)習(xí)庫中的6個數(shù)據(jù)集，分別為Iris、Glass、Wine、Lenses、Hayes-Roth和Liver Disorders，這些數(shù)據(jù)集的信息統(tǒng)計見表1。

表1 數(shù)據(jù)集信息統(tǒng)計

實(shí)驗(yàn)環(huán)境如下：

處理器 AMD Phenom(tm)8400

主頻 1.05GHz

內(nèi)存 1.75GB

操作系統(tǒng) Windows XP

集成開發(fā)環(huán)境 Matlab2012a

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

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

圖1 Iris的收斂效果

圖2 Glass的收斂效果

圖3 Wine的收斂效果

圖4 Lenses的收斂效果

圖5 Hayes-Roth的收斂效果

圖6 Liver Disorders的收斂效果

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

5 結(jié)束語

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