Improve Clustering -Based Graph Algorithms Using (MST) Minimal Spanning Trees
Keywords:
Clustering, Minimum Spanning Trees, Graph, Clustering techniquesAbstract
Clustering is a significant data mining method that is used in a variety of disciplines. Clustering
attempts to divide a big set of data into smaller groups that are more similar within the same group, but
distinct from other groups, each subgroup referred to as a “cluster”. This paper introduces the concept of
clustering, the most important clustering approaches, and the application of graph-based clustering
utilizing one of the graph algorithms, the Minimum Spanning Tree (MST) algorithm, which groups
related nodes into clusters. The method has been evaluated on five various data sets utilizing cluster
validation measures (Adjusted Rand Index, v-measure_ scores), and its performance on all of these data
sets has been demonstrated when compared to other algorithms.
References
Rui Xu and D. Wunsch, "Survey of clustering algorithms," IEEE Transactions on Neural Networks,
vol. 16, no. 3, pp. 645-678, May 2005.
K. P. Sinaga and M. Yang, "Unsupervised K-Means Clustering Algorithm," IEEE Access, vol. 8, pp.
-80727, 2020.
Sathiyakumari, K. et al. “A Survey on Various Approaches in Document Clustering.” (2011).
O. Grygorash, Y. Zhou and Z. Jorgensen, "Minimum Spanning Tree Based Clustering Algorithms,"
18th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'06), 2006, pp. 73-
Kruskal, Joseph B. “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman
Problem.” Proceedings of the American Mathematical Society, vol. 7, no. 1, American Mathematical
Society, 1956, pp. 48–50.
R. C. Prim, "Shortest connection networks and some generalizations," in The Bell System Technical
Journal, vol. 36, no. 6, pp. 1389-1401, Nov. 1957.
C. T. Zahn, “Graph-theoretical methods for detecting and describing gestalt clusters,” IEEE Trans.
Computers, Vol. 20, No. 1, pp. 68–86, January 1971.
Xu Y, Olman V, Xu D. Minimum spanning trees for gene expression data clustering. Genome Inform.
; 12:24-33. PMID: 11791221.
Peter, S. John, and S. P. Victor. "A Novel Algorithm for Informative Meta Similarity Clusters Using
Minimum Spanning Tree." arXiv preprint arXiv:1005.4585 (2010).
Müller A.C., Nowozin S., Lampert C.H. (2012),” Information Theoretic Clustering Using Minimum
Spanning Trees”. In: Pinz A., Pock T., Bischof H., Leberl F. (eds) Pattern Recognition. DAGM/OAGM
Lecture Notes in Computer Science, vol 7476. Springer, Berlin, Heidelberg.
Wang, Xiaochun et al. “Enhancing minimum spanning tree-based clustering by removing densitybased
outliers.” Digit. Signal Process. 23 (2013): 1523-1538.
Zhong, C., Malinen, M., Miao, D., Franti, P. (2015). ¨ A fast minimum spanning tree algorithm
based on k-means. Information Sciences.
Lv, Xiao-bo et al. “CciMST: A Clustering Algorithm Based on Minimum Spanning Tree and Cluster
Centers.” Mathematical Problems in Engineering (2018): n. pag.
Li, Jia et al. “A scaled-MST-based clustering algorithm and application on image segmentation.”
Journal of Intelligent Information Systems 54 (2019): 501-525.
Sisodia, Deepti et al. “Clustering Techniques: A Brief Survey of Different Clustering Algorithms.”
(2012).
Faizan, Muhammad et al. “Applications of Clustering Techniques in Data Mining: A Comparative
Study.” International Journal of Advanced Computer Science and Applications 11 (2020): n. pag
Saxena, Amit, et al. "A review of clustering techniques and developments." Neurocomputing 267
(2017): 664-681
Madhulatha, T. Soni. "An overview on clustering methods." arXiv preprint arXiv:1205.1117 (2012).
Wang, Rixin, et al. "Fault detection of flywheel system based on clustering and principal component
analysis." Chinese Journal of Aeronautics 28.6 (2015): 1676-1688.
P. Praveen, B. Rama and T. Sampath Kumar, "An efficient clustering algorithm of minimum
Spanning Tree," Third International Conference on Advances in Electrical, Electronics, Information,
Communication and Bio-Informatics (AEEICB), 2017, pp. 131-135.
J. G. M. Esgario and R. A. Krohling, "Clustering with Minimum Spanning Tree using TOPSIS with
Multi-Criteria Information," IEEE International Conference on Fuzzy Systems (FUZZ-IEEE), 2018, pp.
-7.
Vathy-Fogarassy, Ágnes, and Janos Abonyi. Graph-based Clustering and Data Visualization
Algorithms. Springer, 2013.
Handl, Julia, Joshua Knowles, and Douglas B. Kell. "Computational cluster validation in postgenomic
data analysis." Bioinformatics 21.15 (2005): 3201-3212.
Al-Mhairat, Muthana et al. (2019). Performance Evaluation of clustering Algorthims.
Pedregosa, Fabian et al. “Scikit-learn: Machine Learning in Python.” J. Mach. Learn. Res. 12 (2011):
-2830.
Downloads
Published
Issue
Section
License
The Authors submitting a manuscript do so on the understanding that if accepted for publication, copyright of the article shall be assigned to Journal of education for Pure Science (Jeds), University of Thi-Qar as publisher of the journal.
Copyright encompasses exclusive rights to reproduce and deliver the article in all form and media, including reprints, photographs, microfilms and any other similar reproductions, as well as translations. The reproduction of any part of this journal, its storage in databases and its transmission by any form or media, such as electronic, electrostatic and mechanical copies, photocopies, recordings, magnetic media, etc. , will be allowed only with a written permission from Journal of education for Pure Science (Jeds), University of Thi-Qar.
Journal of education for Pure Science (Jeds), University of Thi-Qar, the Editors and the Advisory International Editorial Board make every effort to ensure that no wrong or misleading data, opinions or statements be published in the journal. In any way, the contents of the articles and advertisements published in the Journal of education for Pure Science (Jeds), University of Thi-Qar are sole and exclusive responsibility of their respective authors and advertisers.
