isi makalah kelompok 6 (Topik Khusus Basis Data Multimedia) bahasan Latent Semantik Indexing (LSI)

02.30 |

PEMBAHASAN

2.1. Pengertian Metode 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 adalah sebuah metode baru dalam algoritma search engine yang sedang dikembangkan Google Corporation. Dengan metode ini, Google menganalisis kata kunci dengan cara baru, bukan lagi berdasarkan pencocokkan kata secara leksikal. Kata yang dicari tidak hanya kata kuncinya saja seperti pada algoritma pada umumnya, tetapi kata-kata yang berhubungan dengan kata kunci juga dicari.

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 sekunpulan objek yang berhubungan.

Keuntungan Latent Semantik Indexing sebagai berikut :

1. True (Latent) Dimensions

Asumsi di LSI adalah bahwa dimensi baru lebih baik representasi dokumen dan query. Metafora yang mendasari istilah “latent” adalah bahwa dimensi-dimensi baru adalah benar. Ini benar representasi kemudian tertutup oleh proses generasi yang menyatakan dimensi tertentu dengan satu set kata-kata dalam beberapa dokumen dan berbagai set kata-kata dalam dokumen lain.

2. Sinonim

Mengacu pada fakta bahwa konsep dasar yang sama dapat dijelaskan menggunakan istilah yang berbeda. Strategi pengambilan Sinonim adalah istilah untuk kata yang bermakna sama.

Contoh, kata “sulit” merupakan sinonim untuk “sukar” karena “sulit” dan “sukar” bermakna sama.

3. Polisemi

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.

4. Term Dependence

Model ruang vektor tradisional menganggap merdeka dan istilah melayani sebagai dasar vektor ortogonal dari ruang vektor.

Kekurangan Latent Semantic Indexing sebagai berikut :

1. Storage

Banyak dokumen yang memiliki lebih dari 150 istilah yang unik. Jadi representasi vektor jarang akan memakan ruang penyimpanan lebih dari representasi SVD jika kita mengurangi sampai 150 dimensi.

2. Efesiensi

Salah satu kecepatan yang paling penting dalam pencarian vektor ruang berasal dari menggunakan indeks terbalik. Akibatnya, hanya dokumen yang memiliki bebrapa istilah umum dengan query harus diperiksa selama pencarian. Jika query memiliki jangka lebih dari perwakilannya dalam ruang vektor LSI maka hasil kali dalam nilai kemiripan akan mengambil lebih banyak waktu untuk menghitung dalam ruang panjang.

3. LSI dan dataterdistribusi normal

Beanr-benar dirancang untuk data terdistribusi normal namun distribusi tersebut tidak cocok untuk menghitung data, dan data perhitungan yang panjang terdiri dari dokumen metriks.

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”.

2.2. Metode Latent Semantic Indexing Secara Keseluruhan

Secara global, alur proses metode Latent Semantic Indexing (LSI) dapat diilustrasikan dalam gambar 2.2

Gambar 2.2 Alur proses dari metode latent semantic indexing

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 pada koleksi dokumen, 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.

2.3. Langkah dalam pendekatan Latent Semantic Indexing (LSI) :

1. Table Creation

2. Singular Value Decompositions (SVD) Construction

3. Vector Identication

4. Index Creation.

2.3.1 Table Creation

Query: human-computer interaction

Dataset:

c1 Human machine interface for Lab ABC computer application

c2 A survey of user opinion of computer system response time

c3 The EPS user interface management system

c4 System and human system engineering testing of EPS

c5 Relations of user-perceived response time to error measurement

m1 The generation of random,binary, unordered trees

m2 The intersection graph of paths in trees

m3 Graph minors IV: Widths of trees and well-quasi-ordering

m4 Graph minors: A survey

{X}=

r (human.user) = -.38

r (human.minors) = -.29

gambar 1 : matriks konteks X di atas, dibentuk dari judul lima artikel tentang human computer interaction dan empat artikel tentang graph theory. Isi dari sel menandakan jumlah kemunculan sebuah kata (baris) dalam judul (kolom) untuk kata yang muncul, paling sedikit di dua buah judul.

{X}={W}{S}{P}'

{W}=

S { }=

P { }=

Gambar 2 : SVD yang lengkap dari matriks konteks

r (human.user) = .94

r (human.minors) = -.83

Gambar 3: rekonstruksi dua dimensi dari matriks X yang terdapat pada gambar 1, berdasarkan pada kolom dan baris yang diarsir dari SVD yang ditunjukkan pada gambar 2. Membandingkan baris dan sel yang diarsir dan dikotakkan dari gambar 1 dan gambar 3 menggambarkan bagaimana LSA mengenali kesamaan hubungan dengan mengubah nilai perkiraan data.

