面向視角非對齊數據的多視角聚類方法

李驁，馮聰，牛宇童，徐士彪，張英濤，孫廣路

（1.哈爾濱理工大學計算機科學與技術學院，黑龍江 哈爾濱 150080；2.北京郵電大學人工智能學院，北京 100876；3.哈爾濱工業大學計算機科學與技術學院，黑龍江 哈爾濱 150001）

0 引言

近年來，多視角學習在機器學習領域引起了廣泛的研究興趣[1-2]。一方面，在眾多研究領域中，數據自然地呈現出多種表達方式[3-4]。另一方面，數據的各種表達方式之間存在著隱式的一致性和互補性[5-6]。因此，融合數據的多視角特征，能更全面地揭示數據的分布規律，提高多種下游任務的性能。

多視角聚類是多視角學習的典型應用，它旨在融合多個視角的線索，更好地挖掘數據中的本質類簇結構[7-8]?？紤]基于多視角數據的相似性進行融合，Nie 等[9]提出參數無關的自加權多視角聚類方法，該方法重新表述標準的譜聚類算法，為每一視角分配最優權重。文獻[10]尋求一個低秩相似性矩陣作為各視角圖結構的質心，從質心中直接獲取統一的類簇指示矩陣。Liang 等[11]在統一的框架中建模多視角數據的一致性和不一致性，進一步提高聚類性能。為了克服靜態相似性矩陣的缺陷，Wang等[12]提出基于動態相似性融合的多視角聚類方法，實現視角專屬相似性矩陣和公共相似性矩陣的相互促進。降維技術是應對多視角數據冗余性的有效方法。Liu 等[13]提出基于聯合非負矩陣分解的多視角聚類方法，對各視角系數矩陣施加一致性約束，使其融合為一致的類簇指示矩陣。張祎等[14]在矩陣分解的基礎上加入流形約束，有效保持了樣本空間的流形結構。張量低秩約束是一種利用多視角數據高階相關性的有效方法。Zhang 等[15]提出基于低秩張量約束的多視角子空間聚類方法，將各視角的自表達矩陣堆疊成張量，再以張量低秩約束降低其冗余性。Wu 等[16]提出基于關鍵張量學習的譜聚類方法，將各視角基于馬爾可夫鏈的概率轉移矩陣堆疊成張量并施加張量低秩約束，捕獲了多視角數據的高階相關性。

盡管上述多視角聚類方法取得了良好的性能，但在真實場景下的應用仍有一定局限性。由于信道時延、傳輸異步、網絡擁塞等多種客觀因素，獲取的多視角數據會發生視角的非對齊現象，影響現有多視角聚類方法的性能。這類問題是多視角學習中的一類初探新興問題，以三視角數據為例進行說明。如圖1(a)所示，給定一個對齊的多視角數據集其所有視角的特征矩陣Xv的第i列表示同一樣本i在不同視角v下的特征，即同一樣本在各視角的特征矩陣中是沿列對齊的。然而，由于信道時延、傳輸異步等影響因素，如圖1(b)所示，數據的原有視角對齊關系可能會發生錯位，即各視角特征矩陣Xv的同一列可能不再來自相同樣本。由于現有多視角聚類方法大多要求不同視角之間存在嚴格的對齊關系以實現特征融合[2]，視角非對齊現象將誤導現有方法將不同類別樣本的特征加以融合，降低了學習表示的鑒別力，從而限制了現有多視角聚類方法的應用。

圖1 一般多視角數據與視角非對齊多視角數據對比

面向這一新興問題的研究并不多見，根據本文的調研，目前僅包括文獻[17-18]這2 個工作。文獻[17]提出部分視角對齊聚類（PVC,partially view-aligned clustering）方法，設計了一個可微的對齊模塊，并將其集成于深度神經網絡以重建視角對齊關系。文獻[18]提出一種鑒于噪聲穩健損失的多視角對比學習（MvCLN,multi-view contrastive learning with noise-robust loss）模型，使對齊樣本在表示空間中相互靠近，而非對齊樣本則互相遠離。然而，上述工作只適用于兩視角數據。

