CFP last date
20 May 2024
Call for Paper
June Edition
IJCA solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 20 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

Comparison of Parameter Free MST Clustering Algorithm with Hierarchical Agglomerative Clustering Algorithms

by Ramakrishnam Raju BHVS, Valli Kumari.V
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 34 - Number 4
Year of Publication: 2011
Authors: Ramakrishnam Raju BHVS, Valli Kumari.V
10.5120/4086-5894

Ramakrishnam Raju BHVS, Valli Kumari.V . Comparison of Parameter Free MST Clustering Algorithm with Hierarchical Agglomerative Clustering Algorithms. International Journal of Computer Applications. 34, 4 ( November 2011), 26-31. DOI=10.5120/4086-5894

@article{ 10.5120/4086-5894,
author = { Ramakrishnam Raju BHVS, Valli Kumari.V },
title = { Comparison of Parameter Free MST Clustering Algorithm with Hierarchical Agglomerative Clustering Algorithms },
journal = { International Journal of Computer Applications },
issue_date = { November 2011 },
volume = { 34 },
number = { 4 },
month = { November },
year = { 2011 },
issn = { 0975-8887 },
pages = { 26-31 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume34/number4/4086-5894/ },
doi = { 10.5120/4086-5894 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:20:13.531315+05:30
%A Ramakrishnam Raju BHVS
%A Valli Kumari.V
%T Comparison of Parameter Free MST Clustering Algorithm with Hierarchical Agglomerative Clustering Algorithms
%J International Journal of Computer Applications
%@ 0975-8887
%V 34
%N 4
%P 26-31
%D 2011
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Clustering is a splitting up of data into groups of similar objects called clusters. The objects in a cluster are similar between themselves and dissimilar compared to objects of other clusters. This paper is intended to study and compare different data clustering algorithms. The algorithms in investigation are: hierarchical agglomerative clustering algorithms: Parameter Free Minimum Spanning Tree (MST) clustering algorithm and single link, complete link and average link clustering algorithms. K-means partitional clustering algorithm is used in the results as a reference. Our experimental evaluation shows that Parameter Free Minimum Spanning Tree algorithms are lead to better clustering results than hierarchical agglomerative algorithms, which suggests that Parameter Free Minimum Spanning Tree clustering algorithms are well-suited for clustering.

References
  1. Michael B. Eisen, Paul T. Spellman, Patrick O. Brown, David Botstein, “Cluster analysis and display of genome-wide expression patterns”, Proc. Natl. Acad. Sci. USA 95, 14863-14867.
  2. Jain, A. K., Murty, M. N., and Flynn, P. J., 1999, "Data Clustering: A Review", ACM Computing Surveys, vol. 31, no. 3, pp. 264-323.
  3. Jain, A.K. and Dubes, R.C., Algorithms for Clustering Data, Prentice-Hall advanced reference series, Prentice-Hall. Englewood Cliffs, NJ, USA, 1988
  4. C. T. Zahn. “Graph-theoretic methods for detecting and describing gestalt clusters”. IEEE Trans. Comput., 20:68–86, 1971.
  5. S. Ray, R.H. Turi. “ Determination of Number of Clusters in K–Means Clustering and application in color Image Segmentation”, Proc. 4th Intl. Conf. ICAPRDT ‘99, Calcutta India, pp. 137-143 (1999).
  6. Hichem Frigui and Raghu Krishnapuram, “Clustering by Competitive Agglomeration”, Journal: Pattern Recognition-PR, Vol. 30, No. 7, pp. 1109-1119, 1997.
  7. Osama Abu Abbas, “Comparisons Between Data Clustering Algorithms,” The International Arab Journal of Information Technology, vol. 5, no. 3, pp. 320-325, 2008.
  8. Sung Young Jung, and Taek-Soo Kim, “An Agglomerative Hierarchical Clustering Using Partial Maximum Array and Incremental Similarity Computation Method”, Proceedings of the 2001 IEEE International Conference on Data Mining, p.265-272, November 29-December 02, 2001.
  9. “Cluster analysis” in http://en.wikipedia.org/ wiki/Cluster_Analysis, last accessed on 29th April, 2011.
  10. “Hierarchical Clustering Algorithms” in http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/hierarchical.html, last accessed on 12th May, 2011
  11. Margaret H.Dunham “Data Mining Introductory and Advance Topics”, Low price Edition – Pearson Education, Delhi, 2003.
  12. S. Guha, R. Rastogi, and K. Shim, “CURE: An efficient clustering algorithm for large databases,” in Proc. ACM SIGMOD Int. Conf. Management of Data, 1998, pp. 73–84.
  13. Guha, S., Rastogi, R., and Shim, K. “ROCK: A robust clustering algorithm for categorical attributes,” Inf. Syst., vol. 25, no. 5, pp. 345–366, 2000.
  14. G. Karypis, E. Han, and V. Kumar, “Chameleon: Hierarchical clustering using dynamic modeling,” IEEE Computer, vol. 32, no. 8, pp. 68–75, Aug. 1999.
  15. T. Zhang, R. Ramakrishnan, and M. Livny, “BIRCH: An efficient data clustering method for very large databases,” in Proc. ACM SIGMOD Conf. Management of Data, 1996, pp. 103–114.
  16. Ying Xu, Victor Olman, Dong Xu, “Clustering gene expression data using a graph theoretic approach: an application of minimum spanning trees”, Bioinformatics, Vol 18, No 4, Pages 536-545, 2002.
  17. R. Prim. “Shortest connection networks and some generalizations”. Bell System Technical Journal, 36:1389–1401, 1957.
  18. J.B. Kruskal, “On the shortest spanning subtree of a graph and the traveling salesman problem”. American Mathematical Society, 7(48–50), 1956.
  19. B.H.V.S.Ramakrishnam Raju, V. Valli Kumari, “Parameter Free Minimum Spanning Tree (PFMST) based clustering algorithm”, PDCTA 2011, CCIS 203, pp. 552-560, Springer, 2011. ( yet to be published)
  20. J.C. Gower and G.J.S. Ross, “Minimal spanning trees and single linkage cluster analysis”. Applied Statistics, 18:54–64, 1969.
  21. C.C. Gotlieb and S. Kumar, “Semantic clustering of index terms”. Journal of the ACM, 15(4):493–513, 1968.
  22. F.B. Backer and L.J. Hubert. “A graph-theoretic approach to goodness-of-fit in complete-link hierarchical clustering”, Journal of the American Statistical Association, 71:870–878, 1976.
  23. J.G. Augustson and J. Minker, “An analysis of some graph theoretical clustering techniques”, Journal of ACM, 17(4):571–588, 1970.
  24. V.V. Raghavan and C.T. Yu. “A comparison of the stability characteristics of some graph theoretic clustering methods”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 3:393–402, 1980.
  25. Kazumasa Ozawa, “A stratificational overlapping cluster scheme”. Pattern Recognition, vol. 18, no. 3-4, pp. 279-286, 1985.
  26. G.T. Toussaint, “The relative neighborhood graph of a finite planar set”, Pattern Recognition, 12:261–268, 1980.
  27. R. Yager, “Intelligent control of the hierarchical agglomerative clustering process,” IEEE Trans. Syst., Man, Cybern., vol. 30, no. 6, pp.835–845, 2000.
  28. E. Hartuv and R. Shamir, “A clustering algorithm based on graph connectivity”, Inf. Process. Lett., vol. 76, pp. 175–181, 2000.
  29. G. Nagy, “State of the art in pattern recognition”. In Proceedings of the IEEE, volume 56, pages 836–862, 1968.
  30. W.H.E Day, Complexity theory: An introduction for practitioners of classification. In Clustering and Classification, P.Arabie and L. Hubert, Eds. World Scientific Publishing Co., Inc., River Edge, NJ. 1992
  31. K. Krishna and M. Murty, “Genetic K-means algorithm,” IEEE Trans.Syst., Man, Cybern. B, Cybern., vol. 29, no. 3, pp. 433–439, Jun. 1999.
  32. A. K. Jain, Algorithms for Clustering Data, Prentice Hall, Englewood Cliffs, New Jersey, 1988.
  33. UCI Machine Learning Repository: Data Sets, http://archive.ics.uci.edu/ml/datasets.html, last accessed on 10th May, 2011.
Index Terms

Computer Science
Information Sciences

Keywords

Clustering hierarchical Partitional Minimum Spanning Tree

Powered by PhDFocusTM