Algoritma Viterbi 2

Algoritma Viterbi adalah salah satu algoritma yang dapat digunakan untuk melakukan prediksi. Contoh yang dibahas kali ini adalah mengenai memprediksikan cuaca berdasarkan data aktivitas yang dilakukan.

Diasumsikan ada 2 buah keadaan cuaca, yaitu cerah dan hujan
Kemudian diketahui terdapat 3 aktivitas yang dilakukan, yaitu menonton film, berolahraga, dan belajar
Masing-masing keadaan memliki probabilitas untuk berpindah menuju keadaan yang lain,
Dan masing-masing keadaan memiliiki probabilitas untuk melakukan sebuah aktivitas
Maka lakukan prediksi urutan cuaca yang terjadi apabila diketahui beberapa kegiatan yang telah dilakukan

Diasumsikan probabilitas per keadaan adalah sebagai berikut

Diasumsikan probabilitas transisi keadaan per keadaan adalah sebagai berikut

Diasumsikan probabilitas aktivitas per keadaan adalah sebagai berikut

* Masukkan data-data sesuai deskripsi tersebut

Dim keadaan As String() = New String() {"Cerah", "Hujan"}
Dim aktivitas As String() = New String() {"Menonton Film", "Berolahraga", "Belajar"}
Dim probPerKeadaan As Double() = New Double() {0.6, 0.4}
Dim probTransisiKeadaanPerKeadaan As Double(,) = New Double(,) {{0.7, 0.3}, {0.4, 0.6}}
Dim proAktivitasPerKeadaan As Double(,) = New Double(,) {{0.1, 0.4, 0.5}, {0.6, 0.3, 0.1}}

Langkah-langkah penggunaan algoritma ini adalah

1. Tentukan urutan aktivitas yang akan dicari prediksi cuacanya
Diasumsikan keadaan yang diketahui adalah Menonton Film, Belajar, Berolahraga, Menonton Film

Dim urutanAktivitas As Integer() = New Integer() {0, 2, 1, 0}

2. Lakukan proses perhitungan prediksi menggunakan Viterbi
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

Viterbi(keadaan, aktivitas, probPerKeadaan, probTransisiKeadaanPerKeadaan, proAktivitasPerKeadaan, _
		faktorSkala, urutanAktivitas, alurViterbi, probViterbi)

Memasuki proses utama pada fungsi Viterbi

2a. Lakukan inisialisasi T sebagai pemetaan dari probabilitas aktivitas per keadaan

Dim T As Double(,) = New Double(keadaan.Length - 1, 2) {}
For i As Integer = 0 To keadaan.Length - 1
	T(i, 0) = probPerKeadaan(i)
	T(i, 1) = i
	T(i, 2) = probPerKeadaan(i)
Next

2b. Lakukan perhitungan pada masing-masing urutan aktivitas (poin 2b1 – 2b2)

For i As Integer = 0 To urutanAktivitas.Length - 1
	. . .

2b1. Lakukan perhitungan pada semua kemungkinan transisi keadaan (poin 2b1a – 2b1e)

For j As Integer = 0 To keadaan.Length - 1
	. . .
	For k As Integer = 0 To keadaan.Length - 1
	. . .

2b1a. Hitung probabilitas dengan rumus
p = probAktivitasPerKeadaan[k][i] * probTransisiKeadaanPerKeadaan[k][j]
perkalian dengan faktor skala hanya untuk memudahkan pembacaan angka saja

Dim p As Double = probAktivitasPerKeadaan(k, urutanAktivitas(i)) * probTransisiKeadaanPerKeadaan(k, j) * faktorSkala

2b1b. Kalikan nilai probabilitas pada nilai probabilitas viterbi sementara
Dan jumlahkan semua nilai probabilitas ini

tmpProb *= p
tmpNilaiProbViterbi *= p
totalProb += tmpProb

2b1c. Jika nilai probabilitas viterbi lebih dari nilai probabilitas tertinggi untuk aktivitas ini,
maka simpan keadaan ini sebagai keadaan terbaik untuk aktivitas ini

If tmpNilaiProbViterbi > maksProb Then
	maksProb = tmpNilaiProbViterbi
	maksKeadaan = j
End If

2b1d. Jika nilai probabilitas viterbi lebih dari nilai probabilitas tertinggi dari semua aktivitas,
maka simpan keadaan ini sebagai keadaan terbaik

If tmpNilaiProbViterbi > probTertinggi Then
	probTertinggi = tmpNilaiProbViterbi
	alurViterbi(i) = j
	probViterbi(i) = tmpNilaiProbViterbi
End If

2b1e. Setelah selesai melakukan perhitungan pada semua kemungkinan perubahan keadaan pada sebuah keadaan,
Simpan semua nilai probabilitas dan nilai probabilitas tertinggi untuk digunakan pada transisi keadaan berikutnya

U(j, 0) = totalProb
U(j, 1) = maksKeadaan
U(j, 2) = maksProb

2b2. Simpan semua nilai probabilitas dan nilai probabilitas tertinggi untuk digunakan pada aktivitas berikutnya

T = U

2c. Hitung total probabilitas dari semua alur viterbi dan nilai probabilitas viterbi terbaik
Dan tampilkan pada layar

Dim totalProb2 As Double = 0
Dim maksProb2 As Double = 0

For i As Integer = 0 To keadaan.Length - 1
	Dim tmpProb As Double = T(i, 0)
	Dim tmpNilaiAlurViterbi As Double = T(i, 1)
	Dim tmpNilaiProbViterbi As Double = T(i, 2)

	totalProb2 += tmpProb
	If tmpNilaiProbViterbi > maksProb2 Then
		maksProb2 = tmpNilaiProbViterbi
	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.