Spatial clustering with Density-Ordered tree

• We develop a Density-Ordered tree to represent the original data. It efficiently integrates information on not only distance but also density between data points.
• Our method can effectively identify clusters with diverse shapes and densities for spatial dataset.
• Our method provides an innovative way to identify noise and cluster center.
• Experiments demonstrate that our method is more effective than DBSCAN and Chameleon.

Clustering has emerged as an active research direction for knowledge discovery in spatial databases. Most spatial clustering methods become ineffective when inappropriate parameters are given or when datasets of diverse shapes and densities are provided. To address this issue, we propose a novel clustering method, called SCDOT (Spatial Clustering with Density-Ordered Tree). By projecting a dataset to a Density-Ordered Tree, SCDOT partitions the data into several relatively small sub-clusters with a box-plot method. A heuristic method is proposed to find the genuine clusters by repeatedly merging sub-clusters and an iteration strategy is utilized to automatically determine input parameters. Moreover, we also provide an innovative way to identify cluster center and noise. Extensive experiments on both synthetic and real-world datasets demonstrate the superior performance of SCDOT over the baseline methods.