Temu-Kembali Informasi 2017

Temu-Kembali Informasi 2017 Proyek Pemrograman Terpadu (Tiga Tahapan)

Husni [email protected]

Proyek Pemrograman #1 Husni

Proyek Pemrograman #1: Indexing • Sasaran (goal): membangun suatu inverted index untuk suatu koleksi dokumen teks • Input: sehimpunan dokumen teks • Output: inverted index • Tools: dengan memanggil fungsi-fungsi dalam pustaka (atau API) open source atau menulis kode sendiri dari awal menggunakan bahasa pemrograman tertentu (Python, Java dan R adalah bahasa yang banyak digunakan di bidang temu-kembali Informasi)

No PHP

Query

User Interface

Caching Pages Indexing & Ranking

Sisi Online Sisi Offline Inverted Index

Ranking Halaman

Analisa Tautan

Pembangkit Graf Web

Graf Web

Pembangkit Index Kata

Statistika Situs & Halaman

Tautan & Anchors

Pengurai Halaman Halaman

Halaman Tersimpan

Crawler

Internet

Diagram Proyek #1 dan #2

#1

#2

Diagram Proyek #3

Contoh Klasifikasi Teks

Beberapa Tool Indexing Open Source • Apache Lucene (dalam Java) • The Lemur Project: Indri – dari CMU/Umass (dalam C++) • Terrier IR Platform – dari U. Glasgow (dalam Java) •… • https://www.datacamp.com/community/blog/text-mining-in-r-andpython-tips

Buku Python & R untuk Retrieval ☺

Input: Koleksi Dokumen Uji • Korpora berita Reuters (RCV1, RCV2, TRC2) http://trec.nist.gov/data/reuters/reuters.html • • • •

RCV1: ~810,000 cerita berita English dari 1996/08/20 s.d 1997/08/19 (2.5GB tidak dipadatkan) RCV2: 487,000 berita banyak-bahasa dalam 13 bahasa TRC2: 1,800,370 berita dari 2008/01/01 s,d 2009/02/28 (2.87GB) Harus menandatangani kesepakatan.

• Reuters-21578: http://www.daviddlewis.com/resources/testcollections/reuters21578/ • 21,578 news articles in 1987 (28.0MB tanpa kompressan) • Tersedia bagi publik

• Koleksi uji di University of Glasgow: http://ir.dcs.gla.ac.uk/resources/test_collections/ • Tersedia bagi publik: LISA, NPL, CACM, CISI, Cranfield, Time, Medline, ADI • Contoh: Koleksi Time: 423 artikel dari majalah Time (1.5MB)

Output: Inverted Index • Format Output: menggunakan Indeks Berposisi Standar (sebagaimana dibahas dalam Bab 1 dan 2): • File Kamus: daftar kosakata yang diurutkan (dalam baris-baris terpisah) • Daftar Posting: untuk setiap term, daftar kemunculan dalam teks asli • Format: (seperti dalam gambar 2.11) termi, dfi: <doc1, tfi1: <pos1, pos2, … >; doc2, tfi2: <pos1, pos2, …>; …> • Contoh: to, 993427: <1, 6: <7, 18, 33, 72, 86, 231>; 2, 5: <1, 17, 74, 222, 255>; … >

dfi: frekuensi dokumen dari termi tfij: frekuensi term dari termi dalam docj

Persoalan Rancangan • pos berarti posisi token di dalam body dari dokumen • Ini mempermudah penerapan langkah-langkah berikut, misalnya, penelusuran kedekatan

• Anda dapat merancang format indeks sendiri, selama informasi yang diperlukan disertakan • Kamus: term ti, frekuensi dokumen dfi • Posting: daftar (docID, frekuensi term tfij, lokasi) untuk setiap term ti

• Preprocessing harus ditangani secara cermat • Format input dari koleksi data • Tunjukkan bagaimana penanganan digit, tanda hubung, tanda baca, ... dalam tokenisasi.

Fungsionalitas Opsional • Persoalan Efisiensi • Struktur data terpisah (misalnya tree) dapat digunakan untuk menyimpan kosakata dan posting di Indexer • Skip pointer (digunakan dalam pemrosesan query)

