視圖關(guān)系學(xué)習(xí)與圖學(xué)習(xí)的多視圖圖聚類

袁 柱，高清維，王 琳，趙大衛(wèi)，盧一相，孫 冬，竺 德

安徽大學(xué) 電氣工程與自動化學(xué)院，合肥 230601

聚類作為無監(jiān)督學(xué)習(xí)的一個分支是一種常見的數(shù)據(jù)分析方法，在機(jī)器學(xué)習(xí)、人工智能和模式識別等領(lǐng)域有著舉足輕重的作用。它廣泛應(yīng)用于信息檢索、數(shù)據(jù)分類和異常檢測等場景[1]。聚類是根據(jù)數(shù)據(jù)之間的關(guān)系，將數(shù)據(jù)集劃分為不同的聚類簇。聚類分析的目標(biāo)可以概括為“類內(nèi)的相似性與類間的排他性”。現(xiàn)實(shí)生活中，從不同的角度看待問題能夠把問題描述得更加全面。從不同方面描述的數(shù)據(jù)稱為多視圖數(shù)據(jù)，相比單視圖數(shù)據(jù)而言，多視圖數(shù)據(jù)包含更豐富的信息，從而把事物描述得更加全面。因此，多視圖數(shù)據(jù)廣泛存在于實(shí)際應(yīng)用中。例如，一則新聞可以由不同的媒體報道，一個對象可以用正面和側(cè)面等不同的角度分別描述[2-3]。

多視圖聚類應(yīng)用于人臉識別、新聞數(shù)據(jù)處理等人們生活的各個場景。在人臉識別技術(shù)中，往往會受到來自光線、面部表情和面部細(xì)節(jié)的干擾，使得識別精準(zhǔn)度與效率降低，而多視圖聚類能夠有效地解決這一問題。對于目前存在的新聞數(shù)據(jù)類型復(fù)雜、數(shù)量龐大以及傳播速度極快等現(xiàn)狀，有效處理新聞數(shù)據(jù)成為了一個新問題。在日常生活中，面對龐雜的新聞，人們往往不能快速獲得感興趣的信息。而多視圖聚類可以有效挖掘新聞的類屬信息，能夠很好地解決個性化新聞推薦這一難題。本文在后續(xù)的實(shí)驗(yàn)部分將針對上述兩種應(yīng)用場景，驗(yàn)證本文算法的有效性與可行性。

串聯(lián)所有的視圖通常會導(dǎo)致維度災(zāi)難。因此，處理單視圖數(shù)據(jù)的方法不能直接遷移到處理多視圖數(shù)據(jù)上。近些年來，人們陸續(xù)提出了許多多視圖聚類方法。可以分為五類：多視圖子空間聚類[4]、基于協(xié)同訓(xùn)練的多視圖聚類、基于多核學(xué)習(xí)的多視圖聚類、多任務(wù)多視圖聚類、多視圖圖聚類。多視圖子空間聚類方法假設(shè)高維數(shù)據(jù)通常分布于低維子空間的并上[5-6]。它基于自表達(dá)性，即假設(shè)每個樣本可以被其他樣本線性表示。為了得到具有塊對角陣結(jié)構(gòu)表示系數(shù)矩陣Z，關(guān)于Z的兩個廣泛使用的假設(shè)是低秩[6]和稀疏[7]。通過對所有的表示系數(shù)矩陣求平均值得到相似性矩陣，最后把它作為譜聚類算法的輸入[8]，得到最終的聚類結(jié)果。在此基礎(chǔ)上，提出了多種多視圖子空間聚類模型。文獻(xiàn)[9]提出了新的多視圖子空間聚類算法。對所有的視圖都學(xué)習(xí)一個圖，并強(qiáng)制執(zhí)行一個公共的聚類指標(biāo)矩陣。但這一假設(shè)往往是不成立的，因?yàn)楣驳木垲愔笜?biāo)矩陣必須包含所有視圖的部分信息。因此，無法得到一個所有視圖共同認(rèn)可的聚類指標(biāo)矩陣。DiMSC（diversity-induced multi-view subspace clustering）[10]利用希爾伯特-施密特獨(dú)立準(zhǔn)則（Hilbert Schmidt independence criterion，HSIC）作為多樣性項來探索多視圖數(shù)據(jù)的互補(bǔ)性。它通過挖掘多視圖數(shù)據(jù)的互補(bǔ)信息，提高聚類結(jié)果的準(zhǔn)確性。文獻(xiàn)[11]提出了一個基于聯(lián)合相似圖的多視圖子空間聚類方法。這個聯(lián)合相似圖是基于多樣性正則化和秩約束的低秩表示來構(gòu)建的。CiMSC（consistency-induced multiview subspace clustering）[12]以視圖內(nèi)結(jié)構(gòu)一致性和樣本分配一致性作為切入點(diǎn)，可以從高維數(shù)據(jù)中，學(xué)習(xí)到一個有效的子空間表示，并通過非線性重構(gòu)方式將其編碼為潛在表示。但上述三種模型均采用了平均值圖作為譜聚類算法的輸入，忽略了這種低質(zhì)量視圖對聚類結(jié)果的影響。LGOMSC（fusing local and global information for one-step multiview subspace clustering）[13]與文獻(xiàn)[14]提供了一種一步式多視圖子空間聚類，它融合了子空間表示、多視圖信息融合和聚類作為一個統(tǒng)一的優(yōu)化框架來實(shí)現(xiàn)聚類。但這種方法忽略了不同視圖的多樣性，因此多視圖數(shù)據(jù)的互補(bǔ)信息沒有得到充分的挖掘。

