半監(jiān)督空間化競(jìng)爭(zhēng)聚集算法及其在圖像分割中的應(yīng)用

于 平,王士同

(江南大學(xué)數(shù)字媒體學(xué)院,江蘇無(wú)錫214122)

半監(jiān)督空間化競(jìng)爭(zhēng)聚集算法及其在圖像分割中的應(yīng)用

于 平,王士同

(江南大學(xué)數(shù)字媒體學(xué)院,江蘇無(wú)錫214122)

經(jīng)典競(jìng)爭(zhēng)聚集(CA)算法在聚類(lèi)時(shí)對(duì)于樣本中的少量已知信息沒(méi)有加以利用,但這些信息往往需要應(yīng)用到整個(gè)聚類(lèi)過(guò)程中。此外,在相似度度量函數(shù)的選擇上CA算法使用常見(jiàn)的歐氏距離,然而歐氏距離僅適用于團(tuán)狀數(shù)據(jù),制約了算法的應(yīng)用范圍。針對(duì)上述問(wèn)題,通過(guò)引入具備半監(jiān)督學(xué)習(xí)能力的半監(jiān)督項(xiàng)對(duì)隸屬度矩陣進(jìn)行增強(qiáng),利用聚類(lèi)中心和中心鄰近的點(diǎn)組成空間,把樣本點(diǎn)與該空間的距離替代歐氏距離作為新的相似度度量標(biāo)準(zhǔn),并給出判斷聚類(lèi)中心能否合并的閾值參數(shù),最終得到半監(jiān)督空間化CA算法。通過(guò)在人造圖像和真實(shí)圖像上的分割結(jié)果表明,該算法能夠更準(zhǔn)確地獲取聚類(lèi)類(lèi)別數(shù)以及更好的聚類(lèi)效果。

競(jìng)爭(zhēng)聚集算法;相似度度量函數(shù);歐氏距離;半監(jiān)督;空間距離;閾值參數(shù)

1 概述

聚類(lèi)是模式分類(lèi)和系統(tǒng)建模的基本方法[1]。它根據(jù)樣本個(gè)體之間的相似性把樣本空間劃分為不同的子集。聚類(lèi)后的樣本,同一個(gè)子集空間中的個(gè)體具有盡可能大的相似度,而不同子集空間中的個(gè)體差別較大。

本文針對(duì)當(dāng)前競(jìng)爭(zhēng)聚集(Competitive Agglomeration,CA)算法存在的問(wèn)題,提出一種新的CA聚類(lèi)算法,稱(chēng)為半監(jiān)督空間化CA算法。該算法通過(guò)構(gòu)造半監(jiān)督學(xué)習(xí)項(xiàng)有效地對(duì)待聚類(lèi)的樣本數(shù)據(jù)通常存在的少量有益信息加以利用,從而增強(qiáng)聚類(lèi)效果。此外,為解決歐氏距離所造成的缺陷,提出利用聚類(lèi)中心和中心鄰近的點(diǎn)組成空間,把樣本點(diǎn)與該空間的距離替代歐氏距離作為新的相似度度量標(biāo)準(zhǔn),增強(qiáng)算法的適用性。所采用的空間距離由于考慮了數(shù)據(jù)的結(jié)構(gòu)和方向信息,其抗噪音性能更佳,提高了算法的抗噪能力。給出一種合適的判斷聚類(lèi)中心合并的閾值參數(shù),對(duì)最終聚類(lèi)個(gè)數(shù)進(jìn)行有效調(diào)控,為算法獲取更為精準(zhǔn)的類(lèi)別數(shù)提供保障。

2 背景介紹

