高云龍，賴文馨，潘金艷，康麗雯

(1.廈門大學(xué)航空航天學(xué)院，福建 廈門 361102；2.集美大學(xué)信息工程學(xué)院，福建 廈門 361021)

模式識(shí)別是一種計(jì)算機(jī)和數(shù)學(xué)技術(shù)的結(jié)合，它通過對(duì)研究對(duì)象的分析研究，揭示其各因素之間存在的確定或是隨機(jī)的規(guī)律，從而達(dá)到對(duì)研究對(duì)象描述、辨別、分類以及解釋的目的.其技術(shù)方法主要分為監(jiān)督模式識(shí)別與無監(jiān)督模式識(shí)別.監(jiān)督模式識(shí)別是指用一種已知類別樣本作為訓(xùn)練集，建立分類器；而無監(jiān)督模式識(shí)別是在未知?jiǎng)澐诸悇e與訓(xùn)練樣本的情況下，對(duì)未知樣本進(jìn)行特征提取，進(jìn)而進(jìn)行聚類分析.無監(jiān)督聚類分析算法的研究是模式識(shí)別領(lǐng)域的熱門問題.

C均值是一種典型的無監(jiān)督硬劃分聚類算法，而基于C均值提出的模糊C均值(fuzzyC-means,FCM)聚類算法，雖然有效地解決了C均值聚類中心趨同的情況，但是由于模糊概念的引入，出現(xiàn)了新的問題.首先，F(xiàn)CM建模方法中存在同一樣本點(diǎn)對(duì)各個(gè)聚類中心的隸屬度之和為1的約束條件，這表明離群點(diǎn)及噪聲的作用必然存在；在該條件的作用之下，聚類結(jié)果無法擺脫噪聲和離群點(diǎn)對(duì)聚類質(zhì)量的影響.其次，隨著樣本點(diǎn)同整體數(shù)據(jù)簇的偏差程度的增加，模糊隸屬度具有拖尾和翹尾的特性，即本該被舍棄的異常點(diǎn)或離群點(diǎn)反而陷入了極度模糊的狀態(tài)；這使得數(shù)據(jù)簇的類內(nèi)聚程度降低，且混入了部分可分性特征，進(jìn)而也降低了數(shù)據(jù)簇間的可分性.針對(duì)上述兩個(gè)問題，大量基于FCM的模糊聚類算法被提出，主要圍繞以下3個(gè)方面展開.

考慮對(duì)噪聲和異常點(diǎn)的魯棒性：FCM對(duì)噪聲與異常點(diǎn)的高敏感特性，主要源于其同一樣本點(diǎn)對(duì)各聚類中心的隸屬度之和為1的約束條件的設(shè)置.于是Krishnapuram等[1]提出了PCM(possibilisticC-means)聚類模型，該模型將模糊聚類放在可能性理論的框架之下，考慮各個(gè)樣本的“各異性”及其與各聚類中心的內(nèi)在聯(lián)系，使得噪聲點(diǎn)和異常點(diǎn)對(duì)任意聚類中心的隸屬度有可能被降到最低.然而由于PCM沒有考慮數(shù)據(jù)簇之間的相互關(guān)系，其對(duì)初始參數(shù)的設(shè)置極其敏感，且易出現(xiàn)聚類中心趨同的情況，這顯然違背了模糊隸屬關(guān)系最初引入的意圖.Pal等[2]提出了一種將FCM與PCM相結(jié)合的FPCM(fuzzy-possibilisticC-means)模型，該模型不僅具有FCM不同數(shù)據(jù)簇間相互作用的特性，而且具有PCM降低噪聲異常值影響的優(yōu)良特征，因此具有較高質(zhì)量的聚類結(jié)果.但當(dāng)樣本量十分龐大時(shí)，由于FPCM全體樣本點(diǎn)對(duì)同一聚類中心可能性之和為1的條件設(shè)置，每個(gè)樣本點(diǎn)的作用將微乎其微，使得模型迭代難以收斂.為了解決這個(gè)問題，Pal等[3]又提出了PFCM(possibilistic-fuzzyC-means)模型，該模型的改進(jìn)之處在于進(jìn)一步明確了聚類數(shù)據(jù)簇的模糊模型，均衡考慮了各樣本點(diǎn)的隸屬度以及可能性，放松了可能性之和約束為1的條件.但同時(shí)該模型引入了需要用戶設(shè)置的超參數(shù)，使得模型變得復(fù)雜且不具有自適應(yīng)特征.

