單步劃分融合多視圖子空間聚類算法

張 培，祝 恩，蔡志平

國防科技大學 計算機學院，長沙 410073

傳統的聚類方法通過計算數據特征之間的相似度來對樣本進行聚類。然而僅使用單一的特征可能會存在一定的偏差或不足。隨著信息技術、數據挖掘技術等的發展，數據可以被不同類型的特征描述。例如相同語義使用多語言形式表示[1]；生物特征識別中可以使用人臉、指紋、掌紋以及虹膜等特征來唯一地標識一個人；網頁包含文本、鏈接以及視頻等多種模態的數據。這種使用不同的特征來描述的數據稱為多視圖數據。多視圖數據不僅包含每個視圖下特定信息，也包含視圖之間互相補充的信息[2]。使用多視圖數據進行聚類可以充分發揮各視圖的優勢，規避各自的局限，從而獲得更好的聚類性能。

現有的多視圖聚類算法可以被分為四類：直接連接的方法、多核聚類算法[3]、基于圖的多視圖聚類算法[4]以及多視圖子空間聚類算法[5]。多視圖子空間聚類算法通常包含基于矩陣分解的方法和基于子空間的方法。其中基于矩陣分解的方法[6-7]旨在從所有視圖學習一個統一的特征表示。而基于自表達的多視圖子空間聚類算法[8-9]在很多應用中展現了有效性和魯棒性。其關鍵問題在于學習統一的子空間表示，從而揭示多個視圖下理想的一致的聚類結構。現有的多視圖子空間聚類方法大多是將多個圖或表示矩陣融合成一致的圖或表示矩陣，即在相似度級別上融合多視圖信息。如文獻[10]通過執行矩陣分解得到一致的稀疏子空間表示。類似的，文獻[11]得到低秩和稀疏約束下的一致相似度矩陣。也有一些方法首先學習一個潛在表示，然后從潛在空間進行子空間聚類。文獻[12]通過最大化視圖之間的獨立性來編碼視圖之間的互補信息，進而得到一致的表示。與之類似的是文獻[13]，假設所有的視圖都源于一個潛在表示，通過對潛在表示進行子空間聚類得到子空間表示。

盡管這些方法在不同的場景下都取得了極大的成功，但仍存在以下問題：原始數據中通常包含噪聲和一些冗余的信息，因此直接將從原始數據中學習一致的相似圖矩陣或者表示矩陣融合可能會影響最終的聚類性能。此外，現有的方法大多為兩階段，即先進行相似度學習再應用譜聚類或者其他離散化方法得到最終的聚類結果。這樣將表示學習的過程與最終的聚類任務分離的方法會導致學到并不是最適合聚類任務的表示，從而無法得到最優的聚類性能。

本文提出了一種單步劃分融合多視圖子空間聚類算法（one-stage partition-fusion multi-view subspace clustering，OP-MVSC），將表示學習、劃分融合以及聚類過程集成在一個框架中。在這個框架中，聯合優化每個視圖的相似性矩陣、劃分矩陣以及聚類標簽。具體來說，本文首先在每個視圖上建立各自的子空間表示。不同的視圖之間聚類結構應該是類似的，基于這一假設，將每個視圖的劃分矩陣融合為一致的劃分矩陣。這種劃分級別的融合可以避免相似度級別融合中引入原始數據中的噪聲和冗余。此外，通過對一致的劃分施以旋轉矩陣可以直接得到聚類結果，避免使用額外的譜聚類或者其他離散化方法獲得聚類標簽。通過表示學習、劃分融合、譜旋轉這三個子過程的交互，它們之間互相促進，從而獲得更好的聚類結果。除此之外，本文提出一種有效的算法來解決由此產生的優化問題，并在四個廣泛使用的多視圖數據集上與一些先進的方法進行了對比實驗，證明了所提方法的有效性和先進性。

1 相關工作

1.1 符號與定義

對于矩陣A,Ai,:表示第i行,Ai,j表示矩陣A第i行、第j列處的元素。矩陣A的Frobenius 范數表示為||A||F,向量的2 范數表示為||Ai,:||2。矩陣的跡、轉置分別表示為tr(A)及AT。

