Judul
:
Klasifikasi Berita Multilabel Menggunakan Naïve Bayes Dengan Smoothing Modified Absolute Discount Dan Feature Selection Chi Square.
Nama
:
I Made Dwi Putra Suarbawa (NIM: 1208605093)
Pembimbing
:
1. I Putu Gede Hendra Suputra, S.Kom., M.Kom 2. Agus Muliantara, S.Kom., M.Kom
ABSTRAK Dewasa ini, bayak situs berita online mem-posting berita dengan jumlah banyak dan bervariatif. Berita-berita tersebut biasanya memiliki lebih dari satu tag, kategori atau label. Pada saat pemberian label ini, ada kemungkinan seorang editor berita melakukan kesalahan dalam meberikan label. Salah satu kesalahan yang mungkin terjadi adalah kurangnya label yang seharunya diberikan pada berita. Automatic Text categorization merupakan salah satu solusi yang dapat dilakukan, yaitu dengan cara membangun sistem yang mampu mengelompokkan berita kedalam beberapa label tertentu. Salah satu algoritma pengelompokan teks untuk kasus multilabel yang dapat digunakan adalah algoritma naïve bayes modified absolute discount yang disertai dengan seleksi fitur chi square. Untuk kasus pengklasifikasian multilabel, label-label yang diberikan untuk berita adalah label dengan nilai probabilitas melebihi nilai threshold. Berdasarkan hasil pengujian yang dilakukan didapatkan hasil sebaga berikut : implemetasi algoritma klasifikasi yang tidak disertai dengan seleksi fitur menghasilkan nilai F1measure 74,31%. Setelah diterapkannya seleksi fitur, nilai F1 measure yang di dapat adalah 83,15%. Metode naïve bayes MAD yang disertai dengan chi square dapat dikatakan lebih baik dengan peningkatan sebesar 11,89%.
Kata Kunci :Klasifikasi multilabel, Naïve Bayes, Modified Absolute Discount, Chi-Square.
iv
Title
:
Multi Label News Classification Using Naïve Bayes by Smoothing
Modified
Absolute Discount
and
Feature
Selection of Chi Square. Name
:
I Made Dwi Putra Suarbawa (Registration: 1208605093)
Supervisors
:
1. I Putu Gede Hendra Suputra, S.Kom., M.Kom 2. Agus Muliantara, S.Kom., M.Kom
ABSTRACT Today, many online news sites posting news in large numbers and varied. The news usually has more than one tag, category or label. At the time of this labeling, there is the possibility of a news editor to make a mistake in giving the label. One of the errors that may occur is the lack of a label that should be given to the news. Automatic Text Categorization is one solution that can be done, that is the way to build a system capable of classifying news into some specific label. One algorithm for text grouping of multi label case that can be used is naïve Bayes algorithm modified absolute discount accompanied by chi square feature selection. For cases of multi label classification, labels given for the news are labels with a probability value that exceeds the threshold value. Based on the results of tests performed, it was obtained the following results: the implementation of a classification algorithm that is not accompanied with feature selection F1measure generating value 74.31%. After the implementation of feature selection, the value of obtained F1 was 83.15%. Method of naïve Bayes MAD accompanied by chi square can be said to be better with an increase of 11.89%. Keywords: Multi label Classification, Naïve Bayes, Modified Absolute Discount, Chi-Square.
v
KATA PENGANTAR
Puji syukur penulis panjatkan kepada Tuhan yang Maha Esa berkat rahmatNyalah penulis diberi kelancaran dalam membuat penelitian tugas akhir ini, dengan judul “Klasifikasi Berita Multilabel Menggunakan Naïve Bayes Dengan Smoothing Modified Absolute Discount Dan Feature Selection Chi Square”. Terwujudnya penelitian tugas akhir ini tidak lepas dari bantuan berbagai pihak yang telah mendorong dan membimbing penulis, baik tenaga, ide-ide, maupun pemikiran. Secara khusus dalam kesempatan ini penulis ingin mengucapkan terimakasih kepada pihak yang telah membantu penelitian tugas akhir ini, yaitu: 1.
Bapak I Putu Gede Hendra Suputra, S.Kom., M.Kom. sebagai pembimbing I yang telah banyak membantu menyempurnakan penelitian tugas akhir ini.
2.
Bapak Agus Muliantara, S.Kom., M.Kom. sebagai pembimbing II yang telah banyak membantu menyempurnakan penelitian tugas akhir ini.
3.
Bapak-bapak dan ibu-ibu dosen di Jurusan Ilmu Komputer, yang telah meluangkan
waktu
turut
memberikan
saran
dan
masukan
dalam
penyempurnaan penelitian tugas akhir ini. 4.
Teman - teman di Jurusan Ilmu Komputer yang telah memberikan saran, masukan serta dukungan moral dan semangat dalam penyelesaian penelitian tugas akhir ini. Penulis menyadari bahwa penelitian tugas akhir ini masih jauh dari
kesempurnaan, oleh karena itu apabila menemukan kesalahan atau kekurangan dalam penelitian tugas akhir ini, baik dari segi bahasanya maupun isinya, kritik dan saran yang bersifat membangun selalu penulis harapkan demi penyempurnaan tugas akhir ini.
Bukit Jimbaran, 2 September 2016
Penulis
vi
DAFTAR ISI
SURAT PERNYATAAN KEASLIAN KARYA ILMIAH ................................... ii LEMBAR PENGESAHAN TUGAS AKHIR ...................................................... iii KATA PENGANTAR ........................................................................................ iv DAFTAR ISI ..................................................................................................... vii DAFTAR TABEL ............................................................................................... x DAFTAR GAMBAR ......................................................................................... xii DAFTAR LAMPIRAN ..................................................................................... xiii 1.
2.
BAB I PENDAHULUAN .......................................................................... 14 1.1
Latar Belakang ................................................................................... 14
1.2
Rumusan Masalah .............................................................................. 15
1.3
Batasan Masalah ................................................................................ 15
1.4
Tujuan Penelitian ............................................................................... 16
1.5
Manfaat Peneitian .............................................................................. 16
1.6
Metodologi Penelitian ........................................................................ 16
1.6.1
Objek Penelitian ........................................................................... 16
1.6.2
Lingkungan Penelitian .................................................................. 16
1.6.3
Metode Pengumpulan Data ........................................................... 17
1.6.4
Perancangan Sistem ...................................................................... 17
1.6.5
Implementasi Sistem ..................................................................... 18
1.6.6
Metode Yang Digunakan .............................................................. 18
1.6.7
Evaluasi dan Pengujian Sistem...................................................... 19
BAB II TINJAUAN PUSTAKA ................................................................ 20 2.1
Naïve Bayes Classifier ....................................................................... 20
2.2
Modified Absolute Discount ............................................................... 21
2.3
Chi Square ......................................................................................... 22
2.4
Multi-label Classification................................................................... 22
vii
3.
2.5
Text Preprocessing ............................................................................ 23
2.6
Berita ................................................................................................. 24
2.7
Klasifikasi Dokumen ......................................................................... 24
2.8
Model waterfall.................................................................................. 25
2.9
Evaluasi Multilabel ............................................................................ 27
BAB III ANALISIS DAN PERANCANGAN ............................................ 28 3.1
Metode Pengumpulan Data ................................................................ 28
3.2
Analisis Kebutuhan ............................................................................ 28
3.2.1. 3.3
Perancangan Sistem ........................................................................... 29
3.3.1
Use Case ....................................................................................... 30
3.3.2
Activity Diagram .......................................................................... 32
3.3.3
Class Diagram .............................................................................. 35
3.3.4
Sequence Diagram ........................................................................ 37
3.4
ERD (Entity Relationship Diagram) ................................................... 39
3.5
Rancangan Antarmuka ....................................................................... 40
3.6
Implementasi dan Dokumentasi Sistem .............................................. 42
3.7
Skenario Pengujian Sistem ................................................................. 43
3.7.1.
Static Testing ................................................................................ 43
3.7.2.
Whitebox Testing ......................................................................... 43
3.7.3.
Blackbox Testing .......................................................................... 44
3.8 4.
Analisis Kebutuhan Sistem dan Kebutuhan Pemakai ..................... 28
Perancangan Analisis Algoritma ........................................................ 45
BAB IV HASIL DAN PEMBAHASAN .................................................... 46 4.1.
Gambaran Umum Sistem ................................................................... 46
4.2.
Lingkungan Implementasi .................................................................. 48
4.3.
Implementasi Database ...................................................................... 49
viii
4.4.
Implementasi Naïve Bayes dengan modified absolute discount dan
feature selection chi-square pada sistem. ........................................................ 50 4.5.
Implementasi antarmuka .................................................................... 53
4.6.
Pengujian Sistem ............................................................................... 56
4.6.1
Static testing ................................................................................. 56
4.6.2
Blackbox testing ........................................................................... 56
4.6.3
Whitebox testing ........................................................................... 61
4.6.4
Perbandingan NBC MAD dengan dan tanpa seleksi fitur .............. 64
4.6.5
Analisa karateristik naïve bayes .................................................... 65
BAB V KESIMPULAN DAN SARAN ............................................................. 71 5.1.
Kesimpulan........................................................................................ 71
5.2.
Saran ................................................................................................. 71
DAFTAR PUSTAKA ........................................................................................ 72
ix
DAFTAR TABEL
Tabel
Halaman
Tabel 3.1 Analisis Kebutuhan Sistem ................................................................. 29 Tabel 3.2 Pendifinisian Aktor............................................................................. 30 Tabel 3.3 Definisi use case sistem klasifikasi berita ........................................... 30 Tabel 3.4 Tabel deskripsi kelas-kelas pada kelas diagram .................................. 36 Tabel 3.5 Rancangan pengujian sistem Static testing .......................................... 43 Tabel 3.6 Test Plan Function Testing ................................................................. 44 Tabel 4.1 Kode Implementasi Feature selection chi-square ................................ 50 Tabel 4.2 Kode Implementasi formula P(D|Ci)................................................... 51 Tabel 4.3 Implementasi formula P(Ci|D). ........................................................... 52 Tabel 4.4 Implementasi pthreas ......................................................................... 52 Tabel 4.5 Implementasi Modified Absolute Discount ......................................... 53 Tabel 4.6 Hasil Static Testing ............................................................................. 56 Tabel 4.7 Checklist Kebutuhan ........................................................................... 56 Tabel 4.8 Pengujian Fungsional Login Sistem .................................................... 57 Tabel 4.9 Pengujian Fungsional Menambah Data Admin ................................... 58 Tabel 4.10 Pengujian Fungsional Meng-update Data Admin .............................. 58 Tabel 4.11 Pengujian Fungsional Hapus Data Admin ......................................... 59 Tabel 4.12 Pengujian Fungsional Menambah Data Berita................................... 59 Tabel 4.13 Pengujian Fungsional Meng-update Data Berita ............................... 60 Tabel 4.14 Pengujian Fungsional Menghapus Data Berita .................................. 60 Tabel 4.15 Pengujian Fungsional Prediksi label ................................................. 61 Tabel 4.16 Berita pada kasus 1 ........................................................................... 65 Tabel 4.17 Hasil probabilitas label kasus 1 ......................................................... 66 Tabel 4.18 Hasil probabilitas label kasus 1 setelah ditambahkan kata “bank” ..... 66 Tabel 4.19 Hasil probabilitas label kasus 1 setelah ditambahkan kata “cereal” ... 66 Tabel 4.20 Berita pada kasus 2 ........................................................................... 66 Tabel 4.21 Hasil probabilitas label kasus 2 ......................................................... 67 Tabel 4.22 Hasil probabilitas label kasus 2 setelah ditambahkan kata “bank” ..... 67
x
Tabel 4.23 Hasil probabilitas label kasus 2 setelah ditambahkan kata “cereal” ... 67 Tabel 4.24 Hasil probabilitas gabungan berita 1 dan 2 ........................................ 68 Tabel 4.25 Hasil probabilitas kasus 3 di tambah kata “bank dan “money” beberapa kali..................................................................................................................... 69 Tabel 4.26 Hasil percobaan kasus 1.................................................................... 69 Tabel 4.27 Hasil percobaan kasus 2.................................................................... 70 Tabel 4.28 Hasil percobaan kasus 3.................................................................... 70
xi
DAFTAR GAMBAR
Gambar
Halaman
Gambar 2.1 Model Waterfall ............................................................................. 26 Gambar 3.1 Use Case Sistem Klasifikasi Berita ................................................ 32 Gambar 3.2 Activity Diagram Login System ...................................................... 33 Gambar 3.3 Activity Diagram tambah berita ..................................................... 33 Gambar 3.4 Activity Diagram try classification ................................................. 34 Gambar 3.5 Activity Diagram add admin .......................................................... 34 Gambar 3.6 Sequence Predicting Labels ........................................................... 37 Gambar 3.7 Sequence Diagram Add news ......................................................... 38 Gambar 3.8 Sequence Diagram add admin ....................................................... 38 Gambar 3.9 Entity Relationship Diagram Sistem klasifikasi berita. ................... 40 Gambar 3.10 Rancangan antarmuka halaman login. .......................................... 40 Gambar 3.11 Rancangan antamuka Manage Admin ........................................... 41 Gambar 3.12 Rancangan antarmuka Manage News Admin ................................ 42 Gambar 4.1 Alur proses klasifikasi.................................................................... 46 Gambar 4.2 Contoh dokumen dataset reuters-21578. ......................................... 48 Gambar 4.3 Database diagram ......................................................................... 49 Gambar 4.4 implementasi antarmuka login ....................................................... 53 Gambar 4.5 Antarmuka manage admin pada admin .......................................... 54 Gambar 4.6Antarmuk Manage News pada admin .............................................. 55 Gambar 4.7 Flow Graph Proses Training .......................................................... 62 Gambar 4.8 Flow Graph Proses prediksi label berita ......................................... 63 Gambar 4.9 Hasil testing F1 measure ................................................................ 64 Gambar 4.10 Waktu eksekusi testing................................................................. 65
xii
DAFTAR LAMPIRAN
Lampiran
Halaman
Lampiran A. Activity Diagram .................................................................. A-1 Lampiran B. Class Diagram ...................................................................... B-1 Lampiran C. Sequence Diagram ................................................................ C-1 Lampiran D. Rancangan Pengujian Blackbox ........................................... D-1 Lampiran E. Penomoran Kode untuk cyclomatic complexity ...................... E-1
xiii
1. BAB I PENDAHULUAN 1.1 Latar Belakang Berita merupakan sesuatu yang penting untuk memenuhi kebutuhan informasi sehari-hari bagi masyarakat. Kebutuhan masyarakat akan berita semakin meningkat, berbagai pihak mencoba untuk memberikan penyajian berita terbaik yaitu berita yang akurat, cepat dan terpercaya. Kebanyakan editor berita menggolongkan berita hanya ke satu kategori. Padahal suatu berita bisa saja memiliki beberapa topik yang berbeda. Seperti contoh berita “Roby Satria yang tertangkap saat memesan ganja” dapat tergolong ke dalam kategori entertainment dan kriminal. Contoh berita tersebut kurang tepat jika dikategorikan entertainment saja karena berita tersebut juga membahas tentang ganja yang mana topik tersebut berkaitan erat dengan kriminal. Apabila berita tidak di golongkan menjadi multilabel, pada saat pembaca berita ingin mencari berita yang tergolong ke dalam entertainment maka dia tidak akan mendapat berita dengan judul tersebut. Padahal berita tersebut membahas tentang artis. Telah banyak penelitian sebelumnya yang membahas mengenai klasifikasi dokumen teks seperti Afrianto & Kurniawati(2013) yang menggunakan Fuzzy CMeans Dan K-Nearest Neighbors. FCM menggunakan konsep pendekatan fuzzy sehingga sebuah data bisa menjadi anggota dari semua cluster yang ada. Metode ini digunakan untuk menghemat waktu dari KNN karena pencaran k-dokumen terdekat cukup dicari pada lingkungan anggot kelompok dokumen yang serupa `yang di usulkan adalah Support vector Machine oleh Yang, Sun, et al.(2009).Selain itu, ada juga penelitian yang diajukan oleh Ahmed, Khan & Rajeswari(2010) Menggunakan H-SISC (Hierarchical Semi-supervised Impurity based Subspace Clustering). Pada penelitian ini akan menerapkan Metode probabilistic Naïve Bayes Classifier (NBC) pada sistem yang akan dibangun. Menurut Chharia & Gupta(2013), mudah diterapkan dan dapat mengakomodasi data training baru 14
15
dengan mudah. Namun metode ini memiliki kelemahan dalam asumsi yang sulit dipenuhi, yaitu independensi feature kata. NBC akan mendapatkan nilai probabilitas 0 ketika terdapat suatu kata yang tidak ditemukan pada dokumen testing. Metode Smoothing digunakan untuk mengatasi hal ini dimana pada akan digunakan algoritma Modified Absoute Discount Chharia & Gupta(2013). Dalam klasifikasi text, dimensi fitur yang di dapatkan sangat besar, dimana satu kata yang muncul pada dokumen akan digunakan sebagai fitur. Untuk mengatasi permasalahan ini digunakan metode seleksi fitur seperi chi-squared, information gain, mutual information and symmetrical uncertainty Subhajit & Saptarsi(2013). Seleksi fitur yang terbaik untuk kasus multi label adalah information gain dan chisquare Nicolosi(2008). Pada penelitian ini akan digunakan chi-square dimana banyaknya fitur yang akan di pilih adalah fitur yang menghasilkan nilai di atas nilai kritis pada table x2. Dengan kelebihan dan kekurangan yang dimiliki oleh NBC, peneliti akan melakukan pengujian untuk mengetahi apakah dengan menggambungkan metode-metode di atas dapat meberikan hasil yang lebih optimal dari pada hanya menggunakan NBC saja.
1.2 Rumusan Masalah Berdasarkan latar belakang diatas, dapat di rumuskan permasalahan a.
Bagaimana membangun sistem terkomputerisasi yang mampu memberikan label terhadap berita yang di inputkan.
b.
Apakah sistem yang dibangun dengan menerapkan NBC, smoothing MAD dan feature selection chi-square mampu menghasilkan akurasi yang baik.
1.3 Batasan Masalah Agar tidak membahas terlalu jauh mengenai sistem pengklasifikasi berita, maka penysunnan pembuatan sistem ini akan dibatasi pada : a.
Istilah berbeda tetapi memiliki makna yang sama tidak di perhitungkan pada penelitian ini. Istilah-istilah tersebut akan dikenali sebagai istilah dengan makna yang berbeda.
b.
Kesalahan pengetikan tidak di perhitungkan pada penelitian ini.
16
1.4 Tujuan Penelitian Adapun tujuan yang ingin dicapai pada penelitian ini adalah: a. Membangun sistem terkomputerisasi yang mampu mengklasifikasikan berita secara multi-label. b. Mengetahui tingkat akurasi algoritma yang di pilih dalam menyelesaikan kasus klasifikasi multilabel.
1.5 Manfaat Peneitian Adapun manfaat yang diharapkan dari pembuatan tugas akhir ini adalah sebagai berikut: a.
Bagi Penulis Penulis dapat mengetahui bagaimana mengimplementasikan Naïve Bayes Classifier untuk klasifikasi teks, bagaimana mengoptimalkan algoritma terserbut dan bagaimana menguji akurasi sistem yang dibuat.
b.
Bagi Pengguna Sistem yang dihasilkan pada penelitian ini diharapkan dapat digunakan oleh orang yang berkepentingan untuk mengklasifikasikan berita dengan mudah dan cepat.
1.6 Metodologi Penelitian 1.6.1 Objek Penelitian Objek penelitian ini adalah proses pembuatan sistem klasifikasi berita multilabel dengan menggunakan algoritma naïve bayes. Penelitian ini dilakukan pada komputer atau laptop pribadi penulis dengan menggunakan data sampel berita yang penulis peroleh dari Reuters – 21578 Text Categorization Collection Data Set.
1.6.2 Lingkungan Penelitian Lingkungan penelitian dilakukan pada laptop pribadi penulis. Namun implementasi pada lingkungan kerja nyata ketika sistem klasifikasi berita
17
multilabel telah benar- benar dioperasikan, tidak menutup kemungkinan spesifikasi laptop atau komputer yang digunakan akan berubah mengikuti kebutuhan sistem.
1.6.3 Metode Pengumpulan Data Metode pengumpulan data pada penelitian ini dilakukan menggunakan studi literatur. Tujuan dari studi literatur ini adalah literatur yang membahas tentang data berita dan tentang naïve bayes dengan smoothing modified absolute discount dan feature selection chi square sehingga dapat dijadikan acuan dasar penelitian ini.
1.6.4 Perancangan Sistem Pada penelitian ini, perancangan aplikasi menggunakan Unified Modelling Language (UML) sebagai acuan untuk merancang aplikasi yang akan dibangun. 1.
Diagram Use Case Use case atau diagram use case merupakan pemodelan untuk kelakuan
(behavior) sistem informasi yang akan dibuat. Menurut Shalahuddin & A.S.(2015). Use case mendeskripsikan sebuah interaksi antara satu atau lebih aktor dengan sistem informasi yang akan dibuat. Secara kasar, use case digunakan untuk mengetahui fungsi apa saja yang ada di dalam sebuah sistem informasi dan siapa saja yang berhak menggunakan fungsi- fungsi itu. 2.
Diagram Aktivitas Diagram aktivitas atau activity diagram menurut Shalahuddin & A.S.(2015)
adalah diagram menggambarkan workflow (aliran kerja) atau aktivitas dari sebuah sistem atau proses bisnis. Yang perlu diperhatikan adalah bahwa diagram aktivitas menggambarkan aktivitas sistem bukan apa yang dilakukan aktor, jadi aktivitas yang dapat dilakukan oleh sistem 3.
Diagram Kelas Diagram kelas atau class diagram menggambarkan struktur sistem dari segi
pendefinisian kelas- kelas yang akan dibuat untuk membangun sistem. Kelas memiliki apa yang disebut atribut dan metode atau operasi. Kelas- kelas yang ada
18
dengan kebutuhan sistem harus dapat melakukan fungsi- fungsi dengan kebutuhan sistem Shalahuddin & A.S.(2015). 4.
Diagram Sequence Diagram Sequence atau Sequence Diagram merupakan salah satu diagram
Interaction yang menjelaskan bagaimana suatu operasi itu dilakukan. Diagram ini diatur berdasarkan waktu. Objek- objek yang berkaitan dengan proses berjalannya operasi diurutkan dari kiri ke kanan berdasarkan waktu terjadinya dalam pesan yang terurut. Kendall & Kendall(2010).
1.6.5 Implementasi Sistem Untuk menunjang dan membantu dalam melakukan penelitian sampai tahap implementasi pembuatan sistem ini, dibutuhkan sebuah laptop yang memiliki spesifikasi sebagai berikut: 1.
Processor Pentium® Dual-Core CPU T4300 @ 2.10 GHz
2.
Memory 3 GB
3.
Hardisk 500 GB
4.
Touchpad, Keyboard, dan Monitor Sedangkan untuk kebutuhan perangkat lunak mulai tahap penelitian sampai
pada tahapan implementasi sistem ini menggunakan beberapa perangkat lunak sebagai berikut: 1.
Operating System Windows 7 Ultimate Edition
2.
Mengimplementasikan perancangan ke dalam kode program dengan menggunakan bahasa pemrograman PHP
3.
Mengimplementasikan database MySQL.
1.6.6 Metode Yang Digunakan Pada penelitian ini dalam membangun perancangan dan implementasi Aplikasi Klasifikasi Berita Multilabel digunakan metode pengembangan perangkat lunak yakni model proses waterfall. Model proses ini terdiri dari 5 fase yaitu Requirements Analysis and Definition, System and Software Design, Implementation and Unit Testing, Integration and System Testing, dan Operation
19
and Maintenance. Pada tiap fasenya akan dilakukan evaluasi dan dokumentasi apakah fase tersebut sudah dilakukan dengan benar sebelum melanjutkan ke fase berikutnya.
1.6.7 Evaluasi dan Pengujian Sistem Pengujian sistem merupakan aktifitas-aktifitas yang dilakukan pada sebuah perangkat lunak untuk memastikan penerapan perangkat lunak telah sesuai dengan fungsinya atau belum. Pada pengujian ini dilakukan dengan tiga tipe yaitu pengujian
yang
pertama
dilakukan
menggunakan
static
testing
yaitu
membandingkan hasil perancangan yang dibuat dengan kebutuhan yang telah didapat dari pengguna. Pengujian yang kedua dilakukan terhadap aplikasi dengan menggunakan pengujian black-box dan pengujian yang ketiga menggunakan pengujian whitebox testing akan dilakukan dengan pengujian basis path atau dikenal engan cyclomatic complexity.
