Sistem Temu-Kembali Informasi Garis Besar IR & RS Husni Program Studi Teknik Informatika Universitas Trunojoyo Madura
Semeter Gasal 2015 - 10 Sep. 2015
Outline • • • •
Definisi & Arsitektur Information Retrieval Pencarian Web dan Search Engine Information Overload Recommender System
2
Temu-Kembali Informasi... • Temu-Kembali Informasi atau Information Retrieval (IR) berurusan dengan representasi, penyimpanan dan organisasi data tidak terstruktur • IR adalah proses pencarian di dalam suatu koleksi dokumen untuk kebutuhan informasi tertentu (berbentuk query) • Misi IR: membantu pencarian informasi • Dua paradigma utama dalam pencarian: – Retrieval – Browsing 3
Retrieval & Browsing • x
4
Aktifitas Pencarian • Retrieval – Pencarian informasi khusus – Biasanya fokus dan dengan maksud tertentu
• Browsing – Melihat atau menjelajah informasi secara bertingkat – Contoh: Asia-> Indonesia -> Madura -> Pantai -> Camplong
5
Search Engine Mesin Pencarian
• Search engines: perangkat utama yang digunakan untuk mendapatkan informasi di web (Internet) • Mengeluarkan suatu situs dari search engines akan menghentikan situs tersebut 6 dari audien yang diharapkan.
Arsitektur Sistem IR • x
7
Sejarah Search Engines • • • • • •
• • •
Yahoo! (1994-) directory service dan search engine. Infoseek (1994-2001) search engine. Inktomi (1995-) infrastruktur search engine, dibeli Yahoo! 2003. AltaVista (1995-) search engine, dibeli Overture 2003. Ask Jeeves (ask.com, 1996-) Q&A dan search engine, dibeli IAC/InterActiveCorp 2005. Overture (1997-) pay-per-click search engine, dibeli Yahoo! 2003. Google (1998-) search engine. AlltheWeb (1999-) search engine, dibeli Overture 2003 . Bing (bing.com, 2009-) Microsoft search engine (reinkarnasi?) , sebelumnya Live (2006) dan MSN. 8
Statistika Search Engine • Di Amerika, pada 2005 Google memperoleh 36.5%, terus mendominasi. Juli 2015, 64% dari 18 jutaan pencarian. Terjadi penurunan mulai awal 2014 (1 – 2%). Bing 20.4%, Yahoo 12.7%. • Di China dan Korea: Engine lokal lebih populer. • Market share global: Google 70.38%
9
Statistika Pencarian Tahunan Google • 66,435 query per detik
10
Web IR: IR di Web • Generasi Pertama – Pendekatan klasik: model boolean, vektor dan probabilistik – Informational: Teknik IR/DB pada isi halaman, misal: Lycos, Excite, AltaVista
• Generasi Kedua – Web sebagai suatu graf – Navigational: menggunakan data spesifik web: Topologi Link. Contoh: Google
• Generasi Ketiga – – – –
Penelitian terbuka Pencarian informasi mobile (bergerak) Pencarian dalam jejaring sosial Banyak potensi bisnis, jasa (layanan) pencocokan
11
Masalah IR di Web • Koleksi yang sangat besar dan heterogen: – Dinamis – Self-organized (dikelola sendiri) – Hyperlinked (terhubung dengan link/URL) • Query yang sangat pendek • Pengguna tidak normal • Sulit menentukan relevansi dan ranking hasil (tergantung pada konteks dan subjektif) • Synonymy dan ambiguity • Gaya kepengarangan (dalam penulisan isi dan formulasi query) • Kepercayaan SE, pemuatan keyword: daftar kata kunci dimasukkan ke dalam tag meta atau body dari halaman web. 12
IR: Konsep Dasar • Pengguna membutuhkan informasi: diekspresikan sebagai query teks bebas • Kebutuhan informasi : the perceived need for information that leads to someone using an information retrieval system in the first place [Schneiderman dkk. 1997] • Query menyandikan kebutuhan pencari informasi • Query adalah suatu dokumen untuk dibandingkan dengan koleksi dokumen (file atau database informasi) • Efektifitas vs. Efisiensi • Bagaimana membandingkan dokumen? Perlu metrik kemiripan (similarity ) • Bagaimana menghindari pencarian sequential? Dapatkah pencarian dilakukan dalam banyak server? 13
Dari Kebutuhan menjadi Query • Kebutuhan Informasi -> Query -> Search Engine -> Hasil -> Browse OR Query -> ...
Kebutuhan Informasi
Diterjemahkan oleh Pengguna ke dalam suatu Query
14
Taxonomy Pencarian Web • Dalam konteks web kebutuhan dibalik query sering tidak informational • [Broder, 2002] ada 3 maksud dari suatu query: 1. Navigational: Langsung menuju situs tertentu (20%): – q = facebook http://www.facebook.com ? 2. Informational: Informasi yang disediakan oleh satu atau lebih halaman web (50%) – q= lenovo Z475 informasi tentang lenovo Z475 3. Transactional: Mengerjakan aktifitas web-mediated (30%) – q = hotel Bandara Traveloka? – q = email google gmail? 15
Pencarian Exploratory • x
[Marchionini, 2006]
16
Proses Pencarian Informasi • x
17
Matriks Penemuan Informasi
18
http://techcrunch.com/2011/03/03/the-age-of-relevance/
Strategi dan Perangkat • Search engine hanya tool (diantara yang lain) yang dapat dimanfaatkan, dalam suatu strategi, untuk mencapai tujuan (mengerjakan suatu tugas) • Tools baru telah muncul dan terus dikembangkan, menggabungkan kerja di bidang Human Computer Interaction (HCI) dan IR • Pencarian Exploratory adalah area dimana tools baru akan banyak dikembangkan.
19
Antarmuka Pencarian Informasi • • • •
Design Search User Interfaces Evaluate Search User Interfaces Models of the Information Seeking Process Search Interfaces Fundamentals: – Query Specification – Presentation of Search Results – Query Reformulation
• Advanced Topics, including: – – – – – –
Integrating Navigation with Search Personalization in Search Information Visualization Mobile Search Social Search Multimedia Search 20
Pemakaian Mobile • Share of Digital Media Time Spent: Desktop Computer vs. Mobile (Smartphone + Tablet) • Source: comScore Media Metrix Multi-Platform (Beta), U.S., Dec-2012
21
Pemakaian Mobile • Share of Browser-Based Page Traffic by Hour for Computer, Smartphone and Tablet Platforms • Source: comScore Device Essentials, U.S., Monday, Jan. 21, 2013
Pengguna menyelesaikan pekerjaan informasi dengan menggunakan banyak perangkat
22
Waktu Pemakaian Media Digital • Pemanfaatan perangkat mobile meningkat, +44% pemakaian aplikasi mobile dan +38% penggunakan web mobile • Pemanfaatan desktop stabil
23
Pencarian Exploratory: Pencarian Mobile • Pengguna dapat menjelajah (browse) pencarian (query dan hasilnya) yang dikerjakan oleh pengguna lain dalam suatu lokasi.
24
Sekarang... • Informasi yang benar di waktu yang tepat
25
Pencarian Exploratory liveplasma.com
26
Penemuan Informasi musicovery.com
27
Musicovery Mobile
28
Pencarian Exploratory Linkedin People
29
Vivisimo
30
Search Engine Dinamis
31
Fitur Pencarian Informasi • Tidak ada suatu strategi atau tool terbaik untuk mencari informasi • Strategi tergantung pada: – – – –
Sifat dari informasi yang dicari oleh pengguna, Sifat dan struktur dari repository (gudang) content, Tool pencarian yang tersedia, Kebiasaan pengguna dengan informasi dan terminologi yang digunakan dalam repo, – Kemampuan pengguna menggunakan tool pencarian secara kompeten. 32
Pencarian Informasi & Pembuatan Keputusan • Information Search (IS) dan Decision Making (DM) sangat berkaitan • IS untuk DM: kita mencari informasi (Eksternal & Internal) sebelum menyambil keputusan – Klasik dalam DM dan perilaku pengguna
• DM untuk IS: kita harus membuat keputusan mengenai informasi apa yang diperlukan atau kapan menghentikan pencarian – Fitur baru dari Web, disebabkah oleh Information Overload. 33
Information Overload • Internet = information overload: melimpah-ruahnya informasi sehingga menyulitkan pengambilan keputusan • Teknologi IR dasar dapat membantu mencarikan content
jika pengguna mengetahui pasti apa yang dicari • Perlu pencarian exploratory untuk dapat membuat keputusan terbaik (perbandingan, akuisisi pengetahuan, pemilihan produk, dll.), karena: – Tidak tahu cakupan pilihan yang tersedia – Tidak tahu apa yang dicari – Tidak mampu memilih meskipun telah diberikan hasil pencarian. 34
Neuroscience dan Information Overload • Neuroscientists menemukan ketidakproduktifan dan keterpakuan diri dikarenakan decision overload • Otak dikonfigurasi untuk membuat sejumlah pasti keputusan per hari dan sulit untuk melebihi batas tersebut • Pengolahan informasi berbiaya tinggi: memisahkan yang gampang dari yang penting merupakan pekerjaan berat, membuat otak letih • Kapasitas pemrosesan dari pikiran/akal sadar diestimasi 120 bits per detik. 35
Perhatian • Perhatian (attention): sumber daya sangat esensial bagi organisme. • Jutaan neuron (attentional filters) secara konstan memonitor lingkungan untuk memilih hal-hal paling penting sebagai fokus • Orang sukses (yang dapat mengusahakannya) memanfaatkan orang lain untuk mempersempit attentional filter (misal: sekretaris) • Kebanyakan orang cenderung membiarkan pikirannya berjalan liar dan ber-siklus melalui kebanyakan pikiran (Did I close the door? Did I filed the request?). 36
Prinsip Attentional Filters • Perubahan: Otak adalah detektor perubahan sangat hebat • Ketika suatu perubahan terdeteksi, informasi dikirim ke pikiran sadar. – Contoh: seorang teman menelpon, jika suaranya terdengar aneh maka anda menanyakan apakah dia baik-baik saja?
• Kepentingan: sesuatu yang secara personal penting akan berjalan melewati attentional filter – Contoh: dalam ruangan yang crowded terdengar kata-kata yang sangat penting dan anda dengan seketika dapat mengikuti percakapan tersebut.
• Inattentional blindness basketball demo 37
Recommender Systems • Sehari-hari, kita bersandar pada rekomendasi dari orang lain, baik berbentuk ucapan, surat, review buku dan film di majalah, dll… • Dalam recommender system (RS), orangorang menyediakan rekomendasi sebagai input, sistem kemudian mengumpulkan dan mengarahkan ke penerima yang tepat – Pengumpulan rekomendasi – Mencocokkan rekomendasi tersebut dengan melakukan pencarian 38
Recommenders dan Search Engines • SE bukan RS • Meng-query rekomendasi ke SE akan memperoleh sedaftar RS
39
Amazon.com
40
Skenario Mobile • Google Play?
41
Rekomendasi Linked-In
42
Rekomendasi Facebook
43
Komputasi Inti Recommender Systems • Prediksi Rating: Model harus dibangun untuk memprediksi rating (nilai) bagi item-item yang belum dinilai (rate) oleh pengguna – Rating numerik: regresi – Rating diskret: klasifikasi
• Ranking: Skor bagi setiap item dihitung dan item diranking mengikuti skor tersebut (seperti pada SE) – “Lebih simpel” hanya mengurutkan (tidak merating)
• Tugas Pemilihan: model harus dibangun untuk memilih N item paling relevan dan baru bagi pengguna – Proses pasca prediksi rating /ranking, diterapkan strategi evaluasi tertentu.
44
Ide Collaborative Filtering • Memperkirakan pendapat “masa depan” pengguna terhadap item-item tertentu dan merekomendasikan “item terbaik” kepada pengguna berdasarkan apa yang disukai pengguna tersebut sebelumnya dan pendapat pengguna lain yang berpikiran serupa • Collaborative Filtering (CF) hadir setelah content-based tetapi menjadi metode paling terkenal • CF merupakan aplikasi internet umum – harus didukung oleh infrastruktur jaringan – Pemanfaatan banyak server – Setidaknya banyak pengguna dalam satu server
• Tidak ada aplikasi CF yang standalone 45
Movielens: Pemberian Rating
46
Movielens: Rekomendasi
47
Matriks Rating
48
Collaborative Filtering • Koleksi n pengguna U dan koleksi m item I • Matriks rating rui berukuran n × m , dengan rui = ? Jika pengguna u tidak menilai item i. • Prediksi untuk pengguna u dan item j dihitung sebagai Himpunan tetangga u yang telah menilai j
• Dimana, ru adalah rata-rata rating dari pengguna u, K adalah faktor normalisasi sehingga nilai absolut dari sum wuv 1, dan Korelasi pearson dari pengguna u dan v 49
Topik dalam Recommender Systems • • • • • • • • • • •
Prediction Algorithms Evaluation methodologies System deployment and Integration Method selection Conversational systems Persuasion Recommendation presentation and explanations Social computing Trust Preference elicitation and active Learning Robustness and security 50
Tantangan dalam Recommender Systems • • • • • • • • • • •
Skalabilitas algoritma dengan data set besar dan real-world Recommender proactive Recommender yang menjaga privasi Keanekaragaman rekomendasi Integrasi ketertarikan (preferensi) jangka pendek dan panjang Model pengguna umum dan solusi lintas domain Model komputasional terdistribusi Merekomendasikan sederetan item (misal: playlist) Recommender bagi pengguna mobile Topik-topik potensial untuk Rekomendasi untuk kelompok Proyek atau Tugas Akhir Rekomendasi Sadar-Konteks 51
Jenis-jenis Teknik
52
Min input vs. Max output • Sebagian besar pengguna tidak sabar mendapatkan hasil dengan memberikan hanya sedikit input • Ketertarikan pengguna dapat meningkat dan tergantung konteks • Pengguna ingin membuat pilihan yang akurat, yaitu mendapatkan item informasi yang relevan.
53
Collaborative Filtering & Google • SE bukanlah RS, Tetapi... • Sebenarnya Google dan Collaborative Filtering memiliki banyak kemiripan – Sama-sama meranking item – Ranking didasarkan pada opini dari penggunanya • Collaborative Filtering: rating pada items • Google: link ke halaman web
– Keduanya merupakan ekspresi dari Web 2.0
• Web 2.0: melibatkan pengguna – Content dibuat oleh pengguna – Pengguna membantu mengatur, men-share, meremix, meng-kritik dan mengupdatenya. 54
Google • Google: perusahaan yang merajai pencarian dan periklanan online – didirikan oleh Larry Page dan Sergey Brin (Mahasiswa S3 di Stanford University) • “googol” atau 10100 adalah istilah matematis yang dijadikan nama Google • Sukses Google dalam pencarian terutama didasarkan pada algortima PageRank-nya • Gartner memperkirakan saat ini Google menggunakan lebih dari 1 juta server, menangani hasil pencarian, gambar, video, email dan iklan. • Google melaporkan: menghabiskan 200 s.d 250 juta dolar setahun untuk belanja perangkat IT. 55
Perankingan Halaman Web • Menghitung inlinks: link menuju ke suatu halaman web. masukkan teks berikut dalam form pencarian google: link:www.mydomain.com
• Derajat kepentingan halaman-halaman web tidak sederajat – www.unibz.it vs. www.stanford.edu – Inlinks sebagai penentu • www.stanford.edu memiliki 3200 inlinks • www.unibz.it memiliki 352 inlink (Feb 2013)
• Apakah semua inlinks sederajat? – Pertanyaan berulang! 56
Formulasi Rekursif Sederhana • Setiap suara (vote) link adalah proporsional terhadap kepentingan dari halaman sumbernya • Jika halaman P dengan kepentingan x mempunyai n outlink, setiap link mendapatkan x/n suara
57
Model “aliran” Sederhana • a, m dan y adalah kepentingan dari halaman
58
Memecahkan Persamaan Aliran • 3 persamaan, 3 tidak diketahui, tidak ada konstanta – Tidak ada solusi yang unik – Jika kita mengalikan suatu solusi dengan konstanta (λ) diperoleh solusi lain – coba dengan (2 2 1)
• Aturan tambahan memaksa keunikan – y+a+m = 1 (normalisasi) – y = 2/5, a = 2/5, m = 1/5 – Ini adalah skor halaman-halaman di bawah asumsi model aliran
• Metode eliminasi Gauss bekerja untuk contoh kecil, diperlukan metode lebih baik untuk graf yang besar. 59
Matriks • Matriks adalah larik bilangan segi empat
• aij adalah elemen matriks A dalam baris i dan kolom j • A dikatakan matriks n x m jika mempunyai n baris dan m kolom • Perkalian Matriks:
60
Latihan • Hitung perkalian dua matriks berikut:
61
Solusi dari Latihan • Hitung perkalian dua matriks berikut:
62
Formulasi Matriks dari Aliran • Matriks M mempunyai satu baris dan satu kolom untuk setiap halaman web (matriks persegi) • Andaikan halaman i mempunyai n outlink: – Jika i link ke j, maka Mij=1/n – Jika tidak Mij=0
• M adalah matriks stokastik baris – Jumlah (SUM) baris-baris bernilai 1
• Andaikan r adalah vektor dengan satu entri per halaman web – ri adalah skor kepentingan halaman i – Dinamakan sebagai vektor rank
63
Contoh
64
Power Iteration Solution
Proses tersebut meng-converges rank vector apapun vektor awalnya, Diberikan bahwa SUM entrinya adalah 1. 65
Latihan • Buktikan bahwa jika M adalah matriks link yang dideskripsi sebelumnya dan M∞ = (aij) maka a1j= a2j = … = anj untuk semua j=1,…,n. Setiap kolom bersifat konstan. • Hint: gunakan fakta bahwa jika v adalah suatu vektor baris umum yang jumlah entri =1 maka vM∞ = r (Vektor rank)
66
Dari Ranking Statik ke Dinamis • Skor PageRank dari suatu haaman bersifat statik – Tidak tergantung pada Query pengguna
• Bagaimana kita dapat me-retrieve halaman-halaman yang relevan bagi Query pengguna (dan mempunyai skor page-rank tinggi)? • Kita harus menghitung skor untuk setiap halaman lain: derajat kecocokan antara Query dengan halaman • Akan dibahas di pertemuan lain? 67
Bagaimana Google Meranking Tweets • Tweets: teks microblog dengan panjang maks. 140-karakter yang dibuat oleh anggota Twitter • Kuncinya adalah mengidentifikasi "reputed followers," –Twitterers "follow" komentar dari Twitterers lain yang telah mereka pilih, dan mereka juga diikuti "followed“ • Anda mendapatkan reputasi dan kemudian anda memberikan reputasi • Jika banyak orang mengikuti anda, dan anda kemudian mengikuti seseorang – maka meskipun orang baru ini tidak mempunyai banyak pengikut (follower), tweetnya dianggap bernilai (valuable) • Satu pengguna mengikuti penguna lain dalam media sosial adalah analog dengan satu halaman ber-link ke halaman lain pada Web – keduanya adalah bentuk rekomendasi 68 • http://www.technologyreview.com/web/24353/
RS vs. SE I • Penelitian Recommender system telah mengambil teknik-teknik dari IR (misal: content-based filtering) • Search engines telah menggunakan ide dari recommender systems (suatu halaman dikatakan penting jika di-link-kan/disokong oleh halaman lain) • IR berurusan dengan repo besar content takterstruktur mengenai berbagai topik • RS fokus pada repo content kecil pada satu topik khusus • Personalization dalam IR (personalized search engines) menerima banyak perhatian lebih (misal: personalized google) – learning to rank. 69
RS vs. SE II • IR berurusan dengan “locating relevant content” – pengguna sebaiknya mampu mengevaluasi relevansi dari himpunan yang diretrieve • RS berurusan dengan “differentiating relevant content” – pengguna punya tidak cukup pengetahuan untuk mengevaluasi relevansi – Contoh. Bandingkan memilih kamera dengan Google dan dengan dpreview.com
• IR dan RS mendukung tahapan berbeda dari proses pencarian/penemuan informasi • Sistem informasi yang efektif harus memadukan teknikteknik yang hadir dari dua disiplin ini. 70
SE Vertical dan LBS • Vertical SE adalah specialists (fokus pada topik spesifik) dalam perbandingan terhadap generalists (Misal: Google dan Yahoo!) – Health dan medicine: medstory.com – Situs Travel: Kayak.com atau Expedia.com – Real-estate: Zillow.com atau Trulia.com (pencarian berbasis lokasi) – Job search: Indeed.com atau Monster.com – Shopping search engines: Shopzilla.com dan MySimon.com
• Location-based search (LBS) menggunakan informasi geografis untuk menyediakan hasil pencarian yang lebih relevan. 71
Search Engine Dinamis
72
Medstory.com Query: Retinoblastoma
73
Hasil Pencarian di Google Query: Retinoblastoma
74
Zillow.com
75
Trulia: Real-Estate Search
76
Bahan Bacaan • Andrei Z. Broder: A taxonomy of web search. SIGIR Forum 36(2): 3-10 (2002) • Gary Marchionini: Exploratory search: from finding to understanding. Commun. ACM 49(4): 41-46 (2006) • Resnick, P. and Varian, H. R. (1997). Recommender systems. Communications of the ACM,40(3):56-58.
77
