Mixture Model

Mixture modelling (Mixture Modeling) adalah suatu metode penganalisaan data atau data mining yang juga disebut dengan istilah-istilah lain seperti clustering, intrinsic classification dan numerical taxonomy. Metode ini memodel atau mengelompokkan data-data di dalam suatu dataset menjadi kelompok-kelompok data yang sebelumnya tidak terdifinisikan. Di dalam tulisan ini, metode yang diulas adalah pengelompokan data yang memodel suatu distribusi statistik bercampur dengan distribusi statistik yang lain dalam bentuk mixture (penjumlahan berproporsi). Penganalisaan data menggunakan mixture modelling menghasilkan analisa berupa jumlah kelompok di dalam model tersebut, persentase data di dalam setiap kelompok relatif terhadap jumlah keseluruhan data (mixing proportion), parameter yang menerangkan setiap kelompok yang ditemukan dan keterangan data-data yang tercakup di dalam setiap kelompok. Mixture modelling dirumuskan dengan persamaan sebagai berikut:

f(x|M,Pi_1,…,Pi_M-1,Theta_1,…,Theta_M) = SUM(m=1 to M) Pi_m x f_m(x|Theta_m)

Dengan:

• M : Jumlah kelompok
• Pi_m : Mixing proportion kelompok ke-m
• Theta_m : Parameter kelompok ke-m
• f_m(x|Theta_m) : fungsi likelihood dari kelompok ke-m

Dalam melakukan mixture modelling, penentuan jumlah kelompok yang paling sesuai untuk dataset yang sedang dianalisa merupakan masalah yang cukup komplek. Untuk bisa melaksanakan proses ini, keseimbangan antara kesempurnaan suatu model dengan pas tidaknya suatu model terhadap data yang dianalisa harus benar-benar terjaga. Dengan kata lain, model yang dipilih untuk suatu dataset haruslah cukup sempurna agar bisa mencakup semua informasi yang terkandung di dalam dataset tersebut, tetapi tidak harus terlalu sempurna agar tidak mengalami permasalahan over-fit.

Banyak teori yang telah digunakan dalam mengembangkan metode ini, termasuk diantaranya Minimum Message Length (MML), Maximum Likelihood (ML), Akaike Information Criterion (AIC), Schwarz’s Bayesian Information Criterion (BIC), Maximum A Posterior (MAP) dan Markov Chain Monte Carlo (MCMC). Teori-teori ini juga telah diimplementasikan menjadi paket-paket program pengelompokan data seperti SNOB yang menggunakan MML dalam proses pengestimasian parameter dan pemilihan model, EMMIX yang menggunakan ML untuk pengestimasian parameter dan AIC serta BIC untuk pemilihan model dan MCLUST yang juga menggunakan ML untuk pengestimasian parameter dan BIC untuk pemilihan model.

Berikut ini beberapa kumpulan link yang terkait dengan mixture modelling:
David Dowe Mixture Modelling Page memuat link yang lengkap terkait Mixture Modelling dan orang-orang yang menelitinya. David Dowe dengan beberapa peneliti lainnya mengembangkan program Mixture Modelling Snob yang menggunakan prinsip Minimum Message Length dalam pemodelannya. Beberapa peneliti lainnya (berikut software yang dikembangkan) termasuk Geoff McLachlan (EMMIX), Peter Cheeseman (AutoClass), Chris Fraley (MClust), Murray Jorgensen (MultiMix) dan peneliti-peneliti lainnya.

Gaussian Mixture dengan EM Algorithm

Expectation Maximisation (EM) algorithm adalah salah satu alternatif algoritma yang banyak digunakan dalam melakukan pemodelan mixture (mixture modelling). Penjelasan singkat mengenai EM Algoritm dapat dilihat di posting ini.

