Rabu, 05 Februari 2014

Pembuatan Korpus dan Indeks – Temu Kembali Informasi


Oke masuk ke tahap selanjutnya dari artikel sebelumnya, ketika kita melakukan suatu pencarian informasi maka tentu pasti ada batasan/ruang lingkup informasi yang akan kita peroleh. Semisal Google, ruang lingkup pencarian kita adalah seluruh web yang ada di jagat internet ini, WAW. Ruang lingkup pencarian ini selanjutnya akan kita sebut korpus atau koleksi dokumen (teks/suara/citra). Nah, sesuai dengan ilmu yang saya pahami kita akan mempelajari tentang dokumen berbentuk teks.

Sebagai contoh bentuk korpus itu seperti apa, bisa teman-teman lihat pada artikel yang ini. Ya bentuknya tentu saja sebuah teks yang terdapat pada sebuah file atau lebih. Kebetulan model korpus yang saya buat pada artikel tersebut adalah file berformat XML. Inilah yang disebut tahap pembuatan korpus (processing). 

Sebenarnya dalam membuat korpus tidak ada suatu batasan apapun, baik bentuk, jumlah, ataupun format. Kalau mengambil contoh yang telah saya buat di post tersebut, tujuan dibuatnya korpus berbentuk XML adalah ingin membedakan informasi yang ada pada artikel tanaman obat (judul, isi, dan lain-lain). Dalam XML, kita dapat mendefinisikan tag secara bebas, tidak seperti HTML yang memang ada aturannya. Oleh karena itu, di artikel tersebut saya berusaha memisahkan informasi yang berbeda untuk masuk ke tahap berikutnya. Nah, apakah teman-teman bisa membayangkan bentuk korpus yang dimiliki oleh Google? Saya pun tidak tahu :D. Lalu bagaimana bisa Google mengumpulkan jutaan/milyaran informasi yang tersebar di jagat internet? Apakah mungkin manusia yang melakukannya satu persatu? Atau secara otomatis? :D.

Tahap selanjutnya adalah pembuatan indeks (indexing). Indeks ini akan menentukan bagaimana hasil informasi yang kita peroleh nantinya bersama dengan proses pembobotan. Ya, 10 link yang kalian lihat pada halaman pertama ketika searching merupakan hasil pembobotan sedemikian rupa dengan indeksnya. Tentu saja 10 informasi pada halaman pertama tersebut diharapkan sesuai dengan kebutuhan user. Bagaimana jika tidak? Mungkin ada yang salah pada pembobotannya atau kata kunci yang kalian masukkan pada search engine :D.

Pertama-tama, mari kita bahas bagaimana suatu indeks dibuat. Misal saya memiliki 3 dokumen (D) dengan isi kalimat singkat seperti dibawah ini :
D1 :  Ayah dan ibu hari ini di rumah saja dan aku pergi ke mall. 
D2 : Ibu dan adik pergi ke pasar membeli mangga. 
D3 : Aku dan ibu di rumah karena hari ini hujan.
Kemudian, proses pembuatan indeks kurang lebih tahapnya seperti sekaligus akan saya coba jabarkan menggunakan contoh ketiga dokumen di atas.

Struktur dokumen
Karena ini contoh sederhana, tidak ada hal yang harus dipisahkan seperti kasus pada post ini. Ini proses pemilihan hal apa yang akan diindeks dari korpus yang tersedia.

Tokenisasi – pemisahan kata dari dokumen
Kira-kira dari contoh di atas kita akan punya berapa kata?
ayah, dan, ibu, hari, ini, di, rumah, saja, aku, pergi, ke mall, pasar, adik, membeli, mangga, karena, hujan.
Tentu kita tidak mempedulikan apakah hurufnya besar/kecil, yang penting adalah tidak ada duplikasi dan semacamnya.

