張遠(yuǎn)鵬,周 潔,鄧趙紅,鐘富禮,蔣亦樟,杭文龍,王士同,

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

2(南通大學(xué) 醫(yī)學(xué)信息學(xué)系,江蘇 南通 226019)

3(Department of Computing,Hong Kong Polytechnic University,Hong Kong 999077,China)

目前,在各個(gè)領(lǐng)域,如模式識別、生物信息學(xué)、自然語言處理以及社交網(wǎng)絡(luò)挖掘等,經(jīng)常會(huì)出現(xiàn)同源異構(gòu)數(shù)據(jù),即數(shù)據(jù)來源(采樣對象)是相同的,但是采樣的角度(樣本特征空間)存在一定的差異,然而又存在一定的關(guān)聯(lián),這類數(shù)據(jù)又被稱為多視角數(shù)據(jù).例如,對人體的血液樣本進(jìn)行采樣分析時(shí),檢測肝功能的指標(biāo)特征可以看成一個(gè)視角,檢測腎功能的指標(biāo)特征可以看成另外一個(gè)視角;又如,在分析銀行客戶數(shù)據(jù)集時(shí),人口學(xué)信息、賬戶關(guān)聯(lián)信息以及客戶消費(fèi)行為信息都可以被當(dāng)成不同的視角.對于多視角數(shù)據(jù)而言,雖然目前一些學(xué)習(xí)算法能夠從單個(gè)視角學(xué)習(xí)到較為豐富和滿意的簇結(jié)構(gòu)信息,但卻人為地割裂了各個(gè)視角之間的相關(guān)性,而這種相關(guān)性如果能夠加以合理利用,則可以在一定程度上提高算法學(xué)習(xí)的效率.因此在這種情況下,多視角協(xié)同學(xué)習(xí)技術(shù)嶄露頭角,并且被應(yīng)用到了領(lǐng)域自適應(yīng)(domain adaption)[1,2]、遷移學(xué)習(xí)(transfer learning)[3,4]、主動(dòng)學(xué)習(xí)(active learning)[5]、多核學(xué)習(xí)(multi-kernel learning)[6,7]、多視角分類(multi-view classification)[8]、多視角聚類(multi-view clustering)[9-18]等各個(gè)領(lǐng)域.

Cleuziou等人[10]在2009年提出的Co-FKM算法是以經(jīng)典的FCM框架為基礎(chǔ)的多視角協(xié)同聚類算法.該算法通過引入?yún)f(xié)調(diào)各視角間空間劃分的隸屬度約束項(xiàng),從而使得各個(gè)視角的空間劃分在算法收斂時(shí)最大程度的趨于一致,達(dá)到協(xié)同學(xué)習(xí)的目的.實(shí)踐結(jié)果表明,Co-FKM算法具有一定的有效性和擴(kuò)展性.能夠被利用的多視角協(xié)同學(xué)習(xí)的機(jī)制有很多,通過調(diào)研相關(guān)文獻(xiàn),基本上可以分為以下幾類.

(1)視角加權(quán)機(jī)制.視角加權(quán)策略在多視角聚類中的應(yīng)用比較廣泛,文獻(xiàn)[12,13]中,Jiang等人和Deng等人為了降低某一視角較差的樣本分布對算法優(yōu)化迭代時(shí)的干擾,在目標(biāo)函數(shù)中引入香農(nóng)熵,通過極大熵原理,使得視角的權(quán)重偏向于具有較好簇結(jié)構(gòu)邊界的視角,從而獲取更好的全局劃分;Tzortzis等人[14]在CMMs算法[15]的基礎(chǔ)上引入視角權(quán)重因子πv,并將其視為混合模型下視角的先驗(yàn)概率,然后通過在約束條件下優(yōu)化一個(gè)對數(shù)似然函數(shù)問題自適應(yīng)獲得視角權(quán)重因子值;Chen等人[16]在k-means算法的基礎(chǔ)上提出了 TW-k-means算法.該算法利用香農(nóng)熵進(jìn)行自適應(yīng)雙層加權(quán),除了對視角加權(quán)外,還對每個(gè)視角中的樣本進(jìn)行加權(quán).

(2)約束傳播機(jī)制.該機(jī)制的基本原理是:在已知的約束(must-link或 cannot-link)下,通過各個(gè)視角不斷學(xué)習(xí),產(chǎn)生新的約束,并通過映射函數(shù)傳播至其他視角以進(jìn)行協(xié)同學(xué)習(xí).其代表算法是 Eaton等人[17]在Co-EM學(xué)習(xí)框架下提出的基于不完全約束傳播機(jī)制的多視角聚類算法.

(3)特征向量一致性約束機(jī)制.在基于譜聚類的多視角算法中,這一策略常被采用.最具代表性的是Kumar等人[18,19]提出的基于co-training和co-regularization技術(shù)的兩種多視角譜聚類算法.兩種算法均認(rèn)為,同一個(gè)樣本在不同的視角下會(huì)被劃分到同一個(gè)簇中,因此在迭代過程中,通過不同視角下特征向量的一致性約束來使各個(gè)視角的劃分趨于一致.

這 3種協(xié)同學(xué)習(xí)的機(jī)制在不同的應(yīng)用場景下有著各自的優(yōu)勢.在第(3)種機(jī)制中,求解每個(gè)視角樣本特征向量的過程可被看成是一種降維過程,特征向量從某種意義上來說反映出簇的結(jié)構(gòu),特征向量一致性約束機(jī)制實(shí)質(zhì)上是在多視角協(xié)同學(xué)習(xí)過程中,尋求不同視角下簇結(jié)構(gòu)的一致性.

受此啟發(fā),本文提出一種基于代表點(diǎn)一致性約束的多視角模糊聚類算法(multi-view fuzzy clustering with a medoidinvariant constraint,簡稱MFCMddI).在該算法中,簇的結(jié)構(gòu)通過多個(gè)代表點(diǎn)(multi-medoid)來進(jìn)行刻畫,利用視角間代表點(diǎn)一致性來約束協(xié)同學(xué)習(xí)過程,具體來說,

