Clustering K-Medoids

Clustering K-Medoids – Hai hai sobat Exsight, seiring berkembangnya zaman kemampuan untuk mengekstrak informasi berharga dari kumpulan data sangatlah penting untuk kita kuasai. Salah satu teknik yang bisa kita gunakan untuk menemukan pola tersembunyi di dalam data adalah clustering. Ketika membicarakan tentang clustering, seringkali metode K-Means menjadi topik utama. Namun, di balik bayang-bayang popularitas K-Means,terdapat metode lain yang tak kalah menariknya untuk menangani data dengan outlier dan noise, yaitu metode clustering K-Medoids. Tanpa berlama-lama lagi, yuk simak artikel ini dengan seksama yaa!

Definisi

Clustering k-medoids adalah salah satu metode clustering yang mirip dengan k-means, tetapi berbeda dalam cara memilih pusat kluster (centroid). Pada k-medoid, pusat kluster dipilih dari data aktual yang ada, bukan dari rata-rata posisi data. Metode clustering K-Medoids menawarkan pendekatan yang lebih kuat dengan memilih pusat kluster dari data yang sebenarnya, bukan sekadar rata-rata. Hal ini menjadikan metode clustering K-Medoids mampu menghasilkan kluster yang lebih representatif, terutama ketika kita berurusan dengan data yang tidak ideal atau memiliki karakteristik unik

Konsep Dasar

Clustering K-Medoids adalah salah satu metode clustering yang digunakan untuk mengelompokkan data ke dalam beberapa kluster berdasarkan kesamaan di antara data-data tersebut. Berikut adalah konsep dasar dari clustering K-Medoids:

1. Medoid sebagai Pusat Kluster
   Berbeda dengan metode clustering K-Means yang menggunakan rata-rata (mean) sebagai pusat kluster, clustering K- Medoids menggunakan medoid, yaitu data titik yang sebenarnya dalam dataset yang menjadi pusat kluster. Medoid adalah titik yang meminimalkan jarak total ke semua titik lain dalam kluster.
2. Pengukuran Jarak
   Sama halnya seperti clustering K-Means, pada clustering K-Medoids menggunakan pengukuran jarak untuk menentukan kesamaan antara titik-titik data. Umumnya, jarak Euclidean digunakan, tetapi jenis jarak lain seperti Manhattan distance juga bisa digunakan tergantung pada konteks dan tipe data.
3. Proses Iteratif:
   • Inisialisasi
     Pilih k data secara acak sebagai medoid awal.
   • Penugasan (Assignment)
     Setiap data dalam dataset ditugaskan ke kluster yang medoidnya paling dekat berdasarkan jarak terpendek.
   • Pembaruan Medoid
     Untuk setiap cluster yang terbentuk, tentukan medoid baru dengan memilih titik yang meminimalkan total jarak dalam kluster tersebut.
   • Iterasi
     Ulangi langkah penugasan dan pembaruan hingga tidak ada perubahan pada medoid, atau hingga perubahan total jarak tidak signifikan.
4. Kekokohan Terhadap Outlier
   Salah satu kelebihan dari clustering K-Medoids dibandingkan dengan clustering K-Means adalah kekokohannya terhadap outlier atau data ekstrem. Karena medoid adalah titik nyata dari data, metode ini lebih tahan terhadap pengaruh negatif dari data yang berada jauh dari pusat kluster.
5. Kompleksitas Komputasi
   Clustering K-Medoids biasanya lebih lambat daripada clustering K-Means karena perlu menghitung jarak antara setiap titik data dengan setiap medoid, terutama jika dataset besar. Namun, keunggulan dalam menangani outlier dan memberikan kluster yang lebih representatif menjadikan K-Medoids pilihan yang baik dalam situasi tertentu.

Clustering K-Medoids sering digunakan dalam analisis data yang mengandung noise atau outlier, serta dalam situasi di mana hasil yang lebih stabil dan robust diinginkan dibandingkan dengan K-Means.

Perbedan Clustering K-Medoids & K-Means

Penelitian mengenai clustering seringkali dikaitkan dengan metode K-Means, namun tentunya terdapat perbedaan mendasar antara clustering K-Medoids dan K-Means, yaitu sebagai berikut.

