抑制式模糊C－均值聚類研究綜述

范九倫

（西安郵電大學(xué) 通信與信息工程學(xué)院，陜西 西安710121）

計(jì)算機(jī)技術(shù)和網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，使得人們面對(duì)的數(shù)據(jù)類型越來越多，數(shù)據(jù)維數(shù)越來越高，數(shù)據(jù)量越來越大，目前世界已進(jìn)入大數(shù)據(jù)時(shí)代。大數(shù)據(jù)時(shí)代對(duì)人類的數(shù)據(jù)駕馭能力提出了新的挑戰(zhàn)，也為人們獲得更為深刻、全面的洞察能力提供了前所未有的空間與潛力。作為數(shù)據(jù)分析的基本工具，模式識(shí)別的內(nèi)涵在不斷的擴(kuò)大，模式識(shí)別的方法在不斷的推新。鑒于現(xiàn)實(shí)的數(shù)據(jù)很多是沒辦法事先進(jìn)行分類的，因此無監(jiān)督模式識(shí)別方法越來越受到重視，而聚類分析是無監(jiān)督模式識(shí)別的主要方式，因此國際上對(duì)聚類分析的理論、方法、算法的研究一直沒有間斷，這些年大有上漲趨勢，各種有關(guān)聚類分析及應(yīng)用的文章和著作層出不窮。

在眾多的聚類算法中，經(jīng)典的硬C－均值（HCM）聚類算法是一個(gè)被人們經(jīng)常使用的著名算法，其顯著優(yōu)點(diǎn)是原理簡單直觀、運(yùn)行速度快，其明顯缺點(diǎn)是數(shù)據(jù)的“硬劃分”導(dǎo)致數(shù)據(jù)的分類不夠理想。鑒于此，早在上世紀(jì)七八十年代，人們就開始考慮將數(shù)據(jù)的“硬劃分”改為“軟劃分”（即：模糊劃分），從而提出了著名的并被經(jīng)常使用的模糊C－均值（FCM）聚類算法［1－3］。由于隸屬函數(shù)的引入，使得目標(biāo)函數(shù)可表示的內(nèi)容更為寬泛，這使得模糊聚類不僅能夠處理團(tuán)狀數(shù)據(jù)，也能夠處理線狀數(shù)據(jù)、面狀數(shù)據(jù)、殼狀數(shù)據(jù)等眾多的數(shù)據(jù)類型。此外，人們也對(duì)模糊聚類的各種拓展進(jìn)行了研究，如可能性聚類、可能性－模糊混合聚類、模糊C－均值聚類的各種廣義表達(dá)形式［4－9］。

FCM聚類相比HCM聚類的視野更為寬泛、內(nèi)容更為豐富，但FCM聚類的一個(gè)不容忽視的缺點(diǎn)是運(yùn)行速度遠(yuǎn)比HCM聚類慢得多，使其應(yīng)用于大數(shù)據(jù)分析面臨諸多困難。為了提高FCM聚類的運(yùn)行速度，研究者們也做了各種各樣的努力，但均沒有明顯的受益。鑒于一個(gè)好的聚類算法應(yīng)該對(duì)現(xiàn)實(shí)應(yīng)用系統(tǒng)中經(jīng)常出現(xiàn)的大數(shù)據(jù)有好的分類性能，為了給出一種能體現(xiàn)HCM聚類和FCM聚類各自優(yōu)點(diǎn)且分類性能良好的算法，我們提出了抑制式模糊C－均值（S－FCM）聚類算法［10］，該算法在數(shù)據(jù)分類時(shí)引入“抑制式競爭學(xué)習(xí)”機(jī)制，通過對(duì)每個(gè)樣本的最大隸屬度進(jìn)行獎(jiǎng)勵(lì)的同時(shí)抑制其它隸屬度的方式，在運(yùn)行速度和分類性能兩個(gè)方面均比FCM聚類算法有顯著提高。該算法的另一個(gè)優(yōu)點(diǎn)是將HCM聚類和FCM聚類融為一體，通過抑制率α（0≤α≤1）的不同取值可分別得到 HCM 聚類和FCM聚類，即α＝0時(shí)為 HCM 聚類；α＝1時(shí)為FCM 聚類，0＜α＜1為S－FCM聚類。

