Kesederhanaan VSM


Dalam bidang penelitian information retrieval (sistem temu kembali) terdapat salah satu metode perangkingan sederhana namun memberikan hasil yang sudah mencukupi untuk sebuah sistem pencarian terhadap dokumen. Metode tersebut kita kenal dengan nama Vector Space Model (VSM). Pada prinsipnya metode perangkingan pencarian dokumen ini didasarkan pada perhitungan jarak kemiripan dengan cosinus antara vektor dokumen dengan vektor query.

Ketika sebuah dokumen dimasukkan dalam suatu ruang vektor, maka kita dapat membayangkan sebuah ruang vektor yang memiliki dimensi luar biasa besar dan ditentukan oleh banyaknya term/kata yang terbentuk saat proses pengindeksan dokumen. Pengindeksan terhadap kumpulan dokumen yang dapat dicari merupakan sebuah proses tersendiri. Konsep umum yang diterapkan untuk pembuatan struktur indeks adalah menggunakan model inverted index. Dalam inverted index, kita mengenal ada sebuah daftar kamus (dictionary) yang berisi kata atau term hasil dari pemrosesan setiap dokumen. Dari setiap kata yang ada dalam dictionary, lalu terbentuk sebuah linked list yang berisi urutan dokumen yang mengandung term tersebut. (Lihat gambaran struktur tersebut dari Christopher D. Manning.)

Inverted Index

Sebelum dilakukan perhitungan rangking antara dokumen dan query, maka terlebih dahulu harus dihitung bobot setiap kata yang dimiliki tiap dokumen. Perhitungan bobot tiap kata dapat menggunakan pendekatan TF-IDF. Untuk contoh, saya kembali menggunakan tiga buah dokumen sebagai berikut :

D1 = Manajemen Sistem Informasi
D2 = Sistem Sumber Daya Manusia
D3 = Manajemen Informasi Penggajian

Langkah 1: Terhadap 3 dokumen tersebut, maka kita dapat membentuk sebuah matrik term frequency sebagai berikut :

Matrik TF

Langkah 2: Dengan terbentukanya matrik term frequency tersebut, maka sekarang dengan mudah kita dapat membentuk vektor query yang diberikan ke dalam sistem. Contoh query adalah “informasi daya manusia“. Sekarang vektor query yang dapat kita bentuk adalah :

q = {(tf-query-informasi/max-tf-query)*idf-informasi, (tf-query-daya/max-tf-query)*idf-daya, (tf-query-manusia/max-tf-query)*idf-manusia}

sehingga kita dapat memiliki vektor query sebagai berikut :

q = {(1/1)*0.176091, (1/1)* 0.477121 , (1/1)* 0.477121 }

Langkah 3: Sedangkan untuk tiap dokumen, kita dapat membentuk vektor sesuai dengan term yang dicari sebagai berikut :

  • d1 = {0.176091, 0, 0}
  • d2 = {0,  0.477121,  0.477121}
  • d3 = {0.176091, 0, 0}

Langkah 4: berikutnya kita hitung panjang vektor untuk d1, d2, d3, dan q.

  • d1 = sqrt(3*(0.18^2)) = 0.304999007
  • d2 = sqrt(0.18^2 + 3*(0.48^2)) = 0.844951008
  • d3 = sqrt(2*(0.18^2) + 0.48^2) = 0.538201593
  • q = sqrt(0.18^2 + 2*(0.48^2)) = 0.697350353
Langkah 5: Menghitung koefisien kemiripan antara d1, d2, d3 dengan vektor query menggunakan koefisien kemiripan cosinus.
  • cosSim(d1, Q) = (0.176091 *  0.176091)/(0.304999*0.697350)
  • cosSim(d2, Q) = (0.477121* 0.477121+ 0.477121* 0.477121)/(0.84495*0.69735)
  • cosSim(d3, Q) = (0.176091* 0.176091)/(0.5382*0.69735)

Dengan perhitungan tersebut, maka kita mendapati bahwa urutan bobot kemiripan dokumen dengan query adalah d2, d1, dan d3.