Penelusuran Informasi (Information Retrieval) Taufik Fuadi Abidin. Web Search

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


Web Search Overview

3

3


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


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!


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)


Arsitektur dari Web Crawler

http://en.wikipedia.org/wiki/Web_crawler


Nama-Nama Web Crawler

Yahoo! Slurp (Yahoo) Bingbot ( Microsoft's Bing webcrawler) Googlebot (Google) WebCrawler

Open Source Crawler: Nutch HTTrack Seeks


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: /


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


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)


Contoh: WWW yang Near-Duplicate


Pertanyaan

Bagaimana mengeliminasi near-duplicates dari dua halaman web?


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%


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


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


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


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


Pertanyaan

Bagaimana menentukan sebuah halaman e-mail yang merupakan SPAM?

Penelusuran Informasi (Information Retrieval) Taufik Fuadi Abidin. Web Search

Recommend Documents