37
Bng cách  qui, vit tha s th hai trong tích trên nh sau :
(
)
22
|
nn
PXx XxCc
=∧∧ = ==
(
)
(
)
2233 33
| , |
nn nn
PXxXx XxCcPXx XxCc
= =∧∧= = =∧∧= =
và c tip tc
nh vy. Phng pháp phân loi Naïve Bayesian gi thit rng vi mi
i
X
kt qu
tác ng ca nó là c lp vi các
j
X
khác, nh vy chúng ta tha nhn rng:
(
)
(

== == === ==
∏
Mi mt tha s trong tích trên có thc tính d dàng t tp hun luyn
ban u, nh vy phng pháp Naïve Bayesian gim s phc tp ca vic tính toán
giá tr xác sut
(
)
11 22
|
nn
PX x X x X xCc
=∧=∧∧==
4.3 Phân loi email bng phng pháp Naïve Bayesian :
ây mi mu mà ta xét chính là mi mt email, tp các lp mà mi
email có th thuc v là C ={spam, non-spam}
Khi ta nhn c mt email, nu ta không bit mt thông tin gì v nó,
do ó khó có th quyt nh chính xác email này là spam hay không .
Nu nh ta có thêm c m hay thuc tính nào ó ca email thì ta
có th nâng cao hiu qu nhn c email là spam Mt email có nhiu c
im nh : tiêu , ni dung, có ính kèm tp tin hay không,…Ta có th da
vào các thông tin này  nâng cao hiu qu phân lai email spam. Mt ví d
n gin : nu ta bit c rng 95 % email html là email spam, và ta li
nhn c mt email html, nh vy có th da vào xác sut bit trc 95%
email html là email spam  tính c xác sut email mà ta nhn c là
spam, nu xác sut này ln hn xác sut email ó là non-spam, có th kt

38
lun rng email ó là spam, tuy nhiên kt lun này không chính xác lm
Nhng nu ta cóc nhiu xác sut bit trc nh vy, thì kt lun s tr
nên áng tin cy hn.  có c các xác sut bit trc này, s dng

i
X có trong email, ngc li
i
X =0.
Ta tính giá tr tng h MI (X,C) (Mutual Information) mà mi
mt i din ca
X
thuc v loi C nh sau:
{ }
0,1
(,)
( , ) ( , ).log
( )()
x
PXxCc
MIXC PX xCc
PX xPCc
∈
==
= ==
==
∑
{ }
,
c spam non spam
∈−
Công thc 4-5 :công thc tính  tng h MI
Sau ó ta chn các thuc tính có giá tr MI cao nht.Các xác sut
P(X), P(C), P(X,C)c tính da trên d liu hc
Da vào công thc xác sut Bayes và công thc xác sut y  ta

Thc t thì rt khó tính c xác sut
(|)
PXC
u ur
bi vì giá tr s
ng ca các vector rt nhiu và nhiu vector him khi hay thm chí
không xut hin trong tp d liu hun luyn.Nhã nói, phng pháp
Naïve Bayesian gi thit rng
1
X
,
2
X , ,
n
X là nhng bin cc lp, do
ó chúng ta có th tính c xác sut  trên nh sau:
{ }
i1
,
1
().( |)
(|)
().( |)
n
ii
n
ii
k spam non spam
i
PCc PX xCc

chp nhn mt email spam vt qua b lc nhng không chp nhn mt
email hp l quan trng li b b lc chn li.
Gi s N
→
S và S
→
N tng ng vi hai li sai trên ây S dng
lut quyt nh Bayes da trên chi phí [9], ta gi s rng li N
→
S có chi
phí gp
λ
ln li S
→
N, chúng ta phân loi mt email là spam da vào
tiêu chun sau:

40
( )|)
( |)
P C spam X x
P C non spam X x
λ
==
>
=−=
uurr
uurr
Công thc 4-8
Mà

42
5.1 Cài t chng trình phân loi email da trên phng
pháp phân loi Naïve Bayesian:
5.1.1 Khái nim Token :
 xem xét ni dung email chúng tôi dùng khái nim “token”
Các “token” có th xem nh là các t cn xem xét mà ta tách ra t ni
dung ca email. Vi các kí t ch, kí t s, kí t ‘$', kí t gch ngang ‘-’, kí
t gch di ‘_’, kí t nháy n ‘’’ là nhng kí t cu to thành token. Còn
nhng kí t còn li nh khong trng, kí t ‘*’, kí t ‘:’, … c xem là kí t
 tách t hay phân cách các t. Vi nhng t tách c mà gm toàn kí s
