Jurnal Sistem dan Informatika Vol. 1 (Agustus 2005), 1 - 16
Mixture Modelling Menggunakan Prinsip Minimum Message Length Yudi Agusta, PhD Bali Data Mining Center, STIKOM BALI, Denpasar, Bali Abstraksi: Mixture Modelling yang dikenal juga dengan istilah Clustering merupakan metode pengklasifikasian data tanpa arahan yang mengelompokkan data-data di dalam suatu dataset menjadi satu kelompok atau lebih, yang sebelumnya tidak terdifinisikan. Ada dua proses utama yang diperlukan dalam melakukan pengelompokan data menggunakan metode ini: pertama, mengestimasi parameter-parameter yang digunakan untuk menjelaskan tiap kelompok yang dihasilkan dan kedua, mencari model pengelompokan yang paling sesuai untuk dataset yang dianalisa. Di dalam pengembangan metode penganalisaan data berbasis mixture modelling ini, prinsip Minimum Message Length (MML) dapat diaplikasikan secara bersamaan baik dalam pengestimasian parameter dan pencarian model. Di dalam tulisan ini, metode mixture modelling untuk penganalisaan data kontinyu univariate dan multivariate tidak berkorelasi akan dikembangkan. Metode ini juga dilengkapi dengan fasilitas untuk mengamati keberadaan outliers di dalam kelompokkelompok yang dihasilkan. Kata Kunci: Minimum Message Length (MML), Mixture Modelling, Clustering, Pengestimasian Parameter, Pencarian Model, Data Kontinyu Univariate, Outliers
1. Pendahuluan Mixture modelling[1,8,9,10,16], yang juga disebut dengan istilah-istilah lain seperti clustering[2,3,7,16], intrinsic classification[15] dan numerical taxonomy, 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, parameter yang menerangkan setiap kelompok yang ditemukan dan keterangan data-data yang tercakup di dalam setiap kelompok. 1
Jurnal Sistem dan Informatika Vol. 1 (Agustus 2005), 1 - 16 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)[14], Maximum Likelihood (ML), Akaike Information Criterion (AIC)[4], Schwarz’s Bayesian Information Criterion (BIC)[11], Maximum A Posterior (MAP)[5] dan Markov Chain Monte Carlo (MCMC)[9]. Teori-teori ini juga telah diimplementasikan menjadi paket-paket program pengelompokan data seperti SNOB[14,15,17] yang menggunakan MML dalam proses pengestimasian parameter dan pemilihan model, EMMIX[9] yang menggunakan ML untuk pengestimasian parameter dan AIC serta BIC untuk pemilihan model dan MCLUST[6] yang juga menggunakan ML untuk pengestimasian parameter dan BIC untuk pemilihan model. Di dalam tulisan ini, Minimum Message Length (MML) [14] digunakan secara bersamaan dalam pengestimasian parameter dan pemilihan model. Jenis data yang bisa diolah menggunakan metode pengelompokan data seperti ini dapat berupa data berkategori univariate dan multivariate, data kontinyu univariate dan multivariate baik yang berkorelasi maupun tidak. Sebagai salah satu contoh pengembangan metode mixture modelling menggunakan prinsip MML ini, sebuah metode untuk menganalisa data kontinyu univariate dan multivariate tidak berkorelasi akan dikembangkan di dalam tulisan ini. Selain itu, keberadaan outliers di dalam kelompok-kelompok yang ditemukan di dalam pemodelan juga akan ditelusuri. Untuk keperluan itu, dua distribusi statistik akan digabungkan di dalam pengembangan metode ini. Mereka adalah distribusi Normal dan distribusi Student t. Mixture modelling menggunakan kedua distribusi ini sudah dibahas secara terpisah dan menggunakan metode yang berbeda-beda[1,2,3,7,14,15,16,17]. Kedua distribusi ini merupakan distribusi-distribusi yang berbentuk lonceng. Perbedaan di antara kedua distribusi ini terletak pada kemampuan mereka untuk memodel data yang mengandung outliers. Distribusi Student t mempunyai satu parameter tambahan dibandingkan distribusi Normal. Parameter ini disebut dengan degree of freedom (ν). Degree of freedom (ν) yang kecil membuat kedua sisi pada distribusi Student t tersebut makin tebal dan panjang, sedangkan degree of freedom (ν) yang besar dan menuju tidak terhingga akan menyerupai distribusi Normal dengan sisi yang tipis. Dengan kelebihan ini distribusi Student t sering digunakan untuk mengidentifikasi apakah data dalam suatu kelompok yang ditemukan mengandung outliers atau tidak. Secara keseluruhan tulisan ini menjelaskan kedua proses yang diperlukan dalam melakukan pengembangan metode mixture modelling menggunakan prinsip MML. Bagian 2. menjelaskan tentang teori dasar pengembangan metode pengestimasian parameter menggunakan MML. Bagian 3. menjelaskan penyusunan message length yang digunakan 2
Jurnal Sistem dan Informatika Vol. 1 (Agustus 2005), 1 - 16 dalam proses pencarian model. Bagian 4. menggambarkan pengembangan metode pengestimasian parameter untuk data kontinyu univariate dimana keberadaan outliers di dalam setiap kelompok juga dianalisa. Tiga distribusi statistik tercakup dalam pemodelan ini yaitu: distribusi Normal, distribusi Student t dan distribusi multi-nomial. Distribusi statistik yang terakhir diperlukan untuk memodel proporsi data yang terdapat di dalam setiap kelompok yang terdapat di dalam model yang ditemukan. Bagian 5. dan 6. masing-masing menjelaskan metode alternatif dan metode pengevaluasian yang sering digunakan dalam mengevaluasi metode pengelompokan data. Bagian 7. memuat hasil-hasil pemodelan dan perbandingan-perbandingan terhadap pemodelan yang dikembangkan dengan teori yang lain. Bagian 8. memberikan kesimpulan atas pengembangan yang diilustrasikan dalam tulisan ini.
2. Pengestimasian Parameter Menggunakan MML Minimum Message Length (MML)[14] merupakan teknik pengestimasian sebuah titik dan pemilihan model berbasis teori Bayesian dan teori informasi[12] serta bersifat invariance. Ide dasar dari MML adalah menemukan sebuah model yang dapat meminimalkan total dari message length yang terdiri dari dua bagian dimana bagian pertama berisikan encoding untuk model yang terpilih dan bagian kedua berisikan encoding untuk data yang dikompresi berdasarkan model terpilih tersebut. Misalkan data yang sedang dianalisa dilambangkan dengan D dan hipotesa yang sedang ditinjau diberi lambang H dimana prior probability untuk suatu hipotesa H tersebut dilambangkan dengan P(H). Menggunakan teori Bayesian, masalah dalam melakukan pengestimasian suatu titik dan pemilihan model dapat dikatakan sebagai masalah yang memaksimalkan posterior probability P(H)⋅P(D|H). Dari sudut pandang teori informasi, suatu kejadian, dengan probability untuk terjadi adalah p, dapat di-encode dengan message yang panjangnya l = -log2 p bits. Sehingga masalah tersebut di atas dapat disamakan dengan meminimalisasikan MessLen
= − log 2 ( P ( H )) − log 2 ( P ( D | H ))
(1)
dimana bagian pertama dari persamaan (1) di atas merupakan message length dari hipotesa H untuk terjadi dan bagian kedua dari persamaan merupakan message length dari data yang di-encode berdasarkan hipotesa yang ditinjau. Dalam topik permasalahan yang dibahas dalam makalah ini, MML digunakan untuk melakukan pemilihan model pengelompokan dimana setiap kelompok di dalam model tersebut didefinisikan menggunakan dua jenis distribusi yaitu distribusi Normal dan distribusi Student t. Oleh karena itu, permasalahan ini memerlukan pengestimasian parameter-parameter yang tercakup dalam kedua distribusi statistik tersebut. Disamping itu, dalam mengembangkan metode pengelompokan data yang berbasis mixture (penjumlahan berproporsi), sebuah distribusi statistik yaitu distribusi multi-nomial juga diperlukan untuk menerangkan proporsi data yang tercakup di dalam masing-masing kelompok. Untuk
3
Jurnal Sistem dan Informatika Vol. 1 (Agustus 2005), 1 - 16 pengestimasian parameter-parameter tersebut, disini digunakan MML approximation yang dikembangkan pada tahun 1987 oleh Wallace and Freeman[18]. Misalkan data yang sedang dianalisa dilambangkan dengan x, parameter yang akan r r diestimasi dilambangkan dengan θ , maka distribusi untuk prior probability pada θ dapat r r dilambangkan dengan h(θ ) , likelihood function dilambangkan dengan f ( x | θ ) , negative r log-likelihood function L = − log f ( x | θ ) dan Fisher information – yang merupakan determinan dari matrik nilai expected second derivatives dari negative log-likelihood-nya dilambangkan dengan[18]:
r ∂ 2 L F (θ ) = det E r r ∂θ ∂θ ′
(2)
Berpijak pada persamaan (1), dan dengan mengembangkan negative rlog-likelihood, L, sampai ke term kedua dari Taylor series di wilayah sekitar parameter θ , maka message length dapat dihitung menggunakan rumus sebagai berikut:
h(θ ) + L + D = − log h(θ ) f ( x | θ ) + D (1 + log κ ) MessLen = − log D κ D F (θ ) 2 F (θ ) 2 D
(3)
dimana D merupakan jumlah parameter yang diestimasi dan κD merupakan konstanta lattice r yang berdimensi D dengan κ1 = 1/12 dan κD ≤ 1/12. Estimasi dari parameter θ bisa didapatkan dengan meminimalisasikan persamaan (3). Dengan memikirkan bahwa distribusi Normal dan Student t merupakan distribusi kontinyu, maka coding yang terhingga untuk message yang diturunkan, dapat diperoleh dengan memperhitungkan bahwa semua data kontinyu dan parameter-parameter yang tercakup, hanya perlu dicatat sampai tingkat presisi yang terbatas – dimana dalam praktiknya dibuat sampai suatu tingkat presisi – ε. Dengan pemikiran ini, konstanta sebesar Nlog(1/ε) harus ditambahkan ke dalam persamaan message length di atas, dimana N merupakan jumlah data yang tercakup. Disamping itu, untuk sembarang attribute kontinyu, disini diasumsikan bahwa parameter sebaran yang biasanya dilambangkan dengan σ bernilai minimal sama dengan 0.4ε.
3. Mixture Modelling Menggunakan MML Untuk dapat mengaplikasikan MML dalam memecahkan permasalahan pengelompokan data, message yang terdiri dari dua bagian yang berisikan informasi mengenai model pengelompokan data tersebut perlu untuk dibangun. Sesuai dengan teori yang dijelaskan pada Bagian 2., hipotesa dari model pengelompokan data terdiri dari beberapa bagian message yang dapat dipecah seperti berikut ini[1,2,3,14,15,16,17]: 4
Jurnal Sistem dan Informatika Vol. 1 (Agustus 2005), 1 - 16 1a. Jumlah kelompok: Mengasumsikan bahwa semua jumlah kelompok (misalnya, dari 1 sampai 100) mempunyai kemungkinan yang sama untuk menjadi jumlah kelompok hasil pengelompokan data. Dalam hal ini, message bagian ini dimodel menggunakan distribusi uniform dengan batas wilayah tertentu. 1b. Proporsi setiap kelompok: Dengan memikirkan bahwa proporsi dari masing-masing kelompok di dalam model pengelompokan dengan jumlah kelompok sebesar M, hal ini adalah sama dengan kondisi dari distribusi multi-nomial dengan jumlah state sama dengan M. 1c. Untuk setiap kelompok, parameter dari distribusi statistik yang digunakan untuk menjelaskan masing-masing attribute dalam kelompok tersebut: Dalam hal ini, attribute dalam suatu kelompok dimodel menggunakan satu atau lebih distribusi statistik. 1d. Untuk setiap data: Kelompok ke mana data tersebut dikelompokkan. Setelah message bagian pertama dibangun, bagian kedua dari message akan berisikan encoding dari data sesuai dengan model yang telah diturunkan pada message bagian pertama. Karena tujuan utama dari MML adalah untuk menemukan model yang meminimalisasikan message length, maka kita tidak perlu untuk benar-benar membangun kedua bagian message tersebut. Dengan kata lain, kita hanya perlu untuk menghitung panjang message yang digunakan untuk merepresentasikan sebuah model dan memilih model yang memberikan panjang message yang terpendek.
4. Pemodelan Data Kontinyu Univariate Di dalam tulisan ini, sebuah metode pengelompokan data untuk data kontinyu univariate dan multivariate tidak berkorelasi dikembangkan sebagai contoh pengimplementasian MML dalam pengembangan metode pengelompokan data. Dalam hal ini, pemodelan attribute di dalam satu kelompok dilakukan dengan menggunakan distribusi statistik yang bersifat kontinyu. Salah satu feature yang juga ditinjau dalam tulisan ini adalah keberadaan outliers pada masing-masing attribute di dalam suatu kelompok. Untuk keperluan tersebut, distribusi statistik yang digunakan di sini adalah distribusi Normal dan distribusi Student t. Seperti yang telah dijelaskan dalam bagian sebelumnya, untuk memodel proporsi jumlah data yang terdapat pada masing-masing kelompok digunakan distribusi multi-nomial dengan jumlah state yang ditinjau adalah sebanyak kelompok yang terdapat di dalam model yang ditinjau. Oleh karena itu, di sini perlu disediakan metode pengestimasian parameterparameter yang tercakup di dalam ketiga distribusi statistik yang disebutkan di atas. Rincian penurunan metode pengestimasian parameter-parameter yang tercakup di dalam ketiga distribusi statistik tersebut dijelaskan secara berturut-turut pada bagian di bawah ini. 4.1. Distribusi Multi-nomial
Untuk distribusi multi-nomial dengan jumlah state M (dan dengan jumlah sample N), likelihood function dari distribusi ini adalah sebagai berikut: 5
Jurnal Sistem dan Informatika Vol. 1 (Agustus 2005), 1 - 16 f (n1 , n2 , L , n M | p1 , p 2 ,L , p M ) = p1n1 p xn2 L p MnM
(4)
dimana p1 + p 2 + L + p M = 1 , dan untuk semua m: p m ≥ 0 dan n1 + n2 + L + n M = N .
Dengan menggunakan persamaan (2) tentang Fisher information di atas, dapat diketahui bahwa F ( p1 , p 2 , L, p M ) = N ( M −1) / p1 p x L p M [1,2,3,14,15,16,17].
r Dengan mengasumsikan prior uniform h( p) = ( M − 1)! di atas wilayah berdimensi M-1 dari hyper-volume 1 /( M − 1)! , dan meminimalisasikan persamaan message length (3), estimasi terhadap parameter pˆ m dengan menggunakan MML didapat dengan rumus berikut ini: pˆ m = (nm + 1 / 2) /( N + M / 2)
(5)
Mensubstitusikan persamaan likelihood function seperti pada persamaan (4), prior probability yang ditentukan, dan Fisher information yang dijelaskan di atas, ke dalam persamaan (3) memberikan message terdiri dari dua bagian dengan panjang: − log( M − 1)!+ (( M − 1) / 2)(log( Nκ M −1 )+ 1) − ∑m =1 (nm + 1 / 2) log pˆ m M
(6)
4.2. Distribusi Normal
Untuk distribusi Normal dengan likelihood function: f ( x | µ,σ ) =
1 2π σ
e
−
( x−µ )2 2σ 2
(7)
Fisher information-nya adalah sebagai berikut[1,2,3,14,15,16,17]: F ( µ , σ ) = 2 N 2 / σ 4 or F ( µ , σ 2 ) = N 2 / 2(σ 2 ) 3
(8)
Dengan mengasumsikan prior uniform pada µ di atas range terbatas R dan prior 1/σ pada σ (yang sama artinya dengan prior uniform pada logσ dan sama juga artinya dengan prior 1/σ2 N pada σ2) pada range e −4 , e 4 , dan juga melakukan setting s 2 = ∑i =1 ( xi − x ) 2 , serta dengan
[
]
meminimalisasikan persamaan (3), maka estimate untuk parameter µ dan σ menggunakan MML dapat dihitung dengan rumus sebagai berikut:
µˆ MML = x =
6
(∑ x )/ N , σˆ N
i =1
i
2 MML
= s 2 /( N − 1)
(9)
Jurnal Sistem dan Informatika Vol. 1 (Agustus 2005), 1 - 16 Untuk range bagi prior pada σ yang telah dinyatakan di atas, kita perlu untuk menormalisasikan prior tersebut dengan nilai sebesar 0.125 dan untuk range R R R = − , bagi prior pada µ, dalam prakteknya kita memilih range dengan ukuran 2 2 max{10, perbedaan antara data terkecil dan terbesar dari keseluruhan data yang dianalisa}.
4.3. Distribusi Student t
Distribusi Student t dengan mean µ, standard deviation σ, dan degree of freedom ν merupakan sebuah distribusi kontinyu yang mengeneralisasikan beberapa distribusi statistik yang lain seperti distribusi Normal (ν = ∞) dan distribusi Cauchy (ν = 1). Untuk ν yang besar (>100), distribusi Student t dapat diaproksimasikan menggunakan distribusi Normal. Makin kecil nilai ν, makin panjang sisi dari distribusi Student t ini. Menggunakan keistimewaan ini, distribusi Student t sering digunakan untuk memodel data yang mengandung observasi yang tidak biasa seperti outliers. Distribusi ini mempunyai likelihood function seperti berikut ini:
f ( x | µ , σ ,ν ) =
(ν + 1) (ν +1) ) 2 − 2 µ − 1 ( x ) 2 1+ ν σ νσ 2 πν Γ( ) 2
Γ(
(10)
dimana Γ(x) adalah fungsi Gamma yang dirumuskan sebagai berikut:
∞
Γ( x) = ∫ t x −1e −t dt , dimana ψ ( x) = dΓ( x) / dx dan ψ (1) ( x) = d 2 Γ( x) / dx 2 0
(11)
Untuk sembarang integer positif, x, Γ( x) = ( x − 1)!. Untuk x yang besar, penghitungan langsung dari definisi asli fungsi Gamma di atas menghasilkan angka yang sangat besar. Dengan mensubstitusi perbandingan kedua fungsi Gamma di dalam likelihood function dari distribusi Student t di atas menggunakan rumus berikut ini:
1 Γ( J + ) 5 2 ≈ J (1 − 1 + 1 + + O(| J | −3 )) 2 3 8 J 128 J Γ( J ) 1024 J
(12)
maka likelihood function dari distribusi Student t dapat diaproksimasikan menggunakan persamaan di bawah ini:
7
Jurnal Sistem dan Informatika Vol. 1 (Agustus 2005), 1 - 16 1 1 5 1 1 (x − µ)2 + + f ( x | µ , σ ,ν ) = (1 − ) 1 + 4ν 32ν 2 128ν 3 2π σ νσ 2
−
(ν +1) 2
(13)
Pendekatan ini berbeda dengan pendekatan di dalam paper terdahulu[3]. Di dalam tulisan ini, untuk parameter ketiga dari distribusi Student t yaitu parameter ν (degree of freedom), diasumsikan mempunyai nilai yang diketahui. Untuk keperluan ini, Fisher information pada saat ν dianggap sebagai parameter yang diketahui adalah sebagai berikut[1,3]: F (µ ,σ ) =
2 N 2ν (ν + 1) σ 4 (ν + 3) 2
(14)
Mengasumsikan prior uniform bagi µ di atas range terbatas R dan prior 1/σ bagi σ di atas range e −4 , e 4 , estimasi bagi parameter yang tercakup di dalam distribusi Student t menggunakan MML, yaitu µ dan σ dihitung dengan meminimalisasikan persamaan (3) terhadap setiap parameter yang tercakup. Karena tidak ada sufficient statistics yang dapat digunakan untuk mengestimasi parameter-parameter tersebut dan karena parameter yang satu terkait dengan parameter yang lain, maka estimasi dilakukan dengan melakukan binary search melalui setting ∂MessLen / ∂θ = 0 dan mengulang proses search tersebut sampai tingkat akurasi yang diinginkan tercapai.
[
]
5. Teori Alternatif Selain MML, ada beberapa teori alternatif yang sering digunakan untuk melakukan pengembangan metode pengelompokan data berbasis mixture ini. Beberapa di antaranya telah digunakan dalam mengembangkan paket program pengelompokan data antara lain EMMIX[9] yang menggunakan Maximum Likelihood (ML) untuk melakukan pengestimasian parameter dan AIC serta BIC untuk pemilihan model. MCLUST[6] juga menggunakan ML untuk mengestimasi parameter dan BIC untuk memilih model. Berikut ini akan dijelaskan secara ringkas mengenai teori-teori alternatif ini. 5.1. Maximum Likelihood (ML)
Sesuai dengan namanya, ML method melakukan pengestimasian parameter dengan memaksimalkan likelihood function dari data yang sedang dianalisa, terhadap parameter dari distribusi statistik yang digunakan untuk memodel data tersebut. Atau kalau ditinjau dari sisi lain, metode ini berusaha meminimalisasikan negative logarithm dari likelihood function data yang sedang di analisa. Teori ini mempunyai keunggulan dalam hal waktu pencarian estimasi. Walaupun, estimasi dari parameter yang tercakup tidak bisa dicari secara langsung melalui persamaan, pengestimasian masih bisa dilakukan dengan menggunakan metode Expectation Maximisation (EM). Tetapi di balik itu, ada beberapa kelemahan yang sering menjadi kendala bagi teori ini untuk bisa menghasilkan pemodelan yang baik. Salah satunya adalah metode ML sering memberikan estimasi yang bersifat bias, dimana cara 8
Jurnal Sistem dan Informatika Vol. 1 (Agustus 2005), 1 - 16 pengestimasian tidak selalu sama untuk semua kejadian yang dianalisa. Selain itu, teori ini sering terbawa ke dalam permasalahan over-fit, dimana pemodelan cenderung memilih model yang lebih kompleks dari yang seharusnya. 5.2. Akaike Information Criterion (AIC)
Akaike Information Criterion (AIC) [4] diperkenalkan pertama kali oleh Akaike (1974) untuk mengidentifikasikan model dari suatu dataset. Metode ini merupakan salah satu dari metode yang menerapkan pendekatan penalized Maximum Likelihood. Persamaan AIC dalam melakukan pemilihan model adalah sebagai berikut: AIC = L + N p
(15)
dimana L merupakan negative logarithm dari likelihood function dan Np merupakan jumlah parameter yang diestimasi di dalam model tersebut. Jumlah parameter yang diestimasi tergantung pada asumsi yang digunakan untuk menjelaskan setiap data di dalam suatu kelompok. Untuk data kontinyu univariate yang akan ditinjau dalam tulisan ini, jumlah parameter yang diestimasi adalah sebanyak k-1+kp dimana k adalah jumlah kelompok dan p adalah jumlah parameter dalam setiap kelompok. Karena kita akan memodel data kontinyu univariate dan multivariate tidak berkorelasi dengan distribusi Normal atau Student t, maka p di sini adalah sama dengan 2 untuk distribusi Normal dan 3 untuk distribusi Student t untuk setiap attribute di dalam model terpilih. 5.3. Bayesian Information Criterion (BIC)
Bayesian Information Criterion (BIC) [11] yang juga merupakan suatu tipe metode pemilihan model dengan memanfaatkan pendekatan penalized Maximum Likelihood, diperkenalkan pertama kali oleh Schwarz (1978). Sama seperti MML, metode ini dikembangkan dengan basis teori Bayesian. Persamaan yang digunakan BIC dalam melakukan pemilihan model adalah sebagai berikut: BIC = L +
Np 2
log N
(16)
dimana L merupakan negative logarithm dari likelihood function-nya, Np merupakan jumlah parameter independen yang diestimasi dan N merupakan jumlah data. Untuk kasus yang ditinjau di dalam tulisan ini, Np diset sama dengan k-1+kp, dimana k merupakan jumlah kelompok dan p merupakan jumlah parameter yang diestimasi di dalam setiap kelompok. Nilai p diset sama seperti setting yang dilakukan pada AIC.
9
Jurnal Sistem dan Informatika Vol. 1 (Agustus 2005), 1 - 16
6. Metode Pengevaluasian Dalam ekperimen yang dilakukan di dalam tulisan ini, dua metode pengevaluasian akan diterapkan. Mereka adalah metode Kullback-Leibler (KL) Distance dan Probability BitCosting. 6.1. Kullback-Leibler (KL) Distance
Kullback-Leibler (KL) distance[1] merupakan metode pengevaluasian yang digunakan untuk mengukur kedekatan suatu model terhadap model yang lain. KL distance dari sebuah model kontinyu, f ( x | θ ) , terhadap model kontinyu lainnya, f ( x | θˆ) , didifinisikan sebagai berikut ini: ∞ f (x |θ ) KL(θ ,θˆ) = ∫ f ( x | θ ) log dx −∞ f ( x | θˆ)
(17)
Nilai dari KL distance selalu positif dan sama dengan 0 bila θ = θˆ . 6.2. Probability Bit-Costing
Probability Bit-Costing[1] merupakan metode penilaian digunakan untuk mengevaluasi model yang didapat bila tidak ada model yang terdifinisikan sebelumnya untuk data yang dianalisa. Metode ini dipergunakan dengan membagi dataset yang sedang dianalisa menjadi dataset training dan dataset test. Dataset training dianalisa terlebih dahulu menggunakan metode pengelompokan data yang ditinjau. Kemudian dataset test disesuaikan dengan model yang dipilih sebagai model terbaik untuk dataset training. Penyesuaian ini dilakukan dengan menghitung probability bit-costing sebagai berikut: bit − cos ting = ∑ − log( P ( xi | θ training )
(18)
i
untuk setiap data, xi, di dalam dataset test. Di sini, P( xi | θ training ) merupakan probability untuk mendapatkan data, xi, menggunakan model, θ training , yang terpilih untuk dataset training.
7. Hasil Ekperimen Dalam tulisan ini, dua contoh pengimplementasian metode yang telah dikembangkan di atas akan diulas. Contoh pertama merupakan analisa menggunakan dataset buatan. Dataset ini dibuat dengan mengasumsikan bahwa setiap attribute di dalam setiap kelompok di-sample dari distribusi statistik, baik distribusi Normal maupuan distribusi Student t, dengan parameter yang telah ditentukan terlebih dahulu. Contoh kedua merupakan analisa terhadap 10
Jurnal Sistem dan Informatika Vol. 1 (Agustus 2005), 1 - 16 dataset Old Faithful Geyser yang telah dianalisa di dalam penelitian yang dipublikasikan oleh McLachlan and Peel, 2000[7]. Penjelasan lebih lanjut mengenai masing-masing dataset dapat dilihat pada masing-masing bagian di bawah ini. 7.1. Dataset 1
Untuk contoh ini, kami menggunakan dataset yang juga telah digunakan di dalam penelitian yang dipublikasikan oleh Agusta dan Dowe, 2002[2] dan Agusta dan Dowe, 2002[3]. Dataset ini merupakan dataset mixture yang terdiri dari tiga kelompok dan dua variable yang dibuat menggunakan fungsi seperti yang diperlihatkan pada judul dari Gambar 1. Fungsi ini merupakan kombinasi antara distribusi Normal dan Student t. Dataset ini terdiri dari 150 data dengan proporsi untuk masing-masing kelompok adalah 50:50:50. Satu contoh dari dataset tersebut diperlihatkan pada Gambar 1. 6 4 2 0 y
-2 -4
Kelompok 1 Kelompok 2
-6
Kelompok 3 -8 -10
-8
-6
-4
-2
x
0
2
4
6
Gambar 1: 150 data dengan dua variable dalam bentuk mixture dengan tiga kelompok yang dibuat menggunakan kombinasi distribusi Normal dan Student t:
1 / 3[ N ( µ x1 = −2.0, σ x21 = 1.0) × N ( µ y1 = −3.5, σ y21 = 1.0)] + 1 / 3[tν x2 =1.0 ( µ x2 = 0.0, σ x21 = 1.0) × N ( µ y 2 = 0.0, σ y22 = 1.0)] + 1 / 3[ N ( µ x3 = 2.0, σ x23 = 1.0) × N ( µ y3 = 3.5, σ y23 = 1.0)]. Tabel 1 mengilustrasikan sebuah contoh hasil pemodelan menggunakan metode pengolahan data yang dikembangkan di dalam tulisan ini dengan parameter ν di dalam distribusi Student t dianggap sebagai parameter yang telah diketahui. Pada saat data dimodel menggunakan hanya distribusi Normal saja, model yang dihasilkan terdiri dari tiga kelompok dengan message lebih panjang (= 2714,639 nits) daripada kedua model yang didapat dengan menggunakan kombinasi antara distribusi Normal dan distribusi Student t. 11
Jurnal Sistem dan Informatika Vol. 1 (Agustus 2005), 1 - 16
No. Klp. Proporsi Att. 1 Mean SD DefOfF Att. 2 Mean SD DegOfF
MML Gaussian dan t (v=1.0) 2709,859 nits Klp. 1 Klp. 2 Klp. 3 0,328 0,344 0,328 --- presisi pengukuran e = 0,0001 ---2,244 -0,149 2,012 1,079 0,644 0,815 Infinity Infinity 1,000 --- presisi pengukuran e = 0,0001 ---3,631 -0,010 3,518 0,951 0,920 0,855 Infinity Infinity Infinity
Tabel 1: Perbandingan antara dua hasil pengelompokan menggunkan distribusi Normal dan Student t dimana parameter v dianggap sebagai parameter yang diketahui. (Distribusi Normal merupakan bagian khusus dari distribusi Student t dengan v = Infinity).
Rata-rata KL Distance 1 2 Jumlah 3 true Kelompok 4 5
MML 0,0097 ( ± 0,011) 0 0 20 0 0
AIC 0,0109 ( ± 0,011) 0 0 17 3 0
BIC 0,0122 ( ± 0,010) 0 0 17 3 0
Tabel 2: Perbandingan antara MML, AIC dan BIC untuk pemodelan dataset buatan yang terdiri dari tiga kelompok dibuat menggunakan fungsi yang tercantum pada penjelasan Gambar 1. Perbandingan dilakukan terhadap nilai rata-rata KL distance dan jumlah kelompok yang dihasilkan terhadap 20 dataset buatan yang dibuat menggunakan fungsi yang sama.
Table 2 memperlihatkan perbandingan antara pemodelan menggunakan MML, AIC dan BIC. Di sini, dataset dibuat sebanyak 20 kali menggunakan fungsi yang disebutkan di atas. Dari pemodelan menggunakan MML, AIC dan BIC diperoleh hasil bahwa keduapuluh dataset buatan yang dimodel dengan MML, semuanya menghasilkan model dengan tiga kelompok. Sedangkan AIC dan BIC masing-masing menghasilkan 17 model dengan tiga kelompok serta 3 model dengan empat kelompok. Dilihat dari rata-rata Kullback-Leibler distance dari model yang dihasilkan terhadap model asli yang digunakan untuk membuat data buatan ini, didapat bahwa MML memodel dataset buatan ini lebih dekat kepada aslinya daripada AIC dan BIC dengan rata-rata KL distance yang lebih kecil.
12
Jurnal Sistem dan Informatika Vol. 1 (Agustus 2005), 1 - 16 7.2. Dataset 2 (Old Faithful Geyser Dataset)
Old Faithful Geyser dataset terdiri dari 272 data univariate dari lama setiap semburan yang terjadi di Old Faithful Geyser. Dataset ini dianalisa sebagai permasalahan pengelompokan data oleh McLachlan dan Peel, 2002[6] dan Agusta and Dowe, 2002[3]. Dalam penganalisaan ini data yang ada di-lag menjadi dataset yang terdiri dari dua variable. Kali ini, dataset dianalisa untuk mengetahui adanya outliers atau tidak. Dalam bagian ini, dataset ini dianalisa menggunakan metode pengelompokan data yang menggunakan kombinasi antara distribusi Normal dan distribusi Student t. Sebagai perbandingan data dimodel juga menggunakan metode yang menggunakan distribusi Normal saja. Perbandingan metode yang menggunakan MML dengan metode yang menggunakan AIC dan BIC dilakukan dengan membagi dataset aslinya menjadi dua dataset yaitu dataset training dan dataset test dengan proporsi 244:27. Dataset training dimodel terlebih dahulu menggunakan metode yang dianalisa dan kemudian dataset test disesuaikan dengan model yang didapat dari dataset training tersebut. Pengevaluasian dilakukan menggunakan metode probability bit-costing, − log( P( x)) , untuk setiap data, x, di dalam dataset test. Proses ini diulangi 20 kali. Rata-rata probability bit-costings ketiga metode yang digunakan (MML, AIC dan BIC) adalah masing-masing 454,940 ( ± 26,075), 455,450 ( ± 50,871) dan 509,380 ( ± 91,899) nits (1 nit = log 2 e bits). Hasil ini memperlihatkan bahwa MML bekerja lebih baik dibandingkan AIC dan BIC.
5
Previous Eruption Length
4.5 4 3.5
Component 1 3
Component 2 Component 3
2.5
Component 4
2 1.5 1.5
2
2.5
3
3.5
4
4.5
5
Eruption Length
Gambar 2: Model mixture yang terdiri dari empat kelompok sebagai model terbaik yang ditemukan saat memodel Old Faithful Geyser dataset menggunakan metode pengelompokan data berbasis MML. Semua attribute dari semua kelompok yang dihasilkan dimodel
13
Jurnal Sistem dan Informatika Vol. 1 (Agustus 2005), 1 - 16 menggunakan distribusi Normal. Perlu diketahui di sini bahwa semua data yang ada di bagian kiri bawah dari gambar dimodel sebagai satu distribusi Normal. Dalam penganalisaan lebih lanjut, dataset ini memperlihatkan hasil yang paling bagus dengan panjang message yang terpendek saat dimodel menjadi empat kelompok dimana masing-masing attribute pada masing-masing kelompok dimodel menggunakan distribusi Normal saja. Gambar 2 memperlihatkan hasil pemodelan tersebut. Sedangkan, bila dataset dimodel menggunakan metode yang mengkombinasikan distribusi Normal dan distribusi Student t, didapat bahwa dataset ini paling bagus dimodel dengan 3 kelompok. Pemodelan kedua ini diperlihatkan pada Gambar 3. Tetapi message yang didapat pada pemodelan yang kedua memiliki panjang yang lebih besar daripada pemodelan pertama. Dengan kata lain, pemodelan pertama memang lebih tepat dibandingkan dengan pemodelan kedua.
5
Previous Eruption Length
4.5
4
3.5
Component 1 Component 2 Component 3
3
2.5
2
1.5
1.5
2
2.5
3
3.5
Eruption Length
4
4.5
5
Gambar 3: Hasil pemodelan dari Old Faithful Geyser dataset menggunakan metode pengelompokan data yang dikembangkan dalam tulisan ini. Di sini keenam data yang terletak di kiri bawah dimodel sebagai outliers dari attribute kedua dari kelompok ketiga.
8. Kesimpulan Sebagai kesimpulan, tulisan ini mengajak pembaca untuk memahami pengembangan metode mixture modelling menggunakan prinsip Minimum Message Length (MML) dimana data yang diolah merupakan data kontinyu univariate/multivariate tidak berkorelasi dan keberadaan outliers di dalam kelompok yang dihasilkan juga diobservasi. Perbandingan 14
Jurnal Sistem dan Informatika Vol. 1 (Agustus 2005), 1 - 16 antara metode pengelompokan data menggunakan MML ini juga dibandingkan dengan teori alternatif lain seperti Maximum Likelihood (ML), Akaike Information Criterion (AIC) serta Schwarz’s Bayesian Information Criterion (BIC). Eksperimen menunjukkan MML bekerja lebih baik dalam menentukan jumlah kelompok dari data yang dianalisa dan dalam penganalisaan data buatan (Bagian 7.1.) dapat dilihat bahwa MML memodel data buatan tersebut lebih dekat pada model aslinya dibandingkan AIC dan BIC dengan KullbackLeibler distance yang lebih kecil dibandingkan kedua metode alternatif yang ditinjau. Dalam penganalisaan real-data Old Faithful Geyser, MML juga menunjukkan hasil yang sama dengan probability bit-costing yang lebih kecil daripada AIC dan BIC.
Daftar Pustaka [1] Agusta, Y. (2004). Minimum Message Length Mixture Modelling for Uncorrelated and Correlated Continuous Data Applied to Mutual Funds Classification, Ph.D. Thesis, School of Computer Science and Software Engineering, Monash University, Clayton, 3800 Australia [2] Agusta, Y. and Dowe, D.L. (2002a). MML Clustering of Continuous-Valued Data using Gaussian and t Distributions, in B. McKay and J. Slaney (eds), Lecture Notes in Artificial Intelligence 2557, Proceedings of the 15th Australian Joint Conference on Artificial Intelligence (AI02), Springer-Verlag, Berlin, Germany, pp. 143-154 [3] Agusta, Y and Dowe, D.L. (2002b). Clustering of Gaussian and t Distribution using Minimum Message Length, in M. Sasikumar, H. J. Jayprasad and M. Kavitha (eds), Artificial Intelligence: Theory and Practice, Proceedings of the International Conference Knowledge-Based Computer Systems (KBCS-2002), Vikas Publishing House Pvt. LTD., New Delhi, India, pp. 289-299. [4] Akaike, H. (1974). A New Look at the Statistical Model Identification, IEEE Transaction on Automatic Control AC-19(6): 716-723. [5] Cheeseman, P. and Stutz, J. (1996). Bayesian Classification (AutoClass): Theory and Results, in U. M. Fayyad, G. Piatetsky-Shapiro, P. Smyth and R. Uthurusamy (eds), Advances in Knowledge Discovery and Data Mining, AAAI Press/MIT Press, Cambridge, MA, pp. 153-180. [6] Fraley, C. and Raftery, A. E. (1998). MCLUST: Software for Model-Based Cluster and Discriminant Analysis, Technical Report 342, Department of Statistics, University of Washington, Box 354322, Seattle, WA, USA. [7] McLachlan, G.J. and Peel, D. (2202a). On Computational Aspects of Clustering via Mixtures of Normal and t-Components, Proceedings of the American Statistical Association (Bayesian Statistical Science Section), Indianapolis, Alexandria, Virginia. [8] McLachlan, G.J. and Peel, D. (2002b). Finite Mixture Models, John Wiley and Sons, New York. [9] McLachlan, G. J., Peel, D., Basford, K. E. and Adams, P. (1999). The EMMIX Software for the Fitting of Mixtures of Normal and t-Components, Journal of Statistical Software 4(2): 1087-1092.
15
Jurnal Sistem dan Informatika Vol. 1 (Agustus 2005), 1 - 16 [10] Neal, R. M. (1991). Bayesian Mixture Modeling by Monte Carlo Simulation, Technical Report CRG-TR-91-2, Department of Computer Science, University of Toronto, Toronto, Canada. [11] Schwarz, G. (1978). Estimating the Dimension of a Model, The Annals of Statistics 6: 461 – 464. [12] Shannon, C. E. (1948). A Mathematical Theori of Communication, Bell System Tech. Journal 27: 379-423. [13] Wallace, C. S. (1986). An Improved Program for Classification, Proceedings of the 9th Australian Computer Science Conference (ACSC-9), Vol. 8, Monash University, Australia, pp. 357-366. [14] Wallace, C. S. and Boulton, D. M. (1968). An Information Measure for Classification, Computer Journal 11(2): 185-194. [15] Wallace, C. S. and Dowe D. L. (1994). Intrinsic Classification by MML – the Snob Program, Proceedings of the 7th Autralian Joint Conference on Artificial Intelligence (AI94), World Scientific, Singapore, pp. 37-44. [16] Wallace, C. S. and Dowe, D. L. (1997). MML Mixture Modelling of Multi-State, Poisson, von Mises Circular and Gaussian Distribusions, Proceedings of the 6th International Workshop on Artificial Intelligence and Statistics, Fort Launderdale, Florida, pp. 529-536. [17] Wallace, C. S. and Dowe, D. L. (2000). MML Clustering of Multi-state, Poisson, von Mises Circular and Gaussian Distributions, Statistics and Computing 10: 73-83. [18] Wallace, C. S. and Freeman, P. R. (1987). Estimation and Inference by Compact Coding, Journal of the Royal Statistical Society B 49(3): 240-265.
16
