李杏峰，黃玉清*，任珍文，李毅紅

（1.西南科技大學(xué)信息工程學(xué)院，四川綿陽 621010；2.西南科技大學(xué)國防科技學(xué)院，四川綿陽 621010）

0 引言

多視圖聚類是一種重要的學(xué)習(xí)模式，因為它能夠整合不同視圖之間的一致和互補信息?，F(xiàn)有的多視圖聚類方法一般分為五類：協(xié)同訓(xùn)練聚類［1］、圖聚類［2］、子空間聚類［3］、多核學(xué)習(xí)聚類［4］和深度學(xué)習(xí)聚類［5］。其中，子空間聚類可以看作是圖聚類的一種特殊情況。

對于基于圖的多視圖聚類，其目的通常側(cè)重于如何學(xué)習(xí)一個高質(zhì)量的關(guān)系矩陣（關(guān)系圖），隨后譜算法或圖切算法作用于該圖來獲得最終聚類結(jié)果?？偟膩碚f，主流的圖學(xué)習(xí)技術(shù)通?？煞譃橐韵滤姆N：1）構(gòu)造一個預(yù)定義的相似圖作為關(guān)系圖［6］；2）自適應(yīng)鄰域圖學(xué)習(xí)（Adaptive Neighborhood Graph Learning，ANGL），以歐氏距離為尺度，它能自適應(yīng)地構(gòu)建一個關(guān)系矩陣［7-8］；3）自表示學(xué)習(xí)（Self-Expression Learning，SEL）［9-10］，它通過所有數(shù)據(jù)點的線性組合來重構(gòu)每個數(shù)據(jù)點，并生成一個系數(shù)矩陣來構(gòu)造關(guān)系圖；4）矩陣非負分解（Non-negative Matrix Factorization，NMF）［11］或概念分解（Concept Factorization，CF）［12］，它們旨在學(xué)習(xí)原始數(shù)據(jù)的一種新的表示形式，然后利用前三種方法構(gòu)造關(guān)系圖。本文主要研究基于ANGL的多視圖算法。

目前最先進的基于ANGL 的多視圖聚類算法主要有：自加權(quán)多視圖學(xué)習(xí)（Auto-weighted Multiple Graph Learning，AMGL）算法［13］、自適應(yīng)鄰域多視圖學(xué)習(xí)（Multi-view Learning with Adaptive Neighbours，MLAN）算法［14］、基于圖學(xué)習(xí)的多視圖聚類（Multi-View clustering with Graph Learning，MVGL）算法［15］、自權(quán)重多視圖聚類（Self-weighted Multi-view Clustering，SwMC）算法［16］、魯棒自權(quán)重多視圖聚類（Robust Auto-weighted Multi-view Clustering，RAMC）算法［17］和基于圖的多視圖聚類（Graph-based Multi-view Clustering，GMC）算法［18］。AMGL 先用多個原始數(shù)據(jù)學(xué)習(xí)多個關(guān)系圖，然后在不引入附加參數(shù)的情況下，根據(jù)各個視圖重要性分配相應(yīng)的權(quán)值來直接得到共識聚類標(biāo)簽矩陣。MLAN 直接利用ANGL 來融合多個視圖的原始數(shù)據(jù)，從而得到一個共識關(guān)系圖。MVGL 先用ANGL 通過原始數(shù)據(jù)分別學(xué)習(xí)多個關(guān)系圖，然后用列加權(quán)技術(shù)融合多個圖得到一個共識關(guān)系圖。SwMC 先用ANGL 通過原始數(shù)據(jù)分別學(xué)習(xí)多個關(guān)系圖，然后用自加權(quán)技術(shù)融合多個圖得到一個共識關(guān)系圖。RAMC 是SwMC 的魯棒版本，與SwMC 相比，RAMC 在圖融合階段引入l1范數(shù)提高模型魯棒性。GMC 將基于ANGL 的多個關(guān)系圖學(xué)習(xí)和共識關(guān)系圖學(xué)習(xí)集成為一個統(tǒng)一的目標(biāo)函數(shù)，該目標(biāo)函數(shù)用相互強化的方式獲得一個共識關(guān)系圖。理想情況下，如果輸入數(shù)據(jù)有c個類/簇，那么學(xué)到的共識關(guān)系圖應(yīng)該有c個連通部件。因此，上述多視圖聚類算法大都在共識關(guān)系圖上添加了秩約束以保證關(guān)系圖盡可能接近c個連通部件。盡管文獻［13-18］的算法很有效，但是它們依然存在以下兩個缺點：1）通常將原始的多視圖數(shù)據(jù)直接輸入圖學(xué)習(xí)模型，但不干凈的數(shù)據(jù)將極大地影響關(guān)系圖的質(zhì)量。2）通常采用兩個分開的步驟來學(xué)習(xí)共識關(guān)系圖，即先用原始多視圖數(shù)據(jù)構(gòu)造多個候選關(guān)系圖，然后再融合候選關(guān)系圖生成一個共識關(guān)系圖。因為不是直接利用多視圖數(shù)據(jù)融合成共識關(guān)系圖，所以在圖融合過程中會不可避免地損失一些重要信息，從而導(dǎo)致共識關(guān)系圖質(zhì)量下降。