• Tokenization • • • •

Case folding > ubuah ke huruf kecil Penghapusan Stopword > hapus semua kata-kata yang kurang bermakna Stemming > kembalikan kata ke bentuk akarnya Dapat diaktifkan atau dimatikan oleh suatu parameter pemicu (trigger)

Pengumpulan Hasil • Hasil proyek ini dikirimkan ke email [email protected], berisi: • Kode program lengkap (source codes) • Untuk pemanggilan library open source, tunjukkan API atau fungsi pustaka apa saja yang diperlukan dan instruksi dimana mendownloadnya dan bagaimana instalasi, konfigrasi dan kompilasinya.

• Dokumentasi 3 halaman, termasuk: • Fitur-fitur utama: misalnya efisien tinggi, storage kecil, format input beragam, korpus besar, … • Arsitektur dari sistem (gambar dan penjelasan cara kerjanya) • Kesulitan besar yang ditemui • Instruksi instalasi/kompilasi/konfigurasi/lingkungan eksekusi (misal: Java Runtime,…) • Daftar anggota tim: Nama dan bagian yang menjadi tanggungjawab masing-masing anggota (harus jelas)

• Waktu: 3 pekan (Deadline: 30 Oktober 2017)

Evaluasi • Requirement minimum: ketepatan index terhadap data test • Menggunakan Koleksi Uji Reuters-21578 sebagai input, inverted index dibangkitkan oleh program yang dibuat akan diperiksa • Fitur-fitur tambahan akan dipertimbangkan sebagai bonus

• Anda diharuskan mendemokan program tersebut jika program yang dikirimkan via email tidak dapat dikompilasi atau dijalankan.

Proyek Pemrograman #2 Husni

Proyek Pemrograman #2: Pemrosesan Query & Pencarian • Sasaran (goal): mencari dokumen-dokumen yang relevan dengan query yang diberikan pengguna • Input: suatu query (dan inverted index dari proyek #1) • Output: Suatu daftar teranking hasil pencarian dari koleksi Reuters21578 • (rincinya dijelaskan nanti)

Input: Query Pengguna & Inverted Index • Query sederhana • Kata kunci tunggal • Misal: Microsoft, komputer, …

• Teks bebas • Misal: Republik Indonesia, lembaga swadaya masyarakat, …

• Pencarian Boolean sederhana • Misal: open source AND Linux, software engineer OR project manager, …

• Inverted Index • Yang dihasilkan dari Proyek Pemrograman #1

Output: Hasil Pencarian Teranking • Suatu daftar hasil pencarian yang telah teranking dari koleksi uji Reuters-21578 • Ranking: Model Ruang Vektor (VSM = vector space model) • Skema pembobotan Term: TF-IDF • Estimasi kemiripan: cosine similarity antara vektor query dan vektor dokumen wij = (1+ log tfij) * log (N/dfi)

 d j  ( w1, j , w2, j ,, wt , j )  q  ( w1,q , w2,q ,, wt ,q )

  d j q sim(d j , q)    | dj || q |

 w w  w   t



i 1

t

i 1

2 i, j

i, j

i ,q t

2 w i 1 i , q

Output • Contoh: • Query: “Republik Indonesia” • Hasil: <doc#> <skor kemiripan> • 261 135 324 …

0.85 0.67 0.3

Fitur-fitur Opsional • Fungsi Tambahan • Antarmuka yang lebih baik untuk pencarian • Query kompleks: frasa, wildcard, substring, pencarian kedekatan, kombinasi operator boolean, … (Bab 2 & 3) • Pemrosesan Query: pembetulan ejaan, pembetulan fonetik, … (Bab 3) • Skema pembobotan term berbeda: varian dari TF-IDF, … (Bab 6) • Temu-kembali top-k tidak eksak: eliminasi index, daftar juara, pengurutan dampak, indeks berjenjang, … (Ch.7) • Dapat diaktifkan atau dimatikan dengan trigger parameter.

