SISTEM PERINGKASAN DOKUMEN BERITA BAHASA INDONESIA MENGGUNAKAN METODE REGRESI LOGISTIK BINER
MERI MARLINA
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2012
SISTEM PERINGKASAN DOKUMEN BERITA BAHASA INDONESIA MENGGUNAKAN METODE REGRESI LOGISTIK BINER
MERI MARLINA
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 BOGOR BOGOR 2012
ABSTRACT
MERI MARLINA. Text Feature Weighting for Summarization of Document Bahasa Indonesia Using binary logistic regression. Under direction of JULIO ADISANTOSO. This thesis aims to perform text feature weighting for summarization of document bahasa Indonesia using binary logistic regression. There are ten text features, i.e., sentence position (f1), positive keywords in sentence (f2), negative keywords in sentence (f3), sentence centrality (f4), sentence resemblance to the title (f5), sentence inclusion of name entity (f6), sentence inclusion of numerical data (f7), sentence relative length (f8), bushy path of the node (f9), and summation of similarities for each node (f10). Ten of these features will be used as an independent variable in the calculation of the binary logistic regression. To denote that the sentence is not included in the summary we use an output value of 0, an output value of 1, otherwise. To evaluate the text summarization, we use N-Gram with compressin rate 30%. Research results show that the accuracy of this method is 42.84%. Keywords: text summarization, binary logistic regression, text features
Judul Skripsi
: Sistem Peringkasan Dokumen Berita Bahasa Indonesia Menggunakan MetodeRegresi Logistik Biner
Nama
: Meri Marlina
NRP
: G64080114
Menyetujui: Pembimbing
Ir. Julio Adisantoso, M.Kom NIP.19620714 198601 1 002
Mengetahui: Ketua Departemen Ilmu Komputer
Dr. Ir. Agus Buono, M.Si, M.Kom NIP. 19660702 199302 1 001
Tanggal Lulus :
KATA PENGANTAR Alhamdulilahirobbil’alamin, segala puji bagi Allah subhanahu wata’ala atas segala limpahan rahmat serta karunia-Nya sehingga penulis mampu menyelesaikan penelitian ini dengan baik. Penulis juga menyampaikan terima kasih kepada seluruh pihak yang telah berperan dalam penelitian ini, yaitu: 1 Orang tua tercinta, ayahanda Supriatna, ibunda Dedeh, dan kakak yang saya sayangi Deasy, atas doa, kasih sayang, dukungan, serta motivasi kepada penulis untuk penyelesaian penelitian ini. 2 Bapak Ir. Julio Adisantoso, M.Kom selaku dosen pembimbing tugas akhir yang telah memberi banyak ide, saran, bantuan, serta dukungan sampai selesainya penelitian ini. 3 Rekan-rekan seperjuangan di Ilmu Komputer IPB angkatan 45 atas segala kebersamaan, bantuan, dukungan, serta kenangan bagi penulis selama menjalani masa studi. Semoga kita bisa berjumpa kembali kelak sebagai orang-orang sukses. 4 Rekan-rekan satu bimbingan, Susi Handayani, Anita, Putri Dewi P, Fania Rahmania, Alfa Nugraha P, Rizky Utama, Meriska Defriani, dan Hafizhia Dhikrul A,yang telah bersama berjuang dalam mengerjakan tugas akhir mengenai Temu Kembali Informasi. 5 Senior dan sahabat, Tiara Mitra Lia, Ryanti Octaviani S, Annisa Anastasia, Anita, Cut Malisa I, Niken Eka, Wangi Saraswati, Doni Suhartono, dan Ahmad Rivai yang telah menjadi mitra dan bantuannya selama penyelesaikan tugas akhir ini. 6 Seluruh staf Departemen Ilmu Komputer IPB yang telah banyak membantu baik selama penelitian maupun perkuliahan. Penulis berharap penelitian ini dapat memberikan manfaat baik sekarang maupun di masa mendatang.
Bogor, September 2012
Meri Marlina
RIWAYAT HIDUP
Meri Marlina dilahirkan di Karawang pada tanggal 20 Mei 1991. Penulis merupakan anak pertama dari pasangan Supriatna dan Dedeh Endang Ratnawati. Pada tahun 2008, penulis lulus dari Sekolah Menengah Atas 1 Cikampek. Penulis mengikuti tes SNMPTN pada tahun 2008 dan diterima di Program Studi Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam. Selama aktif menjadi mahasiswa, penulis menjadi salah satu pengurus Himpunan Mahasiswa Ilmu Komputer (Himalkom) pada tahun 2010. Selama mengikuti perkuliahan penulis menjadi asisten praktikum untuk Mata Kuliah Rekayasa Perangkat Lunak di Departemen Ilmu Komputer Institut Pertanian Bogor. Penulis juga melakukan praktik kerja lapang di Kantor Kominfo Bogor pada tahun 2011.
DAFTAR ISI Halaman DAFTAR TABEL ............................................................................................................................vi DAFTAR GAMBAR .......................................................................................................................vi DAFTAR LAMPIRAN ....................................................................................................................vi PENDAHULUAN Latar Belakang .............................................................................................................................. 1 Tujuan Penelitian .......................................................................................................................... 1 Ruang Lingkup Penelitian ............................................................................................................ 1 METODE PENELITIAN Pengumpulan Dokumen Teks ....................................................................................................... 1 Tahap Pelatihan ............................................................................................................................ 2 Tahap Pengujian ........................................................................................................................... 6 HASIL DAN PEMBAHASAN Data Korpus .................................................................................................................................. 6 Format Dokumen .......................................................................................................................... 6 Implementasi Sistem ..................................................................................................................... 6 Pemodelan Regresi Logistik Biner ............................................................................................... 7 Pengujian Menggunakan N-gram ................................................................................................. 8 Hasil Perbandingan dengan Algoritme Genetika .......................................................................... 8 SIMPULAN DAN SARAN Simpulan ....................................................................................................................................... 9 Saran ............................................................................................................................................. 9 DAFTAR PUSTAKA ....................................................................................................................... 9 LAMPIRAN .................................................................................................................................... 10
v
DAFTAR TABEL
Halaman 1 Contoh paragraf, pemisahan kalimat dan case folding .................................................................. 7 2 Hasil akurasi menggunakan algoritme genetika ............................................................................ 8
DAFTAR GAMBAR Halaman 1 Peringkasan teks otomatis. ............................................................................................................ 2 2 Ilustrasi kemiripan antar-kalimat. .................................................................................................. 3 3 Ilustrasi koneksi antar-kalimat. ..................................................................................................... 4 4 Kurva logistik (Kleinbaum & Klein 2010). ................................................................................... 6 5 Contoh code pembacaan dokumen. ............................................................................................... 7
DAFTAR LAMPIRAN Halaman 1 Diagram alir algoritma genetika sederhana (Kusumadewi 2003). .............................................. 11 2 Format dokumen pada tahap pelatihan dan pengujian ................................................................ 12 3 Antarmuka sistem peringkasan teks ............................................................................................. 13 4 Contoh nilai nilai fitur untuk setiap kalimat dalam satu dokumen .............................................. 14 5 Tabel model persamaan regresi logistik biner .............................................................................. 15 6 Contoh dokumen berita 34.txt .................................................................................................... 16 7 Antarmuka hasil sistem dokumen berita 34.txt ............................................................................ 17 8 Hasil pengujian antara hasil peringkasan manual dan hasil peringkasan sistem menggunakan N-gram ................................................................................................................. 18
vi
PENDAHULUAN Latar Belakang Pada saat ini, arus informasi dari internet berkembang dengan sangat cepat dan akan terus bertambah. Pertambahan arus informasi ini berbanding lurus dengan pertambahan dokumen di internet. Sebagai contoh, dokumen berita akan terus bertambah seiring dengan bertambahnya peristiwa-peristiwa penting mengenai suatu kejadian. Berita merupakan suatu informasi yang penting dan terbaru tentang suatu kejadian secara berkala. Banyaknya isi dari dokumen berita di internet membuat sebagian orang kurang tertarik untuk membaca dokumen berita tersebut. Hal ini dikarenakan setiap orang memiliki waktu yang berbeda dan terbatas sehingga sebagian orang cenderung tidak membaca dokumen berita tersebut. Membaca merupakan suatu proses kegiatan fisik dan mental yang dilakukan untuk mendapatkan sebuah informasi baru, namun membaca dan memahami isi suatu dokumen yang sangat banyak membutuhkan waktu yang cukup lama. Oleh karena itu, ringkasan dokumen menjadi hal yang penting karena terbatasnya waktu yang dimiliki setiap orang. Namun, meringkas dokumen secara manual oleh manusia membutuhkan waktu dan biaya yang besar bila dokumen memiliki kalimat yang cukup banyak sehingga dibutuhkan suatu sistem ringkasan secara otomatis yang dapat meminimalisir waktu dan biaya yang dibutuhkan untuk meringkas suatu dokumen (Aristoteles 2011). Menurut Manning et al. (2008), peringkasan teks adalah proses penyaringan informasi yang paling penting dari suatu sumber (atau beberapa sumber) untuk menghasilkan dokumen yang ringkas untuk pengguna. Banyak penelitian yang telah dilakukan tentang peringkasan teks, antara lain Fattah dan Ren (2008) yang menghitung sepuluh pembobotan fitur untuk setiap kalimat dalam suatu dokumen menggunakan algoritme genetika dan regresi matematika. Penelitian selanjutnya dilakukan oleh Aristoteles (2011) yang membuat pembobotan fitur pada peringkasan teks bahasa Indonesia menggunakan algoritme genetika dengan melibatkan kalimat semantik pada pembobotan fitur. Permasalahan dari peringkasan teks adalah menentukan pembobotan dari setiap kalimat. Pada penelitian Aristoteles (2011), penggunaan algoritme genetika memiliki perhitungan yang rumit dan waktu komputasi
yang cukup lama dalam menghasilkan suatu ringkasan dokumen sehingga dibutuhkan metode yang dapat mempersingkat waktu komputasi tersebut, yaitu dengan menggunakan metode regresi logistik biner. Pada kasus-kasus penelitian dengan tujuan mengetahui hubungan antara suatu peubah dependent berupa data kategorik dan peubah independent berupa data numerik, analisis regresi linear standar tidak bisa dilakukan. Oleh karena itu, salah satu pendekatan yang dapat dilakukan adalah regresi logistik biner. Regresi logistik biner merupakan salah satu alat statistik yang digunakan untuk menganalisis beberapa faktor dengan sebuah variabel yang bersifat biner. Pada peringkasan dokumen secara otomatis, kalimat-kalimat yang terpilih menjadi hasil ringkasan merupakan kalimat yang dianggap penting. Penting atau tidaknya suatu kalimat tergantung pada nilai peluang dari hasil perhitungan beberapa fitur. Oleh karena itu, penelitian ini menelaah peringkasan teks dengan membuat pembobotan fitur menggunakan metode regresi logistik biner. Hasil dari penelitian akan dibandingkan dengan hasil penelitian dari Aristoteles (2011) yang meneliti tentang pembobotan fitur pada peringkasan teks bahasa Indonesia menggunakan algoritme genetika. Tujuan Penelitian Tujuan penelitian ini ialah menentukan pembobotan fitur menggunakan regresi logistik biner pada peringkasan teks. Ruang Lingkup Penelitian Penelitian ini difokuskan pada peringkasan dokumen berita dengan dokumen yang digunakan berjenis teks bahasa Indonesia, tema dokumen yang digunakan adalah berita nasional, diasumsikan bahwa semua kalimat dalam sebuah dokumen adalah benar, dan dokumen yang digunakan adalah dokumen berjenis teks.
METODE PENELITIAN Penelitian ini dilakukan dengan beberapa tahap yaitu tahap pengumpulan dokumen, tahap pelatihan, dan tahap pengujian. Diagram alur proses dapat dilihat pada Gambar 1. Pengumpulan Dokumen Teks Dokumen yang digunakan dalam penelitian ini adalah 100 dokumen untuk tahap
2
pelatihan dan 50 dokumen untuk tahap pengujian. Pada tahap pengujian, 50 dokumen diringkas secara manual, tujuannya untuk membandingkan ringkasan manual dengan hasil ringkasan sistem. Dokumen yang digunakan dalam penelitian ini adalah dokumen yang berasal dari dokumen berita online harian Kompas yang didapat dari korpus penelitian Ridha (2002). Tahap Pelatihan Tahap pelatihan yang dilakukan ialah: pembobotan fitur teks dan perhitungan skor menggunakan regresi logistik biner.
I
Pengumpulan dokumen 150 dokumen berita
II Tahap pelatihan 100 dokumen Fitur teks
Perhitungan koefisien (regresi logistik biner)
1
Posisi Kalimat (f1)
Posisi kalimat adalah kalimat pertama yang paling penting dari sebuah paragraf. Berikut ini adalah contoh fitur teks posisi kalimat pada sebuah dokumen. Jakarta, Kompas - Komisi Penyelidik Pelanggaran Hak Asasi Manusia (KPP HAM) Trisakti dan Semanggi I-II tetap akan membuat kesimpulan dan menyampaikan rekomendasi mengenai hasil penyelidikannya, meskipun perwira TNI/Polri tidak mau memenuhi panggilan KPP HAM. Namun, demikian, panggilan kedua terhadap sejumlah perwira TNI/Polri telah dilayangkan kepada mereka. Hal itu dikatakan Ketua KPP HAM Albert Hasibuan kepada Kompas di Jakarta akhir pekan lalu. Hasibuan masih mengharapkan perwira TNI/Polri itu memenuhi panggilan KPP HAM. "Tapi, kalau mereka menolak, ya sudah. Kita akan tetap membuat kesimpulan dan rekomendasi berdasarkan keterangan saksi-saksi lain yang telah kita dengar. Rekomendasi itu tentunya akan merugikan mereka sendiri," ujarnya. Misal terdapat tiga kalimat dalam satu paragraf. Kalimat pertama diberi bobot 3/3, kalimat kedua 2/3 dan kalimat ketiga 1/3. Kalimat terakhir tidak begitu penting sehingga diberi bobot 0.
Model
Implementasi
bobot sehingga dapat diketahui kalimat yang masuk dalam ringkasan dan tidak masuk ringkasan. Menurut Fattah dan Ren (2008), terdapat sepuluh fitur teks yang dapat dihitung untuk setiap kalimat dari sebuah dokumen. Fitur teks tersebut yaitu:
50 dokumen
III Tahap pengujian
Hasil ringkasan sistem
Ringkasan manual
2
Positive Keyword (f2)
Positive keyword adalah suatu kata yang sering muncul dalam suatu dokumen (peringkasan). P(keywordi)=
Evaluasi N-Gram
Gambar 1 Peringkasan teks otomatis. Tahap pembobotan fitur dilakukan untuk mendapatkan nilai bobot tertinggi dari suatu kalimat. Bobot yang memiliki nilai tinggi akan dimasukkan dalam peringkasan. Fitur teks merupakan suatu proses perhitungan fitur-fitur untuk mendapatkan
dengan s(E) adalah jumlah kata dalam suatu kalimat yang mengandung keyword dan s(K) adalah jumlah kata dalam kalimat lain yang mengandung keyword, dengan keyword merupakan banyaknya kata yang muncul dalam suatu kalimat. 3
Negative Keyword (f3)
Kalimat negatif merupakan kalimat yang jarang muncul dalam suatu dokumen (peringkasan). P(keywordi)=
3
dengan s(N) adalah jumlah kata dalam suatu kalimat yang mengandung keyword dan s(K) adalah jumlah kata dalam kalimat lain yang mengandung keyword, dengan keyword merupakan kata yang jarang muncul dalam suatu kalimat. 4
Kemiripan Antar-Kalimat (f4)
Kemiripan antar-kalimat merupakan kalimat yang memiliki kata yang sama dengan kata dalam kalimat lain. Skor fitur teks kemiripan antar-kalimat dapat dihitung menggunakan rumus berikut: Score(s)= dengan s(n) adalah keyword dalam s keyword dalam antar kalimat dan s(u) adalah keyword dalam s keyword dalam antar kalimat dengan s adalah kalimat dalam dokumen dan keyword merupakan banyaknya kata yang mirip dalam suatu kalimat. Berikut adalah contoh penerapan kemiripan antarkalimat: 1 2 3
Saya sedang mengerjakan skripsi Saya pergi dengan teman Saya sedang mengerjakan skripsi dengan teman Kalimat 2
Kalimat 1
pergi Sedang mengerjakan
Saya
skripsi
dengan teman
Kalimat3 Gambar 2 Ilustrasi kemiripan antar-kalimat. Berdasarkan ketiga kalimat tersebut, skor kalimat pertama adalah 4/7, skor kalimat kedua adalah 3/7, dan skor kalimat ketiga adalah 6/7. Kalimat pertama memiliki empat kata yang sama dengan kalimat ketiga, yaitu kata “saya, sedang, mengerjakan, skripsi”. Kalimat kedua memiliki tiga kata yang sama dengan kalimat ketiga, yaitu kata “saya, dengan, teman”. Kalimat ketiga memiliki enam kata yang sama dengan kalimat pertama dan kedua, yaitu kata “saya, sedang, mengerjakan, skripsi, dengan, teman”. Berdasarkan ketiga kalimat tersebut, maka perhitungan skor fitur
teks kemiripan antar-kalimat diilustrasikan pada Gambar 2. 5
Kalimat yang Dokumen (f5)
Menyerupai
Judul
Kalimat yang menyerupai judul kalimat adalah kata yang muncul dalam kalimat sama dengan kata yang ada dalam judul dokumen. Berikut ini merupakan contoh penerapan kemiripan kalimat yang menyerupai judul dokumen yaitu : Judul dokumen : Skripsi Saya 1 2 3
Saya sedang mengerjakan skripsi Saya pergi dengan teman Saya sedang mengerjakan skripsi dengan teman Berdasarkan contoh tersebut, skor kalimat pertama adalah skor kalimat kedua adalah , dan skor kalimat ketiga adalah 2/6. Kalimat pertama memiliki dua kata yang sama dengan judul dokumen yaitu “saya, skripsi”. Kalimat kedua memiliki satu kata yang sama dengan judul dokumen yaitu “saya”. Kalimat ketiga memiliki dua kata yang sama dengan judul dokumen yaitu “saya, skripsi”. Skor fitur teks kalimat yang menyerupai judul dokumen dapat dihitung menggunakan rumus berikut: Score(s)= dengan s(n) adalah keyword dalam s keyword dalam judul dan s(u) adalah keyword dalam s keyword dalam judul dengan asumsi s adalah kalimat dalam suatu dokumen. 6
Kalimat yang Mengandung Nama Entity (f6)
Kalimat yang mengandung nama entity merupakan sebuah kumpulan kata yang memiliki makna atau nama sebuah institusi, nama orang, dan nama pulau. Berikut adalah ilustrasi kalimat dalam dokumen yang mengandung nama entity: Jakarta, Kompas - Mantan anggota DPR Bambang Warih Kusumo mengatakan, penahanan mantan Mensesneg Akbar Tandjung tidak memenuhi fatsoen politik. Penahanan itu juga menyimpang dari UndangUndang (UU) Nomor 8/1987 tentang Protokol. Seharusnya, sebelum menahan Akbar Tandjung, Presiden Megawati Soekarnoputri meminta fatwa Mahkamah Agung (MA) atau mempersilakan DPR melepaskan Akbar Tandjung sebagai Ketua DPR. Berdasarkan contoh teks dokumen tersebut, kalimat yang mengandung nama
4
entity terdapat pada kalimat pertama dan kalimat ketiga sehingga skor untuk kalimat pertama adalah 2/14 dan skor kalimat ketiga adalah 3/14 . Perhitungan fitur teks kalimat yang mengandung nama entity adalah sebagai berikut: Score(s)= dengan s(E) adalah nama entity dalam kalimat dan s(K) adalah panjang kalimat. 7
Kalimat yang Mengandung Data Numerik (f7)
Pada pemeringkasan teks, data numerik dipertimbangkan karena kalimat yang berisi data numerik merupakan kalimat yang penting. Berikut ini merupakan ilustrasi kalimat dalam dokumen yang mengandung data numerik: Berapa sebenarnya APBD-nya? Tahun 2001 Rp 234,25 milyar, untuk tahun 2002 direncanakan naik Rp 6,3 milyar. Dari jumlah itu, alokasi dana kesehatan dan kesejahteraan sosial Rp 2,927 milyar, sebagian besar digunakan untuk pemberantasan penyakit menular malaria. Menurut catatan Jaringan Kajian dan Advokasi Kebijakan Publik, Yogyakarta Corruption Watch dan Dinamika Kulon Progo, jumlah keluarga miskin di kabupaten itu 40.904 keluarga, diasumsikan mereka terdiri dari lima jiwa, jumlah orang miskin 204.520 jiwa."Dengan anggaran kesehatan Rp 2,927 milyar, masing-masing keluarga miskin hanya akan menikmati Rp 47.000 per tahun, sangat timpang dibanding anggaran tunjangan kesehatan anggota DPRD Kulon Progo yang mencapai Rp 3,9 juta per tahun," katanya.
panjang dokumen. Perhitungan fitur teks panjang kalimat adalah sebagai berikut: Score (s)= dengan s(K) adalah banyaknya kata dalam suatu kalimat dan s(P) adalah banyaknya kata dalam dokumen. 9
Koneksi Antar-Kalimat (f9)
Koneksi antar-kalimat dihitung berdasarkan jumlah kata dalam suatu kalimat dengan kata yang sama disetiap kalimat dalam dokumen sehingga kata-kata tersebut terkoneksi atau terhubung satu sama lain. Berikut adalah contoh penerapan koneksi antar-kalimat: 1 2 3
Saya sedang mengerjakan skripsi Saya pergi dengan teman Saya sedang mengerjakan skripsi dengan teman Kalimat 2
Kalimat 1
pergi Sedang mengerjakan
Saya dengan teman
skripsi
Kalimat3 Gambar 3 Ilustrasi koneksi antar-kalimat.
Berdasarkan contoh teks dokumen tersebut, kalimat yang mengandung data numerik terdapat pada kalimat ketiga sehingga skor untuk kalimat ketiga adalah 2/25 sedangkan skor untuk kalimat yang lainnya adalah 0 karena tidak ada kalimat yang mengandung data numerik. Perhitungan fitur teks kalimat yang mengandung data numerik adalah sebagai berikut:
Berdasarkan Gambar 3, skor untuk kalimat pertama ialah 5. Kalimat pertama memiliki kata yang sama dengan kalimat kedua dan ketiga, yaitu “saya” sehingga jumlah skor adalah 2 dan memiliki kata yang sama dengan kalimat ketiga, yaitu “sedang”, “mengerjakan”, dan“skripsi” sehingga jumlah skor adalah 3. Penelitian ini menggunakan normalisasi agar skor nilai pada tiap kalimat dalam jangkauan 0 dan 1. Perhitungan fitur teks koneksi antarkalimat adalah sebagai berikut:
Score (s)=
Score(s)=#jumlah koneksi antar-kalimat
dengan s(A) adalah banyaknya kata numerik dan s(P) adalah banyaknya kata dalam kalimat.
10
8
Fitur ini berfungsi menjumlahkan kata dalam suatu kalimat dengan kata yang sama dari kalimat lain dalam suatu dokumen. Masih menggunakan ilustrasi pada Gambar 3. Berdasarkan ilustrasi tersebut, skor untuk
Panjang Kalimat (f8)
Panjang kalimat dihitung berdasarkan jumlah kata dalam kalimat dibagi dengan
Penjumlahan Kalimat (f10)
Bobot
Koneksi
Antar-
5
kalimat pertama adalah 4. Seluruh kata dalam kalimat pertama ada di kalimat lain dalam dokumen tersebut dan memiliki jumlah kata 4, yaitu “saya”, “sedang”, “mengerjakan”, dan “skripsi”. Perhitungan fitur teks penjumlahan bobot koneksi antar-kalimat adalah sebagai berikut: Score (s)=∑ koneksi antar-kalimat Pemodelan Regresi Logistik Biner Regresi matematika adalah model yang baik untuk memperkirakan teks bobot fitur. Dalam model ini fungsi matematika dapat berhubungan dari output ke input (Fattah dan Ren 2008). Regresi logistik biner merupakan model yang digunakan untuk menganalisis hubungan antara variabel independent dengan variabel dependent yang bersifat dua kategori atau lebih. Menurut Hosmer dan Lemeshow (2000), metode regresi logistik adalah suatu metode analisis statistika yang mendeskripsikan hubungan antara peubah respon yang memiliki dua kategori atau lebih dengan satu atau lebih peubah penjelas berskala kategori. Regresi logistik biner telah banyak digunakan secara luas sebagai salah satu alat analisis pemodelan ketika variabel responsnya bersifat biner. Istilah biner ini merujuk pada penggunaan dua buah bilangan 0 dan 1 untuk menggantikan kategori pada variabel respon. Pada penelitian ini, variabel respons atau variabel terikat (dependent variable) terdiri atas dua kategori, yaitu y=1 yang menyatakan “kalimat masuk ke dalam ringkasan” dan Y=0 yang menyatakan “kalimat tidak masuk dalam ringkasan” untuk tahap pelatihan. Pada penelitian ini diasumsikan tidak adanya asumsi-asumsi yang ada pada regresi. Menurut Hosmer dan Lemeshow (2000), model regresi logistik adalah: i
=
i
untuk mempermudah menaksir parameter regresi, maka (x) ditransformasikan dengan menggunakan transformasi logit berikut: g(x)=ln( )= + -
i
dengan nilai adalah nilai konstanta regresi, merupakan nilai dugaan koefisien regresi, dan xi merupakan nilai-nilai fitur. Persamaan tersebut bertujuan menduga parameter yang belum diketahui, yaitu parameter
Perbandingan Algoritme Genetika dan Regresi Logistik Biner Agoritme genetika atau genetic algorithm adalah algoritme pencarian heuristic yang didasarkan atas mekanisme evolusi biologis. Keberagaman pada evolusi biologis adalah variasi dari kromosom antar individu organisme. Variasi kromosom ini akan memengaruhi laju reproduksi dan tingkat kemampuan organisme untuk tetap hidup (Kusumadewi 2003). Algoritme genetika beroperasi pada populasi yang potensial memberikan solusi dengan prinsip survival of the fittest untuk menghasilkan baik dan semakin baik lagi sebagai perkiraan solusi. Diagram alir algoritme sederhana dapat dilihat pada Lampiran 1. Diagram alir ini terdiri atas beberapa bagian yaitu: populasi awal, evaluasi fitness, seleksi individu, pindah silang (crossover), mutasi (mutation), dan populasi baru. Teknik pencarian dilakukan sekaligus atas jumlah solusi yang mungkin yang dikenal dengan istilah populasi. Individu yang terdapat dalam satu populasi disebut dengan istilah kromosom. Populasi awal dibangun secara acak, sedangkan populasi berikutnya merupakan hasil evolusi kromosom-kromosom melalui iterasi yang disebut dengan istilah generasi. Menurut Kusumadewi (2003), pada setiap generasi, kromosom akan melalui proses evaluasi dengan menggunakan alat ukur yang disebut dengan fungsi fitness. Nilai fitnesss dari suatu kromosom akan menunjukkan kualitas kromosom dalam populasi tersebut. Generasi berikutnya dikenal dengan istilah anak (offspring) terbentuk dari gabungan dua kromosom generasi sekarang yang bertindak sebagai induk (parent) dengan menggunakan operator penyilangan (crossover). Suatu kromosom dapat juga dimodifikasi dengan menggunakan operator mutasi. Populasi generasi baru dibentuk dengan cara menyeleksi nilai fitness dari kromosom induk dan nilai fitness dari kromosom anak (offspring), serta menolak kromosom-kromosom lain sehingga ukuran populasi konstan. Menurut Kleinbaum dan Klein (2010), regresi logistik merupakan pendekatan model matematika yang dapat digunakan untuk menjelaskan hubungan antara beberapa variabel prediktor x terhadap variabel respons yang bersifat biner y Kurva logistik dapat dilihat pada Gambar 4. Kurva logistik digambarkan dalam bentuk S sigmoid dengan nilai z berkisar antara -∞
6
sampai dengan ∞ dan nilai f(z) bergerak dari 0 sampai 1. Nilai z merupakan jumlah dari persamaan linear atau z =β0 β1X1 β2X2 … βkXk. Kurva pada Gambar 4 menunjukkan jika nilai z semakin mendekati -∞ maka nilai f(z) akan bergerak mendekati nilai 0 dan jika nilai z mendekati ∞ maka nilai f z bergerak mendekati nilai 1.
Gambar 4 Kurva logistik (Kleinbaum & Klein, 2010). Tahap Pengujian Tahap pengujian menggunakan 50 dokumen berita berbahasa Indonesia (dokumen yang digunakan untuk pengujian berbeda dengan dokumen yang digunakan pada tahap pelatihan). Dokumen ini kemudian diringkas secara manual. Tujuannya ialah untuk membandingkan ringkasan manual dengan hasil ringkasan sistem.
Perangkat keras yang digunakan antara lain: Prosesor intel Dual Core T4300 2.1 GHz. RAM 1 GB. Harddisk 160 GB.
HASIL DAN PEMBAHASAN Data Korpus Penelitian ini menggunakan korpus berita nasional berbahasa Indonesia dari tanggal 11 Maret 2002 sampai 11 April 2002. Korpus berita tersebut berasal dari berita online harian Kompas yang didapat dari korpus penelitian Ridha (2002). Dokumen yang digunakan pada tahap pelatihan sebanyak 100 dokumen yang dengan batas pemampatan (compression rate) sebesar 30% dan berasal dari penelitian yang telah dilakukan Aristoteles (2011). Dokumen yang digunakan pada tahap pengujian sebanyak 50 dokumen dan ringkas secara manual yang berasal dari dokumen penelitian Aristoteles (2011). Format Dokumen Format dokumen pada penelitian ini menggunakan jenis dokumen yang bertipe teks dan memiliki format XML sederhana. Contoh format dokumen dapat dilihat pada Lampiran 2.
Pengujian Menggunakan Metode N-gram
Implementasi Sistem
Pengujian dilakukan dengan menggunakan metode N-gram. N-gram secara umum adalah,
Antarmuka sistem peringkasan dokumen dapat dilihat pada Lampiran 3. Terdapat dua bentuk ringkasan dalam suatu dokumen yaitu ekstraksi dan abstraksi. Ekstraksi adalah suatu ringkasan yang berasal dari kalimat – kalimat paling penting dari suatu dokumen. Abstraksi adalah mengambil intisari dari suatu teks dokumen yang berasal dari kalimat – kalimat baru (Jezek dan Steinberger 2008). Penelitian ini menggunakan teknik ekstraksi dalam membuat suatu ringkasan sehingga dibutuhkan pemotongan kalimat yang baik.
Dice = X merupakan banyaknya kalimat yang dihasilkan sistem, Y merupakan banyaknya kalimat yang diringkas secara manual. Pengujian yang dilakukan untuk membandingkan antara hasil ringkasan secara manual dengan hasil ringkasan sistem. Lingkungan Pengembangan Lingkungan pengembangan yang akan digunakan dalam penelitian ini terdiri atas perangkat lunak dan perangkat keras. Perangkat lunak yang digunakan antara lain: Sistem operasi Windows 7 Ultimate. Microsoft Office 2010. SPSS 17. PHP & Perl sebagai bahasa pemrograman. XAMPP version 1.7.2 sebagai web server. Notepad++.
Langkah-langkah dalam implementasi sistem ini adalah pembacaan dokumen, pemotongan kalimat, case folding, pemisahan kata dan filtering kata. Langkah awal adalah code yang berfungsi untuk pembacaan dokumen. Code untuk pembacaan dokumen dapat dilihat di Gambar 5. Langkah selanjutnya adalah pemisahan kalimat. Menurut Aristoteles (2011), Kalimat adalah gabungan dari dua buah kata atau lebih yang menghasilkan suatu arti dan pola intonasi akhir yang diakhiri dengan suatu tanda
7
berhenti. Berikut merupakan bentuk pemotongan kalimat dalam penelitian ini: Batas kalimat setelah tanda baca seperti . ? ! Batas kalimat sesudah tanda petik, bukan setelah titik Dapat mengenali singkatan seperti Hana, S. Kom. main:{ open (IN,">C:/xampp/htdocs/OS/tes.txt") || die "FILE tidak bisa dibuka....$!\n"; while(<$file>) { print IN $_; } Gambar 5 Contoh code pembacaan dokumen. Case folding berfungsi untuk menyeragamkan kata yang bermakna sama namun memiliki tulisan yang berbeda. Proses case folding adalah mengubah huruf besar menjadi kecil dalam suatu kalimat. Pemisahan kata berguna untuk memotong kalimat menjadi kata-kata dengan ciri antar kata adalah whitespace (spasi, tab, dan newline). Contoh Case folding dapat dilihat pada Tabel 1. Filtering kata adalah memisahkan katakata yang dibutuhkan dengan kata-kata yang tidak bermakna (stopword) sehingga dapat mengurangi kompleksitas perhitungan dari fitur teks. Contoh kata stopword adalah yang, di, pada, dengan, dan lain-lain. Penelitian ini menggunakan bahasa pemrograman Perl dan format data yang digunakan berjenis teks XML. Pemodelan Regresi Logistik Biner Penelitian ini menggunakan data hasil dari perhitungan penelitian Aristoteles (2011) dengan CR 30% karena memiliki F-measure paling besar dibandingkan dengan CR 10% dan 20% yaitu sebesar 4.81%. Data yang didapat dari penelitian Aristoteles (2011) berupa data .txt. Data tersebut dikonversi ke Microsoft Excel agar mudah untuk mendapatkan persamaan regresi logistik biner. Contoh data yang digunakan dalam penelitian ini dapat dilihat pada Lampiran 4. Diasumsikan dalam satu tabel tersebut merupakan jumlah seluruh kalimat dalam korpus, dengan S adalah kalimat, x adalah pembobotan fitur, dan y merupakan variabel respons (dependent) yang bernilai 0 dan 1.
Tabel 1 Contoh paragraf, pemisahan kalimat dan case folding Jakarta, Kompas Kepala Pusat Penerangan (Puspen) TNI Mayjen Sjafrie Sjamsoeddin hingga saat ini belum mendapat informasi dan otoritas untuk menyampaikan mengenai pergantian pimpinan atas TNI. Ia mengaku, justru mendapat informasi mengenai perpanjangan masa dinas Jenderal Endriartono Sutarto dari berita media massa. Pemotongan Kalimat Jakarta, Kompas Kepala Pusat Penerangan (Puspen) TNI Mayjen Sjafrie Sjamsoeddin hingga saat ini belum mendapat informasi dan otoritas untuk menyampaikan mengenai pergantian pimpinan atas TNI. Ia mengaku, justru mendapat informasi mengenai perpanjangan masa dinas Jenderal Endriartono Sutarto dari berita media massa. Case Folding jakarta, kompas kepala pusat penerangan (puspen) tni mayjen sjafrie sjamsoeddin hingga saat ini belum mendapat informasi dan otoritas untuk menyampaikan mengenai pergantian pimpinan atas tni. ia mengaku, justru mendapat informasi mengenai perpanjangan masa dinas jenderal endriartono sutarto dari berita media massa. Penelitian ini menggunakan variabel respons yang terdiri atas dua kategori, yaitu y=1 yang menyatakan “kalimat masuk ke dalam ringkasan” dan y=0 yang menyatakan “kalimat tidak masuk dalam ringkasan”. Nilai y=1 didapat dari peringkasan secara manual yang telah dilakukan pada penelitian Aristoteles (2011). Nilai dari variabel dependent ini untuk mengkategorikan suatu kalimat masuk atau tidaknya dalam suatu ringkasan dalam tahap pelatihan. Peringkasan manual ini dapat menentukan kalimat mana yang masuk dalam peringkasan dan kalimat mana yang tidak masuk dalam ringkasan untuk dilakukan perbandingan pada
8
tahap pengujian dengan hasil ringkasan sistem. Dengan menggunakan perangkat lunak SPSS 17, data yang telah dikonversi ke Microsoft Excel disalin ke SPSS 17 untuk mendapatkan persamaan regresi logistik biner. Dalam proses pemodelan regresi logistik, data yang telah dikonversi ke Microsoft Excel disalin dan diproses dengan menggunakan SPSS 17 untuk menghasilkan persamaan regresi logistik biner. Hasil output SPSS 17 pemodelan regresi logistik dapat dilihat dalam Lampiran 5. Persamaan regresi logistik biner yang telah dihasilkan oleh SPSS dimasukkan ke dalam sistem. Pemodelan regresi logistik menghasilkan persamaan sebagai berikut: ln(
-
)= -2.843 – 0.638x1 + 2.627x2 + 0.258x4 + 1.713x5 - 0.160x6 - 0.08x7 0.462x8 + 1.831x9 - 0.213x10
Dimisalkan dokumen berita yang akan diringkas adalah dokumen yang berada di dalam korpus penelitian didalam direktori “korpus_bener” dengan nama file 34.txt, dokumen dapat dilihat pada Lampiran 6. Hasil ringkasan dari dokumen 34.txt dapat dilihat pada Lampiran 7. Hasil ringkasan pada penelitian ini menggunakan menggunakan compression rate sebesar 30%. Artinya hasil ringkasan sebuah dokumen terdiri atas 30% isi dokumen tersebut. Pengujian Menggunakan N-gram Tahap pengujian menggunakan 50 dokumen berita berbahasa Indonesia (dokumen yang digunakan untuk pengujian berbeda dengan dokumen yang digunakan pada tahap pelatihan). Dalam tahap pengujian ini ringkasan manual dibutuhkan sebagai perbandingan antara hasil ringkasan sistem dengan hasil ringkasan yang telah dilakukan oleh penelitian Aristoteles (2011). Pengujian dalam penelitian ini menggunakan metode N-gram. Metode N-gram menilai ketepatan dari peringkasan dokumen dengan cara membandingkan apakah kalimat hasil peringkasan sistem yang telah dihasilkan sama dengan peringkasan manual. N-gram secara umum adalah: Dice = x merupakan banyaknya kalimat yang dihasilkan sistem dan y merupakan banyaknya kalimat yang diringkas secara manual.
Pemodelan regresi logistik biner menghasilkan akurasi sebesar 42.84% dari perhitungan menggunakan metode N-gram. Dalam penelitian ini terdapat beberapa faktor yang memengaruhi besar kecilnya akurasi yaitu ringkasan manual yang subjektif, jumlah dokumen yang sedikit, dan jenis dokumen yang digunakan. Perhitungan hasil pengujian antara hasil peringkasan manual dan hasil peringkasan sistem menggunakan n-gram dapat dilihat pada Lampiran 8. Hasil Perbandingan dengan Algoritme Genetika Hasil penelitian Aristoteles (2011) yang dapat dilihat pada Tabel 2 Hasil akurasi pada penelitian Aristoteles (2011) menggunakan empat fitur teks pada tahap pengujian meningkat 5.28% dibandingkan dengan menggunakan dua fitur teks. Namun, perbedaan tingkat akurasi dengan menggunakan enam fitur teks, delapan fitur teks, dan sebelas fitur teks adalah sebesar 1%. Oleh karena itu, penggunaan empat fitur teks (f5, f4, f2, f11) pada tahap pengujian dapat merepresentasikan hasil akurasi dari sebelas fitur teks. Nilai akurasi menggunakan algoritme genetika adalah 45.91%. Hasil akurasi menggunakan Tabel 2 algoritme genetika No.
Bobot
Akurasi
1
w5, w4
41.16%
2
w5, w4, w2, w1
46.44%
3
w5, w4, w2, w11, w7, w6
47.12%
4
w5, w4, w2, w11, w7, w6, w10, w9
47.20%
5
w5, w4, w2, w11, w7, w6, w10, w9, w1, w8, w3 Rata-rata
47.63%
45.91%
Hasil akurasi pengujian pemodelan regresi logistik biner menggunakan metode N-gram ialah sebesar 42.84%. Hasil dari penelitian peringkasan menggunakan metode regresi logistik tidak menghasilkan akurasi yang lebih baik dari algoritme genetika. Hal ini dikarenakan model yang telah dihasilkan tidak sesuai dengan analisis regresi logistik. Analisis regresi logistik tersebut terdiri atas uji kelayakan model dan uji parameter model. Uji kelayakan model digunakan untuk mengetahui nilai perbedaan antara data dengan nilai yang dihasilkan sistem. Hasil analisis uji kelayakan
9
model dapat dilihat dalam Lampiran 5 pada tabel Hosmer dan Lemeshow (2000) terdapat nilai sig 0,006. Nilai sig 0,006 menunjukkan bahwa hasil prediksi model tidak sesuai dengan hasil observasi. Uji parameter model digunakan untuk mengetahui manakah variabel independent yang memiliki pengaruh nyata terhadap variabel dependent. Hasil analisis uji parameter model dapat dilihat pada Lampiran 5 bagian tabel variables in the equation. Dapat dilihat bahwa pada kolom sig (significant). terdapat nilai- nilai sig di atas 0,05. Artinya variabel independent tidak memiliki pengaruh secara signifikan terhadap variabel independent. Persamaan yang telah didapat dalam penelitian ini tidak sesuai dengan analisis regresi logistik. Namun, parameter yang tidak signifikan tersebut tetap dimasukkan dalam persamaan untuk mengetahui hubungan antarvariabel independent terhadap variabel dependent yang bersifat biner. Persamaan regresi yang telah didapat dari penelitian ini digunakan untuk melihat kinerja dari metode regresi logistik.
SIMPULAN DAN SARAN Simpulan Hasil penelitian yang telah dilakukan dapat disimpulkan beberapa hal berikut: regresi logistik biner dapat digunakan untuk peringkasan dokumen selama model yang dihasilkan sesuai dengan analisis regresi logistik biner dan model yang dihasilkan sesuai dengan data. penelitian ini menghasilkan akurasi sebesar 42.84%. penelitian ini tidak menghasilkan akurasi yang lebih baik dari penelitian sebelumnya dengan menggunakan algoritme genetika, yaitu sebesar 45.91%.
Saran Terdapat saran setelah dilakukan penelitian peringkasan teks bahasa Indonesia menggunaakan regresi logistik biner yaitu, dalam membuat peringkasan teks menggunakan metode yang lain yang lebih sederhana dan menghasilkan akurasi lebih besar.
DAFTAR PUSTAKA Aristoteles. 2011. Pembobotan fitur pada peringkasan teks bahasa Indonesia menggunakan algoritme genetika [tesis]. Bogor: sekolah Pascasarjana, Institut Pertanian Bogor. Fattah MA, Ren F. 2008. Automatic text summarization. Di dalam: Proceeding of World Academic of Science, Engineering and Technology; 18-24 Feb 2007. hlm 192-195. Hosmer D, Lemeshow S. 2000. Applied Logistic Regression. Ed ke-2. Columbus: A Wiley-Interscience Publ. Jezek K, Steinberger J. 2008. Automatic text summarization (The state of the art 2007 and new challenges). Di dalam: Znalosti 2008; Bratislave, 13-15 Feb 2008. hlm 112. Kleinbaum D, Klein M. 2010. Logistic Regressiom, Ed ke-3. New York: Springer. Kusumadewi Sri. 2003. Artificial Intelligence. Yogyakarta: Graha Ilmu. Manning CD, Raghavan P, Schutze H. 2008. Introduction to Information Retrieval. Cambridge: Cambridge University Press. Ridha A. 2002. Pengindeksan otomatis dengan istilah tunggal untuk dokumen berbahasa Indonesia [skripsi]. Bogor: Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor.
LAMPIRAN
11
Lampiran 1 Diagram alir algoritme genetika sederhana (Kusumadewi 2003).
Bangkitkan populasi awal
Evaluasi fungsi tujuan
Apakah kriteria optimasi
Individuindividu terbaik
Mulai Bangkitkan populasi awal
Hasil Seleksi
Crossover
Mutasi
12
Lampiran 2 Format dokumen pada tahap pelatihan dan pengujian
13
Lampiran 3 Antarmuka sistem peringkasan teks
14
Lampiran 4 Contoh nilai nilai fitur untuk setiap kalimat dalam satu dokumen
s\x s1 s2 s3 s4 s5 s6 s7 s8 s9 s10 s11
x1 1.000 0.750 0.500 0.250 0.000 0.000 0.000 0.000 0.000 0.000 0.000
x2 0.797 0.147 0.748 0.211 0.704 0.126 0.768 0.042 0.169 0.136 0.129
x3 0.203 0.853 0.252 0.789 0.296 0.874 0.232 0.958 0.831 0.864 0.871
x4 0.135 0.203 0.203 0.257 0.108 0.027 0.176 0.041 0.338 0.054 0.216
x5 0.000 0.014 0.014 0.027 0.014 0.000 0.000 0.000 0.014 0.000 0.000
x6 0.087 0.000 0.081 0.156 0.188 0.100 0.095 0.000 0.000 0.000 0.028
x7 0.043 0.042 0.081 0.031 0.000 0.000 0.000 0.111 0.070 0.000 0.028
x8 0.084 0.088 0.135 0.117 0.058 0.036 0.077 0.033 0.157 0.036 0.131
x9 0.000 0.417 0.250 0.000 0.000 0.000 0.583 0.000 0.667 0.000 0.333
x10 0.000 0.680 0.371 0.000 0.000 0.000 1.187 0.000 1.876 0.000 0.629
Y 1.000 1.000 1.000 1.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000
s12
0.000
0.034
0.966
0.014
0.000
0.077
0.000
0.047
0.000
0.000 0.000
15
Lampiran 5 Tabel model persamaan regresi logistik biner Hosmer and Lemeshow Test
Chi-square 21.499
df 8
Sig. 0.006
Variables in the equation
x1
B -0.638
S.E. 0.247
Wald 6.698
x2
2.627
0.226
x4
0.258
x5
df 1
Sig. 0.010
Exp(B) 0.528
135.538
1
0.000
13.833
1.274
0.041
1
0.839
1.295
1.713
4.521
0.144
1
0.705
1.295
x6
-0.160
0.968
0.027
1
0.869
0.852
x7
-0.080
1.560
0.003
1
0.959
0.923
x8
-0.462
2.714
0.029
1
0.865
0.630
x9
1.831
2.007
0.832
1
0.362
6.239
x10
-0.213
0.407
0.273
1
0.601
0.808
Constant
-2.843
0.207
188.089
1
0
0.058
16
Lampiran 6 Contoh dokumen berita 34.txt
17
Lampiran 7 Antarmuka hasil sistem dokumen berita 34.txt
18
Lampiran 8 Hasil pengujian antara hasil peringkasan manual dan hasil peringkasan sistem menggunakan N-gram Dok. Ke-
Sistem
Manual
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
5 7 6 4 3 16 7 2 5 3 3 5 4 3 7 6 7 6 5 5 13 3 4 7 5
9 6 5 6 4 18 9 2 5 5 3 6 6 4 11 8 8 9 6 6 15 4 10 7 8
S M
Hasil N-gram
3 0 1 0 2 2 2 0 1 1 1 1 1 1 2 2 0 2 1 2 1 1 2 1 1
0.428571429 0.000000000 0.181818182 0.000000000 0.571428571 0.117647059 0.250000000 0.000000000 0.200000000 0.250000000 0.333333333 0.181818182 0.200000000 0.285714286 0.222222222 0.285714286 0.000000000 0.266666667 0.181818182 0.363636364 0.071428571 0.285714286 0.285714286 0.142857143 0.153846154
Dok. Ke-
Sistem
Manual
26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
13 6 11 13 19 5 3 4 2 8 14 7 5 4 8 5 13 8 15 5 4 10 5 2 8
13 5 7 9 20 5 5 6 4 11 14 8 7 5 9 5 12 10 17 5 7 6 6 4 8
S M
Hasil N-gram
1 2 3 2 7 1 0 1 0 2 4 2 2 2 4 0 3 2 2 2 2 0 0 0 3
0.076923077 0.363636364 0.333333333 0.181818182 0.358974359 0.200000000 0.000000000 0.200000000 0.000000000 0.210526316 0.285714286 0.266666667 0.333333333 0.444444444 0.470588235 0.000000000 0.240000000 0.222222222 0.125000000 0.400000000 0.363636364 0.000000000 0.000000000 0.000000000 0.375000000
hasil n-gram
0.428470655
