KLASIFIKASI PADA TEXT MINING

Budi Susanto

KLASIFIKASI PADA TEXT MINING

Text dan Web Mining - FTI UKDW - BUDI SUSANTO

1

Tujuan   Memahami

konsep dasar sistem klasifikasi   Memahami beberapa algoritma klasifikasi: ◦  KNN ◦  Naïve Bayes ◦  Decision Tree   Menjelaskan

implementasi algoritma klasifikasi pada text corpus.


2

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.


3

Contoh Implementasi   Identifikasi

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


4

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. Text dan Web Mining - FTI UKDW - BUDI SUSANTO

5

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. Text dan Web Mining - FTI UKDW - BUDI SUSANTO

6

Konsep Dasar   Supervised

learning

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

  Setelah


7

Proses Klasifikasi


8

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.


9

Naïve Bayes Text Classification  

Sebuah dokumen test terpilih masuk sebagai anggota suatu class terbaik jika memiliki maximum a posteriori (MAP) kelas cmap:


10

Naïve Bayes Text Classification


11

Contoh


12

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. Text dan Web Mining - FTI UKDW - BUDI SUSANTO

13

Feature Selection   Algoritma

dasar:


14

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.  


15

Contoh MI   Class

poultry dan term export:


16

Feature Selection: χ   Pada

2

2

statistik, χ 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


17

Contoh χ   Berdasar

2

contoh data slide 16


18

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 dokumendokumen dalam kelas, c. ◦  Lebih cocok untuk Naïve Bayes classifier. Text dan Web Mining - FTI UKDW - BUDI SUSANTO

19

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. Text dan Web Mining - FTI UKDW - BUDI SUSANTO

20

Algoritma Decission Tree


21

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.


22

Information Gain (IG)  

Diberikan himpunan data, D, hidtung impurity D dengan entropy(D):

 

Evaluasi tiap atribut untuk menemukan atribut mana yang terpilih mengurangi impurity.

 

Hitung IG atribut A


23

Contoh


24

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) = ?


25

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.


26

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. Text dan Web Mining - FTI UKDW - BUDI SUSANTO

27

Algoritma k-NN


28

Contoh !nggi 160 150 145 148 158 175 165

berat 80 45 44 75 56 80 70

label O N N O N O ???


29

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


30

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

optimal.

Recall dan Precision lebih

◦  Menghitung seberapa tepat dan lengkap klasifikasi terhadap kelas positif. ◦  Menggunakan confusion matrix   Berisi informasi hasil aktual dan prediksi yang dihasilkan oleh pengklasifikasi. Text dan Web Mining - FTI UKDW - BUDI SUSANTO

31

Evaluasi   Confusion

Matrix


32

Akhir pertemuan #5

TERIMA KASIH.


33

KLASIFIKASI PADA TEXT MINING

Recommend Documents