| 高新波 謝維信 摘要 從模糊聚類準(zhǔn)則函數(shù)的演化、算法實(shí)現(xiàn)的途徑、有效性度量方式以及在模式識(shí)別與圖像處理中的應(yīng)用等4個(gè)方面對(duì)模糊聚類理論的研究進(jìn)展做了綜述和評(píng)價(jià)，指出模糊聚類進(jìn)一步研究的幾個(gè)重要方向及其應(yīng)用前景. 聚類就是按照事物間的相似性進(jìn)行區(qū)分和分類的過程，在這一過程中沒有教師指 導(dǎo)，因此是一種無監(jiān)督的分類. 聚類分析則是用數(shù)學(xué)方法研究和處理所給定對(duì)象的分類. “人以群分，物以類聚”，聚類是一個(gè)古老的問題，它伴隨著人類社會(huì) 的產(chǎn)生和發(fā)展而不斷深化，人類要認(rèn)識(shí)世界就必須區(qū)別不同的事物并認(rèn)識(shí)事物間的相似性［1］. 1 模糊聚類目標(biāo)函數(shù)的演化
其中，ζ為懲罰項(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 4種空間劃分概念的比較 |
| 項(xiàng)目 | 可能性聚類 | 模糊聚類 | 傳統(tǒng)聚類 | 半模糊聚類 |
| 標(biāo)記矢量集 | Npc=［0,1］c-O O={(0,0,…,0)T} |  | Nhc={μi∈Nfc: μi∈{0,1},i} | Nsc=Nfc ∪Nhc |
| 物理意義 | 表示每個(gè)樣本 屬于各類的典型程度 | 表示每個(gè)樣本在 各類間的分享程度 | 是樣本嚴(yán)格類屬 的指示函數(shù) | 只有部分樣 本類分模糊 |
| 收斂速度 | 慢 | 較慢 | 快 | 較快 |
| 對(duì)初始化 的敏感性 | 很敏感 | 不很敏感 | 敏感 | 不很敏感 |
| 抗噪性能 | 強(qiáng) | 較強(qiáng) | 弱 | 較強(qiáng) |
| 如何提高可能性劃分的收斂速度并降低它對(duì)初始化的敏感程度，仍然是從模糊劃分角度進(jìn)一步研究模糊聚類的一個(gè)重要方向. 如果在這方面有所突破，就可以得到一種既具有良好的抗噪魯棒性，同時(shí)又能快速收斂到滿意解的空間劃分方法，不僅能從理論上完善現(xiàn)有的模糊軟聚類方法，也必將縮短它的實(shí)用化進(jìn)程. 1.2 對(duì)相似性準(zhǔn)則D(.)的研究 單一的聚類準(zhǔn)則不能解決所有可能的無監(jiān)督分類問題，因此人們提出了多種相似性函數(shù)，比如：最大似然準(zhǔn)則［15］、最大熵準(zhǔn)則［16］、最小體積準(zhǔn)則［17］和信息論準(zhǔn)則［18］等. 不過，實(shí)際中最常用的還是基于最小類內(nèi)加權(quán)平方誤差和準(zhǔn)則. 經(jīng)典的類內(nèi)平方誤差和(WGSS: within-group sum of squared error)準(zhǔn)則函數(shù)最早被用來定義傳統(tǒng)的硬c-均值聚類算法和ISODATA算法. 隨著模糊集理論的提出，Dunn［19］首先把它推廣到加權(quán)的WGSS函數(shù)，后由Bezdek［20］擴(kuò)展到加權(quán)WGSS的無限族，形成了模糊c-均值類型算法的通用聚類準(zhǔn)則，形式如式(1)所示. 對(duì)該準(zhǔn)則函數(shù)的研究主要集中在相似性測(cè)度或者誤差度量D(.)上，一般用樣本與原型間的距離表示. 不同距離度量用來檢測(cè)不同結(jié)構(gòu)的數(shù)據(jù)子集，常用的距離函數(shù)見表2. 表2 常見的距離函數(shù)及特點(diǎn) |
| 名稱 | 距離函數(shù) | 特點(diǎn)功能 |
| Minkowski |  | 對(duì)應(yīng)1≤p≤∞為一族距離測(cè)度，可用來檢測(cè)從◇形超立方體到□形超立方體結(jié)構(gòu)的數(shù)據(jù)子集 |
| Euclidean |  | 對(duì)應(yīng)p=2的Minkowski距離，可用以檢測(cè)特征空間中○形超球體結(jié)構(gòu)的數(shù)據(jù)子集 |
| Hamming | | 對(duì)應(yīng)p=1的Minkowski距離，可用以檢測(cè)特征空間中◇形超立方體結(jié)構(gòu)的數(shù)據(jù)子集 |
| Maximum | | 對(duì)應(yīng)p=∞的Minkowski距離，可用以檢測(cè)特征空間中□形超立方體結(jié)構(gòu)的數(shù)據(jù)子集 |
| Mahalanobis | DA(a,b)=(a-b)TA(a-b), A為正定矩形 | 可用來檢測(cè)特征空間中超橢球結(jié)構(gòu)的數(shù)據(jù)子集 |
| Bobrowski等人［21］分別討論了L1和L∞范數(shù)下的模糊聚類算法(即Hamming和Maximum距離)，發(fā)現(xiàn)在許多情況下它們比常用的歐氏范數(shù)L2能獲得更好的結(jié)果，建議在聚類分析中要選擇合適的距離函數(shù). 另外Mahalanobis距離的一種特例——加權(quán)歐氏距離(對(duì)應(yīng)A為對(duì)角陣)還被廣泛地使用于模式各維特征對(duì)分類貢獻(xiàn)不同的應(yīng)用背景［22］. 在給定數(shù)據(jù)中搜索一個(gè)結(jié)構(gòu)可以看做尋找合適的距離函數(shù). 這就給我們留下了一個(gè)問題：選擇合適距離的準(zhǔn)則是什么?能否構(gòu)造一種不依賴于事先定義距離測(cè)度的模糊聚類算法?現(xiàn)有文獻(xiàn)很少涉及這一問題，仍屬于有待解決的范疇. 1.3 對(duì)聚類原型B的研究 基于目標(biāo)函數(shù)的模糊聚類又稱做基于原型的聚類，因?yàn)槟繕?biāo)函數(shù)的構(gòu)造依賴于原型的定義，因此原型的類型必須事先給定. 聚類原型的研究是伴隨著聚類應(yīng)用 的發(fā)展和需求而展開的，最初的聚類分析只應(yīng)用于特征空間中超球體聚類結(jié)構(gòu)的檢測(cè)，因此原型為特征空間中的“點(diǎn)”，或者叫聚類中心［20］；為了處理非超球體的聚類結(jié)構(gòu)，Bezdek［23］提出了通過點(diǎn)v∈Rp的r(0≤r≤p-1)維線性簇原型Br(v:{si})={v}+Span({si})，其特點(diǎn)見表3. 表3 幾種原型的特點(diǎn)比較 |
| 線性簇維數(shù) | 聚類原型 | 功能特點(diǎn) |
| r=0 | B0(v;I)=v：點(diǎn) | 檢測(cè)超球體和橢球體結(jié)構(gòu)的子集 |
| r=1 | B1(v;s)=L(v;s)：線 | 檢測(cè)線性結(jié)構(gòu)的模式子集 |
| r=2 | B2(v;s1,s2)=P(v;s1,s2):平面 | 檢測(cè)平面結(jié)構(gòu)的模式子集 |
| 2<r≤p-1 | Bp-1(v；{si})=HP(v；{si})：超平面 | 檢測(cè)超平面結(jié)構(gòu)的模式子集 |
| 此外，為了檢測(cè)呈“薄殼”結(jié)構(gòu)的模式子集，Dave提出球殼［24］和橢球殼［25］兩種原型，并將其應(yīng)用于邊緣檢測(cè)中獲得了較好的效果. 隨著應(yīng)用的需求殼原型被推廣到矩形殼［26］、多面體殼［27］以及任意形狀的殼原型［28］等多種類型，而對(duì)于線性原型也逐步被擴(kuò)展為拋物線［29］、二次曲線以及任意二次多項(xiàng)式形式的原型［30］. 基于目標(biāo)函數(shù)的聚類對(duì)原型有較強(qiáng)的依賴性，因此要求一方面必須充分利用先驗(yàn)知識(shí)選擇合適的原型，另一方面必須與距離測(cè)度相結(jié)合研究，構(gòu)造合理的相似性度量. 1.4 對(duì)加權(quán)指數(shù)m的研究 在模糊聚類目標(biāo)函數(shù){Jm: 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)集 針對(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í)檢測(cè)橢球形結(jié)構(gòu)和線性結(jié)構(gòu)，Jawahar等人［43］又對(duì)不同的幾何結(jié)構(gòu)聚類的檢測(cè)做了一定的嘗試，除此以外很少有這方面的研究報(bào)道. 因此，對(duì)于這3種數(shù)據(jù)集的分析遺留了很多問題，要使模糊聚類真正走向?qū)嵱没?，就必須進(jìn)一步分析實(shí)際數(shù)據(jù)的各種情況，研究“可充分利用先驗(yàn)知識(shí)的聚類算法”、“能容噪的魯棒算法”和“可同時(shí)檢測(cè)多種結(jié)構(gòu)的聚類方法”等. 2 模糊聚類算法實(shí)現(xiàn)途徑的研究 表4 2種聚類神經(jīng)網(wǎng)絡(luò)的比較 |
| 項(xiàng)目 | Kohonen聚類網(wǎng)絡(luò) | Grossberg聚類網(wǎng)絡(luò) |
| 輸入量 | 精確的數(shù)值量 | 數(shù)值量或模糊語言量 |
| 輸出量 | 聚類原型(特征矢量) | 分類結(jié)果和類別數(shù) |
| 學(xué)習(xí)方式 | 競(jìng)爭(zhēng)學(xué)習(xí)(梯度下降) | 模糊邏輯操作 |
| 聚類數(shù)目 | 事先給定 | 自動(dòng)確定 |
| 功能用途 | 球型硬聚類、特征映射 | 球型硬聚類、模式分類 |
| 用神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)聚類分析顯著的優(yōu)勢(shì)在于神經(jīng)網(wǎng)絡(luò)的并行處理，因?yàn)樵诖髷?shù)據(jù)量 情況下聚類是相當(dāng)耗時(shí)的. 然而，以上兩種聚類網(wǎng)絡(luò)仍存在應(yīng)用的局限性——只能實(shí)現(xiàn)球型的硬聚類，為此人們?cè)谀：窠?jīng)網(wǎng)絡(luò)的集成研究方面做了不懈的努力. 從總體上看，模糊聚類神經(jīng)網(wǎng)絡(luò)的研究可分為兩類：一類是從目標(biāo)函數(shù)法演變而來的，其基礎(chǔ)是模糊競(jìng)爭(zhēng)學(xué)習(xí)算法，比較有代表性的如Pal和Bezdek［53］提出的基于競(jìng)爭(zhēng)學(xué)習(xí)的模糊聚類網(wǎng)絡(luò)，解決了球型分布樣本的模糊聚類；Xu［54］提出了帶懲罰項(xiàng)的競(jìng)爭(zhēng)學(xué)習(xí)算法，可以自動(dòng)確定聚類數(shù)；Zhang［55］提出了一種基于Gauss非線性的競(jìng)爭(zhēng)學(xué)習(xí)算法，用于模糊聚類并給出了硬件實(shí)現(xiàn)方法. 另一類模糊聚類神經(jīng)網(wǎng)絡(luò)由模糊邏輯操作構(gòu)成，比如Carpenter等人［56］在ART基礎(chǔ)上發(fā)展的模糊ART，比ART在性能上有較大的改善，Simpson［57］提出的模糊Min-Max網(wǎng)絡(luò)實(shí)現(xiàn)了超盒子形狀的模糊聚類，但這類網(wǎng)絡(luò)的研究很分散，不僅數(shù)量少，理論上也不很成熟. 2.3 基于進(jìn)化計(jì)算的實(shí)現(xiàn) 進(jìn)化計(jì)算是建立在生物進(jìn)化基礎(chǔ)之上基于自然選擇和群體遺傳機(jī)理的隨機(jī)搜索算法. 由于它全局并行搜索，故可以較高的概率獲得全局最優(yōu)解. 此外進(jìn)化計(jì) 算還具有簡(jiǎn)單、通用和魯棒性強(qiáng)等優(yōu)點(diǎn). 為了獲得快速準(zhǔn)確的聚類，人們把進(jìn)化計(jì)算引入到模糊聚類中，形成了一系列基于進(jìn)化計(jì)算的模糊聚類算法. 這一系列算法大致可分為3種類型：一是基于模擬退火的方法，比如有對(duì)模糊分類矩陣U退火處理的［58］，有對(duì)聚類原型漸進(jìn)優(yōu)化的［59］，然而由于模擬退火算法只有當(dāng)溫度下降足夠慢時(shí)才能收斂到全局最優(yōu)點(diǎn)，極大的運(yùn)算時(shí)間限制了其實(shí)用性；二是基于遺傳算法［60］和進(jìn)化策略［61］的方法，這方面的研究主要集中在解的編碼方案、適應(yīng)度函數(shù)的構(gòu)造以及遺傳算子和操作參數(shù)等方面1)；三是基于Tabu搜索的算法，主要是AL-Sultan做了一些探索和嘗試［62］，這方面的研究還是很初步的，有待于進(jìn)一步的深入. 對(duì)比上述3類模糊聚類的實(shí)現(xiàn)途徑，得到如表5所示的結(jié)果. 從表中可知，3種方法各有優(yōu)缺點(diǎn)，從而啟發(fā)我們結(jié)合各自的優(yōu)點(diǎn)去構(gòu)造速度快、精度高而且對(duì)初始化不敏感的模糊聚類算法，比如把梯度算子引入進(jìn)化計(jì)算中，用進(jìn)化計(jì)算來訓(xùn)練神經(jīng)網(wǎng)絡(luò)等，都是很有前途的方向. 表5 3種模糊聚類實(shí)現(xiàn)途徑的比較 |
| 項(xiàng)目 | 基于迭代優(yōu)化的方法 | 基于神經(jīng)網(wǎng)絡(luò)的方法 | 基于進(jìn)化計(jì)算的方法 |
| 搜索本質(zhì) | 梯度下降 | 梯度下降 | 隨機(jī)搜索 |
| 收斂速度 | 較快 | 快 | 慢 |
| 算法精度 | 高 | 高 | 受編碼長(zhǎng)度限制 |
| 算法結(jié)構(gòu) | 串行 | 各維特征間并行 | 各個(gè)體間并行 |
| 初始化敏感性 | 敏感 | 敏感 | 不敏感 |
3 模糊聚類有效性的研究 對(duì)于給定的數(shù)據(jù)集，首先需要判斷有無聚類結(jié)構(gòu)，這屬于聚類趨勢(shì)研究的課題，如果已經(jīng)確認(rèn)有聚類結(jié)構(gòu)則需要用算法來確定這些結(jié)構(gòu)，這屬于聚類分析研究的 課題. 得到聚類結(jié)構(gòu)后，則需要分析聚類的結(jié)果是否合理，這屬于聚類有效性研究的課題. 對(duì)聚類分析而言，有效性問題又可以轉(zhuǎn)化為最佳類別數(shù)c的確定［20］. 歷史上有關(guān)聚類有效性問題的研究大都是基于硬c-均值和模糊c-均值算法的，Dubes［9］和Jain［63］曾對(duì)80年前的研究做過評(píng)述. 現(xiàn)有的聚類有效性函數(shù)按其定義方式可分為：基于數(shù)據(jù)集模糊劃分的、基于數(shù)據(jù)集幾何結(jié)構(gòu)的和基于數(shù)據(jù)集統(tǒng)計(jì)信息的3類，3類的理論基礎(chǔ)和特點(diǎn)均列于表6中. 表6 3類聚類有效性函數(shù)的特點(diǎn)比較 |
| 比較項(xiàng)目 | 基于模糊劃分 | 基于幾何結(jié)構(gòu) | 基于統(tǒng)計(jì)信息 |
| 理論基礎(chǔ) | 好的聚類分析對(duì)應(yīng)于數(shù)據(jù)集較“分明”的劃分 | 每個(gè)子類應(yīng)當(dāng)是緊致的而且子類間是盡可能分離的 | 最佳分類對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)提供的統(tǒng)計(jì)信息最好 |
| 優(yōu)點(diǎn) | 簡(jiǎn)單、運(yùn)算量小 | 與數(shù)據(jù)集的結(jié)構(gòu)密切相關(guān) | 與數(shù)據(jù)集分布密切相關(guān) |
| 缺點(diǎn) | 與數(shù)據(jù)集的結(jié)構(gòu)特征缺乏直接聯(lián)系 | 表述比較復(fù)雜、運(yùn)算量大 | 性能依賴統(tǒng)計(jì)假設(shè)與數(shù)據(jù)分布的一致性 |
| 代表性研究 | Zadeh的分離度［20］ Bezdek的劃分熵［20］ Windham的比例系數(shù)［64］ | Dunn的劃分系數(shù)［65］ Gunderson的分離系數(shù)［66］ Xie-Beni指標(biāo)［67］ | Vogel等人的PFS聚類［68］ Jain等人的自舉法［69］ Beni的熵形式有效性函數(shù)［70］ |
| 沒有萬能的模糊聚類有效性函數(shù)，這也是有效性函數(shù)層出不窮的原因. 既然單一的度量方式不能解決所有可能的聚類有效性問題，那么現(xiàn)有的有效性函數(shù)將長(zhǎng)期并存. 能否給出一種啟發(fā)式的方法來幫助人們選擇適合于待分析問題的有效性函數(shù)呢?答案是肯定的，但這將是一項(xiàng)艱巨的工程. 另外，現(xiàn)有聚類有效性函數(shù)多是針對(duì)模數(shù)c-均值算法的，除了Dave［71］和Krishnapuram［30］提出過針對(duì)模糊c-殼聚類的有效性函數(shù)外，很少有人討論面向模糊線、面以及其他原型聚類算法的有效性問題，此外對(duì)可能性聚類、半模糊聚類的有效性度量也需要進(jìn)一步豐富和發(fā)展，以便完善聚類有效性理論. 上述模糊聚類有效性函數(shù)，主要被用來確定合理的聚類數(shù)，以保證算法得到更有效的分類結(jié)果. 而在實(shí)際的聚類中，即使分類數(shù)選取得合適，由于選取的算法 不合適或者算法的參數(shù)選取得不合適，也可能得不到數(shù)據(jù)的真實(shí)結(jié)構(gòu). 這促使人們?nèi)ふ夷苤笇?dǎo)聚類算法得到更符合實(shí)際分類的函數(shù). 這方面的工作首先是由 Huntsbergery［72］進(jìn)行的，他將模糊c-均值聚類算法應(yīng)用于圖像分割，為了得到理想的分割效果，引入了一個(gè)指導(dǎo)分割的函數(shù)；后來，Bcnsaid等人［73］修改了Xie-Beni指標(biāo)［67］，提出了一個(gè)指導(dǎo)分類的新標(biāo)準(zhǔn)，并在其文章中明確指出對(duì)聚類有效性函數(shù)的研究不僅能回答數(shù)據(jù)集的最佳分類問題，而且能有效地指導(dǎo)聚類算法得到更符合實(shí)際的分類. 4 模糊聚類的應(yīng)用研究 1) 見2246頁(yè)腳注1) |
聯(lián)系客服
