IMPLEMENTASI MODIFIKASI ENHANCED CONFIX STRIPPING STEMMER UNTUK BAHASA INDONESIA DENGAN METODE CORPUS BASED STEMMING

IMPLEMENTASI MODIFIKASI ENHANCED CONFIX STRIPPING STEMMER UNTUK BAHASA INDONESIA DENGAN METODE CORPUS BASED STEMMING DOSEN PEMBIMBING Diana Purwitasarti, S.Kom., M.Sc. MAHASISWA Andita Dwiyoga T (5106 100 158))

Seminar Tugas Akhir – Juli 2010

Latar Belakang (1) 

Enhanced Confix Stripping (ECS) Stemmer, yang merupakan perbaikan dari Confix Stripping (CS) Stemmer, masih melakukan kesalahan stemming : CONTOH KASUS

NO

TIPE KESALAHAN

AWAL

HASIL STEMMING

SEHARUSNYA

1

KESALAHAN ATURAN 18

menyatakan

menyatakan

nyata

2

KESALAHAN ATURAN 31

penyanyi

penyanyi

nyanyi

3

SISIPAN

temaram

temaram

taram

4

AKHIRAN SERAPAN BAHASA ASING

relawan

relawan

rela

5

KATA GABUNGAN

diberitahukan

diberitahukan

beritahu

6

NAMA ORANG

Gumai

Guma

Gumai

7

OVERSTEMING

penyidikan

sidi

sidik

8

UNDERSTEMMING

mengalami

alami

alam

Latar Belakang (2) 

Dalam evaluasi performa sistem pencarian dokumen, pembentukan relevan set secara manual membutuhkan banyak waktu. QUERY SET :

RELEVAN SET :

KOLEKSI DOKUMEN :

Query A : •Query A •Query B •Query C

•Dokumen 1 •Dokumen 2 •Dokumen 3 •Dokumen 4 •Dokumen 5 •Dokumen 6 •Dokumen 7 •Dokumen 8

•Dokumen 1 •Dokumen 2 •Dokumen 4 Query B :

•Dokumen 1 •Dokumen 3 •Dokumen 5

Query C : •Dokumen 2 •Dokumen 5 •Dokumen 6

Permasalahan 





Bagaimana cara memperbaiki kesalahan stemming yang dilakukan oleh ECS Stemmer ? Bagaimana cara mengevaluasi performa sistem temu kembali informasi tanpa melakukan penilaian relevansi dokumen secara manual ? Bagaimana performa sistem pencarian dokumen yang menggunakan ECS Stemmer sebelum dan sesudah perbaikan ?

Tujuan 



Melakukan modifikasi terhadap algoritma ECS Stemmer dengan menerapkan metode corpus based stemmer untuk mengatasi problem overstemming dan understemming. Menerapkan teknik data fusion menggunakan metode Condorcet untuk proses pembentukan relevansi set secara otomatis.

Batasan Masalah 





Teknik stemming dilakukan untuk kata-kata dalam Bahasa Indonesia Modul ECS Stemmer, kamus kata dasar, dan list stopwords serupa dengan yang digunakan oleh I Putu Adhi Kerta dalam Tugas Akhirnya. Koleksi dokumen yang digunakan dalam uji coba diambil dari detikfinance.com mulai dari tanggal 1 November 2009 sampai dengan 31 Desember 2009 dengan jumlah total 1427 dokumen berita.

DASAR TEORI

FLOWCHART SISTEM IR

Sejarah singkat perkembangan ECS Stemmer Nazief-Adriani Stemmer (1996)

Jelita Asian CS Stemmer (2007)

Putu Adhi Kerta ECS Stemmer (2008)

• Pembentukan kamus kata dasar sebagai acuan hasil pemenggalan • Pembentukan tabel aturan pemenggalan awalan dan akhiran

• Penambahan aturan pemenggalan untuk kata ulang (plural) • Penggunaan rule precedence di dalam algoritma stemmer • Penambahan dan revisi aturan dalam tabel aturan pemenggalan

• Revisi aturan dalam tabel aturan pemenggalan • Penggunaan loopPengembalianAkhiran di dalam algoritma stemmer

Perbaikan terhadap ECS Stemmer 





