動態融合的多視圖投影聚類算法

姜凱彬，周世兵，錢雪忠，管嬌嬌

江南大學 人工智能與計算機學院，江蘇 無錫214122

聚類是機器學習中的一個重要課題，旨在發現數據的底層結構。在許多現實世界的應用程序中，數據通常是從不同的來源生成的。例如，信號可以從多個傳感器獲得，圖像可以由多個特征描述符描述。所有這些都稱為多視圖數據[1]。因為不同視圖可以捕捉不同數據視角，存在不同的統計特性，傳統單視圖的聚類方法無法充分反映多視圖聚類結構的本質。因此通過集成異構和互補的信息的無監督多視圖聚類方法開始變得流行。

簡單地將所有特征直接連接成單個視圖，然后對單個視圖數據進行聚類，可能不會獲得比單獨使用單個視圖的傳統方法更好的性能。在過去十年中，許多考慮不同視圖多樣性和互補性的先進多視圖聚類算法被提出，大致可分為多視圖協同訓練算法[2]、多視圖多核聚類算法[3]、基于圖的多視圖聚類算法[4]、基于子空間的多視圖聚類算法[5]。

在這些方法中，采用多視圖譜聚類可以在任意形狀的數據集上聚類并收斂得到全局最優解。因此，多視圖譜聚類能更好地探索多視圖數據的非線性結構，在實踐中常優于其他多視圖聚類方法。文獻[2]開發了一種使用線性核來最小化不同譜嵌入之間的不一致并對多個分區進行正則化的方法。但這種方法不能區分不同視圖的可靠性，容易被噪聲較多的視圖所干擾。為了區分不同視圖對于聚類結果的影響，文獻[6]提出了自適應加權的多視圖譜聚類方法。文獻[7]提出一種從多個視圖中學習一個具有稀疏結構的一致相似矩陣，然后進行單獨聚類的多視圖譜聚類算法。為了避免額外的聚類步驟帶來的不確定性，文獻[8]提出一種基于非負矩陣分解的松弛全局相似性矩陣約束的多視圖聚類算法。上述聚類方法成功解決了低維數據中的聚類問題。為了處理高維數據，文獻[9]提出了兩種無參數加權投影聚類方法，可同時進行結構圖學習和數據降維。

雖然這些算法在不同的場景下取得了較好結果，但仍存在以下問題：（1）以往許多工作都集中在原始數據上，而忽略了高維數據引入的噪聲和冗余信息。當高維數據直接用于聚類任務時，可能會導致重要信息的丟失以及算法性能的下降。（2）現有方法大都預先構造一個共識圖，然后利用該固定的圖執行聚類任務，這種兩步的分離策略可能會造成聚類結果的次優解。（3）通過引入額外的超參數來解決不同視圖在模型中產生的影響，可能會導致模型復雜度的提高。

為了解決上述問題，本文提出了一種動態融合的多視圖投影聚類算法（dynamic-fusion multi-view projection clustering algorithm，DFMPC），將自適應降維圖學習、無參數的自權重圖融合和譜聚類整合在同一框架中，聯合優化投影矩陣、相似性矩陣、共識矩陣以及聚類標簽。具體來說，首先將高維數據投影到低維子空間，建立不同視圖的相似圖。基于不同視圖具有相同的底層聚類結構這一假設，在動態融合過程中，將共識矩陣與所有相似度矩陣對齊一致，自動學習各視圖的權重并對得到的共識矩陣的拉普拉斯矩陣施加秩約束，直接獲得聚類結果。與以往引入需要人工調整的超參數不同的是，本文引入的啟發式超參數會隨著每次優化迭代自動調整。此外，本文設計了一種有效的交替迭代方法來求解聯合優化問題。在人工數據集和真實數據集上得到的實驗結果表明該算法的優越性。

1 相關工作

本章介紹了多視圖聚類方法的基本符號定義，并回顧了傳統多視圖聚類算法的基本形式。

1.1 符號與定義

定義一個具有m個視圖、n個樣本的多視圖數據集為X=[X1,X2,…,Xm]∈Rdv×n，其中dv代表第v個視圖的維度。對于一個矩陣Xv來說，和分別表示矩陣第i行第j列元素以及第j列向量。矩陣X的Frobenius 范數、跡和轉置分別表示為||X||F、tr(X)和XT。向量x的第2 范數為||x||2。此外，I表示單位矩陣，1表示元素全為1的列向量。

1.2 多視圖聚類

2 算法模型

本章在上文介紹的基礎上，提出了本文的算法模型，并給出了模型的優化求解算法。

