Sistem Temu-Kembali Informasi Perhitungan Kemiripan (Pembobotan Term dan Penskoran dalam Model Ruang Vektor, Penskoran dalam Sistem Pencarian Lengkap)
Husni Program Studi Teknik Informatika Universitas Trunojoyo Madura
Semeter Gasal 2015: Okt. - Nop. 2015
Outline • • • • • • • • •
Temu-kembali Teranking Penskoran dokumen Frekuensi term (dalam dokumen) Statistika koleksi (frekuensi dokumen) tf-idf Skema pembobotan Penskoran ruang vektor Percepatan ranking ruang vektor Sistem pencarian lengkap
Boolean Retrieval: Review • Sejauh ini, query pada pemrosesan boolean: – dokumen cocok atau tidak dengan query • Bagus bagi pengguna ahli (pakar) yang paham presisi dari kebutuhannya dan koleksi • Bagus juga buat aplikasi: dapat dengan mudah memperoleh dan menyajikan ribuan hasil • Tidak baik bagi mayoritas pengguna – Kebanyakan pengguna tak-mampu menuliskan query boolean (atau mampu tetapi dianggap merepotkan) – Kebanyakan pengguna tidak mau menjelajah ribuan hasil pemrosesan Query • Hal ini terutama berlaku pada pencarian web.
Masalah dengan Pencarian Boolean: pesta atau lapar • Query boolean sering mengakibatkan terlalu sedikit (=0) atau terlalu banyak (ribuan) hasil • Query 1: “standard user dlink 650” → 200,000 hits • Query 2: “standard user dlink 650 no card found”: 0 hits • Perlu menjadi ahli untuk membuat query yang menghasilkan jumlah hit tepat dan sangat berguna • AND memberikan terlalu sedikit; OR memberikan terlalu banyak.
Model Retrieval Berperingkat • Tidak fokus pada dokumen yang memenuhi ekspresi query, • Sistem mengembalikan dokumen-dokumen berperingkat teratas (top k) dalam koleksi yang berkaitan dengan query • Query teks bebas: Bukan bahasa query operator dan ekspresi, query pengguna dapat hanya satu atau dua kata dalam bahasa manusia • Prinsipnya, ada dua hal di sini: Bahasa query dan model retrieval – Praktisnya, model retrieval teranking telah diasosiasikan dengan query teks bebas.
Anda setuju?
Pesta atau Lapar: Tidak terjadi di Retrieval Berperingkat • Ketika sistem menyajikan himpunan hasil berperingkat, besarnya himpunan tersebut tidak jadi persoalan – Pegguna tidak perlu menjelajah semua hasil, mulai dari yang tertinggi rankingnya – Hanya menunjukkan top k ( ≈ 10) hasil – Tidak membanjiri pengguna – Alasan: algoritma ranking bekerja dengan baik 6
Penskoran: Basis Retrieval Berperingkat • Ingin mengembalikan urutan dokumen yang mungkin paling berguna bagi pencari • Bagaimana menentukan urutan ranking dokumen-dokumen dalam koleksi yang berkaitan dengan query? • Tentukan suatu skor misalya dalam [0, 1] untuk setiap dokumen • Skor ini mengukur seberapa "cocok" dokumen dengan query (similarity). 7
Skor Pencocokan Query-Dokumen • Perlu cara penentuan skor terhadap suatu pasangan query-dokumen • Dapat mulai dengan query satu-term • Jika term query tidak hadir dalam dokumen: – Skor bernilai 0 – Mengapa? Dapat lebih baik? • Semakin sering term query hadir di dalam dokumen, semakin tinggi skornya (harusnya...) • Akan dilihat sejumlah alternatif... 8
1: Koefisien Jaccard • Ukuran kesamaan dua himpunan A dan B sering digunakan • jaccard(A,B) = |A ∩ B| / |A ∪ B| • jaccard(A,A) = 1 • jaccard(A,B) = 0 jika A ∩ B = 0 • A dan B tidak harus berukuran sama • Selalu menetapkan nilai antara 0 dan 1 • Terlihat bahwa dalam konsteks k-gram terjadi overlap antara dua kata. 9
Koefisien Jaccard: Contoh Penskoran • Berapa skor kecocokan query-dokumen yang dihitung dengan koefisien Jaccard untuk dua dokumen berikut? • Query: ides of march • Dokumen 1: caesar died in march • Dokumen 2: the long march • jaccard(Q,D) = |Q ∩ D| / |Q ∪ D| • jaccard(Query, Dokumen1) = 1/6 • jaccard(Query, Dokumen2) = 1/5 10
Persoalan Penskoran di Jaccard • Skor kecocokan menurun seiring bertambahnya panjang dokumen • Perlu normalisasi yang lebih canggih terhadap panjang dokumen • Gunakan normalisasi panjang menggantikan |A ∩ B|/|A ∪ B| (Jaccard)
– 1) Tidak mempertimbangkan term frequency (berapa kali term muncul di dalam dokumen) • Pada J.C. dokumen merupakan himpunan kata, bukan tas kata (bag of words) – 2) Term yang jarang hadir di dalam koleksi harusnya lebih informatif daripada term yang sering - Jaccard tidak melibatkan informasi ini. 11
Matriks kejadian Term-Dokumen Biner: Review • Setiap dokumen direpresentasikan oleh suatu vektor biner∈ {0,1}|V|.
12
Matriks Hitungan Term-Dokumen • Pertimbangkan jumlah kemunculan term di dalam dokumen: – Setiap dokumen adalah vektor hitungan dalam ℕv: [perhatikan kolom di bawah!]
13
Model Bag of words • Representasi vektor tidak melihat urutan (posisi) dari kata di dalam dokumen • “John is quicker than Mary” dan ”Mary is quicker than John” mempunyai vektor yang sama • Ini dinamakan model bag of words (tas kata) • Terlihat sebagai langkah mundur, padahal indeks posisional telah mampu membedakan dua dokumen ini 14
Term Frequency tf • Term frequency tft,d dari term t dalam dokumen d didefinisikan sebagai jumlah (berapa kali) t hadir dalam d • tf digunakan saat perhitungan skor kecocokan querydokumen - caranya? • Frekuensi term mentah bukanlah apa yang diinginkan: – Dokumen dengan 10 kemunculan term adalah lebih relevan daripada dokumen dengan 1 kemunculan term tersebut – Tetapi bukan 10 kali lebih relevan • Relevansi tidak naik proporsional dengan term frequency. Frekuensi dalam IR = Hitungan
15
Proyek Fechner • Gustav Fechner (1801 - 1887) terobsesi dengan relasi mind dan matter • Variasi dari kuantitas fisik (misal energi cahaya) menyebabkan variasi dalam intensitas atau kualitas dari pengalaman subyektif • Fechner mengusulkan fungsi logaritmik untuk hal berdimensi banyak – Peningkatan intensitas stimulus dengan suatu faktor tertentu (katakanlah 10 kali) selalu menghasilkan kenaikan yang sama pada skala psikologis • Jika peningkatan frekuensi term dari 10 ke100 menaikkan relevansi sebesar 1 maka peningkatan frekuensi dari 100 ke 1000 juga menaikkan relevansi sebesar 1. 16
Pembobotan Frekuensi Log • Bobot frekuensi log dari term t dalam d adalah
• 0 → 0, 1 → 1, 2 → 1.3, 10 → 2, 1000 → 4, dll. • Skor untuk pasangan dokumen-query: sum (jumlah total) terms t beririsan (ada dalam q dan d)
• Skor bernilai 0 jika term query tidak hadir dalam dokumen • Jika q' ⊆ q maka skor (d,q’) <= skor (d,q) masalah? 17
Pen-skala-an tf Normal vs. Sublinear
• Rumus di atas mendefinisikan penskalaan tf sublinier • Pendekatan paling simpel (normal) adalah menggunakan jumlah kemunculan term dalam dokumen (frekuensi) • Tetapi... sublinier tf harusnya lebih baik. 18
Properti dari Logaritma • • • • • • • • •
y = loga x iff x = ay loga 1 = 0 loga a = 1 loga (xy) = loga x + loga y loga (x/y) = loga x - loga y loga (xb) = b loga x logb x = loga x / loga b log x pada dasarnya log10 x ln x pada dasarnya loge x (e = 2.7182… Napier atau bilangan Euler) logaritma natural. 19
Document Frequency -df • Term yang jarang dalam koleksi keseluruhan - lebih informatif daripada term yang sering muncul – ingat kembali stop words • Perhatikan term dalam query yang jarang hadir dalam koleksi (misal: arachnocentric) • Dokumen yang mengandung term ini kemungkinan besar sangat relevan dengan query (kebutuhan informasi) arachnocentric • → Diperlukan bobot tinggi untuk term yang jarang muncul seperti arachnocentric. 20
Document Frequency: df • Secara umum term yang sering muncul menjadi kurang informatif daripada yang jarang • Perhatikan suatu term query yang sering dalam koleksi (seperti: high, increase, line) • Dokumen yang mengandung term tersebut kemungkinan besar lebih relevan daripada yang tidak • Tetapi bagaimana dengan query yang mengandung dua term, misal: high arachnocentric • Bagi term yang sering hadir dalam dokumen, misalnya high, harus dibobot positif tetapi lebih rendah daripada terhadap term yang jarang dalam koleksi, seperti arachnocentric • Akan digunakan document frequency (df) untuk menangkap ini. • http://www.wordfrequency.info
21
Bobot idf • dft adalah frekuensi dokumen dari t atau jumlah dokumen yang mengandung t
– dft adalah ukuran inversi dari ke-informatif-an t (lebih kecil lebih baik) – dft ≤ N
• idf (inverse document frequency) dari t didefinisikan sebagai
Fungsi dari t saja, tidak bergantung pada dokumen
– Digunakan log (N/dft), bukan N/dft untuk “mengurangi” pengaruh dari idf. 22
Contoh idf: N = 1 juta Term calpurnia
dft
idft 1
6
animal
100
4
sunday
1000
3
10000
2
100000
1
1000000
0
fly under the
• idft = log ( N/dft ) • Ada satu nilai idf untuk setiap term t dalam koleksi 23
Frekuensi Koleksi vs. Dokumen • Frekuensi koleksi dari t adalah jumlah kemunculan t di dalam koleksi, termasuk jumlah kemunculan dalam dokumen yang sama • Contoh: Kata
Frekuensi Koleksi
Frekuensi Dokumen
insurance
10440
3997
try
10422
8760
• Kata mana yang merupakan term pencarian yang lebih baik (dan harus mendapatkan bobot lebih tinggi dalam query seperti "try insurance")? 24
Pembobotan tf-idf • Bobot tf-idf dari suatu term adalah perkalian dari bobot tf-nya dan bobot idf-nya: • Skema pembobotan yang paling terkenal dalam information retrieval: – Tanda “-” dalam tf-idf adalah strip, bukan pengurangan! – Alternatif penulisan: tf.idf, tf x idf • Bertambah mengikuti jumlah kemunculan term dalam dokumen • Bertambah mengikuti kejarangan term di dalam koleksi.
25
Ranking Akhir dari Dokumen untuk Query
• Masih ada pilihan lainnya ...
26
Pengaruh idf pada Ranking • Berpengaruhkah idf pada ranking hasil query satu term? misal Q: – iPhone
• idf tidak mempengaruhi perankingan query satu term - karena ada satu nilai idf untuk setiap term dalam koleksi.
– idf mempengaruhi ranking dokumen untuk query minimal dua term. – Untuk query capricious person, pembobotan idf menyebabkan hitungan capricious lebih besar dalam perankingan dokumen akhir daripada hitungan person. 27
Biner → Hitungan → Matriks Bobot
• Setiap dokumen direpresentasikan oleh vektor bobot tf-idf bernilai ril ∈ R|V| 28
Dokumen sebagai Vektor • Diperoleh ruang vektor berdimensi |V| – Terms adalah sumbu dari ruang – Dokumen adalah titik atau vektor di dalam ruang tersebut
• Dimensi terlalu tinggi: – 400,000 dalam RCV1 – puluhan juta dimensi ketika kita menerapkan ini pada web search engine
• Dinamakan vektor sangat jarang- sebagian besar entri bernilai nol. 29
Query sebagai Vektor • Ide kunci 1: lakukan yang sama terhadap query: tampilkan sebagai vektor dalam ruang tersebut • Ide kunci 2: Ranking dokumen sesuai dengan kedekatannya terhadap query dalam ruang ini – Kedekatan = kemiripan vektor-vektor – Kedekatan≈ inversi dari jarak
• Review: Ini dilakukan karena ingin mendapatkan yang lebih baik daripada model boolean • Gantinya: berikan peringkat lebih tinggi untuk dokumen yang lebih relevan. 30
Memformalkan Kedekatan pada Ruang Vektor • Pertama: Jarak antara dua titik – ( = jarak antara titik ujung dari dua vektor)
• Jarak euclidean? • Jarak euclidean merupakan ide yang tidak baik. . . • . . . karena jarak euclidean akan BESAR bagi vektor-vektor dengan panjang berbeda. 31
Mengapa Jarak Ide yang Buruk • Jarak euclidean antara q dan d2 adalah besar meskipun sebaran term dalam query q dan sebaran term dalam dokumen d2 sangat mirip.
32
Menggunakan Sudut (bukan Jarak) • Eksperimen sederhana – Ambil dokumen d dan tambahkan ke dirinya sendiri – Namakan dokumen ini d′ – “Secara semantik” d dan d′ mempunyai isi yang sama – Tetapi jarak euclidean antara dua dokumen dapat sangat besar • Jika representasi tft,d digunakan maka sudut antara dua dokumen adalah 0, sesuai dengan kemiripan maksimal • Ide kunci: Dokumen diranking mengikuti besarnya sudut dengan query. 33
Dari sudut ke Cosinus • Dua gagasan berikut sama: – Dokumen diranking urut naik mengikuti besarnya sudut antara query dan dokumen – Dokumen diranking urut turun mengikuti nilai cosinus (query, dokumen)
• Cosinus adalah fungsi yang secara monoton menurun pada interval [0o, 180o] 34
Dari sudut ke Cosinus
• Tetapi bagaimanan dan mengapa haruskah menghitung cosinus? 35
Normalisasi Panjang • Vektor dapat dinormalisasi panjangya dengan membagi setiap komponennya dengan panjangnya - digunakan norm L2:
• Pembagian vektor dengan norm L2 -nya menjadikannya suatu vektor satuan (panjang) • Pengaruh pada dua dokumen d dan d′ (d ditambahkan ke dirinya): keduanya punya vektor identik setelah normalisasi panjang – Akibat: dokumen panjang dan pendek mempunyai bobot yang dapat dibandingkan (comparable). 36
Cosinus(query, dokumen) Vektor satuan
qi : bobot tf-idf dari term i dalam query di : bobot tf-idf dari term i dalam dokumen cos(q,d) : kemiripan cosinus (cosim) antara q dan d … atau cosinus dari sudut antara q dan d. 37
Cosinus untuk Vektor Panjang Ternormalisasi • Untuk vektor length-normalized, cosine similarity merupakan dot product (atau scalar product):
38
Ilustrasi Cosine Similarity
39
Cosine Similarity Antara 3 Dokumen • Semirip apakah novel-novel tersebut – SaS: Sense and
Sensibility – PaP: Pride and Prejudice, and – WH: Wuthering Heights? Catatan: untuk menyederhanakan contoh ini, tidak dilakukan pembobotan idf
40
Cosine Similarity Antara 3 Dokumen Pembobotan Frekuensi Log
Setelah normalisasi panjang
• cos(SaS,PaP) ≈ • 0.789 × 0.832 + 0.515 × 0.555 + 0.335 × 0.0 + 0.0 × 0.0
• • • •
≈ 0.94 cos(SaS,WH) ≈ 0.79 cos(PaP,WH) ≈ 0.69 Mengapa cos(SaS,PaP) > cos(SaS,WH)? 41
Menghitung Skore Cosinus
42
Pengamatan • Inverted index yang digunakan pada pemrosesan query boolean masih penting bagi retrieval dokumen dengan penskoran teratas (top k) • Tidak tepat memeriksa semua dokumen untuk menghitung dokumen top K (lebih mirip) terhadap query input • Query normalnya adalah dokumen pendek Coba dengan Query panjang! 43
Varian Pembobotan tf-idf
• Kolom "n" merupakan singkatan dari skema pembobotan. • Mengapa basis dari log dalam idf tidak penting? 44
Pembobotan Berbeda untuk Query vs. Dokumen • Banyak search engines membolehkan pembobotan berbeda untuk Queries vs. Dokumen • Notasi SMART: menunjukkan kombinasi penggunaan dalam engine, dengan notasi ddd.qqq, menggunakan akronim dari tabel sebelumnya • Suatu skema pembobotan yang sangat standard adalah lnc.ltc Ide Jelek? • Dokumen: tf logaritmik (l sebagai karakter pertama), bukan idf, dan normalisasi cosinus • Query: tf logaritmik (l dalam kolom terkiri), idf (t dalam kolom kedua), normalisasi cosinus … 45
Contoh tf-idf : Inc.ltc • Dokumen: car insurance auto insurance • Query: best car insurance
Latihan: berapa nilai N, yaitu jumlah dokumen? Skor= 0+0+0.27+0.53 = 0.8 46
Rangkuman: Perankingan Ruang Vektor • Merepresentasikan query sebagai vektor tf-idf berbobot • Hitung skor kemiripan cosinus antara vektor Query dan setiap vektor dokumen • Meranking dokumen sesuai dengan skor kemiripan (menurun) • Kembalikan top K (misal: K = 10) kepada pengguna. 47
Penskoran dalam Sistem Pencarian Lengkap
Ranking Cosinus Efisien • Temukan K dokumen dalam koleksi “terdekat” dengan query ⇒ K cosinus query-dok. terbesar • Ranking Efisien: – Menghitung cosinus tunggal (antara Query dengan setiap dokumen) secara efisien – Pilih K nilai cosinus terbesar secara efisien • Dapatkah ini dilakukan tanpa menghitung cosinus semua (N dokumen)? • Dapatkah ditemukan solusi mendekati? 49
Ranking Cosinus Efisien • Apa pengaruh dari (slide 49)? Menyelesaikan masalah K-tetangga terdekat untuk suatu vektor query • Secara umum, tak diketahui bagaimana melakukan ini secara efisien untuk ruang berdimensi tinggi • Tetapi dapat dibuktikan untuk query pendek. Indeks standard mendukung dengan baik.
50
Kasus Khusus: Query tak-dibobot • Anggap setiap term query hadir hanya sekali • Skor idf dipertimbangkan dalam termterm dokumen • Perankingan tidak memperhatikan bobot vektor query – Penyederhanaan dari algoritma pada buku IIR Bab 6 51
Cosinus Cepat: Query tak-dibobot
semuanya 1
Algoritma cepat untuk penskoran pada ruang vektor
52
Menghitung K Cosinus Terbesar: selection vs. sorting • Akan diretrieve top K dokumen (dalam ranking cosinus terhadap query) – Tidak mengurutkan semua dokumen dalam koleksi
• Dapatkah diambil hanya dokumen dengan K cosinus tertinggi? • Katakanlah J = jumlah dokumen dengan cosinus tidak nol (nonzero) – Mendapatkan K terbaik dari J ini 53
Pemilihan Top-K: Heap • Pohon biner (binary tree) dimana setiap nilai node > nilai dari anak (anggap ada J nodes) • Diperlukan 2J operasi untuk konstruksi, kemudian setiap K "juara" dibaca dalam 2log J langkah. • Untuk J=1juta, K=100, ini sekitar 5% biaya pengurutan (2JlogJ).
54
Kemiripan Cosinus Hanya Proxy • Pengguna merumuskan suatu Query • Sistem menghitung kecocokan cosinus dokumen dengan query • Jadi cosinus adalah proxy (wakil) bagi kebahagiaan pengguna • Jika diperoleh suatu daftar K dokumen “dekat” dengan top K berdasarkan ukuran cosinus, tentu Okay • Ingat, tujuan akhirnya: membangun sistem yang efektif dan efisien, bukan menghitung dengan tepat rumus yang digunakan.
55
Pendekatan Generik • Temukan himpunan A pesaing (contender), dengan K < |A| << N (N adalah jumlah total dokumen) – A tidak perlu mengandung top K, tetapi mempunyai banyak dokumen di antara top K – Kembalikan top K dokumen dalam A
• Pikirkan A sebagai pruning non-contenders • Pendekatan yang sama juga digunakan untuk fungsi penskoran lainnya (non-cosinus) (ingat koreksi ejaan dan jarak Levenshtein) • Akan dilihat beberapa skema mengikuti pendekatan ini. 56
Eliminasi Indeks • Algoritma FastCosineScore hanya melibatkan dokumen yang mengandung setidaknya satu term query jelas! • Gunakan ide ini lebih lanjut: – Hanya melibatkan term query yang idf-nya tinggi – Hanya melibatkan dokumen yang mengandung banyak term query.
57
Hanya Term Query Ber-idf Tinggi • Untuk suatu query seperti “catcher in the rye” • Hanya akumulasikan skor dari “catcher” dan “rye” • Intuisi: “in” dan “the” berkontribusi kecil terhadap skor dan tidak banyak mengubah pengurutan ranking – Term tersebut hadir dalam sebagian besar dokumen dan bobot idf-nya rendah • Keuntungan: – Postings dari term idf rendah mempunyai banyak dokumen maka dokumen-dokumen ini dapat dieliminasi dari himpunan contenders A. 58
Dokumen Mengandung Banyak Term Query • Dokumen dengan setidaknya satu term query adalah kandidat dari top K • Bagi query banyak term, hanya hitung skor untuk dokumen yang mengandung beberapa term query – Katakanlah, setidaknya 3 dari 4 – Tentukan suatu “soft conjunction” pada query yang terlihat pada web search engines (Google awal)
• Mudah diimplementasikan dalam postings traversal. 59
3 dari 4 Term Query
• Skor hanya dihitung untuk dokumen 8, 16 dan 32
60
Daftar (Dokumen) Juara • Precompute setiap term kamus t, r dokumen dengan bobot tertinggi dalam posting t – Sebut ini sebagai champion list (daftar juara) bagi t – (dahulu: fancy list atau top docs)
• r harus dipilih saat pembuatan indeks – Adalah mungkin bahwa r < K
• Saat pemrosesan query, hanya hitung skor untuk dokumen-dokumen dalam champion list dari beberapa term query – Ambil K top-scoring dokumen dari champion list. 61
Latihan • Bagaimana kaitan antara Champion Lists dan Index Elimination? (mengeliminasi term query dengan idf rendah - menghitung skor hanya jika sejumlah pasti dari term query hadir di dalam dokumen) • Dapatkah digunakan bersama? • Bagaimana Champion Lists dapat diimplementasikan dalam inverted index? – Tidak ada yang dilakukan oleh champion list terhadap docIDs kecil. 62
Skor Kualitas Statik • Diinginkan top-ranking dokumen yang relevan dan otoritatif • Relevansi dimodelkan dengan skor cosinus • Otoritas pada dasarnya adalah properti tak tergantung query dari suatu dokumen • Contoh sinyal otoritas – Wikipedia di antara websites – Articles dalam surat kabar tertentu – Selembar kertas dengan banyak sitasi – Banyak tanda diggs, Y!buzzes atau del.icio.us – Pagerank 63
Pemodelan Otoritas • Berikan setiap dokumen d suatu skor kualitas tak-bergantung query dalam [0,1] – Tunjukkan ini dengan g(d) • Suatu kuantitas seperti jumlah sitasi diskalakan ke dalam [0,1] – Latihan: usulkan suatu rumus untuk ini.
64
Skor Total (Net Score) • Skor total gabungan relevansi cosinus dan otoritasnya • net-score(q,d) = g(d) + cosine(q,d) – Dapat menggunakan kombinasi linier lain (bukan pembobotan yang sama) – Fungsi dari dua “sinyal” kebahagian pengguna (lebih lanjut nanti)
• Sekarang: cari top K dokumen dengan skor net (net-score)
65
Top K dengan net score Metode Cepat • Ide pertama: Urutkan semua postings berdasar
g(d)
– Pengurutan umum untuk semua postings • Jadi, dapat secara konkuren menjelajah posting term query untuk – Irisan posting – Pehitungan skor cosinus • Latihan: tuliskan pseudocode untuk perhitungan skor cosinus jika postings terurut berdasarkan g(d) 66
Mengurutkan Posting dengan g(d)? • Pada pengurutan g(d), top-scoring docs kemungkinan besar muncul lebih awal dalam penjelajahan posting • Dalam aplikasi terbatas waktu (misalnya harus mengembalikan hasil pencarian dalam 50 ms), penjelajahan dapat dihentikan segera. – Jalan pintas dari menghitung skor untuk semua dokumen dalam postings. 67
Champion lists dalam pengurutan g(d) • Champion lists dapat dikombinasikan dengan pengurutan g(d) • Pelihara untuk setiap term suatu champion list dari r dokumen dengan g(d) + tf-idftd tertinggi • Urutkan posting berdasarkan g(d) • Cari top-K hasil hanya dari dokumen di dalam champion lists ini. 68
Posting Terurut-Pengaruh • Hanya ingin menghitung skor dari dokumen dengan wft,d cukup tinggi • Urutkan setiap postings list berdasarkan wft,d – Saat melibatkan posting dan menghitung skor bagi dokumen, ada batasan skor akhir untuk dokumen-dokumen ini • Jadi: tidak semua posting dalam urutan umum! • Bagaimana menghitung skor untuk mengambil top K? – Dua ide...
69
1. Terminasi Sejak Awal • Ketika menjelajah posting t, stop ’s postings,
stop sejak awal setelah (salah satu) – sejumlah pasti r dokumen – wft,d jatuh di bawah threshold
• Ambil gabungan himpunan hasil dari dokumen – Dokumen dari postings dari setiap term query
• Hitung skor hanya untuk dokumen dalam gabungan (union) ini. 70
2. Term Terurut idf • Ketika melibatkan postings dari term-term query • Cari term-term tersebut dalam urutan idf menurun (ada banyak) – Term idf tinggi kemungkinan besar berkontribusi lebih besar terhadap skor
• Ketika mengupdate kontribusi skor dari setiap term query – Stop jika skor dokumen relatif tidak berubah – Terjadi untuk term query popular (idf rendah)
• Dapat berlaku terhadap cosinus atau beberapa skor total lain. 71
Indeks Parametrik dan Zona • Sejauh ini, dokumen telah berupa suatu deretan term • Faktanya dokumen mempunyai banyak bagian, beberapa dengan semantika khusus: – – – – – –
Author Title Date of publication Language Format etc.
• Ini mengangkat metadata mengenai suatu dokumen. 72
Fields • Kadang ingin mencari berdasarkan metadata – Misal: temukan dokumen yang ditulis oleh William Shakespeare pada tahun 1601, mengandung alas
poor Yorick
• Year = 1601 adalah contoh field • Juga, nama akhir penulis = shakespeare, dll • Field index: postings untuk setiap nilai – kadang membangun pohon range (seperti untuk tanggal) • Field query biasanya diperlakukan sebagai
conjunction
– (dokumen harus dikarang oleh shakespeare) 73
Zona • Zona adalah suatu wilayah dari dokumen yang dapat mengandung sejumlah teks, misalnya: – Title – Abstract – References …
• Bangun inverted indexes pada zones juga mengijinkan peng-query-an • Misal “temukan dokumen dengan merchant in
zona title dan cocok dengan query gentle rain”
74
Contoh Indeks Zona
75
Daftar Tinggi dan Rendah • Untuk setiap term, diperoleh dua postings lists bernama high dan low – Pikirkan high sebagai suatu champion list • Pada saat menjelajahi postings pada suatu query, hanya lintasi high lists lebih dahulu – Jika mendapatkan lebih dari K docs, pilih top K dan stop (berhenti) – Jika tidak lanjutkan untuk mendapatkan dokumen dari low lists • Dapat digunakan bahkan untuk skor cosinus biasa, tanpa kualitas global g(d) • Berarti mensegmen indeks ke dalam dua tier (tingkat). 76
Index Bertingkat • Pecahkan postings (bukan dokumen) ke dalam hirarki daftar – paling penting – … – paling kurang penting
• Dapat dikerjakan dengan g(d) atau ukuran lain • Inverted index dibagi-bagi menjadi tingkatan (tier) kepentingan yang menurun (decreasing) • Saat pemrosesan query gunakan top tier kecuali gagal menghasilkan K dokumen – Karena itu berpindahlah ke tier lebih rendah. 77
Index Bertingkat: Contoh
78
Pendekatan Term Query • Query Teks Bebas (free text query): sehimpunan term yang dimasukkan dalam kotak query • Pengguna lebih menyukai dokumen yang term query muncul di dalamnya, diperkirakan dekat satu dengan lainnya • Katakan w adalah window terkecil dalam suatu dokumen yang mengandung semua term query, misalnya: – Query "strained mercy" window terkecil dalam dokumen "The quality of mercy is not strained" adalah 4 (kata) • Bagaimana fungsi pen-skor-annya? 79
Pengurai Query Query Parser • Satu query teks bebas dari pengguna mungkin diubah menjadi satu atau lebih query terhadap indeks, misal query Q "rising interest rates“ – Jalankan query sebagai query frase – Jika < K dokumen mengandung frase "rising interest rates", jalankan dua query frase "rising interest" dan "interest rates“ – Jika masih mendapatkan < K dokumen, jalankan query ruang vektor "rising interest rates“ – Ranking dokumen yang cocok dengan penskoran ruang vektor • Rangkaian ini dieksekusi oleh query parser. 80
Mentotalkan Skor • Telah dilihat bahwa fungsi skor dapat mengkombinasikan cosinus, kualitas statis, proximity (perkiraan), dll. • Bagaimana mengetahui kombinasi terbaik? • Beberapa aplikasi - melibatkan pakar • Semakin popular: pembelajaran mesin (machine learning) 81
Menyatukan Semuanya
82
Bahan Bacaan • Sub bab 6.2, 6.3, 6.4 (kecuali 6.4.4) • Sub bab 7.1, 7.2
83
Pertanyaan •?
84
