Konsep dan Prinsip serta Algoritma dalam model Latent Semantic Indexing
Information retrieval (IR) system digunakan untuk menemukan kembali (retrieve) informasi-informasi yang relevan terhadap kebutuhan pengguna dari suatu kumpulan informasi secara otomatis
Mendapatkan hasil pencarian yang sesuai dengan kebutuhan dalam suatu koleksi dokumen yang besar merupakan hal sulit. Usaha pengguna secara manual untuk memilah-milah dokumen yang sesuai dengan kebutuhannya ternyata sangat besar. Hasil pencarian merupakan sejumlah dokumen yang relevan menurut sistem, namun relevansi merupakan hal yang subjektif.
Pada umumnya, dokumen dikatakan relevan dengan query apabila dokumen:
(1) Memuat kata atau kalimat yang sama dengan query atau
(2) Memuat kata atau kalimat yang bermakna sama dengan query
Sebagai contoh, terdapat query satu kata yaitu “sulit”. Pada point 1, informasi yang memuat kata “susah” atau “sukar” dinilai tidak relevan karena informasi yang relevan adalah informasi yang memuat kata “sulit”. Sedangkan pada point 2, informasi yang memuat kata “susah” atau “sukar” dinilai relevan karena “susah” atau “sukar” bermakna sama dengan “sulit”.
Makna kata dapat ditinjau dari dua istilah, yaitu sinonim dan polisemi (8). Sinonim adalah istilah untuk kata yang bermakna sama. Contoh, kata “sulit” merupakan sinonim untuk “sukar” karena “sulit” dan “sukar” bermakna sama. Sedangkan polisemi adalah istilah untuk kata yang sama namun maknanya berbeda. Contoh, kata “membajak” dalam “membajak sawah” dan “membajak VCD” merupakan polisemi karena kata “membajak” di kedua frase sama namun mempunyai arti yang berbeda
PENGERTIAN LATENT SEMANTIC INDEXING
Metode Latent Semantic Indexing (LSI) adalah metode yang diimplementasikan di dalam IR system dalam mencari dan menemukan informasi berdasarkan makna keseluruhan (conceptual topic atau meaning) dari sebuah dokumen bukan hanya makna kata per kata.
Latent Semantic Indexing (LSI) adalah metode pengindeksan dan pencarian yang menggunakan teknik matematika yang disebut Dekomposisi Nilai Singular (SVD) untuk mengidentifikasi pola hubungan antara istilah dan konsep-konsep yang terkandung dalam sebuah koleksi teks yang tidak terstruktur.
LSI didasarkan pada prinsip bahwa kata-kata yang digunakan dalam konteks yang sama cenderung memiliki makna yang sama. Fitur utama dari LSI adalah kemampuannya untuk mengekstrak konten konseptual dari suatu tubuh teks dengan mendirikan asosiasi antara istilah-istilah yang terjadi dalam konteks yang serupa.
Menurut SEMPO, latent semantic indexing menggunakan asosiasi kata untuk membantu search engine mengetahui apa yang ada di sebuah halaman web dengan lebih akurat. Pada dasarnya LSI adalah sebuah prinsip algoritma yang digunakan search engine untuk memproses persamaan kata atau sinonim dan memahami hubungan topik antar kata.
TUJUAN LATENT SEMANTIC INDEXING
Tujuan dari LSI adalah mendapatkan suatu pemodelan yang efektif untuk merepresentasikan hubungan antara kata kunci dan dokumen yang dicari. Dari sekumpulan kata kunci, yang tadinya tidak lengkap dan tidak sesuai, menjadi sekumpulan objek yang berhubungan.
Kosep / Alur metode Latent Semantic Indexing secara umum dapat di lihat sebagai berikut :
Penjelasan alurnya :
Alur proses dari metode Latent Semantic Indexing dibagi 2 (dua) kolom, yaitu kolom sebelah kiri yaitu query dan kolom sebelah kanan kanan yaitu, koleksi dokumen. Pada proses sebelah kiri, query diproses melalui operasi teks, kemudian vektor query dibentuk. Vektor query yang dibentuk dipetakan menjadi vektor query terpeta (mapped query vector). Dalam membentuk query terpeta, diperlukan hasil dekomposisi nilai singular dari koleksi dokumen. Pada koleksi dokumen, dilakukan operasi teks pada koleksi dokumen, kemudian matriks katadokumen (terms-documents matrix) dibentuk, selanjutnya dilakukan dekomposisi nilai singular (Singular Value Decomposition) pada matriks kata-dokumen. Hasil dekomposisi disimpan dalam collection index. Proses ranking dilakukan dengan menghitung relevansi antara vektor query terpeta dan collection index. Selanjutnya, hasil perhitungan relevansi ditampilkan ke pengguna.
Konsep Latent Semantic Indexing (LSI) merupakan metode IR yang membangun struktur koleksi dokumen dalam bentuk ruang vektor dengan menggunakan teknik aljabar linier, yaitu singular value decomposition.
Secara umum konsep LSI meliputi beberapa point :
1. Text Operations pada Query dan Document Collection.
Query dari pengguna dan koleksi dokumen dikenakan proses text operations. Proses text operations meliputi,
(i) mem-parsing setiap kata dari koleksi dokumen,
(ii) membuang kata-kata yang merupakan stop words,
(iii) mem-stemming kata-kata yang ada untuk proses selanjutnya.
2. Matrix Creation.
Hasil text operations yang dikenakan pada koleksi dokumen dikenakan proses matrix creation. Proses matrix creation meliputi,
(i) menghitung frekuensi kemunculan dari kata,
(ii) membangun matriks kata-dokumen. Baris matriks menunjukkan kata dan kolom matriks menunjukkan dokumen. Sebagai contoh, elemen matriks pada baris ke-1 dan kolom ke-2 menunjukkan frekuensi kemunculan kata ke-1 pada dokumen ke-2.
3. SVD Decomposition.
4. Query Vector Creation
Vektor Query, q dibentuk seperti membangun sebuah kolom dari matriks kata-dokumen. Contoh vektor query q :
dengan qj, j = 1,2,…..,m adalah frekuensi kemunculan kata Tj pada query
5. Query Vector Mapping.
Memberikan nilai r yang merupakan dimensi dari ruang vektor hasil perkalian baru.
6. Ranking
Kolom-kolom pada matriks VrT adalah vektor-vektor dokumen yang digunakan dalam menghitung sudut antara vektor dokumen dan vektor query.
Ranking dari dokumen relevan ditentukan oleh besar sudut yang dibentuk oleh vektor query dan vektor dokumen. Semakin kecil sudut yang dibentuk, semakin relevan query dengan dokumen.
7. Hasil Akhir
Perhitungan cosinus sudut antara query, q dan dokumen diperoleh dan diurutkan berdasarkan dari yang paling besar sampai yang terkecil. Nilai cosinus sudut yang terbesar menunjukkan dokumen yang paling relevan dengan query.
Query : apple
Selain mendapatkan hasil pencarian, pada bagian bawah google juga memberikan saran mengenai kata apa saja yang menurut google terkait dengan kata “apple”. Disini terlihat bahwa sebenarnya google masih tidak “terlalu yakin” dengan maksud kata yang dicari, karena kata-kata Apple itu sendiri bersifat sangat umum dan dapat berarti Apel sebagai buah-buahan (apple fruit), Apel sebagai brand gadget terkenal (apple laptops,apple ipod, apple store locator) ataukah apel sebagai perusahaan besar (apple jobs), dsb.
Algoritma Latent Semantic Indexing (LSI)
LSI (Latent Semantic Indexing) dibuat untuk mendukung information retrieval dan memecahkan masalah ketidaksesuaian antara kamus pemakai dengan penulis dokumen.
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.
Prinsip Kerja Latent Semantic Indexing (LSI)
Secara umum prinsip Latent Semantic Indexing tidak ada, namun dalam jurnal Jurnal Teknologi Informasi dan Ilmu Komputer (JTIIK) Vol. 1, No. 2 : prinsip kerja Latent Semantic Indexing (LSI) dan Similarity Based Histogram Clustering (SHC) untuk pembentukan cluster kalimat secara semantik, serta mengkombinasikan fitur Sentence Information Density (SID) dan Sentence Cluster Keyword (SCK) untuk pemilihan kalimat representatif cluster. Pengujian dilakukan pada dataset Document Understanding Conference (DUC) 2004 Task 2 dan hasilnya diukur menggunakan Recall-Oriented Understudy for Gisting Evaluation (ROUGE). Hasil pengujian menunjukkan bahwa metode yang diusulkan mampu mencapai nilai ROUGE-1 rata-rata sebesar 0,395 dan nilai ROUGE-2 rata-rata sebesar 0,106.
Contoh Implementasi Latent Semantic Indexing :
1. SISTEM PENDETEKSI PLAGIARISME PADA DOKUMEN TEKS BAHASA INDONESIA DENGAN MENGGUNAKAN METODE LATENT SEMANTIC ANALYSIS
Untuk membantu mendeteksi dokumen yang terindikasi plagiat, dibuatlah sebuah sistem yang dapat menghitung nilai similarity antar dokumen dengan menggunakan metode Latent Semantic Analysis. Metode Latent Semantic Analysis digunakan untuk mencari dokumen yang memiliki kesamaan teks dengan melalui beberapa tahap seperti tokenizing, stoplist, dan stemming. Untuk perhitungannya menggunakan algoritma model ruang vektor. Pada Tugas Akhir ini dilakukan dua skenario pengujian yaitu intra class dan ekstra class untuk mengetahui nilai similarity. Hasil pengujian skenario intra class ini dapat dilihat bahwa terdapat 119 abstrak terindikasi plagiat yang menunjukkan bahwa missed detection pada system terdapat pada 1 dokumen. Sedangkan pada skenario extra class pada fakultas yang sama maupun fakultas yang berbeda, masih menunjukkan terjadinya false detection dan menghasilkan nilai similarity yang melebihi threshold indikasi plagiat
2. PENERAPAN METODE LATENT SEMANTIC INDEXING PADA SEARCH ENGINE
Search Engine memegang peranan penting dalam perkembangan pencarian informasi – informasi melalui jaringan internet. Perkembangan teknologi Search engine pun semakin pesat. Jika dulu kita hanya mengenal yahoo! sebagai search engine yang paling populer dan banyak penggunanya, maka sekarang kepopuleran yahoo! mulai pudar dengan munculnya lawan tangguh yaitu Google. Salah satu keunggulan Google yaitu penggunaan algoritma yang lebih kompleks dan lebih mangkus sehingga dalam setiap pencarian, Google mampu menghasilkan hasil pencarian yang lebih banyak dengan penggunaan waktu yang lebih singkat. Salah satu metode yang digunakan adalah metode indexing. Saat ini Google telah mengembangkan metode baru yang mampu mempermudah penyaringan informasi yang disebut Latent Semantic Indexing.
3. Pencarian Semantik Dokumen Berita Menggunakan Essential Dimension of Latent Semantic Indexing dengan Memakai Reduksi Fitur Document Frequency dan Information Gain Thresholding.
Perkembangan informasi secara digital yang bertambah, menyebabkan dimensi data bertambah besar. Teknik proses temu kembali diperlukan agar mempermudah dalam melakukan pencarian. Dimensi data yang terlalu besar menyebabkan informasi yang penting menyebar terlalu luas, sehingga menjadi kurang informatif. Seleksi fitur dengan memanfaatkan reduksi digunakan untuk menyeleksi kata yang sifatnya penting di dalam dokumen teks. Seleksi fitur yang digunakan pada penelitian ini adalah kombinasi Document Frequency (DF) thresholding, dan Information Gain (IG). Hasil kombinasi dari kedua teknik tersebut menghasilkan matriks pembobotan dengan proses seleksi kata-kata yang penting, dan proses seleksi fitur dapat membantu mengurangi waktu komputasi. Matriks hasil seleksi fitur digunakan untuk perhitungan dalam mencari dokumen yang relevan antara query dan corpus. Essential Dimension of Latent Semantic Indexing (EDLSI), digunakan untuk melakukan pencarian dokumen yang relevan secara semantik. EDLSI merupakan teknik perbaikan dari LSI, dan proses yang digunakan hampir sama dengan LSI. Pada EDLSI terdapat parameter x yang merupakan bobot faktor dimana (0<=x <=1) dan masukan k-rank yang digunakan adalah lebih kecil dibanding menggunakan LSI. Penelitian ini mengunakan dua proses pengujian,dimana pengujian pertama adalah pengujian terhadap 90 data, dan pengujian kedua menggunakan 120 data. Dari hasil pengujian didapatkan nilai Mean Average Pr ecision (MAP) optimal ketika threshold 0.9, k-rank=2, dan x=0.7.
Referensi :
Bian, Rian. 2010. Pengertian Latent Semantic Indexing. https://ryanbian.wordpress.com/2010/06/15/pengertian-latent-semantic-indexing diakses 24/5/2017
Bunyamin, Hendra. 2015. Tesis : INFORMATION RETRIEVAL SYSTEM DENGAN METODE LATENT SEMANTIC INDEXING. INSTITUT TEKNOLOGI BANDUNG : Program Studi Rekayasa Perangkat Lunak
Ferdian, Edward., Hadisaputra, Rian dan Madjid, Nurkholis. PENERAPAN METODE LATENT SEMANTIC INDEXING PADA SEARCH ENGINE . Laboratorium Ilmu dan Rekayasa Komputasi Departemen Teknik Informatika, Institut Teknologi Bandung.
Pasnur,. Santika, Putu Prabu., Syaifuddin, Gus Nanang. 2014. SEMANTIC CLUSTERING DAN PEMILIHAN KALIMAT REPRESENTATIF UNTUK PERINGKASAN MULTI DOKUMEN. Jurnal Teknologi Informasi dan Ilmu Komputer (JTIIK) Vol. 1, No. 2, Oktober 2014 hlm. 91-97
Sari, Yuila Arum., Puspaningrum, Eka Yulia. 2013. Pencarian Semantik Dokumen Berita Menggunakan Essential Dimension of Latent Semantic Indexing dengan Memakai Reduksi Fitur Document Frequency dan Information Gain Thresholding. Seminar Nasional Teknologi Informasi dan Multimedia 2013. STMIK AMIKOM Yogyakarta
Tawisa, Jessy., Wirayuda, Tjokorda Agung Budi. 2012. Tugas Akhir. Universitas Telkom : Program Studi S1 Teknik Informatika.
Download Presentasi: Dian Restiani – Pertemuan 7 (Konsep dan Prinsip Serta Algoritma Latent Semantic Indexing)