PENGELOMPOKAN KODE PROGRAM C BERDASARKAN KEMIRIPAN STRUKTUR MENGGUNAKAN METODE HIERARCHICAL AGGLOMERATIVE CLUSTERING
RUSMAN TRIATMOJO
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2014
PERNYATAAN MENGENAI SKRIPSI DAN SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA Dengan ini saya menyatakan bahwa skripsi berjudul Pengelompokan Kode Program C Berdasarkan Kemiripan Struktur Menggunakan Metode Hierarchical Agglomerative Clustering adalah benar karya saya dengan arahan 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, Agustus 2014 Rusman Triatmojo NIM G64100090
ABSTRAK RUSMAN TRIATMOJO. Pengelompokan Kode Program C Berdasarkan Kemiripan Struktur Menggunakan Metode Hierarchical Agglomerative Clustering. Dibimbing oleh AHMAD RIDHA. Tujuan penelitian ini adalah mengimplementasikan algoritme hierarchical agglomerative clustering untuk membantu pendeteksian penjiplakan pada kode program C secara otomatis dan membandingkan hasil penelitian dengan penelitian sebelumnya menggunakan metode iterasi K-means otomatis dan bisecting Kmeans. Data yang digunakan dalam penelitian ini sebanyak 386 kode program C yang terdiri atas 4 dataset. Metode yang digunakan Single Linkage, Complete Linkage, dan Average Linkage. Hasil clustering yang dilakukan menunjukkan eksekusi waktu metode Single Linkage sebesar 1.7220 detik dengan jumlah cluster 14 dan RI sebesar 0.9706, eksekusi waktu metode Complete Linkage sebesar 1.7500 detik dengan jumlah cluster 10 dan RI sebesar 0.8560, dan eksekusi waktu metode Average Linkage sebesar 1.7400 detik dengan jumlah cluster 14 dan RI sebesar 0.9546. Hasil penelitian ini menunjukkan adanya perbaikan waktu eksekusi clustering dari penelitian sebelumnya yang menggunakan metode iterasi K-means sebesar 8.41 detik dan metode bisecting K-means sebesar 4.69 detik. Katakunci : Hierarchical clustering, Kode Program C, Pendeteksi penjiplakan.
ABSTRACT RUSMAN TRIATMOJO. Grouping of C Programs Based on Structure Similarity Using Hierarchical Agglomerative Clustering. Supervised by AHMAD RIDHA. The purpose of this research is to implement the agglomerative hierarchical clustering algorithm to assist plagiarism detection in C program code automatically and compare this research’s results with previous research using Kmeans automatic iteration and bisecting K-means method. The data used in this research are 386 C programs comprised of 4 datasets. The method used are Single Linkage, Complete Linkage, and Average Linkage. The results show that the execution time of Single Linkage method is 1.7440 seconds with 14 clusters found and 0.9706 of RI, the execution time of Complete Linkage method is 1.7240 seconds with 10 clusters found and 0.8576 of RI, and the execution time of Average Linkage method is 1.7340 seconds with 14 clusters found and 0.9546 of RI. The results of this research show an improved execution time of clustering from previous research using K-means automatic iteration method (11.68 seconds) and bisecting K-means method (6.64 seconds).
Keywords : C code program, Detect Plagiarism, Hierarchical clustering.
PENGELOMPOKAN KODE PROGRAM C BERDASARKAN KEMIRIPAN STRUKTUR MENGGUNAKAN METODE HIERARCHICAL AGGLOMERATIVE CLUSTERING
RUSMAN TRIATMOJO
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 2014
Penguji : 1 Aziz Kustiyo, SSi MKom 2 Dr Imas S Sitanggang, SSi MKom
Judul Skripsi : Pengelompokan Kode Program C Berdasarkan Kemiripan Struktur Menggunakan Metode Hierarchical Agglomerative Clustering Nama : Rusman Triatmojo NIM : G64100090
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 kepada Allah Subhanahu Wa Ta’ala atas segala limpahan rahmat dan karunia-Nya sehingga karya ilmiah berjudul Pengelompokan Kode Program C Berdasarkan Kemiripan Struktur Menggunakan Metode Hierarchical Agglomerative Clustering ini dapat penulis selesaikan. Shalawat dan salam tak lupa penulis curahkan kepada Nabi Besar Muhammad Shallallahu 'Alaihi Wasallam beserta seluruh keluarga, sahabat, dan para pengikutnya sampai akhir zaman. Terima kasih penulis ucapkan kepada Bapak Ahmad Ridha, SKom MS selaku pembimbing yang telah banyak memberikan arahan dalam penyusunan skripsi ini, dan terima kasih kepada Bapak Aziz Kustiyo, SSi MKom dan Ibu Dr Imas S Sitanggang, SSi MKom selaku penguji. Selain itu, ungkapan terima kasih juga penulis sampaikan kepada teman-teman yang telah memberikan saran, motivasi, dan dukungan bagi kelancaran penyusunan skripsi ini. Tak lupa pula ungkapan terima kasih penulis sampaikan kepada ayah, ibu, serta seluruh keluarga, atas segala doa dan kasih sayangnya. Semoga skripsi ini bermanfaat.
Bogor, Agustus 2014
Rusman Triatmojo
DAFTAR ISI DAFTAR TABEL
viii
DAFTAR GAMBAR
viii
PENDAHULUAN
1
Latar Belakang
1
Perumusan Masalah
2
Tujuan Penelitian
2
Manfaat Penelitian
2
Ruang Lingkup Penelitian
2
METODE PENELITIAN
2
Pengambilan Data Penelitian
2
Pemilihan Sampel Tugas dan Pengelompokan Awal
3
Praproses data
3
Clustering
5
Penghentian Looping
6
Validasi Hasil Clustering
6
Perbandingan dengan Penelitian Sebelumnya
6
Lingkungan Implementasi
7
HASIL DAN PEMBAHASAN
7
Pengambilan dan Pemilihan Data
7
Pengelompokan Manual
7
Praproses Data
8
Hierarchical Agglomerative Clustering
9
Validasi Hasil Clustering
11
Perbandingan dengan Penelitian Sebelumnya
12
SIMPULAN DAN SARAN
13
Simpulan
13
Saran
13
DAFTAR PUSTAKA
13
RIWAYAT HIDUP
27
DAFTAR TABEL 1 2 3 4 5 6
Beberapa hasil konversi term dari kode program (Burrows 2004) Term frequency Set data awal Set data setelah pengelompokan manual Hasil percobaan Single Linkage clustering untuk DataSet1 Nilai RI, jumlah cluster, jumlah dokumen, dan waktu eksekusi clustering setiap set data percobaan Single Linkage clustering 7 Hasil percobaan Complete Linkage clustering untuk DataSet1 8 Nilai RI, jumlah cluster, jumlah dokumen, dan waktu eksekusi clustering setiap set data percobaan Complete Linkage clustering 9 Hasil percobaan Average Linkage clustering untuk DataSet1 10 Nilai RI, jumlah cluster, jumlah dokumen, dan waktu eksekusi clustering setiap set data percobaan Average Linkage clustering 11 Perbandingan hasil clustering pada saat nilai i terbaik dengan penelitian sebelumnya
4 5 7 8 9 9 10 10 10 11 12
DAFTAR GAMBAR 1 2 3 4 5
Tahapan praproses sebelum clustering Ilustrasi dari ukuran kesamaan kosinus Contoh program sebelum dilakukan tokenisasi Contoh program setelah dilakukan tokenisasi False positive dokumen D58 dan D59 pada DataSet2
3 5 8 8 11
DAFTAR LAMPIRAN 1 Tabel aturan konversi kode program menjadi token sederhana (Burrows 2004) 2 Hasil pengelompokan manual untuk DataSet1 3 Hasil pengelompokan manual untuk DataSet3 4 Hasil pengelompokan manual untuk DataSet4 5 Hasil pengelompokan manual untuk DataSet1 6 Tabel Hasil percobaan Single Linkage clustering untuk DataSet1 7 Hasil percobaan Single Linkage clustering untuk DataSet2 8 Hasil percobaan Single Linkage clustering untuk DataSet3 9 Hasil percobaan Single Linkage clustering untuk DataSet4 10 Hasil percobaan Single Linkage clustering untuk DataSetAll 11 Hasil percobaan Complete Linkage clustering untuk DataSet1 12 Hasil percobaan Complete Linkage clustering untuk DataSet2 13 Hasil percobaan Complete Linkage clustering untuk DataSet3 14 Hasil percobaan Complete Linkage clustering untuk DataSet4 15 Hasil percobaan Complete Linkage clustering untuk DataSetAll 16 Hasil percobaan Average Linkage clustering untuk DataSet1 17 Hasil percobaan Average Linkage clustering untuk DataSet2 18 Hasil percobaan Average Linkage clustering untuk DataSet3 19 Hasil percobaan Average Linkage clustering untuk DataSet4 20 Hasil percobaan Average Linkage clustering untuk DataSetAll
14 15 16 17 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26
PENDAHULUAN Latar Belakang Mata kuliah pemrograman komputer biasanya akan memberikan tugas kepada mahasiswanya untuk melatih kemampuan pemrograman. Tugas pemrograman yang diberikan umumnya berupa berkas elektronik. Tugas ini biasanya sangat rentan sekali dengan terjadinya penjiplakan yang dilakukan oleh mahasiswa. Penjiplakan yang dilakukan dapat bermacam-macam cara, misalnya mengubah variabel yang ada. Untuk memeriksa terjadinya penjiplakan dilakukan pemeriksaan kesamaan dari program yang dibuat. Namun pemeriksaan yang dilakukan secara manual akan memakan waktu lama dan melelahkan. Oleh karena itu proses pendeteksian secara cepat dan tepat sangatlah dibutuhkan. Pemeriksaan kemiripan kode program yang dilakukan oleh Burrows (2004) ialah dengan cara mencari kode program dari query yang diberikan dan menghitung kemiripannya. Sistem yang digunakan oleh Burrows adalah structure-oriented code-based system. Sistem berbasis kode dengan berorientasikan pada struktur kode program ini membuat representasi yang lebih ringkas dari kode program. Penelitian mengenai pendeteksian penjiplakan kode program C sebelumnya dilakukan oleh Gumilang (2013) dan Notyasa (2013), keduanya mengadopsi aturan penyederhanaan yang dilakukan Burrows (2004). Gumilang (2013) dan Notyasa (2013) keduanya menerapkan pengelompokan berdasarkan kesamaan strukturnya. Penelitian yang dilakukan Gumilang (2013) mengelompokkan kode program secara otomatis dengan 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 cluster 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 centroid yang semakin bertambah. Sedangkan penelitian yang dilakukan Notyasa (2013) dengan hierarchical divisive clustering. Algoritme hierarchical divisive clustering yang digunakan adalah bisecting Kmeans. Bisecting K-means adalah algoritme hierarchical divisive clustering yang menggunakan K-means untuk pemisahan setiap cluster-nya. Pengelompokan kode program pada penelitian ini menggunakan tehnik pengelompokan dalam kategori Hierarchical Agglomerative Clustering yaitu metode Single Linkage, Complete Linkage, dan Average Linkage. Pemodelan Single Linkage dapat digunakan untuk mengelompokkan dokumen yang didasarkan pada jarak terkecil. Jika dua dokumen terpisah oleh jarak yang pendek maka kedua dokumen tersebut akan digabung menjadi satu cluster dan demikian seterusnya. Pemodelan Complete Linkage dapat digunakan untuk mengelompokkan dokumen yang didasarkan pada jarak terbesar. Jika dua dokumen terpisah oleh jarak yang besar maka kedua dokumen tersebut akan digabung menjadi satu cluster dan demikian seterusnya. Pemodelan Average Linkage dapat digunakan untuk mengelompokkan dokumen yang didasarkan pada jarak rata-rata.
2
Perumusan Masalah Berdasarkan latar belakang yang telah dijelaskan, dapat disimpulkan bahwa: 1 Bagaimana mengimplementasikan algoritme hierarchical agglomerative clustering dalam pendeteksian penjiplakan kode program C. 2 Apakah pengelompokan kode-kode program dengan menggunakan hierarchical agglomerative clustering membutuhkan waktu eksekusi yang lebih singkat dibandingkan dengan iterasi K-means otomatis dan bisecting Kmeans. 3 Apakah hierarchical agglomerative clustering dapat menghasilkan cluster yang lebih baik dibandingkan dengan iterasi K-means otomatis dan bisecting K-means. Tujuan Penelitian Tujuan dari penelitian ini ialah mengimplementasikan algoritme hierarchical agglomerative clustering untuk membantu pendeteksian penjiplakan pada kode program C secara otomatis. Manfaat Penelitian Hasil dari penelitian ini diharapkan dapat memudahkan pemeriksaan penjiplakan kode program C, sehingga proses pemeriksaan menjadi lebih cepat dan efisien. Ruang Lingkup Penelitian 1 Data yang digunakan adalah 386 buah kode program tugas pemrograman berbahasa C yang didapat dari data penelitian sebelumnya yang dilakukan oleh Gumilang (2013) dan Notyasa (2013) 2 Penelitian ini mengasumsikan tidak adanya makro sehingga bagian preprocessor directives dibuang semua.
METODE PENELITIAN Secara umum terdapat 6 tahapan penelitian, yaitu pengambilan data penelitian, pemilihan sampel tugas dan pengelompokan manual, praproses data, clustering,validasi hasil, dan perbandingan dengan penelitian sebelumnya. Pengambilan Data Penelitian Tahap awal penelitian dimulai dengan pengambilan data, data yang digunakan dalam penelitian ini adalah data penelitian sebelumnya yang dilakukan oleh Gumilang (2013) dan Notyasa (2013) yang diperoleh dari mata kuliah algoritme dan pemrograman Program Studi S1 Ilmu Komputer. Data penelitian ini adalah kumpulan berkas elektronik tugas pemrograman yang berisi kode program bahasa C.
3 Pemilihan Sampel Tugas dan Pengelompokan Awal Pada tahap ini dilakukan pemilihan sampel tugas dan pengelompokan tugas secara manual. Sampel yang dipilih pada penelitian ini memiliki tingkat kesulitan tidak terlalu mudah dan tidak terlalu sulit. 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. Sampel yang dipilih sebanyak 92 kode program. Sampel diperiksa satu per satu dan dikelompokkan berdasarkan kemiripan algoritme dan struktur kode programnya. Pengelompokan awal ini untuk dasar sebagai perbandingan dalam validasi clustering. Praproses data Praproses data dilakukan untuk mengubah data mentah kode program C ke dalam format yang dapat diproses ke dalam tahapan clustering, hasil praproses data yaitu berupa term frequency. Tahapan-tahapan dalam praproses dapat dilihat pada Gambar 1.
Kumpulan program Tabel term frequency
Pembuangan preprocessor directives
Pembentukan N-gram
Tokenisasi
Konversi Token
Gambar 1 Tahapan praproses sebelum clustering 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. Konversi Token Selanjutnya pada proses konversi token, 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). Beberapa
4 konversi kode program menjadi token sederhana dilakukan berdasarkan aturan konversi seperti pada Tabel 1. Aturan konversi kode program menjadi token sederhana lebih lengkapnya dapat dilihat pada Lampiran 1. Tabel 1 Beberapa hasil konversi term dari kode program (Burrows 2004) Term
Int Main For Return ( ) {
Token sederhana A N M R H I K
Term } = < + , ALPHANUM STRING
Token sederhana L O M A J N 5
Tabel 1 memperlihatkan perubahan penulisan kode menjadi token sederhana. ALPHANUM adalah nama fungsi nama variabel atau nilai variabel. STRING adalah sederetan karakter yang diapit oleh tanda petik (“ ”). Berikut adalah contoh kode program yang diubah menjadi token stream: #include <stdio.h> int main (){ int var; for (var=0; var<5; printf("%d\n", var); var++){ } return 0; } Tokenstream: ANhikANMhNoNNmNNaaikNh5jNilRNl N-gram Tahap selanjutnya adalah proses N-gram. Pada penelitian ini metode Ngram digunakan untuk mengambil potongan-potongan karakter huruf sejumlah N dari suatu token stream. N-gram adalah potongan sejumlah N karakter dari sebuah string. N-gram merupakan sebuah metode yang diaplikasikan untuk pembangkitan kata atau karakter. Cavnar dan Trenkle (1994) menyatakan N-Gram dibedakan berdasarkan jumlah potongan karakter sebesar N. Untuk membantu dalam mengambil potongan-potongan kata berupa karakter huruf tersebut, dilakukan padding dengan blank karakter di awal dan di akhir suatu kata. Nilai N yang digunakan pada penelitian ini adalah nilai N terbaik untuk pendeteksian penjiplakan kode program, yaitu N=4 (Chawla 2003 dalam Burrows 2004). Kemudian kemunculan tiap substring dihitung sehingga didapat tabel term frequency. Tabel 2 merupakan contoh tabel term frequency dari N-gram. Tabel ini digunakan sebagai vektor dokumen untuk proses pengelompokan pada pemodelan single linkage, complete linkage, dan average linkage.
5 Tabel 2 Term frequency Dok
Term
_Nhi Nhik hikF ikHF kHFA HFAN FANj ... dok1 1 1 1 1 1 1 1 ... dok2 1 1 1 0 0 2 1 ... dok3 1 1 1 1 1 3 2 ... ... ... ... ... ... ... ... ... ... Clustering Proses pengelompokan sekumpulan objek ke dalam kelas-kelas yang objekobjeknya serupa disebut clutering. Objek-objek dalam sebuah cluster mirip satu sama lain dan berbeda dengan objek-objek dalam cluster lain (Han & Kamber 2006). Agglomerative secara rekursif menggabungkan sepasang titik yang memiliki paling banyak kesamaan ke dalam satu cluster sehingga berbentuk herarkikal. (Jain 2009). Terdapat beberapa skema yang dapat digunakan dalam penghitungan jarak yang dilakukan pada AHC, yaitu single link, complete link, centroid link, dan average link (Lance 1967). Single link adalah proses clustering yang didasarkan pada jarak terdekat antar-objeknya (minimum distance) (Lance 1967). Complete link adalah proses clustering yang didasarkan pada jarak terjauh dari data antar-kelompok (maximum distance) (Lance 1967). Average link adalah proses clustering yang didasarkan pada jarak rata-rata antar-obyek (average distance) (Lance 1967). 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 2 adalah ilustrasi dari ukuran kesamaan kosinus.
Gambar 2 Ilustrasi dari ukuran kesamaan kosinus Perhitungan standar kesamaan antara dua 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: ⃗ ⃗ |⃗
|| ⃗
|
6 Pembilang menunjukkan perkalian dalam atau dot product antara dua vector, ⃗ (d1) dan ⃗ (d2). Penyebut menunjukkan perkalian panjang jarak Euclid masingmasing vektor (Manning et al. 2008). Penghentian Looping Penelitian ini menggunakan nilai i sebagai parameter pemberhenti looping algoritme hierarchical agglomerative clustering. Apabila I < i maka looping dihentikan. I adalah jarak setiap dokumen. Nilai i adalah bilangan desimal antara 0 sampai 1. Penentuan nilai i terbaik dilakukan dengan melakukan percobaan. Nilai i yang diambil karena memiliki RI yang cukup baik dan memiliki banyak cluster yang mendekati hasil pengelompokan manual. Percobaan dilakukan dari nilai i=0.80 sampai i=1.00 dengan increment sebesar 0.01. Setiap percobaan i dicatat jumlah cluster, nilai akurasi Rand Index, nilai I, dan lama waktu eksekusinya. Validasi Hasil Clustering Validasi dari hasil clustering dilakukan pada tahap ini. Validasi clustering dilakukan dengan menggunakan perhitungan akurasi Rand Index (RI). RI menghitung persentase keputusan yang benar (Manning et al. 2008). Tujuannya adalah memasukkan dua dokumen ke dalam satu cluster yang sama jika dan hanya jika keduanya mirip. Formula RI ditunjukkan sebagai berikut: T T
T T
dengan RI : Rand index TP : true positive / keputusan 2 dokumen mirip berada di cluster yang sama, yang dibandingkan adalah hasil dari cluster manual dengan cluster yang dibuat oleh sistem. FP : false positive / keputusan 2 dokumen berbeda berada di cluster yang sama, yang dibandingkan adalah hasil dari cluster manual dengan cluster yang dibuat oleh sistem. TN : true negative / keputusan 2 dokumen berbeda berada di cluster yang berbeda, yang dibandingkan adalah hasil dari cluster manual dengan cluster yang dibuat oleh sistem. FN : false negative / keputusan 2 dokumen mirip berada di cluster yang berbeda, yang dibandingkan adalah hasil dari cluster manual dengan cluster yang dibuat oleh sistem. Perbandingan dengan Penelitian Sebelumnya Hasil dari penelitian ini kemudian dibandingkan dengan hasil penelitian sebelumnya dengan menggunakan data dari penelitian Gumilang (2013). Variabel yang dibandingkan antara lain jumlah cluster yang dihasilkan, ukuran akurasi hasil clustering-nya, dan lama waktu clustering. Selanjutnya berdasarkan hasil
7 perbandingan tersebut, dapat dianalisis kelebihan dan kekurangan penelitian ini dibandingkan dengan penelitian sebelumnya. Lingkungan Implementasi Lingkungan implementasi perangkat keras yang digunakan pada penelitian ini berupa desktop dengan spesifikasi sebagai berikut: Processor Memory Harddisk
: Intel Core i5 @2.30GHz : 4.00 GB : 640GB
Perangkat lunak yang termasuk lingkungan implementasi pada penelitian ini adalah sebagai berikut:
Windows 7 Professional sebagai sistem operasi PHP 5.3.0 sebagai bahasa pemrograman Netbeans 7.1.2 sebagai integrated development environment XAMPP 3.2.1 sebagai server control panel MySQL 5.6.14 sebagai database management system Notepad++ 6.5.2 sebagai editor
HASIL DAN PEMBAHASAN Pengambilan dan Pemilihan Data Data yang digunakan pada penelitian ini adalah tugas pemrograman kode program berbahasa C. Jumlah data yang digunakan sebanyak 386, yang terdiri atas 4 set data. DataSetAll merupakan gabungan semua DataSet yang digunakan dalam penelitian. Tabel 3 menunjukkan komposisi set data yang digunakan pada penelitian ini. Tabel 3 Set data awal Set data DataSet1 DataSet2 DataSet3 DataSet4 DataSetAll
Jumlah dokumen 92 92 75 66 325
Pengelompokan Manual Pengelompokan manual dilakukan dengan memeriksa nilai output program dan struktur kode programnya. Untuk DataSet1, penelitian ini menggunakan hasil pengelompokan manual yang sudah dilakukan oleh Gumilang (2013). Hasil pengelompokan manual untuk DataSet1 dapat dilihat pada Lampiran 2. Untuk DataSet3 dan DataSet4, penelitian ini menggunakan pengelompokan manual yang sudah dilakukan oleh Notyasa (2013). Hasil pengelompokan manual untuk DataSet3 dan DataSet4 dapat dilihat pada Lampiran 3 dan 4. Setelah dilakukan pemeriksaan nilai output kode program dan dibandingkan strukturnya maka didapat hasil pada DataSet2 menghasilkan 24 cluster. Cluster yang berisi terlalu
8 sedikit dokumen seperti cluster yang hanya berisi 1 atau 2 kode program tersebut kemudian dihilangkan, karena cluster yang anggotanya terlalu sedikit membuat jumlah cluster yang dihasilkan totalnya menjadi lebih banyak. Hasil pengelompokan manual untuk DataSet2 dapat dilihat pada Lampiran 5. Tabel 4 menunjukkan set data setelah dilakukan pengelompokan manual. Tabel 4 Set data setelah pengelompokan manual Set data DataSet1 DataSet2 DataSet3 DataSet4 DataSetAll
Jumlah dokumen 92 79 60 60 291
Cluster manual 9 11 2 6 28
Praproses Data Praproses data terbagi dalam beberapa tahapan, yaitu: pembuangan preprocessor directives, tokenisasi, konversi token, dan N-gram. Pembuangan preprocessor directives dilakukan karena pada penelitian ini diasumsikan tidak adanya penggunaan makro pada kode program. Berikut contoh kode program dari Contoh kode program yang telah dihilangkan preprocessor directives, whitespace, baris comments, karakter “;”, karakter “,”, dan pengubahan huruf uppercase menjadi lowercase. Gambar 3 adalah contoh program sebelum dilakukan tokenisasi, sedangkan Gambar 4 adalah contoh program setelah dilakukan tokenisasi. 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; } Gambar 3 Contoh program sebelum dilakukan tokenisasi 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 } Gambar 4 Contoh program setelah dilakukan tokenisasi
9 Selanjutnya dilakukan proses konversi token 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. Contoh keywords atau special characters yang berhimpitan misalnya inisialisasi variabel dari int a,n=0 setelah dilakukan tokenisasi maka menjadi int an=0, untuk itulah perlu ditambahkan spasi sehingga terpisah tidak berhimpit menjadi int a n=0. Hasil dari proses konversi token adalah string panjang token sederhana yang disebut token stream. Konversi kode program menjadi token sederhana dilakukan berdasarkan aturan konversi seperti pada Tabel 1. Berikut contoh token stream hasil konversi token kode program yang ada di Gambar 4: NhikHFANjNoNFANoNNh5jfNiKhhNhNjNaaiimoNiNaoNNh5jNiRNl Hierarchical Agglomerative Clustering Proses clustering pada penelitian ini menggunakan metode Single Linkage, Complete Linkage, dan Average Linkage. Single Linkage Tabel 5 menunjukkan hasil percobaan clustering pada DataSet1. Berdasarkan hasil percobaan tersebut, dipilih nilai i=0.81. Nilai tersebut dipilih karena memiliki rata-rata RI yang sudah cukup baik, yaitu 0.9706, dan jumlah cluster yang tidak terlalu banyak, yaitu 14. Selanjutnya dilakukan percobaan pada DataSet2, DataSet3, DataSet4, DataSetAll, dan diambil nilai i yang terbaik, dan hasilnya dapat dilihat pada Tabel 6. Untuk hasil lengkap percobaan pada Dataset1, Dataset2, Dataset3, Dataset4, dan DatasetAll dapat dilihat pada Lampiran 6, Lampiran 7, Lampiran 8, Lampiran 9, dan Lampiran 10. Tabel 5 Hasil percobaan Single Linkage clustering untuk DataSet1 i 0.81 0.82 0.83
Jumlah Cluster
RI
14 16 17
0.9706 0.9689 0.9675
I
Waktu (detik) 1.7220 1.7000 1.7210
0.7708 0.8188 0.8211
Tabel 6 Nilai RI, jumlah cluster, jumlah dokumen, dan waktu eksekusi clustering setiap set data percobaan Single Linkage clustering Set Data DataSet1 DataSet2 DataSet3 DataSet4 DataSetAll
RI 0.9706 0.9159 0.9160 0.9739 0.9721
Jumlah Cluster 14 13 4 7 39
Dokumen 92 79 60 60 325
Waktu (detik) 1.7220 3.8610 1.9300 1.4600 74.7553
10
Complete Linkage Tabel 7 menunjukkan hasil percobaan clustering pada DataSet1. Berdasarkan hasil percobaan tersebut, dipilih nilai i=0.87. Nilai tersebut dipilih karena memiliki rata-rata RI yang sudah cukup baik, yaitu 0.8560, dan jumlah cluster yang tidak terlalu banyak, yaitu 10. Selanjutnya dilakukan percobaan pada DataSet2, DataSet3, DataSet4, DataSetAll, dan diambil nilai i yang terbaik dan hasilnya dapat dilihat pada Tabel 8. Untuk hasil lengkap percobaan pada Dataset1, Dataset2, Dataset3, Dataset4, dan DatasetAll dapat dilihat pada Lampiran 11, Lampiran 12, Lampiran 13, Lampiran 14, dan Lampiran 15. Tabel 7 Hasil percobaan Complete Linkage clustering untuk DataSet1 i 0.86 0.87 0.88
Jumlah Cluster 9 10 15
RI 0.8488 0.8560 0.9233
I 0.8531 0.8691 0.8761
Waktu (detik) 1.7800 1.7500 1.7200
Tabel 8 Nilai RI, jumlah cluster, jumlah dokumen, dan waktu eksekusi clustering setiap set data percobaan Complete Linkage clustering Set Data DataSet1 DataSet2 DataSet3 DataSet4 DataSetAll
RI 0.8560 0.8125 0.8591 0.9739 0.9391
Jumlah Cluster 10 12 4 7 29
Dokumen 92 79 60 60 325
Waktu (detik) 1.7500 4.0000 1.9210 1.4110 85.1549
Average Linkage Tabel 9 menunjukkan hasil percobaan clustering pada DataSet1. Berdasarkan hasil percobaan tersebut, dipilih nilai i=0.83. Nilai tersebut dipilih karena memiliki rata-rata RI yang sudah cukup baik, yaitu 0.9546, dan jumlah cluster yang tidak terlalu banyak, yaitu 14. Selanjutnya dilakukan percobaan pada DataSet2, DataSet3, DataSet4, DataSetAll, dan diambil nilai i yang terbaik, dan hasilnya dapat dilihat pada Tabel 10. Untuk hasil lengkap percobaan pada Dataset1, Dataset2, Dataset3, Dataset4, dan DatasetAll dapat dilihat pada Lampiran 16, Lampiran 17, Lampiran 18, Lampiran 19, dan Lampiran 20. Tabel 9 Hasil percobaan Average Linkage clustering untuk DataSet1 i 0.82 0.83 0.84
Jumlah Cluster 14 14 15
RI 0.9546 0.9546 0.9544
I 0.8068 0.8068 0.8398
Waktu (detik) 1.7400 1.7400 1.7500
11 Tabel 10 Nilai RI, jumlah cluster, jumlah dokumen, dan waktu eksekusi clustering setiap set data percobaan Average Linkage clustering Set Data DataSet1 DataSet2 DataSet3 DataSet4 DataSetAll
RI 0.9546 0.8698 0.9160 0.9739 0.9545
Jumlah Cluster 14 11 4 7 35
Dokumen 92 79 60 60 325
Waktu (detik) 1.7400 3.8720 1.9000 1.4600 73.2161
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 dikelompokkannya 2 kode program yang berbeda ke cluster yang sama (false positive). Contoh pasangan dokumen false positive pada DataSet2 saat i=0.85 ditunjukkan pada Gambar 5. Gambar 5 menunjukkan false positive antara dokumen D58 dan D59. Kedua kode program ini memiliki sejumlah perbedaan, 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. #include <stdio.h> unsigned long int fibonacci(long int n) { unsigned long int b,c,i,x,d; if (n==0) return 0; else if (n==1) return 1; else { b=0; c=1; for (i=1;i<=n;i++){ b=b+c; c=b-c; } return b; } } main() { unsigned long int x; scanf("%lu", &x); printf("%lu",fibonacci(x)) ; (x));0; return }
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
#include 1 <stdio.h> unsigned 2 long int F(unsigned longF(unsigned int n) long int n) {3 4 unsigned long int a=0, b=1, c, 5 i; a=0, b=1, c, i; 6 if ((n==0)||(n==1)) 7 return n; 8 Else 9 { 1 for (i=1; i
Gambar 5 False positive dokumen D58 dan D59 pada DataSet2
12 Token stream dokumen D58: HFANhFANikHFANjNjNjNjNIhNooNiRNJIhNooNiRNJkNoNNoNMhNo NNmoNNaaikNoNaNNoNbNlRNllNhikHFANNh5jfNiNh5jNhNiiRNl Token stream dokumen D59: HFANhHFANikHFANoNjNoNjNjNIhhNooNigghNooNiiRNJkMhNoNNm NNaaikNoNaNNoNNoNlRNllNhikHFANNh5jfNiNh5jNhNiiRNl Perbandingan dengan Penelitian Sebelumnya Hasil penelitian ini dibandingkan dengan hasil pendeteksian penjiplakan kode program yang telah dilakukan oleh Gumilang (2013) dan Notyasa (2013). Algoritme yang digunakan pada penelitian Gumilang adalah algoritme flat clustering K-means. Gumilang menggunakan iterasi K-means otomatis agar banyaknya cluster yang diinginkan tidak perlu ditentukan terlebih dahulu. Notyasa (2013) menggunakan algoritme bisecting K-means. Semua proses perbandingan dilakukan pada lingkungan implementasi yang sama. Set data yang digunakan adalah DataSet1 yang berjumlah 92 kode progam. Variabel yang dibandingkan adalah rata-rata jumlah cluster, nilai RI, dan lama waktu eksekusi. Hasil clustering saat nilai i terbaik pada penelitian ini dibandingkan dengan hasil clustering saat nilai i terbaik pada penelitian Gumilang (2013) dan Notyasa (2013) hasilnya Tabel 11. Tabel 11 Perbandingan hasil clustering pada saat nilai i terbaik dengan penelitian sebelumnya Variabel Nilai i terbaik Jumlah cluster Nilai RI Waktu eksekusi (detik)
Bisecting K-means 0.94 9 0.9140 4.6939
Iterasi Kmeans 0.97 11 0.9028 8.4126
Single Linkage 0.81 14 0.9706 1.7220
Complete Linkage 0.87 10 0.8560 1.7500
Average Linkage 0.83 14 0.9546 1.7400
Berdasarkan Tabel 11 dapat dilihat bahwa Single Linkage menghasilkan waktu eksekusi yang lebih cepat dan nilai RI yang lebih tinggi, sedangkan jumlah cluster yang dihasilkan lebih banyak. Complete Linkage menghasilkan waktu eksekusi yang relatif sama dengan Single Linkage dan nilai RI yang lebih rendah, sedangkan jumlah cluster yang dihasilkan tidak terlalu banyak seperti Bisecting K-means. Average Linkage menghasilkan waktu eksekusi yang lebih cepat relatif sama juga dengan Single Linkage dan Complete Linkage dengan nilai RI yang tinggi namun tidak sebagus Single Linkage, sedangkan jumlah cluster yang dihasilkan lebih banyak seperti halnya Single Linkage.
13
SIMPULAN DAN SARAN Simpulan Algoritme Hierarchical Agglomerative Clustering dapat diimplementasikan untuk mendeteksi penjiplakan kode program C. Hasil dari pendeteksian ini cukup baik dengan cluster yang dihasilkan memiliki rata-rata akurasi RI lebih dari 80%. Pendeteksian pada penelitian ini melakukan pengelompokan kode program dalam waktu yang lebih cepat dibandingkan pendeteksian dengan iterasi K-means otomatis dan bisecting K-means, tetapi memiliki rata-rata akurasi RI yang lebih sedikit dibandingkan dengan hasil pendeteksian dengan iterasi K-means otomatis dan bisecting K-means. Jadi berdasarkan hasil penelitian yang dilakukan, rekomendasi algoritme untuk deteksi penjiplakan kode program C yang paling bagus menggunakan metode Single Linkage. 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.
DAFTAR PUSTAKA Burrows 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. Gumilang AP. 2013. Pendeteksian penjiplakan kode program C dengan K-Means [skripsi]. Bogor (ID): Institut Pertanian Bogor. Han J, Kamber M. 2006. Data Mining Concepts and Techniques. Edisi Ke-2. San Francisco (US): Morgan Kaufmann Publisher. Jain AK. 2009. Data clustering: 50 years beyond K-Means. Pattern Recognition Letters Journal 31 (8): 651-666. doi: 10.1016/j.patrec.2009.09.011 Lance GN, Williams WT. 1967. A general theory of classificatory sorting strategies. Computer Journal 9 (4): 373-380. doi: 10.1093/comjnl/9.4.373. Manning CD, Raghavan P, Schütze H. 2008. An Introduction to Information Retrieval. Cambridge (UK): Cambridge University Press. Notyasa A. 2013. Pendeteksian penjiplakan kode program C dengan Bisecting KMeans [skripsi]. Bogor (ID): Institut Pertanian Bogor.
14 Lampiran 1 Tabel aturan konversi kode program menjadi token sederhana (Burrows 2004) 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
15 Lampiran 2 Hasil pengelompokan manual untuk DataSet1 1
2
3
4
5
6
7
8
9
D13 D16 D17
D1 D60 D68 D86 D87 D90 D91
D2 D4 D11 D14 D15 D21 D29 D31 D35 D43 D49 D52 D55 D57 D67 D73 D83
D3 D5 D7 D8 D10 D47 D53 D56 D78 D84
D6 D18 D28 D39 D58 D64 D69 D72
D9 D12 D34 D38 D40
D19 D41 D54 D63
D25 D50
D20 D59 D66 D71 D75 D76 D77 D88 D92
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
16 Lampiran 3 Hasil pengelompokan manual untuk DataSet3 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
17 Lampiran 4 Hasil pengelompokan manual untuk DataSet4 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
18 Lampiran 5 Hasil pengelompokan manual untuk DataSet2 1 2 3 4 5 6 D1 D2 D3 D4 D6 D8 D32 D5 D34 D35 D7 D10 D93 D30 D49 D45 D12 D11 D53 D94 D59 D13 D18 D64 D79 D14 D63 D89 D15 D70 D20 D78 D23 D26 D27 D33 D36 D37 D42 D43 D50 D51 D54 D55 D65 D66 D68 D71 D72 D77 D81 D82 D85 D86 D87 D88 D91 D92 D95 D97
7 8 9 10 11 D16 D21 D29 D33 D90 D17 D75 D41 D46 D98 D24 D83 D56 D48 D60 D62 D76 D96 D80
19 Lampiran 6 Tabel Hasil percobaan Single Linkage clustering untuk DataSet1 i 0.81 0.82 0.83 0.84 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 14 16 17 17 18 18 19 19 20 20 22 23 23 25 26 27 28 30 31 91
RI 0.9706 0.9689 0.9675 0.9675 0.9665 0.9665 0.9587 0.9587 0.9584 0.9584 0.9579 0.9572 0.9572 0.9527 0.9527 0.9545 0.9529 0.9529 0.9522 0.8287
I 0.7708 0.8188 0.8211 0.8211 0.8452 0.8452 0.8650 0.8650 0.8868 0.8868 0.9066 0.9198 0.9198 0.9345 0.9449 0.9545 0.9634 0.9789 0.9854 1.0000
Waktu (detik) 1.7220 1.7000 1.7210 1.7310 1.7210 1.7200 1.7100 1.7810 1.7000 1.7200 1.7000 1.7100 1.7100 1.7010 1.7010 1.6900 1.7000 1.6800 1.7110 1.4910
Lampiran 7 Hasil percobaan Single Linkage clustering untuk DataSet2 i 0.81 0.82 0.83 0.84 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 11 13 13 13 13 14 14 14 15 15 15 16 17 17 18 19 20 21 23 91
RI 0.8944 0.9159 0.9159 0.9159 0.9159 0.9176 0.9176 0.9176 0.9181 0.9181 0.9181 0.9252 0.9286 0.9286 0.9302 0.9310 0.9324 0.9321 0.9338 0.8237
I 0.7662 0.8177 0.8177 0.8177 0.8177 0.8571 0.8571 0.8571 0.8865 0.8865 0.8865 0.9198 0.9228 0.9228 0.9425 0.9573 0.9643 0.9742 0.9882 1.0000
Waktu (detik) 4.1000 3.8510 3.8410 3.8710 3.8610 3.8510 3.8710 3.9010 3.8710 3.8700 3.8920 3.9420 3.8710 3.8710 3.9010 3.8300 3.8200 3.9400 3.9420 3.7710
20 Lampiran 8 Hasil percobaan Single Linkage clustering untuk DataSet3 i 0.81 0.82 0.83 0.84 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 4 4 5 5 5 5 5 5 6 6 6 6 6 8 9 9 10 10 11 74
RI 0.9160 0.9160 0.9168 0.9168 0.9168 0.9168 0.9168 0.9168 0.9153 0.9153 0.9153 0.9153 0.9153 0.9614 0.9302 0.9600 0.9586 0.9586 0.9582 0.4746
I 0.7365 0.7365 0.8281 0.8281 0.8281 0.8281 0.8281 0.8281 0.8874 0.8874 0.8874 0.8874 0.8874 0.9333 0.9477 0.9477 0.9683 0.9683 0.9831 1.0000
Waktu (detik) 1.9410 1.9300 1.9200 1.9100 1.9310 1.9410 1.9110 1.9200 1.9000 1.9100 1.9200 1.9100 1.9000 1.9110 1.9100 1.8900 1.9100 1.8710 1.8800 1.7700
Lampiran 9 Hasil percobaan Single Linkage clustering untuk DataSet4 i 0.81 0.82 0.83 0.84 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 7 7 7 7 8 8 8 8 8 9 9 9 10 10 10 11 11 12 13 65
RI 0.9739 0.9739 0.9739 0.9739 0.9725 0.9725 0.9725 0.9725 0.9725 0.9748 0.9748 0.9748 0.9739 0.9739 0.9739 0.9911 0.9911 0.9925 0.9921 0.6611
I 0.8018 0.8018 0.8018 0.8018 0.8498 0.8498 0.8498 0.8498 0.8498 0.8934 0.8934 0.8934 0.9236 0.9236 0.9236 0.9506 0.9506 0.9725 0.9893 1.0000
Waktu (detik) 1.4400 1.4410 1.4500 1.4600 1.4500 1.4400 1.4500 1.4300 1.4400 1.4300 1.4200 1.4600 1.4310 1.4310 1.4200 1.4200 1.4400 1.4210 1.4400 1.3600
21 Lampiran 10 Hasil percobaan Single Linkage clustering untuk DataSetAll i 0.81 0.82 0.83 0.84 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 39 40 41 43 44 46 47 48 50 51 53 56 58 60 64 67 70 74 79 324
RI 0.9721 0.9734 0.9733 0.9781 0.9780 0.9774 0.9779 0.9779 0.9783 0.9784 0.9784 0.9784 0.9783 0.9810 0.9811 0.9811 0.9812 0.9810 0.9804 0.9235
I 0. 8077 0. 8194 0. 8203 0.8329 0.8425 0.8582 0.8677 0.8767 0.8882 0.8958 0.9079 0.9198 0.9294 0.9392 0.9483 0.9597 0.9684 0.9781 0.9889 1.0000
Waktu (detik) 74.7553 74.4223 75.1283 75.0423 76.3354 76.9124 76.4224 75.7523 78.4695 77.2734 76.6034 81.3106 74.7153 74.4793 74.1672 75.4673 76.4704 81.5977 84.4048 76.4024
Lampiran 11 Hasil percobaan Complete Linkage clustering untuk DataSet1 i 0.81 0.82 0.83 0.84 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 7 7 7 8 8 9 10 15 15 18 18 21 21 22 23 24 27 29 31 91
RI 0.7917 0.7917 0.7917 0.8418 0.8418 0.8488 0.8560 0.9233 0.9233 0.9477 0.9477 0.9575 0.9575 0.9568 0.9575 0.9565 0.9584 0.9505 0.9460 0.8287
I 0.8086 0.8086 0.8086 0.8335 0.8335 0.8531 0.8691 0.8761 0.8761 0.8985 0.8985 0.9186 0.9186 0.9313 0.9427 0.9513 0.9670 0.9785 0.9871 1.0000
Waktu (detik) 1.8000 1.7910 1.7800 1.7510 1.7500 1.7800 1.7500 1.7200 1.7310 1.7500 1.7400 1.7300 1.7200 1.7200 1.7100 1.7210 1.7000 1.7500 1.6900 1.5410
22 Lampiran 12 Hasil percobaan Complete Linkage clustering untuk DataSet2 i 0.81 0.82 0.83 0.84 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 8 8 8 9 9 11 11 12 12 12 13 14 15 15 16 18 19 21 22 91
RI 0.6457 0.6457 0.6457 0.6581 0.6581 0.8022 0.8022 0.8125 0.8125 0.8125 0.8196 0.8617 0.9161 0.9161 0.9176 0.9219 0.9243 0.9283 0.9290 0.8237
I 0.8071 0.8071 0.8071 0.8336 0.8336 0.8509 0.8509 0.8750 0.8750 0.8750 0.9079 0.9177 0.9209 0.9209 0.9431 0.9592 0.9667 0.9776 0.9846 1.0000
Waktu (detik) 4.0420 4.0200 4.0110 4.0110 4.1400 4.0220 4.0500 4.0510 4.1310 4.0000 4.0410 3.9710 4.0800 4.0210 4.0020 3.9710 3.9300 4.0100 4.0600 3.8100
Lampiran 13 Hasil percobaan Complete Linkage clustering untuk DataSet3 i 0.81 0.82 0.83 0.84 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 4 4 4 4 4 4 4 5 5 5 5 6 6 6 8 8 10 10 11 74
RI 0.8591 0.8591 0.8591 0.8591 0.8591 0.8591 0.8591 0.8605 0.8605 0.8605 0.8605 0.8778 0.8778 0.8778 0.9225 0.9225 0.9586 0.9586 0.9831 0.4746
I 0.7955 0.7955 0.7955 0.7955 0.7955 0.7955 0.7955 0.8709 0.8709 0.8709 0.8709 0.9151 0.9151 0.9151 0.9411 0.9411 0.9683 0.9683 0.9831 1.0000
Waktu (detik) 1.9000 1.9210 1.9000 1.9400 1.9110 1.9200 1.9210 1.9000 1.9000 1.9000 1.9110 1.9300 1.8920 1.9000 1.9000 1.9010 1.8700 1.8900 1.8700 1.7410
23 Lampiran 14 Hasil percobaan Complete Linkage clustering untuk DataSet4 i 0.81 0.82 0.83 0.84 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 6 7 7 7 7 7 8 8 8 9 9 9 10 10 10 11 11 12 13 65
RI 0.9403 0.9739 0.9739 0.9739 0.9739 0.9739 0.9762 0.9762 0.9762 0.9748 0.9748 0.9748 0.9739 0.9739 0.9739 0.9911 0.9911 0.9925 0.9921 0.6611
I 0.7517 0.8141 0.8141 0.8141 0.8141 0.8141 0.8627 0.8627 0.8627 0.8941 0.8941 0.8941 0.9236 0.9236 0.9236 0.9506 0.9506 0.9725 0.9893 1.0000
Waktu (detik) 1.4300 1.4100 1.4210 1.4000 1.4110 1.4110 1.4400 1.4210 1.4300 1.4000 1.4300 1.4200 1.4200 1.4000 1.4200 1.4100 1.4300 1.4400 1.4100 1.3200
Lampiran 15 Hasil percobaan Complete Linkage clustering untuk DataSetAll i 0.81 0.82 0.83 0.84 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 22 22 24 25 26 29 33 35 36 44 45 47 51 55 57 60 67 73 79 324
RI 0.9220 0.9220 0.9274 0.9283 0.9316 0.9391 0.9476 0.9486 0.9500 0.9716 0.9723 0.9723 0.9744 0.9751 0.9760 0.9778 0.9782 0.9805 0.9807 0.9235
I 0.8065 0.8065 0.8265 0.8385 0.8464 0.8579 0.8699 0.8781 0.8868 0.8980 0.9052 0.9168 0.9272 0.9383 0.9462 0.9572 0.9691 0.9792 0.9897 1.0000
Waktu (detik) 78.6635 83.5878 85.7099 82.6517 84.1158 85.1549 86.3919 85.9339 82.1837 82.5077 82.7137 81.5457 80.4536 84.5848 81.9087 81.1246 80.0356 75.1873 76.1134 67.1638
24 Lampiran 16 Hasil percobaan Average Linkage clustering untuk DataSet1 i 0.81 0.82 0.83 0.84 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 14 14 14 15 15 15 16 18 19 21 22 22 23 24 25 26 28 29 31 91
RI 0.9546 0.9546 0.9546 0.9544 0.9544 0.9544 0.9534 0.9584 0.9582 0.9577 0.9591 0.9591 0.9589 0.9591 0.9560 0.9545 0.9560 0.9551 0.9474 0.8287
I 0.8068 0.8068 0.8068 0.8398 0.8398 0.8398 0.8603 0.8650 0.8898 0.8987 0.9086 0.9086 0.9221 0.9338 0.9444 0.9525 0.9693 0.9751 0.9862 1.0000
Waktu (detik) 1.7300 1.7400 1.7400 1.7500 1.7300 1.7600 1.7510 1.7400 1.7510 1.7210 1.7200 1.7400 1.7100 1.7030 1.6800 1.6900 1.7200 1.7210 1.6900 1.5510
Lampiran 17 Hasil percobaan Average Linkage clustering untuk DataSet2 i 0.81 0.82 0.83 0.84 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 11 11 12 12 12 12 13 13 14 14 14 15 16 16 17 18 19 21 23 91
RI 0.8698 0.8698 0.8724 0.8724 0.8724 0.8724 0.8741 0.8741 0.9090 0.9090 0.9090 0.9161 0.9181 0.9181 0.9197 0.9219 0.9271 0.9283 0.9358 0.8237
I 0.7863 0.7863 0.8256 0.8256 0.8256 0.8256 0.8674 0.8674 0.8872 0.8872 0.8872 0.9150 0.9277 0.9277 0.9482 0.9596 0.9610 0.9760 0.9897 1.0000
Waktu (detik) 3.9410 3.8720 3.9000 3.9310 3.9010 3.8700 3.9300 3.8810 3.8900 3.8710 3.8800 3.8800 3.8730 3.8710 3.8610 3.9400 3.8810 3.8720 3.9510 3.6010
25 Lampiran 18 Hasil percobaan Average Linkage clustering untuk DataSet3 i 0.81 0.82 0.83 0.84 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 4 4 4 5 5 5 5 5 5 5 6 6 6 6 9 9 10 10 11 74
RI 0.9160 0.9160 0.9160 0.9168 0.9168 0.9168 0.9168 0.9168 0.9168 0.9168 0.9542 0.9542 0.9542 0.9542 0.9600 0.9600 0.9586 0.9586 0.9582 0.4746
I 0.7517 0.7517 0.7517 0.8377 0.8377 0.8377 0.8377 0.8377 0.8377 0.8377 0.9019 0.9019 0.9019 0.9019 0.9487 0.9487 0.9683 0.9683 0.9831 1.0000
Waktu (detik) 1.8910 1.8810 1.9000 1.8600 1.9010 1.8510 1.8600 1.8700 1.8900 1.8910 1.8700 1.8500 1.8700 1.8610 1.8300 1.8400 1.8800 1.9010 1.8710 1.6900
Lampiran 19 Hasil percobaan Average Linkage clustering untuk DataSet4 i 0.81 0.82 0.83 0.84 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 7 7 7 7 7 8 8 8 8 9 9 9 10 10 10 11 11 12 13 65
RI 0.9739 0.9739 0.9739 0.9739 0.9739 0.9725 0.9725 0.9725 0.9725 0.9748 0.9748 0.9748 0.9739 0.9739 0.9739 0.9911 0.9911 0.9925 0.9921 0.6611
I 0.8085 0.8085 0.8085 0.8085 0.8085 0.8528 0.8528 0.8528 0.8528 0.8939 0.8939 0.8939 0.9236 0.9236 0.9236 0.9506 0.9506 0.9725 0.9893 1.0000
Waktu (detik) 1.5400 1.4000 1.4610 1.4600 1.4600 1.4400 1.4500 1.4500 1.4600 1.4100 1.4800 1.4300 1.4400 1.4300 1.4500 1.4800 1.4310 1.4710 1.4400 1.3400
26 Lampiran 20 Hasil percobaan Average Linkage clustering untuk DataSetAll i 0.81 0.82 0.83 0.84 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 35 37 37 38 39 41 42 44 47 49 51 54 56 59 61 64 68 74 79 324
RI 0.9545 0.9703 0.9703 0.9708 0.9708 0.9723 0.9725 0. 9771 0.9777 0.9777 0.9778 0.9778 0.9798 0.9809 0.9808 0.9806 0.9805 0.9804 0.9805 0.9235
I 0.8095 0.8190 0.8190 0.8317 0.8438 0.8599 0.8698 0.8762 0.8863 0.8988 0.9064 0.9167 0.9269 0.9379 0.9462 0.9575 0.9692 0.9794 0.9893 1.0000
Waktu (detik) 73.2161 73.1661 73.2451 74.7871 73.3041 74.0421 74.4781 74.5081 75.0161 75.4681 74.1581 74.4691 74.8881 72.9651 78.6195 77.6754 75.3813 76.8244 76.1134 68.2749
27
RIWAYAT HIDUP Penulis dilahirkan pada tanggal 24 Mei 1992 di Kota Bekasi, Jawa Barat. Penulis merupakan anak ketiga dari pasangan Bapak Supardi dan Ibu Sulanjari. Penulis memiliki dua orang kakak yang bernama Bekti Siswati dan Desi Widyawati. Penulis menyelesaikan pendidikan sekolah menengah atas pada tahun 2010 di SMA Negeri 2 Kota Bekasi. Pada tahun 2010 penulis diterima sebagai mahasiswa Institut Pertanian Bogor melalui jalur Undangan Seleksi Masuk IPB (USMI) dan diterima sebagai mahasiswa Departemen Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Pada tahun 2013 penulis menjalankan praktik kerja lapangan di PT. Suntory Garuda Beverage.
