使用均值距離與關聯(lián)性標記的并行OPTICS算法

鄭 劍，余 鑫

江西理工大學 信息工程學院，江西 贛州 341000

聚類是數(shù)據(jù)挖掘中一種無監(jiān)督學習算法，基于類內(nèi)相似性最大化和類間相似性最小化原則，聚類算法能根據(jù)物理或抽象對象的相關特征，將數(shù)據(jù)對象歸入由類似對象組成的類中，因此聚類算法可以識別數(shù)據(jù)中的潛在分布，在統(tǒng)計學習、模式識別和人工智能方面都有著廣泛的用途[1]。在聚類算法中，DBSCAN[2]和OPTICS[3]等基于密度的聚類算法，可以識別噪聲空間中任意形狀的簇，深受廣大研究人員的關注[4-6]。

互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，迎來了數(shù)據(jù)井噴的大數(shù)據(jù)時代，各種領域的數(shù)據(jù)高速產(chǎn)生，并開始以不同結(jié)構(gòu)化形式呈現(xiàn)出來，體積大（volume）、種類多（variety）、速度快（velocity）、價值高（value）的“4V”特性[7]，使得傳統(tǒng)聚類算法面臨著可擴展性和可伸縮性問題[8]，眾多學者開始研究其他技術(shù)以求解決問題。

Hadoop、Spark等分布式計算架構(gòu)的誕生及Google開發(fā)的MapReduce模型的應用為人們提供了新的設想[9-10]，將改進后的傳統(tǒng)算法與大數(shù)據(jù)計算框架相結(jié)合，成為當前大數(shù)據(jù)聚類的主要研究方向[11-14]。Li等人[15]首先借助MapReduce模型，提出了MapReduce下的并行DBSCAN算法，算法在Map階段將數(shù)據(jù)分片，然后在Reduce階段并行執(zhí)行DBSCAN算法以獲取局部簇，增量合并局部簇獲取全局簇，實現(xiàn)并行DBSCAN聚類。但該算法沒有提出具體的劃分策略來劃分數(shù)據(jù)，且增量合并局部簇，算法合并效率較低；Mahran等人[16]提出了使用網(wǎng)格加速的GriDBSCAN算法，算法構(gòu)造均勻網(wǎng)格劃分數(shù)據(jù)，并以網(wǎng)格為對象并行執(zhí)行DBSCAN聚類，合并網(wǎng)格局部簇獲取全局簇，以此提升算法聚類的效率。但該算法存在兩個明顯問題：劃分網(wǎng)格時，難以確定網(wǎng)格大??；均勻劃分高密度域數(shù)據(jù)時，會割裂數(shù)據(jù)集原有結(jié)構(gòu)，生成大量邊界點，增加算法計算復雜度。此外，仍然采用增量式合并局部簇，合并效率較低。文獻[17-18]分別給出了Hadoop和Spark下的H-DBSCAN和S-DBSCAN算法，在均勻網(wǎng)格劃分的基礎上，增加了對網(wǎng)格邊界的擴展，一定程度上保留了數(shù)據(jù)空間結(jié)構(gòu)，但仍制造了大量的邊界點，增加了計算復雜度，合并局部簇時，也未采用并行化思想。

為了合理劃分數(shù)據(jù)，保留數(shù)據(jù)結(jié)構(gòu)的同時減少邊界點，王興等人[19]提出了IP-DBSCAN算法，采用二分法劃分空間網(wǎng)格，并結(jié)合貪心算法對劃分進行重構(gòu)，從而合理劃分數(shù)據(jù)，局部聚類后，使用R*-tree索引策略判斷處理候選簇，提高合并局部簇的收斂速度。然而，二分法分割數(shù)據(jù)時，仍需輸入網(wǎng)格邊緣長度閾值，且同樣采用增量的方式合并局部簇，算法合并效率較低。Dai等人[20]為了解決劃分閾值問題，設計了一種基于數(shù)據(jù)點分布選擇分界以達到每個節(jié)點負載平衡的PRBP（partition with reduce boundary points）算法，并基于MapReduce提出了使用PRBP劃分的DBSCAN-MR算法，算法選擇邊界點數(shù)最少處作劃分邊界，有效避免了拆分密集區(qū)域數(shù)據(jù)到不同分區(qū)，保留了數(shù)據(jù)集結(jié)構(gòu)，改善了數(shù)據(jù)劃分的不合理性。但PRBP劃分每次都需要對數(shù)據(jù)集所有維度進行計算來確定最佳分片，使得算法計算量很大；同時，DBSCAN算法受參數(shù)影響較大，且不能識別不同密度的集群，聚類穩(wěn)定性不高。

為了進一步解決算法劃分和局部聚類階段的缺陷，吳翠先等人[21]改進了PRBP算法，并使用OPTICS算法局部聚類，增加了算法識別不同密度的能力，但改進的PRBP算法對數(shù)據(jù)的篩選太過粗糙，最佳分片的選取并不準確，且OPTICS算法同樣對參數(shù)MinPts敏感，當MinPts參數(shù)不合理時，直接影響核心領域內(nèi)數(shù)據(jù)點的可達距離的度量，影響算法的穩(wěn)定性；Xiong等人[22]另辟蹊徑，提出DBSCAN-DLP算法，利用密度分級劃分的概念來解決DBSCAN的變密度問題。Bhardwaj等人[23]又將密度水平分區(qū)（density level partitioning，DLP）引入DBSCAN-MR算法，提出了VDMR-DBSCAN算法，利用它們的合并策略，可以識別不同密度的集群。Heidari等人[24]也在此基礎上，提出了MR-VDBSCAN算法，與VDMR-DBSCAN相比，MR-VDBSCAN算法能根據(jù)分區(qū)的密度選擇聚類算法的參數(shù)，提高了本地聚類的準確性和速度。然而，所有這些算法都沒能解決數(shù)據(jù)的合理劃分，與并行化合并局部簇等問題，算法整體效率有待提升。

為了解決上述問題，本文提出一種MapReduce下的并行OPTICS算法——POMDRM-MR（a parallel OPTICS by using mean distance and relevance marks based on MapReduce），主要做了以下幾方面工作：（1）根據(jù)數(shù)據(jù)集的空間分布，提出基于維度稀疏度的最少邊界點劃分策略（partition with reduced boundary points based on dimension sparsity，DS-PRBP），篩選數(shù)據(jù)集稀疏維度劃分數(shù)據(jù)，降低算法劃分的計算復雜度。（2）針對每個分區(qū)，提出標記點排序識別簇算法（marking and ordering points to identify the cluster structure，MOPTICS），構(gòu)建數(shù)據(jù)點與核心點之間的關聯(lián)性，并標記所有數(shù)據(jù)點的迭代次數(shù)，結(jié)合新提出的重排序序列提取簇算法（reordering and extracting clusters，REC），對關聯(lián)性標記序列，進行二次排序并提取簇，提高局部聚類的準確性；局部聚類過程中，又提出領域均值距離策略（field mean distance，F(xiàn)MD），計算所有對象的領域均值距離，代替可達距離排序，提升聚類的穩(wěn)定性。（3）局部簇生成后，首先提出邊界密度篩選策略（using boundary density to filter local cluster，BD-FLC），計算并篩選邊界密度相近局部簇，提高局部簇合并的準確度；又基于n叉樹的并集型合并方法，提出n叉樹合并簇算法（merge cluster by usingn-ary tree，MCNT），加快局部簇的收斂，最后結(jié)合MapReduce，提出并行合并簇算法（merge cluster by usingn-ary tree based on MapReduce，MCNT-MR），并行合并局部簇，提升基于密度的聚類算法合并全局簇的效率。