(1)為了獲取較為豐富的視角內(nèi)簇結(jié)構(gòu)信息,采用了基于多代表點(diǎn)的簇結(jié)構(gòu)表示策略,即引入樣本權(quán)重系數(shù)來刻畫每個(gè)樣本成為代表點(diǎn)的可能性.

(2)為了在多視角間協(xié)同學(xué)習(xí)過程中代表點(diǎn)能保持一致性,我們認(rèn)為,同一樣本在不同視角下代表簇的權(quán)重系數(shù)的差異性最小.基于此,我們首先提出了多視角聚類模型.該模型的目標(biāo)函數(shù)由2項(xiàng)組成:第1項(xiàng)用于產(chǎn)生高質(zhì)量的視角內(nèi)劃分,該項(xiàng)的優(yōu)化目標(biāo)是使得所有樣本之間的距離之和達(dá)到最小;聚類模型的第 2項(xiàng)用于保持視角間代表點(diǎn)的一致性.為了使整種算法模型易于求解,我們采用視角間兩兩約束的方式(pair-wise constraint),即所有樣本在相鄰兩個(gè)視角下的權(quán)重系數(shù)的乘積之和達(dá)到最大,即代表點(diǎn)差異性最小.

(3)在多視角聚類模型的基礎(chǔ)上構(gòu)建了 MFCMddI算法,并給出了算法的流程和時(shí)間復(fù)雜度分析.MFCMddI算法可被當(dāng)作約束優(yōu)化問題,通過引入拉格朗日乘子和KKT條件,利用求極值的方法得到各個(gè)視角下模糊隸屬度和樣本權(quán)重系數(shù)的迭代規(guī)則,通過迭代尋求各個(gè)視角最優(yōu)的簇結(jié)構(gòu),并利用集成策略,得到全局劃分.

本文的貢獻(xiàn)可以概括為以下幾個(gè)方面.

(1)提出了一種新的多視角聚類模型,該模型綜合考慮了視角內(nèi)的劃分質(zhì)量以及視角間代表點(diǎn)一致性,利用代表點(diǎn)一致性約束進(jìn)行多視角間協(xié)同學(xué)習(xí).

(2)在人工集和真實(shí)數(shù)據(jù)集上進(jìn)行系列實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明,所提出的多視角聚類算法相對于其他算法而言具有一定的優(yōu)勢.

1 多視角聚類模型

1.1 問題描述

1.2 模型構(gòu)建

基于模糊聚類的思想,所提出的多視角聚類模型的目標(biāo)是為了獲取每個(gè)視角的模糊隸屬度矩陣Ψm,然后再利用集成策略得到全局的隸屬度矩陣Ψ.在學(xué)習(xí)Ψm的過程中,并非獨(dú)立進(jìn)行,還要考慮第 1.1節(jié)所陳述的兩個(gè)問題.因此,我們提出了如下的多視角聚類模型:

其中,P表示視角數(shù).從公式(1)可以看出,該模型由兩部分組成.

對于該模型,我們的優(yōu)化目標(biāo)是通過尋找合適的Ψm使得J(Ψ)達(dá)到最小.接下來,將對該模型進(jìn)行進(jìn)一步的細(xì)化.

1.2.1 視角內(nèi)劃分質(zhì)量

文獻(xiàn)[20]指出,用單代表點(diǎn)(one-medoid)來表示一個(gè)簇往往不足以刻畫簇的結(jié)構(gòu)特征,而基于多代表點(diǎn)(multi-medoid)簇結(jié)構(gòu)表示策略可以獲取更多的簇結(jié)構(gòu)信息.為了使這種多代表點(diǎn)策略更加一般化,可以認(rèn)為數(shù)據(jù)集中的每個(gè)樣本都有可能成為簇的代表點(diǎn),而這種可能性可以量化成[0,1]區(qū)間的權(quán)重系數(shù),樣本的權(quán)重值越大,該樣本代表其所在簇的可能性越強(qiáng).因此,為了獲取高質(zhì)量的視角內(nèi)劃分,在最小化樣本之間的距離時(shí),還要考慮樣本的模糊隸屬度和樣本權(quán)重系數(shù).視角內(nèi)劃分的方法可以通過優(yōu)化如下的目標(biāo)函數(shù)來獲得.

其中,θcj,m表示在視角m下,樣本xj代表簇c的程度(即樣本權(quán)重系數(shù));ψci,m表示在視角m下,樣本xj屬于簇c的模糊隸屬度.從公式(2)中可以看出,J′(Ψm)由3項(xiàng)構(gòu)成:第1項(xiàng)表示視角m下,所有樣本的距離之和;第2項(xiàng)和第3項(xiàng)為ψci,m和θcj,m的二次約束項(xiàng),目的是提高其泛化能力.Aψ和Aθ為兩個(gè)大于0的參數(shù),用于保持第1項(xiàng)和第2項(xiàng)、第3項(xiàng)之間的平衡,即控制第2項(xiàng)、第3項(xiàng)對于整個(gè)目標(biāo)函數(shù)的貢獻(xiàn).Aψ值越大,樣本屬于不同簇的隸屬度越平滑;同樣地,Aθ越大,簇中樣本權(quán)重系數(shù)分布越均勻.

1.2.2 視角間代表點(diǎn)一致性(或差異性)

為了定量表示代表點(diǎn)之間的差異性(medoid invariant,簡稱MddI),對于簇c中任意的代表點(diǎn)xj,其在視角m和視角m⊕1下的一致性度量標(biāo)準(zhǔn)定義如公式(7)所示.

