基于共享近鄰的多視角譜聚類算法

宋 艷，殷 俊

（上海海事大學(xué)信息工程學(xué)院，上海 201306）

（?通信作者電子郵箱junyin@shmtu.edu.cn）

0 引言

聚類分析［1］就是按照某個(gè)特定標(biāo)準(zhǔn)將一個(gè)數(shù)據(jù)集分割成不同的簇，使同一簇的數(shù)據(jù)盡可能地聚集到一起。傳統(tǒng)的k-means 聚類算法［2］對(duì)樣本空間有特定的要求，當(dāng)樣本空間不為凸時(shí)，算法就會(huì)陷入局部最優(yōu)。與k-means 算法相比，譜聚類算法具有能在任意形狀的樣本空間上聚類且收斂于全局最優(yōu)的優(yōu)點(diǎn)。

譜聚類［3］是一種基于圖的聚類方法，且性能高度依賴于相似矩陣。目前，用于構(gòu)造相似矩陣的方法主要有高斯核函數(shù)法［4］、K 近鄰法（K-Nearest Neighbor，KNN）［5］和ε-閾值法。高斯核函數(shù)一般用于全連接相似矩陣，KNN 和ε-閾值法用于局部連接相似矩陣，三種計(jì)量方法均以距離作為衡量單位，對(duì)于處在不同密度中的數(shù)據(jù)點(diǎn)之間的相似關(guān)系無法衡量，而數(shù)據(jù)點(diǎn)之間的相似性不僅跟兩者之間的距離有關(guān)，同時(shí)也跟兩者是否處在同一密度區(qū)域有關(guān)。針對(duì)以上問題，本文用共享近鄰方法結(jié)合經(jīng)典的高斯核函數(shù)方法，提出了基于共享近鄰的自適應(yīng)高斯核函數(shù)方法。

多視角譜聚類算法［6-8］在單視角算法的基礎(chǔ)上利用不同視角數(shù)據(jù)之間的相關(guān)性以及互補(bǔ)性獲得更多有價(jià)值的信息，是目前譜聚類研究中的一個(gè)重要方向。大部分多視角譜聚類算法在結(jié)合多個(gè)視角的信息后再次用k-means算法實(shí)現(xiàn)聚類，這些方法仍然難以擺脫k-means 算法初始聚類中心不確定的問題。針對(duì)以上問題，本文提出基于共享近鄰的多視角譜聚類算法（Multi-View spectral clustering algorithm based on Shared Nearest Neighbor，MV-SNN），將改進(jìn)的相似矩陣相加整合得到全局相似矩陣，同時(shí)利用拉普拉斯矩陣秩約束理論，直接通過全局相似矩陣得到最終的聚類結(jié)果。

1 相關(guān)工作

譜聚類的基本思想是利用從數(shù)據(jù)中得到的更低維的特征矩陣實(shí)現(xiàn)聚類，主要依靠?jī)蓚€(gè)部分完成聚類工作：1）圖的構(gòu)造；2）對(duì)構(gòu)造好的圖誘導(dǎo)出拉普拉斯矩陣并作特征分解，將數(shù)據(jù)嵌入到特征向量空間，最后再次使用k-means 算法實(shí)現(xiàn)聚類。在多視角譜聚類算法中，Kumar等［9］提出了協(xié)同正則多視角譜聚類（Co-regularized Multi-view Spectral Clustering，CRSC）算法，Zhan 等［10］提出了圖學(xué)習(xí)的多視角譜聚類（Graph Learning for Multi-View clustering，MVGL）算法。

1.1 協(xié)同正則多視角譜聚類算法

Kumar 等［9］將用于有監(jiān)督訓(xùn)練的協(xié)同思想應(yīng)用到無監(jiān)督譜聚類算法中，算法在多視角數(shù)據(jù)聚類結(jié)構(gòu)一致性假設(shè)的前提下，同時(shí)考慮每個(gè)視角譜聚類算法的優(yōu)化情況和不同視角之間的差異情況，提出成對(duì)優(yōu)化模式和基于中心的優(yōu)化模式。后者對(duì)所有視角的數(shù)據(jù)優(yōu)化出一個(gè)中心特征嵌入矩陣U*來平衡其他視角的數(shù)據(jù)，目標(biāo)函數(shù)如下：

