胡紹方，周鳳

　　（貴州大學 計算機科學與技術學院，貴州 貴陽 550025）

　　摘要：針對FCM聚類算法對初始聚類中心敏感和易陷入局部最優解的缺點，提出一種基于細菌覓食的細菌覓食聚類算法。將細菌覓食算法與FCM算法相結合，并以反向學習來初始化細菌種群，增加種群的多樣性和代表性，求得的最優解作為FCM算法的初始聚類中心，使FCM算法對初始聚類中心的依賴性降低，同時也降低了陷入局部最優解的可能性，提高了算法的穩定性。實驗結果表明，該算法克服了FCM算法穩定性差的缺點，收斂速度更快，具有良好的性能和聚類效果。

　　關鍵詞：細菌覓食優化算法；聚類；FCM

0引言

　　隨著計算機技術的發展，信息量的倍增，數據挖掘技術是當前技術研究的重點，而聚類是數據挖掘技術中的一個重要分支，它是一種以相似性為基礎的無監督的機器學習技術，其目的是將目標數據集分成若干個簇，使得同簇內的數據相似度盡可能高，不同簇的數據相似度盡可能低。聚類技術目前應用非常廣泛，在機器學習、模式識別、Web挖掘［1］領域等都有很好的應用前景。

　　模糊C均值(Fuzzy C Means, FCM)是聚類技術的一個重要方法，它是1973年由DUNN J C［2］和BEZDEK J［3］提出的，屬于基于目標函數的模糊聚類算法。FCM算法簡單且快速，其應用非常廣泛，目前已形成了龐大的體系。但是FCM算法也存在缺點，主要表現在［4］:

　?。?）初始聚類中心的數目必須提前給出，而且這個數目的取值至今沒有規律可循；

　?。?）對于不規則簇和帶狀簇識別困難，而且對噪聲敏感；

　?。?）初始聚類中心的選取是隨機的，但不同的選取結果，對聚類結果有較大影響；

　?。?）算法運行過程中比較容易陷入局部極值點，從而得不到全局最優值。

　　針對FCM算法的這些缺點，本文把并行搜索能力強、易于跳出局部極值的細菌覓食算法引進到FCM算法，來改善傳統FCM算法的弊端。最后，運用經典的UCI數據集和自構造數據集進行測試實驗，結果表明這種改進算法是可行的并且提高了聚類的準確率。

1FCM算法　

　　FCM算法是通過不斷的迭代逼近最優解的一種聚類算法。對于集合X={x1,x2,..,xj,..,xn},把這n個數據xj(j=1,2,...,n)分成C={c1,c2,..,ci,..cc}的c個簇，用隸屬度來刻畫數據xj屬于某個類的程度，通常記為uij，取值范圍為［0,1］且∑ci=1uij=1，計算每個分組的聚類中心，使目標函數（即非相似性指標的價值函數）達到最小。在聚類過程中，把聚類生成的類看成模糊集合，所以隸屬矩陣U中的每個點的分量只能取值在0~1間的元素。

　　FCM算法的目標函數：

　　其中，m是一個加權指數，一般是大于1的數。

　　通過拉格朗日公式，要使式（1）達到最小，必須滿足以下兩個條件：

　　ci=∑nj=1umijxj∑nj=1umij(2)

　　uij=1∑ck=1ci－xjck－xj2/(m－1)(3)

　　根據上述兩個條件公式，可以看出FCM算法其實是一個簡單的迭代計算過程，其算法描述如下：

　　(1)設置初始化參數值，包含模糊加權參數值m和聚類數c，以及最大迭代的次數T和算法終止目標精度誤差ε；

　　(2)隨機選中初始化聚類中心C0；

　　(3)根據式（3）計算隸屬度矩陣U(t)；

　　(4)根據式（2）迭代計算聚類中心Ct+1；

　　(5)如果J(t+1)－J(t)<ε或者t>T，則算法結束，否則返回步驟（3）。

　　近年來對FCM算法改進的研究也有很多，2005年周新華、黃道［5］提出了一種利用蟻群算法來改進模糊c均值聚類算法，同年鄭巖［6］等人提出了一種利用遺傳算法來實現動態模糊聚類的算法，施美珍［7］在2012年也提出了利用粒子群來改進模糊聚類的方法，2014年林睦綱［8］等人提出了基于螢火蟲算法的模糊聚類。在FCM算法的步驟中，必須先選中初始化聚類中心，然后才執行迭代運算，而這種操作方式不能一次就得出最終想要的聚類結果，需要反復運行多次才能得到理想聚類效果。因為FCM算法對初始聚類中心具有很強的依賴性。所以，可以采用另外的算法預先尋找、確定初始聚類中心，然后根據這些初始聚類中心再執行FCM算法，這樣不需多次運行FCM算法就可以得到相對準確的結果。