接下來,從理論上探討最大化視角間代表點(diǎn)一致性(或最小化視角間代表點(diǎn)差異性)可以降低聚類模型在視角上的聚類誤差.為了使論證過程簡單化且易于理解,我們假設(shè)K=2.另外,由于公式(8)和ψci,m無關(guān),可假設(shè)不同視角下的對應(yīng)樣本獲得相同的聚類標(biāo)簽,每個(gè)簇選擇一個(gè)代表點(diǎn).我們用Y=〈y1,y2〉表示一個(gè)簇在不同視角下的真實(shí)代表點(diǎn)標(biāo)簽,用概率P(ml≠ml⊕1)表示視角l和視角l⊕1之間代表點(diǎn)的差異性,其中,y1,y2∈{1,2},1≤l≤P.由于所提出的聚類模型在每個(gè)視角下采用的是一種多代表點(diǎn)表示策略,即將所有樣本都當(dāng)成潛在的代表點(diǎn),通過為每個(gè)樣本分配權(quán)重系數(shù)來表示代表性大小.如此,視角內(nèi)簇結(jié)構(gòu)本質(zhì)上可由代表點(diǎn)權(quán)重系數(shù)來刻畫[20],因此,P(ml≠ml⊕1)實(shí)際上反映的是視角l和視角l⊕1的簇結(jié)構(gòu)差異性.

定義1(有效聚類模型).如果存在一個(gè)聚類模型,在視角l上滿足條件或,則該模型被稱為視角l上的有效(non-invalid)聚類模型.

定義2(非完美聚類模型).如果存在一個(gè)聚類模型,在視角l上并沒有完成100%的代表點(diǎn)識別率,則稱該模型為非完美(non-perfect)聚類模型.

定義3(條件獨(dú)立聚類模型).對于視角l的聚類模型ml和視角l⊕1的聚類模型ml⊕1,如果滿足以下條件:

則稱ml和ml⊕1是兩個(gè)條件獨(dú)立的聚類模型.其中,.這里需要注意的是,我們使用代表點(diǎn)識別率來表示一個(gè)聚類模型在某一個(gè)視角上的聚類結(jié)果.這是因?yàn)樵诨诖睃c(diǎn)的聚類模型中,無論是基于單代表點(diǎn),還是多代表點(diǎn),如果代表點(diǎn)或代表點(diǎn)的權(quán)重系數(shù)確定,那么數(shù)據(jù)的最終劃分(標(biāo)簽)也能確定.通過上述 3個(gè)定義,我們給出定理1及其證明.

定理 1.如果條件獨(dú)立的假設(shè)能夠滿足,那么代表點(diǎn)差異性P(ml≠ml⊕1)是有效聚類模型和非完美聚類模型在視角l上代表點(diǎn)識別誤差的嚴(yán)格上限.

證明:聚類模型ml的代表點(diǎn)識別誤差可以表示為

聚類模型ml和ml⊕1之間的代表點(diǎn)差異性P(ml≠ml⊕1)可以表示為

因此,為了證明P(ml≠Y)＜P(ml≠ml⊕1),我們只需證明公式(10)所示的不等式成立即可.

根據(jù)定義3和貝葉斯原理,公式(10)可以改寫成公式(11)所呈現(xiàn)的形式:

根據(jù)定義1和定義2可知:

對于任一樣本xj,其在視角l下,在簇c中的權(quán)重系數(shù)為θcj,l,因此,可以采用進(jìn)行度量,即.換言之,可以反映.因此,根據(jù)定理 1,公式(8)所描述的最大化視角間代表點(diǎn)一致性可以降低聚類模型在視角上的聚類誤差.

2 MFCMddI算法

2.1 目標(biāo)函數(shù)及其優(yōu)化策略

將公式(2)和公式(8)帶入公式(1),即可得到 MFCMddI算法的目標(biāo)函數(shù),如公式(13)所示,其約束條件和公式(2)的約束條件相同:

優(yōu)化公式(13)所示的目標(biāo)函數(shù)可以看成求解一個(gè)約束優(yōu)化問題,通過引入拉格朗日乘子和 KKT條件,可以得到公式(14)所表示的優(yōu)化目標(biāo)函數(shù):

定理2.在給定視角m下的樣本權(quán)重系數(shù)矩陣Θm,公式(14)所呈現(xiàn)的優(yōu)化目標(biāo)函數(shù)取得極值時(shí)需要滿足的必要條件為

證明:KKT條件如公式(17)～公式(19)所示.

將公式(17)和公式(3)所示的約束條件聯(lián)合,可以求出:

其中,

對于公式(18),可以從以下兩個(gè)方面進(jìn)行考慮.

(i)當(dāng)αci,m=0時(shí),公式(20)可以化簡為

(ii)根據(jù)公式(19)所示的 KKT 條件,當(dāng)αci,m＞0 時(shí),ψci,m=0;當(dāng)ψci,m＞0 時(shí),αci,m=0.因此,根據(jù)約束條件(4),可將簇集合分成兩個(gè)子集,如公式(16)所示.故對于;當(dāng)時(shí),,此時(shí)αci,m=0.因此,公式(20)可以重寫為

定理3.在給定視角m下的樣本模糊隸屬度矩陣Ψm,公式(14)所呈現(xiàn)的優(yōu)化目標(biāo)函數(shù)取得極值時(shí)需要滿足的必要條件為

證明:定理3的證明方法與定理2基本相同,需要值得注意的是:公式(14)在對θcj,m求偏導(dǎo)數(shù)時(shí),要分m=1和m≠1兩種情況分別討論,證明過程略. □

2.2 算法流程和復(fù)雜度分析

