李林珂，康昭，龍波

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

0 概述

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

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

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

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

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

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

1 相關(guān)工作

1.1 譜聚類

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

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

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

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

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

1.2 高階拉普拉斯矩陣

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

定義二階鄰近性［21］

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

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

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

1.3 多視角譜聚類

多視角譜聚類可被視為對(duì)多圖的聚類問(wèn)題，其無(wú)向圖可被表示為：

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

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

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

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

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

1.4 黎曼幾何均值

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

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

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

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

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

2 多視角譜聚類算法

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

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

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

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

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

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

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

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

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

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

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

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

算法RMMSC 算法

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

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

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

步驟2 初始化：

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

步驟4通過(guò)式（19）計(jì)算H。

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

2.3 算法復(fù)雜度

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

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

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

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

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

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

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

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

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

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

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

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

3.2 實(shí)驗(yàn)設(shè)定

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

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

3.3 評(píng)估指標(biāo)

本文實(shí)驗(yàn)采用以下3 個(gè)常用的評(píng)價(jià)指標(biāo)來(lái)評(píng)價(jià)算法的聚類效果：

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

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

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

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

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

3.4 對(duì)比算法

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

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

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

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

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

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

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

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

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

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

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

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

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

3.6 參數(shù)分析

3.6.1 參數(shù)靈敏度

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

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

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

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

3.6.2 算法收斂

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

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

4 結(jié)束語(yǔ)

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