（計算機應用技術專業(yè)論文）垃圾郵件過濾算法研究及系統(tǒng)實現(xiàn).pdf

碩士論文垃圾郵件過濾算法研究及系統(tǒng)實現(xiàn) 摘要 電子郵件自發(fā)明以來，已經(jīng)成為人們生活中不可缺少的通訊方式。人們在享受電子 郵件帶來的方便和速度的同時也遭受著垃圾郵件、釣魚攻擊以及其它一些網(wǎng)絡詐騙行為 的危害。據(jù)2 0 0 7 年c o m m t o u c h 發(fā)布的電子郵件威脅趨勢報告顯示，全球9 5 的郵件是 垃圾郵件。垃圾郵件給互聯(lián)網(wǎng)及廣大用戶帶來了很大負面影響，它不僅占用系統(tǒng)資源， 浪費用戶時間，同時也帶來安全隱患，更給國民經(jīng)濟造成了巨大損失，已經(jīng)成為一個全 球性的問題。 面對垃圾郵件的迅速增長而帶來的巨大危害，很多國家紛紛采取抵制措施，希望通 過立法手段還網(wǎng)民以寧靜的空間。同時，人們也積極從技術上展開反垃圾郵件的研究， 從垃圾郵件產(chǎn)生的源頭、傳播途徑，到最后的接收者等各個方面，提出了一些行之有效 的垃圾郵件防范體系和垃圾郵件過濾方法。 本文概述了當前反垃圾郵件的主要技術手段，并且從機器學習的角度研究垃圾郵件 過濾算法，將垃圾郵件過濾問題納入到機器學習框架當中。 垃圾郵件的過濾問題本質(zhì)上是一個分類問題，并且是一個分成兩類的分類問題。過 濾垃圾郵件，即判斷郵件是否是垃圾郵件。若為垃圾郵件，則采取相應措施進行過濾， 否則為正常郵件，不作處理。因此，機器學習中的很多算法都可以用到垃圾郵件過濾當 中去。 本文重點研究了在垃圾郵件過濾中廣泛應用的四種算法：貝葉斯算法，w i n n o w ， a d a b o o s t 和支持向量機。通過大量對比實驗，本文詳細分析了上述四種算法對于樣本的 敏感性和適用的范圍。 此外，本文還實現(xiàn)了一種基于客戶端的垃圾郵件過濾系統(tǒng)。此系統(tǒng)集成了上述四種 過濾算法，通過插件方式，嵌入到郵件客戶端o u t l o o k 當中。當新郵件當來時，可以自 動對進行垃圾郵件過濾。 關鍵詞：垃圾郵件過濾，貝葉斯，w i n n o w ，a d a b o o g ，支持向量機，郵件過濾插件， o u t l o o k a b s t r a c t e m a i lh a sb e c o m ea ni n d i s p e n s a b l ec o m m u n i c a t i o nw a yi np e o p l e sl i v e ss i n c ei t w a s i n v e n t e d w h i l ee n j o y i n gt h ec o n v e n i e n c ea n ds p e e dt h a ti tb r i n g s ，p e o p l ea l s os u f f e rf r o m s p a i r s ，f i s h i n ga t t a c ka n do t h e r n e t w o r kf r a u d s t h e2 0 0 7e m a i lt h r e a tt r e n dr e p o r tp u b l i s h e d b vc o n m 吐o u c hs h o w e dt h a t9 5p e r c e n to fe m a i l sa r es p a m s s p a m sh a v el a r g en e g a t i v e i m p a c to nt h ei n t e r n e ta n d i t su s e r s t h e yt a k eu pal o to fs y s t e mr e s o u r c e s ，w a s t eu s e r s t i m e ， a n db r i n gp o t e n t i a ls e c u r ep r o b l e m s e v e nm o r e ，i tc a u s e st r e m e n d o u sl o s s e st ot h en a t i o n a l e c o n o m y t h es p a mp r o b l e mh a sb e c o m e ag l o b a lp r o b l e m w i t ht h ef a s ti n c r e a m e n to ft h es p a m s ，t h es p a r ep r o b l e mh a sb e c o m em o r ea n dm o r e s e r i o u s f a c i n 【gt ot h i sp r o b l e m ，m a n yc o u n t r i e sh a v e t a k em e a s u r e st of i g h tw i t hi t ，h o p i n gt o g i v eb a c kt oaq u i e ts p a c e t on e t i z e n st h r o u g hl e g i s l a t i v em e a n s b e s i d e s ，p e o p l ea l s od os o m e p o s i t i v er e s e a r c ho na n t i s p a mf r o mt h et e c h i n i c a la s p e c t f r o mt h es p a mp r o d u c i n ga n d 缸a n s i i l i s s i o np h a s et ot h ef m a lr e c e i v e rp h a s e ，al o to fe f f e c t i v es p a r ed e f e n d ss y s t e m sa n d s p a r ef i l t e r i n gm e t h o d sa r ep r o p o s e d t h i sp a p e ro u t l i n e dt h em a i n s t r e a ma n t i - s p a mt e c h n o l o g i e s ，a n ds t u d i e ds p a r ef i l t e r i n g a l g o r i t h m sf r o mt h em a c h i n el e a r n i n ga s p e c t , p u t t i n g t h es p a mf i l t e r i n gp r o b l e mi n t ot h e m a c h i n el e a n i n gf r a m e w o r k e s s e n t i a l l y , s p a r ef i l t e r i n gp r o b l e mi s ac l a s s i f i c a t i o np r o b l e m ，a n di ti sat w o c l a s s p r o b l e m f i l t e r i n ga l le m a i li sb a s i c a l l yj u d g i n gw h e t h e ra ne m a i li s ap a mo rn o t i fi ti sa s p 鋤n ，t h e nt a k et h ec o r r e s p o n d i n gm e a s u r e s t of i l t e ri t o t h e r w i s ei ti sal e g i t i m a t ee m a i l ，a n d n o tt op r o c e s si t t h e r e f o r e ，m a n ya l g o r i t h m si nm a c h i n el e a r n i n gd o m a i nc a n b eu s e dt of i l t e r e m a i l s t h i sp a p e rf o c u s e do nf o u ra l g o r i t h m st h a tw i d e l yu s e di ns p a mf i l t e r i n g ：b a y e s i a n a l g o r i t h m ，w i n n o wa l g o r i t h m ，a d a b o o s t a l g o r i t h m a n ds v ma l g o r i t h m t h r o u g h c o m p r e h e n s i v ec o m p a r a t i o ne x p e r i m e n t s ，t h ep a p e ra n a l y z e d t h ea b o v ef o u ra l g o r i t h m s d e t 2 l i l e d l vi i lt h ei n f l u e n c eo ft h ed i f f e r e n ts a m p l e sa n d t h es c o p eo ft h e ka p p l i c a t i o n i na d d i t i o n t h ep a p e ri m p l e m e n t e das p a mf i l t e r i n gs y s t e mw h i c hi sb a s e do nt h ee m a i l c l i e n t t h es y s t e mw h i c hh a si n t e g r a t e dt h ea b o v ef o u ra l g o r i t h m si se m b e d d e di no u t l o o k i n t h ep l u g i nw a y w h e nan e we m a i lc o m e s ，i tc a n f i l t e ri ta u t o m a t i c a l l y k e yw o r d ：s p a mf i l t e r i n g ，b a y e s ，w i n n o w , a d a b o o s t ，s v m ，a n t i s p a r e a d di n , o u t l o o k 聲明 本學位論文是我在導師的指導下取得的研究成果，盡我所知，在 本學位論文中，除- r ) j n 以標注和致謝的部分外，不包含其他人已經(jīng)發(fā) 表或公布過的研究成果，也不包含我為獲得任何教育機構(gòu)的學位或?qū)W 歷而使用過的材料。與我一同工作的同事對本學位論文做出的貢獻均 已在論文中作了明確的說明。 研究生簽名：趣 刪年否胃鑼 學位論文使用授權聲明 南京理工大學有權保存本學位論文的電子和紙質(zhì)文檔，可以借閱 或上網(wǎng)公布本學位論文的部分或全部內(nèi)容，可以向有關部門或機構(gòu)送 交并授權其保存、借閱或上網(wǎng)公布本學位論文的部分或全部內(nèi)容。對 于保密論文，按保密的有關規(guī)定和程序處理。 研究生簽名：凌整2 加咯年伽溺 碩士論文 垃圾郵件過濾算法研究及系統(tǒng)實現(xiàn) 1 緒論 1 1 垃圾郵件介紹 1 1 1 垃圾郵件概念 垃圾郵件( s p a r em a i l ) 又稱為u b z ( u n s o l i c i t e db u l ke m a i l ) ，主要指的是未經(jīng)接收者同 意而大量散發(fā)的電子郵件【1 1 。根據(jù)中國互聯(lián)網(wǎng)協(xié)會反垃圾郵件規(guī)范以及中國反垃圾 郵件狀況調(diào)查報告中的定義，具有以下特征的電子郵件可被視為是垃圾郵件 2 1 ： ( 一) 收件人事先沒有提出要求或者同意接收的廣告、電子刊物、各種形式的宣傳品 等宣傳性的電子郵件。 ( 二) 收件人無法拒收的電子郵件。 ( 三) 隱藏發(fā)件人身份、地址、標題等信息的電子郵件。 ( 四) 含有虛假的信息源、發(fā)件人、路由等信息的電子郵件。 ( 五) 含有病毒、惡意代碼、色情、反動等不良信息或有害信息的郵件。 1 1 2 垃圾郵件危害 互聯(lián)網(wǎng)上充斥著的各種形式的垃圾郵件不僅給個人帶來很多不必要的麻煩，更帶來 很多社會問題，造成嚴重危害。主要表現(xiàn)在1 2 - 9 1 ： ( 1 ) 對郵件服務商的影響 據(jù)調(diào)查顯示，根據(jù)規(guī)模不同，2 0 0 3 年郵件服務商每天收到的垃圾郵件從1 5 萬封到 3 8 0 0 萬封不等，而這些垃圾郵件占總郵件的比例都近乎在8 0 以上。各運營商為了應 對垃圾郵件，都投入了大量的人力物力進行反垃圾郵件工作，每年在反垃圾郵件上都會 有上百萬元甚至上千萬元的投入。 垃圾郵件除了給郵件運營商造成了重大經(jīng)濟損失外，還在其它方面也帶來重大影 響，主要表現(xiàn)在： ( a ) 人力成本增加； ( b ) 硬件的投資，存儲資源的浪費； ( c ) 影響客戶的滿意度，用戶投訴事件增多； ( d ) 影響郵箱品牌形象：部分垃圾郵件發(fā)送者頻繁更換i p ，冒充正規(guī)i s p 發(fā)送大量 垃圾郵件，給被冒充的i s p 的聲譽帶來非常惡劣的影響，導致整個網(wǎng)段被國際r b l 、s b l 封殺，嚴重影響廣大正常郵件用戶使用。 ( 2 ) 對郵箱用戶的影響 垃圾郵件嚴重損害了郵箱用戶的利益，給其生活帶來很大的麻煩。每天處理大量垃 圾郵箱浪費時間、精力和金錢( 如圖1 1 1 ，1 1 2 所示) 。同時，垃圾郵件傳播非法信息， 1 論文 助長不法交易，誤導消費者，導毀很多消費者上當受騙。里有甚者，使得用戶丟失重要 信息。由于垃圾郵件的泛濫，部分用戶甚至對電子郵件失去信心。 圖l1 】2 0 0 6 和2 0 0 7 年用戶收到正常郵件與垃圾郵件對比 ( 囤中可看出每天用戶收到的垃圾郵件要比正常郵件多) 圖lt22 0 0 7 年用戶每天處理垃圾郵件時間 f 從圈中可以看出，特別到第四季度用戶處理垃圾郵件的時間不斷上升1 舊) 對互聯(lián)網(wǎng)環(huán)境的影響 大量“病毒”型的垃圾郵件具有很強的攻擊性和破壞性，嚴重威脅信息安全，給網(wǎng) 民帶來了許多無法解決的麻煩，遭到網(wǎng)民的痛恨和反感?！吧椤⒈┝Α毙偷睦]件 也會給人們的精神思想造成不良的影響。少數(shù)別有用心者利用垃圾郵件大量散播各種虛 假信息或有害信息，嚴重危害社會穩(wěn)定。一些黑客利用垃圾郵件作為工具，大量襲擊網(wǎng) 站。造成網(wǎng)絡阻塞，甚至癱瘓，2 0 0 2 年2 月，黑客攻擊雅虎等五大熱門網(wǎng)站就是一個例 子。 碩士論文垃圾郵件過濾算法研究及系統(tǒng)實現(xiàn) 1 2 當前反垃圾郵件狀況 面臨當前垃圾郵件問題的日益嚴重，因此亟需加強反垃圾郵件領域的研究。目前反 垃圾郵件的手段主要法律手段、經(jīng)濟手段、技術手段以及綜合協(xié)作手段。 1 2 1 法律手段 通過制定相關反垃圾郵件法律，可以有效遏制垃圾郵件的傳播。目前，世界各國紛 紛開始立法，對垃圾郵件制造者進行制劃1 1 】。 垃圾郵件最早起源于美國，面臨越來越嚴重的垃圾郵件問題，國會議員敦促政府盡 快通過對垃圾郵件重罰的方法，以保證正常工作貿(mào)易的開展。2 0 0 0 年7 月1 8 日通過反 垃圾郵件法案( 也ea n t i s p a ma c t ) ，2 0 0 3 年通過限制垃圾郵件法) ) ( 2 0 0 3c a n s p a r ea c t ) 。 這些法案對濫發(fā)郵件行為進行了規(guī)范，并在經(jīng)濟上對垃圾郵件制造者進行懲治。 歐盟在1 9 9 8 年制定了歐盟隱私保護指令，于2 0 0 2 年批準了反垃圾郵件及保 護在線隱私權法，并于2 0 0 3 年正式實施了反數(shù)字盜版法，這些法案的實施標志著 歐盟正式進入了全球反垃圾郵件的戰(zhàn)爭。 波蘭政府針對垃圾郵件擬立新法規(guī)，對垃圾郵件制造者予以重罰；新西蘭政府也開 始正式實施新的反垃圾郵件法律，同時政府成立了新的組織機構(gòu)以受理投訴和違法行 為。 我國是目前世界受垃圾郵件危害最大的國家之一，有必要建立全國性的反垃圾郵件 法律?；诖耍袊ヂ?lián)網(wǎng)協(xié)會于2 0 0 3 年2 月2 5 日出臺了中國互聯(lián)網(wǎng)協(xié)會反垃圾郵 件郵件服務標準( 征求意見稿) ，又于2 0 0 4 年9 月3 日出臺了中國互聯(lián)網(wǎng)協(xié)會互聯(lián)網(wǎng) 公共電子郵件服務規(guī)范。2 0 0 6 年3 月3 0 日，互聯(lián)網(wǎng)電子郵件服務管理辦法開始正 式施行，成為全國性的有效預防垃圾郵件的法律規(guī)范。 然而，根據(jù)中國互聯(lián)網(wǎng)協(xié)會反垃圾郵件中心的歷次調(diào)查報告顯示1 2 捌，相當多的用 戶收到后不會對垃圾郵件進行投訴。究其原因，近半用戶不知道哪里去投訴，四分之一 用戶感到投訴過程過于繁瑣( 如圖1 2 1 ，1 2 2 所示) 。這些狀況說明，雖然制定有關法律 可以懲治垃圾郵件制造者和傳播者，但是目前大多數(shù)用戶缺乏這方面的法律意識。增強 用戶的法律意識，完善反垃圾郵件相關法律法規(guī)，并嚴格執(zhí)行，還需要一個長期的過程。 同時，也要加大垃圾郵件投訴方式的宣傳力度，并且也需要提供更多更實用地便于網(wǎng)民 投訴的途徑。 垃圾郵件已成為一個全球性的問題，而全球性問題需要全球性的治理。這就要求國 際社會充：分認識垃圾郵件生態(tài)的復雜性，全面加強交流與合作，建立切實有效的反垃圾 郵件國際合作機制，在編織好法律這張“大網(wǎng)”的同時，還要喚起公眾防范意識，共同 打一場全球持久保衛(wèi)戰(zhàn)，才能逐步掃除垃圾郵件，讓信息高速公路真正快起來。 緒論碩士論文 l 0 00 0 r 9 00 0 一 8 00 0 r 葛 7 00 0 r ， _ _ _ 。； j 霉j 攀 安 莓 ? 蕞 6 00 0 r i 秀r =卜 i f 。 5 00 0 p 4 00 0 卜 i|v 3 00 0 2 00 0 一 1 00 0 f 團_爵了曠匿_ j孽_ 二 uu u _ 0 2 0 0 61 02 0 0 62 02 0 0 63 02 0 0 04 02 0 0 7l q2 0 0 72 q2 0 0 7 2 0 0 74 0 4 00 0 3 0 0 0 2 00 0 1 00 0 圖1212 0 0 6 - 2 0 0 7 用戶對垃圾郵件投訴情況 、1 雪二卜rt爭 口不知道哪里投訴 投訴過程過于繁瑣 圖12 22 0 0 6 2 0 0 7 年用戶不投訴的原因 1 2 2 經(jīng)濟手段 采用經(jīng)濟手段也不失為一種防范垃圾郵件的好方法?，F(xiàn)實生活中，人們寄信時需要 貼郵票?；谶@種想法，電子郵票”1 應運而生。其主要做法是在發(fā)送電子郵件前，電子 郵件發(fā)送者需要支付一點很小的費用( 可以是貨幣形式或其它形式) 作為電子郵票。對于 正常郵件使用者，這筆費用幾乎可以忽略。但對于垃圾郵件制造者來說，巨大的費用足 以讓其對郵件望而卻步。 電子郵票主要可以分為兩種，第一種是貨幣形式的電子郵票：第二種是郵件標簽認 證的電子郵票。 g o o d m a i l 開發(fā)的一種基于貨幣形式的電子郵票系統(tǒng)。其基本思想是在電子郵件的頭 信息中加入一個唯一的加密過的i d ，即電子郵票。當接收者收到郵件后，系統(tǒng)將此i d 解密。根據(jù)該i d ，系統(tǒng)會自動從郵件發(fā)送者帳戶劃去一定的金額作為郵件發(fā)送費用。 碩論女 * 敷自口件過濾算* h 究廈系統(tǒng)實現(xiàn) 與g o o d m a i l 做法不同，c a m r a m 應用了一種郵件標簽認證的系統(tǒng)，該系統(tǒng)針對每一 封被發(fā)送出去的電子郵件附加一個數(shù)學迷題來進行驗證，要求郵件發(fā)送者給出正確解答 后方可發(fā)送郵件。這里數(shù)學謎題即是電子自口票，而解答這些謎題需要花費的時間與計算 代價則是支付電子郵票的費用。這種方法類似于目前在網(wǎng)絡上進行登錄時要求輸入驗證 碼的策略。 電子郵票的想法雖好，但是由于部署這套系統(tǒng)需要多方面的合作?；谪泿判问降?電子郵票中的收費問題還有待于逮一步完善。例如，美國在線表示，將出臺一項計劃對 大規(guī)模電子郵件發(fā)送服務進行收費，希望以此抵制垃圾郵件的散播。然而分析人士表示， 對美國在線這一收費服務的抵制行動能否有效還要取決于美國在線用戶的反應和這一 收費服務的實際效果口】。另外，由于電子郵件系統(tǒng)的廣泛應用，每次發(fā)送都要求解答謎 題對于用戶來說也是一個不小的代價，這種方法的推廣實施也面臨很大困難。 1 2 3 技術手段 技術手段作為企業(yè)和用戶最有效防范垃圾郵件的措旖，在反垃圾郵件過程中發(fā)揮了 重要的作用。據(jù)中國互聯(lián)網(wǎng)協(xié)會反垃圾郵件中心調(diào)查顯示，目前使用最多的技術手段為 黑名單、身份認證、關鍵字過濾、行為識別模式和白名單口劃。這幾種技術以其易用使 用，防范效果明顯，占到應用技術的9 5 以上。如圖123 所示： ( 1 ) 黑名單 如果將已知的垃圾郵件制造者的口地址、i s p 域名或郵箱地址收集起來，形成一個 列表，則可以直接拒收從這些地址發(fā)來的郵件。黑名單技術1 1 2 j i e , 是基于此原理，維護一 個垃圾郵件制造者的地址列表，對在此列表內(nèi)的地址進行郵件限制或過濾。 由于垃圾郵件制造者會不斷更換其使用i p 和域名，手工維護這個“黑名單”代價 巨大。實時黑名單( r e a l t i m e b l a c k h o l e l i s t ，簡稱r b l ) n j 以很好得解決這個問題。它提 供了一個可查詢的i p 地址列衰通過d n s 的查詢方式來查找m 是否被列八了黑名單中。 1 緒論 碩士論文 r b l 一般由r b l 服務提供者維護，使用者只要訂閱該黑名單服務即可。中國反垃圾郵 件聯(lián)盟提供免費的實時黑名單服務，無需申請即可使用。 ( 2 ) 身份認證【1 3 】 對發(fā)送者進行嚴格的身份驗證是防止垃圾郵件的一種有效措施。常見有以下幾種策 略：s p f 、s e n d e r i d 、d o m a i n k e y s 。 s p f ( s e n d e rp o l i c yf r a m e w o r k ) 是美國在線( a o l ) 提出的免費開放標準。它可以防止 發(fā)件人假冒，是一種源頭認證技術。發(fā)郵件時，域通過d n s 發(fā)布反向m x 記錄，告訴 i n t e m e t 哪些計算機可以從該域發(fā)送電子郵件。用戶收到郵件后，通過d n s 查詢郵件來 源是否符合源域的郵件發(fā)送策略，從而判定郵件是否為假冒郵件。 s e n d e ri d 是微軟將c a l l e ri d 與s p f 結(jié)合的產(chǎn)物。它設計用于避免域名欺騙以及網(wǎng) 絡釣魚。s e n d e ri d 包含三個獨立的規(guī)范：s p f 、電子郵件來電顯示以及收件方優(yōu)化。其 工作原理如下：當郵件服務器收到一個電子郵件時，域名系統(tǒng)( d n s ) 保存域名的s p f 記 錄，然后服務器查找發(fā)送方域名的公開d n s 記錄，判斷發(fā)送方服務器的i p 地址是否與 記錄相符。如果相符，則發(fā)給郵箱用戶。否則，將郵件拋棄或者返回給發(fā)送方。 d o m a i n k e y s 是y a h o o 提出的基于p k i 方式對郵件發(fā)送者進行驗證的技術。發(fā)送方 生成公鑰私鑰對，私鑰作為郵件數(shù)字簽名，公鑰通過d n s 系統(tǒng)發(fā)布。在接收方，首先 提取郵件簽名，根據(jù)從d n s 系統(tǒng)中獲得發(fā)送域公鑰，驗證發(fā)送方的數(shù)字簽名。若無簽 名或驗證失敗，則拒絕郵件。 身份認證技術的效果很大程度取決于互聯(lián)網(wǎng)對其的支持程度。上述幾種策略都需要 在原有s m t p p o p 體系上做較大的改動。s p f s e n d e ri d 要求d n s 能支持反向m x 解析 記錄，d o m a i n k e y s 要求收發(fā)雙方的i s p 共同支持d o m a l n k e y s 技術。這無疑增加了實施 部署的困難。而且?guī)状筻]件服務商標準各異，難以建立統(tǒng)一的認證框架。 ( 3 ) 關鍵字過濾【1 4 j 一般情況下，垃圾郵件中總有一些詞匯出現(xiàn)的頻率很高，通過創(chuàng)建一些與垃圾郵件 關聯(lián)的單詞表可以用來過濾垃圾郵件。這種方法需要事先收集和定義大量的關鍵字，例 如高頻詞匯。由于垃圾郵件發(fā)送者經(jīng)常將一些單詞故意拼錯，試圖繞過關鍵字過濾器， 所以關鍵字列表需要經(jīng)常升級，通過加入新的關鍵字來適應這種變化。 關鍵字過濾方法簡單易用，可以有效阻斷絕大多數(shù)垃圾郵件，但也存在明顯的缺陷。 其過濾能力與關鍵字有很大關系，會產(chǎn)生較多誤報的情況。 ( 4 ) 行為識別模式 所謂“行為識別模式 ，是通過研究和統(tǒng)計垃圾郵件的行為，從而智能地在線識別 對電子郵件系統(tǒng)的各種惡意攻擊。例如，可以將垃圾郵件發(fā)送行為分為郵件濫發(fā)行為， 郵件非法行為，郵件匿名行為和郵件偽造行為。根據(jù)不同行為采取相應的對策，有效過 濾垃圾郵件【l ”。這種方法可以在通信階段識別出垃圾郵件，不需要進行內(nèi)容掃描，提高 碩士論文垃圾郵件過濾算法研究及系統(tǒng)實現(xiàn) 郵件的過濾速度1 6 1 刀，并可以在最大程度上保持其正常通信不受影響【1 8 】。北京大學校園 網(wǎng)部署的郵件過濾系統(tǒng)，通過行為識別模式“空中攔截”技術，可以攔截9 0 以上的垃 圾郵件，成功反擊了垃圾郵件的侵擾1 1 9 j 。 行為識別模式的缺點需要較長的時間才可以識別出垃圾郵件行為。若垃圾郵件改變 其行為特征，此方法效果便不明顯。 。 ( 5 ) 白名單 與黑名單正相反，白名單【2 0 】是可信任的郵件地址列表或郵件服務器列表。系統(tǒng)維持 一張白名單表，將收到電子郵件的發(fā)送地址與其進行對比，凡是屬于白名單的郵件才被 判定為合法郵件。中國反垃圾郵件聯(lián)盟維護實時白名單服務( c m l ) ，可作為其實時黑名 單服務( r b l ) 的一個附屬補充。 白名單是一種更嚴格的反垃圾郵件措施，因為不在該名單上的地址就不能向用戶發(fā) 送電子郵件。其主要優(yōu)點是反垃圾郵件的成本很低，對垃圾郵件的阻擋效果也很好，幾 乎可認為是1 0 0 。但是它極大地犧牲了電子郵件的易用性，因為它只能接收白名單中 發(fā)出的郵件，因此只適用于已建立起郵件聯(lián)系的郵箱間通訊。否則，需要通過其它方式 先行溝通加入白名單后才可通訊。這極大地限制了白名單技術的應用前景，只是較極端 的有限情況下才適用。 ( 6 ) 其它技術 除了上述五種最常用的反垃圾郵件技術外，還有很多其它技術，也有較好的效果。 如主動識別技術，分布式校驗值交換，基于規(guī)則評分的啟發(fā)式分析檢測技術，挑戰(zhàn)響應 技術，郵件附件長度大小匹配識別技術，支持掃描郵件附件是壓縮文件，結(jié)合防病毒系 統(tǒng)，攔截病毒垃圾郵件等 2 1 - 2 2 】。 1 2 4 綜合協(xié)作手段 新技術條件下垃圾郵件出現(xiàn)的新傳播方式開放、自由、流動、匿名的特點，已 經(jīng)使得其成為一個綜合性的社會問題，要想從根本上杜絕垃圾郵件的泛濫，必須采取全 民總動員的方式。由政府出面組織立法，行業(yè)制訂規(guī)則、積極協(xié)調(diào)，郵件服務商則提供 技術，用戶積極參與、協(xié)同合作。只有這樣，積極主動，各司其職，形成一個反垃圾郵 件的聯(lián)盟，才能從根本上取得顯著成效【2 】。 目前，政府已經(jīng)頒布多項法律法規(guī)，“垃圾郵件舉報受理中心陟也建立了完善的舉 報投訴機制，并且不斷進行垃圾郵件的行業(yè)檢查、開展與國際反垃圾郵件組織的交流與 合作。各個省市已經(jīng)陸續(xù)開通了舉報電話和舉報郵箱，接受網(wǎng)民的舉報。在動員全民的 過程中，通過大力宣傳，提高用戶自身的舉報意識。同時，技術層面上也不斷加快新的 垃圾郵件防范體系和方法的研究。如日本通信產(chǎn)業(yè)部表示，日本計劃啟動對新一代網(wǎng)絡 技術的研究，以便有一天可以取代現(xiàn)有的因特網(wǎng)；法國政府出資幫助開發(fā)面向微軟 7 1 緒論 碩士論文 o u t l o o k 和m o z i l l a 公司雷鳥電子郵件系統(tǒng)的開源軟件，用戶可以使用這種軟件報告垃圾 郵件，以更為快速的系統(tǒng)跟蹤方式打擊垃圾郵件發(fā)送者。 通過各方面的合作，一個初步的垃圾郵件舉報體系已經(jīng)建立，還要通過運用方便用 戶參與的反垃圾郵件系統(tǒng)，采用先進的技術產(chǎn)品，全民協(xié)作，主動出擊，營造一個健康 向上、繁榮和諧的網(wǎng)絡環(huán)境。 1 3 垃圾郵件過濾的機器學習方法 上一節(jié)介紹的前常用的垃圾郵件過濾技術從垃圾郵件的產(chǎn)生、傳播、接收各個方面 對垃圾郵件進行阻截。然而，這些技術普遍缺乏自適應的“學習 能力，不能夠應對當 前發(fā)展迅速、形式多樣的垃圾郵件。無論垃圾郵件形式如何變化，其最終目的都是要發(fā) 送到用戶手中。利用其這一特點，可以從郵件內(nèi)容出發(fā)研究垃圾郵件過濾問題。 本節(jié)從垃圾郵件的內(nèi)容出發(fā)，以機器學習的視角，重新看待垃圾郵件的過濾問題。 機器學習，顧名思義，就是讓“機器 能夠“學習 ，即通過感知“學習”環(huán)境世 界，使得“機器可以對于事物做出合理并且有意義的決策。其核心問題之一就是分類。 垃圾郵件過濾問題就是一個典型的分類問題，并且是分為兩類的分類問題。過濾垃 圾郵件，即判斷郵件是否是垃圾郵件。若為垃圾郵件，則采取相應措施進行過濾，否則 為正常郵件，不作處理。將垃圾郵件過濾問題納入到機器學習框架之下，很多機器學習 算法都可以應用其中。 機器學習經(jīng)過數(shù)十年發(fā)展，其理論研究和算法實現(xiàn)方面都有突破性的進展，應用范 圍也越來越廣。下面介紹一些在垃圾郵件過濾中應用較多的機器學習算法。 1 3 1 決策樹 決策樹【2 3 1 ( d e c i s i o n t r e e ) 是一種逼近離散目標函數(shù)的方法，可以表示為多個i f t h e n 規(guī)則。它將樣本用“屬性一值”二元組表示。樹的節(jié)點是屬。i 生：g ( a t t r i b u t e ) ，表示樣本對 此屬性的測試。節(jié)點后的分支表示該屬性的可能取值( v a l u e ) 。通過把樣本從根節(jié)點排列 ( s o r t ) 至u 葉子節(jié)點來對樣本進行分類，即葉子節(jié)點是樣本所屬的類別。它適用于具有離散 輸出的問題。 基本的決策樹算法是i d 3 算法，采用自頂向下的貪婪搜索遍歷可能的決策樹空間， 選擇分類能力最好的屬性用作樹根節(jié)點的測試。屬性的分類能力甩信息增益來度量。每 次選擇信息增益最大的屬性，即此屬性具有最好的分類能力。若訓練樣本數(shù)目較少或數(shù) 據(jù)含有噪聲，i d 3 算法會遭受過度擬合( o v e r f i t ) 1 b 7 題。c 4 5 算法通過“規(guī)則后修剪 ( r u l e p o s t - p n l n n i n g ) 很好地解決這個問題。 碩士論文 垃圾郵件過濾算法研究及系統(tǒng)實現(xiàn) 決策樹的優(yōu)點是能生成可理解的規(guī)則，計算量相對不是很大。應用于垃圾郵件過濾， 可以清晰顯示出哪些字段比較重要。文酬2 4 j 運用決策樹分類器，對郵件發(fā)送過程中的網(wǎng) 絡會話層數(shù)據(jù)進行挖掘和行為識別，有效地解決了垃圾郵件占用網(wǎng)絡帶寬的問題。 1 3 2k - 近鄰分類器 k 近鄰【2 5 1 ( k - n e a r e s t n e i g h b o r s ，分類器將樣本看作是n 維向量空間中的點， 并在中定義距離度量。其分類基于這樣一個假設：空間中樣本所屬的類別與其鄰近 的樣本的類別相似。因此，分類樣本時，分類器首先計算此樣本與空間中其它樣本之間 的距離，找出離此樣本最近的k 個樣本，即k - 近鄰。然后將k 個近鄰所屬的最普遍的 類別判定為該樣本的類別。 距離的度量一般使用歐氏距離，但也可有其它距離。文獻【2 硯7 1 使用余弦距離對垃圾 郵件進行分類。若對k 個近鄰的貢獻加權，可以使分類器有更好的魯棒性。例如可給離 該樣本距離較近的樣本較大的權值，然后通過k 個近鄰“投票”的方式找出該樣本的類 別。 k 近鄰分類器沒有訓練過程，原理非常直觀，容易理解。對于垃圾郵件過濾，常常 能夠取得好的結(jié)果【2 8 】，也可作為其它分類器的基礎。例如利用k 近鄰的惰性學習機制， 可將新的垃圾郵件動態(tài)加入訓練樣本集中，實現(xiàn)知識不斷積累。在此基礎上，應用k - 近 鄰分類器對未知郵件樣本進行精確匹配，可以去除合法郵件的誤判結(jié)果【2 9 1 。然而由于其 分類速度的局限性，不太適用于對分類速度要求較高的理解郵件過濾場合。 1 3 3 遺傳算法 遺傳算法瞄1 ( g e n e t i ca l g o r i t h m ，g a ) 是基于模擬進化啟發(fā)的學 - j 方法。它將假設 ( h y p o t h e s i s ) 表示為二進制位串的形式，通過交叉和變異選取當前最好的假設生成后續(xù)假 設。首先，算法隨機產(chǎn)生數(shù)個初始假設，稱為群體( p o p u l a t i o n ) 。然后不斷迭代這個群體。 每次迭代，根據(jù)適應度函數(shù)評估群體中的所有成員，用概率方法從其中選取適應度最高 的個體產(chǎn)生新一代群體。新一代群體，一部分由上代直接繼承，另一部分通過交叉和變 異產(chǎn)生。 適應度函數(shù)定義了候選假設的排序準則，是以概率方法選擇下一代群體的準則。例 如對于分類問題，可表示為對訓練樣本的分類準確率。選擇最優(yōu)個體的方法有輪盤賭選 擇、錦標賽選擇和排序選擇等。產(chǎn)生下一代群體使用遺傳算子如交叉和變異。常見的交 叉方法有單點交叉、兩點交叉、均勻交叉。 遺傳算法不易陷入局部最優(yōu)解，有較強的容錯能力。文獻【3 0 】使用其作為主要過濾算 法的優(yōu)化，提高了原有算法的性能。c h i u 等采用基于a l l i a n c e 的方法對郵件進行分類， 發(fā)現(xiàn)和交換其中感興趣信息。采用遺傳算法、粗糙集等多算法融合，提高了郵件過濾的 精度【j 。 9 1 緒論 碩士論文 1 3 4 粗糙集 粗糙集【3 2 ( r o u g hs e t ) 理論是波蘭數(shù)學家z p a w l a k 于1 9 8 2 年提出的一種處理模糊和 不確定性數(shù)據(jù)的新型數(shù)學工具。其主要思想是在保持分類能力不變的前提下，通過知識 簡約，導出問題的決策或分類規(guī)則。分類能力稱為知識。在樣本集中建立等價類，屬于 同一等價類的所有樣本稱為不可分辨的。通過對集合進行等價類的劃分，確定問題的近 似域，從而對含糊性和不確定性信息進行分析和推理，揭示出數(shù)據(jù)間隱含的知識和規(guī)則。 劉洋等【3 3 】將粗糙集引入到垃圾郵件過濾，采用了1 1 種非文本屬性( 包括收信人個數(shù)， 中繼個數(shù)等等) 來進行郵件分類。在一個小規(guī)模的垃圾郵件樣本上實驗，可以達到8 0 左右的正確率。王霞【3 4 1 研究基于聚類和粗糙集的屬性約簡子系統(tǒng)，使用郵件關鍵詞集合 進行二次過濾，形成最小的規(guī)則集合，用來指導用戶的文檔分類，進而過濾垃圾郵件。 1 3 5 人工神經(jīng)網(wǎng)絡 人工神經(jīng)網(wǎng)絡 2 3 1 ( a r t i f i e i a l n e u r a ln e t w o r k s ，是可用于分類、回歸和密度估計 的一大類算法。一個神經(jīng)網(wǎng)絡可看作是某個復雜函數(shù)。這個函數(shù)由很多小的處理單元( 即 神經(jīng)元) 組成一個網(wǎng)絡結(jié)構(gòu)。常用的神經(jīng)網(wǎng)絡有感知機，多層前向神經(jīng)網(wǎng)絡和反向傳播 神經(jīng)網(wǎng)絡。 感知機是最簡單的神經(jīng)網(wǎng)絡。其基本思想找出樣本工的一個線性函數(shù)翩= w r + b ， 使得刪 o 時，將x 歸為一類，刪 o ，則判定屬于該類。 否則，不屬于該類。w i n n o w 在學習w 時采用的是一種錯誤驅(qū)動的方法。在訓練時，一 旦發(fā)生錯誤，將根據(jù)需要降低或者升高w 相應特征的權重。w i n n o w 在訓練速度和分類 速度上具有較大的優(yōu)勢，所以具有更高的實用價值。另外，w m n o w 作為一種在線學習 方法，其在訓練集合不斷擴大的情況下能夠快速對分類器進行更新。 本文使用w i n n o w 進行郵件過濾，2 2 節(jié)詳細介紹基本w m n o w 和b a l a n c e dw i n n o w 兩種算法，并在3 3 2 和3 4 3 節(jié)使用w i n n o w 進行實驗。結(jié)果表明，w i n n o w 無論在訓 練速度還是分類性能都有很好的表現(xiàn)。 1 3 8b o o s t i n g b o o s t i n g 4 l 】是一個將弱分類器融合為強分類器的方法。它通過對已有的分類器進行 加權求和得到最終的分類器( 每個分類器稱為弱規(guī)則或者弱假設，加權求和以后的分類 器稱為強規(guī)則) 。b o o s t i n g 通過關注馬馬規(guī)則的錯誤而逐漸組合成強規(guī)則，它是一種錯誤驅(qū) 動的方法。a d a b o o s t 是b o o s t i n g 方法中最常用的一種。其本身是通過改變數(shù)據(jù)分布來 實現(xiàn)，它根據(jù)每次訓練集之中每個樣本的分類是否正確，以及上次的總體分類的準確率， 來確定每個樣本的權值。將每次訓練得到的分類器最后融合起來，作為最后的決策分類 器。b o o s t i n g 方法的最主要缺點是訓練速度較慢。舢i 【4 2 】等采用a d a b o o s t 算法進行垃圾 郵件過濾，并與樸素貝葉斯算法比較。結(jié)果表明，其性能優(yōu)于樸素貝葉斯。 a d a b o o s t 在本文2 3 節(jié)有詳細介紹，并對其泛化性能進行分析。3 3 3 和3 4 4 節(jié)敘 述了a d a b o o s t 的對比實驗，再次驗證了a d a b o o s t 的高效。 1 緒論 碩士論文 1 3 9 支持向量機 支持向量機【4 3 ( s u p p o r tv e c t o rm a c h i n e ，s v m ) 由v n v a p n i k 提出，是機器學 - - j 中最 廣泛應用的算法之一。其理論基礎統(tǒng)計學習理論保證了其有良好的泛化性能。支持 向量機的核心思想是最大間隔原則和核技巧。最大間隔原則即在尋找可將樣本正確地分 開超平面時，算法不是搜索任意的超平面，而是專注于具有最大間隔的超平面，即此超 平面離其最近的樣本的距離最大。對于線性可分問題，支持向量機總能找到最優(yōu)超平面。 核技巧則用于非線性可分問題，算法通過核函數(shù)將樣本從原始特征空間映射到高維空 間，使得原始問題在高維空間下轉(zhuǎn)換為一個線性可分問題。常用的核函數(shù)有多項式核、 m e r c e r 核和徑向基核等。 支持向量機具有消除各別樣本對分類產(chǎn)生的不良影響的能力，而且允許使用不同的 假設空間，有良好的魯棒性和柔韌性【4 1 1 。t r e t y a k o v l 4 4 1 等對支持向量機和其它機器學 - - j 算法在p u l 語料庫上作了對比實驗，結(jié)果顯示支持向量機優(yōu)于貝葉斯，次于k 近鄰。 y u ”】等的對比實驗表明，其性能優(yōu)于神經(jīng)網(wǎng)絡和貝葉斯。 本文在c c e r t 的中文郵件數(shù)據(jù)集上的實驗表明，支持向量機在中文垃圾郵件處理 中同樣具有良好的性能。2 4 節(jié)將詳述支持向量機算法，3 3 4 和3 4 5 節(jié)簡述了實驗及結(jié) 果。 1 4 本文主要工作及組織安排 1 4 1 主要工作 本文概述了當前主要的垃圾郵件過濾技術。特別地，本文從機器學習的角度，將垃 圾郵件過濾問題納入到機器學習的框架中，使用機器學習方法解決垃圾郵件過濾問題。 本文簡單介紹常用垃圾郵件過濾的機器學習方法，并且選擇了四種有代表性的算法 進行重點研究。它們是貝葉斯，w i n n o w ，a d a b o o s t 和支持向量機。通過對比實驗，驗 證了上述算法在垃圾郵件過濾中的有效性及各自的適用范圍。 此外，本文還實現(xiàn)了一種基于客戶端的垃圾郵件過濾系統(tǒng)。此系統(tǒng)集成了上述四種 過濾分類器，通過插件方式，嵌入到郵件客戶端o u t l o o k 當中。當新郵件當來時，可以 自動進行垃圾郵件過濾。 1 4 2 組織安排 本文章節(jié)組織安排如下： 第一章概述垃圾郵件基本概念以及目前反垃圾郵件研究狀況，特別介紹了垃圾郵件 過濾的機器學習方法，并介紹本文的主要工作。 第二章詳細介紹本文使用的四種垃圾郵件過濾算法，并對算法作簡要分析。 碩士論文垃圾郵件過濾算法研究及系統(tǒng)實現(xiàn) 第三章詳述對比實驗的流程及步驟，驗證四種算法的有效性，評估不同的參數(shù)設置 對算法分類性能的影響。 第四章介紹插件形式的基于客戶端的垃圾郵件過濾系統(tǒng)的實現(xiàn)。 第五章總結(jié)與展望。 1 5 本章小結(jié) 本章從垃圾郵件的基本概念與其危害入手，總結(jié)了當前反垃圾郵件的主要手段，包 括法律手段、經(jīng)濟手段、技術手段和綜合協(xié)作手段，分析了這些手段的優(yōu)點及不足之處。 特別地，在機器學習的框架下，本章簡要介紹了九種機器學習方法以及它們在垃圾郵件 過濾中的應用，尤其是貝葉斯、w i n n o w 、a d a b o o s t 和支持向量機。這四種方法將是本 文接下來章節(jié)討論的重點。 2 本文使用的算法碩士論文 2 本文使用的算法 上一章介紹了常用的垃圾郵件過濾方法， 章將詳細介紹本文使用的四種機器學習算法， 2 1 貝葉斯算法 特別介紹了垃圾郵件的機器學習方法。本 并對其作簡要分析。 2 1 1 起源 貝葉斯算法的理論基礎是貝葉斯統(tǒng)計推斷理論，其源于英國學者貝葉斯于1 7 6 3 年 在英國皇家學會哲學學報上發(fā)表的論文論機會學說中一個問題的求解。該文提出了 一種歸納推理的理論，后被一些統(tǒng)計學家發(fā)展成為一種系統(tǒng)的統(tǒng)計推斷方法，即貝葉斯 統(tǒng)計推斷理論。2 0 世紀5 0 年代以后，通過d ef m e t t i 、s a v a g a 、r a i f f a 、s c h l a i f e r 、j e f i e r y s 、 g o o d 等統(tǒng)計學家大量開拓性的研究工作，貝葉斯統(tǒng)計判斷理論獲得了迅速發(fā)展和完善。 目前，貝葉斯統(tǒng)計已經(jīng)成為與經(jīng)典統(tǒng)計學派并駕齊驅(qū)的當今兩大統(tǒng)計學派之一【4 5 1 。 貝葉斯統(tǒng)計推斷的一般模式為：先驗信息。樣本信息j 后驗信息( 如圖2 1 1 所示) ： 圖2 1 1貝葉斯推斷基本模式 先驗分布反映了試驗前對總體參數(shù)分布的認識，在獲得樣本信息后，人們對這個認 識有了改變，其結(jié)果就反映在后驗分布中，即后驗分布綜合了參數(shù)先驗分布和樣本信息。 貝葉斯推斷是一個“從無到有”的過程，且結(jié)果清楚自然，符合人們的思維習慣。從本 質(zhì)上說，它概況了一般人的學習過程，充分利用了樣本信息和參數(shù)的先驗信息，因而在 進行預測推斷中，能得到更精準的結(jié)果。 2 0 0 2 年8 月，p a u lg r a h a m 寫了一篇名為ap l a nf o rs p a m ) 的文章，提議建立垃 圾郵件和非垃圾郵件單詞的貝葉斯概率模型。2 0 0 3 年1 月，他在垃圾郵件大會上發(fā)表了 ( ( b e t t e rb a y e s i a nf i l t e r i n g ) ) 的演講，詳細介紹了其在ap l a nf o rs p a r e ) ) 中使用的算法 1 4 碩士論文 垃圾郵件過濾算法研究及系統(tǒng)實現(xiàn) 以及未來的打算m 。至此，貝葉斯算法開始在垃圾郵件過濾領域