潘金艷 ,高 朋 ,高云龍 ,謝有為 ,熊?；?/p>

(1.集美大學(xué) 信息工程學(xué)院,福建 廈門 361021;2.集美大學(xué) 航海學(xué)院,福建 廈門 361021;3.廈門大學(xué) 航空航天學(xué)院,福建 廈門 361101)

1 引言

聚類分析是一種重要的無(wú)監(jiān)督學(xué)習(xí)方法,在模式識(shí) 別、機(jī)器學(xué) 習(xí)、數(shù)據(jù)挖 掘等領(lǐng) 域有著 廣泛的 應(yīng)用[1–3].其目的是在一組分布未知的數(shù)據(jù)中,按照某種相似程度,盡可能地將相同性質(zhì)的數(shù)據(jù)點(diǎn)歸為一類.根據(jù)數(shù)據(jù)的集聚規(guī)則,聚類算法可以分為4類:基于劃分、基于層次、基于密度和基于網(wǎng)格[4–5].其中基于劃分的聚類方法,因其直觀的幾何意義和良好的數(shù)學(xué)模型可描述性而一直受到廣泛關(guān)注,最具有代表性的基于劃分 的聚類方法就是模糊 C 均值聚類 (fuzzy Cmeans,FCM).但是傳統(tǒng)FCM聚類算法也存在許多缺陷,如:對(duì)噪聲點(diǎn)和孤立點(diǎn)敏感、對(duì)不平衡數(shù)據(jù)集敏感等.

針對(duì)FCM算法存在的這 些問題,近年來(lái),研究者們展開了廣泛的研究.有研究將FCM對(duì)噪聲點(diǎn)和孤立點(diǎn)敏感問題歸結(jié)為樣本點(diǎn)對(duì)各數(shù)據(jù)簇隸屬度之和為1這一約束條件,該約束條件下噪聲點(diǎn)也會(huì)獲得較高的隸屬度[6,9],繼而在下一步的迭代過(guò)程中對(duì)聚類結(jié)果造成影響.于是,Krishnapuram等提出了可能C均值聚類模型 (possibilistic C-means clustering,PCM)[7],該模型考慮各個(gè)樣本的“各異性”及其與聚類中心的內(nèi)在聯(lián)系,通過(guò)松弛樣本點(diǎn)到聚類中心的隸屬度來(lái)降低噪聲和異常樣本點(diǎn)的影響.然而PCM沒有考慮不同數(shù)據(jù)簇之間的相互作用,而且對(duì)初始聚類中心的設(shè)置極其敏感,易出現(xiàn)聚類中心趨同的情況.Pal等人提出了一種將FCM與PCM相結(jié)合 的模糊可能C均值聚 類模型(fuzzy possibilistic C-means clustering,FPCM)[8],該模型不僅考慮了不同數(shù)據(jù)簇之間的相互作用,而且利用了PCM能夠降低噪聲異常值影響的優(yōu)良特征,因此能夠得到較高質(zhì)量的聚類結(jié)果.但是,當(dāng)樣本量十分龐大時(shí),由于FPCM全體樣本點(diǎn)對(duì)同一聚類中心可能性之和為的約束條件使得每個(gè)樣本點(diǎn)的作用將微乎其微,模型難以收斂[9].為了解決這個(gè)問題,Pal等人又 提出了 可能模 糊C均值聚 類算法(possibilistic fuzzy C-means clustering,PFCM)[10],該模型的改進(jìn)之處在于均衡考慮了各樣本點(diǎn)的隸屬度以及可能性,放松了可能性之和為1的約束條件.但同時(shí)該模型引入了需要用戶設(shè)置的超參數(shù),使得模型變得復(fù)雜且不具有自適應(yīng)特征.相對(duì)熵模糊C均值聚類算 法 (relative entropy fuzzy C-means clustering,REFCM)[11]在FCM框架下,采用相對(duì)熵正則技術(shù),引入朗伯函數(shù)求解模型,松弛了樣本的隸屬度約束條件,降低噪聲和異常樣本點(diǎn)的影響,但算法同樣存在模型復(fù)雜和收斂性不好的問題.

FCM算法對(duì)非平衡數(shù)據(jù)集敏感的問題也引發(fā)了眾多研究,其中Noordam等人從數(shù)據(jù)統(tǒng)計(jì)角度出發(fā),提出了簇大小不敏感模糊 C 均值聚類算法 (cluster size insensitive fuzzy C-means clustering,csiFCM)[12],算法在聚類過(guò)程中確定數(shù)據(jù)簇大小的比值,來(lái)平衡大數(shù)據(jù)簇對(duì)小數(shù)據(jù)簇的影響.但是,由于csiFCM對(duì)數(shù)據(jù)簇初始化聚類中心位置和相鄰簇之間的距離都很敏感,于是Lin等人從數(shù)據(jù)簇完整度和純度的統(tǒng)計(jì)特征角度提出了基于完整性的簇大小不敏感模糊C均值聚類算 法 (size-insensitive integrity-based fuzzy C-means,siibFCM)[13]算法,很好的解決了csiFCM存在的問題,但是該算法對(duì)噪聲點(diǎn)和孤立點(diǎn)不魯棒,在處理含噪聲的數(shù)據(jù)集時(shí)準(zhǔn)確率會(huì)大大降低.

