KOM341 Temu Kembali Informasi

10/8/14

KOM341 Temu Kembali Informasi

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

Proses Temu-Kembali

JULIO ADISANTOSO - ILKOM IPB


1

10/8/14

Konsep IR


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

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



2

10/8/14

Set Theoretic

Model IR U s e r T a s k

Retrieval: Adhoc Filtering

Classic Models boolean vector probabilistic

Structured Models Non-Overlapping Lists Proximal Nodes

Fuzzy Extended Boolean 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 o  Exact match, pencocokan secara tepat sama. o  Query berbentuk ekspresi boolean. o  Dokumen bisa cocok atau tidak cocok dengan query yang diberikan. o  Hasilnya berupa sekumpulan dokumen yang cocok. o  Tidak ada peringkat dokumen sesuai dengan query yang diberikan.



3

10/8/14

Boolean Model o  Bobot wt,d ∈ {0,1} o  Query q terdiri dari kata, frase, atau konsep yang dihubungkan dengan operator Boolean AND, OR, atau NOT. o  Contoh: q = [ka ∧ (kb ∨ ¬kc)] = ka && (kb || !kc)


Contoh d1 d2 d3 d4

è è è è

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

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

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



4

10/8/14

Pembobotan Boolean Contoh query: hero AND (angel OR NOT man) Formulasi query : = [k4 ∧ {k2 ∨ ¬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


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


5

10/8/14

Boolean Scoring : Linear zone combinations o  Contoh: tiap dokumen memiliki dua zona, yaitu title dan body (atau text). o  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


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

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



6

10/8/14

Model Geometrik


Dok-1

Token-3

Kesamaan Antar Vektor Dok-2 Query Dok-4

Dok-3

Token-2

1 nke To

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


7

10/8/14

Ukuran kemiripan Cosine t3

d1

θ t2

t1

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

Ukuran kemiripan Cosine o  Ukuran kesamaan Cosine antara dj dan dk

sim(d j , d k ) =

! ! d j • dk

d j × dk

o  Panjang vektor

d = d '.d JULIO ADISANTOSO - ILKOM IPB


8

10/8/14

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




9

10/8/14

Ukuran kemiripan Dot Product Dot product vektor dj dan q

! ! sim(d j , q) = d j • q

o  o  o  o 

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

Q) Q) Q) Q)

= = = =

0.106 0.016 0.000 0.922


Ukuran kemiripan Cosine o  Panjang vektor |Q| = 0.912 |D1| = 0.615 |D2| = 0.748

|D3| = 1.126 |D4| = 1.385

o  Ukuran kesamaan Cosine n  n  n  n 

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

Q) Q) Q) Q)

= = = =

0.189 0.023 0.000 0.730



10

10/8/14

Prosedur


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



11

10/8/14

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

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


Visualisasi Cluster pruning

Query

Leader

Follower JULIO ADISANTOSO - ILKOM IPB


12

10/8/14

Latihan Gunakan tf.idf dan Cosine o  Dokumen: n  d1: "Shipment of gold damaged in a fire" n  d2: "Delivery of silver arrived in a silver truck" n  d3: "Shipment of gold arrived in a truck"

o  Query: "gold silver truck “ o  Asumsi : N=1000



13

KOM341 Temu Kembali Informasi

Recommend Documents