Revisi aturan nomor 18 dan 31 serta penambahan aturan untuk pemenggalan sisipan pada tabel aturan pemenggalan imbuhan. Penambahan algoritma pada ECS Stemmer untuk melakukan cek keberadaan kata gabungan, contoh “diberitahukan” menjadi “beritahu”. Penggunaan Corpus Based Stemming untuk mengatasi permasalahan kata-kata yang memiliki potensi overstemming dan understemming (memiliki hasil stemming lebih dari satu).

Corpus Based Stemming 

Dikembangkan oleh Jinxi Xu - Bruce Croft dengan latarbelakang adanya proses stemming yang memiliki kemungkianan hasil stemming 2 buah kata atau lebih.  Contoh

:

 mengakui  

:

meng + akui meng + aku + i

 mengawali  

:

meng + awal + i meng + kawal + i

Corpus Based Stemming (2) 

Partisi terhadap kelas stem “awal” menjadi 4 kelas baru : Term diawal diawali awal-awal mengawal pengawalan mengawali

Hasil Stem ECS Stemmer Kata Dasar Seharusnya awal awal awal awal awal awal awal awal / kawal awal awal / kawal awal awal / kawal

Corpus Based Stemmer

diawali awal-awal mengawali

1

diawal

mengawal

2

3

pengawalan

4

Corpus Based Stemming (3) 

Corpus based stemming dimulai dengan melakukan penghitungan nilai em :



 En ( a, b) ab em ( a, b)  max ( , 0) n n a b Keterangan : n

En(a,b)  knanb

n k   ab  na nb

na dan nb

: jumlah frekuensi kata a dan b pada koleksi dokumen

nab

: frekuensi kedua kata tersebut muncul secara bersamaan (co-occurence)

En(a,b)

: nilai ekspektasi munculnya kata a dan b secara bersama-sama, dengan

di dalam jendela teks yang sama. asumsi awal bahwa kedua kata tersebut tidak saling mempengaruhi (statictically independent)

k

: faktor konstan dari estimasi dengan sample berukuran besar yang

dipilih secara random atau acak dari pasangan kata yang terdapat pada corpus yang digunakan.

Corpus Based Stemming : Algoritma Connected Component 

Algoritma Connected Component : 

Hubungkan pasangan term dengan em > 0.01

Corpus Based Stemming : Algoritma Connected Component (2) 

Kekurangan algoritma connected component : 



Jumlah kelas stem yang terbentuk sangat ditentukan jumlah graf yang terbentuk. Saat terbentuk 2 kelas stem oleh algoritma ECS Stemmer, dan salah satu term dari salah satu kelas tersebut salah di-stem oleh ECS Stemmer, algoritma connected component tidak dapat memindahkan term tersebut ke kelas yang lain.

Kelas stem : awal

Kelas stem : awal

Diawali Awal-awal mengawal

Diawali Awal-awal

Kelas stem : kawal

Dikawal kawal

Kelas stem : kawal

mengawal Dikawal kawal

Kelas stem awal

Diawali Awal-awal mengawal Kelas stem kawal

Dikawal kawal

Kelas stem 1

Diawali Awal-awal Kelas stem 2

mengawal Kelas stem 3

Dikawal kawal

Corpus Based Stemming : Algoritma Nilai Em Terbesar 

Algoritma : Pemilihan Hasil Stemming dengan nilai Em terbesar Kelas stem : awal

Kelas stem : kawal

diawali

mengawal dikawal kawal

awal-awal

mengawal

 Dapatkan

nilai em tertinggi dari tiap kelas stem.

Kelas Stem

Term 1

awal

mengawal

kawal

mengawal

Term 2

em

diawali awal-awal dikawal kawal

0,05 0,03 0,11 0

Max (em) 0,03 0,11

Corpus Based Stemming : Algoritma Nilai Em Terbesar (2) 

Algoritma : Pemilihan Hasil Stemming dengan nilai Em terbesar 

Kelas stem yang memiliki nilai em tertinggi akan ditetapkan sebagai kelas stem untuk term tersebut. Kelas stem : awal

diawali Awal-awal

Kelas stem : kawal

mengawal dikawal kawal

Penghitungan similaritas dokumen terhadap query 



Proses penghitungan similaritas diawali dengan penghitungan bobot tf-idf :

Nilai similaritas suatu dokumen terhadap query dihitung menggunakan rumus cosinus similarity :

Pembentukan relevance set 

Pembentukan relevan set secara otomatis = pseudo relevance set (pseudorels)

