RESEARCH OF MOST EFFECTIVE K-MEANS BASED META HEURISTIC SEARCH ALGORITHM

Abstract

One of the most frequently used algorithms in clustering analysis, the main difficulty encountered in applying the k-means method is that the calculation complexity increases due to the number of observations and it cannot converge to the global best solution for the problem. Moreover, if the problem size and complexity increases, the performance of the k-means method gets worse. For all these reasons, it is important to develop a faster and successful clustering algorithm instead of the classical k-means procedure. Meta-heuristic clustering (MSK) algorithms have been developed for this purpose. Thanks to their search capabilities, MSK algorithms can get rid of local solution traps in complex clustering problems and successfully converge to the global solution. Therefore, the cluster success of MSK methods is directly affected by the search success of MSA techniques. In this article, MSK methods are developed by using current and powerful MSA techniques in the literature and the most effective method is investigated by comparing the performance of these algorithms. For this purpose, ten different MSK algorithms have been developed by hybridizing the k-means method with current and powerful MSA techniques. Five different clustering data sets were used to measure the performance of the developed algorithms. Data obtained from experimental studies were analyzed using statistical test methods. The results of the analysis show that among the MSK algorithms developed in the article, the AGDE-based method has a superior performance compared to its competitors in cluster problems in terms of both the convergence rate and the amount of convergence to the global optimum solution.

Keywords

• Clustering
• K-Means
• Meta-Heuristic Search Algorithm
• Meta-Heuristic Clustering Algorithm

Project Number

1919B011904077

K-ORTALAMALAR TABANLI EN ETKİLİ META-SEZGİSEL KÜMELEME ALGORİTMASININ ARAŞTIRILMASI

Abstract

Kümeleme uygulamalarında en sık kullanılan algoritmalardan biri olan k-ortalamalar yönteminin tatbik edilmesinde karşılaşılan başlıca zorluk, gözlem sayısına bağlı olarak hesaplama karmaşıklığının artması ve problem için küresel en iyi çözüme yakınsayamamadır. Üstelik problem boyutunun ve karmaşıklığının artması halinde k-ortalamalar yönteminin performansı daha da kötüleşmektedir. Tüm bu nedenlerden ötürü klasik k-ortalamalar prosedürü yerine daha hızlı ve başarılı bir kümeleme algoritması geliştirme çalışmaları önem kazanmaktadır. Meta-sezgisel kümeleme (MSK) algoritmaları bu amaçla geliştirilmişlerdir. MSK algoritmaları sahip oldukları arama yetenekleri sayesinde karmaşık kümeleme problemlerinde yerel çözüm tuzaklarından kurtulabilmekte ve küresel çözüme başarılı bir şekilde yakınsayabilmektedirler. Bu makale çalışmasında literatürde yer alan güncel ve güçlü meta-sezgisel arama (MSA) teknikleri kullanılarak MSK algoritmaları geliştirilmekte ve performansları karşılaştırılarak en etkili yöntem araştırılmaktadır. Bu amaçla güncel ve güçlü MSA teknikleri ile k-ortalamalar yöntemi melezlenerek 10 farklı MSK algoritması geliştirilmiştir. Geliştirilen algoritmaların performanslarını ölçmek için 5 farklı kümeleme veri seti kullanılmıştır. Deneysel çalışmalardan elde edilen veriler istatistiksel test yöntemleri kullanılarak analiz edilmiştir. Analiz sonuçları, makalede geliştirilen MSK algoritmaları arasında AGDE tabanlı yöntemin hem yakınsama hızı hem de küresel optimum çözüme yakınsama miktarı açısından kümeleme problemlerinde rakiplerine kıyasla üstün bir performansa sahip olduğunu göstermektedir.

Keywords

• Kümeleme
• K-Ortalamalar Yöntemi
• Meta-Sezgisel Arama Algoritması
• Meta-Sezgisel Kümeleme Algoritması

Supporting Institution

TÜBİTAK

Project Number

1919B011904077

Thanks

Bu çalışmada yürütülen faaliyetler, 2020 yılında TÜBİTAK 2209-A Üniversite Öğrencileri Yurt İçi Araştırma Projeleri Destek Programı kapsamında 1919B011904077 numaralı proje olarak TUBİTAK tarafından desteklenmiştir.

References

