Algoritma Bayesian Filter

Bayesian filter merupakan metode terbaru yang digunakan untuk mendeteksi spam mail. Algoritma ini memanfaatkan metode probabilitas dan statistik yang dikemukakan oleh ilmuwan Inggris Thomas Bayes, yaitu memprediksi probabilitas di masa depan berdasarkan pengalaman di masa sebelumnya. Dua kelompok peneliti, satu oleh Pantel dan Lin, dan yang lain oleh Microsoft Research memperkenalkan metode statistik Bayesian ini pada teknologi anti spam filter. Tetapi yang membuat algoritma Bayesian filtering ini popular adalah pendekatan yang dilakukan oleh Paul Graham. 

 Bayesian filter mendeteksi spam dengan cara menghitung probabilitas dari suatu pesan (mail) berdasarkan isinya. Probabilitas ini dapat dihitung dengan terlebih dahulu membuat suatu database spam-mail dan database non spam-mail. Kemudian dengan suatu metode training, software anti spam yang menggunakan algoritma Bayesian dapat dilatih untuk melihat kata-kata yang sering digunakan pada spam-mail, sehingga pada akhirnya dihasilkan filter anti spam yang akurat dengan sesedikit mungkin false positives. False positives adalah e-mail legal yang ditujukan kepada penerima, tetapi karena kesalahan dari filter anti spam, dikategorikan menjadi spam-mail.

Pada dasarnya, algoritma Bayesian filter merupakan merupakan pengembangan dari algoritma penilaian pesan (scoring content-based filter, hampir sama dengan keywords filtering) yaitu filter mencari karakteristik kata-kata yang banyak digunakan pada spam-mail, kata-kata ini diberi nilai individual, dan nilai spam secara keseluruhan dihitung dari nilai individual tersebut. Tetapi algoritma ini memiliki kelemahan yaitu karakteristik kata-kata pada spam-mail dan non-spam mail akan berbeda-beda untuk setiap individu. Kata “business” misalnya yang untuk sebagian orang akan termasuk pada karakteristik kata-kata pada spam-mail, tetapi untuk perusahaan tertentu yang bergerak di bidang itu, kata “business” tersebut akan termasuk pada non spam-mail. Dapat dikatakan bahwa algoritma scoring content-based filter ini tidak kompatibel.

Lain halnya dengan scoring content-based filter, Bayesian filter akan membuat daftar karakteristik kata-kata spam dan non-spam mail secara otomatis. Tentunya terlebih dahulu , kita harus mengklasifikasikan e-mail – e-mail mana saja yang termasuk spam-mail dan mana yang termasuk non-spam mail. Bayesian filter akan menghitung probabilitas dari kata-kata yang umum digunakan pada spam mail berdasarkan klasifikasi ini. Karakteristik dari spam-mail yang dapat diidentifikasi antara lain berdasarkan kata-kata pada body message, header message, dan juga kode HTML (seperti pemberian background warna).

3.1. Perhitungan Probabilitas Berdasarkan Algoritma Bayesian

Pada awalnya, Bayesian filter ini harus di-training terlebih dahulu menggunakan sejumlah spam mail dan sejumlah ham mail. Bayesian filter akan menghitung probabilitas lokal dari suatu kata, misalnya kata “adult”, untuk muncul di kelompok spam mail. Probabilitas lokal ini dapat dirumuskan sebagai berikut :

 

                        P_{local – spam} = N _spam / (N _spam + N _non-spam)         …………..(1.1)

dimana : P_{local – spam}    = probabilitas suatu kata “x” terdapat pada spam-mail

               N _spam           = jumlah spam mail dengan kata “x” di dalamnya

               N _non-spam        = jumlah non-spam mail dengan kata “x” di dalamnya

Atau rumus lain yang digunakan untuk menghitung probabilitas lokal dari suatu kata, terutama jika nilai  N _spam dan N _non-spam kecil adalah bahwa probabilitas akan terletak di sekitar probabilitas ketidakpastian (P = 0.5) :

 

                                                P_{local – spam} = 0.5 +       …………….(1.2)

            dimana : C₁ dan C₂ adalah konstanta yang dipilih melalui eksperimen

