PENDETEKSIAN PENJIPLAKAN KODE PROGRAM C DENGAN BISECTING K-MEANS
ARIZAL NOTYASA
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2013
PERNYATAAN MENGENAI SKRIPSI DAN SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA Dengan ini saya menyatakan bahwa skripsi berjudul Pendeteksian Penjiplakan Kode Program C dengan Bisecting K-means adalah benar karya saya denganarahan dari komisi pembimbing dan belum diajukan dalam bentuk apa pun kepada perguruan tinggi mana pun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir skripsi ini. Dengan ini saya melimpahkan hak cipta dari karya tulis saya kepada Institut Pertanian Bogor. Bogor, Juni 2013 Arizal Notyasa NIM G64070038
ABSTRAK ARIZAL NOTYASA. Pendeteksian Penjiplakan Kode Program C dengan Bisecting K-means. Dibimbing oleh AHMAD RIDHA. Penjiplakan tugas berupa kode program merupakan masalah yang sering dihadapi oleh berbagai institusi akademik. Pendeteksian penjiplakan secara manual memakan banyak waktu dan tenaga. Oleh sebab itu, sebuah sistem yang dapat membantu pendektesian penjiplakan kode program dibutuhkan. Pendeteksian dapat dilakukan dengan mengelompokkan kode-kode program yang mirip berdasarkan struktur kodenya. Cara ini dilakukan pada penelitian sebelumnya dengan menggunakan iterasi K-means otomatis. Iterasi K-means otomatis ini, walau dapat menghasilkan clusters yang cukup baik, tapi membutuhkan waktu eksekusi yang lama. Tujuan penelitian ini adalah meningkatkan efisiensi waktu dan clusters hasil pendeteksian dengan menggunakan algoritme bisecting K-means. Hasil penelitian ini menunjukkan bahwa ada peningkatan efisiensi waktu yang cukup signifikan dari 11.68 detik menjadi 6.64 detik. Algoritme bisecting K-means juga menghasilkan jumlah clusters yang lebih sedikit dengan nilai Rand Index yang lebih baik daripada iterasi K-means. Selain itu, percobaan dengan 2-gram hingga 6-gram menunjukkan bahwa 4-gram memiliki kinerja yang paling baik. Kata kunci: bisecting k-means, hierarchical clustering, pendeteksi penjiplakan
ABSTRACT ARIZAL NOTYASA. C Source Code Plagiarism Detection Using Bisecting Kmeans. Supervised by AHMAD RIDHA. Plagiarism of source codes assignments is a widespread problem in academic institutions. Manual plagiarism detection is time and energy consuming. Therefore, a system that can help detecting this plagiarism is needed. The detection can be done by grouping similar source codes based on their structure. This method is used in previous research by using automatic K-means iterations algorithm. That algorithm, although produced decent clusters, had a long execution time. The purpose of this research is to improve the time efficiency and clusters result quality by using bisecting K-means algorithm. The results showed a significant improvement in execution time from 11.68 seconds to 6.64 seconds. Bisecting K-means also produced fewer clusters with slightly better Rand Index than K-means iterations. Furthermore, experiments using 2-gram to 6-gram showed that 4-gram resulted in the best performance. Keywords: bisecting K-means, hierarchical clustering, plagiarism detection
PENDETEKSIAN PENJIPLAKAN KODE PROGRAM C DENGAN BISECTING K-MEANS
ARIZAL NOTYASA
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Komputer pada Departemen Ilmu Komputer
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2013
Judul Skripsi : Pendeteksian Penjiplakan Kode Program C dengan Bisecting K-means Nama : Arizal Notyasa NIM : G64070038
Disetujui oleh
Ahmad Ridha, SKom MS Pembimbing
Diketahui oleh
Dr Ir Agus Buono, MSi MKom Ketua Departemen
Tanggal Lulus:
PRAKATA Puji dan syukur penulis panjatkan ke hadirat Allah subhanahu wa-ta’ala atas rahmat dan hidayah-Nya sehingga penulis dapat menyelesaikan tugas akhir ini. Shalawat serta salam juga penulis sampaikan pada junjungan Nabi besar Muhammad shallallahu ‘alaihi wa sallam beserta keluarga dan sahabatnya. Banyak pihak yang telah membantu penulis hingga terselesaikannya tugas akhir ini. Oleh sebab itu, penulis ingin mengucapkan rasa terima kasih kepada: 1 Ayahanda Listyo Sumitro dan ibunda Diah Aryati serta kakak penulis Arfika Nurhudatiana dan Yulianto yang senantiasa mendoakan, memotivasi, dan memberikan kasih sayangnya kepada penulis. 2 Bapak Ahmad Ridha, SKom MS selaku dosen pembimbing yang telah membimbing dan mengarahkan penulis selama penelitian tugas akhir ini. 3 Bapak Sony Hartono Wijaya, SKom MKom dan Bapak Mushthofa, SKom MSc selaku dosen penguji. 4 Seluruh teman-teman Ilkomerz 44 atas ilmu, semangat, dan dukungannya selama penulis melakukan penelitian. 5 Sahabat-sahabat di T3S: Trijaya, Wahyu, Putri, Nadea, Nina, Ikhwan, dan Adi atas segala suka dan duka yang dialami bersama. Akhir kata, penulis mohon maaf apabila dalam tulisan ini masih terdapat banyak kekurangan. Penulis berharap semoga tulisan ini dapat bermanfaat bagi para pembaca.
Bogor, Juni 2013 Arizal Notyasa
DAFTAR ISI DAFTAR TABEL
v
DAFTAR GAMBAR
v
DAFTAR LAMPIRAN
v
PENDAHULUAN
1
Latar Belakang
1
Perumusan Masalah
2
Tujuan Penelitian
2
Manfaat Penelitian
2
Ruang Lingkup Penelitian
3
METODE
3
Pengambilan dan Pemilihan Data
3
Pengelompokan Manual
3
Praproses Data
4
Bisecting K-means
6
Validasi Hasil Clustering
8
Perbandingan dengan Penelitian Sebelumnya
9
HASIL DAN PEMBAHASAN
10
Pengambilan dan Pemilihan Data
10
Pengelompokan Manual
10
Praproses Data
11
Bisecting K-means
12
Validasi Hasil Clustering
16
Perbandingan dengan Penelitian Sebelumnya
17
Rentang Nilai i Terbaik
19
Pengaruh Ukuran N-gram terhadap Hasil Clustering
19
SIMPULAN DAN SARAN
20
Simpulan
20
Saran
21
DAFTAR PUSTAKA
21
RIWAYAT HIDUP
27
DAFTAR TABEL 1 2 3 4 5 6 7 8 9 10 11 12 13
Contoh aturan konversi kode program Set data awal Set data setelah pengelompokan manual Term frequency Hasil percobaan clustering untuk DataSet1 Hasil percobaan clustering untuk DataSet2 Hasil percobaan clustering untuk DataSet3 Hasil percobaan clustering untuk DataSetAll Nilai RI, jumlah clusters, jumlah dokumen, dan waktu eksekusi clustering setiap set data Perbandingan hasil clustering bisecting K-means dengan iterasi Kmeans pada saat nilai i=0.97 Perbandingan hasil clustering bisecting K-means dengan iterasi Kmeans pada saat nilai i terbaik Nilai i terbaik untuk setiap set data Hasil percobaan clustering dengan 2-gram hingga 6-gram untuk setiap set data
5 10 10 12 13 13 14 15 15 17 18 19 20
DAFTAR GAMBAR 1 2 3 4 5
Tahapan penelitian Praproses data Ilustrasi kesamaan kosinus False negative dokumen D42 dan D44 pada DataSet1 False positive dokumen D25 dan D59 pada DataSet1
3 4 7 16 17
DAFTAR LAMPIRAN 1 Contoh kode program dari masing-masing set data yang digunakan dalam penelitian 2 Hasil pengelompokan manual untuk DataSet1 3 Hasil pengelompokan manual untuk DataSet2 4 Hasil pengelompokan manual untuk DataSet3 5 Tabel aturan konversi kode program menjadi token sederhana
22 23 24 25 26
PENDAHULUAN Latar Belakang Penjiplakan atau plagiarisme merupakan suatu masalah yang sering dihadapi oleh institut-institut akademik. Penjiplakan pada kode program adalah penggunaan kembali struktur dan syntax bahasa pemrograman yang berasal baik dari mahasiswa ataupun sumber lainnya (Burrows 2004). Tugas akademik berupa kode program umumnya dikumpulkan dalam bentuk berkas digital. Hal ini menyebabkan tugas kode program rentan terhadap aksi penjiplakan. Saat ini pendeteksian penjiplakan semakin sulit dilakukan. Hal ini disebabkan oleh bertambahnya jumlah mahasiswa dan semakin mudahnya mahasiswa untuk saling berbagi hasil perkerjaan mereka baik melalui internet maupun media lainnya. Pendeteksian juga semakin dipersulit dengan adanya modifikasi kode program yang dilakukan oleh mahasiswa untuk mengelabui pendeteksian. Modifikasi yang dilakukan antara lain penambahan atau penghapusan baris komentar atau pengubahan nama variabel atau fungsi. Pendeteksian penjiplakan dengan menggunakan tenaga manusia akan memakan banyak waktu dan tenaga. Oleh sebab itu, dibutuhkan suatu sistem yang dapat membantu pendeteksian penjiplakan kode program secara otomatis. Burrows (2004) telah melakukan pendeteksian penjiplakan untuk repositories kode program berskala besar. Pendeteksian yang dilakukan Burrows ialah dengan mengindeks semua kode program yang terkumpul kemudian melakukan query terhadap hasil indexing tersebut untuk mendapatkan kode-kode program yang mirip. Burrows menggunakan cara pendeteksian penjiplakan structure-oriented code-based system. Sistem berorientasi struktur kode program ini membuat representasi sederhana dari kode program. Sistem ini sengaja mengabaikan elemen yang mudah dimodifikasi seperti komentar, whitespace dan nama variabel. Sistem berorientasi struktur ini juga tidak rentan terhadap penambahan kode program yang bersifat redundant. Mahasiswa harus memodifikasi sebagian besar kode program apabila ingin mengelabui pendeteksian (Bowyer dan Hall 1999, Gitchel dan Tran 1999, Prechelt et al. 2002 dalam Burrows 2004). Gumilang (2013) menggunakan structure-oriented code-based system untuk pendeteksian penjiplakan kode program C dengan clustering. Pendeteksian yang dilakukan Gumilang ialah dengan mengelompokkan kode-kode program berdasarkan kemiripan strukturnya. Proses pengelompokan pada penelitian Gumilang dilakukan dengan menggunakan algoritme flat clustering K-means. Flat clustering memiliki kelemahan, yaitu harus ditentukannya jumlah clusters keluaran yang diinginkan secara manual. Hal ini pada penelitian Gumilang diatasi dengan melakukan iterasi K-means otomatis. Iterasi K-means otomatis yaitu melakukan clustering menggunakan K-means dengan nilai K bertambah secara otomatis pada setiap iterasinya. Iterasi berhenti apabila anggota-anggota clusters hasil sudah cukup dekat dengan centroid-nya. Iterasi K-means otomatis ini membutuhkan waktu eksekusi yang lama. Hal ini dikarenakan pada setiap iterasi dilakukan proses clustering dengan jumlah dokumen yang sama dan jumlah centroids yang semakin bertambah.
2 Pengelompokan tanpa perlu menentukan terlebih dahulu jumlah cluster-nya dapat dilakukan dengan menggunakan hierarchical clustering. Hierarchical clustering terbagi menjadi 2 jenis, yaitu hierarchical agglomerative clustering (HAC) dan hierarchical divisive clustering (HDC). HAC menggunakan pendekatan bottom-up, sedangkan HDC menggunakan pendekatan top-down. HDC, dalam beberapa kasus, terbukti dapat menghasilkan hierarki clusters yang lebih akurat dibandingkan dengan HAC. Hal ini dikarenakan HDC menggunakan pendekatan top-down dan memiliki informasi penyebaran seluruh dokumen sejak awal clustering (Manning et al. 2008). HDC juga dapat berjalan lebih cepat dibandingkan dengan HAC apabila dikombinasikan dengan algoritme flat clustering efisien seperti K-means. Pendeteksian penjiplakan pada penelitian ini dilakukan dengan menerapkan structure-oriented code-based system dan kode-kode program yang mirip kemudian dikelompokkan dengan HDC. Algoritme HDC yang digunakan adalah bisecting K-means. Bisecting K-means adalah algoritme HDC yang menggunakan K-means untuk pemisahan setiap cluster-nya.
Perumusan Masalah Perumusan masalah dalam penelitian ini adalah 1 Bagaimana mengimplementasikan structure-oriented code-based system dan algoritme HDC bisecting K-means dalam pendeteksian penjiplakan kode program C. 2 Apakah pengelompokan kode-kode program dengan menggunakan bisecting K-means membutuhkan waktu eksekusi yang lebih singkat dibandingkan dengan iterasi K-means otomatis. 3 Apakah bisecting K-means dapat menghasilkan clusters yang lebih baik dibandingkan dengan iterasi K-means otomatis.
Tujuan Penelitian Tujuan dari penelitian ini ialah mengimplementasikan structure-oriented code-based system dan algoritme HDC bisecting K-means untuk membantu pendeteksian penjiplakan pada kode program C secara otomatis, cepat, dan akurat.
Manfaat Penelitian Manfaat penelitian ini ialah mempermudah pendeteksian penjiplakan kode program sehingga efisiensi kerja staf akademik dapat meningkat dan aksi penjiplakan yang dilakukan mahasiswa berkurang.
3 Ruang Lingkup Penelitian Ruang lingkup penelitian ini adalah 1 Data yang digunakan adalah 233 buah kode program tugas pemrograman berbahasa C. 2 Penelitian ini mengasumsikan tidak adanya makro pada kode program sehingga preprocessor directives akan dihilangkan semua.
METODE Secara garis besar penelitian ini memiliki 6 tahapan. Tahapan-tahapan pada penelitian ini dapat dilihat pada Gambar 1. Pengambilan dan pemilihan data
Pengelompokan manual
Perbandingan dengan penelitian sebelumnya
Praproses data
Bisecting K-means
Validasi hasil clustering
Gambar 1 Tahapan penelitian Pengambilan dan Pemilihan Data Data yang digunakan sebagai korpus kode program pada penelitian ini diperoleh dari Bagian Komputasi Terapan, Departemen Ilmu Komputer. Data pada penelitian ini berupa berkas digital kode program bahasa C. Kode program yang dipilih berasal dari tugas-tugas pemrograman yang memiliki tingkat kesulitan tidak terlalu mudah dan tidak terlalu susah. Hal ini dikarenakan tugas yang terlalu mudah akan memiliki variasi algoritme pemecahan yang sedikit, sedangkan tugas yang terlalu susah cenderung memiliki jumlah kode program yang sedikit karena banyak mahasiswa yang tidak mengumpulkan tugas.
Pengelompokan Manual Pengelompokan manual pada penelitian ini dilakukan melalui 2 tahap. Tahap pertama adalah pemeriksaan nilai output kode program dan tahap kedua adalah pemeriksaan struktur dan algoritme kode program. Pada tahap pertama setiap kode program dijalankan dan diperiksa nilai output-nya. Kode-kode program yang memiliki nilai output yang sama akan dikelompokkan ke dalam satu cluster yang sama. Selanjutnya pada tahap kedua, kode-kode program tiap
4 cluster tersebut diperiksa strukturnya. Kode-kode program dengan struktur dan algoritme yang secara signifikan sama dikelompokkan ke dalam cluster yang sama dan kode program yang berbeda dipisah ke dalam cluster yang berbeda.
Praproses Data Praproses data dilakukan untuk mengubah data mentah, yaitu kode-kode program C, ke format yang dapat diproses dalam clustering, yaitu tabel term frequency. Praproses data pada penelitian ini terbagi ke dalam 4 tahapan. Gambar 2 menunjukkan alur tahapan praproses data.
Tabel term frequency
Kumpulan kode program
Pembuangan preprocessor directives
Tokenisasi
Penyederhanaan
N-gram
Gambar 2 Praproses data Pembuangan preprocessor directives Tahap pertama adalah pembuangan preprocessor directives. Preprocessor directives adalah sejumlah baris di awal kode program yang diawali dengan karakter “#”. Pembuangan ini dilakukan karena pada penelitian ini diasumsikan tidak adanya penggunaan makro pada kode program. Tokenisasi Proses Tokenisasi dilakukan untuk mendapatkan keywords dan special characters dari kode program. Pada proses tokenisasi, karakter whitespace dibuang semua sehingga didapat term atau string uniknya saja (Manning et al. 2008). Baris komentar pada kode program dibuang karena tidak berpengaruh terhadap output program. Karakter “;” juga dibuang karena merupakan karakter umum yang selalu digunakan di setiap akhir baris kode program C. Penyederhanaan Selanjutnya pada proses penyederhanaan, keywords dan special characters kode program diubah menjadi token sederhana agar lebih ringkas dan mudah dalam pembentukan term. Kode program yang telah diubah menjadi sebuah string panjang token sederhana disebut dengan token stream (Burrows 2004). Konversi kode program menjadi token sederhana dilakukan berdasarkan aturan konversi seperti pada Tabel 1.
5 Tabel 1 Contoh aturan konversi kode program Keywords
Token sederhana
int for return ( ) { } = < + , ALPHANUM STRING
A M R H I K L O M A J N 5
Tabel 1 memperlihatkan contoh aturan konversi beberapa keywords dan special characters kode program C menjadi token sederhana. ALPHANUM adalah nama fungsi, nama variabel, atau nilai variabel. STRING adalah sederetan karakter yang diapit oleh tanda "" (kutip ganda). Berikut adalah contoh kode program yang diubah menjadi token stream: 1 2 3 4 5 6 7 8
#include <stdio.h> int main (){ int var; for (var=0; var<5; var++){ printf("%d\n", var); } return 0; }
Token stream: ANhikANMhNoNNmNNaaikNh5jNilRNl N-gram Tahap selanjutnya adalah proses N-gram. N-gram adalah potongan sejumlah N karakter dari sebuah string. N-gram merupakan sebuah metode yang diaplikasikan untuk pembangkitan kata atau karakter. Pada penelitian ini metode N-gram digunakan untuk mengambil potongan-potongan karakter huruf sejumlah N dari suatu token stream. N-gram dibedakan berdasarkan jumlah potongan karakter sebesar N-nya (Cavnar dan Trenkle 1994). Pengambilan potongan-potongan kata berupa karakter huruf tersebut ditambahkan dengan padding karakter blank untuk membantu pembentukan N-gram di awal dan akhir string. Sebagai contoh kata ”TEXT” dapat diuraikan ke dalam beberapa N-gram berikut (penggunaan karakter „_‟ merepresentasikan blank): uni-grams : T, E, X, T bi-grams : _T, TE, EX, XT, T_ tri-grams : _TE, TEX, EXT, XT_
6 quad-grams : _TEX, TEXT, EXT_ quint-grams : _TEXT, TEXT_ Penggunaan N-gram adalah metode yang sesuai untuk pendeteksian penjiplakan. Hal ini dikarenakan modifikasi atau perubahan pada kode program akan mempengaruhi beberapa N-gram yang berdekatan saja. Oleh sebab itu, kode program yang dimodifikasi akan tetap memiliki sebagian besar N-gram yang sama dengan kode program aslinya dan pendeteksian penjiplakan menjadi semakin mudah dilakukan (Burrows 2004). Lebih jelasnya berikut contoh 2-gram dari kata “Text” dan “Teext”: Text : _T Te ex xt t_ Teext : _T Te ee ex xt t_ Modifikasi hanya menyebabkan perbedaan munculnya N-gram “ee” pada string “Teext”, sedangkan N-gram sisanya sama dengan N-gram pada string “Text”. Pada penelitian ini, proses N-gram dilakukan pada token stream dengan ukuran N=4. N dipilih 4 karena merupakan nilai N terbaik untuk pendeteksian penjiplakan kode program (Chawla 2003 dalam Burrows 2004). Pada bagian akhir penelitian ini juga akan dilakukan percobaan pendeteksian dengan menggunakan nilai N yang berbeda. Hal ini dilakukan untuk melihat pengaruh nilai N yang lebih kecil dan lebih besar terhadap hasil pendeteksian pada penelitian ini. Selanjutnya kemunculan setiap N-gram pada masing-masing dokumen dihitung untuk memperoleh tabel term frequency. Tabel term frequency merupakan tabel yang menyimpan statistik kemunculan seluruh term atau N-gram suatu koleksi dokumen. Tabel ini kemudian digunakan untuk membentuk vektorvektor dokumen pada proses clustering dengan bisecting K-means.
Bisecting K-means Bisecting K-means merupakan algoritme HDC oleh karena itu dilakukan dengan pendekatan top-down. Pertama-tama seluruh kode program dimasukkan ke dalam satu cluster besar. Kemudian algoritme bisecting K-means dilanjutkan mengikuti langkah-langkah berikut (Steinbach et al. 2000): 1 Pilih cluster yang akan dipisah. 2 Temukan 2 sub-clusters dengan menggunakan algoritme K-means. (Tahap pemisahan) 3 Ulangi langkah 2 sebanyak ITER kali dan ambil pemisahan yang menghasilkan 2 sub-clusters terbaik. 4 Ulangi langkah 1, 2, dan 3 hingga didapat jumlah clusters yang diinginkan. Pemilihan cluster Pemilihan cluster yang akan dipisah dilakukan dengan melihat ukuran cluster. Cluster dengan anggota terbanyak akan menjadi kandidat utama cluster yang akan dipisah. Hal ini dikarenakan cluster dengan anggota terbanyak umumnya memiliki tingkat kemiripan anggota yang masih rendah. Apabila cluster kandidat utama ternyata telah memiliki anggota-anggota yang sama persis, dipilih cluster dengan jumlah anggota terbanyak kedua sebagai kandidat berikutnya.
7 K-means Tahap pemisahan pada algoritme bisecting K-means dilakukan dengan algoritme flat clustering K-means dengan K=2. Algoritme K-means yang digunakan pada penelitian ini adalah sebagai berikut: 1 Pilih K dokumen sebagai centroid awal. 2 Tempatkan setiap dokumen ke centroid yang terdekat. 3 Hitung ulang nilai centroid setiap cluster. 4 Ulangi langkah 2 dan 3 sampai nilai centroid-nya tidak berubah. Pemilihan 2 centroids awal pada penelitian ini dilakukan dengan cara pemilihan acak dan perhitungan jarak terjauh. Satu dokumen dipilih secara acak sebagai centroid pertama, kemudian jarak setiap dokumen ke centroid tersebut dihitung. Centroid kedua adalah dokumen dengan jarak terjauh dari centroid pertama. Penelitian ini menggunakan ukuran kesamaan kosinus sebagai pengukur jarak antar vektor dokumen. Kesamaan kosinus memiliki sifat semakin besar nilai persamaan kosinusnya, semakin dekat jarak kedua vektor, dan berarti semakin mirip kedua dokumen tersebut. Gambar 3 adalah ilustrasi dari ukuran kesamaan kosinus.
Gambar 3 Ilustrasi kesamaan kosinus Perhitungan jarak antara 2 dokumen d1 dan d2 adalah dengan menghitung kesamaan kosinus dari representasi vektor dokumen 𝑉 (d1) dan 𝑉 (d2). Vektor dokumen merupakan term frequency yang merepresentasikan jumlah term pada tiap dokumen. Kesamaan kosinus diformulasikan sebagai berikut: sim(d1,d2) =
V d1 ∙V d2 V d1
V d2
Pembilang menunjukkan perkalian dalam atau dot product antara 2 vektor 𝑉 (d1) dan 𝑉 (d2). Penyebut menunjukkan perkalian panjang jarak Euclid masing-masing vektor (Manning et al. 2008).
8 Perulangan pemisahan Tahap pemisahan pada bisecting K-means diulang sebanyak ITER kali. Hal ini bertujuan untuk mendapatkan clusters hasil K-means yang terbaik. Penelitian ini menggunakan nilai ITER=5 (Steinbach et al. 2000). Clusters hasil pemisahan terbaik ditentukan berdasakan nilai I-nya. Nilai I adalah rata-rata jarak setiap anggota clusters ke centroid cluster-nya. Nilai kesamaan kosinus antara centroid dan setiap dokumennya pada satu cluster dijumlahkan semua kemudian dibagi dengan banyaknya anggota pada cluster tersebut sehingga didapat nilai rata-rata internal cluster (𝑥a). Selanjutnya, nilai 𝑥a dari masing-masing cluster dijumlahkan semua dan dibagi dengan banyaknya cluster yang dihasilkan sehingga didapat nilai rata-rata akhir (I). Semakin besar nilai I, semakin dekat rata-rata jarak dokumen di masing-masing cluster dengan centroid cluster-nya dan berarti semakin baik hasil pemisahannya. Nilai I juga digunakan untuk menentukan kapan looping algoritme bisecting K-means akan berhenti. Penghentian looping Algoritme bisecting K-means akan melakukan looping terus menerus sampai tiap cluster hanya berisi satu dokumen atau tidak ada lagi cluster yang dapat dipisah. Pada pendeteksian penjiplakan hal ini tidak diharapkan. Cluster hasil yang hanya berisi satu atau sejumlah dokumen yang sama persis tidak dapat digunakan untuk mendeteksi penjiplakan kode program yang dimodifikasi. Oleh sebab itu diperlukan suatu parameter untuk menghentikan looping pada algoritme bisecting K-means saat clusters yang dihasilkan sudah cukup baik. Penelitian ini menggunakan nilai i sebagai parameter pemberhenti looping algoritme bisecting K-means. Apabila I > i maka looping dihentikan. I adalah ratarata jarak setiap anggota clusters ke centroid cluster-nya. Nilai i adalah bilangan desimal antara 0 sampai 1. Semakin besar nilai i, semakin dekat rata-rata jarak setiap dokumen dengan centroid-nya sebelum looping dihentikan. Secara umum, semakin besar nilai i maka semakin banyak looping yang dilakukan dan berarti semakin banyak jumlah clusters yang dihasilkan. Penentuan nilai i terbaik dilakukan dengan melakukan percobaan. Percobaan dilakukan dari nilai i=0.85 sampai i=1.00 dengan increment sebesar 0.01. Pada masing-masing nilai i tersebut dilakukan percobaan sebanyak 5 kali. Setiap percobaan i dicatat jumlah clusters, nilai akurasi Rand Index, nilai I, dan lama waktu eksekusinya.
Validasi Hasil Clustering Validasi hasil clustering dilakukan untuk mengukur seberapa baik hasil clustering yang didapat. Validasi dilakukan dengan membandingkan clusters hasil bisecting K-means dengan clusters hasil pengelompokan manual. Penelitian ini menggunakan pengukuran akurasi Rand Index (RI) untuk validasi hasil clustering. RI merepresentasikan hasil clustering sebagai kumpulan keputusan. Nilai akurasi RI adalah persentase dari keputusan-keputusan yang benar (Manning et al. 2008). Keputusan benar adalah apabila 2 dokumen yang mirip dikelompokkan ke
9 dalam cluster yang sama dan 2 dokumen yang berbeda dipisahkan ke cluster yang berbeda. Formula RI dituliskan sebagai berikut: RI =
TP +TN TP +FP+FN+TN
dengan RI : Rand index TP : true positive / keputusan 2 dokumen mirip berada di cluster yang sama FP : false positive / keputusan 2 dokumen berbeda berada di cluster yang sama TN : true negative / keputusan 2 dokumen berbeda berada di cluster yang berbeda FN : false negative / keputusan 2 dokumen mirip berada di cluster yang berbeda
Perbandingan dengan Penelitian Sebelumnya Hasil dari penelitian ini kemudian dibandingkan dengan hasil penelitian sebelumnya. Variabel yang dibandingkan antara lain jumlah clusters yang dihasilkan, ukuran akurasi hasil clustering-nya, dan lama waktu clustering. Selanjutnya berdasarkan hasil perbandingan tersebut, dapat dianalisis kelebihan dan kekurangan pendeteksian penjiplakan pada penelitian ini dibandingkan dengan penelitian sebelumnya.
Alat Perangkat keras: Processor Intel Core i3-2328M 2.20 GHz, Read Access Memory 2 GB, dan Hard disk 500 GB.
Perangkat lunak: Operating system Microsoft Windows 7 Professional 64-bit, Programming language PHP 5.3.8, PHP Integrated Development Environment Netbeans for PHP 7.1.2, Server control panel XAMPP 1.7.7, Database management system MySQL, C Integrated Development Environtment Dev-C++ 4.9.9.2, dan Web browser Mozilla Firefox 19.0.2.
10
HASIL DAN PEMBAHASAN Pengambilan dan Pemilihan Data Data yang digunakan pada penelitian ini adalah kode-kode program tugas pemrograman berbahasa C. Jumlah data sebanyak 233 kode program yang dipilih dari 3 tugas dengan kesulitan menengah. Masing-masing tugas tersebut kemudian dijadikan set data pada penelitian ini. Tabel 2 menunjukkan komposisi set data yang digunakan pada penelitian ini. Contoh kode program dari masing-masing set data penelitian ini dapat dilihat pada Lampiran 1. Tabel 2 Set data awal Set data DataSet1 DataSet2 DataSet3 DataSetAll
Jumlah dokumen 92 75 66 233
Pengelompokan Manual Pengelompokan manual dilakukan dengan memeriksa nilai output program dan struktur kode programnya. Khusus untuk DatSet1, penelitian ini menggunakan hasil pengelompokan manual yang sudah dilakukan oleh Gumilang (2013). Hasil pengelompokan manual untuk DatSet1 dapat dilihat pada Lampiran 2. Pemeriksaan nilai output kode program pada DataSet2 menghasilkan 5 clusters, sedangkan pada pemeriksaan DataSet3 menghasilkan 1 cluster. Setiap kode program pada masing-masing clusters tersebut kemudian dibandingkan strukturnya. Setelah dibandingkan, didapat DatSet2 menghasilkan 14 clusters kode program dan DataSet3 menghasilkan 12 clusters. Namun, dari semua clusters yang dihasilkan tersebut, terdapat clusters yang hanya berisi 1 atau 2 kode program. Clusters yang berisi terlalu sedikit dokumen tersebut kemudian dihilangkan. Tabel 3 menunjukkan set data setelah dilakukan pengelompokan manual. Hasil pengelompokan manual untuk DataSet2 dan DataSet3 dapat dilihat pada Lampiran 3 dan 4. Hasil pengelompokan manual untuk DataSetAll adalah 17 clusters gabungan hasil pengelompokan manual set data lainnya. Tabel 3 Set data setelah pengelompokan manual Set data DataSet1 DataSet2 DataSet3 DataSetAll
Jumlah dokumen 92 60 60 212
Clusters manual 9 2 6 17
11 Praproses Data Praproses data terbagi dalam beberapa tahapan, yaitu: pembuangan preprocessor directives, tokenisasi, penyederhanaan, dan N-gram. Pembuangan preprocessor directives dilakukan karena pada penelitian ini diasumsikan tidak adanya penggunaan makro pada kode program. Berikut contoh kode program dari DataSet1 yang telah dihilangkan preprocessor directives-nya: 1 2 main() 3 { 4 unsigned long int a,n=0; 5 long int b=0; 6 scanf("%lu", &a); //baca input 7 while ((pow(10,n++))<=a) 8 b+=1; 9 printf("%lu\n", b); //cetak hasil 10 return 0; 11 }
Proses tokenisasi dilakukan untuk mendapatkan keywords dan special characters kode program. Pada tahap ini dilakukan pembuangan whitespace, baris comments, karakter “;”, dan pengubahan huruf uppercase menjadi lowercase semua. Berikut contoh kode program setelah melalui proses tokenisasi: 1 2 3 4 5 6 7 8 9 10 11
main() { unsigned long int a,n=0 long int b=0 scanf("%lu", &a) while ((pow(10,n++))<=a) b+=1 printf("%lu\n", b) return 0 }
Selanjutnya dilakukan proses penyederhanaan dengan mengubah keywords dan special characters kode program menjadi deretan token sederhana yang merepresentasikan struktur kode program. Sebelum dilakukan pengubahan, dilakukan pengecekan dan penambahan spasi di awal dan akhir keywords atau special characters. Hal ini dilakukan untuk memastikan tidak terjadi kesalahan konversi karena adanya keywords atau special characters yang berhimpitan. Pengubahan yang dilakukan pada penelitian ini mengikuti tabel aturan konversi yang dapat dilihat pada Lampiran 5. Hasil dari proses penyederhanaan adalah string panjang token sederhana yang disebut token stream. Berikut contoh token stream hasil penyederhanaan kode program di atas: NhikHFANjNoNFANoNNh5jfNiKhhNhNjNaaiimoNiNaoNNh5jNiRNl
12 Setelah token stream didapat, kemudian dilakukan proses N-gram. Proses Ngram merupakan proses pembangkitan term dengan mengambil sejumlah N huruf dari suatu string panjang. Pada penelitian ini digunakan N=4. Berikut contoh Ngram yang dihasilkan dari token stream di atas: _Nhi Nhik hikH ikHF kHFA HFAN FANj ANjN
NjNo jNoN NoNF oNFA NFAN FANo AnoN NoNN
oNNh NNh5 Nh5j h5jf 5jfN jfNi fNiK NiKh
iKhh KhhN hhNh hNhN NhNj hNjN NjNa jNaa
Naai aaii aiim iimo imoN moNi oNiN NiNa
iNao NaoN aoNN oNNh NNh5 Nh5j h5jN 5jNi
jNiR NiRN iRNl RNl_
Selanjutnya dihitung jumlah kemunculan setiap N-gram pada masingmasing dokumen. Perhitungan jumlah kemunculan N-gram atau term dari masingmasing dokumen ini menghasilkan tabel term frequency. Tabel 4 merupakan contoh tabel term frequency dari N-gram di atas. Tabel term frequency kemudian digunakan untuk membentuk vektor-vektor dokumen pada proses clustering. Tabel 4 Term frequency Dok dok1 dok2 dok3 ...
_Nhi Nhik 1 1 1 1 1 1 ... ...
Term hikF ikHF kHFA HFAN FANj 1 1 1 1 1 1 0 0 2 1 1 1 1 3 2 ... ... ... ... ...
... ... ... ... ...
Bisecting K-means Proses clustering pada penelitian ini menggunakan algoritme bisecting Kmeans. Bisecting K-means merupakan algoritme hierarchical divisive clustering. Seluruh dokumen dimasukkan ke dalam satu cluster awal kemudian dipisah-pisah berdasarkan kemiripannya. Setiap pemisahan dilakukan dengan menggunakan Kmeans. Nilai i digunakan untuk menghentikan pemisahan pada saat clusters yang dihasilkan sudah cukup baik. Nilai i terbaik ditentukan dengan melakukan serangkaian percobaan clustering. Percobaan clustering dilakukan untuk setiap nilai i=0.85 sampai i=1.00 dengan increment sebesar 0.01. Percobaan dilakukan sebanyak 5 kali untuk setiap nilai i kemudian dihitung nilai rata-ratanya. Percobaan dilakukan untuk setiap set data yang terdapat pada Tabel 3. Hasil percobaan clustering untuk DataSet1, DataSet2, dan DataSet3 dapat dilihat pada Tabel 5, 6, dan 7.
13 Tabel 5 Hasil percobaan clustering untuk DataSet1 i 0.85 0.86 0.87 0.88 0.89 0.90 0.91 0.92 0.93 0.94 0.95 0.96 0.97 0.98 0.99 1.00
Clusters 3 3 3 3 3 5 6 7 7 10 13 15 19 22 29 35
RI 0.6819 0.6859 0.7389 0.7671 0.7226 0.8674 0.8708 0.9021 0.8956 0.9288 0.9372 0.9365 0.9420 0.9405 0.9435 0.9426
I 0.8921 0.8919 0.8993 0.8967 0.8981 0.9086 0.9136 0.9243 0.9340 0.9414 0.9535 0.9611 0.9716 0.9810 0.9906 1.0000
Waktu (detik) 3.5304 3.2341 3.9264 3.5387 3.6974 5.0295 5.4232 6.6771 5.7700 6.6439 7.2860 7.7758 8.2308 8.2383 8.2488 8.4299
Tabel 5 menunjukkan hasil percobaan clustering pada DataSet1. Berdasarkan hasil percobaan tersebut, dipilih nilai i=0.94. Nilai tersebut dipilih karena memiliki rata-rata RI yang sudah cukup baik, yaitu 0.9288, dan jumlah clusters yang tidak terlalu banyak, yaitu 10. Nilai i lebih besar dari 0.94 memiliki rata-rata RI yang sedikit lebih baik tetapi menghasilkan jumlah clusters yang lebih banyak. Jumlah clusters yang terlalu banyak memungkinkan adanya kode-kode program hasil penjiplakan yang awalnya sudah terkumpul dalam satu cluster, terpisah ke clusters yang berbeda. Tabel 6 Hasil percobaan clustering untuk DataSet2 i 0.85 0.86 0.87 0.88 0.89 0.90 0.91 0.92 0.93 0.94 0.95 0.96 0.97 0.98 0.99 1.00
Clusters 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3
RI 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 0.9711
I 0.9998 0.9998 0.9998 0.9998 0.9998 0.9998 0.9998 0.9998 0.9998 0.9998 0.9998 0.9998 0.9998 0.9998 0.9998 1.0000
Waktu (detik) 0.6698 0.5904 0.6001 0.5945 0.5930 0.6074 0.5994 0.6012 0.6024 0.5865 0.5927 0.6018 0.6080 0.5973 0.6090 0.8819
14
Tabel 6 menunjukkan hasil percobaan clustering pada DataSet2. Berdasarkan hasil percobaan tersebut, dapat dilihat bahwa saat clustering baru menghasilkan 2 clusters, nilai I dan RI yang didapat sudah sangat tinggi. Hal ini menandakan bahwa DataSet2 hanya terdiri atas 2 variasi kode program dengan tiap variasinya terdiri atas kode-kode program yang hampir sama persis. Dengan demikian, nilai i terbaik dipilih saat didapat RI=1.00 yaitu saat i kurang dari 1.00. Saat i=1.00, rata-rata RI yang dihasilkan, seperti yang terlihat pada Tabel 6, justru menurun. Hal ini mungkin terjadi karena adanya kode program hasil penjiplakan yang dimodifikasi sehingga memiliki struktur yang sedikit berbeda dari kode program aslinya. Semakin tinggi nilai i, semakin peka clustering terhadap perbedaan-perbedaan kecil pada struktur kode program. Hal ini yang menyebabkan dipisahkannya kembali kode-kode program yang sudah mirip sehingga jumlah clusters yang dihasilkan bertambah banyak dan ukuran RI yang didapat menurun. Tabel 7 Hasil percobaan clustering untuk DataSet3 i 0.85 0.86 0.87 0.88 0.89 0.90 0.91 0.92 0.93 0.94 0.95 0.96 0.97 0.98 0.99 1.00
Clusters 2 2 2 2 2 2 2 2 2 2 3 4 5 6 7 8
RI 0.4994 0.4994 0.4994 0.4994 0.4994 0.4994 0.4994 0.4994 0.4994 0.4994 0.8045 0.8508 0.9581 0.9790 0.9988 0.9954
I 0.9448 0.9448 0.9448 0.9448 0.9448 0.9448 0.9448 0.9448 0.9448 0.9448 0.9507 0.9662 0.9796 0.9839 0.9951 1.0000
Waktu (detik) 1.0281 1.0314 1.0232 1.0405 1.0372 1.0460 1.0192 1.0362 1.0314 1.0257 1.8363 2.3886 3.0212 3.4391 3.6306 3.7029
Tabel 7 menunjukkan hasil percobaan clustering pada DataSet3. Berdasarkan hasil percobaan tersebut dipilih nilai i=0.97. Nilai tersebut dipilih karena memiliki jumlah clusters yang tidak terlalu banyak, yaitu 5, dan rata-rata RI yang sudah cukup baik, yaitu 0.9581. Tabel 8 menunjukkan hasil percobaan clustering untuk DataSetAll. Berdasarkan hasil percobaan tersebut dipilih nilai i=0.96. Nilai tersebut dipilih karena memiliki jumlah clusters yang tidak terlalu banyak, yaitu 16, dengan waktu clustering yang tidak terlalu lama, yaitu 27.7442 detik. Rata-rata RI yang dihasilkan saat nilai i tersebut sudah cukup baik, yaitu 0.9743. Nilai i lebih besar dari 0.96 walau menghasilkan nilai RI yang sedikit lebih baik, tapi clusters yang dihasilkan jauh lebih banyak dan waktu eksekusi yang dibutuhkan lebih lama.
15 Tabel 8 Hasil percobaan clustering untuk DataSetAll i 0.85 0.86 0.87 0.88 0.89 0.90 0.91 0.92 0.93 0.94 0.95 0.96 0.97 0.98 0.99 1.00
Clusters 3 3 4 4 4 5 5 6 6 7 11 16 23 29 37 46
RI 0.7790 0.7790 0.8095 0.8079 0.8379 0.8822 0.8849 0.9008 0.9016 0.9079 0.9492 0.9743 0.9851 0.9869 0.9868 0.9866
I 0.8619 0.8619 0.8869 0.8813 0.8964 0.9125 0.9157 0.9283 0.9359 0.9431 0.9527 0.9619 0.9710 0.9810 0.9906 1.0000
Waktu (detik) 9.1299 9.3102 12.2412 11.8542 14.3293 15.6857 16.8122 17.3291 16.7830 17.7550 23.8100 27.7442 30.5931 32.1461 33.4861 35.0249
Tabel 9 menunjukkan nilai RI, jumlah clusters, jumlah dokumen, dan waktu eksekusi clustering masing-masing set data pada saat i terbaiknya. Berdasarkan Tabel 9, rata-rata nilai RI untuk setiap set data pada penelitian ini sudah cukup baik, yaitu lebih dari 90%. Tabel 9 Nilai RI, jumlah clusters, jumlah dokumen, dan waktu eksekusi clustering setiap set data Set Data DataSet1 DataSet2 DataSet3 DataSetAll
RI 0.9288 1.0000 0.9581 0.9743
Clusters 10 2 5 16
Dokumen 92 60 60 212
Waktu (detik) 6.6439 0.6090 3.0212 27.7442
Hasil clustering DataSet2 memiliki nilai RI=1.00 yang berarti clusters hasil pengelompokan bisecting K-means sama persis dengan clusters hasil pengelompokan manualnya. Waktu yang dibutuhkan untuk mendapatkan nilai RI tersebut juga sangat singkat. Hal ini dikarenakan DataSet2 hanya terdiri atas 2 clusters kode program yang masing-masing anggotanya hampir sama persis. Dengan demikian, proses clustering menjadi mudah dan cepat dilakukan. Tabel 9 juga menunjukkan lama waktu eksekusi clustering yang dibutuhkan tergantung dari banyaknya clusters yang dihasilkan. DataSetAll yang memiliki jumlah clusters terbanyak membutuhkan waktu terlama dibandingkan dengan set data lainnya. Banyaknya dokumen yang diproses tidak mempengaruhi waktu eksekusi secara signifikan. Hal ini dibuktikan dengan hasil clustering pada set data yang memiliki jumlah dokumen yang sama, yaitu DataSet2 dan DataSet3. DataSet2 yang hanya menghasilkan 2 clusters membutuhkan waktu eksekusi yang lebih singkat dibandingkan DataSet3 yang menghasilkan 6 clusters.
16 Validasi Hasil Clustering Validasi hasil clustering pada penelititan ini dilakukan dengan menggunakan ukuran akurasi RI. Hasil clustering untuk set data selain DataSet2 menghasilkan nilai RI kurang dari 1.00. Hal ini menunjukkan bahwa masih terdapat kesalahan pada hasil pendeteksian dengan menggunakan sistem. Kesalahan yang mungkin terjadi adalah dipisahkannya 2 kode program yang mirip ke clusters yang berbeda (false negative) dan dikelompokkannya 2 kode program yang berbeda ke cluster yang sama (false positive). Contoh pasangan dokumen false negative dan false positive pada DataSet1 saat i=0.94 ditunjukkan pada Gambar 4 dan 5. Gambar 4 menunjukkan contoh kesalahan false negative antara dokumen D42 dan D44. Kesalahan ini disebabkan oleh adanya perbedaan pada beberapa bagian kode program sehingga mempengaruhi token stream yang dihasilkan. Perbedaan-perbedaan ini, antara lain adanya tipe data long pada baris ke-5 dokumen D44 dan adanya perbedaan antara penggunaan operator increment ++b pada baris ke-7 dokumen D42 dengan b+=1 pada baris ke-8 dokumen D44. 1 #include <stdio.h> 2 main() { 3 unsigned long int a,n=0; 4 int b=0; 5 scanf("%lu", &a); 6 while ((pow(10,n++))<=a) 7 ++b; 8 printf("%d\n", b); 9 return 0; 10 } 11
1 2 3 4 5 6 7 8 9 10 11
#include <stdio.h> main() { unsigned long int a,n=0; long int b=0; scanf("%lu", &a); while ((pow(10,n++))<=a) b+=1; printf("%lu\n", b); return 0; }
Token stream dokumen D42: NhikHFANjNoNANoNNh5jfNiKhhNhNjNaaiimoNiaaNNh5jNiRNl Token stream dokumen D44: NhikHFANjNoNFANoNNh5jfNiKhhNhNjNaaiimoNiNaoNNh5jNiRNl Gambar 4 False negative dokumen D42 dan D44 pada DataSet1 Gambar 5 menunjukkan false positive antara dokumen D25 dan D44. Kedua kode program ini memiliki sejumlah perbedaan, antara lain adanya 2 tipe data yaitu int dan unsigned long int pada dokumen D59 dan adanya penggunaan operator kondisi if() pada dokumen D25. Namun, kedua kode program tersebut dikelompokkan ke dalam cluster yang sama oleh sistem. Hal ini dapat disebabkan oleh adanya beberapa bagian kode program yang mirip sehingga token stream yang dihasilkan juga masih memiliki banyak kemiripan. Kemiripan kedua kode program ini di antaranya sama-sama menggunakan fungsi while() sebagai fungsi looping-nya dan adanya statement yang sama, yaitu n/=10 pada kedua kode program.
17 1 2 3 4 5 6 7 8 9 10 11 12 13
#include <stdio.h> main() { long int n, x=0; scanf("%ld", &n); while (n>0) { if (n!=0) x += 1; n /= 10; } printf("%d", x); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13
#include<stdio.h> main() { int digit=0; unsigned long int n; scanf("%lu", &n); while(n>0){ digit++; n/=10; } printf("%d", digit); return 0; }
Token stream dokumen D25: NhikFANjNoNNh5jfNiKhNnNikIhNqoNiNaoNNdoNlNh5jNiRNl Token stream dokumen D59: NhikANoNHFANNh5jfNiKhNnNikNaaNdoNlNh5jNiRNl Gambar 5 False positive dokumen D25 dan D59 pada DataSet1
Perbandingan dengan Penelitian Sebelumnya Hasil penelitian ini dibandingkan dengan hasil pendeteksian penjiplakan kode program yang telah dilakukan oleh Gumilang (2013). Algoritme yang digunakan pada penelitian Gumilang adalah algoritme flat clustering K-means. Gumilang menggunakan iterasi K-means otomatis agar banyaknya clusters yang diinginkan tidak perlu ditentukan terlebih dahulu. Set data yang digunakan adalah DataSet1 yang berjumlah 92 kode progam. Variabel yang dibandingkan adalah rata-rata jumlah clusters, nilai RI, dan lama waktu eksekusi. Pertama-tama dilakukan perbandingan hasil clustering saat nilai i terbaik pada penelitian Gumilang. Hasil clustering terbaik pada penelitian Gumliang didapat saat nilai i=0.97. Tabel 10 menunjukkan perbandingan hasil clustering bisecting K-means dengan iterasi K-means pada saat nilai i=0.97. Tabel 10 Perbandingan hasil clustering bisecting K-means dengan iterasi K-means pada saat nilai i=0.97 Variabel Jumlah clusters Nilai RI Waktu eksekusi (detik)
Bisecting K-means 19 0.9420 8.2308
Iterasi K-means 12 0.9063 11.6826
Saat i=0.97 nilai RI yang dihasilkan oleh bisecting K-means lebih baik dibandingkan dengan iterasi K-means. Namun, jumlah clusters yang dihasilkan oleh bisecting K-means secara signifikan lebih banyak. Jumlah clusters yang banyak akan mempersulit pemeriksaan akhir yang nantinya dilakukan secara
18 manual oleh staf akademik dengan berpedoman pada hasil pendeteksian penjiplakan ini. Tabel 10 juga menunjukkan waktu eksekusi clustering yang dibutuhkan bisecting K-means lebih singkat dibandingkan dengan iterasi K-means walau jumlah clusters yang dihasilkannya lebih banyak. Hal ini menunjukkan bahwa algoritme bisecting K-means lebih efisien dibandingkan dengan iterasi Kmeans. Selanjutnya, hasil clustering saat nilai i terbaik pada penelitian ini dibandingkan dengan hasil clustering saat nilai i terbaik pada penelitian Gumilang. Pada penelitian Gumilang didapat hasil iterasi K-means terbaik adalah saat i=0.97, sedangkan pada penelitian ini, hasil clustering terbaik adalah saat i=0.94. Tabel 11 menunjukkan perbandingan hasil clustering bisecting K-means dengan iterasi Kmeans pada saat nilai i terbaik. Tabel 11 Perbandingan hasil clustering bisecting K-means dengan iterasi K-means pada saat nilai i terbaik Variabel Nilai i terbaik Jumlah clusters Nilai RI Waktu eksekusi (detik)
Bisecting K-means 0.94 10 0.9288 6.6439
Iterasi K-means 0.97 12 0.9063 11.6826
Berdasarkan Tabel 11 dapat dilihat bahwa bisecting K-means menghasilkan jumlah clusters yang lebih sedikit dan nilai RI yang lebih tinggi. Hal ini disebabkan oleh adanya pengulangan pemisahan sebanyak ITER kali pada algoritme bisecting K-means. Pengulangan pemisahan ini bertujuan untuk memperoleh clusters hasil pemisahan terbaik dari setiap looping algoritme bisecting K-means. Semakin baik clusters hasil pemisahan yang didapat maka semakin sedikit looping yang perlu dilakukan dan clusters yang dihasilkan menjadi lebih optimal baik jumlah maupun kualitasnya. Tabel 11 juga menunjukkan bahwa waktu eksekusi yang dibutuhkan oleh bisecting K-means lebih singkat dibandingkan dengan iterasi K-means. Hal ini disebabkan oleh adanya proses pemisahan clusters menjadi 2 sub-clusters pada setiap looping algoritme bisecting K-means. Proses pemisahan pada looping berikutnya selalu dilakukan pada sub-clusters hasil pemisahan sebelumnya. Hal ini menyebabkan jumlah dokumen yang dipisah pada suatu looping selalu lebih sedikit dibandingkan dengan jumlah dokumen pada looping sebelumnya. Semakin banyak looping yang dilakukan pada algoritme bisecting K-means, jumlah dokumen yang dipisah juga semakin sedikit. Selain itu, proses pemisahan pada setiap looping dilakukan menggunakan K-means dengan nilai K selalu 2. Pengelompokan K-means dengan nilai K yang kecil cenderung lebih mudah dan cepat dilakukan dibandingkan dengan pengelompokan K-means dengan nilai K yang lebih besar.
19 Rentang Nilai i Terbaik Pada penelitian ini, pengelompokan secara manual telah dilakukan sebelum proses clustering dengan bisecting K-means. Dengan demikian, validasi hasil clustering untuk mengukur sudah seberapa baik clusters yang dihasilkan dapat dilakukan dan nilai i terbaik untuk suatu set data dapat dengan mudah ditentukan. Namun, pada penggunaan sistem pendeteksian ini nantinya, pengguna tidak diharapkan untuk melakukan pengelompokan manual terlebih dahulu sehingga validasi hasil clustering tidak mungkin dilakukan. Hal ini menyebabkan penentuan nilai i terbaik akan lebih sulit dilakukan. Oleh sebab itu, pada bagian ini akan diusulkan rentang nilai i terbaik berdasarkan hasil percobaan-percobaan yang telah dilakukan. Tabel 12 menunjukkan nilai i terbaik untuk keempat set data yang digunakan pada penelitian ini. Tabel 12 Nilai i terbaik untuk setiap set data Set Data DataSet1 DataSet2 DataSet3 DataSetAll
i 0.94 0.85 – 0.99 0.97 0.96
Tabel 12 menunjukkan bahwa hasil clustering terbaik pada penelitian ini didapat saat i 0.94 hingga 0.97. Dengan demikian, rentang nilai i tersebut dapat digunakan dalam pendeteksian suatu set data baru dengan harapan dapat memberikan hasil clustering yang baik. Namun, Tabel 7 menunjukkan bahwa hasil percobaan clustering pada DataSet3 saat i=0.94 memiliki nilai RI yang masih terlalu rendah, yaitu 0.4994. Oleh sebab itu, nilai i=0.94 merupakan nilai yang belum aman untuk selalu menghasilkan clusters yang baik pada penelitian ini. Dengan demikian, pendeteksian terhadap set data baru yang belum diketahui hasil pengelompokan manualnya dapat dilakukan dengan menggunakan nilai i antara 0.95 sampai 0.97.
Pengaruh Ukuran N-gram terhadap Hasil Clustering Ukuran N-gram yang digunakan pada penelitian ini mengacu pada ukuran N-gram terbaik menurut Chawla (2003), yaitu N=4. Pada bagian akhir penelitian ini dilakukan percobaan clustering dengan menggunakan ukuran N-gram kurang dan lebih dari 4 untuk melihat pengaruhnya terhadap hasil pendeteksian pada penelitian ini. Tabel 13 menunjukkan hasil percobaan clustering dengan ukuran 2-gram hingga 6-gram pada setiap set data saat i=0.95. Tabel 13 menunjukkan bahwa ukuran N-gram yang terlalu kecil menghasilkan nilai RI yang rendah. Semakin besar nilai N, maka clusters yang dihasilkan cenderung semakin baik. Namun, semakin besar nilai N, jumlah clusters yang dihasilkan juga cenderung semakin banyak dan waktu eksekusi yang dibutuhkan semakin lama.
20 Tabel 13 Hasil percobaan clustering dengan 2-gram hingga 6-gram untuk setiap set data 2 Clusters RI Waktu (detik)
2 0.38614 0.66538
Clusters RI Waktu (detik)
2 1.00000 0.45738
Clusters RI Waktu (detik)
2 0.65898 0.52038
Clusters RI Waktu (detik)
3 0.77908 2.91646
Ukuran N-gram 3 4 5 DataSet1 6 13 16 0.88303 0.93401 0.93511 3.31638 7.29670 9.64294 DataSet2 2 2 2 1.00000 1.00000 1.00000 0.61758 0.62552 0.70988 DataSet3 2 3 5 0.49943 0.80452 0.98022 0.82234 1.97462 4.13240 DataSetAll 6 11 20 0.89953 0.95568 0.98388 8.88326 23.89546 41.72346
6 17 0.93784 13.69878 2 1.00000 0.77162 4 0.82429 4.20660 21 0.98577 60.54178
Terdapat beberapa pengecualian yang juga ditunjukkan pada Tabel 13. Hasil clustering DataSet2 yang hanya terdiri atas 2 jenis kode program yang homogen tidak terpengaruh dengan berbagai ukuran N-gram yang dicobakan. Selain itu, DataSet3 memiliki nilai RI lebih rendah saat N=6 dibandingkan saat N=5. Hal ini menunjukkan peningkatan nilai N tidak selalu menghasilkan kualitas clusters yang lebih baik. Dengan demikian, N=4 merupakan ukuran N-gram yang paling sesuai pada penelitian ini karena memberikan hasil clustering yang baik dan waktu eksekusi yang tidak terlalu lama.
SIMPULAN DAN SARAN Simpulan Algoritme HDC bisecting K-means dan structure-oriented code-based system dapat diimplementasikan untuk mendeteksi penjiplakan kode program C. Hasil dari pendeteksian ini cukup baik dengan clusters yang dihasilkan memiliki rata-rata akurasi RI lebih dari 90%. Pendeteksian dengan bisecting K-means dapat melakukan pengelompokan kode program dalam waktu yang secara signifikan lebih cepat dibandingkan pendeteksian dengan iterasi K-means otomatis. Pendeteksian pada penelitian ini juga dapat menghasilkan jumlah clusters yang lebih sedikit dengan akurasi RI yang lebih tinggi dibandingkan dengan hasil pendeteksian dengan iterasi K-means otomatis. N=4 merupakan ukuran N-gram terbaik pada penelitian ini karena memberikan hasil clustering yang seimbang antara kualitas clusters dan waktu eksekusinya.
21 Saran Pendeteksian penjiplakan pada penelitian ini dilakukan hanya berorientasikan pada struktur kode program. Hal ini dapat menyebabkan terjadinya kesalahan pada pendeteksian apabila dilakukan modifikasi yang mengubah struktur kode program tanpa mengubah nilai keluarannya. Hal ini dapat diatasi pada penelitian selanjutnya dengan juga memperhatikan faktor semantik kode program pada saat pendeteksian. Pemeriksaan faktor semantik ini dapat dilakukan dengan mengecek nilai keluaran kode program terlebih dahulu sebelum dilakukan proses clustering. Saran lainnya adalah menggunakan algoritme hierarchical agglomerative clustering dalam pendeteksian untuk mengakomodasi adanya kode program baru yang ingin dimasukkan dalam hasil clustering tanpa perlu melakukan clustering ulang kode-kode program lainnya. Selain itu, disarankan untuk menambah korpus kode program sehingga pendeteksian dapat diujikan pada berbagai macam kompleksitas kode program.
DAFTAR PUSTAKA Bowyer K, Hall L. Experience using MOSS to detect cheating on programming assignments. Di dalam: 29th ASEE/IEEE Frontiers in Education Conference: 1999 Nov 10-13; San Juan, Puerto Rico. Champaign (US): Stipes Publishing LLC. hlm 18-22. Burrow S. 2004. Efficient and effective plagiarism detection for large code repositories [tesis]. Melbourne (AU): RMIT University. Cavnar WB, Trenkle JM. 1994. N-Gram-Based Text Categorization. Ann Arbor (US): Environmental Research Institute of Michigan. Chawla M. 2003. An indexing technique for efficiently detecting plagiarism in large volume of source code [tesis]. Melbourne (AU): RMIT University. Gitchel D, Tran N. Sim. A utility for detecting similarity in computer programs. Di dalam: 30th SIGCSE Technical Symposium: 1999 Mar 14-28; New Orleans, Louisiana. New York (US): ACM. hlm 266-270. Gumilang AP. 2013. Pendeteksian penjiplakan kode program C dengan K-means [skripsi]. Bogor (ID): Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Manning CD, Raghavan P, Schütze H. 2008. An Introduction to Information Retrieval. Cambridge (UK): Cambridge University Press. Prechelt L, Malpohl G, Philippsen M. 2002. Finding plagiarisms among a set of programs with JPlag. Universal Computer Science. 8(11):1016–1038. Steinbach M, Karypis G, Kumar V. 2000. A comparison of document clustering techniques [laporan teknis]. Minneapolis (US): Department of Computer Science and Engineering. University of Minnesota. No laporan: 00-0034.
22 Lampiran 1 Contoh kode program dari masing-masing set data yang digunakan dalam penelitian DataSet1 1 2 3 4 5 6 7 8 9 10 11
#include <stdio.h> main() { unsigned long int a,n=0; long int b=0; scanf("%lu", &a); //baca input while ((pow(10,n++))<=a) b+=1; printf("%lu\n", b); //cetak hasil return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
#include <stdio.h> #define size 100000 main() { unsigned long int a,b,g,f,j,d,i,n[size],k,z[size]; scanf("%lu",&a); for(i=1;i<=a;i++) { scanf("%lu",&b); n[i] = b + n[(i-1)]; } scanf("%lu",&d); for(j=1;j<=d;j++) { k=0; scanf("%lu",&g); for (f=1;k<1;f++) { if (((g/n[f])==0) || (((g%n[f])==0)) && ((g/n[f])== 1)) {z[j]=f;k=1;} } } for(i=1;i<=d;i++) { printf("%lu\n",z[i]); } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14
#include <stdio.h> main() { unsigned long int a,b,c,i,x,y,z; scanf("%lu %lu",&a,&x); scanf("%lu %lu",&b,&y); c=(a*y)+(b*x); z=x*y; for(i=2;(i<=c)||(i<=z);i++) { if((c%i==0)&&(z%i==0)) } {c/=i;z/=i;i=1;} printf("%d %d",c,z); return 0; }
DataSet2
DataSet3
23 Lampiran 2 Hasil pengelompokan manual untuk DataSet1 1 D13 D16 D17 D22 D23 D24 D26 D27 D30 D32 D33 D36 D37 D42 D44 D45 D46 D48 D51 D61 D62 D65 D70 D74 D79 D80 D81 D82 D85 D89
2 D1 D60 D68 D86 D87 D90 D91
3 D2 D4 D11 D14 D15 D21 D29 D31 D35 D43 D49 D52 D55 D57 D67 D73 D83
4 D3 D5 D7 D8 D10 D47 D53 D56 D78 D84
5 D6 D18 D28 D39 D58 D64 D69 D72
6 D9 D12 D34 D38 D40
7 D19 D41 D54 D63
8 D25 D50
9 D20 D59 D66 D71 D75 D76 D77 D88 D92
24 Lampiran 3 Hasil pengelompokan manual untuk DataSet2 1 D1 D2 D3 D4 D6 D7 D8 D9 D10 D11 D12 D13 D14 D15 D16 D17 D18 D19 D20 D21 D22 D23 D24 D26 D27 D28 D29 D30
D32 D33 D34 D35 D37 D38 D39 D41 D42 D43 D44 D45 D46 D47 D48 D49 D50 D51 D53 D54 D55 D57 D58 D59
2 D5 D25 D31 D36 D40 D52 D56 D60
25 Lampiran 4 Hasil pengelompokan manual untuk DataSet3 1 D1 D27 D59
2 D2 D12 D24 D29 D39 D49 D56
3 D3 D4 D10 D11 D13 D14 D16 D18 D19 D20 D21 D22 D23 D25 D26 D28 D30 D31 D32 D34 D36 D37 D38 D40 D42 D43 D46 D47 D48 D50 D51 D52 D53 D55 D58 D60 D61
4 D6 D7 D8 D15 D44
5 D9 D17 D41 D54 D57
6 D33 D35 D45
26 Lampiran 5 Tabel aturan konversi kode program menjadi token sederhana Keyword / special character + * / % & | ( ) , { } < > = . ! : int float char double
Token sederhana a b c d e f g h i j k l m n o p q r A B C D
Keyword / special character short long signed unsigned if else while do for ALPHANUM goto case break return switch const continue sizeof struct enum typedef "STRING"
Token sederhana E F G H I J K L M N O P Q R S T U W X Y Z 5
27
RIWAYAT HIDUP Penulis dilahirkan di Jakarta pada tanggal 27 November 1989, merupakan anak kedua dari Bapak Listyo Sumitro dan Ibu Diah Aryati. Pada Tahun 2002 sampai 2004 penulis menempuh pendidikan sekolah menengah pertama di SMP Negeri 19 Jakarta. Kemudian penulis melanjutkan pendidikannya di SMA Negeri 6 Jakarta pada tahun 2004 sampai 2007. Lulus dari sekolah menengah atas, penulis diterima di Departemen Ilmu Komputer Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor melalui jalur Undangan Seleksi Masuk IPB (USMI) pada tahun 2007.
