METODE CLASS FEATURE CENTROID CLASSIFIER UNTUK MENGKLASIFIKASI DATA TEKS ARAB YANG TIDAK SEIMBANG

Prosiding Seminar Nasional Manajemen Teknologi XVI Program Studi MMT-ITS, Surabaya 14 Juli 2012

METODE CLASS FEATURE CENTROID CLASSIFIER UNTUK MENGKLASIFIKASI DATA TEKS ARAB YANG TIDAK SEIMBANG Indriati1), Agus Zainal Arifin2) dan Anny Yuniarti3) Jurusan Teknik Informatika, Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember Kampus ITS Keputih – Sukolilo, Surabaya 60111 [email protected] , [email protected], [email protected] ABSTRAK Banyaknya informasi digital tidak terstruktur yang salah satunya berbentuk teks Arab membutuhkan klasifikasi teks secara otomatis. Banyak penelitian di bidang klasifikasi teks Arab tersebut menggunakan dataset yang dibuat sendiri sehingga kualitasnya tidak dapat ditentukan dan adanya data yang tidak seimbang. Dalam penelitian ini diusulkan sebuah metode untuk klasifikasi teks menggunakan metode Class Feature Centroid (CFC) dengan menambahkan Imbalanced Factor (IF) pada bobot termnya. Metode ini digunakan untuk data yang tidak seimbang pada kelas biner dengan dokumen berteks Arab. Pada tahap training dokumen-dokumen teks Arab mengalami tahap preprocessing hingga menghasilkan termterm. Term-term tersebut akan diberi bobot dengan metode CFC dengan menambahkan IF sehingga membentuk centroid dari masing-masing kelas. Centroid tersebut akan digunakan pada tahap testing, dokumen dengan similarity terbesar terhadap suatu centroid di suatu kelas akan menjadi anggota kelas tersebut. Pada percobaan menunjukkan hasil klasifikasi terbaik yang dapat dicapai dengan menggunakan metode ini yaitu mempunyai nilai F Measure sebesar 0.97. Hasil percobaan tersebut menunjukkan bahwa metode CFC dengan menambahkan IF dapat mengatasi klasifikasi data teks Arab yang tidak seimbang. Kata kunci: klasifikasi teks, Class Feature Centroid, Imbalanced Factor

PENDAHULUAN Peningkatan arus informasi di dunia internet berlangsung sangat cepat. Kecenderungan peningkatan tersebut menyebabkan banyaknya informasi digital yang tidak terstruktur. Salah satu dari informasi digital yang tidak terstruktur tersebut yaitu informasi berbentuk teks Arab yang dapat ditemukan pada berbagai web online berbahasa Arab. Pertumbuhan informasi yang menggunakan teks Arab yang begitu cepat tersebut memotivasi peneliti untuk menemukan beberapa tool yang dapat membantu untuk mengelola informasi tersebut dengan lebih baik, menyaring serta mengklasifikasikan informasi tersebut (Mesleh, 2007). Klasifikasi teks adalah suatu proses untuk mengklasifikasikan teks ke salah satu kelas atau kelas yang telah ditentukan sebelumnya berdasarkan kesamaan isinya. Banyak metode yang telah digunakan untuk klasifikasi teks Arab antara lain Support Vector Machine (Mesleh 2007), N-Gram Frequency Statistics (Khreisat, 2006), Naive bayes, K-nearest-neighbour, Distance based Classifier (Duwairi, 2007), menggunakan Maximum Entropy (Halees, 2007). Banyak penelitian di bidang klasifikasi teks Arab tersebut menggunakan dataset yang dibuat sendiri dengan mengambil artikel dari koran, majalah, jurnal atau berita online. Dataset teks Arab tersebut biasanya kecil dan dikumpulkan secara manual sehingga tidak dapat ditentukan kualitas dan keseimbangannya (Goweder, 2001). Penggunaan dataset teks Arab yang tidak seimbang sebagai data training akan mempengaruhi hasil akhir dari pengklasifikasi teks tersebut dikarenakan jumlah training data pada kelas minoritas sedikit ISBN : 978-602-97491-5-1 C-17-1