目前常用的聚類(lèi)方法主要分為2大類(lèi)[2]:層次聚類(lèi)算法和目標(biāo)函數(shù)聚類(lèi)算法。經(jīng)分析這2類(lèi)算法各有優(yōu)缺點(diǎn),可總結(jié)如下:(1)層次聚類(lèi)算法是產(chǎn)生一個(gè)聚類(lèi)層級(jí)即聚類(lèi)樹(shù)的非單一聚類(lèi),主要通過(guò)合并和分裂2種方式來(lái)實(shí)現(xiàn)。該類(lèi)算法不受初始化和局部極小值對(duì)于聚類(lèi)結(jié)果的影響,不用提前設(shè)置聚類(lèi)得到的類(lèi)別總數(shù),且算法結(jié)構(gòu)較為明朗。但該類(lèi)算法不適用大的數(shù)據(jù)集,初始化階段某層出現(xiàn)的錯(cuò)誤將在合并和分裂過(guò)程中向下一層延續(xù),并最終影響全局的聚類(lèi)。(2)基于目標(biāo)函數(shù)的聚類(lèi)算法,這類(lèi)算法可以把握數(shù)據(jù)整體的結(jié)構(gòu)和形狀,它由具備類(lèi)別特征的原型來(lái)代表一個(gè)類(lèi)別,由特征矢量到類(lèi)別原型的距離和作為目標(biāo)函數(shù),通過(guò)迭代不斷減小目標(biāo)函數(shù),當(dāng)目標(biāo)函數(shù)取得極值時(shí)結(jié)束算法。該類(lèi)算法可以分為硬聚類(lèi)和軟聚類(lèi)2種[3]。2種算法的不同主要表現(xiàn)在對(duì)于隸屬度的取值方面。硬聚類(lèi)的隸屬度值為0或者1,軟聚類(lèi)的隸屬度值為一個(gè)模糊的區(qū)間[0,1]。軟聚類(lèi)由于其模糊性成為聚類(lèi)分析的主流,以文獻(xiàn)[4]提出、文獻(xiàn)[5]推廣的模糊C-均值聚類(lèi)(Fuzzy C Means clustering,FCM)最為經(jīng)典。該算法的動(dòng)態(tài)迭代使算法可以不斷更新數(shù)據(jù)對(duì)于類(lèi)別的隸屬關(guān)系,使算法的錯(cuò)誤不會(huì)固定延續(xù),但這同樣帶來(lái)了需要更大內(nèi)存存儲(chǔ)空間和更大計(jì)算量的問(wèn)題。且FCM算法執(zhí)行前需要預(yù)判和設(shè)定聚類(lèi)對(duì)象的類(lèi)別總數(shù)、初始化,這2項(xiàng)參數(shù)決定了最終的聚類(lèi)效果,即決定了算法能否得到最佳的聚類(lèi)類(lèi)別數(shù)目和目標(biāo)函數(shù)能否取得全局極值。這也是FCM算法及其他相似的迭代聚類(lèi)算法所面臨的共同問(wèn)題。

為解決上述問(wèn)題,文獻(xiàn)[3]提出了一種新穎的聚類(lèi)算法,即競(jìng)爭(zhēng)聚集(CA)算法。該算法采用層次聚類(lèi)的初始化方式,使算法不受初始化和局部極小值的影響,用目標(biāo)函數(shù)聚類(lèi)的特點(diǎn)來(lái)避免層次聚類(lèi)中的缺陷。此外,其更可以通過(guò)迭代的方式自動(dòng)尋找到待聚類(lèi)樣本數(shù)據(jù)集最佳的聚類(lèi)類(lèi)別數(shù)目,是一種無(wú)監(jiān)督的聚類(lèi)方法。盡管CA算法表現(xiàn)出了一些獨(dú)特的聚類(lèi)性能,并且在數(shù)據(jù)處理[3]、遙感衛(wèi)星圖像處理[6]和圖像分割[7]等領(lǐng)域得到了廣泛的應(yīng)用。但是,經(jīng)研究發(fā)現(xiàn),當(dāng)前的CA算法在聚類(lèi)時(shí)忽略了待聚類(lèi)樣本數(shù)據(jù)所包含的一些有益的已知信息,而這些有益信息往往能夠?qū)ψ罱K的聚類(lèi)結(jié)果起到正面作用。此外,經(jīng)典的CA算法在相似度度量函數(shù)的選擇上使用了最常見(jiàn)的歐氏距離,然而歐氏距離僅適用于團(tuán)狀數(shù)據(jù),制約了算法的應(yīng)用范圍。

3 CA算法

CA算法是在層次聚類(lèi)和目標(biāo)函數(shù)聚類(lèi)的基礎(chǔ)上提出的方法。它通常以遠(yuǎn)大于樣本類(lèi)別總數(shù)的小簇來(lái)初始化,然后在迭代過(guò)程中通過(guò)偏移項(xiàng)的作用,不斷增加真實(shí)聚類(lèi)中心的競(jìng)爭(zhēng)力,削弱虛假中心的影響,直至滿足算法的終止條件,從而得到合適的聚類(lèi)效果。

3.1 CA算法基本原理

設(shè)X={x1,x2,…,xN}是數(shù)據(jù)樣本空間,B=(v1,v2,…,vC)是數(shù)據(jù)集的聚類(lèi)中心集合,則CA算法的目標(biāo)函數(shù)可以表示為:

式(1)可以看作2個(gè)部分,第1部分與模糊指數(shù)m=2時(shí)的FCM目標(biāo)函數(shù)功能相似,用來(lái)確定聚類(lèi)簇的大小和形狀。第2部分是一個(gè)偏移項(xiàng),用來(lái)尋找最佳的聚類(lèi)類(lèi)別總數(shù)。

偏移項(xiàng)中參數(shù):

其中,k表示算法迭代的次數(shù);η0和τ是固定的取值。

文獻(xiàn)[3]中根據(jù)拉格朗日條件極值的求解方式給出了式(1)取得極值時(shí)參數(shù)矩陣U和B的值。

在式(2)的約束下,隸屬度的值為:

