Pertemuan 3 – Stoplist dan Stemming

  1. Stoplist dan Stemming serta alur dan algoritmanya.

a. Stoplist

Dalam TBI stopword merupakan bagian dari informasi yang tidak bermakna, seperti halnya imbuhan. Sehingga harus dihilangkan untuk mempercepat proses pengindeksan dan proses query. Misalnya: tetapi, yaitu, adalah, sedangkan, yang, untuk, dari, ke,pada, jika, maka, dan, di.

Proses pembuangan stopword dilakukan dengan acuan kamus/basis data. Stopword yang akan dibuang terlebih dahulu disimpan didalam basis data untuk selanjutnya setiap kata yang ada dalam basis data akan dibuang oleh sistem.

  • Stopword Statis: stopword yang telah ditentukan dari awal sebelum dilakukan proses indeks dan filtering pada suatu sistem temu kembali informasi.

           Kelebihan:

  1. proses filtering stopword menjadi lebih singkat karena tidak ada proses untuk menentukan daftar stopword terlebih dahulu.
  2. Kemudahan berbagai pakai dengan korpus lain yang menggunakan bahasa yang sama, karena stopword yang digunakan merupakan kata-kata umum dalam bahasa tersebut

         Kekurangan:

Pada domain-domain tertentu akan terdapat kata-kata yang bukan stopword, tetapi dianggap stopword oleh     domain tertentu. Seperti kata “resep” pada domain masakan Indonesia.

  • Stopword Dinamis: stopword yang dihasilkan suatu proses tertentu, proses tersebut biasanya melibatkan korpus yang akan digunakan.

       Kelebihan:

Kemampunnya dalam beradaptasi dengan korpus atau domain yang spesifik, akurasi temu kembali informasi akan  lebih baik jika dibandig menggunakan stopword statik.

       Kekurangan:

Dibutuhkan proses komputasi tambahan untuk menghasilkan stopword.

Algoritma yang digunakan untuk menghilangkan stopword:

  1. Memasukkan daftar stopword dari database ke dalam array stoplist
  2. Menampung input kata kunci pencarian ke dalam variabel
  3. Memecah variabel string menggunakan fungsi string split ke dalam array kata kunci
  4. Inisialisasi variabel ketemu berisi nilai Boolean false
  5. Apakah elemen pada array kata kunci sama dengan elemen pada stoplist ? jika iya, lakukan langkah 6, jika tidak terpenuhi lakukan langkah 7.
  6. Ubah nilai variabel ketemu menjadi true. Lakukan langkah 8.
  7. Lakukan langkah 4-5 hingga seluruh elemen pada array stoplist habis
  8. Apakah variabel ketemu bernilai false ? jika kondisi terpenuhi, lakukan langkah 9, jika tidak terpenuhi lakukan langkah 10
  9. Masukkan elemen array kata kunci yang dipilih ke dalam array hasil
  10. Lakukan langkah 4-9 hingga seluruh elemen pada array kata kunci habis.

Dari algoritma di atas, akan dihasilkan sebuah array yang berisi kata kunci pencarian yang dimasukkan oleh pengguna namun sudah terbebas dari stopword.

b. Stemming

Proses penghilangan / pemotongan dari suatu kata menjadi bentuk dasar. Stemming adalah salah satu cara yang digunakan untuk meningkatkan performa IR.

Dalam stemming algoritma yang digunakan untuk bahasa satu dengan yang lainnya berbeda, misalnya bahasa inggris memiliki morfologi yang berbeda dengan bahasa Indonesia. Proses stemming pada teks bebahasa Indonesia lebih rumit karena terdapat variasi imbuhan yang harus dibuang untuk mendapatkan root word dari sebuah kata. (ipi1120)

Tahap Stemming adalah tahap mencari root kata dari tiap kata hasil filtering. Pada tahap ini dilakukan proses pengembalian berbagai bentuk kata ke dalam suatu representasi yang sama. Berikut pada Proses Stemming lanjutan dari proses filtering

proses stopward

Proses Stemming

 

Stemming Bahasa Indonesia

Misalnya:

Berkata        = kata

Mengatakan = kata

Perkataan    = kata

  • Algoritma dalam Stemming

1). Algoritma Stemming Porter

Algoritma ini juga terkenal dogunakan sebagai stammer untuk bahasa inggris, porter stemmer dalam bahasa Indonesia akan menghasilkan keambiguan karena aturan morfologi bahasa Indonesia.

