基于改進信息增益的垃圾郵件過濾研究

翟軍昌，車偉偉，劉艷麗，康建軍

（1.渤海大學 遼寧 錦州 121000；2.沈陽大學 遼寧 沈陽 110044；3.鐵嶺市清河區教育局 遼寧 鐵嶺 112003）

垃圾郵件日益泛濫產生一些列的問題，如導致郵件服務器的運行效率降低、產生網絡擁塞和網絡安全等。隨著垃圾郵件技術手法越來越復雜，如隱藏郵件頭等[1]，垃圾郵件更加具有攻擊性，而且垃圾郵件的危害更大，因此垃圾郵件過濾研究具有重要的現實意義。目前針對垃圾郵件的處理主要以過濾技術為主，其中基于機器學習方法的垃圾郵件過濾技術應用研究最多，如 SVM、KNN、Winnow、Bayes等方法[2]。 機器學習的方法將垃圾郵件過濾看成一個分類問題，首先收集大量合法郵件和垃圾郵件作為樣本，然后指導過濾器對收集到的郵件樣本進行學習，最后通過訓練好的過濾器對新到達的郵件進行最終分類。過濾器通過對郵件樣本的訓練和學習可以自動獲得垃圾郵件的特征，并根據垃圾郵件特征的變化準確的對垃圾郵件進行過濾。

在實際使用中，用戶寧愿接收更多的垃圾郵件，也不愿意將合法郵件誤判為垃圾郵件，此外不同的用戶對于同一封郵件的決策也不同，因此如何有效提取郵件樣本的特征，降低對合法郵件的誤判，顯得尤為重要。在垃圾郵件過濾中，如何有效的選取郵件特征詞時垃圾郵件過濾的關鍵問題之一[3-4]。文中針對垃圾郵件過濾中特征項選擇問題，提出了一種改進的信息增益的方法提取郵件的特征項，并結合最小風險貝葉斯分類器對郵件過濾，實驗結果表明改進后的方法降低了對合法郵件的誤判。

1 郵件特征提取

電子郵件本身是一種無結構的文本，計算機對郵件進行學習和處理時，一般要采用向量空間模型對郵件進行向量化處理，向量空間可以看成是由n個特征項t1，t2，…，tn構成的向量空間，其中特征項可以是字、詞、詞組或短語等，對于任意一個給定的郵件d在向量空間中對應的特征向量為：dˉ={w1，w2，…，wn} ，其中w1，w2，…，wn代表特征項t1，t2，…，tn在郵件d中的權重。

特征項選擇是指通過一種評價方法，從高維向量空間中提取出對郵件分類有效的特征項，從而達到對向量空間降維的目的。常用的特征項選擇方法有文檔頻次（DF）、信息增益（IG）、互信息（MI）、相對熵、 χ2統計和優勢率等[5]。

2 改進的信息增益

信息增益（Information Gain，IG）是指用一個屬性t去劃分樣本空間而導致期望熵降低的程度，如果IG（t）越大，則說明t對整個分類的作用越大。IG（t）反映了單詞t為整個分類所提供的信息量。信息增益的定義如下：

在式（1）中，p（ci）表示 ci類文本在訓練樣本中出現的概率；p（t）表示單詞t在訓練樣本中出現的概率；p（表示單詞t在訓練樣本中不出現的概率；p（ci）表示在單詞t出現的情況下屬于ci類的概率；p（ci）表示在單詞t不出現的情況下屬于ci類的概率。

在垃圾郵件過濾中，由于垃圾郵件分類屬于二類問題，若令ci的取值為c0和c1，c0代表垃圾郵件，c1代表正常郵件。則式（1）變為式（2）：

信息增益同時考慮了每一個特征項出現和不出現時，對判斷一個文本是否屬于某個類所提供的信息量。但是在實際使用中，對垃圾郵件過濾時，當某個特征項在一類郵件中出現的概率高于該特征項在另一類郵件中出現的概率時，則該特征項對該類郵件的分類貢獻要大于對另一類郵件分類時的貢獻?；谏厦娴姆治?，在對垃圾郵件過濾時，考慮到特征項在垃圾郵件和合法郵件中出現的概率不同，從而對兩類郵件分類的貢獻不同，因此對于式（2）做如下改進：

最后根據式（3）和式（4）對式（2）改進后的信息增益記為IG（t）′，IG（t）′的計算方法如式（5）所示：

3 最小風險素貝葉斯決策

貝葉斯分類算法是文本分類中廣泛使用的方法，它是假定對所研究的對象D事先已經有一定的認識，用P（D）表示D的先驗概率。在觀察對象D之前，確定某個假設空間C中的某個假設c成立的先驗概率為P（c）。在c成立時，觀察到D的先驗概率為P（D）。在觀察到訓練數據D后，c成立的后驗概率為P（c），根據貝葉斯公式可知：

貝葉斯方法在垃圾郵件過濾中取得了非常好的效果[6-10]，但是在實際對郵件過濾中，過濾器可能把一封垃圾郵件誤判為合法郵件，也可能把一封合法郵件誤判為垃圾郵件。對于每一個用戶來說，他們寧愿將垃圾郵件誤判為合法郵件，也不愿意將一封合法郵件誤判為垃圾郵件被過濾器過濾掉，因此把一封合法郵件誤判為垃圾郵件的損失遠遠大于把一封垃圾郵件誤判為合法郵件的損失。在垃圾郵件過濾中，考慮兩種分類錯誤所帶來的風險或損失因素作出如下假設：