定義一個有m個視圖、n個樣本的數據集為A=[A1,A2,…,Am]∈Rd×n，其中d=表示第v個視圖中特征的維度。第v個視圖的數據則表示為。此外使用粗體的1 表示元素全為1 的列向量，使用Ik表示k×k維的單位矩陣。

1.2 多視圖子空間聚類相關工作

對于一組數據來說，其數據點通常分布在潛在的低維子空間中而不是均勻分布在整個空間[10]。因此數據點可以通過低維的子空間來表示。在獲得數據的子空間結構后，可以在子空間中進行聚類來代替在整個空間中聚類。給定n個樣本的數據A={a1,a2,…,an}∈Rd×n，其中某個樣本ai可以使用與它位于同一個子空間的其他樣本的線性組合表示。選取A中的d個樣本構成字典D，那么A中每一個樣本都可以表示為D中數據點的線性組合。隨著自表達性質[14]的興起，可以使用整個數據矩陣作為字典來表示數據本身，如式（1）所示：

其中，S={s1,s2,…,sn}∈Rn×n是數據點的線性組合系數矩陣，稱為子空間表示，每個si是原始數據ai的子空間表示。約束diag(S)=0 要求S的對角線元素為0，避免數據點由自己來表示。擴展到多視圖場景,范式如下：

其中，Av表示第v個視圖的數據，Sv表示第v個視圖的子空間表示。Ω(·)為某種正則化函數，Φ(·)為某種可將多個視圖的子空間表示融合為一致表示的策略。λ＞0 是平衡參數。使用不同的正則化函數和不同的一致策略，組成了不同的多視圖子空間聚類方法。其中大部分方法在獲得一致的表示S*后，通過W=1/2(|S*|+|S*T|)得到相似度矩陣，然后進行譜分解得到劃分矩陣F，再對F使用某種聚類算法（通常是K-means）得到最終的聚類標簽。

然而真實世界的數據會有噪聲、異常點或冗余信息，這可能導致相似度矩陣質量較差，直接融合這樣充滿噪聲和冗余的多視圖相似信息會導致較差的聚類結果。且后續得到聚類標簽的過程與前面的相似度學習的過程分離，這也導致了無法得到最優的聚類性能。為了解決這些問題，本文提出一種新的單步劃分融合多視圖子空間聚類算法。

2 算法

本章介紹單步劃分融合多視圖子空間聚類方法，并給出相應的優化算法。

2.1 單步劃分融合多視圖子空間聚類算法

根據前文介紹的多視圖子空間聚類范式（2），可以得到每個視圖對應的子空間表示：

一個理想相似度矩陣中應具有如下性質：相似度矩陣中連通分量的個數等于聚類的簇的個數。根據文獻[15]可知，相似度矩陣中連通分量的個數等于對應拉普拉斯矩陣中零特征值的重數。因此，希望相似度矩陣對應的拉普拉斯矩陣的零特征值數等于聚類的簇的個數k，即rank(Lv)=n-k。自然地，希望將這個秩約束加入到式（3）中，使得Sv具有所希望的理想性質。然而直接使用rank(Lv)=n-k的秩約束會使得該優化問題難以解決。根據Ky Fan 定理[16]，可以得到=min tr((Fv)TLvFv)，其中σi(Lv)是Lv的第i小的特征值。很明顯，Lv的前k小的特征值均為0，即=0，將使得Lv的秩為n-k。因此，問題可以自然轉化為如下形式：

在式（4）中，每個視圖可以得到各自的劃分矩陣。在多視圖聚類中，基于不同視圖之間的聚類結構應該是類似的假設，即無論在哪個視圖，相似的樣本都應該被聚在同一個簇中。因此將每個視圖的劃分Fv對齊，形式化如下：

為了建立劃分矩陣與最后的聚類標簽之間的聯系，引入旋轉矩陣P∈Rk×k：

式中，γ為模糊系數。tc為1×k維的向量，其中只有第c個元素為1其余元素為0。為F*的第i行，對應第i個樣本的一致表示。yic表示第i個樣本屬于第c個簇的概率。P則建立了標簽Y和一致表示F*之間合理的關系。如果樣本i在位置c顯示出突出的結構，則對應yic有一個較大的概率值，表示樣本i較大概率屬于第c個簇。

