大規模數據集Spark并行優化譜聚類

呂洪林,尹青山,2

(1. 遼寧對外經貿學院,遼寧 大連 116052； 2. 吉林大學,吉林 長春 130000)

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

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

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

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

1 譜聚類并行優化

1.1 相似矩陣并行計算

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

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

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

(1)

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

1.2 矩陣并行正規化

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

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

(2)

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

(3)

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

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

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

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

1.3 特征向量計算并行化

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

(4)

根據最大可分理論將式(4)目標函數轉換為方差最大的向量形式，即

(5)

并可以通過拉格朗日乘的方法轉化為

LInvy=λDλ

(6)

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

vi+1=LInvvi

(7)

式中，i為迭代次數，當其足夠大時，對v(i)進行聚類可得最終譜聚類。基于LInv的稀疏特性，文中將樣本數據視為有向圖，并根據圖的消息傳遞機制進行近似特征向量的并行迭代。Laplacian矩陣L的正則化并行計算如下。

輸入 相似矩陣W

輸出 正規化L矩陣

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

主體 ∥正規化過程

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聚類的并行計算通常為初始聚類中心獲取并分發到各分布式節點中，計算各節點中樣本與初始中心的距離，迭代更新聚類中心及距離，直到達到預設的迭代最大次數或誤差限。因此，并行計算中距離的計算仍產生很大的計算量和節點間通信開銷，為此，文中采用樣本二范數關聯的方式優化K-means聚類過程中的距離計算。

(8)

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

(9)

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

2 試驗分析

為驗證文中并行優化算法(記為AppSC)的聚類性能，試驗采用手寫字集MNIST[15]和網絡攻擊統計數據集Cup99[16]作為試驗數據，由8節點192 GB內存的計算機群搭建試驗環境，Spark框架采用V2.0.1版本，MNIST集的樣本數為10 000，特征數為856，特征類別為10，Cup99集樣本數為400 000，特征數為45，特征類別為35。

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

2.1 聚類的效果比較

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

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

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

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

2.2 特征向量求解時間試驗

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

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

2.3 擴展性能測試

采用不同數據規模的Cup99集數據分析文中改進算法的適應性試驗，試驗統計各算法在不同規模集上的運行時間，如圖4所示，圖中試驗結果為50次運行時間的平均值。

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

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

3 結 語

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

但文中算法還需進一步研究并行算法中t近鄰、特征向量維數等參數的自動調優，以充分發揮算法的性能優勢。