式(5)是式(1)中FCM部分的隸屬度更新,式(6)是偏移項(xiàng)部分的隸屬度更新。

式(6)中Ni表示第i類(lèi)的基數(shù);表示類(lèi)別基數(shù)的加權(quán)平均,更新公式如下:

同理得到的聚類(lèi)中心為:

根據(jù)求解得到的參數(shù)公式,只要給CA算法聚類(lèi)樣本,算法就可以通過(guò)迭代,得到最佳的劃分結(jié)果。

3.2 CA算法存在的問(wèn)題

CA算法通過(guò)迭代過(guò)程中不斷丟棄虛假中心的方式可以自動(dòng)得到最終的聚類(lèi)數(shù)目,在處理某些數(shù)據(jù)時(shí)存在其可取性,但從現(xiàn)實(shí)生活中的數(shù)據(jù)特點(diǎn)來(lái)考慮,CA算法在某些方面尚存在某些問(wèn)題。這可以分為2個(gè)方面:

(1)樣本信息利用率不高。實(shí)際生產(chǎn)和生活中的數(shù)據(jù),一般情況是建立在少數(shù)已知信息的基礎(chǔ)上的。無(wú)監(jiān)督的CA算法,極大地浪費(fèi)了這些稀少卻對(duì)數(shù)據(jù)聚類(lèi)十分有用的信息,這必將影響最終聚類(lèi)結(jié)果的恰當(dāng)程度。

(2)相似度度量標(biāo)準(zhǔn)并不可靠,CA算法的目標(biāo)函數(shù)使用歐氏距離作為相似度度量函數(shù)。歐氏距離雖然在計(jì)算上簡(jiǎn)單方便,但僅適用于團(tuán)狀的數(shù)據(jù)聚類(lèi),在處理其他結(jié)構(gòu)的聚類(lèi)時(shí)存在偏差,而且,將目標(biāo)函數(shù)最小化來(lái)得到最佳聚類(lèi)結(jié)果的方法存在對(duì)數(shù)據(jù)集進(jìn)行均等劃分的可能[8-9],此外,歐氏距離本身的抗噪能力也不令人滿意[10]。

以上問(wèn)題,制約了CA算法的適用性范圍。本文將提出一種新的改進(jìn)CA算法來(lái)解決上述問(wèn)題,增強(qiáng)算法的性能及適用性。

4 半監(jiān)督空間化CA算法

針對(duì)前一節(jié)CA算法所存在的問(wèn)題,本節(jié)提出一種新的改進(jìn)CA算法。該算法通過(guò)引入半監(jiān)督學(xué)習(xí)方法改進(jìn)了目標(biāo)函數(shù),此外為了增強(qiáng)適用性進(jìn)一步采用了空間化距離度量標(biāo)準(zhǔn)改進(jìn)原本的歐氏距離,最終得到了半監(jiān)督空間化CA算法。

4.1 半監(jiān)督方法

針對(duì)樣本信息利用率不高的問(wèn)題,本文通過(guò)對(duì)隸屬度引入已知信息的方式,使其充分利用少量但重要的信息,提高聚類(lèi)結(jié)果的正確率。解決方法如下[11]:

待聚類(lèi)的數(shù)據(jù)集可以寫(xiě)為已知和未知數(shù)據(jù)組成的形式:

4.2 空間距離的原理

針對(duì)3.2節(jié)中提到的歐氏距離僅適用于球狀聚類(lèi)且存在等劃分趨勢(shì)的缺陷,本文使用了將歐氏距離空間化[12]的方法進(jìn)行修正和改進(jìn)。

圖1中Mi代表樣本的所有可能聚類(lèi)中心所組成的平滑流形,Ni是距離待測(cè)樣本sq最近的聚類(lèi)中心i和中心i鄰近點(diǎn)的集合,xi1和xi2代表Ni中第i類(lèi)聚類(lèi)中心和第i類(lèi)中心鄰近的2個(gè)點(diǎn),Si是Ni限定的子空間平面,那么通過(guò)其他可能的聚類(lèi)中心和它們鄰近點(diǎn)的平滑流形也必然與Si相交[12]。當(dāng)Ni基數(shù)為2時(shí),xi1和xi2是距離sq最近的點(diǎn)。

圖1 空間距離原理推導(dǎo)

那么sq是距離子空間Si最近的點(diǎn),則距離為:

式(12)的距離在圖1中是一個(gè)通過(guò)原點(diǎn)的平面,考慮到逐個(gè)計(jì)算式(12)中歐氏距離的復(fù)雜性,可以直接把子空間Si看作一個(gè)整體來(lái)計(jì)算。

設(shè)Ni是xi的點(diǎn)組成的矩陣且滿足列滿秩條件,該平行體的體積[13]:

與式(13)類(lèi)似,若sq和Ni線性無(wú)關(guān),那么它們共同組成的超平形體的體積為:

