DELEGATING CLASSIFIERS UNTUK KATEGORISASI
DATA TERSTRUKTUR DENGAN ALGORITMA C4.5
LAPORAN TUGAS AKHIR
Disusun sebagai syarat kelulusan tingkat sarjana
Oleh :
Raden Fitri Indriani / 13503020
PROGRAM STUDI TEKNIK INFORMATIKA
SEKOLAH TEKNIK ELEKTRO DAN INFORMATIKA
INSTITUT TEKNOLOGI BANDUNG
2007
Lembar Pengesahan Program Studi Sarjana Informatika
DELEGATING CLASSIFIERS UNTUK KATEGORISASI DATA TERSTRUKTUR DENGAN ALGORITMA C4.5
Tugas Akhir Program Studi Sarjana Informatika ITB
Oleh Raden Fitri Indriani / 13503020
Telah disetujui dan disahkan sebagai laporan tugas akhir di Bandung, pada tanggal 20 September 2007
Pembimbing II,
Pembimbing I,
Masayu Leylia Khodra, S.T., M.T. NIP. 999023508
Nur Ulfa Maulidevi, S.T., M.Sc. NIP. 999023503
ii
RINGKASAN Klasifikasi merupakan task untuk memberikan label kelas terhadap suatu data yang dilakukan oleh classifier. Kombinasi multi-classifiers memiliki kinerja yang lebih baik dari single classifier (base classifier) yang membentuknya. Akan tetapi, penggunaan multi-classifiers memiliki beberapa kekurangan, yaitu terjadinya loss of comprehensibility dan penggunaan resources komputasi yang berlebihan. Delegating classifiers dibuat dengan motto ‘let others do the things that you cannot do well’. Eksperimen dalam Tugas Akhir ini membuktikan penelitian yang dilakukan oleh Caesar Ferri pada tahun 2004 yang mengusulkan delegating classifiers untuk mengatasi kekurangan multi-classifiers. Delegating classifiers yang digunakan di dalam eksperimen dibangun dengan skema iterative, metode penentuan batas ambang GAP (Global Absolute Percentage), persentase delegasi 1% dengan jumlah base classifier 20 buah dan persentase delegasi 2% jumlah base classifier 10 buah, dan algoritma pembelajaran C4.5. Perhitungan akurasi menggunakan 20x5-folds cross validation. Untuk melakukan eksperimen, aplikasi dibangun dengan menggunakan library dari WEKA ditambah dengan implementasi delegating classifiers. Pembangunan aplikasi menggunakan NetBeans 5.0, JDK 1.5.0, dan WEKA 3.5.3. Eksperimen dilakukan dengan cara membentuk single classifier, multi-classifiers menggunakan bagging dan boosting, serta delegating classifiers untuk 28 buah dataset yang diambil dari UCI dataset repository. Kemudian hasil eksperimen dianalisa dengan cara membandingkan performansi delegating classifiers dengan single classifier dan multi-classifiers dari segi efektifitas yaitu rasio akurasi menggunakan t-test 99% significance dan dari segi efisiensi yaitu waktu untuk melakukan pembelajaran dan 20x5-folds cross validation. Dari segi efektifitas, delegating classifiers lebih baik daripada single classifier. Akan tetapi, efektifitas delegating classifiers belum sebaik multi-classifiers. Sedangkan dari segi efisiensi, delegating classifiers lebih baik daripada multi-classifiers. Kata kunci : delegating classifiers, single classifier, multi-classifiers, bagging, boosting, algoritma C4.5.
iii
KATA PENGANTAR
Syukur kepada Allah SWT. karena dengan ridho-Nya penulis dapat melaksanakan Tugas Akhir ini yang berjudul Delegating Classifiers untuk Kategorisasi Data Terstruktur dengan Algoritma C4.5.
Selama masa pengerjaan Tugas Akhir ini, penulis mendapat dukungan dari berbagai pihak baik berupa material maupun spiritual. Oleh karena itu, penulis ingin mengucapkan terima kasih sebesar-besarnya kepada : 1. Bapak Dr.Ing. M. Sukrisno selaku ketua program studi Teknik Informatika ITB. 2. Ibu Henny Yusnita Zubir, BS, M.T. yang telah menjadi dosen wali yang baik dan perhatian. 3. Ibu Nur Ulfa M., S.T, M.Sc. dan Ibu Masayu Leylia K., S.T., M.T. atas bimbingan dan dukungannya kepada penulis selama mengerjakan tugas akhir ini. 4. Ibu Ir. Sri Purwanti, M.Sc yang telah menjadi penguji pada presentasi proposal Tugas Akhir, Bapak Ir. Dwi Hendratmo, M.Sc., Ph.D. yang telah menjadi penguji pada seminar Tugas Akhir, Bapak Ir. Windy Gambetta yang telah menjadi penguji pada prasidang Tugas Akhir, serta Bapak Dr. Ir. Iping Supriana S. dan Bapak Achmad Imam K., Ph.D. yang telah menjadi penguji pada sidang Tugas Akhir. 5. Seluruh dosen program studi Teknik Informatika yang telah memberikan pengetahuan dan didikan yang berharga bagi penulis. 6. Kedua orang tua penulis, Raden Fadjar dan Sri Yuni Haryati atas dukungan material dan spiritual, doa, bimbingan, perhatian, kasih sayang, serta semangat yang selalu diberikan dan menyertai penulis selama penulis menjalani hidup, terlebih selama pengerjaan Tugas Akhir. 7. R. Ustaram dan Ratu Atih Kencanawati atas doa, dukungan, perhatian, naungan serta bimbingan yang menyertai penulis selama penulis menjalani perkuliahan di Teknik Informatika ITB, terlebih selama pengerjaan Tugas Akhir. 8. Kedua kakak penulis, Raden Fani Sulistyawati dan Raden Fika Sri Astuti, serta kakak ipar penulis, Farhan Affif Masna, yang selalu memberikan semangat, contoh yang baik, perhatian, serta doa kepada penulis. 9. Dede Kurnia Setyawan yang telah menemani penulis menjalani hidup selama tujuh tahun terakhir serta terima kasih atas dukungan, doa, perhatian, semangat, iv
dan kritik serta saran yang tak henti-hentinya diberikan kepada penulis. Terima kasih juga karena selalu bersedia mendengarkan keluh-kesah penulis selama mengerjakan Tugas Akhir. 10. R. Ane Ferliana, R Nila Nurlistyah, R. Dicky Fithansyah, Teungku Achmad Zuchradi, R. Sefi Triwibiyono atas dukungan serta doa yang selalu diberikan kepada penulis. 11. Teungku Adrian Firjatullah, Calista Athaya Finegara, dan Chalifa Agrifinaynegara atas kelucuan yang kalian miliki dan karena telah menjadi teman bermain serta memberikan senyum kepada penulis selama mengerjakan Tugas Akhir. 12. Devi Capricornia Sari, Dini Armyta, Eleina Pratiwi, Filliany Yulistina Cancer, Finish Fernando, Lefi Yusnasari, Nenden Puspita Sari, dan Hanindita Diajeng Sunu atas masa-masa menyenangkan dan penuh tawa yang telah dilalui bersama penulis. 13. Ratna Mutia Suci yang sering menjadi teman sekelompok bagi penulis, Dini Rahmawati, Lely Triastiti, Edward Ferdian, Yus Gias, Anggia Ferdina, Pocut Viqarunnisa, dan Dewi Pramudi atas kerjasama, bantuan, dan dukungannya. 14. Teman-teman seperjuangan, IF 2003, yang telah menemani penulis melewati berbagai suka dan duka selama masa perkuliahan. Semoga IF 2003 bisa semakin kompak dan tetap menjaga silaturahmi walaupun sudah berpencar. 15. Segenap Staf IF lain seperti petugas tata usaha, petugas duktek, petugas dapur dan yang lainnya yang sudah membantu penulis selama menjalani masa perkuliahan. Serta pihak lain yang tidak dapat penulis sebutkan satu-persatu, sekali lagi penulis mengucapkan terima kasih yang sebesar-besarnya.
Penulis mohon maaf jika terdapat kesalahan dalam pengerjaan Tugas Akhir ini. Oleh karena itu, penulis menerima kritik dan saran yang membangun untuk membuat penulis menjadi lebih baik lagi.
Bandung, 9 September 2007
Penulis
v
DAFTAR ISI
Lembar Pengesahan .......................................................................................................ii
RINGKASAN .............................................................................................................. iii
KATA PENGANTAR ..................................................................................................iv
DAFTAR ISI.................................................................................................................vi
DAFTAR GAMBAR ..................................................................................................viii
DAFTAR TABEL.........................................................................................................ix
Bab I Pendahuluan................................................................................................ I-1
1.1 Latar Belakang............................................................................................ I-1
1.2 Rumusan Masalah....................................................................................... I-3
1.3 Tujuan ......................................................................................................... I-3
1.4 Batasan Masalah ......................................................................................... I-3
1.5 Metodologi.................................................................................................. I-4
1.6 Sistematika Pembahasan............................................................................. I-4
Bab II Dasar Teori.................................................................................................II-1
2.1 Estimasi Akurasi Classifier........................................................................II-1
2.1.1 Metode Holdout .................................................................................II-1
2.1.2 Bootstrap............................................................................................II-2
2.1.3 K-fold Cross Validation .....................................................................II-2
2.2 Algoritma C4.5 ..........................................................................................II-3
2.3 Delegating Classifiers ................................................................................II-6
2.3.1 Parameter Terbaik Delegating Classifiers .......................................II-10
2.3.2 Soft Classifier...................................................................................II-11
2.3.3 Probability Estimator Tree ..............................................................II-12
2.3.4 Cautious Classifier...........................................................................II-13
2.4 Multi-Classifiers ......................................................................................II-14
2.4.1 Bagging ............................................................................................II-15
2.4.2 Boosting ...........................................................................................II-16
Bab III Delegating Classifiers...............................................................................III-1
3.1 Perbandingan Delegating Classifiers dan Multi-Classifiers .....................III-1
3.2 Pembangunan Delegating Classifiers .......................................................III-2
3.3 Representasi Decision Tree.......................................................................III-5
3.4 Penentuan Parameter C4.5 ........................................................................III-7
Bab IV Eksperimen .............................................................................................. IV-1
4.1 Dataset...................................................................................................... IV-1
4.2 Kakas........................................................................................................ IV-1
4.3 Skenario Eksperimen ............................................................................... IV-2
4.4 Hasil Eksperimen ..................................................................................... IV-3
4.5 Analisa Hasil Eksperimen........................................................................ IV-5
Bab V Penutup ......................................................................................................V-1
5.1 Kesimpulan ................................................................................................V-1
5.2 Saran ..........................................................................................................V-1
DAFTAR REFERENSI .................................................................................................x
LAMPIRAN A...........................................................................................................A-1
LAMPIRAN B ...........................................................................................................B-1
vi
LAMPIRAN C ...........................................................................................................C-1
LAMPIRAN D...........................................................................................................D-1
vii
DAFTAR GAMBAR
Gambar II-1 Gambar II-2 Gambar II-3 Gambar II-4 Gambar II-5 Gambar II-6 Gambar III-1 Gambar III-2 Gambar III-3 Gambar IV-1 Gambar IV-2 Gambar A-1
Hasil pruning dengan menggunakan rule post pruning.....................II-5
Hasil pruning dengan menggunakan C4.5 pada WEKA ...................II-6
Proses pembangunan umum delegating classifiers [KHO06] ...........II-7
Contoh PET......................................................................................II-13
Algoritma Bagging [KOH98] ..........................................................II-16
Algoritma AdaBoost.M1 [FRE96]...................................................II-17
Proses pembangunan delegating classifiers skema iterative ............III-3
(a) Decision tree dan (b) representasinya .........................................III-5
(a) PET dan (b) representasinya........................................................III-6
Grafik waktu pembelajaran.............................................................. IV-4
Grafik waktu 20x5-folds cross validation........................................ IV-5
Decision tree hasil dari pembelajaran dengan menggunakan data latih
pada Tabel A-1...................................................................................A-2 Gambar A-2 PET yang dihasilkan dari decision tree pada Gambar A-1................A-2 Gambar A-3 Decision tree hasil dari pembelajaran dengan menggunakan delegated set pada Tabel A-3 .............................................................................A-4
Gambar A-4 PET yang dihasilkan dari decision tree pada Gambar A-3................A-4
viii
DAFTAR TABEL
Tabel II-1 Tabel II-2 Tabel III-1 Tabel III-2 Tabel III-3 Tabel IV-1 Tabel IV-2 Tabel A-1 Tabel A-2 Tabel A-3 Tabel B-1 Tabel C-1 Tabel C-2 Tabel C-3 Tabel C-4 Tabel C-5 Tabel C-6 Tabel C-7 Tabel C-8 Tabel C-9 Tabel C-10 Tabel C-11 Tabel C-12 Tabel C-13 Tabel C-14 Tabel C-15 Tabel C-16 Tabel C-17 Tabel C-18 Tabel C-19 Tabel C-20 Tabel C-21 Tabel C-22 Tabel C-23 Tabel C-24 Tabel C-25 Tabel C-26 Tabel C-27 Tabel C-28 Tabel D-1 Tabel D-2
Contoh pembagian data dengan menggunakan Bagging [OPI99]...II-15 Contoh pembagian data dengan menggunakan Boosting [OPI99] ..II-16 Daftar parameter C4.5 yang terdapat pada WEKA ..........................III-7 Nilai akurasi C4.5 dengan nilai parameter yang berbeda-beda ........III-8 Perbandingan nilai parameter C4.5 Tugas Akhir dengan [FER04] ..III-9 Nilai rata-rata AUC untuk setiap classifier yang dihasilkan ........... IV-3 Jumlah classifier yang terjadi peningkatan akurasi yang signifikan berdasarkan t-test 99% significance................................................. IV-5
14 buah data yang digunakan sebagai data latih................................A-1
Nilai confidence dari 14 buah data latih ............................................A-3
Delegated set......................................................................................A-4
Properti 28 buah dataset yang digunakan di dalam eksperimen........B-1
Nilai AUC 20x5-folds cross validation untuk balance scale ............C-1
Nilai AUC 20x5-folds cross validation untuk breast cancer WDBC C-1
Nilai AUC 20x5-folds cross validation untuk breast cancer WIS.....C-2
Nilai AUC 20x5-folds cross validation untuk CMC .........................C-3
Nilai AUC 20x5-folds cross validation untuk dermatology ..............C-3
Nilai AUC 20x5-folds cross validation untuk hayes roth .................C-4
Nilai AUC 20x5-folds cross validation untuk heart disease .............C-5
Nilai AUC 20x5-folds cross validation untuk house voting..............C-5
Nilai AUC 20x5-folds cross validation untuk iris.............................C-6
Nilai AUC 20x5-folds cross validation untuk Monk’s1 ....................C-7
Nilai AUC 20x5-folds cross validation untuk Monk’s2 ....................C-7
Nilai AUC 20x5-folds cross validation untuk Monk’s3 ....................C-8
Nilai AUC 20x5-folds cross validation untuk new thyroid ...............C-9
Nilai AUC 20x5-folds cross validation untuk segmentation.............C-9
Nilai AUC 20x5-folds cross validation untuk tic-tac-toe................C-10
Nilai AUC 20x5-folds cross validation untuk teaching A. eval ......C-11
Nilai AUC 20x5-folds cross validation untuk wine.........................C-11
Nilai AUC 20x5-folds cross validation untuk spect ........................C-12
Nilai AUC 20x5-folds cross validation untuk car...........................C-13
Nilai AUC 20x5-folds cross validation untuk optdigits ..................C-13
Nilai AUC 20x5-folds cross validation untuk spam........................C-14
Nilai AUC 20x5-folds cross validation untuk thyroid Eu ...............C-15
Nilai AUC 20x5-folds cross validation untuk credit approval .......C-15
Nilai AUC 20x5-folds cross validation untuk yeast ........................C-16
Nilai AUC 20x5-folds cross validation untuk p. indian diabetes....C-17
Nilai AUC 20x5-folds cross validation untuk ionosphere ..............C-17
Nilai AUC 20x5-folds cross validation untuk ecoli ........................C-18
Nilai AUC 20x5-folds cross validation untuk auto imports 85.......C-19
Waktu pembelajaran untuk membangun classifier (dalam ms).........D-1
Waktu untuk melakukan 20x5-folds cross validation (dalam ms) ....D-2
ix
