PEMBOBOTAN FITUR PADA PERINGKASAN TEKS BAHASA INDONESIA MENGGUNAKAN ALGORITME GENETIKA
ARISTOTELES
SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2011
PERNYATAAN MENGENAI TESIS DAN SUMBER INFORMASI
Dengan ini saya menyatakan bahwa tesis Pembobotan Fitur pada Peringkasan Teks Bahasa Indonesia Menggunakan Algoritme Genetika adalah karya saya dengan arahan dari komisi pembimbing dan belum diajukan dalam bentuk apa pun kepada perguruan tinggi mana pun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir tesis ini.
Bogor, Januari 2011
Aristoteles NRP G651080031
ABSTRACT
ARISTOTELES. Text Feature Weighting for Summarization of Document Bahasa Indonesia Using Genetic Algorithm. Under direction of Yeni Herdiyeni (chair), Ahmad Ridha (member). This thesis aims to perform text feature weighting for summarization of document bahasa Indonesia using genetic algorithm. There are eleven 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), summation of similarities for each node (f10), and latent semantic feature (f11). We investigate the effect of the first ten sentence features on the summarization task. Then, we use latent semantic feature to increase the accuracy. All feature score functions are used to train a genetic algorithm model to obtain a suitable combination of feature weights. Evaluation of text summarization uses F-measure. The F-measure directly related to the compression rate. The results showed that adding f11 increases the F-measure by 3.26% and 1.55% for compression ratio of 10% and 30%, respectively. On the other hand, it decreases the F-measure by 0.58% for compression ratio of 20%. Analysis of text feature weight showed that only using f2, f4, f5, and f11 can deliver a similar performance using all eleven features. Keywords: text summarization, genetic algorithm, latent semantic feature
RINGKASAN ARISTOTELES. Pembobotan Fitur Teks pada Peringkasan Teks Bahasa Indonesia Menggunakan Algoritme Genetika. Dibimbing oleh Yeni Herdiyeni, dan Ahmad Ridha. Memahami isi dokumen melalui ringkasan teks dokumen memerlukan waktu yang lebih singkat dibandingkan membaca seluruh isi dokumen, sehingga ringkasan teks menjadi sangat penting. Namun demikian, membuat ringkasan dokumen memerlukan waktu dan biaya yang banyak bila dokumen yang diringkas berjumlah banyak dan isi dokumen yang panjang. Oleh karena itu, ringkasan teks dokumen secara otomatis diperlukan untuk mengatasi masalah waktu baca dan biaya. Penelitian ini bertujuan untuk melakukan optimasi peringkasan teks dengan menggunakan algoritme genetika dan menganalisa penambahan ekstraksi fitur teks kalimat semantik menggunakan teknik singular value decomposition. Penelitian ini menggunakan beberapa fitur teks dalam melakukan peringkasan teks dokumen seperti posisi kalimat, positive keyword, negative keyword, kemiripan antar-kalimat, kalimat yang menyerupai judul, kalimat yang mengandung nama entiti, kalimat yang mengandung data numerik, koneksi antarkalimat, penjumlahan bobot koneksi antar-kalimat, dan kalimat semantik. Fitur teks kalimat semantik menggunakan teknik singular value decomposition (SVD). Penentuan bobot dari tiap fitur teks menggunakan teknik algoritme genetika. Penelitian ini terdiri dari tiga tahap yaitu: tahap pengumpulan dokumen, tahap pelatihan, dan tahap pengujian. Pada tahap pengumupulan dokumen, dokumen yang digunakan berjenis teks dengan format xml berjumlah 150 dokumen, 100 dokumen pelatihan dan 50 dokumen pengujian. Pada tahap pelatihan, terbagi atas tiga bagian utama yaitu: ringkasan dokumen, ektraksi fitur teks, dan pemodelan algoritme genetika. Ringkasan teks dokumen dilakukan oleh dua orang, dengan masing-masing meringkas 50 dokumen. Dokumen diringkas dengan batas pemampatan (compression rate) sebesar 30%, 20%, dan 10%. Tujuan dari ringkasan manual ini adalah untuk melakukan perbandingan dengan hasil ringkasan oleh sistem. Ekstraksi fitur teks adalah tahapan yang digunakan untuk mendapatkan ekstraksi skor fitur dari teks dokumen. Ekstraksi fitur teks terdiri dari sebelas fitur teks. Pemodelan algoritme genetika diterapkan pada tahap pelatihan bertujuan agar mendapatkan model atau bobot yang optimal sehingga model ini dapat digunakan pada tahap pengujian. Pemodelan algoritme genetika dimulai dari memberi nilai awal populasi secara acak. Tiap populasi berisi 1000 kromosom. Sebuah kromosom di representasikan sebagai kombinasi seluruh fitur bobot dalam bentuk . Tiap kromosom dievaluasi oleh oleh rata-rata F-measure atau fungsi evaluasi. Fungsi evaluasi berfungsi mengevaluasi tingkat akurasi antara ringkasan oleh sistem dan ringkasan manual. Setiap kromosom, diterapkan pada tiap kalimat pada dokumen pelatihan. Fungsi evaluasi dilakukan sebanyak 100 dokumen. Skor kalimat dilakukan pada tiap dokumen pelatihan dan pengujian diurutkan secara descending. Ringkasan dari sistem berdasarkan pada proses pemampatan atau compression rate (CR) sebesar 10%, 20%, dan 30%, artinya bahwa banyaknya kalimat pada tiap dokumen dikalikan dengan CR 10%, CR 20%, dan CR 30%. Hasil ringkasan dari sistem dievaluasi dengan ringkasan manual sehingga
menghasilkan akurasi F-measure dari tiap dokumen. Rata-rata F-measure adalah nilai akurasi dari seluruh dokumen pelatihan. Setiap satu generasi, diambil empat kromosom terbaik dan dimasukan kembali ke dalam populasi baru. Tahap pengujian menggunakan 50 dokumen (dokumen yang digunakan pada tahap pengujian berbeda dengan dokumen yang digunakan pada tahap pelatihan). Proses selanjutnya adalah melakukan ekstraksi fitur teks. Proses ini sama dengan yang dilakukan ekstraksi fitur teks pada tahap pelatihan. Peringkasan teks secara otomatis didasari oleh model yang telah diciptakan di tahap pelatihan. Kombinasi bobot diterapkan pada fungsi skor untuk setiap kalimat. Akurasi didasari dari hasil ringkasan oleh sistem dengan ringkasan manual. Hasil percobaan menunjukkan bahwa nilai F-measure tidak mengalami kenaikan secara signifikan. Penggunaan sepuluh fitur teks dan sebelas fitur teks pada CR 10% hanya mengalami kenaikan F-measure sebesar 3.26%, pada CR 20% mengalami penurunan sebesar 0.58%, dan CR 30% mengalami peningkatan sebesar 1.55%. Namun, rata-rata F-measure mengalami kenaikan secara linier dari CR 10% ke CR 20% sebesar 6.28%, dari CR 20% ke CR 30% sebesar 6.17%. Hasil akurasi terbaik terdapat pada compression rate 30%. Semakin besar compression rate maka nilai kemiripan hasil ringkasan sistem dengan hasil ringkasan manual semakin besar. Berdasarkan Analisis fitur teks diperoleh nilai bobot tertinggi terdapat pada fitur teks “kalimat yang menyerupai judul dokumen” dan nilai bobot terendah terdapat pada fitur teks “negative keyword”. Fitur teks “kalimat semantik” termasuk empat terbesar dalam rangking bobot pada tiap percobaan di CR10%, CR 20%, dan CR 30% sehingga fitur teks “kalimat semantik” memiliki tingkat kepentingan yang tinggi dalam peringkasan teks. Analisis kinerja fitur teks terhadap akurasi menunjukkan bahwa penggunaan fitur teks positive keyword, kemiripan antar-kalimat, kalimat yang menyerupai judul, dan kalimat semantik (f2, f4, f5, f11) pada tahap pengujian dapat merepresentasikan hasil akurasi dari sebelas fitur teks. Oleh karena itu, fitur teks (f2, f4, f5, f11) merupakan bagian yang penting dalam peringkasan teks.
Kata kunci: algoritme genetika, singular value decomposition, fitur teks, compression rate
© Hak Cipta milik IPB, tahun 2011 Hak Cipta dilindungi Undang-Undang Dilarang mengutip sebagian atau seluruh karya tulis ini tanpa mencantumkan atau menyebutkan sumbernya. Pengutipan hanya untuk kepentingan pendidikan, penelitian, penulisan karya ilmiah, penyusunan laporan, penulisan kritik, atau tinjauan suatu masalah; dan pengutipan tersebut tidak merugikan kepentingan yang wajar IPB Dilarang mengumumkan dan memperbanyak sebagian atau seluruh Karya tulis dalam bentuk apa pun tanpa izin IPB
PEMBOBOTAN FITUR PADA PERINGKASAN TEKS BAHASA INDONESIA MENGGUNAKAN ALGORITME GENETIKA
ARISTOTELES
Tesis Sebagai salah satu syarat untuk memperoleh gelar Magister Komputer pada Program Studi Magister Ilmu Komputer
SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2011
Penguji Luar Komisi pada Ujian Tesis : Ir. Julio Adisantoso, M.Kom
Judul Tesis Nama NRP
: Pembobotan Fitur pada Peringkasan Teks Bahasa Indonesia Menggunakan Algoritme Genetika : Aristoteles : G651080031
Disetujui, Komisi Pembimbing
Ahmad Ridha, S.Kom., M.S. Anggota
Dr. Yeni Herdiyeni, S.Si., M.Kom Ketua
Diketahui,
Ketua Program Studi Ilmu Komputer
Dekan Sekolah Pascasarjana
Dr. Ir. Agus Buono, M.Si., M.Kom.
Prof. Dr. Ir. Khairil A. Notodiputro, M.S
Tanggal Ujian : 3 Desember 2010
Tanggal Lulus:
PRAKATA
Puji syukur dipanjatkan ke hadirat Allah SWT sehingga penulis bisa menyelesaikan tesis ini. Shalawat serta salam semoga selalu tercurah kepada Nabi Muhammad SAW hingga akhir zaman. Amin. Tema yang dipilih dalam penelitian ini adalah tentang peringkasan teks sistem dengan judul Pembobotan Fitur pada Peringkasan Teks Bahasa Indonesia Menggunakan Algoritme Genetika. Penulis mengucapkan terimakasih kepada: 1. Ibu Dr. Yeni Herdiyeni, S.Si, M.Kom sebagai ketua komisi pembimbing yang telah memberikan arahan dalam penelitian dan penulisan tesis. 2. Bapak Ahmad Ridha, S.Kom, M.S sebagai anggota komisi pembimbing yang telah memberikan arahan dalam penelitian dan penulisan tesis. 3. Bapak Ir. Julio Adisantoso, M.Kom sebagai dosen penguji yang telah meluangkan waktu untuk menguji dan memberikan saran-saran dalam penulisan tesis. 4. Teman-teman Angkatan X (Pak Aziz, Rosi, Pak Toto, Defiana, Pak Altien), Wisma Lampung-Aceh (Pak Rico, Yai Agus, Pak Jekvy, Mucle, Pak Cipto), angkatan XI (Deba, Kamal, Bu Dewi, Bu Zuriati), XII yang telah memberikan saran-saran yang berguna untuk pelaksaan penelitian. Penulis mempersembahkan karya ilmiah ini untuk keluarga besar di Lampung, adinda tersayang “Nina” yang telah memberikan dorongan moril. Banyak kekurangan dalam tesis ini, untuk itu penulis mengharapkan kritik atau saran untuk memperbaiki tesis ini. Semoga karya ilmiah ini bermanfaat.
Bogor, Januari 2011
Aristoteles
RIWAYAT HIDUP
Penulis dilahirkan di Telukbetung pada tanggal 21 Mei 1981 dari ayah M. Yamin Nurali (alm) dan ibu Hasnil Wati. Penulis merupakan putra ketiga dari empat bersaudara. Tahun 1999 penulis lulus dari SMA Negeri 9 Bandung. Tahun 2002 lulus D3 Teknik Informatika Universitas Padjadjaran, dan melanjutkan S1 Ilmu Komputer Universitas Padjadjaran lulus tahun 2004. Tahun 2008 lulus seleksi masuk Program Pascasarjana Ilmu Komputer IPB Bogor. Beasiswa pendidikan pascasarjana diperoleh dari Direktorat Pendidikan Tinggi, Departemen Pendidikan Nasional. Pada tahun 2003-2005, penulis bekerja sebagai programmer di PT. Revtech Bandung. Tahun 2006 penulis bekerja sebagai dosen di Universitas Lampung, Program Studi Ilmu Komputer, Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam.
i
DAFTAR ISI Halaman DAFTAR ISI ............................................................................................................ i DAFTAR TABEL .................................................................................................. iv DAFTAR GAMBAR .............................................................................................. v DAFTAR LAMPIRAN .......................................................................................... vi 1 PENDAHULUAN ............................................................................................... 1 1.1 Latar Belakang ............................................................................................. 1 1.2 Tujuan .......................................................................................................... 2 1.3 Manfaat ........................................................................................................ 3 1.4 Ruang Lingkup ............................................................................................ 3 2 TINJAUAN PUSTAKA ...................................................................................... 4 2.1 Peringkasan Teks ......................................................................................... 4 2.2 Paragraf ........................................................................................................ 4 2.3 Ekstraksi fitur teks ....................................................................................... 4 2.3.1 Posisi Kalimat (f1) ........................................................................... 4 2.3.2 Positive Keyword (f2) ...................................................................... 5 2.3.3 Negative Keyword (f3) .................................................................... 6 2.3.4 Kemiripan Antar-Kalimat (f4) ......................................................... 7 2.3.5 Kalimat yang Menyerupai Judul Dokumen (f5) .............................. 8 2.3.6 Kalimat yang Mengandung Nama Entiti (f6) .................................. 9 2.3.7 Kalimat yang Mengandung Data Numerik (f7) ............................... 9 2.3.8 Panjang Kalimat (f8) ...................................................................... 10 2.3.9 Koneksi Antar-Kalimat (f9) ........................................................... 11 2.3.10 Penjumlahan Bobot Koneksi Antar-Kalimat (f10) ........................ 12
ii
2.3.11 Kalimat Semantik (f11) ................................................................. 12 2.4 Algoritme Genetika ................................................................................... 13 2.4.1 Siklus Algoritme Genetika............................................................. 13 2.4.1.1 Populasi ........................................................................... 14 2.4.1.2 Fungsi Evaluasi................................................................ 15 2.4.1.3 Seleksi .............................................................................. 15 2.4.1.4 Pindah Silang ................................................................... 16 2.4.1.5 Mutasi .............................................................................. 17 3 METODE PENELITIAN .................................................................................. 19 3.1 Prosedur Penelitian .................................................................................... 19 3.1.1 Pengumpulan Dokumen Teks ........................................................ 19 3.1.2 Tahap Pelatihan.............................................................................. 20 3.1.2.1 Ringkasan Dokumen Secara Manual .................................. 20 3.1.2.2 Ekstraksi Fitur Teks .............................................................. 20 3.1.2.3 Pemodelan Algoritme Genetika........................................... 20 3.1.3 Tahap Pengujian ............................................................................ 22 3.2 Lingkungan Pengembangan ...................................................................... 23 3.3 Waktu dan Tempat Penelitian.................................................................... 23 4 HASIL DAN PEMBAHASAN ......................................................................... 24 4.1 Data Korpus ............................................................................................... 24 4.2 Format Dokumen ....................................................................................... 24 4.3 Pemotongan Kalimat ................................................................................. 25 4.4 Metode Evaluasi ........................................................................................ 25 4.5 Kalimat Semantik ...................................................................................... 26 4.6 Pemodelan Algoritme Genetika................................................................. 28 4.7 Hasil Pengujian Model Algoritme Genetika ............................................. 32
iii
4.7.1 Hasil F-measure Tahap Pengujian ................................................. 32 4.7.2 Analisa Model Kromosom ............................................................. 33 4.8 Waktu Komputasi ...................................................................................... 37 5 KESIMPULAN DAN SARAN ......................................................................... 39 5.1 Kesimpulan ................................................................................................ 39 5.2 Saran .......................................................................................................... 39 DAFTAR PUSTAKA............................................................................................ 41 LAMPIRAN .......................................................................................................... 43
iv
DAFTAR TABEL Halaman 1
Term frequency dan inverse sentences frequency ........................................ 27
2
Pembobotan term pada kalimat .................................................................... 28
3
Vektor kalimat ............................................................................................. 28
4
Data matriks kemiripan ................................................................................ 28
5
Contoh model kromosom terbaik untuk CR 30% ........................................ 32
6
Ilustrasi nilai bobot pada model kromosom CR 30% .................................. 34
7
Perangkingan bobot ..................................................................................... 36
v
DAFTAR GAMBAR Halaman 1
Ilustrasi kemiripan antar-kalimat. .................................................................. 8
2
Ilustrasi kalimat yang menyerupai judul. ....................................................... 8
3
Ilustrasi koneksi antar-kalimat. .................................................................... 11
4
Siklus algoritma genetika oleh Goldberg (1989). ........................................ 14
5
Ilustrasi penyelesaian masalah dalam algoritme genetika. .......................... 15
6
Diagram alir proses pindah silang. ............................................................... 16
7
Pindah silang satu titik. ................................................................................ 17
8
Diagram alir mutasi. ..................................................................................... 18
9
Proses dan hasil mutasi. ............................................................................... 18
10
Peringkasan teks secara otomatis. ................................................................ 19
11
Proses algoritme genetika. ........................................................................... 21
12
Representasi kromosom pada pembobotan ekstraksi fitur teks. .................. 21
13
Format dokumen pada tahap pelatihan dan pengujian. ................................ 24
14
Representasi kromosom. .............................................................................. 29
15
Diagram alir proses pindah silang antar dua induk. ..................................... 31
16
Diagram alir proses mutasi. ......................................................................... 31
17
Perbandingan pengujian F-measure ’sepuluh fitur teks’ () dan ’sebelas fitur teks’ (■) pada CR 10%, CR 20%, dan CR 30%. ............................... 33
18
Kinerja fitur teks terhadap akurasi. .............................................................. 37
19
Jumlah fitur teks terhadap waktu akurasi ..................................................... 38
vi
DAFTAR LAMPIRAN Halaman 1
Model kromosom CR 30% .......................................................................... 44
1
1 PENDAHULUAN
1.1 Latar Belakang Memahami isi dokumen melalui ringkasan teks dokumen memerlukan waktu yang lebih singkat dibandingkan membaca seluruh isi dokumen, sehingga ringkasan teks menjadi sangat penting. Namun demikian, membuat ringkasan dokumen memerlukan waktu dan biaya yang banyak bila dokumen yang diringkas berjumlah banyak dan isi dokumen yang panjang. Oleh karena itu, ringkasan teks dokumen secara otomatis diperlukan untuk mengatasi masalah waktu baca dan biaya. Peringkasan teks adalah proses yang menghasilkan dokumen yang lebih kecil 50% dari ukuran dokumen (Radev et al. 2002) dengan tujuan memperoleh informasi dalam waktu singkat (Blake et. al 2001). Menurut (Edmundson 1969; Hovy & Lin 1997) untuk melakukan peringkasan teks, bagian-bagian tertentu seperti judul bab, teks tebal, dan awal kalimat merupakan bagian yang penting. Selain itu, menurut Edmundson (1969) frasa seperti “pada ringkasan ini”, “pada kesimpulan ini”, “tulisan ini menjelaskan” merupakan frasa yang berguna untuk mengidentifikasi bagian yang penting dalam teks. Kriteria peringkasan teks terbagi dua bagian yaitu
peringkasan teks
berdasarkan eksktraksi dan abstraksi (Jezek & Steinberger 2008). Teknik ekstraksi merupakan suatu teknik untuk menyalin unit-unit teks yang paling penting atau paling informatif dari teks sumber menjadi ringkasan, sedangkan teknik abstraksi adalah mengambil intisari dari teks sumber kemudian membuat ringkasan dengan menciptakan kalimat-kalimat baru yang merepresentasikan intisari teks sumber dalam bentuk berbeda (Jezek & Steinberger 2008). Beberapa metode peringkasan teks otomatis yang telah dilakukan antara lain peringkasan teks menggunakan teknik rantai leksikal (Barzilay & Elhadad 1997) sebagai metode untuk memperoleh representasi teks. Mitra et al. (1997) membuat peringkasan teks dengan menggunakan teknik bushy path untuk menghasilkan ekstraksi paragraph. Yeh et al. (2005) membuat ringkasan dengan menggunakan teknik lantent semantic analysis (LSA), hasil ringkasan ini didasari oleh kalimat
2
semantik. Peringkasan teks dapat dilakukan dengan menggunakan algoritme genetika (Silla et al. 2004; Khalessizadeh et al. 2006; Fattah & Ren 2008). Algoritme genetika digunakan untuk mencari bobot optimal pada fitur teks kalimat. Pembobotan kalimat merupakan bagian penting dalam peringkasan teks. (Khalessizadeh et al. 2006; Fattah & Ren 2008) telah membuat ringkasan teks dengan menggunakan algoritme genetika sebagai pembobotan kalimat. Menurut Khalessizadeh et al. (2006) algoritme genetika lebih efektif dalam penentuan bobot dibandingkan dengan menggunakan teknik TFIDF. Hasil penelitian yang dilakukan oleh Fattah dan Ren (2008) menunjukkan bahwa peringkasan teks yang dihasilkan dengan menggunakan teknik algoritme genetika lebih baik dibandingkan teknik regresi matematika. Akurasi dari algoritme genetika yaitu 44.94% dan 43.92% untuk peringkasan teks menggunakan teknik regresi matematika. Pada penelitian Fattah dan Ren (2008) melibatkan 10 fitur teks untuk membuat ringkasan dengan algoritme genetika, namun tidak melibatkan hubungan antar kalimat semantik. Kalimat semantik adalah kalimat yang mencirikan hubungan antar kalimat berdasarkan semantik. Kalimat semantik dapat ditentukan dengan menggunakan teknik singular value decomposition (SVD). Oleh karena itu, penelitian ini perlu dilakukan untuk membuat ringkasan teks dengan melibatkan sepuluh fitur teks (Fattah & Ren 2008) dan fitur teks kalimat semantik. Penentuan bobot optimal atau tingkat kepentingan untuk tiap fitur teks digunakan teknik algoritme genetika. 1.2 Tujuan Berdasarkan latar belakang tersebut, penelitian ini bertujuan untuk melakukan optimasi peringkasan teks dengan menggunakan algoritme genetika dan menganalisa penambahan ekstraksi fitur teks kalimat semantik menggunakan teknik singular value decomposition.
3
1.3 Manfaat Manfaat dari penelitian ini adalah menghasilkan ringkasan teks yang optimal dan melakukan peringkasan teks secara cepat dan menghemat waktu untuk memperoleh intisari dokumen. 1.4 Ruang Lingkup Desain dan pengembangan sistem peringkasan teks ini memiliki batasan atau ruang lingkup yang harus dikerjakan dengan cakupan sebagai berikut : 1. Ekstraksi teks yang digunakan adalah bahasa Indonesia. 2. Tema dokumen yang digunakan adalah berita nasional. 3. Dokumen yang digunakan berjenis teks.
4
2 TINJAUAN PUSTAKA
2.1
Peringkasan Teks Peringkasan teks adalah proses pemampatan teks sumber ke dalam versi
lebih pendek namun tetap mempertahankan informasi yang terkandung didalamnya (Barzilay & Elhadad 1997). Ada dua kriteria peringkasan teks yaitu peringkasan teks berdasarkan eksktraksi dan abstraksi (Jezek & Steinberger 2008). Teknik ekstraksi merupakan suatu teknik untuk menyalin unit-unit teks yang paling penting atau paling informatif dari teks sumber menjadi ringkasan, sedangkan teknik abstraksi adalah mengambil intisari dari teks sumber kemudian membuat
ringkasan
dengan
menciptakan
kalimat-kalimat
baru
yang
merepresentasikan intisari teks sumber dalam bentuk berbeda (Jezek & Steinberger 2008). 2.2
Paragraf Paragraf dapat didefinisikan sebagai unit informasi yang memiliki topik atau
pikiran utama atau topik sebagai dasarnya dan disatukan oleh ide pengontrol. Suatu paragraf yang baik adalah paragraf yang mampu mengarahkan dan membawa pembaca memahami dengan baik kesatuan informasi yang diberikan penulisnya melalui ide-ide pengontrolnya (Gunawan et al. 2008). 2.3
Ekstraksi fitur teks Penelitian ini menggunakan sepuluh fitur teks berdasarkan penelitian Fattah
dan Ren (2008) yaitu: posisi kalimat, positive keyword¸ negative keyword, kemiripan antar kalimat, kalimat yang menyerupai judul kalimat, kalimat yang mengandung nama entiti, kalimat yang mengandung data numerik, panjang kalimat, koneksi antar-kalimat, penjumlahan bobot koneksi antar-kalimat, dan penambahan fitur teks kalimat semantik dengan menggunakan teknik SVD. 2.3.1
Posisi Kalimat (f1) Posisi kalimat adalah letak kalimat dalam sebuah paragraf. Pada penelitian
ini diasumsikan bahwa kalimat pertama pada tiap paragraf adalah kalimat yang
5
paling penting. Oleh karena itu, penelitian ini mengurutkan kalimat tersebut berdasarkan posisinya. Berikut ini contoh fitur teks posisi kalimat pada sebuah dokumen. Merokok dapat menjadi kebiasaan yang mahal. Seorang yang sudah candu merokok rata-rata menghabiskan rokok satu bungkus per hari. Dengan merokok rata-rata Rp. 9000,00 per bungkus, maka seorang pencandu akan mengeluarkan sekitar Rp. 3.285.000,00 per tahun. Banyaknya pengeluaran per tahun dapat melebihi nilai tersebut karena ekstra untuk mengganti bajunya yang berlubang karena percikan api rokok. Berdasarkan contoh dokumen tersebut, maka perhitungan skor fitur teks
posisi kalimat untuk kalimat pertama adalah , skor kalimat kedua adalah , skor
kalimat ketiga adalah , dan skor kalimat keempat adalah . Oleh karena itu, menghitung skor fitur teks posisi kalimat dapat dilihat pada (2.1).
(2.1)
Asumsikan s adalah kalimat didalam paragraf, adalah fitur teks posisi kalimat (fitur teks kesatu), N adalah total jumlah kalimat dalam satu paragraf dan X adalah posisi kalimat dalam tiap paragraf. 2.3.2
Positive Keyword (f2) Positive keyword adalah kata yang paling banyak muncul pada sebuah
kalimat. Berikut ini ilustrasi positive keyword pada dokumen pelatihan dan ringkasan manual: Merokok dapat menjadi kebiasaan yang mahal. Seorang yang sudah candu merokok rata-rata menghabiskan rokok satu bungkus per hari. Dengan merokok rata-rata Rp. 9000,00 per bungkus, maka seorang pencandu akan mengeluarkan sekitar Rp. 3.285.000,00 per tahun. Banyaknya pengeluaran per tahun dapat melebihi nilai tersebut karena ekstra untuk mengganti bajunya yang berlubang karena percikan api rokok. Merokok dapat menjadi kebiasaan yang mahal. Dengan merokok rata-rata Rp. 9000,00 per bungkus, maka seorang pencandu akan mengeluarkan sekitar Rp. 3.285.000,00 per tahun. Berdasarkan isi dokumen tersebut, kata merokok merupakan kata yang muncul pada kalimat dan memiliki peluang kemunculan yang tinggi pada
6
ringkasan (tahap pelatihan pada ringkasan manual). adalah ,
adalah , adalah , adalah . Oleh karena
itu, menghitung skor fitur teks positive keyword dapat dilihat pada (2.2). #
! " % &' ("
(2.2)
"$
Asumsikan s adalah kalimat dalam ringkasan dokumen, S adalah kalimat dalam dokumen, adalah fitur teks positive keyword (fitur teks kedua), n adalah jumlah keyword dalam kalimat, " adalah banyaknya keyword ke-i yang muncul dalam kalimat. &' ("
&' (" &' ("
&' ("
) *) () ) * )) () ) (+ &' (" ) *) () ) * ))
) *) () ) ,+, ) * ) () () ) * )) ) *) () ) ,+, ) * )
&' ("
) *) () ) ,+, ) * ) () ) (+ &' (" ) *) () ) ,+, ) * )
&' (" adalah perhitungan dari korpus pelatihan (ringkasan manual),
" , n, dan panjang kalimat dihitung menggunakan kalimat “s” pada tahap pengujian. 2.3.3
Negative Keyword (f3) Negative keyword merupakan kebalikan dari fitur teks positive keyword.
Negative keyword adalah kata yang sedikit muncul dalam kalimat. Berikut ini ilustrasi negative keyword pada dokumen pelatihan dan ringkasan manual: Merokok dapat menjadi kebiasaan yang mahal. Seorang yang sudah candu merokok rata-rata menghabiskan rokok satu bungkus per hari. Dengan merokok rata-rata Rp. 9000,00 per bungkus, maka seorang pencandu akan mengeluarkan sekitar Rp. 3.285.000,00 per tahun. Banyaknya pengeluaran per tahun dapat melebihi nilai tersebut karena ekstra untuk mengganti bajunya yang berlubang karena percikan api rokok. Merokok dapat menjadi kebiasaan yang mahal. Dengan merokok rata-rata Rp. 9000,00 per bungkus, maka seorang pencandu akan mengeluarkan sekitar Rp. 3.285.000,00 per tahun.
7
Berdasarkan isi dokumen tersebut, kata ekstra merupakan kata yang mucul pada kalimat dan memiliki peluang yang tinggi tidak muncul pada ringkasan.
- ) adalah 1, ) - adalah , - adalah , )
adalah . Oleh karena itu, menghitung skor fitur teks negative keyword dapat
dilihat pada (2.3). #
. ! " % - &' ("
(2.3)
"$
Asumsikan s adalah kalimat dalam ringkasan dokumen, S adalah kalimat dalam dokumen, adalah fitur teks negative keyword (fitur teks ketiga), n adalah jumlah
keyword dalam kalimat, " adalah banyaknya keyword ke-i yang muncul dalam kalimat. 2.3.4
Kemiripan Antar-Kalimat (f4) Kemiripan antar-kalimat merupakan kata yang muncul dalam kalimat sama
dengan kata yang muncul dalam kalimat lain. Berikut ini contoh penerapan kemiripan antar-kalimat yaitu : • • •
Saya pergi belajar dan nonton Saya pergi makan Saya sedang nonton
Berdasarkan ketiga kalimat tersebut, maka perhitungan skor fitur teks kemiripan antar-kalimat diilustrasikan pada Gambar 1. Skor kalimat pertama
adalah , skor kalimat kedua adalah , dan skor kalimat ketiga adalah . Pada / /
/
kalimat pertama memiliki tiga kata yang sama dengan kalimat kedua dan kalimat ketiga, yaitu kata “pergi, saya, nonton”. Kalimat kedua memiliki dua kata yang sama dengan kalimat kesatu dan kalimat ketiga, yaitu kata “pergi, saya”. Kalimat ketiga memiliki dua kata yang sama dengan kalimat kesatu dan kalimat kedua yaitu kata “saya, nonton”. Berdasarkan ilustrasi kemiripan antar-kalimat pada Gambar 1, maka skor fitur teks kemiripan antar-kalimat dihitung dengan menggunakan (2.4) dengan asumsi s adalah kalimat, adalah fitur teks kemiripan antar-kalimat (fitur teks keempat). 0 1
2 &' (() ) 3 2 &' (() )) ) ) *) 1 2 &' (() ) 4 2 &' (() )) ) ) *)
(2.4)
8
Gambar 1 Ilustrasi kemiripan antar-kalimat. 2.3.5
Kalimat yang Menyerupai Judul Dokumen (f5) Kalimat yang menyerupai judul dokumen adalah kata yang muncul dalam
kalimat sama dengan kata yang ada dalam judul dokumen. Berikut ini contoh penerapan kemiripan antar-kalimat yaitu : Judul dokumen : Aktivitas Saya • • •
Saya pergi belajar Saya pergi makan Aktivitas saya adalah nonton
Berdasarkan contoh tersebut, maka perhitungan skor fitur teks kalimat yang
menyerupai judul diilustrasikan pada Gambar 2. Skor kalimat pertama adalah ,
skor kalimat kedua adalah , dan skor kalimat ketiga adalah . Pada kalimat pertama memiliki satu kata yang sama dengan judul dokumen yaitu kata “saya”. Kalimat kedua memiliki satu kata yang sama dengan judul dokumen yaitu kata “saya”. Kalimat ketiga memiliki dua kata yang sama dengan judul dokumen yaitu kata “aktivitas, saya”.
Gambar 2 Ilustrasi kalimat yang menyerupai judul.
9
Berdasarkan ilustrasi Gambar 2, maka skor fitur teks kalimat yang menyerupai judul dokumen dapat dihitung dengan menggunakan (2.5) dengan asumsi s adalah kalimat, 5 adalah fitur teks kalimat yang menyerupai judul dokumen (fitur teks kelima). 6 1
2.3.6
2 &' (() ) 3 2 &' (() )7+(+ 1 2 &' (() ) 4 2 &' (() )7+(+
(2.5)
Kalimat yang Mengandung Nama Entiti (f6) Nama entiti adalah sebuah kumpulan kata yang memiliki makna atau
membentuk nama sebuah institusi, nama orang, nama pulau. Misalnya Institut Pertanian Bogor merupakan kumpulan kata yang memiliki makna sebuah institusi perguruan tinggi. Berikut ini ilustrasi kalimat dalam dokumen yang mengandung nama entiti: Ada dua alasan utama mengapa saya memutuskan untuk memilih Institut Pertanian Bogor setelah tamat SMU. Pertama, biaya tidak terlalu mahal. Biaya kuliah cukup murah dan boleh dibayar dua kali. Hal ini penting karena orang tua saya bukan orang kaya. Kedua, sistem pendidikan yang baik. Institut Pertanian Bogor sudah dikenal karena tenaga pengajarnya banyak yang doktor dan berpengalaman dalam mengajar. Selain itu, mahasiswanya diberi praktek baik di laboratorium maupun di lapangan. Berdasarkan teks dokumen tersebut, kalimat yang mengandung nama entiti terdapat pada kalimat kesatu dan kalimat keenam, sehingga skor untuk kalimat kesatu adalah
, skor kalimat keenam adalah , dan skor untuk kalimat yang lain 9
8
adalah bernilai 0. Maka perhitungan fitur teks kalimat mengandung nama entiti dapat menggunakan (2.6) dengan asumsi s adalah kalimat, : adalah fitur teks kalimat yang mengandung nama entiti (fitur teks keenam). ;
2.3.7
)) * *() ) ) 7) ) *)
(2.6)
Kalimat yang Mengandung Data Numerik (f7) Pada peringkasan teks mempertimbangkan data numerik, karena dalam
kalimat yang berisi data numerik terdapat kalimat yang penting. Dokumen keuangan merupakan contoh dokumen yang banyak mengandung data numerik,
10
sehingga peringkasan dokumen tersebut mempertimbangkan fitur teks data nemerik. Berikut ini ilustrasi kalimat dalam dokumen yang mengandung data numerik: Merokok dapat menjadi kebiasaan yang mahal. Seorang yang sudah candu merokok rata-rata menghabiskan rokok satu bungkus per hari. Dengan merokok rata-rata Rp. 9000,00 per bungkus, maka seorang pencandu akan mengeluarkan sekitar Rp. 3.285.000,00 per tahun. Banyaknya pengeluaran per tahun dapat melebihi nilai tersebut karena ekstra untuk mengganti bajunya yang berlubang karena percikan api rokok. Berdasarkan teks dokumen tersebut, kalimat yang mengandung data numerik terdapat pada kalimat kedua, sehingga skor untuk kalimat kedua adalah
9
,
sedangkan skor kalimat-kalimat lain adalah bernilai 0, maka perhitungan fitur teks kalimat mengandung data numerik dapat menggunakan (2.7) dengan s adalah kalimat, / adalah fitur teks kalimat yang mengandung data numerik (fitur teks ketujuh). <
2.3.8
() ) + *() ) ) 7) ) *)
(2.7)
Panjang Kalimat (f8) Panjang kalimat dihitung berdasarkan jumlah kata dalam kalimat dibagi
jumlah kata unik dalam dokumen. Berikut ini ilustrasi panjang kalimat pada sebuah dokumen: Panjang kalimat Merokok dapat menjadi kebiasaan yang mahal. Seorang yang sudah candu merokok rata-rata menghabiskan rokok satu bungkus per hari. Dengan merokok rata-rata Rp. 9000,00 per bungkus, maka seorang pencandu akan mengeluarkan sekitar Rp. 3.285.000,00 per tahun. Banyaknya pengeluaran per tahun dapat melebihi nilai tersebut karena ekstra untuk mengganti bajunya yang berlubang karena percikan api rokok. Berdasarkan contoh dokumen tersebut, maka kata dalam kalimat pertama berjumlah 3 (tidak termasuk kata umum atau stoplist), sedangkan kata unik dalam dokumen berjumlah 25 kata, sehingga panjang kalimat pertama bernilai
5
.
Berdasarkan ilustrasi tersebut, maka perhitungan fitur teks panjang kalimat dapat
11
menggunakan (2.8) dengan asumsi s adalah kalimat, = adalah fitur teks panjang kalimat (fitur teks kedelapan). >
2.3.9
7+ ) ) )() ) ) )+ *() )( +
(2.8)
Koneksi Antar-Kalimat (f9) Koneksi antar-kalimat adalah banyaknya kalimat yang memiliki kata yang
sama dengan kalimat lain dalam satu dokumen. Berikut ini contoh penerapan koneksi antar-kalimat yaitu : • • • •
Saya pergi belajar Saya pergi makan Saya nonton Dia sedang nonton juga
Gambar 3 Ilustrasi koneksi antar-kalimat. Berdasarkan contoh kalimat tersebut, maka fitur teks koneksi antar-kalimat diilustrasikan pada Gambar 3. Kalimat pertama memiliki dua kata yang sama dengan kalimat kedua dan kalimat ketiga yaitu kata “pergi, saya”, sehingga kalimat pertama memiliki dua koneksi. Kalimat kedua memiliki dua kata yang sama dengan kalimat pertama dan kalimat ketiga yaitu kata “pergi, saya”, maka kalimat kedua memiliki dua koneksi. Kalimat ketiga memiliki dua kata yang sama dengan kalimat kedua dan kalimat keempat yaitu kata “saya, nonton”, maka kalimat kalimat ketiga memiliki dua koneksi. Kalimat keempat hanya memiliki kata yang sama dengan kalimat ketiga yaitu kata “nonton”, sehingga kalimat keempat hanya memiliki satu koneksi. Penelitian ini menggunakan normalisasi agar skor nilai pada tiap kalimat dalam jangkauan 0 sampai 1. Perhitungan fitur
12
teks koneksi antar-kalimat dilihat pada (2.9) dengan asumsi s adalah kalimat, 9 adalah fitur teks jumlah koneksi antar-kalimat (fitur teks kesembilan). ? @A+ ) *) ) B ) *)
(2.9)
2.3.10 Penjumlahan Bobot Koneksi Antar-Kalimat (f10) Fungsi fitur teks ini adalah menjumlahkan bobot koneksi antar-kalimat. Perhitungan fitur teks penjumlahan bobot koneksi antar-kalimat dilihat pada (2.10) dengan asumsi s adalah kalimat, 8 adalah fitur teks penjumlahan bobot koneksi antar-kalimat (fitur teks kesepuluh). C ! *) ) ) *)
(2.10)
2.3.11 Kalimat Semantik (f11) Kalimat semantik adalah kalimat yang mencirikan hubungan antar kalimat yang didasari semantik. Asumsikan D adalah sebuah dokumen, D adalah banyaknya kata dalam D, dan adalah banyaknya kalimat dalam D. Matriks kata dapat dilihat pada (2.11), dengan E adalah kalimat ke-j dalam dokumen dan " adalah term ke-i yang muncul didalam dokumen. Pada penelitian ini menggunakan semua keyword atau term yang ada dalam dokumen kecuali kata-kata stoplist.
A =
G H D
G 'F 'FG 'GF 'GFG H H 'DF 'GF
I I I J I
'F ')GF I 'DF
(2.11)
dengan '"FE didefinisikan pada (2.12), dan " adalah banyaknya kemunculan term ke-i pada kalimat. K" sentences frequencyi merupakan banyak kalimat yang mengandung
term
ke-i,
Q
sedangkan LK" MNO PRS U merupakan T
ukuran
diskriminan kemunculan term ke-i dalam dokumen, N adalah banyaknya kalimat dalam satu dokumen.
'"FE " V LK"
(2.12)
Pada penelitian ini, kalimat semantik ditentukan dengan menggunakan teknik SVD (Yie et al. 2005). Persamaan Singular Value Decomposition (SVD)
13
adalah W XY Z , dengan X adalah matriks D V D vektor singular kiri, adalah
matriks diagonal D V singular value, dan Y adalah matriks V vektor singular kanan. Dimana vektor V merepresentasikan kalimat, sedangkan vektor U merepresentasikan kata yang ada pada suatu dokumen. Vektor S merupakan
tingkat penciri dari matrik A. Skor fitur teks kalimat semantik dapat diterapkan pada (2.13) dengan asumsi s adalah kalimat, adalah fitur teks kalimat semantik (fitur teks kesebelas), penjelasan secara detail pada bab pembahasan.
) * * *,)
2.4
(2.13)
Algoritme Genetika Menurut Goldberg (1989) algoritme genetika atau genetic algorithm adalah
algoritme pencarian yang didasari pada mekanisme genetik alamiah dan seleksi alamiah. GA dapat diaplikasikan untuk menyelesaikan permasalahan optimasi kombinasi, yaitu dengan mendapatkan suatu nilai solusi optimal terhadap suatu permasalahan yang mempunyai banyak kemungkinan (Hermanto 2003). GA dikarakteristik dengan lima komponen dasar yaitu: 1.
Representasi kromosom untuk memudahkan penemuan solusi dalam masalah pengoptimasian.
2.
Inisialisasi populasi.
3.
Fitness function yang mengevaluasi setiap solusi.
4.
Proses genetik yang menghasilkan sebuah populasi baru dari populasi yang ada.
5.
Parameter seperti ukuran populasi, peluang proses genetik, dan jumlah generasi.
2.4.1
Siklus Algoritme Genetika Siklus dari algoritme genetika pertama kali diperkenalkan oleh Goldberg
(1989), dapat dilihat pada Gambar 4. Siklus ini terdiri beberapa bagian yaitu: populasi awal, evaluasi fitness, seleksi individu, pindah silang (crossover), mutasi (mutation), dan populasi baru.
14
Gambar 4 Siklus algoritma genetika oleh Goldberg (1989). 2.4.1.1 Populasi Populasi awal adalah sekumpulan kromosom awal yang dibangkitkan secara acak dalam satu generasi. Populasi baru merupakan sekumpulan kromosom baru hasil dari proses seleksi, pindah silang dan mutasi. Jumlah populasi dalam algoritme genetika bergantung pada masalah yang akan diselesaikan. Kromosom adalah kumpulan gen yang membentuk nilai tertentu, yang direpresentasikan sebagai solusi atau individu. Gen-gen dapat berupa nilai biner, float, integer, atau string. Allele merupakan nilai dari gen. Generasi merupakan satu siklus proses evolusi atau satu iterasi didalam algoritme genetika. Gambar 5 menjelaskan ilustrasi tentang representasi penyelesaian masalah dalam algoritme genetika. Teknik untuk pembangkitan populasi awal yaitu: random generator. Random generator adalah suatu proses pembangkitan bilangan acak untuk nilai tiap gen sesuai dengan representasi kromosom yang digunakan. Teknik ini digunakan untuk bilangan real atau float. Penerapan random generator pada Persamaan 2.14.
L[ \ ) ( ]"^_^ F `"ab cd
(2.14)
dengan IPOP merupakan gen berisi nilai dari bilangan acak yang dibangkitkan sebanyak "^_^ (jumlah populasi) dan `"ab (jumlah gen dalam tiap kromosom). Teknik pengkodean adalah suatu teknik untuk membuat kode atau membentuk struktur kromosom. Satu gen umumnya merepresentasikan satu variabel. Teknik pengkodean ini bergantung pada pemecahan masalah yang dihadapi. Kromosom dapat direpresentasikan sebagai string bit, array bilangan real. Berikut ini contoh representasi kromosom: •
String bit
: 11001, 10111
15
•
Array bilangan real
: 7.9, 9.7, -70
Gambar 5 Ilustrasi penyelesaian masalah dalam algoritme genetika. 2.4.1.2 Fungsi Evaluasi Suatu individu atau kromosom dievaluasi berdasarkan suatu fungsi tertentu sebagai ukuran performansinya. Fitness function adalah suatu fungsi yang digunakan untuk mengukur nilai kesamaan atau nilai optimal suatu individu. Nilai fitness adalah suatu nilai yang menyatakan baik atau tidak suatu solusi. Nilai fitness ini yang akan dijadikan referensi dalam mencapai nilai optimal dalam algoritme genetika. Pada evolusi alam, individu yang nilai evaluasi atau fitness tinggi akan bertahan hidup, sedangkan individu yang bernilai evaluasi rendah akan mati (Suyanto 2005). Pada peringkasan teks, nilai fitness ini direpresentasikan sebagai solusi atau irisan hasil ringkasan sistem dengan hasil ringkasan manusia. 2.4.1.3 Seleksi Seleksi adalah tahapan dalam algoritme genetika yang berfungsi memilih kromosom yang terbaik untuk proses pindah silang dan mutasi (Cox 2005) dan mendapatkan calon induk yang baik. Semakin tinggi nilai fitness suatu individu semakin besar kemungkinannya untuk dipilih. Jika kromosom memiliki nilai fitness kecil, maka tergantikan oleh kromosom baru yang lebih baik. Tiap kromosom dalam wadah seleksi akan menerima peluang reproduksi tergantung
16
pada nilai objektif kromosom terhadap nilai objektif dari semua kromosom dalam wadah seleksi tersebut. 2.4.1.4 Pindah Silang Pindah silang merupakan komponen yang penting dalam GA (Gen & Cheng 1997). Pindah silang adalah operator dari algoritme genetika yang melibatkan dua induk untuk membentuk kromosom baru. Pindah silang menghasilkan titik baru dalam ruang pencarian yang siap diuji. Operasi ini tidak selalu dilakukan pada semua individu yang ada. Individu dipilih secara acak untuk dilakukan penyilangan dengan e (peluang terjadi pindah silang) antara 0.6 sampai 0.95. Jika pindah silang tidak dilakukan, maka nilai dari induk akan diturunkan kepada anak (keturunan). Prinsip dari pindah silang adalah melakukan operasi genetika (pertukaran, aritmatika) pada gen-gen yang bersesuaian dari dua induk untuk menghasilkan individu baru. Pindah silang dilakukan pada setiap individu dengan peluang pindah silang yang telah ditentukan. Gambar 6 mengilustrasikan diagram alir proses pindah silang.
Gambar 6 Diagram alir proses pindah silang. Pindah Silang Satu Titik Pindah silang satu titik dan banyak titik biasanya digunakan untuk representasi kromosom dalam biner. Pada pindah silang satu titik, posisi pindah
17
silang k (k=1,2,…,N-1) dengan N = panjang kromosom diseleksi secara acak. Variabel-variabel ditukar antar kromosom pada titik tersebut untuk menghasilkan anak. Pada Gambar 7, ilustrasi pindah silang satu titik dengan peluang pindah silang 0.65 dan 0.70.
Gambar 7 Pindah silang satu titik. 2.4.1.5 Mutasi Mutasi adalah operator sekunder atau operator pendukung dalam algoritme genetika yang berperan mengubah struktur kromosom secara spontan. Perubahan spontan ini menyebabkan terbentuknya suatu mutan, yaitu suatu kromosom baru yang secara genetik berbeda dengan kromosom sebelumnya. Mutasi diperlukan untuk mencari solusi optimum, yaitu 1) mengembalikan gen-gen yang hilang pada generasi berikutnya, 2) memunculkan gen-gen baru yang belum pernah muncul pada generasi sebelumnya (Gen & Cheng 1997). Tingkat mutasi atau peluang mutasi (,f adalah rasio antara jumlah gen yang diharapkan mengalami mutasi pada setiap generasi dengan jumlah gen total dalam populasi. Peluang mutasi yang digunakan untuk running program biasanya rendah antara 0.001 sampai 0.2. Jika tingkat mutasi rendah terlalu rendah, maka semakin kecil memunculkan gen-gen baru. Jika mutasi terlalu tinggi maka banyak
18
mutan yan muncul, akibatnya banyak karakteristik kromosom induk yang hilang pada generasi berikutnya sehingga algoritme generika akan kehilangan mengingat atau belajar dari proses sebelumnya (Gen & Cheng 1997). Gambar 8 mengilustrasikan diagram alir mutasi.
Gambar 8 Diagram alir mutasi. Gambar 9 merupakan contoh penerapan mutasi pada gen yang berisi nilai biner, dengan r adalah indeks atau posisi gen yang mengalami mutasi. Mutasi biner merupakan salah satu cara sederhana untuk mengganti satu atau beberapa nilai gen dari kromosom. Pada Gambar 9, nilai acak r adalah tiga maka nilai gen ketiga yang mengalami mutasi.
Gambar 9 Proses dan hasil mutasi.
19
3 METODE PENELITIAN
3.1
Prosedur Penelitian Penelitian ini dilakukan dengan tiga tahap yaitu: tahap pengumpulan
dokumen teks, tahap pelatihan dan tahap pengujian. Gambar 10 menunjukkan tahap pelatihan dan pengujian.
Gambar 10 Peringkasan teks secara otomatis. 3.1.1 Pengumpulan Dokumen Teks Penelitian ini membutuhkan masukan dokumen teks berbahasa Indonesia dengan dokumen berjenis file teks. Pada penelitian ini digunakan sebanyak 150
20
dokumen berita nasional. Dokumen tersebut berasal dari berita online harian Kompas yang didapat dari korpus penelitian (Ridha 2002). 3.1.2
Tahap Pelatihan Tahap pelatihan terbagi atas tiga bagian utama yaitu: ringkasan dokumen,
fitur teks, dan pemodelan algoritme genetika. Berikut ini penjelasan masingmasing bagian utama tersebut: 3.1.2.1 Ringkasan Dokumen Secara Manual Pada tahap ini, dokumen diringkas secara manual oleh tiga orang yang berbeda. Jumlah dokumen yang digunakan sebanyak 100 dokumen berita berbahasa Indonesia.
Dokumen diringkas dengan pemampatan (compression
rate) sebesar 30%, 20%, dan 10%. 3.1.2.2 Ekstraksi Fitur Teks Ekstraksi fitur teks merupakan suatu proses untuk mendapat ekstraksi teks dari dokumen. Hasil dari fitur teks adalah ektraksi teks seperti posisi kalimat (f1), positive keyword (f2), negative keyword (f3), kemiripan antar-kalimat (f4), kalimat yang menyerupai judul dokumen (f5), kalimat yang mengandung entiti nama (f6), kalimat yang mengandung data numerik (f7), panjang relatif kalimat (f8), koneksi antar-kalimat (f9), penjumlahan bobot koneksi antar-kalimat (f10), dan kalimat semantik (f11). Fitur tersebut telah dijelaskan pada Bab 2. 3.1.2.3 Pemodelan Algoritme Genetika Pada tahap ini, algoritme genetika berfungsi sebagai pencarian pembobotan yang optimal pada tiap ekstraksi fitur teks. Tahap ringkasan manual dan ekstraksi fitur teks digunakan untuk menghitung fitness function yang berfungsi untuk mengevaluasi kromosom. Proses algoritme genetika ditunjukkan pada Gambar 11. Proses algoritme genetika dimulai dengan memberi nilai awal populasi. Tiap populasi berisi 1000 kromosom. Pada Gambar 12, sebuah kromosom direpresentasikan sebagai kombinasi seluruh fitur bobot dalam bentuk ' F ' F I F ' .
21
Gambar 11 Proses algoritme genetika.
Gambar 12 Representasi kromosom pada pembobotan ekstraksi fitur teks. Gambar 12 merupakan representasi kromosom pada pembobotan ekstraksi fitur teks dengan ' bobot pada ekstraksi fitur teks (f1), ' bobot pada ekstraksi
fitur teks (f2), dan seterusnya. Bobot ' F ' F I F ' bernilai antara 0 dan 1 dengan normalisasi bobot sehingga jumlah bobot menjadi 1. Berikut ini langkahlangkah proses algoritme genetika : a.
Populasi awal dibangkitkan secara acak sebanyak 1000 kromosom, dimana tiap nilai kromosom merepresentasikan bobot ekstraksi fitur teks. Bobot atau nilai yang ada pada kromosom diterapkan pada (3.1) yang berfungsi untuk mendapatkan nilai skor tiap kalimat. ' % g ' % g ' % . g ' % 0 g '5 % 6 g ': % ; g '/
% < g '= % > g '9 % ? g '8 % C g ' %
(3.1)
22
b.
Tiap kromosom dievaluasi oleh rata-rata F-measure, dimana nilai precision dan recall diperoleh dari irisan hasil ringkasan yang dibuat oleh mesin dan hasil ringkasan manual. Untuk setiap kromosom, proses F-measure dilakukan sebanyak 100 dokumen. Nilai rata-rata F-measure dapat dilihat pada (3.2).
c.
Setelah dievaluasi dilakukan seleksi kromosom menggunakan minimum fitness function. Seleksi kromosom ini berfungsi untuk memilih kromosomkromosom mana saja yang akan dipilih untuk proses pindah silang, mutasi dan mendapatkan calon induk yang baik.
d.
Peluang pindah silang yang digunakan pada penelitian ini adalah 0.88. Pindah silang terjadi jika peluang yang dihasilkan kromosom yang dijadikan induk lebih kecil dari peluang pindah silang yang telah ditentukan. Teknik yang digunakan pada pindah silang adalah teknik pindah silang satu titik.
e.
Peluang mutasi yang digunakan adalah 0.2.
f.
250 generasi diterapkan pada proses algoritme genetika untuk mendapatkan bobot ekstraksi fitur teks yang optimal. Berikut ini perhitungan F-measure, precision, dan recall menurut (Baeza-
Yates & Ribeiro-Neto 1999):
Kh$
i g j Gj 3 l 3 l k k j i gj g j l
(3.2)
dengan i adalah bobot dari precision (P) dan recall (R), i m penekanan pada
precision dan i n penekanan pada recall. Nilai F-measure diantara 0 dan 1,
oleh karena itu nilai i . Asumsikan bahwa S adalah hasil ringkasan teks dari
mesin (proses fungsi skor dari dokumen training) dan T adalah ringkasan teks secara manual. 3.1.3
Tahap Pengujian Tahap pengujian mengunakan 50 dokumen berita berbahasa Indonesia
(dokumen yang digunakan pada tahap ini berbeda dengan dokumen yang digunakan pada tahap pelatihan). Proses selanjutnya yaitu ekstraksi fitur teks. Proses ini sama dengan yang dilakukan di ekstraksi fitur teks tahap pelatihan. Proses peringkasan teks secara otomatis didasari model yang telah diciptakan di
23
tahap pelatihan. Model ini direpresentasikan sebagai bobot ' F ' F I F ' pada
fitur teks yang stabil atau optimal. Kombinasi bobot ' F ' F I F ' diterapkan
pada fungsi skor untuk setiap kalimat dan dapat dilihat pada (3.1). Fungsi ini digunakan untuk mengintegrasikan semua fitur teks. Pemilihan kalimat berfungsi untuk menghasilkan sebuah ringkasan. Oleh karena itu, seluruh kalimat diurutkan berdasarkan nilai yang dihitung dari (3.1), dan jumlah kalimat yang ditetapkan top-skor menggunakan compression rate (CR) 10%, 20 %, dan 30%. 3.2
Lingkungan Pengembangan
Lingkungan pengembangan yang akan digunakan dalam penelitian ini sebagai berikut: - Perangkat lunak: Windows Vista Business, Bahasa Pemrograman PERL. - Perangkat keras: Intel® Core (TM)2 Duo CPU T8100 @ 2.10 GHz, 2037 MB RAM. 3.3
Waktu dan Tempat Penelitian Penelitian dilaksanakan di laboratorium Pascasarjana Departemen Ilmu
Komputer Institut Pertanian Bogor mulai bulan Maret 2010 sampai dengan bulan Agustus 2010.
24
4 HASIL DAN PEMBAHASAN
4.1
Data Korpus Data korpus berisi berita-berita nasional berbahasa Indonesia dari tanggal 11
Maret 2002 sampai 11 April 2002. Berita tersebut berasal dari berita online harian Kompas yang didapat dari korpus penelitian Ridha (2002). Dokumen yang digunakan pada tahap pelatihan sebanyak 100 dokumen. Dokumen-dokumen tersebut dirangkum dengan batas pemampatan (compression rate) sebesar 30%, 20%, dan 10%, rangkuman tersebut dibuat oleh dua orang yang berbeda. Hasil rangkuman manual ini digunakan untuk mengevaluasi hasil dari ringkasan yang dibuat oleh sistem. Dokumen yang digunakan pada tahap pengujian sebanyak 50 dokumen. Dokumen-dokumen tersebut dirangkum dengan batas pemampatan (compression rate) sebesar 30%, 20%, dan 10%, rangkuman tersebut dibuat oleh satu orang. Hasil rangkuman manual ini digunakan untuk mengevaluasi hasil dari ringkasan yang dibuat oleh sistem. Rata-rata jumlah kalimat pada dokumen berita adalah 26.61. 4.2
Format Dokumen Penelitian ini menggunakan dokumen dalam bentuk format XML sederhana,
dan jenis dokumen yang digunakan bertipe teks. Gambar 13 merupakan contoh format dokumen yang digunakan pada tahap pelatihan dan pengujian.
Gambar 13 Format dokumen pada tahap pelatihan dan pengujian.
25
4.3
Pemotongan Kalimat Penelitian ini menggunakan teknik ekstraksi teks untuk membuat ringkasan,
oleh karena itu diperlukan pemotongan kalimat yang baik. Pengertian kalimat adalah satu atau lebih string kata diakhiri dengan suatu tanda berhenti sepenuhnya, tanda tanya, atau tanda seru. Penelitian ini menggunakan bentuk pemotongan kalimat berupa yaitu: 1.
Batas kalimat sesudah tanda baca . ? ! Contoh : - Aku mau pulang ke desa. - Dia mau kemana ? - Akhir dari sebuah cerita !
2.
Batas kalimat sesudah tanda petik, bukan setelah tanda titik Contoh : “Pindahkan lemari itu. Lemari itu bukan milik mu.”, kata Amir kepada Joko.
3.
Dapat mengenali singkatan seperti Prof. Dr. Jaka, M.Sc akan berkunjung ke Lampung.
4.4
Metode Evaluasi Menurut Mani dan Maybury (1999) terdapat dua teknik untuk mengevaluasi
hasil ringkasan teks yaitu extrinsic evaluation dan instrinsic evaluation. Extrinsic evaluation adalah proses penilaian hasil ringkasan berdasarkan pada fungsi tertentu, sedangkan instrinsic evaluation merupakan metode yang berdasarkan perhitungan antara sistem (peringkasan teks oleh sistem) dengan hasil ringkasan manual. Penelitian ini menggunakan metode instrinsic evaluation dengan menggabungkan metode recall (R), precision (P), dan F-Measure (F) pada hasil ringkasan oleh manusia (ringkasan manual) dengan hasil ringkasan yang dibuat oleh mesin. Berikut ini perhitungan F-Measure, precision, dan recall menurut (Baeza-Yates & Ribeiro-Neto 1999) :
K
3 l 3 l Gj k k j g j l
(5.1)
asumsikan S adalah hasil ringkasan teks dari mesin dan T adalah hasil ringkasan teks manual.
26
4.5
Kalimat Semantik Asumsikan D adalah sebuah dokumen, D adalah banyaknya kata
dalam D, dan adalah banyaknya kalimat dalam D. Matriks kata dapat
dilihat pada (5.2), dengan E adalah kalimat ke-j dalam dokumen dan " adalah term ke-i yang muncul didalam dokumen. Pada penelitian ini menggunakan semua keyword yang ada dalam dokumen kecuali kata-kata stoplist.
A =
'F 'F 'F 'F H H 'oF 'F
H o
I Q I 'FQ I 'FQ J I I 'oFQ
(5.2)
dimana '"FE didefinisikan pada (5.3), dan " adalah banyaknya kemunculan term ke-i pada kalimat. K" sentences frequencyi merupakan banyak kalimat yang mengandung
term
sedangkan LK" MNO P
ke-i,
Q
RST
U merupakan
ukuran
diskriminan kemunculan term ke-i dalam dokumen, N adalah banyaknya kalimat dalam satu dokumen.
'"FE " V LKE
(5.3)
Perlakuan Singular Value Decomposition (SVD) diterapkan pada matriks W dengan W XY Z , dengan X adalah matriks D V D vektor singular kiri, adalah
matriks diagonal D V singular value, dan Y adalah matriks V
vektor singular kanan. Fungsi utama dari SVD adalah mengurangi matriks yang besar menjadi matriks yang lebih kecil disebut sebagai reduksi dimensi. Kegunaan dari
reduksi
dimensi
ini
adalah
mengurangi
waktu
komputasi
tanpa
menghilangkan makna dari matriks tersebut. Penelitian tetap mempertahankan dua dimensi sehingga nilai adalah 2. Penentuan nilai ini belum ada acuan yang jelas, dikarenakan masih dalam topik penelitian. Matriks reduksi berbentuk W Xp p YpZ . Berdasarkan nilai SVD, maka pemberian skor pada kalimat dilakukan teknik (Berry & Dumais 1995), dikarenakan matriks adalah diagonal
singular maka Z . Matrik V terdiri dari n baris, dimana baris tersebut
merepresentasikan vektor kalimat, sehingga vektor kalimat dapat dilihat pada (5.4).
27
Y WZ Xp pq
(5.4)
Penelitian ini memodifikasi hasil Persamaan 5.4 dengan perkalian antar-matriks S*V (Baker 2005). Untuk mencari hubungan kemiripan antar kalimat digunakan Persamaan 5.5.
* F
r
(5.5)
Sehingga akan terbentuk matriks kemiripan antar-kalimat yaitu: H Q
* F * F * F * F H H *Q F *Q F
I Q I * F Q I * F Q J I I *Q F Q
Vektor U merepresentasikan term yang ada pada suatu dokumen. Vektor S merupakan tingkat penciri dari matrik A. Proses pembobotan matrik A dilakukan pada tiap-tiap dokumen pelatihan dan dokumen pengujian. Proses SVD dilakukan setelah pembobotan telah dilakukan. Berikut ini contoh perhitungan kalimat semantik menggunakan proses SVD: s1 : Pengiriman emas rusak karena kebakaran s2 : Pengiriman perak tiba di sebuah truk perak s3 : Pengiriman emas tiba di truk Tabel 1 Term frequency dan inverse sentences frequency S1 emas kebakaran pengiriman perak rusak tiba truk
s2 1 1 1 0 1 0 0
s3 0 0 1 2 0 1 1
SF 1 0 1 0 0 1 1
2 1 3 1 1 2 2
ISF 0.584963 1.584963 0 1.584963 1.584963 0.584963 0.584963
Matriks A dibentuk dari perkalian antara " V LK" s Pada Tabel 2 menunjukkan hasil pembobotan term pada tiap kalimat. Tahap selanjutnya adalah proses SVD dilakukan dengan tujuan mendapatkan vektor kalimat. Vektor kalimat ini yang digunakan sebagai perhitungan kemiripan antar kalimat.
28
Tabel 2 Pembobotan term pada kalimat s1 emas 0.584963 kebakaran 1.584963 pengiriman 0 perak 0 rusak 1.584963 tiba 0 truk 0
s2 0 0 0 3.169925 0 0.584963 0.584963
s3 0.584963 0 0 0 0 0.584963 0.584963
Tabel 3 Vektor kalimat s1 s2 s3
0.0146 -3.2737 2.3165 0.0228 0.0685 -0.0748
Berdasarkan vektor kalimat, dilakukan perhitungan kemiripan antar kalimat menggunakan Persamaan 5.5, sehingga terbentuk matriks kemiripan, ditunjukkan pada Tabel 4. Hasil akhir dari proses kalimat semantik adalah kalimat 1 memiliki skor terendah dan kalimat 3 memiliki skor tertinggi, sehingga makna yang didapat bahwa kalimat 3 memiliki hubungan semantik yang tinggi, sedangkan kalimat 1 memiliki hubungan semantik yang rendah. Tabel 4 Data matriks kemiripan s1 s1 s2 s3 jumlah 4.6
1 -0.005 1.072 2.06668161
s2 s3 Total -0.005 1.072 1 0.866 0.866 1 1.861 2.938 6.865746
skor 0.301013 0.271028 0.427959
Pemodelan Algoritme Genetika Pemodelan algoritme genetika dilakukan pada tahap pelatihan dengan lima
percobaan. Pemodelan algoritme genetika dilakukan terhadap compression rate (CR) 10%, CR 20%, dan CR 30%. Tujuan dari pemodelan algoritme genetika adalah menentukan bobot yang optimal pada tiap-tiap fitur teks. Hasil dari pemodelan algoritme genetika berupa model kromosom terbaik dari CR 10%,
29
CR 20%, dan CR 30%. Model-model kromosom tersebut digunakan pada tahap pengujian. Pemodelan algoritme genetika terdiri beberapa bagian yaitu: 1.
Representasi kromosom Salah satu komponen penting pada algoritme genetika adalah kromosom.
Kromosom pada pemodelan algoritme genetika direpresentasikan sebagai gen yang berisi nilai bobot fitur teks dalam bentuk ' F ' F I F ' . Nilai bobot tersebut dihasilkan dari proses acak antara 0 sampai 1 dan dilakukan proses normalisasi agar jumlah bobot bernilai 1. Bentuk representasi kromosom ditunjukkan pada Gambar 14.
Gambar 14 Representasi kromosom. 2.
Penentuan nilai awal Penentuan nilai awal pada pemodelan algoritme genetika terdiri atas 1000
kromosom untuk tiap populasi, 250 generasi, peluang pindah silang adalah 0.88, dan peluang mutasi adalah 0.2 sedangkan penentuan peluang pindah silang dan peluang mutasi ditentukan berdasarkan eksperimental. 3.
Fungsi evaluasi Pada tahap pelatihan, proses evaluasi pada algoritme genetika berfungsi
sebagai evaluasi tingkat akurasi irisan antara ringkasan oleh sistem dan manual, ditunjukkan pada Persamaan 5.2. Proses fungsi evaluasi adalah sebagai berikut: -
Pada satu generasi, sebuah kromosom yang berisi gen (' F ' F I F ' ) diterapkan pada setiap kalimat pada dokumen pelatihan dan pengujian. Namun pada tahap pengujian hanya digunakan model kromosom yang terbaik yang didapat pada tahap pelatihan.
-
Skor(S) = ' % g ' % g ' % . g
' % 0 g '5 % 6 g ': % ; g
'/ % < g '= % > g '9 % ? g
'8 % C g ' %
-
Skor kalimat dilakukan pada tiap dokumen pelatihan dan pengujian, diurutkan secara descending.
30
-
Ringkasan dari sistem berdasarkan pada proses pemampatan atau compression rate (CR) sebesar 10%, 20 %, dan 30%, artinya bahwa banyaknya kalimat pada tiap dokumen dikalikan dengan CR 10%, CR 20%, dan CR 30%.
-
Hasil ringkasan dari sistem dievaluasi dengan ringkasan manual (5.1), sehingga menghasilkan akurasi atau F-measure dari tiap dokumen.
-
F-measure pada sebuah kromosom adalah rata-rata F-measure atau nilai akurasi dari seluruh dokumen pelatihan.
-
Setiap satu generasi, diambil empat kromosom terbaik dan dikembalikan kedalam populasi.
4.
Seleksi kromosom Proses seleksi kromosom pada pemodelan algoritme genetika didasari oleh F-
measure dari tiap-tiap kromosom, bila F-measure di bawah batas minimum maka kromosom tersebut tidak akan diseleksi. Penelitian ini tidak menggunakan Fmeasure statis, artinya batas minimun F-measure yang diciptakan berdasarkan nilai terendah F-measure terbaik dari masing-masing generasi atau tiap iterasi. Jumlah F-measure terbaik dari masing-masing generasi ditentukan berdasarkan jumlah kromosom dibagi dengan jumlah iterasi. 5.
Proses pindah silang Proses pindah silang terjadi jika peluang yang dihasilkan lebih kecil
dibandingkan peluang pindah silang. Pada penelitian ini, gen yang mengalami pindah silang diantara gen nomor 1 ' sampai gen nomor 11 ' dan diseleksi secara acak. Pertukaran antar kromosom dilakukan pada titik gen yang telah diseleksi secara acak. Pertukaran antar kromosom ini bertujuan untuk mendapat kromosom yang terbaik. Nilai gen ditentukan berdasarkan nilai acak diantara nol sampai satu. Nilai gen yang mengalami pindah silang akan dinormalisasi kembali dengan tujuan menjaga nilai gen dalam kromosom berjumlah satu. Gambar 15 menunjukkan proses pindah silang antar dua induk. 6.
Proses mutasi Proses mutasi terjadi jika peluang yang dihasilkan lebih kecil dibandingkan
peluang mutasi. Gen yang dimutasi adalah gen yang berada diantara gen nomor 1 ' sampai gen nomor 11 ' sedangkan nilai gen ditentukan berdasarkan
31
nilai acak diantara nol sampai satu dan dilakukan secara acak. Mutasi gen hanya berjumlah satu. Nilai gen yang mengalami mutasi akan dinormalisasi kembali dengan tujuan menjaga nilai gen dalam kromosom berjumlah satu. Pada Gambar 16 menunjukkan diagram alir proses mutasi.
Gambar 15 Diagram alir proses pindah silang antar dua induk.
Gambar 16 Diagram alir proses mutasi. 7.
Model kromosom terbaik Proses algoritme genetika dimulai dari penentuan nilai awal, evaluasi fitness,
proses pindah silang, sampai proses mutasi. Pada penelitian ini, proses algoritme genetika berhenti jika nilai generasi telah mencapai 250, diasumsikan bahwa jika
32
iterasi selesai maka didapat model kromosom yang terbaik. Model kromosom terbaik ini yang akan digunakan sebagai bobot yang optimal pada tahap pengujian. Pada Tabel 5 menunjukkan hasil model kromosom terbaik pada CR 30% untuk 10 fitur dan 11 fitur. Tabel 5 Contoh model kromosom terbaik untuk CR 30%
'
'
'
'
'5
':
'/
'=
'9
'8
'
10 fitur
0.008
0.039
0.000
0.086
0.506
0.012
0.089
0.207
0.049
0.004
0.000
11 fitur
0.060
0.056
0.000
0.225
0.428
0.050
0.055
0.003
0.016
0.051
0.056
4.7
Hasil Pengujian Model Algoritme Genetika Pengujian dilakukan sebanyak lima percobaan untuk masing-masing CR
10%, CR 20%, dan CR 30%. Hasil F-measure dihitung berdasarkan rataan dari seluruh dokumen pengujian. Pada tahap ini, pengujian dilakukan pada model kromosom terbaik ' F ' F I F ' pada CR 10%, CR 20%, dan CR 30%. 4.7.1 Hasil F-measure Tahap Pengujian Gambar 17 menunjukkan rata-rata F-measure pada tahap pengujian untuk masing-masing compression rate (CR 10%, CR 20%, dan CR 30%). F-measure tersebut terdiri dari F-measure yang menggunakan sepuluh fitur teks dan Fmeasure yang menggunakan sebelas fitur teks. Berdasarkan Gambar 17, Fmeasure tidak mengalami kenaikan secara signifikan di tiap compression rate. Penggunaan sepuluh fitur teks dan sebelas fitur teks pada CR 10% hanya mengalami kenaikan F-measure sebesar 3.26%, pada CR 20% mengalami penurunan sebesar 0.58%, dan CR 30% mengalami peningkatan sebesar 1.55%. Namun, rata-rata F-measure mengalami kenaikan secara linier dari CR 10% ke CR 20% sebesar 6.28%, dari CR 20% ke CR 30% sebesar 6.17%. Pada CR 30% menunjukkan tingkat akurasi paling tinggi dibandingkan dengan hasil akurasi dari CR 10%, dan CR 20%. Hal ini menunjukkan bahwa semakin besar compression rate maka nilai kemiripan hasil ringkasan sistem dengan hasil ringkasan manual semakin besar.
33
100% 90% 80%
Akurasi
70% 60% 50% 40% 30% 20% 10% 0% 10%
20%
30%
Compression rate
Gambar 17 Perbandingan pengujian F-measure ’sepuluh fitur teks’ () dan ’sebelas fitur teks’ (t) pada CR 10%, CR 20%, dan CR 30%. 4.7.2 Analisa Model Kromosom Berdasarkan Gambar 17, CR 30% memiliki F-measure paling tinggi dibandingkan dengan hasil F-measure dari CR 10%, dan CR 20%. Oleh karena itu, penelitian ini melakukan analisa model kromosom menggunakan model kromosom CR 30%. Tujuan analisa model kromosom pada penelitian ini adalah menentukan bobot fitur teks yang penting didalam peringkasan teks sehingga bobot-bobot fitur teks yang tidak penting dapat diabaikan didalam peringkasan teks. Model kromosom CR 30% (lampiran 1) diilustrasikan pada Tabel 6. Pada Tabel 6, bobot tertinggi diberi nilai 10 dan bobot terendah diberi nilai 0 sehingga total maksimum bobot berjumlah 50. Tujuan ilustrasi tersebut adalah melakukan perangkingan bobot fitur teks dan menganalisa fitur-fitur teks. Berdasarkan Tabel 6, bobot tertinggi terdapat pada fitur teks “kalimat yang menyerupai judul” yaitu '5 . Pada '5 memiliki rata-rata nilai bobot yang tinggi setiap percobaan yang dilakukan pada tahap pelatihan. Artinya fitur teks “kalimat yang menyerupai judul” sering muncul di setiap kalimat dalam dokumen dan fitur
34
teks tersebut memiliki peluang tinggi untuk menentukan kalimat yang penting dalam dokumen. Oleh karena itu, fitur teks “kalimat yang menyerupai judul” memiliki tingkat kepentingan yang paling tinggi dalam peringkasan teks. Tabel 6 Ilustrasi nilai bobot pada model kromosom CR 30% Percobaan 1
2
3
4
5
Jumlah total bobot
4
2
4
1
8
19
5
5
8
5
7
30
0
1
0
0
0
1
9
9
3
9
9
39
10 10
9
10 10
49
7
6
2
6
3
24
8
7
1
7
5
28
2
4
7
2
1
16
1
3
10
4
2
20
3
0
6
8
4
21
6
8
5
3
6
28
Bobot
'
' ' '
'5 ': '/ '= '9
'8 '
Bobot ' (fitur teks “kemiripan antar-kalimat”) merupakan nilai bobot tertinggi kedua setelah fitur teks “kalimat yang menyerupai judul”. Berdasarkan Tabel 6, fitur teks “kemiripan antar-kalimat” rata-rata memiliki nilai 9 pada tiap percobaan kecuali pada percobaan tiga. Makna skor bobot tersebut adalah fitur teks “kemiripan antar-kalimat” mempertimbangkan kemunculan kata dalam kalimat sama dengan kemunculan kata dalam kalimat lain sehingga keterlibatan fitur teks “kemiripan antar-kalimat” dalam peringkasan teks dapat memberikan kontribusi untuk menentukan kalimat yang penting dalam dokumen teks. Oleh karena itu, fitur teks “kemiripan antar-kalimat” merupakan bagian penting dalam peringkasan teks. Fitur teks “positive keyword” memiliki nilai bobot (' ) tertinggi ketiga dari sebelas fitur teks. Analisa skor bobot tersebut adalah fitur teks “positive keyword”
35
mempertimbangkan kemunculan kata di setiap kalimat dalam dokumen sehingga fitur teks tersebut memberikan kontribusi untuk menentukan kalimat yang penting dalam dokumen. Oleh karena itu, fitur teks “positive keyword” perlu dilibatkan dalam peringkasan teks. Fitur teks “kalimat semantik” dan fitur teks “kalimat yang mengandung data numerik” memiliki nilai bobot yang sama yaitu 28. Namun nilai bobot fitur teks “kalimat yang mengandung data numerik” pada percobaan tiga memiliki nilai bobot paling rendah yaitu 1, artinya stabilitas bobot '/ relatif rendah sedangkan nilai bobot fitur tek “kalimat semantik” relatif stabil. Analisa dari skor bobot tersebut adalah fitur teks “kalimat semantik” mempertimbangkan hubungan makna semantik antar kalimat dalam dokumen sehingga fitur teks tersebut memiliki tingkat kepentingan yang tinggi dalam peringkasan teks dan penelitian ini menggunakan bobot ' untuk melakukan pengujian (penentuan empat fitur teks). Fitur teks seperti posisi kalimat (f1), kalimat yang mengandung nama entiti (f6), panjang kalimat (f8), koneksi antar-kalimat (f9), penjumlahan bobot koneksi antar-kalimat (f10) mempunyai peranan penting dalam peringkasan teks namun nilai bobot dari fitur-fitur teks tersebut masih dibawah nilai 25. Maknanya adalah beberapa fitur teks tersebut dapat diabaikan dalam peringkasan teks tetapi akurasi tetap dapat dipertahankan (lihat Gambar 18). Fitur teks “negative keyword” memiliki bobot ' terendah dengan ratarata nol pada setiap percobaan yang dilakukan pada tahap pelatihan. Analisa dari skor bobot tersebut adalah fitur teks “negative keyword” mempertimbangkan ketidakmunculan kata di setiap kalimat dalam dokumen sehingga fitur teks tersebut tidak memberikan kontribusi untuk menentukan kalimat yang penting dalam dokumen. Oleh karena itu, fitur teks “negative keyword” dapat diabaikan dalam peringkasan teks. Tabel 7 menunjukkan perangkingan bobot fitur teks dari bobot terbesar sampai bobot terkecil. Tujuan dari perangkingan bobot fitur teks adalah menganalisa fitur teks yang penting dalam peringkasan teks. Berdasarkan perangkingan bobot tersebut, penelitian ini melakukan pengujian dengan menggunakan
dua
bobot
fitur
teks '5 F ' F empat
bobot
fitur
teks
36
'5 F ' F ' F ' , enam bobot fitur teks '5 F ' F ' F ' F '/ F ': , delapan bobot
fitur teks '5 F ' F ' F ' F '/ F ': F '8 F '9 dan sebelas bobot fitur teks
'5 F ' F ' F ' F '/ F ': F '8 F '9 F ' F '= F ' s
Tujuan
pengujian
dengan
menggunakan beberapa macam fitur teks adalah menentukan jumlah fitur teks yang mewakili sebelas fitur teks namun bisa mempertahankan akurasi tetap tinggi. Tabel 7 Perangkingan bobot Ranking
Bobot Fitur Teks
Jumlah Bobot
1
'5
49
2 3 4 5 6 7 8 9 10 11
'
39
'
30
'
28
'/
28
':
24
'8
21
'9
20
'
19
'=
16
'
1
Gambar 18 menunjukkan kinerja fitur teks terhadap akurasi. Berdasarkan Gambar 18, penggunaan dua bobot fitur teks '5 F ' pada tahap pengujian menghasilkan rata-rata akurasi sebesar 41.16%, empat bobot fitur teks '5 F ' F ' F ' menghasilkan rata-rata akurasi sebesar 46.44%, enam bobot
fitur teks '5 F ' F ' F ' F '/ F ': menghasilkan rata-rata akurasi sebesar
47.12%, delapan bobot fitur teks '5 F ' F ' F ' F '/ F ': F '8 F '9 menghasilkan rata-rata
akurasi
sebesar
47.20%,
dan
'5 F ' F ' F ' F '/ F ': F '8 F '9 F ' F '= F '
sebelas
menghasilkan
bobot
fitur
rata-rata
teks akurasi
sebesar 47.63%. Penggunaan 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
37
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. 100% 90% 80% 70%
Akurasi
60% 50% 40% 30% 20% 10% 0% 2
4
6
8
11
Jumlah Fitur Teks Gambar 18 Kinerja fitur teks terhadap akurasi. 4.8
Waktu Komputasi Analisa waktu komputasi digunakan untuk mengukur waktu komputasi
terhadap
penggunaan
jumlah
fitur teks.
diperlukan
agar menunjukkan
perbandingan waktu komputasi pemodelan algoritme genetika yang menggunakan compression rate 10%, 20% dan 30%. Penelitian ini menggunakan lima percobaan pemodelan algoritme genetika (tahap pelatihan). Perbedaan waktu running program dengan lima percobaan (tahap pelatihan) pada compression rate 10%, 20%, dan 30% dengan satuan jam. Pembentukan model kromosom dengan sebelas fitur teks pada CR 30% membutuhkan waktu
38
komputasi rata-rata 25.861 jam, CR 20% membutuhkan waktu komputasi rata-rata 13.48 jam, dan CR 10% membutuhkan waktu komputasi rata-rata 5.41 jam. Berdasarkan Gambar 19, dua bobot fitur teks '5 F ' terhadap akurasi memerlukan waktu komputasi rata-rata 256 detik, empat bobot fitur teks '5 F ' F ' F ' memerlukan waktu komputasi rata-rata 590.6 detik, enam bobot fitur teks '5 F ' F ' F ' F '/ F ': membutuhkan waktu komputasi rata-rata 671.8
detik, delapan bobot fitur teks '5 F ' F ' F ' F '/ F ': F '8 F '9 memerlukan waktu komputasi rata-rata 679.6 detik, dan sebelas bobot fitur teks
'5 F ' F ' F ' F '/ F ': F '8 F '9 F ' F '= F ' membutuhkan waktu komputasi rata-rata 683.52 detik. Selisih waktu komputasi dengan menggunakan dua fitur teks dan empat fitur teks adalah 334.6 detik, artinya terjadi kenaikan secara signifikan dengan menggunakan empat fitur teks. Kenaikan waktu komputasi tersebut disebabkan karena empat fitur teks tersebut menggunakan fitur teks tambahan yaitu kalimat semantik. Waktu komputasi untuk fitur teks “kalimat semantik” membutuhkan rata-rata 300 detik.
800 700
Waktu (detik)
600 500 400 300 200 100 2
4
6
8
Jumlah Fitur Teks Gambar 19 Jumlah fitur teks terhadap waktu akurasi.
11
39
5 KESIMPULAN DAN SARAN
5.1
Kesimpulan Dari hasil penelitian yang telah dilakukan dapat disimpulkan beberapa hal
berikut : 1.
Algoritme genetika dapat digunakan sebagai penentu bobot yang optimal pada fitur teks.
2.
Bobot pada fitur teks lima (f5) yaitu “kalimat yang menyerupai judul” sangat penting dalam peringkasan teks, dan fitur teks tiga (f3) yaitu “negative keyword” dapat diabaikan dalam peringkasan teks.
3.
Fitur teks “positive keyword (f2)”, “kemiripan antar-kalimat (f4)”, “kalimat yang menyerupai judul dokumen (f5)”, “kalimat semantik (f11)” dapat mewakili sebelas fitur teks untuk melakukan peringkasan teks.
4.
Waktu komputasi empat fitur teks (f2, f4, f5, f11) lebih singkat dibandingkan dengan waktu komputasi ekstraksi sebelas fitur teks.
5.
Semakin besar compression rate maka tingkat akurasi semakin tinggi.
6.
Penambahan satu fitur kalimat semantik dengan menggunakan SVD mampu menggantikan fitur lainnya.
5.2
Saran Beberapa saran setelah dilakukan penelitian peringkasan teks bahasa
Indonesia menggunakan algoritme genetika, yaitu: 1.
Adanya pengembangan lebih lanjut tentang penambahan fitur teks sehingga meningkatkan akurasi.
2.
Untuk mengurangi waktu komputasi pemodelan menggunakan algoritme genetika dapat menerapkan teknik komputasi paralel.
40
3.
Ringkasan manual dokumen sebaiknya dilakukan oleh pakar yang sesuai dengan topik dokumen.
4.
Perlu adanya pengembangan peringkasan teks dengan beberapa metode terbaru sehingga menjadi perbandingan antara ringkasan teks menggunakan algoritme genetika dengan metode-metode terbaru.
41
DAFTAR PUSTAKA
Barzilay R, Elhadad M. 1997. Using lexical chains for text summarization. Proceedings of Intelligent Scalable Text Summarization Workshop (ISTS’97). ACL. Baeza-Yates R, Ribeiro-Neto B. 1999. Modern information retrieval. ACM Press New York. Addison-Wesley. Barker K. 2005. Singular Value Decomposition Tutorial. http://web.ics.purdue.edu/~park283/wp-ontent/uploads/2010/10. [19 April 2010] Berry MW, Dumain ST. 1995. Using linear algreba for intelligent information retrieval. Blake C, Pratt W, Rules B, Fiturs F. 2001. A semantic approach to selecting fiturs from text. ICDM. 59–66. Cox E. 2005. Fuzzy modeling and genetic algorithm for data exploration. USA: Morgan Kauftman Publisher.
mining and
Edmundson H. 1969. New methods in automatic extracting. Journal of ACM. 16(2):264-285. Fattah MA, Ren F. 2008. Automatic text summarization. Proceeding of Word Academic of Science, Engineering and Technology. ISSN 1307-6884. Gen M, Cheng R. 1997. Genetic algorithm and engineering design. John Wiley & Sons, Inc. Canada. Gunawan AW, Achmadi SS, Arianti L. 2008. Pedoman penyajian karya ilmiah. Bogor: IPB Press. Goldberg DE. 1989. Genetic algorithms in search, optimization, and machine learning. Addison Wesley Longman, Inc. Hermanto D. 2003. Algoritma genetika dan contoh aplikasinya. http:// dennyhermanto.webhop.org [12 Maret 2010]. Hovy E, Lin C. 1997. Automatic text summarization in summarist. ACL/EACL-97 Workshop on Intelligent Scalable Text Summarization. 18-24. Jezek K, Steinberger J. 2008. Automatic text summarization (The state of the art 2007 and new challenges). Vaclav Snasel (Ed) : Znalosti. 1-12.
42
Khalessizadeh SM, Zaefarian R, Nasseri SH, Ardil E. 2006. Genetic Mining : Using genetic for topic based on Concept Distibution.World Academy of Science, Engineering and Technology 13. 144-147. Mitra M, Singhal A, dan Buckley C. 1997. Automatic text summarization by paragraph extraction. Proceedings of the ACL’97/EACL’97 Workshop on Intelligent Scalable Text Summarization. 39-46. Radev D, Hovy E, McKeown K. 2002. Introduction to the special issue on text summarization. Computer linguist. 28(4). Ridha A. 2002. Pengindeksan otomatis dengan istilah tunggal untuk dokumen berbahasa indonesia [skripsi]. Bogor. Ilmu Komputer, Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Silla CN, Pappa GL, Freitas, Kaestner CA. 2004. Automatic text summarization with genetic algorithm-based attribute selection. 9th Ibero-America Conference on AL, Lecture Notes in Computer Science. 305-314. Suyanto. 2005. Algoritme genetika dalam matlab. Penerbit ANDI. Yogyakarta. Yeh J, Ke H, Yang W, Meng I. 2005. Text summarization using a trainable summarizer and latent semantic analysis. Information Processing & Management. 41(1). 75-95.
43
LAMPIRAN
44
Lampiran 1 Model kromosom CR 30%
Percobaan model kromosom CR 30% 1
2
3
4
5
F-measure
0.427
0.427 0.416 0.429 0.424
'
0.015
0.004 0.046 0.008
0.043
0.045 0.109 0.047 0.056
' ' '
'5 ': '/ '= '9
'8 '
0
0
0
0
0.06
0
0.195
0.317 0.039 0.181 0.225
0.553
0.324
0.062
0.053 0.038 0.061
0.063
0.068 0.013 0.071 0.055
0.002
0.042 0.069 0.013 0.003
0.002
0.024 0.347 0.032 0.016
0.014 0.05
0
0.22
0.396 0.428 0.05
0.062 0.172 0.051
0.123 0.056 0.018 0.056
