1
I HC QUC GIA TP. H CHÍ MINH
TRNG I HC KHOA HC T NHIÊN
KHOA CÔNG NGH THÔNG TIN
 MÔN H THNG THÔNG TIN
LÊ NGUYN BÁ DUY –TRN MINH TRÍ
TÌM HIU CÁC HNG TIP CN PHÂN LOI
EMAIL VÀ XÂY DNG PHN MM MAIL CLIENT
 TR TING VIT
KHOÁ LUN C NHÂN TIN HC
TP. HCM, NM 2005

2
I HC QUC GIA TP. H CHÍ MINH
TRNG I HC KHOA HC T NHIÊN
KHOA CÔNG NGH THÔNG TIN
 MÔN H THNG THÔNG TIN
LÊ NGUYN BÁ DUY -0112050
TRN MINH TRÍ -0112330
TÌM HIU CÁC HNG TIP CN PHÂN LOI
EMAIL VÀ XÂY DNG PHN MM MAIL CLIENT
 TR TING VIT
KHOÁ LUN C NHÂN TIN HC
GIÁO VIÊN HNG DN
THY LÊ C DUY NHÂN
NIÊN KHÓA 2001-2005

10
1.1 Gii thiu:
Thi i ngày nay là thi i bùng n thông tin, Internet ã tr nên quen

1.1 Gii thiu: 10
1. 2 Yêu cu bài toán: 12
1.3 B cc khoá lu n : 12
Chng 2 : TNG QUAN 14
2.1 Các cách thc con ngi x lý vi spam : 15
2.2 Các phng pháp tip cn: 16
2.2.1 Complaining to Spammers' ISPs : 16
2. 2.2 Ma il Bl ackl i sts /Whit elis ts: 16
2.2.3 Mail volume : 18
2. 2.4 Signature/ Checksum schemes: 19
2.2.5 Genetic Algorithms: 20
2.2.6 Ru le-Based (hay là Heuristic): 21
2.2.7 Challenge-Response: 22
2.2.8 Machine Learning ( Máy hc ): 23
2.3 Phng pháp la chn : 24
2.4 Các ch sánh giá hiu qu phân loi email : 24
2.4.1 Spam Recall và Spam Precision: 24
2.4.2 T l li Err (Error) và t l chính xác Acc(Accuracy) : 25
2.4.3 T l li gia trng WErr (Weighted Error ) và t l chính xác gia trng (Weighted
Accuracy): 25
2.4.4 T s chi phí tng hp TCR (Total Cost Ratio ): 26
Chng 3 : GII THIU CÁC KHO NG LIU DÙNG KIM TH
PHÂN LOI EMAIL 28
3.1 Kho ng liu PU (corpus PU ): 29
3.1.1 Vài nét v kho ng liu PU: 29
3.1.2 Mô t cu trúc kho ng liu PU: 30
3.2 Kho ng liu email ch: 31
Chng 4 : PHNG PHÁP PHÂN LOI NAÏVE BAYESIAN VÀ NG
DNG PHÂN LOI EMAIL 33
4.1 Mt vài khái nim xác sut có liên quan 34

6.3.2 Phng pháp la chn lut yu : 70
Chng 7 : THC HIN VÀ KIM TH PHÂN LOI EMAIL DA
TRÊN PHNG PHÁP ADABOOST 73
7.1 Cài t b phân loi email da trên phng pháp AdaBoost: 74
7.1.1 Tp hun luyn mu và tp nhãn : 74
7.1.2 Xây dng tp lut yu ban u : 75
7.1.3 Th tc WeakLearner chn lut yu: 76
7.1.4 Phân loi email : 76
7.2 Th nghim hiu qu phân loi : 76
7.2.1 Th nghim vi kho ng liu pu: 76
7.2.2 Th nghim vi kho ng liu email ch: 79
7.3 u – nhc m ca phng pháp phân loi AdaBoost: 80
7.3.1 u m : 80
7.3.2 Khuyt m : 80
Chng 8 : XÂY DNG CHNG TRÌNH MAIL CLIENT TING VIT
H TR PHÂN LOI EMAIL 82
8.1 Chc nng: 83
8.2 Xây dng b lc email spam : 83
8.3 T chc d liu cho chng trình : 84
8.4 Giao din ngi dùng : 85
8.4.1 S màn hình : 85
8.4.2 Mt s màn hình chính : 85
Chng 9 : TNG KT VÀ HNG PHÁT TRIN 94
9.1 Các vic ã thc hin c : 95
9.2 Hng ci tin, m rng : 95
9.2.1 V phân loi và lc email spam: 95
9.2.2 V chng trình Mail Client: 96
TÀI LIU THAM KHO 97
Ting Vit : 97
Ting Anh : 97