Condorcet Method (1) SISTEM A

SISTEM B

SISTEM C

Rank

Similarity

Dokumen

Rank

Similarity

Dokumen

Rank

Similarity

Dokumen

1

125

a

1

125

a

1

125

a

2

122

b

2

120

c

2

120

b

3

100

c

3

99

b

3

120

c

a>b>c

a>c>b

a>b=c

SISTEM D

SISTEM E

Rank

Similarity

Dokumen

Rank

Similarity

Dokumen

1

125

b

1

110

c

2

111

a

2

90

a

b>a

c>a

Condorcet Method (2) 







elemen matrix (i,j) : nilai menang, kalah, dan seri dokumen i terhadap dokumen j pada tiap sistem yang ada. a

b

c

a

-

4,1,0

4,1,0

b

1,4,0

-

2,2,1

c

1,4,0

2,2,1

-

Setiap dokumen dibandingkan nilai menang dan kalahnya terhadap dokumen lainnya. Win Lose Tie a

2

0

0

b

0

1

1

c

0

1

1

Penentuan ranking dokumen ditentukan berdasarkan nilai menang dan kalahnya. Dari contoh di atas, maka urutan akhir dokumen adalah a > b = c.

UJI COBA

Hasil Perbaikan ECS Stemmer : 1. Aturan Nomor 18 TERM ECS menyala sala menyanyikan menyanyikan menyatakannya menyatakannya 2. Aturan Nomor 31 term ecs penyanyi sanyi penyawaan sawa

IECS nyala nyanyi nyata iecs nyanyi nyawa

3. Sisipan TERM melamah jelambar lemigas rerata

ECS melamah jelambar lemigas rerata

IECS mamah jambar ligas rata

Hasil Perbaikan ECS Stemmer (2) : 4. Akhiran serapan bahasa asing ('-is', '-isasi', '-isme', '-wan', '-wati') TERM ECS IECS relawan relawan rela riawan riawan ria salawati salawat sala belesis belesis beles eksis eksis eks finalis finalis final menepis tepis tep minimalis minimalis minimal brokerisasi brokerisasi broker difinalisasi difinalisasi final finalisasi finalisasi final maksimalisasi maksimalisasi maksimal memfinalisasi memfinalisasi final standarisasi standarisasi standar terealisasi realisasi real

Hasil Perbaikan ECS Stemmer (3) : TERM bekerjasama berkerjasama beritahukan diberitahu diberitahukan dibertanggungjawabkan

5. Kata Gabungan ECS bekerjasama berkerjasama beritahukan diberitahu diberitahukan dibertanggungjawabkan

IECS kerjasama kerjasama beritahu beritahu beritahu tanggungjawab

dipertanggungjawabkan ditandatangani ditandatanganinya ditindaklanjut ditindaklanjuti diujicoba diujicobakan keanekaragaman

dipertanggungjawabkan ditandatangani ditandatanganinya ditindaklanjut ditindaklanjuti diujicoba diujicobakan keanekaragaman

tanggungjawab tandatangan tandatangan tindaklanjut tindaklanjut ujicoba ujicoba anekaragam

Hasil Perbaikan ECS Stemmer (4) : 5. Perbaikan Hasil Stemming Menggunakan Analisis Nilai Em term

ECS Stemmer

penjajakan

jaja

penyelidikan

lidi

penyidikan

sidi

perancang

ancang

perancangan

ancang

perbankan

perban

pergerakan

gera

perombakan

ombak

List Bentuk Dasar [jaja, jajak, jajakan, penjaja, penjajak] [lidi, lidikan, selidik] [nyidi, nyidik, nyikan, sidi, sidik, sidikan, sikan] [ancang, pancang, perancang, rancang] [ancang, perancang, rancang] [bank, perban, perbank, perbankan] [gera, gerak, gerakan, pergera, pergerak] [ombak, perombak, rombak]

analisis nilai em jajak selidik sidik rancang rancang bank gerak

rombak

Perbandingan Nilai Efektifitas : Pool Depth

Percentage merged documents = 30

10

20

30

Tanpa Stemming

ECS Stemmer

Perbaikan ECS Stemmer

Recall Recall(10) Recall(20) Precision

0,955 0,862 0,879 0,073

1,000 0,890 0,941 0,055

1,000 0,787 0,863 0,038

Precision(10)

