關鍵節點選擇的快速圖聚類算法

尤坊州，白 亮

1.山西大學 計算機與信息技術學院，太原 030006

2.山西大學 計算機智能與中文信息處理教育部重點實驗室，太原 030006

聚類[1-3]是依據特定標準將一個數據集分成不同的類或簇，使得類內相似性盡可能高，類間相似性盡可能低。聚類技術在各行各業中得到廣泛應用，各種聚類方法也被不斷提出和改進，不同的方法適合于不同類型的數據，例如基于連通性的聚類算法[4]、基于中心的聚類算法[5]、基于密度的聚類算法[6]等。其中，譜聚類作為一種極具競爭力的圖聚類算法，由于其能夠有效地識別數據的復雜類結構，已成功應用在不同的領域，如搜索引擎[7]、推薦系統[8]、圖像分割[9]、語音識別[10]等。但是譜聚類的特征求解需要極高的時間復雜度，因而它并不適合應用于大規模數據集。近年來，隨著信息化時代的發展，數據規模呈幾何級數高速增長，如何將譜聚類方法應用于大規模數據集已成為了一個重要的研究內容。

為了提高譜聚類在大規模數據集上的聚類效果，許多加速方法被發展。它們主要從以下兩方面加速聚類算法：（1）降低特征分解的時間復雜度。2001 年Dhillon[11]證明用奇異值分解（singular value decomposition，SVD）特定矩陣代替譜聚類最小化Ncut的目標函數的方法可行。2004 年Fowlkes 等人[12]提出Nystr?m 方法，該方法從給定的數據成對相似性矩陣中計算出一個樣例成對矩陣的特征向量，并利用它估計原始矩陣特征向量的近似值，以提高求解特征值與特征向量的速度。2017 年Nie 等人[13]提出用于學習具有完全k（其中k為簇數）個連通分量的二部圖的方法，在模型中學習的新二部圖近似原始圖，但保留了顯式的簇結構，從中可以立即獲得聚類結果，而無需進行后續處理。（2）選取關鍵節點實現數據壓縮。2008 年Shinnou 和Sasaki[14]將K-means 聚類應用于大規模的數據集，刪除那些靠近聚類中心（關鍵節點）的數據點（設置距離閾值），對剩余的數據點以及聚類中心（關鍵節點）進行譜聚類，那些被刪除的數據點跟隨自己相對應的聚類中心（關鍵節點）被分配到相應的集群中。2009 年Yan 等人[15]提出基于Kmeans 近似的譜聚類方法，首先對數據進行K-means聚類，再對得到的聚類中心（關鍵節點）進行譜聚類，其他數據點跟隨自己相對應的聚類中心（關鍵節點）被分配到相應的集群中。2015 年Chen 和Cai[16]對隨機選擇的關鍵節點與原有數據進行重新編碼，對編碼之后的新數據進行奇異值分解（SVD）。2013 年Liu 等人[17]在Chen 和Cai[16]研究的基礎上進一步提出一種重新編碼的方法，使得提取出的關鍵節點更具有代表性。2020 年Huang 等人[18]提出用隨機選擇與K-means 選擇相結合的方式選取關鍵節點。2019 年Lee 等人[19]提出為每一個點用圖卷積定義自注意力分數，自注意力分數越高的節點越具有代表性。

雖然在大規模數據集上的譜聚類已經取得了一定的研究成果，但還是存在兩個問題：（1）所選取的關鍵節點大多通過隨機選擇或K-means 聚類得到，無法保證被選出的關鍵節點可以很好地代表原有數據，從而影響之后的聚類結果；（2）在用不同方法進行特征分解的近似時，雖然降低了計算的時間復雜度，但受初始選點的影響，聚類結果穩定性差，算法魯棒性不高。

基于此，本文對大規模數據集下的譜聚類算法進行改進，創新之處如下：

（1）從關鍵節點的局部代表性和關鍵節點之間的差異性兩方面考慮，給出一種新的快速關鍵節點選擇方法。

（2）通過對多次近似特征求解結果進行聚類集成，提高聚類結果的魯棒性。