nhn dng, …vi hiu qu cao. Ý tng là tìm cách xây dng mt b
phân loi nhm phân lai cho mt mu mi bng cách hun luyn nhng
mu ã có sn.
• c m
Phng pháp này có th áp dng  mc Server hay Client.
Hn ch là cn phi có mt kho ng liu (corpus) hun luyn ban
u  cho máy hc, vic hun luyn mt nhiu thi gian. Mt hn ch
na là hiu qu phân loi ph thuc vào kho ng liu dùng  hun
luyn.

36
4.2 Phng pháp phân loi Naïve Bayesian :
Phân loi Bayesian là phng pháp phân loi s dng tri thc các xác sut
ã qua hun luyn. Phng pháp này thích hp vi nhng lp bài toán òi hi phi
doán chính xác lp ca mu cn kim tra da trên nhng thông tin t tp hun
luyn ban u [16].
Theo Charles Elkan [16] cho
1
, ,
n
XX
là các thuc tính vi các giá tr ri rc
c dùng  doán mt lp riêng bit C cho mt mu, tp các lp mà mu có th
thuc v là C
{ }
12
, , ,
m
ccc
= . Cho mt mu hun luyn vi giá tr các thuc tính

nn
nn
PXxXx XxCc
PCcX x X x X x PCc
PXxXx Xx
=∧=∧∧==
==∧=∧∧===
=∧=∧∧=
Xác sut
(
)
PCc
=
c tính d dàng t tp d liu hun luyn. Xác
sut
(
)
11 22

nn
PXxXx Xx
=∧=∧∧= không thích hp  dùng cho vic quyt nh
lp ca C bi vì giá tr này nh nhau i vi mi lp c. Nh vy cn c dóan
lp ca C là da vào xác sut
(
)
11 22
|
nn
PX x X x X xCc

1122 22
|
| , |
nn
nn nn
PX x X x X xCc
PXxXx XxCcPXx XxCc
=∧=∧∧==
= = =∧∧= = =∧∧= =

47
*
,,
**
S
S
SN
SN
n
s
N
P Max M Min N
nn
sn
NN






chúng tôi s dng cu trúc d liu là bng bm.ng vi mi kho ng liu
email spam và non-spam chúng tôi xây dng mt bng bm tng
ng.Bng bm này s bao gm token và s email cha token hoc s ln
xut hin ca token trong tng kho ng liu tng ng, hoc có thng
thi cha ba thông tin này – tùy theo chúng ta áp dng cách tính xác sut
spam nào cho mi token. Nh vy mi token s có mt giá tr bm (xác
nh bng hàm bm tnh ngha ) tng ng vi v trí trên bng bm 
ta có th truy xut nhanh n phn t token trên bng. Mc ích xây dng
bng bm là  ti u hóa tc  truy xut các token trích t email cng nh
ti u thi gian xác nh mt email là spam hay không. Mi phn t ca
bng bm lu tr token, s ln xut hin (hoc s email có cha token ó ),
hoc xác sut spam ca nó, tùy theo mc ích x lý c th mà mi phn t