為了解決以上問題，本文提出了魯棒多視圖聚類（Robust Multi-View Graph Clustering，RMVGC）算法。該算法在兩方面進行改進：1）將V個視圖的原始數(shù)據(jù)分解為低秩矩陣（干凈數(shù)據(jù)）和稀疏矩陣（噪聲），同時分別施加核范數(shù)和l2，1范數(shù)到，以保持數(shù)據(jù)的全局結(jié)構(gòu)和增強模型魯棒性；從單個視圖來看，該模型類似魯棒主成分分析（Robust Principle Component Analysis，RPCA）；2）用ANGL 直接融合學(xué)到的低秩干凈數(shù)據(jù)，得到最終的共識關(guān)系圖S，從而避免圖融合過程的信息丟失，提高共識關(guān)系圖質(zhì)量。

綜上所述，本文的主要工作如下：

1）現(xiàn)存的基于ANGL 的多視圖聚類算法對噪聲非常敏感，而實踐應(yīng)用中數(shù)據(jù)通常包含噪聲或異常值，因此，本文先將數(shù)據(jù)中的噪聲分離，得到干凈數(shù)據(jù)；再用ANGL 直接融合干凈數(shù)據(jù)來學(xué)習(xí)可靠的共識關(guān)系圖，有效地提高了模型魯棒性與聚類性能。

2）開發(fā)了一個同時學(xué)習(xí)共識鄰域圖S和低秩干凈數(shù)據(jù)的統(tǒng)一目標(biāo)函數(shù)，該函數(shù)能夠迭代增強S和直到獲得最優(yōu)的S*，并在該S*上執(zhí)行譜聚類得到聚類結(jié)果；與現(xiàn)存的基于ANGL 的多視圖算法相比，這是研究基于ANGL的第一個利用干凈數(shù)據(jù)構(gòu)圖的魯棒多視圖工作。

1 魯棒主成分分析與自適應(yīng)鄰域聚類

1.1 魯棒主成分分析（RPCA）

RPCA 是經(jīng)典的特征提取方法之一［19］，基于RPCA 模型的有效性，許多衍化模型得到了發(fā)展，其中一類具有代表性的低秩稀疏分解模型被廣泛研究。其原理旨在對數(shù)據(jù)矩陣進行分解，尋找低秩分量和稀疏誤差分量，從而有效地揭示數(shù)據(jù)的子空間結(jié)構(gòu)。具體衍化模型如下：

其中：α為平衡參數(shù)；D是X的干凈部分。該模型旨在從噪聲數(shù)據(jù)X中恢復(fù)低秩的干凈數(shù)據(jù)D，以增強模型魯棒性。關(guān)于魯棒性的更多詳細描述細節(jié)，可參考文獻［20-22］。

