Budi Susanto VEKTORISASI DOKUMEN

Budi Susanto

VEKTORISASI DOKUMEN

Tujuan —  Memahami

metode-metode yang diterapkan untuk pembentukan vektor dokumen

Pendahuluan —  Dokumen

bukanlah data terstruktur karena jauh dari bentuk tabel (baris dan kolom). —  Perlu metodologi pembentukan suatu data terstruktur untuk mewakili dokumen. —  Langkah awal adalah harus menentukan features yang mewakiliki seluruh kumpulan dokumen.

Koleksi Dokumen —  Dalam

suatu permasalahan text mining, dokumen-dokumen yang akan diproses harus diidentifikasikan. —  Intervensi manusia dalam pengumpulan dokumen dapat mengontrol integritas proses koleksi dokumen —  Selanjutnya fokus pada pembersihan dokumen-dokumen tersebut dan memastikan berkualitas.

Koleksi Dokumen —  Ketika

koleksi dokumen dalam jumlah yang sangat besar, terkadang dibutuhkan penerapan teknik data sampling: ◦  Untuk memilih himpunan dokumen yang relevan –  Contoh berdasar timestamp –  Contoh lain berdasar kemiripan dokumen

Koleksi Dokumen —  Marijn

Koolen dan Jaap Kamps (2010) mengungkapkan bahwa: ◦  The amount of relevant information increases with collection size. –  Menambahkan dokumen ke dalam koleksi akan menyebabkan semakin berkurangnya informasi yang dikebalikan: karena semakin banyak informasi yang sudah ditutupi oleh koleksi, maka akan semakin sulit menambahkan informasi baru.

◦  The amount of redundant information increases with collection size. –  Redudansi informasi akan menyebabkan kolek dokumen yang besar berpotensi merugikan. http://dl.acm.org/citation.cfm?id=1835586&dl=ACM&coll=DL&CFID=155824736&CFTOKEN=35757112

Koleksi Dokumen

Memilih Sampling —  Pendekatan

umum:

◦  Dipilih secara acak n% dari m dokumen ◦  Pendekatan Kennard-Stone

Pendeteksi Duplikasi Dokumen —  Conrad

et al. (2004) mengatakan “dua dokumen adalah near duplicate jika berbagi lebih dari 80% terminologi yang sama dan perbedaan panjang keduanya tidak lebih dari 20%. ◦  Pemanfaatan nilai hash (MD5 misalnya) terhadap tiap dokumen (exact duplicate) ◦  Menerapkan Shingles (Word N-grams) ◦  Jarak dengan Jaccar, SMC, Cosine

K-Shingling — 

K-Singling suatu dokumen mentransformasikan dokumen ke dalam suatu himpunan yang berisi semua window dari k kata bersambungan. ◦  Contoh: “Nama saya text dan web mining. Matakuliah ini adalah luar biasa.” ◦  4-singles = { –  –  –  –  –  –  –  – 

◦  }

nama saya text dan Saya text dan web Text dan web mining Dan web mining matakuliah Web mining matakuliah ini Mining matakuliah ini adalah Matakuliah ini adalah luar Ini adalah luar biasa

K-Shingling —  Sk(d)

menyatakan k-shingling dokumen d —  Ressemblance (kemiripan) d1 dan d2 R(d1,d2) = |Sk(d1) ∩ Sk(d2)| / |Sk(d1) ∪ Sk(d2)|

—  Ukuran

jarak d1 dan d2 Δ(d1,d2)  =  1-­‐R(d1,d2)  

Jaccard dan SMC —  SMC

(Simple Matching Coefficient)

—  jaccard

Cossine —  Sering

digunakan untuk frekuensi kemunculan kata suatu dokumen

Beberapa Koleksi —  Reuters

corpus RCV1 —  Brown corpus —  Lancaster-Oslo-Bergen corpus (LOB) —  Penn Tree Bank —  TREC (Text Retrieval and Evaluation Conferences) —  Gutenberg Project —  MEDLINE

Standarisasi Dokumen —  Koleksi

dokumen juga sebaiknya di simpan dalam suatu format dokumen yang seragam. ◦  Format XML menjadi pilihan terbaik. ◦  DBMS yang mendukung penyimpanan teks dapat dimanfaatkan.

Deretan Karakter —  Hal

