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

编号 zgly0001606733

文献类型 期刊论文

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

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

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

母体文献 地理与地理信息科学 

年卷期 2017年06期

年份 2017 

分类号 TP311.13 

关键词 DBSCAN  K-DTree  MapReduce  SparkGraphX  空间大数据聚类 

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