1 S－FCM聚類算法

對(duì)于?q空間上的數(shù)據(jù)集X＝｛x1，x2，…，xn｝，通過聚類將數(shù)據(jù)劃分成c個(gè)類，每類的樣本中心記為vi（i＝1，2，…，c），uij表示樣本xj到第i個(gè)類vi的隸屬度，d2ij＝‖xj－vi‖2表示樣本xj到第i個(gè)類vi的距離，m表示模糊C－均值聚類算法中的模糊因子，通常取為2。

模糊聚類問題可表述為數(shù)學(xué)規(guī)劃

使得

這里U＝｛uij｝是一個(gè)c×n矩陣，V＝［v1，v2，…，vc］是一個(gè)q×c矩陣。該數(shù)學(xué)規(guī)劃問題可如下求解［1］。

初始化 初始中心V（0），令k＝0，選擇ε＞0。

步驟1 用（2a）和（2b）計(jì)算U（k）。

如果 ?j，r，dij（k）＞0，那么

如果存在j，r使得dij（k）＝0，那么令

步驟2 用（2c）計(jì)算V（k＋1）。

步驟3 如果 ‖V（k）－V（k＋1）‖ ＜ε，停止；否則令k＝k＋1回到步驟1。

上述算法也可用U（0）作為初始化。這里要求m≥1，當(dāng)m＝1時(shí)上述算法退化為HCM聚類算法。

FCM聚類算法具有很好的適應(yīng)性，但運(yùn)行速度難以滿足現(xiàn)實(shí)需求。另外，模糊因子m的選擇對(duì)算法性能有一定影響。鑒于此，我們基于“競爭學(xué)習(xí)機(jī)制”的思想，提出了抑制式模糊C－均值（S－FCM）聚類算法［10］，具體如下。

在步驟2之前插入一個(gè)對(duì)uij的修改過程。

步驟1＊對(duì)每一個(gè)樣本xj，記

那么

這里0≤α≤1是一個(gè)抑制因子，用于控制抑制的程度。上述修改算法稱為抑制式模糊C－均值（SFCM）聚類算法。可以看到，當(dāng)α＝0時(shí)S－FCM變?yōu)镠CM聚類；α＝1時(shí)S－FCM變?yōu)镕CM聚類。抑制率α的引入，從另一個(gè)途徑建立起FCM和HCM之間的橋梁。大量的實(shí)例表明，S－FCM的分類性能優(yōu)于FCM。

S－FCM聚類算法的思想非常簡單。模糊聚類的目的是為了分類，在計(jì)算過程中獲得的隸屬度，已經(jīng)顯現(xiàn)出樣本的分類趨勢。自然的我們希望隸屬度越大的樣本擁有競爭優(yōu)勢，對(duì)最終分類的話語權(quán)越大。當(dāng)xj到某一個(gè)類中心的隸屬度具有競爭優(yōu)勢時(shí)，應(yīng)該對(duì)這種競爭態(tài)勢予以獎(jiǎng)勵(lì)。換句話說，應(yīng)該對(duì)該樣本到其它類的隸屬度值進(jìn)行抑制，抑制的程度取決于抑制率α，而把抑制的累加值獎(jiǎng)勵(lì)給競爭中的獲勝者。

2 S－FCM聚類算法研究現(xiàn)狀

自從S－FCM聚類算法提出后，國際上很多學(xué)者對(duì)該算法給予關(guān)注，如羅馬尼亞學(xué)者、匈牙利學(xué)者、土耳其學(xué)者、印度學(xué)者、臺(tái)灣學(xué)者、韓國學(xué)者、以色列學(xué)者、孟加拉國學(xué)者、澳大利亞學(xué)者、英國學(xué)者、我國學(xué)者。國際上很多學(xué)者也對(duì)該算法本身及其應(yīng)用進(jìn)行了深入研究。

