TEORI DEMPSTER-SHAFER

Teori Dempster-Shafer adalah teori matematika untuk pembuktian berdasarkan belief functions(fungsi kepercayaan) dan plausible reasonin (penalaran yang masuk akal). Digunakan untuk mengkombinasikan potongan informasi (fakta) yang terpisah untuk mengkalkulasi kemungkinan dari suatu peristiwa.Teori Dempster-Shafer adalah suatu teori matematika untuk pembuktian (Kusumadewi, 2003) berdasarkan belief functions and plausible reasoning (fungsi kepercayaan dan pemikiran yang masuk akal), yang digunakan untuk mengkombinasikan potongan informasi yang terpisah (bukti) untuk mengkalkulasi kemungkinan dari suatu peristiwa. Teori ini dikembangkan oleh Arthur P. Dempster dan Glenn Shafer.

Ada berbagai macam penalaran dengan model yang lengkap dan sangat konsisten, tetapi pada kenyataannya banyak permasalahan yang tidak dapat terselesaikan secara lengkap dan konsisten. Ketidakkonsistenan yang tersebut adalah akibat adanya penambahan fakta baru. Penalaran yang seperti itu disebut dengan penalaran non monotonis. Untuk mengatasi ketidakkonsistenan tersebut maka dapat menggunakan penalaran dengan teori Dempster-Shafer. Secara umum teori Dempster-Shafer ditulis dalam suatu interval:

[Belief,Plausibility]



Belief (Bel) adalah ukuran kekuatan evidence dalam mendukung suatu himpunan proposisi. Jika bernilai 0 maka mengindikasikan bahwa tidak ada evidence, dan jika bernilai 1 menunjukkan adanya kepastian. Dimana nilai bel yaitu (0-0.9).
Plausibility (Pl) dinotasikan sebagai : Pl(s) = 1 – Bel (-s) Plausibility juga bernilai 0 sampai 1. Jika yakin akan-s, maka dapat dikatakan bahwa Bel(-s)=1, dan Pl(-s)=0.

Contoh :
 Diketahui nilai belief  adalah 0,5 dan nilai plausibility adalah 0,8 untuk proposisi “the cat in the box is dead”
 Bel = 0,5
 Fakta yang mendukung proposisi tersebut memiliki nilai kepercayaan sebesar 0,5
  Pl = 0,8
  Fakta yang melawan proposisi tersebut hanya memiliki nilai kepercayaan sebesar 0,2

Pada teori Dempster-Shafer dikenal adanya frame of  discernment (θ) yaitu semesta pembicaraan dari sekumpulan hipotesis. Nilai probabilitas densitas (m) mendefinisikan elemen-elemen θ  serta semua subsetnya. Jika θ berisi n elemen, subset dari θ adalah 2n

FAKTOR KEPASTIAN (CERTAINTY FACTOR)

Certainty Factor (CF) menunjukkan ukuran kepastian terhadap suatu fakta atau aturan.

                                CF[h,e]  = MB[h,e] – MD[h,e]
Dengan :
CF[h,e]  = faktor kepastian
MB[h,e] = ukuran kepercayaan/tingkat keyakinan terhadap hipotesis h, jika diberikan/dipengaruhi evidence  e (antara 0 dan 1)
MD[h,e] = ukuran ketidakpercayaan/ tingkat h,= ketidakyakinan terhadap hipotesis h, jika diberikan/dipengaruhi evidence e (antara 0 dan 1)

3 hal yang mungkin terjadi :

1. Beberapa evidence dikombinasikan untuk menentukan CF dari suatu hipotesis. Jika e1 dan e2 adalah observasi, maka :

Contoh :

• Misal suatu observasi memberikan kepercayaan terhadap h dengan MB[h,e1]= 0,3 dan MD[h,e1] = 0 maka CF[h,e1]=0,3 – 0 = 0,3

