K-Means Centroid Optimization with Genetic Algorithm for Clustering Micro, Small, Medium Enterprises in Yogyakarta

Muhammad Faris Akbar; Lisna Zahrotun

doi:10.30595/juita.v13i2.25480

Authors

Muhammad Faris Akbar Ahmad Dahlan University
Lisna Zahrotun Ahmad Dahlan University

DOI:

https://doi.org/10.30595/juita.v13i2.25480

Keywords:

Genetic Algorithm, K-Means, Optimization,

Abstract

K-Means is a widely used data clustering algorithm due to its simplicity and fast performance. However, the weakness of K-Means is in determining the cluster centroid randomly, which can result in suboptimal clustering results, especially since it tends to get stuck on local solutions. This research aims to overcome this weakness by integrating the Genetic Algorithms (GA) into the K-Means process, optimizing the initial centroid, and improving clustering quality. The method combines GA with K-Means on MSME data in Yogyakarta, where GA rearranges the cluster's initial centroid more optimally. The results showed that this method reduced the average value of the Davies-Bouldin Index (DBI) from 1,819 in conventional K-Means to 1,349 with GA integration, indicating an improvement in cluster quality by 25.9%. These results prove that integration of GA with K-Means improves clustering accuracy and improves cluster separation, as measured by a significant decrease in DBI value

Author Biographies

Muhammad Faris Akbar, Ahmad Dahlan University

Faculty of Industrial Engineering, Informatics Student

Lisna Zahrotun, Ahmad Dahlan University

Industrial Engineering Faculty, Informatics Lecturer

References

[1] B. Khusul Khotimah, F. Irhamni, and T. Sundarwati, “A GENETIC ALGORITHM FOR OPTIMIZED INITIAL CENTERS K-MEANS CLUSTERING IN SMEs,” J Theor Appl Inf Technol, vol. 15, no. 1, 2016, [Online]. Available: www.jatit.org

[2] Y. Ansori and C. Wulandari, “CRISP-DM Method On Indonesian Micro Industries (UMKM) Using K-Means Clustering Algorithm,” MATICS: Jurnal Ilmu Komputer dan Teknologi Informasi (Journal of Computer Science and Information Technology), vol. 14, no. 2, pp. 35–40, Oct. 2022, doi: 10.18860/mat.v14i2.13760.

[3] R. Kesuma Dinata, H. Novriando, N. Hasdyna, S. Retno, J. Hadari Nawawi, and K. Barat, “JEPIN (Jurnal Edukasi dan Penelitian Informatika) Reduksi Atribut Menggunakan Information Gain untuk Optimasi Cluster Algoritma K-Means,” JEPIN (Jurnal Edukasi dan Penelitian Informatika), 2020.

[4] R. Kurniati, O. Arsalan, and Y. Ramadhana, “Initial Centroid Determination Using Genetic Algorithm in Data Clustering,” Jurnal Generic, vol. Vol 13 No 1 (2021), 2021.

[5] G. J. Oyewole and G. A. Thopil, “Data clustering: application and trends,” Artif Intell Rev, vol. 56, no. 7, pp. 6439–6475, Jul. 2023, doi: 10.1007/s10462-022-10325-y.

[6] L. Zahrotun, S. Hadi Nugroho, U. Linarti, and A. Hendri Soleliza Jones, “Analisis Persebaran UMKM Bidang Jasa Menggunakan Metode AHC Complete Linkage,” KESATRIA: Jurnal Penerapan Sistem Informasi (Komputer & Manajemen), vol. 4, no. 2, pp. 255–265, 2023.

[7] M. Faishal, R. Juniardi, L. Zahrotun, U. Linarti, and A. Hendri Soleliza Jones, “Data Mining Pengelompokan UMKM di Bidang Fashion dan Kerajinan Kota Yogyakarta Menggunakan AHC Average Linkage,” JUMANJI, vol. 7, no. 2, pp. 2598–8069, 2023.

[8] L. Zahrotun, Y. R. Amanatullah, U. Linarti, and A. H. Soleliza Jones, “Strategy for improving and empowering MSMEs through grouping using the AHC method,” Jurnal Sisfokom (Sistem Informasi dan Komputer), vol. 13, no. 1, pp. 130–136, Feb. 2024, doi: 10.32736/sisfokom.v13i1.2021.

[9] U. Linarti, A. Rahmawati, A. Hendri Soleliza Jones, and L. Zahrotun, “Penerapan Metode K-Medoids Guna Pengelompokan Data Usaha Mikro, Kecil dan Menengah (UMKM) Bidang Kuliner Di Kota Yogyakarta,” Jurnal Ilmu Komputer dan Sistem Informasi (JIKOMSI), vol. 7, no. 1, pp. 37–45, 2024.

[10] L. Zheng, L. Haiyan, L. Ce, L. Qingyu, and L. Gang, “Research on K-Means Clustering Optimization Algorithm Based on Machine Learning,” Hans Journal of Data Mining, vol. 12, no. 01, pp. 20–26, 2022, doi: 10.12677/hjdm.2022.121003.