1. Alam, M. S., Rahman, M. M., Hossain, M. A., Islam, M. K., Ahmed, K. M., Ahmed, K. T., ... & Miah, M. S. (2019). Automatic Human Brain Tumor Detection in MRI Image Using Template-Based K Means and Improved Fuzzy C Means Clustering Algorithm. Big Data and Cognitive Computing, 3(2), 27.
2. Amiri, M., Amnieh, H. B., Hasanipanah, M., & Khanli, L. M. (2016). A new combination of artificial neural network and K-nearest neighbors models to predict blast-induced ground vibration and air-overpressure. Engineering with Computers, 32(4), 631-644.
3. Arunkumar, N., Mohammed, M. A., Ghani, M. K. A., Ibrahim, D. A., Abdulhay, E., Ramirez-Gonzalez, G., & de Albuquerque, V. H. C. (2019). K-means clustering and neural network for object detecting and identifying abnormality of brain tumor. Soft Computing, 23(19), 9083-9096.
4. Bonab, M. B., Hashim, S. Z. M., Haur, T. Y., & Kheng, G. Y. (2019). A New Swarm-Based Simulated Annealing Hyper-Heuristic Algorithm for Clustering Problem. Procedia Computer Science, 163, 228-236.
5. Borkar, G. M., Patil, L. H., Dalgade, D., & Hutke, A. (2019). A novel clustering approach and adaptive SVM classifier for intrusion detection in WSN: a data mining concept. Sustainable Computing: Informatics and Systems, 23, 120-135.
6. Carrasco, J., García, S., Rueda, M. M., Das, S., & Herrera, F. (2020). Recent trends in the use of statistical tests for comparing swarm and evolutionary computing algorithms: Practical guidelines and a critical review. Swarm and Evolutionary Computation, 54, 100665.
7. Chen, S., Liu, X., Ma, J., Zhao, S., & Hou, X. (2019). Parameter selection algorithm of DBSCAN based on K-means two classification algorithm. The Journal of Engineering, 2019(23), 8676-8679.
8. Cheng, Min-Yuan, and Doddy Prayogo. Symbiotic organisms search: a new metaheuristic optimization algorithm, Computers & Structures 139 (2014): 98-112.

