Jurnal Ilmiah NERO Vol. 1 No. 2
2014
IMPLEMENTASI AUTOMATED TEXT SUMMARIZATION UNTUK DOKUMEN TUNGGAL BERBAHASA INDONESIA DENGAN MENGGUNAKAN GRAPH-BASED SUMMARIZATIONALGORITHM DAN ALGORITMA GENETIKA Gede Aditra Pradnyana1, I Komang Ari Mogi2
Program Studi Teknik Informatika, STMIK STIKOM Indonesia Denpasar, Bali, Indonesia 2 Jurusan Ilmu Komputer, Fakultas MIPA, Universitas Udayana Jimbaran, Bali, Indonesia Email :
[email protected],
[email protected]
1
Abstrak
Ringkasan merupakan suatu cara yang efektif untuk menyajikan suatu karangan yang panjang dalam bentuk yang singkat. Ringkasan adalah penyajian singkat dari suatu karangan asli tetapi dapat tetap mempertahankan urutan isi dan sudut pandang pengarang asli, sedangkan perbandingan bagian atau bab dari karangan asli secara proporsional tetap mempertahankan dalam bentuknya yang singkat. Dalam membuat ringkasan kita diharuskan untuk membaca keseluruhan isi artikel tersebut terlebih dahulu, untuk kemudian meringkasnya. Hal ini tentu menjadi masalah dimana ringkasan dibuat dengan tujuan untuk meminimalkan waktu membaca tetapi tetap dapat memberikan teks yang isinya langsung mengarah pada tujuan utama atau ide pokoknya. Untuk memecahkan masalah tersebut diperlukan suatu perangkat atau aplikasi yang dapat meringkas teks secara otomatis. Automated Text Summarization (ATS) merupakan aplikasi berbasis komputer untuk menghasilkan ringkasan dari sebuah artikel tanpa menghilangkan tujuan utama dari artikel tersebut. Pada paper ini dikembangkan suatu metode ATS berbasis graf (Graph-Based Summarization Algorithm) untuk dokumen berbahasa Indonesia yang menggunakan Algoritma Genetika sebagai penyeleksi kalimat yang tidak sesuai dengan ide pokok dari teks. Dari hasil pengujian diperoleh kesimpulan bahwa untuk proses dokumen yang sama, waktu proses Algoritma Genetika dipengaruhi oleh penentuan nilai generasi, populasi dan elitism. Nilai generasi dan populasi yang ditetapkan berbanding lurus dengan waktu proses dan penggunaan sumber daya. Keywords:Dokumen, Ringkasan, Automated Text Summarization, Graph, Algoritma Genetika
1. Pendahuluan Informasi adalah pengetahuan yang didapatkan dari pembelajaran, pengalaman, atau instruksi. Selain itu informasi juga dapat diartikan data yang telah diolah menjadi suatu bentuk yang penting bagi si penerima dan mempunyai nilai yang nyata yang dapat dirasakan dalam keputusan-keputusan yang sekarang atau keputusan-keputusan yang akan datang. Salah satu cara untuk mendapatkan informasi adalah membaca dokumen teks atau artikel. Namun untuk membaca dokumen terdapat beberapa permasalahan yaitu terbatasnya waktu yang dimiliki pembaca, dokumen teks yang panjang sehingga memberikan kesan basa-basi atau membosankan, dan kalimat yang kurang sesuai dengan tujuan utama atau ide pokok dokumen teks tersebut. Agar para pembaca dapat menghemat waktu untuk mendapatkan tujuan utama atau ide pokok dokumen, maka perlu dilakukan peringkasan pada teks aslinya. Ringkasan (summary) merupakan suatu cara yang efektif untuk menyajikan suatu karangan yang panjang dalam bentuk yang singkat. Ringkasan juga didefinisikan sebagai sebuah teks yang dihasilkan dari satu atau lebih teks, mengandung informasi dari teks asli dan panjangnya tidak lebih dari setengah teks asli [1]. Walaupun bentuknya ringkas, namun ringkasan itu harus tetap mempertahankan pikiran pengarang dan pendekatannya yang asli. Dengan kata lain ringkasan merupakan penyajian singkat dari suatu karangan asli tetapi dengan tetap mempertahankan urutan isi dan sudut pandang pengarang asli, sedangkan perbandingan bagian 33 | N E R O
Jurnal Ilmiah NERO Vol. 1, No.2
2014
atau bab dari karangan asli secara proporsional tetap mempertahankan dalam bentuknya yang singkat. Dalam membuat ringkasan kita harus diharuskan untuk membaca keseluruhan isi artikel tersebut terlebih dahulu, kemudian meringkasnya. Hal ini tentu menjadi masalah dimana ringkasan dibuat dengan tujuan untuk meminimalkan waktu membaca tetapi tetap dapat memberikan teks yang isinya langsung mengarah pada tujuan utama atau ide pokoknya. Untuk memecahkan masalah tersebut diperlukan suatu perangkat atau aplikasi yang dapat meringkas teks secara otomatis. Automated TextSummarization (ATS) merupakan aplikasi berbasis komputer untuk menghasilkan ringkasan dari sebuah artikel tanpa menghilangkan tujuan utama dari artikel tersebut [2]. Tujuan utamanya adalah untuk menunjukkan beberapa kalimat utama yang digabung menjadi satu ringkasan, dengan harapan dapat mengurangi waktu untuk memahami isi dari bacaan. Penelitian mengenai peringkasan teks otomatis telah berlangsung dari tahun 1958 sampai sekarang. Berbagai metode telah diterapkan dan masih terus dikembangkan oleh para peneliti di seluruh dunia. Salah satu metode yang banyak dikembangkan adalah metoda berbasis graf. Metoda berbasis graf termasuk sebuah pendekatan baru pada peringkasan teks. Walaupun pendekatan non-graf cukup berhasil menemukan unit teks yang paling penting dalam dokumen, para peneliti percaya teori graf dapat membantu seseorang memahami lebih baik keterhubungan antar unit teks [3]. Pada paper ini dikembangkan suatu metode ATS berbasis graf untuk dokumen berbahasa Indonesia yang menggunakan Algoritma Genetika sebagai penyeleksi kalimat yang tidak sesuai dengan ide pokok dari teks. Algoritma Genetika adalah suatu metode optimasi pencarian yang umum digunakan untuk mencari lintasan terpendek (shortest path finding) yang didasarkan pada mekanisme dari seleksi dan genetika natural.Metode yang dikembangkan ini diharapkan dapat menghasilkan suatu ringkasan yang sesuai dengan ide pokok dari artikel aslinya, sesuai dengan hasil ringkasan berdasarkan ekstraksi manusia, dan dapat mengurangi waktu untuk memahasi isi dari artikel tersebut. 2.
Dasar Teori
2.1 Graph Secara kasar graf (graph) adalah suatu diagram yang memuat informasi tertentu jika diintepretasikan secara tepat [4]. Suatu graf adalah himpunan benda-benda yang disebut simpul (vertex atau node) yang terhubung oleh sisi (edge) atau busur (arc). Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan simpul) yang dihubungkan oleh garis-garis (melambangkan sisi) atau garis berpanah (melambangkan busur). Suatu sisi dapat menghubungkan suatu simpul dengan simpul yang sama. Sisi yang demikian dinamakan gelang (loop). Suatu graf yang terdiri dari simpul dan sisi dapat dinyatakan dalam suatu persamaan seperti terlihat pada Persamaan (1). , (1) dimana G merupakan graph (graf), V merupakan verteks (simpul), dan E merupakan edge (sisi). 2.2 Algoritma Genetika 2.2.1 Definisi Algoritma Genetika Algoritma Genetika (Genetic Algorithm, GA) adalah algoritma pencarian yang didasarkan atas mekanisme seleksi alami dan evolusi biologis. Algoritma Genetika mengkombinasikan antara deretan struktur dengan pertukaran informasi acak ke bentuk algoritma pencarian dengan beberapa perubahan bakat pada manusia. Pada setiap generasi, himpunan baru dari deretan individu dibuat berdasarkan kecocokan pada generasi sebelumnya. Satu siklus iterasi Algoritma Genetika (sering disebut sebagai generasi) terdapat dua proses, yakni proses seleksi dan rekombinasi. Proses seleksi adalah proses evaluasi kualitas setiap string didalam populasi untuk memperoleh peringkat calon solusi. Berdasarkan hasil evaluasi, dipilih string-string yang akan mengalami proses rekombinasi. Proses pemilihan biasanya dilakukan secara acak, string dengan 34 | N E R O
Jurnal Ilmiah NERO Vol. 1 No. 2
2014
kualitas yang lebih baik akan memiliki peluang lebih besar untuk terpilih sebagai calon-calon string generasi berikutnya. Proses rekombinasi meliputi proses genetika untuk memperoleh string baru dari pertukaran karakter dari calon-calon string yang didapat pada tahap seleksi. String-string pada generasi baru dihasilkan dengan menggunakan operasi genetik secara acak pada calon string yang terpilih pada tahap seleksi. Proses rekombinasi akan menghasilkan string-string baru yang berbeda dibandingkan induknya dan dengan demikian diperoleh domain pencarian yang baru. 2.2.2
Cara Kerja Algoritma Genetika Cara kerja Algoritma Genetika sangat sederhana, hanya mencakup proses penduplikasian string-string dan pertukaran bagian-bagian dari string. Meskipun cukup sederhana, tetapi mempunyai kemampuan untuk menyelesaikan persoalan optimasi. Kemampuan ini didukung oleh tiga operator genetik yaitu reproduksi, rekombinasi dan mutasi. Pada reproduksi terjadi proses penduplikasian string berdasarkan nilai fungsi objektifnya. Nilai objektif ini dapat dilihat sebagai suatu keuntungan yang ingin dicapai atau dimaksimalkan. Sementara proses pertukaran bagian-bagian string dilakukan oleh operator rekombinasi dan mutasi. Di samping ketiga operator dasar (reproduksi, rekombinasi, dan mutasi), parameterparameter genetik (jumlah populasi, maksimum generasi, probabilitas rekombinasi, probabilitas mutasi, dan lain-lain), serta asumsi-asumsi yang digunakan dalam pemodelannya juga mempunyai peran penting. Pada Algoritma Genetika terdapat beberapa proses yaitu:
a. Proses Pengkodean (Encoding) Pada proses pengkodean, gen dapat direpresentasikan dalam bentuk string bit, pohon, array bilangan real, daftar aturan, elemen permutasi, elemen program, atau representasi lainnya yang dapat diimplementasikan untuk operator genetika. Ada beberapa macam teknik pengkodean yang dapat dilakukan dalam Algoritma Genetika, diantaranya pengkodean biner (binary encoding), pengkodean permutasi (permutation encoding), pengkodean nilai (value encoding) dan pengkodean pohon (tree encoding). b. Proses Seleksi Seleksi adalah proses untuk menentukan individu mana saja yang akan dipilih untuk dilakukan rekombinasi dan bagaimana keturunan terbentuk dari individu-individu terpilih tersebut. Langkahnpertama yang dilakukan dalam seleksi adalah pencarian nilai fitness. Masing-masing individu dalam suatu wadah seleksi akan menerima probabilitas reproduksi yang tergantung pada nilai obyektif dirinya sendiri terhadap nilai obyektif dari semua individu dalam wadah seleksi tersebut. Nilai fitness kemudian akan digunakan pada tahap seleksi berikutnya. Ada beberapa macam proses seleksi yang ada pada Algoritma Genetika, diantaranya: Seleksi dengan Roda Roulette (Roulette Wheel Selection), seleksi berdasarkan Ranking Fitness (Rank-based Fitness), seleksi Stocastic Universal Sampling, seleksi Lokal (Local Selection), seleksi dengan Pemotongan (Truncation Selection) dan seleksi dengan Turnamen (Tournament Selection).
c. Proses Rekombinasi Rekombinasi adalah proses untuk menyilangkan dua kromosom sehingga membentuk kromosom baru yang harapannya lebih baik dari pada induknya. Rekombinasi dikenal juga dengan nama crossover. Tidak semua kromosom pada suatu populasi akan mengalami proses rekombinasi. Kemungkinan suatu kromosom mengalami proses rekombinasi didasarkan pada probabilitas crossover yang telah ditentukan terlebih dahulu. Probabilitas crossover menyatakan peluang suatu kromosom akan mengalami crossover. Ada beberapa macam proses rekombinasi yang ada pada Algoritma Genetika, diantaranya: rekombinasi diskret, rekombinasi menengah, rekombinasi garis, rekombinasi satu titik, rekombinasi banyak titik, rekombinasi seragam, rekombinasi dengan permutasi. 35 | N E R O
Jurnal Ilmiah NERO Vol. 1, No.2
2014
d. Proses Mutasi Mutasi adalah proses penambahan nilai acak yang sangat kecil dengan probabilitas rendah pada variabel keturunan. Peluang mutasi didefinisikan sebagai persentasi dari jumlah total gen pada populasi yang mengalami mutasi. Peluang mutasi mengendalikan banyaknya gen baru yang akan dimunculkan untuk dievaluasi. Jika peluang mutasi terlalu kecil, banyak gen yang mungkin berguna tidak dievaluasi, tetapi bila peluang mutasi ini terlalu besar maka akan terlalu banyak gangguan acak, sehingga anak akan kehilangan kemiripan dari induknya dan algoritma juga akan kehilangan kemampuan untuk belajar dari history pencarian. Ada dua macam proses mutasi yang ada pada Algoritma Genetika, diantaranya mutasi bilangan real dan mutasi biner. 2.3 Proses Parsing dan Stemming Dalam bidang tata bahasa dan linguistik, parsing adalah sebuah proses untuk membuat sebuah kalimat menjadi lebih bermakna. Hal ini dilakukan dengan cara memecah kalimat tersebut menjadi kata-kata atau frase-frase [5]. Proses parsing merupakan proses penguraian dokumen yang semula berupa kalimat-kalimat berisi kata-kata dan tanda pemisah antar kata seperti titik (.), koma (,), spasi dan tanda pemisah lain menjadi kata-kata saja. Tahapan dalam proses parsing antara lain: 1. Isi dokumen akan diuraikan menjadi kata-kata saja, baik kata penting maupun kata tidak penting. 2. Informasi hasil penguraian tersebuat akan disimpan dalam tabel daftar kata. 3. Proses penguraian akan dilakukan sampai isi dari keseluruhan dokumen selesai diproses. Stemming merupakan suatu proses yang dilakukan untuk menemukan kata dasar dari sebuah kata. Proses yang dilakaukan adalah menghilangkan semua imbuhan (affixes) baik yang terdiri dari awalan (prefixes), sisipan (infixes), akhiran (suffixes) dan kombinasi dari awalan dan akhiran (confixes) pada kata turunan. Imbuhan untuk setiap bahasa selalu berbeda-beda, contohnya imbuhan pada Bahasa Indonesia lebih kompleks bila dibandingkan dengan imbuhan pada Bahasa Inggris. Karena seperti yang telah disebutkan di atas bahwa imbuhan pada Bahasa Indonesia terdiri dari awalan, sisipan, akhiran, bentuk perulangan (repeated forms) dan confixes. Imbuhan-imbuhan yang melekat pada suatu kata harus dihilangkan untuk mengubah bentuk kata tersebut menjadi bentuk kata dasarnya. Stemming teks berbahasa Indonesia memiliki beberapa masalah yang sangat khusus terhadap bahasa. Salah satu masalah tersebut adalah perbedaan tipe dari imbuhan-imbuhan (affixes), yang lain adalah bahwa awalan (prefixes) dapat berubah tergantung dari huruf pertama pada kata dasar. Sebagai contoh ”me-” dapat berubah menjadi ”mem-” ketika huruf pertama dari kata dasar tersebut adalah ”b”, misalnya ”membuat”, tetapi ”me-” juga dapat berubah menjadi ”meny-” ketika huruf pertama dari kata dasar melekat adalah ”s”, misalnya ”menyapu”. Selanjutnya ketika ada lebih dari satu imbuhan yang melekat pada suatu kata, maka urutan untuk menghilangkan imbuhan-imbuhan pada kata tersebut menjadi sangat penting. Berdasarkan penelitian yang dilakukan oleh Agusta (2009) diperoleh kesimpulan bahwa proses stemming dokumen teks berbahasa Indonesia menggunakan Algoritma Porter membutuhkan waktu yang lebih singkat dibandingkan dengan stemming menggunakan Algoritma Nazief & Adriani [6]. Selain itu, menurut penelitian yang telah dilakukan juga memperoleh hasil bahwa keakuratan dari Algoritma Porter tidak memiliki perbedaan yang signifikan terhadap Algoritma Nazief & Adriani, namun dari segi waktu yang dibutuhkan masing-masing algoritma dalam melakukan prosesnya (stemming), Algoritma Porter lebih cepat dibandingkan dengan Algoritma Nazief & Adriani.
36 | N E R O
Jurnal Ilmiah NERO Vol. 1 No. 2
2014
2.4 Algoritma Porter Stemmer Porter Stemmer for Bahasa Indonesia dikembangkan oleh Fadillah Z. Tala pada tahun 2003. Implementasi Porter Stemmer for Bahasa Indonesia berdasarkan English Porter Stemmer yang dikembangkan oleh W.B. Frakes pada tahun 1992. Beberapa modifikasi telah dilakukan oleh Faddilah untuk membuat Algoritma Porter dapat digunakan sesuai dengan bahasa Indonesia, karena bahasa Inggris datang dari kelas yang berbeda. Adapun langkah-langkah algoritma ini adalah sebagai berikut [6]: 1. Hapus Particle, 2. Hapus Possesive Pronoun. 3. Hapus awalan pertama. Jika tidak ada lanjutkan ke langkah 4a, jika ada cari maka lanjutkan ke langkah 4b. 4. a. Hapus awalan kedua, lanjutkan ke langkah 5a. b. Hapus akhiran, jika tidak ditemukan maka kata tersebut diasumsikan sebagai root word. Jika ditemukan maka lanjutkan ke langkah 5b. 5. a. Hapus akhiran. Kemudian kata akhir diasumsikan sebagai root word b. Hapus awalan kedua. Kemudian kata akhir diasumsikan sebagai root word. 2.5 Proses Stopword Removal Sebagian besar bahasa resmi di berbagai negara memiliki kata fungsi dan kata sambung seperti preposisi dan kata hubung yang hampir selalu muncul pada dokumen-dokumen teks. Kata-kata ini umumnya tidak memiliki arti yang lebih untuk memenuhi kebutuhan seorang searcher dalam mencari informasi. Kata-kata tersebut (misalnya a, an, the on pada bahasa Inggris) disebut sebagai Stopwords [7]. Sebelum proses stopword removal dilakukan, terlebih dulu dibuat daftar stopword(stoplist). Sebuah sistem Text Retrieval biasanya disertai dengan sebuah Stoplist. Stoplist berisi sekumpulan kata yang 'tidak relevan', namun sering sekali muncul dalam sebuah dokumen. Dengan kata lain Stoplist berisi sekumpulan Stopwords [8]. 2.6 Perhitungan Bobot Kalimat dan Bobot Relasi Antar Kalimat 2.6.1
TF-IDF (Terms Frequency-Inverse Document Frequency) Metode ini merupakan metode untuk menghitung nilai/bobot suatu kata (term) pada dokumen. Metode ini akan mengabaikan setiap kata-kata yang tergolong tidak penting. Oleh sebab itu, sebelum melalukan metode ini, proses stemming dan stopword removal harus dilakukan terlebih dahulu oleh sistem. Karena melakukan pembobotan suatu kalimat bukan kata, pada metode ini terdapat 4 proses yang berbeda untuk perhitungan nilai suatu kalimat, yaitu [9]: 1. Kecocokan kata-kata pada kalimat dengan daftar kata kunci/keyword. Idenya adalah semakin tinggi nilai suatu kalimat, maka kalimat tersebut semakin penting keberadaannya di dalam suatu dokumen. 2. Menghitung frekuensi kata-kata suatu kalimat terhadap artikel dan hasilnya akan dibagi dengan jumlah kata pada artikel tersebut. Alasannya adalah semakin tinggi frekuensi kata tersebut di dalam suatu artikel, maka kalimat yang memiliki kata tersebut semakin penting keberadaanya di dalam suatu artikel. 3. Bagian ketiga ini sangat sederhana yaitu hanya melihat posisi kalimat di dalam suatu paragraf. Umumnya suatu paragraf yang baik hanya akan memiliki satu gagasan atau ide pokok. Berdasarkan metode deduktif induktif sesuai kaidah Bahasa Indonesia, ide pokok suatu paragraf terdapat pada kalimat yang berada di awal dan atau akhir dari paragraf tersebut. Oleh sebab itu, kalimat yang berada di awal dan akhir suatu paragraf akan diberikan nilai yang lebih tinggi dibandingkan kalimat-kalimat lain pada paragraf tersebut. 4. Bagian keempat ini sangat berhubungan dengan hasil pemetaan artikel. Pada bagian keempat ini akan dihitung jumlah relasi (yang disimbolkan dengan edge) suatu kalimat di dalam dokumen. Idenya adalah semakin banyak relasi yang dimiliki suatu kalimat dengan kalimat lainnya di dalam suatu artikel maka kalimat tersebut kemungkinan mendiskusikan topik utama suatu artikel. Kalimat tersebut semakin penting keberadaannya di dalam artikel tersebut. 37 | N E R O
Jurnal Ilmiah NERO Vol. 1, No.2
2014
Kemudian hasil dari keempat perhitungan di atas akan ditambahkan dan menjadi nilai dari dari tf, seperti terlihat pada Persamaan (2). tf = bobot1 + bobot2 + bobot3 + bobot4(2) 2.6.2 Perhitungan Bobot Edge Untuk perhitungan bobot edge akan digunakan perhitunyan seperti telihat pada Persamaan (3)[10]. (3) Nilai overlap i,j diperoleh dengan menghitung jumlah kata yang sama antara kalimat ke-i dan kalimat ke-j dengan mengabaikan stopword yang ada di dalam kalimat-kalimat tersebut. Kemudian hasil dari persamaan diatas akan digunakan untuk menentukan nilai relasi dari setiap kalimat berdasarkan hasil pemetaan dari dokumen. 2.7 Summarization (ringkasan) Peringkasan teks otomatis (automated text summarization atau ATS) adalah pembuatan ringkasan dari sebuah teks secara otomatis dengan memanfaatkan aplikasi yang dijalankan pada komputer. Sebuah sistem peringkas diberi masukan berupa teks, kemudian melakukan peringkasan, dan menghasilkan keluaran berupa teks yang lebih singkat dari teks asli. Hasil peringkasan mengandung poin-poin penting atau informasi utama dari teks sumber. Terdapat dua pendekatan pada peringkasan teks, yaitu ekstraksi (shallower approaches) dan abstraksi (deeper approaches). Pada teknik ekstraksi, sistem menyalin unit-unit teks yang dianggap paling penting atau paling informatif dari teks sumber menjadi ringkasan. Unit-unit teks yang disalin dapat berupa klausa utama, kalimat utama, atau paragraf utama. Sedangkan teknik abstraksi melibatkan parafrase dari teks sumber. Teknik abstraksi mengambil intisari dari teks sumber, kemudian membuat ringkasan dengan menciptakan kalimat-kalimat baru yang merepresentasikan intisari teks sumber dalam bentuk berbeda dengan kalimat-kalimat pada teks sumber. Kalimat adalah satuan bahasa terkecil, dalam wujud lisan atau tulisan, yang mengungkapkan pikiran yang utuh. Berdasarkan jumlah sumbernya, sebuah ringkasan dapat dihasilkan dari satu sumber (single-document) atau dari banyak sumber (multi-document). Peringkasan single-document masukannya berupa sebuah teks dan keluarannya berupa sebuah teks baru yang lebih singkat. 3. Perancangan dan Implementasi Sistem 3.1 Analisis Sistem Analisis yang dilakukan adalah analisis mengenai kebutuhan sistem. Untuk mempermudah menganilisa kebutuhan sistem diperlukan sebuah perangkat dan teknik-teknik tertentu, tepatnya adalah diagram aliran data yang berfungsi menyusun daftar input, proses dan output dari sistem automated text summarization yang akan dikembangkan.Hasil yang didapatkan adalah analisa dari model proses sistem yaitu penentuafn input-input dari sistem, penentuan proses-proses dalam operasi sistem, dan penentuan output dari pemrosesan input sistem. 3.1.1
Penentuan Input-Input dari Sistem Input yang masuk diproses dalam sistem berupa sebuah dokumen yang akan diringkas. Dokumen disini berperan sebagai suatu data mentah yang akan dijadikan objek pada penelitian ini. Dokumen berupa artikel-artikel mengenai teknologi informasi dalam Bahasa Indonesia dengan format file PDF. 38 | N E R O
Jurnal Ilmiah NERO Vol. 1 No. 2
2014
3.1.2
Penentuan Proses-Proses dalam Operasi Sistem Setelah melakukan teknik kajian pustaka pada tahap sebelumnya, secara garis besar proses-proses yang ada pada sistem adalah: 1. Proses upload dokumen ke dalam sistem. 2. Proses konversi dokumen dengan format file PDF menjadi file txt. 3. Proses devide to word atau parsing yaitu proses yang memecah kalimat-kalimat dalam file txt menjadi kata-kata. 4. Proses stopword removal atau menghilangkan kata-kata tidak penting. 5. Proses stemming dengan algoritma Porter Stemmer for Bahasa Indonesia. 6. Proses perhitungan bobot kalimat 7. Proses perhitugan bobot relasi antar kalimat. 8. Proses summarization dengan menggunakan algoritma Genetika
3.1.3
Penentuan Output dari Proses Input Sistem Output yang dihasilkan sistem melalui pemrosesan input dari user adalah dokumen hasil proses peringkasan yang dapat disimpan dalam format file .doc. 3.2 Desain Sistem Flowchart sistem automated text summarization ini bertujuan untuk menjelaskan alur logika sistem, mulai dari pemrosesan input menjadi output yang akan dihasilkan.Dalam kasus pengembangan sistem automated text summarization ini, proses-proses yang dilalui dalam proses text preprocessing mengalami sedikit modifikasi yaitu penggunaan kamus kata dasar untuk filtering kata-kata sebelum masuk ke dalam proses stemming. Penggunaan kamus kata dasar untuk filtering berguna untuk meningkatkan akurasi proses stemming. Setiap term yang terdapat dalam kamus kata dasar tidak akan melewati proses stemming. Gambar rancangan alur proses Automated Text Summarization dengan menggunakakan graph dan Algoritma Genetika terlihat pada Gambar 1.
Gambar 1. Diagram Alir (Flowchart) Sistem ATS 39 | N E R O
Jurnal Ilmiah NERO Vol. 1, No.2
2014
Berikut ini adalah deskripsi dan spesifikasi dari Algoritma Genetika yang digunakan dalam pembuatan sistem Tabel 1. Spesifikasi Algoritma Genetika Variabel Keterangan Jumlah node dalam graph Sejumlah Kalimat Jumlah relasi maksimum untuk setiap node Jumlah kalimat - 1 Jumlah populasi yang digunakan Dapat ditentukan (Node) Metode Seleksi Roulette Wheel danElitsm Metode Reproduksi Single Point Crossover, 1-Point mutation (opsional) Kriteria penghentian 10000 generasi Kondisi lain Asymetric graph, tidak ada node yang dilewati lebih dari sekali
Gambar 2. GUI dari Sistem ATS Untuk memudahkan penggunaan sistem terutama untuk pengguna yang masih awam, maka dibuatkan rancangan antarmuka sistem yang berbasis Graphical User Interface (GUI). Untuk perancangan GUI sistem Automated Text Summarization ini penulis memiliki beberapa pertimbangan yaitu bagaimana merancang bentuk dan desain sistem agar sistem dapat diakses atau digunakan dengan mudah. Gambar 2 adalah rancangan GUI dari sistem Automated Text Summarization. 3.3 Pengujian Sistem Pendekatan pengujian yang digunakan untuk uji coba sistem Automated TextSummarization yang telah dikembangkan yaitu pengujian white box tepatnya pengujian basis path. Pengujian white box adalah pengujian yang didasari pada pemeriksaan detail prosedural. Alur logika dari sistem diujicoba dengan menyediakan kasus ujicoba yang melakukan sekumpulan kondisi atau perulangan tertentu pada proses peringkasan. Selain dengan pendekatan white box diatas, pengujian terhadap sistem juga dilakukan dengan cara membandingkan perhitungan integrasi manual dengan yang dilakukan sistem, serta pengujian waktu proses integrasi.
40 | N E R O
Jurnal Ilmiah NERO Vol. 1 No. 2
2014
4. Hasil dan Pembahasan Pengimplementasian sistem Automated Text Summarization mencakup lingkup perangkat keras dan perangkat lunak. Sistem diimplementasikan pada bahasa pemrograman web PHP. Pada lingkup perangkat keras spesifikasi yang diperlukan adalah: 1. Processor Intel(R) Core(TM) 2 Duo CPU P8400 @ 2,26 GHz 2,27 GHz 2. RAM 2 GB 3. Hardisk 320 GB Sedangkan spesifikasi yang diperlukan pada lingkup perangkat lunak adalah: 1. Database Management System (DBMS) MySQL. 2. Web Server Apache ( XAMPP 1.7.4 ) 3. Web Browser Mozilla Firefox 4.0 4. Sistem Operasi Windows 7 Ultimate 4.1 Pengujian Proses Summarization Pada proses summarization terdapat tiga tahap utama yang dilakukan yaitu pembobotan TF – IDF, pembobotan relasi, dan peringkasan dengan Algoritma Genetika. Maka pengujian ini difokuskan pada tiga tahapan tersebut. Pengujian dilakukan dengan membandingkan hasil perhitungan yang terjadi dengan cara manual dan yang dilakukan oleh sistem. 4.1.1
Pengujian Proses Pembobotan Kalimat dengan TF – IDF Pengujian terhadap proses pembobotan kalimat dengan TF – IDF dilakukan untuk mengetahui apakah perhitungan pada sistem sudah sesuai dengan teorinya. Misalkan akan dilakukan pembobotan terhadap sebuah kalimat, kalimatnya adalah “Proyek ini dimotori oleh Patrick Naughton, Mike Sheridan, James Gosling dan Bill Joy, beserta sembilan pemrogram lainnya dari Sun Microsystems”. Kalimat tersebut berada pada teks Asal Usul Java. Setelah sampai pada proses perhitungan bobot kalimat menggunakan rumus TF-IDF, diperoleh 4 bobot dimana nilai dan perhitungan 4 bobot adalah sebagai berikut : Kalimat : “Proyek ini dimotori oleh Patrick Naughton, Mike Sheridan, James Gosling danBill Joy, beserta sembilan pemrogram lainnya dari Sun Microsystems”. Kata : proyek, motor, patrick, naughton, mike, sheridan, james, gosling, bil, joy, beserta, sembilan, program, sun, microsystems. Total Kata : 181 kata Bobot 1 : 2 (hanya proyek dan program) Bobot 2 : Frekuensi kata dalam teks : Proyek 7, motor 1, patrick 1, naughton 1, mike 1, sheridan 1, james 2, gosling 3, bil 1, joy 1, beserta 1, sembilan 1, program 2, sun 2, microsystems 2. Jadi Bobot 2 = 7+1+1+1+1+1+2+3+1+1+1+1+2+2+2/181 = 27/181= 0,149171 Bobot 3 : 0 ( Karena posisi kalimat tidak berada di awal atau akhir paragraf ) Bobot 4 : 9 relasi Total dari penjumlahan 4 buah bobot tersebut akan menjadi nilai TF dari kalimat. Sehingga nilai dari TF nya adalah TF = bobot 1 + bobot 2 + bobot 3 + bobot 4 = 2 + 0,149171 + 0+ 9 = 11,149171 Selanjutnya adalah perhitungan IDF kalimat. IDF dihitung dengan menggunakan persamaan “IDF = log N/n”. Dimana nilai IDF kalimat diperoleh dengan menjumlakan nilai dari seluruh IDF kata-kata yang ada dalam kalimat tersebut. Jadi nilai IDF akan dihitung satu persatu sebagai berikut: IDF “proyek” = log N/n = log 19/7 = 0,43365 IDF “motor” = log N/n = log 19/1 = 1,27875 IDF “patrick” = log N/n = log 19/1 = 1,27875 IDF “naughton” = log N/n = log 19/1 = 1,27875 41 | N E R O
Jurnal Ilmiah NERO Vol. 1, No.2
2014
IDF “ mike” = log N/n = log 19/1 = 1,27875 IDF “sheridan” = log N/n = log 19/1 = 1,27875 IDF “ james” = log N/n = log 19/2 = 0,97772 IDF “gosling,” = log N/n = log 19/3 = 0,80163 IDF “bil” = log N/n = log 19/1 = 1,27875 IDF “ joy” = log N/n = log 19/1 = 1,27875 IDF “ beserta” = log N/n = log 19/1 = 1,27875 IDF “ sembilan” = log N/n = log 19/1 = 1,27875 IDF “ program” = log N/n = log 19/2 = 0,97772 IDF “ sun” = log N/n = log 19/2 = 0,97772 IDF “ microsystems” = log N/n = log 19/2 = 0,97772
Semua IDF kata tersebut lalu dijumlahkan untuk mendapat nilai dari IDF kalimat. Nilai dari IDF nya adalah 16,65491. Nilai dari bobot kalimat diperoleh dengan mengalikan TF dengan IDF. Jadi nilai bobot kalimatmya adalah : Bobot = TF x IDF = 11,149171x 16,65491= 185, 68843
Gambar 3. Hasil Pembobotan TF-IDF Kalimat Sistem Dari hasil perbandingan perhitungan secara manual dan dengan sistem dapat dilihat bahwa perhitungan TF-IDF yang dilakukan oleh sistem sudah sesuai dengan perhitungan yang dilakukan secara manual. 4.1.2 Pengujian Proses Pembobotan Relasi antar Kalimat Hampir sama dengan pengujian proses pembobotan kalimat dengan TF-IDF, pengujian proses pembobotan relasi antar kalimat bertujuan untuk membuktikan bahwa perhitungan bobot relasi antar kalimat yang dilakukan oleh sistem sudah sesuai dengan rumus atau teori yang ada. Misalkan akan dihitung bobot relasi kalimat pertama “Proyek ini dimotori oleh Patrick Naughton, Mike Sheridan, James Gosling danBill Joy, beserta sembilan pemrogram lainnya dari Sun Microsystems” dengan kalimat kedua “Salah satu hasil proyek ini adalah maskot Duke yang dibuat oleh Joe Palrang”. Berikut adalah perhitungan manual bobot relasi : Posisi kalimat pertama : 3 Posisi kalimat kedua : 4 Nilai overlap : 2 Bobot kalimat pertama : 185, 68843 Bobot kalimat kedua : 50, 27524 42 | N E R O
Jurnal Ilmiah NERO Vol. 1 No. 2
2014
Jadi bobot relasi dari kalimat pertama ke kalimat kedua adalah : Cost(3,4) =
=
= 0,019890
Gambar 4 Perhitungan Bobot Relasi oleh Sistem Dari hasil perbandingan perhitungan secara manual dan dengan sistem dapat dilihat bahwa perhitungan bobot relasi antar kalimat yang dilakukan oleh sistem sudah sesuai dengan perhitungan yang dilakukan secara manual. 4.2 Hasil Pengujian Sistem Pengujian sistem dilakukan dengan melakukan proses terhadap lima buah dokumen uji dengan format teks berbahasa Indonesia, dengan jumlah kalimat dan paragraph yang beragam. Dokumen pengujian dapat dilihat dalam lampiran 1.Berikut ini adalah contoh hasil ringkasan dari sistem dan teks asli yang diringkas. 1. Text Asli Mengenal pencegahan kanker sangatlah tepat dan benar. Lebih baik mencegah daripada mengobati. Mengurangi risiko pada kanker tertentu mungkin bisa melalui perubahan pada makanan dan gaya hidup. Bagaimana risiko bisa dikurangi tergantung pada spesifikasi kanker. Tembakau yang ada pada rokok yang digunakan secara langsung dihubungkan dengan sepertiga pada semua penyakit kanker. Tidak merokok dan menghindari kontak langsung dengan asap rokok bisa sangat mengurangi risiko pada kanker paru-paru, ginjal, saluran kemih, kepala dan leher. Kanker adalah sel yang telah kehilangan pengendalian dan mekanisme normalnya, sehingga mengalami pertumbuhan yang tidak teratur. Kanker bisa terjadi dari berbagai jaringan dalam berbagai organ. Sejalan dengan pertumbuhan dan perkembangbiakannya, sel-sel kanker membentuk suatu masa dari jaringan ganas yang menyusup ke jaringan di dekatnya dan bisa menyebar ke seluruh tubuh. Kanker adalah sel yang telah kehilangan pengendalian dan mekanisme normalnya, sehingga mengalami pertumbuhan yang tidak teratur. Kanker bisa terjdi dari berbagai jaringan dalam berbagai organ. Sejalan dengan pertumbuhan dan perkembangbiakannya, sel-sel kanker membentuk suatu massa dari jaringan ganas yang menyusup ke jaringan di dekatnya dan bisa menyebar (metastasis) ke seluruh tubuh. Sel-sel kanker dibentuk dari sel-sel normal dalam suatu proses rumit yang disebut transformasi, yang terdiri dari tahap inisiasi dan promosi. Pada tahap inisiasi terjadi suatu perubahan dalam bahan 43aragra sel yang memancing sel menjadi ganas. Perubahan dalam bahan 43aragra sel ini disebabkan oleh suatu agen yang disebut karsinogen, yang bisa berupa bahan kimia, virus, radiasi (penyinaran) atau sinar matahari. Tetapi tidak semua sel memiliki kepekaan yang sama terhadap suatu karsinogen. Kelainan 43aragra 43 | N E R O
Jurnal Ilmiah NERO Vol. 1, No.2
2014
dalam sel atau bahan lainnya yang disebut 44aragrap, menyebabkan sel lebih rentan terhadap suatu karsinogen. Bahkan gangguan fisik menahunpun bisa membuat sel menjadi lebih peka untuk mengalami suatu keganasan. Pada tahap promosi, suatu sel yang telah mengalami inisiasi akan berubah menjadi ganas. 2. Text Ringkasan Algoritma Genetika Mengenal pencegahan kanker sangatlah tepat dan benar. Mengurangi risiko pada kanker tertentu mungkin bisa melalui perubahan pada makanan dan gaya hidup. Kanker bisa terjadi dari berbagai jaringan dalam berbagai organ. Sejalan dengan pertumbuhan dan perkembangbiakannya, sel-sel kanker membentuk suatu masa dari jaringan ganas yang menyusup ke jaringan di dekatnya dan bisa menyebar ke seluruh tubuh. Kanker adalah sel yang telah kehilangan pengendalian dan mekanisme normalnya, sehingga mengalami pertumbuhan yang tidak teratur. Sejalan dengan pertumbuhan dan perkembangbiakannya, sel-sel kanker membentuk suatu massa dari jaringan ganas yang menyusup ke jaringan di dekatnya dan bisa menyebar (metastasis) ke seluruh tubuh. Sel-sel kanker dibentuk dari sel-sel normal dalam suatu proses rumit yang disebut transformasi, yang terdiri dari tahap inisiasi dan promosi. Bahkan gangguan fisik menahunpun bisa membuat sel menjadi lebih peka untuk mengalami suatu keganasan. 4.5 Pengujian Waktu Proses Tabel 1. Waktu Proses dengan Populasi = 10, Generasi = 20, Elitism = 5 JudulDokumen BanyakKalimat Waktu Proses AlgoritmaGenetika (mSec) Uji1.txt 32 2.0215 Uji2.txt 20 0.2540 Uji3.txt 16 0.2865 Uji4.txt 17 0.2040 Uji5.txt 10 0.0915 Tabel 2. Waktu Proses dengan Populasi = 10, Generasi = 10, Elitism = 5 JudulDokumen BanyakKalimat Waktu Proses AlgoritmaGenetika (mSec) Uji1.txt 32 1.7324 Uji2.txt 20 0.2424 Uji3.txt 16 0.2531 Uji4.txt 17 0.1727 Uji5.txt 10 0.0790 Tabel 3. Waktu Proses dengan Populasi = 5, Generasi = 10, Elitism = 5 JudulDokumen BanyakKalimat Waktu Proses AlgoritmaGenetika (mSec) Uji1.txt Uji2.txt Uji3.txt Uji4.txt Uji5.txt
44 | N E R O
32 20 16 17 10
0.5959 0.2053 0.2246 0.1439 0.0734
Jurnal Ilmiah NERO Vol. 1 No. 2
2014
4.6 Pengujian Sumber Daya Tabel 4. Penggunaan Memori Populasi = 10, Generasi = 20, Elitism = 5 JudulDokumen BanyakKalimat Memori (bytes) Uji1.txt Uji2.txt Uji3.txt Uji4.txt Uji5.txt
32 20 16 17 10
258462 237112 235255 215409 215993
Tabel 5. Penggunaan Memori Populasi = 10, Generasi = 10, Elitism = 5 JudulDokumen BanyakKalimat Memori (bytes) Uji1.txt Uji2.txt Uji3.txt Uji4.txt Uji5.txt
32 20 16 17 10
243544 224784 227080 208816 208024
Tabel 6. Penggunaan Memory Populasi = 5, Generasi = 10, Elitism = 5 JudulDoku BanyakKali Memori (bytes) men mat Uji1.txt 32 239352 Uji2.txt 20 221168 Uji3.txt 16 222440 Uji4.txt 17 216312 Uji5.txt 10 202992 5.
Kesimpulan dan Saran
5.1 Kesimpulan Kesimpulan yang dapat diambil dari penelitian yang telah dilakukan adalah secara umum sistem ATS yang telah dibangun dapat dibagi menjadi beberapa proses. Adapun proses yang ada pada sistem adalah proses devide to word, proses pencocokan kata dasar, proses stemming, proses stopword removal, dan proses pencarian jalur terpendek pada graf dengan Algoritma Genetika, yang sebelumnya didahului dengan proses pembobotan kalimat dengan metode TF-IDF (term frequency-inverse document frequency) yang telah dimodifikasi dan pembobotan relasi antar kalimat.Rata-rata waktu proses dan penggunaan sumber daya Algoritma Genetika berbeda-beda. Untuk proses dokumen yang sama, waktu proses Algoritma Genetika dipengaruhi oleh penentuan nilai generasi, populasi dan elitism. Dapat disimpulkan bahwa nilai generasi dan populasi berbanding lurus dengan waktu proses dan penggunaan sumber daya. 5.2 Saran Untuk pengembangan sistem lebih lanjut penulis ingin menyampaikan beberapa saran, yaitu pada pengembangan selanjutnya, sistem dapat dikembangkan untuk melakukan peringkasan dokumen-dokumen dengan bahasa lain, tidak terbatas pada dokumen yang berbahasa Indonesia saja, baik untuk peringkasan dokumen tunggal (single document) maupun banyak dokumen (multi document). Perbaikan pada algoritma Genetika yang digunakan juga dapat dilakukan dalam menentukan parameter-parameter yang optimal, seperti populasi, generasi, dan elitism. 45 | N E R O
Jurnal Ilmiah NERO Vol. 1, No.2
2014
Daftar Pustaka [1] Hovy, E. H, Automated Text Summarization. In R. Mitkov (Ed.), Handbook of Computation Linguistics, Oxford: Oxford University Press, 2001. [2] Budhi, Gregorius S., dkk., “Indonesian Automated Text Summarisation”. UK Petra JurusanTeknikInformatika: Surabaya, 2005. [3]Purwarsih,Nurzaitun, Sistem Peringkas Teks Otomatis untuk Dokumen Tunggal Berita Berbahasa Indonesia dengan Menggunakan Graph-based Summarization Algorithm dan Similarity. [4] Siang, Jong Jek, “Matematika Diskrit dan Aplikasinya pada Ilmu Komputer”, Yogyakarta: Andi Yogyakarta, 2006. [5] Budhi, Gregorius S., Ibnu Gunawan danFerry Yuwono, “Algoritma Porter Stemmer For Bahasa Indonesia Untuk Pre-Processing Text Mining Berbasis Metode Market Basket Analysis”, UK Petra Jurusan Teknik Informatika: Surabaya, 2007. [6]Agusta, Ledy, “Perbandingan Algoritma Stemming Porter dengan Algoritma Nazief & Adriani untuk Stemming Dokumen Teks Bahasa Indonesia”, Konferensi Nasional Sistem dan Informatika: Bali, 2009. [7] Chakrabarti, Soumen, “Mining the Web: Discovering knowledge from hypertext data”. Morgan Kaufman: San Francisco, 2003. [8] Han, Jiawei and Kamber, Micheline, “Data Mining : Concepts and Techniques”, San Francisco : Morgan Kaufmann, 2001. [9] Budhi, Gregorius S, Arlinah I. Rahardjo, dan Hendrawan Taufik, ”Hierarchical Clustering Untuk Aplikasi Automated Text Integration”. UK Petra Jurusan Teknik Informatika, Surabaya, 2008. [10] Sjobergh, Jonas , Kenji Araki, “Extraction Based Summarisation Using Shortest Path Algorithm”, Sweden : KTH Nada, 2005 Gede Aditra Pradnyana, S.Kom., M.Kom., menyelesaikan pendidikan Sarjana pada Jurusan Ilmu Komputer, Fakultas MIPA Universitas Udayana (UNUD) di tahun 2011. Pendidikan Magister Teknik Informatika diselesaikan Tahun 2013 di Institut Teknologi Sepuluh Nopember (ITS). Penulis aktif mengajar di STMIK STIKOM Indonesia sejak tahun 2014. I Komang Ari Mogi, S.Kom., M.Kom.,menyelesaikan pendidikan Sarjana pada Jurusan Ilmu Komputer, Universitas Brawijaya di tahun 2011. Pendidikan Magister Teknik Informatika diselesaikan Tahun 2013 di Institut Teknologi Sepuluh Nopember (ITS). Penulisaktifmengajar di Universitas Udayana sejaktahun 2014
46 | N E R O
