Penjelasan k-Medoids, Algoritma, dan Contohnya

Pada artikel sebelumnya tentang kelemahan k-means dan contohnya (lihat pada artikel sebelumnya disini), algoritma k-means sangat sensitif terhadap pencilan (outliers) karena object-object pencilan sangat jauh berbeda dari object lain pada umumnya sehingga ketika dimasukkan ke dalam suatu cluster, object-object seperti itu mendistorsi nilai rerata (mean) dari cluster tersebut. Hal ini secara tak sengaja berpengaruh pada object-object lainnya. Contoh tentang kelemahan ini bisa dibaca lagi di artikel sebelumnya [Kelemahan k-means dan Contohnya].

Bagaimana kita bisa memodifikasi algoritma k-means untuk mengurangi sensitivitas terhadap pencilan? Alih-alih menggunakan nilai rerata dari object-object dalam suatu cluster sebagai titik acuan (pusat cluster), kita bisa mengambil object-object aktualnya untuk menyajikan cluster-cluster tersebut dengan menggunakan salah satu object sebagai pusat cluster di tiap cluster (jadi yang menjadi pusat cluster bukan nilai rerata dari object-object tetapi salah satu objectnya-lah yang menjadi titik acuan atau pusat cluster). Object-object lainnya (sisanya) dimasukkan ke dalam cluster yang terdekat atau paling mirip dengan object yang menjadi pusat cluster tersebut. Metode partisi kemudian dilakukan berdasarkan prinsip meminimalkan hasil penjumlahan dari ketidakmiripan (simpangan) diantara setiap object p dan object yang menjadi pusat clusternya. 

[rumus kriteria simpangan mutlak]

Dimana E adalah jumlah simpangan (error) mutlak untuk semua object-object p dalam dataset, dan o_i adalah pusat cluster C_i. Ini adalah dasar dari metode k-medoids, yang mengelompokkan object sebanyak n ke dalam cluster sebanyak k dengan cara meminimalkan jumlah simpangan (error) mutlak.

Jika k = 1, kita bisa mendapatkan median secara tepat dalam waktu O(n²). Namun bila k adalah suatu angka positif umum lainnya, k-medoid menjadi rumit dari sisi komputasi.

Algoritma PAM (Partitioning Around Medoids) adalah wujud umum dari clustering k-medoids. Algoritma ini mengatasi masalah iterasi, yaitu masalah karena metode atau cara yang greedy atau boros dan tidak efisien secara komputasi. Seperti halnya algoritma k-means, object yang menjadi pusat cluster pada awalnya dipilih secara acak. Berikutnya, kita mempertimbangkan apakah mengganti object yang menjadi pusat cluster dengan object lainnya akan meningkatkan kualitas clustering atau tidak. Semua kemungkinan pergantian dicoba. Proses iterasi dalam mengganti object-object yang menjadi pusat cluster dengan object-object lainnya berlanjut terus hingga kualitas clustering yang dihasilkan tidak bisa lagi ditingkatkan dengan pergantian atau dengan kata lain mencapai titik stabil. Kualitas ini diukur dengan fungsi rerata ketidakmiripan (jarak simpangan) diantara suatu object dengan object yang menjadi pusat clusternya.

Untuk lebih detilnya secara khusus, misalkan o₁,...,o_k adalah pusat-pusat cluster (atau medoids-nya). Untuk menentukan apakah suatu object yang bukan-pusat-cluster, yang dituliskan dengan o_random , adalah suatu penggantian yang baik untuk medoids saat ini (atau object yang sedang menjadi pusat cluster) o_j (1 ≤ j ≤ k), kita menghitung jarak dari setiap object p ke object terdekat di dalam {o₁,...,o_j-1,o_random,o_j+1,...,o_k}, dan kita gunakan jarak tersebut untuk meng-update fungsi jarak/simpangan (selisih jumlah jarak antara object dengan pusat cluster). Penetapan kembali object-object ke {o₁,...,o_j-1,o_random,o_j+1,...,o_k} adalah mudah. Misalkan object p saat ini masuk ke suatu cluster yang disajikan dengan medoid o_j (gambar (a) atau (b) di bawah). Apakah kita akan menetapkan ulang p ke cluster yang lain jika o_j diganti dengan o_random? Object p perlu ditetapkan ulang ke o_random atau ke suatu cluster lain yang disajikan dengan o_i (i ≠ j) yang manapun yang terdekat. Misalnya, dalam gambar (a), p adalah terdekat ke o_i dan karenanya ditetapkan ulang ke o_i. Namun, dalam gambar (b), p adalah terdekat ke o_random dan dengan begitu ditetapkan ulang ke o_random. Sebaliknya, bagaimana jika p saat ini ditetapkan ke suatu cluster yang disajikan dengan suatu object lain o_ii ≠j?

4 Kemungkinan fungsi simpangan k-medoids

Object o tetap dimasukkan ke cluster yang disajikan dengan o_i sepanjang o masih lebih dekat ke o_i dibanding ke o_random (gambar (c)). tetapi bila sebaliknya, o dimasukkan ke o_random (gambar  (d)).

Setiap kali penetapan ulang terjadi, selisih dalam simpangan mutlak, E, berkontribusi pada fungsi jarak/simpangan. Jadi, fungsi jarak/simpangan menghitung perbedaan/selisih nilai simpangan (error) mutlak jika object yang menjadi pusat cluster saat ini diganti dengan object lain. Jumlah total jarak/simpangan dari pertukaran ini adalah jumlah simpangan-simpangan yang terjadi akibat pertukaran dengan object-object lain ketika dicoba untuk menjadi pusat cluster (atau medoid). Jika jumlah totalnya adalah negatif, maka o_j diganti dengan o_random karena simpangan (error) mutlak E berkurang. Jika jumlah totalnya adalah positif, object yang sedang menjadi pusat cluster, o_j, tetap dipertahankan, dan tidak ada yang berubah dalam iterasi tersebut.

Algoritma: k-medoids.

Input:

• k: jumlah cluster
• D: dataset yang berisi object sebanyak n

Output: satu set cluster sebanyak k

Metode:

(1)    Secara acak memilih object-object k yang ada dalam D sebagai pusat awal cluster;
(2)    Repeat
(3)                    Tetapkan setiap object lainnya ke cluster dimana object tersebut paling dekat/mirip dengan object yang menjadi pusat cluster;
(4) Pilih secara acak object laian (yang bukan pusat cluster), orandom;
(5) Hitung total simpangan, S, dengan mempertukarkan object pusat cluster, oj, dengan orandom;
(6) if S < 0 then tukar oj dengan orandom untuk membuat object-object pusat cluster k yang baru;
(7)    Until stabil (tidak ada perubahan)

Berikut di bawah ini adalah video contoh k-medoids baik secara manual maupun menggunakan software RapidMiner:

Artikel terkait clustering:

• Pengertian Clustering atau Analisa Cluster
• Metode-metode Dasar dalam Clustering
• Penjelasan Cara Kerja Algoritma k-Means: Suatu Teknik Clustering Partisi Berbasis Centroid
• Contoh Ilustrasi Clustering Dengan Menggunakan k-Means dan Variannya: k-Modes
• Kelemahan k-Means dan Contohnya
• Penjelasan k-Medoids, Algoritma, dan Contohnya
• k-Means vs k-Medoids, Kelemahan k-Medoids dan Solusinya: CLARA