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

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

Fast Density-Based Clustering Algorithm for Location Big Data

This paper proposes a simple but efficient density-based clustering, named CBSCAN, to fastdiscover cluster patterns with arbitrary shapes and noises from location big data effectively. Firstly, we define the notion of Cell and propose distance analysis principle based on Cell, which can quickly find core points in high density areas and density relationships with other points without distance computing. Secondly, we propose the Cell-based cluster that maps point-based density cluster to grid-based density cluster. By leveragingexclusion grids and relationships with their adjacent grids, we can fast determine all inclusion grids of Cell-based cluster. Furthermore, we implement a fast density-based algorithm based onthe distance analysis principle and Cell-base cluster, which transforms DBSCAN of point-based expansion to Cell-based expansion clustering.The proposed algorithm improves clustering efficiencysignificantly by using inherent property of location data to reduce huge number of distance calculations. Finally, our comprehensive experiments on benchmark datasets demonstrate the clustering effectiveness of the proposed algorithm.Experimental results onmassive-scale real and synthetic location datasets show that CBSCAN improves 525 fold, 30 fold and 11 fold of efficiencycompared with DBSCAN, DBSCAN with PR-Tree and Grid index optimization respectively.