郑 剑，余 鑫
江西理工大学 信息工程学院，江西 赣州 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 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； 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是陡峭上升点； 定义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) 构造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节点上。 POMDRM-MR算法主要包括三个阶段：（1）数据划分，使用DS-PRBP策略筛选数据集稀疏维度，划分数据。（2）局部聚类，使用MOPTICS算法构建各分区上数据点与核心点之间的关联性，标记数据点迭代次数，迭代过程中，调用FMD策略获取数据点的领域均值距离排序，输出结果序列，再结合REC算法，二次排序序列，输出局部簇。（3）全局合并，使用BD-FLC策略计算并筛选合并列表中边界密度相近局部簇，同时调用MCNT算法加快收敛局部簇，最后结合MapReduce模型，提出MCNT-MR算法并行合并局部簇，提升算法合并局部簇的效率。 目前基于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策略划分数据集，能有效减少算法划分的计算复杂度，提高并行密度聚类算法数据划分阶段的效率。 目前基于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，计算其领域均值距离并排序； 假如当前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.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的值对应了执行算法所需要的并行节点数； POMDRM-MR算法的具体步骤如下所示： 步骤1输入数据集Q，调用DS-PRBP策略，计算数据集Q的维度稀疏度，筛选稀疏维度划分数据，分配MapReduce任务。 步骤2执行MapReduce任务，调用MOPTICS算法与FMD策略构建带有关联性标记的领域均值距离序列，使用REC算法对输出序列二次排序并提取局部簇，完成局部聚类。 步骤3调用BD-FLC策略筛选待合并簇，并使用MCNT算法加快合并局部簇的收敛速度，最后调用MCNT-MR算法并行合并局部簇，输出全局簇。 为验证POMDRM-MR算法的性能，在一台Master机和三台Slaver机，共四个节点上设计了性能对照实验，每一台硬件设备的处理器均为Intel®Core™i5-9400H CPU@2.9 GHz，16 GB DRAM内存，1 TB SATA3 7200RPM硬盘。实验的软件编程环境为python3.5.2； 表1 实验中各节点的具体配置Table 1 Configuration of each node POMDRM-MR算法采用的实验数据是来自UCI公共数据库（https：//archive.ics.uci.edu/ml/index.php）的四个真实数据集，分别是Iris、Uscd1990、Susy和Hepmass。Iris是模式识别文献中最著名的数据集，包含4个属性，共150条数据，具有数据量小，结构简单等特点； 表2 实验数据集信息Table 2 Information of datasets 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的计算公式如下： 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值的选取能有效提高算法聚类的准确性，也不会过于增加算法的计算复杂度。 为验证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算法在局部聚类阶段的准确性和稳定性最差。 为了验证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算法的准确率与其他三种算法相比近似，提升较小； 图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%； 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； 图13 F统计量Fig.13 F-statistics 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； 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算法采用均匀划分的方式划分网格，虽然减少了数据划分的时间，但生成了大量的边界点，反而在合并集群时需要花费更多的时间，而且合并过程并由采用并行的思想； 针对大数据环境下的密度聚类算法一直存在着数据划分不合理，聚类结果准确性和稳定性较低以及并行化效率不佳等问题，为了解决这些问题，本文提出了一种MapReduce下基于均值距离与关联性标记的POMDRM-MR算法。算法通过提出DS-PRBP策略，选择数据集稀疏维度划分数据集；
对于E点，有 |AE|=6>cd(A),故rd(E,A)=6；
对于C点，有 |AC|=31.3 Extract Clusters提取算法
s、e之间每个点的高度不低于其前身；
I不包括超过MinPts的非陡峭上升的连续点；
I是包含陡峭上升点的极大区间。陡峭下降区域定义同。1.4 n叉树的树型合并（n-ary tree）
2.1 算法思想
2.2 数据划分
2.3 局部聚类
假如ge_exp已经在SeedList中，则更新SeedList中ge_exp的领域均值距离，将其ID索引更新，与当前核心对象gexp的ID保持一致并排序。
2.4 全局合并
第二，增量合并增加了算法复杂度，降低了算法的总体并行化效率。对此，提出边界密度筛选策略BD-FLC，对合并列表中待合并簇进行边界密度的计算与筛选；
又基于n叉树的并集型合并，提出n叉树合并算法MCNT，加快局部簇收敛速度，最后结合MapReduce模型，提出并行局部簇合并算法MCNT-MR，并行合并局部簇，提升算法总体并行化效率。
执行map函数，输入表merge_list，检索该merge_list的边界点对象的key-value值，根据key值g_boundary在l1,l2,…,lk中进行索引LC，得到相应的k值，将此边界点对象的key-value值分配到相应的lk中，并输出key-value值2.5 POMDRM-MR算法步骤
3.1 实验环境
操作系统为Ubuntu 16.04；
MapReduce架构为Apache Hadoop3.2版本。4个节点的详细配置如表1所示。
3.2 数据来源
Uscd1990是美国1990年的人口普查数据集，其中包括68个属性，共有2 458 285条记录，数据结构复杂；
Susy是一组记录超对称粒子探测数据的数据集，包含18个属性，共5 000 000条记录，具有数据量大、数据均匀等特点；
Hepmass是一组记录外来粒子特征的数据集，总共包括28个属性和10 500 000个数据点，具有数据量大、随机等特点。数据集的详细信息如表2所示。
3.3 评价指标
3.4 参数选取
3.5 FMD策略与MOPTICS算法有效性分析
3.6 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算法的表现要更好。
而在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算法。
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算法在各方面都有显著的改进。
3.7 POMDRM-MR大数据下的性能分析
当节点数达到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算法适用于大规模数据集，并行化性能随着计算节点的增加而更好。
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能更快地对数据进行处理，且节点数量越多，并行化效率越高。
在各个数据分区上，提出MOPTICS算法构建数据点与核心点之间的关联性，标记数据点的迭代次数；
在距离度量中，提出FMD策略计算领域均值距离，代替可达距离排序；
最后提出REC算法对MOPTICS算法输出的关联性标记序列进行二次优化排序与提取簇，提升聚类的精确度；
合并局部簇时，算法提出BD-FLC策略筛选密度相近局部簇合并，又基于n叉树的并集型合并提出MCNT算法，加快局部簇合并的收敛，最后与MapReduce结合，提出MCNT-MR算法，并行合并局部簇，提升算法并行化合并的效率。对比其他算法，POMDRM-MR算法能根据数据集空间的分布状况来选择稀疏维度划分数据，构建关联性标记序列重排序提取簇来提高准确性，以及利用领域均值距离重定义可达距离，提升聚类稳定性。四个标准数据集实验的对比分析也表明POMDRM-MR算法在聚类精度、密度识别和聚类稳定性和并行效率上都有显著的提高。此外，扩充大规模数据集实验也验证了POMDRMMR算法的并行化效果。虽然改进后算法在聚类精度，稳定性和并行能力上有所提升，但仍存在提升空间，并且本文并未解决自动化选择边界密度差异阈值以及边界点k值的选取的问题，算法还有待进一步提高，这些将是下一步的研究工作。