Model 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 Kasus:
Misalkan seorang data analis ingin membuat cluster kepadatan penduduk tinggi dan rendah pada sebuah propinsi dengan mengambil sampel dari 10 kota, didapatkan data kepadatan penduduk dalam ribuan per km persegi sbb:


Kota
 Kepadatan
A 636
B 473
C 487
D 576
E 788
F 639
G 777
H 244
I 511
J 468

Iterasi ke-1


Langkah (1) Tentukan k. Untuk soal di atas jumlah pengelompokan adalah 2 sehingga k=2.

Langkah (2) Hitung Centroid: dipilih 2 centroid secara acak yaitu kota H (244) dan Kota G(777). 

Langkah (3) Hitung Jarak setiap centroid: Tabel berikut menunjukkan J1 adalah jarak masing-masing kota dengan centroid 1, dan J2 adalah jarak masing-masing kota dengan centroid kedua.

Kota
Kepadatan
J1
J2
Iterasi 1
A
636
392
141
C2
B
473
229
304
C1
C
487
243
290
C1
D
576
332
201
C2
E
788
544
11
C2
F
639
395
138
C2
G
777
533
0
C2
H
244
0
533
C1
I
511
267
266
C2
J
468
224
309
C1

Langkah (4) kolom iterasi1 menunjukkan proses clusterisasi: Karena jarak kota A ke centroid 2 lebih kecil daripada jarak ke centroid 1, maka kota A masuk ke cluster 2 (C2). Kota B masuk ke cluster 1 (C1). Demikian seterusnya sampai selesai menghitung kota J. Sehingga cluster C1={B,C,H,I} dan cluster C2={A,D,E,F,G,J}.

Langkah (5) Hitung banyaknya perubahan: Pada iterasi 1 ini sepuluh kota berubah clusternya sehingga perlu dirasakan untuk menambah iterasi lagi.


Iterasi ke-2


Langkah (2) Hitung Centroid: centroid cluster C1 adalah rata-rata (mean) dari kota B, C, H, dan I yaitu(473+487+244+468)/4=418. Sedangkan centroid cluster C2 didapatkan dengan menghtung mean kota A,D,E,F,G,J, yaitu (636+576+...+511)/6=654.5.

Kota Kepadatan Iterasi 1 Means
B 473 C1 418
C 487
H 244
J 468
A 636 C2 654.5
D 576
E 788
F 639
G 777
I 511


                                                                          
Langkah (3) Hitung Jarak setiap centroid: Tabel berikut menunjukkan J1 adalah jarak masing-masing kota dengan centroid 1 yang baru, dan J2 adalah jarak masing-masing kota dengan centroid kedua yang baru di iterasi ke-2.

Kota
Kepadatan
J1
J2
Iterasi 1
Iterasi 2
Perubahan
A
636
118
18.5
C2
C2
TIDAK
B
473
45
181.5
C1
C1
TIDAK
C
487
31
167.5
C1
C1
TIDAK
D
576
58
78.5
C2
C1
YA
E
788
270
133.5
C2
C2
TIDAK
F
639
121
15.5
C2
C2
TIDAK
G
777
259
122.5
C2
C2
TIDAK
H
244
274
410.5
C1
C1
TIDAK
I
511
7
143.5
C2
C1
YA
J
468
50
186.5
C1
C1
TIDAK
Langkah (4) kolom iterasi 2 menunjukkan clusterisasi : Karena jarak kota A ke centroid 2 lebih kecil daripada jarak ke centroid 1, maka kota A masuk ke cluster 2 (C2). Kota B masuk ke cluster 1 (C1). Demikian seterusnya sampai selesai menghitung kota J. Sehingga cluster C1={B,C,D,H,I,J} dan cluster C2={A,E,F,G}.
Langkah (5) Hitung banyaknya perubahan: Bila dibandingkan dengan iterasi pertama, maka ada dua kota yang berubah cluster yaitu kota D dan I dari cluster C2 pindah ke cluster C1. Pada iterasi 2 ini tinggal 2 kota saja yang berubah clusternya. Tapi masih perlu dirasakan untuk menambah iterasi lagi untuk memeriksa apakah perubahan bisa diturunkan lagi.

Iterasi ke-3

Langkah (2) Hitung Centroid: centroid cluster C1 centroid adalah rata-rata (mean) dari kota B,C,D,H,I, dan J yaitu (473+487+…+468)/6=459.83. Centrod cluster C2 didapatkan dengan menghtung mean kota A,E,F,G, yaitu (636+788+639+777)/4=710.
KotaKepadatanIterasi 2Means
B473C1    459.83
C487
D576
H244
I511
J468
A636C2710
E788
F639
G777
Langkah (3) Hitung Jarak setiap centroid: Tabel berikut menunjukkan J1 adalah jarak masing-masing kota dengan centroid 1 yang baru, dan J2 adalah jarak masing-masing kota dengan centroid kedua yang baru di iterasi ke-3.
Kota
Kepadatan
J1
J2
Iterasi 2
Iterasi 3
Perubahan
A
636
176.17
74
C2
C2
TIDAK
B
473
13.17
237
C1
C1
TIDAK
C
487
27.17
223
C1
C1
TIDAK
D
576
116.17
134
C1
C1
TIDAK
E
788
328.17
78
C2
C2
TIDAK
F
639
179.17
71
C2
C2
TIDAK
G
777
317.17
67
C2
C2
TIDAK
H
244
215.83
466
C1
C1
TIDAK
I
511
51.17
199
C1
C1
TIDAK
J
468
8.17
242
C1
C1
TIDAK
Langkah (4) kolom iterasi3 menunjukkan proses clusterisasi : Karena jarak kota A ke centroid 2 lebih kecil daripada jarak ke centroid 1, maka kota A masuk ke cluster 2 (C2). Kota B masuk ke cluster 1 (C1). Demikian seterusnya sampai selesai menghitung kota J. Sehingga cluster C1={B,C,D,H,I,J} dan cluster C2={A,E,F,G}.
Langkah (5) hitung banyaknya perubahan: Bila dibandingkan antara iterasi kedua dan ketiga, maka sudah tidak ada perubahan cluster. Sehingga proses K-mean selesai sampai iterasi ke-3 saja.
Kesimpulan dari kota-kota A, B, C, … J yang termasuk kota dengan kepadatan penduduk tinggi (cluster C2) yaitu A, E, F dan G, sedangkan kota-kota B,C,D,H,I, dan J termasuk kota dengan kepadatan rendah (Cluster C1)

Daftar Pustaka


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


4 comments: