翟軍昌，車偉偉

(1.渤海大學(xué)，遼寧 錦州 121000;2.沈陽大學(xué)，遼寧 沈陽 110044)

0 引言

伴隨著電子郵件(E-mail)的廣泛應(yīng)用，大量包含欺詐、營銷、暴力、色情和病毒等信息的垃圾郵件也隨之產(chǎn)生。針對垃圾郵件問題的處理，目前主要以過濾技術(shù)為主，其中典型的代表有以基于內(nèi)容的過濾和基于身份標(biāo)示的過濾2種類型［1-4］?；趦?nèi)容的過濾技術(shù)，以貝葉斯(Bayes)［5-8］、支持向量機(jī)(SVM)和決策樹(KNN)等機(jī)器學(xué)習(xí)方法為代表，該類方法的主要特點是，根據(jù)郵件的內(nèi)容特征作為郵件分類的依據(jù)?；谏矸輼?biāo)示的過濾技術(shù)，以基于黑、白名單過濾，反向DNS查詢和基于用戶信譽(yù)的過濾技術(shù)等為代表，該類方法的特點是根據(jù)郵件發(fā)件人的身份特征相關(guān)信息來判斷郵件是否為垃圾郵件［1-4］。

目前基于貝葉斯算法的垃圾郵件過濾研究中，主要集中以下幾個方面的研究:(1)郵件樣本的特征項選擇處理方法研究［9］;(2)貝葉斯算法自身的改進(jìn)研究［10-11］;(3)貝葉斯算法與其它算法結(jié)合研究［12-13］;(4)基于貝葉斯算法的用戶反饋方式研究［1］等。

本文針對垃圾郵件過濾中過濾器對合法郵件的誤判問題，對條件熵H(c|t)中的條件概率p(ci|t)和)的計算方法利用貝葉斯法則進(jìn)行變形處理，并在變形后的計算方法中考慮特征項t出現(xiàn)和不出現(xiàn)時的先驗概率分布情況，利用特征項t的先驗概率對條件熵H(c|t)進(jìn)行加權(quán)處理，從而對信息增益的估計方法作了改進(jìn)。最后從降低用戶損失的角度去考慮，將改進(jìn)后的信息增益估計方法與最小風(fēng)險貝葉斯決策算法結(jié)合對郵件過濾。實驗結(jié)果表明改進(jìn)后的方法提高了過濾器對合法郵件的識別能力，降低了過濾器對合法郵件的誤判率，提高了過濾器的分類精度，從而降低了用戶的損失。

1 相關(guān)知識介紹

1.1 電子郵件文本表示

利用計算機(jī)處理電子郵件時，通常采用向量空間模型來表示，即對于任意一封郵件d，對應(yīng)的特征向量為=(x1，x2，...，xn)，xi∈(0，1)，i=0，1，…，n，其中xi為d對應(yīng)特征項Xi的權(quán)重。如果權(quán)重xi采用布爾權(quán)重表示方法時，xi取1表示在郵件中出現(xiàn)，xi取0表示在郵件中沒有出現(xiàn)。

1.2 特征項選擇與熵

對于大量的郵件樣本信息，特征詞刻畫了郵件樣本庫的特征信息，為了提高對郵件分類的精度，需要從郵件樣本庫中尋找對分類起作用的特征詞信息。特征項選擇是一種計算特征詞或郵件樣本概率分布與類別之間關(guān)系的評價方法，如文檔頻次(DF)、信息增益(IG)、互信息(MI)、相對熵和χ2統(tǒng)計等。通過用特征項選擇的方法可以達(dá)到對郵件樣本向量空間降維的目的，同時也可以提高對郵件處理的效率和分類精度。

定義1 熵。假設(shè)隨機(jī)變量X可能的取值xi有n種，如果每一種取值xi出現(xiàn)的概率為p(xi)，則隨機(jī)變量X的不確定性稱為熵，記為H(X)。

