金 海，張勁松，吳 睿,3

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

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

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

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

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

1.1 經(jīng)典譜聚類

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

(1)

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

(2)

1.2 加權核K-means算法

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

(3)

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

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

(4)

其聚類中心為

(5)

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

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

(6)

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

(7)

(8)

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

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

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

2.1 基于Leaders初始聚類設置

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

表1 Leaders算法的偽代碼實現(xiàn)

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

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

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

(9)

(10)

(11)

(12)

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

(13)

3 試驗與分析

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

表2 試驗數(shù)據(jù)集相關參數(shù)

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

(14)

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

3.1 聚類性能比較試驗

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

圖1 算法在各數(shù)據(jù)集上的性能試驗結果

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

3.2 算法運行時間比較試驗

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

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

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

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

4 結 語

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