Adapun langkah-langkah algoritma ini adalah sebagai berikut:

1). Hapus Particle

2). Hapus Possesive Pronom

3). Hapus awalan pertama. Jika tidak ada lanjutkan ke langkah 4a, jika ada maka lanjutkan ke langkah 4b.

4). a Hapus awalan kedua, lanjutkan ke langkah 5a

4). b Hapus akhiran. Jika tidak ditemukan maka lanjutkan ke langkah 5b

5). a Hapus akhiran. Kemudian kata akhir diasumsikan sebagai root word

5). b Hapus awalan kedua. Kemudian kata akhir diasumsikan sebagai root word

untuk lebih jelasnya perhatikan gambar dibawah ini :

algoritma stemming poter

Terdapat 5 kelompok aturan pada Algoritma Porter untuk Bahasa Indonesia :

stemming poter 1

stemming poter 2

stemming poter 3

stemming poter 4

  • Algoritma Nazief & Adriani Stemmer

Tahap-tahap:

1) Cari kata yang akan distem dalam kamus. Jika ditemukan maka akan diasumsikan bahwa kata tersebut adalah root word. Maka algoritma berhenti.

2) Inflection Suffixes (“lah”, “-kah”, “-ku”, “-mu”, atau “-nya”) dibuang. Jika berupa particles (“-lah”, “-kah”, “-tah”, atau “-pun”) maka langkah ini diulangi lagi untuk menghapus Possesive Pronous (“-ku”, “-mu”, atau “-nya”), jika ada.

3) Hapus Derivation Suffixes (“-i”, “-an”, atau “-kan”). Jika kata ditemukan di kamus, maka algoritma berhenti. Jika tidak maka ke langkah 3a

     a) Jika “-an” telah dihapus dan huruf terahir dari kata tersebut adalah “-k” maka “-k” juga ikut dihapus. Jika kata tersebut ditemukan dalam kamus maka algoritma berhenti. Jika tidak ditemukan maka lakukan langkah 3b.

     b) Akhiran yang dihapus (“-i”, “-an” atau “-kan”)dikembalikan, lanjut ke langkah 4.

4) Hapus Derrivation Prefix. Jika pada langkah 3 ada sufiks yang dihapus maka pergi ke langkah 4a, jika tidak pergi ke langkah 4b.

     a) Periksa tabel kombinasi awalan-akhiran yang tidak diijinkan. Jika ditemukan maka algoritma berhenti, jika tidak pergi ke langkah 4.

      b) For i = 1 to 3, tentukan tipe awalan kemudian hapus awalan. Jika root word belum juga ditemukan lakukan langkah 5, jika sudah maka algoritma berhenti.

      CATATAN: jika awalan kedua sama dengan awalan pertama algoritma berhenti

5) Melakukan Recoding.

6) Jika semua langkah telah selesai tetapi tidak juga berhasil maka kata awal diasumsikan sebagai root word. Proses selesai.

Tipe awalan ditentukan melalui langkah-langkah berikut:

  • Jika awalannya adalah “di-“, “ke-”, atau “se-” maka tipe awalannya secara berturut-turut adalah “di-”, “ke-”, atau “se-”.
  • Jika awalannya adalah “te-”, “me-”, “be-”, atau “pe-” maka dibutuhkan sebuah proses tambahan untuk menentukan tipe awalannya.
  • Jika dua karakter pertama bukan “di-”, “ke-”, “se-”, “te-”, “be-”, “me-”, atau “pe-” maka berhenti.
  • Jika tipe awalan adalah “none” maka berhenti. Jika tipe awalan adalah bukan “none” maka awalan dapat dilihat pada Tabel 2. Hapus awalan jika ditemukan.

 

tabel kombinasi

tabel aturan awalan

tabel jenis awalan

 

Untuk mengatasi keterbatasan pada algoritma diatas, maka ditambahkan aturan-aturan dibawah ini:

1) Aturan reduplikasi.

a. Jika kedua kata yang dihubungkan oleh kata penghubung adalah kata yang sama maka root word adalah bentuk tunggalnya, contoh : “buku-buku” root word-nya adalah “buku”.

b. Kata lain, misalnya “bolak-balik”, “berbalas-balasan, dan ”seolah-olah”. Untuk mendapatkan root word-nya,

