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)2). [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(ks2 + 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.
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:
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
Dataset besar itu batasannya seperti apa ya Pak? terima kasih
ReplyDeletepengertian dataset besar relatof tergantung apakah mengacu ke jumlah "sample/record data" atau bisa juga mengacu ke jumlah "attributes" data. Kemudian yang disebut jumlah besar dan kecil juga tergantung dar area/bidang penggunaan (ecommerce, marketing, kedokteran, teknik, dll). Beberapa area dengan 10000 sample data sudah dibilang besar, tetapi beberapa area yang lain yang dimaksud besar adalah berisi jutaan sampel data.
DeleteSelain itu, juga tergantung dengan kemampuan komputasi harware/software dan waktu komputasi. Untuk kontek artikel di atas, yang dimaksud dengan jumlah besar mengacu pada kemampuan dan/atau waktu komputasi software/hardware sehingga perlu teknik tertentu untuk mengatasi problem komputasi dengan data besar.
adakah referensi khusus berupa buku dll yang dapat diacu untuk metode ini?
ReplyDeleteSalah satu buku yang bisa menjadi rekomendasi:
DeleteData Mining
Concepts and Techniques
Jiawei Han | Micheline Kamber | Jian Pei
Pak apa bisa kasih contoh seperti apa k-medoids tidak terlalu terpegaruh jika ada pencilan itu seperti apa ?
ReplyDelete