Algoritma K-Medoids: Contoh Perhitungan Manual Lengkap

Tutorial ini membahas algoritma K-Medoids dengan contoh perhitungan manual lengkap untuk melakukan clustering. Contoh menggunakan enam pelanggan dan dua atribut dengan jumlah cluster \(k=2\).

Berbeda dari K-Means yang menggunakan centroid berupa nilai rata-rata, K-Medoids menggunakan objek data aktual sebagai pusat cluster. Pada tutorial ini digunakan pendekatan PAM (Partitioning Around Medoids) dengan proses pemilihan medoid awal, assignment, perhitungan total cost, dan pertukaran atau swap medoid hingga tidak ada perbaikan cost.

---

Daftar Isi

• Pengertian K-Medoids
• Perbedaan K-Means dan K-Medoids
• Apa Itu Medoid?
• Rumus Jarak Euclidean
• #01 Menentukan Data dan Jumlah Cluster
• #02 Menentukan Medoid Awal
• #03 Menghitung Matriks Jarak
• #04 Mengalokasikan Data ke Medoid Terdekat
• #05 Menghitung Total Cost Awal
• #06 Melakukan Swap Medoid
• #07 Menghitung Assignment Setelah Swap
• #08 Melanjutkan Iterasi hingga Konvergen
• #09 Hasil Cluster Akhir
• Interpretasi Hasil K-Medoids
• Kelebihan dan Kekurangan K-Medoids
• Ringkasan
• FAQ K-Medoids
• Referensi
• Source Code K-Medoids

---

Pengertian K-Medoids

K-Medoids adalah algoritma clustering partisional yang membagi data menjadi \(k\) cluster. Setiap cluster direpresentasikan oleh sebuah medoid.

Medoid adalah objek nyata dari dataset yang digunakan sebagai pusat representatif cluster. Anggota cluster ditentukan berdasarkan kedekatan terhadap medoid.

Salah satu algoritma K-Medoids yang dikenal luas adalah PAM (Partitioning Around Medoids). PAM mengevaluasi kemungkinan pertukaran antara medoid dan non-medoid untuk mencari konfigurasi dengan total jarak yang lebih kecil.

Perbedaan K-Means dan K-Medoids

Apa Itu Medoid?

Medoid adalah titik data yang digunakan untuk merepresentasikan sebuah cluster. Misalnya jika A1 menjadi medoid, maka koordinat pusat cluster benar-benar sama dengan data A1.

Ini berbeda dari centroid K-Means yang dihitung menggunakan rata-rata koordinat anggota cluster.

Rumus Jarak Euclidean

Tutorial ini menggunakan Euclidean Distance:

$$ d(x_i,x_j) = \sqrt{ \sum_{p=1}^{q} (x_{ip}-x_{jp})^2 } $$

Karena contoh menggunakan dua atribut:

$$ d(A_i,A_j) = \sqrt{ (X1_i-X1_j)^2 + (X2_i-X2_j)^2 } $$

Jika atribut memiliki skala yang sangat berbeda, data sebaiknya dinormalisasi atau distandardisasi terlebih dahulu agar satu atribut tidak mendominasi jarak.

#01 Menentukan Data dan Jumlah Cluster

Contoh menggunakan enam pelanggan dengan dua atribut yang telah berada pada skala yang sebanding.

Jumlah cluster:

$$ k=2 $$

#02 Menentukan Medoid Awal

Untuk memperlihatkan proses swap dengan jelas, medoid awal pada contoh dipilih:

$$ M_1=A1=(2,2) $$

$$ M_2=A2=(2,3) $$

Jadi konfigurasi medoid awal adalah: A1 dan A2.

Pemilihan medoid awal dapat memengaruhi jalannya proses. Pada implementasi praktis, inisialisasi dapat menggunakan strategi tertentu atau beberapa kali percobaan untuk mengurangi risiko memperoleh solusi lokal yang kurang baik.

#03 Menghitung Matriks Jarak

Contoh Jarak A1 ke A2

$$ d(A1,A2) = \sqrt{ (2-2)^2 + (2-3)^2 } $$

$$ d(A1,A2) = 1 $$

Contoh Jarak A1 ke A4

$$ d(A1,A4) = \sqrt{ (2-8)^2 + (2-8)^2 } = 8.485281 $$

#04 Mengalokasikan Data ke Medoid Terdekat

