.: [TKI] Text Classification

Pada kesempatan kali ini saya akan mencoba menjelaskan bagaimana suatu dokument dapat di klasifikasikan? contohnya jika ada portal berita yang memiliki beberapa kategori, dan kita ingin mengkategorikan berita baru yang ada. jikalau kita menggunakan cara konvensiional, makas kita akan mengklasifikasikanya manual, tapi bagaimana kalau misalkan kita memiliki 1000 dokumen baru? apakah itu baik kita kategorikan secara manual? saya rasa tidak. maka dari itu sya akan mencoba untuk sedikit menjelaskan bagaimana untuk mengklaskan dokumen secara otomatis.

langsung saja, untuk dapat melakukan pengkelasaanterhadap dokumen berikut beberapa langkah yang harus dilakukan.

kita akan membahasa masing masing dari tahapan yang ada diatas.

#Langkah pertama:

pada langkah ini kita di fukuskan untuk mengumpulkan dokumen, yang dimaksudkan untuk membuat suatu kelas untuk fungsi klasifikasi,

# Langakah kedua

pada langkah ini kita akan melakukan seleksi fitur yang berguna untuk kira-kira pada kelas tertentu punya identitas apa sih yang berbeda.

nah pada langakah ini terdapat 3 metode (yang saya tau)

1. metode petama yaitu metode Luhn dimana dalam metode ini saya tidak akan bercerita banyak. tapi initinya kita melakukan langkah-langkah yang biasa digunakan dalan pemprosesan text.

- Buang stopwoard => IDF = 0

- Buang daerah kurva sebelah kanan => IDF = log N

2. metode kedua yaitu namanya Mutual Information (MI) -> peluang similarity

sebelumnya kita harus mengetahui tabel berikut:

\|	Ct = 1	\| Ct = 0
Cc = 1 \|	N11	\| N10
Cc = 0 \|	N01	\| N00

jika kita ketahui c = class dan t = term

jadi misalkan kita ingin tau (c = spam, t = jual), maksudnya yaitu seberapa banyak kata jual kita kelaskan di kelas spam (N11)

Formula dari MI

$I(U:C) = \sum_{t=(0,1)} \sum_{c=(0,1)} P(U=Ct, C=Cc) log_{2} \frac{P(U=Ct, C=Cc)}{P(U=Ct)P(C=Cc)}$

langsung saja kita ke contoh soal

misalkan ada data:

seberapa besar kata-kata (brazil, council, producers, roasted) masuk kedalam class coffee??

term	N00	N10	N01	N11
brazil	98012	102	1835	51
council	96322	133	3525	20
producers	98524	119	1118	34
roasted	99824	143	23	10

berapa besaranya kata Brazil masuk ke kelas coffee -> I(Brazil, Coffee)

berapa besaranya kata Council masuk ke kelas coffee -> I(Council, Coffee)

berapa besaranya kata Producers masuk ke kelas coffee -> I(Producers, Coffee)

berapa besaranya kata Roasted masuk ke kelas coffee -> I(Roasted, Coffee)

$I(Brazil, Coffee) = \frac{51}{100000} log_{2} \frac{100000 * 51}{(51+102)+(51+1835)} + \frac{1835}{100000} log_{2} \frac{100000 * 1835}{(1835+98012)+(1835+51)} + \frac{102}{100000} log_{2} \frac{100000 * 102}{(102+51)+(102+98012)} + \frac{98012}{100000} log_{2} \frac{100000 * 98012}{(98012+1835)+(98012+102)} = 0.0015536892$ $I(Council, Coffee) = \frac{20}{100000} log_{2} \frac{100000 * 20}{(20+133)+(20+3525)} + \frac{3525}{100000} log_{2} \frac{100000 * 3525}{(3525+96322)+(3525+20)} + \frac{133}{100000} log_{2} \frac{100000 * 133}{(133+20)+(133+96322)} + \frac{96322}{100000} log_{2} \frac{100000 * 96322}{(96322+3525)+(96322+133)} = 0.0001774273$ $I(Producers, Coffee) = \frac{34}{100000} log_{2} \frac{100000 * 34}{(34+119)+(34+1118)} + \frac{1118}{100000} log_{2} \frac{100000 * 1118}{(1118+98524)+(1118+34)} + \frac{119}{100000} log_{2} \frac{100000 * 119}{(119+34)+(119+98524)} + \frac{98524}{100000} log_{2} \frac{100000 * 98524}{(98524+1118)+(98524+119)} = 0.0040003424$ $I(Roasted, Coffee) = \frac{10}{100000} log_{2} \frac{100000 * 10}{(10+1113)+(10+23)} + \frac{23}{100000} log_{2} \frac{100000 * 23}{(23+99824)+(23+10)} + \frac{1113}{100000} log_{2} \frac{100000 * 1113}{(1113+10)+(1113+99824)} + \frac{99824}{100000} log_{2} \frac{100000 * 99824}{(99824+23)+(99824+1113)} = 0.0006484759$

dari hasil tersebut kita mengetahui bahwa producers > brazil > roasted > council,
maka jikka hanya ingin mengambil 2 terbesar saja, maka kita akan memilih producers danbrazil

3. metode ketiga yaitu chi-square (x^2)
langsung saja, dengan data yang sama
rumus chi-square yaiut
$x^{2} (D, t, c) = \sum_{t=(0,1)} \sum_{c=(0,1)} \frac{(N_{CtCc}-E_{CtCc})^{2}}{E_{CtCc}}$ $E_{CtCc} = N . P(t) . P(c) = N . \frac{N_{CtCc}+NCt_{not}Cc}{N} . \frac{N_{CtCc}+NCtCc_{not}}{N}$

