基于禁忌粒子群優(yōu)化的FCM聚類方法

陳曉霞，廖家平，趙熙臨，諶金豆

（湖北工業(yè)大學(xué)電氣與電子工程學(xué)院，湖北 武漢430068）

模糊C－均值是基于目標(biāo)函數(shù)的無監(jiān)督動(dòng)態(tài)聚類方法，通過模糊理論對重要數(shù)據(jù)分析和建模，建立了樣本屬性的不確定性描述，比較客觀地反映現(xiàn)實(shí)世界.該算法計(jì)算簡單，具有比較直觀的幾何意義，成功地應(yīng)用于模式識(shí)別、數(shù)據(jù)分析等領(lǐng)域.然而基于傳統(tǒng)目標(biāo)函數(shù)的FCM，采用迭代的爬山技術(shù)尋找最優(yōu)解，本質(zhì)上是一種局部搜索算法，存在一個(gè)致命問題：對初始值敏感，容易陷入局部極小值.隨著群體智能方法的發(fā)展，將具有全局搜索能力的群智能算法和具有局部搜索能力的FCM相結(jié)合成為研究熱點(diǎn).文獻(xiàn)［1］利用遺傳算法對初始聚類中心進(jìn)行優(yōu)化并執(zhí)行FCM算法，提高了收斂速度并改善了分類效果，增強(qiáng)了算法的魯棒性；文獻(xiàn)［2］提出了蟻群算法確定FCM模型初始聚類中心的方法，優(yōu)化聚類效果；文獻(xiàn)［3］提出了利用粒子群算法（PSO）全局尋優(yōu)FCM最優(yōu)初始聚類中心.這些方法能有效克服FCM算法固有的缺陷，但同時(shí)也帶來新的問題.遺傳算法和蟻群算法本身存在大量參數(shù)和復(fù)雜的操作，計(jì)算開銷較大，對算法收斂速度有極大影響，特別是對大樣本數(shù)據(jù)聚類時(shí)，聚類效果的改進(jìn)不及收斂速度影響大，對整體算法沒有很大優(yōu)勢.PSO算法簡單，參數(shù)少，計(jì)算方便，求解快，但有容易早熟導(dǎo)致陷入局部最優(yōu)解的問題.粒子群規(guī)模的選擇和初始粒子的隨機(jī)性也會(huì)影響其優(yōu)化結(jié)果，因此保持粒子的多樣性是必要的.將禁忌搜索引進(jìn)粒子群算法，通過對粒子群算法的輸出進(jìn)行局部及鄰域搜索，可以實(shí)現(xiàn)真正意義上的全局尋優(yōu).該混合優(yōu)化算法既保留了PSO算法的并行處理能力，同時(shí)也充分利用了禁忌搜索算法的局部搜索能力，針對FCM模型全局最優(yōu)初始聚類中心的確定及對FCM聚類準(zhǔn)確性有極好的效果.

1 模糊C－均值算法（FCM）

模糊C均值算法是聚類分析中的一種基本劃分方法，常采用誤差平方和準(zhǔn)則函數(shù)作為聚類準(zhǔn)則，它通過優(yōu)化目標(biāo)函數(shù)得到每個(gè)樣本點(diǎn)對所有類中心的隸屬度，從而決定樣本點(diǎn)的類屬以達(dá)到自動(dòng)對數(shù)據(jù)樣本進(jìn)行分類的目的.考慮一有限數(shù)據(jù)集X＝｛x1，x2，…，xn｝，是一組有n個(gè)m 維向量組成的樣本集合.利用FCM聚類算法將它們分為C個(gè)子集，每個(gè)子集又可稱為類，C為2到n之間的整數(shù).對于每類，可用兩個(gè)參數(shù)來描述它：一個(gè)是用于表示每個(gè)樣本隸屬于該類的概率uik，另一個(gè)是該類的中心點(diǎn)