此外,本課題組在研究中發(fā)現(xiàn),FCM模糊隸屬度具有拖尾和翹尾的結(jié)構(gòu)特征,這一特征造成離群樣本的隸屬度會(huì)陷入“極端模糊”狀態(tài),這種狀態(tài)使得數(shù)據(jù)簇的內(nèi)聚程度以及可分性下降.因此針對(duì)這些問題,本文提 出了一 種新的 基于可 靠性的 魯棒模 糊聚類算法 (reliability-based of robust fuzzy flustering,RRFCM),通過(guò)分析樣本點(diǎn)的可靠性來(lái)降低噪聲點(diǎn)、孤立點(diǎn)和數(shù)據(jù)簇不平衡問題對(duì)聚類結(jié)果的影響,提高聚類的質(zhì)量.

2 相關(guān)算法分析

2.1 模糊C均值聚類算法(FCM)

自FCM[14]被提出以來(lái)就一直展現(xiàn)出強(qiáng)大的生命力,后人在其基礎(chǔ)上不斷提出各種各樣的衍生算法,來(lái)改進(jìn)其存在的缺點(diǎn).FCM基本思想是將包含n個(gè)樣本點(diǎn)的數(shù)據(jù)集X={x1,x2,···,xn},按照模糊的方法劃分到c個(gè)不同的數(shù)據(jù)簇,通過(guò)最小化簇內(nèi)加權(quán)誤差平方和得到目標(biāo)函數(shù)

對(duì)模型(1)通過(guò)拉格朗日乘子法求解,得到

其中:c為數(shù)據(jù)簇的個(gè)數(shù),n為數(shù)據(jù)點(diǎn)的個(gè)數(shù),m為模糊控制系數(shù)(m >1),uij表示第j個(gè)樣本點(diǎn)xj隸屬于第i類vi的程度,即隸屬度.則表示其 歐氏距離的平方.

2.2 模糊隸屬度的“拖尾與翹尾”結(jié)構(gòu)特征

在FCM算法中,模糊控制系數(shù)m的取值對(duì)聚類結(jié)果的影響很大.當(dāng)m過(guò)小時(shí),聚類的模糊程度將會(huì)減小,進(jìn)而導(dǎo)致數(shù)據(jù)簇之間的作用力減小;當(dāng)m=1時(shí),算法退化為k-means算法;而當(dāng)m過(guò)大時(shí),聚類的模糊程度增大,所有數(shù)據(jù)點(diǎn)趨向于分為一類[15–16].因此,m的取值通常為[1.1,2.5][14–15],一般取值為2[17].

圖1 m取值對(duì)隸屬度的影響Fig.1 The influence ofm value on membership degree

2.3 噪聲點(diǎn)、孤立點(diǎn)對(duì)聚類結(jié)果的影響

在無(wú)監(jiān)督學(xué)習(xí)中,因?yàn)槿鄙贁?shù)據(jù)整體結(jié)構(gòu)特征的先驗(yàn)知識(shí),通常根據(jù)樣本點(diǎn)與整體樣本的偏移程度來(lái)判斷其是否為噪聲點(diǎn),即:如果某一樣本點(diǎn)遠(yuǎn)離大部分樣本點(diǎn),且歐式距離相對(duì)較大時(shí),那么該點(diǎn)為噪聲的可能性就會(huì)變得很大,反之,則不認(rèn)為是噪聲;但是,如果數(shù)據(jù)點(diǎn)周圍也存在較多近鄰樣本點(diǎn)時(shí),實(shí)驗(yàn)中將其視為噪聲點(diǎn)處理顯然會(huì)造成較大的誤差.

由式(1)(3)可知,由于模糊隸屬度和為1的約束,噪聲點(diǎn)的存在會(huì)使聚類中心發(fā)生偏移,具體表現(xiàn)為:將噪聲點(diǎn)歸為某一類,則該類的聚類中心會(huì)偏移向噪聲點(diǎn)方向.當(dāng)噪聲點(diǎn)距離數(shù)據(jù)簇較遠(yuǎn)時(shí),由于模糊隸屬度的拖尾與翹尾特征會(huì)造成本該被舍棄的離群點(diǎn),陷入了“極度模糊”的狀態(tài),從而造成該數(shù)據(jù)簇的類內(nèi)聚程度降低,同時(shí)也降低了數(shù)據(jù)簇間的可分性.下面通過(guò) 圖2來(lái)說(shuō)明 這種情 況,如 圖2(a)中有標(biāo)記為“o”和“*”的兩類數(shù)據(jù)簇,但是由于噪聲點(diǎn)的存在,FCM算法錯(cuò)誤的將噪聲點(diǎn)作為新的一類,而本該分開的兩個(gè)數(shù)據(jù)簇卻重疊在了一起,如圖2(b)這樣的聚類結(jié)果顯然不符合實(shí)際情況.

2.4 非平衡數(shù)據(jù)集聚類結(jié)果的影響

