EVALUASI ALGORITMA CB* UNTUK KONSTRUKSI STRUKTUR BAYESIAN

NETWORK DALAM DATA MINING

LATAR BELAKANG

Berkembangnya Teknologi Basis Data Penyimpanan data dari berbagai sumber dapat

dilakukan dengan mudah dan cepat Muncul kebutuhan menganalisis data

Terotomatisasi Teknologi untuk menangani permasalahan

tersebut adalah : Teknologi Data Mining

LATAR BELAKANG

Proses mendapatkan informasi pengetahuan berdasarkan nilai yang terdapat pada basis data

Proses secara otomatis menemukan informasi yang berguna yang tersimpan pada data dengan ukuran besar.[TAN06]

Data Mining

TUJUAN Membangun perangkat lunak dengan

mengimplementasikan Algoritma CB*

Perangkat lunak berfungsi untuk membangun struktur Bayesian Network

Melakukan uji coba dan evaluasi dari sisi fungsi Algoritma CB*

BATASAN MASALAH

Algoritma yang digunakan adalah Algoritma CB* (terdiri dari 2 fase)

Fase pertama Algoritma CB* tidak menangani data tidak lengkap

Studi kasus adalah data Visit to Asia Data yang hilang adalah secara acak Data yang digunakan adalah data biner RUP sebagai metode pengembangan PL

DASAR TEORI(1)

Bayesian Network:

Sebuah Probabilistic Graphical Model dengan Arc yang berarah dan tidak cyclic untuk mengambarkan hubungan kausalitas antara variabel-variabel dari domain persoalan yang dimodelkan

DASAR TEORI(2)

Komponen Bayesian Network:

Struktur Graph

disebut Directed Acyclic Graph (DAG) terdiri dari Node dan Arc.

Node : Merepresentasikan variable acak

Arc : Merepresentasikan garis berarah yang menunjukkan

hubungan kebergantungan antar node

CPT (conditional probability table)

merupakan himpunan parameter yang berisi probabilitas bersyarat

setiap node-node

KONSEP DASAR BAYESIAN NETWORK(1)

Directed graph G adalah Graf dimana semua

edge-nya mempunyai arah. Arc/edge: representasi panah dari x ke y Adjacent: tetangga Parent: node asal Child: node tujuan Ancestor: Leluhur Descendent: keturunan Root: node yg tidak memiliki parent Directed Acyclic Graph (DAG) adalah graf

berarah yang tidak mengandung siklus. Collider (v-structure): ABC

KONDISI MARKOV Kondisi Markov merupakan hubungan antara DAG dan

distribusi probabilitas. Bayesian Network memanfaatkan kondisi Markov untuk

merepresentasikan JPD secara efisien. Contoh DAG yang mengilustrasikan kondisi Markov

Kebebasan kondisional dari DAG di atas

Maka JPD untuk nilai dari f,c,b,l dan h adalah :

H

B L

F C

P(f,c,l,b,h) = P(f|b,l) P(c|l) P(b|h) P(l|h) P(h)P(f,c,l,b,h) = P(f|b,l) P(c|l) P(b|h) P(l|h) P(h)

MARKOV EKUIVALEN Dua DAG merupakan markov ekuivalen jika dan hanya

jika, berdasarkan kondisi markov, keduanya mempunyai kebebasan kondisional yang sama.

Contoh DAG yang saling markov ekuivalen yaitu :

d-Separation

Dari DAG pada gambar tersebut dalam dikatakan bahwa:

A dan E d-separated oleh {B}, karena chain A-B-C-E terblok pada B dan chain A-B-D-E terblok pada B

B dan E d-separated oleh {C,D} karena chain B-C-E terblok pada C da chain B-D-E terblok pada D

C dan D d-separated oleh {B} karena chain C-B-D terblok pada B dan chain C-E-D terblok tanpa node apapun (collider)

C

B E

D

A

INFORMATION GAINTolok ukur yang dipakai untuk menghitung ukuran volume informasi yang terdapat antara dua node.

Mutual Information

Conditional Mutual Information

