Latent Semantic Analysis - Singular Value Decomposition

Mau sharing mengenai pemahaman LSA - SVD yang udah nempel di kepala, walau belum 100% paham pengimplementasiannya ke dalam coding... hehe, cekidot...

Latent Semantic Analysis (LSA) merupakan teknik matematika/statistika untuk mengekstraksi dan menyimpulkan hubungan kontekstual arti kata yang diaplikasikan pada bagian teks yang dibutuhkan (Landauer, Foltz and Laham, 1998). Pada LSA, dilakukan preprocessing yang salah satunya berfungsi sebagai penentu kumpulan term untuk direpresentasikan dalam sebuah matriks semantik dan kemudian diolah secara matematis menggunakan teknik aljabar linier Singular Value Decomposition (SVD), sehingga dalam hal ini, query dapat dibandingkan dengan hasil SVD untuk menghitung similaritas antara query-document (Baker, 2005). Selain itu, juga dilakukan representasi ke dalam bentuk matriks, sehingga dari hasil dekomposisi SVD, terdapat tiga jenis operasi perbandingan yang dapat dilakukan yaitu:

1. Membandingkan dua kata (terms)
2. Membandingkan dua dokumen (documents)
3. Membandingkan kata (terms) dengan dokumen (documents)

Berbeda dari dua operasi sebelumnya yang memerlukan penghitungan  cosine similarity, untuk membandingkan kata i dengan dokumen j dapat diketahui dari nilai cell(i,  j) dari matriks aproksimasi kata-dokumen yang didapat dari perhitungan SVD.

(Deerwester et al., 1990)

Gambar 1 - Representasi geometri 2 dimensi dari term dan dokumen pada analisis SVD

Pada gambar di atas, kumpulan term yang ada dipetakan keberadaannya ke tiap dokumen, sehingga didapatkan nilai keberadaan tiap term pada dokumen-dokumen yang ada, sehingga isu yang muncul adalah “seberapa dekat hubungan antara term i dengan dokumen j?”. Melalui standar informasi pendekatan sistem temu balik, untuk membandingkan dua baris, kolom, atau menguji cell digunakan matriks X, yang terdiri dari term pada dokumen (Deerwester et al., 1990). Namun kita menggunakan X^ yang merepresentasikan pola dari X dan nilainya mendekati X yang sebenarnya. Karena X^ = TSD’ (Deerwester et al., 1990), maka dapat digambarkan sebagai berikut.

T : mendeskripsikan baris asli sebagai vektor turunan nilai faktor ortogonal
S : adalah matriks diagonal yang memuat nilai skala jika ketiga komponen matriks dikalikan
D : mendeskripsikan kolom seperti matriks T
t : adalah jumlah baris pada X
d : adalah jumlah kolom pada X
m : adalah rank pada X (≤min(t,d))

Berikut merupakan contoh pengimplementasian rumus di atas.

                                    

                                         Misal, X =

 

Dengan,
T (9 dimensi vektor singular kiri untuk 12 term)
S (matriks diagonal dari 9 nilai singular)
D (9 dimensi vektor singular kanan untuk 9 dokumen)

Maka untuk mencari X^ (agar mengetahui keterhubungan antara term dan dokumen lebih detil), maka perlu untuk mencari matriks T, S, dan D^T untuk kemudian dihitung ke dalam rumus yang telah disebutkan di atas.

Untuk mencari T, dilakukan:

1. Mencari hasil dari XX^T
2. Mencari eigenvalue dan eigenvector dari XX^T. Eigenvector adalah vektor tak nol yang memenuhi persamaan. Dimana A adalah matriks segiempat, λ bernilai skalar, dan v adalah eigenvector / vektor karakteristik. λ adalah eigenvalue / akar karakteristik nya.
3. Konversi matriks vektor ke matriks ortogonal menggunakan proses Gram-Schmidt orthonormalization

Gambar 2 - Hasil matriks T

Untuk mencari D, dilakukan:

1. Mencari hasil dari X^TX
2. Mencari eigenvalue dan eigenvector dari X^TX
3. Konversi matriks vektor ke matriks ortogonal menggunakan proses Gram-Schmidt orthonormalization
4. Didapatkan D, namun yang dibutuhkan adalah D^T, maka dilakukan transpose terhadap D

Gambar 3 - Hasil matriks D transpose

Untuk mendapatkan S, hanya perlu mengakarkan nilai eigenvalue yang sudah didapatkan dan merangkaikan dalam matriks secara diagonal.

Gambar 4 - Hasil matriks S

Lalu dimasukkan ke dalam rumus perkalian matriks berikut,

Sehingga didapatkan hasil berikut,

Dari hasil tersebut, ditemukan dokumen yang paling mewakili makna dari kumpulan term yang ada. Sehingga dapat diberikan rekomendasi dokumen sesuai dengan nilai yang dihasilkan.