Mesin IR: Information Retrieval atau Search Engine

Untuk mengakali Search Engine (SE) seperti google, yahoo, atau lebih kerennya meng-OPTIMASI Search Engine, sehingga muncul terminologi SEO : Search Engine Optimization, ada baiknya kita tahu cara kerja mesin pencari secara umum.


Introduction

Ada beberapa teknik yang digunakan oleh mesin pencari untuk menemukan dokumen yang relevan sesuai dengan kueri (kata kunci) pengguna, dan tentu saja tidak sama dengan pencarian database dengan Select ... Where ....
Semua teknik pada intinya berusaha menghitung kemiripan antara dokumen yang ditemukan terhadap kueri yang diinputkan pengguna. Pada akhirnya, teknik-teknik tersebut menentukan cara penyusunan index dari seluruh dokumen pada koleksi.

Wah, di sini kita ketemu beberapa istilah baru. Ok, sebelum membahas lebih mendalam tekniknya, kita perjelas dulu istilahnya.

• Kueri : inputan kata kunci pencarian yang diberikan pengguna kepada mesin IR seperti google, yahoo, bing, etc
• Indexing : proses penyusunan index dari seluruh dokumen pada koleksi, yang terdiri dari kata-kata (token)
• Koleksi : adalah kumpulan dokumen yang disalin ke mesin IR (istilah IR-nya korpus). Misalnya Google "menjepret" seluruh halaman website yang bisa diakses umum (tanpa login terlebih dahulu) kemudian menyalinnya ke mesin IR di ruang servernya google (kira-kira total halaman internet seluruh dunia berapa Terrabyte ya?).

Cara menjepretnya gimana? tanya sama Google ... ! hehehe.
Biasanya menggunakan program robot atau crawler untuk menelusuri halaman-halaman internet,... seluruhnya, termasuk blog yang anda baca ini.
Setelah halaman dijepret dan disalin ke server Google (dokumen baru), maka proses indexing akan dilakukan kembali. Tentu saja tidak mengindeks ulang seluruhnya, tapi lebih kepada proses update index terhadap kata-kata yang ketemu pada dokumen baru tersebut.

• Tokenisasi : proses pembentukan token dari suatu dokumen, dengan memecah dokumen menjadi kata-kata, dapat berupa array kata.
• Retrieving : proses menemukan dokumen dari koleksi sesuai dengan kata kunci (kueri) user 

Cukup dulu istilahnya. Nah, ada 2 isitlah penting yang menjadi dasar cara kerja mesin IR atau search engine:
1. Proses Indexing
2. Proses Retrieving


Metode Sistem IR

Beberapa metode dapat melalui sub-tahap yang berbeda pada proses indexing dan retrieving. Misalnya sistem IR dengan model Boolean, yang hanya memeriksa ada atau tidak kata-kata kueri pada file index. Bila menggunakan model TF-IDF, maka proses indexing-nya pun akan sedikit berbeda. Model Probabilistik juga akan berbeda.
Perbedaan yang mencolok adalah antara model Boolean dan model statistik (TF-IDF dan probabilistik), yaitu adanya perhitungan bobot.

Ketemu lagi istilah baru:
TF-IDF, bobot, boolean. Wah kayaknya semakin informatika nanti bahasanya nih. OK, saya coba jelaskan dengan bahasa yang umum saja.

Model Boolean:

Kata-kata diberi nilai 1 bila ada pada dokumen koleksi, dan nol bila tidak ada. Jadi bisa dikatakan bobotnya adalah 0 atau 1. Meskipun beberapa usaha modifikasi bobot dilakukan untuk meningkatkan relevansi hasil pencarian.

Model Statistik:

Kata-kata diberi nilai sesuai dengan frekuensi kemunculan pada dokumen. Beberapa formulasi matematika dilakukan untuk menghitung bobot yang berbeda antara kata yang penting dan kata yang tidak penting. Tentu saja mesin tidak tahu mana kata yang penting atau tidak penting. Penilaian dilakukan melalui formulasi tersebut, berdasarkan fakta bahwa:

• suatu kata dianggap penting dalam dokumen kalau sering muncul, tetapi tidak terlalu sering. Maka term frequency (TF) yang tinggi akan lebih baik.
• suatu kata dianggap lebih spesifik dalam dokumen, bila tidak banyak dokumen pada koleksi yang mengandung kata tersebut.Maka document frequency (DF) yang rendah akan lebih baik. Karena berlawanan, digunakanlah formulasi  'lawan' atau dalam bahasa matematika: inverse. Sehingga yang dihitung adalah IDF (inverse document frequency)
• Selanjutnya, bobot kata dapat diformulasikan dalam bentuk perkalian atau kombinasi antara TF dan IDF.

Model statistik sederhana, bobot adalah perkalian sederhana antara TF dan IDF untuk setiap kata.
Model statistik yang lebih kompleks (probabilistik), bobot adalah perkalian atau kombinasi yang agak kompleks sedikit antara TF, IDF dan komponen probabilistik tentunya.

Beberapa search engine untuk mengindeks dokumen web juga memperhatikan kata-kata penting tidak hanya berdasarkan kemunculan atau frekuensi. Misalnya bila suatu kata pada dokumen web mengandung tag-tag khusus, seperti bold, italic, anchor text (link), dan seterusnya, ia akan diberi bobot yang lebih tinggi atau penambahan bobot di luar konteks term frequency (kemunculan kata) tadi.

