基于黎曼流形的多視角譜聚類算法

李林珂，康昭，龍波

（1.電子科技大學 格拉斯哥學院，成都 611731；2.電子科技大學 計算機科學與工程學院，成都 611731；3.西南技術物理研究所，成都 610041）

0 概述

聚類分析是數據挖掘與機器學習領域中的研究熱點，也是一種重要的數據分析技術［1-3］。傳統的聚類分析旨在將單個視角的物理或抽象集合分成相似對象類，但由于數據來源的多樣性，同一個數據可能有不同的觀察視角［4］，例如文本可以由不同語言表示，圖像可以有不同的特征描述符。多視角聚類旨在從多個視角的數據中學習一個新的統一表示，再將該表示輸入到傳統的聚類算法中。最簡單的結合多視角數據信息的方法是將各視圖特征直接拼接起來，得到單視圖數據進行聚類［4-5］，但這種方法沒有考慮到不同視角數據的差異性對最優解的影響。因此，多視角聚類的主要難點在于如何有效結合不同視角數據的互補信息。

近年來，多視角聚類算法主要分為基于矩陣分解、基于子空間聚類和基于譜聚類三類［6］。基于矩陣分解的多視角聚類算法旨在尋找一個共同的指示矩陣，現有許多研究將非負矩陣分解應用在多視角問題中［7-9］，受深度學習的影響，一些基于深度矩陣分解的方法也被提出［10］，此外還有一些基于核的方法［11］。基于子空間聚類的多視角聚類算法［12-14］將數據分散到不同的子空間中，并為數據尋找合適的低維子空間，代表算法包括稀疏子空間聚類［15］、基于格拉斯曼流形的子空間聚類［16］等。基于譜聚類的多視角聚類算法［17］旨在通過矩陣特征分解在局部流形結構上獲得數據劃分的一致性。

與其他算法相比，譜聚類算法的實現過程相對簡單，且不易陷入局部最優解［18］。提升對各視角互補信息的提取利用率，是提高譜聚類算法效果的關鍵步驟。現已有多種方法用于提升譜聚類算法對不同視角數據的利用率［19-20］。根據現有的互補信息提取方法，將多視角譜聚類算法分為以下三大類［21］：第一類采用聯合訓練方式，使得各個視角的聚類結果彼此關聯［4，19］；第二類假設預定義的鄰接矩陣是最優鄰接矩陣的擾動，然后通過低秩優化或稀疏優化，從所有視角中構造一個最優的鄰接矩陣［20，22］；第三類線性或凸性結合了不同視角的拉普拉斯矩陣，并通過最小化組合矩陣的歸一化分割來優化基拉普拉斯矩陣的組合系數［23］。

近年來，第三類方法在多視角譜聚類領域被廣泛應用，且有多種相關創新方法用于結合不同視角的基拉普拉斯矩陣。在傳統算法中：平均多視角譜聚類（Average Multi-View Spectral Clustering，A-MVSC）為每個視角的拉普拉斯矩陣分配相同的權重值，以得到一個新的拉普拉斯矩陣；單一視角最佳效果譜聚類（Single Best Spectral Clustering，SB-SC）在對每個視角分別進行譜聚類后，選取其中最佳的聚類效果。在典型的相關創新算法中：文獻［24］提出的自動加權多圖學習（Autoweighted Multiple Graph Learning，AMGL）在不引入附加參數的情況下，自動學習每個基拉普拉斯的最佳權重值；文獻［25］采用最大正則角（Canonical Angle）來度量不同視角下譜聚類結果的差異；文獻［21］提出的基于最優鄰域的多視角譜聚類算法（Multi-view Spectral Clustering with Optimal Neighborhood Laplacian Matrix，ONMSC）使最優拉普拉斯矩陣落在所有基拉普拉斯矩陣的鄰域內，并引入高階拉普拉斯矩陣，提高了最優拉普拉斯矩陣對各視角信息的利用率；對于高階拉普拉斯矩陣中引入的高階連接信息，文獻［26］在圖嵌入的研究中指出，頂點之間的一階連接信息代表了圖的頂點間的局部相似關系，二階連接信息表現了擁有相同近鄰的頂點也具有相似性；文獻［21］將高階連接信息應用在多視角譜聚類算法中，在一定程度上提高了聚類的效果，同時研究了各階連接信息對聚類效果的影響，發現隨著所用拉普拉斯矩陣階數的增大，近鄰數的范圍變大，相應算法的判別能力也隨之下降。