1 算法及相關概念

1.1 PRBP劃分算法

PRBP[20]算法是數(shù)據(jù)劃分中一種常用的以最少邊界點劃分的優(yōu)化算法，劃分過程主要分以下四個階段：

（1）構(gòu)造網(wǎng)格，如圖1所示，為數(shù)據(jù)集Q構(gòu)造一個網(wǎng)格，并以2ε為寬度初始化網(wǎng)格，獲取維度切片。

圖1 PRBP分片F(xiàn)ig.1 PRBP partition

（2）計算每個維度切片的s.count與s.accuCount，根據(jù)下述公式篩選滿足條件的切片維度。

其中，R為搜索范圍，Qsize表示數(shù)據(jù)集大小，θ表示均衡參數(shù)，s.count為當前分片點數(shù)，s.accuCount為累計點數(shù)。

（3）根據(jù)（2）中所選維度，選擇s.count最小的維度最佳分片拆分數(shù)據(jù)集Q，得到數(shù)據(jù)集Q1和Q2。

（4）與閾值β比較，超過β則繼續(xù)拆分，否則結(jié)束拆分，最終得到劃分結(jié)果。如圖1所示，實線處即為一個最佳分片。

1.2 OPTICS聚類算法

OPTICS算法是聚類算法中一種按可達距離排序數(shù)據(jù)，并識別聚類結(jié)構(gòu)的密度聚類算法。與DBSCAN不同，OPTICS算法并不直接生成簇，相關定義如下：

定義1（core distance，核心距離）設x∈X，對于給定參數(shù)ε和MinPts，稱使得數(shù)據(jù)對象x成為核心對象的最小鄰域半徑為對象x的核心距離，記為cd(x)，cd(x)的計算公式如下：

定義2（reachability distance，可達距離）設x,y∈X，對于給定參數(shù)ε和MinPts，稱rd(y,x)為y關于x的可達距離。rd(y,x)的計算公式如下：

以圖2所示數(shù)據(jù)集，對OPTICS算法的核心距離以及可達距離進行說明。

圖2 可達距離示意圖Fig.2 Reachability distance

如圖所示，令ε=9，MinPts=5，對于A點有ρ(A)=9>MinPts=5，故A點為核心點，以半徑AD為半徑的圓內(nèi)有5個點，cd(A)=|AD|=4；對于E點，有 |AE|=6>cd(A),故rd(E,A)=6；對于C點，有 |AC|=3

1.3 Extract Clusters提取算法

Extract Clusters[3]算法是一種自動簇提取算法，通常用于對OPTICS算法輸出的可達距離序列進行簇識別與提取簇，其相關定義如下：

定義3（ξ-steep points，ξ陡峭點）設點p∈{1,2,…,n-1}，如果點p的值小于其下一點的值ξ%，則稱點p為ξ陡峭上升點，記為UpPointξ(p)，如果點p的下一點值小于點p值ξ%，則稱點p為ξ陡峭下降點，記為DownPointξ(p)。定義如下：

定義4（ξ-steep areas，ξ陡峭區(qū)域）設區(qū)間I=[s,e]是陡峭上升區(qū)域，則滿足以下條件：s、e是陡峭上升點；s、e之間每個點的高度不低于其前身；I不包括超過MinPts的非陡峭上升的連續(xù)點；I是包含陡峭上升點的極大區(qū)間。陡峭下降區(qū)域定義同。

定義5（cluster，類簇）區(qū)間C=[s,e]?[1,m]是一個類簇，則：

