呂洪林,尹青山,2

(1. 遼寧對外經(jīng)貿(mào)學(xué)院,遼寧 大連 116052； 2. 吉林大學(xué),吉林 長春 130000)

譜聚類能夠基于數(shù)據(jù)的非線性核距離對數(shù)據(jù)集進(jìn)行歸類，從而挖掘數(shù)據(jù)背后的隱藏價值，成為近年研究熱點(diǎn)[1-2]。但隨著互聯(lián)網(wǎng)和信息傳輸能力的發(fā)展，以大數(shù)據(jù)為特性的TB甚至PB級的大規(guī)模數(shù)據(jù)集已經(jīng)成為常態(tài)，經(jīng)典譜聚類對于大規(guī)模數(shù)據(jù)集的運(yùn)行時間及計算瓶頸越來越突出[3]。

為此，已有研究提出了各種改進(jìn)的譜聚類算法。文獻(xiàn)[4]通過數(shù)據(jù)采樣預(yù)處理提取核心點(diǎn)集，借助一致性理論由核心點(diǎn)集完成大規(guī)模數(shù)據(jù)集的快速譜聚類。文獻(xiàn)[5]通過Leaders算子初始聚類控制抽樣子集對原始數(shù)據(jù)類別的覆蓋，再通過子集部分核矩陣完成大規(guī)模集譜聚類。文獻(xiàn)[6—7]提出使用Nystr?m近似技術(shù)避免計算整個相似矩陣，取得較好的加速效果；文獻(xiàn)[8]提出共享近鄰約束譜聚類，用共享近鄰去衡量數(shù)據(jù)相似性，用主動約束描述數(shù)據(jù)關(guān)系，實(shí)現(xiàn)增量式聚類。

隨著分布式并行框架的興起，文獻(xiàn)[9]研究了近似密集相似計算方法，分析了Nystr?m與稀疏矩陣方法；文獻(xiàn)[10]以MapReduce框架并行優(yōu)化譜聚類，提高算法的運(yùn)算效率和性能，其聚類速率隨數(shù)據(jù)規(guī)模的增大呈近似線性增長；文獻(xiàn)[11]以MapReduce框架對初始聚類數(shù)據(jù)并行地進(jìn)行K-means迭代聚類，獲取大規(guī)模數(shù)據(jù)集的快速高效聚類；文獻(xiàn)[12]基于輪廓系數(shù)和Spark框架并行改進(jìn)相似距離計算，有效提高了譜聚類的準(zhǔn)確率和擴(kuò)展能力。

并行化有效提升譜聚類在大規(guī)模數(shù)據(jù)集上的聚類性能，但與HDFS等主流系統(tǒng)的兼容性有待提高。當(dāng)前Spark技術(shù)已成為大數(shù)據(jù)處理的主流平臺，其RDD和DAG抽象極大地提高了數(shù)據(jù)挖掘的并行分析性能。為此，本文提出適于譜聚類在大規(guī)模集應(yīng)用的Spark框架并行化算法，通過試驗結(jié)果驗證改進(jìn)算法在大規(guī)模數(shù)據(jù)集下良好的聚類性能和可擴(kuò)展性。

1 譜聚類并行優(yōu)化

1.1 相似矩陣并行計算

譜聚類算法中的相似矩陣主要由所有樣本之間的兩兩相似信息構(gòu)成，在大規(guī)模數(shù)據(jù)集下，對所有樣本計算相似度將帶來難以承受的計算開銷甚至導(dǎo)致聚類失敗，為此，采用分布式并行算法運(yùn)算復(fù)雜度將由原始算法的O(n2)降低為O(n2/p)，其中p為計算并發(fā)度，同時采用t近鄰[7]方法對稠密相似矩陣進(jìn)行稀疏化。

