USULAN PENELITIAN SISTEM PENILAIAN OTOMATIS PADA JAWABAN UJIAN BERBENTUK ESAI MENGGUNAKAN METODE RABIN KARPDiajukan Untuk Membuat Skripsi Program Sarjana (S-1) pada Jurusan Teknik Informatika Fakultas Sains dan Teknologi UIN Maliki Malang Oleh: David Indra Lesmana NIM. 07650117

1. 2. 3. 4.

JURUSAN TEKNIK INFORMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS ISLAM NEGERI MAULANA MALIK IBRAHIM MALANG 2011

1

1. JUDUL SISTEM PENILAIAN OTOMATIS PADA JAWABAN BERBENTUK ESAI MENGGUNAKAN METODE RABIN KARP 2. LATAR BELAKANG Seiring perkembangan teknologi informasi dan komputer, dunia pendidikan mengalami perubahan sistem pengajaran yang cukup signifikan. Beberapa institusi pendidikan mulai mengembangkan sistem e-learning dalam proses pengajarannya. E-learning merupakan suatu sistem dimana penyampaian materi pembelajaran, pelatihan atau program pendidikan menggunakan peralatan elektronik, termasuk di dalamnya adalah penggunaan komputer, atau peralatan peralatan elektronik (seperti telepon mobile) dalam tujuan memberikan materi pelatihan, pendidikan atau pembelajaran (Putri Ratna, dkk.2006). E-learning telah berkembang meluas di berbagai jenjang pendidikan, dari Sekolah Dasar sampai Perguruan Tinggi. Dalam konsep e-learning, pelaksanaan ujian dapat dilakukan secara online, mulai dari menjawab soal ujian hingga proses penilaian. Selama ini kebanyakan proses ujian dan penilaian dilaksanakan secara manual yaitu dengan membaca esai satu per satu. Para pengajar perlu menghabiskan banyak waktu untuk menilai jawaban ujian siswa mereka. Semakin banyak jumlah ujian yang dikoreksi, kualitas penilaian yang diberikan semakin menurun (Firdausiah, dkk. 2008). Penilaian adalah suatu proses untuk mengambil keputusan dengan menggunakan informasi yang diperoleh melalui pengukuran hasil belajar baik yang menggunakan instrumen tes maupun yang tidak. Penilaian dengan esei (essay grading) menjadi pilihan pengajar dalam mengevaluasi tingkat kemampuan dari siswanya walaupun kenyataannya tidak mudah memberikan penilaian yang objektif pada setiap siswa dalam mengevaluasi jawaban dari soal esei. Bentuk esei ini oleh banyak peneliti dianggap alat yang sangat ampuh untuk mengukur hasil pembelajaran, begitu juga untuk mengamati kemahiran berpikir tingkat tinggi seperti sintesis dan analisis. (Adhitia, dkk. 2009)

2

Dengan memanfaatkan metode untuk pencocokan string pada dokumen, dapat dikembangkan untuk merancang aplikasi penilaian otomatis pada jawaban berbentuk esai. Algoritma pencocokan string sendiri ada bermacam-macam, antara lain Boyer-Moore, Brute Force, Knuth-Morris-Pratt, Rabin-Karb, SmithWaterman dan lain-lain. Pada penelitian sebelumnya (Nugroho, 2011) dilakukan penelitian secara skematis bagaimana cara kerja algoritma Rabin-Karp mendeteksi plagiarisme pada suatu dokumen, dalam penelitian tersebut Nugroho menyatakan bahwa algoritma ini cocok untuk pencarian jamak (multiple pattern), Nugroho juga menjelaskan bahwa stemming juga sangat mempengaruhi pada akurasi nilai simmilarity. Sedangkan pada penelitian yang dilakukan oleh Jelita Asian, Huge E. Williams dan S.M.M. Tahaghoghi dengan judul Stemming Indonesia mengemukakan algoritma stemming yang mempunyai keakuratan paling baik adalah Nazief and Adriani. Pada penelitian ini akan dilakukan perancangan aplikasi dengan membandingkan kemiripan jawaban esai dengan kunci jawaban yang tersimpan dalam sistem. Dengan mengetahui persentase kemiripan kedua teks jawaban tersebut dapat dijadikan acuan untuk melakukan penilaian. Algoritma yang digunakan dalam penelitian ini adalah Rabin-Karb algorithm. Algoritma ini digunakan karena sangat efektif untuk pencarian lebih dari satu kata (multi pattern). Selain itu juga disisipkan algoritma stemming Nazief and Adriani untuk memperoleh tingkat akurasi yang baik pada nilai similarity. Karena hal-hal tersebut penulis mengusulkan Sistem Penilaian Otomatis Pada Jawaban Ujian Berbentuk Esai Menggunakan Metode Rabin Karp. Sistem ini digunakan untuk menilai ujian dalam bentuk esai atau berbasis teks. Dengan sistem ini, diharapkan mampu mengatasi masalah proses penilaian ujian siswa di institusi pendidikan.

