一種復合的雙引擎智能垃圾郵件過濾方法

摘要：研究了幾種常用的垃圾郵件過濾算法，分析了這幾種方法在郵件過濾應(yīng)用中各自的優(yōu)缺點。根據(jù)這幾種算法的優(yōu)缺點，對它們進行改良與結(jié)合，并增加了通過查看發(fā)出的郵件內(nèi)容進行自動學習的機制；同時針對中英文垃圾郵件采用不同的學習算法，從而建立一個適用中英文環(huán)境的垃圾郵件過濾方法。實驗表明，該方法的效率和性能達到了較好的水平。

關(guān)鍵詞：垃圾郵件; 正常郵件; 黑白名單; 規(guī)則; 貝葉斯過濾算法

中圖分類號：TP393．098文獻標志碼：A

文章編號：1001－3695(2008)01－0268－03

隨著因特網(wǎng)的迅猛發(fā)展， e mail已成為一種重要的通信方式。但由于其成本低廉、使用簡單、傳播迅速，因特網(wǎng)上出現(xiàn)了越來越多的不請自來的郵件——垃圾郵件。這些雜亂的垃圾郵件不僅浪費了網(wǎng)絡(luò)帶寬，并且使得用戶不得不花費大量的時間和精力來處理它們，嚴重影響了用戶對電子郵件的正常使用。為了處理這些垃圾郵件，垃圾郵件智能分析，自動過濾技術(shù)已經(jīng)得到一定的發(fā)展，尤其是近幾年出現(xiàn)了許多優(yōu)秀的技術(shù)成果；但是由于中文語境復雜，垃圾郵件識別的準確性和效率均不夠高，使用單一技術(shù)過濾垃圾郵件的效果并不理想。本文對幾種常用的過濾算法進行了研究、分析，并依據(jù)各算法的優(yōu)缺點對其進行改進和相互結(jié)合，以疊加的方式對郵件進行多層過濾，并通過各算法之間自動傳遞輔助信息來提高算法本身的智能化、精確度。本文提出了通過查看用戶發(fā)出的郵件內(nèi)容來進行輔助學習，從而提高自動獲取知識的能力。最終建立一個能夠適應(yīng)中英文實際運行環(huán)境的綜合垃圾郵件過濾方法。最后，通過仿真實驗，對該方法的效率和性能和其他單一算法進行了分析和比較。

1常用過濾算法的比較

1．1基于規(guī)則配置的過濾方法

基于規(guī)則的過濾算法也稱啟發(fā)式算法，在垃圾郵件過濾技術(shù)發(fā)展初期使用最廣。其原理是通過與預先設(shè)定的規(guī)則相比較來判定是否為垃圾郵件。 通常這些規(guī)則通過管理員手動設(shè)置一些特定關(guān)鍵字，如免費、優(yōu)惠、特價等作為判斷依據(jù)，因此，該算法需要長期定制和維護這些規(guī)則，隨著用戶需求的不同而手動調(diào)整。

雖然該算法也能在一定程度上滿足用戶的需求，能夠處理郵件頭和正文，但是實質(zhì)還是生硬的二值判斷，局限在二維空間上進行處理，缺少可信度的知識；同時要求用戶自己定義規(guī)則，對用戶的專業(yè)素質(zhì)要求高，用戶需要花費很多時間定義自己的規(guī)則。另外規(guī)則的純粹人工定制，可能考慮并不周全。

1．2黑名單方法

該算法的基本思想是將對方的IP地址或郵件地址存在一個數(shù)據(jù)庫，作為過濾判斷依據(jù)。當對方改變郵件地址或IP地址時，該方法就可能失去作用。這種算法到目前為止還是很常用的一種算法。當郵件到達時，過濾系統(tǒng)首先查看郵件首部的郵件發(fā)送者的地址，將地址和黑白名單中的地址進行比較，若處于黑名單的地址就直接拒收，若處于白名單中的地址就接收。該算法的優(yōu)點是簡單明確，占用計算機資源少。但它有兩個缺點：

