關(guān)鍵節(jié)點選擇的快速圖聚類算法

尤坊州，白 亮

1.山西大學(xué) 計算機與信息技術(shù)學(xué)院，太原 030006

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

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

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

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

基于此，本文對大規(guī)模數(shù)據(jù)集下的譜聚類算法進(jìn)行改進(jìn)，創(chuàng)新之處如下：

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

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

1 譜聚類算法的簡介

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

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

其中，σ是核參數(shù)，一般情況下被設(shè)置為數(shù)據(jù)的方差。譜聚類的實質(zhì)是將聚類問題轉(zhuǎn)換為圖分割問題，其目的為最小化如下目標(biāo)函數(shù)：

其中，A1,A2,…,Ak為被分割的多個不相交子集。但是人們無法直接對上述目標(biāo)函數(shù)求最優(yōu)解，因此利用Laplacian 矩陣，將目標(biāo)函數(shù)轉(zhuǎn)換為：

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

2 大規(guī)模數(shù)據(jù)的快速圖聚類算法

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

2.1 關(guān)鍵節(jié)點的選擇

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

定義1關(guān)鍵節(jié)點代表性的評價指標(biāo)LD定義如下：

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

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

Fig.2 Sorting nodes in cluster 1 according to LD value圖2 根據(jù)LD 值在集群1 中對節(jié)點進(jìn)行排序

Fig.3 Key nodes selected in turn in each cluster圖3 在每個集群中依次選出的關(guān)鍵節(jié)點

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

2.2 二部圖劃分

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

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采用聚類集成操作以解決聚類結(jié)果不穩(wěn)定的問題。

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

基于U′，本文將利用K-means 聚類算法完成集成任務(wù)，集成的優(yōu)化目標(biāo)如下：

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

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

2.4 快速圖聚類算法總流程

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

算法1KNS 算法描述

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

輸出：k簇聚類結(jié)果。

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

3 實驗分析

3.1 實驗數(shù)據(jù)

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

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

（2）Pen：手寫數(shù)字?jǐn)?shù)據(jù)集，包含10 992 個數(shù)據(jù)點、16 個特征和10 類，分別來自44 個作者的250 個樣本，使用每個數(shù)字的抽樣協(xié)調(diào)信息。

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

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

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

3.2 評價指標(biāo)

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

3.3 實驗結(jié)果分析

為了測試新算法的有效性，使用該算法與經(jīng)典譜聚類算法SC（original spectral clustering）[9]和若干個改進(jìn)譜聚類算法進(jìn)行了比較分析。改進(jìn)算法包括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]。在比較過程中，本文設(shè)置聚類簇數(shù)k為數(shù)據(jù)集真實的簇個數(shù)，選擇高斯函數(shù)為核函數(shù)計算圖的相似性矩陣，其核參數(shù)被設(shè)置為0.095，首次聚類簇數(shù)d為最終聚類簇數(shù)k+1。為了使得比較在同一環(huán)境上，在每一個算法中使用相同的核參數(shù)。對于KNS 算法，設(shè)置t的值為3。

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

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

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

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 結(jié)束語

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

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