3

3. RUMUSAN MASALAH Adapun rumusan masalah dari penelitian ini adalah bagaimana merancang dan membangun sistem penilaian pada jawaban ujian berbentuk esai menggunakan metode rabin karp. 4. BATASAN MASALAH Adapun batasan masalah dalam penelitian ini adalah: 1. Esai yang dinilai dalam sistem ini menggunakan bahasa Indonesia. 2. Tipe jawaban esai yang dinilai dalam sistem ini bersifat definitif . 3. Hanya menguji data berupa text, tidak menguji data berupa gambar 4. Sistem tidak memperhatikan kesalahan ejaan 5. Data yang diuji menggunakan bahasa Indonesia 6. K-gram yang digunakan 1 sampai dengan 5 7. Sistem tidak memperhatikan sinonim 8. Sistem tidak membahas kata-kata bermakna negatif (seperti bukan, tidak) 9. Text input diakuisisi dari file text 5. TUJUAN DAN MANFAAT PENELITIAN a. Tujuan Penelitian Adapun tujuan dari penelitian ini adalah:1. Membuat sistem penilaian otomatis pada jawaban ujian berbentuk esai

(Automatic Essay Grading)2. Dapat mengimplemetasikan metode rabin karp dalam sistem penilaian

otomatis pada jawaban ujian berbentuk esai (Automatic Essay Grading)3. Untuk menetukan penilaian dalam sistem penilaian otomatis pada jawaban

ujian berbentuk esai (Automatic Essay Grading) b. Manfaat Penelitian Adapun manfaat dari penelitian ini adalah terbentuknya suatu implemetasi metode Rabin Karp dalam sistem penilaian otomatis pada jawaban ujian berbentuk esai (Automatic Essay Grading), sehingga Membantu dosen dalam memberikan penilaian ujian mahasiswa secara objektif.

4

6. TINJAUAN PUSTAKAa. Tes Esai

Tes esai adalah suatu bentuk tes yang terdiri dari pertanyaan atau suruhan yang menghendaki jawaban yang berupa uraian-uraian yang relatif panjang. Tes dirancang untuk mengukur hasil belajar di mana unsur-unsur yang diperlukan untuk menjawab soal dicari, diciptakan dan disusun sendiri oleh pengambil tes. Peserta tes harus menyusun sendiri kata-kata dan kalimat-kalimat dalam merumuskan jawabannya. Butir soal mengandung pertanyaan atau tugas yang jawaban atau pengerjaan soal tersebut harus dilakukan dengan cara mengekspresikan pikiran peserta tes, constructed-response tests are those that call for the examinee to produce something. Bentuk-bentuk pertanyaan atau suruhan meminta pada murid-murid untuk menjelaskan, membandingkan, menginterpretasikan dan mencari perbedaan. Semua bentuk pertanyaan tersebut mengharapkan agar murid-murid menunjukkan pengertian mereka terhadap materi yang dipelajari. Tes esai digunakan untuk mengatasi kelemahan daya ukur soal objektif yang terbatas pada hasil belajar rendah. Soal tes bentuk ini cocok untuk mengukur hasil belajar yang level kognisinya lebih dari sekedar memanggil informasi, karena hasil belajar yang diukur bersifat kompleks dan sangat mementingkan kemampuan menghasilkan, memadukan dan menyatakan gagasan. Soal uraian (essay) berbeda dengan soal objektif dalam kebenarannya yang bertingkat. Jawaban tidak dinilai mulai dari 100% benar dan 100% salah. Kebenaran bertingkat tergantung tingkat kesesuaian jawaban siswa dengan jawaban yang dikehendaki yang dituangkan dalam kunci. Jawaban mungkin mengarah kepada jawaban yang tidak tunggal (divergence). Kebenaran yang dicapai bisa 0%, 20%, 30%, 50%, 70%, atau 100% tergantung ketepatan jawabannya. Di banding dengan tes objektif, soal esai mempunyai beberapa keunggulan. Pertama, kekuatan soal untuk mengukur hasil belajar yang kompleks dan melibatkan level kognitif yang tinggi. Kedua, memberi kesempatan pada anak untuk menyusun jawaban sesuai dengan jalan pikirannya sendiri. Kecakapan ini

5

sangat penting dalam kehidupan masyarakat karena individu dalam masyarakat tidak hanya mengadakan pilihan terhadap alternatif-alternatif tapi harus menggunakan alternatif lain yang lebih berguna. (Susanti, 2008) Meski soal esai sangat berguna, namun memiliki beberapa kelemahan. Pertama, terdapat subjektivitas dalam penilaiannya karena penilai yang berbeda atau situasi yang berbeda. Dua atau lebih penilai memberikan penilaian terhadap jawaban yang sama atau seorang penilai menilai sebuah jawaban pada situasi yang berbeda sangat mungkin menghasilkan nilai yang berbeda. Kedua, tes esai menghendaki jawaban yang panjang, sehingga tidak memungkinkan ditulis butir tes dalam jumlah banyak. Akibatnya, soal tidak representatif dalam mengukur kemampuan yang diharapkan. Ketiga, penggunaan soal esai membutuhkan waktu koreksi yang lama dalam menentukan nilai. b. Text Mining Text mining adalah salah satu bidang khusus dari data mining. Sesuai dengan buku The Text Mining Handbook, Text Mining dapat didefinisikan sebagai suatu proses menggali informasi dimana seorang user berinteraksi dengan sekumpulan dokumen menggunakan tools analisis yang merupakan komponen-komponen dari data mining. Tujuan dari text mining adalah untuk mendapatkan inormasi yang bergunadari sekumpulan dokumen. Sumber data yang digunakan pada text mining adalah sekumpulan text yang memiliki format yang tidak terstruktur atau minimal semi struktur. Teks yang diproses oleh text mining, pada umumnya memiliki beberapa karakteristik diantaranya memiliki dimesi yang tinggi, terdapat noise pada data, dan terdapat struktur teks yang tidak baik. Cara yang digunakan dalam mempelajari suatu text adalah terlebih dahulu menentukan fitur-fitur yang mewakili setiap kata, namun sebelum itu perlu dilakukan tahap pre-processing yang dilakukan secara umum dalam text mining pada dokumen, yaitu case foding, tokenizing, filtering, dan stemming.

6

Case Foding Tokenizing Filtering Stemming

Gambar 1. Tahap Preprocessing

Case Foding dan Tokenizing Case folding adalah mengubah semua huruf dalam dokumen menjadi huruf kecil. Hanya huruf a sampai dengan z diterima. Karakter selain huruf dihilangkan dan dianggap delimiter . Tahap tokenizing / parsing adalah tahap pemotongan string input berdasarkan tiap kata yang menyusunnya.

Gambar 2. Contoh Case Foding dan Tokenizing

Filtering Filtering adalah tahap mengambil kata-kata penting dari hasil token. Bisa menggunakan algoritma stoplist (membuang kata yang kurang penting) atau wordlist (menyimpan kata penting). Stoplist / stopword adalah kata-kata yang tidak deskriptif yang dapat dibuang dalam pendekatan bag-of-words. Contoh stopwords adalah yang, di, dari, dan dan seterusnya.

7

Gambar 3. Contoh Filtering

