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

宋 艷，殷 俊

（上海海事大學信息工程學院，上海 201306）

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

0 引言

聚類分析［1］就是按照某個特定標準將一個數據集分割成不同的簇，使同一簇的數據盡可能地聚集到一起。傳統的k-means 聚類算法［2］對樣本空間有特定的要求，當樣本空間不為凸時，算法就會陷入局部最優。與k-means 算法相比，譜聚類算法具有能在任意形狀的樣本空間上聚類且收斂于全局最優的優點。

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

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

1 相關工作

譜聚類的基本思想是利用從數據中得到的更低維的特征矩陣實現聚類，主要依靠兩個部分完成聚類工作：1）圖的構造；2）對構造好的圖誘導出拉普拉斯矩陣并作特征分解，將數據嵌入到特征向量空間，最后再次使用k-means 算法實現聚類。在多視角譜聚類算法中，Kumar等［9］提出了協同正則多視角譜聚類（Co-regularized Multi-view Spectral Clustering，CRSC）算法，Zhan 等［10］提出了圖學習的多視角譜聚類（Graph Learning for Multi-View clustering，MVGL）算法。

1.1 協同正則多視角譜聚類算法

Kumar 等［9］將用于有監督訓練的協同思想應用到無監督譜聚類算法中，算法在多視角數據聚類結構一致性假設的前提下，同時考慮每個視角譜聚類算法的優化情況和不同視角之間的差異情況，提出成對優化模式和基于中心的優化模式。后者對所有視角的數據優化出一個中心特征嵌入矩陣U*來平衡其他視角的數據，目標函數如下：

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

1.2 圖學習的多視角譜聚類算法

首先將v個視角下通過KNN算法得到的相似矩陣S(i)乘以對應權重Q(i)相加整合；然后構造出一個全局相似矩陣A；最后通過最小化誤差函數來最小化兩者之間的差異，從而獲得全局相似矩陣A的值。同時該優化框架結合拉普拉斯矩陣秩約束方法，根據全局相似矩陣得到聚類結果，目標函數如下：

其中：Aj表示矩陣A的第j列向量，列和為1；γ為權衡參數，用來控制后一項的比重；矩陣L為矩陣A所對應的拉普拉斯矩陣。

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

2 相似矩陣構造方法

譜聚類算法中相似矩陣的構造方法最經典的應該屬于高斯核函數和KNN算法。

高斯核函數：

其中：Xi和Xj表示兩個數據點；σ 是一個需要人工指定的參數。該構造方法中，兩點的相似度只與兩點間的歐氏距離有關，但是只以距離作為衡量相似度的標準，對應不同密度的簇就無法處理。

KNN 算法是一種高斯核函數的局部連接構造方法，它并不能解決存在密度差異的兩個數據點之間的相似情況，而相似值應同時滿足空間上相近的兩個數據點之間具有較高的相似度且位于同一個簇的數據點具有較高的相似度兩個要求。本文利用共享近鄰的思想來構造相似矩陣，該方法根據數據集流形結構的特點來增強同簇數據點之間的相似性。

2.1 基于共享近鄰的構造方法

數據點Xi和Xj之間的共享最近鄰（Shared Nearest Neighbor，SNN）：

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

圖1 共享近鄰個數示意圖Fig.1 Schematic diagram of number of shared neighbors

結合共享近鄰的思想，給出任意兩點Xi和Xj之間的相似度度量Sij，基于共享近鄰的自適應高斯核函數：

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

1）假設當兩點Xi和Xj距離較近時，則值較小，于是Sij值變大，使得相近的數據點具有較高的相似度。

2）假設當數據點Xi和Xj位于同一簇中，數據點Xi和Xk位于不同簇中，且時，統計它們之間共享近鄰的個數，有SNN(Xi，Xj)＞SNN(Xi，Xk)（同一密度簇中的共享近鄰個數更多），進而得到相似度Sij＞Sik，使得位于同一簇上的兩點具有更高的相似度。

