INVERSE CLASS FREQUENCY DAN NAÏVE BAYES PADA KLASIFIKASI DUAL STAGE PADA DOKUMEN BERBAHASA ARAB Dika R. Yunianto
Septyawan R. Wardhana
Rizka W. Sholikah
Jurusan Informatika Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember Surabaya, Indonesia
Jurusan Informatika Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember Surabaya, Indonesia
Jurusan Informatika Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember Surabaya, Indonesia
[email protected]
[email protected]
[email protected]
Abstrak Klasifikasi dokumen menjadi fokus penelitian beberapa dekade terakhir. Berbagai macam metode untuk membuat sistem klasifikasi secara otomatis telah dikembangkan. Klasifikasi dokumen pada bahasa Arab memiliki kesulitan tersendiri, dikarenakan bahasa Arab memiliki morfologi yang unik dengan kompleks. Pada beberapa dokumen bahasa Arab terdapat hirarki kelas yang menunjukan kelas dan sub-kelas dimana dokumen tersebut berada. Klasifikasi dual stage dapat menjadi solusi untuk menyelesaikan masalah klasifikasi pada dokumen yang memiliki hirarki kelas. Untuk melakukan klasifikasi dual stage perlu diperhatikan hubungan kata suatu dokumen terhadap kelas untuk menemukan ciri khas suatu kelas. Penelitian ini mengusulkan sebuah metode klasifikasi yang mempertimbangkan keterkaitan antara kata dengan kelas dan sub-kelas pada klasifikasi dual stage untuk dokumen berbahasa Arab. Metode ini akan dibangun dengan menggunakan class frequency dalam penentuan kelas, kemudian menggunakan chi-square sebagai seleksi fitur untuk mereduksi dimensi dan Naïve Bayes classifier untuk melakukan prediksi pada bagian sub-kelas. Hasil pengujian menunjukan bahwa metode usulan dapat diaplikasikan dalam klasifikasi dual stage dengan nilai rata-rata akurasi pada stage pertama sebesar 80,54% dan stage kedua sebesar 66,67%.
1
Pendahuluan
Perkembangan jumlah dokumen digital yang semakin hari kian pesat, membuat klasifikasi dokumen menjadi fokus penelitian
beberapa dekade terakhir. Dengan jumlah data yang demikian besar klasifikasi dokumen secara manual dirasa kurang efektif ditinjau dari segi waktu dan biaya. Selain itu dibutuhkan seorang ahli untuk dapat mengelompokan dokumen dengan benar. Permasalahan tersebut mengarahkan pada pengembangan sistem klasifikasi secara otomatis. Klasifikasi dokumen teks secara otomatis dibutuhkan dalam berbagai bidang seperti dokumen berita, perpustakaan digital dan teks pada website yang berjumlah besar (1). Beberapa metode telah dikembangkan untuk klasifikasi dokumen diantaranya dengan pendekatan statistika, pendekatan jarak, Bayesian, k- Nearest Neighbors dan decision tree serta beberapa metode lainnya (2). Pengembangan klasifikasi untuk dokumen berbahasa Arab dirasa masih memiliki kesulitan tersendiri mengingat struktur yang unik dan morfologi yang lebih kompleks Penelitian terkait mengenai klasifikasi untuk dokumen teks berbahasa Arab diantaranya telah dilakukan oleh Hadi (3). Pada penelitian tersebut dilakukan pembandingan metode Naïve Bayes dan kNearest Neighbour untuk klasifikasi dokumen berbahasa Arab. Hasilnya menunjukan bahwa metode Naïve Bayes lebih unggul jika dibandingkan dengan metode k-Nearest Neighbour. Fadi pada penelitiannya melakukan klasifikasi dokumen berbahasa Arab menggunakan Naïve Bayes dan Chi Square sebagai seleksi fitur. Dari penelitian menunjukan bahwa penggunaan seleksi fitur mempengaruhi tingkat akurasi dari klasifikasi yang dilakukan dengan metode Naïve Bayes (4). Aymen, dalam penelitiannya melakukan pengkategorian pada dokumen berita berbahasa Arab yang memiliki susunan hirarki, yaitu kategori yang di dalamnya terdapat beberapa sub-kategori. Pengkategorian
ini disebut dengan dual stage categorization. Untuk melakukan kategorisasi peneliti menggunakan metode pembobotan term atau kata TF.IDF (Term Frequency and Inverse Document Frequency) pada kategori utama dan Chi-Square pada sub-kategori (5). Pada penelitian tersebut dibuktikan bahwa metode pembobotan term dapat dijadikan untuk klasifikasi dokumen. Beberapa dokumen dapat diklasifikasi dalam bentuk hirarki atau dual stage, dimana terdapat kelas pada stage pertama dan sub-kelas pada stage kedua. Metode klasifikasi pada dual stage ini perlu memperhatikan kemunculan kata dalam kelas untuk menemukan ciri khas suatu kelas. Pada paper ini diusulkan sebuah metode klasifikasi baru yang mempertimbangkan relasi antara kata dengan kelas dan sub-kelas untuk klasifikasi dual stage pada dokumen berbahasa Arab. Metode usulan akan menggunakan Inverse Class Frequency (ICF) dan Naïve Bayes classifier untuk menentukan kelas pada stage pertama dan sub-kelas pada stage kedua dari suatu dokumen. Metode ICF memperhatikan hubungan kata atau term pada suatu kelas dengan melihat frekuensi kemunculan kata tersebut pada suatu kelas (6). yang dapat dijadikan parameter untuk mengetahui representatif suatu kata terhadap kelas tersebut. Hal ini akan berpengaruh pada penentuan klasifikasi untuk stage selanjutnya atau klasifikasi pada sub-kelas. Diharapkan metode ini dapat meningkatkan akurasi dalam melakukan pengklasifikasian untuk kasus klasifikasi dual stage dokumen berbahasa Arab.
2
untuk melakukan klasifikasi stage pertama pada dokumen testing. TABEL 1. KELAS DUAL STAGE Kelas
Sub-Kelas
(Stage 1)
(Stage 2) Haji
Ibadah
Puasa Sholat Zakat Jual beli
Perekonomian
Pinjaman Simpanan Warisan Halal-haram
Sosial
Jenazah Perceraian Pernikahan
Untuk mengurangi besar dimensi term maka dilakukan seleksi fitur menggunakan metode Chi-Square measurements. Dari hasil featseleksi fitur pada term, term yang tersisa dihitung probabilitasnya terhadap sub-kelas. Nilai probabilitas tersebut akan dikalikan dengan probabiitas term lain pada perhitungan naïve bayes. Document Training
Document Testing
Preprocessing
Preprocessing
TF -ICF
Classification Stage 1 (TF.ICF)
Metodologi
Data yang digunakan dalam penelitian ini merupakan dokumen teks berbahasa Arab yang diambil dari Maktabah Syamilah dan Pustaka Ilmu Sunni Salafiyah. Terdapat 3 kelas pada stage pertama dan 4 sub-kelas pada setiap kelas. Pembagian kelas dan sub-kelas dapat dilihat pada Tabel 1. Metode yang diusulkan merupakan metode yang memeperhatikan kemunculan kata atau term pada suatu kelas. TF (Term Frequency) dan ICF (Inverse Class Frequency) digunakan sebagai metode untuk klasifikasi pada stage pertama. Dokumen training yang telah dipreprocessing menghasilkan kumpulan term yang dihitung nilai TF dan ICF pada setiap term tersebut. Nilai TF-ICF tersebut akan digunakan
Feature Selection (Chi Square Measurement)
Naïve Bayes Model
Classification Stage 2 (Naïve Bayes) Output (Class & sub-Class)
Gambar 1. Tahapan metode.
2.1. Preprocessing Dokumen teks berbahasa Arab pada dataset terlebih dahulu akan melalui tahapan
preprocessing. Pada tahap ini yang pertama dilakukan adalah tokenisasi. Tokenisasi merupakan metode yang digunakan untuk menghilangkan spasi, simbol, dan tanda baca yang ada pada dokumen. . Langkah selanjutnya dalam tahap ini adalah melakukan stopword removal dengan menghilangkan kata yang tidak memiliki nilai informasi. Setelah didapatkan kata dari hasil stopword removal, kemudian setiap kata dilakukan normalisasi stopword. Normalisasi dalam bahasa arab penting untuk dilakukan, mengingat terdapat banyak variasi penulisan untuk sebuah kata yang sama. Normalisasi dilakukan dengan merubah ﺃ, ﺇ, ﺁ, kedalam alif ()ﺍ, merubah ta marbutoh ( ) ﺓ menjadi ha ( ) ﻩ, merubah ya ( ) ﻯmenjadi ya ( ﻱ ) (7). Setelah normalisasi selesai kemudian dilakukan stemming untuk mendapatkan kata dasar dari setiap kata. Stemmer yang digunakan untuk melakukan stemming pada penelitian ini merupakan stemming dari Khoja (8). Tahapan preprocessing ini akan diterapkan baik untuk data training maupun data testing. 2.2. Klasifikasi kelas Klasifikasi dokumen pada kelas dilakukan dengan menggunakan metode TF.ICF. TF merupakan pembobotan pada kata dengan menghitung frekuensi kemunculan kata ti pada suatu dokumen dj. Perhitungan pembobotan dapat dilakukan dengan melihat persamaan (1). 𝑊𝑇𝐹 (𝑡𝑖 , 𝑑𝑗 ) = 𝑓(𝑡𝑖 , 𝑑𝑗 )
(1)
ICF memiliki dasar perhitungan memperhatikan kemunculan kata ti pada sekumpulan kelas. Semakin banyak kelas c yang mengandung kata ti, maka akan semakin rendah nilai kata tersebut. Hal tersebut terjadi karena kata ti dianggap tidak dapat merepresentasikan sautu kelas tertentu. Perhitungan ICF dapat dilakukan dengan menggunakan persamaan (2) (6). 𝑁𝑐 ) 𝑁𝑐(𝑡𝑖)
𝑊𝐼𝐶𝐹 (𝑡𝑖) = 1 + log (
(2)
Pada persamaan (2) Nc merupakan jumlah keseluruhan kelas dalam koleksi dan Nc(ti) menunjukan jumlah kelas yang mengandung kata ti. Perhitungan bobot TF.ICF dilakukan dengan
melakukan perkalian antara persamaan (1), dan (2) sehingga meghasilkan persamaan (3). Oleh 𝑊 (𝑡𝑖 , 𝑑𝑗 ) = 𝑊𝑇𝐹 (𝑡𝑖 , 𝑑𝑗 ) × 𝑊𝐼𝐶𝐹 (𝑡𝑖 , 𝑑𝑗 ) (3) Setelah mendapatkan bobot dari setiap kata pada setiap kelasnya, selanjutnya bobot tersebut dijumlahkan. Nilai hasil penjumlahan bobot tertinggi pada setiap kelasnya merupakan kelas untuk dokumen testing tersebut. 2.3. Chi-Square feature selection Setelah didapatkan kelas yang sesuai, selanjutnya akan dilakukan seleksi fitur pada kelas tersebut untuk mengurangi dimensi pada penentuan sub-kelas. Pada tahapan ini digunakan metode chi-square. Chi-square dipilih karena dapat melihat keterkaitan antara suatu kata ti dengan sub-class s. Dalam sebuah kelas yang terdiri dari N dokumen. A merupakan jumlah dokumen pada s yang mengandung kata ti. B merupakan jumlah dokumen pada s yang tidak mengandung kata ti. C menunjukan jumlah dokumen yang bukan pada sub-kelas s yang mengandung kata ti. Sedangkan D adalah jumlah dokumen yang tidak terletak pada s dan tidak memiliki kata ti. Sehingga untuk menghitung bobot setiap kata dengan metode Chi-Square dapat dilakukan dengan menggunakan persamaan (4) 𝜒 2 (𝑡𝑖, 𝑠𝑖) =
𝑁 ×(𝐴𝐷−𝐶𝐵)2 (𝐴+𝐶)×(𝐵+𝐷)×(𝐴+𝐵)×(𝐶+𝐷)
(4)
Setelah didapatkan bobot untuk setiap kata, selanjutnya akan dipilih N kata berdasarkan bobot tertinggi untuk setiap sub-kelas. 2.4. Naïve Bayes classifier Naive Bayes (NB) classifier merupakan metode machine learning yang didasarkan pada teorema Bayes. NB menghitung probabilitas dari setiap kata terhadap sub-kelas. Metode ini merupakan jenis supervised yang mana prediksi pada data testing didasarkan pada model yang telah dibuat berdasarkan data training. Dari N kata yang didapat dari tahapan sebelumnya, selanjutnya akan dihitung probabilitasnya terhadap sub-kelas Si dengan menggunakan NB sesuai persamaan (5). 𝑃(𝑆𝑖|𝑡) =
𝑃(𝑡|𝑆𝑖)𝑃(𝑆𝑖) 𝑃(𝑡)
(5)
Karena nilai P(t) akan sama untuk semua kata maka P(t) dapat dihilangkan, sehingga NB dapat dihitug dengan persamaan (6). 𝑃(𝑆𝑖|𝑡) = 𝑃(𝑡|𝑆𝑖)𝑃(𝑆𝑖)
(6)
Jika N merupakan jumlah kata pada dokumen testing, maka penentuan sub-kelas dari dokumen testing dapat dilakukan dengan menggunakan persamaan (7).
iliki banyak term-term ciri khas dari kelas tersebut. TABEL 4. AKURASI STAGE KEDUA
Kelas
Ibadah
𝑉𝑁𝐵 = 𝑎𝑟𝑔𝑚𝑎𝑥𝑆𝑖𝜖𝑆 𝑃(𝑆𝑖) ∏𝑁 𝑗=1 𝑃(𝑡𝑗|𝑆𝑖) (7) Perekonomian
Hasil akhir dari metode ini merupakan output yang menunjukan kelas dan sub-kelas dari dokumen testing.
3.
Sosial
Hasil dan Pembahasan TABEL 2. CONFUSION MATRIKS
Relevan Ditampilkan Tidak ditampilkan
Rata-rata Tidak relevan
TP
FP
TN
FN
Pengujian pada penelitian ini menggunakan evaluasi yang umum digunakan dalam Information Retrieval (IR). Berdasarkan Tabel 2 penghitungan akurasi dilakukan dengan merujuk pada persamaan (8). 𝐴𝑘𝑢𝑟𝑎𝑠𝑖 =
𝑡𝑝+𝑡𝑛 𝑡𝑝+𝑓𝑝+𝑓𝑛+𝑡𝑛
(8)
TABEL 3. AKURASI STAGE PERTAMA
Class
Akurasi(%)
Ibadah
83,33
Perekonomian
100
Sosial
58,33
Rata-rata
80,54
Pada klasifikasi di stage pertama perlu diperhatikan persebaran term-term di setiap kelas dan juga persebaran term-term yang merupakan ciriciri dari kelas tersebut. Hal ini dapat dilakukan dengan pemilihan dokumen training yang mem-
Sub-Kelas
Akurasi (%)
Haji
0
Puasa
100
Sholat
100
Zakat
100
Jual beli
66,67
Pinjaman
33,33
Simpanan
100
Warisan
100
Halal-haram
66,67
Jenazah
0
Perceraian
66,67
Pernikahan
66,67 66,67
Akurasi pada klasifikasi di stage kedua lebih kecil dibandingkan dengan akurasi pada stage pertama. Hal ini dikarenakan term-term pada stage kedua memiliki similaritas yang cukup tinggi antar sub-kelasnya dibandingkan dengan antar kelas pada stage pertama. Penelitian yang terkait, menggunakan pembobotan term TF-IDF untuk melakukan klasifikasi menghasilkan nilai akurasi tertinggi sebesar 98,93% (5). TF-ICF pada klasifikasi di stage pertama mampu memperhatikan hubungan term pada suatu kelas dilihat dari Tabel 3 dimana akurasi tertinggi pada pengujian sebesar 100%. Hal tersebut juga didukung dengan faktor term-term yang terdapat pada data training merupakan term ciri khas dari kelas tersebut. Metode naïve bayes pada klasifikasi stage kedua memperhatikan probabilitas term pada sub-kelas dimana term-term tersebut dianggap variabel yang bebas atau tidak mempengaruhi term lain. Adanya akurasi 0% pada sub-kelas Haji di Tabel 4 juga dapat dikarenakan term pada sub kelas haji memiliki similaritas yang tinggi dengan sub-kelas yang lain dalam kelas yang sama. Hal tersebut dapat dijadikan pekerjaan untuk kedepannya, dengan memperhatikan similaritas antar term pada klasifikasi sub-kelas.
4.
Kesimpulan
Metode TF.ICF dan Naïve Bayes classifier dengan Chi-square untuk seleksi fitur dapat diaplikasikan pada klasifikasi dual stage untuk dokumen berbahasa Arab. Metode TF.ICF pada klasifikasi stage pertama memiliki nilai akurasi yang lebih besar dibandingkan dengan metode TF.IDF dikarenkan metode tersebut memperhatikan hubungan term terhadap suatu kelas. Metode ini selain digunakan untuk dokumen berbahasa Arab juga memungkinkan untuk diterapkan pada dokumen teks dengan bahasa lain yang memiliki susunan hirarki kelas yang sama. Untuk kedepannya dalam klasifikasi dual stage perlu memperhatikan similaritas antar term pada klasifikasi stage kedua, dikarenakan similaritas term antar sub-kelas lebih tinggi dibandingkan similaritas term antar kelas.
Daftar Pustaka [1] Arabic Text Classification using Polynomial Networks. Al-Tahrawi, Mayy M. and AlKhatib, Sumaya N. Amman : Journal of King Saud University - Computer and Information Sciences, 2015. [2] Dunham, M. H. Chapter 4 classification. In Data Mining : Introduction in Advances Topics. s.l. : Prentice Hall, 2003. [3] Niave Bayesian and K-Nearest Neighbour to Categorize Arabic Text Data. Hadi, W, et al., et al. Le Havre, France : s.n., 2008. In Proceedings of the European Simulation and Modeling Conference. [4] Naive Bayes Based on Chi Square to Categorize Arabic Data. Thabtah, Fadi, et al., et al. 2009, Vol. 10. [5] Arabic Text Classification Algorithm using TFIDF and Chi Square Measurements. Abu-Errub, Aymen. 6, Amman : International Journal of Computer Applications (0975-8887), 2014, Vol. 93. [6] Term Weighting Berbasis Indeks Buku dan Kelas untuk Perangkingan Dokumen Berbahasa Arab. Fauzi, M. Ali, Arifin, Agus Zainal and Yuniarti, Anny. s.l. : Lontar Komputer, Universitas Udayana, 2015. [7] Arabic Information Retrieval at UMass in TREC10. Larkey, Leah S. and Connell, Margaret E.
[8] Stemming Arabic Text. Khoja, S and Garside, R. Lancaster : Computing Department, Lancaster University, 1999.
