A Novel Spatial Clustering Algorithm Based on Delaunay Triangulation
- 1
- 2
Abstract
Exploratory data analysis is increasingly more necessary as larger spatial data is managed in electro-magnetic media. Spatial clustering is one of the very important spatial data mining techniques which is the discovery of interesting rela-tionships and characteristics that may exist implicitly in spatial databases. So far, a lot of spatial clustering algorithms have been proposed in many applications such as pattern recognition, data analysis, and image processing and so forth. However most of the well-known clustering algorithms have some drawbacks which will be presented later when ap-plied in large spatial databases. To overcome these limitations, in this paper we propose a robust spatial clustering algorithm named NSCABDT (Novel Spatial Clustering Algorithm Based on Delaunay Triangulation). Delaunay dia-gram is used for determining neighborhoods based on the neighborhood notion, spatial association rules and colloca-tions being defined. NSCABDT demonstrates several important advantages over the previous works. Firstly, it even discovers arbitrary shape of cluster distribution. Secondly, in order to execute NSCABDT, we do not need to know any priori nature of distribution. Third, like DBSCAN, Experiments show that NSCABDT does not require so much CPU processing time. Finally it handles efficiently outliers.
- G. Piatetsky-Shapiro and W. J. Frawley. “Knowledge discovery in databases,” AAAI/MIN Press, 1999.
- U. Fayyad, G. Piatetsky-Shapiro, and P. Smyth. “The KDD process for extracting useful knowledge from vol-umes of data,” Communications of ACM, Vol. 39, 1996.
- S. Shekhar, C. T. Lu, P. Zhang, and R. Liu, “Data mining for selective visualization of large spatial datasets,” Proc-essing of 14th IEEE international conference on tools with artificial intelligence (ICTAI’02), 2002.
- J. Han and M. Kamber, “Data mining: Concepts and Techniques,” Academic Press, 2001.
- I. Atsushi and T. Ken, “Graph-based clustering of random point set,” Structural, Syntactic and Statistical Pattern Recognition, Springer Berlin, pp. 948–956, 2004.
- R. T. Ng and J. Han, “CLARANS: A method for cluster-ing objects for spatial data mining,” IEEE Transactions on Knowledge and Data Engineering, Vol. 14, No. 5, pp. 1003–1016, 2002.
- S. Guha, R. Rastogi, and K. Shim, “CURE: An efficient clustering algorithm for large databases,” Proceedings of the 1998 ACM SIGMOD international conference on Management of data, ACM Press, pp. 73–84, 1998.
- T. Zhang, R. Ramakrishnan, and M. Livny, “BIRCH: An efficient data clustering method for very large databases,” Proceedings of the 1996 ACM SIGMOD international conference on Management of data, ACM Press, pp. 103–114, 1996.
- L. Kaufman and P. J. Rousseeuw, “Finding Groups in Data: An introduction to cluster analysis,” John Wiley & Sons, 1990.
- M. Ester, H. P. Kriegel, J. Sander, and X. Xu, “Density- based algorithm for discovering clusters in large spatial databases with noise,” Proceedings of the 1996 Knowl-edge Discovery and Data Mining (KDD’96) international conference, AAAI Press, pp. 226–231, 1996.
- M. Ankerst, M. M. Breunig, H. P. Kriegel, et al., “OP-TICS: Ordering points to identify the clustering struc-ture,” Proceedings of the International Conference on Management of Data (SIGMOD), ACM Press, pp. 49–60, 1999.
- J. Sander, M. Ester, H. P. Kriegel, and X. Xu, “Den-sity-Based Clustering in Spatial Databases: The algorithm GDBSCAN and its applications,” Data Mining and Knowledge Discovery, Vol. 2, No. 2, pp.169–194, 1998.
- X. Wang and H. J. Hamilton, “DBRS: A density-based spatial clustering method with random sampling,” Pro-ceedings of the 7th PAKDD, Springer, pp. 563–575, 2003.