Karena kelemahan scoring dengan Jaccard adalah tidak disertakannya frekuensi suatu term dalam suatu dokumen, maka diperlukan skoring dengan kombinasi dari Term Frequency dan Invers Document Frequency atau disingkat tf-idf.

Term Frequency (tf)

Tf menyatakan jumlah berapa banyak keberadaan suatu term dalam satu dokumen dan kemudian dilogaritmikan agar mengurangi besarnya bilangan, dimana logaritmik suatu bilangan akan mengurangi digit jumlah, misalnya 1000 dengan log (1000) hanya menghasilkan angka tiga. Rumus Tf adalah sebagai berikut:

Jadi jika suatu term terdapat dalam suatu dokumen sebanyak 5 kali maka diperoleh bobot = 1 + log (5) =1.699. Tetapi jika term tidak terdapat dalam dokumen tersebut, bobotnya adalah nol.

Inverse Document Frequency (Idf)

Terkadang suatu term muncul di hampir sebagian besar dokumen mengakibatkan proses pencarian term unik terganggu. Idf berfungsi mengurangi bobot suatu term jika kemunculannya banyak tersebar di seluruh koleksi dokumen kita. Rumusnya adalah dengan inverse document frequency. Document frequency adalah seberapa banyak suatu term muncul di seluruh document yang diselidiki.

Sehingga bobot akhir suatu term adalah dengan mengalikan keduanya yaitu tf x idf. Berikut ini kita mengambil contoh suatu kasus. Misalnya kita memiliki vocabulary sebagai berikut:

girl, cat, assignment, exam, peace

Dan kita diminta merangking suatu query: “girl exam” terhadap dua dokumen di bawah ini:

Document 1 : exam peace cat peace peace girl

Document 2 : assignment exam

Langkah pertama adalah kita membuat tabel dengan term urut abjad (lexicography) dan mengisi nilai bobotnya untuk document 1 dan document 2. Setelah itu menghitung score(q,d1) dan score(q,d2) yang menyatakan berturut-turut skor rangking query terhadap dokumen 1 dan dokumen 2.

Bagaimana angka-angka tf-idf tersebut muncul? Jawabannya adalah dengan menghitung bobotnya lewat rumus tf x idf di atas. Perhatikan exam dan girl yang merupakan query (ditandai kotak hitam). Tampak untuk dokumen 1 score-nya adalah 0 + 0.3 = 0.3, sementara untuk dokumen 2 score-nya 0 + 0 = 0, jadi jika diranking, yang pertama adalah dokumen 1 dan berikutnya dokumen 2. Bagaimana menghitung bobot Wt,d untuk girl pada document 2 di atas yang diperoleh hasil 0.3? berikut ini jalan lengkapnya:

Coba hitung bobot di kolom yang lainnya siapa tahu saya salah hitung.

Antara query dengan document perlu dihitung skor untuk mengetahui ranking hasil dari searching kita. Salah satu teknik termudah adalah dengan koefisien Jaccard. Koefisien ini mudah karena kita tinggal mencari item mana saja yang sama dibagi dengan total item keduanya.

Berikut ini adalah contoh sederhana kasus menghitung koefisien Jaccard. Jika diketahui A={1,2,3,4}, B={1,2,4}, dan C={1,2,4,5}, berapakah Jaccard (A,B), Jaccard(B,C), dan Jaccard(A,C). Berikut ini penyelesaiannya.

Berikutnya untuk kasus query dan document. Misalnya kita punya query: ides of march dengan dua buah document yaitu doc1: caesar died in march, doc2: the long march. Cari koefisien jaccard antara query dengan doc1 dan doc2.

Koefisien jaccard memiliki kelemahan dimana koefisien ini tidak memperhatikan term frequency (berapa kali suatu term terdapat di dalam suatu dokumen). Perlu diketahui, bahwa terms yang jarang muncul dalam suatu koleksi sangat bernilai dari sisi informasi, tetapi koefisien Jaccard tidak mempertimbangkan hal ini. Jadi kita butuh cara lain untuk menormalisasikannya.

Entropy mengukur ketidakpastian suatu variabel acak. Istilah ini pertama kali saya kenal di mata pelajaran kimia. Misal kita punya uang logam, jika kita lempar kita tidak memiliki kepastian apakah yang diperoleh gambar atau angka. Bagaimana dengan dadu? Tentu saja memiliki ketidak pastian, bahkan melebihi ketidakpastian dari uang logam yang dilempar. Masalahnya jika dadu yang dilempar memiliki ketidakpastian yang lebih tinggi dari uang logam yang dilempar, berapa besar? Nah kita akan coba bahas dengan konsep entropy. Manfaatnya adalah, konsep ini diterapkan untuk pembuatan pohon keputusan (decision tree).

Rumus Entropy

Entropy menggunakan konsep probabilitas dalam menentukan besar entropy suatu kejadian. Misal probabilitas uang yang normal adalah ½ untuk gambar dan ½ untuk angka, sementara untuk dadu tiap angka memiliki peluang yang sama yaitu 1/6 dengan anggapan dadunya normal (fair). Rumus entropy adalah sebagai berikut:

Berapakah entropy fair coin?

Masukan saja rumus di atas, maka diperoleh

H(x)=-( 0.5 * log(0.5) + 0.5 * log(0.5)) = 1.

Oiya, logaritmic yang digunakan adalah basis 2 (bukan sepuluh). Nah bagaimana jika coinnya tidak normal, misal peluang muncul gambar = 0.75 dan angka =0.25? Jawabannya adalah dengan rumusan di atas juga,

H(x) = – (0.75*log(0.75)+0.25*log(0.25)) = -(-0.3112-0.5)=0.8112.

Berapakah entropy fair dice (dadu normal)?

Entropy ini akan digunakan untuk menentukan percabangan pohon keputusan. Misalnya ada data dengan atribut usia, pelajar/tidak, income, dan credit rating yang menentukan seseorang membeli barang. Pertama-tama dihitung entropy atribut-atribut itu untuk mencari information gained berdasarkan entropy itu, jadi logikanya makin rendah entropy-nya maka makin kuat atribut itu menjadi akar.

Misal kita memiliki data training terhadap beberapa query dengan term-term tertentu berikut ini.

Pertanyaannya adalah berapakah nilai g –nya?

Sebelum menjawab pertanyaan itu terlebih dahulu didefinisikan istilah-istilahnya. Kita misalnya memiliki query “like dog cat temle ant bird wine girl”. Misalnya kita akan menentukan bobot antara ST dengan SB, maksudnya ST adalah letak suatu query pada Dokument (docID) pada Title atau Body, yang disingkat jadi T dan B pada S. Misal pada data pertama Ф1, query like ada di document ID = 17 pada Body, tetapi tidak ada di Title. Sementara ‘r’ adalah penilaian dari pakar (humen expert) yang menyatakan apakah data itu relevan atau tidak. Pada kasus ini diberi angka nol (0) berarti tidak relevan, yang nantikanya akan dijumlahkan dengan variabel n01n (artinya number of St=0, Sb=1 dan tidak relevan (n)).

Sementara g sendiri adalah bobot opimal yang akan kita cari dengan rumusan di bawah ini (buka buku Information Retrieval oleh Manning):

Masukan data-data n10r, n01n, n10r, n10n, n01r dan n01n. Sebagai contoh, n10r adalah jumlah St=1,Sb=0, r=1 dimana di tabel atas berjumlah 0, dan seterusnya.

Sehingga diperoleh nilai g

Bab pertama pada mata kuliah Information Retrieval adalah seputar bagaimana kita mencari suatu kata dalam beberapa berkas yang telah kita simpan. Berkas-berkas tersebut berupa format text dari aplikasi-aplikasi pengolah kata (word processing).