根據(jù)上式,則式(12)的距離可以改寫(xiě)為:

圖2中“oabcdefg”表示xj和矩陣Vi所組成的平行六面體[12],體積是“og”與平行四邊形“oabc”的距離和該“oabc”面積的乘積,將“og”和“oabc”表示的量和空間分別用xj和Vi表示,那么根據(jù)式(15)“og”到“oabc”所組成的空間距離的平方可以表示為:

將式(16)應(yīng)用到聚類(lèi)算法中,其中,xj表示樣本中第j個(gè)點(diǎn);Vi是第i個(gè)中心點(diǎn)和中心鄰近點(diǎn)所組成的矩陣,那么dxj→i就可以表示xj到Vi組成的超平行體的距離。存在的條件是保證矩陣Vi的列向量線性無(wú)關(guān),為了滿足這個(gè)條件,將式(16)正則化[14]得:

圖2 空間距離推導(dǎo)

由于在式(16)中

觀察式(17),可以發(fā)現(xiàn)該式類(lèi)似于大量的核學(xué)習(xí)方式,同樣可以進(jìn)行核化得到核化后的距離標(biāo)準(zhǔn)。為了簡(jiǎn)潔,在本文中對(duì)于該部分將不再探討,主要采用式(17)作為距離函數(shù)。

4.3 鄰近中心點(diǎn)的判斷與合并部分

上一節(jié)介紹了CA算法空間化距離的原理及計(jì)算方式,由這些介紹可以看出在一定范圍的聚類(lèi)中心對(duì)于改進(jìn)后的CA算法距離差異并不大,但這些聚類(lèi)中心時(shí)常卻因?yàn)椴粷M足傳統(tǒng)CA的舍棄條件而被錯(cuò)誤地保存下來(lái)。針對(duì)這樣的狀況,根據(jù)參考文獻(xiàn)[15]的思想,加入新的判別方式來(lái)合并更新這些聚類(lèi)中心,以使算法達(dá)到迭代出合理聚類(lèi)總數(shù)的目的。

判斷合并原理如下:

式(18)是聚類(lèi)中心相似性的距離衡量方式;θ是合并聚類(lèi)中心的閾值,根據(jù)實(shí)驗(yàn)經(jīng)驗(yàn)在本文中取0.001;式(20)和式(21)分別為新聚類(lèi)中心和它對(duì)應(yīng)的隸屬度的計(jì)算方法。

考慮到聚類(lèi)中心集合內(nèi)有3個(gè)或多個(gè)元素同時(shí)滿足合并條件時(shí),同一類(lèi)的隸屬度將分別被合并多次的情況,本文對(duì)更新后的隸屬度重新按約束條件進(jìn)行修正。

該段程序執(zhí)行過(guò)程如下:

步驟1計(jì)算聚類(lèi)中心集合內(nèi)任意2個(gè)元素的距離。

步驟2將滿足dv≤θ的聚類(lèi)中心按照式(20)的方式合并為新的聚類(lèi)中心,按照式(21)計(jì)算對(duì)應(yīng)的新隸屬度。

步驟3按照約束條件修正更新后的隸屬度矩陣,更新聚類(lèi)數(shù)目。

4.4 半監(jiān)督空間化CA算法

根據(jù)前3節(jié)的介紹,下面給出本文所提半監(jiān)督空間化CA算法的具體目標(biāo)函數(shù)如下:

4.4.1 目標(biāo)函數(shù)迭代參數(shù)的推導(dǎo)

為了得到最優(yōu)的聚類(lèi)結(jié)果,下面介紹所需迭代參數(shù)的相關(guān)推導(dǎo)。

(1)求解隸屬度的更新公式:

根據(jù)拉格朗日極值求解方式,可將式(22)寫(xiě)作如下的優(yōu)化函數(shù)形式:

1)對(duì)uij求偏導(dǎo)和定義Ni:

則式(23)可化為如下形式:

將式(25)代入式(24)得到:

2)求參數(shù)λ:

把式(22)的約束條件代入式(26)兩邊可得:

由式(27)可以解出:

3)求解隸屬度更新矩陣:

把式(28)代入式(26)可以解出:

式(29)可以寫(xiě)為:

在式(30)中,有:

在式(32)中,有:

算法的參數(shù):

其中,t為迭代的次數(shù);τ和η0為定值。

(2)聚類(lèi)中心的更新公式求解:

由于本文中所使用空間距離的原理本質(zhì)仍然是歐氏距離,因此用歐氏距離近似代替該距離進(jìn)行中心參數(shù)的迭代推導(dǎo)。

即:

則求導(dǎo)后的目標(biāo)函數(shù)可近似為:

求解得到:

4.4.2 算法具體執(zhí)行過(guò)程描述