對于FCM算法的整體過程，可用隸屬度矩陣U＝ ｛uik，1≤i≤C，1≤k≤n｝來表示每一樣本對各類的隸屬程度；V ＝ ｛v1，v2，…，vc｝為所有類聚類中心集合.其目標(biāo)函數(shù)采用的是類內(nèi)加權(quán)平方和的極小值，可以表示為：

其中dik用來表示每類中樣本與該類中心的距離，采用的是歐式距離表達(dá)方式.參數(shù)m是算法中隸屬度矩陣模糊化指數(shù)權(quán)重，關(guān)于m的最優(yōu)值的選取仍缺乏相關(guān)的理論指導(dǎo)，實(shí)驗(yàn)經(jīng)驗(yàn)表明，［1.5，2.5］是參數(shù)m可實(shí)現(xiàn)FCM模糊聚類的有效區(qū)間［8］.根據(jù)FCM原理可知其過程是一個(gè)按其梯度下降的迭代過程.每次迭代都可以獲得對應(yīng)的uik和vi.其對應(yīng)的結(jié)果如下：

從FCM工作原理可知，該算法是敏感于初始值的.當(dāng)初始值選擇在某個(gè)目標(biāo)函數(shù)極小點(diǎn)附近時(shí)，算法容易陷入該極小點(diǎn)所表現(xiàn)的聚類結(jié)果而陷入局部最優(yōu).針對該算法敏感于初始值的問題，將一些具有全局尋優(yōu)能力的群體智能算法與之相結(jié)合成為研究的熱點(diǎn).

2 基于禁忌粒子群優(yōu)化后的FCM算法

2.1 粒子群優(yōu)化算法（PSO）

PSO算法是一種進(jìn)化計(jì)算技術(shù)，由Eberhart博士和Kennedy博士于1995年提出.該算法是受到飛鳥集活動(dòng)規(guī)律的啟發(fā)，利用群體智能建立的一個(gè)簡化模型.在該模型中，每個(gè)優(yōu)化問題的可行解都是一個(gè)粒子Si，所有的粒子都有被優(yōu)化的函數(shù)決定的適應(yīng)值f（Si），每個(gè)粒子還有一個(gè)速度Vi決定他們的方向和距離，粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間進(jìn)行搜索.粒子群算法具有記憶功能，只有全局最優(yōu)解或局部最優(yōu)解向其他粒子傳遞信息是個(gè)單向的信息流動(dòng)，整個(gè)搜索更新過程是跟隨當(dāng)前最優(yōu)解的過程，因此該算法較其他智能算法更快收斂最優(yōu)解.它具有簡單、容易實(shí)現(xiàn)、無須多參數(shù)調(diào)整等優(yōu)點(diǎn).目前廣泛應(yīng)用于函數(shù)優(yōu)化、模糊系統(tǒng)控制以及其他遺傳算法應(yīng)用領(lǐng)域.該算法基本思路是：初始化一群隨機(jī)解，也即是粒子.然后通過迭代找到最優(yōu)解.在每次迭代過程中，粒子通過跟蹤兩個(gè)“極值”來更新自己，第一個(gè)是粒子本身所找到的最優(yōu)解，這個(gè)解叫個(gè)體極值pBest，另一個(gè)是整個(gè)種群中找到的最優(yōu)解，這個(gè)極值是全局極值gBest.經(jīng)過數(shù)次迭代，直至滿足停止迭代條件為止，最終得到的gBest就是要找的解.

關(guān)于PSO優(yōu)化算法應(yīng)考慮粒子編碼、自適應(yīng)函數(shù)的選擇和粒子更新策略三方面內(nèi)容.PSO采用的是實(shí)數(shù)編碼形式，粒子的長度由優(yōu)化問題決定；適應(yīng)度函數(shù)的選擇一般都是待優(yōu)化問題的函數(shù)表達(dá)形式，在解決FCM優(yōu)化問題上，一般都是將FCM的目標(biāo)函數(shù)作為適應(yīng)度函數(shù)，表達(dá)式如下：

標(biāo)準(zhǔn)的粒子更新策略表示如下

