Contoh Algoritma LSI


LSI (Latent Semantic Indexing) dibuat untuk mendukung information retrieval dan memecahkan masalah ketidaksesuaian antara kamus pemakai dengan penulis dokumen. Asumsi yang mendasari LSI adalah terdapat sebuah struktur pokok atau “latent” yang mempresentasikan hubungan antar kata. LSI menerima sebuah vektor atau matrik dari sekumpulan dokumen, dimana setiap baris mewakili satu term (bisa kata atau frase), tiap kolom mewakili satu dokumen, dan tiap selnya akan berisi nilai bobot kata terhadap dokumen. Bobot dari kata tiap dokumen dapat berisi Term Frequency atau juga menggunakan TF-IDF (dalam contoh yang akan saya tuliskan mengasumsikan penggunaan TF).

LSI menggunakan SVD (Singular-Value Decomposition) untuk memodelkan relasi asosiatif antara term. Ide dasar SVD adalah menerima kumpulan data dengan dimensi dan variabel tinggi serta menguranginya ke dalam ruang dimensi yang berukuran lebih kecil untuk menampakkan lebih jelas sub struktur dari data asli dan mengurutkannya mulai dari paling bervariasi sampai dengan tidak bervariasi. Dalam SVD, sebuah rectangular matrix (matrik yang ukuran n x m tidak sama) terurai ke dalam perkalian (product) tiga matrik yang lain.

A = USVT

dimana matrik pertama (U) adalah matrik m x m left singular vector, sedangkan VT adalah matrik n x n right singular vector. Left dan Right Singular Vector adalah matrik orthogonal, di mana UTU=I, VTV=I. Kolom matrik U adalah orthonormal eigenvector dari AAT, sedangkan kolom matrik V adalah orthonormal eigenvector ATA. Matrik S merupakan matrik diagonal yang berisi akar pangkat eigenvalue dari matrik U atau V dalam urutan descending.

Saya akan mencoba menuliskan langkah-langkah perhitungan SVD berdasar contoh 3 buah string berikut :


D1 = Manajemen Sistem Informasi

D2 = Sistem Sumber Daya Manusia

D3 = Manajemen Informasi Penggajian

Berdasar ketiga dokumen tersebut, kita dapat membentuk sebuah matrix A sebagai berikut :

matrik_A

Langkah utama yang perlu diselesaikan adalah mendekomposisikan matrik A menjadi 3 matrik lain menggunakan SVD. Untuk perhitungan pada tiap langkah, saya menggunakan bantuan BlueBit Matrix Calculator dan mengikuti tahapan yang ditulis oleh Gerald Kowalski (hal 48 – 53).

Langkah 1: Hitung ATA.

3.000 1.000 2.000
1.000 4.000 0.000
2.000 0.000 3.000

Langkah 2: Temukan determinan sehingga |ATA-CI|=0. Hasil determinan ini digunakan untuk mendapatkan Eigenvalue dan singular value yang akan bermanfaat untuk membentuk matrik S.

langkah 2 SVD

Untuk menghitung eigenvalue dari mattrik di atas, saya menggunakan bantuan Wolfram. Dari tool ini saya mendapatkan 3 buah nilai c1 = 5.39138, c2 = 3.77287, c3 = 0.835752, dimana |c1| > |c2| > |c3|

Dari nilai eigenvalue tersebut, kita dapat menghitung Singular value sebagai berikut :

daum_equation_1366177122273

Langkah 3: Hitung Eigenvector dengan mengevaluasi (ATA-ciI)Xi=0. Berdasar hasil Wolfram saat menghitung Eigenvalue pada langkah 2, diperoleh Eigenvector adalah sebagai berikut :

Eigenvector

Dari setiap Eigenvector tersebut, kita normalisasikan dengan membagi setiap nilai dari tiap Eigenvector dengan panjang tiap vektor:

Normalisasi Eigenvector

Langkah 4: Bentuk matrik V dengan menggunakan hasil dari kalkulasi normalisasi Eigenvector sebagai kolom dalam matrik V

Matrix VLangkah 5: Bentuk matrik U dengan U=AVS-1.

MatrixU

Tahapan perhitungan SVD ini dapat dikatakan sebagai sebuah langkah lanjut dalam proses indexing dalam sistem Information Retrieval. Dalam hal ini, setelah mendapatkan SVD, biasanya akan dilakukan tahapan berikutnya yaitu untuk pengurangan ukuran dimensi, sebanyak k. Untuk nilai k yang terbaik memang perlu untuk dilakukan percobaan, sehingga penentuan nilai k yang optimal menjadi kesempatan terbuka luas untuk diteliti oleh para matematikawan. Dalam contoh kita ini, dimisalkan nilai k=2, sehingga kita akan mereduksi dimensi SVD menjadi:

svd_k

Seperti yang sudah kita ketahui bahwa matrik A berisi sekumpulan n dokumen. Sedangkan matrik V harus berisi n baris, dimana setiap baris berisi koordinat dari sebuah vektor dokumen. Untuk sebuah dokumen, vektor d adalah d = dTUS-1. Dalam LSI, setiap query dapat diperlakukan sebagai sebuah dokumen, sehingga vektor q adalah q = qTUS-1. Terkait dengan reduksi dimensi sebesar k, maka vektor dokumen, d, dan vektor query, q, dapat dituliskan sebagai:

d = dTUkSk-1

q = qTUkSk-1

Dengan perlakuan tersebut, maka antara vektor query, q, dan sebuah vektor dokumen, d, dapat dihitung koefisien similarity dengan cosinus sebagai berikut :

sim(q,d)=sim(qTUkSk-1, dTUkSk-1)

Sekarang kita dapat menghitung rangking semua dokumen terhadap query yang diberikan. Misal query yang diberikan adalah informasi daya manusia. Vektor query dapat dibentuk sebagai berikut :

vector_q

 

Dengan terbentuknya vektor untuk query tersebut, maka sekarang kita dapat menghitung koefisien similarity menggunakan cosinus antara query dengan tiap dokumen, sebagai berikut:

cosinus_q_d

 

Dari hasil perhitungan koefisien similarity tersebut, dapat dituliskan urutan dokumen yang paling dekat dengan query adalah D2, D3, D1.

Demikian sedikit contoh tentang LSI dari apa yang dapat saya pahami. Untuk penerapan yang sesungguhnya, maka akan lebih baik jika dapat menerapkan pustaka yang sudah siap, seperti JAMA: Java Matrix Package yang sudah memberikan operasi matrik sangat lengkap.

Jika dirasa ada yang salah dalam contoh di atas, jangan sungkan-sungkan untuk memberi masukannya. Thanks.