抽樣改進加權核大數據譜聚類算法

申 銳，吳 睿

（1.山西交通職業技術學院，山西 晉中 030600；2.西安交通大學軟件學院，陜西 西安 710061）

1 引言

隨著科技與互聯網的發展以及信息傳輸量的急速提高，以大數據為主要特性的網絡結構日益凸顯出來，TB 甚至PB 級的海量信息數據已經成為常態。但是網絡在方便我們日常工作和豐富我們生活的同時，如何提取有價值的知識顯得尤為重要。聚類能夠根據數據特征，將相似特征數據進行歸類，從而高效組織數據[1]。現有k-means 等聚類算法依賴于初始值的選取，并且基于歐氏距離和梯度下降進行的搜索常常使算法陷入局部最優，而基于非線性核距離且對任意形狀樣本集都具有全局最優解的譜聚類，成為近年研究熱點[2]。

但是，傳統的譜聚類算法涉及構造相似度矩陣和對相應的拉普拉斯矩陣特征分解，需要的空間復雜度和的時間復雜度對于大規模數據集來說是難以承受的計算負擔[3]。為此，文獻[4]通過計算數據的低維嵌入，提出基于拐點估計的譜聚類中心數自動確定方法，對分布復雜數據集的譜聚類效果較好；文獻[5]通過在選取的核心點集上分組和譜聚類，并根據數據集與核心點集的一致性實現大數據譜聚類。文獻[6]提出使用Nystro¨m 近似技術來避免計算整個相似性矩陣，加速大數據譜聚類；隨后文獻[7]又用近似奇異值分解方法提升了Nystro¨m 方法中特征分解的效率；而文獻[8]則設計了一種自適應采樣的方法，改進了Nystro¨m 譜聚類的聚類效果。文獻[9]根據 Nystro¨m 誤差界分析，采用集成Nystro¨m以犧牲數據計算準確性換來大數據譜聚類的快速計算，具有更快的收斂速度。為避開矩陣特征分解的時間復雜度，文獻[10]在研究加權核k-means 算法與譜聚類Normalized Cut 目標函數在數學上等價基礎上，通過加權核k-means 算法優化，取得了更好的聚類結果。但其在有效捕捉非線性數據結構的同時，還需存儲一個較大的核矩陣；文獻[11]提出了基于地標點的譜聚類算法，指出該方法適用于大規模數據集，并且性能要優于Nystro¨m 方法，并在隨后給出了相關理論分析，但該方法用隨機采樣確定地標點，抽樣結果不穩定。

隨機映射由于可在降低數據規模的同時保持大部分原始信息而被廣泛用于聚類算法中，為此在已有加權核k-means 與經典譜聚類等價方法的研究基礎上，利用隨機映射得到近似奇異值分解，然后由分解得到的近似奇異向量確定各點在數據集中的權重并計算抽樣概率，以此得到快速合理抽樣，然后通過約束隨機抽樣的樣本點生成的子空間來逼近聚類中心，從而僅需要計算部分核矩陣即可實現大規模譜聚類，極大減少核矩陣的復雜度，實驗驗證了改進算法與標準算法具有相近的聚類表現，但極大縮短運行時間。

2 加權核k-means 與譜聚類等價性

2.1 經典譜聚類

譜聚類基于譜圖理論，將待分析大數據作為無向加權圖進行處理，從而將聚類問題轉變為子圖內權值最大而子圖間權值最小的最佳圖劃分問題[2]。將 n 點數據集 X=｛x1，x2，…，xn｝視為無向圖G，則將X 聚類為k 類即為將V=X 劃分為k 個子集，即且Vi∩Vj=?，i≠j。譜聚類應使其劃分所得類的類內連接權值最大，或類間權值達到最小值，由此得到譜聚類的目標函數。建立類別矩陣描述 V 中元素是否屬于類Vi，即對于節點 xi，若 xi∈Vi，則 Uij=1，否則 Uij=0，根據節點類別的唯一性，有UT1k=1n，向量1n∈Rn×1的元素全為1。則譜聚類目標函數可寫為[11]：

式中：NL（V1，V2）=L（V1，V2）/L（V1，V）—兩個子類間總的歸一化連接邊權值—描述了子類Vi內元素的連接權值ZD1/2且滿足約束是單位矩陣，tr（·）表示矩陣跡[11]。

