基于IMI-WNB算法的垃圾郵件過濾技術研究

劉 潔,王 錚,王 輝

(河南理工大學 計算機科學與技術學院,河南 焦作 454000)

0 概述

電子郵件能夠為用戶間的通信提供便捷,但垃圾郵件也隨之產生。根據卡巴斯基信息安全網站Securelist發布的2018年全球垃圾郵件數據顯示,中國成為全球第一垃圾郵件來源地,占全球垃圾郵件來源的11.69%[1]。垃圾郵件不僅占據大量的網絡帶寬和郵箱空間,容易造成網絡擁堵,而且其包含一些惡意軟件和釣魚網站,可能會給用戶帶來巨大的經濟損失。因此,對垃圾郵件進行過濾研究具有重要意義。

目前,關于垃圾郵件的過濾技術主要有基于黑白名單過濾技術、基于行為模式識別技術以及基于內容的過濾技術。其中,基于內容的過濾技術可行性較高、耗費較少,已經成為當前研究垃圾郵件過濾技術的主流方向[2-3],主要包括支持向量機(Support Vector Machine,SVM)、K鄰近(K-Nearest Neighbor,KNN)、樸素貝葉斯(Naive Bayes,NB)等[4]。樸素貝葉斯分類器實現較為簡單、且準確率高,已成為對垃圾郵件進行過濾的廣泛應用分類方法[5-6],但該方法基于條件獨立性假設,即假設條件之間完全獨立,在一定程度上影響了分類結果的精確度。

在對垃圾郵件分類前,特征選擇算法的優劣性對分類效果會造成影響,常見的幾種特征選擇方法有文檔頻率(DF)、信息增益(IG)、TF-IDF、開方擬合檢驗(χ2test)和互信息(Mutual Information,MI)等。其中,互信息效果雖然較差,但是該方法復雜度低、容易理解,是普遍使用的一種特征選擇方法[7-8]。傳統的互信息方法沒有計算特征詞的頻度,可能會出現低頻詞匯的互信息值較高的情況,導致分類精確度受到影響[9-10]。

針對特征冗余和獨立性假設的問題,研究人員對特征選擇和分類算法進行改進,以提高郵件的分類精度。文獻[11]將樸素貝葉斯、隨機樹和隨機森林3種機器學習算法應用于垃圾郵件數據集,其分類精度高于僅基于貝葉斯分類器的算法。文獻[12]提出一種支持向量機算法與K-均值聚類算法相結合的郵件分類算法,以提高分類精度、減少訓練時間。文獻[13]將互信息應用于加權樸素貝葉斯,通過加權部分消除樸素貝葉斯條件獨立性假設對分類效果的影響,從而提高了樸素貝葉斯的文本分類效果,但該方法存在沒有對傳統的互信息算法進行改進的問題。文獻[14]提出一種TSVM-NB算法,該算法利用樸素貝葉斯算法進行初次訓練,并使用支持向量機算法構造最優分類超平面以降低特征項維度。同時,再次利用樸素貝葉斯算法生成分類模型,提高垃圾郵件過濾的速度和正確率,但該算法適用于屬性向量重疊較大的語料集,對混疊性較弱的語料集的效率提升有限。文獻[15]引入熵的思想,并結合MapReduce技術提出一種基于MapReduce的改進互信息文本特征選擇機制,提高文本分類的精度。文獻[16]提出一種基于MapReduce的并行特征選擇方法,利用最大互信息理論選擇信息豐富的特征變量組合。上述方法僅改進分類過程中的特征選擇算法,并未聯同分類算法對分類進行綜合改進。

在以上研究基礎上,本文提出一種基于改進互信息的加權樸素貝葉斯(Improved Mutual Information-Weighted Naive Bayes,IMI-WNB)算法。在特征選擇階段,引入詞頻因子以及類間差異因子對傳統的互信息算法進行改進,實現特征降維。在分類階段引入改進的互信息(IMI)值對樸素貝葉斯算法進行屬性加權,實現對垃圾郵件的精確分類。

1 改進的互信息算法

1.1 互信息算法

垃圾郵件在經過文本預處理后引入大量特征項,然而大量的特征項對于分類沒有意義,屬于噪音特征,不對其進行降維處理將會影響垃圾郵件過濾的分類效果[17]?；バ畔⑺惴ㄊ翘卣鬟x擇算法的一種,互信息值表示出特征項與類別之間的相關程度,且互信息值越大,則該特征項與類別的關聯性越緊密。互信息值的計算方法為:

(1)

其中,w表示特征項,C表示類別,P(w,C)表示特征項w與類別C共同出現的概率,P(w)表示特征項在整個訓練文本中出現的概率,P(C)表示訓練文本中該類別在訓練文本中出現的概率,P(w|C)表示特征項w在類別C中出現的概率。

