关键词: 密度聚类, 网格聚类, 计算复杂度, 大规模数据集

Abstract: Aiming at the high computational complexity of density based spatial clustering of applications with noise（DBSCAN）, as well the inability to cluster multi-density datasets, a fusion clustering algorithm（G_FDBSCAN） combining the grid clustering algorithm and DBSCAN is proposed. The new algorithm introduces grid division to divide the dataset into sparse areas and dense areas for processing respectively, so as to reduce the time complexity of calculation and the clustering error caused by global parameters. Then, it improves the traditional DBSCAN clustering algorithm to obtain FDBSCAN to take the results of grid clustering in dense areas as a whole to participate in the subsequent clustering, and carries out neighborhood retrieval on the basis of grid division, so as to reduce the invalid query and repeated query of objects in the process of neighborhood retrieval and class expansion, which further reduces the time overhead. Theoretical analysis and experimental tests show that compared with DBSCAN algorithm, DPC algorithm, KMEANS algorithm, BIRCH algorithm and CBSCAN algorithm, when the clustering results are optimal or close to, the clustering efficiency is increased by 24 times, 11times, 2 times, 3 times and1 time respectively.

Key words: density clustering, grid clustering, computational complexity, large spatial datasets