基于子空間融合的多視圖聚類算法

黃宗超，王思為，祝 恩，唐樹靈

(國(guó)防科技大學(xué) 計(jì)算機(jī)學(xué)院 湖南 長(zhǎng)沙 410073)

0 引言

子空間聚類假定數(shù)據(jù)點(diǎn)來(lái)自多個(gè)潛在低維子空間，然后對(duì)處于多個(gè)潛在低維子空間上的高維數(shù)據(jù)點(diǎn)進(jìn)行聚類。子空間聚類方法得到了很好的發(fā)展，涌現(xiàn)出許多子空間聚類模型來(lái)揭示數(shù)據(jù)分布的這些低維子空間，以便可以正確分割數(shù)據(jù)中的所有簇，并且每個(gè)簇都在一個(gè)低維子空間。近年來(lái)已經(jīng)開發(fā)了許多子空間聚類方法，例如基于迭代的方法[1-2]、基于因子分解的方法[3-4]、統(tǒng)計(jì)方法[5]以及基于譜聚類的方法[6-7]。文獻(xiàn)[8]提出低秩子空間分割以找到具有低秩表示的子空間結(jié)構(gòu)。文獻(xiàn)[9]提出稀疏子空間聚類以找到與來(lái)自相同子空間的數(shù)據(jù)點(diǎn)相對(duì)應(yīng)的稀疏表示，在獲得子空間表示后，可以對(duì)這種新的表示執(zhí)行譜聚類。目前，以譜聚類[10]為基礎(chǔ)的子空間聚類方法受到廣泛關(guān)注。譜聚類是一種以圖論為基礎(chǔ)的聚類方法, 它將數(shù)據(jù)集中的每個(gè)數(shù)據(jù)當(dāng)作圖的頂點(diǎn), 數(shù)據(jù)之間的相似度當(dāng)作帶權(quán)的邊, 這樣就轉(zhuǎn)化為對(duì)圖的劃分來(lái)解決數(shù)據(jù)聚類[11]。基于譜聚類的子空間聚類方法，其基本過程為:通過找出樣本在低維子空間的表示系數(shù)來(lái)構(gòu)造相似度矩陣, 然后利用譜聚類方法獲得數(shù)據(jù)的聚類結(jié)果。上述方法主要關(guān)注單一數(shù)據(jù)來(lái)源的特征，而不是多個(gè)數(shù)據(jù)來(lái)源的特征。本文將對(duì)具有多視圖特征的數(shù)據(jù)集應(yīng)用子空間聚類，以尋找數(shù)據(jù)集的子空間結(jié)構(gòu)并對(duì)其進(jìn)行聚類。

計(jì)算機(jī)視覺中的許多問題與由多個(gè)不同視圖的特征集表示的數(shù)據(jù)有關(guān)，不同的特征集表示有關(guān)數(shù)據(jù)集不同且部分獨(dú)立的信息。這些不同的特征可以從不同的角度來(lái)提供有用的信息，從而提高數(shù)據(jù)的聚類性能，多視圖聚類是將這些特征集集成在一起來(lái)執(zhí)行聚類。文獻(xiàn)[12]提出多視圖譜聚類模型，以集成異構(gòu)視覺的特征來(lái)進(jìn)行圖像分類。文獻(xiàn)[13]引入正則化多視圖譜聚類，以在具有正則約束的同時(shí)對(duì)不同視圖執(zhí)行聚類。為了解決大規(guī)模多視圖聚類問題，文獻(xiàn)[14]提出了多視圖K-means聚類方法。文獻(xiàn)[9]提出一種基于結(jié)構(gòu)化稀疏學(xué)習(xí)的多視圖聚類方法，以同時(shí)執(zhí)行特征選擇和多視圖聚類。但是，這些方法僅直接關(guān)注于聚類，而不是挖掘數(shù)據(jù)特征所隱藏的結(jié)構(gòu)。本文提出一種新穎的多視圖子空間聚類模型，對(duì)不同視圖的特征進(jìn)行降維以獲得各自的低維子空間表示，然后把各個(gè)視圖的低維子空間表示融合映射到一個(gè)共享的公共子空間表示，從而獲得多視圖一致的低維子空間表示。簡(jiǎn)單來(lái)說(shuō)，就是從單個(gè)的視圖數(shù)據(jù)特征學(xué)習(xí)一個(gè)低維子空間表示，再將多個(gè)視圖的低維子空間表示融合學(xué)習(xí)到一個(gè)一致的低維子空間表示，把融合得到的子空間表示進(jìn)行譜聚類。在3個(gè)基準(zhǔn)數(shù)據(jù)集上的對(duì)比實(shí)驗(yàn)結(jié)果證明了所提出方法的有效性。

