Algoritma Porter Stemmer For Bahasa Indonesia Untuk Pre-Processing Text Mining Berbasis Metode Market Basket Analysis
Belakangan ini semakin populer penggunaan Data Mining untuk menggali informasi dari data mentah. Salah satu bagian dari Data Mining yang cukup menarik adalah Text Mining. Metode ini digunakan untuk menggali informasi dari data - data dalam bentuk teks seperti buku, makalah, paper, dan lain sebagainya.
Keyword-Based Association Analysis adalah sebuah metode pada Text Mining yang dikembangkan dari metode Market Basket Analysis. Untuk melakukan proses Keyword-Based Association Analysis data dalam bentuk teks harus dirubah dahulu menjadi format Compact Transaction, yang berisi Document_ID dan Set of Keywords. Ada beberapa hal yang perlu dilakukan pada tahap pre-processing ini, yaitu: Parsing, Stemming, Removing Stopwords dan sebagainya.
Dokumen dalam bahasa indonesia mempunyai keunikan tersendiri, karena kata - kata dalam bahasa indonesia dapat berubah bentuk saat mendapatkan imbuhan. Akibat dari hal proses Stemmer dari dokumen berbahasa Indonesia, yaitu proses mengembalikan kata ke bentuk dasar, memerlukan teknik tersendiri yang berbeda dengan teknik Stemmer pada bahasa - bahasa lain. Pada paper ini, peneliti menerapkan algoritma Porter Stemmer for Bahasa Indonesia, yang dikembangkan oleh Fadillah Z. Tala pada tahun 2003, guna proses Stemmer pada tahap pre-processing data teks menjadi bentuk Compact Transaction.
Teori Penunjang
Knowledge Discovery (Data Mining)
Data Mining atau KDD adalah proses untuk menemukan interesting knowledge dari sejumlah besar data yang disimpan baik di dalam databases, data warehouses atau tempat penyimpanan informasi lainnya. Sebagai sebuah proses, knowledge discovery dapat dilihat pada gambar.
Gambar Tahap-tahap dalam proses knowledge discovery
Text Mining : Keyword Based Association Analysis
Keyword-Based Association Analysis merupakan sebuah analisa yang mengumpulkan keywords atau terms (istilah) yang sering muncul secara bersamaan dan kemudian menemukan hubungan asosiasi dan korelasi di antara keywords atau terms itu.
Seperti analisa lain di dalam text databases, sebelumnya association analysis melakukan pre-processing terhadap text data dengan cara parsing, stemming, removing stopwords, dan sebagainya. Setelah itu baru menjalankan algoritma association mining. Di dalam sebuah document database, setiap dokumen dapat dianggap sebagai sebuah transaksi, sedangkan sekumpulan keywords di dalam document dapat dianggap sebagai sekumpulan items di dalam sebuah transaksi. Sehingga pada database akan mempunyai format sebagai berikut: {document_id, a_set_of _keywords}. Format seperti ini biasa disebut format Compact Transaction.
Parsing
Dalam bidang tata bahasa dan linguistik, parsing adalah sebuah proses yang dilakukan seseorang untuk menjadikan sebuah kalimat menjadi lebih bermakna atau berarti dengan cara memecah kalimat tersebut menjadi kata-kata atau frase-frase.
Stopwords, Stoplist, Stopwords Removal
Kebanyakan bahasa resmi di berbagai negara memiliki kata fungsi dan kata sambung seperti artikel dan preposisi yang hampir selalu muncul pada dokumen teks. Biasanya kata-kata ini tidak memiliki arti yang lebih di dalam memenuhi kebutuhan seorang searcher di dalam mencari informasi. Kata-kata tersebut (misalnya a, an, the on pada bahasa Inggris) disebut sebagai Stopwords.
Sebuah sistem Text Retrieval biasanya disertai dengan sebuah Stoplist. Stoplist berisi sekumpulan kata yang 'tidak relevan', namun sering sekali muncul dalam sebuah dokumen. Dengan kata lain Stoplist berisi sekumpulan Stopwords.
Stopwords removal adalah sebuah proses untuk menghilangkan kata yang 'tidak relevan' pada hasil parsing sebuah dokumen teks dengan cara membandingkannya dengan Stoplist yang ada.
Stemming
Stemming adalah proses pemetaan dan penguraian berbagai bentuk (variants) dari suatu kata menjadi bentuk kata dasarnya. Proses ini juga disebut sebagai conflation. Proses stemming secara luas sudah digunakan di dalam Information retrieval (pencarian informasi) untuk meningkatkan kualitas informasi yang didapatkan.
Porter Stemmer for Bahasa Indonesia
Porter Stemmer for Bahasa Indonesia dikembangkan oleh Fadillah Z. Tala pada tahun 2003. Implementasi Porter Stemmer for Bahasa Indonesia berdasarkan English Porter Stemmer yang dikembangkan oleh W.B. Frakes pada tahun 1992. Karena bahasa Inggris datang dari kelas yang berbeda, beberapa modifikasi telah dilakukan untuk membuat Algoritma Porter dapat digunakan sesuai dengan bahasa Indonesia. Desain dari
Tabel Kelompok rule pertama : inflectional particles
Tabel Kelompok rule kedua :inflectional possesive pronouns
Tabel Kelompok rule ketiga: first order of derivational prefixes
Tabel Kelompok rule keempat: second order of derivational prefixes
Tabel Kelompok rule kelima: derivational suffixes
Desain Sistem
Langkah pre-processing untuk Keyword-Based Association Analysis yang dikembangkan ini sebenarnya adalah bagian dari sebuah sistem Text Mining yang akan diintegrasikan dengan Search Engine buku - buku TA pada perpustakaan UK Petra. Secara keseluruhan DFD level 1 dari sistem dapat dilihat pada gambar 3.
Gambar DFD Level 1 untuk Sistem Text Mining
Pada paper ini penulis hanya akan membahas tahap preprocessing Abstrak TA, sementara itu tahap Generate Association Rules dan tahap Search Keywords dibahas pada makalah lain yang ditulis oleh penulis yang sama, dengan judul "Penggunaan metode Market Basket Analysis untuk meningkatkan kemampuan Search Engine Online buku Tugas Akhir pada Perpustakaan UK Petra".
Pre-processing teks abstrak TA
Gambar DFD Level 2 Proses Pre-processing teks abstrak TA
Walaupun dalam aplikasi tahap 'pre-processing' ini ditujukan untuk pre-processing teks abstrak TA menjadi bentuk Compact Transaction, disain dari tahap ini bersifat umum sehingga dapat dipakai pula untuk melakukan pre-preprocessing dokumen teks lain. Pada langkah ini terdapat tiga proses yang berurutan, yaitu:
- Proses Parsing Abstrak, proses ini digunakan untuk memotong - motong dokumen kata per kata dan menyimpannya pada array kata_abstrak. Flowchart dapat dilihat pada gambar.
- Proses penghapusan Stopwords dari array kata_abstrak, proses ini digunakan untuk menghapus kata - kata yang 'tidak relefan' dari array kata_abstrak. Pada tahap ini semua kata yang ada dalam array akan dikembalikan ke bentuk dasarnya menggunakan algoritma
Porter Stemmer for Bahasa Indonesia. Selanjutnya kata yang telah 'di-stem' dibandingkan dengan tabel Stopword yang ada dan dihapus bila kata tersebut ada dalam tabel Stopword. Kemudian semua kata yang tersisa akan ditandai sebagai 'Keyword' dan diserahkan kepada user untuk diperiksa kembali secara manual (optional). Flowchart dari proses ini dapat dilihat pada gambar.
Gambar Flowchart Parsing
Gambar Flowchart Remove Stopwords
- Proses filter Keywords, pada proses ini keyword - keyword yang didapat akan diproses menjadi format Compact Transaction. Pada proses ini kata - kata (keyword) hasil proses ke - 2 akan dibandingkan dengan tabel Keyword. Bila telah ada pada tabel keyword maka kata yang diproses diberi ID sesuai dengan ID Keyword dan dimasukkan ke dalam tabel Transaksi. Bila belum ada akan dibuat ID baru secara otomatis, kemudian kata bersama ID-nya dimasukkan ke dalam tabel Transaksi dan tabel Keyword. Sementara itu KodeTA pada tabel Transaksi didapat dari nomor buku TA yang diproses.
Fungsi Stemmer
Fungsi Stemmer yang didisain berdasarkan algoritma Porter Stemmer for Bahasa Indonesia adalah inti dari tahap pre-processing untuk sistem Teks Mining yang dibuat (Flowchart dapat dilihat pada gambar 7). Guna dari fungsi ini adalah sebagai berikut:
- Dengan mengembalikan kata menjadi kata dasarnya, akan sangat mengurangi macam kata yang perlu diperiksa dan dibandingkan dengan tabel Stopword maupun tabel Keyword. Hal ini akan mempercepat proses perbandingan kata serta mengurangi isi tabel Stopword dan tabel Keyword.
- Pengembalian kata ke bentuk dasarnya dapat dilihat sebagai pengelompokan beberapa macam kata yang memiliki arti sama atau sejenis dan digeneralisasi menjadi satu kata saja. Hal ini berguna untuk proses Text Mining selanjutnya, karena akan dapat meningkatkan kemungkinan terbentuknya sebuah Rule Assosiasi, atau dapat meningkatkan kualitas Rule Assosiasi yang dihasilkan. Berikut ini ilustrasi sederhana, misal terdapat 5 dokumen yang akan diproses.
- Bila tanpa melalui proses Stemmer, rule yang dihasilkan adalah sebagai berikut:
Rule 1: IF memakan THEN nasi Support = 0.4 ; Confidence = 0,67
Rule 2: IF nasi THEN memakan Support = 0.4 ; Confidence = 0.67
- Dengan melalui proses Stemmer, rule yang dihasilkan adalah sebagai berikut:
Rule 1: IF makan THEN nasi Support = 0.6 ; Confidence = 0,6
Rule 2: IF nasi THEN makan Support = 0.6 ; Confidence = 1
Rule 3: IF makan THEN ayam Support = 0.6 ; Confidence = 0.6
Rule 4: IF ayam THEN makan Support = 0.6 ; Confidence = 1
Pengujian
Pengujian hasil tahap pre-processing dilakukan dengan menggunakan software penyimpan database SQL Server 2000 dan Windows XP. Hardware yang digunakan adalah Prosesor Pentium IV 1,5 GHz, RAM 256 MB. Data yang digunakan untuk pengujian adalah abstrak buku TA UK Petra 2001 s/d 2004 untuk semua jurusan, sebanyak 323 judul. Opsi untuk pemeriksaan hasil Stemmer secara manual dimatikan.
Dari hasil pengujian didapat: Waktu proses = 20 menit 51 detik; Keyword yang dihasilkan sebanyak 5694 kata; Kesalahan hasil Stemmer sebanyak 107 kata, yaitu 2% dari total hasil keyword. Capture isi tabel Transaksi dapat dilihat pada gambar.
Gambar Flowchart fungsi Stemmer
Gambar Isi tabel Transaksi setelah pre-prepocessing
Kesimpulan
- Penerapan algoritma Porter Stemmer for Bahasa Indonesia dalam tahap pre-processing dari metode Keyword-Based Association Analysis sangat berguna karena dapat mengurangi lama waktu proses, mengurangi besar tabel penyimpan Stopword dan Keyword serta dapat meningkatkan kualitas Rule Assosiasi yang dihasilkan oleh metode Keyword-Based Association Analysis.
- Kesalahan proses 'Stem' kata secara otomatis cukup kecil, yaitu 2% sehingga dapat diatasi dengan cepat menggunkan pemeriksaan kembali secara manual terhadap hasil Stemmer.
- Kecepatan proses tahap pre-preprocessing ini cukup bagus, sehingga tahap ini dapat digunakan pada pengaplikasian sistem Text Mining yang dibuat untuk Search Online buku TA pada Perpustakaan UK Petra.
Daftar Pustaka
1. Chakrabarti, Soumen, 2003, Mining the Web: Discovering knowledge from hypertext data. San Francisco: Morgan Kaufman.
2. Frakes, Bill, 1999, What is Information Retrieval, Computer Science Department.Virginia : Tech.
3. Frakes, W.B., R. Baeza, 1992, Information Retrieval, Data Structures and Algorithms. Prentice Hall.
4. Han, Jiawei, Micheline Kamber, 2001, Data Mining : Concepts and Techniques. Morgan Kaufmann.
5. Hand, David, Heikki Mannila, Padhraic Smyth, 2001, Priciples Of Data Mining, The MIT Press.
6. Parsing, Yotor.com, 2005. <http://www.yotor.com/wiki/en/pa/Parsing.htm>
7. Porter, M. F. ,1980, An algorithm for suffix stripping, Program 14(3), p. 130-137.
8. Tala, Fadillah Z., 2003, A Study of Stemming Effects on Information Retrieval in Bahasa Indonesia. Institute for Logic, Language and Computation Universeit Van Amsterdam.
9. Tan, A., 1999, Text mining: The state of the art and the challenges, In Proceedings of the Pacific Asia Conference on Knowledge Discovery and Data mining, PAKDD'99 workshop on Knowledge Discovery from Advanced Databases.p.65-70.
Gregorius S. Budhi, memperoleh gelar S.T. dari Teknik Elektro ITATS Surabaya tahun 1993. Tahun 2001 memperoleh gelar M.T. dari Teknik Informatika ITS Surabaya. Saat ini sebagai staf pengajar tetap Teknik Informatika UK Petra, Surabaya.
Ibnu Gunawan, memperoleh gelar S.T. dari Teknik Elektro UK Petra Surabaya tahun 2002. Saat ini sebagai staf pengajar tetap Teknik Informatika UK Petra, Surabaya.
Ferry Yuwono, memperoleh gelar S.Kom dari Teknik Informatika UK Petra Surabaya tahun 2005. Saat ini sebagai staf di departemen IT sebuah perusahaan di Surabaya.