A density-based algorithm for discovering clusters in large spatial Databases with Noise
Martin Ester, Hans‐Peter Kriegel, Jörg Sander et al. · 1996
Clustering algorithms are attractive for the task of class iden-tification in spatial databases. However, the application to large spatial databases rises the following requirements for clustering algorithms: minimal requirements of domain knowledge to determine the input parameters, discovery of clusters with arbitrary shape and good efficiency on large da-tabases. The well-known clustering algorithms offer no solu-tion to the combination of these requirements. In this paper, we present the new clustering algorithm DBSCAN relying on a density-based notion of clusters which is designed to dis-cover clusters of arbitrary shape. DBSCAN requires only one input parameter and supports the user in determining an ap-propriate value for it. We performed an experimental evalua-tion of the effectiveness and efficiency of DBSCAN using synthetic data and real data of the SEQUOIA 2000 bench-mark. The results of our experiments demonstrate that (1) DBSCAN is significantly more effective in discovering clus-ters of arbitrary shape than the well-known algorithm CLAR-ANS, and that (2) DBSCAN outperforms CLARANS by factor of more than 100 in terms of efficiency.
Cited by 18,547 works.
Authors
References
- Algorithms for Clustering Data
- Finding groups in data: an introduction to cluster analysis
- The R*-tree: an efficient and robust access method for points and rectangles
- Efficient and Effective Clustering Methods for Spatial Data Mining
- A database interface for clustering in large spatial databases
- An introduction to spatial database systems
- Systems for knowledge discovery in databases
- Multi-step processing of spatial joins
- The SEQUOIA 2000 storage benchmark
- A dynamic approach for clustering data