在多視圖圖聚類方法中，用圖形表示對象與對象之間的關(guān)系。圖形中的節(jié)點(diǎn)對應(yīng)數(shù)據(jù)對象，圖形中的每個邊描繪一對對象之間的關(guān)系。一般把對象之間的關(guān)系用相似性表示，即輸入圖矩陣由樣本數(shù)據(jù)相似性矩陣生成。一個常見的假設(shè)是每個視圖可以捕獲多視圖數(shù)據(jù)的部分信息，多視圖數(shù)據(jù)中每個視圖對應(yīng)的圖形都具有相似的聚類結(jié)構(gòu)。因此，多視圖可以通過合并視圖以增強(qiáng)數(shù)據(jù)對象之間的關(guān)系。多視圖圖聚類的目的是在所有視圖中找到一個融合圖，然后在融合圖上應(yīng)用圖形切割算法或譜聚類，產(chǎn)生最終的聚類結(jié)果。如何得到一個有利于聚類的融合圖，成為多視圖圖聚類的首要問題。在文獻(xiàn)[15-17]中運(yùn)用多視圖數(shù)據(jù)矩陣加權(quán)融合的方法，雖然它們沒有添加額外的聚類方法，但它們獨(dú)立地為每個視圖構(gòu)造相似圖矩陣，這種方法可能會得到次優(yōu)的融合圖。MAGC（multi-view attributed graph clustering）[18]使用圖過濾來實(shí)現(xiàn)聚類的平滑表示，并引入一種加權(quán)機(jī)制，區(qū)別不同視圖的不同貢獻(xiàn)。在實(shí)際應(yīng)用中，每個視圖在共識圖中的重要性不同。因此，文中給每個相似圖分配不同的權(quán)重[19]。GMC（graph-based multi-view clustering）[20]應(yīng)用一種自加權(quán)圖融合技術(shù)，將所有多視圖數(shù)據(jù)矩陣融合，生成一個融合圖數(shù)據(jù)矩陣。融合圖數(shù)據(jù)矩陣反過來改進(jìn)了每個視圖的數(shù)據(jù)矩陣，在不使用別的圖切割算法下直接得到了最終的聚類結(jié)果。文獻(xiàn)[21]開發(fā)了一個統(tǒng)一的框架，同時進(jìn)行圖學(xué)習(xí)和譜聚類。然而，這種方法不能對所有視圖保持靈活的局部多樣性結(jié)構(gòu)，導(dǎo)致聚類性能表現(xiàn)不佳[22]。文獻(xiàn)[23]的方法運(yùn)用每個視圖是融合圖的一個擾動和接近融合圖的圖應(yīng)該被賦予較大權(quán)重的理論。在融合過程中對圖進(jìn)行動態(tài)加權(quán)，有效降低了噪聲圖的干擾效應(yīng)。文獻(xiàn)[24-25]針對現(xiàn)有的基于歐幾里德結(jié)構(gòu)的多視圖圖聚類方法，提出了一種基于流行拓?fù)浣Y(jié)構(gòu)的聚類方法，將多個自適應(yīng)圖整合到一個共識圖中。GBS（graph-based system）[26]的工作原理是提取每個視圖的數(shù)據(jù)特征矩陣，構(gòu)造所有視圖的圖矩陣，并將構(gòu)造的圖矩陣融合生成一個統(tǒng)一的圖矩陣，得到最終的聚類。文獻(xiàn)[27]為了實(shí)現(xiàn)最優(yōu)的全局特征學(xué)習(xí)，提出了一種把自適應(yīng)圖學(xué)習(xí)稀疏表示與自適應(yīng)加權(quán)合作學(xué)習(xí)相結(jié)合。它通過引入自適應(yīng)圖學(xué)習(xí)的同步優(yōu)化方法可以更好地保留每個視圖內(nèi)部的完整結(jié)構(gòu)，使得到的全局最優(yōu)矩陣有利于最終的聚類結(jié)果。

影響多視圖聚類性能的因素是能否充分挖掘和利用隱藏在其中的信息。這些信息包括高維數(shù)據(jù)在低維子空間的分布、多視圖數(shù)據(jù)分布的幾何形狀、多視圖視圖數(shù)據(jù)之間的互補(bǔ)信息以及不同視圖所占權(quán)重等。然而上文提及的方法，在一定程度上不能有效地利用或挖掘出這些信息，以至于得到次優(yōu)的聚類結(jié)果。為了充分挖掘隱藏在多視圖數(shù)據(jù)中的信息，本文提出了一種視圖關(guān)系與圖結(jié)構(gòu)學(xué)習(xí)的多視圖圖聚類方法，在一個統(tǒng)一的框架中基于多視圖自表達(dá)來整合圖融合與譜聚類學(xué)習(xí)。具體來說，首先把視圖自表達(dá)學(xué)習(xí)擴(kuò)充到多視圖領(lǐng)域，有效地揭示了高維數(shù)據(jù)的低維子空間分布。其次對得到的相似圖做流形正則化處理，控制樣本數(shù)據(jù)分布的幾何形狀，明確地加強(qiáng)子空間表示。然后利用HSIC作為多樣性表示，充分利用隱藏在多視圖數(shù)據(jù)之間的互補(bǔ)信息。進(jìn)一步，采用誘導(dǎo)自加權(quán)的圖融合學(xué)習(xí)方法，交替優(yōu)化融合圖和不同視圖所占權(quán)重，將相似圖動態(tài)加權(quán)得到融合圖。最后，通過對融合圖圖結(jié)構(gòu)的學(xué)習(xí)，建立了與譜聚類的聯(lián)系，構(gòu)建了一個高質(zhì)量的譜聚類輸入圖，生成聚類結(jié)果。圖1展示了本文工作的框架結(jié)構(gòu)圖。在后續(xù)五個廣泛使用的數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，提出的視圖關(guān)系學(xué)習(xí)與圖學(xué)習(xí)的多視圖圖聚類算法具有一定的有效性和競爭性。