atau dengan menggunakan rumus yang lebih ringkas

$x^{2} (D,c ,t)= \frac{(N_{11}+N_{01}+N_{10}+N_{00})(N_{11}N_{00}-N_{10}N_{01})}{(N_{11}+N_{01})(N_{11}+N_{01})(N_{00}+N_{01})(N_{00}+N_{10})}$

$x^{2}(Brazil) = \frac{(51+1835+102+98012)(51 . 98012-102.1835)}{(51+102)(51+1835)(98012+1835)(98012+102)} = 818.94$

$x^{2}(Council) = \frac{(20+3525+133+96322)(20 . 96322-133 . 3525)}{(20+133)(20+3525)(96322+3525)(96322+133)} = 40.67$

$x^{2}(Producers) = \frac{(34+1118+119+98524)(34 . 98524-119 . 1118)}{(34+119)(34+1118)(98524+1118)(98524+119)} = 597.71$

$x^{2}(Roasted) = \frac{(10+23+143+99824)(10 . 99824-143 . 23)}{(10+143)(10+23)(99824+23)(99824+143)} = 1964.29$

dari hasil tersebut roasted>brazil>producers>council

nah, jika kita perhatikan, terdapat perbedaan hasil antara dua metode yang kita gunakan yaitu MI dan chi-square

#Langkah ketiga
lanjut pada langkah ketiga kita akan melakukan dan membuat kelas dengan fungsi klasifikasi menggunakan dokumen latih.

untuk dapat membuaat fungsi klasifikasi, harus kita ketahui ada beberapa cara
cara pertama berdasarkan vektor { KNN, SVM}
cara kedua berdasarkan peluang {Decision tree, Naive Bayes}

pada artikel ini saya hanya akan membahas tentang cara pengerjaan menggunakan naive bayes.
ada beberapa istilah sebelumnya:
P(c) = berapa peluang kelas c
P(c) = berapa peluang kelas bukan c
P(c|d) = berapa peluang dokumen d berada dalam kelas c
P(~c|d) = berapa peluang dokumen d berada dalam kelas bukan d

langsung saja ke contoh soal:

	Doc ID	Word in Document	in C = Chinese
training set	1	Chinese Beijing Chinese	yes
	2	Chinese Chinese sanghai	yes
	3	Chinese Macau	yes
	4	Tokyo Japan Chinese	no
test set	1	Chinese Chinese Chinese Tokyo Japan	?

$P(c|ds) = P(c).[P(Chinese|c)]^{3} . P(Tokyo|c) . P(Japan|c) = \frac{3}{4} . \frac{5}{8} . \frac{0}{8} . \frac{0}{8} = -$

$\small P(-c|ds) = P(-c).[P(Chinese|-c)]^{3} . P(Tokyo|-c) . P(Japan|-c) = \frac{1}{4} . \frac{1}{3} . \frac{1}{3} . \frac{1}{3} = \frac{1}{108}$

dari hasil tersebut nilai peluang P(c|ds) menjadi nol karena ada data yang tidak ada dalam kelas chinese, maka dari itu kita harus memikirkan cara bagaimana perluang tersebut tidah harus Nol. tenang saja kita tidak harus memikirkannya begitu serius soalnya sudah ada metode dimana nal tersebut dapat tertangani. yaitu menggunakan smoothing. ada dua cara untuk smoothing, yaitu:

1. Laplace Smoothing
menggunakan metode Laplace Smoothing = add one smoothing
metode ini hanya tinggal menambahkan 1 pada masing-masing nilai pembilang, dan menampahkan angkan sebanyak kata unit yang ada dalam kelas tersebut

$\small P(c|ds) = P(c).[P(Chinese|c)]^{3} . P(Tokyo|c) . P(Japan|c) = \frac{3}{4} . \frac{5+1}{8+6} . \frac{0+1}{8+6} . \frac{0+1}{8+6} = \frac{3}{4} . \frac{6}{14} . \frac{1}{14} . \frac{1}{14} = \frac{18}{10976} = 0.0016$

$\small P(-c|ds) = P(-c).[P(Chinese|-c)]^{3} . P(Tokyo|-c) . P(Japan|-c) = \frac{1}{4} . \frac{1+1}{3+3} . \frac{1+1}{3+3} . \frac{1+1}{3+3} = \frac{1}{4} . \frac{2}{9} . \frac{2}{9} . \frac{2}{9} = \frac{8}{2916} = 0.0027$

dari hasil tersebut kita dapat menentukan bahwa dokumen tersebut masuk kedalam kelas chinese

2. Bernaulli
sebenarnya hampir sama dengan Laplace Smoothing, hanya saja bernauli menambahkan beberapa perhirungan kedalamnya.
pembilang -> +1
penyebut -> +(jumlah kelas)

$\small P(c|ds) = P(c).[P(Chinese|c)]^{3} . P(Tokyo|c) . P(Japan|c) . [1-P(Beijing|c)]. [1-P(Sanghai|c)]. [1-P(Macau|c)]$

$\small P(-c|ds) = P(-c).[P(Chinese|-c)]^{3} . P(Tokyo|-c) . P(Japan|-c) . [1-P(Beijing|-c)]. [1-P(Sanghai|-c)]. [1-P(Macau|-c)]$

Search what you want

Labels

Friday, January 8, 2016

[TKI] Text Classification

No comments:

Post a Comment

.