基于自適應鄰域的魯棒多視圖聚類算法

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

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

0 引言

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

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

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

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

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

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

2）開發了一個同時學習共識鄰域圖S和低秩干凈數據的統一目標函數，該函數能夠迭代增強S和直到獲得最優的S*，并在該S*上執行譜聚類得到聚類結果；與現存的基于ANGL 的多視圖算法相比，這是研究基于ANGL的第一個利用干凈數據構圖的魯棒多視圖工作。

1 魯棒主成分分析與自適應鄰域聚類

1.1 魯棒主成分分析（RPCA）

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

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

1.2 自適應鄰域圖學習（ANGL）

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

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

2 基于自適應鄰域的魯棒多視圖模型

為了增強模型魯棒性，將式（3）中的原始數據X替換為干凈數據D，式（3）重構為：

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

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

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

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

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

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

由定理1 可知，使S滿足c個連通分量的條件等價于S的秩約束rank(LS)=n-c?；诖?，最終的目標函數轉換為：

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

1）共識圖S的構造是在干凈數據上實現，因此S的質量將得到提高。

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

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

3 算法優化求解

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

4 實驗與結果分析

4.1 實驗準備

本文在MRSCV1、BBCSport、COIL20、ORL、UCI digits 五種廣泛使用的基準數據集上進行聚類實驗，各個數據集屬性如表1 所示。為了驗證RMVGC 的有效性，對比了2 種經典的單視圖聚類算法：譜聚類（Spectral Clustering，SC）［26］和自適應鄰域聚類（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 是目前流行的圖學習技術）。用表2～6 記錄了聚類性能和時間，聚類性能的值越大，其性能越好，運行時間和標準差的值越小越好。實驗平臺是在一臺Mac mini 2018 上運行的Matlab 2016b，其CPU 為Intel Core i7（3.2 GHz），內存為16 GB。

4.2 聚類可視化分析

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

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

4.3 敏感性與收斂性

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

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

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

4.4 結果分析

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

1）一般情況下，多視圖算法優于單視圖算法。但如表3所示，在特殊情況下，單視圖算法CAN 比多視圖算法具有更好的聚類性能，這違背了多視圖聚類方法的初衷，表明了進一步開發優秀且穩定的多視圖學習技術的必要性。

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

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

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

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

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

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

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

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

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

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

5 結語

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