數(shù)據(jù)不平衡主要表現(xiàn)在不同數(shù)據(jù)簇樣本容量或數(shù)據(jù)簇分布特征(方差)的差異上.以圖3二分類為例,選取正類的樣本數(shù)量遠(yuǎn)大于負(fù)類的樣本數(shù)量,且分布特征不一致.由于FCM天生趨向于將數(shù)據(jù)簇均等分,因此數(shù)據(jù)簇之間的分界線將明顯偏移向樣本容量和方差較大的數(shù)據(jù)簇.如圖3(b)所示,黑色實(shí)線為理論分界線,虛線為實(shí)際分界線.

圖2 噪聲對(duì)聚類結(jié)果的影響Fig.2 Influence of noise on clustering results

通過(guò)以上分析可知,如何確定哪些點(diǎn)為噪聲點(diǎn),并排除它們對(duì)聚類結(jié)果帶來(lái)的影響就顯得尤為重要.在目前眾 多對(duì)噪聲魯棒 性的FCM算 法中,如:PCM[7],FPCM[8],PFCM[10],REFCM[11]等 等,都是通 過(guò)描述樣本點(diǎn)與聚類中心的偏移程度,即假設(shè)的先驗(yàn)?zāi)Ｐ蛠?lái)辨識(shí)樣本點(diǎn)是否為噪聲點(diǎn).然而,根據(jù)式(3)可以看出聚類中心的計(jì)算也容易受到噪聲點(diǎn)的影響,聚類中心估計(jì)不準(zhǔn)確,會(huì)對(duì)噪聲的判別帶來(lái)誤導(dǎo).因此,這類算法的魯棒性對(duì)聚類中心的估計(jì)依賴性較強(qiáng).

圖3 數(shù)據(jù)集不平衡對(duì)聚類結(jié)果的影響Fig.3 Influence of data sets imbalance on clustering results

與 Fisher 線性判別分析(Fisher linear discriminant analysis,Fisher LDA)思想相似,好的聚類算法應(yīng)當(dāng)使得同一簇內(nèi)的對(duì)象彼此相似,不同簇間的對(duì)象相異.而目前對(duì)噪聲魯棒性強(qiáng)的FCM算法中,都過(guò)度強(qiáng)調(diào)同一簇內(nèi)對(duì)象的相似性,而忽略了不同簇間的相異性,無(wú)法同時(shí)實(shí)現(xiàn)類內(nèi)聚程度大,類間可分性強(qiáng)的組合最優(yōu)性.基于這個(gè)問題,本文提出了基于全局與局部的不確定性聚類模型.

3 改進(jìn)算法分析

3.1 基于全局不確定性的聚類模型

模糊不確定性是指樣本點(diǎn)類別 屬性的不確定性.在當(dāng)前聚類中心確定的條件下,一個(gè)樣本點(diǎn)距離不同數(shù)據(jù)簇交疊區(qū)域越遠(yuǎn),則該樣本點(diǎn)的類別不確定性越小,基于這一幾何意 義,本文中 把任意一個(gè)樣本 點(diǎn)xj的模糊不確定性建模為

其中n為不確定性因子.基于上述不確定性公式,聚類過(guò)程應(yīng)當(dāng)使得不確定性最小,即有

圖4是一個(gè)最簡(jiǎn)單的帶有噪聲的二分類的數(shù)據(jù)集.對(duì)于距離聚類中心較近的點(diǎn),如點(diǎn)C,它隸屬于某一類的隸屬度值會(huì)很大,即具有明確的類別特征;而對(duì)于距離數(shù)據(jù)簇較遠(yuǎn)的噪聲點(diǎn)和兩個(gè)數(shù)據(jù)簇交界處的數(shù)據(jù)點(diǎn),如點(diǎn)A和點(diǎn)B,表現(xiàn)在圖1中即為橫軸中間和兩端位置,由隸屬度可知它們的類別特征不明顯.根據(jù)式(4)可知,對(duì)于任意xj,模糊不確定性aj的取值與樣本點(diǎn)的類別屬性無(wú)關(guān),其值大小僅取決于樣本點(diǎn)xj與聚類中心vi的歐氏距離.因此 參數(shù)aj的引 入,進(jìn)一步的加強(qiáng)了類別特征不明顯樣本點(diǎn)的影響力,提高了數(shù)據(jù)簇間的可分性;另外對(duì)于具有明確類別特征樣本點(diǎn),式(5)的權(quán)重aj較小,相對(duì)削弱了噪聲點(diǎn)和邊緣點(diǎn)對(duì)聚類結(jié)果的影響,因此提高了算法的魯棒性.

圖4 帶有噪聲的二分類數(shù)據(jù)集Fig.4 Noisy binary data sets

3.2 基于局部不確定性的聚類模型

第3.1節(jié)在分析樣本點(diǎn)的不確定性過(guò)程中,依賴當(dāng)前FCM的聚類中心,對(duì)每一個(gè)數(shù)據(jù)點(diǎn)的aj進(jìn)行 分析,因此將其稱作基于全局不確定性的聚類模型.

