Hierarchical Clustering Untuk Aplikasi Automated Text Integration

Algoritma Cosine Distance

Metode cosine distance merupakan tata cara yang digunakan untuk mengkalkulasikan similarity (tingkat kesamaan) antar dua buah obyek. Pada observasi ini obyek Berikut adalah persamaan dari tata cara Cosine Distance :

Pada penelitian ini obyek v1 dan v2 yaitu dua buah dokumen yang berbeda.

Proses Parsing, Stemming dan Stopword Removal

Dalam bidang tata bahasa dan linguistik, parsing adalah sebuah proses untuk menjadikan sebuah kalimat menjadi lebih berarti atau memiliki arti dengan cara memecah kalimat tersebut menjadi kata-kata atau frase – frase.

Stemming yaitu proses pemetaan dan penguraian aneka macam bentuk (variants) dari sebuah kata menjadi bentuk kata dasarnya. Proses stemming dipakai di dalam proses Information Retrieval (penelusuran isu) untuk meningkatkan mutu berita yang didapatkan .

Stopwords removal adalah sebuah proses untuk menetralisir kata yang ‘tidak relevan’ pada hasil parsing sebuah dokumen teks dengan cara membandingkannya dengan Stoplist (Stopword list) yang ada. Contoh dari Stopword contohnya, kata sambung, postingan dan preposisi. 

Bobot Relasi antar kalimat

Bobot relasi antara dua kalimat yakni sama dengan jarak antara kedua kalimat tersebut. Konsekuensinya yakni jika bobot korelasi antara dua kalimat tertentu lebih kecil dari lainnya, maka jarak keduanya juga lebih bersahabat [5, 8]. Secara formal, misal terdapat n kalimat P=S1, S2, …, Sn, maka bobot kekerabatan antara dua kalimat Si dan Sj dapat dilihat pada persamaan 3. 

dimana i, j ialah letak kalimat ke i dan j; yaitu jumlah kata yang sama atara Si dan Sj sesudah stopword yang ada dihilangkan ; dan W(Sj) adalah bobot kalimat ke j.

Pada penelitian sebelumnya letak kalimat ke i dan j diukur cuma pada satu paragraf saja. Pada observasi ini definisi tersebut diubah, yaitu: i dan j yakni nomor urut kalimat pada adonan dokumen yang disusun secara berurutan menurut kekerabatan antar dokumen, yang diukur menggunakan Cosine Distance (persamaan 2).

Bobot Kalimat

Bobot Kalimat yakni sebuah nilai senuah kalimat yang mengindikasikan sebeberapa penting arti kalimat tersebut pad suatu paragraf. Semakin tinggi nilai kalimatnya makin penting pula artinya dalam paragraf. Proses Parsing, Stemming dan Stopword Removal harus dijalankan apalagi dahulu sebelum proses perkiraan bobot kalimat ini dilakukan.

Perhitungan bobot kalimat ini berbasis pada dan sudah dimodifikasi pada observasi sebelumnya. Ada empat macam bobot kalimat yang digunakan pada penelitan sebelumnya yaitu:

W1 ® Banyaknya kata yang sama antara kalimat yang dijumlah dengan daftar kata kunci (keyword) pada dokumen tempat kalimat tersebut berada.

W2 ® Nilai yang diputuskan dari kemunculan kata – kata didalam kalimat terhadap pemakaian kata – kata tersebut pada dokumen daerah kalimat berada.

W3 ® Nilai ini diputuskan oleh posisi dimana kalimat tersebut berada kepada paragrafnya. Berdasarkan kaidah Deduktif – Induktif bahasa Indonesia ada 2 macam nilai yang digunakan disini, yakni: Bila kalimat tersebut berada pada awal / tamat paragraf memiliki bobot 2, sementara kalau tidak mempunyai bobot 1.

W4 ® Menghitung banyaknya relasi sebuah kalimat dengan kalimat – kalimat lain pada dokumen yang sama.

Bobot Kalimat total dapat dilihat pada persamaan 4.

dimana j adalah kalimat ke-j dari total n kalimat.

Untuk penelitian kali ini perkiraan bobot kalimat ini dimodifikasi kembali biar sesuai keperluan pada observasi ini. Pemikiran dari modifikasi ini yaitu:

– Pada observasi terdahulu proses cuma diterakan pada satu dokumen saja, oleh alasannya adalah itu bobot dari kalimat cukup dijumlah kepada sebuah dokumen saja.

– Pada penelitian ini ada beberapa dokumen yang digabungkan, untuk itu perlu diperhitungkan bahwa bobot suatu kalimat tidak cuma diukur terhadap kalimat lain pada dokumen yang serupa melainkan juga terhadap kalimat lain di dokumen yang berbeda yang akan diintegrasikan.