10
1.1 Gii thiu:
Thi i ngày nay là thi i bùng n thông tin, Internet ã tr nên quen
thuc và không th thiu i vi mi quc gia và xã hi. Liên lc qua Internet ã tr
nên ph bin, và email là mt phng tin liên lc có chi phí thp, nhanh chóng và
hiu qu nht trên Internet. Hng ngày mi ngi s dng email u nhn c mt
ng ln email, tuy nhiên không phi tt c các email mà ta nhn c u cha
thông tin mà ta quan tâm. Nhng email mà ta không mun nhn y là email Spam.
Ngc li, nhng email không phi là spam gi là non-spam – email hp lc
ngidùng chp nhn.
Spam chính là nhng email c phát tán mt cách rng rãi không theo bt
c mt yêu cu nào ca ngi nhn vi s lng ln (unsolicited bulk email
(UBE)), hay nhng email qung cáo c gi mà không có yêu cu ca ngi nhn
(unsolicited commercial email (UCE)) [1].
Nhiu ngi trong chúng ta ngh rng spam là mt vn  mi, nhng thc
ra nó ã xut hin khá lâu – ít nht là t nm 1975. Vào lúc khi thy, ngi dùng
hu ht là các chuyên gia v máy tính, h có th gi hàng tá thm chí hàng trm

phn hi là ã có th bù p chi phí u t [4].
 ngn chn spam, nhiu nhà khoa hc, các t chc, các cá nhân ã nghiên
cu và phát trin nhng k thut phân loi và lc email, tuy nhiên các spammer -
nhng ngi to nên spam và phát tán chúng cng tìm mi cách vt qua các b lc
này. Cuc chin gia các spammer và nhng ngi chng spam vn còn ang tip
din và dng nh không có hi kt. Thc t cho thy, nhu cu có mt phng
pháp và công c chng spam hu hiu là rt cn thit.
Xut phát t thc trng ó, nhóm chúng tôi chn hng nghiên cu ”Tìm
hiu các hng tip cn cho bài toán phân loi email và xây dng phn mm
Mail Client h tr ting Vit “ vi mc ích tìm hiu, th nghim các phng
pháp tip cn cho bài toán phân loi email , t ó thc hin phân loi email giúp
ngn chn email spam hiu qu.
1
/>2
/>
12
1.2 Yêu cu bài toán:
Yêu cu i vi mt h thng phân loi email và ngn chn email spam
ng nhiên là phân loi c email là spam hay non-spam, tó s có bin pháp
ngn chn email spam, hiu qu phân loi email phi kh quan, tuy nhiên không th
ánh i hiu qu phân loi email spam cao mà b qua li sai cho rng email non-
spam là spam, bi vì cùng vi vic tng kh nng phân loi email spam thì kh nng
xy ra li nhn nhm email non-spam thành email spam cng tng theo. Do ó yêu
cu i vi mt h thng phân loi email spam là phi nhn ra c email spam
càng nhiu càng tt và gim thiu li nhn sai email non-spam là email spam.
1.3 B cc khoá lun :
Chúng tôi chia khoá lun làm 9 chng
§ Chng 1 Gii thiu v tài, bài toán phân loi email.
§ Chng 2 Tng quan : trình bày mt s hng tip cn phân loi email
và chng email spam,ng thi có s nhn xét ánh giá các phng

v Kt qu thc hin kim th vi thut toán ADaBoost with real value
predictions
Ng liu T=5
T=10 T=50 T=100 T=200 T=500
HTML SàS 48 48 49 49 49 49
SàN 2 2 1 1 1 1
NàN 49 49 49 49 49 49
NàS 1 1 1 1 1 1
SR 96.00% 96.00% 98.00% 98.00% 98.00% 98.00%
SP 97.96% 97.96% 98.00% 98.00% 98.00% 98.00%
TEXT SàS 84 93 98 98 98 98
SàN 14 5 0 0 0 0
NàN 98 97 98 99 99 99
NàS 2 3 2 1 1 1
SR 85.71% 94.90% 100.00% 100.00% 100.00% 100.00%
SP 97.67% 96.88% 98.00% 98.99% 98.99% 98.99%
ng 7-3 kt qu th nghim phân loi email vi ng liu email ch bng thut toán
AdaBoost with real-value predictions
v Kt qu thc hin kim th vi thut toán ADaBoost with discrete
predictions
Ng liu T=5
T=10 T=50 T=100 T=200 T=500
HTML SàS 48 49 50 50 50 50
SàN 2 1 0 0 0 0
NàN 49 49 49 49 49 49
NàS 1 1 1 1 1 1
SR 96.00% 98.00% 100.00% 100.00% 100.00% 100.00%
SP 97.96% 98.00% 98.04% 98.04% 98.04% 98.04%

