Algoritma Rock
Algoritma ROCK merupakan suatu algoritma clustering yang mengelompokkan data berbasiskan LINK antar data yang ada. ROCK sendiri adalah singkatan dari RObust Clustering using linKs. Data yang mempunyai tingkat hubungan (link) tinggi akan digabungkan ke dalam satu cluster, sedang yang mempunyai tingkat hubungan (link) yang kecil akan dipisahkan dari cluster dimana data tersebut dikelompokkan.
Cara menghitung tingkat hubungan (link) antar data dilakukan dengan memanfaatkan salah satu distance space yang ada seperti Eucledian Distance, Jaccard Distance atau distance space lain yang memungkinkan Untuk data transaksi supermarket, biasanya menggunakan Jaccard Distance. Dengan Jaccard Distance, natural data transaksi pada supermarket dapat didefinisikan dengan nilai ya atau tidak, sehingga proses clustering masih bisa dilaksanakan. Adapun rumus yang digunakan adalah:
g(C_i,C_j) = link[C_i, C_j] / ((n_i + n_j)^(1+2*f(theta)) – n_i^(1+2*f(theta)) – n_j^(1+2*f(theta)))
dimana:
n: jumlah data dalam suatu cluster
f(theta): fungsi yang menentukan jumlah tetangga dari data yang dievaluasi.
n: jumlah data dalam suatu cluster
f(theta): fungsi yang menentukan jumlah tetangga dari data yang dievaluasi.
Untuk transaksi supermarket, f(theta) yang digunakan adalah 1-theta/(1+theta), dimana theta ditentukan dengan menyesuaikan keadaan data.
Adapun prosedur yang diterapkan dalam clustering menggunakan ROCK algorithm ini sama dengan apa yang dilaksanakan pada saat melakukan clustering hirarki dengan prosedur agglomerative. Dari cluster sejumlah n (n sama dengan Jumlah Data), kemudian satu per satu di-merge sampai tidak lagi ditemukan link antar cluster atau jumlah cluster yang diinginkan tercapai.
Untuk menangani masalah data outliers, algoritma ROCK ini mengambil cara untuk menghapuskan data-data tersebut dari kumpulan data yang akan menjadi dasar proses clustering. Proses penghapusan kelompok-kelompok yang terdiri dari data outliers dilakukan setelah jumlah cluster yang tersisa dalam proses clustering sudah menjadi sekitar 1/3 dari jumlah data yang ada.
Some notes:
1. Specific criterion for terminating the process is not natural.
2. Handling outliers by eliminating the data is not natural too, since those data exist in real world.
1. Specific criterion for terminating the process is not natural.
2. Handling outliers by eliminating the data is not natural too, since those data exist in real world.
Reference:
Sudipto Guha, Rajeev Rastogi, and Kyuseok Shim (2000). ROCK: A Robust Clustering Algorithm for Categorical Attributes. Proceedings of the 15th International Conference on Data Engineering.
Sudipto Guha, Rajeev Rastogi, and Kyuseok Shim (2000). ROCK: A Robust Clustering Algorithm for Categorical Attributes. Proceedings of the 15th International Conference on Data Engineering.
Sumber:yudiagusta.wordpress.com
