胡 健,劉祥敏,毛伊敏+,陳志剛

(1.江西理工大學 信息工程學院,江西 贛州 341000;2.贛南科技學院 信息工程學院,江西 贛州 341000;3.中南大學 計算機學院,湖南 長沙 410000)

1 問題的提出

聚類分析[1]作為一種無監(jiān)督學習,在數(shù)據(jù)挖掘和機器學習領(lǐng)域中扮演著至關(guān)重要的角色,它根據(jù)數(shù)據(jù)對象的特征對數(shù)據(jù)集進行聚類,使類內(nèi)相似度最大化、類間相似性最小化,從而發(fā)現(xiàn)對象間的內(nèi)在聯(lián)系,獲取蘊藏在數(shù)據(jù)背后的價值。然而,隨著大數(shù)據(jù)時代的來臨,爆炸式增長的數(shù)據(jù)使得傳統(tǒng)聚類算法的計算性能瓶頸愈加突出,這嚴重制約了聚類算法在大數(shù)據(jù)集上的應(yīng)用。因此,如何降低大數(shù)據(jù)環(huán)境下聚類算法的計算開銷成為了一個具有挑戰(zhàn)性的問題。

近年來,隨著MapReduce并行計算模型以及Hadoop、Spark[2-4]等大數(shù)據(jù)分布式并行計算框架的快速發(fā)展,聚類算法的并行化研究逐漸得到了廣泛的關(guān)注,相關(guān)研究如表1所示。SREEDHAR等[5]設(shè)計了基于MapReduce框架的并行k-means算法KM-I2C,根據(jù)聚類間和聚類內(nèi)相似性將不同聚類劃分為子聚類,一定程度上提高了聚類精度,但未能合理地調(diào)度map和reduce作業(yè)從而容易出現(xiàn)節(jié)點負載不均衡。針對此問題,文獻[6]引入池塘采樣方法以等概率采樣輸出中間數(shù)據(jù),然后采用第一自適應(yīng)調(diào)度,將中間數(shù)據(jù)合理地放入節(jié)點,有效地解決了負載不均衡的問題。但該算法對質(zhì)心的初始化可能存在局部最優(yōu)問題。為此,文獻[7]先初始化隨機抽樣,然后并行化距離計算過程,最后并行執(zhí)行聚類分析,該算法處理大規(guī)模數(shù)據(jù)時具有良好的收斂性和較高的聚類精度,但在處理高維數(shù)據(jù)時仍然存在問題,且聚類精度有待提升。此外,胡健等[8]提出了基于MapReduce和加權(quán)網(wǎng)格信息熵的DBWGIE-MR算法,通過構(gòu)建加權(quán)網(wǎng)格加強網(wǎng)格間的關(guān)聯(lián)性,從而提高聚類精度;ATILAGN等[9]提出了FN-DBSCAN算法,該算法首先計算成對距離,然后計算模糊鄰域,并通過向隊列中添加核心點的鄰居來迭代得到局部簇,最后合并得到最終聚類結(jié)果,這些過程都是并行的,在保證聚類精度的同時減少了運行時間。盡管以上算法都取得了不錯的效果,但在處理高維數(shù)據(jù)時均易陷入“維數(shù)災(zāi)難”,從而導(dǎo)致巨大的計算開銷。

表1 相關(guān)算法比較分析

譜聚類算法[10-11]作為一類新穎的聚類算法,能夠?qū)Ω呔S、任意形狀的樣本空間進行聚類,已被證明在非凸樣本空間中比傳統(tǒng)的聚類算法(如k-means)更加有效[12],并在圖像分割[13-15]、推薦系統(tǒng)[16]、社區(qū)發(fā)現(xiàn)[17]、計算機視覺[18-20]等領(lǐng)域得到了廣泛的應(yīng)用。由于譜聚類算法的諸多優(yōu)點,一些學者開始研究譜聚類算法的并行化。CHEN等[21]比較了傳統(tǒng)的相似矩陣稀疏化方法與Nystrom近似方法,提出了并行潽聚類(Parallel Spectral Clustering,PSC)算法,該算法首先基于MapReduce構(gòu)造稀疏相似度矩陣,將數(shù)據(jù)實例分發(fā)到分布式節(jié)點上,在每個節(jié)點上使用最小磁盤I/O的方式計算本地數(shù)據(jù)和整個集合之間的相似性;然后將特征向量矩陣存儲在分布式節(jié)點上,并行求解特征向量矩陣和k-means聚類。PSC算法實現(xiàn)了譜聚類在分布式系統(tǒng)上的并行化,在大數(shù)據(jù)集上實現(xiàn)了良好的加速。文獻[22]將MapReduce與譜聚類算法結(jié)合,實現(xiàn)了并行譜聚類算法(Parallel Spectral Clustering Algorithm, PSCA),該算法在節(jié)點分配數(shù)據(jù)時,將索引i和索引n-i+1的數(shù)據(jù)點放在一起計算相似值,在建立稀疏相似矩陣時可以保證每對數(shù)據(jù)點之間的相似值只計算一次;在計算特征向量時,將Laplacian矩陣存儲在Hadoop文件系統(tǒng)中,通過分布式Lanzos操作得到特征向量;最后利用并行k-means聚類處理特征向量的轉(zhuǎn)置矩陣,得到聚類結(jié)果。在此研究基礎(chǔ)上,文獻[23]在實現(xiàn)t近鄰稀疏化相似度矩陣時引入KD樹(k-dimension tree)索引技術(shù),加快搜索近鄰范圍,并通過實驗證明提升了算法性能。但是,以上算法存在4個問題:①分配數(shù)據(jù)時,不管是采用MapReduce的默認分區(qū)策略還是將索引i和索引n-i+1的數(shù)據(jù)放在一起,對數(shù)據(jù)的分配具有隨機性,未能根據(jù)數(shù)據(jù)的分布特性采用合理的數(shù)據(jù)劃分方法,節(jié)點執(zhí)行任務(wù)時容易產(chǎn)生負載不均衡的問題;②在構(gòu)建稀疏矩陣過程中,盡管用KD樹索引技術(shù)在一定程度上可以減少計算,但是KD樹只適用于低維數(shù)據(jù),在高維數(shù)據(jù)上可能需要大量的時間來回溯樹和最優(yōu)解,依然會產(chǎn)生大量的冗余計算從而導(dǎo)致搜索性能下降;③在正規(guī)化Laplacian矩陣時,在各節(jié)點上分布式計算矩陣相乘操作,時間開銷大;④用k-means算法進行最終聚類時,僅是簡單地并行化,沒有解決隨機選取初始聚類中心引起的初始中心敏感問題,從而可能導(dǎo)致聚類效果不夠穩(wěn)定。

針對以上問題,本文提出基于KD樹和混沌蜉蝣優(yōu)化算法的并行譜聚類算法(Parallel Spectral Clustering algorithm using KD-tree and chaotic Mayfly Optimization algorithm, PSC-MO),主要工作可歸納為以下4點:

(1)提出了基于采樣的KD-tree數(shù)據(jù)分區(qū)策略(Data Partitioning Strategy, DPS)劃分數(shù)據(jù)以獲得均勻的分區(qū),實現(xiàn)了各節(jié)點的負載均衡;

(2)采用KD樹索引實現(xiàn)t近鄰稀疏化,提出了優(yōu)化的分區(qū)分配策略(Optimized Partition Assignments strategy, OPA)和基于三角不等式的KD樹剪枝策略以進行跨分區(qū)的t近鄰搜索,避免了冗余計算,從而提高了搜索效率;

(3)實現(xiàn)了Laplacian矩陣構(gòu)建與正規(guī)化過程的并行化,并提出正規(guī)化定理,通過元素對應(yīng)相乘的方式代替矩陣相乘以優(yōu)化Laplacian矩陣正規(guī)化過程,進一步減少了時間開銷;

(4)設(shè)計了混沌蜉蝣優(yōu)化算法(Chaotic Mayfly Optimization Algorithm, CMO),用于獲取最佳的初始簇中心位置,有效解決了算法對初始簇中心敏感的問題。

2 相關(guān)算法及概念介紹

2.1 KD樹

KD樹是一種對k維空間數(shù)據(jù)進行組織和存儲的樹形數(shù)據(jù)結(jié)構(gòu),用垂直于坐標軸的超平面把一個k維空間劃分成多個不相交的k維超矩形區(qū)域,由BENTLEY等[24]于1975年首次提出。傳統(tǒng)的KD樹常用于近鄰搜索中,在低維數(shù)據(jù)上非常有效,但在高維數(shù)據(jù)上表現(xiàn)差強人意。于是,研究人員發(fā)展了許多KD樹的變體,如PCA(principal component analysis)樹[25]、RP(random projection)樹[26]和三進制投影樹[27]。此外,PROCIPOUC等[28]提出Bkd-tree用于索引大型多維點數(shù)據(jù)集;ADAMS等[29]設(shè)計了一種能用于高維空間的高斯KD樹,可支持快速的Monte Carlo采樣查詢;WU等[30]提出隨機投影KD樹,將高維數(shù)據(jù)點投影到低維空間;文獻[31]提出一種隨機KD樹,通過構(gòu)建多個并行搜索的隨機KD樹進行近似最近鄰搜索?；赗P樹搜索精度高的優(yōu)點,RAM等[32]提出一種新的KD樹用于近鄰搜索。

2.2 蜉蝣算法

蜉蝣算法(Mayfly Algorithm, MA)是2020年由ZERVOUDAKIS等[33]提出的一種模擬蜉蝣的社會行為的優(yōu)化算法,該算法結(jié)合了群智能算法與進化算法的主要優(yōu)點,將最優(yōu)的雄性個體與最優(yōu)的雌性個體交配得到最優(yōu)的子代。MA算法主要包括雄性蜉蝣的運動、雌性蜉蝣的運動、蜉蝣交配。

(1)

更新雄性蜉蝣的速度為:

(2)

其中:g為引力系數(shù);a1、a2為正吸引系數(shù);β為能見度系數(shù);rp、rg為蜉蝣當前位置與歷史最佳位置和最佳蜉蝣位置的笛卡爾距離;xhi為蜉蝣歷史訪問過的最佳位置;xg為種群中最佳雄性蜉蝣位置;d為舞蹈系數(shù);r1為[-1,1]均勻分布的隨機數(shù)。笛卡爾距離計算公式為:

(3)

(2)雌性蜉蝣的運動 假設(shè)a3為正吸引系數(shù),β為能見度系數(shù),rmf為雄性與雌性蜉蝣間的笛卡爾距離,fl為隨機飛行系數(shù),r2為[-1,1]均勻分布的隨機數(shù),更新雌性蜉蝣的速度為:

(4)

(3)蜉蝣交配 根據(jù)適應(yīng)度函數(shù)選擇蜉蝣進行兩兩配對,適應(yīng)度最優(yōu)的雄性蜉蝣個體和適應(yīng)度最優(yōu)的雌性蜉蝣個體交配,適應(yīng)度次優(yōu)的雄性蜉蝣個體和適應(yīng)度次優(yōu)的雌性蜉蝣個體交配,以此類推,交配得到兩個子代,其子代為:

(5)

式中:male表示雄性父代;female表示雌性父代;L∈[-1,1]為高斯分布中的隨機數(shù);offspring1和offspring2表示兩個子代,子代的初始速度為0。

2.3 混沌

Sin混沌映射是由正弦三角函數(shù)派生的正弦映射,其映射折疊次數(shù)無限,比Logistic映射具備更佳的混沌特性[34],其映射方程為:

xn+1=S(xn)=μsin(πxn),-1≤xn≤1,
xn≠0,n=0,1,…,N。

(6)

式中:S(xn)表示Sin映射;x為迭代值;μ為控制參數(shù),μ∈[0,1]。

2.4 譜聚類算法

譜聚類算法將聚類問題轉(zhuǎn)化為圖的最優(yōu)切分問題,其本質(zhì)是通過特征分解將原始的高維數(shù)據(jù)空間映射到低維特征向量空間,然后在特征向量空間中對數(shù)據(jù)點進行聚類。NG等[35]提出的經(jīng)典譜聚類的步驟為:

(1)構(gòu)建相似度矩陣W、對角矩陣D,

(7)

(2)計算Laplacian矩陣L并正規(guī)化:

L=D-W,

(8)

(9)

(3)計算矩陣的前k個最小特征向量,構(gòu)成特征向量矩陣Z∈Rn×k;

(4)用k-means算法將數(shù)據(jù)點vi∈Rk(i=1,…,n)聚類。

在文獻[35]的基礎(chǔ)上,研究人員對譜聚類進行了若干研究。為解決傳統(tǒng)譜聚類算法對尺度參數(shù)敏感的問題,ZELNIK-MANOR等[36]提出一種自適應(yīng)的譜聚類方法,根據(jù)其鄰域信息為每個點計算一個自適應(yīng)參數(shù)。LIU等[37]通過局部密度獲取數(shù)據(jù)中的隱式聚類結(jié)構(gòu)特征,并與自適應(yīng)的高斯核函數(shù)相結(jié)合,提出一種基于共享鄰域自適應(yīng)相似度的譜聚類算法;WANG等[38]提出一種基于消息傳遞的譜聚類算法(Spectral Clustering algorithm based on Message Passing,MPSC),利用密度敏感相似度來度量數(shù)據(jù)間的相似度。在流式計算場景下,文獻[39]提出一種流式數(shù)據(jù)相似性計算方法。此外,YANG等[40]中提出一種深度譜聚類學習方法,用相對熵將雙自編碼網(wǎng)絡(luò)和深度譜聚類融合;文獻[41]設(shè)計了normalized min cut問題的連續(xù)松弛,并通過訓練圖神經(jīng)網(wǎng)絡(luò)來進行譜聚類分析。雖然譜聚類算法具有良好的聚類性能,但是處理大規(guī)模數(shù)據(jù)集時,存儲相似度矩陣、求解特征向量存在資源占用瓶頸。為此,一些學者對譜聚類進行了并行化研究[21-23],將數(shù)據(jù)分發(fā)到多個計算節(jié)點進行分布式處理。另外,為避免存儲稠密的相似度矩陣,學者們提出了許多改進算法,主要有兩個改進方向:①稀疏化相似度矩陣,包括設(shè)置閾值和t近鄰兩種,計算后只存儲矩陣中的非零元素;②子矩陣方法,即對相似度矩陣的行或列進行采樣,只計算部分數(shù)據(jù)間的相似性,最經(jīng)典的是FOWLKES等[42]提出的Nystr?m近似算法。

3 PSC-MO算法

PSC-MO算法主要包括4個階段:數(shù)據(jù)分區(qū)、并行構(gòu)建相似度矩陣、并行計算特征向量、并行聚類。

(1)在數(shù)據(jù)分區(qū)階段,提出DPS策略,對原始數(shù)據(jù)執(zhí)行KD樹分區(qū),獲取均勻的數(shù)據(jù)分區(qū)。

(2)在并行構(gòu)建相似度矩陣階段,首先計算分區(qū)內(nèi)部數(shù)據(jù)的t近鄰,然后提出OPA策略和兩個基于三角不等式的剪枝策略,在此基礎(chǔ)上進行跨分區(qū)的t近鄰搜索,最后計算數(shù)據(jù)點與其t近鄰的相似度值,構(gòu)建稀疏相似度矩陣。

(3)在并行計算特征向量階段,提出正規(guī)化定理,通過矩陣對應(yīng)位置元素相乘的方式得到正規(guī)化Laplacian矩陣,求解前k個特征向量構(gòu)成特征向量矩陣并正規(guī)化。

(4)在并行聚類階段,調(diào)用混沌蜉蝣優(yōu)化算法以獲取最優(yōu)的初始簇中心,然后進行k-means聚類,獲取最終聚類結(jié)果。

3.1 數(shù)據(jù)分區(qū)

目前,并行譜聚類算法劃分數(shù)據(jù)時大都采用MapReduce默認的數(shù)據(jù)分區(qū)器,忽略了數(shù)據(jù)間的分布特性,容易產(chǎn)生數(shù)據(jù)傾斜,從而引起節(jié)點負載不均衡。針對這一問題,本文提出基于采樣的KD-tree數(shù)據(jù)分區(qū)策略(DPS),得到Map上的數(shù)據(jù)分區(qū)。該策略包括5個主要步驟:采樣、支撐點選擇、映射、空間劃分和數(shù)據(jù)劃分。

(1)采樣 為降低映射成本,對原始數(shù)據(jù)集D={v1,v2,v3,…,vn}進行隨機采樣,得到采樣數(shù)據(jù)集S(如圖1a中黑點為采樣數(shù)據(jù))。

