基于一致性圖的權重自適應多視角譜聚類算法

王麗娟，邢津萍，尹明，郝志峰，蔡瑞初，溫雯

（1.廣東工業大學計算機學院，廣東 廣州 510006；2.廣東工業大學自動化學院，廣東 廣州 510006；3.汕頭大學，廣東 汕頭 515063）

0 引言

多視角數據描述了同一事物在不同視角下的多種數據信息。比如：一個新聞往往以文字、視頻、圖片等不同的形式出現，一張照片中的景色往往以不同的角度進行拍攝。這些視角的形式、內容通常不同。因此，探索同一對象在每個視角內部隱含的一致性信息是一個極具挑戰的問題。多視角聚類是一個有效的數據挖掘算法。其聚類性能依賴于多視角數據一致性信息的發現程度。傳統的單視角聚類算法，如文獻［1-3］只能依次處理每一個視角，這樣做可能會割裂數據內部一致性，無法有效提取多視角內部信息。目前，多視角聚類方法大致可分為基于子空間［4-6］、基于非負矩陣分解［7-8］、基于圖［9-10］3 種聚類方法?；谧涌臻g的多視角聚類方法從多個子空間或者潛在空間中學習所有視角數據新的統一表示，以便在構建聚類模型時更容易處理高維多視角數據。文獻［11］提出一個協同訓練框架下的多視角子空間聚類，利用在一個視角下自動學習的標簽來輔助另一個視角下判別性子空間的生成?；诜秦摼仃嚪纸獾亩嘁暯蔷垲愃惴ɡ梅秦摼仃嚪纸鈱υ紨祿M行降維處理，獲得的低維數據特征有利于學習數據的潛在特征。文獻［12］提出一個將非負特征分解用于數據并將數據進行融合，制定了一個帶有歸一化策略的聯合矩陣分解?；趫D的多視角聚類方法利用樣本之間的加權無向圖來表示樣本之間的關系。這一類方法通常假設每個單獨的視角都可以捕獲數據的部分信息，同時所有的樣本關系圖都具有相同的潛在一致性數據信息。文獻［13］提出一個共同正則化多視角譜聚類方法，在學習共享特征向量的同時減小多個視角之間的差異，保持多個視角之間具有一致性。文獻［14］提出學習多個視角間的相似度矩陣，學習得到一個一致性的聯通分量的方法。但是，以上這些方法在獲取視角間一致性信息時忽略了視角的多樣性和重要性排序，平等對待每個視角會受到冗余視角的干擾，無法提取多視角數據內隱含的一致性信息，降低了聚類性能。

本文提出一個基于一致性圖的權重自適應多視角譜聚類算法（WGSC）。首先引入自適應的視角權重，使得不同視角發揮不同作用，自適應調節加權視角權重，學習真實的一致性共享相似度矩陣。其次學習具有多樣性的特征嵌入，建立特征嵌入與樣本嵌入的二部圖，實現特征嵌入和樣本嵌入之間的特征遷移，最大化兩者間的一致性。最后分別將共享相似度矩陣、特征嵌入同樣本嵌入聯合優化，以此提高樣本嵌入的一致性。

1 相關工作

1.1 遷移學習

傳統的機器學習通常需要使用同分布假設的標注數據進行訓練，然而在實際過程中不同數據集可能存在一些問題，比如數據分布差異、標注數據過期和訓練數據過期等問題。為了充分利用標簽數據，保證新任務上的模型精度，遷移學習應運而生。遷移學習利用輔助數據集來提高目標數據集的學習性能，其目的是獲取源域和學習任務中的知識，以幫助提升目標域中的預測函數的學習。

對于該思想在聚類問題中的應用，文獻［15］提出自我學習聚類（STC），在大量無標簽輔助數據的幫助下對目標數據進行聚類。STC 擴展了基于信息理論的協同聚類算法［16］，假設目標數據集和輔助數據集共享相同的特征聚類。遷移譜聚類（TSC）［17］在此基礎之上提出了一種基于類似假設的方法。與基于信息理論的STC 不同，TSC 在建立圖的基礎上對任務進行聚類。在TSC 的基礎上，本文將兩個視角延伸到多個視角并改善了只能建立相同特征數視角的二部圖約束，即便特征數不同的視角也能建立二部圖，實現多視角數據中樣本嵌入和特征嵌入之間的遷移學習。

