Title :
CRYSTAL - A new density-based fast and efficient clustering algorithm
Author :
Bhattacharya, Priyadarshi ; Gavrilova, Marina L.
Author_Institution :
Dept. of Comput. Sci., Calgary Univ., Calgary, AB
Abstract :
In this paper, we present a fast O(nlogn) clustering algorithm based on Delaunay triangulation for identifying clusters of different shapes, not necessarily convex. The clustering result is similar to human perception of clusters. The novelty of our method is the growth model we follow in the cluster formation that resembles the natural growth of a crystal. Our algorithm is able to identify dense as well as sparse clusters and also clusters connected by bridges. We demonstrate clustering results on several synthetic datasets and provide a comparison with popular K-means based clustering methods. The clustering is based purely on proximity analysis in the Delaunay triangulation and avoids usage of global parameters. It is robust in the presence of noise. Finally, we demonstrate the capability of our clustering algorithm in handling very large datasets.
Keywords :
mesh generation; pattern clustering; CRYSTAL; Delaunay triangulation; K-means based clustering methods; density based clustering algorithm; growth model; proximity analysis; Bridges; Clustering algorithms; Clustering methods; Computer science; Convergence; Drives; Geographic Information Systems; Humans; Noise robustness; Shape;
Conference_Titel :
Voronoi Diagrams in Science and Engineering, 2006. ISVD '06. 3rd International Symposium on
Conference_Location :
Banff, Alberta, BC
Print_ISBN :
0-7695-2630-6
DOI :
10.1109/ISVD.2006.18