基于正交基的多視圖遷移譜聚類

王麗娟，張霖，尹明，郝志峰，蔡瑞初，溫雯

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

0 概述

聚類是一種無監督的大規模數據分析算法，在過去的幾十年中，許多經典聚類算法被提出。經典的聚類算法包含但不限于標準譜聚類［1］（Spectral Clustering，SC）、稀疏子空間聚類［2］（Sparse Subspace Clustering，SSC）和低秩表示［3］（Low-Rank Representation，LRR）等。盡管這些算法取得了較好的成果，但其僅考慮單視圖數據，忽略了來自不同的特征集或異構源的信息。

在現實生活中，目標對象通常由來自不同視圖的信息表示，即數據可以由多個不同的特征集或多個異構源來描述。例如，一幅圖像可用像素強度、梯度方向直方圖（Histogram of Oriented Gradient，HOG）和局部二值模式（Local Binary Pattern，LBP）等不同的圖像特征來描述。在生物醫學研究中，不同細胞的化學結構和反應都可以用來代表某種藥物，而序列和基因表達值可以在不同方面代表某種蛋白質［4］。多視圖數據提供來自不同視圖的豐富底層信息，只有所有視圖結合在一起才能準確、真實地表示對象。為了充分利用多視圖信息，近年來研究人員提出了許多多視圖聚類算法［5-7］。

考慮到多個視圖特征共同描述同一數據，因此不同視圖之間應該存在許多共享信息。如何將多個視圖集成在一起，從不同的視圖中提取一致的底層信息，是多視圖聚類需要重點解決的問題。基于此，研究人員提出一些有效的多視圖聚類算法，主要分為圖學習（或圖融合）和譜學習，圖學習通過學習一致性圖對多視圖數據進行聚類。文獻［8］通過學習多個單一圖，繼而將學習到的多個圖集成到具有k個分量的全局圖中。文獻［9］利用拉普拉斯矩陣上的秩約束學習一致性圖，無需后處理步驟直接從圖本身獲得聚類分配結果。譜學習通過直接學習或構建公共子空間學習一致性表示，從而獲取多視圖數據之間的一致性信息。例如，自適應加權Procrustes［5］（Adaptively Weighted Procrustes，AWP）利 用 PA（Procrustes Analysis）技術從譜嵌入中恢復了一致性聚類指標矩陣。文獻［6］提出一種結合非負嵌入和譜嵌入的多視角譜聚類（NESE）算法，該算法在統一框架中同時學習非負嵌入和譜嵌入，其中非負嵌入直接揭示了一致的聚類結果，從而提升聚類性能。文獻［10］表明，挖掘多視圖數據之間的底層一致性，對于提高多視圖聚類性能非常重要。

綜上所述，挖掘多視圖數據之間的底層一致信息是一項至關重要和具有挑戰性的工作。本文提出一種基于正交基的多視圖遷移譜聚類（Orthogonal basis-based Multiview Transfer Spectral Clustering，OMTSC）算法。OMTSC 算法同時學習每個視圖的聚類分配矩陣和特征嵌入，并將聚類分配矩陣分解為共享正交基矩陣和聚類編碼矩陣。其中正交基矩陣包含一組潛在的聚類中心，即每個多視圖樣本可以有效地分配給多個不同權重的類。同時，引入基于二部圖的協同聚類來控制和實現多視圖之間的知識遷移，發現多視圖之間的一致性信息，維護各個視圖的特征流形信息。在此基礎上，通過從正交基矩陣和特征嵌入遷移知識來獲取每個視圖聚類任務的聚類編碼矩陣，將正交基矩陣和加權聚類編碼矩陣相結合學習多視圖聚類分配矩陣，從而得到最終聚類指標。

1 相關工作

本節將介紹文中用到的符號以及遷移學習和單（多）視圖譜聚類的相關工作。

1.1 矩陣表示

在本文中，X={X(1)，X(2)，…，X(V)}表示V個視圖的數據矩陣，表示第v個視圖的數據矩陣，其中，dv表示第v個視圖的特征數目，n表示樣本總數目，對應于第v個視圖的第(i，j)個元素，I和1 表示對角線元素為1 的單位矩陣。

