JULIO ADISANTOSO - ILKOM IPB 1

10/23/2009

Ad Hoc Retrieval

KOM341 Temu Kembali Informasi

User mencari informasi dengan memberikan satu atau lebih query terhadap koleksi terkini. Contoh: mencari multicore computer chips terbaru. Query : multicore AND computer AND chip Akan dieksekusi setiap ada penambahan dokumen baru Æ standing query Mungkin tidak menemukan artikel baru lain yang relevan, misalnya multicore processors. Gunakan Boolean: (multicore OR multi-core) AND (chip OR processor OR microprocessor)

KULIAH #7 • Text Classification

JAS - DEPT. ILMU KOMPUTER IPB

Classification

Categorization/Classification

Lebih mudah kalau dokumen dikelompokkan menjadi misalnya dua kelas, yaitu dokumen tentang multicore computer chips dan dokumen BUKAN t t tentang multicore lti computer t chips. hi Kelas biasanya merujuk ke topik dokumen. Prosesnya sering disebut sebagai text classification, text categorization, topic classification, topic spotting.

Given:


Deskripsi dokumen d∈X, dimana X adalah kumpulan dokumen. Himpunan kelas atau kategori: C = {c1, c2,…, cn}

Tujuan: Menentukan kategori dari d: c(d)∈C, dimana c(d) adalah fungsi kategorisasi (classifier).

3


Document Classification

(AI)

(Programming)

(HCI)

Classes: ML Training Data:

learning intelligence algorithm reinforcement network...

Planning

Semantics

planning temporal reasoning plan language...

programming semantics language proof...

Garb.Coll.

4

Learning Method “planning language proof intelligence”

Test Data:

2

Multimedia

GUI

garbage ... collection memory optimization region...


JULIO ADISANTOSO - ILKOM IPB

...

5

Kita mempelajari fungsi klasifikasi yang memetakan dokumen ke kategori tertentu: γ:Χ→C Disebut juga supervised learning, karena supervisor (orang yang menentukan kategori dokumen) berperan langsung di dalam proses pembelajaran.


6

1

10/23/2009

Metode

Metode

Manual

Automatic document classification

Digunakan oleh Yahoo!, Looksmart, about.com, ODP, Medline Sangat akurat karena dilakukan oleh ahli. Konsisten pada saat ukurannya kecil/sedikit. kecil/sedikit Sulit dan mahal


Hand-coded rule-based systems Digunakan oleh CS dept’s spam filter, Reuters, CIA, Verity, … Masukkan ke kategori g jjika dokumen mengandung g g kombinasi kata tertentu. Akurasi tinggi jika rule dibuat dengan sangat baik oleh ahli dan kompleks.

7


Metode

Metode Bayes

Automatic document classification

Berbasis teori peluang Utamanya teorema Bayes Untuk kejadian a dan b, Bayes Rules:

Supervised learning Beberapa menggunakan machine learning (Autonomy, MSN, Verity, Enkata, Yahoo!, …)

k-Nearest Neighbors (simple, powerful) Naive Bayes (simple, common method) Support-vector machines (new, more powerful) dsb Membutuhkan hand-classified training data Data dapat dibangun oleh amatir

p (a, b) = p(a ∩ b) = p (a | b) p(b) = p(b | a ) p (a) p ( a | b ) p ( b ) = p (b | a ) p ( a ) Prior p (b | a ) p(a ) p (b | a ) p(a ) p ( a | b) = = p (b) ∑ x=a,a p(b | x) p( x)

Banyak sistem komersial menggunakan metode campuran

Posterior


9


Naïve Bayes Model

Pendugaan Parameter

Supervised learning method Multinomial Naïve Bayes Model Peluang dokumen d dalam kelas c :

Pendugaan parameter

P ( c | d ) ∝ P (c )

∏ P(t

k

| c)

t '∈V

dimana P(tk|c) adalah peluang term tk muncul pada dokumen kelas c, P(c) peluang dokumen ada pada kelas c.


10

T N Pˆ (c) = c , Pˆ (t | c) = ct N ∑ Tct '

1≤ k ≤ nd


8

11

dimana Nc adalah banyaknya dokumen dalam kelas c, N adalah total dokumen, Tct adalah banyaknya t dalam dokumen training dari kelas c.


12

2

10/23/2009

Laplace smoothing

Contoh

Atau Add-One Smoothing. Untuk menghilangkan dugaan parameter yang bernilai nol.

Pˆ (t | c) =

Tctt + 1 Tctt + 1 = ⎞ ⎛ ct ' + 1) ⎜ ∑ Tct ' ⎟ + B ' t '∈V ⎝ t '∈V ⎠

∑ (T

TRAINING SET

TEST SET

docID

words in document

in c = China?

1

Chinese Beijing Chinese

yes

2

Chinese Chinese Shanghai

yes

3

Chinese Macao

yes

4

Tokyo Japan Chinese

no

5

Chinese Chinese Chinese Tokyo Japan

?

P(c) = ¾ dan P(¬c) = ¼ P(Chinese|c) = (5+1)/(8+6) = 6/14 = 3/7 P(Tokyo|c) = P(Japan|c) = (0+1)/(8+6) = 1/14 P(Chinese| ¬c) = (1+1)/(3+6) = 2/9 P(Tokyo| ¬ c) = P(Japan| ¬ c) = (1+1)/(3+6) = 2/9

dimana B = |V| = banyaknya term dalam vocabulary.

Pˆ (c | d 5 ) ∝ 3 / 4 ⋅ (3 / 7) 3 ⋅1 / 14 ⋅1 / 14 ≈ 0.0003 Pˆ (c | d ) ∝ 1 / 4 ⋅ (2 / 9)3 ⋅ 2 / 9 ⋅ 2 / 9 ≈ 0.0001 5


13

Bernoulli Model


14

Contoh

Kejadian Bernoulli Multivariate Bernoulli Model ˆ (t | c) : rasio dokumen dari kelas c yang P mengandung term t. Dalam multinomial didefinisikan sebagai rasio token dalam dokumen kelas c yang mengandung term t.

TRAINING SET

TEST SET

docID

words in document

in c = China?

1

Chinese Beijing Chinese

yes

2

Chinese Chinese Shanghai

yes

3

Chinese Macao

yes

4

Tokyo Japan Chinese

no

5

Chinese Chinese Chinese Tokyo Japan

?

P(c) = ¾ dan P(¬c) = ¼ P(Chinese|c) = (3+1)/(3+2) = 4/5 P(Tokyo|c) = P(Japan|c) = (0+1)/(3+2) = 1/5 P(Beijing|c) = P(Shanghai|c) = P(Macao|c) = (1+1)/(3+2) = 2/5 P(Chinese| ¬c) = (1+1)/(1+2) = 2/3 P(Tokyo| ¬ c) = P(Japan| ¬ c) = (1+1)/(1+2) = 2/3 P(Beijing|c) = P(Shanghai|c) = P(Macao|c) = (0+1)/(1+2) = 1/3


15

Contoh


16

Maximum a Posteriori

Pˆ (c | d 5 ) ∝ Pˆ (c ).Pˆ (Chinese | c ).Pˆ ( Japan | c).Pˆ (Tokyo | c) .(1 − Pˆ ( Beijing | c)).(1 − Pˆ ( Shanghai | c )).(1 − Pˆ ( Macao | c)) = 3 / 4 ⋅ 4 / 5 ⋅1 / 5 ⋅ (1 − 2 / 5).(1 − 2 / 5).(1 − 2 / 5) ≈ 0.005 Pˆ (c | d ) ∝ 1 / 4 ⋅ 2 / 3 ⋅ 2 / 3 ⋅ 2 / 3.(1 − 1 / 3).(1 − 1 / 3).(1 − 1 / 3) ≈ 0.022

Tujuan klasifikasi: mendapatkan kelas terbaik untuk suatu dokumen. Kelas terbaik : sangat mirip atau maximum a posteriori (MAP) kelas cmap :

5

cmap = arg max Pˆ (c | d ) = arg max Pˆ (c)

Jadi, dokumen d5 diklasifikasikan ke ¬c (bukan China)

c∈C

c∈C

∏ Pˆ (t

k

| c)

1≤ k ≤ nd

diduga dari training set JAS - DEPT. ILMU KOMPUTER IPB


17


18

3

10/23/2009

Maximum a Posteriori cmap = arg max P (c | d ) = arg max c∈C

c∈C

Asumsi Saling Bebas

P ( d | c ) P (c ) P(d )

• Kejadian A dan B saling bebas P(A∩B) = P(A,B) = P(A).P(B)

= arg max P (d | c) P (c) c∈C

• Maka:

• Multinomial

P(d|c)=P(|c)

• Bernoulli

P(d|c)=P(<e1, …, ek, …, eM>|c)

Multinomial Bernoulli

P(d | c) = P( t1 ,..., t nd | c) =

∏ P( X

k

= t k | c)

∏ P(U

i

= ei | c)

1≤ k ≤ nd

P(d | c) = P( e1 ,..., eM | c) =

1≤i ≤ M


19


20

Multinomial vs Bernoulli

Vector Space Classification


21

Klasifikasi Menggunakan Ruang Vektor

Test Document = Government ?

Setiap dokumen training direpresentasikan sebagai vektor. Setiap titik (vektor) dokumen training diberi label sesuai dengan kelasnya.

Similarity hypothesis true in general?

Government Government

Science

Science

Arts

Arts



23


24

4

10/23/2009

Rocchio Classification


Centroid dari kelas c:

r

µ (c ) =

1 Dc

Batas antara dua kelas adalah titik yang memiliki jarak sama ke kedua centroid-nya t id Æ |a1|=|a2|, |b1|=|b2|, |c1|=|c2|

r

∑ v (d )

d ∈Dc


25



Contoh

Dokumen d dikelompokkan ke dalam kelas c

Dari contoh sebelumnya, diperoleh:

26

Menggunakan jarak

r r arg min µ c − v ( d ) c

Menggunakan ukuran kesamaan Cosine

r r arg max cos( µ (c ), v ( d ))

Jarak d5 terhadap centroid: |µc-d5|≈1.15 dan |µ¬c-d5|≈0.00 maka Rocchio mengklasifikasikan d5 ke kelas ¬c (bukan China).

c JAS - DEPT. ILMU KOMPUTER IPB

27

k Nearest Neighbor Classification


28

Contoh: k=6 (6NN)

Mengklasifikasikan dokumen d ke dalam kelas c Tentukan k-neighborhood N atau kNN sebagai k terdekat dari d Hitung banyaknya dokumen i dalam N pada kelas c Duga nilai P(c|d) = i/k Pilih

P(science|

)?

Government Science

cmap = arg max P (c | d )

Arts

c∈C



29


30

5

10/23/2009

Ukuran Kemiripan

Contoh : 1NN

Metode kNN tergantung pada ukuran kemiripan (bisa juga jarak) yang digunakan. Paling sederhana adalah jarak Euclidean. Untuk teks, yang paling efektif adalah ukuran kemiripan cosine dengan bobot vektor tf.idf. tf idf Skor dokumen di suatu kelas:

dimana Ic(d’)=1 jjk d’ ada dalam kelas c, dan sebaliknya = 0. JAS - DEPT. ILMU KOMPUTER IPB

Dengan menggunakan jarak Euclidean, maka: |d1-d5|=|d2-d5|=|d3-d5| = 1.4171 |d4-d5|= 0.0000 Maka d5 lebih dekat ke kelas d4.

31


Kombinasi Metode Klasifikasi

Kombinasi Metode Klasifikasi

Beberapa peneliti menunjukkan bahwa kombinasi beberapa classifier yang berbeda dapat meningkatkan akurasi.

Simple voting

Classifier 1: X Æ class1 Classifier 2: X Æ class2 Jadi, X dimasukkan kemana?



33

32

Untuk tiap dokumen test, kita klasifikasikan ke kelas ci jika mayoritas classifier memasukkan dokumen test ke kelas ci.

Dynamic classifier selection (DCS) Pendekatan kNN dengan ukuran kesamaan Cosine, dilakukan iterasi. Adaptive classifier combination (ACC) Kombinasi NB dan kNN


34

6

JULIO ADISANTOSO - ILKOM IPB 1

Recommend Documents