其中，m=max{x∈D|RR-D(x)>RR-D(eU+1)}，M=min{x∈U|RR-D(x)

1.4 n叉樹的樹型合并（n-ary tree）

構(gòu)造n叉樹[25]的樹型結(jié)構(gòu)時，以一個集合構(gòu)造一棵樹，集合本身由樹的根節(jié)點代表，集合中的每一個元素構(gòu)造成樹的每一個葉子節(jié)點。利用n叉樹合并一組不相交集合X={x1,x2,…,xn}和Y={y1,y2,…,yn}時，一般分為兩個步驟：

build(X,Y)階段：分別將集合X和集合Y構(gòu)建n叉樹，取任意集合中元素xi為Root節(jié)點，其余元素為Leaf節(jié)點，所有Leaf節(jié)點與Root節(jié)點相連。

merge(X,Y)階段：將集合X生成樹的Root節(jié)點作Leaf節(jié)點連接到集合Y生成樹的Leaf節(jié)點上。

2 POMDRM-MR并行算法

2.1 算法思想

POMDRM-MR算法主要包括三個階段：（1）數(shù)據(jù)劃分，使用DS-PRBP策略篩選數(shù)據(jù)集稀疏維度，劃分數(shù)據(jù)。（2）局部聚類，使用MOPTICS算法構(gòu)建各分區(qū)上數(shù)據(jù)點與核心點之間的關聯(lián)性，標記數(shù)據(jù)點迭代次數(shù)，迭代過程中，調(diào)用FMD策略獲取數(shù)據(jù)點的領域均值距離排序，輸出結(jié)果序列，再結(jié)合REC算法，二次排序序列，輸出局部簇。（3）全局合并，使用BD-FLC策略計算并篩選合并列表中邊界密度相近局部簇，同時調(diào)用MCNT算法加快收斂局部簇，最后結(jié)合MapReduce模型，提出MCNT-MR算法并行合并局部簇，提升算法合并局部簇的效率。

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

目前基于PRBP劃分的并行密度聚類算法，劃分數(shù)據(jù)時需要迭代計算數(shù)據(jù)集所有維度來選取最佳分片，這使得算法計算量很大。且相對于數(shù)據(jù)分布稀疏的維度，在數(shù)據(jù)分布密集的維度獲取到更優(yōu)的最佳分片的可能性要小得多。因此，使用PRBP算法對數(shù)據(jù)集各個維度不加選擇地劃分，并不合理。對此，提出基于維度稀疏度的DS-PRBP策略，通過篩選數(shù)據(jù)集稀疏維度劃分數(shù)據(jù)，減少算法劃分數(shù)據(jù)的計算量，提高算法劃分的合理性。DS-PRBP策略描述如下：

將d維空間數(shù)據(jù)集Q上的點分別投影在d個維度上，會在每一個維度dl(l=1,2,…,d)上形成一維數(shù)據(jù)點xil的聚集。根據(jù)每一個維度上點xil與其左右相鄰點之間的最小距離dmin(xil)計算出當前維度dl的維度稀疏度dl_sparsity。篩選出d個維度中dl_sparsity最大的前K(2≤K≤5)個維度，計算此K個維度獲取最佳分片，劃分數(shù)據(jù)集。

維度稀疏度dl_sparsity的定義如下：

定義6（維度稀疏度dl_sparsity）對于一個d維數(shù)據(jù)集Q，獲取Q在維度dl(l=1,2,…,d)下每一個數(shù)據(jù)點與其左右數(shù)據(jù)點之間的最小距離dmin(xil)，計算得到dl維度下所有數(shù)據(jù)點之間最小距離的平均值，稱之為數(shù)據(jù)集Q在dl維度的維度稀疏度dl_sparsity。

維度稀疏度dl_sparsity的計算公式如下：

其中，l為維度，xil(i=1,2,…,n)為數(shù)據(jù)集在維度dl下的點的升值排序點，即有x(i+1)l≥xil，dmin(xil)為數(shù)據(jù)點xil與左右相鄰點之間的最小距離。

證明設數(shù)據(jù)集Q在維度dl的長度為L，相鄰兩點之間距離為 |xil-x(i-1)l|,i>1。若點xil到左右相鄰點之間的最短距離為dmin(xil)，且由dmin(xil)構(gòu)成的維度長度為L′，則所以L≥L′，當且僅當 |xil-x(i-1)l|=dmin(xil)時，即數(shù)據(jù)集上的點均勻分布時，L=L′。

由此可知，由dmin(xil)構(gòu)成的維度長度L′是數(shù)據(jù)集在當前維度的最短長度。n相等，dmin(xil)均值越小，維度越密集，dmin(xil)均值越大，維度越稀疏，獲取整體最佳分片的可能性越大。

因此，由dmin(xil)構(gòu)成的維度最小距離均值dl_sparsity=，可以衡量數(shù)據(jù)集在當前維度的稀疏分布，即dl_sparsity可以有效篩選出數(shù)據(jù)集稀疏維度劃分數(shù)據(jù)，減少算法計算量。

PRBP算法作為一種最少邊界點劃分算法，得益于其對各個維度的最少邊界點劃分原理，算法能最大程度地保留數(shù)據(jù)集的原始結(jié)構(gòu)，使得數(shù)據(jù)劃分后，單個分區(qū)上的數(shù)據(jù)結(jié)構(gòu)和分布更純粹，降低了同一分區(qū)夾雜不同簇數(shù)據(jù)的概率。而在更純粹結(jié)構(gòu)和單一分布的數(shù)據(jù)集聚類時，一定程度上能提升算法局部聚類的準確性。同時，最少邊界點劃分，能避免劃分密集區(qū)域數(shù)據(jù)集，減少大量邊界點的生成，降低了算法在后續(xù)局部簇合并階段的合并計算量，以及簇合并數(shù)量。

但PRBP算法每次劃分都需要計算數(shù)據(jù)集的所有維度的特性，使得算法在處理大規(guī)?；蛣虞m上千緯度化的大數(shù)據(jù)集時，擁有極高的計算復雜度。算法的劃分邏輯也決定了其并不適用于大規(guī)模和高緯度的數(shù)據(jù)集的處理。DS-PRBP算法改進了PRBP算法的計算策略，通過對大數(shù)據(jù)下所有維度進行有且僅有一次的維度稀疏度的計算，篩選出前K(2≤K≤5)個最稀疏維度進行劃分，保留了PRBP算法劃分的優(yōu)勢，又減少了算法迭代計算所有維度的計算量。因此，使用DS-PRBP策略劃分數(shù)據(jù)集，能有效減少算法劃分的計算復雜度，提高并行密度聚類算法數(shù)據(jù)劃分階段的效率。

2.3 局部聚類

目前基于OPTICS的并行密度聚類算法，在局部聚類過程中，多采用貪心策略的方式迭代擴張，即總是選擇可達距離最小的點，且算法不直接產(chǎn)生結(jié)果簇，而是生成一個增廣的可達距離排序。這種方式存在兩個問題，一是貪心策略，會將迭代方向從一個密集區(qū)域引入到另一個密集區(qū)域，而簇周邊的稀疏對象就會被擱置在有序種子隊列的末尾，得不到準確的劃分，導致可達距離圖失真，影響聚類的準確性，大規(guī)模數(shù)據(jù)聚類時，局部簇外圍點的錯誤分簇，也會使得合并局部簇時，待合并簇的核心邊界密度計算錯誤，影響合并的準確性。二是聚類直接生成可達距離序列，不同密度閾值MinPts的設置，會對可達距離的度量與排序產(chǎn)生主觀性影響，造成較大的排序差異，影響聚類穩(wěn)定性。在傳統(tǒng)OPTICS算法的小規(guī)模數(shù)據(jù)聚類中，參數(shù)MinPts只適配當前小規(guī)模數(shù)據(jù)集聚類，聚類結(jié)果較穩(wěn)定。面對擁有復雜結(jié)構(gòu)且分布差異較大的大規(guī)模數(shù)據(jù)集時，OPTICS算法的全局參數(shù)MinPts無法兼顧和適用于所有分區(qū)上的數(shù)據(jù)集聚類，這會導致在一部分分區(qū)上，參數(shù)MinPts并不合理，從而影響算法在局部分區(qū)的聚類結(jié)果。

針對這些問題，本文首先提出標記點排序識別簇算法MOPTICS，構(gòu)建數(shù)據(jù)點與核心點之間關聯(lián)性，并標記數(shù)據(jù)點的迭代次數(shù)，輸出關聯(lián)性標記序列，又提出FMD策略計算所有數(shù)據(jù)對象的領域均值距離，代替可達距離排序，提升算法的穩(wěn)定性，最后基于Extract Clusters算法，提出重排序序列提取簇算法REC，對MOPTICS算法輸出的關聯(lián)性標記序列，進行二次排序并提取局部簇，提高聚類結(jié)果的準確性。為便于敘述，首先對FMD策略進行介紹。

2.3.1 FMD策略計算領域均值距離

由于OPTICS算法在DBSCAN算法的基礎上，改進了算法對參數(shù)ε的敏感性，但仍然對參數(shù)MinPts敏感，而MinPts的設置決定著可達距離的度量，MinPts參數(shù)變化的同時，就會引起算法可達距離的變化。而核心領域內(nèi)點的可達距離并不等于該點到核心點的實際距離，因此，當同一個點鏈接多個核心對象時，MinPts參數(shù)的變化，就有可能導致該點到核心點的可達距離違背實際距離，即實際距離近，而可達距離遠，造成點的分簇錯誤，影響排序的準確性。對此，提出FMD策略，通過計算鄰域內(nèi)每一個數(shù)據(jù)對象在領域內(nèi)的均值距離，代替可達距離排序，提升算法的穩(wěn)定性。FMD策略的定義與計算公式如下：

定義7（field mean distance，領域均值距離）設核心點q所在ε鄰域內(nèi)有點pi(i=1,2,…,m)，與其核心領域內(nèi)點pj(j=1,2,…,n)，則pi到q領域內(nèi)所有pj的最短距離的均值dam稱為pi關于當前核心對象q的領域均值距離，dam計算公式如下：

其中，d為數(shù)據(jù)空間維度，l為當前維度，pil與pjl分別為l維度下的值，n為點pj所在核心領域內(nèi)點的點數(shù)。

證明

（1）對于?oi,oj，dmin(oi,oj)=dmin(oj,oi)對稱性滿足。

（3）對于?oi,oj，dmin(oi,z)+dmin(z,oj)≥dmin(oi,oj)，三角不等式滿足。

因此公式滿足距離度量的基本條件，能夠衡量ε鄰域內(nèi)點到核心點q領域內(nèi)所有點的均值距離。

在大規(guī)模數(shù)據(jù)集的并行OPTICS算法聚類中，算法對多個分區(qū)進行局部聚類，但由于OPTICS算法參數(shù)MinPts為全局參數(shù)，且由人為設置，因此，當MinPts設置不合理時，不僅會將多個不同簇鏈接到同一個簇，且當一個對象由多個核心對象可達時，如a點同時由b點和c點可達時，實際距離‖ab‖<‖ac‖，但由于b點的核心距離更大，導致可達距離度量上‖ab‖>‖ac‖，由此造成錯誤排序，使得原本屬于b簇的a點被分配到c簇，從而無法準確地對核心領域內(nèi)點進行排序，如圖3所示，不同MinPts參數(shù)下的算法的聚類結(jié)果也不盡相同，以圖中數(shù)據(jù)點分布可見，經(jīng)驗聚類可生成4個局部簇，然而在不同的MinPts參數(shù)下，傳統(tǒng)OPTICS算法聚類的結(jié)果卻有著明顯的差異，當MinPts=4時，如圖3（a）所示，聚類生成5個局部簇，而MinPts=6時，如圖3（c）所示，聚類生成8個局部簇，當且僅當MinPts=5時，聚類結(jié)果最為準確，且聚類結(jié)果復現(xiàn)幾率低，聚類穩(wěn)定性較差。

圖3 不同MinPts值下的聚類結(jié)果Fig.3 Clustering results under different MinPts

而采用FMD策略后，如圖4所示，e點的可達距離度量，為其到核心領域內(nèi)所有點最短路徑的均值，此時，最短路徑的點也不再以核心點p的位置而定，而是以所有核心領域點共同決定，產(chǎn)生的可達距離將不再受人為MinPts的設置而大幅變動，由此產(chǎn)生的聚類結(jié)果更加穩(wěn)定精確。

圖4 領域均值距離Fig.4 Field mean distance

2.3.2 構(gòu)建關聯(lián)性標記排序

獲取領域均值距離的計算方式后，提出MOPTICS算法為原始數(shù)據(jù)集構(gòu)建關聯(lián)性標記序列，以解決傳統(tǒng)OPTICS算法的貪心策略，所造成的數(shù)據(jù)點之間相鄰關系的斷裂，導致錯誤排序。得益于HDFS文件系統(tǒng)，MOPTICS算法在NameNode節(jié)點的基礎上為每一個數(shù)據(jù)塊中的點新增記錄，添加點地址信息、及遺忘域Forgotten。域內(nèi)存放數(shù)據(jù)點的FV值與ID值。FV記錄所有數(shù)據(jù)點的迭代次數(shù)，ID索引數(shù)據(jù)點的當前鏈接的核心點，并在迭代中，使用FMD策略度量距離排序，輸出帶有關聯(lián)性標記的領域均值距離序列。算法總體步驟如下：

初始化數(shù)據(jù)集Q，為Q中所有數(shù)據(jù)對象添加Forgotten域。如圖5所示，域內(nèi)存放兩個值，一個ID索引值，一個FV迭代值，并初始化為0。

圖5 Forgotten值域Fig.5 Forgotten range

獲取數(shù)據(jù)集Q中所有核心對象gcore及其擴展對象gexp，算法迭代時，將初始化后的gcore及gexp分配相同ID索引，并將gexp添加至SeedList。計算SeedList中g(shù)exp到gcore領域內(nèi)所有對象的領域均值距離，按領域均值距離排序并擴展，擴展時分兩種情況：

假如當前gexp也是核心對象，則為當前gexp與其擴展對象ge_exp分配相同ID，并將ge_exp添加至SeedList，計算其領域均值距離并排序；假如ge_exp已經(jīng)在SeedList中，則更新SeedList中g(shù)e_exp的領域均值距離，將其ID索引更新，與當前核心對象gexp的ID保持一致并排序。

假如當前gexp不是核心對象，保持當前gexp與其核心對象gcore的ID不變。

每一次迭代時，將SeedList中擴展對象的FV累加1，直至其被添加進OrderList中。迭代結(jié)束，輸出OrderList。

最終輸出的關聯(lián)性標記點的排序如圖6所示。

圖6 關聯(lián)性標記點排序Fig.6 Sorting of relevance marker points

2.3.3 REC提取類簇

構(gòu)建關聯(lián)性標記排序后，OrderList中對象已經(jīng)攜帶了可供重排序的關聯(lián)性標記信息，為了提取更準確的局部簇，在Extract Clusters算法的基礎上，提出REC重排序提取簇算法對OrderList進行二次排序并提取類簇，步驟如下：

遍歷OrderList序列，將待處理指針指向OrderList序列頭部，開始識別聚類簇。檢測OrderList序列，計算ξ陡峭點，識別到ξ陡峭下降區(qū)域，則記錄新簇cluster，并將陡峭下降區(qū)域的點存入cluster，識別到ξ陡峭上升區(qū)域，則尋找與之對應的ξ陡峭下降區(qū)域，簇cluster提取結(jié)束。

提取cluster時，遍歷cluster內(nèi)所有數(shù)據(jù)點，記錄cluster內(nèi)點最大FV值Lci_FVmax。提取全部簇后，以FVthreshold為閾值篩選出長久擱置點gspa（擱置越久，迭代次數(shù)越多，F(xiàn)V值越大，排序越靠后）。其中FVthreshold計算公式如下：

對擱置點gspa，根據(jù)gspa的ID找出其核心對象gcore，并重排序OrderList。判斷gcore是否屬于當前簇，此處分兩種情況：

gcore屬于當前簇，將gspa加入當前簇；

gcore不屬于當前簇，則將gspa插入到gcore所在簇的末尾，形成新的可達圖，并輸出提取簇。聚類簇與可達距離圖，如圖7所示。

圖7 聚類簇與新可達距離序列圖Fig.7 Clustering and new reachable distance sequence

算法借助HDFS文件系統(tǒng)中NameNode節(jié)點攜帶的信息，能直接為數(shù)據(jù)點增加遺忘值記錄，且在排序過程中，通過NameNode中塊地址信息與新增記錄，可以很快找到重排序的數(shù)據(jù)點的點地址信息。此外，算法并不對每一個數(shù)據(jù)點都重新分配排序，而是利用MOPTICS為每個數(shù)據(jù)點增加迭代次數(shù)和核心點的索引信息，在REC算法的二次排序當中，設置迭代閾值，通過迭代次數(shù)篩選公式，篩選出迭代次數(shù)較高的稀疏點進行合理位置的二次排序，相對于全排序來說，大大減少了算法的排序計算量。經(jīng)過二次排序后的有序結(jié)果隊列也完美地修正了原始OPTICS序列中的稀疏點的不合理分配，提高了可達距離序列圖的合理性，以及生成的局部簇的準確性，也為后續(xù)局部簇合并時，待合并簇的邊界密度的精準計算與篩選做好鋪墊，間接提升局部簇合并的準確性。

2.4 全局合并

目前基于劃分的密度聚類算法，合并局部簇時，通常僅根據(jù)核心邊界點來篩選局部簇，并增量合并局部簇。這導致了兩個問題：第一，核心邊界點合并，會誤將不同密度簇合并為同一個簇，降低算法合并準確性；第二，增量合并增加了算法復雜度，降低了算法的總體并行化效率。對此，提出邊界密度篩選策略BD-FLC，對合并列表中待合并簇進行邊界密度的計算與篩選；又基于n叉樹的并集型合并，提出n叉樹合并算法MCNT，加快局部簇收斂速度，最后結(jié)合MapReduce模型，提出并行局部簇合并算法MCNT-MR，并行合并局部簇，提升算法總體并行化效率。

2.4.1 BD-FLC策略篩選合并簇

BD-FLC策略的主要思想在于，當一個簇被一分為二時，其分割邊界區(qū)域的密度是高度近似甚至相等的。因此，選擇合并列表中邊界密度相近局部簇合并，可以有效提高局部簇合并的準確率。具體步驟如下：

（1）整理合并列表。獲取局部簇邊界點，將同一邊界點所屬多個簇添加至merge_list合并列表，并標記分區(qū)PI，簇編號CID，是否為核心邊界點isCore。篩選isCore為true點進行合并，多次合并整理生成最終列表。merge_list構(gòu)建過程如圖8所示。

圖8 整理合并列表Fig.8 Organizing list to be merged

（2）計算邊界密度。以merge_list中待合并簇的核心邊界點為中心，向周圍擴張k個點，計算k個點之間的最小平均距離，即局部簇邊界密度，計算公式如下：

（3）根據(jù)密度差異選擇合并簇。根據(jù)merge_list中局部簇邊界密度計算密度差異，設定差異閾值篩選合并簇，密度差異公式如下：

不同區(qū)域數(shù)據(jù)點之間的最小平均距離，能很好地反映局部簇的密度分布，相較于計算局部簇的整體密度，計算局部簇的邊界密度篩選局部簇合并，更準確得多。而不同局部簇邊界密度相比于相同簇，差異是巨大的，因此，通過對數(shù)據(jù)集采樣計算k值，并選擇合適的差異閾值對局部簇進行篩選合并，能有效避免將不同簇合并到同一簇，提高算法合并的準確性。

2.4.2 局部簇的合并

篩選局部簇后，為了加快局部簇合并的收斂速度，基于n叉樹提出新型局部簇合并算法MCNT，算法基于n叉樹對多個集合的并集型合并方式，提出了合并局部簇的兩個方法Build、Merge。Build方法構(gòu)造n叉樹，Merge方法合并n叉樹。算法的總體步驟如下：

在Build階段，算法選擇篩選后的merge_list中的所有待合并簇LC，將同一本地簇LC中的對象相連接，返回一棵以Root節(jié)點為代表的樹，簇中任一核心對象作為Root節(jié)點，其他對象則作為Leaf節(jié)點。所有的Leaf節(jié)點都與Root節(jié)點相連接，生成多個以Root節(jié)點為代表的LC n叉樹。

在Merge階段，以merge_list中待合并簇CID為標準，取一棵LC的n叉生成樹為根樹，將同一merge_list中其他LC生成樹的Root節(jié)點作為Leaf節(jié)點連接到當前LC n叉樹的Root節(jié)點上，完成局部簇的合并。

2.4.3 局部簇的并行合并

為了實現(xiàn)并行化合并的局部簇，提高局部簇合并的效率，本文在MCNT算法的基礎上，提出了基于MapReduce的并行局部簇合并算法MCNT-MR，算法的主要步驟如下：

以篩選后的局部簇合并列表merge_list作為輸入。將表merge_list中待合并簇劃分為k個部分l1,l2,…,l（k按合并數(shù)量，非邊界點數(shù)），其中k的值對應了執(zhí)行算法所需要的并行節(jié)點數(shù)；執(zhí)行map函數(shù)，輸入表merge_list，檢索該merge_list的邊界點對象的key-value值，根據(jù)key值g_boundary在l1,l2,…,lk中進行索引LC，得到相應的k值，將此邊界點對象的key-value值分配到相應的lk中，并輸出key-value值傳遞到Reduce函數(shù)中去。在Reduce函數(shù)階段，對于每個Mi，并行化執(zhí)行MCNT算法，輸出并行局部簇合并結(jié)果，結(jié)合LC中無需合并簇，共同輸出全局聚類簇。

2.5 POMDRM-MR算法步驟

POMDRM-MR算法的具體步驟如下所示：

步驟1輸入數(shù)據(jù)集Q，調(diào)用DS-PRBP策略，計算數(shù)據(jù)集Q的維度稀疏度，篩選稀疏維度劃分數(shù)據(jù)，分配MapReduce任務。

步驟2執(zhí)行MapReduce任務，調(diào)用MOPTICS算法與FMD策略構(gòu)建帶有關聯(lián)性標記的領域均值距離序列，使用REC算法對輸出序列二次排序并提取局部簇，完成局部聚類。

步驟3調(diào)用BD-FLC策略篩選待合并簇，并使用MCNT算法加快合并局部簇的收斂速度，最后調(diào)用MCNT-MR算法并行合并局部簇，輸出全局簇。

3 實驗結(jié)果及比較

3.1 實驗環(huán)境

為驗證POMDRM-MR算法的性能，在一臺Master機和三臺Slaver機，共四個節(jié)點上設計了性能對照實驗，每一臺硬件設備的處理器均為Intel?Core?i5-9400H CPU@2.9 GHz，16 GB DRAM內(nèi)存，1 TB SATA3 7200RPM硬盤。實驗的軟件編程環(huán)境為python3.5.2；操作系統(tǒng)為Ubuntu 16.04；MapReduce架構(gòu)為Apache Hadoop3.2版本。4個節(jié)點的詳細配置如表1所示。

表1 實驗中各節(jié)點的具體配置Table 1 Configuration of each node

3.2 數(shù)據(jù)來源

POMDRM-MR算法采用的實驗數(shù)據(jù)是來自UCI公共數(shù)據(jù)庫（https：//archive.ics.uci.edu/ml/index.php）的四個真實數(shù)據(jù)集，分別是Iris、Uscd1990、Susy和Hepmass。Iris是模式識別文獻中最著名的數(shù)據(jù)集，包含4個屬性，共150條數(shù)據(jù)，具有數(shù)據(jù)量小，結(jié)構(gòu)簡單等特點；Uscd1990是美國1990年的人口普查數(shù)據(jù)集，其中包括68個屬性，共有2 458 285條記錄，數(shù)據(jù)結(jié)構(gòu)復雜；Susy是一組記錄超對稱粒子探測數(shù)據(jù)的數(shù)據(jù)集，包含18個屬性，共5 000 000條記錄，具有數(shù)據(jù)量大、數(shù)據(jù)均勻等特點；Hepmass是一組記錄外來粒子特征的數(shù)據(jù)集，總共包括28個屬性和10 500 000個數(shù)據(jù)點，具有數(shù)據(jù)量大、隨機等特點。數(shù)據(jù)集的詳細信息如表2所示。

表2 實驗數(shù)據(jù)集信息Table 2 Information of datasets

3.3 評價指標

3.3.1 加速比

采用加速比來衡量POMDRM-MR算法在大數(shù)據(jù)環(huán)境下的并行計算性能，加速比是單處理系統(tǒng)和并行處理器系統(tǒng)中運行同一任務所消耗時間的比率，計算公式如下：

其中，T1為該任務的串行運行時間，Tp是該任務在并行處理系統(tǒng)中的運行時間。Sp越大，并行計算所耗費的相對時間越少，算法的并行效率越高。

3.3.2 F-measure

參數(shù)設置和適當?shù)脑u估標準尤為重要。為了定量地評價該算法的輸出，采用F-measure值來評估聚類結(jié)果，F(xiàn)-measure值是聚類算法的準確率和召回率的加權(quán)平均值，定義如下：

一般情況下，λ參數(shù)被設置為1，F(xiàn)-measure綜合考慮了聚類結(jié)果的準確率和召回率，可以更準確地評估聚類算法的結(jié)果，F(xiàn)-measure值越高，意味著聚類的結(jié)果更準確合理。

3.3.3 方差分析ANOVA

方差分析可以用來確定幾個組的觀測數(shù)據(jù)或處理結(jié)果是否存在顯著差異，于本文來說，即算法是否具有意義上的改進。使用F-statistics（F統(tǒng)計量）來評估本文算法的提升，F(xiàn)-statistics是組間均方（MSB）和組內(nèi)均方（MSE）的比值，其自由度分別為k-1和N-k。Fstatistics的計算公式如下：

3.4 參數(shù)選取

POMDRM-MR算法在調(diào)用BD-FLC策略計算待合并簇的邊界密度時，需要指定具體的k值，來獲取邊界核心點周圍k個最近鄰點。為了使POMDRM-MR算法能獲得更加準確的聚類結(jié)果，本文在基于Uscd1990多密度數(shù)據(jù)集下，保證其他參數(shù)不變的同時，將邊界點數(shù)k的取值設置為[5~16]，獨立運行10次，取10次的FMeasure均值進行分析。如圖9所示，當k值取12時，能得到較為準確的聚類結(jié)果。

