Relevance Feedback (RF), Query Expansion (QE), dan perbedaan diantara keduanya

Relevance Feedback (RF).

Relevance Feedback (RF) merupakan suatu teknik temu kembali informasi dimana user memberikan feedback (pengaruh) pada dokumen hasil temu kembali yang dianggap relevan.

Query expansion (QE).

Query Expansion (QE) merupakan suatu teknik kembali informasi untuk memperbaiki query sehingga dapat memperoleh hasil yang lebih baik. Contoh: pada search engine Google kita mengetikan: tki temu kembali infromasi. Maka search engine melakukan query expansion (QE) dengan menampilkan saran: Did you mean: tki temu kembali informasi.

Pada dasarnya kedua teknik ini (RF dan QE) tujuannya adalah untuk memperbaiki hasil temu kembali agar hasil dokumen/pencarian yang dilakukan menjadi lebih baik. Namun diantara keduanya memiliki perbedaan.

Perbedaannya yaitu:

Pada RF ada tanda/input/klik dari user untuk memperbaiki query sedangkan pada QE tidak ada (sistem secara automatis memperbaiki query).

Download this article: Relevance Feedback (RF), Query Expansion (QE), dan perbedaan diantara keduanya

Pengukuran Kesamaan Dot Product

Dot product digunakan untuk mengukur kesamaan (similarity) antara dua vektor.

Perhitungan dot product yaitu:
Misalkan terdapat vektor dj dan q, rumus dot product yaitu:

Cara perhitungannya menjumlahkan masing-masing hasil kali antara anggota vektor dj dan q.
Misalkan dj=[1 2 3 4 5] dan q=[6 7 8 9 10],
Maka:

sim(dj,q)=(1×6)+(2×7)+(3×8)+(4×9)+(5×10)
sim(dj,q)=6+14+24+36+50
sim(dj,q)=130
Jadi hasil pengukuran kesamaan dot product dj dan q adalah 130

Download this post: Pengukuran kesamaan dot product.pdf

 

Pembobotan tf.idf

Menghitung Term Frequency (tf)
Term frequency (tf) merupakan frekuensi kemunculan term (t) pada dokumen (d).
Contoh:
Terdapat kalimat:
Saya sedang belajar menghitung tf.idf. Tf.idf merupakan frekuensi kemunculan term pada dokumen. Langkah awal perhitungan tersebut adalah menghitung tf, kemudian menghitung df dan idf. Langkah terakhir menghitung nilai tf.idf. Mari kita belajar!
Catatan: tiap kalimat dianggap sebagai dokumen.
Tentukan nilai tf!

Jawaban:
Jadi dokumen tiap kalimat ditandai:
Saya sedang belajar menghitung tf.idf. Tf.idf merupakan frekuensi kemunculan term pada dokumen. Langkah awal perhitungan tersebut adalah menghitung tf, kemudian menghitung df dan idf. Langkah terakhir menghitung nilai tf.idf. Mari kita belajar!
Tabel tf:

Menghitung document  frequency (df)
Document  frequency (df) adalah banyaknya dokumen dimana suatu term (t) muncul.
Contoh: Dari soal yang sama pada menghitung tf, tentukan nilai df!

Jawaban:
Nilai df:

Atau:

Menghitung invers document frequency (idf)

Contoh: Dari soal yang sama pada menghitung df, hitung nilai idf!
Jawaban:

Contoh: Dari soal yang sama pada menghitung df, hitung nilai idf! (dengan jumlah dokumen=N)
Jawaban:

Contoh: Dari soal yang sama pada menghitung df, hitung nilai idf! (N=1000)
Jawaban:

Menghitung tf.idf
Hasil kali tf x idf
Contoh: Dari soal yang sama pada menghitung df, hitung nilai tf.idf! (dengan jumlah dokumen=N)
Jawaban:

Download this article: Pembobotan tf.idf

Pembobotan Temu Kembali Informasi

Dalam temu kembali sebuah kata perlu diberi bobot, makin sering suatu kata muncul pada suatu dokumen, maka diduga kata tersebut semakin penting dalam dokumen.
Pendekatan yang digunakan untuk menghitung bobot:
tf
tf.idf
BM25, dan lain-lain.

 

Masalah pada stemming

Masalah pada proses stemming yaitu:

1. Understemming,
   yaitu: jumlah kata/imbuhan yang dipotong terlalu sedikit, misalnya ‘pengorbanan’ menjadi ‘korbanan’
2. Overstemming,
   yaitu: jumlah kata/imbuhan yang dipotong terlalu banyak, misalnya ‘mencapai’ menjadi ‘capa’

Stemming

Stemming merupakan proses membuang prefiks dan sufiks (secara morfologi) dari suatu kata berimbuhan menjadi kata dasar. Program stemmer (program untuk melakukan proses stemming) untuk kata bahasa inggris: http://www.tartarus.org/~martin/PorterStemmer/

Aturan pemotongan pada proses stemming: P1 (kondisi) S2 -> P2S2 Yaitu jika sebuah kata mempunyai prefiks (awalan) P1 dan sufiks (akhiran) S1 memenuhi kondisi yang diberikan, maka P1 dan S1 diganti menjadi P2 dan S2. Kondisi dapat berupa operator AND, OR, atau NOT. Setiap bahasa melakukan proses stemming yang berbeda-beda disesuaikan dengan aturan bahasa tersebut dalam prefiks dan sufiks.

Contoh Stemming:

Lakukan proses stemming untuk kata-kata berikut:

1. Dermawan

2. Awan

dengan (m>1) wan->