在大規(guī)模集上相似矩陣占用較大的存儲開銷，為此，采用t近鄰[7]和倒排索引進(jìn)行矩陣稀疏化和對稱性快速修復(fù)[13]。對每個樣本xi進(jìn)行t近鄰相似過濾，得到距離最近的t個鄰居，組成集合Sset[xi]

Sset[xi]={([xi],sim(xi,x1)),…,([xi],sim(xi,xt))}

(1)

式中，[xi]為樣本xi的序號；sim(xi,xt)為兩樣本的相似度值。t近鄰稀疏化后，對相似矩陣進(jìn)行對稱性修復(fù)，如圖1所示，以xi的鄰居xj的序號作為KEY值，收集其Sset[xi]，倒排后與Sset[xi]進(jìn)行“或”合并，從而得到xj的所有相似度信息，實(shí)現(xiàn)矩陣的對稱性修復(fù)。

1.2 矩陣并行正規(guī)化

根據(jù)單向迭代和t稀疏化計算樣本的相似矩陣W={wi,j}后，由其對角矩陣D={Di,j}得到經(jīng)典譜聚類算法計算樣本的Laplacian矩陣及其正規(guī)化計算式

L=D-W=D-1/2·L·D-1/2

(2)

其中，對角矩陣的計算式為

(3)

經(jīng)典并行譜聚類算法需要大小為N×N的2個矩陣存儲，空間需求較大。因此，對W通過相應(yīng)位置變換構(gòu)建Laplacian矩陣，其過程如圖2所示。

首先以行為單位，并行計算W每行元素的和，如圖2(a)所示，W的行元素代表了樣本的相似度集合信息，圖中IndexArr()為與當(dāng)前樣本相似的其他樣本的序號集，而VarArr()描述了該相似值。在計算行元素的和之后，為每行增加對角索引號，并將D中非零對角元素添加到W矩陣的相應(yīng)對角元素位置。最后對W非對角元素值取反，如圖2(b)所示，則可以構(gòu)建Laplacian矩陣。

根據(jù)式(2)所示，Laplacian矩陣L的正規(guī)化通常通過矩陣連乘完成，其復(fù)雜度較高，達(dá)到O(n3)[14]。為此，將矩陣連乘轉(zhuǎn)換為標(biāo)量與矩陣相乘的形式[13]，其計算復(fù)雜度相應(yīng)的降為O(n2/p)。

整個計算過程見表1，計算對角矩陣后，利用Spark框架的broadcast機(jī)制將其各元素分配到對應(yīng)的節(jié)點(diǎn)內(nèi)，各計算節(jié)點(diǎn)完成矩陣相應(yīng)元素取反及添加索引操作。

1.3 特征向量計算并行化

譜聚類需求解Lnorm的前k個特征值對應(yīng)的特征向量，構(gòu)成降維矩陣，文中采用并行近似特征向量計算代替經(jīng)典譜聚類中的精確特征向量計算，以加速大規(guī)模集特征向量的計算過程。目標(biāo)函數(shù)為

(4)

根據(jù)最大可分理論將式(4)目標(biāo)函數(shù)轉(zhuǎn)換為方差最大的向量形式，即

(5)

并可以通過拉格朗日乘的方法轉(zhuǎn)化為

LInvy=λDλ

(6)

式中，LInv為L的取反矩陣，根據(jù)式(6)可知計算LInv的前k個特征向量即得到傳統(tǒng)譜聚類的最優(yōu)解。基于PIC算法思想[15]可得迭代計算式為

vi+1=LInvvi

(7)

式中，i為迭代次數(shù)，當(dāng)其足夠大時，對v(i)進(jìn)行聚類可得最終譜聚類?；贚Inv的稀疏特性，文中將樣本數(shù)據(jù)視為有向圖，并根據(jù)圖的消息傳遞機(jī)制進(jìn)行近似特征向量的并行迭代。Laplacian矩陣L的正則化并行計算如下。

輸入 相似矩陣W

輸出 正規(guī)化L矩陣

