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

胡紹方，周　鳳

(貴州大學 計算機科學與技術(shù)學院，貴州 貴陽 550025)

?

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

胡紹方，周鳳

(貴州大學 計算機科學與技術(shù)學院，貴州 貴陽 550025)

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

細菌覓食優(yōu)化算法；聚類；FCM

引用格式：胡紹方，周鳳. 基于細菌覓食的FCM聚類算法[J].微型機與應(yīng)用，2016,35(11)：8-10，13.

0　引言

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

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

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

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

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

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

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

1　FCM算法

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

(1)

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

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

(2)

(3)

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

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

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

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

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

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

2　細菌覓食算法

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

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

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

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

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

(4)

(5)

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

(6)

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

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

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

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

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

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

(1)初始化種群，按照種群規(guī)模數(shù)目N初始化，并指定聚類數(shù)目c，然后再將每個細菌隨機地指派為某一類，把其最初的聚類劃分，作為細菌i的位置編碼，同時計算各類的聚類中心，隨機生成的初始解每一維分量都滿足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、細菌規(guī)模數(shù)S和游動次數(shù)Ns的初始值。

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

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

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

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

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

4　實驗及結(jié)果

為了驗證BFFM算法的可行性和有效性，使用數(shù)據(jù)集進行試驗測試，分別使用公用的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所示。

圖1　自構(gòu)造數(shù)據(jù)集DataSet0

分別用FCM算法和BFFM算法對UCI數(shù)據(jù)集中的Iris、Wine和自構(gòu)造數(shù)據(jù)集Dataset0進行聚類分析，算法中設(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)評判聚類準確率：

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

表2　Wine數(shù)據(jù)集聚類結(jié)果

表3　自構(gòu)造數(shù)據(jù)集Dataset0聚類結(jié)果

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

5　結(jié)論

本文提出的BFFM算法將細菌覓食算法與FCM算法相結(jié)合來改進FCM算法，并以反向?qū)W習的思想來生成初始種群，增加種群的多樣性和代表性，從而使BFFM算法

不但克服了傳統(tǒng)FCM算法對初始聚類中心的依賴性、易陷入局部極值等缺點，同時也提高了聚類的精準度，使聚類的收斂速度更快，聚類結(jié)果更完善。

[1] 雷秀娟.群智能優(yōu)化算法及其應(yīng)用[M].北京:科學出版社,2012.

[2] 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.

[4] 丁旭晨,林錦賢.改進的高效模糊C均值聚類算法[J].微型機與應(yīng)用,2013,32(23):74-76,79.

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

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

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

[8] 林睦綱,劉芳菊,童小嬌.一種基于螢火蟲算法的模糊聚類方法[J].計算機工程與應(yīng)用,2014,50(21):35-38,73.

[9] PASSINO K M. Biomimicry of bacterial foraging for distributed optimization and control[J].Control System Magazine, 2002, 22(3): 52-67.

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

[11] 王暉.基于一般反向?qū)W習的群體隨機搜索算法框架[J].南昌工程學院學報,2012，31(3):1-6.

FCM clustering algorithm based on bacterial foraging optimization

Hu Shaofang，Zhou Feng

(School of Computer Science and Technology, Guizhou University,Guiyang 550025,China)

FCM clustering algorithm is sensitive to initial clustering center and is easy to fall into local optimal solution. A bacterial foraging optimization clustering algorithm based on bacterial foraging was proposed. The bacterial foraging algorithm and FCM algorithm are combined, and using reverse learning to initialize the population, to increase the diversity and representation of the population, the optimal solution is obtained as the initial clustering center of FCM algorithm. It not only reduces the dependence of the initial cluster centers of FCM algorithm, but also reduces the possibility of falling into the local optimal solution, and improves the stability of the algorithm. Experimental results show that this algorithm overcomes the shortcomings of poor stability of FCM algorithm, convergence rate is faster, and has good performance and clustering results.

bacterial foraging optimization; cluster; FCM

TP391

A

10.19358/j.issn.1674- 7720.2016.11.003

2016-04-05)

胡紹方(1984-)，男，碩士，主要研究方向：網(wǎng)絡(luò)技術(shù)。

周鳳(1976-)，女，碩士，副教授，主要研究方向：網(wǎng)絡(luò)技術(shù)。