85

of a NaiveBayesian and A memory-based approach. In 4
th
PKDDsWorkshop on
MachineLearning and Textual Information
Access.
[18] I.Androutsopoulos,G.Paliouras,and E.Michelakis.Learning to filter unsolicited
commercial e-mail.Technical report,National Centre for Scientific
Research“Demokritos”,2004.

17
lp và da vào ó ta có th ngn chn nhn email spam c phát tán
t nhng ni này.
Vic thit lp danh sách các a ch email en hay máy ch gi
email này s do mt nhóm tình nguyn xác nhn. Mt s nhà cung cp
dch v mng ISP s dùng danh sách en kiu này và tng t chi
nhn email t nhng máy ch hay email trong dánh sách ó. Nh
vy, nhng email spam sc phân loi và chn ngay ti máy ch
nhn email.
• c m:
Phng pháp này bc u loi c khong 50% [5] email
spam.
Khuyt m ca phng pháp này là chúng không thng
u vi hn mt na s server mà spam ang s dng hin nay. Và
nu xác nhn sai danh sách en này thì vic dùng nó ng ngha vi
vic b qua mt lng ln email hp l.
Phng pháp này có th b qua mt nu nh các spammer gi
li email thông qua mt máy ch SMTP (Simple email Transfer
Protocol) có ngun gc hp pháp không k tên trong danh sách
“Blacklist”.
Ngoài ra, danh sách này không ch t chi nhn email t các

gi email qung cáo phi thit lp nhiu kt ni hn  gi mt s
ng email ging nhau. u này làm cho các email qung cáo ó d
dàng b phát hin da trên vic phân tích s lng email.
Mt hn ch ca b lc này là t l chp nhn phân loi sai
FAR (false acceptance rate) ca nó còn khá cao. Vi:
3


102
Kt qu th nghim vi 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 57 56 56 56 56 55 56 56 56
N 0 1 1 1 1 2 1 2 1
N 55 53 54 56 55 55 54 54 53
S 2 4 3 1 2 2 3 3 4
SR 100.00% 98.25% 98.25% 98.25% 98.25% 96.49% 98.25% 96.55% 98.25%
SP 96.61% 93.33% 94.92% 98.25% 96.55% 96.49% 94.92% 94.92% 93.33%
TCR 28.5 11.4 14.25 28.5 19 14.25 14.25 11.6 11.4
9S 56 56 56 54 55 55 55 55 55
N 1 1 1 3 2 2 2 2 2
N 56 53 54 56 55 55 54 54 53
S 1 4 3 1 2 2 3 3 4
SR 98.25% 98.25% 98.25% 94.74% 96.49% 96.49% 96.49% 96.49% 96.49%
SP 98.25% 93.33% 94.92% 98.18% 96.49% 96.49% 94.83% 94.83% 93.22%
TCR 5.71.5405412.035714 4.75 2.85 2.851.9655171.965517 1.5
999S 52 54 54 52 51 54 55 55 55
N 5 3 3 5 6 3 2 2 2
N 56 54 54 56 55 56 55 54 53

432 0
549
0100.00%100.00%
PU2
126 513 14
57
12 2
56
1 85.71% 92.31%
126 513
126 0
513
0100.00%100.00%
PU3
1638 2079 182 231
176 6
216
15 96.70% 92.15%
1638
20791638 0
2079
0100.00%100.00%
PUA
513 513 57
57
56 1
38
19 98.25% 74.67%
513 513
513 0

PU3
1638
2079
182 231 178
4
217
14 97.80% 92.71%
1638 2079
1634
4 2079 0 99.76% 100.00%
PUA
513 513
57
57 56
1 40 17 98.25% 76.71%
513 513 513
0
513
0
100.00%
100.00%

104
c) T=100
Ng
 liu
 email hc S
 email kim th
S->SS->NN->NN-
>S

