基于Spark 框架和ASPSO 的并行劃分聚類算法

毛伊敏，甘德瑾，廖列法，陳志剛

（1.江西理工大學信息工程學院，江西 贛州 341000；2.中南大學計算機學院，湖南 長沙 410083）

0 引言

聚類算法根據(jù)數(shù)據(jù)的相似特征將數(shù)據(jù)集劃分成不同的類別，同一類別下的對象具有一定的相似性，而不同類別對象之間則差異較大[1]，因其能夠發(fā)現(xiàn)樣本數(shù)據(jù)潛在的分布模式，被廣泛應(yīng)用于計算機科學、生物信息學、圖像處理、社交網(wǎng)絡(luò)、天文學以及許多其他的領(lǐng)域。在聚類算法中，基于劃分的聚類算法，如K-means 算法[2]、K-中心點算法[3]和CLARANS（clustering algorithm based on randomized search）[4]，由于聚類思想簡單且聚類可行性高，受到人們的廣泛關(guān)注。

隨著5G 時代的到來，數(shù)據(jù)規(guī)模爆炸式增長。相較于傳統(tǒng)數(shù)據(jù)，大數(shù)據(jù)擁有數(shù)據(jù)規(guī)模大、數(shù)據(jù)種類多樣化、數(shù)據(jù)價值密度低、數(shù)據(jù)增長速度快等基本特征[5-6]。然而，傳統(tǒng)的劃分聚類算法在處理大數(shù)據(jù)時，其時間復雜度以幾何級數(shù)增長。因此，如何使劃分聚類算法更快地處理大數(shù)據(jù)，是國內(nèi)外重點關(guān)注的問題。

隨著傳統(tǒng)的數(shù)據(jù)挖掘算法在分布式計算框架的廣泛應(yīng)用，Spark 憑借計算速度快、簡潔易用、通用性強和支持多種運行模式等優(yōu)勢深受廣大研究人員青睞。其中，Mugdha 等[7]最早提出了K-means 與Spark 結(jié)合的近似算法，但該算法易受噪聲數(shù)據(jù)影響，劃分后的數(shù)據(jù)網(wǎng)格存在數(shù)據(jù)離散系數(shù)較大與抗干擾性差的問題。針對此問題，王海艷等[8]提出了基于Spark 與密度區(qū)域劃分（SP-DAP，Spark and density-area partition）算法，提取數(shù)據(jù)集中的高密度數(shù)據(jù)區(qū)域，極大地減小了數(shù)據(jù)劃分后的離散系數(shù)并增強了算法的抗干擾性。但該算法無法準確獲取局部簇的簇數(shù)，從而導致對大型數(shù)據(jù)的聚類存在局部簇的簇數(shù)難以確定的問題。為了解決此問題，Wang 等[9]提出基于 Spark 與 K-means（SK-means，Spark and K-means）并行聚類算法，通過將數(shù)據(jù)劃分為幾個可重疊子集，并進行預處理得到簇數(shù)。徐鵬程等[10]在Spark 平臺上引入Canopy算法和最大最小距離方法，通過簡單的距離計算把初始數(shù)據(jù)劃分為多個子集，獲取局部聚類的簇數(shù)，解決了局部簇的簇數(shù)難以確定的問題。雖然這些算法對局部簇的簇數(shù)難以確定的問題進行了改進，但是并沒有避免局部簇質(zhì)心的隨機性對聚類效果的影響。

近年來，群體智能優(yōu)化算法憑借其尋優(yōu)效果好、易實現(xiàn)等優(yōu)勢得到了廣泛應(yīng)用。因此，許多學者引入群體智能算法對數(shù)據(jù)的局部簇質(zhì)心進行優(yōu)化。例如，Multazam 等[11]在Spark 平臺上提出遺傳算法與K-means 相結(jié)合（SP-GAKMS，Spark and genetic algorithmwith K-means），通過對種群個體的多次選擇、交叉以及變異的遺傳操作，使種群個體逐漸優(yōu)化并逐步逼近最優(yōu)解，最終得到最優(yōu)的初始質(zhì)心集。許明杰等[12]在 Spark 環(huán)境下提出PSOK-means（particle swarm optimization and K-means）算法，利用粒子群優(yōu)化（PSO，particle swarm optimization）算法來提高K-means 的全局搜索能力，得到初始質(zhì)心。Gao 等[13]利用最優(yōu)化問題對 PSO 算法進行改進，提出了SP-PSOK-means（Spark and PSO with K-means）算法，利用遠離個體最差經(jīng)驗和最差群體經(jīng)驗提高局部搜索能力，獲取全局最優(yōu)初始質(zhì)心。雖然這些算法成功應(yīng)用了群優(yōu)化算法來獲取局部簇的初始質(zhì)心，但存在局部搜索能力差、搜索精度不高且易陷入局部最優(yōu)值等缺點，導致無法獲取全局最優(yōu)初始質(zhì)心，因此算法的初始質(zhì)心優(yōu)化能力有待進一步提升。

此外，基于Spark 并行計算框架下的劃分聚類算法在進行局部簇的并行化合并過程時存在算法局部簇并行化合并效率低的問題。為了解決這個問題，Agrawal 等[14]提出基于Spark 節(jié)點相似度的局部簇合并（SP-LCMNS，Spark and local cluster merging and node similarity）算法，通過合并二次劃分算法與群體結(jié)構(gòu)，避免了點與邊集的重復計算，極大地提高了局部簇的并行化合并效率；Lai 等[15]提出了基于Spark 局部聚合的自動迭代聚簇算法（SP-LAICA，Spark and local aggregation and iterative clustering algorithm），通過尋找局部簇數(shù)據(jù)集中連接緊密的節(jié)點集，并迭代合并局部簇，實現(xiàn)了對局部簇的高效率并行化合并。雖然上述算法對提升局部簇的并行化合并的效率有一定提升，但這些算法都存在一定的局限性，導致簇的并行化合并效率降低。因此，局部簇并行化合并效率低的問題仍是亟待解決的問題。

綜上，如何有效減小數(shù)據(jù)離散系數(shù)、增強算法抗干擾性、確定局部聚類簇數(shù)、避免局部簇質(zhì)心隨機性以及提高局部簇并行化合并效率等仍然是目前亟待解決的問題。針對這些問題，本文提出了一種基于Spark 框架和粒子群優(yōu)化自適應(yīng)策略（ASPSO，adaptive strategy based on particle swarm optimization）下的并行劃分聚類（PDC-SFASPSO，parallel division clustering based on Spark framework and ASPSO）算法。本文的主要工作如下。1)提出了基于皮爾遜相關(guān)系數(shù)和方差（PCCV，Pearson’s correlation coefficient and variance）的網(wǎng)格劃分策略，計算數(shù)據(jù)網(wǎng)格的皮爾遜相關(guān)系數(shù)與相關(guān)系數(shù)閾值，通過與閾值比較，對數(shù)據(jù)網(wǎng)格進行劃分，獲取數(shù)據(jù)離散系數(shù)較小的網(wǎng)格單元G1，G2，G3，…，Gm，并設(shè)計離群因子對網(wǎng)格單元進行離群點過濾，解決了數(shù)據(jù)離散系數(shù)較大與抗干擾性差的問題。2)提出了基于勢函數(shù)與高斯函數(shù)（PFGF，potential function and Gaussian function）的網(wǎng)格劃分策略，對數(shù)據(jù)點進行局部區(qū)域的有效覆蓋，并提出更新函數(shù)FU(xi，yj)，更新數(shù)據(jù)集中的樣本點，形成以不同樣本點為核心的區(qū)域簇，獲取局部聚類的簇數(shù)，解決了局部簇的簇數(shù)難以確定的問題。3)提出了ASPSO，計算自適應(yīng)參數(shù)η，通過自適應(yīng)參數(shù)更新粒子的位置和速度，獲取局部簇質(zhì)心，解決了局部簇質(zhì)心的隨機性問題。4)提出了基于簇半徑與鄰居節(jié)點（CRNN，cluster radius and neighbor node）的局部簇合并策略，計算出鄰居節(jié)點，并根據(jù)簇的相似性函數(shù)CSM(ni，nj)進行相似度判斷，結(jié)合Spark 并行計算框架將相似度大的簇進行合并，避免了在并行化運算過程中對所有簇的點與邊集同時展開搜索，提高了局部簇并行化合并的效率。

1 相關(guān)概念介紹

定義1勢函數(shù)。勢函數(shù)可以對數(shù)據(jù)點的作用勢進行分析，度量樣本空間中2個數(shù)據(jù)點隨距離的變化情況[16]。設(shè)有一個樣本集Si，x1和x2為數(shù)據(jù)集中的2 個樣本點，則勢函數(shù)γ(x1，x2)可以表示為

其中，T為常數(shù)，d2(x1，x2)為x1和x2之間的距離。

定義2高斯核函數(shù)。高斯核函數(shù)是某種沿徑向?qū)ΨQ的標量函數(shù)，可以將有限維數(shù)據(jù)映射到高維空間，并將數(shù)據(jù)集劃分成多個不同子空間，從而進行局部計算[17]。設(shè)σ表示帶寬，x表示樣本點，x′表示核中心，則高斯核函數(shù)k(x，x′)可以表示為

定義3鄰居節(jié)點。鄰居節(jié)點表示簇與簇之間的交集節(jié)點，可以衡量簇與簇之間親密程度。設(shè)有2 個簇Ci，Cj的數(shù)據(jù)點，對于任意樣本點xi，如果其到質(zhì)心的距離小于簇半徑Ri和Rj，則此樣本點稱為鄰居節(jié)點，其集合稱為鄰居節(jié)點集[18]。

定義4PSO 算法。PSO 算法是一種基于群體智能的全局隨機搜索算法，可以對粒子的位置進行不斷調(diào)優(yōu)，求解粒子最優(yōu)化問題[19]。該算法主要包括3 個階段：粒子位置與速度的初始化、粒子速度更新、粒子位置更新。其具體步驟如下。

1)粒子位置與速度的初始化

2)粒子速度更新

其中，ω為慣性權(quán)重，表示之前的速度對當前速度的影響；c1和c2為學習因子，rand和Rand 為0～1 的隨機數(shù)。

3)粒子位置更新

2 PDC-SFASPSO 算法

2.1 算法思想

PDC-SFASPSO 算法主要包括3 個階段：數(shù)據(jù)劃分、局部聚類、局部簇合并。1)數(shù)據(jù)劃分階段提出網(wǎng)格劃分策略PCCV，進行數(shù)據(jù)劃分。2)局部聚類階段，首先提出PFGF 策略與更新函數(shù)FU(xi，yj)獲取局部聚類的簇數(shù)；然后提出ASPSO 初始化局部簇質(zhì)心；最后結(jié)合Spark 提出并行化局部聚類策略（SPPLCS，Spark and parallel local clustering strategy）進行局部簇的并行化計算，實現(xiàn)局部聚類。3)局部簇合并階段提出局部簇合并策略CRNN，合并相似度大的局部簇。

2.2 數(shù)據(jù)劃分

目前大數(shù)據(jù)環(huán)境下的劃分聚類算法中，在對數(shù)據(jù)劃分時存在數(shù)據(jù)離散系數(shù)較大與抗干擾性差的問題。因此，本文在進行數(shù)據(jù)劃分的過程中提出了網(wǎng)格劃分策略PCCV 來解決此問題。該策略主要包括3 個步驟：數(shù)據(jù)集的粗略劃分、網(wǎng)格的劃分、離群點的過濾。

2.2.1 數(shù)據(jù)集的粗略劃分

對于初始數(shù)據(jù)集，可以對數(shù)據(jù)先進行粗略劃分，獲取數(shù)據(jù)離散系數(shù)較小的網(wǎng)格。其具體過程為：首先獲取劃分數(shù)據(jù)集，并將其標記為Gs；其次提出分割函數(shù)FD(xi)計算出劃分閾值，分別與每個數(shù)據(jù)點比較，將大于閾值的數(shù)據(jù)放入網(wǎng)格Gmax中，小于閾值的數(shù)據(jù)則放入Gmin中；最后獲得2 個數(shù)據(jù)網(wǎng)格Gmax與Gmin。

定理1分割函數(shù)FD(xi)。已知空間數(shù)據(jù)集中第i維度的數(shù)據(jù)的方差為Si，數(shù)據(jù)之和為di，網(wǎng)格中數(shù)據(jù)點的個數(shù)為num，則分割函數(shù)FD(xi)為

其中，為第k維度下的數(shù)據(jù)值。

證明由于方差越大，該維度所帶的信息量越多。對于不同維度下方差相同的數(shù)據(jù)，di越大表明數(shù)據(jù)越離散，di越小表明數(shù)據(jù)越集中。因此，網(wǎng)格的劃分維度k可根據(jù)確定，并選取的最大值作為網(wǎng)格的劃分維度。又由于均值可以反映數(shù)據(jù)的整體傾向，因此，選取該維度下數(shù)據(jù)的均值作為數(shù)據(jù)劃分的網(wǎng)格分割函數(shù)。證畢。

2.2.2 網(wǎng)格的劃分

在獲取Gmax與Gmin這2 個數(shù)據(jù)網(wǎng)格之后，由于分割函數(shù)只能對數(shù)據(jù)集進行粗略劃分，無法對相似度較大的數(shù)據(jù)進行網(wǎng)格劃分，導致無法獲取網(wǎng)格單元。因此，需要對網(wǎng)格Gmax與Gmin進行進一步的數(shù)據(jù)劃分，獲取離散系數(shù)較小的網(wǎng)格單元，其具體過程如下。

1)提出數(shù)據(jù)的皮爾遜相關(guān)系數(shù)閾值PCCk。計算網(wǎng)格中數(shù)據(jù)點的PCCk值，以PCCk值作為網(wǎng)格劃分閾值對數(shù)據(jù)網(wǎng)格進行劃分，通過比較數(shù)據(jù)的皮爾遜相關(guān)系數(shù)與PCCk的大小，將系數(shù)大于PCCk的數(shù)據(jù)標記為core，系數(shù)小于PCCk的數(shù)據(jù)標記為uncore。

2)將網(wǎng)格中2 種數(shù)據(jù)core 與uncore 分別劃分為2 個更小的網(wǎng)格，并取消標記。

3)對網(wǎng)格數(shù)據(jù)點個數(shù)進行判斷，如果數(shù)據(jù)點的個數(shù)大于網(wǎng)格單元的閾值maxNum，則返回步驟1)；否則停止對網(wǎng)格進行劃分。其中maxNum表示數(shù)據(jù)集的數(shù)據(jù)個數(shù)n與并行化節(jié)點Partition個數(shù)的比值。

4)將劃分好的網(wǎng)格單元進行標記，得到網(wǎng)格單元G1，G2，G3，…，Gm。

定理2皮爾遜相關(guān)系數(shù)閾值PCCk。設(shè)PCCi，j為任意2 個數(shù)據(jù)點的皮爾遜相關(guān)系數(shù)值，Gnum為網(wǎng)格單元的數(shù)據(jù)點個數(shù)，sum 為求和函數(shù)，ω為數(shù)據(jù)點的密度權(quán)重，則PCCk為

證明PCCi，j代表數(shù)據(jù)點之間的關(guān)聯(lián)程度，即PCCi，j越大，數(shù)據(jù)點之間的相似度越大。將式(11)代入式(10)可得的大小反映了數(shù)據(jù)的離散化程度，其值越大，則數(shù)據(jù)越離散；其值越小，則數(shù)據(jù)越集中。因此的大小可以很好地對數(shù)據(jù)相似程度進行衡量，PCCk可以作為網(wǎng)格劃分的皮爾遜相關(guān)系數(shù)閾值。證畢。

2.2.3 離群點的過濾

在獲取網(wǎng)格單元G1，G2，G3，…，Gm后，由于網(wǎng)格單元存在離群點，會造成算法的抗干擾性差。因此，為了增強算法的可抗干擾性，設(shè)計離群因子GOF來過濾離群點，具體過程為：計算每個網(wǎng)格單元中數(shù)據(jù)的GOF值，若GOF值遠大于ε（網(wǎng)格單元數(shù)據(jù)閾值），則將該數(shù)據(jù)點視為離群點，并對其進行刪除。

定理3離群因子GOF。假設(shè)d(xi，xj)表示網(wǎng)格中2 個數(shù)據(jù)點的歐氏距離，表示網(wǎng)格單元的中心點，則離群因子GOF為

證明d表示當前網(wǎng)格中某一數(shù)據(jù)點與其余的m-1個數(shù)據(jù)點的歐氏距離，其大小可以表示網(wǎng)格的密度。d越小表明網(wǎng)格的密度越大，d越大表明網(wǎng)格的密度越小。表示當前數(shù)據(jù)點到網(wǎng)格中心的距離。對于離群點來說，其值會相對于其他數(shù)據(jù)點更大。如果數(shù)據(jù)點的GOF值遠大于ε，則可以將此數(shù)據(jù)點過濾，因此，可以用GOF來過濾網(wǎng)格的離群點。證畢。

數(shù)據(jù)劃分的偽代碼如算法1 所示。

算法1數(shù)據(jù)劃分

輸入初始數(shù)據(jù)集S

輸出數(shù)據(jù)網(wǎng)格單元G1，G2，G3，…，Gm

2.3 局部聚類

目前在大數(shù)據(jù)環(huán)境下的劃分聚類算法中，對數(shù)據(jù)的局部聚類需要對網(wǎng)格單元的數(shù)據(jù)進行質(zhì)心初始化，再結(jié)合并行化計算完成局部聚類。然而，在實現(xiàn)質(zhì)心初始化的過程中，由于無法確定局部聚類的簇數(shù)，導致不能更好地確定初始質(zhì)心集的個數(shù)，無法實現(xiàn)較優(yōu)的初始質(zhì)心。因此，為了獲取局部聚類的簇數(shù)，更好地實現(xiàn)初始化質(zhì)心，完成并行化局部聚類，提出LC 策略，其具體過程包括3 個步驟：局部聚類簇數(shù)獲取、局部簇質(zhì)心初始化、局部簇并行化計算。

2.3.1 局部聚類簇數(shù)獲取

為了有效地實現(xiàn)局部聚類，需要優(yōu)先獲取局部聚類的簇數(shù)，因此本文提出了PFGF 策略，通過勢函數(shù)與高斯核函數(shù)來完成數(shù)據(jù)的覆蓋與搜索，獲取局部聚類的簇數(shù)。其具體過程為：首先，對數(shù)據(jù)集中任意一對數(shù)據(jù)xi和xj通過式(1)計算其作用勢γ(xi，xj)，并以xi為基準樣本，將其他的樣本點對xj的作用勢進行累加，得到每個樣本點的作用勢集合為ρ={ρ1，ρ2，…，ρn}；其次，為了對原始數(shù)據(jù)進行全局搜索，從ρ中選擇最大作用勢ρi放入一個空的集合M{}中，并以ρi為當前的高斯核中心，以給定的核寬σ建立相應(yīng)的高斯核來對原始數(shù)據(jù)的一個局部區(qū)域有效覆蓋；最后，為了尋找新的最大勢值，需要消除當前高斯核所覆蓋的局部區(qū)域的樣本勢值，提出基于高斯核函數(shù)的更新函數(shù)FU(xi，yj)對數(shù)據(jù)集中的其他樣本點進行更新。

定理4更新函數(shù)FU(xi，yj)。假設(shè)當前的高斯核中心為ρi，集合中的樣本點為ρj，則其更新函數(shù)FU(xi，yj)為

其中，σk表示核寬，表示高斯內(nèi)核。

證明由高斯核函數(shù)的衰減特性可知，當樣本點距離高斯核中心較遠時，xj對xi的影響十分小，又由于表示高斯內(nèi)核，因此S中各個樣本點的勢值都可以有效更新。證畢。

2.3.2 局部簇質(zhì)心初始化

在獲取了局部聚類的簇數(shù)之后，為了解決局部簇質(zhì)心隨機性的問題，本文提出了策略ASPSO。該策略主要包括2 個階段：自適應(yīng)參數(shù)確定、質(zhì)心初始化。自適應(yīng)參數(shù)確定階段提出AS 策略，引入柯西變異算子，設(shè)置粒子平均速度與η來作為自適應(yīng)參數(shù)；質(zhì)心初始化階段通過AS 策略與PSO 算法相結(jié)合，并根據(jù)自適應(yīng)參數(shù)，對粒子的速度與位置不斷更新，跳出局部最優(yōu)，獲取初始化質(zhì)心。

1)自適應(yīng)參數(shù)確定

在實現(xiàn)質(zhì)心初始化的過程中，提出了粒子的收斂性，由此性質(zhì)可知粒子最終收斂于，算法將停止運行，如果算法沒有在收斂之前得到全局最優(yōu)解，就會導致過早收斂，陷入局部最優(yōu)解。

因此，為了實現(xiàn)初始質(zhì)心的全局最優(yōu)解，需要設(shè)計自適應(yīng)參數(shù)來避免局部最優(yōu)。為此，PDC-SFASPSO 算法設(shè)計了AS 策略，來確定自適應(yīng)參數(shù)，其具體過程如下。

定理6粒子群體平均速度。已知粒子的個數(shù)為n，粒子的速度為vk，i，則粒子的平均速度為

證明由于在初始階段，粒子的平均速度較大，隨著粒子位置的不斷更新，由可知，粒子速度不斷減小，導致平均速度相對減小，群體也開始慢慢收斂，即其平均速度的變化的趨勢與收斂的趨勢是一致的，因此選取平均速度作為控制變異步長的自適應(yīng)參數(shù)。證畢。

② 提出柯西變異算子的離散性。由此性質(zhì)可知，柯西分布具有比高斯分布更加離散的取值，更有利于算法跳出局部最優(yōu)。因此，AS 策略引入的變異算子為柯西變異算子，并將其與參數(shù)結(jié)合，根據(jù)式(17)對陷入局部最優(yōu)的粒子進行位置更新，跳出局部最優(yōu)。

證明由于f(x)與g(x)都是以x=μ對稱，因此要證明f(x)＞g(x)，只需證明當x＞N時，f(x)＞g(x)即可。令顯然存在N＞ 0時，使W(x)＞ 0，即，即可知f(x)＞g(x)，證畢。

③設(shè)計邊界限制參數(shù)η。由于C(1)是引入的柯西算子，是由t=1 的柯西分布函數(shù)產(chǎn)生的隨機數(shù)，并不能得到有效搜索區(qū)域，因此，在進行數(shù)據(jù)集搜索時，對搜索區(qū)域進行邊界限制，只對滿足邊界限制參數(shù)η的數(shù)據(jù)區(qū)域進行搜索。

定理8邊界限制參數(shù)。假設(shè)x0為xi的中位數(shù)，和分別表示xi左側(cè)和右側(cè)的尺度參數(shù)，則參數(shù)η為

對于任意的x，滿足

證明由于x0為xi的中位數(shù)，即(x-x0)2的均值表示粒子位置維度的2 階中心矩，減少了粒子的離散化程度和噪聲的影響。可以有效防止參數(shù)η過大而影響算法2 的收斂。而由于x滿足

2)質(zhì)心初始化

在通過AS 策略進行自適應(yīng)參數(shù)選取，保證不會陷入局部最優(yōu)解之后，便可以進行質(zhì)心的初始化。其具體過程如下。

①將每個網(wǎng)格單元的數(shù)據(jù)看作一群粒子S1，S2，…，Sm，并通過式(3)～式(5)對其進行初始化。

③計算參數(shù)η的值，獲取有效搜索區(qū)域，根據(jù)更新的適應(yīng)值，結(jié)合式(6)與式(7)在有效搜索區(qū)域中對粒子的速度與粒子的位置進行更新。

局部聚類的偽代碼如算法2 所示。