因為譜聚類算法適合處理比較稀疏的數據，為了得到更精確的結果，本文進一步對相似矩陣進行稀疏化處理，只有兩個數據點之間的共享近鄰數大于閾值δ，相似度Sij值才不為0，具體的處理過程總結在下列的算法1中。

算法1 相似矩陣的構造方法。

輸出 相似矩陣S。

if 數據點Xi在點Xj的k 近鄰空間中且數據點Xj在點Xi的k 近鄰空間中

if SNN(Xi，Xj)＞閾值δ

在該算法中，主要有兩個參數：k 和δ。k 值過大則會導致最終只有一個簇，k值過小則會導致每個數據點都自成一簇；δ值根據k值而定，一般情況下，δ=k/2。

2.2 相似矩陣散點圖實驗

為了驗證算法1 的有效性，將KNN 算法和算法1 在人工數據集（三環數據集，具體介紹見4.1 節）上構造相似矩陣（兩者的參數k 均取10）并通過散點圖表示，如圖2 所示。所測試的數據集為其中第1 個數據點到第100個數據點屬于第1 個簇，第101 個數據點到第200 個數據點屬于第2個簇，第201個數據點到第300個數據點屬于第3個簇，一共有3 個簇；因此理論上該數據集得到的相似矩陣應該是標準的對角塊結構。

圖2中的散點表示兩個數據點相似：從圖2（a）可以看出，由算法1 得到的相似矩陣圖中的點基本都集中在對角塊上，說明達到了簇內數據點之間高度相似的要求；在圖2（b）由KNN算法得到的散點圖中，很多點散落在對角結構之外，說明不同簇的很多數據點之間依然相似，并沒有達到相似矩陣的構造要求。

圖2 三環數據集相似矩陣的散點圖Fig.2 Scatter plots of similarity matrix of three-circle data set

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

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

3.1 目標函數

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

其中：S(i)*表示優化過的第i 個視角的相似矩陣（優化過程在3.3節給出），因為相似矩陣，它滿足下列定理1。

定理1相似矩陣S的連通分支數c等于其對應的拉普拉斯矩陣的特征值為0的個數。

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

根據文獻［11］，有以下等式：

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

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

3.2 目標函數求解

由于目標函數（7）中有兩個變量，本文將該問題分為兩個子問題：

1）固定矩陣U，更新矩陣A，目標函數變為：

因為每列都是獨立的，按列進行更新，則式（8）的拉格朗日函數是：

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

根據Karush-Kuhn-Tucker（KKT）準則［12］可以得到：

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

2）固定矩陣A，更新矩陣U，目標函數變為：

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

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

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

通過式（11）更新矩陣U

until 函數收斂

3.3 初始相似矩陣的優化

為了使各個視角初始相似矩陣的簇結構更加突出，本文在各個視角的初始相似矩陣S 的基礎上（S 在算法1 中給出），根據定理1的結論，對矩陣S進行秩約束得到新的矩陣S*。目標函數如下：

其中：α是正則化參數，矩陣U是由矩陣S對應的拉普拉斯矩陣L前c個最小特征值對應的特征向量組成的矩陣。該目標函數有兩個變量S和U，同樣將這個目標函數分為兩個子問題。

1）固定矩陣U，更新矩陣S，目標函數為：

式（13）的拉格朗日函數是：

2）固定矩陣S，更新矩陣U，目標函數變為：

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

算法3 初始相似矩陣的優化。

輸入 v個視角的相似矩陣S，聚類個數c；

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

初始化 式（13）中，初始的矩陣U的值通過初始矩陣S對應的拉普拉斯矩陣L前c個最小特征值對應的特征向量得到。

3.4 收斂性分析

在3.2 節的目標函數求解中，式（8）是凸函數，同時由式（11）的拉格朗日函數推導出的海森（Hessian）矩陣是半正定的（詳細證明參考文獻［13］），可以得到式（11）的目標函數是凸函數，綜上可以得到式（7）收斂的結論。同理3.3 節中的兩個子函數（13）和（16）也是凸函數，所以式（12）收斂。具體的收斂實驗在4.3.3節給出。