傳統的線性與凸性結合方法雖然具有高效性，卻無法很好地獲得每一視角中數據的結構信息。而對稱正定（Symmetric Positive Definite，SPD）流形中的黎曼幾何均值［27］將不同視角的拓撲信息結合，相比于傳統算法，更加有效地提取出了各層數據的特征。現有大量基于隨機塊模型的多層圖研究［28-30］存在。例如，文獻［27］將SPD 幾何均值與特征嵌入結合，提高了多層網絡數據聚類的效果。

為更好地將各視角數據的互補信息引入到用于譜聚類的最優拉普拉斯矩陣中，本文提出一種基于黎曼幾何均值與高階連接信息的多視角譜聚類算法。按一定的權重線性結合單一視角的各階拉普拉斯矩陣，將其作為該視角的基拉普拉斯矩陣。在此基礎上，計算各視角的基拉普拉斯矩陣的幾何均值即最優拉普拉斯矩陣并作為輸入進行譜聚類。本文方法利用黎曼幾何均值來聚合各視圖信息，充分挖掘數據中的流形信息，同時引入高階拉普拉斯矩陣，實現對數據中高階連接信息的挖掘。

1 相關工作

1.1 譜聚類

譜聚類算法是由圖論演變而來、基于譜圖劃分理論的聚類算法［31］，其將所有數據樣本定義為無向圖G=(X,E)的頂點，將樣本數據的相似性看作點與點之間帶權重的邊，從而建立鄰接矩陣（相似度矩陣），并求得正則拉普拉斯矩陣進行降維。對所有新數據點分組，使同一組對象之間具有較高的相似度而不同組的差異較大，從而達到聚類的目的。譜聚類算法的具體步驟如下：

定義圖G=(X,E)。其 中：X=[x1,x2,…,xn]T∈Rn×d為圖的頂點集，即數據樣本集；n為樣本數；d為樣本的特征維度；E為連接頂點之間邊的集合。基于k 近鄰（k-Nearest Neighbor，kNN）算法，可以對給定的數據集X與核函數κ(·,·) 構造鄰接矩陣A∈Rn×n，即xi、xj中只要有一個在對方的k個近鄰中時，則被視為互相關聯的，其距離可由核函數κ(·,·)表示。鄰接矩陣A的i行j列被構造如下：

同時，可以得到相應的度矩陣D∈Rn×n：

相應的一階正則拉普拉斯矩陣被定義為：

定義H∈Rn×c為聚類指示矩陣，其中c為類別數，則標準化譜聚類的目標函數如下：

1.2 高階拉普拉斯矩陣

現有研究表明，高階連接信息能夠有效提高多視角譜聚類的效果，且在使用二階連接信息時，聚類效果與運算效率相對較好。因此，本文只引入圖的二階連接信息，研究其對本文算法聚類效果的影響。

定義二階鄰近性［21］

二階鄰近性指的是網絡中的一對頂點(u,v)的近鄰網絡結構的相似性。令aj為一階鄰接矩陣A的第j列，則二階鄰接矩陣A(2)可被定義如下：

其相應的度矩陣可被定義為：

由此可以得到二階正則拉普拉斯矩陣：

1.3 多視角譜聚類

多視角譜聚類可被視為對多圖的聚類問題，其無向圖可被表示為：

其中：V≥1 表示視角的數目，也是圖的個數。對每個視 角p∈{1,2,…,V} 構造其鄰接矩 陣A1,A2,…,AV∈Rn×n與一階正則拉普拉斯矩陣L1,L2,…,LV∈Rn×n。為了在聚類時應用每個視角的數據特征，文獻［23］線性結合了各個視角的拉普拉斯矩陣，并得到了用于譜聚類的最優拉普拉斯矩陣，其目標函數如下：