文獻[17-18]工作揭示了一種處理視角非對齊數據的可行思路：先基于特征的相似度信息學習視角對齊關系，再重建視角之間的對應關系以緩解視角非對齊現象對多視角學習的影響。在此基礎上，本文提出了一種新的、適用于多視角的視角非對齊數據聚類方法。首先，本文方法基于多視角非負矩陣分解進行表示學習，將異構的多視角特征嵌入可度量的低維同構空間。其次，在低維同構空間中，基于二部圖最優匹配學習視角對齊關系，并提出參考視角的概念將對齊模型推廣至具有2 個以上視角的非對齊數據。最后，將上述表示學習和數據對齊模塊放入統一的Bi-level 優化框架，通過交替求解上層問題（表示學習）和下層問題（數據對齊），使二者在迭代中相互促進，以提升模型的總體性能。本文的貢獻如下。

1) 提出一種新穎的面向視角非對齊數據的多視角聚類方法，將表示學習和數據對齊置于同一目標函數中交替優化，學習到具有2 個以上視角的復雜非對齊數據的緊湊表示。

2) 提出了一種基于Bi-level 優化的目標函數，將表示學習和數據對齊抽象為上下層問題。設計了一種基于交替優化的數值求解算法，該算法具有較好的參數穩定性和高效的收斂性能。

3) 將本文方法應用于視角非對齊數據的多視角聚類任務，在3 個公開數據集、3 種視角不對齊率和3 種評價指標上，本文方法均優于8 種先進的多視角聚類方法。本文方法的總體結構如圖2 所示。

圖2 本文視角非對齊數據表示學習方法的總體結構

1 相關工作

1.1 多視角非負矩陣分解

多視角非負矩陣分解（MultiNMF,multiview non-negative matrix factorization）[13-14]是一種有效的多視角表示學習方法，能夠在降低原始特征維度的同時融合各視角的特征，學習到緊湊的多視角公共表示。假設具有Nv個視角的多視角數據集對各視角的特征矩陣Xv進行非負矩陣分解，使Xv≈Uv(Vv)T，得到基矩陣Uv和系數矩陣Vv，則Vv可作為該視角的低維表示，再對Vv施加一致性約束，可得到公共表示矩陣V*。該方法的目標函數為

1.2 Kuhn-Munkres 算法

二部圖是一種有著廣泛應用的圖論模型。對于二部圖G和它的2 個大小相等的頂點集V1,V2，G上的最優匹配是指一個V1,V2的頂點之間的一一對應，使所有相互匹配的頂點對之間的邊權總和最小。假設W是圖G的邊權矩陣，Wi,j表示頂點i與頂點j之間的邊權；定義指示變量Pi,j，當頂點i與頂點j互相匹配時，Pi,j=1，否則Pi,j=0，二部圖最優匹配問題的目標函數為

式(2)又稱為線性指派問題，是一類特殊的整數線性規劃問題，分別由Kuhn和Munkres 在20 世紀50 年代獨立解決，一般把該算法稱為Kuhn-Munkres算法。該算法能在多項式時間內精確求解二部圖的最優匹配問題[19]。

2 本文方法描述及其數值算法

2.1 數據降維的必要性分析

多視角數據通常具有較高的特征維度，含有較多冗余信息，判別性較低。以人臉數據集ORL的視角1為例，該數據集的判別性信息隨奇異值的分布規律如圖3 所示。如圖3(a)所示，盡管特征總數多達400 個，但其前50個特征值已包含了該數據集中超過60%的主要判別信息。如圖3(b)和圖3(c)所示，與原始特征矩陣相比，后30%小奇異值重建數據矩陣的取值較為均勻，說明其中的判別性信息較少。因此，對原始高維冗余數據進行降維，保留其主要判別分量，可以有效減少數據的冗余信息，提高特征的判別性。

圖3 ORL 數據集視角1 判別性信息分析

2.2 面向視角非對齊數據的多視角聚類方法

面向視角非對齊數據聚類，現有方法的思路可以概括為：從多視角數據中學習潛在的視角對齊關系，以指導模型從視角非對齊數據中學習有效的表示。在此基礎上，本文提出將學習到的表示轉化為一種跨視角相似度信息并反饋到視角對齊模型中，通過二者的相互促進，以學習到的對齊關系指導表示學習模型盡可能地融合來自同類樣本的視角信息，以消除視角不對齊因素的影響，改善表示特征的判別性，進而提高聚類性能。

本文的思路來自兩方面的觀察。一方面，對于數據對齊來說，保持跨視角一致性的表示學習是必要的。在缺少監督信號的情況下，表示特征之間的相似度信息是對齊關系學習的重要依據。但由于多視角特征的異構性，需要先將原始多視角特征嵌入一個低維同構的表示空間，才能有效地度量跨視角相似度。另一方面，對于視角非對齊數據的表示學習來說，對齊關系學習也是不可或缺的。由于視角非對齊現象的影響，模型無法直接對多視角數據進行特征融合，不能很好地利用多視角潛在一致性。因此，需要為每個特征找到與之對齊的其他視角特征，使它們對應相同的類簇，才能確保特征融合的有效性。受此啟發，本文提出在2 個模塊之間建立雙向數據通道，以提高聯合學習性能。

為了實現這一目的，本文將上述2 個模塊嵌入基于文獻[20]的Bi-level 優化框架中進行交替優化，使它們在迭代中相互促進，以提升模型的總體性能。本文面向視角非對齊數據的統一表示學習和數據對齊模型為

2.3 上層問題：表示學習

如上文所述，非負矩陣分解是一種有效的降維技術，能濾除數據中的冗余信息，提高特征的判別性。此外，該技術學到的特征具有較好的跨視角一致性，在跨模態檢索領域有著廣泛應用[21-22]。受此啟發，本文基于該技術設計表示學習模塊，以促進視角對齊關系學習并獲得多視角公共表示。

在多視角非負矩陣分解中，基矩陣Uv捕獲了原始特征空間中的潛在概念，而Vv則是這些潛在概念的疊加系數，從而把原始特征Xv嵌入一個以潛在概念為基底構成的坐標空間。由于不同視角所描述的樣本是一致的，各視角的疊加系數Vv具有很高的相關性，對Vv施加一致性約束后，可視為原始特征的一種同構表示，具有跨視角一致性，即屬于相同類簇的樣本的不同視角的特征，在表示空間中也具有較高的相似性。

然而，傳統的多視角非負矩陣分解只適用于視角對齊數據。對于視角非對齊數據，引入基于參考視角的對齊矩陣Pv,1 ≤v≤Nv,v≠u。將Pv右乘于原始特征矩陣Xv，可調整Xv的視角對齊關系，再對對齊后的特征矩陣Xv Pv,1 ≤v≤Nv進行多視角非負矩陣分解，得出表示學習的目標函數為

其中，λv是權衡參數，Pv是由數據對齊模塊學習到的視角對齊矩陣。

2.4 下層問題：數據對齊

數據對齊模塊的功能是從視角非對齊數據中學習潛在的視角對齊關系，為表示學習模塊提供對齊矩陣Pv。本文提出一種基于參考視角的對齊方法，即選定一個參考視角，以之為基準逐個對齊其他視角，使所有視角都與參考視角保持對齊。該方法將一個Nv視角的對齊問題轉化為Nv? 1個兩視角對齊的子問題。因此，可以先針對兩視角對齊問題設計模型，再由參考視角擴展到多視角的情況。

由于不同視角特征的跨視角相似度越大，它們屬于相同類簇的可能性也就越大，應該令所有相互匹配的特征對之間的跨視角相似度總和最大。然而，由于原始特征的異構性之間的相似度無法度量，只能用相應的低維同構表示之間的距離來近似估計，由此得到兩視角對齊模型的目標函數為

其中，C表示一種可能的特征匹配方案。注意到式(5)等價于一個二部圖最優匹配模型。將Xv,Xu分別作為二部圖的 2 個頂點集合V1,V2，將距離作為2 個頂點之間的邊權Wi,j，將指示變量表示特征對是否匹配，可得到如式(2)所示的二部圖最優匹配模型。

基于參考視角，可將式(5)推廣至多視角情況。設u為參考視角，v為任意視角，距離矩陣Dv為視角v,u特征之間的成對距離則求解視角v關于參考視角u的對齊矩陣Pv的目標函數為

2.5 目標函數求解

目標函數式(3)是Bi-level 優化問題，上層問題是非凸的，下層問題是整數規劃問題，難以同時求解。本文采用交替優化策略，通過交替求解上下層問題來獲得近似解。

2.5.1 上層問題求解

上層問題的目標函數如式(4)所示，該問題可通過交替優化變量Vv,Uv,V*求解。為了消除對基向量的L1范數約束，引入輔助變量Qv

其中，Qv∈RK×K為對角矩陣，Mv為視角v的特征維數，K為低維表示的維數。借助輔助變量Qv，把式(4)等價變形為

從式(9)可將目標函數拆成如下的子問題。

U-子問題。將式(9)用矩陣的跡展開并引入拉格朗日乘子Φ，得到無約束拉格朗日函數

對L1求導并令其導數等于 0，結合 KKT（Karush-Kuhn-Tucker）條件得

從式(12)中解得U的更新規則為

V-子問題。由于式(9)中Q的作用是對U進行L1范數歸一化，而U在V-子問題中是常量，因此可通過對U,V進行顯式歸一化來消除輔助變量Q