Langkah pertama adalah merepresentasikan teks sebagai matriks yang setiap barisnya mewakili kata yang unik dan setiap kolom mewakili kalimat. Setiap sel berisikan frekuensi kemunculan kata di setiap kolom. Selanjutnya, isi dari sel merupakan transformasi preliminary yag detilnya akan dideskripsikan kemudian, yang masing – masing frekuensi sel diberi bobot oleh sebuah fungsi yang menghasilkan keutamaan kata dalam sebuah

kalimat.

Selanjutnya, metode ini mengaplikasikan SVD (Singular Value Decomposition) ke dalam matriks. Dalam SVD, matriks persegi didekomposisi menjadi tiga matriks lainnya. Matriks pertama mendeskripsikan baris asli sebagai vector turunan nilai factor orthogonal. Satu matriks lagi mendeskripsikan kolom seperti sebelumnya. Matriks ketiga adalah matriks diagonal yang memuat nilai skala jika ketiga komponen matriks dikalikan.

Dari matriks-matriks yang telah dibuat, akan ditemukan kata yang berhubungan dengan katakunci yang dicari. Kemudian, dari kata-kata tersebut, dicarilah halaman-halaman web yang sesuai dari daftar alamat web yang terdapat pada basis data.

2.3.2 SVD ( Singular Value Decomposition ) Construction

Singular Value Decomposition (SVD) adalah suatu metode untuk mendekomposisi suatu matriks, A berukuran m x n, menjadi 3 (tiga) buah matriks, yaitu U, S dan V seperti pada ilustrasi di bawah ini.

A = U S V^T

Hasil SVD adalah matriks U adalah matriks berukuran m x k dan V matriks bujursangkar n x k, keduanya mempunyai kolom-kolom ortogonal sedemikian sehingga ;

U^TU = V^TV = I

Dan S adalah matriks U diagonal berukuran k x k. Entry-entry di diagonal utama matriks S adalah nilai singular dari matriks A.

Hasil SVD dapat lebih dipahami matriks A ditulis dengan interpretasi yang berbeda. Bila u₁, u₂, ..., u_k adalah vektor-vektor kolom dari matriks U, 𝜎₁, 𝜎₂, ... , 𝜎_k adalah entry-entry di diagonal utama dari matriks S, dan v_1,v_2,..., v_k adalah vektor-vektor kolom dari matriks V. Maka matriks A dapat ditulis sebagai ;

Nilai-nilai 𝜎₁, untuk i = 1, 2, ... , k pada persamaan diatas diurutkan menurun dari yang terbesar sampai terkecil. Apabila beberapa nilai 𝜎₁yang besar diambil dan nilai 𝜎₁yang kecil (mendekati nol) dibuang sehingga diperoleh suatu aproksimasi dari A yang baik.

Contoh :

Menghitung SVD matriks A_(mxn) = A_(2x3)

Dapatkan Singular Value Decomposition (SVD) dari matrik yang berukuran m×n berikut ini:

B_(2×3) =

Jawab:

1. Menghitung Matrik B^TB dan BB^T

B^TB = C = =

BB^T = D = =

2. Mencari Eigenvalue (l) dari Matrik B^TB dan BB^T

Eigenvalue Matrik B^TB: ÷C-lIê= 0

Þ [(20-l)(8-l)(20-l) + 4(-4)16 + 16(4)(-4)] - [16(8-l)16 + (-4)²(20-l) + 4²(20-l)] = 0

Þ [-l³ + 48l² -720l + 3200 -256 -256] - [256(8-l) + 16(20-l) + 16 (20-l)] = 0

Þ (-l³ + 48l² -720l + 2688) - (2048 - 256l + 320 - 16l + 320 -16l) = 0

Þ (-l³ + 48l² -720l + 2688) - (2688 - 288l) = 0

Þ -l³ + 48l² - 432l = 0

Þ -l(l² - 48l - 432) = 0

Þ -l (l - 12)(l - 36) = 0

l₁ = 0, l₂ = 12, dan l₃ = 36

Jika dinyatakan dalam bentuk matrik diagonal D₁² =

Eigenvalue Matrik BB^T: ÷D-lIê= 0

Þ [(24-l)(24-l) - 12²] = 0

Þ (l²- 48l + 576 - 144) = 0

Þ l²- 48l + 432 = 0

Þ (l - 12) (l - 36) = 0

l₁ = 12 dan l₂ = 36

Jika dinyatakan dalam bentuk matrik diagonal D₂² =

