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)

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.

Locality Sensitive Hashing

Locality Sensitive Hashing (LSH) merupakan suatu metode untuk melakukan pengurangan jumlah dimensi dari data dengan dimensi tinggi, dimana pengurangan dilakukan dengan berbasis pada probabilitas. Ide dasarnya adalah melakukan hashing terhadap input data, sehingga data yang probabilitasnya tinggi untuk dikatakan sejenis akan di-map ke dalam bucket yang sama. Rendah tingginya probabilitas suatu data terhadap data yang lain, dihitung dengan jarak dari kedua data tersebut. Data yang dekat secara jarak akan mempunyai probabilitas tinggi, sedangkan data yang jauh secara jarak akan mempunyai probabilitas yang rendah. Data yang mempunyai probabilitas tinggi di-hash ke dalam satu bucket yang sama.

Locality Sensitive Hashing dapat juga digunakan untuk Clustering. Vector dari feature space dianggap himpunan dan ukuran similarity yang sering digunakan adalah Jaccard distance. Feature space dapat dianggap high-dimensional. Skema min-wise independent permutation (MinHash) kemudian digunakan untuk menyimpan item yang sejenis ke dalam satu bucket.

Persamaan yang sering digunakan adalah sebagai berikut:
* if d(p,q) \le R, then h(p) = h(q) (i.e.,p and q collide) atau probabilitas data untuk dibilang sama adalah tinggi,
* if d(p,q) \ge cR, then h(p) = h(q) dengan probabilitas yang rendah

Mining All Frequent Queries

Selama dua bulan, saya men-supervisi dua orang mahasiswa asal Perancis (Lucie Copin dan Nicolas Pecheur) tepatnya dari Politech Montpellier, yang melakukan pengembangan aplikasi untuk keperluan mining all frequent queries dari sebuah Data Warehouse. Basis teori yang digunakan untuk aplikasi tersebut adalah paper berikut:

Tao-Yuan Jen, Dominique Laurent, and Nicolas Spyratos (2008). Mining all frequent projection-selection queries in a star schema database. Proceedings of the 11th International Conference on Extending Database Technology: Advances in Database Technology, pp. 368-379, ACM New York, NY, USA.

Selama dua bulan, mereka berusaha untuk mengertikan teori dan algoritma yang dituangkan di dalam paper tersebut, berusaha menganalisanya untuk bisa dituangkan ke dalam suatu sistem aplikasi yang efektif, kemudian membuat laporan dan melakukan presentasi terhadap aplikasi yang mereka hasilkan. Teori dan algoritma yang dituangkan di dalam paper tersebut memang tergolong rumit, dan untuk bisa mengertikannya memerlukan kerja keras. Beruntungnya mereka datang berdua, sehingga mereka bisa mendiskusikan apa yang sulit untuk dicerna.

Dari apa yang tertuang di paper dan apa yang dijelaskan dari kedua mahasiswa ini, pada intinya aplikasi yang dibuat, akan mendapat masukan/input berupa sebuah data warehouse, dan kemudian menghasilkan keluaran/output berupa jenis-jenis query yang menghasilkan record dengan jumlah yang lebih banyak atau sama dengan threshold yang ditentukan.

Adapun beberapa proses yang dilakukan di dalam algoritma tersebut adalah proses men-generate queries, proses pruning dan proses scanning. Proses generate adalah proses untuk menghasilkan semua class query yang bisa dihasilkan dari keadaan yang ada sebelumnya. Proses pruning adalah proses untuk memotong anak class query yang parent querynya tidak frequent. Proses scanning adalah dari class query yang tersisa diperiksa query mana saja yang merupakan query dengan frekuensi di atas threshold.

Sistem ini dikembangkan oleh dua orang internship dari Perancis ini dalam 3 bulan. Waktu yang tidak panjang untuk mengertikan sekaligus untuk mengembangkan sistemnya. Hasil pengembangan sistem ini juga telah dipublikasikan dalam bentuk demonstration paper dengan bibliography sebagai berikut:

Lucie Copin, Nicolas Pecheur, Anne Laurent, Yudi Agusta, Budi Sentana, Dominique Laurent, Tao-Yuan Jen: DBFrequentQueries: Extraction de requêtes fréquentes. Jean-Gabriel Ganascia, Pierre Gançarski (Eds.): Extraction et gestion des connaissances (EGC’2009), ISBN 978-2-85428-878-0, Actes, Strasbourg. Page 499

Latent Class Cluster Analysis

Latent Class Cluster Analysis merupakan nama lain dari Mixture Modelling yang berusaha memodel data yang ada menjadi beberapa cluster dengan umumnya berbasiskan pada distribusi Normal dan menggunakan model tersebut di kemudian hari untuk menentukan class yang mana yang cocok untuk suatu data/record yang baru. Misalnya: suatu konsumen supermarket yang baru, kira-kira masuk ke kelompok yang mana dari beberapa kelompok yang sudah dimodel menggunakan Latent Class Cluster Analysis ini.

Latent Class Cluster Analysis ini merupakan turunan dari Latent Variable Analysis, dengan perkembangan yang bisa digambarkan sebagai berikut:

Category (Latent Variabel , Variabel Dimodel)
Factor Analysis (Continuous, Continuous)
Latent Class Analysis (Categorical, Categorical)
Latent Class Cluster Analysis/Latent Profile Analysis (Categorical, Continuous)
Latent Trait Analysis (Continuous, Categorical)

Latent Class Analysis identik juga dengan Naive Bayes Method, tetapi dikembangkan tanpa supervisi.