KLASIFIKASI PADA TEXT MINING

4/2/13

Text dan Web Mining - FTI UKDW - BUDI SUSANTO

1

KLASIFIKASI PADA TEXT MINING Budi Susanto


2

Tujuan •  Memahami konsep dasar sistem klasifikasi •  Memahami beberapa algoritma klasifikasi: •  KNN •  Naïve Bayes •  Decision Tree •  Menjelaskan implementasi algoritma klasifikasi pada text

corpus.

Text dan Web Mining -‐ FTI UKDW -‐ BUDI SUSANTO

1

4/2/13


3

Pendahuluan •  Masalah klasifikasi adalah bagaimana menentukan suatu

objek masuk ke suatu class yang sebenarnya. •  Dalam text mining, suatu class lebih bersifat area subjek umum.

(disebut juga Topik). •  Pekerjaan klasifikasi disebut sebagai text classification, text categorization, topic classification, atau topic spotting.


4

Contoh Implementasi •  Identifikasi bahasa suatu dokumen •  Mendeteksi encoding dokumen •  Mendeteksi otomatis halaman/email spam •  Sentiment detection •  Personal email sorting •  Topic-specific (vertical search)


2

4/2/13


5

Machine Learning •  Klasifikasi dilakukan berdasar pembelajaran dari

kumpulan dokumen untuk mendapatkan suatu pola tiap class. •  Pola dapat berupa suatu rule

•  Pembelajaran untuk mendapatkan pola atau kriteria

keputusan suatu class oleh komputer dilakukan dengan cara “mempelajari” secara otomatis dari data pelatihan (training data). •  Jika menggunakan metode statisik, disebut statistical text

classification.


6

Machine Learning •  Diperlukan sejumlah dokumen (training document) yang

sangat baik untuk tiap class. •  Harus dilakukan dengan cara manual terkait pemberian label class

tiap training document. •  Aktifitas ini disebut labeling

•  Semua algoritma klasifikasi dalam text mining mewakili

dokumen dalam suatu ruang dimensi yang tinggi. •  Untuk mengifisiensikan, diperlukan pengurangan dimensi •  Disebut dengan feature selection.


3

4/2/13


7

Konsep Dasar •  Supervised learning

γ :Χ →C •  Setelah mempelajari γ, kita dapat menerapkannya untuk himpunan dokumen test.


8

Proses Klasifikasi


4

4/2/13


9

Naïve Bayes Text Classification •  Menurut metode multinomial Naïve Bayes, probabilitas

suatu dokumen, d, sebagai bagian dari anggota class c dihitung sebagai:

•  P(tk|c) adalah probabilitas kondisi kemunculan term tk dalam

sebuah dokumen class c.

•  Seberapa yakin tk berkontribusi bahwa c adalah kelas yang benar

•  P(c) adalah probabilitas kemunculan sebuah dokumen dalam kelas

c.

•  adalah token-token dalam d.


10

Naïve Bayes Text Classification •  Sebuah dokumen test terpilih masuk sebagai

anggota suatu class terbaik jika memiliki maximum a posteriori (MAP) kelas cmap:


5

4/2/13


11

Naïve Bayes Text Classification


12

Contoh


6

4/2/13


13

Feature Selection •  Feature Selection adalah proses pemilihan sebuah subset

term yang muncul dalam himpunan training. •  Klasifikasi teks hanya akan menggunakan hasil feature selection. •  Alasan: •  Agar metode pengklasifikasian lebih efisien dengan mengurangi ukuran

vocabulary. •  Meningkatkan akurasi klasifikasi dengan membuang feature noise.


14

Feature Selection •  Algoritma dasar:


7

4/2/13


15

Feature Selection: Mutual Information •  A(t,c) nilai mutual information dari term t dan

class c. •  MI mengukur seberapa besar kontribusi ada/ tidaknya suatu term, t, dalam pembuatan keputusan klasifikasi yang benar, c.


16

Contoh MI •  Class poultry dan term export:


8

4/2/13


17

2 Feature Selection: χ •  Pada statistik,

χ 2 test digunakan untuk menguji

independensi antar dua kejadian.

•  Dua kejadian, A dan B, dikatakan independen jika P(AB)=P(A)P(B). •  A adalah kemunculan term •  B adalah kemunculan class


18

Contoh χ 2 •  Berdasar contoh data slide 16


9

4/2/13


19

Feature Selection: Frequency-based •  Memilih term-term yang paling umum dalam kelas. •  Frekuensi dapat didefinisikan sebagai frekuensi dokumen •  Jumlah dokumen dalam kelas, c, yang mengandung term, t. •  Frekuensi dapat didefinisikan sebagai frekuensi koleksi •  Jumlah token-token, t, yang muncul di dokumen-dokumen dalam kelas, c. •  Lebih cocok untuk Naïve Bayes classifier.


20

Decision Tree •  Decision Tree dibangun dengan cara membagi data

pelatihan sehingga hasil subset adalah pure. •  pure subset adalah salah satu yang berisi contoh pelatihan dari

suatu kelas tunggal.

•  Sebuah decision tree dapat diubah menjadi himpunan

aturan if-then. •  Setiap aturan yang dihasilkan bersifat mutually exclusive dan

lengkap. •  Setiap instan data dicakup oleh sebuah aturan tunggal.


10

4/2/13


21

Algoritma Decission Tree


22

Decision Tree •  Salah satu hal terpenting dalam pembentukan decission

tree adalah pemilihan impurity function. •  Fungsi yang meminimalkan impurity setelah pembagian.

•  Impurity function yang terkenal: •  Information gain dan information gain ratio.


11

4/2/13


23

Information Gain (IG) •  Diberikan himpunan data, D, hitung impurity D dengan entropy(D):

•  Evaluasi tiap atribut untuk menemukan atribut mana yang terpilih

mengurangi impurity.

•  Hitung IG atribut A


24

Contoh


12

4/2/13


25

Contoh •  Entropy(D) = entropy([9,5]) = 0.940 bit •  Entropy(Aoutlook, D) = (5/14) × 0.971 + (4/14) × 0 + (5/14) × 0.971 =

0.693 bit •  Gain(outlook) = Entropy(D) - Entropy(Aoutlook, D) = 0.247 bit •  Hitunglah IG untuk atribut yang lain: •  Gain(temperature) = ? •  Gain(humidity) = ? •  Gain(windy) = ?


26

k-NN •  Pada kNN, setiap dokumen dimasukkan dalam satu kelas

yang muncul terbanyak di antara k tetangga terdekatnya. •  Sebuah dokumen uji, d, diharapkan memiliki label kelas yang sama dengan dokumen latih yang berada pada satu area lokal disekitar d.


13

4/2/13


27

k-NN •  Terdapat alternatif probabilistik untuk memperkirakan

keanggotaan kelas sebuah dokumen uji. •  P(lingkaran|bintang) = 1/3 •  P(X|bintang) = 2/3 •  P(diamond|bintang) = 0

•  Pemilihan nilai k disarakan bernilai ganjil, k=3 dan k=5

umum digunakan.

•  Namun nilai k besar juga digunakan, antara 50-100.

•  Penghitungan dokumen latih yang dekat dengan

dokumen uji dapat digunakan Euclidean, Minkowski Distance. •  Untuk mengukur bobot “vote” untuk k-NN, dapat digunakan cosine.


28

Algoritma k-NN


14

4/2/13


29

Contoh Dnggi 160 150 145 148 158 175 165

berat 80 45 44 75 56 80 70

label O N N O N O ???


30

Evaluasi •  Accuracy •  (Jumlah terklasifikasi benar/total dokumen)*100 •  Metode evaluasi: •  Holdout set (test set) •  D=Dtrain ∪ Dtest, dan Dtran ∩ Dtest = ∅ . •  Biasanya 50-50, atau 2/3 train dan 1/3 test.

•  n-fold Cross-validation


15

4/2/13


31

Evaluasi •  Jika pengklasifikasian dilakukan terhadap topik tertentu,

misalnya positif jika benar masuk ke topik, dan negatif jika tidak. •  Pengukuran akurasi dipandang tidak optimal, jika ternyata terdapat

dokumen uji yang “mengganggu”

•  Pengukuran Recall dan Precision lebih optimal. •  Menghitung seberapa tepat dan lengkap klasifikasi terhadap kelas positif. •  Menggunakan confusion matrix •  Berisi informasi hasil aktual dan prediksi yang dihasilkan oleh

pengklasifikasi.


32

Evaluasi •  Confusion Matrix


16

4/2/13


33

Evaluasi •  Contoh confusion matrix Prediksi Class Class Aktual

A

B

C

A

25

5

2

B

3

32

4

C

1

0

15

•  Presisi •  Ukuran akurasi terhadap suatu class yang telah diprediksi. •  PresisiA = 25/(25+3+1)

•  Recall •  Ukuran kemampuan model prediksi untuk memilih data pada class tertentu dari dataset. •  RecallA = 25/(25+5+2)


34

TERIMA KASIH. Akhir pertemuan #5


17

KLASIFIKASI PADA TEXT MINING

Recommend Documents