史愛(ài)武，尹杰，范平

（1.武漢紡織大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院，武漢 430000；2.湖北科技學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，咸寧 437000）

0 引言

數(shù)據(jù)采集存儲(chǔ)技術(shù)快速發(fā)展積累了大量數(shù)據(jù)，對(duì)數(shù)據(jù)深入分析并指導(dǎo)實(shí)踐成為迫切需要，基于此大數(shù)據(jù)研究成為近年來(lái)研究熱點(diǎn)。聚類分析是數(shù)據(jù)挖掘中的分支，來(lái)源于多研究領(lǐng)域，包括統(tǒng)計(jì)學(xué)、機(jī)器學(xué)習(xí)、模式識(shí)別等。其可以輔助分類研究，應(yīng)用在生物學(xué)、地理信息學(xué)、商業(yè)分析、互聯(lián)網(wǎng)搜索等領(lǐng)域。DBSCAN 算法是基于密度的聚類算法，它具備抗噪聲能力，能夠在具有噪聲的數(shù)據(jù)集中發(fā)現(xiàn)任意形狀類簇，有較好的聚類效果[1]。但DBSCAN 算法依然存在缺陷：算法在聚類中迭代計(jì)算，需要大規(guī)模內(nèi)存磁盤(pán)I/O 交互，降低了計(jì)算速率；算法需要人工干預(yù)確定閾值，且對(duì)初始參數(shù)大小有敏感性，參數(shù)選定不準(zhǔn)確，易降低聚類準(zhǔn)確率；對(duì)不同數(shù)據(jù)集分布，特別是密度分布不均勻的樣本集，采用全局閾值，對(duì)樣本核心點(diǎn)，邊界點(diǎn)和噪聲點(diǎn)的劃分會(huì)存在偏差，降低聚類準(zhǔn)確率；對(duì)分布分散程度不高的數(shù)據(jù)集，全局閾值會(huì)造成不同簇類合并成同一簇類，降低聚類準(zhǔn)確率。針對(duì)以上問(wèn)題，許多學(xué)者對(duì)DBSCAN 算法進(jìn)行研究及改進(jìn)。

周水庚等人[2]提出矩形分區(qū)局部聚類策略；邱寧佳等人[3]提出基于MapReduce 的GA-DBSCAN 算法，胡贏雙等人[4]提出基于MapReduce 網(wǎng)格劃分強(qiáng)連通聚類算法；黃明吉等人[5]提出樣本數(shù)據(jù)量劃分策略和Spark并行化，計(jì)算速率有所提升，但存在網(wǎng)格劃分，數(shù)據(jù)量劃分等方法不能相對(duì)較高契合多密度不均勻聚類，準(zhǔn)確率有所下降。韓利釗等[6]提出網(wǎng)格合并方法，可靈活定位不均勻數(shù)據(jù)劃分區(qū)域，但其需要確定Eps參數(shù)初值，且算法時(shí)間復(fù)雜度相對(duì)較高，效率相對(duì)較低；于亞飛等人[7]、宋金玉等人[8]提出DBSCAN 算法參數(shù)配置策略，利用距離k-dist矩陣以及概率密度分布曲線獲取參數(shù)值，提高參數(shù)自適應(yīng)性，但是該方法需要人工干預(yù)確定k值，不同k值對(duì)應(yīng)擬合曲線導(dǎo)數(shù)計(jì)算的大小不同；宋明等人[9]提出數(shù)據(jù)交替分區(qū)增量計(jì)算，田路強(qiáng)[10]提出分布式增量聚類，在提高聚類準(zhǔn)確率同時(shí)會(huì)出現(xiàn)數(shù)據(jù)增量合并效率偏低。

針對(duì)上述學(xué)者研究需要提升的方面，提出SDKBDBSCAN 聚類改進(jìn)算法，設(shè)計(jì)不規(guī)則動(dòng)態(tài)區(qū)域并行計(jì)算模型，采取過(guò)濾不規(guī)則邊界單元區(qū)域，指定不重疊區(qū)域的合并策略，應(yīng)用概率密度以及均值方法，搭建Spark 并行計(jì)算框架算法架構(gòu)。

