HIERARCHICAL CLUSTERING UNTUK APLIKASI AUTOMATED TEXT INTEGRATION

Hierarchical Clustering Untuk Aplikasi Automated Text Integration

Salah satu cara buat memperoleh kabar seimbang merupakan menggunakan membaca beberapa dokumen yg membahas topik yg sama. Tetapi hal ini menyulitkan pembaca untuk menangkap topik bahasan primer berdasarkan dokumen - dokumen tadi lantaran 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 tadi secara holistik. 

Pada penelitian ini peneliti mencoba menciptakan aplikasi Automated Text Integration yg bisa membentuk integrasi berdasarkan beberapa dokumen elektro yg tidak selaras dengan topik bahasan yg sama secara otomatis. Proses integrasi akan membuat dokumen baru yg mengandung semua bagian berdasarkan dokumen – dokumen awal, namun mempunyai susunan antar kalimat dan antar paragraf yang tidak sinkron. Perbedaan ini karena saat proses integrasi topik – topik bahasan yg serupa (similar) menurut seluruh dokumen dikumpulkan sebagai satu paragraf dan disusun ulang kalimat per kalimat sinkron dengan besarnya kecenderungan (similiarity) antar kalimatnya. Dengan membaca output integrasi dibutuhkan pembaca bisa terbantu dalam menyerap informasi penting yg terdapat pada perpaduan dokumen yg tidak sama serta tidak perlu lagi membaca sekumpulan dokumen satu per satu.

Hierarchical Clustering

Pada prosedur pemecahan clustering, data akan dikelompokkan sebagai cluster-cluster dari kemiripan satu data menggunakan yg lain. Prinsip dari clustering adalah memaksimalkan kecenderungan antar anggota satu cluster dan meminimumkan kesamaan antar anggota cluster yg tidak sinkron.

Kategori algoritma clustering yang banyak dikenal adalah Hierarchical Clustering. Hierarchical Clustering adalah keliru satu prosedur pemecahan clustering yg bisa dipakai buat meng-cluster dokumen (document clustering). Dari teknik hierarchical clustering, dapat dihasilkan suatu formasi partisi yg berurutan, dimana pada perpaduan tersebut terdapat:

a. Cluster – cluster yg memiliki poin – poin individu. Cluster – cluster ini berada pada level yang paling bawah.

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

Hasil holistik dari prosedur pemecahan hierarchical clustering secara grafik dapat digambarkan menjadi tree, yang diklaim dengan dendogram. Tree ini secara grafik menggambarkan proses penggabungan menurut cluster – cluster yg ada, sehingga menghasilkan cluster menggunakan level yang lebih tinggi. Gambar 1 adalah model dendogram.

Gambar  Dendogram 

Agglomerative Hierarchical Clustering

Metode ini menggunakan taktik disain Bottom-Up yang dimulai dengan meletakkan setiap obyek sebagai sebuah cluster tersendiri (atomic cluster) dan selanjutnya menggabungkan atomic cluster – atomic cluster tersebut sebagai cluster yg lebih besar serta lebih besar lagi sampai akhirnya semua obyek menyatu dalam sebuah cluster atau proses dapat pula berhenti apabila sudah mencapai batasan kondisi eksklusif. Metode Agglomerative Hierarchical Clustering yang dipakai dalam penelitian ini merupakan metode AGglomerative NESting (AGNES). Cara kerja AGNES dapat ditinjau pada gambar.

Adapun ukuran jeda yang digunakan untuk menggabungkan dua butir obyek cluster merupakan Minimum Distance yg dapat dipandang dalam persamaan.

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

Algoritma Cosine Distance

Metode cosine distance adalah metode yang digunakan buat menghitung similarity (tingkat kecenderungan) antar 2 butir obyek. Pada penelitian ini obyek Berikut merupakan persamaan menurut metode Cosine Distance :

Pada penelitian ini obyek v1 serta v2 adalah 2 butir dokumen yg tidak selaras.

Proses Parsing, Stemming dan Stopword Removal

Dalam bidang rapikan bahasa serta linguistik, parsing merupakan sebuah proses untuk berakibat sebuah kalimat menjadi lebih bermakna atau berarti dengan cara memecah kalimat tersebut sebagai kata-kata atau frase – frase.

Stemming adalah proses pemetaan dan penguraian aneka macam bentuk (variants) berdasarkan suatu kata menjadi bentuk kata dasarnya. Proses stemming digunakan di pada proses Information Retrieval (pencarian berita) buat menaikkan kualitas informasi yg didapatkan .

Stopwords removal merupakan sebuah proses buat menghilangkan istilah yg 'nir relevan' pada output parsing sebuah dokumen teks menggunakan cara membandingkannya dengan Stoplist (Stopword list) yang terdapat. Contoh berdasarkan Stopword contohnya, istilah sambung, artikel dan kata depan. 

Bobot Relasi antar kalimat

Bobot rekanan antara dua kalimat merupakan sama menggunakan jeda antara ke 2 kalimat tersebut. Konsekuensinya merupakan apabila bobot relasi antara 2 kalimat tertentu lebih mini dari yg lain, maka jarak keduanya juga lebih dekat [5, 8]. Secara formal, misal masih ada n kalimat P=S1, S2, …, Sn, maka bobot relasi antara 2 kalimat Si serta Sj bisa dicermati pada persamaan 3. 

dimana i, j adalah letak kalimat ke i serta j;

adalah jumlah istilah yg sama atara Si dan Sj sesudah stopword yg terdapat dihilangkan ; dan W(Sj) merupakan bobot kalimat ke j.

Pada penelitian sebelumnya letak kalimat ke i serta j diukur hanya pada satu paragraf saja. Pada penelitian ini definisi tadi diubah, yaitu: i dan j adalah angka urut kalimat pada adonan dokumen yg disusun secara berurutan menurut relasi antar dokumen, yang diukur memakai Cosine Distance (persamaan dua).

Bobot Kalimat

Bobot Kalimat merupakan sebuah nilai senuah kalimat yg mengindikasikan sebeberapa krusial arti kalimat tersebut pad sebuah paragraf. Semakin tinggi nilai kalimatnya semakin krusial pula adalah 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 serta telah dimodifikasi pada penelitian sebelumnya. Ada empat macam bobot kalimat yg dipakai pada penelitan sebelumnya yaitu:

W1 ® Banyaknya istilah yang sama antara kalimat yg dihitung menggunakan daftar istilah kunci (keyword) pada dokumen tempat kalimat tersebut berada.

W2 ® Nilai yang dipengaruhi menurut kemunculan istilah – istilah didalam kalimat terhadap pemakaian kata – kata tadi dalam dokumen tempat kalimat berada.

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

W4 ® Menghitung banyaknya relasi sebuah kalimat menggunakan kalimat – kalimat lain dalam dokumen yang sama.

Bobot Kalimat total dapat dipandang pada persamaan 4.

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

Untuk penelitian kali ini perhitungan bobot kalimat ini dimodifikasi kembali agar sesuai kebutuhan pada penelitian ini. Pemikiran berdasarkan modifikasi ini adalah:

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

- Pada penelitian ini terdapat beberapa dokumen yang digabungkan, untuk itu perlu diperhitungkan bahwa bobot sebuah kalimat nir hanya diukur terhadap kalimat lain pada dokumen yg sama melainkan juga terhadap kalimat lain di dokumen yg berbeda yang 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 penting sebuah kalimat dibandingkan menggunakan kalimat – kalimat lain yg masih ada pada semua dokumen yg akan diintegrasikan. Persamaan hasil modifikasi bisa dipandang dalam persamaan lima.

dimana W5 adalah Banyaknya istilah kunci (keyword) yg sama antara kalimat yg dihitung menggunakan daftar istilah kunci pada semua dokumen yg akan diintegrasikan. Asumsinya merupakan semakin banyak kata dalam kalimat tersebut sama dengan daftar kata kunci, semakin krusial eksistensi kalimat tadi pada dokumen hasil integrasi.

1. Desain Aplikasi Automated Text Integration

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

Gambar Diagram Use Case Aplikasi

Inti dari pelaksanaan ini merupakan Do Integration, dimana pada use case ini proses integrasi beberapa dokumen yg dipilih dilakukan. Diagram activity dari use case ini dapat ditinjau pada Gambar 3.

Gambar  Do Integration Activity Diagram

