IMPLEMENTASI DETEKSI PENJIPLAKAN DENGAN ALGORITMA WINNOWING PADA DOKUMEN TERKELOMPOK
Tugas Akhir I Wayan Surya Priantara 5107100057
Dosen Pembimbing Diana Purwitasari, S.Kom., M.Sc. Umi Laili Yuhana, S.Kom., M.Sc.
1
Latar Belakang 2
Banyak artikel / tulisan yang dihasilkan oleh seseorang, menjiplak karya milik orang lain. Kegiatan penjiplakan sering terjadi pada bidang pendidikan. Sebuah dokumen dibandingkan satu persatu walau tidak memiliki kesamaan topik.
3
PERMASALAHAN
Rumusan Masalah 4
Bagaimana mengelompokan dokumen berdasarkan kesamaan kalimat. Bagaimana mekanisme pengecekan kesamaan kalimat pada satu dokumen dengan koleksi dokumen
Batasan Masalah 5
Dataset yang akan dilakukan pendeteksian adalah file teks digital yang berekstensi .doc, .docx, dan .pdf.
Tujuan 6
Mengefektifkan pengecekan penjiplakan pada banyak dokumen dengan mengelompokan dokumen.
Tipe-tipe Penjiplakan 7
Word for word plagiarism Menyalin setiap kata secara lansung tanpa diubah sedikitpun. Plagiarism of authorship Mengakui hasil karya orang lain sebagai hasil karya sendiri Plagiarism of ideas. Mengakui hasil pemikiran atau ide orang lain sebagai pemikirin diri sendiri. Plagiarism of sources Jika seorang penulis menggunakan kutipan dari penulis tanpa mencantumkan narasumbernya.
Contoh 8
Dokumen A : ...... cairan hidrotermal tidak harus berasal dari larutan magma, kalau demikian istilah hidrotermal bukan berarti genetik.. ......
Dokumen B : .... Park dan Diarmid (1964) berpendapat bahwa cairan hidrotermal tidak harus berasal dari larutan magma, kalau demikian istilah hidrotermal bukan berarti genetik.
Langkah-langkah 9
Mulai Dokumen
Ya
Membaca Isi Dokumen
Membentuk Kelompok
String isi dokumen
Membentuk Fingerprint
Mendeteksi Tingkat Kesamaan
Membentuk Kelompok
Fingerprint
Menampilkan Hasil
Tingkat Kesamaan
Tidak
Menentukan Kelompok
Membentuk fingerprint dengan algoritma winnowing dan untuk mengelompokan dengan algoritma k-means++
Selesai
Tingkat Kesamaan 10
Tingkat kesamaan sebuah dokumen terhadap dokumen lain diukur dengan cara membandingkan seluruh nilai hash (fingerprint) antar dokumen.
𝑗𝑢𝑚𝑙𝑎 𝑎𝑠 𝑦𝑎𝑛𝑔 𝑠𝑎𝑚𝑎 𝑇𝑖𝑛𝑔𝑘𝑎𝑡 𝐾𝑒𝑠𝑎𝑚𝑎𝑎𝑛 = 𝑥 100% 𝑡𝑜𝑡𝑎𝑙 𝑔𝑎𝑏𝑢𝑛𝑔𝑎𝑛 𝑗𝑢𝑚𝑙𝑎 𝑎𝑠
Tampilan Antarmuka 11
Tampilan Antarmuka 12
Tampilan Antarmuka 13
Dataset 14
Dataset adalah dokumen-dokumen tugas mata kuliah sosio etika pada semester gasal 2009/2010 di Teknik Informatika ITS . No 1
Nama Tugas Tugas 1
2
Tugas 2
3
Tugas 3 Total
Topik
Jumlah
Komunikasi
15
Bioinformatika
15
Surface Recontruction
15
Hyperspectral
15 60
Skenario Uji Coba 15
Pengelompokan • Penentuan Nilai Alpha • Penentuan Kelompok untuk Dokumen baru • Waktu Deteksi Penjiplakan
Deteksi Penjiplakan • Hasil Tingkat Kemiripan
Penentuan Nilai Alpha 16
Jumlah Kelompok yang Terbentuk Percobaan No.
Nilai Alpha
1
2
3
4
5
Rata-rata
1
0,25
3
4
4
4
4
4
2
0,5
6
6
6
5
6
6
3
0,75
7
8
5
6
7
7
4
1
6
5
8
8
4
7
Analisis Bahwa semakin kecil nilai alpha, maka jumlah kelompok yang sebaiknya terbentuk semakin sedikit. Begitupula sebaliknya.
Penentuan Nilai Alpha 17
Nilai Akurasi tiap Percobaan Percobaan
No.
Nilai Alpha
1
2
3
4
5
Ratarata
1
0,25
0,6469
0,7613
0,7158
0,8877
0,8134
0,7650
2
0,5
0.8616
0,8055
0,7777
0,8373
0,8228
0.8209
3
0,75
0,7085
0,8998
0,4157
0,7368
0,5501
0,6621
4
1
0,0886
0,3111
0,5940
0,5135
0,3889
0,3792
Analisis Nilai alpha 0,5 memiliki nilai akurasi tertinggi. Hal ini dikarenakan pada nilai tersebut banyak dokumen yang sesuai terkelompok sesuai dengan topik.
Hasil Pembentukan Kelompok 18
No
Nama Kelompok
Jumlah Dokumen
Topik Pembahasan
1
Kelompok 0
14
-
2
Kelompok 1
6
Bioinformatika
3
Kelompok 2
8
Hyperspectral
4
Kelompok 3
17
Komunikasi/Surface
5
Kelompok 4
7
Hyperspectral
6
Kelompok 5
8
Bioinformatika
Hasil Uji Coba Penentuan Kelompok 19
Nama Dokumen Tugas 2 Sostek 5107100125 Kelas B.doc Tugas 2 Sostek5107100032 kelas B.doc Tugas 2 Sostek5107100167 Kelas B.doc Tugas 2 SosTek_5107100070_Kel as B.doc Tugas 3 Soset 5101700098 - Kelas B.doc Tugas 3 sosioetika5107100116 Kelas B.doc Tugas 3 Sostek 5106100024 - Kelas B.doc
Topik Bioinformatika
Hasil Pengelompokan Kelompok 1 Bioinformatika Kelompok 3 Surface Kelompok 3 Surface Kelompok 3 Surface
Keterangan Benar
Hyperspectral
Kelompok 2 Hyperspectral
Benar
Hyperspectral
Kelompok 4 Hyperspectral Kelompok 2 Hyperspectral
Benar
Surface Surface Bioinformatika
Hyperspectral
Benar Benar Salah
Benar
Analisis Pada penentuan kelompok untuk dokumen baru memiliki tingkat kesesuaian yang tinggi
Hasil Uji Coba Waktu Deteksi 20
Jumlah Kelompok Nama Dokumen
Tidak Dikelompokan
Dikelompokan (6 Kelompok)
Quick Sort2.docx
64 detik
4 detik
Tugas 1 Soset - 5107100098 - Kelas B.doc
98 detik
4 detik
Tugas 1 sostek - 5107100100 kelas B.doc
88 detik
5 detik
Tugas 1 Sostek - 5106100093 Kelas B.doc
84 detik
5 detik
107 detik
9 detik
74 detik
9 detik
Tugas 1 Sostek - 5106100104 kelas (B).doc Tugas 1 Sostek - 5106100117 Kelas B.docx
Analisis Sebuah dokumen dilakukan pendeteksian penjiplakan dokumen waktu yang diperlukan lebih lama pada kumpulan yang tidak dikelompokan dibandingkan kumpulan dokumen yang dikelompokan
Hasil Deteksi Penjiplakan 21
Analisis Dari dataset dokumen ditemukan beberapa dokumen yang di duga melakukan penjiplakan
Hasil Uji Coba Deteksi Penjiplakan 22
Kesimpulan 23
Berdasarkan hasil percobaan bahwa nilai alpha yang terbaik adalah 0,50. Hal ini dikarenakan dari jumlah kelompok yang terbentuk stabil dan nilai akurasi yang dimiliki cukup tinggi. Selain itu pembahasan topik pada tiap kelompok tidak terlalu tinggi atau pun rendah sehingga jumlah pembagian anggota tiap kelompok hampir merata. Dari data set yang digunakan telah ditemukan dokumen yang diduga melakukan penjiplakan
Terima Kasih 24
Definisi Penjiplakan 25
Kamus Besar Bahasa Indonesia Menggambar
atau menulis garis-garis gambaran atau tulisan yg telah tersedia (dengan menempelkan kertas kosong pada gambar atau tulisan yg akan ditiru). Mencontoh atau meniru tulisan atau pekerjaan orang lain. Mencuri karangan orang lain dan mengakui sebagai karangan sendiri. Mengutip karangan orang lain tanpa seizin penulisnya. Back
Algoritma Winnowing 26
Winnowing adalah algoritma yang digunakan untuk melakukan proses document fingerprinting. Document fingerprinting merupakan proses mengubah string menjadi nilai-nilai hash. Input dari proses document fingerprinting adalah string teks. Kemudian outputnya akan berupa sekumpulan nilai hash yang disebut fingerprint.
Contoh Penerapan Alg. Winnowing 27
1. 2.
Teks : the classic problem Removing : theclassicproblem n-gram (n=5) : thecl hecla eclas class lassi assic ssicp sicpr icpro cprob probl roble oblem
3.
Hashing : rolling hash 13518 12463 12232 12268 12852 12411 13774 13491 12639 12500 13551 13538 13021
4.
Window : 1 3 5 7 9
5.
Back
[13518 12463 12232 12268] [12232 12268 12852 12411] [12852 12411 13774 13491] [13774 13491 12639 12500] [12639 12500 13551 13538 ]
2 [12463 12232 12268 12852] 4 [12268 12852 12411 13774] 6 [12411 13774 13491 12639] 8 [13491 12639 12500 13551] 10 [12500 13551 13538 13021]
Fingerprint : 12232 12268 12411 12500
Rolling Hashing 28
Fungsi hash 𝐻(𝑐1 …𝑐 )didefinisikan sebagai berikut: 𝑘
𝑐1 ∗ 𝑏
+ 𝑐2 ∗ 𝑏
𝑘−2
+ ⋯ + 𝑐 𝑘−1 ∗ 𝑏𝑘 + 𝑐𝑘
thecl = t * 3 (5-1) + h * 3 (5-2) + e * 3 (5-3) c * 3 (5-4) + l * 3 (5-5) = 116 * 3 (4) + 104 * 3 (3) + 101 * 3 (2) + 99 * 3 (1) + 105 * 3 (0) = 13518
Keuntungan dari rolling hash adalah untuk nilai hash berikutnya dapat dilakukan dengan cara:
𝐻
𝑘−1
𝑐2 …𝑐 𝑘+1
= 𝐻
𝑐1 …𝑐 𝑘
− 𝑐1 ∗ 𝑏
hecla = (13518 – t * 3 (4) ) * 3 + a = 13518 – 116 * 3 (4) ) * 3 + 97 = 12463
Back
𝑘−1
∗ 𝑏 + 𝑐(𝑘+1)
Algoritma K-means++ 29
Langkah algoritma K-means++ adalah :
Menentukan satu centroid awal pada seluruh data dokumen Melakukan pembobotan D(d), ketidakmiripan tiap dokumen dengan centroid terdekat
Memilih satu centroid dari data dengan probabalitas tiap dokumen terpilih D(d2). Ulangi langkah 2, bila centroid terpilih < k
Melakukan pengelompokan K-means.
Algoritma K-means 30
Langkah-langkah Alg. K-means
Menentukan nilai k
Menentukan centroid
Mengelompokkan setiap dokumen
Menghitung tingkat kesamaan setiap dokumen ke masing-masing centroid
Menentukan nilai – nilai hash sebagai centroid baru Kembali ke langkah 3 jika nilai – nilai hash pada centroid baru dengan centroid lama tidak sama.
Penentuan Centroid 31
centroidα(C) = ⋃ f(Cα, h) | h ∈ ⊎ W(di), Dok 1
Dok 2
Dok 3
12479
12875
13444
𝑓(,𝐶) 𝑛
Frekuensi
≥ 𝛼
𝑓(, 𝐶) 𝑛
13455
13455
13114
Hash
12875
12399
13455
12479
1
0,3333
13887
13444
13455
3
1
12875
2
0,6667
13887
1
0,3333
12399
1
0,3333
13444
2
0,6667
13114
1
0,3333
Penentuan Jumlah Kelompok 32
𝑘≈ 𝑛 2
Rule of Thumb Hartigan Index H(k) = (n – k – 1)
𝑒𝑟𝑟 𝑘 − 𝑒𝑟𝑟 𝑘+1 𝑒𝑟𝑟 𝑘+1
dimana :
err(k) = Back
𝑘 𝑖=1
𝑛 𝑗 =1;𝑗 𝜀𝐶𝑖
𝑑2 𝑋𝑗 , 𝑋𝐶𝑖
Rule of Thumb 33
Rule of Thumb merupakan algoritma penentuan jumlah kelompok yang sebaiknya terbentuk dalam pengklasteran berdasarkan banyaknya data yang tersedia Contoh Rule of Thumb
𝑘≈ 𝑛 2
𝑘≈
100
𝑘 ≈ 50 𝑘 ≈ 7,071
2
Hartigan Index 34
Hartigan index merupakan salah satu metode statistik untuk menguji perubahan relatif dari nilai perubahan suatu kelompok. Metode ini dapat digunakan untuk mengetahui jumlah kelompok yang sesuai dari perbandingan tingkat error suatu kelompok dengan kelompok satu setelahnya.
Hartigan Index 35
Contoh
dimana jumlah data adalah 100
k
Nilai err(k)
2
27,80
3
13,70
4
11,38
H(2) = (100 – 2 – 1)
27,80− 13,70
k
H(k)
2
99,8321
3
19,5711
13,70
