ESSAY GRADING DENGAN KONSEP SIMILARITY RABIN KARP
Kompetensi
:
RPL (Rekayasa Perangkat Lunak)
Nama
:
Ida Bagus Komang Winduyasa
NIM
:
1208605014
Pembimbing
:
1. Agus Muliantara, S. Kom., M. Kom 2. I Putu Gede Hendra Suputra, S. Kom., M. Kom.
ABSTRAK Esai adalah alat pengujian untuk menilai kemampuan pengetahuan pelajar yang melibatkan kemampuan untuk mengingat, mengorganisasikan, mengekspresikan dan mengintegrasikan serta mengembangkan gagasan berdasarkan pengetahuan yang dimiliki. Elearning Moodle merupakan salah satu elearning yang menyediakan evaluasi esai. Dalam proses penilaian esai pada Moodle masih memiliki kekurangan karena dilakukan secara manual. Pemeriksaan esai membutuhkan waktu yang lebih lama dibanding metode opsional, perbedaan pemahaman terhadap maksud dari jawaban esai juga mempengaruhi penilaian. Semakin banyak jumlah ujian yang dinilai mengakibatkan kualitas penilaian secara manual semakin menurun. Essay Grading merupakan sistem automasi penilaian esai terintegrasi dengan Elearning Moodle yang mengimplementasikan algoritma Rabin Karp. Essay Grading bekerja dengan melakukan pencocokan string dengan menghitung kesamaan penggunaan kata dan urutan kata antara jawaban dengan kunci jawaban. Proses penghitungan kesamaan dilakukan melalui dua tahapan, preproses yaitu tokenizing, filtering dan stemming, serta proses utama yakni k-gram parsing, hashing, dan string matching. Hasil perhitungan string matching akan dijadikan sebagai nilai dari masing masing jawaban. Penelitian ini menunjukkan automasi penilaian esai Essay Grading dengan algoritma Rabin Karp terintegrasi dengan Moodle berhasil diimplementasikan. Perolehan hasil penilaian sistem terhadap esai bervariatif untuk setiap nilai k-gram dan jenis stemming yang digunakan. Essay Grading dapat memberikan penilaian yang optimal dengan k-gram optimal 3 dan stemming arifin. Penilaian terendah adalah 57,9 dan tertinggi 93,9 dengan rata-rata tingkat perbedaan penilaian esai sebesar 14,57% dari penilaian manual.
Kata Kunci : Essay Grading, Rabin Karp, K-gram, Hashing, String Matching.
vi
THE ESSAY GRADING BY THE CONCEPT OF RABIN KARP SIMILARITY
Competence
:
RPL (Software Engineering)
Name
:
Ida Bagus Komang Winduyasa
Registration
:
1208605014
Supervisors
:
1. Agus Muliantara, S. Kom., M. Kom 2. I Putu Gede Hendra Suputra, S. Kom., M. Kom.
ABSTRACT An essay is a testing tool to assess the students’ knowledge which involves the ability to remember, organize, express and integrate and develope ideas based on their knowledge. E-learning of Moodle is one of the e-learnings that provides essay evaluation. In an essay on Moodle assessment process still has shortcomings because it is conducted manually. Assessment or evaluation of essays takes longer than the optional method; a difference of understanding of the intent of the essay also affects the assessment. The more the number of tests that being assessed results in the more decreasing the quality of manual assessment. Essay Grading is an automation system of essay assessment integrated with E-learning of Moodle that implements the algorithm of Rabin Karp. Essay Grading works by matching string by calculating the similarity of word usage and the word order of the answers with the answer key. The process of calculating the similarity was conducted in two stages, the preprocessing, namely tokenizing, filtering and stemming, as well as the main processes namely k-gram parsing, hashing, and string matching. The result of the calculation of string matching will be used as the grade of each answer. This study showed that the automation of Essay Grading with Rabin Karp algorithm integrated with Moodle was successfully implemented. The obtaining of the results of the essay grading system was varied for each value of K-gram and the stemming types used. Essay Grading can provide optimal assessment of the K-gram optimal 3 and stemming arifin. The lowest score was 57.9 and the highest was 93.9 with the average rate differences of essay grading of 14.57% of the manual grading. Keywords: Essay Grading, Rabin Karp, K-gram, Hashing, String Matching.
vii
KATA PENGANTAR Penelitian dengan judul Essay Grading dengan Konsep Similarity Rabin Karp ini disusun dalam rangkaian kegiatan pelaksanaan Tugas Akhir di Jurusan Ilmu Komputer FMIPA UNUD. Sehubungan dengan telah terselesaikannya penelitian ini, maka diucapkan terima kasih dan penghargaan kepada berbagai pihak yang telah membantu penulis, antara lain: 1. Bapak Agus Muliantara, S. Kom., M. Kom sebagai Pembimbing I yang telah banyak membantu menyempurnakan penelitian ini; 2. I Putu Gede Hendra Suputra, S. Kom., M. Kom.sebagai Pembimbing II yang telah bersedia mengkritisi, memeriksa dan menyempurnakan penelitian ini; 3. Dra. Ni Wayan Arnati, M.Hum., sebagai dosen pakar linguistik yang telah bersedia menilai, memeriksa dan menyempurnakan penelitian ini. 4. Bapak I Made Widiartha, S.Si., M.Kom, I Gede Santi Astawa, S.T., M.Cs, I Komang Ari Mogi, S.Kom, M.Kom dan dosen lainnya yang tidak dapat disebutkan satu per satu, sebagai pakar informatika dan responden yang bersedia menyempurnakan, menilai, memeriksa dan memberikan masukan dan saran pada penelitian ini;
5. Bapak-bapak dan ibu-ibu dosen di Jurusan Ilmu Komputer, yang telah meluangkan waktu turut memberikan saran dan masukan dalam penyempurnaan penelitian ini; 6. Teman - teman di Jurusan Ilmu Komputer yang telah memberikan dukungan moral dan semangat dalam penyelesaian penelitian ini. Disadari pula bahwa sudah tentu penelitian ini masih mengandung kelemahan dan kekurangan. Memperhatikan hal ini, maka masukan dan saransaran penyempurnaan sangat diharapkan. Bukit Jimbaran, 26 Agustus 2016
Penulis
viii
DAFTAR ISI HALAMAN JUDUL................................................................................................ i HALAMAN SAMPUL ........................................................................................... ii LEMBAR PENGESAHAN TUGAS AKHIR ........................................................ v ABSTRAK ............................................................................................................. vi ABSTRACT ........................................................... Error! Bookmark not defined. KATA PENGANTAR ......................................................................................... viii DAFTAR ISI .......................................................................................................... ix DAFTAR GAMBAR ............................................................................................ xii DAFTAR TABEL ................................................................................................ xiv DAFTAR LAMPIRAN ......................................................................................... xv BAB I PENDAHULUAN ....................................................................................... 1 1.1.
Latar Belakang ......................................................................................... 1
1.2.
Rumusan Masalah .................................................................................... 3
1.3.
Batasan Masalah ....................................................................................... 3
1.4.
Tujuan ....................................................................................................... 4
1.5.
Manfaat ..................................................................................................... 4
1.6.
Metode Penelitian ..................................................................................... 5
1.6.1.
Bahan Dan Lokasi Penelitian ............................................................ 5
1.6.2.
Metode Pengumpulan Data ............................................................... 5
1.6.3.
Metode Pengembangan Perangkat Lunak ......................................... 5
BAB II KAJIAN TEORI......................................................................................... 7 2.1.
Ujian Esai ................................................................................................. 7
2.2.
Konsep Kepakaran ................................................................................... 8
2.3.
Sistem Elearning Moodle ......................................................................... 8
2.4.
Sistem Temu Kembali Informasi (Information Retrieval) ....................... 8
2.4.1.
Text Mining ....................................................................................... 9
2.4.2.
Proses Text Mining ............................................................................ 9
2.4.2.1.
Text Preprocessing .................................................................... 9
2.4.2.2.
Pencocokan Kata (String Matching) ........................................ 10
2.4.3.
Algoritma String Matching Rabin Karp ......................................... 11
ix
2.4.3.1.
K- Gram ................................................................................... 12
2.4.3.2.
Hashing .................................................................................... 13
2.4.3.3.
Konsep Dasar Rabin Karp ....................................................... 14
2.4.4. 2.5.
Modified Rabin Karp Algorithm ..................................................... 15
Tinjauan Empiris .................................................................................... 17
BAB III ANALISIS DAN PERANCANGAN SISTEM ...................................... 19 3.1.
Analisa Kebutuhan ................................................................................. 19
3.1.1.
System Requirement ........................................................................ 19
3.1.2.
Kebutuhan Fungsi Sistem / Fungction Requirement ...................... 21
3.1.3.
Kebutuhan Interface ........................................................................ 23
3.2.
Desain dan Model Sistem ....................................................................... 23
3.2.1.
Alur Kerja Sistem ............................................................................ 23
3.2.2.
Diagram Alir Sistem (Flow Chart) ................................................. 24
3.3.
3.2.2.1.
Diagram Konteks dan Data Flow Diagram Sistem ................ 31
3.2.2.2.
Entity Relationalship Diagram ................................................ 34
Tahap Implementasi Sistem ................................................................... 35
3.3.1.
Arsitektur Integrasi Sistem Moodle dan Essay Grading ................. 36
3.3.2.
Penambahan Modul pada Moodle ................................................... 37
3.3.3.
Desain Antar Muka Sistem ............................................................. 38
3.4.
Tahap Pengujian ..................................................................................... 42
3.4.1.
Skenario Pengujian Sistem.............................................................. 42
3.4.2.
Static Testing (Pengujian Statis) ..................................................... 43
3.4.3.
Functional Testing........................................................................... 43
3.4.4.
Perancangan Tabel Hasil Pengujian ................................................ 44
BAB IV PEMBAHASAN ..................................................................................... 45 4.1.
Lingkungan Implementasi ...................................................................... 45
4.2.
Integrasi dan Implementasi Antar Muka ................................................ 45
4.3.
Implementasi Sistem .............................................................................. 46
4.3.1.
Integrasi Antar Muka Sistem .......................................................... 47
4.3.2.
Tahap Preprocessing ....................................................................... 53
4.3.2.1.
Seleksi Data Jawaban............................................................... 54
4.3.2.2.
Case Folding dan Tokenizing .................................................. 54
x
4.3.2.3.
Filtering .................................................................................... 55
4.3.2.4.
Stemming ................................................................................. 55
4.3.3.
Tahap Processing ............................................................................ 56
4.3.3.1.
K-gram ..................................................................................... 56
4.3.3.2.
Hashing .................................................................................... 57
4.3.3.3.
Proses String Matching ............................................................ 57
4.3.3.4.
Similarity Coefficient ............................................................... 58
4.3.4.
Tahap Pengujian .............................................................................. 58
4.3.4.1.
Static Testing ........................................................................... 58
4.3.4.2.
Functional Testing ................................................................... 61
4.3.4.3.
User Navigation Testing .......................................................... 63
4.3.4.4.
Black Box Testing ................................................................... 65
4.3.4.5.
Pengujian Penilaian Sistem...................................................... 65
4.3.5.
Analisa Hasil Uji ............................................................................. 78
BAB V KESIMPULAN DAN SARAN ................................................................ 84 5.1.
Kesimpulan ............................................................................................. 84
5.2.
Saran ....................................................................................................... 85
DAFTAR PUSTAKA ........................................................................................... 86 LAMPIRAN .......................................................................................................... 88
xi
DAFTAR GAMBAR Gambar. 2.1. Alur Text Preprocessing .................................................................. 10 Gambar. 2.2. Comparison block awal ................................................................... 14 Gambar. 2.3. Menggeser comparison block.......................................................... 14 Gambar. 2.4. Pembandingan kedua....................................................................... 15 Gambar. 2.5. Perbandingan keempat (nilai hash sama) ........................................ 15 Gambar. 2.6. Perbandingan kelima (string ditemukan) ........................................ 15 Gambar. 3.1. Flow Chart Preproses Jawaban dan Kunci Jawaban Esai .............. 24 Gambar. 3.2. Pengambilan Data ........................................................................... 25 Gambar. 3.3. Flow Chart Case Folding dan Tokenizing ...................................... 26 Gambar. 3.4. Flow Chart Filtering ....................................................................... 27 Gambar. 3.5. Flow Chart Stemming...................................................................... 28 Gambar. 3.6. Proses Utama Sistem ....................................................................... 28 Gambar. 3.7. Flow Chart K-grams ....................................................................... 29 Gambar. 3.8. Flow Chart Hashing ........................................................................ 30 Gambar. 3.9. Flow Chart String Matching ........................................................... 30 Gambar. 3.10. Diagram Konteks Sistem............................................................... 31 Gambar. 3.11. DFD Level 0 .................................................................................. 31 Gambar. 3.12. DFD Level 1 Proses 1 ................................................................... 32 Gambar. 3.13. DFD Level 1 Proses 2 ................................................................... 33 Gambar. 3.14. DFD Level 1 Proses 3 ................................................................... 33 Gambar. 3.15. DFD Level 1 Proses 4 ................................................................... 34 Gambar. 3.16. ERD Sistem ................................................................................... 34 Gambar. 3.17. Physical Diagram Sistem .............................................................. 35 Gambar. 3.18. Arsitektur Integrasi Sistem ............................................................ 36 Gambar. 3.19. Detail Arsitektur Integrasi Sistem ................................................. 36 Gambar. 3.20. Antar Muka Pilih Kuis .................................................................. 38 Gambar. 3.21. Antar Muka Set Kunci Jawaban .................................................... 39 Gambar. 3.22. Antar Muka Detail Kuis ................................................................ 39 Gambar. 3.23. Antar Muka Detail Answer Per Soal ............................................. 40 Gambar. 3.24. Antar Muka Detail Answer Per User ............................................ 40 Gambar. 3.25. Antar Muka Kamus Kata Dasar .................................................... 41
xii
Gambar. 3.26. Antar Muka Kamus Kata Hubung................................................. 41 Gambar. 3.27. Antar Muka Form Manajemen Kata Dasar ................................... 41 Gambar. 3.28. Antar Muka Form Manajemen Kata Hubung ............................... 42 Gambar. 4.1. Susunan Package Modul Essay Grading ........................................ 46 Gambar. 4.2. Menu Essay Grading ....................................................................... 47 Gambar. 4.3. Menu Kamus Kata Essay Grading .................................................. 48 Gambar. 4.4. Form Select Quiz To Grade............................................................. 49 Gambar. 4.5. Form Select Quiz To Set .................................................................. 49 Gambar. 4.6. Form Detail Kuis ............................................................................. 50 Gambar. 4.7. Form Set Kunci Jawaban................................................................. 50 Gambar. 4.8. Detail Jawaban Kuis per Soal.......................................................... 51 Gambar. 4.9. Detail Jawaban Kuis per User ......................................................... 51 Gambar. 4.10. Antar Muka Kamus Kata Dasar .................................................... 52 Gambar. 4.11. Antar Muka Kamus Kata Hubung................................................. 52 Gambar. 4.12. Antar Muka Form Manajemen Kata Dasar ................................... 53 Gambar. 4.13. Antar Muka Form Manajemen Kata Hubung ............................... 53 Gambar. 4.14. Fungsi Ajax Load Jawaban ........................................................... 54 Gambar. 4.15. Fungsi Tokenizing ......................................................................... 54 Gambar. 4.16. Fungsi Filtering ............................................................................. 55 Gambar. 4.17. Fungsi Stem ................................................................................... 56 Gambar. 4.18. Fungsi K-gram............................................................................... 56 Gambar. 4.19. Fungsi Hashing.............................................................................. 57 Gambar. 4.20. Fungsi Processing ......................................................................... 58 Gambar. 4.21. Fungsi Hitung Similaritas.............................................................. 58 Gambar. 4.22. Grafik Waktu Proses Soal 1 .......................................................... 78 Gambar. 4.23. Grafik Penilaian Soal 1 ................................................................. 78 Gambar. 4.24. Grafik Waktu Proses Jawaban Soal 2 ........................................... 79 Gambar. 4.25. Grafik Waktu Proses Jawaban Soal 3 ........................................... 79 Gambar. 4.25. Grafik Penilaian Jawaban Soal 2 ................................................... 79 Gambar. 4.27. Grafik Penilaian Jawaban Soal 3 ................................................... 80
xiii
DAFTAR TABEL Tabel. 3.1. Kebutuhan Fungsional User ................................................................ 19 Tabel. 3.2. Kebutuhan Non-Functional User ........................................................ 20 Tabel. 3.3. Kebutuhan Sistem ............................................................................... 21 Tabel. 3.4. Kebutuhan Interface ............................................................................ 23 Tabel. 3.5. Data Jawaban Esai .............................................................................. 44 Tabel. 3.6. Data Uji Jawaban Esai ........................................................................ 44 Tabel. 4.1. Static Testing Spesifikasi Sistem ........................................................ 59 Tabel. 4.2. Static Testing Premeditation Sistem ................................................... 60 Tabel. 4.3. Static Testing Repeatability Sistem .................................................... 61 Tabel. 4.4. Functional Testing dari Functional Requirement................................ 61 Tabel. 4.5. Testing dari Non-Functional Requirement ........................................ 62 Tabel. 4.6. User Navigation Testing .................................................................... 63 Tabel. 4.7. Tabel Uji Black Box Testing .............................................................. 65 Tabel. 4.8. Data Soal dan Kunci Jawaban Esai .................................................... 66 Tabel. 4.9. Data Jawaban Esai Soal 1 ................................................................... 67 Tabel. 4.10. Data Jawaban Esai Soal 2 ................................................................. 67 Tabel. 4.11. Data Jawaban Esai Soal 3 ................................................................. 68 Tabel. 4.12. Hasil Uji Jawaban Esai Soal 1 Stemming Arifin .............................. 68 Tabel. 4.13. Hasil Uji Jawaban Esai Soal 1 Stemming Nazief ............................. 69 Tabel. 4.14. Hasil Uji Jawaban Esai Soal 1 Stemming Porter .............................. 70 Tabel. 4.15. Hasil Uji Jawaban Esai Soal 2 Stemming Arifin .............................. 71 Tabel. 4.16. Hasil Uji Jawaban Esai Soal 2 Stemming Nazief ............................. 72 Tabel. 4.17. Hasil Uji Jawaban Esai Soal 2 Stemming Porter .............................. 73 Tabel. 4.18. Hasil Uji Jawaban Esai Soal 3 Stemming Arifin .............................. 74 Tabel. 4.19. Hasil Uji Jawaban Esai Soal 3 Stemming Nazief ............................. 75 Tabel. 4.20. Hasil Uji Jawaban Esai Soal 3 Stemming Porter .............................. 77 Tabel. 4.21. Rangkuman Hasil Pengujian Sistem ................................................. 80 Tabel. 4.22. Tabel Sampel Jawaban Esai Soal 2 ................................................... 82 Tabel. 4.23. Tabel Sampel Jawaban Esai Soal 3 ................................................... 82
xiv
DAFTAR LAMPIRAN Lampiran 1. Lampiran I Deskripsi Hasil Uji Fungsional 2. Lampiran II Pengujian Kebutuhan Non Fungsional 3. Lampiran III Pengujian User Interface 4. Lampiran IV Data Uji
xv