sehingga sedikit term juga yang dapat mewakili kelas tersebut. Training data menunjukkan distribusi kelas yang tidak seimbang apabila jumlah kelas yang satu berbeda jauh dengan jumlah kelas yang lain (Cabrera, 2007). Ketidakseimbangan training data pada klasifikasi teks Arab ini akan terlihat jelas pada kelas biner karena pada kelas biner apabila jumlah training data kelas positif jauh lebih kecil dari jumlah training data kelas negatif maka kelas yang positif menjadi kelas minoritas dan kelas negatif adalah mayoritas (Chen, 2011). Training data akan menjadi kelas positif apabila sesuai dengan satu kelas yang jumlah dokumennya kecil sedangkan training data yang jumlah dokumennya banyak akan menjadi kelas negatif. Ada beberapa jenis strategi untuk memecahkan masalah dataset tidak seimbang antara lain re-sampling, cost sensitive learning, menyesuaikan algoritma untuk bias rare class, perbaikan bobot term atau pendekatan fitur seleksi. Strategi perbaikan bobot term selain untuk memecahkan dataset tidak seimbang juga sesuai digunakan untuk kelas biner. Telah dilakukan penelitian perbaikan bobot TFIDF term dengan nama Improved TFIDF (I_TFIDF) (Xu, 2011). Pada penelitian ini nilai TFIDF dibagi dengan Imbalanced Factor yaitu nilai yang merefleksikan ketidakseimbangan kemunculan dari term di dua kelas. Hasil pembobotan dengan I_TFIDF ini menghasilkan performa yang lebih baik daripada TFIDF. Pada masalah pengklasifikasian teks Arab, salah satu metode supervised learning yang sering digunakan yaitu klasifikasi berbasis centroid (Broder, 2007). Ide dasarnya adalah untuk membangun sebuah vektor prototipe atau centroid pada setiap kelas menggunakan training set dokumen (Tan, 2008). Metode tersebut mempunyai kelebihan pada pendeknya waktu training dan testing dikarenakan efisiensi algoritmanya. Tetapi klasifikasi berbasis centroid kinerjanya akan menjadi kurang baik dikarenakan centroid tidak memiliki nilai yang baik. Untuk mengatasi masalah ini, banyak metode menggunakan feedback loop untuk menyesuaikan vektor prototipe centroid secara iteratif. Metode-metode yang digunakan antara lain metode Dragpushing (Tan, 2007a), metode Hypothesis Margin (Tan, 2007b), metode Weight Adjustment (Shankar, 2000) dan metode Class Feature Centroid (CFC) (Guan, 2009). Metode CFC mempunyai kelebihan karena metode tersebut menggunakan intra-class dan inter-class distribusi term sehingga meningkatkan bobot term yang sangat diskriminatif selama pelatihan. Setiap term mempunyai bobot sesuai dengan frekuensi dokumennya (informasi intra class) dan faktor diskriminatif kelas yang berbanding terbalik dengan jumlah kelas yang berisi term tersebut (informasi inter class). Keduanya dapat memproses corpus secara efisien dengan waktu yang linear dan secara iteratif terupdate. Tetapi metode CFC mempunyai kelemahan yaitu performanya tidak optimal untuk kelas biner dan data nya tidak seimbang karena agresifitas menghilangkan term yang tidak diskriminatif yaitu term yang muncul dalam kedua kelas dengan tidak menghitung jumlah term yang sebenarnya. Oleh karena itu, dalam penelitian ini diusulkan sebuah metode baru untuk klasifikasi teks dengan CFC dengan menambahkan Imbalanced Factor pada bobot termnya. METODE Metode Class Feature Centroid dengan Imbalance Factor (CFCIF) yaitu metode klasifikasi dokumen dengan menggunakan CFC dan IF untuk menghitung bobot term dari centroid masing-masing kelas. Metode ini membutuhkan dua tahapan proses untuk melakukan klasifikasi dokumen yaitu tahap training dan tahap testing. Tahap training digunakan untuk membentuk centroid dengan pembobotannya menggunakan CFC dan IF. Gambar 1 menggambarkan urutan proses yang dilakukan pada tahap training untuk metode klasifikasi dokumen CFCIF.

ISBN : 978-602-97491-5-1 C-17-2


Gambar 1. Urutan proses pada tahap training metode klasifikasi dokumen CFCIF

Sebelum dilakukan tahap preprocessing dan indexing seluruh dokumen training telah tersimpan dalam database dan telah di encode terlebih dahulu menggunakan UTF-8. Proses penyimpanan dokumen training ke dalam database dilakukan dengan melakukan perulangan pembacaan file dokumen teks yang memiliki ekstensi text (.txt) dalam satu folder yang sesuai dengan nama kelasnya. Dokumen-dokumen training tersebut akan di load dari database untuk dilakukan preprocessing dengan menggunakan class ArabicAnalyzer pada library Lucene 3.4. Analyzer ini melakukan proses pemisahan rangkaian kata (tokenization), normalization and filtration dari token, menghilangkan stopword serta mengaplikasikan light stemming. Apabila ada sebuah dokumen teks Arab !!‫وھﺬا ﯾﻘﻮدﻧﺎ اﻟﻰ ﺳﺆال ﻣﮭﻢ‬: mengalami proses tokenization untuk memisahkan rangkaian kata dan membuang tanda baca maka akan terbentuk term-term yaitu ‫وھﺬا – ﯾﻘﻮدﻧﺎ – اﻟﻰ – ﺳﺆال – ﻣﮭﻢ‬. Setelah itu akan dilakukan proses normalization dan filtration untuk menghilangkan harokat, tetapi karena dokumen yang digunakan tidak menggunakan harokat maka hasilnya akan sama yaitu ‫ وھﺬا – ﯾﻘﻮدﻧﺎ – اﻟﻰ – ﺳﺆال – ﻣﮭﻢ‬. Term-term yang telah terbentuk akan mengalami proses stopword removal yaitu menghilangkan kata-kata yang termasuk stopword sehingga akan menyisakan ‫ وھﺬا – ﯾﻘﻮدﻧﺎ – ﺳﺆال – ﻣﮭﻢ‬karena term ‫ اﻟﻰ‬termasuk dalam daftar stopword. Pada tahap akhir preprocessing term-term yang tersisa akan mengalami proses stemming yaitu proses untuk merubah ke dalam bentuk kata dasar sehingga akan terbentuk term-term yaitu ‫ ﻣﮭم‬-‫ ﺳؤال‬-‫ھذا – ﯾﻘودﻧﺎ‬. Hasil dari preprocessing akan menjadi masukan pada proses indexing. Proses indexing juga menggunakan class IndexWriterConfig yang ada pada library Lucene. Setelah itu akan dilakukan pembobotan term dengan membaca index yang telah dibuat dari data training kemudian membuat matriks untuk masing-masing kelas yang dimensinya m x n dimana m adalah adalah jumlah term dan n adalah jumlah dokumen dan isi matriksnya yaitu nilai term frekuensi masing-masing term dalam dokumen. Bobot untuk setiap term tersebut dihitung dengan rumus CFCIF (Class Feature Centroid dengan Imbalance Factor) yaitu DFt j i

wij  b

cj

 C  log  CFt i 

 1     IF 

,

ISBN : 978-602-97491-5-1 C-17-3

(1)


j

dimana DFti adalah frekuensi dokumen term ti di kelas Cj, |Cj| adalah jumlah dokumen di kelas Cj, |C| adalah total jumlah kelas dokumen, CFti adalah jumlah kelas yang mengandung term ti dan b adalah konstanta .IF adalah Imbalanced Factor dan λ adalah koordinator parameter distribusi kelas. Rumus IF adalah sebagai berikut: ( ∗

( )=

( ∗

. ( ) ∗

( ) , ( ) ,

( ) ) ( ) )

jika DF(ti)+ ≠0 dan DF(ti)- ≠0.

jika DF(ti)+ =0.

. ( )

,

(2)

jika DF(ti)- =0.

dimana DF(ti)+ adalah jumlah dokumen yang didalamnya mengandung term ti di kelas positif/minoritas dan DF(ti)- adalah jumlah dokumen yang didalamnya mengandung term ti di kelas negatif/mayoritas. Lambang λ adalah koordinator parameter distribusi kelas dan digunakan untuk memberi kekuatan pada bobot term di kelas positif/minoritas.Setelah pembobotan term tersebut dilakukan akan terbentuklah centroid untuk masing-masing kelas. Centroid untuk kelas Cj adalah vektor term Centroidj = (w1j, w2j, ..., w|F|j), dimana wkj (1 ≤ k ≤ |F|) merepresentasikan bobot dari term tk. Proses testing akan dilakukan setelah proses training menghasilkan nilai centroid untuk masing-masing kelas. Gambar 2 menggambarkan urutan proses testing untuk melakukan klasifikasi dokumen. Langkah pertama yaitu membaca dokumen testing satupersatu dari folder testing untuk kemudian dilakukan tahap preprocessing yang sama dengan dokumen training dengan menggunakan ArabicAnalyzer. Setelah itu akan melakukan perhitungan similarity antara dokumen testing dengan centroid masing-masing kelas dengan menggunakan cosine similarity. Apabila setiap dokumen testing telah dihitung similarity nya akan ditampilkan hasil klasifikasi dari dokumen testing berdasarkan similarity terbesar terhadap salah satu centroid.