2.2 加權核k-means 算法

核k-mean 算法采用非線性核距離度量[12]。對核k-mean 算法的每個數據xi都分配一個權值wi，得到加權核Kmeans 算法的目標函數：

式中：κ（，）：Rd×Rd→R—核距離函數；Hk—再生核希爾伯特空間，的泛函范數；ci（·）—第 i∈［k］聚類中心，則由權值 W=diag（w1，…，wn）可以構建待聚類集合的加權類別矩陣Y=（y1，…，yk）T=UW及，其中則加權核k-means 最佳的類中心為[12]：

將式（2）目標函數平方項展開，寫為矩陣跡的形式得

式中：K∈Rn×n—核距離函數矩陣，Kij=κ（xi，xj），由于式第一項為常量，比較式（1）和式（4）可見，Normalized Cut 目標函數基于矩陣跡與加權核k-means 是等價的，因此可以通過加權核k-means 算法的迭代計算解算NA（V）目標函數，替代矩陣特征分解的高復雜度計算。加權核k-means 算法進行大規模數據譜聚類，在時間和空間復雜度上均有很大優勢，并且在聚類效果上也令人滿意，但式（4）仍需計算全部核矩陣K，在大規模數據集應用時仍受限。為此，通過隨機抽樣部分數據構建部分核矩陣，并約束樣本子空間以涵蓋聚類中心，設計了改進加權核k-means 算法進行大數據譜聚類。

3 抽樣改進加權核k-means 算法

根據式（3），聚類中心為類內所有數據的線性組合，即其位于類內數據張成的子空間中，ci（·）∈Hκ，因此，如果采樣數據能夠把類中心約束到其張成的較小的子空間?Hκ，且滿足（1）盡可能的足夠??；（2）具有足夠覆蓋空間以近似的聚類結果，則可以通過采樣數據獲得與原數據相似的聚類效果。為此，文中首先給出基于隨機映射的快速數據抽樣，在合理抽樣基礎上給出構造的方法以改進加權核k-means 算法的復雜度。

3.1 基于隨機映射的快速數據抽樣

作為抽樣改進加權核k-means 算法的關鍵，抽樣點的選取在很大程度上影響了改進算法的聚類效果。常用的方式是均勻隨機采樣，但在大規模數據集上隨機抽樣的不穩定性很可能會導致所抽樣本點集中于某一區域。為此，采用基于隨機映射的近似奇異值分解（Singular Value Decomposition，SVD）算法[13]，在降低采樣過程時間復雜度的同時，得到與精確SVD 相近的采樣結果，快速數據抽樣算法，如表1 所示。

表1 基于近似奇異值分解的快速數據抽樣Tab.1 Fast Data Sampling Based on Approximate SVD

根據表1 算法產生抽樣所需的抽樣矩陣S，通過STA∈Rp×d可實現數據抽樣。根據文獻[14]中定理，基于該抽樣所得到的矩陣A∈Rn×d的行樣本，其最優近似誤差與相差一個較小的因子，保持了原始矩陣的大部分信息，即對任意矩陣抽樣并適當調整樣本尺寸后，所產生的矩陣與原始矩陣在Frobenius 范數平方上接近，從而表明，采用基于近似SVD 的抽樣可以保證抽樣誤差在特定的界內，這使得采樣的樣本具有較好的代表性。因此，利用該方法所得到的采樣樣本，其與數據點形成的相似度矩陣能較好地描述數據之間的關系[14]。

3.2 基于改進加權核k-means 的譜聚類

4 實驗與分析

為驗證文中算法（記為Sik-SC）性能，將其與經典譜聚類（Clas-SC）[15]、基于標準加權核的譜聚類（Swk-SC）[11]、基于 Nystro¨m譜聚類（Nys-SC）[8]和基于 MEKA 近似核聚類（Mek-KC）[7]四種譜聚類方法進行性能比較實驗。實驗環境：Intel（R）CoreTMi7-4710MQ@2.50GHZ，16G 內存，MATLAB 2016b，數據集部分重要參數，如表2 所示。

表2 實驗數據集參數Tab.2 Data Characteristics of Benchmark Datasets

