Incident Matrix dan Inverted Index

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.

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

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.

approach,1 Doc 3
breakthrough,1 Doc 1
drug,2 Doc 1 Doc 2
for,3 Doc 1 Doc 3 Doc 4
hopes,1 Doc 4
new,3 Doc2 Doc3Doc4
of,1 Doc 3
patients,1 Doc 4
schizophrenia,4 Doc 1 Doc 2 Doc 3 Doc 4
treatment,1 Doc 3

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.

Musik dan Billyard di Asian Institute of Technology (AIT)

Seharian kuliah dan belajar jika tidak diselingi dengan hiburan bisa pecah kepala. Untungnya di tempat saya kuliah tersedia studio musik gratis. Dalam rangka acara Welcome Show mahasiswa baru kami dari persatuan mahasiswa Indonesia Thailand (PERMITHA) cabang AIT akan menyumbangkan beberapa kontes dari dance, music dan talent.

Yang terpenting dari adanya acara sebenarnya adalah kumpul-kumpulnya karena akibat kesibukan, biasanya kami jarang bertemu satu sama lain. Karena jauh dari kampung halaman, kami merasa seperti saudara sendiri, dan saat berkumpul adalah saat yang tepat untuk menumpahkan uneg-uneg di kepala, dari masalah studi hingga masalah keluarga bahkan keuangan.

Student Union Café (SU Café) merupakan sarana mengusir penat kami para mahasiswa. Syukurlah dengan aturan baru pemerintah Thailand, di seluruh kampus tidak boleh diperjual belikan minuman keras. Sebelum berlatih, kami memanfaatkan meja billyard yang ada, lumayan. Bagi mahasiswa apa sih yang tidak menarik dari yang gratisan, he he.

Seperti biasa, jari-jari terasa sakit karena lama tidak menyentuh senar gitar. Untungnya tangan masih lincah dan feeling masih ok. Karena kami rata-rata sudah berumur (aliran 80-an) terpaksa kami mencari lagu yang slow, misalnya lagu “love will keep us alive” yang dibawakan oleh group Eagles di tahun 90-an. Mengingatkan saya ketika akhir-akhir SMA dahulu.