1.2 自適應(yīng)鄰域圖學(xué)習(xí)（ANGL）

探索數(shù)據(jù)的局部連通性是一種有效的聚類任務(wù)策略［1，7-8，14，16，20］。給定一個數(shù)據(jù)矩陣Xd×n={x1，x2，…，xn}，其中d和n分別為X的特征數(shù)和樣本數(shù)。對于第i個數(shù)據(jù)點xi，所有數(shù)據(jù)點{x1，x2，…，xn} 可以連接到xi，每個連接的數(shù)據(jù)點稱為xi的鄰域點。根據(jù)每個鄰域點與xi的歐氏距離大小，賦予一個概率值sij，距離越小對應(yīng)的概率值越大；反之亦然［23-24］。可以通過解決以下問題來得到自適應(yīng)鄰域圖S：

其中：γ為平衡參數(shù)；sij和si為矩陣S的元素和向量。定義圖拉普拉斯矩陣LS=P-(S+ST/2)，其中P為度矩陣，且其對角元素為綜上，式（2）重寫為：

2 基于自適應(yīng)鄰域的魯棒多視圖模型

為了增強模型魯棒性，將式（3）中的原始數(shù)據(jù)X替換為干凈數(shù)據(jù)D，式（3）重構(gòu)為：

其中：β為平衡參數(shù)。與式（1）相比，式（4）中流形正則化項Tr(DLSDT)將增強D的低秩恢復(fù)［19］。與式（3）相比，式（4）用干凈數(shù)據(jù)D構(gòu)造關(guān)系圖S而不是原始數(shù)據(jù)X，且D和S相互迭代增強以獲得最優(yōu)解。因此，用式（4）中的S進行聚類，能夠得到更好的單視圖聚類結(jié)果。

雖然式（4）能夠有效地進行單視圖聚類，但是單視圖數(shù)據(jù)集存在來源單一的局限性，容易導(dǎo)致有偏見的聚類結(jié)果，而且現(xiàn)實生活中，許多數(shù)據(jù)集往往來自于多個源。例如，同一條新聞可以用多種不同語言的文章來報道。與之相反，多視圖聚類會考慮視圖之間的一致性和互補性，從而能夠獲得更可靠的聚類結(jié)果。

因此，將式（4）擴展到多視圖版本：

其中：X(v)、E(v)和D(v)是第v個視圖的原始數(shù)據(jù)、噪聲和干凈數(shù)據(jù)。值得注意的是，式（5）是將學(xué)到的V個低秩干凈數(shù)據(jù)直接融合學(xué)習(xí)一個干凈的共識圖S。與式（5）相比，現(xiàn)有的自適應(yīng)鄰域多視圖算法大都采用兩個步驟，即先學(xué)習(xí)V個圖然后再融合這V個圖來學(xué)習(xí)一個共識圖。兩步融圖方法與式（5）中的一步融圖方法相比，將會丟失一些重要的圖信息。

理想情況下，當(dāng)輸入數(shù)據(jù)有c個類/簇時，學(xué)到的S應(yīng)該具有精確的c個連通部件。盡管式（5）中的S是從多個干凈數(shù)據(jù)中學(xué)習(xí)得到，但式（5）中的S并不滿足這個期望屬性。因此，為得到c個連通部件的S，引入以下秩約束定理。

定理1拉普拉斯矩陣LS的特征值0的重數(shù)c等于圖S中連通分量的個數(shù)。［23］

由定理1 可知，使S滿足c個連通分量的條件等價于S的秩約束rank(LS)=n-c?；诖耍罱K的目標(biāo)函數(shù)轉(zhuǎn)換為：

綜上所述，與文獻［13-18］相比，式（6）中的共識S具有以下優(yōu)點：

1）共識圖S的構(gòu)造是在干凈數(shù)據(jù)上實現(xiàn)，因此S的質(zhì)量將得到提高。

2）共識圖S的學(xué)習(xí)僅用一個步驟，與分開的兩步融圖法相比，可以減少圖信息丟失。

