analisis penggunaan stemming dengan algoritma … · merupakan keputusan biner (retrieve / reject...

ANALISIS PENGGUNAAN STEMMING DENGAN ALGORITMA DAWSON PADASISTEM INFORMATION RETRIEVAL

Fauzia Albaar¹, Yanuar Firdaus A.w.², Warih Maharani³

¹Teknik Informatika, Fakultas Teknik Informatika, Universitas Telkom

AbstrakInformation Retrieval system digunakan untuk menemukan kembali informasi-informasi yangrelevan terhadap kebutuhan pengguna dari suatu kumpulan informasi secara otomatis. Informasiyang diinginkan direpresentasikan dalam bentuk query dan mengandung satu atau lebih termyang akan digunakan dalam pencarian.

Suatu Information Retrieval system dikatakan ideal jika sistem tersebut dapat menemukanseluruh dokumen yang relevan dan sistem hanya menemukan dokumen yang relevan saja. Akantetapi, term-term yang terdapat di dokumen dan di query sering memiliki banyak varianmorfologik, sehingga pasangan term yang memiliki bentuk beda tidak akan dianggap ekivalenoleh sistem.

Dalam konteks Information Retrieval, stemming dapat digunakan untuk membatasi varian bentukkata yang berbeda menjadi bentuk dasarnya, sehingga nantinya dapat meningkatkan kemampuansistem dalam menemukan dokumen relevan sesuai query yang ada. Dalam tugas akhir ini, dibuatsebuah sistem temu kembali informasi yang mengimplementasikan teknik stemming denganmenggunakan algoritma Dawson dan Porter.

Porter stemmer merupakan algoritma penghilangan akhiran morphological dan infleksional yangumum dari bahasa Inggris dan terdiri dari himpunan kondisi atau action rules. Dawson stemmermenyatakan bahwa bentuk yang paling diharapkan dari context sensitive rule adalah bentuk yangdapat digeneralisasi untuk diterapkan dalam berbagai situasi. Pada tugas akhir ini akandilakukan analisis perbandingan penerapan kedua algoritma tersebut pada Information Retrievalsystem.

Kata Kunci : sistem temu kembali informasi, stemming, algoritma Dawson, algoritma Porter

AbstractInformation Retrieval system used to recover information relevant to the needs of users from acollection of information automatically. The desired information represented in the form of query,And contains one or more terms that will be used in the search.

An Information Retrieval system, is called ideal if the system can finds all relevant documents andit finds the relevant documents only. However, the terms contained in documents and in queriesoften have many morphological variants, so that couples which have a different term would not beconsidered equivalent to the system.

In the context of Information Retrieval, stemming can be used to limit the different variants ofword forms into basic form, so that later can upgrade the system in finding relevant documentsbased on existing query. In this final project developed an information retrieval system thatimplements the technique using a Porter and Dawson stemming algorithm.

Porter stemmer is the removal algorithm morphological and inflectional endings from Englishcommon and consists of a set of conditions or rules action. Dawson Stemmer stated that the mostdesirable form of context-sensitive rule is a form that can be generalized to apply in varioussituations. In this final project will be carried out comparative analysis of the algorithms are atthe Information Retrieval system.

Keywords : Information Retrieval System, stemming, Dawson algorithm, Porter algorithm

Powered by TCPDF (www.tcpdf.org)

Tugas Akhir - 2010

Fakultas Teknik Informatika Program Studi S1 Teknik Informatika

1

1 PENDAHULUAN

Pada bab satu ini akan menjelaskan tentang latar belakang, perumusan masalah, batasan masalah, tujuan, metodologi penyelesain masalah, dan rencana kerja pembuatan tugas akhir ini.

1.1 Latar Belakang Information Retrieval (Sistem Temu Balik Informasi) pada dasarnya digunakan untuk menemukan kembali informasi-informasi yang relevan terhadap kebutuhan pengguna dari suatu kumpulan informasi secara otomatis. Informasi yang diinginkan pengguna direpresentasikan dalam bentuk query dan mengandung satu atau lebih term yang akan digunakan dalam pencarian, selain itu dapat juga ditambahkan informasi lain seperti bobot tiap term tersebut. Oleh karena itu, keputusan menemubalikkan dokumen dibuat dengan membandingkan term-term dari query dengan term indeks yang terdapat dalam dokumen tersebut. Keputusan yang diambil dapat merupakan keputusan biner (retrieve / reject), atau melibatkan perkiraan relevance degree dokumen terhadap query. Dalam Information Retrieval, mendapatakan dokumen yang relevan tidaklah cukup. Tujuan yang harus dipenuhi adalah bagaimana mendapatkan dokumen relevan dan tidak mendapatkan dokumen yang tidak relevan. Suatu Information Retrieval dikatakan ideal jika sistem tersebut dapat menemukan seluruh dokumen yang relevan dan sistem hanya menemukan dokumen yang relevan saja. Akan tetapi, term-term yang terdapat di dokumen dan di query sering memiliki banyak varian morfologik, sehingga pasangan term seperti “computing” dan “computation” tidak akan dianggap ekuivalen oleh sistem tanpa suatu bentuk Natural Language Processing (NLP). Karena alasan tersebut, teknik stemming atau stemmers dikembangkan dengan tujuan mereduksi term menjadi bentuk akarnya. Yang dalam penggunaanya pada Information Retrieval System, stemming tidak harus menghasilkan kata-kata yang bermakna, sehingga kata “computation” dapat direduksi menjadi “comput”. Stemming adalah proses pemotongan (pembuangan) affiks, baik prefiks maupun sufiks dari sebuah term. Dalam konteks Information Retrieval, stemming dapat digunakan untuk mereduksi bentuk term agar menghindari ketidakcocokan yang dapat mengurangi recall, di mana term-term yang berbeda namun memiliki makna dasar yang sama direduksi menjadi satu bentuk. Sebagai salah satu contoh sederhana, jika mencari suatu dokumen dengan judul “I like fish’ dengan menggunakan query “fishing”, kata yang dimaksud tidak akan pernah terdapat dalam hasil pencarian. Akan tetapi, jika query dipotong sehingga diubah menjadi fish, maka pencarian akan berhasil dan juga menghasilkan kata-kata fish, fishy, fisherman dll. Hal ini tidak hanya berarti varian yang berbeda dari suatu term dapat direduksi sebagai satu bentuk representative, tetapi juga berdampak terhadap berkurangnya ukuran inverted file (jumlah term yang diperlukan untuk merepresentasikan suatu koleksi dokumen). Jika ukuran inverted file yang kecil akan dapat menghemat storage space dan mempercepat waktu pemrosesan. Terdapat beberapa algoritma stemming pada Information Retrieval System yang sudah dikenal luas, diantaranya adalah algoritma Porter, algoritma Paice / Husk, algoritma Lovins, algoritma

Tugas Akhir - 2010


2

Simple, algoritma nice serta algoritma Dawson. Namun, algoritma stemming yang akan diimplementasikan pada Tugas Akhir ini hanya algoritma Dawson dan algoritma Porter, yang sebagai pembanding. Algoritma Dawson dikembangkan oleh john Dawson. Algoritma Dawson mirip dengan algoritma Lovins dan algoritma Porter, karena merupakan sebuah single-pass context-sensitive suffix removal stemmer. Dawson juga menyatakan bahwa bentuk yang paling diharapkan dari context sensitive rule adalah bentuk yang dapat digeneralisasi untuk diterapkan dalam berbagai situasi. Tujuan utama dari algoritma Dawson adalah untuk mengambil algoritma yang asli yang diusulkan oleh algoritma Lovins, dan berusaha memperbaiki aturan dan teknik serta mengkoreksi dasar kesalahan yang sering muncul dari algoritma Lovins. Langkah pertama adalah dengan memasukan semua bentuk jamak dan kombinasi yang cukup sederhana tanpa melakukan Stemming, ini akan menambah jumlah daftar akhir hingga mencapai lima ratus. Langkah kedua adalah dengan menerapkan algoritma Dawson dengan prinsip-prinsip penyelesaian, dimana setiap akhiran itu sudah ada terlebih dahulu di daftar akhiran, termasuk semua varian, flexions dan kombinasinya. ini akan menambah jumlah daftar akhir hingga seribu dua ratus. Dawson stemmer menghapus paling banyak satu suffix dari satu term, karena sifatnya sebagai algoritma single pass. Algoritma ini melakukan penghapusan endings berdasarkan prinsip longest-match, di mana masing-masing rule berasosiasi dengan salah satu dari beberapa contextual restrictions yang mencegah penghapusan endings untuk kondisi tertentu. Semua endings diasosiasikan dengan default exception, yaitu stem harus terdiri dari dua huruf atau lebih. Rule-rule lain mensyaratkan salah satu dari kondisi berikut dalam penghapusan endings, yaitu menambah panjang minimum dari stem setelah penghapusan endings, mencegah penghapusan endings ketika huruf-huruf tertentu muncul di stem serta kombinasi dari kedua restriksi tersebut. Algoritma Porter dibuat oleh Martin Porter dan pertama kali dipublikasikan pada tahun 1980. Algoritma ini merupakan algoritma pembuangan suffix yang context sensitive, terdiri dari lima step linear untuk menghasilkan stem akhir.

Beberapa defenisi yang digunakan dalam algoritma Porter ini : Konsonan adalah huruf- huruf selain A,I,U,E, atau O, dan Y yang diawali oleh suatu

konsonan. Vokal adalah huruf-huruf selain konsonan.

1.2 Perumusan Masalah Pada Tugas akhir ini akan dibahas beberapa permasalahan, diantaranya:

1. Bagaimana mengimplementasikan teknik stemming dalam suatu information retrieval system?

2. Bagaimana perbandingan antara algoritma-algoritma Stemming yang akan dipakai dalam tugas akhir ini, yaitu algoritma Dawson dan algoritma Porter, jika ditinjau dari pengaruhnya terhadap nilai rata-rata modified Hamming distance antara term dan stem yang dihasilkan, nilai recall, precision, non-interpolated average precision, banyaknya term yang diubah oleh stemmer, rata-rata jumlah term dalam suatu conflation class, dan faktor kompresi index?

Tugas Akhir - 2010


3

1.3 Batasan Masalah Batasan masalah yang diperlukan dalam tugas akhir ini antara lain:

1. Dokumen yang digunakan untuk Tugas Akhir ini merupakan berkas teks dengan query dan relevance judgments yang telah ditentukan sebelumnya.

2. Algoritma stemming yang akan diimplementasikan pada Tugas Akhir Ini hanya meliputi algoritma Dawson dan algoritma Porter.

3. Parameter output berdasarkan hasil perbandingan yang dilakukan kedua algoritma Stemming, yaitu algoritma Dawson dan algoritma Porter.

1.4 Tujuan Tujuan dari Tugas Akhir ini adalah :

1. Menghasilkan suatu perangkat lunak yang dapat menyimpulkan pengaruh stemming pada suatu information retrieval sistems.

2. Menganalisis keakuratan hasil information retrieval sistems yang dihasilkan oleh perangkat lunak dengan membandingkan bentuk normal information retrieval sistems dengan yang menggunakan Stemming Algorithm.

3. Melakukan perbandingan dari algoritma yang akan dipakai, yaitu algoritma Dawson dan algoritma Porter berdasarkan kriteria tertentu, seperti nilai rata-rata modified Hamming distance antara term dan stem yang dihasilkan, nilai recall, precision, non-interpolated average precision, banyaknya term yang diubah oleh stemmer, rata-rata jumlah term dalam suatu conflation class, dan faktor kompresi index.

1.5 Metodologi Penyelesaian Masalah Metodologi penyelesaian masalah yang dilakukan antara lain:

1. Studi Literatur. • Mengumpulkan serta mempelajari literatur yang berkaitan dengan tugas akhir yang

akan dibuat ini, baik berupa artikel, buku referensi, serta sumber-sumber lain yang berhubungan dengan information retrieval sistems dan algoritma stemming.

2. Analisis Penyelesaian Masalah. • Melakukan analisis terhadap algoritma stemming digunakan, yaitu algoritma Dawson.

3. Analisis dan Perancangan Perangkat Lunak. • Melakukan analisis dan perancangan terhadap perangkat lunak information retrieval

yang akan dibangun, termasuk menentukan bahasa pemrograman yang akan digunakan, lingkungan pembuatan, arsitektur, fungsionalitas, dan antarmuka sistem.

4. Implementasi dan Pengujian Perangkat Lunak. • Implementasi algoritma akan dilakukan berdasarkan hasil analisis dan perancangan

algoritma pada tahap sebelumnya. • Pengujian algoritma akan dilakukan dengan menggunakan input berupa koleksi

dokumen. 5. Evaluasi dan Analisis Hasil.

• Evaluasi dan analisis hasil dilakukan dengan membandingkan nilai modified Hamming distance untuk algoritma yang digunakan, nilai recall, precision, faktor

Tugas Akhir - 2010


4

kompresi index, rata-rata jumlah term dalam suatu conflation class, banyaknya term yang diubah oleh stemmer, dan, serta membandingkan dengan information retrieval system yang tidak menggunakan teknik stemming.

6. Penyusunan laporan tugas akhir.


Tugas Akhir - 2010


40

5 KESIMPULAN DAN SARAN

5.1 Kesimpulan Beberapa kesimpulan yang dapat diambil dari tugas akhir ini, antara lain : 1. Nilai recall algoritma Dawson relatif lebih besar daripada algoritma Porter. Karena dokumen

relevan yang terambil oleh algoritma Dawson lebih banyak dibandingkan algoritma Porter.

2. nilai precision yang dihasilkan algoritma Porter cenderung lebih besar daripada algoritma Dawson. Karena Jumlah dokumen yang terambil dengan algoritma Porter pada kedua dokumen koleksi lebih sedikit dan di antaranya relevan.

3. nilai non-IAP yang dihasilkan algoritma Dawson cenderung lebih besar daripada algoritma Porter. Karena Peringkat dokumen relevan yang terambil oleh algoritma Dawson berada pada urutan awal dokumen yang terambil, serta hasil pembobotan suatu term akan mempengaruhi sebaran term tersebut pada dokumen. Semakin tinggi frekuensi suatu term maka sebarannya semakin kecil dalam suatu dokumen. Kedua hal tersebut menghasilkan nilai bobot yang semakin tinggi. Sebaran term akan mempengaruhi urutan dokumen relevan yang terambil. Jika dokumen relevan yang terambil berada pada urutan-urutan awal dokumen yang terambil maka nilai non-IAP yang dihasilkan dapat semakin besar.

4. Untuk dokumen MED nilai wc dan icf yang dihasilkan algoritma Porter lebih tinggi daripada yang dihasilkan algoritma Dawson. Namun, pada dokumen ADI nilai wc dan icf yang dihasilkan algoritma Dawson lebih tinggi dari algoritma Porter. Hal ini menunjukan bahwa algoritma Dawson juga cenderung sama dengan algoritma Porter dalam melakukan stemming. Hal ini dipengaruhi oleh Jumlah kata unik setelah stemming.

5.2 Saran Saran-saran yang dapat penulis anjurkan untuk keperluan analisis lebih lanjut : 1. Untuk dapat melihat lebih jauh perbandingan antar stemmer dapat digunakan metoda lain

seperti table look-up, n-g diagram dan metode affix removal lainnya.

2. Dapat ditambahkan satu parameter lagi untuk melihat tingkat kekuatan suatu stemmer, yaitu parameter modified Hamming distance.


Tugas Akhir - 2010


45

Daftar Pustaka [1] Algoritam Porter.

http://www.pdf-search-engine.com/algoritma-porter-dengan-java-pdf.htm Di Download Pada Tanggal 17 Maret 2009, Jam 20.20

[2] Algoritma Stemming. http://www.comp.lancs.ac.uk/computing/research/stemming/Links/algorithms.htm Di Download Pada Tanggal 17 Maret 2009, Jam 20.00

[3] Algoritma Stemming. http://www.inf.ufes.br/a_stemming_algorithm_for_the_portuguese_language.pdf Di Download Pada Tanggal 17 Maret 2009, Jam 20.25

[4] Bab 2 http://www.ittelkom.ac.id/library/index.php?view=article&catid=20%3Ainformatika&id=540%3Ainformation-retrieval&option=com_content&Itemid=15

[5] Dawson Stemmer. http://www.snowball.tartarus.org/algorithms/dawson/stemmer.html Di Download Pada Tanggal 18 maret 2009, Jam 14.45

[6] Dawson Stemmer. http://www.tartarus.org/ ~ martin / DawsonStemmer Di Download Pada Tanggal 18 maret 2009, Jam 15.15

[7] Frakes, WB & Fox, CJ (2003) Kekuatan dan kesamaan dari Affix Removal Stemming Algorithms, SIGIR Forum, 37: 26-30

[8] Lovins, J. (1968) Pengembangan Stemming Algoritma, Mechanical Penerjemahan dan komputer Linguistik, 11: 22-31

[9] Paice, CD (1990) Another Stemmer, SIGIR Forum, 24: 56-61 [10] Porter Stemmer. http://www.tartarus.org/ ~ martin / PorterStemmer

Di Download Pada Tanggal 17 Maret 2009, Jam 20.25 [11] Stemming. http://www.blog.tupil.com/stemming-with-haskell/

Di Download Pada Tanggal 23 Februari 2009, Jam 19.40 [12] Stemming. http://www.comp.lancs.ac.uk/computing/research/stemming/general

Di Download Pada Tanggal 25 Februari 2009, Jam 19.00 [13] Stemming. http://en.wikipedia.org/wiki/stemming/

Di Download Pada Tanggal 23 Februari 2009, Jam 20.00


Tugas Akhir - 2010


analisis penggunaan stemming dengan algoritma … · merupakan keputusan biner (retrieve / reject...

Documents