PEMBANGUNAN PERANGKAT LUNAK STREAMING ENSEMBLE ALGORITHM (SEA): ALGORITMA UNTUK KLASIFIKASI DALAM SKALA BESAR
TESIS Karya tulis sebagai salah satu syarat untuk memperoleh gelar Magister dari Institut Teknologi Bandung
Oleh
GIRI DHANESWARA NIM : 23505012
PROGRAM STUDI MAGISTER INFORMATIKA SEKOLAH TEKNIK ELEKTRO DAN INFORMATIKA INSTITUT TEKNOLOGI BANDUNG 2008
ABSTRAK PEMBANGUNAN PERANGKAT LUNAK STREAMING ENSEMBLE ALGORITHM (SEA): ALGORITMA UNTUK KLASIFIKASI DALAM SKALA BESAR Oleh Giri Dhaneswara NIM : 23505012 Pada awalnya data mining belum dapat menangani data yang bersifat stream (data yang terus-menerus bertambah dan semakin cepat laju pertambahannya), namun sekarang muncul kebutuhan untuk dapat menyelesaikan permasalahan data stream. Banyak peneliti melakukan penelitian sehingga data mining dapat menangani permasalahan data streams. Hal ini dikenal sebagai mining data stream. Dalam data streams juga terdapat permasalahan yang lain yaitu concept drift (perubahan konsep pada model yang telah dibangun). Pada tahun 2001, sebuah algoritma yang diberi nama Streaming Ensemble Algorithm (SEA), dibuat oleh W. Nick Street dan YongSeog Kim dikembangkan untuk menangani permasalahan data streams dan concept drift pada data mining dengan tugas klasifikasi. SEA merupakan perkembangan dari metode ensemble. SEA dalam menangani data streams adalah dengan cara selalu melakukan pembelajaran pada blok-blok data yang terkini. Untuk menangani concept drift, SEA melakukannya dengan cara menggantikan base classifier yang sudah tidak sesuai konsepnya dengan classifier yang lebih tepat. Perangkat lunak SEA yang dibangun menggunakan paradigma pengembangan unified process. Perangkat lunak ini diuji melalui metode black-box. Eksperimen dilakukan untuk mengetahui pengaruh parameter-parameter pada SEA terhadap akurasi, banyaknya terjadi concept drift, lamanya waktu pelatihan, dan kebutuhan memory. Data yang digunakan untuk melakukan eksperimen ini adalah mengenai apakah pendapatan melebihi $50K/yr berdasarkan data census. Dari hasil eksperimen diperoleh tingkat akurasi 83,09% untuk data pelatihan, dan akurasi data test 82,46% Kata kunci: data mining, metode ensemble, streaming ensemble algorithm (SEA), data streams dan concept drift.
i
ABSTRACT SOFTWARE DEVELOPMENT OF STREAMING ENSEMBLE ALGORITHM (SEA): ALGORITHM FOR LARGE-SCALE CLASSIFICATION By Giri Dhaneswara NIM : 23505012 From the beginning, data mining can’t handle data with stream characteristic (data that’s continuously increase over time and the increase become much faster), nowadays the needs for such data have emerge. This has made many researchers done research in data mining so it can handle data streams problems. This is also known as mining data streams. In data streams there is also a concept drift problems (the change of concept in the model that have been built). In the year 2001, an algorithm that was named Streaming Ensemble Algorithm (SEA), made by W. Nick Street and YongSeog Kim was developed to handle data streams and concept drift problems in data mining for classification task. SEA was developed from ensemble method. In handling data streams, the newest data blocks are learned by SEA. Moreover in handling concept drift, SEA replaces inappropriate base classifier with an appropriate classifier. SEA Software has been built using unified process development paradigm. SEA software is tested using black-box method. Experiments were conducted on census data. The objective of the experiments is to know how the parameter in SEA affects the accuration, the concept drift occurrence, training time, and the memory. The results of the experiment show an accuration of 83,09% for the training data, and 82,46% for the test data. Keywords: data mining, ensemble method, streaming ensemble algorithm (SEA), data streams and concept drift.
ii
PEMBANGUNAN PERANGKAT LUNAK STREAMING ENSEMBLE ALGORITHM (SEA): ALGORITMA UNTUK KLASIFIKASI DALAM SKALA BESAR
Oleh
Giri Dhaneswara NIM : 23505012
Program Studi Magister Informatika Sekolah Teknik Elektro dan Informatika Insitut Teknologi Bandung
Menyetujui Bandung, Tanggal .............................
Pembimbing
(Dr. Ir. G. A. Putri Saptawati, M.Comm) NIP. 132127666
iii
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.
iv
KATA PENGANTAR Dengan penuh sukacita, penulis panjatkan puji syukur kepada Tuhan Yang Maha Esa, karena dengan kasih dan rahmat-Nya penulis dengan segala keterbatasannya dapat menyelesaikan tesis ini. Tidak sedikit kesulitan serta hambatan yang dihadapi dalam penelitian dan penulisan tesis ini, namun berkat bantuan dan bimbingan dari berbagai pihak, semua dapat diatasi. Pada kesempatan kali ini, penulis ingin menyampaikan rasa hormat dan terima kasih yang sebesar-besarnya kepada Ibu Dr. Ir. G. A. Putri Saptawati, M.Comm, selaku dosen pembimbing yang sudah meluangkan waktunya untuk memberi petunjuk, dorongan, arahan, saran dan bimbingan selama penelitian berlangsung dan selama penulisan tesis ini. Penulis juga ingin mengucapkan terima kasih kepada: 1. Ibu Ir. Hira Laksmiwati, M.Sc. dan Bapak Adi Mulyanto, S.T., M.T. sebagai dosen penguji yang banyak memberikan saran, arahan dan masukan yang sangat berarti. 2. Ibu Dr. Inggriani Liem, sebagai dosen wali yang telah memberikan banyak dorongan, motivasi, dan arahan, selama penulis kuliah. 3. Staf Tata Usaha S2 ITB, khususnya Bapak Ade dan Ibu Nur yang sudah membantu penulis dalam segala hal, baik selama penulis kuliah. 4. Istri, Eyang Sri Taryani, Papa dan Mama, kedua adikku Gapit dan Ganjar, Papa dan Mama Mertua, dan adik iparku Intan, yang selalu memberikan kasih sayang, semangat, dukungan, dan doa yang tiada henti-hentinya. 5. Teman-teman S2 RPL atas segala bantuan, perhatian, dan kerjasamanya selama kuliah. 6. Yoseph Adhitya, S.Kom, M.T. atas segala bantuan, perhatian, dan kerjasamanya. 7. Keluarga besar Papa dan Mama atas segala perhatiannya. 8. Semua pihak yang tidak mungkin disebutkan disini satu persatu yang telah memberikan andilnya selama penelitian berlangsung dan selama penulisan tesis ini.
v
Penulis menyadari bahwa masih banyak kekurangan dalam tesis ini. Oleh sebab itu, penulis dengan segala kerendahan hati memohon saran dan kritik saran yang diberikan, segala kekurangan tersebut dapat diperbaiki dimasa yang akan datang. Penulis berharap tesis dapat bermanfaat bagi teman-teman yang membutuhkan.
Bandung, Maret 2008
Penulis
vi
DAFTAR ISI ABSTRAK......................................................................................................................i ABSTRACT...................................................................................................................ii PEDOMAN PENGGUNAAN TESIS ..........................................................................iv KATA PENGANTAR ...................................................................................................v DAFTAR ISI................................................................................................................vii DAFTAR LAMPIRAN..................................................................................................x DAFTAR GAMBAR ....................................................................................................xi DAFTAR TABEL.......................................................................................................xiv DAFTAR ISTILAH .....................................................................................................xv BAB I
Pendahuluan...................................................................................................1
I.1
Latar Belakang Masalah ................................................................................1
I.2
Rumusan Masalah..........................................................................................2
I.3
Tujuan ............................................................................................................2
I.4
Batasan Masalah ............................................................................................3
I.5
Metodologi Penelitian....................................................................................3
I.6
Sistematika Penulisan ....................................................................................4
BAB II
Dasar Teori.....................................................................................................5
II.1
Data Mining ...................................................................................................5
II.1.1
Pengantar Data Mining ..........................................................................5
II.1.2
Penjelasan Konsep, Instans, dan Atribut ...............................................7
II.1.3
Klasifikasi sebagai Salah Satu Tugas Data Mining ...............................8
II.2
Data Streams................................................................................................10
II.3
Concept Drift ...............................................................................................11
II.4
Ensemble Classifier .....................................................................................12
II.4.1
Pengantar Ensemble Classifier ............................................................12
II.4.2
Metode untuk Mengkonstruksi Sebuah Ensemble Classifier ..............12
II.5
Streaming Ensemble Algorithm (SEA) ........................................................14
II.5.1
Pendahuluan SEA ................................................................................14
II.5.2
Metode SEA.........................................................................................15
II.6
Backpropagation sebagai Base Classifier ...................................................16
II.7
Paradigma Pengembangan PL Menggunakan Unified Process...................18
vii
BAB III
Analisis Dasar Teori ................................................................................22
III.1
Analisis Data Streams..................................................................................22
III.2
Analisis Concept Drift .................................................................................23
III.3
Analisis Mining Data Streams .....................................................................23
III.4
Analisis SEA................................................................................................24
III.4.1
Penerapan SEA pada Mining Data Streams ........................................24
III.4.2
Cara Kerja SEA....................................................................................25
III.4.3
Input dan Output dari SEA ..................................................................28
III.4.4
Algoritma Rinci SEA...........................................................................28
III.4.5
Analisis Parameter Masukan Streaming Ensemble Algorithm (SEA) .32
III.5
Kesimpulan Hasil Analisis...........................................................................34
III.6
Analisis Studi Kasus ....................................................................................34
BAB IV IV.1
Kebutuhan dan Model Analisis Perangkat Lunak ...................................37 Kebutuhan Perangkat Lunak........................................................................37
IV.1.1
Deskripsi Umum Perangkat Lunak......................................................37
IV.1.1.1
Perspektif Produk.........................................................................37
IV.1.1.2
Fungsi Produk ..............................................................................38
IV.1.1.3
Batasan dan Asumsi.....................................................................39
IV.1.2
Pemodelan Use-Case ...........................................................................39
IV.1.2.1
Diagram Use-Case .......................................................................39
IV.1.2.2
Definisi Aktor ..............................................................................40
IV.1.2.3
Definisi Use-Case ........................................................................40
IV.2
Model Analisis .............................................................................................41
IV.2.1
Realisasi Use-Case Tahap Analisis .....................................................41
IV.2.2
Identifikasi Kelas .................................................................................41
IV.2.3
Diagram Interaksi Antar Kelas ............................................................42
IV.2.4
Deskripsi Data dan Deskripsi Kebutuhan Non-Fungsional .................43
BAB V V.1
Model Perancangan dan Implementasi Perangkat Lunak........................44 Model Perancangan......................................................................................44
V.1.1 V.1.1.1
Diagram Kelas .................................................................................44
V.1.1.2
Daftar Operasi dan Atribut, serta Diagram State .............................45
V.1.2 V.2
Kelas Tahap Perancangan ....................................................................44
Perancangan Antarmuka ......................................................................45
Implementasi................................................................................................46 viii
V.2.1
Lingkungan Perangkat Keras...............................................................46
V.2.2
Lingkungan Perangkat Lunak ..............................................................46
V.2.3
Implementasi Antarmuka.....................................................................46
BAB VI
Pengujian dan Eksperimen Perangkat Lunak ..........................................50
VI.1
Pengujian Perangkat Lunak .........................................................................50
VI.2
Eksperimen ..................................................................................................52
VI.2.1
Pengaruh Ukuran Tetap Ensemble.......................................................53
VI.2.2
Pengaruh Jumlah Tuple yang Ditangani Sebuah Base Classifier ........57
VI.2.3
Pengaruh Faktor Kebenaran (PC) .........................................................62
VI.2.4
Kesimpulan Hasil Eksperimen.............................................................67
VI.2.5
Analisis Kesimpulan Hasil Eksperimen...............................................69
BAB VII
Kesimpulan dan Saran .............................................................................71
VII.1
Kesimpulan ..............................................................................................71
VII.2
Saran ........................................................................................................73
DAFTAR PUSTAKA ..................................................................................................74
ix
DAFTAR LAMPIRAN LAMPIRAN A Skenario Use-Case .............................................................................76 LAMPIRAN B Diagram Sequence..............................................................................86 LAMPIRAN C Daftar Atribut dan Operasi Kelas.......................................................96 LAMPIRAN D Diagram State...................................................................................102 LAMPIRAN E Hasil Pengujian.................................................................................109
x
DAFTAR GAMBAR Gambar II.1.
Proses KDD ........................................................................................7
Gambar II.2.
Proses Pembangunan Model Klasifikasi...........................................10
Gambar II.3.
Concept descriptions yang baru dan lama dan sebuah “jendela” yang bergerak berdasarkan stream dari data examples..............................11
Gambar II.4.
Gambaran Umum Ensemble .............................................................12
Gambar II.5.
Neuron pada Manusia .......................................................................17
Gambar II.6.
Arsitektur Backpropagation..............................................................18
Gambar II.7.
Pengembangan Secara Iteratif pada Unified Process .......................18
Gambar II.8.
Keterangan Tahapan Pengembangan pada Unified Process.............19
Gambar II.9.
Keterhubungan Use-Case ke Model Rekayasa Perangkat Lunak.....20
Gambar IV.1.
Contoh Diagram Entity-Relationship yang akan dibuat VIEW........38
Gambar IV.2.
Diagram Use-Case Perangkat Lunak SEA .......................................39
Gambar IV.3.
Diagram Interaksi Antar Kelas .........................................................42
Gambar V.1.
Diagram Kelas ..................................................................................44
Gambar V.2.
Hirarki Menu.....................................................................................45
Gambar V.3.
Antarmuka Form Utama ...................................................................46
Gambar V.4.
Antarmuka Form Konfigurasi Basis Data ........................................47
Gambar V.5.
Antarmuka Form Manipulasi Basis Data .........................................47
Gambar V.6.
Antarmuka Form Konfigurasi Base Classifier .................................48
Gambar V.7.
Antarmuka Form Proses Klasifikasi Base Classifier........................48
Gambar V.8.
Antarmuka Form Konfigurasi SEA ..................................................49
Gambar V.9.
Antarmuka Form Proses Klasifikasi SEA ........................................49
Gambar VI.1.
Grafik Selama Pelatihan Ensemble untuk Parameter Ukuran Ensemble = 10...................................................................................53
Gambar VI.2.
Grafik Tingkat Akurasi Ensemble pada Data Pelatihan untuk Parameter Ukuran Ensemble = 10.....................................................54
Gambar VI.3.
Grafik Tingkat Akurasi Ensemble pada Data Test untuk Parameter Ukuran Ensemble = 10......................................................................54
Gambar VI.4.
Grafik Selama Pelatihan Ensemble untuk Parameter Ukuran Ensemble = 20...................................................................................55
xi
Gambar VI.5.
Grafik Tingkat Akurasi Ensemble pada Data Pelatihan untuk Parameter Ukuran Ensemble = 20.....................................................55
Gambar VI.6.
Grafik Tingkat Akurasi Ensemble pada Data Test untuk Parameter Ukuran Ensemble = 20......................................................................56
Gambar VI.7.
Grafik Selama Pelatihan Ensemble untuk Ukuran Ensemble = 30 ...56
Gambar VI.8.
Grafik Tingkat Akurasi Ensemble pada Data Pelatihan untuk Parameter Ukuran Ensemble = 30.....................................................57
Gambar VI.9.
Grafik Tingkat Kebenaran Prediksi (SEA) Data Test untuk Parameter Ukuran Ensemble = 30......................................................................57
Gambar VI.10. Grafik Selama Pelatihan Ensemble untuk Parameter Jumlah Tuple yang Ditangani Sebuah Base Classifier = 100..................................58 Gambar VI.11. Grafik Tingkat Akurasi Ensemble pada Data Pelatihan untuk Parameter Jumlah Tuple yang Ditangani Sebuah Base Classifier = 100.....................................................................................................59 Gambar VI.12. Grafik Tingkat Akurasi Ensemble pada Data Test untuk Parameter Jumlah Tuple yang Ditangani Sebuah Base Classifier = 100 ...........59 Gambar VI.13. Grafik Selama Pelatihan Ensemble untuk Parameter Jumlah Tuple yang Ditangani Sebuah Base Classifier = 500..................................60 Gambar VI.14. Grafik Tingkat Akurasi Ensemble pada Data Pelatihan untuk Parameter Jumlah Tuple yang Ditangani Sebuah Base Classifier = 500.....................................................................................................60 Gambar VI.15. Grafik Tingkat Akurasi Ensemble pada Data Test untuk Parameter Jumlah Tuple yang Ditangani Sebuah Base Classifier = 500 ...........61 Gambar VI.16. Grafik Selama Pelatihan Ensemble untuk Parameter Jumlah Tuple yang Ditangani Sebuah Base Classifier = 1000................................61 Gambar VI.17. Grafik Tingkat Akurasi Ensemble pada Data Pelatihan untuk Parameter Jumlah Tuple yang Ditangani Sebuah Base Classifier = 1000...................................................................................................62 Gambar VI.18. Grafik Tingkat Akurasi Ensemble pada Data Test untuk Parameter Jumlah Tuple yang Ditangani Sebuah Base Classifier = 1.000 ........62 Gambar VI.19. Grafik Selama Pelatihan Ensemble untuk Parameter Faktor Kebenaran (PC) = 25 .........................................................................63 Gambar VI.20. Grafik Tingkat Akurasi Ensemble pada Data Pelatihan untuk Parameter Faktor Kebenaran (PC) = 25.............................................63 xii
Gambar VI.21. Grafik Tingkat Akurasi Ensemble pada Data Test untuk Parameter Faktor Kebenaran (PC) = 25..............................................................64 Gambar VI.22. Grafik Selama Pelatihan Ensemble untuk Parameter Faktor Kebenaran (PC) = 50 .........................................................................64 Gambar VI.23. Grafik Tingkat Akurasi Ensemble pada Data Pelatihan untuk Parameter Faktor Kebenaran (PC) = 50.............................................65 Gambar VI.24. Grafik Tingkat Akurasi Ensemble pada Data Test untuk Parameter Faktor Kebenaran (PC) = 50..............................................................65 Gambar VI.25. Grafik Selama Pelatihan Ensemble untuk Parameter Faktor Kebenaran (PC) = 100 .......................................................................66 Gambar VI.26. Grafik Tingkat Akurasi Ensemble pada Data Pelatihan untuk Parameter Faktor Kebenaran (PC) = 100...........................................66 Gambar VI.27. Grafik Tingkat Akurasi Ensemble pada Data Test untuk Parameter Faktor Kebenaran (PC) = 100............................................................67
xiii
DAFTAR TABEL Tabel II.1.
Data Bermain Olah Raga Sesuai dengan Cuaca .......................................8
Tabel II.2.
Diagram pada UML ................................................................................20
Tabel III.1. Data IPK Mahasiswa dengan Waktu t ....................................................22 Tabel III.2. Data IPK Mahasiswa dengan Waktu t+1 ................................................22 Tabel III.3. Data Credit Rating Tahun 2006..............................................................23 Tabel III.4. Data Credit Rating Tahun 2007..............................................................23 Tabel IV.1. Tabel hasil JOIN antara Tabel Pinjaman dan Tabel Rekening ...............38 Tabel IV.2. Definisi Aktor .........................................................................................40 Tabel IV.3. Definisi Use-Case ...................................................................................40 Tabel IV.4. Identifikasi Kelas Perangkat Lunak SEA ...............................................41 Tabel V.1.
Keterhubungan Diagram Kelas dengan Hirarki Menu ...........................45
Tabel VI.1. Hasil Eksperimen untuk Parameter Ukuran Tetap Ensemble .................67 Tabel VI.2. Hasil Eksperimen untuk Parameter Jumlah Tuple yang Ditangani Sebuah Base Classifier ........................................................................................68 Tabel VI.3. Hasil Eksperimen untuk Parameter Faktor Kebenaran (Pc) ...................68
xiv
DAFTAR ISTILAH Istilah
Keterangan Himpunan nilai yang mengkarakteristikkan sebuah masukan pada data mining. Disebut juga fitur. [WIT05] Teknik klasifikasi / classifier individual yang digunakan Base classifier sebagai dasar pembentuk ensemble. [TAN05] Model yang dihasilkan oleh proses klasifikasi. [HAN01] Classifier Concept description Hasil keluaran yang didapatkan dari sebuah skema pembelajaran. [WIT05] Perubahan konsep pada model yang telah dibangun. Concept Concept drift drift hanya ada pada permasalahan data streams. [TSY04] Proses pengekstraksian pengetahuan dari data berskala besar. Data mining [HAN01] Data yang terus-menerus bertambah dan semakin cepat laju Data streams pertambahannya. [GAB05] Objek-objek yang ingin dikenakan proses data mining. Setiap Instans instans merupakan sebuah contoh individual dan independen dari konsep yang ingin dipelajari. Disebut juga contoh. [WIT05] Konsep Hal yang ingin dipelajari dari proses data mining. [WIT05] Metode ensemble Teknik klasifikasi yang menggabungkan prediksi beberapa classifier untuk melakukan klasifikasi. [TAN05] Model Representasi konsep yang telah diperoleh dari proses klasifikasi. [HAN01] Anomali atau kesalahan yang terdapat pada data. [HAN01] Noise Variabel explanatory Atribut-atribut instans yang digunakan untuk melakukan prediksi pada proses klasifikasi. Disebut juga variabel bebas. [TAN05] Variabel target Atribut instans yang akan diprediksi pada proses klasifikasi. Disebut juga variabel bergantung. [TAN05] Atribut
xv
