International Journal of Computational Intelligence Research

Open Access Open Access  Restricted Access Subscription Access
Open Access Open Access Open Access  Restricted Access Restricted Access Subscription Access

An O-Means Clustering Algorithm Using Minimum Spanning Tree


Affiliations
1 Department of Computer Science and Research Center St. Xavier’s College, Palayamkottai, Tamil Nadu, India
     

   Subscribe/Renew Journal


Clustering is a process of discovering group of objects such that the objects of the same group are similar, and objects belonging to different groups are dissimilar. A number of clustering algorithms exist that can solve the problem of clustering, but most of them are very sensitive to their input parameters. Many systems in Science and Engineering can be modeled as graph. Graph based clustering algorithms aimed to find hidden structures from objects. Minimum Spanning Tree clustering algorithm is capable of detecting clusters with irregular boundaries. In this paper we present a new clustering algorithm OMCMST using Minimum Spanning Tree. The newly proposed OMCMST algorithm combines the features of divisive hierarchical and center-based partitional methods using Minimum Spanning Tree. It finds hidden pattern in data set without using any input parameters.

Keywords

Euclidean Minimum Spanning Tree, Clustering, Cluster Separation, Subtree
Subscription Login to verify subscription
User
Notifications
Font Size


  • Anderberg, M.R. “Cluster analysis for Applications” Academic press, Inc. New York, 1973

  • 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.

  • D. Avis “Diameter partitioning.” Discrete and Computational Geometry, 1:265-276, 1986.

  • 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.

  • Diday, E. “The dynamic cluster method in non-hierarchical clustering”. J. Comput. Inf. Sci. 2, 61–88, 1973.

  • Feng Luo,Latifur Kahn, Farokh Bastani, I-Ling Yen, and Jizhong Zhou, “A dynamically growing self-organizing tree(DGOST) for hierarchical gene expression profile”,Bioinformatics,Vol 20,no 16, pp 2605-2617, 2004.

  • 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.

  • Gary Chartrand and Ping Zhang “Introduction to Graph Theory”, Tata MgrawwHill, Paperback-2008.

  • J.C. Gower and G.J.S. Ross “Minimum Spanning trees and single-linkage cluster analysis” Applied Statistics 18, 54-64, 1969.

  • 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.

  • P. Hansen and M. Delattre, “Complete-link cluster analysis by graph coloring” Journal of the American Statistical Association 73, 397-403, 1978.

  • 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.

  • D. Johnson, “The np-completeness column: An ongoing guide”. Journal of Algorithms,3:182-195, 1982.

  • S. John Peter, S.P. Victor, “A Novel Algorithm for Dual similarity clusters using Minimum spanning tree”. Journal of Theoretical and Applied Information technology, Vol.14. No.1 pp 60-66, 2010.

  • 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.

  • Mao, J. and Jain, A.K. “A self-organizing network for hyperellipsoidal clustering (HEC)”. IEEE Trans. Neural Netw. 7, 16–29, 1996.

  • Mc Queen, J. 1967. “Some methods for classification and analysis of multivariate observations”. In Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, 281–297.

  • 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.

  • Symon, M.J. “Clustering criterion and multi-variate normal mixture”. Biometrics 77, 35–43, 1977.

  • 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.

  • 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.

  • Y.Xu, V.Olman and D.Xu. “Minimum spanning trees for gene expression data clustering”. Genome Informatics,12:24-33, 2001.

  • C. Zahn. “Graph-theoretical methods for detecting and describing gestalt clusters”. IEEE Transactions on Computers, C-20:68-86, 1971.


Abstract Views: 384

PDF Views: 0




  • An O-Means Clustering Algorithm Using Minimum Spanning Tree

Abstract Views: 384  |  PDF Views: 0

Authors

S. John Peter
Department of Computer Science and Research Center St. Xavier’s College, Palayamkottai, Tamil Nadu, India

Abstract


Clustering is a process of discovering group of objects such that the objects of the same group are similar, and objects belonging to different groups are dissimilar. A number of clustering algorithms exist that can solve the problem of clustering, but most of them are very sensitive to their input parameters. Many systems in Science and Engineering can be modeled as graph. Graph based clustering algorithms aimed to find hidden structures from objects. Minimum Spanning Tree clustering algorithm is capable of detecting clusters with irregular boundaries. In this paper we present a new clustering algorithm OMCMST using Minimum Spanning Tree. The newly proposed OMCMST algorithm combines the features of divisive hierarchical and center-based partitional methods using Minimum Spanning Tree. It finds hidden pattern in data set without using any input parameters.

Keywords


Euclidean Minimum Spanning Tree, Clustering, Cluster Separation, Subtree

References