胡紹方，周鳳

　?。ㄙF州大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽 550025）

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

　　關(guān)鍵詞：細(xì)菌覓食優(yōu)化算法；聚類；FCM

0引言

　　隨著計算機(jī)技術(shù)的發(fā)展，信息量的倍增，數(shù)據(jù)挖掘技術(shù)是當(dāng)前技術(shù)研究的重點，而聚類是數(shù)據(jù)挖掘技術(shù)中的一個重要分支，它是一種以相似性為基礎(chǔ)的無監(jiān)督的機(jī)器學(xué)習(xí)技術(shù)，其目的是將目標(biāo)數(shù)據(jù)集分成若干個簇，使得同簇內(nèi)的數(shù)據(jù)相似度盡可能高，不同簇的數(shù)據(jù)相似度盡可能低。聚類技術(shù)目前應(yīng)用非常廣泛，在機(jī)器學(xué)習(xí)、模式識別、Web挖掘［1］領(lǐng)域等都有很好的應(yīng)用前景。

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

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

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

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

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

　　針對FCM算法的這些缺點，本文把并行搜索能力強(qiáng)、易于跳出局部極值的細(xì)菌覓食算法引進(jìn)到FCM算法，來改善傳統(tǒng)FCM算法的弊端。最后，運用經(jīng)典的UCI數(shù)據(jù)集和自構(gòu)造數(shù)據(jù)集進(jìn)行測試實驗，結(jié)果表明這種改進(jìn)算法是可行的并且提高了聚類的準(zhǔn)確率。

1FCM算法　

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

　　FCM算法的目標(biāo)函數(shù)：

　　其中，m是一個加權(quán)指數(shù)，一般是大于1的數(shù)。

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

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

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

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

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

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

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

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

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

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

2細(xì)菌覓食算法

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

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

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

　　細(xì)菌的位置按照下式進(jìn)行調(diào)整更新：

　　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是每一步前進(jìn)的步長，φ(i)表示細(xì)菌隨機(jī)翻滾的方向，Xrand(j,k,l)表示當(dāng)前個體Xi(j,k,l)鄰域內(nèi)的一個隨機(jī)位置。如果翻轉(zhuǎn)后適應(yīng)度值得到改善，則繼續(xù)沿著翻轉(zhuǎn)的方向前進(jìn)，細(xì)菌個體i的適應(yīng)度值用fiti來表示：

　　其中Jc為總的類內(nèi)離散度。

3基于細(xì)菌覓食的FCM聚類算法

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

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

　　3.1基于反方向?qū)W習(xí)的初始化

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

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

　　（2)為每一個上一步產(chǎn)生的初始解生成其相應(yīng)的反向解，它在每個維度的分量按下式計算：

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

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

　　3.2算法的實現(xiàn)步驟

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

　　(2)種群初始化。本文采用基于反向?qū)W習(xí)的方法產(chǎn)生初始種群，并隨機(jī)選取c個細(xì)菌作為初始聚類中心。

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

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

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

　　（6）執(zhí)行FCM聚類過程。將細(xì)菌尋優(yōu)結(jié)束時最終的位置作為FCM算法的初始聚類中心，開始執(zhí)行FCM算法聚類過程進(jìn)行聚類。

4實驗及結(jié)果

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

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

　　precision=dD×100%(8)

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

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

5結(jié)論

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

參考文獻(xiàn)

　　［1］ 雷秀娟.群智能優(yōu)化算法及其應(yīng)用［M］.北京:科學(xué)出版社,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.

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

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

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

　?。?］ 施美珍.基于粒子群優(yōu)化算法的模糊聚類分析及其應(yīng)用［D］.廣州：華南理工大學(xué),2012.

　　［8］ 林睦綱,劉芳菊,童小嬌.一種基于螢火蟲算法的模糊聚類方法［J］.計算機(jī)工程與應(yīng)用,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.

　　［10］ 周雅蘭.細(xì)菌覓食優(yōu)化算法的研究與應(yīng)用［J］.計算機(jī)工程與應(yīng)用,2010, 46 (20):1621.

　?。?1］ 王暉.基于一般反向?qū)W習(xí)的群體隨機(jī)搜索算法框架［J］.南昌工程學(xué)院學(xué)報,2012，31（3）:16.