Incident Matrix

Jika kita ingin mengetahui dalam document mana saja kah kata tertentu, misalnya Indonesia berada? Caranya adalah kita melihat kata Indonesia dalam incident matrix kemudian melihat dalam matrix itu dalam dokumen mana saja kata Indonesia berada. Dalam prakteknya incident matrix sangat memboroskan memori karena seperti kita perkirakan, jumlah keberadaan sangat sedikit, atau dengan kata lain banyak jumlah nol dibanding satu.

Berikut ini contoh soal dari buku referensi Information Retrieval karya Manning, dkk tentang pembuatan incident matrix dan inverted index. Jawaban soal dapat Anda lihat di situs ini, walaupun baru bab 1 saja yang diselesaikan.

Doc 1 – breakthrough drug for schizophrenia
Doc 2 – new schizophrenia drug
Doc 3 – new approach for treatment of schizophrenia
Doc 4 – new hopes for schizophrenia patients

Perhatikan soal di atas, dimana misalnya kita memiliki empat dokumen. Dokumen satu berisi kata breakthrough, drug, for, schizophrenia. Tentu saja ini hanya perumpamaan, karena satu dokument tentu bisa saja hingga berjuta-juta kata. Bagaimana cara membuat incident matrixnya? Sesuai dengan namanya, incident matrix berarti matriks yang berisi keberadaan suatu kata dalam dokumen. Jadi kita cari kata ‘breakthrough‘ ada di dokumen satu, ‘drug‘ di dokumen satu dan dua, dan seterusnya.

Terlepas dari kelemahan dari sisi kapasitas matriks yang besar, incident matrix sangat baik digunakan untuk mencari kata dengan operasi boolean (boolean retrieval). Misalnya kita diminta mencari kata-kata dengan boolean:

for AND NOT (drug OR approach)

Maka kita dengan mudah melakukan operasi logika dari incident matrix.

Term vectors
for – 1 0 1 1
drug – 1 1 0 0
approach – 0 0 1 0

Seperti operasi aljabar boole yang telah kita pelajari dari mata kuliah logika, kita kerjakan terlebih dahulu yang dalam kurung (drug OR approach).

1 1 0 0 OR 0 0 1 0 = 1 1 1 0

Setelah operasi NOT diperoleh invers dari jawaban di atas yaitu : 0 0 0 1 dan terakhir dilakukan proses AND dengan for:

1 0 1 1 AND 0 0 0 1 = 0 0 0 1

Inverted Index

Bentuk incident matrix jarang sekali digunakan saat ini. Bentuk yang terkenal adalah Inverted Index, di mana Term di hubungkan dengan lokasi document dimana term tersebut berada. Term adalah suatu kata kunci yang dijadikan objek searching. Pada contoh di atas kita menggunakan kata, walaupun terkadang kita harus memanipulasi kata tersebut, misalnya words yang jamak kita konversi menjadi word (kata dasarnya), serta metode-metode lain yang dibahas di buku Manning di bab-bab berikutnya.

Perhatikan bentuk inverted index di atas. Suatu Term, misalnya ‘for‘ memiliki frekuensi keberadaan sebanyak 3. Di sebelah kanannya berjajar posting list yang sudah tersortir berdasarkan lokasi dokumen, diberi nama docID. Sebenarnya bentuk inverted index tidak seperti di atas, bentuk di atas hanya mempermudah pengetikan saja, aslinya adalah sebagai berikut:

Maaf tulisannya kayak gitu .. tapi jika Anda bisa membacanya, dijamin seumur hidup Anda bisa membaca seluruh jenis tulisan :D.

Kompresi sangat bermanfaat karena kecepatan prosesor dalam melakukan encode dan decode jauh di atas kecapatan baca dan tulis dari disk ke memory. Apalagi jika kita menggunakan Single-Pass In Memory Indexing (SPIMI) dimana kita dapat melakukan kompresi pada Terms dan Postings. Berbagai metode dapat kita gunakan untuk melakukan kompresi pada Terms, sementara untuk Postings dapat kita lakukan dengan dua cara yaitu:

