郝笑弘，尹青山

（1.山西水利職業(yè)技術(shù)學(xué)院，山西 太原030032；2.吉林大學(xué)軟件學(xué)院，吉林 長春130012）

1 引言

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

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

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

為引，在已有研究基礎(chǔ)上，提出基于并行框架和Nystrom采樣相結(jié)合的改進(jìn)譜聚類算法，算法在自適應(yīng)相似矩陣計(jì)算基礎(chǔ)上，通過數(shù)據(jù)分塊和單向節(jié)點(diǎn)并行，提高算法相似矩陣的計(jì)算效率，通過Nystrom加權(quán)抽樣逼近，減少拉普拉斯矩陣特征向量的計(jì)算復(fù)雜度，最后通過KD樹結(jié)構(gòu)進(jìn)一步減少k-mean聚類過程的距離計(jì)算，從而降低了傳統(tǒng)譜聚類的計(jì)算復(fù)雜度，提高了聚類效率，仿真實(shí)驗(yàn)驗(yàn)證了算法的有效性。

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

2.1 譜聚類算法流程

譜聚類算法采用無向圖思想，將數(shù)據(jù)集中的數(shù)據(jù)視為無向圖中的節(jié)點(diǎn)，而數(shù)據(jù)之間的相似度，則表示為節(jié)點(diǎn)間的權(quán)重，然后根據(jù)權(quán)重規(guī)則將無向圖劃分為不同的子圖，通過子圖內(nèi)的邊的高權(quán)重與子圖間邊的低權(quán)重優(yōu)化實(shí)現(xiàn)數(shù)據(jù)的聚類分析。譜聚類最優(yōu)劃分求解通常依賴?yán)绽咕仃?，其流程為?/p>

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

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

（3）設(shè)yi∈Rk對應(yīng)矩陣U的i列，i=1,2,…,n，則通過k-means算法對yi∈Rk進(jìn)行聚類，聚類結(jié)果為C1,C2,…,Ck。

2.2 自適應(yīng)相似矩陣并行計(jì)算

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

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

根據(jù)文獻(xiàn)中self-Tunin聚類思想［11］可得到數(shù)據(jù)xi到xj的相異度xj到xi的相異度，則可以得到相似函數(shù)的參數(shù)自適應(yīng)形式，即

式中：σi-當(dāng)前數(shù)據(jù)xi與其鄰域的距離均值，用于描述當(dāng)前數(shù)據(jù)的鄰域密度，σ-σi均值數(shù)據(jù)密度差值，σmax-的最大值權(quán)值因子，用以調(diào)整高斯核函數(shù)。

對于大規(guī)模數(shù)據(jù)集，上述自適應(yīng)相似矩陣的計(jì)算量巨大，為此基于并行框架，在數(shù)據(jù)分塊基礎(chǔ)上，將不同數(shù)據(jù)塊分發(fā)到框架的并行計(jì)算節(jié)點(diǎn)上，并行計(jì)算各節(jié)點(diǎn)內(nèi)數(shù)據(jù)的相似度，然后根據(jù)框架節(jié)點(diǎn)序號(hào)，依次計(jì)算兩節(jié)點(diǎn)內(nèi)數(shù)據(jù)之間的相似度值，為減少數(shù)據(jù)重復(fù)計(jì)算，當(dāng)前序號(hào)下的節(jié)點(diǎn)內(nèi)數(shù)據(jù)，僅與比其序號(hào)值大的節(jié)點(diǎn)內(nèi)數(shù)據(jù)計(jì)算相似度值。

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

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

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

L矩陣的并行化計(jì)算過程，可以通過L′=D-1/2×L和L′×D-1/2兩個(gè)并行化過程實(shí)現(xiàn)，L′=D-1/2×L并行計(jì)算過程如圖1所示，L′×D-1/2采用相似的并行計(jì)算過程。

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

2.3 近似特征向量并行計(jì)算

針對大規(guī)模數(shù)據(jù)集，傳統(tǒng)譜聚類采用的前k個(gè)特征向量組成的降維矩陣仍需要巨大的計(jì)算量，為此，采用Nystr?m采樣方法進(jìn)行特征向量的低秩逼近。

設(shè)數(shù)據(jù)集規(guī)模為n，隨機(jī)抽樣點(diǎn)數(shù)為m，則有( )n-m個(gè)數(shù)據(jù)為未抽樣數(shù)據(jù)，則數(shù)據(jù)集的相似矩陣可表示為：

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

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

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

根據(jù)式（9）通過低秩逼近計(jì)算矩陣L的特征值及其對應(yīng)的特征向量，即：

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

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

2.4 K-means并行計(jì)算

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

圖3 基于KD樹結(jié)構(gòu)的快速k-means計(jì)算流程Fig.3 Fast K-means Calculation Process based on KD Tree Structure

3 算法性能實(shí)驗(yàn)驗(yàn)證

為驗(yàn)證文中算法在大規(guī)模數(shù)據(jù)集聚類方面的有效性，實(shí)驗(yàn)構(gòu)建計(jì)算機(jī)集群，以進(jìn)行并行分布式計(jì)算，選取UCI庫中的Waveform集、Pendigits集和Forest集三個(gè)數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)集，并將數(shù)據(jù)集分別擴(kuò)展為大規(guī)模數(shù)據(jù)集，以聚類準(zhǔn)確率和標(biāo)準(zhǔn)化互信息作為聚類性能評價(jià)指標(biāo)，實(shí)驗(yàn)中并行框架采用Spark V2.3.0，開源MPI V1.8。

3.1 算法聚類性能比較實(shí)驗(yàn)

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

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

從表1實(shí)驗(yàn)結(jié)果中可以看出，算法在各個(gè)大規(guī)模數(shù)據(jù)集上都取得較好的聚類準(zhǔn)確率，其聚類結(jié)果與原始譜聚類相近，但略有優(yōu)勢，主要因?yàn)橄嗨凭仃嚨膮?shù)自適應(yīng)設(shè)置，使其更適于不同數(shù)據(jù)集的數(shù)據(jù)特征，從而驗(yàn)證了算法的聚類性能和相似矩陣自適應(yīng)計(jì)算的有效性。

3.2 算法計(jì)算復(fù)雜性實(shí)驗(yàn)

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

圖4 不同節(jié)點(diǎn)數(shù)下的算法加速比Fig.4 Speedup Under Different Number of Nodes

4 總結(jié)

為解決傳統(tǒng)譜聚類算法在應(yīng)用于大規(guī)模數(shù)據(jù)上時(shí)，復(fù)雜度較高且資源占用較大，導(dǎo)致算法聚類效果不好甚至無法聚類的問題，提出基于并行框架和Nystrom采樣相結(jié)合的改進(jìn)譜聚類算法，算法在自適應(yīng)相似矩陣計(jì)算基礎(chǔ)上，通過數(shù)據(jù)分塊和單向節(jié)點(diǎn)并行，提高算法相似矩陣的計(jì)算效率，通過Nystrom加權(quán)抽樣逼近，減少拉普拉斯矩陣特征向量的計(jì)算復(fù)雜度，最后通過KD樹結(jié)構(gòu)進(jìn)一步減少k-mean聚類過程的距離計(jì)算，從而降低傳統(tǒng)譜聚類的計(jì)算復(fù)雜度，提高了聚類效率，仿真實(shí)驗(yàn)驗(yàn)證了算法的有效性。