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

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.

SNOB

SNOB merupakan sebuah software mixture modelling yang berbasis teori Bayesian. Dilihat dari arti literalnya SNOB mempunyai arti yang kurang mengenakkan. Beberapa arti literal dari SNOB termasuk:

• a person who imitates, cultivates, or slavishly admires social superiors and is condescending or overbearing to others,
• a person who believes himself or herself an expert or connoisseur in a given field and is condescending toward or disdainful of those who hold other opinions or have different tastes regarding this field: a musical snob,
• a person who tends to patronize, rebuff, or ignore people regarded as social inferiors and imitate, admire, or seek association with people regarded as social superiors,
• a person who affects an offensive air of self-satisfied superiority in matters of taste or intellect,
• a person regarded as arrogant and annoying, and
• a person who admires people of high rank or social class, and despises those in a lower class etc than himself.

Software ini secara otomatis memodel data di dalam suatu dataset dan berusaha memberikan output berupa jumlah kelompok yang ada di dalam dataset tersebut, dan sekaligus karakteristik dari masing-masing kelompok yang dihasilkan. Karena kemampuanya yang seperti ini mungkin para pencetus dan pemrogramnya menamai software ini dengan nama SNOB.

Beberapa kelebihan SNOB antara lain dapat mengendalikan masalah overfitting yang sering ‘menghantui’ metode-metode pemodelan yang ada baik yang bertipe supervised maupun unsupervised. Salah satu asumsi yang masih menjadi permasalahan dalam memodel data dengan SNOB adalah bahwa variabel-variabel di dalam dataset dianggap tidak saling berkorelasi, padahal pada kenyataannya variabel-variabel di dalam suatu dataset umumnya saling berkorelasi satu dengan yang lainnya, walaupun hanya sedikit.