STBI-2011
Sistem Temu Balik Informasi 2011
Temu-Balik Boolean Husni
[email protected] Husni.trunojoyo.ac.id Komputasi.wordpress.com
Pemrolehan-Kembali Informasi Information Retrieval (IR)
Pencarian material (biasanya dokumen) dari suatu yang tak-terstruktur (biasanya teks) yang memenuhi kebutuhan informasi dari dalam koleksi yang besar (biasanya disimpan pada komputer).
2
Data Tak-Terstruktur (text) vs. Terstruktur (database), 1996
3
Data Tak-Terstruktur (text) vs. Terstruktur (database), 2009
4
http://www.internetworldstats.com/images/world2010users.png
5
http://www.internetworldstats.com/images/world2010pie.png
6
Sec. 1.1
Data Tak-Terstruktur, 1680 Buku mana dalam koleksi Shakespeare yang berisi kata Brutus AND Caesar tetapi NOT Calpurnia? Meng-grep semua buku yang mengandung Brutus dan Caesar, kemudian mengeluarkan yang mengandung Calpurnia?!!! Mengapa itu bukan jawaban? Lambat (jika koleksinya banyak, besar) NOT Calpurnia bukan hal sepele Operasi lain (seperti temukan kata “Romans dekat countrymen) tidak mungkin
Retrieval teranking (kembalikan dokumen terbaik) 7
Sec. 1.1
Hubungan Term-document 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 TETAPI NOT Calpurnia
1 jika buku mengandung kata, 0 jika tidak
Sec. 1.1
Vektor Hubungan Diperoleh vektor 0/1 untuk setiap term Untuk menjawab query: Ambil vektor untuk Brutus, Caesar dan Calpurnia (dikomplemenkan) bitwise AND.
110100 AND 110111 AND 101111
= 100100.
9
Sec. 1.1
Jawaban Terhadap 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. 10
Sec. 1.1
Asumsi Dasar dari IR Koleksi (Corpus): Himpunan tetap (fix) dokumen Goal (Tujuan): Retrieve (temukan kembali) dokumen-dokumen dengan informasi yang relevan dengan kebutuhan informasi pengguna dan bantu pengguna menyelesaikan suatu tugas.
11
Model Pencarian Klasik Singkirkan tikus dengan cara yang benar secara politis
TASK
Misconception? Info tentang menghilangkan tikus tanpa membunuhnya
Info Need
Mistranslation? Bagaimana menangkap tikus?
Verbal form
Misformulation? Menangkap tikus
Query
SEARCH ENGINE
Query Refinement
Results
Corpus
Sec. 1.1
Baguskah Dokumen yang diRETRIEVE? Precision (Presisi): Prosentase dari dokumen yang diperoleh yang relevan dengan kebutuhan informasi pengguna
Recall : Prosentase dari dokumen yang relevan dalam koleksi (himpunan) yang diretrieve Juga terdapat definisi dan ukuran ketepatan lain...
13
Sec. 1.1
Koleksi Lebih Besar Misal N = 1 juta dokumen, masing-masing sekitar 1000 kata. Rata-rata 6 byte per kata termasuk spasi atau tanda baca 6 GB data dalam koleksi dokumen. Katakanlah ada M = 500 Ribu term berbeda di antaranya.
14
Sec. 1.1
Tidak dapat Membangun Matriks Matrisk 500 Ribu x 1 Juta terdiri dari setengah trilyun 0 dan 1. Tetapi tidak terdiri lebih dari se-milyar 1.
???
Matriks sangat jarang (banyak kosongnya).
Bagaimana representasi yang baik? Hanya rekam posisi bernilai 1.
15
Sec. 1.2
Inverted index Untuk setiap term t, simpan daftar semua dokumen yang mengandung t. Identifikasi berdasarkan docID, nomor seri dokumen
Menggunakan array berukuran tetap? Brutus
1
Caesar
1
Calpurnia
2
2 2
31
4
11
31 45 173 174
4
5
6
16 57 132
54 101
Bagaimana jika kata Caesar ditambahkan ke dalam dokumen 14? 16
Sec. 1.2
Inverted index ...perlu daftar posting berukuran variable Pada disk, bersifat kontinu: normal dan terbaik Dalam memory, gunakan linked lists atau array berukuran variable DocId Tarik-ulur dalam ukuran & kemudahan penyisipan
Brutus
1
Caesar
1
Calpurnia
Dictionary
2
2 2 31
4
11
31 45 173 174
4
5
6
16 57 132
54 101
Daftar Posting Urut berdasarkan docID (Mengapa?)
17
Sec. 1.2
Konstruksi Inverted Index Dokumen awal (akan diindex)
Friends, Romans, countrymen. Tokenizer Friends Romans
Aliran token Dibahas kemudian Token Baru
Modul Linguistik (Bahasa) friend
roman
Countrymen
countryman
Indexer friend
2
4
roman
1
2
countryman
13
Inverted index
16
Tahapan Indexer : deretan token Deretan pasangan (Token baru, Doc-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 Kemudian berdasarkan docID Langkah Indexing Utama
Sec. 1.2
Sec. 1.2
Tahapan Indexer : Dictionary & Posting Banyak entri term dalam satu dokumen digabungkan. Bagi ke dalam Dictionary dan Posting Tambahkan informasi frekuensi dokumen.
Mengapa frekuensi? (dibahas nanti)
Sec. 1.2
Biaya Penyimpanan? Daftar doc-ID Term & Jumlah posting
Pointer
Dibahas nanti: •Bagaimana mengindex dengan efisien? •Berapa kapasitas simpan yang 22 dibutuhkan?
Sec. 1.3
Index yang baru dibangun Bagaimana memroses suatu query?
Fokus Kini
Kemudian – jenis query apa yang dapat diproses?
23
Sec. 1.3
Pemrosesan Query: AND Perhatikan pemrosesan query: Brutus AND Caesar Temukan Brutus dalam Dictionary; Ambil posting-nya.
Temukan Caesar dalam Dictionary; Ambil posting-nya.
Temukan irisan dari kedua posting tersebut: 2
4
8
16
1
2
3
5
32 8
64 13
128 21
Brutus
34 Caesar 24
Sec. 1.3
Gabungan atau Irisannya Periksa kedua postingan, temukan yang sama posting-nya. Jumlah waktu linier dengan jumlah posting
2
8
2
4
8
16
1
2
3
5
32 8
64 13
128 21
Brutus 34 Caesar
Jika panjang list adalah x dan y, penggabungan memerlukan operasi O(x+y). Krusial: posting diurutkan berdasarkan docID. 25
Perpotongan dua posting list (Algoritma “merge”)
26
Sec. 1.3
Query Boolean: Kecocokan Pasti Model Retrieval Boolean mampu menangani query berwujud ekspresi Boolean: Query Boolean: query menggunakan AND, OR dan NOT untuk menyatukan term-term query. Melihat setiap dokumen sebagai himpunan kata Tepatkah: Dokumen sesuai kondisi atau TIDAK.
Model paling sederhana untuk membangun sistem IR
Tool retrieval komersil utama selama 30 tahun. Banyak sistem pencarian mengunakan model Boolean: Email, Katalog perpustakaan, Mac OS X Spotlight 27
Sec. 1.4
Contoh: www.westlaw.com Layanan pencarian legal komersial (anggota berbayar) paling besar (dimulai 1975; ranking ditambahkan pada 1992) Puluhan terabyte data; 700.000 pengguna Mayoritas pengguna masih menggunakan query boolean Contoh query: What is the statute of limitations in cases involving the federal tort claims act? LIMIT! /3 STATUTE ACTION /S FEDERAL /2 TORT /3 CLAIM ! = wildcard, /3 = dalam 3 kata, /S = dalam kalimat sama 28
Sec. 1.4
Contoh: www.westlaw.com Contoh query lain: Kebutuhan bagi penyandang cacat agar dapat mengakses tempat kerja disabl! /p access! /s work-site work-place (employment /3 place)
SPACE : disjungsi, bukan konjungsi! Query panjang (tepat); operator kedekatan; dikembangkan bertahap; tidak seperti pencarian web Banyak pencari pro masih menyukai pencarian Boolean: Tahu pasti apa yang diperoleh Tapi tidak berarti itu benar-benar bekerja lebih baik
Sec. 1.3
Query Boolean: Merge Lebih Umum Latihan: Sesuaikan gabungan untuk query: Brutus AND NOT Caesar Brutus OR NOT Caesar
Masihkah proses “merge” memerlukan waktu O(x+y)? Apa yang dapat dicapai?
30
Sec. 1.3
Penggabungan Bagaimana dengan formula Boolean yang berubahubah? (Brutus OR Caesar) AND NOT (Antony OR Cleopatra) Dapatkah selalu di”merge” dalam waktu “linier”? Linier dalam apa? Dapatkah dilakukan lebih baik?
31
Sec. 1.3
Optimisasi Query Bagaimana urutan terbaik untuk pemrosesan query? Pertimbangkan query berupa suatu AND dari n term. Untuk setiap n term, dapatkan postingnya, kemudian AND-kan bersama-sama. Brutus
2
Caesar
1
Calpurnia
4 2
8
16 32 64 128
3
5
8
16
21 34
13 16
Query: Brutus AND Calpurnia AND Caesar
32
Sec. 1.3
Contoh Optimisasi Query Proses dalam urutan frekuensi menaik: Mulai dengan set paling kecil, kemudian dilanjutkan ke depan. Inilah mengapa menyimpan frekuensi dokumen dalam dictionary
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. 33
Sec. 1.3
Optimisasi Lebih Umum Misal:
(madding OR crowd) AND (ignoble OR strife) Dapatkan frekuensi dokumen untuk semua term. Estimasi ukuran setiap OR dengan menjumlahkan frekuensi dokumenya (konservatif). Proses dalam urutan naik dari ukuran OR
34
Latihan... Tuliskan urutan pemrosesan query untuk: Term (tangerine OR trees) eyes AND (marmalade OR skies) kaleidoscope marmalade AND skies (kaleidoscope OR tangerine eyes) trees
Freq 213312 87009 107913 271658 46653 316812 35
Latihan Pemrosesan Query Latihan: Jika query adalah friends AND romans AND (NOT countrymen), bagaimana jika menggunakan frekuensi countrymen? Latihan : Perluas gabungan menjadi query Boolean tertentu. Dapatkah kita selalu menjamin eksekusi dalam waktu linier dalam total ukuran posting?
Hint: Mulai dengan query formula Boolean: setiap term query muncul hanya sekali dalam query. 36
Latihan... Coba fitur pencarian di http://www.rhymezone.com/shakespeare/ Tuliskan 5 fitur pencarian yang menurut anda dapat melakukan lebih baik
37
IR & Pencarian Lanjut... Bagaimana dengan frase? Stanford University
Kedekatan: Temukan Gates NEAR Microsoft. Perlu index untuk meng-capture informasi posisi dalam dokumen.
Zona dalam dokumen: Temukan dokumen dengan (author = Ullman) AND (teks mengandung automata).
38
Akumulasi Fakta 1 vs. 0 kehadiran term pencarian 2 vs. 1 kehadiran 3 vs. 2 kehadiran, dll. Biasanya tampak lebih baik
Perlu informasi frekuensi term dalam dokumen
39
Ranking Hasil Pencarian Query Boolean memberikan inklusi atau eksklusi dari dokumen. Sering hasilnya diranking/dikelompokkan Perlu mengukur kedekatan dari query ke setiap dokumen. Perlu memutuskan apakah dokumen yang disajikan kepada pengguna bersifat singleton (tunggal), atau kelompok dokumen yang mencakup berbagai aspek dari query.
40
IR vs. Database: Terstruktut vs Tak-Terstruktur Data terstruktur mengacu ke informasi dalam “tabel” Employee
Manager
Salary
Smith
Jones
50000
Chang
Smith
60000
Ivy
Smith
50000
Umumnya memungkinkan query range numerik dan sesuai tepat (untuk teks), misalnya:
Salary < 60000 AND Manager = Smith 41
Data Tak-Terstruktur Umumnya mengacu ke teks bebas Memungkinkan: Query Keyword dengan menyertakan operatoroperator Query “konsep” yang lebih canggih, misal: Temukan semua halaman web yang berkaitan dengan penyalahgunaan obat.
Model klasik untuk pencarian dokumen teks
42
Data Semi-Terstruktur Nyatanya hampir tidak ada data yang “takterstruktur” Misal: slide ini punya zona teridentifikasi dengan jelas seperti Title dan Bullets Menfasilitasi pencarian “semi-structured” seperti Title mengandung data AND Bullets mengandung search
43
Pencarian Semi-Terstruktur Lebih Canggih Title mengenai Object Oriented Programming AND Author menyerupai stro*rup Dimana * adalah operator wild-card Isu: Bagaimana memroses “mengenai”? Bagaimana meranking hasil?
Fokus dari pencarian XML (IIR, Bab 10)
44
Clustering, Klasifikasi & Ranking Clustering: Diberikan sehimpunan dokumen, kelompokkan mereka ke dalam cluster-cluster berdasarkan pada konten-nya.
Classification: Diberikan sehimpunan topik, kemudian muncul suatu dokumen baru D, tentukan topik mana yang akan diikuti oleh D.
Ranking: Bagaimana mengurutkan sehimpunan dokumen, misalnya himpunan hasil pencarian. 45
Web & Tantangannya Dokumen tidak biasa dan beragam Pengguna, query, kebutuhan informasi tidak biasa dan beragam Diluar dari term, menggali ide dari social networks link analysis, clickstreams ...
Bagaimana search engines bekerja? Dan bagaimana membuatnya lebih baik?
46
IR yang lebih Canggih
Cross-language information retrieval Question answering Summarization Text mining …
47
Resources Kuliah Hari ini... Introduction to Information Retrieval, Bab 1 Shakespeare: http://www.rhymezone.com/shakespeare/ Coba jelajah tertata dengan fitur deretan keyword!
Managing Gigabytes, Bab 3.2 Modern Information Retrieval, Bab 8.2
48
Pertanyaan?
49
Tugas Kerjakan latihan-latihan berikut: Exercise 1.2 Exercise 1.7 Exercise 1.10
Gunakan google dan yahoo. Coba beberapa query boolean. Catat hasil yang diberikan. Bandingkan! Jawaban tugas di upload ke blog masing-masing. Alamat blog Anda dituliskan di blog komputasi.wordpress.com, pada halaman STBI-2011 50