其中：v表示視角個(gè)數(shù)；Tr（）表示求跡運(yùn)算；I表示單位矩陣；參數(shù)γi為正則化加權(quán)項(xiàng)，它的大小代表了視角i 的重要程度，且需要人工指定。max Tr(U(i)TL(i)U(i)) 是第i 個(gè)視角的譜聚類優(yōu)化函數(shù)，-Tr(U(i)U(i)TU*U*T) 則表示第i 個(gè)視角的特征嵌入矩陣和中心嵌入矩陣的誤差函數(shù)，通過最小化差異函數(shù)來平衡中心嵌入矩陣和各個(gè)視角特征嵌入矩陣之間的差異，將兩者需求進(jìn)行整合得到最終的式（1），最后再對(duì)矩陣U*實(shí)施k-means方法得到聚類結(jié)果。CRSC 算法是多視角譜聚類算法的開端，之后的多視角聚類方法均是在各個(gè)視角聚類結(jié)構(gòu)一致的假設(shè)條件下開展工作。

1.2 圖學(xué)習(xí)的多視角譜聚類算法

首先將v個(gè)視角下通過KNN算法得到的相似矩陣S(i)乘以對(duì)應(yīng)權(quán)重Q(i)相加整合；然后構(gòu)造出一個(gè)全局相似矩陣A；最后通過最小化誤差函數(shù)來最小化兩者之間的差異，從而獲得全局相似矩陣A的值。同時(shí)該優(yōu)化框架結(jié)合拉普拉斯矩陣秩約束方法，根據(jù)全局相似矩陣得到聚類結(jié)果，目標(biāo)函數(shù)如下：

其中：Aj表示矩陣A的第j列向量，列和為1；γ為權(quán)衡參數(shù)，用來控制后一項(xiàng)的比重；矩陣L為矩陣A所對(duì)應(yīng)的拉普拉斯矩陣。

由于相似矩陣的構(gòu)造方法對(duì)譜聚類算法有很大影響，而MVGL 算法在前期使用KNN 算法構(gòu)造相似矩陣，所以它最終的聚類準(zhǔn)確率會(huì)受到一定影響。

2 相似矩陣構(gòu)造方法

譜聚類算法中相似矩陣的構(gòu)造方法最經(jīng)典的應(yīng)該屬于高斯核函數(shù)和KNN算法。

高斯核函數(shù)：

其中：Xi和Xj表示兩個(gè)數(shù)據(jù)點(diǎn)；σ 是一個(gè)需要人工指定的參數(shù)。該構(gòu)造方法中，兩點(diǎn)的相似度只與兩點(diǎn)間的歐氏距離有關(guān)，但是只以距離作為衡量相似度的標(biāo)準(zhǔn)，對(duì)應(yīng)不同密度的簇就無法處理。

KNN 算法是一種高斯核函數(shù)的局部連接構(gòu)造方法，它并不能解決存在密度差異的兩個(gè)數(shù)據(jù)點(diǎn)之間的相似情況，而相似值應(yīng)同時(shí)滿足空間上相近的兩個(gè)數(shù)據(jù)點(diǎn)之間具有較高的相似度且位于同一個(gè)簇的數(shù)據(jù)點(diǎn)具有較高的相似度兩個(gè)要求。本文利用共享近鄰的思想來構(gòu)造相似矩陣，該方法根據(jù)數(shù)據(jù)集流形結(jié)構(gòu)的特點(diǎn)來增強(qiáng)同簇?cái)?shù)據(jù)點(diǎn)之間的相似性。

2.1 基于共享近鄰的構(gòu)造方法

數(shù)據(jù)點(diǎn)Xi和Xj之間的共享最近鄰（Shared Nearest Neighbor，SNN）：

