TBI18-TI15B-P7-ALGORITMA LATENT SEMENTIC INDEXING-AGUNG NURIZAL

ALGORITMA LATENT SEMENTIC INDEXING

  1. Pengertian

Latent Semantic Analysis( LSA ) metode yang dipatenkan pada tahun 1988 (US Patent 4,839,853) oleh Scott Deerwester, Susan Dumais, George Furnas, Richard Harshman, Thomas Landauer, Karen Lochbaum dan Lynn Streeter. Dalam konteks aplikasinya ke pencarian informasi, metode LSA ini juga  disebut sebagai  Laten Semantic Indexing (LSI). LSA dapat ditafsirkan sebagai cara yang cepat dan praktis untuk mendapatkan perkiraan perkiraan substitutability kontekstual penggunaan kata-kata dalam segmen teks yang besar yang belum ditentukan makna kesamaan antara kata-kata dan segmen teks yang mungkin mencerminkan suatu hubungan tertentu. Sebagai metode praktis untuk mengkarakterisasi arti dari  kata, LSA menghasilkan ukuran hubungan katakata, bagian kata  dan bagian-bagian yang berkorelasi dengan beberapa fenomena kognitif manusia yang melibatkan asosiasi atau kesamaan semantik. Konsekuensi praktis dari metode LSA ini, memungkinkan kita untuk sangat mendekati penilaian manusia untuk menilai kesamaan makna antara kata dan secara objektif memprediksi konsekuensi dari keseluruhan kata berdasarkan kesamaan antara bagian-bagian kata serta perkiraan yang kata yang sering muncul.

Teknik Latent Semantic Analysis (LSA) banyak digunakan dalam Natural Language Processing. Contoh penggunaan LSA adalah dalam penilaian esai, sumarisasi, dan klasifikasi dokumen secara otomatis. Landauer dan Dumais (1997) mengajukan teknik yang bernama Latent Semantic Analysis (LSA). LSA (Latent Semantic Analysis) adalah metode statistik aljabar yang mengekstrak struktur semantik yang tersembunyi dari kata dan kalimat (R. Peter, S. G, D. G, & S. Kp, 2009).

 

  1. Konsep

Cara kerja LSA ialah dengan menghasilkan sebuah model yang didapat dengan mencatat kemunculan-kemunculan kata dari tiaptiap dokumen yang direpresentasikan dalam sebuah matriks yang dinamakan term-document matrix, setelah itu dilakukan proses Singular Value Decomposition (SVD) yang akan digunakan untuk mendapatkan Cosine Similarity (nilai kemiripan) antara satu dokumen dengan dokumen yang lain (Landauer, Foltz, & Laham, 1998).

 

Langkah awal adalah data training dibuat menjadi matriks kata dokumen, sehingga menghasilkan matriks kata dokumen dan dictionary. Matriks kata dokumen direduksi dimensi oleh SVD (Singular Value Decompotion) ke dimensi 300 , sehingga menghasilkan matriks ruang semantik, yang di dalamnya berisi vektor-vektor kata. Data dari dokumen artikel uji coba dibuat menjadi vektor kata dokumen, sehingga menghasilkan matriks kalimat dan matriks topik sesuai dengan dictionary dari data training, yang di dalamnya berisi vektor-vektor kalimat yang mewakili setiap kalimat yang ada di dalam dokumen, dan vektor topik yang mewakili topik inti dokumen. Topik adalah kalimat yang ada pada semua dokumen yang digabung menjadi satu.  Penilaian yang ada pada metode LSA adalah melakukan perhitungan cosine similarity antara vektor kalimat dengan vektor topik, sehingga menghasilkan score setiap kalimat yang akan digabungkan pada saat menghitung nilai score awal pada tahap maximum marginal relevance. Asumsi bahwa dokumen uji akan mencakup beberapa kata yang ada pada korpus. Pengguna dapat mengambil asumsi bahwa ada berapa banyak kata pada korpus yang harus dicakup pada dokumen berita, misalkan ada sebanyak n. Untuk mendapatkan score setiap kalimat, sistem akan mengukur seberapa dekat makna semantik antara kalimat dengan seluruh kata yang ada pada topik. Kalimat yang dianggap dicakup oleh topik dalam dokumen uji adalah kalimat yang menghasilkan cosine similarity tertinggi. Hal ini dilakukan dengan membandingkan vektor kalimat dengan vektor topik, kemudian akan didapatkan nilai akhir yang dilakukan dengan cara mengambil cosine similarity dengan nilai tertinggi.

 

 

  1. Algoritma LSI

 

Secara global, alur proses metode Latent Semantik Indexing (LSI) dapat diilustrasikan

dalam gambar.

 