其中，參數(shù)c1和c2學(xué)習(xí)因子，r1和r2是在（0，1）區(qū)間的隨機(jī)數(shù)，參數(shù)w是慣性權(quán)值，其大小決定了算法的全局搜尋能力.不同的參數(shù)選擇對應(yīng)的不同策略，其優(yōu)化結(jié)果不同.

2.2 禁忌搜索算法

禁忌搜索算法（TS）的思想由美國工程院士科羅拉多1986年提出，是一種亞啟發(fā)式搜索算法，是對局部領(lǐng)域搜索的擴(kuò)張.禁忌算法通過引入一個(gè)靈活的存儲(chǔ)結(jié)構(gòu)和相對應(yīng)的禁忌準(zhǔn)則來避免循環(huán)搜索，同時(shí)通過藐視準(zhǔn)則來赦免一些被禁忌的優(yōu)良狀態(tài)，以保證多樣化的有效搜索，最終實(shí)現(xiàn)全局優(yōu)化.TS算法在組合優(yōu)化、機(jī)器學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)等領(lǐng)域取得很大成功.近年來，TS算法在函數(shù)全局優(yōu)化方面有較多研究.

禁忌搜索算法的基本思路：TS算法從一個(gè)初始解X出發(fā)，這個(gè)初始解可以從其他啟發(fā)式算法獲得，也可以在可行解集合中任選.確定完初始解后，定義其對應(yīng)的鄰域S（x），在鄰域中移動(dòng)已改進(jìn)當(dāng)前解，從而獲得新的解X′，然后從X′開始，重復(fù)搜索.在搜索過程中，要構(gòu)建一定禁忌長度T的循環(huán)記憶表禁忌表，以保證算法避免循環(huán)和局部最優(yōu).同時(shí)也要遵循相應(yīng)的“特赦準(zhǔn)則”對搜索過程中最優(yōu)候選解進(jìn)行解禁，保證算法的順利進(jìn)行.禁忌表是個(gè)循環(huán)表，在搜索過程中仍然有可能陷入循環(huán)，因此必須給定算法停止準(zhǔn)則以結(jié)束算法.

對于禁忌搜索算法的研究，應(yīng)該把握以下幾個(gè)關(guān)鍵點(diǎn)：

1）初始解的選擇.TS算法必須有一個(gè)初始解，這個(gè)初始解對算法本身性能有影響.從可行解中獲得初始解有一定隨機(jī)性，當(dāng)前更多的是將另一種啟發(fā)式算法的輸出作為初始解以優(yōu)化算法性能；

2）禁忌長度T的選擇.禁忌表長度T在很大程度上影響著搜素速度和解的質(zhì)量.過大會(huì)增加計(jì)算量且易陷入局部最優(yōu)；過小容易陷入循環(huán)搜索，整個(gè)搜索將圍繞著相同的幾個(gè)解徘徊；

3）應(yīng)該遵循特赦準(zhǔn)則.特赦準(zhǔn)則對搜索過程中的最佳候選解進(jìn)行解禁，以保證算法繼續(xù)進(jìn)行，是實(shí)現(xiàn)全局優(yōu)化的關(guān)鍵步驟；

4）設(shè)置一個(gè)合理算法終止準(zhǔn)則.

2.3 禁忌粒子群混合優(yōu)化算法

禁忌粒子群優(yōu)化算法是以粒子群算法為主體，以禁忌算法為個(gè)體在鄰域中移動(dòng)尋優(yōu).PSO算法輸出解作為TS算法的初始解，利用TS算法在解空間搜索到更好的解，其結(jié)果相當(dāng)于對粒子群的輸出做更新.該混合算法既克服了PSO算法局部搜索能力較弱和存在早熟收斂的問題，又利用了禁忌搜索較強(qiáng)的“爬山”能力，加快了混合算法的收斂速度，提高了收斂解的有效性，實(shí)現(xiàn)兩者優(yōu)勢互補(bǔ).該混合算法在求解FCM最優(yōu)初始中心步驟如下：