其中：N(Xi)表示與點(diǎn)Xi最近的前k個(gè)點(diǎn)構(gòu)成的集合；N(Xj)表示與點(diǎn)Xj最近的前k個(gè)點(diǎn)構(gòu)成的集合。如圖1所示，兩個(gè)對(duì)象A、B 的8 個(gè)最近鄰中，有4 個(gè)（深色）是A、B 共享的，因此這兩個(gè)對(duì)象之間的共享近鄰個(gè)數(shù)為4。

圖1 共享近鄰個(gè)數(shù)示意圖Fig.1 Schematic diagram of number of shared neighbors

結(jié)合共享近鄰的思想，給出任意兩點(diǎn)Xi和Xj之間的相似度度量Sij，基于共享近鄰的自適應(yīng)高斯核函數(shù)：

其中：σi和σj分別為點(diǎn)Xi和點(diǎn)Xj到各自第p 個(gè)近鄰的歐氏距離（p 一般取7），使用特定的縮放參數(shù)σi和σj，不僅能夠解決高斯核函數(shù)中σ 需要人工指定的問題，而且也能捕捉到兩點(diǎn)鄰域內(nèi)數(shù)據(jù)點(diǎn)分布的稀疏稠密情況從而得到更好的聚類結(jié)果。為了進(jìn)一步驗(yàn)證以上函數(shù)有效性，本文在以下兩種具體情形中對(duì)其結(jié)果進(jìn)行分析：

1）假設(shè)當(dāng)兩點(diǎn)Xi和Xj距離較近時(shí)，則值較小，于是Sij值變大，使得相近的數(shù)據(jù)點(diǎn)具有較高的相似度。

2）假設(shè)當(dāng)數(shù)據(jù)點(diǎn)Xi和Xj位于同一簇中，數(shù)據(jù)點(diǎn)Xi和Xk位于不同簇中，且時(shí)，統(tǒng)計(jì)它們之間共享近鄰的個(gè)數(shù)，有SNN(Xi，Xj)＞SNN(Xi，Xk)（同一密度簇中的共享近鄰個(gè)數(shù)更多），進(jìn)而得到相似度Sij＞Sik，使得位于同一簇上的兩點(diǎn)具有更高的相似度。

因?yàn)樽V聚類算法適合處理比較稀疏的數(shù)據(jù)，為了得到更精確的結(jié)果，本文進(jìn)一步對(duì)相似矩陣進(jìn)行稀疏化處理，只有兩個(gè)數(shù)據(jù)點(diǎn)之間的共享近鄰數(shù)大于閾值δ，相似度Sij值才不為0，具體的處理過程總結(jié)在下列的算法1中。

算法1 相似矩陣的構(gòu)造方法。

輸出 相似矩陣S。

if 數(shù)據(jù)點(diǎn)Xi在點(diǎn)Xj的k 近鄰空間中且數(shù)據(jù)點(diǎn)Xj在點(diǎn)Xi的k 近鄰空間中

if SNN(Xi，Xj)＞閾值δ

在該算法中，主要有兩個(gè)參數(shù)：k 和δ。k 值過大則會(huì)導(dǎo)致最終只有一個(gè)簇，k值過小則會(huì)導(dǎo)致每個(gè)數(shù)據(jù)點(diǎn)都自成一簇；δ值根據(jù)k值而定，一般情況下，δ=k/2。

2.2 相似矩陣散點(diǎn)圖實(shí)驗(yàn)

為了驗(yàn)證算法1 的有效性，將KNN 算法和算法1 在人工數(shù)據(jù)集（三環(huán)數(shù)據(jù)集，具體介紹見4.1 節(jié)）上構(gòu)造相似矩陣（兩者的參數(shù)k 均取10）并通過散點(diǎn)圖表示，如圖2 所示。所測(cè)試的數(shù)據(jù)集為其中第1 個(gè)數(shù)據(jù)點(diǎn)到第100個(gè)數(shù)據(jù)點(diǎn)屬于第1 個(gè)簇，第101 個(gè)數(shù)據(jù)點(diǎn)到第200 個(gè)數(shù)據(jù)點(diǎn)屬于第2個(gè)簇，第201個(gè)數(shù)據(jù)點(diǎn)到第300個(gè)數(shù)據(jù)點(diǎn)屬于第3個(gè)簇，一共有3 個(gè)簇；因此理論上該數(shù)據(jù)集得到的相似矩陣應(yīng)該是標(biāo)準(zhǔn)的對(duì)角塊結(jié)構(gòu)。

