RANCANG BANGUN SISTEM PENCARIAN DOKUMEN JURNAL MENGGUNAKAN METODE BM25+
LEMBAR JUDUL SKRIPSI
DENI SUPRIAWAN NIM. 1108605001
PROGRAM STUDI TEKNIK INFORMATIKA JURUSAN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS UDAYANA BUKIT JIMBARAN 2016
SURAT PERNYATAAN KEASLIAN KARYA ILMIAH Yang bertanda tangan di bawah ini menyatakan bahwa naskah Skripsi dengan judul: “RANCANG BANGUN SISTEM PENCARIAN DOKUMEN JURNAL MENGGUNAKAN METODE BM25+”
Nama
: Deni Supriawan
NIM
: 1108605001
Program Studi : Teknik Informatika E-mail
:
[email protected]
Nomor telp/HP : 082144190930 Alamat
: Jl. Bedugul 17 Sidakarya, Denpasar
Belum pernah dipublikasikan dalam dokumen skripsi, jurnal nasional maupun internasional atau dalam prosiding manapun, dan tidak sedang atau akan diajukan untuk publikasi di jurnal atau prosiding manapun. Apabila di kemudian hari terbukti terdapat pelanggaran kaidah – kaidah akademik pada karya ilmiah saya, maka saya bersedia menanggung sanksi-sanksi yang dijatuhkan karena kesalahan tersebut, sebagaimana diatur oleh Peraturan Menteri Pendidikan Nasional Nomor 17 Tahun 2010 tentang Pencegahan dan Penanggulangan Plagiat di Perguruan Tinggi. Demikian Surat Pernyataan ini saya buat dengan sesungguhnya untuk dapat dipergunakan bilamana diperlukan. Denpasar, 1 Juli 2016 Yang membuat pernyataan,
Deni Supriawan NIM. 1108605001 ii
LEMBAR PENGESAHAN TUGAS AKHIR Judul Kompetensi Nama NIM Tanggal Seminar
: Rancang Bangun Sistem Pencarian Dokumen Jurnal Menggunakan Metode BM25+ : Rekayasa Perangkat Lunak : Deni Supriawan : 1108605001 : 17 Juni 2016 Disetujui oleh:
Pembimbing I
Penguji I
I Made Widiartha, S.Si., M.Kom. NIP. 198212202008011008
Drs. I Wayan Santiyasa, M.Si. NIP. 196704141992031002
Pembimbing II
Penguji II
Ida Bagus Gede Dwidasmara, S.Kom., M.Cs. NIP. 198503152010121007
I Putu Gede Hendra Suputra, S.Kom., M.Kom. NIP. 198812282014041001 Penguji III
I Gede Oka Gartria Atitama, S.Kom., M.Kom. NIP. 1991022620160312001 Mengetahui, Jurusan Ilmu Komputer FMIPA UNUD Ketua,
Agus Muliantara, S.Kom., M.Kom. NIP. 198006162005011001 iii
Judul
: Rancang Bangun Sistem Pencarian Dokumen Menggunakan Metode BM25+ Nama : Deni Supriawan NIM : 1108605001 Pembimbing I : I Made Widiartha, S.Si., M.Kom. Pembimbing II : Ida Bagus Gede Dwidasmara, S.Kom., M.Cs.
Jurnal
ABSTRAK Jurnal penelitian merupakan dokumen yang diperlukan bagi para mahasiswa yang sedang melakukan penelitian tugas akhir untuk dijadikan sebagai referensi. Jumlah dokumen jurnal tentunya akan terus bertambah, sehingga pencarian secara manual belum tentu menghasilkan jurnal yang diinginkan. Dari masalah ini diperlukan suatu sistem pencarian dokumen yang dapat memberikan hasil pencarian yang sesuai dengan keinginan pengguna. Sistem Temu Kembali Informasi (STKI) merupakan kegiatan untuk menemukan suatu material (dokumen) dari data yang tidak terstruktur (berbentuk teks) yang dapat memenuhi kebutuhan informasi yang dicari dalam koleksi dokumen besar. Sistem bekerja dengan menghitung bobot dokumen pada hasil pencarian untuk mengetahui tingkat relevansinya dengan kata kunci pengguna. Salah satu metode pembobotan dokumen yang digunakan dalam masalah ini adalah Metode BM25+. BM25+ memiliki fungsi yang sesuai dengan prinsip pembobotan yang baik, yaitu memiliki inverse document frequecy (IDF), term frequency (TF), fungsi normalisasi dari panjang dokumen (document length normalization), dan terdapat parameter delta untuk mengatur batas bawah dari normalisasi TF terhadap panjang dokumen. Data dokumen yang digunakan berjumlah 264 jurnal terdiri dari Jurnal SNATIA dan JELIKU. Dari hasil pengujian static, black box, white box, dan performance, sistem telah berhasil dirancang dan diimplementasikan berdasarkan hasil definisi kebutuhan fungsional dan non-fungsional. Dari hasil pengujian tuning parameter delta, nilai Non Interpolated Average Precision (NIAP) yang dihasilkan oleh metode BM25+ lebih besar dari metode BM25 yakni meningkat sekitar 10.53%. Nilai delta 0.7 akan menghasilkan nilai NIAP maksimal (0.84) untuk semua kemungkinan panjang dokumen. Hal ini menunjukkan sistem mampu memberikan bobot besar untuk dokumen yang relevan dengan kata kunci, sehingga dokumen tersebut terdapat pada urutan teratas pada hasil pencarian. Kata Kunci: Sistem Pencarian Dokumen, BM25+, NIAP
iv
Title
: Search System Design of Journal Document by Using BM25+ Method Name : Deni Supriawan Registration : 1108605001 Main Supervisor : I Made Widiartha, S.Si., M.Kom. Second Supervisor : Ida Bagus Gede Dwidasmara, S.Kom., M.Cs. ABSTRACT Journal of research is the necessary documents for the students who are undertaking research thesis to be used as a reference. The number of journal document will certainly continue to grow, so that the manual search is not necessarily obtain the desired journal. Of this problem, it is required a document retrieval system that can provide search results according to the user’s needs. Information Retrieval System (STKI) is an activity to find a material (documents) from unstructured data (text-based) to meet the needs of the information sought in a large document collection. The system works by calculating the weight of documents on the search results to find the level of relevance to the keywords of the users. One of the document weighting methods used in this problem is the method of BM25+. It has the function according to the principle of good weighting scheme, i.e. it has the inverse document frequecy (IDF), term frequency (TF), the function of the document length normalization, and a parameter of delta to set the lower limit of the normalization of TF to the length of document. Document data used were 264 journals, consisting of Journals of SNATIA and JELIKU. From the results of static, black box, white box, and performance testing, the system has been successfully designed and implemented based on the definition of functional and non-functional requirements. From the test results of the tuning parameter delta, Non Interpolated Average Precision (NIAP) values produced by the BM25+ method was greater than the BM25 method, which increased by about 10.53%. Delta value of 0.7 would result in a maximum NIAP (0.84) for all the possible length of the document. This indicated that the system was able to give great weight to the relevant documents by keyword, so that these documents were on the top of the search results. Keywords: Document Search System, BM25+, NIAP
v
KATA PENGANTAR Tugas Akhir dengan judul Rancang Bangun Sistem Pencarian Dokumen Jurnal Menggunakan Metode BM25+ ini disusun sebagai salah satu syarat dalam melakukan penelitian Tugas Akhir di Jurusan Ilmu Komputer FMIPA Universitas Udayana. Sehubungan dengan telah terselesaikannya penelitian ini, maka diucapkan terima kasih dan penghargaan kepada berbagai pihak yang telah membantu penulis, antara lain: 1. Bapak I Made Widiartha, S.Si., M.Kom. sebagai Pembimbing I yang telah membimbing dan membantu menyempurnakan penelitian tugas akhir ini; 2. Bapak Ida Bagus Gede Dwidasmara, S.Kom., M.Cs. sebagai Pembimbing II yang telah bersedia mengkritisi, memeriksa, dan menyempurnakan penelitian tugas akhir ini; 3. Komisi Tugas Akhir Jurusan Ilmu Komputer FMIPA UNUD, yang telah memberikan petunjuk dalam penyusunan laporan penelitian tugas akhir ini; 4. Bapak-bapak dan Ibu-ibu dosen di Jurusan Ilmu Komputer yang secara tidak langsung telah memberikan dukungan serta arahan kepada penulis; 5. Seluruh teman-teman mahasiswa Jurusan Ilmu Komputer FMIPA Universitas Udayana yang telah memberikan bantuan dan dukungan moral dalam penyelesaian penelitian tugas akhir ini. Disadari pula bahwa sudah tentu penelitian tugas akhir ini masih mengandung kelemahan dan kekurangan. Memperhatikan hal ini, maka masukan dan saran-saran penyempurnaan sangat diharapkan. Bukit Jimbaran, Juni 2016
Penulis
vi
DAFTAR ISI
LEMBAR JUDUL ................................................................................................... i SURAT PERNYATAAN KEASLIAN KARYA ILMIAH .................................... ii LEMBAR PENGESAHAN TUGAS AKHIR ....................................................... iii ABSTRAK ............................................................................................................. iv ABSTRACT ............................................................................................................ v KATA PENGANTAR ........................................................................................... vi DAFTAR ISI ......................................................................................................... vii DAFTAR TABEL .................................................................................................. ix DAFTAR GAMBAR .............................................................................................. x DAFTAR LAMPIRAN ......................................................................................... xii BAB I PENDAHULUAN ....................................................................................... 1 1.1 Latar Belakang ......................................................................................... 1 1.2 Rumusan Masalah .................................................................................... 3 1.3 Tujuan Penelitian ...................................................................................... 3 1.4 Batasan Masalah ....................................................................................... 3 1.5 Manfaat Penelitian .................................................................................... 3 1.6 Metodelogi Penelitian ............................................................................... 4 1.6.1 Desain Penelitian ............................................................................... 4 1.6.2 Pengumpulan Data ............................................................................ 5 1.6.3 Pengolahan Data Awal ...................................................................... 5 1.6.4 Metode yang digunakan .................................................................... 6 1.6.5 Eksperimen dan Pengujian Metode ................................................... 6 1.6.6 Evaluasi dan Validasi Hasil .............................................................. 8 1.6.7 Jadwal Pelaksanaan Kegiatan ......................................................... 11 BAB II TINJAUAN PUSTAKA........................................................................... 12 2.1. Sistem Temu Kembali Informasi............................................................ 12 2.2. Text Preprocessing ................................................................................. 14 2.2.1. Case Folding ................................................................................... 14 2.2.2. Tokenizing ....................................................................................... 15 2.2.3. Filtering .......................................................................................... 15 2.2.4. Stemming ......................................................................................... 16 2.3. BM25+.................................................................................................... 17 2.4. Model Proses Waterfall .......................................................................... 20 2.5. Unified Modeling Language (UML) ...................................................... 21 2.5.1 Use Case Diagram .......................................................................... 22 2.5.2 Class Diagram ................................................................................ 24 2.5.3 Activity Diagram ............................................................................. 27 2.5.4 Sequence Diagram .......................................................................... 28 2.6. Teknik Pengujian Perangkat Lunak ....................................................... 31 2.6.1. Static Testing ................................................................................... 31 2.6.2. White Box Testing ........................................................................... 31 2.6.3. Black Box Testing ............................................................................ 32 vii
2.6.4. Performance Testing ....................................................................... 33 2.7. Precision, Recall, dan NIAP .................................................................. 33 2.8. Tinjauan Studi ........................................................................................ 35 BAB III ANALISIS DAN PERANCANGAN SISTEM ...................................... 37 3.1. Definisi Kebutuhan................................................................................. 37 3.1.1. Kebutuhan Fungsional .................................................................... 37 3.1.2. Kebutuhan Non-Fungsional ............................................................ 38 3.2. Perancangan Sistem ................................................................................ 38 3.2.1 Use Case Diagram .......................................................................... 38 3.2.2 Activity Diagram ............................................................................. 41 3.2.3 Class Diagram ................................................................................ 57 3.2.4 Sequence Diagram .......................................................................... 59 3.2.5 Entity Relationship Diagram........................................................... 70 3.3. Perancangan Antarmuka ......................................................................... 71 BAB IV HASIL DAN PEMBAHASAN .............................................................. 78 4.1. Lingkungan Perancangan dan Implementasi Sistem .............................. 78 4.2. Implementasi Database .......................................................................... 78 4.3. Implementasi Antarmuka ....................................................................... 80 4.3.1 Antarmuka User .............................................................................. 80 4.3.2 Antarmuka Admin ........................................................................... 84 4.4. Implementasi Sistem .............................................................................. 85 4.5. Pengujian Sistem .................................................................................... 90 4.5.1. Static Testing ................................................................................... 90 4.5.2. Black Box Testing ............................................................................ 91 4.5.3. White Box Testing ........................................................................... 95 4.5.4. Performance Testing ....................................................................... 99 4.5.5. Precision dan Recall ..................................................................... 104 4.5.6. Tuning Parameter BM25+ ............................................................. 106 BAB V KESIMPULAN DAN SARAN .............................................................. 109 5.1. Kesimpulan ........................................................................................... 109 5.2. Saran ..................................................................................................... 110 DAFTAR PUSTAKA ......................................................................................... 111
viii
DAFTAR TABEL
Tabel 1.1. Rancangan Tabel Kebutuhan Fungsional .............................................. 6 Tabel 1.2. Rancangan Tabel Kebutuhan Non-Fungsional ...................................... 7 Tabel 1.3. Rancangan Tabel Static Testing ............................................................. 9 Tabel 1.4. Rancangan Tabel Black Box Testing ...................................................... 9 Tabel 1.5. Rancangan Tabel Performance Testing ............................................... 10 Tabel 1.6. Rancangan Tabel Precision dan Recall ............................................... 10 Tabel 1.7. Jadwal Kegiatan ................................................................................... 11 Tabel 2.1. Simbol Use Case Diagram .................................................................. 22 Tabel 2.2. Simbol Class Diagram ......................................................................... 25 Tabel 2.3. Simbol Activity Diagram ..................................................................... 27 Tabel 2.4. Simbol Sequence Diagram................................................................... 29 Tabel 2.5. Hubungan Cyclomatic Complexity dan Resiko .................................... 32 Tabel 3.1. Kebutuhan fungsional .......................................................................... 37 Tabel 3.2. Kebutuhan Non-fungsional .................................................................. 38 Tabel 3.3. Definisi Aktor ...................................................................................... 39 Tabel 3.4. Definisi Use Case................................................................................. 39 Tabel 3.5. Hubungan Class dan Use Case ............................................................ 58 Tabel 4.1. Kode Preprocessing Teks .................................................................... 86 Tabel 4.2. Kode Indexing ...................................................................................... 87 Tabel 4.3. Kode Hitung Bobot Dokumen ............................................................. 88 Tabel 4.4. Hasil Static Testing .............................................................................. 90 Tabel 4.5. Skenario Black Box Testing ................................................................. 91 Tabel 4.6. Hasil Black Box Testing ....................................................................... 92 Tabel 4.7. Flowgraph Indexing ............................................................................. 96 Tabel 4.8. Kasus Uji Proses Indexing ................................................................... 97 Tabel 4.9. Flowgraph Hitung Bobot Dokumen .................................................... 98 Tabel 4.10. Kasus Uji Proses Hitung Bobot Dokumen......................................... 99 Tabel 4.11. Hasil Performance Testing Query 1 Term ....................................... 100 Tabel 4.12. Hasil Performance Testing Query 2 Term ....................................... 100 Tabel 4.13. Hasil Performance Testing Query 3 Term ....................................... 101 Tabel 4.14. Hasil Performance Testing Query 4 Term ....................................... 101 Tabel 4.15. Hasil Performance Testing Query 5 Term ....................................... 102 Tabel 4.16. Rata-rata Waktu Berdasarkan Penambahan Term ........................... 102 Tabel 4.17. Rata-rata Waktu Berdasarkan Penambahan Dokumen .................... 103 Tabel 4.18. Hasil Pengujian Precision dan Recall .............................................. 105
ix
DAFTAR GAMBAR
Gambar 2.1. Bagian-bagian Sistem Temu Kembali Informasi ............................. 13 Gambar 2.2. Contoh Case Folding ....................................................................... 15 Gambar 2.3. Contoh Tokenisasi ............................................................................ 15 Gambar 2.4. Contoh Filtering ............................................................................... 16 Gambar 2.5. Contoh Stemming ............................................................................. 17 Gambar 2.6. Model Proses Waterfall .................................................................... 20 Gambar 3.1. Use Case Diagram Sistem Pencarian Jurnal .................................... 39 Gambar 3.2. Activity Diagram Autentikasi ........................................................... 41 Gambar 3.3. Activity Diagram Tambah Data Jurnal ............................................. 42 Gambar 3.4. Activity Diagram Edit Data Jurnal ................................................... 43 Gambar 3.5. Activity Diagram Hapus Data Jurnal ................................................ 44 Gambar 3.6. Activity Diagram Lihat Master Data Jurnal ..................................... 45 Gambar 3.7. Activity Diagram Tambah Data Publikasi........................................ 46 Gambar 3.8. Activity Diagram Edit Data Publikasi .............................................. 47 Gambar 3.9. Activity Diagram Hapus Data Publikasi .......................................... 48 Gambar 3.10. Activity Diagram Lihat Master Data Publikasi .............................. 49 Gambar 3.11. Activity Diagram Pencarian Publikasi ........................................... 50 Gambar 3.12. Activity Diagram Lihat Detail Publikasi ........................................ 51 Gambar 3.13. Activity Diagram Melihat List Jurnal ............................................. 51 Gambar 3.14. Activity Diagram Melihat List Publikasi ........................................ 52 Gambar 3.15. Activity Diagram Preprocessing Teks ........................................... 53 Gambar 3.16. Activity Diagram Indexing ............................................................. 54 Gambar 3.17. Activity Diagram Hitung Bobot Dokumen .................................... 56 Gambar 3.18. Class Diagram Sistem Pencarian Jurnal ........................................ 57 Gambar 3.19. Sequence Diagram Autentikasi ...................................................... 60 Gambar 3.20. Sequence Diagram Tambah Data Jurnal ........................................ 61 Gambar 3.21. Sequence Diagram Edit Data Jurnal .............................................. 62 Gambar 3.22. Sequence Diagram Hapus Data Jurnal ........................................... 63 Gambar 3.23. Sequence Diagram Lihat Master Data Jurnal ................................ 63 Gambar 3.24. Sequence Diagram Tambah Data Publikasi ................................... 64 Gambar 3.25. Sequence Diagram Edit Data Publikasi ......................................... 65 Gambar 3.26. Sequence Diagram Hapus Data Publikasi...................................... 66 Gambar 3.27. Sequence Diagram Lihat Master Data Publikasi ........................... 66 Gambar 3.28. Sequence Diagram Pencarian Publikasi......................................... 67 Gambar 3.29. Sequence Diagram Lihat Detail Publikasi ..................................... 68 Gambar 3.30. Sequence Diagram Lihat List Jurnal .............................................. 69 Gambar 3.31. Sequence Diagram Lihat List Publikasi ......................................... 69 Gambar 3.32. Entity Relationship Diagram Sistem Pencarian Jurnal .................. 70 Gambar 3.33. Rancangan Antarmuka Home......................................................... 71 Gambar 3.34. Rancangan Antarmuka Detail Publikasi ........................................ 72 Gambar 3.35. Rancangan Antarmuka List Jurnal ................................................. 73 Gambar 3.36. Rancangan Antarmuka List Publikasi ............................................ 74 x
Gambar 3.37. Rancangan Antarmuka Login ......................................................... 75 Gambar 3.38. Rancangan Antarmuka Dashboard Admin .................................... 75 Gambar 3.39. Rancangan Antarmuka Master Data .............................................. 76 Gambar 3.40. Rancangan Antarmuka Tambah Data ............................................ 77 Gambar 4.1. Skema Database Sistem Pencarian Jurnal ....................................... 79 Gambar 4.2. Antarmuka Home ............................................................................. 80 Gambar 4.3. Antarmuka Hasil Pencarian .............................................................. 81 Gambar 4.4. Antarmuka Detail Publikasi ............................................................. 81 Gambar 4.5. Antarmuka List Jurnal ...................................................................... 82 Gambar 4.6. Antarmuka List Publikasi ................................................................. 83 Gambar 4.7. Antarmuka Login.............................................................................. 83 Gambar 4.8. Antarmuka Dashboard ..................................................................... 84 Gambar 4.9. Antarmuka Master Data ................................................................... 84 Gambar 4.10. Antarmuka Tambah Data ............................................................... 85 Gambar 4.11. Grafik Waktu berdasarkan Penambahan Dokumen ..................... 103 Gambar 4.12. Grafik Waktu berdasarkan Penambahan Term............................. 104 Gambar 4.13. Grafik Hasil Uji Precision dan Recall ......................................... 105 Gambar 4.14. Grafik Hasil Uji NIAP Tuning Parameter Delta .......................... 107 Gambar 4.15. Grafik Hasil Uji Precision Tuning Parameter Delta .................... 107 Gambar 4.16. Grafik Hasil Uji Recall Tuning Parameter Delta ......................... 108
xi
DAFTAR LAMPIRAN
LAMPIRAN 1. Hasil Uji Precision dan Recall 2. Hasil Uji Tuning Parameter BM25+
xii