perhitungan expectation maximization
DESCRIPTION
perhitungan em secara manualTRANSCRIPT
Dokumen Fitur (Kemunculan) Kelas
Dok 1 rakyat (2), aturan (3), subsidi (2) Positif
Dok 2 pemerintah (3), bbm (2), korupsi (4) Negatif
Dok 3 rakyat (1), aturan (2), korupsi (3) ?
Dok 4 pemerintah (2), rakyat (1), bbm (2) ?
a. Term documents matrix
aturan korupsi Subsidi rakyat Pemerintah Bbm
Dok 1 3 0 2 2 0 0
Dok 2 0 4 0 0 3 2
Dok 3 2 3 0 1 0 0
Dok 4 0 0 0 1 2 2
b. Model Probabilistik awal
𝑃 𝑤𝑘𝑗 𝐶𝑖 =𝑓 𝑤𝑘𝑗 𝐶𝑖 + 1
𝑓 𝐶𝑖 + |𝑊|
𝑓 𝑤𝑘𝑗 𝐶𝑖 : nilai kemunculan kata 𝑤𝑘𝑗 pada kata 𝐶𝑖
𝑓 𝐶𝑖 : jumlah keseluruhan kata pada kategori 𝐶𝑖
|𝑊|: jumlah keseluruhan kata/fitur yang digunakan
𝑃 𝐶𝑖 =𝑓𝑑 𝐶𝑖
|𝐷|
𝑓𝑑 𝐶𝑖 : jumlah dokumen yang memiliki kategori𝐶𝑖
|𝐷| : jumlah seluruh training dokumen
Model probabilistik awal yang terbentuk (Menggunakan Naïve bayes
classifier) adalah sebagai berikut :
Kelas P (Ci) P (Wkj|Ci)
aturan Korupsi subsidi Rakyat pemerintah Bbm
Positif 1/2
4/13
1/13 3
/13 3/13 1
/13 1/13
Negatif ½ 1
/15 5/15 1
/15 1/15 4
/15 3/15
c. Expectation Step
p(𝑐𝑖|𝑑𝑗 )=p 𝑐𝑖 Πk=1
dj p(𝑤𝑘𝑗 |𝑐𝑖)
𝑝 𝑐𝑟 Πk=1
dj p(𝑤𝑘𝑗 |𝑐𝑟)
|𝑐|𝑟=1
p 𝑐𝑖 : probabilitas kemunculan kejadian kelas 𝑐𝑖
p(“positif”|”dok 3”) = (p(“positif”) x (p ”rakyat”|“positif”) x
(“aturan”|”positif”) x p(“korupsi”|”positif”)) : ((p(”positif”) x
p(“rakyat”|”positif”) x p(“aturan”|”positif”) x p(“korupsi”|”positif”)) +
(p(“negatif”) x p(“rakyat”|”negatif”) x p(“aturan”|”negatif”) x
p(“korupsi”|”negatif”)))
= (1/2 x
3/13 x
4/13 x
1/3 ) : ((
1/2 x
3/13 x
4/13 x
1/13 ) + (
1/2 x
1/15
x 1/15 x
5/15 ))
= (12
/4394) : ((12
/4394) + (5/6750))
= 0,0027 : (0,0027 + 0,0027)
= 0,0027 : 0,0034
≈ 0,7941
p(“negatif”|”dok 3”) = (p((“negatif”) x (p ”rakyat” |“ negatif”) x
p(“aturan”|”negatif”) x p(“korupsi”|” negatif”)) : ((p(”positif”) x
p(“rakyat”|” positif”) x p(“aturan”|”posif”) x p(“korupsi”|”positif”)) +
(p(“negatif”) x p(“rakyat”|” negatif”) x p(“aturan”|”negatif”) x
p(“korupsi”|”negatif”)))
= (1/2 x
1/15 x
1/15 x
5/15 ) : ((
1/2 x
3/13 x
4/13 x
1/13 ) + (
1/2 x
1/15
x 1/15 x
5/15 ))
= (5/6750) : ((
12/4394) + (
5/6750))
= 0,0007 : (0,0027 + 0,0007)
= 0,0007 : 0,0034
= 0,2058
Karena P (“negatif”|”dok 3”) > (P”negatif”|”dok 3”) maka kelas
perkiraan untuk dok 3 adalah “positif”.
d. Maximization Step.
𝑝 𝑤𝑘𝑗 |𝑐𝑖 =1 + 𝑁
𝐷 𝑗=1 𝑤𝑘𝑗 , 𝑑𝑗 𝑝(𝑐𝑖|𝑑𝑗 )
𝑊 + 𝑁 𝐷 𝑗=1
𝑤 𝑠=1 𝑤𝑠 , 𝑑𝑗 𝑝(𝐶𝑖|𝑑𝑗 )
𝑁 𝑤𝑘𝑗 , 𝑑𝑗 : jumlah kata wk pada dokumen dj
Karena nilai 𝑊 + 𝑁 𝐷 𝑗=1
𝑤 𝑠=1 𝑤𝑠 , 𝑑𝑗 𝑝(𝐶𝑖|𝑑𝑗 ) akan selalu sama
untuk setiap perhitungan, maka nilainya dihitung terlebih dahulu,
sebagai pengganti akan diberi nama f(p). karena masih terdapat
beberapa probabilitas yang memiliki nilai 0 yaitu
p(“negatif”|”dokumen1”) dan p(“positif”|”dokumen2”) serta terdapat
beberapa kata yang nilai kemunculannya nol pada beberapa dokumen
seperti korupsi, pemerintah dan bbm pada dokumen1, aturan, subsidi
dan rakyat pada dokumen2, aturan, korupsi dan subsidi pada dokumen3,
sehingga f(p) dapat dituliskan sebagai berikut:
f(p) = 6 + (N p(“aturan”|”dok 1”) p(“positif”|”dok 1”) +
N p(“aturan”|”dok 3”) p(“positif”|”dok 3”) +
N p(“subsidi”|”dok 1”) p(“positif”|”dok 1”) +
N p(“rakyat”|”dok 1”) p(“positif”|”dok 1”) +
N p(“rakyat”|”dok 3”) p(“positif”|”dok 3”) +
N p(“korupsi”|”dok 3”) p(“positif”|”dok 3”) +
N p(“aturan”|”dok 3”) p(“negatif”|”dok 3”) +
N p(“bbm”|”dok 2”) p(“negatif”|”dok 2”) +
N p(“rakyat”|”dok 3”) p(“negatif”|”dok 3”) +
N p(“pemerintah”|”dok 2”) p(“negatif”|”dok 2”) +
N p(“korupsi”|”dok 3”) p(“negatif”|”dok 3”) +
N p(“korupsi”|”dok 2”) p(“negatif”|”dok 2”))
= 6 + 3 x 1 + 2 x 0,794 + 2 x 1 + 2 x 1 + 1 x 0,794 + 3 x 0,794 + 2 x
0,205 +
2 x 1 + 1 x 0,205 + 3 x 1 + 3 x 0,205 + 4 x 1
= 6 + 3 + 1,588 + 2 + 2 + 0,794 + 2,382 + 0,41 + 2 + 0,205 + 3 + 0,615
+ 4
= 27,994
p(“aturan”|”positif”) = (1 + N (“aturan, dok 1”) p(“positif”|”dok 1”) +
N(“aturan, dok 2”) p(“positif”|”dok 2”) +
N(“aturan, dok 3”) p(“positif”|”dok 3”)) : f(p)
= (1 + 3 x 1 + 0 x 0 + 2 x 0,794) : 27,994
= (1 + 3 + 0 1, 588) : 27,994
= 5,588 : 27,994
= 0,199
p(“aturan”|”negatif”) = (1 + N (“aturan, dok 1”) p(“negatif”|”dok 1”) +
N (“aturan, dok 2”) p(“negatif”|”dok 2”) +
N (“aturan, dok 3”) p(“negatif”|”dok 3”) ) : f(p)
= (1 + 3 x 0 + 0 x 1 + 2 x 0,205) : 27,994
= (1 + 0 + 0 + 0,41) : 27,994
= 1,041 : 27,994
= 0,050
p(“korupsi”|”positif”) = (1 + N (“korupsi”, dok 1”) p(“positif”|”dok 1”)
+
N(“korupsi, dok 2”) p(“positif”|”dok 2”) +
N(“korupsi, dok 3”) p(“positif”|”dok 3”)) : f(p)
= (1 + 0 x 1 + 4 x 0 + 3 x 0,794) : 27,994
= (1 + 0 x 0 + 2,382) : 27,994
= 0,120
p(“korupsi”|”negatif”) = (1 + N (“korupsi, dok 1”) p(“negatif”|”dok 1”)
+
N (“korupsi, dok 2”) p(“negatif”|”dok 2”) +
N (“korupsi, dok 3”) p(“negatif”|”dok 3”) ) : f(p)
= (1 + 3 x 0 + 4 x 1 + 3 x 0,205) : 27,994
= (1 + 0 + 4 + 0,615) : 27,994
= 0,2
p(“subsidi”|”positif”) = (1 + N (“subsidi”, dok 1”) p(“positif”|”dok 1”)
+
N(“subsidi, dok 2”) p(“positif”|”dok 2”) +
N(“subsidi, dok 3”) p(“positif”|”dok 3”)) : f(p)
= (1 + 2 x 1 + 0 x 0 + 0 x 0,794) : 27,994
= (1 + 2 + 0 + 0) : 27,994
= 0,107
p(“subsidi”|”negatif”) = (1 + N (“subsidi, dok 1”) p(“negatif”|”dok 1”)
+
N (“subsidi, dok 2”) p(“negatif”|”dok 2”) +
N (“subsidi, dok 3”) p(“negatif”|”dok 3”) ) : f(p)
= (1 + 2 x 0 + 0 x 1 + 0 x 0,205) : 27,994
= (1 + 0 + 0 + 0) : 27,994
= 0,035
p(“rakyat”|”positif”) = (1 + N (“rakyat”, dok 1”) p(“positif”|”dok 1”) +
N(“rakyat, dok 2”) p(“positif”|”dok 2”) +
N(“rakyat, dok 3”) p(“positif”|”dok 3”)) : f(p)
= (1 + 2 x 1 + 0 x 0 + 1 x 0,794) : 27,994
= (1 + 2 + 0 + 0,794) : 27,994
= 0,135
p(“rakyat”|”negatif”) = (1 + N (“rakyat, dok 1”) p(“negatif”|”dok 1”) +
N (“rakyat, dok 2”) p(“negatif”|”dok 2”) +
N (“rakyat, dok 3”) p(“negatif”|”dok 3”) ) : f(p)
= (1 + 2 x 0 + 0 x 1 + 1 x 0,205) : 27,994
= (1 + 0 + 0 + 0,205) : 27,994
= 0,043
p(“pemerintah”|”positif”) = (1 + N (“pemerintah”, dok 1”)
p(“positif”|”dok 1”) +
N(“pemerintah, dok 2”) p(“positif”|”dok 2”) +
N(“pemerintah, dok 3”) p(“positif”|”dok 3”)) : f(p)
= (1 + 0 x 1 + 3 x 0 + 0 x 0,794) : 27,994
= (1 + 0 + 0 + 0) : 27,994
=0,035
p(“pemerintah”|”negatif”) = (1 + N (“pemerintah, dok 1”)
p(“negatif”|”dok 1”) +
N (“pemerintah, dok 2”) p(“negatif”|”dok 2”) +
N (“pemerintah, dok 3”) p(“negatif”|”dok 3”) ) : f(p)
= (1 + 0 x 0 + 3 x 1 + 0 x 0,205) : 27,994
= (1 + 0 + 3 + 0) : 27,994
= 0,142
p(“bbm”|”positif”) = (1 + N (“bbm”, dok 1”) p(“positif”|”dok 1”) +
N(“bbm, dok 2”) p(“positif”|”dok 2”) +
N(“bbm, dok 3”) p(“positif”|”dok 3”)) : f(p)
= (1 + 0 x 1 + 2 x 0 + 0 x 0,794) : 27,994
= (1 + 0 + 0 + 0) : 27,994
= 0,035
p(“bbm”|”negatif”) = (1 + N (“bbm, dok 1”) p(“negatif”|”dok 1”) +
N (“bbm, dok 2”) p(“negatif”|”dok 2”) +
N (“bbm, dok 3”) p(“negatif”|”dok 3”) ) : f(p)
= (1 + 0 x 0 + 2 x 1 + 0 x 0,205) : 27,994
= (1 + 0 + 2 + 0) : 27,994
= 0,107
p(“positif”) = (1 + p (“positif”|”dok 1”) + p (“positif”|”dok 2”) +
p (“positif”|”dok 3”)) : (2+3)
= (1 + 1 + 0 + 0,794) : 5
= 2,794 : 5
= 0,558
p(“negatif”) = (1 + p (“negatif”|”dok 1”) + p (“negatif”|”dok 2”) +
p (“negatif”|”dok 3”)) : (2+3)
= (1 + 0 + 1 + 0,205) : 5
= 2,205 : 5
= 0,441
e. Langkah selanjutnya untuk menyelesaikan maximization step adalah
meng-update nilai probabilitas untuk setiap kategori yang ada:
𝑝 𝑐𝑖 =1 + 𝑝
|𝐷|𝑗=1 (𝑐𝑖|𝑑𝑗 )
𝐶 + |𝐷|
|C| adalah jumlah semua kategori
|D| adalah jumlah seluruh training dokumen
Model probabilistik setelah maximaization step.
Kelas P (Ci) P (Wkj|Ci)
aturan korupsi Subsidi rakyat pemerintah bbm
Positif 0,558 0,199 0,120 0,107 0,135 0,035 0,035
Negatif 0,441 0,050 0,2 0,035 0,043 0,142 0,107
Proses expectation step dan maximization step dilakukan dalam
beberapa iterasi sehingga peubahan nilai probabilitas p wkj ci dan
p(ci) tidak melebihi batas yang telahditentukan dari iterasi sebelumnya.
Namun pada contoh ini expectation step dan maximization step hanya
dilakukan dalam satu kali iterasi, sehingga langkah selanjutnya
penentuan kategori untuk dokumen 4:
𝑐∗ =arg max
ci ∈ C p wkj ci
k
x p(ci)
p(“positif”|”dok 4”) = p(“positif”) x p(“pemerintah”|”positif”) x
p(“rakyat”|”positif”) x p(“bbm”|”positif”)
= 0,558 x 0,035 x 0,135 x 0,035
= 9,2 x 10-5
p(“negatif”|”dok 4”) = p(“negatif”) x p(“pemerintah”|” negatif”) x
p(“rakyat”|” negatif”) x p(“bbm”|” negatif”)
= 0,441 x 0,142 x 0.043 x 0,107
= 2,8 x 10-4
Karena p(“positif”|”dok 4”) < p(“negatif”|”dok 4”) sehingga kelas “dok
4” adalah negatif.