Stemming Stemming adalah proses pencarian bentuk dasar suatu kalimat dengan cara menghilangkan imbuhannya. Stemming merupakan suatu proses yang terdapat dalam sistem IR yang mentransformasi kata-kata yang terdapat dalam suatu dokumen ke kata-kata akarnya (root word) dengan menggunakan aturan-aturan tertentu. Stemming sangat penting dalam mendukung efektivitas pencarian informasi dalam bahasa Indonesia, penerjemahan dokumen, dan pencarian di dalam web. Imbuhan bahasa Indonesia lebih kompleks dari pada bahasa inggris karena di dalam bahasa Indonesia terdapat awalan (prefiks), infiks (sisispan), akhiran(sufiks), konfiks (gabungan prefiks dan sufiks), serta gabungan imbuhan. Sehingga stemming bahasa Indonesia harus mampu menemukan akar kata sesuai dengan aturan baku bahasa Indonesia. Stemming digunakan untuk mengganti bentuk dari suatu kata menjadi kata dasar dari kata tersebut yang sesuai dengan struktur morfologi Bahasa Indonesia yang baik dan benar. Sehingga imbuhan-imbuhan yang melekat pada suatu kata harus dihilangkan untuk mengubah bentuk kata tersebut menjadi bentuk kata dasarnya.

8

Gambar 4. Contoh Stemming

c.

String Matching (Pencocokan Kata) String matching atau pencocokan string adalah suatu metode yang digunakan

untuk menemukan suatu keakuratan/hasil dari satu atau beberapa pola teks yang diberikan. String matching merupakan pokok bahasan yang penting dalam ilmu komputer karena teks merupakan adalah bentuk utama dari pertukaran informasi antar manusia, misalnya pada literatur, karya ilmiah, halaman web dsb. (HulbertHelger,2007) String matching digunakan dalam lingkup yang bermacammacam, misalnya pada pencarian dokumen, pencocokan DNA sequences yang direpresentasikan dalam bentuk string dan juga string matching dapat dimanfaatkan untk mendeteksi adanya plagiarisme dalam karya seseorang. String-matching fokus pada pencarian satu, atau lebih umum, semua kehadiran sebuah kata (lebih umum disebut pattern) dalam sebuah teks. Semua algoritma yang akan dibahas mengeluarkan semua kehadiran pola dalam teks. Pola dinotasikan sebagai x = x[0..m-1]; m adalah panjangnya. Teks dinotasikan sebagai y = y[0..n-1]; n adalah panjangnya. Kedua string dibentuk dari set karakter yang disebut alphabet dinotasikan dengan ukuran . (Atmopawiro, 2006) Hash Hashing adalah suatu cara untuk mentransformasi sebuah string menjadi suatu nilai yang unik dengan panjang tertentu (fixed-length) yang berfungsi sebagai

9

penanda string tersebut. Fungsi untuk menghasilkan nilai ini disebut fungsi hash, sedangkan nilai yang dihasilkan disebut nilai hash. Algoritma Rabin-Karp didasarkan pada fakta jika dua buah string sama maka harga hash value -nya pasti sama. Contoh sederhana hashing adalah: Firdaus, Hari Munir, Rinaldi Rabin, Michael Karp, Richard 7864 9802 1990 8822

Gambar 5. Contoh Hashing

Contoh di atas adalah pengunaan hashing dalam pencarian pada database. Apabila tidak di-hash, pencarian akan dilakukan karakter per karakter pada namanama yang panjangnya bervariasi dan ada 26 kemungkinan pada setiap karakter. Namun pencarian akan menjadi lebih efisien setelah di-hash karena hanya akan membandingkan empat digit angka dengan cuma 10 kemungkinan setiap angka. Nilai hash pada umumnya digambarkan sebagai fingerprint yaitu suatu string pendek yang terdiri atas huruf dan angka yang terlihat acak (data biner yang ditulis dalam heksadesimal). (Firdaus,2008) K-Gram Kgrams adalah rangkaian terms dengan panjang K. Kebanyakan yang digunakan sebagai terms adalah kata. K-gram merupakan sebuah metode yang diaplikasikan untuk pembangkitan kata atau karakter. Metode k-grams ini digunakan untuk mengambil potongan-potongan karakter huruf sejumlah k dari sebuah kata yang secara kontinuitas dibaca dari teks sumber hingga akhir dari dokumen. Berikut ini adalah contoh k-grams dengan k=5 :

Text: A do run run run, a do run run Kemudian dilakukan penghilangan spasi : Adorunrunrunadorunrun Sehingga dihasilkan rangkaian 5-grams yang diturunkan dari text :

10