4 實驗與分析

實驗在兩個人工數據集和兩個真實數據集上進行。在人工數據集上，對提出的MV-SNN 算法進行測試；在真實數據集上，將MV-SNN算法和下列聚類方法進行對比。

1）SC-Best（Best result of Spectral Clustering）算法。該算法將標準的譜聚類算法在每個視角上分別執行，選取其中結果最好的視角。

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

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

4）MVGL 算法。每個視角的相似矩陣由KNN 算法構造，這些單視角下學習的圖被融合并通過拉普拉斯矩陣秩約束進行優化以獲得所要求的連通分量個數的全局相似矩陣。

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

6）MCGC（Multi-view Consensus Graph Clustering）［16］算法。該算法將每個視角通過KNN 算法獲得的相似矩陣經過秩優化處理后，求解出一個近似于各個視角對角塊結構的全局相似矩陣。

4.1 數據集

4.1.1 人工數據集

1）三環數據集。通過在數據集上分別添加1%和2%的噪聲構成兩個視角該數據集一共有3個簇，每個簇有100 個數據。因為噪聲相對較大，使得不同簇中的數據點非常接近，因此會給聚類帶來一定的難度。

4.1.2 真實數據集

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

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

表1 多視角數據集Tab.1 Multi-view data sets

4.2 聚類指標

本文通過以下3個聚類指標對聚類效果進行衡量，3個聚類指標的取值均在0～1，值越大表示聚類效果越好。

1）準確度ACC（Accuracy）。

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

2）純度（Purity）P。

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

4.3 實驗結果及分析

4.3.1 人工數據集實驗

在人工數據集上對本文提出的MV-SNN 算法進行驗證，結果如圖3、4 所示。其中：三環數據集上不同簇的數據點分別用點、正方形和叉形描述；雙月數據集上不同簇的數據點分別用正方形和叉形描述；兩個數據集在算法中設置的參數均為k=10，閾值δ=5。

圖3（a）和（b）中的數據點之間的連接邊值均由3.3 節的相似矩陣得到，可以看到圖中的標注點A處，同簇的數據點之間并沒有連接邊，而標注點B處，不同簇的數據點間出現了連接邊；而由3.1節學習得到的全局相似矩陣繪制的圖3（c）中，同簇之間的數據點均有邊連接，構成一個連通圖，不同簇之間的數據點之間沒有連接邊，說明三環數據集已經被正確劃分。

圖3 三環數據集聚類結果Fig.3 Three-circle data set clustering results

圖4 雙月數據集聚類結果Fig.4 Two-month data set clustering results

圖4（a）和（b）中的標注點A處，同簇的數據點之間并沒有連接邊，而標注點B 處，不同簇的數據點間出現了連接邊，說明數據點被錯誤劃分；而圖4（c）中，同簇之間的數據點均有邊連接，不同簇之間的數據點之間沒有連接邊，說明雙月數據集已經被正確劃分。

從圖3（a）、（b）和圖4（a）、（b）中可見，單視角譜聚類會出現數據點之間連接錯誤的情況，而圖（c）將兩個視角之間的相似信息進行融合，加強同簇數據之間的相似性，從而不會出現單視角下錯誤的聚類情況。

4.3.2 真實數據集實驗

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

表2 UCI digits和NH數據集聚類結果Tab.2 Clustering results of UCI digits and NH datasets

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

對于NH 數據集的高維復雜性，以上所有算法在3個指標上的結果均遜于UCI digits 數據集的結果，但是當簇數較少時，由于MV-SNN 算法采用了新的相似矩陣構造方法，該方法對高維數據有很好的適用性，以及采用新的簇劃分方法，從而聚類性能優于其他的多視角譜聚類算法，且在聚類時間上幾乎減少50%。

4.3.3 收斂性驗證

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

5 結語

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