設決策空間由兩個決策ai（i=0，1）組成，其中i=0表示決策為垃圾郵件，i=1表示決策為合法郵件。設損失因子為λ=（ai，cj），λ=（ai，cj）表示當真實狀態為 cj（j=0 代表垃圾郵件，j=1代表合法郵件）而采取的決策為ai時所帶來的損失。當i=j時（即郵件被正常識別）損失為0；當垃圾郵件被誤判為合法郵件時損失為1，當合法郵件被誤判為垃圾郵件時損失為λ，并且 λ>1。

根據上面的假設可知，對于任意給定的郵件d，如果采取決策ai，則它的條件期望損失為：

根據最小風險貝葉斯假設和式（8）知，有式（9）和式（10）成立：

在過濾郵件時希望損失最小，所以最小風險貝葉斯決策規則如下：

對于任意給定的郵件d，根據最小風險貝葉斯決策規則式（11）知，當郵件d被判斷為垃圾郵件時，有下式成立：

4 實驗結果與分析

在Windows XP環境下，以VC++6.0為實驗平臺，實驗中使用的語料庫為Androutsopoulos[7]等人提供的Ling-Spam，實驗中選用了lemm_stop語料庫，其中包括2 412封語言學家的正常郵件和481封垃圾郵件，將郵件樣本分成10份進行交叉實驗。對于過濾器的評價標準，采用召回率（SR）、正確率（SP）其計算方法如下：

其中nS→S表示被正確識別出的垃圾郵件總數，nS→L表示被誤判為合法郵件的垃圾郵件總數，nL→S表示被誤判為垃圾郵件的合法郵件總數。

實驗中選用特征向量維數從100～1 000，每次實驗增加100，閾值λ取999，最后根據10份樣本交叉實驗的結果對召回率和正確率取平均值，召回率（SR）、正確率（SP）在算法改進前和改進后的變化如圖1和圖2所示。

圖1 召回率變化對比Fig.1 Recall change contrast

圖2 正確率變化對比Fig.2 Precision change contrast

5 結 論

文中針對垃圾郵件過濾中的特征項選擇問題，提出了一種改進的信息增益方法來提取特征詞，并采用了最小風險貝葉斯的決策方法，最后在英文語料庫上進行實驗，實驗結果表明在改進后的算法中雖然漏掉了一部分垃圾郵件，但是合法郵件誤判率在降低，對合法郵件判斷更加準確了，這樣用戶的損失也就降低了，這正好符合最小風險的貝葉斯決策的思想。

文中下一步研究的工作是在提高過濾器的正確率，降低用戶損失的基礎上，提高過濾器的召回率。

[1]Sanchez F，DUAN Zhen-hai，DONG Ying-fei.Understanding forgery properties of spam delivery paths[C]//CEAS 2010 Seventh annual Collaboration， Electronic messaging，AntiA-buse and Spam Conference （CEAS 2010），Redmond，Washington，2010.

[2]陳孝禮，劉培玉.應用于垃圾郵件過濾的詞序列核[J].計算機應用，2011，31（3）：698-701.

CHEN Xiao-li，LIU Pei-yu.Word sequence kernel applied in spam-filtering[J].Joumal of Computer Applications，2011，31（3）：698-701.

[3]鄧維斌，王國胤，洪智勇.基于粗糙集的加權樸素貝葉斯郵件過濾方法[J].計算機科學，2011，38（2）：218-221.

DENG Wei-bin，WANG Guo-yin，HONG Zhi-yong.Weighted naive bayes spam filtering method based on rough set[J].Computer Science，2011，38（2）：218-221.

[4]閆鵬，鄭雪峰，李明祥，等.關于貝葉斯推理的垃圾郵件特征選擇評估函數[J].計算機工程與應用，2008，44（33）：105-107.

YAN Peng，ZHENG Xue-feng，LI Ming-xiang， et al.Feature selection approach based on Bayes reasoning in anti-spam classifier[J].Computer Engineering and Applications， 2008，44（33）：105-107.

[5]盧揚竹，張新有，祁玉.郵件過濾中特征選擇算法的研究及改進[J].計算機應用，2009，31（3）：2812-2815.

LU Yang-zhu，ZHANG Xin-you，QI Yu.Improvement of feature selection method in spam filtering[J].Joumal of Computer Applications，2009，31（3）：2812-2815.

[6]Sahami M，Dumais S，Heckerman D，et al.A Bayesian approach to filtering Junk e-mail[C]//Learning for Text Categorization：PapersfromAAAIWorkshop.Madison，Wisconsin，1998：55-62.

[7]Androutsopoulos I，Koutsias J，Chandrinos K V，et al.An evaluation of naive bayesian anti-spam filtering[C]//Proc.of the Workshop on Machine learning in the New Information Age，11th European Conference on Machine Learning（ECML’00），Barcelona，Spain，2000：9-17.

[8]Schneider K.A Comparison of Event Models for Naive Bayes Anti-spam E-mail Filtering [C]//Procedings of the 10th Conference of the European Chapter of the Association for Computational Linguistics（EACL’03），2003：307-314.

[9]Vangelis M，Androutsopoulos I，Georgios P.Spam filtering with Naive Bayes-which Naive Bayes?[C]//CEAS 2006 Third Conference on Email and AntiSpam（CEAS 2006） ，Mountain View，California USA，July 27-28，2006.

[10]CHEN Bin，DONG Shou-bin，FANG Wei-dong.Introduction of Fingerprint Vector based Bayesian Method for Spam Filtering[C]//CEAS 2007 Fourth Conference on Email and Anti-Spam，MountainView（CEAS2007），CaliforniaUSA，2007.