基于一步張量學習的多視圖子空間聚類

趙曉佳 徐婷婷 陳勇勇 徐 勇,2

人類借助于日漸先進的數據收集和信息技術,在不同領域中獲取到不同類型的多數圖數據,更加全面地挖掘出隱藏在數據中特征和結構信息[1-2].如圖1(a) 視頻監控通過采集不同時態下的圖像,更加有助于理解行人的姿態、面部表情等行為動作;圖1(b)采集不同視角下的汽車圖片,有助于更加清晰地刻畫車輛的全貌;圖1(c) 表示的是一張人臉圖像在Local Binary Pattern[3]、Gabor[4]、Histogram of Oriented Gradients[5]等描述下的特征表示.多視圖數據可以反映出更加全面的信息,結合不同的應用場景,衍生出多種多視圖學習應用,如多視圖聚類[2,6-9],多視圖半監督分類[10],多視圖分類[11],多視圖檢索[12]等等.由于現實生活中的數據大多沒有樣本標簽并且標簽信息的獲取十分復雜,在進行基于標簽的分類操作時會耗費很大的人力、物力.另一方面,隨著聚類算法的成熟,一些聚類算法[13-14]的性能逐漸逼近分類算法,多視圖聚類引起了廣泛關注.

圖1 多視圖數據示例Fig.1 Examples of multi-view data

現有的單視圖聚類和多視圖聚類算法的性能高度依賴于親和度矩陣的質量,其核心是構造一個具有判別性的親和度矩陣.對親和度矩陣求解的方法大致劃分為三大類,分別是基于圖[15-16]、基于核[17-18]和基于子空間[7,19-23]的方法.例如,Liang 等[15]提出了同時對視圖間的一致性和差異性進行建模的圖聚類方法;Wang 等[16]提出了同時學習數據相似度矩陣和聚類結構的聚類方法.然而基于圖的聚類方法是根據原始數據的特征直接進行圖的構建,容易受到噪聲和異常值影響.為了處理非線性復雜數據的聚類問題,文獻[17]通過使用核技巧將稀疏子空間聚類擴展到非線性流形;Yin 等[18]將對稱正定矩陣嵌入到再生核希爾伯特空間中,有效地揭示了潛在的子空間結構.但是基于核的聚類方法的性能在很大程度上依賴于核函數的選擇,而在實踐中如何選擇核函數仍是一個待探索的問題.為了提升魯棒性,子空間聚類方法利用獨立的兩步驟去學習親和度矩陣,即1) 根據原始數據的特征矩陣對其進行自表示,利用特定正則項求得自表示矩陣;2) 通過自表示矩陣固定得到親和度矩陣,來描述未標記數據點之間的成對關系.例如,稀疏子空間聚類 (Sparse subspace clustering,SSC)[22]和低秩表示(Lowrank representation,LRR)[21]是兩種最具代表性的子空間聚類算法.他們分別利用l1范數和核范數得到了稀疏和低秩的自表示矩陣.Gao 等[24]采用譜聚類的方式整合不同視圖的子空間聚類結果以獲得一致性的指示矩陣.

為了挖掘多視圖特征的高階相關性,Zhang 等[6]和Xie 等[7]相繼提出將所有視圖的自表示矩陣拼接成一個三階張量,即包含了二維點對點的維度,同時囊括了一個新的視圖維度.Chen 等[25],Zhang等[26]和Wu 等[27]均采用張量這一數據結構來處理多視圖聚類的問題,并利用聯合學習和張量低秩優化的思想以學習一個更具辨別性的親和度矩陣.此類方法的核心是低秩張量分解技術.現有常見的張量分解技術為CANDECOMP/PARAFAC分解[28]、Tucker 分解[29]、張量奇異值分解(Tensor singular value decomposition,t-SVD)[30].其中基于t-SVD的張量核范數是張量多秩l1范數的最緊凸松弛,在低秩近似理論與應用中取得了優異性能.文獻[2]采用基于t-SVD 的張量多秩最小化方法,隱式地過濾掉高維噪聲.文獻[31]采用了自適應近鄰的方法,為每個數據點分配最佳近鄰來學習相似性矩陣,以捕獲數據的局部特征.但這些方法都基于根據某種運算,如指數法[32]、絕對對稱化[6]、平方運算[33]等,利用自表示矩陣固定求解親和度矩陣,即兩者的求解過程獨立進行,無法有效地挖掘兩者間的高度相關性,不能獲取更優的親和度矩陣.