1.2 多視角聚類

在文獻［13］提出的協同訓練和協同聚類基礎上，文獻［18-19］提出了多種不同的多視角聚類算法。但是這些算法都忽略了不同視角之間的權重和樣本關系學習的問題。文獻［14］提出了基于圖學習的多視角聚類算法，該算法給出了權重參數，使得不同視角信息具備不同重要性。但是這種算法忽略了權重因子非負的問題，因為一個非負的歸一化權重能夠減少某一個視角完全決定整個算法的情況，使得視角參數更加可靠。因此，文獻［20］提出一種可擴展的多視角聚類方法，該方法給每個視角分配非負的權重，從而避免了因某一視角權重過大而決定整體結果。受到該方法的啟發，本文提出視角權重向量，視角權重由相似度矩陣和共享相似度矩陣之間的差異自適應調節，無須再手動調節視角權重參數。通過最小化兩者之間的差異，促使共享相似度矩陣最大化學習視角間的一致性信息。但是，多視角數據樣本的信息尚未得到充分利用，為此本文充分學習樣本的特征，建立特征嵌入與樣本嵌入的聯系，將特征嵌入的多樣性特征轉化為有利于樣本嵌入的一致性表達，實現信息的遷移。

2 WGSC 聚類算法

2.1 符號定義

對于具有nv個視角的多視角數據樣本X={X1，X2，…，Xnv}，其中，Xv∈Rd×n表示第v個視角下的樣本數據，d表示的是對應視角下的特征維度，n是樣本點的個數。特征嵌入F∈Rn×c，c表示聚類的個數?！琗‖2，1表示2，1 范數，表示2 范數的平方，表示Frobenis 范數的平方。

2.2 相似度矩陣的初始化

相似度矩陣的初始化通常采用高斯核全連接的方式構造相似度矩陣，本文采用式（1）分別初始化每個視角v的相似度矩陣Sv。該式利用樣本點之間的距離計算兩者之間的相似度sij，并對相似度矩陣施加范數約束，避免某一個樣本點對應的相似度向量si中存在只有一個非零值的情況。

其中：εs是調節相似度矩陣的正則化參數。

2.3 WGSC 算法整體流程

WGSC 算法整體流程如圖1 所示，首先構建每個視角的相似度矩陣并初始化其對應的視角權重，對兩者進行加權求和，最小化共享的相似度矩陣G和多個視角相似度矩陣Sv之間的差異，以此獲得所有視角的一致性表達。其次學習每個視角特征嵌入Av并建立與共享樣本嵌入F的二部圖，遷移多樣性數據于樣本嵌入和特征嵌入之間，同時最大化特征嵌入與樣本嵌入間的一致性約束，實現多個視角間的多樣性信息轉化為一致性信息。最終以樣本嵌入為中間樞紐站，整合共享相似度矩陣、樣本嵌入和特征嵌入的統一學習框架。該框架可分為兩個部分：一是本文方法的核心，樣本嵌入F的學習是從特征嵌入Av和共享相似度矩陣G中學習一致性和多樣性信息，提高樣本嵌入的一致性；二是為了充分利用原始數據信息，學習共享相似度矩陣G得到一致性樣本關系和遷移特征嵌入的多樣性信息。通過相似度矩陣Sv和視角權重αv的結合學習，篩選更優的視角，減少不重要信息的干擾，得到一致性相似度矩陣G。從特征嵌入的多樣性信息中學習能夠補充單一地學習樣本關系的不足，學習到的多樣性特征信息能夠提供更多多視角間的一致性信息，兩者相輔相成最終獲得更好的多視角聚類結果。

圖1 WGSC 算法流程Fig.1 Procedure of WGSC algorithm

2.4 共享相似度矩陣的學習

