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

郝笑弘，尹青山

（1.山西水利職業技術學院，山西 太原030032；2.吉林大學軟件學院，吉林 長春130012）

1 引言

計算機技術的快速發展和網絡帶寬的不斷擴展，海量多樣化數據成為當前數據處理的常態，面對海量數據，如何挖掘出最有價值信息成為研究的熱點，聚類作為數據挖掘的重要手段和研究方向，通過廣泛的探索性分析和數據內在聯系識別，達到相似特征數據的歸類，從而提示數據的隱藏價值［1］。譜聚類以非線性核距離作為聚類相似判斷依據，適用于非凸等任意形狀的數據，且能夠取得全局最優解［2］。但傳統譜聚類計算代價與存儲開銷阻礙了其在大規模數據集中的應用，且數據規模越大，這種性能瓶頸越明顯。

為此，文獻［3］兼顧視角內劃分質量與視角間協同，通過多代表點策略和多視角代表性保持對多樣化大規模數據集進行一致性約束，并通過加權系數最大化與拉格朗日乘子實現數據的譜聚類，相比于傳統譜聚類，改進算法在聚類時間和存儲優化上具有一定的優勢；文獻［4］選用非負矩陣分解對多視角數據進行處理，以獲得各視角的潛在特征矩陣，然后引入正交約束以優化局部特征，通過數據加權調整缺失數據的聚類貢獻影響，最后通過分塊處理以緩解大規模數據的內存需求；文獻［5］以Nystr?m近似采樣降低大規模數據的相似度計算復雜度，有利于聚類效率的提高，通過對采樣過程的自適應優化要，進一步提高譜聚類在大規模數據集上的聚類效果；文獻［6］將樣本映射至高維函數核空間，通過領域信息建立系統加權濾波器和二維直方圖，以此獲得核空間的快速迭代，算法對大規模數據和高斯噪聲具有較好的適應性和魯棒性；

并行框架的廣泛應用為譜聚類在大規模集上的使用提供了新的思路，文獻［7］通過自適應格網劃分與加權以及信息熵提高密度聚類的準確性，然后結合MapReduce框架對改進后的密度聚類時行局部簇并行優化，從而加快局部簇的生成與合并，有效提高算法的處理速率；文獻［8］基于MapReduce的并行計算框架通過分片局部簇計算和全局簇增量合并對DBSCAN算法進行并行優化，以提高DBSCAN算法對大規模數據集的適用性，但算法的數據分塊效率不高，且局部簇合并較為復雜；文獻［9］改進Spark框架中占用內存較大的top操作，并通過自底向上的聚類策略提高層次聚類算法的區域性，提出基于Spark框架的并行圖過濾聚類，其聚類效果優于其他相關并行策略；文獻［10］以Hadoop和Spark雙并行框架對密度聚類進行降低計算復雜度優化，并給出在兩種并行框架下的數據分塊策略，但算法的簇合并法效率不高［11］。

為引，在已有研究基礎上，提出基于并行框架和Nystrom采樣相結合的改進譜聚類算法，算法在自適應相似矩陣計算基礎上，通過數據分塊和單向節點并行，提高算法相似矩陣的計算效率，通過Nystrom加權抽樣逼近，減少拉普拉斯矩陣特征向量的計算復雜度，最后通過KD樹結構進一步減少k-mean聚類過程的距離計算，從而降低了傳統譜聚類的計算復雜度，提高了聚類效率，仿真實驗驗證了算法的有效性。

2 譜聚類并行優化

2.1 譜聚類算法流程

譜聚類算法采用無向圖思想，將數據集中的數據視為無向圖中的節點，而數據之間的相似度，則表示為節點間的權重，然后根據權重規則將無向圖劃分為不同的子圖，通過子圖內的邊的高權重與子圖間邊的低權重優化實現數據的聚類分析。譜聚類最優劃分求解通常依賴拉普拉斯矩陣，其流程為：

（1）輸入初始類數k及相似矩陣S∈Rn×n，然后建立數據集的相似圖，計算邊的權重矩陣W；

（2）計算圖的拉普拉斯矩陣L，并給出其前k個特征向量組成的矩陣對V的每一行時行規范化處理，使其范數值為1，得到矩陣U=[uij]，其中，

（3）設yi∈Rk對應矩陣U的i列，i=1,2,…,n，則通過k-means算法對yi∈Rk進行聚類，聚類結果為C1,C2,…,Ck。

2.2 自適應相似矩陣并行計算

在進行無向圖劃分時，需要先通過高斯核函數度量數據之間距離，進而形成數據的相似性連接圖，相似圖對應一個相似矩陣，通常數據挖掘需要處理多樣化數據，因而相似圖通常采用全連接圖，這樣由數據距離值計算無向圖的邊權值為：

式中：Aij-兩數據xi和xj之間的連接邊權值；σ-數據鄰域范圍控制的尺度參數，用以調整兩數據之間的相異度；d(xi,xj)-兩個數據xi和xj之間距離。

根據文獻中self-Tunin聚類思想［11］可得到數據xi到xj的相異度xj到xi的相異度，則可以得到相似函數的參數自適應形式，即

式中：σi-當前數據xi與其鄰域的距離均值，用于描述當前數據的鄰域密度，σ-σi均值數據密度差值，σmax-的最大值權值因子，用以調整高斯核函數。

對于大規模數據集，上述自適應相似矩陣的計算量巨大，為此基于并行框架，在數據分塊基礎上，將不同數據塊分發到框架的并行計算節點上，并行計算各節點內數據的相似度，然后根據框架節點序號，依次計算兩節點內數據之間的相似度值，為減少數據重復計算，當前序號下的節點內數據，僅與比其序號值大的節點內數據計算相似度值。