Penjelasan menurut diagram activity pada gambar tiga adalah menjadi 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 kabar nama serta path dokumen – dokumen tersebut pada listbox dokumen. Format dokumen yang dapat dipilih merupakan *.doc serta *.txt.
• Setelah user menentukan pilihan menu ‘Integration’, pelaksanaan akan meminta user mengisikan nilai batas terendah similarity antar dokumen yg diijinkan oleh user buat dokumen – dokumen yg akan diintegrasikan.
• Selanjutnya apabila listbox dokumen terisi, pelaksanaan akan merubah semua dokumen yang terdapat kedalam bentuk teks, menggantinya sebagai sekumpulan kalimat dan kata – kata yg berurutan (divide to word / parsing), melakukan proses stemming, stopword removal, menandai kata – istilah mana saja yang merupakan keyword, dan menghitung similarity antar dokumen menggunakan persamaan 2.
• Selanjutnya aplikasi akan memperlihatkan list similarity antar dokumen serta memberi indikasi apabila similarity tadi dibawah nilai yg sudah ditentukan. Bila user memilih melanjutkan proses menggunakan memilih ‘continue’, aplikasi akan menyusun dokumen – dokumen tadi secara berurutan sinkron menggunakan level similarity-nya.
• · Langkah berikutnya aplikasi akan menghitung bobot kalimat (Weight Of Sentence) dan bobot relasi antar kalimat (Weight Of Relation). Bobot rekanan antar kalimat ini yang akan digunakan buat mengintegrasikan dokumen memakai metode AGglomerative NESting (AGNES).
• Pada proses integrasi, awalnya seluruh kalimat pada seluruh dokumen dianggap menjadi atomic cluster – atomic cluster. Selanjutnya secara sedikit demi sedikit cluster – cluster tadi akan disatukan memakai anggaran Minimum Distance dalam persamaan 1. Setelah seluruh kalimat telah tergabung menjadi sebuah cluster, dilakukan proses buat memecah cluster tadi sebagai paragraf – paragraf. Caranya adalah, kalimat – kalimat yg bergabung terlebih dahulu menjadi cluster – cluster akbar dipercaya menjadi sebuah paragraf tersendiri. Asumsinya, apabila secara natural kalimat – kalimat tersebut bergabung, bisa dipercaya kalimat – kalimat tadi mempunyai similarity yg cukup tinggi dan membahas topik bahasan yg sama. Agar lebih kentara, proses integrasi ini bisa dilihat pada gambar 4. Sementara buat memproses kalimat – kalimat tersisa yang nir mau bergabung kedalam cluster – cluster besar , digunakan aturan sebagai berikut:

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

o Jika lebih berdasarkan satu kalimat, kalimat – kalimat yg tersisa tadi akan dipaksakan bergabung sebagai satu paragraf tersendiri.

Gambar Proses Integrasi menggunakan AGNES

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

Pengujian Aplikasi

Pengujian Hasil Integrasi

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

Gambar Dokumen berasal ke - 0

Gambar Dokumen dari ke - 1

Gambar  Hasil Integrasi

Pengujian Dalam Bentuk Survey

Pengujian ini dilakukan menggunakan cara meminta donasi 100 orang responden generik buat membaca dokumen – dokumen berasal serta dokumen hasil integrasi, lalu menjawab tiga pertanyaan berikut:

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

2. Menurut anda, apakah dokumen output integrasi tersebut sudah menaruh citra secara umum berdasarkan holistik dokumen yg terdapat sebelumnya ? A. Ya B. Tidak

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

Kedua jenis dokumen yang digunakan sebagai bahan informasi lapangan bertipe eksposisi, yaitu dokumen yang berusaha menyebutkan suatu prosedur atau proses, menaruh definisi, memberitahuakn, mengungkapkan, menafsirkan gagasan, memberitahuakn bagan atau tabel, atau mengulas sesuatu kepada pembaca. 

Sementara buat dokumen berbentuk naratif misalnya cerita warga , tidak disertakan pada survey, karena peneliti sendiri sudah melihat adanya kerancuan dalam jalan cerita dalam dokumen output integrasinya. Hal ini selalu terjadi pada beberapa uji coba dalam beberapa topik dokumen deskriptif, misalnya “Timun Emas”, “Sangkuriang”, “Jack dan Kacang Polong” dan lain – lainnya. Oleh karena itu bisa disimpulkan bahwa proses integrasi ini nir cocok buat dokumen yang berjenis deskriptif.

Pengujian Kecepatan Proses 

Pengujian kecepatan proses pelaksanaan 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 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, 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, //www.miislita.com/information-retrieval-tutorial/cosine-similarity-tutorial.html (January, 2007)

[4] Gregorius S. Budhi, Ibnu Gunawan serta 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. Tiga 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 generik 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)