Jl Srijaya Negara Bukit Besar Palembang 30139, Telpon : +62711‐353414
PROGRAM STUDI D3 JURUSAN TEKNIK KOMPUTER POLITEKNIK NEGERI SRIWIJAYA PALEMBANG TK
Teori Dempster-Shafer
Hand On Lab 3
Inteligensi Buatan
100 menit
Lecturer : M. Miftakul Amin, S. Kom., M. Eng. Website : http://mafisamin.blog.ugm.ac.id Tujuan : 1. Mahasiswa dapat menjelaskan konsep ketidakpastian. 2. Mahasiswa dapat menggunakan teori dempster-shafer menyelesaikan masalah ketidak pastian Perlengkapan : -
untuk
1. Pengantar Banyak masalah di dunia ini yang tidak pasti yang tidak dapat dimodelkan secara lengkap dan konsisten. Contoh penalaran induktif: Premis 1 : Aljabar adalah pelajaran yang sulit Premis 2 : Geometri adalah pelajaran yang sulit Premis 3 : Kalkulus adalah pelajaran yang sulit Konklusi : Matematika adalah pelajaran yang sulit Pada penalaran induktif ini, muncul premis baru yang dapat mengakibatkan gugurnya konklusi yang sudah diperoleh. Sebagai contoh jika muncul premis -4 sebagai contoh: Premis 4 : Optika adalah pelajaran yang sulit Premis ke-4 mengakibatkan konklusi bahwa Matematika adalah pelajaran yang sulit menjadi keliru. Hal ini disebabkan Optika bukan merupakan bagian dari matematika. Sebuah penalaran dimana adanya penambahan fakta baru mengakibatkan ketidakkonsistenan disebut dengan penalaran non monotonis, yang ditandai dengan: Mengandung ketidak pastian Adanya perubahan pada pengetahuan Adanya penambahan fakta baru dapat mengubah konklusi yang sudah terbentuk. 2. 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 (nol) maka mengindikasikan bahwa tidak ada evidence, sedangkan jika bernilai 1 (satu) menunjukkan adanya kepastian. Plausibility menunjukkan keadaan yang dapat dipercaya. Keterkaitan antara plausibility dan belief dapat dituliskan: Pl (H) = 1 – Bel (H) ……….formula 1)
1 | H a l a m a n
Dalam teori dempster – shafer diasumsikan bahwa hipotesa – hipotesa yang digunakan dikelompokkan ke dalam suatu lingkungan (environment) atau disebut juga frame discernment tersendiri yang biasa disebut himpunan semesta pembicaraan dari sekumpulan hipotesa dan diberikan notasi Θ. Selain itu juga dikenal juga probabilitas fungsi densitas (m) yang menunjukkan besarnya kepercayaan evidence terhadap hipotesa tertentu. Berikut akan diberikan contoh penerapan dempster – shafer. Misalkan Θ = {A, F, D, B} Dengan : A = Alergi; F = Flu; D = Demam; B = Bronkitis. Tujuan kita adalah mengkaitkan ukuran kepercayaan elemen-elemen Θ. Tidak semua evidence secara langsung mendukung tiap-tiap elemen. Seabgai contoh mungkin evidence Panas hanya mendukung {F, D, B}. untuk itu perlu adanya probabilitas fungsi densitas (m). nilai m tidak hanya mendefinisikan elemen-elemen Θ saja, namun juga semua sub set-nya. Sehingga jika Θ berisi n elemen, maka subset dari Θ semuanya berjumlah 2n. kita harus menunjukkan bahwa jumlah semua m dalam subset Θ sama dengan 1. Untuk mencari fungsi densitas digunakan formula: .
∑ ∑
.
……….formula 2)
3. Implementasi Teori Dempster – Shafer Si Ani mengalami gejala panas badan, dari diagnose dokter, penyakit yang mungkin diderita oleh Ani adalah flue, demam, dan bronchitis adalah: •
Gejala -1 : Panas Apabila diketahui nilai kepercayaan setelah dilakukan observasi panas sebagai gejala dari penyakit flue, demam dan bronchitis adalah: {F, D, B} = 0,8 { Θ } = 1 - 0,8 =0,2 Sehari kemudian Ani datang lagi dengan gejala yang baru yaitu hidungnya buntu.
•
Gejala -2 : hidung buntu Kemudian diketahui juga nilai kepercayaan setelah dilakukan observasi terhadap hidung buntu sebagai gejala dari alergi, penyakit flue dan demam adalah: {A, F, D} = 0,9 { Θ } = 1 - 0,9 =0,1 Munculnya gejala baru ini mengharuskan kita untuk menghitung densitas baru untukbeberapa kombinasi (m3). E2 E1 {F, D, B} 0,8 Θ 0,2
2 | H a l a m a n
{A, F, D} 0,9 {F, D} 0,72
Θ 0,1 {F, D, B} 0,08
{A, F, D} 0,18
Θ 0,02
Selanjutnya dihitung m3 dengan formula 2) sebagai berikut: o o o o
m m m m
,
F, D
0,72
A, F, D
,
0,18
F, D, B
,
0,08
,
Θ
0,02
Dari sini kita dapat lihat bahwa pada mulanya dengan hanya ada gejala panas m{F,D,B} = 0,8;namun setelah ada gejala baru yaitu hidung buntu, maka nilai m{F,D,B} menjadi 0,08. Demikian pula pada mulanya dengan hanya ada gejala hidung buntu m{A,F,D} = 0,9; namun setelah ada gejala baru yaitu panas, maka nilai m{A,F,D}=0,18. Dengan adanya 2 gejala ini, nilai densitas yang paling kuat adalah m{F,D} yaitu sebesar 0,72. Hari berikutnya Ani datang lagi dan memberitahukan bahwa minggu lalu dia baru saja datang dari piknik. •
Gejala -3 : piknik Jika diketahui nilai kepercayaan setelah dilakukan observasi terhadap piknik sebagai gejala dari alergi adalah: {A} = 0,6 { Θ } = 1 - 0,6 =0,4 Maka kita harus menghitung kembali nilai densitas baru untuk setiap himpunan bagian dengan fungsi densitas m5.
{F, D} 0,72 {A, F, D} 0,18 {F, D, B} 0,08 Θ 0,02
{A} 0,6 Φ 0,432
Θ 0,4 {F, D} 0,288
{A} 0,108
{A, F, D} 0,072
Φ 0,048
{F, D, B} 0,032
{A} 0,012
Θ 0,008
Sehingga dapat dihitung: o
m
A
o
m
F, D
o
m
A, F, D
o
m
F, D, B
o
m
Θ
,
, ,
0,231
, , ,
0,554
, , ,
, ,
,
,
, ,
,
0,138 0,062 0,015
Dengan adanya gejala baru (si Ani baru saja datang dari piknik), nilai densitas yang paling kuat adalah tetap m{F,D} yaitu sebesar 0,554.
3 | H a l a m a n
4. Implementasi Dempster – Shafer dalam Sistem Pendukung Keputusan. Ada 3 jurusan yang diminati oleh Si Ali, yaitu jurusan Teknik Informatika (I), Psikologi (P) dan Hukum (H). untuk itu dia mencoba mengikuti beberapa tes uji coba. Ujicoba pertama adalah tes logika, hasil tes menunjukkan bahwa probabilitas densitas m1{I,P} = 0,75. Tes kedua adalah tes matematika, hasil tes menunjukkan bahwa probabilitas densitas m2 {I} = 0,8. •
Dari hasil tes kedua tentukanlah probabilitas densitas yang baru untuk {I,P} dan {I} Jawab: m1 {I,P} = 0,75 m1{Θ} = 1 – 0,75 = 0,25 m2{I} = 0,8 m2{Θ} = 1 – 0,80 = 0,20 sehingga diperoleh aturan kombinasi untuk m3 sebagai berikut: E2 E1 {I, P} 0,75 Θ 0,25
{I} 0,80 {I} 0,60
Θ 0,20 {I,P} 0,15
{I} 0,20
Θ 0,05
Sehingga dapat dihitung:
•
o
m
I
o
m
I, P
o
m
Θ
,
,
,
,
0,80 0,15 0,05
Di hari berikutnya si Ali mengikuti tes ketiga yaitu tes wawasan kebangsaan. Hasil tes menunjukkan bahwa probabilitas densitas m4{H}=0,3. Tentukanlah probabilitas densitas yang baru untuk {I,P}, {I} dan {H}. Jawab: m4 {H} = 0,30 m4{Θ} = 1 – 0,30 = 0,70 sehingga diperoleh aturan kombinasi untuk m5 sebagai berikut:
{I} 0,80 {I,P} 0,15 Θ 0,05
4 | H a l a m a n
{H} 0,30 Φ 0,240
Θ 0,70 {I} 0,560
Φ 0,045
{I,P} 0,105
{H} 0,015
Θ 0,350
Sehingga dapat dihitung: o
m
I
o
m
I, P
o
m
H
o
m
Θ
, ,
0,783
, , , , ,
, ,
,
0,147
,
,
0,021 0,049
Sehingga dapat disimpulkan bahwa probabilitas densitas terbesar Si Ali masuk jurusan Informatika. Tugas : 1) Selesaikan kasus berikut menggunakan teori dempster – shafer. Diketahui Θ = {H1, H2, H3, H4} Terdapat E1 yang mendukung H1, H2, dan H4 dengan m=0,8 Dengan demikian m1 {H1, H2, H3, H4} = 0,80 m1 {Θ} = 1 - 0,80 = 0,20 Kemudian terdapat juga E2 yang merupakan evidence yang mendukung H1, H2, dan H3 dengan m=0,7 Dengan demikian: m2 {H1, H2, H3} = 0,70 m2 {Θ} = 1 - 0,70 = 0,30 carilah densitas baru (m3) untuk beberapa kombinasi karena munculnya evidence baru E2. Jika selanjutnya muncul E4 yang mendukung H3 dengan nilai kepercayaan m4 {H3} = 0,5 dari sini diketahui m4{Θ} = 1 – 0,5 = 0,5. Tentukan nilai densitas m5. Diperiksa tanggal :_____________ Dosen Pengampu:
(M. Miftakul Amin, S. Kom., M. Eng.) NIP. 197912172012121001 Sumber referensi: Hartati, Sri; Iswanti, Sari. 2008. Sistem Pakar dan Pengembangannya. Yogyakarta: Penerbit Graha Ilmu Kusumadewi, Sri. 2003. Artificial Intelligence (Teknik dan Aplikasinya). Yogyakarta: Penerbit Graha Ilmu
5 | H a l a m a n
Nama Laboratorium :
Nomor Komputer :
Untuk menjawab soal dibantu dengan menyajikan ke bentuk baris dan kolom sebagai berikut: E2 E1 {H1, H2, H4} 0,80
{H1, H2, H3} 0,70
Θ 0,30
{H1, H2} 0,56
{H1, H2, H4} 0,24
Θ {H1, H2, H3} Θ 0,14 0,06 0,20 Selanjutnya pencarian nilai densitas dengan menggunakan formula 2) sebagai berikut: ,
o
m
H1, H2
o
m
H1, H2, H3
,
0,14
o
m
H1, H2, H4
,
0,24
o
m
Θ
,
0,56
0,06
Kemudian muncul E4 yang mendukung H3 dengan nilai kepercayaan m4 {H3} = 0,5 dari sini diketahui m4{Θ} = 1 – 0,5 = 0,5. Tentukan nilai densitas m5.
{H1, H2} 0,56 {H1, H2, H4} 0,24 {H1, H2, H3} 0,14 Θ 0,06
{H3} 0,5
Θ 0,5
Φ 0,28
{H1, H2} 0,28
Φ 0,12
{H1, H2, H4} 0,12
{H3} 0,07
{H1, H2, H3} 0,07
{H3} 0,03
Θ 0,03
Sehingga dapat dihitung: ,
o
m
H1, H2
o
m
H1, H2, H4
o
m
Θ
o
m
H1, H2, H3
o
m
H3
,
0,47
, , ,
, ,
,
0,05
,
, ,
,
, ,
0,20
,
,
0,12
0,17
Dari hasil perhitungan yang diperoleh, nilai densitas paling kuat adalah m5 {H1, H2} yaitu 0,47.
6 | H a l a m a n
