RINGKASAN MULTI DOKUMEN BERBASIS ISI DENGAN

PENGKLASTER SEKUENSIAL DAN ALGORITMA GENETIKA

*Dewi Yanti Liliana, **Tiara Arinta Dewi

Program Studi llmu Komputer, Program Teknologi Informasi dan llmu Komputer, Universitas

Brawijaya, J1. Veteran Malang, Jawa Timur, 65141

E-mail: *dewi.liliana@ub.ac.id

Abstrak

Peringkasan dokumen diperlukan untuk mengekstrak intisari atau bagian penting dari keseluruhan dokumen untuk mempermudah menangkap informasi yang disampaikan pada suatu dokumen tunggal. Permasalahan yang dihadapi adalah bagaimana jika pengguna menginginkan ringkasan informasi dari berbagai dokumen (ringkasan multi dokumen). Berbagai macam dokumen tidal( dapat diringkas menjadi satu, hanya dokumen-dokumen yang memiliki kesamaan isi yang dapat menghasilkan satu ringkasan. Untuk itu sebelum diringkas, dokumen-dokumen tersebut dikelompokkan terlebih dahulu menggunakan algoritma pengklaster sekuensial. Selanjutnya peringkasan dokumen dilakukan dengan ekstraksi kalimat dan perangkingan berbasis algoritma genetika. Ekstraksi kalimat berfungsi untuk mengidentifikasi kalimat¬kalimat penting berdasarkan fitur-fitur yang ditentukan, dan dari nilai fitur tersebut kalimat akan dirangking secara optimal dengan algoritma genetika. Hasil dari ringkasan tiap dokumen dalam satu klaster digabung menjadi satu ringkasan. Penelitian ini diujikan pada beberapa klaster dokumen dengan ukuran ringkasan 25%, 50%, dan 75%. Berdasarkan pengujian yang dilakukan dihasilkan rata-rata precision 0.710491, rata-rata recall 0.70388, dan rata-rata F-measure yang merepresentasikan akurasi sistem 0.7069. Dengan akurasi yang dihasilkan maka metode yang diusulkan dapat membantu memperoleh ringkasan infomasi secara efektif.

Kata kunci: algoritma genetika, ekstraksi fitur, pengklaster sekuensial, peringkasan multi dokumen

Abstract

Document summarization is required to extract the essential part of the whole document to facilitate the capture of information presented in a single document. The problem faced is what if the user wants to summarize from the various documents (multi-document summarization). Various kinds of documents cannot be condensed into one, only documents that have similar content can generate a summary. For that reason before summarized, these documents are grouped first using sequential clustering algorithms. Furthermore document summarization is done by sentence extraction and ranked-based genetic algorithms. Sentence extraction serves to identib, important sentences based on determined features, and the value of those features will rank sentences optimally with genetic algorithms. The result of a summary of each document in the cluster is combined into a single summary. This study tested on several clustering documents with a summary measure of 25%, 50%, and 75%. Based on tests performed its yield 0.710491 average precision, average recall 0.70388, and the average F-measure system accuracy representing 0.7069. With the resulting accuracy of the proposed method can help to obtain an information summary effectively.

Key words: genetic algorithms, feature extraction, sequential clustering, multi documents summarization

PENDAHULUAN

Perkembangan informasi online menjadi media yang semakin penting untuk menemukan dan merepresentasikan informasi tekstual. Mengingat dokumen teks sekarang ini begitu banyak, maka diperlukan suatu cara yang mudah untuk mendapatkan informasi yang dibutuhkan. Salah satu cara yang dapat ditempuh adalah dengan meringkas dokumen [1].

Tersedianya sumber informasi yang tidak terbatas mengakibatkan perolehan sumber informasi dan pertukaran data berupa teks melibatkan banyak sumber informasi sehingga memicu penelitian mengenai metode peringkasan dokumen yang semula ditujukan untuk membuat sebuah ringkasan dari dokumen tunggal menjadi metode peringkasan multi dokumen [2].

Dokumen-dokumen yang akan diringkas menjadi satu hams memiliki keterkaitan topik atau isi [3, 4]. Untuk itu, sebelum diringkas dokumen-dokumen tersebut dikelompokkan terlebih dahulu sesuai kesamaan konten, dalam penelitian ini menggunakan Pengklaster sekuensial. Kemudian, dokumen diekstrak menggunakan enam fitur [3]. Hasil dari ekstraksi kalimat akan dirangking untuk

menentukan       kalimat-kalimat  penting.

Perangkingan kalimat dilakukan dengan pendekatan algoritma genetika. Algoritma genetika dapat bekerja secara optimal untuk mengolah keenam nilai tersebut agar menjadi satu nilai tunggal dimana semua nilai fitur dapat terpenuhi bersamaan. Dengan nilai tunggal yang dihasilkan, kalimat dapat diurutkan dari yang paling besar nilainya. Nilai mengindikasikan tingkat kepentingan kalimat. Dengan adanya ringkasan, diharapkan pengguna dapat dengan mudah memahami makna sebuah teks tanpa hams membaca keseluruhan teks.

DESAIN SISTEM

Sistem akan menerima input beberapa dokumen berbahasa Inggris dari user kemudian dokumen-dokumen tersebut akan diproses melalui beberapa tahapan untuk menghasilkan ringkasan yang merupakan intisari dari dokumen-dokumen masukan.

Pertama, sistem akan melakukan preprocessing terhadap dokumen-dokumen masukan. Sebelum diringkas dokumen¬dokumen masukan tersebut akan

dikelompokkan  terlebih dahulu.

Pengelompokkan dokumen dilakukan berdasarkan kesamaan konten yang dimiliki karena hanya dokumen yang memiliki banyak kesamaan konten yang dapat diringkas menjadi satu [2]. Pengelompokkan dilakukan menggunakan metode pengklaster sekuensial.

Selanjutnya, peringkasan untuk masing-masing dokumen dilakukan dalam dua bagian yaitu ekstraksi kalimat dan perangkingan kalimat berbasis algoritma genetika. Hasil dari ringkasan tiap dokumen akan digabung. Proses penggabungan dilakukan terhadap ringkasan suatu dokumen dengan ringkasan dokumen lain dalam satu klaster, sehingga dihasilkan teks ringkasan gabungan untuk multi dokumen. Dokumen-dokumen yang berada dalam satu klaster akan menghasilkan sebuah ringkasan, jadi jumlah ringkasan sama dengan jumlah klaster. Hasil ringkasan multi dokumen akan dievaluasi menggunakan tiga parameter yaitu precision, recall, dan F-measure [6].

A. Pengklaster sekuensial

Perhitungan pengklaster sekuensial menggunakan nilai TF.1DF yang telah dinormalisasi dan cosine similarity. TF.1DF adalah perkalian antara term frequency dengan inverse document frequency. Variabel TF merupakan jumlah suatu term/kata dalam suatu dokumen, sedangkan 1DF merupakan invers document frequency dari sebuah term/kata. Dengan menggunakan bobot TF-1DF, sebuah dokumen dapat dimodelkan

sebagai sebuah vektor. Dokumen               dapat dimodelkan atas komponen Ti sehingga jika seluruh dokumen dikumpulkan maka akan terbentuk matriks term-dokumen dengan bobot term/TF-IDF sebagai nilainya.

Tahapan proses pengklaster sebagai betikut :

1.            Masukan dari proses ini adalah

kumpulan dokumen hasil praproses.

2.            Inisialisasi nilai threshold kemiripan = 0.085 (pengesetan awal berasal dari ujicoba) dan Smax = 0.

3.            Untuk setiap dokumen dilakukan perhitungan kemitipan dengan dokumen yang telah terklaster.

4.            Sebelum dilakukan perhitungan kemitipan, dilakukan pengecekan pada klaster ke-1. Jika klaster ke-1 kosong maka dokumen ke-i langsung dimasukkan pada klaster 1 .

5.            Nilai Smax dihitung dari maksimum nilai kemiripan dokumen ke-i dengan dokumen lain yang sudah terklaster.

6.            Jika nilai Smax lebih besar daripada nilai threshold maka dokumen ke-i dimasukkan pada klaster yang bersesuaian.

7.            Jika nilai Smax lebih besar daripada nilai threshold maka dokumen ke-i dimasukkan pada klaster yang bersesuain.

8.            Jika nilai Smax kurang dan threshold maka dokumen dimasukkan pada klaster ban'.

9.            Dilakukan sampai semua dokumen terklaster

B. Ekstraksi Kalimat

Sebelum melakukan ekstraksi kalimat, dokumen dipecah menjadi tiap kalimat. Setiap kalimat dan dokumen tersebut akan diekstraksi sehingga memiliki nilai yang mewakili kalimat tersebut. Ada enam fitur untuk setiap kalimat. Setiap fitur diberi nilai antara '0 'dan '1'. Enam fitur tersebut sebagai berikut:

1.            Fitur Panjang Kalimat (F1)

Fitur ini berfungsi untuk menyaring kalimat pendek seperti nama pengarang dan datelines seperti pada artikel berita. Kalimat pendek tidak dipakai untuk ringkasan dokumen. Perhitungan fitur ini ditunjukkan dengan persamaan 1:

jumlah kata pada suatu kalimat

(1)

Fl = jumlah kata pada kalimat terpanjang

2.            Fitur Pembobotan Kata/Term Weight (F2) Nilai suatu kalimat dapat dihitung sebagai jumlah nilai bobot kata dalam kalimat tersebut. Di sini akan dilakukan penghitungan menggunakan persamaan TF.IFS dan kata ke¬k sampai ke-n untuk kalimat(S) dan x sampai y. TS.ISF adalah perkalian antara term frequency dengan inverse sentence frequency. Ide dasar dan penilaian TF.ISF adalah mengevaluasi setiap kata dalam distribusinya pada seluruh kalimat di dokumen. Jadi nilai TF.ISF ditentukan untuk mengevaluasi pentingnya sebuah kata dalam dokumen bedasarkan frekuensinya dalam sebuah kalimat dan distribusinya di seluruh kalimat dalam dokumen.

Perhitungan fitur ini ditunjukkan dengan persamaan berikut:

o (s)

F2 =        k             (2)

Max (Elk'=1 ok (sr))

3. Fitur Kemiripan Kalimat (F3)

Fitur ini merupakan kesamaan antar kalimat. Untuk tiap kalimat S, kemitipan antara S dan tiap kalimat lain dihitung menggunakan cosine similarity Bobot kata TS.ISF; dan TS.ISFj dari kata t sampai n pada kalimat Si dan Si direpresentasikan oleh vektor. Kemiripan tiap kalimat ditunjukkan oleh persamaan berikut :

4.            Fitur Proper noun (F4)

Kalimat yang mengandung proper noun termasuk kalimat penting yang biasanya masuk dalam ringkasan. Proper noun adalah kata yang menunjukkan nama sesuatu, seperti nama orang, nama tempat, nama bulan, dan sebagainya. Berikut ini persamaan untuk menghitung nilai proper noun :

F4jumlah proper noun pada kalimat S 14) = panjang kalimat/jumlah kata S

5.            Fitur Thematic word (F5)

Thematic word yang dimaksud adalah kata yang frekuensinya tinggi pada suatu dokumen. Fitur ini penting karena berhubungan dengan topik. Pada penelitian ini diasumsikan Thematic word atau kata tematik adalah kata yang frekuensinya lebih dari satu, untuk

mengantisipasi   dokumen             pendek.

Persamaannya ditunjukkan oleh persamaan berikut :

F5 =

jumlah thematic word pada kalimat S

Max jumlah thematic word pada suatu kalimat

(5)

6. Fitur Numerical data (F6)

Kalimat yang mengandung data numerik dianggap kalimat penting dan biasanya masuk dalam ringkasan. Nilai dari fitur ini dihitung dengan persamaan berikut :

jumlah data numerik pada kalimat S

F6 =        (6)

panjang kalimat S

C. Perangkingan Berbasis Algoritma

Genetika

Berikut ini penjelasan langkah-langkah perangkingan berbasis Algoritma Genetika (AG):

1.            Pembangkitan Populasi Awal dan Representasi Kromosom

Pada      penelitian            ini           kromosom

merepresentasikan fitur-fitur yang ada. Satu individu terdiri dari enam kromosom sesuai dengan jumlah fitur. Tiap kromosom terdiri dari sejumlah gen sesuai dengan persamaan berikut [5] :

Li= [ 2log[(b — a)102 + 1]1            (7)

dengan b = batas atas interval dan a = batas bawah interval.

Maka jumlah gen untuk tiap kromosom sebagai berikut:

Li= [ 2log[(1 — 0)102 + 1]1

(8)

= [ 21og[101]= 7

Dengan demikian ukuran gen untuk tiap individu dengan enam kromosom (enam fitur) =7 x 6 = 42.

2.            Crossover Satu Titik

Proses crossover tergantung pada suatu parameter yaitu probabilitas crossover (Pc). Misalkan probabilitas crossover adalah 0.8, artinya diharapkan 80% individu yang akan mengalami crossover.

3.            Mutasi Biner

Sama dengan pengkodeannya, mutasi yang digunakan adalah mutasi biner. Mutasi biner yaitu mengubah nilai 1 menjadi 0 dan sebaliknya, 0 jadi 1. Proses mutasi tergantung pada probabilitas mutasi (Pm). Misalkan probabilitas mutasi 0.01, artinya diharapkan 1% dari total gen mengalami mutasi.

4.            Perhitungan Nilai Fitness dan Seleksi

Seleksi yang digunakan pada penelitian ini adalah seleksi Rank-Based fitness. Seleksi dilakukan dengan mengurutkan individu sesuai nilai fitnessnya kemudian mengambil individu-individu teratas. Seluruh individu, yaitu individu awal, anakan hasil crossover, dan anakan hasil mutasi dihitung nilai fitnessnya kemudian diurutkan mulai dari yang

terbesar sesuai nilai fitness dan diambil yang tertinggi sebanyak ukuran populasi / jumlah individu awal. Fungsi fitness didapatkan dari persamaan objektif Fan. Persamaan objektif Fan merupakan persamaan minimum sehingga fungsi fitness dihitung dari invers persamaan objektif Fan. Persamaan fungsi fitness ditunjukkan pada persamaan berikut:

Fitness =              (9)

m ,

               ETi( 1     2 max    bj —by) n

Nilai w? dihitung dari nilai wi yang telah didapat pada tahap sebelumnya. Nilai max br merupakan nilai maksimum fitur ke-j pada semua kalimat.

Untuk menghitung nilai W digunakan persamaan berikut :

x

=             .              (10)

x total

Dimana j = 1,2,...,n (n adalah jumlah kromosom tiap individu). Untuk menghitung nilai x yang merupakan variabel temporer dengan persamaan berikut:

xi = a+ Rb —a)1(214 — 1)] x vi

(11)

dengan a = batas bawah interval data, pada kasus ini adalah 0; b = batas atas interval data, pada kasus ini adalah 1; Lj = panjang gen ke-j Kemudian dihitung x total untuk tiap individu (pada kasus ini sepanjang 6 kromosom).

5.            Merangking kalimat

Setelah diketahui individu mana yang memiliki nilai fitness tertinggi, individu tersebut dij adikan sebagai solusi terbaik. Untuk mendapatkan urutan rangking, nilai bobot dari individu yang tepilih sebagai solusi terbaik, digunakan untuk menghitung nilai altematif ke-i sebagai nilai kalimat ke-i dengan persamaan berikut [5]:

gt= E7=1Wi it

(12)

D. Penggabungan Ringkasan tiap Master

Penggabungan merupakan proses untuk menggabungkan hasil ringkasan masing-masing dokumen yang ada dalam satu klaster. Hasil ringkasan digabungkan menggunakan perhitungan cosine similarity dengan TF (Term Frequency). TF adalah frekuensi kata pada suatu kalimat. Perhitungan cosine

similarity dengan TF seperti ditunjukkan pada persamaan berikut:

~ ~

,∑k=1 7&k × ,∑ 7)

~~~

dengan 7&k jumlah kata k pada kalimat I; 7)k jumlah kata k pada kalimat j.