1 基本理論內(nèi)容

1.1 DBSCAN算法

DBSCAN 算法基于密度對(duì)空間樣本形成類簇。在n維空間內(nèi)，以參數(shù)設(shè)定閾值半徑Eps以及閾值大小為聚類限定條件，將空間內(nèi)樣本點(diǎn)以迭代計(jì)算方式發(fā)現(xiàn)任意形狀類簇，過(guò)濾樣本數(shù)據(jù)集噪聲點(diǎn)，得到密度聚類結(jié)果。在n維樣本集中，列出算法相應(yīng)定義：

定義1Eps鄰域在n維空間內(nèi)對(duì)任意的樣本點(diǎn)p，以p為中心，Eps為半徑內(nèi)所有樣本點(diǎn)集合。即表示為式（1）：

其中Dist(p,q)表示p到q的距離，通常情況下，用Minkowski距離公式計(jì)算Dist，公式表示為式（2）：

定義2核心點(diǎn)在n維空間內(nèi)對(duì)任意樣本點(diǎn)p，滿足在以p為中心點(diǎn)的鄰域值不少于Minpts個(gè)樣本點(diǎn)。即表示為：，稱p為核心點(diǎn)；

定義3邊界點(diǎn)在n維空間內(nèi)存在一個(gè)p不屬于核心點(diǎn)，而且該點(diǎn)落在核心點(diǎn)的鄰域范圍內(nèi)，稱p點(diǎn)為邊界點(diǎn)；

定義4噪聲點(diǎn)在n維空間存在一個(gè)點(diǎn)p不屬于核心點(diǎn)，而且該點(diǎn)落在所有核心點(diǎn)的鄰域范圍之外，稱p點(diǎn)為噪聲點(diǎn)；

定義5直接密度可達(dá)在n維空間內(nèi)，若存在p在q的Eps鄰域范圍內(nèi)，并且q為核心點(diǎn)，可稱p是從q出發(fā)直接密度可達(dá)，不具有對(duì)稱性。

定義6密度可達(dá) 在n維空間內(nèi)，若存在數(shù)據(jù)集，滿足從pi出發(fā)到pi+1直接密度可達(dá)，那么可以說(shuō)是p1出發(fā)到pi+1是密度可達(dá)。不具有對(duì)稱性但具有傳遞性。

定義7密度相連在n維空間內(nèi)，若存在o，從點(diǎn)o出發(fā)到p密度可達(dá)，且從o出發(fā)到q密度可達(dá)，可稱p和q密度相連。具有對(duì)稱性，且p和q可以不屬于核心點(diǎn)。

1.2 Spark并行內(nèi)存計(jì)算框架

Apache Spark 是加州大學(xué)伯克利分校的AMP Lab實(shí)驗(yàn)室研究并開(kāi)發(fā)，發(fā)展為Apache 頂級(jí)項(xiàng)目。Spark 是內(nèi)存分布式計(jì)算引擎框架，在沿用MapReduce 計(jì)算引擎結(jié)構(gòu)基礎(chǔ)上，引入RDD（Resilient Distributed Dataset）分布式彈性數(shù)據(jù)集。執(zhí)行時(shí)數(shù)據(jù)映射到RDD 結(jié)構(gòu)中，發(fā)揮其內(nèi)存計(jì)算結(jié)構(gòu)特性以及在迭代計(jì)算中將數(shù)據(jù)反復(fù)緩存至內(nèi)存的特點(diǎn)，與MapReduce 將數(shù)據(jù)在內(nèi)存與硬盤(pán)I/O 轉(zhuǎn)換相較，提高十倍甚至百倍的計(jì)算速度[11]。

從RDD 依賴關(guān)系中，可對(duì)RDD 的操作分為邏輯傳遞的轉(zhuǎn)換操作和實(shí)際運(yùn)行的行動(dòng)操作，轉(zhuǎn)換操作不會(huì)立即執(zhí)行，要等行動(dòng)操作全觸發(fā)。用于并行操作重要的算子，包括Map、Reduce、Join、Foreach 等，對(duì)算法優(yōu)化起到關(guān)鍵作用。

Spark 整體架構(gòu)如圖1 所示。

