Penentuan Centroid Awal Pada Algoritma   K-Means Dengan Dynamic Artificial Chromosomes Genetic Algorithm Untuk Tuberculosis Dataset

Mursalim Mursalim; Purwanto Purwanto; M Arief Soeleman

doi:10.33633/tc.v20i1.4230

Penentuan Centroid Awal Pada Algoritma K-Means Dengan Dynamic Artificial Chromosomes Genetic Algorithm Untuk Tuberculosis Dataset

Mursalim Mursalim, Purwanto Purwanto, M Arief Soeleman

Abstract

Data merupakan hal penting diera sekarang begitu juga dengan metode data mining yang dapat mengekstraksi data menghasilkan informasi. Klastering 1 dari 5 peran data mining yang berfungsi untuk mengelompokkan data berdasarkan tingkat kemiripan dan jarak minimum. Algoritma K-Means termasuk algoritma yang populer banyak digunakan diberbagai bidang seperti bidang pendidikan, kesehatan, sosial, biologi, ilmu komputer. Seringkali metode K-Means dikombinasikan dengan metode optimasi seperti algoritma genetika untuk mengatasi permasalah pada K-Means yaitu sensitif dalam penentuan centroid awal .Namun metode algoritma genetika memiliki kekurangan yaitu mengalamai konvergen prematur sehingga hasil dari algorima genetika terjebak pada optimum lokal. Penelitian ini mengkombinasikan dynamic artificial cromosomes genetic algorithm dengan K-Means dalam menentukan nilai centroid awal pada k-means. Hasil eksperimen menunjukkan bahwa metode DAC GA + K-Means lebih unggul dibandingkan dengan K-Means dan GA + K-Means pada 2 dataset yang diuji dengan optimal nilai klaster sebanyak 2 dan 1 dataset sebanyak 3 klaster. Metode tersebut perolehan nilai DBI sebesar 0.138, 0.279 serta 0.382, nilai Sum Square Error sebesar 92.56, 332,39 dan 1280.68 serta nilai fitness yang tebentuk adalah 7.12, 3.57 dan 2.13.

Keywords

Data mining; initial centroid; k-means; Sum Square Error; fitness; Davies Bouldin Index; GA; DAC-GA; Tuberculosis

Full Text:

PDF

References

P. Bhatia, “Introduction to Data Mining,” Data Min. Data Warehous., pp. 17–27, 2019, doi: 10.1017/9781108635592.003.

Y. Fu, Data mining, vol. 16, no. 4. 1997.

S. Agarwal, Data mining: Data mining concepts and techniques. 2014.

J. Nayak, B. Naik, and H. S. Behera, “Computational Intelligence in Data Mining,” vol. 711, 2019, doi: 10.1007/978-981-10-8055-5.

J. Yadav and M. Sharma, “A Review of K-mean Algorithm,” Int. J. Eng. Trends Technol., vol. 4, no. 7, pp. 2972–2976, 2013.

L. E. Agustín-Blas, S. Salcedo-Sanz, S. Jiménez-Fernández, L. Carro-Calvo, J. Del Ser, and J. A. Portilla-Figueras, “A new grouping genetic algorithm for clustering problems,” Expert Syst. Appl., vol. 39, no. 10, pp. 9695–9703, 2012, doi: 10.1016/j.eswa.2012.02.149.

P. A. Ariawan, “Optimasi Pengelompokan Data Pada Metode K-means dengan Analisis Outlier,” J. Nas. Teknol. dan Sist. Inf., vol. 5, no. 2, pp. 88–95, 2019, doi: 10.25077/teknosi.v5i2.2019.88-95.

S. Bhatia, “New improved technique for initial cluster centers of K means clustering using Genetic Algorithm,” 2014 Int. Conf. Converg. Technol. I2CT 2014, pp. 1–4, 2014, doi: 10.1109/I2CT.2014.7092112.