METODE EVALUASI

Proses evaluasi hasil text summarization dilakukan menggunakan tiga parameter yaitu precision, recall, dan F-measure [6]. Sebuah sistem informasi dikatakan baik jika tingkat precision, recall, dan F-measurenya tinggi. Cara mengevaluasinya yaitu membandingkan ringkasan otomatis hasil sistem dengan ringkasan manual.

1.            Precision

Precision merupakan perbandingan jumlah informasi relevan yang didapatkan sistem dengan jumlah seluruh informasi yang terambil oleh sistem baik yang relevan maupun tidak. Persamaan precision ditunjukkan pada persamaan berikut :

P =          ;4335;7 (14)

(;4335;7R<34n8)

2.            Recall

Recall merupakan perbandingan jumlah informasi relevan yang didapatkan sistem dengan jumlah seluruh informasi relevan yang ada dalam koleksi informasi (baik yang terambil atau tidak terambil oleh sistem). Persamaan recall ditunjukkan pada persamaan berikut:

Keterangan:

correct : jumlah kalimat yang diekstrak oleh sistem dan manusia.

wrong : jumlah kalimat yang diekstrak oleh sistem tetapi tidak diekstrak oleh manusia. missed : jumlah kalimat yang diekstrak oleh manusia tetapi tidak diekstrak oleh sistem.