1 譜聚類算法的簡介

2000 年，Shi 和Malik[9]首次提出基于Normalized cut 準則的譜聚類算法。與傳統的聚類方法相比，譜聚類收斂于全局最優解且聚類效果好。本文用G=(V,E)表示圖，其中V表示頂點集，E表示邊集，給定包含n個節點的數據集，xi對應頂點集V中的每個數據點。譜聚類構造矩陣W={wi,j}i,j=1,2,…,n用于揭示數據點之間的相似性關系，對矩陣W求行和（或列和）得到度矩陣D∈Rn×n，由如下定義，得到Laplacian 矩陣：

其中，通過高斯核計算W：

其中，σ是核參數，一般情況下被設置為數據的方差。譜聚類的實質是將聚類問題轉換為圖分割問題，其目的為最小化如下目標函數：

其中，A1,A2,…,Ak為被分割的多個不相交子集。但是人們無法直接對上述目標函數求最優解，因此利用Laplacian 矩陣，將目標函數轉換為：

其中，H=[h1,h2,…,hk]為指示向量。譜聚類求解Laplacian 矩陣的前k個特征向量，最終通過K-means算法得到聚類結果。由于譜聚類中需要求解特征向量，其時間復雜度高達O(n3)，并不適合應用在大規模數據集上做聚類運算。

2 大規模數據的快速圖聚類算法

為解決大規模數據的聚類問題，本文提出基于關鍵節點選擇的快速圖聚類算法。算法的總框架包含以下三個主要步驟：（1）選擇關鍵節點形成關鍵節點與原始數據之間的相似性矩陣W；（2）構建二分圖，通過奇異值分解獲得數據的近似特征向量；（3）對多次近似特征向量進行集成。接下來，本文將分別對它們進行詳細介紹。

2.1 關鍵節點的選擇

對于大規模數據，在進行譜聚類時由于其數據量大，導致在進行特征值與特征向量計算時時間復雜度較高。因此，本文提出一種關鍵節點的選擇方法。通過此方法，本文對數據進行篩選，從中選出最具代表性的節點，構成新的鄰接矩陣，再對其進行特征值與特征向量的計算，從而降低時間復雜度。接下來，首先給出關鍵節點的評價指標的相關定義。

定義1關鍵節點代表性的評價指標LD定義如下：

節點的LD代表了它在其所屬類中與比自己度小的節點的相似性總和。某點的LD值越高，則表明以它為中心的局部密度越稠密，其所能夠代表的節點越多。LD定義了關鍵節點的局部重要性，但若只考慮關鍵節點的局部重要性有可能導致被選出的節點均來自于同一類中。為了使得被選取出的節點可以代表不同的類，除了要考慮關鍵節點的局部重要性外，還應考慮關鍵節點之間的差異性。為解決差異性問題，本文首先將數據以K-means 聚類方法初始劃分為d類，然后在每一類中通過比較LD的值選出一個關鍵節點，共計d個關鍵節點。為解釋上述計算過程，本文以圖1 為例進行闡述。如圖1 所示，給定的數據關系圖中包含19 個節點，通過K-means 聚類方法被劃分為3 個集群。以第一個集群為例解釋LD計算方法，集群1 包含6 個點（V1～V6）。如圖2 所示，計算每個點的LD值，并從大到小進行排序。通過此方法，在其他集群中根據LD的值對節點進行排序，依次選出每一個集群中的關鍵節點、次關鍵節點等，如圖3 所示。

Fig.1 Corresponding initial partition obtained by K-means clustering method圖1 由K-means聚類方法得到相應初始劃分

Fig.2 Sorting nodes in cluster 1 according to LD value圖2 根據LD 值在集群1 中對節點進行排序

Fig.3 Key nodes selected in turn in each cluster圖3 在每個集群中依次選出的關鍵節點

為增加聚類效果的穩定性以及算法的魯棒性，需要對由奇異值分解而來的多個近似特征向量進行集成，因此在選擇關鍵節點后，需要形成多個相似性矩陣。將從每一類中選出的LD值最高的關鍵節點形成相似性矩陣W1∈Rd×n（在本例中，選擇V5、V10、V14構成相似性矩陣W1∈R3×19），再從每一類中選出LD值次高的關鍵節點，形成相似性矩陣W2∈Rd×n（在本例中，選擇V6、V9、V16構成相似性矩陣W2∈R3×19）。以此類推。