[11] Taslim, D. Toresa, D. Jollyta, D. Suryani, and E. Sabna, “Optimasi K-Means dengan Algoritma Genetika untuk Target Pemanfaat Air Bersih Provinsi Riau,” Indonesian Journal of Computer Science, vol. 10, no. 1, Jul. 2022, doi: 10.33022/ijcs.v10i1.3064.

[12] M. E. Al Rivan and R. A. Sonaru, “Perbandingan Metode K-Means dan GA K-Means untuk Clustering Dataset Heart Disease Patients,” JATISI (Jurnal Teknik Informatika dan Sistem Informasi), vol. 9, no. 3, pp. 2585–2597, Sep. 2022, doi: 10.35957/jatisi.v9i3.2799.

[13] Hendrik, Kusrini, and Kusnawi, “OPTIMASI PENENTUAN SENTROID AWAL PADA K-MEANS UNTUK MENINGKATKAN HASIL EVALUASI DAVIES-BOULDIN INDEX,” Jurnal Informatika Teknologi dan Sains (JINTEKS), vol. 6, no. 1, 2024.

[14] Y. Ramadhana and M. Ihsan Jambak, “The Influence of Optimization of the k-Means Algorithm with Genetic Algorithm on the Results of High Dimension Data Clustering,” Indonesian Journal of Computer Science Attribution, vol. 13, no. 1, p. 302, 2024.

[15] S. García, S. Ramírez-Gallego, J. Luengo, J. M. Benítez, and F. Herrera, “Big data preprocessing: methods and prospects,” Big Data Anal, vol. 1, no. 1, Dec. 2016, doi: 10.1186/s41044-016-0014-0.

[16] K. Maharana, S. Mondal, and B. Nemade, “A review: Data pre-processing and data augmentation techniques,” Global Transitions Proceedings, vol. 3, no. 1, pp. 91–99, Jun. 2022, doi: 10.1016/j.gltp.2022.04.020.

[17] S. P. Kandel, Z. Asgar, W. Zheng, and P. J. Vander Broek, “Standardizing values of a dataset,” US 10,824,606 B1, Nov. 03, 2020 Accessed: Dec. 17, 2024. [Online]. Available: https://patentimages.storage.googleapis.com/3c/fc/fd/3469d295ce2e73/US10824606.pdf

[18] M. S. Gal and D. L. Rubinfeld, “Data standardization,” New York University Law Review, vol. 94, no. 4, pp. 737–770, Oct. 2019, doi: 10.2139/ssrn.3326377.

[19] S. Roy, P. Sharma, K. Nath, D. K. Bhattacharyya, and J. K. Kalita, “Pre-processing: A data preparation step,” in Encyclopedia of Bioinformatics and Computational Biology: ABC of Bioinformatics, vol. 1–3, Elsevier, 2018, pp. 463–471. doi: 10.1016/B978-0-12-809633-8.20457-3.

[20] A. S. Sukamto, W. Setiawan, and E. E. Pratama, “JEPIN (Jurnal Edukasi dan Penelitian Informatika) Data Mining untuk Pengelompokan Saham pada Sektor Energi dengan Metode K-Means,” JEPIN (Jurnal Edukasi dan Penelitian Informatika), Apr. 2023.

[21] A. A. Arrosyad, A. I. Purnamasari, and I. Ali, “IMPLEMENTASI ALGORITMA K-MEANS CLUSTERING UNTUK ANALISIS PERSEBARAN UMKM DI JAWA BARAT,” JATI (Jurnal Mahasiswa Teknik Informatika), vol. 8, no. 3, 2024.

[22] R. Li and L. A. Kazakovtsev, “COMPARATIVE STUDY OF MUTATION OPERATORS IN THE GENETIC ALGORITHMS FOR THE K-MEANS PROBLEM,” Facta Universitatis, Series: Mathematics and Informatics, p. 1091, Feb. 2020, doi: 10.22190/fumi2004091l.

[23] Y. Fang and J. Li, “A review of tournament selection in genetic programming,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2010, pp. 181–192. doi: 10.1007/978-3-642-16493-4_19.

[24] S. Prayudani, A. Hizriadi, E. B. Nababan, and S. Suwilo, “Analysis Effect of Tournament Selection on Genetic Algorithm Performance in Traveling Salesman Problem (TSP),” in Journal of Physics: Conference Series, Institute of Physics Publishing, Jul. 2020. doi: 10.1088/1742-6596/1566/1/012131.

[25] O. Bell, “Applications of Gaussian Mutation for Self Adaptation in Evolutionary Genetic Algorithms,” Journal of Machine Learning in Fundamental Sciences, Jan. 2022, [Online]. Available: http://arxiv.org/abs/2201.00285

[26] I. Firman Ashari, R. Banjarnahor, D. R. Farida, S. P. Aisyah, A. P. Dewi, and N. Humaya, “Application of Data Mining with the K-Means Clustering Method and Davies Bouldin Index for Grouping IMDB Movies,” Journal of Applied Informatics and Computing (JAIC), vol. 6, no. 1, pp. 2548–6861, 2022, [Online]. Available: http://jurnal.polibatam.ac.id/index.php/JAIC