為了解決上述問題,本文提出了一種新穎的基于一步張量學習的多視圖子空間聚類算法,它可以有效地降低噪聲和異常值的影響并探究親和度矩陣和表示張量之間的高度相關性,以獲得更優的親和度矩陣,進而得到更優的多視圖聚類性能.本文的貢獻總結如下:1) 針對多視圖聚類問題,提出了一種基于一步張量學習的多視圖子空間聚類算法,該算法通過學習一個魯棒的低秩張量表示進行聚類,充分挖掘了數據的多模態信息,具有較高的魯棒性與準確率.2) 與現有多視圖聚類算法相比,該算法在一個統一框架下對表示張量與親和度矩陣進行聯合學習,相互促進.利用t-SVD 對表示張量進行高階約束,減少噪聲和異常值的影響.并采用自適應近鄰法重建親和度矩陣,以獲得更加靈活的圖用于多視圖聚類.3) 該算法采用交替方向乘子法進行有效優化.在多個數據集上驗證了所提出方法在解決多視圖聚類問題上的優越性.

1 多視圖聚類相關概述

本節包括親和度矩陣學習、低秩張量表示的多視圖聚類和張量奇異值分解三個部分.在表1 中總結了本文所使用的主要符號和定義.

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

1.1 親和度矩陣學習

多視圖子空間聚類方法的核心是求解一個具有較強辨別能力的親和度矩陣,以更好地捕獲多視圖數據間的一致性與差異性[1].基于自表示的子空間聚類方法憑借其出色的性能,成為該研究領域的熱門方向[21-22],其優化模型依賴于自表示特性,即屬于同一線性子空間的樣本可以相互線性表示[34].數據集X=[x1,···,xn] 表示維度為d的n個原始樣本點,其自表示學習模型如下:

基于圖學習的多視圖聚類方法往往利用原始數據學習親和度矩陣.即將數據點作為構建的圖節點,它們之間的邊代表兩者之間的相似性[38],其基本模型如下:

其中,aij表示親和度矩陣A中第 (i,j) 個元素,若數據點xi與xj的的距離越小,則aij的數值越大,兩者的相似性也就越高.大量的文獻[2,15-16]借助圖學習的思想,大大提高了聚類性能.

1.2 低秩張量表示的多視圖聚類

多視圖聚類中,假設有由V個視圖構成的多視圖數據其中第v個視圖的特征維度為dv.考慮到使用三維的表示張量可更好的探索不同視圖的一致性與差異性,Zhang 等[6]和Xie等[7]提出了基于低秩張量表示的多視圖子空間聚類模型:

Φ(·) 將所有視圖的表示矩陣作為正面切片豎向合并為一個三階表示張量Z∈Rn×n×V.由于不同視圖的特征維度可能不同,但是樣本數目為固定值,所以將特定于視圖的誤差矩陣進行垂直連接,以構造誤差矩陣E.使用張量表示相當于在保持矩陣表示的基礎上增添了不同視圖間關系的新維度,進而可以探索多視圖中更加全面的內部信息.

1.3 張量奇異值分解

圖2 張量奇異值分解示例Fig.2 Examples of t-SVD

2 基于一步張量學習的多視圖子空間聚類

本文提出了基于一步張量學習的多視圖子空間聚類方法(One-step tensor learning for multi-view subspace clustering,OTSC),其框架結構如圖3 所示.OTSC 利用張量將不同視圖的特征自表示信息進行統一建模,并使用t-SVD 對其進行低秩表示.采用自適應近鄰方法進行重建親和度矩陣,聯合學習親和度矩陣A與‘干凈’的表示張量Z,其優化過程借助乘法器交替方向法.

圖3 基于一步張量學習的多視圖子空間聚類結構圖Fig.3 The framework of the one-step tensor learning for multi-view subspace clustering (OTSC)

2.1 OTSC 模型框架

大量子空間聚類方法[14,26,35,39]中親和度矩陣的學習往往脫離原始數據的特征信息進行分步求解,使得聚類結果只能達到次優解.在處理多視圖聚類問題時,常采用基于多個特定于視圖的表示矩陣尋求一個一致性的表示矩陣的方法[14,16,40],忽視了視圖間的高階信息.為解決以上問題,本方法采用基于圖學習的聚類方法,利用張量將樣本間的關系拓展到視圖間的高階關系,并充分挖掘親和度矩陣與多視圖原始數據之間的密切聯系,來獲取一個更具辨別能力的親和度矩陣.由于原始數據易被噪聲和異常值破壞[41],故對表示張量進行t-SVD 以獲得一個去除噪聲和異常值的‘干凈’張量,并與親和度矩陣進行聯合學習.基于以上思想,將圖學習模型(2)拓展到具有V個視圖的多視圖數據中,可得:

多視圖聚類的本質是根據樣本的相似度信息,將樣本劃分到不同的簇中[43].為了提高聚類算法的性能,獲得一個更具區分性的親和度矩陣,采用自適應近鄰方法,以確保簇內樣本點的相似性高,簇間差異性大的特性.基于自適應近鄰的方法僅保留ai中數值最大的前K項[31],其余元素aij(j ＞k) 置為0,可保證同類中的樣本點的相似度系數大于簇間的相似度系數.參數β的值由自適應近鄰數目即K值決定,詳見第2.2 節優化過程式(20b).

2.2 模型優化

對目標式(6)進行優化求解的過程,涉及多個變量求解的問題,為此采用交替方向乘子法對式(6) 進行優化.式(6)中變量Z與目標函數和兩個約束條件耦合,增加了計算難度,為此引入一個輔助變量Y使其解耦為:

針對上式,構建增廣拉格朗日函數,獲得無約束目標函數計算公式如下:

借助增廣拉格朗日公式將式(7)中的約束條件轉換為式(8) 最小化問題.其中〈·,·〉代表矩陣的內積運算; Θ,Π和ρ分別表示拉格朗日乘子與懲罰參數.

對式(8)通過固定其他變量來交替求解各變量優化的子問題,以求得最優解.優化過程中首先通過t-SVD 學習更新變量Z,其次更新輔助變量Y;之后對噪聲矩陣E和親和度矩陣A同時更新;最后更新兩個拉格朗日乘子 Θ,Π和懲罰參數ρ.詳細子問題優化過程如下:

1)更新Z:固定式(8)中與Z無關變量,對Z第t+1 次迭代的優化問題可化為:

由于不同視圖之間互不干擾,故上式中變量Yv是相互獨立的,因此將上式等價轉換為V個子問題,其中第v個視圖的變量更新問題可寫為:

式(11)對Yv是凸函數,因此對上式求關于Yv的導數并使其為0,求得Yv的如下封閉解:

親和度矩陣反應了樣本之間的相似性關系,直接決定了一個聚類算法的性能好壞.為了獲得更靈活的相似度矩陣,確保類內樣本點的相似度高于類間樣本點的相似度,對其應用自適應近鄰方法,僅保留A中前K項最大值的ai,以提高聚類的性能,如下式所示:

由上式可知,在式(6)中的參數β是由自適應近鄰的數量K所決定.這意味著僅需在在式(6)中預先定義參數α,γ和近鄰數量K即可進行算法的優化工作.

5)更新 Θ,Π和ρ:在 (t+1) 次迭代過程中,拉普拉斯乘子 Θ,Π和懲罰參數ρ的更新方式如下:

其中λ＞1,ρmax代表ρ的最大值.本方法可總結為算法1,通過對式(6)的優化,獲得親和度矩陣A的最優解,之后在A上應用譜聚類算法,得到最終的聚類結果.

算法 1.OTSC 多視圖子空間聚類的優化算法

2.3 時間復雜度分析

3 實驗結果與分析

3.1 實驗設計

數據集:為了驗證算法的有效性, 在六個分別隸屬于面部圖像、新聞故事、手寫數字和通用對象場景四種不同類別廣泛使用的數據集上進行實驗.

1) Extended YaleB:該數據集由耶魯大學發布, 包含38 個人類對象在不同光線強度下的各64張圖像. 在本實驗中根據文獻[6]只對前10 個不同對象進行驗證, 構成了包含640 張面部圖片的數據.

2) ORL:ORL 人臉數據集是由英國劍橋Olivetti 實驗室所創建. 包含40 個人在不同的時間、光照、面部表情(睜眼/閉眼, 微笑/不微笑)和面部細節(戴眼鏡/不戴眼鏡)環境下采集的400 張圖像.Extended YaleB 與ORL 數據集都屬于面部圖像類別, 對二者分別提取強度、LBP[3]和Gabor[4]三種特征作為多視圖數據的不同視圖.

3) 3Sources:該數據集是從BBC、路透社和衛報三種在線新聞收集的多視圖文本數據集, 涵蓋416 條不同的新聞報道. 數據集來自六類主題標簽:商業、娛樂、健康、政治、體育、技術, 是具有三種特征的多視圖數據.

4) BBCSport:屬于新聞故事類數據集, 來自2004-2005 年BBC Sport 網站的五個主題領域的體育新聞文章, 常用作機器學習研究的基準. BBCSport 包含具有兩種不同類型特征的544 個文檔,構成V=2 的多視圖數據.