考慮數(shù)據(jù)簇的內(nèi)聚程度與可分性：FCM過多地考慮數(shù)據(jù)簇內(nèi)聚程度，而將部分判別信息納入其中，反而使得類內(nèi)聚程度下降，簇間可分性降低，具體表現(xiàn)為可見FCM的翹尾特性.例如在數(shù)據(jù)集中存在著一些離群點(diǎn)，而在不去除該異常樣本點(diǎn)的情況下，按照距離劃分的策略，應(yīng)該將其歸屬于較近的一類數(shù)據(jù)簇.然而FCM作用下的離群樣本的隸屬度會(huì)陷入“極端模糊狀態(tài)”，這使得兩類數(shù)據(jù)簇的內(nèi)聚程度以及可分性下降.因此對(duì)于該類離群值的挖掘至關(guān)重要，有效地判別離群樣本，考慮樣本間的“各異性”，可以獲得更高質(zhì)量的聚類結(jié)果.

部分學(xué)者在該角度上對(duì)聚類算法進(jìn)行了研究，提出了將局部領(lǐng)域空間信息引入聚類模型的新想法.這類算法可減少離群點(diǎn)對(duì)聚類結(jié)果的負(fù)面影響,提高諸如圖像處理的質(zhì)量.例如：Ozdemir等[4]提出ICS(inter-cluster separation)模型，在FCM的目標(biāo)函數(shù)中添加由聚類數(shù)據(jù)簇中心所確定的類間可分性；Veenman等[5]在兩個(gè)相鄰數(shù)據(jù)簇相互配合的基礎(chǔ)上，對(duì)數(shù)據(jù)簇方差進(jìn)行硬約束，從而使聚類結(jié)果的劃分更加清晰；Cheng等[6]通過統(tǒng)計(jì)不同數(shù)據(jù)簇聚類中心的希爾伯特-施密特獨(dú)立性來描述不同數(shù)據(jù)簇之間的可分性.受到簇間可分性研究的啟發(fā)，Deng等[7]和Forghani[8]將類間可分性信息引入到模糊軟子空間聚類模型中；Wu等[9]在PCM的基礎(chǔ)上引入類間可分性，以避免不同的數(shù)據(jù)簇聚類中心趨于一致.

隨著最小絕對(duì)值收斂和選擇算子(least absolute shrinkage and selection operator，LASSO)、套索算法和正則化技術(shù)的發(fā)展和廣泛應(yīng)用，眾多學(xué)者把正則化技術(shù)引入到FCM中，通過對(duì)模糊隸屬度的正則化約束提高FCM對(duì)噪聲和異常樣本點(diǎn)的魯棒性.例如：Xenaki等[10]在PCM框架下對(duì)隸屬度進(jìn)行了稀疏性處理，提出了稀疏正則化的可能性聚類方法SPCM(saprse PCM)，通過對(duì)隸屬度矩陣施加稀疏性，從而有效剔除了噪聲和異常樣本點(diǎn)的影響.Zarinbal等[11]在FCM框架下提出REFCM(relative entropy FCM)，采用相對(duì)熵正則化技術(shù)，降低噪聲和異常樣本點(diǎn)的影響.Zhu等[12]提出了一種改進(jìn)的模糊劃分廣義FCM聚類方法GIFP-FCM(generalized FCM clustering algorithm with improved fuzzy partitions)，該方法能夠較好地分割帶紋理的噪聲圖像.Zhang等[13]基于松弛法，提出了偏差-稀疏FCM(deviation-sparse FCM,DSFCM)，通過對(duì)偏差施加稀疏性,DSFCM對(duì)噪聲和異常樣本體現(xiàn)出較好的識(shí)別和處理能力.

本文結(jié)合以上3個(gè)方面的想法，提出了一種新的聚類算法，利用正則化技術(shù)與軟閾值方法獲得稀疏性結(jié)構(gòu)特征，以此提高模型對(duì)噪聲的魯棒性，同時(shí)引入了虛擬類，挖掘離群點(diǎn)，把握數(shù)據(jù)樣本的“各異性”，從而獲取更高質(zhì)量的聚類結(jié)果.

1 相關(guān)工作

1.1 FCM聚類

FCM算法的標(biāo)準(zhǔn)化目標(biāo)函數(shù)與其約束條件如下所示：

(1)

按照FCM的算法思想，其算法步驟可歸納如下：