Pengumpulan Hasil • Hasil proyek ini dikirimkan ke email [email protected], berisi: • Kode program lengkap (source codes) • Untuk pemanggilan library open source, tunjukkan API atau fungsi pustaka apa saja yang diperlukan dan instruksi dimana mendownloadnya dan bagaimana instalasi, konfigrasi dan kompilasinya.

• Dokumentasi 2 halaman, termasuk: • Fitur-fitur utama: misalnya efisien tinggi, storage kecil, format input beragam, korpus besar, … • Arsitektur dari sistem (gambar dan penjelasan cara kerjanya) • Kesulitan besar yang ditemui • Instruksi instalasi/kompilasi/konfigurasi/lingkungan eksekusi (misal: Java Runtime, …) • Daftar anggota tim: Nama dan bagian yang menjadi tanggungjawab masing-masing anggota (harus jelas)

• Waktu: 3 pekan (Deadline: 21 Nopember 2017)

Evaluasi • Requirement minimum: ketepatan penanganan query simpel • Beberapa query contoh dari Koleksi Uji Reuters-21578 disubmitkan ke program anda, dan daftar teranking yang dihasilkan diperiksa ketepatannya

• Fitur opsional akan dipertimbangkan sebagai bonus • Variasi jenis query, skema pembobotan, efisiensi penskoran dan ranking, …

• Anda diharuskan mendemokan program tersebut jika program yang dikirimkan via email tidak dapat dikompilasi atau dijalankan.

Proyek Pemrograman #3 Husni

Proyek Pemrograman #3: Klasifikasi Teks • Goal: mengklasifikasikan dokumen teks ke dalam kategori yang telah didefinisikan • Input: koleksi uji Reuters-21578 • Kategori-kategori yang telah ditetapkan • Dokumen-dokumen yang sudah diberi label (untuk training) • Dokumen uji untuk pengujian (testing)

• Output: classifier untuk setiap kategori, dan hasil klasifikasi terhadap dokumen uji.

Input: Himpunan Training dan Test • Mengggunakan koleksi Reuters-21578 • Tersedia di:

http://kdd.ics.uci.edu/databases/reuters21578/reuters21578.html • 21,578 artikel berita tahun 1987 (28.0MB tidak dipadatkan)

• Didistribusikan dalam 22 file dalam format SGML • Preprocessing dari tag-tag SGML • Format file: http://kdd.ics.uci.edu/databases/reuters21578/README.txt

Kategori Telah Terdefinisi dalam Reuters-21578 • 5 himpunan kategori • • • • •

Exchanges: 39 categories Orgs: 56 categories People: 267 categories Places: 175 categories Topics: 135 categories

 Dalam proyek ini, kita HANYA melibatkan klasifikasi 135 kategori berdasarkan topik (135 topical categories) • 10 kelas terbesar • Earn, acquisitions, money-fx, grain, crude, trade, interest, ship, wheat, corn

Himpunan Training dan Test • Menggunakan Reuters-21578 untuk klasifikasi teks • Modified Lewis (ModLewis) Split • Training: 13,625 • Test: 6,188

• Modified Apte (ModApte) Split: digunakan dalam proyek ini • Training: 9,603 • Test: 3,299 • Modified Hayes (ModHayes) Split • Training: 20,856 • Test: 722

Contoh Artikel Reuters

Training set dalam pembagian ModApte

26-FEB-1987 15:01:01.79 Kategori cocoa Berdasar el-salvadorusauruguay kan Topik …  <TITLE>BAHIA COCOA REVIEW SALVADOR, Feb 26 - Showers continued throughout the week in Isi Teks … 

Output Fase Training: suatu Classifier • Tulis program anda sendiri atau panggil fungsi pustaka open source untuk mewujudkan setidaknya satu dari metode klasifikasi teks berikut: • Probabilistic classifier: Naïve Bayes (NB) (Bab 13) • Vector space classifiers: Rocchio classification (Bab 14), kNN classification (Bab 14) • SVM classification (Bab 15) •…

Sec.14.1

Dokumen Uji dari Kelas Apa?

Government Science Arts

33

