高新波　謝維信

摘要　從模糊聚類準(zhǔn)則函數(shù)的演化、算法實(shí)現(xiàn)的途徑、有效性度量方式以及在模式識(shí)別與圖像處理中的應(yīng)用等4個(gè)方面對(duì)模糊聚類理論的研究進(jìn)展做了綜述和評(píng)價(jià)，指出模糊聚類進(jìn)一步研究的幾個(gè)重要方向及其應(yīng)用前景.　
關(guān)鍵詞　聚類分析　模糊聚類　聚類有效性　模式識(shí)別　圖像處理

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

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

　　　　　　(1)

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

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

表2　常見的距離函數(shù)及特點(diǎn)

表3　幾種原型的特點(diǎn)比較

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

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

表4　2種聚類神經(jīng)網(wǎng)絡(luò)的比較

表5　3種模糊聚類實(shí)現(xiàn)途徑的比較

表6　3類聚類有效性函數(shù)的特點(diǎn)比較

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

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