IMPLEMENTASI PERINGKASAN OTOMATIS PADA DOKUMEN TERSTRUKTUR DENGAN METODE FAKTORISASI MATRIKS NONNEGATIF

MAKALAH SEMINAR TUGAS AKHIR PERIODE JULI 2011

IMPLEMENTASI PERINGKASAN OTOMATIS PADA DOKUMEN TERSTRUKTUR DENGAN METODE FAKTORISASI MATRIKS NONNEGATIF Arlisa Yuliawati1, Diana Purwitasari2, Umi Laili Yuhana3 Teknik Informatika, Fakultas Teknologi Informasi, ITS email : [email protected], [email protected], [email protected] beberapa perangkat lunak untuk peringkasan dokumen telah lebih dulu dikembangkan, diantaranya SUMMARIST, The MEAD Summarizer, LexRank, Corporum Summarizer-Cognit AS, dan sebagainya (Dalianis, 2005; Radev, 2003).

Abstract—Salah satu kegunaan dari peringkasan teks otomatis adalah untuk memudahkan proses pencarian kata kunci pada mesin pencari. Pencarian kata kunci lebih baik jika dilakukan terhadap dokumendokumen yang sudah teringkas, sehingga hasil pencarian bisa lebih tepat. Oleh karenanya, peringkasan harus bias menghasilkan informasi inti dari suatu dokumen yang diringkas, yang mana dapat dilakukan dengan pengambilan topik-topik penting dari setiap bagian dokumen.

Dokumen terstruktur yang dimaksud dalam makalah ini menggambarkan pengorganisasian dokumen ke dalam struktur-struktur hirarki tertentu. (Lemone, 1998). Peringkasan pada dokumen terstruktur dimaksudkan untuk mengambil pokok bahasan dari setiap bagian sehingga ringkasan yang dihasilkan lebih dapat menggambarkan intisari dokumen yang diringkas.

Dalam makalah Tugas Akhir ini dijelaskan mengenai peringkasan yang dikhususkan pada dokumen terstruktur untuk mengambil kalimat-kalimat penting yang mewakili maksud utama dokumen. Dengan ekstraksi matriks term-by-sentences dari dokumen menggunakan metode Faktorisasi Matriks Nonnegatif (Nonnegative Matrix Factorization/NMF), diharapkan proses peringkasan dapat memberi hasil ringkasan yang lebih bermakna. Evaluasi dilakukan untuk mengetahui hasil peringkasan dokumen. Dengan metode NMF, hasil peringkasan cenderung lebih baik dan bermakna.

Berdasarkan metodenya, peringkasan dokumen dapat dibedakan menjadi peringkasan generik (generic summarization) dan peringksan berdasarkan query (query-based summarization) (Lee, Park, Ahn, & Kim, 2009). Metode pertama merupakan proses peringkasan dengan mengambil poin penting dokumen secara semantik dengan pengolahan kata-kata dalam dokumen, sedangkan pada metode kedua, peringkasan dilakukan dengan memperhatikan kata kunci dalam menghasilkan ringkasan. Dalam jurnal tersebut juga dijelaskan bahwa generic summarization dibagi lagi ke dalam dua bagian, yaitu metode supervised dan unsupervised. Pada metode supervised, diperlukan data training dari sekumpulan orang untuk menghasilkan ringkasan suatu dokumen, sehingga ketika terdapat dokumen yang berbeda, diperlukan pula data training yang berbeda. Metode supervised ini hanya dapat ditetapkan untuk model data tertentu. Sedangkan pada metode unsupervised, peringkasan tidak memerlukan data training seperti yang dilakukan pada metode supervised.

Kata kunci : Peringkasan Otomatis, Dokumen Terstruktur, Faktorisasi Matriks Nonnegatif, Multiplicative Update, Generic Relevance of Sentence (GRS). I. PENDAHULUAN Dalam proses pencarian dokumen pada halaman web, pencarian kata kunci terhadap koleksi dokumen pada umumnya dilakukan pada keseluruhan isi dokumen. Dengan demikian terkadang proses temu kembali informasi memerlukan waktu yang lama. Padahal pengguna cenderung mengharapkan hasil yang tepat dengan waktu singkat dalam proses pencarian informasi. Oleh karena itu sebaiknya proses pencocokan kata kunci terhadap koleksi dokumen dilakukan pada inti dokumen yang memiliki isi lebih singkat tentunya.

II. PENELITIAN TERDAHULU Salah satu metode peringkasan secara unsupervised yang pernah dikembangkan adalah metode peringkasan menggunakan LSA (Latent Semantik Analysis) (Gong & Liu, 2001). Metode ini menggunakan metode SVD (Singular Value Decomposition) untuk proses dekomposisi matriks. Salah satu matriks yang dihasilkan adalah matriks yang merepresentasikan topik dalam suatu kalimat. Matriks tersebut cenderung bersifat non sparse dan berisi bilangan negatif dan nonnegatif pada elemenelemennya. Karena sifat matriks yang non sparse (padat) itulah, kecenderungan suatu kalimat mengandung suatu topik tertentu lebih sulit dikenali. Hal itu dikarenakan

Hal tersebut melatarbelakangi diperlukannya sistem peringkas otomatis pada suatu dokumen. Peringkas teks otomatis (Automatic Text Summarization) sendiri merupakan perangkat berbasis komputer untuk menghasilkan teks yang lebih pendek dari teks aslinya namun masih menyimpan poin utama dari teks yang diringkas (Dalianis, 2005). Untuk keperluan tersebut,

1

