论文部分内容阅读
DBSCAN是一种应用广泛的基于密度的聚类算法,具有能从存在噪声点的点集中发现任意形状的点聚类且不需要提前设定聚类个数等优点。但是,经典DBSCAN算法因为需要迭代式的点间距离计算,性能会随着数据规模的增大而急剧下降。针对这一问题,本文提出一种性能优化的并行聚类算法——KDSG-DBSCAN。KDSG-DBSCAN 基于 Spark MapReduce 对 DBSCAN 进行并行化设计,利用K-D树邻域查询算法减少距离计算次数,并运用并行图连通算法优化类簇合并的效率。本文的研究工作主要有以下四个方面:1)经典DBSCAN算法的执行流程性能分析。在梳理和总结数据聚类分析与大数据分布式存储计算领域的理论与应用现状的基础上,通过对经典DBSCAN的执行流程进行分析,本文提出了从减少迭代点间距离计算和并行化两个方面来优化DBSCAN算法性能的思路。2)基于索引机制提高局部聚类效率。在DBSCAN局部聚类阶段中,距离判断产生了大量不必要的两两点间距离计算,形成了性能瓶颈。针对这个问题,本文引入K-D树索引结构,通过K-D树邻域查询筛选出邻域内的点进行计算,有效减少了计算次数,提高了 DBSCAN局部聚类阶段的性能。3)基于并行图连通策略优化DBSCAN类簇合并性能。针对并行DBSCAN算法在局部类簇合并的过程中产生了大量的通讯和传输消耗,本文用图结构来表达类数据点的聚类关系,基于Spark GraphX的并行图连通方法来提高类簇合并的并行度,降低通讯和传输消耗,从而提高了性能。4)实现算法和实验验证算法的性能提升效果。基于Java面向对象编程技术和Spark分布式内存计算框架实现了设计的算法。针对提出的算法,开展四组对比实验,对比分析KDSG-DBSCAN、经典DBSCAN与未使用图连通的KDS-DBSCAN算法的执行效率,分析了KDSG-DBSCAN各子阶段执行时间占比、不同数据规模下KDSG-DBSCAN的扩展性、不同计算节点数量及CPU核数下KDSG-DBSCAN的扩展性。实验结果表明,本文提出的算法相对于经典DBSCAN具有明显的性能提升;在大规模点数据的聚类中具有良好的可扩展性,为空间大数据的聚类挖掘提供了一种可行的优化方案。