MFCMddI算法采用ψci,m和θcj,m相互迭代的方式來優(yōu)化目標(biāo)函數(shù),即固定一個(gè)變量,求解另外一個(gè).這里,我們先初始化ψci,m,然后求解θcj,m.另外,各個(gè)視角間存在協(xié)同學(xué)習(xí)(從公式(25)亦可看出,在求解θcj,m時(shí),依賴其他視角的代表點(diǎn)權(quán)重系數(shù)),因此在算法執(zhí)行之前,除了需要對ψci,m初始化之外,還需要對θcj,m進(jìn)行初始化.在文獻(xiàn)[22]中,為了避免目標(biāo)函數(shù)陷于局部最優(yōu),所采用的初始化策略能夠使得簇中代表點(diǎn)在樣本空間的分布比較均勻.具體來說,第 1個(gè)簇中代表點(diǎn)選自距離其他樣本距離之和最小的樣本,剩下的簇中代表點(diǎn)選自距離已選代表點(diǎn)最遠(yuǎn)的樣本.因此,MFCMddI算法借鑒這種初始化策略,首先對第 1個(gè)視角的ψci,m和θcj,m(m=1)進(jìn)行初始化,如果在視角1下簇c的中心是xi,則ψci,m=1;否則,ψci,m=0.同樣地,如果在視角 1下簇c的中心是xj,則θcj,m=1;否則,θcj,m=0.對于多視角數(shù)據(jù)而言,由于不同視角之間樣本的對應(yīng)關(guān)系是已知的,故在第 1個(gè)視角初始化完成之后,其他視角直接采用第 1個(gè)視角的結(jié)果.這樣做的目的是使得在多視角協(xié)同聚類過程中,同一個(gè)簇在不同的視角下保持一致的標(biāo)簽編號.當(dāng)算法收斂時(shí),可以獲取到每個(gè)視角下的模糊劃分矩陣.一般來說,可以通過計(jì)算其幾何均值來獲取全局的模糊劃分,本文亦采取同樣的集成策略,即

其中,Ψm表示視角m的模糊劃分矩陣,Ψ表示全局模糊劃分矩陣.初始化算法和MFCMddI算法描述如算法1和算法2所示.

算法1.Initialization.

輸入:第1個(gè)視角樣本的距離矩陣Γ1、簇個(gè)數(shù)K、視角數(shù)P.

輸出:每個(gè)視角的初始模糊隸屬度矩陣Ψm和代表點(diǎn)權(quán)重系數(shù)矩陣Θm;m=1,2,3,…,P.

過程:

算法2.MFCMddI.

輸入:每個(gè)視角的距離矩陣Γm(m=1,2,3,…,P);簇個(gè)數(shù)K;視角數(shù)P;平衡參數(shù)Aψ,Aθ,Bθ;迭代停止誤差ε;m=1,2,3,…,P;初始化得到的各個(gè)視角初始的Ψm和Θm.

輸出:全局模糊隸屬度矩陣Ψ.

過程:

在MFCMddI算法執(zhí)行之前,需要設(shè)置不同的參數(shù),K和ε可由用戶按照樣本的特征設(shè)定,Aψ和Aθ用于控制目標(biāo)函數(shù)中兩個(gè)泛化項(xiàng)的貢獻(xiàn),Bθ用于控制視角間代表點(diǎn)一致性約束的貢獻(xiàn).為了使各項(xiàng)之間趨于平衡,在Aψ已知的情況下,我們給出另外兩個(gè)平衡參數(shù)的取值指導(dǎo)規(guī)則:Aθ=AψN/K,Bθ=Aθ/2.

從算法2的描述中可以看出,MFCMddI算法的時(shí)間復(fù)雜度由兩部分構(gòu)成,分別為計(jì)算每個(gè)視角下樣本之間的距離所消耗的時(shí)間以及迭代過程所消耗的時(shí)間.計(jì)算樣本之間距離的時(shí)間復(fù)雜度為O(N2P),迭代過程的時(shí)間復(fù)雜度為O(PNK),因此,整種算法的時(shí)間復(fù)雜度為O(N2P+PNK),其中,P表示視角數(shù),N表示樣本數(shù),K表示簇個(gè)數(shù).

3 實(shí)驗(yàn)與分析

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

為了評價(jià) MFCMddI算法在多視角數(shù)據(jù)集上的聚類效果,本節(jié)將在不同類型的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),包括:(1)人造數(shù)據(jù)集;(2)真實(shí)數(shù)據(jù)集.另外,還將所提出的算法應(yīng)用到腦磁共振圖像組織分割的場景中.為了突出所提算法的優(yōu)勢,選擇相關(guān)的單視角聚類算法 FCMdd[22]和多視角聚類算法 MVFCMddV[23]、TW-k-means[16]、CoTrainSpec[11]、Co-FKM[10]、WV-Co-FCM[12]、MFCMdd-RWG-P[24]作為對比算法,并利用指標(biāo) NMI(normalized mutual information)[25]和ARI(adjusted rand index)[26]進(jìn)行聚類效果的評價(jià),其中,NMI基于信息論,ARI基于樣本對計(jì)數(shù),二者的定義如下.

假設(shè)某一數(shù)據(jù)集包含N個(gè)樣本,Nij表示由聚類算法產(chǎn)生的第i個(gè)簇與真實(shí)的第j個(gè)簇的契合程度,Ni和Nj分別表示所述第i個(gè)簇與第j個(gè)簇的樣本數(shù),則

在對腦磁共振圖像進(jìn)行組織分割時(shí),我們采用DC(dice coefficient)和JS(jaccard similarity)來評價(jià)分割的效果[27].假設(shè)Ai和Bi分別表示算法分割的第i個(gè)簇和真實(shí)第i個(gè)簇,則DC和JS的定義如下:

其中,C表示簇個(gè)數(shù),|·|表示集合中元素的個(gè)數(shù).DC和JS的取值區(qū)間均為[0,1],值越大,表示聚類效果越好.

在實(shí)驗(yàn)部分,MFCMddI算法與對比算法的可調(diào)參數(shù)設(shè)置,采用網(wǎng)格搜索策略,并結(jié)合評價(jià)指標(biāo),進(jìn)行參數(shù)尋優(yōu),各算法的尋優(yōu)范圍和設(shè)置策略見表1.

Table 1 Parameters setup for MFCMddI and comparison approaches表1 MFCMddI和對比算法的參數(shù)設(shè)置