根據(jù)上節(jié)推導(dǎo)的參數(shù),改進(jìn)后算法的具體執(zhí)行過(guò)程如下:

輸入待聚類(lèi)的樣本數(shù)據(jù)X={x1,x2,…,xN},該樣本數(shù)據(jù)可以寫(xiě)成式(10)的形式,N表示樣本空間的大小

輸出樣本的類(lèi)別劃分

初始化:設(shè)定聚類(lèi)中心個(gè)數(shù)的最大數(shù)值C=Cmax,2≤Cmax≤N;初始化迭代計(jì)數(shù)t=0,給出丟棄競(jìng)爭(zhēng)簇的判別條件ε,定值η0,τ,如式(11)利用部分已知信息,初始化隸屬度矩陣U。

優(yōu)化迭代:

步驟2更新計(jì)算基數(shù)矩陣Ni,判斷類(lèi)別基數(shù)是否滿足丟棄競(jìng)爭(zhēng)簇的條件,如果Ni＜ε,則丟棄類(lèi)別i對(duì)應(yīng)的元素。

步驟3利用矩陣U(t)中不滿足丟棄條件的元素,根據(jù)式(35)計(jì)算更新聚類(lèi)中心vi。

步驟4對(duì)更新的聚類(lèi)中心進(jìn)行判斷合并,更新聚類(lèi)中心C。

步驟5判斷聚類(lèi)中心的個(gè)數(shù)是否發(fā)生改變,若發(fā)生改變,則令迭代計(jì)數(shù)t=t+1,跳回步驟1依次計(jì)算;否則算法結(jié)束,跳出循環(huán)。

5 實(shí)驗(yàn)結(jié)果與分析

隨著信息化和數(shù)字化成為時(shí)代的特征,數(shù)字圖像在人類(lèi)生活中扮演的角色越來(lái)越重要,對(duì)于這些圖像信息處理的需要也越來(lái)越迫切。圖像分割是數(shù)字圖像處理的主要技術(shù)之一,圖像分割的好壞將直接影響到圖像的后續(xù)處理。基于圖像分割重要意義,本文的實(shí)驗(yàn)主要將應(yīng)用于圖像分割領(lǐng)域。為驗(yàn)證算法的有效性,在實(shí)驗(yàn)部分將分別用人造圖像和真實(shí)圖像對(duì)所提算法進(jìn)行評(píng)估。

本文設(shè)計(jì)了與相關(guān)算法進(jìn)行性能的比對(duì),其中有常用的FCM算法[4,5]、基于已知信息的可能性模糊C-均值聚類(lèi)(Possibility Fuzzy C Means clustering, PFCM)算法[11]及經(jīng)典CA算法[3],通過(guò)與以上3種算法的比較對(duì)本文算法的性能做出綜合評(píng)價(jià)。

在人造圖像的實(shí)驗(yàn)中,與相關(guān)算法進(jìn)行性能對(duì)比時(shí),采用歸一化互信息(Normalized Mutual Information,NMI)[16-17]作為評(píng)價(jià)指標(biāo)進(jìn)行討論,評(píng)價(jià)指標(biāo)的定義如下rNMI:

其中,Ni,k表示第i個(gè)聚類(lèi)與參考類(lèi)k的契合程度;Ni表示第i個(gè)聚類(lèi)所包含的數(shù)據(jù)樣本量;Nk表示類(lèi)k所包含的數(shù)據(jù)樣本量;N表示整個(gè)數(shù)據(jù)樣本的總量。

該評(píng)價(jià)指標(biāo)的取值為[0,1]區(qū)間,數(shù)值越高表示聚類(lèi)的性能越好。需要說(shuō)明的是,對(duì)于圖像分割,該評(píng)價(jià)指標(biāo)只能應(yīng)用于有標(biāo)準(zhǔn)圖的實(shí)驗(yàn),即人造圖像實(shí)驗(yàn),而真實(shí)圖像由于缺乏標(biāo)準(zhǔn)圖,并不能進(jìn)行評(píng)價(jià)。對(duì)于不能評(píng)價(jià)的真實(shí)圖像可以通過(guò)觀察分割結(jié)果來(lái)進(jìn)行評(píng)判。

實(shí)驗(yàn)的運(yùn)行環(huán)境和相關(guān)算法的參數(shù)設(shè)定如表1和表2所示。

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

表2 各算法的相關(guān)參數(shù)設(shè)定

