基于ＴＦ＊ＩＤＦ的垃圾郵件過濾特征選擇改進算法

摘 要：隨著電子郵件的普及與應用，垃圾郵件的泛濫也越來越受到人們的關注。而如何進行郵件特征選擇，是郵件分類中的重要問題。在介紹詞頻和倒文檔頻度的基礎上，對幾種常用的特征選擇算法進行了分析和比較，針對現(xiàn)有特征選擇算法過于機械的缺點，將關鍵字權重引入到郵件分類中，提出了一種基于關鍵詞權重的TF*IDF特征選擇改進算法，并進行了實驗驗證。實驗結果表明，采用該算法改進后的貝葉斯過濾器具有更好的過濾效果。

關鍵詞：垃圾郵件；過濾器；貝葉斯；特征選擇；TF*IDF

中圖分類號：TP393.098文獻標志碼：A

文章編號：1001-3695(2009)06-2165-03

doi:10.3969/j.issn.1001-3695.2009.06.050

Improved feature selection algorithm in spam filtering based on TF*IDF

CHEN Qi， WU Zhao-hui， YAO Fang， SONG Xiu-rong， ZHANG Fu-zhi

(College of Information Science Engineering， Yanshan University， Qinhuangdao Hebei 066004， China)

Abstract:With the development of network and computer， more and more spam e-mails affect our lives. This paper firstly introduced the current popular feature selection methods based on term frequency and inversed document frequency. Then it compared and analyzed the various feature extraction algorithms， and introduced a new extracted feature algorithm by using the advanced TF*IDF. Finally it completed the experimental verification with the PU1 corpus. The experiment results demonstrate that the advanced naive Bayes filter has better performance.

Key words:spam；filtering；Bayes；feature selection；TF*IDF

基于內(nèi)容的垃圾郵件過濾中，原始提取得到的特征詞庫十分龐大，向量維數(shù)也十分驚人。在這些特征詞中，有些對區(qū)分正常郵件和垃圾郵件所起到的作用不但非常小，有時還會引起噪聲，導致過度擬合。特征選擇就是為了降低向量空間的維數(shù)，提高分類效果，減小計算復雜度，從而努力移除原始特征中不帶分類信息或帶信息比較少的詞。常用的特征選擇方法有：文檔頻度、信息增益、期望交叉熵、互信息、 χ2分布等^[1]。本文主要介紹向量空間模型中廣泛使用的TF*IDF公式，并將其用于垃圾郵件文本特征項的選擇。TF指單詞在文本中出現(xiàn)的次數(shù)，IDF為逆文本頻數(shù)也叫倒文檔頻度^[2]。

1 TF*IDF算法

1.1 算法相關概念

在介紹TF*IDF(term frequency*inverse document frequency)算法之前，首先引入TF和IDF兩個概念。

1)詞頻(TF) 即一個特征項在某一文檔中出現(xiàn)的次數(shù)，反映了某一個特征項對該文本的重要性，其定義如下所示：

TFij=freqij=特征詞ti在文檔dj中的頻率

可利用對數(shù)降低詞頻對TF取值的影響，從而減少了少數(shù)高頻詞對特征權重計算的影響，如下所示：

TFij=log(freqij)+1

2)倒文檔頻度(IDF) 這一分量反映了某一特征項區(qū)別于其他文檔的程度，是一個關鍵詞在整個數(shù)據(jù)全局中重要性的全局性統(tǒng)計特征，稱為倒文檔頻度。如果一個詞在整個數(shù)據(jù)全集中出現(xiàn)的頻度很小，則它應該是反映包含該類詞的文檔內(nèi)容的重要詞匯。因此，一個關鍵詞的權重應該與該詞所在的文檔的總數(shù)成反比或近似反比的關系。

IDFi=log(n/ni)=log(全集中文檔的總數(shù)/含關鍵詞i的文檔總數(shù))

其中：n為全部訓練樣本數(shù)，ni為出現(xiàn)特征詞ti的訓練樣本數(shù)。它反映了某一特征項在分類過程中對某一類的區(qū)分度。

1.2 原始TF*IDF算法

TF*IDF公式認為對區(qū)別文檔最有意義的特征項應該是那些在一類文檔中出現(xiàn)頻率足夠高，而在文檔集合的其他文檔中出現(xiàn)頻率足夠小的詞語，所以引入了逆文本頻度IDF的概念，并以TF和IDF的乘積作為特征空間坐標系的取值測度。設TFij為特征詞ti在文檔dj中的頻度；n為全部訓練樣本數(shù)，ni為出現(xiàn)特征詞ti的訓練樣本數(shù)，最初的TF*IDF公式如下所示。

