基于改進(jìn)的細(xì)菌覓食FCM聚類算法

滕建 樂紅兵

摘要

傳統(tǒng)的模糊C均值聚類算法對(duì)初值敏感，容易陷入局部最優(yōu)的問題，本文結(jié)合細(xì)菌覓食算法和粒子群算法的優(yōu)點(diǎn)，將兩種算法結(jié)合，將其應(yīng)用與改進(jìn)傳統(tǒng)的模糊C均值聚類算法的改進(jìn)，該改進(jìn)方式既保留了粒子群算法的全局搜索能力也保留了細(xì)菌覓食算法的局部搜索能力，將細(xì)菌的趨化過程轉(zhuǎn)換為粒子群算法中尋找最優(yōu)解的過程，并保留了細(xì)菌覓食算法中的復(fù)制、遷徒，最后將算法的最后剩余的點(diǎn)作為模糊C均值聚類算法的起始點(diǎn)。在UCI數(shù)據(jù)集的測(cè)試結(jié)果表明，該算法有效解決了初始值的敏感和局部最優(yōu)的問題。

【關(guān)鍵詞】細(xì)菌覓食 FCM粒子群

隨著數(shù)據(jù)挖掘技術(shù)引用的不斷深入，聚類作為數(shù)據(jù)挖掘的重要分支其亦成為研究的重點(diǎn)。1974年Dunn通過把模糊數(shù)學(xué)和傳統(tǒng)的K-means聚類算法相結(jié)合，提出了模糊C均值聚類算法。隨后模糊C均值聚類得到了廣泛的應(yīng)用，但同時(shí)存在多個(gè)問題如聚類數(shù)目不能自動(dòng)確定;對(duì)初始值敏感，容易陷入局部最優(yōu)等問題等。粒子群算法（PSO）是由Kennedy和Eberhart提出，通過模擬鳥群捕食行為來求問題的最優(yōu)解的一種智能優(yōu)化算法。細(xì)菌覓食算法（BFO）由Passino模擬大腸桿菌在人體腸道中的覓食行文提出的一種智能優(yōu)化算法。但兩種算法都有自己的優(yōu)缺點(diǎn)，PSO算法在后期缺乏限制機(jī)制，容易陷入局部最優(yōu);BFO算法在趨化運(yùn)動(dòng)中具有隨機(jī)性，收斂速度比較慢，沒有考慮其他細(xì)菌的信息。本文將兩種算法結(jié)合解決了兩個(gè)智能優(yōu)化算法的缺陷，來改進(jìn)模糊C均值算法的初始點(diǎn)。

1 算法概述

1.1 模糊C均值算法

