DocumentCode :
1889630
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
fYear :
2006
fDate :
2-5 July 2006
Firstpage :
102
Lastpage :
111
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;
fLanguage :
English
Publisher :
ieee
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
Type :
conf
DOI :
10.1109/ISVD.2006.18
Filename :
4124809
Link To Document :
بازگشت