KDSG-DBSCAN:一种基于K-D Tree和Spark GraphX的高性能DBSCAN算法

作者：高旭; 桂志鹏; 隆玺; 栗法; 吴华意; 秦昆

来源：地理与地理信息科学, 2017, 33(06): 1-7+127.

• DBSCAN
• K-D Tree
• MapReduce
• Spark GraphX
• 空间大数据聚类

DBSCAN是一种基于密度的聚类算法,其能从包含噪声点的数据集中发现任意形状的聚类并且无需预先设定聚类个数,因此得到了广泛应用。但随着数据规模的增大,迭代式的点间距离计算导致经典单机串行DBSCAN算法的性能显著下降,使之无法满足实际应用的效率需求。为此,该文提出一种性能改进的分布式并行聚类算法——KDSG-DBSCAN。该算法利用K-D Tree邻域查询减少点间距离计算次数,利用图连通算法优化局部类簇合并过程,并基于Apache Spark MapReduce平台实现了计算过程的并行化。通过4组对比实验,分析了KDSGDBSCAN、经典DBSCAN与未使用图连通的KDS-DBSCAN算法的执行效率、KDSG-DBSCAN各子阶段执行时间占比、不同数据规模下KDSG-DBSCAN的扩展性以及不同计算节点数量和CPU核数下KDSG-DBSCAN的扩展性。结果表明,KDSG-DBSCAN算法具有良好的可扩展性和加速比。

• 单位
  武汉大学; 地球空间信息技术协同创新中心; 武汉大学测绘遥感信息工程国家重点实验室