• Jika ada observasi baru dengan MB[h,e2]=0,2 dan MD[h,e2] = 0, maka : MB[h,e1 ^ e2] = 0,3 + 0,2 * (1-0,3) = 0,44

MD[h,e1 ^ e2] = 0

CF[h,e1 ^ e2] = 0,44 – 0 = 0,44

· Asih menderita bintik-bintik di wajahnya. Dokter memperkirakan Asih terkena cacar dengan kepercayaan MB[cacar,bintik] = 0,80 dan MD[cacar,bintik] = 0,01 maka : CF[cacar,bintik] = 0,80 – 0,01 = 0,79

· Jika ada observasi baru bahwa Asih juga panas badan dengan kepercayaan MB[cacar,panas] = 0,7 dan MD[cacar,panas]=0,08 maka :

MB[cacar,bintik ^ panas] = 0,8 + 0,7 * (1 – 0,8)=0,94

MD[cacar,bintik ^ panas] = 0,01+ 0,08 * (1 – 0,01) = 0,0892

CF[cacar,bintik ^ panas] = 0,94 – 0,0892 = 0,8508

2. CF dihitung dari kombinasi beberapa hipotesis

Jika h1 dan h2 adalah hipotesis maka :

Contoh :

· Misal suatu observasi memberikan kepercayaan terhadap h1 dengan MB[h1,e]=0,5 dan MD[h1,e] = 0,2 maka: CF[h1,e] = 0,5 – 0,2 = 0,3

· Jika observasi tersebut juga memberikan kepercayaan terhadap h2 dengan MB[h2,e]= 0,8 dan MD[h2,e]=0,1, maka: CF[h2,e] = 0,8 – 0,1= 0,7

· Untuk mencari CF[h1^h2,e] diperoleh dari MB[h1^h2,e] = min (0,5 ; 0,8) = 0,5

MD[h1^h2,e] = min (0,2 ; 0,1) = 0,1

CF[h1^h2,e] = 0,5 – 0,1 = 0,4

· Untuk mencari CF[h1h2,e] diperoleh dari MB[h1 h2,e] = max (0,5 ; 0,8) = 0,8

MD[h1h2,e] = max (0,2 ; 0,1) = 0,2

CF[h1h2,e] = 0,8 – 0,2 = 0,6

Asih menderita bintik-bintik di wajahnya. Dokter memperkirakan Asih terkena cacar dengan kepercayaan MB[cacar,bintik]= 0,80  dan MD[cacar,bintik]= 0,01 maka

CF[cacar,bintik] = 0,80 - 0,01 = 0,79

• Jika observasi tersebut juga memberikan kepercayaan bahwa Asih mungkin juga terkena alergi dengan kepercayaan MB[alergi,bintik] = 0,4 dan MD[alergi,bintik]=0,3 maka CF[alergi,bintik] = 0,4 – 0,3 = 0,1 

• Untuk mencari CF[cacar^ alergi, bintik] diperoleh dari MB[cacar^alergi,bintik] = min (0,8 ; 0,4) = 0,4

MD[cacar^alergi,bintik] = min (0,01 ; 0,3) = 0,01

CF[cacar^alergi,bintik] = 0,4 – 0,01 = 0,39

· Untuk mencari CF[cacar alergi bintik] diperoleh dari alergi, MB[cacar alergi,bintik] = max (0,8 ; 0,4) = 0,8

MD[cacar alergi,bintik] = max (0,01 ; 0,3)

CF[cacar alergi,bintik] = 0,8 – 0,3 = 0,5

· Kesimpulan : semula faktor kepercayaan bahwa Asih terkena cacar dari gejala munculnya bintik-bintik di wajahnya adalah 0,79. Demikian pula faktor kepercayaan bahwa Asih terkena alergi dari gejala munculnya bintik-bintik di wajah adalah 0,1. Dengan adanya gejala yang sama mempengaruhi 2 hipotesis yang berbeda ini memberikan faktor kepercayaan :