圖2中的散點(diǎn)表示兩個(gè)數(shù)據(jù)點(diǎn)相似：從圖2（a）可以看出，由算法1 得到的相似矩陣圖中的點(diǎn)基本都集中在對(duì)角塊上，說明達(dá)到了簇內(nèi)數(shù)據(jù)點(diǎn)之間高度相似的要求；在圖2（b）由KNN算法得到的散點(diǎn)圖中，很多點(diǎn)散落在對(duì)角結(jié)構(gòu)之外，說明不同簇的很多數(shù)據(jù)點(diǎn)之間依然相似，并沒有達(dá)到相似矩陣的構(gòu)造要求。

圖2 三環(huán)數(shù)據(jù)集相似矩陣的散點(diǎn)圖Fig.2 Scatter plots of similarity matrix of three-circle data set

3 基于共享近鄰的多視角譜聚類算法

為了提高算法性能，在進(jìn)行多視角數(shù)據(jù)融合前，MV-SNN算法先對(duì)單視角數(shù)據(jù)構(gòu)成的相似矩陣進(jìn)行優(yōu)化；然后將各個(gè)視角優(yōu)化后的相似矩陣相加整合得到一個(gè)全局相似矩陣；最后利用秩約束理論，直接通過全局相似矩陣得到最終的聚類結(jié)果。

3.1 目標(biāo)函數(shù)

為了保留各個(gè)視角攜帶的信息，本文將不同視角下的相似矩陣通過相加的方式融合為一個(gè)全局相似矩陣，表示如下：

其中：S(i)*表示優(yōu)化過的第i 個(gè)視角的相似矩陣（優(yōu)化過程在3.3節(jié)給出），因?yàn)橄嗨凭仃?，它滿足下列定理1。

定理1相似矩陣S的連通分支數(shù)c等于其對(duì)應(yīng)的拉普拉斯矩陣的特征值為0的個(gè)數(shù)。

這個(gè)定理表明，如果滿足rank(L)=n -c 這個(gè)條件（n 是數(shù)據(jù)點(diǎn)的個(gè)數(shù)），即L 的前c 個(gè)最小特征值之和等于0，那么就可以直接通過相似矩陣S得到最終的c個(gè)簇。

根據(jù)文獻(xiàn)［11］，有以下等式：

其中：λi表示拉普拉斯矩陣L 的第i個(gè)特征值，L=D -S，D 表示度矩陣，它是一個(gè)對(duì)角陣，對(duì)角元素是矩陣S 的每列和，U是由拉普拉斯矩陣L 前c 個(gè)最小特征值對(duì)應(yīng)的特征向量組成的矩陣。

其中：γ1、γ2是權(quán)衡參數(shù)表示矩陣A與矩陣的Frobenius 內(nèi)積。為了避免出現(xiàn)Aj中有一個(gè)元素的值為1，而其余值為0的情況，添加F范數(shù)來平滑矩陣A中的元素。通過最小化目標(biāo)函數(shù)（7），最終可以得到相似矩陣A和矩陣U。

3.2 目標(biāo)函數(shù)求解

由于目標(biāo)函數(shù)（7）中有兩個(gè)變量，本文將該問題分為兩個(gè)子問題：

1）固定矩陣U，更新矩陣A，目標(biāo)函數(shù)變?yōu)椋?/p>

因?yàn)槊苛卸际仟?dú)立的，按列進(jìn)行更新，則式（8）的拉格朗日函數(shù)是：

其中：Mj是矩陣M 的列向量，矩陣M 的元素Mij=分別是矩陣U 的第i 列和第j 列向量；η和ρ是拉格朗日乘子。

根據(jù)Karush-Kuhn-Tucker（KKT）準(zhǔn)則［12］可以得到：