Stopwords – pembuangan kata berdasarkan aturan
Aturan yang umum adalah membuang kata-kata hubung, karena kata ini jumlahnya bisa sangat banyak padahal informasinya KURANG dibutuhkan, ingat! KURANG bukan tidak dibutuhkan sama sekali. Pada kasus tertentu hal ini sangat diperlukan terutama masalah semantik. Contoh kata hubung dalam kasus ini: dan, ini, di saja, ke, karena. Sehingga kata yang kita miliki adalah :
ayah, ibu, hari, rumah, aku, pergi, mall, pasar, adik, membeli, mangga, hujan.
Stemming – pemotongan imbuhan
Pemotongan imbuhan sebenarnya opsional mirip seperti pembuangan kata, tujuannya adalah meminimalisir duplikasi. Dalam kasus ini: membeli. Pada dua kata ini terdapat imbuhan, jika imbuhannya dibuang maka menjadi: beli. Teknik stemming ini sangat beragam dari yang mudah hingga sulit. Ingat ini opsional, dalam kasus ini saya menggunakannya sehingga kata yang kita miliki :
ayah, ibu, hari, rumah, aku, pergi, mall, pasar, adik, beli, mangga, hujan
Untuk memudahkan saya membuat dua tabel seperti di bawah ini. Total dokumen adalah 3 (N):

Tabel tf (frekuensi kemunculan kata suatu dokumen)
tf
ayah
ibu
hari
rumah
aku
pergi
mall
pasar
adik
beli
mangga
hujan
D1
1
1
1
1
1
1
1
0
0
0
0
0
D2
0
1
0
0
0
1
0
1
1
1
1
0
D3
0
1
1
1
1
0
0
0
0
0
0
1

Tabel df (banyaknya dokumen yang mengandung kata tersebut)
df
ayah
ibu
hari
rumah
aku
pergi
mall
pasar
adik
beli
mangga
hujan
D
1
3
2
2
2
2
1
1
1
1
1
1

Nah, karena ini adalah contoh sederhana tentu saja nilainya tidak besar sehingga mudah perhitungannya nantinya hehe :D. Mengerti kan maksud tabel ini? Kalau bingung tanya aja ya :D

Pembobotan
Dari tabel tf dan df, kita akan membuat sebuah tabel baru untuk menyimpan nilai bobot yang kita beri nama nilai idf (inverse document frequency) = log(N/df) dimana N adalah jumlah dokumen yang ada yakni 3. Jadi tidak akan mungkin nilai df yang ada melebihi N :D. Nilai idf inilah yang akan menjadi standar kita untuk menghitung urutan informasi yang akan dihasilkan.

Setelah dihitung kurang lebih seperti ini tabelnya:
Tabel idf
idf
ayah
ibu
hari
rumah
aku
pergi
mall
pasar
adik
beli
mangga
hujan
D
0.48
0
0.18
0.18
0.18
0.18
0.48
0.48
0.48
0.48
0.48
0.48
Contoh : idf "ayah" = log(3/1) = 0.48
Pembuatan indeks telah selesai sampai pada tahap Pembobotan untuk menghasilkan tabel idf. Ya inilah tujuan kita, menghitung secara sistematis apa informasi yang ada dalam ketiga dokumen tersebut dan hal itu direpresentasikan oleh nilai pada tabel idf yang kita buat. Mengapa kata “ibu” bernilai 0? ya karena kata “ibu” muncul di seluruh ketiga dokumen (df = N), ini artinya kata “ibu” membuat informasi malah menjadi kabur dan tidak bisa merujuk secara spesifik pada salah satu dokumen. Bagaimana kalau kita mencari informasi dengan kata kunci “rumah ibu”? Kira-kira dokumen mana yang paling relevan dengan kata “rumah” dan “ibu”. Hal ini akan kita kupas pada post berikutnya yaitu Retrieving hehe :D.

Ribet? Pusing? Tenang, bagi yang tidak mau pusing dengan tahap indexing ada banyak tools yang mempermudah kita salah satunya Sphinx, seperti salah satu artikel ini yang saya buat sebelumnya. Kita hanya perlu mengatur konfigurasi, ya konfigurasi tanpa perlu pusing berpikir algoritmanya. Kalau masih mengerti silakan aja ke artikel ini, disana saya membuat contoh algoritma dan kode nya menggunakan PHP. Satu hal yang perlu diingat, yang saya sampaikan ini murni hal dasar dan saya belum menguasai lebih jauh lagi karena masih banyak metode yang sangat kompleks untuk menghasilkan informasi yang relevan, ya seperti Google sekarang. Tetapi ini bisa menjadi pondasi bagi teman-teman berpikir bagaimana temu kembali informasi bekerja. Terima kasih :D.


3 komentar: