BAB V EKSPERIMEN TEXT CLASSIFICATION Pada bab ini akan dibahas eksperimen untuk membandingkan akurasi hasil text classification dengan menggunakan algoritma Naïve Bayes dan SVM dengan berbagai pendekatan feature selection. Tujuan dilakukan eksperimen text classification ini adalah untuk menentukan algoritma dan pendekatan feature selection yang memberikan performansi maksimum dalam menyelesaikan permasalahan text classification.
5.1 Lingkungan Eksperimen Eksperimen dilakukan menggunakan perangkat-perangkat sebagai berikut: 1. Laptop dengan processor Intel Pentium M 1.83 GHz dan memory 1 GB DDR2. 2. Sistem operasi Windows XP. 3. Java Runtime Environment 5 4. Weka 3.5.3 5. SVMLight 6.01
5.2 Data Data set yang digunakan tahap pembelajaran terdiri dari dua sumber data sesuai dengan kelas targetnya. Untuk kelas target course dan project, data set yang digunakan adalah dokumen-dokumen web yang dikumpulkan dari situs departemen Computer Science Universitas Cornell, Universitas Washington, Universitas Texas, dan Universitas Wisconsin.
Data
set
tersebut
dapat
diakses
pada
situs
http://www.cs.cmu.edu/afs/cs.cmu.edu/project/theo-20/www/data/webkb-data.gtar.gz. Untuk kelas target co-author, data set yang digunakan adalah makalah-makalah ilmiah yang dikumpulkan dari situs http://citeseer.ist.psu.edu.
Jumlah total data set yang
digunakan dalam tahap pembelajaran adalah 400 dokumen, dengan perincian 244 dokumen memiliki kelas target course, 86 dokumen memiliki kelas target project, dan 70 dokumen memiliki kelas target co-author. Dari total data set tersebut, sebanyak 267 dokumen akan digunakan sebagai training set dan 133 dokumen digunakan sebagai test set. Dengan demikian perbandingan training set : test set sebesar 1:2 [MIT97].
V-1
V-2
Pada tahap klasifikasi, dokumen yang akan diklasifikasikan merupakan dokumendokumen web yang dihasilkan oleh query terhadap pasangan nama individu. Hal ini sesuai dengan fungsi GoogleTop(“X Y”,k) pada Algoritma II-5. Nilai k yang digunakan sebesar 10.
5.3 Prosedur Eksperimen Eksperimen text classification dilakukan dengan memanfaatkan dua buah algoritma klasifikasi, yaitu Naïve Bayes dan SVM. Algoritma Naïve Bayes disediakan oleh kakas Weka versi 3.5.3. Weka merupakan perangkat lunak pembelajaran mesin yang dibangun menggunakan bahasa pemrograman Java (http://www.cs.waikato.ac.nz/~ml/). Perangkat lunak ini mengimplementasikan banyak algoritma pembelajaran mesin dari berbagai macam paradigma. Sedangkan algoritma SVM disediakan oleh kakas SVMLight versi 6.01. SVMLight merupakan perangkat lunak berbasis teks yang mengimplementasikan teknik SVM dengan menggunakan bahasa pemrograman C (http://www.cs.cornell.edu/ People/tj/svm_light/ index.html).
Secara garis besar, eksperimen text classification dilakukan dengan langkah-langkah sebagai berikut: 1. Melakukan preprocessing pada data set, dengan langkah-langkah sebagai berikut: a. Membuang semua tag html yang terdapat dalam dokumen web. b. Membuang semua kata tidak penting dan baris kosong dalam dokumen web. Kata-kata tidak penting adalah kata-kata yang terdapat dalam daftar stopword atau merupakan bilangan. Daftar stopword diambil dari sistem text retrieval freeWAIS-sf dan dapat dilihat pada Lampiran D. c. Menerapkan stemming pada dokumen yang dihasilkan oleh langkah sebelumnya. Penggunaan stemming dimaksudkan untuk meningkatkan performansi [JOA04]. Stemming yang digunakan adalah Porter Stemming karena tidak memerlukan kamus dan memiliki waktu komputasi yang cepat. d. Membentuk representasi dokumen menjadi vektor kata, baik untuk dokumendokumen yang tidak dikenakan proses stemming (langkah 1.b) maupun untuk dokumen-dokumen yang telah dikenakan proses stemming (langkah 1.c). 2. Menerapkan
feature selection melalui pembentukan kelompok kata. Feature
selection dilakukan dengan menggunakan pendekatan term frequency, mutual information, dan term frequency-index document frequency. Ketika pendekatan
V-3
tersebut diterapkan baik pada dokumen yang dikenakan proses stemming, maupun dokumen yang tidak dikenakan proses stemming. 3. Membangun arsip masukan untuk kakas weka dan kakas SVMLight. 4. Membagi setiap dokumen menjadi training set dan test set secara acak. 5. Melakukan tahap pembelajaran dengan menggunakan algoritma Naïve Bayes dan SVM. 6. Mengimplementasikan Multi Class SVM dengan teknik one-against-one. Kakas SVMLight versi 6.01 hanya ditujukan untuk mengklasifikasikan data set yang hanya memiliki dua kelas target. Karena itu, perlu dibangun program tambahan yang mengimplementasikan Multi Class SVM dengan teknik one-against-one. Program tambahan ini juga mengimplementasikan model klasifikasi yang dihasilkan oleh SVMLight. 7. Mengimplementasikan model klasifikasi yang dihasilkan oleh algoritma Naïve Bayes untuk memprediksi data yang baru. 8. Mengumpulkan dokumen-dokumen web yang akan diklasifikasikan dengan melakukan query ke search engine Google. Dokumen-dokumen tersebut merupakan dokumen yang dihasilkan oleh fungsi GoogleTop(“X Y”,k) dengan X dan Y adalah kombinasi pasangan individu yang mungkin dan nilai k= 10. 9. Mengimplementasikan algoritma ClassifyRelation yang terdapat pada Algoritma II-5. Langkah ini merupakan tahap klasifikasi data yang baru dengan menggunakan model klasifikasi yang memiliki performansi maksimum.
Jenis-jenis eksperimen yang dilakukan untuk algoritma Naïve Bayes dan SVM pada tahap pembelajaran adalah sebagai berikut: 1. Algoritma Naïve Bayes Eksperimen text classification dengan menggunakan algoritma Naïve Bayes dibagi menjadi tiga jenis, yaitu: a. Dokumen direpresentasikan sebagai pasangan atribut dan nilai seperti pada Tabel III-1. Untuk representasi dokumen tersebut, pendekatan feature selection yang digunakan adalah term frequency, mutual information, dan term frequencyindex document frequency baik untuk dokumen yang dikenakan proses stemming, maupun dokumen yang tidak dikenakan proses stemming.
V-4
b. Dokumen direpresentasikan sebagai boolean-featured-vector . Pada jenis eksperimen ini atribut pada dokumen adalah n kata yang memiliki bobot tertinggi dari setiap kelompok kata ditambah dengan atribut SameLine dari Tabel III-1. Sedangkan nilai atribut adalah ada tidaknya kata tersebut pada keseluruhan dokumen. Atribut SameLine tetap digunakan karena berdasarkan eksperimen yang dilakukan [MAT06], atribut tersebut merupakan pengklasifikasi yang signifikan. Pada eksperimen ini, n yang digunakan sebesar 50 untuk setiap kelompok kata. Berdasarkan hasil eksperimen sebelumnya (1.a), maka atribut yang digunakan pada eksperimen 1.b merupakan kata-kata pada kelompok kata yang dihasilkan oleh pendekatan term frequency tanpa stemming dan mutual information dengan stemming. Hal ini dikarenakan perolehan akurasi maksimum untuk klasifikasi dokumen tanpa stemming dicapai oleh pendekatan term frequency, sedangkan untuk klasifikasi dokumen dengan stemming dicapai oleh pendekatan mutual information. c. Dokumen direpresentasikan sebagai boolean-featured-vector pada n baris pertama dokumen. Eksperimen ini dilakukan untuk menguji hipotesis bahwa kata-kata yang paling mendeskripsikan suatu kelas target tertentu terletak di baris-baris awal dokumen. Implikasi dari hipotesis ini adalah semakin kecil nilai n, semakin tinggi akurasi yang dicapai. Pada eksperimen ini, n yang digunakan adalah 25%, 50%,75%, dan 100% baris dari keseluruhan jumlah baris pada dokumen. Pada eskperimen sebelumnya (1.a dan 1.b), akurasi maksimum dicapai oleh pendekatan term frequency tanpa stemming. Karena itu, dengan memperhatikan hasil eksperimen sebelumnya, maka pada eksperimen ini atribut yang digunakan adalah kata-kata pada kelompok kata yang dihasilkan dengan pendekatan term frequency tanpa stemming.
2. Algoritma SVM Eksperimen text classification dengan menggunakan algoritma SVM
dibagi
menjadi tiga jenis, yaitu: a.
Dokumen direpresentasikan sebagai pasangan atribut dan nilai seperti pada Tabel III-1.
V-5
Dengan memperhatikan akurasi yang dicapai pada eksperimen 1.a, maka pada eksperimen ini pendekatan feature selection yang digunakan adalah term frequency tanpa stemming dan mutual information dengan stemming. b.
Dokumen direpresentasikan sebagai boolean-featured-vector Dengan memperhatikan akurasi yang dicapai pada eskperimen sebelumnya 2.a, maka atribut yang digunakan pada eksperimen ini merupakan kata-kata pada kelompok kata yang dihasilkan oleh pendekatan term frequency tanpa stemming. Hal ini dikarenakan perbedaan akurasi yang cukup signifikan untuk pendekatan term frequency tanpa stemming dan mutual information dengan stemming pada eksperimen 2.a.
c.
Dokumen direpresentasikan sebagai boolean-featured-vector pada n baris pertama dokumen. Seperti halnya pada eksperimen 1.c, eksperimen ini bertujuan untuk menguji hipotesis bahwa kata-kata yang paling mendeskripsikan suatu kelas target tertentu terletak di baris-baris awal dokumen. Nilai n yang digunakan adalah 25% ,50%,75%, dan 100% baris dari keseluruhan jumlah baris pada dokumen. Dengan memperhatikan akurasi yang dicapai pada eskperimen sebelumnya (2.b), maka pada eksperimen ini atribut yang digunakan adalah kata-kata pada kelompok kata yang dihasilkan dengan pendekatan term frequency tanpa stemming.
5.4 Pengukuran Performansi Performansi yang diukur dalam eksperimen ini adalah ketepatan atau akurasi algoritma klasifikasi dalam mengklasifikasikan test set berdasarkan model klasifikasi yang dihasilkan.
Akurasi
dihitung
melalui
perbandingan
jumlah
dokumen
yang
diklasifikasikan dengan benar dengan jumlah seluruh dokumen pada test set. Semakin tinggi nilai akurasi suatu algoritma, berarti semakin bagus performansi algoritma tersebut dalam mengklasifikasikan suatu data yang baru, yang dalam hal ini adalah jenis relasi antar sepasang individu.
5.5 Hasil Hasil eksperimen menggunakan algoritma Naïve Bayes dan SVM dirangkum berdasarkan jenis eksperimen yang telah dijelaskan pada 5.3. Tabel V-1 merangkum hasil eksperimen
V-6
nomor 1.a dan 2.a, Tabel V-2 merangkum hasil eksperimen nomor 1.b dan 2.b, sedangkan Tabel V-3 merangkum hasil eksperimen nomor 1.c dan 2.c.
Tabel V-1 Hasil Eksperimen Text Classification (a)
Non-Stemming Naïve Bayes SVM 91.18% 82.71%
Pendekatan Feature Selection
Term Frequency Term Frequency-Inverse Document Frequency Mutual Information
76.47% 38.24%
-
Stemming Naïve Bayes SVM 87.50% 75.00% 80.15%
69.92%
Tabel V-2 Hasil Eksperimen Text Classification (b)
Naïve Bayes
Pendekatan Feature Selection
Term Frequency (non stemming) Mutual Information (stemming)
SVM
88.9706% 77.941%
93.98% -
Tabel V-3 Hasil Eksperimen Text Classification (c) Algoritma
n=25%
n=50%
n=75%
n=100%
Naïve Bayes
93.38%
91.18%
88.97%
88.97%
SVM
92.48%
90.23%
86.45%
93.99%
5.6 Diskusi 5.6.1 Pengaruh Pendekatan Feature Selection Dari Tabel V-1, feature selection dengan pendekatan term frequency memberikan akurasi tertinggi dibandingkan dua pendekatan lainnya pada Naïve Bayes. Sedangkan pada SVM, pendekatan term frequency juga memberikan akurasi tertinggi dibandingkan dengan pendekatan mutual information.
V-7
100.00% 90.00% 80.00% 70.00% 60.00% 50.00% 40.00% 30.00% 20.00% 10.00% 0.00%
91.18%
87.50%
76.47%
80.15% 75.00%
89.34% 75.74% 59.20%
Pendekatan Feature Selection TF
38.24%
TF-IDF MI
Non Stemming
Stemming
Rata-Rata
Gambar V-1 Grafik Eksperimen Pendekatan Feature Selection pada Naïve Bayes
Untuk membandingkan performansi ketiga pendekatan feature selection, diambil hasil eksperimen dengan menggunakan Naïve Bayes baik pada dokumen yang telah dikenakan proses stemming, maupun dokumen yang tidak dikenakan proses stemming. Gambar V-1 menunjukkan perbedaan akurasi dari ketiga pendekatan yang digunakan pada eksperimen. Secara rata-rata, pendekatan mutual information memberikan akurasi minimum. Rendahnya akurasi yang dicapai oleh pendekatan mutual information menunjukkan bahwa data set yang digunakan memiliki perbedaan frekuensi kemunculan kata yang sangat tinggi. Akibatnya kata yang jarang muncul akan memiliki bobot mutual information yang jauh lebih tinggi daripada kata yang sering muncul [YAN97]. Hal ini juga diperkuat oleh akurasi yang dicapai oleh pendekatan term frequency-inverse document frequency. Seperti halnya mutual information, inverse document frequency akan memberikan bobot yang tinggi untuk kata-kata yang jarang muncul. Namun, pada pendekatan term frequency-inverse document frequency, bobot inverse document frequency akan dikalikan dengan bobot term frequency sehingga bobotnya akan berada di antara bobot term frequency dan mutual information. Sebagai akibatnya, akurasinya pun berada di antara akurasi yang dicapai oleh pendekatan term frequency dan pendekatan mutual information.
Dilihat dari rata–rata , perbedaan akurasi pendekatan term frequency dan term frequencyinverse document frequency adalah sebesar 13,61%, sedangkan perbedaan akurasi pendekatan term frequency dan mutual information adalah sebesar 30,15%. Hal ini menunjukkan bahwa akurasi pendekatan term frequency mengungguli dua pendekatan
V-8
lainnya walaupun pendekatan term frequency tergolong pendekatan yang sangat sederhana.
Berdasarkan diskusi di atas, dapat disimpulkan bahwa performansi pendekatan feature selection tergantung pada karakteristik data set yang digunakan. Dilihat dari akurasinya, pendekatan mutual information tidak cocok jika digunakan untuk data set yang memiliki perbedaan frekuensi kemunculan kata yang tinggi. Sebaliknya, pendekatan term frequency sangat cocok diterapkan pada data set yang memiliki perbedaan frekuensi kemunculan kata yang tinggi.
5.6.2 Pengaruh Penggunaan Stemming
100.00% 90.00% 80.00% 70.00% 60.00% 50.00% 40.00% 30.00% 20.00% 10.00% 0.00%
91.18% 87.50% 76.47%
80.15%
80.88% 68.63%
75.00%
Non Stemming
38.24%
Stemming
TF
TF-IDF
MI
Rata-Rata
Gambar V-2 Grafik Eksperimen Pengaruh Stemming pada Naïve Bayes
Pengaruh penggunaan stemming pada Naïve Bayes dapat dilihat pada Gambar V-2. Penggunaan stemming ternyata menurunkan akurasi pada pendekatan term frequency dan term frequency-inverse document frequency. Namun penurunan akurasi tersebut tidak terlalu signifikan, yaitu sebesar 3,68% untuk pendekatan term frequency dan 1,47% untuk pendekatan term frequency-inverse document frequency. Dengan demikian pengaruh penggunaan stemming untuk kedua pendekatan tersebut masih sebanding. Akan tetapi, penggunaan stemming ternyata menaikkan akurasi yang sangat signifikan pada pendekatan mutual information, yaitu sebesar 41,91%.
Hal ini disebabkan karena
V-9
penggunaan stemming akan menurunkan perbedaan frekuensi kemunculan kata pada data set sehingga cocok untuk pendekatan mutual information.
Dilihat dari rata-rata akurasinya, dapat disimpulkan bahwa penggunaan stemming menurunkan akurasi. Walaupun demikian penggunakan stemming ternyata menaikkan akurasi yang sangat signifikan pada feature selection dengan pendekatan mutual information.
5.6.3 Pengaruh Lingkup Dokumen Pengaruh banyaknya jumlah baris yang disertakan pada proses klasifikasi terhadap akurasi dapat dilihat pada Tabel V-3. Pada Naïve Bayes, jumlah baris ternyata berpengaruh terhadap akurasi. Semakin sedikit jumlah baris ternyata menaikkan akurasi. Hal ini membuktikan kebenaran hipotesis awal bahwa kata-kata yang paling mendeskripsikan suatu kelas target tertentu terletak di baris-baris awal dokumen. Akibatnya, semakin sedikit jumlah baris yang diambil, semakin tinggi akurasi yang dihasilkan. Namun, banyaknya jumlah baris yang disertakan pada proses klasifikasi ternyata tidak berpengaruh pada SVM. Hal ini dapat dilihat dari variasi akurasi yang dicapai untuk setiap jumlah baris pada Tabel V-3. Pada SVM, akurasi maksimum dicapai jika seluruh baris dokumen disertakan pada proses klasifikasi. Dengan demikian dapat disimpulkan bahwa hipotesis awal hanya berlaku pada algoritma Naïve Bayes.
5.6.4 Pengaruh Algoritma Klasifikasi Berdasarkan eksperimen yang telah dilakukan, baik Naive Bayes maupun SVM memberikan akurasi maksimum untuk representasi dokumen sebagai boolean featuredvector, proses feature selection menggunakan pendekatan term frequency serta tanpa proses stemming untuk data set yang digunakan. Perbedaan Naive Bayes dan SVM terletak pada lingkup dokumen yang digunakan. Pada Naive Bayes, akurasi maksimum didapatkan jika digunakan 25% dari baris pertama pada dokumen, sedangkan pada SVM, akurasi maksimum didapatkan jika digunakan keseluruhan dokumen. Berdasarkan Tabel V-3, akurasi maksimum Naive Bayes adalah 93,38% sedangkan akurasi maksimum SVM adalah 93,99%. Dengan demikian, perbedaan akurasi maksimum Naive Bayes dan SVM tidak signifikan, yaitu sebesar 0,61%. Dengan demikian dapat dinyatakan bahwa kedua algoritma tersebut sebanding. Hal ini juga diperkuat oleh hasil eksperimen yang dilakukan oleh [JOA04] dengan data set yang sama.
V-10
Karena akurasi kedua algoritma tersebut sebanding, maka dilakukan implementasi model klasifikasi yang dihasilkan oleh kedua algoritma tersebut untuk memprediksi data yang baru. Hasil prediksi adalah jenis relasi antara sepasang individu. Cuplikan hasil prediksi tersebut dapat dilihat pada Lampiran E. Dari hasil prediksi yang telah dilakukan, Naive Bayes cenderung mengklasifikasikan setiap dokumen ke dalam kelas target course karena kelas target course memiliki prior probability yang tinggi sebagai akibat banyaknya dokumen yang memiliki kelas target course dibandingkan dengan dokumen-dokumen yang memiliki kelas target lainnya pada tahap pembelajaran. Hal ini berarti ketepatan Naive Bayes dalam memprediksi data yang baru tergantung dari komposisi dokumendokumen dengan kelas target tertentu pada tahap pembelajaran. Sebaliknya, hasil prediksi SVM lebih variatif karena SVM tidak bergantung pada jumlah dokumen dengan kelas target tertentu pada tahap pembelajaran.
Berdasarkan hasil diskusi di atas, dapat disimpulkan bahwa akurasi algoritma klasifikasi konvensional seperti Naïve Bayes sangat tergantung pada proses preprocessing, lingkup dokumen, dan komposisi dokumen dengan kelas target tertentu pada tahap pembelajaran. Sebaliknya, algoritma SVM merupakan teknik pembelajaran baru yang lebih “tangguh” daripada teknik konvensional karena tidak tergantung pada parameter-parameter di atas. Selain itu, akurasi SVM juga melebihi akurasi Naïve Bayes. Dengan demikian SVM merupakan algoritma yang memberikan performansi maksimum untuk permasalahan text classification.