Nilai I(X,Y) menentukan apakah X dan Y saling bergantung dan seberapa besar hubungan ketergantungan tersebut

)1..(....................)()(

),(log),(),(

ji xx ji

jijiji xPxP

xxPxxPXXI

)2.(..........)|()|(

)|,(log),,()|,(

,

cxx ji

jijiji

jicxPcxP

cxxPcxxPcXXI

ALGORITMA CB* (1)

Merupakan algoritma yang mengkombinasikan dua pendekatan yaitu pendekatan dependency analysis dan pendekatan search and scoring.

Tujuan utama adalah secara khusus membangun struktur Bayesian Network untuk data yang tidak lengkap (terdapat missing value) [SIT06].

Tujuan lain untuk memperoleh algoritma pencarian struktur yang secara komputasi mudah dikerjakan, tidak terlalu tergantung pada CI test dan tidak membutuhkan node ordering.

ALGORITMA CB*(2)

Terdiri dari dua fase yaitu [SIT06] :Fase pertama diperoleh dari (sebagai bagian dari) Algoritma CB.

Hasilnya node ordering.

Fase kedua dirancang untuk mempelajari struktur Bayesian Network dari data yang memiliki missing value, sama dengan yang diaplikasikan oleh Algoritma BC [SIT06].

Algoritma BC sendiri terdiri dari : Bagian pertama adalah pencarian interval estimasi probabilitas,

disebut dengan tahap Bound. Bagian kedua adalah tahap Collapse yang mencari nilai estimasi

tunggal dari interval yang telah diperoleh. Bagian terakhir adalah pembangunan struktur Bayesian Network itu

sendiri.

i iq

j

c

k ij

i

i

iii

ijpPXg

1 1 )(

))|(ˆˆ(

)ˆ(

)()|(ˆ

Analisis dan Perancangan Perangkat Lunak

Perangkat lunak dibangun dengan metode Rational Unified Process (RUP).

RUP merupakan proses pengembangan perangkat lunak dengan pendekatan iteratif, sehingga dapat mengurangi kegagalan perangkat lunak dalam menangkap kebutuhan pemakai.

Notasi yang digunakan adalah notasi UML.

USE CASE

Diagram Use Case : Gambaran fungsi-fungsi sistem

INTERAKSI ANTAR KELAS

Diagram interaksi kelas tahap analisis

PERANCANGAN PLDiagram Kelas

Perancangan Struktur Data

Cuplikan Data “Visit to Asia”

IMPLEMENTASI PL(1)

Lingkungan Implementasi

IMPLEMENTASI PL(2)Implementasi Kelas

IMPLEMENTASI PL(3)Implementasi Antarmuka

IMPLEMENTASI PL(4)Implementasi Antarmuka Basis Data

IMPLEMENTASI PL(5)Implementasi Antarmuka Konstruksi Struktur Awal

IMPLEMENTASI PL(6)Implementasi Antarmuka Hasil Akhir Konstruksi Struktur

PENGUJIAN PL (1)

Pengujian Use Case Mengambil Data

PENGUJIAN PL (2)Pengujian Use Case mengkonstruksi Struktur

PENGUJIAN PL (3)Pengujian Use Case Menampilkan Hasil Konstruksi

PENGUJIAN PL (4)Pengujian Use Case Menyimpan Gambar

EVALUASI HASIL(1)Hasil Konstruksi Struktur

Hasil Konstruksi Struktur dari Data Lengkap

EVALUASI HASIL(2)Hasil Konstruksi Struktur

Data Tidak Lengkap 15% Data Tidak Lengkap 20%

Data Tidak Lengkap 10%Data Tidak Lengkap 5%

EVALUASI HASIL(3)Hasil Konstruksi Struktur Data Tidak Lengkap 50%

EVALUASI HASIL(4)

Dari variasi jumlah missing value yang dimiliki tabel data, mulai dari 5% sampai 20, dapat dilihat bahwa antara data lengkap dan data yang tidak lengkap (missing value 5%, 10%, 15% dan 20%) tidak ditemukan perbedaan, tidak ada penambahan atau pengurangan arc.

EVALUASI HASIL(5)

Untuk variasi kuantitas missing value 50%, dapat dilihat bahwa struktur yang dihasilkan berbeda dengan data lengkap.

Pengurangan arc dan penambahan arc tidak terjadi, namun perubahan arah arc dapat dilihat pada node TubOrLung dan LungCancer.

Pada data lengkap arah arc dari LungCancer ke TubOrLung namun pada data yang memiliki missing value 50% arah arc berubah menjadi TubOrLung ke LungCancer.

Diakibatkan oleh nilai peluang LungCancer lebih kecil dibandingkan dengan LungCancer diberikan TubOrLung ([LungCancer, TubOrLang)].

Nilai Peluang LungCancer = 0.9438703140830801 sedangkan nilai peluang untuk LungCancer diberikan TubOrLung = 0.9454151872745498, sehingga TubOrLung dijadikan sebagai parent dari LungCancer.

Evaluasi Algoritma CB* Evaluasi dari sisi fungsi Algoritma CB* merefer ke hipotesa yang dikemukakan pada [SIT06] yaitu :

Algoritma CB* dapat membangkitkan node ordering yang menghasilkan struktur yang markov ekivalen ke struktur original.

Algoritma CB* dapat mengkonstruksi struktur Bayesian Network dari database yang tidak lengkap.

Jumlah missing value tidak berpengaruh secara mutlak terhadap struktur Bayesian Network yang dihasilkan.

Algoritma CB* dapat mengkonstruksi struktur Bayesian Network tanpa informasi sebelumnya (Missing Information Principles).

KESIMPULAN Algoritma CB* mampu membangun struktur Bayesian Network dari

data yang tidak lengkap dengan syarat atribut basis data bernilai biner.

Perubahan struktur yang dihasilkan akibat pengaruh jumlah data yang sangat terbatas dan bisa pula diakibatkan oleh kombinasi atau pola data yang ada.

Kuantitas missing value dalam basis data yang menjadi masukan tidak berpengaruh secara mutlak terhadap struktur yang dihasilkan.

RUP memberikan kemudahan dalam melakukan perubahan-perubahan setiap tahapan yang ada karena sifatnya adalah iteratif.

SARAN

Mencoba melakukan pengembangan perangkat lunak untuk studi kasus yang memiliki data multinominal (tidak biner).

Mencoba mengkonstruksi struktur Bayesian Network dari studi kasus selain visit to Asia .

Perlu dilakukan analisis lebih lanjut tentang bagaimana distribusi missing value mempengaruhi struktur yang dihasilkan Algoritma CB*.

Mencoba melakukan pengujian performansi terhadap Algoritma CB* bukan hanya melakukan pengujian dari sisi fungsionalitas.

Mencoba membandingkan dengan Algoritma lain yang juga mengkombinasikan dua pendekatan seperti Algoritma CB*

TERIMA KASIH

ALGORITMA CB* Langkah 1 : Melakukan inisialisasi. Bertujuan untuk membuat

sebuah graf lengkap dari himpunan node V. Langkah 2 : Melakukan CI test untuk memeriksa independensi

antar node. Langkah 3 : Melakukan identifikasi collider (a c b)

terhadap semua CI relation (pasangan node yang tidak saling

terhubung oleh edge). Langkah 4 : Melakukan pemberian arah berdasarkan aturan yang

diturunkan dari konsep d-separation. Langkah 5 : Melakukan pendefinisian himpunan parent untuk

setiap node. Langkah 6 : Melakukan orientasi edge berdasarkan Bayesian

Scoring Function untuk edge yang masih undirected (edge tanpa arah) maupun bidirected (edge yang menghubungkan dua head node : a b)

ALGORITMA CB* Langkah 7 : Menghasilkan total order node dari DAG G dengan

melakukan topological sort.

Langkah 8 : Mendapatkan himpunan parent setiap node. Disini fase ke dua (Algoritma BC) dijalankan.

Langkah 9: Melakukan perbandingan antara new_prob dan old_prob. Jika new_Prob lebih besar dari old_Prob maka nilai old_Prob diisi dengan nilai dari new_Prob kemudian ord di-increment.

Langkah 10 : Tampilkan himpunan parent dari node i yang merupakan DAG yang dihasilkan pa.da fase I dan tampilkan old_prob atau nilai JPD dari DAG tersebut.

Penanganan Missing Value dengan Algoritma CB* (1)

Penanganan Missing Value dilakukan pada fase kedua dari Algoritma CB*

Sepenuhnya dilakukan di tahap bound.

Dilakukan perhitungan berdasarkan data yang tersedia untuk membentuk nilai interval estimasi.

Sama sekali tidak dilakukan perubahan atau manipulasi apapun terhadap missing value.

Jika missing value direpresentasikan dengan NULL, maka seluruh nilai NULL yang terdapat dalam basis data akan dibiarkan.

Penanganan Missing Value dengan Algoritma CB* (2)

Algoritma tidak mengestimasi apa nilai yang seharusnya muncul menggantikan nilai NULL tersebut.

Satu-satunya operasi yang dilakukan terhadap nilai-nilai NULL adalah menghitung jumlah kemunculan nilai NULL.

Jadi untuk pemeriksaan pasangan variabel, yang harus dipertimbangkan hanyalah berapa banyak nilai NULL yang ditemukan.

BC tidak memperdulikan apa kira-kira nilai yang hilang tersebut, data diproses sebagaimana adanya.