傳統的譜聚類通常預先計算樣本點之間的距離得到相似度矩陣。但是，在多視角聚類中，直接對每個視角的相似度矩陣做聚類難以保證多個視角之間的一致性。為了解決這個問題，提出學習視角間共享的相似度矩陣。本文方法賦值相似度矩陣對應的視角權重并對其加權求和，通過Frobenis 范數約束減少加權后的相似度矩陣與共享相似度矩陣的差值，得到具有多個視角間一致性樣本關系的共享相似度矩陣。視角權重的自適應調節數值由相似度矩陣與共享相似度矩陣之間的差異決定，如果差異過大會減少視角權重的值，從而提高更優視角的權重。參數權重的引入打破了每個視角之間的平等性，對所含信息重要性差異化的多個視角進行排序，降低了次優視角的權重，最小化了每個視角相似度矩陣與共享相似度矩陣的差異，優化了共享相似度矩陣的一致性學習。最后得到共享的相似度矩陣G：

其中：αv為視角權重；Sv為相似度矩陣；G為共享相似度矩陣。

2.5 特征嵌入的學習

在聚類中，同一類中的樣本往往有相似的特征分布，并且特征的相似度越高，屬于同一類的概率也越大［21］。本文方法利用遷移學習思想，知識從源域遷移映射到目標域，表現為將特征信息遷移到樣本信息，學習每個視角的特征嵌入并將相似的信息傳遞給樣本嵌入。在方法實現上，采用二部圖來表示樣本和特征之間的關系，尋找樣本和特征之間的最小切割，最大化兩者之間的相同點。其中，2，1 范數［22］能夠有效降低樣本中的噪聲對特征選擇的影響。其函數表達式如式（3）所示：

2.6 目標函數

本文方法以樣本嵌入F為中心，以共享相似度圖G和特征嵌入Av為出發點，在譜聚類中實現對樣本嵌入的優化，得到最終的目標函數。首先，學習每個視角所對應的相似度矩陣，并對權重αv平均初始化。其次，在Frobenis 范數的約束下最小化相似度矩陣和共享相似度矩陣的差異，得到最優的共享相似度矩陣。與此同時，建立樣本嵌入F與特征嵌入Av之間的二部圖，最大化兩者的共同性，以此加強樣本嵌入的一致性學習，同時通過2，1 范數降低特征嵌入學習過程中噪聲對特征選擇的影響。在迭代更新中，共享相似度矩陣學習了所有視角的相似度矩陣，視角權重的更新由相似度矩陣和共享相似度矩陣的差異決定，如果單個視角的相似度矩陣與共享相似度矩陣差異很大，意味著該視角的相似度矩陣存在很多與其他視角不一樣的數據點，視角權重將自適應降低權重參數的值，同時更重要的視角權值會增加。通過這種方式，最終的共享相似度矩陣學習了所有視角的一致性信息。共享相似度矩陣由每個視角的相似度矩陣、視角參數共同決定，這為譜聚類的學習提供了一個可靠的相似度矩陣。譜聚類不僅需要考慮樣本相似度矩陣，還需要考慮特征嵌入學習。為了進一步優化樣本嵌入，將多個視角中的多樣性特征遷移至樣本嵌入中，通過最大化特征嵌入與樣本嵌入之間的一致性，補充了樣本嵌入中的多樣性信息，提升了樣本嵌入的準確性和一致性。具體來講，樣本嵌入將具有一致性的樣本關系作用于特征嵌入，特征嵌入將優化后的多樣性特征反饋給樣本嵌入，樣本嵌入學習視角間多樣性特征信息，以此最大化視角間的一致性信息。最終圖學習、譜聚類以及參數更新在統一的框架中聯合優化，在譜聚類作用下得到一個具有一致性和準確性的樣本嵌入，提高了最終的聚類性能。本文方法的目標損失函數如式（4）所示：

其中：αv為視角權重；Sv為相似度矩陣；G為共享相似度矩陣；Av為特征嵌入；F為樣本嵌入；為歸一化后的樣本數據；λ為樣本學習調節參數；μ、β為特征樣本參數。

2.7 模型優化

