APLIKASI PEMBANGUNAN BAYESIAN NETWORK PADA DATA MINING
TESIS Karya tulis sebagai salah satu syarat untuk memperoleh gelar Magister dari Institut Teknologi Bandung
Oleh
HENGKY SIPAYUNG NIM : 23505015 Program Studi Magister Informatika
SEKOLAH TEKNIK ELEKTRO DAN INFORMATIKA INSTITUT TEKNOLOGI BANDUNG 2008
ABSTRAK
APLIKASI PEMBANGUNAN BAYESIAN NETWORK PADA DATA MINING Oleh HENGKY SIPAYUNG NIM : 23505015
Data mining adalah proses mengekstrasi data untuk mendapatkan pengetahuan dari kumpulan data yang besar. Salah satu metode data mining adalah klasifikasi yaitu proses pencarian model klasifikasi yang dapat membedakan objek label kelasnya. Bayesian Networks adalah salah satu teknik yang dapat dipakai untuk membangun model klasifikasi. Komponen Bayesian Network terdiri dua komponen yaitu struktur DAG yang menggambarkan hubungan kausalitas antar atribut data dan sebuah tabel yang berisi probabilitas bersyarat berdasarkan atribut sebelumnya.
TPDA (Three Phase Dependency Analysis) adalah salah satu algoritma untuk membangun struktur Bayesian Networks. Algoritma ini membangun struktur Bayesian Networks berdasarkan nilai informasi yang terdapat pada dua node. Semakin besar informasi yang mengalir antara dua node maka semakin besar peluang untuk menghubungkan pasangan node tersebut. TPDA terdiri dari tiga fase. Fase pertama disebut drafting yaitu fase penentuan graph awal untuk menghubungkan dua node. Fase kedua disebut thickening yaitu fase menambahkan garis antar dua node yang tidak dapat dipisahkan. Fase ketiga disebut thinning yaitu fase di mana setiap garis antara dua node akan diuji untuk menentukan apakah garis tersebut dapat di hapus atau tidak.
Berdasarkan hasil evaluasi kinerja inferensi kelas target menggunakan struktur Bayesian Network yang dihasilkan oleh aplikasi pada tesis ini, terlihat bahwa tingkat akurasi inferensi cukup tinggi. Namun demikian ketika hasil struktur Bayesian
ii
Networks yang dihasilkan tesis ini dibandingkan dengan struktur yang dihasilkan BN PowerConstructor terdapat perbedaan struktur yang dihasilkan. Oleh sebab itu, aplikasi yang dikembangkan pada tesis ini masih memerlukan perbaikan supaya struktur yang dihasilkan akan sama, mengingat BN PowerConstructor adalah aplikasi yang telah terbukti kebenarannya dalam membangun struktur Bayesian Networks dengan mengimplementasikan algoritma TPDA.
Kata kunci : data mining, klasifikasi, inferensi, Bayesian Networks
iii
ABSTRACT DEVELOPMENT OF APPLICATION OF BAYESIAN NETRWORKS AT DATA MINING
By HENGKY SIPAYUNG NIM : 23505015
Data mining is a process of extracting data to get knowledge from large data repositories. One of method of data mining is classification that is process of seeking model of classification that able to differentiate its class label object. Bayesian Networks is one of technique that able to use to build classification model. Component Bayesian Network compose two component that is DAG structure depicting causality relationship among data attribute and a containing tables of conditional probability based on previous attribute called CPT.
TPDA (Three Phase Dependency Analysis) is one of algorithm to build structure of Bayesian Networks. This algorithm builds structure of Bayesian Networks based on value of information is found on two node. Ever greater of value of information can flow of between two node hence is ever greater of opportunity to connect of the nodes. TPDA consist of three phase. First phase is drafting that is phase to determine early graph to connect a pairs of node. Second phase is thickening that is phase that add edge to current structure when a pairs of node can not separated. Third phase is thinning that is phase where each of edge is examined and it will be removed if two node if found to be separated.
Based on result of performance evaluation of class inference using structure of Bayesian Network yielded by application in this thesis, seen that level of inference accuration is high enough. But when structure of Bayesian Networks yielded by
iv
application in this thesis is compared with structure yielded by
BN
PowerConstructor there are difference between of them. On that account, the application has developed in this thesis still need repaired to get same structure, because BN PowerConstructor which is developed by implementing TPDA algorithm have proven its truth.
Keyword : data mining, classification, inference, Bayesian Networks.
v
HALAMAN PENGESAHAN APLIKASI PEMBANGUNAN BAYESIAN NETWORK PADA DATA MINING
Oleh Hengky Sipayung Nim : 23505015
Program Studi Magister Informatika Institut Teknologi Bandung
Menyetujui Pembimbing
Tanggal 27 Juni 2008
(Dr.Ing. Ir. Benhard Sitohang)
vi
PEDOMAN PENGGUNAAN TESIS
Tesis S2 yang tidak dipublikasikan terdaftar dan tersedia di Perpustakaan Institut Teknologi Bandung, dan terbuka untuk umum dengan ketentuan bahwa hak cipta ada pada pengarang dengan mengikuti aturan HaKI yang berlaku di Institut Teknologi Bandung. Referensi kepustakaan diperkenankan dicatat, tetapi pengutipan atau peringkasan hanya dapat dilakukan seizin pengarang dan harus disertai dengan kebiasaan ilmiah untuk menyebutkan sumbernya. Memperbanyak atau menerbitkan sebagian atau seluruh tesis haruslah seizin Direktur Program Pascasarjana, Institut Teknologi Bandung.
vii
Dipersembahkan untuk Orang tuaku : Bpk T. Barth Sipayung dan Ibu Asramawati Br Purba P. untuk istriku : Sri Umi Pujawati dan untuk anak-anakku : Gita Sri Dewi Asmaradana Br. Sipayung dan Azahra Annisa Putri Br. Sipayung
viii
KATA PENGANTAR
Dengan mengucap syukur Alhamdulillah kepada Allah S.W.T, akhirnya penulis dapat menyelesaikan tesis ini sebagai syarat kelulusan Magister Informatika
di
Institut Teknologi Bandung.
Topik yang dipilih berkaitan dengan persoalan data mining, khususnya rekayasa perangkat lunak untuk membangun aplikasi data mining. Metode data mining yang dipilih adalah metode klasifikasi menggunakan Bayesian Networks. Sedangkan metodologi pengembangan perangkat lunak menggunakan metodologi Rational Unified Process. Struktur Bayesian Network dibangun dengan menggunakan algoritma TPDA.
Diharapkan semua yang telah dilakukan penulis ini dapat memberikan manfaat sebesarnya khususnya dalam rekayasa perangkat lunak pada data mining.
Bandung, 27 Juni 2008
Penulis
ix
UCAPAN TERIMA KASIH Penulis mengucapkan terima kasih sebesar–besarnya kepada semua pihak yang telah membantu penulis dalam menyelesaikan tesis ini : 1.
Bapak Dr. Ing. Ir. Benhard Sitohang selaku pembimbing I yang telah menyediakan waktu, tenaga dan pikiran selama proses bimbingan.
2.
Ibu Dr. Ir. G.A. Putri Saptawati, M.Comm dan Bapak Dr. techn. Saiful Akbar, S.T, M.T yang telah memberikan kritik dan saran untuk perbaikan tesis ini pada review proposal, seminar, prasidang dan sidang tesis.
3.
Ibu Dr.Ir. Inggriani Liem selaku dosen wali yang terus menerus memberikan dorongan untuk menyelesaikan tesis ini.
4.
Istri dan anakku yang telah memberikan semangat bagi penulis untuk menyelesaikan tesis ini.
5.
Orang tuaku tercinta Bapak T. Barth Sipayung dan Ibu Asramawaty Br. Purba Tambak yang telah memberikan dorongan moril dan materil.
6.
Pak Ade, Ibu Nurhayati dan seluruh staf S2 informatika ITB
7.
Teman–teman RPL 2005.
Pihak-pihak lain yang tidak bisa disebutkan satu persatu.
x
DAFTAR ISI ABSTRAK ............................................................................................................. ii ABSTRACT ........................................................................................................... iv HALAMAN PENGESAHAN............................................................................... vi PEDOMAN PENGGUNAAN TESIS ................................................................. vii KATA PENGANTAR........................................................................................... ix UCAPAN TERIMA KASIH ................................................................................. x DAFTAR ISI ......................................................................................................... xi DAFTAR LAMPIRAN ....................................................................................... xiv DAFTAR GAMBAR............................................................................................ xv DAFTAR TABEL .............................................................................................. xvii DAFTAR ISTILAH ..........................................................................................xviii DAFTAR SIMBOL ............................................................................................. xix BAB. I.
PENDAHULUAN .............................................................................. 1
I.1
Latar Belakang Masalah............................................................................... 1
I.2
Rumusan Masalah ........................................................................................ 3
I.3
Tujuan .......................................................................................................... 4
I.4
Batasan Masalah .......................................................................................... 4
I.5
Metodologi Penelitian .................................................................................. 5
I.6
Sistematika Penulisan .................................................................................. 6
BAB. II.
TINJAUAN PUSTAKA ..................................................................... 8
II.1 Definisi Data Mining ................................................................................... 9 II.2 Beberapa Metode untuk Data Mining .......................................................... 9 II.2.1 Aturan Asosiasi ............................................................................................ 9 II.2.2 Klasifikasi .................................................................................................... 9 II.2.3 Clustering ................................................................................................... 10 II.3 Bayesian Networks .................................................................................... 10 II.4 Fundamental Probabilitas Bayesian ........................................................... 11 II.4.1 Aksioma ..................................................................................................... 11 II.4.2 Prior Probabilitas dan Probabilitas Bersyarat ........................................... 12 II.5 Dasar Bayesian Networks .......................................................................... 14 II.5.1 Definisi Bayesian Networks....................................................................... 14
xi
II.5.2 Kaidah Aturan Berantai ............................................................................. 16 II.5.3 Topologi Jaringan Bayesian Networks ...................................................... 16 II.5.3.1
Koneksi Serial .................................................................................... 16
II.5.3.2
Koneksi Divergen .............................................................................. 17
II.5.3.3
Koneksi Konvergen ........................................................................... 17
II.5.4 Bebas Bersyarat dan d-Separation ............................................................ 18 II.6 Contoh Mengambil Keputusan Menggunakan Bayesian Networks .......... 19 II.7 Algoritma untuk Membangun Struktur Bayesian Networks...................... 21 II.7.1 Three Phase Dependency Analysis (TPDA) .............................................. 22 II.7.1.1
Konsep Dasar TPDA ......................................................................... 23
II.7.2 Algoritma TPDA tanpa Pengurutan Node ................................................. 25 II.8 Kajian Studi Literatur TPDA .................................................................... 31 II.9 Visualisasi pada Data Mining ................................................................... 33 II.9.1 Histogram ................................................................................................... 34 II.9.2 Pie Chart..................................................................................................... 35 II.9.3 Bar/Colum Chart ........................................................................................ 36 II.10 Aplikasi Visualisasi Bayesian Networks ................................................... 37 II.11 Visualisasi Struktur Bayesian Networks .................................................... 38 BAB. III.
ANALISA PERMASALAHAN ...................................................... 40
III.1 Studi Kasus Data Mining ........................................................................... 40 III.1.1
Kriteria Nasabah Aktif dan Nasabah Produktif ................................. 40
III.1.1.1
Nasabah Produktif.............................................................................. 41
III.1.1.2
Nasabah Aktif .................................................................................... 41
III.1.2
Attribut Data ...................................................................................... 41
III.2 Aplikasi Klasifikasi dan Visualisasi Data Mining yang di Kembangkan. . 44 III.3 Visualisasi dan Prediksi Kelas Nasabah Bank ........................................... 45 III.4 Evaluasi Performansi Metode Klasifikasi .................................................. 46 BAB. IV.
ANALISA DAN PERANCANGAN ............................................... 48 PERANGKAT LUNAK .................................................................. 48
IV.1 Analisa Perangkat Lunak ........................................................................... 48 IV.1.1
Deskripsi Umum Perangkat Lunak .................................................... 48
IV.1.2
Metode Pengembangan Perangkat Lunak SIDAMIBAYES ............. 48
xii
IV.1.3
Asumsi dan Batasan Perangkat Lunak............................................... 50
IV.1.4
Fungsi Utama Perangkat Lunak ......................................................... 51
IV.1.5
Diagram Use Case ............................................................................. 51
IV.1.5.1
Definisi Actor .................................................................................... 52
IV.1.5.2
Definisi Use Case............................................................................... 52
IV.1.5.3
Skenario Use Case ............................................................................. 52
IV.1.6
Pemodelan Kelas Tahap Analisis ...................................................... 53
IV.1.6.1
Identifikasi Kelas ............................................................................... 53
IV.1.6.2
Identifikasi Interaksi Antar Kelas ...................................................... 54
IV.2 Perancangan Perangkat Lunak ................................................................... 55 IV.2.1
Daftar Kelas Tahap Perancangan ....................................................... 56
IV.2.1.1
Realisasi Use Case Tahap Perancangan (Diagram Kelas) ................. 56
IV.2.1.2
Deskripsi Atribut dan Operasi ........................................................... 57
IV.2.2
Interaksi Antar Kelas (Sequence Diagram) ....................................... 58
IV.2.3
Perancangan Struktur Data ................................................................ 59
IV.2.4
Perancangan Antar Muka (Layar)...................................................... 60
BAB. V.
IMPLEMENTASI DAN PENGUJIAN .......................................... 63
V.1 Implementasi SIDAMIBAYES.................................................................. 63 V.1.1 Implementasi Lingkungan SIDAMIBAYES ............................................. 63 V.1.2 Implementasi Kelas .................................................................................... 64 V.1.3 Implementasi Antar Muka SIDAMIBAYES ............................................. 64 V.2 Pengujian SIDAMIBAYES ....................................................................... 70 V.2.1 Prosedur Pengujian .................................................................................... 70 V.2.2 Hasil Pengujian .......................................................................................... 71 V.3 Evaluasi Kinerja Model Klasifikasi ........................................................... 73 V.4 Analisa Visualisasi Hubungan Kausalitas Struktur yang Dihasilkan ........ 74 V.4.1 Berdasarkan Hasil Evaluasi Kinerja Model Klasifikasi ............................. 74 V.4.2 Berdasarkan Aplikasi BN PowerConstructor ............................................ 74 BAB. VI.
KESIMPULAN DAN SARAN ........................................................ 77
VI.1 Kesimpulan ................................................................................................ 77 VI.2 Saran........................................................................................................... 77 DAFTAR PUSTAKA ........................................................................................... 79
xiii
DAFTAR LAMPIRAN LAMPIRAN A. Aplikasi Bayesian Networks................................................... 81 A.1. Paket Aplikasi BN PowerSoft .................................................................... 81 A.2. GeNie/Smile ............................................................................................... 82 LAMPIRAN B. Skenario Use Case ................................................................... 84 B.1. Skenario Use Case untuk Konfigurasi ....................................................... 84 B.2. Skenario Use Case untuk Bangun Struktur BN ......................................... 84 B.3. Skenario Use Case untuk Visualisasi Struktur Bayesian Networks ......... 84 LAMPIRAN C. Daftar Atribut dan Operasi Kelas .......................................... 85 C.1. Daftar atribut dan Operasi Kelas FormUtama ........................................... 85 C.2. Daftar atribut dan Operasi Kelas FormKonfigurasi ................................... 85 C.3. Daftar atribut dan Operasi Kelas FormVisBNChart .................................. 86 C.4. Daftar atribut dan Operasi Kelas FormVisBNCircle ................................. 86 C.5. Daftar atribut dan Operasi Kelas FormPrediksiKelas ................................ 86 C.6. Daftar atribut dan Operasi Kelas NodeBN ................................................ 87 C.7. Daftar atribut dan Operasi Kelas NodeStateProb ...................................... 87 C.8. Daftar atribut dan Operasi Kelas DataTabel .............................................. 88 C.9. Daftar atribut dan Operasi Kelas CPT ....................................................... 88 C.10. Daftar atribut dan Operasi Kelas Temp_PairNode .................................... 89 C.11. Daftar atribut dan Operasi Kelas PairNode................................................ 89 LAMPIRAN D. Sequence Diagram ................................................................... 90 D.1. Sequence Diagram untuk Use Case BangunStrukturBN ........................... 90 D.2. Sequence Diagram untuk Use Case Visualisasi Struktur Bayes ................ 91 D.3. Sequence Diagram untuk Use Case Prediksi Kelas ................................... 92 LAMPIRAN E. Rancangan Antar Muka .......................................................... 93 E.1. Rancangan Antar Muka Form Konfigurasi................................................ 93 E.2. Rancangan Antar Muka Form Utama dan Menu ....................................... 93 E.3. Rancangan Antar Muka Form Visualisasi BN Circle Node ..................... 94 E.4. Rancangan Antar Muka Form Visualisasi BN Bar chart Node ................. 94 E.5. Rancangan Antar Muka Form CPT untuk setiap Node ............................. 95 E.6. Rancangan Antar Muka Form untuk memprediksi kelas target. ............... 95
xiv
DAFTAR GAMBAR Gambar 1.1. Proses membangun model klasifikasi [HAN02]......................................2 Gambar 2.1. Model Klasifikasi sebagai Fungsi F(x) [TAN01] ................................10 Gambar 2.2. Contoh sederhana Bayesian Networks [JIE96]. ....................................11 Gambar 2.3. Contoh struktur sebuah DAG ................................................................15 Gambar 2.4. Contoh struktur Bayesian Networks (CPT tidak ditampilkan) ..............16 Gambar 2.5. Koneksi Serial [JEN96]. ........................................................................17 Gambar 2.6. Koneksi Divergen [JEN96] ....................................................................17 Gambar 2.7. Koneksi Konvergen [JEN96] .................................................................18 Gambar 2.8. Struktur BN untuk Contoh Kasus Klassifikasi [HAN01]. .....................19 Gambar 2.9. Contoh Multi Koneksi pada Bayesian Networks [JIE01] ......................23 Gambar 2.9. Contoh struktur BN untuk implementasi TPDA[JIE01]........................27 Gambar 2.10. Prosedur edge_needed_A .....................................................................29 Gambar 2.12. Prosedur Orients_Edge ........................................................................31 Gambar 2.10. Histogram “waktu bepergian” sensus penduduk Amerika 2000. ........35 Gambar 2.11. Contoh sebuah Pie Chart......................................................................36 Gambar 2.12. Contoh bar chart untuk representasi pemilu Eropa 2004. ...................36 Gambar 2.13. Contoh bar chart menampilkan pemilu tahun 2004 dan 1999 ............37 Gambar 2.14. Contoh Tahapan Visualisasi DAG [HUNG99] ...................................38 Gambar 3.1. Cuplikan Tabel Data Bank dalam format MS. Access ..........................43 Gambar 4.1. Diagram Use Case SIDAMIBAYES .....................................................52 Gambar 4.2. Diagram interaksi antar kelas pada tahap analisis .................................55 Gambar 4.3. Diagram Kelas SIDAMIBAYES ...........................................................58 Gambar 4.4 Sequence Diagram Use Case Konfigurasi ..............................................59 Gambar 5.1. Hasil Implementasi Antar Muka Form Utama ......................................65 Gambar 5.2. Implementasi antar muka Form Konfigurasi .........................................66 Gambar 5.3. Implementasi Antar Muka Form Visualisasi BN Bar chart ...................67 Gambar 5.4. Implementasi Antar Muka Form Visualisasi BN Circle ........................68 Gambar 5.5. Implementasi Antar Muka Form Prediksi .............................................69 Gambar 5.6. Implementasi Antar Muka CPT .............................................................69 Gambar 5.7. Struktur BN pada BN PowerConstructor...............................................75
xv
Gambar 5.8. Struktur BN pada SIDAMIBAYES .......................................................76 Gambar A.1. Tampilan Visualisasi Struktur BN pada BN PowerConstructor ...........82 Gambar A.2. Visualisasi pada Genie/SMILE untuk distribusi probabilitas ...............83
xvi
DAFTAR TABEL
Tabel 2.1 Contoh CPT untuk P(X | Y)........................................................................13 Tabel 2.2 Contoh JPD untuk P(X,Y) ..........................................................................13 Tabel 3.1 Atribut Trainingset .....................................................................................42 Tabel 4.1 Actor SIDAMIBAYES ...............................................................................52 Tabel 4.2. Use case SIDAMIBAYES .........................................................................53 Tabel 4.3. Identifikasi Kelas Analisis .........................................................................54 Tabel 4.4 Struktur Data SIDAMIBAYES (Kelas DataTabel) ...................................60 Tabel 4.5 Daftar Antar Muka Pengguna SIDAMIBAYES ........................................61 Tabel 5.1 Lingkungan Implementasi SIDAMIBAYES ..............................................63 Tabel 5.2 Daftar Implementasi Kelas .........................................................................64 Tabel 5.3. Rencana Pengujian Berdasarkan Fungsi (Use Case) .................................71 Tabel 5.4. Hasil Pengujian Use Case Konfigurasi .....................................................71 Tabel 5.5. Hasil Pengujian Use Case Bangun Struktur BN .......................................71 Tabel 5.6. Hasil Pengujian Use Case Visualisasi Struktur BN ..................................72 Tabel 5.7. Hasil Pengujian Use Case Prediksi Kelas .................................................73 Tabel 5.8 Hasil Evaluasi Kinerja Model Klasifikasi ..................................................74
xvii
DAFTAR ISTILAH
Training Set
:
Data latih, yaitu data yang digunakan untuk membangun model pengklasifikasi.
Test Set
:
Data uji, yaitu data yang digunakan untuk mengukur akurasi model
Classifier
:
Model klasifikasi
Decision Tree
:
Model pengklasifikasi yang berupa pohon keputusan
CPT
:
Singkatan dari (Conditional Probability Table), yaitu tabel yang berisi probabilitas suatu node berdasarkan node lain.
Learning
:
Proses pembelajaran untuk memperoleh model pengklasifikasi
Dataset
:
Kumpulan data
Edge
:
Garis yang menghubungkan simpul
Noise data
:
Data yang bersifat mengganggu / berbeda dengan nilai umumnya data
Missing value
:
Nilai yang kosong
Edge
:
Garis yang menghubungkan antara satu node ke node lain pada struktur Bayesian Network..
Bayesian network
:
Salah satu pendekatan Bayesian untuk klasifikasi data dengan membuat suatu graph untuk menggambarkan hubungan antar atribut
DAG.
:
Node probability table:
Graph berarah yang tidak siklik Tabel peluang dari node – node yang ada pada Bayesian network.
Data pre-processor
:
Melakukan perbaikan data untuk menghilangkan noise data atau missing value sebelum dijadikan training data dan testing data.
xviii
DAFTAR SIMBOL
:
Aktor yaitu orang yang akan menjalankan aplikasi.
:
Boundary atau obyek antar muka, yaitu kelas yang berhubungan langsung dengan aktor / lingkungan.
:
Control, yaitu kelas yang memuat fungsi–fungsi transaksional yang menghubungkan boundary dan entity.
:
Entity, yaitu kelas yang berfungsi untuk menyimpan data / informasi yang digunakan dalam sistem.
xix