1.2 遷移學習

遷移學習［11-13］的目的是通過遷移源領域的知識來提高目標學習者在目標領域中的表現，其在文檔分類［11］、情感分類［14］、協同訓練［15］等許多數據挖掘領域中都取得較好的效果。協同訓練考慮在只有一小組標記樣本的情況下，通過遷移相關知識給無標記樣本，從而提高學習算法的性能。

文獻［16］基于協同訓練提出一種雙視圖譜聚類算法，即二部圖協同聚類。該算法通過在兩個視圖之間遷移相關知識，達到提升多視圖聚類性能的目的。二部圖的相似矩陣定義為：

其中：A∈?d×n為數據矩陣，d和n分別表示特征個數和樣本個數。

對應的圖拉普拉斯矩陣定義為：

其中：D1=diag(A1)；D2=diag(AT1)。

二部圖協同聚類的目標函數表示如下：

其中：向量x為特征嵌入；向量y為樣本嵌入。可將式（3）轉化為：

1.3 正交基聚類

文獻［17］提出一種無監督特征選擇算法，即同時正交基聚類特征選擇（Simultaneous Orthogonal basis Clustering Feature Selection，SOCFS）算法。該算法旨在利用目標矩陣通過正交基聚類獲取投影數據點的潛在聚類中心，繼而引導投影矩陣選擇判別特征。給出特征權重矩陣G∈?d×m，目標矩陣K∈?m×n，SOCFS正交基聚類部分表示如下：

其中：目標矩陣K可直接對投影的數據點GTA進行聚類。因此，允許K擁有額外的自由度，將其分解為正交基矩陣BK∈?m×c和聚類指標矩陣EK∈?n×c，即K=BET。施加在BK上的正交約束保證了BK的每一列是獨立的，即BK由投影的數據點GTA的正交基構成。此外，BK的列可以看作是相應聚類中心的方向。施加在EK上的正交和非負約束使得EK的每一行只有一個非零元素。因此，可以利用K=BET來尋找潛在的聚類中心，從而更好地分離聚類。

1.4 單視圖譜聚類

本節主要介紹通用的單視圖譜聚類算法［15］。假設存在n個數據點，需將其分成c個類。譜聚類第1 步是構造一個無向相似圖G={X，W}，其中，X∈?d×n為頂點集，W∈?n×n為對應的相似矩陣，W中的元素wi，j定義為每對頂點(xi，xj)的相似性，可通過式（7）計算：

其中：N(x*)為搜索x*的k近鄰函數。

通過求解一個特征值分解問題得到原始數據的譜嵌入，即：

其中：P∈?n×c為聚類分配矩陣；L∈?n×n為圖拉普拉斯矩陣，可由L=I-W定義。求解得出的最優P是L最小的k個特征值對應的特征向量。最后，對聚類分配矩陣P進行k-means 聚類，返回k-means 的聚類結果作為最終指標。

1.5 多視圖譜聚類

其中：α(v)是一個非負歸一化系數，可以反映不同視圖的權重；r是一個標量，用于控制權重在不同視圖上的分布；L(v)為第v個視圖的圖拉普拉斯矩陣；F為求解得出的一致性嵌入，即多視圖聚類分配矩陣。

在實際應用中，數據往往由多個不同的特征集或多個異構源來描述，即多視圖數據。單視圖譜聚類［15，20-22］并不能獨立地處理多視圖數據，并且聚類性能一般。為解決這一問題，近年來研究人員在單視圖聚類的基礎上提出多視圖聚類算法。多視圖譜聚類通過最大化多視圖一致性來提高聚類性能。因此，如何最大化多視圖一致性成為一個關鍵問題。

現有的多視圖聚類算法［5-7］通過學習一致性嵌入或者一致性圖來挖掘多視圖一致性，但其存在不足之處：一是多視圖一致性信息挖掘不充分；二是無法有效地平衡不同視圖的質量差異。本文OMTSC算法與現有算法的不同之處在于：OMTSC 分解一致性表示，即聚類分配矩陣，分別學習正交基矩陣和聚類編碼矩陣。一方面，正交基矩陣可以捕獲并儲存多視圖一致性；另一方面，聚類編碼矩陣通過加權融合，可更好地平衡不同視圖的質量差異。并且OMTSC 算法利用二部圖充分挖掘多視圖數據的一致性和多樣性，通過多樣性提升一致性的學習性能。

