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

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

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

中圖分類號(hào)：TP393．098文獻(xiàn)標(biāo)志碼：A

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

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

1常用過濾算法的比較

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

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

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

1．2黑名單方法

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

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

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

1．3基于統(tǒng)計(jì)的智能學(xué)習(xí)方法

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

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

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

1．5待解決的問題

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

2復(fù)合智能算法的設(shè)計(jì)

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

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

2．1郵件過濾功能

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

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

2．2郵件配置功能

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

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

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

b)白名單具有很高的可信度，它的正確性不會(huì)因?yàn)檫^濾系統(tǒng)的誤判而降低。

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

2．3智能學(xué)習(xí)功能

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

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

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

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

2．4詞庫特征項(xiàng)的選擇

文件的特征向量不可能包括所有的詞匯，所以很有必要用一定的算法進(jìn)行特征選擇。 本文介紹的特征選擇算法如下：首先，去掉一些出現(xiàn)頻率過大又不起判別作用的代詞、副詞等，用ZipF規(guī)則來分析訓(xùn)練庫中存放的垃圾郵件和正常郵件，分別除去郵件中出現(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復(fù)合智能算法的性能評(píng)估 

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

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

4結(jié)束語

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

參考文獻(xiàn)：

[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]吳立德. 獨(dú)立于語種的文本分類算法[C]//Proc of 2000 International Conference on Multilingual Information Processing. 2000:37－43.

[5]張曉冬，張書杰. 關(guān)于信息過濾模型的探討[J]. 計(jì)算機(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)容請(qǐng)以PDF格式閱讀原文”