(2)支撐點選擇 首先從采樣數(shù)據(jù)集S中隨機選出第一個點;接著依次選出后續(xù)的支撐點,每次選擇到近期被選出的兩個點(文獻[43]中已證明以近期選出的兩個點或三個點為基準時選出的支撐點較為理想)距離最大的點,得到候選集,并從候選集中組合出所有的支撐點集合;最后從S中隨機抽取數(shù)據(jù)構(gòu)造評價集,將評價集中的數(shù)據(jù)兩兩組合成數(shù)據(jù)對,選出能排除最多數(shù)據(jù)對的那組支撐點(假設(shè)為q個)即為最優(yōu)的支撐點集合PS={PS1,PS2,…,PSq|q<

(3)映射 提出數(shù)據(jù)映射定理,根據(jù)選定的支撐點將數(shù)據(jù)映射到q維向量空間。如圖1a所示,二維空間q=2,PS={PS1,PS2},對任一數(shù)據(jù)點vi(1≤i≤n),x軸表示vi到PS1的距離d(vi,PS1),y軸表示vi到PS2的距離d(vi,PS2)。

定理1數(shù)據(jù)映射。給定一個支撐點集合PS={PS1,PS2,…,PSq},若vi、vj是PS構(gòu)成的度量空間中的點,其中vi、vj∈v且i≠j,則vi、vj可以映射到同一個q維向量空間且保留原始數(shù)據(jù)間的相似性。

證明根據(jù)三角不等式d(vi,vj)≥max{|d(vi,PSu)-d(vj,PSu)||PSu∈PS,u∈[1,q]}=D(φ(vi),φ(vj)),其中D()為無窮范數(shù),φ(vi)、φ(vj)分別表示vi、vj的映射向量,φ(vi)=,可知數(shù)據(jù)間在原始度量空間中距離的最小值可由映射向量空間中的距離確定,因此映射向量空間中的距離可以反映原始度量空間中的距離。證畢。

(4)空間劃分 首先選出方差最大的維度,根據(jù)數(shù)據(jù)集S在該維度上的值進行升序排序,選出中位數(shù)作為根節(jié)點,小于根節(jié)點的數(shù)據(jù)分配給左子樹,大于根節(jié)點的數(shù)據(jù)分配給右子樹。劃分時對于恰好處在分割線上的點,分為兩種情況:①當分割線左右的點數(shù)量不相等時,將處在分割線上的點分配給點數(shù)少的那個子樹;②當分割線左右的點數(shù)量相等時,將處在分割線上的點分配給離它最近的那個點所在的子樹。之后重復(fù)該劃分過程,直到將S劃分成大小相等的m個不相交的部分即為分區(qū)Pi(1≤i≤m)。

注:KD樹中每個分割維度的最小值、最大值和中位數(shù)構(gòu)成了包含分區(qū)Pi的軸對齊邊界框Bound(Pi),故原始空間記為∪Bound(Pi)(1≤i≤m),其中,Bound(Pi)∩Bound(Pj)=?(i≠j)。另外,對每個分區(qū)Pi,其包含Pi內(nèi)所有點vj的最小邊界框為MinBound(Pi)={[dmin(vj,PSu),dmax(vj,PSu)]|vj∈Pi,u∈[1,q]}。

KD樹劃分示例圖如圖1a所示,采樣數(shù)據(jù)集S={v1,v3,v4,v5,v6,v9,v11,v12,v15},第一次分區(qū)迭代時,mp=m=4,計算出x軸方向上的方差為7.65,y軸方向上的方差為10.62,因此使用y軸的中位數(shù)7劃分,整個采樣數(shù)據(jù)集S被劃分成兩個部分。此后,以類似的方式將這兩部分遞歸劃分,直到得到4個均勻的部分,即P1={v1,v2,v3}、P2={v4,v5,v6,v7}、P3={v8,v9,v10,v11}和P4={v12,v13,v14,v15}。由分區(qū)結(jié)果可以計算出Pi的最小邊界框MinBound(Pi)(如圖1b中灰色陰影部分),如MinBound(P1)={[2,6],[8,10]}。

(5)數(shù)據(jù)劃分 在得到一組不相交的子空間Bound(Pi)后,D中的每個對象都可以根據(jù)Bound(Pi)分配到相應(yīng)的分區(qū)Pi中,即利用映射后的樣本數(shù)據(jù)間的分割來估計原始數(shù)據(jù)之間的分割。劃分完成后,輸出兩表:分區(qū)信息表和數(shù)據(jù)信息表。分區(qū)信息表記錄每個分區(qū)Pi的信息,包括Pi的分區(qū)IDpid和Pi的最小邊界框MinBound(Pi);數(shù)據(jù)信息表記錄每個點vi的信息,包括vi的IDvid、對應(yīng)的分區(qū)IDpid和映射向量φ(vi)。

3.2 并行構(gòu)建相似度矩陣

相似度矩陣是對任意兩樣本之間相似度信息的描述,其構(gòu)造的好壞對最終聚類效果至關(guān)重要?，F(xiàn)有的并行算法構(gòu)建矩陣時計算所有數(shù)據(jù)間的距離,產(chǎn)生大量冗余計算,這嚴重制約了譜聚類算法的效率?；诖?本文采用t近鄰稀疏化相似度矩陣,具體思想為:①局部t近鄰搜索:并行計算每個Map分區(qū)內(nèi)部樣本數(shù)據(jù)的t近鄰;②跨分區(qū)的t近鄰搜索:提出優(yōu)化的分區(qū)分配策略(OPA)將合格的數(shù)據(jù)分配給分區(qū),進行跨分區(qū)的t近鄰搜索,得到各樣本數(shù)據(jù)的t近鄰,同時,搜索過程中設(shè)計基于三角不等式的KD樹剪枝策略以快速縮小搜索區(qū)域,避免無效計算;③獲取相似度矩陣:計算數(shù)據(jù)間的相似度值并存儲整個數(shù)據(jù)集的相似度矩陣。

(1)局部t近鄰搜索

計算每個分區(qū)Pi中數(shù)據(jù)點之間的距離,并找到每個數(shù)據(jù)點vj∈Pi的局部t近鄰結(jié)果。之后,將vj的t個最近的鄰居vj.tNN、vj到其第t個最近鄰居的距離vj.dt和vj的搜索范圍vj.SR添加到數(shù)據(jù)信息表,Pi的搜索區(qū)域Pi.SR添加到分區(qū)信息表。其中,vj.SR={[d(vj,PSu)-vj.dt,d(vj,PSu)+vj.dt]|u∈[1,q]}表示vj的搜索范圍,是一個將搜索區(qū)域限定在可能更新vj.tNN的潛在數(shù)據(jù)點的閾值;Pi.SR=∪vj∈Pivj.SR∪MinBound(Pi)表示Pi的搜索區(qū)域。

(2)跨分區(qū)的t近鄰搜索

完成各分區(qū)內(nèi)部的t近鄰搜索后,在各個分區(qū)之間進行t近鄰搜索。一旦某個數(shù)據(jù)vi滿足d(vi,vj)

定理2OPA策略。設(shè)m為分區(qū)個數(shù),將分區(qū)Pi的數(shù)據(jù)分配給分區(qū)Pj,則

(10)

式中i、j為分區(qū)下標。

此外,為避免將無效數(shù)據(jù)分配給分區(qū)導(dǎo)致冗余計算,本文設(shè)計了基于三角不等式的KD樹剪枝策略,其具體過程為:①提出數(shù)據(jù)近鄰點判斷定理,對不屬于分區(qū)Pi內(nèi)的數(shù)據(jù)點vj,若其位于Pi的搜索區(qū)域Pi.SR之外,則對數(shù)據(jù)點vj進行剪枝,將vj與該分區(qū)內(nèi)所有數(shù)據(jù)的相似度值記為0,否則依次計算各數(shù)據(jù)間距離,更新t近鄰結(jié)果;②提出分區(qū)近鄰點判斷定理,對分區(qū)Pi,若其最小邊界框與數(shù)據(jù)點vj(vj?Pi)的搜索區(qū)域不相交,則將分區(qū)Pi從點vj的搜索區(qū)域中刪除,且分區(qū)Pi內(nèi)所有數(shù)據(jù)與數(shù)據(jù)點vj的相似度值記為0,否則依次計算各數(shù)據(jù)間距離,更新t近鄰結(jié)果。

定理3數(shù)據(jù)近鄰點判斷。給定一個分區(qū)Pi,一數(shù)據(jù)點vj?Pi,若vj的映射向量φ(vj)位于Pi的搜索區(qū)域Pi.SR之外,則?v∈Pi,vj?v.tNN。

證明已知φ(vj)位于Pi的搜索區(qū)域Pi.SR之外,則?PSk∈PS,?v∈Pi,有d(vj,PSk)>d(v,PSk)+v.dt或d(vj,PSk)v.dt。由三角不等式,又有?v∈Pi,滿足d(vj,v)≥|d(vj,PSk)-d(v,PSk)|>v.dt。

因此?v∈Pi,vj?v.tNN,即數(shù)據(jù)點vj不屬于分區(qū)Pi內(nèi)所有數(shù)據(jù)的t近鄰。證畢。

定理4分區(qū)近鄰點判斷。給定一個分區(qū)Pi,一數(shù)據(jù)點v?Pi,若MinBound(Pi)∩v.SR=?,則有?vj∈Pi,vj?v.tNN。

證明因為?vj∈Pi,?PSu∈PS,MinBound(Pi)=

{[dmin(vj,PSu),dmax(vj,PSu)]|vj∈Pi,u∈[1,q]},所以有dmin(vj,PSu)≤d(vj,PSu)≤dmax(vj,PSu)。

又因為MinBound(Pi)∩v.SR=?,且v.SR={[d(v,PSu)-v.dt,d(v,PSu)+v.dt]|u∈[1,q]},所以?PSu∈PS,有

d(v,PSu)-v.dt>dmax(v,PSu)

或d(v,PSu)+v.dt

?d(vj,PSu)≤dmax(vj,PSu)

或d(v,PSu)+v.dt

?|d(v,PSu)-d(vj,PSu)|>v.dt

由三角不等式又有?vj∈Pi,

d(v,vj)≥|d(v,PSu)-d(vj,PSu)|>v.dt

?vj?v.tNN。證畢。

(3)獲取相似度矩陣

對稀疏矩陣中的每個非零元素,計算數(shù)據(jù)點與其t近鄰的相似度值,生成兩個鍵值對、,并將結(jié)果暫時存到combine。其中:key1為元素的行id,value1為列id和相似度值,key2為元素的列id,value2為行id和相似度值。之后,接受combine中的鍵值對,調(diào)用reduce函數(shù),具有相同key的元素對應(yīng)于所需對稱矩陣的同一行中的值,合并后得到最終的相似度矩陣。

并行構(gòu)建相似度矩陣的偽代碼如算法1所示。

算法1并行構(gòu)建相似度矩陣。

輸入:頂點集V,度量距離函數(shù)d,近鄰數(shù)t,分區(qū)數(shù)m;

輸出:相似度矩陣S∈Rn×n。

1. for each partitionPido

2. for each vertexv∈Pido //計算v的t近鄰、到第t個近鄰的距離及v的搜索范圍

3. computev.tNN,v.dtandv.SR

4. end for

5. computePi.SR=∪v∈Piv.SR∪MinBound(Pi) //獲取Pi的搜索區(qū)域

6. end for

7. for each vertexv∈Pido //分區(qū)間數(shù)據(jù)分配

10. Assign (v,Ps)

11. end for

12. else

14. Assign (v,Ps)

15. end for

16. end if

17.end for

18. for each partitionPido

19. for each vertexv∈Pido

20. for each allocated vertexvjdo

21. ifv∈vj.SR then

22. ifd(v,vj)≤v.dtthen //用vj的搜索范圍更新v的t近鄰

23. updatev.tNN

24. end if

25. end if

26. ifvj∈v.SR then

27. ifd(v,vj)≤vj.dtthen //用v的搜索范圍更新vj的t近鄰

28. updatevj.tNN

29. end if

30. end if

31. end for

32. end for

33.end for

34.compute similarity

35.similarityToSymmetry () //調(diào)整相似矩陣為對稱矩陣

36.MapReduce.Ruduce ()

37.returnthe similar matrixS∈Rn×n//獲得相似度矩陣

38.Function: Assign (v,Ps) //判斷近鄰點

39.ifφ(v)∈Ps.SR then

40. assignv toPs//數(shù)據(jù)近鄰點判斷

41.else ifMinBound(Ps)∩v.SR=? then

42. assignv toPs//分區(qū)近鄰點判斷

43.end if

3.3 并行計算特征向量

由于稀疏相似矩陣是按行劃分存儲在分布式節(jié)點上的,且矩陣的加減操作對于每一行是獨立的,矩陣的計算可以在各節(jié)點分布執(zhí)行。并行計算特征向量主要分為3個步驟:①計算Laplacian矩陣:求出對角矩陣并通過變換矩陣對應(yīng)位置元素的方式得到Laplacian矩陣;②正規(guī)化Laplacian矩陣:提出正規(guī)化定理,用元素對應(yīng)相乘的方式代替矩陣相乘操作,優(yōu)化Laplacian矩陣正規(guī)化過程;③求解特征向量:用Lanczos算法并行求解前k個最小特征值及其對應(yīng)的特征向量。

(1)計算Laplacian矩陣

并行計算相似度矩陣W每行元素之和,得到對角矩陣D。由于對角矩陣除對角線以外的元素都為0,而相似度矩陣對角線上的元素都為0,因此,對相似度矩陣的非對角線元素進行取反,將對角陣的對角元素一一對應(yīng)添加到取反后的相似度矩陣對角線上,得到Laplacian矩陣L。

(2)正規(guī)化Laplacian矩陣

提出正規(guī)化定理,將對角矩陣D的對角線元素其分發(fā)到各個節(jié)點上,各節(jié)點根據(jù)正規(guī)化定理將矩陣L的元素與對應(yīng)的對角陣元素相乘,得到正規(guī)化矩陣L′。

定理5正規(guī)化定理。對于Laplacian矩陣L,其正規(guī)化后的矩陣L′仍為對稱矩陣,且等于原矩陣L對應(yīng)位置元素xij乘一個系數(shù)(標量)cicj,其中,ci為對角陣元素。

證明因為D為對角陣,故D-1/2也為對角陣;又因為L′=D-1/2LD-1/2=(D-1/2L)D-1/2,所以L′即為先求對角陣D-1/2右乘矩陣L作為中間結(jié)果,后用對角陣D-1/2左乘中間結(jié)果。由對角陣的性質(zhì)可知,對角陣右乘一個矩陣就是用對角陣的對角依次與該矩陣對應(yīng)行上的元素相乘,相當于對矩陣L依次做行變換,即

(11)

對角陣左乘一個矩陣,就是用對角陣的對角依次與該矩陣對應(yīng)列上的元素相乘,相當于對矩陣依次做列變換,即

(12)

由此可以得出,某一矩陣左乘對角陣之后再右乘對角陣,相當于對對角陣左邊的矩陣依次做行變換和列變換,即xij對應(yīng)的系數(shù)為cicj,故有

(13)

因此,Laplacian矩陣的正規(guī)化操作可以通過矩陣對應(yīng)位置元素乘一個系數(shù)(標量)的方式來實現(xiàn)。另外,因為L是對稱矩陣,所以xij=xji,又因為cicj=cjci,所以cicjxij=cjcixji,即變換之后得到的L′依然為對稱矩陣。證畢。

(3)求解特征向量

首先,將矩陣L′按行分割存放,每次迭代將要和矩陣相乘的向量發(fā)送到矩陣L′的位置,通過Lanczos算法并行計算向量和矩陣L′的乘積,得到三對角矩陣;然后,通過QR(orthogonal triangular)算法求出三對角矩陣的特征值和特征向量,且這些特征值和特征向量就是原Laplacian矩陣的特征值和特征向量近似值;最后,對特征值按由小到大的順序排列,其對應(yīng)的特征向量構(gòu)成一個新的n×k階特征向量矩陣Z并對其正規(guī)化。

并行求解特征向量的偽代碼如算法2所示。

算法2并行求解特征向量。

輸入:相似度矩陣S∈Rn×n;

輸出:正規(guī)化特征向量矩陣T。

1.for each partitionPido

2. for each linee∈Pido

4. Lii=Dii//獲取L的對角線元素

5. if Wij≠0 then

6. Lij=-Wij//獲取L的非對角線元素

7. end if

8. if Lij≠0 then

10. end if

11. end for

12. end for

13.for each partitionPido

14. Lanczos (αi,βi) //調(diào)用Lanczos算法

15.end for

16.construct the multiplication result

17.QR (βi,γi) //QR分解

18.regularized eigenvector matrixT

19.MapReduce.Ruduce () //合并得到正規(guī)化特征向量矩陣

20.returnT

3.4 并行聚類

在對譜聚類算法的特征譜空間聚類時,初始簇中心的選取對聚類效率和正確率有很大影響,現(xiàn)有的并行譜聚類算法采用隨機選取的方式,容易引起算法初始簇中心敏感的問題。考慮到MA算法具有對初值不敏感和求解精度高的特點,故在并行聚類過程中引入MA算法,但該算法在迭代的過程中種群的多樣性會降低,可能出現(xiàn)早熟收斂,為此,本文提出混沌蜉蝣優(yōu)化算法(CMO)用于獲取初始簇中心,然后對特征空間進行并行聚類,最后得到最終聚類結(jié)果。

3.4.1 CMO算法

CMO算法獲取初始簇中心的具體過程為:①初始化種群:用Sin混沌序列初始化種群;②更新位置:提出速度更新參數(shù)sr1、sr2,改進原有的速度更新公式,更新蜉蝣速度與位置;③判斷早熟收斂:提出蜉蝣群體適應(yīng)度方差的早熟收斂判斷機制,并添加混沌擾動幫助算法跳出局部最優(yōu),迭代終止后得到最佳的初始簇中心。

(1)初始化種群

混沌變量具有隨機性、遍歷性和規(guī)律性的特點,將其運用于優(yōu)化搜索可以保持種群的多樣性,幫助算法跳出局部最優(yōu),從而提高算法的全局搜索能力。本文用Sin混沌序列對種群進行初始化,步驟描述如下:

步驟1隨機生成(-1,1)內(nèi)的初始值Z0,記iter=0;

步驟2對式(6)進行迭代,得到Z序列,iter自增1;

步驟3若達到最大迭代次數(shù),結(jié)束程序,同時存儲最終產(chǎn)生的Z序列。

(2)更新位置

提出速度更新參數(shù)sr1、sr2,代替原來的隨機數(shù)r1、r2,更新蜉蝣速度與位置,同時記錄蜉蝣的個體極值對應(yīng)的位置pbest和全局極值對應(yīng)的位置gbest。

定理6速度更新參數(shù)sr1、sr2。在速度更新公式中嵌入Sin混沌變量,雄性蜉蝣的速度為:

(14)

雌性蜉蝣的速度為

(15)

式中sr1、sr2為從Sin混沌中隨機選取的兩個混沌數(shù)。

證明由于Sin混沌映射在-1到1之間波動,均勻分布的隨機數(shù)也在[-1,1]之間,隨機選取的混沌數(shù)sr1、sr2可以用來代替均勻分布的隨機數(shù)r1和r2。同時,比起單純采用隨機數(shù),嵌入Sin混沌序列更有利于保證蜉蝣運動過程的隨機性和遍歷性,故參數(shù)sr1、sr2可用于更新蜉蝣速度。證畢。

(3)判斷早熟收斂

提出群體適應(yīng)度方差σ2,判斷算法是否早熟收斂,若早熟收斂,則以搜索停滯的解為基礎(chǔ)產(chǎn)生Sin混沌序列,對部分陷入局部最優(yōu)的蜉蝣進行混沌擾動,避免算法陷入局部最優(yōu),提高全局搜索能力和尋優(yōu)精度。添加混沌擾動的具體步驟如下:

步驟1根據(jù)式(6)迭代生成混沌變量;

步驟2將混沌變量載波到原變量的解空間;

步驟3按式newX′=(X′+newX)/2對蜉蝣的位置進行混沌擾動,其中:X′為需要進行混沌擾動的蜉蝣位置,newX為產(chǎn)生的混沌擾動量,newX′為混沌擾動后的蜉蝣位置。

(16)

式中f為歸一化因子,其作用是限制σ2的大小,

(17)

證明σ2越小,表示各蜉蝣的適應(yīng)度值越接近平均適應(yīng)度,即偏離程度越小,此時種群趨于收斂;反之,σ2越大,表示各蜉蝣的適應(yīng)度值越遠離平均適應(yīng)度,即偏離程度越大,則此時種群更容易處于隨機搜索狀態(tài)。因此,群體適應(yīng)度方差σ2可以反映種群中所有雄蜉蝣的“收斂程度”。證畢。

CMO算法獲取初始簇中心的步驟如下:

步驟1輸入Laplacian矩陣降維之后的結(jié)果矩陣,待聚類個數(shù)K,最大迭代次數(shù)Imax,群體適應(yīng)度方差臨界值?,混沌搜索迭代次數(shù)M。

步驟2采用Sin混沌映射初始化產(chǎn)生兩組數(shù)目相同的(K個)的初始種群,初始種群分別代表雄性蜉蝣、雌性蜉蝣,初始化其位置并設(shè)定參數(shù),然后用Sin混沌映射函數(shù)產(chǎn)生混沌隨機序列S1、S2。

步驟3每個雄性蜉蝣根據(jù)選取的中心按照最小距離原則劃分聚類數(shù)據(jù)集,計算適應(yīng)度值,并根據(jù)式(14)更新雄性蜉蝣的速度與位置,同時記錄每個雄性蜉蝣的個體極值對應(yīng)的位置pbest和全局極值對應(yīng)的位置gbest。適應(yīng)度函數(shù)采用聚類指標DBI指數(shù)的計算公式:

(18)

步驟4根據(jù)式(15)更新雌性蜉蝣的速度與位置。

步驟5進行交叉,產(chǎn)生雄性和雌性后代,用產(chǎn)生的具有最優(yōu)適應(yīng)度的新后代取代具有最劣的適應(yīng)度的父代蜉蝣。

步驟6判斷是否滿足精度要求或者達到最大迭代次數(shù),若是,轉(zhuǎn)步驟9,否則轉(zhuǎn)步驟7。

步驟7計算雄性蜉蝣的群適應(yīng)度方差σ2。若σ2

步驟8若算法早熟收斂,利用混沌搜索更新蜉蝣位置來跳出局部最優(yōu),完成后轉(zhuǎn)步驟3。

步驟9將得到的最佳位置作為k-means算法的初始簇中心。

3.4.2 并行k-means聚類

用CMO算法獲取初始簇中心后,進行并行k-means聚類,此過程包括Map階段和Reduce階段。在Map階段,計算每個數(shù)據(jù)點vi到初始聚類中心Cj(1≤j≤k)的距離,將該樣本點分配給距離最小的聚類中心,以鍵值對形式存儲,將中間結(jié)果寫入到Reduce函數(shù)。在Reduce階段,對Map函數(shù)寫入的結(jié)果按key值進行合并,計算每個簇的平均值,更新聚類中心。迭代此過程,直至獲得穩(wěn)定的聚類中心位置,輸出最終聚類結(jié)果。

3.5 PSC-MO算法流程

PSC-MO算法的具體實現(xiàn)步驟如下:

步驟1調(diào)用DPS數(shù)據(jù)分區(qū)策略,將原始數(shù)據(jù)集合理劃分為大小相同的文件塊。

步驟2啟動MapReduce任務(wù),調(diào)用算法1獲得相似度矩陣,并將結(jié)果存入分布式文件系統(tǒng)HDFS中。

步驟3啟動新的MapReduce任務(wù),調(diào)用算法2得到正規(guī)化特征向量矩陣Z,將結(jié)果存儲到Hadoop分布式文件系統(tǒng)(Hadoop Distributed File System,HDFS)中。

步驟4再次啟動新的MapReduce任務(wù),先調(diào)用CMO算法獲取初始聚類中心,然后進行k-means聚類,迭代直至獲得最終聚類結(jié)果。

3.6 算法時間復(fù)雜度分析

PSC-MO算法時間復(fù)雜度主要由數(shù)據(jù)劃分、并行構(gòu)建相似度矩陣、并行計算特征向量以及并行聚類4部分組成,分別記為T1、T2、T3和T4。

(1)數(shù)據(jù)劃分階段,對于KD樹分區(qū),需要采樣后執(zhí)行映射操作,然后將整個空間分割。假設(shè)選出l個支撐點,S為樣本集大小,m為分區(qū)數(shù),執(zhí)行映射的時間復(fù)雜度為O(Sl),將空間劃分為m個分區(qū)的時間復(fù)雜度為O(SlogSlogm),故數(shù)據(jù)劃分階段的時間復(fù)雜度為T1=O(S×(l+logSlogm))。

(2)并行構(gòu)建相似度矩陣階段,將KD樹用于t近鄰搜索,避免遍歷所有點,且用剪枝策略避免其在高維數(shù)據(jù)上陷入維度詛咒,假設(shè)數(shù)據(jù)維度為d,則計算整個數(shù)據(jù)集之間的距離時間復(fù)雜度為O(ndlogn/m),通過保留大小為t的最大堆稀疏化矩陣,故構(gòu)建稀疏相似度矩陣的時間復(fù)雜度為T2=O((ndlogn+nlognlogt)/m)。

(3)并行求解特征向量階段,Laplacian矩陣正規(guī)化的時間復(fù)雜度為O(nt/m),用Lanczos計算矩陣與向量相乘的時間為nt,求前k個特征向量的時間復(fù)雜度為O(knt/m+k2n),故并行求解特征向量階段的時間復(fù)雜度為T3=O(nt/m)+O(knt/m+k2n)。

(4)并行聚類階段,假設(shè)待聚類數(shù)目為k,M為迭代次數(shù),計算任意點與當前k個聚類中心的距離,時間復(fù)雜度為T4=O(nMk2/m)。

因此,PSC-MO算法的時間復(fù)雜度為TPSC-MO=T1+T2+T3+T4。大數(shù)據(jù)環(huán)境下,由于S

對于PSC[21]算法,在構(gòu)造相似度矩陣階段需要掃描整個數(shù)據(jù)集,計算歐式距離并迭代地重構(gòu)最大堆,該階段的時間復(fù)雜度為O((n2d+n2logt)/m);在并行求解特征向量階段,Laplacian矩陣正規(guī)化的時間復(fù)雜度為O(n3/m),設(shè)p為特征求解中Arnoldi長度,q為Arnoldi迭代次數(shù),則求前k個特征向量的時間復(fù)雜度為O(p3q)+(O(pn/m)+O(nt/m))×O(q(p-k)),故并行求解特征向量階段的時間復(fù)雜度近似為O(n3/m);并行聚類階段時間復(fù)雜度為O(nMk2/m)。因此,算法總時間復(fù)雜度為TPSC=O((n2d+n2logt)/m)+O(n3/m)+O(nMk2/m)。

對于PSCA[22]算法,構(gòu)造相似度矩陣的時間復(fù)雜度為O((n2d+n2logn)/m);在并行求解特征向量階段,Laplacian矩陣正規(guī)化的時間復(fù)雜度為O(n3),Lanczos算法矩陣與向量相乘的時間復(fù)雜度為O(n2),并行求解特征向量階段的時間復(fù)雜度近似為O(kn2/m+k2n);并行聚類階段時間復(fù)雜度與PSCA算法基本相同。因此,PSCA算法時間復(fù)雜度為TPSCA=O((n2d+n2logn)/m)+O(n3)+O(kn2/m+k2n)+O(nMk2/m)。

對于PSC-KD[23]算法,構(gòu)造相似度矩陣時采用KD樹索引查找近鄰,其時間復(fù)雜度為O((ndlogn+n2logn)/m),但最壞情況下(即數(shù)據(jù)維度過高)可能達到O((n2d+n2logn)/m);求解特征向量和并行聚類階段與PSCA算法基本相同。因此,PSC-KD算法時間復(fù)雜度TPSC-KD=O((ndlogn+n2logn)/m)+O(n3)+O(kn2/m+k2n)+O(nMk2/m)。

另外,由于nlogn

4 實驗結(jié)果與分析

4.1 實驗環(huán)境

為驗證PSC-MO算法的性能,本文設(shè)計了相關(guān)實驗。實驗采用的分布式集群包含1個Master節(jié)點和7個Slaver節(jié)點。各節(jié)點的硬件配置均為Intel(R)Core(TM)i7-9750H CPU、16 GB DDR4 RAM、1TB SSD,且各節(jié)點處于同一局域網(wǎng)中,通過500 Mb/s以太網(wǎng)進行通信。軟件配置為Ubuntu 16.04.7,Hadoop 2.7.5和JDK 1.8.0。

4.2 實驗數(shù)據(jù)

在算法可行性分析中,需要在規(guī)模不同的數(shù)據(jù)集上驗證PSC-MO算法的可行性;在算法性能比較中,用規(guī)模較大但維度不同的數(shù)據(jù)集評估PSC-MO算法的性能。因此,本文采用5個數(shù)據(jù)集,分別是規(guī)模較小的Corel[44]和規(guī)模較大的RCV1[45],covtype[46],kddb[47]和picasa[48]。Corel是科雷爾公司收集整理的圖像數(shù)據(jù)集,包含10類共1 000張圖像;RCV1是路透社提供的新聞?wù)Z料庫,為方便實驗對比,刪除了多重標記的數(shù)據(jù)和小于500個文檔的類,最終獲得了103類共計193 844個文檔,47 236個屬性;covtype記錄了美國科羅拉多州不同地塊的森林植被類型,該數(shù)據(jù)集共有581 012個實例,每個實例具有54個屬性;kddb是KDD CAUP 2010的問題訓練集,實驗采用的數(shù)據(jù)集是勝利者轉(zhuǎn)換過的版本,共包含826 048條數(shù)據(jù)和29 890 095條特征,具有數(shù)據(jù)維度高的特點;picasa來自于Google的picasa圖片數(shù)據(jù)集,該數(shù)據(jù)集有1 730 897條實例,144個屬性,具有數(shù)據(jù)量大的特點。數(shù)據(jù)集的詳細信息如表2所示。