本文工作的主要貢獻如下：

1）提出一種基于正交基的多視圖遷移譜聚類（OMTSC）算法。該算法在一個統一框架中學習聚類分配矩陣和特征嵌入。

2）聚類分配矩陣可分解為正交基矩陣和聚類編碼矩陣。正交基矩陣保留潛在的聚類中心，并捕獲多視圖數據之間的一致性信息。

3）OMTSC 算法學習特征嵌入，借助其多樣性并最大限度地優化多視圖一致性。

2 OMTSC 算法

為有效地挖掘多視圖數據之間的一致性，本節提出基于正交基的多視圖遷移譜聚類（OMTSC）算法。

2.1 多視圖遷移譜聚類

OMTSC 算法沿用文獻［17］采用正交基聚類發現潛在的聚類中心的思想，可將每個視圖的聚類分配矩陣P分解為兩個子矩陣，即共享正交基矩陣B∈?c×c和一個聚類編碼矩陣E(v)∈?n×c。聚類分配矩陣可表示為P(v)=E(v)B，則傳統多視圖譜聚類可以演化為以下形式：

其中：為第v個視圖的歸一化圖拉普拉斯矩陣；W(v)為第v個視圖的相似矩陣；D(v)=diag(W(v)1)。對聚類編碼矩陣施加的正交約束促使E(v)的每一行只有一個元素。E(v)的每一行元素選擇了B中的一行，這是一個將多個樣本分配給不同聚類的過程。對正交基矩陣B施加的正交約束促使B的每一行相互獨立。因此，本文利用B來細化潛在的聚類中心，從而捕獲多視圖數據之間的一致性信息，以獲得更好的聚類性能。

OMTSC 算法為更好地學習多視圖一致性，通過優化學習到的正交基矩陣B，并致力于進一步細化潛在的聚類中心。本文為每個視圖構建對應的特征嵌入，其中k為降維數目。受文獻［16］采用基于二部圖協同聚類來控制和實現兩個任務之間的知識遷移的啟發，OMTSC 引入二部圖協同聚類，并將多個視圖連接在一起。不同于二部圖協同聚類算法，OMTSC 適用于多視圖聚類任務。考慮到B是多視圖數據的共同聚類中心，它可以在多個視圖之間進行遷移。B可將在上一視圖捕獲到的一致性知識遷移到下一視圖，從而促進下一視圖的學習和優化。同時，OMTSC 通過從正交基矩陣B和特征嵌入A(v)遷移知識來獲取并優化每個視圖聚類任務的聚類編碼矩陣E(v)。其相關模型如下：

在多視圖之間遷移的正交基矩陣B，基于多視圖數據一致性原則，可以促進一致性信息的學習，多視圖譜聚類任務可以從共同聚類中心學習的角度相互遷移一致性知識。以二部圖為橋梁，B可將一致性知識遷移給A(v)，從而促使當前視圖更好地學習A(v)。得益于協同聚類，A(v)可從多視圖數據中提取重要特征。具有群稀疏約束的A(v)可提升處理每個視圖的帶噪和高維特征的能力，同時提高被提取特征的多樣性和完整性。在A(v)提取的多樣性信息的基礎上，B可通過二部圖有選擇性地提取多視圖一致性知識，從而進一步細化潛在的聚類中心。此外，從A(v)和B遷移知識給E(v)，有利于優化E(v)。同時，E(v)借助其特異性，有效提升多視圖一致性。

