k-Means vs k-Medoids, Kelemahan k-Medoids dan Solusinya: CLARA

Metode mana yang lebih handal antara k-means vs k-medoids? 

Metode k-medoids lebih handal dibanding dengan k-means ketika ada data noise dan pencilan karena k-medoids tidak terlalu dipengaruhi oleh data pencilan atau data ekstrem lainnya dibandingkan dengan k-means. Namun demikian, kompleksitas tiap-tiap iterasi dalam algoritma k-medoids secara komputasi adalah O(k(n-k)²). [Baca artikel sebelumnya tentang: Penjelasan k-Medoids, Algoritma, dan Contohnya]. Bila nilai n dan k sangat besar, komputasi ini mejadi sangat mahal (lama dan rumit), dan jauh lebih mahal dibanding dengan metode k-means. Kesamaan dari kedua metode tersebut adalah bahwa pengguna perlu menetapkan k atau jumlah clusternya. Berikut di bawah ini adalah tabel yang lebih menjelaskan tentang kajian perbandingan antara k-means vs k-medoids dalam beberapa aspek:

Perbandingan k-means vs k-medoids dalam beberapa aspek

Bagaimana kita bisa mengatasi masalah komputasi dalam metode k-medoids ketika memiliki dataset yang besar? Algoritma k-medoids yang umum seperti PAM (Partitioning Around Medoids; lihat algoritmanya dalam artikel sebelumnya di link ini) bekerja efektif untuk dataset yang kecil, tetapi tidak berjalan baik untuk dataset yang besar. Untuk bekerja dengan dataset yang besar, metode berbasis sampling yang disebut dengan CLARA (Clustering LARge Applications) bisa digunakan. Alih-alih menggunakan seluruh dataset, CLARA menggunanakan sample dataset secara random. Algoritma PAM (Partitioning Around Medoids) kemudian diterapkan untuk menghitung medoids terbaik dari sample tersebut. Idealnya, sample seharusnya menyajikan data yang sangat mirip dengan dataset asli. Dalam banyak kasus, sample yang semakin besar akan bekerja dengan baik sehingga setiap object memiliki probabilitas yang sama untuk dipilih ke dalam sample. Object-object yang dipilih menjadi pusat cluster (medoids) akan cenderung mirip dengan yang sudah dipilih dari seluruh dataset. CLARA membuat clustering dari dari banyak sample secara acak dan menghasilkan clustering terbaik sebagai outputnya. Kompleksitas dalam menghitung medoids pada sample acak adalah O(ks² + k(n-k)), dimana s adalah ukuran sample, k adalah jumlah cluster, dan n adalah jumlah total object. CLARA bisa mengatasi dataset yang lebih besar dibandingkan dengan PAM.

Tingkat ke-efektivitas-an CLARA bergantung pada ukuran sample. Perhatikan bahwa PAM (Partitioning Around Medoids) mencari k-medoids terbaik diantara dataset, tetapi CLARA (Clustering LARge Applications) mencari k-medoids terbaik diantara sample dataset yang terpilih. CLARA tidak bisa menghasilkan clustering yang baik jika medoids terbaik yang di-sample-kan sangat jauh dari k-medoids terbaik. Jika satu object adalah salah satu dari k-medoids terbaik tetapi tidak dipilih selama proses sampling, CLARA tidak akan pernah menghasilkan clustering terbaik. (Kita akan mencoba ini dalam contoh latihan di artikel lainnya).

Bagaimana kita bisa meningkatkan kualitas dan skalabilitas CLARA?
Harap diingat bahwa ketika mencari medoids yang lebih baik, PAM menguji setiap object di dalam dataset terhadap medoid saat ini (object yang sedang menjadi pusat cluster), padahal CLARA membatasi kandidat medoids hanya ke suatu sampel acak dari dataset. Algoritma ter-acak (randomized) yang disebut CLARANS (Clustering LARge Applications based upon RANdomized Search) memberikan ‘pertukaran’ antara biaya (kompleksitas komputasi) dan ke-efektif-an dalam menggunakan sample untuk menghasilkan clustering.

Pertama, CLARANS secara acak memilih object-object sebanyak k di dalam dataset sebagai medoids. Kemudian memilih secara acak satu medoid x dan satu object y yang bukan salah satu medoids. Bisakah dengan menggatikan x dengan y meningkatkan kriteria simpangan (error) mutlak? Jika ya, penggantian dilakukan. CLARANS melakukan pencarian acak seperti itu sebanyak m kali. Sekumpulan medoids yang dihasilkan setelah langkah sebanyak m dianggap sebagai optimum lokal. CLARANS mengulang proses acak ini sebanyak m kali dan menghasilkan optimal lokal terbaik sebagai hasil akhir.

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