對(duì)于給定的樣本數(shù)據(jù)集X、數(shù)據(jù)簇個(gè)數(shù)c、最大誤差閾值ε、最大迭代次數(shù)n，返回隸屬度矩陣U以及聚類中心矩陣V.

1) 初始化隸屬度矩陣U(0)以及聚類中心V(0)，迭代次數(shù)為t=1.

4) 當(dāng)‖U(t+1)-U(t)‖<ε或者達(dá)到迭代最大次數(shù)停止，輸出隸屬度矩陣U和聚類中心矩陣V；否則返回第2)步，迭代次數(shù)t=t+1繼續(xù)迭代.

由于FCM存在硬性約束條件，即同一樣本點(diǎn)對(duì)各聚類中心的隸屬度之和為1，F(xiàn)CM對(duì)噪聲與離群點(diǎn)特別敏感，容易在該部分陷入極度“模糊”的狀態(tài).其過于關(guān)注樣本點(diǎn)的內(nèi)在聯(lián)系，而忽略了樣本的“各異性”，對(duì)噪聲的魯棒性較差，尤其不適合進(jìn)行離群值的挖掘，容易得到質(zhì)量較低的聚類結(jié)果.除此之外，F(xiàn)CM還存在著極易陷入局部最優(yōu)解的缺陷以及傾向于均分?jǐn)?shù)據(jù)簇的問題.

1.2 PCM聚類

PCM的標(biāo)準(zhǔn)化目標(biāo)函數(shù)及約束條件如下所示：

(2)

其中λi為懲罰系數(shù).通過分析可知，PCM在FCM的基礎(chǔ)上，引入了松弛項(xiàng)，放松了對(duì)隸屬度之和為1的約束條件，以達(dá)到改善FCM存在的對(duì)噪聲以及離群點(diǎn)敏感的問題.

根據(jù)PCM算法的思想機(jī)制，其算法步驟可歸納如下：

對(duì)于給定的樣本數(shù)據(jù)集X、數(shù)據(jù)簇個(gè)數(shù)c、最大誤差閾值ε、最大迭代次數(shù)n，返回隸屬度矩陣U以及聚類中心矩陣V.

將FCM返回的隸屬度矩陣U以及聚類中心V作為初始化結(jié)果，并且以此計(jì)算懲罰因子作為初始值，迭代次數(shù)為t=1.

4) 當(dāng)‖U(t+1)-U(t)‖<ε或者達(dá)到迭代最大次數(shù)停止，輸出隸屬度矩陣U和聚類中心矩陣V；否則返回第1)步，迭代次數(shù)t=t+1繼續(xù)迭代.

PCM雖然解決了FCM的部分缺陷問題，但由于其模型的構(gòu)建方式，PCM同樣存在問題.從隸屬度迭代公式中可以觀察到：當(dāng)懲罰因子很大時(shí)，隸屬度uij將會(huì)趨近于1；當(dāng)懲罰因子很小時(shí)，隸屬度uij將會(huì)趨近于0.這正是PCM能有效地改善噪聲問題的關(guān)鍵所在.但這同樣表明模型具有特別高的靈敏度，非常依賴參數(shù)的設(shè)置以及聚類中心的初始化，使得迭代過程非常容易陷入聚類中心重合的困境，而這顯然是很不利于尋找最優(yōu)解的.

1.3 PFCM聚類

PFCM是FCM與PCM的結(jié)合模型，其標(biāo)準(zhǔn)化目標(biāo)函數(shù)及約束條件如下所示：

(3)

PFCM在FCM的基礎(chǔ)上引入了概率權(quán)重tij，同時(shí)參照PCM的做法，對(duì)tij的約束進(jìn)行放松，這樣能避免FPCM由于樣本容量過大而導(dǎo)致的概率權(quán)重變得非常小時(shí)產(chǎn)生的計(jì)算誤差.

根據(jù)PFCM的算法思想機(jī)制，其算法計(jì)算步驟可歸納如下：

對(duì)于給定的樣本數(shù)據(jù)集X、數(shù)據(jù)簇個(gè)數(shù)c、最大誤差閾值ε、最大迭代次數(shù)n，設(shè)定參數(shù)a和b，將FCM返回的隸屬度矩陣U以及聚類中心V作為初始化結(jié)果，取概率權(quán)重矩陣T等于隸屬度矩陣U為初始值，并且計(jì)算懲罰因子，此時(shí)迭代次數(shù)為t=1.