其中：λ為每個視圖的譜聚類與協同聚類目標之間的權衡；μ為稀疏因子。當λ和μ設置為0 時，該模型將退化為具有共同聚類中心的多視圖譜聚類。現有的多視圖聚類算法［5-7］通過學習一致性嵌入或者一致性圖來挖掘多視圖一致性。其不足之處在于：一是多視圖一致性信息挖掘不充分，MVGL 算法［8］和MCGC 算法［9］由于沒有去除冗余信息或考慮噪聲矩陣，將對學習到的一致性圖造成影響；二是無法有效地平衡不同視圖的質量差異。譜聚類的性能在很大程度上取決于相似矩陣的質量。Co-Reg 算法［23］完全忽略了不同視圖相似矩陣之間的質量差異，AASC 算法［24］為每個視圖分配了一個特定的權重，但這并不能很好地解決不同相似矩陣之間的質量差異。由于譜嵌入具有嚴格的一致性約束，AASC 算法很有可能學習到較差的譜嵌入。本文提出的OMTSC 算法旨在解決上述問題。

在多視圖聚類任務中，正交基矩陣B迭代遷移一致性知識，聚類編碼矩陣E(v)對單個視圖聚類任務進行編碼。一方面，B可捕獲并儲存多視圖一致性信息，形成潛在聚類中心；另一方面，加權聚類編碼矩陣可更好地平衡不同視圖的質量差異。特征嵌入A(v)和B在二部圖上相互遷移知識，從而相互促進彼此的學習和優化。

2.2 模型優化

本節將主要探討對OMTSC 算法模型的優化。顯而易見，直接解決問題式（14）是一項具有挑戰性的工作，由于它是非凸的，因此本文采用一種交替方向策略來優化多變量問題。首先固定B、A(v)和α(v)更新E(v)，然后固定E(v)、A(v)和α(v)更新B，繼而固定E(v)、B和α(v)更新A(v)，最后固定E(v)、B和A(v)更新α(v)。重復以上步驟直至目標模型收斂。

下面簡單介紹更新的過程：

首先明確更新E(v)和B的重點，由于對E(v)和B施加正交約束，因此E(v)和B實際上是位于Stiefel流形上，這個問題可以通過對流形的反復更新來解決，如果E(v)和B不在流形上，則通過更新其在流形上的投影來求解。在迭代過程中，Stiefel 流形由以下命題定義：

命題1假設一個秩為p的矩陣Z，Z在Stiefel 流形上的投影可以定義為：

引入一個變量S來分離上述問題，即：

針對上述問題，本文采用ADMM 算法，其增廣拉格朗日形式如下：

其中：Y是拉格朗日乘數。

然后對于下面問題：

有封閉（closed-form）解，即：

算法1基于正交基的多視圖遷移譜聚類

3 實驗

本節選用3 個數據集進行實驗，并同時與9 種聚類算法進行比較，以此評估OMTSC 算法的聚類性能。最后分析OMTSC 算法的時間復雜度、收斂性和參數靈敏性。

3.1 數據集

本文選用3 個真實數據集來評估多視圖數據聚類的性能。實驗數據集包括人臉、圖像和文本數據。數據集詳細信息如表1 所示。

表1 數據集信息Table 1 Introduction to datasets

ORL［27］是人臉識別領域流行的人臉數據庫，共有400 個樣本，分為40 個類，可由3 個視圖描述，分別是強度特征、LBP 特征和Gabor 特征。

WikipediaArticles 可分為30 個類，由于其中一些類很少，因此選取其中10 個最受歡迎的類，選取的數據集共有693 個樣本。

COIL20［28］是一個圖像數據集，共有1440幅圖像，可分為20類，對于每幅圖像提取3 個不同的特征向量，包括強度特征、LBP 特征和Gabor 特征。

3.2 對比算法

本文選用1 種單視圖聚類算法和8 種多視圖聚類算法，與OMTSC 算法進行比較。下文簡要介紹對比算法：

1）SC-Best［15］。SC-Best 算法對每個視圖中的特征進行標準的譜聚類，并由實驗者手動選擇最佳的聚類性能作為最終的聚類結果。

2）CoReg SPC［23］。該算法通過對聚類假設進行共正則化，使不同的視圖保持一致。

3）AASC［24］。該算法將相似矩陣聚集在一起進行譜聚類。

4）RMSC［29］。該算法為多視圖聚類恢復了一個共享的低秩轉移概率矩陣。

