Spark 并行化改进的SDKB-DBSCAN 聚类算法
2021-07-09史爱武尹杰范平
史爱武，尹杰，范平
（1.武汉纺织大学数学与计算机学院，武汉 430000；2.湖北科技学院计算机科学与技术学院，咸宁 437000）
0 引言
数据采集存储技术快速发展积累了大量数据，对数据深入分析并指导实践成为迫切需要，基于此大数据研究成为近年来研究热点。聚类分析是数据挖掘中的分支，来源于多研究领域，包括统计学、机器学习、模式识别等。其可以辅助分类研究，应用在生物学、地理信息学、商业分析、互联网搜索等领域。DBSCAN 算法是基于密度的聚类算法，它具备抗噪声能力，能够在具有噪声的数据集中发现任意形状类簇，有较好的聚类效果[1]。但DBSCAN 算法依然存在缺陷：算法在聚类中迭代计算，需要大规模内存磁盘I/O 交互，降低了计算速率；算法需要人工干预确定阈值，且对初始参数大小有敏感性，参数选定不准确，易降低聚类准确率；对不同数据集分布，特别是密度分布不均匀的样本集，采用全局阈值，对样本核心点，边界点和噪声点的划分会存在偏差，降低聚类准确率；对分布分散程度不高的数据集，全局阈值会造成不同簇类合并成同一簇类，降低聚类准确率。针对以上问题，许多学者对DBSCAN 算法进行研究及改进。
周水庚等人[2]提出矩形分区局部聚类策略；邱宁佳等人[3]提出基于MapReduce 的GA-DBSCAN 算法，胡赢双等人[4]提出基于MapReduce 网格划分强连通聚类算法；黄明吉等人[5]提出样本数据量划分策略和Spark并行化，计算速率有所提升，但存在网格划分，数据量划分等方法不能相对较高契合多密度不均匀聚类，准确率有所下降。韩利钊等[6]提出网格合并方法，可灵活定位不均匀数据划分区域，但其需要确定Eps参数初值，且算法时间复杂度相对较高，效率相对较低；于亚飞等人[7]、宋金玉等人[8]提出DBSCAN 算法参数配置策略，利用距离k-dist矩阵以及概率密度分布曲线获取参数值，提高参数自适应性，但是该方法需要人工干预确定k值，不同k值对应拟合曲线导数计算的大小不同；宋明等人[9]提出数据交替分区增量计算，田路强[10]提出分布式增量聚类，在提高聚类准确率同时会出现数据增量合并效率偏低。
针对上述学者研究需要提升的方面，提出SDKBDBSCAN 聚类改进算法，设计不规则动态区域并行计算模型，采取过滤不规则边界单元区域，指定不重叠区域的合并策略，应用概率密度以及均值方法，搭建Spark 并行计算框架算法架构。
1 基本理论内容
1.1 DBSCAN算法
DBSCAN 算法基于密度对空间样本形成类簇。在n维空间内，以参数设定阈值半径Eps以及阈值大小为聚类限定条件，将空间内样本点以迭代计算方式发现任意形状类簇，过滤样本数据集噪声点，得到密度聚类结果。在n维样本集中，列出算法相应定义：
定义1Eps邻域在n维空间内对任意的样本点p，以p为中心，Eps为半径内所有样本点集合。即表示为式（1）：
其中Dist(p,q)表示p到q的距离，通常情况下，用Minkowski距离公式计算Dist，公式表示为式（2）：
定义2核心点在n维空间内对任意样本点p，满足在以p为中心点的邻域值不少于Minpts个样本点。即表示为：，称p为核心点；
定义3边界点在n维空间内存在一个p不属于核心点，而且该点落在核心点的邻域范围内，称p点为边界点；
定义4噪声点在n维空间存在一个点p不属于核心点，而且该点落在所有核心点的邻域范围之外，称p点为噪声点；
定义5直接密度可达在n维空间内，若存在p在q的Eps邻域范围内，并且q为核心点，可称p是从q出发直接密度可达，不具有对称性。
定义6密度可达 在n维空间内，若存在数据集，满足从pi出发到pi+1直接密度可达，那么可以说是p1出发到pi+1是密度可达。不具有对称性但具有传递性。
定义7密度相连在n维空间内，若存在o，从点o出发到p密度可达，且从o出发到q密度可达，可称p和q密度相连。具有对称性，且p和q可以不属于核心点。
1.2 Spark并行内存计算框架
Apache Spark 是加州大学伯克利分校的AMP Lab实验室研究并开发，发展为Apache 顶级项目。Spark 是内存分布式计算引擎框架，在沿用MapReduce 计算引擎结构基础上，引入RDD（Resilient Distributed Dataset）分布式弹性数据集。执行时数据映射到RDD 结构中，发挥其内存计算结构特性以及在迭代计算中将数据反复缓存至内存的特点，与MapReduce 将数据在内存与硬盘I/O 转换相较，提高十倍甚至百倍的计算速度[11]。
从RDD 依赖关系中，可对RDD 的操作分为逻辑传递的转换操作和实际运行的行动操作，转换操作不会立即执行，要等行动操作全触发。用于并行操作重要的算子，包括Map、Reduce、Join、Foreach 等，对算法优化起到关键作用。
Spark 整体架构如图1 所示。
图1 Spark架构图
2 SDKB-DBSCAN改进算法
2.1 不规则动态密度区域划分
网格划分即设存在一个d维数据集S={s1,s2,…,sd}，S中各维数据表示为在第i维数据区间[ri,li)上i=1,2,..,d且各数据是有界的，则称D=[r1,l1)×[r2,l2)×…×[rd,ld)为d维的数据空间。D维空间是不相交数据集，表示为数据各个属性，对每一维数据空间划分，可形成d维网格单元，网格单元是以左闭右开的形式表示，其是d维空间基本划分单元[9]。对于网格划分，给出d维空间下每一维数据空间网格宽度的计算公式，表示为式（3）：
其中c为扩充线性方程，适当放缩网格宽度，找到合适的初始单元网格。计算各个维度的边界差与样本个数的比并取其最小值作为网格宽度的基准。之后可确定各个数据维度网格数量并确定其网格索引[12]。表示为式（4）：
区域合并即初始网格单元后，在d维空间内数据p是包含在某一个网格单元中，每一个网格单元由不同数据填充，可用每一个不相交的网格数据个数作为网格单元密度，den(f)表示密度大小。不规则分区算法伪代码如下所示：
算法1 贪心策略广度优先搜索层次归并算法
输入：DataSet 数据集
输出：partitionInfo 分区数据集
区域划分是控制相邻单元网格密度相对差比来合并网格单元，引入贪心策略，将问题分解成若干子问题，寻找未标记索引对应的密度最大值为核心网格单元，与相邻网格单元计算密度相对差比[13]表示为式（5）：
将其作为判断网格合并条件，初始核心与相邻网格依次按上式计算，并将满足d d()f,f0<ε条件，来确定相邻网格归属。若满足条件时，将相邻网格与核心网格标为一类，为减弱平均密度带来的密度差比波动，采取一种层次归并算法，统一平均密度值，其表示为式（6）：
区域划分采用广度优先搜索算法，不断合并满足条件的网格；不满足条件时，相邻单元网格标记为边界网格。将所有计算过的网格标记为已搜索状态，直到本次合并结束。若此时还有符合条件是未搜索状态，则继续求解子问题，直至区域划分结束。
2.2 区域自适应参数局部聚类
数据区域划分后，将不同区域数据分配到Spark 的RDD不同分区中。改进算法优化不同分区自适应确定Eps和Minpts，一定程度减小密度不均匀数据所统一参数对聚类的影响。
改进算法在自适应确定参数上引入核密度估计理论。定义为：设X1,X2,…,Xn是从总体X中抽取的独立同分布样本，总体X有未知分布密度函数f(x),x∈R，则f(x)的核密度估计为式（7）：
式中函数K(u)为核函数，h是与n有关的正数，为光滑参数或者窗宽[14]。
设定不同h窗宽，可得到不同效果f(x)。h窗宽过小时，f(x)限制局部观测数据，会得到过多错误峰值，估计函数效果不理想，将h映射对应自适应Eps取值过小，会增加样本成为噪声概率，降低聚类准确率；h窗宽过大时，f(x)过于光滑，无法去反映出正确的密度函数，同样h窗宽对应Eps取值过大，对于不同密度数据会错误合并为同一类，降低聚类准确率。
h窗宽的确定可影响Eps确定，改进算法采用Gaussian做为核函数，最小化积分均方误差MISE计算求得最优h窗宽，获取最优Eps[15]。MISE表示为式（8）：
其中可将AMISE(h)表示为渐进积分均方差误差，表示为式（9）：
求解最优h窗宽，即需要AMISE(h)误差值取得最小，因此对上式求偏导数可得式（10）：
数据样本总体服从方差为σ2的正态分布，用高斯核函数，代入式（10）可得式（11）：
由此可得自适应下最优Eps。
自适应确定Minpts采用在分区中每个Eps邻域范围内样本个数的均值策略，表示为式（12）：
其中Num即表示在每个Eps邻域范围内所包含样本数量，将上式定义到并行结构中内存计算。
2.3 自定义聚类合并策略
区域划分以及分区自适应确定参数并行计算后，给出自定义策略将局部聚类结果合并，形成最终全局聚类[16]。改进合并策略采用对各分区下不规则边界网格单元中样本进行局部合并。具体分为以下几点：
（1）设在两个分区C1,C2的边界网格上分别对应样本P1,P2，若P1,P2分别在对应分区上为其自适应确定下Eps的核心点，并且存在dist(P1,P2)≤min(epsC1,epsC2)，可以判定C1,C2合并为同一分类；
（2）在一类簇不规则边界网格单元中的噪声点，有可能是另一个类簇中的边界点。设在一个分区C1中存在一个噪声点P1，若在其他类簇中如C2的边界网格单元中样本能符合一个P2使得dist(P2,P1) ≤epsC2，则将分区C1中的P1划分为C2类；
（3）在两个不规则边界网格单元中的噪声点，会有边界样本个数一侧相对较少或者密度相对较低的情况。在聚类合并的全局条件下，若存在两个分区C1,C2中分别有噪声点数据集S1,S2，其中一个样本P，满足dist(P,Pi)≤min(epsC1,epsC2)的邻域范围内密度直达的样本Pi有Numi≤min(epsC1,epsC2)，则可将噪声点P定义为一个新类簇中的核心点，剩余的样本Pi为新类簇中的边界点。
2.4 改进算法流程结构
上述为SDKB-DBSCAN 具体改进算法方案，这里给出算法整体流程与Spark 并行化设计结构。SDKB_DBSCAN 算法执行逻辑流程如图（2）所示。
SDKB_DBSCAN 算法Spark RDD 并行化转换执行算子流程如图（3）所示。
图3 SDKB_DBSCAN RDD转换执行算子流程图
InitData 在经过mapValue 算子切割后，将InitRDD转化成DataFrame 数据格式。数据在分区阶段设计结构dfZone
分区内并行计算LocalDBSCAN，动态自适应确定Eps以及Minpts。分区聚类结果标记数据结构partition
改进算法分区合并策略，设计数据结构为merge
3 实验分析
3.1 实验环境
为验证改进算法准确率和运行速率性能，编码实现改进算法，设计实验加以分析。实验环境如表1所示。
表1 实验硬件以及软件环境
实验采用对串行DBSCAN 算法，并行化网格分区SparkDBSCAN 算法，以及SDKB_DBSCAN 改进算法对比实验，使用的数据集如表2 所示。
表2 实验数据集
实验数据聚类结果对比分析：全局人工干预阈值Local_DBSCAN 算法，类簇划分需多次调参以获取更适类簇，图4（a）所示，密度不均匀聚类存在噪声点较多，误差较大；Spark_DBSCAN 并行算法，网格分区并行迭代，全局人工干预阈值，重叠边界区域局部合并来实现并实验，聚类依赖于网格划分，不能做到动态参数自适应，且网格分区会使算法无法在全局范围识别任意类型簇，图4（b）所示，SparkDBSCAN 算法聚类准确率，略低于Local_DBSCAN 算法；SDKB_DBSCAN 改进算法，不规则动态分区降低密度不均匀敏感性，动态自适应阈值减少人工干预误差并内存计算，设计缓存机制模型，图4（c）所示，改进算法在聚类数据尤其是密度不均匀类簇准确率较前两种算法有相对提升。
图4 三种算法数据聚类效果图
Local_DBSCAN、SparkDBSCAN、SDKB_DBSCAN算法准确率量化数据如表3 所示。
表3 三种算法聚类准确度（%）
3.2 并行实验性能
从运行数据量和时间来看，Local_DBSCAN 算法在相同数据维度下有明显时间消耗，效率限制明显，串行计算消耗更多CPU 与内存，SDKB_DBSCAN 改进算法，设计并行计算有向无环图DAG 以及Spark 并行过滤缓存机制与类簇合并融合算法，从局部聚类到聚类合并提升计算效率，在数据分区阶段广度优先搜索不规则分区，需消耗一定计算资源，整体来讲Spark_DBSCAN与SDKB_DBSCAN 改进算法聚类效率在数量级上相同。图5 所示，SDKB_DBSCAN 改进算法运行效率略高于Spark_DBSCAN 算法，高于Local_DBSCAN 算法。
图5 三种算法时间消耗对比图
加速比是同一任务运行单核处理和并行处理运行时间消耗的比率，可以用来衡量并行性能。图6 显示不同核数不同数据量加速比。
图6 SDKB_DBSCAN多核加速比
在核数低且数据量少的情况下，对并行处理效率并无明显提升，其中调度资源分配，并行化Suffle 阶段会消耗一定时间，若数量增加核数增大，则加速比提升明显。
4 结语
针对DBSCAN 算法存在的缺陷，串行计算速度慢，人工干预确定阈值参数敏感，数据密度不均匀降低准确率等问题，提出一种不规则动态区域划分，自适应并行确定各阈值，不规则边界区域缓存机制合并的SD⁃KB_DBSCAN 聚类改进算法。实验表明，改进算法对准确率和运行速率相对优于Local_DBSCAN 以及Spark_DBSCAN 算法。
后续工作，将围绕对更多的数据集进行测试和算法优化。包括分区策略算法选取优化以及Spark 并行融合设计优化，改进算法运行模式，Spark 缓存策略和内存管理优化，进一步提高SDKB_DBSCAN 聚类改进算法性能。