其中(?)+表示取非負(fù)實(shí)數(shù)。在矩陣A 中只保留每個(gè)數(shù)據(jù)點(diǎn)的最近的m 個(gè)值，同時(shí)根據(jù)得 到值為列向量Aj中值不為零的個(gè)數(shù)γ2=

2）固定矩陣A，更新矩陣U，目標(biāo)函數(shù)變?yōu)椋?/p>

問題（11）對(duì)于變量U 的最優(yōu)解是其對(duì)應(yīng)拉普拉斯矩陣L前c 個(gè)最小特征值對(duì)應(yīng)的特征向量組成的矩陣，兩個(gè)子問題交替迭代，最終可以得到矩陣A 和U 值。具體的算法流程總結(jié)在下列的算法2中。

算法2 基于共享近鄰的多視角譜聚類。

輸出 具有c個(gè)連通分支的相似矩陣A。初始化 全局相似矩陣矩陣U 由矩陣A 對(duì)應(yīng)的拉普拉斯矩陣L的前c個(gè)最小特征值對(duì)應(yīng)的特征向量組成

通過式（11）更新矩陣U

until 函數(shù)收斂

3.3 初始相似矩陣的優(yōu)化

為了使各個(gè)視角初始相似矩陣的簇結(jié)構(gòu)更加突出，本文在各個(gè)視角的初始相似矩陣S 的基礎(chǔ)上（S 在算法1 中給出），根據(jù)定理1的結(jié)論，對(duì)矩陣S進(jìn)行秩約束得到新的矩陣S*。目標(biāo)函數(shù)如下：

其中：α是正則化參數(shù)，矩陣U是由矩陣S對(duì)應(yīng)的拉普拉斯矩陣L前c個(gè)最小特征值對(duì)應(yīng)的特征向量組成的矩陣。該目標(biāo)函數(shù)有兩個(gè)變量S和U，同樣將這個(gè)目標(biāo)函數(shù)分為兩個(gè)子問題。

1）固定矩陣U，更新矩陣S，目標(biāo)函數(shù)為：

式（13）的拉格朗日函數(shù)是：

2）固定矩陣S，更新矩陣U，目標(biāo)函數(shù)變?yōu)椋?/p>

問題（16）對(duì)于變量U 的最優(yōu)解與式（11）相同，兩個(gè)子問題交替迭代，最終可以得到矩陣S 和U 的值。具體的算法流程總結(jié)在算法3中。

算法3 初始相似矩陣的優(yōu)化。

輸入 v個(gè)視角的相似矩陣S，聚類個(gè)數(shù)c；

輸出 更新后的v個(gè)視角的初始相似矩陣S*。

初始化 式（13）中，初始的矩陣U的值通過初始矩陣S對(duì)應(yīng)的拉普拉斯矩陣L前c個(gè)最小特征值對(duì)應(yīng)的特征向量得到。

3.4 收斂性分析

在3.2 節(jié)的目標(biāo)函數(shù)求解中，式（8）是凸函數(shù)，同時(shí)由式（11）的拉格朗日函數(shù)推導(dǎo)出的海森（Hessian）矩陣是半正定的（詳細(xì)證明參考文獻(xiàn)［13］），可以得到式（11）的目標(biāo)函數(shù)是凸函數(shù)，綜上可以得到式（7）收斂的結(jié)論。同理3.3 節(jié)中的兩個(gè)子函數(shù)（13）和（16）也是凸函數(shù)，所以式（12）收斂。具體的收斂實(shí)驗(yàn)在4.3.3節(jié)給出。

4 實(shí)驗(yàn)與分析

實(shí)驗(yàn)在兩個(gè)人工數(shù)據(jù)集和兩個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行。在人工數(shù)據(jù)集上，對(duì)提出的MV-SNN 算法進(jìn)行測(cè)試；在真實(shí)數(shù)據(jù)集上，將MV-SNN算法和下列聚類方法進(jìn)行對(duì)比。

1）SC-Best（Best result of Spectral Clustering）算法。該算法將標(biāo)準(zhǔn)的譜聚類算法在每個(gè)視角上分別執(zhí)行，選取其中結(jié)果最好的視角。