算法2局部聚類

輸入初始數(shù)據(jù)集S，粒子的初始位置x和始速度v，簇數(shù)K，自適應(yīng)參數(shù)

輸出質(zhì)心數(shù)據(jù)集

2.3.3 局部簇并行化計算

在對網(wǎng)格單元的數(shù)據(jù)質(zhì)心初始化之后，便需要對網(wǎng)格單元進行并行化合并，獲取局部簇，實現(xiàn)局部并行化聚類。因此，本文提出并行化局部聚類策略SPPLCS，實現(xiàn)對局部簇的并行化計算來完成整個局部聚類的過程。其基本步驟如下。

1)將各個網(wǎng)格單元G1，G2，G3，…，Gm分配到Partition。

2.4 局部簇合并

為了解決局部簇并行化合并效率低的問題，本文提出了局部簇合并策略CRNN，該策略結(jié)合Spark計算框架將相似度大的簇進行合并，提高了局部簇并行化合并效率。其主要步驟如下。

2)對于簇Ci，Cj，通過鄰居節(jié)點集疏密程度判斷2 個簇之間的親密程度，并分別計算出2 個簇的樣本點數(shù)ni，nj，提出簇的相似性函數(shù)CSM(ni，nj)，計算出簇與簇之間的相似度。

定理9簇的相似性函數(shù)。設(shè)nei和nej分別為Ci和Cj之間的鄰居節(jié)點和非鄰居節(jié)點的個數(shù)，ni和nj分別為簇和簇的樣本點的個數(shù)，則簇的相似性函數(shù)表示為

局部簇合并的偽代碼如算法3 所示。

算法3局部簇并行化合并

輸入局部簇

輸出局部簇的并行化合并

2.5 算法時間復雜度分析

PDC-SFASPSO 算法的時間復雜度主要由網(wǎng)格單元的獲取、局部簇的形成以及局部簇的并行化合并三部分構(gòu)成，時間復雜度分別如下。

1)網(wǎng)格單元的獲取階段的時間復雜度主要取決于數(shù)據(jù)集的粗略劃分、網(wǎng)格劃分、網(wǎng)格單元的離群點過濾。設(shè)數(shù)據(jù)集的樣本點數(shù)為n，維度數(shù)為m，網(wǎng)格單元個數(shù)為p，Partition 數(shù)為r，則網(wǎng)格單元的獲取階段的時間復雜度為

2)局部簇的形成階段的時間復雜度主要取決于簇數(shù)的獲取、質(zhì)心初始化、局部并行化聚類。設(shè)有q個局部區(qū)域覆蓋，g個全局最優(yōu)值，w個有效搜索區(qū)域，即粒子的自適應(yīng)平均速度只需迭代w次，對于參數(shù)η便只需更新lgw次，令最大迭代次數(shù)為Iter，則局部簇的形成階段的時間復雜度為

3)局部簇的并行化合并階段的時間復雜度主要取決于計算簇半徑與鄰居節(jié)點，通過相似度進行簇的并行化合并。假設(shè)簇數(shù)為k，分布式節(jié)點數(shù)為d，則其時間復雜度為

綜上可知，PDC-SFASPSO 算法的時間復雜度為

其中，w?n，因此nw?n2。由于g?n，r?n，d?n，k?n，因此最終的時間復雜度近似為

SP-DAP 算法對劃分后的數(shù)據(jù)進行并行化聚類階段的時間復雜度為。由于該算法并沒有計算出局部聚類簇數(shù)，導致沒有較優(yōu)的初始化質(zhì)心，因此并行化聚類的迭代次數(shù)要遠大于 PDC-SFASPSO 算法。因此，而O(n2lgn)?，因此，PDC-SFASPSO 算法的時間復雜度要低于SP-DAP 算法。

對于SP-GAKMS 算法，由于該算法在使用群智能算法初始化質(zhì)心時，會導致陷入局部最優(yōu)，并不能獲取較優(yōu)的初始質(zhì)心。因此，其算法的迭代次數(shù)也遠大于PDC-SFASPSO 算法，導致并行化聚類階段的時間復雜度。所以，PDC-SFASPSO算法的時間復雜度低于SP-GAKMS 算法。

對于SP-LCMNS算法，設(shè)對邊的迭代次數(shù)為e，則該算法的數(shù)據(jù)劃分的時間復雜度為(2)O n e，在對數(shù)據(jù)集進行并行化聚類時，僅僅使用了二次劃分算法進行優(yōu)化，并未在并行化聚類之前對數(shù)據(jù)集進行簇的生成，導致了并行化聚類的迭代次數(shù)增多。因此該階段的時間復雜度為

其中，Iter′?Iter，u?q，故PDC-SFASPSO 算法的時間復雜度要低于SP-GAKMS 算法。

綜上可知，相較于SP-DAP 算法、SP-GAKMS算法與SP-LAICA 算法，PDC-SFASPSO 算法有更理想的時間復雜度。

3 實驗與分析

3.1 實驗環(huán)境

為了驗證PDC-SFASPSO 算法的性能，本文設(shè)計了相關(guān)實驗。在硬件方面，實驗包括4 個計算節(jié)點，即一個master 節(jié)點和3 個worker 節(jié)點，并修改主機名分別為master、salve_1、salve_2、salve_3。所有節(jié)點的CPU 均為Inter Core i5，2.50 GHz 四核CPU，16 GB 內(nèi)存，512 GB 存儲磁盤。實驗環(huán)境中的4 個節(jié)點處于同一個局域網(wǎng)中，所有的計算節(jié)點通過1 Gbit/s 以太網(wǎng)相連。在軟件方面，使用CentOS6.0系統(tǒng)安裝Hadoop 2.7.7，從而配置Hadoop集群，對每個節(jié)點都安裝JDK1.8.0 并完成節(jié)點的集群配置。安裝Hive1.1.2 與Spark2.2.0，使用Hive將HDFS中的數(shù)據(jù)進行分析和管理。在Spark 并行計算框架的基礎(chǔ)上，使用Scala 編程語言對數(shù)據(jù)進行處理，并將處理好的數(shù)據(jù)導入集群。最后使用Superset 對集群中處理好的數(shù)據(jù)進行可視化處理。各個節(jié)點的具體配置如表1 所示。