0,069

0,052

0,030

Precision(20) MAP Recall Recall(10) Recall(20) Precision

0,072 0,758 0,941 0,733 0,829 0,143

0,054 0,802 1,000 0,780 0,907 0,106

0,036 0,663 1,000 0,640 0,835 0,070

Precision(10)

0,121

0,088

0,044


0,136 0,750 0,890 0,548 0,761 0,198

0,103 0,811 0,992 0,558 0,877 0,148

0,064 0,681 1,000 0,483 0,861 0,103

Precision(10)

0,139

0,094

0,049

Precision(20) MAP

0,184 0,685

0,141 0,790

0,094 0,705

Measure

Perbandingan Nilai Efektifitas (2) : Pool Depth


10

20

30

Tanpa Stemming

ECS Stemmer



0,956 0,825 0,850 0,106

1,000 0,853 0,916 0,078

1,000 0,765 0,865 0,053

Precision(10)

0,096

0,072

0,040


0,102 0,799 0,928 0,681 0,818 0,182

0,076 0,846 0,992 0,695 0,883 0,136

0,049 0,702 1,000 0,583 0,832 0,095

Precision(10)

0,146

0,102

0,052


0,172 0,790 0,889 0,501 0,752 0,248

0,132 0,864 0,981 0,471 0,808 0,189

0,086 0,726 1,000 0,412 0,791 0,139

Precision(10)

0,161

0,103

0,055

Precision(20) MAP

0,230 0,775

0,171 0,854

0,118 0,768

Measure

Perbandingan Nilai Efektifitas (3) : Pool Dept h


10

20

30

Tanpa Stemming

ECS Stemmer



0,959 0,800 0,831 0,134

1,000 0,828 0,908 0,098

1,000 0,698 0,843 0,068

Precision(10)

0,117

0,087

0,045


0,125 0,805 0,912 0,587 0,786 0,220

0,095 0,864 0,983 0,563 0,845 0,167

0,062 0,720 1,000 0,480 0,816 0,121

Precision(10)

0,160

0,103

0,054


0,205 0,788 0,876 0,403 0,721 0,297

0,156 0,858 0,978 0,380 0,746 0,236

0,105 0,750 0,997 0,334 0,683 0,176

Precision(10)

0,164

0,106

0,056

Precision(20) MAP

0,266 0,770

0,202 0,853

0,126 0,776

Measure

Simpulan 





Perbaikan berhasil dilakukan terhadap seluruh kesalahan stemming yang dilakukan oleh algoritma ECS Stemmer Penggunaan metode corpus based stemming digunakan untuk menyelesaikan permasalahan overstemming dan understemming Penggunaan data fusion dan metode condorcet dapat mempersingkat waktu yang dibutuhkan untuk melakukan pembentukan relevan set.

Saran 



Penggunaan koleksi dokumen yang berbeda untuk mengetahui pengaruh dari metode corpus based stemming terhadap hasil dari proses stemming yang dilakukan. Percobaan terhadap parameter data fusion dan metode Condorcet yang berbeda untuk mengetahui konsistensi hasil efektifitas sistem temu kembali informasi .

SEKIAN DAN TERIMA KASIH

Tabel Aturan Pemenggalan Imbuhan (1) 

Tabel Aturan Pemenggalan Imbuhan oleh Algoritma Nazief-Adriani : Aturan 1 2 3 4 5 6 7 8 9 10



FORMAT KATA berV... berCAP... berCAerV... belajar beC1erC2... terV... terCerV... terCP... teC1erC2... me{l|r|w|y}V...

Pemenggalan ber-V... | be-rV... ber-CAP... dimana C!=‟r‟ & P!=‟er‟ ber-CaerV... dimana C!=‟r‟ bel-ajar be-C1erC2... dimana C1!={‟r‟|‟l‟} ter-V... | te-rV... ter-CerV... dimana C!=‟r‟ ter-CP... dimana C!=‟r‟ dan P!=‟er‟ te-C1erC2... dimana C1!=‟r‟ me-{l|r|w|y}V...

Keterangan simbol huruf : 

C : huruf konsonan

A : huruf vokal atau konsonan



V : huruf vokal

P : partikel atau fragmen dari suatu kata, misalnya “er”

<< Kembali >>


Tabel Aturan Pemenggalan Imbuhan oleh Algoritma Nazief-Adriani : Aturan 11 12 13 14 15 16 17 18 19 20



