崔藝馨，陳曉東

(太原工業(yè)學(xué)院 網(wǎng)絡(luò)與信息中心，太原 030008)

0 引言

譜聚類以非線性核距離進行圖相似性分割，相比于傳統(tǒng)k-means等基于歐氏距離的聚類算法，能夠?qū)Ψ峭沟热我庑螤顢?shù)據(jù)集實現(xiàn)全局最優(yōu)解，成為近年研究熱點[1-2]，但隨著大規(guī)模數(shù)據(jù)集的普及，經(jīng)典譜聚類的相似性計算和特征分解時間開銷和存儲代價太高[3]，且隨著數(shù)據(jù)規(guī)模的不斷膨脹，計算性能瓶頸越來越突出。

為此，基于采樣核心點集[4]、基于加權(quán)核k均值[5]、基于Nystr?m近似技術(shù)[6]及其改進[7]、基于共享近鄰約束[8]等各種改進的大規(guī)模數(shù)據(jù)集譜聚類算法被提出。

近年，隨著MapReduce、Hadoop及Spark等分布式并行框架的興起，大規(guī)模集并行譜聚類開始廣泛應(yīng)用。Jin等[9]以MapReduce框架并行優(yōu)化譜聚類，聚類速率隨數(shù)據(jù)規(guī)模的增大呈現(xiàn)近似線性增長；張文杰等[10]在數(shù)據(jù)的初始聚類后采用MapReduce框架并行地對數(shù)據(jù)進行k-means細化聚類，實現(xiàn)大數(shù)據(jù)集快速高效聚類；李曉瑜等[11]以初始聚類緩解局部最優(yōu)解問題，采用MapReduce模型對改進后算法進行并行實現(xiàn)，算法獲得較好的準確率和擴展性；劉鵬等[12]利用輪廓系數(shù)及形態(tài)學(xué)相似距離改進聚類算法，并基于Spark框架實現(xiàn)算法并行計算，具有較好計算效率和并行能力。

已有并行算法大多與主流Hadoop分布式文件系統(tǒng)(Hadoop Distributed File System， HDFS)、Spark等的兼容性較差[13-14]，為此，基于Spark并行框架，提出了用于大規(guī)模數(shù)據(jù)集譜聚類的并行化算法，算法主要研究了相似矩陣的單向循環(huán)構(gòu)建、Laplacian矩陣的構(gòu)建與正規(guī)化及近似特征向量計算等步驟的并行優(yōu)化。實驗結(jié)果驗證了算法在大規(guī)模數(shù)據(jù)集下良好聚類性能和可擴展性。

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

1.1 Spark并行框架

Spark并行框架是AMP實驗室(Algorithms Machines and People lab)為簡化計算機集群程序的并行編寫而設(shè)計，其對相同數(shù)據(jù)的多次調(diào)用、資源任務(wù)的調(diào)度執(zhí)行和節(jié)點并行通信等底層內(nèi)在操作都進行抽象，具有更高級API調(diào)用，其分布式結(jié)構(gòu)的靈活、編程接口的多樣和容錯性能的強大，使其適于高性能迭代計算，通過節(jié)點內(nèi)存分布式緩存計算和低延遲任務(wù)啟動減少磁盤的I/O時間。如圖1所示為Spark并行計算的運行框架，通常部署在數(shù)千節(jié)點之間，支持standalone、Yarn等集群管理器。相對于Hadoop等并行架構(gòu)，Spark框架在內(nèi)存中直接緩存中間結(jié)果，具有極大的運行速度和通用性能優(yōu)勢。

圖1 Spark并行框架示意圖Fig. 1 Schematic diagram of Spark parallel framework

1.2 單向迭代相似矩陣并行計算

