Algoritma K-Medoid dan Contoh Perhitungan Manual

Pondok Belajar   December 16, 2018   Data Mining   5 comments  

Pengertian K-Medoid

K-Medoid merupakan kelompok metode partitional Clustering yang meminimalkan jarak antara titik berlabel berada dalam cluster dan titik yang ditunjuk sebagai pusat klaster itu. Berdeda dengan algoritma K-Means, K-Medoid memilih data points sebagai pusat (medoids). Perbedaan dari kedua algoritma ini yaitu algoritma K-Medoids atau PAM menggunakan objek sebagai perwakilan (medoid) sebagai pusat cluster untuk setiap cluster, sedangkan K-Means menggunakan nilai rata-rata (mean) sebagai pusat cluster [Kaur, dkk., 2014]. Algoritma K-Medoids memiliki kelebihan untuk mengatasi kelemahan pada pada algoritma K-Means yang sensitif terhadap noise dan outlier, dimana objek dengan nilai yang besar yang memungkinkan menyimpang pada dari distribusi data. Kelebihan lainnya yaitu hasil proses Clustering tidak bergantung pada urutan masuk dataset [Furqon, dkk., 2015].

K-Medoid adalah teknik partisi klasik Clustering yang mengelompokkan data set dari ni objek ke dalam kelompok k yang dikenal apriori. Dibandingkan dengan K-Mens, K-Medoid lebih kuat untuk mengatasi kebisingan (noise) dan pencilan (outlier) karena meminimalkan sejumlah dissimilarities berpasangan, bukan jumlah kuadrat jarak Euclidean. Sebuah medoid dapat didefinisikan sebagai objek cluster yang rata-rata perbedaan untuk semua objek dalam cluster minimal yaitu titik paling berlokasi di cluster.

Langkah-langkah algoritma K-Medoid:

1.   Inisialisasi pusat cluster sebanyak k (jumlah cluster)

2.   Alokasikan setiap data (objek) ke cluster terdekat menggunakan persamaan ukuran jarak Euclidian Distance dengan persamaan:

 3. Pilih secara acak objek pada masing-masing cluster sebagai kandidat medoid baru.

4.   Hitung jarak setiap objek yang berada pada masing-masing cluster dengan kandidat medoid baru.

5.   Hitung total simpangan (S) dengan menghitung nilai total distance baru – total distance lama. Jika S < 0, maka tukar objek dengan data cluster untuk membentuk sekumpulan k objek baru sebagai medoid.

6.   Ulangi langkah 3 sampai 5 hingga tidak terjadi perubahan medoid, sehingga didapatkan cluster beserta anggota cluster masing-masing.

 Bisa juga dengan menggunakan langkah-langkah seperti berikut ini :

1.      Inisialisasi: memilih objek k secara acak yang akan berfungsi sebagai medoids.

2.      Mengasosiasikan setiap titik data dengan medoid yang paling serupa dengan mengguna kan ukuran jarak dan menghitung biaya.

3.      Secara acak memilih objek k baru yang akan berfungsi sebagai medoid dan menyimpan  salinan dari set asli.

4.      Gunakan set medoids baru untuk menghitung ulang biaya.

5.      Jika biaya yang baru lebih besar dari pada biaya lama kemudian hentikan algoritma  tersebut.

6.      Ulangi langkah kedua hingga kelima sampai tidak ada perubahan dalam medoid.

Contoh Soal:

Contoh K-Medoid dengan perhitungan metode Manhattan Distance

D	X1	X2
D1	2	6
D2	3	4
D3	3	8
D4	4	7
D5	6	2
D6	6	4
D7	7	3
D8	7	4
D9	8	5
D10	7	6

·         Menentukan pusat medoid

Pusat medoid 1=3,4 (Y1)

Pusat medoid 2=7,4 (Y2)

Dihitung dengan perhitungan manhattan distance |x1-y1|&|x2-y2|

D	X1	X2	Distance (3,4)	Distance (7,4)
D1	2	6	|2-3|+|6-4|=3	|2-7|+|6-4|=5
D2	3	4	|3-3|+|4-4|=0	|3-7|+|4-4|=4
D3	3	8	|3-3|+|8-4|=4	|3-7|+|8-4|=7
D4	4	7	|4-3|+|7-4|=4	|4-7|+|7-4|=6
D5	6	2	|6-3|+|2-4|=5	|6-7|+|2-4|=3
D6	6	4	|6-3|+|4-4|=3	|6-7|+|4-4|=1
D7	7	3	|7-3|+|3-4|=5	|7-7|+|3-4|=1
D8	7	4	|7-3|+|4-4|=4	|7-7|+|4-4|=0
D9	8	5	|8-3|+|5-4|=6	|8-7|+|5-4|=2
D10	7	6	|7-3|+|6-4|=7	|7-7|+|6-4|=2

Total Cost = 3+0+4+4+3+1+1+0+2+2=20

1.      Medoid 1 dengan anggota {(3,4),(2,6),(3,8), (4,7)}

2.      Medoid 2 dengan anggota {(7,4),(6,2),(6,4), (7,3),(8,5),(7,6)}

Kemudian mencari pusat medoid yang baru didapat yaitu (3,4) dan (7,3)

D	X1	X2	Distance (3,4)	Distance (7,4)
D1	2	6	|2-3|+|6-4|=3	|2-7|+|6-3|=8
D2	3	4	|3-3|+|4-4|=0	|3-7|+|6-3|=6
D3	3	8	|3-3|+|8-4|=4	|3-7|+|6-3|=9
D4	4	7	|4-3|+|7-4|=4	|4-7|+|7-3|=7
D5	6	2	|6-3|+|2-4|=5	|6-7|+|2-3|=2
D6	6	4	|6-3|+|4-4|=3	|6-7|+|4-3|=2
D7	7	3	|7-3|+|3-4|=5	|7-7|+|3-3|=0
D8	7	4	|7-3|+|4-4|=4	|7-7|+|4-3|=1
D9	8	5	|8-3|+|5-4|=6	|8-7|+|5-3|=3
D10	7	6	|7-3|+|6-4|=7	|7-7|+|6-3|=3

Total cost =3+0+4+4+2+2+0+1+3+3=22

Total cost baru =22>20 (nilai total cost sebelumnya)

Jika nilai cost baru lebih besar dibandingkan dengan cost lama maka hentikan perhitungan

Medoid 1 dengan anggota {(3,4),(2,6),(3,8), (4,7)}

Medoid 2 dengan anggota {(7,4),(6,2),(6,4), (7,3),(8,5),(7,6)}