Setiap data dihitung jaraknya terhadap A1 dan A2. Data masuk ke cluster medoid dengan jarak paling kecil.

Contoh A3

Jarak A3 ke A1:

$$ d(A3,A1) = 1 $$

Jarak A3 ke A2:

$$ d(A3,A2) = 1.414214 $$

Karena 1 lebih kecil daripada 1.414214, A3 masuk ke cluster dengan medoid A1.

Contoh A5

$$ d(A5,A1) = 9.219544 $$

$$ d(A5,A2) = 8.485281 $$

A5 lebih dekat ke A2 pada konfigurasi awal.

#05 Menghitung Total Cost Awal

Total cost adalah jumlah jarak minimum seluruh data terhadap medoid cluster masing-masing.

$$ Cost_{awal} = 0 + 0 + 1 + 7.81025 + 8.485281 + 8.602325 $$

$$ Cost_{awal} = 25.897856 $$

Nilai ini menjadi acuan untuk menilai apakah pertukaran medoid menghasilkan cluster yang lebih baik.

#06 Melakukan Swap Medoid

PAM mencoba menukar satu medoid dengan satu data non-medoid. Konfigurasi yang menghasilkan total cost lebih kecil dianggap sebagai perbaikan.

Contoh Kandidat Terbaik Iterasi 1

Pada iterasi pertama, kandidat terbaik adalah menukar:

A2 → A4

Medoid baru:

A1 dan A4

Total cost kandidat:

$$ Cost_{baru} = 4 $$

Perubahan cost:

$$ \Delta = Cost_{baru} - Cost_{lama} $$

$$ \Delta = 4 - 25.897856 = -21.897856 $$

Karena \(\Delta < 0\), swap diterima.

#07 Menghitung Assignment Setelah Swap

Setelah swap terbaik pada iterasi pertama, medoid menjadi A1 dan A4. Seluruh data dihitung kembali terhadap medoid baru.

Contoh A5

$$ d(A5,A1) = 9.219544 $$

$$ d(A5,A4) = 1 $$

A5 masuk ke cluster A4 .

Total cost setelah swap:

$$ Cost = 4 $$

#08 Melanjutkan Iterasi hingga Konvergen

Proses swap diulangi menggunakan medoid terbaru. Algoritma berhenti jika tidak ada kandidat pertukaran yang menghasilkan total cost lebih kecil.

Iterasi Terakhir

Medoid sebelum evaluasi: A1 dan A4 .

Cost saat ini:

$$ Cost = 4 $$

Kandidat swap terbaik yang tersisa memiliki cost:

$$ Cost_{candidate} = 4.414214 $$

Karena tidak ada kandidat dengan cost lebih kecil, proses dinyatakan konvergen.

#09 Hasil Cluster Akhir

Medoid akhir:

A1 dan A4 .

Total cost akhir:

$$ Cost_{akhir} = 4 $$

Penurunan cost:

$$ 25.897856 - 4 = 21.897856 $$

atau sekitar:

$$ 84.55\% $$

Interpretasi Hasil K-Medoids

Pada dataset contoh, cluster akhir memisahkan data menjadi dua kelompok yang cukup jelas.

Cluster dengan medoid A1 berisi: A1, A2, A3.

Cluster dengan medoid A4 berisi: A4, A5, A6.

Medoid dapat digunakan sebagai contoh anggota yang paling representatif terhadap kelompoknya pada konfigurasi hasil clustering.

Namun, makna bisnis dari setiap cluster tetap harus ditentukan berdasarkan atribut asli dan konteks data. Algoritma hanya membentuk kelompok berdasarkan ukuran jarak yang digunakan.

Kelebihan dan Kekurangan K-Medoids

Kelebihan K-Medoids

• Pusat cluster merupakan data aktual sehingga mudah diinterpretasikan.
• Umumnya lebih tahan terhadap outlier dibanding K-Means.
• Dapat digunakan dengan berbagai ukuran dissimilarity selama definisinya sesuai.
• Cocok ketika representasi cluster harus berupa objek nyata.

Kekurangan K-Medoids

• PAM dapat memiliki biaya komputasi lebih tinggi dibanding K-Means.
• Jumlah cluster \(k\) harus ditentukan terlebih dahulu.
• Hasil dapat dipengaruhi pemilihan medoid awal dan solusi lokal.
• Penggunaan distance tetap sensitif terhadap skala atribut.
• Dataset sangat besar memerlukan pendekatan yang lebih efisien daripada evaluasi swap PAM secara penuh.

