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 cNJng
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 ÿLӅ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 cNJng 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 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 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ó ÿLӅ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 ÿLӇm cӫa phѭѫng pháp phân loҥi Naïve Bayesian:………………………. 61
5.3.1 Ѭu ÿLӇm :…………………………………………………………………………………………61
5.3.2 KhuyӃt
ÿLӇ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 ÿLӇm cӫa phѭѫng pháp phân loҥi AdaBoost:………………………………. 80
7.3.1 Ѭu ÿLӇm :…………………………………………………………………………………………80
7.3.2 KhuyӃt
ÿLӇ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
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
Oѭӧ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 cNJng
ÿѭӧ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) cNJng 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 ÿLӇ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%
Oѭӧng email trên mҥng là spam1, 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 cNJng 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 http://zdnet.com.com/2100-1106-955842.html
2 http://zdnet.com.com/2100-1105_2-1019528.html
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 cNJng 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
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à
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 cNJng 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 ÿLӅ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!” …
Mӝt ÿLӅu quan trӑng cҫn phҧi cân nhҳc ÿӃn khi lӑc spam là cái giá phҧi trҧ khi
lӑc sai. NӃu mӝt bӝ lӑc tӯ chӕi nhұn hҫu hӃt các email gӱi ÿӃn hoһc ÿánh dҩu mӝt
email thұt sӵ quan trӑng nào ÿó là spam thì ÿiӅu ÿó còn tӋ hѫn cҧ viӋc nhұn tҩt cҧ
email spam ÿѭӧc gӱi ÿӃn. Ngѭӧc lҥi, nӃu có quá nhiӅu email spam vѭӧt ÿѭӧc bӝ lӑc
thì rõ ràng bӝ lӑc hoҥt ÿӝng không hiӋu quҧ, không ÿáp ӭng ÿѭӧc yêu cҫu cӫa ngѭӡi
sӱ dөng.
16
2.2 Các phѭѫng pháp tiӃp cұn:
2.2.1 Complaining to Spammers’ ISPs :
• Ý tѭӣng :
Tìm cách làm tăng chi phí gӱi spam cӫa các spammer bҵng
nhӳng lӡi than phiӅn, phҧn ánh ÿӃn các nѫi cung cҩp dӏch vө mҥng
(Internet Service Provider – ISP). Khi chúng ta biӃt chính xác nhӳng
email spam thӵc sӵÿѭӧc gӱi ÿӃn tӯ dӏch vө ISP nào, ta sӁ phҧn ánh
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 ÿLӇm :
Ĉây cNJng là giҧi pháp chӕng spam ÿҫu tiên. Nhӳng lӡi than
phiӅn cNJng 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 cNJng 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 ÿLӇm:
Phѭѫng pháp này bѭӟc ÿҫu loҥi ÿѭӧc khoҧng 50% [5] email
spam.
KhuyӃt ÿLӇ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
(ISP), và thұt sӵ hӳu dөng vӟi ngѭӡi dùng nӃu hӑ sӱ dөng mӝt ISP
ÿáng tin cұy.
18
Ngѭӧc lҥi vӟi viӋc thiӃt lұp mӝt danh sách ÿen “Blacklist” ta
còn có thӇ thiӃt lұp mӝt danh sách “Whitelist”. Vӟi nhӳng ÿӏa chӍ gӱi
email (hoһc tên miӅn domains) nҵm trong danh sách này sӁÿѭӧc các
ISP tӵÿӝng chҩp nhұn email gӱi tӯ nó. Mһc ÿӏnh tҩt cҧ nhӳng email
khác sӁ bӏ tӯ chӕi..
NӃu các spammer gӱi email spam vӟi phҫn “sender” cӫa email
có cùng tên miӅn ÿѭӧc chҩp nhұn trong “Whitelist” thì email spam
vүn có thӇÿӃn ÿѭӧc tay ngѭӡi nhұn.
2.2.3 Mail volume :
• Ý tѭӣng:
Bӝ lӑc sӁ sӱ dөng thuұt toán ÿӇ kiӇm tra sӕ lѭӧng email nhұn
ÿѭӧ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ӕ
Oѭӧ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 ÿLӇ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ӕ
Oѭӧng email giӕng nhau. ĈLӅ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 http://spamshield.conti.nu
19
S
N
S
n
FAR
n
→
=
S
N
n →
:
6ӕ email spam mà bӝ lӑc nhұn là non-spam.
S
n
:
6ӕ 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
email khác nhau lҥi có chung mӝt giá trӏ “signature/ checksum”.
• Ĉһc ÿLӇm:
Cách tҩn công mӝt bӝ lӑc kiӇu này là thêm vào ngүu nhiên mӝt
vài ký tӵ hay mӝt câu vô nghƭa trong mӛi email spam ÿӇ tҥo ra sӵ
khác biӋt cӫa giá trӏ “signature”. Khi bҥn thҩy nhӳng thӭ hӛn tҥp chèn
ngүu nhiên trong phҫn tiêu ÿӅ (subject) cӫa email, ÿó chính là cách ÿӇ
tҩn công bӝ lӑc dӵa vào “signature/ checksum”.
Các spammer dӉ dàng ÿӕi phó ÿӕi vӟi các bӝ lӑc dӵa trên
“signature/ checksum” bҵng phѭѫng pháp trên. Khi mà nhӳng ngѭӡi
viӃt các chѭѫng trình lӑc email tìm ÿѭӧc cách chӕng lҥi cách chèn
20
ngүu nhiên này thì các spammer lҥi chuyӇn sang cách khác. Vì thӃ,
cách chӕng spam dùng các bӝ lӑc “signature/checksum” chѭa bao giӡ
là mӝt cách tӕt.
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.
Brightmail4 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 ÿLӇ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”.
4http://brightmail.com
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 ÿLӇ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ҧ
Qăng xӱ lý phҧi lӟn.
+ѭӟng tiӃp cұn này ÿѭӧc ӭng dөng trong trình lӑc spam
Spamassassin5. 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.
ĈiӇm yӃu cӫa trình lӑc “Spamassassin” là hoҥt ÿӝng vӟi hiӋu
quҧ chѭa cao tҥi mӭc ngѭӡi dùng cá nhân.
2.2.6 Rule-Based (hay là Heuristic):
• Ý tѭӣng:
Dӵa vào luұt tìm kiӃm các mүu có dҩu hiӋu là spam nhѭ các tӯ
và ngӳ xác ÿӏnh, hàng loҥt các chӳ hoa và dҩu chҩm than, phҫn header
cӫa email sai ÿӏnh dҥng, ngày trong email là ӣ tѭѫng lai hoһc quá
khӭ.Ĉó là cách hҫu hӃt phҫn lӟn các trình lӑc spam hoҥt ÿӝng tӯ năm
2002.
• Ĉһc ÿLӇm:
5 http://spamassassin.org
22
HiӋu suҩt cӫa trình lӑc dӵa trên luұt (rule-based filters) khác
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 cNJng 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 ÿLӅ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 ÿӇ Yѭӧ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 ÿLӅ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 ÿLӇm:
6 http://spamarrest.com/products
23
Lӧi thӃ cӫa hӋ thӕng này là ÿӇ lӑt lѭӟi rҩt ít spam. ĈLӅ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 ÿLӇ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 ÿLӋ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
Wѭӡng bao quanh thӃ giӟi luôn muӕn gӱi thông ÿLӋp cho ta.
2.2.8 Machine Learning ( Máy hӑc ):
•
Ý tѭӣng:
Áp dөng các pKѭѫ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 ÿLӇ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.
24
2.3 Phѭѫng pháp lӵa chӑn :
Trong nhӳng hѭӟng tiӃp cұn ÿã tìm hiӇu, chúng tôi chӑn hѭӟng tiӃp cұn
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 cNJng 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:
S
S
S
S
S
N
n
SR
n
n
−>
−>
−>
=
+
Công thӭc 2-1 :Công thӭc tính Spam Recall
25
S
S
S
S
N
S
n
SP
n
n
−>
−>
−>
=
+
Công thӭc 2-2 : Công thӭc tính Spam Precesion
Vӟi :
ü n
S
S >
−
là sӕ email là spam mà bӝ lӑc nhұn ra là spam
ü n
N
S >
−
là sӕ email là spam mà bӝ lӑc nhұn ra là email non-spam
ü n
S
N
>
−
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)
hoһc tӍ lӋ lӛi (Err). Công thӭc tính tӍ lӋ chính xác và tӍ lӋ lӛi nhѭ sau :
N
N
S
S
N
S
n
n
Acc
N
N
−>
−>
+
=
+
Công thӭc 2-3 :công thӭc tính tӍ lӋ chính xác
N
S
S
N
N
S
n
n
Err
N
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
•
N
N
n
>
−
là sӕ email là non-spam và ÿѭӧc bӝ lӑc nhұn ra là non- spam
•
S
N
n
>
−
là sӕ email là non-spam mà bӝ lӑc nhұn ra là spam
•
S
S
n
>
−
là sӕ email là spam mà ÿѭӧc bӝ lӑc nhұn ra là spam
•
N
S
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