1 相關(guān)工作

1.1 子空間聚類

很多數(shù)據(jù)集的數(shù)據(jù)分布于底層的低維子空間中，而不是均勻分布于整個(gè)空間。 因此，數(shù)據(jù)點(diǎn)可以由低維子空間來(lái)進(jìn)行表示。在獲得數(shù)據(jù)集的低維子空間結(jié)構(gòu)后，可以基于子空間表示來(lái)進(jìn)行聚類而不是通過對(duì)整個(gè)空間執(zhí)行聚類。通用的子空間聚類公式可以表示為

(1)

式中：標(biāo)量α>0是重構(gòu)誤差的權(quán)重系數(shù)；q是全為1的列向量，ZTq=q是指子空間表示Z的每列和為1；L(X,XZ)和Ω(Z)分別表示重構(gòu)損失函數(shù)和正則化項(xiàng)，通常會(huì)根據(jù)不同的假設(shè)來(lái)進(jìn)行定義。例如，稀疏子空間聚類[9]是基于1-norm在無(wú)限多個(gè)可能的表示中搜索最稀疏的表示；低秩表示聚類[15]試圖揭示具有低秩表示的聚類結(jié)構(gòu)；平滑表示聚類[16]深入分析了基于自我表示方法的分組效果。基于子空間表示矩陣Z，一般會(huì)用來(lái)構(gòu)造相似度矩陣。 而后，基于相似度矩陣W，通常對(duì)其執(zhí)行譜聚類算法來(lái)得到最終的聚類結(jié)果[9，15-16]。

1.2 多視圖子空間聚類

在子空間聚類中組合多個(gè)視圖的特征是很具有挑戰(zhàn)性的，較為直接的方法是將所有視圖的特征串聯(lián)在一起，然后對(duì)所串聯(lián)的特征執(zhí)行聚類。但是在這種方法中，信息量更多的視圖和信息量較少的視圖將被同等對(duì)待，因此解決方案不是最佳的。還有另外一種多視圖子空間聚類方式，是對(duì)原始的多個(gè)視圖的數(shù)據(jù)特征進(jìn)行融合得到一個(gè)視圖，然后再對(duì)這個(gè)視圖進(jìn)行子空間聚類。本文則提出一種直接對(duì)每個(gè)視圖的低維子空間表示進(jìn)行融合的多視圖子空間聚類方法。

2 多視圖子空間聚類算法

2.1 基于子空間融合的多視圖聚類模型的建立

(2)

2.1.2子空間表示融合 在式(2)中，每個(gè)視圖都可以得到一個(gè)各自的子空間表示矩陣Zv。但是在多視圖聚類中，數(shù)據(jù)原本的分布是一致的，相似的樣本屬于同一個(gè)簇，并且不同視圖之間的子空間表示矩陣應(yīng)具有一致結(jié)構(gòu)。因此，將所有子空間表示矩陣融合為一個(gè)公共的子空間表示，使得公共的子空間表示能夠綜合所有視圖子空間所包含的數(shù)據(jù)分布結(jié)構(gòu)，其數(shù)學(xué)表示式為

(3)

式中：rv是每一個(gè)視圖的子空間表示矩陣的權(quán)重。雖然每一個(gè)視圖的數(shù)據(jù)分布是一致的，但是一般會(huì)側(cè)重于不同的數(shù)據(jù)。這m個(gè)子空間表示可能存在著一些共有的數(shù)據(jù)點(diǎn)分布結(jié)構(gòu)，也會(huì)有每個(gè)視圖所獨(dú)有的數(shù)據(jù)點(diǎn)分布結(jié)構(gòu)。因此，將所有視圖的子空間表示矩陣以不同的權(quán)重融合起來(lái)，得到一個(gè)公共的子空間表示矩陣Z，使其盡可能包含數(shù)據(jù)的所有簇的分布情況。