adoru dorun orunr runru unrun nrunr runru unrun nruna runad unado nador adoru dorun orunr runru unrun (Kurniawati and Wicaksana, 2008) Metode Rabin Karp Algoritma Karp-Rabin diciptakan oleh Michael O. Rabin dan Richard M. Karp pada tahun 1987 yang menggunakan fungsi hashing untuk menemukan pattern di dalam string teks. Dalam buku String Search Algorithm, dijelaskan bahwa metode ini sebuah metode alternatif untuk menyelesaikan masalah string matching yang menggunakan fungsi hash. Metode ini melakukan suatu proses untuk mencari kesamaan pada sebuah pattern dengan sebuah text string. Karakteristik Algoritma Rabin-Karp : (Fernando, 2009) Menggunakan sebuah fungsi hashing Fase prepocessing menggunakan kompleksitas waktu O(m) Untuk fase pencarian kompleksitasnya : O(mn) Waktu yang diperlukan O(n+m)

Fungsi hashing menyediakan metode sederhana untuk menghindari perbandingan jumlah karakter yang quadratik di dalam banyak kasus atau situasi. Daripada melakukan pemeriksaan terhadap setiap posisi dari teks ketika terjadi pencocokan pola, akan lebih baik efisien untuk melakukan 18 pemeriksaan hanya jika teks yang sedang proses memiliki kemiripan seperti pada pattern. Untuk melakukan pengecekan kemiripan antara dua kata ini digunakan fungsi hash. (Fernando,2009) Dengan fungsi hash, berarti urutan m karakter dianggap sebagai sebuah bilangan dalam suatu basis b. Urutan teks T[i .. i + m-1] dapat dianggap sebuah bilangan x(i) = T[i] b m-1 + T[i+1] b m-2 + + T[i + m-1] yang berikutnya T[i+1 .. i+m] x(i+1) = T[i+1] b m-1 + T[i+2] b m-2 + + T[i+m] [2] Jika panjang pola m besar, maka bilangan yang didapat dari fungsi hash akan terlalu besar maka perlu hasilnya di mod dengan suatu angka q. Hash = T[i] b m-1 + T[i+1] b m-2 + + T[i + m-1] mod q [3] [1] Dengan mengetahui x(i) dapat dihitung x(i+1) untuk urutan m karakter

11

Algoritma Rabin-Karp adalah algoritma pencocokan string yang menggunakan fungsi hash sebgai pembanding antara string yang dicari (m) dengan substring pada teks (n). Apabila hash value keduanya sama maka akan dilakukan perbandingan sekali lagi terhadap karakter-karakternya. Apabila hasil keduanya tidak sama, maka substring akan bergeser ke kanan. Pergeseran dilakukan sebanyak (n-m) kali. Perhitungan nilai hash yang efisien pada saat pergeseran akan mempengaruhi performa dari algoritma ini. Cara kerja dari algoritma Rabin-Karp dapat dilihat pada gambar 6 dan gambar 7. (Firdaus, 2008)

Gambar 6. Algoritma Rabin Karp

Berikut ini adalah ilustrasi cara kerja algoritma Rabin-Karp: Diberikan masukan cab dan text aabbcaba. Fungsi hash yang dipakai misalnya akan menambahkan nilai keterurutan setiap huruf dalam alfabet (a = 1, b = 2, dst.) dan melakukan modulo dengan 3. Didapatkan nilai hash cab adalah 0 dan tiga karakter pada text yaitu aab adalah 1. Dapat dilihat pada gambar 7 :

12

Gambar 7. Pengecekan Tiga Karakter Pertama

Hasil perbandingan ternyata tidak sama, maka substring pada teks akan begeser satu karakter ke kanan. Algoritma tidak menghitung kembali nilai hash substring. Disinilah dilakukan apa yang disebut rolling hash yaitu mengurangi nilai karakter yang keluar dan menambahkan nilai karakter yang masuk sehingga didapatkan kompleksitas waktu yang relatif konstan pada setiap kali pergeseran. Setelah pergeseran, didapatkan nilai hash dari fingerprint abb (abb = aab - a + b) menjadi dua (2 = 1 - 1 + 2). Proses pergeseran dan pengecekan dapat dilihat pada gambar 8 dan 9:

