使用均值距離與關聯性標記的并行OPTICS算法

鄭 劍，余 鑫

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

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

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

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

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

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

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

1 算法及相關概念

1.1 PRBP劃分算法

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

（1）構造網格，如圖1所示，為數據集Q構造一個網格，并以2ε為寬度初始化網格，獲取維度切片。

圖1 PRBP分片Fig.1 PRBP partition

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

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

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

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

1.2 OPTICS聚類算法

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

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

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

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

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

如圖所示，令ε=9，MinPts=5，對于A點有ρ(A)=9>MinPts=5，故A點為核心點，以半徑AD為半徑的圓內有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，ξ陡峭區域）設區間I=[s,e]是陡峭上升區域，則滿足以下條件：s、e是陡峭上升點；s、e之間每個點的高度不低于其前身；I不包括超過MinPts的非陡峭上升的連續點；I是包含陡峭上升點的極大區間。陡峭下降區域定義同。

定義5（cluster，類簇）區間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）

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

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

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

2 POMDRM-MR并行算法

2.1 算法思想

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

2.2 數據劃分

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

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

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

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

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

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

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

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

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

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

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

2.3 局部聚類

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

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

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

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

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

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

證明

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

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

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

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

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

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

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

2.3.2 構建關聯性標記排序

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

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

圖5 Forgotten值域Fig.5 Forgotten range

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

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

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

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

最終輸出的關聯性標記點的排序如圖6所示。

圖6 關聯性標記點排序Fig.6 Sorting of relevance marker points

2.3.3 REC提取類簇

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

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

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

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

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

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

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

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

2.4 全局合并

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

2.4.1 BD-FLC策略篩選合并簇

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

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

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

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

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

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

2.4.2 局部簇的合并

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

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

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

2.4.3 局部簇的并行合并

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

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

2.5 POMDRM-MR算法步驟

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

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

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

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

3 實驗結果及比較

3.1 實驗環境

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

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

3.2 數據來源

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

表2 實驗數據集信息Table 2 Information of datasets

3.3 評價指標

3.3.1 加速比

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

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

3.3.2 F-measure

參數設置和適當的評估標準尤為重要。為了定量地評價該算法的輸出，采用F-measure值來評估聚類結果，F-measure值是聚類算法的準確率和召回率的加權平均值，定義如下：

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

3.3.3 方差分析ANOVA

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

3.4 參數選取

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

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

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

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

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

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

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

3.6 POMDRM-MR算法性能分析

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

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

3.6.1 準確率分析

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

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

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

3.6.2 方差的比較分析

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

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

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

3.6.3 F統計量差異分析

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

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

圖13 F統計量Fig.13 F-statistics

3.7 POMDRM-MR大數據下的性能分析

3.7.1 加速比分析

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

圖14 加速比Fig.14 Speedup ratio

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

3.7.2 運行時間

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

圖15 運行時間Fig.15 Running time

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

4 結束語

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