Algoritma NMF (Non-Negative Matrix Factorization) adalah salah satu algoritma yang dapat digunakan untuk menganalisa hubungan antara sebuah frase/kalimat dengan sekumpulan dokumen. Contoh yang dibahas kali ini adalah mengenai penentuan urutan peringkat data berdasarkan query yang digunakan.
Diasumsikan data kalimat yang tersedia adalah sebagai berikut:
| Isi kalimat |
|---|
| Saya suka sama suami situ sebab suami situ suka senyum-senyum sama saya. |
| Santapan kita setiap jam setengah satu siang satu soto sapi sama seratus tusuk sate sapi pula. |
| Saya sebal sama situ sebab situ suka senyum-senyum sama suami saya sehingga suami saya suka senyum-senyum sendiri saja. |
| Sempat-sempatnya semut-semut itu saling senyum-senyum dan salam-salaman sama semut-semut yang mau senyum-senyum dan salam-salaman sama semut-semut itu. |
Contoh data awal adalah sebagai berikut:
|
1 2 3 4 5 |
Dim input As New List(Of String) input.Add("Saya suka sama suami situ sebab suami situ suka senyum-senyum sama saya.") input.Add("Santapan kita setiap jam setengah satu siang satu soto sapi sama seratus tusuk sate sapi pula.") input.Add("Saya sebal sama situ sebab situ suka senyum-senyum sama suami saya sehingga suami saya suka senyum-senyum sendiri saja.") input.Add("Sempat-sempatnya semut-semut itu saling senyum-senyum dan salam-salaman sama semut-semut yang mau senyum-senyum dan salam-salaman sama semut-semut itu.") |
Dan query data yang digunakan adalah
| Isi Kalimat |
|---|
| Sapi saling suka |
Contoh data baru adalah sebagai berikut:
|
1 |
Dim query As String = "Sapi saling suka" |
Langkah-langkah penggunaan algoritma ini adalah
1. Lakukan proses tokenizing dan lowercase pada masing-masing kalimat dan query
Setiap kata akan dijadikan huruf kecil semua,
dan kemudian dilakukan proses penghilangan tanda baca
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini
|
1 2 3 4 5 |
For i As Integer = 0 To daftarDokumen.Count - 1 daftarDokumen(i) = Tokenizing(daftarDokumen(i).ToLower) Next query = Tokenizing(query.ToLower) |
* Gunakan fungsi ini untuk menghilangkan tanda baca
Tanda baca yang diperhitungkan adalah:
titik ,koma, titik koma, titik dua, hubung -, tanda tanya, tanda seru, kurung biasa (), kurung kotak [], kurung kurawal {}, tanda petik satu, tanda petik ganda, garis miring
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
Public Function Tokenizing(ByVal input As String) As String input = input.Replace(".", "") input = input.Replace(",", "") input = input.Replace(":", "") input = input.Replace("-", " ") input = input.Replace("?", "") input = input.Replace("!", "") input = input.Replace("(", "") input = input.Replace(")", "") input = input.Replace("[", "") input = input.Replace("]", "") input = input.Replace("{", "") input = input.Replace("}", "") input = input.Replace("'", "") input = input.Replace("""", "") input = input.Replace("/", "") Return input End Function |
2. Susun matriks A dan q sesuai dengan masing-masing kata yang ditemukan dalam semua kalimat (poin 2a – 2c)
2a. Lakukan perulangan pada masing-masing kalimat
Lakukan pemisahan masing-masing kata berdasarkan karakter spasi
Kemudian catat semua kata unik yang belum terdapat pada daftar kata
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
Dim daftarKata As New List(Of String) For i As Integer = 0 To daftarDokumen.Count - 1 Dim tmpKata() As String = daftarDokumen(i).Split(" ") For j As Integer = 0 To tmpKata.Length - 1 Dim isTerpilih As Boolean = False For k As Integer = 0 To daftarKata.Count - 1 If tmpKata(j) = daftarKata(k) Then isTerpilih = True Exit For End If Next If Not isTerpilih Then daftarKata.Add(tmpKata(j)) Next Next |
2b. Lakukan pengurutan kata berdasarkan urutan alfabet
hal ini hanya dilakukan untuk memudahkan pembacaan saja
|
1 |
daftarKata.Sort() |
2c. Lakukan perhitungan pada masing-masing kata yang ditemukan
Catat jumlah dari masing-masing kata yang terdapat dalam masing-masing kalimat
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
Dim tmpA(daftarKata.Count - 1)() As Double For i As Integer = 0 To tmpA.Count - 1 tmpA(i) = New Double(daftarDokumen.Count - 1) {} Next For i As Integer = 0 To daftarDokumen.Count - 1 Dim tmpKata() As String = daftarDokumen(i).Split(" ") For j As Integer = 0 To tmpKata.Length - 1 Dim idxKata As Integer = daftarKata.IndexOf(tmpKata(j)) tmpA(idxKata)(i) += 1 Next Next |
3. Lakukan proses dekomposisi matriks menggunakan metode non-negative matrix factorization
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini
|
1 2 3 |
Dim wh() As pMatrix = A.nmf(daftarKata.Count, 100, 0) Dim W As pMatrix = wh(0) Dim H As pMatrix = wh(1) |
* Fungsi utama dari metode ini adalah untuk melakukan dekomposisi matriks sehingga memenuhi persamaan
A = WH
Pada awalnya, matriks W dan matriks H akan bernilai acak,
Kemudian nilai matriks akan diupdate agar hasilnya semakin mendekati A
Matriks H diupdate dengan menggunakan rumus
H = H * (W'A)/(W'WH)
Matriks W diupdate dengan menggunakan rumus
W = W * (AH')/(WHH')
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
Public Overridable Function nmf(ByVal k As Integer, ByVal n As Integer, ByVal e As Double) As pMatrix() Dim generator As New Random(0) Dim w As pMatrix = urandom(jumlahBaris, k, 1, n, generator) Dim h As pMatrix = urandom(k, jumlahKolom, 1, n, generator) Do w = urandom(jumlahBaris, k, 1, n, generator) h = urandom(k, jumlahKolom, 1, n, generator) For i As Integer = 0 To n - 1 ' Hitung W * H Dim wh As pMatrix = w.perkalianMatriks(h) Dim cost As Double = kuadratJarak(wh) ' if found solution If cost < e Then Exit For End If ' Lakukan update matriks fitur Dim wt As pMatrix = w.Transpos() Dim hn As pMatrix = wt.perkalianMatriks(Me) Dim hd As pMatrix = wt.perkalianMatriks(wh) h.perkalianSkalar(hn.perkalianSkalar(hd.inversiSkalar())) ' Lakukan update matriks bobot Dim ht As pMatrix = h.Transpos() Dim wn As pMatrix = perkalianMatriks(ht) Dim wd As pMatrix = w.perkalianMatriks(h).perkalianMatriks(ht) w.perkalianSkalar(wn.perkalianSkalar(wd.inversiSkalar())) If Double.IsNaN(w.matriks(0)(0)) OrElse Double.IsNaN(h.matriks(0)(0)) Then Exit For End If Next i Loop While Double.IsNaN(w.matriks(0)(0)) OrElse Double.IsNaN(h.matriks(0)(0)) Return New pMatrix() {w, h} End Function |
4. Hitung bobot Hi dengan rumus
bobot Hi* = E(Hiq) / E(Hpq)
|
1 2 3 4 5 6 7 8 9 10 |
Dim Hpq As Double = H.sum() Dim bobotHi(daftarKata.Count - 1) As Double For idxKata As Integer = 0 To daftarKata.Count - 1 Dim Hiq As Double = 0 For idxKalimat As Integer = 0 To daftarDokumen.Count - 1 Hiq += H.matriks(idxKata)(idxKalimat) Next bobotHi(idxKata) = Hiq / Hpq Next |
5. Hitung GRS (Generic Relevance of Sentence) dengan rumus
GRSj = E(Hij * bobot Hi*)
|
1 2 3 4 5 6 7 |
Dim GRSj(daftarDokumen.Count - 1) As Double For idxKata As Integer = 0 To daftarKata.Count - 1 For idxKalimat As Integer = 0 To daftarDokumen.Count - 1 GRSj(idxKalimat) += H.matriks(idxKata)(idxKalimat) * bobotHi(idxKata) Next Next |
6. Lakukan pengurutan kalimat berdasarkan skor GRS tertinggi
Kemudian tmapilkan hasil akhir perhitungan pada layar
|
1 2 3 4 5 6 7 8 9 10 |
Dim urutan(daftarDokumen.Count - 1) As Integer For idxKalimat As Integer = 0 To daftarDokumen.Count - 1 urutan(idxKalimat) = idxKalimat Next Array.Sort(GRSj, urutan) Console.WriteLine("Hasil akhir perhitungan: ") For i As Integer = GRSj.Count - 1 To 0 Step -1 Console.WriteLine("Peringkat " & GRSj.Count - i & " adalah dokumen #" & urutan(i) + 1 & " dengan nilai GRS: " & GRSj(i).ToString("F6")) 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.