Gambar 8. Pengecekan Terhadap Substring Berikutnya

Gambar 9. Pengecekan Pattern c a b dengan Substring a b b

13

Hasil perbandingan juga tidak sama, maka dilakukan pergeseran. Begitu pula dengan perbandingan ketiga. Pada perbandingan keempat, didapatkan nilai hash yang sama. Gambar 10 pengecekan terhadap susbstring:

Gambar 10. Perbandingan Pattern dengan Substring Berikutnya

Karena nilai hash sama, maka dilakukan perbandingan string karakter perkarakter antara bca dan cab didapatkan hasil bahwa kedua string tidak sama. Seperti pada gambar 11 :

Gambar 11. Perbandingan Pattern yang mempunyai nilai hash yang sama dengan Substring

Maka, kembali substring bergeser ke kanan. Pada perbandingan yang kelima, kedua nilai hash dan karakter pembentuk string sesuai, sehingga solusi ditemukan. Seperti pada gambar 12 :

Gambar 12. Hasil Pencarian Pattern ditemukan

14

Dari hasil perhitungan, kompleksitas waktu yang dibutuhkan adalah O(m+n) dengan m adalah panjang string masukan dan n adalah jumlah looping yang dilakukan untuk menemukan solusi. Hasil ini jauh lebih efisien daripada kompleksitas waktu yang didapat menggunakan algoritma Brute-Force yaitu O(mn). Algoritma Rabin-Karp ternyata masih kurang optimal dan cepat pada pencarian pola string tunggal (single pattern search) apabila dibandingkan dengan algoritma Boyer-Moore ataupun algoritma Knuth-Morris-Pratt, tetapi menjadi pilihan bila digunakan untuk mencari string dengan pola yang banyak (multiple pattern search). Bila algoritma lain dapat mencari string berpola tunggal dalam waktu O(n), jika digunakan untuk mencari pola sebanyak k, maka akan membutuhkan waktu selama O(nk). Sedangkan varian Rabin-Karp di atas lebih efisien karena diharapkan dapat mencari dengan kompleksitas waktu O(n+k). (Firdaus, 2008)

Gambar 13. Algoritma Rabin Karp Untuk Multipattern

15

Menghitung Nilai Inti dari pendekatan k-grams dibagi menjadi dua tahap. Tahap pertama, membagi kata menjadi k-grams. Kedua, mengelompokkan hasil terms dari kgrams yang sama. Kemudian untuk menghitung similarity dari kumpulan kata. Nilai similarity dapat dihitung dengan menggunakan :

Dimana S adalah nilai similarity, A dan B adalah jumlah dari kumpulan K-grams dalam teks 1 dan teks 2. C adalah jumlah dari Kgrams yang sama dari teks yang dibandingkan. Berikut ini adalah contoh penghitungan nilai similarity 3 kata dengan K=2 (bigrams). No 01 02 03 04 05 Jawaban Sukarno (6) Sistem (5) Rancangan (8) Penelitian (9) University (9) Kunci Jawaban Bobot Soekarno (7) System (5) Desain (5) Penelitian (9) Universitas (10) Total Nilai Soal 10 20 20 25 25 K-Gram Sama 4 3 0 9 8 Perhitungan (2*4/6+7)*10 = 6 (2*3/5+5)*20 = 12 0 (2*9/9+9)*25 = 25 (2*8/9+10)*25 = 21 64

7. METODE PENELITIANa. Persiapan Proposal

Pada tahap ini peneliti melakukan persiapan dan penyusunan proposal penelitian untuk tugas akhir. b. Lokasi dan Waktu Penelitian Penelitian ini akan dilaksanakan di Universitas Islam Negeri (UIN) Maulana Malik Ibrahim Malang tempat peneliti berdomisili. Dengan melakukan studi literatur dan perancangan sistem. Waktu pelaksanaan penelitian dimulai dari bulan Oktober 2011. c. Sumber Data Sumber data dalam penelitian ini yaitu:

16

1. Sumber data primer yaitu soal-soal dan jawaban yang diambil dari materi

matakuliah di jurusan teknik informatika 2. Sumber data sekunder yaitu semua data yang nantinya menjadi data pendukung dalam pembuatan sistem ini.d. Perencanaan dan Pembuatan Sistem i. Desain Sistem

