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

張 培，祝 恩，蔡志平

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

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

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

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

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

1 相關(guān)工作

1.1 符號與定義

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

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

1.2 多視圖子空間聚類相關(guān)工作

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

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

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

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

2 算法

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

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

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

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

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

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

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

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

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

2.2 優(yōu)化過程

2.2.1 固定Fv、F*、P、Y，優(yōu)化Sv

忽略無關(guān)項，目標函數(shù)的優(yōu)化式可轉(zhuǎn)化為：

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

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

2.2.2 固定Sv、Fv、P、Y,優(yōu)化F*

去掉其他無關(guān)項，關(guān)于F*的優(yōu)化式可轉(zhuǎn)化為：

2.2.3 固定Sv、F*、P、Y，優(yōu)化Fv

關(guān)于Fv的優(yōu)化式可以轉(zhuǎn)化為：

2.2.4 固定Sv、Fv、F*、Y，優(yōu)化P

忽略其他無關(guān)項，P的優(yōu)化式可以轉(zhuǎn)化為：

2.2.5 固定Sv、Fv、F*、P，優(yōu)化Y

忽略其他無關(guān)項，關(guān)于Y的優(yōu)化可以轉(zhuǎn)化為：

2.3 時間復雜性分析

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

算法2OP-MVSC

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

輸出：聚類標簽矩陣Y。

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

1.重復執(zhí)行

2.通過式（9）來優(yōu)化Sv

3.通過解式（10）來優(yōu)化F*

4.通過解式（12）來優(yōu)化Fv

5.通過解式（13）來優(yōu)化P

6.通過解式（14）來優(yōu)化Y

7.直至算法收斂

8.返回聚類標簽矩陣Y

3 實驗及結(jié)果分析

3.1 數(shù)據(jù)集介紹

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

Table 1 Introduction of datasets表1 數(shù)據(jù)集介紹

3.2 對比方法介紹

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

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

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

F-score是精確率（Precision）和召回率（Recall）的加權(quán)調(diào)和平均值，定義如下：

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

3.3 模型分析

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

Fig.1 Sensitivity of parameters on Caltech7圖1 數(shù)據(jù)集Caltech7 上的參數(shù)敏感性

圖2 為在MSRC-v1 上隨著迭代次數(shù)的增加聚類性能變化曲線，可以看出，算法在有限的迭代次數(shù)內(nèi)可以達到最優(yōu)的性能并保持穩(wěn)定。

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

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

3.4 實驗結(jié)果分析

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

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

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

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

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

4 結(jié)束語

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