表2說(shuō)明了在實(shí)驗(yàn)中各個(gè)算法的參數(shù)設(shè)定。一般隸屬度指數(shù)定義在[1.5,2.5]之間[18],在絕大多數(shù)情況下可以直接設(shè)定為2[19]。在表2中,FCM和PFCM的模糊度指數(shù)采用經(jīng)典的設(shè)定,即m=2;C是聚類(lèi)中心數(shù)目,根據(jù)對(duì)人造圖像和其他2幅真實(shí)圖像的設(shè)定與預(yù)判,聚類(lèi)總數(shù)分別設(shè)置為3類(lèi)、2類(lèi)和3類(lèi);M指算法迭代的最大循環(huán)次數(shù),Q是算法迭代終止的閾值,該兩項(xiàng)根據(jù)實(shí)驗(yàn)經(jīng)驗(yàn)取值。根據(jù)文獻(xiàn)[3]CA算法和本文算法中最初的聚類(lèi)總數(shù)Cmax為15;η0和τ是算法中偏移項(xiàng)的參數(shù),根據(jù)實(shí)驗(yàn)調(diào)試的結(jié)果3幅圖像η0分別設(shè)定為1,3和2;ε是Ni的判斷閾值參考文獻(xiàn)[3]設(shè)定。

5.1 人造圖像實(shí)驗(yàn)

為了檢驗(yàn)本文算法的圖像分割效果,選取了有明確聚類(lèi)中心的人造圖像?？紤]到聚類(lèi)結(jié)果的直觀性,模擬圖像的類(lèi)別不宜過(guò)多,過(guò)多一則不便于觀察圖像效果,二來(lái)不容易體現(xiàn)本文算法的自動(dòng)尋找類(lèi)別總數(shù)的性能;模擬圖像的類(lèi)別太少,不能體現(xiàn)算法性能比對(duì)的價(jià)值;因而本文圖像構(gòu)建了3個(gè)類(lèi)別。3類(lèi)的聚類(lèi)中心按順時(shí)針?lè)较蛞来螢?0.117 2, 0.312 5,0.968 8),出于全面考慮,設(shè)定了2個(gè)接近的中心和一個(gè)差別較大的中心。另外,在圖像中隨機(jī)選取了15個(gè)點(diǎn)作為已知信息使用。圖3為各算法對(duì)加入噪聲后的圖像進(jìn)行聚類(lèi)后生成的分割結(jié)果對(duì)比。

由圖3的人造模擬圖像的聚類(lèi)結(jié)果可以看到, CA算法由于噪聲的影響,最終所得類(lèi)別總數(shù)超過(guò)了3類(lèi),與真實(shí)類(lèi)別數(shù)不符,可以判定為失去自動(dòng)尋找聚類(lèi)總數(shù)的性能。而本文算法并未受到噪聲的影響,成功獲取了正確的聚類(lèi)總數(shù)。另外,從圖像上可以看出FCM算法與PFCM算法的聚類(lèi)效果沒(méi)有明顯差別,而本文算法對(duì)于左側(cè)2類(lèi)的聚類(lèi)效果要明顯優(yōu)于這2種算法。

圖3 人造模擬圖像的聚類(lèi)結(jié)果

下面對(duì)圖像聚類(lèi)后得到的數(shù)據(jù)進(jìn)行分析。表3為圖像設(shè)定的數(shù)據(jù)和各算法處理加噪后圖像得到的數(shù)據(jù)。

表3 人造圖像的數(shù)據(jù)及各算法的聚類(lèi)結(jié)果數(shù)據(jù)

分析表3數(shù)據(jù)可以得到,聚類(lèi)中心方面,FCM算法和PFCM算法得到的聚類(lèi)中心與圖像的真實(shí)中心較為接近;本文算法除第2個(gè)中心較接近真實(shí)中心外,其他值存在的偏差要大于另2類(lèi)算法。出現(xiàn)這種狀況的原因可以分為2個(gè)方面:(1)本文算法采取近似的方式,用傳統(tǒng)歐氏距離得到的中心更新公式來(lái)替代本文算法實(shí)際并不存在的中心點(diǎn)迭代公式; (2)本文算法采用空間化距離,把聚類(lèi)中心和與它鄰近的點(diǎn)作為一個(gè)整體來(lái)考慮,這無(wú)疑擴(kuò)大了聚類(lèi)中心取值的范圍,算法得到的中心數(shù)值并不能完全等效傳統(tǒng)算法意義上的聚類(lèi)中心。表3中作為評(píng)價(jià)指標(biāo)的歸一化互信息的值是算法多次執(zhí)行后取得的平均值。分析該指標(biāo)可以得到,本文算法的聚類(lèi)性能要稍好于其他2類(lèi)算法;PFCM算法的性能對(duì)比FCM算法要差一些,根據(jù)文獻(xiàn)[11],PFCM算法將已知信息的隸屬度值取為1的做法破壞了樣本原有的模糊屬性,在一定程度上會(huì)對(duì)整個(gè)樣本集的模糊劃分造成影響。

FCM算法和PFCM算法是經(jīng)過(guò)預(yù)判后設(shè)定的聚類(lèi)類(lèi)別數(shù)目,但是現(xiàn)實(shí)生活中某些圖像預(yù)判類(lèi)別總數(shù)并不那么容易。對(duì)于這種狀況,顯然本文算法更具優(yōu)勢(shì)。

5.2 真實(shí)圖像實(shí)驗(yàn)

為了進(jìn)一步驗(yàn)證本文算法處理真實(shí)圖像的分割效果,選取了2組真實(shí)圖像進(jìn)行實(shí)驗(yàn)。這2組真實(shí)圖像分別是自然界的常見(jiàn)圖像和醫(yī)學(xué)上的常見(jiàn)圖像。真實(shí)圖像中已知樣本點(diǎn)總數(shù)如表4所示。

表4 真實(shí)圖像的已知樣本數(shù)據(jù)點(diǎn)數(shù)

表5是各個(gè)算法對(duì)2組圖像的聚類(lèi)總數(shù),圖4和圖5分別是2組真實(shí)的圖像和算法對(duì)它們的聚類(lèi)結(jié)果。

表5 真實(shí)圖像聚類(lèi)后的類(lèi)別總數(shù)

圖4 圖像1的聚類(lèi)結(jié)果

圖5 圖像2的聚類(lèi)結(jié)果

根據(jù)表5,可以看出CA算法依舊無(wú)法獲取較為準(zhǔn)確的聚類(lèi)類(lèi)別數(shù),而本文算法依舊保持了較好的聚類(lèi)性能,得到了正確的聚類(lèi)類(lèi)別數(shù)。進(jìn)一步地觀察圖4的聚類(lèi)結(jié)果,其中,PFCM算法對(duì)于目標(biāo)和背景的聚類(lèi)效果要優(yōu)于FCM算法,而本文算法的聚類(lèi)結(jié)果更優(yōu)于PFCM算法,不僅聚類(lèi)得到的樹(shù)葉區(qū)域范圍較廣,而且噪點(diǎn)較少。這有效地驗(yàn)證了本文算法的聚類(lèi)優(yōu)勢(shì),更說(shuō)明了使用半監(jiān)督學(xué)習(xí)方式和空間化距離度量標(biāo)準(zhǔn)可以增強(qiáng)CA算法的聚類(lèi)效果,使之得到更佳的聚類(lèi)性能。此外,由于本文算法保有了原CA算法的競(jìng)爭(zhēng)學(xué)習(xí)機(jī)制,同樣具備自動(dòng)聚類(lèi)的能力,這是如FCM和PFCM等需預(yù)先設(shè)定聚類(lèi)類(lèi)別數(shù)的算法所不具備的。根據(jù)人造和真實(shí)圖像的實(shí)驗(yàn)結(jié)果,說(shuō)明了本文算法確為一種有效的具備自動(dòng)聚類(lèi)能力且性能更佳的聚類(lèi)方法,為今后在圖像分割領(lǐng)域的應(yīng)用,如醫(yī)學(xué)圖像分割等專(zhuān)業(yè)領(lǐng)域的分割任務(wù)提供一種新的技術(shù)手段,有著較好的應(yīng)用前景。

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

針對(duì)傳統(tǒng)CA算法存在的信息利用率低和相似度度量標(biāo)準(zhǔn)不可靠的問(wèn)題,本文通過(guò)引入半監(jiān)督項(xiàng)和樣本到中心的空間距離進(jìn)行改進(jìn),并加入聚類(lèi)中心相似性合并的判斷閾值,提出了半監(jiān)督空間化CA算法。半監(jiān)督項(xiàng)利用已知信息對(duì)隸屬度矩陣進(jìn)行了強(qiáng)化,空間化距離避免了傳統(tǒng)歐氏距離的缺陷,加入的判斷閾值進(jìn)一步保證了算法整個(gè)過(guò)程中對(duì)于虛假中心的舍棄趨勢(shì)。通過(guò)人造圖像和真實(shí)圖像2組實(shí)驗(yàn),對(duì)比分析本文算法與FCM算法、PFCM算法、CA算法的性能,結(jié)果表明,本文算法能夠更準(zhǔn)確地獲得聚類(lèi)類(lèi)別數(shù),聚類(lèi)結(jié)果更好,表現(xiàn)出了一定的抗噪性能。

[1] 修 宇,王士同.方向相似性聚類(lèi)方法DSCM[J].計(jì)算機(jī)研究與發(fā)展,2006,43(8):1425-1431.

[2] Jain A K.Algorithms for Clustering Data[M].[S.l.]: Prentice-Hall,Inc.,1988.

[3] Frigui H.Clustering by Competitive Agglomeration[J]. Pattern Recognition,1997,30(7):1109-1119.

[4] Dunn J C.Well-separated Clusters and Optimal Fuzzy Partitions[J].Journal of Cybernetics,1974,4(1):95-104.

[5] Bezdek J C.Pattern Recognition with fuzzy Objective Function Algorithms[M].[S.l.]:Kluwer Academic Publishers,1981.