thì không c xem là token (ví d: “12345”).
Ví d ta có các token sau:
“qvp0045”, “ indira”, “mx-05”, “$7500”, “3d0725”, “ platinum”.
Nu ta có mt chui sau: “ />” thì ta s có
các token tng ng là: “http”, “www”, “27meg”, “com”, “foo”.
5.1.2 Vector thuc tính :
Nhã nói  mc 4.3.1, ta chuyn mi mt email sang mt
vector x
r
=(
1
x ,
2
x , ,
n
x ) vi
1
x ,
2
x , ,

th bit c kh nng email ó là spam là bao nhiêu,iu này hp lý
n là ch s dng hai giá tr 0 và 1.Vi không gian vector c trng
X
r
,
chúng tôi chn n là s các thuc tính ca
X
r
 th nghim ln lt là 10,
15 và 20. Chn n sao cho không ln quá, nu n ln có kh nng nhng
thuc tính không phi là c trng, nh vy s làm “nhiu “ kh nng
phân loi úng.Ngc li nu chn n quá nh, ta s không có c s
cn thit các thuc tính.
5.1.3 Chn ngng phân loi :
Chúng tôi tin hành th nghim vi giá tr
λ
ln lt là 1, 9 và 999,
nh vy ngng phân loi t xác nh mt email là spam ln lt là 0.5, 0.9,
0.999.
5.1.4 Cách thc hin :
Chúng ta s bt u vi hai kho ng liu email : kho ng liu email
spam và kho ng liu email non-spam. S lng email trong mi kho ng
liu ban u không hn ch. Nu kho ng liu càng ln thì hiu qu lc
email s càng cao. T hai kho ng liu này, chúng tôi phân tích và duyt
qua tt c các token bao gm c phn tiêu  ca email.i vi nhng
email html, chúng tôi thc hin bóc tách các th html  ly ni dung gia
các th.
Sau ó ta tính xác sut spam ca mi token ã c phân tích, xác
sut này chính là xác sut mt email ch cha token ó và là email spam.
Nh vy mu cht ây là ta phi tính ra c xác sut spam ca

S
N
s
) và
N
N
n
bng Min(1,
N
N
n
)
Do ó Công thc 5-1vit li nh sau:
(1, )
(,)
(1, ) (1, )
S
S
S
SN
Min
N
P X w C spam
n
Min Min
NN
===
+
công thc 5-2
Theo cách trên thì chúng ta ánh giá kh nng spam ca mt token

ü
S
N
là tng s email ca kho ng liu hc spam
ü
N
N là tng s email ca kho ng liu hc non-spam
Tuy nhiên, ta nhn thy rng công thc trên ã ánh giá kh nng
spam ca mi token là nh nhau vi token xut hin 1 ln trong 1 email và
token xut hin 100 ln trong 1 email, bi vì  c hai trng hp, ta u ch
tính thêm vào s email cha token là 1 mà thôi
Chúng ta có th kt hp hai cách tính  trên, có th s dng c
nhiu thông tin v token hn. Chúng tôi  xut thêm mt công thc na -
c xem là s kt hp gia hai công thc trên
*
(,)
**
S
S
SN
SN
n
b
N
P X w C spam
nn
bg
NN
===
+

mt token nào ó hay xác sut spam ca mt token nh sau:
Tính theo công thc 5-2, ta có :
(1, )
,,
(1, ) (1, )
S
S
S
SN
Min
N
P Max M Min N
n
Min Min
NN






=


+




Công thc 5-5 :công thc tính xác sut spam ca token da trên s ln xut hin

,,
**
S
S
SN
SN
n
s
N
P Max M Min N
nn
sn
NN






=


+




Công thc 5-7 :ctính xác sut spam ca token da trên s ln xut hin và s email cha nó
Vi :
ü s là s ln xut hin ca token trong kho ng liu hc spam