Dalam sebuah model Gaussian Mixture, data sebanyak m (y_1,…, y_m) diasumsikan berasal dari satu atau lebih distribusi Gaussian (diasumsikan sejumlah n). Kalau z_j diasumsikan sebagai distribusi Gaussian dari mana y_j berasal, maka probabilitas dari suatu y untuk berasal dari distribusi Gaussian tersebut dirumuskan sebagai:

p(y|z=i,theta) = N(mu_i, sigma_i)
= (2*PI)^(D/2) * |sigma_i|^(-1/2) * exp(-(y-mu_i)^T*sigma_i^(-1)*(y-mu_i)/2)

Tujuannya di sini adalah mengestimate parameter yang tidak diketahui theta = {mu_1, …,mu_n,sigma_1,…,sigma_n,p(z=1),…,p(z=n)}

Expectation Step

Dalam E-Step, dilakukan pengestimasian nilai z, dengan kondisi yang terdapat di dalam sample yang ada dan nilai estimasi parameter yang didapatkan dari tahap M-Step sebelumnya dengan rumus seperti berikut ini:

p(z_j=i|y_j,theta_t) = p(z_j=i,y_j|theta_t)/p(y_j|theta_t)
=p(y_j|z_j=i,theta_t)*p(z_j=i|theta_t)/SUM(k=1ton)(p(y_j|z_j=k,theta_t)*p(z_i=k,theta_t))

Maximisation Step

Dalam M-Step, kita perlu untuk memaksimalkan expected log-likelihood dari probability density function (pdf) sebagai berikut:

Q(theta) = E_z [ln TIMES(j=1 to m) p(y_j,z|theta)|y_j)]
= E_z [SUM (j=1 to m) ln p(y_j,z|theta)|y_j]
= SUM (j=1 to m) E_z [ln p(y_j,z|theta)|y_j]
= SUM (j=1 to m) SUM (i=1 to n) p(z_j = i|y_j,theta_t) ln p(z_j=i,y_j|theta)
= SUM (j=1 to m) SUM (i=1 to n) p(z_j = i|y_j,theta_t) ln (p(y_j|z_j=i,theta)*p(z_j=i| theta))

Di sini, terdapat contsrain :

SUM(i=1 to n) p(z_j = i|theta) = 1

Dengan menggunakan Lagrange Multiplier, pdf di atas dapat dikembangkan menjadi:

L(theta) = (SUM (j=1 to m) SUM (i=1 to n) p(z_j = i|y_j,theta_t)
* (-D*ln(2*PI)-ln|sigma_i|/2 - (y-mu_i)^T*sigma_i^(-1)*(y-mu_i)/2 + ln (p(z_j=i|
theta)))) + lambda (SUM(i=1 to n) p(z_j = i|theta) - 1)

Estimasi terhadap theta_(t+1) didapatkan dengan mencari nilai maksimum dari pdf terhadap parameter yang diestimasi dimana dL(theta)/dtheta = 0

Dari hasil penurunan didapatkan (selengkapnya dapat dilihat di wikipedia), estimasi parameter mu_i, sigma_i dan p(z_j=i|theta) dihitung dengan rumus sebagai berikut :

mu_i = (SUM (j=1 to m) p(z_j = i|y_j,theta_t) * y_j) / SUM (j=1 to m) p(z_j = i|y_j,theta_t)

sigma_i = (SUM (j=1 to m) p(z_j = i|y_j,theta_t)*(y-mu_i)*(y-mu_i)^T) / SUM (j=1 to m) p(z_j = i|y_j,theta_t)

p(z_j=i|theta) = SUM (j=1 to m) p(z_j = i|y_j,theta_t) / m

Referensi:
Dempster A., Laird N., and Rubin D. (1977). Maximum Likelihood From Incomplete Data Via the EM Algorithm. Journal of the Royal Statistical Society, Series B, 39(1): 1-38.

Modelling Criteria

Likelihood Ratio
Under Construction.

Akaike Information Criterion (AIC)
Under Construction

Schwarz’s Bayesian Information Criterion (BIC)
Under Construction