JULIO ADISANTOSO - ILKOM IPB 1

1/12/2011

KOM341 Temu Kembali Informasi

Proses Temu-Kembali

KULIAH #4 • Pemodelan IR • Boolean model • Vector space model

JULIO ADISANTOSO - ILKOM IPB

Konsep IR

Pemodelan IR  Model IR didefinisikan sebagai empat komponen [D, F, Q, R(q, dj)]  Keterangan:    


D adalah kumpulan dokumen Q adalah query F menunjukkan pemodelan dokumen dan query R(q, dj) adalah fungsi peringkat yang dikaitkan dengan suatu nilai R, dimana qQ dan djD


Set Theoretic

Model IR U s e r

Retrieval: Adhoc Filtering

Fuzzy Extended Boolean Classic Models boolean vector probabilistic

Structured Models

T a s k

Non-Overlapping Lists Proximal Nodes

Algebraic Generalized Vector Lat. Semantic Index Neural Networks Probabilistic Inference Network Belief Network

Browsing Browsing Flat Structure Guided Hypertext JULIO ADISANTOSO - ILKOM IPB


Boolean Model  Exact match, pencocokan secara tepat sama.  Query berbentuk ekspresi boolean.  Dokumen bisa cocok atau tidak cocok dengan query yang diberikan. diberikan  Hasilnya berupa sekumpulan dokumen yang cocok.  Tidak ada peringkat dokumen sesuai dengan query yang diberikan.


1

1/12/2011

Boolean Model

Contoh

 Bobot wt,d  {0,1}

d1 d2 d3 d4

 Query q terdiri dari kata, frase, atau konsep yang dihubungkan dengan operator Boolean AND,, O OR,, atau NOT. O  Contoh: q = [ka  (kb  kc)] = ka && (kb || !kc)

   

Hasil Tokenisasi: 1) affirm 2) angel 3) conqueror 4) hero 5) man 6) pallid


Pembobotan Boolean Contoh query: hero AND (angel OR NOT man) Formulasi query : = [k4  {k2  k k5}] = [(0 1 0 1)  {(1 0 0 0}   (0 0 1 0)}] = (0 1 0 1) Hasil query (tidak ada urutan): d2 dan d4

 Contoh: tiap dokumen memiliki dua zona, yaitu title dan body (atau text).  Untuk setiap w[0,1] dapat dihitung: score(d,q)=w.sT(d,q) + (1-w).sB(d,q) sT(d, q){0,1} : nilai Boolean q dalam Title sB(d, q){0,1} : nilai Boolean q dalam Body



7) play 8) tragedy 9) unveil 10) uprise 11) wan 12) worm


Boolean Model Keuntungan  Implementasi mudah dan sederhana  Query mudah disusun dan dimengerti p AND,, OR,, NOT sesuai dengan g bahasa  Operator alami Kelemahan  Tidak ada peringkat dokumen sesuai dengan query yang diberikan  Exact matching  Repot untuk query yang kompleks


Boolean Scoring : Linear zone combinations

And the angels, all pallid and wan, Uprising, unveiling, affirm That the play is the tragedy, ”Man,” Angel and its hero the Conqueror Worm.


Vector Space Model  Model berbasis token  Memungkinkan partial matching dan pemeringkatan dokumen. Cenderung sebagai best matching.  Prinsip dasar:    

Dokumen sebagai vektor token Terdapat t kumpulan token Query sebagai vektor token Kesamaan vektor dokumen dan query dihitung berdasarkan jarak atau kesamaan antar vektor


2

1/12/2011

Kesamaan Antar Vektor Dok-1

Token-3

Model Geometrik

Dok-2 Query Dok-4

Dok-3 Dok 3

Token-2

Dokumen mana yang paling dekat dengan query? Urutkan setiap dokumen berdasarkan ukuran kesamaan/kedekatannya dengan vektor query JULIO ADISANTOSO - ILKOM IPB


Ukuran kemiripan Cosine


t3

 Ukuran kesamaan Cosine antara dj dan dk d1

sim(d j , d k ) 



  d j  dk

d j  dk

 Panjang vektor t2

t1

Ukuran kemiripan sebagai nilai Cosinus dari sudut  JULIO ADISANTOSO - ILKOM IPB

d  d '.d JULIO ADISANTOSO - ILKOM IPB

Nilai koefisien vektor  Koefisien vektor menunjukkan seberapa penting suatu kata  VSM tidak memberi ketentuan mengenai nilai koefisien vektor (bobot kata)  Beberapa contoh nilai bobot  {0, 1}  tf  tf.idf




3

1/12/2011

Ukuran kemiripan Dot Product


Dot product vektor dj dan q

 Panjang vektor

  sim(d j , q )  d j  q

   

sim(D1, sim(D2, sim(D3, sim(D4,

Q) Q) Q) Q)

= = = =

0.106 0.016 0.000 0.922

|Q| = 0.912 |D1| = 0.615 |D2| = 0.748

 Ukuran kesamaan Cosine    

sim(D1, sim(D2, sim(D3, sim(D4,


Prosedur

|D3| = 1.126 |D4| = 1.385

Q) Q) Q) Q)

= = = =

0.189 0.023 0.000 0.730


Masalah komputasi  Jika ukuran koleksi = N sangat besar (jutaan, milyaran, …), berapa nilai kompleksitas untuk menentukan urutan dokumen dari satu query pada N dokumen pada koleksi?  Sangat S t besar b sehingga hi waktu kt komputasi k t i akan k sangat lama.  Cluster pruning : preprocessing untuk mengelompokkan dokumen dalam koleksi sesuai dengan kedekatan vektor.


Cluster pruning


Visualisasi Cluster pruning

 Prosedur (preprocessing):  Ambil secara acak √N dokumen. Disebut sebagai leaders.  Untuk setiap dokumen yang bukan leader (disebut followers) hitung kedekatannya dengan leader. followers), leader

Query

 Proses query q:  Dapatkan leader L yang dekat dengan q.  Cari K dokumen terdekat q di antara follower dari L

Leader JULIO ADISANTOSO - ILKOM IPB


Follower JULIO ADISANTOSO - ILKOM IPB

4

1/12/2011

Latihan Gunakan tf.idf dan Cosine  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



5

JULIO ADISANTOSO - ILKOM IPB 1

Recommend Documents