a)黑白名單在設(shè)定時必須準確。如果將友好地址列在了黑名單中，會造成誤判。

b)黑白名單需要不斷地更新和維護，并且通常無法涵蓋所有的情況。因此，黑白名單算法的智能化不高，對一些預先不知道的垃圾郵件地址無法預防。

1．3基于統(tǒng)計的智能學習方法

中心矩向量就代表某一類郵件，如垃圾郵件或合法郵件。當一份新郵件經(jīng)過過濾系統(tǒng)時，就將其與垃圾郵件或合法郵件的中心矩向量進行類似性比較，根據(jù)cosine函數(shù)值的大小來分類。

當然該算法存在的問題是可能某些出現(xiàn)過于頻繁的詞并不能真正代表該郵件（如是、但是等副詞）。解決該問題的辦法是將dfi設(shè)定在一定范圍，若dfi超出了一定范圍，就不選用作為向量元素。

該算法是以某個詞在郵件中出現(xiàn)的頻率作為向量元素，所以它適用于各種語言環(huán)境。

1．5待解決的問題

綜上分析可知，每種算法在過濾垃圾應(yīng)用中均有其局限性。為此，本文中針對這種情況提出了一種復合智能算法。該算法對前面算法的優(yōu)點進行了整合，盡量將一些需要手動操作的過程進行了自動化處理，同時也盡量為用戶提供手動修改的靈活性。

2復合智能算法的設(shè)計

復合智能算法的出現(xiàn)就是解決傳統(tǒng)算法過濾垃圾郵件存在的不足，該算法盡可能遵循的一個原則，即以一種盡可能準確的算法讓用戶盡可能少地參與配置過濾系統(tǒng)，并智能地學習用戶需求和習慣，區(qū)分垃圾郵件和合法郵件，達到準確地過濾垃圾郵件的目的。復合智能算法采用層次過濾架構(gòu)。其中：黑名單算法過濾一些比較明顯的垃圾郵件；白名單就直接接收一些合法郵件，減少了中間環(huán)節(jié)，規(guī)則算法采用自定義的規(guī)則過濾了一些郵件同時提供了算法的學習資料；貝葉斯算法和中心矩向量算法是整個算法的核心部分，它們對規(guī)則算法提供的垃圾郵件、白名單提供的合法郵件、用戶發(fā)出的郵件和提取的郵件進行學習，過濾最后一部分垃圾郵件。黑名單算法必須是一種很保守的算法，黑名單庫主要是用戶手動配置，這樣做不至于去攔截一些合法郵件，當然這種配置也不是必需的，只是很好地方便了用戶。

復合算法的結(jié)構(gòu)圖如圖1所示，主要包括郵件過濾功能、郵件分詞功能、郵件學習功能、郵件配置功能。

2．1郵件過濾功能

當一份郵件到達郵件過濾系統(tǒng)時，系統(tǒng)首先提取發(fā)送方的郵件地址或IP地址，查看郵件地址或IP地址是否在黑名單中，不過一般不提倡根據(jù)IP來判斷，許多IP地址均是一些公共郵箱地址，一旦誤判，后果嚴重。通常黑名單的提取方法都相當慎重。在本算法中，默認要讓用戶自己手動去提取。當然，系統(tǒng)也可以配置成自動提取方式，系統(tǒng)根據(jù)規(guī)則算法的最終閾值來提取黑名單。若郵件不在黑名單中，就查看郵件是否在白名單中；若在白名單中，就接收郵件，同時提取詞匯讓貝葉斯算法或中心矩算法學習；若不在，就讓規(guī)則算法來判斷。

規(guī)則算法也起了重要的輔助作用。為了使該算法達到零誤判率，除了提高算法的閾值外，要根據(jù)實際情況調(diào)整各規(guī)則的分值，現(xiàn)已有相關(guān)的工具來測試這些規(guī)則的有效性。不過在本算法中，系統(tǒng)可以自動測試這些規(guī)則，系統(tǒng)默認配置成定期檢查這些規(guī)則的有效性，如讓這些規(guī)則分別對系統(tǒng)中已經(jīng)接收的垃圾郵件和合法郵件進行判別；若合法郵件被大量匹配，就說明要刪除該規(guī)則或者降低其分值，有些規(guī)則被垃圾郵件大量匹配，但由于沒有達到閾值漏報，而且在合法郵件中匹配值不高，就可以提高其分值。

2．2郵件配置功能

從圖1中，看出用戶可以查看收到的正常郵件和垃圾郵件，并且可以手動從中提取某些郵件的地址存入白名單或黑名單中。可能有些郵件從內(nèi)容上講是合法郵件，但是用戶由于某些個人的原因不想收到該用戶的郵件，用戶就可以將該郵件地址存入黑名單；同理，某些郵件從內(nèi)容講可能是屬于垃圾郵件的范疇，用戶由于需要，想收到該郵件，就可以將該郵件放入白名單庫。

針對用戶發(fā)出的郵件，系統(tǒng)會自動從其提取郵件地址列入到白名單中，同時也從郵件內(nèi)容中提取詞匯存入正常詞庫作為學習資料。通常情況下，用戶發(fā)出的郵件是友好的，用戶發(fā)出郵件的對象肯定是友好的，并且發(fā)出郵件的地址也一定是真實的。不僅如此，用戶對于一封新到達的正常郵件通常會給予回復，而一旦回復，這封新郵件的發(fā)送方地址自然作為發(fā)出地址被記錄下來。這樣做的好處有兩點：

a)白名單信息是在用戶正常使用郵件的過程中被自動獲取的，用戶無須額外的操作。

b)白名單具有很高的可信度，它的正確性不會因為過濾系統(tǒng)的誤判而降低。

同理，用戶發(fā)出的郵件還將作為貝葉斯算法進行正常郵件學習的主要來源。用戶發(fā)出的郵件內(nèi)容通常與收到的正常郵件的內(nèi)容相似，使用的語言習慣也是相通的。用戶在回復一封正常郵件時往往會附帶上原信件的內(nèi)容，這些內(nèi)容對貝葉斯算法和中心矩向量算法來說將是寶貴的學習資源。

2．3智能學習功能

本算法具有雙引擎智能學習功能：一個引擎是貝葉斯算法；另一個引擎是中心矩向量算法。它們同時將中文詞庫和英文詞庫區(qū)分開來。貝葉斯算法主要用于過濾英文郵件，中心矩向量算法主要用于過濾中文郵件。這樣做的目的是想充分發(fā)揮各種算法所長，貝葉斯算法已經(jīng)被驗證在英文環(huán)境下有良好的性能；中心矩向量算法在分類性能和準確性上要優(yōu)于貝葉斯算法[2]。如圖1所示，智能學習算法學習資料來源主要有兩類：

a)由系統(tǒng)自動提取。通過從規(guī)則算法過濾的垃圾郵件，以及從用戶這里發(fā)出的郵件，還有白名單算法接收的正常郵件，過濾系統(tǒng)可以提取學習資料。智能算法最重要的一點就是讓用戶可以不必手動參與過濾系統(tǒng)的操作，系統(tǒng)也能自動地過濾一些垃圾郵件。

b)由用戶手動提取。手動參與并不是必需的，僅是提供了一個進一步優(yōu)化系統(tǒng)的入口，用戶選取的學習資料是最準確的，可進一步提高系統(tǒng)分類的準確性和效率。

