Penerapan Teknik Bayesian Network dalam Pengembangan Prototipe Aplikasi Web Content Mining
LAPORAN TUGAS AKHIR
Disusun sebagai syarat kelulusan tingkat sarjana
oleh : Miridhani Riani Ningrum / 13503023
PROGRAM STUDI TEKNIK INFORMATIKA SEKOLAH TEKNIK ELEKTRO DAN INFORMATIKA INSTITUT TEKNOLOGI BANDUNG 2007
ABSTRAKSI Pada Tugas Akhir ini dikaji berbagai tipe data pada web yang dapat ditambang dengan menggunakan teknik Bayesian Network (BN). Tipe data pada web terdiri dari content web, link antar halaman web, serta data perilaku pengunjung web. Dilain pihak, BN dapat digunakan pada permasalahan deskriptif (hubungan antara variabel) maupun prediktif (klasifikasi). Hasil analisis menunjukkan bahwa BN dapat diterapkan pada ketiga bidang kajian web mining, yaitu web content mining, web structure mining, serta web usage mining. Karena dapat digunakan pada ketiga bidang kajian tersebut, maka dipilih bidang kajian web content mining sebagai topik utama dari Tugas Akhir ini. Pengembangan prototipe difokuskan pada tujuan deskriptif. Aplikasi pembangunan BN untuk deskriptif mengimplementasikan algoritma TPDA. Karena masukan dari aplikasi tersebut berbentuk file basis data maka data harus melalui preprocessing terlebih dahulu. Untuk menangani bagian preprocessing, dibangun AGEHA, sebuah modul yang bertugas mengolah content e-mail menjadi data dalam bentuk yang terstruktur baik dalam bentuk format file teks maupun format file database. Sedangkan untuk bagian yang bertugas membangun struktur BN, akan digunakan Program TPDA yang telah dikembangkan oleh Laboratorium Basis Data. Pengujian dilakukan terhadap fungsionalitas memperlihatkan bahwa perangkat lunak telah dapat menjalankan seluruh kebutuhan yang didefinisikan. Sedangkan hasil akurasi dari struktur BN yang dibangun adalah sebesar 88,7%. Dari Tugas Akhir ini dapat disimpulkan bahwa BN dapat digunakan sebagai salah satu teknik dalam aplikasi web mining, baik untuk tujuan prediktif maupun deskriptif. Lebih lanjut, tipe data mentah pada web yang dapat di-mining dengan menggunakan BN mencakup seluruh bentuk data. Hasil akurasi dari penerapan BN pada web content mining juga menunjukkan hasil yang cukup baik. Kata kunci: data mining, web mining, Bayesian Network (BN), prediktif, deskriptif
i
Lembar Pengesahan Program Studi Teknik Informatika Penerapan Teknik Bayesian Network dalam Pengembangan Prototipe Aplikasi Web Content Mining
Tugas Akhir Program Studi Teknik Informatika ITB
Oleh Miridhani Riani Ningrum / 13503023
Telah disetujui dan disahkan sebagai laporan tugas akhir di Bandung, pada tanggal 1 Oktober 2007
Pembimbing
Ir. G. A. Putri Saptawati, M.Comm NIP. 132127666
ii
KATA PENGANTAR
Puji syukur Penulis panjatkan ke hadirat Tuhan Yang Maha Esa sehingga berkat rahmat-Nya, Penulis dapat melaksanakan tugas akhir serta dapat menyelesaikan laporan tugas akhir sesuai waktu yang telah ditentukan. Laporan ini disusun sebagai syarat kelulusan tingkat sarjana. Pada kesempatan ini, Penulis juga ingin mengucapkan terima kasih kepada pihakpihak yang telah memberikan bantuan dan bimbingan selama pelaksanaan tugas akhir dan penyusunan laporan tugas akhir. Ucapan terima kasih disampaikan kepada: 1. Bapak Dr. Ing. H. M. Sukrisno Mardiyanto selaku Ketua Program Studi Teknik Informatika ITB. 2. Ibu Ir. G. A. Putri Saptawati, M. Comm. selaku dosen pembimbing yang telah membimbing dan memberikan masukan selama pelaksanaan tugas akhir. 3. Ibu Ir. Sri Purwanti, M.Sc, selaku dosen penguji pada presentasi proposal dan seminar Tugas Akhir ini atas seluruh masukan dan arahannya. 4. Ibu Yani Widyani S.T., M.T. selaku dosen pra sidang dan sidang tugas akhir atas seluruh masukan dan arahannya. 5. Ibu Tricya E. Widagdo, S.T., M. Sc. selaku dosen penguji pada sidang tugas akhir atas seluruh masukan dan arahannya. 6. Ibu Nur Ulfa Maulidevi, S.T., M. Sc. selaku dosen mata kuliah IF40Z1 Tugas Akhir 1 dan IF40Z2 Tugas Akhir 2. 7. Seluruh staf dosen program studi Teknik Informatika ITB yang telah membimbing Penulis dalam perjalanannya menyelesaikan pendidikan sarjana. 8. Bapak Ade, Ibu Nurhayati, dan Bapak Rasidi serta pegawai tata usaha Program Studi Teknik Informatika ITB.
iii
iv
9. Ayah, ibu, adik, serta seluruh keluarga penulis atas doa, dukungan, serta cintanya yang tiada batas. 10. Yudi Rizkiadi dan Ronny Hendrawan, teman terdekat Penulis yang selalu memberikan dukungan dan nasehat selama perjalanan Penulis di Teknik Informatika ITB. 11. Dini Rahmawati, Eunice Sherta Ria, Wulan Widyasari, Febrian Aris Rosadi, Riza Ramadhan, dan Audi Primandhanty, teman-teman topik data mining yang telah berjuang bersama dalam Tugas Akhir ini. 12. Brahmasta Adipradana, Adistya Alindita, Amudi Sebastian, Ridwan, serta teman-teman penulis lainnya yang telah membantu dan memberikan dukungan selama pengerjaan Tugas Akhir ini. 13. Teman-teman asisten RPL angkatan 2004 dan angkatan 2005 atas seluruh tawa dan canda selama pengerjaan Tugas Akhir ini. 14. Seluruh teman-teman Teknik Informatika angkatan 2003 yang telah berjalan bersama selama bangku perkuliahan. 15. Semua pihak yang telah membantu Penulis yang tidak dapat disebutkan satu per satu. Akhir kata, disadari masih terdapat kekurangan dalam laporan tugas akhir ini. Untuk itu, diharapkan kritik dan saran dari pembaca. Terima kasih. Oktober 2007
Penulis
DAFTAR ISI
ABSTRAKSI
..................................................................................................... i
Lembar Pengesahan Program Studi Teknik Informatika ....................................... ii KATA PENGANTAR ........................................................................................... iii DAFTAR ISI
.................................................................................................... v
DAFTAR GAMBAR ........................................................................................... viii DAFTAR TABEL .................................................................................................. ix DAFTAR ISTILAH ................................................................................................ x DAFTAR SIMBOL ............................................................................................... xi BAB I PENDAHULUAN .....................................................................................I-1 I.1
Latar Belakang.........................................................................................I-1
I.2
Rumusan Masalah....................................................................................I-2
I.3
Tujuan ......................................................................................................I-2
I.4
Batasan Masalah ......................................................................................I-3
I.5
Metodologi...............................................................................................I-3
I.6
Sistematika Pembahasan..........................................................................I-4
BAB II DASAR TEORI ..................................................................................... II-1 II.1
Reasoning dan Kausalitas ...................................................................... II-1
II.2
Causal Network ..................................................................................... II-2
II.3
Bayesian Network .................................................................................. II-6
II.3.1
Pendahuluan .................................................................................... II-6
II.3.2
Komponen Bayesian network ......................................................... II-9
II.3.3
Joint Probability Distribution........................................................ II-10
II.3.4
d-seperation ................................................................................... II-11
II.3.5
Konstruksi Bayesian network........................................................ II-13
II.4
World Wide Web .................................................................................. II-15
II.4.1
Pendahuluan .................................................................................. II-15
II.4.2
Struktur Global.............................................................................. II-16 v
vi
II.5
Data Mining......................................................................................... II-17
II.5.1
Pendahuluan .................................................................................. II-17
II.5.2
Preprocessing................................................................................ II-18
II.6
Web mining .......................................................................................... II-18
II.6.1
Web content mining....................................................................... II-20
II.6.2
Web usage mining ......................................................................... II-21
II.6.3
Web structure mining .................................................................... II-23
BAB III ANALISIS PENYELESAIAN MASALAH ........................................ III-1 III.1
Analisis Konsep Bayesian network ................................................... III-1
III.2
Analisis Bidang Kajian Web mining yang Menjadi Fokus................ III-2
III.3
Analisis Studi Kasus.......................................................................... III-5
III.3.1
Deskripsi Umum ......................................................................... III-5
III.3.2
Deskripsi Data Masukan............................................................. III-5
III.3.3
Analisis Preprocessing ............................................................... III-6
III.3.4
Analisis Aplikasi Web Mining .................................................... III-7
BAB
IV
ANALISIS,
PERANCANGAN,
DAN
IMPLEMENTASI PERANGKAT LUNAK .........................IV-1 IV.1
Analisis Metodologi Pengembangan.................................................IV-1
IV.2
Analisis Perangkat Lunak..................................................................IV-2
IV.2.1
Deskripsi Umum .........................................................................IV-2
IV.2.2
Fitur Utama Perangkat Lunak.....................................................IV-2
IV.2.3
Model Use Case ..........................................................................IV-3
IV.3
Analisis Use Case Membangun Struktur BN ....................................IV-6
IV.3.1
Deskripsi Umum Perangkat Lunak Program TPDA...................IV-6
IV.3.2
Batasan Umum Perangkat Lunak ...............................................IV-7
IV.4
Analisis Use Case Preprocessing......................................................IV-8
IV.4.1
Deskripsi Umum .........................................................................IV-8
IV.4.2
Realisasi Use Case Tahap Analisis AGEHA..............................IV-8
IV.5
Perancangan Perangkat Lunak ........................................................IV-11
IV.5.1
Class diagram perancangan ......................................................IV-11
vii
IV.5.2 IV.6
Sequence diagram perancangan................................................IV-13
Implementasi Perangkat Lunak .......................................................IV-14
IV.6.1
Batasan Perangkat Lunak .........................................................IV-14
IV.6.2
Lingkungan Pengembangan......................................................IV-14
IV.6.3
Lingkungan Perangkat Keras....................................................IV-14
IV.6.4
Input Data .................................................................................IV-15
IV.6.5
Output Data...............................................................................IV-15
BAB V PENGUJIAN PERANGKAT LUNAK ................................................. V-1 V.1
Tujuan Pengujian ................................................................................... V-1
V.2
Lingkungan Pengujian ........................................................................... V-1
V.3
Data Pengujian....................................................................................... V-1
V.4
Skenario Pengujian ................................................................................ V-2
V.5
Hasil Pengujian ...................................................................................... V-3
V.6
Kesimpulan Hasil Pengujian.................................................................. V-4
BAB VI KESIMPULAN DAN SARAN ...........................................................VI-1 VI.1
Kesimpulan........................................................................................VI-1
VI.2
Saran ..................................................................................................VI-1
DAFTAR PUSTAKA ........................................................................................... xii LAMPIRAN A KONSEP DATA MINING ....................................................... A-1 LAMPIRAN B KONSEP BAYESIAN NETWORK ........................................ B-1 LAMPIRAN C DOKUMEN EMAIL.................................................................. C-1 LAMPIRAN D DAFTAR STOPWORDS........................................................ D-1 LAMPIRAN E ALGORITMA PEMBANGUN STRUKTUR BN............................................................................................E-1 LAMPIRAN F RANCANGAN ANTARMUKA AGEHA..................................F-1 LAMPIRAN G HASIL AGEHA ........................................................................ G-1 LAMPIRAN H PENGUJIAN FUNGSIONALITAS ........................................ H-1 LAMPIRAN I HASIL PROGRAM TPDA..........................................................I-1
DAFTAR GAMBAR
Gambar 1. Bentuk serial connection................................................................... II-3 Gambar 2. Bentuk diverging connection ............................................................ II-4 Gambar 3. Bentuk converging connection.......................................................... II-4 Gambar 4. Contoh causal network [JEN01] ....................................................... II-6 Gambar 5. Representasi graf untuk studi kasus medis [NEA04]....................... II-8 Gambar 6. Representasi graf untuk studi kasus medis [NEA04]..................... II-10 Gambar 7. DAG yang mengilustrasikan Chain Blocking ................................. II-13 Gambar 8. Perubahan versi dari struktur web redhat.com [ZHA03] ................ II-16 Gambar 9. Arsitektur web mining [GAL01] .................................................... II-19 Gambar 10. Search engine sebagai contoh web content mining [MAX04] ...... II-21 Gambar 11. Contoh web access log .................................................................. II-23 Gambar 12. Skema kerja data cleaning dari aplikasi preprocessing................. III-9 Gambar 13. Contoh Binary Search Tree yang dibangun ................................. III-10 Gambar 14. Skema solusi yang ditawarkan ..................................................... III-11 Gambar 15. Diagram Use Case..........................................................................IV-4 Gambar 16. Tampilan Program TPDA ..............................................................IV-7 Gambar 17. Diagram kelas analisis....................................................................IV-8 Gambar 18. Sequence diagram analisis ...........................................................IV-10 Gambar 19. Diagram kelas perancangan .........................................................IV-11 Gambar 20. Sequence diagram perancangan ...................................................IV-13 Gambar 21. Sequence diagram perancangan ...................................................... V-3 Gambar 22. Langkah-langkah dalam data mining.............................................. A-1 Gambar 23. DAG yang mengilustrasikan Markov condition.............................. A-1 Gambar 24. DAG yang mengilustrasikan Markov Blanket ................................ A-3
viii
DAFTAR TABEL
Tabel 1. Representasi nilai dari variabel-variabel BN [NEA04] ........................ II-8 Tabel 2. Contoh data mentah yang tersedia pada web access log..................... II-22 Tabel 3. Tabel Rangkuman Bidang Kajian Web Mining .................................. II-25 Tabel 4. Rangkuman analisis terhadap bidang kajian web mining .................... III-4 Tabel 5. Klasifikasi kelas ................................................................................... III-6 Tabel 6. Daftar kebutuhan fungsional................................................................IV-3 Tabel 7. Daftar kebutuhan fungsional................................................................IV-3 Tabel 8. Definisi Aktor ......................................................................................IV-4 Tabel 9. Definisi Use Case.................................................................................IV-5 Tabel 10. Daftar Tanggung Jawab dan Atribut Setiap Kelas Analisis...............IV-9 Tabel 11. Daftar Tanggung Jawab dan Atribut Setiap Kelas Perancangan .....IV-12
ix
DAFTAR ISTILAH
Istilah Arc Asam amino Building blocks Causal network DAG DAG-faithful d-separation Edge Event
Definisi Directed edge di dalam sebuah graf Molekul dasar pembentuk protein Unit dasar yang membangun sistem tertentu Grafik yang menyatakan proses causal Directed acyclic graph Suatu dataset adalah DAG-faithful jika model probabilisitiknya adalah struktur DAG. Directed separation dari dua buah simpul dalam graf berdasarkan set of rules Hubungan antara sepasang simpul Kejadian
x
DAFTAR SIMBOL
Simbol Diagram Use Case
Penjelasan Aktor, merepresentasikan seseorang atau sesuatu yang berinteraksi dengan sistem yang akan dibangun. Use case, merepresentasikan fungsionalitas dari sistem yang akan dibangun. Keterhubungan, merepresentasikan keterhubungan antar use cases atau antara aktor dengan use case, dimana aktor tertentu dapat memanfaatkan fungsionalitas tertentu dari sistem yang akan dibangun. Generalisasi, merepresentasikan apakah suatu use case merupakan turunan dari use case lain atau suatu aktor merupakan turunan dari aktor lain.
Diagram Sequence Aktor, merepresentasikan seseorang atau sesuatu yang berinteraksi dengan sistem yang akan dibangun. Pemanggilan fungsi pada objek lain. Pemanggilan fungsi di dalam objek. Pengembalian nilai sebagai hasil dari pemanggilan fungsi. Diagram Kelas Paket. Merepresentasikan kumpulan paket atau kelas. Dapat diisi dengan nama paket. Dependency, menyatakan keterhubungan antar paket atau antar kelas.
xi
