UAS-Information Retrieval

Nama : Abdul Kodir

UAS-IR--SERANG-42

1.  Metode / Algoritma apa saja yang digunakan untuk melakukan IR?

1. Metode Pencocokan (Boolean)
2. Metode Kesamaan Query / Vector Space Model, diantaranya :
1. Similarity Rangking Method / Metode Kesamaan Peringkat

Metode yang terlihat untuk pertandingan (misalnya, Boolean) mengasumsikan bahwa
Dokumen adalah baik relevan dengan query atau tidak relevan.

Metode Kesamaan peringkat : mengukur tingkat kesamaan antara query dan dokumen.

B. Weighting Method / Metode Pembobotan: tf dan idf

           Term Frekuensi (tf):

Adalah Sebuah istilah yang muncul beberapa kali dalam dokumen diberi bobot lebih daripada sebuah istilah yang muncul hanya sekali.

           Dokumen Invers Frekuensi (idf)

Adalah Sebuah istilah yang terjadi pada beberapa dokumen yang mungkin akan menjadi pembeda yang lebih baik dimana istilah yang muncul di sebagian atau semua dokumen.

3.      Metode Nilai Kecocokan berdasar kepentingan dokumen (PageRank)

2.    Perbedaan Information Retrieval dan Data Retrieval

Information Retrieval	Data Retrieval
Berhubungan dengan text bahasa umum yang tidak selalu terstruktur dan ada kemungkinan memiliki kerancuan arti	Berhubungan dengan data, yang mana semantik strukturnya sudah terdefinisikan
Informasi yang diambil mengenai subyek atau topic	Isi dokumen/data mengandung bagian dari keyword
Semantik sering kali hilang	Semantik terdefinisi dengan baik
Kesalahan kecil masih bisa ditorensi	Kesalahan kecil/tunggal dari suatu obyek menunjukkan kegagalan

Model yang terdapat dalam Information Retrieval terbagi dalam 3 model besar, yaitu:

1.      Set-theoretic models, model merepresentasikan dokumen sebagai himpunan kata atau frase. Contoh model ini ialah standard Boolean model dan extended Boolean model.

2.      Algebratic model, model merepresentasikan dokumen dan query sebagai vektor atau matriks similarity antara vektor dokumen dan vektor query yang direpresentasikan sebagai sebuah nilai skalar. Contoh model ini ialah vector space model dan latent semantic indexing (LSI).

3.      Probabilistic model, model memperlakukan proses pengembalian dokumen sebagai sebuah probabilistic inference. Contoh model ini ialah penerapan teorema bayes dalam model probabilistik.

Proses dalam Information Retrieval dapat digambarkan sebagai sebuah proses untuk mendapatkan relevant documents dari collection documents yang ada melalui pencarian query yang diinputkan user.

Proses yang terjadi di dalam Information Retrieval System terdiri dari 2 bagian utama, yaitu Indexing subsystem, dan Searching subsystem (matching system). Proses indexing dilakukan untuk membentuk basisdata terhadap koleksi dokumen yang dimasukkan, atau dengan kata lain, indexing merupakan proses persiapan yang dilakukan terhadap dokumen sehingga dokumen siap untuk diproses. Proses indexing sendiri meliputi 2 proses, yaitu document indexing dan term indexing. Dari term indexing akan dihasilkan koleksi kata yang akan digunakan untuk meningkatkan performansi pencarian pada tahap selanjutnya. Tahap-tahap yang terjadi pada proses indexing ialah:

1.   Word Token

Yaitu mengubah dokumen menjadi kumpulan term dengan cara menghapus semua karakter dalam tanda baca yang terdapat pada dokumen dan mengubah kumpulan term menjadi lowercase.

2.   Stopword Removal

Proses penghapusan kata-kata yang sering ditampilkan dalam dokumen seperti: and, or, not dan sebagainya.

3.   Stemming

Proses mengubah suatu kata bentukan menjadi kata dasar.

4.   Term Weighting

Proses pembobotan setiap term di dalam dokumen.

Search subsystem (matching) merupakan proses menemukan kembali informasi (dokumen) yang relevan terhadap query yang diberikan. Tidak semua dokumen yang diambil (retrieved) oleh system merupakan dokumen yang sesuai dengan keinginan user (relevant). Gambar dibawah ini menunjukkan hubungan antara dokumen relevan, dokumen yang terambil oleh system, dan dokumen relevan yang terambil oleh system:

