stoplist dan stemming yasmi afrizal [email protected]
DESCRIPTION
Pertemuan ke- 3. StopList dan Stemming yasmi afrizal [email protected]. Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester G anjil 20 10 /201 1. Pertemuan ke- 3. Hukum Zipf. - PowerPoint PPT PresentationTRANSCRIPT
StopList dan StemmingStopList dan Stemming
yasmi afrizal yasmi afrizal [email protected][email protected]
Pertemuan ke-3
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
Hukum Zipf
Pertemuan ke-3
• Jika kata-kata di dalam suatu koleksi diranking, r, berdasarkan frekuensinya, f, maka memenuhi relasi:r × (f/n) = c
dimana n adalah jumlah kemunculan kata di dalam koleksi, 19 juta dalam contoh.
• Koleksi berbeda mempunyai konstanta c berbeda.
• Dalam teks bahasa Inggris, c sekitar 0.1.
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
Metode Hukum Zipf • Stop lists: Abaikan kata-kata yang sangat
sering (upper cut-off). Digunakan oleh hampir semua sistem.
• Significant words: Abaikan kata yang paling sering dan paling sedikit (upper and lower cut- off). Jarang digunakan.
• Term weighting: Berikan bobot berbeda untuk term-term berdasarkan pada frekuensinya, kata- kata yang paling sering dibobot kurang. Digunakan oleh hampir semua metode perankingan.
Pertemuan ke-3
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
Pandangan Logik Dokumen
• Representasi dokumen dipandang sebagai suatu continuum (rangkaian kesatuan).
Pertemuan ke-3
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
Arsitektur Sistem IR
Pertemuan ke-3
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
Arsitektur IR: Contoh
Pertemuan ke-3
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
Komponen Sistem IR
• Operasi Teks membentuk kata-kata indeks (token)– Tokenization (pemisahan kata)– Penghapusan Stopword (seperti ‘the’, ‘of’,
…)– Stemming (mengubah kata-kata berbeda ke
bentuk akarnya)• Indexing membangun suatu inverted index
dari kata ke penunjuk dokumen.– Pemetaan dari kata kunci ke Id dokumen.
Pertemuan ke-3
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
...Komponen Sistem IR
Pertemuan ke-3
• Searching meretrieve dokumen-dokumen yang mengandung token query yang diberikan dari inverted index.
• Ranking memberikan score kepada semua dokumen yang diretrieve sesuai dengan relevance metric.
• User Interface menangani interaksi dengan pengguna:– Input query dan output dokumen.– Feedback relevansi– Visualisasi hasil.
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
...Komponen Sistem IR • Operasi Query mentransformasi query untuk
meningkatkan retrieval:– Query expansion menggunakan thesaurus.– Query transformation menggunakan
feedback relevansi.– Optimisasi query untuk meningkatkan kinerja.
(kurang penting daripada dalam sistem data retrieval)
• Pertanyaan: bagaimana menambahkan suatu komponen personalisasi ke sistem IR?
Pertemuan ke-3
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
Pencarian Web
Pertemuan ke-3
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
• Aplikasi IR terhadap dokumen pada WWW • Perbedaan:
– Ukuran – lebih dari 25 milyar dokumen diindeks pada Google, terus bertambah
– Perubahan dokumen tidak dapat dikendalikan.– Harus menghimpun corpus dokumen dengan
menjaring (spidering) web.– Dapat mengeksploitasi informasi layout
struktural dalam HTML (XML).– Dapat mengeksploitasi struktur link dari web
Sistem Pencarian Web
Pertemuan ke-3
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
Area Terkait
Pertemuan ke-3
• Manajemen Basis Data• Ilmu Perpustakaan dan Informasi• Kecerdasan Buatan• Pemrosesan bahasa alamai• Pembelajaran Mesin
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
Relevansi• Relevansi merupakan suatu judgment
(keputusan) subyektif dan dapat didasarkan pada:– topik yang tepat.– waktu (informasi terbaru).– otoritatif (dari suatu sumber terpercaya).– kebutuhan informasi dari pengguna.
• Kriteria relevansi utama: suatu sistem IR sebaiknya (harus) memenuhi kebutuhan informasi pengguna.
Pertemuan ke-2
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
Pencarian Keyword
• Ide paling sederhana dari relevansi: apakah string query ada di dalam dokumen (kata demi kata, verbatim)?
• Ide yang lebih fleksibel: Berapa sering kata-kata di dalam query muncul di dalam dokumen, tanpa melihat urutannya (bag of words)?
Pertemuan ke-2
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
Masalah dengan Keyword
• Mungkin tidak meretrieve dokumen relevan yang menyertakan synonymous terms.– “restaurant” vs. “café”– “NDHU” vs. “National Dong Hwa
University”• Mungkin meretrieve dokumen tak-relevan
yang menyertakan ambiguous terms.– “bat” (baseball vs. mamalia)– “Apple” (perusahaan vs. buah-buahan)– “bit” (unit data vs. perilaku menggigit)
Pertemuan ke-2
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
Bukan Sekedar Keyword
• Kita akan mendiskusikan dasar-dasar IR berbasis keyword, tetapi…– Fokus pada perluasan dan pengembangan
terakhir untuk mendapatkan hasil terbaik.• Kita akan membahas dasar-dasar pembangunan
sistem IR yang efisien, tetapi…– Fokus pada algoritma dan kemampuan dasar,
bukan masalah sistem yang memungkinkan pengembangan ke database ukuran industri.
Pertemuan ke-2
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
IR Cerdas
• Memanfaatkan pengertian atau makna dari kata yang digunakan.
• Melibatkan urutan kata di dalam query.• Beradaptasi dengan pengguna berdasarkan
pada feedback, langsung atau tidak langsung.• Memperluas pencarian dengan term terkait.• Mengerjakan pemeriksaan ejaaan/perbaikan
tanda pengenal otomatis.• Memanfaatkan Otoritas dari sumber informasi.
Pertemuan ke-2
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
Indeks • Sistem IR jarang mencari koleksi dokumen secara
langsung. Berdasarkan pada koleksi dokumen, dibangun sebuah index. Pengguna mencari index tersebut.
Pertemuan ke-2
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
Indexing Otomatis
• Tujuan dari automatic indexing adalah membangun index dan meretrieve informasi tanpa intervensi manusia.
• Ketika informasi yang dicari adalah teks, metode automatic indexing akan sangat efektif.
• Penelitian automatic indexing fundamental dimulai oleh Gerald Salton, Professor of Computer Science di Cornell & mahasiswa Pasca-Sarjananya (Sistem SMART).
Pertemuan ke-2
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
IR dari Koleksi Besar
• Information retrieval dari koleksi sangat besar bersandar pada:– Jumlah computer power yang besar untuk
mengerjakan algoritma sederhana terhadap jumlah data yang sangat banyak.
• komputasi kinerja-tinggi– Pemahaman pengguna terhadap informasi dan
kemampuan dari sistem.• Interaksi manusia - komputer• Machine-learning banyak digunakan untuk
mendapatkan kinerja terbaik.
Pertemuan ke-2
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
Searching & Browsing
Pertemuan ke-2
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
• Orang dalam perulangan
IR dari Koleksi Dokumen Teks
• Kategori utama dari metode:– Ranking kemiripan terhadap query (vector
space model).– Pencocokan exact (Boolean).– Ranking berdasarkan tingkat kepentingan
dokumen (PageRank)– Kombinasi beberapa metode
• Contoh: Web search engine, seperti Google & Yahoo, menggunakan metode kombinasi, berdasarkan pada pendekatan pertama dan ketiga, dengan kombinasi exact dipilih menggunakan machine learning
Pertemuan ke-2
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
Istilah Penting • Information retrieval: sub-bidang ilmu
komputer yang berurusan dengan penemuan kembali dokumen (khususnya teks) terotomatis berdasarkan pada content dan contextnya.
• Searching: Pencarian informasi spesifik di dalam badan informasi. Hasilnya adalah sehimpunan hit.
• Browsing: Eksplorasi tak-terstruktur dari badan informasi.
• Linking: Berpindah dari satu item ke item lain mengikuti link (sambungan) seperti rujukan (referensi).
Pertemuan ke-2
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
...Istilah• Query: Suatu string teks, menggambarkan
informasi yang sedang dicari pengguna. Setiap kata dari query dinamakan search term.
• Query dapat berupa search term tunggal, string dari term, frase atau ekspresi tertentu menggunakan simbol khusus, misalnya regular expression.
• Pencarian Full text: Metode yang membandingkan query dengan setiap kata di dalam teks, tanpa membedakan fungsi dari berbagai kata.
• Pencarian Bidang : Metode pencarian pada bidang struktural atau bibliografis spesifik, seperti penulis atau judul.
Pertemuan ke-2
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
...Istilah
• Corpus: Koleksi dokumen yang diindeks dan dijadikan target pencarian.
• Daftar kata: Himpunan semua term yang digunakan dalam indeks untuk suatu corpus (dikenal sebagai vocabulary file).
• Pada pencarian full text, word list adalah semua term di dalam corpus, stop words dihapus. Term- term terkait dikombinasi dengan stemming.
• Controlled vocabulary: Metode indexing dimana word list bersifat tetap. Term-term dari vocabulary tersebut dipilih untuk mendeskripsikan setiap dokumen.
• Keyword: Nama untuk term-term dalam word list, terutama dengan controlled vocabulary
Pertemuan ke-2
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
Mengurutan & Ranking Hit
• Ketika pengguna men-submit suatu query ke sistem IR, sistem mengembalikan sehimpunan hit. Pada koleksi dokumen besar, himpunan hit akan sangat besar.
• Nilai untuk pengguna sering tergantung pada urutan hit ditampilkan.
• Tiga metode utama:– Mengurutkan hit, misal berdasarkan tanggal– Meranking hit berdasarkan kemiripan antara
query dan dokumen– Meranking hit berdasarkan kepentingan dari
dokumen
Pertemuan ke-2
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
IR Berbasis Teks
• Sebagian besar metode ranking didasarkan pada model ruang vektor (vector space model).
• Sebagian besar metode pencocokan (matching) didasarkan ada operator Boolean.
• Metode Web search mengkombinasikan model ruang vektor dengan ranking berdasarkan pada tingkat kepentingan dokumen.
• Banyak sistem (dalam praktek) menggabungkan fitur- fitur dari beberapa pendekatan.
• Pada bentuk dasar, semua pendekatan menganggap kata sebagai token terpisah, dengan usaha minimal untuk memahami kata-kata secara linguistik.
Pertemuan ke-2
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
FrekuensiKata
• Observasi: Beberapa kata lebih umum daripada yang lain.
• Statistika: Koleksi sangat besar dari dokumen teks tak-terstruktur mempunyai karakteristik statistik serupa. Statistik ini:– Mempengaruhi efektifitas dan efisiensi
dari struktur data yang digunakan untuk mengindeks dokumen
– Banyak model retrieval memanfaatkannya
Pertemuan ke-2
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
...Frekuensi Kata
• Contoh: Contoh berikut ini diambil dari :– Jamie Callan, Characteristics of Text,
1997– 19 Juta kata sampel– Slide berikut memperlihatkan 50 kata
yang paling umum, diranking (r) berdasarkan frekuensinya (f).
Pertemuan ke-2
Jurusan Teknik Informatika Universitas Ahmad Dahlan Semester Ganjil 2010/2011
...Frekuensi Kata
Pertemuan ke-2
Distribusi RankingFrekuensi
• Untuk semua kata di dalam suatu dokumen, untuk setiap kata w– f adalah frekuensi munculnya w– r ranking dari w disusun menurut frekuensi. (kata
yang paling umum muncul mempunyai rank =1)
Pertemuan ke-2
Contoh Frekuensi Rank
• Slide berikut memperlihatkan kata-kata di dalam data Callan yang telah dinormalisasi. Dalam contoh ini:– r adalah ranking dari kata w
dalam sampel.– f adalah frekuensi kata w di dalam
sampel.– n adalah jumlah total kemunculan
kata di dalam sampel.
Pertemuan ke-2
...Contoh RankingFrekuensi
Pertemuan ke-2