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

3
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 is ts: 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.
• c 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.
• c 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.
• c 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.
• 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

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á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