相對(duì)于全局不確定性的聚類模型,此處基于FCM對(duì)數(shù)據(jù)的劃分,尋找數(shù)據(jù)點(diǎn)近鄰點(diǎn)信息,建立局部不確定性的聚類模型.通過(guò)局部不確定性聚類模型挖掘不同數(shù)據(jù)簇之間交疊區(qū)域樣本的不確定性,挖掘局部聚類結(jié)構(gòu)特征,從而在聚類過(guò)程中,突出不同數(shù)據(jù)簇交疊區(qū)域樣本的可分性.依據(jù)這一思路提出基于模糊理論建立局部不確定性的聚類為

3.3 基于可靠性的魯棒模糊聚類

將模型(5)–(6)與FCM相結(jié)合,建 立如下基于可靠性的魯棒模糊聚類算法為

其中:uij,vi,xj與FCM算法中符號(hào)代表的含義相同,λ為全局不確定性比例系數(shù),γ為局部不確定性比例系數(shù),aj代表數(shù)據(jù)點(diǎn)的模糊不確定性程度,n為不確定性模糊因子,表示數(shù)據(jù)點(diǎn)xj的K個(gè)近鄰中,與xj標(biāo)簽相同數(shù)據(jù)點(diǎn)的均值.很顯然,當(dāng)λ,γ的值為0的時(shí)候,算法退化為FCM.本文中的符號(hào)以及定義總結(jié)在表1中.

表1 模型中符號(hào)及其代表含義Table 1 Notations used in this paper

3.4 優(yōu)化過(guò)程

基于式(8),利用拉格朗日乘子法,建立帶有拉格朗日約束項(xiàng)的輔助函數(shù)

函數(shù)L對(duì)輔助參數(shù)βj求偏導(dǎo)數(shù)得到

函數(shù)L對(duì)隸屬度uij求偏導(dǎo)數(shù)得到

令式(11)為零,得到

將式(12)代入式(10)得到βj,并將βj代回式(12)得到

函數(shù)L對(duì)聚類中心vi求偏導(dǎo)數(shù)得

令式(14)為零,得到

4 實(shí)驗(yàn)分析

4.1 時(shí)間復(fù)雜度分析

表2中給出幾種不同算法的時(shí)間復(fù)雜度,其中,N表示數(shù)據(jù)點(diǎn)的個(gè)數(shù),c表示聚類簇的個(gè)數(shù),t表示迭代的次數(shù),w表示選取近鄰窗口的大小,q在FRFCM算法中表示灰階的個(gè)數(shù).

表2 不同算法時(shí)間復(fù)雜度Table 2 Time complexity of different algorithms

可以看 出 FCM[14],csiFCM[12]和 siibFCM[13]3種算法有較低的計(jì)算復(fù)雜度.而FRFCM (fast robust fuzzy C-means clustering)[18],FLICM (fuzzy local information C-means clustering)[19]和RRFCM3種算法均引入局部近鄰約束,FRFCM算法將基于像素點(diǎn)聚類的方式改 為基于 灰階聚 類,q的取值 為 [0,255](q ?N),因此相較其他聚類算法復(fù)雜度要小得多.雖然FRFCM算法也引入了近鄰約束,但僅在算法收斂后,只對(duì)隸屬度進(jìn)行一次隸屬度中值濾波,而FLICM和RRFCM算法的局部信息需要在每次迭代中更新,因此計(jì)算代價(jià)都很高,優(yōu)點(diǎn)就是相較于其他幾種方法,都能得到較好的聚類結(jié)果.

4.2 算法步驟

算法可以通過(guò)以下步驟迭代得到聚類結(jié)果.

步驟1確定m,c,λ,γ的取值,最大迭代次數(shù)iteration和目標(biāo)函數(shù)收斂閾值?,初始化迭代次數(shù)t=0;

步驟2初始化聚類中心vi;

步驟3第1次迭代時(shí),根據(jù)式(2)求隸屬度;若t>1,則根據(jù)式(13)更新隸屬度uij;

步驟4根據(jù)式(4)更新aj;

步驟5根據(jù)式(15)更新聚類中心vi;

步驟6若Jt?Jt+1<ε且t

步驟7根據(jù)隸屬度矩陣U得到聚類結(jié)果.

4.3 實(shí)驗(yàn)設(shè)置

分別在人造數(shù)據(jù)集、UCI數(shù)據(jù)集[20]進(jìn)行實(shí)驗(yàn),來(lái)驗(yàn)證算法對(duì)含噪聲數(shù)據(jù)集、不平衡數(shù)據(jù)集和真實(shí)數(shù)據(jù)集的魯棒性,并進(jìn)一步驗(yàn)證算法在圖像分割實(shí)驗(yàn)中的實(shí)用性.

實(shí)驗(yàn)環(huán)境:

PC:HUAWEI

CPU:1.60 GHz–1.80 GHz RAM:8 GB

應(yīng)用軟件:MATLAB R2019a

選取相關(guān)算法進(jìn)行對(duì)比,以驗(yàn)證本文算法的有效性,參考文獻(xiàn) [21–22],文中RRFCM及其對(duì)比算法的模糊控制系數(shù)m均取2,全局和局部模糊不確定系數(shù)λ,γ通過(guò)尋優(yōu)得到.