MAKALAH SEMINAR TUGAS AKHIR PERIODE JULI 2011 Bentuk 𝐴 ≈ 𝑊𝐻 pada Persamaan (1) dapat dijelaskan sebagai bentuk similar antara matriks A dengan hasil perkalian dari matriks W dan H. Untuk mencapai kondisi similar antara A dengan W*H tersebut, diperlukan suatu kriteria yang dapat dikatakan sebagai Cost Function. Beberapa model Cost Function dapat dibangun dengan pengukuran jarak antara dua matriks nonnegatif A dan B, seperti dijelaskan dalam Persamaan (2) (Lee & Seung, 2001).

setiap elemen pada vektor kolom matriks hasil dekomposisi tersebut pasti memiliki nilai yang merepresentasikan persentase kecenderungan kalimat terhadap suatu topik. Hal itulah yang memunculkan metode dekomposisi matriks yang menghasilkan matriks yang lebih sparse dan bersifat nonnegatif sebagai metode peringkasan dokumen. Metode ini adalah dekomposisi matriks dengan proses faktorisasi matriks nonnegatif (Nonnegative Matrix Factorization/NMF) yang dapat menghasilkan matriks yang merepresentasikan kaitan kalimat dengan topik tersembunyi (hidden topic). Elemen-elemen matriks yang lebih sparse ini lebih mudah digunakan untuk mengetahui kecenderungan suatu kalimat terhadap suatu topik tertentu sehingga memiliki kemungkinan lebih besar dalam mengekstrak kalimat penting (Lee, Park, Ahn, & Kim, 2009). Dengan perpaduan pengambilan ringkasan pada setiap section dokumen dan menggunakan metode Faktorisasi Matriks Nonnegatif, diharapkan ringkasan yang dihasilkan lebih bermakna dan dapat dengan mudah dimengerti.

‖𝐴 − 𝐵‖2 = ��𝐴𝑖𝑗 − 𝐵𝑖𝑗 � 𝑖𝑗

Dalam Tugas Akhir ini, proses pengukuran menuju kondisi 𝐴 ≈ 𝑊𝐻 menggunakan aturan Frobenius Norm (Lee, Park, Ahn, & Kim, 2009) yang dibuat berdasarkan aturan Cost Function seperti dijelaskan pada Persamaan (2). Dengan aturan ini, terdapat dua buah matriks yang akan dihitung jarak keduanya, yaitu matriks A dengan perkalian antara matriks W dan H. Aturan Frobenius Norm yang digunakan dalam metode dekomposisi NMF dijelaskan pada Persamaan (3) berikut.

Faktorisasi matriks nonnegatif (NMF) merupakan metode dekomposisi matriks term-by-sentences A yang berukuran mxn menjadi matriks W (mxr) dan H (rxn) yang hanya bernilai bilangan nonnegatif dan bersifat lebih sparse (Lee, Park, Ahn, & Kim, 2009). Metode dekomposisi dengan NMF dapat dinyatakan dalam bentuk persamaan berikut. 𝐴 ≈ 𝑊𝐻

𝛩𝐸 (𝑊, 𝐻) ≡ ||𝐴 −

(1)

c

Term 1

d

Term 2

e

f

Term 3

g

h

Term 4

(i)

a

b

c

d

e

f

𝑚

𝑛

𝑟

2

𝑙=1

(3)

≡ � � �𝐴𝑗𝑖 − � 𝑊𝑗𝑙 𝐻𝑙𝑖 � 𝑗=1 𝑖=1

Dengan demikian bentuk Frobenius Norm yang digunakan dalam metode NMF seperti pada Persamaan (3) menunjukkan hasil perhitungan Frobenius Norm untuk selisih masing-masing elemen dari matriks A dengan matriks hasil perkalian matriks W dan H. III.1. MULTIPLICATIVE UPDATE RULE

Dalam pembahasan mengenai peringkasan dokumen dengan metode NMF, matriks A menunjukkan matriks yang berisi bobot term dalam kalimat dan berukuran jumlah term (m) x jumlah kalimat (n). Sedangkan matriks W merupakan matriks berukuran mxr dan matriks H berukuran rxn. Nilai r dinyatakan sebagai 10% dari nilai n (Lee, Park, Ahn, & Kim, 2009). b

𝑊𝐻||2𝐹

Bentuk umum dari Frobenius Norm dijelaskan dalam 2 bentuk persamaan ||𝐴||2𝐹 = ∑𝑖,𝑗�𝑎𝑖𝑗 � . Nilai variabel A menunjukkan suatu matriks, sehingga nilai Frobenius Norm dari A atau ||𝐴||2𝐹 dijelaskan dalam bentuk jumlah kuadrat dari masing-masing elemen matriks penyusun matriks A.

Matriks W merepresentasikan matriks term yang memiliki topik hidden di dalamnya, disebut sebagai Non-negative Semantic Feature Matrix (NSFM), dan ditunjukkan dalam setiap vektor barisnya. Sedangkan matriks H merepresentasikan variabel yang menyimpan bobot topik hidden dalam setiap kalimat, Non-negative Semantic Variable Matrix (NSVM), ditunjukkan dalam vektor kolomnya, seperti ditunjukkan pada Gambar 1.

a

(2)

Persamaan (2) menunjukkan aturan Cost Function untuk jarak antara A dan B yang memiliki batas bawah nol, dan kondisi terpenuhi jika dan hanya jika A = B.

FAKTORISASI MATRIKS NONNEGATIF

III.

2

Multiplicative Update berfungsi untuk meng-update nilai matriks W dan H untuk mencapai kondisi A≈WH. Oleh karena itu terdapat suatu persoalan, dimana nilai ||𝐴 − 𝑊𝐻||2𝐹 harus kecil. Salah satu cara yang digunakan adalah aturan Multiplicative Update ini. Dimana dengan adanya aturan ini diharapkan nilai dari ||𝐴 − 𝑊𝐻||2𝐹 tidak meningkat (Lee & Seung, 2001). Persamaan update nya sendiri dijelaskan pada Persamaan (4) dan (5). (𝑊 𝑇 𝐴)𝛼𝜇 𝐻𝛼𝜇 ← 𝐻𝛼𝜇 (𝑊 𝑇 𝑊𝐻)𝛼𝜇

Kalimat 1

Kalimat 3 Kalimat 2

(4)

(ii)

Gambar 1. Ilustrasi Representasi Matriks W (i) dan Matriks H (ii)

2

MAKALAH SEMINAR TUGAS AKHIR PERIODE JULI 2011

𝑊𝑖𝛼 ← 𝑊𝑖𝛼

(𝐴𝐻 𝑇 )𝑖𝛼 (𝑊𝐻𝐻𝑇 )𝑖𝛼

ini persamaan dasar pada model vector space (Garcia, 2006). 𝐷 𝑤𝑖𝑗 = 𝑡𝑖𝑗 ∗ log10 � � 𝑑𝑓𝑖

(5)

Proses update seperti nampak pada Persamaan (4) dan Persamaan (5), perhitungan perkalian dan pembagian matriks nya dilakukan dengan perkalian dan pembagian antar elemen matriks, seperti ditunjukkan oleh indeks ke𝛼𝜇 dan indeks ke-𝑖𝛼 pada matriks W dan H.

(8)

Pada Persamaan (8), 𝑤𝑖𝑗 menunjukkan bobot term ke-i pada dokumen ke-j, 𝑡𝑖𝑗 menunjukkan termfrequency/jumlah kemunculan term ke-i pada dokumen ke-j yang seringkali dinyatakan sebagai term-frequency yang dinormalisasi yang dijelaskan dalam bentuk

III.2. GENERIC RELEVANCE OF SENTENCE (GRS)

𝑡𝑓𝑖𝑗 =

Proses ekstraksi kalimat ringkasan dilakukan dengan mengambil n kalimat dengan skor kalimat tertinggi (Lee, Park, Ahn, & Kim, 2009). Skor kalimat diperoleh dari perhitungan Generic Relevance of Sentence (GRS) setiap kalimat. Perhitungan nilai GRS melibatkan elemenelemen matriks H sebagai matriks yang merepresentasikan variabel yang berisi bobot topik hidden dalam setiap kalimat. Penjelasan persamaan GRS untuk setiap kalimat dapat dilihat pada Persamaan (6) dan (7).

𝑖=1

. Nilai 𝑚𝑎𝑥�𝑡𝑖𝑗 � menunjukkan jumlah

maksimum term yang muncul pada sebuah kalimat. Bentuk idf (inverse document frequency) pada Persamaan 𝐷 (8) dijelaskan dalam bentuk logaritma dari . 𝑑𝑓𝑖 𝑑𝑓𝑖

menunjukkan document-frequency (jumlah dokumen yang berisi term ke-i) sedangkan nilai 𝐷 menunjukkan jumlah koleksi dokumen. Dalam kaitannya dengan peringkasan dokumen, perhitungan idf dilakukan pada term terhadap kalimat. Beberapa jenis persamaan pembobotan (Lee, Park, Ahn, & Kim, 2009) yang digunakan dalam implementasi Tugas Akhir ini dijelaskan pada Persamaan (9) hingga Persamaan (16).

𝑟

𝐺𝑅𝑆𝑗 = � �𝐻𝑖𝑗 . 𝑤𝑒𝑖𝑔ℎ𝑡(𝐻𝑖∗ )�

𝑡𝑖𝑗

𝑚𝑎𝑥�𝑡𝑖𝑗 �

(6)

Pada Persamaan (6), 𝐺𝑅𝑆𝑗 menunjukkan skor untuk setiap vektor kolom ke-j pada matriks H. Sedangkan nilai weight yang tertera pada Persamaan (6) tersebut merupakan bobot untuk elemen (i,j) pada matriks H yang dijelaskan dalam Persamaan (7) berikut. ∑𝑛𝑞=1 𝐻𝑖𝑞 𝑤𝑒𝑖𝑔ℎ𝑡(𝐻𝑖∗ ) = 𝑟 ∑𝑝=1 ∑𝑛𝑞=1 𝐻𝑝𝑞

No Weight Merupakan perhitungan bobot term yang murni dihitung berdasarkan jumlah kemunculan suatu term pada suatu koleksi dengan menggunakan persamaan tf (termfrequency) tanpa normalisasi. 𝑤𝑖𝑗 = 𝑡𝑖𝑗

(7)

(9)

Keterangan Persamaan (6) dan (7): 𝑟 = jumlah baris pada matriks H 𝑖 = indeks baris, dengan 1 < i < r 𝐻𝑖𝑗 = elemen matriks H pada posisi (i,j), dengan j adalah indeks kolom yang merepresentasikan kalimat (1 < j < n). 𝑛 = jumlah kalimat 𝑞 = indeks kolom kalimat, dengan 1 < q < n 𝐻𝑖𝑗 = elemen-elemen matriks H pada posisi baris i tertentu 𝑝 = indeks baris, dengan 1 < p < r 𝐻𝑖𝑗 = elemen-elemen matriks H pada posisi (p,q), yang merupakan keseluruhan elemen pada matriks H

Ordinary Weight

