Metode Clustering: K-means dengan menggunakan Evidence Accumulation

Kelemahan K-means

K-means merupakan salah satu algoritma clustering yang sangat simple. Diberikan data, dan jumlah cluster yang ingin dibuat. Langkah pertama dari K-means adalah dengan menentukan pusat dari setiap cluster secara acak. Setelah itu algoritma ini akan meng-update setiap pusat cluster. Algoritma akan berhenti ketika pusat cluster tidak berubah setelah diupdate. Untuk detilnya bisa dilihat di sini.

Tentu saja, kita hanya bisa menerka-nerka berapakah K yang cocok untuk data yang sedang diproses. K yang terlalu kecil akan mengakibatkan beberapa natural cluster akan digabung kedalam satu grup. Di lain pihak, K yang terlalu besar mengakibatkan overclustering. Lalu, meskipun kita telah mengetahui K yang tepat, hasil dari K-means tidak selalu sama dan tidak selalu yang diinginkan. Terutama untuk grup yang tidak berbentuk lingkaran.

Mengapa lingkaran? Kalau kita perhatikan K-means memakai mean dan standard deviation sebagai parameter yang mendeskripsikan pusat cluster. Dengan menggunakan Mean dan standard deviation maka secara tidak langsung kita memodelkan bahwa pusat cluster mengikuti distribusi Gaussian yang notabene berbentuk seperti lingkaran.

Pertanyaan-pertanyaan yang diatas inilah yang akan selalu menghantui kita ketika K-means dipergunakan dalam solusi pengolahan citra.

Evidence Accumulation

Dalam paper mereka, Fred dan Jain menggunakan intuisi bahwa: data yang termasuk dalam cluster natural biasanya akan lebih sering di-cluster bersama dalam cluster yang sama. Misalkan, katakanlah kita memiliki 4 data A,B,C, dan D yang tergabung dalam 2 cluster I dan II. A dan B ada pada I dan C dan D ada pada II. Kalau kita jalankan K-means berkali-kali, kemungkinan A dan B dikelompokan bersama lebih sering ketimbang B dan C. Katakanlah pada contoh kali ini, kita menjalankan K-means 100 kali, dan menghitung berapa kali dua data dikelompokan dalam satu cluster. Berikut ini adalah hasilnya:

	A	B	C	D
A	0	65	10	20
B	65	0	5	13
C	10	5	0	70
D	20	13	70	0

Kalau table (co_assoc)di atas dinormalisasi sedemikian sehingga semakin besar nilai frekuensi, akan semakin kecil nilainya, maka kita mendapatkan affinity matrix yang baru. Affinity matrix ini akan merepresentasikan "jarak"/distance baru antara dua data. "Jarak" ini akan mendekatkan data yang sering dikelompokkan secara bersama dan menjauhkan data yang jarang dikelompokkan bersama. Dapet idenya? Yap sangat mudah dan menarik.

Langkah berikutnya adalah, meng-cluster data dengan menggunakan algoritma clustering agglomerative single/average link dan affinity matrix yang baru.

Seperti yang kita ketahui bahwa hasil dari algoritma agglomerative clustering adalah sebuah dendrogram. Untuk mendapatkan hasil akhir, algoritma Evidence accumulation K-means menghitung cluster lifetime dari dendrogramyang telah dibentuk. Cluster lifetime tertinggi akan menjadi nilai threshold untuk dendrogram. Lalu apa maksudnyadendrogram di threshold? Dengan kita men-threshold dendrogram, kita akan mendapakan cluster level. Setiap levelmempunyai jumlah cluster yang unik. Cluster lifetime didefinisikan sebagai jarak antara dua consecutive cluster levels.  Untuk lebih detilnya, silahkan dibaca rujukan yang diberikan pada tautan di atas.

Secara singkat, algoritma ini akan menjalankan algoritma K-means berulang kali dengan K yang dipilih secara acak. Setelah itu matrix co_assoc dihitung. Lalu co_assoc dijadikan affinity matrix yang baru. Dengan matriks ini algoritma ini akan menjalankan algoritma single/average link agglomerative clustering.

Percobaan kecil Untuk melihat kekuatan dari metode clustering ini, marilah kita lihat pada dataset yang sederhana yang memiliki data dua dimensi.

Jelas, kalau kita lihat pada data di atas, dataset tersebut memiliki 3 grup yang berbeda. Dua grup mempunyai bentuk seperti setengah lingkaran, dan satu grup yang lainnya berbentuk titik besar. Berikut ini adalah hasil dari K-means dengan K = 3.

Sebanyak apapun kita jalankan K-means, hasil dari algoritma ini tidak akan dapat mencapai hasil yang diinginkan. Sebaliknya, algoritma evidence accumulation clustering dapat membuat hasil sebagai berikut:

Perfect?! Yak anda benar. algoritma ini berhasil menghasilkan clustering yang tepat dan sesuai dengan harapan. Jangan lupa juga, tidak seperti K-means, algoritma ini menebak jumlah cluster yang ada secara otomatis. Hebat? sangat hebat!

Kelemahan

Salah satu kelemahan yang saya temukan adalah, algoritma ini membutuhkan waktu yang lebih lama dari K-means. Well, ini merupakan konsekuensi logis dari algoritma ini. Lebih jauh lagi, memory space yang dibutuhkan jauh lebih besar karena algoritma ini membutuhkan matriks co_assoc. Ukuran matriks ini adalah pangkat dua dari jumlah data yang ada.

Selain dari itu, algoritma ini memiliki hasil yang sangat impresif!