生成式不完整多視圖數據聚類

趙博宇 張長青 , 陳 蕾 ,3 劉新旺 李澤超 胡清華

在實際應用中,數據通常從不同的角度采集,稱為多視圖數據[1-2].多視圖學習研究[2-7]表明,有效利用不同視圖之間的一致性和互補性可以顯著提高任務(如多視圖聚類/分類)性能.在聚類方面,已有大量的研究將單視圖聚類擴展到多視圖聚類.在這些方法中,基于自表示的多視圖子空間聚類[8-12]方法通過可學習的關系矩陣處理復雜的高維數據,取得了顯著效果.最近,一些相關研究[13-15]將譜聚類和自表示關系圖聯合優化,進一步提高多視圖融合效果.

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

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

圖1 同時用 P (X|H) 對隱空間 H 進行建模,并基于隱表示生成完整特征.根據完整的數據,GM-PMVC 將子空間表示集成到一個張量中,可以挖掘多視圖數據高階相關性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

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

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

本文所使用的主要符號和定義.如表1 所示:

表1 符號與定義Table 1 Notations and definitions

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

塊對角化矩陣及其逆過程可以定義為:

張量展開unfold(·) 及其逆過程fold(·) 定義為:為了簡明表示,相關定義如下:

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

由于空間域的卷積運算等于頻域的點積運算,根據循環矩陣乘法(即循環卷積)的性質,自然可以利用快速傅立葉變換(FFT)來優化張量積的運算速度.

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

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

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

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

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

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

2 生成式不完整多視圖聚類模型

在本節中將首先引入生成模型來估算部分數據的缺失視圖,然后在完整數據的基礎上進一步引入多秩張量來建模不同視圖之間潛在的高階相關性.

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

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

2.1 多視圖生成模型

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

其中本文使用了線性映射P(v)來表示轉換函數.由于數據中可能存在噪聲.本方法引入了一個誤差項E1.然后將目標函數轉換為:

2.2 總體目標函數

實際上,應該計算每個視圖中每個樣本對之間的相似性.然而,視圖不完整的情況導致無法計算完整的相似度矩陣.通過引入隱表示h,可以動態生成缺失的視圖,從而使得每個樣本具有完整的視圖.相應地,利用基于低秩張量約束的子空間聚類來構造樣本對之間的關系.相應地,目標函數如下:

2.3 優化

模型的目標函數中存在多個變量塊,無法保證對整體變量具有凸性,此處采用交替方向最小化策略[31],即通過固定其他變量來交替更新每個變量.因此,優化可以分解為如下多個優化子問題:

H-子問題:固定其他變量后,通過最小化以下目標來更新H:

得到與H相關的導數并將其設置為零.可以使用以下規則更新H:

設Z(v)的目標函數的導數為零,最終可以得到如下更新規則:

Xc-子問題:變量Xc可以通過以下方式更新:

上面的子問題可以用文獻[1]中的引理4.1 來解決.

G-子問題:固定其他參數,通過優化如下目標獲得更新:

進一步,可轉化為以下優化問題

類似于矩陣核范數[16],張量核范數可以基于t-SVD 分解實現優化目標,細節見算法1.

更新乘子項 最后,根據LADMAP[31]算法更新各個乘子系數矩陣:

其中,maxμ和ρ分別對應于乘子系數的上限和正系數.

2.4 復雜度分析

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

3 實驗

3.1 實驗設置

實驗主要在如下四個真實數據上進行:

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

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

3)COIL20MV3http://w.cs.columbia.edu/CAVE/software/softlib/.Columbia 對象圖像庫(COIL20MV)數據集包含20 個對象類別,一共1 440張圖像,這些圖像與2 個視圖關聯.每個類別包含72 張圖像.所有圖像都被標準化為 3 2×32 像素陣列,每個像素具有256 灰度級.

4)BBCSport4http://mlg.ucd.ie/datasets/.該數據集由544 篇對應5 個主題的體育新聞文檔組成,其中提取了兩種不同類型的特征.

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

由于所有數據集最初都是完整的,因此,實驗中采取隨機丟棄視圖的策略.本文缺失率定義為,其中指示第i個樣本的第v個視圖是否存在.在實驗中,缺失率從10 %調整到50 %,步長為10 %.為確保實驗中樣本數目的穩定性,在進行隨機丟棄時,保證每個樣本至少有一個視圖可用.

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

3.2 實驗結果

圖2 顯示了在不同的缺失率下,不同方法在四個數據集上的聚類性能.結果表明:1)隨著缺失率的增加,各種方法的性能都有一定程度的下降.2)在ORL 和BBCsport 數據集上,t-SVD-MSC方法表現出比其他方法更好的性能,表明了低秩約束的有效性,并且可以有效地探索數據的簇結構.在另外兩個數據集上,所提方法的實驗結果明顯優于平均插值的t-SVD-MSC 方法.這是因為在所提模型中,數據插補和聚類可以迭代地相互改進.3) 缺失率在10 %到50 %之間變化過程中,所提出的方法始終優于其他比較方法.特別是對于YaleB 和COIL20MV 數據集,所提方法比其他方法有顯著的效果提升.這是因為所提模型可以利用生成模型和高階張量有效地挖掘不同視圖之間的相關性,以保證聚類的性能.

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

3.3 模型分析

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

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

圖3 YaleB 數據集上缺失率為10 %時的模型分析:(a) 參數調整對NMI 指標的影響;(b)迭代過程中的收斂條件數值和聚類指數曲線(收斂條件數值已歸一化)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 結論

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

表2 算法運行時間對比(秒)Table 2 Algorithm running time comparison (s)