表1 實驗中節(jié)點的配置

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

本節(jié)實驗采用4 個真實的數(shù)據(jù)集，分別是Online Retail、N_BaloT、Health News 及Bag words[20]。其中，Online Retail 數(shù)據(jù)集包含非商店在線零售的所有交易；N_BaloT 是從9 臺商業(yè)物聯(lián)網(wǎng)設(shè)備收集的真實數(shù)據(jù)；Health News 包含來自超過15 個主要健康新聞機構(gòu)的健康新聞；Bag words 包含5 個文本集合。這些數(shù)據(jù)集的詳細信息如表2 所示。

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

3.3 評價指標

3.3.1 加速比

加速比是通過并行計算來降低總體運行時間而獲得的性能提升的數(shù)值化表示形式，其定義為

其中，T1表示算法在單節(jié)點上的運行時間；Tp表示并行計算的運行時間；Sp越大，表示算法的并行化效率越高。

3.3.2 NMI

標準互信息（NMI，normalized mutual information）通過對信息進行量化度量，并根據(jù)2 個概率分布的信息熵的差值進行聚類的效果評估，其定義為

其中，X和Y為N維向量，I(X，Y)表示X和Y之間的互信息，H(X)和H(Y)分別表示X和Y的熵；NMI 值越大，聚類效果越好。

3.3.3 ARI

調(diào)整蘭德指數(shù)（ARI，adjusted Rand index）是通過將模型的超分布假設(shè)為隨機模型從而用于聚類模型的性能評估，該評價指標具有更高的區(qū)分度，其定義為

3.4 PSO 算法的優(yōu)越性分析

文獻[21]中MSPSO 算法通過保留粒子歷史最優(yōu)位置，重新初始化其他粒子，提高了粒子多樣性，擴大了搜索空間，從而獲取全局最優(yōu)解。因此，為驗證ASPSO 算法的優(yōu)越性，本文選取MSPSO 算法、PSO算法、ASPSO 算法在4 個不同基準函數(shù)（Sphere、Schwefel、Ackely、Griewank）進行仿真實驗，函數(shù)的具體信息如表3 所示。算法參數(shù)設(shè)置如下：采用線性下降慣性權(quán)重，并且w在[0.35，0.95]內(nèi)取值隨迭代數(shù)增加而線性遞減。學習因子c1和c2均為1.5，種群規(guī)模為40，函數(shù)維度為30，收斂閾值ε設(shè)置為10-5，邊界值vmax為0.5Range，并設(shè)置ASPSO 算法的尺度參數(shù)為[-100，100]。為對算法進行統(tǒng)計算分析，將每個函數(shù)獨立運行50 次，其結(jié)果如表4 所示。

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

表4 ASPSO 算法與PSO 算法的性能對比

從表4 可以看出，ASPSO 算法的平均值與標準差始終低于PSO 算法與MSPSO 算法，ASPSO算法在收斂精度和應(yīng)用在不同類型函數(shù)的穩(wěn)定性方面明顯優(yōu)于PSO 算法與MSPSO 算法。尤其是在高維多峰函數(shù)f3與f4上，PSO 算法的標準差分別為6.332 與3.289，很顯然，未優(yōu)化的PSO 算法所在的搜索區(qū)域有多個極值點，且快速收斂陷入了局部最優(yōu)解，相較于標準差仍保持理論較優(yōu)的ASPSO 算法，其全局搜索能力與穩(wěn)定性明顯遠低于ASPSO 算法。這是因為ASPSO 算法采用了AS策略，設(shè)計了控制變異步長參數(shù)與邊界限制參數(shù)，對粒子位置進行更新，

幫助粒子跳出局部最優(yōu)，獲取全局最優(yōu)解。從函數(shù)f1與f2可以看出，ASPSO 算法的標準差接近理論最優(yōu)值0，具有較高的收斂精度，極大地體現(xiàn)了ASPSO 算法較強的跳出局部極值能力和較好的全局搜索能力。實驗表明，在全局尋優(yōu)能力和算法穩(wěn)定程度方面，ASPSO 算法明顯比傳統(tǒng)PSO 算法具有更好的優(yōu)越性。

3.5 聚類過程性分析

由于Bag words 數(shù)據(jù)集具有樣本數(shù)量多、屬性多的特點。因此，選取Bag words 數(shù)據(jù)集對算法進行聚類過程性分析。算法首先采用PCCV 策略對數(shù)據(jù)集進行劃分，獲取網(wǎng)格單元。由于數(shù)據(jù)集包含多維特征屬性，聚類效果不易觀測，因此將數(shù)據(jù)網(wǎng)格單元投影到二維空間進行演示。其中圖1 展示了部分網(wǎng)格單元數(shù)據(jù)點的分布。然后，通過ASPSO算法獲取各個數(shù)據(jù)網(wǎng)格單元的質(zhì)心點集，通過SPPLCS 策略將質(zhì)心點與其他網(wǎng)格單元中心距離最近的2 個數(shù)據(jù)網(wǎng)格單元進行并行化合并，獲取局部簇，圖2 展示了部分局部簇數(shù)據(jù)點的分布。最后，采用CRNN策略計算出各個簇之間的鄰居節(jié)點數(shù)，依據(jù)鄰居節(jié)點數(shù)，并結(jié)合CSM(ni，nj)函數(shù)對簇的相似性進行判斷，將相似度大的局部簇進行合并，從而完成并行化聚類。圖3 顯示了第一輪2 個簇合并的數(shù)據(jù)點。

圖1 網(wǎng)格單元數(shù)據(jù)集分布

圖2 局部數(shù)據(jù)點的分布

圖3 第一輪2 個簇合并的數(shù)據(jù)點

3.6 算法可行性分析與并行化效率比較

為了驗證PDC-SFASPSO 算法的可行性并比較各個算法之間的并行化效率，使用算法的加速比來進行衡量。并對每一個數(shù)據(jù)集都運行20 次，取其均值作為實驗結(jié)果，如圖4 所示。

