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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 禁忌搜索算法

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

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

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

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

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

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

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

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

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

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

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

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

4）t＝t＋1；

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

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

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

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

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

3 實驗性能測試及結(jié)果分析

為了驗證禁忌粒子群優(yōu)化算法提高FCM聚類收斂速度及準確率的有效性，采用VC＋＋編程對UCI數(shù)據(jù)集Iris數(shù)據(jù)集和Wine數(shù)據(jù)集進行仿真實驗，將本文TSPOS＿FCM、文獻［3］的PSO＿FCM 和FCM算法進行比較.Iris數(shù)據(jù)集是由150個4維向量樣本組成，共分為三個種類，每個種類有50個樣本；Wine數(shù)據(jù)集由178個13維向量樣本組成，分為三個種類，各類樣本數(shù)目分別為59、71和48.這兩個數(shù)據(jù)集常用來檢驗聚類算法的性能.設置FCM聚類數(shù)目c＝3，模糊指標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個，禁忌表長為6，記憶長度為100，局部最優(yōu)解長度取4，終止判據(jù)是最大迭代次數(shù)為100或最佳值保留次數(shù)為20.表1為3個算法對2個測試數(shù)據(jù)集的實驗結(jié)果，分別對3種算法做10次實驗，其中FCM算法是取10實驗所得最好的結(jié)果.

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

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

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

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

4 結(jié)束語

綜上所述，F(xiàn)CM算法存在對初始值敏感，易陷入局部極小值的缺陷，結(jié)合PSO算法能有效解決這個問題，考慮到PSO算法有可能出現(xiàn)早熟收斂的情況，本文引入禁忌算法增大PSO算法的搜索范圍，增加粒子的多樣性，同時，通過禁忌表禁忌一些局部最優(yōu)解，防止陷入循環(huán)中，有效地在保證優(yōu)化效果的基礎上縮短了全局最優(yōu)解的時間，提高了整體算法的收斂速度和聚類結(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］ 關 勤，鄧趙紅.改進的FCM算法［J］.計算機工程與應用，2011，47（10）：27－31.

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

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

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

［6］ 江克勤，施培蓓.優(yōu)化初始中心的模糊C均值算法［J］.合肥工業(yè)大學學報（自然科學版），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］.計算機研究與發(fā)展，2009，46（5）：814－822.

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

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

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

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

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