Asih menderita cacar dan alergi = 0,39

Asih menderita cacar atau alergi = 0,5

Pertengahan tahun 2002, ada indikasi bahwa turunnya devisa Indonesia disebabkan oleh permasalahan TKI di Malaysia. Apabila diketahui MB[devisaturun,TKI] = 0,8 dan MD[devisaturun,TKI] = 0 3 maka CF[devisaturun,TKI] :

CF[devisaturun,TKI] = MB[devisaturun,TKI] - MD[devisaturun,TKI] = 0,8 - 0,3 = 0,5

· Akhir September 2002 kemarau berkepanjangan mengakibatkan gagal panen yang cukup serius, berdampak pada turunnya ekspor Indonesia. Bila diketahui MB[devisaturun,eksporturun] = 0,75 dan MD[devisaturun,eksporturun] = 0,1, maka CF[devisaturun,eksporturun] dan CF[devisaturun,TKI^eksporturun] : 

· CF[devisaturun,eksporturun] = MB[devisaturun,eksporturun] –MD[devisaturun,eksporturun]= 

0,75 – 0,1 = 0,65 

· MB[devisaturun, TKI^eksporturun] = MB[devisaturun,TKI] + MB[devisaturun, eksporturun] * (1-MB[devisaturun,TKI])= 

0 8 + 0,75 * (1 – 0,8) = 0,95

· MD[devisaturun, TKI^eksporturun] = MD[devisaturun,TKI] + MD[devisaturun,eksporturun] * (1 – MD[devisaturun,TKI]) = 0,3 + 0,1 * (1 – 0,3)      = 0,37

· CF[devisaturun,TKI^eksporturun] = MB[devisaturun,TKI^eksporturun] – MD[devisaturun, TKI^eksporturun] = 

0,95 – 0,37 = 0,58

· Isu terorisme di Indonesia pasca bom bali tgl 12 Oktober 2002 ternyata juga ikut mempengaruhi turunnya devisa Indonesia sebagai akibat berkurangnya wisatawan asing. Bila diketahui MB[devisaturun,bombali] = 0,5 dan MD[devisaturun bombali] = 0,3 maka CF[devisaturun,bombali] dan CF[devisaturun, TKI ^ eksporturun ^ bombali] :

· CF[devisaturun,bombali] =

MB[devisaturun,bombali] –

MD[devisaturun,bombali] = 0,5 – 0,3 = 0,2

· MB[devisaturun,TKI ^ eksporturun^bombali]= MB[devisaturun, TKI ^ eksporturun] + MB[devisaturun,bombali] * (1 – MB[devisaturun, TKI ^ eksporturun]) = 0,95 + 0,5 * (1 – 0,95) = 0,975

· MD[devisaturun, TKI ^ eksporturun ^ bombali] = MD[devisaturun,TKI ^ eksporturun] + MD[devisaturun,bombali] * (1 – MD[devisaturun,TKI ^ eksporturun]) = 

0,37 + 0 3 * (1 – 0,37) = 0,559

· CF[devisaturun,TKI ^ eksporturun ^ bombali] = MB[devisaturun, TKI^eksporturun^bombali] – MD[devisaturun, TKI^eksporturun^bombali] = 0,975 – 0,559 = 0,416

3. Beberapa aturan saling bergandengan ketidakpastian dari bergandengan, suatu aturan menjadi input untuk aturan yang lainnya

Maka :

MB[h,s] = MB’[h,s] * max (0,CF[s,e])

MB’[h,s] = ukuran kepercayaan h berdasarkan keyakinan penuh terhadap validitas s

Contoh :

PHK = terjadi PHK

Pengangguran = muncul banyak pengangguran

Gelandangan = muncul banyak gelandangan

Aturan 1 :

IF terjadi PHK THEN muncul banyak pengangguran

CF[pengangguran, PHK] = 0,9

Aturan 2 :

IF muncul banyak pengangguran THEN muncul