將式（4）（5）（6）整合在一起，可以得到整個框架：

通過這種方式，相似度矩陣、一致劃分及標簽矩陣得以在一個框架中聯合優化，并且這三個過程可以互相促進，從而獲得更好的聚類結果。

2.2 優化過程

2.2.1 固定Fv、F*、P、Y，優化Sv

忽略無關項，目標函數的優化式可轉化為：

由于每個視圖都需要進行子空間表示的建立,可以對每個視圖的Sv分別進行優化。將Sv按列展開可以得到如下向量形式：

其中，Qi,j=||Fi,:-Fj,:||2，Fi,:為對應F的第i行。對S:,i求導并令導數為0 可以得到S:,i的閉式解：

2.2.2 固定Sv、Fv、P、Y,優化F*

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

2.2.3 固定Sv、F*、P、Y，優化Fv

關于Fv的優化式可以轉化為：

2.2.4 固定Sv、Fv、F*、Y，優化P

忽略其他無關項，P的優化式可以轉化為：

2.2.5 固定Sv、Fv、F*、P，優化Y

忽略其他無關項，關于Y的優化可以轉化為：

2.3 時間復雜性分析

整個算法流程如算法2 所示。在整個優化過程中，算法OP-MVSC 的計算復雜性可以分為相似圖構建、劃分融合以及譜旋轉三個子階段。其對應的時間復雜度分別為O(mn3+(m+1)nk3)、O(k3)以及O(nk2)。因此，算法2 的整體時間復雜度為O(T(mn3+mnk3+k3))，其中T為迭代次數。

算法2OP-MVSC

輸入：具有m個視圖的多視圖數據，聚類個數k，超參數λ、γ。

輸出：聚類標簽矩陣Y。

初始化：初始化Fv，隨機正交初始化F*，初始化P為k×k維的單位矩陣，初始化Y為每行只有一個位置為1 其余為0 的n×k維的矩陣

1.重復執行

2.通過式（9）來優化Sv

3.通過解式（10）來優化F*

4.通過解式（12）來優化Fv

5.通過解式（13）來優化P

6.通過解式（14）來優化Y

7.直至算法收斂

8.返回聚類標簽矩陣Y

3 實驗及結果分析

3.1 數據集介紹

本文在4 個廣泛使用的公開數據集上進行了實驗。如表1 所示，Wikipedia Articles 是一個廣泛使用的跨模檢索數據集，包含屬于10 個類的693 個樣本。將從圖像中提取128 維的SIFT 特征和從文本的隱含狄利克雷分布模型中提取的10 維特征組成多視圖數據。MSRC-v1 是一個場景識別數據集，其中有8個類，每個類有30 個樣本。從中挑選了7 個類（樹、汽車、人臉、奶牛、自行車、建筑和飛機）共210 張圖像。從每張圖像中提取多種特征組成多視圖數據集Caltech7 和Caltech20，該數據集是來源于101 類的圖像數據集，選擇其中廣泛使用的7 個類和20 個類，提取不同特征構成多視圖數據集。

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

3.2 對比方法介紹

本文將提出的OP-MVSC 與下面的方法進行對比。其中直接連接特征方法（direct）作為一種基準方法，直接將多個視圖的特征拼接在一起然后執行Kmeans得到最終的結果。

Co-reg（co-regularized）[18]方法使用協同正則化方法使得不同視圖的劃分之間達成一致，本文僅對比其中的“成對”方法。LMSC（latent multi-view subspace clustering）[13]不是在原始特征上而是在共同的潛在表示上進行數據的重建，從而得到共同的潛在子空間表示，進而執行譜聚類得到最終結果。RMKMC（multiviewK-means clustering on big data）[19]通過獲得共同聚類指示矩陣并引入?2,1范數，對輸入數據的異常值具有魯棒性。mPAC（multiple partition aligned clustering）[20]方法為每個劃分矩陣分配不同的旋轉矩陣得到統一的聚類指示矩陣。FMR（flexible multi-view representation learning for subspace clustering）[12]方法通過希爾伯特-史密斯獨立性準則（Hilbert-Schmidt independence criterion，HSIC）構造包含互補和一致信息的潛在表示，然后對潛在表示進行數據重建得到子空間表示。上述的方法，本文均按照論文中推薦的參數范圍進行網格搜索并選取最好的結果。

