Penelusuran Informasi (Information Retrieval) Taufik Fuadi Abidin
Web Search
Penelusuran Informasi (Information Retrieval)
Topik Pertemuan Ini
Web Search Overview Sejarah Perkembangan Web Search Arsitektur Web Crawler Tantangan dalam Web Search Tech Near Duplicate Jaccard Coefficient SPAM
Penelusuran Informasi (Information Retrieval)
Web Search Overview
3
3
Penelusuran Informasi (Information Retrieval)
World Wide Web (WWW) Diperkenalkan pertama sekali oleh Tim Berners-Lee pada tahun 1990 Saat ini, Lee menjabat sebagai ketua World Wide Web Consortium (W3C) yang mengatur perkembangan WWW Situs web pertama yang dibuat oleh Lee dan ditempatkan pada web server pertama dapat dilihat di http://info.cern.ch
Tim Berners-Lee juga pengembang protokol HTTP, URL dan HTML
Penelusuran Informasi (Information Retrieval)
Sejarah Perkembangan Web Search Tahun 1993, web robots (spiders/crawlers) diciptakan untuk mengumpulkan URL, diantaranya: Wanderer ALIWEB (Archie-Like Index of the WEB) WWW Worm
Pada tahun 1994, mahasiswa Graduate Stanford, David Filo dan Jerry Yang, secara manual mengumpulkan web site yang populer dan membuatnya dalam bentuk toxonomy (hirarki). Ide ini menjadi cikal bakal lahirnya Yahoo!
Penelusuran Informasi (Information Retrieval)
Sejarah Perkembangan Web Search Tahun 1994, Brian Pinkerton mengembangkan Webcrawler sebagai bagian dari tugas kuliah di Univ of Washington. Projek ini kemudian menjadi bagian dari Excite (www.excite.com) dan AOL. Pada tahun 1995, lahir Altavista (www.altavista.com) Pada tahun 1998, Larry Page dan Sergey Brin, mahasiswa Stanford, memperkenalkan Google yang menggunakan link analysis untuk melakukan ranking, selain teks info (tf x idf)
Penelusuran Informasi (Information Retrieval)
Arsitektur dari Web Crawler
http://en.wikipedia.org/wiki/Web_crawler
Penelusuran Informasi (Information Retrieval)
Nama-Nama Web Crawler
Yahoo! Slurp (Yahoo) Bingbot ( Microsoft's Bing webcrawler) Googlebot (Google) WebCrawler
Open Source Crawler: Nutch HTTrack Seeks
Penelusuran Informasi (Information Retrieval)
Tata Krama Sebuah Web Crawler Tata krama dari sebuah web crawler dapat diatur melalui Robots Exclusion Protocol Aturan tata krama tersebut dapat diatur melalui file robot.txt User-agent: * Disallow: /
Penelusuran Informasi (Information Retrieval)
Robot.txt User-agent: * Disallow: /cgi-bin/ Disallow: /tmp/ Disallow: /~joe/
User-agent: Google Disallow: /~joe/junk.html Disallow: /~joe/foo.html Disallow: /~joe/bar.html
Penelusuran Informasi (Information Retrieval)
Web Search Challenges Distributed Data: Document menyebar pada lebih dari jutaan web server Volatile Data: Document WWW berubah dan hilang dengan cepat (dead links) Large Volume: Jumlah halaman WWW cukup besar Unstructured and Redundant Data: Tidak ada struktur yang sama, lebih dari 30% adalah halaman web yang (near) duplicate Quality of Data: Tidak ada editor, typos Heterogeneous Data: Beragam tipe media (image, video, languages, character sets)
Penelusuran Informasi (Information Retrieval)
Contoh: WWW yang Near-Duplicate
Penelusuran Informasi (Information Retrieval)
Pertanyaan
Bagaimana mengeliminasi near-duplicates dari dua halaman web?
Penelusuran Informasi (Information Retrieval)
Mendeteksi Near-Duplicates Hitung similarity menggunakan pengukuran jarak (distance measure) Kesamaan yang ingin dihitung adalah kesamaan penulisan (syntax) bukan kesamaan arti (semantics) Semantic Similarity sulit dihitung Halaman web dikatakan near-duplicates jika tulisannya mirip, bukan penulisannya berbeda tetapi artinya sama. Hal ini sulit ditentukan Tentukan threshold dari near-duplicates, misalnya 80%
Penelusuran Informasi (Information Retrieval)
Representasi Web dalam n-Gram (Shingle) Shingles adalah n-gram Shingles digunakan sebagai fitur dalam menentukan kesamaan sintaks (syntactic similarity) dari halaman web Sebagai contoh, “a rose is a rose is a rose” dalam 3gram adalah { a-rose-is, rose-is-a, is-a-rose } Kesamaan (similarity) dari dua dokumen dapat dihitung menggunakan Jaccard Coefficient dari himpunan shingle (n-gram) 15
15
Penelusuran Informasi (Information Retrieval)
Jaccard Coefficient Jika A dan B adalah dua dokumen Jaccard Coefficient adalah:
Dimana JACCARD(A, A) = 1 JACCARD(A, B) = 0 jika A ∩ B = 0 Ukuran halaman A dan B boleh berbeda Nilai Jaccard antara 0 dan 1 16
16
Penelusuran Informasi (Information Retrieval)
Contoh Perhitungan Jaccard Coefficient Diketahui 3 dokumen: d1: “Jack London traveled to Oakland” d2: “Jack London traveled to the city of Oakland” d3: “Jack traveled from Oakland to London”
Menggunakan 2-gram (bi-gram), Jaccard Coefficient dari J(d1,d2) dan J(d1,d3) adalah: J(d1, d2) = 3/8 = 0.375 J(d1, d3) = 0 Perhatikan bahwa coefficient ini sangat sensitive dan cendrung menuju dissimilarity
Penelusuran Informasi (Information Retrieval)
SPAM SPAM dapat juga diartikan sebagai unwanted info Sebelum algoritma page rank diperkenalkan dan search engine masih hanya menggunakan text info (frequency dan idf) hasil ranking dapat dikelabui oleh spammer dengan menulis keyword tertentu secara berulang-ulang dalam sebuah halaman web SPAM dapat berbentuk: Web Email Blog / Wiki
Penelusuran Informasi (Information Retrieval)
Pertanyaan
Bagaimana menentukan sebuah halaman e-mail yang merupakan SPAM?