針對(duì)S－FCM聚類，目前的研究大致上可分為以下6個(gè)部分。

（1）S－FCM 聚類算法的理論分析

有關(guān)S－FCM 聚類算法的理論問題包括：SFCM聚類算法的競爭學(xué)習(xí)機(jī)理是什么？S－FCM聚類算法是否收斂？

羅馬尼亞和匈牙利學(xué)者們從理論的角度研究了S－FCM 聚類算法［11－18］，尤其是LászlóSzilágyi專門以S－FCM聚類算法為主要研究內(nèi)容完成了博士論文（L.Szilágyi，Novel image processing methods based on fuzzy logic，PhD Thesis，BUTE Budapest，2008）［18］。

為了分析S－FCM聚類算法的競爭學(xué)習(xí)行為，LászlóSzilágyi等人分析了抑制率α的作用，通過引入Quasi Learning Rate（QLR）來定性分析抑制效果，得到非獲勝者的抑制率在數(shù)學(xué)上等價(jià)于獲勝者與給定的樣本之間距離的“虛擬”縮短。其結(jié)論是S－FCM聚類算法具有偽競爭性。

為了分析S－FCM 聚類算法的收斂性，László Szilágyi等人提出了S－FCM聚類算法的優(yōu)化版本Optimally Suppressed FCM（OS－FCM）并給出可收斂的迭代算法，通過分析計(jì)算和數(shù)值模擬表明這兩個(gè)算法的性能基本相當(dāng)，這從另一個(gè)側(cè)面表明SFCM聚類算法具有收斂行為，盡管從理論上目前還沒有好的辦法證明其收斂性。

（2）抑制率α的固定選擇

在算法運(yùn)行前經(jīng)驗(yàn)選擇一個(gè)固定的α值，該值與迭代次數(shù)無關(guān)。抑制率α的固定選擇是在原始SFCM中提出的，作為一種折中，建議取α＝0.5以便既保持FCM優(yōu)良的分類性能又體現(xiàn)HCM運(yùn)行速度快的優(yōu)點(diǎn)。實(shí)驗(yàn)結(jié)果表明，S－FCM 在不降低FCM分類性能的同時(shí)運(yùn)行速度有明顯提高。此外，S－FCM對(duì)模糊因子m不太敏感。

（3）抑制率α的不固定選擇

即抑制率α是變化的，換句話說抑制率是迭代次數(shù)的函數(shù)。這一思路改變了原始S－FCM的初衷，其目的不在于提高速度而是更多的關(guān)注更加優(yōu)越的分類性能。

國際模糊工程領(lǐng)域著名專家、臺(tái)灣中原大學(xué)楊敏生教授及其學(xué)生們對(duì)抑制率α的確定進(jìn)行了深刻研究，他們基于原型驅(qū)動(dòng)學(xué)習(xí)的思想給出抑制率α的指數(shù)型選擇公式［19］和相應(yīng)的算法 MS－FCM，通過在核磁共振成像（MRI）圖像上的大量實(shí)驗(yàn)指出“MS－FCM clustering algorithm is more efficient and is strongly recommended as an MRI segmentation technique”。此外，人們還提出了一些抑制率α的其它選擇方法，如臺(tái)灣學(xué)者［20］給出柯西型選擇公式、韓國學(xué)者［21］給出含有模糊因子m的指數(shù)型選擇公式、國內(nèi)學(xué)者［22］給出采用模糊偏差的指數(shù)型選擇公式、孟加拉國學(xué)者［23］引入清晰度來選取更為細(xì)致的抑制率。

（4）在核聚類算法中引入抑制式思想

臺(tái)灣中原大學(xué)楊敏生教授及其學(xué)生們?cè)谄涮岢龅暮司垲愃惴ㄖ星度肓艘种剖礁偁帉W(xué)習(xí)機(jī)制，并將其應(yīng)用于MRI圖像的分割，獲得了滿意的效果［24－26］。