[6] Sjahputera O.Clustering of Detected Changes in Highresolution Satellite Imagery Using a Stabilized Competitive AgglomerationAlgo-rithm[J].IEEETransactions on Geoscience and Remote Sensing,2011, 49(12):4687-4703.

[7] Boujemaa N.Generalized Competitive Clustering for Image Segmentation[C]//Proceedings of the19th International Conference of the North American Fuzzy Information Processing Society.[S.l.]:IEEE Press, 2000:133-137.

[8] 劉小芳.點(diǎn)密度函數(shù)加權(quán)模糊C-均值算法的聚類(lèi)分析[J].計(jì)算機(jī)工程與應(yīng)用,2004,40(24):64-65.

[9] Tang Chenglong.New Fuzzy C-means Clustering Model Based on the Data Weighted Approach[J].Data& Knowledge Engineering,2010,69(9):881-900.

[10] Mao Qirong,Hu Suli.A Semi-supervised Recognition MethodBasedonProbabilityDistanceManifold Learning and Graph-model[J].Journal of Computer and Theoretical Nanoscience,2014,11(2):303-309.

[11] Bensaid A M,Hall L O,Bezdek J C,et al.Partially Supervised Clustering for Image Segmentation[J]. Pattern Recognition,1996,29(5):859-871.

[12] Liu Yiguang,Li Chunguang.k-NS:A Classifier by the Distance to the Nearest Sub-space[J].IEEE Transactions on Neural Networks,2011,22(8):1256-1268.

[13] Barth N.The Gramian and k-Volume in n-Space:Some Classical Results in Linear Algebra[J].Journal of Young Investigators,1999,2(1):1-4.

[14] Aster R,Borchers B,Thurber C.Tikhonov Regularization[EB/OL].(2013-01-22).http://en.wikipedia.org/ wiki/Tikhonov_regularization.

[15] Treerattanapitak K,Jaruskulchai C.Generalized Agglomerative Fuzzy Clustering[C]//Proceedings of the19th International Conference on Neural Information Processing.Berlin,Germany:Springer,2012:34-41.

[16] Deng Zhaohong.EnhancedsoftSubspaceClustering Integrating Within Cluster and between Cluster Information[J].Pattern Recognition,2010,43(3):767-781.

[17] Jing Liping,Ng M K.An Entropy Weighting k-means Algorithm for Subspace Clustering of High-dimensional Sparse Data[J].IEEE Transactions on Knowledge and Data Engineering,2007,19(8):1026-1041.

[18] Wu Kuo-Lung.Analysis of Parameter Selections for Fuzzy C-means[J].Pattern Recognition,2012,45(1): 407-415.

[19] Zhang Yunjie,Wang Weina,Zhang Xiaona,et al.A Cluster ValidityIndexforFuzzyClustering[J]. Information Sciences,2008,178(4):1205-1218.

編輯 顧逸斐

Semi-supervised Spatial Competitive Agglomeration Algorithm and Its Application in Image Segmentation

YU Ping,WANG Shitong
(School of Digital Media,Jiangnan University,Wuxi 214122,China)

Classic Competitive Agglomeration(CA)algorithm fails to take into account of the information about a few samples which are known and important during the process of cluster.Moreover,competitive agglomeration chooses Euclidean distance as a similarity metric function.But,the distance is more applicable when the distribution of the data points is spherical.This restricts the scope of its application.In order to solve these problems,the semi-supervised entry with the ability to learn is introduced to enhance membership matrix.And a distance from a sample to the spaces is used to instead of Euclidean distance,that each of them is composed of one cluster center and its nearest points.A threshold parameter about similarity of cluster centers is introduced to algorithm as the judgment for merging.The semi-supervised spatial distance competitive agglomeration is proposed.Two sets of experiments using artificial image and real images are operated,and the results show that the proposed algorithm has greater ability to get right cluster number,and gets better clustering results.

Competitive Agglomeration(CA)algorithm;similarity metric function;Euclidean distance;semisupervised;spatial distance;threshold parameter

于 平,王士同.半監(jiān)督空間化競(jìng)爭(zhēng)聚集算法及其在圖像分割中的應(yīng)用[J].計(jì)算機(jī)工程,2015, 41(2):234-241.

英文引用格式:Yu Ping,Wang Shitong.Semi-supervised Spatial Competitive Agglomeration Algorithm and Its Application in Image Segmentation[J].Computer Engineering,2015,41(2):234-241.

1000-3428(2015)02-0234-08

:A

:TP391.41

10.3969/j.issn.1000-3428.2015.02.045

國(guó)家自然科學(xué)基金資助項(xiàng)目(61170122);江蘇省自然科學(xué)基金資助項(xiàng)目(BK2012552)。

于 平(1988-),女,碩士研究生,主研方向:多媒體技術(shù)與應(yīng)用;王士同,教授。

2014-03-24

:2014-04-21E-mail:wxjn00@163.com