Pembahasan Data Mining (Chapter 4)

Algoritma K-Means Clustering

Karakteristik K-Means

K-Means sangat cepat dalam proses clustering
K-Means sangat sensitif pada pembangkitan centroid awal secara random
Memungkinkan suatu cluster tidak mempunyai anggota
Hasil clustering dengan K-Means bersifat tidak unik (selalu berubah-ubah) – terkadang baik, terkadang jelek
K-means sangat sulit untuk mencapai global optimum

Memperhatikan input dalam algoritma K-Means, dapat dikatakan bahwa algoritma ini hanya mengolah data kuantitatif atau numerik.
Sebuah basis data tidak mungkin hanya berisi satu macam tipe data saja, akan tetapi beragam tipe.
Sebuah basis data dapat berisi data-data dengan tipe sebagai berikut: binary, nominal, ordinal, interval dan ratio.
Berbagai macam atribut dalam basis data yang berbeda tipe disebut sebagai data multivariate.
Tipe data seperti nominal dan ordinal harus diolah terlebih dahulu menjadi data numerik (bisa dilakukan dengan cara diskritisasi), sehingga dapat diberlakukan algoritma K-Means dalam pembentukan clusternya.

Contoh Kasus Perhitungan K-Means Clustering

Ditentukan banyaknya cluster yang dibentuk dua (k=2). Banyaknya cluster harus lebih kecil dari pada banyaknya data (k<n).

Contoh Dataset K-means

Inisialisasi centroid dataset pada tabel dataset diatas adalah C1 = {1 , 1} dan C2 = {2 , 1}. Inisialiasasi centroid dapat ditentukan secara manual ataupun random.

Untuk pengulangan berikutnya (pengulangan ke-1 sampai selesai), centroid baru dihitung dengan menghitung nilai rata-rata data pada setiap cluster. Jika centroid baru berbeda dengan centroid sebelumnya, maka proses dilanjutkan ke langkah berikutnya. Namun jika centroid yang baru dihitung sama dengan centroid sebelumnya, maka proses clustering selesai.

Rumus yang digunaka untuk menghitung distance space atau jarak data dengan centroid menggunakan Euclidiean Distance.

Persamaan Euclidean Distance

Pengulangan ke-1

Jarak data dengan Centroid C1 adalah:

Pengulangan ke-1 C1 K-means

Jarak data dengan Centroid C2 adalah:

Pengulangan ke-1 C2 K-means

Untuk seterusnya, hitung jarak pada setiap baris data, dan hasilnya seperti pada tabel dibawah.

Hasil Perhitungan Pengulangan ke-1

Kelompokan data sesuai dengan cluster-nya, yaitu data yang memiliki jarak terpendek. Contoh; karena d(x1,c1) < d(x1,c2) maka x1 masuk ke dalam cluster 1. Pada tabel diatas, data n=1 masuk ke dalam cluster 1 karena dc1 < dc2, sedangkan n=2,3,4 masuk ke dalam cluster 2 karena dc2 < dc1.

Pengelompokan Data pada Pengulangan ke-1

Setelah mendapatkan label cluster untuk masing-masing data n=1,2,3,4 maka dicari nilai rata-ratanya dengan menjumlahkan seluruh anggota masing-masing cluster dan dibagi jumlah anggotanya.