劉 潔,王 錚,王 輝

(河南理工大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,河南 焦作 454000)

0 概述

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

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

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

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

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

1 改進(jìn)的互信息算法

1.1 互信息算法

垃圾郵件在經(jīng)過文本預(yù)處理后引入大量特征項,然而大量的特征項對于分類沒有意義,屬于噪音特征,不對其進(jìn)行降維處理將會影響垃圾郵件過濾的分類效果[17]?；バ畔⑺惴ㄊ翘卣鬟x擇算法的一種,互信息值表示出特征項與類別之間的相關(guān)程度,且互信息值越大,則該特征項與類別的關(guān)聯(lián)性越緊密?；バ畔⒅档挠嬎惴椒?

(1)

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

m個類別訓(xùn)練文本的互信息值計算方法為:

(2)

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

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

1.2.1 詞頻因子

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

(3)

(4)

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

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

(5)

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

1.2.2 類間差異因子

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

(6)

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

(7)

(8)

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

(9)

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

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.統(tǒng)計詞頻tfCspam(wi)和tfCham(wi)

4.統(tǒng)計文檔頻率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)結(jié)果代入式(9),計算IMI值

11.end

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

13.for i=1 to k

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

15.end

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

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

2.1 樸素貝葉斯分類模型

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

(10)

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

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

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

(11)

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

(12)

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

(13)

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

(14)

2.2 基于IMI的加權(quán)樸素貝葉斯分類器

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

(15)

(16)

將屬性權(quán)值代入上式并取對數(shù)可得:

(17)

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

(18)

(19)

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

IMI-WNB算法的實現(xiàn)過程如下所示:

算法2IMI-WNB算法

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

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

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

2.for i=1 to k

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

4.統(tǒng)計文檔頻率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)結(jié)果代入式(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)中進(jìn)行計算

16.end

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

18.end

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

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

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

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

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

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

3.1 實驗環(huán)境與數(shù)據(jù)

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

3.2 評價標(biāo)準(zhǔn)

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

(20)

(21)

(22)

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

3.3 實驗結(jié)果

本文實驗過程步驟如下:

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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