Boolean Retrieval & Vectore Space Model

Boolean Retrieval Dan Kemiripan Dokumen: Vector Space Model Wayan Sriyasa Departemen Ilmu Komputer, FMIPA, IPB

Boolean Retrieval dan Kesamaan Dokumen: Vector Space Model Pendahuluan Sistem temu kembali informasi dengan menggunakan model Boolean Retrieval merupakan salah satu model dimana proses pencarian informasi dari query yang diterima diperlakukan dengan ekspresi boolean. Ekspresi boolean yang dimaksud dapat berupa operator logika AND, OR dan NOT. Untuk dapat melakukan proses Booelan Retrieval, keberadaan inverted index sangat diperlukan, karena index ini akan sangat membantu dalam proses temu kembali yang efektif. Beberapa langkah yang dapat dilakukan dalam proses Booelan Retrieval ini antara lain: 1. Lakukan indexing, dalam hal ini inverted index 2. Temukan kata/term query didalam dictionary dan posting list-nya 3. Lakukan operasi dari operator logika yang diinginkan dengan mencari irisan dari posting list, (pada tulisan ini hanya dicoba untuk operator logika AND). Setelah pencarian dokumen sesuai dengan input query selesai, selanjutnya perlu dilakukan perangkingan dokumen tersebut berdasarkan pencirian oleh kata/term query oleh bobot kata/term tersebut didalam dokumen. Perangkingan ini dapat dilakukan dengan menggunakan skor tf*idft (sudah dibahas pada tugas sebelumnya), serta dengan konsep jarak kemiripan dokumen dengan menggunakan pendekatan vector space model. Didalam Vector Space Model, dokumen direpresentasikan sebagai sebuah vektor, dimana setiap elemen vektor tersebut merupakan nilai dari bobot tf*idft yang sudah dinormalisasi. Pada model ini, setiap bobot kata/term ditiap dokumen dibandingkan dan dihitung sudut kedekatannya (dalam derajat (0). Pembandingan ini dengan menggunakan sebuah operasi perkalian matrix yang disebut sebagai inner product atau dot product yang dapat dinotasikan sebagai: xT = (x1, x2, x3, x4); yT = (y1, y2, y3, y4)  x●y = xTy

........................(1)

Sebelum dapat dihitung sudut dari vektor ini, terlebih dahulu harus dihitung panjang dari vektor tersebut. Panjang vektor dinotasikan debagai |x|dan kuadrat dari panjang vektor |x|2 merupakan dot product-nya sendiri. |x|2 = xTy

........................(2)

sehingga panjang vektor |x| menjadi:

|x| x T y

........................(3)

Sudut simpangan (θ) antara dua vektor ini (dengan dimensi yang sama) dapat kita tentukan dengan menghitung nilai cosinus θ sbb: xT y cos  ........................(4) |x||y| Dan untuk menghitung derajat (θ) dapat dilakukan dengan menghitung arccos dari persamaan (4). Dengan mengetahui sudut simpangan vektor, maka dapat diketahui kemiripan antar dokumen didalam korpus. Sebagai elemen vektor dapat digunakan nilai bobot tf*idft. Dengan sangat bervariasinya kemunculan kata/term pada korpus sehingga perlu dilakukan normalisasi bobot, sebagai berikut: tf * idfd,t Wnorm  ........................(5) (tf * idf)2



1

Boolean Retrieval Dan Kemiripan Dokumen: Vector Space Model Wayan Sriyasa Departemen Ilmu Komputer, FMIPA, IPB

Implementasi Script yang digunakan pada tugas ini merupakan lanjutan dari script tugas sebelumnya. Cuplikan script berikut merupakan langkah yang dilakukan untuk melakukan proses boolean retrieval dan perhitungan matriks Vector Space. Langkah 1: Normalisasi bobot ################################################################ ## Step 4: Normalisasi bobot ## ## unit[i]{term}=bobot[i]{term]/sqrt(sum(bobot[i]{term})^2) ## ################################################################ for $i (0..$#tf) { $len2 = 0; foreach $x (sort keys %dictio) { $len2 += $bobot[$i]{$x}**2; } $len = sqrt($len2); foreach $x (sort keys %dictio) { $unit[$i]{$x} = $bobot[$i]{$x}/$len; #print OUT4 "dokumen ke-$i, $x, $bobot[$i]{$x}, $unit[$i]{$x}\n"; } }

Langkah 2. Perhitungan vektor space (sudut simpangan antar dokumen) ################################################# ## Step 5: Hitung sudut (cos) vektor ## ## Cos[i][j]=unit[i]{term}*unit[j]{term} ## ## cosinus[i][j]=acos(cos[i][j]) ## ################################################# for $i (0..$#tf) { for $j (0..$#tf) { $Jum=0; foreach $x (sort keys %dictio) { $Jum += $unit[$i]{$x} * $unit[$j]{$x}; } $cos[$i][$j] = $Jum; } } print "\n"; for $i (0..$#tf) { for $j (0..$#tf) { $cosin[$i][$j] = acos($cos[$i][$j])/pi*180; printf "%.1f ",$cosin[$i][$j]; } print "\n"; }

Langkah 3. Pencarian dengan Boolean Pencarian kata pada indeks dilakukan menurut tahap berikut:  Setiap kata yang dicari dilakukan pencarian pada hash rec{kata}, hasil dari pencarian ini adalah hash dok{frekuensi} dari tiap-tiap kata.  Operasi AND dilakukan dengan membuat hash and{kata} dan mengisi hash tersebut sesuai nomor dokumen yang ditemukan (kompleksitas θ(n)). Dokumen hasil adalah item pada hash yang memiliki jumlah sebanding dengan banyaknya kata yang dicari.

2

Boolean Retrieval Dan Kemiripan Dokumen: Vector Space Model Wayan Sriyasa Departemen Ilmu Komputer, FMIPA, IPB

Struktur hashtable yang digunakan untuk menyimpan index adalah sebagai berikut: Field N_dok kata pos_dok

Keterangan Jumlah dokumen didalalm korpus Hash yang menyimpan frekuensi kata pada tiap dokumen Array yang menyimpan posisi dokumen didalam korpus

berikut cuplikan script yang melakukan pencarian kata/term didalam korpus: ######################################################## ## Cari tiap-tiap kata dalam hash yang sudah disimpan ## ######################################################## foreach my $str (@ARGV) { # ambil kata yang dicari dari hash "kata" last if (!$rec->{'kata'}{lc $str}); my %hash = %{ $rec->{'kata'}{lc $str} }; my @key = keys %hash; # hitung idf per kata untuk bobot dokumen # log2(N_dok / n dok), N_dok = jumlah dokumen, n = frekuensi kata yang dicari dalam dokumen my $idf = log($rec->{'N_dok'} / scalar @key) / log(2); # hitung bobot hasil tf x idf , tf = total frekuensi kata foreach $x (@key) { $and{$x}++; $bobot{$x} += $hash{$x} * $idf; } }

Hasil pencarian berupa array hasil (berisi nomor dokumen) lalu diurutkan menurut bobot. #################################################################### ## Periksa banyak dokumen yang mengandung kata-ktata yang dicari ## #################################################################### my @hasil = (); foreach $x (keys %and) { push @hasil, $x if $and{$x} == scalar @ARGV ; } # stop pencarian kalo kata tidak ditemukan die("Tidak ada dokumen yang cocok...\n") if !@hasil; # urutkan temuan dokumen sesuai dengan bobotnya my @urut = sort { $bobot{$b} <=> $bobot{$a} } @hasil;

Teks dokumen selanjutnya dibaca dari file korpus dan diambil bagian yang cukup mewakili yaitu DOCNO dan TITLE. ################################################## ## baca ulang korpus dan ambil id dokumen ## ## serta judulnya; record separator = -- ## ################################################## open(IN, "korpus.txt") or die("File korpus.txt tidak ditemukan..."); $/ = "\n"; my $nomor = 0; my $str; print "\n";

3

Boolean Retrieval Dan Kemiripan Dokumen: Vector Space Model Wayan Sriyasa Departemen Ilmu Komputer, FMIPA, IPB

Sebagai hasil akhir ditampilkan nomor, id dokumen, judul dan bobot-nya. ################################################################## ## Ambil idDokumen dan Judul dokumen yang sesuai dengan query ## ################################################################## foreach $x (@urut) { # ambil text dari awal dokumen -seek(IN, $rec->{'pos_dok'}[$x-1], 0); next if (!($str = )); # cetak nomor urut temuan printf "Dokumen ke-%2d: \n", ++$nomor; print "################\n"; #cetak id dokumen print "Id Dokumen: "; print "$2 " while ($str =~ m/<(DOCNO)>(.+)<\/\1>/gs); print "\n"; #cetak judul dokumen print "Judul dokumen: "; print $2 while ($str =~ m/<(TITLE)>(.+)<\/\1>/gs); #cetak bobot kata pada dokumen yang dimaksud print "\n"; printf "bobot kata yang dicari adalah %2.3f\n", $bobot{$x}; print "\n"; # cetak list hanya 5 dokumen saja last if $nomor >= 5; }

Hasil dan Pembahasan Berikut hasil run dari script yang telah dibuat: Script1. Proses indexing dan perhitungan vektor

Gambar 1. Hasil run script index.pl 4

Boolean Retrieval Dan Kemiripan Dokumen: Vector Space Model Wayan Sriyasa Departemen Ilmu Komputer, FMIPA, IPB

Scrip 2. Proses pencarian dokumen dengan query interaktif dari user. Scenario1. Proses sukses, kata/term yang dicari ada pada korpus.

Gambar 2. Hasil run script cari.pl, dengan query "flu burung"

Scenario2. Proses sukses, kata/term yang dicari tidak ada pada korpus.

Gambar 3. Hasil run script cari.pl dengan query "google yahoo"

Implementasi perhitungan sudut simpangan vektor antar dokumen berhasil dilakukan, berikut contoh vektor sudut yang dihasilkan dengan menggunakan 4 dokumen didalam 1 korpus: Dari hasil perhitungan ini (Gambar 4), diperoleh sebuah matrix berukuran 4x4 yang menunjukkan sudut kemiringan antar dokumen. Matrix ini adalah simetris dimana diagonalnya bernilai 0 (nol) yang memperlihatkan kemiringan terhadap dokumen itu sendiri. Besaran sudut berbanding terbalik terhadap kemiripan sebuah dokumen terhadap dokumen lainnya. Pada contoh ini, dokumen ke-2 vs ke-3 memiliki sudut terkecil 850, ini berarti kemiripan dokumen ini lebih besar daripada dokumen Gambar 4. Perhitungan vektor dari 4 yang lainnya. dokumen

5

Boolean Retrieval Dan Kemiripan Dokumen: Vector Space Model Wayan Sriyasa Departemen Ilmu Komputer, FMIPA, IPB

Manfaat lebih lanjut dari matrix sudut ini adalah pada aplikasi untuk peng-klasifikasian dokumen, penelusuran link web, dll. Proses pencarian dokumen dengan query yang diberikan telah berhasil dilakukan, dimana dokumen yang ditemukan akan diurutkan berdasarkan bobotnya (gambar 2). Query diproses dengan menggunakan operator logika AND. Dokumen yang dapat ditampilkan oleh script di-set hanya 5 (bisa di-set lebih dari ini) dimana dokumen dengan rangking teratas memiliki bobot terbesar dibandingkan dengan bobot keempat dokumen lainnya.

Kesimpulan Sistem temu kembali informasi dengan menggunakan model Boolean Retrieval merupakan salah satu model dimana proses pencarian informasi dari query yang diterima diperlakukan dengan ekspresi boolean. Untuk dapat melakukan proses Booelan Retrieval, keberadaan inverted index sangat diperlukan. Didalam Vector Space Model, dokumen direpresentasikan sebagai sebuah vektor, dimana setiap elemen vektor tersebut merupakan nilai dari bobot tf*idft yang sudah dinormalisasi. Setiap bobot kata/term ditiap dokumen dibandingkan dan dihitung sudut kedekatannya (dalam derajat (0) dengan sebuah operasi perkalian matrix yang disebut sebagai inner product atau dot product. Pada implementasinya, index direkonstruksi dengan menggunakan hashtable, dan logika pencarian hanya mendukung AND. Untuk setiap dokumen yang mengandung kata yang sama, dibedakan berdasarkan bobotnya. Referensi ----------------. http://nlp.stanford.edu/IR-book/html/htmledition/irbook.html ----------------. http://en.wikipedia.org/wiki/Natural_language_processing Adisantoso, J; dan Ridha, A. 2009. Materi Kuliah: Sistem Temu Kembali Informasi. Istitut Pertanian Bogor. Indonesia. Feldman, R; Sanger, J. 2007. THE TEXT MINING HANDBOOK: Advanced Approaches in Analyzing Unstructured Data. Cambridge University Press. USA. Manning, C.D; Raghavan, P Dan Schutze, H. 2008. Introduction To Information Retrieval. Cambridge University Press. USA. Rijsbergen, C.J. 2008. Information Retrieval. Department Of Computing Science, University Of Glasgow. USA.

6