5) UCI-Digits:數據集包含從荷蘭公用事業地圖集合中提取的手寫數字(0 ～9)共10 類阿拉伯數字, 每類有200 張圖像. 依據[16]提取了該數據集傅里葉系數、像素平均和形態特征三個特征作為多視圖數據.

6) COIL-20:該數據集由哥倫比亞大學圖像庫發布. 含有20 個不同物體在360° 旋轉中不同角度的各72 張成像. 與ExtendedYaleB、ORL 數據集相同采用1 024 維強度、3 304 維LBP、6 750 維Gabor 三個視圖特征.

表2 詳細總結了上述六個數據集的信息.

表 2 真實多視圖數據集信息Table 2 Summary of all real-world multi-view databases

對比算法:本文提出的方法與以下12 種最先進聚類方法進行對比, 其中包括3 種單視圖聚類(SVC)和9 種多視圖聚類(MVC)方法. 為了和SVC方法進行對比, 在多視圖數據的每個視圖上分別采取SSC[22]、LRR[21]、RSS[42]三種單視圖聚類方法, 并選取最好的聚類結果; 11 種流行的MVC 方法, 包括低秩和稀疏分解(RMSC)[40]、多樣性誘導多視圖子空間聚類(DiMSC)[44]、低秩張量約束的多視圖子空間聚類(LT-MSC)[6]、自動權重的多視圖學習(MLAN)[45]、多視圖張量多秩最小化(t-SVD)[7]、基于圖的多視圖聚類(GMC)[16]、潛在的多視圖子空間聚類(LMSC)[46]、張量積表示(SCMV-3DT)[39]、多視圖子空間聚類中的低階張量圖學習(LRTG)[41]、加權張量核范數最小化(WTNNM)[47]和圖正則化的張量和親和度矩陣低秩表示的子空間聚類(GLTA)[25].

參數設置:模型中有四個參數α,β,γ與K, 其中α,β,γ分別表示局部流形、親和度矩陣正則化項和噪聲在模型中的貢獻度,K為自適應近鄰數目.由于式(6)中參數β可由參數α與K通過式(20b)求解得出, 因此模型中只需對參數α,γ,K進行參數選擇. 實驗中, 依據經驗對參數α和γ從集合[0.001、0.005、0.01、0.05、0.1、0.2、0.4、0.5、1、2、5、10、50、100、500]中選擇,K從[5, 15]的區間選擇以尋求最優的聚類性能. 具體的, 針對七個多視圖數據集的參數設置如表3 所示. 在對比實驗中, 本文遵從對比算法相應文章中的參數設定, 對每個算法進行了10 次測試, 并記錄了最優的參數下的平均結果和標準偏差.

表3 參數設置Table 3 Parameter setting

評估指標:為了全面地驗證本算法的性能, 采用準確性(ACC)、標準化互信息(NMI)、調整后的等級指數(AR)、F 分數、精確度和召回率六個流行的指標來評估聚類性能. 不同的指標側重于聚類不同的屬性, 但都滿足其值越高, 聚類性能越好的特性. ACC 是評估聚類任務的常用度量指標, 定義為:

上式中,Li,Yi分別表示第i個樣本的聚類標簽和真實標簽,δ((map(Li)=Yi) 表示正確聚類樣本的個數.NMI 的具體數學定義為:

其中,H(·) 表示熵,I(·) 表示互信息,可表示為:I(L,Y)=H(L)+H(Y)-H(L,Y) 反應了L與Y之間的相關程度.AR、F 分數、精確度和召回率將聚類視為一系列決策,其相關定義的更多細節可參考文獻[7].

3.2 實驗結果

受文獻[47]的啟發,本文也考慮了利用加權張量核范數進行張量低秩優化,并用WOTSC 表示.實驗結果如表4～表6 所示,加粗數字表示最優聚類結果,下劃線的數據表示次優結果.通過觀察實驗結果,可以得出以下結論:1) 本文提出的OTSC及WOTSC 在大多數情形下都取得了最優值,或者次優解,彰顯了本算法優異的聚類性能.2) 通過比較SVC和MVC 的聚類結果,可知大多數MVC 算法的性能高于SVC 的聚類結果,直接地展現出多視圖聚類的優勢.例如,在Extended YaleB 數據集上,WOTSC 比SVC 最優的RSS 算法的聚類性能在六個指標上分別提高了23.0%、15.6%、25.3%、22.7%、23.8%和21.6%.3) 與LRTG 方法進行對比,本方法在所有數據集上的聚類效果都優于LRTG.這是由于所提方法是通過t-SVD 對數據特征的表示張量進行低秩約束,以去除高維噪聲和異常值.相比于塔克分解,t-SVD 更具魯棒性與高效性.4) RMSC、LT-MSC、LMSC和t-SVD 都是基于低秩表示的多視圖聚類方法,通過獨立的兩步求解親和度矩陣,即親和度矩陣的計算與表示張量的求解分步進行.通過與以上算法的對比,可得本文提出的方法通過聯合學習表示張量和親和度矩陣,可以更好地捕獲數據中的底層低維結構.