表2 實驗數(shù)據(jù)集

4.3 評價指標

4.3.1 NMI

標準化互信息(Normalized Mutual Information,NMI)利用互信息來衡量數(shù)據(jù)分布的吻合程度。為驗證PSC-MO算法的聚類效果,本文采用NMI作為聚類質(zhì)量評估標準,其定義為:

(19)

式中:向量X為聚類得到的類別序列構(gòu)成的n維向量;向量Y表示真實樣本標簽構(gòu)成的n維向量,n為樣本個數(shù)。I(X,Y)表示X與Y的互信息,H(X)和H(Y)分別表示X和Y的香農(nóng)熵。NMI的取值區(qū)間為[0,1],值越大表明聚類質(zhì)量越高。

4.3.2 加速比

加速比是指同一任務(wù)在串行處理和并行處理下消耗的時間的比率。為評估PSC-MO算法并行處理大數(shù)據(jù)的能力,本文采用加速比衡量算法的效果和并行性能,加速比定義為:

(20)

式中:TS、TP分別為算法串行運行時間和并行運行時間;Speedup越大說明算法的并行化程度越高。

4.3.3 Efficiency

并行效率(Efficiency)是指并行系統(tǒng)的加速比和執(zhí)行任務(wù)所用計算節(jié)點數(shù)的比率。為評估PSC-MO算法的可擴展性,本文采用Efficiency衡量算法的并行效率,Efficiency定義為:

(21)

式中:SN為算法的加速比;N為集群中計算節(jié)點數(shù)量。η的值越接近1說明算法對集群的利用率越高。

4.4 算法可行性比較分析

4.4.1 CMO算法可行性分析

為驗證CMO算法的可行性和優(yōu)越性,在4個不同的基準測試函數(shù)上對粒子群算法(Particle Swarm Optimization Algorithm, PSO)、遺傳算法(Genetic Algorithm, GA)、差分進化算法(Differential Evolution Algorithm,DE)、蜉蝣算法(Mayfly Algorithm,MA)[33]和CMO算法進行仿真實驗。實驗所用的基準測試函數(shù)包括單峰函數(shù)和多峰函數(shù),其具體信息如表3所示。為避免參數(shù)隨機性對最終效果的影響,實驗中將所有算法的參數(shù)設(shè)置相同,通過多次運行實驗選取結(jié)果較好的數(shù)值作為參數(shù),最終選取種群規(guī)模N=40(MA和CMO算法中雄性和雌性個體分別為20),正吸引系數(shù)a1=1、a2=1.5,能見度系數(shù)β=2,舞蹈系數(shù)d=0.1,隨機飛行系數(shù)fl=0.1,最大迭代次數(shù)Maxiter=1 000,維度d分別為10、50、100。為對算法進行統(tǒng)計學分析,選取各算法在基準測試函數(shù)上獨立運行60次的實驗結(jié)果,將各算法的平均值和標準差作為評價指標?；鶞蕼y試函數(shù)優(yōu)化結(jié)果如表4所示。