1）輸入待聚類的樣本數(shù)據(jù)，并設(shè)置PSO算法和TS算法中所需設(shè)置的參數(shù)，初始化粒子，t＝0；

2）計(jì)算每個(gè)粒子的適應(yīng)度值，即對每個(gè)粒子Xi，根據(jù)FCM 的目標(biāo)函數(shù)求出f（Ui，Xi），并找出個(gè)體極值pBest和全局極值gBest；

3）根據(jù)粒子更新策略式（5）和式（6）對每個(gè)粒子的速度和位置進(jìn)行更新.

4）t＝t＋1；

5）迭代過程中若解無改進(jìn)，則繼續(xù)下一步，否則轉(zhuǎn)為步驟2；

6）根據(jù)當(dāng)前解的鄰域函數(shù)產(chǎn)生一定數(shù)目的鄰域解，進(jìn)行搜索，從中選取適應(yīng)度最高的若干候選解；

7）對每個(gè)候選解是否滿足特赦準(zhǔn)則進(jìn)行判斷，如果滿足，則用滿足特赦準(zhǔn)則的最佳候選解替代當(dāng)前解，并用其對應(yīng)的禁忌對象替代最早進(jìn)入禁忌表的禁忌對象，同時(shí)用該候選解替代TS算法的歷史最優(yōu)解，轉(zhuǎn)入步驟6；如果不滿足，則繼續(xù)以下步驟；

8）判斷候選解對應(yīng)各對象的禁忌屬性，選擇候選解集中非禁忌對象對應(yīng)的最佳狀態(tài)替代當(dāng)前解，用與之對應(yīng)的禁忌對象替代最早進(jìn)入禁忌表的禁忌對象元素；

9）判斷是否滿足終止判據(jù)條件，若為否，轉(zhuǎn)為步驟2，若滿足，停止迭代，輸出FCM的最優(yōu)初始中心.

3 實(shí)驗(yàn)性能測試及結(jié)果分析

為了驗(yàn)證禁忌粒子群優(yōu)化算法提高FCM聚類收斂速度及準(zhǔn)確率的有效性，采用VC＋＋編程對UCI數(shù)據(jù)集Iris數(shù)據(jù)集和Wine數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)，將本文TSPOS＿FCM、文獻(xiàn)［3］的PSO＿FCM 和FCM算法進(jìn)行比較.Iris數(shù)據(jù)集是由150個(gè)4維向量樣本組成，共分為三個(gè)種類，每個(gè)種類有50個(gè)樣本；Wine數(shù)據(jù)集由178個(gè)13維向量樣本組成，分為三個(gè)種類，各類樣本數(shù)目分別為59、71和48.這兩個(gè)數(shù)據(jù)集常用來檢驗(yàn)聚類算法的性能.設(shè)置FCM聚類數(shù)目c＝3，模糊指標(biāo)m＝2，粒子群規(guī)模N＝50，c1＝2，c2＝2，vmax＝2，vmin＝－2，最大迭代次數(shù)tmax＝100，慣性權(quán)重w＝0.729 8，最優(yōu)解改變量閾值e＝1e－4，TS局部搜索半徑SR＝0.3，鄰域解和候選解均取8個(gè)，禁忌表長為6，記憶長度為100，局部最優(yōu)解長度取4，終止判據(jù)是最大迭代次數(shù)為100或最佳值保留次數(shù)為20.表1為3個(gè)算法對2個(gè)測試數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果，分別對3種算法做10次實(shí)驗(yàn)，其中FCM算法是取10實(shí)驗(yàn)所得最好的結(jié)果.

表1 各種FCM聚類算法性能比較

