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

范九倫

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

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

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

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

1 S－FCM聚類算法

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

模糊聚類問題可表述為數學規劃

使得

這里U＝｛uij｝是一個c×n矩陣，V＝［v1，v2，…，vc］是一個q×c矩陣。該數學規劃問題可如下求解［1］。

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

步驟1 用（2a）和（2b）計算U（k）。

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

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

步驟2 用（2c）計算V（k＋1）。

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

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

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

在步驟2之前插入一個對uij的修改過程。

步驟1＊對每一個樣本xj，記

那么

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

S－FCM聚類算法的思想非常簡單。模糊聚類的目的是為了分類，在計算過程中獲得的隸屬度，已經顯現出樣本的分類趨勢。自然的我們希望隸屬度越大的樣本擁有競爭優勢，對最終分類的話語權越大。當xj到某一個類中心的隸屬度具有競爭優勢時，應該對這種競爭態勢予以獎勵。換句話說，應該對該樣本到其它類的隸屬度值進行抑制，抑制的程度取決于抑制率α，而把抑制的累加值獎勵給競爭中的獲勝者。

2 S－FCM聚類算法研究現狀

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

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

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

有關S－FCM 聚類算法的理論問題包括：SFCM聚類算法的競爭學習機理是什么？S－FCM聚類算法是否收斂？

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

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

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

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

在算法運行前經驗選擇一個固定的α值，該值與迭代次數無關。抑制率α的固定選擇是在原始SFCM中提出的，作為一種折中，建議取α＝0.5以便既保持FCM優良的分類性能又體現HCM運行速度快的優點。實驗結果表明，S－FCM 在不降低FCM分類性能的同時運行速度有明顯提高。此外，S－FCM對模糊因子m不太敏感。

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

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

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

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

臺灣中原大學楊敏生教授及其學生們在其提出的核聚類算法中嵌入了抑制式競爭學習機制，并將其應用于MRI圖像的分割，獲得了滿意的效果［24－26］。

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

（5）將抑制式思想應用于相關領域

如抑制式競爭學習機制應用于聚類神經網絡［31－33］，抑制式競爭學習機制應用于學習矢量量化［34］，抑制式競爭學習機制應用于支持矢量機［35］，抑制式競爭學習機制應用于粗糙－模糊聚類［36－37］。

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

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

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

3 后期研究的一些建議

盡管對S－FCM的研究已經取得了一些成果，但仍有很多問題值得進一步探討，下面列舉幾個問題供大家研究時參考。

（1）抑制率α的固定選擇問題。如何根據數據結構選擇合適的α值，目前還沒有進一步的報道。

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

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

（4）依據偽學習率的廣義抑制式模糊C－均值聚類算法。最近，通過改變偽學習率而非直接選擇抑制率的方式，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］.中國體視學與圖像分析，2004，9（2）：109－113.

［28］Zhao F，Fan 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.