基于改進(jìn)信息增益的垃圾郵件過(guò)濾研究

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

（1.渤海大學(xué) 遼寧 錦州 121000；2.沈陽(yáng)大學(xué) 遼寧 沈陽(yáng) 110044；3.鐵嶺市清河區(qū)教育局 遼寧 鐵嶺 112003）

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

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

1 郵件特征提取

電子郵件本身是一種無(wú)結(jié)構(gòu)的文本，計(jì)算機(jī)對(duì)郵件進(jìn)行學(xué)習(xí)和處理時(shí)，一般要采用向量空間模型對(duì)郵件進(jìn)行向量化處理，向量空間可以看成是由n個(gè)特征項(xiàng)t1，t2，…，tn構(gòu)成的向量空間，其中特征項(xiàng)可以是字、詞、詞組或短語(yǔ)等，對(duì)于任意一個(gè)給定的郵件d在向量空間中對(duì)應(yīng)的特征向量為：dˉ={w1，w2，…，wn} ，其中w1，w2，…，wn代表特征項(xiàng)t1，t2，…，tn在郵件d中的權(quán)重。

特征項(xiàng)選擇是指通過(guò)一種評(píng)價(jià)方法，從高維向量空間中提取出對(duì)郵件分類有效的特征項(xiàng)，從而達(dá)到對(duì)向量空間降維的目的。常用的特征項(xiàng)選擇方法有文檔頻次（DF）、信息增益（IG）、互信息（MI）、相對(duì)熵、 χ2統(tǒng)計(jì)和優(yōu)勢(shì)率等[5]。

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

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

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

在垃圾郵件過(guò)濾中，由于垃圾郵件分類屬于二類問(wèn)題，若令ci的取值為c0和c1，c0代表垃圾郵件，c1代表正常郵件。則式（1）變?yōu)槭剑?）：

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

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

3 最小風(fēng)險(xiǎn)素貝葉斯決策

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

貝葉斯方法在垃圾郵件過(guò)濾中取得了非常好的效果[6-10]，但是在實(shí)際對(duì)郵件過(guò)濾中，過(guò)濾器可能把一封垃圾郵件誤判為合法郵件，也可能把一封合法郵件誤判為垃圾郵件。對(duì)于每一個(gè)用戶來(lái)說(shuō)，他們寧愿將垃圾郵件誤判為合法郵件，也不愿意將一封合法郵件誤判為垃圾郵件被過(guò)濾器過(guò)濾掉，因此把一封合法郵件誤判為垃圾郵件的損失遠(yuǎn)遠(yuǎn)大于把一封垃圾郵件誤判為合法郵件的損失。在垃圾郵件過(guò)濾中，考慮兩種分類錯(cuò)誤所帶來(lái)的風(fēng)險(xiǎn)或損失因素作出如下假設(shè)：

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

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

根據(jù)最小風(fēng)險(xiǎn)貝葉斯假設(shè)和式（8）知，有式（9）和式（10）成立：

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

對(duì)于任意給定的郵件d，根據(jù)最小風(fēng)險(xiǎn)貝葉斯決策規(guī)則式（11）知，當(dāng)郵件d被判斷為垃圾郵件時(shí)，有下式成立：

4 實(shí)驗(yàn)結(jié)果與分析

在Windows XP環(huán)境下，以VC++6.0為實(shí)驗(yàn)平臺(tái)，實(shí)驗(yàn)中使用的語(yǔ)料庫(kù)為Androutsopoulos[7]等人提供的Ling-Spam，實(shí)驗(yàn)中選用了lemm_stop語(yǔ)料庫(kù)，其中包括2 412封語(yǔ)言學(xué)家的正常郵件和481封垃圾郵件，將郵件樣本分成10份進(jìn)行交叉實(shí)驗(yàn)。對(duì)于過(guò)濾器的評(píng)價(jià)標(biāo)準(zhǔn)，采用召回率（SR）、正確率（SP）其計(jì)算方法如下：

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

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

圖1 召回率變化對(duì)比Fig.1 Recall change contrast

圖2 正確率變化對(duì)比Fig.2 Precision change contrast

5 結(jié) 論

文中針對(duì)垃圾郵件過(guò)濾中的特征項(xiàng)選擇問(wèn)題，提出了一種改進(jìn)的信息增益方法來(lái)提取特征詞，并采用了最小風(fēng)險(xiǎn)貝葉斯的決策方法，最后在英文語(yǔ)料庫(kù)上進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明在改進(jìn)后的算法中雖然漏掉了一部分垃圾郵件，但是合法郵件誤判率在降低，對(duì)合法郵件判斷更加準(zhǔn)確了，這樣用戶的損失也就降低了，這正好符合最小風(fēng)險(xiǎn)的貝葉斯決策的思想。

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

[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]陳孝禮，劉培玉.應(yīng)用于垃圾郵件過(guò)濾的詞序列核[J].計(jì)算機(jī)應(yīng)用，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]鄧維斌，王國(guó)胤，洪智勇.基于粗糙集的加權(quán)樸素貝葉斯郵件過(guò)濾方法[J].計(jì)算機(jī)科學(xué)，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]閆鵬，鄭雪峰，李明祥，等.關(guān)于貝葉斯推理的垃圾郵件特征選擇評(píng)估函數(shù)[J].計(jì)算機(jī)工程與應(yīng)用，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]盧揚(yáng)竹，張新有，祁玉.郵件過(guò)濾中特征選擇算法的研究及改進(jìn)[J].計(jì)算機(jī)應(yīng)用，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，F(xiàn)ANG 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.