Penerapan Algoritma Invasive Weed Optimnization untuk Penentuan Titik Pusat Klaster pada K-Means

Abstract

Abstrak

K-means merupakan salah satu algoritmaclustering yang paling populer. Salah satu alasan dari kepopuleran K-means adalah karena mudah dan sederhana ketika diimplementasikan. Namun hasil klaster dari K-means sangat sensitif terhadap pemilihan titik pusat awalnya. K-means seringkali terjebak pada solusi lokal optima. Hasil klaster yang lebih baik seringkali baru bisa didapatkan setelah dilakukan beberapa kali percobaan. Penyebab lain seringnya K-means terjebak pada solusi lokal optima adalah karena cara penentuan titik pusat baru untuk setiap iterasi dalam K-means dilakukan dengan menggunakan nilai mean dari data-data yang ada pada klaster bersangkutan. Hal tersebut menyebabkan K-means hanya akan melakukan pencarian calon titik pusat baru disekitar titik pusat awal. Untuk mengatasi permasalahan tersebut, penerapan metode yang memiliki kemampuan untuk melakukan pencarian global akan mampu membantu K-means untuk dapat menemukan titik pusat klaster yang lebih baik. Invasive Weed Optimization merupakan algoritma pencarian global yang terinspirasi oleh proses kolonisasi rumput liar. Pada penelitian ini diusulkan sebuah metode yang merupakan hasil hibridasi dari metode K-means dan algoritma Invasive Weed Optimization (IWOKM). Kinerja dari metode IWOKM telah dicobakan pada data bunga Iris kemudian hasilnya dibandingkan dengan K-means. Dari pengujian yang dilakukan, didapat hasil bahwa metode IWOKM mampu menghasilkan hasil klaster yang lebih baik dari K-means.

Kata kunci—K-means, IWO, IWOKM, analisa klaster

Abstract

K-means is one of the most popular clustering algorithm. One reason for the popularity of K-means is it is easy and simple when implemented. However, the results of K-means is very sensitive to the selection of initial centroid. The results are often better after several experiment. Another reason why K-means stuck in local optima is due to the method of determining the new center point for each iteration that is performed using the mean value of the data that exist on the cluster. This causes the algorithm will do search for the centroid candidates around the center point. To overcome this, implement a method that is able to do a global search to determine the center point on K-means may be able to assist K-means in finding better cluster center. Invasive Weed Optimization (IWO) is a global search algorithm inspired by weed colonization process. In this study proposed a method which is the result of hybridization of K-means and IWO (IWOKM). Performance of the method has been tested on flower Iris dataset. The results are then compared with the result from K-means. The result show that IWOKM able to produce better cluster center than K-means.

Keywords—K-means, IWO, IWOKM, cluster analysis