鑒于目前許多郵件系統(tǒng)均要求用戶手動提供資料給郵件系統(tǒng)學習，這就大大地降低了郵件的易用性。本智能學習算法將規(guī)則算法、黑白名單算法以及自動從用戶發(fā)送出去的郵件中提取相應(yīng)的學習詞匯結(jié)合在一起，既提高了郵件過濾的準確性和性能，又降低了用戶操作負擔。郵件配置功能也增加了用戶有針對性地過濾垃圾郵件的靈活性。

2．4詞庫特征項的選擇

文件的特征向量不可能包括所有的詞匯，所以很有必要用一定的算法進行特征選擇。 本文介紹的特征選擇算法如下：首先，去掉一些出現(xiàn)頻率過大又不起判別作用的代詞、副詞等，用ZipF規(guī)則來分析訓練庫中存放的垃圾郵件和正常郵件，分別除去郵件中出現(xiàn)次數(shù)少于三次的詞匯。ZipF規(guī)則指的是出現(xiàn)次數(shù)排第二位的詞匯出現(xiàn)的可能性是排在第一位的詞匯出現(xiàn)可能性的1/2；排第三位的詞匯出現(xiàn)的可能性是排在第一位的詞匯出現(xiàn)可能性的1/3。如果出現(xiàn)次數(shù)最多的詞匯出現(xiàn)次數(shù)是N，則排在第二位的詞匯出現(xiàn)次數(shù)為（i/i×N）。

3復合智能算法的性能評估 

通過實驗將復合智能算法與其他算法進行比較（表1），得到一種總結(jié)性結(jié)果。本文采用200封正常郵件（包括100封中文郵件和100封英文郵件）和200封垃圾郵件（包括100封中文郵件和100封英文郵件）作為實驗樣本，每個樣本均刪除掉在郵件分類中那些不起作用的代詞、副詞等。本文算法實驗效果的評價指標分別是查全率和誤報率。

在表1中貝葉斯和中心矩向量算法都是先學習200封郵件，再過濾200封郵件。復合智能算法則是在自動化的過程中實現(xiàn)實驗結(jié)果的。在本實驗中，筆者發(fā)現(xiàn)復合智能算法查全率達到了95.2%，遠遠高于其他算法。若是用戶再手動利用一下黑名單算法，調(diào)整一下規(guī)則算法和兩種學習算法的學習資料， 復合智能算法在查全率和誤報率方面會有更好的表現(xiàn)。當然隨著用戶手動發(fā)送郵件的增多，本算法學習資料的增多，過濾性能進一步提升。

4結(jié)束語

本文提出用一種復合雙引擎智能算法來過濾垃圾郵件。實驗結(jié)果表明復合智能算法要優(yōu)于傳統(tǒng)的算法中任何一種單一算法，而且最大程度地保持了算法的自動化和智能化，具有很高的適用性。但是為讓該方法有更高的準確性，對詞庫特征項的選取還有待進一步的優(yōu)化，而中心矩向量算法分類閾值的選擇也需深入研究。

參考文獻：

[1]GRAHAM P.A plan for spam[EB/OL].(2002－10－14).http://www.paulgraham.com/spam.html.

[2]GRAHAM P. A better Bayesian filtering[EB/OL].(2003－10 14).http://www.paulgraham.com/better.html.

[3]SOONTHORNPHISAJ N， CHAIKULSERIWAT K，PIYANAN T O. Anti spam filtering: a centroid based classification approach[C]//Proc of the 6th International Conference on Signal Processing. 2002: 1096 1099.

[4]吳立德. 獨立于語種的文本分類算法[C]//Proc of 2000 International Conference on Multilingual Information Processing. 2000:37－43.

[5]張曉冬，張書杰. 關(guān)于信息過濾模型的探討[J]. 計算機工程與應(yīng)用， 2002，38（5）：99 100.

[6]CHANG K C， FUNG R M. Target identification with Bayesian networks in a multiple hypothesis tracking system[J]. IEEE Trans Optical Engineering， 1997，36(3):684－691.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”