該節對提出的算法進行詳細的求解。由于該算法所含變量非凸，本文采用最優交替乘子法（ADMM）［23］對該目標公式進行求解，取得G、F、A的最優解。首先引入輔助變量Q、β，并得到該算法的拉格朗日函數如下：

其中：Yv是拉格朗日乘子；γ是懲罰參數。

更新G，固定其余變量，保留只含有G的項，最終可以得到式（6）：

式（11）為非凸函數，采用最優交替乘子法取得最優解。

更新F，固定其余變量：

定 理1對于秩 為p的矩陣Z∈Rn×p，Z在Stiefel Manifold［24］上的投影定義為：

N是半正定矩陣，式（24）是一個二次凸優化問題。本文實驗通過經典拉格朗日乘數的方法來有效解決該問題。因此，式（24）優化等價于式（25）優化：

式（29）的優化參考了文獻［25］算法優化。

2.8 算法復雜度分析

在WGSC 算法中，假設總迭代次數為m，視角權重更新中的迭代次數為t。WGSC 由3 個子問題組成：更新共享相似度矩陣，迭代優化共享相似度矩陣G，復雜度為O(n2cm+nm2t+m3t)；更新樣本嵌入F，需要計算其本身和投影，時間復雜度為O（n2c）；更新特征嵌入Av，計算的復雜度為O(n2c)。因此，WGSC的復雜度為O（n2cm+nm2t+m3t）。

3 實驗結果與分析

本節將驗證上述方法的性能，本文實驗將在5 個真實的數據集上運行。

3.1 數據集描述和實驗環境

3-Sources 數據集來自3 個著名的在線新聞資源：BBC，Reuters，Guardian。該數據集在3 個來源中共報道169 篇，分為6 個主題標簽，每篇新聞都有一個主題標簽。Yale 數據集包含了15 個人的165 張GIF 格式的灰度圖像，每個對象在不同心情、不同條件下提供11 張照片。MSRCV1 數據集包含240 張圖像和8 個對象類別，選擇7 種類別的數據，每種類型有6 種提取方式，即CENT、CMT、GIST、HOG、LBP、SIFT。ORL 數據集包含40 個不同主題的400 張圖像，所有圖像均在暗光均勻的光線下拍攝，且在不同的時間、不同的光照、不同的面部表情和不同細節下拍攝。COIL20 數據集包含20 個物體的圖像，每個物體有72 張不同角度的彩色圖像，共1 440 張。本文實驗運行于Apple M1 芯片，內存8 GB，MATLAB R2020a 軟件。

3.2 實驗設置與對比算法

首先對實驗數據進行歸一化處理，使得所有的樣本數據值在［-1，1］之間。對歸一化后的樣本數據輸入到WGSC 算法中得到樣本嵌入，并對樣本嵌入做K-means 聚類得到最終的實驗結果。其中將所有對比算法中近鄰參數設置為類的個數，本文實驗也設置為類的個數。本文實驗將多視角的數據分別依次傳輸到單視角算法中進行運行，并選取實驗結果最好的視角作為最終的實驗結果，其余算法均一次性運行所有視角的數據并得到最終的實驗結果。所有實驗結果均由上述實驗方式得到，并在同一數據集下運行30 次得到相應實驗結果，計算各評估指標的平均值和標準差。

多視角聚類對比算法如下：

1）譜聚類［26］構建樣本的相似度矩陣，距離與邊權值成反比。通過對所有數據點組成的圖進行切圖，讓切圖后不同的子圖間邊權重和盡可能得低，而子圖內的邊權重和盡可能得高，從而達到聚類的目的。優點在于具有能在任意形狀的樣本空間上聚類且收斂于全局最優解，但是對相似度圖的改變和聚類參數的選擇非常敏感。

2）可擴展多視角聚類（SFMC）算法［20］。SFMC是一個用于多視角聚類的可擴展和無參數的圖形融合框架，以自我監督加權方式尋求跨多個視圖兼容的聯合圖。學習的一致性圖和視角參數的自適應相互學習解決了超參數的問題。

3）加權多視圖譜聚類（WMSC）算法［27］。根據特征向量對聚類結果的影響，引出尋找一個一致的拉普拉斯矩陣，以及對相似的視圖賦予相似的權重來差異化最終的聚類，運用最大典型角的方法來衡量聚類結果的差異。