函數(shù) diagM←simM.map(e.count)broadcast();

主體 ∥正規(guī)化過程

lapM←simM.map{

FOR each linee

IF diagM[e]==0

SP中的每一個值：arr_v=0；

ELSE

arr_v=arr_v×(diagM[e])-0.5；

}

lapM←lapM.map{

FOR each linee

FORi:SP.arr_value.length

IF diagM[e]==0

arr_v[i]=0；

ELSE

arr_v[i]=arr_v[i]×(diagM[i])-0.5；

}

∥lapM采用RDD[SP]的形式進(jìn)行存儲；

lapM:RDD[SP]；

1.4 K-means聚類并行化算法

譜聚類算法中K-means聚類的并行計算通常為初始聚類中心獲取并分發(fā)到各分布式節(jié)點(diǎn)中，計算各節(jié)點(diǎn)中樣本與初始中心的距離，迭代更新聚類中心及距離，直到達(dá)到預(yù)設(shè)的迭代最大次數(shù)或誤差限。因此，并行計算中距離的計算仍產(chǎn)生很大的計算量和節(jié)點(diǎn)間通信開銷，為此，文中采用樣本二范數(shù)關(guān)聯(lián)的方式優(yōu)化K-means聚類過程中的距離計算。

(8)

realDis=(a1-a2)2+(b1-b2)2

(9)

顯然boDis值小于等于realDis值，由于節(jié)點(diǎn)中的各個樣本或聚類中心都會事先計算并記錄boDis值，因此在K-means聚類過程計算距離時，先進(jìn)行如下比較過程：①初始化樣本與其最近聚類中心的距離bDis，然后比較boDis與bDis的值大?。虎谌鬮oDis大于等于之前計算的bDis最小值，說明realDis不可能小于bDis最小值；③若boDis小于bDis最小值，則計算realDis，當(dāng)realDis

2 試驗分析

為驗證文中并行優(yōu)化算法(記為AppSC)的聚類性能，試驗采用手寫字集MNIST[15]和網(wǎng)絡(luò)攻擊統(tǒng)計數(shù)據(jù)集Cup99[16]作為試驗數(shù)據(jù)，由8節(jié)點(diǎn)192 GB內(nèi)存的計算機(jī)群搭建試驗環(huán)境，Spark框架采用V2.0.1版本，MNIST集的樣本數(shù)為10 000，特征數(shù)為856，特征類別為10，Cup99集樣本數(shù)為400 000，特征數(shù)為45，特征類別為35。

以精確特征向量并行譜聚類(記為AccSC)，基于Spark并行計算框架的K-means并行優(yōu)化算法(記為Sp-kmeans)[14]及PIC快速迭代聚類算法(記為PicSC)[9]作為性能對比算法，以歸一化互信息(NMI)作為性能評價指標(biāo)，NMI∈[0,1]值越大表明算法的聚類性能更優(yōu)。

2.1 聚類的效果比較

以MNIST手寫集和類別數(shù)20的Cup99集為數(shù)據(jù)，比較各算法的譜聚類效果，試驗中算法分別進(jìn)行50次取各試驗的平均NMI作為試驗，其值見表1和表2，其中表2試驗進(jìn)行了t近鄰稀疏處理。

表1 平均NMI值試驗結(jié)果(未進(jìn)行稀疏處理)

表2 稀疏化后的NMI試驗結(jié)果(t=200)

從表1和表2試驗結(jié)果中可以看出，基于精確特征向量的AccSC算法在不同的試驗數(shù)據(jù)集上均取得較好的聚類性能，文中算法采用近似特征向量替換，其聚類性能相比EigSC算法聚類性能有所下降，但仍比另外兩種算法的聚類性能更優(yōu)，驗證了采用近似特征向量替代精確特征向量計算的有效性。表3中試驗數(shù)據(jù)的相似矩陣在經(jīng)過t=200近鄰稀疏化后，雖丟失部分相似度信息，但對比表2和表3中相同算法的試驗結(jié)果可以看出，經(jīng)稀疏處理后算法得到的NMI值更優(yōu)，說明合理的t值設(shè)置不僅有效減少了算法對于大規(guī)模集譜聚類時的存儲開銷，而且一定程度提高了算法的聚類性能，后續(xù)試驗采用t=200近鄰稀疏。