weigth(Tij)=TFij×IDFij=freqij×log(n/ni)

對TFij降維處理后如下所示：

weigth(Tij)=TFij×IDFij=log((freqij+1)×log(n/ni)

考慮到文本長度對項的權重的影響，作歸一化處理后公式如下所示：

weight(Tij)=TFij×log(n/ni)/mi=1(TFij×log(n/ni))2

TF*IDF在文本分類領域取得不錯的分類效果，但這并不代表它沒有缺點。陸玉昌等人^[3]從單詞加權和向量旋轉的角度，解釋了IDF的簡單結構不可能很好地反映單詞的有用程度，提出了采用信息增益、文本權重特征選擇方法作為特征選擇公式中的后半部分，對單詞加權，并通過實驗驗證了改進的有效性。

2 TF*IDF算法的不足

2.1 郵件過濾中特征選擇特點

郵件過濾中對特征項的選擇有以下三種特點：

a)二元分類。垃圾郵件過濾不同于普通文本多元分類，是典型的二元分類。對所有郵件只有兩個類別，即正常郵件和垃圾郵件，非此即彼。所以，在進行特征選擇時不能只考慮一個類別對應權重而忽視另一個類別的信息。這就要求在使用TF*IDF算法時，必須綜合考慮對應權重。

b)文本短小。郵件文本一般都比較短小，但內(nèi)容龐雜，在進行特征提出時要求能快速實現(xiàn)。TF*IDF算法計算復雜度相對比較低，能滿足這種小文本分類的要求。

c)數(shù)量有限。郵件過濾中特征項數(shù)量的選擇與分類效果也有著密切的聯(lián)系。在特征選擇過程中，特征太少，不能全面表現(xiàn)郵件的內(nèi)容，區(qū)分度不夠；特征太多，又有一些無關的特征引入了分類噪聲。有實驗數(shù)據(jù)表明^[4]：當中文語料的特征項集合大小為1 200~1 800時，精確率和召回率相對較高；對英文語料庫，其最佳特征集合大小為350~800。

2.2 TF*IDF局限性

TF*IDF的主要思想是：如果某個詞條，在一個文檔中出現(xiàn)的頻率TF高，并且在其他文檔中很少出現(xiàn)，則認為該詞條具有很好的類別區(qū)分能力，適合用來進行分類。而IDF的主要思想是：如果包含詞條t的文檔越少，ni越小，IDF越大，也就是說明詞條t具有很好的類別區(qū)分能力。如果某一類Ci中包含詞條t的文檔數(shù)為m，而其他類包含t的文檔總數(shù)為k，顯然所有包含t的文檔總數(shù)為n=m+k。當m增大，n也增大，IDF的值會減小，則表示該詞條t類別區(qū)分能力不強。但是實際上，m越大，說明詞條t在Ci類的文檔中頻繁出現(xiàn)，能夠很好地代表Ci類的文本特征，應該賦予較高的權重并選做該類文本的特征詞。這就是IDF沒有考慮特征詞在類間分布的一方面。

另一方面，雖然包含t的文檔n較少，但是如果其均勻分布在各個類間，這樣的特征詞就不適合用來分類，應該賦予較小的權重，然而按照TF*IDF計算其IDF值卻很大。存在這些缺點的原因主要是因為TF*IDF是將文檔集作為整體來考慮的，特別是其中IDF的計算，而沒有考慮到特征項在類間的分布情況。

3 TF*IDF特征選擇改進算法

3.1 對TF和IDF的改進

1)對詞頻(TF)的改進 設freqi1為特征詞ti在垃圾郵件樣本集中出現(xiàn)的次數(shù)，freqi2為ti在正常郵件樣本集中出現(xiàn)的次數(shù)。如果某一特征項既在垃圾郵件中大量出現(xiàn)，并且在正常郵件中大量出現(xiàn)，雖然該特征項出現(xiàn)的頻度很高，但實際上它并不具備有很好的區(qū)分度。因此對詞頻分量進行進一步改進如下所示：

TFi=log(|freqi1-freqi2|+1)+1

用特征項在垃圾郵件和正常郵件中詞頻的絕對差來表述特征項的詞頻，可以更加精確地進行特征項的選擇。

2)對倒文檔頻度(IDF)的改進 IDF反映了某一特征項對某一類的區(qū)分度。應用到垃圾郵件的特征選擇時，如果某一特征詞對垃圾郵件有區(qū)分度，但同時對正常郵件也有區(qū)分度，那它就不是一個可有效區(qū)分的特征詞。因此對IDF進行改進如下所示：