Ringnorm 集[15]MNIST 集為含有10 種類型的手寫數字圖片集；MNIST 集為含有10 種類型的手寫數字圖片集[16]；實驗中聚類結果的準確性采用歸一化互信息來評價：

4.1 聚類性能比較實驗

Nys-SC、Mek-SC 和 Sik-SC 算法在 4 個數據集上 NMI 結果，如圖1 所示。由于Clas-SC 與Swk-SC 對所有數據進行處理，即采樣率為100%，因此其在Ringnorm 數據集上的NMI 指標為0.3758 和0.3895，而在MNIST 集上，由于數據規模巨大，數據維數較高，兩算法沒有實現聚類。

圖1 算法在各數據集上的性能實驗結果Fig.1 Performance Results on Various Data Sets

從圖1 結果可見，通過數據抽樣，Nys-SC、Mek-SC 和Sik-SC算法在2 個數據集上都表現出較好的聚類性能。且隨著采樣點數的增加，三種算法的聚類NMI 指標逐漸增大，聚類性能逐漸提高。將圖1 結果與Clas-SC 與Swk-SC 兩種算法的實驗結果對比分析，Sik-SC 算法在不同采樣率下的NMI 指標與Clas-SC 和Swk-SC 算法的NMI 指標相關不大，而隨著采樣點數的增加，Sik-SC 算法的聚類NMI 指標逐漸逼近Swk-SC 算法的聚類NMI指標，說明文中改進加權核k-means 算法通過將聚類中心約束在采樣數據張成的子空間的改進方法可以取得與使用完整核矩陣相近的聚類結果，也說明改進方法有效。

4.2 算法運行時間比較實驗

Nys-SC、Mek-SC 和Sik-SC 算法在不同采樣時的運行時間結果，如圖2 所示。Clas-SC 算法與Swk-Sc 算法在Ringnorm 數據集上的運行時間分別為247.4842（s）和 157.67012（s），而在 MNIST集上因無法實現聚類，其運行時間未知。

圖2 算法在各數據集上的運行時間Fig.2 The Running Time of the Algorithm on Each Data Set

從運行時間比較實驗結果可以看出，Clas-SC 算法聚類所需要時間最長，主要是因為其完整的Laplacian 矩陣特征分解過程的時間復雜度最高，而Swk-SC 算法采用加權核kmeans 算法替代矩陣特征分解，聚類效率有了明顯的提高，但其全部核矩陣的使用在數據規模巨大時，無法得到聚類結果，而僅使用部分核矩陣的Nys-SC、Mek-SC 和Sik-SC 算法在所有數據集上的運行時間都得到大大幅度的縮減，且在MNIST 集上仍取得較快的聚類運行時間。從圖2 三種算法的實驗結果可以看出，隨著采樣點數的增加，抽樣率改進聚類效果的同時三種算法的聚類時間也逐漸增加，但Sik-SC 算法的變化趨勢相對最為緩慢，且大多數情況下聚類時間較短，這主要因為，隨著抽樣點數的增加，同樣采用抽樣策略的Nys-SC 算法，其近似特征向量的計算時間大幅增加，而Mek-SC 算法的最佳k 秩近似核矩陣的求解效率也會大幅降低，Sik-SC 算法僅與采樣點數及迭次數相關，因此在采樣數增大時，能夠較緩慢的增長趨勢，聚類效率更高。

綜合實驗結果可以看出，Sik-SC 算法在保持與經典Swk-SC算法聚類性能相似的情況下，極大的提高算法的聚類效率，更適合大規模數據挖掘工作。

5 結語

在分析經典譜聚類算法與加權核k-means 函數等價的基礎上，設計了一種基于抽樣改進加權核k-means 的大規模數據譜聚類算法，算法通過加權核k-means 優化迭代過程避免Laplacian矩陣特征分解的高復雜度資源占用，通過隨機映射得到近似奇異值分解，并由分解得到的近似奇異向量確定各點在數據集中的權重并計算抽樣概率，以此得到快速合理抽樣，通過約束抽樣子空間以涵蓋聚類中心，避免全部核矩陣的使用，從而降低經典算法的時間空間復雜度。實驗結果表明，改進算法在保持與經典算法相近聚類精度基礎上，大幅提高了聚類效率。但是改進算法還需進一步考慮如何合理設置采樣數以提高算法的性能。