相似矩陣主要描述兩樣本的相似信息，為實現(xiàn)Spark并行框架的優(yōu)化計算，需要對數(shù)據(jù)進行合理劃分，并行數(shù)據(jù)劃分時通常采用網(wǎng)絡(luò)、KD(K-Dimensional)樹及二叉樹等方法。為平衡各節(jié)點間的任務(wù)負載，提高有效數(shù)據(jù)的使用和相似度計算的質(zhì)量，對大規(guī)模數(shù)據(jù)集進行分塊時采用依據(jù)數(shù)據(jù)對象的二叉樹索引網(wǎng)格劃分，并進行二次擴展，算法采用自項而下的二分法對數(shù)據(jù)格網(wǎng)進行分割，直到網(wǎng)絡(luò)尺寸小于預(yù)設(shè)閾值，根節(jié)點記錄網(wǎng)絡(luò)總大小及數(shù)據(jù)點數(shù)，各級子節(jié)點記錄最小外包矩形(Minimal Bounding Rectangle, MBR)值及其數(shù)據(jù)點。Spark架構(gòu)在進行并行計算時，統(tǒng)計網(wǎng)格點數(shù)，并遍歷二叉樹節(jié)點，對于非平衡實際數(shù)據(jù)分布，先根據(jù)點將分區(qū)進行排序，然后采用貪心算法重組集合，從而得到n組分區(qū)樣本。分區(qū)不可避免地會將同一聚類數(shù)據(jù)分配到不同的二叉樹節(jié)點，即邊界點劃分問題，對此，在二叉樹劃分后，需進行二次劃分擴展，即對于每個分區(qū)，將邊界擴展，使處于邊界點的數(shù)據(jù)劃分到兩個分塊中，這樣通過少量的計算增加獲得更合理的數(shù)據(jù)分塊。

在大規(guī)模數(shù)據(jù)集下，提出基于單向循環(huán)迭代的分布式相似度并行計算方法，先完成節(jié)點內(nèi)樣本相似計算，再完成分區(qū)間相似計算，在計算過程中主節(jié)點分區(qū)不參與，當(dāng)前分區(qū)僅與序號更大的分區(qū)樣本進行單向相似計算，以避免重復(fù)計算，單向循環(huán)迭代如圖2所示。

大規(guī)模數(shù)據(jù)集生成的稠密相似度矩陣對數(shù)據(jù)存儲的開銷極大，為此，對其采用t近鄰算法進行稀疏化。

圖2 單向循環(huán)迭代相似度計算過程Fig. 2 One-way loop iterative similarity calculation process

1.3 Laplacian矩陣并行計算

由相似矩陣W={wi, j}計算對角矩陣D={Di, j}：

(1)

則Laplacian矩陣L的構(gòu)建及正規(guī)化為：

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

(2)

傳統(tǒng)并行構(gòu)建矩陣L的方法首先計算相似矩陣W的行元素和，然后同位置元素值相減，其計算和存儲空間需求較大。對矩陣D和W的元素分析發(fā)現(xiàn)，由于相似度定義中元素與其自身的相似度為0，因此W的對角元素均為0，而D的非對角元素均為0，于是，首先并行計算W每行元素的和，得到對角矩陣D；然后為W每行增加一個對角索引號，并將D中非零對角元素添加到W矩陣的相應(yīng)對角線位置；最后對W矩陣每行非對角元素值根據(jù)索引號進行取反操作，則可以構(gòu)建Laplacian矩陣。

Laplacian矩陣L正規(guī)化過程的矩陣連乘復(fù)雜度很高，因此，根據(jù)對角矩陣右乘某矩陣的操作等價于將對角線位置的非零元素與該矩陣相應(yīng)的行向量相乘，將式(2)中的矩陣連乘以標量乘矩陣的方式進行并行優(yōu)化，其過程如下。

首先，根據(jù)式(2)計算D-1/2后，將其對角元素值以數(shù)組A(D-1/2)的形式發(fā)送到分布式節(jié)點中，在分布式節(jié)點內(nèi)分D-1/2×L和L′×D-1/2兩步完成L的正則化。

D-1/2×L優(yōu)化：如圖3所示，各節(jié)點按其L行號提取A(D-1/2)中對應(yīng)的元素值進行相乘，各節(jié)點并行進行可快速得到中間結(jié)果L′=D-1/2×L。

圖3 構(gòu)建Lnorm的中間過程示意Fig. 3 Schematic diagram of intermediate process of constructing Lnorm

L′×D-1/2優(yōu)化：如圖4所示，其過程與圖3相似，節(jié)點并行地以其獲得的L′的行號提取Arr(D-1/2)中對應(yīng)的對角元素值，并進行相乘，則得到L的正規(guī)化矩陣Lnorm=L′×D1/2。

圖4 構(gòu)建Lnorm并行化過程示意圖Fig. 4 Schematic diagram of parallelization process of constructing Lnorm

1.4 近似特征向量計算并行化

