PERANCANGAN INFORMATION RETRIEVAL SYSTEM UNTUK DOKUMEN BERBAHASA INDONESIA DENGAN MENGGUNAKAN EXTENDED BOOLEAN

Jurnal Ilmu Komputer dan Sistem Informasi

PERANCANGAN INFORMATION RETRIEVAL SYSTEM UNTUK DOKUMEN BERBAHASA INDONESIA DENGAN MENGGUNAKAN EXTENDED BOOLEAN Steven Teknik Informatika Universitas Tarumanagara Jl. S. Parman No.1, Jakarta 11440 Indonesia

email : [email protected] menggunakan model Extended Boolean. Perancangan sistem information retrieval ini bertujuan untuk menemukan sebanyak mungkin dokumen yang relevan di dalam suatu koleksi dokumen, yang sesuai dengan kueri pengguna.

ABSTRACT Information retrieval system is a system that is designed to find documents that satisfies user’s information needs. User represents his information needs in words. The word will represent the same word in documents and it’s called query. System will retrieve all relevant documents and show it to the user. This paper will describe an information retrieval system using extended boolean method. There are two methods in this system, boolean method for retrieval process and vector space method for ranking process.

2. Information Retrieval Information Retrieval System adalah sistem yang dirancang untuk menemukan dokumen yang memenuhi kebutuhan informasi penggunanya. Terdapat prosesproses yang dijalankan pada sistem. Proses-proses yang dijalankan adalah preprocessing, pencarian menggunakan Extended Boolean, dan pemeringkatan menggunakan Vector Space.

Key words : Boolean, extended booelan, information retrieval system, vector space.

1. Pendahuluan

2.1. Preprocessing

Information retrieval atau IR adalah ilmu tentang pencarian informasi, khususnya dalam bentuk teks yang dianggap memenuhi kebutuhan informasi penggunanya. Pada awalnya information retrieval hanya dilakukan oleh orang-orang dengan pekerjaan tertentu, seperti pustakawan, asisten penegak hukum, dan pekerjaan lainnya. Namun sekarang jutaan orang dapat terlibat dalam aktivitas information retrieval ketika menggunakan search engine berbasis web. IR sendiri terus berkembang seiring dengan meningkatnya kebutuhan manusia akan informasi. Peningkatan kebutuhan informasi ini mendorong munculnya sistem-sistem pencari informasi untuk memenuhi kebutuhan informasi penggunanya. Sistem information retrieval menggunakan model untuk mengukur tingkat kemiripan antara kueri yang dimasukkan dengan isi dokumen. Di dalam model tersebut terjadi proses komputasi yang akan memberikan penilaian bagi sistem mengenai seberapa dekat kemiripan antara isi dokumen dengan kueri pengguna. Beberapa model yang telah dikembangkan adalah model Vector Space, model Boolean, dan model probabilistic. Setiap model mempunyai karakteristik dan cara pengukuran kemiripan yang berbeda [5]. Berdasarkan latar belakang di atas, maka dirancanglah suatu sistem information retrieval

Preprocessing merupakan salah satu cara yang digunakan untuk meningkatkan hasil pengambilan dokumen-dokumen relevan yang terdapat di dalam koleksi dokumen. Proses ini dilakukan pada isi dokumen pada koleksi dan kueri yang dimasukkan oleh pengguna. Preprocessing terdiri dari beberapa proses, yaitu : 1. Lexical Analysis Lexical Analysis adalah proses pengkonversian term menjadi sekumpulan token. Proses ini juga disebut dengan tokenisasi. Pada proses ini umumnya karakter non-huruf seperti tanda baca, tanda hubung, angka, dan lainnya akan dihilangkan dan seluruh huruf akan diubah menjadi huruf kecil. Tujuan dari proses ini adalah mengubah term sehingga dapat dikenali oleh sistem. 2. Stopwords removal Tujuan dari proses ini adalah menghilangkan katakata yang sering muncul dan dianggap tidak berguna. Proses ini juga bermanfaat untuk mengurangi waktu yang diperlukan untuk proses indexing dan pembobotan istilah. 3. Stemming Stemming adalah proses pemotongan imbuhan suatu kata, agar kata tersebut direpresentasikan oleh sistem dalam bentuk kata dasar. Operasi ini bertujuan agar dalam proses pencarian dokumen yang relevan

183