Bagaimana mengurutkan dokumen dari yang paling relevan (cocok) dengan preferensi pengguna?

Bobot setiap kata pada kueri dijumlahkan, kemudian dihitung nilainya untuk semua dokumen yang mengandung kata-kata tersebut, baik sebagian maupun seluruhnya (selanjutnya saya sebut sebagai dokumen yang ditemukan).
Kemudian nilai tersebut diurutkan secara menurun (descending). Maka penjumlahan bobot yang paling besar, tentu dianggap paling relevan oleh pengguna. Itulah yang mesin IR simpulkan.


Meningkatkan Ranking Dokumen (relevansi)

Beberapa model sistem IR mengembangkan teknik pengolahan bobot yang lebih advance, tidak hanya sekedar penjumlahan bobot. Nah, ada lagi besaran yang akan dihitung, yang disebut dengan kemiripan (similarity) antara dokumen yang ditemukan dengan kueri user.
Pada umumnya, perhitungan kemiripan yang digunakan adalah model ruang vektor, setiap penjumlahan bobot kata dari dokumen-dokumen yang ditemukan dilakukan secara vektor, dengan dimensi n (atau sejumlah kata pada kueri). Penjumlahan bobot kata untuk kueri pun sama, dilakukan secara vektor.

Dalam ruang berdimensi n, maka vektor itu dapat menuju ke segala arah. (bayangkan saja dimensinya ada 3 atau vektor di dalam ruang XYZ).
Bila vektor kueri menunjuk ke arah atas tegak lurus misalnya, maka dokumen yang paling mirip dengan kueri tentu saja yang arah vektornya ke atas juga, tidak mungkin yang agak horizontal misalnya.
Nah, cara yang paling mudah, adalah hitung sudut yang dibentuk antara vektor kueri dengan vektor dokumen.
Semakin mirip, maka sudutnya akan semakin mendekati nol. Kalau dokumen sama dengan kueri, maka vektornya akan berhimpitan, atau sudutnya NOL.

Kalau sudah pakai konsep itu, maka perhitungan kemiripan dapat dilakukan dengan menggunakan rumus cosinus, dan disebutlah teknik ini dengan cosine similarity antara dokumen dengan kueri.
Kenapa cosinus (COS) ? karena cosinus kan menghitung antara kaki-kaki yang membentuk sudut. Kaki-kaki ini adalah vektor dokumen dan vektor kueri.

Kalau kata anak-anak SMA:  SINCOSTAN  = de-mi sa-mi, de-sa
de-mi (depan - miring) SIN,    sa-mi (samping - miring) COS,  de-sa (depan - samping) TAN

Apaan tuh?
Itu adalah trigonometri segitiga siku-siku, untuk menghitung sudut teta dalam SINUS, COSINUS dan TANGEN
Kalau lupa rumusnya, buka buku SMA lagi aja deh....

Setelah similarity diperoleh, maka nilai yang mendekati 1 (atau sudutnya mendekati 0) dianggap paling mirip. Jadi, kembali urutan dokumen dari yang paling relevan sampai yang tidak relevan dapat diperoleh dari mengurutkan nilai similarity antara kueri user dengan masing-masing dokumen yang ditemukan.

Selesai deh kerjaan mesin IR.

Search Engine Optimization (SEO)

Trus, apa yang bisa dilakukan untuk halaman web kita bisa paling relevan (muncul di peringkat atas) saat user memasukkan kata kunci?
Nah, langkah-langkah mengoptimasinya, ilmunya ada pada pakarSEO Ali Akbar.

Cara mudahnya adalah, pilih kata-kata penting yang kira-kira akan dicari pengguna, tentu saja topiknya adalah yang sedang kita bahas dalam web atau blog kita.
Seringlah sebutkan kata itu di dalam dokumen, tapi jangan terlalu sering (meningkatkan frekuensi).
Karena mesin pencari menambahkan bobot lain selain dari frekuensi kemunculan, maka tandai kata itu dengan tag-tag khusus, misalnya bold, italic, underline, font increase, font color, dsb.
Selain itu, karena mesin pencari juga memberi bobot lebih pada zone (istilah baru lagi), maka masukkan kata penting itu di dalam zone.


Zone

Istilah baru lagi muncul.
Zone adalah beberapa area di dalam dokumen yang penting, seperti judul dokumen (title), nama file, nama URL, alamat URI, maupun informasi meta dokumen lainnya (kalau dokumen web, berarti yang berada di dalam tag HEADER). Silakan masukkan kata penting tersebut di dalam zone tadi, maka bobotnya akan menjadi lebih tinggi, sehingga kemungkinan masuk ke halaman 1 mesin pencari semakin besar.

Silakan mencoba. semoga bermanfaat.

Bila anda merujuk blog ini untuk tulisan ilmiah, sebaiknya rujuk buku text nya: Modern Information Retrieval  (Ricardo Baeza) atau Introduction to Information Retrieval (Christopher D. Manning). Di sana bahasannya lebih lengkap, dan rumus-rumus juga ada.