5）MVGL［8］。該算法從不同的單視圖中學習全局圖。由于秩約束，因此聚類指標直接由全局圖獲得。

6）MVGC［9］。該算法利用拉普拉斯矩陣上的秩約束學習一致性圖，并利用拉普拉斯矩陣直接獲取聚類標簽。

7）AWP［5］。該算法利用PA技術從譜嵌入中恢復一致性聚類指標矩陣。

8）WMSC［7］。該算法利用不同視圖的歸一化拉普拉斯矩陣的特征向量張成子空間之間的最大標準角，它可衡量不同視圖聚類結果之間的差異性。因此，最小化標準角可以為所有視圖帶來更好的聚類一致性。

9）NESE［6］。該算法在統一框架中同時學習非負嵌入和譜嵌入，其中非負嵌入直接揭示了一致的聚類結果，從而提升聚類性能。

本文對每種算法分別進行了10 次實驗，通過比較各評估指標的均值和標準差對比聚類性能。所有算法的聚類結果由3 個評估指標測量：即聚類精度（Accuracy，ACC）、歸一化互信息（Normalized Mutual Information，NMI）、調整蘭特指數（Adjusted Rand Index，ARI）。對于每個評估指標，指標值越大，結果越好。

3.3 實驗結果與分析

3 個數據集的聚類結果如表2～表4 所示，其中，粗體字體是最優結果，下劃線字體是次優結果，表中數值為均值±標準差。SC-Best 是SC 在單一視圖下得到的最佳結果。

表2 不同算法在WikipediaArticles 數據集上的聚類結果Table 2 Clustering results of different algorithms in WikipediaArticles dataset

表3 不同算法在COIL20 數據集上的聚類結果Table 3 Clustering results of different algorithms in COIL20 dataset

表4 不同算法在ORL 數據集上的聚類結果Table 4 Clustering results of different algorithms in ORL dataset

由表2～表4 可以得出以下結論：

1）在以上3 個數據集中，OMTSC 算法的聚類性能均優于其他算法。特別是在與WikipediaArticles、ORL 數據集上的次優結果相比，OMTSC 算法在ARI指標上的提升超過了近5%。

2）值得注意的是大多數對比算法在不同的數據集上的性能并不穩定。比如NESE 算法在COIL20數據集上取得次優結果，然而在另外兩個數據集上的性能并不理想，而OMTSC 算法在不同數據集上保持著最優結果。這是因為NESE 算法是直接學習一致性嵌入，而OMTSC 算法將一致性嵌入分解為公共正交基矩陣和聚類編碼矩陣，考慮多視圖的一致性和不同視圖的特異性，并在模型優化過程中促進兩者的相互學習。同時，利用每個視圖特征嵌入的多樣性來捕獲多視圖潛在的一致性。

3）與SC-Best 算法和CoReg 算法相比，OMTSC算法可以充分挖掘多視圖一致性，捕獲潛在聚類中心，并有效消除視圖中的噪聲和不重要信息，從而提升其聚類性能。其中，SC-Best 算法需要對每個視圖分別進行聚類，然后手動選擇最佳性能視圖，故不適用于實際應用。而CoReg 算法完全忽略了視圖相似矩陣之間的質量差異，對學習到的一致的特征向量集有很大影響。OMTSC 算法考慮了不同視圖的顯著差異，它通過學習加權聚類編碼矩陣，可以很好地平衡不同視圖相似矩陣之間的質量差異。

4）ORL和COIL20數據集都有3個視圖，其中視圖的特征數目大多超過3 000 個。由于ORL 和COIL20 數據集的高維性，其中存在一些噪聲和冗余信息。OMTSC 算法基于群稀疏約束的特征嵌入，可有效消除視圖中的噪聲，降低視圖中高維和噪聲特征對聚類性能的影響。可以看出，與ORL數據集上的MVGL 算法相比，OMTSC 算法在ACC上的提升超過了近10%；與COIL20 數據集上的MCGC 算法相比，OMTSC 算法在AR 上的提升超過了近10%。這可能是因為MVGL 算法和MCGC算法沒有去除冗余信息或噪聲矩陣。