m個類別訓練文本的互信息值計算方法為:

(2)

通過式(2)計算出互信息值,并選取合適的閾值,可針對分類不重要的特征項進行過濾,從而實現特征的選擇。

1.2 基于詞頻因子與類間差異因子的IMI算法

1.2.1 詞頻因子

互信息算法的計算方式只考慮到特征詞的文本頻率而沒有考慮到詞頻,這在一定程度上會影響其分類精度。例如,2個特征項wj和wq的文本頻率相同,且特征項wj的詞頻是特征項wq詞頻的數倍,即tf(wj)>>tf(wq),一般認為詞頻更大的特征項wj與該類別的相關程度更高。然而按照傳統互信息的計算方式,這2個特征項的互信息值是相同的,這顯然與實際情況不符。因此,引入詞頻因子α對不同特征項間的詞頻差異進行描述,詞頻因子α可定義為:

(3)

(4)

其中,tfCspam(wi)與tfCham(wi)分別為特征項wi的垃圾郵件與非垃圾郵件類詞頻,dfCspam(wi)表示特征項wi的垃圾郵件類文本頻率,dfCham(wi)表示特征項wi的非垃圾郵件類文本頻率。

引入詞頻因子α后,改進的互信息值計算方法為:

(5)

特征項的詞頻高于文本頻率時,詞頻因子的權重越大,說明該特征項對郵件分類的能力越強。

1.2.2 類間差異因子

如果特征項在2個類別中都平均分布時,則不利于類別的判定,在某一類別出現較多而在另一類別中極少出現,一般認為該特征項對于郵件類別的判別作用較大。在概率統計中標準差反映了數據集的離散程度,標準差較大的特征項更利于郵件類別的判定。通過計算垃圾郵件類Cspam與非垃圾郵件類Cham之間特征項wi頻數的標準差對互信息模型進行改進。假設特征項wi在垃圾郵件Cspam類中的頻數為tfCspam(wi),在非垃圾郵件Cham類中的頻數為tfCham(wi),頻數平均值為tfavg(wi),則有:

(6)

引入類間差異因子σ對類間詞頻差異進行描述,類間差異因子σ定義為:

(7)

(8)

引入類間差異因子σ后,改進的互信息值計算方法為:

(9)

式(9)在式(5)的基礎上增加了類間頻數差異權重因子,體現出類間頻數差異對郵件分類的影響,提高互信息算法對有效特征項的選擇效率。

1.2.3 IMI算法描述

算法1IMI算法

輸入郵件特征向量集T={w1,w2,…,wn},特征子集維度k

輸出特征子集F={w1,w2,…,wk}

1.計算P(Cham)和P(Cspam)

2.for i=1 to n

3.統計詞頻tfCspam(wi)和tfCham(wi)

4.統計文檔頻率dfCspam(wi)和dfCham(wi)

5.計算P(wi|Cspam)和P(wi|Cham)

6.計算P(wi)

7.式(2)計算互信息值MI(wi)

8.式(4)計算詞頻因子αi

9.式(8)計算類間差異因子σi

10.將式(2)、式(4)、式(8)結果代入式(9),計算IMI值

11.end

12.Sort(T) //將特征向量按IMI值降序排列

13.for i=1 to k

14.將特征項wi加入特征子集F中

15.end

算法1是IMI-WNB算法中特征選擇階段的算法,IMI算法改進了傳統互信息算法中只考慮到文本頻率而未考慮到詞頻的問題,定義并引入詞頻因子與類間差異因子,體現詞頻與類間詞頻差異對分類的貢獻度,在完成特征降維的同時,還增強了特征項的表達能力。

2 基于IMI的樸素貝葉斯分類算法

2.1 樸素貝葉斯分類模型

樸素貝葉斯分類是基于貝葉斯定理與特征條件獨立假設的分類方法,其通過計算已有的事件訓練集得到事件概率,并對事件發生的概率進行預測。給定類別Cj與文本對象d時,貝葉斯公式可表示為:

(10)

其中,P(Cj)表示Cj類發生的先驗概率,對于垃圾郵件分類,類別C可被分為垃圾郵件與非垃圾郵件,即C={Cspam,Cham}。P(Cj|d)表示在給定輸入文本對象為d時,該對象屬于類別Cj的后驗概率。假設文本d的特征項為{w1,w2,…,wn},根據樸素貝葉斯條件獨立性假設,則有:

P(d|Cj)=P(w1,w2,…,wn|Cj)=

P(w1|Cj)×P(w2|Cj)×…×P(wn|Cj)=

(11)

將式(11)代入式(10)可得:

(12)

先驗概率P(d)為標準化常量,是一個常數。因此,樸素貝葉斯計算的最大后驗概率類別Cmap如下所示:

(13)