No	Aspek Perbedaan	Clustering K-Medoids	Clustering K-Means
1.	Pemilihan Pusat Cluster	Pusat cluster disebut dengan medoid, dimana medoid merupakan salah satu titik data sebenarnya dari dataset yang memiliki total jarak terkecil terhadap semua titik lain dalam cluster tersebut. Medoid selalu merupakan titik data aktual dalam dataset, tidak seperti centroid dalam K-Means.	Pusat cluster atau disebut dengan centroid , dimana centroid merupakan rata-rata aritmatika dari semua data dalam satu cluster. Centroid dapat berupa titik data yang bukan bagian dari dataset asli, karena dihitung berdasarkan rata-rata posisi semua titik dalam cluster tersebut.
2.	Ketahanan (Robustness) Terhadap Outlier	Lebih tahan terhadap outliers dan noise. Hal ini dikarenakan medoid adalah titik data yang sebenarnya, pemilihan medoid tidak dipengaruhi oleh outliers secara signifikan. Ini membuat K-Medoids lebih stabil dalam menghadapi dataset yang memiliki nilai ekstrim.	Lebih sensitif terhadap outliers dan data yang memiliki noise, karena centroid bisa dipengaruhi oleh nilai ekstrim. Outliers dapat menyebabkan centroid bergerak jauh dari pusat cluster yang sebenarnya.
3.	Komputasi	Lebih memakan waktu komputasi, terutama untuk dataset yang besar, karena harus menghitung total jarak untuk setiap titik data dalam cluster setiap kali mengubah medoid. Proses ini membuat K-Medoids lebih lambat dibandingkan K-Means.	Lebih efisien dalam hal komputasi karena perhitungan centroid lebih sederhana dan langsung. Algoritma K-Means biasanya lebih cepat dalam konvergensi.
4.	Hasil Clustering	Cenderung memberikan hasil clustering yang lebih stabil karena medoid adalah titik data yang sebenarnya, sehingga perubahan dalam dataset atau inisialisasi tidak terlalu memengaruhi hasil akhir secara signifikan.	Hasil clustering dapat bervariasi karena centroid yang dihitung dapat berubah dengan dataset yang berbeda atau inisialisasi yang berbeda.

Kelebihan dan Kelemahan

Terdapat beberapa kelebihan dan kelemahan dari algoritma Clustering K-Medoids diantaranya adalah sebagai berikut.

Kelebihan

1. Robust terhadap Outlier
K-Medoids menggunakan medoid sebagai pusat klaster, yang merupakan titik data aktual dari dataset. Berbeda dengan centroid di K-means yang bisa sangat dipengaruhi oleh data ekstrem atau outlier, medoid tidak terpengaruh secara signifikan. Hal ini membuat K-medoids lebih tahan terhadap outlier, sehingga hasil klasterisasi lebih stabil dan representatif.

2. Medoid adalah Titik Data Nyata
Dalam K-medoids, pusat setiap klaster adalah medoid yang dipilih dari titik data yang ada, bukan centroid yang dihitung. Hal ini menjadikan hasil klasterisasi lebih mudah diinterpretasikan karena medoid merupakan elemen dari dataset asli.

3. Stabilitas pada Distribusi Data yang Tidak Merata
Algorima K-Medoids lebih baik dalam menangani situasi di mana data tidak terdistribusi secara merata. Hal ini dikarenakan pemilihan medoid tidak terpengaruh oleh jarak rata-rata yang bisa dipengaruhi oleh ukuran klaster, metode ini bisa memberikan hasil klasterisasi yang lebih konsisten.

Kelemahan

1. Waktu Komputasi Lebih Tinggi
Proses menemukan medoid yang optimal di K-medoids membutuhkan perhitungan jarak antara setiap titik data dengan setiap medoid, dan memerlukan iterasi untuk mengevaluasi biaya total klasterisasi. Ini bisa memakan waktu, terutama untuk dataset yang besar, karena banyaknya perhitungan yang harus dilakukan. Oleh karena itu, K-medoids sering lebih lambat dibandingkan K-means.

2. Tidak Cocok untuk Dataset yang Sangat Besar
Dikarenakan waktu komputasi yang lebih tinggi, K-medoids tidak cocok digunakan untuk dataset dengan jumlah data yang sangat besar. Skalabilitas menjadi masalah karena setiap iterasi membutuhkan pengecekan semua kemungkinan medoid, yang bisa menjadi sangat tidak efisien dengan bertambahnya jumlah data.

