10/8/14
KOM341 Temu Kembali Informasi
KULIAH #4 • Pemodelan IR • Boolean model • Vector space model
Proses Temu-Kembali
JULIO ADISANTOSO - ILKOM IPB
JULIO ADISANTOSO - ILKOM IPB
1
10/8/14
Konsep IR
JULIO ADISANTOSO - ILKOM IPB
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
JULIO ADISANTOSO - ILKOM IPB
JULIO ADISANTOSO - ILKOM IPB
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.
JULIO ADISANTOSO - ILKOM IPB
JULIO ADISANTOSO - ILKOM IPB
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)
JULIO ADISANTOSO - ILKOM IPB
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
JULIO ADISANTOSO - ILKOM IPB
JULIO ADISANTOSO - ILKOM IPB
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
JULIO ADISANTOSO - ILKOM IPB
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
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
JULIO ADISANTOSO - ILKOM IPB
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
JULIO ADISANTOSO - ILKOM IPB
JULIO ADISANTOSO - ILKOM IPB
6
10/8/14
Model Geometrik
JULIO ADISANTOSO - ILKOM IPB
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
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
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
JULIO ADISANTOSO - ILKOM IPB
JULIO ADISANTOSO - ILKOM IPB
JULIO ADISANTOSO - ILKOM IPB
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
JULIO ADISANTOSO - ILKOM IPB
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
JULIO ADISANTOSO - ILKOM IPB
JULIO ADISANTOSO - ILKOM IPB
10
10/8/14
Prosedur
JULIO ADISANTOSO - ILKOM IPB
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.
JULIO ADISANTOSO - ILKOM IPB
JULIO ADISANTOSO - ILKOM IPB
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
JULIO ADISANTOSO - ILKOM IPB
Visualisasi Cluster pruning
Query
Leader
Follower JULIO ADISANTOSO - ILKOM IPB
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
JULIO ADISANTOSO - ILKOM IPB
JULIO ADISANTOSO - ILKOM IPB
13