Harmonisasi Algoritma Hybrid Untuk Membangun Struktur Bayesian Network Pada Basisdata Ilham M.Said, Handayani Tjandrasa Teknik Informatika ITS
[email protected] Staff Pengajar Teknik Informatika ITS Abstrak Perkembangkan berbagai algoritma untuk mengkonstruksi struktur Bayesian Network, baik untuk basis data lengkap maupun untuk basis data yang tidak lengkap (terdapat missing value) cukup banyak. Beberapa algoritma hanya dapat bekerja secara parsial saja. Dan yang menjadi masalah adalah dari beberapa penelitian belum ada uji coba dari penggabungan algoritma CB (Constraint Base) dan BC (Bound dan Collapse) dalam konstruksi struktur Bayesian Network berdasarkan data lengkap dan tidak lengkap. Oleh karena itu solusi penggunaan metode Analisis dependensi dan Search & Scoring yang dapat bekerja untuk data lengkap dan tidak lengkap adalah merupakan solusi alternative dalam membangun struktur. Simpulan Pengembangan (propose) adalah melakukan konstruksi struktur Bayesian Network dari data lengkap dan tidak lengkap dengan algoritma Hybrid (CB dan BC).. Kedua Algoritma ini terdiri dari dua fase yaitu fase pertama menghasilkan node ordering dan fase kedua untuk mengkonstruksi struktur DAG(Directed Acyclic Graph) dari Bayesian Network. Pada fase kedua juga dapat menangani missing value. Sedangkan jumlah missing value tidak berpengaruh secara mutlak terhadap struktur Bayesian Network yang dihasilkan. Jumlah missing value yang besar ataupun yang kecil pada basis data tetap dapat menghasilkan struktur. Namun dalam makalah ini yang ditekankan adalah berapapun jumlah missing value yang dimiliki oleh basis data, Algoritma Hybrid ini tetap mampu menghasilkan konstruksi struktur Bayesian Network. Kata kunci : Data lengkap, Data tidak lengkap, Bayesian Network, Missing Value, Dependency Analysis, Search and Scoring, Node Ordering
1. Pendahuluan Konsep Algoritma CB merupakan konsep algoritma pembangunan framework Bayesian Network yang mengkombinasikan algoritma dengan pendekatan metode analisis dependensi (Algoritma PC) dan metode search & scoring (Algoritma K2) [PUS05]. Tujuan utama dari Algoritma CB adalah memperoleh algoritma pencarian framework yang secara komputasi mudah dikerjakan, yaitu tidak terlalu bergantung pada CI (conditional independence) test dan tidak membutuhkan node ordering (node ordering tidak di inputkan secara manual dalam pembentukannya) [SIN95]. Namun, Algoritma CB mensyaratkan data lengkap. Berdasarkan cara kerja dan fungsinya yang berbeda dari beberapa ciri algoritma tersebut maka yang menjadi masalah adalah masing-masing dari algoritma tidak bisa bekerja secara bersamasama untuk membangun framework Bayesian Network dari data yang lengkap dan tidak lengkap. padahal pada kenyataannya basisdata itu ada yang lengkap dan ada yang tidak lengkap. Dari beberapa algoritma tersebut hanya bisa berjalan dan berfungsi secara parsial saja dari beberapa bentuk basisdata. Pada penelitian Improvement of CB & BC Algorithm (CB* Algorithm) for Learning Structure of Bayesian Networks as Classifier in Data Mining [SIT06]. Sekolah Teknik Elektro dan Informatika, ITB menyatakan bahwa dengan menggabungkan kedua algoritma tersebut tetap akan mampu menghasilkan konstruksi struktur dari basisdata tidak lengkap. Namun penelitian ini pada makalah belum terlihat adannya analisa lebih jauh akan performansinya, kemudian
memeriksa kebenaran struktur Bayesian Network yang dihasilkan. Pada penelitian dengan judul algoritma CB: algoritma yang dibangun dengan dua pendekatan untuk konstruksi struktur bayesian network dalam data mining [PUS05].Program Studi Teknik Informatika, STEI, ITB. Menyatakan bahwa algoritma yang di telitinya hanya memperlihatkan konstruksi struktur pada data lengkap, dan belum dapat bekerja pada data tidak lengkap.
2. Metode Penelitian Metodologi adalah kumpulan metode untuk menguraikan bagaimana suatu kumpulan aktivitas dilaksanakan. Umumnya metodologi terdiri dari prosedur, teknik dan disiplin tertentu. Metode yang digunakan pada penelitian ini adalah :
Gambar 2.1. Desain System
Berikut penjelasan pada gambar 2.1 adalah : 1. Tahap pertama disusun dari tujuh langkah sebagai bagian dari Algoritma CB dan hasilnya adalah node ordering. Fase pertama ini sebagian besar digunakan untuk mengkonstruksi DAG. 2. Tahap kedua disusun dari tiga langkah. Fase ini dirancang untuk mempelajari struktur Bayesian Network dari data yang memiliki missing value, sama dengan yang diaplikasikan oleh Algoritma BC. Algoritma BC sendiri terdiri dari tiga bagian utama yaitu: a. Pencarian interval estimasi probabilitas disebut tahap bound (penanganan missing value). b. Mencari nilai estimasi tunggal dari interval yang telah diperoleh disebut tahap collapse. c. pembangunan struktur Bayesian Network itu sendiri.
Gambar 2.2. FlowChart System Berikut penjelasan pada gambar 2.2 adalah : 1. Menerima masukan sebuah tabel basis data yang memiliki missing value dan yang tidak memiliki missing value tentunya (disediakan juga data lengkap), yang dibangkitkan struktur Bayesian Network dari atribut-atributnya. 2. Inisialisasi : menginisialisasi nilai–nilai awal untuk konstruksi struktur Bayesian Network dengan tujuan mendapatkan Graph Lengkap. 3. Pembuatan node ordering, yang terdiri dari sub-sub fungsi : CI test, identifikasi collider, pemberian arah dengan rule dan pembangkitan node ordering. 4. Bagian bound Menghitung CPT (Conditional Probability Table) dalam bentuk tabel, berdasarkan nilai probabilitas nodenode dari struktur BN. 5. Bagian Collapse Memanfaatkan hasil yang diperoleh pada tahap bound untuk mencari
satu nilai estimasi tunggal dari probabilitas kondisional yang bersesuaian 6. Melakukan Scoring function dalam menentukan hubungan ketergantungan antar variabel, apakah sebuah variabel atau node dapat ditambahkan sebagai parent atau tidak. 7. Konstruksi struktur Bayesian Network . 2.1 Rancangan Metode Konstruksi Struktur Bayesian Network Pendekatan yang digunakan untuk membangun framework Bayesian Network [CHE01] yaitu metode search and scoring dan metode dependency analysis. Masing-masing metoda ini memandang Bayesian Network dari sudut yang berbeda. Pada metoda search and scoring, Bayesian Network dipandang sebagai sebuah struktur yang merepresentasikan JPD (Joint Probability Distribution)dari variabelvariabel, sedangkan pada metoda dependency analysis, Bayesian Network dipandang sebagai sebuah struktur yang merepresentaskan sekumpulan kebebasan kondisional di antara node-node. Berikut ini diberikan penjelasan lebih rinci mengenai kedua pendekatan tersebut [CHE97[b] : 1. Metode Search and Scoring (Scoring Based). Metode ini melakukan pengembangan struktur dengan mencari sebuah struktur yang paling cocok dengan data. Dalam metode ini, permasalahan digambarkan sebagai pencarian struktur graf (model) yang baik dari data. Model dibangkitkan dari kombinasi node (variabel) yang ada. Pencarian tersebut dilakukan dengan search method. Setiap model dievaluasi oleh sebuah scoring function 2. Metode Dependency Analysis (Constraint Based) Pada metode ini, permasalahan digambarkan sebagai pencarian kebebasan (ketidakbergantungan) dari data yang kemudian dipergunakan untuk (meng-infer) sebuah struktur. Hubungan kebebasan tersebut data diukur dengan menggunakan salah satu dari beberapa jenis Conditional Independence test (CI test) dan hubungan tersebut digunakan sebagai batasan untuk membangun framework Bayesian Network.
2.2 Membangkitkan Node Ordering yang Menghasilkan Struktur yang Markov Ekuivalen Dengan Struktur Original Algoritma Hybrid dapat membangkitkan node ordering yang mampu menghasilkan struktur Bayesian Network yang Markov ekuivalen dengan struktur original (mendekati struktur asal). - Node ordering adalah urutan node-node pada graf yang merepresentasikan salah [2] satu dari dua kemungkinan berikut : 1. Hubungan sebab akibat (causal) Node yang muncul lebih awal adalah node yang merupakan penyebab dari node yang muncul berikutnya. 2. Urutan sementara (temporal ordering) Node yang muncul lebih awal
menyatakan event yang terjadi lebih dahulu dibanding node yang muncul berikutnya. - Markov condition (Kondisi Markov) Markov condition merupakan hubungan antara graf dan distribusi probabilitas yang menjadi hal mendasar dalam Bayesian Network. Markov condition mendefinisikan hubungan kebebasan yang terdapat pada graf dan kebebasan yang terdapat pada distribusi probabilitas dari data. Kebutuhan node ordering dapat dipenuhi oleh Algoritma Hybrid dengan memanfaatkan pendekatan dependency analysis. Arah edge pada DAG yang dianggap sebagai hubungan parent mempengaruhi child adalah pada collider yang terdapat dalam DAG tersebut. Adanya edge berarah yang lain hanya dapat diinterpretasikan sebagai kebergantungan langsung antara dua node yang dihubungkan tanpa dapat diketahui node mana yang berpengaruh terhadap node yang lain. 2.3 Rancangan Tabel-Tabel untuk Sistem Tabel 2.1 Rancangan Data Visit to Asia Nama Keterangan Variabel Visit to Penyebab langsung dari Asia? tuberculosis yaitu apakah pasien pernah ke Asia tau tidak. Smoking ? Penyebab langsung lung cancer dan bronchitis atau apakah pasien adalah perokok atau tidak. Tuberculosis Apakah pasien memiliki ? penyakit tuberculosis atau tidak. Lung Apakah pasien memiliki kanker Cancer ? paru atau tidak. Either Tub Variabel gabungan dari or Lung tuberculosis dan lung cancer. Cancer? Bernilai true/yes bila pasien memiliki tuberculosis atau lung cancer. Bronchitis? Penyebab langsung dari dyspnoea yaitu apakah pasien memiliki penyakit bronchitis atau tidak. Prositive X- Apakah tes X-ray menunjukkkan ray? hasil positif atau tidak, tidak ada keterkaitan langsung dengan dyspnoea. Dyspnoea ? Apakah pasien memiliki penyakit kesulitan bernapas atau tidak. Tabel 2.2 Rancangan Representasi nilai dari variable-variabel BN Node Nilai Keterangan h1 H
h2 b1
B b2
Ada riwayat merokok (H=history) Tidak ada riwayat merokok Bronkhitis ada (B=bronkhitis) Bronkhitis tidak ada
l1 L
F
l2 f1 f2 c1
C c2
Kanker paru-paru ada (L=lung) Kanker paru-paru tidak ada Kelelahan ada (F=fatique) Kelelahan tidak ada Hasil uji sinar-X terhadap kanker paru-paru positif (C=cancer) Hasil uji sinar-X terhadap kanker paru-paru negatif
2.3.1 Rancangan Penanganan Missing Value Menggunakan Algoritma hybrid Penanganan Missing Value dilakukan pada fase kedua dari Algoritma hybrid atau dengan kata lain penanganan ini akan dilakukan oleh Algoritma BC yang merupakan bagian dari Algoritma hybrid . Tabel 2.3 Node order : Case 1 2 3 4 5 6 7 8 9 10
X1 1 1 2 NULL 2 NULL 1 2 NULL 1
X1 X 2 X2 1 NULL 2 1 1 2 2 NULL 2 NULL
Untuk memeriksa apakah X2 adalah parent X1, harus dicari nilai-nilai berikut (tahap Bound) : P(X1=1|X2=1) hitung jumlah kasus (X1=NULL|X2=1) cari nilai Pmin dan Pmax (interval estimasi) P(X1=2|X2=1) P(X1=1|X2=2) P(X1=2|X2=2) 2.4 Kajian Pustaka 2.4.1. Bayesian Network Bayesian Network merupakan salah satu metode yang dapat di pakai untuk membangun model klasifikasi. metode ini adalah efektif dalam hal merepresentasikan model klasifikasi dengan beberapa alasan, antara lain : 1. Dapat merepresentasikan hubungan sebab akibat diantara variabel-variabel yang terdapat pada framework Bayesian Networks[HEC96]. 2. Mengeksploitasi conditional independence dalam membangun struktur jaringan sehingga dapat membangun model klasfikasi yang lebih tepat [NEA04]. Hal tersebut mengakibat berkurangnya kompleksitas perhitungan dalam melakukan inferensi (mengambil keputusan). 3.Metode Bayesian yang digunakan pada model klassifikasi yang dibangun benar-benar sangat cocok/dekat dengan training data yang digunakan, Ini menyebabkan ketika model digunakan untuk memprediksi data dengan menggunakan testing data menghasilkan
performansi yang jelek. Hal bisa diakibatkan antara lainnya karena : terlalu banyak attribut/ node yang digunakan dalam melakukan prediksi atau karena noise yang terdapat pada data.
(interval estimate) berdasarkan observasi yang ada pada basis data. Kemudian hasil estimasi interval dipersempit menjadi satu point estimasi yang unik dengan menyatukan value yang ekstrim dari estimasi interval.
2.4.2 Desain Conditional Independency Test
2.4.4 Rancangan Perhitungan probabilitas kondisional dari kejadian :
Salah satu jenis CI test yang bisa digunakan untuk menghitung kebebasan kondisional pada variabel acak diskret adalah conditional mutual information test. CI test ini akan digunakan pada tahap pertama dari Agoritma Hybrid. Pada saat I(Xi,Xj) memiliki nilai lebih kecil dari sebuah threshlod (ambang batas) tertentu yang dinotasikan dengan , maka dapat dikatakan bahwa Xi dan Xj adalah marginally independent. Pada saat I(Xi,Xj)|C) memiliki nilai lebih kecil dari , maka dapat dikatakan bahwa Xi dan Xj adalah conditionally independent. Nilai threshold yang dianjurkan adalah 0.01, sehingga algoritma ini akan mengatakan bahwa X dan Y akan independent jika I(x,y) < , di mana =0.01 atau 0.05. Semakin tinggi nilai mutual information antara dua node/variabel, semakin tinggi kemungkinan untuk membuat arc yang menghubungkan node-node tersebut.. Disini penulis menentukan = 0.005.
P(h1)*P(b1|h1)*P(l1|h1)*P(f1|b1,l1)*P(c1|l1) = 0.2*0.25*0.03*0.75*0.6 = 0.0000675. JPD untuk Struktur bayesiannya : P(U) = P(H,B,L,F,C)= P(H) P(B/H) P(L/H) P(F/B,L) P(C/L) Causal Inference :
P b1 | h1
Ph1| b1Pb1 Ph1| b1Pb1 Ph1| b2Pb2
Probabilitas Bronchitis akibat merokok : P b1 p h1 | b1 p h1 P h1 | b1 P b1 P h1 | b1 P b1 P h1 | b 2 P b 2 0 . 25 0 . 2 0 . 076 0 . 25 0 . 2 0 . 75 0 . 8
P b1 | h1
2.4.3 Deskripsi Analisa Algoritma Hybrid Algoritma Hybrid merupakan pengembangan dari Algoritma CB dan BC. Algoritma CB dikembangkan oleh Singh & Voltorta adalah sebagai suatu algoritma yang mengkombinasikan metode analisis dependensi dan metode search and scoring merupakan salah satu algoritma yang tidak terlalu bergantung pada CI test dan tidak membutuhkan node ordering tetapi membangkitkan sendiri node ordering [SIN95]. Algoritma ini bertujuan untuk memperoleh metode pencarian struktur yang secara komputasi mudah dikerjakan. Namun, Algoritma CB hanya mampu membangun Bayesian Network dari basis data yang lengkap. Hal ini disebabkan beberapa hal yaitu : [SIM06] 1. Test kebebasan yang dilakukan oleh Algoritma CB dalam menghasilkan node ordering hanya dapat dilakukan dengan asumsi data pada kondisi lengkap. Adanya data yang bernilai null akan mempengaruhi derajat kebebasan, frekuensi amatan dan frekuensi harapan yang digunakan dalam test kebebasan, sehingga CI test tidak dapat dilakukan. 2. Bayesian Scoring Function yang digunakan oleh Algoritma CB dalam pemberian orientasi arah edge yang masih undirected maupun bidirected hanya dapat dilakukan dengan mensyaratkan data lengkap. 3. Algoritma K2 pada Algoritma CB tidak menangani estimasi maupun penanganan unknown value. Untuk memimalisasi masalah missing value, Algoritma BC (Bound and Collapse) diusulkan oleh Ramoni dan Sebastiani. Metode ini diawali dengan membatasi kumpulan dari possible estimate
Pb1 p h1 | b1 p h1
Probabilitas tidak Bronchitis akibat merokok : P(b2/h1)= 1- 076 = 0.924 Diagostic Inference :
P h 1 p b 1 | h1 p b 1 P b 1 | h 1 P h 1 P b 1 | h 1 P h 1 P b 1 | h 2 P h 2 P h1 | b 1
Probabilitas merokok dengan penyakit Bronchitis: P h 1 p b 1 | h1 P h1 | b 1 p b 1
P b1 | h1 P h1 P b1 | h1 P h1 P b1 | h 2 P h 2
0 . 25 0 . 2 0 . 55 0 . 25 0 . 2 0 . 05 0 . 8
indikasi
Probabilitas tidak merokok dengan indikasi penyakit Bronchitis:
P h2 | b1
P h 2 p b1 | h2 p b1
Pb1 | h2 Ph2 = Pb1 | h2 Ph2 Pb1 | h1Ph1
1- 0.55 = 0.45 Probabilitas tidak Bronchitis akibat merokok : P(b2/h1)= 1- 076 = 0.924
3. Pembahasan Hasil Setelah menyelesaikan tahap implementasi, maka selanjutnya tahapan yang akan dilakukan adalah pengujian terhadap perangkat lunak yang telah dihasilkan. Struktur yang dihasilkan untuk kasus uji pertama ini akan dibandingkan dengan struktur asal Bayesian Network gambar 3.2.
dari Dysponea. Perubahan dalam pembentukan parent dapat disebabkan nilai peluang untuk Bronchitis yang menjadi parent dari Dysponea lebih besar yaitu, peluang terbesar untuk himpunan Dyspnoea = 0.5648 sedangkan nilai peluang Dysponea diberikan adalah parent Bronchitis([Dyspnoea,Bronchitis]) adalah 0.87198 sehingga Bronchitis adalah sebagai parent dari Dyspnoea. 3.2 Evaluasi Algoritma Hybrid Untuk melakukan evaluasi hasil fungsi Algoritma Hybrid yg di bahas yaitu : 1.Algoritma Hybrid dapat mengkonstruksi struktur Bayesian Network dari database yang tidak lengkap. Berapapun data yang hilang pada basis data, Algoritma CB tetap dapat mengkonstruksi struktur Bayesian Network, disamping dapat mengkonstruksi struktur dari basis data yang lengkap tentunya. Hal ini dibuktikan setelah dilakukan implementasi dan uji coba menggunakan data Visit to Asia. Meskipun data yang hilang cukup besar, yaitu 50%, Algoritma Hybrid tetap dapat mengkonstruksi struktur Bayesian 2. Algoritma Hybrid dapat membangkitkan node ordering yang menghasilkan struktur yang markov ekivalen ke struktur original. Node ordering dapat dibangkitkan pada fase pertama dari Algoritma Hybrid,
Gambar 3.2 Hasil Kasus Uji Pertama (Data Lengkap VisitToAsia) Tabel 3.1 Data Uji Hasil VisitToAsia
3. Data dengan jumlah missing value yang besar dapat menghasilkan struktur Bayesian Network yang sama dengan struktur Bayesian Network dari data yang lengkap. Hal ini dapat dilihat pada kasus Fire yang memiliki 10000 record. Meskipun jumlah missing value yang dimiliki basis data adalah 50%, struktur yang dihasilkan masih sama dengan struktur data yang lengkap. Namun untuk kasus Chest Clinic, jumlah missing value yang kecil (15%), menghasilkan struktur Bayesian Network yang berbeda dengan struktur Bayesian Network dari data lengkap. Jadi jumlah data yang besar atau kecil dapat menghasilkan struktur Bayesian Network yang sama atau berbeda dengan struktur Bayesian Network dari data lengkap.
4. Kesimpulan
Hasil perbandingan antara struktur asal dengan struktur yang dihasilkan oleh Algoritma Hybrid adalah pengurangan arc, yaitu hilangnya arc DysPonea-TubOrLung . Sedangkan untuk arah arc tidak terdapat perubahan. Secara lebih umum, perbedaan hasil konstruksi struktur dengan Algoritma Hybrid terhadap struktur asal Bayesian Network terletak pada himpunan parent
1. Dari hasil uji pada kasus Visit to Asia, kemudian Chest Clinic terdapat perubahan pada struktur yang dihasilkan. Perubahan struktur ini dapat terjadi akibat pengaruh data yang digunakan. Data yang digunakan dalam pengujian ini jumlahnya sangat terbatas dan tidak ada jaminan bahwa data tersebut sudah mencukupi sebagai data uji untuk menghasilkan struktur yang baik. Namun hasil uji pada kasus Fire, perubahan struktur tidak ditemukan walaupun data yang hilang adalah sebanyak 50%, hal ini disebabkan karena sampel data yang dimiliki oleh Fire berjumlah lebih besar dari dua kasus yang lain. Sehingga meskipun data yang hilang adalah 50% namun sudah cukup mewakili data yang lengkap.
2. Algoritma Hybrid adalah Algoritma yang dibangun berdasarkan dua pendekatan yaitu analisis dependensi ( constraint based) dan search and scoring (scoring based ) mampu menghasilkan struktur Bayesian Network dari data yang tidak lengkap (terdapat missing value), dengan syarat data diskret dan atribut yang bernilai biner.
5. Pustaka [SIT06] Sitohang, B., & Saptawati, P. (2006). Improvement of CB & BC Algorithm (CB* Algorithm) for Learning Structure of Bayesian Networks as Classifier in Data Mining . Sekolah Teknik Elektro dan Informatika, ITB.J.ICT Vol.1,No.1,2007,29-41 [PUS05] Sandhyaduhita, P., I. (2005). Algoritma CB: Algoritma yang Dibangun dengan Dua Pendekatan untuk Konstruksi Struktur Bayesian Network dalam Data Mining . Program Studi Teknik Informatika, STEI, ITB. [Sel08] Selvia Lorena Br Ginting(2008). Studi algoritma CB Dalam Data Mining untuk Konstruksi Struktur Bayesian Network dari Basis Data Incomplete, Konferensi Nasional Sistem dan Informatika 2008; Bali, November 15, 2008,KNS,108-038 [CHE97[a]] Cheng, J., Bell, D., & Liu, W. (1997). An Algorithm for Bayesian Belief Networks Construction from Data . Proceeding of Ai & STAT ’97 (pp.83-90). Ft. Lauderdale, Florida. [CHE97[b]] Cheng, J., Bell, D., & Liu, W. (1998). Learning Bayesian Networks from Data : An Efficient Approach Based on Information Theory. Faculty of Informatics, University of Ulster, U.K. [SEB97] Sebastiani, P., & Ramona, M. (1997). Bayesian Inference with Missing Data Using Bound and Collapse . Report KMi-TR-58, Knowledge Media Institute, The Open University. [SIN95] Singh, M., & Valtorta, M. (1995). Construction of Bayesian Network Structures from Data: a Brief Survey and an Efficient Algorithm . Dept. of Computer Science, University of South Carolina,Columbia, USA. [SIM06] Simanjuntak, H. (2006). CB untuk Pengembangan Algoritma Konstruksi Struktur Bayesian Network dari Data Tidak Lengkap . Program Studi Teknik Informatika, STEI, ITB. [MAH05] Maharani, H. (2005). Konstruksi Struktur Bayesian Network dalam Data Mining untuk Basis Data Incomplete dengan Metode Bound and Collapse . Program Studi Teknik Informatika, STEI, ITB. [NEA04] Neapolitan, R., E. (2004). Learning Bayesian Networks. USA : Pearson Pentice Hall. [CHE01] Cheng, Jie, et al. (2001). Learning Bayesian Network from data : An Information-Theory Based Approach . Department of Computing Science, University of Alberta., Faculty of Informatics, University of Ulster, Toronto,Canada.
