余 瑤，杜世強，宋金梅

1.西北民族大學 數(shù)學與計算機科學學院，蘭州 730030

2.西北民族大學 中國民族信息技術研究院，蘭州 730030

聚類是計算機視覺、機器學習和數(shù)據(jù)挖掘領域中最基本的任務之一，旨在沒有先驗信息，不需要訓練的情況下，將無標簽數(shù)據(jù)根據(jù)樣本相似性合理的劃分為不同的子集，每個子集可稱為一個簇。由于大數(shù)據(jù)背景下，獲取有標簽數(shù)據(jù)是一個耗時耗力成本高昂的工作，所以聚類作為一種重要的無監(jiān)督學習方法變得非常重要。在過去的幾十年里，各種各樣的聚類方法相繼被提出，K-means[1]是最常用的聚類方法，目的是學到一個聚類中心，使得簇內的數(shù)據(jù)距中心較近；標準譜聚類（SPC）[2]首先根據(jù)樣本之間的相似度構造一個相似矩陣，然后建立一個無向加權圖，最后利用圖拉普拉斯算子的性質學習相似矩陣。現(xiàn)有的大多數(shù)聚類算法來源于SPC，其中最重要的一步是構造數(shù)據(jù)點間的相似度矩陣，根據(jù)構造方式的不同，基于SPC 的聚類方法主要分為兩類，包括基于自表示的子空間聚類方法[3-4]和基于圖的聚類方法。

基于自表示的方法是將樣本點表示為同一子空間內其他點的線性組合，然后通過系數(shù)矩陣構造相似度矩陣。文獻[5]提出低秩子空間聚類（LRR），在自表示矩陣上施加低秩約束來捕獲全局結構，但聚類的精度需要在子空間獨立并且數(shù)據(jù)充足的情況下才能保證，這種假設條件對于現(xiàn)實數(shù)據(jù)集來說過于嚴苛。文獻[6]等放寬約束條件，引入稀疏性準則提出了稀疏子空間聚類（SSC）算法，將每個數(shù)據(jù)點表示為其他數(shù)據(jù)點的稀疏線性組合來捕獲數(shù)據(jù)的局部結構。文獻[7]利用低秩和稀疏約束的互補度量子空間聚類里的自表示系數(shù)，用得到的系數(shù)矩陣來計算相似度矩陣進而執(zhí)行譜聚類得到最終結果?；趫D的聚類方法重點是如何學習到一個高質量的圖，然后在該圖上使用譜聚類算法來獲得最終結果。文獻[8]提出一種魯棒圖學習（RGC）算法，自適應的去除原始數(shù)據(jù)中的噪聲，從真實數(shù)據(jù)中學習精確的圖。

另外，現(xiàn)實世界中充滿著各種復雜多樣的數(shù)據(jù)，獲取數(shù)據(jù)的來源也各不相同。例如，一個客觀對象可以由文字、圖像、音頻或視頻來描述。多視圖信息的充分利用更能夠提升聚類性能，因此許多多視圖聚類方法從這些流行的單視圖方法中衍生出來。多視圖子空間學習方法主要基于自表示來探索樣本之間的關系，文獻[9]提出了多視圖子空間聚類（MVSC）方法，對每個視圖的系數(shù)矩陣進行譜聚類以獲得不同視圖間共同的聚類結構。文獻[10]利用系數(shù)矩陣的稀疏性和不同視圖間的互補信息提出了排他性一致性多視圖子空間聚類。文獻[11]將低秩稀疏子空間聚類（LRSSC）[4]算法拓展到多視圖領域提出了多視圖低秩稀疏子空間聚類算法（MLRSSC），不僅能從多個視圖中學習到更精確的圖，還能捕獲數(shù)據(jù)的全局和局部結構。但有些多視圖聚類方法僅探索視圖間的一致性而忽視了每個視圖的局部結構，文獻[12]提出為不同的特征分配權重并在各個視圖特定的自表示空間中獲取局部信息進而提高聚類性能。基于圖學習的多視圖聚類方法中，文獻[13]提出以歐式距離為度量標準，自適應的構造一個關系矩陣，稱為自適應近鄰學習（ANGL）。通過ANGL 融合多個視圖的原始矩陣，得到一個共識關系圖，從而提出自適應近鄰多視圖學習（MLAN）[14]算法。由于大多算法假設不同特征重要性相同，而在現(xiàn)實中這一假設并不完全適用，文獻[15]提出了自適應近鄰加權聚類算法（SWCAN），為不同特征分配權重，在學習相似圖的同時將樣本劃分為多個簇?，F(xiàn)實數(shù)據(jù)中，有些圖摻雜了較大的噪聲，這會降低聚類性能，所以文獻[16]提出一種基于低秩和稀疏分解的馬爾可夫鏈方法用于魯棒多視圖譜聚類（RMSC）來克服這一缺陷。RMSC 先在每個單視圖上構造轉移概率矩陣，然后用從這些矩陣中恢復出的低秩轉移概率矩陣作為標準馬爾可夫鏈聚類方法的輸入。

上述多視圖聚類方法已經取得了良好的效果，但還是沒有有效地利用多視圖數(shù)據(jù)間的互補信息，忽視了多視圖數(shù)據(jù)的高階相關性。針對這一問題，文獻[17]提出了基于Tucker 分解的低秩張量約束多視圖子空間聚類（LTMSC），但Tucker分解并不是秩函數(shù)的凸松弛，所以文獻[18]進一步提出了基于張量奇異值分解的多視圖子空間聚類，通過基于t-SVD的核范數(shù)對張量施加一種新型的低秩約束，確保了多個視圖之間的一致性。但大多基于張量核范數(shù)最小化的聚類方法同等的對待每一個奇異值，限制了處理問題的靈活性，所以文獻[19]充分利用奇異值的先驗信息，提出了基于張量加權核范數(shù)的多視圖聚類方法。文獻[20]提出了本質張量學習的多視圖譜聚類（ETLMSC），主要學習一個具有低秩約束的本質張量，然后將其作為基于馬爾科夫鏈的譜聚類的輸入。文獻[21]進一步提出了基于截斷核范數(shù)的低秩張量分解的多視圖譜聚類算法。

基于上述研究發(fā)現(xiàn)多視圖聚類算法中相似矩陣和圖的質量至關重要，但部分算法構造的圖由于受噪聲和異常值的影響而不具有魯棒性且無法充分利用多視圖的互補信息，而基于張量的算法又通常使用原始數(shù)據(jù)構造張量且計算復雜度高。針對以上問題，本文提出一種面向多視圖聚類的低秩張量表示學習（LRTRL-MVC）算法，主要貢獻為：

（1）將魯棒圖學習擴展到多視圖數(shù)據(jù)，在去除噪聲和異常值影響的同時進一步利用多視圖的互補信息，獲得更加精確揭示樣本之間關系的親和圖，提升聚類性能。

（2）利用各視圖數(shù)據(jù)獲得的魯棒圖構造3 階張量，挖掘多視圖數(shù)據(jù)間的高階相關性。

（3）選用基于張量奇異值分解（t-SVD）的核范數(shù)來保持本質張量的低秩性質，以便更好地捕獲多視圖共用的類別信息。

（4）提出了一種基于交替方向乘子法（ADMM）的優(yōu)化算法來求解目標函數(shù)。與其他相關的最好多視圖聚類算法相比，提出的方法在4個不同的數(shù)據(jù)集上取得了最好的聚類效果。

1 相關符號和定義

表1 相關符號Table 1 Summary of notations

定義1（f-對角張量[21]）對于一個3 階張量，若其所有正面切片都是對角矩陣，則稱為f-對角張量。

定義2（單位張量[21]）對于張量I∈?n×n×n3，第一個正面切片是大小為n×n的單位矩陣，其他所有正面切片均為0矩陣。