3.            F-Measure

F-Measure merupakan hubungan antara recall dan precision yang merepresentasikan akurasi sistem. Persamaan F-Measure seperti pada persamaan berikut:

F = ~∗T∗U (TRU) (16)

HASIL UJI COBA

Pengujian dilakukan untuk mengetahui seberapa dekat hasil ringkasan sistem dengan hasil ringkasan manual. Perhitungan terhadap tiga parameter yang berbeda yaitu precision, recall, dan F-measure dilakukan untuk ukuran ringkasan dokumen yang berbeda, yaitu 25%, 50%, dan 75%. Setelah dilakukan pengujian akan diketahui kemampuan sistem dalam menghasilkan informasi yang relevan yang diinginkan user.

Dari 9 dokumen yang dimasukkan terbagi menjadi 4 klaster. Hasil percobaan untuk semua ukuran ringkasan dengan parameter algoritma genetika jumlah individu = 20, maksimum generasi = 50, probabilitas crossover = 0.8, dan probabilitas mutasi 0.01 ditunjukkan pada gambar 1, 2, dan 3.

Gambar 1. Grafik Nilai Precision

Pada Gambar 1 nilai precision terendah dihasilkan oleh klaster 1 dengan ukuran ringkasan 25%. Nilai precision tertinggi dihasilkan klaster 2 dengan ukuran ringkasan 75%.