除此之外我國學(xué)者［27－28］、孟加拉國學(xué)者 M.A.Ali及其澳大利亞和英國合作者也對(duì)S－FCM聚類算法進(jìn)行了相關(guān)探討［29－30］。

（5）將抑制式思想應(yīng)用于相關(guān)領(lǐng)域

如抑制式競爭學(xué)習(xí)機(jī)制應(yīng)用于聚類神經(jīng)網(wǎng)絡(luò)［31－33］，抑制式競爭學(xué)習(xí)機(jī)制應(yīng)用于學(xué)習(xí)矢量量化［34］，抑制式競爭學(xué)習(xí)機(jī)制應(yīng)用于支持矢量機(jī)［35］，抑制式競爭學(xué)習(xí)機(jī)制應(yīng)用于粗糙－模糊聚類［36－37］。

（6）用抑制式思想解釋已有算法

S.Krinidis和 V.Chatzis于2010年提出了FLICM算法［38］，最近LászlóSzilágyi［39］分 析了FLICM算法的理論基礎(chǔ)及其存在的錯(cuò)誤，并用SFCM的思想解釋了該算法的細(xì)節(jié)處理過程，以進(jìn)一步修正錯(cuò)誤明辨是非。

經(jīng)過近10年的研究，S－FCM聚類算法所體現(xiàn)的抑制式競爭學(xué)習(xí)機(jī)制的思想逐漸得到國內(nèi)外研究者們的普遍認(rèn)可。正如孟加拉國學(xué)者 M.A.Ali及其澳大利亞和英國合作者在其綜述文章中所評(píng)價(jià)的［40］，抑制式模糊C－均值聚類算法已成為與模糊C－均值聚類算法、可能性C－均值聚類算法一樣的很受歡迎和廣泛使用的模糊聚類算法。印度學(xué)者R.Ravindraiah和K.Tejaswini在其綜述文章中也建議采用抑制式競爭學(xué)習(xí)機(jī)制來加速相關(guān)模糊聚類算法［41］。

3 后期研究的一些建議

盡管對(duì)S－FCM的研究已經(jīng)取得了一些成果，但仍有很多問題值得進(jìn)一步探討，下面列舉幾個(gè)問題供大家研究時(shí)參考。

（1）抑制率α的固定選擇問題。如何根據(jù)數(shù)據(jù)結(jié)構(gòu)選擇合適的α值，目前還沒有進(jìn)一步的報(bào)道。

（2）抑制率α的不固定選擇問題。目前已經(jīng)有一些抑制率α隨迭代次數(shù)變化的選擇辦法，但這些辦法并非惟一的辦法，仍可給出一些其它選擇途徑。

（3）在相關(guān)學(xué)習(xí)算法中嵌入抑制式競爭學(xué)習(xí)機(jī)制。前述的一些學(xué)習(xí)算法已經(jīng)嵌入了抑制式競爭學(xué)習(xí)思想并獲得成功，這為進(jìn)一步在很多學(xué)習(xí)算法中嵌入抑制式思想提供了借鑒依據(jù)，這方面仍有很多工作可做。

（4）依據(jù)偽學(xué)習(xí)率的廣義抑制式模糊C－均值聚類算法。最近，通過改變偽學(xué)習(xí)率而非直接選擇抑制率的方式，L.Szilágyi和S.M.Szilágyi提出了一系列廣義形式的抑制式模糊C－均值聚類算法［17］，這為深入探討開辟了新的途徑，這方面的研究剛剛開始，可做的工作還很多。

［1］Bezdek J C.Pattern Recognition with fuzzy objective function algorithms ［M］.New York： Plenum Press，1981.

［2］Bezdek J C，Keller J，Krishnapuram R，et al.Fuzzy models and algorithms for pattern recognition and image processing［M］.New York：Springer，1999.