表3 基準測試函數(shù)

表4 基準測試函數(shù)優(yōu)化結(jié)果比較

從表3可以看出,各算法在4個測試函數(shù)上的尋優(yōu)精度和尋優(yōu)穩(wěn)定性隨著維度增大而降低,且CMO算法多次尋優(yōu)的平均值和標準差相比MA算法均更小,始終擁有更好的尋優(yōu)性能。在優(yōu)化單峰函數(shù)F1、F2時,CMO算法不論是在10維、50維還是100維,求解精度和求解穩(wěn)定性相比PSO、GA、DE、MA算法都有一定幅度的提升,甚至在維度為10時平均值能達到理論最優(yōu)解0,標準差最小,比MA算法提升了20個數(shù)量級以上。在優(yōu)化多峰函數(shù)時,CMO算法在不同維度下的求解精度均更高,其中,優(yōu)化F3時平均差分別達到了6.1285E-57、2.6429E-26和7.2687E-12,標準差達到了9.3891E-57、6.2682E-27和3.2629E-12,取得了較為理想的結(jié)果,這也說明本文的改進策略是可行有效的。另外,隨著維度逐漸增大,各算法的求解精度和穩(wěn)定性都有所降低,而CMO算法則變化較小,尤其是在多峰函數(shù)F8上,維度為100時算法的平均值和標準差分別達到了2.9752E-03和1.9529E-03,依然接近理論最優(yōu)解,表現(xiàn)出了極強的穩(wěn)定性。這是由于單峰函數(shù)在求解區(qū)域內(nèi)只有一個極值,尋優(yōu)相對容易,故各算法的尋優(yōu)結(jié)果差異較不明顯。而對多峰函數(shù)進行尋優(yōu)的過程中,其求解區(qū)域內(nèi)存在大量局部極值點,未作改進的MA算法易陷入局部最優(yōu),其求解精度不高。相比之下,CMO算法充分利用混沌運動的隨機性、遍歷性保證了種群的多樣性和搜索的遍歷性,在迭代過程中始終保持較強的搜索能力,這就在保證局部搜索能力的同時加強了算法的全局尋優(yōu)能力。此外,CMO算法在MA算法的基礎(chǔ)上增加了早熟收斂判斷機制,用Sin混沌搜索有效地幫助算法跳出局部最優(yōu)點,從而更精確地找到全局最優(yōu)值。因此可以得出,CMO算法具有可行性,且魯棒性和穩(wěn)定性優(yōu)于其他對比算法。