dengan kueri, sistem mampu mengambil lebih banyak dokumen-dokumen dari koleksi dokumen yang di dalam isinya mengandung kata dasar dari kata yang ada dalam kueri. Stemming untuk bahasa Indonesia yang akan digunakan adalah Jelita Asian Stemmer. Stemmer ini merupakan stemmer yang dikembangkan dari stemmer Nazief dan Adriani. Proses stemming yang dilakukan melibatkan kamus kata dasar tiap akhir proses pemotongan imbuhan [1].

dokumen yang mirip dengan dokumen yang dibutuhkan. Tingkat kemiripan antara dokumen yang dipersiapkan dan dokumen yang didapat dari koleksi dokumen digunakan untuk melakukan pemeringkatan pada hasil pencarian [4]. Pengukuran kemiripan model ini kini telah berkembang menjadi pengukuran kemiripan antara vektor yang merepresentasikan kueri dengan vektor yang merepresentasikan dokumen. Jika salah satu kata dapat mewakili kata-kata lainnya di dalam sebuah dokumen dengan menggunakan sebuah vektor, maka sangat memungkinkan pembandingan dokumen dengan kueri untuk melihat seberapa mirip isi dokumennya. Metode tradisional untuk menentukan kedekatan antara dua buah vektor dengan menggunakan koefisien kemiripan (similarity coefficent) dalam hal ini model vector space menggunakan cosine similarity karena operasi vektor pada sistem biasanya berada pada kuadran positif dengan diasumsikan tidak ada term yang bernilai negatif [4]. Seperti model sistem information retrieval lainnya, model vector space menggunakan struktur data inverted list untuk mempermudah proses pencarian dokumen. Inverted list memungkinkan akses yang cepat terhadap daftar dokumen yang mengandung sebuah term tertentu bersama informasi lainnya, seperti bobot setiap istilah yang terdapat dalam masing-masing dokumen, posisi term dalam masing-masing dokumen, dan lain sebagainya. Kelemahan model ini adalah dokumen yang memiliki lebih banyak kata didalamnya akan cenderung menjadi dokumen yang dianggap relevan [7]. Proses pengukuran kemiripan antara vektor kueri dengan setiap vektor dokumen pada metode vector space secara umum dilakukan dengan beberapa tahap, yaitu [6] : 1. Membuat inverted list terhadap setiap term unik dalam dokumen maupun kueri.

2.2. Model Extended Boolean Model Boolean merupakan model paling sederhana untuk diimplementasikan di antara model-model retrieval lainnya. Model ini bergantung pada penggunaan operator Boolean dalam melakukan retrieval. Model ini juga sering digunakan pada search engine di internet karena pemrosesan kueri yang cepat [9] serta retrieval berdasarkan semantik kueri [7]. Model ini merepresentasikan term pada kueri yang dimasukkan ke dalam sistem sebagai ekspresi Boolean dan term ini dapat dikombinasikan dengan operator Boolean AND, OR, dan NOT [6]. Menggabungkan kata-kata pada kueri dengan operator AND akan memunculkan koleksi dokumen yang berisi kata-kata pada kueri tersebut. Sedangkan jika operator OR digunakan untuk menggabungkan kata-kata pada kueri, maka koleksi dokumen yang berisi salah satu kata atau seluruh kata pada kueri itu yang akan dimunculkan dan jika operator NOT yang digunakan maka koleksi dokumen yang tidak berisi kata pada kuerilah yang muncul [4]. Namun model ini dinilai belum cukup untuk memenuhi kebutuhan akan sistem information retrieval yang membutuhkan proses matching yang fleksibel, seperti pencarian kata yang berada pada jarak tertentu dengan kata yang lain serta adanya pemeringkatan agar pengguna dapat memperoleh hasil yang terbaik dari pencarian yang dilakukan oleh sistem [2]. Model boolean lalu dikembangkan menjadi extended boolean. Model ini mengenal pemeringkatan hasil dokumen [4] dan penambahan proximity operator [6]. Proximity operator yang digunakan pada model ini adalah operator NEAR dan WITH. Penggunaan proximity operator seperti NEAR pada kueri akan memunculkan set dokumen yang berisi katakata pada kueri yang memiliki jarak tertentu dan penggunaan proximity operator WITH pada kueri akan memunculkan set dokumen yang berisi kata-kata pada kueri yang terletak bersebelahan dan berurutan sesuai dengan kuerinya.

2. Menghitung nilai inverse document frequency atau idf masing-masing term dengan menggunakan persamaan :

 d idf j = log   df  j

   

(1) Keterangan : d :Jumlah seluruh dokumen dalam koleksi dfj :Jumlah dokumen yang mengandung term-j. dfj dapat disebut sebagai document frequency 3. Menghitung nilai bobot setiap istilah yang dimiliki oleh setiap dokumen menggunakan perkalian antara idf terhadap tf (term frequency) untuk merepresentasikan vektor dokumen. Teknik pembobotan ini disebut dengan tf-idf. Nilai dari tf-idf diperoleh dengan menggunakan persamaan :

2.3. Model Vector Space Model ini didasarkan pada usulan yang diajukan oleh Peter Luhn. Ia mengusulkan agar ketika mencari dokumen pada sebuah koleksi dokumen, pengguna sebaiknya mempersiapkan terlebih dahulu sebuah

wi,j = tf ij × idf j

184

(2)


Keterangan : wi,j : Bobot term-j pada dokumen-i tfij : frekuensi kemunculan term-j pada dokumen-i 4. Menghitung koefisien kemiripan coefficient)dengan persamaan :

sim (d j ,q ) =

Cara yang digunakan untuk mengukur kemampuan suatu sistem dalam mengambil dokumen-dokumen yang relevan adalah dengan menggunakan precision dan recall [5]. Recall adalah perbandingan dari jumlah dokumen relevan yang terambil dengan jumlah seluruh dokumen relevan yang ada dalam koleksi atau peluang acak terambilnya sebuah dokumen relevan dari dokumen yang terambil. Sedangkan precision merupakan perbandingan dari jumlah dokumen relevan yang terambil dengan jumlah dokumen yang terambil. Nilai precision ini dapat mengindikasikan kualitas sistem dalam menyajikan hasil [5]. Persamaan untuk mendapatkan nilai precision and recall adalah sebagai berikut [5]:

(similarity

d j .q dj .q

(3)

dengan

d j .q = ∑ j =1 wi , j .wq , j t

∑

Pr ecision =

t

dj =

(4)

j =1

wi2, j

(5) Re call =

q =

∑

Keterangan : : sim(dj,dk) dj

:

q

:

dj

q wi,j wq,j

t

w2 j =1 q , j

jumlah dokumen yangterambil dan relevan jumlah dokumen yangterambil jumlah dokumen yang terambil dan relevan jumlah dokumen yang relevan pada kueri

(7)

(8)

(6)

3.Perancangan Sistem Information Retrieval Sudut kosinus atau koefisien kemiripan antara vektor dokumen dengan vektor kueri Seluruh bobot term yang terkandung di dalam vektor dokumen-j Seluruh bobot term yang terkandung di dalam vektor kueri Panjang vektor dokumen-j

Sistem yang dirancang adalah sistem information retrieval menggunakan model extended boolean. Flowchart sistem information retrieval ditunjukkan pada gambar 2 berikut.

Panjang vektor kueri Bobot term-j pada dokumen-i Bobot term-j pada kueri

2.4. Evaluasi Sistem Pada saat sistem information retrieval melakukan operasi pencarian, sistem akan mengambil sejumlah dokumen dari koleksi dokumen. Dokumen yang diambil oleh sistem terdiri dari dokumen yang relevan dan dokumen yang tidak relevan dengan kueri yang telah dimasukkan sebelumnya. Kondisi ini diilustrasikan pada gambar 2 berikut

Gambar 1 Diagram Hasil Pencarian Dokumen

Gambar 2 Flowchart Sistem Information Retrieval Yang Dirancang

185


Sistem akan menerima input dari pengguna berupa kueri dan berdasarkan kueri tersebut, sistem akan melakukan pencarian di dalam koleksi dokumen terhadap dokumen-dokumen yang dianggap sistem relevan dengan kueri. Dokumen-dokumen yang dianggap relevan adalah dokumen-dokumen yang di dalam isinya mengandung kata-kata yang terdapat pada kueri. Sebagai output, sistem akan membuat daftar dokumen-dokumen yang dianggap relevan. Tahapan-tahapan pemrosesan dokumen pada sistem ini yaitu: 1. Mengumpulkan seluruh dokumen untuk dijadikan indeks. 2. Melakukan proses tokenisasi pada dokumen menjadi sekumpulan token. 3. Melakukan proses preprocessing, yaitu stopword removal dan stemming sehingga menghasilkan token-token dokumen yang telah ternormalisasi. 4. Membuat inverted index dari token-token yang sudah ternormalisasi. Indeks dibuat dengan cara mengelompokkan token menurut urutan dan letak kata-kata pada kumpulan dokumen.

3.2. Rancangan Modul Sistem Information retrieval system dengan extended boolean terdiri dari 4 modul utama, yaitu : 1. Modul Indexing Modul ini merupakan modul yang digunakan untuk melakukan proses-proses preprocessing sebelum dilakukan retrieval. Terdiri dari : a) Form Input Document. Digunakan untuk menyimpan 1 dokumen yang akan diproses b) Form Batch Input. Digunakan untuk menyimpan beberapa dokumen yang terletak pada sebuah folder. c) Menu Database. Menu ini digunakan untuk menyimpan dan menghapus daftar stopword, stemword, dan dokumen. Terdiri dari : I. Form Document Form ini digunakan untuk melihat atau menghapus daftar koleksi dokumen yang sudah dimasukkan dan diproses ke dalam sistem. II. Form Stopword Form ini digunakan untuk menambah atau menghapus daftar stopword untuk proses stopword removal. III. Form Stemword Form ini digunakan untuk menambah atau menghapus daftar kata dasar atau stemword untuk proses stemming.