對于所有的算法實(shí)驗(yàn),分別記錄50次獨(dú)立實(shí)驗(yàn)結(jié)果的各評價(jià)指標(biāo)的平均值和標(biāo)準(zhǔn)差用于算法性能評價(jià).實(shí)驗(yàn)運(yùn)行的平臺(tái)為Windows 7,CPU為I5-4950,4核心,內(nèi)存為8G,MATLAB版本為R2012b.

3.2 人造數(shù)據(jù)集實(shí)驗(yàn)

為了驗(yàn)證MFCMddI算法在視角內(nèi)的劃分質(zhì)量以及視角間代表點(diǎn)一致性約束的效果,首先構(gòu)建如圖1所示的人工數(shù)據(jù)集DS1.DS1包含2個(gè)視角,每個(gè)視角均包含共11個(gè)樣本,其中,樣本1～樣本4屬于同一簇,其余樣本屬于另外一簇.由第1.2節(jié)所提出的聚類模型可知,當(dāng)Bθ=0時(shí),MFCMddI退化成基于多代表點(diǎn)的單視角算法.因此,為了驗(yàn)證MFCMddI在視角內(nèi)刻畫簇結(jié)構(gòu)上的優(yōu)勢,選擇視角-1,并引入單代表點(diǎn)單視角聚類算法FCMdd,與其在視角內(nèi)進(jìn)行聚類效果比較.表2給出了FCMdd和MFCMddI在視角-1上的聚類結(jié)果.

Fig.1 Sample distribution of DS1圖1 DS1的樣本分布

Table 2 Clustering results for FCMdd and MFCMddI on view-1表2 FCMdd和MFCMddI在視角-1上的聚類結(jié)果

從表2中可以看出,FCMdd將樣本1～樣本4、樣本11劃分為一類,標(biāo)記成簇1;其余樣本劃分為另一類,標(biāo)記成簇2;且算法識別出簇1的代表點(diǎn)為樣本4(代表點(diǎn)用“√”標(biāo)記,非代表點(diǎn)用“-”標(biāo)記),簇2的代表點(diǎn)為樣本7.另外,通過仔細(xì)觀察亦可發(fā)現(xiàn),在 FCMdd中,代表點(diǎn)隸屬于其所代表簇的程度為 1,即ψ24=1.這種現(xiàn)象在MFCMddI中并不存在,在MFCMddI中,并不要求具有最大θ的樣本同樣具有最大的ψ,例如在簇1中,樣本4代表簇1的程度最高,然而其屬于簇1的程度低于樣本1～樣本3.上述現(xiàn)象出現(xiàn)的原因可以歸結(jié)為如下幾點(diǎn).

1)在FCMdd中,代表點(diǎn)距離自身的距離總為0,按照FCMdd中模糊隸屬度的計(jì)算方法,其模糊隸屬度顯然為1.換言之,在FCMdd中,若一個(gè)樣本被選為一個(gè)簇的代表點(diǎn),那么它不可能再屬于其他簇.

2)與FCMdd不同,在MFCMddI進(jìn)行視角內(nèi)劃分時(shí),不再單獨(dú)地選擇某一個(gè)樣本作為簇的代表點(diǎn),而是將所有的樣本都當(dāng)成潛在的代表點(diǎn),為每一個(gè)樣本分配不同的權(quán)重系數(shù)來反映其在簇中的重要程度,從而實(shí)現(xiàn)共同刻畫簇結(jié)構(gòu).在某一簇中權(quán)重系數(shù)高的樣本有可能屬于另外一個(gè)簇.

通過觀察樣本11的劃分情況,亦能發(fā)現(xiàn)單代表點(diǎn)和多代表點(diǎn)的區(qū)別.在圖1(a)中,虛線標(biāo)識的空心圓代表簇1和簇2的理想簇中心(并非實(shí)際樣本),從圖中可以看出,樣本11離右邊的簇中心更近,但是從FCMdd劃分的結(jié)果來看,樣本11被劃分至左邊的簇,因?yàn)闃颖?1離代表點(diǎn)4更近,按照FCMdd中模糊隸屬度的計(jì)算方法,樣本11屬于簇1的模糊隸屬度大于屬于簇2的模糊隸屬度.這說明,單代表點(diǎn)在刻畫簇結(jié)構(gòu)時(shí)存在一定的缺陷,尤其是像簇1中無樣本靠近理想簇中心時(shí),這種單代表點(diǎn)策略的問題暴露的越明顯.但是在MFCMddI,樣本11被正確地劃分到簇1,這說明多代表點(diǎn)策略比單代表點(diǎn)策略更能刻畫簇的結(jié)構(gòu).

另外,為了觀察MFCMddI算法在利用視角間代表點(diǎn)一致性約束進(jìn)行多視角協(xié)同聚類與獨(dú)立聚類之間的差異,在DS1上分別以Bθ=0以及Bθ≠0兩種情況來執(zhí)行MFCMddI算法,聚類結(jié)果見表3.

Table 3 Independent and cooperative clustering results for MFCMddI on DS1表3 MFCMddI在DS1上的獨(dú)立聚類和協(xié)同聚類結(jié)果

在表3中,加粗的權(quán)重系數(shù)表示簇中最具代表性的兩個(gè)樣本.從實(shí)驗(yàn)結(jié)果可以看出,當(dāng)Bθ=0時(shí),視角-1中簇2的兩個(gè)最具代表性的樣本依次是 7,8,而視角-2中簇 2的兩個(gè)最具代表性的樣本依次是 8,10,即在視角-1與視角-2間,簇2的代表點(diǎn)不完全一致.另外,在視角-2中,樣本11被錯(cuò)誤地劃分至簇1中.當(dāng)Bθ≠0時(shí),兩個(gè)視角進(jìn)行協(xié)同聚類,協(xié)同的目標(biāo)是使得視角間對應(yīng)樣本的權(quán)重系數(shù)乘積之和達(dá)到最大,即保持視角間簇中樣本的代表性保持不變.從表3的實(shí)驗(yàn)結(jié)果可以看出,視角-1中簇2的兩個(gè)最具代表性的樣本依次為7,8,視角-2中簇2的兩個(gè)最具代表性的樣本同樣依次為7,8.這說明相對于獨(dú)立聚類而言,MFCMddI算法利用視角間代表點(diǎn)一致性約束,調(diào)整了兩個(gè)視角中樣本的權(quán)重系數(shù),使得視角間簇中對應(yīng)樣本的代表性保持一致.這一調(diào)整使得視角-2中簇 2中樣本的代表性變得更為合理,從而使得樣本11被正確地劃分至簇2中.