2.2 二部圖劃分

由關鍵節點的選擇，得到可以揭示d個關鍵節點與n個原數據之間關系的相似性矩陣Wi∈Rd×n。進而形成關鍵節點與原有數據的二部圖[20]B=(X,Y,E)，如圖4 所示，其中X代表原始節點集，Y代表關鍵節點集，E為X與Y之間的邊集。對于給定的二部圖B，文獻[17]中提出奇異值分解SVD 方法：根據譜圖理論，對二部圖歸一化分割，可以同時劃分原數據與關鍵節點。用奇異值分解代替特征分解以減小時間復雜度。為了劃分二部圖，可以將優化任務形式化為廣義特征值問題。將記為

Fig.4 Illustration of bipartite graph圖4 二部圖示意

其中，Di1和Di2分別為Wi的列和與行和。由歸一化矩陣的奇異值分解SVD 得到：

其中，Σ=Diag(σ1,σ2,…,σd)，Ni∈Rd×d，Mi∈Rn×d分別為左右奇異值向量。易證得，Mi的列向量為的特征向量，Ni的列向量為的特征向量。得到如下：

由不同的矩陣Wi通過奇異值分解依次獲得不同的矩陣Mi。

2.3 多近似特征矩陣集成

由于矩陣W的形成具有一定的不確定性，會受到初始K-means 聚類劃分的影響，且形成的不同矩陣W之間具有差異性，滿足聚類集成對于基聚類的要求。由矩陣W通過奇異值分解操作得到矩陣U，對矩陣U采用聚類集成操作以解決聚類結果不穩定的問題。

定義2對奇異值分解后的t個矩陣U1,U2,…,Ut進行融合，記作：

基于U′，本文將利用K-means 聚類算法完成集成任務，集成的優化目標如下：

其中，P為最終的n×k劃分矩陣，Z為K-means 的k×kt類中心矩陣?？偟募蛇^程如圖5 所示。

Fig.5 Example of ensemble process圖5 集成流程示例

2.4 快速圖聚類算法總流程

融合上述三個步驟，一個基于關鍵節點選擇的快速圖聚類算法（fast graph clustering algorithm based on key node selection）被提出，簡稱為KNS 算法，其總流程描述如下。

算法1KNS 算法描述

輸入：n個數據點，首次聚類簇數d，最終聚類簇數k，集成組數t。

輸出：k簇聚類結果。

在時間復雜度方面,由于數據集規模較大，近似K-means 算法時間復雜度為O(n)，計算相似性矩陣與排序的時間復雜度為O(2n2)，得到的時間復雜度為O(nd)，得到的時間復雜度為O(d3)，得到M1的時間復雜度為O(ndk)。由于n?k且n?d，執行t次后本文算法總時間復雜度近似為O(t(n+2n2))。

3 實驗分析

3.1 實驗數據

為驗證本文算法的有效性，從https://cs.nyu.edu/～roweis/data.html 中選取了5 個Benchmark 數據集，數據集的簡要描述如下：

（1）Digits：手寫數字數據集，包含5 620 個數據點、64 個特征和10 類，每個數據是一個數字的8×8 圖像的像素值。

（2）Pen：手寫數字數據集，包含10 992 個數據點、16 個特征和10 類，分別來自44 個作者的250 個樣本，使用每個數字的抽樣協調信息。

（3）Statlog：地球資源衛星多光譜數據集，包含6 435 個數據點、36 個特征和6 類，其數據為3×3 的街區在衛星圖像上的像素值。

（4）MNIST：包含10 000 個數據點、256 個特征和10 類，來自Yann LeCun 頁面的手寫數字，數字進行標準化并集中在固定大小的圖像中，每個圖像表示為一個784 維的向量。

（5）Letters：英文字母表中26 個大寫字母的數據集，包含20 000 個數據點、16 個特征和26 類。

