Abstract
Minimum spanning tree (MST) based clustering algorithms have been employed successfully to detect clusters of heterogeneous nature. Given a dataset of n random points, most of the MST-based clustering algorithms first generate a complete graph G of the dataset and then construct MST from G. The first step of the algorithm is the major bottleneck which takes O(n 2) time. This paper proposes two algorithms namely MST-based clustering on K-means Graph and MST-based clustering on Bi-means Graph for reducing the computational overhead. The proposed algorithms make use of a centroid based nearest neighbor rule to generate a partition-based Local Neighborhood Graph (LNG). We prove that both the size and the computational time to construct the graph (LNG) is O(n 3/2), which is a \(O(\sqrt n)\) factor improvement over the traditional algorithms. The approximate MST is constructed from LNG in \(O(n^{3/2} \lg n)\) time, which is asymptotically faster than O(n 2). The advantage of the proposed algorithms is that they do not require any parameter setting which is a major issue in many of the nearest neighbor finding algorithms. Experimental results demonstrate that the computational time has been reduced significantly by maintaining the quality of the clusters obtained from the MST.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Jain, A.K., Murty, M.N., Flynn, P.J.: Data clustering: a review. ACM Computing Surveys (CSUR) 31(3), 264–323 (1999)
Schaeffer, S.E.: Graph clustering. Computer Science Review 1(1), 27–64 (2007)
Zahn, C.T.: Graph-theoretical methods for detecting and describing gestalt clusters. IEEE Transactions on Computers 100(1), 68–86 (1971)
Xu, Y., Olman, V., Xu, D.: Minimum spanning trees for gene expression data clustering. GENOME INFORMATICS SERIES, pp. 24–33 (2001)
Laszlo, M., Mukherjee, S.: Minimum spanning tree partitioning algorithm for microaggregation. IEEE Transactions on Knowledge and Data Engineering 17(7), 902–911 (2005)
Luo, T., Zhong, C.: A neighborhood density estimation clustering algorithm based on minimum spanning tree. In: Yu, J., Greco, S., Lingras, P., Wang, G., Skowron, A. (eds.) RSKT 2010. LNCS, vol. 6401, pp. 557–565. Springer, Heidelberg (2010)
Zhong, C., Miao, D., Fränti, P.: Minimum spanning tree based split-and-merge: A hierarchical clustering method. Information Sciences 181(16), 3397–3410 (2011)
Wang, X., Wang, X.L., Chen, C., Wilkes, D.M.: Enhancing minimum spanning tree-based clustering by removing density-based outliers. Digital Signal Processing 23(5), 1523–1538 (2013)
Wang, X., Wang, X., Wilkes, D.M.: A divide-and-conquer approach for minimum spanning tree-based clustering. IEEE Transactions on Knowledge and Data Engineering 21(7), 945–958 (2009)
Cheng, B., Yang, J., Yan, S., Fu, Y., Huang, T.S.: Learning with L1-graph for image analysis. IEEE Transactions on Image Processing 19(4), 858–866 (2010)
Liu, H., Yan, S.: Robust graph mode seeking by graph shift. In: Proceedings of the 27th International Conference on Machine Learning (ICML 2010), pp. 671–678 (2010)
Zhong, C., Malinen, M., Miao, D., Fränti, P.: Fast approximate minimum spanning tree algorithm based on K-means. In: Wilson, R., Hancock, E., Bors, A., Smith, W. (eds.) CAIP 2013, Part I. LNCS, vol. 8047, pp. 262–269. Springer, Heidelberg (2013)
Chen, X.: Clustering based on a near neighbor graph and a grid cell graph. Journal of Intelligent Information Systems 40(3), 529–554 (2013)
Chavent, M., Lechevallier, Y., Briant, O.: DIVCLUS-T: A monothetic divisive hierarchical clustering method. Computational Statistics and Data Analysis 52(2), 687–701 (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Jothi, R., Mohanty, S.K., Ojha, A. (2015). Fast Minimum Spanning Tree Based Clustering Algorithms on Local Neighborhood Graph. In: Liu, CL., Luo, B., Kropatsch, W., Cheng, J. (eds) Graph-Based Representations in Pattern Recognition. GbRPR 2015. Lecture Notes in Computer Science(), vol 9069. Springer, Cham. https://doi.org/10.1007/978-3-319-18224-7_29
Download citation
DOI: https://doi.org/10.1007/978-3-319-18224-7_29
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-18223-0
Online ISBN: 978-3-319-18224-7
eBook Packages: Computer ScienceComputer Science (R0)