理想情況下，L矩陣中對角零子矩陣會以塊形式存在，相應(yīng)的L特征分解后得到k個零特征值[9]，其對應(yīng)的特征向量組成的矩陣V將具有明顯的非零元分布，此時可以使用經(jīng)典聚類算法將特征向量矩陣V聚類。但實際應(yīng)用中，k個最小特征向量對就的特征向量的矩陣形式通常為V′=VQ，式中，Q為某個正交矩陣，則此時的V′無法直接進行聚類，需要對其進行標準化處理，即：

(3)

其中：i=1,2,…,n，j=1,2,…,n。由于Q為正交的，因而標準化后的矩陣U={Ui, j}在高維空間可形成相互正交的k個簇，從而保證標準化處理后矩陣U的可聚性。

實際應(yīng)用中，為加速近似特征向量的求解，根據(jù)拉普拉斯矩陣L=I-D-1/2SD1/2，先計算矩陣S′=D-1/2SD1/2的前k個最大特征值對應(yīng)的特征向量，然后對特征向量組成的矩陣進行式(3)標準化，以保證矩陣的正常聚類，最后通過k-means算法對標準化矩陣進行聚類，則得到的k個特征向量與直接計算L矩陣的最小特征值對應(yīng)向量是等價的[6]。

對于矩陣S′最大特征值對應(yīng)的特征向量的計算，設(shè)以向量形式表示的目標函數(shù)為：

J=max tr(YT(-S′)Y);YTDY=I

(4)

則根據(jù)文獻[15]中方法，可將式(4)通過拉格朗日乘子轉(zhuǎn)化為迭代形式的計算式，即：

vi+1=SInv′vi

(5)

其中，SInv′為矩陣S取反，則根據(jù)式(5)可以通過迭代方式近似計算S′的前k個特征向量，進而得到拉普拉斯矩陣的近似特征向量。

1.5 改進并行譜聚類計算流程

改進并行化譜聚類算法對輸入的大規(guī)模集數(shù)據(jù)首先進行分塊并分配到各節(jié)點通過單向循環(huán)迭代計算相似矩陣，并進行t稀疏化，然后對稀疏存儲的相似矩陣通過位置替換和矩陣矢量乘計算和正則化Laplacian矩陣，最后將正則化Laplacian矩陣表示為圖形式，通過消息傳遞并行迭代計算近似特征向量和k-mean聚類實現(xiàn)最終大規(guī)模譜聚類，整個算法的計算流程如圖5所示。

圖5 本文改進譜聚類算法流程Fig. 5 Flowchart of the proposed improved spectral clustering algorithm

2 算法性能實驗驗證

本章從聚類性能、運行效率和數(shù)據(jù)集可擴展性三個方面對本文提出的算法(記為ApEigSC)的性能進行測試，實驗用計算機群由1個主控節(jié)點和8個分布式節(jié)點組成，CPU為Intel Xeon 2.10 GHz，總內(nèi)存192 GB，Spark版本為V2.0.1，MPI版本為開源V1.8.8，實驗數(shù)據(jù)如表1所示。

表1 實驗所用的數(shù)據(jù)集 Tab. 1 Datasets used in experiment

以精確特征向量計算的本文算法(簡記為EigSC)、基于Spark框架的k-means并行聚類(記為SpK-means)[12]及PIC算法(記為SpPic)[9]進行實驗比較，以歸一化互信息(Normalized Mutual Information, NMI)作為性能評價指標。

(6)

其中：X、X′待計算互信息的兩個向量，I(X,X′)為其互信息。

2.1 聚類效果比較實驗

為測試算法的聚類效果，實驗選取不同類別數(shù)的新聞集NG2(類別數(shù)2)、NG10(類別數(shù)10)及NG20(類別數(shù)20)為數(shù)據(jù)，實驗中對各實驗算法進行20次測試實驗，其NMI結(jié)果的平均值如表2所示。

從表2實驗結(jié)果中可以看出：EigSC算法采用ScaLAPCK線性庫進行精確特征向量計算，在各實驗數(shù)據(jù)集上都取得最好的聚類效果性能；ApEigSC方法采用近似計算求解特征向量，其聚類性能有稍許下降，但仍比SpK-means和SpPic算法的聚類效果有明顯的性能優(yōu)勢。實驗結(jié)果一方面驗證了ApEigSC算法的并行優(yōu)化算法對提高大規(guī)模譜聚類性能是有效的；另一方面也說明近似特征向量相比精確的特征向量計算，其聚類性能損失不大，但結(jié)合后面運行時間比較實驗結(jié)果可知，近似特征矩陣可以明顯提升譜聚類在大規(guī)模聚類時的運算效率。

表2 稀疏化后的NMI實驗結(jié)果 Tab. 2 NMI experimental results after sparsification

2.2 特征向量求解時間實驗

從KDD數(shù)據(jù)集中抽取不同數(shù)量的樣本數(shù)據(jù)，并存儲于HDFS中。在數(shù)據(jù)集上以不同的特征規(guī)模，分析ApEigSC算法的近似特征向量運算時間，并與EigSC算法中的精確特征向量計算及ArPack算法的特征向量計算方法進行對比，結(jié)果如圖6所示。

圖6 運行時間隨特征規(guī)模變化曲線Fig. 6 Running time varies with feature scale

從實驗結(jié)果可見，各算法的特征向量的運算時間隨著特征求解規(guī)模增加出現(xiàn)不同速度的增長：ApEigSC算法的運算時間增長最為緩慢，性能最優(yōu)，反映出特征向量并行近似計算的運行時間優(yōu)勢；EigSC算法呈現(xiàn)一定的時間增長，但增長緩慢且近似線性增加，主要因為特征規(guī)模的增加使得EigSC算法需要更多的迭代完成收斂，但迭代次數(shù)增加帶來總運行時間的近似線性增長；ArPack算法的高復(fù)雜度單機計算模式隨特征規(guī)模的增長，運行時間呈現(xiàn)指數(shù)增長。

2.3 算法可擴展性實驗

以KDD數(shù)據(jù)集生成不同樣本規(guī)模的實驗數(shù)據(jù)集，分析各算法的運行時間，每組數(shù)據(jù)進行20次實驗，取結(jié)果的平均值，實驗結(jié)果如圖7所示。

從圖7可以看出，4種算法在不同規(guī)模數(shù)據(jù)集上的運行時間都在增長，但都呈現(xiàn)線性增長，表現(xiàn)出較好的可擴展性，ApEigSC和SpPic算法對不同規(guī)模的數(shù)據(jù)集，算法的運行時間變化幅度不大，說明其數(shù)據(jù)可擴展性更優(yōu)，這主要是因為這兩種算法通過迭代計算近似特征向量，在并行化基礎(chǔ)上迭代次數(shù)越多，近似特征向量計算的運行效率優(yōu)勢越明顯，因而算法的聚類時間增加較緩慢，而ApEigSC算法的可擴展性更優(yōu)。SpK-means算法的時間開銷主要集中在距離計算上，在聚類數(shù)一定時其聚類時間受樣本規(guī)模的影響，EigSC具有精確的特征向量計算，但隨著樣本規(guī)模的增加，其樣本間精確的相似計算時間開銷也隨之增大，因而運行時間受樣本影響最大。

圖7 樣本規(guī)模增加時算法運行總時間Fig. 7 Total running time of algorithm runs as sample size increases

綜合所有實驗結(jié)果可以看出，文中算法通過并行優(yōu)化和近似特征向量求解，在取得與精確特征向量計算方法相近的聚類效果基礎(chǔ)上，進一步減少了算法的聚類時間開銷，在大規(guī)模數(shù)據(jù)集上具有較好的擴展性。

3 結(jié)語

針對并行譜聚類在大規(guī)模集上難以避免的計算耗時或無法聚類等性能瓶頸，基于Spark技術(shù)，提出了適用于大規(guī)模集的并行譜聚類優(yōu)化算法，算法通過相似矩陣的單向循環(huán)并行計算、Laplacian矩陣的并行構(gòu)建及正則化以及近似特征向量的使用，在獲得較好的譜聚類性能基礎(chǔ)上，有效減少了算法的計算量和存儲空間需求，提高了算法的運行效率。實驗結(jié)果驗證了所提算法在大規(guī)模數(shù)據(jù)集下良好的聚類性能和可擴展性。

在后續(xù)工作中，將繼續(xù)研究近似特征向量提取后，k-means算法對近似特征向量聚類過程的并行優(yōu)化，以進一步實現(xiàn)大規(guī)模譜聚類算法的并行優(yōu)化性能。