4.4.2 PSC-MO算法可行性分析

為驗證PSC-MO算法在大數(shù)據(jù)環(huán)境下并行聚類的可行性,采用算法的加速比來進行衡量,對PSC-MO算法在Corel、RCV1、covtype、kddb、picasa 5個數(shù)據(jù)集上進行測試。為避免實驗結(jié)果的偶然性,算法在每個數(shù)據(jù)集上獨立運行5次,取其平均值,實驗結(jié)果如圖2所示。

從圖2可以看出,隨著節(jié)點數(shù)逐漸增加,PSC-MO算法在5個數(shù)據(jù)集上的加速比基本呈上升趨勢,且數(shù)據(jù)集規(guī)模越大,PSC-MO算法加速比的上升趨勢愈加明顯,表現(xiàn)出其良好的可行性與有效性。其中,當節(jié)點數(shù)為2時,PSC-MO算法在五個數(shù)據(jù)集上的加速比差距較小,在規(guī)模最小的Corel數(shù)據(jù)集上最小;當節(jié)點數(shù)為4時,PSC-MO算法的加速比分別比在一個節(jié)點上增加了1.13、1.47、2.28、2.61、2.87;當節(jié)點數(shù)為8時,算法加速比達到最高,分別為3.19、3.78、5.38、6.74、7.51,比在6個節(jié)點上增加了0.18、0.24、0.68、1.51、1.85。這是由于PSC-MO算法設(shè)計了DPS策略,在方差最大的維度上劃分數(shù)據(jù)并分配均勻的數(shù)據(jù)給各節(jié)點,減少了節(jié)點間的通信時間,保證了各節(jié)點間負載均衡,極大地提高了并行處理效率。此外,在構(gòu)建相似度矩陣時,采用OPA策略將合格的數(shù)據(jù)分配給分區(qū)并對數(shù)據(jù)點和分區(qū)進行剪枝,避免了冗余計算,減少了系統(tǒng)讀寫和傳輸數(shù)據(jù)占用的時間,節(jié)點間交互較少,一定程度上提升了算法的并行性能,且數(shù)據(jù)規(guī)模越大,減少冗余計算的優(yōu)勢被逐漸放大,PSC-MO算法的加速比提升更大。這也表明PSC-MO算法適用于大數(shù)據(jù),且在規(guī)模較大的數(shù)據(jù)集上效果尤為明顯。

4.5 算法性能比較分析

4.5.1 聚類效果

為評估PSC-MO算法的聚類效果,將NMI值作為評價指標,將PSC-MO算法分別與不使用CMO優(yōu)化的PSC-NOMO、PSC-KD、PSC算法在RCV1、covtype、kddb、picasa 4個數(shù)據(jù)集上進行對比實驗。另外,為避免t值的選取影響實驗結(jié)果準確性,在各數(shù)據(jù)集上分別取不同的t值,每次測試獨立運行5次,取5次NMI的均值作為實驗結(jié)果。實驗結(jié)果如圖3所示。

從圖3可以看出,隨著t近鄰數(shù)的不斷增加,各算法的NMI值先增加后減少,在同一數(shù)據(jù)集上相同t值達到NMI最大值,并且PSC-MO算法在不同數(shù)據(jù)集上的NMI值始終保持最高,表現(xiàn)出良好的聚類效果。其中,在數(shù)據(jù)量較小但類別數(shù)較多的數(shù)據(jù)集RCV1上(如圖3a所示,t值為60時PSC-MO算法的NMI值達到了0.501,分別比PSC-NOMO、PSC-KD、PSC算法高出了0.104、0.138、0.159;在數(shù)據(jù)集covtype、kddb上(如圖3b和圖3c),各算法分別在t=80、t=120時聚類效果最好,PSC-MO算法的NMI值最高甚至達到了0.764;在數(shù)據(jù)量最大的數(shù)據(jù)集picasa上(如圖3d),在t值為200時PSC-MO算法的NMI值為0.627,分別比PSC-NOMO、PSC-KD、PSC算法高出了26.92%、48.23%、46.84%。出現(xiàn)這種現(xiàn)象主要有兩個原因:①PSC-MO算法采用了DPS策略對數(shù)據(jù)分區(qū),盡可能將相似度大的數(shù)據(jù)劃分到同一計算節(jié)點上,一定程度上減少了錯誤劃分的可能,間接提升了聚類效果;②選取的t值太小不能包PSC-KD含足夠多的數(shù)據(jù)間的相似信息,t值太大可能包含過多的信息,這都會使得聚類時尋優(yōu)變得更加困難,從而影響算法的聚類效果,但PSC-MO算法在對特征譜空間聚類時,設(shè)計了CMO算法尋找最佳的初始聚類中心,提高了算法的全局搜索能力,從而提高了聚類質(zhì)量。對于PSC-NOMO算法,僅是采用DPS策略對數(shù)據(jù)分區(qū),并未改進最后聚類的過程,算法的聚類效果只有小幅度的提升。同樣地,PSC-KD、PSC算法也只是簡單地并行化k-means聚類過程,極易受噪聲數(shù)據(jù)的影響,聚類效果并不理想。

4.5.2 算法運行時間

為驗證PSC-MO算法的時間復(fù)雜度,在上述4個數(shù)據(jù)集上對PSC-MO、PSCP(不包含KD樹剪枝的PSC-MO算法變體)、PSCA和PSC-KD算法分別進行5次測試,取其平均值,得到各算法的運行時間(如圖4)。

從圖4可以看出,隨著數(shù)據(jù)規(guī)模和數(shù)據(jù)維度的增大,各算法的運行時間也不斷增加,但相較于PSCP、PSC-KD和PSCA算法,PSC-MO算法在4個數(shù)據(jù)集上的運行時間均有所下降,尤其是在規(guī)模較大的數(shù)據(jù)集kddb、picasa上降低的幅度更為明顯。其中,在kddb數(shù)據(jù)集上,PSC-MO算法的運行時間降低幅度最大,分別比PSCP、PSC-KD和PSCA算法降低了57.56%、64.79%和69.74%;在規(guī)模較小的covtype數(shù)據(jù)集上降低的幅度最小,但也分別降低了12.04%、34.45%和47.04%。造成這種結(jié)果的主要原因有4點:①PSC-MO算法的DPS策略增加了處理數(shù)據(jù)集的時間,在小規(guī)模數(shù)據(jù)集上執(zhí)行該策略耗費的時間小于其對算法時間開銷的優(yōu)化,但隨著數(shù)據(jù)集規(guī)模的增大,DPS策略消耗的時間所占比重逐漸降低,數(shù)據(jù)規(guī)模足夠大時其對算法的整體性能影響幾乎可以忽略,故PSC-MO算法在大規(guī)模數(shù)據(jù)集上效果顯著;②PSC-MO算法在耗時最多的并行構(gòu)建相似度矩陣過程中,采用KD樹索引并提出了合理的剪枝策略,避免了冗余計算,加快了搜索t近鄰的速度,極大地減少了算法的運行時間;③PSC-MO算法對Laplacian矩陣正規(guī)化的優(yōu)化避免了矩陣的直接相乘操作,減少了時間開銷;④PSC-MO算法利用CMO算法可以找到較為合適的初始聚類中心位置,減少算法迭代次數(shù),從而有效地降低了算法的運行時間。相比之下,未用KD樹剪枝策略的PSCP算法和PSC-KD算法存在許多額外的非t近鄰數(shù)據(jù)間的計算,該過程需要大量的時間開銷,尤其是在數(shù)據(jù)維度高的kddb數(shù)據(jù)集上,PSCP算法和PSC-KD算法的劣勢更加明顯;另外,PSC-KD算法與PSCA算法在Laplacian矩陣正規(guī)化和最終聚類迭代過程中也需要消耗大量的計算資源。整體來說,相較于PSCP、PSC-KD和PSCA算法的運行時間,PSC-MO算法展現(xiàn)了出色的性能。

4.5.3 算法加速比

為評估PSC-MO算法在大數(shù)據(jù)環(huán)境下的并行性能,在上述4個數(shù)據(jù)集上對PSC-MO、PSCP(不包含KD樹剪枝的PSC-MO算法變體)、PSCA和PSC-KD算法分別進行5次測試,取運行時間的平均值作為實驗結(jié)果,然后計算加速比,最終的實驗結(jié)果如圖5所示。

從圖5可以看出,隨著節(jié)點數(shù)的增加,各算法的加速比也逐步增加,并且PSC-MO算法在規(guī)模較大的kddb、picssa數(shù)據(jù)集上始終擁有最高的加速比。在處理RCV1這樣規(guī)模相對較小的數(shù)據(jù)集時(如圖5a),各算法加速比差別不大,當節(jié)點數(shù)為2時,PSC-MO、PSCP算法的加速比分別為1.36、1.41,略小于PSCA和PSC-KD算法(1.49、1.57),但隨著節(jié)點數(shù)目增多,PSC-MO、PSCP算法的加速比超越了PSCA和PSC-KD算法,且各個算法的加速比增長趨于平緩。這是由于在數(shù)據(jù)集的規(guī)模較小時,各節(jié)點間的通信時間占算法的很大一部分,而通過并行化運算獲得的運行速度提升卻極為有限從而導(dǎo)致了加速比較小;當節(jié)點數(shù)量增加時,相比其他算法,用DPS分區(qū)策略的PSC-MO、PSCP算法可以有效控制節(jié)點之間的負載均衡,因此PSC-MO、PSCP算法的加速比略高于其他算法。此外,可以看出,在處理kddb以及picasa這樣規(guī)模相對較大的數(shù)據(jù)集時(如圖5c和圖5d),3個對比算法的加速比最終趨于穩(wěn)定,而PSC-MO算法運行的加速比隨著節(jié)點數(shù)的增加而逐漸增加,尤其是在picasa數(shù)據(jù)集上,當節(jié)點數(shù)分別為2、4、6、8時,PSC-MO算法運行的加速比分別為1.95、3.87、5.66、7.51,基本接近線性增長,并且PSC-MO算法始終具有最高的加速比,而未進行KD樹剪枝的PSCP算法的加速比始終小于PSC-MO算法的加速比。這是由于PSC-MO算法的分區(qū)策略保證了各節(jié)點間的負載均衡,而搜索t近鄰時的KD樹剪枝策略可以一定程度上減少節(jié)點間的通信開銷,并且隨著數(shù)據(jù)規(guī)模的增大,算法通過高效的并行化運算減少總體運行時間的優(yōu)勢被逐漸放大,從而有了更大的加速比。因此,PSC-MO算法在大數(shù)據(jù)環(huán)境下?lián)碛懈玫牟⑿行阅堋?/p>