5) 當(dāng)‖U(t+1)-U(t)‖<ε或者達(dá)到迭代最大次數(shù)停止，輸出隸屬度矩陣U和聚類中心矩陣V；否則返回第1)步，迭代次數(shù)t=t+1繼續(xù)迭代.

雖然PFCM在一定程度上克服了FCM以及PCM所存在的問題缺陷，但是從其模型設(shè)置以及計(jì)算公式的推導(dǎo)中可見，該模型依賴于多個(gè)參數(shù)設(shè)置，不具有較強(qiáng)的自適應(yīng)特性.

2 適應(yīng)稀疏模糊(ASFCM)聚類模型

2.1 ASFCM

在此，本文提出一種新的模型：

(4)

上述模型中,β是權(quán)重系數(shù)，λj是第j個(gè)樣本點(diǎn)隸屬于虛擬數(shù)據(jù)簇的可能性權(quán)重，該權(quán)重的取值設(shè)置方式將在后文詳細(xì)說明.其余符號(hào)的含義與FCM模型的相同.

由前文可知，F(xiàn)CM模型的提出雖大大改善了C均值的趨同性等缺陷，但又暴露出新的問題.其中，模糊概念的引入導(dǎo)致離群點(diǎn)陷入過于模糊的狀態(tài)，即隸屬度呈現(xiàn)翹尾狀態(tài)，這一問題亟待解決；同時(shí)其隸屬度之和為1的約束，使得算法對(duì)噪聲和離群值更加敏感.

針對(duì)上述兩大問題，本文在FCM模型的基礎(chǔ)上，再次引入C均值模型來達(dá)到有效抑制FCM的翹尾特性的目的.除此之外，模型(4)中引入了一個(gè)虛擬的噪聲數(shù)據(jù)簇，算法會(huì)將自動(dòng)判別出的噪聲劃分到該虛擬數(shù)據(jù)簇中，以此挖掘離群值的信息，并降低離群點(diǎn)對(duì)聚類結(jié)果的影響.

綜合來看，模型的后兩項(xiàng)作為正則化項(xiàng)，使得模型具有稀疏結(jié)構(gòu)特征.

ASFCM沒有把所有數(shù)據(jù)樣本放在同等地位，不會(huì)因?yàn)檫^于關(guān)注所有數(shù)據(jù)的內(nèi)在聯(lián)系而忽略了樣本的差異，其將樣本劃分成有效樣本以及噪聲樣本兩大部分，即能夠很好地把握樣本數(shù)據(jù)的“各異性”.

2.2 隸屬度取值稀疏性

參考Zhang等[14]獲取具有稀疏特征的相似度矩陣的優(yōu)化步驟，可以利用拉格朗日乘子法進(jìn)行求解，并獲得如下表達(dá)式：

(5)

其中η,γ≥0,均為拉格朗日乘子.根據(jù)KKT(Karush-Kuhn-Tucker)條件，可以獲得如下信息：

(6)

這里采用軟閾值方法進(jìn)一步分情況討論，可得：

(7)

根據(jù)上述情況綜合討論可得:

(8)

式(8)表明，該隸屬度取值符合軟閾值方法特征，具有稀疏特性.同時(shí)容易看出，隸屬度取值的稀疏性可以有效地挖掘出離群點(diǎn)信息，將離群點(diǎn)劃分至引入的虛擬噪聲數(shù)據(jù)簇，從而有效地排除此類異常值對(duì)聚類結(jié)果的影響，能夠在一定程度上提高數(shù)據(jù)簇的類內(nèi)聚程度以及數(shù)據(jù)簇之間的判別特性.

2.3 模型求解分析

為了便于模型的求解，對(duì)式(8)中λj進(jìn)行設(shè)置：λj=δ-η，其中δ為可設(shè)置的參數(shù)，稱δ為魯棒距離閾值.于是進(jìn)一步獲得隸屬度的表達(dá)式如下：

(9)

對(duì)于被引入的虛擬噪聲數(shù)據(jù)簇，取值為

(10)

由隸屬度表達(dá)式可看出，δ的取值小于樣本點(diǎn)到任一聚類中心距離時(shí)，虛擬數(shù)據(jù)簇的隸屬度恒為1.選取合適的魯棒距離閾值，可以極大程度排除噪聲的影響，這表示ASFCM對(duì)噪聲具有較好的魯棒性.在合理設(shè)置魯棒距離閾值的基礎(chǔ)上，ASFCM所獲得的隸屬度可根據(jù)實(shí)際實(shí)驗(yàn)數(shù)據(jù)的分布特點(diǎn)，以及其具體樣本與聚類中心的距離進(jìn)行自主調(diào)整，自動(dòng)且高效地判別噪聲.基于這一性能表現(xiàn)，該算法具有自適應(yīng)特性.