由相似矩陣A={Aij}可以構建正則化Laplacian矩陣L為：

式中：D={Di,j}-對角矩陣，其計算式為：

可以證明，對于Ai,j≥0，其L矩陣對稱且顯半正定，這說明，當其局部聚類與其他局部聚類中的樣本不相關時，L矩陣中將存在非零塊對角陣，此時L的前k個最小特征值對應的特征向量組成矩陣V，再對V進行k-means等聚類，即可得到最終的譜聚類。

L矩陣的并行化計算過程，可以通過L′=D-1/2×L和L′×D-1/2兩個并行化過程實現，L′=D-1/2×L并行計算過程如圖1所示，L′×D-1/2采用相似的并行計算過程。

圖1 矩陣L的并行化計算過程Fig.1 Parallel Computing Process of Matrix L

2.3 近似特征向量并行計算

針對大規模數據集，傳統譜聚類采用的前k個特征向量組成的降維矩陣仍需要巨大的計算量，為此，采用Nystr?m采樣方法進行特征向量的低秩逼近。

設數據集規模為n，隨機抽樣點數為m，則有( )n-m個數據為未抽樣數據，則數據集的相似矩陣可表示為：

式中：A-抽樣數據間的相似矩陣；B-抽樣數據與其他數據間的相似矩陣；C-未被抽樣的數據間的相似矩陣，由于式（6）中未被抽樣數據的數據量遠大于抽樣數據，Nystr?m算法采用A和E來近似表示K：

Nystrom采樣方法通過矩陣的低秩逼近，僅需計算少量采樣數據進行相關計算，避免了大規模數據集中未被采樣數據的使用，從面極大程度降低算法的復雜度。但傳統采樣方法未充分考慮不同抽樣數據的重要性，使得采樣數據對最終結果的貢獻度難以保證，為此采用加權采樣形式，其加權核矩陣為：

設矩陣L的特征分解表示為L=?λ?T。式中：λ-特征值組成的對角陣，由A=?AλA?AT可得：

根據式（9）通過低秩逼近計算矩陣L的特征值及其對應的特征向量，即：

近似特征向量的計算流程，如圖2所示。

圖2 近似特征向量計算流程Fig.2 Similar Eigenvector Calculation Process

2.4 K-means并行計算

KD樹通過查詢當時節點最近鄰的數據點進行距離比較，從而避免數據點之間的距離計算，實現快速節點匹配，為此，在譜聚類的k-means算法對特征向量進行聚類過程中，引入KD樹作為特征矩陣的數據存儲結構，并建立聚類中心KD結構，然后利用KD樹自有的最近鄰查詢實現數據點與其距離最小的聚類中心點的歸類，從而有效解決數據距離迭代計算的冗余，其過程如圖3所示。

圖3 基于KD樹結構的快速k-means計算流程Fig.3 Fast K-means Calculation Process based on KD Tree Structure

3 算法性能實驗驗證

為驗證文中算法在大規模數據集聚類方面的有效性，實驗構建計算機集群，以進行并行分布式計算，選取UCI庫中的Waveform集、Pendigits集和Forest集三個數據集作為實驗數據集，并將數據集分別擴展為大規模數據集，以聚類準確率和標準化互信息作為聚類性能評價指標，實驗中并行框架采用Spark V2.3.0，開源MPI V1.8。

3.1 算法聚類性能比較實驗

為測試文中算法（簡記為ImpSC，采樣比例為10%）的聚類性能，實驗選取原始譜聚類（簡記為TrSC）、并行k-means算法（簡記為Pkmeans）、隨機抽樣譜聚類（簡記為RadSC）和特征自適應選擇聚類算法（簡記為AflC）作為實驗比較算法，實驗中在每個實驗數據集上對進行20次實驗，取實驗結果的平均值，結果如表1所示。

表1 各算法的聚類性能比較結果（%）Tab.1 Performance Comparison of each Algorithm（%）

從表1實驗結果中可以看出，算法在各個大規模數據集上都取得較好的聚類準確率，其聚類結果與原始譜聚類相近，但略有優勢，主要因為相似矩陣的參數自適應設置，使其更適于不同數據集的數據特征，從而驗證了算法的聚類性能和相似矩陣自適應計算的有效性。

3.2 算法計算復雜性實驗

加速比是檢驗改進算法的并行化能力的重要指標，為此，將Waveform集的數據規模人工擴充0.6G、1G、2G和3G，然后在不同節點下分析算法的加速比，實驗結果如圖4所示，圖中實驗結果為多次實驗結果的平均值。從實驗結果可以看出，當數據規模在0.6G時，由于數據規模較小，隨著節點數增加，算法在處理數據分塊和數據之間的通信方面占用資源較大，因而算法的加速比不高，甚至節點較多時，出現一定的下降，但隨著數據規模增大，算法的加速比快速增大，主要因為數據規模越大，數據分塊及節點通信占用的次源比重變小，而算法的并行運算優勢凸顯，從而驗證改進算法更適于大規模數據集應用。

圖4 不同節點數下的算法加速比Fig.4 Speedup Under Different Number of Nodes

4 總結

為解決傳統譜聚類算法在應用于大規模數據上時，復雜度較高且資源占用較大，導致算法聚類效果不好甚至無法聚類的問題，提出基于并行框架和Nystrom采樣相結合的改進譜聚類算法，算法在自適應相似矩陣計算基礎上，通過數據分塊和單向節點并行，提高算法相似矩陣的計算效率，通過Nystrom加權抽樣逼近，減少拉普拉斯矩陣特征向量的計算復雜度，最后通過KD樹結構進一步減少k-mean聚類過程的距離計算，從而降低傳統譜聚類的計算復雜度，提高了聚類效率，仿真實驗驗證了算法的有效性。