Didalam sistem penilaian esai otomatis ini terdapat dua user diantaranya : 1. Pengajar Dalam sistem ini pengajar akan berperan untuk memasukkan pertanyaan dan kunci jawaban kedalam database yang nantinya akan diproses oleh sistem. 2. Mahasiswa Dalam sistem ini mahasiswa akan menjawab pertanyaan yang nantinya jawaban tersebut akan dicocokkan dengan kunci jawaban yang tersimpan dalam database sehingga sistem bisa melakukan proses penilaian otomatis.

17

Mahasiswa Input

Dosen

Jawaban Mahasiswa (text)

Kunci Jawaban Dosen (text)

Databas e

Databas e

Preprocessing

Pencocokan kata dg Rabin Karp

Preprocessing

Penilaian

Nilai Akhir

Output

Gambar 14. Desain Sistem

Sistem aplikasi ini berjalan dengan mengolah masukan user. Setelah sistem mendapatkan input dari user, sistem akan masuk ke tahap preprocessing. Pada tahap ini akan dilakukan beberapa proses, yaitu case foding, tokenizing, filtering (penghilangan kata yang tidak penting) dan stemming (pemotongan kata atau term menjadi kata dasar). Case folding adalah mengubah semua huruf dalam dokumen menjadi huruf kecil. Hanya huruf a sampai dengan z diterima. Karakter selain huruf

18

dihilangkan dan dianggap delimiter . Tahap tokenizing / parsing adalah tahap pemotongan string input berdasarkan tiap kata yang menyusunnya. Proses filtering adalah proses penghilangan kata-kata dan tanda baca seperti yang, di, dari, dan, koma dan sebagainya. Proses Filtering yang digunakan dalam sistem ini adalah menggunakan algoritma stopword dimana tiap kata (term) akan dicek apakah kata tersebut ada dalam daftar stopword. Jika terdapat dalam stopword, kata tersebut akan dihilangkan sehingga setelah dilakukan proses filtering akan didapatkan daftar kata penting. Setelah proses filtering nantinya akan disisipkan proses stemming. Proses stemming adalah suatu proses pemotongan terhadap imbuhan sperti prefix (awalan) dan suffiks (akhiran) dan confix (awalan dan akhiran) sehingga akan didapatkan kata dasarnya.Start Jawaban Mahasiswa

Case Foding Tokenizing

Filtering

Stemming

Kata Dasar

End

Gambar 15. Preprocessing

19

Setelah melalui tahap preprocessing, maka langkah selanjutnya adalah melakukan parsing k-gram dan akan menghasilkan substring k-gram. Setelah melalui proses diatas, maka akan diteruskan untuk proses hashing sehingga akan menghasilkan hash value yang akan digunakan untuk proses string matching sehingga akan diketahui berapa k-gram yang sama. Dalam proses penilaian, proses yang terjadi adalah proses perhitungan nilai similarity. Inti dari pendekatan k-grams dibagi menjadi dua tahap. Tahap pertama, membagi kata menjadi k-grams. Kedua, mengelompokkan hasil terms dari k-grams yang sama. Kemudian untuk menghitung similarity dari kumpulan kata.Start Kata Dasar

Parsing k-gram Substring k-gram Hashing

Hash Value

String matching Penilaian

Nilai

EndGambar 16. Processing

20

ii. Pembuatan Sistem Dalam tahap ini dilakukan perancangan aplikasi yang terdiri dari perancangan proses-proses utama dan desain aplikasi yang berupa tampilan antarmuka. e. Penulisan dan Pembuatan Laporan Pada tahap ini dilakukan penulisan dan pembuatan laporan dari hasil penelitian yang dilakukan selama proses pembuatan aplikasi untuk dokumentasi tugas akhir. 8. JADWAL PENELITIAN No. 1 2 3 4 5 6 Jenis Kegiatan Persiapan proposal Pengumpulan data Perancangan sistem Implementasi sistem Ujicoba dan Pengembangan Penulisan Laporan Bulan ke I II III IV V