2）MVSC（large-scale Multi-View Spectral Clustering via bipartite graph）算法［14］。該算法通過局部流形整合機(jī)制來整合多個(gè)視角的數(shù)據(jù)，并通過二分圖來提升圖構(gòu)造的速度。該算法中用到的參數(shù)r依靠搜尋得到，本文按照作者的建議在對(duì)數(shù)空間搜尋lg 10r的最優(yōu)值，設(shè)定搜尋范圍為[0.1，2]，步長(zhǎng)為0.2。

3）CRSC 算法。該算法通過高斯核函數(shù)來構(gòu)造每個(gè)視角下的相似矩陣，使用一個(gè)協(xié)同正則化項(xiàng)來最小化不同視角和全局視角之間的差異性。

4）MVGL 算法。每個(gè)視角的相似矩陣由KNN 算法構(gòu)造，這些單視角下學(xué)習(xí)的圖被融合并通過拉普拉斯矩陣秩約束進(jìn)行優(yōu)化以獲得所要求的連通分量個(gè)數(shù)的全局相似矩陣。

5）GSF（Graph Structure Fusion for multi-view clustering）算法［15］。該算法將每個(gè)視角下通過KNN 算法獲得的相似矩陣通過哈達(dá)瑪積（Hadamard）的方式進(jìn)行融合，將融合后的全局圖通過拉普拉斯矩陣秩約束直接得到簇劃分。

6）MCGC（Multi-view Consensus Graph Clustering）［16］算法。該算法將每個(gè)視角通過KNN 算法獲得的相似矩陣經(jīng)過秩優(yōu)化處理后，求解出一個(gè)近似于各個(gè)視角對(duì)角塊結(jié)構(gòu)的全局相似矩陣。

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

4.1.1 人工數(shù)據(jù)集

1）三環(huán)數(shù)據(jù)集。通過在數(shù)據(jù)集上分別添加1%和2%的噪聲構(gòu)成兩個(gè)視角該數(shù)據(jù)集一共有3個(gè)簇，每個(gè)簇有100 個(gè)數(shù)據(jù)。因?yàn)樵肼曄鄬?duì)較大，使得不同簇中的數(shù)據(jù)點(diǎn)非常接近，因此會(huì)給聚類帶來一定的難度。

4.1.2 真實(shí)數(shù)據(jù)集

1）UCI digits。數(shù)據(jù)集中有10 個(gè)不同的手寫數(shù)字，從“0”“1”一直到“9”，每個(gè)數(shù)字有200 個(gè)樣本，屬于一類，一共有2 000 個(gè)樣本。該數(shù)據(jù)集一共有6 組特征，選取其中的3 組特征構(gòu)成3 個(gè)視角進(jìn)行實(shí)驗(yàn)：第一個(gè)視角是輪廓相關(guān)性特征，由216維表示；第二個(gè)視角是強(qiáng)度均值特征，由240維表示；第三個(gè)視角是Karhunen-Loeve系數(shù)特征，由64維表示。

2）NH。數(shù)據(jù)集有5 個(gè)不同的類別，共4 660 張面部圖像，一共有3 個(gè)視角：第一個(gè)是局部二值特征（Local Binary Patterns，LBP），由3 304維表示；第二個(gè)是Gabor特征，由6 750維表示；第三個(gè)是強(qiáng)度特征，由2 000 維表示。實(shí)驗(yàn)使用的數(shù)據(jù)集匯總在表1中。

表1 多視角數(shù)據(jù)集Tab.1 Multi-view data sets

4.2 聚類指標(biāo)

本文通過以下3個(gè)聚類指標(biāo)對(duì)聚類效果進(jìn)行衡量，3個(gè)聚類指標(biāo)的取值均在0～1，值越大表示聚類效果越好。

1）準(zhǔn)確度ACC（Accuracy）。

