illustrated K-means


K-means adalah model data dimana data-data dikelompokkan ke dalam beberapa cluster. Masing-masing cluster memiliki satu centroid, yaitu titik tengah cluster yang dihitung dari jarak eucledian rata-rata masing-masing data yang ada dalam cluster tsb. Menurut Tan (2006) clustering merupakan sebuah proses untuk mengelompokan data ke dalam beberapa cluster sehingga data dalam satu cluster memiliki tingkat kemiripan yang maksimum dan data antar cluster memiliki kemiripan yang minimum.

Jarak Euclidean

Jarak Euclidean adalah perhitungan jarak dari 2 buah titik atau lebih dalam Euclidean space. Euclidean space diperkenalkan oleh Euclid, seorang matematikawan dari Yunani sekitar tahun 300 Sebelum Masehi.

Jarak Euclidean Pada 1 dimensi

Rumus jarak dalam 1 dimensi
rumus1dimensi
Misalkan kita ingin menghitung jarak Euclidean 1 dimensi. Titik pertama adalah 10, titik kedua adalah 30. Caranya adalah kurangkan 30 dengan 10 sehingga menghasilkan 20. Hitung nilai kuadratnya sehingga kita mendapat nilai 400. Kemudian diakarkan sehingga mendapatkan nilai 20. Sehingga jarak euclidean dari 2 titik tersebut adalah 20.


Jarak Euclidean Pada 2 dimensi

Koordinat Jarak
Caranya hampir sama. Misalkan titik pertama mempunyai kordinat (1,2). Titik kedua ada di kordinat (5,5). Caranya adalah kurangkan setiap kordinat titik kedua dengan titik yang pertama. Yaitu, (5-1,5-2) sehingga menjadi (4,3). Kemudian pangkatkan masing-masing sehingga memperoleh (16,9). Kemudian tambahkan semuanya sehingga memperoleh nilai 16+9 = 25. Hasil ini kemudian diakarkan menjadi 5. Sehingga jarak euclideannya adalah 5

Rumus jarak Eucledian untuk dua dimensi antara P(x1,y1) dan Q(x2,y2) adalah:
Euclide heorem


Step by step K-Means

gambarkMeans
Gambar 1 Step by step K means

Contoh Soal:

  • Misalkan kita memiliki 10 data A,B,C,...J seperti tergambar berikut ini:
Gambar 2 plot posisi data

  • STEP 1: Tentukan berapa klaster yang akan dibentuk atau tentukan nilai k. Misalkan kita tentukan saja ada 3 klaster yang akan kita buat. Jadi k=3. 
  • Sampai dengan step 1 ini semua klaster masih kosong atau  C1={}, C2={}, C3={}.

ITERASI 1

  • STEP 2; Tentukan satu wakil data dari setiap klaster secara acak. Wakil  data ini disebut dengan centroid karena letaknya di tengah klaster. Karena klaster ada 3, maka centroid yang kita buat harus tiga juga. Misalkan titik C, G, I.
    Catatan: Titik centroid awal tidak harus merupakan data, boleh juga sembarang titik secara acak. 
Gambar 3 Tiga titik centroid awal


  • STEP 3; Untuk masing-masing anggota, Tentukan centroid mana yang paling dekat dengannya. Masing-masing titik dihitung jarak Euclediannya ke tiap-tiap centroid, dan kemudian kita pilih centroid dengan jarak terdekat.
Gambar 4 Menghitung centroid terdekat pada iterasi 1

  • STEP 4: Buat ketiga klaster 
Gambar 4 Membuat klaster pada iterasi 1

  • STEP 5: Pada iterasi 1, semua klaster mengalamibanyak perubahan. C1 dari kosong menjadi {A,B,C,D,E,H} C2 menjadi {F,G} dan C3 menjadi {I,J}. Sehingga perlu dilakukan iterasi lagi.

ITERASI 2:

  • STEP 2: Sekarang hitung ulang titik-titik centroid masing-masing klaster.
Gambar 5 Menghitung ulang centroid untuk iterasi 2

  • STEP 3: Kalau sudah, untuk setiap anggota, tentukan titik centroid terdekat dengannya.
Gambar 6 Menghitung centroid terdekat di iterasi 2

  • STEP 4: Buat lagi tiga klaster hasil iterasi 2
Gambar 7 Klaster hasil iterasi 2

  • STEP 5: Bila kia bandingkan gambar 4 dan gambar 7, semua klaster masih berubah. C1 kehilangan dua anggota enjadi {A,B,C,D}, C2 bertambah 1 anggota menjadi {E,F,G}, dan C3 bertambah 1 anggota menjadi {H,I,J}. Sehingga masih perlu diperiksa di iterasi berikutnya.

ITERASI 3:

  • STEP 2: Hitung ulang titik centroid
Gambar 8 Hitung 3 centroid di iterasi 3

  • STEP 3: Untuk setiap anggota tentukan lagi titik centroid terdekat.
Gambar 9 Hitung titik centroid terdekat

  • STEP 4: Buat lagi ketiga klaster.
Gambar 10 Hasil klaster di iterasi 3

  • STEP 5: Bila dibandingkan gambar 7 dan gambar 10 perubahan klaster sudah tidak ada sehingga iterasi tidak perlu kita dilanjutkan.
Gambar 11 Hasil Kmeans Clustering

KESIMPULAN

  • Jadi, hasil proses klasterisasi terlihat pada gambar 11. Kesimpulan Data-data dapat dibagi menjadi 3 klaster yaitu {A, B, C, D},{E, F, G}, {H, I, J}.

Daftar Pustaka

Tan, P.N., Steinbach, M., Kumar, V. (2006) Introduction to Data Mining. Boston:Pearson Education.



2 comments: