趙博宇 張長(zhǎng)青 , 陳 蕾 ,3 劉新旺 李澤超 胡清華

在實(shí)際應(yīng)用中,數(shù)據(jù)通常從不同的角度采集,稱(chēng)為多視圖數(shù)據(jù)[1-2].多視圖學(xué)習(xí)研究[2-7]表明,有效利用不同視圖之間的一致性和互補(bǔ)性可以顯著提高任務(wù)(如多視圖聚類(lèi)/分類(lèi))性能.在聚類(lèi)方面,已有大量的研究將單視圖聚類(lèi)擴(kuò)展到多視圖聚類(lèi).在這些方法中,基于自表示的多視圖子空間聚類(lèi)[8-12]方法通過(guò)可學(xué)習(xí)的關(guān)系矩陣處理復(fù)雜的高維數(shù)據(jù),取得了顯著效果.最近,一些相關(guān)研究[13-15]將譜聚類(lèi)和自表示關(guān)系圖聯(lián)合優(yōu)化,進(jìn)一步提高多視圖融合效果.

盡管基于自表示的多視圖子空間聚類(lèi)技術(shù)已經(jīng)引起了人們的廣泛關(guān)注,并取得了很好的性能,但是這些方法只適用于具有完整視圖的數(shù)據(jù),不能處理具有缺失視圖的數(shù)據(jù).對(duì)于視圖缺失的情況,現(xiàn)有的方法大多是先對(duì)缺失值進(jìn)行補(bǔ)全,然后對(duì)后續(xù)任務(wù)應(yīng)用傳統(tǒng)的多視圖學(xué)習(xí)算法.廣泛使用的數(shù)據(jù)補(bǔ)全方法之一是矩陣補(bǔ)全[16-17],它基于低秩假設(shè),對(duì)于隨機(jī)缺失情況具有較好的效果.基于深度學(xué)習(xí)的補(bǔ)全方法[18-22]通常通過(guò)將問(wèn)題建模為視圖轉(zhuǎn)換,從可用視圖生成缺失視圖.這些方法側(cè)重于缺失視圖的填充,而不是具體的分析任務(wù)(如聚類(lèi)),因此不能保證后續(xù)任務(wù)的性能.現(xiàn)有的不完整多視圖聚類(lèi)方法[23-25]沒(méi)有考慮與缺失視圖對(duì)應(yīng)的(互補(bǔ))信息的一致性,因此在挖掘不同視圖之間的相關(guān)性時(shí)缺乏合理性和魯棒性.

上述解決視圖缺失問(wèn)題的方法主要有以下局限性:1)對(duì)于具有任意視圖缺失模式的數(shù)據(jù)樣本,當(dāng)前的補(bǔ)全方法通常不夠靈活.此外,對(duì)于具有較多視圖的數(shù)據(jù),視圖缺失模式(即可用視圖的組合)將變得更加復(fù)雜,這將導(dǎo)致大多數(shù)現(xiàn)有視圖補(bǔ)全方法無(wú)法使用;2)現(xiàn)有缺失視圖聚類(lèi)方法沒(méi)有有效地利用多個(gè)視圖之間的高階相關(guān)性[8-9,11].為了解決上述問(wèn)題,本文提出了一種新穎的多視圖聚類(lèi)方法,它可以同時(shí)補(bǔ)全缺失的數(shù)據(jù)和探索多個(gè)視圖之間的高階相關(guān)性.所提模型的框架如圖1 所示.

圖1 同時(shí)用 P (X|H) 對(duì)隱空間 H 進(jìn)行建模,并基于隱表示生成完整特征.根據(jù)完整的數(shù)據(jù),GM-PMVC 將子空間表示集成到一個(gè)張量中,可以挖掘多視圖數(shù)據(jù)高階相關(guān)性Fig.1 Illustration of generative model for partial multi-view clustering (GM-PMVC).Given incomplete multi-view data,we simultaneously model latent space H by P (X|H) and generate complete feature based on latent representation.According to the completed data,GM-PMVC integrates subspace representation into a tensor which can effectively explores higher-order correlations equipped with low-rank constraint

本文的貢獻(xiàn)總結(jié)如下:1) 針對(duì)不完整視圖數(shù)據(jù),提出了一種新的多視圖子空間聚類(lèi)算法,該算法能夠在統(tǒng)一的框架下補(bǔ)全缺失數(shù)據(jù)并進(jìn)行多視圖聚類(lèi).因此,數(shù)據(jù)補(bǔ)全和聚類(lèi)可以迭代地相互促進(jìn);2) 與現(xiàn)有的不完整多視圖聚類(lèi)算法相比,該算法能夠靈活地處理具有任意視圖缺失模式的數(shù)據(jù),并利用生成模型和高階張量充分挖掘不同視圖之間的相關(guān)性;3) 利用增廣拉格朗日交替方向最小化(ALADM)方法對(duì)算法進(jìn)行了有效的優(yōu)化,并在不同的數(shù)據(jù)集上進(jìn)行了充分實(shí)驗(yàn).結(jié)果表明,在不同的缺失率下,該算法比現(xiàn)有算法具有更好的性能.

1 張量奇異值分解(t-SVD)及其核范數(shù)(t-TNN)

本文所使用的主要符號(hào)和定義.如表1 所示:

表1 符號(hào)與定義Table 1 Notations and definitions

為了引入t-SVD 和其產(chǎn)生的張量核范數(shù),本文首先介紹相關(guān)的張量操作.具體地,假設(shè)對(duì)于任意三階張量表示為B∈Rn1×n2×n3,則其塊循環(huán)矩陣可以表示為:

塊對(duì)角化矩陣及其逆過(guò)程可以定義為:

張量展開(kāi)unfold(·) 及其逆過(guò)程fold(·) 定義為:為了簡(jiǎn)明表示,相關(guān)定義如下:

定義 1.張量積 (t-product):張量B∈Rn1×n2×n3和C∈Rn2×n4×n3之間的張量積可以定義為S=B*C=fold{bcirc(B)unfold(C)}∈Rn1×n4×n3.

由于空間域的卷積運(yùn)算等于頻域的點(diǎn)積運(yùn)算,根據(jù)循環(huán)矩陣乘法(即循環(huán)卷積)的性質(zhì),自然可以利用快速傅立葉變換(FFT)來(lái)優(yōu)化張量積的運(yùn)算速度.

定義 2.正交張量 (Orthogonal tensor):張量Q∈Rn1×n1×n3是對(duì)角的,當(dāng)且僅當(dāng)

其中,I∈Rn1×n1×n3是單位張量,其滿足第一個(gè)正面的切片是n1×n1單位矩陣并且其他正面切片的元素全為0.(不失一般性,張量P∈Rn1×n2×n3的轉(zhuǎn)置為n2×n1×n3,其計(jì)算過(guò)程為先轉(zhuǎn)置P的每一個(gè)正面的切片,然后將第2 到n3的正面切片在張量中的順序顛倒).

定義 3.張量奇異值分解 (t-SVD)[26]:給定一個(gè)張量B∈Rn1×n2×n3,t-SVD 可以表示為B=U*S*VT,其中U∈Rn1×n1×n3,V∈Rn2×n2×n3均是對(duì)角的,S∈Rn1×n2×n3是f對(duì)角.其中,如果一個(gè)張量是f對(duì)角的,那么其每個(gè)正面切片都是對(duì)角的.

定義 4.張量多秩 (Tensor multi-rank):張量B∈Rn1×n2×n3的多秩是一個(gè)向量p,其第i個(gè)元素為Bf的第i正面切片的秩.

基于t-SVD 的張量核范數(shù)(t-TNN)定義為

其中Sf可以通過(guò)算法1 中的快速傅里葉變換獲得.張量多秩被證明是一種有效的范數(shù),是張量多秩的l1范數(shù)的最緊凸松弛[27-28].

2 生成式不完整多視圖聚類(lèi)模型

在本節(jié)中將首先引入生成模型來(lái)估算部分?jǐn)?shù)據(jù)的缺失視圖,然后在完整數(shù)據(jù)的基礎(chǔ)上進(jìn)一步引入多秩張量來(lái)建模不同視圖之間潛在的高階相關(guān)性.

所提算法是基于子空間聚類(lèi)的,對(duì)于高維數(shù)據(jù),由于它能夠恢復(fù)低維數(shù)據(jù)的子空間結(jié)構(gòu),因此非常有效.其基本假設(shè)是每個(gè)數(shù)據(jù)點(diǎn)可以通過(guò)所有數(shù)據(jù)點(diǎn)的線性組合來(lái)重建.它的工作原理是構(gòu)造一個(gè)關(guān)系矩陣來(lái)編碼數(shù)據(jù)的 “自表示”.給定從多個(gè)子空間(簇)采集的N個(gè)數(shù)據(jù)樣本X=[x1,···,xN]∈RD×N,子空間聚類(lèi)的形式可以表示為:

其中L(·,·) 和 Θ (·) 分別表示為數(shù)據(jù)重建損失和關(guān)系矩陣Z的正則項(xiàng),而λ是平衡這兩項(xiàng)的超參數(shù).在獲得自表示關(guān)系矩陣Z后,可以更進(jìn)一步得到用來(lái)做譜聚類(lèi)的相似度矩陣

2.1 多視圖生成模型

由于最大化似然函數(shù)等價(jià)于最小化損失 Δ,考慮到缺失的情況,可以獲得生成模型部分的以下目標(biāo)函數(shù):

其中本文使用了線性映射P(v)來(lái)表示轉(zhuǎn)換函數(shù).由于數(shù)據(jù)中可能存在噪聲.本方法引入了一個(gè)誤差項(xiàng)E1.然后將目標(biāo)函數(shù)轉(zhuǎn)換為:

2.2 總體目標(biāo)函數(shù)

實(shí)際上,應(yīng)該計(jì)算每個(gè)視圖中每個(gè)樣本對(duì)之間的相似性.然而,視圖不完整的情況導(dǎo)致無(wú)法計(jì)算完整的相似度矩陣.通過(guò)引入隱表示h,可以動(dòng)態(tài)生成缺失的視圖,從而使得每個(gè)樣本具有完整的視圖.相應(yīng)地,利用基于低秩張量約束的子空間聚類(lèi)來(lái)構(gòu)造樣本對(duì)之間的關(guān)系.相應(yīng)地,目標(biāo)函數(shù)如下:

2.3 優(yōu)化

模型的目標(biāo)函數(shù)中存在多個(gè)變量塊,無(wú)法保證對(duì)整體變量具有凸性,此處采用交替方向最小化策略[31],即通過(guò)固定其他變量來(lái)交替更新每個(gè)變量.因此,優(yōu)化可以分解為如下多個(gè)優(yōu)化子問(wèn)題:

H-子問(wèn)題:固定其他變量后,通過(guò)最小化以下目標(biāo)來(lái)更新H:

得到與H相關(guān)的導(dǎo)數(shù)并將其設(shè)置為零.可以使用以下規(guī)則更新H:

設(shè)Z(v)的目標(biāo)函數(shù)的導(dǎo)數(shù)為零,最終可以得到如下更新規(guī)則:

Xc-子問(wèn)題:變量Xc可以通過(guò)以下方式更新:

上面的子問(wèn)題可以用文獻(xiàn)[1]中的引理4.1 來(lái)解決.

G-子問(wèn)題:固定其他參數(shù),通過(guò)優(yōu)化如下目標(biāo)獲得更新:

進(jìn)一步,可轉(zhuǎn)化為以下優(yōu)化問(wèn)題

類(lèi)似于矩陣核范數(shù)[16],張量核范數(shù)可以基于t-SVD 分解實(shí)現(xiàn)優(yōu)化目標(biāo),細(xì)節(jié)見(jiàn)算法1.

更新乘子項(xiàng) 最后,根據(jù)LADMAP[31]算法更新各個(gè)乘子系數(shù)矩陣:

其中,maxμ和ρ分別對(duì)應(yīng)于乘子系數(shù)的上限和正系數(shù).

2.4 復(fù)雜度分析

所提算法由六個(gè)子問(wèn)題組成.完整的流程如算法2 所示.更新H的復(fù)雜度為O(v(k2d+kdn)+k3+k2n),其中v,n,d和k對(duì)應(yīng)視圖個(gè)數(shù),數(shù)據(jù)樣本數(shù)量,多視圖特征的平均維數(shù)和隱表示的維數(shù).對(duì)于更新P,主要的復(fù)雜度是矩陣乘法和隱表示矩陣求逆,其復(fù)雜度為 O (v(kdn+k2n+k3)).對(duì)于更新Z和Xc,主要的復(fù)雜度是矩陣求逆,即 O (v(n3)).對(duì)于更新E和乘子項(xiàng)系數(shù),主要復(fù)雜性是矩陣乘法,即 O (v(kdn+kn2)). 對(duì)于G子問(wèn)題,需要計(jì)算n×v×n張量的傅里葉變換和逆變換,及其頻域中n次n×v矩陣的SVD 分解,因此該問(wèn)題的復(fù)雜度為O(vn2log2(n)+v2n2).總體上,算法每次迭代更新的復(fù)雜度為O(v(k2d+kdn+k2n+k3+n3+kn2+n2log2n+vn2)).因?yàn)樵诙嘁晥D情況下,一般有n ?v,并且考慮譜聚類(lèi)復(fù)雜度以及迭代次數(shù)t,整體復(fù)雜度為 O (tv(n3+kdn+k2d+k3)).

3 實(shí)驗(yàn)

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

實(shí)驗(yàn)主要在如下四個(gè)真實(shí)數(shù)據(jù)上進(jìn)行:

1)Extended YaleB1http://cvc.yale.edu/projects/yalefacesB/yalefacesB.html.這個(gè)數(shù)據(jù)集由38 個(gè)人在不同光照下各64 張正面圖像構(gòu)成.與當(dāng)前相關(guān)方法[30]類(lèi)似,實(shí)驗(yàn)中使用前10 類(lèi) (每個(gè)人的所有圖像即為同一類(lèi)) 的圖像,從中提取3 種類(lèi)型的特征,即有640 個(gè)正面人臉圖像樣本的多視圖特征.

2)ORL2http://w.uk.research.att.com/facedatabase.html.ORL 人臉數(shù)據(jù)集包含40 個(gè)人的圖像,其中每個(gè)人有10 張不同的圖像.圖像在不同的時(shí)間、光照條件、面部表情狀態(tài)下拍攝,包括3 種特征.

3)COIL20MV3http://w.cs.columbia.edu/CAVE/software/softlib/.Columbia 對(duì)象圖像庫(kù)(COIL20MV)數(shù)據(jù)集包含20 個(gè)對(duì)象類(lèi)別,一共1 440張圖像,這些圖像與2 個(gè)視圖關(guān)聯(lián).每個(gè)類(lèi)別包含72 張圖像.所有圖像都被標(biāo)準(zhǔn)化為 3 2×32 像素陣列,每個(gè)像素具有256 灰度級(jí).

4)BBCSport4http://mlg.ucd.ie/datasets/.該數(shù)據(jù)集由544 篇對(duì)應(yīng)5 個(gè)主題的體育新聞文檔組成,其中提取了兩種不同類(lèi)型的特征.