Gambar 2. Grafik Nilai Recall

Pada gambar 2 nilai recall terendah dihasilkan oleh klaster 1 dengan ukuran ringkasan 25% sedangkan nilai recall tertinggi dihasilkan oleh klaster 2 dengan ukuran ringkasan 75%.

Gambar 3. Grafik Nilai F-measure

Pada gambar 3 nilai F-measure terendah dihasilkan oleh klaster 1 dengan ukuran ringkasan 25%, sedangkan nilai tertinggi dihasilkan oleh klaster 2 dengan ukuran ringkasan 75%. Untuk ukuran ringkasan 25% didapatkan rata-rata nilai F-measure 0.5878, ukuran ringkasan 50% didapatkan rata-rata nilai F-measure 0.6891, dan untuk ukuran ringkasan 75% rata-rata nilai F-measure sebesar 0.8438.

Di sini terlihat nilai F-measure semakin naik untuk ukuran ringkasan yang semakin besar

pula.      Rata-rata             nilai        F-measure

merepresentasikan akurasi sistem ini, yaitu 0.7069.

KESIMPULAN

Penelitian ini telah menghasilkan sistem peringkasan multi dokumen berbahasa Inggris berbasis isi menggunakan pengklaster sekuensial dan perangkingan berbasis algoritma genetika. Berdasarkan evaluasi