為了獲取聚類中心的迭代公式，再次利用拉格朗日乘子法進(jìn)行求解.對(duì)式(5)中的vi進(jìn)行求導(dǎo)后整理可得：

(11)

進(jìn)一步整理可以得到聚類中心的表達(dá)公式：

(12)

根據(jù)上述模型求解結(jié)果，可歸納ASFCM的算法流程如下：

對(duì)于給定的樣本數(shù)據(jù)集X、數(shù)據(jù)簇個(gè)數(shù)c、最大誤差閾值ε、最大迭代次數(shù)n，設(shè)定可調(diào)參數(shù)δ，返回隸屬度矩陣U以及聚類中心矩陣V.

1) 初始化隸屬度矩陣U(0)以及聚類中心V(0)，迭代次數(shù)為t=1.

2) 根據(jù)式(9)對(duì)uij，根據(jù)式(10)對(duì)u(c+1)j進(jìn)行迭代更新.

3) 根據(jù)公式(12)對(duì)進(jìn)行迭vi代更新.

4) 當(dāng)‖U(t+1)-U(t)‖<ε或者達(dá)到迭代最大次數(shù)停止，輸出隸屬度矩陣U、聚類中心矩陣V；否則返回第2)步，迭代次數(shù)t=t+1繼續(xù)迭代.

接下來進(jìn)行對(duì)比實(shí)驗(yàn)驗(yàn)證ASFCM的性能.

3 實(shí)驗(yàn)部分

在接下來的實(shí)驗(yàn)中，魯棒閾值距離的參數(shù)設(shè)置將根據(jù)具體實(shí)驗(yàn)數(shù)據(jù)的離散程度(如方差)進(jìn)行初步設(shè)置，并根據(jù)效果進(jìn)行參數(shù)微調(diào).在合理的設(shè)置范圍內(nèi)，δ越大則去噪能力越弱，δ越小則噪聲能力越強(qiáng).

3.1 隸屬度曲線實(shí)驗(yàn)

正如前文所述，F(xiàn)CM對(duì)離群值極度敏感，這種特點(diǎn)的具體表現(xiàn)是，該算法無法排除離群值的影響，而離群值的隸屬度會(huì)陷入過度模糊，進(jìn)而導(dǎo)致錯(cuò)誤劃分的情況.

為了能夠直觀地展現(xiàn)FCM的翹尾特性，說明本文所提出的模型ASFCM能有效克服這種缺陷，在本實(shí)驗(yàn)中，隨機(jī)生成了兩個(gè)一維數(shù)據(jù)簇，并在數(shù)據(jù)簇周圍疊加了10%的離群數(shù)據(jù)點(diǎn)，再存儲(chǔ)為一維數(shù)組，有效樣本數(shù)據(jù)與噪聲數(shù)據(jù)共有22 000個(gè).先將樣本按大小進(jìn)行排序后，分別利用FCM算法以及本文的新算法ASFCM計(jì)算隸屬度，并將隸屬度曲線繪制在圖像上，結(jié)果如圖1所示.圖中的虛線是FCM計(jì)算下其中一個(gè)數(shù)據(jù)簇的隸屬度曲線，該曲線在兩端呈現(xiàn)趨向于0.5的狀態(tài)，而在模糊的概念中，0.5的隸屬度代表的是完全模糊，這顯然不利于聚類的進(jìn)行，即FCM存在的翹尾問題；而圖中的實(shí)線是ASFCM聚類結(jié)果的同一數(shù)據(jù)簇的隸屬度曲線，可以明顯地看到，對(duì)于離群噪聲數(shù)據(jù)，ASFCM能夠完全排除其影響，即這類噪聲對(duì)任意數(shù)據(jù)簇隸屬度皆為0，這顯然符合我們對(duì)聚類結(jié)果的理想預(yù)期.

圖1 FCM與ASFCM的隸屬度曲線對(duì)比Fig.1 Membership curve comparison of FCM and ASFCM algorithms

