PERANCANGAN ALGORITMA BAYESIAN NETWORK UNTUK MEMFILTER WEBSITE TERLARANG
THE DESIGN OF THE ALGORITHM BAYESIAN NETWORK IN ORDER TO FILTER THE ILLEGAL WEBSITE
Lukman Syafie, Armin Lawi, Suarga Bagian Matematika Terapan, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Hasanuddin.
Alamat Korespondensi: Lukman Syafie, S.Si Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Hasanuddin Makassar, HP: 085242809809 Email:
[email protected]
ABSTRAK Perkembangan internet yang sangat pesat dapat berpotensi memberi dampak yang negatif misalnya tersedianya material yang ilegal, berorientasi pornografi, kekerasan, dan sebagainya, sehingga diperlukan adanya sistem filter yang efektif. Penelitian ini bertujuan untuk: (1) membangun algoritma klasifikasi Bayesian Network, (2) merancang simulasi filter content-type teks yang mampu mengklasifikasi website berdasarkan algoritma klasifikasi yang dibuat, dan (3) menganalisis kinerja hasil simulasi algoritma klasifikasi Bayesian Network untuk filter website. Metode penelitian yang digunakan adalah metode eksperimen dengan bentuk penelitian kuantitatif. Klasifikasi dilakukan dengan memperhitungkan peluang kemunculan kata-kata yang tidak terdapat pada data pelatihan. Hasil penelitian menunjukkan bahwa akurasi hasil klasifikasi dapat ditingkatkan dengan teknik penambahan nilai peluang dari kata-kata yang tidak terdapat pada data pelatihan. Kata kunci : Naïve Bayes, Jaringan Bayes, Klasifikasi Web, Algoritma.
ABSTRACT The development of internet which is growing fast can potentially give negative impacts such as the availability of illegal material, pornographic, violent oriented and so forth, so it needed an effective filter system. This study aims to (1) develop the classification of the Algorithm Bayesian Network; (2) design the filter simulation of the content-type text which will be capable of classifying the websites based on the existing algorithm classification; (3) analyze the simulation result of the performance of the Algorithm Bayesian Network to filter the websites. The method used in the research was the quantitative experimental method. The classification was carried out by calculating the frequencies of the word not given during the training process appeared. The result of the research revealed that the accuracy of the classification result could be improved by the technique of increasing the chances for words that had not been given during the training process. Keywords: Naïve Bayesian, Bayesian Network, Web classification, Algorithm.
PENDAHULUAN Perkembangan internet yang sangat pesat pada satu sisi menguntungkan dalam kemudahan memperoleh informasi, di sisi lain dapat berpotensi memberi dampak yang negatif. Dampak negatif misalnya tersedianya material yang ilegal, berorientasi pornografi, kekerasan, dan sebagainya. Untuk mengantisipasi kasus di atas, diperlukan suatu sistem untuk memfilter website. Filter website dapat diimplementasikan pada 2 tempat, yaitu filter pada komputer pengguna (Client-side filters) dan filter pada komputer server (Server-side filters) yang menyediakan akses internet. Pada tipe filter di komputer pengguna, bentuk filter yang umum digunakan adalah berbasis alamat URL atau alamat IP. Filter jenis ini didasarkan pada daftar URL atau IP yang dibuat secara manual. Pada tipe filter di komputer server, bentuk filter yang umum digunakan adalah berbasis proxy atau DNS. Filter jenis ini juga didasarkan pada daftar URL atau alamat IP yang dibuat oleh administrator server tersebut. Karena alasan tersebut, diusulkan suatu sistem filter website pada komputer pengguna (Client-side filters) yang dapat meminimalkan keterlibatan pengguna dalam menganalisis dan mendeteksi website untuk membuat sistem yang user-friendly. Beberapa metode telah diajukan untuk menghambat pertumbuhan website terlarang, Lee dkk. (2002) telah mengajukan teknik klasifikasi berdasarkan isi teks yang terdapat pada website menggunakan metode Artificial Neural Networks (ANN). Pop (2006) mengajukan teknik klasifikasi menggunakan Naive Bayesian Filtering, metode ini memanfaatkan teorema probabilitas yaitu teorema Bayes. Selanjutnya Guermazi (2007) mengkombinasikan filter berdasarkan URL dan analisa teks dan struktur dari website. Metode filter yang lain menggunakan Version Space Support Vector Machine (Pasaribu dkk., 2010), sedang Urvoy dkk. (2008) menggunakan metode analisis kesamaan bentuk HTML. Dalam tulisan ini, masalah website diperlakukan sebagai masalah klasifikasi yaitu masalah pengenalan pola. Pengguna hanya perlu memutuskan apakah sebuah website termasuk dalam kategori boleh diakses (whitelist) atau tidak boleh diakses (blacklist). Sistem kemudian akan belajar dari keputusan untuk memilah-milah apakah website berikutnya yang masuk adalah blacklist atau tidak. Salah satu metode yang dapat digunakan adalah metode Bayesian Network. Metode ini memanfaatkan teorema probabilitas yaitu teorema Bayes Penelitian ini bertujuan untuk: (1) membangun algoritma klasifikasi Bayesian Network, (2) merancang simulasi filter content-type teks yang mampu mengklasifikasi
website berdasarkan algoritma klasifikasi yang dibuat, dan (3) menganalisis kinerja hasil simulasi algoritma klasifikasi Bayesian Network untuk filter website. BAHAN DAN METODE Secara umum desain penelitian yang dilakukan adalah metode eksperimen dengan bentuk penelitian kuantitatif. Tahapan yang dilakukan adalah membangun algoritma klasifikasi Bayesian Network, merancang simulasi filter content-type teks yang mampu mengklasifikasi website berdasarkan klasifikasi yang dibuat, dan menganalisis kinerja hasil simulasi algoritma klasifikasi Bayesian Network untuk filter website. Variabel atau peubah yang diamati dan diukur dalam penulisan ini adalah halaman website yang dilambangkan dengan atribut wj, yang mewakili website ke-j, kata-kata dalam website dilambangkan dengan kp, yang mewakili kata ke-p, dan kategori dari website yang dilambangkan dengan ci, yaitu kategori ke-i. Kategori pertama adalah website terlarang yang disebut Spam dilambangkan dengan S, kategori kedua adalah website tidak terlarang yang disebut Ham dilambangkan dengan H. Data yang digunakan dalam penelitian ini adalah sekumpulan halaman website yang akan diklasifikasikan berdasarkan konten atau isi teks. Data penelitian dikumpulkan dari beberapa website yang diperoleh secara online kemudian disimpan sehingga diperoleh file format html. Selain itu, data penelitian diperoleh juga dari dataset penelitian yang dilakukan oleh Laode Sahlan (Sahlan, 2011). Daftar kata-kata umum (stoplist) berjumlah 1.933 kata yang terdiri atas 1.154 kata bahasa Inggris (Lewis. 2000) dan 779 kata bahasa Indonesia (Tala. 2003). Alat bantu komputasi yang digunakan pada penelitian ini adalah software Delphi 2010 dengan database Sqlite 3. HASIL Klasifikasi website membutuhkan jumlah data pelatihan yang cukup besar untuk mendapatkan akurasi yang tinggi. Data pelatihan merupakan infomasi general yang mewakili suatu kategori tertentu. Akan tetapi jumlah data pelatihan yang besar akan berimplikasi meningkatkan kompleksitas perhitungan, sebaliknya jumlah data pelatihan yang kecil dapat menurunkan tingkat akurasi karena adanya kemungkinan kata-kata yang terdapat pada website uji tidak terdapat pada data pelatihan. Oleh karena itu dilakukan klasifikasi dengan memperhitungkan peluang kemunculan kata-kata yang tidak terdapat pada data pelatihan.
Proses klasifikasi dilakukan dengan menghitung nilai peluang menggunakan persamaan: (C c i | W w j )
Dengan wj
,
(W w j | C ci ) (C ci ) (W w j )
(C c i | W w j )
(W w j | C c i )
merupakan nilai peluang kategori ci jika diketahui website
merupakan nilai peluang dari kemunculan website
jika diketahui
wj
website tersebut berkategori ci , (C ci ) adalah nilai peluang kemunculan kategori ci , dan (W w j )
adalah nilai peluang kemunculan website
wj
.
Website terdiri dari kumpulan kata-kata yang menyusun website tersebut sehingga perhitungan peluang
(W w j | C c i )
kemunculan kata-kata pada website
wj
dapat dianggap sebagai hasil perkalian dari peluang (Pop, 2006):
(W w j | C c i ) (K k p | C ci ) p
sehingga (C c i | W w j ) (C ci ) ( K k p | C c i ) p
dimana
1 (W w j )
yang merupakan suatu nilai konstan dalam setiap perhitungan sehingga
persamaan klasifikasi dapat dinyatakan dalam bentuk persamaan: (C ci | W w j ) (C ci ) ( K k p | C c i ) p
Dari persamaan tersebut diperoleh rumus klasifikasi:
C
(C Spam | W w j ) ln (C Ham | W w ) j
Selanjutnya website dikategorikan sebagai website terlarang (Spam) jika
C
0
selain itu
termasuk kategori Ham (Pop, 2006). Berdasarkan
percobaan
yang
dilakukan,
rumusan
umum
klasifikasi
gagal
mengklasifikasi website jika jumlah kata dalam data pelatihan bernilai besar sementara frekuensi kemunculan setiap kata bernilai kecil, karena perkalian dari frekuensi kata hasilnya sangat kecil dan cenderung menuju nol. Oleh karena itu dilakukan modifikasi persamaan dengan bentuk logaritma natural sehingga persamaan yang baru dinyatakan dalam bentuk: ln (C c i | W w j ) ln (C c i ) (K k p | C c i ) p
atau
ln (C c i | W w j ) ln (C ci ) ln (K k p | C c i ) p
Dari persamaan tersebut diperoleh rumusan klasifikasi:
C
ln (C Spam | W w j ) ln (C Ham | W w j )
Selanjutnya website dikategorikan sebagai website terlarang (Spam) jika
C
0
dan selain itu
termasuk Ham. Pengujian dilakukan sebanyak 20 kali percobaan dengan jumlah data uji tiap percobaan masing-masing sebanyak 40 website. Total frekuensi kata yang digunakan sebanyak 28.811 kata. Berdasarkan pengujian, grafik tingkat akurasi yang ditunjukkan oleh gambar 1 memperlihatkan bahwa nilai akurasi dari keseluruhan pengujian cenderung meningkat. Dari gambar 2 terlihat bahwa nilai False Negatif cenderung turun seiring dengan penambahan jumlah data pelatihan, sementara itu pada gambar 3 terlihat nilai False Positif turun secara drastis seiring dengan penambahan jumlah data pelatihan.
PEMBAHASAN Penelitian ini menunjukkan bahwa akurasi hasil klasifikasi dapat ditingkatkan dengan teknik penambahan nilai peluang dari kata-kata yang tidak terdapat pada data pelatihan. Beberapa metode dan algoritma Bayesian Network telah dikaji sebelumnya. Campos (2002) dalam penelitiannya menggunakan prosedur pencarian data dalam suatu jaringan Bayes menggunakan teknik Ant Colony Optimization. Selanjutnya Sanghai dkk. (2003) mengusulkan
model
Dynamic
Probabilistic
Relational
Models
(DPRMs),
yang
memungkinkan penalaran dengan kelas, dan objek dalam lingkungan yang dinamis. Metode yang lain menggunakan teknik Linear Progrraming (LP) untuk mencari nilai tertinggi suatu struktur Bayesian Network diajukan oleh Jaakkola (2010). Klasifikasi menggunakan Teorema Bayes ini membutuhkan biaya komputasi yang mahal, karena kebutuhan untuk menghitung nilai probabilitas nilai dari perkalian kartesius untuk tiap nilai atribut dan tiap nilai kelas. Data pelatihan untuk Teorema Bayes membutuhkan paling tidak perkalian kartesius dari seluruh kelompok atribut yang mungkin. Misalkan terdapat 16 atribut dengan jenis data masing-masing adalah Boolean tanpa missing value, maka data pelatihan minimal yang dibutuhkan oleh Teorema Bayes untuk digunakan dalam klasifikasi adalah 216 = 65.536 (Shadiq, 2009). Sehingga masalah utama yang dihadapi untuk menggunakan teorema Bayes dalam pengklasifikasian yaitu kebanyakan data latih tidak memiliki varian klasifikasi sebanyak itu, akibatnya jika suatu data pengujian tidak ada dalam data pelatihan, maka data pengujian tersebut tidak dapat diklasifikasikan.
Pada penelitian sebelumnya yang dilakukan oleh Sahlan (2011), klasifikasi menggunakan Naïve Bayesian menghasilkan tingkat akurasi yang kurang akurat akibat jumlah data pelatihan yang sedikit. Atas dasar itu, diajukan teknik penambahan nilai peluang dari kata-kata pada website pengujian yang tidak terdapat pada data pelatihan. Teknik ini diharapkan dapat menjadi solusi masalah klasifikasi dengan varian data pelatihan yang terbatas. Berdasarkan pengujian, nilai akurasi dari keseluruhan pengujian cenderung meningkat. Meskipun terdapat kasus penurunan tingkat akurasi pada saat tertentu, hal ini disebabkan oleh karena jumlah data pelatihan yang masih kecil. Dari keseluruhan pengujian, tingkat akurasi cenderung naik seiring dengan penambahan jumlah data pelatihan tersebut. Nilai False Negatif dari keseluruhan pengujian cenderung turun seiring dengan penambahan jumlah data pelatihan, hal ini disebabkan karena adanya penambahan data pelatihan yang merupakan infomasi general yang mewakili suatu kategori. Nilai False Positif turun secara drastis seiring dengan penambahan jumlah data pelatihan. Ini berarti informasi umum dari data pelatihan untuk website kategori Ham sudah mampu mewakili kategori tersebut. Nilai False Positif lebih cepat stabil dibandingkan nilai False Negatif, meskipun jumlah frekuensi kata dari data pelatihan untuk website kategori Ham lebih kecil dibandingkan kategori Spam. Ini berarti banyak website yang seharusnya termasuk dalam kategori Spam akan tetapi menggunakan kata-kata yang umum digunakan dalam website kategori Ham sehingga informasi data pelatihan untuk website kategori Spam menjadi bias.
KESIMPULAN DAN SARAN Jumlah data pelatihan berpengaruh secara signifikan terhadap hasil proses klasifikasi. Tingkat akurasi hasil klasifikasi dapat ditingkatkan dengan teknik penambahan nilai peluang dari kata-kata website uji yang tidak terdapat pada data pelatihan. Penambahan bentuk logaritma natural pada perhitungan awal prior probability mampu mengklasifikasi website jika jumlah kata dalam data pelatihan bernilai besar sementara frekuensi kemunculan setiap kata bernilai kecil. Banyak website kategori Spam yang menggunakan kata-kata yang umum digunakan dalam website kategori Ham, sehingga dapat melewati sistem filter website berbasis contenttext yang ada. Untuk kelanjutan penelitian ini, disarankan dilakukan penelitian lebih lanjut dengan data pelatihan yang lebih besar dan memiliki informasi yang akurat, yang dapat mewakili
suatu kelas tertentu, dilakukan analisis terhadap content-type yang lain dari website, serta mengkombinasikan sistem filter Bayesian Network dengan sistem filter yang lain sehingga tingkat akurasi dapat lebih tinggi.
DAFTAR PUSTAKA Campos, Luis M. de., dkk. (2002). Ant Colony Optimization for Learning Bayesian Networks. International Journal of Approximate Reasoning 31 (2002) 291–311 Guermazi, Radhouane, dkk. (2007). Combining Classifiers for Web Violent Content Detection and Filtering. ICCS 2007, Part III, LNCS 4489, pp. 773–78. Jaakkola, Tommi, dkk. (2010). Learning Bayesian Network Structure using LP Relaxations. Proceedings of the 13th International Conference on Artificial Intelligence and Statistics (AISTATS). Chia Laguna Resort, Sardinia, Italy. Volume 9 of JMLR: W&CP 9. Lee, Pui Y., dkk. (2002). Neural Networks for Web Content Filtering. Nanyang Technological University. Jurnal IEEE Intelligent Systems. Lewis. David D. (2000). Stop word list of the Smart Information Retrieval Project. http://jmlr.org/papers/volume5/lewis04a/a11-smart-stop-list/english.stop. Diakses tanggal 30 Januari 2013 02:40 Pasaribu, Hiskia E., dkk. (2010). Klasifikasi Dokumen Web Menggunakan Version Space Support Vector Machine. Fakultas Informatika Institut Teknologi Telkom, Bandung. Konferensi Nasional Sistem dan Informatika (2010). KNS I10-059 Pop, Ioan. (2006). An approach of the Naive Bayes classifier for the document classification. General Mathematics Vol. 14, No. 4 (2006), 135–138. Sahlan, La Ode. (2011). Penerapan Metode Naive Bayesian Dalam Pengklasifikasian Dokumen Web. Makassar. Skripsi, Jurusan Matematika Universitas Hasanuddin. Sanghai, Sumit., dkk. (2003). Dynamic probabilistic relational models. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, pp. 992.1002, Shadiq, Muh. Ammar. (2009). Keoptimalan Naïve Bayes dalam Klasifikasi. Program Studi Ilmu Komputer Fakultas Pendidikan Matematika Dan Ilmu Pengetahuan Alam Universitas Pendidikan Indonesia. Tala, Fadillah Z. (2003). A Study of Stemming Effects on Information Retrieval in Bahasa Indonesia. Master of Logic Project, Institute for Logic, Language and Computation, Universiteit van Amsterdam, Netherlands. Urvoy, Tangui, dkk. (2008). Tracking Web Spam with HTML Style Similarities. ACM Journal Name, Vol. V, No. N, Month 2006, Pages 1–26.
Akurasi (%)
Nilai Akurasi Terhadap Jumlah Website Pelatihan 100 80 60 40 20 0 1 2 3 4 5 6 7 8 9 1011121314151617181920 Jumlah Website Pelatihan
Gambar 1. Grafik tingkat akurasi terhadap jumlah website pelatihan
False Negatif (%)
Nilai False Negatif Terhadap Jumlah Website Pelatihan 50 40 30 20 10 0 1 2 3 4 5 6 7 8 9 1011121314151617181920 Jumlah Website Pelatihan
Gambar 2. Grafik false negatif terhadap jumlah website pelatihan
False Positif (%)
Nilai False Positif Terhadap Jumlah Website Pelatihan 60 50 40 30 20 10 0 1 2 3 4 5 6 7 8 9 1011121314151617181920 Jumlah Website Pelatihan
Gambar 3. Grafik false positif terhadap jumlah website pelatihan