sistem   yang      dilakukan             dengan

membandingkan hasil ringkasan sistem dan

ringkasan manual diperoleh nilai F-measure tertinggi untuk ukuran ringkasan 75% yaitu sebesar 0.8438, sedangkan nilai F-measure untuk ukuran ringkasan 25% dan 50% yaitu sebesar 0.5878 dan 0.6891. Jadi semakin besar ukuran ringkasan semakin tinggi nilai F-measure atau akurasinya. Rata-rata nilai F-measure untuk semua ukuran ringkasan yang merepresentasikan akurasi sistem yaitu sebesar 0.7069.

PUSTAKA

[1]          Fattah, M. A. dan Ren, Fuji. Automatic Text Summarization. World Academy of Science, Engineering and Technology. Singapore. 2008

[2]          Hariharan, S. Extraction Based Multi Document Summarization using Single Document Summary Cluster. B.S. Abdur Rahman University. Vandalur. 2010

[3]          Kogilavani, A., dan Balasubramani, P. Clustering Feature Specific Sentence Extraction Based Summarization of Multiple Documents. Kongu Engineering College. Erode. 2010

[4]          Kuo, J. dan Chen, H. Cross-document Event Clustering Using Knowledge Mining From Co-reference Chains. National Taiwan University. Taipei. 2006.

[5]          Kusumadewi, Sri. Pencarian Bobot Atribut Pada Multiple Attribute Decision Making (MADM) dengan Pendekatan Obyektif Menggunakan Algoritma Genetika. Gematika Jurnal Manajemen Informatika. Jakarta. 2005

[6]          Nedunchelian, R., Muthucumarasamy, R., dan Saranathan, E. Comparison Of Multi Document Summarization Techniques. IJCSNS (International Journal of Computer Science and Network Security). 2011