Simulated Annealing

Simulated Annealing merupakan metode searching yang memanfaatkan teori probabilitas untuk mencari global minimum dari suatu permasalahan optimasi. Simulated annealing umumnya digunakan untuk variabel yang bersifat categorical. Target dari metode ini adalah menemukan solusi bagus yang bisa diterima, bukan untuk mencari solusi yang terbaik. Nama annealing berasal dari keilmuan metallurgy, di mana proses tersebut akan berusaha mencari suatu posisi suhu tertentu yang optimal untuk mengurangi kerusakan dan menambah ukuran kristal di dalam suatu material.

Analogi dengan proses tersebut, metode Simulated Annealing ini juga berusaha untuk mencari solusi dengan berpindah dari solusi yang satu ke solusi yang lainnya, dan apabila solusi baru yang diuji mempunyai nilai fungsi ‘energy’ yang lebih kecil, maka solusi yang sedang diuji akan menggantikan solusi yang lama. Umumnya solusi baru yang dipilih merupakan solusi yang ada di dekat/sekitar solusi yang lama. Fungsi energi ini sangat bergantung pada parameter-parameter seperti parameter T (yang sering disebut dengan parameter “Temperature”). Metode ini merupakan adaptasi dari algoritma Metropolis-Hasting, yang merupakan suatu jenis metode Monte Carlo, untuk menciptakan sample state yang diperlukan.

Dalam metode ini, beberapa parameter terkait harus didefinisikan termasuk, the state space (umumnya berupa vector yang terdiri dari beberapa karakteristik), fungsi energy, prosedur untuk menciptakan solusi baru, fungsi probabilitas untuk menerima atau menolak, dan fungsi jadwal annealing dengan keterangan sebagai berikut:

- The state space umumnya ditentukan dengan melihat pada objek yang menjadi domain space pencarian.

- Fungsi energy umumnya menyesuaikan pada state space dan beberapa parameter kaitan lainnya.

- Prosedur untuk menciptakan solusi baru harus ditentukan seefisien mungkin dengan memikirkan karakteristik yang menjadi objek optimasi. Metode swapping antar karakteristik juga menjadi salah satu solusinya.

- Fungsi probabilitas untuk menerima atau menolak umumnya mempunyai bentuk tertentu dan bergantung pada apakah objek optimasi dapat merupakan fungsi probabilitas atau tidak. Fungsi probabilitas yang sering digunakan adalah fungsi probabilitas yang terkait dengan algoritma Metropolis-Hastings.

- Sedangkan untuk rate jadwal annealing umumnya ditentukan dengan melihat permasalahan yang ada pada objek optimasi dan ditentukan secara empiris.

Referensi:
[1] Kirkpatrick, S., Gelatt C. D., Vecchi M. P. (1983). Optimization by Simulated Annealing. Science. New Series 220 (4598): pp. 671 – 680. ISSN: 00368075.
[2] Metropolis N., Rosenbluth A. W., Rosenbluth M. N., Teller A. H., Teller E. (1953). Equations of State Calculations by Fast Computing Machines. Journal of Chemical Physics, 21 (6): pp. 1087 – 1092.

Latent Class Analysis

Latent Class Analysis merupakan turunan dari Latent Variable Analysis yang berusaha memodel data categorical ke dalam kelompok-kelompok. LCA ini pada dasarnya sama dengan Mixture Model tetapi dikhususkan untuk memecahkan masalah class analysis untuk variabel categorical. Karena metode ini hanya diterapkan untuk memodel variabel categorical, dependency antar variabel sering tidak diperhitungkan.

LCA ini juga sering digambarkan sebagai persamaan log linier dan memerlukan kegiatan pengestimasian parameter dan pemilihan model yang paling sesuai dengan data yang dimodel. Untuk mengingatkan, beberapa turunan dari Latent Variable Analysis antara lain:

CATEGORY (LATENT VARIABEL , VARIABEL YANG DIMODEL)
Factor Analysis (Continuous, Continuous)
Latent Class Analysis (Categorical, Categorical)
Latent Class Cluster Analysis/Latent Profile Analysis (Categorical, Continuous)
Latent Trait Analysis (Continuous, Categorical)

Jangan Menyerah – D’Masiv

Jangan Menyerah – D’Masiv. Very good lyrics and to hear it, make you feel better and stronger.

Lyric of Jangan Menyerah by D’Masiv

Tak ada manusia
Yang terlahir sempurna
Jangan kau sesali
Segala yang telah terjadi

Kita pasti pernah
Dapatkan cobaan yang berat
Seakan hidup ini
Tak ada artinya lagi

Reff 1:
Syukuri apa yang ada
Hidup adalah anugerah
Tetap jalani hidup ini
Melakukan yang terbaik

Tak ada manusia
Yang terlahir sempurna
Jangan kau sesali
Segala yang telah terjadi

Back to Reff 1

Reff 2:
Tuhan pasti kan menunjukkan
Kebesaran dan kuasanya
Bagi hambanya yang sabar
Dan tak kenal Putus asa

Back to Reff 1
Back to Reff 2

Selamat Galungan & Kuningan

,-”-,…,-”-,…,-”-,
!….:…!…..:…!…..:
!….*..!…..*…!…..*
!……..!………!
e”……e”……..e”
!……..!………!
!……..!………!

Rahajeng Nyanggra Rahina Galungan lan Kuningan, Dumogi Ida Sang Hyang Widhi Wasa Micayang Kerahayuan lan Kerahajengan Ring I Rage Sareng Sinamian.

Selamat Menyambut Hari Raya Galungan dan Kuningan, Semoga Tuhan Yang Maha Esa Memberikan Kesehatan dan Kesejahteraan Pada Kita Semua.

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 (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.