由于式(14)的歸一化不改變式(9)中的目標函數值，因此在顯式歸一化U,V后，V-子問題可化簡為

將式(15)用矩陣的跡展開并引入拉格朗日乘子Ψ，得到無約束拉格朗日函數

從式(17)解得V的更新規則為

V*-子問題。對于式(9)，只考慮與V*有關的部分，可得到目標函數為

式(19)是一個最小二乘問題，求導并令導數等于0，可解得V*的閉式解為

2.5.2 下層問題求解

式(6)是一類特殊的整數線性規劃問題，可采用文獻[19]中多項式時間的精確算法對其進行求解。本文的數值求解算法如算法1 所示。

算法1目標函數式(3)的數值求解算法

3 實驗結果及分析

3.1 數據集描述

本節在3 個公開數據集上進行多視角聚類實驗，數據集的具體情況闡述如下。

MSRC-v1 數據集。該數據集是一個物體圖像數據集，選擇其中7 個類別的樣本，共210 張圖像。提取5 種不同的特征作為5 個視角，分別為色矩（CM,color moment）特征、局部二進制模式（LBP,local binary pattern）特征、CENTRIST 特征、GIST特征以及SIFT 特征。

ORL 數據集。該數據集是一個人臉圖像數據集，由400 張人臉圖像組成。提取4 種不同的特征作為4 個視角，分別為強度特征（Intensity）、LBP特征、Gabor 特征以及灰度值特征（Gray）。

Digits 數據集。該數據集包含10 種手寫數字的圖像，樣本總數為2 000。提取3 種不同的特征作為3 個視角，分別為剖面相關特征、傅里葉系數特征以及形態學特征。

3.2 對比實驗設置及實驗結果分析

由于文獻[17]中的部分視角對齊聚類方法PVC和文獻[18]中的多視角穩健對比學習方法MvCLN 僅能處理具有2 個視角的數據聚類問題，因此本文分別在兩視角和2 個以上視角這2 種情況下進行對比實驗。由于視角非對齊現象可以看作一類針對多視角數據的復雜噪聲干擾，為了盡可能地公平，在包含2個以上視角的聚類實驗中，本文選取了若干對一般性噪聲穩健的先進傳統多視角聚類方法進行比較，使對比實驗能夠在一定程度上客觀地說明本文方法的優勢。2 個以上視角情況下的對比方法包括：文獻[12]中的基于圖的多視角聚類（GMC,graph-based multi-view clustering）方法、文獻[11]中的非一致圖融合（DGF,distance graph fusion）方法、文獻[10]中的自加權多視角聚類（SwMC,self-weighted multiview clustering）方法、文獻[16]中的基于關鍵張量學習的多視角譜聚類（ETLMSC,essential tensor learning for multi-view spectral clustering）方法、文獻[9]中的無參多圖學習（AMGL,auto-weighted multiple graph learning）方法和文獻[13]中的多視角非負矩陣分解（MultiNMF,multi-view NMF）方法。

對于上述6 種對比方法，首先在常用的三視角設定下進行實驗，分別采用MSRC-v1和ORL的前3 個視角及Digits的全部視角，實驗結果如圖4(a)～圖4(c)所示。其次，與PVC[17]和MvCLN[18]在上述數據集的兩視角子集上進行對比實驗，分別采用MSRC-v1的CM和CENTRIST 視角，ORL的LBP和Gabor 視角以及Digits的傅里葉系數和剖面特征視角，實驗結果如圖4(d)所示。最后，為了證明本文方法對一般多視角數據集的有效性，分別在MSRC-v1和ORL的全部視角上與上述6 種傳統多視角聚類方法進行對比實驗，實驗結果如圖4(d)所示。實驗中設置了3 種視角不對齊率（0.3、0.5和0.7），采用準確率（ACC,accuracy）、歸一化互信息（NMI,normalized mutual information）和純度（PUR,purity）作為評價指標，所有實驗均重復5 次，取其均值作為最終結果。對本文方法的參數設定如下：參考文獻[13,14]中的做法，將表示學習中各視角的權衡參數λv設置為相同值λ；將參考視角u設置為視角1；取高斯核函數作為距離函數，即其中σ為高斯核的尺度參數，實驗中取λ= 0.01，σ=1。

圖4 本文方法在三視角和兩視角設定下的對比實驗結果

如圖4(a)～圖4(c)所示，在絕大多數情況下，本文方法的各項性能指標都超過了其他對比方法。以不同不對齊率下的指標均值來考量對比方法的平均性能，本文方法在MSRC-v1、ORL、Digits 這3 個數據集上，ACC 指標依次超過次優方法7%、7%和13%；NMI 指標依次超過次優方法8%、8%和14%；PUR 指標依次超過次優方法7%、8%和13%。當不對齊率逐漸增大時，其他對比方法的性能下降趨勢明顯，而本文方法的性能變化趨勢相對平緩。在MSRC-v1 數據集上，當不對齊率逐漸增大時，本文方法的各項指標幾乎保持不變。在Digits 數據集上，本文方法的性能下降趨勢更平緩，例如當不對齊率從0.5 上升至0.7 時，對比方法的NMI 指標平均下降了16.4%，而本文方法的NMI 指標只下降了5.1%。

本文方法與PVC、MvCLN 方法的比較結果如圖4(d)所示?？梢钥吹?，本文方法在MSRC-v1和ORL 數據集的評價指標上的性能均優于PVC和MvCLN。在Digits 數據集上，ACC 指標取得了幾乎最優的性能，NMI和PUR 這2 個指標在部分實驗條件下取得了次優的性能，說明本文方法有效改進了該領域的前人工作。本文方法在四、五視角設定下的實驗結果如圖5 所示?？梢钥吹剑黜椥阅苤笜嗽谒囊暯荗RL 數據集和五視角MSRC-v1 數據集上的變化趨勢與在相應的三視角子集上基本一致，說明本文方法對一般的多視角數據集同樣有效。

圖5 本文方法在四、五視角設定下的對比實驗結果

綜上所述，本文方法在多個數據集、多種視角數量和多種不對齊率下的實驗中都取得了最優性能。上述實驗結果證明了本文方法對視角非對齊數據表示學習及其聚類應用的有效性和穩健性。

3.3 數據對齊模塊的有效性驗證

為了驗證數據對齊模塊的有效性，選取類簇對齊率作為視角對齊程度的評價指標，并繪制不同視角的類簇對齊率隨迭代次數變化的曲線，這里展示在不對齊率為0.3 時MSRC-v1 數據集上的實驗結果。如圖6 所示，在初始狀態下，視角2和視角3的類簇對齊率處于較低水平（僅略高于數據本身的樣本對齊率0.7）。隨著迭代數的增加，對齊率顯著提高，最后穩定在高于初始狀態4.5%～12%的水平。

注意到，圖6的曲線變化趨勢與圖7(b)的收斂曲線的變化趨勢基本一致：經過約3 輪迭代后，數值算法開始收斂，數據集對齊程度趨于飽和。這里提出一種提高該飽和程度的可能策略：在迭代過程中動態地調整一致性約束項的權衡系數λ。理由如下：在算法迭代初期，數據不對齊程度較高，不應強制Vv趨于一致，應設置較小的λ值；而在迭代后期，數據對齊程度有所提高，可加快Vv融合以提高其跨視角一致性，應適當增大λ值。

圖6 視角2和視角3 在MSRC-v1 數據集上的類簇對齊率變化曲線

3.4 參數穩定性與收斂性分析

本文方法共包括2 個參數：表示學習中的權衡參數λ和數據對齊中的高斯核尺度參數σ。本文按照{0.001,0.01,0.1,1,10,100,1000}的變化范圍進行網格搜索，分析聚類性能對不同參數組合的敏感程度。圖7(a)是在不對齊率為0.7的MSRC-v1 數據集上，ACC 指標關于參數λ和σ的變化分布?？梢钥闯?，在較大的參數范圍內，性能指標的變化幅度相對較小，說明本文方法具有較好的參數穩定性，從而具有較好的易用性。

為了證明本文數值算法的收斂性，以迭代次數和目標函數值分別為橫、縱坐標繪制收斂曲線。在不對齊率為0.7的MSRC-v1數據集上的實驗結果如圖7(b)所示。從圖7 中可以看出，本文數值算法具有較好的收斂性能。

圖7 參數穩定性與收斂性分析

4 結束語

面向視角非對齊數據的多視角學習問題，本文提出了一種基于多視角非負矩陣分解的學習方法。在3 個公開數據集、多種不同的視角數量和3 種不對齊率上，本文方法的聚類性能均優于8 種先進的多視角聚類方法。在此基礎上，后續研究可考慮引入核技巧擴展本文的表示學習模型，增強其非線性適應能力。此外，在視角非對齊設定下，表示學習的穩定性及相關參數的影響分析也是值得探索的后續研究方向。