BAB III METODOLOGI PENELITIAN Terdapat tiga tahapan utama dalam penelitian ini. Ketiga tahapan tersebut yaitu, pembentukan klaster data SMS, pembentukan model klasifikasi, serta implementasi model klasifikasi ke perangkat seluler. Pembentukan Klaster Data SMS Pada Gambar 3 ditunjukkan tahapan pembentukan klaster data yang digunakan. Pada tahap ini, akan dilakukan pembentukan klaster data dan pembentukan dataset dari data SMS. Terdapat lima subtahap dari tahapan pembentukan klaster data, yaitu subtahap pengumpulan data SMS, subtahap praproses, subtahap pembentukan klaster data teks dan pemilihan klaster terbaik, subtahap representasi pesan, dan subtahap pembentukan dataset. Pengumpulan data SMS dilakukan untuk memperoleh sumber data yang akan digunakan pada penelitian ini. SMS yang dikumpulkan adalah SMS berindikasi tindak penipuan yang beredar di masyarakat pada tahun 2010-2011. Kumpulan SMS tersebut diperoleh dari penulis, beberapa orang kolega penulis, dan media internet.
Gambar 3 Tahapan Pembentukan Klaster Data
18 Struktur Praproses Tahap praproses dapat dipecah lagi menjadi beberapa tahap. Rincian lengkap tahap praproses dapat dilihat pada Gambar 4.
Gambar 4 Tahapan Praproses Tahapan praproses data yang dilakukan adalah sebagai berikut : 1. Tokenizing: Pada proses tokenizing dilakukan pemotongan untuk setiap kata, rangkaian angka dan rangkaian angka dengan huruf yang memiliki makna tertentu, yang terdapat dalam SMS. Karakter selain huruf, rangkaian angka, atau rangkaian angka dengan huruf akan dihilangkan. Setiap kata, rangkaian angka, maupun rangkaian angka dengan huruf disebut sebagai token. Ilustrasi dari proses tokenizing dapat dilihat di bawah ini. Data awal : Tolong belikan dlu Mama pulsa 50 rb di No Mama yang baru ini 081313779293 MAMA mau pakai Nelpon pnting.! ini No orng MAMA pakai Hasil proses tokenizing : tolong belikan dlu mama pulsa nominal di no yang baru ini nomortelepon mau pakai nelpon pnting orng 2. Filtering: Proses filtering merupakan proses pembuangan token yang termasuk dalam daftar stop word. Beberapa kata yang termasuk dalam daftar stop word adalah yang, di, ke, dari, adalah, dan, atau, dan lain sebagainya.
19 Ilustrasi dari proses filtering dapat dilihat di bawah ini. Data hasil proses tokenizing : tolong belikan dlu mama pulsa nominal di no yang baru ini nomortelepon mau pakai nelpon pnting orng Hasil proses filtering : tolong belikan dlu mama pulsa nominal no baru ini nomortelepon mau pakai nelpon pnting orng
3. Stemming: Pada proses stemming dilakukan penghapusan awalan dan akhiran yang terdapat pada setiap token yang mengandung imbuhan. Proses ini dilakukan untuk mendapatkan kata dasar dari setiap token. Ilustrasi dari proses stemming dapat dilihat di bawah ini. Data hasil proses filtering : tolong belikan dlu mama pulsa nominal no baru ini nomortelepon mau pakai nelpon pnting orng Hasil proses stemming : tolong beli dlu mama pulsa nominal no baru ini nomortelepon mau pakai nelpon pnting orng
4. Word Approximation: Proses word approximation merupakan proses perbaikan token yang salah ketik atau token yang disingkat (Angkawattanawit et al. 2008). Karena token yang salah ketik atau token yang disingkat tidak akan memiliki makna. Padahal bisa saja token tersebut memiliki makna yang dapat digunakan dalam mengenali kategori suatu SMS. Proses word approximation dilakukan dengan menggunakan algoritma Damerau Levenshtein (Navarro 2001). Ukuran jarak Damerau Levenshtein adalah jarak antara dua string yang dihitung dari jumlah minimum operasi yang diperlukan untuk mengubah satu string ke string yang lain, di mana operasi yang dimaksud didefinisikan sebagai penyisipan, penghapusan, atau
20 penggantian satu karakter, atau penukaran dari dua karakter yang berdekatan. Pseudocode dari algoritma Damerau Levenshtein ditunjukkan pada Gambar 5.
Gambar 5 Pseudocode Algoritma Damerau Levensthein Data hasil proses stemming dan daftar kata dasar dalam Bahasa Indonesia digunakan sebagai masukan pada proses ini. Proses word approximation dilakukan perbandingan kata dengan memperhatikan empat jenis kesalahan pengetikan, yaitu : a. Penyisipan sebuah huruf. b. Penghapusan sebuah huruf. c. Penggantian sebuah huruf dengan huruf lain. d. Penukaran dua karakter yang berdekatan. Tahapan yang dilakukan pada proses word approximation dengan menggunakan algoritma Damerau Levenshtein adalah sebagai berikut : a. Menghitung jarak antara token dengan setiap kata yang terdapat pada daftar kata dasar dengan menggunakan ukuran jarak Damerau Levenshtein. b. Mencari nilai jarak yang paling kecil.
21 c. Mengganti token tersebut dengan kata dari daftar kata dasar, dimana jarak antara token dengan kata tersebut merupakan jarak paling kecil. Ilustrasi dari proses word approximation dapat dilihat di bawah ini. Data hasil proses stemming : tolong beli dlu mama pulsa nominal no baru ini nomortelepon mau pakai nelpon pnting orng Hasil proses word approximation : tolong beli dulu mama pulsa nominal nomor baru ini nomortelepon mau pakai telepon penting orang
Pembentukan Klaster Data Teks dan Pemilihan Klaster Terbaik Proses
pembentukan
klaster
data
dilakukan
untuk
mendapatkan
pengelompokkan dari seluruh data SMS yang ada (Huang 2008). Proses ini dilakukan menggunakan data hasil tahap praproses. Pada penelitian ini dilakukan percobaan membentuk klaster menggunakan algoritma ROCK dengan merubah masukan jumlah klaster dan nilai ambang . Jumlah klaster yang digunakan adalah 2, 3, 4, dan 5. Sedangkan nilai ambang yang digunakan antara 0.01 sampai 0.18. Tahapan dari pembentukan klaster data menggunakan algoritma ROCK adalah (Guha et al. 2000): 1. Menentukan inisialisasi untuk masing-masing data poin sebagai klaster pada awalnya. 2. Menghitung similaritas antara suatu klaster dengan klaster lainnya, simx,y= |x∩y|⁄|x(y|
menggunakan rumus jaccard coefficient berikut :
|x∩y| menyatakan banyaknya item yang sama pada x dan y, sedangkan |x(y| menyatakan banyaknya gabungan item pada x dan y.
Sebagai contoh penghitungan jaccard coefficient, diberikan dua SMS )! dan
)* sebagai berikut :
22
)! = { baru, beli, dulu, ini, mama, mau, nominal, nomor, nomortelepon, )* = { ada, baru, ini, jangan, kantor, kirim, lagi, masalah, nominal, nomor, orang, pakai, penting, pulsa, telepon, tolong}
simx1 ,x2 = 8⁄23 =0,35
nomortelepon, papa, polisi, pulsa, telepon, tolong}
3. Menentukan nilai matrik tetangga A dengan menggunakan nilai nilai ambang (θ). A[x,y] bernilai 1 jika sim(x,y) ≥ θ dan bernilai 0 jika sim(x,y) ≤ θ. Sebagai contoh penentuan nilai matrik tetangga A dapat dilihat berikut ini : +,-)! , )* = 0,35
nilai ambang (θ) = 0,3
A[)! , )* ] = 1, maka )! dan )* merupakan tetangga. 4. Menghitung link antara suatu klaster dengan klaster lainnya menggunakan persamaan 1. Link(Ti, Tj) antarobjek diperoleh dari jumlah tetangga antara Ti dan Tj. Link(Ti, Tj) = |tetangga(Ti) ∩ tetangga(Tj)|. Sebagai contoh penentuan Link(Ti,Tj) dapat dilihat berikut ini : Diberikan empat titik data yaitu )! , )* , ). , dan )/ . 1 1 Matrik tetangga A = 0 0 1
Link()! , )* ) = 3
Link()! , ). ) = 1 Link()! , )/ ) = 3
Link()* , ). ) = 2 Link()* , )/ ) = 3 Link(). , )/ ) = 1
1 1 1 1
0 1 1 0
1 1 1 0 1
23 5. Menghitung nilai goodness measure untuk setiap klaster dengan klaster lainnya jika link != 0 yang disebut local heap, dengan menggunakan Persamaan 2. Sebagai contoh penghitungan nilai goodness measure dapat dilihat berikut ini : Diberikan dua klaster yaitu C1 dan C2 . nilai ambang (θ) = 0,3 Link(C1 , C2 ) = 3 ni = 1 nj = 1
fθ= 1-θ⁄1+θ = 1-0,3⁄1+0,3 = 0,7⁄1,3 = 0,54
gx1 ,x2 = 3⁄(1+1)1+2.0,54 - 11+2.0,54 - 11+2.0,54 = 3⁄4,23-1-1 =1,35
6. Memilih nilai maksimum goodness measure antarkolom di baris ke i yang disebut global heap. 7. Ulangi langkah 5 dan 6 hingga mendapatkan nilai maksimum di global heap dan local heap 8. Selama ukuran data > k, dengan k adalah jumlah kelas yang ditentukan lakukan penggabungan klaster yang memiliki nilai local heap terbesar menjadi satu klaster, tambahkan link antarklaster yang digabungkan, hapus klaster yang digabungkan dari local heap dan update nilai global heap dengan nilai hasil penggabungan. 9. Lakukan langkah 8 hingga menemukan jumlah klaster yang diharapkan atau tidak ada lagi link antara klaster-klasternya Setelah itu dilakukan pemilihan klaster terbaik dari semua klaster yang terbentuk dengan menggunakan ukuran kebaikan klaster. Ukuran kebaikan klaster yang digunakan adalah cohesion dan separation. Semakin tinggi nilai cohesion dan semakin rendah nilai separation, maka semakin baik klaster tersebut terhadap klaster lainnya. Selain itu, waktu proses dan jumlah klaster yang memiliki anggota SMS yang termasuk penipuan juga digunakan untuk memilih klaster terbaik.
24 Pengelompokkan dari klaster terbaik yang akan menjadi kategori kelas dari data SMS. Representasi Pesan Setiap SMS yang telah melalui tahap praproses diubah menjadi bentuk vektor numerik yang elemennya adalah nilai 1 atau 0 (Sebastiani 2002). Dimana nilai 1 menunjukkan bahwa suatu token dimiliki oleh SMS dan nilai 0 menunjukkan suatu token tidak dimiliki oleh SMS. Pembentukan Dataset Dataset dibentuk dengan menggabungkan data berbentuk vektor yang dihasilkan dari proses representasi data dengan kategori kelas yang merupakan hasil dari proses pembentukan klaster data. Dataset ini yang akan digunakan pada tahapan selanjutnya, yaitu tahapan pembentukan model klasifikasi. Pembentukan Model Klasifikasi Tahapan setelah pembentukan dataset adalah tahapan pembentukan dan pemilihan model. Tahapan pembentukan dan pemilihan model dapat dilihat pada Gambar 6. Penentuan Data Latih dan Data Uji Proses penentuan data menjadi data latih dan data uji dilakukan dengan menggunakan teknik 10 fold cross validation. Data latih akan digunakan untuk membentuk model klasifikasi. Sedangkan data uji akan digunakan untuk menghitung akurasi yang diperoleh dari model klasifikasi.
25
Gambar 6 Tahapan Pembentukan Model Klasifikasi. Klasifikasi Terdapat dua proses dalam klasifikasi, yaitu proses pelatihan data latih untuk membentuk model klasifikasi dan proses penghitungan akurasi dari model klasifikasi yang terbentuk menggunakan data uji. Klasifikasi dilakukan menggunakan algoritma Naive Bayes (Deng & Peng 2006) pada dataset yang telah melalui proses seleksi fitur. Pada proses pelatihan data, dilakukan penghitungan class prior probability menggunakan dan conditional probability untuk setiap token menggunakan Persamaan 4. Jumlah kategori kelas yang digunakan pada proses klasifikasi tergantung dengan hasil dari proses pembentukan klaster data. Proses klasifikasi dilakukan dengan menggunakan library WEKA (Witten et al. 2011). Setelah model klasifikasi terbentuk, dilakukan penghitungan akurasi dengan melakukan penambahan data pada data uji. Proses ini dilakukan berulang sebanyak 20 kali perulangan. Pada setiap perulangan, dilakukan penambahan data uji sebanyak 5 data. Proses penghitungan akurasi dilakukan dengan menggunakan metode
26 evaluasi confusion matrix (Han & Kamber 2011). Akurasi akhir adalah rata-rata akurasi dari semua akurasi yang diperoleh dari 20 perulangan. Implementasi Model Klasifikasi ke Perangkat Seluler Model klasifikasi yang telah diperoleh pada tahap sebelumnya akan diimplementasikan ke perangkat seluler berbasis Android. Sistem ini dibuat menggunakan bahasa pemrograman Java (Eclipse 2010) dan basis data SQLite (Hipp et al. 2010). Berdasarkan arsitektur Android (Xie et al. 2012), aplikasi penyaringan SMS berindikasi tindak penipuan yang akan dikembangkan berada pada lapisan aplikasi pada arsitektur Android. Sedangkan SQLite merupakan salah satu library yang dapat digunakan dalam pengembangan aplikasi untuk framework Android. Dalam penentuan label dari SMS baru, dilakukan penghitungan posterior probability dengan menggunakan persamaan (5). Sebagai contoh penghitungan posterior probability adalah sebagai berikut : Contoh data disajikan pada Tabel 2. Tabel 2. Contoh data Id_data 1 2 3 4 5
Token1 1 0 1 1 0
P(C1) = 3⁄5 =0,6 P(C1) = 2⁄5 =0,4
Token2 1 0 1 0 1
P(Token1=1 | C1) = 2⁄3 =0,67 P(Token1=0 | C1) = 1⁄3 =0,33 P(Token1=1 | C2) = 1⁄2 =0,5 P(Token1=0 | C2) = 1⁄2 =0,5 P(Token2=1 | C1) = 2⁄3 =0,67 P(Token2=0 | C1) = 1⁄3 =0,33 P(Token2=1 | C2) = 1⁄2 =0,5 P(Token2=0 | C2) = 1⁄2 =0,5 P(Token3=1 | C1) = 2⁄3 =0,67 P(Token3=0 | C1) = 1⁄3 =0,33 P(Token3=1 | C2) = 1⁄2 =0,5 P(Token3=0 | C2) = 1⁄2 =0,5
Token3 1 1 0 1 0
Token4 0 1 1 1 1
Kelas C1 C1 C1 C2 C2
P(Token4=1 | C1) = 2⁄3 =0,67 P(Token4=0 | C1) = 1⁄3 =0,33 P(Token4=1 | C2) = 2⁄2 =1 P(Token4=0 | C2) = 0⁄2 =0
Data Baru : X = Token1=1 , Token2=0, Token3=0, Token4=1 Class-conditional Probability untuk kelas C1 P(X | C1)= P(Token1=1 | C1) * P(Token2=0 | C1) * P(Token3=0 | C1) * P(Token4=1 | C1) = 0,67 * 0,33 * 0,33 * 0,67 = 0,048 Class-conditional Probability untuk kelas C1 P(X | C2)= P(Token1=1 | C2) * P(Token2=0 | C2) * P(Token3=0 | C2) * P(Token4=1 | C2) = 0,5 * 0,5* 0,5 * 1 = 0,125 Posterior Probability untuk kelas C1 P(C1 | X)= P(C1) * P(X | C1) /( [P(C1) * P(X | C1)] + [P(C2) * P(X | C2)]) = 0,6 * 0,048 /( [0,6 * 0,048] + [0,4 * 0,125]) = 0,0288 / 0,0788 = 0,365 Posterior Probability untuk kelas C2 P(C2 | X)= P(C2) * P(X | C2) /( [P(C1) * P(X | C1)] + [P(C2) * P(X | C2)]) = 0,4 * 0,125/( [0,6 * 0,048] + [0,4 * 0,125]) = 0,05/ 0,0788 = 0,635 Karena nilai P(C2 | X) 4 P(C1 | X) , maka data baru X masuk ke dalam kelas C2
27
