Metode, Cara Kerja dan Algoritma IR

1.      Metode / Algoritma Yang digunakan dalam melakukan IR (Information Retrieval)

a).  Model Boolean (BIR Boolean Information Retrieval)

Model ini merupakan model IR sederhana yang berdasarkan atas teori himpunan dan aljabar boolean. Boolean sendiri pertama kali dikembangkan oleh seroang ilmuan matematika bernama George Boole (1815-1864). Yang dikemukakan sebagai suatu struktur logika aljabar yang mencakup operasi Logika AND, OR dan NOR, dan juga teori himpunan untuk operasi union.

Didalam struktur data, Boolean merupakan sebuah tipe data yang bernilai “True” atau “False” (benar atau salah). Sehingga didalam IR, logika boolean berarti bahwa data yang di crawler sesuai atau tidak antara variable – variablenya.

Kelebihan Model Boolean

• Mudah Untuk di Implementasikan
• Konsep Yang Terstruktur

Kekurangan Model Boolean

• Pencocokan yang tepat dapat mengambil dokumen terlalu sedikit atau terlalu banyak.
• Sulit untuk pengindexkan, beberapa dokumen yang lebih penting dari pada yang lain kadang berada dibawah dokumen yang tidak penting.
• Sulit untuk menerjemahkan query ke dalam ekspresi Boolean
• Semua istilah sama-sama berbobot
• Lebih seperti pengambilan data dari pencarian informasi

Struktur Data dan Algoritmanya

Jika dilihat dari sudut pandang matematika atau sudut pandang praktis, BIR (boolean Information Retrieval) adalah logika yang paling mudah.  Namun secara logika dan struktur data tidak semudah hal yang diutarakan diatas. Algoritma BIR diantaranya adalah Hash Table, Steeming dan lain lain. Diabawah merupakan rekaman bagaimana cara kerja Hash Tabel salasatu algoritma dalam BIR

b). Model Vector Space (VSM)

Model Vector Space adalah Model dalam IR yang berbasis token untuk memungkinkan partial matching dan pemeringkatan dokumen (pengindexan). Dengan prinsip dasar dokumen menjadi sebuah token yang kemudian ti kumpulkan menjadi t(n) token-token, kemudian Query menjadi vector token yang berfungsi untuk mencari token-token yang berhubungan dengan melihat kesamaan vektor dokumen dan query berdasarkan jarak vektor.

Kelebihan Vector Space Model (VSM)

1. Adanya peringkat pengambilan informasi
2. Menampilkan referensi yang sesuai kebutuhan
3. Penyocokan secara partial.

Kekurangan Vector Space Model (VSM)

• Menganggap informasi adalah independen
• Bobot pemahaman(istilah) tidak lagi diperlukan.

Cara Kerja VSM dan Algoritmanya.

Pada VSM, setiap dokumen dan  query dari pengguna direpresentasikan  sebagai ruang vektor berdimensi n.  Biasanya digunakan nilai bobot istilah (term weigthing) sebagai nilai dari vektor pada dokumen nilai 1 untuk setiap istilah yang  muncul pada vektor query.

Pada model ini, bobot dari query dan dokumen dinyatakan dalam bentuk  vektor, seperti: Q = (wq1, wq2, wq3, . . . ,wqt) dan Di= (wi1, wi2, wi3, . . . , wit) Dengan wqj dan wij sebagai bobot istilah Tj dalam query Q dan dokumen Di. Dengan demikian dokumen yang lebih panjang dengan jumlah istilah yang lebih banyak memiliki kemungkinan lebih besar untuk dianggap relevan dengan istilah-istilah query tertentu dibandingkan dokumen-dokumen yang lebih pendek. Sehingga pada kebanyakan lingkungan penemu-kembalian, vektor dokumen ternormalisasi lebih disukai namun proses normalisasi vektor querytidak diperlukan karena ukurannya yang umumnya pendek dan perbedaan panjang antar-query relatif kecil.

c). Model Probabilistic

Model Probabilitas didasarkan pada Prinsip Ranking Probabilitas, yang menyatakan bahwa sistem pencarian informasi yang seharusnya berdasarkan peringkat probabilitas dokumen mereka yang relevan dengan query, mengingat semua bukti yang tersedia [Belkin dan Croft 1992].

Olehkarena itu dalam metode probabilitas ini, suatu dokumen yang sering di temukan dan diindexing ulang merupakan dokumen yang paling relevan dari kata kunci, sehingga akan selalu muncul ketika katakunci itu di queue.

2. Perbedaan cara kerja Precision versus Recall adalah :

a). Precision disebut juga kepresisan atau kecocokan antara permintaan informasi dengan jawaban terhadap permintaan informasi itu sendiri, artinya persis atau cocok dokumen tersebut untuk keperluan pencari informasi, bergantung pada seberapa relevan dokumen tersebut bagi si pencari.suatu perbandingan ratio jumlah isi dokumen yang relevan dengan jumlah seluruh dokumen yang terambil oleh sistem baik relevan maupun tidak relevan. 

Contoh : 
  Tabel Rumus 

	Relevan	Tidak Relevan	Total
Ditemukan	a (hits)	b (noise)	a+b
Tidak ditemukan	c (misses)	d (reject)	c+d
Total	a+b	c+d	a+b+c+d

 

Tabel contoh precision

	Relevan	Tidak Relevan	Total
Ditemukan	60	30	90
Tidak ditemukan	15	5	20
Total	90	20	110

 Precision = [a/ (a+b)] x 100

[60/(60+30)]x100 = 66.7 %

 b). Recall (remember, recollect, remind) menemukan kembali informasi yang sudah tersimpan dari proporsi jumlah dokumen yang dapat ditemukan-kembali oleh sebuah proses pencarian dengan perbandingan  jumlah dokumen relevan yang didapatkan sistem dengan jumlah seluruh dokumen relevan yang ada dalam  dokumen.

  Tabel Rumus

	Relevan	Tidak Relevan	Total
Ditemukan	a (hits)	b (noise)	a+b
Tidak ditemukan	c (misses)	d (reject)	c+d
Total	a+b	c+d	a+b+c+d

Tabel contoh precision

	Relevan	Tidak Relevan	Total
Ditemukan	60	30	90
Tidak ditemukan	15	5	20
Total	90	20	110

Recall = [a/ (a+c)] x 100

[60/(60+15)]x100 = 80 %

3.  Algoritma Web-Crawler sederhana

Web-Crawler sering juga disebut Web Spider atau Web Robot merupakan web aplikasi atau program komputer atau script automatic yang berfungsi mengumpulkan atau mencari informasi dari berbagai halaman web atau blog yang ada di internet secara perodik dan sistimatis. Web crawler  fungsi utamanya adalah untuk melakukan penjelajahan serta pengambilan halaman-halaman situs, dari hasil pengumpulan situs.
Cara Kerja Web Crawler :
a). Mengunduh (download)  halaman web : melakukan pengunduhan halaman web berdasarkan URL yang diberikan kemudian file di simpan di basisdata, kemudian dimanupulasi untuk di index atau untuk diarsip dengan mengunakan pengarsipan otomatis.
b). Memprasing halaman web yang telah diunduh dan mengambil semua link :  memprasing ke seluruh halaman web yang sudah diunduh dan mengambil link-link dihalaman lain kemudian didepinisikan dengan sebuah penanda HTML.
c). Setiap link yang diambil diulangi proses : melakukan proses bentuk pengulangan (rekursif) dalam hal ini mengunakan dua metode yaitu :
(1). Depth First yaitu menikuti jalur samapai selesai sebelum mencoba jalur yang lain,  dengan mengunakan algoritma ini menemkan link pertama pada halaman pertama kemudian halaman yang berasosiasi dengan link tersebut menemukan link pertama dan berulang sampai terakhir samapi semuanya dikunjungi.
(2). Breadth First yaitu pengujian setiap link pada sebuah halaman sebelum memproses halaman selanjutnya, dengan mengunakan algoritma ini akan menelusuri setiap link pada halaman pertama kemudian menelusuri kembali sampai pada level link yang pernah dikunjungi.
Dalam Web Crawler harus melakukan tolak ukur antara lain :
a). Pengendalian Query similaritas  : sebuah query  mengendalikan crawler  dan didefinisikan pentingnya sebuah halaman sebagai similaritas texttual diantara halaman web dan query.
b). Menghitung banyaknya link halaman web, maka banyak nya link halaman yang keluar semakin berharga karna merupakan direktori web, contoh kasus di blogspot semakian banyak link dan menyukai Google+ maka semakin blog tersebut terindex, tolak ukur ini biasa disebut Forward Link Count .
c). Banyaknya link dari halaman web makan secara intutif  sebuah halaman web yang dilinkan dengan banyak halaman yang menjadi referensi. tolak ukuran ini sering disebut juga Backlink Count.
d). Halaman web sebagai lokasi sebagai conoh, URL yang ber ujung ".COM" lebih berguna dari URL lainya, tolak ukur ini biasa disebut Location Matric.
d). Menetapkan semua link yang sama contoh kasus : sebuah link yahoo dihitung dengan link individu, jika link yahoo  lebih penting maka link yahoo lebih tinggi, tolak ukur ini biasa disebut PageRank
Dari penjelasan diatas google sudah menerapkan web Crawler https://www.google.co.id/

Berikut merupakan Algoritma Web Crawler yang Sederhana.

Q <—- S0

DO WHILE NOT (isQueueEmpty(Q))

u <—- Dequeue (Q)

d(u) <—- Fetch(u)

CALL Store(D,(d(u),u))

L <—- Parse (d(u))

FOR EACH v IN L

CALL Store (E,(u,v))

IF NOT (v € D OR v € Q)

THEN Enqueue (Q,v).

END FOR

END DO

Penjelasan dari algoritma diatas.

Ketika Queue Kosong maka diminta untuk melakukan pengisian Queue, ketika ada maka diambil dari data store kemudian ditampilkan. Secara sederhana algoritma diatas memerintahkan seperti demikian.