基于KD树划分的云计算DBSCAN优化算法

• 作者: 景维鹏 程逸群 陈广胜
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 聚类 DBSCAN算法 Spark平台 数据划分 数据融合
• 年，卷（期）: 2017,（4）
• 所属期刊栏目: 先进计算与数据处理
• 页码范围: 21-27
• 页数: 7页
• 分类号: TP311
• 字数: 5527字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2017.04.004

摘要

在并行RDD-DBSCAN算法的数据划分和区域查询过程中会对数据集进行重复访问,降低了算法效率.为此,提出基于数据划分和融合策略的并行DBSCAN算法(DBSCAN-PSM).利用KD树进行数据划分,实现数据分区与区域查询步骤的合并,从而减少数据集的访问次数以及降低I/O过程对算法效率的影响.采用判定数据点自身属性的方式,对标注为边缘点的数据进行融合,避免全局标记的额外时间开销.实验结果表明,DBSCAN-PSM算法相比RDD-DBSCAN算法可节省18%左右的运行时间,适用于处理海量数据聚类问题.