P

P

Merupakan perhitungan bobot term berdasar prinsip tf*idf dengan menggunakan tf tanpa normalisasi (𝑡𝑖𝑗 ). 𝑁 � 𝑤𝑖𝑗 = 𝑡𝑖𝑗 ∗ log10 � 𝑛(𝑖)

P

P

(10)

Pada Persamaan (10), N menunjukkan jumlah kalimat dalam satu dokumen sedangkan 𝑛(𝑖) menunjukkan jumlah kalimat yang mengandung term ke-i. Binary Weight

IV. PEMBOBOTAN KATA UNTUK MEMBENTUK MATRIKS TERM-BY-SENTENCES

Merupakan perhitungan bobot term menggunakan model tf biner. Jika term ke-i pernah muncul dalam kalimat ke-j setidaknya satu kali, maka bobotnya 1, jika tidak maka bobotnya nol.

Untuk membangun matriks term-by-sentences yang digunakan dalam proses dekomposisi matriks, diperlukan pembobotan setiap term yang telah diambil bentuk dasarnya menggunakan metode Porter’s Stemming. Bobot masing-masing term ini yang akan menyusun elemenelemen matriks term-by-sentences.

𝑤𝑖𝑗 = �

1, 𝑗𝑖𝑘𝑎 𝑡𝑒𝑟𝑚 𝑖 𝑚𝑢𝑛𝑐𝑢𝑙 𝑚𝑖𝑛𝑖𝑚𝑎𝑙 𝑠𝑒𝑘𝑎𝑙𝑖 𝑑𝑎𝑙𝑎𝑚 𝑘𝑎𝑙𝑖𝑚𝑎𝑡 � 0, 𝑗𝑖𝑘𝑎 𝑠𝑒𝑏𝑎𝑙𝑖𝑘𝑛𝑦𝑎

(11)

Modified Binary Weight

Bentuk modifikasi dari Binary Weight, dimana kondisi ketika term ke-i muncul setidaknya sekali dalam kalimat maka bobotnya merupakan perhitungan idf, jika tidak maka bobot term ke-i dalam kalimat ke-j adalah nol.

Persamaan pembobotan term yang sering digunakan adalah persamaan tf-idf pada model vector space. Berikut

3

MAKALAH SEMINAR TUGAS AKHIR PERIODE JULI 2011

𝑤𝑖𝑗 = �

log10 �

𝑁 � , 𝑗𝑖𝑘𝑎 𝑡𝑒𝑟𝑚 𝑖 𝑚𝑢𝑛𝑐𝑢𝑙 𝑚𝑖𝑛𝑖𝑚𝑎𝑙 𝑠𝑒𝑘𝑎𝑙𝑖 𝑑𝑎𝑙𝑎𝑚 𝑘𝑎𝑙𝑖𝑚𝑎𝑡 � 𝑛(𝑖) 0, 𝑗𝑖𝑘𝑎 𝑠𝑒𝑏𝑎𝑙𝑖𝑘𝑛𝑦𝑎

Persamaan (9) hingga Persamaan (16) matriks A yang berukuran term-by-sentences. 6. Melakukan proses dekomposisi matriks dengan metode Faktorisasi Matriks Nonnegatif pada matriks term-by-sentences untuk menghasilkan matriks H (termasuk proses Multiplicative Update di dalamnya). 7. Menghitung skor setiap kalimat menggunakan metode Generic Relevance of Sentence (GRS) menggunakan matriks H yang merepresentasikan kalimat dalam dokumen. 8. Memilih n kalimat dengan skor GRS tertinggi. Nilai n ditentukan oleh pengguna.

(12)

Augmented Weight

Merupakan bentuk pembobotan menggunakan tf yang dinormalisasi dan dimodifikasi dengan penambahan dan perkalian dengan konstanta 0.5 pada persamaan tf normalisasinya. 𝑤𝑖𝑗 = 0.5 + (0.5 ∗ 𝑡𝑓𝑖𝑗 ) Nilai 𝑡𝑓𝑖𝑗 pada normalisasi.

(13)

Persamaan (13) menunjukkan nilai tf

Gambaran setiap langkah lebih detil dijelaskan pada Gambar 2. Sistem utama perangkat lunak dibagi ke dalam dua bagian utama, yaitu bagian prapemrosesan dan bagian ekstraksi hasil peringkasan. Bagian prapemrosesan terdiri atas proses ekstraksi teks dari dokumen HTML, proses tokenisasi untuk mendapatkan term penting pada dokumen, penerapan proses stemming dan perhitungan bobot setiap term untuk membangun matriks term-bysentences. Sedangkan tahap ekstraksi hasil peringkasan dijelaskan ke dalam tahap ekstraksi matriks term-bysentences, tahap dekomposisi matriks dengan metode NMF, perhitungan skor GRS per kalimat kemudian diakhiri dengan proses ektraksi teks hasil ringkasan dokumen.

Ordinary Augmented Weight Merupakan perhitungan tf*idf menggunakan bentuk tf normalisasi (𝑡𝑓𝑖𝑗 ) yang digunakan pada perhitungan Augmented Weight dan dikalikan dengan idf. 𝑁 𝑤𝑖𝑗 = �0.5 + (0.5 ∗ 𝑡𝑓𝑖𝑗 )� ∗ log10 � � 𝑛(𝑖)

(14)

Logarithm Weight

Bentuk modifikasi tf tanpa normalisasi dalam bentuk logaritmik dari penjumlahan nilai term-frequency setiap term dengan konstanta 1. 𝑤𝑖𝑗 = log10 �1 + 𝑡𝑖𝑗 � (15)