其中：μp表示第p個視角的線性組合權重值，共有V個視角；向量μ為各個視角拉普拉斯矩陣的權重值集；r是平衡各個視角貢獻度的超參數。但是文獻［23］算法過度縮減了最優拉普拉斯矩陣的可行集［11］，導致解決方案代表性較弱，其性能可能略遜于使用單個視角進行聚類的效果。

文獻［21］考慮了低階與高階拉普拉斯矩陣的特性，使最優拉普拉斯矩陣落在各階拉普拉斯矩陣線性結合后的鄰域中，并用該最優拉普拉斯矩陣進行譜聚類，其目標函數如下：

其中：L*表示最優拉普拉斯矩陣；表示第u階基拉普拉斯矩陣的線性組合；O為最高階數，[O]等同于{1,2,…,O}；γ為重要程度平衡系數。在式（12）中，相關性測量矩陣M記錄了鄰接矩陣之間的內核校準值［32］，其定義如下：

文獻［21］算法雖然增強了用以譜聚類的拉普拉斯矩陣的不同視角的數據信息表示能力，且提高了譜聚類的聚類效果，但是仍然沒有很好地結合各視角的拉普拉斯矩陣的信息。

1.4 黎曼幾何均值

基于圖論的隨機塊模型（Stochastic Block Model，SBM）是近年來普遍用于非標準數據聚類與社區檢測的聚類方法，其原理與譜聚類算法類似，但數據節點間的鄰接關系在譜聚類算法中被表示為給定值，在隨機塊模型中卻被表示為伯努利隨機變量，可根據概率對等性對該模型中具有相似特征的節點進行分類［33-34］。在隨機塊模型的多層數據聚類問題中，相比于矩陣的算數平均值，矩陣冪均值在冪趨于-∞時更好地恢復了互補層數據的聚類信息。

黎曼幾何均值是一種基于SPD 流形中黎曼距離的矩陣冪均值。尋找不同圖SPD 矩陣的黎曼幾何均值的過程，等同于尋找一個到各個圖SPD 矩陣{Lp}1≤p≤V黎曼距離最小 的SPD矩陣L的過程，可表示為［35］：

其中：Φ(·,·)算子表示對SPD 矩陣的一系列操作；η(N)表示N×N的SPD 矩陣的流形；D：η(N)×η(N)→R為相應距離。

式（14）中黎曼距離D的具體表達式如下［35］：

其中：Log 表示SPD 矩陣的對數運算。在這種情況下，不同圖的信息都能被最優SPD 矩陣L較好地表現出來。

2 多視角譜聚類算法

2.1 幾何均值與一階拉普拉斯矩陣的結合

在傳統的多視角譜聚類算法中，用于譜聚類的最優拉普拉斯矩陣由各視角的拉普拉斯矩陣線性結合所得。這種信息結合方式類似于算數均值的運算，沒有很好地考慮到不同視角的特有拓撲信息，從而降低了最優拉普拉斯矩陣的代表性。

為提高數據的利用率，本文首先計算不同視角下相應的一階基拉普拉斯矩陣的黎曼幾何均值，即最優拉普拉斯矩陣L*，并將其作為譜聚類算法的輸入矩陣得到最終的聚類結果。該過程可用以下目標函數表示：

2.2 幾何均值與高階拉普拉斯矩陣的結合

為更好地在最優拉普拉斯矩陣L*中表示出各視角的信息，本文將黎曼幾何均值與高階拉普拉斯矩陣的思想相結合。首先按一定的權重值αu(u∈[O])線性結合單一視角的各階拉普拉斯矩陣，作為該視角的基拉普拉斯矩陣；然后計算各視角相應的基拉普拉斯矩陣的幾何均值，并將該幾何均值作為譜聚類算法的輸入，進行數據聚類。具體步驟如下：

1）計算得到最優拉普拉斯矩陣L*。

獲得最優拉普拉斯矩陣的目標函數如下：

其中：αu為第u階拉普拉斯矩陣的權重值。當V＞2時，該問題沒有閉式解，因此，本文通過Fréchet-Karcher 梯度流計算其幾何均值。具體的迭代過程如下［36］：

