naive bayes

TUGAS 3

NAIVE BAYES

NAMA : A A Gede Oka Kessawa A

NIM : 0904505033

JURUSAN TEKNIK INFORMATIKA

UNIVERSITAS UDAYANA

2012

Klasifikasi Naive Bayes

Teknik clasifikasi Bayes adalah sebuah bentuk klasifikasi probabilistik yang

berdasarkan Teorema Bayes (dari statistik Bayesian) dengan strong (naive)

independence assumptions atau asusmsi bebas. Sebuah aturan yang lebih deskriptif

untuk dasar sebuah model yang akan menjadi “model bercirikan kebebasan”.

Dalam sebuah aturan yang mudah, sebuah klasifikasi Naive Bayes diasumsikan

bahwa ada atau tidaknya ciri tertentu dari sebuah kelas tidak ada hubungannya dengan

ciri dari kelas lainnya. Untuk contohnya, buah akan dianggap sebagai sebuah apel jika

berwarna merah, berbentuk bulat dan berdiameter sekitar 6 cm. Walaupun jika ciri-ciri

tersebut bergantung satu sama lainnya atau keberadaanya merupakan ciri dari kelas

lainnya, klasifikasi Naive Bayes tetap menganggap bagian-bagian dari kelas tersebut

masing-masing memberikan jawaban bahwa kelas itu adalah apel.

Berdasarkan dari ciri alami dari sebuah model probabilitas, klasifikasi naive

Bayes bisa dibuat lebih efisien dalam bentuk pembelajaran. Dalam beberapa bentuk

praktiknya, parameter untuk perhitungan model naive bayes menggunakan metode

maximum likelihood, atau kemiripan tertinggi.

Gambar 1 Ilustrasi naive Bayes

Jadi sebuah data akan dilakukan klasifikasi berdasarkan sekelompok data yang sudah

mengalami proses pembelajaran untuk menentukan termasuk data yang mana jika

datum tersebut diklasifikasikan.

Data latih untuk Teorema Bayes membutuhkan paling tidak perkalian kartesius

dari seluruh kelompok atribut yang mungkin, jika misalkan ada 16 atribut yang masing-

masingnya berjenis Boolean tanpa missing value, maka data latih minimal yang

dibutuhkan oleh Teorema bayes untuk digunakan dalam klasifikasi adalah 216 = 65.536

data, sehingga ada 3 masalah yang dihadapi untuk menggunakan teorema bayes dalam

pengklasifikasian, yaitu :

1. Kebanyakan data latih tidak memiliki varian klasifikasi sebanyak itu (oleh

karenanya sering diambil sample) .

2. Jumlah atribut dalam data sample dapat berjumlah lebih banyak (lebih dari 16)

3. Jenis nilai atribut dapat berjumlah lebih banyak [lebih dari 2 – Boolean] terlebih

lagi untuk jenis nilai atribut yang bersifat tidak terbatas 1 - ∞ seperti numeric

dan kontiniu.

4. Jika suatu data X tidak ada dalam data latih, maka data X tidak dapat di

klasifikasikan, karena peluang untuk data X di klasifikasikan kedalam suatu

kelas adalah sama untuk tiap kelas yang ada.

Untuk mengatasi berbagai permasalahan diatas, berbagai varian dari

pengklasifikasian yang menggunakan teorema bayes diajukan, salah satunya adalah

Naïve Bayes, yaitu penggunaan Teorema Bayes dengan asumsi keidependenan atribut.

Asumsi keidependenan atribut akan menghilangkan kebutuhan banyaknya jumlah data

latih dari perkalian kartesius seluruh atribut yang dibutuhkan untuk mengklasifikasikan

suatu data.

Gambar 2 : Ilustrasi Naive Bayes

Dampak negative dari asumsi naïve tersebut adalah keterkaitan yang ada antara

nilai-nilai atribut diabaikan sepenuhnya. Dampak ini secara intuitif akan berpengaruh

dalam pengklasifikasian, namun percobaan empiris mengatakan sebaliknya. Hal ini

tentu saja cukup mengejutkan, karena dalam pengaplikasian dunia nyata, asumsi

diabaikannya keterkaitan antara atribut selalu dilanggar.

Pertanyaan yang muncul adalah apakah yang menyebabkan baiknya performa

yang didapatkan dari pengaplikasian asumsi naïve ini? Karena secara intuitif, asumsi

keidependenan atribut dalam dunia nyata hampir tidak pernah terjadi. Seharusnya

dengan asumsi tersebut performa yang dihasilkan akan buruk.

Domingos dan Pazzani (1997) pada papernya untuk menjelaskan performa naïve

bayes dalam fungsi zero-one loss. Fungsi zero-one loss ini mendefinisikan error hanya

sebagai pengklasifikasian yang salah. Tidak seperti fungsi error yang lain seperti

squared error, fungsi zero-one loss tidak member nilai suatu kesalahan perhitungan

peluang selama peluang maksimum di tugaskan kedalam kelas yang benar. Ini berarti

bahwa naïve bayes dapat mengubah peluang posterior dari tiap kelas, tetapi kelas

dengan nilai peluang posterior maksimum jarang diubah. Sebagai contoh, diasumsikan

peluang sebenarnya dari dan , sedangkan peluang yang

dihasilkan oleh naïve bayes adalah dan . Nilai peluang

tersebut tentu saja berbeda jauh, namun pilihan kelas tetap tidak terpengaruh.

Bukti Optimal Naive Bayes

Seperti yang telah di ketahui bahwa naïve Bayes bernilai optimal ketika seluruh

atribut bernilai independen terhadap atribut lainnya. Pada bagian ini akan dibandingkan

antara nilai naïve bayes yang seluruh atribut independen terhadap atribut lainnya dan

nilai naïve bayes yang tidak seluruh atributnya independen.

Misalkan sebuah data latih, dengan atribut A, B dan C yang bersifat Boolean,

dan kelas dan , dengan peluang yang sebanding untuk tiap kelas .

A dan B berkorelasi penuh (A = B), sehingga B dapat diabaikan.

Prosedur klasifikasi optimal untuk sebuah data tuple adalah untuk menugaskan data

tuple tersebut kedalam kelas positif jika :

Kelas positif :

Dan sebaliknya, menugaskan kelompok atribut kepada kelas negatif jika :

Kelas negatif :

Kelas acak :

Sedangkan prosedur klasifikasi Naïve Bayes yang tidak optimal

memperhitungkan juga nilai B seperti halnya nilai B sama sekali tidak berkorelasi

dengan nilai A. hal ini sama dengan menghitung nilai A dua kali. Untuk naïve bayes

rumusnya adalah :

Kelas positif :

Kelas negatif :

Kelas Acak :

Dengan mengaplikasikan naïve bayes untuk pengklasifikasian yang optimal,

maka dapat di representasikan sebagai

Karena , maka nilai dan tidak perlu dihitung dan dapat

diabaikan dalam perhitungan, nilai P(A) dan P(C) juga mengeliminasi satu sama lainnya

dalam operasi pengurangan, sehingga nilai P(A) dan nilai P(C) tidak perlu di hitung,

sehingga setelah pengeliminasian perhitungan yang tidak di perlukan dan didapatkan :

Untuk perhitungan korelasi optimal. Sedangkan untuk perhitungan korelasi

dengan Naïve Bayes :

Karena dalam peluang nilai peluang maksimal adalah 1, maka dapat dituliskan :

Misalkan dan Sehingga rumusnya menjadi :

untuk nilai peluang optimal dengan asumsi keidependenan atribut.

untuk nilai peluang naïve bayes tanpa keidependenan atribut.

Kedua kurva fungsi diatas digambarkan sebagai berikut :

Gambar 2 Kurva Perbandingan Naive Bayes

Kurva diatas memperlihatkan bahwa walaupun asumsi keidependenan atribut

dilanggar, karena B=A, pengklasifikasian naïve bayes dengan asumsi atribut yang tidak

independen tidak sama dengan pengklasifikasian naive bayes optimal dengan

keidependenan atribut hanya di dua bagian sempit, satu diatas kurva dan satu lagi

