TEMU KEMBALI INFORMASI

Model IR Vector Space

TEMU KEMBALI INFORMASI JULIO ADISANTOSO Departemen Ilmu Komputer IPB

Pertemuan 3 MODEL IR

JULIO ADISANTOSO Departemen Ilmu Komputer IPB

TEMU KEMBALI INFORMASI


Konsep Boolean Model

Konsep IR





Pemodelan IR Model IR didefinisikan sebagai empat komponen, yaitu: D, F, Q, R(q, dj ) Keterangan: dengan D adalah kumpulan dokumen, Q adalah query, F menunjukkan pemodelan dokumen dan query, dan R(q, dj ) adalah fungsi peringkat yang dikaitkan dengan suatu fungsi R, dimana q ∈ Q dan dj ∈ D.





Model IR





Remember: Matrik Term-Document Matrik untuk mengabstraksikan inverted index:    t1 w11 w12 w13 . . . w1N  t2   w21 w22 w23 . . . w2N      ..   .. .. .. ..  . .  .  . . . . .  tT

wT1 wT2 wT3 . . .

wTN

dengan wij adalah bobot term ke-i pada dokumen ke-j untuk i = 1, 2, . . . , T (term) dan j = 1, 2, . . . , N (dokumen).





Standard Boolean Model Exact match, pencocokan secara tepat sama. Query berbentuk ekspresi boolean. Dokumen bisa cocok atau tidak cocok dengan query yang diberikan. Hasilnya berupa sekumpulan dokumen yang cocok. Tidak ada peringkat dokumen sesuai dengan query yang diberikan. —————– Bobot wtd ∈ {0, 1} Query q terdiri dari kata, frase, atau konsep yang dihubungkan dengan operator Boolean AND, OR, atau NOT. Contoh: q = [ta ∧ (tb ∨ ¬tc )] = ta AND (tb OR !tc ) JULIO ADISANTOSO Departemen Ilmu Komputer IPB




Contoh: Korpus: d1 → And the angels, all pallid and wan, d2 → Uprising, unveiling, affirm d3 → That the play is the tragedy, ”Man” d4 → Angel and its hero the Conqueror Worm. Hasil tokenisasi: affirm angel conqueror hero

man pallid play tragedy


unveil uprise wan worm




Pembobotan Boolean Contoh query: hero AND (angel OR NOT man)

Formulasi query: = [t4 ∧ {t2 ∨ ¬t5 }] = [(0101) ∧ {(1000) ∨ ¬(0010)}] = (0101) Hasil query (tidak ada urutan): d2 dan d4




Vector Space Model Pembobotan

Vector Space Model (VSM) Prinsip dasar: Dokumen sebagai vektor token Terdapat T kumpulan token Query sebagai dokumen kecil (sebagai juga vektor token) Kesamaan vektor dokumen dan query dihitung berdasarkan jarak atau kesamaan antar vektor

Jadi, VSM adalah model berbasis token, yang memungkinkan partial matching dan pemeringkatan dokumen. Cenderung sebagai best matching.





Metode Pembobotan Pertanyaannya, apa yang digunakan sebagai nilai elemen vektor dokumen d~j = (w1j , w2j , . . . , wTj )? VSM tidak memberikan ketentuan mengenai nilai yang digunakan sebagai elemen vektor (wij ). Nilai elemen vektor term ke-i pada dokumen ke-j (wij ) menunjukkan ukuran kepentingan term ke-i pada dokumen ke-j. Sering disebut sebagai metode pembobotan dalam IR.





Metode Pembobotan Metode pembobotan melibatkan 3 komponen: 1

2

3

Lokal, menunjukkan bobot suatu term pada suatu dokumen. Tidak memperhatikan dokumen lainnya. Misalnya: TF. Global, menunjukkan bobot suatu term di seluruh dokumen dalam korpus. Misalnya: IDF. Normalisasi, menunjukkan apakah panjang vektor dinormalisasi atau tidak

Bobot term ke-i pada dokumen ke-j (wij ) merupakan hasil kali ketiga komponen tersebut. Metode pembobotan yang melibatkan 3 komponen tersebut telah dibakukan dalam bentuk SMART Notation (Manning et.al 2009)





SMART Notation (Manning et.el 2009)

Sebagai contoh, pembobotan TF.IDF dinotasikan sebagai pembobotan ”ntn”. Pembobotan TF dinotasikan sebagai pembobotan ”nnn”.





Jarak 2 Vektor

Jarak 2 vektor d~1 dan d~2 didefinisikan sebagai (Jarak Euclidean): r 0 p ~ ~ ~ ~ ~ ~ J(d1 , d2 ) = d1 − d2 d1 − d2 = (x1 − x2 )2 + (y1 − y2 )2





Ukuran Jarak Semakin besar nilai jarak 2 vektor dokumen, maka 2 dokumen tersebut dikatakan semakin tidak mirip. Sebaliknya, 2 dokumen dikatakan mirip jika memiliki jarak yang kecil. Dokumen dengan ukuran besar cenderung memiliki vektor yang panjang, sebaliknya dokumen dengan ukuran kecil cenderung memiliki vektor yang pendek. Kosekuensinya, walaupun dua vektor tersebut berdekatan, akan memiliki jarak yang cukup besar → missleading. Ukuran jarak tidak cocok digunakan untuk dokumen yang memiliki ukuran beragam → perlu normalisasi (jadikan sebagai vektor satuan), atau menggunakan ukuran kemiripan.





Ukuran Kemiripan Cosine Ukuran kemiripan sebagai nilai Cosinus dari sudut θ. Perhatikan gambar samping: cos(θ) = cos(θ2 − θ1 ) = cos(θ1 )cos(θ2 ) + sin(θ1 )sin(θ2 ) 1 x2 +y1 y2 = kdx11 k kdx22 k + kdy11 k kdy22 k = xkd 1 kkd2 k =

0 d~1 d~2 kd1 kkd2 k

→ cosine similarity

dengan p k d k adalah panjang vektor = ~d0~d JULIO ADISANTOSO Departemen Ilmu Komputer IPB




Prosedur IR secara Umum





Contoh SE dengan TF.IDF





Contoh SE dengan TF.IDF Query diperlakukan sebagai sebuah dokumen kecil. Panjang vektor: k Q k= 0.912, k D1 k= 0.615, k D2 k= 0.748, k D3 k= 1.126, k D4 k= 1.385 Ukuran kesamaan Cosine sim(D1 , Q) = 0.189 sim(D2 , Q) = 0.023 sim(D3 , Q) = 0.000 sim(D4 , Q) = 0.730

Urutan hasil: D4 D1 D2 D3 JULIO ADISANTOSO Departemen Ilmu Komputer IPB




Latihan Kelas 1 Diketahui dokumen: d1 : Shipment of gold damaged in a fire d2 : Delivery of silver arrived in a silver truck d3 : Shipment of gold arrived in a truck

Query: gold silver truck Asumsi: N=1000

Bagaimana urutan hasil jika menggunakan pembobotan TF.IDF dengan ukuran kesamaan cosine?





Latihan Kelas 2 Diketahui corpus XML yang digunakan pada latihan kelas pertemuan sebelumnya. Dengan menggunakan R, lakukan hal-hal berikut: Buat matrik Term Document untuk semua term yang ada seperti sebelumnya, dan hitung nilai IDF setiap term. Buat matrik Term Document hanya untuk term yang memiliki nilai IDF ¿1.0 dan panjang kata [3,15], serta bobot elemen matrik menggunakan TF.IDF (ntn).



TEMU KEMBALI INFORMASI

Recommend Documents