pertama yang perlu dipertimbangkan adalah format character set yang digunakan. ◦  ASCII tidak menjadi masalah ◦  Bagaimana dengan UTF, UNICODE? ◦  Bagaimana dengan dokumen MS WORD? ◦  XML? yang mengandung entitas karakter   © dan sebagainya.

—  Sistem

penulisan karakter

◦  Arabic apakah sama dengan Latin atau Katagana atau sejenis yang lain?

Unit Dokumen —  File

dalam suatu folder —  Email dalam suatu inbox ◦  Mengandung attachment —  Sebuah

HTML.

file EPUB terdiri dari beberapa file

Bagaimana Anda melakukan Tokenisasi? JEJU, KOMPAS.com - Persediaan tuna global menipis akibat penangkapan berlebih. Menurut daftar merah International Union for Conservation of Nature (IUCN), saat ini lima dari delapan spesies tuna tergolong kategori terancam atau hampir punah. Para pemerhati konservasi mengemukakan peringatan mengenai hal ini pula dalam Kongres Konservasi Dunia (World Conservation Congress) IUCN di Jeju, Korea Selatan, hari Sabtu (8/9). Tuna sirip biru Atlantik adalah yang paling terancam ketersediaannya. Ikan ini merupakan favorit para pecinta makanan sushi Jepang, dan dihargai tinggi. Rekor tertinggi seekor ikan dengan berat 592 pon (269 kilogram) pernah dinilai seharga 56,49 juta yen (sekitar 737.000 USD). http://sains.kompas.com/read/2012/09/12/20015474/Lima.dari.Delapan.Spesies.Tuna.Hampir.Punah

Tokenisasi —  A

token is an instance of a sequence of characters in some particular document that are grouped together as a useful semantic unit for processing. —  A type is the class of all tokens containing the same character sequence. —  A term is a (perhaps nor- malized) type that is included in the IR system’s dictionary.

Tokenisasi —  Pada

pendekatan modern, yang tersimpan dalam index atau vektor adalah suatu bentuk token yang telah melalui proses normalisasi. ◦  Tokenisasi perlu juga memperhatikan bahasa yang digunakan dalam dokumen. ◦  Terdapat beberapa token yang tidak umum –  Singkatan –  Sebutan suatu produk –  Email, url, nomor nota, dan sebagainya

Identifikasi Bahasa —  Latih

pengenalan suatu identifikasi bahasa berdasar suatu corpus teks besar dari suatu bahasa terpilih. ◦  Pelatihan yang dimaksud untuk mendapatkan frekuensi/kompresi terhadap kemunculan ngram.

—  Gunakan

hasil pelatihan untuk menilai teks yang baru.

Pelatihan Identifikasi Bahasa —  Untuk

tiap corpus, kumpulkan statistik kemunculan dari kemunculan n-gram dalam corpus c dengan panjang |c|. —  Hitung probabilitas kemunculan n-gram i

William B. Cavnar and John M. Trenkle, N-Gram-Based Text Categorization.

Identifikasi Bahasa suatu Teks —  Untuk

setiap pengenal bahasa

◦  Untuk sebuah dokumen tidak dikenal, hitung statistik kemunculan dari n-gram dalam dokumen d dengan panjang |d|. ◦  Hitung probabilitas kemunculan n-gram j —  Hitung

jarak dengan model tiap bahasa

N-Gram-Based Text Categorization

Contoh sederhana Sample 1

Test

Sample 2

Test

Saya makan nasi

makan

I eat rice

makan

say

1

0.0769

ie

1

0.125

aya

1

0.0769

ea

1

0.125

ya

1

0.0769

eat

1

0.125

am

1

0.0769

at

1

0.125

ma

1

0.0769

tr

1

0.125

mak

1

0.0769

1

0.3333

0.256410256

ri

1

0.125

aka

1

0.0769

1

0.3333

0.256410256

ric

1

0.125

kan

1

0.0769

1

0.3333

0.256410256

ice

1

0.125

an

1

0.0769

nn

1

0.0769

0 mak

1

0.3333

0.333333333

na

1

0.0769

0 aka

1

0.3333

0.333333333

nas

1

0.0769

0 kan

1

0.3333

0.333333333

asi

1

0.0769

13

0.769230769

8

1

Pendeteksian dengan ML (n-gram kata)

Contoh Sederhana add-one smoothing

Contoh Sederhana add-one smoothing

Stemming dan Lemmatization —  Tujuan: untuk