圖1 視圖關(guān)系學(xué)習(xí)與圖學(xué)習(xí)的多視圖圖聚類算法框架Fig.1 Multi-view graph clustering algorithm framework for view relation learning and graph learning

1 視圖關(guān)系學(xué)習(xí)與圖學(xué)習(xí)的多視圖圖聚類

1.1 符號與定義

X={X1,X2,…,Xv}是有v個視圖的多視圖數(shù)據(jù)矩陣，其中表示第v個視圖的特征維度，n表示視圖所包含的樣本個數(shù)。Zv∈Rn×n(v=1,2,…,h)是第v個視圖相似圖。U∈Rn×n是融合圖。β、γ、δ、ε、ζ是權(quán)衡參數(shù)。

1.2 多視圖自表達(dá)學(xué)習(xí)

1.2.1 單視圖自表達(dá)學(xué)習(xí)

單視圖數(shù)據(jù)集是指利用一種類型的特征對樣本集合進(jìn)行描述，從而構(gòu)成的數(shù)據(jù)矩陣。給定一個單視圖樣本數(shù)據(jù)集X=[x1,x2,…,xn]∈Rd×n，該樣本數(shù)據(jù)集有n個樣本向量，每個樣本向量的特征維度是d，設(shè)這組數(shù)據(jù)屬于k（k已知或未知）個低維線性子空間的并。

單視圖子空間聚類是指將這組樣本數(shù)據(jù)分割為不同的類，在理想情況下，每一類對應(yīng)一個子空間。它的基本思想是，將樣本數(shù)據(jù)向量xi表示為其他所有屬于數(shù)據(jù)集X的樣本向量的線性組合?？梢员硎緸椋?/p>

對表示系數(shù)施加一定的約束，使得當(dāng)xi與xj不屬于同一個子空間時，有zij=0。將所有的數(shù)據(jù)及其表示系數(shù)按一定方式排成矩陣，則方程（1）等價于：

其中，Z∈Rn×n表示系數(shù)矩陣。若已知數(shù)據(jù)的子空間結(jié)構(gòu)，并將數(shù)據(jù)按類別逐列排放，則在一定條件下可使表示系數(shù)矩陣Z具有塊對角結(jié)構(gòu)，可以寫為：

其中，Zα(α=1,2,…,k)表示樣本數(shù)據(jù)在所屬子空間的系數(shù)矩陣。也就是說，若Z具有塊對角結(jié)構(gòu)，那么這種結(jié)構(gòu)揭示了高維數(shù)據(jù)的低維子空間結(jié)構(gòu)。

在實(shí)際應(yīng)用中，數(shù)據(jù)往往受各種噪聲或奇異值樣本的影響，這種影響是不可忽略的，此時可以把視圖自表達(dá)模型描述為：

本文使用最小二乘回歸子空間聚類模型，優(yōu)化上述方程（4），得到方程（5）：

式中，第一項為數(shù)據(jù)項，刻畫了表示數(shù)據(jù)與真實(shí)數(shù)據(jù)的逼近程度；第二項為正則項。β>0 是一個權(quán)衡參數(shù)，用來衡量視圖自表達(dá)學(xué)習(xí)中數(shù)據(jù)項和正則項的關(guān)系。若β的值過大，對噪聲或離群值魯棒效果較差；若β的值過小，得到的Zv的結(jié)構(gòu)對最終的聚類結(jié)果不利。

1.2.2 擴(kuò)充到多視圖領(lǐng)域的自表達(dá)學(xué)習(xí)

為了更加完備地表示一個樣本集合，往往需要使用更高維度的特征描述樣本集合，這被稱為多視圖數(shù)據(jù)集。把視圖自表達(dá)學(xué)習(xí)擴(kuò)充到多視圖領(lǐng)域的優(yōu)勢在于：（1）多視圖數(shù)據(jù)集的不同特征可以從不同的角度捕獲更多的信息，相比單視圖聚類只能利用單一的特征獲得部分信息，多視圖聚類結(jié)果的精度更高。（2）多視圖數(shù)據(jù)之間存在互補(bǔ)和一致性信息，將多視圖數(shù)據(jù)矩陣構(gòu)成單一的特征表示矩陣，通常會存在特征冗余，并且不同視圖的統(tǒng)計特性是不同的。如果只是簡單地將所有視圖矩陣組合成一個數(shù)據(jù)矩陣，通常會破壞原始特征空間的內(nèi)在結(jié)構(gòu)。而將視圖自表達(dá)學(xué)習(xí)擴(kuò)充到多視圖領(lǐng)域可以有效解決上述問題。

在后續(xù)的可視化分析中，本文所提算法在BBCSport多視圖數(shù)據(jù)集上的聚類結(jié)果要明顯優(yōu)于在該數(shù)據(jù)集上只使用單視圖的聚類結(jié)果。證明了本文將視圖自表達(dá)學(xué)習(xí)擴(kuò)充到多視圖領(lǐng)域的可行性。

把從單視圖的自表達(dá)學(xué)習(xí)擴(kuò)充到多視圖領(lǐng)域得到方程（6）：

如同在SMR（smooth representation），本文使用圖的正則化技術(shù)，它明確地加強(qiáng)子空間表示以滿足聚類效果[28]。流行正則化學(xué)習(xí)可以挖掘數(shù)據(jù)分布的幾何形狀，將其作為一個增加的正則項來控制樣本分布的幾何形狀。流形正則化學(xué)習(xí)的一個直觀解釋是，如果兩個數(shù)據(jù)點(diǎn)很接近，那么它們在相似圖中也很接近。它具有以下形式||xi-xj||2→0 ?||zi-zj||2→0，?i≠j。定義如下：