若隨機(jī)變量X的取值變化越多，則隨機(jī)變量X所攜帶的信息量越大，同時隨機(jī)變量X的熵H(X)也就越大。

定義2 條件熵。假設(shè)有隨機(jī)變量X和Y，隨機(jī)變量X和Y的可能取值xi和yi分別有n和m種，每一種取值xi和yj出現(xiàn)對應(yīng)的概率分別為p(xi)和p(yj)，p(xi|yj)表示觀測到隨機(jī)變量Y后隨機(jī)變量X發(fā)生的概率。則在觀測到隨機(jī)變量Y之后，隨機(jī)變量X的不確定性稱為條件熵，記為H(X|Y)。

1.3 貝葉斯分類模型

貝葉斯分類方法是一種基于概率分析的可能性推理理論，其作為一種有效的分類器，廣泛應(yīng)用于文本分類領(lǐng)域。在垃圾郵件過濾中，假設(shè)郵件樣本向量空間由 n 個特征項 X1，X2，...，Xn構(gòu)成特征向量 X?，郵件樣本空間中有2個類別，即c0垃圾郵件和c1合法郵件2類。對于任意給定的一封郵件d，根據(jù)貝葉斯公式計算郵件d屬于cj類的概率為:

在公式(3)中，可由全概率得出:

根據(jù)樸素貝葉斯假設(shè)，在公式(3)和公式(4)中對條件概率)的計算時，假設(shè)構(gòu)成中的各個特征項X1，X2，…，Xn是相互獨立的，則有:

在公式(5)中，先驗概率p(Xi|cj)可以采用文檔頻次估計的方法，若A代表cj類郵件樣本中出現(xiàn)特征詞Xi的郵件數(shù)量，B代表cj類郵件樣本的數(shù)量，則采用Laplacean平滑處理后的計算方法為:

在公式(3)和公式(4)中，先驗概率p(cj)的計算，可以通過樣本空間中cj類樣本的總數(shù)N占樣本空間的樣本總數(shù)M的比例表示，即:

1.4 最小風(fēng)險貝葉斯分類模型

在垃圾郵件過濾中，從用戶的角度去考慮，不同的用戶對于同一封郵件的決策不同，而且過濾器對合法郵件的誤判給用戶帶來的損失，大于過濾器對垃圾郵件誤判的損失。每一個用戶寧愿將垃圾郵件誤判為合法郵件，也不愿意將一封合法郵件誤判為垃圾郵件被過濾器過濾掉。因此最小風(fēng)險貝葉斯分類模型考慮2種分類誤判給用戶所帶來的風(fēng)險或損失，作出如下假設(shè):

(1)假設(shè)將郵件d判斷為垃圾郵件c0的決策為a0，將郵件d判斷為合法郵件c1的決策為a1。

(2)設(shè)損失因子為 λ(ai，cj)，λ(ai，cj)表示當(dāng)真實狀態(tài)為cj而采取的決策為ai時所帶來的損失。

(3)對于損失因子 λ(ai，cj)，當(dāng) i=j時(即郵件被正常識別)損失為0;當(dāng)垃圾郵件被誤判為合法郵件時損失為1，當(dāng)合法郵件被誤判為垃圾郵件時損失為 λ，并且 λ ＞1。

因此，對于任意給定的郵件d，如果采取決策ai，則它的條件期望損失為:

在過濾郵件時希望損失最小，所以最小風(fēng)險貝葉斯決策規(guī)則如下:

對于任意給定的郵件d，根據(jù)最小風(fēng)險貝葉斯決策規(guī)則式(9)知，當(dāng)郵件d被判斷為垃圾郵件時，有下式成立:

2 信息增益分析及改進(jìn)

2.1 信息增益分析

信息增益刻畫了隨機(jī)變量取值不確定性的程度，即用一個屬性t去劃分樣本空間而導(dǎo)致期望熵降低的程度。

