高新波　謝維信

摘要　從模糊聚類準則函數的演化、算法實現的途徑、有效性度量方式以及在模式識別與圖像處理中的應用等4個方面對模糊聚類理論的研究進展做了綜述和評價，指出模糊聚類進一步研究的幾個重要方向及其應用前景.　
關鍵詞　聚類分析　模糊聚類　聚類有效性　模式識別　圖像處理

　　聚類就是按照事物間的相似性進行區(qū)分和分類的過程，在這一過程中沒有教師指 導，因此是一種無監(jiān)督的分類.　聚類分析則是用數學方法研究和處理所給定對象的分類.　“人以群分，物以類聚”，聚類是一個古老的問題，它伴隨著人類社會 的產生和發(fā)展而不斷深化，人類要認識世界就必須區(qū)別不同的事物并認識事物間的相似性^［1］.　
傳統(tǒng)的聚類分析是一種硬劃分，它把每個待辨識的對象嚴格地劃分到某個類中，具有非此即彼的性質，因此這種分類的類別界限是分明的.　而實際上大多數對象并沒有嚴格的屬性，它們在性態(tài)和類屬方面存在著中介性，適合進行軟劃分.　Zadeh^［2］提 出的模糊集理論為這種軟劃分提供了有力的分析工具，人們開始用模糊的方法來處理聚類問題，并稱之為模糊聚類分析.　由于模糊聚類得到了樣本屬于各個類別的 不確定性程度，表達了樣本類屬的中介性，即建立起了樣本對于類別的不確定性的描述，能更客觀地反映現實世界，從而成為聚類分析研究的主流.
模糊劃分的概念最早由Ruspini^［3］提出，利用這一概念人們提出了多種聚類方法，比較典型的有：基于相似性關系和模糊關系的方法(包括聚合法和分裂法)^［4］，基于模糊等價關系的傳遞閉包方法^［5］、基于模糊圖論最大樹方法^［6］， 以及基于數據集的凸分解、動態(tài)規(guī)劃和難以辨識關系等方法.　然而由于上述方法不適用于大數據量情況，難以滿足實時性要求高的場合，因此其實際的應用不夠廣 泛，故在該方面的研究也就逐步減少了.　實際中受到普遍歡迎的是基于目標函數的方法，該方法設計簡單、解決問題的范圍廣，最終還可以轉化為優(yōu)化問題而借助 經典數學的非線性規(guī)劃理論求解，并易于計算機實現.　因此，隨著計算機的應用和發(fā)展，該類方法成為聚類研究的熱點.　
以下將從目標函數的演化、算法的實現途徑、有效性度量方式以及在實際中的應用等4個方面綜述基于目標函數的模糊聚類方法的研究進展.　有關傳統(tǒng)聚類分析以及其他的模糊聚類方法的系統(tǒng)總結可參見文獻［1，7～10］.　

1　模糊聚類目標函數的演化
模糊聚類問題可以用數學語言描述為：把一組給定的模式O={o₁,o₂,…，o_n}劃分為c個模糊子集(聚類)S₁,S₂,…,S_c.　如果用μ_ik(1≤i≤c, 1≤k≤n)表示模式o_k隸屬于模糊子集S_i的程度，那么就得到了這組模式的模糊c-劃分U={μ_ik|1≤i≤c, 1≤k≤n}.　完成這樣一組無類別標記模式集模糊劃分的操作就是模糊聚類分析.為了獲得有意義的分類，需要定義劃分的準則，如相似性或相異性準則D(^.)等.　假定每個模糊子集S_i(1≤i≤c)都有一個典型模式p_i，常被稱做聚類原型，這樣任一模式o_k與模糊子集S_i的相似性可以通過模式o_k與聚類原型p_i間的失真度d_ik=D(o_k,p_i)來度量.　
基于目標函數的模糊聚類主要是利用模式集O的觀測值X={x₁,x₂,…,x_n}R_s與原型特征值B={β_i, 1≤i≤c}之間的距離構造一個目標函數，然后通過優(yōu)化這一帶約束的非線性規(guī)劃問題獲得最佳的模糊c-劃分：

　　　　　　(1)