Tahapan-tahapan pemrosesan kueri pada sistem ini yaitu : 1. Melakukan tokenisasi pada kueri yang telah dimasukkan ke dalam sistem. 2. Melakukan preprocessing, yaitu stemming sehingga menghasilkan token-token kueri yang telah ternormalisasi. 3. Melakukan pencarian token kueri pada inverted index dokumen. 4. Melakukan retrieval pada indeks dokumen yang sesuai dengan kueri 5. Melakukan interseksi jika operator boolean terdapat pada kueri.

2. Modul Retrieval Modul ini adalah form yang digunakan dalam pencarian dokumen 3. Modul Help Modul ini berisi petunjuk bagaimana mengoperasikan sistem information retrieval. 4. Modul About Modul ini berisi tentang informasi program.

3.1. Batasan Rancangan Batasan rancangan sistem ini antara lain : 1. Dokumen berupa artikel berbahasa Indonesia yang diambil dari situs berita resmi di internet dan sudah diubah menjadi format file teks. 2. Sistem mengenali term sebagai sebuah kata. 3. Kueri yang dimasukkan dapat berupa kata berimbuhan. 4. Stemmer menggunakan algoritma Nazief dan Adriani untuk Bahasa Indonesia yang telah dikembangkan oleh Jelita Asian. 5. Operator yang digunakan pada model Extended Boolean ini adalah AND, OR, NOT, WITH, dan NEAR. 6. Pemeringkatan dokumen menggunakan model Vector Space, yang berdasarkan pada bobot dan frekuensi kata. 7. Sistem memunculkan sebanyak mungkin dokumen relevan dengan kueri yang dimasukkan. 8. Jumlah dokumen yang diproses berjumlah 500 dokumen.

Keempat modul tersebut dapat diakses melalui menu utama.

3.3. Tampilan Program Tampilan program adalah sebagai berikut : 1. Menu Utama

Gambar 3 Tampilan Menu Utama

186


2. Menu Input Document

6. Menu Database, Submenu Stemword

Gambar 4 Tampilan Menu Input Document

3. Menu Batch Input

Gambar 5 Tampilan Menu Batch Input

4. Menu Database, Submenu Document

Gambar 8 Tampilan Menu Database, Sub-menu Stopword

7. Modul Retrieval

Gambar 6 Tampilan Menu Database,Sub-menu Document

5. Menu Database, Submenu Stopword Gambar 9 Tampilan Modul Retrieval

8. Form Hasil

Gambar 10 Tampilan Form Hasil

Gambar 7 Tampilan Menu Database, Sub-menu Stopword

187


pengujian dan perhitungan precision dan recall adalah sebagai berikut

9. Modul Help

Tabel 1 Nilai Rata-rata Precision dan Recall Berdasarkan Tingkatan Urutan Dokumen Hasil Pengujian 50 Kueri

Tingkatan Dokumen 5 dokumen 10 dokumen

Rata-rata Precision 0.8703 0.7105

Rata-rata Recall 0.2845 0.3769

