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

المؤلفون

  • Shaima M.Aldkeli
  • Kahdhim H.Alibraheemi

DOI:

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

الكلمات المفتاحية:

Clustering، Minimum Spanning Trees، Graph، Clustering techniques

الملخص

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.

المراجع

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/

التنزيلات

منشور

2023-01-17

إصدار

مجلد 12 عدد 1 (2022): Journal of Education for Pure Science- University of Thi-Qar

القسم

Articles

الرخصة

Copyright Policy

Authors retain copyright of their articles published in the Journal of Education for Pure Science (JEPS).

By submitting their work, authors grant the journal a non-exclusive license to publish, distribute, and archive the article in all formats and media.

License

All articles published in JEPS are licensed under the Creative Commons Attribution 4.0 International License (CC BY 4.0).

This license permits unrestricted use, distribution, and reproduction in any medium, provided that the original author(s) and the source are properly credited.

Author Rights

Authors have the right to:

  • Share their articles on personal websites, institutional repositories, and academic platforms

  • Reuse their work in future research and publications

  • Distribute the published version without restriction

Journal Rights

The journal retains the right to:

  • Publish and archive the articles

  • Include them in indexing and archiving systems such as LOCKSS and CLOCKSS

  • Promote and disseminate the published work

Responsibility

The contents of all articles are the sole responsibility of the authors. The journal, editors, and editorial board are not responsible for any errors, opinions, or statements expressed in the published articles.

Open Access Statement

JEPS provides immediate open access to its content, supporting the principle that making research freely available to the public enhances global knowledge exchange.

This work is licensed under a Creative Commons Attribution 4.0 International License.
https://creativecommons.org/licenses/by/4.0/