其中：T={T1，T2，…，Tc}表示原始的n 個(gè)數(shù)據(jù)包含真實(shí)的c 個(gè)類別，P={P1，P2，…，Pc}表 示聚類后n 個(gè)數(shù)據(jù)的c 個(gè)預(yù)測(cè)類別。Ti表示第i 個(gè)類別中包含的數(shù)據(jù)點(diǎn)表示集合Ti中包含的點(diǎn)的個(gè)數(shù)；Pi表示聚類后第i個(gè)類別中包含的數(shù)據(jù)點(diǎn)表示集合Pi中包含的點(diǎn)的個(gè)數(shù)。

2）純度（Purity）P。

3）歸一化互信息（Normalized Mutual Information，NMI）RNMI。

4.3 實(shí)驗(yàn)結(jié)果及分析

4.3.1 人工數(shù)據(jù)集實(shí)驗(yàn)

在人工數(shù)據(jù)集上對(duì)本文提出的MV-SNN 算法進(jìn)行驗(yàn)證，結(jié)果如圖3、4 所示。其中：三環(huán)數(shù)據(jù)集上不同簇的數(shù)據(jù)點(diǎn)分別用點(diǎn)、正方形和叉形描述；雙月數(shù)據(jù)集上不同簇的數(shù)據(jù)點(diǎn)分別用正方形和叉形描述；兩個(gè)數(shù)據(jù)集在算法中設(shè)置的參數(shù)均為k=10，閾值δ=5。

圖3（a）和（b）中的數(shù)據(jù)點(diǎn)之間的連接邊值均由3.3 節(jié)的相似矩陣得到，可以看到圖中的標(biāo)注點(diǎn)A處，同簇的數(shù)據(jù)點(diǎn)之間并沒有連接邊，而標(biāo)注點(diǎn)B處，不同簇的數(shù)據(jù)點(diǎn)間出現(xiàn)了連接邊；而由3.1節(jié)學(xué)習(xí)得到的全局相似矩陣?yán)L制的圖3（c）中，同簇之間的數(shù)據(jù)點(diǎn)均有邊連接，構(gòu)成一個(gè)連通圖，不同簇之間的數(shù)據(jù)點(diǎn)之間沒有連接邊，說明三環(huán)數(shù)據(jù)集已經(jīng)被正確劃分。

圖3 三環(huán)數(shù)據(jù)集聚類結(jié)果Fig.3 Three-circle data set clustering results

圖4 雙月數(shù)據(jù)集聚類結(jié)果Fig.4 Two-month data set clustering results

圖4（a）和（b）中的標(biāo)注點(diǎn)A處，同簇的數(shù)據(jù)點(diǎn)之間并沒有連接邊，而標(biāo)注點(diǎn)B 處，不同簇的數(shù)據(jù)點(diǎn)間出現(xiàn)了連接邊，說明數(shù)據(jù)點(diǎn)被錯(cuò)誤劃分；而圖4（c）中，同簇之間的數(shù)據(jù)點(diǎn)均有邊連接，不同簇之間的數(shù)據(jù)點(diǎn)之間沒有連接邊，說明雙月數(shù)據(jù)集已經(jīng)被正確劃分。

從圖3（a）、（b）和圖4（a）、（b）中可見，單視角譜聚類會(huì)出現(xiàn)數(shù)據(jù)點(diǎn)之間連接錯(cuò)誤的情況，而圖（c）將兩個(gè)視角之間的相似信息進(jìn)行融合，加強(qiáng)同簇?cái)?shù)據(jù)之間的相似性，從而不會(huì)出現(xiàn)單視角下錯(cuò)誤的聚類情況。

4.3.2 真實(shí)數(shù)據(jù)集實(shí)驗(yàn)

下面6 個(gè)算法均以譜聚類算法為基礎(chǔ)，SC-Best、MVSC 和CRSC 算法前期各不相同，但最后都需要k-means 算法得到聚類結(jié)果；MCGC、MVGL、GSF 和MV-SNN 算法多視角數(shù)據(jù)融合的方式各不相同，但是最后都是通過拉普拉斯矩陣秩約束理論得到聚類結(jié)果。聚類結(jié)果如表2 所示，最好的結(jié)果均加粗標(biāo)注。其中：UCI digits 數(shù)據(jù)集MV-SNN 算法中參數(shù)k=18，閾值δ=9；NH數(shù)據(jù)集MV-SNN算法中參數(shù)k=16，閾值δ=8。