定義3（張量積t-product[22]）假設張量A∈?n1×m×n3，B∈?m×n2×n3，則張量積A?B 是一個大小為n1×n2×n3的張量，且：

2 面向多視圖聚類的低秩張量表示學習

本文提出的算法由兩部分組成，第一部分將魯棒圖學習擴展到多視圖中，利用魯棒主成分分析[23]（RPCA）的思想，將多視圖數(shù)據(jù)的每個視圖矩陣分解成低秩矩陣和稀疏矩陣，并在干凈的低秩矩陣上利用自適應近鄰法構造魯棒圖。第二部分用第一部分得到的圖作為輸入，計算出相應的轉移概率矩陣，再堆疊構建一個3階張量并將張量沿第三維旋轉，然后對張量進行t-SVD 分解，得到一個低秩張量和一個噪聲張量，最后在低秩張量上執(zhí)行馬爾可夫譜聚類得到最終的聚類結果，本文算法框架如圖1所示。

圖1 LRTRL-MVC算法框架Fig.1 Framewok of LRTRL-MVC algorithm

2.1 多視圖魯棒圖學習

2.1.1 目標函數(shù)

2.1.2 目標函數(shù)求解

2.2 基于馬爾可夫鏈的譜聚類

2.3 低秩張量學習

2.3.1 目標函數(shù)

根據(jù)算法2，在基于馬爾可夫鏈的譜聚類方法[28]中，轉移概率矩陣直接影響著聚類性能。同樣對于面向多視圖聚類的馬爾可夫鏈譜聚類方法[16，19，29]，轉移概率矩陣對聚類結果也具有重要的影響，因此如何基于多視圖來學習譜聚類的轉移概率矩陣是要解決的主要問題。其中一個代表性方法RMSC[16]將每個視圖下的轉移概率矩陣Pi分解為共享概率矩陣Z和視圖特定的噪聲矩陣Ei，以此來獲取共享信息。但是該方式忽略了每個視圖中包含的對聚類有用的特殊信息，所以，將每個Pi分成兩部分，即Pi=Zi+Ei，然后分別收集堆疊所有的Zi和Ei來構造3階張量Z 和E，進而在張量形式下揭示不同視圖之間的高階相關性。由于不同視圖是同一對象的不同表示形式，因此，不同視圖下的低秩部分Zi通常具有相同的類別屬性。另外，樣本類別數(shù)目通常比樣本數(shù)目少的多，所以，由不同視圖下的低秩部分Zi構成的張量Z 具有低秩結構，使用基于t-SVD 的張量核范數(shù)|| ||?來度量。此外對于噪聲項，由于噪聲樣本一般是稀疏的，所以用對異常值和噪聲具有較強魯棒性的?2,1范數(shù)來度量。不直接使用轉移概率張量P∈?n×n×m，而是將其沿第三維即特征維旋轉，這種旋轉操作在Mtalab 中可以通過fft 功能輕松實現(xiàn)，且沿特征維的快速傅里葉變換不僅保持了視圖之間的關系，還大大降低了優(yōu)化求解中的計算復雜度。得到張量形式的目標函數(shù)為：

3 實驗結果與分析

3.1 實驗設置

3.1.1 數(shù)據(jù)集

為驗證算法的有效性，在4 個數(shù)據(jù)集上進行實驗，分別是BBCSport、Newsgroups data set（NGs）、Yale 和MSRCv1。

BBCSport[20]（http：//mlg.ucd.ie/datasets/bbc.html）數(shù)據(jù)集總共有2種不同的視圖，包含來自英國廣播公司體育網(wǎng)站的737 份文件，對應于田徑、板球、足球、橄欖球和網(wǎng)球5個熱門領域的體育新聞。

NGs（http：//qwone.com/～jason/20Newsgroups）是20個新聞組數(shù)據(jù)集的子集，共有3 個視圖。由500 個新聞組文檔組成。每個原始文檔都用3 種不同的特征提取方法進行預處理。

