PART-OF-SPEECH TAGGING UNTUK DOKUMEN BAHASA BALI MENGGUNAKAN ALGORITMA BRILL TAGGER KOMPETENSI KOMPUTASI
SKRIPSI
NI PUTU MERI SRIYATI NIM. 1208605026
PROGRAM STUDI TEKNIK INFORMATIKA JURUSAN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS UDAYANA 2016
i
ii
LEMBAR PENGESAHAN TUGAS AKHIR
Judul
: Part-Of-Speech Tagging untuk Dokumen Bahasa Bali Menggunakan Algoritma Brill Tagger
Kompetensi
: Komputasi
Nama
: Ni Putu Meri Sriyati
NIM
: 1208605026
Tanggal Seminar : 07 Januari 2016 Disetujui oleh :
Pembimbing I
Penguji I
I Putu Gede Hendra Suputra, S.Kom, M.Kom. NIP. 19881228 201404 1 001
I Gede Santi Astawa, S.T., M.Cs. NIP. 19801206 200604 1 003
Pembimbing II
Penguji II
Agus Muliantara, S.Kom.,M.Kom. Agus Muliantara, S.Kom.,M.Kom. NIP. 19800616 200501 1 001 NIP. 19800616 200501 1 001
Ida Bagus Made Mahendra, S.Kom., M.Kom. Agus Muliantara, NIP. 19080621 200812 S.Kom.,M.Kom. 1 002 NIP. 19800616 200501 1 001 Penguji III
Agus Muliantara, S.Kom.,M.Kom. I Dewa Made Bayu Atmaja Darmawan, S.Kom., M.Cs. 19800616 NIP. 19890127NIP. 201212 1 001 200501 1 001
Mengetahui, Ketua Jurusan Ilmu Komputer FMIPA UNUD Agus Muliantara, S.Kom.,M.Kom. NIP. 19800616 200501 1 001 Agus Muliantara, S.Kom.,M.Kom. NIP. 19800616 200501 1 001
ii
iii
Judul
: Part-Of-Speech Tagging untuk Dokumen Bahasa Bali Menggunakan Algoritma Brill Tagger
Nama
: Ni Putu Meri Sriyati
NIM
: 1208605026
Pembimbing I
: I Putu Gede Hendra Suputra, S.Kom, M.Kom.
Pembimbing II : Agus Muliantara, S.Kom., M.Kom .
ABSTRAK Setiap hari pertumbuhan data semakin meningkat, sehingga diperlukan text processing untuk mengelola data yang besar. Namun, dalam text processing sering kali muncul permasalahan ambiguitas kata. Hal ini menyebabkan perbedaan arti yang dapat mempengaruhi makna dari sebuah kalimat. Sehingga diperlukan sebuah pelabelan kelas kata atau biasa disebut Part-of-Speech Tagging. Perkembangan teknologi dapat digunakan untuk melestarikan budaya Bali. Penelitian Part-of-Speech Tagging ini digunakan untuk memberikan label pada dokumen bahasa Bali. Metode Brill Tagger menghasilkan aturan yang diperoleh berdasarkan Transformation-based Error Driven Learning sehingga membuat metode Brill Tagger menjadi sangat kompetitif dibandingkan metode stokastik. Metode ini menggunakan dua aturan pembelajaran, yaitu : aturan leksikal dan aturan kontekstual. Pembelajaran aturan leksikal menggunakan pola imbuhan dalam bahasa Bali dan aturan kontekstual menggunakan aturan frasa, pola bigram, dan trigram. Pada proses pembelajaran digunakan 70% kalimat dari dataset yaitu sebanyak 507 kalimat menghasilkan 175 aturan leksikal dan 21 aturan kontesktual. Kedua aturan ini diaplikasikan pada data testing yaitu 30% kalimat dari dataset yang terdiri dari 3413 kata menghasilkan nilai akurasi 90,16%. Kata Kunci : Part-of-Speech Tagging, Brill Tagger, Lexical, Contextual.
iii
iv
Title
: Part-Of-Speech Tagging for Document Bali Language Using Brill Tagger Algorithm
Name
: Ni Putu Meri Sriyati
NIM
: 1208605026
Main Supervisor
: I Putu Gede Hendra Suputra, S.Kom, M.Kom.
Co-Supervisor
: Agus Muliantara, S.Kom., M.Kom.
ABSTRACT Everyday data growth is increasing, so that text processing is required to manage large data. However, in a text processing, it often appears problems of lexical ambiguity. This causes differences that may affect the meaning of a sentence. So, we need a word class labeling or the so-called Part-of-Speech Tagging. The development of technology can be used to preserve the Balinese culture. The research on Part-of-Speech Tagging is used to label Balinese language documents. Brill Tagger method generates rules obtained from Transformation-Based Error Driven Learning, thus causing methods Brill Tagger to be very competitive compared with stochastic method. This method uses two learning rules, namely the lexical rules and contextual rules. Learning lexical rules using affix pattern in Balinese while contextual rules use phrase rules, bigram and trigram patterns. The process of learning uses 70% of sentences from the dataset i.e. as many as 507 sentences generating 175 lexical rules and 21 contextual rules. Both of these rules are applied to the data testing that is 30% of the dataset consisting of 3,413 words generating accuracy value of 90.16%. Keyword : Part-of-Speech Tagging, Brill Tagger, Lexical, Contextual.
iv
v
KATA PENGANTAR Penelitian dengan judul “Part-Of-Speech Tagging untuk Dokumen Bahasa Bali menggunakan Algoritma Brill Tagger” ini disusun dalam rangkaian kegiatan pelaksanaan Tugas Akhir di Jurusan Ilmu Komputer FMIPA UNUD. Sehubungan dengan telah terselesaikannya penelitian ini, maka diucapkan terimakasih dan penghargaan kepada berbagai pihak yang telah membantu penyusun, antara lain : 1. Bapak I Putu Gede Hendra Saputra, S.Kom., M.Kom. selaku Pembimbing I yang telah membimbing dan membantu menyempurnakan penelitian ini. 2. Bapak Agus Muliantara, S.Kom., M.Kom. selaku Pembimbing II sekaligus Ketua Jurusan Ilmu Komputer FMIPA UNUD yang telah banyak membantu dan meluangkan waktu untuk penelitian ini. 3. Bapak Drs. I Gede Nala Antara, M.Hum. selaku Narasumber yang membantu dalam pembuatan dataset pada penelitian ini. 4. Bapak-bapak dan ibu-ibu dosen di Jurusan Ilmu Komputer yang bersedia meluangkan waktunya untuk memberikan masukan dalam penyempurnaan penelitian ini. 5. Rekan-rekan mahasiswa di Jurusan Ilmu Komputer khususnya angkatan 2012 yang telah memberi dukungan, motivasi, semangat dan kerja sama dalam penelitian ini. Penulis menyadari bahwa tugas akhir ini masih belum sempurna, untuk itu kritik dan saran yang bermanfaat demi kesempurnaan tugas akhir ini sangat penyusun harapkan.
Bukit Jimbaran, 4 Januari 2016 Penyusun
Ni Putu Meri Sriyati
v
vi
DAFTAR ISI HALAMAN JUDUL ............................................................................................ i LEMBAR PENGESAHAN TUGAS AKHIR ....................................................... ii ABSTRAK ......................................................................................................... iii ABSTRACT ....................................................................................................... iv KATA PENGANTAR ......................................................................................... v DAFTAR ISI ...................................................................................................... vi DAFTAR TABEL ............................................................................................ viii DAFTAR GAMBAR .......................................................................................... ix DAFTAR LAMPIRAN ....................................................................................... xi BAB I PENDAHULUAN .................................................................................... 1 1.1 Latar Belakang ........................................................................................... 1 1.2 Rumusan Masalah ...................................................................................... 2 1.3 Tujuan Penelitian ....................................................................................... 2 1.4 Batasan Masalah ........................................................................................ 3 1.5 Manfaat Penelitian ..................................................................................... 3 1.6 Metodelogi Penelitian................................................................................. 3 1.6.1 Desain Penelitian ................................................................................. 3 1.6.2 Pengumpulan Data............................................................................... 5 1.6.3 Pengolahan Data Awal ........................................................................ 5 1.6.4 Metode yang Digunakan ...................................................................... 6 BAB II TINJAUAN PUSTAKA .......................................................................... 7 2.1 Tinjauan Empiris ........................................................................................ 7 2.2 Tinjauan Teoritis ........................................................................................ 8 2.2.1 Part-of-SpeechTagging ........................................................................ 8 2.2.2 Penentuan Kelas Kata .......................................................................... 8 2.2.3 Morfologi Tata Bahasa Bali ................................................................ 9 2.2.4 Brill Tagger ....................................................................................... 15 BAB III ANALISIS DAN PERANCANGAN .................................................... 21 3.1 Kebutuhan Fungsional .............................................................................. 21 3.1.1 Melakukan Persiapan ......................................................................... 21 3.2 Rancangan Data ....................................................................................... 22 3.3 Rancangan Antar Muka Sistem ................................................................ 22 3.3.1 Form Tab Persiapan ........................................................................... 22 3.3.2 Form Tab Inisialisasi ......................................................................... 23 3.3.3 Form Tab Training ............................................................................ 24 3.3.4 Form Tab Testing .............................................................................. 25 3.4 Pengolahan Data ...................................................................................... 25 3.4.1 Tahap Persiapan ................................................................................ 25 3.4.2 Tahap Inisialisasi ............................................................................... 28
vi
vii
3.4.3 Tahap Training Data .......................................................................... 29 3.5 Pengujian dan Evaluasi............................................................................. 35 3.5.1 Skenario Pengujian ............................................................................ 35 3.5.2 Evaluasi Sistem ................................................................................. 36 BAB IV HASIL DAN PEMBAHASAN ............................................................ 37 4.1 Pengumpulan Dataset ............................................................................... 37 4.2 Implementasi Pembuatan Lexicon............................................................. 37 4.3 Implementasi Pembuatan Aturan Kontekstual .......................................... 39 4.3.1 Implementasi Pembuatan Bigram ...................................................... 39 4.3.2 Implementasi Pembuatan Trigram ..................................................... 40 4.4 Implementasi Inisialisasi Tag ................................................................... 41 4.5 Implementasi Pelatihan Data Training ...................................................... 42 4.5.1 Implementasi Aturan Leksikal ........................................................... 42 4.5.2 Implementasi Aturan Kontekstual ...................................................... 44 4.4 Impelentasi Data Testing .......................................................................... 46 4.5 Tampilan Antar Muka Sistem .................................................................. 47 4.6 Hasil dan Pengujian Sistem ...................................................................... 50 4.6.1 Analisis Nilai Threshold pada Hasil Pengujian .................................. 50 4.6.2 Pengujian Data Testing ...................................................................... 52 BAB V KESIMPULAN DAN SARAN.............................................................. 55 5.1 Kesimpulan .............................................................................................. 55 5.2 Saran ........................................................................................................ 55 DAFTAR PUSTAKA ........................................................................................ 56 LAMPIRAN ...................................................................................................... 57
vii
viii
DAFTAR TABEL Tabel
Halaman
Tabel 2. 1 Contoh Lexicon ................................................................................... 9 Tabel 2. 2 Daftar Kelas Kata yang Digunakan dalam Penelitian ......................... 10 Tabel 2. 3 Aturan Imbuhan Prefiks (Awalan) ..................................................... 12 Tabel 2. 4 Aturan Imbuhan Infiks (Sisipan) ........................................................ 13 Tabel 2. 5 Aturan Imbuhan Sufiks (Akhiran)...................................................... 13 Tabel 2. 6 Aturan Imbuhan Konfiks ................................................................... 14 Tabel 2. 7 Daftar Proses Hilangnya Fonem ........................................................ 14 Tabel 3. 1 Contoh Kata dan Tag dengan nilai frekuensi ...................................... 28 Tabel 3. 2 Contoh Aturan Imbuhan Beserta Tag ................................................. 30 Tabel 3. 3 Contoh Aturan Imbuhan dengan Nilai Skornya .................................. 31 Tabel 3. 4 Aturan Frasa untuk Membuat Aturan Kontekstual ............................. 33 Tabel 3. 5 Contoh Aturan Kontekstual dari Aturan Frasa ................................... 33 Tabel 3. 6 Contoh Aturan Kontekstual Menggunakan Pola Bigram .................... 33 Tabel 3. 7 Contoh Aturan Kontekstual Menggunakan Pola Trigram ................... 33 Tabel 3. 8 Tabel Pengujian ................................................................................. 36 Tabel 4. 1 Dataset yang Digunakan Dalam Penelitian ........................................ 37 Tabel 4. 2 Hasil Pengujian Menggunakan Nilai Threshold ................................. 51 Tabel 4. 3 Hasil Testing Data ............................................................................. 53
viii
ix
DAFTAR GAMBAR Gambar
Halaman
Gambar 1.1 Tahapan dalam POS Tagging Dokumen Bahasa Bali.......................15 Gambar 2.1 Error-driven learning module(Brill,1995).........................................16 Gambar 2.2 Contoh Transformation-based Error Driven Learning(Brill,1995)...17 Gambar 3. 1 Rancangan Tampilan Memasukkan Data ....................................... 23 Gambar 3. 2 Rancangan Tampilan Proses Inisialisasi ......................................... 24 Gambar 3. 3 Rancangan Tampilan Tahap Training Rule..................................... 24 Gambar 3. 4 Rancangan Tampilan Pengujian Data Testing ................................ 25 Gambar 3. 5 Contoh Tagged Corpus .................................................................. 26 Gambar 3. 6 Contoh Untagged Corpus ............................................................... 26 Gambar 3. 7 Contoh Lexical Rule ...................................................................... 27 Gambar 3. 8 Contoh Contextual Rule ................................................................. 28 Gambar 3. 9 Flowchart Proses Inisialisasi .......................................................... 29 Gambar 3. 10 Flowchart Proses Training Lexical ............................................... 32 Gambar 3. 11 Flowchart Proses Training Aturan Kontekstual ............................ 34 Gambar 3. 12 Pengujian dengan Melihat Keakuratan Tag Sistem ....................... 35 Gambar 4. 1 Pemisahan Kata dan Menghitung Frekuensi Kata ........................... 38 Gambar 4. 2 Sintak Pembuatan Lexicon ............................................................. 38 Gambar 4. 3 Sintak Membuat Bigram Depan ..................................................... 40 Gambar 4. 4 Sintak Membuat Bigram Belakang ................................................. 40 Gambar 4. 5 Sintak Pembuatan Trigram ............................................................. 41 Gambar 4. 6 Sintak Proses Inisialisasi Tag Unknown Word ............................... 41 Gambar 4. 7 Sintak Menentukan Nilai Tag Pada Unknown Word ...................... 42 Gambar 4. 8 Sintak Method Aturan Leksikal...................................................... 43 Gambar 4. 9 Sintak ArrayList dari Aturan Leksikal ............................................ 43 Gambar 4. 10 Sintak Menghitung Nilai Score .................................................... 43 Gambar 4. 11 Sintak Menetukan Nilai Tag......................................................... 44 Gambar 4. 12 Sintak Memanggil Class Contextual Rule..................................... 44 Gambar 4. 13 Sintak Method Bigram Aturan Kontekstual .................................. 45 Gambar 4. 14 SIntak Method Trigram Aturan Kontekstual................................. 45
ix
x
Gambar 4. 15 Sintak ArrayList Aturan Kontesktual ........................................... 45 Gambar 4. 16 Sintak Menghitung Nilai Score .................................................... 46 Gambar 4. 17 Sintak Menerapkan Aturan Leksikal ............................................ 46 Gambar 4. 18 Sintak Menerapkan Aturan Kontekstual ....................................... 47 Gambar 4. 19 Sintak Membandingkan Hasil Tag Sistem dengan Goal Tag ........ 47 Gambar 4. 20 Tampilan Pada Tab Persiapan ...................................................... 48 Gambar 4. 21 Proses Pada Tab Inisialisasi Tag .................................................. 48 Gambar 4. 22 Tampilan Daftar Lexical dan Contextual Rule .............................. 49 Gambar 4. 23 Tampilan Tab Proses Training Data ............................................. 49 Gambar 4. 24 Tampilan Tab Testing .................................................................. 50 Gambar 4. 25 Grafik Pengujian Nilai Threshold ................................................. 52 Gambar 4. 26 Grafik Pengaruh Nilai Threshold Terhadap Jumlah Rule .............. 52 Gambar 4. 27 Kesalahan Tag Karena Kata Dasar Tidak Ada Pada Lexicon ........ 54 Gambar 4. 28 Kesalahan Tag Karena Rule Tidak Masuk Dalam Output Rule ..... 54
x
xi
DAFTAR LAMPIRAN Lampiran 1. Daftar Aturan Leksikal 2. Daftar Aturan Kontekstual
xi