FORMAT KATA mem{b|f|v}... mempe{r|l}... mem{rV|V}... men{c|d|j|z}... menV... meng{g|h|q}... mengV... menyV... mempV... pe{w|y}V...

Pemenggalan mem-{b|f|v}... mem-pe... me-m{rV|V}... | me-p{rV|V}... men-{c|d|j|z}... me-nV... | me-tV meng-{g|h|q}... meng-V... | meng-kV... meny-sV… mem-pV... dimana V!=„e‟ pe-{w|y}V...


C : huruf konsonan




V : huruf vokal


<< Kembali >>


Tabel Aturan Pemenggalan Imbuhan oleh Algoritma Nazief-Adriani : Aturan 21 23 24 25 26 27 28 29 30



FORMAT KATA perV... perCAP perCAerV... pem{b|f|V}... pem{rV|V}... pen{c|d|j|z}... penV... peng{g|h|q}... pengV...

Pemenggalan per-V... | pe-rV... per-CAP... dimana C!=‟r‟ dan P!=‟er‟ per-CAerV... dimana C!=‟r‟ pem-{b|f|V}... pe-m{rV|V}... | pe-p{rV|V}... pen-{c|d|j|z}... pe-nV... | pe-tV... peng-{g|h|q}... peng-V... | peng-kV...


C : huruf konsonan




V : huruf vokal


<< Kembali >>


Tabel Aturan Pemenggalan Imbuhan oleh Algoritma Nazief-Adriani : Aturan 31 32 33 34



FORMAT KATA penyV... pelV... peCerV... peCP...

Pemenggalan peny-sV… pe-lV... kecuali “pelajar” yang menghasilkan “ajar” per-erV... dimana C!={r|w|y|l|m|n} pe-CP... dimana C!={r|w|y|l|m|n} dan P!=‟er‟


C : huruf konsonan




V : huruf vokal


<< Kembali >>

REVISI DAN TAMBAHAN ATURAN OLEH CS STEMMER 

Sebelum :

Aturan FORMAT KATA 12 mempe{r|l}... 16 meng{g|h|q}...



Pemenggalan mem-pe... meng-{g|h|q}...

Sesudah :

Aturan Aturan 12 16 35 36 12

FORMAT KATA FORMAT KATA mempe... meng{g|h|q|k}... terC1erC2... peC1erC2... mempe...

Pemenggalan Pemenggalan mem-pe... meng-{g|h|q|k}... ter-C1erC2... dimana C1!= „r‟ pe-C1erC2... dimana C1!={r|w|y|l|m|n} mem-pe... << Kembali >>

REVISI DAN TAMBAHAN ATURAN OLEH ECS STEMMER 

Sebelum :

Aturan 14 17 19 29 30 

FORMAT KATA men{c|d|j|z}... mengV... mempV... peng{g|h|q}... pengV...

Pemenggalan men-{c|d|j|z}... meng-V... | meng-kV... mem-pV... dimana V!=„e‟ peng-{g|h|q}... peng-V... | peng-kV...

Sesudah :

Aturan Aturan 14 17 19 29 30

FORMAT KATA FORMAT KATA men{c|d|j|s|z}... mengV... mempA... pengC... pengV...

Pemenggalan Pemenggalan men-{c|d|j|s|z}... meng-V... | meng-kV... | (mengV-... jika V=‟e‟) mem-pA... dengan A!=‟e‟ peng-C... peng-V... | peng-kV... | (pengV-... jika V=‟e‟) << Kembali >>

REVISI DAN TAMBAHAN ATURAN : 

Sebelum :

Aturan FORMAT KATA 18 menyV... 31 penyV... 

Pemenggalan meny-sV… peny-sV…

Sesudah :

Aturan Aturan 18 31 37 38 39 40

FORMAT KATA FORMAT KATA menyV… penyV… CerV… CelV… CemV… CinV…

Pemenggalan Pemenggalan me-nyV… | meny-sV… pe-nyV… | peny-sV… CerV… | CV… CelV… | CV… CemV… | CV… CinV… | CV… << Kembali >>

IMPLEMENTASI MODIFIKASI ENHANCED CONFIX STRIPPING STEMMER UNTUK BAHASA INDONESIA DENGAN METODE CORPUS BASED STEMMING

Recommend Documents