3）共識圖S依靠ANGL 學(xué)到，因此數(shù)據(jù)的局部結(jié)構(gòu)將被保護［23］；且在干凈數(shù)據(jù)D(v)上強加的低秩約束能夠保護數(shù)據(jù)的全局結(jié)構(gòu)［25］。由此可知，S能夠同時保護數(shù)據(jù)的局部結(jié)構(gòu)和全局結(jié)構(gòu)。

3 算法優(yōu)化求解

本文設(shè)計了一個基于增廣拉格朗日乘子（Augmented Lagrange Multiplier，ALM）和交替方向最小化（Alternating Direction Minimization，ADM）的策略［25］來求解式（6）。首先引用輔助變量Z，讓式（6）變得可分割，從而得到以下增廣拉格朗日函數(shù)：

4 實驗與結(jié)果分析

4.1 實驗準備

本文在MRSCV1、BBCSport、COIL20、ORL、UCI digits 五種廣泛使用的基準數(shù)據(jù)集上進行聚類實驗，各個數(shù)據(jù)集屬性如表1 所示。為了驗證RMVGC 的有效性，對比了2 種經(jīng)典的單視圖聚類算法：譜聚類（Spectral Clustering，SC）［26］和自適應(yīng)鄰域聚類（Clustering with Adaptive Neighborhood，CAN）［23］；6 種流行的同類型多視圖聚類算法：AMGL［13］、MLAN［14］、MVGL［15］、GMC［18］、潛在多視圖子空間聚類（Latent Multi-view Subspace Clustering，LMSC）［3］和潛在嵌入空間多視圖聚類（Multi-view Clustering in Latent Embedding Space，MCLES）［27］。其中LMSC 和MCLES 是基于SESL（Self-Expression Subspace Learning）的多視圖子空間聚類算法，可以被看作多視圖圖聚類的一種特殊情況；AMGL、MLAN、MVGL、GMC 是基于ANGL的多視圖圖聚類算法（SESL 和ANGL 是目前流行的圖學(xué)習(xí)技術(shù)）。用表2～6 記錄了聚類性能和時間，聚類性能的值越大，其性能越好，運行時間和標(biāo)準差的值越小越好。實驗平臺是在一臺Mac mini 2018 上運行的Matlab 2016b，其CPU 為Intel Core i7（3.2 GHz），內(nèi)存為16 GB。

4.2 聚類可視化分析

為了評估RMVGC 學(xué)到的干凈多視圖數(shù)據(jù)D的有效性，本文對學(xué)到的干凈數(shù)據(jù)D和原始數(shù)據(jù)X運行t-分布隨機鄰居嵌入（t-distributed Stochastic Neighbor Embedding，t-SNE）［28］。如圖1 所示，在數(shù)據(jù)集ORL 上，學(xué)到的D比X更加緊湊；在MRSCV1數(shù)據(jù)集上，D和X的簇變化特別明顯，在其他簇上，也都有趨于緊湊的趨勢。因此，兩個數(shù)據(jù)集的D都比X更具判別性且更加緊湊清晰。

圖1 ORL和MRSCV1的原始數(shù)據(jù)和干凈數(shù)據(jù)在二維空間中的可視化Fig.1 Visualization of original data and clean data of ORL and MRSCV1 in two-dimensional space

4.3 敏感性與收斂性

如圖2（a）所示，RMVGC 在ORL 數(shù)據(jù)集上收斂曲線下降較快，表明該算法能夠在一定的迭代次數(shù)下收斂。

圖2 RMVGC在ORL數(shù)據(jù)集上的模型分析Fig.2 Model analysis of RMVGC on ORL dataset

如圖2（b）所示，RMVGC 涉及到兩個參數(shù)α和β需要調(diào)整且其調(diào)整范圍都是從10-3～103。由圖3（b）可知，當(dāng)1 ≤α≤103且1 ≤β≤103時，RMVGC 能夠取得令人滿意的聚類性能（即標(biāo)準互信息（Normalized Mutual Information，NMI）），表明該算法對α和β的調(diào)整不敏感。此外，本文的兩個輔助參數(shù)k和λ對所有實驗分別固定為k=30 和λ=1。根據(jù)文獻［8］可知，雖然γ和k都可以用來調(diào)整每個樣本鄰域點個數(shù)，但是由于k是整數(shù)且具有實際意義，因此用k來代替γ參數(shù)的調(diào)整更有效。