在文本分類中，如果H(c)代表類別c的熵，H(c|t)代表觀測到屬性t后屬于類別c的條件熵，則信息增益的定義如下:

在公式(11)中，p(ci)表示ci類文本在訓(xùn)練樣本中出現(xiàn)的概率;p(t)和分別表示特征詞t在樣本中出現(xiàn)和不出現(xiàn)時的概率;p(ci|t)和分別表示在特征詞t出現(xiàn)和不出現(xiàn)時屬于ci類的概率。IG(t)反映了特征詞t對整個分類所提供的信息量。即IG(t)越大時，則說明特征詞t對整個分類的作用越大。

在信息增益的計算中，由于H(c)可以根據(jù)先驗概率計算得出，而對于一個確定的分類集來說，它是一個確定的值，因此每一個特征詞t的信息增益值(即IG(t))的大小由條件熵H(c|t)的估計值決定。又因為IG(t)的大小反映了t為整個分類所提供的信息量，所以條件熵H(c|t)的計算方法將直接影響最終分類的效果。

2.2 信息增益的改進(jìn)

(1)在公式(11)中，根據(jù)貝葉斯法則將條件熵H(c|t)中的條件概率p(ci|t)和的計算方法進(jìn)行變形，變形后的計算方法，如公式(12)所示:

(2)將公式(12)代入公式(11)中的條件熵H(c|t)計算式中，則條件熵H(c|t)的估計方法為:

在式(13)中，條件熵H(c|t)的值只與先驗概率p(t)、p(t|ci)和p(ci)的取值有關(guān)。

(3)在式(13)中，考慮到特征項t的分布情況，用先驗概率p(tj)乘以條件熵H(c|t)，對條件熵H(c|t)做加權(quán)處理，則新的條件熵H'(c|t)計算公式為:

(4)改進(jìn)后的信息增益估計式為:

3 實驗結(jié)果與分析

實驗中以VC++6.0為實驗環(huán)境，實驗中使用的郵件樣本是由 Androutsopoulos［7］等人提供的 Ling-Spam郵件樣本庫，選用了lemm_stop形式語料，其中包括2412封語言學(xué)家的合法郵件和481封垃圾郵件，將郵件樣本分成10份進(jìn)行交叉實驗。實驗中選擇了文獻(xiàn)［9］中召回率(SR)和正確率(SP)兩個評價標(biāo)準(zhǔn)。召回率反映了過濾系統(tǒng)發(fā)現(xiàn)垃圾郵件的能力，召回率越高，說明過濾系統(tǒng)識別垃圾郵件的能力越強(qiáng)。正確率反映了過濾系統(tǒng)識別垃圾郵件的正確率，即過濾系統(tǒng)正確識別垃圾郵件的能力，正確率越高，說明合法郵件被誤判為垃圾郵件的數(shù)量就越少。

實驗中選用特征向量維數(shù)從100～1000，每次實驗增加100，當(dāng)合法郵件被誤判為垃圾郵件時損失因子λ取999，分別采用公式(11)和公式(15)的方法計算特征詞的信息增益值，然后采用最小風(fēng)險貝葉斯決策公式(10)進(jìn)行分類決策，最后根據(jù)10份樣本交叉實驗的結(jié)果對召回率和正確率取平均值，實驗結(jié)果如表1所示。

表1 實驗結(jié)果(%)

通過表1可以看出，首先，在改進(jìn)后的算法中過濾器的正確率有明顯的提高，實驗結(jié)果表明改進(jìn)后的過濾器對合法郵件的誤判率在降低，降低了用戶的損失。其次，在改進(jìn)后的算法中過濾器的召回率在降低，表明改進(jìn)后的過濾器對垃圾郵件的誤判率有所提高。最后，在改進(jìn)后的算法中當(dāng)特征向量取600維、700維和1000維時，過濾器的正確率提高的比例低于過濾器召回率降低的比例，在其它情況下，過濾器的正確率提高的比例均高于過濾器召回率降低的比例。因此，算法改進(jìn)后的過濾器雖然漏掉了一部分垃圾郵件，但是對合法郵件的識別能力提高了，從而降低了過濾器對合法郵件的誤判給用戶帶來的損失。