2.2 特征向量求解時間試驗

本節(jié)主要對譜聚類中的耗時較大的相似度計算及特征向量求解進(jìn)行運(yùn)算效率試驗比較。從Cup99數(shù)據(jù)集中抽取0.1、0.5、1、2、5、10萬條樣本，并將數(shù)據(jù)存儲于HDFS中。首先對文中單向循環(huán)迭代相似度計算(記為Mulit)及傳統(tǒng)數(shù)據(jù)廣播式相似計算(記為DataBC)進(jìn)行運(yùn)行時間對比試驗，結(jié)果如圖3所示，近鄰稀疏處理t=200。

從試驗結(jié)果可知，Mulit方法具有良好的計算效率，性能優(yōu)于DataBC方法，且隨著數(shù)據(jù)集規(guī)模的增加，優(yōu)勢更為明顯，數(shù)據(jù)集規(guī)模的增加對Mulit方法的運(yùn)算時間影響變化較小，主要由于其不僅保證樣本相似度的單次計算，且避免了DataBC方法對大規(guī)模集時主節(jié)點(diǎn)壓力過大產(chǎn)生的性能瓶頸。

2.3 擴(kuò)展性能測試

采用不同數(shù)據(jù)規(guī)模的Cup99集數(shù)據(jù)分析文中改進(jìn)算法的適應(yīng)性試驗，試驗統(tǒng)計各算法在不同規(guī)模集上的運(yùn)行時間，如圖4所示，圖中試驗結(jié)果為50次運(yùn)行時間的平均值。

從圖4可以看出，AppSC、AccSC、Sp-kmeans和PicSC算法在不同規(guī)模數(shù)據(jù)集上均表現(xiàn)出較好的可擴(kuò)展性，AppSC和PicSC兩種算法的平均用時對數(shù)據(jù)集的規(guī)模不敏感，表現(xiàn)出更優(yōu)的可擴(kuò)展性，主要由于近似特征向量的使用使數(shù)據(jù)規(guī)模的增加僅影響了算法的迭代次數(shù)，獲得線性增長的運(yùn)算復(fù)雜度。Sp-kmeans算法的距離計算時間消耗及AccSC算法的精確特征向量計算均會受到樣本數(shù)據(jù)規(guī)模的影響，因而運(yùn)行時間受樣本影響最大。

綜合試驗結(jié)果，文中算法在并行優(yōu)化和近似稀疏基礎(chǔ)上，進(jìn)一步采用近似特征向量求解方法，取得與精確特征向量算法相近的聚類效果，但有效減少了算法復(fù)雜度，表現(xiàn)出較好的擴(kuò)展性和穩(wěn)健性。

3 結(jié) 語

為解決大規(guī)模數(shù)據(jù)集譜聚類的計算耗時等性能瓶頸，基于當(dāng)前Spark技術(shù)主流并行框架，提出了一種用于大規(guī)模集聚類的改進(jìn)并行算法，算法對相似矩陣稀疏化、Laplacian矩陣的構(gòu)建、K-means聚類過程距離計算進(jìn)行并行優(yōu)化，同時采用近似特征向量計算進(jìn)一步減少計算量，并分析了近特征向量的有效性。試驗結(jié)果驗證了算法在大規(guī)模數(shù)據(jù)集下良好聚類性能可擴(kuò)展性。

但文中算法還需進(jìn)一步研究并行算法中t近鄰、特征向量維數(shù)等參數(shù)的自動調(diào)優(yōu)，以充分發(fā)揮算法的性能優(yōu)勢。