［3］Yang M S.A survey of fuzzy clustering［J］.Math Comput Model，1993，18：1－16.

［4］Krishnapuram R，Keller J.A possibilistic approach to clustering［J］.IEEE Trans Fuzzy Syst，1993，1（2）：98－110.

［5］Pal N R，Pal K，Keller J M，et al.A possibilistic fuzzy c－means clustering algorithm［J］.IEEE Trans Fuzzy Systems，2005，13（4）：517－530.

［6］Yu J，Yang M S.Optimality test for generalized FCM and its application to parameter selection［J］.IEEE Trans Fuzzy Systems，2005，13（1）：164－176.

［7］Jian Yu，General C－means clustering model［J］.IEEE Trans PAMI，2005，27（8）：1197－1211.

［8］Yang Z，Chung F－L，Wang S.Robust fuzzy clustering－based image segmentation［J］.Applied Soft Computing，2009，9：80－84.

［9］Zhu L，Chung F－L，Wang S.Generalized fuzzy C－means clustering algorithm with improved fuzzy partitions［J］.IEEE Trans.SMC－PartB，2009，9（3）：578－591.

［10］Fan J L，Zhen W Z，Xie W X.Suppressed fuzzy C－means clustering algorithm［J］.Pattern Recognition Letters，2003，24（9／10）：1607－1612.

［11］Szilágyi L，Szilágyi S M，Benyo Z.A thorough analysis of the suppressed fuzzy C－means algorithm［J］.Progress in Pattern Recognition，Image Analysis and Applications，Lecture Notes in Computer Science，2008，5197：203－210.

［12］Szilágyi L，Szilágyi S M，Benyo Z.Analytical and numerical evaluation of the suppressed fuzzy c－means algorithm［J］.Lecture Notes in Computer Science，2008，5285：146－157.

［13］Szilágyi L，Szilágyi S M，Benyo Z.A unified approach to c－means clustering models［C］／／IEEE International Conference on Fuzzy Systems，2009：456－461.

［14］Szilágyi L，Iclanzan D，Szilágyi S M，et al.A generalized C－means clustering model using optimized via evolutionary computation［C］／／IEEE International Conference on Fuzzy Systems，2009：451－455.

［15］Szilágyi L，Szilágyi S M，Kiss C.A generalized approach to the suppressed fuzzy c－means algorithm［J］.Modeling Decisions for Artificial Intelligence，Lecture Notes in Computer Science，2010，6408：140－151.

［16］Szilágyi L，Szilágyi S M，Benyo Z.Analytical and numerical evaluation of the suppressed fuzzy c－means algorithm：a study on the competition in c－means clustering models［J］.Soft Comput，2010，14：495－505.

［17］Szilágyi L，Szilágyi S M.Generalization rules for the suppressed fuzzy c－means clustering algorithm［J／OL］.Neurocomputing.（2014－04－13）［2014－04－26］.http：／／www.sciencedirect.com／science／article／pii／S0925231214004263.

［18］Szilágyi L.Novel image processing methods based on fuzzy logic［D］.BUTE Budapest，2008.

［19］Hung W L，Yang M S，Chen D H.Parameter selec－tion for suppressed fuzzy C－means with an application to MRI segmentation［J］.Pattern Recognition Letters，2006，27：424－438.

［20］Hung W L，Chang Y C.A modified fuzzy C－means algorithm for differentiation in MRI of ophthalmology［J］.Modeling Decisions for Artificial Intelligence，Lecture Notes in Computer Science，2006，3885：340－350.

［21］Nyma A，Kang M，Kwon Y－K，et al.A hybrid technique for medical image segmentation［J］.Journal of Biomedicine and Biotechnology，2012E－location.DOI：10.1155／2012／830252.

［22］Li Y，Li G.Fast fuzzy c－means clustering algorithm with spatial constraints for image segmentation［J］.Advances in Neural Network Research and Applications，Lecture Notes in Electrical Engineering，2010，67：431－438.