模糊C均值算法，使用隸屬度來改進(jìn)C均值聚類算法。設(shè)有集合x=（X₁，X₂，X₃，X₄...X_n）分為C={c₁，c₂，c₃，c₄…，c_k）聚類，每個(gè)樣本點(diǎn)以一定的隸屬度屬于某一聚類，隸屬度為uij（i=1，2，…"n;j=1，2，…k）模糊C均值算法通過不斷的迭代，直達(dá)目標(biāo)函數(shù)J（1）到預(yù)定的最小值。

其中m為模糊度，典型取值為2;‖x_i-c_j‖²為樣本到假定聚類中心的距離;隸屬度矩陣U中的數(shù)據(jù)需滿足以下三個(gè)條件：

至少有一個(gè)數(shù)據(jù)屬于一個(gè)聚類，每個(gè)樣本對(duì)聚類的隸屬度之和為1。

公式（1）通過拉格朗日公式，要使J達(dá)到最小值可得以下兩個(gè)解（3）（4）：

2 粒子群優(yōu)化細(xì)菌覓食算法

BFO-PSO算法是在細(xì)菌覓食的基礎(chǔ)上集合粒子群的特點(diǎn)改進(jìn)產(chǎn)生的一種優(yōu)化算法。細(xì)菌覓食算法主要分為三個(gè)過程趨向、復(fù)制、遷徙。

趨向是細(xì)菌覓食算法的核心過程。其更新公式為（5）：

q_n（j+1，k，l）=q_n（j，k，l）+c（n）*f（n）（5）

其中表示細(xì)菌k在經(jīng)過j次趨向，n次復(fù)制，1次遷徙時(shí)的位置。c（n）表示步長(zhǎng)，f（n）表示旋轉(zhuǎn)方向。其趨化分為兩種情況。其一為翻轉(zhuǎn)算子，是指細(xì)菌向隨機(jī)方向前進(jìn)一個(gè)步長(zhǎng)。其二為前進(jìn)算子指細(xì)菌在上一個(gè)方向適應(yīng)度得到改善，沿原方向繼續(xù)前進(jìn)至適應(yīng)度不在改善或達(dá)到最大移動(dòng)步數(shù)。當(dāng)細(xì)菌達(dá)到最大趨化算子數(shù)上限時(shí)，將執(zhí)行繁殖步驟，首先根據(jù)健康度保留前一半而后復(fù)制。為避免陷入局部最小值得情況，當(dāng)完成復(fù)制操作進(jìn)行遷移操作細(xì)菌以一定的概率遷徙到別處。

粒子群優(yōu)化算法模擬自然界中的鳥群和魚群提出的一種群智能算法。理論假設(shè)每個(gè)粒子有兩個(gè)屬性位置和速度。首相隨機(jī)初始化一群粒子作為初始解。其次通過不斷迭代找到最優(yōu)解，在每次迭代中，通過局部最優(yōu)和全局最優(yōu)兩個(gè)值來更新位置和速度。

其中V_i（t）表示第t次迭代時(shí)粒子i的速度，x_i（t）表示t次迭代時(shí)的速度，w為慣性權(quán)值，和全局搜索能力相關(guān)，c₁和c₂為正常數(shù)r₁和r₂為隨機(jī)數(shù)p_i為局部最優(yōu)，p_g為全局最優(yōu)·粒子通過不斷的向全局最優(yōu)和局部最優(yōu)位置加速運(yùn)動(dòng)，最終趨向于全局最優(yōu)解。

細(xì)菌覓食算法有較強(qiáng)的局部搜索能力，但趨向性的隨機(jī)容易使得收斂速度不夠理想，粒子群算法有較強(qiáng)的全局搜索能力。綜上本文通過引入粒子群算法的全局搜索能力來改進(jìn)細(xì)菌覓食算法，可改善收斂速度，改善細(xì)菌覓食算法的全局搜索能力，在趨向操作中引入全局和局部最優(yōu)值。

改進(jìn)的細(xì)菌覓食算法

細(xì)菌覓食算法有較強(qiáng)的局部搜索能力，但趨向性的隨機(jī)容易使得收斂速度不夠理想，粒子群算法有較強(qiáng)的全局搜索能力。綜上借用粒子群算法的全局搜索能力來改進(jìn)細(xì)菌覓食算法，可改善收斂速度。將趨向操作引入粒子群算法的全局和局部最優(yōu)值。改進(jìn)后細(xì)菌的趨向公式為（8）（9）：

基于本算法的具體情況采用聚類算法的距離作為健康值的具體計(jì)算公式：

其中d（x_i-c_j）為每一個(gè)聚類中的點(diǎn)到其聚類中心的距離。

算法步驟：

結(jié)合以上算法新的算法過程如下：

首先初始化參數(shù)S，N_c，N_s，N_re，N_ed，P_ed，C₁，c2，R1，R2其中S為細(xì)菌數(shù)，N_c為趨向步數(shù)，N_s為游動(dòng)的最大的步長(zhǎng)，N_re為復(fù)制操作數(shù)，N_ed為遷徙數(shù)，P_ed為遷徙的概率，C₁和C₂、R₁、R₂為隨機(jī)參數(shù)。

開始循環(huán)：

遷徙的循環(huán)forl=1 to N_ed

復(fù)制的循環(huán)fork=1 to_re

趨向的循環(huán)forj=1 to N_c

遍歷細(xì)菌fori=1 to S

（初次時(shí)初始化每個(gè)每個(gè)細(xì)菌的健康值J_health（i，j，k，l））

更新細(xì)菌的位置直達(dá)新的位置如果健康值大于現(xiàn)在的健康值或者游動(dòng)的到達(dá)步長(zhǎng)設(shè)定數(shù)N}，記錄下最優(yōu)健康值得位置和最優(yōu)健康值。