圖1 Spark架構(gòu)圖

2 SDKB-DBSCAN改進(jìn)算法

2.1 不規(guī)則動(dòng)態(tài)密度區(qū)域劃分

網(wǎng)格劃分即設(shè)存在一個(gè)d維數(shù)據(jù)集S={s1,s2,…,sd}，S中各維數(shù)據(jù)表示為在第i維數(shù)據(jù)區(qū)間[ri,li)上i=1,2,..,d且各數(shù)據(jù)是有界的，則稱D=[r1,l1)×[r2,l2)×…×[rd,ld)為d維的數(shù)據(jù)空間。D維空間是不相交數(shù)據(jù)集，表示為數(shù)據(jù)各個(gè)屬性，對(duì)每一維數(shù)據(jù)空間劃分，可形成d維網(wǎng)格單元，網(wǎng)格單元是以左閉右開(kāi)的形式表示，其是d維空間基本劃分單元[9]。對(duì)于網(wǎng)格劃分，給出d維空間下每一維數(shù)據(jù)空間網(wǎng)格寬度的計(jì)算公式，表示為式（3）：

其中c為擴(kuò)充線性方程，適當(dāng)放縮網(wǎng)格寬度，找到合適的初始單元網(wǎng)格。計(jì)算各個(gè)維度的邊界差與樣本個(gè)數(shù)的比并取其最小值作為網(wǎng)格寬度的基準(zhǔn)。之后可確定各個(gè)數(shù)據(jù)維度網(wǎng)格數(shù)量并確定其網(wǎng)格索引[12]。表示為式（4）：

區(qū)域合并即初始網(wǎng)格單元后，在d維空間內(nèi)數(shù)據(jù)p是包含在某一個(gè)網(wǎng)格單元中，每一個(gè)網(wǎng)格單元由不同數(shù)據(jù)填充，可用每一個(gè)不相交的網(wǎng)格數(shù)據(jù)個(gè)數(shù)作為網(wǎng)格單元密度，den(f)表示密度大小。不規(guī)則分區(qū)算法偽代碼如下所示：

算法1 貪心策略廣度優(yōu)先搜索層次歸并算法

輸入：DataSet 數(shù)據(jù)集

輸出：partitionInfo 分區(qū)數(shù)據(jù)集

區(qū)域劃分是控制相鄰單元網(wǎng)格密度相對(duì)差比來(lái)合并網(wǎng)格單元，引入貪心策略，將問(wèn)題分解成若干子問(wèn)題，尋找未標(biāo)記索引對(duì)應(yīng)的密度最大值為核心網(wǎng)格單元，與相鄰網(wǎng)格單元計(jì)算密度相對(duì)差比[13]表示為式（5）：

將其作為判斷網(wǎng)格合并條件，初始核心與相鄰網(wǎng)格依次按上式計(jì)算，并將滿足d d()f,f0<ε條件，來(lái)確定相鄰網(wǎng)格歸屬。若滿足條件時(shí)，將相鄰網(wǎng)格與核心網(wǎng)格標(biāo)為一類，為減弱平均密度帶來(lái)的密度差比波動(dòng)，采取一種層次歸并算法，統(tǒng)一平均密度值，其表示為式（6）：

區(qū)域劃分采用廣度優(yōu)先搜索算法，不斷合并滿足條件的網(wǎng)格；不滿足條件時(shí)，相鄰單元網(wǎng)格標(biāo)記為邊界網(wǎng)格。將所有計(jì)算過(guò)的網(wǎng)格標(biāo)記為已搜索狀態(tài)，直到本次合并結(jié)束。若此時(shí)還有符合條件是未搜索狀態(tài)，則繼續(xù)求解子問(wèn)題，直至區(qū)域劃分結(jié)束。

2.2 區(qū)域自適應(yīng)參數(shù)局部聚類

數(shù)據(jù)區(qū)域劃分后，將不同區(qū)域數(shù)據(jù)分配到Spark 的RDD不同分區(qū)中。改進(jìn)算法優(yōu)化不同分區(qū)自適應(yīng)確定Eps和Minpts，一定程度減小密度不均勻數(shù)據(jù)所統(tǒng)一參數(shù)對(duì)聚類的影響。

改進(jìn)算法在自適應(yīng)確定參數(shù)上引入核密度估計(jì)理論。定義為：設(shè)X1,X2,…,Xn是從總體X中抽取的獨(dú)立同分布樣本，總體X有未知分布密度函數(shù)f(x),x∈R，則f(x)的核密度估計(jì)為式（7）：

式中函數(shù)K(u)為核函數(shù)，h是與n有關(guān)的正數(shù)，為光滑參數(shù)或者窗寬[14]。

設(shè)定不同h窗寬，可得到不同效果f(x)。h窗寬過(guò)小時(shí)，f(x)限制局部觀測(cè)數(shù)據(jù)，會(huì)得到過(guò)多錯(cuò)誤峰值，估計(jì)函數(shù)效果不理想，將h映射對(duì)應(yīng)自適應(yīng)Eps取值過(guò)小，會(huì)增加樣本成為噪聲概率，降低聚類準(zhǔn)確率；h窗寬過(guò)大時(shí)，f(x)過(guò)于光滑，無(wú)法去反映出正確的密度函數(shù)，同樣h窗寬對(duì)應(yīng)Eps取值過(guò)大，對(duì)于不同密度數(shù)據(jù)會(huì)錯(cuò)誤合并為同一類，降低聚類準(zhǔn)確率。

h窗寬的確定可影響Eps確定，改進(jìn)算法采用Gaussian做為核函數(shù)，最小化積分均方誤差MISE計(jì)算求得最優(yōu)h窗寬，獲取最優(yōu)Eps[15]。MISE表示為式（8）：

其中可將AMISE(h)表示為漸進(jìn)積分均方差誤差，表示為式（9）：

求解最優(yōu)h窗寬，即需要AMISE(h)誤差值取得最小，因此對(duì)上式求偏導(dǎo)數(shù)可得式（10）：

數(shù)據(jù)樣本總體服從方差為σ2的正態(tài)分布，用高斯核函數(shù)，代入式（10）可得式（11）：

由此可得自適應(yīng)下最優(yōu)Eps。

自適應(yīng)確定Minpts采用在分區(qū)中每個(gè)Eps鄰域范圍內(nèi)樣本個(gè)數(shù)的均值策略，表示為式（12）：

其中Num即表示在每個(gè)Eps鄰域范圍內(nèi)所包含樣本數(shù)量，將上式定義到并行結(jié)構(gòu)中內(nèi)存計(jì)算。

2.3 自定義聚類合并策略

區(qū)域劃分以及分區(qū)自適應(yīng)確定參數(shù)并行計(jì)算后，給出自定義策略將局部聚類結(jié)果合并，形成最終全局聚類[16]。改進(jìn)合并策略采用對(duì)各分區(qū)下不規(guī)則邊界網(wǎng)格單元中樣本進(jìn)行局部合并。具體分為以下幾點(diǎn)：

（1）設(shè)在兩個(gè)分區(qū)C1,C2的邊界網(wǎng)格上分別對(duì)應(yīng)樣本P1,P2，若P1,P2分別在對(duì)應(yīng)分區(qū)上為其自適應(yīng)確定下Eps的核心點(diǎn)，并且存在dist(P1,P2)≤min(epsC1,epsC2)，可以判定C1,C2合并為同一分類；

（2）在一類簇不規(guī)則邊界網(wǎng)格單元中的噪聲點(diǎn)，有可能是另一個(gè)類簇中的邊界點(diǎn)。設(shè)在一個(gè)分區(qū)C1中存在一個(gè)噪聲點(diǎn)P1，若在其他類簇中如C2的邊界網(wǎng)格單元中樣本能符合一個(gè)P2使得dist(P2,P1) ≤epsC2，則將分區(qū)C1中的P1劃分為C2類；