為了避免大量較小數相乘造成下溢出問題,對式(13)乘積取對數可得:

(14)

2.2 基于IMI的加權樸素貝葉斯分類器

樸素貝葉斯分類算法是基于條件獨立性假設的分類方法,然而在實際應用中,該獨立性假設通常不成立。為了消除部分條件獨立性假設對分類造成的不利影響,可通過在樸素貝葉斯公式中加入屬性權重值以區分不同特征項對分類的貢獻度。IMI值可以作為屬性權重應用于貝葉斯分類中,當IMI值計算結果較大時,特征項與類別的相關性較高,當IMI值較低甚至為負值時,表示該特征項對分類的作用較小?；バ畔⒅悼梢栽谝欢ǔ潭壬媳硎咎卣黜椗c類別之間的相關性,消除部分條件獨立性假設對分類的不利影響。將式(13)中的后驗概率賦予互信息權值可得:

(15)

(16)

將屬性權值代入上式并取對數可得:

(17)

為避免出現概率為0的情況,本文對互信息公式中的P(wi)和P(wi|Cj)進行拉普拉斯平滑處理,具體如下式所示:

(18)

(19)

其中,df(wi)表示特征項wi在整個訓練集中的文本頻率,dftotal表示整個訓練集的文本頻率,dfCj(wi)表示特征項wi在類Cj訓練集中的文本頻率,dfCj表示類Cj訓練集中的文本頻率。

IMI-WNB算法的實現過程如下所示:

算法2IMI-WNB算法

輸入特征子集F={w1,w2,…,wk},郵件樣本集D={d1,d2,…,dl}

輸出樣本集各樣本所屬類別C

1.計算P(Cham)和P(Cspam)

2.for i=1 to k

3.統計詞頻tfCspam(wi)和tfCham(wi)

4.統計文檔頻率dfCspam(wi)和dfCham(wi)

5.式(19)計算P(wi|Cspam)和P(wi|Cham)

6.式(18)計算P(wi)

7.式(1)計算互信息值MI(wi|Cspam)與MI(wi|Cham)

8.式(3)計算詞頻因子αij

9.式(7)計算類間差異因子σij

10.將式(1)、式(3)與式(7)結果代入式(16)計算得到IMI(wi,Cspam)與IMI(wi,Cham)值

11.end

12.for i=1 to l

13.for each wiin di

14.計算P(wi,Cspam)和P(wi,Cham)

15.將IMI(wi,Cspam)、IMI(wi,Cham)、P(Cham)、P(Cspam)與P(wi|Cspam)代入式(17)中進行計算

16.end

17.C(d,map)=max{C(di,ham),C(di,spam)} //判別類型

18.end

算法2是垃圾郵件過濾分類階段算法,在通過特征選擇階段算法1獲得特征子集后,算法2將IMI值作為屬性權重值應用于樸素貝葉斯分類中,體現出不同特征項對分類決策貢獻的差異,消除部分樸素貝葉斯條件獨立性假設對分類的不利影響,從而提高分類精度。

2.3 IMI-WNB算法的垃圾郵件過濾流程

IMI-WNB算法的垃圾郵件過濾流程如圖1所示。首先,在郵件預處理階段對文本進行去停用詞處理,然后再對文本進行分詞,采用Python中文分詞組件jieba對文本進行自動分詞。其次,在特征選擇階段使用本文所提IMI算法對文本中的特征項進行特征選擇。通過IMI算法可以將對分類無關的特征項篩選出去。最后,在訓練階段統計出樣本中的先驗概率與條件概率,并在應用階段使用IMI-WNB分類器分類時代入計算,根據計算出的最大后驗概率對郵件文本進行判定,當垃圾郵件概率大于非垃圾郵件概率時,分類器判定該郵件文本為垃圾郵件。

圖1 IMI-WNB算法的垃圾郵件過濾流程Fig.1 Spam filtering procedure of IMI-WNB algorithm

3 實驗結果與分析

本文使用trec06c郵件語料庫對垃圾郵件進行過濾實驗,并對IMI-WNB算法與傳統的NB算法進行過濾效果對比。同時,為了更充分地體現本文算法的過濾效果與現實意義,實驗將本文算法與其他改進算法進行過濾效果對比。

3.1 實驗環境與數據

實驗在Windows 10下進行,硬件配置為i5-7300HQ 2.50 GHz CPU,內存8.00 GB,硬盤500 GB。采用Python 3.7為實驗環境。實驗數據來自公開的垃圾郵件語料庫trec06c,從中隨機抽取14 000封郵件作為樣本集,其中7 000封為正常郵件,7 000封為垃圾郵件。

3.2 評價標準