2.1 動態融合的多視圖投影聚類算法

鑒于子空間學習在高維數據處理中的優越性，本文在前文介紹的式（1）的基礎上，將原始數據Xv投影到低維子空間，從具有盡可能少的噪聲和冗余的低維子空間中學習相似度矩陣。其對應的低維子空間的自適應圖學習優化目標如式（3）所示：

在多視圖學習中，考慮到每個視圖的相似度圖都是共識圖的擾動，以及為了避免低質量視圖的影響，讓共識圖更好地捕捉隱藏在多視圖數據中的真實樣本相似性，本文通過衡量不同視圖的重要性來輸出最終的共識表示，并期望低維子空間中的共識矩陣A可以將所有相似度矩陣S一致對齊。在此基礎上，自權重融合機制如式（4）所示：

其中，權重αv代表不同視圖的重要性，可以采用反向距離加權方案[6]得到權重αv，具體公式如下：

此時動態融合得到的共識矩陣A并不能直接獲得最終聚類結果，還需要額外的聚類步驟。由文獻[13]可知，A的拉普拉斯矩陣LA的特征值0的重數r等于A的圖中連通分量數。為了使動態融合得到共識矩陣的數據點精確聚集成c個簇，即rank(LA)=n-c，希望對共識矩陣A的圖拉普拉斯矩陣施加秩約束，使A達到理想的效果。但由于LA依賴于目標矩陣A并且rank(LA)=n-c也是非線性的，直接引入秩約束會使得優化問題難以求解。根據Ky Fan’s定理[14]，可以得到式（6）：

最后，整合式（3）、式（4）、式（6），得到動態融合的多視圖投影聚類算法模型的目標函數：

通過這種方式，可以同時研究投影矩陣、相似矩陣、共識矩陣、權系數和譜嵌入矩陣，在統一的優化框架下聯合學習自適應圖、自權重圖融合和聚類標簽。具體來說，(Wv)TXv(Xv)TWv將正交約束應用于散射矩陣進行低維子空間學習，建立不同視圖的相似圖S，緩解了維數災難，保留了數據有效信息。融合過程中共識矩陣A自動學習各S視圖的權重，學習到的A返回更新各視圖的相似矩陣S。共識矩陣的拉普拉斯矩陣LA上的秩約束也適用于約束共識矩陣中連通分量的個數（等于所需的簇數c），直接獲得聚類結果。

2.2 模型優化

2.2.1 固定Wv、A、F，優化Sv

關于初始化相似度矩陣，去掉其他無關項，每個視圖初始化相似度矩陣優化式可以轉化為：

由式（9）得到目標函數的拉格朗日函數：

其中，η和ξ是拉格朗日乘子。根據KKT（Karush-Kuhn-Tucker）條件[15]，求解得到式（10）中初始化相似度矩陣Sv的最優解為：

然而，關于迭代優化過程中的相似度矩陣，去掉其他無關項，優化式可以轉化為：

同理，按照求解式（8）的方法求解式（12），從而得到相似度矩陣Sv的最優解為：

2.2.2 固定Sv、A、F，優化Wv

去掉其他無關項，關于Wv優化式可以轉化為：

2.2.3 固定Sv、Wv、F，優化A

去掉其他無關項，關于A優化式可以轉化為：

為了加速計算，文獻[16]中提出的有效迭代算法使A完全稀疏。定義vi是一個向量并且令其第j個元素vij=，A的最優解可化簡為：

2.2.4 固定Sv、Wv、A，優化F

去掉其他無關項，關于F優化式可以轉化為：

F的最優解通過對LA進行特征值分解，選擇c個最小非零特征值對應的c個特征向量得到。

2.2.5 優化αv、β、λ

對于權重系數αv的更新，在式（5）中已經給出，它依賴于A和Sv。而傳統方法的參數β、λ值可能從0 到無窮大，很難調整，因此本文以啟發式的方法進行更新優化[17]，避免了選擇參數的不確定性，能較好地保留數據結構信息且可以得到更好的性能。對于參數β，在不失普遍性的情況下，假設式（13）中gi1,gi2,…,gin從小到大排列，若限制si有k個非零項，可以得到sik>0和si,k+1=0。此外，還要對式（13）施加=1 正則化約束。為了得到具有k個非零值的最優稀疏si，考慮數據的局部性，β可設置為：

而λ的初始值設為1，該值在每次迭代中自動調整。若在迭代過程中A的連通分量數小于簇的個數c，則λ變為兩倍；反之，則λ減少一半。

2.3 時間復雜度分析

