一種基于抽樣改進加權核K-means的大數據譜聚類算法

金 海，張勁松，吳 睿,3

(1. 深圳職業技術學院，廣東 深圳 518055； 2. 浙江工業大學， 浙江 杭州 310014; 3. 西安交通大學，陜西 西安 710061)

科技與互聯網的快速發展產生了海量信息數據，如何從TB、PB級的數據中提取有價值的知識，聚類成為主要工具。聚類能夠根據數據特征和內在關系，將特征相似數據歸類，從而高效組織數據[1]。現有聚類算法大多基于歐氏距離，對于非凸樣本空間易陷入局部最優，且無法完全反映復雜數據集的空間分布特點[2-3]。而基于非線性核距離計算相似矩陣的譜聚類，可實現包含非凸形結構等任意形狀樣本集的全局最優解聚類，成為極具競爭力的聚類方法[4]。

經典算法在較小規模的數據集上聚類性能優越，而隨著海量規模數據集應用的出現，其相似矩陣的計算、存儲及特征分解的時間、空間復雜度限制了其優越性能的發揮[5]。為此，錢鵬江等[6]約束譜聚類的指示向量并融合約束最小球理論，將大規模數據集自適應圖松弛譜聚類算法的復雜度降低到漸近線性時間，數據抽樣和并行處理能夠避免數據規模的限制。Li等[7]抽取代表點構建了鄰接矩陣，并計算了其特征向量和特征解。張順龍等[8]借助稀疏編碼抽取了大規模集的代表點來逼近相似矩陣，但其抽樣點集需盡可能大。楊藝等[4]在選取的核心點集上進行分組和譜聚類，并根據數據一致性進行了大規模數據的譜聚類。Fowlkes等[9]研究了Nystr?m近似來改善經典譜聚類的相似性矩陣計算。Kumar等[10]根據Nystr?m誤差界分析，采用集成抽樣方法以犧牲準確性換取更快的算法收斂速度，提高了算法的效率。

稀疏化和Nystr?m近似對內存占用效果較好，但仍需計算經典譜聚類的全部相似矩陣，為此，Dhillon等[11]在推導出加權核K-means算法與譜聚類目標函數在數學上等價基礎上，通過加權核K-means來優化譜聚類的目標函數，避免全部相似矩陣的計算，取得了更好的聚類結果，但其核矩陣仍需較多的存儲和計算資源。因此，在分析核矩陣復雜性原因的基礎上，本文提出基于隨機抽樣改進加權核K-means算法的大規模數據集譜聚類方法。算法通過Leaderths算子快速獲得初始聚類數，以指導數據抽樣，然后在子樣本集中約束樣本子空間逼近聚類中心，從而僅需計算樣本核矩陣，極大減少核矩陣的復雜度。

1 基于加權核K-means的譜聚類算法

1.1 經典譜聚類

經典譜聚類基于譜圖理論，將數據聚類轉為最佳子圖劃分問題[3]。數據集表示為無向加權圖G=(V,E,A)，其中V為待聚類數據集，E表示數據間連接的集合，而衡量連接值大小即衡量兩數據同類可能性的權重，組成非負對稱矩陣A。

(1)

式中，link_ratio(Vi,Vi)描述子類Vi內元素的歸一化連接權值。由于對于一次聚類，類內總權值與類間總權值之和為整個無向圖節點總權值，因此，最大化式(1)所示目標函數可以使類內連接權值最大且類間連接權值最小。

(2)

1.2 加權核K-means算法

核K-means算法采用非線性核距離度量，與經典K-means算法相比，更適于存在非線性分布的數據集的聚類，目標函數為使劃分后的類中數據點到類中心的距離誤差總和最小[12]，即

(3)

式中,κ():Rd×Rd→R為非線性核距離函數；Hk為其再生核希爾伯特空間；ci()為每個子類的聚類中心。

對數據集中元素分配權值w，則加權核K-means目標函數為

(4)

其聚類中心為

(5)

由此可以得到加權類別矩陣Y∈Rk×n為

Y=(y1,…,yk)T=UW

(6)

式中，W=diag(w1,…,wn)。對式(4)的平方項展開并推導為矩陣秩的形式可得[11]

(7)

(8)

但加權核K-means的核矩陣計算和存儲，在大規模數據應用時仍受限。為此，本文通過隨機抽樣近似核矩陣，設計了改進加權核K-means算法，以減少大數據集應用中算法的時間和空間復雜度。

2 抽樣改進加權核K-means算法

數據抽樣思想改進加權核K-means算法可以避免數據規模的限制[13]，但樣本集的數據規模及其初始類設置對原始大數據集所含類別的完整覆蓋，對算法的聚類性能起決定作用。為此，首先通過Leaders快速聚類方法對大規模數據集進行初始聚類，獲得初始聚類中心，然后根據初始中心多次隨機抽樣形成多子樣本集，對每個子樣本集進行加權核K-means聚類，最后對各子樣本集聚類結果進行整合，從而在合理控制抽樣數據規模的同時增強初始聚類設置對原始類別的覆蓋，使其近似核矩陣的計算更合理。