Yale（http：//vision.ucsd.edu/datasets/yale_face_dataset_original）人臉數(shù)據(jù)庫包含3 個視圖，有15 個人的165 張灰度圖像。每個主題包括11個不同的表達和配置的圖像。本文提取了3種類型的特征。

MSRCv1[10]數(shù)據(jù)集有5 個視圖，包含由7 個類別組成的210 幅圖像，并且本文對于每幅圖像選擇5 個特征向量。

3.1.2 評價指標

為了綜合評估聚類的性能，本文采用3個常用的評價指標對結果進行度量，分別是精確度[18]（ACC）、純度[18]（Purity）和歸一化互信息[18]（NMI）。對于所有指標，值越高表示性能越好。

3.1.3 對比算法

為了說明提出算法的有效性，我們將在實驗數(shù)據(jù)集上與下列5個相關算法進行對比：

（1）低秩表示（LRRbest）[5]，對每個視圖采用低秩表示算法，選擇最優(yōu)結果。

（2）魯棒圖學習（RGCbest）[8]，自適應的去除原始數(shù)據(jù)中的噪聲和異常值，從每個視圖中學習到最可靠的圖進行聚類，選擇最優(yōu)結果。

（3）基于自適應近鄰的多視圖學習（MLAN）[14]，同時進行多視圖聚類、半監(jiān)督分類和局部流形結構學習，得到最優(yōu)圖直接劃分聚類。

（4）同時學習特征權重和局部結構的多視圖子空間聚類（JFLMSC）[12]，將特征的自適應局部學習、自表示學習和權重學習結合到一個框架中，利用每個視圖的全局和局部結構進行多視圖子空間聚類。

（5）本質張量學習用于多視圖譜聚類（ETLMSC）[20]，學習一個本質張量用于基于馬爾可夫鏈的譜聚類，揭示多視圖表示的高階相關性。

3.2 實驗結果與分析

3.2.1 實驗結果

分別在4個數(shù)據(jù)集上對5個算法和本文提出的算法進行實驗，為減小實驗的誤差，對不同的算法單獨調整參數(shù)直至最優(yōu)，不同數(shù)據(jù)集上的實驗結果分別如表2～5所示，最優(yōu)結果加粗表示。

表2 數(shù)據(jù)集BBCSport上的實驗結果Table 2 Experimental results on BBCSport

表3 數(shù)據(jù)集NGs上的實驗結果Table 3 Experimental results on NGs

表4 數(shù)據(jù)集Yale上的實驗結果Table 4 Experimental results on Yale

表5 數(shù)據(jù)集MSRCv1上的實驗結果Table 5 Experimental results on MSRCv1

從表2～5中可以看出，4個數(shù)據(jù)集中，本文提出的算法都取得了最佳聚類性能。例如在Yale人臉數(shù)據(jù)集上，與相應的次優(yōu)算法MLAN相比，本文提出的方法在3個評價指標ACC、NMI和Purity上分別提升了17、13和22個百分點。所提算法的純度在4 個數(shù)據(jù)集上相比于ETLMSC 方法，分別提高了1、12、20 和7 個百分點。提出的算法與單視圖的LRR、RGC算法相比，在性能上均取得了較大的提升，主要是由于單視圖聚類算法僅僅利用了單個視圖的信息，即使選擇最優(yōu)的視圖進行聚類，在性能上也無法取得更好的結果。與在原始數(shù)據(jù)上直接學習圖的多視圖聚類算法MLAN 相比，本文算法是在干凈的低秩數(shù)據(jù)上學習圖，使得聚類效果有了進一步的提升。與JFLMSC算法相比，通過構造張量進一步探索到多視圖數(shù)據(jù)的高階相關性，使得聚類準確性更高。與基于張量的方法ETLMSC 相比，本文方法仍體現(xiàn)出優(yōu)越性，主要歸功于轉移概率矩陣構造的可靠性以及高階相關性的有效探索。由上述實驗可以發(fā)現(xiàn)，與其他傳統(tǒng)算法相比，本文算法在不同類型數(shù)據(jù)集和不同評價指標上都有更優(yōu)異的表現(xiàn)。

3.2.2 參數(shù)分析

圖2 參數(shù)β 和λ 對BBCSport數(shù)據(jù)集的影響Fig.2 Influence of β and λ values on BBCSport dataset

3.2.3 復雜度分析

本文提出的算法的主要計算量來自低秩張量學習每次迭代過程中Z和E 的求解，優(yōu)化求解張量E 的時間復雜度為O(mn2)。而對于張量Z，一方面，沿第3維的傅里葉變換和逆傅里葉變換時間復雜度為O(mn2lbn)，另一方面，在傅里葉域計算每個正面切片奇異值分解的時間復雜度為O(mn2)，所以求解計算Z的總時間復雜度為O(mn2+mn2lbn) 。通常視圖數(shù)m遠遠小于樣本n，那么m≤lbn，所以相較于不進行張量旋轉所需要的計算復雜度O(m2n2lbn)，張量旋轉操作降低了計算復雜度。其次算法復雜度還涉及到多視圖魯棒圖學習和基于馬爾可夫譜聚類中的奇異值分解和矩陣求逆的操作，一般他們的計算復雜度為O(n3)。記迭代次數(shù)為t，提出的算法總的計算復雜度為O(n3+tmn2(m+lb(n)))。

表6顯示了提出的算法和5種對比算法的時間復雜度以及在4 個數(shù)據(jù)集上運行10 次的平均時間，其中dv表示第v個視圖特征向量的維數(shù)，m和n分別為視圖數(shù)和樣本數(shù)，r是樣本數(shù)據(jù)矩陣的秩，平均運行時間以s 為計量單位。雖然MLAN 和ETLMSC 算法所需運行時間較短，但其聚類性能不如本文提出的算法。與比較算法中運行時間較長的兩個算法RGC 和JFLMSC 相比，提出算法的運行時間在BBCSport 和MSRCv1 數(shù)據(jù)集上多于RGC 和JFLMSC，但是在NGs 和Yale 數(shù)據(jù)集上顯著少于RGC 和JFLMSC。在實際應用中，提出的LRTRL-MVC 能夠在可接受的時間范圍內達到更好聚類效果。

3.3 可視化結果

為了更直觀地看到聚類結果，將面向多視圖聚類的低秩張量表示學習算法與其他對比算法在MSRCv1 數(shù)據(jù)集上的聚類結果進行可視化。先通過tSNE方法將高維特征映射到二維子空間，再利用算法得到的聚類結果對映射后的二維數(shù)據(jù)進行著色，由此直觀地顯示出算法的聚類性能。從圖3中可以觀察到，本文提出的算法能有效地將相似樣本聚集到一個簇中，體現(xiàn)出優(yōu)越的聚類性能。

圖3 MSRCv1數(shù)據(jù)集上算法可視化結果Fig.3 Visualization results of algorithm on MSRCv1 dataset

4 結論

本文提出了一種面向多視圖聚類的低秩張量表示學習算法，通過把魯棒主成分分析和自適應近鄰學習融合到一個框架將魯棒圖學習擴展到多視圖，充分利用了多視圖數(shù)據(jù)的互補信息。然后利用精確的魯棒圖計算轉移概率矩陣進而構造3 階張量。通過基于張量奇異值分解的核范數(shù)約束低秩張量來揭示多視圖間的高階相關性，最后利用馬爾可夫譜聚類獲得最終的聚類結果。在BBCSport、NGs、Yale 和MSRCv1 數(shù)據(jù)集的聚類實驗中，與算法LRR、SPC、MLAN、JFLMSC和ETLMSC相比，不論是數(shù)值指標還是可視化結果，本文提出的算法都獲得了更好的聚類結果。