4）聚合相似度矩陣的譜聚類（AASC）算法［28］。對不同視角的相似度矩陣的學習減少不重要特征對聚類的影響，并在此基礎之上引入權重向量，優化每個視角的相似度學習。

5）共同正則化譜聚類（Co-Reg）算法［29］。建立一個共同正則化譜聚類框架，并在此基礎之上提出兩種正則化方案來實現這個目標。兩種方案的區別在于K-means 所作用的特征向量的不同，第1 個方案是K-means 作用于所有視圖中的其中一個特征向量，第2 個方案是K-means 作用于代表所有視角潛在的具有一致性的特征向量。

6）多視角一致性聚類（MCGC）算法［30］。學習一個最小化所有視角差異的一致性圖，并用拉普拉斯矩陣的秩加以約束，最終通過學習到的一致性圖直接獲得樣本的標簽。

3.3 結果分析

3.3.1 算法性能對比

本文采用6 個聚類評估標準來評估聚類性能，分別是聚類精確度（Accuracy）、標準化互信息（NMI）［31］、純度（Purity）、精確率（Precision）、召回率（Recall）和F1 值。這6 個評估標準下的實驗結果值越大，表明效果越好。表1～表5 分別展示了本文算法與多個對比算法在3-Sources、MRSCV1、Yale、ORL、COIL20 數據集下的實驗結果，其中，實驗結果均以平均值（標準差）的形式展示，加粗數字為最優值。

表1 不同算法在3-Sources 數據集上的比較Table 1 Comparison of different algorithms on 3-Sources dataset >%

表2 不同算法在MRSCV1 數據集上的比較Table 2 Comparison of different algorithms on MRSCV1 dataset %

表3 不同算法在Yale 數據集上的比較Table 3 Comparison of different algorithms on Yale dataset %

表4 不同算法在ORL 數據集上的比較Table 4 Comparison of different algorithms on ORL dataset %

表5 不同算法在COIL20 數據集上的比較Table 5 Comparison of different algorithms on COIL20 dataset %

1）WGSC 與SFMC 相比，SFMC 更適用于數據規模更大的數據集，其學習每個視角對應的錨點，壓縮了數據的規模，學習視角間的一致性圖。但是，在錨點降維過程中損失了很多特征，因此本文利用二部圖的方式學習樣本特征并進行遷移學習至樣本嵌入補充多樣性。從表1 實驗結果可以看出，WGSC優于SFMC，這表明對于數據相似度矩陣在樣本特征損失較大的情況下，學習樣本特征能提升聚類性能。

2）WMSC 和WGSC 都是聚焦于得到視角間一致的聚類結果。WGSC 采用的是學習一致性相似度矩陣的方法。為了尋找視角間潛在的一致性樣本關系，賦予相似度矩陣對應視角權重，融合相似度矩陣得到具有一致性的共享相似度矩陣。兩者不同之處在于：WMSC 學習具有一致性的拉普拉斯矩陣，它運用最大典型角的方法來減少不同視角之間的差異。實驗結果表明，WGSC 優于WMSC，因為相比于拉普拉斯矩陣的學習，相似度矩陣學習過程中的數據損失更少，聚類性能更佳。

3）WGSC 在所有數據集的聚類結果正確率比AASC 高出了5%以上，這表明WGSC 有良好的聚類性能。AASC 引入了權重向量并由特征值決定權重的大小。不同于AASC，WGSC 用相似度矩陣決定最終權重的大小，并在每輪中迭代更新。WGSC 對權重的評估具有更加豐富的信息，對于數據關系不清晰和雜亂的視角，賦予更低的權重能夠降低包含較多噪聲的視角對聚類性能的影響。

4）與WGSC 相比，Co-Reg 學習了具有一致性的特征向量，并最小化不同視圖間的特征向量之間的差異來達成一致性。不同于Co-Reg，WGSC 直接學習一致性相似度矩陣避免了原始數據中不可靠特征和不重要特征對特征向量的影響。