［23］Saad M F，Alimi A M.Improved modified suppressed fuzzy C－means［C］／／2nd International Conference on Image Processing Theory，Tools and Applications（IPTA），2010：313－318.

［24］Hung W L，Yang M S，Chen D H.Segmentation in MRI of ophthalmology using a robust－type clustering algorithm ［C］／／IEEE International Conference on Fuzzy Systems，2009：427－430.

［25］Hung W L，Yang M S，Chen D H.Color image segmentation using cauchy－type fuzzy c－means algorithm［C］／／Fourth International Conference on Fuzzy Systems and Knowledge Discovery，2007：24－27.

［26］Tsai H S，Hung W L，Yang M S.A robust kernelbased fuzzy C－means algorithm by incorporating suppressed and magnified membership for MRI image segmentation［J］.Artificial Intelligence and Computational Intelligence，Lecture Notes in Computer Science，2012，7530：744－754.

［27］黃建軍，謝維信.半抑制式模糊C－均值聚類算法［J］.中國體視學(xué)與圖像分析，2004，9（2）：109－113.

［28］Zhao F，F(xiàn)an J L，Liu H Q.Optimal－selection－based suppressed fuzzy c－means clustering algorithm with self－tuning non local spatial information for image segmentation［J］.Expert Systems with Applications，2014，41（9）：4083－4093.

［29］Ali M A.Karmakar G C，Dooley L S.Fuzzy image segmentation using suppressed fuzzy C－means clustering（SFCM）［C］／／International Conference on Computer and Information Technology（ICCIT 04），2004：363－368.

［30］Ali M A.Laurence S D，Gour C K.Automatic feature set selection for merging image segmentation results using fuzzy clustering［C］／／8th International Conference on Computer and Information Technology （ICCIT’05），2005：28－30.

［31］Liu D，Tang Y，Guan X.Texture segmentation using intensified fuzzy Kohonen clustering Network［C］／／Wang L，Chen K，Ong Y S.ICNC 2005，LNCS 3611，2005：75－80.

［32］Yang M S，Hung W L，Chen D H.Self－organizing map for symbolic data［J］.Fuzzy Sets and Systems，2012，203：49－73.

［33］Chen D H，Hung W L，Yang M S.A batch version of the SOM for symbolic data［C］／／2010Sixth International Conference on Natural Computation（ICNC 2010），2010：1－5.

［34］Hung W L，Chen D H，Yang M S.Suppressed fuzzy－soft learning vector quantization for MRI segmentation［J］.Artificial Intelligence in Medicine，2011，52：33－43.

［35］Zhao Q H，Ha M H，Peng G B，et al.Support vector machine based on half－suppressed fuzzy C－means clustering［C］／／Proceedings of the Eighth International Conference on Machine Learning and Cybernetics.Baoding：IEEE，2009：1236－1240.

［36］Srivastava A，Asati A，Bhattacharya M.A fast and noiseadaptive rough－fuzzy hybrid algorithm for medical image segmentation［C］／／IEEE International Conference on Bioinformatics and Biomedicine，2010：416－421.

［37］Srivastava A，Asati A，Bhattacharya M.Fast hybrid rough－set theoretic fuzzy clustering technique with application to multispectral image segmentation［C］／／Proceedings of the First International Conference on Intelligent Interactive Technologies and Multimedia，2010，126－129.

［38］Krinidis S，Chatzis V.A robust fuzzy local information c－means clustering algorithm［J］.IEEE Trans Image Proc，2010，19（5）：1328－1337.

［39］Szilágyi L.Lessons to learn from a mistaken optimization［J］.Pattern Recognition Letters，2014，36（15）：29－35.

［40］Ali M A，Karmakar C C and Dooley S L.Review on Fuzzy Clustering Algorithms［J］.Journal of Advanced Computations，2008，2（3）：169－181.

［41］Ravindraiah R，Tejaswini K.A survey of image segmentation algorithma based on fuzzy clustering［J］.International Journal of Computer Science and Mobile Computing，2013，2（7）：200－206.