Optimasi Clustering K-Means dengan Algoritma Genetika Multiobyektif

Abstract

Clustering (pengelompokkan) merupakan suatu teknik yang membagi kumpulan obyek kedalam beberapa kelompok berdasarkan kemiripan sifat. Kualitas pengelompokkan yang bagus mempunyai sifat memiliki tingkat kemiripan yang tinggi dalam suatu cluster dan memiliki tingkat kemiripan yang rendah antar cluster. K-Means merupakan salah satu teknik clustering partisioning dan tiap-tiap kelompok direpresentasikan dengan nilai rata-ratanya. Kelemahan K-Means diantaranya sulit mencapai optimum global, karena sangat tergantung dengan pemilihan awal titik pusat. Pada proses iterasinya, K-Means tidak selalu menghasilkan nilai varian dalam cluster yang minimum dan varian antar cluster yang maksimum, sehingga kualitas cluster yang dihasilkan kurang bagus. Kelemahan lain jumlah cluster yang tidak diketahui oleh pengguna yang dan belum ada metode yang efisien dan bersifat universal dalam pemilihan jumlah kelompok tersebut. K-Means sensitif terhadap outlier. Pada proses perhitungan, semua obyek dimasukkan termasuk yang outlier, sehingga mempengaruhi bentuk cluster yang dihasilkan. Keterbatasan lain adalah K-Means hanya bekerja pada atribut numerik, dan tidak bisa untuk variabel kategori. Untuk meningkatkan kinerja clustering K-Means, salah satu metode yang bisa digunakan adalah algoritma genetika. Algoritma ini berbasis teori evolusi dan biologi, yang dapat melakukan pencaharian dalam ukuran besar dan non linier. Untuk mencapai kondisi konvergen digunakan operator genetik yaitu persilangan, mutasi dan elitism yang dievolusikan dalam fungsi fitness. Penelitian ini melakukan perbandingan K-Means dan K-Means algoritma genetika multiobyektif, dengan 2 fungsi tujuan yaitu meminimumkan varian dalam cluster dan memaksimalkan varian antar cluster. Perbandingan dilakukan pada data iris dan data wine dari UCI Machine Learning. Metode algoritma genetika multiobyektif yang digunakan non dominasi sorting dengan pendekatan pareto rangking. Fungsi fitness berdasarkan pareto rangking adalah dummy fitness sesuai dengan nilai rangking. Penyelesaian dari pareto rangking berupa pasangan koordinat nilai varian dalam cluster dan varian antar cluster yang terbagi menjadi front sesuai rangking. Penyelesaian berada pada front pertama yang memiliki nilai rangking satu, berupa himpunan pasangan nilai yang saling tidak mendominasi antar solusi. Evaluasi kuantitatif hasil clustering bisa dengan beberapa pendekatan antara lain Hubert Statistic, Indeks Dun dan Indeks Davies Bouldin. Pendekatan Indeks Davies Bouldin bertujuan untuk memaksimalkan jarak antar cluster dan pada waktu yang sama mencoba untuk meminimalkan jarak antar cluster. Pada penelitian ini untuk mencari penyelesaian optimum menggunakan kriteria indeks validitas Davies Bouldin serta kesesuaian jumlah cluster yang dihasilkan. ..dst