5）在這5 個數據集中，3-Sources 數據集特征數量遠多于樣本點個數。因此，特征較多的數據集在WGSC 算法上的表現相比于其他算法表現更佳。這是因為WGSC 將視角間的特征信息遷移到了樣本嵌入中，且這些視角的多樣性特征能夠補充樣本關系中存在的不足。此外，3-Sources 數據集的樣本點個數較少，對模型的遷移特征部分中二部圖的計算更有利，與其他算法相比更具優勢，不僅學習了構建的相似度矩陣中的樣本關系，還學習了大量的特征信息。

綜上，該實驗驗證了自適應學習視角權重能提高共享相似度矩陣學習的準確率，在保證不同視角之間的一致性以外，學習了原始數據的潛在一致性特征，并通過二部圖遷移了不同視角間的多樣性信息，確保了聚類的準確率。

3.3.2 共享相似度矩陣的一致性驗證

在圖2 中，圖2（a）～圖2（c）分別對應MRSCV1 在3 個視角下的相似度矩陣圖，圖2（d）表示在迭代優化后得到的共享相似度矩陣?？梢钥闯?，最終的共享相似度矩陣整合了視角間的一致性樣本關系，學習了樣本之間潛在的一致性。因此，WGSC 具備學習一致性共享相似度矩陣的能力。

3.3.3 算法收斂性分析

圖3 所示為WGSC 在以上5 個數據集中的收斂情況。從圖3 可以看出，WGSC 在每個數據集上都表現出穩定的收斂性，且每次迭代都確保了目標函數值的減少。目標函數收斂到正數或負數，其中負數函數值是因為特征嵌入學習中存在負數項，尤其是原始樣本數據相比于其他的項的值更大，所以目標函數值為負數是正常的。一般在30 次之后達到收斂效果，獲得了該算法的局部最優值，從而驗證了該算法具有良好的收斂性。

圖3 WGSC 在3-Sources、MRSCV1、Yale、ORL 和COIL20 數據集上的收斂圖Fig.3 The converge drawing of WGSC on 3-Sources，MRSCV1，Yale，ORL and COIL20 datasets

3.3.4 參數分析

本文算法中需要調試的參數有μ、λ、β3 個。首先3 個參數的取值范圍均設置為｛10-4，10-3，10-2，10-1，100，101，102，103｝，然后對其中2 個取上述范圍，另一個設為0.1，最終得到在3-Sources 數據集的正確率［見 圖4（a）～圖4（c）］、NMI［見 圖4（e）～圖4（f）］和Purity［見圖4（g）～圖4（i）］評估指標的實驗結果。從圖4 可以看出，β在｛10-2，10-1，100｝下有較為穩定的性能，λ在｛10-3，10-2，10-1，100｝下表現出可靠的性能。相對于上述2個參數，μ在該算法中的表現相對敏感。

圖4 β、μ、λ 在3-Sources 數據集下的參數分析Fig.4 Parameter analysis of β，μ，λ in 3-Sources dataset

4 結束語

本文對譜聚類的相似度矩陣和樣本嵌入重點優化，提出一個基于一致性圖的權重自適應多視角譜聚類（WGSC）算法。WGSC 基于自適應的視角權重，學習一個一致的共享相似度矩陣，自適應改變每個視角的相似度矩陣對應權重，提高共享相似度矩陣的一致性。通過構建樣本點和樣本特征二部圖，學習每個視角中的特征信息，獲得不同視角的多樣性信息，以此提高樣本嵌入一致性。本文算法建立樣本嵌入、共享相似度矩陣與特征嵌入的關系，實現三者間的信息轉化，獲得最優的樣本嵌入。實驗結果表明，本文算法能自適應學習權重參數及最優的相似矩陣，遷移特征嵌入中的信息至樣本嵌入，有效提升樣本嵌入的一致性和多樣性，進而提高聚類結果的準確率。本文算法在大規模樣本數據下的性能有較大提升空間，對部分參數較為敏感，下一步將挖掘參數與樣本之間的關聯，構建無參數聚類模型并優化相似度矩陣學習，將模型運用于大規模數據，避免參數對準確率的影響。