1. Storing successive docIDs, dengan kata lain menggunakan offset. Misal dari pada kita menulis <1001,1010,1052,…> kita dapat menuliskannya dengan <1001,9,42,…> dimana menghasilkan angka yang jauh lebih kecil.
2. Menggunakan variable size dari prefix code. Caranya adalah dengan melihat nilai maksimum dari sebaran angka, akibatnya terhindar dari pemborosan kapasitas byte tiap Posting. Nah, akan kita bahas penggunakaan variable size ini dengan kode Elias gama dan delta.

Elias Gamma Coding

Metode ini dikembangkan oleh Peter Elias. Dengan teknik pengkodean:

1. Tulis dalam biner
2. Jumlah bit pada proses no.1 dikurang satu untuk menentukan jumlah nol (zeros) yang harus ditambahkan di muka angka tersebut.

Contoh kita punya bilangan 11 langkah pertama adalah konversi 11 menjadi biner, yakni 1011. Langkah dua menghasilkan tiga yang berasal dari 4 bit dikurang satu. Hasilnya adalah 0001011. Deretan angka 11,55, dan 27 dengan elias gamma code menjadi 00010110001111000011011.

Bagaimana dengan docede-nya? Caranya gampang, hitung jumah nol (zero) sebelum ditemukan bilangan 1, misalnya kita akan mendekode 0001011. Karena ada 3 zero maka (3+1) setelah zero itu adalah bilanganya, yaitu 1011, yang jika dikonversi ke desimal menjadi 11. Apa fungsi Elias Gamma Coding tersebut? Tentu saja manfaatnya adalah kita dapat mengirim tiga angka berjajar sekaligus, sebab jika kita hanya meng-concatenate tiga bilangan tersebut akan tidak bermakna, misalnya tiga bilangan tersebut di atas jika dikirim 1011111111011 ada berjuta2 variasi kombinasi biner tersebut yang setara dengan desimalnya.

Elias Delta Coding

Seperti Elias Gamma, kode ini ditemukan oleh Peter Elias. Kode ini menerapkan juga metode pada gamma coding, terutama di bagian kepala. Tekniknya adalah sebagai berikut:

1. Cari pangkat tertinggi binernya, misalnya desimal 11 jika dibinerkan menjadi 1011 dimana pangkat tertingginya adalah 3. Jadi N’=3.
2. Gunakan Gamma Coding untuk mengkodekan bilangan N dimana N=N’+1. Jadi untuk kasus desimal 11 maka kita harus membuat Gamma Coding dari 4 yaitu 00100.
3. Tambahkan sisa N’ binary pada hasil no.2. Jadi diperoleh jawaban 00100011.

Berikutnya adalah medekode Elias Delta Coding, prinsipnya adalah kebalikan dari langkah satu sampai tiga di atas. Misalnya kita akan mendekode 00100011.

1. Temukan jumlah zero sebelum ditemukan angka satu, yaitu 00, berjumlah dua. Berarti ada (2+1) angka yang harus diperhatikan setelah dua angka nol ini yaitu 100 yang dalam desimalnya berarti 4, jadi kita mendapatkan N’ dengan N-1 = 4-1 = 3.
2. Jika N’ telah diketahui, yaitu 3 maka ada tiga bit tersisa yang menjadi bagian bilangan itu yakni 011. Jadi diperoleh jawaban 1011 yang artinya 11.

Jika kita diberikan rentetan biner sebagai berikut: 00110000110011110010100111110000 merupakan deretan angka 35, 101, dan 112. (Perhatikan warna biner di atas untuk memudahkan).

Reference

Manning, Christopher D., Prabhakar Raghavan and Hinrich Schütze (2008), Introduction to information retrieval, Cambridge: Stanford University.