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 Mail Blacklists /Whitelists: ........................................................................... 16
2.2.3 Mail volume :............................................................................................... 18
2.2.4 Signature/ Checksum schemes: ..................................................................... 19
2.2.5 Genetic Algorithms:......................................................................................20
2.2.6 Rule-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 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
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

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
Bng 5-5 Kt qu kim th phân lai email bng phng pháp phân lai Bayesian
trên kho ng liu email ch............................................................................61
Bng 7-1 Kt qu th nghim phân loi email vi ng liu s PU bng thut toán
AdaBoost with real -value predictions............................................................77
Bng 7-2 Kt qu th nghim phân loi email vi ng liu s PU bng thut toán
AdaBoost with discrete predictions ................................................................77
B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 .....................................................79
Bng 7-4 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 discrete predictions.........................................................80

9
Chng 1 : MU

10

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
mang li li nhun. Trong s 100.000 email spam phát tán, ch cn mt email có
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


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à
d nhiên là các email n t các tên min này hoàn toàn b khóa (block out). Mt s
h thng cn c vào header ca email (nhng trng nh ni gi (from ), tiêu 
(subject)..) và loi b nhng email có a ch xut phát t nhng spammer (ngi
phát tán spam). Vài h thng khác li tìm kim trong ni dung ca email, nhng du
vt cho thy có s tn ti ca spam chng hn email có quá nhiu du than, s ch
cái c vit hoa nhiu mt cách bt bình thng …
Tuy nhiên các spammer ngày càng tinh vi, vì th các k thut dùng  chng
spam cng phi c ci tin, và chính nhng ci tin này càng thôi thúc các
spammer tr nên ranh ma và tinh vi hn… Kt qu là nh hin nay, các email spam
gn nh ging vi mt email thông thng. Tuy nhiên email spam có mt u
không bao gi thay i ó là bn cht ca nó. Bn cht ó chính là mc tiêu qung
cáo sn phm hay dch v. Nó là c s cho phng pháp lc email da trên ni dung
(content based filtering).Theo ó, chúng ta c gng phát hin ra các ngôn ng qung
cáo (sales-pitch language) thay vì chú ý n các ch s thng kê ca email chng
hn nh có bao nhiêu ln xut hin ch “h0t chixxx!” …

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:
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
a ch IP (Internet Protocol) t nhng ni chuyên dùng gi spam mà
nó còn t chi luôn c nhng email mà có tên min nm trong danh
sách “Blacklist” này.
Cách này c áp dng ti mc nhà cung cp dch v mng

FAR (false acceptance rate) ca nó còn khá cao. Vi:
3


19
SN
S
n
FAR
n
→
=
SN
n
→
:  email spam mà b lc nhn là non-spam.
S
n
:  email spam thc sn b lc..
2.2.4 Signature/ Checksum schemes:
• Ý tng:
ây là mt trong nhng phng pháp phân loi email da trên
ni dung. Khi mt email ti thì giá tr “Signature/ Checksum” sc
tính toán cho mi email này và so sánh nó vi giá tr tính c t
nhng email spam c trng trong t nhng email spam có sn trên
Internet. Nu giá tr “signature/ checksum” ca nhng email ti ging
vi bt k giá tr nào trong c s d liu thì email ó c ánh giá là
spam.
Mt cách n gin  tính giá tr này là gán mt giá tr cho mi
kí t, sau ó cng tt c chúng li. S là không bình thng nu 2

• Ý 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
bin “mutation”. Mc ích tin trình này là tìm ra c mt giá tr
“score” nh nht da vào hàm “fitness function”. Giá tr “score” sau
ó sc s dng  phân loi email là spam hay non-spam.[6]
• c m:
ây là hng tip cn phân loi email da trên ni dung.
ng tip cn hiu qu nht cho b lc ti mc ISP c
ánh giá là da trên thut toán di truyn “Genetic Algorithms” [6]
im không thun li ca thut toán di truyn là òi hi kh
ng x lý phi ln.
ng tip cn này c ng dng trong trình lc spam
Spamassassin
5
. Nó hot ng rt hiu qu ti mc ISP và c nhiu
ngi ánh giá là mt trong nhng b lc hot ng hiu qu nht ti
mc ISP.

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
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

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
−>
−> −>
=
+
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

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
>−
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