一种面向大规模二维点集数据的密度聚类算法

A Density Clustering Algorithm for Large-scale Two-dimensional Lattice Data

针对密度聚类算法无法应用于大规模数据集的问题,提出一种基于划分网格的密度聚类算法(GDSCAN)。将大规模二维点阵图划分为若干网格,网格最短边不小于给定邻域半径,目标点所在网格中任意点的邻域范围不会超过与该网格直接连接的网格,只需在保留网格内寻找邻域点,从而减少计算量;聚类从任意无类别核心点开始,将该点的所有密度可达组成一个簇,以此类推直至所有核心点都有类别;采用提出的GDSCAN算法对不同数量级的二维路网节点进行聚类验证。结果表明,GDSCAN算法可有效解决大规模二维点阵数据集中密度聚类的效率问题,数据量越大,效果越明显,且时间复杂度明显降低。

Aiming at the problem that the density clustering algorithm cannot be applied to large-scale data sets,a grid dividing-based density clustering algorithm(GDSCAN)was proposed.The large-scale two-dimensional lattice map was divided into several grids,the shortest edge of the grid was not less than the given neighborhood radius,then the neighborhood range of any point in the grid where the target point was located will not exceed the grid which directly conneced with the grid,only the neighborhood points need to be found in the reserved mesh,so as to reduce the calculation amount;Clustering started from any unclassified core point,and formed a cluster with all the density of the point,and so on until all core points had a class.The proposed GDSCAN algorithm was used to cluster the two-dimensional road network nodes of different orders of magnitude.The results show that the GDSCAN algorithm can effectively solve the efficiency problem of density clustering in large-scale two-dimensional lattice data sets,and the larger the amount of data is,the more obvious the effect is,and the time complexity is significantly reduced.