為了更進(jìn)一步地突出MFCMddI算法的多視角協(xié)同聚類效果,構(gòu)建DS2,并引入其他多視角聚類算法進(jìn)行聚類效果的比較.DS2數(shù)據(jù)集包含3個(gè)視角,由3維空間樣本通過向3個(gè)2維空間(x-y,y-z,x-z)投影得到,每個(gè)視角均包含3個(gè)簇共600個(gè)樣本,如圖2所示.

MFCMddI算法以及所引入的對比算法的聚類結(jié)果見表4.對于MFCMddI,分別給出在Bθ=0和Bθ≠0時(shí)每個(gè)視角的聚類結(jié)果,當(dāng)Bθ≠0時(shí),global表示利用公式(27)而得到的全局聚類結(jié)果.從表4中評價(jià)指標(biāo)反映的情況來看,在視角-y-z上,相對于獨(dú)立聚類,協(xié)同聚類使得該視角的劃分質(zhì)量有了明顯的提升.這一優(yōu)勢可通過圖3進(jìn)一步說明.

Fig.2 Distribution of DS2圖2 DS2的樣本分布

Table 4 Clustering results in terms of NMI and ARI of different approaches on DS2表4 不同算法在DS2上以NMI和ARI為指標(biāo)的聚類結(jié)果

Fig.3 Clustering results of view-y-zwithBθ=0 andBθ≠0圖3 視角-y-z在Bθ=0與Bθ≠0時(shí)的聚類結(jié)果

圖3展示了視角-y-z在Bθ=0以及Bθ≠0時(shí)的聚類結(jié)果.在該圖中,按照樣本權(quán)重系數(shù)大小,每個(gè)簇中標(biāo)記了兩個(gè)最具代表性的點(diǎn),并用“五角星”表示.對比圖3(b)和圖3(a)可以看出,在簇中代表點(diǎn)一致性約束的作用下,“▽”表示的簇的兩個(gè)代表點(diǎn)發(fā)生了較為明顯的漂移,結(jié)合圖2(c),我們可以看出,這種漂移是朝著真實(shí)簇中心方向,從而使得圖3(b)的劃分結(jié)果更接近真實(shí)情況.

對于引入的多視角對比算法,WV-Co-FCM、MFCMdd-RWG-P、TW-k-means和CoRegSpec在DS2數(shù)據(jù)集上均達(dá)到了完美劃分,MVFCMddV和Co-FKM表現(xiàn)略差.其原因可以歸結(jié)為以下幾個(gè)方面.

1)WV-Co-FCM和TW-k-means算法通過引入香農(nóng)熵來自適應(yīng)協(xié)同學(xué)習(xí)不同視角的權(quán)重,而對于DS2數(shù)據(jù)集,視角-x-y具有非常清晰的簇結(jié)構(gòu)邊界,因此,這兩種算法能夠在該視角上學(xué)習(xí)到較高的權(quán)重,使得整個(gè)數(shù)據(jù)集的劃分結(jié)果極大地偏向于視角-x-y,故取得了表4所示的完美結(jié)果.

2)在 MFCMdd-RWG-P算法中,用戶可以自定義每個(gè)簇中代表點(diǎn)的個(gè)數(shù),且強(qiáng)制每個(gè)簇在不同的視角下代表點(diǎn)必須一致,同時(shí)為每個(gè)視角分配權(quán)重,權(quán)重可以通過與模糊隸屬度不斷交替迭代,使得目標(biāo)函數(shù)值最小的方式而自適應(yīng)獲得.與WV-Co-FCM和TW-k-means類似,在DS2數(shù)據(jù)上,由于視角-x-y的易分性,該算法達(dá)到完美劃分.

3)在CoRegSpec算法中,Kumar等人將半監(jiān)督學(xué)習(xí)中的協(xié)同正則化(co-regularization)技術(shù)移植至無監(jiān)督學(xué)習(xí)中來解決多視角聚類問題,并以此構(gòu)建了多視角譜聚類的學(xué)習(xí)框架.在該架構(gòu)中,協(xié)同正則化項(xiàng)引入的基礎(chǔ)是認(rèn)為同一樣本在不同視角下應(yīng)該屬于同一個(gè)簇;另外,對于每個(gè)正則化項(xiàng),可由用戶設(shè)定正則化參數(shù)來控制其貢獻(xiàn);同時(shí),該參數(shù)也反映視角的重要程度.因此在 DS2中,由于視角-x-y的易分性,可以通過為該視角分配較大的正則化參數(shù)來保證整個(gè)數(shù)據(jù)集的聚類效果.

4)MVFCMddV事實(shí)上是FCMdd算法的多視角版本,MVFCMddV針對每個(gè)視角,構(gòu)建樣本到簇中心距離矩陣,同時(shí)自適應(yīng)學(xué)習(xí)每個(gè)簇在每個(gè)視角下的權(quán)重,然后通過加權(quán)求和的方式合并各個(gè)視角下的距離矩陣,使得目標(biāo)函數(shù)的形式和FCMdd統(tǒng)一.然而,MVFCMddV算法并沒有像WV-Co-FCM和TW-kmeans那樣考慮視角本身的權(quán)重,因而在DS2數(shù)據(jù)上,視角-x-y易分性所帶來的好處并沒有得到很好的體現(xiàn).