(4)

2.1.3目標(biāo)函數(shù) 將式(2)和式(4)相結(jié)合，可以得到整個(gè)算法的框架為

(5)

式(5)中第1項(xiàng)是構(gòu)造每個(gè)視圖的子空間表示，第2項(xiàng)是子空間的融合過程，第3項(xiàng)是公共子空間表示的拉普拉斯矩陣的構(gòu)造。通過這種方式，融合得到的公共子空間表示矩陣可以綜合各個(gè)視圖的子空間表示，并且能夠盡可能照顧到各個(gè)子空間所獨(dú)有的數(shù)據(jù)簇的分布，使得聚類效果達(dá)到最好。

2.2 優(yōu)化過程

2.2.1固定Zv、rv,優(yōu)化Z忽略其他無(wú)關(guān)項(xiàng)，目標(biāo)函數(shù)的優(yōu)化式可以轉(zhuǎn)化為

(6)

(7)

式中：fi是F的第i行。再通過對(duì)Zi,j求導(dǎo)并令導(dǎo)數(shù)為0，可以得到Zi,j的閉式解為

(8)

2.2.2固定Zv、Z,優(yōu)化rv忽略其他無(wú)關(guān)項(xiàng)，目標(biāo)函數(shù)的優(yōu)化式可以轉(zhuǎn)化為

(9)

易知式(9)可以等價(jià)為

(10)

令M=Tr((Zv)TZc)，則M∈Rm×m。令f=Tr((Zv)TZ)，則f∈Rm×1。故式(10)可以等價(jià)為

(11)

式中：r=[r1,r2,…,rm]Τ∈Rm×1。易知，這個(gè)問題可以通過求解QP問題得到r的最優(yōu)解。

2.2.3固定Z、rv,優(yōu)化Zv忽略其他無(wú)關(guān)項(xiàng)，目標(biāo)函數(shù)的優(yōu)化式可以轉(zhuǎn)化為

(12)

(13)

對(duì)式(13)進(jìn)行展開并求導(dǎo)，可得Zv的優(yōu)化結(jié)果為

(14)

多視圖子空間聚類算法的流程如下。

輸出：聚類標(biāo)簽矩陣Y。

初始化：初始化Zv、Z，初始化r使得每個(gè)視圖子空間表示矩陣所占權(quán)重相等，隨機(jī)正交初始化F。

1 判斷是否收斂；

2 通過解式(8)來(lái)優(yōu)化Z；

3 通過解式(11)來(lái)優(yōu)化r；

4 通過解式(14)來(lái)優(yōu)化Zv；

5 循環(huán)直至目標(biāo)函數(shù)值收斂；

6 將融合得到的公共子空間表示Z輸入到譜聚類中，最終返回聚類標(biāo)簽矩陣Y。

每種視圖數(shù)據(jù)的樣本數(shù)為n，算法的時(shí)間復(fù)雜度為O(n3)。

3 實(shí)驗(yàn)結(jié)果及分析

3.1 數(shù)據(jù)集和對(duì)比算法

在3個(gè)廣泛使用的數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)評(píng)估，這3個(gè)數(shù)據(jù)集為Caltech101-7數(shù)據(jù)集[18]、bbcsport_seg14of4數(shù)據(jù)集[19]以及 WebKB數(shù)據(jù)集[20]。Caltech101-7是圖像數(shù)據(jù)集Caltech101廣泛使用的子集， 在此子集中有7個(gè)類別，并且從這7個(gè)類別中總共選擇了1 474張圖像，每個(gè)樣本提取了6個(gè)視圖；bbcsport_seg14of4是圖像數(shù)據(jù)集BBCsports的一個(gè)子集，包含4個(gè)視圖、5個(gè)類別，每個(gè)類別選取了116個(gè)樣本；WebKB數(shù)據(jù)集包含1 051個(gè)來(lái)自4所大學(xué)的網(wǎng)頁(yè)，相應(yīng)的標(biāo)記分類為教授、學(xué)生、項(xiàng)目或其他網(wǎng)頁(yè)，共有2個(gè)視圖，此數(shù)據(jù)集的目的是開發(fā)一個(gè)反映萬(wàn)維網(wǎng)內(nèi)容的概率性、象征性知識(shí)庫(kù)，使網(wǎng)絡(luò)上的文本信息以計(jì)算機(jī)可理解的形式提供，從而實(shí)現(xiàn)更復(fù)雜的信息檢索和問題解決方案。

