Nusantara Journal of Computers and its Applications Volume 2 – No.7, Desember 2016
STRATEGI PEMILIHAN KALIMAT PADA PERINGKASAN MULTI DOKUMEN Satrio Verdianto, Agus Zainal Arifin, dan Diana Purwitasari Jurusan Teknik Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember (ITS) ABSTRAK
Ringkasan berita diartikan sebagai teks yang dihasilkan dari satu atau lebih kalimat yang menyampaikan informasi penting dari berita. Salah satu fase penting dalam peringkasan adalah pembobotan kalimat (sentence scoring). Dimana pada peringkasan berita, metode pembobotannya sebagian besar menggunakan fitur dari berita sendiri. Berdasarkan hasil dari penelitian [3] bahwa untuk pembobotan kalimat pada dokumen yang memiliki karakter teks pendek dan terstruktur seperti berita maka teknik pembobotan kalimat terbaik adalah dengan menggunakan kombinasi dari keempat fitur yaitu word frequency, TF-IDF, posisi kalimat, dan kemiripan kalimat terhadap judul (Resemblance to the title ). Pada penelitian ini kombinasi keempat fitur tersebut dibandingkan dengan kombinasi tiga fitur dan dua fitur dan dievaluasi menggunakan nilai ROUGE-N dan dievaluasi berdasarkan lama waktu eksekusi. Berdasarkan hasil uji coba didapatkan hasil bahwa yang paling optimal diantara keempat kombinasi fitur tersebut adalah kombinasi antara dua buah fitur yakni fitur posisi kalimat dan word frequency dengan nilai ROUGE-N sebesar 0.679 dan lama waktu eksekusi 28.458 detik. Kata Kunci : kemiripan kalimat terhadap judul, pembobotan kalimat, posisi kalimat, ROUGE-N, TF-IDF, word frequency ABSTRACT
News Briefs interpreted as a text resulting from one or more sentences that convey important information from news. One important phase in peringkasan is weighting sentence (sentence scoring). Where in peringkasan news, the weighting method mostly using the features of the news itself. Based on the results of the study [3] that for weighting sentences in documents that have character short text and structured as news, the technique of weighting sentence is best to use a combination of all four features that word frequency, TF-IDF, the position of the sentence, and the similarity of the sentence against title (Resemblance to the title). In this study, the combination of all four of these features compared to the combination of three features and two features and evaluated using a value ROUGE-N and evaluated based on the length of time of execution. Based on trial results showed that among the four most optimal combination of these features is the combination of two features of the feature position of the sentence and word frequency values ROUGE-N of 0679 and 28 458 seconds long execution time. Keywords: similarity sentence against title, the weighting sentence, sentence position, ROUGE-N, TF-IDF, word frequency
I. PENDAHULUAN
K
EBUTUHAN untuk mengakses informasi khususnya berita secara praktis menjadi masalah yang harus diselesaikan seiring berkembang-pesatnya berita yang dapat diakses secara online. Peringkasan berita secara otomatis adalah salah satu solusi untuk menjawab permasalahan diatas. Ringkasan berita dapat diartikan sebagai sebuah teks yang dihasilkan dari satu atau lebih kalimat yang mampu menyampaikan informasi penting dari sebuah berita. Dimana panjang dari sebuah ringkasan tidak lebih dari setengah panjang dokumen asli, dan biasanya lebih pendek [7]. Peringkasan multi dokumen berita merupakan sistem peringkasan yang melibatkan lebih dari satu berita sebagai input.
Selain itu, dibutuhkan teknik pembobotan kalimat yang handal untuk dapat menghasilkan ringkasan berita yang baik. Berdasarkan hasil dari penelitian [3] bahwa untuk pembobotan kalimat pada dokumen yang memiliki karakter teks pendek dan terstruktur seperti berita maka teknik pembobotan kalimat terbaik adalah dengan menggunakan kombinasi dari keempat fitur yaitu word frequency, TF-IDF, posisi, dan Resemblance to the title.
1
Nusantara Journal of Computers and its Applications Volume 2 – No.7, Desember 2016
B. TF-IDF Term Frequency Inverse Document Frequency (TF-IDF) adalah konsep pembobotan term pada sebuah dokumen. Ketika TF-IDF diterapkan pada lingkup kalimat, maka sebuah kalimat akan diberlakukan sebagai dokumen. Konsep dari TF-IDF adalah jika ada “kata-kata yang spesifik” muncul pada kalimat tertentu maka kalimat tersebut relatif dianggap sebagai kalimat penting [2]. Metode ini melakukan perbandingan antara frekuensi kemunculan term j pada kalimat i ( dengan frekuensi kalimat yang mengandung term j (
. Bobot TF-
IDF dari term j dapat dihitung dengan menggunakan persamaan 1, dimana tf wi docj adalah frekuensi kata w ke-i
Gambar 1. Diagram alir proses sistem secara umum
Sebelum memasuki proses pembobotan, koleksi dokumen berita melalui fase praproses data. Fase praproses data meliputi proses xml parsing, tokenizing, stopword removal, dan stemming. XML parsing adalah proses pengubahan data .xml ke bentuk string atau teks. Tokenizing adalah proses pemenggalan kata-kata sehingga setiap kata dapat berdiri sendiri. Stopword removal adalah proses menghapus kata kunci yang tidak layak untuk digunakan, seperti kata sambung, kata depan, kata ganti dls. Sedangkan stemming adalah proses untuk memperoleh kata dasar dari setiap kata. Dalam tugas akhir ini stemming dilakukan dengan memanfaatkan kategloDB. Proses stemming dilakukan dengan mengubah setiap kata ke bentuk dasarnya dengan merujuk ke kategloDB. Data hasil praproses disimpan ke dalam database. II. TINJAUAN PUSTAKA A. Word Frequency Konsep dari Word Frequency (WF) adalah semakin sering suatu kata muncul dalam sebuah teks maka kata tersebut dianggap sebagai kata penting [3]. Sehingga untuk mendapatkan kata-kata penting dari sebuah dokumen dilakukan pembobotan kata dengan menghitung frekuensi kemunculan kata tersebut pada dokumen. Semakin besar frekuensi kemunculan sebuah kata maka skornya akan semakin tinggi. Langkah awal yang dilakukan adalah ekstraksi term dari dokumen kemudian memberikan bobot pada tiap term tersebut berdasarkan jumlah kemunculan term pada dokumen. Kemudian meranking term berdasarkan bobot dan menyeleksi term yang memiliki bobot diatas nilai ambang (threshold). Term yang terseleksi akan menjadi Word Frequency List (WFList). WFList inilah yang nantinya digunakan sebagai fitur pada pembobotan kalimat dengan cara mengukur kemiripan antara kalimat terhadap WFList. Metode untuk mengukur kemiripan dapat menggunakan cosine similarity atau metode pengukur kemiripan yang lain.
pada dokumen ke-j. Konsep tersebut memberikan pengukuran terhadap pentingnya kata w ke-i pada dokumen tersebut. Sedangkan idf wi ditentukan melalui Persamaan 2, dimana N adalah jumlah dokumen, df wi adalah jumlah dari dokumen yang mengandung kata w ke-i.
tf_idf widocj tf widocj idf wi
idf wi log(
N ) df wi
(1) (2)
C. Posisi Kalimat Posisi kalimat merupakan salah satu fitur yang dapat digunakan untuk pembobotan kalimat. Dimana penilaiannya berdasarkan pada letak kalimat dalam sebuah dokumen. Sama seperti penelitian [10] yang menggunakan posisi sebagai salah fitur pembobotan kalimat. Dengan menggunakan aturan, kalimat yang posisinya berada diawal dokumen memiliki skor lebih besar dibanding kalimat yang posisinya diakhir. Penelitian tersebut mampu memberikan penjelasan ilmiah tentang alasan penggunaan aturan tersebut untuk pembobotan kalimat dengan mengutip pernyataan dari Baxendale bahwa kebanyakan kalimat yang muncul diawal paragraf merupakan topic sentence. Hal inilah yang menjadi dasar Jiang-ping (2012) untuk memberikan skor lebih besar pada kalimat yang muncul di awal dokumen. Namun sebenarnya, topic sentence kurang tepat digunakan sebagai alasan dikarenakan topic sentence berlaku untuk semua jenis tulisan termasuk berita online. Dan topic sentence bisa saja muncul disemua posisi dokumen, baik di awal, tengah, maupun akhir. Dalam ilmu jurnalistik, ada beberapa teknik penulisan berita. Teknik yang paling banyak digunakan untuk berita online adalah “piramida terbalik”. Pola “piramida terbalik” merupakan teknik penulisan berita yang dimulai atau diawali dari kalimat yang dianggap paling penting, setelah itu diikuti hal-hal yang kurang penting. Penelitian ini meyakini bahwa alasan ini merupakan alasan yang tepat untuk memberikan skor lebih besar pada kalimat yang ada di posisi awal dibanding dengan penggunaan alasan topic sentence.
2
Nusantara Journal of Computers and its Applications Volume 2 – No.7, Desember 2016
D. Kemiripan Kalimat dengan Judul Berita Judul berita merupakan satu komponen penting dalam penulisan berita. Dalam berita online, judul ditulis secara ringkas dan jelas. Sebuah judul minimal mengandung unsur SP-O-K (Subyek – Predikat – Obyek – Keterangan) dan dapat diambil dari beberapa kata atau kutipan yang ada dalam isi berita. Hal inilah yang menjadi dasar penggunaan judul sebagai informasi untuk mengetahui kalimat penting dalam sebuah berita. Konsep dari teknik pembobotan kalimat berdasarkan kemiripan kalimat terhadap judul adalah bahwa bobot sebuah kalimat besar ketika nilai kemiripan antara judul dengan kalimat tinggi. Semakin besar bobot kalimat maka kalimat tersebut akan dianggap semakin penting. Hal ini sama seperti yang ada pada penelitian [2] bahwa kalimat yang mirip dengan judul dan kalimat yang mencakup kata-kata dalam judul yang akan dianggap sebagai kalimat penting. III. PEMBOBOTAN KALIMAT DAN PEMILIHAN KALIMAT SEBAGAI RINGKASAN A. Pembobotan Kalimat Fase pembobotan kalimat merupakan proses perhitungan empat buah fitur untuk tiap kalimat. Keempat buah fitur tersebut ialah fitur posisi kalimat, fitur word frequency, fitur TF-IDF, dan fitur kemiripan kalimat dengan judul. Konsep dari pembobotan kalimat yang pertama adalah dengan menggunakan WF. Dalam hal ini WFList didapatkan dari sejumlah term dengan nilai WF memenuhi nilai ambang (threshold), WFList = { . Pembobotan kalimat dihitung berdasarkan nilai kemiripan antara kalimat terhadap WFList, persamaan 3. Dalam penelitian ini digunakan cosine similarity untuk mengukur kemiripan antara kalimat dengan WFList, Bobot kalimat berdasarkan WF untuk selanjutnya disebut dengan , dengan S adalah kalimat. Sehingga adalah nilai kemiripan kalimat terhadap WFList, dimana S={ . Pembobotan kalimat kedua ( ) pada penelitian ini menggunakan pendekatan TF-IDF. Setelah didapatkan bobot tiap term dengan menggunakan persamaan 1, langkah selanjutnya adalah menghitung bobot kalimat berdasarkan bobot TF-IDF yang selanjutnya disebut dengan menggunakan persamaan 4. merupakan hasil penjumlahan dari seluruh bobot term j yang muncul pada kalimat i ( Pembobotan kalimat ketiga ( ) menggunakan fitur posisi. dihitung dengan menggunakan persamaan 5 yang mengadopsi dari penelitian (Mei & Chen, 2012). Dengan aturan, kalimat yang posisinya berada diawal dokumen memiliki skor lebih besar dibanding kalimat yang posisinya diakhir. Pembobotan kalimat keempat ( ) melibatkan judul berita (Title). Penghitungan menggunakan persamaan 6 yang mengadopsi dari [2] yaitu dengan cara membagi antara jumlah term judul yang muncul pada kalimat (Ntw) dengan jumlah seluruh term yang ada pada judul (T).
(3) (4) (5) (6) Setelah didapatkan bobot sampai langkah berikutnya adalah menghitung total bobot kalimat i dengan menggunakan persamaan 7. Bobot kalimat yang didapat berdasarkan sampai seluruhnya dijumlahkan. Seluruh kalimat akan dihitung bobotnya, hasil dari persamaan 7 inilah yang akan menjadi total bobot kalimat i.
score( ) =
+
( )+ ( )+ ( )
(7)
B. Pemilihan Kalimat sebagai Ringkasan Fase pemilihan kalimat dan penyusunan ringkasan dilakukan dengan melakukan pengurutan bobot kalimat secara descending (terbesar ke terkecil). Kemudian beberapa kalimat dengan bobot terbesar diambil sebagai ringkasan. IV. UJI COBA DAN EVALUASI Uji coba dilakukan dengan mengukur performa hasil ringkasan dengan menggunakan kombinasi empat fitur berita yaitu posisi kalimat (p), word frequency (w), TF-IDF (t), dan judul berita (j). Nantinya kombinasi 4 fitur akan dibandingkan dengan kombinasi 3 fitur dan kombinasi 2 fitur. Untuk mengukur performansi hasil ringkasan digunakan metode evaluasi ROUGE-N yaitu ROUGE-1 dan evaluasi berdasarkan waktu eksekusi. A. Dataset Pengujian pada sistem peringkasan dalam penelitian ini dilakukan dengan membandingkan hasil ringkasan sistem dengan hasil ringkasan manusia dengan menggunakan ROUGE-N. Pengujian dilakukan terhadap 15 kelompok dokumen berita berformat .xml yang dikelompokkan berdasarkan topik dimana masing-masing kelompok memiliki jumlah dokumen berita yang dijelaskan pada Tabel 1. Ringkasan yang dihasilkan terdiri dari 10 buah kalimat untuk masing-masing topik. Tabel 1. Dataset berita
NO 1 2 3 4 5 6 7 8 9 10 11
TOPIK BERITA BLBI LG G4 Kunjungan Mark Zuckerberg Internet Indonesia lambat Intel Prosesor baru Intel Smartphone 4G Intel Kunjungan Jokowi Pidato Presiden dan pemberian penghargaan Saran SBY Proyek LRT
JUMLAH BERITA 4 3 4 2 3 3 3 2 3 3 3
3
Nusantara Journal of Computers and its Applications Volume 2 – No.7, Desember 2016 12 13 14 15 TOT AL
Jokowi ke Arab Saudi Jokowi ancam copot menteri Iklan Jokowi Unikom dan UPI di LIMA Badminton 45
2 2 5 3
B. Evaluasi berdasarkan Nilai ROUGE-1 Dari Tabel 2 dapat dilihat bahwa kombinasi empat fitur yakni posisi kalimat (p), word frequency (w), TF-IDF (t), dan judul berita (j) memiliki total nilai ROUGE-1 terbesar kedua setelah kombinasi tiga fitur yakni posisi kalimat, word frequency, dan TF-IDF. Perbedaan ditunjukkan pada dataset ringkasan ke-4 yang disebabkan oleh struktur xml yang kurang tepat sehingga mengakibatkan sistem dengan kombinasi pwtj mengambil kalimat yang bukan bagian dari berita, yakni kalimat “Baca juga:….” Tabel 2. Nilai ROUGE-1 antara ringkasan sistem (kombinasi 2, 3, dan 4 fitur) dengan ringkasan groundtruth
Dari Tabel 3 dapat dilihat bahwa urutan rata-rata waktu eksekusi seluruh kombinasi terhadap 15 topik berita dari yang tercepat hingga yang terlambat ialah sebagai berikut. 1. pj 2. wj 3. pw 4. pwj 5. pt 6. tj 7. wt 8. wtj 9. pwt 10. pwtj 11. ptj Pengukuran berdasarkan waktu eksekusi saja tentunya tidak dapat dijadikan landasan mutlak untuk mengukur performa suatu metode. Maka dari itu, untuk mengetahui kombinasi yang paling optimal untuk digunakan dalam proses pemilihan kalimat, analisis berdasarkan waktu eksekusi akan dipadukan dengan analisis berdasarkan nilai ROUGE-1.
Selanjutnya posisi ketiga adalah kombinasi dua fitur yakni posisi kalimat dan word frequency. Perbedaan nilai ROUGE-1 diantara ketiganya pun dapat dikatakan sangat kecil yakni sekitar 0.01. Hal ini menunjukkan bahwa kombinasi empat fitur bukanlah yang terbaik dalam menghasilkan ringkasan yang baik. Selain itu, hasil ini juga menunjukkan bahwa fitur posisi kalimat dan word frequency mengambil peranan penting dalam menghasilkan ringkasan yang baik. Sebaliknya fitur kemiripan dengan judul berita tidak peranan penting karena dengan atau tanpa fitur tersebut nilai ROUGE-1 tidak menunjukkan perbedaan yakni antara pwtj dan pwt. Bahkan pada kombinasi tiga fitur dan dua fitur dapat dilihat bahwa penggunaan fitur tersebut menghasilkan nilai ROUGE-1 yang lebih kecil dibandingkan menggunakan fitur lain.
D. Analisis Tabel 4 menunjukkan urutan kombinasi berdasarkan nilai ROUGE-1 dan waktu eksekusi. Nilai ROUGE-1 diurutkan secara descending (terbesar - terkecil) sedangkan waktu eksekusi diurutkan secara ascending (tercepat – terlambat).
Tabel 4. Urutan kombinasi berdasarkan ROUGE-1 dan waktu eksekusi
C. Evaluasi berdasarkan Waktu Eksekusi Selain itu, uji coba juga dilakukan dengan mengukur waktu eksekusi masing-masing kombinasi untuk seluruh berita. Tabel 3. Lama waktu eksekusi program (dalam satuan detik) tiap kombinasi fitur untuk tiap topik berita
4
Nusantara Journal of Computers and its Applications Volume 2 – No.7, Desember 2016
adalah kombinasi fitur posisi kalimat dan word frequency dengan nilai ROUGE-1 sebesar 0.679 dan lama waktu eksekusi 28.458 detik. B. Saran Adapun saran untuk pengembangan lebih lanjut dari proses peringkasan multi-dokumen dalam Tugas Akhir ini ialah dilakukan pengembangan lebih lanjut agar tingkat akurasi yang dihasilkan bisa lebih baik yaitu dengan cara mencari tahu nilai parameter-parameter yang optimal contohnya parameter threshold jumlah kata yang dimasukkan ke dalam WFList. DAFTAR PUSTAKA Dari tabel tersebut dapat diambil disimpulkan bahwa kombinasi dua fitur yakni posisi kalimat dan word frequency merupakan kombinasi yang optimal untuk mendapatkan ringkasan yang baik dengan waktu yang cukup cepat. Kombinasi dua fitur yakni posisi kalimat dan word frequency merupakan kombinasi yang optimal disebabkan oleh hal-hal berikut. 1. Sebagian besar berita cenderung menyampaikan ide pokoknya pada awal-awal kalimat sedangkan kalimatkalimat selanjutnya merupakan penjelas atau bahkan informasi-informasi lain di luar pokok bahasan. Sehingga dengan menggunakan fitur posisi kalimat, kita dapat mengambil intisari dari berita tersebut. Selain itu, perhitungan skor posisi kalimat juga sangat sederhana (persamaan 5 ) sehingga tidak memakan waktu eksekusi program. 2. Kalimat-kalimat berita yang dapat dijadikan sebagai ringkasan secara umum mengandung kata-kata yang sering muncul pada kumpulan dokumen. 3. Fitur TF-IDF sebenarnya merupakan fitur yang cukup penting untuk menghasilkan ringkasan yang baik. Hal ini dapat dilihat dari nilai ROUGE-1 yang tinggi ketika menggunakan fitur TF-IDF. Namun, jika dilihat berdasarkan waktu, penggunaan fitur TF-IDF cukup memakan waktu eksekusi karena dalam prosesnya fitur ini harus menghitung bobot TF-IDF tiap kata di tiap dokumen. 4. Untuk fitur kemiripan dengan judul berita, berdasarkan hasil uji coba, dapat disimpulkan bahwa fitur tersebut tidak terlalu memegang peranan penting karena dengan atau tanpa fitur tersebut nilai ROUGE-1 tidak menunjukkan perbedaan yakni antara kombinasi 4 fitur dan kombinasi fitur posisi kalimat, word frequency, dan TF-IDF. Bahkan pada kombinasi tiga fitur dan dua fitur dapat dilihat bahwa penggunaan fitur tersebut menghasilkan nilai ROUGE-1 yang lebih kecil dibandingkan menggunakan fitur lain.
[1] Fachrurrozi, M., Yusliani, N., & Yoanita, R. U. (2013). Frequent Term based Text Summarization for Bahasa Indonesia. International Conference on Innovations in Engineering and Technology (ICIET'2013) . Bangkok (Thailand). [2] Ferreira, R., Cabral, L. d., Lins, R. D., e Silva, G. P., & Freitas, F. (2013). Assessing sentence scoring techniques for extractive text summarization. Expert Systems with Applications, 40, 5755–5764. [3] Ferreira, R., Freitas, F., Cabral, L. d., Lins, R. D., Lima, R., Franc¸a, G., . . . Favaro, L. (2014). A Context Based Text Summarization System. 11th IAPR International Workshop on Document Analysis Systems. IEEE. [4] Holi, M. H. (2006). Integrating tf-idf Weighting With Fuzzy View based Search. Proceedings of the ECAI Workshop on Text-Based Information Retrieval (TIR-06). Riva del Garda, Italy. [5] Karel J., J. S. (2008). Automatic Text Summarization (The State of The Art 2007 and New Challenges). Znalosti (hal. 1-12). Ústav informatiky a softvérového inziinierstva: FIIT STU Bratislava. [6] Lin, C. Y. (2004). ROUGE: a Package for Automatic Evaluation of Summaries. In Proceedings of Workshop on Text Summarization Brances Out (hal. 74-81). Barcelona: Association for Computational Linguistics. [7] Radev, D. R., Hovy, E. H., & McKeown, K. (2002). Introduction to the Special Issue on Summarization. Computational Linguistics, 28(4), 399408. [8] Salton, G., & Buckley, C. (1988). TERM-WEIGHTING APPROACHES IN AUTOMATIC TEXT RETRIEVAL. Information Processing & Management, 24, 513-523. [9] Kavita-Ganesan (2016). ROUGE 2.0 Documentation - Java Package for Evaluation of Summarization Tasks [Online].Tersedia:http://kavitaganesan.com/content/rouge-2.0-documentation [18 Juli 2016] [10] Mei, J.-P., & Chen, L. (2012). SumCR: A new subtopic-based extractive approach for text summarization. Knowl Inf Syst (2012), 31, 527–545.
V. KESIMPULAN DAN SARAN A. Kesimpulan Berdasarkan uji coba, didapatkan kesimpulan bahwa diantara empat kombinasi fitur yakni fitur posisi kalimat, word frequency, TF-IDF, dan judul berita, kombinasi yang paling optimal berdasarkan nilai ROUGE-1 dan waktu eksekusi 5