其中，前兩項是擴(kuò)充到多視圖領(lǐng)域的視圖自表達(dá)學(xué)習(xí)。利用樣本數(shù)據(jù)相關(guān)性，對原始數(shù)據(jù)構(gòu)建表示系數(shù)矩陣。方程使用Frobenius 范數(shù)進(jìn)行約束，使得表示系數(shù)矩陣Z具有塊對角結(jié)構(gòu)且對大部分噪聲有很強(qiáng)的魯棒性，揭示了高維數(shù)據(jù)的低維子空間分布。最后一項是流形正則化項，γ是正則化項參數(shù)。對得到的相似圖做流形正則化處理，控制樣本數(shù)據(jù)分布的幾何形狀，明確地加強(qiáng)子空間表示，進(jìn)一步提高聚類精確度。

可以看出，方程（8）所提算法僅考慮多視圖的相似性信息。雖然使用流行正則化技術(shù)進(jìn)一步地約束，但忽略了多視圖數(shù)據(jù)之間的關(guān)系，沒有充分挖掘和利用多視圖之間的信息，得到的相似圖質(zhì)量較低。

1.3 視圖關(guān)系學(xué)習(xí)

多視圖的互補(bǔ)信息是每個視圖可能包含其他視圖不具備的知識。因此，采用多視圖能夠全面和準(zhǔn)確地描述數(shù)據(jù)。然而，現(xiàn)有的多視圖學(xué)習(xí)方法有很大的局限性，它們不能保證不同視圖對應(yīng)不同相似矩陣之間的互補(bǔ)性。換句話說，這些方法假設(shè)獨(dú)立構(gòu)造的相似矩陣之間有豐富的互補(bǔ)信息，或假設(shè)多視圖彼此之間是獨(dú)立的。然而，這種假設(shè)是沒有任何依據(jù)的。因此，本文對視圖之間的多樣性進(jìn)行研究。

為了增加多視圖數(shù)據(jù)之間的多樣性，本文探究矩陣之間的依賴關(guān)系。根據(jù)文獻(xiàn)[29]可以得到，多視圖數(shù)據(jù)的多樣性與它們的依賴性息息相關(guān)。簡單來說，如果數(shù)據(jù)之間有高度的依賴性，那么它們之間就有更強(qiáng)的多樣性。兩個變量之間的依賴性可以用很多方法來測量。本文采用HSIC，因?yàn)镠SIC 實(shí)現(xiàn)簡單，能夠解決線性和非線性問題，并且經(jīng)驗(yàn)HSIC 可以用數(shù)據(jù)矩陣乘積的跡來表示，這保證了問題的可解性。HSIC在希爾伯特空間中計算Zv和Zv′上的互協(xié)方差算子的平方范數(shù)，根據(jù)經(jīng)驗(yàn)HSIC的定義[29]，其表達(dá)式為：

其中，K1和K2是格拉姆矩陣，H=δij-1/n，H∈Rn×n。本文使用HSIC衡量數(shù)據(jù)之間的依賴性，保證多視圖數(shù)據(jù)提供足夠的互補(bǔ)信息，減少數(shù)據(jù)的冗余信息。

多視圖互補(bǔ)信息的探索是多視圖聚類的核心。因此，結(jié)合方程（8）和方程（9）得到：

其中，δ是正則化項參數(shù)。最后一項利用HSIC 獨(dú)立準(zhǔn)則，依據(jù)核相關(guān)性度量來挖掘多視圖數(shù)據(jù)間的多樣性，明確地對不同視圖進(jìn)行共正則化，深入探索了不同視圖的互補(bǔ)信息。通過對上述聯(lián)合增強(qiáng)的多視圖自表達(dá)學(xué)習(xí)，可以得到每個視圖的相似圖{Z1,Z2,…,Zh}。通常取相似圖的平均值圖作為譜聚類算法的輸入，以獲得最終的聚類結(jié)果。但該方法沒有區(qū)分不同視圖在融合圖中所占權(quán)重，并且會受到噪聲視圖的影響。因此，用次優(yōu)的融合圖作為譜聚類的輸入得到的聚類結(jié)果并不理想。

1.4 圖融合

本文基于以下兩點(diǎn)：（1）每個視圖的相似圖Zv是融合圖U的一個擾動；（2）接近融合圖的視圖應(yīng)該占較大的權(quán)重。提出一種誘導(dǎo)自加權(quán)的圖融合學(xué)習(xí)，自動加權(quán)每個相似圖Z1,Z2,…,Zh的不同權(quán)重，得到一個統(tǒng)一的融合圖U：

其中，wv根據(jù)如下計算規(guī)則獲取：

在實(shí)際應(yīng)用中為了避免分母為0，使用方程（13）：

其中，μ是一個非常小的數(shù)。

方程（11）中的wv依賴于U，即方程（11）中第一項的U和wv相互耦合。如果固定wv，可以把wv理解為第v個視圖的在融合圖中的所占權(quán)重。如果相似圖Zv很接近融合圖U，那么||Zv-U||F的值很小，wv的值就很大，即接近融合圖的視圖能夠分得較高的權(quán)重。反之當(dāng)Zv遠(yuǎn)離U時，wv的值很小，視圖分配的權(quán)重較低。這使得wv可以作為多視圖在融合圖中的權(quán)重，這一項的存在是有意義的。

根據(jù)方程（11）得到的U可以進(jìn)一步用于方程（13）wv的更新。因此可以通過交替優(yōu)化U和wv的方法，來解決前文提出的一種誘導(dǎo)自加權(quán)的圖融合學(xué)習(xí)。在下文的算法1，給出交替優(yōu)化U和wv的具體過程。

1.5 圖結(jié)構(gòu)學(xué)習(xí)與譜聚類