I.       Pengukuran Performansi Information Retrieval System

Nilai performansi dari aplikasi IR menunjukkan keberhasilan dari suatu IRS dalam mengembalikan informasi yang dibutuhkan oleh user. Untuk mengukur performansi dari IRS, digunakan koleksi uji. Koleksi uji terdiri dari tiga bagian, yaitu koleksi dokumen, query, dan relevance judgement. Koleksi dokumen adalah kumpulan dokumen yang dijadikan bahan pencarian oleh sistem. Relevance judgement adalah daftar dokumen-dokumen yang relevan dengan semua query yang telah disediakan. Parameter yang digunakan dalam performansi sistem, antara lain :

1.      Precision (ketepatan)

Precision ialah perbandingan jumlah dokumen relevan yang didapatkan sistem dengan jumlah seluruh dokumen yang terambil oleh sistem baik relevan maupun tidak relevan.

precision = Jumlah dokumen yang relevan dengan query dan terambil.            

                                jumlah seluruh dokumen yang terambil

2.      Recall (kelengkapan)

Recall ialah perbandingan jumlah dokumen relevan yang didapatkan sistem dengan jumlah seluruh dokumen relevan yang ada dalam koleksi dokumen (terambil ataupun tak terambil sistem).

recall = Jumlah dokumen yang relevan dengan query dan terambil sistem.

                   jumlah seluruh dokumen relevan dalam koleksi dokumen

3.      Interpolate Average Precision (IAP)

Pengukuran performansi dengan mempertimbangkan aspek keterurutan atau rangking dapat dilakukan dengan melakukan interpolasi antara precision dan recall. IAP akan mencatat semua Semua dokumen yang relevan dan urutan dokumen tersebut pada hasil IRS dan menghitung nilai precisionnya.

Nilai precision untuk semua titik ditentukan oleh perubahan nilai recall yang terjadi. Nilai precision berubah pada saat nilai recall berubah naik. Precision disatu titik recall tertentu adalah maksimal precision untuk semua titik recall yang lebih kecil dari titik tersebut. Sebagai contoh, suatu IRS mendapatkan 10 dokumen berdasarkan suatu query dengan urutan sebagai berikut D1, D2, D3, D4, D5, D6, D7, D8, D9, dan D10. Dokumen yang relevan dalam koleksi dokumen berdasar query tersebut ialah D2, D4, D7, D13, dan D20, maka nilai precision dari sistem tersebut ialah 3/10 = 0.3, sedangkan nilai recall nya ialah 3/6 = 0.5.

Contoh Recall dan Precision dengan Matching Exact:

•     Koleksi dari 10.000 dokumen, 50 pada topik yang spesifik

•     Pencarian Ideal menemukan 50 dokumen dan menolak yang lain.

•     Pencarian aktual mengidentifikasi 25 dokumen, 20 relevan tapi 5 berada di topik lain

•     Presisi: 20/25 = 0,8 (80% hits yang relevan)

•     Recall: 20/50 = 0,4 (40% dari yang relevan ditemukan)

Mengukur Presisi dan Recall:

Presisi mudah untuk mengukur:

•     User  melihat setiap dokumen yang diidentifikasi dan memutuskan apakah itu relevan.

•     Pada contoh, hanya 25 dokumen yang ditemukan perlu untuk diperiksa.

Recall sulit untuk mengukur:

•     Untuk mengetahui semua item yang relevan, User harus melihat seluruh koleksi dokumen dan melihat setiap objek untuk memutuskan apakah itu sesuai dengan kriteria.

•     Dalam contoh, 10.000 dokumen semuanya harus diperiksa.

 3. Jelaskan Algoritma Web-Crawler yang sederhana, berikan contohnya.

 Web crawler merupakan program komputer yang melakukan kunjungan ke situs situs di internet, secara periodik & sistematis tergantung kepada aturan yang sudah ditentukan. Biasanya dikenal dengan sebutan bot / robot / automatic indexer / web spider.

Penting sekali bagi web site untuk mempersiapkan diri ketika sang robot menjadi tamu mengunjungi situs anda, sehingga hasil pencatatan tentang situs juga memuaskan, yang tentu berdampak baik bagi nilai situs di mata mesin pencari/Search Engine.

