大規(guī)模數(shù)據(jù)集Spark并行優(yōu)化譜聚類

呂洪林,尹青山,2

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

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

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

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

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

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

1.1 相似矩陣并行計算

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

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

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

(1)

式中，[xi]為樣本xi的序號；sim(xi,xt)為兩樣本的相似度值。t近鄰稀疏化后，對相似矩陣進行對稱性修復(fù)，如圖1所示，以xi的鄰居xj的序號作為KEY值，收集其Sset[xi]，倒排后與Sset[xi]進行“或”合并，從而得到xj的所有相似度信息，實現(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()為與當前樣本相似的其他樣本的序號集，而VarArr()描述了該相似值。在計算行元素的和之后，為每行增加對角索引號，并將D中非零對角元素添加到W矩陣的相應(yīng)對角元素位置。最后對W非對角元素值取反，如圖2(b)所示，則可以構(gòu)建Laplacian矩陣。

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

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

1.3 特征向量計算并行化

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

(4)

根據(jù)最大可分理論將式(4)目標函數(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ù)，當其足夠大時，對v(i)進行聚類可得最終譜聚類。基于LInv的稀疏特性，文中將樣本數(shù)據(jù)視為有向圖，并根據(jù)圖的消息傳遞機制進行近似特征向量的并行迭代。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]的形式進行存儲；

lapM:RDD[SP]；

1.4 K-means聚類并行化算法

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

(8)

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

(9)

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

2 試驗分析

為驗證文中并行優(yōu)化算法(記為AppSC)的聚類性能，試驗采用手寫字集MNIST[15]和網(wǎng)絡(luò)攻擊統(tǒng)計數(shù)據(jù)集Cup99[16]作為試驗數(shù)據(jù)，由8節(jié)點192 GB內(nèi)存的計算機群搭建試驗環(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)作為性能評價指標，NMI∈[0,1]值越大表明算法的聚類性能更優(yōu)。

2.1 聚類的效果比較

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

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

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

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

2.3 擴展性能測試

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

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

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

3 結(jié) 語

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

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