3. Pemilihan Medoid Awal yang Sulit
Hasil akhir dari K-medoids bisa dipengaruhi oleh pemilihan medoid awal. Jika medoid awal tidak dipilih dengan baik, algoritma mungkin akan menemukan solusi suboptimal yang tidak merepresentasikan struktur data dengan baik.

Tahapan Algoritma Clustering K Medoids

1. Menentukan k sebagai banyaknya klaster yang ingin dibentuk.
2. Membangkitkan k pusat klaster (medoid) secara acak.
3. Menghitung jarak objek non-medoid dengan medoid pada tiap klaster dan menempatkan tiap objek non-medoid tersebut ke medoid terdekat, kemudian hitung total jaraknya.
4. Memilih secara acak objek non-medoid pada masing-masing klaster sebagai kandidat medoid baru
5. Menghitung jarak setiap objek non- medoid baru dan menempatkan tiap objek non-medoid tersebut ke kandidat medoid terdekat, kemudian hitung total jaraknya.
6. Menghitung selisih total jarak (S_{total jarak}), dimana
   S_{total jarak} = total jarak pada kandidat medoidbaru – total jarak pada medoid lama
7. Jika diperoleh nilai Stotaljarak< 0, maka kandidat medoidbaru tersebut menjadi medoidbaru dan jika diperoleh S_totaljarak > 0 iterasi berhenti
8. Kembali ke langkah (4) sampai (7) sampai tidak terjadi perubahan medoidatau Stotal jarak> 0

Tutorial Clustering K-Medoids dengan Software R

Selengkapnya kita akan mencoba tutorial clustering K-Medoids dengan software R. Adapun studi kasus yang akan kita gunakan yaitu terkait Tindak Pindak Kriminal yang didapatkan dari situs Badan Pusat Statistik Indonesia tahun 2022. Adapun data bisa di-download di sini.
Keterangan terkait data yang digunakan yaitu:
* Tidak terdapat missing value pada data.
* Data terdiri atas 34 observasi.

#Load Library

Tahapan awal, sebelum melakukan running syntax di software R terlebih dahulu melakukan load library R.  Adapun syntax R yang digunakan adalah sebagai berikut.

# Import library untuk data wrangling
library(tidyverse)
library(dplyr)

# Import library untuk visualisasi
library(factoextra) # Visualisasi hasil clustering
library(gridExtra) # Visualisasi karakteristik cluster
library(GGally) # Correlation matrix
library(ggiraphExtra)
library(sf) # Read data map
library(plotly) # Interactive Plotting
library(Rtsne)

# Machine Learning - Clustering 
library(cluster)
library(factoextra)
library(mvnTest)

#Load Data

data=read.csv(file.choose(),header=TRUE,sep=",")
rownames(data) <- data$Provinsi

Berdasarkan Gambar 1. terlihat bahwa data yang digunakan terdiri atas 34 data dengan 7 variabel.

#Standarisasi Data

dataclus <- data[,-1]
datafix<-scale(dataclus)

#Penentuan Jumlah Cluster (K optimum)

set.seed(1000)

fviz_nbclust(x =datafix, 
             FUNcluster = pam,
             method = 'wss',
             k.max = 10)

Jumlah cluster optimum (K Optimum) dapat ditentukan juga menggunakan bantuan grafik Elbow, dimana k minimum akan didapat ketika grafik sudah tidak bergerak menurun dengan tajam.
Berdasarkan Gambar 3, terlihat bahwa grafik sudah tidak bergerak menurun dengan tajam ketika pada titik cluster 4 sehingga dapat diartikan jumlah cluster optimum yaitu sebesar 4.

#Hasil Pembagian Cluster

RNGkind(sample.kind = "Rounding")
set.seed(1000)

customer_kmedoid <- pam(x =datafix, k = 4, metric = "euclidean", stand = FALSE)
table(customer_kmedoid$clustering)
fviz_cluster(object = customer_kmedoid, data = datafix)

Hasil pada Gambar 4, menampilkan informasi bahwa terdapat 4 cluster yang terbentuk dalam hal ini terlihat bahwa untuk cluster yang ditandai dengan warna Hijau hanya terdiri atas 1 provinsi yaitu Sumatera Utara. Kemudian untuk cluster yang ditandai dengan warna Ungu terdiri atas Provinsi Jawa Timur, DKI Jakarta, Sumatera Selatan, dan Sulawesi Selatan, sedangkan provinsi-provinsi lainnya terdapat pada cluster yang ditandai dengan warna Merah dan warna Biru.

Secara lebih detail apabila kita perhatikan jumlah Provinsi tiap cluster terlihat seperti pada Gambar 5. dimana terlihat bahwa mayoritas Provinsi terdapat pada cluster 3 sebanyak 17 provinsi, lalu di posisi terbanyak kedua terdapat 12 provinsi pada cluster 1.

Secara lebih pengkategorian cluster untuk masing- masing Provinsi adalah sebagai berikut.

Provinsi	Cluster K- Medoid
Aceh	1
Sumatera Utara	2
Sumatera Barat	1
Riau	1
Jambi	3
Sumatera Selatan	4
Bengkulu	1
Lampung	1
Kep. Bangka Belitung	3
Kep. Riau	3
DKI Jakarta	4
Jawa Barat	1
Jawa Tengah	1
DI Yogyakarta	3
Jawa Timur	4
Banten	3
Bali	3
Nusa Tenggara Barat	3
Nusa Tenggara Timur	1
Kalimantan Barat	3
Kalimantan Tengah	3
Kalimantan Selatan	1
Kalimantan Timur	3
Kalimantan Utara	3
Sulawesi Utara	1
Sulawesi Tengah	1
Sulawesi Selatan	4
Sulawesi Tenggara	3
Gorontalo	3
Sulawesi Barat	3
Maluku	3
Maluku Utara	3
Papua Barat	3
Papua	1

Berdasarkan Tabel di atas selanjutnya kita melakukan profiling cluster untuk mengetahui karakteristik dari setiap cluster . Dalam hal ini kita akan menghitung nilai Rata-Rata Tiap Cluster pada Data Asli yaitu sebagai berikut.

Variabel	Cluster 1	Cluster 2	Cluster 3	Cluster 4
Nyawa	33,500	96,000	10,941	60,750
Fisik	951,000	5396,000	344,235	3108,250
Kesusilaan	873,500	6949,000	435,647	3284,250
Kemerdekaan	2201,333	12973,000	882,118	4950,000
Hak Milik	39,500	86,000	28,882	150,750
Narkotika	840,000	4287,000	355,294	1921,000
Penipuan	210,250	904,000	94,176	219,250

Berdasarkan Tabel 2. diperoleh informasi bahwa nilai hampir sebagian besar kejahatan (kejahatan nyawa, fisik, kesusilaan, kemerdekaan, Narkotika, dan Penipuan) memiliki nilai rata- rata tertinggi pada Cluster 2 , dalam hal ini hanya terdapat 1 Provinsi yang masuk dalam Cluster 2 yaitu Provinsi Sumatera Utara.

Namun ada 1 kejahatan dengan nilai rata-rata tertinggi di cluster lainnya, yaitu kejahatan Hak Milik dimana nilai rata-rata tertinggi sebesar 150,750 dan terdapat pada cluster 4. Adapun cluster 4 terdiri atas 4 provinsi yaitu Provinsi Sumatera Selatan, DKI Jakarta, Jawa Timur, dan Sulawesi Selatan.

Referensi

Nahdliyah, M., Widiharih, T., & Prahutama, A. (2019). Metode K- Medoids Clustering dengan Validasi Silhouette Index dan C- Index (Studi Kasus Jumlah Kriminalitas Kabupaten/Kota di Jawa Tengah Tahun 2018). Jurnal Gaussian, Vol.8, No.2, 161 – 170.

Oktarina, C., Notodiputro, K., & Indahwati. (2020). Comparison of K- Means Clustering Method and K- Medoids on Twitter Data. Indonesian Journal of Statistics and Its Applications, Vol.4, No.1, 189- 202.

https://rpubs.com/Anoe/cluster-kmeans-kmedoids

Finally, sampai sudah nih kita di penghujung artikel, sekian dulu ya penjelasan terkait Clustering K- Medoids . Apabila masih ada yang dibingungkan bisa langsung saja ramaikan kolom komentar atau hubungi admin melalui tombol bantuan di kanan bawah. Stay tuned di website https://exsight.id/blog/ agar tidak ketinggalan artikel-artikel menarik lainnya. Bye bye!