于 平,王士同

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

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

于 平,王士同

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

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

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

1 概述

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

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

2 背景介紹

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

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

3 CA算法

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

3.1 CA算法基本原理

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

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

偏移項中參數(shù):

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

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

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

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

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

同理得到的聚類中心為:

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

3.2 CA算法存在的問題

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

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

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

以上問題,制約了CA算法的適用性范圍。本文將提出一種新的改進CA算法來解決上述問題,增強算法的性能及適用性。

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

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

4.1 半監(jiān)督方法

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

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

4.2 空間距離的原理

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

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

圖1 空間距離原理推導

那么sq是距離子空間Si最近的點,則距離為:

式(12)的距離在圖1中是一個通過原點的平面,考慮到逐個計算式(12)中歐氏距離的復雜性,可以直接把子空間Si看作一個整體來計算。

設Ni是xi的點組成的矩陣且滿足列滿秩條件,該平行體的體積[13]:

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

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

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

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

圖2 空間距離推導

由于在式(16)中

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

4.3 鄰近中心點的判斷與合并部分

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

判斷合并原理如下:

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

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

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

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

步驟2將滿足dv≤θ的聚類中心按照式(20)的方式合并為新的聚類中心,按照式(21)計算對應的新隸屬度。

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

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

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

4.4.1 目標函數(shù)迭代參數(shù)的推導

為了得到最優(yōu)的聚類結果,下面介紹所需迭代參數(shù)的相關推導。

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

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

1)對uij求偏導和定義Ni:

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

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

2)求參數(shù)λ:

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

由式(27)可以解出:

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

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

式(29)可以寫為:

在式(30)中,有:

在式(32)中,有:

算法的參數(shù):

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

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

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

即:

則求導后的目標函數(shù)可近似為:

求解得到:

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

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

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

輸出樣本的類別劃分

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

優(yōu)化迭代:

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

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

步驟4對更新的聚類中心進行判斷合并,更新聚類中心C。

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

5 實驗結果與分析

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

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

在人造圖像的實驗中,與相關算法進行性能對比時,采用歸一化互信息(Normalized Mutual Information,NMI)[16-17]作為評價指標進行討論,評價指標的定義如下rNMI:

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

該評價指標的取值為[0,1]區(qū)間,數(shù)值越高表示聚類的性能越好。需要說明的是,對于圖像分割,該評價指標只能應用于有標準圖的實驗,即人造圖像實驗,而真實圖像由于缺乏標準圖,并不能進行評價。對于不能評價的真實圖像可以通過觀察分割結果來進行評判。

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

表1 實驗環(huán)境

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

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

5.1 人造圖像實驗

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

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

圖3 人造模擬圖像的聚類結果

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

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

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

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

5.2 真實圖像實驗

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

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

表5是各個算法對2組圖像的聚類總數(shù),圖4和圖5分別是2組真實的圖像和算法對它們的聚類結果。

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

圖4 圖像1的聚類結果

圖5 圖像2的聚類結果

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

6 結束語

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

[1] 修 宇,王士同.方向相似性聚類方法DSCM[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] 劉小芳.點密度函數(shù)加權模糊C-均值算法的聚類分析[J].計算機工程與應用,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].計算機工程,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

國家自然科學基金資助項目(61170122);江蘇省自然科學基金資助項目(BK2012552)。

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

2014-03-24

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