Program Web Crawler yang dimiliki oleh situs mesin pencari, membutuhkan data dari situs yang ada, dimana proses kunjungan (crawling/indexing) tidak tentu dan tergantung sekali oleh banyak faktor yang sudah ditentukan melalui Algoritma.

Berikut Algoritma Web Crawler :

• Breadth-First,

• Best-First,

• PageRank,

• Shark-Search, dan

• InfoSpiders.

 Breadth-first

Adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpul-simpul yang tadi dikunjungi, demikian seterusnya. algoritma BFS menggunakan graf sebagai media representasi persoalan, tidak sulit untuk mengaplikasikan algoritma ini dalam persoalan-persoalan teori graf.

Cara Kerja Algoritma Breadth First Search

Dalam algoritma BFS, simpul anak yang telah dikunjungi disimpan dalam suatu antrian. Antrian ini digunakan untuk mengacu simpul-simpul yan bertetangga dengannya yang akan dikunjungi kemudian sesuai urutan pengantrian. Untuk memperjelas cara kerja algoritma BFS beserta antrian yang digunakannya.

Berikut langkah-langkah algoritma BFS:

1. Masukkan simpul ujung (akar) ke dalam antrian.
1. Ambil simpul dari awal antrian, lalu cek apakah simpul merupakan solusi
2. Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.
3. Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam antrian.
4. Jika antrian kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan
5. Ulangi pencarian dari langkah kedua.

Best-First

Best-First merupakan sebuah metode yang membangkitkan simpul dari simpul sebelumnya. Best-first memilih simpul baru yang memiliki biaya terkecil diantara  semua leaf nodes (simpul-simpul pada level terdalam) yang pernah dibangkitkan. Penentuan simpul terbaik dilakukan dengan menggunakan sebuah fungsi yang disebut fungsi evaluasi f(n).

Fungsi evaluasi best-first dapat berupa biaya perkiraan dari suatu simpul menuju ke goal atau gabungan antara biaya sebenarnya dan biaya perkiraan tersebut.

Pada setiap langkah proses pencarian terbaik pertama, kita memilih node-node dengan menerapkan fungsi heuristik yang memadai pada setiap node/simpul yang kita pilih dengan menggunakan aturan-aturan tertentu untuk menghasilkan penggantinya. Fungsi heuristic merupakan suatu strategi untuk melakukan proses pencarian ruang keadaan suatu problema secara selektif, yang memandu proses pencarian yang kita lakukan sepanjang jalur yang memiliki kemungkinan sukses paling besar.

Ada beberapa istilah yang sering digunakan pada metode best-first search, yaitu:

1. Start node adalah sebuah terminology untuk posisi awal sebuah pencarian.
2. Curret node adalah simpul yang sedang dijalankan dalam algoritma pencarian jalan terpendek
3. Suksesor adalah simpul-simpul yang yang akan diperiksa setelah current node
4. Simpul (node) merupakan representasi dari area pencarian
5. Open list adalah tempat menyimpan data simpul yang mungkin diakses dari starting node maupun simpul yang sedang dijalankan
6. Closed list adalah tempat menyimpan data simpul yang juga merupakan bagian dari jalur terpendek yang telah berhasil didapatkan
7. Goal node yaitu simpul tujuan
8. Parent adalah curret node dari suksesor.

Algoritma best-first pertama kali, dibangkitkan node A. Kemudian semua suksesor A dibangkitan, dan dicari harga paling minimal. Pada langkah 2, node D terpilih karena harganya paling rendah, yakni 1. Langkah 3, semua suksesor D dibangkitkan, kemudian harganya akan dibandingkan dengan harga node B dan C. Ternyata harga node B paling kecil dibandingkan harga node C, E, dan F. Sehingga B terpilih dan selanjutnya akan dibangkitkan semua suksesor B. Demikian seterusnya sampai ditemukan node tujuan. Ilustrasi algoritma best-first dapat dilihat pada gambar 3.4 dibawah ini.

Untuk mengimplementasikan algoritma pencarian ini, diperlukan dua buah senarai, yaitu: OPEN untuk mengelola node-node yang pernah dibangkitkan tetapi belum dievaluasi dan CLOSE untuk mengelola node-node yang pernah dibangkitkan dan sudah dievaluasi.