2）計算得到最優的聚類指標矩陣H。

得到最優拉普拉斯矩陣L*后，將其作為輸入代入以下目標函數：

根據譜聚類的基本性質易得，H的最優解為矩陣L*的與c個最小特征值相對應的特征向量所構成的矩陣。

綜上所述，完整的基于高階拉普拉斯矩陣與黎曼幾何均值的多視角譜聚類算法（Riemann Manifold based Multi-view Spectral Clustering，RMMSC）描述如下：

算法RMMSC 算法

輸入樣本數n，數據類別數c，V個特征視角的數據集[x1,x2,…,xV]T，各階拉普拉斯矩陣平衡參數αu，迭代步長β，近鄰數N

輸出最優拉普拉斯矩陣L*，最優聚類指標矩陣H

步驟1建立數據各視角的各階鄰接矩陣與正則拉普拉斯矩陣。

步驟2 初始化：

步驟3重復式（18），直到滿足迭代停止條件：

步驟4通過式（19）計算H。

對于最終得到的H，RMMSC 算法用K-means 算法為樣本的最終聚類結果分配對應的標簽。為減小K-means 算法的隨機性，本文在每一次實驗中，對其聚類過程重復50 次，并取具有最小K-means 損失值的聚類結果。

2.3 算法復雜度

本文算法采用的迭代方法涉及矩陣對數與指數的運算，其對應時間復雜度為O(n3)。最終對H的計算涉及對大小為n2的矩陣的奇異值分解（Singular Value Decomposition，SVD）問題，其對應的時間復雜度也為O(n3)［21］。總體而言，算法復雜度為O(In3)，其中I為迭代次數，這與現有多數算法的復雜度處于同一數量級，例如AMGL［24］、ONMSC［21］。

3 實驗

為驗證本文方法的聚類效果，選擇5 個當下流行的數據集，分別從聚類精度（ACC）、歸一化互信息（NMI）、純度（Purity）這三個角度與已有的7 個聚類算法做對比實驗。實驗的計算機環境為：處理器為Intel?CoreTMi5-8400 CPU@2.80 GHz，內存16 GB，操作系統為Windows10，編程語言為MATLAB R2017a（64 位）。RMMSC 算法源代碼鏈接為：https：//github.com/sckangz/RMMSC。

3.1 數據集

本文采用包括自然語言處理、圖像識別、圖像處理等分支，機器學習中常用的5 個數據集作為測試數據集，如表1 所示。

表1 實驗數據集屬性Table 1 The attributes of datasets in experiment

各個數據集主要屬性的具體描述如下：

Flower17：本數據集包含17 個英國常見的花朵類別，每個類別包含80 幅圖，共1 360 個樣本，有hsv、hog、color、shape 等7 個特征維度。

BBCSport：本數據集由英國廣播公司體育網站的文件組成。選取其中554 個樣本，包含5 個領域的體育新聞文章（田徑、板球、足球、橄欖球、網球）。數據集包含從兩個特征維度構造的矩陣。

UCI-Digit：本數據集包含手寫數字0～9的2 000個樣本，共10 個類別。本實驗使用了樣本的3 個特征集，分別為76 個字符形狀的傅里葉系數、216 個輪廓相關的特征以及64 個Karhunen-love 系數。

Mfeat：本數據集包含摘自荷蘭實用地圖集的手寫數字0～9 的2 000 個樣本，共有10 個類別，每個類別200 個圖案。本實驗使用樣本的12 個特征集。

Caltech101mit：本數據集是由102 個類別的對象圖片組成的數據集，這些圖像分別隸屬于102 個種類，包含大象、自行車、足球、人類的大腦等，主要用于目標識別和圖像分類，共1 530 個樣本、25 個特征視角。

3.2 實驗設定