3.2 評價指標

本文使用標準互信息（normalized mutual information，NMI）[21]和調整蘭德系數（adjusted Rand index，ARI）[22]來評價最終聚類質量，可以比較客觀地評價出劃分與標準劃分之間相比的準確度，并比較不同算法完成聚類的用時。

3.3 實驗結果分析

為了測試新算法的有效性，使用該算法與經典譜聚類算法SC（original spectral clustering）[9]和若干個改進譜聚類算法進行了比較分析。改進算法包括CSC 算法（construction of committee based spectral clustering）[14]、Nystr?m 算法（Nystr?m spectral clustering）[12]、LSC 算法（landmark based spectral clustering）[16]、SNC算法（scalable normalized cut）[23]、FastESC 算法（fast explicit spectral clustering）[24]、EulerSC 算法（Euler spectral clustering）[25]。在比較過程中，本文設置聚類簇數k為數據集真實的簇個數，選擇高斯函數為核函數計算圖的相似性矩陣，其核參數被設置為0.095，首次聚類簇數d為最終聚類簇數k+1。為了使得比較在同一環境上，在每一個算法中使用相同的核參數。對于KNS 算法，設置t的值為3。

同時為對KNS 算法中多近似特征矩陣集成的效果進行評價，設置對比實驗，比較無集成操作的KNS算法（fast graph clustering algorithm based on key node selection without ensemble，NE-KNS，即在KNS 算法中設置t的值為1）與其他算法在5 個數據集下的聚類結果。

使用上述9 種算法得到聚類結果后，應用NMI和ARI 這兩種評價指標對上述聚類結果進行評價，實驗結果如表1、表2 所示，并比較各算法用時，實驗結果如表3 所示。其中由于NE-KNS 算法為KNS 算法的一部分，用時均少于KNS 算法，但其聚類效果并不為最佳，故不具有比較意義，沒有列出。

表1 和表2 展示了不同算法在5 個Benchmark 數據集上的聚類效果，結合表3 所展示的不同算法的聚類用時發現，在多數數據集上，比如Digits、Statlog、MNIST 數據集，本文算法聚類效果更好，更接近于真實劃分。多近似特征矩陣集成的應用，使得聚類結果更加穩定，聚類效果更好。并且在全部數據集下，本文的聚類用時對比其他比較算法有大幅度的縮短，尤其是在Pen、Letters 數據集下，耗時僅為最長用時的1.35%，這就證明了本文算法在提高聚類效果的同時極大縮短了聚類用時，使得大規模數據集下的聚類更具有可行性。雖然在一部分情況下聚類精度并未達到最好，但也證明了新算法具有的優勢。綜上所述，本文提出的基于關鍵節點選擇的快速圖聚類算法較其他算法有更好的聚類結果，用時大幅度縮短，因此本文算法對于大規模數據集來說有更好的適用性。

Table 1 Comparison of NMI of different algorithms表1 不同算法的NMI值比較

Table 2 Comparison of ARI of different algorithms表2 不同算法的ARI值比較

Table 3 Comparison of clustering time of different algorithms表3 不同算法的聚類用時比較 s

4 結束語

本文針對譜聚類算法的高計算成本問題，提出一種新的快速圖聚類算法。該算法通過選出具有代表性的關鍵節點代表原數據，獲得數據的近似特征向量，并通過聚類集成實現多近似結果的融合，提高了圖聚類的魯棒性。在不同的數據集上的實驗結果表明，該算法在NMI 和ARI 兩個評價指標上的效果都有提高，且用時短，證實了該算法的有效性，提高了譜聚類算法在大數據集上的規模適應性。

雖然本文算法在降低譜聚類的時間復雜度和縮短聚類用時方面取得一定進步，但是在關鍵節點的選擇方面仍存在部分所選關鍵節點代表性差的問題。在今后的工作中，會將工作重點放在如何更準確地選擇出關鍵節點方面，希望結合神經網絡等方法找出關鍵節點，將大規模數據集通過分步依次壓縮為具有代表性的小數據集，進一步實現準確的數據壓縮。