整個算法流程如算法1 所示。在整個優化過程中，所提出的DFMPC算法的時間復雜度主要由三部分組成：相似圖構造、圖融合和譜聚類。其對應的復雜度分別為O(mnd+4nd2+d3)、O(n3+mn)以及O(cn2)。其中m代表視圖數，d代表特征數，c代表聚類數。由于n?m并且n?c，DFMPC 算法的時間復雜度可以表示為O(4nd2+d3+n3)。

算法1DFMPC

輸入：具有m個視圖的多視圖數據集{Xv}mv=1，聚類個數c，初始啟發式超參數λ。

輸出：共識矩陣A∈Rn×n及聚類結果。

3 實驗研究

本文在2 個人工數據集、8 個圖像和文檔真實數據集上進行了實驗，同時與目前已有的一些先進算法進行比較，驗證本文提出的DFMPC算法的優越性。

3.1 人工數據集實驗

本節選取兩組人工數據集RandomGaussian數據集和TwoMoon 數據集進行實驗，其中兩組人工數據集介紹如下：

（1）RandomGaussian數據集：兩個視圖都由中心分別為(0,1)和(-1,0)的二維兩高斯分布數據組成，每個類有100個樣本點，每個類的協方差矩陣為

（2）TwoMoon 數據集：兩個視圖分別通過添加0.12%的隨機高斯噪聲疊加彎月的形狀生成，每個類有100個樣本點。

由于頁面空間限制，本文只展示DFMPC在每個人工數據集上單個視圖的聚類過程。圖1 顯示了RandomGaussian 數據集和TwoMoon 數據集的第一個視圖的聚類過程。圖1（b）展示出不同視圖初始的相似矩陣構造圖，可以看到兩個類簇是有連接的。圖1（c）展示出不同視圖迭代學習后的相似矩陣構造圖。可以看出一些有噪聲的相似度邊緣被刪除，而一些可信的相似度邊緣被加強，這表明學習得到的共識矩陣可以有效改進相似度矩陣。但兩個類簇此時并未完全分離。圖1（d）展示出不同視圖最終學習到的共識矩陣構造圖。由于本文算法可以利用不同視圖的互補信息，對不同視圖中難以分離的點進行更為有效的分離從而得到完全分離的兩個類簇。

圖1 DFMPC在人工數據集上的聚類結果Fig.1 Clustering results of DFMPC on artificial datasets

總的來說，不同視圖的相似矩陣和自加權得到的共識矩陣的學習可以相互加強，彼此促進，形成一種動態融合的增強效果，進而得到一個擁有最佳的底層聚類結構的共識矩陣。

3.2 真實數據集實驗

為了全面評估DFMPC 算法對不同的多視圖數據集的兼容性和有效性，本節在表1所示的8個真實數據集上，與7種現有算法進行了實驗比較。

表1 數據集介紹Table 1 Introduction of datasets

8 個多視圖數據集分別是：來源于文獻[6]的Caltech101-7、Caltech101-20，來源于Clément Grimal（http://lig-membres.imag.fr/grimal/data.html）的Newsgroups（NGs）以及來源于文獻[8]的BBCSport、3sources、UCI、MSRCv1和ORL。

用于比較的7 種多視圖譜聚類算法分別是：SC_best、Co-reg（co-regularized）[2]、SwMC（self-weighted multiview clustering）[6]、SwMPC（self-weighted multiview projected clustering）[9]、MCLES（multi-view clustering in latent embedding space）[8]、MSC_IAS（multiview subspace clustering with intactness-aware similarity）[10]和GFSC（multi-graph fusion for multi-view spectral clustering）[18]。其中SC_best方法是將本文算法涉及到的譜聚類算法在多視圖數據集的每個單視圖上執行，然后選取最佳單個視圖結果。

對比方法參數根據原始論文中的建議進行調整，以產生最佳結果。在實驗中，算法精度為20次運行結果的平均值和標準差。采用了4 種常用的評價指標，即準確度（accuracy，ACC）、歸一化互信息（normalized mutual information，NMI）、調整蘭德指數（adjusted Rand index，ARI）和純度（purity，PUR）。對于這些度量，值越高表示聚類性能越好。表2 至表5報告了8個真實數據集的詳細聚類結果，粗體值代表最佳性能，其中→0→0 表示均值和標準差非常接近于0。

表2 不同算法在數據集上的ACCTable 2 ACC of different algorithms on datasets 單位：%

