Metode Dempster-Shafer: Contoh Perhitungan Manual Lengkap

Dempster-Shafer adalah metode penalaran untuk menggabungkan beberapa evidence atau bukti ketika terdapat ketidakpastian. Metode ini menggunakan nilai mass function, belief, dan plausibility untuk merepresentasikan tingkat dukungan terhadap satu atau beberapa hipotesis.

Pada sistem pakar, Dempster-Shafer dapat digunakan ketika sebuah gejala tidak selalu menunjuk pada satu diagnosis secara pasti. Sebagian keyakinan dapat diberikan pada suatu hipotesis, sedangkan sisanya ditempatkan pada himpunan ketidaktahuan atau frame of discernment.

Tutorial ini menggunakan contoh diagnosis kerusakan laptop agar proses perhitungan dapat diikuti secara manual, mulai dari menentukan hipotesis, memberikan nilai mass pada evidence, menghitung konflik, menggabungkan evidence dengan aturan Dempster, hingga memperoleh hasil akhir.

Daftar Isi

• Pengertian Dempster-Shafer
• Konsep Dasar Dempster-Shafer
• Frame of Discernment
• Mass Function
• Belief dan Plausibility
• Rumus Kombinasi Dempster
• Konflik pada Dempster-Shafer
• Contoh Kasus Dempster-Shafer
  • #01 Menentukan Hipotesis
  • #02 Evidence Pertama
  • #03 Evidence Kedua
  • #04 Kombinasi Evidence Pertama dan Kedua
  • #05 Evidence Ketiga
  • #06 Kombinasi dengan Evidence Ketiga
  • #07 Hasil Akhir
• Menghitung Belief dan Plausibility dari Hasil Akhir
• Cara Membaca Nilai Konflik
• Pseudocode Dempster-Shafer
• Dempster-Shafer vs Certainty Factor
• Dempster-Shafer vs Naive Bayes
• Kelebihan dan Kekurangan
• Kapan Dempster-Shafer Cocok Digunakan?
• Kesalahan Umum Implementasi
• Ringkasan
• FAQ Dempster-Shafer
• Referensi
• Source Code Dempster-Shafer

Pengertian Dempster-Shafer

Dempster-Shafer Theory adalah teori evidensi yang digunakan untuk merepresentasikan dan menggabungkan ketidakpastian.

Berbeda dengan probabilitas klasik yang biasanya memberikan nilai langsung pada suatu kejadian tunggal, Dempster-Shafer dapat memberikan dukungan pada:

• satu hipotesis,
• beberapa hipotesis sekaligus,
• atau seluruh ruang hipotesis jika evidence belum cukup spesifik.

Secara sederhana, prosesnya adalah:

Evidence 1
    ↓
Mass Function
    ↓
Evidence 2
    ↓
Kombinasi Dempster
    ↓
Mass Baru
    ↓
Evidence Berikutnya
    ↓
Hasil Akhir

Konsep Dasar Dempster-Shafer

Beberapa konsep penting dalam Dempster-Shafer adalah:

Nilai mass biasanya dinyatakan pada rentang:

dan jumlah seluruh mass:

dengan:

sebelum proses kombinasi.

Frame of Discernment

Frame of discernment adalah himpunan seluruh hipotesis yang mungkin.

Misalnya pada diagnosis sederhana kerusakan laptop digunakan dua hipotesis:

H1 = Overheating
H2 = Gangguan RAM

Maka:

Power set-nya:

Himpunan:

sering ditulis sebagai:

dan merepresentasikan kondisi ketika evidence belum mampu membedakan H1 atau H2 secara spesifik.

Mass Function

Mass function atau basic probability assignment (BPA) dilambangkan dengan:

Nilai tersebut menunjukkan seberapa besar evidence mendukung himpunan hipotesis \(A\).

Misalnya gejala "laptop cepat panas" memberikan dukungan:

Sisa ketidaktahuan:

Jumlahnya:

Artinya evidence pertama memberikan dukungan 70% secara langsung kepada H1, sedangkan 30% belum cukup spesifik untuk membedakan H1 dan H2.