9. DAFTAR PUSTAKA Anak Agung Putri Ratna, M Salman, Bagio Budiardjo, Djoko Hartando, Seinosuke Narita. 2006. SIMPLE: Sistem Penilaian Esei Otomatis Berbasis WEB Dengan Metoda Latent Semantic Analysis Yang Digunakan Pada Bahasa Indonesia Dengan Penambahan Kata Bobot. Departemen Elektro Fakultas Teknik Universitas Indonesia. http://journal.eng.ui.ac.id/data/2._AAP_Ratna_ok_.pdf (diakses 25 September 2011) 2) Andi Besse Firdausiah, Daniel Oranova S, Umi laili Yuhana, Toshihiro Kita. 2008. Sistem Penilaian Otomatis Jawaban Essay Menggunakan Ontologi Pada Moodle. Jurusan Teknik Informatika Institut Teknologi 10 November Surabaya. http:// telkomnika.ee.uad.ac.id/n9/files/Vol.6No.3Des08/6.3.12.08.03.pdf (diakses 25 September 2011)1)

21

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

13)

14)

Rama Adhitia, Ayu Purwarianti. 2009. Penilaian Esai Jawaban Bahasa Indonesia Menggunakan Metode Svm - Lsa Dengan Fitur Generik. Program Studi Teknik Informatika Institut Teknologi Bandung. http://jsi.cs.ui.ac.id/index.php/jsi/article/download/45/30.pdf (diakses 25 September 2011) Putra, Dian Perdhana. 2007. Perancangan Algoritma Pencocokan String Menggunakan Fungsi Hash Untuk Pendeteksian Plagiarisme. Program Studi Teknik Informatika Institut Teknologi Bandung. http://www.informatika.org/~rinaldi/.../Makalah2_IF3058_2010_016.pdf (diakses 28 September 2011) Jelita Asian, Huge E. Williams dan S.M.M. Tahaghoghi. 2007. Stemming Indonesia. Journal School of Computer Science and Information Technology. RMIT University, Australia. Atmopawiro, Alsasian. 2006. Pengkajian Dan Analisis Tiga Algoritma Efisien Rabin-Karp, Knuth-Morris-Pratt, Dan Boyer-Moore Dalam Pencarian Pola Dalam Suatu Teks . Program Studi Teknik Informatika, Institut Teknologi Bandung. http://www.informatika.org/~rinaldi/Matdis/2006.../Makalah0607-94.pdf (diakses 28 September 2011) Firdaus, Hari Bagus. 2008. Deteksi Plagiat Dokumen Menggunakan Algoritma Rabin-Karp. Program Studi Teknik Informatika Sekolah Teknik Elektro dan Informatika, Institut Teknologi Bandung (ITB). Bandung. http://www.informatika.org/~rinaldi/Stmik/.../MakalahIF2251-2008-076 (diakses pada 01 Oktober 2011) Nugroho, Eko. 2011. Perancangan Sistem Deteksi Plagiarisme Dokumen Teks Dengan Menggunakan Algoritma Rabin Karp. Program Studi ilmu Komputer Jurusan Matematika Universitas Brawijaya. Fernando, Hary. 2009. Perbandingan dan Pengujian Beberapa Algoritma Pencocokan String. Program Studi Teknik Informatika, Institut Teknologi Bandung (ITB). Bandung. http://www.informatika.org/~rinaldi/Stmik/.../MakalahIF3051-2009006.pdf (diakses 12 Oktober 2011) Kosinov, Serhiy. 2002. Evaluation of N-Grams Conflation Approach in Text-Based Information Retrieval . University of Alberta. Canada http://citeseerx.ist.psu.edu/.../download?doi=10.1.1.2.3145.pdf (diakses 12 Oktober 2011) Ronen Feldman dan James Sanger. 2007. The Text Mining Handbook : Advanced Approaches in Analyzing Unstructured Data. Cambridge : Cambridge University Press. Sholom M Weiss, Nitin Indurkhya, Tong Zhang dan Fred J Damerau. 2005. Text Mining Predictive Methods for Analyzing Unstructured Information. New york : Springer. A Stephen , Graham. 2000. String Searching Algorithms. Singapore : World Scientific. Susanti, Rini. 2008. Bentuk Tes dan Tingkah laku.

22

http://suyonoum08.wordpress.com/2008/02/09/bentuk-tes-dan-tingkahlaku-belajar/ (diakses 25 Oktober 2011)

23