kedua kata diartikan secara terpisah. Jika keduanya memiliki root word yang sama maka diubah menjadi bentuk tunggal, contoh: kata “berbalas-balasan”, “berbalas” dan “balasan” memiliki root word yang sama yaitu “balas”, maka root word “berbalas-balasan” adalah “balas”. Sebaliknya, pada kata “bolak-balik”, “bolak” dan “balik” memiliki root word yang berbeda, maka root word-nya adalah “bolak-balik”

2) Tambahan bentuk awalan dan akhiran serta aturannya.

a. Untuk tipe awalan “mem-“, kata yang diawali dengan awalan “memp-” memiliki tipe awalan “mem-”.

b. Tipe awalan “meng-“, kata yang diawali dengan awalan “mengk-” memiliki tipe awalan “meng-”.

 

Pebandingan Algoritma Stemming Porter dengan Algoritma Nazief & Adriani untuk stemming dokumen Bahasa Indonesia:

a. Proses stemming dokumen teks berbahasa Indonesia menggunakan Algoritma Porter membutuhkan waktu yang lebih singkat dibandingkan dengan stemming menggunakan algoritma Nazief & Adriani.

b. Proses stemming dokumen teks berBahasa Indonesia menggunakan Algoritma Porter memiliki prosentase keakuratan (presisi) lebih kecil dibandingkan dengan stemming menggunakan Algoritma Nazief & Adriani.

c. Pada proses stemming menggunakan Algoritma Nazief & Adriani, kamus yang digunakan sangat mempengaruhi hasil stemming. Semakin lengkap kamus yang digunakan maka semakin akurat pula hasil stemming.

d. Kamus yang digunakan mempengaruhi perhitungan presisi. Semakin lengkap kamus yang digunakan maka semakin akurat pula nilai presisinya. Atau dapat dilihat pada gambar di bawah ini

perbandingan

Stemming pada query ganda:

Permintaan informasi pemakai di sampaikan dengan cara memformulasikan queri, namun queri untuk metode Bololean dan P-norm di formulasikan secara lengkap pada saat pemakai memformulasikan permintaan informasinya. Akhirnya sistem seringkali tampak kurang efisien, yang disebabkan oleh individu yang berbeda akan memakai istilah yang berbeda untuk domain subjek yang sama. Sebaliknya istilah yang sama seringkali mempunyai makna ganda, oleh karena itu permintan informasi pemakai adalah sangat individual dan internal sifatnya yang kadang diketahui secara tepat dan lengkap.

Jaringan Inferensi dirancang agar pemakai dapat memformulasikan permintaan informasinya secara bertahap, artinya setelah queri pertama diproses lalu pemakai membaca dan mengidentifikasi istilah penting dari dokumen yang terambil, bila dinilai kurang sesuai maka pemakai dapat menyempurnakan permintaannya dengan cara mencantumkan istilah penting tersebut dalam queri berikutnya (secara otomatis sistem akan memperhalus struktur jaringan queri yang ada) .

Dalam jurnal MAKARA, SAINS, VOL. 8, NO. 2 menyebutkan kebebasan kepada pemakai untuk memformulasikan permintaan informasinya baik dengan queri Boolean (queri menggunakan operator and, or, atau not), dengan pendekatan probabilistik (queri menggunakan operator sum dan wtd) ataupun campuran dari kedua tipetersebut yang formulasinya dinamakan sebagai queri ganda. Ide mengkombinasikan queri Boolean dan probabilistik dipandang sebagai mengkombinasikan multiple sources of evidence. Hal ini dimaksudkan agar menduga relevansi antar dokumen dan queri lebih logis sehingga dapat meningkatkan kinerja sistem.

Download PPT

TBI-3-Kelompok Dian Restiani

Referensi :

1. blog : https://ranuchi.wordpress.com/2010/05/18/information-retrieval-intro/
2. Bab 2 : http://repository.widyatama.ac.id/xmlui/bitstream/handle/123456789/6830/Bab%202.pdf?sequence=11
3. queri ganda : http://repository.ui.ac.id/contents/koleksi/2/c737ea3ac21e7be11f286ce3aa0b1098d96fb350.pdf
4.https://yudiagusta.files.wordpress.com/2009/11/196-201-knsi09-036-perbandingan-algoritma-stemming-porter dengan-algoritma-nazief-adriani-untuk-stemming-dokumen-teks-bahasa-indonesia.pdf
5. https://ti.ukdw.ac.id/ojs/index.php/eksis/article/download/363/133
6.http://download.portalgaruda.org/article.php?article=414302&val=8924 title=Stopword%20Dinamis%20dengan%20Pendekatan%20Statistik