Pada Persamaan (15) 𝑡𝑖𝑗 menunjukkan nilai tf tanpa normalisasi. Ordinary Logarithm Weight

Bentuk tf*idf dengan menggunakan model tf logaritmik seperti yang diterapkan pada Persamaan (15). 𝑁 𝑤𝑖𝑗 = log10 �1 + 𝑡𝑖𝑗 � ∗ log10 � � 𝑛(𝑖) (16)

V. IMPLEMENTASI EKSTRAKSI RINGKASAN DENGAN METODE FAKTORISASI MATRIKS NONNEGATIF Langkah-langkah melakukan peringkasan menggunakan metode Faktorisasi Matriks Nonnegatif (Lee, Park, Ahn, & Kim, 2009) yang diterapkan pada dokumen terstruktur adalah sebagai berikut: 1. Melakukan ekstraksi teks dari dokumen HTML. 2. Memecah teks ke dalam kalimat-kalimat 3. Memecah kalimat ke dalam kata-kata dan menghilangkan stopword dan penghilangan karakter – karakter aneh. 4. Mengambil bentuk kata dasar dengan metode Porter’s Stemmer 5. Menghitung bobot setiap term dengan salah satu persamaan pembobotan yang ditunjukkan pada

Gambar 2. Arsitektur Perangkat Lunak

Dari bagan pada Gambar 2 tersebut dapat diketahui bahwa pengguna memiliki peran dalam perangkat lunak yaitu dengan memeberi masukan kepada perangkat lunak berupa dokumen HTML yang akan diringkas, jenis pembobotan dan rentang bilangan acak yang digunakan.

4

MAKALAH SEMINAR TUGAS AKHIR PERIODE JULI 2011 Empat komponen luar yang digunakan dalam pembangunan perangkat lunak peringakas dokumen terstruktur ini antara lain pustaka jsoup untuk untuk ekstraksi isi dokumen HTML, dan JAMA untuk proses perhitungan matriks. Kemudian algoritma Porter’s Stemmer untuk proses pengambilan kata dasar, dan database yang digunakan sebagai storage untuk hasil pengolahan dokumen. Hasil implementasi perngkat peringkas pada dokumen terstruktur ini berupa perangkat lunak berbasis desktop. Hasil pengambilan gambar untuk tampilan antarmuka ditampilkan pada Gambar 3 dan Gambar 5berikut.

Gambar 5. Tampilan Antarmuka ketika Peringkasan Selesai

Tampilan yang ditunjukkan pada Gambar 5 menunjukkan tampilan antarmuka ketika proses peringkasan telah selesai dilakukan. Di dalamnya terdapat notifikasi untuk pengguna ketika perangkat lunak telah selesai melakukan peringkasan pada dokumen. VI. UJI COBA DAN EVALUASI Terdapat dua macam uji coba yang dilakukan, yaitu uji coba parameter dan uji coba hasil peringkasan. Uji coba paramater dilakukan untuk mendapatkan parameterparameter yang relevan untuk diimplementasikan pada metode Faktorisasi Matriks Nonnegatif. Uji coba peringkasan digunakan untuk mengetahui kebenaran ringkasan yang dihasilkan.

Gambar 3. Tampilan Antarmuka Utama Perangkat Lunak

Gambar 3 menunjukkan tampilan utama perangkat lunak ketika pertama kali dijalankan. Terdapat menu-menu pilihan yang memungkinkan pengguna untuk member masukan-masukan yang digunakan dalam proses peringkasan.

Data uji yang digunakan ada dua macam, yaitu data uji dari dokumen jurnal dari situs Science Direct sejumlah enam puluh data dan satu paragraf sederhana yang dipakai dalam uji coba parameter. Contoh data dokumen HTML dan satu paragraf sederhana yang digunakan sebagai data uji ditunjukkan pada Tabel 1 dan Gambar 6. Tabel 1. Data Uji 1 : Contoh Sepuluh Data Dokumen HTML dari Total Enam Puluh Data No Judul Dokumen A complexity perspective on collaborative decision making in 1. organizations The ecology of group-performance An empirical study of the effectiveness of multimedia 2. disclosure of informed consent A technology mediated learning perspective An investigation of moderators of the link between technology 3. use in the supply chain and supply chain performance Building and leveraging information in dynamic environments 4. The role of IT infrastructure flexibility as enabler of organizational responsivene Communicative practices in an online financial forum during 5. abnormal stock market behavior Consumer feelings and behaviours towards well designed 6. websites Effects of initial and ongoing trust in IT outsourcing A 7. bilateral perspective Family and work-related consequences of addiction to 8. organizational pervasive technologies Identifying key factors affecting transnational knowledge 9. transfer Information technology and productivity Empirical evidence 10. from the Chinese electronics industry

Gambar 4. Tampilan Antarmuka ketika Proses Peringkasan

Gambar 3 menampilkan proses selama terjadi peringkasan dokumen. pada bagian ini ditampilkan proses yang sedang berjalan serta nilai yang dihasilkan pada setiap iterasi update matriks. Dengan adanya bagian ini, pengguna dapat mengetahui sejauh mana proses peringkasan sedang berjalan.

5

MAKALAH SEMINAR TUGAS AKHIR PERIODE JULI 2011 Sepuluh contoh data uji pada Tabel 1 merupakan dokumen-dokumen yang telah diunduh dari situs Science Direct yang berada pada domain IT & Management. Data tersebut digunakan dalam uji coba hasil peringkasan.

2.

