PENCARIAN JUDUL TA MENGGUNAKAN TEXT MINING DAN METODE SUFFIX TREE Aulia Adi Pribadi.1, Entin Martiana K2 Mahasiswa Jurusan Teknik Informatika1 , Dosen Pembimbing 2 Jurusan Teknik Informatika Politeknik Elektronika Negeri Surabaya Institut Teknologi Sepuluh Nopember Kampus PENS-ITS Keputih Sukolilo Surabaya 60111 Telp (+62)31-5947280, 5946114, Fax. (+62)31-5946114 Email :
[email protected]
ABSTRAK Dalam pencarian terhadap suatu kumpulan dokumen umumnya menghasilkan pencarian berupa dokumen dokumen yang tersusun berdasarkan peringkat kecocokan dalam daftar yang panjang. Tidak jarang dalam suatu pencarian menghasilkan puluhan bahkan bisa mencapai ribuan dokumen yang menyebabkan pengguna harus meneliti satu persatu dokumen yang dikehendaki. Hal ini menyebabkan pengguna mengalami kesulitan terutama dalam hal waktu untuk menentukan dokumen yang relevean dengan topic yang dicari.. Pada Proyek Akhir ini dikembangkan suatu aplikasi pengelompokan dokumen berbasis web dengan metode suffix tree clustering. Konsep dasar metode ini adalah dengan mengelompokkan dokumen hasil pencarian ke dalam bentuk grup-grup atau cluster berdasarkan frase bersama yang terdapat di dalam dokumen-dokumen tersebut. Aplikasi membutuhkan input pencarian dan akan menghasilkan output berupa cluster yang di dalamnya terdapat dokumen yang bersesuaian. Cluster ini bisa bertingkat-tingkat tergantung dari kata atau phrase yang mungkin bisa dibedakan lagi pada cluster induk yang sama. Cluster- cluster yang dihasilkan inilah yang ditampilkan kepada pengguna. Selanjutnya pada cluster terakhir yang dipilih akan menampilkan kumpulan dokumen yang masing-masing terdiri dari judul dan cuplikan. Dengan metode ini diharapkan hasil pencarian judul TA akan lebih mudah untuk ditelusuri. Kata kunci : text mining, suffix tree, suffix tree clustering, pengelompokan dokumen
ABSTRACT In search of a collection of documents generally results in the search of documents arranged by rank a match in a long list. Not uncommon in a quest to generate tens of thousands of documents can even reach that cause users to have to examine one by one the desired document. This led to users having trouble, especially in terms of time to determine which documents relevean to the topic that looking for. This Final Project developed a web-based document clustering applications with the suffix tree clustering method. The basic concept of this method is to classify documents in the form of search results into groups or clusters based on common phrases contained in these documents. The application requires a search input and will produce output in the form of clusters in which there is a corresponding document. The cluster can be stratified depending on the word or phrase that may be distinguished on the same parent cluster. The resulting clusters is shown to the user. Then on the last of the selected cluster will feature a collection of documents, each consisting of titles and snippets. With this method is expected to result of final project title search will easier to navigate. Keyword: text mining, suffix tree, suffix tree clustering, Cluster
1
1. PENDAHULUAN Perkembangan teknologi saat ini khususnya pada dunia internet berkembang sangat pesat yang disebabkan oleh berkembangnya ilmu tekonologi informasi pada semua aspek kehidupan. Hal ini yang menyebabkan banyak pengguna teknologi informasi mencari informasi informasi yang mereka butuhkan sehingga mengakibatkan munculnya suatu ilmu baru dalam teknologi informasi yaitu Pencarian Informasi. (Information Rertrieval) Sistem pencarian dokumen umumnya menampilkan hasil pencarian yang bedasarkan kata kunci (keywords) dan peringkatnya yang ditampilkan dalam daftar yang panjang. Pengguna akan memilih dokumen yang dicari dalam daftar yang panjang tersebut sesuai dengan pengguna inginkan. Sayangnya sebagian search engine masih mengadopsi sistem tersebut. Selain itu sebagian besar search engine memiliki karakteristik pencarian dokumen yang tingkat kecocokannya(rate similiarity) rendah. Dalam permasalahan tersebut kita dapat menggunakan model clusteringuntuk mengelompokkan hasil pencarian dokumen yang sesuai dengan topik yang terkait sehingga memudahkan pengguna dalam memilih dokumen yang relevan dengan topik.Dalam proyek akhir ini digunakan metode Suffix Tree Clustering (STC) untuk mengelompokkan dokumen hasil pencarian.STC tidak memperlakukan dokumen sebagai suatu himpunan kata-kata tetapi lebih sebagai string, yaitu memanfaatkan kedekatan informasi antar kata. STC bergantung pada model suffix tree untuk mengefisiensikan identifikasi set dokumen yang berbagi frase dan menggunakan informasi ini untuk membuat cluster. Tujuan dari proyek akhir ini adalah membangun sistempencarian judul tugas akhir untuk studi kasus PENS – ITS. Tugas akhir ini nantinya diharapkan mampu untuk : Meningkatkan kemampuan dalam pencarian informasi judul Tugas Akhir Memberikan informasi secara cepat dan relevan untuk pencarian judul Tugas Akhir.
Suffix tree Clustering memiliki dua langkah utama. Dalam langkah pertama, pencarian shared phrase untuk semua dokumen berita yang dikoleksi. Kita menyebut shared phrase sebagai phrase cluster atau base cluster, yang ditemukan dengan menggunakan suatu struktur data yang dinamakan suffix tree [Novan]. Dalam langkah kedua, kita mengkombinasikan base cluster-base cluster ke dalam suatu cluster. Penggabungan antar dua base cluster didasarkan pada jumlah dokumen yang melakukan overlap diantara kedua base cluster tersebut [Zamir]. Suatu phrase yang dimaksud dalam konteks algoritma ini adalah urutan satu atau lebih kata-kata. STC memiliki tiga langkah utama, yaitu : 1. 2. 3.
Beberapa karakteristik yang membuat Suffix tree Clustering cocok digunakan untuk pengelompokan dokumen. Pertama adalah mengenerate cluster-cluster untuk pengelompokan dokumen berdasarkan phrase. Phrase juga bermanfaat untuk membangun uraian dan keakuratan deskripsi dari clustercluster. Kedua, tidak tergantung pada model data. Hal itu mengasumsikan hanya dokumendokumen dengan topik yang sama yang akan memiliki shared phrase. Ketiga, STC memperbolehkan adanya overlaping cluster. Hal itu sangat penting untuk menghindari pembatasan bahwa setiap dokumen hanya memiliki satu cluster saja, karena sering kita jumpai satu dokumen mempunyai lebih dari satu topik dan dengan begitu terdapat kemiripan yang lebih dari satu kelompok dokumen. Keempat, STC menggunakan definisi cluster yang sederhana. Semua dokumen yang berisi salah satu phrase cluster akan menjadi anggota dari cluster tersebut. STC menggunakan phrase untuk mendeteksi kemiripan antar dokumen. STC menggunakan suffix tree untuk mengidentifikasi phrase. Fitur yang membuat suksesnya STC sebagai algoritma clustering adalah adanya overlaping cluster. Kualitas cluster yang terbentuk dari algoritma STC ini akan menurun jika tanpa menggunakan multiword phrase dan tidak memperbolehkan adanya overlaping cluster.
2. DASAR TEORI 2.1 Suffix tree Clustering
Inti dari suatu hasil pencarian yang menerapkan clustering adalah penggunaan algoritma clustering. Algoritma Suffix tree Clustering (STC) memiliki dua kunci utama, yaitu : 1. 2.
Cleaning Dokumen. Identifikasi Base Cluster menggunakan Suffix tree. Mengkombinasikan Base Cluster ke dalam suatu cluster.
2.2 Document Cleaning
Menggunakan phrase sebagai dasar pembentukan clusternya. Menggunakan suatu definisi cluster sederhana.
Document Cleaning adalah tahap awal dalam algoritma Suffix tree Clustering. Pada tahap ini, dokumen yang telah didapat dari proses download akan dibersihkan dan dipersiapkan untuk tahap selanjutnya. Proses
2
ntuk mempersiapkan dokumen meliputi proses pembersihan dokumen , proses analisa leksikal teks, proses penghapusan stopword, dan proses stemming. 2.3 Stemming Bahasa Indonesia
B
Dalam morfologi kata Bahasa Indonesia dikenal adanya 3 imbuhan yaitu awalan (prefiks), sisipan, dan akhiran (sufiks). Untuk penanganan dokumen yang mengandung kata jadian pada tugas akhir ini hanya akan menghilangkan awalan dan akhiran [William]. Metode ini didahului dengan pembacaan tiap kata dari file sampel. Sehingga input dari algoritma ini adalah sebuah kata yang kemudian dilakukan : Sehingga bentuknya menjadi : Urutan pemotongan awalan dan akhiran adalah sebagai berikut : 1. 2. 3.
Pecah isi dokumen dalam bentuk array sejumla kata yang terdapat dalam dokumen Lakukan pemotongan imbuhan menurut aturan pemotongan. Simpan hasil pemotongan dalam array baru.
Aturan pemotongan dilakukan secara berurutan sebagai berikut : a. b.
Pemotongan Akhiran Pemotongan Awalan
Untuk awalan dan akhiran semua gabungan dua awalan atau akhiran akan dilakukan sampai awalan atau akhiran tersebut habis. 2.4 Identifikasi Base Cluster
Tahap identifikasi base cluster merupakan tahap terpenting dalam algoritma suffix tree clustering, karena pada tahap ini akan menghasilkan cluster-cluster dasar [Zamir]. Pembentukkan base cluster dilakukan dengan cara menemukan share phrase antar dokumen. Untuk menemukan share phrase digunakan struktur data suffix tree. Dengan menggunakan struktur data ini, maka setiap dokumen akan direpresentasikan menjadi suatu kalimat. Untuk menemukan base cluster dapat dilakukan dengan cara membuat suatu invert index dari phrase untuk semua dokumen. Contoh pembentukkan suffix tree untuk kalimat cat ate cheese, mouse ate cheese too, dan cat ate mouse too ditunjukkan pada Gambar 1. Pada Gambar 1 menunjukkan adanya internal node yang terbentuk. Setiap internal node merepresentasikan suatu kelompok dokumen dan share phrase untuk kelompok tersebut. Oleh karena itu, setiap internal node juga merepresentasikan base cluste yang terbentuk. Semua base cluster yang terbentuk dapat ditunjukkan pada Tabel 1. 3
Gb 1 IdentifikasiBase Cluster Tabel 1 Base Cluster yang terbentuk Base Phrase Documents Cluster a cat ate 1,3 b Ate 1,2,3 c Cheese 1,2 d Mouse 2,3 e Too 2,3 f ate cheese 1,2 Setiap base cluster yang terbentuk memiliki suatu score. Penghitungan score merupakan suatu fungsi dari jumlah dokumen yang masuk anggota base cluster dan jumlah kata yang menyusun phrase dari base cluster. Fungsi untuk menghitung score base cluster ditunjukkan oleh persamaan (1). (1) s(B) = |B|.f(|P|) dimana pada persamaan (1) : |B|= jumlah dokumen di dalam base cluster B dan |P| = jumlah kata yang menyusun frase P. f(|P|) = 0, jika |P| = 1 dan f(|P|) = 6, jika |P| ≥ 6 2.5 Kombinasi Base Cluster
Tahap ini digunakan untuk menangani ovelaping cluster. Dalam tahap ini, phrase tidak dipertimbangkan. Sebelum melakukan kombinasi antar base cluster, kita harus menghitung dulu nilai similarity antar base cluster yang didasarkan pada jumlah dokumen yang overlap. Adanya overlaping dokumen ini didasarkan karena dokumen memiliki lebih dari satu topik sehingga dokumen dapat memiliki lebih dari satu phrase yang di-share. Ukuran nilai similarity menggunakan nilai biner. Rumus untuk menghitung nilai similarity antar base cluster ditunjukkan pada persamaan (2) dan (3). |Bm ∩ Bn| / |Bm| > 0,5 |Bm ∩ Bn| / |Bn| > 0,5
(2) (3)
Dimana pada persamaan (2) dan (3) : |Bm ∩ Bn| = jumlah dokumen yang overlap terhadap base cluster Bm dan Bn. |Bm| dan |Bn| = jumlah dokumen dalam base cluster Bm dan Bn.
Dalam persamaan di atas, menunjukkan penggunaan nilai threshold 0,5 karena nilai tersebut merupakan nilai tengah antara 0 sampai 1. Jika persamaan (2) dan (3) bernilai benar maka similarity akan bernilai 1 sehingga antara kedua base cluster tersebut akan terhubung. Jika salah satu dari persamaan (2) dan (3) bernilai benar atau keduanya bernilai salah maka similarity akan bernilai 0 sehingga antara kedua base cluster tersebut tidak terhubung.
3.2 Filtering Tabel 3 Hasil Pengujian Filtering Input
-
informasi saat ini menjadi sesuatu yang sangat penting dalam berbagai aspek
Output
- informasi - sesuatu
3.3 Proses Stemming Gb 2 Hasil kombinasi Base Cluster Dari Gambar 3 menunjukkan bahwa antar base cluster terhubung sehingga dari 6 base cluster tersebut akan membentuk satu cluster tunggal. 3.
PENGUJIAN DAN ANALISIS Ttext mining dengan beberapa dokumen.
3.1 Tokenizing Tabel 2 Hasil Pengujian Tokenizing Input
Informasi saat ini menjadi sesuatu yang sangat penting dalam berbagai aspek kehidupan
Output
-
-
Hampir setiap kalimat dalam bahasa indonesia tersusun dari kata-kata yang berimbuhan. Untuk mengembalikan kata-kata tersebut ke bentuk dasarnya diperlukan suatu proses, proses inilah yang dinamakan stemming. Pada pengujian ini, akan diberikan inputan suatu kalimat yang tersusun dari kata berimbuhan. Hasil yang benar dari pengujian ini adalah katakata berimbuhan dalam kalimat tersebut akan berubah ke bentuk dasarnya. Hasil pengujian ini ditunjukkan pada Tabel 7. Pada Tabel 4 menunjukkan bahwa katakata yang menyusun kalimat dikembalikan ke bentuk dasarnya. Contoh hasil stemming kata ditunjukkan pada Tabel 5 . Tabel 4 Hasil Pengujian Proses Stemming
informasi saat ini menjadi sesuatu yang sangat penting dalam berbagai aspek kehidupan
Input
Kalimat
digunakan
sebagai ukuran
Output
Kalimat guna bagai ukur pakai kata
Tabel 5 Contoh Hasil Stemming Kata Kata Berimbuhan Digunakan Sebagai Pemaikaian Ukuran Terurut
4
Kata Dasar guna bagai pakai ukur urut
3.4 Tahap Pembentukkan Suffix tree Pada tahap ini akan dilakukan pengujian terhadap hasil pembentukan suffix tree. Pengujian dilakukan dengan memberikan inputan beberapa kalimat. Hasil pengujian dapat dilihat dari base cluster yang terbentuk. Tabel 6 menunjukkan hasil uji coba pembentukkan suffix tree. Beberapa kalimat yang digunakan sebagai uji coba pembentukkan suffix tree antara lain: 1. Kucing makan keju 2. Kucing makan tikus juga 3. Tikus makan keju juga 4. Tikus makan ikan mati 5. Kucing makan ikan mati juga 6. Kucing bermain bola Tabel 6 Hasil Pengujian Generate Suffix tree No Base Share Parent Score Cluster Phrase 1 1 keju 0 2 2 2 makan 0 5 3 3 kucing 0 4 4 4 juga 0 3 5 5 tikus 0 3 6 6 keju 2 2 7 8 makan 5 2 8 9 mati 0 2 9 11 ikan mati 0 4 10 12 ikan mati 2 4 11 13 bola 0 1 12 15 main bola 0 2 13 16 makan 3 3
Pada tahap ini akan dilakukan pengujian terhadap hasil penghitungan similiarity antar base cluster. Pengujian juga dilakukan terhadap pembentukkan cluster. Pengujian dilakukan dengan data base cluster yang didapat dari Tabel 7. Tabel 7 Cluster yang terbentuk dari hasil uji coba
Base Cluster 1, 6 2,3,4,5,25,13 14,15,16 23,24
157 308 132 242 500 222 407 844
78 169 72 103 262 140 235 484
7 30 2 9 36 4 13 50
4. KESIMPULAN Setelah melalui tahap implementasi dan uji coba, maka dapat ditarik kesimpulan sebagai berikut: 1. Algoritma suffix tree clustering dapat diterapkan untuk clustering dokumen berbahasa Indonesia. 2. Untuk melakukan clustering dokumen yang didasarkan pada multiword phrase atau base cluster yang digunakan struktur data suffix tree. 3. Untuk pembentukan suffix tree membutuhkan waktu yang lama karena selain tergantung pada jumlah dokumen yang dikoleksi juga tergantung pada jumlah kata untuk setiap dokumen yang ingin diklasifikasikan. DAFTAR PUSTAKA
3.5 Tahap Penghitungan Similiarity
Cluster 0 1 2 3
5 10 3 5 10 3 5 10
Score 4 20 10 3
Pada tabel 7 menunjukkan data yang terdapat pada tabel 6 di merger dan membentuk 4 cluster besar . 3.5 Perhitungan Waktu. Tabel 8 hasil percobaan waktu generate suffix tree Jml Jml Jml Base Waktu Dok Kata Cluster (Detik) 3 31 25 1 5 56 38 3 10 104 72 18 3 91 42 1,5 5
Suffix Trees diambil dari http://www.allisons.org/ll/AlgDS/Tree/Suffi x/ Adiwijaya Igg Ph.D. 2006. Text Mining and Knowledge Discovery, Kolokium bersama komunitas datamining Indonesia & softcomputing Indonesia. Agus Zainal Arifin, 2008. Klasifikasi Online Dokumen Berita dengan Menggunakan Algoritma Suffix Tree Clustering. Sesindo 2008 -ITS Fast String Searching With Suffix Trees diambil dari http://marknelson.us/1996/08/01/suffixtrees/ Guihong Cao, Dawei Song dan Peter Bruza. 2003. Suffix Tree Clustering on Post Retrieval Documents. Hung Chim dan Xiaotie Deng. 2007. A New Suffix Tree Similarity Measure for Document Clustering. Canada : IW3C2 Jon Atle Gulla. 2009. Contextualized Clustering in Exploratory Web Search. Stoplist bahasa indonesia diambil dari http://yudiwbs.wordpress.com/2008/07/23/st op-words-untuk-bahasa-indonesia/ Novan S. 2001. Implementasi Aplikasi Information Retrieval Untuk Pendeteksian dan Klasifikasi Berita Kejadian Berbahasa Indonesia Berbasis Web. Tugas Akhir,
Jurusan Teknik Informatika Fakultas Teknologi Informasi ITS Surabaya. Samue Sambasivam dan Nick Theodosopoulos. 2006. Advances Data Clustering Methods of Mining Web Documents. Tries and Suffix Trees diambil dari http://www.cs.mcgill.ca/~cs251/Ol dCourses/1997/topic7/
6
7
