An iterative detection and removal method for detecting spatial clusters of different densities

摘要

A fundamental element of exploratory spatial data analysis is the discovery of clusters in a spatial point dataset. When clusters with distinctly different local densities exist, the determination of suitable density level is still an unsolved problem. On that account, an iterative detection and removal method is proposed in this study. In each step of the novel method, there are two stages. In the detection stage, density level is statistically modeled as a significance level controlled by the number and support domain of the points in the dataset, and then a hypothesis test is used to detect the high-density points. In the removal stage, the Delaunay triangulation network is used to construct clusters and support domains for the identified high-density points, and then the high-density points and their support domains are removed from the dataset. The detection and removal operation are iteratively implemented until no high-density points can be detected. Experiments and comparisons show that the proposed method, on the one hand, outperforms four state-of-the-art methods for detecting clusters of complex shapes and diverse densities, and on the other hand, no user-specified parameters are required. In addition, the support domains of clusters are very useful for spatial analysis.