從表1中可以看出，TSPOS＿FCM在所有的指標(biāo)上優(yōu)于其他算法，其中傳統(tǒng)的FCM算法由于采用了梯度算子，函數(shù)值下降非常迅速，容易陷入局部最小值，這是使用梯度算子很難避免的結(jié)果.而目標(biāo)函數(shù)的方差較大，說明FCM的輸出解不穩(wěn)定，對初始聚類中心敏感.而PSO＿FCM算法中聚類正確率較高，最優(yōu)解對應(yīng)目標(biāo)函數(shù)的方差較小，說明算法的全局搜索能力較好，算法輸出最優(yōu)解較為穩(wěn)定.TSPSO＿FCM將禁忌算法和粒子群算法結(jié)合起來，克服了PSO后期易陷入局部最優(yōu)和過于早熟問題，通過禁忌算法增加力粒子搜索空間，增加了粒子的多樣性，有助于全局最優(yōu)解的搜索，從評價(jià)指標(biāo)上可以看出其聚類準(zhǔn)確率是最高的，同時(shí)最優(yōu)解對應(yīng)方差最小，說明其最優(yōu)解是最穩(wěn)定的.

其中聚類劃分熵Hm（U，C）是一種基于香農(nóng)信息的聚類有效性函數(shù)，其表達(dá)式如下：

其值越小表示隸屬度矩陣中元素接近1或0的個(gè)數(shù)越多，類別間發(fā)生混疊現(xiàn)象少，聚類準(zhǔn)確率高.

4 結(jié)束語

綜上所述，F(xiàn)CM算法存在對初始值敏感，易陷入局部極小值的缺陷，結(jié)合PSO算法能有效解決這個(gè)問題，考慮到PSO算法有可能出現(xiàn)早熟收斂的情況，本文引入禁忌算法增大PSO算法的搜索范圍，增加粒子的多樣性，同時(shí)，通過禁忌表禁忌一些局部最優(yōu)解，防止陷入循環(huán)中，有效地在保證優(yōu)化效果的基礎(chǔ)上縮短了全局最優(yōu)解的時(shí)間，提高了整體算法的收斂速度和聚類結(jié)果的正確率.

［1］ Chen W，Lu T.J.An improved genetic FCM clustering algorithm［C］／／2010 2ndInternational Conference on Future Computer and Communication.China，2010（1）：45－47.

［2］ 關(guān) 勤，鄧趙紅.改進(jìn)的FCM算法［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（10）：27－31.

［3］ 陳壽文，李明東.一種混合均值聚類算法的實(shí)現(xiàn)［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46（18）：132－134.

［4］ 況 夯，羅 軍.基于遺傳FCM算法的文本聚類［J］.計(jì)算機(jī)應(yīng)用，2009，29（2）：558－561.

［5］ 趙小強(qiáng)，張守明.基于人工蜂群的模糊聚類算法［J］.蘭州理工大學(xué)學(xué)報(bào)，2010，36（5）：79－83.

［6］ 江克勤，施培蓓.優(yōu)化初始中心的模糊C均值算法［J］.合肥工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），2009，32（5）：762－765.

［7］ Wang Z.B.The study of an improved FCM clustering algorithm ［C］／／2010 2ndInternational Conference on Signal Processing Systems.China，2010，（2）：95－100.

［8］ 朱 林，王士同，鄧趙紅.改進(jìn)模糊劃分的FCM聚類算法的一般化研究［J］.計(jì)算機(jī)研究與發(fā)展，2009，46（5）：814－822.

［9］ 溫重偉，李榮鈞.改進(jìn)的粒子群優(yōu)化模糊C均值聚類算法［J］.計(jì)算機(jī)應(yīng)用研究，2010，27（7）：2 520－2 522.

［10］朱文婕，吳 楠.一個(gè)改進(jìn)的模糊聚類有效性指標(biāo)［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（5）：206－209.

［11］韓 琳，賀興時(shí).基于免疫粒子群優(yōu)化的模糊C均值聚類算法［J］.西安工程科技學(xué)院學(xué)報(bào)，2007，3（21）：355－361.

［12］唐 俊.PSO算法原理及應(yīng)用［J］.計(jì)算機(jī)技術(shù)和發(fā)展.2010，2（20）：213－216.

［13］張玉芳，薛青松，熊忠陽.基于禁忌搜索的動(dòng)態(tài)粒子群算法［J］.計(jì)算機(jī)工程與應(yīng)用.2008，44（24）：56－58.