Nilai mass bukan selalu sama dengan probabilitas klasik. Mass dapat diberikan kepada himpunan hipotesis, bukan hanya pada satu hipotesis tunggal.

Belief dan Plausibility

Belief

Belief terhadap \(A\) adalah jumlah mass seluruh subset yang sepenuhnya mendukung \(A\).

Untuk singleton H1 pada contoh sederhana:

Plausibility

Plausibility menunjukkan batas maksimum dukungan yang masih mungkin diberikan kepada \(A\).

atau:

Jika:

dan:

maka:

Interval keyakinannya:

Rumus Kombinasi Dempster

Jika terdapat dua mass function \(m_1\) dan \(m_2\), maka kombinasi Dempster untuk himpunan \(Z\neq\emptyset\) adalah:

dengan konflik:

Nilai \(K\) menunjukkan total dukungan yang saling bertentangan.

Jika:

maka tidak ada konflik.

Jika:

mendekati 1, evidence semakin bertentangan dan hasil kombinasi perlu diinterpretasikan dengan hati-hati.

Konflik pada Dempster-Shafer

Misalnya:

dan:

Karena:

maka kontribusi konflik:

Nilai tersebut masuk ke \(K\), bukan langsung menjadi mass baru.

Setelah seluruh konflik dihitung, mass yang tidak konflik dinormalisasi menggunakan:

Contoh Kasus Dempster-Shafer

Contoh berikut menggunakan diagnosis kerusakan laptop.

#01 Menentukan Hipotesis

Digunakan dua hipotesis:

Frame of discernment:

Digunakan tiga evidence:

#02 Evidence Pertama

Evidence E1:

Laptop cepat panas

Pakar memberikan mass:

Tabel mass E1:

#03 Evidence Kedua

Evidence E2:

Kipas laptop sangat berisik

Mass:

Tabel mass E2:

#04 Kombinasi Evidence Pertama dan Kedua

Kombinasi dilakukan dengan mencari irisan setiap himpunan.

Contoh:

sehingga:

Contoh lainnya:

sehingga:

Seluruh kombinasi:

Tidak ada irisan kosong, sehingga:

Mass untuk H1:

Mass untuk Θ:

Karena:

hasil tidak perlu dinormalisasi lebih lanjut.

Hasil kombinasi E1 dan E2:

#05 Evidence Ketiga

Evidence E3:

Laptop sering mengalami blue screen

Evidence ini lebih mendukung gangguan RAM.

Diberikan mass:

Tabel mass:

#06 Kombinasi dengan Evidence Ketiga

Sekarang gabungkan:

dengan:

Contoh konflik:

maka:

Nilai ini masuk ke konflik:

Kombinasi lengkap:

Total konflik:

Maka:

Mass H1

atau sekitar:

Mass H2

atau sekitar:

Mass Θ

atau sekitar:

Validasi:

#07 Hasil Akhir

Sebelum melihat tabel akhir, hasil kombinasi menunjukkan bahwa mass terbesar diberikan kepada:

yaitu:

Hasil akhir:

Berdasarkan mass terbesar, hipotesis yang paling kuat didukung oleh evidence pada contoh ini adalah:

H1 — Overheating

dengan mass sekitar:

Nilai 71.96% adalah mass hasil kombinasi Dempster-Shafer pada model contoh ini. Nilai tersebut tidak harus ditafsirkan sama seperti probabilitas statistik klasik.

Menghitung Belief dan Plausibility dari Hasil Akhir

Dari hasil akhir:

Belief H1

Karena hanya mass \(\{H1\}\) yang sepenuhnya mendukung H1:

atau:

Plausibility H1

Mass yang masih mungkin mendukung H1 adalah:

maka:

atau:

Interval H1:

Dengan kata lain, berdasarkan evidence yang tersedia, dukungan terhadap H1 berada dalam interval sekitar 71.96% sampai 81.78%.

Cara Membaca Nilai Konflik

Pada kombinasi terakhir diperoleh:

atau:

Nilai ini cukup besar karena dua evidence pertama sangat mendukung H1, sedangkan evidence ketiga mendukung H2.

Interpretasinya:

• evidence tidak sepenuhnya sejalan;
• terdapat pertentangan yang cukup besar;
• normalisasi Dempster masih menghasilkan distribusi mass baru karena \(K<1\);
• hasil perlu dibaca bersama konteks evidence dan kualitas sumber pengetahuan.

Jika:

maka:

dan aturan kombinasi Dempster tidak dapat digunakan karena terjadi konflik total.

Pseudocode Dempster-Shafer

Berikut pseudocode sederhana untuk menggabungkan dua mass function:

function combine(m1, m2):

    result = {}
    conflict = 0

    for each setA, valueA in m1:

        for each setB, valueB in m2:

            intersection =
                intersect(setA, setB)

            product =
                valueA * valueB

            if intersection is empty:
                conflict += product
            else:
                result[intersection] += product

    if conflict == 1:
        return error "Total conflict"

    for each set in result:
        result[set] =
            result[set] / (1 - conflict)

    return result

Jika evidence lebih dari dua, lakukan kombinasi secara bertahap:

m12 = combine(m1, m2)

m123 = combine(m12, m3)

m1234 = combine(m123, m4)

dan seterusnya.

Dempster-Shafer vs Certainty Factor

Dempster-Shafer dan Certainty Factor sama-sama digunakan untuk menangani ketidakpastian, tetapi konsepnya berbeda.

Dempster-Shafer vs Naive Bayes

Kelebihan dan Kekurangan

Kelebihan Dempster-Shafer

• Dapat merepresentasikan ketidaktahuan melalui Θ.
• Dapat menggabungkan beberapa evidence.
• Dapat memberikan mass pada satu atau beberapa hipotesis.
• Memiliki ukuran Belief dan Plausibility.
• Dapat menghitung tingkat konflik antar-evidence.
• Cocok digunakan pada sistem pakar dengan evidence yang tidak selalu pasti.

Kekurangan Dempster-Shafer

• Perhitungan menjadi lebih kompleks ketika jumlah hipotesis banyak.
• Jumlah subset pada power set bertambah secara eksponensial.
• Konflik tinggi dapat menghasilkan normalisasi yang sulit diinterpretasikan.
• Nilai mass awal tetap membutuhkan dasar yang dapat dipertanggungjawabkan.
• Implementasi harus menangani irisan himpunan dengan benar.
• Hasil sangat dipengaruhi kualitas evidence dan mass yang diberikan.

Kapan Dempster-Shafer Cocok Digunakan?

Dempster-Shafer cocok digunakan ketika:

• terdapat beberapa hipotesis yang mungkin;
• evidence tidak selalu menunjuk pada satu hipotesis secara pasti;
• ketidaktahuan perlu direpresentasikan secara eksplisit;
• beberapa sumber evidence perlu digabungkan;
• sistem membutuhkan Belief dan Plausibility;
• atau diperlukan mekanisme untuk mengukur konflik antar-evidence.

Contoh penerapan:

• diagnosis kerusakan perangkat,
• identifikasi gangguan sistem,
• diagnosis berbasis gejala,
• klasifikasi evidence,
• sistem pakar,
• evaluasi risiko,
• dan penggabungan informasi dari beberapa sumber.

Kesalahan Umum Implementasi

1. Total mass tidak sama dengan 1

Setiap mass function harus memenuhi:

2. Menganggap Θ sama dengan salah satu hipotesis

Θ mewakili seluruh frame of discernment atau ketidaktahuan yang belum spesifik.

3. Konflik ikut dimasukkan sebagai hipotesis

Nilai:

berasal dari irisan kosong dan digunakan untuk normalisasi. Konflik tidak diperlakukan sebagai diagnosis biasa.

4. Tidak membagi dengan \(1-K\)

Setelah konflik dihitung, mass non-konflik harus dinormalisasi:

5. Menganggap mass sama dengan probabilitas klasik

Mass Dempster-Shafer dapat diberikan pada himpunan hipotesis, sehingga interpretasinya berbeda dengan probabilitas klasik.

6. Tidak menangani konflik total

Jika:

kombinasi tidak dapat dihitung dengan aturan Dempster standar karena penyebut menjadi nol.