dibawah, di tempat lain, naïve bayes menghasilkan klasifikasi yang benar, yaitu pada

(0,1) ( 0.5,0.5) (1,0) ini menunjukkan bahwa penggunaan klasifikasi naïve bayes bisa

lebih luas daripada yang dikira sebelumnya.

Bentuk Klasifikasi

Klasifikasi Naive Bayes merupakan bentuk klasifikasi yang melakakukan teknik

pengklasifikasian dengan menghitung derajat kecocokan. Jika derajat kecocokannya

tinggi, maka data tersebut akan diklasifikasikan ke dalam kelas yang bersesuaian. Jika

klasifikasi Vnb memiliki atribut a1, a2, ... an, maka hasil dari Vnb dapat dihitung dengan,

V nb=argmaxvj∈V P (vj ) ΠP ( ai|v j )

Atau bisa dijabarkan menjadi bentuk seperti berikut.

V nj=P (v j ) P (a1 …an∨v j)

P(a1…an)

Menurut perhitungan di atas, masing-masing atribut akan menghasilkan nilai posterior

tersendiri, sehingga bisa juga dijabarkan per masing-masing atribut. Sehingga akan

lebih jelas dalam jabaran berikut.

V nj=P(vj)(P ( a1|v j )∗P ( a1|v j )∗…∗P (an|v j ))

Atau tiap masing-masing atribut yang dilambangkan dengan a i Dimana, P(ai|Vj)

dihitung dengan menggunakan estimasi-m

P (ai|v j )=nc+mp

n+m

Dimana:

n= jumlah contoh dimana v = vj

nc = jumlah contoh dimana v = vj dan a = ai

p = prioritas yang dihitung untuk P (ai|v j )

m = persamaan ukuran sampel

vj = dimana atribut sama dengan kasus tertentu, misalnya YES atau NO, diterima

atau tidak

untuk nilai m, ditentukan sewenang-wenang namun dari beberapa sumber, nilai

m disesuaikan dengan banyak jenis dari atribut. Sedangkan untuk nilai p, ditentukan

berdasarkan banyak kemungkinan yang muncul, perhitungan tersebut didapat dari 1

dibagi dengan banyak kemungkinan, misalkan ada 3 kemungkinan, maka nilai dari p

adalah 1/3 = 0,33

Model dan Langkah-Langkah Klasifikasi Naive Bayes

Naive Bayes adalah sebuah bentuk klasifikasi yang tentu saja tujuannya adalah

untuk mengklasifikasikan terhadap data yang masuk atau diuji. Klasifikasi naive Bayes

adalah bentuk klasifikasi yang berdasarkan tentang pembelajaran, jadi perhitungan dan

klasifikasi akan terbentuk mengikuti data-data yang sudah digunakan untuk proses

pembelajaran.

Berikut adalah contoh data yang mengikuti proses pembelajaran.

Tabel 1 Data Pembelajaran

no Atribut1 Atribut2 Atribut3 Result/hasil

1 X A 1 YA

2 X B 2 TIDAK

3 Y A 3 YA

4 X B 3 TIDAK

... ... ... ... ...

n X B 1 YA

dari data yang digunakan untuk pembelajaran tersebut, dilakukan pengujian terhadap

sebuah data, misalkan:

Tabel 2 Data diuji

Atribut1 Atribut2 Atribut3 Result/hasil

X A 2 ?

Untuk mencari apakah hasil bernilai ya atau tidak, dilakukan proses penghitungan

derajat kecocokan berdasarkan jumlah data bersesuaian per atributnya.

Tabel 3 tabel kecocokan atribut

no X dan YA A dan YA 2 dan YA

1 TRUE TRUE FALSE

2 FALSE FALSE FALSE

3 FALSE TRUE FALSE

4 FALSE FALSE FALSE

...

n TRUE FALSE FALSE

Dari Tabel 3 tersebut, didapat data yang akan digunakan untuk mencari derajat

kecocokan per atribut.

Tabel 4 tabel kecocokan per atribut

YA TIDAK

X X

n 3 n 3

n_c 2 n_c 1

p 0,5 p 0,5

m 3 m 3

A A

n 2 n 2

n_c 2 n_c 0

p 0,5 p 0,5

m 3 m 3

2 2

n 1 n 1

n_c 0 n_c 1

p 0,33 p 0,33

m 3 m 3

Dari tabel tersebut, lalu dihitung nilai poseterior per atribut, per kemungkinan.

1) P ( X|YA )=nc+m∗p

n+m=2+3∗0,5

3+3=0,583

2) P ( A|YA )=nc+m∗p

n+m=2+3∗0,5

2+3=0,5

3) P (2|YA )=nc+m∗p

n+m=0+3∗0,5

1+3=0,375

Sehingga,

V (YA )=P (YA )∗P ( X|YA )∗P ( A|YA )∗P (2|YA )

V (YA )=0,5∗0,583∗0,5∗0,375=0,0546

Dihitung juga untuk V(TIDAK)

1) P ( X|TIDAK )=nc+m∗p

n+m=1+3∗0,5

3+3=0,416

2) P ( A|TIDAK )=nc+m∗p

n+m=0+3∗0,5

2+3=0,3

3) P (2|TIDAK )=nc+m∗p

n+m=1+3∗0,5

1+3=0,625

Sehingga,

V (TIDAK )=P (TIDAK )∗P ( X|TIDAK )∗P ( A|TIDAK )∗P (2|TIDAK )

V (TIDAK )=0,5∗0,416∗0,3∗0,625=0,039

V(YA) =0,0546, V(TIDAK)=0,039

Karena V(YA)>V(TIDAK) maka data yang diuji tersebut termasuk tidak.

Contoh Kasus Naive Bayes

Sebuah Perusahaan bernama perusahaan NABA memiliki beberapa anak

perusahaan. Salah satu anak perusahaan tersebut sedang melakukan pencarian pegawai

dan salah seorang analisis di perusahaan tersebut memiliki beberapa orang anak yang

ingin dimasukkan ke dalam perusahaan tersebut. Berikut adalah data anak tersebut:

Tabel 5 Data anak diuji

no

jenis

kelamin

pendidika

n pengalaman kerja biaya administrasi

1 Laki SMA 1 100000

2 Perempuan SMA 3 300000

3 Laki Diploma 3 500000

4 Perempuan Sarjana 2 100000

Kemudian bapak tersebut memiliki data salah satu anak perusahaan dan melakukan

klasifikasi apakah anak-anak tersebut akan diterima atau tidak. Berikut data penerimaan

pegawai tersebut

Tabel 6 data penerimaan pegawai

noJenis

Kelamin

Pendidik

an

Lama

Pengalam

an Kerja

Biaya

Administra

si

status

1

Perempua

n SMA 4 100000

diterim

a

2

Perempua

n SMA 5 300000

diterim

a

3

Perempua

n Diploma 3 300000

diterim

a

4

Perempua

n SMA 2 300000 tidak

5 Laki Sarjana 3 100000

diterim

a

6 Laki SMA 1 100000 tidak

7 Laki Diploma 1 300000 tidak


diterim

a

9

Perempua

n Diploma 2 100000 tidak


diterim

a

11

Perempua

n Sarjana 4 100000

diterim

a

12

Perempua

n Diploma 2 300000

diterim

a

13 Laki Sarjana 1 500000

diterim

a

14 Laki Sarjana 1 100000 tidak

15

Perempua

n SMA 5 100000

diterim

a

16

Perempua

n Sarjana 3 100000

diterim

a

17

Perempua

n Sarjana 1 100000 tidak




Lalu perhitunganpun dilakukan

Tabel 7 Pengujian Data 1

NoLaki dan Diterima

SMA dan diterima 1 tahun dan diterima

100ribu dan diterima

1 FALSE TRUE FALSE TRUE2 FALSE TRUE FALSE FALSE3 FALSE FALSE FALSE FALSE4 FALSE FALSE FALSE FALSE5 TRUE FALSE FALSE TRUE6 FALSE FALSE FALSE FALSE7 FALSE FALSE FALSE FALSE8 TRUE FALSE FALSE TRUE9 FALSE FALSE FALSE FALSE

