Algoritma Rock

5 10 2009

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 (lihat tulisan saya tentang Similarity Measure). 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.

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.

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.


Actions

Information

10 responses

15 03 2014
agungplentong

pak yudi, saya ingin implenetasi algoritma rock untuk pemilihan spesiikasi komputer, tetapi banyak saya baca tentang rumus rock saya makin tidak paham, apakan pak yudi bersedia membantu saya memberikan contoh sederhana mengenai algoritma rock untuk pemilihan specifikasi komputer. email saya agungadk(at)gmail.com

19 06 2014
Yudi Agusta

Algoritma Rock adalah variasi dari clusering berbasis hirarki, dimana link yang digunakan untuk menghubungkan suatu data ke data yang lain, konsepnya sama dengan clustering berbasis hirarki tersebut.

Dalam algoritma Rock, data akan dianalisa satu dengan yang lainnya, yang berdekatan akan berusaha dimerge. Proses merge akan dlakukan secara berulang, sampai tidak ada data lagi yang perlu dianalisa atau dimerge. Untuk mengevaluasi data mana yang dekat dengan data yang mana, bisa menggunakan berbagai jenis konsep jarak.

Demikian dan bisa membantu.

29 06 2014
agungplentong

ada contoh hitungan manualnya gak mas? satu buah saja untuk referensi belajar dan buat programnya.

3 07 2014
Yudi Agusta

Saya jarang memberikan hitung-hitungan manual. Cukup mendalami prosedur dan rumus pencarian nilai-nilai yang diperlukan akan bisa menyelesaikan hitungan manual yang diperlukan. Karena metode seperti clustering sering diselesaikan dengan proses iterasi yang panjang, dan perhitungannya tidak bisa diselesaikan dalam satu tahap saja. Demikian dan semoga menjawab

6 07 2014
agungplentong

baik lah mas, terimakasih kalo begitu mudah mudahan ada pencerahan nanti hehehe

15 03 2011
sarasuartha

halo pak yudi, saya tertarik dengan tulisan bapak ttg algoritma rock ini, saya mw nanya apa ad contoh ttg algoritma rock ini, alnya saya masih baru blajar..biar lebih cpet mengerti…klu bapak ada contohnya tolng krim ke email saya ya pak…mksi pak…suksma

5 10 2011
Yudi Agusta

Contoh perhitungan saya tidak ada. Dicoba saja untuk melakukan clustering dengan 5 data dan menjadi dua kelompok misalnya, dan lakukan perhitungan menggunakan rumus di atas. Mungkin akan lebih mudah mendapatkan insight apa yang dilakukan oleh algoritma ini.

13 03 2011
Yasir mubarok

pak yudi, bisa minta tolong dikirimkan ke email saya, literatur (pdf atau doc) tentang algoritma rock dan algoritma c4.5…
terima kasih sebelumnya…

5 10 2011
Yudi Agusta

Saya dulu search melalui internet. Search Google dengan keyword “Rock Algorithm” langsung dapat pdfnya.

1 07 2010
Yus

nice info…..

go to my blog ok???

mas-yuz.blogspot.com

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: