BAB II KAJIAN PUSTAKA
2.1
Retrival Informasi Retrival informasi merupakan bagian dari ilmu komputer yang berhubungan dengan pengambilan informasi dari dokumen-dokumen yang didasarkan pada isi dan konteks dari dokumen-dokumen itu sendiri. Retrival informasi merupakan suatu pencarian informasi (biasanya berupa dokumen) yang didasarkan pada suatu kueri (input pengguna) yang diharapkan dapat memenuhi keinginan pengguna dari kumpulan dokumen yang ada. Sedangkan, definisi kueri dalam retrival informasi merupakan sebuah formula yang digunakan untuk mencari informasi yang dibutuhkan oleh pengguna, dalam bentuk yang paling sederhana, sebuah kueri merupakan suatu keywords (kumpulan kata kunci) dan dokumen yang mengandung keywords merupakan dokumen yang dicari dalam sistem retrival informasi. Proses dalam retrival informasi dapat digambarkan sebagai sebuah proses untuk mendapatkan dokumen yang relevan dari kumpulan dokumen yang ada melalui pencarian kueri yang di-input oleh pengguna. Sistem retrival informasi bertujuan untuk menjembatani kebutuhan informasi pengguna dengan sumber informasi yang tersedia dalam situasi seperti dikemukakan oleh Belkin (1980,p133-143) sebagai berikut: 1.
M empresentasikan sekumpulan ide dalam sebuah dokumen menggunakan sekumpulan konsep.
9
10
2.
Terdapat beberapa pengguna yang memerlukan ide yang telah dikemukakan tersebut, tapi mereka tidak dapat mengidentifikasikan dan menemukannya dengan baik.
3.
Sistem retrival informasi bertujuan untuk mempertemukan ide yang dikemukakan dalam dokumen dengan kebutuhan informasi pengguna yang dinyatakan dalam bentuk pertanyaan (kueri). Berkaitan dengan sumber informasi di satu sisi dan kebutuhan informasi pengguna
di sisi yang lain, sistem retrival informasi berperan untuk: 1.
M enganalisis isi sumber informasi dan pertanyaan pengguna.
2.
M empertemukan
pertanyaan
pengguna
dengan
sumber
informasi
untuk
mendapatkan dokumen yang relevan. Adapun fungsi utama sistem retrival informasi seperti dikemukakan oleh Lancaster (1979) dan Kent (1971) adalah sebagai berikut: 1.
M engidentifikasi sumber informasi yang relevan dengan minat masyarakat pengguna yang ditargetkan.
2.
M enganalisis isi sumber informasi (dokumen).
3.
M erepresentasikan isi sumber informasi dengan cara tertentu yang memungkinkan untuk dipertemukan dengan pertanyaan (kueri) pengguna.
4.
M erepresentasikan pertanyaan (kueri) pengguna dengan cara tertentu yang memungkinkan untuk dipertemukan sumber informasi yang terdapat dalam basis data.
11
5.
M empertemukan pernyataan pencarian dengan data yang tersimpan dalam basis data.
6.
M enemu-kembalikan informasi yang relevan.
7.
M enyempurnakan unjuk kerja sistem berdasarkan umpan balik yang diberikan oleh pengguna. Sementara itu Tague-Sutcliffe (1996,pp1-3) melihat sistem retrival informasi
sebagai suatu proses yang terdiri dari 6 (enam) komponen utama yaitu: 1.
Kumpulan dokumen
2.
Pengindeksan
3.
Kebutuhan informasi pemakai
4.
Strategi pencarian
5.
Kumpulan dokumen yang ditemukan
6.
Penilaian relevansi M enurut Baeza-Yates (1999, pp20-22), terdapat tiga macam model klasik dalam
retrival informasi yaitu Boolean, vektor, dan probabilitas. Pada model Boolean, dokumen dan kueri direpresentasikan sebagai satu set index terms. Oleh karena itu, dikatakan bahwa model ini adalah set theoretic. Teknik Boolean merupakan suatu cara dalam mengekspresikan keinginan pemakai ke sebuah kueri dengan mamakai operator-operator Boolean yaitu : “and”, “or”, dan “not”. Adapun maksud dari operator “and” adalah untuk menggabungkan istilah-istilah kedalam sebuah ungkapan, dan operator “or” adalah untuk memperlakukan istilah-istilah sebagai sinonim, sedangkan operator “not” merupakan sebuah pembatasan.
12
Pada model vektor, dokumen dan kueri direpresentasikan sebagai vektor dalam sebuah ruang t-dimensi. Oleh karena itu, dikatakan bahwa model ini adalah algebraic. Pada model probabilitas, kerangka kerja untuk membuat model dokumen dan kueri direpresentasikan berdasarkan teori probabilitas. Oleh karena itu, model ini dinamakan probabilistic. Dalam sebuah sistem retrival informasi yang konvensional, dokumen yang ada di dalam koleksi tetap statis sementara kueri baru yang dimasukkan ke dalam sistem. M odel operasional ini disebut sebagai ad hoc retrieval dan sering digunakan pada beberapa tahun belakangan ini. Sebuah tugas yang mirip namun berbeda adalah dimana kueri nya tetap statis dan dokumen baru yang masuk ke dalam sistem (dan pergi). M odel operasional memiliki istilah yaitu penapisan. Sebagai contoh, penapisan dapat digunakan dalam pemilihan sebuah artikel berita di antara ribuan artikel yang diterbitkan setiap hari.
2.1.1
Kategorisasi Dokumen Teks M enurut Ramadan (2006, pp1-2), pengkategorisasian dokumen teks adalah suatu
hal yang penting dan kebutuhan terhadapnya akan semakin meningkat seiring dengan berjalannya waktu, karena dokumen semakin lama akan semakin banyak dan ukuran harddisk akan semakin besar. Sehingga perlu dilakukan pengkajian metode untuk kategorisasi dokumen teks dan uji coba terhadap hal tersebut melalui melakukan eksperimen terhadap beberapa metode-metode kategorisasi, yaitu metode dengan menggunakan pohon, naïve Bayes, K-Nearest Neighbor dan Neural Network. Ada dua varian utama dalam pengkategorisasian dokumen teks: klasterisasi dokumen teks dan pengkategorisasian dokumen teks. Klasterisasi dokumen teks
13
berhubungan dengan menemukan sebuah struktur kelompok yang belum kelihatan dari sekumpulan dokumen teks. Sedangkan pengkategorisasian dokumen teks dapat dianggap sebagai task untuk membentuk struktur dari penyimpanan dokumen teks berdasarkan pada struktur kelompok yang sudah diketahui sebelumnya. Pada kategorisasi dokumen teks, diberikan sekumpulan kategori (label) dan koleksi dokumen yang berfungsi sebagai data latih, yaitu data yang digunakan untuk membangun model, dan kemudian dilakukan proses untuk menemukan kategori yang tepat untuk dokumen test, yaitu dokumen yang digunakan untuk menentukan akurasi dari model. M isalkan ada sebuah dokumen x sebagai input, maka output yang dihasilkan oleh model tersebut adalah kelas atau kategori y dari beberapa kategori tertentu yang telah didefinisikan sebelumnya (y1,…,yk). Adapun contoh dari pemanfaatan kategorisasi dokumen teks adalah pengkategorisasian berita ke dalam beberapa kategori seperti bisnis, teknologi, kesehatan dan lain sebagainya; pengkategorisasian email sebagai spam atau bukan; pengkategorisasian kilasan film sebagai film favorit, netral atau tidak favorit; pengkategorisasian paper yang menarik dan tidak menarik; dan penggunaan dari kategorisasi dokumen teks yang paling umum adalah kategorisasi otomatis dari web pages yang dimanfaatkan oleh portal Internet seperti Yahoo. M enurut Thoster Joachim (1999), tujuan dari text categorization adalah pengklasifikasian dokumen teks ke dalam jumlah kategori yang sudah ditentukan. Setiap dokumen bisa memiliki banyak kategori, tepat satu kategori, atau tidak memiliki kategori sama sekali. Dengan menggunakan machine learning, tujuannya adalah untuk mempelajari classifiers dari contoh-contoh yang mewakili tiap kategori secara otomatis.
14
Berdasarkan definisi di atas, dapat disimpulkan bahwa text categorization adalah sebuah proses untuk mengkategorisasi sebuah dokumen teks sesuai dengan kategori yang telah ditentukan yang bertujuan untuk mempermudah dalam mengorganisir dokumen teks dalam jumlah besar.
2.1.2
Retrival Dokumen Teks Retrival dokumen teks adalah sebuah cabang dari retrival informasi dimana
informasi yang disimpan adalah berupa teks. Sistem retrival dokumen teks menemukan informasi dari kriteria yang diberikan dengan mencocokkan kueri yang dimasukkan oleh pengguna akhir dengan dokumen-dokumen teks yang telah tersimpan. Sebuah sistem retrival dokumen teks terdiri dari koleksi dokumen teks, sebuah algoritma klasifikasi untuk membangun indeks, dan sebuah antarmuka pengguna untuk menghubungkan dengan koleksi. Sebuah sistem retrival dokumen teks memiliki dua tugas utama, yaitu : 1.
M enemukan dokumen teks yang relevan sesuai dengan kueri yang dimasukkan.
2.
M engevaluasi dokumen teks yang cocok dan mengurutkan sesuai dengan relevansinya dengan menggunakan algoritma tertentu. M enurut Ricardo Baeza-Yates (1999,p10), proses dari retrival informasi teks adalah
sebagai berikut :
15
Gambar 2.1 Proses Retrival Dokumen Teks
2.2
Tahap-Tahap Kategorisasi Teks Dalam pengaplikasian kategorisasi dokumen teks terdapat beberapa tahap, yaitu : pemrosesan awal, fase pelatihan dan fase kategorisasi dan retrival dokumen teks.
2.2.1 Pemrosesan Awal Langkah pertama dari kategorisasi dokumen teks adalah serangkaian dari proses untuk mengubah dokumen teks, yang awalnya berupa kalimat-kalimat, menjadi vektor yang sesuai dengan algoritma yang digunakan.
16
2.2.1.1
Tokenisasi Tokenisasi adalah sebuah proses untuk memilah isi dokumen teks sehingga menjadi
satuan kata-kata. M enurut Weiss et al. (2005), proses ini cukup rumit untuk sebuah program komputer karena beberapa karakter dapat dijadikan sebagai pembatas (delimiter) dari token-token itu sendiri. Pembatas dari token tersebut antara lain spasi, tab, dan baris baru, sedangkan karakter ( ) < > ! ? ” . , terkadang dianggap sebagai pembatas dan juga bukan pembatas tergantung pada kondisi pemakaiannya. Pemilahan ini biasanya dilakukan dengan cara memisahkan kalimat menjadi katakata dan menghilangkan kata-kata yang bukan merupakan alfabet dan angka. Semua huruf kapital diubah menjadi huruf kecil agar token dapat diurutkan secara alfabet dan diperlakukan sama dengan token-token lain.
2.2.1.1.1
Penapisan (Filtering) Tahap penapisan adalah tahap mengambil kata-kata penting dari hasil token.
Biasanya dilakukan dengan cara menghilangkan stopwords dan stoplist dari token yang telah diperoleh dari proses tokenisasi. M enurut Talla (2002, p21), stopword adalah daftar kata-kata yang tidak dipakai didalam pemrosesan bahasa alami. Hasil penelitian sebelumnya menyatakan bahwa penggunaan stopword meningkatkan kemampuan pemrosesan bahasa alami. M enurut Soumen (2003,p48), kebanyakan bahasa resmi di berbagai negara memiliki kata fungsi dan kata sambung seperti artikel dan preposisi yang hampir selalu muncul pada dokumen teks. Biasanya kata-kata ini tidak memiliki arti yang lebih di
17
dalam memenuhi kebutuhan seorang pengguna di dalam mencari informasi. Kata-kata tersebut (misalnya a, an, the on pada Bahasa Inggris) disebut sebagai Stopwords. Sebuah sistem Text Retrieval biasanya disertai dengan sebuah Stoplist. Stoplist berisi sekumpulan kata yang 'tidak relevan', namun sering sekali muncul dalam sebuah dokumen teks. Stopwords removal adalah sebuah proses untuk menghilangkan kata yang 'tidak relevan' pada hasil parsing sebuah dokumen teks dengan cara membandingkannya dengan stopword dan stoplist yang ada.
2.2.1.2
Stemming M enurut Talla (2003, p7), Stemming merupakan suatu proses untuk menemukan
kata dasar dari sebuah kata. Dengan menghilangkan semua imbuhan (affixes) baik yang terdiri dari awalan (prefixes), sisipan (infixes), akhiran (suffixes) dan confixes (kombinasi dari awalan dan akhiran) pada kata turunan. Stemming digunakan untuk mengganti bentuk dari suatu kata menjadi kata dasar dari kata tersebut yang sesuai dengan struktur morfologi Bahasa Indonesia yang baik dan benar. Imbuhan (affixes) pada Bahasa Indonesia lebih kompleks bila dibandingkan dengan imbuhan (affixes) pada Bahasa Inggris. Karena seperti yang telah disebutkan di atas bahwa imbuhan (affixes) pada Bahasa Indonesia terdiri dari awalan (prefixes), sisipan (infixes), akhiran (suffixes), bentuk perulangan (repeated forms) dan confixes (kombinasi dari awalan dan akhiran). Imbuhan-imbuhan yang melekat pada suatu kata harus dihilangkan untuk mengubah bentuk kata tersebut menjadi bentuk kata dasarnya.
18
Stemming teks berbahasa Indonesia memiliki beberapa masalah yang sangat khusus terhadap bahasa. Salah satu masalah tersebut adalah perbedaan tipe dari imbuhanimbuhan (affixes), yang lain adalah bahwa awalan (prefixes) dapat berubah tergantung dari huruf pertama pada kata dasar. Sebagai contoh ”me-” dapat berubah menjadi ”mem” ketika huruf pertama dari kata dasar tersebut adalah ”b”, misalnya ”membuat” (to make), tetapi ”me-” juga dapat berubah menjadi ”meny-” ketika huruf pertama dari kata dasar melekat adalah ”s”, misalnya ”menyapu” (to sweep). Selanjutnya ketika ada lebih dari satu imbuhan (affixes) yang melekat pada suatu kata, maka urutan untuk menghilangkan imbuhan-imbuhan (affixes) pada kata tersebut menjadi sangat penting. Jika dalam proses meghilangkan imbuhan-imbuhan (affixes) tersebut kita tidak memperhatikan urutan penghilangan imbuhan-imbuhan (affixes) tersebut, maka kata dasar yang benar dari kata tersebut tidak akan ditemukan. Sebagai contoh pada kata ”diberi-kan” (to be given) yang diturunkan dari kata dasar ”beri” (to give). Jika kita menghilangkan akhiran (suffixes) ”kan” terlebih dahulu sebelum menghilangkan awalan (prefix) ”di-” maka pada proses stemming ini kita mendapatkan kata dasar yang benar yaitu ”beri” (to give), akan tetapi jika algoritma stemming mencoba untuk menghilangkan awalan (prefixes) terlebih dahulu sebelum akhiran (suffixes) maka hasil kata dasar yang dihasilkan dari proses stemming dengan menggunakan algoritma tersebut adalah ”ikan” (fish) (setelah menghilangkan awalan ”di” dan ”ber”) dimana ”ikan” merupakan kata dasar yang valid yang terdapat dalam kamus tetapi ”ikan” bukan merupakan kata dasar yang benar untuk kata turunan ”diberikan”.
19
Penilitian terhadap stemming untuk text retrieval, machine translation, document summarization dan text classification sudah pernah dilakukan sebelumnya. Untuk stemming yang dilakukan pada Text Retrieval, stemming ini meningkatkan kesensitivan retrival dengan meningkatkan kemampuan untuk menemukan dokumen teks yang relevan,
tetapi hal itu
terkait
dengan
pengurangan
pada pemilihan
dimana
pengelompokkan menjadi kata dasar menyebabkan penghilangan makna kata. Pada text retrieval, stemming diharapkan dapat meningkatkan recall, tetapi memungkinkan untuk menurunkan precision.
2.2.1.2.1 Imbuhan (afiks) Imbuhan (afiks) adalah suatu bentuk linguistik yang di dalam suatu kata merupakan unsur langsung, yang bukan kata dan bukan pokok kata. M elainkan mengubah leksem menjadi kata kompleks, artinya mengubah leksem itu menjadi kata yang mempunyai arti lebih lengkap, seperti mempunyai subjek, predikat dan objek. Sedangkan prosesnya sendiri di sebut afiksasi (affixation). Kata afiks itu merupakan bentuk terikat, tidak dapat berdiri sendiri dan secara gramatis (tertulis) selalu melekat pada bentuk lain. a)
Awalan (prefiks) Prefiks disebut juga awalan. Prefiks adalah afiks (imbuhan) yang ditempatkan di bagian muka suatu kata dasar Alwi et al. (1998, pp31-32). Istilah ini berasal dari bahasa Latin praefixus yang berarti melekat (fixus, figere) sebelum sesuatu (prae).
20
Berikut merupakan kegunaan dari setiap prefiks : 1.
berM enambah prefiks ini membentuk verba (kata kerja) yang sering kali mengandung arti (makna) mempunyai atau memiliki sesuatu. Juga dapat menunjukkan keadaan atau kondisi atribut tertentu. Penggunaan prefiks ini lebih aktif berarti mempergunakan atau mengerjakan sesuatu. Fungsi utama prefiks "ber-" adalah untuk menunjukkan bahwa subyek kalimat merupakan orang atau sesuatu yang mengalami perbuatan dalam kalimat itu. Sekitar satu dari tiap 44 kata yang tertulis dalam Bahasa Indonesia memiliki prefiks ini. Contoh : bekerja, berlari, bersabar, bergembira.
2. me-, meng-, menge-, meny, memM enambah salah satu dari prefiks ini membentuk verba yang sering kali menunjukkan tindakan aktif di mana fokus utama dalam kalimat adalah pelaku, bukan tindakan atau obyek tindakan itu. Jenis prefiks ini sering kali mempunyai arti mengerjakan, menghasilkan, melakukan atau menjadi sesuatu. Prefiks ini yang paling umum digunakan dan sekitar satu dari tiap 13 kata yang tertulis dalam Bahasa Indonesia memiliki salah satu dari prefiks ini. Contoh : menetap, menghilang, mendarat, menjamu. 3. diPrefiks ini mempunyai pertalian yang sangat erat dengan prefiks "me-." Prefiks "me-" menunjukkan tindakan aktif sedangkan prefiks "di-" menunjukkan tindakan
21
pasif, di mana tindakan atau obyek tindakan adalah fokus utama dalam kalimat itu, dan bukan pelaku. Contoh : digergaji, dipotong, didesain, dihukum. 4. pePrefiks ini membentuk nomina yang menunjukkan orang atau agen yang melakukan perbuatan dalam kalimat. Kata dengan prefiks ini juga bisa memiliki makna alat yang dipakai untuk melakukan perbuatan yang tersebut pada kata dasarnya. Apabila kata dasarnya berupa kata sifat, maka kata yang dibentuk dengan prefiks ini memiliki sifat atau karakteristik kata dasarnya. Sekitar satu dari tiap 110 kata yang tertulis dalam Bahasa Indonesia memiliki prefiks ini. Contoh : perawat, peramal, pelindung, petani. 5. terSekitar satu dari tiap 54 kata yang tertulis dalam Bahasa Indonesia memiliki prefiks ini. Penambahan afiks ini menimbulkan dua kemungkinan:
‐
Jika menambahkan ke kata dasar adjektif, biasanya menghasilkan adjektif yang menyatakan tingkat atau kondisi paling tinggi (ekstrim) atau superlatif. (misalnya: paling besar, paling tinggi, paling baru, paling murah)
‐
Jika menambahkan ke kata dasar yang bukan adjektif, umumnya menghasilkan verba yang menyatakan aspek perfektif, yaitu suatu perbuatan yang telah selesai dikerjakan. Afiks ini juga bisa menunjukkan perbuatan spontanitas, yaitu suatu perbuatan yang terjadi secara tiba-tiba atau tidak
22
disengaja (misalnya aksi oleh pelaku yang tidak disebutkan, pelaku tidak mendapat perhatian atau tindakan natural). Fokus dalam kalimat adalah kondisi resultan tindakan itu dan tidak memfokuskan pada pelaku perbuatan atau bagaimana kondisi resultan itu tercapai. Contoh : terbatas, terkunci, tersenyum, terputus. 6. seM enambah prefiks ini dapat menghasilkan beberapa jenis kata. Prefiks ini sering dianggap sebagai pengganti “satu” dalam situasi tertentu. Sekitar satu dari tiap 42 kata yang tertulis dalam Bahasa Indonesia memiliki prefiks ini. Penggunaan paling umum dari prefiks ini adalah sebagai berikut: ‐
untuk menyatakan satu benda, satuan atau kesatuan
‐
untuk menyatakan seluruh atau segenap
‐
untuk menyatakan keseragaman, kesamaan atau kemiripan
‐
untuk menyatakan tindakan dalam waktu yang sama atau menyatakan sesuatu yang berhubungan dengan waktu
Contoh : semangkuk, sekota, seribu, seindah.
23
b)
Akhiran (Sufiks) Sufiks atau akhiran adalah afiks yang digunakan di bagian belakang kata Alwi et al. (1998, pp33-34). Istilah ini juga berasal dari bahasa Latin suffixus yang berarti melekat (fixus, figere) di bawah. Berikut merupakan kegunaan dari setiap sufiks : 1. -an M enambah sufiks ini biasanya menghasilkan kata benda yang menunjukkan hasil suatu perbuatan. Sufiks ini pun dapat menunjukkan tempat, alat, instrumen, pesawat, dan sebagainya. Contoh : pakaian, pandangan, rakitan, aturan. 2. -i M enambah sufiks ini akan menghasilkan verba yang menunjukkan perulangan, pemberian sesuatu atau menyebabkan sesuatu. Sufiks ini sering digunakan untuk memindahkan perbuatan kepada suatu tempat atau obyek tak langsung dalam kalimat yang mana tetap dan tidak mendapat pengaruh dari perbuatan tersebut. Sufiks ini pun menunjukkan di mana dan kepada siapa tindakan itu ditujukan. Sekitar satu dari tiap 70 kata yang tertulis dalam Bahasa Indonesia memiliki sufiks ini. Contoh : resapi, alami, islami, lingkari.
24
3. –kan M enambah sufiks ini akan menghasilkan kata kerja yang menunjukkan penyebab, proses pembuatan atau timbulnya suatu kejadian. Fungsi utamanya yaitu untuk memindahkan perbuatan verba ke bagian lain dalam kalimat. Sekitar satu dari tiap 20 kata yang tertulis dalam Bahasa Indonesia memiliki sufiks ini. Contoh : kerjakan, palingkan, paparkan, hilangkan. 4. -kah M enambah sufiks ini menunjukkan bahwa sebuah ucapan merupakan pertanyaan dan sufiks ini ditambahkan kepada kata yang merupakan fokus pertanyaan dalam kalimat. Sufiks ini jarang digunakan. Contoh : siapakah, kapankah, diakah, dimanakah. 5. -lah Sufiks ini memiliki penggunaan yang berbeda dan membingungkan, tetapi secara singkat dapat dikatakan bahwa sufiks ini sering digunakan untuk memperhalus perintah, untuk menunjukkan kesopanan atau menekankan ekspresi. Hanya sekitar satu dari tiap 400 kata yang tertulis dalam Bahasa Indonesia memiliki sufiks ini. Contoh : pakailah, buanglah, akulah, masuklah.
25
6. -nya, -ku, -mu Satuan-satuan ini bukan merupakan afiks murni dan semuanya tidak dimasukkan sebagai entri dalam kamus ini. Pada umumnya satuan-satuan ini dianggap sebagai kata ganti yang menyatakan kepemilikan yang digabungkan dengan kata dasar yang mana tidak mengubah arti kata dasar. Selain sebagai kata ganti yang menyatakan kepemilikan, satuan “-nya” pun dapat memiliki fungsi untuk menunjukkan sesuatu. Penggunaan “-nya” baik sebagai kata ganti maupun penunjuk (bukan sebagai sufiks murni) adalah sangat umum dan sekitar satu dari tiap 14 kata tertulis dalam Bahasa Indonesia memiliki satuan ini. Penggunaan “ku” dan “-mu” bervariasi sesuai dengan jenis tulisan. Dua jenis kata ganti ini sangat umum digunakan dalam komik, cerpen dan tulisan tidak resmi lainnya, dan jarang digunakan dalam tulisan yang lebih formal seperti surat kabar dan majalah berita. Contoh : bukunya, pensilku, ibumu, kartunya.
2.2.1.2.2 Algoritma Porter Algoritma Porter dibuat oleh M artin Porter dan pertama kali dipublikasikan pada tahun 1980. Algoritma ini merupakan algoritma pembuangan sufiks yang context sensitive, terdiri dari lima langkah linear untuk menghasilkan stem akhir. M enurut Talla (2003, p13), langkah-langkah dari penerapan algoritma Porter untuk Bahasa Indonesia adalah sebagai berikut :
26
Gambar 2.2 Algoritma Porter untuk Bahasa Indonesia
2.2.2
Tahap Pelatihan Tahap kedua dari text categorization adalah tahap pelatihan (training). Pada tahap ini sistem akan membangun model yang berfungsi untuk menentukan kelas dari dokumen yang belum diketahui kelasnya. Tahap ini menggunakan data yang telah diketahui kelasnya (data training) yang kemudian akan dibentuk model yang direpresantasikan melalui vektor dari tiap dokumen. Data training disini digunakan sebagai patokan untuk menentukan kata-kata kunci dari tiap kategori. M enurut Sebastiani (2000, p11), data training adalah sekumpulan dokumen contoh yang diobservasi untuk didapatkan karakteristiknya demi mempermudah classifier untuk menentukan kategori.
27
2.2.3 Tahap Kategorisasi dan Retrival Dokumen Teks Tahap terakhir adalah tahap pengujian kategorisasi yang akan memberikan kelas pada data testing dengan menggunakan model yang telah dibangun pada tahap training dan retrival dengan mengambil data relevan terhadap kueri yang dimasukkan. Proses ini dilakukan dengan menggunakan metode classifier yang telah ditentukan. Tujuan dilakukan testing adalah untuk mengetahui performansi dari model yang telah dibentuk dengan menggunakan sekumpulan data test. Dengan beberapa parameter pengukuran untuk mengetahui keakuratannya yaitu precision dan recall.
2.2.3.1
Evaluasi Salah satu penerapan prinsip relevansi yang sejak dahulu digunakan dalam
pengembangan sistem retrival informasi adalah penggunaan ukuran recall and precis ion. Sejak teori tentang retrival informasi berkembang di tahun 1940an, para ilmuan selalu memeras otak, bagaimana caranya membuat sistem retrival informasi yang benar-benar handal. Recall and precision adalah upaya untuk mengukur keefektifan sebuah sistem retrival informasi dalam memenuhi permintaan informasi dan mengukur kemampuan sistem dalam menyediakan dokumen yang relevan dengan kebutuhan pemakai. Terjemahan yang pas untuk istilah ini dalam Bahasa Indonesia belum ditemukan. Istilah recall digunakan pula dalam psikologi untuk menjelaskan proses mengingat yang dikerjakan otak manusia. Kata lain untuk recall dalam Bahasa Inggris adalah remember, recollect, remind. Di bidang IR, recall berkaitan dengan kemampuan menemukan-kembali
28
butir informasi yang sudah tersimpan. Jadi, terjemahan bebasnya mungkin adalah “penemuan-kembali”. Precision dapat diartikan sebagai kepersisan atau kecocokan (antara permintaan informasi dengan jawaban terhadap permintaan itu). Jika seseorang mencari informasi di sebuah sistem, dan sistem menawarkan beberapa dokumen, maka kepersisan ini sebenarnya juga adalah relevansi. Artinya, seberapa persis atau cocok dokumen tersebut untuk keperluan pencari informasi, bergantung pada seberapa relevan dokumen tersebut bagi si pencari. Recall adalah proporsi jumlah dokumen yang dapat ditemukan-kembali oleh sebuah proses pencarian di sistem IR. Rumusnya: Jumlah dokumen relevan yang ditemukan / Jumlah semua dokumen relevan di dalam koleksi. Lalu, precision adalah proporsi jumlah dokumen yang ditemukan dan dianggap relevan untuk kebutuhan si pencari informas i. Rumusnya: Jumlah dokumen relevan yang ditemukan / Jumlah semua dokumen yang ditemukan. M enurut Rijsbergen (1979, p115), rumus dari recall dan precision adalah sebagai berikut : Precision = | A ∩ B | / |B| …… (2.1) Recall = | A ∩ B | / |A| …… (2.2) Dimana A adalah dokumen yang relevan dan B adalah dokumen yang ditemukan.
29
Dengan kata lain, untuk menghitung recall dan precision-nya dapat digunakan rumus sebagai berikut : Tabel 2.1 TP,TN,FN,FP
obtained result / classification
E1 E2
correct result / classification E1 E2 tp fp (true positive) (false positive) fn tn (false negative) (true negative)
….. (2.3)
……(2.4) dimana 1. 2. 3. 4.
TN / True Negative: dokumen salah dan diprediksikan salah TP / True Positive: dokumen benar dan diprediksikan benar FN / False Negative: dokumen benar dan diprediksikan salah FP / False Positive: dokumen salah dan diprediksikan benar M enurut Asian (2007, pp 43-44), untuk precision, terdapat beberapa jenis yang dapat
digunakan. perbedaan dari tiap precision adalah pada hasil dokumen yang diretrievenya. Berikut adalah macam-macam precision yang ada :
a.
Precision@n Precision ini mengambil dokumen yang diretrieve sebanyak n, dan menghitung precision berdasarkan n dokumen yang diambil tersebut. M isalnya sebuah kueri
30
menghasilkan 20 dokumen hasil, apabila menggunakan precision@10, maka precision yang dihitung hanyalah berdasarkan 10 dokumen peringkat tertinggi. b.
R-Precision R-precision mengambil dokumen yang diretrieve berdasarkan jumlah dokumen relevan yang ada. Apabila dokumen relevan yang ada sebanyak 20 buah, maka perhitungan precision ini akan mengambil 20 dokumen peringkat tertinggi. Dalam hal ini sama hasilnya seperti precision@20.
c.
Mean Average Precision (M AP) M etode perhitungan precision ini mengambil dokumen yang diretrieve sampai semua dokumen relevan telah ditemukan. M isalnya dokumen relevan paling akhir ditemukan di peringkat 20, maka perhitungan M AP ini akan menggunakan 20 dokumen tersebut. Apabila tidak ada dokumen relevan pada hasil dokumen yang diretrieve, maka nilai M AP nya adalah 0.
2.3
Metode-Metode Adapun metode-metode yang telah digunakan oleh berbagai kalangan untuk melakukan kategorisasi dan retrival dokumen teks adalah sebagai berikut :
2.3.1
Pendekatan Machine Learning pada Kategorisasi dan Retrival Dokumen Teks M enurut Sebastiani (2000, p10), pada tahun 1980-an, pendekatan utama yang
digunakan pada realisasi dari pengklasifikasi dokumen otomatis terdapat dalam instrukasi manual melalui teknik knowledge-engineering, contoh : membangun sistem pakar secara manual yang mampu mengambil keputusan kategorisasi. Sistem pakar seperti itu
31
biasanya terdiri dari satu set peraturan yang ditentukan secara manual dari tipe if
, then . Sejak awal 1990-an, sebuah pendekatan baru pada pembuatan pengklasifikasi dokumen secara otomatis ( pendekatan machine learning ) menjadi terkemuka dan dominan. Pada pendekatan ini, sebuah proses induktif yang umum (learner) secara otomatis membangun sebuah classifier untuk sebuah kategori c i dengan mengobservasi karakteristik dari sekumpulan dokumen yang sebelumnya telah diklasifikasikan secara manual di bawah kategori ci. Dari karakterisitik ini, proses induktif mengumpulkan sedikit demi sedikit karakteristik yang harus dimiliki oleh sebuah dokumen agar dapat diklasifikasikan ke dalam kategori tersebut. Dalam terminologi machine learning, masalah klasifikasi adalah sebuah aktivitas dari supervised learning, karena proses pembelajaran tersebut dikontrol dan diawasi. Dalam hal efektivitas, classifier yang dibangun dengan menggunakan teknik machine learning mencapai tingkap performa yang cukup tinggi, membuat klasifikasi otomatis adalah alternatif yang dapat dijalankan daripada klasifikasi manual.
2.3.1.1 Support Vector Machine Konsep dasar SVM sebenarnya merupakan kombinasi harmonis dari teori-teori komputasi yang telah ada puluhan tahun sebelumnya, seperti margin hyperplane (Duda & Hart, 1973), kernel diperkenalkan oleh Aronszajn tahun 1950, dan demikian juga dengan konsep-konsep pendukung yang lain. Akan tetapi hingga tahun 1992, belum pernah ada upaya merangkaikan komponen-komponen tersebut.
32
Berbeda dengan strategi neural network yang berusaha mencari hyperplane pemisah antar class, SVM berusaha menemukan hyperplane yang terbaik pada input space. Prinsip dasar SVM adalah linear classifier, dan selanjutnya dikembangkan agar dapat bekerja pada problem non-linear. Dengan memasukkan konsep kernel trick pada ruang kerja berdimensi tinggi. Perkembangan ini memberikan rangsangan minat penelitian di bidang pattern recognition untuk investigasi potensi kemampuan SVM secara teoritis maupun dari segi aplikasi. Dewasa ini SVM telah berhasil diaplikasikan dalam problema dunia nyata (real-world problems), dan secara umum memberikan solusi yang lebih baik dibandingkan metode konvensional seperti misalnya artificial neural network. M enurut Drs. M ahmudin, SIP (2005), salah satu metode Text Categorization dalam menentukan classifier adalah Support Vector Machine (SVM ). M etode SVM membentuk fungsi keputusan dari feature-feature dalam koleksi dokumen dengan menggunakan prinsip structural risk minimization dari teori statistika diterapkan pembelajaran mesin (machine learning). Secara interpretasi geometri, SVM adalah pencarian bidang pemisah pada bidang banyak (hyperplane) yang memisahkan kelompok feature-feature. Pembangunan fungsi keputusan melalui training data. Fungsi keputusan dari pembelajaran ini yang akan digunakan untuk menentukan kategori dokumen secara otomatis.
33
Gambar 2.3 M aksimum M argin Hyperlane dengan M enggunakan SVM untuk 2 Kelas Karakteristik SVM dirangkumkan sebagai berikut: 1.
Secara prinsip SVM adalah linear classifier.
2.
Pattern recognition dilakukan dengan mentransformasikan data pada input space ke ruang yang berdimensi lebih tinggi, dan optimisasi dilakukan pada ruang vektor yang baru tersebut. Hal ini membedakan SVM dari solusi pattern recognition pada umumnya, yang melakukan optimisasi parameter pada ruang hasil transformasi yang berdimensi lebih rendah daripada dimensi input space.
2.3.2
3.
M enerapkan strategi Structural Risk Minimization (SRM )
4.
Prinsip kerja SVM pada dasarnya hanya mampu menangani klasifikasi dua class.
Naïve Bayes M enurut Destuardi dan Surya Sumpeno (2009,p3), klasifikasi–klasifikasi Bayes adalah klasifikasi statistik yang dapat memprediksi kelas suatu anggota probabilitas. Untuk klasifikasi Bayes sederhana yang lebih dikenal sebagai Naïve Bayesian Classifier dapat diasumsikan bahwa efek dari suatu nilai atribut sebuah kelas yang diberikan adalah
34
bebas dari atribut-atribut lain. Asumsi ini disebut class conditional independence yang dibuat untuk memudahkan perhitungan-perhitungan pengertian ini dianggap “naive”, dalam bahasa lebih sederhana naïve itu mengasumsikan bahwa kemunculan suatu term kata dalam suatu kalimat tidak dipengaruhi kemungkinan kata-kata yang lain dalam kalimat padahal dalam kenyataanya bahwa kemungkinan kata dalam kalimat sangat dipengaruhi kemungkinan keberadaan kata-kata yang dalam kalimat. Dalam Naïve Bayes di asumsikan prediksi atribut adalah tidak tergantung pada kelas atau tidak dipengaruhi atribut laten. M enurut Errival Ahmad (2009), pendekatan Bayes pada saat klasifikasi adalah mencari probabilitas tertinggi (VMAP ) dengan masukan atribut (a1, a2, a3, …, an). arg max
,
,
,…,
…… (2.5)
Teorema Bayes sendiri berawal dari rumus :
|
…… (2.6)
dimana P(A | B) artinya peluang A jika diketahui keadaan B. Kemudian dari persamaan rumus diatas kita mendapatkan bahwa : |
…… (2.7)
sehingga didapatkan teorema Bayes :
|
|
…… (2.8)
35
M enggunakan teorema Bayes ini, persamaan diatas akan dapat ditulis menjadi: ,
arg max
,
,…, ,
,
…… (2.9)
,…,
Karena nilai P(a1, a2, a3, …, an) konstan untuk semua vj , maka persamaan ini dapat ditulis menjadi: arg max
,
,
…… (2.10)
,…,
Untuk menghitung P(a1, a2, a3, …, an | vj ) bisa jadi semakin sulit karena jumlah term P(a1, a2, a3, …, an | vj ) bisa jadi sangat besar. Hal ini disebabkan jumlah term tersebut sama dengan jumlah semua kombinasi posisi kata dikali dengan jumlah kategori yang ada. Naïve Bayesian Classifier menyederhanakan hal ini dengan asumsi bahwa fitur-fitur yang terdapat didalamnya saling tidak tergantung atau independen, setiap kata independen satu sama lain. Dengan kata lain: ,
Dengan
,
∏
,…,
|
…… (2.11)
men-substitusikan persamaan ini dengan persamaan diatas akan
menghasilkan: arg max
∏
|
…… (2.12)
P(vj ) dapat diartikan peluang sms kategori j. Dapat ditulis seperti:
36
dimana |smsj | adalah jumlah kata pada kategori j dan |tot_sms| adalah jumlah sms yang digunakan dalam pelatihan. Sedangkan P(ai|vj ) adalah peluang a i jika diketahui keadaan vj , dalam artian, peluang kata ke i, dalam sms kategori j. Dapat ditulis seperti ini: |
…… (2.13)
_
|
dimana ni adalah jumlah kemunculan kata ai pada kategori vj . Dan |kata_ vj | adalah jumlah kata yang ada pada kategori vj . _
…… (2.14)
2.3.3 Rocchio M enurut Santini (2001, pp361-362), salah satu algoritma yang paling sukses untuk pencarian umpan balik relevansi. Algoritma Rocchio pertama kali diterbitkan pada tahun 1965, dan kemudian ditulis ulang pada tahun 1971. Algoritma ini memiliki interpretasi sederhana di dalam vector space model. Seperti yang telah disebutkan sebelumnya, sebuah kueri Q dapat direpresentasikan sebagai sebuah dokumen, sebagai sebuah vektor di dalam space, ∑ Dimana
…… (2.15)
adalah term relevansi dari T1 untuk kueri.
Ketika jawaban kueri dipresentasikan, pengguna akan memilih beberapa dokumen yang relevan
dan sebuah himpunan dokumen
yang tidak
relevan,
keduanya
direpresentasikan sebagai vektor di dalam space. Efek dari umpan balik relevans i diilustrasikan seperti gambar berikut. Dimana hanya dokumen yang relevan yang dipilih,
37
titik kueri bergerak lebih dekat ke arah pusat dari dokumen yang dianggap relevan. Kueri baru akan mengungkap beberapa dokumen baru yang diharapkan akan lebih relevan terhadap topik yang dipikirkan oleh pengguna daripada yang ada di kueri.
Gambar 2.4 Ilustrasi Skematik dari Efek Umpan Balik Relevansi Jadikan {r1,…,rp}
{1,…,N} sebagai indeks dari dokumen yang dipilih pengguna
sebagai dokumen yang relevan, dan jadikan R = {
,k= 1,…,p} sebagai himpunan
korespondensi dari himpunan dokumen relevan. Dengan cara yang sama jadikan {s1,…,sq} {1,…,N} sebagai indeks dari dokumen yang dipilih pengguna sebagai dokumen yang , k = 1,…,p} sebagai himpunan korespondensi dari
tidak relevan, dan jadikan S = {
himpunan dokumen tidak relevan. Secara formal algoritma Rocchio melakukan penggantian untuk yang kedua kali terhadap kueri Q dengan kueri Q1 yang telah dimodifikasi, di definisikan sebagai ∑
∑
…… (2.16)
38
Dimana β,γ > 0 adalah dua bobot konstanta yang menentukan kekuatan aksi dari umpan balik. Hasil yang terbaik, didapatkan dengan γ = 0,25 dan β = 0,75. Penulisan : ∑
∑
,
,
…… (2.17)
Kueri baru dapat ditulis sebagai vektor ∑
∑
∑
,
…… (2.18)
,
Hasil ini di dalam skema pembobotan kembali, dimana bobot dari term kueri yang awalnya merupakan
di dalam
diberi nilai ∑
∑
,
,
…… (2.19)
di dalam kueri baru. Beberapa variasi dari strategi Rocchio telah dianalisa oleh Ide (1971). Yang pertama sama dengan formula yang dibuat oleh Rocchio, tanpa normalisasi ∑
∑
…… (2.20)
yang kedua hanya diperbolehkan umpan balik yang positif : ∑
…… (2.21)
39
2.3.4 Decision Tree (Pohon Keputusan) M enurut Linoff et al. (2004), Sebuah pohon keputusan adalah sebuah struktur yang dapat digunakan untuk membagi kumpulan data yang besar menjadi himpunan-himpunan record yang lebih kecil dengan menerapkan serangkaian aturan keputusan. Dengan masing-masing rangkaian pembagian, anggota himpunan hasil menjadi mirip satu dengan yang lain. Decision Tree adalah sebuah struktur pohon, dimana setiap node pohon merepresentasikan atribut yang telah diuji, setiap cabang merupakan suatu pembagian hasil uji, dan node daun (leaf) merepresentasikan kelompok kelas tertentu. Level node teratas dari sebuah Decision Tree adalah node akar (root) yang biasanya berupa atribut yang paling memiliki pengaruh terbesar pada suatu kelas tertentu. Pada umumnya Decision Tree melakukan strategi pencarian secara top-down untuk solusinya. Pada proses mengklasifikasi data yang tidak diketahui, nilai atribut akan diuji dengan cara melacak jalur dari node akar (root) sampai node akhir (daun) dan kemudian akan diprediksi kelas yang dimiliki oleh suatu data baru tertentu. Sebuah model pohon keputusan terdiri dari sekumpulan aturan untuk membagi sejumlah populasi yang heterogen menjadi lebih kecil, lebih homogen dengan memperhatikan pada variabel tujuannya. Sebuah pohon keputusan mungkin dibangun dengan seksama secara manual, atau dapat tumbuh secara otomatis dengan menerapkan salah satu atau beberapa algoritma pohon keputusan untuk memodelkan himpunan data yang belum terklasifikasi. Variabel tujuan biasanya dikelompokkan dengan pasti dan model pohon keputusan lebih mengarah pada perhitungan probabilitas dari masing-mas ing record terhadap kategori-kategori tersebut, atau untuk mengklasifikasi record dengan mengelompokkannya dalam satu kelas.
40
Gambar 2.5 Contoh Pohon Keputusan Keterangan : C(t) - subset of classes accessible from node t F(t) - feature subset used at node t D(t) - decision rule used at node t M enurut Larose (2005,p116), banyak algotima yang dapat dipakai dalam pembentukan pohon keputusan antara lain ID3, CART dan C4.5.
2.3.4.1 Algoritma Iterative Dichotomiser 3 (ID3) M enurut Ramadan (2006, p3), metode pohon, yang selanjutnya disebut dengan, Iterative Dichotomiser 3 (ID3) merupakan sebuah metode yang digunakan untuk membangkitkan pohon keputusan. ID3 diperkenalkan pertama kali oleh Quinlan (1979). Kemampuan metode ini untuk menghasilkan aturan-aturan pengklasifikasi konsep secara otomatis menarik perhatian beberapa peneliti untuk melakukan penelitian mengenai potensi aplikasi metode ini.
Namun sejauh ini aplikasi ID3 secara luas masih belum
41
banyak dikenal baik di kalangan peneliti di luar negeri maupun di Indonesia. Hal ini disebabkan karena acuan-acuan mengenai ID3 sangat sulit ditemukan dan hanya terbatas pada jurnal-jurnal ilmiah tertentu. Tambahan lagi keterbatasan-keterbatasan metode ID3 yang asli yang diperkernalkan oleh Quinlan (1979), seperti keterbatasan dalam representasi ordered outcome, cukup menciutkan banyak peneliti untuk melakukan eksplorasi lebih lanjut dari metode ini pada bidang-bidang lain. Algoritma pada metode ini berbasis pada Occam’s razor: lebih memilih pohon keputusan yang lebih kecil (teori sederhana) dibanding yang lebih besar. Tetapi tidak dapat selalu menghasilkan pohon keputusan yang paling kecil dan karena itu Occam’s Razor bersifat heuristik. Occam’s razor diformalisasi menggunakan konsep dari entropi informasi. Secara ringkas, cara kerja Algoritma ID3 dapat digambarkan sebagai berikut: 1.
Ambil semua atribut yang tidak terpakai dan hitung entropinya yang berhubungan dengan test sample.
2.
Pilih atribut dimana nilai entropinya minimum.
3.
Buat simpul yang berisi atribut tersebut. Adapun sample data yang digunakan oleh ID3 memiliki beberapa syarat, yaitu:
1.
Deskripsi atribut-nilai. Atribut yang sama harus mendeskripsikan tiap contoh dan memiliki jumlah nilai yang sudah ditentukan.
2.
Kelas yang sudah didefinisikan sebelumnya. Suatu atribut contoh harus sudah didefinisikan, karena mereka tidak dipelajari oleh ID3.
42
3.
Kelas-kelas yang diskrit. Kelas harus digambarkan dengan jelas. Kelas yang kontinyu dipecah-pecah menjadi kategori-kategori yang relatif, misalnya saja metal dikategorikan menjadi “hard, quite hard, flexible, soft, quite soft”.
4. Jumlah contoh (example) yang cukup. Karena pembangkitan induktif digunakan, maka dibutuhkan test case yang cukup untuk membedakan pola yang valid dari peluang suatu kejadian. Pemillihan atribut pada ID3 dilakukan dengan properti statistik, yang disebut dengan information gain. Gain mengukur seberapa baik suatu atribut memisahkan training example ke dalam kelas target. Atribut dengan informasi tertinggi akan dipilih. Dengan tujuan untuk mendefinisikan gain, pertama-tama digunakanlah ide dari teori informasi yang disebut entropi. Entropi mengukur jumlah dari informasi yang ada pada atribut. Rumus menghitung entropi informasi adalah: Entropy(S) ≡ – p log p – p log p …… (2.22) + 2 + 2 Dan rumus untuk menghitung gain adalah: Gain(S,A)≡ Entropy(S) – (Σ (|Sv| / |S| )) Entropy(Sv) …… (2.23)
2.3.4.2 Algoritma C4.5 M enurut Larose (2005, p116), algoritma C4.5 merupakan pengembangan dari algoritma ID3. Algoritma C4.5 mengkonstruksi pohon keputusan dari sebuah set data training, yang berupa kasus-kasus atau record-record (tupel) dalam basis data, dimana tiap record memiliki atribut kontinyu atau diskrit atau keduanya.
43
M enurut Ruggieri (2000, p209), tiga prinsip kerja algoritma C4.5 adalah: kontruksi pohon keputusan, pemangkasan pohon keputusan dan evaluasi dan pembuatan aturanaturan dari pohon keputusan. C4.5 mengkonstruksi pohon dengan menerapkan strategi divide and conquer. Pada awalnya, hanya ada akar. Pada setiap simpul berikutnya, Algoritma 1 dieksekusi. Pada algoritma ini, T adalah himpunan kasus. Fungs i ComputeFrequency (langkah 1) digunakan untuk menghitung jumlah kasus pada T yang menjadi anggota kelas Ci, dimana i Є [1, NClass]. Secara umum algoritma C4.5 untuk membangun pohon keputusan adalah sebagai berikut: a. Pilih atribut sebagai root b. Buat cabang untuk masing-masing nilai c. Bagi kasus dalam cabang d. Ulangi proses untuk masing-masing cabang sampai semua kasus pada cabang memiliki kelas yang sama.
2.3.4.3 Algoritma CART CART (Classification and Regression Trees) adalah salah satu metode atau algoritma dari salah satu teknik eksplorasi data yaitu teknik pohon keputusan. M etode ini dikembangkan oleh Leo Breiman, Jerome H. Friedman, Richard A. Olshen dan Charles J. Stone sekitar tahun 1980-an. M enurut Breiman et al. (1993, pp3-4), CART merupakan metodologi statistik nonparametric yang dikembangkan untuk topik analisis klasifikas i, baik untuk peubah respon kategorik maupun kontinyu. CART menghasilkan suatu pohon klasifikasi jika peubah responnya kategorik, dan menghasilkan pohon regresi jika peubah
44
responnya kontinyu. Tujuan utama CART adalah untuk mendapatkan suatu kelompok data yang akurat sebagai penciri dari suatu pengklasifikasian. Bentuk dari CART adalah seperti berikut ini :
Gambar 2.6 Diagram CART Pada Gambar 1 di atas A, B dan C merupakan peubah-peubah penjelas yang terpilih untuk menjadi simpul. A merupakan simpul induk, sementara B dan C merupakan simpul anak dimana C juga merupakan simpul akhir yang tidak bercabang lagi. Sementara α dan β merupakan suatu nilai yang merupakan nilai tengah antara dua nilai amatan peubah xj secara berurutan. Diagram yang dihasilkan oleh CART ini merupakan suatu model, biasanya diinterpretasikan ke dalam suatu tabel untuk penjelasannya. Hal ini berbeda dengan regresi konvensional dimana model regresi dapat dituliskan menjadi model matematik atau persamaan regresinya.
45
2.3.5 K-Nearest Neighbour M enurut Richards dan Jia (2006,pp207-208), salah satu algoritma klasifikasi nonparametrik yang memiliki formulasi statistik paling sederhana dan paling mudah diimplementasikan adalah K-Nearest Neighbour Classifier (KNN Classifier). K-Nearest Neighbour Classifier berasumsi bahwa piksel-piksel yang saling berdekatan satu sama lain (dikenal sebagai piksel-piksel bertetangga) di dalam feature space akan tergolong ke dalam kelas yang sama. Dalam proses klasifikasinya, K-Nearest Neighbour Classifier akan mengukur jarak spektral (spectral distance) setiap piksel yang ada pada citra terhadap piksel-piksel yang berada di bawah daerah sampel. Fungsi diskriminan KNearest Neighbour Classifier sendiri diformulasikan sebagai berikut: …..(2.24) …..(2.25) adalah jarak spektral suatu nilai piksel ke nilai piksel tetangganya. k i menyatakan jumlah piksel sampel pada kelas yang ke i dan …… (2.26) , dan M adalah jumlah kelas.
Gambar 2.7 Ilustrasi K-Nearest Neighbor
46
Seperti algoritma-algoritma machine learning lainnya, K-Nearest Neighbor Classifier dihadapkan pada satu masalah utama, yaitu lamanya waktu proses klasifikasi. Hal ini dikarenakan K-Nearest Neighbour Classifier mengukur jarak spektral setiap piksel ke semua piksel yang ada dalam daerah sampel. Waktu proses klasifikasi akan semakin lama seiring semakin banyaknya jumlah saluran (band), bertambah besarnya ukuran daerah sampel dan bertambahnya jumlah kelas yang akan diklasifikasikan. Seperti yang diungkapkan oleh Richards and Jia (2006,p208) "...that (K-Nearest Neighbour Classifier) requires an impractically high computational load, especially when the number of spectral bands and/or the number of training samples is large". Kemungkinan metode yang dapat dilakukan untuk mengefisiensikan waktu eksekusi K-Nearest Neighbour Classifier adalah dengan memodifikasi algoritma pengukur jarak
spektral pada algoritma ini.
Umumnya K-Nearest Neighbour
Classifier
menggunakan Euclidean Distance sebagai metode pengukur jarak spektral. Akan tetapi, metode pengukur jarak spektral lainnya seperti Manhattan Distance juga dapat digunakan dalam K-Nearest Neighbour Classifier. Manhattan Distance memiliki bentuk formulas i yang lebih sederhana dibandingkan dengan Euclidean Distance. Dilihat dari bentuk persamaan matematisnya, sudah dapat diprediksi bahwa algoritma pengukur jarak spektral ini akan memiliki waktu kalkulasi yang lebih cepat dibanding Euclidean Distance. M eskipun demikian, tentunya akurasi hasil klasifikasinya masih perlu dipertanyakan. Distance Space berfungsi untuk menghitung jarak antara data dan sentroid. Ada beberapa macam distance space yang sudah diimplementasikan diantaranya adalah : Manhattan/City Block distance space dan Euclidean distance space.
47
2.3.5.1 Manhattan/City Block distance space M enurut M iyamoto (1955,pp 422-436), untuk menghitung jarak antara 2 titik misal x1 dan x2 adalah sebagai berikut:
,
∑
…… (2.27)
dimana:
2.3.5.2
p
: dimensi data
|.|
: nilai absolut
Euclidean Distance Space M enurut Bezdek (1981), jarak antara dua titik dapat dihitung dengan cara : ,
∑
…… (2.28)
Dimana: P
: dimensi data
Dalam Euclidean perhitungan yang dilakukan merupakan jarak terpendek antara dua titik, sedangkan pada Manhattan mampu mendeteksi keadaan tertentu seperti keberadaan outliers dengan lebih baik.
2.3.6 Jaringan S araf Tiruan (Artificial Neural Network) Jaringan saraf tiruan adalah sistem pengolah informasi yang mempunyai sifat sebagaimana jaringan saraf biologis. Jaringan saraf tiruan merupakan model tiruan
48
bagaimana mahluk hidup memahami dan mengenali informasi disekitarnya. Sifat-sifat utama dari jarangan saraf tiruan antara lain: mempunyai terminal-terminal input data yang disebut sebagai neuron. Kumpulan input data berbentuk pola yang dianggap cukup mempunyai ciri fenomena atau pun objek yang akan diamati. Neuron pada lapisan input terhubung dengan neuron-neuron lain pada lapisan tersembunyi, hingga lapisan output. Antar neuron saling terhubung, dan terdapat nilai bobot diantara neuron-neuron tersebut. Nilai bobot ditemukan melalui proses pembelajaran, hingga tercapai kesesuaian anatara nilai output hasil olahan dengan nilai yang diinginkan. Algoritma jaringan saraf tiruan banyak digunakan untuk mengatasi masalah-masalah penyimpanan dan pemanggilan data, klasifikasi dan identifikasi pola, pemetaan pola input dan output, pengelompokan pola, hingga pada pencarian nilai-nilai optimasi. Konsep pertama yang harus di pahami sebelum masuk pada tahap coding adalah layer. Jaringan Saraf Tiruan umumnya terdiri dari 3 layer, yaitu input layer, hidden layer, dan output layer. Ketiga layer inilah yang akan membentuk topologi Jaringan Saraf Tiruan. Tiap layer terdiri dari unit-unit node yang jumlahnya dapat kita tentukan sendiri, bisa dibayangkan bahwa tiap node pada Jaringan Saraf Tiruan ibaratnya seperti neuron pada otak manusia. Jumlah node pada input layer tergantung pada jumlah data input yang akan masuk pada sistem, misalnya pada operasi penjumlahan diatas maka jumlah node pada input layer sebanyak 2 buah.
49
Gambar 2.8 Gambaran Umum Jaringan Saraf Tiruan Proses arus informasi dalam sistem JST di atas dimulai dari node-node input. Untuk mencerminkan tingkat kekuatan hubungan ini, digunakan faktor pembobot (weight), sehingga yang diterima oleh node-node di lapisan tersembunyi adalah signal terbobot (weigthed signal ) yaitu xiWj,i dimana Wj,i merupakan besaran bobot hubungan dari node input i menuju node tersembunyi ke-j. Jumlah total signal terbobot yang masuk ke salah satu node atau elemen proses di lapis tersembunyi ini selanjutnya akan dikirim ke nodenode di lapisan output. Tiap neuron menerima signal output dari berbagai neuron lainnya dan mengeluarkan output nya dengan menghitung tingkat (level) aktivitas yang masuk adalah :
Ij =
i =Np
∑ xW i
j, i
…… (2.29)
i= 1
Jika input bersih cukup kuat untuk mengaktifkan node j, maka output dari node tersebut adalah : y j = f (I j ) …… (2.30)
50
Dengan : Np
= jumlah node yang masuk dari lapisan sebelumnya ke node yang dituju
xi
= signal input dari node input ke i=1, 2, ... , Np.
Wj,i
= besarnya bobot node ke i ke node j.
Ij
= total signal bobot bersih yang masuk ke node j
f
= fungsi aktivasi
yj
= signal output node j
2.3.7 Latent Semantic Indexing M enurut Baeza-Yates(1999,pp44-45), Latent Semantic Indexing (LSI) ialah suatu teknik yang memetakan kueri dan dokumen ke dalam suatu ruang yang disebut Latent Semantic Space. Dalam Latent Semantic Space, suatu kueri dan suatu dokumen dapat memiliki nilai kesamaan yang tinggi meskipun kueri dan dokumen tersebut tidak memiliki term yang sama, selama term-term tersebut mirip secara semantik maka nilai kesamaan yang dihasilkan akan tinggi. LSI mengasumsikan bahwa terdapat suatu struktur tersembunyi yaitu struktur semantik yang terdapat dalam term yang terdapat dalam dokumen. Struktur semantik yang dimaksud disini ialah hubungan antara setiap kata yang muncul dalam suatu dokumen. Tujuan dari LSI adalah mendapatkan suatu pemodelan yang efektif untuk merepresentasikan hubungan antara kata kunci dan dokumen yang dicari. Dari
51
sekumpulan kata kunci, yang tadinya tidak lengkap dan tidak sesuai, menjadi sekumpulan objek yang berhubungan. M etode retrival yang sudah berkembang sebelumnya tidak mampu menangani masalah sinonim dan polisemi. Sinonim adalah kata yang berbeda namun memiliki makna yang sama. M isalnya pengguna menggunkan kata yang berbeda untuk mencari objek yang sama, sebagai contoh kata “car” dan “automobile”. Polisemi adalah kata yang sama, namun memiliki makna yang berbeda, sebagai contoh kata “jaguar” bisa bermakna tipe kendaraan atau nama binatang. Latent Semantic Indexing (LSI) adalah model temu kembali yang mampu memecahkan masalah sinomim. Dengan menggunakan Singular Value Decomposition (SVD) dan Eigenvalue pada sebuah term dengan menggunakan matriks bobot term dari dokumen. Dimensi transformasi ruang di-reduce dengan cara memilih nilai singular (singular value). M etode penentuan similarity antara dokumen kueri dan dokumen koleksi pada LSI adalah sama dengan M odel Ruang Vektor, yaitu dengan menghitung nilai cosinus dari vektor kueri dan vektor dokumen. M etode LSI ini memiliki banyak kemiripan dengan M odel Ruang Vektor, metode pembobotan dan pencarian similarity sangatlah identik, yang membedakan 2 metode ini adalah metode SVD dalam pereduksian dimensi yang digunakan pada LSI.
52
2.3.7.1 Singular Value Decomposition SVD (Singular Value Decomposition) adalah salah satu teknik untuk mengolah matriks dari cabang ilmu aljabar linear yang diperkenalkan oleh Beltrami pada tahun 1873. SVD merupakan salah satu alat matematis yang digunakan untuk merepresentasikan sebuah matriks dan mampu melakukan berbagai analisis dan komputasi matriks. Langkah pertama adalah merepresentasikan teks sebagai matriks yang setiap barisnya mewakili kata yang unik dan setiap kolom mewakili kalimat. Setiap sel berisikan frekuensi kemunculan kata di setiap kolom. Selanjutnya, isi dari sel merupakan transformasi preliminary yang detilnya akan dideskripsikan kemudian, yang mas ing– masing frekuensi sel diberi bobot oleh sebuah fungsi yang menghasilkan keutamaan kata dalam sebuah kalimat. Selanjutnya, metode ini mengaplikasikan SVD (Singular Value Decomposition) ke dalam matriks. M atriks yang direpresentasikan menggunakan SVD akan diuraikan menjadi 3 (tiga) komponen matriks, yaitu matriks vektor singular kiri, martiks nilai singular, dan matriks vektor singular kanan. SVD dari sebuah matriks I yang berdimensi M xN adalah sebagai berikut :
A = U S VT ………………….(2.31) Keterangan : A = matriks berdimensi M xN U = matriks vektor singular kiri berdimensi M xM
53
S = matriks nilai singular berdimensi M xN dengan nilai terurut menurun V = matriks vektor singular kanan berdimensi NxN
2.3.8 Model Ruang Vektor M enurut M arjuki (2008, p129), di dalam M odel Ruang Vektor, dokumendokumen direpresentasikan sebagai vektor-vektor. Kesuksesan maupun kegagalan dari metode M odel Ruang Vektor tergantung kepada pembobotan term. Term mencakup katakata, frase-frase, atau unit indeks lainnya yang digunakan untuk mengidentifikasi konten dari sebuah teks. Karena term yang berbeda memiliki tingkat kepentingan yang berbeda di dalam teks, indikator penting (pembobotan term) dikaitkan dengan setiap term. Performa retrival dari sistem retrival informasi sangat tergantung kepada tingkat kesamaan. M odel Ruang Vektor terdiri dari tiga tahap pengerjaan, yaitu pengindeksan dokumen, pembobotan term, dan memberikan peringkat sesuai dengan tingkat kesamaan.
2.3.8.1 Pengindeksan dokumen Beberapa kata dalam sebuah dokumen tidak menggambarkan isi dari dokumen tersebut. Seperti kata the dan is. Kata-kata tersebut dikenal dengan nama kata-kata buangan. Dengan menggunakan automatic document indexing, kata-kata buangan tersebut dihilangkan dari dokumen. Pembuatan indeks tersebut dapat berdasarkan :
o
Frekuensi kemunculan istilah dalam sebuah dokumen.
o
M etode Non Linguistik : Probabilistic Indexing.
54
2.3.8.2 Pembobotan Term (Term Weighting) Pembobotan term dalam M odel Ruang Vektor secara keseluruhan berdasarkan statistik term tunggal. Ada tiga faktor utama dalam pembobotan istilah dengan menggunakan ruang vektor : 1.
Faktor frekuensi term
2.
Faktor frekuensi koleksi
3.
Faktor normalisasi panjang (Length normalization factor)
Ketiga faktor tersebut diatas dikalikan untuk menghasilkan bobot term. Skema pembobotan yang paling umum untuk term dalam sebuah dokumen adalah dengan menggunakan frekuensi kemunculan. Pembobotan dasar dilakukan dengan menghitung frekuensi kemunculan term dalam dokumen karena dipercaya bahwa frekuensi kemunculan term merupakan petunjuk sejauh mana term tersebut mewakili isi dokumen. M enurut Luhn (1958), kekuatan pembeda terkait dengan frekuensi term (term-frequency, tf), di mana term yang memiliki kekuatan diskriminasi adalah term dengan frekuensi sedang. Pembobotan baku yang digunakan adalah term-frequency inversdocument freqeuency (TF-IDF) sebagai berikut : log
;
1,2, … , ;
1,2, … ,
…..(2.32)
dengan t = total term dalam indeks, n = total dokumen dalam koleksi, dfi = total dokumen yang mengandung term ke-i.
55
2.3.8.3 Peringkat Dokumen Tingkat kesamaan (similarity) term dalam M odel Ruang Vektor ditentukan berdasarkan koefisien asosiatif berdasarkan inner product dari vektor dokumen dan kueri vektor, dimana word overlap menunjukkan kesamaan istilah. Inner product umumnya sudah dinormalisasi. M etode tingkat kesamaan yang paling populer adalah cosine coefficient, yang menghitung sudut antara vektor dokumen dengan vektor kueri.
,
∑ ∑
∑
…………(2.33)
