The week's pick
Random Articles
Reseach Article
Local Density-based Hierarchical Clustering for Overlapping Distribution using Minimum Spanning Tree
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 43 - Number 12 |
| Year of Publication: 2012 |
| Authors: S. John Peter |
10.5120/6153-8542
|
S. John Peter . Local Density-based Hierarchical Clustering for Overlapping Distribution using Minimum Spanning Tree. International Journal of Computer Applications. 43, 12 ( April 2012), 7-11. DOI=10.5120/6153-8542
Abstract
In this paper, we propose a clustering algorithm to find clusters of different sizes, shapes and densities. Density and Hierarchical based approaches are adopted in the algorithm using Minimum Spanning Tree, resulting in a new algorithm – Local Density-based Hierarchical Clustering Algorithm for overlapping data distribution using Minimum Spanning Tree (LDHCODMST). The algorithm is divided into two stages. In the first stage, local density is estimated at each data point. In the second stage, hierarchical approach is used by merging clusters according to the computed cluster distance based on overlap in distribution of data points. The proposed algorithm improves the effectiveness of clustering result in which data are distributed in different shapes and different density, and that it can get a better clustering efficiency.
References
- Anil K. Jain, Richard C. Dubes "Algorithm for Clustering Data", Michigan State University, Prentice Hall, Englewood Cliffs, New Jersey 07632. 1988.
- T. Asano, B. Bhattacharya, M. Keil and F. Yao. "Clustering Algorithms based on minimum and maximum spanning trees". In Proceedings of the 4th Annual Symposium on Computational Geometry,Pages 252-257, 1988.
- N. Chowdhury and C. A. Murthy, " Minimum Spanning Tree –Based Clustering Techniques: Relationship with Bayes Classifier", Pattern Recognition, Vol. 30, no 11, pp 1919-1929, 1997.
- M. Ester, H. -P. Kriegel, J. Sander, and X. Xu. "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise". In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining (KDD96), 1996.
- M. Fredman and D. Willard. "Trans-dichotomous algorithms for minimum spanning trees and shortest paths". In Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science,pages 719-725, 1990.
- H. Gabow, T. Spencer and R. Rarjan. "Efficient algorithms for finding minimum spanning trees in undirected and directed graphs", Combinatorica, 6(2):109-122, 1986.
- S. Guha, R. Rastogi, and K. Shim. "CURE an efficient clustering algorithm for large databases". In Proceeding of the 1998 ACM SIGMOD Int. Conf. on Management of Data , pp 73-84, Seattle, Washington, 1998.
- J. C. Gower and G. J. S. Ross "Minimum Spanning trees and single-linkage cluster analysis" Applied Statistics 18, 54-64, 1969.
- P. Hansen and M. Delattre, "Complete-link cluster analysis by graph coloring" Journal of the American Statistical Association 73, 397-403, 1978.
- A. Hinneburg and D. A. Keim, "An Efficient Approach to Clustering in Large Multimedia Databases with Noise," In Proc. Of th 4th Intl. Conf. on Knowledge Discovery and Data Mining, pp. 58-65. 1998.
- A. Hinneburg and D. A. Keim, "A General Approach to Clustering in Large Databases with Noise," Knowledge and Information Systems (KAIS), vol. 5, no. 4, pp. 387-415, 2003.
- Hubert L. J "Min and max hierarchical clustering using asymmetric similarity measures" Psychometrika 38, 63-72, 1973.
- S. C. Johnson, "Hierarchical clustering schemes" Psychometrika 32, 241-254, 1967.
- Jundi Ding, SongCan Chen , RuNing Ma and Bo Wang, "A Fast Directed Tree Based Neighborhood Clustering Algorithm for Image Segmantation", Neural Information Processing , Lecture Notes in Computer Science, Vol 4233,pp 369-378, 2006.
- D. Karger, P. Klein and R. Tarjan, "A randomized linear-time algorithm to find minimum spanning trees". Journal of the ACM, 42(2):321-328, 1995.
- J. Kruskal, "On the shortest spanning subtree and the travelling salesman problem", In Proceedings of the American Mathematical Society, pp 48-50, 1956.
- M. Laszlo and S. Mukherjee, "Minimum Spanning Tree Partitioning Algorithm for Micro aggregation", IEEE Trans, Knowledge and Data Eng, Vol. 17, no 7, pp 902-911, July 2005.
- J. Nesetril, E. Milkova and H. Nesetrilova. Otakar boruvka on "Minimum spanning tree problem": Translation of both the 1926 papers, comments, history. DMATH: Discrete Mathematics, 233, 2001.
- Oleksandr Grygorash, Yan Zhou, Zach Jorgensen. "Minimum spanning Tree Based Clustering Algorithms". Proceedings of the 18th IEEE International conference on tools with Artificial Intelligence (ICTAI'06) 2006.
- F. Preparata and M. Shamos. "Computational Geometry": An Introduction. Springer-Verlag, Newyr, NY ,USA, 1985¬.
- R. Prim. "Shortest connection networks and some generalization". Bell systems Technical Journal,36:1389-1401, 1957.
- A. Vathy-Fogarassy, A. Kiss, and J. Abonyi , "Hybrid Minimal Spanning Tree and Mixture of Gaussians Based Clustering Algorithms", Proc. IEEE Intl Conf. Tools with Artificial Intelligence, pp 73-81, 2006.
- Y. Xu, V. Olman and D. Xu. "Minimum spanning trees for gene expression data clustering". Genome Informatics,12:24-33, 2001.
- Xiaochun Wang, Xiali Wang and Mitchell Wilkes, "A Divide-and-Conquer Approach for Minimum Spanning Tree Based Clustering", IEEE Trans, Knowledge and Data Eng, Vol. 21 no 7 , pp 945-958, July 2009.
- Yu-Chen Song, J. O'Grady,G. M. P. O'Hare, Wei Wang,"A Clustering Algorithm incorporating Density and Direction", IEEE Computer Society, CIMCA 2008.
- C. Zahn. "Graph-theoretical methods for detecting and describing gestalt clusters". IEEE Transactions on Computers, C-20:68-86, 1971.
- Zhou, S. , Zhao, J. : "A Neighborhood-Based Clustering Algorithm". PAKD 2005, LNAI 3518 361-371 , 1982.
Index Terms
Keywords