滕建 樂紅兵

摘要

傳統(tǒng)的模糊C均值聚類算法對初值敏感，容易陷入局部最優(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ù)集的測試結(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ù)目不能自動確定;對初始值敏感，容易陷入局部最優(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)動中具有隨機(jī)性，收斂速度比較慢，沒有考慮其他細(xì)菌的信息。本文將兩種算法結(jié)合解決了兩個智能優(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）聚類，每個樣本點(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ù)需滿足以下三個條件：

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

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

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

BFO-PSO算法是在細(xì)菌覓食的基礎(chǔ)上集合粒子群的特點(diǎn)改進(jìn)產(chǎn)生的一種優(yōu)化算法。細(xì)菌覓食算法主要分為三個過程趨向、復(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次遷徙時的位置。c（n）表示步長，f（n）表示旋轉(zhuǎn)方向。其趨化分為兩種情況。其一為翻轉(zhuǎn)算子，是指細(xì)菌向隨機(jī)方向前進(jìn)一個步長。其二為前進(jìn)算子指細(xì)菌在上一個方向適應(yīng)度得到改善，沿原方向繼續(xù)前進(jìn)至適應(yīng)度不在改善或達(dá)到最大移動步數(shù)。當(dāng)細(xì)菌達(dá)到最大趨化算子數(shù)上限時，將執(zhí)行繁殖步驟，首先根據(jù)健康度保留前一半而后復(fù)制。為避免陷入局部最小值得情況，當(dāng)完成復(fù)制操作進(jìn)行遷移操作細(xì)菌以一定的概率遷徙到別處。

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

其中V_i（t）表示第t次迭代時粒子i的速度，x_i（t）表示t次迭代時的速度，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)動，最終趨向于全局最優(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）：

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

其中d（x_i-c_j）為每一個聚類中的點(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為游動的最大的步長，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

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

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

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

找出每個細(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ù)據(jù)集UCI數(shù)據(jù)集Iris、Wine。Iris數(shù)據(jù)集包含3個類其中每個類中有50個對象，每一個數(shù)據(jù)有包含花的4個屬性分別為花瓣的長度、花瓣寬度、花萼的長度、花萼的寬度。Wine是葡萄酒數(shù)據(jù)，包含178個數(shù)據(jù)樣本，包括13種葡萄酒的屬性。實驗環(huán)境為windows？平臺matlab2014硬件環(huán)境為i7-4710內(nèi)存8G。

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

由實驗可以看出，本文算法可以有效改進(jìn)FCM算法對初始聚類中心選擇對聚類準(zhǔn)確的的影響能夠提高算法的準(zhǔn)確率，但同時也增加了算法的復(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ī)工程與應(yīng)用，2010，46（20）：16-21.

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

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