Dari aliran diatas, peneliti akhirnya menetapkan bahwa bobot kalimat pada persamaan 4 perlu dimodifikasi dengan sebuah bobot kelima. Bobot kelima ini (W5) merepresentasikan seberapa penting sebuah kalimat ketimbang kalimat – kalimat lain yang terdapat pada semua dokumen yang akan diintegrasikan. Persamaan hasil adaptasi dapat dilihat pada persamaan 5.

dimana W5 ialah Banyaknya kata kunci (keyword) yang sama antara kalimat yang dihitung dengan daftar keyword pada semua dokumen yang akan diintegrasikan. Asumsinya yakni semakin banyak kata pada kalimat tersebut sama dengan daftar kata kunci, makin penting eksistensi kalimat tersebut pada dokumen hasil integrasi.

1. Desain Aplikasi Automated Text Integration

Desain aplikasi Automated Text Integration mampu dilihat pada diagram Use Case pada gambar 2

Gambar Diagram Use Case Aplikasi

Inti dari aplikasi ini adalah Do Integration, dimana pada use case ini proses integrasi beberapa dokumen yang diseleksi dikerjakan. Diagram activity dari use case ini dapat dilihat pada Gambar 3.

Gambar  Do Integration Activity Diagram

Penjelasan dari diagram activity pada gambar 3 adalah sebagai berikut:

• Sebelum proses ini, user harus menentukan terlebih dulu dokumen – dokumen mana yang akan diintegrasikan pada hidangan ’Open Dokumen’. Proses ini secara otomatis akan menulis informasi nama dan path dokumen – dokumen tersebut pada listbox dokumen. Format dokumen yang dapat diseleksi yakni *.doc dan *.txt.
• Setelah user memilih sajian ‘Integration’, aplikasi akan meminta user mengisikan nilai batas terendah similarity antar dokumen yang diijinkan oleh user untuk dokumen – dokumen yang hendak diintegrasikan.
• Selanjutnya jika listbox dokumen terisi, aplikasi akan mengganti semua dokumen yang ada kedalam bentuk teks, merubahnya menjadi sekumpulan kalimat dan kata – kata yang berurutan (divide to word / parsing), melakukan proses stemming, stopword removal, menandai kata – kata mana saja yang merupakan keyword, dan menghitung similarity antar dokumen dengan persamaan 2.
• Selanjutnya aplikasi akan memperlihatkan list similarity antar dokumen dan memberi tanda jikalau similarity tersebut dibawah nilai yang telah diputuskan. Bila user menentukan melanjutkan proses dengan menentukan ‘continue’, aplikasi akan menyusun dokumen – dokumen tersebut secara berurutan sesuai dengan level similarity-nya.
• · Langkah selanjutnya aplikasi akan menghitung bobot kalimat (Weight Of Sentence) dan bobot korelasi antar kalimat (Weight Of Relation). Bobot hubungan antar kalimat ini yang mau digunakan untuk mengintegrasikan dokumen menggunakan tata cara AGglomerative NESting (AGNES).
• Pada proses integrasi, mulanya semua kalimat pada semua dokumen dianggap sebagai atomic cluster – atomic cluster. Selanjutnya secara bertahap cluster – cluster tersebut akan disatukan menggunakan hukum Minimum Distance pada persamaan 1. Setelah semua kalimat sudah tergabung menjadi suatu cluster, dijalankan proses untuk memecah cluster tersebut menjadi paragraf – paragraf. Caranya yaitu, kalimat – kalimat yang bergabung apalagi dahulu menjadi cluster – cluster besar dianggap sebagai suatu paragraf tersendiri. Asumsinya, jikalau secara natural kalimat – kalimat tersebut bergabung, mampu dianggap kalimat – kalimat tersebut memiliki similarity yang cukup tinggi dan membahas topik bahasan yang sama. Agar lebih terang, proses integrasi ini dapat dilihat pada gambar 4. Sementara untuk memproses kalimat – kalimat tersisa yang tidak inginbergabung kedalam cluster – cluster besar, digunakan aturan selaku berikut:

o Bila cuma 1 kalimat (mirip kalimat no. 0-1-1 pada gambar 4) akan digabungkan pada paragraf terakhir.

o Bila lebih dari satu kalimat, kalimat – kalimat yang tersisa tersebut akan dipaksakan bergabung menjadi satu paragraf tersendiri.

Gambar Proses Integrasi menggunakan AGNES

· Langkah terakhir ialah menghidangkan hasil integrasi terhadap user dalam bentuk performa teks. User kemudian dapat menentukan untuk menyimpan hasil integrasi kedalam file *.doc atau *.txt.

Pengujian Aplikasi

Pengujian Hasil Integrasi