48
ca bng bm s mang nhng thông tin khác nhau. Bng bm c mô t
nh sau:
Hình 5-1Mô t cu trúc bng bm
Sau khi có 2 bng bm tng ng vi hai kho ng liu email, ta s
xây dng bng bm th ba. Mi phn t trong bng bm này s lu nhng
thông tin gm: token và kh nng (xác sut) spam ca token.Tuy nhiên 
vic thc hin tin li và không phi xét quá nhiu token, chúng tôi ch
xem xét nhng token mà s ln xut hin ca nó hoc s email cha nó
trong c s d hc ban u ln hn mt ngng nào ó, vi nhng token
mà tng s ln xut hin hoc tng s email cha nó nh hn ngng này,
chúng tôi không tính xác sut cho token ó. u này là hp lý bi vì
nhng token có tng s ln xut hin ( hoc tng s email cha nó quá ít
thì cng không áng  xem xét n, do ó s giúp gim bt s token cn
tính xác sut cng nh dung lng lu tr cho d liu  bng bm th ba
này.ây chúng tôi th nghim ln lt hai ngng 3 và 5, kt qu thc
hin  hai ngng này gn nh là tng ng nhau, cui cùng chúng tôi
chn giá tr 3.
Theo Paulgraham [7] thì chúng ta cn hn ch loi li false positive
(nhn email non-spam thành email spam ), do ó s ln xut hin ca
các token hoc s email cha token trong kho ng liu non-spam sc

49
nhân vi mt trng s W,iu này giúp phân bit c gia nhng token
thnh thong xut hin trong các email hp l vi nhng token hu nh
không xut hin, chúng tôi th nghim ln lt vi hai giá tr 1 và 2.
Ví d thông tin bng bm th 3:
Token: Kh nng spam :
madam 0.99

token ca ta.Mt token cha tng xut hin trong kho ng liu hc thì kh
ng spam ca nó tng i thp [7], chúng tôi ly giá tr trung tính 0.4.
Tó chúng tôi tính kh nng tng hp mt email cha n token này là
spam.
Cách tính kh nng tng hp :chúng tôi da vào Công thc 4-7
{ }
i1
,
1
().( |)
(|)
().( |)
n
ii
n
ii
k spam non spam
i
PCc PX xCc
PCcXx
PCk PX xCk
=
∈−
=
= ==
= ==
= ==
∏
∑
∏

madam 0.99
promotion 0.99
shorstest 0.047225013
Xác sut mt email là Spam là :0.6
à Kh nng kt hp
0.99*0.99*0.047225013*0.6
0.6*0.99*0.99*0.047225013 (1-0.6)*(1-0.
99)(1-0.99)(1-0.047225013)
=
+
Sau khi có kh nng tng hp, chúng tôi so sánh vi các giá tr
ngng ( ã nói  mc 4.3.1)  phân loi email spam hay non-spam, nu
xác sut spam tng hp ca email ln hn ngng t chúng tôi kt luân
email ó là spam, ngc li email ó là non-spam.

51
5.2 Th nghim hiu qu phân loi
5.2.1 Th nghim vi kho ng liu pu:
Bi vì kho ng liu hc và kim th là s, do ó chúng tôi thay i v
cách ly token, ây chúng tôi xem token là các con s, và du hiu tách
token là các khong trng.
5.2.1.1 Kch bn kim th :
Chúng tôi th nghim nhân trng s non-spam W vi 1 và 2
Vi mi W, chúng tôi th nghim vi
λ
ln lt vi các giá tr 1, 9,
và 999
ng ng vi mi giá tr
λ
và W chúng tôi thc hin tính xác sut

999 S 43 43 43 43 43 43 45 45 47
N 5 5 5 5 5 5 3 3 1
N 61 61 61 61 61 61 61 61 61
S 0 0 0 0 0 0 0 0 0
SR 89.58% 89.58% 89.58% 89.58% 89.58% 89.58% 93.75% 93.75% 97.92%
SP 100.00% 100.00% 100.00% 100.00% 100.00% 100.00% 100.00% 100.00% 100.00%
TCR 9.6 9.6 9.6 9.6 9.6 9.6 16 16 48
ng 5-1 Kt qu kim th phân lai email bng phng pháp phân lai Naïve Bayesian trên
kho ng liu PU1

53
Hình 5-2 Lc  so sánh các ch s spam recall (SR) và spam precision (SP) theo s token th
nghim trên kho ng liu PU1 vi công thc 5-7 (
9
λ=
)
Hình 5-3 Lc  ch s TCR theo s token th nghim trên kho ng liu PU1 vi công thc 5-7
(
9
λ=
)

54
v Kt qu kim th trên PU2:
Công thc 5-5 Công thc 5-6 Công thc 5-7
λ
10
15 20
10 15
20

57.14% 64.29%
50.00% 57.14%
57.14% 57.14%
64.29%
35.71%
SP
100.00%
100.00% 100.00%
100.00% 100.00%
100.00%
100.00% 100.00% 100.00%
TCR
2
2.333333 2.8
2
2.3333332.3333332.333333
2.8
1.555556
9SS
7
8 8
7
888
8
5
N
7
6 6
7
566

2.3333332.333333
2 2.6
2.3333332.333333
2.333333
1.555556
999SS
7
8 8
7
678
5
5
N
7
6 6
7
876
9
9
N
57
57 57
57 57
57
57 57 57
S
0
0 0
0
000

)
Hình 5-5 Lc  ch s TCR theo s token th nghim trên kho ng liu PU2 vi công thc 5-5
(
9
λ=
)