在設(shè)置的實(shí)驗(yàn)中,對(duì)于圖像數(shù)據(jù)集,本文均提取圖像的如下三種特征:灰度強(qiáng)度、局部二值模式、Garbor 特征.圖像的強(qiáng)度特征表示單通道圖像像素的值.局部二值模式是描述圖像局部特征的算子,其具有灰度不變性和旋轉(zhuǎn)不變性等特點(diǎn).Gabor 特征可以用來(lái)描述圖像紋理信息特征.圖像的強(qiáng)度特征維度取決于圖像的大小,局部二值模式和Garbor 特征的維度分別為3 304 和6 750.對(duì)于文本數(shù)據(jù)集,每個(gè)文本被分為兩個(gè)部分,并且分別用TF-IDF歸一化方法提取相應(yīng)特征[32].

由于所有數(shù)據(jù)集最初都是完整的,因此,實(shí)驗(yàn)中采取隨機(jī)丟棄視圖的策略.本文缺失率定義為,其中指示第i個(gè)樣本的第v個(gè)視圖是否存在.在實(shí)驗(yàn)中,缺失率從10 %調(diào)整到50 %,步長(zhǎng)為10 %.為確保實(shí)驗(yàn)中樣本數(shù)目的穩(wěn)定性,在進(jìn)行隨機(jī)丟棄時(shí),保證每個(gè)樣本至少有一個(gè)視圖可用.

為了證明所提方法對(duì)于不完整多視圖數(shù)據(jù)是有效的,將該方法與幾種最新的方法進(jìn)行比較:聯(lián)合表示學(xué)習(xí)與聚類(lèi)(SRLC)[25],基于t-SVD 的多視圖子空間聚類(lèi)(t-SVD-MSC)[8],不完整多視圖聚類(lèi)(PVC)[23],不完整多模態(tài)分組(IMG)[24],多個(gè)不完整視圖聚類(lèi)(MIC)[33],雙對(duì)齊不完整多視圖聚類(lèi)(DAIMC)[34].由于t-SVD-MSC[8]方法不能處理不完整多視圖數(shù)據(jù)集,因此在預(yù)處理階段用該視圖的平均值填充缺失的視圖.為了保證實(shí)驗(yàn)對(duì)比的公平性,實(shí)驗(yàn)中使用網(wǎng)格搜索方法來(lái)調(diào)整超參數(shù),并使用ACC 和NMI 聚類(lèi)度量來(lái)評(píng)估不同方法的性能在每一個(gè)數(shù)據(jù)集上,分別對(duì)每種方法的不同缺失率重復(fù)10 次實(shí)驗(yàn),得到其平均性能作為評(píng)價(jià).

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

圖2 顯示了在不同的缺失率下,不同方法在四個(gè)數(shù)據(jù)集上的聚類(lèi)性能.結(jié)果表明:1)隨著缺失率的增加,各種方法的性能都有一定程度的下降.2)在ORL 和BBCsport 數(shù)據(jù)集上,t-SVD-MSC方法表現(xiàn)出比其他方法更好的性能,表明了低秩約束的有效性,并且可以有效地探索數(shù)據(jù)的簇結(jié)構(gòu).在另外兩個(gè)數(shù)據(jù)集上,所提方法的實(shí)驗(yàn)結(jié)果明顯優(yōu)于平均插值的t-SVD-MSC 方法.這是因?yàn)樵谒崮Ｐ椭?數(shù)據(jù)插補(bǔ)和聚類(lèi)可以迭代地相互改進(jìn).3) 缺失率在10 %到50 %之間變化過(guò)程中,所提出的方法始終優(yōu)于其他比較方法.特別是對(duì)于YaleB 和COIL20MV 數(shù)據(jù)集,所提方法比其他方法有顯著的效果提升.這是因?yàn)樗崮Ｐ涂梢岳蒙赡Ｐ秃透唠A張量有效地挖掘不同視圖之間的相關(guān)性,以保證聚類(lèi)的性能.