譜聚類作為多視圖圖聚類的方法之一，它是一種應(yīng)用圖的分割理論，將圖分割為多個獨(dú)立的連通分量，每個連通對應(yīng)一個簇。目前通常把圖割理論優(yōu)化為對拉普拉斯矩陣進(jìn)行譜分解問題。一般情況下，聚類的目標(biāo)聚類簇數(shù)量往往是事先給定的，在本文中取k。那么方程（10）與方程（11）的解融合圖U也應(yīng)該有k個連接點(diǎn)，即數(shù)據(jù)點(diǎn)已經(jīng)被聚類為k個簇。如何約束融合圖U，使得U能滿足上述條件，獲得優(yōu)質(zhì)的譜聚類輸入圖，因此，本文對融合圖U的結(jié)構(gòu)進(jìn)行學(xué)習(xí)。

根據(jù)拉普拉斯矩陣性質(zhì)，圖U的連接點(diǎn)k的數(shù)目等于它的拉普拉斯矩陣LU的零特征值的重根數(shù)目。由于LU是一個半正定矩陣，它的特征值λn≥…≥λ2≥λ1≥0。即如果，那么融合圖U就有k個連接點(diǎn)，才能作為譜聚類的輸入。因此本文需要最小化

通過對融合圖的拉普拉斯矩陣LU的特征向量進(jìn)行聚類，將聚類問題轉(zhuǎn)換成圖的最優(yōu)劃分問題。根據(jù)Ky Fan定理，本文可以得到譜聚類的目標(biāo)函數(shù)：

譜聚類算法通過輸入融合圖U和聚類目標(biāo)簇數(shù)k，接著計算度矩陣DU和拉普拉斯矩陣LU，然后利用拉普拉斯矩陣的特征向量進(jìn)行聚類。

將方程（14）帶入到方程（11）中，可得到：

聯(lián)合方程（10）和方程（15）得到一種基于視圖關(guān)系與圖結(jié)構(gòu)學(xué)習(xí)的多視圖圖聚類算法模型：

其中，前四項相輔相成，充分地挖掘了多視圖數(shù)據(jù)的互補(bǔ)信息。這樣得到的相似圖，可以有效且全面地揭示隱藏在數(shù)據(jù)中的分布結(jié)構(gòu)。ε、ζ是正則化項參數(shù)。后兩項進(jìn)一步用誘導(dǎo)自加權(quán)的圖融合學(xué)習(xí)方法，把融合圖和不同視圖所占權(quán)重交替優(yōu)化。最后，通過對融合圖結(jié)構(gòu)的學(xué)習(xí)，建立了圖學(xué)習(xí)與譜聚類之間的聯(lián)系，構(gòu)建了一個高質(zhì)量的輸入圖作為譜聚類算法的輸入，從而得到最終聚類結(jié)果。

2 優(yōu)化

2.1 方程（10）的優(yōu)化算法

求解方程（10）需要利用HSIC 的內(nèi)積，即Kv=(Zv)TZv?？梢缘玫饺缦路匠蹋?/p>

可以看出，方程（18）對于每個視圖都是獨(dú)立的。因此，對于每個視圖，本文可以分別更新Zv。方程（18）關(guān)于Zv求導(dǎo)得到：

通過求解方程（20），可以得到每個視圖的相似圖。對方程（10）的求解步驟，在算法1中做出總結(jié)。

2.2 方程（16）的優(yōu)化算法

提取的多視圖數(shù)據(jù)矩陣，使用算法1得到相似圖Z1,Z2,…,Zh。之后本文通過求解方程（16）得到融合圖U。觀察到，方程（16）中的變量是相互耦合的，本文可以通過交替迭代的方法優(yōu)化求解。

2.2.1 固定F 和U 更新wv

方程（16）轉(zhuǎn)化成方程（11），可以由方程（13）直接得到。

2.2.2 固定F 和wv 更新U

注意到L是U的函數(shù)，方程（16）可以轉(zhuǎn)化為：

方程（22）關(guān)于U(:,i)的導(dǎo)數(shù)為：

2.2.3 固定wv 和U 更新F

可以把方程（16）轉(zhuǎn)化為求解方程（25）：

F的最優(yōu)解由LU的k個特征值對應(yīng)的k個最小特征向量組成。

經(jīng)過優(yōu)化，所有變量都更新完畢。算法1總結(jié)了方程（16）的求解細(xì)節(jié)。

算法1MVG（multi-view graph clustering algorithm combining view relation learning and graph learning）算法的優(yōu)化

輸入：多視圖數(shù)據(jù)矩陣X={X1,X2,…,Xh}，聚類的數(shù)量k，參數(shù)β>0,γ>0,δ>0,ε>0,ζ>0。

輸出：相似圖Z1,Z2,…,Zh，融合圖U，聚類指標(biāo)矩陣F。

步驟1利用HSIC內(nèi)積，把方程（10）轉(zhuǎn)化為方程（18）。對方程（18）關(guān)于Zv求導(dǎo)，令導(dǎo)數(shù)為0，得到多視圖相似圖矩陣Z1,Z2,…,Zh。方程（16）中的各變量相互耦合，步驟2、步驟3、步驟4采用交替迭代的方法優(yōu)化求解。

步驟2固定F和U，把方程（16）轉(zhuǎn)化為方程（11），根據(jù)方程（12）求解wv。

步驟3固定F和wv，由于L是U的函數(shù)，把方程（16）轉(zhuǎn)化為方程（21）。對方程（21）進(jìn)行變換，并關(guān)于U(:,i)求導(dǎo)，令導(dǎo)數(shù)為0，可得U。

步驟4固定wv和U，把方程（16）轉(zhuǎn)化為方程（25），根據(jù)方程（25）求解F。

2.3 復(fù)雜度分析

