Hierarchical Clustering Untuk Aplikasi Automated Text Integration

Hierarchical Clustering Untuk Aplikasi Automated Text Integration

Salah satu cara untuk memperoleh informasi seimbang adalah dengan membaca beberapa dokumen yang membahas topik yang sama. Namun hal ini menyulitkan pembaca untuk menangkap topik bahasan utama dari dokumen - dokumen tersebut karena harus mengingat – ingat isi dokumen yang telah dibaca sebelumnya. Pembaca harus mengintegrasikan dahulu dokumen – dokumen yang dia baca didalam pikirannya sebelum dapat merangkum maksud dan topik utama dokumen – dokumen tersebut secara keseluruhan. 

Pada penelitian ini peneliti mencoba membuat aplikasi Automated Text Integration yang dapat menghasilkan integrasi dari beberapa dokumen elektronik yang berbeda dengan topik bahasan yang sama secara otomatis. Proses integrasi akan menghasilkan dokumen baru yang mengandung semua bagian dari dokumen – dokumen awal, namun memiliki susunan antar kalimat serta antar paragraf yang berbeda. Perbedaan ini karena saat proses integrasi topik – topik bahasan yang serupa (similar) dari semua dokumen dikumpulkan menjadi satu paragraf dan disusun ulang kalimat per kalimat sesuai dengan besarnya kesamaan (similiarity) antar kalimatnya. Dengan membaca hasil integrasi diharapkan pembaca dapat terbantu dalam menyerap informasi penting yang ada dalam kumpulan dokumen yang berbeda dan tidak perlu lagi membaca sekumpulan dokumen satu per satu.

Hierarchical Clustering

Pada algoritma clustering, data akan dikelompokkan menjadi cluster-cluster berdasarkan kemiripan satu data dengan yang lain. Prinsip dari clustering adalah memaksimalkan kesamaan antar anggota satu cluster dan meminimumkan kesamaan antar anggota cluster yang berbeda.

Kategori algoritma clustering yang banyak dikenal adalah Hierarchical Clustering. Hierarchical Clustering adalah salah satu algoritma clustering yang dapat digunakan untuk meng-cluster dokumen (document clustering). Dari teknik hierarchical clustering, dapat dihasilkan suatu kumpulan partisi yang berurutan, dimana dalam kumpulan tersebut terdapat:

a. Cluster – cluster yang mempunyai poin – poin individu. Cluster – cluster ini berada di level yang paling bawah.

b. Sebuah cluster yang didalamnya terdapat poin – poin yang dipunyai semua cluster didalamnya. Single cluster ini berada di level yang paling atas.

Hasil keseluruhan dari algoritma hierarchical clustering secara grafik dapat digambarkan sebagai tree, yang disebut dengan dendogram. Tree ini secara grafik menggambarkan proses penggabungan dari cluster – cluster yang ada, sehingga menghasilkan cluster dengan level yang lebih tinggi. Gambar 1 adalah contoh dendogram.

Gambar  Dendogram 

Agglomerative Hierarchical Clustering

Metode ini menggunakan strategi disain Bottom-Up yang dimulai dengan meletakkan setiap obyek sebagai sebuah cluster tersendiri (atomic cluster) dan selanjutnya menggabungkan atomic cluster – atomic cluster tersebut menjadi cluster yang lebih besar dan lebih besar lagi sampai akhirnya semua obyek menyatu dalam sebuah cluster atau proses dapat pula berhenti jika telah mencapai batasan kondisi tertentu. Metode Agglomerative Hierarchical Clustering yang digunakan pada penelitian ini adalah metode AGglomerative NESting (AGNES). Cara kerja AGNES dapat dilihat pada gambar.

Adapun ukuran jarak yang digunakan untuk menggabungkan dua buah obyek cluster adalah Minimum Distance yang dapat dilihat pada persamaan.

Dimana |p – p’| jarak dua buah obyek p dan p’.

Algoritma Cosine Distance

Metode cosine distance merupakan metode yang digunakan untuk menghitung similarity (tingkat kesamaan) antar dua buah obyek. Pada penelitian ini obyek Berikut adalah persamaan dari metode Cosine Distance :

Pada penelitian ini obyek v1 dan v2 adalah 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 bermakna atau berarti dengan cara memecah kalimat tersebut menjadi kata-kata atau frase – frase.

Stemming adalah proses pemetaan dan penguraian berbagai bentuk (variants) dari suatu kata menjadi bentuk kata dasarnya. Proses stemming digunakan di dalam proses Information Retrieval (pencarian informasi) untuk meningkatkan kualitas informasi yang didapatkan .

Stopwords removal adalah sebuah proses untuk menghilangkan kata yang 'tidak relevan' pada hasil parsing sebuah dokumen teks dengan cara membandingkannya dengan Stoplist (Stopword list) yang ada. Contoh dari Stopword misalnya, kata sambung, artikel dan preposisi. 

Bobot Relasi antar kalimat

Bobot relasi antara dua kalimat adalah sama dengan jarak antara kedua kalimat tersebut. Konsekuensinya adalah bila bobot relasi antara dua kalimat tertentu lebih kecil dari yang lain, maka jarak keduanya juga lebih dekat [5, 8]. Secara formal, misal terdapat n kalimat P={S1, S2, …, Sn}, maka bobot relasi antara dua kalimat Si dan Sj dapat dilihat pada persamaan 3. 

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

Pada penelitian sebelumnya letak kalimat ke i dan j diukur hanya pada satu paragraf saja. Pada penelitian ini definisi tersebut diubah, yaitu: i dan j adalah nomor urut kalimat pada gabungan dokumen yang disusun secara berurutan berdasarkan relasi antar dokumen, yang diukur menggunakan Cosine Distance (persamaan 2).

Bobot Kalimat

Bobot Kalimat adalah sebuah nilai senuah kalimat yang mengindikasikan sebeberapa penting arti kalimat tersebut pad sebuah paragraf. Semakin tinggi nilai kalimatnya semakin penting pula artinya dalam paragraf. Proses Parsing, Stemming dan Stopword Removal harus dikerjakan terlebih dahulu sebelum proses perhitungan bobot kalimat ini dilakukan.

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

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

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

W3 ® Nilai ini ditentukan oleh posisi dimana kalimat tersebut berada terhadap paragrafnya. Berdasarkan kaidah Deduktif – Induktif bahasa Indonesia ada 2 macam nilai yang dipakai disini, yaitu: Bila kalimat tersebut berada pada awal / akhir paragraf memiliki bobot 2, sementara bila tidak memiliki 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 perhitungan bobot kalimat ini dimodifikasi kembali agar sesuai kebutuhan pada penelitian ini. Pemikiran dari modifikasi ini adalah:

- Pada penelitian terdahulu proses hanya diterakan pada satu dokumen saja, oleh sebab itu bobot dari kalimat cukup dihitung terhadap sebuah dokumen saja.

- Pada penelitian ini ada beberapa dokumen yang digabungkan, untuk itu perlu diperhitungkan bahwa bobot sebuah kalimat tidak hanya diukur terhadap kalimat lain pada dokumen yang sama melainkan juga terhadap kalimat lain di dokumen yang berbeda yang akan diintegrasikan.

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

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

1. Desain Aplikasi Automated Text Integration

Desain aplikasi Automated Text Integration dapat 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 dipilih dilakukan. 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 dahulu dokumen – dokumen mana yang akan diintegrasikan pada menu ’Open Dokumen’. Proses ini secara otomatis akan menulis informasi nama dan path dokumen – dokumen tersebut pada listbox dokumen. Format dokumen yang dapat dipilih adalah *.doc dan *.txt.
• Setelah user memilih menu ‘Integration’, aplikasi akan meminta user mengisikan nilai batas terendah similarity antar dokumen yang diijinkan oleh user untuk dokumen – dokumen yang akan diintegrasikan.
• Selanjutnya bila listbox dokumen terisi, aplikasi akan merubah 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 menunjukkan list similarity antar dokumen dan memberi tanda bila similarity tersebut dibawah nilai yang telah ditentukan. Bila user memilih melanjutkan proses dengan memilih ‘continue’, aplikasi akan menyusun dokumen – dokumen tersebut secara berurutan sesuai dengan level similarity-nya.
• · Langkah berikutnya aplikasi akan menghitung bobot kalimat (Weight Of Sentence) dan bobot relasi antar kalimat (Weight Of Relation). Bobot relasi antar kalimat ini yang akan dipakai untuk mengintegrasikan dokumen menggunakan metode AGglomerative NESting (AGNES).
• Pada proses integrasi, awalnya semua kalimat pada semua dokumen dianggap sebagai atomic cluster – atomic cluster. Selanjutnya secara bertahap cluster – cluster tersebut akan disatukan menggunakan aturan Minimum Distance pada persamaan 1. Setelah semua kalimat telah tergabung menjadi sebuah cluster, dilakukan proses untuk memecah cluster tersebut menjadi paragraf – paragraf. Caranya adalah, kalimat – kalimat yang bergabung terlebih dahulu menjadi cluster – cluster besar dianggap sebagai sebuah paragraf tersendiri. Asumsinya, bila secara natural kalimat – kalimat tersebut bergabung, dapat dianggap kalimat – kalimat tersebut memiliki similarity yang cukup tinggi dan membahas topik bahasan yang sama. Agar lebih jelas, proses integrasi ini dapat dilihat pada gambar 4. Sementara untuk memproses kalimat – kalimat tersisa yang tidak mau bergabung kedalam cluster – cluster besar, dipakai aturan sebagai berikut:

o Bila hanya 1 kalimat (seperti 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 adalah menyuguhkan hasil integrasi kepada user dalam bentuk tampilan teks. User kemudian dapat memilih 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 dapat dilihat hasil integrasinya. Pada gambar 4 dapat dilihat bagaimana proses penggabungannya. Gambar 5 menjadi dokumen ke - 0 dan gambar 6 adalah 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 umum 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 terorganisir dengan baik (tiap paragraf memberikan arti yang jelas dan dapat dipahami) ? A. Ya B. Tidak

2. Menurut anda, apakah dokumen hasil integrasi tersebut telah memberikan gambaran secara umum 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 jelas? A. Ya B. Tidak

Kedua jenis dokumen yang dipakai menjadi bahan survey bertipe eksposisi, yaitu dokumen yang berusaha menjelaskan suatu prosedur atau proses, memberikan definisi, menerangkan, menjelaskan, menafsirkan gagasan, menerangkan bagan atau tabel, atau mengulas sesuatu kepada pembaca. 

Sementara untuk dokumen berbentuk naratif seperti cerita rakyat, tidak disertakan dalam survey, karena peneliti sendiri telah melihat adanya kerancuan pada jalan cerita pada dokumen hasil integrasinya. Hal ini selalu terjadi pada beberapa uji coba pada beberapa topik dokumen naratif, seperti “Timun Emas”, “Sangkuriang”, “Jack dan Kacang Polong” dan lain – lainnya. 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 dilakukan 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

SUMBER-SUMBER ARTIKEL DI ATAS :

[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-tutorial/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)