在某些情況下，基于單視圖基線的SC_best方法比一些多視圖基線方法稍好，這表明探索多視圖數據仍然需要良好的多視圖聚類技術。相比之下，本文提出的DFMPC 方法表現出更好的性能。這主要是因為DFMPC采用了動態圖融合和自加權策略，學習到了更精確的一致特征表示。

表3 不同算法在數據集上的NMITable 3 NMI of different algorithms on datasets 單位：%

表4 不同算法在數據集上的ARITable 4 ARI of different algorithms on datasets 單位：%

表5 不同算法在數據集上的PURTable 5 PUR of different algorithms on datasets 單位：%

DFMPC 在ACC、NMI、ARI 和PUR 四個指標上都明顯優于Co-reg經典協同訓練多視圖方法。相比之下，DFMPC能更好區分不同視圖的可靠性。

基于圖的SwMC 方法在3sources 和Caltech101-20 數據集的ARI 指標分別比DFMPC 高7.21 個百分點和10.6個百分點，但在其他數據集中DFMPC表現更好。這表明通過聯合學習單個圖和統一圖，DFMPC可以融合所有視圖學習更好的一致特征表示。

多數真實數據集上的結果表明，DFMPC 算法優于MSC_IAS、SwMPC、MCLES 和GFSC 多視圖子空間聚類方法。這是因為DFMPC 對高維數據投影降維，并用非參數自加權方法提高了聚類效果。

3.3 收斂性分析

為了驗證DFMPC 算法的收斂性，圖2 顯示了8個真實數據集的目標函數值的收斂曲線，x軸和y軸分別表示迭代次數和相應的目標值。目標函數值與迭代次數成反比，目標函數值在10 次迭代內急劇下降達到最小值并趨于穩定。這表明DFMPC 收斂效率很高。

圖2 DFMPC在8個數據集上的收斂曲線Fig.2 Convergence curves of DFMPC on 8 datasets

3.4 魯棒性分析

本節通過向不同維度真實數據集添加均值為0，方差0到0.5（步長為0.05）不同強度的隨機噪聲來驗證算法的魯棒性。由于頁面空間限制，只展示了4種效果較好的多視圖聚類算法在ORL 數據集的魯棒性。如圖3 所示，隨著噪聲的增加，所有算法的性能都會下降，但DFMPC的性能在絕大多數情況下領先其他算法并且算法性能增益更為顯著。當隨機噪聲方差從0 增到0.5時，DFMPC 與SwMC 的結果相比，在ACC、NMI、ARI 和PUR 的性能增益從2.00、3.29、1.36、1.50個百分點提高到14.00、4.55、26.50、15.25個百分點。與MCLES算法相比，DFMPC的4個指標性能增益從5.50、6.35、6.83、6.00個百分點提高到26.00、16.21、34.78、26.69個百分點。與SwMPC算法相比，DFMPC 的4 個指標性能增益從5.05、4.53、4.76、3.70 個百分點提高到17.27、13.22、28.27、18.50個百分點。這些結果表明，當數據集含有噪聲時，正交約束應用于散射矩陣進行低維子空間學習的DFMPC 方法能夠抑制噪聲并保持良好的聚類性能，具有良好的魯棒性。

圖3 ORL數據集上4種多視圖方法的魯棒性比較Fig.3 Robustness comparison of 4 multi-view algorithms on ORL dataset

3.5 可視化分析

為了更直觀地觀察DFMPC算法的聚類性能，本文采用一種非線性降維的t-分布式隨機鄰近嵌入（tdistributed stochastic neighbor embedding，t-SNE）算法[19]，將每個視圖的原始特征和由DFMPC 得到的一致相似特征映射到2D空間，使樣本點在2D空間中被可視化。由于頁面空間限制，本文只提供了3sources 和NGs 數據集的可視化結果，具體如圖4 所示，其中不同的顏色表示不同的類別。本文方法可以清楚地揭示底層的聚類結構，即動態融合得到的一致相似表示比每個視圖的原始特征更能體現良好的聚類結構。這進一步證實了DFMPC算法的有效性。

圖4 t-SNE在3sources和NGs數據集上的可視化結果Fig.4 Visualization results of t-SNE on 3sources and NGs datasets

4 結束語

本文提出了一種新的動態融合的多視圖投影聚類算法，在統一的優化框架下聯合學習自適應圖、無參數的自權重圖融合和精確的聚類標簽。該算法可以同時研究投影矩陣、相似矩陣、共識矩陣和聚類標簽，在低維空間上得到清楚的底層聚類結構。最后，直接從動態融合得到的最佳共識矩陣得到聚類結果。在人工數據集和真實數據集上的實驗證明了本文算法的有效性和良好性能。