圖9 k值的選取Fig.9 Selection of k value

如圖9所示，邊界點數(shù)k的值給定得太小或太大都沒有意義。k值給定得太小時，采樣點較少，算法無法正確計算待合并簇的邊界密度，合并準確率較低，而k值太大時，反而會增加算法的計算量，即計算更多的點的最少平均距離來確定邊界核心點的密度。因此合適k值的選取能有效提高算法聚類的準確性，也不會過于增加算法的計算復雜度。

3.5 FMD策略與MOPTICS算法有效性分析

為驗證FMD策略和MOPTICS算法關聯(lián)性標記在局部聚類階段的有效性，同樣在Uscd1990多密度數(shù)據(jù)集上，對H-DBSCAN、DBSCAN-MR、MR-VDBSCAN和POMDRM-MR等算法的局部聚類結(jié)果進行對比，局部聚類結(jié)果如圖10所示。

圖10 不同局部聚類方式下的聚類效果比較Fig.10 Comparison of results in different local cluster algorithms

如圖10所示，采用FMD策略與MOPTICS算法關聯(lián)性標記的POMDRM-MR算法，在局部聚類階段的效果最好，算法的穩(wěn)定性也是最佳。這是因為，在局部聚類過程中，MOPTICS算法的關聯(lián)性標記與REC算法根據(jù)標記的二次提取修正了傳統(tǒng)OPTICS算法貪心策略擴張導致的可達距離圖的錯誤排序，而FMD策略又使得算法對參數(shù)Minpts不再敏感，減輕了人為主觀性參數(shù)設置，給算法聚類穩(wěn)定性帶來的影響。而MR-VDBSCAN對不同分區(qū)采用不同參數(shù)的聚類方式使其能識別多密度聚類，在面對多密度數(shù)據(jù)集時，聚類的準確性也僅次于POMDRM-MR（OPTICS算法本身就能識別多密度聚類），且二者都使用PRBP算法對數(shù)據(jù)集劃分，使得各個分區(qū)數(shù)據(jù)集的分布與結(jié)構(gòu)也更純粹。而H-DBSCAN和DBSCAN-MR算法局部聚類時，直接調(diào)用傳統(tǒng)DBSCAN算法進行局部聚類，這使得它們的準確率最差，但相對于H-DBSCAN算法，DBSCAN-MR算法在數(shù)據(jù)劃分時，也采用PRBP算法劃分，相對于H-DBSCAN算法的均勻劃分，DBSCAN-MR算法聚類數(shù)據(jù)集質(zhì)量更好，其局部聚類效果也更佳，而H-DBSCAN算法均勻劃分數(shù)據(jù)集，破壞了數(shù)據(jù)集空間結(jié)構(gòu)，這也使得H-DBSCAN算法在局部聚類階段的準確性和穩(wěn)定性最差。

3.6 POMDRM-MR算法性能分析

為了驗證POMDRM-MR算法的性能與聚類效果，在Iris、Uscd1990、Susy和Hepmass四個數(shù)據(jù)集下進行了多次對照實驗，根據(jù)聚類結(jié)果的準確率、方差及F統(tǒng)計量，選擇具有代表性的H-DBSCAN、DBSCAN-MR和MR-VDBSCAN算法與POMDRM-MR算法進行比較（由于OPTICS算法不可分割的有序序列結(jié)構(gòu)，目前對并行OPTICS算法的研究文獻較少，且DBSCAN的運行速度是OPTICS的1.6倍[23]，故此本文選擇具有代表性的并行DBSCAN算法作為比較），實驗結(jié)果如表3所示。

表3 算法綜合聚類性能比較分析Table 3 Comparative analysis of performance of all algorithms

3.6.1 準確率分析

算法的準確率可以直接反映該算法的聚類效果，準確率越高，聚類效果越好。采用F-measure值計算算法10次實驗結(jié)果的平均值，將POMDRM-MR算法的準確率分別與H-DBSCAN、DBSCAN-MR和MR-VDBSCAN算法進行比較，對照結(jié)果如圖11所示。

如圖11所示，POMDRM-MR算法在四種數(shù)據(jù)集上的準確率最高。在Iris數(shù)據(jù)集上，POMDRM-MR算法的準確率與其他三種算法相比近似，提升較??；在Susy數(shù)據(jù)集上，POMDRM-MR算法的準確率分別比MR-VDBSCAN、H-DBSCAN和DBSCAN-MR算法高出1.7、2.4和4.3個百分點；在Hepmass數(shù)據(jù)集上，POMDRMMR算法的準確率則比其他三種算法分別高出2.4、2.9和5.2個百分點。這是因為POMDRM-MR算法采用DS-PRBP策略劃分數(shù)據(jù)集，其劃分的本質(zhì)依賴于PRBP算法的最少邊界點劃分原理，一定程度上保留了數(shù)據(jù)集的原始結(jié)構(gòu)，使得局部分區(qū)上的數(shù)據(jù)分布更加純粹，結(jié)構(gòu)也更加單一，而在結(jié)構(gòu)單一、分布純粹的數(shù)據(jù)集上聚類時，無疑能提升算法聚類的準確性。同時，算法還在局部聚類階段使用MOPTICS算法構(gòu)造數(shù)據(jù)之間的關聯(lián)性，并標記數(shù)據(jù)點的迭代次數(shù)，聯(lián)合REC算法對關聯(lián)性標記序列進行二次排序，克服了傳統(tǒng)OPTICS算法貪心策略造成的稀疏點與稠密點的相鄰關系的斷裂，也提高了算法局部聚類的準確性；此外，在局部簇合并過程中，算法采用BD-FLC策略對待合并簇進行了密度篩選，避免了將不同密度簇合并到同一個簇中，同樣對局部簇合并的準確率有所增益。而H-DBSCAN算法采用均勻網(wǎng)格劃分，盡管擴展了網(wǎng)格邊界，但割裂了數(shù)據(jù)空間結(jié)構(gòu)，導致不如POMDRM-MR算法精確。DBSCAN-MR算法采用PRBP策略劃分數(shù)據(jù)，沒有提出其他策略提高聚類準確度，因此在所有算法中精度最低。MR-VDBSCAN算法采用PRBP劃分后，在不同分區(qū)中使用不同的密度參數(shù)進行聚類，提高準確率的同時可以識別密度不同局部簇。因此，在多密度數(shù)據(jù)集Uscd1990中，MR-VDBSCAN算法聚類的準確性優(yōu)于其他兩種算法，其準確率比H-DBSCAN和DBSCAN-MR分別高出1.5和2.8個百分點。但得益于POMDRM-MR算法采用MOPTICS算法聚類，同樣可以識別多密度數(shù)據(jù)集，因此在四種數(shù)據(jù)集上，POMDRM-MR算法的表現(xiàn)要更好。