7. Memberikan nilai mass tanpa dasar

Nilai mass sebaiknya berasal dari pakar, data empiris, penelitian sebelumnya, atau proses pembobotan yang dapat dijelaskan.

Ringkasan

Dempster-Shafer adalah metode penalaran yang menggabungkan evidence menggunakan mass function.

Pada contoh ini:

H1 = Overheating
H2 = Gangguan RAM

Evidence pertama:

Evidence kedua:

Setelah dikombinasikan:

Evidence ketiga mendukung H2:

Setelah kombinasi akhir:

Sehingga hipotesis dengan dukungan terbesar adalah:

H1 — Overheating

Pada saat yang sama, sistem masih menyimpan mass:

pada Θ sebagai ketidaktahuan yang belum dapat dialokasikan secara spesifik.

FAQ Dempster-Shafer

Apa itu Dempster-Shafer?

Dempster-Shafer adalah teori evidensi yang digunakan untuk merepresentasikan dan menggabungkan ketidakpastian berdasarkan beberapa evidence.

Apa itu frame of discernment?

Frame of discernment adalah himpunan seluruh hipotesis yang mungkin dalam suatu masalah.

Apa itu mass function?

Mass function adalah nilai dukungan yang diberikan evidence kepada satu atau beberapa hipotesis.

Apa itu Θ pada Dempster-Shafer?

Θ adalah keseluruhan frame of discernment. Mass pada Θ menunjukkan evidence belum cukup spesifik untuk memilih hipotesis tertentu.

Apa itu Belief?

Belief adalah jumlah dukungan yang secara pasti mendukung suatu hipotesis.

Apa itu Plausibility?

Plausibility adalah batas maksimum dukungan yang masih mungkin diberikan kepada suatu hipotesis.

Apa itu konflik K?

Konflik K adalah jumlah mass dari kombinasi evidence yang menghasilkan irisan kosong.

Berapa rentang nilai konflik?

Nilai konflik berada pada rentang 0 sampai 1. Semakin besar K, semakin kuat pertentangan antar-evidence.

Bagaimana jika K = 1?

Jika K = 1, terjadi konflik total dan aturan kombinasi Dempster standar tidak dapat digunakan karena \(1-K=0\).

Apakah Dempster-Shafer menghasilkan ranking?

Bisa. Salah satu pendekatan sederhana adalah membandingkan mass pada hipotesis singleton dan memilih nilai tertinggi, selama interpretasinya sesuai dengan model yang digunakan.

Apakah nilai mass sama dengan probabilitas?

Tidak selalu. Mass dapat diberikan pada himpunan hipotesis, sehingga konsepnya berbeda dari probabilitas klasik.

Apa perbedaan Dempster-Shafer dan Certainty Factor?

Dempster-Shafer menggunakan mass function, belief, plausibility, dan conflict. Certainty Factor menggunakan nilai tingkat keyakinan dan aturan CF Combine.

Apakah Dempster-Shafer termasuk metode sistem pakar?

Ya. Dempster-Shafer sering digunakan sebagai salah satu metode untuk menangani ketidakpastian pada sistem pakar.

Dari mana nilai mass diperoleh?

Nilai mass dapat diperoleh dari pakar, data empiris, penelitian terdahulu, atau metode penilaian lain yang dapat dipertanggungjawabkan.

Referensi

1. Dempster, A. P. (1967). Upper and Lower Probabilities Induced by a Multivalued Mapping. The Annals of Mathematical Statistics, 38(2), 325–339.
2. Shafer, G. (1976). A Mathematical Theory of Evidence. Princeton University Press.
3. Smets, P., & Kennes, R. (1994). The Transferable Belief Model. Artificial Intelligence, 66(2), 191–234.

Source Code Dempster-Shafer

Berikut source code yang menggunakan metode Dempster-Shafer pada RumahSourceCode.

Source Code Sistem Pakar Metode Dempster Shafer PHP

Rp350,000

Source Code Sistem Pakar Metode Dempster Shafer VB.Net

Rp475,000

Source Code Sistem Pakar Metode Dempster Shafer Codeigniter

Rp525,000