banyak gelandangan

MB[gelandangan,pengangguran] = 0 7 

Maka =

MB[gelandangan, pengangguran] = [0,7] * [0,9] = 0,63

 
 

PROBABILITAS DAN TEOREMA BAYES

PROBABILITAS

Probabilitas menunjukkan kemungkinan sesuatu akan terjadi atau tidak. 

Misal dari 10 orang sarjana , 3 orang menguasai cisco, sehingga peluang untuk memilih sarjana yang menguasai cisco adalah : p(cisco) = 3/10 = 0.3

TEOREMA BAYES

dengan:

p(Hi | E) = probabilitas hipotesis Hi benar jika diberikan evidence (fakta) E

p( E | Hi) = probabilitas munculnya evidence (fakta) E jika diketahui hipotesis Hi benar

p(Hi) = probabilitas hipotesis Hi (menurut hasil sebelumnya) tanpa memandang evidence (fakta) apapun

n = jumlah hipotesis yang mungkin

Contoh :

Asih mengalami gejala ada bintik-bintik di wajahnya. Dokter menduga bahwa Asih terkena cacar dengan :

· probabilitas munculnya bintik-bintik di wajah, jika Asih terkena cacar à p(bintik2|cacar) = 0,8

· probabilitas Asih terkena cacar tanpa memandang gejala apapun à p(cacar) = 0,4

· probabilitas munculnya bintik-bintik di wajah, jika Asih terkena alergi à p(bintik2|alergi) = 0,3

· probabilitas Asih terkena alergi tanpa memandang gejala apapun à p(alergi) = 0,7

· probabilitas munculnya bintik-bintik di wajah, jika Asih jerawatan à p(bintik2|jerawatan) = 0,9

· probabilitas Asih jerawatan tanpa memandang gejala apapun à p(jerawatan) = 0,5 

Maka :

· 

 probabilitas Asih terkena cacar karena ada bintik-bintik di wajahnya :

· probabilitas Asih terkena alergi karena ada bintik-bintik di wajahnya :

· probabilitas Asih jerawatan karena ada bintik-bintik di wajahnya :

Jika setelah dilakukan pengujian terhadap hipotesis muncul satu atau lebih evidence (fakta) atau observasi baru maka :

dengan :

e= evidence lama

E = evidence atau observasi baru

p(H|E,e) = probabilitas hipotesis H benar jika muncul evidence baru E dari evidence lama e

p(H|E) = probabilitas hipotesis H benar jika diberikan evidence E.

p(e|E,H)= kaitan antara e dan E jika hipotesis benar

P(e|E) = kaitan antara e dan E tanpa memandang hipotesis apapun.

Misal :

· Adanya bintik-bintik di wajah merupakan gejala seseorang terkena cacar. Observasi baru menunjukkan bahwa selain bintik-bintik di wajah, panas badan juga merupakan gejala orang kena acar. Jadi antara munculnya bintik-bintik di wajah dan panas badan juga memiliki keterkaitan satu sama lain.

· Asih ada bintik-bintik di wajahnya. Dokter menduga bahwa Asih terkena cacar dengan probabilitas terkena cacar bila ada bintik-bintik di wajah à p(cacar|bintik2) = 0,8

· Ada observasi bahwa orang terkena cacar pasti mengalami panas badan. Jika diketahui probabilitas orang terkena cacar bila panas badan à p(cacar|panas ) = 0,5

· Keterkaitan antara adanya bintik-bintik di wajah dan panas badan bila seseorang terkena cacar à  p(bintik2|panas, cacar) = 0,4

· Keterkaitan antara adanya bintik-bintik di wajah dan panas badan à p(bintik2|panas) = 0,6

Maka :

· Pengembangan lebih jauh dari Teorema Bayes adalah Jaringan Bayes. 

· Contoh : hubungan antara krismon, PHK, pengangguran, gelandangan dalam suatu jaringan.