Temu-Kembali Informasi 2017 02: Temu-Kembali Boolean Husni
[email protected]
Modifikasi dari slide kuliah Stanford CS276
Temu-Kembali Informasi Information Retrieval • Information Retrieval (IR) adalah menemukan materi (biasanya dokumen) dari suatu yang sifatnya tak-terstruktur (biasanya teks) yang memenuhi kebutuhan informasi dari dalam koleksi besar (yang biasanya disimpan pada beberapa komputer).
2
Data Tak-Terstruktur (Teks) vs. Terstruktur (Database) pada 1996
3
Data Tak-Terstruktur (Teks) vs. Terstruktur (Database) pada 2009
4
Sec. 1.1
Data Tak-Terstruktur pada 1620 • Sandiwara Shakespeare mana yang mengandung kata Brutus AND Caesar tetapi NOT Calpurnia? • Kita dapat mengambil semua sandiwara Shakespeare yang mengandung Brutus dan Caesar, kemudian mengeluarkan yang mengandung Calpurnia? • Mengapa itu bukan jawabannya? • Lambat pemrosesannya (untuk corpora besar) • NOT Calpurnia itu tidak sepele (non-trivial) • Operasi lain (misal, carilah kata Romans dekat countrymen) tidak mudah dikerjakan • Temu-kembali teranking (dokumen-dokumen terbaik yang dikembalikan) • Kuliah-kuliah berikutnya 5
Sec. 1.1
Pengaruh Term-Document Hubungan Kata dan Dokumen Antony and Cleopatra
Julius Caesar
The Tempest
Hamlet
Othello
Macbeth
Antony
1
1
0
0
0
1
Brutus
1
1
0
1
0
0
Caesar
1
1
0
1
1
1
Calpurnia
0
1
0
0
0
0
Cleopatra
1
0
0
0
0
0
mercy
1
0
1
1
1
1
worser
1
0
1
1
1
0
Brutus AND Caesar BUT NOT Calpurnia
1 jika sandiwara mengandung kata, 0 jika tidak
Sec. 1.1
Vektor Pengaruh (Hubungan) • Sehingga diperoleh suatu vektor 0/1 untuk setiap term. • Untuk menjawab query: ambil vektor Brutus, Caesar dan Calpurnia (di-komplemen-kan) bitwise AND. • 110100 AND 110111 AND 101111 = 100100.
7
Sec. 1.1
Jawaban untuk Query • Antony and Cleopatra, Act III, Scene ii Agrippa [Aside to DOMITIUS ENOBARBUS]: Why, Enobarbus, When Antony found Julius Caesar dead, He cried almost to roaring; and he wept When at Philippi he found Brutus slain.
• Hamlet, Act III, Scene ii Lord Polonius: I did enact Julius Caesar I was killed i' the Capitol; Brutus killed me. 8
Sec. 1.1
Asumsi Dasar dalam Temu-Kembali Informasi • Koleksi (corpus): Himpunan tetap dokumen • Sasaran (goal): Menemukan-kembali (memperoleh) dokumendokumen yang mengandung informasi yang relevan dengan kebutuhan informasi pengguna dan membantu pengguna tersebut menyelesaikan suatu tugas
9
Model Pencarian Klasik Singkirkan tikus dengan cara yang benar secara politis
Task
Misconception?
Info tentang cara menghapus tikus tanpa membunuhnya
Info Need
Mistranslation? Verbal form
Bagaimana cara memerangkap tikus hidup? Misformulation?
Query
perangkap tikus Search Engine
Query Refinement
Results
Corpus
Sec. 1.1
Seberapa Baik Dokumen yang Diperoleh? • Ketepatan (Presisi, Precision): Bagian (persentase) dari dokumendokumen yang diperoleh yang relevan dengan kebutuhan informasi pengguna • Penarikan-Kembali (Recall): Persentase dari dokumen-dokumen yang relevan dari dalam koleksi yang diperoleh (diterima pengguna) • Definisi dan ukuran yang lebih tepat akan dijelaskan pada kuliahkuliah berikutnya...
11
Sec. 1.1
Koleksi Lebih Besar • Anggap N = 1 juta dokumen, masing-masing mengandung 1000 kata. • Rerata 6 byte per kata termasuk spasi dan tanda baca • 6GB data di dalam dokumen-dokumen tersebut.
• Katakanlah di sana ada M = 500K term-term berbeda di antaranya.
12
Sec. 1.1
Dapatkan Dibuatkan Matriksnya • Matriks 500K x 1M yang mempunyai setengah triliun 0 dan 1. • Tetapi mempunyai tidak lebih dari satu milyar 1. • Matriksnya sangat jarang (sparse, lihat nilai 1).
• Seperti apa representasi yang lebih baik?
Mengapa?
• Kita hanya merekam yang posisi 1.
13
Sec. 1.2
Inverted Index Indeks Terbalik
• Untuk setiap term t, kita harus menyimpan daftar (list) semua dokumen yang mengandung term t tersebut. • Setiap dokumen diidentifikasi dengan docID, suatu nomor seri dokumen
• Dapatkah digunakan larik berukuran tetap (fixed-size array)? Brutus
1
Caesar
1
Calpurnia
2
2
2 31
4
11 31 45 173 174
4
5
6
16 57 132
54 101
Apa yang terjadi jika kata Caesar ditambahkan ke dokumen 14? 14
Sec. 1.2
Inverted index • Diperlukan daftar posting berukuran tak-tetap (variable-size postings list) • Pada disk, a continuous run of postings is normal and best • Dalam memory, dapat menggunakan linked list atau array yang panjangnya taktetap Posting • Ada tarik-ulur dalam ukuran/kemudahan penyisipan
Brutus
1
Caesar
1
Calpurnia Dictionary (Kamus)
2
2
2 31
4
11
31 45 173 174
4
5
6
16 57 132
54 101 Postings
Diurutkan berdasarkan docID (mengapa?). 15
Sec. 1.2
Konstruksi Inverted Index Dokumen yang diindeks.
Friends, Romans, countrymen. Tokenizer
Token stream. Lebih lanjut nanti...
Friends Romans Modul-modul Linguistik friend
Token termodifikasi.
Indexer Inverted index.
Countrymen
roman
countryman
friend
2
4
roman
1
2
countryman
13
16
Sec. 1.2
Tahapan Indexer: Rentetan Token • Rentetan dari pasangan (Token Termodifikasi, Document ID). Doc 1 I did enact Julius Caesar I was killed i' the Capitol; Brutus killed me.
Doc 2 So let it be with Caesar. The noble Brutus hath told you Caesar was ambitious
Sec. 1.2
Tahapan Indexer: Urutkan • Urutkan berdasarkan term-term ...dan kemudian berdasarkan docID
Langkah Indexing Inti
Sec. 1.2
Tahapan Indexer: Dictionary & Postings • Beberapa entri term dalam satu dokumen digabungkan • Bagi ke dalam dictionary dan postings • Informasi frekuensi dokumen ditambahkan.
Mengapa frekuensi? Lihat diskusi selanjutnya!
Sec. 1.2
Biaya Penyimpanan? Daftar dari docID Term dan jumlah kemunculannya
Nanti dalam kuliah berikutnya: ▪ Bagaimana mengindeks secara efisien? ▪ Berapa banyak storage (disk) yang diperlukan? Pointer
20
Sec. 1.3
Indeks Telah Terwujud! • Bagaimana kita memroses suatu query? • Kemudian: Jenis query apa yang dapat diproses?
Fokus hari ini
21
Sec. 1.3
Pemrosesan Query: AND • Seandainya query yang akan diproses adalah Brutus AND Caesar • Temukan Brutus di dalam dictionary; • Dapatkan (retrieve) posting-postingnya. • Temukan Caesar di dalam dictionary; • Retrieve posting-postingnya. • “Merge” (gabungkan) dua posting tersebut: 2
4
8
16
1
2
3
5
32 8
64 13
128 21
Brutus 34 Caesar
22
Sec. 1.3
Gabungannya • Kunjungi dua posting itu secara bersamaan, waktunya sebanding dengan jumlah total dari entri posting-posting
2
8
2
4
8
16
1
2
3
5
32
8
64
13
128
21
Brutus
34 Caesar
Jika panjang daftar adalah x dan y, maka gabungannya memerlukan operasi O(x+y). Penting sekali: posting telah diurutkan berdasarkan docID.
23
Irisan Dua Daftar Posting (Algoritma “merge”)
24
Sec. 1.3
Query Boolean: Cocok Pasti Tepat • Model Temu-Kembali Boolean: agar mampu menangani query berbentuk ekspresi Boolean: • Query Boolean: menggunakan operator AND, OR dan NOT untuk menggabungkan term-term query • Menampilkan setiap dokuen sebagai sehimpinan kata-kata • Apakah tepat (presisi): dokumen sesuai kondisi atau tidak.
• Mungkin model paling simpel untuk membangun suatu sistem IR
• Perangkat retrieval komersil utama selama 3 dekade. • Banyak sistem pencarian masih menggunakan model Boolean: • Pencarian di Gmail, katalog perpustakaan, Pencarian file di Windows Explorer, Mac OS X Spotlight 25
Sec. 1.4
Contoh: WestLaw
http://www.westlaw.com/
• Layanan pencarian legal komersial terbesar (anggota berbayar) (dimulai 1975; ranking ditambahkan pada 1992) • Puluhan terabytes data; 700,000 pengguna • Mayaritas pengguna masih menggunakan query boolean • Contoh query: • Apa undang-undang pembatasan dalam kasus-kasus yang melibatkan tindakan gugatan tort federal? • LIMIT! /3 STATUTE ACTION /S FEDERAL /2 TORT /3 CLAIM • ! = wildcard, /3 = dalam 3 kata, /S = dalam kalimat yang sama
26
Sec. 1.4
Contoh: WestLaw
http://www.westlaw.com/
• Contoh query lain: • Persyaratan bagi penyandang cacat untuk dapat mengakses tempat kerja • disabl! /p access! /s work-site work-place (employment /3 place)
• Catatan: SPACE adalah disjunction, bukan conjunction! • Pertanyaan yang panjang dan tepat; operator kedekatan; dikembangkan secara bertahap; tidak seperti pencarian web • Banyak pencari professional masih menyukai pencarian Boolean • Dia tahu secara pasti apa yang diperolehnya
• Tetapi itu bukan berarti sesungguhnya ia bekerja lebih baik….
Sec. 1.3
Query Boolean: Gabungan Lebih Umum • Latihan: Sesuaikan algoritma merge untuk query:
Brutus AND NOT Caesar Brutus OR NOT Caesar Dapatkah kita masih menjalankan merge itu dalam waktu O(x+y)? Apa yang dapat kita capai?
28
Sec. 1.3
Penggabungan Bagaimana dengan suatu formula Boolean berubah-ubah?
(Brutus OR Caesar) AND NOT (Antony OR Cleopatra) • Dapatkah kita selalu me-merge-kan itu dalam waktu “linier”? • Linier dalam apa?
• Dapatkah dilakukan dengan cara lebih baik?
29
Sec. 1.3
Optimisasi Query • Apakah urutan terbaik dalam pemrosesan query? • Anggap suatu query yang meng-AND-kan n term. • Untuk masing-masing dari n term, ambil postingnya, kemudian ANDkan bersama-sama. Brutus
2
Caesar
1
2
13
16
Calpurnia
4
8
16
32 64 128
3
5
8
Query: Brutus AND Calpurnia AND Caesar
16
21 34
Sec. 1.3
Contoh Optimisasi Query • Proses mengikuti naiknya frekuensi: • Mulai dengan himpunan terkecil, kemudian lanjutkan ke lebih besar.
Inilah mengapa frekuensi dokumen disimpan dalam kamus Brutus
2
Caesar
1
Calpurnia
4 2
8
16 32 64 128
3
5
8
16 21 34
13 16
Eksekusi query sebagai (Calpurnia AND Brutus) AND Caesar. 31
Sec. 1.3
Optimisasi Lebih Umum • Misalnya (madding OR crowd) AND (ignoble OR strife) • Dapatkan frekuensi dokumen untuk semua term. • Estimasikan ukuran dari setiap OR dengan menjumlahkan frekuensi dokumennya (konservatif). • Proses mengikuti kenaikan ukuran OR.
32
Latihan • Rekomendasikan suatu urutan pemrosesan query untuk (tangerine OR trees) AND (marmalade OR skies) AND (kaleidoscope OR eyes)
Term eyes kaleidoscope marmalade skies tangerine trees
Frekuensi 213312 87009 107913 271658 46653 316812 33
Latihan Pemrosean Query • Latihan: Jika query-nya adalah friends AND romans AND (NOT countrymen), bagaimana kita dapat menggunakan frekuensi dari countrymen? • Latihan: Perluas merge untuk query Boolean berubah-ubah (sembarang). Dapatkah kita selalu menjamin eksekusi dalam waktu linier dalam ukuran posting total? • Hint: Mulai dengan kasus query boolean: setiap term query hadir hanya sekali dalam query tersebut.
34
Latihan
• Coba fitur-fitur pencarian pada http://www.rhymezone.com/shakespeare/ • Tuliskan lima fitur pencarian yang anda pikirkan dapat melakukan lebih baik.
35
Apa yang ada di Depan IR? Lebih dari Pencarian Term • Bagaimana dengan frasa? • Universitas Trunojoyo Madura
• Kedekatan: Temukan Gates DEKAT Microsoft. • Perlu indeks untuk menangkap informasi posisi dalam dokumen.
• Zona dalam dokumen: Temukan dokumen dengan (author = Ullman) AND (teks tersebut mengandung automata).
36
Akumulasi Fakta • 1 vs. 0 kemunculan dari suatu term pencarian • 2 vs. 1 kemunculan • 3 vs. 2 kemunculan, dll. • Biasanya lebih banyak terlihat lebih baik
• Diperlukan informasi frekuensi term di dalam dokumen.
37
Perankingan Hasil Pencarian • Query boolean memberikan inklusi atau eksklusi dokumen. • Sering kita ingin meranking/mengelompokkan hasil • Perlu mengukur kedekatan dari query ke setiap dokumen. • Perlu memutuskan apakah dokumen yang disajikan kepada pengguna adalah singletons (tunggal), atau sekelompok dokumen yang mencakup berbagai aspek dari query.
38
IR vs. Databases: Data Terstruktur vs. Tak-Terstruktur • Data terstruktur cenderung merujuk kepada informasi di dalam “table” Karyawan
Manajer
Gaji
Smith
Jones
50000
Chang
Smith
60000
Ivy
Smith
50000
Khasnya memungkinkan query pencocokan eksakta dan range numeris (untuk teks), misal: Salary < 60000 AND Manager = Smith. 39
Data Tak-Terstruktur • Khasnya merujuk kepada teks bebas • Memungkinkan • Query kata kunci (keyword) termasuk operator-operator • Query “konsep” yang lebih canggih, misal: • Temukan semua halaman web yang berkaitan erat dengan drug abuse
• Model klasik untuk pencarian dokumen teks.
40
Data Semi-Terstruktur • Faktanya,hampir tidak ada data yang “Tak-Terstruktur” • Misalnya, slide ini mempunyai zona-zona yang dikenali secara berbeda seperti Title dan Bullets • Memudahkan pencarian “semi-terstruktur” seperti • Title mengandung data AND Bullets mengandung pencarian
... untuk tidak mengatakan apapun tentang struktur linguistik
41
Pencarian Semi-Terstruktur Lebih Canggih • Title tentang Object Oriented Programming AND Author sesuatu seperti stro*rup • Dimana * adalah operator wild-card • Persoalan: • Bagaimana kita memroses “tentang”? • Bagaimana kita merangking hasil?
• Merupakan fokus dari pencarian XML (lihat buku IIR bab 10)
42
Clustering, Classification dan Ranking • Clustering (Klasterisasi): • Diberikan sehimpunan dokumen, kelompokkan dokumen-dokumen tersebut ke dalam klaster-klaster berdasarkan pada isinya.
• Classification (Klasifikasi): • Diberikan sehimpunan topik, ditambahkan suatu dokumen baru D, putuskan topik mana yang akan ditempati oleh D.
• Ranking (Pemeringkatan): • Dapat kita pelajari bagaimana urutan terbaik dari sehimpunan dokumen, misalnya sehimpunan hasil pencarian.
43
Web dan Tantangannya • Dokumen-dokumen beragam dan tak-biasa • Query dan kebutuhan informasi pengguna beragam dan takbiasa • Lebih dari term-term, mengeksploitasi gagasan dari jejaring sosial • Analisa link (tautan), clickstreams ...
• Bagaimana search engines bekerja? Dan bagaimana kita dapat membuatnya lebih baik?
44
Temu-Kembali Informasi Lebih Canggih • Temu-Kembali Informasi lintas Bahasa • Question answering • Summarization • Text mining •…
45
Sumber Daya Kuliah Hari ini • Introduction to Information Retrieval, Bab 1 • Shakespeare: • http://www.rhymezone.com/shakespeare/ • Coba jelajah murni dengan fitur deretan keyword!
• Managing Gigabytes, sub-bab 3.2 • Modern Information Retrieval, sub-bab 8.2
Ada Pertanyaan? 46