4.4 評(píng)價(jià)指標(biāo)

為了驗(yàn)證算法的好壞,人造數(shù)據(jù)集和UCI實(shí)驗(yàn)結(jié)果用蘭德指數(shù)(Rand index,RI)作為評(píng)判標(biāo)準(zhǔn):

蘭德指數(shù)是利用樣本點(diǎn)之間的關(guān)系來(lái)衡量聚類結(jié)果,其中:a是樣本點(diǎn)中原來(lái)屬于同一類,聚類后仍屬于同一類的數(shù)據(jù)對(duì)個(gè)數(shù);b表示原來(lái)不屬于同一類,聚類后仍然不屬于同一類的數(shù)據(jù)對(duì)個(gè)數(shù);n表示數(shù)據(jù)點(diǎn)的個(gè)數(shù),分母表示所有樣本點(diǎn)所組成的數(shù)據(jù)對(duì)總個(gè)數(shù).RI∈[0,1],RI的值越大,表示聚類效果越好.

4.5 人造數(shù)據(jù)集驗(yàn)證魯棒性和類大小不敏感性

4.5.1球形數(shù)據(jù)集

FCM算法對(duì)數(shù)據(jù)集的分布比較敏感,對(duì)于凸集或類球形數(shù)據(jù)集,往往有好的聚類結(jié)果.本文首先在球形分布數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn).其中包括兩個(gè)可分性較好的高斯分布的數(shù)據(jù)簇.此外,為了驗(yàn)證算法的魯棒性,在數(shù)據(jù)集中加入了3個(gè)高斯分布的噪聲點(diǎn).具體參數(shù)如表3所示.

表3 球形數(shù)據(jù)集及噪聲分布Table 3 Spherical data sets and noise distribution

實(shí)驗(yàn)中λ的取值為0.4,n的取值為2 (不確定因子),γ的取值為1e?6;因?yàn)樗惴▽?duì)初始值很敏感,這種不確定性會(huì)導(dǎo)致聚類結(jié)果出現(xiàn)較大的偏差,因此,本文對(duì)FCM和RRFCM兩種算法分別進(jìn) 行10次重復(fù)實(shí)驗(yàn),取RI的平均值作為實(shí)驗(yàn)最終結(jié)果,來(lái)減小誤差,得到實(shí)驗(yàn)結(jié)果如圖5所示.

圖5 RRFCM算法在球形數(shù)據(jù)集上的聚類分析Fig.5 Clustering analysis of RRFCM algorithm on spherical data sets

表2中兩個(gè)高斯分布的均值為理論的聚類中心,因此算法得到的vi偏移越小,則表示受噪聲的影響越小.在圖5(b)(c)中分別用“*”來(lái)表示理論聚類中心,“□”表示算法聚類結(jié)果.從圖5(b)可以看出FCM將3個(gè)噪聲點(diǎn)分給了第1類,由于噪聲點(diǎn)的“拉扯力”,因此,聚類中心向噪聲點(diǎn)的方向發(fā)生較大的偏移.FCM算法分別得到的聚類中心為(2.488,4.911)和(4.786,2.041),蘭德指數(shù)RI為60.82%.如圖5(c)所示為RRFCM算法的聚類結(jié)果,得到的 聚類中心為 (2.825,4.500) 和(4.714,2.043),蘭德指 數(shù)RI為63.40%.算法在對(duì)第2類的聚類中心幾乎沒有影響的情況下,使第1類的聚類中心更加靠近真實(shí)值,可以看出,算法在沒有降低精度的同時(shí),還對(duì)噪聲點(diǎn)表現(xiàn)出了良好的魯棒性.

學(xué)生黨支部作為高?；鶎狱h組織的重要組成部分，理應(yīng)是高校開展思想政治工作的戰(zhàn)斗堡壘，然而，目前理工科院系學(xué)生黨支部建設(shè)卻面臨著一些突出問題。從個(gè)人的角度來(lái)講，理工科學(xué)生對(duì)政治的淡漠和參與度較低，一定程度導(dǎo)致了入黨積極性不足；而“務(wù)實(shí)”的“功利主義”又導(dǎo)致部分入黨學(xué)生動(dòng)機(jī)不純，更看重入黨帶來(lái)的現(xiàn)實(shí)回報(bào)，而非黨組織所要求的政治意識(shí)和應(yīng)當(dāng)承擔(dān)的責(zé)任。此外，還有部分學(xué)生黨員黨性意識(shí)不高，對(duì)黨組織歸屬感不強(qiáng)，參與黨支部活動(dòng)積極性不高等。

4.5.2非球形數(shù)據(jù)集

FCM算法能很好地識(shí)別球形數(shù)據(jù)集,但對(duì)于非球形數(shù)據(jù)集的識(shí)別能力較差.為了驗(yàn)證RRFCM算法是否具有很好的泛化性能,設(shè)置如圖6所示兩個(gè)棒狀的高斯分布數(shù)據(jù)簇,方差均為,通過(guò)改變它們的中心距來(lái)判斷算法對(duì)數(shù)據(jù)簇形狀變 化的魯 棒性.如 圖6(a),當(dāng)兩個(gè) 棒狀數(shù) 據(jù)簇中 心距為2.8時(shí),由圖6(b)和圖6(c)可 見FCM和RRFCM算 法都可以很 好的正確分類;進(jìn)一步縮小中心距為2.4,如圖6(e)所示,FCM算法分界線發(fā)生了傾斜,更加傾向于將兩個(gè)數(shù)據(jù)簇分為上、下兩類來(lái)平衡數(shù)據(jù)簇形狀變化帶來(lái)的影響,這種現(xiàn)象在中心距縮小為2.2時(shí)更加明顯,如圖6(h)所示,FCM算法分界線幾乎變?yōu)樗椒较?聚類中心也由數(shù)據(jù)簇的中心位置偏移到中間空白位置,這樣的分類結(jié)果顯然是不理想的;而RRFCM算法在3種不同的中心距時(shí),均能正確地將數(shù)據(jù)集分為左右明顯分離的兩個(gè)簇(圖6(c)(f)(i)).實(shí)驗(yàn)結(jié)果說(shuō)明算 法不但 對(duì)噪聲具有魯棒性,而且不受數(shù)據(jù)簇的形狀變化帶來(lái)的影響,即對(duì)數(shù)據(jù)分布也有較好的魯棒性,當(dāng)數(shù)據(jù)集分布非類球形時(shí),仍然能得到較好的聚類結(jié)果.

圖6 RRFCM算法在非球形數(shù)據(jù)集上的聚類分析Fig.6 Clustering analysis of RRFCM algorithm on non-spherical data sets

4.5.3 非平衡數(shù)據(jù)集

上述魯棒性驗(yàn)證實(shí)驗(yàn)是在平衡數(shù)據(jù)集上進(jìn)行的,本節(jié)改變數(shù)據(jù)簇的樣本容量,來(lái)驗(yàn)證RRFCM算法對(duì)非平衡數(shù)據(jù)集的有效性.

選取兩個(gè)服從高斯分布的球形數(shù)據(jù)集,不平衡度設(shè)置為20 (正負(fù)類樣本容量的比值),數(shù)據(jù)簇具體參數(shù)如表4 所示.對(duì)比算法為 FCM[14],csiFCM[12]和 siib-FCM[13].結(jié)果如圖7所示,從隸屬度等高線可以看出FCM算法和csiFCM算法的聚類中心明顯偏向較大的數(shù)據(jù)簇,siibFCM雖然比較好的解決了聚類中心偏移的問題,但是依然存在少量錯(cuò)分點(diǎn).而RRFCM算法對(duì)數(shù)據(jù)集大小不敏感,能準(zhǔn)確地將兩個(gè)簇分開.

圖7 不同算法在非平衡數(shù)據(jù)集上的聚類效果Fig.7 Clustering effect of different algorithms on size imbalance data sets

表4 非平衡數(shù)據(jù)集分布Table 4 Size imbalance data sets distribution

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

UCI 數(shù)據(jù)庫(kù) 是加 州大 學(xué)歐文分 校 (University of California Irvine,UCI)提供的用于機(jī)器學(xué)習(xí)常用標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)集[20].本文選取了12個(gè)UCI數(shù)據(jù)集,來(lái)檢驗(yàn)RRFCM 算法在處理真實(shí)數(shù)據(jù)時(shí)的表現(xiàn).

實(shí)驗(yàn)選 取 FCM[14],PFCM[10],GIFP–FCM[23–24],csiFCM[12],siibFCM[13]和 RBI–FCM[25]作為對(duì)比算法.其中基于改進(jìn)模糊劃分的廣義模糊C均值聚類(generalized fuzzy C-means clustering algorithm with improved fuzzy partitions,GIFP–FCM) 算法是 Zhu 等人提出的,文章通過(guò)引入新的隸屬度約束,解決了基于改進(jìn)模糊劃分的模糊C均值聚類(improved fuzzy partitions for fuzzy regression models,IFP–FCM)[26]算 法模糊指數(shù)m的一般化問題,同時(shí)算法從Voronoi距離和競(jìng)爭(zhēng)學(xué)習(xí)的角度對(duì)其魯棒性和快速收斂性進(jìn)行了合理解釋;簇間可分的魯棒模糊C均值聚類(robust fuzzy C-means clustering algorithm integrating between cluster information,RBI–FCM)算法是Gao等人提出的,文章利用k-means算法對(duì)模糊隸屬度的稀疏特征,降低簇之間相互作用,提高了簇間可分性,另外算法的魯棒性,也有效降低了FCM 對(duì)數(shù)據(jù)簇分布差異性和抽樣不均衡的敏感性,得到理想的聚類結(jié)果.該組實(shí)驗(yàn)的評(píng)價(jià)指標(biāo)為蘭德指數(shù)RI,實(shí)驗(yàn)結(jié)果如表5所示,實(shí)驗(yàn)結(jié)果表明,RRFCM算法 在12個(gè)UCI數(shù)據(jù)集上均取 得最高的蘭德指數(shù),充分說(shuō)明RRFCM算法在真實(shí)數(shù)據(jù)上的實(shí)用性.

4.7 圖像分割