為了對垃圾郵件過濾效果進行評價,實驗引入精確度P、召回率R和F值3個評價指標。假設垃圾郵件被判定為垃圾郵件的總數為Tspam,垃圾郵件被判定為正常郵件的總數為Fspam,正常郵件被判定為垃圾郵件的總數為Fham,則3個評價指標的計算方法分別為:

(20)

(21)

(22)

其中,精確度代表了垃圾郵件的檢對率,正常郵件被誤判為垃圾郵件會降低精確度,召回率代表了垃圾郵件的檢出率,召回率低說明有大量垃圾郵件被漏檢,F值為綜合精確度和召回率的評價標準,其表示郵件過濾的綜合效果。

3.3 實驗結果

本文實驗過程步驟如下:

步驟1對trec06c語料庫中選取的郵件樣本進行分詞處理,建立停用詞表去除文本中的停用詞,并對文本進行特征選擇。使用MI算法得到的特征項集為TMI,使用IMI算法得到的特征項集為TIMI。

步驟2分別從特征項集TMI與TIMI中提取n個特征項t1,t2,…,tn組建特征向量空間RMI與RIMI,在特征向量空間中分別利用NB算法與IMI-WNB算法進行分類。

步驟3將14 000封郵件樣本平均分為10份,采用十折交叉法對樣本進行計算,即每次選取其中9份樣本作為訓練集,1份樣本作為測試集進行分類實驗,每個樣本均有一次作為訓練集進行測試,每個維度總共進行10次測試,最后計算10次實驗平均值作為該維度的數據結果。實驗選取向量空間維度n從10到700對郵件進行分類,取平均值后繪制折線圖。精確度、召回率、F值的實驗結果如圖2～圖4所示。

圖2 2種算法的精確度實驗結果Fig.2 Experimental results of precision of two algorithms

圖3 2種算法的召回率實驗結果Fig.3 Experimental results of recall rate of two algorithms

圖4 2種算法的F值實驗結果Fig.4 Experimental results of F-value of two algorithms

從圖2可以看出:傳統NB算法的精確度隨著特征項維度的增大呈現先增大后降低再增大的趨勢,且當維度為150時精確度最低,當特征維度達到500后,精確度逐漸趨于平緩;然而本文算法在低維度時的精確度與傳統NB算法相差不大,當特征項的維度達到75后,其精確度開始下降,且在維度為150時達到最低,但其精確度受到的影響明顯小于傳統NB算法,且本文算法的精確度整體上高于傳統NB算法。

從圖3可以看出:傳統NB算法的召回率在特征維度達到20后開始下降,當特征維度達到150時召回率降至最低,接下來隨著特征項維度的增加召回率逐漸增加,當維度達到500時召回率趨于穩定;本文算法的召回率在特征維度為20時開始下降,但下降速度相對傳統NB算法更加趨緩,且整體召回率高于傳統NB算法。類似地,從圖4可以看出,相比傳統NB算法,本文算法的F值有明顯提高,且波動更加平緩。

在使用trec06c語料庫作為郵件樣本進行郵件過濾時,本文算法與PTw2v算法[18]、C4.5算法[19]、GWO_GA算法[20]的性能對比如表1所示。從表1可以看出:PTw2v算法的精確度與召回率相差不大,且有較好的分類效果;本文算法相較C4.5算法召回率更高,說明C4.5算法存在較多的垃圾郵件被漏檢,本文算法在F值上也高于該算法,說明本文算法具有更好的分類效果;GWO_GA算法的召回率較高,但在精確度上遠低于本文算法,說明該算法存在大量的正常郵件被誤判為垃圾郵件,且該算法的F值也略低于本文算法。

表1 4種算法的性能對比Table 1 Performance comparison of four algorithms

綜合分析上述實驗結果可知,相比傳統NB算法,本文算法的精確度、召回率與F值明顯提高,且變化趨勢更加穩定。

4 結束語

由于傳統互信息算法在特征選擇中對于詞頻以及類間頻數差異考慮不足,本文提出一種改進的互信息算法,并針對特征項在文本中的詞頻數以及類間頻數差異對分類的影響進行分析與改進,有效利用訓練集中的頻數信息,彌補了傳統互信息算法僅考慮到文本頻率的缺陷。同時,本文對樸素貝葉斯算法進行屬性加權并提出一種IMI-WNB算法,部分消除了樸素貝葉斯算法獨立性假設對分類的不利影響。仿真實驗結果表明,該算法明顯提高了郵件分類的精確度、召回率、F值及穩定性,且取得良好的過濾效果。本文的郵件過濾技術是基于郵件的文本內容進行分類,然而除了郵件文本內容外,郵件還有題目、發送時間、收件人與發件人等郵件頭信息可供分類判定。因此,下一步將利用加權樸素貝葉斯算法對郵件的文本內容與郵件頭信息進行綜合分析,以提高郵件過濾分類效果。