表2 UCI digits和NH數(shù)據(jù)集聚類結(jié)果Tab.2 Clustering results of UCI digits and NH datasets

表2中，對(duì)于UCI digits數(shù)據(jù)集，多視角譜聚類算法的結(jié)果都優(yōu)于單視角聚類結(jié)果，說明了多視角聚類的優(yōu)越性。當(dāng)簇?cái)?shù)較多時(shí)，MV-SNN 算法的ACC 結(jié)果僅次于GSF 算法但是優(yōu)于MCGC 算法，GSF 算法采用哈達(dá)瑪積融合多視角數(shù)據(jù)，在一定程度上可以摒棄多余信息的干擾；本文采用視角數(shù)據(jù)相加的方式，對(duì)于多視角信息之間的補(bǔ)充有很好的作用，但是也會(huì)增加多視角聚類時(shí)無用信息的干擾；而MCGC 算法從相似矩陣的圖形結(jié)構(gòu)出發(fā)，在一定程度上可以使得相似矩陣近似于對(duì)角塊結(jié)構(gòu)，但是當(dāng)數(shù)據(jù)集簇?cái)?shù)較多時(shí)，對(duì)角塊結(jié)構(gòu)構(gòu)造的準(zhǔn)確率會(huì)有所下降。同時(shí)本文采用共享近鄰計(jì)算數(shù)據(jù)點(diǎn)之間的相似度，對(duì)于不是很稀疏的數(shù)據(jù)集，參數(shù)k的取值控制在20以內(nèi)便能探測(cè)到數(shù)據(jù)點(diǎn)之間的相似信息，因此聚類時(shí)間效率會(huì)明顯優(yōu)于以上幾個(gè)算法。

對(duì)于NH 數(shù)據(jù)集的高維復(fù)雜性，以上所有算法在3個(gè)指標(biāo)上的結(jié)果均遜于UCI digits 數(shù)據(jù)集的結(jié)果，但是當(dāng)簇?cái)?shù)較少時(shí)，由于MV-SNN 算法采用了新的相似矩陣構(gòu)造方法，該方法對(duì)高維數(shù)據(jù)有很好的適用性，以及采用新的簇劃分方法，從而聚類性能優(yōu)于其他的多視角譜聚類算法，且在聚類時(shí)間上幾乎減少50%。

4.3.3 收斂性驗(yàn)證

圖5 UCI digits和NH數(shù)據(jù)集的收斂曲線Fig.5 Convergence curves of UCI digits and NH datasets

5 結(jié)語

基于共享近鄰的自適應(yīng)高斯核函數(shù)在譜聚類相似矩陣構(gòu)造環(huán)節(jié)，用歐氏距離和局部密度兩個(gè)指標(biāo)來綜合衡量數(shù)據(jù)點(diǎn)之間的相似性，可以應(yīng)對(duì)不同密度的數(shù)據(jù)簇，得到更合理的相似性分布；同時(shí)多視角聚類中采用視角信息相加的方式融合多個(gè)視角的信息，比單視角聚類結(jié)果更好；最后MV-SNN 算法采用拉普拉斯矩陣秩約束的方法，直接通過相似矩陣得到最終的聚類結(jié)果，而其他譜聚類算法后期仍要使用k-means 算法，又會(huì)帶來初始中心點(diǎn)不確定的問題。實(shí)驗(yàn)證明，MV-SNN算法相較于其他多視角譜聚類算法，聚類效果有很大提升。在未來工作中，還要對(duì)多視角數(shù)據(jù)的融合方式進(jìn)一步研究，由于各個(gè)視角所攜帶信息的不同，直接采用等量權(quán)重進(jìn)行融合不太合理，因此考慮采用信息熵來衡量各個(gè)視角數(shù)據(jù)所攜帶的信息，進(jìn)一步優(yōu)化權(quán)重分布。