Improve Clustering -Based Graph Algorithms Using (MST) Minimal Spanning Trees

Authors

  • College of Science University of Basrah
  • college of Science University of Basrah

DOI:

https://doi.org/10.32792/jeps.v12i1.154

Keywords:

Clustering, Minimum Spanning Trees, Graph, Clustering techniques

Abstract

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.

http://cs.joensuu.fi/sipu/datasets/

Downloads

Published

2023-01-17