Pada Gambar diatas kita dapat melihat alur proses dari metode latent semantic indexing dibagi 2 (dua) kolom, yaitu kolom sebelah kiri yaitu query dan kolom sebelah 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, kemudian matriks kata-dokumen (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 (Bunyamin, 2005).

 

Algoritma yang sering diimplementasikan dengan LSI :

  1. Algoritma Singular Value Decompositiion (SVD)

 

Pertama kali diusulkan oleh Eckartand Young, termasuk metode eksplorasi statistik multidimensi dengan latar belakang metematika aljabar linier. Termasuk algoritma teknik pengurangan dimensi yang paling cepat proses kerjanya dibanding teknik pengurangan dimensi lainnya seperti PCA, ICA dan fastICA (extensionICA) merupakan metode matematis untuk menguraikan matriks tunggal, dengan mengkompres menjadi tiga matriks yang lebih kecil dengan ukuran yang sama. Cara kerjanya mengurangi data pada kolom dan baris.

Algoritma Singular Value Decomposition (SVD) mempunyai kelebihan pada efisiensi waktu proses untuk digunakan pada dataset yang berskala besar.Masalah pada data dibidang high dimentional biomedis disebabkan karena data tersebut memiliki ribuan atribut serta ribuan jumlah record yang saling berkorelasi (multicolinearity) dan menghasilkan data yang kompleks. Data yang kompleks memiliki banyak kebisingan (noise), anomali (outlier), elemen yang hilang (missing value), tidak konsisten dan juga entitas data tidak berhubungan.

Pada Penelitian ini menggunakan algoritma singular value decomposition untuk mengurangi dimensi pada high-dimentional biomedical data set.

  1. Vector Space Model (VSM)

 

Vector Space Model (VSM) adalah cara model algoritma konvensional yang biasa digunakan dalam proses temu kembali informasi. Prosesnya dengan menghitung kemiripan dua buah vektor, yaitu antara vektor dari corpus dan vektor dari query (Kontostathis 2007). Untuk melakukan perhitungan terhadap kemiripan antar vektor digunakan rumus Cosine Similarity pada persamaan (5) (Parsons 2009):

CosSim (di,q) = .q|||| (5)

dimana di adalah dokumen vector ke i yang diambil dari nilai matriks V, q adalah kata kunci/query vector hasil perhitungan LSI.

 

  1. K-Nearest Neighbor (KNN)

 

Adalah algoritma pendekatan untuk mencari kasus dengan menghitung kedekatan antara kasus baru dengan kasus lama, yaitu berdasarkan pada pencocokan bobot dari sejumlah fitur yang ada.[10]  Menurut Olivas [11], k-Nearest Neighbor Imputation termasuk dalam Machine Learning

 

Solutions dalam teknik imputasi. Metode ini menangani missing value pada suatu data dengan melakukan imputasi dengan mempertimbangkan nilai yang diberikan oleh record yang paling mirip.

 

  1. Algoritma CDS (Campbell, Dudek, Smith)

 

Algoritma CDS merupakan salah satu algoritma umum yang digunakan untuk menjadwalkan urutan job pada permasalahan flowshop dengan lebih dari 2 mesin guna mendapatkan sebuah waktu penyelesaian atau makespan yang mendekati minimum. Algoritma ini merupakan pengembangan dari algoritma Johnson.

 

 

 

  1. Implementasi

 

Sistem temu kembali informasi dalam dokumen menggunakan metode LSI dikembangkan berbasis desktop menggunakan bahasa java. Proses yang berjalan di dalam sistem ini dibagi menjadi proses pengindexan dan proses pencarian. Proses pengindeksan merupakan proses untuk membuat indeks dan representasi dokumen di dalam komputer menjadi bentuk  vektor dokumen. Indeks merupakan kumpulan kata-kata atau konsep yang telah dipilih dan digunakan sebagai petunjuk menuju informasi atau dokumen terkait.

 

Proses pengindeksan mencakup operasi teks, pembobotan, pembentukan matriks term document dan penghitungan SVD ( singular value decomposition). Operasi teks akan mengubah teks di dalam dokumen menjadi potongan-potongan kata dasar atau stemming dalam huruf kecil dan menghapus kata sambung dan kata-kata lainnya yang tidak digunakan dalam temu kembali informasi. Pembobotan merupakan metode yang umum dan efektif dalam meningkatkan performa pencarian kembali dalam model vektor yang dilakukan dengan mentransformasi frekuensi kasar kemunculan suatu term di dalam dokumen menggunakan suatu fungsi.

 

Contoh penerapan LSA dalam jurnal Ria Hari Gusmita dan Ruli Manurung yang berjudul “Penerapan Latent Sementic Analysis(LSA Untuk Menentukan Kesamaan Makna antara Kata dalam Bahasa Inggris dan kata dalam Bahasa Indonesia)”.

 

file presentasi :ALGORITMA LATENT SEMENTIC INDEXING P7

 

  1. Referensi

 

http://hirupmotekar.com/2017/05/30/dwi-ngafifudin-konsep-dan-prinsip-serta-algoritma-dalam-latent-sementic-indexing/

http://ir.cs.ui.ac.id/inacl2016/paper/INACL_2016_paper_1-2-3.pdf

http://hirupmotekar.com/2017/05/30/novi-kurniawan-tbi-pertemuan-ketujuh-latent-semantic-indexing/

http://ir.cs.ui.ac.id/inacl2016/paper/INACL_2016_paper_1-2-3.pdf