Uji coba bertujuan untuk mengetahui rentang bilangan acak di antara rentang 0.05 hingga 0.25 (pada uji coba sebelumnya) yang memerlukan waktu eksekusi paling kecil. Uji coba ini dilakukan menggunakan dokumen jurnal berjudul “IT investments disclosure, information quality, and factors influencing managers’ choices”. Uji coba dilakukan sebanyak sepuluh kali untuk masingmasing rentang bilangan yang ditentukan. Hasil uji coba ini digunakan sebagai pertimbangan poemilihan rentang bilangan acak yang sesuai untuk inisialisasi matriks term (W) dan mastriks kalimat (H).

Non-negative matrix factorization (NMF) has previously been shown to be a useful decomposition for multivariate data. Two different multiplicative algorithms for NMF are analyzed. They differ only slightly in the multiplicative factor used in the update rules. One algorithm can be shown to minimize the conventional least squares error while the other minimizes the generalized Kullback-Leibler divergence. The monotonic convergence of both algorithms can be proven using an auxiliary function analogous to that used for proving convergence of the Expectation-Maximization algorithm. The algorithms can also be interpreted as diagonally rescaled gradient descent, where the rescaling factor is optimally chosen to ensure convergence. Gambar 6. Data Uji 2 : Paragraf Sederhana

VI.1.

Hasil pengamatan terhadap waktu eksekusi yang dihasilkan setiap rentang bilangan ditunjukkan pada Tabel 3 berikut.

UJI COBA PARAMETER

Data uji yang digunakan dalam uji coba parameter ini adalah data paragraf sederhana seperti pada Gambar 6. Terdapat empat macam skenario uji coba parameter. 1.

Tabel 3. Rata-rata Waktu Eksekusi pada Setiap Rentang Bilangan Acak Rentang Bilangan Acak Waktu Eksekusi (menit) 0.1 - 0.15 4.539 0.1 - 0.2 4.582 0.1 - 0.25 4.352 0.15 - 0.2 5.4247 0.15 - 0.25 4.961 0.2 - 0.25 5.2687

Penentuan rentang bilangan acak berdasar nilai Frobenius Norm.

Uji coba ini bertujuan untuk mendapatkan rentang nilai acak yang menghasilkan nilai Frobenius Norm lebih kecil. Pada uji coba ini dilakukan lima kali uji coba untuk masing-masing rentang bilangan acak pada masingmasing persamaan pembobotan. Dari uji coba tersebut diperoleh data rata-rata hasil pengamatan nilai Frobenius Norm yang dihasilkan oleh masing-masing rentang bilangan acak yang ditentukan. Rata-rata nilai Frobenius Norm yang kecil menunjukkan jarak yang dekat antara matriks A dengan hasil perkalian matriks W dan H.

Hasil yang ditunjukkan oleh Tabel 3 menghasilkan rentang bilangan antara 0.1 hingga 0.25 yang memerlukan waktu eksekusi paling kecil (4.352 menit). Pada implementasi selanjutnya digunakan rentang bilangan acak tersebut untuk inisialisasi matriks awal. VI.2.

Tabel 2. Rata-rata Nilai Frobenius Norm pada Setiap Rentang Nilai Acak

Batas Bawah

Batas Atas

0.00 0.01 0.01 0.05 0.05 0.05 0.10 0.50 2.00 3.00

1.00 0.02 0.05 0.10 0.25 0.50 0.50 0.70 4.00 7.00

Interval

Rata-rata Nilai Frobenius Norm

1.00 0.01 0.04 0.05 0.20 0.45 0.40 0.20 2.00 4.00

3.6500 ≈ 3.7 3.6559 ≈ 3.7 3.6567 ≈ 3.7 3.6575 ≈ 3.7 3.6498 ≈ 3.6 3.6594 ≈ 3.7 3.6549 ≈ 3.7 3.6603 ≈ 3.7 3.7021 ≈ 3.7 3.6543 ≈ 3.7

UJI COBA HASIL PERINGKASAN

Pada uji coba ini terdapat dua macam uji coba, yang pertama pengamatan nilai Kappa yang dihasilkan oleh ringkasan menggunakan metode NMF dengan ringkasan kunci. Uji coba kedua adalah perbandingan nilai Kappa antara metode NMF dengan metode LSA yang masingmasing perhitungan Kappanya diperoleh dari pembandingan dengan ringkasan kunci.

Hasil rata-rata nilai Frobenius Norm pada setiap rentang bilangan acak dapat dilihat pada Tabel 2.

Rentang Bilangan

Penentuan rentang bilangan acak berdasarkan waktu eksekusi

Perhitungan Tingkat Kesepakatan Dua Observer Menggunakan Kappa Salah satu metode untuk evaluasi hasil peringkasan adalah dengan Kappa Statistics (Hori, Hirao, & Isozaki, 2004). Metode ini memungkinkan proses perhitungan tingkat kesepakatan/agreement diantara dua interobserver atau lebih atas sebuah kondisi/permasalahan yang sama secara analisis statistik (Vierra & Garrett, 2005).

Hasil yang diperoleh dari uji coba parameter untuk menentukan rentang bilangan acak berdasarkan nilai Frobenius Norm yang dihasilkan, diperoleh rentang bilangan antara 0.05 hingga 0.25 yang menghasilkan nilai Frobenius Norm paling kecil.

Secara umum perhitungan Kappa dilakukan berdasarkan perbedaan tingkat kesepakatan antara berapa banyak kesepakatan yang diperoleh (observed agreement) dibandingkan dengan berapa banyak kesepakatan yang diharapkan (expected agreement). Tampilan perhitungan

6

MAKALAH SEMINAR TUGAS AKHIR PERIODE JULI 2011 data dapat dilihat pada . Secara perhitungan statistik Kappa dinyatakan dalam Persamaan (17) berikut. (𝑝𝑜 − 𝑝𝑒 ) 𝜅= (1 − 𝑝𝑒 )

Tabel 5 menunjukkan intepretasi hasil nilai Kappa yang berarti tingkat kesepakatan yang terjadi antara dua hasil ringkasan yang dibandingkan. Semakin tinggi nilai Kappa, intepretasi yang dihasilkan semakin baik.

(17)

Pada Persamaan (17), 𝜅 menyatakan nilai Kappa, p o menyatakan observed agreement, dan p e menyatakan expected agreement.

Uji coba pertama bertujuan untuk mengetahui persamaan pembobotan yang menghasilkan nilai Kappa terbaik. Uji coba dilakukan pada masing-masing persamaan pembobotan dengan menggunakan enam puluh data uji. Nilai Kappa yang tinggi menunjukkan tingkat kesepakatan yang tinggi antara dua ringkasan yang dibandingkan.

Berdasarkan Tabel 4, a dan d menyatakan jumlah kedua observer setuju, sedangkan b dan c menytakan jumlah kedua observer tidak setuju. Ketika nilai b dan c bernilai 0 maka nilai observed agreement (p o ) adalah 1 atau 100%, sebaliknya, jika a dan d bernilai 0 maka p o bernilai 0 (Vierra & Garrett, 2005).

Observer 2

Tabel 4. Variasi Interobserver Observer 1 Hasil Ya Tidak Ya a b Hasil Tidak c d Total n1 n0

Hasil uji coba perhitungan tingkat kesepakatan dua ringkasan dengan metode Kappa antara ringkasan dengan metode NMF dan ringkasan kunci ini dapat dilihat pada Tabel 6 berikut. Tabel 6. Rata-rata Nilai Kappa untuk setiap Persamaan Pembobotan Menggunkaan 60 Dokumen Rata-rata Kappa Persamaan pembobotan Intepretasi Kappa 60 dokumen No Weight 0.353515 Fair Logarithm Weight 0.323237 Fair Binary Weight 0.245306 Fair Ordinary Weight 0.201167 Fair Ordinary Logarithm Weight 0.1859 Slight Modified Binary Weight 0.145711 Slight Augmented Weight 0.125539 Slight Ordinary Augmented Weight -1.26362 Poor

Total m1 m0 n

Perhitungan p o dan p e dijelaskan dalam Persamaan (18) berikut. 𝑛1 𝑚1 𝑛0 𝑚0 𝑝𝑒 = �� � ∗ � �� + �� � ∗ � �� 𝑛 𝑛 𝑛 𝑛 (18)

Pada Persamaan (18), n 1 menyatakan jumlah persetujuan observer 1, sedangkan n 0 menyatakan jumlah total observer 2 tidak setuju dengan hasil. Demikian halnya dengan m 1 dan m 0 secara berurutan keduanya menyatakan tingkat persetujuan dan ketidaksetujuan dari observer 2.

Dari hasil uji coba pada Tabel 6 diperoleh dua persamaan yaitu No Weight dan Logarithm Weight yang menghasilkan nilai Kappa tertinggi dengan intepretasi nilai Kappa adalah Fair. Persamaan No Weight menunjukkan model persamaan tf murni (perhitungan jumlah kemunculan term dalam kalimat), sedangkan persamaan Logarithm Weight merupakan bentuk persamaan tf logaritmik.

Sedangkan p o menyatakan probabilitas dari jumlah dimana kedua observer (a dan d) setuju dibandingkan dengan jumlah total (n). 𝑎+𝑑 𝑝𝑜 = 𝑛

Uji coba yang kedua bertujuan untuk membandingkan nilai Kappa yang diperoleh dari metode NMF dengan metode LSA. Uji coba ini dilakukan dengan enam puluh data uji menggunakan persamaan pembobotan yang telah diperoleh pada uji coba sebelumnya, yaitu No Weight yang memiliki nilai Kappa tertinggi. Dilakukan dua macam pengujian, yaitu perhitungan nilai Kappa antara ringkasan metode NMF dengan ringkasan kunci dan perhitungan nilai Kappa antara ringkasan metode LSA dengan ringkasan kunci. Hasil perhitungan Kappa menunjukkan bahwa rata-rata nilai Kappa yang dihasilkan ringkasan dengan metode NMF lebih besar (0.353515/Fair) daripada ringkasan hasil metode LSA (0.009101/Slight). Sehingga dapat diartikan bahwa ringkasan dengan metode NMF lebih bagus daripada ringkasan dengan metode LSA.

(19)

Penerapan perhitungan Kappa pada Tugas Akhir ini adalah dengan menjadikan hasil ringkasan perangkat lunak dan hasil ringkasan kunci yang telah ditentukan sebagai dua observer yang berbeda. Dengan demikian kondisi yang dibandingkan antara kedua ringkasan sebagai observer adalah ketersediaan kalimat-kalimat ringkasan yang menjadi ringkasan kunci pada ringkasan hasil keluaran perangkat lunak. Sehingga p o dalam hal ini menyatakan probabilitas kalimat yang terpilih menjadi kalimat penyusun ringkasan pada kedua observer. Tabel 5. Intepretasi Nilai Kappa

Nilai 𝜅 <0 0 – 0.2 0.21 – 0.4 0.41 – 0.6 0.61 – 0.8 0.81 – 1

Strength of Agreement Poor Slight Fair Moderate Substatsial Almost perfect

7

MAKALAH SEMINAR TUGAS AKHIR PERIODE JULI 2011 VII. EVALUASI HASIL UJI COBA

peringkasan dokumen. Melalui perhitungan Kappa antara dua ringkasan, dapat diketahui tingkat kesepakatan hasil ringkasan menggunakan metode NMF dengan ringkasan kunci yang diharapkan. Berdasar dua macam uji coba hasil ringkasan diperoleh bahwa ringkasan menggunakan metode NMF cenderung menghasilkan nilai Kappa yang tinggi dan terbukti lebih bagus dibandingkan dengan ringkasan menggunakan metode LSA.

Berdasarkan uji coba yang telah dilakukan pada Subbab VI.1 dan VI.2 dapat dilakukan evaluasi mengenai hasil uji coba. 1.

2.

3.

Dari uji coba penentuan rentang bilangan acak yang menghasilkan nilai Frobenius Norm paling kecil diperoleh rentang bilangan acak terbaik adalah antara 0.05 hingga 0.25. Namun berdasar waktu eksekusi terkecil pada proses peringkasan dokumen, rentang bilangan acak yang diperoleh adalah antara 0.1 hingga 0.25. Dari pengamatan hasil perhitungan nilai Kappa antara ringkasan yang dihasilkan metode NMF dengan ringkasan kunci diperoleh persamaan pembobotan dengan nilai Kappa tertinggi, yaitu No Weight. Hal tersebut karena persamaan No Weight menggunakan model pembobotan tf tanpa normalisasi (murni jumlah kemunculan term dalam kalimat). Sehingga kalimat-kalimat yang diekstrak sebagai kalimat penyusun ringkasan cenderung kalimat-kalimat yang mengandung bobot topik yang tinggi. Dari perbandingan nilai Kappa yang dihasilkan oleh ringkasan metode NMF dan ringkasan metode LSA, diketahui bahwa ringkasan dengan metode NMF memilili rata-rata nilai Kappa yang lebih baik daripada metode LSA. Hal tersebut karena proses pemilihan kalimat-kalimat penting yang dilakukan metode NMF lebih tepat. Metode NMF menghasilkan matriks yang nonegatif dan sparse sehingga kecenderungan suatu kalimat terhadap suatu topik lebih mudah dikenali daripada matriks yang berisi bilangan negative dan nonegatif serta bersifat padat seperti yang dihasilkan pada metode LSA.

Untuk penelitian lebih lanjut, diharapkan proses peringkasan dokumen terstruktur dapat diterapkan apda seluruh tipe dokumen, tak hanya terbatas pada dokumen jurnal dari halaman web. REFERENSI Dalianis, H. (2005). GSLT: Natural Language Generation Spring 2005, . Retrieved 25 June, 2011, from http://people.dsv.su.se/~hercules/kurser/nlg/NLG_Sum_9GSLT-OH.pdf Garcia, D. E. (2006). Mi Islita. Retrieved April 18, 2011, from The Classic Vector Space Model: http://www.miislita.com/term-vector/term-vector-3.html Gong, Y., & Liu, X. (2001). Generic Text Summarization Using Relevance Measure and Latent Semantic Analysis. Proceedings of the 24th annual international ACM SIGIR conference on research and development in information retrival (SIGIR’01), (pp. (pp. 19–25)). New Orleans, USA. Hori, C., Hirao, T., & Isozaki, H. (2004). Evaluation Measures Considering Sentence Concatenation for Automatic Summarization by Sentence or Word Extraction. Lee, D. D., & Seung, H. S. (2001). Algorithm for nonnegative matrix factorization. Advance in Neural Information Processing Systems, 13 , 556-562.

VIII. SIMPULAN DAN SARAN PERBAIKAN Proses peringkasan pada suatu dokumen web dapat dilakukan dengan cara melakukan peringaksan pada setiap subbab/section dalam dokumen. Pengambilan isi setiap bagian dokumen dilakukan dengan cara mengenali struktur yang membangun bagian tersebut sehingga proses ekstraksi dapat dibatasi pada bagian-bagian tertentu pada suatu dokumen. Untuk menbangun matriks term-by-sentences, diperlukan persamaan pembobotan yang tepat agar dapat menghasilkan matriks yang tepat mewakili isi dokumen. Dari hasil pengamatan terhadap ringkasan yang dihasilkan oleh masing-masing persamaan, diperoleh peramaan No Weight yang menghasilkan nilai Kappa besar paling besar.

Lee, J.-H., Park, S., Ahn, C.-M., & Kim, D. (2009). Automatic generic document summarization based on non-negative matrix factorization. Information Processing and Management, 45 , 20-34. Lemone, K. (1998). What is a Structured Document? Retrieved May 10, 2011, from Worcester Polytechnic Institute Computer Science: http://web.cs.wpi.edu/~kal/elecdoc/EDstrucdoc.html Radev, D. (2003). Text Summarization. Retrieved 26 June, 2011, from http://www.summarization.com/

Berdasarkan hasil uji coba penentuan rentang bilangan acak terbaik untuk implementasi peringkasan menggunakan metode Faktorisasi Matriks Nonnegatif dapat digunakan rentang bilangan acak antara 0.1 hingga 0.25. Rentang tersebut menghasilkan nilai Frobenius Norm dan waktu ekseskusi yang kecil dalam proses

Vierra, A. J., & Garrett, J. M. (2005). Undertanding Interobserver Agreement: The Kappa Statistic. Family Medicine Vol 37 no 5 , pp. 360-363.

8

MAKALAH SEMINAR TUGAS AKHIR PERIODE JULI 2011

9