2細菌覓食算法

　　細菌覓食算法(Bacterial Foraging Optimization, BFO)是PASSINO K M［9］于2002年提出的一種新型仿生類群體智能算法。它主要通過趨化、繁殖、遷徙三種算子進行位置更新和最優解搜索，進而實現種群的進化。該算法的優點［10］在于并行搜索、易跳出局部極值等。

　　在細菌的這三種算子中，細菌向食物源區域靠攏的行為被稱為趨化算子。在趨化算子中，細菌的運動行為有兩種：一種是細菌向隨機方向前進單位步長，把其定義為翻轉算子，另外一種是如果細菌執行翻轉算子一次后，其適應度值得到改善，則細菌沿同一方向繼續移動，直到細菌的適應度值不再改善或達到最大的移動步數，把其定義為前進算子。細菌達到最大趨化算子次數后，將執行繁殖算子，細菌的繁殖行為同樣遵循自然界的“優勝劣汰，適者生存”的原則。細菌生活的區域可能突然會發生劇烈變化，這樣可能導致生活在這個區域的細菌種群死亡或遷徙到一個新的適合的生活區域，在該算法中把這種現象描述成為遷徙算子。在這三種算子中，趨化算子為算法的核心部分，它可以提高細菌的局部搜索精度，繁殖算子可以增加細菌的快速收斂性能，而遷徙算子的存在則有利于趨化算子跳出局部極值進而尋找全局最佳值，三種算子相互配合以達到快速準確地尋找全局最優解。

　　假設Xi(j,k,l)表示細菌個體i的位置，其中j表示j代趨化算子，k表示細菌k代繁殖算子，l表示l代遷徙算子。

　　細菌的位置按照下式進行調整更新：

　　Xi(j+1,k,l)=Xi(j,k,l)+rand()*step*φ(i)(4)

　　φ(i)=Xi(j,k,l)－Xrand(j,k,l)Xi(j,k,l)－Xrand(j,k,l)(5)

　　其中，step是每一步前進的步長，φ(i)表示細菌隨機翻滾的方向，Xrand(j,k,l)表示當前個體Xi(j,k,l)鄰域內的一個隨機位置。如果翻轉后適應度值得到改善，則繼續沿著翻轉的方向前進，細菌個體i的適應度值用fiti來表示：

　　其中Jc為總的類內離散度。

3基于細菌覓食的FCM聚類算法

　　對數據的聚類實際上就是對函數進行優化的過程，通過對此迭代搜尋目標函數的最優解，直到得到最佳的聚類效果。繁殖算子的“優勝劣汰”原則可以保留優秀的初始聚類中心，遷徙算子可以有效地幫助跳出局部最優解，體現了算法的全局搜索性能。

　　基于細菌覓食的FCM聚類算法（Bateria Foraging Optimization Fuzzy C Means,BFFM)的思想：首先利用BFO算法的并行搜索等優點求得群體最優解，以這些最優解作為FCM算法的初始聚類中心，然后利用FCM算法對初始聚類中心進行進一步優化計算，最后求得聚類結果。此算法克服了FCM算法對隨機選擇的初始聚類中心的敏感，提高了算法的穩定性，提升了算法的收斂速度。

　　3.1基于反方向學習的初始化

　　初始種群是算法進行搜索的起點，而初始種群的分布狀況以及好壞在一定程度上會影響算法的求解效率和最終結果。細菌覓食算法采用的是隨機產生初始群體的初始化方式，這種方式不能保證所產生的初始群體的均勻分布?；诜聪驅W習［11］的群體初始化方法，不僅提升了初始種群的多樣性，同時也可以使初始群體比較均勻地分布在解空間內，提高算法的運行效率。具體步驟為:

　?。?)初始化種群，按照種群規模數目N初始化，并指定聚類數目c，然后再將每個細菌隨機地指派為某一類，把其最初的聚類劃分，作為細菌i的位置編碼，同時計算各類的聚類中心，隨機生成的初始解每一維分量都滿足Xid∈［ad,bd］(d∈(1,2,...,D)，D為維數，a、b分別為樣本數據中對應維的上、下限。

　?。?)為每一個上一步產生的初始解生成其相應的反向解，它在每個維度的分量按下式計算：

　　vid=ad+bd－Xid,d∈D（7）

　　(3)把上面兩步產生的解合并，計算它們的適應度值并排序，選出前N個適應度較高的解作為初始種群。

　　3.2算法的實現步驟

　　(1)參數、種群的初始化。設定遷移次數Ned、繁殖次數Nre、趨化次數Nc、基本遷移概率Ped、細菌規模數S和游動次數Ns的初始值。

　　(2)種群初始化。本文采用基于反向學習的方法產生初始種群，并隨機選取c個細菌作為初始聚類中心。