M. E. Celebi, H. A. Kingravi, and P. A. Vela, “A comparative study of efficient initialization methods for the k-means clustering algorithm,” Expert Syst. Appl., vol. 40, no. 1, pp. 200–210, 2013, doi: 10.1016/j.eswa.2012.07.021.

M. Erisoglu, N. Calis, and S. Sakallioglu, “A new algorithm for initial cluster centers in k-means algorithm,” Pattern Recognit. Lett., vol. 32, no. 14, pp. 1701–1705, 2011, doi: 10.1016/j.patrec.2011.07.011.

T. P. Hong, C. H. Chen, and F. S. Lin, “Using group genetic algorithm to improve performance of attribute clustering,” Appl. Soft Comput. J., vol. 29, pp. 371–378, 2015, doi: 10.1016/j.asoc.2015.01.001.

A. C. Jinyin et al., “A Novel Cluster Center Fast Determination Clustering Algorithm,” Appl. Soft Comput. J., 2017, doi: 10.1016/j.asoc.2017.04.031.

Y. Lu, S. Lu, F. Fotouhi, Y. Deng, and S. J. Brown, “Incremental genetic K-means algorithm and its application in gene expression data analysis,” BMC Bioinformatics, vol. 5, pp. 1–10, 2004, doi: 10.1186/1471-2105-5-172.

J. Qiao and Y. Lu, “A new algorithm for choosing initial cluster centers for k-means,” no. Iccsee, pp. 527–530, 2013, doi: 10.2991/iccsee.2013.135.

D. Q. Zeebaree, H. Haron, A. M. Abdulazeez, and S. R. M. Zeebaree, “Combination of k-means clustering with genetic algorithm: A review,” Int. J. Appl. Eng. Res., vol. 12, no. 24, pp. 14238–14245, 2017.

E. Utik Wahyuningtyas, R. Regasari Mardi Putri, and Sutrisno, “Optimasi K-Means Untuk Clustering Dosen Berdasarkan Kinerja Akademik Menggunakan Algoritme Genetika Paralel,” J. Pengemb. Teknol. Inf. dan Ilmu Komput. Univ. Brawijaya, vol. 2, no. 8, pp. 2548–964, 2018, [Online]. Available: http://j-ptiik.ub.ac.id.

M. A. Rahman and M. Z. Islam, “A hybrid clustering technique combining a novel genetic algorithm with K-Means,” Knowledge-Based Syst., vol. 71, pp. 345–365, 2014, doi: 10.1016/j.knosys.2014.08.011.

M. R. Kamal, R. Satria, A. Syukur, F. I. Komputer, and U. D. Nuswantoro, “Integrasi Kromosom Buatan Dinamis untuk Memecahkan Masalah Konvergensi Prematur pada Algoritma Genetika untuk Traveling Salesman Problem,” J. Intell. Syst., vol. 1, no. 2, pp. 61–66, 2015.

W. O. Health, “Tuberculosis (TB) World Health Organization,” 2019. https://www.who.int/tb/en/ (accessed Jan. 01, 2019).

J. B. MacQueen, “Some methods for classification and analysis of multivariate observations,” in Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, 1967, pp. 281–297.

S. N. D. S.N. Sivanandam, Introduction to Genetic Algorithms. Springer-Verlag Berlin Heidelberg, 2008.

P. C. Chang, W. H. Huang, and C. J. Ting, “Dynamic diversity control in genetic algorithm for mining unsearched solution space in TSP problems,” Expert Syst. Appl., vol. 37, no. 3, pp. 1863–1878, 2010, doi: 10.1016/j.eswa.2009.07.066.

D. L. Davies and D. W. Bouldin, “A Cluster Separation Measure,” IEEE Trans. Pattern Anal. Mach. Intell., vol. PAMI-1, no. 2, pp. 224–227, 1979, doi: 10.1109/TPAMI.1979.4766909.

DOI: https://doi.org/10.33633/tc.v20i1.4230