根據譜聚類相關文獻，為達到較好的實驗效果，本文對實驗中涉及的3 個主要超參數進行設定。近鄰數在[0.05s,0.15s,…,0.95s]中取值，其中s=n/c為平均樣本數。經驗證發現，近鄰數取值在10 附近時算法聚類效果相對較好。由于本實驗只涉及一二階拉普拉斯矩陣的應用，2.2節中算法的各階拉普拉斯矩陣的平衡參數αu被簡化為參數α，即在線性結合時，設置一階拉普拉斯矩陣的權重為1，二階拉普拉斯矩陣的權重為α。同時，經所用數據集驗證，算法在迭代步長為0 ＜β＜時收斂，且在取值為時算法體現出較好的收斂效果與較快的收斂速度［37］。

除此之外，由于拉普拉斯矩陣是對稱半正定矩陣，其特征向量的所有元素為0 或正數。但MATLAB 中的矩陣對數函數（logm）無法對特征值中含有非正數的矩陣進行運算，即logm 函數的輸入矩陣需要為對稱正定矩陣，而對稱半正定拉普拉斯矩陣特征向量中的0 元素則影響了logm 函數的正常使用。為解決此問題，本文對各視角的基拉普拉斯矩陣歸一化處理至（0，1），從而避免logm 函數無法運算得到正確結果的情況.

3.3 評估指標

本文實驗采用以下3 個常用的評價指標來評價算法的聚類效果：

1）精確度（ACC），用于比較聚類結果的標簽與數據集所提供的標簽的匹配度，計算公式如下：

其中：li與分別表示xi的聚類結果與相應的聚類標簽；n為樣本總數。當且僅當x=y時，函數δ(x,y)=1，其他情況下為0。基于Kuhn-Munkres 算法［38］，置換映射函數map(.)將每個聚類的索引映射到具體的標簽上。

2）歸一化互信息（Normalized Mutual Information，NMI），用于衡量兩個聚類結果的相似程度即聚類效果，計算公式如下：

3）純度（Purity），即正確聚類樣本數占總樣本數的比例，計算公式如下［39］：

其中：ni表示 類別Ci中數據點 的個數表示第i組輸入數據被分配到第j類的樣本個數。算法的ACC、NMI、Purity 指標值越大，聚類效果越好。

3.4 對比算法

為證明本文算法的有效性，將其與7 個現有的多視角譜聚類算法以及多核聚類算法進行對比。

1）平均多視角譜聚類（Average Multi-View Spectral Clustering，A-MVSC）算法，其為每個視角的拉普拉斯矩陣分配相同的權重值，以得到一個新的拉普拉斯矩陣進行聚類。

2）單一視角最佳效果譜聚（Single Best Spectral Clustering，SB-SC）算法，其對每個視角分別進行譜聚類，并選取最佳的聚類效果。

3）自動加權多圖學習（Auto-weighted Multiple Graph Learning，AMGL）算法［24］，該算法可以自動學習每個圖的最優權值，且不需要引入附加參數。

4）自適應近鄰的多視角學習（Multiview Learning with Adaptive Neighbors，MLAN）算 法［40］，該算法可以同時進行聚類和局部結構學習。

5）最優鄰域的多核聚類（Optimal Neighbors Kernel Clustering，ONKC）算法［11］，該算法構造了有自適應能力的局部核，充分考慮了單個數據樣本的局部密度。

6）基于矩陣誘導正則化的多核K 均值聚類（Multiple Kernel k-means Clustering with Matrix Induced Regularization，MKKM-MR）算法［10］，該算法減少了冗余核對聚類結果的影響，增強了所選核的多樣性。

7）基于最優鄰域拉普拉斯矩陣的多視角譜聚類（Multi-View Spectral Clustering with Optimal Neighborhood Laplacian Matrix，ONMSC）算法［21］，該算法引入了低階與高階拉普拉斯矩陣的最優鄰域，增強了最優拉普拉斯函數的容量，且利用隱藏的高階連接信息獲得了較好的收斂性。

3.5 實驗結果

基于一階拉普拉斯矩陣和二階拉普拉斯矩陣的幾何均值的多視角譜聚類性能如表1 和表2 所示，其中最優數據加粗表示。可以看出，本文算法在Flower17、BBCSport，UCI-Digit、Mfeat 數據集中的聚類效果普遍優于其他對比算法。以Flower17 數據集為例，其ACC 較基準模型ONMSC 提高了1.47 個百分點，Purity 提高了1.04 個百分點。但Caltech101mit數據集聚類的ACC 與Purity 稍低于ONMSC。