215
16 95.60% 91.58%
1638
20791618
20 2067
12 98.78% 99.26%
PUA
513 513 57
57
56 1
38
19 98.25% 74.67%
5
13 513
513 0
513
0100.00%100.00%
d) T=50
Ng
 liu
 email hc S
 email kim th
S->SS->NN->NN-
>S
SR SP
Spam
Non-
spam
Spam Non-spam
PU1

57
57 0
37
20100.00% 74.03%
513 513
512 1
510
3 99.81% 99.42%
e) T=10
Ng
 liu
 email hc S
 email kim th
S->SS->NN->NN-
>S
SR SP
Spam
Non-
spam
Spam Non-spam
PU1
432
549
48 61 45
3
565
93.75% 90.00%
432 549
395 37
515

1
29 28
98.25% 66.67%
513 513
510
3 437
76
99.42% 87.03%
f) T=5
Ng
 liu
 email hc S
 email kim th
S->SS->NN->NN-
>S
SR SP
Spam
Non-
spam
Spam Non-spam
PU1
432
549
48 61 44
4
538
91.67% 84.62%
432 549
388 44
493

• c m:
6
/>
23
Li th ca h thng này là  lt li rt ít spam. u bt li ca
nó can thip thô bo n ngi gi. Bng cách s dng h thng này, ta
cn xác nh rõ ai là ngi gi email.
Mt m bt li khác ca h thng này là có nhiu email non-
spam b loi b và thi gian trì hoãn quá lâu. Ví d nh mt ngi mun
mi bn i d tic nhng ngi bn y s ch thy email tr li ca bn
vào ngày hôm sau và n lúc ó thì ã quá tr.
Nhiu trng hp ngi gi s không tr li cho các thông p
kiu này và email h gi s b tht lc.
S dng phng pháp dng này chng khác nào ta ang t cô lp
chính mình vi mi ngi xung quanh. H thng này s ging nh bc
ng bao quanh th gii luôn mun gi thông p cho ta.
2.2.8 Machine Learning ( Máy hc ):
• Ý tng:
Áp dng các png pháp máy hc trong các bài toán phân loi,
c bit là phân loi vn bn vào bài toán phân loi email, các thut toán
máy hc nh Naïve Bayesian [9],[17],[18] AdaBoost [13], Suppor
Vector Machine[18], , ã c s dng trong lnh vc phân loi vn bn,
nhn dng, …vi hiu qu cao. Ý tng là tìm cách xây dng mt b
phân loi nhm phân lai cho mt mu mi bng cách hun luyn nhng
mu ã có sn.
• c m
Phng pháp này có th áp dng  mc Server hay Client.
Hn ch là cn phi có mt kho ng liu (corpus) hun luyn ban
u  cho máy hc, vic hun luyn mt nhiu thi gian. Mt hn ch
na là hiu qu phân loi ph thuc vào kho ng liu dùng  hun

nn
−>
−> −>
=
+
Công thc 2-1 :Công thc tính Spam Recall

25
SS
SS NS
n
SP
nn
−>
−> −>
=
+
Công thc 2-2 : Công thc tính Spam Precesion
Vi :
ü n
SS >−
là s email là spam mà b lc nhn ra là spam
ü n
NS >−
là s email là spam mà b lc nhn ra là email non-spam
ü n
SN >−
là s email non-spam mà b lc nhn ra là spam
2.4.2 T l li Err (Error) và t l chính xác Acc(Accuracy) :
Trong vic phân loi email, hiu qu phân loi da vào t l chính xác (Acc)

>−
là s email là non-spam và c b lc nhn ra là non- spam
•
SN
n
>−
là s email là non-spam mà b lc nhn ra là spam
•
SS
n
>−
là s email là spam mà c b lc nhn ra là spam
•
NS
n
>−
là s email là spam mà c b lc nhn ra là non-spam
2.4.3 T l li gia trng WErr (Weighted Error ) và t l chính xác
gia trng (Weighted Accuracy):
Trong phân loi email có hai loi li : li nhn spam ra non-spam (false
negative) và li nhn non-spam ra spam(false positive) [3]. Li th hai là li