5)Co-FKM算法是在FCM的框架下,通過引入模糊隸屬度約束項(xiàng),使得各個(gè)視角之間的劃分盡量趨于一致.這種協(xié)同學(xué)習(xí)的方式會(huì)使得最終的劃分結(jié)果趨于一種均衡狀態(tài),例如,對于 DS2數(shù)據(jù)集來說會(huì)降低視角-x-y的劃分質(zhì)量,但是會(huì)提高視角-y-z的劃分質(zhì)量.因此,對于多視角數(shù)據(jù)集而言,若某個(gè)視角存在清晰的簇結(jié)構(gòu)邊界,Co-FKM算法并非首選,基于視角加權(quán)的算法更加合適.然而對于本文所提出的MFCMddI算法而言,和Co-FKM一樣,并沒有考慮視角的權(quán)重;但是與Co-FKM不同的是,簇中代表點(diǎn)的一致性約束對于原本有著較好簇結(jié)構(gòu)邊界的視角(模糊隸屬度矩陣偏“硬(crisp)”)不會(huì)造成很大的影響,因此在利用公式(27)進(jìn)行模糊隸屬度矩陣合成時(shí),最終的結(jié)果會(huì)偏向具有較好簇結(jié)構(gòu)邊界的視角.這也是MFCMddI算法在未考慮視角權(quán)重的情況下,在DS2上取得完美劃分的原因.

3.3 真實(shí)數(shù)據(jù)集

為了更進(jìn)一步地驗(yàn)證MFCMddI算法在真實(shí)數(shù)據(jù)集上的表現(xiàn),我們從BSDS300中選擇一幅大小為121×81的彩色圖像(DS3)進(jìn)行圖像分割實(shí)驗(yàn)[29],分別將其RBG顏色空間的3個(gè)分量當(dāng)成3個(gè)視角,該圖像如圖4所示,圖4(a)為原圖像;圖4(b)為人工分割結(jié)果,作為評價(jià)依據(jù);圖4(c)為視角-R;圖4(d)為視角-G;圖4(e)為視角-B.

MFCMddI算法以及所選對比算法在NMI和ARI上的評價(jià)結(jié)果見表5.另外,圖5也給出了從視覺角度的劃分結(jié)果.從定量評價(jià)的結(jié)果以及分割視角效果來看,MFCMddI相對于所選的對比算法而言具有一定的優(yōu)勢.

除了DS3之外,我們還使用CMU PIE數(shù)據(jù)集來測試算法的性能.該數(shù)據(jù)集包含41 368幅64×64人臉圖像,這些圖像分別由68人在不同的光照、姿勢和表情下獲得[30].圖6給出了C05和C27組中的示例樣本,其中,C05和C07為Deng等人[31]公開的在不同角度和光照條件下拍攝的照片.我們從C05和C27中各抽取100幅圖像,構(gòu)建2視角數(shù)據(jù)集DS4來進(jìn)行算法測試,實(shí)驗(yàn)結(jié)果見表6.

Fig.4 Image elephant,manual partition result and its three views圖4 Elephant、人工分割結(jié)果及其3個(gè)視角

Table 5 Clustering results in terms of NMI and ARI of different approaches on DS3表5 不同算法在DS3上以NMI和ARI為指標(biāo)的聚類結(jié)果

Fig.5 Segmentation results of different approaches on DS3圖5 不同算法在DS3上的分割結(jié)果

Fig.6 Samples from CMU PIE face dataset圖6 CMU PIE人臉數(shù)據(jù)庫中的示例樣本

Table 6 Clustering results in terms of NMI and ARI of different approaches on DS4表6 不同算法在DS4上以NMI和ARI為指標(biāo)的聚類結(jié)果

從表6中可以看出,相對于所引入的對比算法,MFCMddI在評價(jià)指標(biāo)NMI和ARI上取得了最佳的表現(xiàn)效果.相對于對比算法中表現(xiàn)最好的WV-Co-FCM,NMI指標(biāo)提升了6.69%,ARI指標(biāo)提升了9.83%.相對于表現(xiàn)最差的MFCMdd-RWG-P,NMI指標(biāo)提升了18.54%,ARI指標(biāo)提升了32.2%.另外,圖7給出了在協(xié)同狀態(tài)以及非協(xié)同狀態(tài)下,MFCMddI算法在 DS4上的可視化聚類結(jié)果以及代表點(diǎn)選擇情況(每個(gè)簇標(biāo)注了兩個(gè)最具代表性樣本,且標(biāo)注中的數(shù)字表示樣本在原始數(shù)據(jù)集中的編號).

Fig.7 Clustering results of MFCMddI on each view of DS4 withBθ≠0 andBθ=0 respectively圖7 在Bθ≠0和Bθ=0時(shí)MFCMddI算法在DS4上各個(gè)視角聚類結(jié)果

Fig.7 Clustering results of MFCMddI on each view of DS4 withBθ≠0 andBθ=0 respectively(Continued)圖7 在Bθ≠0和Bθ=0時(shí)MFCMddI算法在DS4上各個(gè)視角聚類結(jié)果(續(xù))

從圖7中可以看出,在非協(xié)同狀態(tài),視角-C05與視角-C27所標(biāo)記的代表樣本在大多數(shù)情況下并不相同.然而在DS4中,兩個(gè)視角的樣本是同一個(gè)志愿者在不同角度和光照條件下獲得,故在DS4中,往往存在這樣的一個(gè)事實(shí):在視角C05中具有代表性的樣本在視角C27中仍然具有代表性.所以,利用這樣的事實(shí)作為約束條件進(jìn)行視角間協(xié)同聚類,能夠改善非協(xié)同聚類的性能.而從表6的定量分析以及從圖7所呈現(xiàn)的視覺效果來說,確實(shí)如此.