計(jì)算下一個(gè)細(xì)菌直至遍歷S個(gè)細(xì)菌。

找出每個(gè)細(xì)菌的最優(yōu)健康值的位置和全部細(xì)菌健康值的位置使用公式使用公式（9）和公式（10）進(jìn)行一次趨向操作。

趨向的循環(huán)直至j=N_c。

進(jìn)入復(fù)制循環(huán)，按健康值的大小進(jìn)行排序，健康值低的一半細(xì)菌消除，剩余的一半細(xì)菌進(jìn)行復(fù)制直至k=N_re。

進(jìn)入遷徙的循環(huán)，細(xì)菌以一定的概率P_ed直至1=N_ed。

將細(xì)菌算法的結(jié)果作為FCM算法的初始聚類中心進(jìn)行FCM聚類。

3 實(shí)驗(yàn)和分析

為驗(yàn)證算法的可行性本文使用較廣泛的公用數(shù)據(jù)集UCI數(shù)據(jù)集Iris、Wine。Iris數(shù)據(jù)集包含3個(gè)類其中每個(gè)類中有50個(gè)對(duì)象，每一個(gè)數(shù)據(jù)有包含花的4個(gè)屬性分別為花瓣的長(zhǎng)度、花瓣寬度、花萼的長(zhǎng)度、花萼的寬度。Wine是葡萄酒數(shù)據(jù)，包含178個(gè)數(shù)據(jù)樣本，包括13種葡萄酒的屬性。實(shí)驗(yàn)環(huán)境為windows？平臺(tái)matlab2014硬件環(huán)境為i7-4710內(nèi)存8G。

分別用FCM算法和本文算法對(duì)這兩個(gè)數(shù)據(jù)進(jìn)行聚類計(jì)算結(jié)果如表1所示。

由實(shí)驗(yàn)可以看出，本文算法可以有效改進(jìn)FCM算法對(duì)初始聚類中心選擇對(duì)聚類準(zhǔn)確的的影響能夠提高算法的準(zhǔn)確率，但同時(shí)也增加了算法的復(fù)雜度。

4 結(jié)論

通過引入粒子群算法中全局和局部最優(yōu)變量可以有效改善細(xì)菌覓食算法陷入局部最優(yōu)，并用此改進(jìn)算法所得結(jié)果來改進(jìn)FCM算法初始值的選擇，可以有效的改善聚類的精度，優(yōu)化聚類結(jié)果。

參考文獻(xiàn)

[1]Dunn J C.A Fuzzy Relative ofthe ISODATA Process and ItsUse in Detecting Compact Well-Separated Clusters[J].Journal ofCybernetics，1973，3（03）：32-57.

[2]Eberhart R，Kennedy J.A new optimizerusing particle swarm theory[C].MicroMachine and Human Science，1995.MHS'95.，Proceedings of the SixthInternational Symposium on.IEEE，1995：39-43.

[3]Passino K M.Biomimicry of bacterialforaging for distributed optimizationand control[J].IEEE controlsystems，2002，22（03）：52-67.

[4]黃婉平.自適應(yīng)粒子群優(yōu)化算法及其應(yīng)用研究[D].浙江大學(xué)，2006.

[5]劉小龍.細(xì)菌覓食優(yōu)化算法的改進(jìn)及應(yīng)用[D].華南理工大學(xué)，2011.

[6]周雅蘭.細(xì)菌覓食優(yōu)化算法的研究與應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（20）：16-21.

[7]]李錦，王聯(lián)國(guó).基于細(xì)菌覓食優(yōu)化算法的城市軌道交通調(diào)度優(yōu)化[J].計(jì)算機(jī)工程與科學(xué)，2017，39（03）：586-592.

[8]]孫冠群，張黎鎖.基于細(xì)菌覓食算法的異步電動(dòng)機(jī)現(xiàn)場(chǎng)效率估算[J].計(jì)量學(xué)報(bào)，2017，38（02）：215-219.