（3）在兩個(gè)不規(guī)則邊界網(wǎng)格單元中的噪聲點(diǎn)，會(huì)有邊界樣本個(gè)數(shù)一側(cè)相對(duì)較少或者密度相對(duì)較低的情況。在聚類合并的全局條件下，若存在兩個(gè)分區(qū)C1,C2中分別有噪聲點(diǎn)數(shù)據(jù)集S1,S2，其中一個(gè)樣本P，滿足dist(P,Pi)≤min(epsC1,epsC2)的鄰域范圍內(nèi)密度直達(dá)的樣本Pi有Numi≤min(epsC1,epsC2)，則可將噪聲點(diǎn)P定義為一個(gè)新類簇中的核心點(diǎn)，剩余的樣本Pi為新類簇中的邊界點(diǎn)。

2.4 改進(jìn)算法流程結(jié)構(gòu)

上述為SDKB-DBSCAN 具體改進(jìn)算法方案，這里給出算法整體流程與Spark 并行化設(shè)計(jì)結(jié)構(gòu)。SDKB_DBSCAN 算法執(zhí)行邏輯流程如圖（2）所示。

SDKB_DBSCAN 算法Spark RDD 并行化轉(zhuǎn)換執(zhí)行算子流程如圖（3）所示。

圖3 SDKB_DBSCAN RDD轉(zhuǎn)換執(zhí)行算子流程圖

InitData 在經(jīng)過(guò)mapValue 算子切割后，將InitRDD轉(zhuǎn)化成DataFrame 數(shù)據(jù)格式。數(shù)據(jù)在分區(qū)階段設(shè)計(jì)結(jié)構(gòu)dfZone>，運(yùn)用貪心算法，層次歸并均量算法以及廣度優(yōu)先搜索算法迭代擴(kuò)展，用FIFO 隊(duì)列作為迭代依據(jù)，以動(dòng)態(tài)規(guī)則劃定不規(guī)則密度分區(qū)，整合dfZone運(yùn)用算子轉(zhuǎn)換子PartitionRDD。

分區(qū)內(nèi)并行計(jì)算LocalDBSCAN，動(dòng)態(tài)自適應(yīng)確定Eps以及Minpts。分區(qū)聚類結(jié)果標(biāo)記數(shù)據(jù)結(jié)構(gòu)partition，執(zhí)行g(shù)roupBy轉(zhuǎn)換算子以及collect 操作算子聚合標(biāo)記數(shù)據(jù)樣本。

改進(jìn)算法分區(qū)合并策略，設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)為merge，將數(shù)據(jù)通過(guò)map 算子轉(zhuǎn)化為MergeRDD，按照改進(jìn)算法設(shè)計(jì)，將MergeRDD 的分區(qū)執(zhí)行內(nèi)存緩存，減少Spark RDD 間依賴計(jì)算，提升執(zhí)行效率。執(zhí)行map 算子以及filter 算子分別得到各分區(qū)邊界區(qū)域核心點(diǎn)，初始聚類結(jié)果下的噪聲點(diǎn)以及聚類后的噪聲點(diǎn)，依次迭代更新，遍歷映射全局簇類標(biāo)識(shí)，得到最終全局聚類結(jié)果。

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)環(huán)境

為驗(yàn)證改進(jìn)算法準(zhǔn)確率和運(yùn)行速率性能，編碼實(shí)現(xiàn)改進(jìn)算法，設(shè)計(jì)實(shí)驗(yàn)加以分析。實(shí)驗(yàn)環(huán)境如表1所示。

表1 實(shí)驗(yàn)硬件以及軟件環(huán)境

實(shí)驗(yàn)采用對(duì)串行DBSCAN 算法，并行化網(wǎng)格分區(qū)SparkDBSCAN 算法，以及SDKB_DBSCAN 改進(jìn)算法對(duì)比實(shí)驗(yàn)，使用的數(shù)據(jù)集如表2 所示。

表2 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)數(shù)據(jù)聚類結(jié)果對(duì)比分析：全局人工干預(yù)閾值Local_DBSCAN 算法，類簇劃分需多次調(diào)參以獲取更適類簇，圖4（a）所示，密度不均勻聚類存在噪聲點(diǎn)較多，誤差較大；Spark_DBSCAN 并行算法，網(wǎng)格分區(qū)并行迭代，全局人工干預(yù)閾值，重疊邊界區(qū)域局部合并來(lái)實(shí)現(xiàn)并實(shí)驗(yàn)，聚類依賴于網(wǎng)格劃分，不能做到動(dòng)態(tài)參數(shù)自適應(yīng)，且網(wǎng)格分區(qū)會(huì)使算法無(wú)法在全局范圍識(shí)別任意類型簇，圖4（b）所示，SparkDBSCAN 算法聚類準(zhǔn)確率，略低于Local_DBSCAN 算法；SDKB_DBSCAN 改進(jìn)算法，不規(guī)則動(dòng)態(tài)分區(qū)降低密度不均勻敏感性，動(dòng)態(tài)自適應(yīng)閾值減少人工干預(yù)誤差并內(nèi)存計(jì)算，設(shè)計(jì)緩存機(jī)制模型，圖4（c）所示，改進(jìn)算法在聚類數(shù)據(jù)尤其是密度不均勻類簇準(zhǔn)確率較前兩種算法有相對(duì)提升。

圖4 三種算法數(shù)據(jù)聚類效果圖

Local_DBSCAN、SparkDBSCAN、SDKB_DBSCAN算法準(zhǔn)確率量化數(shù)據(jù)如表3 所示。

表3 三種算法聚類準(zhǔn)確度（%）

3.2 并行實(shí)驗(yàn)性能

從運(yùn)行數(shù)據(jù)量和時(shí)間來(lái)看，Local_DBSCAN 算法在相同數(shù)據(jù)維度下有明顯時(shí)間消耗，效率限制明顯，串行計(jì)算消耗更多CPU 與內(nèi)存，SDKB_DBSCAN 改進(jìn)算法，設(shè)計(jì)并行計(jì)算有向無(wú)環(huán)圖DAG 以及Spark 并行過(guò)濾緩存機(jī)制與類簇合并融合算法，從局部聚類到聚類合并提升計(jì)算效率，在數(shù)據(jù)分區(qū)階段廣度優(yōu)先搜索不規(guī)則分區(qū)，需消耗一定計(jì)算資源，整體來(lái)講Spark_DBSCAN與SDKB_DBSCAN 改進(jìn)算法聚類效率在數(shù)量級(jí)上相同。圖5 所示，SDKB_DBSCAN 改進(jìn)算法運(yùn)行效率略高于Spark_DBSCAN 算法，高于Local_DBSCAN 算法。

圖5 三種算法時(shí)間消耗對(duì)比圖

加速比是同一任務(wù)運(yùn)行單核處理和并行處理運(yùn)行時(shí)間消耗的比率，可以用來(lái)衡量并行性能。圖6 顯示不同核數(shù)不同數(shù)據(jù)量加速比。

圖6 SDKB_DBSCAN多核加速比

在核數(shù)低且數(shù)據(jù)量少的情況下，對(duì)并行處理效率并無(wú)明顯提升，其中調(diào)度資源分配，并行化Suffle 階段會(huì)消耗一定時(shí)間，若數(shù)量增加核數(shù)增大，則加速比提升明顯。

4 結(jié)語(yǔ)

針對(duì)DBSCAN 算法存在的缺陷，串行計(jì)算速度慢，人工干預(yù)確定閾值參數(shù)敏感，數(shù)據(jù)密度不均勻降低準(zhǔn)確率等問(wèn)題，提出一種不規(guī)則動(dòng)態(tài)區(qū)域劃分，自適應(yīng)并行確定各閾值，不規(guī)則邊界區(qū)域緩存機(jī)制合并的SD?KB_DBSCAN 聚類改進(jìn)算法。實(shí)驗(yàn)表明，改進(jìn)算法對(duì)準(zhǔn)確率和運(yùn)行速率相對(duì)優(yōu)于Local_DBSCAN 以及Spark_DBSCAN 算法。

后續(xù)工作，將圍繞對(duì)更多的數(shù)據(jù)集進(jìn)行測(cè)試和算法優(yōu)化。包括分區(qū)策略算法選取優(yōu)化以及Spark 并行融合設(shè)計(jì)優(yōu)化，改進(jìn)算法運(yùn)行模式，Spark 緩存策略和內(nèi)存管理優(yōu)化，進(jìn)一步提高SDKB_DBSCAN 聚類改進(jìn)算法性能。