Program memiliki tingkat akurasi yang lebih baik untuk mencari dokumen pada peringkat 5 besar jika dibandingkan dengan pencarian dokumen pada peringkat 10 besar. Hal ini disebabkan karena pada pengujian hanya ditemukan kurang dari 10 dokumen yang dianggap relevan dengan beberapa kueri yang dimasukkan. Selain itu terdapat pula perbedaan dokumen yang terambil karena perbedaan operator yang digunakan pada kueri, contohnya adalah penggunaan operator AND dan WITH pada kueri ‘penyidik kpk’. Terdapat dokumen yang dianggap tidak relevan ketika operator WITH digunakan sedangkan dokumen tersebut relevan ketika operator AND digunakan. Hal ini disebabkan karena perbedaan sifat dari kedua operator tersebut.

Gambar 11 Tampilan Modul Help

10. Modul About

5. Kesimpulan Dari hasil percobaan, didapat bahwa sistem memiliki tingkat akurasi sebesar 0.8703 untuk pencarian dokumen pada 5 peringkat dokumen teratas dan akurasi sebesar 0.7105 untuk pencarian dokumen pada 10 peringkat dokumen teratas. Akurasi dapat ditingkatkan dengan menambah jumlah koleksi dokumen agar jumlah dokumen relevan bertambah. Pemilihan operator pada kueri juga dapat mempengaruhi hasil perolehan dokumen relevan.

Gambar 12 Tampilan Modul About

4. Pengujian Sistem Pengujian pada program information retrieval system untuk dokumen berbahasa Indonesia dengan menggunakan extended boolean ini dilakukan dengan menggunakan metode Black Box Testing. Metode Black Box Testing adalah salah satu metode untuk melakukan pengujian terhadap fungsi-fungsi yang dimiliki oleh program information retrieval system untuk mengetahui apakah output yang dihasilkan sudah sesuai dengan yang diharapkan. Pengujian program information retrieval system ini dilakukan dengan memberikan serangkaian kueri, lalu kueri tersebut diproses untuk dilakukan pencarian dokumen-dokumen yang relevan Jumlah kueri yang digunakan berjumlah 50 kueri.

REFERENSI [1] Asian, Jelita; Williams, Hugh E.; Tahaghogi, S.M.M, 2005, ”Stemming Indonesian”, ACSC ’05 Proceedings of the Twenty-eighth Australasian conference on Computer Science, Vol. 38, Australian Computer Society, Inc, Darlinghurst. [2] Chang, Kevin Chen-Chuan; Molina, Hector Garcia; Paepcke , Andreas, 1996, “Boolean Query Mapping Across Heterogeneous Information Sources”. IEEE Transactions On Knowledge And Data Engineerin,. Vol. 8, Nomor 4, IEEE Computer Society, Los Alamitos. [3] Frakes, William B. dan Yates, Ricardo Baeza, 1992, Information Retrieval : Data Structures & Algorithms, Prentice Hall, Upper Saddle River. [4]Goker, Ayse. Davies, John, 2009, Information Retrieval : Searching in the 21st Century, John Wiley and Sons, New Jersey. [5] Grossman, David A. Dan Fireder, Ophir, 2004, Information Retrieval Algorithms and Heuristics, 2th Edition, Dordrecht, Springer [6] Maning, Christopher D.; Raghavan Prabhakan dan Schutze, Hinrich, 2009, An Introduction to Information Retrieval, Cambridge University Press, Cambridge.

4. 1. Evaluasi Sistem Perhitungan rata-rata precision dan recall dilakukan untuk 5 dan 10 peringkat dokumen teratas. Hasil

188


[7] Manwar, A. B.; Mahalle, Hemant S.; Chinchkhede, K. D.; Chavan, Vinay, 2012, “A Vector Space Model For Information Retrieval: A Matlab Approach”, Indian Journal of Computer Science and Engineering. Vol. 3, No. 2, Engg Journals Publications, Chennai. [8] Pohl, Stefan; Zobel, Justin; Moffat, Alistair, 2010, “Extended Boolean Retrieval for Systematic Biomedical Reviews”. ACSC ’10 Proceedings of the Thirty-Third Australasian Conference on Computer Science, Vol. 102, Australian Computer Society, Inc, Darlinghurst. [9] THOR Center for Neuroinformatics, 2012, Boolean Retrieval, http://cogsys.imm.dtu.dk/thor/projects/multimedia/textmini ng/node2.html.

Steven, mahasiswa Program Studi Teknik Informatika Fakultas Teknologi Informasi Universitas Tarumanagara, Jakarta.

189

PERANCANGAN INFORMATION RETRIEVAL SYSTEM UNTUK DOKUMEN BERBAHASA INDONESIA DENGAN MENGGUNAKAN EXTENDED BOOLEAN

Recommend Documents