其中，ζ為懲罰項，f(μ_ik)∈C為約束條件，m為加權指數.　這樣，模糊聚類的目標函數就由參量集{U,D(^.),B,m,X}而確定.　對應于這些參量，模糊聚類目標函數的發(fā)展演化可以從以下5個大的方面來概括.　
1.1　對模糊劃分矩陣U的研究
傳統(tǒng)的聚拎分析為一種硬劃分，μ_i(x_k)∈{0,1}為樣本x_k類屬的指示函 數，而類別標記矢量μ(x_k)=(μ_1k,μ_2k,…,μ_ck)^T則成為歐氏c-空間的基矢量.　為了表達模式間的相近信息，Ruspini^［3］引入了模糊劃分的概念，令μ_i(x_k)∈［0,1］，把標記矢量μ(x_k)擴展為歐氏c-空間中的超平面，這樣標記矢量既可稱做模糊標記又可稱為概率標記.　由于存在概率約束，使得隸屬函數只能表示模式在模糊類間的分享程度，而不能反映典型性，為此Krishnapuram等人^［11］提出可能性c-劃分的概念，放松了概率約束，從而使標記矢量μ(x_k) 變?yōu)槌ピc的單位超立方體.　由此而產生的可能性聚類算法具有良好的抗噪性能，但收斂速度慢，容易陷入局部極值點而得不到最優(yōu)分類.　為了結合傳統(tǒng)硬聚 類的收斂速度和模糊聚類的對初始化不敏感(獲得全局最優(yōu)解的概率大)而且能反映樣本間相近信息等優(yōu)點，Selim和Ismail^［12］提出了半模糊劃分的概念，只保留劃分矩陣中較模糊的元素，其余的元素作去模糊處理.　這樣使劃分矩陣U既具有一定的明晰性，又保持了樣本在空間分布的模糊性，從而提高了分類識別的正確性.　后來，Kamel等人^［13］以及裴繼紅等人^［14］分別從不同的角度提出了改進型的半模糊劃分方法，即為閾值型軟聚類算法和截集模糊軟聚類算法.　上述幾種軟劃分的比較顯示在表1中.　

表1　4種空間劃分概念的比較

表2　常見的距離函數及特點

表3　幾種原型的特點比較

　　此外，為了檢測呈“薄殼”結構的模式子集，Dave提出球殼^［24］和橢球殼^［25］兩種原型，并將其應用于邊緣檢測中獲得了較好的效果.　隨著應用的需求殼原型被推廣到矩形殼^［26］、多面體殼^［27］以及任意形狀的殼原型^［28］等多種類型，而對于線性原型也逐步被擴展為拋物線^［29］、二次曲線以及任意二次多項式形式的原型^［30］.　
基于目標函數的聚類對原型有較強的依賴性，因此要求一方面必須充分利用先驗知識選擇合適的原型，另一方面必須與距離測度相結合研究，構造合理的相似性度量.　
1.4　對加權指數m的研究
在模糊聚類目標函數{J_m: 1<m<∞}中，Bezdek^［20］引入了加權指數m，使Dunn的聚類準則變成m=2時的特例.　有人認為從數學上看參數m的出現不自然也沒有必要^［16］，但是對于從硬聚類準則函數推廣得到的目標函數(1)，如果不給隸屬度乘一個權重，這種推廣則是無效的.　參數m又稱為平滑因子，控制著模式在模糊類間的分享程度^［20］，因此，要實現模糊聚類就必須選定一個m，然而最佳m的選取目前尚缺乏理論指導.　
Bezdek^［31］給出過一個經驗范圍1.1≤m≤5；后又從物理解釋上得出m=2最有意義；Chan等人^［32］從漢字識別的應用背景得出m的最佳取值應在1.25～1.75之間；Bezdek等人^［33］從算法收斂性角度著手，得出m的取值與樣本數目n有關的結論，建議m的取值要大于n/(n-2)；Pal等人^［34］則從聚類有效性的實驗研究中得到m的最佳選取區(qū)間應為［1.5，2.5］，在不作特殊要求下可取區(qū)間中值m=2.　
上述有關m取值范圍，大都來自實驗和經驗，均為啟發(fā)式的，一方面不夠系統(tǒng)，另一方面沒有給出具體的優(yōu)選算法.　此外，也還缺乏最優(yōu)m的檢驗方法.　這一系列的開放問題，都值得進一步的探索，以便奠定m優(yōu)選的理論基礎.　
1.5　對各種數據集X聚類的研究
在實際應用中會遇到不同的數據類型，因此要研究模糊聚類的目標函數就必須首先研究所要處理的數據類型.　常見的數據大都為特征空間中的點集，除此以外，人們還研究了關系數據^［35］、方向數據^［36］、區(qū)間型數據和模糊數^［37］等形式，并得出了一些有意義的結論.　還有一種類型的數據——符號數據^［38］，也引起了廣泛的關注.　這種數據不僅包括一般數值型數據，還包括區(qū)間數、模糊數和語言量等形式，在模糊概念聚類方面有著較多的研究和應用，但這些類型的數據并不常用，實際中最常遇到的數據多數為部分有標記的、噪聲污染的和多種結構混合的數據.　
針對存在部分標記的數據，為了獲得更好的聚類效果，Pezdrcy^［39］提出了部分監(jiān)督的模糊聚類算法，以利用數據中蘊涵的先驗知識.　Bensaid^［40］又進一步發(fā)展了該理論，把它應用于圖像分割中，并取得了良好的效果.　對于噪聲污染的數據，更是涌現了大批的魯棒聚類算法以克服噪聲干擾，Dave等人^［41］對這些方法做了很好的總結，在此不再贅述.　至于多種結構并存的數據，只有Gustafson等人^［42］提出的模糊協(xié)方差矩陣聚類方法能同時檢測橢球形結構和線性結構，Jawahar等人^［43］又對不同的幾何結構聚類的檢測做了一定的嘗試，除此以外很少有這方面的研究報道.　
因此，對于這3種數據集的分析遺留了很多問題，要使模糊聚類真正走向實用化，就必須進一步分析實際數據的各種情況，研究“可充分利用先驗知識的聚類算法”、“能容噪的魯棒算法”和“可同時檢測多種結構的聚類方法”等.　

2　模糊聚類算法實現途徑的研究
有了聚類的準則函數，接下來就是如何優(yōu)化目標函數獲得最佳聚類的問題了，即研究算法的實現途徑.　現有的實現途徑主要分為3類：基于交替優(yōu)化(AO)、神經網絡(NN)和進化計算(EC)等方法.　以下概述這3方面的研究進展.　
2.1　基于交替優(yōu)化的實現
在優(yōu)化目標函數的過程中，人們曾試探過動態(tài)規(guī)劃、分支定界和凸切割等方法，然而大量的存貯空間和運行時間限制了其應用.　實際中應用最為廣泛的是Dunn和Bezdek^{［19，20］}提出的迭代優(yōu)化算法——模糊c-均值類型的算法，到目前為止，對它的研究主要集中在收斂性證明、算法停止準則的設立以及原型初始化等方面.　
幾經修補，最后證得交替優(yōu)化算法沿一個子序列收斂到目標函數的極值點或鞍點^{［44，45］}.　對于停止準則，提出了以連續(xù)兩代的原型變化量小于某個閾值和劃分矩陣變化量小于某個閾值兩類方法^［46］.　不幸的是，由于迭代優(yōu)化本質上屬于局部搜索的爬山法，很容易陷入局部極值點，因此對初始化較敏感.　為了獲得全局最優(yōu)解或滿意解，人們把希望寄托在好的初始化上，比較有名的初始化方法有Yager等人^［47］提出的山函數或勢函數法，不過該方法的計算量隨樣本維數呈指數增長，為此，Chiu^［48］提出改進算法使計算量只與樣本數目有關，解決了計算精度與復雜度之間的矛盾；此外還有Chaudhuri^［49］的密度函數估計法、Postaire^［50］的形態(tài)學方法以及模糊測度法和Marr算子等方法.　
2.2　基于神經網絡的實現
神經網絡在聚類分析中的應用首先起源于Kohonen^［51］的兩項工作——學習矢量量化和自組織特征映射以及Grossberg^［52］的自適應共振理論，兩者的主要情況如表4所示.　

表4　2種聚類神經網絡的比較

表5　3種模糊聚類實現途徑的比較

表6　3類聚類有效性函數的特點比較

4　模糊聚類的應用研究
模糊聚類理論的發(fā)展推動了其在生產實踐中的應用，反過來實際應用的需求又促進了模糊聚類理論的不斷豐富和完善.　隨著理論的發(fā)展，模糊聚類已經在眾多 的領域獲得廣泛的應用，并取得了令人滿意的效果和可觀的效益.　其應用范圍涉及到通訊系統(tǒng)中的信道均衡、矢量量化編碼中的碼書設計、時間序列的預測、神經 網絡的訓練、參數估計、醫(yī)學診斷、天氣預報、食品分類、水質分析等領域.　對上述應用的介紹，有興趣的讀者可參見文獻［1，7～10，20］和高新波的論 文¹⁾，本文不再贅述.　鑒于模糊聚類在模式識別和圖像處理兩個領域中相當成功的應用，以下主要對這兩方面詳細介紹.　
4.1　模糊聚類在模式識別中的應用
模式識別中兩大主要的分支為有監(jiān)督的分類和無監(jiān)督分類，而其中無監(jiān)督分類與聚類分析相對應.　正是由于模糊聚類與模式識別的天然聯系，使得它首先在模式識別領域獲得成功的應用.　模糊聚類不需要訓練樣本，可直接通過機器學習達到自動分類的目的.　
模式識別中一個最重要的問題是特征提取，模糊聚類不但能從原始數據中直接提取特征^［74］，還能對已經得到的特征進行優(yōu)選和降維操作^［75］，以免造成“維數災難”；在提取完特征后就需要分類器設計，模糊聚類算法既可以提供最近鄰原型分類器^［75］，還可以用來進行特征空間劃分和模糊規(guī)則提取，以構造基于模糊IF-THEN規(guī)則的分類器^［76］；在物體識別或線條檢測中，模糊聚類既可以直接用于原始數據上^{［24，25，30］}，也可以用于變換域中，比如Hough變換中峰值檢測問題一直困繞著其推廣應用，Jolion等人^［77］提出基于模糊聚類的峰值檢測方法，解決了這一難題，使得Hough變換可以自動執(zhí)行，方便快捷；另外在不變性模式識別中也有借助模糊聚類技術的報道.　
在一些模式識別的具體應用中，模糊聚類也取得了較好的效果，比如漢字字符識別中的字符預分類^［78］；語音識別中的分類和匹配^［79］；雷達目標識別中目標庫的建立和新到目標的歸類^［80］等等，在此不再一一列舉.　
4.2　模糊聚類在圖像處理中的應用
圖像處理是計算機視覺的重要組成部分，由于人眼視覺的主觀性使圖像比較適合用模糊手段處理，同時訓練樣本圖像的匱乏又需要無監(jiān)督分析，而模糊聚類正好滿足這兩方面的要求，因此成為圖像處理中一個強大的研究分析工具.　
模糊聚類在圖像處理中最為廣泛的應用為圖像分割，由于圖象分割問題可以等效為象素的無監(jiān)督分類，因此早在1979年Coleman和Andrews^［81］就提出用聚類算法進行圖像分割，此后基于二維直方圖^［82］、塔型結構^［83］、小波分析^［84］、分形分維^［85］等一系列新技術，人們又相繼提出了多種基于模糊聚類的灰度圖像分割新方法，并且在紋理圖像分割^［86］、彩色圖像分割¹⁾、序列圖像分割¹⁾、遙感圖像分割^［86］等方面也獲得了很大的進展.　
基于模糊聚類的方法在邊緣檢測^{［24，25，30］}、圖像增強^［87］、圖像壓縮^［88］、曲線擬合²⁾等眾多方面的研究同樣也取得了豐碩的成果.　
隨著應用的發(fā)展，對模糊聚類理論又提出了許多新的要求，比如聚類算法的快速實現在圖像處理的應用中要求極為迫切；必須把模糊聚類同新的技術相結合才能 取得好的結果；只有充分挖掘和利用實際應用中的先驗知識，并指導聚類才有望在速度和質量上同步提高；另外，現有的模糊聚類都是針對靜態(tài)數據的，還需研究數 據動態(tài)變化或數據不斷到達情況的分析方法.　上述種種還需在理論上繼續(xù)開拓和創(chuàng)新.

1) 見2246頁腳注1)
2) 見2246頁腳注1)
致謝　本工作為國家自然科學基金(批準號：69472046)資助項目.
作者簡介：1) 高新波.　基于進化計算和神經網絡的模糊聚類新算法研究.　西安電子科技大學碩士論文，1996
2) 裴繼紅.　基于模糊信息處理的圖像分割方法研究.　西安電子科技大學博士論文，1998
作者單位：西安電子科技大學電子工程學院（高新波）
深圳大學（謝維信）