IDFi=|log(n/ni)-log(/ni)|

其中：n表示垃圾郵件集文檔數(shù)，ni表示含ti的垃圾郵件文檔數(shù)；表示正常郵件集文檔數(shù)，ni表示含ti的正常郵件文檔數(shù)。

綜合考慮詞頻和倒文檔頻度，在垃圾郵件過濾中，對每個特征項的關鍵字權重可以定義如下： weight(ti)=TFi×IDFi=[log(|freqi1-freqi2|+1)+1]×|log(n/ni)-log(/ni)|

其中：weight(ti)值越高的特征項，重要性越高，即為準備提取的內(nèi)容。

3.2 TF*IDF改進算法

IM-TF*IDF(improved TF*IDF， IM-TF*IDF)算法的完整表述如下:

a)在垃圾郵件過濾過程中，首先對郵件文本進行預處理，對分詞所得的特征項的集合，利用停用詞庫去掉多次出現(xiàn)但不表現(xiàn)文本主題的特征詞(如連詞、量詞、語氣助詞、感嘆詞等)以及文本中出現(xiàn)頻率過少的詞；另外，在對中文垃圾郵件進行處理時還應注意，去掉單字符的特征詞和超過七個字(通常有效的中文詞組小于七個字)的特征詞，進行粗糙降維。

b)然后利用IM-TF*IDF構造評價函數(shù)來計算特征詞與類之間的關系，即對于郵件文本中的每一個特征項ti，它的關鍵字權重weight(ti)計算公式如下所示：

weight(ti)=[log(|freqi1-freqi2|+1)+1]×|log(n/ni)-log(/ni)|

其中：weight(ti)為特征詞ti的權重，freqi1為特征詞ti在垃圾郵件樣本集中出現(xiàn)的次數(shù)，freqi2為ti在正常郵件樣本集中出現(xiàn)的次數(shù)，n為垃圾郵件集的文檔總數(shù)，ni表示含ti的垃圾郵件文檔數(shù)；表示正常郵件集的文檔總數(shù)，ni表示含ti的正常郵件文檔數(shù)，計算各個特征項的關鍵字權重。

c)根據(jù)weight(ti)的大小，對所有待選擇的特征項進行排列，從隊列中按權重大小依次從大到小選取符合要求數(shù)量的特征項用于垃圾郵件過濾中。通過選取預定數(shù)量的最優(yōu)特征詞，從而提高郵件過濾器的分類精度。

改進后的TF*IDF特征選擇方法既考慮到了特征項在文本出現(xiàn)的頻率，同時又對于低頻特征項也有很好的區(qū)分度，使有些出現(xiàn)次數(shù)雖低但都很重要的特征得到了重視。同時改進后的IM-TF*IDF算法對特征項在類別間的分布進行了綜合的考量，既能提取出對垃圾郵件高度敏感的特征項，也能提取出能正確反映正常郵件特點的特征項，使得綜合提取的結果能攜帶更多的分類信息。該算法可用做特征選擇方法或作為對其他特征選擇方法二次提取的一種補充^[5]。

4 實驗及評價

4.1 評價體系 

設待判定的郵件集合中共有N封郵件，其分布情況如表1所示。

表1 垃圾郵件過濾系統(tǒng)判定情況分布

判定實際為垃圾郵件實際為正常郵件

垃圾郵件AB

正常郵件CD

N=A+B+C+D=Ns+Nh。其中Ns=A+C為實際的垃圾郵件數(shù)目，Nh=B+D為實際的正常郵件數(shù)目。通?？梢圆捎靡韵碌脑u價指標：

a)查全率(召回率，recall)

recall=A/(A+C)=A/Ns=正確判定為垃圾郵件的數(shù)目/實際垃圾郵件數(shù)目

即垃圾郵件的檢出率，反映過濾系統(tǒng)發(fā)現(xiàn)垃圾郵件的能力。當查全率越大時，漏網(wǎng)的垃圾郵件數(shù)越少，系統(tǒng)性能也越好。

b)準確率(正確率，precision)

Precision=A/(A+B)=正確判定為垃圾郵件的數(shù)目/判定為垃圾郵件數(shù)目

即垃圾郵件的檢對率，反映“找對”垃圾郵件的能力。準確率越高，表示將合法郵件誤判為垃圾郵件的可能性越小，進而使系統(tǒng)性能越好。

4.2 實驗對比

采用本文IM-TF*IDF特征選擇算法進行實驗，綜合考慮詞頻和倒文檔頻度，weight(ti)值越高的特征項，能攜帶代表本類別特性的分類信息越多，重要性越高，即為準備提取的內(nèi)容。實驗1 DF、IG和IM-TF*IDF實驗對比。

