Clustering : Algoritma K-Medoids

Penambangan Data
Chapter 12

1
 K-Medoids
Metode partitional clustering* yang bertujuan untuk
menemukan satu set k-cluster diantara data yang paling
mencirikan objek dalam kumpulan suatu data.

*Data dikelompokkan ke dalam sejumlah cluster tanpa adanya suatu hirarki antara satu dengan yang lainnya.
2
K-Medoids
 Metode ini merupakan algoritma yang digunakan untuk menemukan
medoids di dalam sebuah cluster yang merupakan titik pusat dari
suatu kelompok (cluster).
 Berbeda dengan algoritma K-Means, K-Medoids memilih data points
sebagai pusat (medoids)
 Perbedaan lainnya yaitu, K-Medoids menggunakan objek sebagai
perwakilan (medoids) pusat cluster untuk setiap cluster, sedangkan K-
Means menggunakan nilai rata-rata (mean) sebagai pusat cluster.
3
Langkah-Langkah Algoritma K-Medoids
1. Inisialisasi pusat cluster sebanyak k (jumlah cluster)
2. Alokasikan setiap data (objek) ke cluster terdekat menggunakan
ukuran jarak Euclidean Distance.
3. Pilih secara acak objek pada masing-masing cluster sebagai
kandidat medoid baru.
4. Hitung jarak setiap objek yang berada pada setiap masing-
masing cluster dengan menempuh medoids baru.
4
Langkah-Langkah Algoritma K-Medoids
5. Hitung total simpangan (S) dengan menghitung nilai total distance

baru-total distance lama. Jika S<0, maka ganti objek dengan data
cluster untuk memperoleh sekelompok k objek yang baru sebagai
medoid.
6. Ulangi tahap ke 3 sampai ke 5 hingga tidak terjadi perubahan medoid,
sehingga didapatkan cluster beserta anggota cluster masing-masing.

5
Rumus Euclidean Distance

Keterangan
d (x, y) : Jarak antara data x ke data y
: Data testing ke-i
: Data training ke-i

6
Contoh Kasus
Kelompokkan data berikut ke dalam 2 cluster dengan centroid:
A : (3, 5)
B : (1, 2)
No Pixel 1 Pixel 2
1 0 5
2 3 5
3 1 2
4 7 9
5 7 2

7
Langkah 1 :
Inisialisasi pusat cluster (centroid) sebanyak k (jumlah cluster)
Ditentukan k=2 dan centroid A = (3, 5) dan B (1, 2)

No Pixel 1 Pixel 2
1 0 5
2 3 5
3 1 2
4 7 9
5 7 2

9
Langkah 2 :
Alokasikan setiap data (objek) ke cluster terdekat
menggunakan ukuran jarak Euclidean Distance.
 Hitung jarak semua data ke titik pusat A (3, 5)

No Jarak ke A
1 =3
2 =0
3 = 3.6
4 = 5.7
5 =5

11
 Hitung jarak semua data ke titik pusat B (1, 2)

No Jarak ke A
1 = 3.2
2 = 3.6
3 =0
4 = 9.2
5 =6

12
 No A B Distance Cluster
1 3 3.2 3 A
2 0 3.6 0 A
3 3.6 0 0 B
4 5.7 9.2 5.7 A
5 5 6 5 A
Total Distance 13.7

 Anggota A (0,5), (3,5), (7,9), (7,2)

Anggota B (1,2)
13
Langkah 3 :
Pilih secara acak objek pada masing-masing cluster
sebagai kandidat medoid baru.
Ditentukan k=2 dan centroid A = (7, 2) dan B (1, 2)

No Pixel 1 Pixel 2
1 0 5
2 3 5
3 1 2
4 7 9
5 7 2

15
Langkah 4 :
Hitung jarak setiap objek yang berada pada setiap
masing-masing cluster dengan menempuh medoids baru.
 Hitung jarak semua data ke titik pusat A (7, 2)

No Jarak ke A
1 = 7.6
2 =5
3 =6
4 =7
5 =0

17
 Hitung jarak semua data ke titik pusat B (1, 2)

No Jarak ke A
1 = 3.2
2 = 3.6
3 =0
4 = 9.2
5 =6

18
 No A B Distance Cluster
1 7.6 3.2 3.2 B
2 5 3.6 3.6 B
3 6 0 0 B
4 7 9.2 7 A
5 0 6 0 A
Total Distance Baru 13.8

 Anggota A (7,9), (7,2)

Anggota B (0,5), (3,5), (1,2)
19
Langkah 5 :
Hitung total simpangan (S) dengan menghitung
Nilai Total Distance Baru-total Distance Lama.
 Total Simpangan:

S = Total Distance Baru – Total Distance Lama

S = 13.8-13.7
S = 0.1

 Kesimpulan
Karena S lebih besar dari 0, maka iterasi berhenti

21
Kesimpulan dan Hasil Interpretasi Cluster
No Pixel 1 Pixel 2 Cluster
1 0 5 B
2 3 5 B
3 1 2 B
4 7 9 A
5 7 2 A

 Interpretasi :
Cluster A

22
 Latihan
 Kelompokkan data berikut No Nama Tinggi (cm) Berat (kg)
menjadi 2 cluster menggunakan 1 Adin 179 79
K-Medoids , bila diketahui titik 2 Bima 170 70
pusat : 3 Dodi 175 79
 A (175, 75) dan B (180, 80) 4 David 178 78
5 Lena 175 77
6 Ziko 175 75
7 Zidane 180 80

23
 Latihan
 Kelompokkan data berikut No Nama Tinggi (cm) Berat (kg)
menjadi 2 cluster menggunakan 1 Adin 179 79
KMedoids , bila diketahui titik 2 Bima 170 70
pusat : 3 Dodi 175 79
 A (175, 75) dan B (178, 78) 4 David 178 78
5 Lena 175 77
6 Ziko 175 75
7 Zidane 180 80

24
 Latihan
 Kelompokkan data berikut No Nama Tinggi (cm) Berat (kg)
menjadi 2 cluster menggunakan 1 Adin 179 79
KMedoids , bila diketahui titik 2 Bima 170 70
pusat : 3 Dodi 175 79
 A (175, 75) dan B (175, 77) 4 David 178 78
5 Lena 175 77
6 Ziko 175 75
7 Zidane 180 80

25