ABSTRAK PENGEMBANGAN SUFFIX TREE CLUSTERING UNTUK COMPARATIVE TEXT MINING
Oleh KUSMAYA NIM : 23504036
Kemajuan teknologi mendukung komputerisasi dalam berbagai hal, seperti: pencatatan, perhitungan, dan penggambaran. Hal ini menyebabkan tersedianya data dalam jumlah besar, yang dapat menghasilkan pengetahuan yang berguna. Analisis terhadap data tersebut merupakan sesuatu yang penting, baik dalam melakukan eksplorasi, maupun dalam pengambilan keputusan. Pentingnya analisis tersebut menyebabkan penelitian tentang data mining berkembang. Comparative Text Mining (CTM) merupakan bagian dari text mining yang secara khusus mempunyai fungsi; menemukan tema umum dari semua koleksi, dan menemukan tema khusus dari suatu dokumen. Penggunaan CTM salah satunya yaitu untuk summarizing reviews. Summarization adalah proses otomatis yang menghasilkan versi dokumen yang lebih pendek (50% atau kurang) namun tetap berguna bagi pengguna. Dengan summarization, pengguna diharapkan dapat menangkap isi dokumen tanpa harus melihat keseluruhan dokumen. Metode clustering adalah metode yang memiliki kemampuan untuk menganalisis serta mengelompokkan secara otomatis dokumen-dokumen. Teknik clustering pada umumnya menggunakan kata dan dokumen biasanya dianggap sebagai kumpulan kata-kata tanpa adanya urutan atau yang disebut bag of word. Suffix Tree Clustering (STC) adalah algoritma pertama yang menggunakan frasa (multiword terms) sehingga prosesnya lebih sederhana dibandingkan dengan algoritma yang lain. STC adalah algoritma incremental, kompleksitas waktu perhitungannya linear O(n) dan memenuhi kriteria untuk document clustering Web. Penerapan algoritma STC untuk CTM dilakukan untuk membuktikan dan melakukan kajian terhadap performansi dari algoritma STC tersebut. Dalam eksperimen dilakukan pengamatan pengaruh parameter terhadap optimalisasi hasil yang dicapai, yaitu dengan cara melakukan komparasi terhadap tema yang dihasilkan oleh CTM dengan tema yang dihasilkan oleh STC.
Kata kunci: metoda clustering, suffix tree clustering, comparative text mining, summary, dan tema.
i
ABSTRACT DEVELOPMENT OF SUFFIX TREE CLUSTERING FOR THE COMPARATIVE TEXT MINING
By KUSMAYA NIM : 23504036
The progress of technology supports the computerization in many field, i.e: recording, computing, and illustration. These lead to the need of available of data in large volume, which can yield the knowledge which is useful. The analysis to the data is needed, whether in exploring or in decision making. The importance of the data analysis cause the research of about data mining expanding. Comparative Text Mining (CTM) is one of many technique in text mining which peculiarly have the function; finding common theme from all collection, and finding the special theme from a document. The use of CTM, for example, is to summarizing reviews. Summarization is an automatic process yielding shorter document version (50% or less) but remains useful for user. By summarization, user is expected to be able to catch the document’s content without having to see the overall of document. Clustering method is a method owning ability to analyse and also to group documents automatically. Generally, clustering technique using word and document is usually considered as a word sets without the existence of sequence, called bag of word. Suffix Tree Clustering (STC) is the first algorithm that use phrase (multi-word terms) so that its process is simpler compared with other algorithm. STC is an incremental algorithm, the complexity of the algorithm is linear O(n) and fulfill the criterion for clustering web documents. This thesis aims to study and to prove the performance of STC’s algorithm by applying it to CTM case. In experiment, observation is done to see how parameter influence optimalization which may result, by comparing the theme yielded by CTM with the theme yielded by STC. Keywords: method clustering, suffix tree clustering, comparative text mining, summary, and theme.
ii
PEDOMAN PENGGUNAAN TESIS Tesis S2 yang tidak dipublikasikan terdaftar dan tersedia di Perpustakaan Institut Teknologi Bandung, dan terbuka untuk umum dengan ketentuan bahwa hak cipta ada pada pengarang dengan mengikuti aturan HaKI yang berlaku di Institut Teknologi Bandung. Referensi kepustakaan diperkenankan dicatat, tetapi pengutipan atau peringkasan hanya dapat dilakukan seizin pengarang dan harus disertai dengan kebiasaan ilmiah untuk menyebutkan sumbernya.
Memperbanyak atau menerbitkan sebagian atau seluruh tesis haruslah seizin Direktur Program Pascasarjana, Institut Teknologi Bandung.
iii
KATA PENGANTAR
Bismillahirrahmaanirrahiim Puji syukur penulis panjatkan ke hadirat Allah SWT yang senantiasa memberikan nikmat dan karunia-Nya sehingga penulis dapat menyelesaikan tesis ini.
Tujuan dari pembuatan tesis ini adalah sebagai salah satu syarat kelulusan dalam pendidikan Magister Informatika, Sekolah Teknik Elektro dan Informatika, Institut Teknologi Bandung. Pada kesempatan ini penulis ingin menyampaikan rasa terima kasih yang sebesar-besarnya kepada: 1. Bapak Dr. Oerip S. Santoso, M.Sc. selaku pembimbing yang telah banyak meluangkan waktu dan pikiran untuk membimbing dan senantiasa memberikan masukan serta kritikan yang sangat bermanfaat sehingga penulis dapat menyelesaikan tesis ini. 2. Ir. Sri Purwanti, M.Sc. sebagai wali angkatan 2004 S2-IF yang senantiasa membimbing, mengarahkan, dan memberikan motivasi selama pendidikan pascasarjana. 3. Ibu Dra. Harlili, M.Sc. dan Bapak Drs. Judhi Santoso, M.Sc. selaku penguji yang telah memberikan masukan dan kritikan untuk perbaikanperbaikan tesis ini. 4. Ibu Yani Widyani, ST., MT. selaku penguji seminar tesis yang telah memberikan masukan dan kritikan untuk perbaikan-perbaikan tesis ini. 5. Seluruh staf pengajar Program Studi Teknik Informatika ITB, atas ilmu pengetahuan yang telah diberikan selama pendidikan pascasarjana. 6. Staf Tata Usaha dan Perpustakaan, khususnya Bapak Ade dan Ibu Nurhayati, yang telah banyak membantu penulis selama kuliah dan penulisan tesis ini. 7. Alm. Ayah, Ibu, Istri dan Ananda penulis atas segala do’a, dukungan, pengertian, dan pengharapan mereka yang tiada henti. 8. M. Shalahudin, ST. dan Rosa A. S., ST. yang telah banyak membantu penulis dan menjadi teman diskusi.
iv
9. Rekan-rekan pengajar Program Studi Teknik Informatika UNLA Bandung yang telah memberikan dukungan dan motivasi selama pendidikan pascasarjana. 10. Rekan-rekan di Program Studi Informatika angkatan 2004, atas kebersamaannya selama kuliah, semoga tali silaturahmi tetap terjaga.
Penulis
menyadari
bahwa
masih
terdapat
kekurangan-kekurangan
yang
menyebabkan tesis ini jauh dari sempurna. Oleh karena itu, saran dan kritik yang membangun sangat penulis harapkan untuk perbaikan dan pengembangan lebih lanjut. Akhir kata, semoga tesis ini dapat bermanfaat bagi perkembangan keilmuan.
Bandung, September 2007
Penulis
v
DAFTAR ISI
ABSTRAK ............................................................................................................. i ABSTRACT .......................................................................................................... ii PEDOMAN PENGGUNAAN TESIS ................................................................ iii KATA PENGANTAR ......................................................................................... iv DAFTAR ISI ........................................................................................................ vi DAFTAR LAMPIRAN ....................................................................................... ix DAFTAR GAMBAR ............................................................................................ x DAFTAR TABEL ............................................................................................... xi BAB I Pendahuluan I.1. Latar Belakang .............................................................................................. I-1 I.2. Rumusan Masalah ......................................................................................... I-4 I.3. Tujuan ........................................................................................................... I-4 I.4. Batasan Masalah ............................................................................................ I-5 I.5. Metodologi .................................................................................................... I-5 I.6 Sistematika Penulisan ..................................................................................... I-5 BAB II Dasar Teori II.1. Data Mining ................................................................................................ II-1 II.1.1. Pendahuluan ...................................................................................... II-1 II.1.2. Tahap-tahap pada Data Mining ........................................................ II-2 II.1.3. Text Mining ....................................................................................... II-3 II.2. Metode Clustering ...................................................................................... II-5 II.2.1. Metode Hirarki .................................................................................. II-5 II.2.2. Metode Partisional ............................................................................. II-7 II.3. Document Clustering …………………….………………………………..II-8 II.3.1. Model Ruang Vektor ………………………………………………. II-9 II.3.2. Kriteria Document Clustering ..…………………………………... II-10 II.4. Preprocessing …………………………………………………………… II-11 II.5. Suffix Tree Clustering ………………………………………………….. II-12 II.5.1. Pembentukan Base Cluster ……………………………………….. II-13 II.5.1.1 Skor Base Cluster …..…………………………………………… II-13
vi
II.5.1.2. Pengukuran Similarity ………….…………………………….… II-14 II.5.2 Penggabungan (Merging) Base Cluster …………………………… II-15 II.6. Comparative Text Mining ……………………………………………… II-17 II.6.1 Theme Timing and Extraction ……………………………….……. II-20 II.6.2 Theme Passage Extraction ……..…………………………….……. II-21 II.6.3 Theme Summarization ……………………………………….……. II-22 BAB III Analisis III.1 Proses Document Clustering ………………………….…….…………... III-1 III.1.1. Preprocessing ……..…………………………………………….... III-2 III.1.2. Processing ……………………………………………………..…. III-2 III.2 Analisis Suffix Tree Clustering ………………………..……………..… III-3 III.2.1. Pembentukan Cluster ………………..…………..…………….…. III-3 III.2.2. Topik Cluster ……………….…………..……..……………….… III-4 III.3 Analisis Comparative Text Mining …………………………………….. III-6 III.4 Pengembangan STC untuk CTM ..…..…………………………….….… III-8 BAB IV Implementasi dan Pengujian IV.1 Impementasi Sistem ................................................................................. IV-1 IV.1.1 Batasan Impementasi ....................................................................... IV-1 IV.1.2 Lingkungan Impementasi ................................................................ IV-1 IV.1.3 Impementasi Struktur Data .............................................................. IV-2 IV.1.4 Impementasi Antarmuka ................................................................. IV-6 IV.2 Pengujian Sistem ...................................................................................... IV-9 IV.2.1 Tujuan Pengujian ............................................................................. IV-9 IV.2.2 Kriteria Pengujian .......................................................................... IV-10 IV.2.3 Prosedur Pengujian Metode ........................................................... IV-10 BAB V Analisis Hasil Pengujian V.1 Tujuan dan Skenario Pengujian .................................................................. V-1 V.2 Koleksi Dokumen ....................................................................................... V-2 V.3 Hasil Pengujian ........................................................................................... V-3 V-4 Analisis Hasil Pengujian ............................................................................. V-5
vii
BAB VI Kesimpulan dan Saran VI.1 Kesimpulan ............................................................................................... VI-1 VI.2 Saran ......................................................................................................... VI-2
DAFTAR PUSTAKA
viii
DAFTAR LAMPIRAN Lampiran A. Contoh dokumen ………………………………………………. A-1 Lampiran B. Hasil Komparasi Topik Cluster dan Topik Spesifik ................... B-1 Lampiran C. Cara perhitungan distribusi kata dan nilai theta .......................... C-1
ix
DAFTAR GAMBAR Gambar I-1.
Illustrasi Model Cross-Collection Mixture ………………… I-4
Gambar II.1.
Tahap pada Data Mining ………………………………...… II-3
Gambar II.2.
Taksonomi Metoda Clustering di dalam Data Mining .......... II-6
Gambar II-3.
Clustering Hierarki Agglomerative dan Divisive pada objek data {a,b,c,d,e} .............................................................................. II-6
Gambar II-4.
Dendogram ............................................................................ II-7
Gambar II-5.
Partitioning Clustering: (a) inisialisasi data; (b) iterasi pertama; (c) clustering setelah iterasi kedua (d) clustering setelah iterasi ketiga ..................................................................................... II-8
Gambar II-6.
Grafik fungsi f ...................................................................... II-14
Gambar II-7.
Suffix tree dari strings "cat ate cheese", "mouse ate cheese too" dan "cat ate mouse too" …………………………………… II-16
Gambar II-8.
Base cluster graph ............................................................... II-17
Gambar II-9.
(a) The Simple Mixture Model, (b) Cross-Collection Mixture Model …………………………………………………….. II-19
Gambar II-10.
Proses meng-generate suatu kata w dalam dokumen d pada koleksi Ci ............................................................................. II-21
Gambar II-11.
Algoritma klasifikasi ........................................................... II-22
Gambar III-1.
Proses Clustering Document ……………………………… III-2
Gambar III-2.
Suffix Tree dan Array dari Kalimat “cat ate cheese”, “mouse ate cheese too”, dan “cat ate mouse too” ……………………... III-4
Gambar III-3.
Suffix Tree ............................................................................ III-5
Gambar III-4.
Tema Spesifik Dokumen ...................................................... III-8
Gambar III-6.
Proses pengembangan STC untuk CTM ............................. III-11
Gambar IV-1.
Halaman utama .................................................................... IV-7
Gambar IV-2.
Halaman penyetelan ............................................................. IV-8
Gambar IV-3.
Halaman bantu ..................................................................... IV-8
Gambar IV-4.
Suffix Tree ……………………………………………….. IV-11
x
DAFTAR TABEL
Tabel II-1.
Enam simpul dan frasa .............................................................. II-16
Tabel II-2.
Tabel summary ……………………………..………………… II-19
Tabel III-1. Topik cluster dan nilai theta ..................................................... III-10 Tabel V-1.
Daftar koleksi dokumen ............................................................. V-2
Tabel V-2.
Hasil skenario 1 .......................................................................... V-3
Tabel V-3.
Hasil skenario 2 .......................................................................... V-3
Tabel V-4.
Hasil skenario 3 .......................................................................... V-4
Tabel V-5.
Hasil skenario 4 ........................................................................... V-4
Tabel V-6.
Hasil Komparasi Topik Cluster dan Topik Spesifik untuk 20 Dokumen ..................................................................................... V-6
xi