Pada proses mencari eigenvalue matrik B^TB (matrik C) didapatkan l₁ = 0, mengacu pada prosedur penyelesaian SVD matrik m×n terdapat catatan bahwa: jika dalam perhitungan eigenvalue didapatkan l = 0 maka untuk prosedur perhitungan eigenvalue l = 0 diabaikan yang berakibat eigenvektor untuk kolom l = 0 pada prosedur selanjutnya akan dihilangkan dari matrik eigenvektornya.. Sehingga, matrik diagonal D₁²= D₂² = D².

D² =

3. Mencari Eigenvektor Matrik B^TB dan BB^T

Untuk l₁ = 0

Eigenvektor Matrik B^TB:

· Untuk l₁ = 0 (C – l₁I) =

Pers.1

Pers.2

Pers.3

Eliminasi Pers.1 dan Pers.3:

20x₁₁ + 4x₁₂ + 16x₁₃ = 0

16x₁₁ – 4x₁₂ + 20x₁₃ = 0

36x₁₁ + 36x₁₃ = 0

x₁₁+ x₁₃= 0

x₁₁ = – x₁₃ Pers.4

Subsitusikan Pers.4 ke Pers.2

4(-x₁₃) + 8x₁₂ - 4x₁₃ = 0

8x₁₂ - 8x₁₃ = 0

x₁₂ = x₁₃Pers.5

Proses normalisasi untuk :

= = =

= =

· Untuk l₂ = 12 (C – l₂I) =

Pers.1

Pers.2

Pers.3

Eliminasi Pers.1 dan Pers.3:

8x₂₁ + 4x₂₂ + 16x₂₃ = 0

16x₂₁ – 4x₂₂ + 8x₂₃ = 0

24x₂₁ + 24x₂₃ = 0

x₂₁+ x₂₃= 0

x₂₁ = – x₂₃ Pers.4

Subsitusikan Pers.4 ke Pers.2

4(-x₂₃) - 4x₂₂ - 4x₂₃ = 0

-4x₂₂ - 8x₂₃ = 0

x₂₂ = -2x₂₃Pers.5

Proses normalisasi untuk :

= = =

= =

· Untuk l₃ = 36 (C – l₃I) =

Pers.1

Pers.2

Pers.3

Eliminasi Pers.1 dan 4 × Pers.2:

-16x₃₁ + 4x₃₂ + 16x₃₃ = 0

16x₃₁ – 112x₃₂ + 16x₃₃ = 0

108x₃₂ = 0

x₃₂= 0 Pers.4

Subsitusikan Pers.4 ke Pers.3

16x₃₁ - 4(0) - 16x₃₃ = 0

16x₃₁ - 16x₃₃ = 0

x₃₁ = x₃₃Pers.5

Proses normalisasi untuk :

= = =

= =

Sehingga, eigenvektor yang didapatkan adalah:

X =

Akan tetapi, untuk prosedur selanjutnya eigenvektor yang digunakan adalah eigenvektor dari kolom yang nilai eigenvalue () lebih dari nol (positif).

Q =

Eigenvektor Matrik BB^T:

· Untuk l₁ = 12 (D – l₁I) =

Pers.2

Pers.1

12x₁₁ + 12x₁₂= 0

x₁₁ + x₁₂ = 0

x₁₁ = – x₁₂Pers.3

Proses normalisasi untuk :

= = =

= =

· Untuk l₂ = 36 (D – l₂I) =

Pers.2

Pers.1

-12x₂₁ + 12x₂₂= 0

-x₂₁ + x₂₂ = 0

x₂₁ = x₂₂Pers.3

Proses normalisasi untuk :

= = =

= =

Sehingga, eigenvektor yang didapatkan adalah:

Y =

BAB III

PENUTUP

III.1 Kesimpulan

Metode Latent Semantic Indexing (LSI), sangat bermanfaat untuk digunakan pada search engine, karena dengan metode ini search engine dapat mencari dokumen yang diinginkan oleh pengguna dengan lebih akurat. Hal ini terbukti pada search engine Google yang mampu menghasilkan pencarian yang akurat dengan pemanfaatan waktu yang lebih sedikit.

Singular Value Decomposition (SVD) adalah suatu metode untuk mendekomposisi suatu matriks.

DAFTAR PUSTAKA

http://www.search-marketing.info/search-enginehistory/ diakses tanggal 03 Mei 2014.

http://bovis.gyuvet.ch/3dict/323webde.html diakses tanggal

http://www.cs.arizona.edu/classes/cs630/spring03/slides/jan-29.ppt

http://lsa.colorado.edu/papers/dp1.LSAintro.pdf