9. Dasarathy, B.V. (1980) "Nosing Around the Neighborhood: A New System Structure and Classification Rule for Recognition in Partially Exposed Environments". IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI-2, No. 1, 67-71.
10. Deng, W., Yao, R., Zhao, H., Yang, X., & Li, G. (2019). A novel intelligent diagnosis method using optimal LS-SVM with improved PSO algorithm. Soft Computing, 23(7), 2445-2462.
11. Eberhart, R., & Kennedy, J. (1995, October). A new optimizer using particle swarm theory. In Micro Machine and Human Science, 1995. MHS'95., Proceedings of the Sixth International Symposium on (pp. 39-43). IEEE.
12. Eftimov, T., Korošec, P., & Seljak, B. K. (2017). A novel approach to statistical comparison of meta-heuristic stochastic optimization algorithms using deep statistics. Information Sciences, 417, 186-215.
13. Galán, S. F. (2019). Comparative evaluation of region query strategies for DBSCAN clustering. Information Sciences, 502, 76-90.
14. Ghazizadeh, G., Gheibi, M., & Matwin, S. (2020, May). CB-DBSCAN: A Novel Clustering Algorithm for Adjacent Clusters with Different Densities. In Canadian Conference on Artificial Intelligence (pp. 232-237). Springer, Cham.
15. Huang, K. W., Wu, Z. X., Peng, H. W., Tsai, M. C., Hung, Y. C., & Lu, Y. C. (2019). Memetic Particle Gravitation Optimization Algorithm for Solving Clustering Problems. IEEE Access, 7, 80950-80968.
16. Jiang, Y., & Zhou, Z. H. (2004, August). Editing training data for kNN classifiers with neural network ensemble. In International symposium on neural networks (pp. 356-361). Springer, Berlin, Heidelberg.
17. Jin, C. H., Pok, G., Lee, Y., Park, H. W., Kim, K. D., Yun, U., & Ryu, K. H. (2015). A SOM clustering pattern sequence-based next symbol prediction method for day-ahead direct electricity load and price forecasting. Energy conversion and management, 90, 84-92.
18. Jothi, R., Mohanty, S. K., & Ojha, A. (2019). DK-means: a deterministic k-means clustering algorithm for gene expression analysis. Pattern Analysis and Applications, 22(2), 649-667.
19. Kahraman, H. T., Aras, S., & Gedikli, E. (2020). Fitness-distance balance (FDB): A new selection method for meta-heuristic search algorithms. Knowledge-Based Systems, 190, 105169.
20. Kahraman, H. T., Sagiroglu, S., Colak, I., Developing intuitive knowledge classifier and modeling of users' domain dependent data in web, Knowledge Based Systems, vol. 37, pp. 283-295, 2013.
21. Karaboga, D., & Basturk, B. (2007). A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. Journal of global optimization, 39(3), 459-471.
22. Kurada, R. R., & Kanadam, K. P. (2019). A Novel Evolutionary Automatic Clustering Technique by Unifying Initial Seed Selection Algorithms into Teaching–Learning-Based Optimization. In Soft Computing and Medical Bioinformatics (pp. 1-9). Springer, Singapore.
23. Kushwaha, N., & Pant, M. (2020). Fuzzy Particle Swarm Page Rank Clustering Algorithm. In Soft Computing: Theories and Applications (pp. 895-904). Springer, Singapore.
24. Lim, T.-S., Loh, W.-Y. & Shih, Y.-S. (1999). A Comparison of Prediction Accuracy, Complexity, and Training Time of Thirty-three Old and New Classification Algorithms. Machine Learning.
25. Miao, J., Zhou, X., & Huang, T. Z. (2020). Local segmentation of images using an improved fuzzy C-means clustering algorithm based on self-adaptive dictionary learning. Applied Soft Computing, 106200.
26. Mirjalili, S., Mirjalili, S. M., & Lewis, A. (2014). Grey wolf optimizer. Advances in engineering software, 69, 46-61.
27. Mohamed, A. W., & Mohamed, A. K. (2019). Adaptive guided differential evolution algorithm with novel mutation for numerical optimization. International Journal of Machine Learning and Cybernetics, 10(2), 253-277.
28. Mohamed, A., Saber, W., Elnahry, I., & Hassanien, A. E. (2020, April). Clustering Analysis Based on Coyote Search Technique. In Joint European-US Workshop on Applications of Invariance in Computer Vision (pp. 182-192). Springer, Cham.
29. Nan, F., Li, Y., Jia, X., Dong, L., & Chen, Y. (2019). Application of improved som network in gene data cluster analysis. Measurement, 145, 370-378.
30. Nithya, A., Appathurai, A., Venkatadri, N., Ramji, D. R., & Palagan, C. A. (2020). Kidney disease detection and segmentation using artificial neural network and multi-kernel k-means clustering for ultrasound images. Measurement, 149, 106952.
31. Pal, S. S., Hira, R., & Pal, S. (2020). Comparison of Four Nature Inspired Clustering Algorithms: PSO, GSA, BH and IWD. In Computational Intelligence in Pattern Recognition (pp. 669-674). Springer, Singapore.
32. Pandeeswari, N., & Kumar, G. (2016). Anomaly detection system in cloud environment using fuzzy clustering based ANN. Mobile Networks and Applications, 21(3), 494-505.
33. Pandey, S., Samal, M., & Mohanty, S. K. (2020). An SNN-DBSCAN Based Clustering Algorithm for Big Data. In Advanced Computing and Intelligent Engineering (pp. 127-137). Springer, Singapore.
34. Pierezan, J., & Coelho, L. D. S. (2018, July). Coyote optimization algorithm: a new metaheuristic for global optimization problems. In 2018 IEEE Congress on Evolutionary Computation (CEC) (pp. 1-8). IEEE.
35. Pouladzadeh, P., Shirmohammadi, S., Bakirov, A., Bulut, A., & Yassine, A. (2015). Cloud-based SVM for food categorization. Multimedia Tools and Applications, 74(14), 5243-5260.
36. Salimi, H. (2015). Stochastic fractal search: a powerful metaheuristic algorithm. Knowledge-Based Systems, 75, 1-18.
37. Singh, H., Kumar, Y., & Kumar, S. (2019). A new meta-heuristic algorithm based on chemical reactions for partitional clustering problems. Evolutionary Intelligence, 12(2), 241-252.
38. Wu, M., Li, X., Liu, C., Liu, M., Zhao, N., Wang, J., ... & Zhu, L. (2019). Robust global motion estimation for video security based on improved k-means clustering. Journal of Ambient Intelligence and Humanized Computing, 10(2), 439-448.
39. Xu, G., Zhang, L., Ma, C., & Liu, Y. (2020). A mixed attributes oriented dynamic SOM fuzzy cluster algorithm for mobile user classification. Information Sciences, 515, 280-293.
40. Yang, X. S., & Deb, S. (2009, December). Cuckoo search via Lévy flights. In 2009 World Congress on Nature & Biologically Inspired Computing (NaBIC) (pp. 210-214). IEEE.
41. Yu, H., Fan, J., & Lan, R. (2019). Suppressed possibilistic c-means clustering algorithm. Applied Soft Computing, 80, 845-872.
42. Yu, H., Wen, G., Gan, J., Zheng, W., & Lei, C. (2020). Self-paced learning for k-means clustering algorithm. Pattern Recognition Letters, 132, 69-75.
43. Zhan, Charles T. Graph-theoretical methods for detecting and describing gestalt clusters. IEEE Transactions on computers, 1971, 100.1: 68-86.
44. Zhao, F., Chen, Y., Liu, H., & Fan, J. (2019). Alternate PSO-based adaptive interval type-2 intuitionistic fuzzy C-means clustering algorithm for color image segmentation. IEEE Access, 7, 64028-64039.
45. Zhao, W., Wang, L. & Zhang, Z. Artificial ecosystem-based optimization: a novel nature-inspired meta-heuristic algorithm. Neural Comput & Applic (2019). https://doi.org/10.1007/s00521-019-04452-x
46. Zhou, Y., Wu, H., Luo, Q., & Abdel-Baset, M. (2019). Automatic data clustering using nature-inspired symbiotic organism search algorithm. Knowledge-Based Systems, 163, 546-557.