4 結(jié)束語

在垃圾郵件過濾中，從用戶損失的角度去考慮，過濾器對合法郵件的誤判是用戶所不能容忍的。本文針對過濾器對合法郵件的誤判問題，通過對信息增益的條件熵估計方法作了改進(jìn)，從而提出了一種改進(jìn)的垃圾郵件過濾算法。實驗結(jié)果表明，雖然改進(jìn)后的算法降低了過濾器的召回率，但改進(jìn)后的算法提高了過濾器的正確率，提高了過濾器對合法郵件的識別能力，而且過濾器的正確率提高的比例高于過濾器召回率降低的比例，因此從用戶損失的角度去考慮，改進(jìn)后的算法降低了用戶的損失。

［1］黃國偉，許昱瑋.基于用戶反饋的混合型垃圾郵件過濾方法［J］.計算機(jī)應(yīng)用，2013，33(7):1861-1865.

［2］鄧維斌，王國胤，洪智勇.基于粗糙集的加權(quán)樸素貝葉斯郵件過濾方法［J］.計算機(jī)科學(xué)，2011，38(2):218-221.

［3］Sanchez F，Duan Z，Dong Y.Understanding forgery properties of spam delivery paths［C］//Proceedings of the 7th Annual Conference on Collaboration，Electronic Messaging，Anti-Abuse and Spam.2010.

［4］陳孝禮，劉培玉.應(yīng)用于垃圾郵件過濾的詞序列核［J］.計算機(jī)應(yīng)用，2011，31(3):698-701.

［5］Sahami M，Dumais S，Heckerman D，et al.A Bayesian approach to filtering junk e-mail［C］//Proceedings of the 1998 AAAI Workshop on Learning for Text Categorization.1998:55-62.

［6］Androutsopoulos I，Koutsias J，Chandrinos K V，et al.An evaluation of naive Bayesian anti-spam filtering［C］//Proceedings of the 11th European Conference on Machine Learning.2000:9-17.

［7］Metsis V，Androutsopoulos I，Paliouras G.Spam filtering with naive Bayes:Which naive Bayes?［C］//Proceedings of the 3rd Conference on Email and Anti-Spam.2006.

［8］Chen Bin，Dong Shoubin，F(xiàn)ang Weidong.Introduction of fingerprint vector based Bayesian method for spam filtering［C］//Proceedings of the 4th Conference on Email and Anti-Spam.2007.

［9］翟軍昌，秦玉平，車偉偉.應(yīng)用特征詞分類貢獻(xiàn)的垃圾郵件過濾研究［J］.計算機(jī)工程與應(yīng)用，2012，48(34):116-119，170.

［10］薛正元.基于改進(jìn)貝葉斯決策的郵件過濾［J］.計算機(jī)工程與應(yīng)用，2013，49(7):98-101，125.

［11］梁志文，楊金民，李元旗.基于多項式模型和低風(fēng)險的貝葉斯垃圾郵件過濾算法［J］.中南大學(xué)學(xué)報:自然科學(xué)版，2013，44(7):2787-2792.

［12］陶永才，薛正元，石磊.基于MapReduce的貝葉斯垃圾郵件過濾機(jī)制［J］.計算機(jī)應(yīng)用，2011，31(9):2412-2416.

［13］夏超，徐德華.一種改進(jìn)的貝葉斯郵件過濾算法［J］.計算機(jī)與現(xiàn)代化，2010(10):125-128，132.

［14］Guzella T S，Caminhas W M.A review of machine learning approaches to spam filtering［J］.Expert Systems with Applications，2009，36(7):10206-10222.

［15］Lai Chih-chin.An empirical study of three machine learning methods for spam filtering［J］.Knowledge-based Systems，2007，20(3):249-254.