1
A萎I H窺C QU渦C GIA TP. H唄 CHÍ MINH
TR姶云NG A萎I H窺C KHOA H窺C T衛 NHIÊN
KHOA CÔNG NGH烏 THÔNG TIN
D浦 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
J姥 TR営 TI蔭NG VI烏T
KHOÁ LU一N C盈 NHÂN TIN H窺C
TP. HCM, N;M 2005

2
A萎I H窺C QU渦C GIA TP. H唄 CHÍ MINH
TR姶云NG A萎I H窺C KHOA H窺C T衛 NHIÊN
KHOA CÔNG NGH烏 THÔNG TIN
D浦 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
J姥 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Ê A永C DUY NHÂN
NI ÊN KHÓA 2001-2005

3
N云I C謂M 愛N
Trc tiên, chúng tôi xin chân thành cm n thy Lê c Duy Nhân, ngi

2. 2.2 Ma il Bl ackl i sts /Whit el ists: 16
2.2.3 Mail volume : 18
2. 2.4 Sign ature/ 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
4.1.1 nh ngha bin c, xác sut : 34
4.1.2 Xác sut có u kin, công thc xác sut y  – công thc xác sut Bayes35
4.2 Phng pháp phân loi Naïve Bayesian : 36
4.3 Phân loi email bng phng pháp Naïve Bayesian : 37
4.3.1 Phân loi email da trên thut toán Naïve Bayesian 38
4.3.2 Chn ngng phân loi email : 39
Ch逢挨ng 5 : TH衛C HI烏N VÀ KI韻M TH盈 PHÂN LO萎I EMAIL D衛A

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 d i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
Ph映 l映c 99

6
Ph映 l映c 1 : K院t qu違 th穎 nghi羽m phân lo衣i email b茨ng ph逢挨ng pháp Bayesian
v噂i kho ng英 li羽u h丑c và ki吋m th穎 pu 99
Ph映 l映c 2 : K院t qu違 th穎 nghi羽m phân lo衣i email b茨ng ph逢挨ng pháp
AdaBoost v噂i kho ng英 li羽u h丑c và ki吋m th穎 pu 103

9
λ=
) 57
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
λ=
) 57
Hình 5-8 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 PUA vi công thc 5-5 (
9
λ=
) 59
Hình 5-9 Lc  ch s TCR theo s token th nghim trên kho ng liu PUA
vi công thc 5-5 (
9
λ=
) 59

8
Danh mc các bng:
Bng 3-1Mô t cu trúc kho ng liu PU 31
B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 52
Bng 5-2 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 PU2 54
B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 56
Bng 5-4 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 PUA 58

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
email n các nhóm tin (newsgroup) và spam hu nh ch liên quan n các email
gi n các nhóm tin Usenet, gây ra tình trng không th kim soát c các email
nhn. Sau ó các bin pháp trng tr v mt xã hi và hành chính ã có tác dng,
th phm ã b trng pht , công khai hay bí mt, nhng ngi này nhanh chóng
c a vào mt danh sách, và mt k thut lc spam sm nht xut hin ó là
”bad sender” – lc email ca nhng ngi gi c xem là xu.
WWW(World-Wide Web) ã mang th gii Internet n nhiu ngi, và h
qu ca nó là nhiu ngi không phi là chuyên gia trong th gii máy tính cng
c tip xúc nhiu vi Internet, nó cho phép truy cp n nhng thông tin và dch
v mà trc ây là không c phép. Ch trong vòng 2-3 nm chúng ta ã chng
kin s bùng n s ngi s dng Internet và tt nhiên là nhng c hi qung cáo
trên y. Và spam ã phát trin mt cách nhanh chóng tây, nhng k thut ngn

11
chn spam trc ây ã không còn thích hp. Spam thng theo sau nhng qung
cáo thng mi chèo kéo khách hàng ( nhng email qung cáo thng mi c gi
mà không có yêu cu ) [2]. Spam ã và ang gây tác hi n ngi s dng Internet
và tc ng truyn Internet. Vi ngi s dng email, spam gây cho h cm
giác bc bi và phi mt thi gian và tin bc  xóa chúng,ôi khi h có th b
mt nhng email quan trng ch vì xóa nhm, tc  trên mng xng sng ca
Internet (Internet Backbone) cng b spam là cho chm li vì s lng spam c
chuyn i trên mng là cc ln [3]. Theo thng kê ca ZDNet  thi m nm
2004, mi ngày có khong 4 t email spam c phát tán qua Internet, trên 40%
ng email trên mng là spam
1
, gn ây ã t con s 50%
2
. Cho dù c nhn
din là “k thù ca cng ng“(“public enemy”) Internet, nhng spam ã và ang

và chng email spam,ng thi có s nhn xét ánh giá các phng
pháp, tó có c s chn la hng tip cn gii quyt vn .
§ Chng 3 : Gii thiu và mô t v c s d liu dùng  hc và kim th
Hai chng tip theo, chúng tôi trình bày c s lý thuyt và thc hin
phân loi email theo phng pháp Bayesian.
§ Chng 4: Trình bày c s lý thuyt cho hng tip cn da trên phng
pháp Bayesian.
§ Chng 5: Thc hin phân loi email d trên phng pháp Bayesian và
kim th.
Hai chng tip theo, chúng tôi trình bày c s lý thuyt và thc hin
phân loi email theo phng pháp AdaBoost
§ Chng 6: Trình bày c s lý thuyt cho hng tip cn da trên thut
toán AdaBoost.
§ Chng 7: Thc hin phân loi d trên phng pháp AdaBoost và kim
th.

13
§ Chng 8: Xây dng phn mm email Client ting Vit h tr phân loi
email
§ Chng 9: Tng kt, trình bày v nhng vn ã thc hin, nhng kt
qut c, xut hng m rng, phát trin trong tng lai.

14
Ch逢挨ng 2 : T蔚NG QUAN

15
2.1 Các cách th泳c con ng逢運i x穎 lý v噂i spam :
Trên th gii ã có nhiu t chc, công ty phát trin nhiu cách thc khác
nhau  gii quyt vn  spam. Có nhiu h thng c xây dng sn mt “danh
sách en” (Blacklist ) cha các tên min mà tó spam c to ra và phát tán, và

li vi dch vó và dch v này s t chi cung cp dch v cho các
spammer dùng gi spam.
• A員c 8k吋m :
ây cng là gii pháp chng spam u tiên. Nhng li than
phin cng có tác dng ca nó. Nhng ni gi spam s b vô hiu hóa,
khi ó các spammer phi ng ký mt tài khon mi vi nhà cung cp
dch v ISP  có th tip tc phát tán các email spam ca mình. Dn
dn vic chuyn ni cung cp dch v s làm các spammer tn nhiu
chi phí và khi chúng ta phát hin càng sm thì chi phí trên ca các
spammer càng tng nhiu.
Cách này cng gp phi nhng khó khn ó là không th bit
chính xác nhng email spam này thc sn tâu do các spammer
ã khéo léo che giu i phn header ca email n i ngun gc. Do
ó cn phi hiu bit v header ca email  hiu rõ email spam này
tht s n t âu.
2.2.2 Mail Blacklists /Whitelists:
• Ý t逢荏ng:
Mt danh sách en (Blacklist) các a ch email hay các máy
ch email (mail server) chuyên dùng ca các spammer sc thit

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.
• A員c 8k吋m:

c t mt máy ch (host) c th trong các ln kt ni sau cùng
(cách này ã c b lc Spamshield
3
ca Kai s dng. Nu s
ng email nhn c ln hn mt ngng nào ó thì các email ó
sc phân loi là spam.
• A員c 8k吋m:
B lc t ra hiu qu trong vic phân loi úng tt c các email
hp l trong iu kin vi mt ngng phân loi  cao.Nu b lc
c s dng cho cá nhân, thì nó hot ng rt hiu qu. Có th xem
ây là mt u im ca b lc bi vì vi email cá nhân thì nhng k
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


19
SN
S
n
FAR
n
→
=
SN
n
→

B lc này c ng dng ti mc server,c các nhà cung
cp dch v mng (ISP) s dng.
Theo P.Graham [5], b lc kiu này ch lc khong 50-70%
spam
u im ca b lc này là ít khi phân loi sai email non-spam.
Brightmail
4
là phn mm chng spam da trên hng tip cn
này. Cách hot ng ca nó là to ra mt mng li các a ch email
gi. Bt kì email nào c gi n nhng a ch này thì u là spam
vì vi nhng email hp l thì him khi li c gi n nhng a ch
gi này. Vì vy, khi b lc nhn thy nhng email ging nhau gi n
mt a ch giã c to ra này thì nó s lc ra B lc phân bit
nhng email ging nhau da vào “signatures” ca chúng.
2.2.5 Genetic Algorithms:
• Ý t逢荏ng:
B lc da trên thut toán di truyn (Genetic Algorithms) s
dng các b nhn dng c trng (“fearture detectors”)  ghi m
(score) cho mi email. Thc t, nhng “fearture detectors” này là mt
tp các lut c xây dng da trên các kinh nghim ã có (empirical
rules) và áp dng vào mi email  thu v mt giá tr s.
Thut toán di truyn này c biu din là nhng cây (trees)
và c kt hp vi mt tp hun luyn cùng vi mt hàm thích hp
“fitness function”.
4


21
 ch tin hóa (Evolutionary mechanism) ca thut toán
:thut tóan thc hin hai thao tác c bn là phép lai “crossover” và t

nhau rt nhiu. Cách n gin nht là loi b các email mà có cha
nhng t xu nào ó (ví d nhng t mà thng xut hin nhiu hay
ch xut hin trong spam). Nhng ây cng là im yu  các
spammer có th li dng  qua mt các b lc kiu này bng cách c
gng tránh s dng nhng t xu và thay bng nhng t “tt” -c
s dng nhiu trong email non-spam. Trong khi ó các email non-
spam thì b loi b nu vô tình cha mt vài t “xu” dng này. iu
này, dn n kh nng lc sai còn cao.
Mt u bt li khác là các lut dng này u là tnh. Khi các
spammer tìm ra c mt phng pháp mi  t qua thì nhng
ngi vit trình lc li phi vit nhng lut mi  lc các spam.
Nhng spammer chuyên nghip thì có th kim tra c nhng email
trên các h thng lc da trên lut trc khi gi chúng i.
Nu b lc c xây dng da trên lut phc tp thì vn phát
huy tác dng lc spam hiu qu. Ví d nh trình lc Spamassassin
lc lên n 90-95% spam.
Mt u thun li là b lc da trên lut tnh thì d cài t.
2.2.7 Challenge-Response:
• Ý t逢荏ng:
Khi bn nhn c email t ai ó mà cha h gi cho bn trc
ó thì h thng lc challenge-response
6
gi ngc li 1 email yêu cu h
phi n 1 trang web và in y  thông tin vào form trc khi email
chuyn cho ngi dùng.
• A員c 8k吋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

phân loi email bng phng pháp máy hc, phng pháp này có hiu qu cao,
ng thi cng rt khó b các spammer vt qua. Ngoài ra, hng tip cn này
có th áp dng c  mc Client
C th hng tip cn mà nhóm chúng tôi tìm hiu và th nghim là
phân loi email da trên thut toán hun luyn Naïve Bayes và Adaboost, hai
phng pháp này có mt s u im sau:
§ Hiu qu phân loi trong các lnh phân loi vn bn, nhn dng
ã c kim chng và khá cao
§ Thích hp cho tng ngi dùng c th và  mc Client
§ Có kh nng t hc  phân loi úng.
§ ng tip cn còn khá mi.
2.4 Các ch雨 s嘘"8ánh giá hi羽u qu違 phân lo衣i email :
2.4.1 Spam Recall và Spam Precision:
 tin li cho vic so sánh, ngi ta a ra hai ch sánh giá là spam
recall và spam precision.
Spam recall là t l phn trm gia s email –c b lc coi là spam - b
chn li và tng s email spam (thc s ) n b lc
Spam Precision là t l phn trm gia s email b chn thc s là spam
vi s email b chn -c b lc coi là spam, spam precision ánh giá mc 
an toàn ca b lc.
Công thc tính Spam Recall (SR) và Spam Precision(SP) nh sau:
SS
SS SN
n
SR
nn
−>
−> −>
=
+

NN
−> −>
+
=
+
Công th泳c 2-3 :công th泳c tính t雨 l羽 chính xác
NS SN
NS
nn
Err
NN
−> −>
+
=
+
Công th泳c 2-4 : công th泳c tính t雨 l羽 l厩i
Vi
•
N
N và
S
N là s email non-spam và s email spam cn phân loi
•
NN
n
>−
là s email là non-spam và c b lc nhn ra là non- spam
•
SN
n