表4 數據集Extended YaleB、ORL 的聚類結果Table 4 Clustering results (mean ± standard deviation) on Extended YaleB and ORL

表5 數據集3Sources、UCI-Digits 的聚類結果Table 5 Clustering results (mean ± standard deviation) on 3Sources and UCI-Digits

表6 數據集BBCSport、COIL-20 的聚類結果Table 6 Clustering results (mean ± standard deviation) on BBCSport and COIL-20

3.3 模型分析

消融實驗:為了探究聯合優化模塊對本算法的性能影響,探索‘一步化’學習表示張量與親和度矩陣的有效性,本節對該模塊進行消融測試.分別在Extended YaleB、COIL-20、3Sources、UCI-Digits 四個數據集上進行實驗,OTSCA和OTSCZ分別表示依據經過聯合優化的親和度矩陣、表示張量以進行聚類的方法.實驗結果如圖4 所示,可觀測出,OTSCA的ACC與NMI的值都高于OTSCZ,其中在Extended YaleB 數據集上尤為明顯,彰顯了聯合優化模塊的高效性與探索親和度矩陣與表示張量的高階相關性的積極作用.參數選擇:為了驗證參數選擇對OTSC 模型的影響,本文在ORL 數據集上進行了參數α和γ在[0.001、0.005、0.01、0.05、0.1、0.2、0.4、0.5、1、2、5、10、50、100、500]的集合上遍歷的實驗.結果如圖5 所示,可看出本算法在該數據集上當γ取自區間[0.05,0.5],α取自區間[0.00,1]時,有較好的性能 (ACC和NMI取得較高的值).此外,本節還探索了參數自適應近鄰數目K對聚類結果準確率的影響.結果如圖6 所示,顯示出ORL 數據集在參數K取值由5 到9 時ACC為遞增變化,并在K=9 時取得最大值.

圖4 OTSC 性能的消融實驗Fig.4 Ablation experiment of OTSC performance

圖5 根據 A CC和 N MI 調整數據集ORL 參數 α 與γFig.5 Parameters tuning in terms of A CC and N MI on ORL

圖6 參數 K 對數據集ORL 的 A CC 影響Fig.6 The effect of parameter K on the A CC of ORL.

3.4 模型收斂性

本算法采用交替方向乘子法進行多個變量的更新,具有較快的收斂速度.圖7 顯示了OTSC 在數據集BBCSport、ExtendedYaleB 上準確率、停止標準與迭代次數的關系.可觀測出,算法的殘差在5 次迭代后趨于穩定,并且準確率也達到峰值而趨于穩定,都反應出本模型的優化算法的高效收斂性.

圖7 收斂性曲線 ((a) BBCSport;(b) Extended YaleB)Fig.7 The convergence curves and ACC versus iterations on ((a) BBCSport;(b) Extended YaleB)

4 結論

針對多視圖聚類兩步化求解親和度矩陣、如何探索多視圖之間的高階相關性的問題,本文提出了一種基于一步張量學習的多視圖子空間聚類方法.本方法借助圖學習的思想,利用張量三維數據結構的屬性來充分挖掘多視圖數據的底層低維結構.具體地,本算法將特定于視圖的表示矩陣拼接為三維張量以探索數據間高階相關性,并采用t-SVD(如式(4)所示)低秩約束以尋求一個‘干凈’的表示張量.通過引入‘一步化’聯合學習框架,有效地實現表示張量和親和度矩陣的共同優化,克服了對親和度矩陣固定求解的問題.此外,還采用自適應最近鄰方案,共同學習一個魯棒的低秩張量圖.由于該算法涉及多個優化變量,故采取交替方向乘子法進行交替優化.在六個多視圖數據集上的實驗表明本方法的有效性和魯棒性.在后續工作中,考慮將‘一步化’聯合求解的方法拓展到深度學習中,借助卷積神經網絡來學習更具判別性的親和度矩陣.