SOURCE DETECTION PADA KASUS PLAGIARISME DOKUMEN BERDASARKAN WORDS PHRASING DENGAN MODEL RUANG VEKTOR
TUGAS AKHIR Diajukan Sebagai Salah Satu Syarat Untuk Memperoleh Gelar Sarjana Teknik Pada Jurusan Teknik Informatika
Oleh : AGUNG SUCIPTO 11051100379
FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS ISLAM NEGERI SULTAN SYARIF KASIM RIAU PEKANBARU 2014
ii
iii
SOURCE DETECTION PADA KASUS PLAGIARISME DOKUMEN BERDASARKAN WORDS PHRASING DENGAN MODEL RUANG VEKTOR AGUNG SUCIPTO 11051100379
Tanggal Sidang: 17 Februari 2014 Periode Wisuda : Juni 2014
Jurusan Teknik Informatika Fakultas Sains dan Teknologi Universitas Islam Negeri Sultan Syarif Kasim Riau
ABSTRAK Plagiarisme merupakan sebuah tindakan penggunaan dan mengutip sebagian isi karya tulisan orang lain tanpa mencantumkan sumber dan kemudian diakui sebagai miliknya sendiri. Namun pendeteksian plagiarisme yang telah dikembangkan masih melakukan pendeteksian 1:1 dan tidak dapat menemukan sumber dari dokumen. Penelitian ini menggabungkan antara pendeteksian plagiarisme dan mesin pencarian dengan model ruang vektor, ini bertujuan melakukan pendeteksian plagiarisme terhadap banyak dokumen. Konsep pendeteksian ini, yaitu melakukan pembuatan query terhadap isi dokumen dengan menggunakan word phrasing berbentuk triword, quadword dan pentaword dengan menggunakan stemming algoritma Nazief Adriani dan tanpa stemming serta melakukan pemilihan frekuensi kemunculan kata tertinggi, terendah dan tengah yang akan digunakan pada pencarian model ruang vektor, lalu mengukur kemiripan antara dokumen input terhadap dokumen yang telah dihasilkan oleh pencarian menggunakan algoritma biword winnowing. Pengujian akan dilakukan sebanyak lima kali dengan delapan belas konfigurasi pembuatan query berdasarkan kombinasi words phrasing. Kesimpulan Dari beberapa pengujian pembuatan query berdasarkan words phrasing dapat menemukan dokumen yang memiliki kesamaan antara dokumen uji dan dokumen yang ada pada corpus serta dapat menunjukkan persamaan kutipan antara dua dokumen. Selain itu tahap pengujian mengasumsikan pembuatan query berbentuk triword tanpa stemming dan pemilihan frekuensi kemunculan kata tertinggi dapat menghasilkan pencarian yang memiliki rata-rata nilai jaccard coefficient sebesar 15.66% dan stabil disetiap pengujiannya. Kata kunci: Algoritma, Biword Winnowing, Jaccard Coefficient, Model Ruang Vektor, Plagiarisme, Query, Words Phrasing.
vii
SOURCE DETECTION OF PLAGIARISM CASE DOCUMENT BASED ON WORDS PHRASING BY VECTOR SPACE MODEL AGUNG SUCIPTO 11051100379 Final Exam Date: February 17th, 2014 Graduation Ceremony Period: June 2014
Informatics Engineering Department Faculty of Science and Technology State Islamic University of Sultan Syarif Kasim Riau
ABSTRACT Plagiarism is an action of using or quoting some content of others’ papers without publishing the source and then recognized as his own. However, plagiarism detector that has been developed is still using 1:1 detection. It still can not find the source of document. This study combines the detection of plagiarism and search engine with the vector space model, it aims to detect plagiarism against a lot of documents. This detection concept, namely the conduct of making queries against the contents of document by using the word phrasing shaped triword, quadword and pentaword by using stemming Nazief Adriani alogarithm and without stemming and elect the highest frequency of the word occurrence, the lowest and the middle which will be used in the vector space model search, then measure the similarity between the input document to the document that has been produced by algorithm biword Winnowing search. Tests will be performed five times with eighteen query making configuration based on words phrasing combination. Conclusion of some query making tests based on words phrasing can find documents that have similarity between the test document and the documents in the corpus as well as to show the similarities of quotes between the two documents. Besides testing phase that assumes queries making shaped triword without stemming and selecting the highest frequency of the word occurrence can result a search that has an average value of Jaccard coefficient of 15.66% and stable in every test.
Key Words: Algorithm, Biword Winnowing, Jaccard Coefficient, Plagiarism, Query, Vector Space Model, Words Phrasing.
viii
KATA PENGANTAR
Alhamdulillaahi Robbil’alamin, penulis bersyukur ke-hadirat Allah SWT, karena atas segala limpahan rahmat dan karunia-Nya yang diberikan sehingga penulis dapat menyelesaikan penelitian dan penulisan laporan tugas akhir ini. Allahumma sholli’ala Muhammad wa’ala ali sayyidina Muhammad, yang tidak lupa penulis haturkan juga untuk Rosul Allah, Muhammad SAW. Laporan tugas akhir ini merupakan salah satu prasyarat untuk memenuhi persyaratan akademis dalam rangka meraih gelar kesarjanaan di Jurusan Teknik Informatika, Fakultas Sains dan Teknologi, Universitas Islam Negeri Sultan Syarif Kasim Riau (UIN SUSKA Riau). Selama menyelesaikan tugas akhir ini, penulis telah banyak mendapatkan bantuan, bimbingan, dan petunjuk dari banyak pihak baik secara langsung maupun tidak langsung. Untuk itu dalam kesempatan ini penulis ingin mengucapkan terimakasih yang sebesar-besarnya kepada: 1. Ayahku Johan dan Ibuku Almh. Sujinah yang menjadi sumber semangat penulis, atas segenap do’a yang tiada hentinya dan dukungan mereka selama masa Tugas Akhir ini. 2. Abangku Agus Susilo dan Agus Triono beserta kakaku Nur Linda, Nur Ratnawati dan Sri Handayani yang selalu memberikan semangat dan motivasi disaat penulis lelah dan hilang arah. 3. Prof. Dr. H. M. Nazir, selaku Rektor Universitas Islam Negeri Sultan Syarif Kasim Riau. 4. Dra. Yenita Morena, M.Si, selaku Dekan Fakultas Sains dan Teknologi Universitas Islam Negeri Sultan Syarif Kasim Riau. 5. Elin Haerani, ST, M.Kom, selaku Ketua Jurusan Teknik Informatika, Fakultas Sains dan Teknologi. 6. Surya Agustian, ST, M.Kom, selaku dosen pembimbing tugas akhir. Terimakasih pak untuk waktu yang selalu bapak luangkan untuk penulis, ilmu, semangat, dan motivasinya yang luar biasa.
ix
7. M. Safrizal,ST.,M.Sc, selaku dosen penguji 1 yang banyak membantu dan memberi masukan penulis dalam penyempurnaan laporan tugas akhir ini. 8. Teddie D.,ST.,MTI, selaku dosen penguji 2 yang banyak membantu dan memberi masukan penulis dalam penyempurnaan laporan tugas akhir ini. 9. Muhammad Affandes, MT, sebagai koordinator tugas akhir yang telah memberi masukan-masukan untuk penyelesaian tugas akhir ini, dan sangat sabar membantu penulis dalam mempersiapkan semua kebutuhan penulis dalam penyelesaian Tugas Akhir ini. 10. Seluruh staff dan karyawan Fakultas Sains & Teknologi Khususnya Jurusan Teknik Informatika. 11. Desy Arjuna, seseorang yang sangat istimewa yang dengan ikhlas selalu menemai dan memberi semangat kepada penulis. 12. Sahabatku Penghuni SHP 141 Eka, Harja, Tuah, Aan, Firman, Rizan, Fahrul, Andika dan Irwan. You are the best. 13. Teman-teman karib satu angkatan 2010 khususnya kelas B yang tidak dapat disebutkan satu persatu, terima kasih atas kebersamaannya. 14. Teman-teman karib satu angkatan 2010 Teknik Informatika. 15. Seluruh pihak yang turut membantu penulis dalam bentuk apapun.
Akhirnya, penulis menyadari dalam penulisan laporan ini masih terdapat kekurangan. Oleh karena itu, saran dan kritik sangat penulis harapkan untuk kemajuan penulis secara pribadi. Terimakasih. Pekanbaru, 14 Februari 2014
Agung Sucipto
x
DAFTAR ISI
HALAMAN JUDUL LAPORAN .....................................................................i LEMBAR PERSETUJUAN ............................................................................ ii LEMBAR PENGESAHAN ............................................................................ iii LEMBAR HAK ATAS KEKAYAAN INTELEKTUAL................................iv LEMBAR PERNYATAAN..............................................................................v LEMBAR PERSEMBAHAN ..........................................................................vi ABSTRAK ..................................................................................................... vii ABSTRACT.................................................................................................... viii KATA PENGANTAR .....................................................................................ix DAFTAR ISI ...................................................................................................xi DAFTAR GAMBAR ....................................................................................xiv DAFTAR TABEL........................................................................................ xvii DAFTAR RUMUS ........................................................................................xix DAFTAR SIMBOL ........................................................................................xx BAB I PENDAHULUAN............................................................................. I-1 1.1. Latar Belakang .......................................................................... I-1 1.2. Rumusan Masalah ...................................................................... I-3 1.3. Batasan Masalah ........................................................................ I-3 1.4. Tujuan Penelitian ....................................................................... I-3 1.5. Sistematika Penulisan ................................................................ I-3 BAB II LANDASAN TEORI ....................................................................... II-1 2.1. Plagiarisme ................................................................................ II-1 2.1.1. Pengertian Plagiarisme .................................................... II-1 2.1.2. Metode Pendeteksi Plagiarisme ....................................... II-2 2.1.3. Kebutuhan Mendasar Algoritma Pendeteksi Plagiarisme II-2 2.1.4. Persentase kata, kalimat dan paragraf ............................ II-3 2.2. Information Retrieval ................................................................. II-3 2.2.1. Arsitektur information retrieval ...................................... II-3 2.2.2. Koleksi DOkumen (corpus) ............................................ II-4
xi
2.2.3.Text Processing ............................................................... II-4 2.3. Model Dalam Information Retrieval .......................................... II-11 2.3.1. Model Boolean ................................................................. II-11 2.3.2. Model Probabilistik.......................................................... II-12 2.3.3. Model Ruang Vektor........................................................ II-12 2.4. Pemrosesan Dokumen ................................................................ II-15 2.5. Jaccard Coefficient .................................................................... II-16 2.6. Algoritma Winnowing ................................................................ II-16 2.6.1. Pengenalan Algoritma ..................................................... II-16 2.6.2. Algoritma Winnowing ...................................................... II-16 2.6.2.1 Processing ............................................................ II-17 2.6.2.2 Metode K-gram..................................................... II-17 2.6.2.3 Rolling Hash ......................................................... II-18 2.6.2.4 Pembentukan window ........................................... II-19 BAB III METODOLOGI PENELITIAN ..................................................... III-1 3.1. Identifikasi Masalah ................................................................... III-1 3.2. Rumusan Masalah ...................................................................... III-1 3.3. Studi Pustaka.............................................................................. III-2 3.4. Hipotesa...................................................................................... III-2 3.5. Analisa........................................................................................ III-2 3.6. Perancangan Perangkat Lunak ................................................... III-6 3.7. Implementasi Pengujian ............................................................. III-6 3.8. Pengujian Sistem ........................................................................ III-7 3.9. Kesimpulan dan Saran................................................................ III-7 BAB IV ANALISIS DAN PERANCANGAN ............................................. IV-1 4.1. Analisa Source Detection........................................................... IV-1 4.2. Analisa Pembuatan Query.......................................................... IV-2 4.3. Analisa Information Retrieval dengan model ruang vektor ....... IV-9 4.4. Algoritma Winnowing dengan pendekatan biword .................... IV-13 4.5. Perancangan Aplikasi................................................................. IV-38 4.5.1. Use Case Diagram ........................................................... IV-38 4.5.2. Deskripsi Fungsional........................................................ IV-39
xii
4.5.3. Perancangan Database ..................................................... IV-44 4.5.4. Perancangan File Teks ..................................................... IV-45 4.5.5. Perancangan Struktur Menu............................................. IV-45 4.5.6. Perancangan Interface...................................................... IV-46 4.5.6.1 Rancangan Menu Halaman Utama ....................... IV-47 4.5.6.2 Rancangan Menu Koleksi Dokumen .................... IV-49 4.5.6.3 Rancangan Menu Source Detection ..................... IV-50 4.5.6.4 Rancangan Menu Hasil Pengujian........................ IV-52 4.5.6.5 Rancangan Menu Halaman Bantuan .................... IV-53 4.5.6.6 Rancangan Menu Halaman Login ........................ IV-53 BAB V IMPLEMENTASI DAN PENGUJIAN ........................................... V-1 5.1. Tahapan Implementasi .............................................................. V-1 5.1.1. Batasan Implementasi ...................................................... V-1 5.1.2. Lingkungan Implementasi................................................ V-1 5.1.3. Implementasi Antarmuka Aplikasi .................................. V-2 5.2. Hipotesa Pengujian Aplikasi ...................................................... V-9 5.3. Pengujian Aplikasi ..................................................................... V-10 5.3.1. Rencana Pengujian ........................................................... V-10 5.3.1.1 Pengujian Konfigurasi Pembuatan Query ............ V-10 5.3.1.2 Pengujian Kemiripan Dokumen ........................... V-49 5.3.2. Kesmipulan Pengujian ..................................................... V-53 BAB VI PENUTUP ...................................................................................... VI-1 6.1. Kesimpulan ................................................................................ VI-1 6.2. Saran........................................................................................... VI-1 DAFTAR PUSTAKA DAFTAR RIWAYAT HIDUP
xiii
DAFTAR GAMBAR
Gambar
Halaman
2.1.Arsitektur Information Retrieval............................................................. II-4 2.2. Contoh lima tahap indexing pada sistem berbasis content secara urut mulai dari markup removal, tokenization, stopwords filtration, stemming dan weighting ....................................................................................................................... II-5 2.3. Representasi Grafis Sudut Vektor Dokumen dan Query ....................... II-14 2.4. Besar sudut antara vektor query dan vektor dokumen........................... II-14 3.1. Tahapan Penelitian................................................................................. III-1 3.2. Analisa Kerangka Teoritis Penelitian .................................................... III-3 4.1. Flowchart Source Detection .................................................................. IV-2 4.2. Flowchart pembuatan query menggunakan algoritma stemming Nazief Adriani .......................................................................................................... IV-4 4.3. Flowchart pembuatan query tanpa menggunakan algoritma stemming. IV-5 4.4. Flowchart Preprocessing Dokumen ...................................................... IV-6 4.5. Flowchart Stopword Removal................................................................ IV-6 4.6. Flowchart Algoritma Stemming Nazief Adriani.................................... IV-7 4.7. Flowchart Pembentukan triword,quadword dan pentaword ................. IV-8 4.8. Flowchart Perhitungan frekuensi triword,quadword dan pentaword.... IV-8 4.9. Flowchart Pemilihan triword, quadword dan pentaword ..................... IV-9 4.10. Tahapan Preprocessing Dokumen ...................................................... IV-9 4.11. Tahapan Preprocessing Query ............................................................ IV-11 4.12. Penerapan Model Ruang Vektor ......................................................... IV-12 4.13. Tahapan dalam Information Retrieval ................................................ IV-13 4.14. Flowchart algoritma winnowing dengan pendekatan biword .............. IV-14 4.15. Flowchart proses preprocessing .......................................................... IV-15 4.16. Flowchart proses tokenisasi................................................................. IV-16 4.17. Flowchart proses mendapatkan nilai MD5.......................................... IV-16 4.18. Flowchart proses hitung nilai hash...................................................... IV-17
xiv
4.19. Flowchart proses pembentukan window.............................................. IV-17 4.20. Flowchart proses memilih fingerprint ................................................. IV-18 4.21. Flowchart proses hitung similarity ...................................................... IV-18 4.22. Use Case Diaagram Source Detection ................................................ IV-38 4.23. Context Diagram.................................................................................. IV-39 4.24. Data Flow Diagram (DFD) Level 1 .................................................... IV-40 4.25. Data Flow Diagram (DFD) Level 2 proses data master ..................... IV-42 4.26. Entity Relationship Diagram (ERD) .................................................... IV-42 4.27. Rancangan struktur menu admin.......................................................... IV-46 4.28. Rancangan struktur menu pengguna umum......................................... IV-46 4.29. Rancangan interface umum ................................................................. IV-46 4.30. Rancangan interface pengguna umum................................................. IV-47 4.31. interface halaman utama admin ........................................................... IV-48 4.32. interface halaman utama pengguna umum .......................................... IV-48 4.33. interface halaman koleksi dokumen admin ......................................... IV-49 4.34. interface halaman koleksi dokumen pengguna umum......................... IV-49 4.35. interface halaman tambah koleksi dokumen........................................ IV-50 4.36. interface halaman hasil source detection admin .................................. IV-51 4.37. interface halaman hasil source detection pengguna umum ................. IV-51 4.38. interface halaman hasil biword winnowing ......................................... IV-52 4.39. interface halaman hasil pengujian........................................................ IV-52 4.40. interface halaman bantuan ................................................................... IV-53 4.41. interface halaman form login ............................................................... IV-53 5.1. antarmuka menu beranda pengguna umum ........................................... V-2 5.2. antarmuka menu beranda admin ............................................................ V-3 5.3. antarmuka menu koleksi dokumen pengguna umum............................. V-3 5.4. antarmuka menu koleksi dokumen admin ............................................. V-4 5.5. antarmuka menu koleksi dokumen, tambah........................................... V-4 5.6. antarmuka menu koleksi dokumen, hasil pencarian .............................. V-5 5.7. antarmuka menu source detection.......................................................... V-6 5.8. antarmuka menu source detection, hasil proses pada pengguna umum V-6 5.9. antarmuka menu source detection, hasil proses pada admin ................. V-7
xv
5.10. antarmuka perbandingan dokumen ...................................................... V-7 5.11. antarmuka halaman hasil pengujian..................................................... V-8 5.12. antarmuka halaman bantuan ................................................................ V-8 5.13. antarmuka halaman menu login ........................................................... V-9 5.14. Screen shoot kemiripan dokumen pengujian I hasil pertama .............. V-49 5.15. Screen shoot kemiripan dokumen pengujian I hasil kedua.................. V-50 5.16. Screen shoot kemiripan dokumen pengujian I hasil ketiga ................. V-50 5.17. Screen shoot kemiripan dokumen pengujian II hasil pertama ............. V-51 5.18. Screen shoot kemiripan dokumen pengujian II hasil kedua ................ V-52 5.19. Screen shoot kemiripan dokumen pengujian II hasil ketiga ................ V-52
xvi
DAFTAR TABEL
Tabel
Halaman
4.1. Pembobotan index dokumen.................................................................. IV-24 4.2. Hasil Pembobotan index query .............................................................. IV-26 4.3. Hasil Token Biword ............................................................................... IV-28 4.4. Nilai hash token biword......................................................................... IV-33 4.5. Token biword dengan fingerprint yang sama ........................................ IV-37 4.6. Proses DFD Level 1 source detection system........................................ IV-41 4.7. DFD Level 2 proses data master............................................................ IV-42 4.8. Keterangan Entitas pada ERD................................................................ IV-43 4.9. Conceptual data model tabel pengujian ................................................. IV-44 4.10. Conceptual data model tabel hasil pengujian ...................................... IV-44 5.1. Hasil Pengujian I Konfigurasi 1 ............................................................. V-11 5.2. Hasil Pengujian I Konfigurasi 2 ............................................................. V-11 5.3. Hasil Pengujian I Konfigurasi 3 ............................................................. V-12 5.4. Hasil Pengujian I Konfigurasi 4 ............................................................. V-13 5.5. Hasil Pengujian I Konfigurasi 5 ............................................................. V-13 5.6. Hasil Pengujian I Konfigurasi 6 ............................................................. V-14 5.7. Hasil Pengujian I Konfigurasi 7 ............................................................. V-14 5.8. Hasil Pengujian I Konfigurasi 8 ............................................................. V-15 5.9. Hasil Pengujian I Konfigurasi 9 ............................................................. V-15 5.10. Hasil Pengujian I Konfigurasi 10 ......................................................... V-16 5.11. Hasil Pengujian I Konfigurasi 11 ......................................................... V-16 5.12. Hasil Pengujian I Konfigurasi 12 ......................................................... V-17 5.13. Hasil Pengujian I Konfigurasi 13 ......................................................... V-18 5.14. Hasil Pengujian I Konfigurasi 14 ......................................................... V-18 5.15. Hasil Pengujian I Konfigurasi 15 ......................................................... V-19 5.16. Hasil Pengujian I Konfigurasi 16 ......................................................... V-19 5.17. Hasil Pengujian I Konfigurasi 17 ......................................................... V-20
xvii
5.18. Hasil Pengujian I Konfigurasi 18 ......................................................... V-20 5.19. Hasil Pengujian 1 dengan seluruh konfigurasi..................................... V-21 5.20. Hasil Pengujian II Konfigurasi 1.......................................................... V-25 5.21. Hasil Pengujian II Konfigurasi 2.......................................................... V-25 5.22. Hasil Pengujian II Konfigurasi 3.......................................................... V-26 5.23. Hasil Pengujian II Konfigurasi 4.......................................................... V-26 5.24. Hasil Pengujian II Konfigurasi 5.......................................................... V-27 5.25. Hasil Pengujian II Konfigurasi 6.......................................................... V-27 5.26. Hasil Pengujian II Konfigurasi 7.......................................................... V-28 5.27. Hasil Pengujian II Konfigurasi 8.......................................................... V-28 5.28. Hasil Pengujian II Konfigurasi 9.......................................................... V-29 5.29. Hasil Pengujian II Konfigurasi 10........................................................ V-30 5.30. Hasil Pengujian II Konfigurasi 11........................................................ V-30 5.31. Hasil Pengujian II Konfigurasi 12........................................................ V-31 5.32. Hasil Pengujian II Konfigurasi 13........................................................ V-31 5.33. Hasil Pengujian II Konfigurasi 14........................................................ V-32 5.34. Hasil Pengujian II Konfigurasi 15........................................................ V-32 5.35. Hasil Pengujian II Konfigurasi 16........................................................ V-33 5.36. Hasil Pengujian II Konfigurasi 17........................................................ V-34 5.37. Hasil Pengujian II Konfigurasi 18........................................................ V-34 5.38. Hasil Pengujian 1I dengan seluruh konfigurasi ................................... V-35 5.39. Hasil Pengujian 1II dengan seluruh konfigurasi .................................. V-38 5.40. Hasil Pengujian 1V dengan seluruh konfigurasi .................................. V-41 5.41. Hasil Pengujian V dengan seluruh konfigurasi .................................... V-44 5.42. Hasil pengujian terbaik pada setiap pengujian..................................... V-47
xviii
DAFTAR RUMUS
Rumus
Halaman
2.1. Logarithm term frequency...................................................................... II-10 2.2. Augmented term frequency..................................................................... II-10 2.3. Inverse Document Frequency ................................................................ II-11 2.4 Rumus Relevansi Model ruang vektor................................................... II-14 2.5. Sudut antara vektor ................................................................................ II-14 2.6. Inner product ......................................................................................... II-15 2.7. Cosine Similarity.................................................................................... II-15 2.8. Pembobotan Query................................................................................. II-15 2.9. Pembobotan Kata ................................................................................... II-15 2.10. Jaccard Coefficient .............................................................................. II-16 2.11. Metode hash......................................................................................... II-19 2.12. Rolling hash ......................................................................................... II-19
xix
DAFTAR SIMBOL Flowchart Terminator : Simbol terminator (Mulai/ selesai) merupakan tanda bahwa sistem akan dijalankan atau berakhir
Proses: Simbol yang digunakan untuk melakukan pemrosesan data baik oleh user maupun komputer (sistem)
Verifikasi : Simbol yang digunakan untuk memutuskan apakah valid atau tidak validnya suatu kejadian.
Data : Simbol yang digunakan untuk mendeskripsikan dat yang digunakan.
Data Flow Diagram (DFD)
Entitas Relationship Diagram (ERD)
xx
xxi