4.4 結(jié)果分析

為了避免實驗結(jié)果的隨機性，如表2～6 所示，本文記錄了30 次獨立實驗的平均聚類結(jié)果和標(biāo)準差，聚類結(jié)果的值越大，其性能越好。通過對實驗結(jié)果的進一步分析，可得出以下結(jié)論：

1）一般情況下，多視圖算法優(yōu)于單視圖算法。但如表3所示，在特殊情況下，單視圖算法CAN 比多視圖算法具有更好的聚類性能，這違背了多視圖聚類方法的初衷，表明了進一步開發(fā)優(yōu)秀且穩(wěn)定的多視圖學(xué)習(xí)技術(shù)的必要性。

2）本文所提出的RMVGC 算法相對于所有對比算法上的聚類性能提升較大，這說明了該算法的有效性和泛化能力。

3）雖然AMGL、MLAN、MVGL、GMC 都是基于ANGL 的多視圖聚類算法，但是這些算法都是用ANGL在原始數(shù)據(jù)X(v)上學(xué)習(xí)關(guān)系圖S，而本文的RMVGC 是在學(xué)到的低秩干凈數(shù)據(jù)D(v)上學(xué)習(xí)關(guān)系圖S。圖1中數(shù)據(jù)的可視化分析進一步顯示用D(v)學(xué)圖是可行的。

4）從表2～6 可知，RMVGC 不僅優(yōu)于基于ANGL 的算法，而且優(yōu)于流行的基于SESL的算法，即LMSC和MCLES。

與之前研究的JLSMKC（Joint Low-rank and Sparse Multiple Kernel Subspace Clustering）［29］算法相比，雖然JLSMKC 與RMVGC 都是基于圖學(xué)習(xí)的聚類算法，但是JLSMKC 旨在處理單視圖樣本數(shù)據(jù)的非線性結(jié)構(gòu)，而本文旨在處理多視圖樣本數(shù)據(jù)，挖掘多視圖數(shù)據(jù)之間的共識性。

表1 五個廣泛使用的基準數(shù)據(jù)集的屬性Tab.1 Properties of five widely used benchmark datasets

表2 在MRSCV1數(shù)據(jù)集上的聚類性能和運行時間Tab.2 Clustering performance and running time on MRSCV1 dataset

表3 在BBCSport數(shù)據(jù)集上的聚類性能和運行時間Tab.3 Clustering performance and running time on BBCSport dataset

表4 在COIL20數(shù)據(jù)集上的聚類性能和運行時間Tab.4 Clustering performance and running time on COIL20 dataset

表5 在ORL數(shù)據(jù)集上的聚類性能和運行時間Tab.5 Clustering performance and running time on ORL dataset

表6 在UCI digits數(shù)據(jù)集上的聚類性能和運行時間Tab.6 Clustering performance and running time one UCI digits dataset

5 結(jié)語

針對現(xiàn)存的自適應(yīng)鄰域多視圖聚類算法沒有考慮噪聲和圖融合過程信息丟失的問題，本文提出了一種基于自適應(yīng)鄰域的魯棒多視圖聚類算法，旨在提高模型魯棒性和避免圖融合過程的信息丟失。在5種常用數(shù)據(jù)集上，與2個經(jīng)典的單視圖聚類算法和6 個流行的多視圖聚類算法進行比較的結(jié)果顯示，本文算法具有最好的聚類性能，且因其對噪聲和異常值的魯棒性，該算法易于擴展到實踐應(yīng)用中；但是由于參數(shù)較多，可能會增加計算成本。在未來的工作中，本文提出的框架將考慮與k-means算法結(jié)合，以提高算法效率。