Khóa luận Thực tế 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 hỗ trợ tiếng Việt

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 ( 9l = ) .........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 ( 9l = ) .....................................................................................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 ( 9l = ) ..........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 ( 9l = ) ...............................................................................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 ( 9l = ) ..........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 ( 9l = ) .....................................................................................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 ( 9l = ) .........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 ( 9l = ) ...............................................................................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 2 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 19 S N S nF A R n ®= S Nn ® : 6ӕ email spam mà bӝ lӑc nhұn là non-spam. Sn : 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”. 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 ÿ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 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 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 nSR n n -> -> -> = + Công thӭc 2-1 :Công thӭc tính Spam Recall 25 S S S S N S nSP n n -> -> -> = + Công thӭc 2-2 : Công thӭc tính Spam Precesion Vӟi : ü n SS >- là sӕ email là spam mà bӝ lӑc nhұn ra là spam ü n NS >- là sӕ email là spam mà bӝ lӑc nhұn ra là email non-spam ü n SN >- 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 nAcc 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 nErr N N -> ->+= + Công thӭc 2-4 : công thӭc tính tӍ lӋ lӛi Vӟi · NN và SN là sӕ email non-spam và sӕ email spam cҫn phân loҥi · NNn >- là sӕ email là non-spam và ÿѭӧc bӝ lӑc nhұn ra là non- spam · SNn >- là sӕ email là non-spam mà bӝ lӑc nhұn ra là spam · SSn >- là sӕ email là spam mà ÿѭӧc bӝ lӑc nhұn ra là spam · NSn >- 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 26 nghiêm trӑng hѫn, bӣi ngѭӡi dùng có thӇ chҩp nhұn mӝt email spam vѭӧt qua bӝ lӑc nhѭng khó mà chҩp nhұn mӝt email hӧp lӋ lҥi bӏ bӝ lӑc chһn lҥi.ĈӇ biӇu thӏ tác ÿӝng cӫa hai loҥi lӛi này ÿӕi vӟi tӍ lӋ chính xác và tӍ lӋ lӛi, ta sӁ xem mӛi mӝt email hӧp lӋ nhѭ là l email hӧp lӋ. Do ÿó khi mӝt email hӧp lӋ bӏ phân loҥi sai, thay vì xem nhѭ có mӝt lӛi, ta xem nhѭ là l lӛi, và khi phân loҥi ÿúng ta xem nhѭ là l lҫn thành công. Ta có hai tӍ lӋ : tӍ lӋ chính xác gia trӑng WAcc (Weighted Accuracy Rate ) và tӍ lӋ lӛi gia trӑng WErr (Weighted Error Rate) (WErr=1 -WAcc). N N S S N S n nWAcc N N l l -> ->+= + Công thӭc 2-5 TӍ lӋ chính xác gia trӑng N S S N N S n nWErr N N l l -> ->+= + Công thӭc 2-6 TӍ lӋ lӛi gia trӑng Vӟi : ü NN và SN là sӕ email non-spam và sӕ email spam cҫn phân loҥi ü NNn >- là sӕ email là non-spam và ÿѭӧc bӝ lӑc nhұn ra là non- spam ü SNn >- là sӕ email là non-spam mà bӝ lӑc nhұn ra là spam ü SSn >- là sӕ email là spam mà ÿѭӧc bӝ lӑc nhұn ra là spam ü NSn >- là sӕ email là spam mà ÿѭӧc bӝ lӑc nhұn ra là non-spam 2.4.4 TӍ sӕ chi phí tәng hӧp TCR (Total Cost Ratio ): Giá trӏ cӫa tӍ lӋ chính xác và tӍ lӋ lӛi thѭӡng có sӵ sai lӋch cao.ĈӇ thҩy rõ ÿѭӧc hiӋu quҧ cӫa cách phân loҥi, ngѭӡi ta thѭӡng so sánh tӍ lӋ chính xác hoһc tӍ lӋ lӛi giӳa bӝ phân loҥi vӟi trѭӡng hӧp ÿѫn giҧn nhҩt và ÿѭӧc xem là trѭӡng hӧp “ranh giӟi “(baseline).”Ranh giӟi” ÿѭӧc chӑn là trѭӡng hӧp không sӱ dөng mӝt bӝ lӑc nào, các email hӧp lӋ không bao giӡ bӏ chһn lҥi và các email 27 là spam thì luôn luôn ÿi qua. Nhѭ vұy tӍ lӋ chính xác gia trӑng và tӍ lӋ lӛi gia trӑng cӫa trѭӡng hӧp “ranh giӟi “ là : Công thӭc 2-7: TӍ lӋ chính xác gia trӑng cӫa trѭӡng hӧp "Ranh giӟi " b S N S NWErr N Nl = + Công thӭc 2-8: TӍ lӋ lӛi gia trӑng cӫa trѭӡng hӧp "Ranh giӟi " Vӟi : NN , SN , NNn >- , SNn >- , SSn >- , NSn >- có cùng ý nghƭa nhѭ ӣ mөc 2.4.1 và 2.4.2 TӍ sӕ chi phí toàn bӝ TCR ( total cost ratio) cho phép ta so sánh ÿѭӧc hiӋu quҧ cӫa trѭӡng hӧp sӱ dөng bӝ lӑc so vӟi trѭӡng hӧp “ranh giӟi”: b S N S S N NWErrTCR WErr n nl -> -> = = + Công thӭc 2-9 Công thӭc tính tӍ sӕ chi phí tәng hӧp Giá trӏ TCR càng lӟn thì hiӋu quҧ phân loҥi càng cao, vӟi TCR nhӓ hѫn 1 thì rõ ràng không sӱ dөng bӝ lӑc còn tӕt hѫn. . b N N S NWAcc N N l l = + 28 Chѭѫng 3 : GIӞI THIӊU CÁC KHO NGӲ LIӊU DÙNG KIӆM THӰ PHÂN LOҤI EMAIL 29 3.1 Kho ngӳ liӋu PU (corpus PU ): 3.1.1 Vài nét vӅ kho ngӳ liӋu PU: Các nghiên cӭu vӅ phân loҥi Yăn bҧn có nhiӅu thuұn lӧi vì có sҹn các kho ngӳ liӋu công cӝng ÿӇ dùng chung, tuy nhiên sӱ dөng nhӳng kho ngӳ liӋu này vào viӋc lӑc spam lҥi gһp phҧi rҳc rӕi bӣi vҩn ÿӅ tính riêng tѭ, cá nhân. Nhӳng email spam thì không có vҩn ÿӅ gì, tuy nhiên không thӇ sӱ dөng nhӳng email hӧp lӋ mà không thӇ không vi phҥm ÿӃn sӵ riêng tѭ cӫa ngѭӡi gӣi và ngѭӡi nhұn cӫa nhӳng email này. Chúng tôi sӱ dөng kho ngӳ liӋu PU ÿӇ hӑc và kiӇm thӱ7 PU là mӝt kho ngӳ liӋu email chuҭn, gӗm có bӕn kho ngӳ liӋu nhӓ hѫn bao gӗm PU1, PU2, PU3 và PUA. Mӛi mӝt token sӁÿѭӧc thay thӃ tѭѫng ӭng bҵng mӝt con sӕ duy nhҩt nhѭ minh hӑa trong hình 3-1. Hình 3-1Email sau khi tách token và mã hoá (trong kho ngӳ liӋu pu) Hàm ánh xҥ tӯ văn bҧn sang các con sӕ không ÿѭӧc công bӕ, do ÿó viӋc khôi phөc lҥi văn bҧn ban ÿҫu là cӵc kǤ khó,ÿiӅu này ÿҧm bҧo ÿѭӧc tính bí mұt, riêng tѭ cӫa ngѭӡi gӣi và ngѭӡi nhұn. Nhӳng email giӕng nhau cNJng ÿѭӧc xem xét. Trong kho ngӳ liӋu PU1 và PU2, nhӳng email giӕng nhau và nhұn trong cùng mӝt ngày ÿѭӧc xóa thӫ công.Trong kho ngӳ liӋu PU3 và PUA quá trình này ÿѭӧc thӵc hiӋn tӵÿӝng, ӣ hai kho ngӳ liӋu này, khái niӋm khác nhau cӫa hai email ÿѭӧc xem xét nhѭ sau :hai email ÿѭӧc xem là khác nhau nӃu chúng có ít nhҩt 5 dòng khác nhau.Tҩt cҧ nhӳng email giӕng nhau, bҩt kӇ ngày nhұn,ÿӅu 7ĈӇ lҩy cѫ sӣ dӳ liӋu PU, vào trang web Internet CONtent Filtering Group, config/ 30 bӏ xóa ÿi, chӍ giӳ lҥi mӝt email mà thôi.&ѫ chӃ này ÿѭӧ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ѭӧng lӟn email là cӫa nhӳng ngѭӡi gӣi thѭӡng xuyên liên lҥc vӟi ngѭӡi tҥo kho ngӳ liӋu - nhӳng email RC (Relative Correspondence), nhӳng email này cNJng ÿѭӧ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ѭӡi tҥo ÿã nhұn ÿѭӧc trong vòng 36 tháng cho ÿӃn tháng 12 năm 2003, gӗ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ѭӡi tҥo ÿã nhұn ÿѭӧc trong khoҧng thӡi gian 22 tháng cho ÿӃn thӡi ÿLӇ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 ngày. PU2 cNJng 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Ӌ không phҧi là tiӃng Anh vүn ÿѭӧc giӳ lҥi TӍ lӋ non-spam :spam cӫa PU3 xҩp xӍ PU1, tuy nhiên sӕ lѭӧng cӫa PU3 nhiӅu gҩp 4 lҫn PU1, trong PU2 tӍ lӋÿó xҩp xӍ 4:1, ӣ PUA tӍ lӋÿó là 1:1 Trong tҩ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 ÿӅu bӏ loҥi bӓ (ngoҥi trӯ trѭӡng tiêu ÿӅ (subject). Các dҩu chҩm câu, các kí tӵÿһc biӋt khác (!,$) cNJng ÿӵӧc xem xét . 31 Mӛi kho ngӳ liӋu pu lҥi ÿѭӧc chia ra làm 11 thѭ mөc tӯ part 1 ÿӃn part 10, và mӝt thѭ mөc unused, mӛi thѭ mөc tӯ part 1 ÿӃn part 10 chӭa sӕ lѭӧng email nhѭ nhau và sӕ lѭӧng email spam và email hӧp lӋ trong mӛi thѭ mөc part i (i=1,…,10) trên là nhѭ nhau, thѭ mөc unused chӭa nhӳng email không sӱ dөng. Chúng tôi sӱ dөng tӯ part 1 ÿӃn part 9 ÿӇ phөc vө cho viӋc hӑc.Ĉӕi vӟi viӋc kiӇm thӱ kӃt quҧ , chúng tôi sӱ dөng kho ngӳ liӋu ÿã ÿѭӧc hӑc (tӯ part 1 ÿӃn part 9 ) và kho ngӳ liӋu chѭa ÿѭӧc hӑc ÿӇ kiӇm thӱ.ĈӇ thӵc hiӋn viӋc kiӇm thӱ các thuұt toán ÿѭӧc tiӋn lӧi, chúng tôi tiӃn hành chia nhóm kho ngӳ liӋu hӑc.Vӟi mӛi kho ngӳ liӋu PU, chúng tôi phân loҥi email thành hai thѭ mөc, mӝt thѭ mөc chӭa các email spam tӯ part 1 ÿӃn part 9, thѭ mөc còn lҥi chӭa email hӧp lӋ tӯ part 1 ÿӃn part 9, vӟi part 10 chúng tôi cNJng tiӃn hành phân loҥi tѭѫng tӵ nhѭ trên 3.2 Kho ngӳ liӋu email chӳ: ĈӇ tҥo kho ngӳ liӋu email là chӳ, chúng tôi lҩy dӳ liӋu tҥi trang : Index of /publiccorpus Ngӳ liӋu gӗm nhӳng email ÿѭӧc thu thұp trong các năm 2002 và 2003, sӕ lѭӧng email spam 2398 là, sӕ Oѭӧng email 6951 Tên Email hӧp lӋ ban ÿҫu Email RC Email hӧp lӋ khác bӏ xóa Email hӧp lӋ còn lҥi Email spam Tәng sӕ email giӳ lҥi TӍ lӋ non- spam:spam Pu1 1182 564 618 481 1099 1.28 Pu2 6207 5628 579 142 721 4.01 Pu3 8824 6253 258 2313 1826 4139 1.27 Pua 980 369 40 571 571 1142 1 %ҧng 3-1Mô tҧ cҩu trúc kho ngӳ liӋu PU 32 Chúng tôi tiӃn hành 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 non- spam 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 khi ÿã xӱ lý khoҧng 1000 mail. Sau ÿó chúng tôi tҥo thành 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 ÿӇ kiӇm thӱ là 98. Vӟi ngӳ liӋu email non-spam là văn bҧn trѫn (text/plain) sӕ lѭӧng dùng huҩn luyӋn là 528, sӕ lѭӧng dùng ÿӇ kiӇm thӱ là 100 ĈӇ tҥo kho ngӳ liӋu email html, chúng tôi cNJng xây dӵng tѭѫng tӵ nhѭ trên. Vӟi ngӳ liӋu email non-spam là html, chúng tôi dùng 141 email ÿӇ huҩn luyӋn, 50 email dùng ÿӇ 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ӱ. 33 Chѭѫng 4 : PHѬѪNG PHÁP PHÂN LOҤI NAÏVE BAYESIAN VÀ ӬNG DӨNG PHÂN LOҤI EMAIL 34 4.1 Mӝt vài khái niӋm xác suҩt có liên quan 4.1.1 Ĉӏnh nghƭa biӃn cӕ, xác suҩt : 4.1.1.1 Khái niӋm phép thӱ và biӃn cӕ: Gieo mӝt ÿӗng tiӅn trên mӝt mһt phҷng :ÿó là mӝt phép thӱ KӃt quҧ có thӇ xҧy ra khi gieo ÿӗng tiӅn : “Xuҩt hiӋn mһt sҩp” hoһc “Xuҩt hiӋn mһt ngӳa” “Xuҩt hiên mһt sҩp” -Ĉó là mӝt biӃn cӕ “Xuҩt hiӋn mһt ngӳa” -Ĉó là mӝt biӃn cӕ 4.1.1.2 Ĉӏnh nghƭa xác suҩt: Theo [8] có nhӳng ÿӏnh nghƭa xác suҩt sau: Dҥng cәÿLӇn : Xác sṷt cͯa bi͇n c͙ A là m͡t s͙ không âm,ký hi͏u P(A), bi͋u th͓ kh̫ Qăng x̫y ra bi͇n c͙ A và ÿ˱ͫc xác ÿ͓nh nh˱ sau : ( ) mP A n = = Sӕ trѭӡng hӧp thuұn lӧi cho A / Sӕ trѭӡng hӧp có thӇ có khi phép thӱ thӵc hiӋn (Nhӳng khҧ năng hoһc các biӃn cӕ sѫ cҩp – nӃu chúng xҧy ra thì suy ra A xҧy ra – gӑi là nhӳng trѭӡng hӧp thuұn lӧi cho A ). Ĉ͓nh nghƭa xác sṷt theo ph˱˯ng pháp th͙ng kê : Làm ÿi làm lҥi mӝt phép thӱ nào ÿó n lҫn mà có m lҫn biӃn cӕ A xuҩt hiӋn thì tӹ sӕ m/n gӑi là tҫn suҩt cӫa biӃn cӕ A Khi n thay ÿәi,tҫn suҩt m/n cNJng thay ÿәi nhѭng nó luôn dao ÿӝng quanh mӝt sӕ cӕÿӏnh ÿó. Sӕ cӕÿӏnh ҩy ÿѭӧc gӑi là xác suҩt cӫa biӃn cӕ A theo nghƭa thӕng kê. Trên thӵc tӃ khi n ÿӫ lӟn ta xҩp xӍ P(A) bӣi m/n 35 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 Bayes 4.1.2.1 Xác suҩt có ÿLӅu kiӋn Theo Ĉһng Hҩn [8]: Xác sṷt có ÿL͉u ki͏n cͯa bi͇n c͙ A vͣi ÿL͉u ki͏n bi͇n c͙ B ÿã x̫y ra là m͡t con s͙ không âm,ÿ˱ͫc ký hi͏u P(A/B) nó bi͉u th͓ kh̫ năng x̫y ra bi͇n c͙ A trong tình hu͙ng bi͇n c͙ B ÿã x̫y ra ( )( | ) ( ) P ABP A B P B = Công thӭc 4-1: công thӭc tính xác suҩt có ÿLӅu kiӋn Suy ra: ( | ) ( ) ( | ) ( ) ( )P A B P B P B A P A P AB´ = ´ = Công thӭc 4-2 4.1.2.2 Công thӭc xác suҩt ÿҫy ÿӫ: Giҧ sӱ 1 2 3, , ,..., nB B B B là mӝt nhóm ÿҫyÿӫ các biӃn cӕ. Xét biӃn cӕ A sao cho A xҧy ra chӍ khi mӝt trong các biӃn cӕ 1 2 3, , ,..., nB B B B xҧy ra. Khi ÿó : 1 ( ) ( ). ( / ) n i i i P A P B P A B = = å Công thӭc 4-3 :công thӭc xác suҩt ÿҫy ÿӫ Công thӭc trên ÿѭӧc gӑi là công thӭc xác suҩt ÿҫy ÿӫ 4.1.2.3 Công thӭc xác suҩt Bayes: Tӯ các công thӭc:Công thӭc 4-1, Công thӭc 4-2 và Công thӭc 4-3, ta có: 1 ( ) ( ). ( / )( | ) ( ) ( ). ( / ) k k k k n i i i P AB P B P A BP B A P A P B P A B = = = å Công thӭc 4-4 : công thӭc xác suҩt Bayes 36 4.2 Phѭѫng pháp phân loҥi Naïve Bayesian : Phân loҥi Bayesian là phѭѫng pháp phân loҥi sӱ dөng tri thӭc các xác suҩt ÿã qua huҩn luyӋn. Phѭѫng pháp này thích hӧp vӟi nhӳng lӟp bài toán ÿòi hӓi phҧi dӵÿoán chính xác lӟp cӫa mүu cҫn kiӇm tra dӵa trên nhӳng thông tin tӯ tұp huҩn luyӋn ban ÿҫu [16]. Theo Charles Elkan [16] cho 1,..., nX X là các thuӝc tính vӟi các giá trӏ rӡi rҥc ÿѭӧc dùng ÿӇ dӵÿoán mӝt lӟp riêng biӋt C cho mӝt mүu, tұp các lӟp mà mүu có thӇ thuӝc vӅ là C { }1 2, ,..., mc c c= . Cho mӝt mүu huҩn luyӋn vӟi giá trӏ các thuӝc tính Wѭѫng ӭng là 1,..., nx x , dӵÿoán mүu thuӝc vӅ lӟp c Î C khi xác suҩt ( )1 1 2 2| ... n nP C c X x X x X x= = Ù = Ù Ù = có giá trӏ lӟn nhҩt. Sӱ dөng công thӭc xác suҩt Bayes ta có : ( ) ( )( ) ( ) 1 1 2 2 1 1 2 2 1 1 2 2 ... | | ... ... n n n n n n P X x X x X x C c P C c X x X x X x P C c P X x X x X x = Ù = Ù Ù = = = = Ù = Ù Ù = = = = Ù = Ù Ù = Xác suҩt ( )P C c= ÿѭӧc tính dӉ dàng tӯ tұp dӳ liӋu huҩn luyӋn. Xác suҩt ( )1 1 2 2 ... n nP X x X x X x= Ù = Ù Ù = không thích hӧp ÿӇ dùng cho viӋc quyӃt ÿӏnh lӟp cӫa C bӣi vì giá trӏ này nhѭ nhau ÿӕi vӟi mӛi lӟp c. Nhѭ vұy căn cӭÿӇ dӵÿóan lӟp cӫa C là dӵa vào xác suҩt ( )1 1 2 2 ... |n nP X x X x X x C c= Ù = Ù Ù = = .Tuy nhiên viӋc tính toán xác suҩt này rҩt phӭc tҥp [9] . Mӝt pKѭѫng pháp ÿѫn giҧn và ÿѭӧc ÿѭa ra sӟm nhҩt là phѭѫng pháp phân loҥi Naïve Bayesian, theo ÿó giҧ thiӃt rҵng mӛi iX ÿӝc lұp vӟi các jX ( i j¹ ), nhѭ vұy ta sӁ có: ( ) ( )1 1 2 2 1 ... | | n n n i i i P X x X x X x C c P X x C c = = Ù = Ù Ù = = = = =Õ Thұt vұy, sӱ dөng công thӭc xác suҩt Bayes ta có : ( ) ( ) ( ) 1 1 2 2 1 1 2 2 2 2 ... | | ... , ... | n n n n n n P X x X x X x C c P X x X x X x C c P X x X x C c = Ù = Ù Ù = = = = = Ù Ù = = = Ù Ù = = 37 Bҵng cách ÿӋ qui, viӃt thӯa sӕ thӭ hai trong tích trên nhѭ sau : ( )2 2 ... |n nP X x X x C c= Ù Ù = = = ( ) ( )2 2 3 3 3 3| ... , ... |n n n nP X x X x X x C c P X x X x C c= = Ù Ù = = = Ù Ù = = và cӭ tiӃp tөc nhѭ vұy. Phѭѫng pháp phân loҥi Naïve Bayesian giҧ thiӃt rҵng vӟi mӛi iX kӃt quҧ tác ÿӝng cӫa nó là ÿӝc lұp vӟi các jX khác, nhѭ vұy chúng ta thӯa nhұn rҵng: ( ) ( )1 1 2 2 1 1| ... , |n nP X x X x X x C c P X x C c= = Ù Ù = = = = = và tѭѫng tӵ nhѭ vұy ÿӕi vӟi 2X ,.., nX . Nhѭ vұy xác suҩt ( )1 1 2 2 ... |n nP X x X x X x C c= Ù = Ù Ù = = = ( ) ( ) ( ) ( )1 1 2 2| | ... | | n n n i i i P X x C c P X x C c P X x C c P X x C c= = = = = = = = =Õ Mӛi mӝt thӯa sӕ trong tích trên có thӇÿѭӧc tính dӉ dàng tӯ tұp huҩn luyӋn ban ÿҫu, nhѭ vұy phѭѫng pháp Naïve Bayesian giҧm sӵ phӭc tҥp cӫa viӋc tính toán giá trӏ xác suҩt ( )1 1 2 2 ... |n nP X x X x X x C c= Ù = Ù Ù = = 4.3 Phân loҥi email bҵng phѭѫng pháp Naïve Bayesian : Ӣÿây mӛi mүu mà ta xét chính là mӛi mӝt email, tұp các lӟp mà mӛi email có thӇ thuӝc vӅ là C ={spam, non-spam} Khi ta nhұn ÿѭӧc mӝt email, nӃu ta không biӃt mӝt thông tin gì vӅ nó, do ÿó khó có thӇ quyӃt ÿӏnh chính xác email này là spam hay không . NӃu nhѭ ta có thêm ÿһc ÿLӇm hay thuӝc tính nào ÿó cӫa email thì ta có thӇ nâng cao hiӋu quҧ nhұn ÿѭӧc email là spam Mӝt email có nhiӅu ÿһc ÿiӇm nhѭ : tiêu ÿӅ, nӝi dung, có ÿính kèm tұp tin hay không,…Ta có thӇ dӵa vào các thông tin này ÿӇ nâng cao hiӋu quҧ phân lӑai email spam. Mӝt ví dө ÿѫn giҧn : nӃu ta biӃt ÿѭӧc rҵng 95 % email html là email spam, và ta lҥi nhұn ÿѭӧc mӝt email html, nhѭ vұy có thӇ dӵa vào xác suҩt biӃt trѭӟc 95% email html là email spam ÿӇ tính ÿѭӧc xác suҩt email mà ta nhұn ÿѭӧc là spam, nӃu xác suҩt này lӟn hѫn xác suҩt email ÿó là non-spam, có thӇ kӃt 38 luұn rҵng email ÿó là spam, tuy nhiên kӃt luұn này không chính xác lҳm Nhѭng nӃu ta cóÿѭӧc nhiӅu xác suҩt biӃt trѭӟc nhѭ vұy, thì kӃt luұn sӁ trӣ nên ÿáng tin cұy hѫn. ĈӇ có ÿѭӧc các xác suҩt biӃt trѭӟc này, sӱ dөng phѭѫng pháp Naïve Bayesian huҩn luyӋn tұp mүu (email) ban ÿҫu, sau ÿó sӁ sӱ dөng các xác suҩt này ӭng dөng vào phân lӑai mӝt mүu (email) mӟi. 4.3.1 Phân loҥi email dӵa trên thuұt toán Naïve Bayesian Giҧ thiӃt mӛi mӝt email ÿѭӧc ÿҥi diӋn bӣi mӝt vector thuӝc tính ÿһc trѭng 1 2( , ,..., )nx x x x= r vӟi 1 2, ,..., nx x x , là giá trӏ cӫa các thuӝc tính 1X , 2X ,.., nX tѭѫng ӭng trong không gian vector ÿһc trѭng X r . Theo M Sahami et al [9] ta sӱ dөng các giá trӏ nhӏ phân, iX =1 nӃu các ÿһc ÿLӇm cӫa iX có trong email, ngѭӧc lҥi iX =0. Ta tính giá trӏ tѭѫng hӛ MI (X,C) (Mutual Information) mà mӛi mӝt ÿҥi diӋn cӫa X thuӝc vӅ loҥi C nhѭ sau: { }0,1 ( , )( , ) ( , ).log ( ) ( )x P X x C cMI X C P X x C c P X x P C cÎ = = = = = = =å { },c spam non spamÎ - Công thӭc 4-5 :công thӭc tính ÿӝ tѭѫng hӛ MI Sau ÿó ta chӑn các thuӝc tính có giá trӏ MI cao nhҩt.Các xác suҩt P(X), P(C), P(X,C)ÿѭӧc tính dӵa trên dӳ liӋu hӑc Dӵa vào công thӭc xác suҩt Bayes và công thӭc xác suҩt ÿҫy ÿӫ ta có ÿѭӧc xác suҩt mӝt email vӟi vector ÿһc trѭng xr x r thuӝc vӅ loҥi c là: { }, ( ). ( | )( | ) ( ). ( | ) k spam non spam P C c P X x C cP C c X x P C k P X x C k Î - = = = = = = = = =å uur r uur r uur r Vӟi C là e email ÿѭӧc xét, { },c spam nonspamÎ Công thӭc 4-6 39 Thӵc tӃ thì rҩt khó tính ÿѭӧc xác suҩt ( | )P X C uur bӣi vì giá trӏ sӕ Oѭӧng cӫa các vector rҩt nhiӅu và nhiӅu vector hiӃm khi hay thұm chí không xuҩt hiӋn trong tұp dӳ liӋu huҩn luyӋn.Nhѭÿã nói, phѭѫng pháp Naïve Bayesian giҧ thiӃt rҵng 1X , 2X ,.., nX là nhӳng biӃn cӕÿӝc lұp, do ÿó chúng ta có thӇ tính ÿѭӧc xác suҩt ӣ trên nhѭ sau: { } i 1 , 1 ( ). ( | ) ( | ) ( ). ( | ) n i i n i i k spam non spam i P C c P X x C c P C c X x P C k P X x C k = Î - = = = = = = = = = = Õ å Õ Công thӭc 4-7 Vӟi ( | )iP X C và ( )P C ÿѭӧc tính dӵa trên dӳ liӋu hӑc, viӋc tính này dӵa vào tұp huҩn luyӋn ban ÿҫu. Tӯ xác suҩt này, ta so sánh vӟi mӝt giá trӏ ngѭӥng t (trình bày ӣ mөc ) mà ta cho là ngѭӥng ÿӇ phân loҥi email spam hay không, nӃu xác suât này lӟn hѫn t, ta cho là email ÿó là spam, ngѭӧc lҥi ta xem email ÿó là non-spam. 4.3.2 Chӑn ngѭӥng phân loҥi email : Trong phân loҥi email, có hai loҥi sai lҫm : sai lҫm nhұn mӝt email là spam mһc dù thӵc tӃ nó là non-spam (false positive) và sai lҫm thӭ hai là nhұn mӝt email là non-spam mһc dù nó là spam (false negative). Rõ ràng là sai lҫm thӭ nhҩt là nghiêm trӑng hѫn bӣi vì ngѭӡi sӱ dөng có thӇ chҩp nhұn mӝt email spam vѭӧt qua bӝ lӑc nhѭng không chҩp nhұn mӝt email hӧp lӋ quan trӑng lҥi bӏ bӝ lӑc chһn lҥi. Giҧ sӱ N ® S và S ® N tѭѫng ӭng vӟi hai lӛi sai trên ÿây Sӱ dөng luұt quyӃt ÿӏnh Bayes dӵa trên chi phí [9], ta giҧ sӱ rҵng lӛi N® S có chi phí gҩp l lҫn lӛi S®N, chúng ta phân loҥi mӝt email là spam dӵa vào tiêu chuҭn sau: 40 ( ) | ) ( | ) P C spam X x P C non spam X x l = = > = - = uur r uur r Công thӭc 4-8 Mà ( | ) 1 ( | )P C spam X x P C non spam X x= = = - = - = uur r uur r Nên ta có: ( | )P C spam X x t= = > uur r vӟi 1 t l l = + và 1 t t l = - Nhѭ vұy ngѭӥng phân loҥi ÿѭӧc chӑn là t tùy thuӝc vào giá trӏ l 41 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 42 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: 5.1.1 Khái niӋm ³Token´ : ĈӇ xem xét nӝi dung email chúng tôi dùng khái niӋm “token” Các “token” có thӇ xem nhѭ là các tӯ cҫn xem xét mà ta tách ra tӯ nӝi dung cӫa email. Vӟi các kí tӵ chӳ, kí tӵ sӕ, kí tӵ ‘$', kí tӵ gҥch ngang ‘-’, kí tӵ gҥch dѭӟi ‘_’, kí tӵ nháy ÿѫn ‘’’ là nhӳng kí tӵ cҩu tҥo thành token. Còn nhӳng kí tӵ còn lҥi nhѭ khoҧng trҳng, kí tӵ ‘*’, kí tӵ ‘:’, … ÿѭӧc xem là kí tӵ ÿӇ tách tӯ hay phân cách các tӯ. Vӟi nhӳng tӯ tách ÿѭӧc mà gӗm toàn kí sӕ thì không ÿѭӧc xem là token (ví dө: “12345”). Ví dө ta có các token sau: “qvp0045”, “ indira”, “mx-05”, “$7500”, “3d0725”, “ platinum”. NӃu ta có mӝt chuӛi sau: “” thì ta sӁ có các token tѭѫng ӭng là: “http”, “www”, “27meg”, “com”, “foo”. 5.1.2 Vector thuӝc tính : Nhѭÿã nói ӣ mөc 4.3.1, ta chuyӇn mӛi mӝt email sang mӝt vector xr =( 1x , 2x ,.., nx ) vӟi 1x , 2x ,.., nx là giá trӏ các thuӝc tính 1X , 2X ,.., nX trong không gian vector ÿһc trѭng X r . Các thuӝc tính có thӇ là mӝt token , nhóm các token …Trong trѭӡng hӧp ÿѫn giҧn nhҩt, mӛi mӝt thuӝc tính ÿѭӧc thӇ hiӋn bӣi mӝt token ÿѫn và tҩt cҧ các thuӝc tính có giá trӏ luұn lý (Boolean), nhѭ vұy iX =1 nӃu email chѭá token, trѭӡng hӧp ngѭӧc lҥi iX =0. Chúng tôi chӑn thuӝc tính là token ÿѫn, nhѭng thay vì giá trӏ cӫa các thuӝc tính là giá trӏ luұn lý (boolean), chúng tôi chӑn là xác suҩt spam cӫa mӛi token. Xác suҩt spam cӫa mӛi token sӁ có giá trӏ trong ÿӑan [0, 1].Xác suҩt cho ta nhiӅu thông tin hѫn so vӟi giá trӏ luұn lý.Ví dө : xét 43 token “$” xuҩt hiӋn trong email, nӃu ta sӱ dөng giá trӏ luұn lý, ta không ÿӫ cѫ sӣÿӇ nghi ngӡ email này là email spam, và nӃu email này khá dài thì càng khó kӃt luұn rҵng nó là spam. Tuy nhiên sӱ dөng xác suҩt, ta có thӇ biӃt ÿѭӧc khҧ năng email ÿó là spam là bao nhiêu,ÿiӅu này hӧp lý Kѫn là chӍ sӱ dөng hai giá trӏ 0 và 1.Vӟi không gian vector ÿһc trѭng X r , chúng tôi chӑn n là sӕ các thuӝc tính cӫa X r ÿӇ thӱ nghiӋm lҫn lѭӧt là 10, 15 và 20. Chӑn n sao cho không lӟn quá, nӃu n lӟn có khҧ năng nhӳng thuӝc tính không phҧi là ÿһc trѭng, nhѭ vұy sӁ làm “nhiӉu “ khҧ năng phân loҥi ÿúng.Ngѭӧc lҥi nӃu chӑn n quá nhӓ, ta sӁ không có ÿѭӧc sӕ cҫn thiӃt các thuӝc tính. 5.1.3 Chӑn ngѭӥng phân loҥi : Chúng tôi tiӃn hành thӱ nghiӋm vӟi giá trӏ l lҫn lѭӧt là 1, 9 và 999, nhѭ vұy ngѭӥng phân loҥi t xác ÿӏnh mӝt email là spam lҫn lѭӧt là 0.5, 0.9, 0.999. 5.1.4 Cách thӵc hiӋn : Chúng ta sӁ bҳt ÿҫu vӟi hai kho ngӳ liӋu email : kho ngӳ liӋu email spam và kho ngӳ liӋu email non-spam. Sӕ lѭӧng email trong mӛi kho ngӳ liӋu ban ÿҫu không hҥn chӃ. NӃu kho ngӳ liӋu càng lӟn thì hiӋu quҧ lӑc email sӁ càng cao. Tӯ hai kho ngӳ liӋu này, chúng tôi phân tích và duyӋt qua tҩt cҧ các token bao gӗm cҧ phҫn tiêu ÿӅ cӫa email.Ĉӕi vӟi nhӳng email html, chúng tôi thӵc hiӋn bóc tách các thҿ html ÿӇ lҩy nӝi dung giӳa các thҿ. Sau ÿó ta tính xác suҩt spam cӫa mӛi token ÿã ÿѭӧc phân tích, xác suҩt này chính là xác suҩt mӝt email chӍ chӭa token ÿó và là email spam. Nhѭ vұy mҩu chӕt ӣÿây là ta phҧi tính ra ÿѭӧc xác suҩt spam cӫa mӛi token. Theo Paulgraham [7], xác suҩt spam cӫa mӛi token ÿѭӧc tính dӵa trên sӕ lҫn xuҩt hiӋn cӫa mӛi token trong mӛi kho ngӳ liӋu hӑc ban ÿҫu. Ví dө mӝt token w có sӕ lҫn xuҩt hiӋn trong kho ngӳ liӋu spam là s, 44 trong kho ngӳ liӋu non-spam là n, sӕ email tәng cӝng cӫa hai kho ngӳ liӋu spam và non-spam lҫn lѭӧt là SN và NN , thӃ thì xác suҩt spam cӫa token w ÿѭӧc tính nhѭ sau: ( , ) S S N s NP X w C spam s n N N = = = + Công thӭc 5-1 Tuy nhiên, vì sӕ lҫn xuҩt hiӋn cӫa mӝt token trong mӛi kho ngӳ liӋu hӑc có khҧ năng vѭӧt quá kích thѭӟc cӫa kho ngӳ liӋu hӑc ÿó (tәng sӕ email) do ÿó, trong công thӭc trên, thay SN s bҵng Min(1, SN s ) và NN n bҵng Min(1, NN n ) Do ÿó Công thӭc 5-1viӃt lҥi nhѭ sau: (1, ) ( , ) (1, ) (1, ) S S S S N Min NP X w C spam nMin Min N N = = = + công thӭc 5-2 Theo cách trên thì chúng ta ÿánh giá khҧ năng spam cӫa mӝt token xuҩt hiӋn trong mӝt kho ngӳ liӋu hӑc 100 lҫn ӣ 100 email khác nhau là bҵng vӟi khҧ năng spam cӫa mӝt token xuҩt hiӋn trong mӝt kho ngӳ liӋu hӑc 100 lҫn nhѭng chӍӣ trong mӝt email Chúng tôi ÿӅ xuҩt mӝt cách tính xác suҩt spam cӫa token khác nhѭ sau: thay vì dӵa vào sӕ lҫn xuҩt hiӋn cӫa token trong tӯng kho ngӳ liӋu hӑc, chúng tôi dӵa vào sӕ email chӭa token trong tӯng kho ngӳ liӋu hӑc. Công thӭc tính nhѭ sau : 45 ( , ) S S S N S N n NP X w C spam n n N N = = = + công thӭc 5-3 Vӟi : ü Sn là sӕ email có chӭa token trong kho ngӳ liӋu email spam ü Nn là sӕ email có chӭa token trong kho ngӳ liӋu email non- spam ü SN là tәng sӕ email cӫa kho ngӳ liӋu hӑc spam ü NN là tәng sӕ email cӫa kho ngӳ liӋu hӑc non-spam Tuy nhiên, ta nhұn thҩy rҵng công thӭc trên ÿã ÿánh giá khҧ năng spam cӫa mӛi token là nhѭ nhau vӟi token xuҩt hiӋn 1 lҫn trong 1 email và token xuҩt hiӋn 100 lҫn trong 1 email, bӣi vì ӣ cҧ hai trѭӡng hӧp, ta ÿӅu chӍ tính thêm vào sӕ email chӭa token là 1 mà thôi Chúng ta có thӇ kӃt hӧp hai cách tính ӣ trên,ÿӇ có thӇ sӱ dөng ÿѭӧc nhiӅu thông tin vӅ token hѫn. Chúng tôi ÿӅ xuҩt thêm mӝt công thӭc nӳa - ÿѭӧc xem là sӵ kӃt hӧp giӳa hai công thӭc trên * ( , ) * * S S S N S N n b NP X w C spam n nb g N N = = = + công thӭc 5-4 Vӟi ü Sn là sӕ email có chӭa token trong kho ngӳ liӋu email spam ü Nn là sӕ email có chӭa token trong kho ngӳ liӋu email non- spam ü SN là tәng sӕ email cӫa kho ngӳ liӋu hӑc spam ü NN là tәng sӕ email cӫa kho ngӳ liӋu hӑc non-spam 46 ü b là sӕ lҫn xuҩt hiӋn cӫa token trong kho ngӳ liӋu email spam ü g là sӕ lҫn xuҩt hiӋn cӫa token trong kho ngӳ liӋu email non- spam Còn ÿӕi vӟi các token chӍ xuҩt hiӋn kho ngӳ liӋu này mà không xuҩt hiӋn ӣ kho ngӳ liӋu kia thì ta không thӇ kӃt luұn rҵng mӝt token chӍ xuҩt hiӋn ӣ kho ngӳ liӋu spam thì không bao giӡ xuҩt hiӋn trong mӝt email non-spam, và ngѭӧc lҥi. Cách thích hӧp ӣ ÿây là ta sӁ gán cho chúng mӝt giá trӏ phù hӧp [7] Nhѭ vұy, vӟi nhӳng token chӍ xuҩt hiӋn trong kho ngӳ liӋu email spam thì ta sӁ gán khҧ năng xác suҩt spam cho nó là giá trӏ N gҫn vӟi 1 (chҷng hҥn 0.9999 )và ngѭӧc lҥi thì gán xác suҩt spam là giá trӏ M gҫn vӟi 0 (chҷng hҥn 0.0001). Nhѭ vұy ta ÿã xác ÿӏnh ÿѭӧc xác suҩt spam cӫa mӝt email có chѭá mӝt token nào ÿó hay xác suҩt spam cӫa mӝt token nhѭ sau: Tính theo công thӭc 5-2, ta có : (1, ) , , (1, ) (1, ) S S S S N Min NP Max M Min N nMin Min N N æ öæ ö ç ÷ç ÷ ç ÷ç ÷= ç ÷ç ÷+ç ÷ç ÷è øè ø Công thӭc 5-5 :công thӭc tính xác suҩt spam cӫa token dӵa trên sӕ lҫn xuҩt hiӋn Tính theo công thӭc 5-3, ta có : , , S S S N S N n NP Max M Min N n n N N æ öæ ö ç ÷ç ÷ ç ÷ç ÷= ç ÷ç ÷+ç ÷ç ÷è øè ø Công thӭc 5-6 :công thӭc tính xác suҩt spam cӫa token dӵa trên sӕ email chӭa token Tính theo công thӭc 5-4 47 * , , * * S S S N S N n s NP Max M Min N n ns n N N æ öæ ö ç ÷ç ÷ ç ÷ç ÷= ç ÷ç ÷+ç ÷ç ÷è øè ø Công thӭc 5-7 :ctính xác suҩt spam cӫa token dӵa trên sӕ lҫn xuҩt hiӋn và sӕ email chӭa nó Vӟi : ü s là sӕ lҫn xuҩt hiӋn cӫa token trong kho ngӳ liӋu hӑc spam ü n là sӕ lҫn xuҩt hiӋn cӫa token trong kho ngӳ liӋu hӑc non- spam ü Sn là sӕ email chӭa token trong kho ngӳ liӋu hӑc spam ü Nn là sӕ email chӭa token trong kho ngӳ liӋu hӑc non-spam ü SN là tәng sӕ email chӭa trong kho ngӳ liӋu hӑc spam ü NN là tәng sӕ email chӭa trong kho ngӳ liӋu hӑc non-spam Mӝt vҩn ÿӅ phӭc tҥp mà chúng tôi gһp phҧi trong quá trình thӵc hiӋn phân loҥi email dӵa trên thuұt toán Naïve Bayesian là viӋc tách token và tính xác suҩt spam cӫa token, bӣi vì sӕ token là khá lӟn, ӣÿây chúng tôi sӱ dөng cҩu trúc dӳ liӋu là bҧng băm.Ӭng vӟi mӛi kho ngӳ liӋu email spam và non-spam chúng tôi xây dӵng mӝt bҧng băm tѭѫng ӭng.Bҧng băm này sӁ bao gӗm token và sӕ email chӭa token hoһc sӕ lҫn xuҩt hiӋn cӫa token trong tӯng kho ngӳ liӋu tѭѫng ӭng, hoһc có thӇÿӗng thӡi chӭa ba thông tin này – tùy theo chúng ta áp dөng cách tính xác suҩt spam nào cho mӛi token. Nhѭ vұy mӛi token sӁ có mӝt giá trӏ băm (xác ÿӏnh bҵng hàm băm tӵÿӏnh nghƭa ) tѭѫng ӭng vӟi vӏ trí trên bҧng băm ÿӇ ta có thӇ truy xuҩt nhanh ÿӃn phҫn tӱ token trên bҧng. Mөc ÿích xây dӵng bҧng băm là ÿӇ tӕi ѭu hóa tӕc ÿӝ truy xuҩt các token trích tӯ email cNJng nhѭ tӕi ѭu thӡi gian xác ÿӏnh mӝt email là spam hay không. Mӛi phҫn tӱ cӫa bҧng băm lѭu trӳ token, sӕ lҫn xuҩt hiӋn (hoһc sӕ email có chӭa token ÿó ), hoһc xác suҩt spam cӫa nó, tùy theo mөc ÿích xӱ lý cө thӇ mà mӛi phҫn tӱ 48 cӫa bҧng băm sӁ mang nhӳng thông tin khác nhau. Bҧng băm ÿѭӧc mô tҧ nhѭ sau: Hình 5-1Mô tҧ cҩu trúc bҧng băm Sau khi có 2 bҧng băm tѭѫng ӭng vӟi hai kho ngӳ liӋu email, ta sӁ xây dӵng bҧng băm thӭ ba. Mӛi phҫn tӱ trong bҧng băm này sӁ lѭu nhӳng thông tin gӗm: token và khҧ năng (xác suҩt) spam cӫa token.Tuy nhiên ÿӇ viӋc thӵc hiӋn tiӋn lӧi và không phҧi xét quá nhiӅu token, chúng tôi chӍ xem xét nhӳng token mà sӕ lҫn xuҩt hiӋn cӫa nó hoһc sӕ email chӭa nó trong cѫ sӣ dӳ hӑc ban ÿҫu lӟn hѫn mӝt ngѭӥng nào ÿó, vӟi nhӳng token mà tәng sӕ lҫn xuҩt hiӋn hoһc tәng sӕ email chӭa nó nhӓ hѫn ngѭӥng này, chúng tôi không tính xác suҩt cho token ÿó. ĈLӅu này là hӧp lý bӣi vì nhӳng token có tәng sӕ lҫn xuҩt hiӋn ( hoһc tәng sӕ email chӭa nó quá ít thì cNJng không ÿáng ÿӇ xem xét ÿӃn, do ÿó sӁ giúp giҧm bӟt sӕ token cҫn tính xác suҩt cNJng nhѭ dung lѭӧng lѭu trӳ cho dӳ liӋu ӣ bҧng băm thӭ ba này.Ӣÿây chúng tôi thӱ nghiӋm lҫn lѭӧt hai ngѭӥng 3 và 5, kӃt quҧ thӵc hiӋn ӣ hai ngѭӥng này gҫn nhѭ là tѭѫng ÿѭѫng nhau, cuӕi cùng chúng tôi chӑn giá trӏ 3. Theo Paulgraham [7] thì chúng ta cҫn hҥn chӃ loҥi lӛi false positive (nhұn email non-spam thành email spam ), do ÿó sӕ lҫn xuҩt hiӋn cӫa các token hoһc sӕ email chӭa token trong kho ngӳ liӋu non-spam sӁÿѭӧc 49 nhân vӟi mӝt trӑng sӕ W,ÿiӅu này giúp phân biӋt ÿѭӧc giӳa nhӳng token thӍnh thoҧng xuҩt hiӋn trong các email hӧp lӋ vӟi nhӳng token hҫu nhѭ không xuҩt hiӋn, chúng tôi thӱ nghiӋm lҫn lѭӧt vӟi hai giá trӏ 1 và 2. Ví dө thông tin bҧng băm thӭ 3: Token: Khҧ năng spam : madam 0.99 promotion 0.99 republic 0.99 shortest 0.047225013 mandatory 0.047225013 standardization 0.07347802 Cách tính xác suҩt spam cho mӛi token ÿѭӧc thӵc hiӋn theo các công thӭc nhѭÿã nói ӣ trên. Cuӕi cùng ÿӇ xác ÿӏnh mӝt email mӟi ÿӃn có phҧi là spam không thì chúng tôi trích ra n token ӣ trong email ÿó.Cách chӑn mүu tұp thuӝc tính ÿӇ xét thông thѭӡng là chӑn ra n token mӝt cách ngүu nhiên, tuy nhiên nhұn thҩy rҵng nhӳng token trung tính ( khҧ năng spam là 0.4-0.6 thì không có tác dөng lҳm trong viӋc nhұn dҥng email spam ) nên ta chӑn n token này vӟi ÿӏnh hѭӟng là chӑn nhӳng token ÿһc trѭng cho mӝt email spam và email non-spam, chúng tôi chӑn nhӳng token có khҧ năng spam cao nhҩt và thҩp nhҩt. Nhѭ vұy chúng tôi chӑn n token có khoҧng cách giӳa xác suҩt spam cӫa chúng vӟi giá trӏ trung tính 0.5 là cao nhҩt Chúng ta gӑi giá trӏ này là giá trӏ “ÿһc trѭng”. Nhѭ vұy ta sӁ chӑn ÿѭӧc nhӳng token hoһc là có khҧ năng spam cao nhҩt (xác suҩt spam cao nhҩt ) hoһc là nhӳng token có khҧ năng non-spam cao nhҩt ( xác suҩt spam thҩp nhҩt ). NӃu có k (k ³ 2) token có cùng giá trӏ “ÿһc trѭng “, bӣi vì khҧ năng xuҩt hiӋn cӫa k token này ngang nhau, do ÿó hoàn toàn không mҩt tính tәng quát, chúng tôi chӑn token ÿҫu tiên trong k token có cùng giá trӏ “ ÿһc trѭng “này. Sau khi chӑn ÿѭӧc n token này chúng tôi sӁ tra trong bҧng 50 Eăm thӭ 3 ( lѭu token và khҧ năng spam cӫa nó) ÿӇ lҩy ra khҧ năng spam riêng cӫa mӛi token. NӃu không tìm thҩy khҧ năng spam riêng cho token trong bҧng băm,có nghƭa là token này là mӟi – chѭa có trong cѫ sӟ dӳ liӋu token cӫa ta.Mӝt token chѭa tӯng xuҩt hiӋn trong kho ngӳ liӋu hӑc thì khҧ Qăng spam cӫa nó tѭѫng ÿӕi thҩp [7], chúng tôi lҩy giá trӏ trung tính 0.4. Tӯÿó chúng tôi tính khҧ năng tәng hӧp mӝt email chӭa n token này là spam. Cách tính khҧ năng tәng hӧp :chúng tôi dӵa vào Công thӭc 4-7 { } i 1 , 1 ( ). ( | ) ( | ) ( ). ( | ) n i i n i i k spam non spam i P C c P X x C c P C c X x P C k P X x C k = Î - = = = = = = = = = = Õ å Õ uur r ThӃ thì xác suҩt spam tәng hӧp cӫa mӝt email Cÿѭӧc xét là : }{ 1 , 1 ( ) ( | ) ( | ) ( ). ( | ) n i i i n i i k spam non spam i P C spam P X x C c P C spam X x P C k P X x C k = Î - = = = = = = = = = = Õ å Õ uur r Ví dө Token: Xác sṷt (Probability): madam 0.99 promotion 0.99 shorstest 0.047225013 Xác suҩt mӝt email là Spam là :0.6 à Khҧ năng kӃt hӧp 0.99*0.99*0.047225013*0.6 0.6*0.99*0.99*0.047225013 (1-0.6)*(1-0.99)(1-0.99)(1-0.047225013) = + Sau khi có khҧ năng tәng hӧp, chúng tôi so sánh vӟi các giá trӏ ngѭӥng ( ÿã nói ӣ mөc 4.3.1) ÿӇ phân loҥi email spam hay non-spam, nӃu xác suҩt spam tәng hӧp cӫa email lӟn hѫn ngѭӥng t chúng tôi kӃt luân email ÿó là spam, ngѭӧc lҥi email ÿó là non-spam. 51 5.2 Thӱ nghiӋm hiӋu quҧ phân loҥi 5.2.1 Thӱ nghiӋm vӟi kho ngӳ liӋu pu: Bӣi vì kho ngӳ liӋu hӑc và kiӇm thӱ là sӕ, do ÿó chúng tôi thay ÿәi vӅ cách lҩy token, ӣÿây chúng tôi xem token là các con sӕ, và dҩu hiӋu tách token là các khoҧng trҳng. 5.2.1.1 Kӏch bҧn kiӇm thӱ : Chúng tôi thӱ nghiӋm nhân trӑng sӕ non-spam W vӟi 1 và 2 Vӟi mӛi W, chúng tôi thӱ nghiӋm vӟi l lҫn lѭӧt vӟi các giá trӏ 1, 9, và 999 7ѭѫng ӭng vӟi mӛi giá trӏ l và W chúng tôi thӵc hiӋn tính xác suҩt spam theo các công thӭc :Công thӭc 5-5, Công thӭc 5-6 và Công thӭc 5-7 Sӕ token ÿѭӧc lҩy lҫn lѭӧt là 10, 15, 20 Chúng tôi kiӇm tra vӟi các kho ngӳ liӋu pu1, pu2, pu3 và puA 7ѭѫng ӭng vӟi mӛi kho ngӳ liӋu trên chúng tôi cho hӑc tӯ part1 ÿӃn part 9, sau ÿó chúng tôi thӱ nghiӋm phân loҥi trên part10, chӭa nhӳng email chѭa ÿѭӧc hӑc. 5.2.1.2 KӃt quҧ thӱ nghiӋm vӟi kho ngӳ liӋu pu : KӃt quҧ thӵc hiӋn: chúng tôi trình bày kӃt quҧ thӵc hiӋn vӟi trѭӡng hӧp nhân trӑng sӕ non-spam W=2, kӃt quҧ chi tiӃt vӟi W=1 xin xem phҫn phө lөc. 52 v KӃt quҧ kiӇm thӱ trên PU1: Công thӭc 5-5 Công thӭc 5-6 Công thӭc 5-7 l 10 15 20 10 15 20 10 15 20 16ĺS 44 45 45 45 45 44 46 46 47 6ĺN 4 3 3 3 3 4 2 2 1 1ĺN 61 61 61 61 61 61 61 61 61 1ĺS 0 0 0 0 0 0 0 0 0 SR 91.67% 93.75% 93.75% 93.75% 93.75% 91.67% 95.83% 95.83% 97.92% SP 100.00% 100.00% 100.00% 100.00% 100.00% 100.00% 100.00% 100.00% 100.00% TCR 12 16 16 16 16 12 24 24 48 96ĺS 44 45 45 44 44 44 45 46 47 6ĺN 4 3 3 4 4 4 3 2 1 1ĺN 61 61 61 61 61 61 61 61 61 1ĺS 0 0 0 0 0 0 0 0 0 SR 91.67% 93.75% 93.75% 91.67% 91.67% 91.67% 93.75% 95.83% 97.92% SP 100.00% 100.00% 100.00% 100.00% 100.00% 100.00% 100.00% 100.00% 100.00% TCR 12 16 16 12 12 12 16 24 48 9996ĺS 43 43 43 43 43 43 45 45 47 6ĺN 5 5 5 5 5 5 3 3 1 1ĺN 61 61 61 61 61 61 61 61 61 1ĺS 0 0 0 0 0 0 0 0 0 SR 89.58% 89.58% 89.58% 89.58% 89.58% 89.58% 93.75% 93.75% 97.92% SP 100.00% 100.00% 100.00% 100.00% 100.00% 100.00% 100.00% 100.00% 100.00% TCR 9.6 9.6 9.6 9.6 9.6 9.6 16 16 48 %ҧ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 53 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 ( 9l = ) 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 ( 9l = ) 54 v KӃt quҧ kiӇm thӱ trên PU2: Công thӭc 5-5 Công thӭc 5-6 Công thӭc 5-7 l 10 15 20 10 15 20 10 15 20 1SĺS 7 8 9 7 8 8 8 9 5 6ĺN 7 6 5 7 6 6 6 5 9 1ĺN 57 57 57 57 57 57 57 57 57 1ĺS 0 0 0 0 0 0 0 0 0 SR 50.00% 57.14% 64.29% 50.00% 57.14% 57.14% 57.14% 64.29% 35.71% SP 100.00% 100.00% 100.00%100.00% 100.00% 100.00% 100.00% 100.00% 100.00% TCR 22.333333 2.8 22.3333332.3333332.333333 2.81.555556 9SĺS 7 8 8 7 8 8 8 8 5 6ĺN 7 6 6 7 5 6 6 6 9 1ĺN 57 57 57 57 57 57 57 57 57 1ĺS 0 0 0 0 0 0 0 0 0 SR 50.00% 57.14% 57.14% 50.00% 61.54% 57.14% 57.14% 57.14% 35.71% SP 100.00% 100.00% 100.00%100.00% 100.00% 100.00% 100.00% 100.00% 100.00% TCR 22.3333332.333333 2 2.62.3333332.3333332.3333331.555556 999SĺS 7 8 8 7 6 7 8 5 5 6ĺN 7 6 6 7 8 7 6 9 9 1ĺN 57 57 57 57 57 57 57 57 57 1ĺS 0 0 0 0 0 0 0 0 0 SR 50.00% 57.14% 57.14% 50.00% 42.86% 50.00% 57.14% 35.71% 35.71% SP 100.00% 100.00% 100.00%100.00% 100.00% 100.00% 100.00% 100.00% 100.00% TCR 22.3333332.333333 2 1.75 22.3333331.5555561.555556 %ҧ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 55 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 ( 9l = ) 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 ( 9l = ) 56 v KӃt quҧ kiӇm thӱ trên PU3: Công thӭc 5-5 Công thӭc 5-6 Công thӭc 5-7 l 10 15 20 10 15 20 10 15 20 1SĺS 169 168 168 167 169 165 165 172 170 6ĺN 13 14 14 15 13 17 17 10 12 1ĺN 228 228 227 228 228 229 226 222 224 1ĺS 3 3 4 3 3 2 5 9 7 SR 92.86% 92.31% 92.31% 91.76% 92.86% 90.66% 90.66% 94.51% 93.41% SP 98.26% 98.25% 97.67% 98.24% 98.26% 98.80% 97.06% 95.03% 96.05% TCR 11.37510.7058810.1111110.11111 11.3759.5789478.2727279.5789479.578947 9SĺS 167 168 168 164 166 163 165 171 170 6ĺN 15 14 14 18 16 19 17 11 12 1ĺN 229 228 227 228 229 229 227 222 225 1ĺS 2 3 4 3 2 2 4 9 6 SR 91.76% 92.31% 92.31% 90.11% 91.21% 89.56% 90.66% 93.96% 93.41% SP 98.82% 98.25% 97.67% 98.20% 98.81% 98.79% 97.63% 95.00% 96.59% TCR 5.5151524.439024 3.644.0444445.3529414.9189193.4339621.9782612.757576 999SĺS 163 163 165 160 156 156 163 168 169 6ĺN 19 19 17 22 26 26 19 14 13 1ĺN 229 229 229 229 229 229 227 225 225 1ĺS 2 2 2 2 2 2 4 6 6 SR 89.56% 89.56% 90.66% 87.91% 85.71% 85.71% 89.56% 92.31% 92.86% SP 98.79% 98.79% 98.80% 98.77% 98.73% 98.73% 97.60% 96.55% 96.57% TCR 0.0902330.0902330.0903230.0900990.0899210.089921 0.045330.0302930.030298 %ҧ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 57 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 ( 9l = ) 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 ( 9l = ) 58 v .Ӄt quҧ kiӇm thӱ trên PUA: Công thӭc 5-5 Công thӭc 5-6 Công thӭc 5-7 l 10 15 20 10 15 20 10 15 20 16ĺS 46 46 46 43 42 41 50 48 46 6ĺN 11 11 11 14 15 16 7 9 11 1ĺN 57 56 57 57 57 57 56 56 57 1ĺS 0 1 0 0 0 0 1 1 0 SR 80.70% 80.70% 80.70% 75.44% 73.68% 71.93% 87.72% 84.21% 80.70% SP 100.00% 97.87% 100.00% 100.00% 100.00% 100.00% 98.04% 97.96% 100.00% TCR 5.181818 4.75 5.181818 4.071429 3.8 3.5625 7.125 5.7 5.181818 96ĺS 46 46 45 42 41 38 49 46 45 6ĺN 11 11 12 15 16 19 8 11 12 1ĺN 57 56 57 57 57 57 56 55 57 1ĺS 0 1 0 0 0 0 1 2 0 SR 80.70% 80.70% 78.95% 73.68% 71.93% 66.67% 85.96% 80.70% 78.95% SP 100.00% 97.87% 100.00% 100.00% 100.00% 100.00% 98.00% 95.83% 100.00% TCR 5.181818 2.85 4.75 3.8 3.5625 3 3.352941 1.965517 4.75 9996ĺS 43 43 42 41 37 35 47 45 44 6ĺN 14 14 15 16 20 2 10 12 13 1ĺN 57 57 57 57 57 57 56 57 57 1ĺS 0 0 0 0 0 0 1 0 0 SR 75.44% 75.44% 73.68% 71.93% 64.91% 94.59% 82.46% 78.95% 77.19% SP 100.00% 100.00% 100.00% 100.00% 100.00% 100.00% 97.92% 100.00% 100.00% TCR 4.071429 4.071429 3.8 3.5625 2.85 18.5 0.056492 4.75 4.384615 %ҧ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 59 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 ( 9l = ) 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 ( 9l = ) 60 Nhұn xét :kӃt quҧ kiӇm thӱ trên các kho ngӳ liӋu PU là khá tӕt, hiӋu quҧ phân loҥi giӳa các công thӭc là không quá khác biӋt, vӟi cách chӑn 9l = và 1l = hiӋu quҧ hѫn vӟi 999l = , theo chúng tôi thì kho ngӳ liӋu không lӟn lҳm nên sӱ dөng 999l = thì không hiӋu quҧ bҵng. VӅ cách chӑn sӕ token, hiӋu quҧ phân loҥi khi chӑn sӕ token là 10, 15 hay 20 cNJng không khác biӋt lҳm. 5.2.2 Thӱ nghiӋm vӟi kho ngӳ liӋu email chӳ : 5.2.2.1 Kӏch bҧn kiӇm thӱ : Sau khi ÿã thӱ nghiӋm vӟi kho ngӳ liӋu sӕ, chúng tôi chӑn mӝt bӝ ( l , n, W) ÿӇ kiӇm thӱ vӟi kho ngӳ liӋu email chӳ. Chúng tôi thӱ nghiӋm vӟi bӝ dӳ liӋu l = 9, sӕ token là 15, trӑng sӕ non-spam là 2. Ngӳ liӋu hӑc và kiӇm thӱӣÿây gӗm ngӳ liӋu email là email văn bҧn trѫn (text/plain), và ngӳ liӋu email html. Ngӳ liӋu email văn bҧn trѫn có sӕ email dùng ÿӇ huҩn luyӋn là :517 email non-spam, 528 email spam. Ngӳ liӋu dung ÿӇ kiӇm thӱ gӗm 98 email spam, 100 email non-spam. Ngӳ liӋu email html có sӕ email dùng ÿӇ huҩn luyӋn là 141 email non-spam, 155 email spam, sӕ email dung ÿӇ kiӇm thӱ là 50 email spam, 50 email non- spam. 5.2.2.2 KӃt quҧ kiӇm thӱ : Ngӳ liӋu email văn bҧn trѫn: · Ngӳ liӋu hӑc :sӕ email spam :517, sӕ email non- spam:528 · Ngӳ liӋu kiӇm thӱ :sӕ email spam :98, sӕ email non- spam :100 Ngӳ liӋu email html, sӕ email kiӇm thӱ :Spam =50, non-spam=50 61 %ҧ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ӳ KӃt quҧ thӵc hiӋn vӟi ngӳ liӋu email văn bҧn (text/plain) khá tӕt, các chӍ sӕ spam recall, spam precision khá cao, tuy nhiên thӵc hiӋn vӟi kho ngӳ liӋu email html thì chӍ sӕ spam recall không ÿѭӧc cao trong khi chӍ sӕ spam precision vүn tӕt. KӃt quҧ này mӝt phҫn vì kho ngӳ liӋu email html cӫa chúng tôi không ÿѭӧc lӟn lҳm, sӕ lѭӧng email html dùngÿӇ huҩn luyӋn Wѭѫng ÿӕi ít. Email html có ÿһc ÿLӇm là nӝi dung cӫa nó hҫu hӃt là các thҿ html, nhӳng thҿ html này không cung cҩp ÿѭӧc nhiӅu thông tin trong viӋc phân lӑai, nӝi dung chӳ thұt sӵ tѭѫng ÿӕi ít, ÿLӅu này cNJng ҧnh Kѭӣng ÿӃn kӃt quҧ thӵc hiӋn cӫa thuұt tóan Naïve Bayesian 5.3 Ѭu ± nhѭӧc ÿLӇm cӫa phѭѫng pháp phân loҥi Naïve Bayesian: 5.3.1 Ѭu ÿLӇm : · Mӝt ѭu ÿiӇm cӫa bӝ lӑc Bayes là nó cho phép hӑc spam. Nghƭa là, khi có mӝt email spam vӵѫt qua ÿѭӧc bӝ lӑc thì ngѭӡi dùng có thӇÿánh dҩu spam cho email ÿó và bӝ lӑc sӁ tӵ phân tích email spam ÿó và cұp nhұt thêm vào kho ngӳ liӋu spam. · HiӋu quҧ phân loҥi là khá cao Công thӭc 5-5 Công thӭc 5-6 Công thӭc 5-7 TEXT 6ĺS 96 94 96 6ĺN 2 4 2 1ĺN 99 99 99 1ĺS 1 1 1 SR 97.96% 95.92% 97.96% SP 98.97% 98.95% 98.97% TCR 32.66667 19.6 32.66667 HTML SĺS 32 24 23 6ĺN 18 26 27 1ĺN 50 50 50 1ĺS 0 0 0 SR 64.00% 48.00% 46.00% SP 100.00% 100.00% 100.00% TCR 2.777778 1.923077 1.851852 62 · Thӡi gian huҩn luyӋn nhanh, theo Charles Elkan [16] vӟi e mүu huҩn luyӋn và sӕ thuӝc tính là f thӡi gian cҫn thiӃt ÿӇ huҩn luyӋn phân lӑai Naïve Bayesian là hàm tuyӃn tính O(ef), không có thuұt tóan máy hӑc nào có thӇ khҧo sát vӟi cùng dӳ liӋu huҩn luyӋn ÿó nhanh hѫn Naïve Bayesian · Ngoài nhӳng bӝ lӑc ÿѭӧc xây dӵng sҹn dӵa trên kho ngӳ liӋu email có trѭӟc, thì vӟi mӛi ngѭӡi dùng sӁ có bӝ lӑc riêng ÿѭӧc xây dӵng dӵa trên kho ngӳ liӋu hӑc email cӫa chính hӑ. Do ÿó, viӋc ÿѭa spam vѭӧt qua ÿѭӧc bӝ lӑc xây dӵng sҹn thì không chҳc là nó có thӇ vѭӧt qua ÿѭӧc bӝ lӑc cӫa tӯng ngѭӡi dùng cө thӇ. 5.3.2 KhuyӃt ÿLӇm : · KhuyӃt diӇm cӫa phѭѫng pháp phân loҥi Bayes chính là viӋc phҧi huҩn luyӋn cho nó · KhuyӃt ÿLӇm thӭ hai là hiӋu quҧ phân lӑai phө thuӝc vào kho ngӳ liӋu huҩn luyӋn ban ÿҫu, nӃu ngӳ liӋu không ÿӫ lӟn, kӃt quҧ phân lӑai sӁ bӏ ҧnh hѭӣng. · Dӳ liӋu ÿã qua huҩn luyӋn là khá nhiӅu, làm tăng dung lѭӧng lѭu trӳ. 63 Chѭѫng 6 : PHѬѪNG PHÁP ADABOOST VÀ ӬNG DӨNG PHÂN LOҤI EMAIL 64 Thuұt toán Adaboost (Adaptive Boost)[15],ÿѭӧc giӟi thiӋu lҫn ÿҫu vào năm 1995 bӣi Freund và Schapire [10],[11], là mӝt trong các thuұt toán theo phѭѫng pháp Boosting. Boosting là mӝt trong các phѭѫng pháp mӟi nhҩt ÿѭӧc ÿӅ xuҩt dùng ÿӇ nâng cao khҧ năng dӵÿoán ÿúng [12]. Boosting ÿѭӧc áp dөng trong các bài toán phân loҥi và hӗi qui. Boosting kӃt hӧp các luұt “yӃu “ (weak rule) có ÿӝ chính xác dӵÿoán thҩp ÿӇ cho ra mӝt luұt có ÿӝ chính xác dӵÿoán cao [12]. Thông thѭӡng mӛi mӝt luұt yӃu là mӝt luұt ÿѫn giҧn, có thӇ dӵa vào ÿó ÿӇ dӵÿoán ÿӕi tѭӧng ÿѭӧc xét thuӝc vӅ loҥi nào, tuy nhiên ÿӝ chính xác cӫa dӵÿoán là không cao. Các luұt yӃu sӁÿѭӧc huҩn luyӋn tuҫn tӵ dӵa trên các mүu huҩn luyӋn rҩt khó dӵÿoán ÿúng nӃu chӍ căn cӭ vào các luұt ÿã có trѭӟc. Các thuұt toán boost gӗm AdaBoost, Uboost, LPBoost, LPUBoost ….Ӣÿây chúng tôi tұp trung vào AdaBoost, và AdaBoost ӭng dөng trong lƭnh vӵc phân loҥi văn bҧn 6.1 Thuұt toán AdaBoost : Mô tҧ phác thҧo thuұt toán nhѭ sau: Hình 6-1 Mô tҧ thuұt toán AdaBoost Thuұt toán sӁ tìm ra mӝt tұp các luұt yӃu bҵng cách gӑi thӵc hiӋn lһp ÿi lһp lҥi mӝt thӫ tөc WeakLearner vӟi sӕ lҫn T. Nhӳng luұt yӃu này sӁÿѭӧc kӃt hӧp tuyӃn tính lҥi ÿӇ cho ra mӝt luұt phân loҥi mҥnh hѫn : 1 ( ) ( ) T t t H x h x = = å . Thӫ tөc · Cho mӝt tұp huҩn luyӋn 1 1 2 2( , ), ( , ),..., ( , )m mx y x y x y · { }1, 1iy Î - + là nhãn ÿúng cӫa mӛi ix trong tұp X · Vӟi mӛi t, t=1,…T o Xây dӵng hàm phân phӕi ( )tD i tѭѫng ӭng 1...i m= o Chӑn mӝt luұt yӃu { }: 1, 1th X ® - + vӟi lӛi Pr [ ( ) ] tt D t i i h x ye = ¹ là nhӓ nhҩt bҵng thӫ tөc WeakLearner · Ra : hàm dùng ÿӇ dӵÿoán H 65 WeakLearner dùng ÿӇ chӑn ra luұt yӃu có lӛi phân loҥi sai nhӓ nhҩt tѭѫng ӭng trong mӛi bѭӟc chҥy t=1, … T, kӃt quҧ là ta có ÿѭӧc tұp luұt ÿã huҩn luyӋn gӗm T luұt yӃu. Lӛi xҧy ra khi ( )i iH x y¹ , thuұt toán AdaBoost xây dӵng thӫ tөc WeakLearner chӑn lӵa luұt yӃu sao cho tѭѫng ӭng vӟi luұt yӃu ÿѭӧc chӑn lӛi sai e ÿѭӧc giҧm tӕi ÿa. Thuұt toán tìm cách duy trì mӝt tұp các trӑng sӕ tѭѫng ӭng vӟi tұp mүu huҩn luyӋn. Mӭc ҧnh hѭӣng cӫa trӑng sӕ vӟi mүu hӑc i ӣ lҫn t là ( )tD i Trong quá trình hӑc, các trӑng sӕ sӁÿѭӧc cұp nhұt ÿӝng. NӃu phân loҥi sai trӑng sӕ sӁ tăng lên nhҩn mҥnh nhӳng mүu huҩn luyӋn bӏ phân loҥi sai, ngѭӧc lҥi, trӑng sӕ giҧm xuӕng [15]. 6.2 AdaBoost trong phân loҥi văn bҧn nhiӅu lӟp : Mӝt trong các lƭnh vӵc ӭng dөng quan trӑng cӫa thuұt toán AdaBoost là phân loҥi văn bҧn. Trong phân loҥi văn bҧn vӟi nhiӅu lӟp, có hai thuұt toán AdaBoost mӟi nhҩt là AdaBoost.MH và AdaBoost.MR, trong phҥm vi luұn văn này chúng tôi tұp trung nghiên cӭu thuұt toán AdaBoost.MH. Xét bài toán phân loҥi văn bҧn nhiӅu lӟp (nhãn ), X biӇu thӏ tұp các văn bҧn và Y là tұp có giӟi hҥn các nhãn hoһc lӟp.Ĉӏnh nghƭa kích thuӟc cӫa Y là k= | Y |. Trong trѭӡng hӧp phân loҥi nhiӅu lӟp, mӛi mӝt văn bҧn x Î X ÿѭӧc gán nhiӅu nhãn trong Y. Mӝt ví dө dӉ thҩy là phân loҥi tin tӭc là mӝt dҥng phân loҥi văn bҧn nhiӅu lӟp, mӛi mӝt tin có thӇ phù hӧp vӟi nhiӅu lӟp, chҷng hҥn mӝt tin có thӇ thuӝc vӅ nhiӅu loҥi nhѭ tin xã hӝi, kinh tӃ, văn hoá... NKѭ vұy mӛi mүu sӁÿѭӧc gán nhãn là mӝt cһp (x,Y) vӟi YÍ Y là mӝt tұp các nhãn ÿѭӧc gán cho x. Vӟi YÎ Y,ÿӏnh nghƭa Y[l] cho lÎ Y là Y[l]= +1 nӃu l Î Y -1 nӃu lÏ Y Phân loҥi nhiӅu lӟp ӣÿây là tìm cách xӃp hҥng các nhãn mà x có thӇ có.Mөc ÿích cӫa viӋc huҩn luyӋn là thu ÿѭӧc mӝt hàm f: X´ Y® R sao cho vӟi mӛi văn bҧn x, nhӳng nhãn trong Y sӁÿѭӧc sҳp xӃp theo thӭ tӵ ( ),.f x . Nhѭ vұy, nӃu 66 Cho ( ) ( ) ( )1 1 2 2, , , ,..., ,m mx Y x Y x Y , ix Î X và iY Í Y. · Khӣi tҥo 1 1( , )D i l mk = · Vӟi mӛi t =1,…, T o Huҩn luyӋn tұp hӑc yӃu sӱ dөng tD o Chӑn mӝt luұt yӃu th : X ´Y® R bҵng thӫ tөc WeakLearner o Chӑn t Ra Î o Cұp nhұt ( ) ( ) [ ] ( )( )t1 , exp - , , t i t it t D i l Y l h x l D i l Z a + = tZ ÿѭӧc chӑn sao cho 1tD + là hàm phân phӕi Ra : ( )( ) ( ) ( ) 1 ( ) , T t t t H x sign f x f x h xa = = = å ( ) ( )1 2, ,f x l f x l> thì 1l ÿѭӧc xem là có thӭ hҥng ѭu tiên xӃp loҥi cao hѫn 2l . Thuұt toán huҩn luyӋn ÿѭӧc xem là thành công nӃu vӟi mӛi x có tұp nhãn tѭѫng ӭng là Y thì thuұt toán sӁ xӃp hҥng các nhãn trong Y cao hѫn các nhãn không có trong Y Thuұt toán AdaBoost MH phân loҥi văn bҧn nhiӅu lӟp : Cho S là tұp mүu huҩn luyӋn ( ) ( ) ( )1 1 2 2, , , ,..., ,m mx Y x Y x Y vӟi ix Î X và iY Í Y. Ӣ mӛi bѭӟc thӵc hiӋn t, thӫ tөc WeakLearner sӁ chӑn mӝt luұt yӃu h: X ´Y® R,dҩu cӫa h(x, l) cho biӃt nhãn lÿѭӧc gán hay không gán cho x, còn giá trӏ | h(x, l)| ÿѭӧc xem là ÿӝ tin cұy cӫa dӵÿoán Thuұt toán AdaBoost MH phân loҥi văn bҧn vӟi nhiӅu lӟp [14] Hình 6-2 Mô tҧ thuұt toán AdaBoost MH phân loҥi văn bҧn nhiӅu lӟp Luұt yӃu th ÿѭӧc chӑn sao cho giá trӏ ( ) [ ] ( )( )t 1 , exp - , m t t i t i i l Z D i l Y l h x la = = åå nhӓ nhҩt 6.3 Ӭng dөng AdaBoost trong phân loҥi email: Bài toán chúng ta ÿang xét là phân loҥi email, ӣÿây chúng ta chӍ phân loҥi email hoһc là loҥi spam hoһc là loҥi non-spam. Nhѭ vұy bài toán phân loҥi email là trѭӡng hӧp ÿһc biӋt cӫa phân loҥi văn bҧn nhiӅu lӟp, khi mӛi mүu huҩn luyӋn chӍ 67 nhұn mӝt nhãn ÿѫn – thay vì mӝt tұp nhãn. Khi ÿó phân loҥi email vӟi hai lӟp spam và non-spam trӣ thành bài tóan phân loҥi văn bҧn nhӏ phân. 6.3.1 Thuұt toán AdaBoost.MH trong truӡng hӧp phân loҥi nhӏ phân Xét bài toán hai lӟp, mүu huҩn luyӋn là tұp ( ) ( ) ( ){ }1 1 2 2, , , ,..., ,m mS x y x y x y= gӗm m bӝ ( , )i ix y ÿã ÿѭӧc gán nhãn, ix là các mүu huҩn luyӋn thuӝc vӅ không gian mүu huҩn luyӋn X và iy Î {-1, +1} là lӟp hay nhãn tѭѫng ӭng gҳn vӟi ix . Mөc ÿích cӫa viӋc hӑc là có ÿѭӧc mӝt hàm H: X® R, sao cho vӟi mӛi mүu x, dҩu cӫa H(x) cho biӃt lӟp mà x thuӝc vӅ (-1 hay +1 ), và ÿӝ lӟn |H(x)| cho biӃt ÿӝ tin cұy ÿѭӧc dӵÿoán. Mӝt hàm nhѭ thӃ có thӇ dùng cho viӋc phân loҥi hay xӃp loҥi các mүu chѭa gһp. Mã giҧ cӫa AdaBoost.MH trong trѭӡng hӧp phân loҥi nhӏ phân nhѭ sau: 68 Thӫ tөc Adaboost Vào :S= miii yx 1)},{( = # S là tұp mүu huҩn luyӋn # khӣi tҥo hàm phân phӕi 1D (Cho tҩt cҧ i, 1 ” i ” m ) 1D (i)= 1/m Lһp :vӟi mӑi t : t:=1 …T Huҩn luyӋn tұp hӑc yӃu sӱ dөng phân bӕ tD Chӑn mӝt luұt yӃu th :X® R dùng thӫ tөc WeakLearner Chӑn a t Î R, Cұp nhұt tD ( cho tҩt cҧ i, 1 ” i ” m ) 1 ( )exp( ( ))( ) t t i t it t D i y h xD i Z a + - = # tZ là hӋ sӕ chuҭn hoá ( tZ ÿѭӧc chӑn sao cho 1+tD là hàm #phân phӕi HӃt lһp Ra: luұt kӃt hӧp ÷ ø ö ç è æ = å = T t tt xhsignxH 1 )()( a Hình 6-3 Mô tҧ thuұt toán AdaBoost.MH phân loҥi nhӏ phân Ban ÿҫu các trӑng sӕ 1D là nhѭ nhau, nhѭng thuұt toán boost cұp nhұt trӑng sӕӣ mӛi lҫn t theo hàm mNJ, luұt yӃu th ÿѭӧc chӑn sao cho giá trӏ ( ) ( )( )t 1 exp - ( ) m t t i t i i Z D i y h xa = = å ÿҥt cӵc tiӇu. Giӟi hҥn lӛi huҩn luyӋn sai : Ĉһt 1 ( ) ( ) T t t t f x h xa = = å , thӃ thì H(x)=sign(f(x)), ÿһt [ ] 1pé ù =ë û nӃu p ÿúng, ngѭӧc lҥi [ ] 0pé ù =ë û 69 Theo (Schapire &Singer 1998)[12] , giӟi hҥn lӛi huҩn luyӋn sai cӫa hàm H là : T t t=1 1 |{ : ( )}| Zi ii H x ym ¹ £ Õ Thұt vұy, vì 1 1D m = , bҵng qui nҥp theo t ta có : ( )tt 1 exp ( ) ( ) i it t tt y h x D i m Z a + - = å Õ iexp(-y ( ))i tt f x m Z = Õ (1) 1Ӄu ( )i iH x y¹ (có lӛi xҧy ra ) thì [ ]( ) 1i iH x yé ù¹ =ë û và ( ) 0i iy f x £ nên iexp(-y ( )) 1if x ³ 1Ӄu ( )i iH x y= thì [ ]( ) 0i iH x yé ù¹ =ë û Nhѭ vұy luôn có ÿѭӧc : [ ] i( ) exp(-y ( ))i i iH x y f xé ù¹ £ë û (2) .Ӄt hӧp (1) và (2), ta có giӟi hҥn trên cӫa lӛi sai : [ ] i 1 1 1: ( ) exp(-y ( ))i i i i i H x y f x m m = é ù¹ £ë û å 1( )t T i t Z D i+ æ ö = ç ÷ è ø å Õ t t Z= Õ +Ӌ quҧ quan trӑng cӫa công thӭc trên là : thay vì phҧi cӵc tiӇu lӛi huҩn luyӋn, ta chӍ cҫn cӵc tiӇu giӟi hҥn trên tZ trong mӛi lҫn thӵc hiӋn boost, ta có thӇ áp dөng giӟi hҥn này phөc vө cho viӋc chӑn giá trӏ ta và chӑn luұt yӃu th ӣ mӛi bѭӟc chҥy t 70 6.3.2 Phѭѫng pháp lӵa chӑn luұt yӃu : Ӣ mӛi bѭӟc chҥy t, luұt yӃu ÿѭӧc lӵa chӑn sao cho lӛi sai ÿѭӧc cӵc tiӇu, dӵa vào giӟi hҥn trên cӫa lӛi sai, thay vì chӑn th sao cho lӛi huҩnluyӋn là nhӓ nhҩt, ta chӑn th sao cho tZ là nhӓ nhҩt Vӟi mӛi tӯ w,ÿӏnh nghƭa w Î x tѭѫng ÿѭѫng vӟi w có trong văn bҧn x.Ĉӏnh nghƭa luұt yӃu h nhѭ sau: ( )h x = 0c nӃu w xÏ và ( )h x = 1c nӃu w xÎ Theo (Schapire &Singer )[14], có ba phѭѫng pháp lӵa chӑn luұt yӃu vӟi thuұt toán AdaBoost MH nhѭ sau: 6.3.2.1 AdaBoost.MH with discrete predictions : Vӟi cách thӵc hiӋn này , { }( )0,1jc j Î sӁ có giá trӏ +1 hoһc -1, vӟi mӝt luұt w ta có thӇ cӵc tiӇu giá trӏ tZ bҵng cách sau : Ĉһt { }0 :X x w x= Ï và { }1 :X x w x= Î Vӟi giá trӏ phân phӕi hiӋn tҥi là tD , ta có nhӳng giá trӏ tѭѫng ӭng vӟi mӛi { }0,1j Î và vӟi mӛi { }1, 1bÎ - + nhѭ sau: 1 ( ) m j b t i j i i W D i x X y b = é ùé ù= Î Ù =ë ûë ûå Nhѭ vұy jbW là trӑng sӕ, ӭng vӟi phân phӕi tD cӫa mүu huҩn luyӋn trong tұp { }( )0,1jX j Î thuӝc vӅ loҥi { }( )1, 1b b Î - + . ThiӃt lұp ( )j jjc sign W W+ -= - Ĉһt { }0,1 | |j jt j r W W+ - Î = -å (Schapire &Singer, 1998 )[12] chӍ ra rҵng ÿӇ cӵc tiӇu giá trӏ tZ , ta chӑn 11 ln 2 1 t t t r r a æ ö+ = ç ÷-è ø 71 Dүn ÿӃn 21tZ r= - 6.3.2.2 AdaBoost.MH with real -value predictions: Khác vӟi thuұt toán AdaBoost vӯa trình bày, ӣÿây { }( )0,1jc j Î có giá trӏ thӵc chӭ không nhѭ phѭѫng pháp vӯa nói là { }( )0,1jc j Î có giá tri là +1 hoһc -1. ĈӇ cӵc tiӇu giá trӏ tZ , giá trӏ { }( )0,1jc j Î vӟi mӛi luұt ÿѭӧc tính nhѭ sau: Theo (Schapire &Singer,1998) [12], tZ ÿҥt giá trӏ cӵc tiӇu nӃu chӑn 1 ln 2 j j j Wc W + - æ ö = ç ÷ è ø ThiӃt lұp 1ta = , suy ra { }0,1 2 j jt j W W+ - Î Z = å Nhѭ vұy, luұt yӃu th ÿѭӧc chӑn sao cho giá trӏ tZ = { }0,1 2 j j j W W+ - Î å là nhӓ nhҩt, còn ta trong trѭӡng hӧp này là 1 Tuy nhiên, các giá trӏ jW+ , jW- có thӇ rҩt nhӓ hay bҵng 0,ÿiӅu này sӁ dүn ÿӃn các giá trӏ { }( )0,1jc j Î có giá trӏ rҩt lӟn hay vô hҥn.Trong thӵc tӃ nhӳng giá trӏ này có thӇ gây ra các vҩn ÿӅ phӭc tҥp trong tính toán, gây tràn sӕ. Theo (Schapire &Singer)[14]ÿӇ giӟi hҥn các giá trӏ { }( )0,1jc j Î không quá lӟn, { }( )0,1jc j Î sӁÿѭӧc tính nhѭ sau : 1 ln 2 j j j Wc W e e + - æ ö+ = ç ÷+è ø Vӟi 1 m e = 72 6.3.2.3 AdaBoost.MH with real -value predictions and abstainings Thuұt toán AdaBoost vӟi giá trӏ dӵÿoán thӵc (AdaBoost.MH with real -value predictions) gán mӝt giá trӏ biӇu thӏÿӝ tin cұy trong cҧ hai trѭӡng hӧp luұt xuҩt hiӋn hay không. Nhѭ vұy nó ngҫm cho rҵng mӝt luұt không thoҧ trong văn bҧn cNJng chӭa ÿӵng thông tin vӅ loҥi cӫa văn bҧn ÿó.Ta có thӇ loҥi bӓ giҧ thiӃt này và ép luұt yӃu không nhұn giá trӏ gì khi luұt không thoҧ văn bҧn.ĈiӅu này ÿѭӧc thӵc hiӋn mӝt cách ÿѫn giҧn chӍ bҵng cách gán cho mӛi luұt yӃu giá trӏÿӝ tin cұy là 0 nӃu không thoҧ văn bҧn. Vӟi mӝt luұt h, thuұt toán sӁ cho giá trӏ dӵÿoán 1c vӟi nhӳng văn bҧn (ӣÿây là email ) thoҧ luұt h, vӟi các văn bҧn còn lҥi, giá trӏ dӵÿoán 0c sӁ có giá trӏ là 0.Do ÿó, luұt h sӁ không có tác dөng gì ÿӃn viӋc phân loҥi nӃu văn bҧn không thӓa. ThiӃt lұp 1ta = Xem 0 0 , ( ) i t i x X W D i Î = å là trӑng sӕ cӫa tҩt cҧ các văn bҧn không thoҧ h Theo (Schapire &Singer, 1998 )[12].thì { } 0 0,1 2 j jt j Z W W W+ - Î = + å Nhѭ vұy ӣ mӛi bѭӟc chҥy t, luұt yӃu ÿѭӧc chӑn sao cho { } 0 0,1 2 j jt j Z W W W+ - Î = + å nhӓ nhҩt Mӝt ѭu ÿiӇm cӫa phѭѫng pháp này so vӟi cách thӵc hiӋn trѭӟc là cҧi thiӋn tӕc ÿӝ thӵc hiӋn, thӵc tӃ tӕc ÿӝ thӵc hiӋn cӫa phѭѫng pháp này nhanh hѫn 15% so vӟi phѭѫng pháp thӵc hiӋn theo thuұt toán. AdaBoost.MH with real -value predictions. 73 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 74 7.1 Cài ÿһt bӝ phân loҥi email dӵa trên phѭѫng pháp AdaBoost: Chúng tôi tiӃn hành cài ÿһt bӝ phân loҥi email dӵa trên thuұt toán AdaBoost vӟi ba cách Ø Cách 1 : cài ÿһt theo thuұt toán AdaBoost MH With Discrete Value Prediction Ø Cách 2: cài ÿһt theo thuұt toán AdaBoost MH With Real Value Prediction Sau khi thӵc hiӋn, chúng tôi lѭu lҥi T luұt ÿã ÿѭӧc chӑn ÿӇ phân loҥi cho các mүu mӟi Chúng tôi xây dӵng mӝt cҩu trúc dӳ liӋu luұt nhѭ sau : Struct rule { Token :chuӛi //lѭu token 0c :sӕ thӵc //giá trӏ cӫa luұt khi token không có trong //email ÿѭӑc xét 1c :sӕ thӵc // giá trӏ cӫa luұt khi token có trong email //ÿѭӑc xét } 7.1.1 Tұp huҩn luyӋn mүu và tұp nhãn : Tұp huҩn luyӋn mүu chính là các email spam và email non-spam ÿѭӧc dung ÿӇ huҩn luyӋn, tұp nhãn là Y={-1,+1}, ӣÿây chúng tôi qui ÿӏnh -1 là spam và +1 là non-spam 75 7.1.2 Xây dӵng tұp luұt yӃu ban ÿҫu : Vӟi mӛi token8 w , ÿӏnh nghƭa w Î x tѭѫng ÿѭѫng vӟi w có trong email x.Ĉӏnh nghƭa luұt yӃu h nhѭ sau: ( )h x = 0c nӃu w xÏ và 1( )h x c= nӃu w xÎ Chúng tôi tiӃn hành cài ÿһt thӱ nghiӋm thuұt toán AdaBoost vӟi hai cách khác nhau, do ÿó tѭѫng ӭng vӟi mӛi cách, cách lҩy giá trӏ 0c và 1c khác nhau, các giá trӏ 0c , 1c mà h(x) có thӇ nhұn ÿѭӧc tính nhѭÿã nói ӣ các mөc 6.3.2.1 và mөc 6.3.2.2. Sӕ lѭӧng cӫa tұp luұt yӃu ÿѭӧc dùng ÿӇ huҩn luyӋn theo nguyên tҳc là không hҥn chӃ, nhѭ vұy chúng ta có thӇ lҩy tҩt cҧ các token trong tұp hӑc. Tuy nhiên, chúng tôi nhұn thҩy ÿӇ lҩy hӃt tҩt cҧ các token thì rҩt mҩt thӡi gian và tӕc ÿӝ huҩn luyӋn cNJng chұm ÿi, vì thӃ chúng tôi chӍ chӑn ra mӝt sӕ các token thoҧ mãn mӝt tiêu chí nào ÿó ÿӇ xây dӵng luұt yӃu. Mӛi luұt yӃu ÿѭӧc chӑn nhѭ sau :chúng tôi duyӋt qua tҩt cҧ các mүu hӑc, tính sӕ lҫn xuҩt hiӋn cӫa mӛi token, nhӳng token có sӕ lҫn xuҩt hiӋn lӟn hѫn mӝt giá trӏ ngѭӥng nào ÿó (ÿѭӧc qui ÿӏnh ) sӁÿѭӧc lӵa chӑn, viӋc lӵa chӑn ngѭӥng ÿӇ quyӃt ÿӏnh luұt có ÿѭӧc chӑn hay không tuǤ thuӝc vào kho ngӳ liӋu hӑc. Chúng tôi chia thành hai tұp riêng, mӝt tұp gӗm các token xuҩt hiӋn trong các email spam, tұp kia gӗm các token xuҩt hiӋn trong email non-spam.Cách xây dӵng tұp luұt yӃu nhѭ vұy làm giҧm ÿáng kӇ sӕ luұt cҫn xét Khi huҩn luyӋn, chúng tôi sӁ quyӃt ÿӏnh sӕ lѭӧng các luұt yӃu cҫn chӑn, khi ÿó chúng tôi sӁ chӑn tұp luұt yӃu bҵng cách lҫn lѭӧt chӑn mӝt token chѭa có trong tұp ÿѭӧc chӑn tӯ tұp các token spam, rӗi lҥi chӑn mӝt token chѭa có trong tұp ÿѭӧc chӑn tӯ tұp các token non-spam cho ÿӃn khi ÿӫ sӕ Oѭӧng yêu cҫu ĈӇ thӵc hiӋn viӋc duyӋt các token và tìm kiӃm mӝt token vӟi tӕc ÿӝ nhanh, tѭѫng tӵ nhѭ thӵc hiӋn thuұt toán huҩn luyӋn Naïve Bayesian chúng tôi 8 Xem ÿӏnh nghƭa token ӣ mөc 5.1.1 76 cNJng xây dӵng bҧng băm tѭѫng tӵ nhѭ bҧng băm ÿã ÿѭӧc sӱ dөng ӣ cách thӵc hiӋn theo phѭѫng pháp Naïve Bayesian. 7.1.3 Thӫ tөc WeakLearner chӑn luұt yӃu: Thӫ tөc WeakLearner ÿѭӧc xây dӵng nhҵm tìm luұt yӃu th nhѭ sau : chӑn luұt yӃu th ӣ bѭӟc chҥy t sao cho tZ nhӓ nhҩt, cách chӑn tZ và ta ÿã ÿѭӧc ÿӅ cұp ӣ các mөc 6.3.2.1 và 6.3.2.2 7.1.4 Phân loҥi email : Khi nhұn ÿѭӧc mӝt email x, chúng tôi sӁ tiӃn hành so khӟp các luұt tӯ kho ngӳ liӋu các luұt ÿѭӧc chӑn sau quá trình huҩn luyӋn , tӯÿó tính giá trӏ f(x), nӃu f(x) >0 (cùng dҩu vӟi +1 ) chúng tôi cho email ÿó là non-spam, ngѭӧc lҥi (cùng dҩu vӟi -1 ) chúng tôi cho email ÿó là spam. 7.2 Thӱ nghiӋm hiӋu quҧ phân loҥi : 7.2.1 Thӱ nghiӋm vӟi kho ngӳ liӋu pu: 7.2.1.1 Kӏch bҧn kiӇm thӱ: Vói mӛi phiên bҧn AdaBoost ÿã cài ÿһt, chúng tôi chӑn tұp luұt yӃu vӟi sӕ lѭӧng là 2500 luұt, nhӳng luұt ÿѭӧc xem là ӭng cӱ viên nӃu sӕ lҫn xuҩt hiӋn cӫa token lӟn hѫn hay bҵng 10 lҫn. NӃu sӕ luұt yӃu ban ÿҫu không ÿӫ 2500, chúng tôi sӁ lҩy tҩt cҧ sӕ sҹn có.Chúng tôi thӱ nghiӋm vӟi T lҫn lѭӧt là 5, 10, 50, 100, 200 và 500. Chúng tôi lҫn lѭӧt kiӇm thӱ vӟi các pu, vӟi mӛi pu, chúng tôi cho hӑc tӯ part 1-ÿӃn part 9.Ĉӕi vӟi viӋc kiӇm thӱ chúng tôi kiӇm thӱ trên kho ngӳ liӋu chѭa ÿѭӧc huҩn luyӋn là part 10 cӫa mӛi pu 7.2.1.2 KӃt quҧ kiӇm thӱ: Chúng tôi trình bày kӃt quҧ kiӇm thӱ vӟi T=500, vӅ chi tiӃt kӃt quҧ kiӇm thӱ, xem phҫn phө lөc 77 v KӃt quҧ thӵc hiӋn kiӇm thӱ vӟi thuұt toán ADaBoost with real value predictions Ngӳ liӋu6ӕ email hӑc Sӕ email kiӇm thӱS->SS->NN->NN->SSR SP SpamNon-spamSpam Non-spam PU1 432 549 48 61 48 0 58 3100.00% 94.12% 432 549 432 0 549 0100.00%100.00% PU2 126 513 14 57 12 2 56 1 85.71% 92.31% 126 513 126 0 513 0100.00%100.00% PU3 1638 2079 182 231 176 6 216 15 96.70% 92.15% 1638 20791638 0 2079 0100.00%100.00% PUA 513 513 57 57 56 1 38 19 98.25% 74.67% 513 513 513 0 513 0100.00%100.00% %ҧ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 v KӃt quҧ thӵc hiӋn kiӇm thӱ vӟi thuұt toán ADaBoost with discrete predictions Ngӳ liӋu6ӕ email hӑc Sӕ email kiӇm thӱS->SS->NN->NN->SSR SP SpamNon-spamSpam Non-spam PU1 432 549 48 61 46 2 57 4 95.83% 92.00% 432 549 432 0 549 0100.00%100.00% PU2 126 513 14 57 13 1 57 0 92.86%100.00% 126 513 126 0 513 0100.00%100.00% PUA 513 513 57 57 53 4 45 12 92.98% 81.54% 513 513 513 513 513 0 513 0100.00%100.00% PU3 1638 2079 182 231 173 9 216 15 95.05% 92.02% 1638 20791624 14 2074 5 99.15% 99.69% %ҧ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 Nhұn xét : theo Schapire & Singer [14], hiӋu quҧ phân loҥi cӫa thuұt toán AdaBoost with real value predictions cao hѫn cӫa thuұt toán AdaBoost with discrete predictions, tuy nhiên ӣÿây ta thҩy ÿLӅu ÿó không rõ rӋt. HiӋu quҧ phân loҥi cӫa cҧ hai thuұt toán trên các kho ngӳ liӋu là khá cao. Vӟi thuұt toán AdaBoost, lӛi phân loҥi sai trên các kho ngӳ liӋu ÿã huҩn luyӋn sӁ ngày càng giҧm khi T ngày càng tăng, tѭѫng ӭng vói các chӍ sӕ 78 spam recall và spam precision ngày càng tăng, dѭӟi ÿây là biӇu ÿӗ thӇ hiӋn ÿiӅu ÿó 0.00% 20.00% 40.00% 60.00% 80.00% 100.00% 120.00% 1 33 65 97 129 161 193 225 257 289 321 353 385 417 449 481 T % SR SP Hình 7-1 Ĉӗ thӏ biӇu diӉn sӵ biӃn thiên cӫa spam recall (SR) và spam precision (SP) theo T (thuұt tóan AdaBoost.MH with discrete predictions) 0.00% 20.00% 40.00% 60.00% 80.00% 100.00% 120.00% 1 31 61 91 121 151 181 211 241 271 301 331 361 391 421 451 481 T % SR SP Hình 7-2 Ĉӗ thӏ biӇu diӉn sӵ biӃn thiên cӫa spam recall (SR) và spam precision (SP) theo T (thuұt tóan AdaBoost MH with real value predictions ) 79 7.2.2 Thӱ nghiӋm vӟi kho ngӳ liӋu email chӳ: 7.2.2.1 Kӏch bҧn kiӇm thӱ: Chúng tôi thӱ nghiӋm hai thuұt toán AdaBoost ÿã cài ÿһt vӟi T ÿѭӧc chӑn lҫn lѭӧt là 5, 10, 50, 100, 200, và 500. 7.2.2.2 KӃt quҧ kiӇm thӱ: Ngӳ liӋu email văn bҧn trѫn, sӕ email kiӇm thӱ : Spam =98, non- spam=100 Ngӳ liӋu email html, sӕ email kiӇm thӱ :Spam =50, non-spam=50 v KӃt quҧ thӵc hiӋn kiӇm thӱ vӟi thuұt toán ADaBoost with real value predictions Ngӳ liӋu T=5 T=10 T=50 T=100 T=200 T=500 HTML SàS 48 48 49 49 49 49 SàN 2 2 1 1 1 1 NàN 49 49 49 49 49 49 NàS 1 1 1 1 1 1 SR 96.00% 96.00% 98.00% 98.00% 98.00% 98.00% SP 97.96% 97.96% 98.00% 98.00% 98.00% 98.00% TEXT SàS 84 93 98 98 98 98 SàN 14 5 0 0 0 0 NàN 98 97 98 99 99 99 NàS 2 3 2 1 1 1 SR 85.71% 94.90% 100.00% 100.00% 100.00% 100.00% SP 97.67% 96.88% 98.00% 98.99% 98.99% 98.99% %ҧ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 v KӃt quҧ thӵc hiӋn kiӇm thӱ vӟi thuұt toán ADaBoost with discrete predictions Ngӳ liӋu T=5 T=10 T=50 T=100 T=200 T=500 HTML SàS 48 49 50 50 50 50 SàN 2 1 0 0 0 0 NàN 49 49 49 49 49 49 NàS 1 1 1 1 1 1 SR 96.00% 98.00% 100.00% 100.00% 100.00% 100.00% SP 97.96% 98.00% 98.04% 98.04% 98.04% 98.04% 80 TEXT SàS 91 91 95 97 96 97 SàN 7 7 3 1 2 1 NàN 98 98 98 98 99 99 NàS 2 2 2 2 1 1 SR 92.86% 92.86% 96.94% 98.98% 97.96% 98.98% SP 97.85% 97.85% 97.94% 97.98% 98.97% 98.98% %ҧ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 Nhұn xét : hiӋu quҧ phân loҥi trên ngӳ liӋu email là chӳ cӫa thuұt toán AdaBoost khá tӕt, so vӟi phѭѫng pháp phân loҥi Naïve Bayesian thì ADaBoost phân loҥi email html tӕt hѫn, hiӋu quҧ phân loҥi trên email là Yăn bҧn trѫn cNJng tѭѫng ÿѭѫng vӟi Naïve Bayesian. 7.3 Ѭu ± nhѭӧc ÿLӇm cӫa phѭѫng pháp phân loҥi AdaBoost: 7.3.1 Ѭu ÿLӇm : · Mӝt ѭu ÿiӇm cӫa AdaBoost giӕng vӟi phѭѫng pháp phân loҥi Naïve Bayes là nó cho phép hӑc cұp nhұt, nghƭa là khi mӝt email spam vѭӧt qua ÿѭӧc bӝ lӑc thì ngѭòi dung có thӇÿánh dҩu email ÿó là spam và huҩn luyӋn lҥi bӝ lӑc · HiӋu quҧ phân loҥi là khá cao · ViӋc lѭu trӳ tұp luұt ÿã qua huҩn luyӋn khá gӑn nhҽ, trong khi ÿó vӟi phѭѫng pháp phân loҥi Naïve Bayes thì dӳ liӋu sau khi hӑc là khá lӟn n. Vӟi phѭѫng pháp phân loҥi Naïve Bayesian, dӳ liӋu huҩn luyӋn sӁ phình to sau mӛi lҫn huҩn luyӋn cұp nhұt thêm, ÿiӅu này vӟi cách thӵc hiӋn theo phѭѫng pháp AdaBoost là không ÿáng kӇ. 7.3.2 KhuyӃt ÿLӇm : · CNJng giӕng nhѭ các phѭѫng pháp máy hӑc cӫa phѭѫng pháp phân loҥi dӵa trên thuұt toán AdaBoost chính là viӋc phҧi huҩn luyӋn cho nó, viӋc huҩn luyӋn hiӋu quҧ hay không còn phҧi phө thuӝc vào kho ngӳ liӋu huҩn luyӋn ban ÿҫu 81 · KhuyӃt ÿLӇm thӭ hai là thӡi gian huҩn luyӋn, so vӟi Naïve Bayesian,ÿӇ huҩn luyӋn cùng mӝt kho ngӳ liӋu thì phѭѫng pháp AdaBoost cҫn thӡi gian lâu hѫn rҩt nhiӅu, theo chúng tôi nhұn thҩy thì sӵ chênh lӋch ҩy khá lӟn. 82 Chѭѫng 8 : XÂY DӴNG CHѬѪNG TRÌNH MAIL CLIENT TIӂNG VIӊT HӚ TRӦ PHÂN LOҤI EMAIL 83 8.1 Chӭc năng: Chúng tôi xây dӵng phҫn mӅm Mail Client vӟi các chӭc năng chính nhѭ sau: Ø Chӭc năng gӣi nhұn email Ø Luѭ trӳ email tѭѫng ӭng vӟi tӯng mөc Ø Soҥn email Ø Xây dӵng sәÿӏa chӍ Ø Lӑc email spam Ø Quҧn lý email nhѭ sao chép, chuyӃn, xóa … email Ø Và mӝt sӕ công cө hӛ trӧ khác khác : … ĈӇ hӛ trӧ cho viӋc kiӇm thӱ Mail Client chúng tôi xây dӵng chѭѫng trình Flood Mail gӣi mail hàng loҥt ÿӃn mӝt ÿӏa chӍ nhұn nào ÿó. 8.2 Xây dӵng bӝ lӑc email spam : Chúng tôi sӱ dөng bӝ lӑc dӵa trên thuұt toán hӑc Naïve Bayes và AdaBoost, vӟi Naivê Bayes chúng tôi sӱ dөng cách cài ÿһt theo cách tính xác suҩt spam cho mӛi token dӵa trên sӕ lҫn xuҩt hiӋn trong tұp huҩn luyӋn ban ÿҫu, chӑn sӕ token ÿӇ duyӋt mӝt email là 15, chӑn 9l = do ÿó ngѭõng phân loҥi email spam là t=0.9. Vӟi bӝ lӑc dӵa trên AdaBoost chúng tôi chӑn cách cài ÿһt theo AdaBoost.MH with real value predictions. Chúng tôi xây dӵng thành các component tích hӧp vào chѭѫng trình dѭӟi dҥng các dll. Chúng tôi cNJng xây dӵng chӭc năng lӑc email theo phѭѫng pháp BlackList và luұ do ngѭӡi dùng tӵÿӏnh nghƭa, phѭѫng pháp này sӁ hӛ trӧ cho bӝ lӑc email ngăn chһn email spam. 84 8.3 Tә chӭc dӳ liӋu cho chѭѫng trình : Dӳ liӋu chѭѫng trình :gӗm nӝi dung các email, các luұt do ngѭӡi dùng thiӃt lұp. /ѭu trӳ nӝi dung các email gӣi và nhұn : ÿѭӧc lѭu dѭӟi dҥng các tұp tin văn bҧn, vӟi mӛi thѭ mөc tѭѫng ӭng nhѭ hӝp thѭÿӃn, hӝp thѭÿi,.. sӁ có mӝt tұp tin lѭu nӝi dung các email trong các thu