A Novel Spatial Clustering Method based on Delaunay Triangulation

Cluster analysis plays an important role in spatial data mining because it allows interesting structures and clusters to be discovered directly from the data without the use of any background knowledge. Commonly-used clustering algorithms tend to identify ellipsoidal, spherical, or other regularly-shaped clusters, but encounter difficulties when dealing with complex underlying groups that possess non-linear shapes, various densities, and noisy connections between multiple clusters. In this article, we proposed a graph-based spatial clustering technique that utilizes Delaunay triangulation along with conventional mechanisms like DBSCAN (density-based spatial clustering of applications with noise) and KNN (k-nearest neighbors). Using these mechanisms, we take into account the distribution of triangle area, angles, and relative side length as one of the criteria for separating clusters with different densities. Moreover, by integrating Otsu's segmentation algorithm, our proposed method is able to resolve the issue of adjacent clusters touching one another. In performance evaluations using simulated synthetic data, as well as real data with regular and irregular structures, our methodology maintains top performance in clustering and separability of neighboring clusters compared to traditional clustering techniques.

spatial clustering

Delaunay triangulation

density estimation

DBSCAN

KNN

Otsu's segmentation 

Mid-Level

Machine Learning

Symposium on Data Science and Statistics (SDSS) 2023