Pendekatan Initial Centroid Search Untuk Meningkatkan Efisiensi Iterasi Klustering K-Means

Muhammad Zulfahmi Nasution; Muhammad Siddik Hasibuan

doi:10.33633/tc.v19i4.3875

Pendekatan Initial Centroid Search Untuk Meningkatkan Efisiensi Iterasi Klustering K-Means

Muhammad Zulfahmi Nasution, Muhammad Siddik Hasibuan

Abstract

Pengelompokan K-Means bertujuan untuk mengumpulkan satu set titik pusat cluster yang optimal melalui iterasi yang berurutan. Fakta bahwa semakin optimal posisi dari titik pusat awal maka semakin sedikit jumlah iterasi dari algoritma pengelompokkan K-Means untuk konvergen. Oleh karena itu, Salah satu cara untuk menemukan set initial centroid adalah melalui metode iteratif guna mencari sejumlah initial centroid yang lebih baik untuk proses pengelompokan K-Means. Langkah awal yang kami lakukan adalah mengambil sampel data dari set data dan menjalankan algoritma K-Means sebagai proses awal untuk inisialisasi centroid cluster. Kemudian kami mengulang proses iterasi dengan sejumlah initial centroid yang telah diinisialisasikan sebelumnya dan mengukur hasil pengelompokkan melalui sum-of-square-error guna menentukan kebaikan keanggotaan cluster. Centroid akhir yang memberikan jarak terendah yang akan kami teruskan ke proses pengelompokan K-means secara lengkap. Harapan kami adalah pendekatan ini akan mengarah pada set initial centroid yang lebih baik sebagai proses pengelompokan K-Means sehingga mampu meningkatkan kinerja Algoritma K-Means karena hasil konvergensi Algoritma K-Means akan berbanding lurus dengan pemilihan initial centroid.

Keywords

Titik Pusat Cluster, Pengelompokkan, Sum of Square Error, Konvergen, K-Means

Full Text:

PDF

References

J. Ortiz-Bejar, E. S. Tellez, M. Graff, J. Ortiz-Bejar, J. C. Jacobo, and A. Zamora-Mendez, “Performance analysis of k-means seeding algorithms,” in 2019 IEEE International Autumn Meeting on Power, Electronics and Computing, ROPEC 2019, 2019, doi: 10.1109/ROPEC48299.2019.9057044.

C. Xiong, Z. Hua, K. Lv, and X. Li, “An improved K-means text clustering algorithm by optimizing initial cluster centers,” in Proceedings - 2016 7th International Conference on Cloud Computing and Big Data, CCBD 2016, 2017, doi: 10.1109/CCBD.2016.059.

Y. Chen, P. Hu, and W. Wang, “Improved K-Means Algorithm and its Implementation Based on Mean Shift,” in Proceedings - 2018 11th International Congress on Image and Signal Processing, BioMedical Engineering and Informatics, CISP-BMEI 2018, 2019, doi: 10.1109/CISP-BMEI.2018.8633100.

V. Divya and K. N. Devi, “An Efficient Approach to Determine Number of Clusters Using Principal Component Analysis,” in Proceedings of the 2018 International Conference on Current Trends towards Converging Technologies, ICCTCT 2018, 2018, doi: 10.1109/ICCTCT.2018.8551182.

A. Ilham, D. Ibrahim, L. Assaffat, and A. Solichan, “Tackling Initial Centroid of K-Means with Distance Part (DP-KMeans),” in Proceeding - 2018 International Symposium on Advanced Intelligent Informatics: Revolutionize Intelligent Informatics Spectrum for Humanity, SAIN 2018, 2019, doi: 10.1109/SAIN.2018.8673364.

P. Fränti and S. Sieranoja, “How much can k-means be improved by using better initialization and repeats?,” Pattern Recognit., 2019, doi: 10.1016/j.patcog.2019.04.014.

D. Tanir and F. Nuriyeva, “On selecting the initial cluster centers in the K-means algorithm,” in 11th IEEE International Conference on Application of Information and Communication Technologies, AICT 2017 - Proceedings, 2019, doi: 10.1109/ICAICT.2017.8687081.

J. James Manoharan and S. Hari Ganesh, “Initialization of optimized K-means centroids using divide-and-conquer method,” ARPN J. Eng. Appl. Sci., 2016.

C. M. Poteras, M. C. Mihaescu, and M. Mocanu, “An optimized version of the K-Means clustering algorithm,” in 2014 Federated Conference on Computer Science and Information Systems, FedCSIS 2014, 2014, doi: 10.15439/2014F258.

G. Shi, B. Gao, and L. Zhang, “The optimized K-means algorithms for improving randomly-initialed midpoints,” in Proceedings of 2013 2nd International Conference on Measurement, Information and Control, ICMIC 2013, 2013, doi: 10.1109/MIC.2013.6758177.

M. Goyal and S. Kumar, “Improving the Initial Centroids of k-means Clustering Algorithm to Generalize its Applicability,” J. Inst. Eng. Ser. B, 2014, doi: 10.1007/s40031-014-0106-z.

H. Singh and K. Kaur, “New Method for Finding Initial Cluster Centroids in K-means Algorithm,” Int. J. Comput. Appl., 2013, doi: 10.5120/12890-9837.

Y. Li, J. Cai, H. Yang, J. Zhang, and X. Zhao, “A Novel Algorithm for Initial Cluster Center Selection,” IEEE Access, 2019, doi: 10.1109/ACCESS.2019.2921320.

DOI: https://doi.org/10.33633/tc.v19i4.3875