從在DS3和DS4這兩個(gè)真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果來看,基于視角加權(quán)策略協(xié)同聚類的算法,如WV-Co-FCM、TW-k-means、MFCMdd-RWG-S并未像在DS2上一樣取得最佳的劃分結(jié)果.這是因?yàn)樵贒S3和DS4上,任一視角上都不具備存在明顯的簇結(jié)構(gòu)邊界的優(yōu)勢,這使得這類聚類算法所學(xué)習(xí)的權(quán)重的差異不夠顯著.然后,這兩個(gè)數(shù)據(jù)集在各個(gè)視角上卻能保持如前所述的事實(shí),即樣本的重要程度在各個(gè)視角間差異很小,這樣的事實(shí)卻是有利于所提出MFCMddI算法的學(xué)習(xí),因而在兩個(gè)數(shù)據(jù)集上取得了具有一定競爭力的劃分結(jié)果.

3.4 應(yīng)用案例

從腦部磁共振圖像(magnetic resonance images,簡稱 MRIs)中分離出腦組織,包括灰質(zhì)(gray matter,簡稱GM)、白質(zhì)(white matter,簡稱WM)和腦脊液(cerebrospinal fluid,簡稱CSF)對于臨床診斷和輔助決策有著非常重要的作用[32-34].我們從McGill大學(xué)MN(McConnel brain imaging center of the montreal neurological institute)協(xié)會(huì)提供的BrainWeb模擬數(shù)據(jù)庫[35]中選擇5幅腦部磁共振圖像,相關(guān)屬性見表7.

Table 7 Properties of selected MRIs表7 所選腦部核磁共振圖像的相關(guān)屬性

ID為1的MRI及其解剖學(xué)上的分割結(jié)果(作為金標(biāo)準(zhǔn))如圖8所示.對于所選的5幅MRI,分別利用Gabor濾波器抽[36]取不同的特征構(gòu)建3個(gè)不同的特征視角,然后在所構(gòu)建的多視角數(shù)據(jù)集上執(zhí)行MFCMddI算法和對比算法,并利用JS和DC指標(biāo)進(jìn)行評價(jià).表8給出了所有算法在5幅MRI上運(yùn)行的均值和標(biāo)準(zhǔn)差(每幅圖像獨(dú)立執(zhí)行 50次,獲得均值和標(biāo)準(zhǔn)差,然后再取每幅圖像的均值的平均值和標(biāo)準(zhǔn)差的平均值).對于 MFCMddI,僅給出集成后的全局劃分結(jié)果.從表8的結(jié)果來看,TW-k-means和MFCMddI均取得了較好的分割效果.

Fig.8 Illustration sample of MRI and anatomical segmentation resutls圖8 MRI示例樣本和解剖學(xué)分割結(jié)果

Table 8 Clustering results in terms of JS and DC of different approaches on MRIs表8 不同算法在MRI上以JS和DC為指標(biāo)的聚類結(jié)果

3.5 參數(shù)分析

MFCMddI算法中,需要分析的主要參數(shù)有Aψ,Aθ,Bθ,其中,Aθ與Bθ可按照前文所述的指導(dǎo)規(guī)則設(shè)定.故只需分析Aψ在不同取值下對MFCMddI算法聚類效果的影響.我們從0.001～3這個(gè)區(qū)間中,為Aψ設(shè)定14個(gè)不同的值,分別為0.001,0.005,0.01,0.06,0.09,0.14,0.20,0.25,0.3,0.7,1,1.5,2和3,然后從NMI和ARI中選擇一個(gè)評價(jià)指標(biāo)(這里選擇NMI,ARI類似),在DS2、DS3和DS4上評價(jià)MFCMddI算法在不同Aψ下的聚類效果,從而分析算法對參數(shù)Aψ的敏感性.圖9給出了MFCMddI算法在所選3個(gè)數(shù)據(jù)集上,評價(jià)指標(biāo)NMI隨Aψ變化的曲線.

Fig.9 Clustering results on DS2,DS3 and DS4 in terms of NMI for the proposed MFCMddI with different parameterAψ圖9 MFCMddI算法在DS2、DS3和DS4上NMI隨參數(shù)Aψ的變化關(guān)系

從圖9中可以看出,參數(shù)Aψ對MFCMddI算法的聚類效果有著較大的影響,較大或者較小的取值都會(huì)降低算法的性能,在實(shí)踐中,可以在[0.001,0.8]中進(jìn)行參數(shù)尋優(yōu).

4 結(jié) 論

傳統(tǒng)的單視角聚類算法在應(yīng)用于多視角聚類任務(wù)時(shí)缺乏有效的協(xié)同學(xué)習(xí)方法.針對此問題,本文首先提出了一種多視角聚類模型.該模型的目標(biāo)函數(shù)由兩項(xiàng)構(gòu)成:第1項(xiàng)反映視角內(nèi)劃分質(zhì)量;第2項(xiàng)為約束項(xiàng),反映視角間的協(xié)同學(xué)習(xí)機(jī)制.在此基礎(chǔ)上,提出了一種基于多代表點(diǎn)一致性約束的多視角模糊聚類算法.該算法通過采用簇結(jié)構(gòu)多代表點(diǎn)表示策略來保障視角內(nèi)的劃分質(zhì)量;同時(shí),認(rèn)為簇內(nèi)代表點(diǎn)在不同的視角下能夠保持其代表性,進(jìn)而在算法的目標(biāo)函數(shù)中,通過最大化兩兩相鄰視角下代表點(diǎn)權(quán)重系數(shù)的乘積之和的方式進(jìn)行協(xié)同學(xué)習(xí).理論分析表明,該協(xié)同學(xué)習(xí)機(jī)制確實(shí)能夠保證聚類效果的提升.最后,在人工數(shù)據(jù)集以及真實(shí)數(shù)據(jù)集上,通過實(shí)驗(yàn)驗(yàn)證了該算法在多視角數(shù)據(jù)集上的聚類效果,并通過與同類算法的對比,突出該算法的優(yōu)勢.

盡管 MFCMddI算法在多視角數(shù)據(jù)集上具有不錯(cuò)的聚類效果,然而在后續(xù)的研究過程中,仍然存在進(jìn)一步拓展的空間,例如,如何解決不同視角下樣本數(shù)量不一致問題、如何差異化地對待不同的視角問題等.這些問題也將成為我們后續(xù)研究的重要目標(biāo).