ISBN : 978-602-97491-5-1 C-17-4


Gambar 2. Urutan proses tahap testing metode klasifikasi dokumen CFCIF

HASIL DAN PEMBAHASAN Tahap uji coba menggunakan dataset yang terdiri dari 2400 dokumen yang terbagi menjadi 8 kelas yaitu kelas arts, culture, economy, international, locals, medical, sport, society. Masing-masing kelas mempunyai 300 dokumen dengan perbandingan data training dan testing yaitu 2:1. Uji coba dilakukan dengan mengganti variasi nilai parameter b dan λ. Selain itu dilakukan perbandingan rasio jumlah dokumen untuk kombinasi 2 kelas untuk mendapatkan nilai λ yang optimal agar hasil klasifikasi dokumen menjadi baik dengan F Measure yang tinggi. 1.2 1 0.8

b=e-1.8

0.6

b=e-1.3

0.4

b=e-0.8

0.2

b=e

0 1

2

3

4

5

6

7

8

9

10

Gambar 3. Nilai F-Measure pada klasifikasi kelas biner Medical dan Sport untuk variasi nilai b

ISBN : 978-602-97491-5-1 C-17-5


Percobaan merubah nilai parameter b menghasilkan grafik seperti pada Gambar 3 yang menunjukkan bahwa nilai b kurang berpengaruh terhadap nilai F Measure hasil klasifikasi dengan menggunakan metode CFCIF. Setelah itu dilakukan percobaan dengan merubah variasi nilai λ pada kombinasi kelas biner dari 8 kelas mulai dari 1 hingga 10. Pada Tabel 1 akan terlihat beberapa nilai λ mayoritas yang dapat digunakan untuk menghasilkan klasifikasi yang mempunyai nilai F Measure tinggi. Tabel 1. Hasil uji coba dengan mengkombinasi klasifikasi untuk dua kelas pada dataset

A B Arts Culture Economy International Locals Medical Society Sport Arts 5 4 5 5 4 4 5 Culture 3 4 4 4 5 3 3 Economy 4 5 4 5 5 4 4 International 3 5 5 5 3 3 2 Locals 3 5 3 4 5 4 3 Medical 4 5 3 5 5 4 5 Society 3 6 4 4 4 5 6 Sport 4 6 4 4 4 5 4 -

1

1

0.8

0.8

0.6

F Measure

F Measure

Percobaan dengan merubah variasi λ ini akan menghasilkan nilai λ bervariasi antara 2, 3, 4, 5 atau 6 untuk mendapatkan hasil klasifikasi yang baik. Hal ini dikarenakan bedanya kedekatan antara dua kelas yang dibandingkan. Berdasarkan mayoritas λ yang digunakan dari percobaan , hasil klasifikasi yang baik didapatkan jika menggunakan nilai λ=3, λ=4 atau λ=5. Percobaan selanjutnya yaitu menggunakan rasio jumlah dokumen pada kelas biner dengan menggunakan kombinasi 8 kelas yang ada pada dataset. Rasio jumlah dokumen yang digunakan yaitu 1:5, 1:10 dan 1:20.

1:5

0.4

1:10

0.2

1:20

0

0.6

1:5

0.4

1:10

0.2

1:20

0

1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10

λ

λ

Gambar 4. Nilai F Measure kelas Medical dan Art

Gambar 5. Nilai F Measure kelas Medical dan Culture

ISBN : 978-602-97491-5-1 C-17-6

1

0.8

0.8

0.6

1:5

0.4

1:10

0.2

1:20

0

0.6

1:5

0.4

1:10

0.2

1:20

0

1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10

λ

λ

Gambar 6. Nilai F Measure kelas Medical dan Economy

F Measure

F Measure

1

Gambar 7. Nilai F Measure kelas Medical dan International

1

1

0.8

0.8

0.6

F Measure

F Measure


1:5

0.4

1:10

0.2

1:20

0

0.6

1:5

0.4

1:10

0.2

1:20

0

1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10

λ

λ

Gambar 8. Nilai F Measure kelas Medical dan Locals

Gambar 9. Nilai F Measure kelas Medical dan Sport

F Measure

1 0.8 0.6

1:5

0.4

1:10

0.2

1:20

0 1 2 3 4 5 6 7 8 9 10 λ