2.1 基于Leaders初始聚類設置

Leaders方法[14]通過選取大規模數據集中各子類的Leader來實現基于能量的數據聚類，其在無需先驗數據類別數設置的情況下，對大數據集只需掃描一次即可完成聚類。雖然該算法對數據元素的輸入順序較為敏感，聚類結果并不精確，會存在類內相似性大于類間相似性的情況，但其聚類速度較快，聚類效率優勢十分明顯，可以用于對大規模數據集的預處理，算法實現過程見表1。

表1 Leaders算法的偽代碼實現

文中采用Leaders算法進行初始聚類預處理，利用獲得的聚類中心進行多樣本子集的隨機抽樣和樣本集的加權核K-means聚類初始值設置。

2.2 子樣本集加權核K-means聚類

Leaders算法聚類結果并不精確，會存在類內相似性大于類間相似性的情況，因此對每個初始聚類中心的數據進行隨機抽樣，可以在維護各個抽樣之間關聯性的同時，將未被正確分類的數據通過隨機抽樣分布到不同的子樣本集中，這樣通過子樣本集的重新聚類實現這部分數據的新分類。

(9)

(10)

(11)

(12)

將式(8)代入得抽樣子集改進加權核K-means算法的目標函數為

(13)

3 試驗與分析

為驗證文中譜聚類算法(記為SikSC)的性能，試驗將其與傳統譜聚類(記為TraSC)[1]、自適應Nystr?m譜聚類(記為NysSC)[9]和內存高效核近似聚類(記為MekSC)[4]3種方法進行比較。試驗服務器環境構建為：Intel Xeon E5-2699 v4 @ 2.20 GHz，8 GB內存，Matlab 2012b。試驗采用表2所示的4個數據集，Waveform集由施加均值0、σ2=1噪聲的3種類型的波形樣本組成[15]；Ringnorm集[16]包含正態分布的兩種樣本，且兩樣本存在重疊，聚類難度較大；USPS集和MNIST集為圖片集，各包含10種手寫數字[16]。

表2 試驗數據集相關參數

采用歸一化互信息(NMI)作為評價指標

(14)

式中，Uc和Ut分別為試驗和真實類別矩陣，H(Uc)和H(Ut)分別為其信息熵。試驗中迭代次數為50，聚類結果為20次試驗平均值。

3.1 聚類性能比較試驗

圖1所示為4種算法在不同采樣點數的聚類NMI結果，由于傳統譜聚類對所有數據進行處理，因此其在前3個數據集結果如圖中虛線所示，其在各采樣點下NMI值始終為唯一值；而在圖1(d)的MINIST數據集中，由于數據集規模太大，平臺內存局限，傳統譜聚類無法實現聚類。

圖1 算法在各數據集上的性能試驗結果

從圖中試驗結果看出，傳統算法由于使用所有數據在前3個規模相對較小的數據集中取得聚類結果最優，但在MNIST大規模數據集時因核矩陣占用資源巨大而無法聚類，而NysSC、MekSC及文中SikSC算法通過抽樣實現4個數據集的較好聚類，說明抽樣約束減少資源占用對大數據譜聚類是有效的。隨著采樣點數的增加，3種算法聚類性能(NMI指標)逐漸提高，SikSC最優，且逼近傳統譜聚類NMI指標，說明文中算法通過改進抽樣策略和子集中對聚類中心的約束可以取得與完整核矩陣相近的聚類結果，也說明改進方法有效。

3.2 算法運行時間比較試驗

在上一試驗基礎上，NysSC、MekSC和SikSC這3種算法采樣點數取2000，TraSC仍使用全部數據，在4個數據集上運行時間比較結果見表3。

表3 算法運行時間的試驗結果 s

從運行時間可以看出，傳統算法運行時間最長，其完整的Laplacian矩陣特征分解時間復雜度最高，而使用數據抽樣或近似的NysSC、MekSC及SikSC算法的運行時間在所有數據集上都大幅縮減，且在MNIST集上仍取得可接受的聚類時間。進一步測試不同采樣點下3種算法的聚類時間可知，隨著采樣點數的增加，3種算法的聚類時間也逐漸增加，但SikSC算法的變化趨勢相對最為緩慢，且聚類時間較短，這是由于NysSC算法近似特征向量的計算時間開銷較大，而MekSC算法的最佳秩近似核矩陣的求解效率也大幅降低。

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

4 結 語

在分析經典譜聚類算法目標函數與加權核K-means函數等價基礎上，設計了一種基于抽樣改進加權核K-means算法的大規模數據譜聚類算法。算法通過Leaders進行初始聚類預處理，以增加隨機抽樣的有效性，使隨機抽樣及其數據規模更合理，通過子類加權核K-means迭代優化避免Laplacian矩陣特征分解資源占用，從而通過部分核矩陣的使用降低經典算法的時間、空間復雜度。試驗結果表明，改進算法在保持聚類精度基礎上，大幅提高了聚類效率。