Misalkan jika C₁ = 2 dan C₂ = 1, dan jika suatu kata “x” hanya ditemukan pada satu spam-mail dan tidak ditemukan sama sekali pada ham mail, maka probabilitas lokal suatu message baru yang mengandung kata tersebut dikategorikan sebagai spam adalah 0.75. Probabilitas ini tidak terlalu tinggi untuk dikategorikan sebagai spam. Sementara jika kata tersebut ditemukan pada sepuluh spam-mail dan tidak ditemukan sama sekali pada ham mail, maka probabilitas lokal-nya akan sama dengan 95.4%, yang cukup tinggi untuk dikategorikan sebagai spam. Perhitungan probabilitas ini jika dilakukan dengan rumus (1.1), akan memberikan hasil yang terlalu “kasar”, yaitu probabilitas mutlak = 1.

Probabilitas lokal dari masing-masing kata tersebut kemudian menggunakan aturan rantai (chain rule) Bayesian untuk menentukan probabilitas total dari suatu message adalah spam. Bayesian chain rule dirumuskan sebagai berikut :

 

        …………………………(1.3)

dimana : a = probabilitas suatu message dikategorikan sebagai spam dengan adanya kata “a” 

               b = probabilitas suatu message dikategorikan sebagai spam dengan adanya kata “b” 

Untuk menentukan probabilitas total, perhitungan di atas dilakukan terus menerus secara iterative dari  probabilitas lokal masing-masing kata pada message tersebut.

            Sebagai salah satu cara untuk menghindari false positives, filter dapat di-training untuk mengkategorikan message sebagai spam hanya jika :

   ……………… (1.4)

dimana :           = probabilitas total suatu message dengan kata-kata tertentu dikategorikan sebagai spam

                   =  probabilitas total suatu message dengan kata-kata tertentu dikategorikan sebagai legitimate mail

Seperti telah dibahas di atas, bahwa setiap kata memiliki probabilitas lokal untuk muncul pada spam-mail dan probabilitas lokal untuk muncul pada legitimate-mail. Berdasarkan probabilitas lokal tersebut, suatu message mempunyai probabilitas total untuk dikategorikan sebagai spam mail atau sebagai legitimate mail. Karena false positives dianggap lebih beresiko karena dapat menghilangkan mail yang penting bagi seseorang atau suatu perusahaan, maka dipilih nilai l tertentu pada persamaan(1.4) di atas untuk memperkecil kemungkinan terjadinya false positives.

Kelemahan dari Bayesian chain rule ini adalah tiap kata diasumsikan terpisah dan tidak tergantung satu sama lain. Padahal dalam menganalisis suatu teks, setiap kata saling berhubungan satu dengan yang lain. Kelemahan ini diatasi oleh algoritma probabilitas chi-squared yang dikembangkan pada proyek SpamBayes (akan dibahas berikut ini).

            3.2. Pengembangan Algoritma Bayesian

Salah satu pengembangan algoritma Bayesian filter adalah proyek SpamBayes yang ditujukan untuk melakukan pembaharuan dari algoritma Bayesian filter yang pertama kali dikembangkan oleh Paul Graham. Proyek SpamBayes ini dimotori oleh Gary Robinson dan Tim Peters. Secara prinsip proyek SpamBayes ini sama dengan algoritma Bayesian dari Paul Graham. Kelebihannya adalah SpamBayes dapat mengkategorikan mail menjadi spam-mail, non-spam mail (ham), dan unsure-mail. Unsure-mail dapat dikatakan sebagai pesan yang tidak dapat dikategorikan secara rating menjadi spam mail ataukah ham mail. Pengkategorian seperti ini juga dilakukan dengan cara yang sama yaitu dengan memberikan algoritma belajar pada SpamBayes berdasarkan beberapa e-mail yang dikategorikan sebagai spam mail atau ham mail.