基于禁忌粒子群優化的FCM聚類方法

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

（湖北工業大學電氣與電子工程學院，湖北 武漢430068）

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

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

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

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

其中dik用來表示每類中樣本與該類中心的距離，采用的是歐式距離表達方式.參數m是算法中隸屬度矩陣模糊化指數權重，關于m的最優值的選取仍缺乏相關的理論指導，實驗經驗表明，［1.5，2.5］是參數m可實現FCM模糊聚類的有效區間［8］.根據FCM原理可知其過程是一個按其梯度下降的迭代過程.每次迭代都可以獲得對應的uik和vi.其對應的結果如下：

從FCM工作原理可知，該算法是敏感于初始值的.當初始值選擇在某個目標函數極小點附近時，算法容易陷入該極小點所表現的聚類結果而陷入局部最優.針對該算法敏感于初始值的問題，將一些具有全局尋優能力的群體智能算法與之相結合成為研究的熱點.

2 基于禁忌粒子群優化后的FCM算法

2.1 粒子群優化算法（PSO）

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

關于PSO優化算法應考慮粒子編碼、自適應函數的選擇和粒子更新策略三方面內容.PSO采用的是實數編碼形式，粒子的長度由優化問題決定；適應度函數的選擇一般都是待優化問題的函數表達形式，在解決FCM優化問題上，一般都是將FCM的目標函數作為適應度函數，表達式如下：

標準的粒子更新策略表示如下

其中，參數c1和c2學習因子，r1和r2是在（0，1）區間的隨機數，參數w是慣性權值，其大小決定了算法的全局搜尋能力.不同的參數選擇對應的不同策略，其優化結果不同.

2.2 禁忌搜索算法

禁忌搜索算法（TS）的思想由美國工程院士科羅拉多1986年提出，是一種亞啟發式搜索算法，是對局部領域搜索的擴張.禁忌算法通過引入一個靈活的存儲結構和相對應的禁忌準則來避免循環搜索，同時通過藐視準則來赦免一些被禁忌的優良狀態，以保證多樣化的有效搜索，最終實現全局優化.TS算法在組合優化、機器學習和神經網絡等領域取得很大成功.近年來，TS算法在函數全局優化方面有較多研究.

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

對于禁忌搜索算法的研究，應該把握以下幾個關鍵點：

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

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

3）應該遵循特赦準則.特赦準則對搜索過程中的最佳候選解進行解禁，以保證算法繼續進行，是實現全局優化的關鍵步驟；

4）設置一個合理算法終止準則.

2.3 禁忌粒子群混合優化算法

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

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

2）計算每個粒子的適應度值，即對每個粒子Xi，根據FCM 的目標函數求出f（Ui，Xi），并找出個體極值pBest和全局極值gBest；

3）根據粒子更新策略式（5）和式（6）對每個粒子的速度和位置進行更新.

4）t＝t＋1；

5）迭代過程中若解無改進，則繼續下一步，否則轉為步驟2；

6）根據當前解的鄰域函數產生一定數目的鄰域解，進行搜索，從中選取適應度最高的若干候選解；

7）對每個候選解是否滿足特赦準則進行判斷，如果滿足，則用滿足特赦準則的最佳候選解替代當前解，并用其對應的禁忌對象替代最早進入禁忌表的禁忌對象，同時用該候選解替代TS算法的歷史最優解，轉入步驟6；如果不滿足，則繼續以下步驟；

8）判斷候選解對應各對象的禁忌屬性，選擇候選解集中非禁忌對象對應的最佳狀態替代當前解，用與之對應的禁忌對象替代最早進入禁忌表的禁忌對象元素；

9）判斷是否滿足終止判據條件，若為否，轉為步驟2，若滿足，停止迭代，輸出FCM的最優初始中心.

3 實驗性能測試及結果分析

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

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

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

其中聚類劃分熵Hm（U，C）是一種基于香農信息的聚類有效性函數，其表達式如下：

其值越小表示隸屬度矩陣中元素接近1或0的個數越多，類別間發生混疊現象少，聚類準確率高.

4 結束語

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

［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］ 關 勤，鄧趙紅.改進的FCM算法［J］.計算機工程與應用，2011，47（10）：27－31.

［3］ 陳壽文，李明東.一種混合均值聚類算法的實現［J］.計算機工程與應用，2010，46（18）：132－134.

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

［5］ 趙小強，張守明.基于人工蜂群的模糊聚類算法［J］.蘭州理工大學學報，2010，36（5）：79－83.

［6］ 江克勤，施培蓓.優化初始中心的模糊C均值算法［J］.合肥工業大學學報（自然科學版），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］ 朱 林，王士同，鄧趙紅.改進模糊劃分的FCM聚類算法的一般化研究［J］.計算機研究與發展，2009，46（5）：814－822.

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

［10］朱文婕，吳 楠.一個改進的模糊聚類有效性指標［J］.計算機工程與應用，2011，47（5）：206－209.

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

［12］唐 俊.PSO算法原理及應用［J］.計算機技術和發展.2010，2（20）：213－216.

［13］張玉芳，薛青松，熊忠陽.基于禁忌搜索的動態粒子群算法［J］.計算機工程與應用.2008，44（24）：56－58.