圖2所示為經(jīng)過ASFCM的處理后，一個(gè)有效樣本數(shù)據(jù)簇和引入的虛擬數(shù)據(jù)簇對(duì)所有樣本點(diǎn)的隸屬度曲線.可以看到，ASFCM可以自動(dòng)判別出離群數(shù)據(jù)點(diǎn)，并將其劃分至虛擬噪聲數(shù)據(jù)簇中，也就是代表有效樣本數(shù)據(jù)簇的虛線兩端的截?cái)?，以及代表虛擬噪聲數(shù)據(jù)簇的實(shí)線兩端逼近于1.0的曲線走向.ASFCM通過有效樣本及噪聲的有效劃分達(dá)到了降低離群值對(duì)聚類結(jié)果影響的目的.

圖2 ASFCM對(duì)有效樣本數(shù)據(jù)簇及虛擬噪聲數(shù)據(jù)簇的劃分結(jié)果Fig.2 Division results of ASFCM algorithm on data cluster and noise cluster

3.2 隸屬度等高線圖

為了能夠進(jìn)一步清晰地展示ASFCM對(duì)離群值的有效挖掘以及稀疏特性，本文中生成一組人造數(shù)據(jù)集，其由兩個(gè)量級(jí)一致的數(shù)據(jù)簇以及疊加的部分離群噪聲構(gòu)成.

根據(jù)這組人造數(shù)據(jù)集，制作了FCM與ASFCM聚類結(jié)果的隸屬度等高線分布圖像(圖3)，其等高線值取自樣本對(duì)各實(shí)際數(shù)據(jù)簇的隸屬度的最大值.

圖3 FCM(a)和ASFCM(b)隸屬度的等高線圖Fig.3 The contour map of FCM (a) and ASFCM (b) membership degree

而ASFCM有著非常明顯的稀疏結(jié)構(gòu)特征，可以高效地去除離群噪聲點(diǎn)的影響.對(duì)任意實(shí)際數(shù)據(jù)簇，ASFCM所計(jì)算出的噪聲的隸屬度都非常低(除了與有效數(shù)據(jù)重疊的噪聲)，即幾乎所有的噪聲都被識(shí)別并被劃分到引入的虛擬噪聲數(shù)據(jù)簇中.這樣的劃分方式大大降低了離群值對(duì)聚類質(zhì)量的影響，使得數(shù)據(jù)簇類內(nèi)聚程度更高.

3.3 魯棒性實(shí)驗(yàn)

本實(shí)驗(yàn)是利用兩個(gè)等距離離群噪聲來展示其對(duì)隸屬度計(jì)算的影響(圖4)，以此對(duì)比FCM、PCM、PFCM、GIFP-FCM、REPCM、ASFCM 6種算法對(duì)噪聲的魯棒特性(圖5).

圖4 兩個(gè)有效樣本數(shù)據(jù)簇和兩個(gè)噪聲Fig.4 Two data clusters and two noise samples

圖5 6種算法的隸屬度曲線Fig.5 Membership curves of six algorithms

分析圖5可以得知，對(duì)于此類等距噪聲，F(xiàn)CM雖正確地劃分了樣本標(biāo)簽，但兩個(gè)噪聲點(diǎn)的隸屬度卻是0.5，這表明隸屬度中不存在任何判別信息，這兩個(gè)噪聲會(huì)被隨機(jī)劃分至任意數(shù)據(jù)簇中.而PCM與PFCM，雖都將兩個(gè)噪聲點(diǎn)的影響幾乎降至0，但其隸屬度曲線并非很完美，而且極度依賴初始參數(shù)的設(shè)置.GIFP-FCM雖然做到有效樣本不模糊，即判別信息十分明確，但是它卻完全無視噪聲點(diǎn)的影響，直接將其劃分至一類有效樣本數(shù)據(jù)簇中，導(dǎo)致隸屬度曲線的判別分界線出現(xiàn)明顯的偏移.REFCM雖然在一定程度上降低了兩個(gè)噪聲的影響，但是極易出現(xiàn)聚類中心重合的情況，且曲線走勢(shì)仍存在改進(jìn)的空間.最后，我們的ASFCM計(jì)算出的結(jié)果，不僅把兩個(gè)噪聲點(diǎn)的影響完全排除，而且可將兩個(gè)數(shù)據(jù)簇完全劃分開來，可分性大大提高.

3.4 UCI數(shù)據(jù)集

UCI(University of California Irvine)數(shù)據(jù)集是一個(gè)常用的標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)集，其來源于實(shí)際的生活生產(chǎn)中，具有分布形式多樣、數(shù)據(jù)特征豐富的特點(diǎn).本實(shí)驗(yàn)引入9個(gè)UCI數(shù)據(jù)集對(duì)算法的有效性進(jìn)行驗(yàn)證，所使用的數(shù)據(jù)集特點(diǎn)如表1所示.

