Algoritma LSA (Latent Semantic Analysis) 16


Algoritma LSA (Latent Semantic Analysis) 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:

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:

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

For i As Integer = 0 To input.Count - 1
	input(i) = Tokenizing(input(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

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

Dim daftarKata As New List(Of String)
For i As Integer = 0 To input.Count - 1
	Dim tmpKata() As String = input(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

daftarKata.Sort()

2c. Lakukan perhitungan pada masing-masing kata yang ditemukan
Catat jumlah dari masing-masing kata yang terdapat dalam masing-masing kalimat
Kemudian lakukan proses yang sama untuk query yang digunakan

Dim tmpA(daftarKata.Count - 1)() As Double
For i As Integer = 0 To tmpA.Count - 1
	tmpA(i) = New Double(input.Count - 1) {}
Next

For i As Integer = 0 To input.Count - 1
	Dim tmpKata() As String = input(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

Dim tmpQ(daftarKata.Count - 1)() As Double
For i As Integer = 0 To tmpQ.Count - 1
	tmpQ(i) = New Double(0) {}
Next

Dim tmpQuery() As String = query.Split(" ")
For j As Integer = 0 To tmpQuery.Length - 1
	Dim idxKata As Integer = daftarKata.IndexOf(tmpQuery(j))
	tmpQ(idxKata)(0) += 1
Next

3. Lakukan proses dekomposisi matriks menggunakan metode dekomposisi Singular
Penjelasan lebih detail tentang algoritma ini dapat dilihat pada Regresi Linier dengan Dekomposisi SIngular

Dim svd As SingularValueDecomposition = A.SVD

Dim U As ObyekMatriks = svd.GetU
Dim S As ObyekMatriks = svd.S
Dim V As ObyekMatriks = svd.GetV

4. Lakukan aproksimasi derajat 2 dari masing-masing matriks U, S, dan V
Nilai yang disimpan adalah semua baris pada 2 kolom pertama U dan V,
dan 2 baris pertama x 2 kolom pertama S

Dim tmpUk(U.GetUkuranBaris - 1)() As Double
For i As Integer = 0 To U.GetUkuranBaris - 1
	tmpUk(i) = New Double(1) {}

	For j As Integer = 0 To 1
		tmpUk(i)(j) = U.GetElement(i, j)
	Next
Next

Dim tmpSk(1)() As Double
For i As Integer = 0 To 1
	tmpSk(i) = New Double(1) {}

	For j As Integer = 0 To 1
		tmpSk(i)(j) = S.GetElement(i, j)
	Next
Next

Dim tmpVk(V.GetUkuranBaris - 1)() As Double
For i As Integer = 0 To V.GetUkuranBaris - 1
	tmpVk(i) = New Double(1) {}

	For j As Integer = 0 To 1
		tmpVk(i)(j) = V.GetElement(i, j)
	Next
Next

5. Hitung nilai matriks q pada aproksimasi derajat 2 dengan rumus
new q = qT * Uk * (1/Sk)

For i As Integer = 0 To 1
	For j As Integer = 0 To 1
		If S.GetElement(i, j) <> 0 Then
			tmpSk(i)(j) = 1 / S.GetElement(i, j)
		End If
	Next
Next

Dim Sk1 As New ObyekMatriks(tmpSk)
Dim rank2q As ObyekMatriks = q.Transpos.PerkalianMatriks(Uk).PerkalianMatriks(Sk1)

6. Hitung nilai similarity masing-masing kalimat menggunakan teknik kosinus
dan urutkan berdasarkan nilai tertinggi
nilai similarity dihitung dengan rumus:
sim = (newq(0) * vk(0) + newq(1) * vk(1)) / (sqrt(newq(0) ^ 2 + newq(1) ^ 2) * sqrt(vk(0) ^ 2 + vk(1) ^ 2))

Dim similarity(input.Count - 1) As Double
Dim urutan(input.Count - 1) As Integer
For i As Integer = 0 To input.Count - 1
	Dim nom As Double = rank2q.GetElement(0, 0) * tmpVk(i)(0) + rank2q.GetElement(0, 1) * tmpVk(i)(1)
	Dim denom As Double = Math.Sqrt(rank2q.GetElement(0, 0) ^ 2 + rank2q.GetElement(0, 1) ^ 2) * Math.Sqrt(tmpVk(i)(0) ^ 2 + tmpVk(i)(1) ^ 2)
	similarity(i) = nom / denom
	urutan(i) = i
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.


Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *

16 pemikiran di “Algoritma LSA (Latent Semantic Analysis)

    • pip Penulis

      qT adalah transpos dari q. Artinya matriks q mengalami proses transposisi sebelum dilakukan proses selanjutnya.

      Pada baris dibawahnya terdapat baris skrip seperti ini
      Dim rank2q As ObyekMatriks = q.Transpos.PerkalianMatriks(Uk).PerkalianMatriks(Sk1)

      yang artinya qT = q.Transpos

      • WaitingForUs

        matriks ‘q’ didapat dari matriks query (sapi saling suka) ?
        kalau iya, berarti nilai matriksnya hanya 1 dimensi ( misal dlm contoh : 34 x 1) ?
        itu kan ga bisa dikalikan dg Uk,Sk (new q = qT * Uk * (1/Sk)), sebelum ditranspose dirubah ke ordo x2 gitu ?

        • pip Penulis

          Iya betul, dengan contoh diatas, matriks q hanya berisi matriks berukuran 34 x 1. qT artinya transpos dari q, sehingga menghasilkan matriks berukuran 1 x 34
          Matriks Uk diambil dari matriks U yang hanya diambil 2 nilai pertama saja, sehingga akan menghasilkan matriks berukuran 34 x 2
          pada bagian qT * Uk, maka akan menghasilkan matriks berukuran 1 x 34 * 34 x 2 = 1 x 2.

  • WaitingForUs

    bagaimana mengatakan bahwa itu mirip dg query ? biasanya dlm menentukan kemiripan itu ada sebuah batasan, yang menyatakan bahwa itu mirip dengan kalimat query, (misal 50% ke bawah) itu ga mirip, sedangkan (diatas 50%) itu menyatakan mirip dg kalimat query, itu gmn ya ? komputer itu kan ga bisa menentukan sebelum diprogram.

    • pip Penulis

      Pada poin terakhir (nomor 6) terdapat sebuah rumus yang digunakan untuk menghitung similarity antara kata kunci dengan dokumen, sehingga sebuah dokumen akan menghasilkan sebuah skor. Semua skor ini kemudian dapat dibandingkan dan/atau diurutkan untuk mendapatkan jawaban yang diinginkan.

      • WaitingForUs

        pada rumus :
        sim = (newq(0) * vk(0) + newq(1) * vk(1)) / (sqrt(newq(0) ^ 2 + newq(1) ^ 2) * sqrt(vk(0) ^ 2 + vk(1) ^ 2))
        bagian “newq(0), vk(0)” dan “newq(1), vk(1)” itu apa ya ? apakah didapat dari kalimat query dan matriks vk (yg udah diaproksimasi 2derajat)?

        • pip Penulis

          Ini adalah bagian untuk menghitung skor dari masing-masing dokumen seperti yang saya jelaskan sebelumnya. JIka anda melihat screenshot hasil akhir, maka akan terdapat 4 buah nilai skor karena terdapat 4 buah dokumen yang digunakan sebagai input. Tentu saja nilai skor ini sudah mewakili hubungan antara kalimat input dengan dokumen tersebut.

    • pip Penulis

      Pertanyaan tersebut menurut saya kurang lebih sama seperti pertanyaan “mengapa 1 ditambah dengan 2 sama dengan 3? mengapa angka 1 tidak ditambahkan dengan angka lain untuk menghasilkan angka 3?”. Jawaban dari pertanyaan ini adalah jawaban atas pertanyaan anda.

      • WaitingForUs

        maaf mas, sy msh bingung di bagian ini
        di contoh, diket :
        newq = [0.027255 -0.032204]
        vk =
        [0.359184 -0.469388]
        [0.043311 -0.030301]
        [0.527328 -0.60895]
        [0.768789 0.638699]

        nah pd rumus : sim = (newq(0) * vk(0) + newq(1) * vk(1)) / (sqrt(newq(0) ^ 2 + newq(1) ^ 2) * sqrt(vk(0) ^ 2 + vk(1) ^ 2))
        newq(0) = matriks kalimat 1
        vk(0) = [0.359184 -0.469388]

        newq(1) = matriks kalimat 2
        vk(1) = [0.043311 -0.030301]

        dst.
        apakah begitu mas ?
        kalau seperti itu, utk newq (query) nya tuh, nilai vk nya dmn ya ? kan cuma ada 4 baris dalam vk (yg sudah dihitung) ?
        maaf mas nanya nanya hehehe

        • pip Penulis

          Dalam kasus ini
          newq = [0.027255 -0.032204]

          maka
          newq(0) = 0.027255 dan newq(1) = -0.032204

          sedangkan dalam kasus ini
          vk =
          [0.359184 -0.469388]
          [0.043311 -0.030301]
          [0.527328 -0.60895]
          [0.768789 0.638699]

          Matriks tersebut berjumlah 4 baris karena terdapat 4 dokumen yang digunakan sebagai input. Nilai vk(0) dan vk(1) adalah mengikuti baris dokumen dimana perhitungan dilakukan. Sehingga:
          untuk dokumen 1 -> vk(0) = 0.359184 dan vk(1) = -0.469388
          untuk dokumen 2 -> vk(0) = 0.043311 dan vk(1) = -0.030301
          dan seterusnya

        • WaitingForUs

          itu cara mencari similaity, dari referensi ya, kalo blh tau, referensinya dr mana ya mas ?
          makasih mas atas penjelasannya

    • pip Penulis

      Saya tidak memahami maksud kolerasi dari apakah yang anda maksud, tetapi pada intinya contoh implementasi akan menghasilkan output berupa matriks2 dan nilai similarity sesuai dengan penjelasan diatas. Jika nilai similarity bukanlah yang anda cari maka diperlukan langkah modifikasi tambahan untuk mendapatkan hasil korelasi yang anda inginkan.