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

李林珂，康昭，龍波

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

0 概述

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

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

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

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

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

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

1 相關(guān)工作

1.1 譜聚類

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

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

同時，可以得到相應(yīng)的度矩陣D∈Rn×n：

相應(yīng)的一階正則拉普拉斯矩陣被定義為：

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

1.2 高階拉普拉斯矩陣

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

定義二階鄰近性［21］

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

其相應(yīng)的度矩陣可被定義為：

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

1.3 多視角譜聚類

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

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

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

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

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

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

1.4 黎曼幾何均值

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

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

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

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

其中：Log 表示SPD 矩陣的對數(shù)運算。在這種情況下，不同圖的信息都能被最優(yōu)SPD 矩陣L較好地表現(xiàn)出來。

2 多視角譜聚類算法

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

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

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

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

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

1）計算得到最優(yōu)拉普拉斯矩陣L*。

獲得最優(yōu)拉普拉斯矩陣的目標函數(shù)如下：

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

2）計算得到最優(yōu)的聚類指標矩陣H。

得到最優(yōu)拉普拉斯矩陣L*后，將其作為輸入代入以下目標函數(shù)：

根據(jù)譜聚類的基本性質(zhì)易得，H的最優(yōu)解為矩陣L*的與c個最小特征值相對應(yīng)的特征向量所構(gòu)成的矩陣。

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

算法RMMSC 算法

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

輸出最優(yōu)拉普拉斯矩陣L*，最優(yōu)聚類指標矩陣H

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

步驟2 初始化：

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

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

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

2.3 算法復(fù)雜度

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

3 實驗

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

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

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

表1 實驗數(shù)據(jù)集屬性Table 1 The attributes of datasets in experiment

各個數(shù)據(jù)集主要屬性的具體描述如下：

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

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

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

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

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

3.2 實驗設(shè)定

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

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

3.3 評估指標

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

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

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

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

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

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

3.4 對比算法

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

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

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

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

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

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

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

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

3.5 實驗結(jié)果

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

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

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

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

3.6 參數(shù)分析

3.6.1 參數(shù)靈敏度

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

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

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

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

3.6.2 算法收斂

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

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

4 結(jié)束語

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