MVG 算法的復(fù)雜度由三部分組成。具體來說，更新Zv需要計算矩陣的逆，它的復(fù)雜度為O(n3)。更新U的復(fù)雜度為O(hn)，其中h是多視圖數(shù)據(jù)的視圖數(shù)。更新F需要計算拉普拉斯矩陣的特征向量，它的復(fù)雜度為O(kn2)，其中k是聚類數(shù)目，n是樣本個數(shù)。設(shè)經(jīng)過t次迭代后算法停止，總復(fù)雜度為O((n2+h+kn)tn)，其中h?n，k?n，t?n。對比其他方法的復(fù)雜度：MCLES（multi-view clustering in latent embedding space）[30]的總復(fù)雜度為其中d(v)是第v個視圖數(shù)據(jù)集的維度，d是隱含嵌入表示的維度，k是聚類數(shù)目，V是多視圖數(shù)據(jù)的視圖數(shù)，n是樣本個數(shù)；GMC[20]的總復(fù)雜度為O(((mk+mn+c+cn)n)t+mnkd)，其中m是多視圖數(shù)據(jù)的視圖數(shù)，k是領(lǐng)域的數(shù)量，c是聚類數(shù)目，t是迭代次數(shù)，n是樣本個數(shù)；LMSC（latent multi-view subspace clustering）[31]的復(fù)雜度為O(k2d+d3+k3+n3+dkn+kn2)，其中k為潛在表示的維度，d是多視圖特征的總維度，n是樣本個數(shù)；MCDCF（multi-view clustering via deep concept factorization）[32]的總復(fù)雜度為O(m(pn2+dn2+hrqn2))，其中m是多視圖數(shù)據(jù)的視圖數(shù)，p是近鄰圖數(shù)量，q是內(nèi)在維度，d是所有視圖的原始特征維度，r是迭代次數(shù)，n是樣本個數(shù)；FPMVS（fast parameter-free multi-view subspace clustering）[33]的總復(fù)雜度為O(hk2+hk3+nk3)，其中h是所有視圖的維度總和，k為聚類數(shù)，n是樣本個數(shù)。通過對比上述算法的復(fù)雜度，本文所提算法更簡潔。

2.4 收斂性分析

觀察方程（16）發(fā)現(xiàn)，除了圖融合項外，其余項是明顯的凸函數(shù)。因此僅需要證明圖融合項是否具有收斂性。接下來重點(diǎn)對圖融合項的收斂性做理論分析。

引理1[34]對于任何的非0常數(shù)x和y，都有以下不等式成立：

代入wv=1/(2||Zv-U||F)，得到：

根據(jù)引理1，可以得到：

聯(lián)合方程（28）和方程（29），可以得到：

因此，每次迭代之后，圖融合項總是在單調(diào)遞減，直至收斂。因此在大多數(shù)情況下，算法1 至少會收斂到局部最優(yōu)解。在后續(xù)的收斂性實(shí)驗(yàn)部分同樣證明了這一點(diǎn)。

3 實(shí)驗(yàn)

為了驗(yàn)證本文方法的聚類性能，在五個廣泛使用的多視圖數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。根據(jù)六個評價指標(biāo)，將MVG算法與其他算法進(jìn)行比較。

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

五個數(shù)據(jù)集分別是reuters-1200、BBCSport、prokaryotic、ORL 和3scources。數(shù)據(jù)集的資料詳細(xì)統(tǒng)計在表1中。

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

3.2 比較方法

實(shí)驗(yàn)中，將本文提出的MVG算法與九種多視圖聚類算法進(jìn)行對比。對比算法分別是SC_best、GMC[20]、GFSC（multi-graph fusion for multi-view spectral clustering）[23]、MCLES[30]、LMSC[31]、MCDCF[32]、FPMVS[33]、Co-Reg[35]、LTMSC（low-rank tensor constrained multiview subspace clustering）[36]。SC_best 算法在每一個視圖上運(yùn)用譜聚類算法，通過信息量最大的一個視圖，得到單個視圖的最佳聚類結(jié)果。Co-Reg 算法運(yùn)用共正則化的原理，使不同視圖的聚類一致。MCLES算法在潛在嵌入表示之后構(gòu)造相似矩陣，并利用聚類指標(biāo)矩陣直接得出聚類結(jié)果。GMC算法使用稀疏表示和自加權(quán)策略得到多個視圖統(tǒng)一的圖矩陣，之后對圖的拉普拉斯矩陣施加秩約束，不需要額外的聚類步驟。LMSC算法引入多視圖潛在表示，增強(qiáng)聚類結(jié)果的魯棒性。LMSC 算法在子空間表示中加入低秩約束，探索數(shù)據(jù)的高階相關(guān)性，減少了視圖的冗余信息。GFSC算法提出新的多視圖譜聚類模型，同時進(jìn)行圖融合和譜聚類。MCDCF 將多層概念分解引入到多視圖聚類中，能夠?qū)W習(xí)層次信息，并推導(dǎo)出一個共識表示矩陣來獲取視圖間的共享信息。FPMVS將錨抽樣機(jī)制和子空間圖的構(gòu)建統(tǒng)一到一個模型里，兩個過程相互協(xié)商，提高聚類效果。

3.3 評價指標(biāo)

聚類分析要求高的類內(nèi)的相似性，低的類間的相似性。為了對所有聚類算法的性能進(jìn)行評估，本文選擇了6個廣泛使用的評價指標(biāo)，對所有的評價指標(biāo)，數(shù)值越大，說明聚類性能越好。不同的評價指標(biāo)算法對聚類特性的偏好不同，選用多個評價指標(biāo)能能全面地評價算法的聚類效果。

（1）標(biāo)準(zhǔn)化互信息NMI（normalized mutual information）：

其中，H(X)和H(Y)分別是隨機(jī)變量X、Y的熵，I(X,Y)是兩個隨機(jī)變量X和Y的互信息。

