Klasifikasi Dokumen Dengan Algoritma Naïve Bayes dengan Penambahan Parameter Probabilitas Parent

  • Published on
    17-Oct-2015

  • View
    40

  • Download
    0

Embed Size (px)

DESCRIPTION

Penerapan Algortima Naive Bayes

Transcript

  • Fakultas Ilmu Komputer Universitas Indonesia

    2009

    Klasifikasi Dokumen

    Menggunakan Algoritma

    Nave Bayes dengan

    Penambahan Parameter

    Probabilitas Parent

    Category Bayu Distiawan Trisedya - 0906644511

    Hardinal Jais 0806444530

  • i

    Daftar Isi

    Daftar Isi ......................................................................................................................................................... i

    Klasifikasi Dokumen ...................................................................................................................................... 1

    Nave Bayes ................................................................................................................................................... 2

    Inovasi ........................................................................................................................................................... 4

    Hasil Eksperimen dan Analisa ....................................................................................................................... 9

    Kesimpulan dan Saran ................................................................................................................................. 16

  • 1

    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 kata-

    kata 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

  • 2

    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.

    Nave Bayes

    Nave Bayes merupakan salah satu metode machine learning yang menggunakan perhitungan

    probabilitas. Konsep dasar yang digunakan oleh Nave bayes adalah Teorema Bayes, yaitu melakukan

    klasifikasi dengan melakukan perhitungan nilai probabilitas ( | )i jp C c D d , 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 ( | )i jp C c D d pada P={ ( | )i jp C c D d

    | c C dan d D}. Nilai probabilitas ( | )i jp C c D d dapat dihitung dengan persamaan (Mitchell,

    2005):

    ( )

    ( | )( )

    i j

    i j

    j

    P C c D d

    p C c D dP D d

    ( | ) ( )

    ( )

    j i i

    j

    p D d C c p C c

    p D d

    dengan ( | )j ip D d C c merupakan nilai probabilitas dari kemunculan dokumen dj jika diketahui

    dokemen tersebut berkategori ci, ( )ip C c adalah nilai probabilitas kemunculan kategori ci, dan

    ( )jp D d adalah nilai probabilitas kemunculan dokumen dj.

    Nave Bayes menganggap sebuah dokumen sebagai kumpulan dari kata-kata yang menyusun

    dokumen tersebut, dan tidak memperhatikan urutan kemunculan kata pada dokumen. Sehingga

    perhitungan probabilitas ( | )j ip D d C c dapat dianggap sebagai hasil perkalian dari probabilitas

    kemunculan kata-kata pada dokumen dj. Perhitungan probabilitas ( | )i jp C c D d dapat dituliskan

    sebagai berikut:

    1 2 3

    ( | ) ( )

    ( | )( , , ,..., ,... )

    k i i

    ki j

    k n

    p w C c p C c

    p C c D dp w w w w w

  • 3

    dengan ( | )k ik

    p w C c adalah hasil perkalian dari probabilitas kemunculan semua kata pada

    dokumen dj.

    Proses klasifikasi dilakukan dengan membuat model probabilistik dari dokumen training, yaitu

    dengan menghitung nilai ( | )kp w c . Untuk wkj diskrit dengan wkj V = {v1, v2, v3, , vm} maka ( | )kp w c

    dicari untuk seluruh kemungkinan nilai wkj dan didapatkan dengan melakukan perhitungan (Mitchell,

    2005):

    ,( )( | )

    ( )

    b k kjk kj

    b

    D w w cp w w c

    D c

    dan

    ( )( )

    | |

    bD cp c

    D

    dengan ,( )b k kjD w w c adalah fungsi yang mengembalikan jumlah dokumen b pada kategori c yang

    memiliki nilai kata wk = wkj, ( )bD c adalah fungsi yang mengembalikan jumlah dokumen b yang memiliki

    kategori c, dan |D| adalah jumlah seluruh training dokumen. Persamaan ,( )b k kjD w w c sering kali

    dikombinasikan dengan Laplacian Smoothing untuk mencegah persamaan mendapatkan nilai 0, yang

    dapat menggangu hasil klasifikasi secara keseluruhan. Sehingga persamaan ,( )b k kjD w w c dituliskan

    sebagai (Mitchell, 2005):

    ,( ) 1( | )

    ( ) | |

    b k kjk kj

    b

    D w w cp w w c

    D c V

    dengan |V| merupakan jumlah kemungkinan nilai dari wkj.

    Pemberian kategori dari sebuah dokumen dilakukan dengan memilih nilai c yang memiliki nilai

    ( | )i jp C c D d maksimum, dan dinyatakan dengan:

    * arg max ( | ) ( )kc C

    k

    c p p w c p c

    Kategori c* merupakan kategori yang memiliki nilai ( | )i jp C c D d maksimum. Nilai ( )jp D d

    tidak mempengaruhi perbandingan karena untuk setiap kategori nilainya akan sama. Berikut ini

    gambaran proses klasifikasi dengan algoritma Nave Bayes:

  • 4

    Gambar 1. Tahapan Proses Klasifikasi Dokumen dengan Algoritma Nave Bayes

    Inovasi

    Klasifikasi dokumen biasanya dilakukan dengan menggunakan jumlah kategori yang cukup

    besar. Diantara kategori-kategori yang ada biasanya dapat dikelompokkan lagi ke dalam kategori-

    kategori 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 Kategori Fitur (Kemunculan)

    dokumen1 Football Football(3), game(2), shoot(1)

    dokumen2 Football Football(3), manager(2), pinalty(1)

    dokumen3 Tennis Roger(2), Federer(2), win(1)

  • 5

    dokumen4 Tennis Maria(2), Sharapova(2), win(1)

    dokumen5 Computer game Football(3), game(1), computer(2)

    dokumen6 Computer game Formulaone(3), game(1), computer(2)

    dokumen7 Operating system Windows(2), memory(1), computer(2)

    dokumen8 Operating system Linux(2), disk(1), computer(2)

    dokumen9 ? Football(1), memory(1), manager(1), computer(1)

    dengan persamaan:

    ,( ) 1( | )

    ( ) | |

    kj ikj i

    i

    f w cp w c

    f c W

    ,( )kj if w c adalah nilai kemunculan kata wkj pada kategori ci

    ( )if c adalah jumlah keseluruhan kata pada kategori ci

    |W| adalah jumlah keseluruhan kata/fitur yang digunakan dan

    ( )( )

    | |

    d ii

    f cp c

    D

    ( )d if c 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

Recommended

View more >