Ringkasan

K-Medoids membagi data menjadi beberapa cluster dengan menggunakan objek aktual sebagai pusat cluster.

Pada contoh ini digunakan \(k=2\) dengan medoid awal A1 dan A2. Total cost awal adalah 25.897856.

Setelah proses swap, medoid akhir menjadi A1 dan A4 dengan total cost 4.

Algoritma berhenti ketika tidak ada pertukaran medoid dan non-medoid yang mampu menurunkan total cost.

FAQ K-Medoids

Apa itu K-Medoids?

K-Medoids adalah algoritma clustering yang menggunakan data aktual sebagai pusat atau medoid setiap cluster.

Apa itu medoid?

Medoid adalah objek data yang dipilih untuk merepresentasikan sebuah cluster.

Apa perbedaan medoid dan centroid?

Medoid merupakan data aktual dari dataset, sedangkan centroid adalah titik rata-rata yang tidak harus terdapat pada dataset.

Apa itu PAM?

PAM adalah Partitioning Around Medoids, salah satu algoritma untuk melakukan K-Medoids dengan mengevaluasi pertukaran medoid dan non-medoid.

Bagaimana menentukan cluster suatu data?

Data ditempatkan pada cluster dengan medoid yang memiliki jarak paling kecil terhadap data tersebut.

Apa yang dimaksud total cost?

Total cost adalah jumlah jarak setiap data terhadap medoid cluster terdekatnya.

Kapan swap medoid diterima?

Pada pendekatan PAM yang digunakan dalam tutorial ini, swap diterima jika menghasilkan total cost yang lebih kecil.

Kapan algoritma berhenti?

Algoritma berhenti ketika tidak ada kandidat swap yang mampu menurunkan total cost.

Apakah K-Medoids tahan terhadap outlier?

K-Medoids umumnya lebih robust terhadap outlier dibanding K-Means karena pusat cluster harus berupa objek aktual dan tidak dihitung sebagai rata-rata semua anggota.

Apakah K-Medoids harus menggunakan Euclidean Distance?

Tidak. Ukuran dissimilarity dapat dipilih sesuai karakter data. Tutorial ini menggunakan Euclidean Distance agar perhitungan manual mudah diikuti.

Apakah data perlu dinormalisasi?

Jika atribut memiliki skala yang berbeda jauh, normalisasi atau standardisasi sangat disarankan sebelum menghitung jarak.

Bagaimana menentukan nilai k?

Nilai k dapat ditentukan berdasarkan kebutuhan analisis atau dibantu evaluasi clustering seperti silhouette score dan pendekatan validasi cluster lainnya.

Apakah K-Medoids termasuk supervised learning?

Tidak. K-Medoids termasuk unsupervised learning karena proses clustering tidak membutuhkan label kelas target.

Kapan K-Medoids cocok digunakan?

K-Medoids cocok ketika dibutuhkan clustering dengan pusat yang merupakan objek nyata dan ketika robustness terhadap data ekstrem lebih penting dibanding efisiensi K-Means.

---

Referensi

1. Kaufman, L. & Rousseeuw, P. J. (1990). Finding Groups in Data: An Introduction to Cluster Analysis. Wiley.
2. Park, H. S. & Jun, C. H. (2009). A Simple and Fast Algorithm for K-Medoids Clustering. Expert Systems with Applications, 36(2), 3336–3341.
3. Han, J., Kamber, M. & Pei, J. (2011). Data Mining: Concepts and Techniques, Third Edition. Morgan Kaufmann.

---

Source Code K-Medoids

Berikut adalah beberapa source code yang menggunakan algoritma K-Medoids untuk clustering.

Ada yang Ditanyakan?

Jika anda masih ada kesulitan atau kekeliruan tentang penjelasan metode di atas, bisa menghubungi kami lewat WA/Email sesuai halaman Kontak.

Jika ingin memiliki file excel dari metode di atas bisa melihat cara download di halaman Download.

Jika ingin memiliki source code dari metode di atas, baik berbasis web maupun desktop bisa melihat daftar harga donasi di halaman Daftar Source Code.

Donasi ini digunakan oleh penulis untuk membayar server dan membeli kopi sembari membuat tutorial Metode/Algoritma lainnya :).