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

来源：软件学报杂志2018年第8期北京时间：

作者：于彦伟,贾召飞,曹磊,赵金东,刘兆伟,刘惊雷

单位：于彦伟，烟台大学 计算机与控制工程学院, 山东 烟台 26400511,贾召飞，烟台大学 计算机与控制工程学院, 山东 烟台 26400502,曹磊，Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge 02139, USA03,赵金东，烟台大学 计算机与控制工程学院, 山东 烟台 26400504,刘兆伟，烟台大学 计算机与控制工程学院, 山东 烟台 26400505,刘惊雷，烟台大学 计算机与控制工程学院, 山东 烟台 26400506

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

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

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