Contoh: Klasifikasi Rocchio • Definisi dari centroid

1 (c)  v (d)  | Dc | d Dc

• Dimana Dc Adalah himpunan semua dokumen yang masuk ke kelas c dan v(d) adalah representasi ruang vector dari d. • Training: Kalkulasicentroids (vektor prototype) dari semua kategori

• Testing: menempatkan dokumen uji ke kategori dengan centroid terdekat berdasarkan pada cosine similarity

Proyek & Evaluasi • Sistem anda harus mampu menyelesaikan tugas-tugas berikut menggunakan pembagian ModApte dalam datasat Reuters-21578: • Pelatihan (training) Classifier • Pengujian (Testing klasifikasi) • Evaluasi hasil

• Evaluasi dari classifier anda • Training: Efisiensi • Testing: precision/recall/F-measure

Contoh: Klasifikasi Rocchio Training

Centroid Calculation

Training docs

centroids

HTML Parsing Cosine Similarity

Test doc.

Evaluation

Testing

P, R, F1

class

Tahapan (Contoh) dalam Klasifikasi Rocchio 1. Uraikan dokumen HTML dalam dataset Reuters-21578. Dapatkan text body, topics, dan pisahkan mereka ke dalam dokumen training dan test. •

Body sebagai isi, topics sebagai kelas

2. Untuk setiap dokumen, hitung bobot TF-IDF dari teks body sebagai suatu vektor. 3. Untuk setiap dokumen training, hitung centroid dengan menjumlahkan semua vektor dalam setiap kelas topik. • Sehingga anda akan mendapatkan 135 centroid, satu untuk setiap kelas topik.

4. Untuk setiap dokumen uji, dapatkan centroid paling mirip menggunakan cosine similarity sebagai kelas yang akan jadi tujuannya. 5. Bandingkan kelas tersebut dengan jawaban sebenarnya (dalam tag topics), dan evaluasi berapa banyak dokumen uji yang terklasifikasi dengan benar.

Fungsionalitas Opsional • Seleksi fitur: (Sub-bab 13.5) • mutual information • chi-square • …

• Himpunan data training/test berbeda • Berbeda pembagain dalam dataset Reuters • Koleksi uji yang lain

• Metode klasifikasi berbeda • Naïve Bayes, kNN, SVM, …

• Antarmuka pengguna untuk klasifikasi • Untuk pemilihan himpunan data training/test • Untuk pemilihan metode klasifikasi

• Visualization dari hasil klasifikasi •…

Pengumpulan Hasil • Hasil proyek ini dikirimkan ke email [email protected], berisi: • Kode program lengkap (dan file executable-nya) • Manual pengguna lengkap (atau UI) untuk training/testing • Dokumentasi 2 halaman, termasuk: • Fitur-fitur utama: misalnya efisien tinggi, storage kecil, format input beragam, korpus besar, … • Arsitektur dari sistem (gambar dan penjelasan cara kerjanya) • Kesulitan besar yang ditemui • Instruksi instalasi/kompilasi/konfigurasi/lingkungan eksekusi (misal: Java Runtime, …) • Daftar anggota tim: Nama dan bagian yang menjadi tanggungjawab masing-masing anggota (harus jelas)

• Waktu: 3 pekan (Deadline: 15 Desember 2017)

Evaluasi • Requirement minimal – dua pilihan: • Pemilihan otomatis: Secara otomatis mengklasifikasi semua dokumen uji dalam ModApte, dan menampilkan hasil evaluasi terhadap efektifitas klasifikasi tersebut (precision, recall, F-measure, akurasi) • Pemilihan secara acak beberapa dokumen uji (berdasarkan ID-nya), dan menampilkan hasil klasifikasinya (output dari classifier anda dan jawaban seharusnya)

• Fitur opsional akan dianggap sebagai bonus • Pemilihan fitur, himpunan data training/test berbeda, metode klasifikasi berbeda, UI, visualisasi, …

• Anda diharuskan mendemokan program tersebut jika program yang dikirimkan via email tidak dapat dikompilasi atau dijalankan.

Ada Pertanyaan atau Komentar?