圖4 各算法處理各數(shù)據(jù)集的加速比

從圖4 可以看出，PDC-SFASPSO 在節(jié)點數(shù)達到4 時，加速比最大，并且在各個數(shù)據(jù)集上PDCSFASPSO 的加速比隨著節(jié)點數(shù)的增多而不斷增大，尤其是在Online Retail 數(shù)據(jù)集上，PDC-SFASPSO 的加速比的增長趨勢更加明顯，很好地體現(xiàn)了PDC-SFASPSO 的并行化可行性。其中，當節(jié)點數(shù)達到4 時，在Online Retail 數(shù)據(jù)集上，PDC-SFASPSO的加速比相較于SP-DAP 算法、SP-GAKMS 算法和SP-LAICA 算法分別增加了0.3、0.28、0.4；在N_BaloT數(shù)據(jù)集上，PDC-SFASPSO 的加速比相較于SP-DAP算法、SP-GAKMS 算法和SP-LAICA 算法分別增加了 0.3、0.26、0.4；在 Bag words 數(shù)據(jù)集上，PDC-SFASPSO 的加速比相較于SP-DAP 算法、SP-GAKMS 算法和SP-LAICA 算法分別增加了0.03、0.02、0.1。產(chǎn)生這些結(jié)果的原因如下：一方面，PDC-SFASPSO 采用了PCCV 策略，解決了數(shù)據(jù)間離散系數(shù)較大與算法抗干擾性差的問題，間接地提高了聚類的并行化效率；另一方面，算法在并行化合并階段設(shè)計了相似性函數(shù)CSM(ni，nj)進行相似度判斷，極大地提高了局部簇并行化合并的效率。因此，在4 種數(shù)據(jù)集中，PDC-SFASPSO 相較于其他3 種算法具有最佳的并行化效率且具有可行性。

3.7 聚類效果與算法性能比較分析

在目前基于Spark 計算框架的并行聚類算法中，SP-DAP 算法[7]、SP-GAKMS[10]算法和SP-LAICA算法[15]在對數(shù)據(jù)集進行并行化聚類時，分別在數(shù)據(jù)集劃分階段、局部聚類階段與局部簇并行化合并階段進行了算法的優(yōu)化，解決了數(shù)據(jù)離散系數(shù)較大、局部簇質(zhì)心隨機性以及局部簇并行化合并效率低等問題，從而極大地提高了算法的聚類效果，相較于大多數(shù)基于Spark 的并行聚類算法有著更優(yōu)的聚類效果、并行效率和時間效率等性能，因此本文選擇這3 種算法與提出的PDC-SFASPSO 算法進行聚類效果、并行效率與時間效率等比較與分析。

3.7.1 聚類效果比較分析

1)NMI 值比較

使用NMI 作為衡量指標評價算法的聚類效果，分別比較各個算法在不同數(shù)據(jù)集上的NMI 值，從而對各個算法的聚類效果進行分析。因此，為了驗證PDC-SFASPSO 算法的聚類效果，將4 種算法在上述4 種數(shù)據(jù)集上進行比較，通過比較NMI 值來體現(xiàn)算法的聚類效果，并分別運行10 次得出聚類結(jié)果，取其聚類結(jié)果均值并結(jié)合一定的誤差范圍作為實驗結(jié)果。實驗結(jié)果如表5 所示。

表5中的數(shù)據(jù)表明，在聚類效果方面，各算法的NMI 值隨著數(shù)據(jù)集的特征屬性增多而不斷減小，PDC-SFASPSO 算法在4 種數(shù)據(jù)集上始終表現(xiàn)得最好。其中，在Online Retail 數(shù)據(jù)集中，PDC-SFASPSO 算法的NMI 值相比于SP-DAP、SP-GAKMS和SP-LAICA算法分別高出了3.2%、4.9%和2.9%；在N_BaloT 數(shù)據(jù)集上，分別高出了7.3%、8.4%和9.3%。產(chǎn)生這種結(jié)果的主要原因是PDC-SFASPSO 采用PCCV 策略解決了數(shù)據(jù)離散系數(shù)較大與算法抗干擾性差的問題，并且在對局部簇質(zhì)心進行初始化時，提出了策略ASPSO，獲取了全局最優(yōu)初始質(zhì)心，解決了局部簇質(zhì)心隨機性的問題，極大地提高了聚類效果。

表5 各算法處理數(shù)據(jù)集的NMI 值

2)ARI 值比較

為了進一步驗證PDC-SFASPSO 算法的聚類效果，使用ARI 作為衡量指標評價算法的聚類效果，將4 種算法分別在上述4 種數(shù)據(jù)集上進行處理，并分別運行10 次得出聚類結(jié)果，取其聚類結(jié)果均值作為實驗結(jié)果，如圖5 所示。

從圖5 可以看出，在對各數(shù)據(jù)集進行處理時，PDC-SFASPSO 算法的ARI 值始終保持最高，并且隨著數(shù)據(jù)集的特征屬性增多，PDC-SFASPSO 的ARI值與其他3 種算法的ARI 值相比較，PDC-SFASPSO算法的優(yōu)勢更加明顯。尤其是在Bag words 數(shù)據(jù)集上，PDC-SFASPSO 憑借著設(shè)計了PFGF 策略，其ARI 值遠高于SP-LAICA。在Online Retail 數(shù)據(jù)集上PDC-SFASPSO 算法的ARI 值相比于SP-DAP 算法、SP-GAKMS 算法和SP-LAICA 算法分別高0.02、0.03和0.04，在Bag words 數(shù)據(jù)集上分別高0.06、0.10和0.12。產(chǎn)生這些結(jié)果的主要原因是PDC-SFASPSO算法設(shè)計了ASPSO 策略獲取局部簇質(zhì)心，解決了局部簇質(zhì)心的隨機性問題。并且PDC-SFASPSO 算法在初始化質(zhì)心之前，設(shè)計了PFGF 策略來獲取局部聚類的簇數(shù)，解決了算法局部簇簇數(shù)難以確定的問題，從而提高了算法的聚類效果。因此，通過對比算法在 4 種數(shù)據(jù)集上的 ARI 值可以看出，PDC-SFASPSO 算法具有最佳的聚類效果。