Gambar 10. Nilai F Measure kelas Medical dan Society

Percobaan dilakukan dengan menggunakan variasi parameter λ untuk mengklasifikasi 2 kelas biner dengan mengkombinasi 8 kelas pada dataset. Variasi parameter yang digunakan yaitu mulai λ=1 sampai dengan λ=10. Hasil dari percobaan tersebut dapat dilihat dari Gambar 4 sampai dengan Gambar 10. Grafik pada Gambar 10 menunjukkan nilai F Measure yang lebih rendah dibandingkan yang lain dikarenakan dokumen-dokumen dalam kelas Medical dan Society mempunyai topik yang hampir sama. KESIMPULAN DAN SARAN Metode CFC ditambahkan Imbalanced Factor dapat digunakan untuk mengklasifikasikan data teks Arab yang tidak seimbang pada kelas biner dengan F Measure terbaik yang didapatkan yaitu 0.97. Penentuan nilai parameter λ pada metode CFCIF ISBN : 978-602-97491-5-1 C-17-7


bergantung pada kedekatan antara dua kelas yang digunakan untuk membentuk centroid. Sedangkan parameter b pada metode CFCIF tidak begitu berpengaruh terhadap hasil klasifikasi. Metode CFCIF ini dapat digunakan untuk mengklasifikasi dokumen dengan rasio jumlah dokumen 1:5 ,1:10 dan 1:20 Untuk penelitian selanjutnya, dapat menerapkan metode CFCIF dengan dataset yang multilabel karena metode CFCIF ini menghasilkan klasifikasi yang baik apabila kelas yang dibandingkan isi dari dokumennya mempunyai topik yang jauh berbeda. DAFTAR PUSTAKA Azmi A,M, Thanyyan S,A. (2012). A text summarizer for Arabic. Elsevier Ltd. Chen C, Shyu ML. (2011). Clustering-based Binary-class Classification for Imbalanced Data Sets. IEEE in Information Reuse and Integration (IRI). Duwairi R. (2007). Arabic Text Categorization. The International Arab Journal of Information Technology Vol 4 No 2. Goweder A, Roeck A D. (2001). Assessment of a Significant Arabic Corpus. Arabic NLP Workshop at ACL/EACL. Guan H., Zhou J.,Guo M. (2009). A Class Feature Centroid Classifier for Text Categorization. in 18th International World Wide Web Conference,page 201-201,April 2009 Halees A E. (2007).Arabic text classification using maximum entropy. The Islamic University Journal (Series of Natural Studies and Engineering)15 (1) 157–167. Hayder K. Al Ameed, Shaikha O. Al Ketbi, Amna A. Al Kaabi, Khadija S. Al Shebli, Naila F. Al Shamsi, Noura H. Al Nuaimi, Shaikha S. Al Muhairi. (2005). Arabic Light Stemmer: Anew Enhanced Approach. The Second International Conference on Innovations in Information Technology. Khreisat L. (2006). Arabic text classification using N-Gram frequency statistics. A comparative study. in: Proceedings of the international conference on data mining (DMIN), Nevada, USA, pp. 78–82. Mesleh, Abdelwadood Moh’d. (2007). Support Vector Machines based Arabic Languange Text Classification System:Feature Selection Comparative study. 12th WSEAS Int Conf. on APPLIED MATHEMATICS,Cairo. Shankar S. dan Karypis G .(2000). Weight Adjustment Schemes for a Centroid Based Classifier. Army High Performance Computing Research Center. Tan,S .(2007a). Large margin DragPushing Strategy for Centroid Text Categorization. Expert Systems with Applications, 33(1):215–220, 2007. Tan.S .(2007b). Using hypothesis margin to boost centroid text classifier. In Proceedings of the 2007 ACM Symposium on Applied Computing, pages 398–403,Seoul, Korea, 2007. Tan.S (2008). An improved centroid classifier for text categorization. Elseiver Ltd Expert Systems with Applications, 35(1-2):279–285, 2008.

ISBN : 978-602-97491-5-1 C-17-8


Xu G, Gao X, Zhang X,Zhao X .(2011). Improved TFIDF weighting for imbalanced biomedical text classification. In proceeding Elsevier Ltd. International Conference on Energy and Environmental Science.

ISBN : 978-602-97491-5-1 C-17-9

METODE CLASS FEATURE CENTROID CLASSIFIER UNTUK MENGKLASIFIKASI DATA TEKS ARAB YANG TIDAK SEIMBANG

Recommend Documents