HIERARCHICAL CLUSTERING UNTUK APLIKASI AUTOMATED TEXT INTEGRATION

Hierarchical Clustering Untuk Aplikasi Automated Text Integration

Salah satu cara untuk memperoleh berita seimbang adalah dengan membaca beberapa dokumen yg membahas topik yg sama. Namun hal ini menyulitkan pembaca untuk menangkap topik bahasan primer berdasarkan dokumen - dokumen tersebut karena wajib mengingat – ingat isi dokumen yang telah dibaca sebelumnya. Pembaca wajib mengintegrasikan dahulu dokumen – dokumen yg dia baca didalam pikirannya sebelum bisa merangkum maksud serta topik utama dokumen – dokumen tersebut secara holistik. 

Pada penelitian ini peneliti mencoba menciptakan pelaksanaan Automated Text Integration yang bisa menghasilkan integrasi berdasarkan beberapa dokumen elektro yang berbeda menggunakan topik bahasan yang sama secara otomatis. Proses integrasi akan menghasilkan dokumen baru yg mengandung semua bagian dari dokumen – dokumen awal, tetapi mempunyai susunan antar kalimat dan antar paragraf yang tidak sinkron. Perbedaan ini karena ketika proses integrasi topik – topik bahasan yg serupa (similar) dari seluruh dokumen dikumpulkan sebagai satu paragraf dan disusun ulang kalimat per kalimat sinkron dengan besarnya kecenderungan (similiarity) antar kalimatnya. Dengan membaca hasil integrasi diperlukan pembaca bisa terbantu pada menyerap informasi krusial yang terdapat pada kumpulan dokumen yang berbeda serta nir perlu lagi membaca sekumpulan dokumen satu per satu.

Hierarchical Clustering

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

Kategori prosedur pemecahan clustering yg banyak dikenal adalah Hierarchical Clustering. Hierarchical Clustering adalah galat satu prosedur pemecahan clustering yang dapat digunakan buat meng-cluster dokumen (document clustering). Dari teknik hierarchical clustering, dapat didapatkan suatu kumpulan partisi yg berurutan, dimana pada perpaduan tersebut masih ada:

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

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

Hasil keseluruhan dari prosedur pemecahan hierarchical clustering secara grafik bisa digambarkan menjadi tree, yg diklaim menggunakan dendogram. Tree ini secara grafik menggambarkan proses penggabungan berdasarkan cluster – cluster yang ada, sehingga membentuk cluster dengan level yg lebih tinggi. Gambar 1 adalah contoh dendogram.

Gambar  Dendogram 

Agglomerative Hierarchical Clustering

Metode ini memakai strategi disain Bottom-Up yg dimulai dengan meletakkan setiap obyek menjadi sebuah cluster tersendiri (atomic cluster) serta selanjutnya menggabungkan atomic cluster – atomic cluster tersebut sebagai cluster yang lebih besar serta lebih besar lagi sampai akhirnya semua obyek menyatu dalam sebuah cluster atau proses dapat juga berhenti bila sudah mencapai batasan syarat tertentu. Metode Agglomerative Hierarchical Clustering yang digunakan dalam penelitian ini adalah metode AGglomerative NESting (AGNES). Cara kerja AGNES bisa ditinjau pada gambar.

Adapun ukuran jeda yg dipakai untuk menggabungkan dua buah obyek cluster adalah Minimum Distance yg bisa dilihat dalam persamaan.

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

Algoritma Cosine Distance

Metode cosine distance merupakan metode yang dipakai untuk menghitung similarity (taraf kecenderungan) antar dua butir obyek. Pada penelitian ini obyek Berikut adalah persamaan menurut metode Cosine Distance :

Pada penelitian ini obyek v1 serta v2 adalah dua buah dokumen yang berbeda.

Proses Parsing, Stemming serta Stopword Removal

Dalam bidang rapikan bahasa serta linguistik, parsing merupakan sebuah proses buat menjadikan sebuah kalimat menjadi lebih bermakna atau berarti menggunakan cara memecah kalimat tersebut sebagai istilah-kata atau frase – frase.

Stemming merupakan proses pemetaan dan penguraian berbagai bentuk (variants) dari suatu kata sebagai bentuk kata dasarnya. Proses stemming dipakai pada pada proses Information Retrieval (pencarian fakta) buat menaikkan kualitas informasi yg didapatkan .

Stopwords removal merupakan sebuah proses untuk menghilangkan kata yang 'tidak relevan' dalam hasil parsing sebuah dokumen teks menggunakan cara membandingkannya dengan Stoplist (Stopword list) yang terdapat. Contoh berdasarkan Stopword misalnya, kata sambung, artikel serta kata depan. 

Bobot Relasi antar kalimat

Bobot rekanan antara 2 kalimat merupakan sama dengan jeda antara ke 2 kalimat tadi. Konsekuensinya adalah apabila bobot relasi antara dua kalimat eksklusif lebih kecil berdasarkan yg lain, maka jeda keduanya juga lebih dekat [5, 8]. Secara formal, misal masih ada n kalimat P=S1, S2, …, Sn, maka bobot relasi antara dua kalimat Si serta Sj bisa dipandang pada persamaan tiga. 

dimana i, j merupakan letak kalimat ke i dan j;

adalah jumlah istilah yang sama atara Si dan Sj setelah stopword yg terdapat dihilangkan ; serta W(Sj) merupakan 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 serta j merupakan angka urut kalimat dalam adonan dokumen yang disusun secara berurutan menurut rekanan antar dokumen, yg diukur menggunakan Cosine Distance (persamaan dua).

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 serta Stopword Removal harus dikerjakan terlebih dahulu sebelum proses perhitungan bobot kalimat ini dilakukan.

Perhitungan bobot kalimat ini berbasis dalam serta sudah dimodifikasi pada penelitian sebelumnya. Ada empat macam bobot kalimat yg digunakan pada penelitan sebelumnya yaitu:

W1 ® Banyaknya kata yang sama antara kalimat yang dihitung menggunakan daftar istilah kunci (keyword) dalam dokumen tempat kalimat tadi berada.

W2 ® Nilai yg dipengaruhi dari kemunculan istilah – istilah didalam kalimat terhadap pemakaian istilah – istilah tadi pada dokumen tempat kalimat berada.

W3 ® Nilai ini ditentukan sang posisi dimana kalimat tersebut berada terhadap paragrafnya. Berdasarkan kaidah Deduktif – Induktif bahasa Indonesia terdapat dua macam nilai yg dipakai disini, yaitu: Bila kalimat tadi berada pada awal / akhir paragraf memiliki bobot dua, sementara jika nir mempunyai bobot 1.

W4 ® Menghitung banyaknya relasi sebuah kalimat menggunakan kalimat – kalimat lain pada dokumen yg sama.

Bobot Kalimat total bisa dilihat dalam persamaan 4.

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

Untuk penelitian kali ini perhitungan bobot kalimat ini dimodifikasi balik supaya sesuai kebutuhan dalam penelitian ini. Pemikiran dari modifikasi ini adalah:

- Pada penelitian terdahulu proses hanya diterakan dalam satu dokumen saja, sang sebab itu bobot berdasarkan kalimat cukup dihitung terhadap sebuah dokumen saja.

- Pada penelitian ini terdapat beberapa dokumen yang digabungkan, buat itu perlu diperhitungkan bahwa bobot sebuah kalimat nir hanya diukur terhadap kalimat lain pada dokumen yang sama melainkan juga terhadap kalimat lain pada dokumen yang tidak sinkron yg akan diintegrasikan.

Dari pemikiran diatas, peneliti akhirnya tetapkan bahwa bobot kalimat pada persamaan 4 perlu dimodifikasi dengan sebuah bobot kelima. Bobot kelima ini (W5) merepresentasikan seberapa krusial sebuah kalimat dibandingkan menggunakan kalimat – kalimat lain yg masih ada pada seluruh dokumen yg akan diintegrasikan. Persamaan output modifikasi dapat dipandang pada persamaan 5.

dimana W5 adalah Banyaknya istilah kunci (keyword) yg sama antara kalimat yg dihitung menggunakan daftar kata kunci dalam seluruh dokumen yang akan diintegrasikan. Asumsinya adalah semakin banyak kata pada kalimat tersebut sama menggunakan daftar kata kunci, semakin penting eksistensi kalimat tersebut dalam dokumen hasil integrasi.

1. Desain Aplikasi Automated Text Integration

Desain aplikasi Automated Text Integration bisa dipandang pada diagram Use Case pada gambar 2

Gambar Diagram Use Case Aplikasi

Inti menurut aplikasi ini adalah Do Integration, dimana pada use case ini proses integrasi beberapa dokumen yg dipilih dilakukan. Diagram activity berdasarkan use case ini dapat dilihat pada Gambar tiga.

Gambar  Do Integration Activity Diagram

Penjelasan menurut diagram activity pada gambar 3 merupakan menjadi berikut:

• Sebelum proses ini, user harus memilih terlebih dahulu dokumen – dokumen mana yg akan diintegrasikan dalam menu ’Open Dokumen’. Proses ini secara otomatis akan menulis informasi nama serta path dokumen – dokumen tersebut pada listbox dokumen. Format dokumen yg dapat dipilih adalah *.doc dan *.txt.
• Setelah user menentukan menu ‘Integration’, pelaksanaan akan meminta user mengisikan nilai batas terendah similarity antar dokumen yg diijinkan oleh user buat dokumen – dokumen yang akan diintegrasikan.
• Selanjutnya apabila listbox dokumen terisi, pelaksanaan akan merubah semua dokumen yg ada kedalam bentuk teks, menggantinya sebagai sekumpulan kalimat dan istilah – kata yg berurutan (divide to word / parsing), melakukan proses stemming, stopword removal, menandai kata – istilah mana saja yang adalah keyword, dan menghitung similarity antar dokumen dengan persamaan dua.
• Selanjutnya pelaksanaan akan memperlihatkan list similarity antar dokumen serta memberi tanda jika similarity tersebut dibawah nilai yang sudah dipengaruhi. Bila user menentukan melanjutkan proses menggunakan memilih ‘continue’, aplikasi akan menyusun dokumen – dokumen tersebut secara berurutan sinkron menggunakan level similarity-nya.
• · Langkah berikutnya aplikasi akan menghitung bobot kalimat (Weight Of Sentence) serta bobot relasi antar kalimat (Weight Of Relation). Bobot rekanan antar kalimat ini yg akan dipakai buat mengintegrasikan dokumen memakai metode AGglomerative NESting (AGNES).
• Pada proses integrasi, awalnya semua kalimat dalam seluruh dokumen dipercaya menjadi atomic cluster – atomic cluster. Selanjutnya secara bertahap cluster – cluster tersebut akan disatukan memakai aturan Minimum Distance dalam persamaan 1. Setelah seluruh kalimat telah tergabung sebagai sebuah cluster, dilakukan proses buat memecah cluster tersebut sebagai paragraf – paragraf. Caranya adalah, kalimat – kalimat yang bergabung terlebih dahulu sebagai cluster – cluster besar dipercaya menjadi sebuah paragraf tersendiri. Asumsinya, bila secara natural kalimat – kalimat tersebut bergabung, bisa dianggap kalimat – kalimat tadi mempunyai similarity yg relatif tinggi dan membahas topik bahasan yang sama. Agar lebih jelas, proses integrasi ini bisa dilihat dalam gambar 4. Sementara buat memproses kalimat – kalimat tersisa yang tidak mau bergabung kedalam cluster – cluster akbar, digunakan aturan sebagai berikut:

o Jika hanya 1 kalimat (seperti kalimat no. 0-1-1 pada gambar 4) akan digabungkan pada paragraf terakhir.

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

Gambar Proses Integrasi menggunakan AGNES

· Langkah terakhir merupakan menyuguhkan output integrasi kepada user dalam bentuk tampilan teks. User lalu bisa menentukan untuk menyimpan output integrasi kedalam arsip *.doc atau *.txt.

Pengujian Aplikasi

Pengujian Hasil Integrasi

Untuk membandingkan hasil integrasi dengan dokumen aslinya. Dua butir dokumen pendek aslinya pada gambar 5 dan 6 digabungkan dan dalam gambar 7 dapat ditinjau output integrasinya. Pada gambar 4 dapat ditinjau bagaimana proses penggabungannya. Gambar 5 sebagai dokumen ke - 0 serta gambar 6 merupakan dokumen ke – 1.

Gambar Dokumen dari ke - 0

Gambar Dokumen asal ke - 1

Gambar  Hasil Integrasi

Pengujian Dalam Bentuk Survey

Pengujian ini dilakukan menggunakan cara meminta donasi 100 orang responden umum buat membaca dokumen – dokumen dari dan dokumen hasil integrasi, kemudian menjawab 3 pertanyaan berikut:

1. Menurut anda, apakah istilah-istilah dalam dokumen output integrasi tersebut telah terorganisir menggunakan baik (tiap paragraf menaruh arti yg kentara dan bisa dipahami) ? A. Ya B. Tidak

2. Menurut anda, apakah dokumen output integrasi tersebut sudah memberikan citra secara generik berdasarkan keseluruhan dokumen yg terdapat sebelumnya ? A. Ya B. Tidak

3. Menurut anda, apakah dokumen output integrasi bisa memberikan warta - warta penting yg terdapat dalam dokumen sebelumnya secara jelas? A. Ya B. Tidak

Kedua jenis dokumen yg dipakai sebagai bahan kuesioner bertipe eksposisi, yaitu dokumen yg berusaha menjelaskan suatu mekanisme atau proses, menaruh definisi, memperlihatkan, menjelaskan, menafsirkan gagasan, menampakan bagan atau tabel, atau mengulas sesuatu kepada pembaca. 

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

Pengujian Kecepatan Proses 

Pengujian kecepatan proses pelaksanaan Automated Text Integration ini dilakukan pada spesfikasi hardware dan aplikasi ini dia, Processor: Pentium IV 1600 MHz; Memory: 512 Mbyte; HardDisk: 40 Gigabyte serta Operating System: Windows XP Professional. Hasil pengujian bisa ditinjau pada tabel.

Tabel Hasil Pengujian Kecepatan Proses

SUMBER-SUMBER ARTIKEL DI ATAS :

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

[2] Arifin, E. Zaenal, serta 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, //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 serta Kebudayaan Republik Indonesia, Pedoman umum ejaan bahasa Indonesia yg 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, //glaros.dtc.umn.edu/gkhome/fetch/papers/doccluster.pdf (January, 2007)