Untuk membandingkan hasil integrasi dengan dokumen aslinya. Dua buah dokumen pendek aslinya pada gambar 5 dan 6 digabungkan dan pada gambar 7 mampu dilihat hasil integrasinya. Pada gambar 4 mampu dilihat bagaimana proses penggabungannya. Gambar 5 menjadi dokumen ke – 0 dan gambar 6 yaitu dokumen ke – 1.

Gambar Dokumen asal ke – 0

Gambar Dokumen asal ke – 1

Gambar  Hasil Integrasi

Pengujian Dalam Bentuk Survey

Pengujian ini dilakukan dengan cara meminta bantuan 100 orang responden biasa untuk membaca dokumen – dokumen asal dan dokumen hasil integrasi, kemudian menjawab 3 pertanyaan berikut:

1. Menurut anda, apakah kata-kata pada dokumen hasil integrasi tersebut telah terstruktur dengan baik (tiap paragraf memperlihatkan arti yang terperinci dan mampu diketahui) ? A. Ya B. Tidak

2. Menurut anda, apakah dokumen hasil integrasi tersebut telah memberikan gambaran secara lazim dari keseluruhan dokumen yang ada sebelumnya ? A. Ya B. Tidak

3. Menurut anda, apakah dokumen hasil integrasi dapat memberikan informasi – informasi penting yang terdapat pada dokumen sebelumnya secara terperinci? A. Ya B. Tidak

Kedua jenis dokumen yang digunakan menjadi materi survey bertipe eksposisi, yakni dokumen yang berusaha menjelaskan sebuah mekanisme atau proses, menunjukkan definisi, pertanda, menjelaskan, menafsirkan pemikiran , menerangkan sketsa atau tabel, atau mengulas sesuatu kepada pembaca. 

Sementara untuk dokumen berupa naratif seperti cerita rakyat, tidak disertakan dalam survey, alasannya peneliti sendiri sudah melihat adanya kerancuan pada jalan cerita pada dokumen hasil integrasinya. Hal ini senantiasa terjadi pada beberapa uji coba pada beberapa topik dokumen naratif, seperti “Timun Emas”, “Sangkuriang”, “Jack dan Kacang Polong” dan lain – yang lain. Oleh karena itu dapat disimpulkan bahwa proses integrasi ini tidak cocok untuk dokumen yang berjenis naratif.

Pengujian Kecepatan Proses 

Pengujian kecepatan proses aplikasi Automated Text Integration ini dikerjakan pada spesfikasi hardware dan software berikut ini, Processor: Pentium IV 1600 MHz; Memory: 512 Mbyte; HardDisk: 40 Gigabyte dan Operating System: Windows XP Professional. Hasil pengujian dapat dilihat pada tabel.

Tabel Hasil Pengujian Kecepatan Proses

[1] Akhadiah, Sabarti, Maidar M. K. Arsjad dan Sakura Ridwan, Buku Materi Pokok : Bahasa Indonesia, Jakarta: Penerbit Karunika Jakarta UT. 1986.

[2] Arifin, E. Zaenal, dan Amran Tasai, Cermat Berbahasa Indonesia Untuk Perguruan Tinggi, Jakarta: Penerbit Akademika Pressindo, 2000.

[3] Garcia, E., “An information retrieval tutorial on cosine similarity measures, dot products and term weight calculations”, 2006, http://www.miislita.com/information-retrieval-bimbingan/cosine-similarity-tutorial.html (January, 2007)

[4] Gregorius S. Budhi, Ibnu Gunawan dan Ferry Yuwono, “Algortima Porter Stemmer For Bahasa Indonesia Untuk Pre-Processing Text Mining Berbasis Metode Market Basket Analysis”, PAKAR Jurnal Teknologi Informasi Dan Bisnis vol. 7 no. 3 November, 2006.

[5] Gregorius S. Budhi; Rolly Intan, Silvia R. dan Stevanus R. R., “Indonesia Automated Text Summarization”. Proceeding ICSIIT 2007. , 26 – 27 July 2007.

[6] Han, Jiawei and Micheline Kamber, Data Mining: Concepts and Techniques, Morgan Kaufmann, 2001.

[7] Pusat Pembinaan & Pengembangan Bahasa Departemen Pendidikan dan Kebudayaan Republik Indonesia, Pedoman umum ejaan bahasa Indonesia yang disempurnakan. Jakarta: Balai Pustaka, 1999.

[8] Sjobergh, Jonas, and Kenji Araki, Extraction based summarization using a shortest path algorithm. Sweden: KTH Nada, 2005.

[9] Steinbach, M., G. Karypis and Vipin Kumar, A comparisont of document clustering techniques, Minnesota: University of Minnesota, Department of Computer Science and Engineering, 2000, http://glaros.dtc.umn.edu/gkhome/fetch/papers/doccluster.pdf (January, 2007)