10 TRUE FALSE FALSE FALSE11 FALSE FALSE FALSE TRUE12 FALSE FALSE FALSE FALSE13 TRUE FALSE TRUE FALSE14 FALSE FALSE FALSE FALSE15 FALSE TRUE FALSE TRUE16 FALSE FALSE FALSE TRUE17 FALSE FALSE FALSE FALSE18 FALSE FALSE FALSE FALSE19 FALSE FALSE FALSE FALSE20 FALSE FALSE FALSE FALSE

Tabel 8 data 1

yes no Laki Laki n 10 n 10 n_c 4 n_c 6 p 0,5 p 0,5 m 4 m 4

P(Laki|YES) 0,428571429 P(LAKI|NO)0,57142

9 SMA SMA n 8 n 8 n_c 3 n_c 5 p 0,33 p 0,33 m 4 m 4

P(SMA|YES) 0,36 P(SMA|NO)0,52666

7 1 1

n 6 n 6 n_c 1 n_c 5 p 0,2 p 0,2 m 4 m 4 P(1|YES) 0,18 P(1|NO) 0,58 100000 100000 n 11 n 11 n_c 6 n_c 5 p 0,33 p 0,33 m 4 m 4

P(100000|YES) 0,488 P(100000|NO)0,42133

3

P(YES) 0,006776229 P(NO)0,03677

2Karena P(YES)<P(NO) sehingga, data peserta uji satu tidak diterima

Tabel 9 Pengujian Data 2No

Perempuan dan Diterima

SMA dan diterima 3 tahun dan diterima


1 TRUE TRUE FALSE FALSE2 TRUE TRUE FALSE TRUE3 TRUE FALSE TRUE TRUE4 FALSE FALSE FALSE FALSE5 FALSE FALSE TRUE FALSE6 FALSE FALSE FALSE FALSE7 FALSE FALSE FALSE FALSE8 FALSE FALSE TRUE FALSE9 FALSE FALSE FALSE FALSE

10 FALSE FALSE TRUE TRUE11 TRUE FALSE FALSE FALSE12 TRUE FALSE FALSE TRUE13 FALSE FALSE FALSE FALSE14 FALSE FALSE FALSE FALSE15 TRUE TRUE FALSE FALSE16 TRUE FALSE TRUE FALSE17 FALSE FALSE FALSE FALSE18 FALSE FALSE FALSE FALSE19 FALSE FALSE FALSE FALSE20 FALSE FALSE FALSE FALSE

Tabel 10 data 2yes no Perempuan Perempuan n 10 n 10 n_c 7 n_c 3 p 0,5 p 0,5 m 4 m 4

P(Perempuan|YES) 0,642857143

P(Perempuan|NO)

0,357143

SMA SMA n 8 n 8 n_c 3 n_c 5 p 0,33 p 0,33 m 4 m 4

P(SMA|YES) 0,36 P(SMA|NO)0,52666

7 3 3 n 6 n 6 n_c 5 n_c 1 p 0,2 p 0,2 m 4 m 4 P(3|YES) 0,58 P(3|NO) 0,18 300000 300000 n 8 n 8 n_c 4 n_c 4 p 0,33 P 0,33 m 4 M 4

P(300000|YES) 0,443333333 P(300000|NO)0,44333

3

P(YES) 0,029754 P(NO)0,00750

5Karena P(YES)>P(NO) sehingga, data peserta uji dua diterima


No Laki dan DiterimaDiploma dan diterima 3 tahun dan diterima


1 FALSE FALSE FALSE FALSE2 FALSE FALSE FALSE FALSE3 FALSE TRUE TRUE FALSE4 FALSE FALSE FALSE FALSE5 TRUE FALSE TRUE FALSE6 FALSE FALSE FALSE FALSE7 FALSE FALSE FALSE FALSE8 TRUE TRUE TRUE FALSE9 FALSE FALSE FALSE FALSE

