PENERAPAN METODE RULE-BASED DENGAN UNSUPERVISED LEARNING UNTUK PELABELAN DOKUMEN BERBAHASA INDONESIA
Oleh:
M Karibun H S G64101053
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR 2005
ABSTRAK M KARIBUN H S. Penerapan Metode Rule-based dengan Unsupervised Learning untuk Pelabelan Dokumen Berbahasa Indonesia. Dibimbing oleh YENI HERDIYENI dan PANJI WASMANA. Penelitian ini menerapkan metode Rule-based dengan Unsupervised Learning untuk pelabelan dokumen teks berbahasa Indonesia. Metode Rule-based menggunakan pola kata untuk menentukan label dari kata yang tidak diketahui. Pola diperoleh melalui proses pembelajaran otomatis dan diurutkan berdasarkan frekuensi kemunculan. Pelabelan kata yang ambigu atau tidak diketahui labelnya dilakukan dengan cara melihat pola kata sekitar dan mengambil pola kata dengan frekuensi kemunculan terbesar. Penambahan metode pengujian jenis imbuhan pada sistem diharapkan dapat meningkatkan pengenalan label pada dokumen. Penelitian menggunakan 102 dokumen teks yang terdiri dari 305.989 token untuk proses pelatihan dan menghasilkan 7.706 rule. Basis data rule yang diperoleh dari proses pembelajaran dan basis data perubahan jenis kata berdasarkan imbuhan digunakan untuk proses pengujian sistem. Pengujian menggunakan 52 dokumen teks yang terdiri dari 131.719 token. Pengujian menghasilkan 97,82 % token yang berhasil dikenali . Pengujian manual terhadap 3 dokumen yang terdiri dari 431 token menghasilkan tingkat kebenaran 85,85%. Kata Kunci: Part of Speech Tagging, Natural Language, Information Retrieval, Algoritma Eric Brill, dan Computational Linguistic.
PENERAPAN METODE UNSUPERVISED LEARNING RULE-BASED PART OF SPEECH TAGGING UNTUK PELABELAN PADA DOKUMEN BERBAHASA INDONESIA
M Karibun H S
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Komputer pada Departemen Ilmu Komputer
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOG OR 2005
Judul
: Penerapan Metode Rule-based dengan Unsupervised Learning untuk Pelabelan Dokumen Berbahasa Indonesia.
Nama
: M Karibun H S
NRP
: G64101053
Menyetujui,
Pembimbing I
Pembimbing II
Yeni Herdiyeni, S.Si., M.Kom
Panji Wasmana, S.Kom., M.Si
NIP. 132 282 665
NIP. 132 311 917
Mengetahui, Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam
Dr. Ir. Yonny Koesmaryono, M.Si NIP. 131 473 999
Tanggal Lulus:…………..
RIWAYAT HIDUP Penulis dilahirkan di RSCM, Jakarta pada tanggal 17 November 1981 sebagai anak pertama dari dua bersaudara, anak dari pasangan Bapak Hamdan Eddy Yassin dan Ibu Pipiet Senja. Penulis menikah pada tanggal 15 Februari 2000 dengan Seli Siti Sholihat. Penulis menyelesaikan sekolah menengah umum di SMUN 3 Depok, lulus pada tahun 1999. Setelah lulus melanjutkan pendidikannya di Jurusan Biologi Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Indonesia selama dua tahun (1999-2001). Pada tahun 2001, penulis mengikuti Seleksi Penerimaan Mahasiswa Baru (SPMB) ke Departemen Ilmu Komputer Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor. Penulis sempat aktif di Badan Kerohanian Islam Mahasiswa (BKIM) pada tahun 2001-2002 dan menjadi ketua angkatan 38 BKIM Baranangsiang. Selama kuliah, penulis pernah menjadi staf pengajar di Pengabdian Pada Masyarakat (P2M) Fakultas Teknik Universitas Indonesia Salemba pada tahun 20012004. Penulis juga pernah menjadi Asisten Dosen Praktikum Departemen Ilmu Komputer pada tahun 2002-2004. Penulis pernah menjadi ketua Bareng Karib Silaturahmi Mahasiswa Ilkom (Bakar Singkong) pada tahun 2002. Penulis juga menjadi anggota Divisi Riset dan Development di Himpunan Mahasiswa Ilmu Komputer (HIMALKOM) pada tahun 2003-2004. Pada tahun 2004 penulis menjadi pengajar pada pelatihan Microsoft Visual C++ 6.0 di P2M FTUI. Pada tahun 2005 penulis melakukan Praktik Kerja Lapang (PKL) di Divisi Hukum Bank Indonesia Thamrin Jakarta. Bidang yang diminati penulis berkaitan dengan kecerdasan buatan, yaitu Computational Linguistic, Image Processing, dan Speech Recognition.
PRAKATA Alhamdulillahirobbil’alamin penulis ucapkan atas segala limpahan rahmat dan hidayah-Nya sehingga penulis dapat menyelesaikan karya ilmiah ini. Melalui lembar ini, penulis ingin menyampaikan penghargaan dan terima kasih kepada semua fihak atas bantuan, dorongan, saran, kritik, serta koreksi yang ditujukan selama penulisan karya ilmiah ini. Ucapan terima kasih penulis ucapkan kepada: 1. Istri tercinta, Seli Siti Sholihat, atas semua kasih sayang, cinta, bimbingan, dan segala hal yang tak mungkin tersebut satu persatu disini. Semoga cinta kita tetap abadi dan semoga keluarga kita termasuk keluarga yang dirahmati Allah, keluarga sakinah. 2. Mama tercinta dan tersayang, Pipiet Senja, atas semua doa dan kesempatan mengenal kasih sayang ibu di dunia ini. Serta papa, Hamdan Eddy Yassin, atas semua bantuan finansialnya. 3. Adik, Adzimattinur Siregar, yang telah mensuplai komik penghilang stress selama penulisan karya ilmiah ini. 4. Mertua, Sri Mulyati dan khususnya Engkos Kosasih atas semua nasihat, bimbingan, dan kesempatan untuk mengenal semua warna kehidupan. 5. Ibu Yeni Herdiyeni, S.Si, M.Kom. dan bapak Panji Wasmana, S.Kom, M.Si. sebagai pembimbing skripsi I dan II atas segala bimbingan, saran, kritik, dan kesabarannya atas penelitian ini. 6. Seluruh staf pengajar Departemen Ilmu Komputer atas semua ilmu dan contoh kepribadiannya selama penulis kuliah di Departemen Ilmu Komputer. 7. Usep Aris Sutandi, S.Kom. atas segala bentuk persahabatan, saran, kritik, dan contekan format penulisan karya ilmiahnya. 8. Semua penghuni DC-7 pada tahun 2002-2004 atas semua bentuk persahabatan, kesenangan, dan pendidikan kepribadiannya. 9. Ibu Yayuk dan seluruh staf administrasi Departemen Ilmu Komputer atas segala pengabdian dan kesabarannya. Akhir kata, semoga karya ilmiah ini dapat dipergunakan untuk kemashlahatan kita bersama.
Depok, Oktober 2005
Penulis
DAFTAR ISI Halaman DAFTAR TABEL………………………………………………………………….………………....……vii DAFTAR LAMPIRAN…………………………………………………………….………………............vii PENDAHULUAN Latar Belakang………………………………………………………………..……………….……...1 Tujuan………………………………………………………………………...………………. ……...2 Ruang Lingkup Penelitian……………………………………………………………………….……2 TINJAUAN PUSTAKA Pembagian Jenis Kata………………………………………………………..……………………….2 Grammar…………………………………………………………………….. ……………… ….……3 Token………………………………………………………………………………………………….4 Part of Speech……………………………………………………………….. ……………… ……….4 Stemming…………………………………………………………………….. ……………………….4 N th Order Tagging…………………………………………………………………………… ……….4 Polisemi……………………………………………………………………………………………….4 Kinerja sistem………………………………………………………………...……………………….5 METODOLOGI Transformation Based Learning……………………………………………...……………….………5 Proses Pelabelan Kata………………………………………………………...……………………….5 Pemberian Label berdasarkan Imbuhan……………………………………………………… ……….6 HASIL DAN PEMBAHASAN Implementasi sistem…………………………………………………………………………..............8 Basis data sistem……………………………………………………………...……………….………9 Proses pembelajaran…………………………………………………………. ………………………..9 Ukuran pengujian…………………………………………………………..………………………….9 Hasil pengujian……………………………………………………………..…………………………9 Persentase pengujian tagset dan imbuhan………………………………….………………………...10 Persentase token yang ambigu………………………………………………..……………………...10 Persentase pengujian pola…………………………………………………..………………………..10 Persentase token yang berhasil dikenali……………………………………...……………… ………10 Persentase token yang tidak berhasil diidentifikasi…………………………..……………… ……...10 Persentase token yang berhasil diidentifikasi secara benar…………………………………… …….11 KESIMPULAN DAN SARAN Kesimpulan…………………………………………………………………...………………. …….11 Saran………………………………………………………………………….………………. …….11 DAFTAR PUSTAKA……………………………………………………………………………… ………11 LAMPIRAN………………………………………………………………………... ………………………13 DAFTAR TABEL Halaman 1. Spesifikasi implementasi sistem…………………………………………..………………………………9 2. Data hasil pembelajaran…………………………………………………………………………………..9 3. Data hasil pengujian sistem…………………………………………………...………………………….9 DAFTAR GAMBAR Halaman 1. Proses tokenizing teks…………………………………………………………………………… ……….5 2. Proses pelabelan kata.…………………………………………………...……………………… ………..6 3. Proses pengujian imbuhan……………………………………………………..…………………………6
DAFTAR LAMPIRAN Halaman 1. Tahapan ekstraksi jawaban pada Question Answering System (QAS)………… ………………………14 2. Klasifikasi pendekatan algoritma Part of Speech Tagging……………………... ……………… ……….15 3. Proses rule-based tagging……………………………………………………….……………………….16
PENDAHULUAN Latar Belakang Part-of-Speech Tagging adalah proses pemberian label klasifikasi pada setiap bagian dari dokumen teks berbasis bahasa natural. Part-of-Speech Tagging yang akurat merupakan langkah awal yang kritis bagi pemrosesan bahasa natural (Vasilakopoulos, 2003). Part-o f-Speech Tagging juga merupakan suatu tahapan penting dalam Question Answering System (QAS). Posisi Part-ofSpeech Tagging dalam QAS dapat dilihat pada Lampiran 1. Pada lampiran terlihat bahwa keluaran dari proses Part-of-Speech Tagging merupakan dasar dari pengubahan suatu dokumen teks menjadi bentuk logik. QAS menggunakan keluaran dari Part-of-Speech Tagging untuk mencari jawaban terhadap pertanyaan yang diajukan pada sistem mengenai suatu dokumen teks. Beberapa penelitian mengenai Part-ofSpeech Tagging yang telah dilakukan sebelumnya, dapat dikelompokkan seperti pada Lampiran 2 (James, 1995). Pengelompokan pertama adalah sistem supervised dan unsupervised. Pada sistem supervised, dokumen yang sudah dilabeli secara manual dimasukkan ke dalam sistem untuk dipelajari. Selanjutnya sistem akan membentuk basis data pola berdasarkan dokumen yang dimasukkan. Sementara pada sistem unsupervised, tidak dilakukan pelabelan secara manual pada dokumen yang dimasukkan untuk dipelajari oleh sistem. Sehingga sistem diharuskan untuk melabeli setiap kata dan mempelajari sendiri pola-pola yang ada. Masing-masing pendekatan memiliki kelebihan dan kekurangan. Pendekatan supervised memudahkan sistem untuk mengenali kata atau pola yang baru. Kekurangan dari pendekatan ini adalah lamanya waktu pembelajaran yang dibutuhkan dan besarnya kemungkinan keputusan yang ambigu. Sementara pada sistem unsupervised, dapat diharapkan terbentuknya sebuah sistem yang mengerti semua bahasa yang ada. Kekurangan dari sistem ini adalah lamanya atau sulitnya proses pelabelan ketika sistem diperkenalkan pada sesuatu yang baru dan belum memiliki referensi sebelumnya.
Pembagian selanjutnya adalah Part-ofSpeech Tagging berbasis rule, stochastic dan neural network . Pada Part-of-Speech Tagging berbasis rule, sistem mengandalkan ketersediaan basis data pola yang akan digunakan untuk memutuskan klasifikasi sebuah kata. Sementara pada stochastic, sistem akan menggunakan prinsip-prinsip statistik dalam pengklasifikasian kata. Dan pada pendekatan dengan teknik neural network , sistem akan menggunakan teknik jaringan saraf tiruan untuk menggolongkan kata-kata yang dimasukkan ke dalam sistem (James, 1995). Beberapa penelitian yang telah dilakukan di antaranya: -
Penelitian Part-of-Speech Tagging dengan menggunakan algoritma Baum-Welch menghasilkan tingkat akurasi 86,6% (Cutting et al, 1992). Penelitian menggunakan Penn Treebank Corpus yang terdiri dari 120.000 kata.
-
Penelitian Eric Brill (1995), Unsupervised Learning Rule-based Part-of-Speech Tagging dapat mengidentifikasi secara benar lebih dari 90% token ambigu. Penelitian menggunakan data pelatihan 120.000 kata dan data tes 200.000 kata.
-
Penelitian Rabiner (1989), Hidden Markov Models Part-of-Speech Tagging memiliki tingkat akurasi 96,5%. Penelitian ini juga menggunakan Penn Treebank yang terdiri dari 120.000 kata. Penelitian ini juga menggunakan Brown Corpus sebagai perbandingan yang tersusun dari 350.000 kata.
-
Penelitian Weischedel (1993), Maximum Entropy Model Part-of-Speech Tagging, memiliki tingkat akurasi 85%. Penelitian ini menggunakan Penn Treebank yang terdiri dari 120.000 kata dan Wall Street Journal Corpus sebagai perbandingan yang tersusun dari 133.805 kata.
Penelitian mengenai Part-of-Speech Tagging yang ada sebelumnya dibangun dengan menggunakan bahasa Inggris. Sehingga dibutuhkan beberapa penyesuaian untuk penggunaan pada bahasa Indonesia.
1
Tujuan
Yang termasuk dalam jenis kata ini adalah segala kata yang dipakai untuk menggantikan kata benda atau yang dibendakan. Pembagian tradisional menggolongkan kata-kata ini ke dalam suatu jenis kata yang tersendiri.
Penelitian ini bertujuan untuk mengimplementasikan metode Rule-based dengan Unsupervised Learning untuk pelabelan kata dalam bahasa Indonesia. Ruang Lingkup Penelitian
Kata ganti menurut sifat dan fungsinya dapat dibedakan atas:
Ruang lingkup penelitian ini meliputi: 1.
Pembelajaran dan pembentukan basis data pola kata dalam kalimat
a. Kata ganti Personalia
2.
Pembentukan basis data referensi kata
3.
Pembuatan metode penentuan label kata berdasarkan imbuhan
b. Kata ganti kepemilikan atau Pronomina Possessiva
4.
Perhitungan dan pengukuran kinerja sistem
e. Kata ganti penanya atau Pronomina Interrogativa
Secara sederhana, terdapat 10 jenis kata dalam bahasa Indonesia (Keraf, 1980):
f. Kata ganti tak tentu atau Pronomina Indeterminativa 5.
Kata benda adalah nama dari semua benda dan segala yang dibendakan. Selanjutnya kata-kata benda, menurut wujudnya, dibagi atas:
b. Kata benda abstrak
3.
Kata sifat atau Adjektif (Adj) Kata yang menyatakan sifat atau hal keadaan dari suatu benda: tinggi, rendah, lama, baru, dan sebagainya digolongkan sebagai kata sifat.
4.
- Kata bilangan utama (Nume ralia Cardinalia): satu, dua, tiga, seratus, dan sebagainya.
Kata kerja atau Verba (Vb) Semua kata yang menyatakan perbuatan atau laku digolongkan ke dalam kata kerja. Bila suatu kata kerja menghendaki adanya suatu pelengkap maka disebut kata kerja transitif, misalnya: memukul, menangkap, melihat, mendapat, dan sebagainya. Sebaliknya bila kata kerja tersebut tidak membutuhkan suatu pelengkap maka disebut kata kerja intransitif, misalnya: menangis, meninggal, berjalan, berdiri, dan sebagainya.
Kata ganti atau Pronomina (Pro)
Kata bilangan atau Numeralia (Num) Kata bilangan adalah kata yang menyatakan jumlah benda atau jumlah kumpulan atau urutan tempat dari namanama benda. Menurut sifatnya, kata bilangan dapat dibagi atas:
a. Kata benda konkrit
2.
Pronomina
d. Kata ganti penghubung atau Pronomina Relativa
Pembagian Jenis Kata
Kata benda atau Nomina (N)
atau
c. Kata ganti petunjuk atau Pronomina Demonstrative
TINJAUAN PUSTAKA
1.
orang
- Kata bilangan tingkat (Numeralia Ordinalia): pertama, kedua, ketiga, kelima, kesepuluh, dan sebagainya. - Kata bilangan tak tentu: beberapa, segala, semua, tiap-tiap, dan sebagainya. - Kata bilangan kumpulan: berdua, bertiga, bertujuh, dan sebagainya. 6.
Kata keterangan atau Adverbia (Adv) Kata-kata keterangan atau adverbia adalah kata-kata yang memberi keterangan tentang: a. Kata kerja b. Kata sifat c. Kata keterangan d. Kata bilangan
2