4.5.4 算法并行效率

為評估PSC-MO算法在大數(shù)據(jù)環(huán)境下的可擴展性,在上述4個數(shù)據(jù)集上對PSC-MO、PSC、PSCA和PSC-KD算法分別進行測試,分別比較用不同節(jié)點數(shù)處理各算法的并行效率。同時,為避免實驗結(jié)果的偶然性,每次測試獨立運行5次,取5次Efficiency(并行效率)的均值作為實驗結(jié)果。最終的實驗結(jié)果如圖6所示。

從圖6可以看出,隨著節(jié)點數(shù)的增加,各算法的并行效率均呈下降趨勢,但PSC-MO算法在數(shù)據(jù)量更大的數(shù)據(jù)集covtype、kddb、picssa上始終保持最高的效率,且下降幅度較小,表現(xiàn)出良好的系統(tǒng)可擴展性。其中,在數(shù)據(jù)量較小的數(shù)據(jù)集RCV1上(如圖6a),各算法差異較不明顯,當節(jié)點數(shù)較少時PSC-MO算法的并行效率要低于其他算法,但當節(jié)點數(shù)達到8時,PSC-MO算法的效率超越了其他算法,分別比PSC、PSCA和PSC-KD算法高出了17.51%、24.60%、6.78%;在數(shù)據(jù)集covtype上(如圖6b),PSC-MO算法的效率要明顯高于其他算法,當節(jié)點數(shù)為8時,分別高出了30.47%、45.58%、20.35%;在數(shù)據(jù)集kddb上(如圖6c),當節(jié)點數(shù)達到8時,PSC-MO算法的效率分別比PSC、PSCA和PSC-KD算法高出了52.03%、104.79%、63.96%;在數(shù)據(jù)集kddb上(如圖6d),PSC-MO算法的效率依然高于其他算法且表現(xiàn)得相當平穩(wěn),當節(jié)點數(shù)為2、4、6、8時其并行效率分別達到了97.54%、96.74%、94.27%、93.82%,均保持在90%以上。產(chǎn)生這種結(jié)果的主要原因是:①PSC-MO算法采用了DPS策略,用KD樹將整個數(shù)據(jù)空間分割成若干個均勻的子空間,節(jié)點間負載達到均衡,減少了節(jié)點間互相等待的時間。同時,通過對數(shù)據(jù)采樣、選擇支撐點的方式減少了計算成本,這都有效提升了算法并行效率,但在小規(guī)模數(shù)據(jù)集上,由于DPS策略將數(shù)據(jù)分布到各節(jié)點、任務(wù)調(diào)度等會造成通信時間增多,而通過該策略減少的時間開銷卻極為有限,故在小數(shù)據(jù)集上效果不太明顯;②PSC-MO算法在計算相似度矩陣時采用了OPA策略分配數(shù)據(jù),并設(shè)計了合理的剪枝策略對數(shù)據(jù)和分區(qū)進行剪枝,避免了冗余計算,大大減少了節(jié)點間傳輸數(shù)據(jù)的時間開銷,一定程度上提高了算法并行效率,且隨著數(shù)據(jù)集規(guī)模的增大,該策略對算法效率提升的優(yōu)勢愈加明顯。相比之下,PSC、PSCA算法分配數(shù)據(jù)時,未考慮數(shù)據(jù)的分布特性,節(jié)點數(shù)較多時將數(shù)據(jù)分布到各節(jié)點會導(dǎo)致通信時間增加,尤其是在小規(guī)模數(shù)據(jù)集上,其通信時間比重大大增加,從而降低算法并行效率;而PSC-KD算法雖然采用了KD樹索引結(jié)構(gòu),但搜索t近鄰時未提出有效的方法,數(shù)據(jù)規(guī)模過大時易陷入性能瓶頸。因此,PSC-MO算法對集群的利用率更為穩(wěn)定,擁有較強的系統(tǒng)可擴展性。

5 結(jié)束語

為彌補大數(shù)據(jù)環(huán)境下并行譜聚類算法的不足,本文設(shè)計并實現(xiàn)了一種新的并行譜聚類算法PSC-MO。首先,提出了DPS策略劃分數(shù)據(jù),解決了各節(jié)點間負載不均衡的問題;其次,在構(gòu)建稀疏相似矩陣過程中,提出了OPA策略和基于三角不等式的KD樹剪枝策略以進行跨分區(qū)的t近鄰搜索,既減少了通信開銷又降低了計算成本;然后,提出了正規(guī)化定理,通過元素對應(yīng)相乘的方式代替矩陣相乘以優(yōu)化Laplacian矩陣正規(guī)化過程,進一步減少了時間開銷;最后,提出混沌蜉蝣優(yōu)化算法用于k-means并行聚類,有效避免了算法的初始化敏感問題。此外,為驗證PSC-MO算法的性能,本文在4個數(shù)據(jù)集上分析并比較了PSC-MO算法與其他算法的聚類效果、運行時間、加速比和并行效率。實驗表明,PSC-MO算法不僅具有良好的聚類效果,還在大規(guī)模數(shù)據(jù)集上表現(xiàn)出了良好的數(shù)據(jù)和系統(tǒng)可擴展性。

雖然PSC-MO算法在大數(shù)據(jù)環(huán)境下表現(xiàn)出良好的性能,但算法并未實現(xiàn)t近鄰數(shù)、特征值數(shù)和后期聚類數(shù)的自動調(diào)優(yōu),這些不足也將是未來的研究方向。此外,未來也將嘗試將PSC-MO算法用于更多的大數(shù)據(jù)應(yīng)用場景中,充分發(fā)揮其在聚類性能上的優(yōu)勢。