圖11 準確率比較分析Fig.11 Analysis of accuracy

3.6.2 方差的比較分析

算法多次聚類結(jié)果的準確率方差可以反映算法的穩(wěn)定性，方差越小，算法穩(wěn)定性越高。在10次實驗中記錄了四種算法的準確率方差，分別比較了POMDRM-MR、H-DBSCAN、DBSCAN-MR和MR-VDBSCAN算法的穩(wěn)定性，結(jié)果如圖12所示。

圖12 方差的比較分析Fig.12 Analysis of variance

如圖可見，在四個數(shù)據(jù)集中，POMDRM-MR算法相較于其他算法，方差更小，算法的穩(wěn)定性更高，且在較大、復雜數(shù)據(jù)集上具有決定性的優(yōu)勢。盡管在小規(guī)模數(shù)據(jù)集Iris上，POMDRM-MR的方差與其他算法方差相近。然而，在大數(shù)據(jù)集上，如Susy數(shù)據(jù)集，POMDRM-MR算法的方差分別比H-DBSCAN，DBSCAN-MR和MRVDBSCAN算法低57%、37.8%和36.7%；而在Hepmass數(shù)據(jù)集上，POMDRM-MR算法的方差則分別低60.9%、48.6%和47.4%。這是因為小規(guī)模數(shù)據(jù)集結(jié)構(gòu)簡單，分布單一，并不會對算法聚類產(chǎn)生較大影響，但大規(guī)模數(shù)據(jù)集，復雜的數(shù)據(jù)結(jié)構(gòu)會嚴重影響并行算法的穩(wěn)定性。而POMDRM-MR算法的DS-PRBP最少邊界點劃分策略一定程度保護了數(shù)據(jù)集空間結(jié)構(gòu)，局部聚類中FMD策略的使用，也使得算法對參數(shù)Minpts不再敏感，人為參數(shù)的設置也不會對算法的距離排序產(chǎn)生較大的影響，此外，MOPTICS的關聯(lián)性標記與REC算法的二次排序中也起到修正算法聚類波動的效果，這使得POMDRMMR算法的穩(wěn)定性最高；DBSCAN-MR算法與MR-VDBSCAN算法的穩(wěn)定性相近，因為它們都使用PRBP算法來分割數(shù)據(jù)，可以產(chǎn)生更少的邊界點，但效果不如POMDRM-MR算法顯著。H-DBSCAN算法采用均勻的方式劃分網(wǎng)格，破壞了數(shù)據(jù)的空間結(jié)構(gòu)，并產(chǎn)生了大量邊界點，使其穩(wěn)定性遠小于DBSCAN-MR和MRVDBSCAN算法。

3.6.3 F統(tǒng)計量差異分析

在F-統(tǒng)計量的差異性分析中，作出H0假設：“四種算法聚類結(jié)果的平均值相等，即μa=μb=μc=μd”，并計算了POMDRM-MR和其他算法在Uscd1990、Susy和Hepmass上的F-統(tǒng)計量，以評估POMDRM-MR算法在大規(guī)模數(shù)據(jù)集上的改進。

如圖13所示，“All”柱代表所有算法的整體差異，在上述數(shù)據(jù)集中，“All”中的F值均達到了較高水平，這表明至少有一個算法與其他算法之間存在著較大差異。因此，將POMDRM-MR算法分別與DBSCAN-MR、MRVDBSCAN和H-DBSCAN算法進行對比以檢測這種巨大的差異是否是由POMDRM-MR算法引起。圖13中，在Susy數(shù)據(jù)集中，DBSCAN-MR和POMDRM-MR之間的F統(tǒng)計值達到6.199E+04；H-DBSCAN和POMDRMMR算法之間的F統(tǒng)計值為1.632E+04。同理，在Hepmass數(shù)據(jù)集上，POMDRM-MR和其他算法之間的F統(tǒng)計也達到了一個巨大的水平，計算結(jié)果拒絕了H0假設，這證明了與Susy和Hepmass數(shù)據(jù)集上的其他算法相比，POMDRM-MR的聚類結(jié)果有了顯著的改進；在Uscd1990數(shù)據(jù)集上，盡管POMDRM-MR與MR-VDBSCAN相比，改進并不明顯，但在表3中計算得到的F統(tǒng)計量值仍比接受假設的P值大得多，這使得本文的H0假設同樣無效。因此，計算結(jié)果表明，POMDRM-MR算法在各方面都有顯著的改進。

圖13 F統(tǒng)計量Fig.13 F-statistics

3.7 POMDRM-MR大數(shù)據(jù)下的性能分析

3.7.1 加速比分析

加速比指算法在單處理器系統(tǒng)和并行處理器系統(tǒng)中運行同一任務所消耗的時間比。作為測試并行算法性能的重要指標，加速比越大，并行性能越好。在本實驗中，從Hepmass數(shù)據(jù)集中隨機提取了四個子集，包含100 000行、3 000 000行，5 000 000行、10 000 000行，計算算法在這些數(shù)據(jù)集上不同節(jié)點的加速比，以度量算法在Hadoop并行化框架下的計算能力，結(jié)果如圖14所示。

圖14 加速比Fig.14 Speedup ratio