Jawaban:

Dari Soal diketahui aturan stemming yaitu: (m>1)wan ->

dengan demikian P1 tidak ada, S1 adalah wan, dan S2 adalah null (kata kosong). Dan m adalah banyaknya suku kata pada kata dasar.

1. Dermawan, m = 2 (derma) wan ->

    dengan proses stemming menjadi: ‘derma’

2. Awan, m = 1 Tidak memenuhi kondisi.

    Sehingga dengan proses stemming tetap: ‘awan’

Bahan Bacaan (Referensi/resources) TemuKembali Informasi

Bahan bacaan untuk belajar tentang Information Retrieval (IR) atau Temu Kembali Informasi (TKI), yaitu:
Webpage:
–http://www.cs.unt.edu/~rada/CSCE5200
–check periodically for updates, announcements, etc.
Textbook:
–Introduction to Information Retrieval (Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze)
–Readings in Information Retrieval (K.Sparck Jones and P. Willett)
–Modern Information Retrieval (Ricardo Baeza-Yates and Berthier Ribeiro-Neto)

Boolean Model

Boolean  retrieval merupakan model untuk information retrieval (IR) yang bertujuan untuk membentuk kueri dalam format ekspresi Boolean dari term-term, seperti AND, OR dan NOT.
Seperti namanya Boolean Model , maka setiap term dalam setiap dokumen merupakan vektor 0 (nol) atau 1 (satu). Bernilai 1 jika term tersebut terdapat dalam dokumen, dan benilai 0 jika term tersebut tidak terdapat dalam dokumen.
Contoh:
Apabila terdapat dokumen:
1.  Fahri menghampiri apartemen Maria untuk minta
bantuan karena komputer yang digunakan untuk
menyusun tesis mengalami error. Maria menuju
apartemen tempat tinggal Fahri dan menemukan
komputer Fahri kena virus.
2.  Selama membantu menyusun tesis, timbul perasaan
cinta Maria kepada Fahri.
3.  …..
4.  …..
5.  …..
Kemudian setelah dibentuk tabel berdasarkan frekuensi kemunculan kata/term sebagai berikut:

dan dibentuk Boolean model menjadi:

Dan query nya adalah Aisyah dan Noura, bukan Fahri. Dokumen manakah yang relevan untuk query tersebut?
Langkah awal, bentuk tabel Boolean dari tabel frekuensi kemunculan kata tersebut menjadi:
Kemudian hitung bentuk vektor Boolean dari kueri.
Query (q) = Aisyah dan Noura, bukan Fahri
= (Aisyah AND Noura) NOT Fahri
= (00011 AND 00111) NOT (11010)
= (00011) AND (00101)
= 00001
Dengan demikian dokumen yang relevan dengan query adalah dokumen 5.

Download this post: Boolean model

Contoh program (source code) tokenisasi dan menghitung frekuensi kata dengan PHP

Korpus (kumpulan dokumen) merupakan format XML yang disimpan dalam ‘korpus.txt’.
Salah satu contoh langkah program yaitu:
-membuka file korpus, pada PHP dapat dilakukan dengan:
$filename = “korpus.txt”;
$handle = fopen($filename, “r”);
-menghilangkan whitespace, seperti spasi, newline, dll:
$line = preg_replace(‘/^\s*/’, ”, $line);
$line = preg_replace(‘/\s*$/’, ”, $line);
-mengubah kata-kata pada korpus menjadi huruf kecil, sehingga memudahkan proses pencarian kata pada dokumen:
$line = strtolower($line);
-tokenisasi, kemudian menyimpannya sebagai array:
$kata = preg_split(“/[\s,.:]+/”, $line);
if (preg_match(“/^[a-z]/”, $tok)) {
$freq[$tok]+=1;
$s++; //menghitung jumlah seluruh kata
}
-mengambil nilai frekuensi array tersebut.
foreach ($freq as $key => $val) {
echo “$key => $val<br />”;
}

Contoh program (source code) secara keseluruhan yaitu:
$filename = “korpus.txt”;
$handle = fopen($filename, “r”);
while (!feof($handle)) {
$line = fgets($handle); //baca per baris
$line = preg_replace(‘/^\s*/’, ”, $line);
$line = preg_replace(‘/\s*$/’, ”, $line);
$line = strtolower($line);
if ($line==”<text>”) { // awal
$start=1;
}
elseif ($line==”</text>”) {
$start=0;
}
if ($start==1 && $line!=”<text>”) {
$kata = preg_split(“/[\s,.:]+/”, $line);
foreach($kata as $tok) {

$tok=preg_replace(‘/[?!.,()*]|\”/’,”,$tok);
$tok=preg_replace(‘/^\’/',”,$tok);
if (preg_match(“/^[a-z]/”, $tok)) {
$freq[$tok]+=1;
$s++; //menghitung jumlah seluruh kata
}
}
}
}
arsort($freq); //mengurutkan kata dari frekuensi yang terbesar
foreach ($freq as $key => $val) {
echo “$key => $val<br />”;
}
fclose($handle);
?>

OK, selamat berkreasi!!!

Download this post: PROGRAM TOKENISASI DAN HITUNG FREKUENSI DENGAN PHP

Tokenisasi dan Segmentasi teks

Tokenisasi adalah  tahap pemrosesan di mana teks input dibagi menjadi unit-unit kecil yang disebut token, yang dapat berupa suatu kata, suatu angka, atau suatu tanda baca.
Segmentasi adalah proses tokenisasi sederhana.

Download this post: TOKENISASI DAN SEGMENTASI TEKS