56
v Kt qu kim th trên PU3:
Công thc 5-5 Công thc 5-6 Công thc 5-7
λ
10
15 20
101520101520
1SS 169 168 168 167
169
165
165
172 170
N
13
14 14
151317171012
N 228 228 227 228
228
229
226
222 224
S 3343
3

181619171112
N 229 228 227 228
229
229
227
222 225
S 2343
2
2
4
9
6
SR 91.76% 92.31% 92.31%
90.11% 91.21%
89.56%
90.66%
93.96%
93.41%
SP 98.82% 98.25% 97.67%
98.20% 98.81%
98.79%
97.63%
95.00%
96.59%
TCR 5.5151524.439024 3.644.044444
5.352941
4.918919
3.433962
1.978261
2.757576

96.55%
96.57%
TCR 0.0902330.0902330.0903230.090099
0.089921
0.089921 0.045330.030293
0.030298
ng 5-3 Kt qu kim th phân lai email bng phng pháp phân lai Naïve Bayesian trên
kho ng liu PU3

57
Hình 5-6 Lc  so sánh các ch s spam recall (SR) và spam precision (SP) theo s token th
nghim trên kho ng liu PU3 vi công thc 5-6 (
9
λ=
)
Hình 5-7 Lc  ch s TCR theo s token th nghim trên kho ng liu PU3 vi công thc 5-6
(
9
λ=
)

58
v t qu kim th trên PUA:
Công thc 5-5 Công thc 5-6 Công thc 5-7
λ
10 15 20 10 15 20 10 15 20
1 S 46 46 46 43 42 41 50 48 46
N 11 11 11 14 15 16 7 9 11
N 57 56 57 57 57 57 56 56 57
S 0 1 0 0 0 0 1 1 0

)

60
Nhn xét :kt qu kim th trên các kho ng liu PU là khá tt, hiu
qu phân loi gia các công thc là không quá khác bit, vi cách chn
9
λ=
và
1
λ=
hiu qu hn vi
999
λ=
, theo chúng tôi thì kho ng liu
không ln lm nên s dng
999
λ=
thì không hiu qu bng. V cách chn
s token, hiu qu phân loi khi chn s token là 10, 15 hay 20 cng không
khác bit lm.
5.2.2 Th nghim vi kho ng liu email ch :
5.2.2.1 Kch bn kim th :
Sau khi ã th nghim vi kho ng liu s, chúng tôi chn mt b
(
λ
, n, W)  kim th vi kho ng liu email ch.
Chúng tôi th nghim vi b d liu
λ
= 9, s token là 15, trng s
non-spam là 2.

• Mt u im ca b lc Bayes là nó cho phép hc spam. Ngha là, khi có
mt email spam vt qua c b lc thì ngi dùng có thánh du
spam cho email ó và b lc s t phân tích email spam ó và cp nht
thêm vào kho ng liu spam.
• Hiu qu phân loi là khá cao
Công thc 5-5 Công thc 5-6 Công thc 5-7
TEXT S 96 94 96
N 2 4 2
N 99 99 99
S 1 1 1
SR 97.96% 95.92% 97.96%
SP 98.97% 98.95% 98.97%
TCR 32.66667 19.6 32.66667
HTML SS 32 24 23
N 18 26 27
N 50 50 50
S 0 0 0
SR 64.00% 48.00% 46.00%
SP 100.00% 100.00% 100.00%
TCR 2.777778 1.923077 1.851852