綜上所述，本文提出的OMTSC 算法在聚類性能及穩定性上，均優于其他先進的多（單）視圖聚類算法。

3.4 時間復雜度分析

不同算法的時間復雜度如表5 所示。由算法1可知，OMTSC 算法可分為2 個子問題。對于第1 個問題，涉及計算一個正交基矩陣B和多個聚類編碼矩陣E(v)的投影，其計算包括矩陣乘積和加法，時間復雜度為O(n2k)。為了尋求投影，需要對E(v)和B進行奇異值分解。已知對于m×n矩陣，奇異值分解的時間復雜度為O(min{mn2，m2n})。因此，計算正交基矩陣B和聚類編碼矩陣E(v)及投影的時間復雜度為O((t1+t2)(n2k))。其中t1和t2分別是E(v)和B單次優化過程的更新迭代次數。對于第2 個問題，OMTSC 算法計算新的特征嵌入A(v)的時間復雜度為O(n2k)，新的變量S的時間復雜度為O(max(n2D，n3)k)，Y的時間復雜度可忽略不計。因此，OMTSC 算法優化迭代部分的總時間復雜度為O(t3((t1+t2)n2k+max(n2D，n3)k))，其中t3是優化過程的總迭代次數。

表5 不同算法的時間復雜度Table 5 Time complexity of different algorithms

3.5 參數靈敏性

在OMTSC 算法中存在有3 個參數：λ為每個視圖的譜聚類與協同聚類目標之間的權衡；μ為稀疏因子；r是一個標量，用于控制權重在不同視圖上的分布。根據ORL 和WikipediaArticles 數據集的實驗結果，分析以上參數對聚類評估指標ACC 的敏感性，其結果如圖1 所示。

1）當固定r=2 時，將參數λ和μ設置為［0.000 1，10 000］，結果如圖1（a）、圖1（b）所示。可以看出，在ORL 和WikipediaArticles 數據集中，當λ=［0.000 1，1］和μ=［0.000 1，10 000］時，算法能取得最優性能。由此可知，參數λ對OMTSC 算法的性能較敏感，參數μ對OMTSC 算法的性能不敏感。

2）在ORL 數據集上，固定參數λ=0.1和μ=0.001；在WikipediaArticles 數據集上，固定參數λ=1和μ=1。同時，將參數r設置為［2，10］。結果如圖1（c）、圖1（d）所示。由此可知，在這兩個數據集上，當r=2 時算法能取得最優性能。

圖1 不同參數下OMTSC 算法在ORL 和WikipediaArticles 數據集上的聚類性能Fig.1 Clustering performance of OMTSC algorithm on ORL and WikipediaArticles datasets with different parameters

3.6 收斂性分析

本節采用ORL 和WikipediaArticles 數據集來評估OMTSC 算法的收斂性。當更新E(v)和B時，對應的更新問題分別是E(v)和B的連續函數，故只要步長t1和t2足夠小，其值便可單調遞減。一般來說，步長t1和t2越小，所需的迭代次數就越大。本文設定t1=t2=1。根據式（14），ADMM 算法［30-31］給出詳細的解釋，并說明了如何保證該算法的收斂性。

4 結束語

本文提出了一種基于正交基的多視圖遷移譜聚類（OMTSC）算法。將每個視圖的聚類分配矩陣分解為正交基矩陣和一個聚類編碼矩陣，正交基矩陣通過捕獲并儲存多視圖一致性，獲取多視圖數據的潛在聚類中心。同時，基于加權聚類編碼矩陣，OMTSC 可以更好地平衡不同視圖之間的質量差異。通過引入協同聚類控制和實現知識遷移，在二部圖上同時學習優化特征嵌入和聚類分配矩陣。在此基礎上，利用特征嵌入的多樣性最大化多視圖一致性，學習最優的潛在聚類中心，進而提升多視圖聚類性能。此外，本文設計一種交替迭代優化算法對目標函數進行優化，在3 種真實基準數據集上的實驗結果驗證了該算法的有效性。下一步將考慮構造自適應圖，以更好地發現數據的內在關系，提升聚類性能。