K-MEANS

1.1  K-Means

       Dalam statistik dan mesin pembelajaran, pengelompokan K-Means merupakan metode analisis kelompok yang mengarah pada pemartisian N objek pengamatan ke dalam K kelompok (cluster) dimana setiap objeck pengamatan dimiliki oleh sebuah kelompok dengan mean (rata-rata) terdekat, mirip dengan algoritma Expectation-Maximization untuk Gaussian Mixture dimana keduanya mencoba untuk menemukan pusat dari kelompok dalam data sebanyak iterasi perbaikan yang dilakukan oleh kedua algoritma. K-Means merupakan salah satu metode pengelompokan dan nonhierarki (sekatan) yang berusaha mempartisi data yang ada ke dalam bentuk dua atau lebih kelompok. Metode ini mempartisi data kedalam kelompok sehingga data berkarakteristik sama dimasukan kedalam satu kelompok yang sama dan data yang berkarakteristik berbeda dikelompokan ke dalam kelompok yang lain. Adapun tujuan pengelompokan data ini adalah untuk meminimalkan fungsi objektif dalam suatu kelompok dan memaksimalkan variasi antar kelompok.

2.1.1      Metode K-Means

Dari beberapa teknik yang paling sederhana dan umum dikenal adalah clustering k-means. Dalam teknik ini, objek-objek dikelompokan ke dalam K kelompok atau cluster. Untuk melakukan clustering ini, nilai k harus ditentukan terlebih dahulu. Biasanya user atau pemakai sudah mempunyai informasi awal tentang objek yang sedang dipelajari, termasuk berapa jumlah cluster yang paling tepat.

Secara detail dapat digunakan ukuran ketidakmiripan untuk pengelompokan objek. Ketidak miripan dapat diterjemahkan dalam konsep jarak. Jika dua objek atau data titik cukup dekat, maka dua objek itu mirip. Semakin dekat semakin tinggi kemiripannya. Hasil klastering dikatakan baik jika nila interclass similiarity (kesamaan antar kelas/ WVC (withing cluster variation) tinggi dan nilai interclass similarity (kesamaan antar kelas/ BVC (between cluster variation) rendah. Nilai WVC dapat dilihat dari nilai SSE-nya sedangkan BVC dihitung dengan rumus : BVC = d(m1,m2,…,mn) dimana d adalah jarak antara centroid m.

2.1.2      Algoritma K-Means

K-means bertujuan untuk membagi objek-objek atau data data yang diberikan menjadi beberapa cluster sejumlah K cluster-cluster tersebut mempunyai suatu nilai tengah / nilai pusat yang disebut dengan centroid. Tujuan dari algoritma k-means adalah meminimalisir total dari jarak elemen-elemen antar cluster (jarak antar cluster dengan cluster lainnya). Algoritma pengelompokan data dengan k-means dapat diringkas dengan sebagai berikut :

1.     Tentukan jumlah kelompok

2.     Alokasikan data ke dalam kelompok secara acak

3.     Hitung pusat (sentroid/rata-rata) dari data yang ada di masing-masing kelompok

4.     Alokasikan masing-masing data ke sentroid/rata-rata terdekat

5.     Kembali kelangkah 3, apabila masih ada data yang berpindah kelompok, atau apabila ada perubahan nilai sentroid diatas nilai ambang yang ditentukan, atau apabila perubahan nilai pada fungsi objektif yang digunakan masih diatas nilai ambang yang ditentukan.

Pada langkah ke 3, lokasi sentroid (titik pusat) setiap kelompok yang di ambil dari rata-rata (mean) semua nilai data pada setiap fiturnya harus dihitung kembali. Jika M menyatakan jumlah data dalam sebuah kelompok, i menyatakan fitur ke-I dalam sebuah kelompok dan p menyatakan dimensi data, untuk menghitung sentroid fitur ke-I digunakan formula :

C_I =

Formula tersebut dilakukan sebanyak p dimensi sehingga I mulai dari 1 sampai p.

Ada beberapa cara yang dapat digunakan untuk mengukur  jarak data ke pusat kelompok, di antaranya Euclidean (Bezdek, 1981), Manhattan/City Block (Miyamoto dan Agusta, 1995) dan Minkowsky (Miyamoto dan Agusta, 1995). Masing-masing cara mempunyai kelebihan dan kekurangan.

Pengukuran jarak pada ruang jarak (distance space) Euclidean menggunakan formula

D(x­₂ , x₁) = || x₂ – x₁ ||₂ = _2j – x_1j |­²

D adalah jarak antara data x₂ dan x­­₁, dan | . | adalah nilai mutlak. Pengukuran jarak pada ruang jarak manhattan menggunakan formula

D(x­₂ , x₁) = || x₂ – x₁ ||₁ = _2j – x_1j |­

Pengukuran jarak pada ruang jarak Minkowsky menggunakan formula

D(x­₂ , x₁) = || x₂ – x₁ |  = _2j – x_1j

λ adalah parameter Minkowsky. Secara umum, λ merupakan parameter penentu dalam karakteristik jarak. Jika λ = 1, ruang jarak pada Minkowsky sama dengan manhattan. Jika λ = 2, ruang jaraknya akan sama dengan Euclidean. Jika λ = ∞, ruang jaraknya akan sama dengan ruang jarak Chebyshev. Namun demikian, cara yang paling banyak digunakan adalah Euclidean dan Manhattan. Euclidean menjadi pilihan jika kita ingin member jarak terpendek antara dua titik (jarak lurus). Sedangkan manhattan memberikan jarak terjauh pada dua data. Manhattan juga sering digunakan karena kemampuannya dalam mendeteksi keadaan khusus, seperti keberadaan outlier, dengan lebih baik (Agusta, 2005).

Pada langkah ke 4, pengalokasian kembali data ke dalam masing-masing kelompok dalam metode k-means didasarkan pada perbandingan jarak antara data dengan sentroid setiap kelompok yang ada. Data di alokasikan ulang secara tegas ke kelompok yang mempunyai sentroid dengan jarak terdekat dari data tersebut. Data dialokasikan ulang secara tegas ke kelompok yang mempunyai sentroid dengan jarak terdekat dari data tersebut. Pengalokasian ini dapat dirumuskan sebagai berikut (MacQueen, 1967):

a­­_il adalah nilai keanggotaan titik x_i ke pusat kelompok C_l, d adalah jarak terpendek dari data x_i­ ke K kelompok setelah dibandingkan, dan C_l adalah sentroid (pusat kelompok) ke-l.

fungsi objektif yang digunakan untuk K-means ditentukan berdasarkan jarak dan nilai keanggotaan data dalam kelompok, fungsi objektif yang digunakan adalah sebagai berikut. (MacQueen, 1957):

N adalah jumlah data, K adalah jumlah kelompok, a_il adalah nilai keanggotaan titik data x_i ke pusat data kelompok C_l, C_l adalah pusat kelompok ke-l, dan D(x_i,C_l) adalah jarak titik x_i ke kelompok C_l yang diikuti, a mempunyai nilai 0 atau 1. Apabila suatu data merupakan anggota suatu kelompok, nilai a_il = 1, jika tidak nilai a­_il­ = 0.