分別采用DF、IG和 IM-TF*IDF進行特征選擇的垃圾郵件過濾器過濾效果對比。

本文實驗完全采用英文郵件樣本，語料采用公開的垃圾郵件公共語料庫PU1。PU1語料庫中共有1 099封郵件，其中正常郵件681封，垃圾郵件481封。將其均分為10份，每份大約110篇。分別采用文檔頻度(Df)、信息增益(IG)和改進型詞頻*倒文檔頻度(IM-TF*IDF)三種特征選擇方法作為郵件特征選擇方法，在貝葉斯過濾器上進行郵件過濾實驗，對比提取不同數(shù)目或比例的郵件特征項所得到的過濾效果。每次取PU1語料庫中9份作為訓練集進行學習，將剩余1份作為測試集，進行實驗。實驗結果對比如圖1、2所示。

實驗2 對比TF*IDF和IM-TF*IDF 

與實驗1類似，分別采用原始的TF*IDF算法和改過后的IM-TF*IDF算法作為特征選擇方法，在貝葉斯過濾器上進行實驗。其實驗結果查全率和準確率對比如圖3、4所示。

4.3 結果分析

由實驗1可知，隨著選取特征數(shù)量的增多，DF、IG和IM-TF*IDF三種特征選擇算法中的查全率和準確率基本都保持增長的趨勢，這說明隨著特征數(shù)的增多，所選擇特征包含的種類信息越來越全面，進而能更好地反映本類郵件的特點，分類效果也就越好。

由實驗1可知，DF、IG和IM-TF*IDF三種算法整體比較而言，采用IG和TF*IDF優(yōu)于DF，而在特征數(shù)量比較小的情況下TF*IDF方法又優(yōu)于IG，隨著選取特征量的增多，IG算法的準確率略高于TF*IDF算法，但IG算法的運行時間遠高于IM-TF*IDF。總的來說，改進后的TF*IDF方法整體優(yōu)于IG。

由實驗2可知，相對于原始的TF*IDF算法，無論是查全率還是準確率上，改進后的IM-TF*IDF算法都有明顯的優(yōu)勢，這是因為改進后的TF*IDF算法既考慮到了特征項在垃圾郵件中的重要程度，又考慮了它在正常郵件中的反映程度，使選擇所得特征項更具代表性，減少了分類噪聲。

由實驗1、2可知，對于四種特征選擇算法都有一個所選特征項占單詞表比例的大致峰值，使得該算法得到的分類效果最好。而超過這一峰值，再增加特征選擇的特征詞數(shù)并不能使過濾得到更好的效果。這是因為過多特征詞的使用引入分類噪聲的結果。

綜合兩個實驗可知，IM-TF*IDF算法在時間復雜度上小于IG，大于DF，等價于原始的TF*IDF，但在分類精度上遠遠優(yōu)于另外三種算法。

5 結束語

在基于內(nèi)容的垃圾郵件過濾中，無論采用哪種過濾算法，對其進行特征選擇都是必不可少的，特征選擇算法的優(yōu)劣與垃圾郵件過濾器的性能有著直接的關系。本文針對原始TF*IDF對分類反映程度的不足，提出一種改進型的特征選擇TF*IDF算法IM-TF*IDF，綜合考慮特征詞在類別間的分布，使TF和IDF在計算時既考慮到了特征詞在正常郵件中的分布，又考慮到它在垃圾郵件中的分布，并將DF、IG、原始TF*IDF和IM-TF*IDF算法分別應用到樸素貝葉斯過濾器中進行對比實驗，實驗結果表明這種采用IM-TF*IDF進行特征選擇的貝葉斯過濾器，可以取得更好的過濾效果。

參考文獻：

［1］張文良，黃亞樓，倪維健.基于差分貢獻的垃圾郵件過濾特征選擇方法[J].計算機工程，2007，33(8):80-82.

[2]DEEPAK P，PARAMESWARAN S.Spam filtering using spam mail communities[C]//Proc of IEEE SAINT’05.[S.l.]:IEEE Press，2005：377-383.

[3]陸玉昌，魯明羽，李凡.向量空間法中單詞權重函數(shù)的分析和構造[J].計算機研究與發(fā)展，2002，39(10):1205-1210.

[4]李翔鷹，葉楓.一種基于多貝葉斯算法的垃圾郵件過濾方法[J].計算機工程與應用，2006，42（31）:114-116.

[5]LAI C C.An empirical study of threemachine learning methods for spam filtering [J].Knowledge-Based System，2007，20（3）：249-254.