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 ã hng dn chúng tôi thc hin  tài này. Nh có s hng dn, ch bo tn tình ca thy, chúng tôi ã hoàn thành khoá lun này. Chúng con xin kính gi lòng bit n, kính trng ca chúng con n ông bà, cha m và các ngi thân trong gia ình ã ht lòng nuôi chúng con n hc, luôn luôn  bên chúng con,ng viên giúp  chúng con vt qua khó khn Chúng em xin cm n tt c các thy cô trng i hc Khoa Hc T Nhiên, c bit là các thy cô trong khoa Công Ngh Thông Tin ã ht lòng ging dy, truyn t nhiu kin thc và kinh nghim quý báu cho chúng em. Chúng em cng xin chân thành cm n khoa Công Ngh Thông Tin, b môn H Thng Thông Tin ã to mi u kin thun li trong quá trình thc hin khoá lun ca chúng em. Chúng tôi xin chân thành cm n bn bè trong lp cng nh các anh chi trc ã giúp , óng góp ý kin cho chúng tôi. Vi thi gian nghiên cu ngn, trong vòng 6 tháng và nng lc ca nhng ngi làm  tài, chc chn  tài còn có nhiu thiu sót. Chúng tôi rt mong nhn c nhng góp ý, nhn xét  tài c hoàn thin hn. Thành ph H Chí Minh Tháng 7 nm 2005 Nhng ngi thc hin: Lê Nguyn Bá Duy – Trn Minh Trí. 4 v Mc lc: Chng 1 : MU 9 1.1 Gii thiu: 10 1. 2 Yêu c u bài t oá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 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 TRÊN PHNG PHÁP PHÂN LOI NAÏVE BAYESIAN 41 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: 42 5.1.1 Khái nim “Token” : 42 5.1.2 Vector thuc tính : 42 5.1.3 Chn ngng phân loi : 43 5.1.4 Cách thc hin :. 43 5 5.2 Th nghim hiu qu phân loi 51 5.2.1 Th nghim vi kho ng liu pu: 51 5.2.2 Th nghim vi kho ng liu email ch : 60 5.3 u – nhc m ca phng pháp phân loi Naïve Bayesian: 61 5.3.1 u m : 61 5.3.2 Khuyt m : 62 Chng 6 : PHNG PHÁP ADABOOST VÀ NG DNG PHÂN LOI EMAIL 63 6.1 Thut toán AdaBoost : 64 6.2 AdaBoost trong phân loi vn bn nhiu lp : 65 Thut toán AdaBoost MH phân loi vn bn nhiu lp : 66 6.3 ng dng AdaBoost trong phân loi email: 66 6.3.1 Thut toán AdaBoost.MH trong trung hp phân loi nh phân 67 Gii hn li hun luyn sai : 68 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 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 1. Kt qu thc hin vi thut toán AdaBoost with real value predictions 103 2. Kt qu thc hin vi thut toán AdaBoost with discrete predictions 105 7 Danh mc các hình v: Hình 3-1Email sau khi tách token và mã hoá (trong kho ng liu pu) 29 Hình 5-1Mô t cu trúc bng bm 48 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 λ= ) 53 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 λ= ) 53 Hình 5-4 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 PU2 vi công thc 5-5 ( 9 λ= ) 55 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 λ= ) 55 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 λ= ) 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 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 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 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 [...]... 2003, s l ng email 6951 31 ng email spam 2398 l, s Chỳng tụi ti n hnh x lý v phõn l ai email : l ai b nh ng email cú t p tin ớnh kốm, phõn lo i email html v email v n b n tr n (text/plain) S email spam l v n b n tr n sau khi ó x lý kh ang 600 email, email nonspam l v n b n tr n sau khi ó x lý l kho ng 2500 mail S email non-spam l email html sau khi ó x lý l g n 200 mail, s email spam l email html sau... m cú 1182 email Nh ng email h p l khụng cú n i dung v nh ng email RC s b lo i b , k t qu l cú 618 email h p l Nh ng email spam trong PU1 l email spam ng ó nh n c trong kho ng th i gian 22 thỏng cho n th i it o m 12-2003, bao g m nh ng email khụng ph i l email ti ng Anh v nh ng email gi ng nhau nh n trong m t ngy PU2 c ng t ng t nh PU1, i m khỏc nhau õy l nh ng email RC PU3 v PUA,nh ng email h p l... 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 thnh 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... khi ó x lý kho ng 1000 mail Sau ú chỳng tụi t o thnh hai kho ng li u email v n b n tr n (text/plain) v email html Vi c t o kho ng li u email v n b n tr n (text/plain) th c hi n b ng cỏch ch n ng u nhiờn cỏc email t kho ng li u sau khi ó qua x lý, s email spam dựng hu n luy n l 517, s l ng email spam non-spam l v n b n tr n (text/plain) s l dựng ki m th l 98 V i ng li u email ng dựng hu n luy n l 528,... xỏc nh ng email spam ny th c s nt ó khộo lộo che gi u i ph n header c a email ú c n ph i hi u bi t v header c a email th t s nt õu do cỏc spammer n i ngu n g c Do hi u rừ email spam ny õ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 16 c thi t l p v d a vo ú ta cú th ng n ch n nh n email spam... dựng hu n luy n l 528, s l ng ki m th l 100 t o kho ng li u email html, chỳng tụi c ng xõy d ng t V i ng li u email non-spam l html, chỳng tụi dựng 141 email email dựng ng t nh trờn hu n luy n, 50 ki m th Cũn ng li u emal spam l html, chỳng tụi dựng 205 email hu n luy n v 50 email ki m th 32 Ch ng 4 : PH NG PHP PHN LO I NAẽVE BAYESIAN V LO I EMAIL 33 NG D NG PHN 4.1 M t vi khỏi ni m xỏc su t cú liờn... i, ch gi l i m t email m thụi ch ny c ỏp d ng cho c email spam v email non-spam Theo [18], trong quỏ trỡnh t o kho ng li u PU, m t v n phỏt sinh ú l cú m t l xuyờn liờn l c v i ng ng l n email l c a nh ng ng i g i th ng i t o kho ng li u - nh ng email RC (Relative Correspondence), nh ng email ny c ng c lo i b 3.1.2 Mụ t c u trỳc kho ng li u PU: Nh ng email h p l trong PU1 l nh ng email h p l ng c trong... n i ny Vi c thi t l p danh sỏch cỏc a ch email en hay mỏy ch g i email ny 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 ny 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 ny b c u lo i c kho ng 50% [5] email spam Khuy t m c a ph ng phỏp ny l chỳng... 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 ng email gi ng nhau g im ts u ny lm cho cỏc email qu ng cỏo ú d dng 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 ny 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 http://spamshield.conti.nu 18 FAR = nS N nS nS N : email spam m b l c nh n l non-spam nS email. .. t c cỏc kho ng li u PU, cỏc t p tin ớnh kốm, cỏc th HTML, cỏc tr ng khỏc trong header c a email (subject) Cỏc d u ch m cõu, cỏc kớ t u b lo i b (ngo i tr tr c bi t khỏc (!,$) c ng 30 ng tiờu c xem xột c Tờn Email Email h p l ban Email Email Email T ng T l non- RC h p l h p l spam s spam:spam khỏc b cũn l i u email gi l i xúa Pu1 1182 564 618 481 1099 1.28 Pu2 6207 5628 579 142 721 4.01 Pu3 8824 6253 . 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,. 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