4種對(duì)比算法如下：MLRR_Con[8]是一種基準(zhǔn)方法，直接將多個(gè)視圖的特征拼接在一起，然后對(duì)其執(zhí)行K-means得到最終結(jié)果；Co-reg[12]使用協(xié)同正則化方法，使得不同視圖的劃分達(dá)成一致，這里對(duì)比其中的 “成對(duì)”方法；RMKMC[21]通過獲得共同的聚類指示矩陣并引入2,1范數(shù)，使得該方法對(duì)輸入數(shù)據(jù)的異常值具有魯棒性；FMR[22]通過希爾伯特-史密斯獨(dú)立性準(zhǔn)則構(gòu)造包含互補(bǔ)和一致信息的潛在表示，然后對(duì)潛在表示進(jìn)行數(shù)據(jù)重建得到子空間表示。這4種算法均按照文獻(xiàn)中所推薦的參數(shù)范圍進(jìn)行網(wǎng)格搜索并選取最好的結(jié)果。

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

本文使用準(zhǔn)確率(ACC)、調(diào)和平均數(shù)(F-score)和純度(P)3個(gè)指標(biāo)來(lái)衡量聚類的效果。不同算法在Caltech101-7、bbcsport_seg14of4、WebKB數(shù)據(jù)集下的性能結(jié)果如表1所示?？梢钥闯觯诖蠖鄶?shù)情況下，直接對(duì)特征進(jìn)行串聯(lián)拼接的MLRR_Con方法的性能最差，本文算法在3個(gè)真實(shí)數(shù)據(jù)集下ACC、F-score和P值均為最高。這說(shuō)明多視圖聚類算法對(duì)探索不同視圖之間的互補(bǔ)信息的確是可行的。

表1 不同算法在3個(gè)數(shù)據(jù)集下的性能結(jié)果Table 1 Performance results of different algorithms in three datasets

以bbcsport_seg14of4數(shù)據(jù)集為例，對(duì)兩個(gè)超參數(shù)進(jìn)行敏感性分析。初始化參數(shù)β值為100，參數(shù)α值的敏感性分析結(jié)果如圖1所示?？梢钥闯?，在0.03～0.10區(qū)間內(nèi)，α值波動(dòng)不大，ACC值對(duì)于α值敏感度不高，α值約等于0.072時(shí)ACC值最高。α值為0.072，對(duì)參數(shù)β值進(jìn)行敏感性分析，結(jié)果如圖2所示?？梢钥闯?，β值為500左右時(shí)ACC值最高。β值對(duì)于ACC值的影響稍大，因此取一個(gè)比較好的β值對(duì)于實(shí)驗(yàn)結(jié)果會(huì)有所提升。

圖1 bbcsport_seg14of4數(shù)據(jù)集下參數(shù)α值的敏感性分析Figure 1 Sensitivity analysis of parameter α in the bbcsport_seg14of4 dataset

圖2 bbcsport_seg14of4數(shù)據(jù)集下參數(shù)β值的敏感性分析Figure 2 Sensitivity analysis of parameter β in the bbcsport_seg14of4 dataset

4 小結(jié)

本文提出了一種新穎的多視圖子空間聚類模型。為了利用不同視圖的互補(bǔ)信息，分別對(duì)各個(gè)視圖執(zhí)行子空間表示，然后將它們統(tǒng)一起來(lái)得到公共的子空間表示，再將公共的子空間表示進(jìn)行譜聚類。本文模型充分利用了不同子空間表示所隱藏的數(shù)據(jù)簇的分布信息，這與之前的直接對(duì)原始數(shù)據(jù)進(jìn)行融合的方法不同。后續(xù)研究將在以上工作的基礎(chǔ)上繼續(xù)開展，考慮大規(guī)模數(shù)據(jù)并將低秩表示算法引入模型中。