圖像分割是指將圖像分成若干互不重疊的子區(qū)域,使得同一個(gè)子區(qū)域內(nèi)的特征具有相似度高,不同子區(qū)域的屬性呈現(xiàn)較為明顯的差異,是圖像處理與機(jī)器視覺的基本方法之一[27],在圖像分析的預(yù)處理階段具有十分重要的作用[28],也是圖像后期分析的基礎(chǔ).

4.7.1人造合成圖像分割

首先在有噪聲的人造圖像上進(jìn)行實(shí)驗(yàn).

實(shí)驗(yàn)選 取 FCM[14],csiFCM[12],siibFCM[13],FLICM[18]和FRFCM[19]作為對(duì) 比算法.其 中,FLICM和FRFCM算法都是通過(guò)引入圖像近鄰信息來(lái)優(yōu)化算法,FLICM利用模糊局部(空間和灰度)相似性度量,來(lái)提高算法 對(duì)噪聲 的不敏 感性和 圖像細(xì) 節(jié)保留能力;FRFCM通過(guò)引入基于灰階聚類和隸屬度中值濾波器,使得算法不需要像FLICM那樣計(jì)算近鄰信息,因此大大降低了計(jì)算代價(jià),并且中值濾波還起到了對(duì)噪聲魯棒的作 用.實(shí)驗(yàn)選 取分割精度 SA (segmentation accuracy)作為圖像分割結(jié)果的評(píng)價(jià)指標(biāo)其中:c為類的個(gè)數(shù),Ai表示通過(guò)算法迭代后屬于第i類像素點(diǎn),Ci表示在原始圖像中屬于第i類的像素點(diǎn).顯然,當(dāng)圖像完美分割的時(shí)候,SA的值應(yīng)該無(wú)限接近于1.

表5 各算法在UCI數(shù)據(jù)集的RI指數(shù)(%)Table 5 RI index of each algorithm on UCI data sets (%)

第1張圖像大小為128×128,分為平衡的兩類數(shù)據(jù)集,左側(cè)區(qū)域灰度值為20,右側(cè)灰度值為140.為了驗(yàn)證算法魯棒性,依次加入均值為0,方差為0.05,0.15和0.3的高斯噪聲.從圖9可以看出,當(dāng)方差為0.05時(shí),5種對(duì)比算法都可以準(zhǔn)確分類,但只有FLICM和FRFCM兩種算法幾乎可以完全去除噪聲;當(dāng)方差為0.15和0.3時(shí),隨著噪聲方差的增大,前3 種算法雖然能準(zhǔn)確分類,但都變得模糊不清.FLICM算法仍能較好的去除噪聲,對(duì)比FRFCM右側(cè)區(qū)域則抑制噪聲較差,這種趨勢(shì)隨著噪聲方差的增大表現(xiàn)得更加明顯;而RRFCM則受高斯噪聲方差變化的影響較小,只有在方差為0.3時(shí)才會(huì)出現(xiàn)少量噪點(diǎn),RRFCM算法在準(zhǔn)確分類的同時(shí)也有效的去除了噪聲,表現(xiàn)出較好的魯棒性.

從圖8分割精度折線圖可以看出,隨著噪聲方差的增大,除了FLICM和RRFCM算法,其他算法的精度都有所下降,因此SA隨噪聲變化的折線圖更加直觀反映了算法對(duì)噪聲較好的魯棒性.

第2張圖片大小為512×512,分為不平衡的四類數(shù)據(jù)集,其中左上角小正方的灰度值為0,記為I;右上角矩形灰度值為85,記為II;右下角大正方灰度值為255,記為III;左 下角矩形灰度值為170,記為IV;和圖9 一樣依次加入均值和方差均相同的高斯噪聲.由圖10可以看出,無(wú)論噪聲方差多大,所有對(duì)比算法都不能將I和II分界很好的分出來(lái),并且III和IV的噪聲都無(wú)法去除;而本文算法,在當(dāng)噪聲方差為0.05和0.15時(shí),I和II都能正確分類,且IV的噪聲幾乎被完全的去除掉;當(dāng)噪聲方差為0.15時(shí),盡管III和IV被錯(cuò)分到一起,但是整體噪聲仍然得到較好的抑制.

圖8 高斯噪聲方差對(duì)SA的影響Fig.8 The influence of Gaussian noise variance on SA

相比于二分類圖像分割,各對(duì)比算法在數(shù)據(jù)不平衡時(shí)均出現(xiàn)錯(cuò)分的情況,并且對(duì)噪聲魯棒性也會(huì)變得很差.而RRFCM算法僅在噪聲方差較高時(shí)才會(huì)出現(xiàn)錯(cuò)分,并且在噪聲抑制上要優(yōu)于其他算法.從圖10的SA折線圖可以觀察到,在噪聲方差變大時(shí),只有FRFCM算法和RRFCM算法仍能保持較高的分割精度,但就分割正確性來(lái)說(shuō),顯然RRFCM算法要表現(xiàn)的更好.

圖9 人造二分類圖像分割Fig.9 Artificial binary image segmentation

圖10 高斯噪聲方差對(duì)SA的影響Fig.10 The influence of Gaussian noise variance on SA