由圖14可以看出，POMDRM-MR算法適用于處理較大規(guī)模數(shù)據(jù)集，在處理大型數(shù)據(jù)集時具有更大的加速比，但并不適用于小數(shù)據(jù)集。在處理小數(shù)據(jù)集時，隨著節(jié)點的增加，POMDRM-MR算法的加速比不增反降。如圖14中的100 000行所示，當只有一個節(jié)點時，加速比為1，當節(jié)點數(shù)增加到4時，加速比降到0.6。這是因為當數(shù)據(jù)集的大小遠小于集群處理的數(shù)據(jù)量時，將數(shù)據(jù)分配到不同的計算節(jié)點會產(chǎn)生不同的時間成本開銷，包括集群運行時間、任務調(diào)度時間、節(jié)點存儲時間等，從而降低了算法的計算速度，因此其并行效果較低。而當算法運行在大數(shù)據(jù)集上時，加速比會隨著節(jié)點的增加而增加。如圖14中的3 000 000行，隨著節(jié)點數(shù)由1增加到2，算法的加速比從1增加到1.2；當節(jié)點數(shù)達到4時，算法的加速比達到2.4，這表明當數(shù)據(jù)量足夠大時，節(jié)點越多，算法的效率越高。當數(shù)據(jù)的大小達到5 000 000和10 000 000，2個節(jié)點時，算法的加速比分別為1.4和1.5；3個節(jié)點時，加速比分別為2.0和2.4；4個節(jié)點時，加速比分別為3.1和3.7。在節(jié)點數(shù)量相同的情況下，數(shù)據(jù)量越大，算法的加速比越高，這是因為在大型數(shù)據(jù)集下，該算法的并行計算和并行合并局部簇方面具有更多的優(yōu)勢，使得加速比隨著計算節(jié)點的增加而增加，算法的并行效果也大大提升。這也表明，POMDRM-MR算法適用于大規(guī)模數(shù)據(jù)集，并行化性能隨著計算節(jié)點的增加而更好。

3.7.2 運行時間

運行時間能反映算法的運行效率，用時越少，意味著算法的效率越高。在Hepmass的四個子集上記錄了這四個算法的運行時間來分別比較POMDRM-MR和H-DBSCAN、DBSCAN-MR、MR-VDBSCAN算法的運行效率，實驗結(jié)果見圖15。

圖15 運行時間Fig.15 Running time

如圖15所示，POMDRM-MR算法在大型數(shù)據(jù)集上的并行效率更高，與其他算法相比，POMDRM-MR算法聚類花費的時間更少，數(shù)據(jù)集越大，算法的優(yōu)勢越明顯。當數(shù)據(jù)量為100 000時，這四種算法的運行時間相差無幾，這是因為在處理小數(shù)據(jù)集時，將數(shù)據(jù)分布到不同的計算節(jié)點會產(chǎn)生不同的時間成本，包括集群運行時間、任務調(diào)度時間、節(jié)點存儲時間等，這些時間占聚類總時間的絕大部分，因此POMDRM-MR的并行優(yōu)勢并沒有得到體現(xiàn)。然而，當數(shù)據(jù)集的大小達到3 000 000時，POMDRM-MR算法的運行時間比DBSCAN-MR、MRVDBSCAN和H-DBSCAN算法分別低15.3%、20.8%和29.4%。當數(shù)據(jù)量達到5 000 000時，如圖15所示，POMDRM-MR算法的運行時間比DBSCAN-MR、MR-VDBSCAN和H-DBSCAN算法分別低19.1%、25.9%和35.2%。尤其當數(shù)據(jù)量達到10 000 000，POMDRM-MR算法的運行時間分別比其他算法少23.4%、29.1%和37.4%。這是因為在大規(guī)模數(shù)據(jù)集上進行聚類時，生成的本地集群的數(shù)量在聚類中顯著增加，然而，H-DBSCAN算法采用均勻劃分的方式劃分網(wǎng)格，雖然減少了數(shù)據(jù)劃分的時間，但生成了大量的邊界點，反而在合并集群時需要花費更多的時間，而且合并過程并由采用并行的思想；DBSCAN-MR算法和MR-VDBSCAN算法使用PRBP算法劃分數(shù)據(jù)，產(chǎn)生的邊界點最少，這也使得合并集群的時間減少，因此DBSCAN-MR和MR-VDBSCAN算法比H-DBSCAN算法運行得更快。但是MR-VDBSCAN算法需要計算局部聚類時不同分區(qū)的密度參數(shù)這使它比DBSCAN-MR算法要慢，此外，它們都沒有并行地合并本地簇，這使得它們在聚類中效率低下。對于POMDRM-MR算法，它使用DS-PRBP策略選擇稀疏維度劃分數(shù)據(jù)，大大加快了算法劃分數(shù)據(jù)階段的時間，其次，在合并局部簇階段，采用MCNT算法加快局部簇合并的收斂速度，并結(jié)合MapReduce架構(gòu)提出了MCNTMR算法并行合并局部簇，這使得POMDRM-MR算法的運行速度最快，效率最高。這也更加表明了，針對大規(guī)模數(shù)據(jù)集時，POMDRM-MR能更快地對數(shù)據(jù)進行處理，且節(jié)點數(shù)量越多，并行化效率越高。

4 結(jié)束語

針對大數(shù)據(jù)環(huán)境下的密度聚類算法一直存在著數(shù)據(jù)劃分不合理，聚類結(jié)果準確性和穩(wěn)定性較低以及并行化效率不佳等問題，為了解決這些問題，本文提出了一種MapReduce下基于均值距離與關聯(lián)性標記的POMDRM-MR算法。算法通過提出DS-PRBP策略，選擇數(shù)據(jù)集稀疏維度劃分數(shù)據(jù)集；在各個數(shù)據(jù)分區(qū)上，提出MOPTICS算法構(gòu)建數(shù)據(jù)點與核心點之間的關聯(lián)性，標記數(shù)據(jù)點的迭代次數(shù)；在距離度量中，提出FMD策略計算領域均值距離，代替可達距離排序；最后提出REC算法對MOPTICS算法輸出的關聯(lián)性標記序列進行二次優(yōu)化排序與提取簇，提升聚類的精確度；合并局部簇時，算法提出BD-FLC策略篩選密度相近局部簇合并，又基于n叉樹的并集型合并提出MCNT算法，加快局部簇合并的收斂，最后與MapReduce結(jié)合，提出MCNT-MR算法，并行合并局部簇，提升算法并行化合并的效率。對比其他算法，POMDRM-MR算法能根據(jù)數(shù)據(jù)集空間的分布狀況來選擇稀疏維度劃分數(shù)據(jù)，構(gòu)建關聯(lián)性標記序列重排序提取簇來提高準確性，以及利用領域均值距離重定義可達距離，提升聚類穩(wěn)定性。四個標準數(shù)據(jù)集實驗的對比分析也表明POMDRM-MR算法在聚類精度、密度識別和聚類穩(wěn)定性和并行效率上都有顯著的提高。此外，擴充大規(guī)模數(shù)據(jù)集實驗也驗證了POMDRMMR算法的并行化效果。雖然改進后算法在聚類精度，穩(wěn)定性和并行能力上有所提升，但仍存在提升空間，并且本文并未解決自動化選擇邊界密度差異閾值以及邊界點k值的選取的問題，算法還有待進一步提高，這些將是下一步的研究工作。