表2 不同聚類算法在5 個基準數據集上的性能對比Table 2 Performance comparison of different clustering algorithms on five benchmark datasets

相比于一階拉普拉斯矩陣和二階拉普拉斯矩陣的單獨應用，按一定權重值結合一階與二階拉普拉斯矩陣在一定程度上提升了Flower17、BBCSport、Caltech101mit數據集的聚類效果。對于Flower17 數據集，ACC 提高了0.67 個百分點，NMI 提高了0.93 個百分點，Purity提高了0.66個百分點。而UCI-Digit與Mfeat數據集在應用二階拉普拉斯矩陣后，也表現出高于AMGL、MLAN、ONMSC 等算法的聚類效果。

由于本文算法包含多次對矩陣的開方（sqrtm）與對數（logm）運算，在所選數據集最優結果對應的參數取值下，其平均運行時間約為365 s（對于小樣本數據集，如BBCSport 運算時間極短，為4 s；但對大樣本數據集如Caltech101 運行時間較長，為483 s），長于基準模型ONMSC 算法的平均運行時間27 s。但本文算法達到收斂所需的迭代次數普遍少于ONMSC 算法。

3.6 參數分析

3.6.1 參數靈敏度

本文算法共涉及3 個參數：α，β，s。其中：α為二階拉普拉斯矩陣的權重；β為迭代步長；s為平均樣本數，用以計算近鄰數。為檢驗RMMSC 的參數靈敏度，本文應用了網格搜索的方法，固定2 個參數，在一定范圍內改變其他參數的值。對參數進行靈敏性分析后發現，β對各數據集聚類效果影響極小，可忽略不計；α對聚類結果有一定的影響，但在較大的參數范圍內相對穩定；s對BBCSport 數據集聚類結果影響較大，而對其他數據集影響相對較小。同時，該算法在多個參數取值下的結果皆優于基準算法ONMSC，說明其可行性強。圖1～圖3 展示了算法對選取的2 個數據集（Flower17 與Caltech101mit）的參數靈敏度，可以看出，對于Caltech101mit，算法在s=0.05 時不收斂，無法得到有效聚類結果。

圖1 參數α 對聚類效果的影響Fig.1 Parameter α’s influence on clustering effect

圖2 s 與α 對聚類效果的共同影響Fig.2 Joint influence of s and α on clustering effect

圖3 參數s 對聚類效果的影響Fig.3 Parameter s’s influence on clustering effect

3.6.2 算法收斂

對所用數據集，本文在特定參數下測試所提算法的迭代收斂性。圖4 顯示了收斂性測試結果，其中橫坐標表示迭代的次數，縱坐標表示兩次連續迭代所得的拉普拉斯矩陣的差值矩陣的二范數。可以看出，在合適的參數取值下，所用數據集均在15 次迭代內達到了較好的收斂效果。

圖4 本文算法收斂性分析Fig.4 Convergence analysis of the proposed algorithm

4 結束語

本文提出一種基于高階拉普拉斯矩陣與黎曼幾何均值的多視角譜聚類算法。由于頂點之間的二階鄰近性反映出擁有相同近鄰的頂點也在對方的鄰域中，因此與傳統的譜聚類算法相比，該算法一階與二階拉普拉斯矩陣的共同應用提高了不同視角基拉普拉斯矩陣對視角信息的表達能力。此外，相比于算術均值的使用，SPD 流形下的黎曼幾何均值將各視角的拓撲信息概括到單個最優拉普拉斯矩陣，使最終用于譜聚類的拉普拉斯矩陣更好地表達了各視角數據的互補信息。在多個數據集上的測試結果表明，該算法具有較好的聚類性能與收斂性。本文同時給出了具有較快收斂速率與聚類效果的推薦參數取值。后續將會進一步優化本文算法，縮短其在較大數據集下的運算時間，同時也將結合子空間聚類思想，進一步提高聚類性能。