mengurangi perubahan bentuk atau turunan dari suatu kata. ◦  Stemming –  Menggunakan proses heuristik untuk membuang awalan dan akhiran

◦  Lemmatization –  Menerapkan kamus kontrol dan analisis morfologi –  Biasanya membuang akhiran

Stemmer untuk Indonesia —  Algoritma

Nazief dan Adriani —  Algoritma Idris dan Mustapha —  Algoritma Arifin dan Setiono —  Algoritma Ahmad, Yussof dan Sembok —  Algoritma Vega

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.59.4851&rep=rep1&type=pdf

Afiks (Imbuhan) Bahasa Indonesia —  Empat

macam:

◦  Prefiks –  afiks yang dilekatkan di depan kata dasar

◦  Sufiks –  afiks yang dilekatkan di belakang kata dasar

◦  Konfiks –  gabungan prefiks dan sufiks yang mengapit kata dasar dan membuat suatu kesatuan

◦  infiks –  bentuk afiks yang diletakkan di tengah kata dasar

Algoritma Bobby Nazief dan Mirna Adriani 1. 

2. 

Cari kata yang akan distem dalam kamus. Jika ditemukan maka diasumsikan bahwa kata tesebut adalah root word. Maka algoritma berhenti. Inflection Suffixes (“-lah”, “-kah”, “-ku”, “mu”, atau “-nya”) dibuang. Jika berupa particles (“-lah”, “-kah”, “-tah” atau “pun”) maka langkah ini diulangi lagi untuk menghapus Possesive Pronouns (“-ku”, “-mu”, atau “-nya”), jika ada.

Algoritma Bobby Nazief dan Mirna Adriani 3. 

Hapus Derivation Suffixes (“-i”, “-an” atau “-kan”). Jika kata ditemukan di kamus, maka algoritma berhenti. Jika tidak maka ke langkah 3a a.  Jika “-an” telah dihapus dan huruf terakhir dari kata tersebut adalah “-k”, maka “-k” juga ikut dihapus. Jika kata tersebut ditemukan dalam kamus maka algoritma berhenti. Jika tidak ditemukan maka lakukan langkah 3b. b.  Akhiran yang dihapus (“-i”, “-an” atau “-kan”) dikembalikan, lanjut ke langkah 4.

Algoritma Bobby Nazief dan Mirna Adriani 4. 

Hapus Derivation Prefix. Jika pada langkah 3 ada sufiks yang dihapus maka pergi ke langkah 4a, jika tidak pergi ke langkah 4b. a.  Periksa tabel kombinasi awalan-akhiran yang tidak diijinkan. Jika ditemukan maka algoritma berhenti, jika tidak pergi ke langkah 4b. b.  For i = 1 to 3, tentukan tipe awalan kemudian hapus awalan. Jika root word belum juga ditemukan lakukan langkah 5, jika sudah maka algoritma berhenti. Catatan: jika awalan kedua sama dengan awalan pertama algoritma berhenti.

Algoritma Bobby Nazief dan Mirna Adriani 5.  6. 

Melakukan Recoding. Jika semua langkah telah selesai tetapi tidak juga berhasil maka kata awal diasumsikan sebagai root word. Proses selesai.

Algoritma Bobby Nazief dan Mirna Adriani — 

Tipe awalan ditentukan melalui langkah-langkah berikut: 1.  Jika awalannya adalah: “di-”, “ke-”, atau “se-” maka tipe awalannya secara berturut-turut adalah “di-”, “ke-”, atau “se-”. 2.  Jika awalannya adalah “te-”, “me-”, “be-”, atau “pe-” maka dibutuhkan sebuah proses tambahan untuk menentukan tipe awalannya. 3.  Jika dua karakter pertama bukan “di-”, “ke-”, “se-”, “te-”, “be-”, “me-”, atau “pe-” maka berhenti. 4.  Jika tipe awalan adalah “none” maka berhenti. Jika tipe awalan adalah bukan “none” maka awalan dapat dilihat pada Tabel 2. Hapus awalan jika ditemukan.

Algoritma Bobby Nazief dan Mirna Adriani

Algoritma Bobby Nazief dan Mirna Adriani

Algoritma Bobby Nazief dan Mirna Adriani

Feature Selection —  Memilih

k-top dari bobot

◦  Bobot dapat dilakukan dengan TF/IDF

◦  Dapat menerapkan validasi regresi linier ◦  Information Gain untuk tiap kategori

MATURNUWUN!