Algoritma Best First selengkapnya adalah sebagai berikut.

1. OPEN berisi initial state dan CLOSED masih kosong.

2. Ulangi sampai goal ditemukan atau sampai tidak ada di dalam OPEN.
a. Ambil simpul terbaik yang ada di OPEN.
b. Jika simpul tersebut sama dengan goal, maka sukses
c. Jika tidak, masukkan simpul tersebut ke dalam CLOSED
d. Bangkitkan semua aksesor dari simpul tersebut
e. Untuk setiap suksesor kerjakan:

Jika suksesor tersebut belum pernah dibangkitkan, evaluasi suksesor tersebut, tambahkan ke OPEN, dan catat parent.

Jika suksesor tersebut sudah pernah dibangkitkan, ubah parent-nya jika jalur melalui parent ini lebih baik daripada jalur melalui parent yang sebelumnya. Selanjutnya perbarui biaya untuk suksesor tersebut dn nodes lain yang berada di level bawahnya.

Algoritma yang menggunakan metode best-first, yaitu:

1. Greedy Best-First

Greedy Best-First adalah algoritma best-first yang paling sederhana dengan hanya memperhitungkan biaya perkiraan (estimated cost) saja, yakni f(n) = h(n).

Biaya yang sebenarnya (actual cost) tidak diperhitungkan. Dengan hanya memperhitungkan biaya perkiraan yang belum tentu kebenarannya, maka algoritma ini menjadi tidak optimal.

1. A*

A* adalah algoritma best-first yang menggabungkan Uniform Cost dan Greedy Best-First. Biaya yang diperhitungkan didapat dari biaya sebenarnya ditambah dengan biaya perkiraan. Dalam notasi matematika dituliskan sebagai f(n)= g(n) + h(n).

Dengan perhitungan biaya seperti ini, algoritma A* adalah complete dan optimal.

PageRank

Adalah sebuah Aalgoritma yang telah dipatenkan yang berfungsi menentukan situs web mana yang lebih penting/populer. PageRank merupakan salah satu fitur utama mesin pencari Google dan diciptakan oleh pendirinya, Larry Page dan Sergey Brin yang merupakan mahasiswa Ph.D. Universitas Stanford. Dari pendekatan yang sudah dijelaskan pada artikel konsep pagerank.

Lawrence Page and Sergey Brin membuat algoritma pagerank seperti di bawah ini:

Algoritma awal :

PR(A) = (1-d) + d ( ( PR(T1) / C(T1) ) + … + ( PR(Tn) / C(Tn) ) )

Salah satu algoritma lain yang dipublikasikan :

PR(A) = (1-d) / N + d ( ( PR(T1) / C(T1) ) + … + ( PR(Tn) / C(Tn) ) )

PR(A) adalah Pagerank halaman A

• PR(T1) adalah Pagerank halaman T1 yang mengacu ke halaman A
• C(T1) adalah jumlah link keluar (outbound link) pada halaman T1
• d adalah damping factor yang bisa diberi antara 0 dan 1.
• N adalah jumlah keseluruhan halaman web (yang terindeks oleh Google)

Dari algoritma di atas dapat dilihat bahwa pagerank ditentukan untuk setiap halaman anda bukan keseluruhan situs web. Pagerank sebuah halaman ditentukan dari pagerank halaman yang mengacu kepadanya yang juga menjalani proses penentuan pagerank dengan cara yang sama, jadi proses ini akan berulang sampai ditemukan hasil yang tepat.

Akan tetapi pagerank halaman A tidak langsung diberikan kepada halaman yang dituju, akan tetapi sebelumnya dibagi dengan jumlah link yang ada pada halaman T1 (outbound link), dan pagerank itu akan dibagi rata kepada setiap link yang ada pada halaman tersebut. Demikian juga dengan setiap halaman lain “Tn” yang mengacu ke halaman “A”.

Setelah semua pagerank yang didapat dari halaman-halaman lain yang mengacu ke halaman “A” dijumlahkan, nilai itu kemudian dikalikan dengan damping factor yang bernilai antara 0 sampai 1. Hal ini dilakukan agar tidak keseluruhan nilai pagerank halaman T didistribusikan ke halaman A.

Shark-Search

Suatu algoritma baru, yang disebut “Algoritma Shark-Search“, algoritma ini sementara menggunakan metafora sederhana yang sama, mengarah pada penemuan informasi yang relevan lebih dalam waktu eksplorasi yang sama.
Salah satu perbaikan langsung adalah dengan menggunakan, bukan evaluasi (yang relevan / tidak relevan) biner relevansi dokumen, apa yang akan kita sebut akhirat mesin kesamaan dalam rangka untuk mengevaluasi relevansi dokumen untuk query yang diberikan.

Seperti mesin menganalisa dua dokumen dinamis dan mengembalikan “kabur” nilai, yaitu, skor antara 0 dan 1 (0 untuk ada kesamaan apapun, 1 untuk sempurna cocok “konseptual”) daripada nilai biner.
Perbaikan pertama ini memiliki dampak langsung pada daftar prioritas. Kami menggunakan “kabur” nilai relevansi, memberikan anak skor warisan, sehingga lebih memilih anak-anak dari sebuah node yang memiliki skor yang lebih baik. Informasi ini dapat diperbanyak bawah rantai keturunan, sehingga meningkatkan pentingnya cucu dari simpul yang relevan atas cucu dari node tidak relevan. Anak-anak dari sebuah simpul tidak relevan menggunakan skor orangtua mereka mewarisi untuk menghitung skor mereka sendiri mewarisi – dengan mengalikannya dengan beberapa faktor peluruhan d, yang berperan sebanding dengan “memudar” faktor Marchiori ini [Marchiori 97]. Jadi, misalkan dokumen X dan Y dianalisis dan X yang memiliki skor yang lebih tinggi. Misalkan lebih lanjut bahwa anak-anak dari kedua X dan Y memiliki skor nol, dan algoritma sekarang harus memilih yang paling menjanjikan dari cucu mereka. Karena kedua skor mereka dikalikan dengan d 2, pencarian hiu memilih cucu X pertama (yang tampaknya intuitif yang benar). Melangkah lebih jauh dari X, ke zona cicit, akan membawa keturunan Y kembali menjadi pertimbangan, mengingat pilihan yang sesuai d. Perilaku ini dihargai terus menerus warisan skor jauh lebih alami dibandingkan dengan pendekatan Boolean dari Shark-Search.

 InfoSpiders

infoSpiders bekerja berdasarkan prosedur Algoritma yang telah ditentukan oleh masing-masing search engine, mereka akan melakukan penilaian terhadap web tersebut berdasarkan faktor algoritma sehingga bisa memunculkan web mana yang paling tinggi nilai relevansinya pada informasi yang kita inginkan.

Contohnya kita ingin mencari informasi sepak bola di google, maka dengan sekejap SPIDER-nya google akan mensearch kesemua web di dunia ini yang mempunyai kata sepakbola dengan software mereka.

dibayangkan kalau kita search kata “Information Retrieval” di google pasti akan muncul banyak web yang menampilkan kata Informationretrieval, akan tetapi bagaimana kita bisa mensortir mana yang paling relevan dengan kita dan paling akurat informasinya, oleh karena itu ada PageRank.
sehingga dapat dikatakan InfoSpider dan PageRank saling terkai satu sama lain dalam hal menjalankan proses Web Crawler.

Jadi setiap InfoSpider dan PageRank ada nilai relevansinya dan itu ditentukan oleh beberapa faktor, antara lain:

1. Frekuensi dan lokasi kata kunci dalam Halaman Web

Jika kata kunci hanya muncul sekali di dalam badan halaman, web tersebut akan menerima skor yang rendah untuk kata kunci tersebut.

2. Berapa lama web telah ada

Orang-orang membuat halaman web baru setiap hari, dan tidak semua dari mereka menunggu dekat lama. Google menghargai web dengan waktu lebih lama.

3. Jumlah halaman Web lainnya yang memiliki link ke halaman yang bersangkutan

Google melihat berapa banyak halaman Web link ke situs tertentu untuk menentukan relevansinya. Link ini termasuk link keluar atau link kedalam. Jadi semakin banyak link yang ada pada halaman tersebut (yang pasti link yang sesuai dengan informasi yang kita mau) akan mempunyai nilai besar.