面向位置大数据的快速密度聚类算法

摘要：

面向位置大数据聚类,提出了一种简单但高效的快速密度聚类算法CBSCAN,以快速发现位置大数据中任意形状的聚类簇模式和噪声.首先,定义了Cell网格概念,并提出了基于Cell的距离分析理论,利用该距离分析,无需距离计算,可快速确定高密度区域的核心点和密度相连关系;其次,给出了网格簇定义,将基于位置点的密度簇映射成基于网格的密度簇,利用排他网格与相邻网格的密度关系,可快速确定网格簇的包含网格;第三,利用基于Cell的距离分析理论和网格簇概念,实现了一个快速密度聚类算法,将DBSCAN基于数据点的密度扩展聚类转换成基于Cell的密度扩展聚类,极大地减少高密度区域的距离计算,利用位置数据的内在特性提高了聚类效率;最后,在基准测试数据上验证了所提算法的聚类效果,在位置大数据上的实验结果统计显示,与DBSCAN、PR-Tree索引和Grid索引优化的DBSCAN相比,CBSCAN分别平均提升了525倍、30倍和11倍效率.

关键词：聚类分析、密度聚类、位置大数据、Cell网格、网格簇

所属期刊栏目：29

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金61403328,61773331,61572419,61502410;山东省重点研发计划2015GSF115009;山东省自然科学基金ZR2013FM011,ZR2013FQ023,ZR2014FQ016

在线出版日期：2018-09-28（万方平台首次上网日期，不代表论文的发表时间）

页数：共15页

页码：2470-2484