（2）準(zhǔn)確度ACC（accuracy），準(zhǔn)確度用來度量預(yù)測結(jié)果與真實(shí)數(shù)據(jù)之間的關(guān)系，定義如下：

其中，si和ri是給定樣本數(shù)據(jù)xi的真實(shí)類別標(biāo)記和聚類標(biāo)記。當(dāng)x=y時，δ(x,y) 的值為1，否則為0。map(ri)是映射函數(shù)，將聚類標(biāo)記映射到真實(shí)類別。

（3）蘭德系數(shù)RI（Rand index），它表示預(yù)測樣本正確聚類的值。值越大說明聚類結(jié)果和樣本真實(shí)情況越相似。RI定義如下：

其中，TP是同一類的樣本劃分到同一個聚類簇；FN是同一類的樣本劃分到不同的聚類簇；FP是不同類的樣本劃分到同一個聚類簇；TN是不同類的樣本劃分到不同的聚類簇。

（4）精確率P（precision），它表示預(yù)測樣本判定為相同聚類中，樣本真實(shí)情況正確分類的占比。P定義如下：

（5）F（F-score），結(jié)合精確率和召回率R（recall）定義如下：

（6）調(diào)整蘭德系數(shù)AR（adjusted Rand index），在RI的基礎(chǔ)上，提出了具有更高預(yù)測區(qū)分度的AR，定義如下：

3.4 實(shí)驗(yàn)結(jié)果

對于比較算法，采用原論文中的建議調(diào)節(jié)參數(shù)，保存較好的實(shí)驗(yàn)結(jié)果。對于所有算法，每個實(shí)驗(yàn)重復(fù)運(yùn)行10 次，報告平均值的標(biāo)準(zhǔn)偏差。評價指標(biāo)的值越大，表明聚類性能越好。表2～表6 報告了MVG算法在5 個數(shù)據(jù)集reuters-1200、BBCSport、prokaryotic、ORL和3scources上的聚類結(jié)果。其中，最優(yōu)結(jié)果加粗顯示。

表2 各算法在reuters-1200數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Table 2 Experimental results of each algorithm on reuters-1200 dataset

表3 各算法在BBCSport數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Table 3 Experimental results of each algorithm on BBCSport dataset

表4 各算法在prokaryotic數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Table 4 Experimental results of each algorithm on prokaryotic dataset

表5 各算法在ORL數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Table 5 Experimental results of each algorithm on ORL dataset

表6 各算法在3scources數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Table 6 Experimental results of each algorithm on 3scources dataset

通過比較表2～表6的實(shí)驗(yàn)結(jié)果，本文可以觀察到以下幾點(diǎn)：

（1）在所有的實(shí)驗(yàn)結(jié)果中，MVG算法在大部分情況下優(yōu)于其他多視圖聚類方法。具體來說，MVG 算法在總實(shí)驗(yàn)中排名第一的占比為66.7%，排名第二的占比為26.7%，排名第三的占比為3.34%。

（2）在ORL 和reuters-1200 數(shù)據(jù)集上，MVG 算法始終優(yōu)于其他多視圖聚類方法，這表明本文提出的MVG算法的有效性。在reuters-1200數(shù)據(jù)集上，MVG算法展示出較強(qiáng)的競爭力，評價指標(biāo)NMI、ACC、P、F、RI和AR分別比次優(yōu)方法提升0.22、0.09、0.115、0.152、0.032和0.185。

（3）MVG 算法始終優(yōu)于SC_best 方法，多視圖數(shù)據(jù)優(yōu)于單視圖數(shù)據(jù)的聚類結(jié)果，表明多視圖聚類中探索數(shù)據(jù)互補(bǔ)信息的重要性。MVG算法在大多數(shù)情況下優(yōu)于GFSC算法，表明加入視圖關(guān)系學(xué)習(xí)能夠有效提高多視圖聚類性能。

3.5 可視化分析

為了更直觀地描述算法的聚類結(jié)果，分析其揭示隱藏在數(shù)據(jù)中分布結(jié)構(gòu)的能力。本文運(yùn)用t-SNE（t-distributed stochastic neighbor embedding）可視化算法，將對比算法的聚類結(jié)果、MVG算法的聚類結(jié)果和在單視圖數(shù)據(jù)集上的MVG 算法的聚類結(jié)果可視化。圖2展示了上述三個實(shí)驗(yàn)在BBCSport數(shù)據(jù)集上的可視化聚類結(jié)果，不同的顏色表示不同的聚類簇。根據(jù)圖2（a）～圖2（e）觀察到，本文提出的MVG算法，相同顏色的點(diǎn)更緊密，即聚類簇內(nèi)的數(shù)據(jù)點(diǎn)具有強(qiáng)相關(guān)性。且不同顏色的簇之間分離度更高，即簇與簇之間有較強(qiáng)的無關(guān)性。實(shí)驗(yàn)結(jié)果進(jìn)一步驗(yàn)證了類內(nèi)的相似性與類間排他性的聚類目標(biāo)。這充分表明本文算法的可行性與有效性，以及該算法具有揭示隱藏在數(shù)據(jù)中分布結(jié)構(gòu)的能力。根據(jù)圖2（e）、圖2（f）可以觀察到，MVG算法在BBCSport多視圖數(shù)據(jù)集上的聚類結(jié)果，要明顯優(yōu)于在該數(shù)據(jù)集上只使用單視圖進(jìn)行聚類的結(jié)果。這表明多視圖聚類方法優(yōu)于單視圖聚類方法，同時驗(yàn)證了本文將視圖自表達(dá)學(xué)習(xí)擴(kuò)充到多視圖領(lǐng)域的可行性。

3.6 消融研究