4.7.2 彩色真實(shí)圖像分割

接下來(lái)選取Berkeley圖庫(kù)作為測(cè)試對(duì)象,選取的圖像為#238011,#15088和#135069.

從 圖12(b)(d)(e)(f)可以看 出,由于月 亮數(shù)據(jù)簇較小,因 此FCM,siibFCM,FLICM和FRFCM錯(cuò)誤的 將月亮與周圍天空錯(cuò)分為一類,導(dǎo)致分割結(jié)果中月亮和背景天空融合到一起,并且天空也不能完整分割.雖然 圖12(c)顯 示csiFCM算法將 月亮很好地分割出 來(lái),但是與邊緣天空錯(cuò)分為一類,而且仍然未解決劃分結(jié)果均衡這一問題,即并沒有解決對(duì)數(shù)據(jù)集大小敏感這一問題;而RRFCM算法在 正確分 類的前提下,如 圖12(g)準(zhǔn)確地將月亮分割出來(lái);圖13所示水中船只,為了得到圖片主體船,需要將水面和水波作為噪聲劃為一類.在對(duì)比算法中,只有FLICM和FRFCM算法可以較好的去除波紋,而其他算法雖然也能正確分類,使主體與背景分割開來(lái),但仍然存在少量水波無(wú)法去除.如圖13(g)所示,本文算法完全去掉了波紋,并得到清晰的湖船主體.

圖11 人造四分類圖像分割Fig.11 Artificial quad-classification image segmentation

圖12 各算法對(duì)Berkeley圖庫(kù)圖像分割結(jié)果Fig.12 Algorithms on Berkeley library image segmentation results

圖13 各算法對(duì)Berkeley圖庫(kù)圖像分割結(jié)果Fig.13 Algorithms on Berkeley library image segmentation results

圖14和圖15為算法在常用圖像分割數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果,選取的c值為2和3.實(shí)驗(yàn)選取的對(duì)比算法及參數(shù)與圖13和圖14實(shí)驗(yàn)均相同.

在這些 結(jié)果中 可以 看到,siibFCM和FLICM算 法在一些數(shù)據(jù)不均衡或分布不均勻的圖像取得較好的分割結(jié)果.而在部分?jǐn)?shù)據(jù)不均衡圖像上,siibFCM算法卻并不能很好的解決該問題.對(duì)于一些背景“純凈”,但分布不均勻的圖像,FLICM算法的分割結(jié)果也不是很理想.FRFCM相較于其他對(duì)比算法的優(yōu)點(diǎn)是計(jì)算速度快,但也僅在個(gè)別圖像上取得較好的分割結(jié)果.而RRFCM算法面對(duì)這些圖像存在問題,均可以得到較好的分割結(jié)果.

在 原圖中加入 均值 為0,方差為0.15的高斯噪 聲,如圖16所示.可見FCM,siibFCM和FRFCM算法僅能看清鷹的輪廓,而不能很好的抑制噪聲;csiFCM算法在加入高斯噪聲后,當(dāng)噪聲方差較低時(shí),聚類效果和FCM算法相差不大,隨著方差的增加,所有簇將會(huì)聚為一類,無(wú)法得到可觀測(cè)的聚類結(jié)果(為了方便觀察,圖16(c) 加入了熱圖),因此在 真實(shí)圖像分割 中,csi-FCM算法幾乎不具備魯棒性;FLICM優(yōu)于以上對(duì)比算法,對(duì)噪聲 具有一 定的抑 制作用,但相比 于RRFCM算法仍存在均衡分類的現(xiàn)象,結(jié)果如圖16(e)所示將一部分背景天空錯(cuò)分到主體鷹這一小數(shù)據(jù)簇上.為了便于觀察RRFCM算法的魯棒性,如圖16(g)所示加入未加噪聲的分類結(jié)果,對(duì)比圖16(h)可以看出,RRFCM算法在真實(shí)圖像分割中,在解決數(shù)據(jù)簇大小敏感問題的同時(shí),可以較好地抑制噪聲,結(jié)果優(yōu)于對(duì)比算法.

圖14 c=2圖像分割Fig.14 c=2 image segmentation

圖15 c=3圖像分割Fig.15 c=3 image segmentation

5 結(jié)束語(yǔ)

由實(shí)驗(yàn)結(jié)果可知,本文所提出的RRFCM算法,在保證模糊C均值聚類算法優(yōu)點(diǎn)的同時(shí),提高了算法的魯棒性,也有效解決了算法對(duì)數(shù)據(jù)大小敏感的問題,并在人造數(shù)據(jù)集、真實(shí)數(shù)據(jù)集和圖像分割上取得較好的結(jié)果.但算法也存在局限性,對(duì)初始聚類中心較為敏感,對(duì)初始化聚類中心位置依賴性較強(qiáng),并且由于要計(jì)算數(shù)據(jù)點(diǎn)近鄰約束信息,因此算法計(jì)算代價(jià)較高,今后將在解決該問題上進(jìn)行研究,就其初始化聚類中心不敏感性和算法實(shí)現(xiàn)快速性做出更為合理的分析與解釋.