表1 UCI數(shù)據(jù)集特點(diǎn)Tab.1 The features of UCI datasets

為了評(píng)估不同的聚類算法，引入了蘭德指數(shù)、標(biāo)準(zhǔn)化互信息及2種不同的聚類有效度評(píng)估方法，共4種指標(biāo)進(jìn)行實(shí)驗(yàn)對(duì)比評(píng)估.

首先，對(duì)4種指標(biāo)進(jìn)行簡(jiǎn)單介紹.

蘭德指數(shù)RRI為常見的聚類評(píng)估指標(biāo)，其表達(dá)式如下所示：

(13)

其中:f00表示實(shí)際類別信息一致并且聚類判別結(jié)果一致的樣本個(gè)數(shù)，f11表示實(shí)際類別信息不同并且聚類判別結(jié)果不同的樣本個(gè)數(shù);N(N-1)/2表示樣本內(nèi)可組成的數(shù)據(jù)對(duì)個(gè)數(shù);RRI的取值為0到1，RRI的值越大，表明聚類效果越好，類內(nèi)純度越高.

標(biāo)準(zhǔn)化互信息利用信息熵來衡量聚類結(jié)果，其表達(dá)式如下：

NNMI=

(14)

其中:Nij表示既屬于集合i又屬于集合j的樣本數(shù)量;Ni表示屬于集合i的樣本數(shù)量;Nj表示屬于集合j的樣本數(shù)量;N表示全體樣本個(gè)數(shù).其取值為0～1，值越大表明聚類結(jié)果一致性越高，因而可以用來評(píng)價(jià)帶有標(biāo)簽信息的數(shù)據(jù)集.

基于歐式距離度量的聚類有效度EEVA是由類間分離度SSPT與類內(nèi)緊致度CCMP共同衡量所得.

(15)

(16)

(17)

其中：Ni表示屬于第i個(gè)聚類中心的樣本個(gè)數(shù)；其余符號(hào)同F(xiàn)CM的符號(hào)含義.EEVA的取值越大，表示類內(nèi)越緊致，類間分離程度越高，聚類效果越好.

為了避免單一的有效度評(píng)估方式造成的誤差，根據(jù)樸尚哲等[15]對(duì)模糊聚類算法評(píng)估指標(biāo)的整理論述，選取基于隸屬度的聚類有效度量指數(shù)進(jìn)行進(jìn)一步的評(píng)估，其由緊致度C與相似度S共同衡量，表達(dá)式如下：

(18)

(19)

(20)

其中，

(21)

Sij=min(uik,ujk),k=1,2,…,n.

(22)

符號(hào)含義同F(xiàn)CM的符號(hào)含義.該指標(biāo)越小，表明類內(nèi)聚程度越高，類間分離度越好，聚類質(zhì)量越高.

本實(shí)驗(yàn)利用UCI數(shù)據(jù)集中的9組數(shù)據(jù)進(jìn)行測(cè)試，對(duì)于每個(gè)數(shù)據(jù)、每個(gè)算法，進(jìn)行10次重復(fù)實(shí)驗(yàn)，并取聚類結(jié)果的平均值進(jìn)行記錄比較，記錄結(jié)果如表2所示.其中標(biāo)黑的是本文算法數(shù)據(jù)以及結(jié)果最優(yōu)的數(shù)據(jù),既標(biāo)有下劃線又標(biāo)黑的數(shù)據(jù)表示雖指標(biāo)最優(yōu)但聚類中心重合.

表3記錄了各算法的聚類有效度EEVA與VCS的平均值.雖然FCM算法表現(xiàn)出最高的EEVA指標(biāo)，但是該算法無法排除離群噪聲點(diǎn)的影響，因此盡管其聚類有效度EEVA最高，實(shí)際上聚類效果卻并非最佳.其余算法在一定程度上都排除了噪聲點(diǎn)的影響，雖然它們的聚類有效度EEVA都有下降趨勢(shì)，但是綜合表2以及VCS來看，聚類質(zhì)量有所提高，尤其是ASFCM，該算法在盡可能保證EEVA指標(biāo)較高的情況下，同時(shí)也較大幅度地降低了VCS指標(biāo).