為了驗(yàn)證本文提出的MVG算法中，視圖多樣性項、多視圖數(shù)據(jù)分布的幾何形狀和融合圖圖結(jié)構(gòu)項對聚類效果的影響，在5 個數(shù)據(jù)集上進(jìn)行消融研究。MVG的3個變體算法定義如下，MVG-D忽略視圖多樣性，MVG-C忽略視圖數(shù)據(jù)分布的幾何形狀，MVGS 忽略融合圖圖結(jié)構(gòu)。MVG-D、MVG-C 和MVG-S分別將參數(shù)δ、γ、ζ設(shè)為0，在6 個評價指標(biāo)上的聚類結(jié)果如圖3所示。根據(jù)圖3，可以觀察到以下幾點(diǎn)：（1）對比MVG 聚類算法的結(jié)果，當(dāng)忽略多視圖數(shù)據(jù)分布的幾何形狀，即MVG-C不進(jìn)行流行正則化學(xué)習(xí)時，相比MVG 算法在常見的5 個數(shù)據(jù)集3scources、ORL、prokaryotic、BBCSport 和reuters-1200 上的聚類評價指標(biāo)都顯示次優(yōu)的聚類結(jié)果。（2）忽略融合圖圖結(jié)構(gòu)時，即MVG-S?？梢钥闯?，對聚類輸入圖的圖結(jié)構(gòu)進(jìn)行約束，在聚類評價指標(biāo)都有一定程度的提升。

圖3 MVG算法的消融研究Fig.3 Ablation study of MVG algorithm

3.7 參數(shù)敏感性分析

MVG 算法有5 個參數(shù)，β是數(shù)據(jù)自表達(dá)項的參數(shù)，γ是控制數(shù)據(jù)分布幾何形狀項的參數(shù)，δ是視圖多樣性項的參數(shù)，ε是圖融合項的參數(shù)，ζ是圖結(jié)構(gòu)項的參數(shù)。在reuters-1200數(shù)據(jù)集上進(jìn)行參數(shù)敏感性分析實(shí)驗(yàn)，本文給出所有參數(shù)的敏感性分析結(jié)果。固定其他4個參數(shù)保持不變，改變其中一個參數(shù)的取值范圍。圖4展示了在reuters-1200數(shù)據(jù)集上所有參數(shù)對聚類性能的影響。

由圖4可以看出，參數(shù)β、參數(shù)γ、參數(shù)δ、參數(shù)ε和參數(shù)ζ分別在10、0.1、1、0.1、10 左右，聚類取得最佳結(jié)果。參數(shù)的取值，過大或者過小都會降低聚類性能或?qū)е戮垲惥炔▌虞^大。當(dāng)β的值過大時，對噪聲或奇異值樣本魯棒效果較差；當(dāng)β的值過小時，得到的Zv的結(jié)構(gòu)對最終的聚類結(jié)果不利。當(dāng)γ的值過大時，對樣本分布的幾何形狀約束過高；當(dāng)γ的值過小時，不能明確地加強(qiáng)子空間表示。當(dāng)δ的值過大時，視圖的多樣性項權(quán)重過高，導(dǎo)致學(xué)習(xí)的相似圖不準(zhǔn)確；當(dāng)δ的值過小時，多視圖視圖之間的互補(bǔ)信息不能得到充分的挖掘。類似的，參數(shù)ε的值過大時，會導(dǎo)致聚類評價指標(biāo)的波動過大；參數(shù)ε的值過小時，融合圖的質(zhì)量不再受到算法的關(guān)注。參數(shù)ζ的值過大時，導(dǎo)致次優(yōu)的聚類評價指標(biāo)；參數(shù)ζ的值過小時，一定程度上忽略了融合圖圖結(jié)構(gòu)的學(xué)習(xí)。

3.8 收斂性實(shí)驗(yàn)

本文提出的MVG 算法包含4 個未知變量，分別是Zv、wv、U和F。在每次迭代中，每次優(yōu)化問題都有一個封閉解，可以表明，整個優(yōu)化算法有較好的收斂性。圖5顯示了MVG算法在5個數(shù)據(jù)集上的收斂曲線。橫坐標(biāo)表示迭代次數(shù)，縱坐標(biāo)表示目標(biāo)函數(shù)值。在實(shí)驗(yàn)中，最大迭代數(shù)為10。從圖5 可以看出，MVG在少量迭代中收斂，這能夠證明所提出的算法有很好的收斂性。

圖5 MVG算法的收斂性實(shí)驗(yàn)Fig.5 Convergence experiment of MVG algorithm

4 結(jié)論

在一個統(tǒng)一的框架中基于多視圖自表達(dá)來整合圖融合與譜聚類學(xué)習(xí)。把視圖自表達(dá)學(xué)習(xí)擴(kuò)充到多視圖領(lǐng)域，有效地揭示了高維數(shù)據(jù)的低維子空間分布。對得到的相似圖做流形正則化處理，控制樣本數(shù)據(jù)分布的幾何形狀，明確加強(qiáng)子空間表示。把HSIC 準(zhǔn)則作為多樣性項，充分利用隱藏在多視圖數(shù)據(jù)之間的互補(bǔ)信息。采用誘導(dǎo)自加權(quán)的圖融合學(xué)習(xí)方法，通過交替迭代優(yōu)化，將相似圖動態(tài)加權(quán)，得到一個融合圖。通過對融合圖結(jié)構(gòu)的學(xué)習(xí)，建立了圖學(xué)習(xí)與譜聚類之間的聯(lián)系，構(gòu)建一個高質(zhì)量的輸入圖作為譜聚類的輸入，生成聚類結(jié)果。不僅能夠充分挖掘隱藏在多視圖數(shù)據(jù)中的豐富的信息，在此基礎(chǔ)上自加權(quán)融合相似圖，優(yōu)化譜聚類的輸入。在多個數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，該算法具有一定的可行性與有效性。