Fakultas Ilmu Komputer Universitas Indonesia
Klasifikasi Dokumen Menggunakan Algoritma Naïve Bayes dengan Penambahan Parameter Probabilitas Parent Category Bayu Distiawan Trisedya - 0906644511 Hardinal Jais – 0806444530
2009
Daftar Isi
Daftar Isi ......................................................................................................................................................... i Klasifikasi Dokumen ...................................................................................................................................... 1 Naïve Bayes ................................................................................................................................................... 2 Inovasi ........................................................................................................................................................... 4 Hasil Eksperimen dan Analisa ....................................................................................................................... 9 Kesimpulan dan Saran................................................................................................................................. 16
i
Klasifikasi Dokumen Klasifikasi dokumen adalah proses pengelompokan dokumen sesuai dengan kategori yang dimilikinya. Klasifikasi dokumen merupakan masalah yang mendasar namun sangat penting karena manfaatnya cukup besar mengingat jumlah dokumen yang ada setiap hari semakin bertambah. Sebuah dokumen dapat dikelompokkan ke dalam kategori tertentu berdasarkan kata-kata dan kalimat-kalimat yang ada di dalam dokumen tersebut. Kata atau kalimat yang terdapat di dalam sebuah dokumen memiliki makna tertentu dan dapat digunakan sebagai dasar untuk menentukan kategori dari dokumen tersebut. Perhatikan beberapa kalimat berikut ini: 1. Harga minyak kembali bertahan di atas 67 dollar AS per barrel menjelang penutupan transaksi di bursa komoditas New York Exchange. [Ekonomi, Kompas 24 Oktober 2008] 2. Sony Dwi Kuncoro serta ganda putera Muhammad Ahsan/Bona Septano menyusul dua ganda campuran Indoensia lolos ke final turnamen Jepang Terbuka Super Series. [Olahraga, Kompas 20 September 2008]
3. Timbulnya beberapa wabah penyakit ketika musim penghujan tiba berkaitan erat dengan kerusakan kualitas lingkungan. [Kesehatan, Kompas 4 November 2008] Pada kalimat (1) terdapat kata harga dan dollar. Kata-kata tersebut memiliki keterkaitan erat dengan masalah ekonomi, sehingga dapat disimpulkan bahwa kalimat (1) membahas masalah ekonomi. Kalimat (2) memiliki kata final dan turnamen. Dari kata-kata tersebut akan muncul dugaan bahwa kalimat (2) sedang membahas masalah olahraga. Terakhir, pada kalimat (3) terdapat kata wabah dan penyakit yang menunjukkan bahwa kalimat tersebut membahas bidang kesehatan. Kata harga yang terdapat pada dokumen lain belum dapat dijadikan sebagai patokan bahwa dokumen lain tersebut membahas mengenai ekonomi. Apabila dokumen lain tersebut memiliki katakata lain yang mengarahkan pada pembahasan ekonomi secara bersamaan, maka dapat disimpulkan bahwa dokumen tersebut membahas mengenai ekonomi. Untuk dapat menentukan kategori dari sebuah dokumen haruslah dilihat semua kata-kata yang terkait pada dokumen tersebut. Manfaat dari klasifikasi dokumen adalah untuk pengorganisasian dokumen. Dengan jumlah dokumen yang sangat besar, untuk mencari sebuah dokumen akan lebih mudah apabila kumpulan dokumen yang dimiliki terorganisir dan telah dikelompokkan sesuai kategorinya masing-masing. Contoh aplikasi penggunaan klasifikasi dokumen teks yang banyak digunakan adalah e-mail spam filtering. Pada 1
aplikasi spam filtering sebuah e-mail diklasifikasikan apakah e-mail tersebut termasuk spam atau tidak dengan memperhatikan kata-kata yang terdapat di dalam e-mail tersebut. Aplikasi ini telah digunakan oleh banyak e-mail provider.
Naïve Bayes Naïve Bayes merupakan salah satu metode machine learning yang menggunakan perhitungan probabilitas. Konsep dasar yang digunakan oleh Naïve bayes adalah Teorema Bayes, yaitu melakukan klasifikasi dengan melakukan perhitungan nilai probabilitas p(C ci | D dj ) , yaitu probabilitas kategori ci jika diketahui dokumen dj. Klasifikasi dilakukan untuk mementukan kategori c C dari suatu dokumen d D dimana C = {c1, c2, c3, …, ci} dan D = {d1, d2, d3, …, dj}. Penentuan dari kategori sebuah dokumen dilakukan dengan mencari nilai maksimum dari p(C ci | D dj ) pada P={ p(C ci | D dj ) | c C dan d D}. Nilai probabilitas p(C ci | D dj ) dapat dihitung dengan persamaan (Mitchell, 2005):
p(C ci | D dj )
P(C ci D dj ) P( D dj )
p( D dj | C ci) p(C ci) p( D dj )
dengan p( D dj | C ci) merupakan nilai probabilitas dari kemunculan dokumen dj jika diketahui dokemen tersebut berkategori ci, p(C ci )
adalah nilai probabilitas kemunculan kategori ci, dan
p( D dj ) adalah nilai probabilitas kemunculan dokumen dj. Naïve Bayes menganggap sebuah dokumen sebagai kumpulan dari kata-kata yang menyusun dokumen tersebut, dan tidak memperhatikan urutan kemunculan kata pada dokumen. Sehingga perhitungan probabilitas p( D dj | C ci) dapat dianggap sebagai hasil perkalian dari probabilitas kemunculan kata-kata pada dokumen dj. Perhitungan probabilitas p(C ci | D dj ) dapat dituliskan sebagai berikut:
p( w
k
p(C ci | D dj )
| C ci ) p(C ci )
k
p( w1, w2, w3,..., wk ,...wn) 2
dengan
p( w
k
| C ci) adalah hasil perkalian dari probabilitas kemunculan semua kata pada
k
dokumen dj. Proses klasifikasi dilakukan dengan membuat model probabilistik dari dokumen training, yaitu dengan menghitung nilai p( wk | c) . Untuk wkj diskrit dengan wkj V = {v1, v2, v3, …, vm} maka p( wk | c) dicari untuk seluruh kemungkinan nilai wkj dan didapatkan dengan melakukan perhitungan (Mitchell, 2005):
p( wk wkj | c)
Db( wk wkj , c) Db(c)
dan
p (c )
Db(c) |D|
dengan Db(wk wkj , c) adalah fungsi yang mengembalikan jumlah dokumen b pada kategori c yang memiliki nilai kata wk = wkj, Db(c) adalah fungsi yang mengembalikan jumlah dokumen b yang memiliki kategori c, dan |D| adalah jumlah seluruh training dokumen. Persamaan Db(wk wkj , c) sering kali dikombinasikan dengan Laplacian Smoothing untuk mencegah persamaan mendapatkan nilai 0, yang dapat menggangu hasil klasifikasi secara keseluruhan. Sehingga persamaan Db(wk wkj , c) dituliskan sebagai (Mitchell, 2005):
p( wk wkj | c)
Db( wk wkj , c) 1 Db(c) | V |
dengan |V| merupakan jumlah kemungkinan nilai dari wkj. Pemberian kategori dari sebuah dokumen dilakukan dengan memilih nilai c yang memiliki nilai
p(C ci | D dj ) maksimum, dan dinyatakan dengan:
c* arg max p p( wk | c) p(c) cC
k
Kategori c* merupakan kategori yang memiliki nilai p(C ci | D dj ) maksimum. Nilai p( D dj ) tidak mempengaruhi perbandingan karena untuk setiap kategori nilainya akan sama. Berikut ini gambaran proses klasifikasi dengan algoritma Naïve Bayes: 3
Gambar 1. Tahapan Proses Klasifikasi Dokumen dengan Algoritma Naïve Bayes
Inovasi Klasifikasi dokumen biasanya dilakukan dengan menggunakan jumlah kategori yang cukup besar. Diantara kategori-kategori yang ada biasanya dapat dikelompokkan lagi ke dalam kategorikategori yang lebih umum yang memiliki domain yang sama, atau dapat disebut sebagai parent category. Diantara kategori-kategori yang memiliki domain yang sama banyak terdapat fitur-fitur yang sama yang menunjukkan ciri dari parent category-nya tersebut. Banyaknya fitur-fitur yang saling beririsan tersebut membuat jumlah kesalahan klasifikasi antar kategori yang memiliki domain yang sama sangat besar. Untuk lebih jelasnya, perhatikan contoh berikut ini:
Dokumen dokumen1 dokumen2 dokumen3
Kategori Football Football Tennis
Fitur (Kemunculan) Football(3), game(2), shoot(1) Football(3), manager(2), pinalty(1) Roger(2), Federer(2), win(1) 4
dokumen4 dokumen5 dokumen6 dokumen7 dokumen8 dokumen9
Tennis Computer game Computer game Operating system Operating system ?
Maria(2), Sharapova(2), win(1) Football(3), game(1), computer(2) Formulaone(3), game(1), computer(2) Windows(2), memory(1), computer(2) Linux(2), disk(1), computer(2) Football(1), memory(1), manager(1), computer(1)
dengan persamaan:
p( wkj | ci )
f ( wkj , ci ) 1 f (ci ) | W |
f (wkj , ci ) adalah nilai kemunculan kata wkj pada kategori ci f (ci ) adalah jumlah keseluruhan kata pada kategori ci |W| adalah jumlah keseluruhan kata/fitur yang digunakan dan
p(ci )
fd (ci ) |D|
fd (ci ) adalah jumlah dokumen yang memiliki kategori ci |D| adalah jumlah seluruh training dokumen dibentuk sebuah model probabilistik:
Kategori
p(ci)
p(wkj|ci) computer federer football formulaone game linux manager maria pinalty roger sharapova shoot disk memory win windows
Football
¼
1/28
1/28
7/28
1/28
3/28 1/28 3/28
1/28 2/28
1/28 1/28
2/28 1/28 1/28
1/28 1/28
Tennis
¼
1/26
3/26
1/26
1/26
1/26 1/26 1/26
3/26 1/26
3/26 3/26
1/26 1/26 1/26
3/28 1/26
Computer game
¼
5/28
1/28
4/28
4/28
3/28 1/28 1/28
1/28 1/28
1/28 1/28
1/28 1/28 1/28
1/28 1/28
5/26
1/26
1/26
1/26
1/26 3/26 1/26
1/26 1/26
1/26 1/26
1/26 2/26 2/26
1/26 3/26
Operating system ¼
Penentuan kategori untuk dokumen9:
c* arg max p( wkj | ci ) p(ci) ciC
k
5
p(“football”|”dokumen9”)= p(“football”) x p(“football”|” football”) x p(“memory”|” football”) x p(“manager”|” football”) x
p(“computer”|” football”)
= 1/4 x 7/28x 1/28 x 3/28 x 1/28 = 21/2458645 ≈ 8,5141 x 10-6 p(“tennis”|”dokumen9”)= p(“tennis”) x p(“football”|” tennis”) x p(“memory”|” tennis”) x p(“manager”|” tennis”) x
p(“computer”|” tennis”)
= 1/4 x 1/26x 1/26 x 1/26 x 1/26 = 1/1827904 ≈ 5,4707 x 10-7 p(“computer game”|”dokumen9”)= p(“computer game”) x p(“football”|” computer game”) x p(“memory”|” computer game”) x
p(“manager”|” computer game”) x p(“computer”|” computer game”)
= 1/4 x 4/28x 1/28 x 1/28 x 5/28 = 20/2458645 ≈ 8,1346 x 10-6 p(“operating system”|”dokumen9”)= p(“operating system”) x p(“football”|” operating system”) x p(“memory”|” operating system”) x
p(“manager”|” operating system”) x p(“computer”|” operating
system”)
= 1/4 x 1/26x 2/26 x 1/26 x 1/26 = 2/1827904 ≈ 1,094 x 10-6 Secara intuitif, kita dapat menentukan bahwa kategori dokumen9 adalah computer game, namun dari perhitungan metode naïve bayes dokumen9 diklasifikasikan ke kategori football. Pada perhitungan tersebut, dokumen9 diklasifikasikan ke dalam kategori football karena prior probability dari ketegori computer game kurang memiliki informasi general mengenai computer yang relevansinya dengan kategori computer game cukup besar. Dalam hal ini sebagai contoh fitur “disk” yang dimiliki oleh dokumen9 yang sebenarnya dapat diidentifikasi bila kita melihat kumpulan dokumen ke dalam kelompok-kelompok yang lebih general. Oleh karena itu, pada tugas machine learning kali ini akan
6
dilakukan klasifikasi dokumen menggunakan metode naïve bayes dengan menambahkan nilai prior probability dari parent category dari masing-masing kategori spesifiknya. Berikut ilustrasinya: General Kategori p(ci)
p(wkj|ci) computer federer football formulaone game linux manager maria pinalty roger sharapova shoot disk memory win windows
Sports
½
1/38
3/38
7/38
1/38
3/38 1/38 3/38
3/38 2/38
3/38 3/38
2/38 1/38 1/38
3/38 1/38
Computer
½
9/38
1/38
4/38
4/38
3/38 3/38 1/38
1/38 1/38
1/38 1/38
1/38 2/38 2/38
1/38 3/38
p(“sports”|”dokumen9”)= p(“sports”) x p(“football”|” sports”) x p(“memory”|” sports”) x p(“manager”|” sports”) x
p(“computer”|” sports”)
= 1/2 x 7/38x 1/38 x 3/38 x 1/38 = 21/4170272 ≈ 5,0356 x 10-6 p(“computer”|”dokumen9”)= p(“computer”) x p(“football”|” computer”) x p(“memory”|” computer”) x p(“manager”|” computer”) x p(“computer”|” computer”) = 1/2 x 4/38x 2/38 x 1/38 x 9/38 = 72/4170272 ≈ 1,7265 x 10-5
sehingga untuk menentukan kategori dilakukan perhitungan: p(“football”|”dokumen9”)* = p(“football”|”dokumen9”) x p(“sports”|”dokumen9”) = 21/2458645 x 21/4170272 = 441/1,0253 x 1013 ≈ 4,3010 x 10-11 p(“tennis”|”dokumen9”)* = p(“tennis”|”dokumen9”) x p(“sports”|”dokumen9”) = 1/1827904 x 21/4170272 = 21/7,6228 x 1012 ≈ 2,7548 x 10-12
p(“computer game”|”dokumen9”)* = p(“computer game”|”dokumen9”) x p(“computer”|”dokumen9”) 7
= 20/2458645 x 72/4170272 = 1440/1,0253 x 1013 ≈ 1,4044 x 10-10 p(“opeating system”|”dokumen9”)* = p(“opertaing system”|”dokumen9”) x p(“computer”|”dokumen9”) = 2/1827904 x 72/4170272 = 144/1,0253 x 1013 ≈ 1,4044 x 10-11 dari perhitungan tersebut maka dokumen9 diklasifikasikan ke kategori computer game. Penambahan prior probability dari parent category dengan menggunakan algoritma Naïve Bayes ini mirip dengan penambahan unlabeled documents pada klasifikasi dokumen menggunakan algoritma Expectation Maximization. Pada klasifikasi dokumen menggunakan algoritma Expectation Maximization hasil klasifikasi diperbaiki dengan memperkaya fitur-fitur yang dimiliki sebuah kategori yang belum tercakup pada labeled document dengan persamaan sebagai berikut: |C |
p( D | ) p(C ci | ) p(dj | C ci; ) p(ci | ) p(dj | ci; ) djDu i 1
djDl
Proses klasifikasi dokumen dengan menambahkan prior probability dari parent category bertujuan untuk menambahkan fitur-fitur yang dimiliki sebuah kategori dengan memanfaatkan fitur dari kategori lain yang masih dalam satu domain. Proses tersebut mirip dengan penambahan fitur dari unlabeled documents dari algoritma Expectation Maximization, sehingga bagian kedua dari persamaaan |C |
algoritma Expectation Maximization
p(c | ) p(d | c ; ) digantikan p(C c | ) p(d | C c ; ) , i
j
i
i
djDu i 1
j
i
djDp
maka persamaan klasifikasi dokumen dengan menambahkan prior prbability dari parent category dapat dituliskan sebagai berikut:
p( D | ) p(C ci | ) p(dj | C ci; ) p(C ci | ) p(dj | C ci; ) djDl
djDp
Dengan memperhatikan hal-hal tersebut maka diharapkan inovasi yang dilakukan ini dapat meningkatkan akurasi dari klasifikasi dokumen dengan memperkecil kesalahan klasifikasi antar kategori yang memiliki domain yang berbeda.
8
Hasil Eksperimen dan Analisa Untuk menguji hipotesis bahwa dengan penambahan parameter prior probability dari parent category akan meningkatkan akurasi klasifikasi dokumen, maka dilakukan percobaan klasifikasi dokumen. Percobaan ini dilakukan dengan menggunakan program yang dibuat dengan memanfaatkan library WEKA 3.5.7 yang didapat dari http://www.cs.waikato.ac.nz/~ml/weka/. WEKA merupakan kumpulan algoritma machine learning yang ditulis dalam bahasa pemrograman Java. Data yang digunakan dalam percobaan ini adalah dataset 20Newsgroups dataset dari http://people.csail.mit.edu/jrennie/20Newsgroups/. Data ini berupa kumpulan e-mail yang memiliki 20 buah kategori. Dokumen e-mail yang terdapat pada 20Newsgroups dataset yang digunakan pada percobaan ini merupakan dokumen-dokumen yang telah dihilangkan tag header-nya. Jumlah keseluruhan dokumen yang digunakan mencapai 18828 dokumen. Data akan direpresentasikan ke dalam term-document matrix. Term documents matrix marupakan representasi kumpulan dokumen yang akan digunakan untuk melakukan proses klasifikasi dokumen teks. Pada term documents matrix, sebuah dokumen direpresentasikan sebagai kumpulan fitur dan dapat diilustrasikan sebagai dj = [w1j, w2j, …, wkj] dengan dj merupakan dokumen ke-j dan wkj merupakan nilai kemunculan fitur ke-k pada dokumen dj. Matriks ini akan berisi nilai-nilai kemunculan fitur. Jenis fitur yang akan digunakan pada percobaan ini adalah jenis fitur frekuensi. Jenis fitur frekuensi akan menyimpan nilai frekuensi kemunculan fitur pada sebuah dokumen. Untuk menghilangkan bias data, pada percobaan ini dilakukan k-fold cross validation. Pada percobaan ini digunakan 3 buah fold. Satu buah fold digunakan untuk testing documents, sedangkan dua fold lainnya digunakan untuk training documents. Percobaan pertama dilakukan dengan menggunakan 10000 fitur. Jumlah dokumen training yang digunakan bervariasi mulai dari 500 dokumen hingga 10000 dokumen. Hasil yang diperoleh menunjukkan bahwa dengan menambahkan parameter prior probability dari parent category dapat meningkatkan hasil klasifikasi dokumen teks. Rata-rata peningkatan akurasi klasifikasi dapat mencapai 0,81%. Berikut grafik hasil klasifikasi dokumen menggunakan 10000 fitur.
9
Gambar 2. Hasil Klasifikasi Dokumen Menggunakan 10000 Fitur
Percobaan pertama dilakukan dengan menggunakan 20000 fitur. Jumlah dokumen training yang digunakan bervariasi mulai dari 500 dokumen hingga 10000 dokumen. Hasil yang diperoleh menunjukkan bahwa dengan menambahkan parameter prior probability dari parent category dapat meningkatkan hasil klasifikasi dokumen teks. Rata-rata peningkatan akurasi klasifikasi dapat mencapai 0,79%. Berikut grafik hasil klasifikasi dokumen menggunakan 10000 fitur.
Gambar 3. Hasil Klasifikasi Dokumen Menggunakan 20000 Fitur
10
Pada percobaan kedua rata-rata peningkatan akurasi klasifikasi yang didapatkan lebih rendah. Hal ini disebabkan oleh fitur-fitur spesifik dari sebuah kategori sudah masuk ke dalam daftar fitur yang digunakan, sehingga klasifikasi menggunakan algoritma Naïve Bayes biasa telah memberi hasil yang baik. Namun dengan menambahkan jumlah fitur yang besar akan meningkatkan proses komputasi sehingga proses klasifikasi dokumen menjadi jauh lebih lama. Dari dua hasil yang diperoleh tersebut dapat disimpulkan bahwa dengan menambahkan parameter pror probability dari parent category dapat meningkatkan hasil klasifikasi dokumen dengan memperkecil jumlah kesalahan klasifikasi antar kategori yang memiliki domain yang berbeda. Dari proses klasifikasi dokumen dengan menggunakan parameter prior probability dari parent category didapatkan beberapa jenis kesalahan klasifikasi sebagai berikut: x = Kelas hasil klasifikasi Naïve Bayes biasa. y = Kelas hasil klasifikasi Naïve Bayes dengan penambahan parameter parent probability.
1. Kesalahan dari kelas x ke kelas y, dimana parent(x) == parent(y), parent(realTopic) != parent(x) dan parent(realTopic) != parent(y) 2. Kesalahan dari kelas x ke kelas y, dimana parent(x) != parent(y), parent(realTopic) != parent(x) dan parent(realTopic) != parent(y) Dari kesalahan 1 dan 2 didapatkan kesalahan ini terjadi ketika distribusi probabilitas sebuah dokumen merata untuk setiap kategori. Dari hasil tersebut diperoleh bahwa penambahan fitur dari parent category tidak mempengaruhi hasil klasifikasi dokumen-dokumen tersebut. 3. Kesalahan dari kelas x ke kelas y, dimana parent(x) != parent(y), parent(realTopic) != parent(x) dan parent(realTopic) == parent(y). Dari hasil ini diperoleh bahwa penambahan parameter probabilitas parent category memberikan hasil yang cukup baik, ditunjukkan dengan beralihnya kesalahan klasifikasi menuju ke kategori yang memiliki domain dama dengan kategori aslinya. 4. Kesalahan dari kelas x ke kelas y, dimana realTopic == x dan realTopic != y. Artinya dokumendokumen yang diklasifikasikan benar dengan Naive Bayes biasa menjadi salah diklasifikasikan dengan menggunakan penambahan parameter parent probability. Kesalahan klasifikasi ini dipengaruhi jumlah fitur yang digunakan dalam merepresentasikan term document matrix. Semakin banyak jumlah fitur yang digunakan, maka kesalahan yang muncul akan semakin sedikit. Hal ini diakibatkan karena pemilihan fitur diurutkan berdasarkan frekuensi kemunculan 11
fitur pada kumpulan dokumen yang digunakan. Semakin sedikit fitur yang digunakan maka semakin sedikit spesifik fitur yang dimiliki oleh sebuah kategori dan parentnya, sehingga semakin besar kemungkinan sebuah dokumen memiliki fitur-fitur yang beririsan antara parent category, sehingga tidak didapatkan gambaran umum yang baik dari sebuah dokumen. Dengan memperbesar jumlah fitur yang digunakan maka fitur-fitur spesifik yang ada pada sebuah kategori dapat tercakup, sehingga dapat mengurangi kesalahan klasifikasi ini. Untuk lebih jelasnya perhatikan gambar berikut ini:
a
b
Gambar 4. a) Distribusi Fitur pada Penggunaan 10000 Fitur b) Distribusi Fitur pada Penggunaan 20000 Fitur
Untuk menggambarkan decision boundary dari hasil klasifikasi Naïve Bayes biasa dan Naïve Bayes dengan penambahan parameter prior probability dari parent category maka digunakan ndimensional density function sebagai berikut:
1 1 n yj ( X ) ( X Xj )T K j 1 ( X Xj ) ln Kj ln 2 ln P(Cj ) 2 2 2 Untuk memperjelas decision boundary maka digunakan dua buah kelas, yaitu kelas dokumen yang diklasifikasikan benar dan kelas dokumen yang diklasifikasikan salah, sehingga persamaannya menjadi dapat dituliskan sebagai berikut:
1 1 n yb( X ) ( X Xb)T Kb1 ( X Xb) ln Kb ln 2 ln P(Cb) 2 2 2 1 1 n ys ( X ) ( X Xs)T K s1 ( X Xs) ln Ks ln 2 ln P(Cs) 2 2 2 12
Untuk menggambarkan decision boundary dari kedua kelas tersebut maka dilakukan kombinasi antara dua buah diskriminan tersebut y( X ) ys( X ) yb( X ) , sehingga persamaan decision boundary dari Naïve Bayes diturunkan menjadi:
1 1 1 Kb P(Cb) y( X ) ( X Xb)T Kb1 ( X Xb) ( X Xs)T K s1 ( X Xs) ln ln 2 2 2 Ks P(Cs) Dari persamaan tersebut bisa muncul tiga buah kemungkinan decision boundary yang terbentuk. Kemungkinan pertama adalah jika matriks kovarians yang dibentuk adalah Ki 2 I , maka:
2 0 0 0 0 2 ... 0 Ki 2d 0 ... ... ... 0 ... 2 0 i 1 (1/ 2 ) I
i 2 I independen untuk setiap fitur i Penurunan rumusan matematisnya adalah sebagai berikut: Nilai
1 n ln Ki dan ln 2 dapat diabaikan karena akan konstan, maka 2 2 yi ( X )
yi ( X )
|| X Xi ||2 ln P(Ci) , dengan || X Xi ||2 ( X X )T ( X X ) 2 2
1 2
[ X T X 2 X iT X X iT X i ] ln P(Ci) , dengan X T X konstan
2
yi ( X ) wiT X i wi 0 (linear discriminant) Dimana wi
1
2
X i dan wi 0
1 2
2
X iT X i ln P(Ci )
Kemungkinan kedua adalah jika matriks kovarians yang dibentuk kovarians yang terbentuk acak namun nilainya sama untuk semuafitur yang ada Ki K , maka fitur-fitur tersebut akan membentuk
13
hyper-ellipsoidal clusters dengan ukuran dan bentuk yang sama. Untuk kasus ini decision boundary yang dibentuk adalah linier namun masih belum dapat menentukan decision region-nya. Penurunan rumusan matematisnya adalah sebagai berikut: Nilai
1 n ln Ki dan ln 2 dapat diabaikan karena akan konstan, maka 2 2 1 yi ( X ) ( X X i )T K 1 ( X X i ) ln P(Ci) 2 yi ( X ) wiT X i wi 0 (linear discriminant) 1 Dimana wi K X i dan wi 0
1 T 1 X i K X i ln P(Ci ) 2
Kemungkinan ketiga seperti yang diperoleh pada percobaan ini adalah dimana kovarians yang terbentuk nilainya acak dan memiliki nilai yang berbeda-beda untuk tiap-tiap kategori yang ada. Dalam kasus ini decision boundary yang terbentuk adalah hyperquadratics (hyperplanes, pasangan hyperplanes, hyperspheres, hyperellipsoids, hyperparaboloids, hyperhyperboloids). Decision boundary yang terbentuk telah dapat memisahkan region dari masing-masing kategori. Penurunan rumusan matematisnya adalah sebagai berikut: Nilai
n ln 2 dapat diabaikan karena akan konstan, maka 2 yi( X ) X TWi X wi X wi 0 (quadratic discriminant) Dimana Wi
1 1 Ki , wi K 1 X i dan 2
1 1 wi 0 X iT K 1 X i ln | Ki | ln P(Ci ) 2 2 Penjelasan diatas juga menambahkan pengetahuan kita mengenai penambahan jumlah fitur akan memperkecil rata-rata peningkatan akurasi. Karena dengan menambahkan jumlah fitur yang digunakan untuk menggambarkan sebuah kategori, maka nilai kovarian dari masing-masing kategori akan semakin 14
kecil sehingga membuat decision boundary yang terbentuk makin mempersempit decision region dari masing-masing kategori yang ada sehingga dengan naïve bayes biasa sudah memberikan akurasi yang cukup baik dan penambahan parameter prior probability dari parent category hanya memberi sedikit informasi tambahan dari fitur-fitur parent category nya. Hal tersebut dapat dicapai dengan memaksimalkan nilai Maximum Likelihood Estimation dengan penambahan parameter prior probability dari parent category sebgai berikut: n
p( D | ) p( xi | ) , xi adalah fitur-fitur yang digunakan dalam model probabilistik Naïve i 1
Bayes. Untuk memaksimalkan p( D | ) , maka:
p( D | ) 0 , untuk mempermudah perhitungan maka digunakan ln p( D | ) ln p( D | ) 0 n
ln p( x
k
i 1
| ) 0
ˆ arg max ln p( D | ) , untuk meyakinkan bahwa penambahan fitur dapat memperkecil kovarians, maka digunakan distribusi gausian sebagai berikut:
1 n 1 ln p( xi | ) ( xi )T K 1 ( xi ) ln 2 ln | K | , dengan gradien 2 2 2 ln p( xi | ) K 1 ( xi ) , untuk mendapatkan nilai optimum, maka ln p( xi | ) 0 n
K i 1
ˆ
1
( xi ) 0 , maka
1 n xi , maka semakin banyak fitur yang berkorelasi dengan sebuah kategori akan n i 1
memperbesar nilai ˆ sehingga decision region yang terbentuk semakin optimal. Dilihat dari nilai kovarians probabilitas hasil klasifikasi dokumen, didapatkan hasil bahwa nilai kovarians dari Naïve Bayes biasa lebih besar daripada nilai kovarians yang diperoleh dari algoritma Naïve Bayes dengan penambahan parameter prior probability dari parent category. Hal ini menunjukkan bahwa probabilitas yang didapatkan dengan penambahan parameter prior probability dari parent 15
category lebih stabil dan presisi, dan menghasilkan decision boundary yang lebih baik. Dari hasil tersebut juga meunjukkan bahwa terdapat keterkaitan antara fitur-fitur dari category dengan parent categorynya sehingga dapat memberikan informasi fitur tambahan yang diperlukan. Berikut gambaran decision boundary dari dua buah metode yang digunakan:
a
b
Gambar 5. a) Decision Boundary dari Metode Naïve Bayes Biasa b) Decision Boundary dari Metode Naïve dengan Penambahan Parameter Prior Probability dari Parent Category
Kesimpulan dan Saran Dari hasil yang diperoleh dapat ditarik beberapa kesimpulan sebagai berikut: 1. Penambahan parameter prior probability dari parent category dapat meningkatkan akurasi klasifikasi dokumen teks dengan mengurangi kesalahan klasifikasi antar dokumen yang memiliki domain yang berbeda. 2. Dengan penambahan parameter prior probability dari parent category dimungkinkan terjadi kesalahan klasifikasi dimana pada penggunaan metode Naïve Bayes biasa diklasifikasikan benar 16
menjadi salah diklasifikasikan apabila menggunakan penambahan parameter prior probability dari parent categor. Walaupun jumlah kesalahan ini sangat kecil, namun dapat mempengaruhi hasil klasifikasi secara keseluruhan. Hal ini dapat dikurangi dengan penambahan jumlah fitur yang digunakan untuk membangun model probabilistik yang ada. Saran yang mungkin dapat dipertimbangkan untuk pengembangan metode klasifikasi dokumen teks selanjutnya antara lain: 1. Mempergunakan berbagai macam jenis fitur seperti TF-IDF, frequency normalized dan lain sebagainya, karena pada eksperimen ini hanya digunakan satu jenis fitur saja, yaitu jenis fitur frekuensi. 2. Mempergunakan metode hierarchical document classification untuk melihat sisi lain dari pengaruh penggunaan parameter prior probability dari parent category.
17
