Algoritma Dempster-Shafer adalah salah satu algoritma yang digunakan untuk pengambilan keputusan. Contoh yang dibahas kali ini adalah mengenai pemilihan film dengan genre sesuai inputan.
Algoritma ini juga menggunakan metode CF (Certainty Factor). Dalam kasus ini, CF dilambangkan sebagai tingkat kepercayaan dari masing-masing genre
Diasumsikan ada 5 buah Film yang ingin ditonton, yaitu A,B,C,D,E
Masing-masing film memiliki satu / lebih genre film tersebut, dan memiliki nilai tingkat kepercayaan atas genre tersebut
Sehingga dalam kasus ini, diasumsikan data awalnya adalah sebagai berikut
| Kode | Genre | Film dengan genre ini | tingkat kepercayaan |
|---|---|---|---|
| 1 | Fantasi | A B | 0.4 |
| 2 | Komedi | A C D E | 0.3 |
| 3 | Kriminal | B | 0.6 |
| 4 | Horor | B D E | 0.3 |
| 5 | Petualangan | C D E | 0.4 |
| 6 | Science Fiction | A E | 0.5 |
| 7 | Sejarah | C D | 0.6 |
| 8 | Slice of Life | C | 0.7 |
Langkah pertama adalah memasukkan data-data yang digunakan.
Contoh data adalah sebagai berikut
Untuk kriteria genre
Terdapat 5 kolom untuk merepresentasikan masing-masing genre A B C D E
Jika mengandung genre A, maka kolom pertama akan bernilai 1
Jika mengandung genre B, maka kolom kedua akan bernilai 1
dan seterusnya sampai genre E
Dim genre(7, 5) As Double genre(0, 0) = 1 genre(0, 1) = 1 genre(0, 2) = 0 genre(0, 3) = 0 genre(0, 4) = 0 genre(0, 5) = 0.4 genre(1, 0) = 1 genre(1, 1) = 0 genre(1, 2) = 1 genre(1, 3) = 1 genre(1, 4) = 1 genre(1, 5) = 0.3 genre(2, 0) = 0 genre(2, 1) = 1 genre(2, 2) = 0 genre(2, 3) = 0 genre(2, 4) = 0 genre(2, 5) = 0.6 genre(3, 0) = 0 genre(3, 1) = 1 genre(3, 2) = 0 genre(3, 3) = 1 genre(3, 4) = 1 genre(3, 5) = 0.3 genre(4, 0) = 0 genre(4, 1) = 0 genre(4, 2) = 1 genre(4, 3) = 1 genre(4, 4) = 1 genre(4, 5) = 0.4 genre(5, 0) = 1 genre(5, 1) = 0 genre(5, 2) = 0 genre(5, 3) = 0 genre(5, 4) = 1 genre(5, 5) = 0.5 genre(6, 0) = 0 genre(6, 1) = 0 genre(6, 2) = 1 genre(6, 3) = 1 genre(6, 4) = 0 genre(6, 5) = 0.6 genre(7, 0) = 0 genre(7, 1) = 0 genre(7, 2) = 1 genre(7, 3) = 0 genre(7, 4) = 0 genre(7, 5) = 0.7
Langkah-langkah penggunaan algoritma ini adalah
1. Tentukan Genre yang diminati
Pilihan genre harus lebih dari 1
Console.WriteLine("")
Console.WriteLine("Masukkan pilihan Genre minimal 2: ")
Console.WriteLine("contoh pemilihan: 1,2,3 ")
Dim input As String = Console.ReadLine
2. Lakukan proses perhitungan pertama dengan data yang digunakan adalah
himpunan pertama adalah himpunan genre pertama
himpunan kedua adalah himpunan genre kedua
Proses detailnya dijelaskan pada point dibawah ini.
3. Cari irisan himpunan antara himpunan genre pertama dan himpunan genre kedua
Nilai kepercayaan untuk irisan ini adalah nilai kepercayaan genre pertama dikali dengan nilai kepercayaan genre kedua
nilai(iCount, 0) = IIf(genre(pilihanGenre(i) - 1, 0) And genre(pilihanGenre(i + 1) - 1, 0), 1, 0) nilai(iCount, 1) = IIf(genre(pilihanGenre(i) - 1, 1) And genre(pilihanGenre(i + 1) - 1, 1), 1, 0) nilai(iCount, 2) = IIf(genre(pilihanGenre(i) - 1, 2) And genre(pilihanGenre(i + 1) - 1, 2), 1, 0) nilai(iCount, 3) = IIf(genre(pilihanGenre(i) - 1, 3) And genre(pilihanGenre(i + 1) - 1, 3), 1, 0) nilai(iCount, 4) = IIf(genre(pilihanGenre(i) - 1, 4) And genre(pilihanGenre(i + 1) - 1, 4), 1, 0) nilai(iCount, 5) = genre(pilihanGenre(i) - 1, 5) * genre(pilihanGenre(i + 1) - 1, 5)
4. Cari irisan himpunan antara himpunan selain genre pertama dan himpunan genre kedua
Nilai kepercayaan untuk irisan ini adalah (1 dikurangi nilai kepercayaan genre pertama) dikali dengan nilai kepercayaan genre kedua
If Not (nilai(iCount, 0) = genre(pilihanGenre(i + 1) - 1, 0) _ And nilai(iCount, 1) = genre(pilihanGenre(i + 1) - 1, 1) _ And nilai(iCount, 2) = genre(pilihanGenre(i + 1) - 1, 2) _ And nilai(iCount, 3) = genre(pilihanGenre(i + 1) - 1, 3) _ And nilai(iCount, 4) = genre(pilihanGenre(i + 1) - 1, 4)) Then iCount += 1 nilai(iCount, 0) += genre(pilihanGenre(i + 1) - 1, 0) nilai(iCount, 1) += genre(pilihanGenre(i + 1) - 1, 1) nilai(iCount, 2) += genre(pilihanGenre(i + 1) - 1, 2) nilai(iCount, 3) += genre(pilihanGenre(i + 1) - 1, 3) nilai(iCount, 4) += genre(pilihanGenre(i + 1) - 1, 4) nilai(iCount, 5) += (1 - genre(pilihanGenre(i) - 1, 5)) * genre(pilihanGenre(i + 1) - 1, 5) Else nilai(iCount, 5) += (1 - genre(pilihanGenre(i) - 1, 5)) * genre(pilihanGenre(i + 1) - 1, 5) End If
5. Cari irisan himpunan antara himpunan genre pertama dan himpunan selain genre kedua
Nilai kepercayaan untuk irisan ini adalah nilai kepercayaan genre pertama dikali dengan (1 dikurangi nilai kepercayaan genre kedua)
If Not (nilai(iCount, 0) = genre(pilihanGenre(i) - 1, 0) _ And nilai(iCount, 1) = genre(pilihanGenre(i) - 1, 1) _ And nilai(iCount, 2) = genre(pilihanGenre(i) - 1, 2) _ And nilai(iCount, 3) = genre(pilihanGenre(i) - 1, 3) _ And nilai(iCount, 4) = genre(pilihanGenre(i) - 1, 4)) Then iCount += 1 nilai(iCount, 0) = genre(pilihanGenre(i) - 1, 0) nilai(iCount, 1) = genre(pilihanGenre(i) - 1, 1) nilai(iCount, 2) = genre(pilihanGenre(i) - 1, 2) nilai(iCount, 3) = genre(pilihanGenre(i) - 1, 3) nilai(iCount, 4) = genre(pilihanGenre(i) - 1, 4) nilai(iCount, 5) = genre(pilihanGenre(i) - 1, 5) * (1 - genre(pilihanGenre(i + 1) - 1, 5)) Else nilai(iCount, 5) = genre(pilihanGenre(i) - 1, 5) * (1 - genre(pilihanGenre(i + 1) - 1, 5)) End If
6. Cari irisan himpunan antara himpunan selain genre pertama dan himpunan selain genre kedua
Nilai kepercayaan untuk irisan ini adalah (1 dikurangi nilai kepercayaan genre pertama) dikali dengan (1 dikurangi nilai kepercayaan genre kedua)
iCount += 1 nilai(iCount, 0) = 0 nilai(iCount, 1) = 0 nilai(iCount, 2) = 0 nilai(iCount, 3) = 0 nilai(iCount, 4) = 0 nilai(iCount, 5) = (1 - genre(pilihanGenre(i) - 1, 5)) * (1 - genre(pilihanGenre(i + 1) - 1, 5))
7. Jumlahkan semua nilai kepercayaan dari irisan himpunan yang kosong
Dim totNull As Double = 0 For j As Integer = 0 To iCount - 1 If nilai(j, 0) = 0 And nilai(j, 1) = 0 And nilai(j, 2) = 0 And nilai(j, 3) = 0 And nilai(j, 4) = 0 Then totNull += nilai(j, 5) End If Next
8. Lakukan pencatatan proses data baru untuk setiap irisan yang terbentuk
Nilai kepercayaan untuk setiap irisan adalah nilai yang ada dibagi dengan (1 dikurangi jumlah nilai kepercayaan himpunan kosong -> point 7)
iData = 0 For j As Integer = 0 To iCount nilai(j, 5) = nilai(j, 5) / (1 - totNull) If Not (j <> iCount _ And nilai(j, 0) = 0 And nilai(j, 1) = 0 And nilai(j, 2) = 0 And nilai(j, 3) = 0 And nilai(j, 4) = 0) Then hasil(iData, 0) = nilai(j, 0) hasil(iData, 1) = nilai(j, 1) hasil(iData, 2) = nilai(j, 2) hasil(iData, 3) = nilai(j, 3) hasil(iData, 4) = nilai(j, 4) hasil(iData, 5) = nilai(j, 5) iData += 1 End If Next
9. Lakukan proses perhitungan selanjutnya dengan data yang digunakan adalah
himpunan pertama adalah himpunan hasil perhitungan sebelumnya
himpunan kedua adalah himpunan genre ke i+1
Ulangi langkah-langkah point ke 2-8 untuk proses ini.
ReDim nilai(genre.Length - 1, jumlahKolomKriteria - 1) Dim iCount As Integer = -1 For j As Integer = 0 To iData * 2 - 1 If j <= iData - 1 Then Dim st As Boolean = False Dim ist As Integer = 0 For k As Integer = 0 To iCount If j = iData - 1 Then If nilai(k, 0) = IIf(genre(pilihanGenre(i + 1) - 1, 0), 1, 0) _ And nilai(k, 1) = IIf(genre(pilihanGenre(i + 1) - 1, 1), 1, 0) _ And nilai(k, 2) = IIf(genre(pilihanGenre(i + 1) - 1, 2), 1, 0) _ And nilai(k, 3) = IIf(genre(pilihanGenre(i + 1) - 1, 3), 1, 0) _ And nilai(k, 4) = IIf(genre(pilihanGenre(i + 1) - 1, 4), 1, 0) Then st = True ist = k Exit For End If Else If nilai(k, 0) = IIf(hasil(j, 0) And genre(pilihanGenre(i + 1) - 1, 0), 1, 0) _ And nilai(k, 1) = IIf(hasil(j, 1) And genre(pilihanGenre(i + 1) - 1, 1), 1, 0) _ And nilai(k, 2) = IIf(hasil(j, 2) And genre(pilihanGenre(i + 1) - 1, 2), 1, 0) _ And nilai(k, 3) = IIf(hasil(j, 3) And genre(pilihanGenre(i + 1) - 1, 3), 1, 0) _ And nilai(k, 4) = IIf(hasil(j, 4) And genre(pilihanGenre(i + 1) - 1, 4), 1, 0) Then st = True ist = k Exit For End If End If Next If Not st Then iCount += 1 If j = iData - 1 Then nilai(iCount, 0) += IIf(genre(pilihanGenre(i + 1) - 1, 0), 1, 0) nilai(iCount, 1) += IIf(genre(pilihanGenre(i + 1) - 1, 1), 1, 0) nilai(iCount, 2) += IIf(genre(pilihanGenre(i + 1) - 1, 2), 1, 0) nilai(iCount, 3) += IIf(genre(pilihanGenre(i + 1) - 1, 3), 1, 0) nilai(iCount, 4) += IIf(genre(pilihanGenre(i + 1) - 1, 4), 1, 0) nilai(iCount, 5) += hasil(j, 5) * genre(pilihanGenre(i + 1) - 1, 5) Else nilai(iCount, 0) += IIf(hasil(j, 0) And genre(pilihanGenre(i + 1) - 1, 0), 1, 0) nilai(iCount, 1) += IIf(hasil(j, 1) And genre(pilihanGenre(i + 1) - 1, 1), 1, 0) nilai(iCount, 2) += IIf(hasil(j, 2) And genre(pilihanGenre(i + 1) - 1, 2), 1, 0) nilai(iCount, 3) += IIf(hasil(j, 3) And genre(pilihanGenre(i + 1) - 1, 3), 1, 0) nilai(iCount, 4) += IIf(hasil(j, 4) And genre(pilihanGenre(i + 1) - 1, 4), 1, 0) nilai(iCount, 5) += hasil(j, 5) * genre(pilihanGenre(i + 1) - 1, 5) End If Else nilai(ist, 5) += hasil(j, 5) * genre(pilihanGenre(i + 1) - 1, 5) End If Else Dim st As Boolean = False Dim ist As Integer = 0 For k As Integer = 0 To iCount If j < iData * 2 - 1 Then If nilai(k, 0) = hasil(j - iData, 0) _ And nilai(k, 1) = hasil(j - iData, 1) _ And nilai(k, 2) = hasil(j - iData, 2) _ And nilai(k, 3) = hasil(j - iData, 3) _ And nilai(k, 4) = hasil(j - iData, 4) Then st = True ist = k Exit For End If Else Exit For End If Next If Not st Then iCount += 1 nilai(iCount, 0) += hasil(j - iData, 0) nilai(iCount, 1) += hasil(j - iData, 1) nilai(iCount, 2) += hasil(j - iData, 2) nilai(iCount, 3) += hasil(j - iData, 3) nilai(iCount, 4) += hasil(j - iData, 4) nilai(iCount, 5) += hasil(j - iData, 5) * (1 - genre(pilihanGenre(i + 1) - 1, 5)) Else nilai(ist, 5) += hasil(j - iData, 5) * (1 - genre(pilihanGenre(i + 1) - 1, 5)) End If End If Next ReDim hasil(genre.Length - 1, jumlahKolomKriteria - 1) Dim totNull As Double = 0 For j As Integer = 0 To iCount - 1 If nilai(j, 0) = 0 And nilai(j, 1) = 0 And nilai(j, 2) = 0 And nilai(j, 3) = 0 And nilai(j, 4) = 0 Then totNull += nilai(j, 5) End If Next iData = 0 For j As Integer = 0 To iCount nilai(j, 5) = nilai(j, 5) / (1 - totNull) If Not (j <> iCount _ And nilai(j, 0) = 0 And nilai(j, 1) = 0 And nilai(j, 2) = 0 And nilai(j, 3) = 0 And nilai(j, 4) = 0) Then hasil(iData, 0) = nilai(j, 0) hasil(iData, 1) = nilai(j, 1) hasil(iData, 2) = nilai(j, 2) hasil(iData, 3) = nilai(j, 3) hasil(iData, 4) = nilai(j, 4) hasil(iData, 5) = nilai(j, 5) iData += 1 End If Next
10. Cari nilai kepercayaan maksimal dari data hasil proses yang terakhir
Maka, rekomendasi film yang ditonton adalah film-film yang termasuk dalam himpunan dengan nilai kepercayaan maksimal.
Dim Maks As Double = 0 Dim iMaks As Integer = -1 For i As Integer = 0 To iData - 1 If hasil(i, 5) > Maks Then Maks = hasil(i, 5) iMaks = i End If Next
Hasil akhir adalah: (klik untuk perbesar gambar)
Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:
Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.