10 TRUE TRUE TRUE FALSE11 FALSE FALSE FALSE FALSE12 FALSE TRUE FALSE FALSE13 TRUE FALSE FALSE TRUE14 FALSE FALSE FALSE FALSE15 FALSE FALSE FALSE FALSE16 FALSE FALSE TRUE FALSE17 FALSE FALSE FALSE FALSE18 FALSE FALSE FALSE FALSE19 FALSE FALSE FALSE FALSE20 FALSE FALSE FALSE FALSE

Tabel 12 data 3yes no Laki Laki n 10 n 10 n_c 4 n_c 6 p 0,5 p 0,5 m 4 m 4

P(Laki|YES) 0,428571429 P(LAKI|NO)0,57142

9 Diploma Diploma n 6 n 6 n_c 4 n_c 2 p 0,33 p 0,33 m 4 m 4

P(Diploma|YES) 0,532 P(Diploma|NO) 0,332

3 3 n 6 n 6 n_c 5 n_c 1 p 0,2 p 0,2 m 4 m 4 P(3|YES) 0,58 P(3|NO) 0,18 500000 500000 n 1 n 1 n_c 1 n_c 0 p 0,33 p 0,33 m 4 m 4

P(500000|YES) 0,464 P(500000|NO) 0,264

P(YES) 0,03067968 P(NO)0,00450



NoPerempuan dan Diterima

Sarjana dan diterima

2 tahun dan diterima


1 TRUE FALSE FALSE TRUE2 TRUE FALSE FALSE FALSE3 TRUE FALSE FALSE FALSE4 FALSE FALSE FALSE FALSE5 FALSE TRUE FALSE TRUE6 FALSE FALSE FALSE FALSE7 FALSE FALSE FALSE FALSE8 FALSE FALSE FALSE TRUE9 FALSE FALSE FALSE FALSE

10 FALSE FALSE FALSE FALSE11 TRUE TRUE FALSE TRUE12 TRUE FALSE TRUE FALSE13 FALSE TRUE FALSE FALSE14 FALSE FALSE FALSE FALSE15 TRUE FALSE FALSE TRUE16 TRUE TRUE FALSE TRUE17 FALSE FALSE FALSE FALSE18 FALSE FALSE FALSE FALSE19 FALSE FALSE FALSE FALSE20 FALSE FALSE FALSE FALSE

Tabel 14 data 4yes no Perempuan Perempuan N 10 n 10 n_c 7 n_c 3 P 0,5 p 0,5 M 4 m 4

P(Perempuan|YES) 0,642857143

P(Perempuan|NO)

0,357143

SMA SMA N 6 n 6 n_c 4 n_c 2 P 0,33 p 0,33 M 4 m 4 P(SMA|YES) 0,532 P(SMA|NO) 0,332 3 3 N 4 n 4 n_c 1 n_c 3 P 0,2 p 0,2 M 4 m 4 P(3|YES) 0,225 P(3|NO) 0,475 100000 100000 N 11 n 11 n_c 6 n_c 5 P 0,33 p 0,33 M 4 m 4

P(300000|YES) 0,488 P(300000|NO)0,42133

3

P(YES) 0,0187758 P(NO)0,01186


Dari 4 data tersebut, didapatkan kesimpulan bahwa

data Status1 Tidak diterima2 Diterima3 Diterima4 Diterima

Daftar Pustaka

- Wikipedia, naive bayes clasifiers, http://www.saylor.org/site/wp-content/uploads/2011/02/Wikipedia-Naive-Bayes-Classifier.pdf ,diunduh pada 10 Mei 2012

- Meisner, E. Naive Bayes example, 2003 http://www.inf.u-szeged.hu/~ormandi/ai2/06-naiveBayes-example.pdf , diunduh pada 10 Mei 2012

- Optimality of Naive Bayes, http://courses.ischool.berkeley.edu/i290-dm/s11/SECURE/Optimality_of_Naive_Bayes.pdf , diunduh pada 10 Mei 2012

- Frank, E. Naive Bayes for Text Classification with Unbalanced Classes. Computer Science Department, University of Waikato, New Zealand. http://www.cs.waikato.ac.nz/~eibe/pubs/FrankAndBouckaertPKDD06new.pdf, diunduh pada 10 Mei 2012

naive bayes

Documents