　　(3)執行趨向行為。細菌i在執行趨向行為過程中主要進行翻轉行為和游動行為。此過程中按照式(4)和式(5)更新細菌的位置。

　　(4)執行復制行為。在復制之前，先按照細菌種群的適應度的大小降序排列，保留前一半適應度值較大的個體，去除掉另外一半適應度值小的個體，并對保留的這些個體進行一分為二的分裂復制，這樣不但完成了單次復制，而且保證了細菌種群規模不變。若滿足復制操作的終止條件，則進行遷徙操作，否則返回步驟（2）。

　　（5）以設定的概率Ped執行遷徙行為。大于遷徙概率就執行遷徙行為，即此細菌將消失，并隨機在一個新的位置生成一個新的細菌，否則細菌將維持原來的位置不動。如果遷徙行為達到設置的最大迭代次數，則進入聚類過程，否則返回（2）。

　　（6）執行FCM聚類過程。將細菌尋優結束時最終的位置作為FCM算法的初始聚類中心，開始執行FCM算法聚類過程進行聚類。

4實驗及結果

　　為了驗證BFFM算法的可行性和有效性，使用數據集進行試驗測試，分別使用公用的UCI數據集Iris 、Wine和自構造數據集Dataset0。Iris數據集包含3類且每類均有50個數據對象，每個數據包含花瓣長度和寬度、尊片長度和寬度4個屬性。Wine是以葡萄酒的成分分析為數據來源，它包含178個數據，將其劃分為3類，其中每類包含數據數目為59個、71個、48個。自構造數據集Dataset0是以等概率生成的4組2維數據點組成，該數據集包含160個數據點，以高斯分布分配到4個組，每組均包含40個數據對象，并且滿足球形分布，如圖1所示。

　　分別用FCM算法和BFFM算法對UCI數據集中的Iris、Wine和自構造數據集Dataset0進行聚類分析，算法中設定最大誤差ε=10－3，模糊加權指數取2，BFFM算法種群規模為S=50，趨化次數Nc=5，遷徙次數Ns=3，繁殖次數為Nre=2，繁殖比例為0.5，遷移次數Ned=2，遷移概率為0.25，移動最大步長為0.05。兩種算法各自運行30次。用式（8）評判聚類準確率：

　　precision=dD×100%(8)

　　其中，d代表正確地分配到某個類中數據的個數，D表示該類中所包含的總的數據個數。實驗結果如表1~表3所示。 

　　由實驗結果可以看出，BFFM算法相對于傳統的FCM算法來說性能更加優越，提高了聚類的準確度，同時它也增加了算法的收斂速度。當然BFFM算法本身也存在缺陷，該算法所用的時間要比FCM算法稍長些，但整體來說，經過改進后算法的性能更加完善。

5結論

　　本文提出的BFFM算法將細菌覓食算法與FCM算法相結合來改進FCM算法，并以反向學習的思想來生成初始種群，增加種群的多樣性和代表性，從而使BFFM算法不但克服了傳統FCM算法對初始聚類中心的依賴性、易陷入局部極值等缺點，同時也提高了聚類的精準度，使聚類的收斂速度更快，聚類結果更完善。

參考文獻

　　［1］ 雷秀娟.群智能優化算法及其應用［M］.北京:科學出版社,2012.

　?。?］ DUNN J C.A Fuzzy relative of the ISODATA process and its use in detecting compact well separated cluster［J］.J Cybernet,1974(3):3257.

　　［3］ BEZDEK J. Pattern recognition with Fuzzy objective function algorithms［M］.New York: Plenum, 1981.

　?。?］ 丁旭晨,林錦賢.改進的高效模糊C均值聚類算法［J］.微型機與應用,2013,32(23):7476,79.

　?。?］ 周新華,黃道.一種基于蟻群算法的模糊c均值聚類［J］.控制工程,2005,12(2)：132134.

　?。?］ 鄭巖,黃榮懷,戰曉蘇，等.基于遺傳算法的動態模糊聚類［J］.北京郵電大學學報,2005,28(1):7578.

　　［7］ 施美珍.基于粒子群優化算法的模糊聚類分析及其應用［D］.廣州：華南理工大學,2012.

　?。?］ 林睦綱,劉芳菊,童小嬌.一種基于螢火蟲算法的模糊聚類方法［J］.計算機工程與應用,2014,50(21):3538,73.

　?。?］ PASSINO K M. Biomimicry of bacterial foraging for distributed optimization and control［J］.Control System Magazine, 2002, 22(3): 5267.

　?。?0］ 周雅蘭.細菌覓食優化算法的研究與應用［J］.計算機工程與應用,2010, 46 (20):1621.

　　［11］ 王暉.基于一般反向學習的群體隨機搜索算法框架［J］.南昌工程學院學報,2012，31（3）:16.