3.7.2 性能比較分析

1)抗干擾性比較

為了驗證PDC-SFASPSO 與其他3 種算法在大數(shù)據(jù)集下并行化聚類的抗干擾性，通過利用Sklearn中的函數(shù)生成一種具有缺失值的噪聲數(shù)據(jù)集，將其分成多份，分別依次加入上述4 種數(shù)據(jù)集中。將ARI 值作為評價指標，對加入含有缺失值噪聲數(shù)據(jù)的算法的聚類效果進行比較。通過比較算法的聚類效果來對算法的可抗干擾性進行分析，算法聚類效果越好，則算法受噪聲數(shù)據(jù)的影響越小，即算法的可抗干擾性越好[14]。實驗結(jié)果如圖6 所示。

從圖6 可以看出，隨著噪聲數(shù)據(jù)的不斷增加，各算法的ARI 值逐漸減小，PDC-SFASPSO 在4 種數(shù)據(jù)集中的ARI 值始終保持最高，具有更好的聚類效果，并且噪聲數(shù)據(jù)越多，PDC-SFASPSO 算法的抗干擾能力相較于其他3種算法優(yōu)勢越加明顯。其中，當噪聲數(shù)據(jù)達到50%時，在Online Retail 數(shù)據(jù)集上，PDC-SFASPSO的ARI值相較于SP-DAP、SP-GAKMS和SP-LAICA 算法分別高21%、27%、33.3%；在Bag words 數(shù)據(jù)集上，PDC-SFASPSO 的ARI 值分別高32.3%、49.1%、40.9%。產(chǎn)生這些結(jié)果的主要原因是由于最開始沒有加入噪聲數(shù)據(jù)，ARI 值達到最大，當加入噪聲數(shù)據(jù)后，算法的ARI 值會因為噪聲數(shù)據(jù)的突然加入，呈現(xiàn)快速下降的趨勢，因此在噪聲數(shù)據(jù)為20%～40%時，算法的ARI 值下降最快。而PDC-SFASPSO 算法由于設(shè)計了PCCV 策略，提高了算法的聚類效果，并通過設(shè)計離群因子GOF來對離群點過濾，減小了噪聲數(shù)據(jù)對算法聚類效果的影響，極大地增強了算法的抗干擾能力。同時，通過對比圖6(b)～圖6(d)可以看出，隨著噪聲數(shù)據(jù)的不斷增加，PDC-SFASPSO 算法的ARI 值一直保持最優(yōu)，這也證明了PDC-SFASPSO 算法具有最佳的抗干擾性。

圖6 算法處理各數(shù)據(jù)集的ARI

2)算法運行時間比較

將PDC-SFASPSO、SP-DAP、SP-GAKMS 與SP-LAICA 算法分別在Online Retail、N_BaloT、Health News 及Bag words 數(shù)據(jù)集上進行對比實驗，分析各個算法的運行時間，實驗結(jié)果如圖7 所示。

圖7 算法在各個數(shù)據(jù)集上的運行時間

從圖7 可以看出，隨著數(shù)據(jù)集的屬性與數(shù)據(jù)量的增多，算法運行的時間開銷也逐漸增大。并且PDC-SFASPSO 算法在4 種數(shù)據(jù)集上的運行時間始終最低。其中，在Health News 數(shù)據(jù)集上，相較于Online Retail 數(shù)據(jù)集算法的時間開銷產(chǎn)生了明顯的增長，分別增加了38.2%、73.5%、79.6%、85.9%，然而對于PDC-SFASPSO 算法，其時間消耗增加的始終較為平緩。產(chǎn)生此結(jié)果的主要原因是PDC-SFASPSO 算法使用了網(wǎng)格劃分策略PCCV 解決了數(shù)據(jù)間離散系數(shù)較大的問題與算法抗干擾性差的問題，從而提高了算法的聚類效果，間接地提高了并行化合并效率；此外，在并行化階段，PDC-SFASPSO 算法設(shè)計了CRNN 策略，極大地減小了聚簇時間消耗，解決了局部簇并行化合并效率低的問題。因此，PDC-SFASPSO 算法在各個數(shù)據(jù)集上相對于其他3 種算法時間消耗始終處于最低。

4 結(jié)束語

針對傳統(tǒng)的劃分聚類算法在大數(shù)據(jù)環(huán)境下的不足，本文提出了一種基于Spark 框架和ASPSO 策略下的并行劃分聚類算法PDC-SFASPSO。該算法在數(shù)據(jù)劃分階段提出了網(wǎng)格劃分策略，保證了劃分后的數(shù)據(jù)網(wǎng)格單元數(shù)據(jù)離散系數(shù)較小，并設(shè)計了離群因子過濾網(wǎng)格單元數(shù)據(jù)，增強了數(shù)據(jù)的抗干擾性；使用基于PFGF 的搜索策略對數(shù)據(jù)進行核覆蓋搜索獲取局部簇簇數(shù)，并提出ASPSO 優(yōu)化算法，通過自適應(yīng)參數(shù)避免算法陷入局部最優(yōu)解從而獲取全局最優(yōu)質(zhì)心；提出了局部簇并行化合并策略CRNN，通過避免對所有簇的點與邊集同時展開搜索而提高算法局部簇的并行化合并效率。為了驗證PDC-SFASPSO算法的性能，本文設(shè)計了相關(guān)實驗，在Online Retail、N_BaloT、Health News和Bag words 數(shù)據(jù)集上將PDC-SFASPSO 算法分別與SP-DAP、SP-GAKMS和SP-LAICA 算法進行比較。實驗結(jié)果顯示，與其他算法相比，PDC-SFASPSO 算法在處理大數(shù)據(jù)時具有相對較好的性能表現(xiàn)。但是，該算法仍有一些需要改進及完善的地方，如數(shù)據(jù)的特征約簡與負載平衡等問題，這些都是下一步重點研究的問題。