Algoritma K-Means Clustering dan Contoh Perhitungan Untuk Data Numerik 2 Dimensi (bag. 1)

Table of Contents

Algoritma pengelompokan (clustering) semacam K-Means dikenal sebagai algoritma pembelajaran tidak terbimbing (unsupervised learning) karena tidak adanya target kelas untuk setiap data. Algoritma K-Means menjadi salah satu algoritma yang peling penting dalam bidang data mining. Memiliki kelebihan sebagai algoritma yang mudah diimplementasikan, relatif cepat ditinjau dari waktu komputasi dan telah digunakan secara luas untuk menyelesaikan berbagai persoalan komputasi. 

Penting untuk diketahui bahwa, K yang dimaksudkan dalam K-Means adalah jumlah partisi, sehingga algoritma ini mengelompokkan setiap titik pada data X dalam salah satu partisi K. Semakin besar nilai K berdampak pada banyaknya cluster untuk mengelompokkan data X. Nilai K ini juga menjadi parameter yang dibutuhkan oleh algoritma K-Means. Tidak ada ketetapan mutlak bagaimana menentukan nilai K yang optimal. Biasanya, penentuan nilai K didasarkan atas informasi yang diketahui sebelumnya tentang seberapa banyak cluster data yang muncul pada data X.  Cara lain yang paling naif dalam menentukan nilai K adalah melakukan percobaan dengan beberapa nilai K hingga ditemukan bentuk pengelompokan yang tepat. Namun dewasa ini, banyak peneliti telah mencoba untuk melakukan pencarian nilai K yang optimum pada K-Means menggunakan berbagai pendekatan meta-heuristik seperti particle swarm optimization (pso), ant colony optimization (aco) dan lain sebagainya. 

Gambar 1 Contoh pengelompokan  menjadi dua cluster

Istilah yang lazim ditemukan dalam algoritma K-Means adalah centroid. Centroid dapat diartikan sebagai titik pusat cluster, banyaknya centroid juga bergantung dari banyaknya nilai K yang diberikan. Gambar 1 menunjukkan terdapat data set yang dilakukan pengelompokan menjadi dua cluster. Maka, untuk mendapatkan dua cluster, nilai K yang diberikan adalah 2. Kemudian, dua cluster tersebut harus memiliki centroid sebagai titik pusat cluster. Penentuan centroid ini dapat dilakukan secara random atau mengambil beberapa titik data sebagai centroid. Data akan terkelompok berdasarkan centroid terdekat, sehingga terbentuklah suatu pengelompokan data sesuai jumlah K yang diberikan. 

Secara garis besar, algoritma K-Means Clustering dijelaskan dalam 5 tahap berikut :

1. Inisialisasi, tentukan nilai K sebagai jumlah cluster. Jika perlu tetapkan ambang batas perubahan fungsi objektif (batas yang menentukan iterasi berhenti atau tidak) dan ambang batas perubahan posisi centroid. 
2. Pilih K data dari data set X sebagai centroid.
3. Alokasikan semua data ke centroid terdekat dengan menghitung metrik jarak.
4. Hitung kembali centroid C berdasarkan data yang mengikuti cluster masing-masing.
5. Ulangi langkah 3 dan 4 hingga kondisi konvergen tercapai, yaitu (a) perubahan fungsi objektif sudah di bawah ambang batas atau (b) tidak ada data yang berpindah cluster atau (c) perubahan posisi centroid sudah berada di bawah ambang batas. 

Kali ini saya tidak berpanjang lebar menjelaskan mengenai rumus matematika dari algoritma K-Means, teman-teman bisa mencari sendiri diberbagai paper atau referensi lain. Saya lebih suka menjelaskan langsung contoh perhitungan manualnya, karena sepanjang pengalaman saya belajar algoritma, materi lebih mudah dimengerti jika langsung diimplementasikan ke studi kasus dan dijelaskan pula tahap-tahap perhitungan manualnya.

Pada contoh ini, disediakan data sampel berupa 10 data sebagaimana yang terpampang pada gambar 2. Data tersebut memiliki dua dimensi (fitur x dan fitur y) agar mudah di visualisasikan dalam koordinat kartesius.

Gambar 2 Set data sintetik numerik 2 dimensi

Berdasarkan data set tersebut, dilakukan proses pengelompokan menjadi 3 cluster (k = 3). berdasarkan k=3, maka ditentukan titik centroid sebanyak k berdasarkan titik-titik tertentu data set. Dapat dilakukan secara random ataupun langsung ditentukan. Maka dipilih data ke-2, 4 dan 6 sebagai centroid awal. Pengukuran jarak pada setiap data terhadap titik centroid dilakukan menggunakan perhitungan jarak Euclidean.

Gambar 3 Penentuan centroid

Setelah nilai K dan centroid terinisialisasi, maka perlu ditentukan pula nilai fungsi objektif sebagai ambang batas iterasi yaitu sebesar 0.1. Sebagai permulaan, misalnya ditentukan nilai fungsi objektif sebesar 1000. Jadi jika pada iterasi tertentu nilai fungsi objektif didapatkan sudah berada di bawah ambang batas 0.1, maka iterasi akan berhenti. 

Tahap berikutnya adalah melakukan iterasi untuk memperoleh pembaharuan titik centroid serta mendapatkan perubahan nilai fungsi objektif. Sepanjang nilai fungsi objektif masih berada di atas ambang batas yang ditetapkan, maka proses iterasi akan tetap beranjut. 

Tahap iterasi saya jelaskan di bagian 2.

Referensi :

1. Prasetyo, Eko. 2014. Data Mining : Mengolah Data Menjadi Informasi Menggunakan Matlab. Yogyakarta : Andi.