聯(lián)合表2與表3的結(jié)果進(jìn)行具體分析.PCM與GIFP-FCM的聚類效果依賴參數(shù)的設(shè)置，盡管聚類結(jié)果多次出現(xiàn)高指標(biāo)的情況，但這兩種算法都出現(xiàn)了聚類中心趨同問題，直觀表現(xiàn)是表3中對(duì)應(yīng)的聚類有效度EEVA大幅度下降與VCS明顯增大.PFCM的聚類質(zhì)量相對(duì)較高，但對(duì)于它的多個(gè)超參數(shù)，無從獲得其設(shè)置方法，只能依靠經(jīng)驗(yàn)調(diào)試.而REFCM的參數(shù)靈敏度過高，微小的偏差會(huì)導(dǎo)致整個(gè)聚類結(jié)果質(zhì)量的迅速下降，平均聚類有效度偏低.

表2 UCI數(shù)據(jù)集實(shí)驗(yàn)結(jié)果Tab.2 Experimental results of UCI datasets %

表3 聚類有效度Tab.3 Validity indexes

可見利用UCI數(shù)據(jù)集的聚類分析所計(jì)算出的平均蘭德指數(shù)、平均標(biāo)準(zhǔn)化互信息以及聚類有效度來評(píng)估，ASFCM整體優(yōu)于FCM、PCM、PFCM、GIFP-FCM、REFCM 5種算法.

3.5 圖像分割

在本實(shí)驗(yàn)中，分別利用FCM、PCM、PFCM、GIFP-FCM、REFCM以及ASFCM 6種算法進(jìn)行圖像分割，為了展現(xiàn)ASFCM算法對(duì)離群噪聲的有效抑制，在每張彩色實(shí)驗(yàn)圖片上疊加了椒鹽噪聲，并將算法自動(dòng)判別出的劃分至虛擬數(shù)據(jù)類的噪聲點(diǎn)通過K最近鄰(K-nearest neighbor,KNN)分類算法設(shè)置新的標(biāo)簽.具體實(shí)現(xiàn)方式為：計(jì)算以該像素點(diǎn)為中心的窗口內(nèi)各相鄰像素點(diǎn)標(biāo)簽的數(shù)量，取數(shù)量最大的標(biāo)簽作為該噪聲點(diǎn)的標(biāo)簽，最后按照算法聚類出的新標(biāo)簽，同一數(shù)據(jù)簇中的樣本點(diǎn)取均值還原圖像.結(jié)果如圖6所示，可以看出：無論是FCM、PCM、 PFCM、GIFP-FCM或REFCM都無法去除疊加的椒鹽噪聲的影響，但是ASFCM能夠較大程度移除噪聲信息，還原出較高質(zhì)量的分割圖像.ASFCM分割出的圖像顏色區(qū)分度大，貼近原圖色彩，這表示聚類結(jié)果中數(shù)據(jù)簇類內(nèi)聚程度高，數(shù)據(jù)簇間可分性大.

圖6 6種算法下房子(a1～a8)、馬(b1～b8)、花(c1～c8)的圖像分割結(jié)果Fig.6 Image segmentation of house (a1-a8),horse (b1-b8) and flower (c1-c8) under six algorithm

4 結(jié) 論

本文提出了一種新的模糊聚類模型ASFCM，其在以下3個(gè)方面上提高了聚類質(zhì)量.

1) 引入了虛擬噪聲數(shù)據(jù)簇，避免噪聲對(duì)有效樣本計(jì)算的影響，提高了對(duì)噪聲的魯棒性.

2) 結(jié)合FCM與C均值，引入魯棒距離的概念，具有自適應(yīng)性，可以自動(dòng)判別并去除離群異常點(diǎn)，防止誤判，進(jìn)而突出類內(nèi)聚程度，形成可分性更好的數(shù)據(jù)簇.

3) 采用了正則化技術(shù)，使得模型具有稀疏結(jié)構(gòu)特征，降低了噪聲和異常樣本點(diǎn)的影響，同時(shí)也使得可靠樣本點(diǎn)不具有模糊性.

經(jīng)過實(shí)驗(yàn)驗(yàn)證，ASFCM不僅能夠有效地克服FCM的翹尾缺陷，還能有效地挖掘出離群值，大大提高聚類質(zhì)量，具有較好的性能.

但由于我們?nèi)鄙賹?duì)于不同數(shù)據(jù)集的先驗(yàn)知識(shí)，未來將在如何更好地設(shè)置魯棒距離閾值、找到高效的方法上做進(jìn)一步研究.