圖2 在四個(gè)數(shù)據(jù)集上不同缺失率的準(zhǔn)確度(ACC)和歸一化互信息(NMI) (平均值 ± 標(biāo)準(zhǔn)差)Fig.2 Results (mean ± std) in terms of accuracy and NMI on four datasets with different missing rate

3.3 模型分析

超參數(shù)選擇.在實(shí)驗(yàn)中,將H的維數(shù)設(shè)為100,并且提出的模型有兩個(gè)超參數(shù)需要調(diào)整λ1和λ2.H的維度是從特定的范圍{ 100,200,400,800} 中選擇的.在所提的方法中,λ1和λ2是從{10-2,10-1,100,101,102,103}中選擇的兩個(gè)折衷參數(shù).圖3 (a)顯示了這兩個(gè)超參數(shù)對(duì)YaleB 的影響.

收斂性分析.圖3 (b)顯示了收斂曲線和聚類(lèi)性能曲線.可以看出,在有限的迭代次數(shù)內(nèi),收斂曲線下降較快,聚類(lèi)性能曲線上升較快,證明了所設(shè)計(jì)的優(yōu)化方法可以在一定的迭代次數(shù)下收斂.

圖3 YaleB 數(shù)據(jù)集上缺失率為10 %時(shí)的模型分析:(a) 參數(shù)調(diào)整對(duì)NMI 指標(biāo)的影響;(b)迭代過(guò)程中的收斂條件數(shù)值和聚類(lèi)指數(shù)曲線(收斂條件數(shù)值已歸一化)Fig.3 Model analysis on YaleB with missing rate:10 %:(a) Performence with parameter tuning;(b) Convergence and clustering index curves during iteration (convergence values are normlized)

4 結(jié)論

本文提出了一種新穎的不完整多視圖聚類(lèi)模型(GM-PMVC),可以在任意視圖缺失的情況下補(bǔ)全缺失并完成子空間聚類(lèi).通過(guò)隱表示H有效利用所有可用視圖信息,有效地編碼基于子空間聚類(lèi)的多視圖互補(bǔ)性(即每一個(gè)單一視圖都來(lái)自于完整的隱空間).在融合多視圖信息的同時(shí),將各個(gè)視圖的關(guān)系矩陣拼接為三階張量.由于高階張量的低秩約束能有效挖掘數(shù)據(jù)之間的高階相關(guān)性,具體地,基于三階張量的奇異值分解(t-SVD) (如算法1 所示)的低秩約束既能挖掘各個(gè)視圖內(nèi)的低維子空間結(jié)構(gòu),又能同時(shí)保證各個(gè)視圖關(guān)系矩陣之間的一致性.視圖的缺失能通過(guò)隱表示H補(bǔ)全缺失信息,所提框架同時(shí)補(bǔ)全缺失視圖和挖掘多視圖的高階相關(guān)性,兩者相互促進(jìn),從而提高聚類(lèi)效果.由于該框架涉及多個(gè)優(yōu)化變量,本文所使用的增廣拉格朗日交替方向最小化(AL-ADM)方法能有效優(yōu)化含復(fù)雜約束項(xiàng)的目標(biāo)函數(shù),實(shí)驗(yàn)證明經(jīng)過(guò)少量迭代次數(shù)即能收斂.所提模型具有相對(duì)較高的時(shí)間復(fù)雜度(如表2所示),因此模型在優(yōu)化效率方面還具有改進(jìn)空間.本方法在基準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果與現(xiàn)有的不完整多視圖聚類(lèi)方法相比,驗(yàn)證了GM-PMVC 的有效性,并且在多數(shù)驗(yàn)證數(shù)據(jù)上具有顯著的效果提升.

表2 算法運(yùn)行時(shí)間對(duì)比(秒)Table 2 Algorithm running time comparison (s)