本文使用準確率（accuracy，ACC）和F-score兩個指標來衡量聚類的效果。其定義如下：定義TP（true positive）、TN（true negative）、FP（false positive）、FN（false negative）分別為判斷正樣本為正、判斷負樣本為負、判斷正樣本為負以及判斷負樣本為正。準確率定義為模型判斷正確的樣本占總樣本的比例，表示如下：

F-score是精確率（Precision）和召回率（Recall）的加權調和平均值，定義如下：

本文取β為1，即同等地看待精確率和召回率的重要性。其中精確率和召回率的定義分別為Precision=TP/(TP+FP)，Recall=TP/(TP+FN)。

3.3 模型分析

本文有兩個超參數{λ,γ}，λ從{1 0,20,30} 中選取，γ從1.2 至1.8 的范圍內以步長為0.2 進行選擇。以Caltech7 為例，圖1 顯示了不同的超參數對聚類性能的影響。可以觀察到在λ∈{1 0,20} 且γ∈{1 .6,1.8}的范圍內聚類效果相當穩定，同樣的結果在其他數據集上也有體現。

Fig.1 Sensitivity of parameters on Caltech7圖1 數據集Caltech7 上的參數敏感性

圖2 為在MSRC-v1 上隨著迭代次數的增加聚類性能變化曲線，可以看出，算法在有限的迭代次數內可以達到最優的性能并保持穩定。

Fig.2 Clustering performance during iterations圖2 迭代過程中的聚類性能

這也證明了從一致的表示中得到的聚類標簽對后續優化中表示的學習起到了正向引導作用，進而提高了聚類性能。在不斷的迭代中互相促進，從而達到更好的聚類性能。

3.4 實驗結果分析

對比算法在四種真實數據集中的結果如表2 和表3 所示。其中最好的結果用粗體標注，次好結果用下劃線標注。

如表2 所示，在大多數情況下，直接連接特征的方法表現出最差的性能，這表明了多視圖聚類算法探索不同視圖之間互補信息的有效性。本文提出的方法在不同數據集下的ACC均為最高，分別超過次好的方法2.16 個百分點、1.90 個百分點、7.26 個百分點以及0.54 個百分點。從表3 中可以看到，在F-score指標下，本文方法在Wikipedia Article、MSRC-v1 和Caltech7 上都取得了最佳的性能，分別超過次優2.00個百分點、6.48 個百分點、6.92 個百分點；僅在Caltech20 上略低于mPAC 方法。

相比于其他先進的方法，上述實驗結果很好地說明了本文提出的OP-MVSC 方法的有效性。將其歸因于以下兩點：（1）OP-MVSC 聯合優化子空間表示、劃分矩陣以及聚類標簽。當在某一輪迭代中產生更加準確的聚類標簽時，在下一次迭代中充分利用這種高質量的標簽來引導視圖表示和劃分的學習。通過在算法迭代中彼此促進，進而可以改進聚類性能。（2）在劃分級對多視圖信息進行融合，相對于相似度融合，這種劃分級的融合具有更少的噪聲和冗余信息，從而得到更好的聚類性能。

Table 2 Comparison of different algorithms under 4 datasets in terms of ACC表2 對比算法在4 個數據集下的ACC

Table 3 Comparison of different algorithms under 4 datasets in terms of F-score表3 對比算法在4 個數據集下的F-score

4 結束語

本文提出了一種新穎的單步劃分融合多視圖子空間聚類算法。與現有的基于相似度融合多視圖信息的方法不同，本文從更富含聚類結構信息的劃分級別進行融合，并引入旋轉矩陣直接得到聚類結果，避免了兩階段算法分離表示學習和聚類過程的缺陷。直接將表示學習、劃分融合和聚類過程統一在一個框架中，使得表示和聚類結果在迭代過程中互相促進，從而達到理想的聚類效果。多個多視圖數據集上的實驗結果驗證了本文方法的有效性和優越性。在未來的工作中，將考慮大規模多視圖聚類問題以及自適應融合的方法。