基于改進TFIDF算法的郵件分類技術

陶 峰，湯 鯤，程 光

(1.武漢郵電科學研究院，湖北 武漢 430074；2.南京烽火星空通信發(fā)展有限公司，江蘇 南京 210019；3.東南大學 計算機科學與工程學院，江蘇 南京 210096)

0 引 言

中國互聯(lián)網協(xié)會反垃圾郵件中心發(fā)表的《2014年第四季度中國反垃圾郵件狀況調查報告》，根據調查結果估算，用戶平均每周接收到的電子郵件數量為35.0封，平均每周接收到的垃圾郵件數量為14.3封，收到垃圾郵件的比例是41.0%。根據中國互聯(lián)網協(xié)會反垃圾郵件中心的調查顯示，有超過50%的用戶因為反垃圾郵件功能弱而影響對電子郵件的滿意程度。因此，如何實現對這類垃圾郵件的準確過濾成為近年來熱門的研究課題。

垃圾郵件分類方法用的比較多的有樸素貝葉斯(Naive Bayes)[1-2]、神經網絡[3]、K-近鄰[4]、支持向量機(SVM)[5-6]等。由于郵件分類算法都是建立在特征項提取基礎上的，因此特征項提取直接影響著郵件的分類效果。

TFIDF[7-10]是廣泛使用的權值計算方法，用術語頻率乘以逆文檔來表示特征項的權值。近年來，不少學者將TFIDF算法用于特征提取，并在實驗中取得了較好的效果。目前，在郵件分類中常用的特征提取方法有：信息增益[11-12]、互信息[13]、期望交叉熵、文本證據權、CHI統(tǒng)計[14]以及TFIDF算法。TFIDF因其便于理解、操作簡單、時間復雜度低等優(yōu)點而應用廣泛，但是仍然存在很多不足。該方法只考慮了特征詞文檔的絕對數量和特征詞在某類郵件中的詞頻，沒有考慮到特征詞在類中的分布情況和特征詞在其他類郵件中的詞頻，高估了低頻詞的作用并低估了高頻詞的作用。文中將對TFIDF進行一定的修改和優(yōu)化，以克服傳統(tǒng)TFIDF的缺陷。

1 特征提取算法及其改進

1.1 CHI統(tǒng)計算法

CHI統(tǒng)計算法是使用統(tǒng)計的方法計算特征詞t與郵件類別d的關聯(lián)程度。特征詞t與郵件類別d的相關度表示如下：

(1)

其中，N表示郵件總數量；A表示郵件類別d中包含特征詞t的郵件數量；B表示包含特征詞t但是不屬于郵件類別d的郵件數量；C表示郵件類別d中不包含特征詞t的郵件數量；D表示不屬于郵件類別d也不包含特征詞t的郵件數量。

1.2 傳統(tǒng)的TFIDF算法

TFIDF的主要思想是：如果一個特征詞在一類郵件中出現的頻率TF較高，并在其他類郵件中出現頻率較少，則認為這個特征詞具有較強的類別區(qū)分能力，適合用于對郵件分類。TF是詞頻，表示特征項在一類郵件中出現的頻率。IDF是逆文檔頻率，是特征在文本空間中分布情況的量化，常用的計算方法是IDF=log(N/n),N表示總的郵件數量，n表示出現特征向量的郵件數量。TFIDF是結合詞頻和逆文檔頻率兩種屬性而得到的計算方法，具體計算公式如下：

W(d,t)=tf(d,t)×log(N/n)

(2)

其中，W(d,t)表示特征t在郵件類別d(垃圾郵件或者正常郵件)中的權重。

1.3 TFIDF算法存在的問題

TFIDF算法是將郵件集作為一個整體來進行處理，并沒有考慮到特征詞的分布問題，明顯存在以下三點不足：

(1)考慮到特征詞在類內分布的情況：如果一個特征詞在某一類郵件中均勻分布，則說明這個特征詞能很好地區(qū)分該類別，分類能力較強，該特征詞應該被賦予較高的權值。相反，如果一個特征詞只在某一類郵件中的幾封郵件中出現，則說明這個特征詞不能很好地代表該類郵件，應該賦予較低的權值。對此，傳統(tǒng)的TFIDF算法并不能很好地處理。

(2)TFIDF算法并沒有考慮到特征詞在類間的分布情況，TFIDF算法只考慮到特征項在某一類郵件中出現的頻率情況。如果特征詞在一類郵件中出現的頻率很高，但是在另一類郵件中出現的頻率很低，這樣的特征詞應該被賦予很高的權值。相反，如果特征詞在某一類郵件中出現的頻率很高，但是在另一類郵件中出現的頻率也很高，這樣的特征詞代表性很差，應該賦予較低的權值。對此也需要進行一定的改進。

(3)IDF的主要思想是：如果包含特征詞t的文檔越少，即n越小，IDF越大，說明特征詞t的區(qū)分能力越好。如果特征詞在某一類郵件中大量出現，n也會很大，按照IDF公式得到的IDF的值會很小，說明這個特征詞區(qū)分能力不強。實際上特征詞在某一類中大量出現，說明該特征詞能夠很好地代表這類郵件，這樣的特征詞應該被賦予較高的權值。相反，如果特征詞比較均勻地分布在垃圾郵件集和正常郵件集中，這樣的特征詞對分類的貢獻較小，即使其中包含特征詞t的郵件數量n較小，也應該賦予較小的權值，但是IDF卻賦予較大的值，顯然不合理。

如表1所示，假設有5封正常郵件和5封垃圾郵件，若只考慮3個特征詞，分別用t1、t2、t3表示，di(i=1,2,…,5)表示垃圾郵件，ni(i=1,2,…,5)表示正常郵件。

表1 特征詞分布表

從表1可以看出，特征詞t1在垃圾郵件中均勻分布，說明特征詞對垃圾郵件的分類能力較強。t1特征詞沒有在正常郵件中出現，說明對正常郵件沒有分類能力。特征詞t2在垃圾郵件中出現頻率很高，但是集中在個別郵件中，說明特征詞t2的分類能力較弱。t3在垃圾郵件和正常郵件集中均勻分布，幾乎沒有分類能力。

根據傳統(tǒng)的TFIDF算法分別計算特征詞t1、t2、t3的權值大小，結果見表2。

表2 傳統(tǒng)TFIDF權值計算結果

從表2可以看出，特征詞t1在垃圾郵件類別中的權重為10.4，而特征詞t2和t3在垃圾郵件類別中的權重分別為34.5和15.3。當郵件集中出現特征詞t1和t2的頻率相同時，特征詞的權重由IDF確定，但是僅僅考慮特征詞出現的文檔數量顯然是不合理的。特征詞t3在垃圾郵件和正常郵件之間分布均勻，說明該特征詞不具備分類能力，結果卻被賦予較高的權值。因此可以看出僅僅使用傳統(tǒng)的TFIDF算法，不能選擇出更有代表性的特征詞。

1.4 TFIDF算法的改進

(1)針對傳統(tǒng)的TFIDF沒有考慮到特征詞在郵件類中的分布情況進行改進。假設垃圾郵件(或者正常郵件)中第i封郵件中出現特征詞t的頻率為ni。

(3)

其中，TF(d,t)表示改進后的TF算法，表示特征項t在郵件類別d中出現的頻率；a(a≥1)是常數，可以通過實驗來確定最佳值。

f(x)=log(x+1)2與f(x)=x的函數圖如圖1所示。

圖1 函數圖

由圖1可知，兩個函數都是遞增函數，即當一封郵件出現的次數越來越大時，TF的疊加也隨之增加。隨著x的增大，f(x)=log(x+1)2的增大會變得平緩，當特征詞在某一類郵件中沒有出現時，TF=0。假設a=2，當一封郵件某一特征詞都只出現1次的時候，TF疊加log(22)=1.3863；當一封郵件某一特征詞出現9次，TF疊加log(102)=4.6052；當一封郵件某一特征詞出現99次，TF疊加log(1002)=9.2103?？梢钥闯?，改進后的TF算法不僅很好地抑制了某個特征詞在特例郵件中大量出現的情況，又能體現出特征詞在郵件中大量出現比在郵件中只出現一次更重要。

(2)針對傳統(tǒng)的TFIDF算法僅僅考慮到特征詞在一類特征詞中的出現情況對其進行改進。當特征詞在不同類別的郵件集中出現的頻率相差較小時，這樣的特征詞應該被賦予較小的權值，相反當特征詞在不同類別的郵件集中出現的頻率相差較大時，應該被賦予較大的權值。在這里引用頻率差的概念：

(4)

通過使用頻率差來反映特征詞分別在正常郵件和垃圾郵件中的差異，對于在兩類郵件出現頻率差不多的特征詞賦予較小的權值，這也符合需要的特征詞的要求，選擇出更加有區(qū)分度的特征詞。

(3)針對IDF的不足提出改進，當某一類郵件中出現特征詞t的郵件數量較大，在另一類郵件中出現的郵件數量較小時，說明特征詞t有很好的區(qū)分能力。改進后的IDF算法如下：

(5)

其中，IDF(d,t)表示特征詞t在郵件類別d中的IDF值；N表示總的郵件數量；A表示郵件類別d中包含特征詞t的郵件數量；B表示包含特征詞t但是不屬于郵件類別d的郵件數量；C表示郵件類別d中不包含特征詞t的郵件數量；D表示不屬于郵件類別d也不包含特征詞t的郵件數量。

假設郵件總數量為N，郵件類別d的郵件數量為Nd，那么不屬于郵件類別d的郵件數量為N-Nd。可以得到:

A+C=Nd

(6)

B+D=N-Nd

(7)

則改進后IDF算法的變形公式為：

(8)

其中，N、Nd是已知值，且A與B分別表示兩個類別的郵件集中出現特征詞t的郵件數量，是互不相關的。因此可以看出，IDF隨著A的增大而增大，IDF隨著B的增大而減小。改進后的IDF算法能夠很好地體現這個思想：特征詞在某一類郵件中出現越多，在另一類郵件中出現越少，這個特征詞應該賦予更高的權值。

結合上面對TFIDF算法的改進，得到最終的TFIDF權值計算公式：

W(d,t)=F(d,t)×IDF(d,t)

(9)

計算特征詞t在垃圾郵件中的TFIDF值時，先對特征詞t在垃圾郵件中的TF與特征詞t在正常郵件中的TF進行相減，再與IDF相乘得到。

2 實驗與分析

2.1 實驗數據

從CCERT提供的中文郵件中隨機抽出5000封正常郵件和5000封垃圾郵件作為訓練集，500封正常郵件和500封垃圾郵件作為測試集。將其等量分為5份，每份訓練集包含2000封郵件(1000封正常郵件，1000封垃圾郵件)，每份測試集包含200封郵件(100封正常郵件，100封垃圾郵件)。

2.2 分類器

文中使用了樸素貝葉斯算法[15-16]，根據樣本訓練構建的特征庫通過貝葉斯公式計算出待分類郵件屬于垃圾郵件和正常郵件的概率。同時比較屬于正常郵件的概率和屬于垃圾郵件的概率，來判斷郵件屬于哪一種類別，這樣能很好地提高分類的準確率。具體公式如下：

P(d|e)=[p1×p2×…×pn]/[p1×

p2×…×pn+(1-p1)×

(1-p2)×…×(1-pn)]

(10)

其中，P(d|e)表示待分類的郵件e屬于郵件類別d的概率；Pi表示特征詞ti在郵件類別d中出現的概率，通過訓練樣本得到。

最終通過比較P(normal|e)與P(trash|e)的大小，來確定待分類郵件e屬于正常郵件還是垃圾郵件。

2.3 實驗評價體系

借助文本分類和信息檢索領域的技術指標來評價郵件分類算法的性能。評價體系見表3。

表3 評價體系

召回率(recall)：也稱查全率，即垃圾郵件的查出率，該指標系數越高，說明找回漏掉的垃圾郵件能力越強，計算公式如下：

(11)

正確率(precision)：也稱查準率，即垃圾郵件的查對率，該指標系數越大，說明合法郵件被誤判的風險越小，計算公式如下：

(12)

F值：是召回率R和正確率P的調和平均值，是召回率和正確率的綜合評判標準，公式如下：

(13)

精確率(accuracy)：對所有郵件的判對率，表明正確判定全部郵件的能力，公式如下：

(14)

其中，X表示測試郵件總的數量。

2.4 實驗結果

分別使用傳統(tǒng)的TFIDF算法和改進后的TFIDF算法對五組樣本集進行實驗，結果如表4～6所示。

表4 CHI統(tǒng)計算法特征提取實驗結果

表5 傳統(tǒng)的TFIDF算法特征提取實驗結果

表6 改進后的TFIDF算法特征提取實驗結果

結合表4和表5，可以看出傳統(tǒng)的TFIDF算法在正確率、F值、精確率上都要高于CHI統(tǒng)計方法，召回率略低于CHI統(tǒng)計方法。說明TFIDF算法適合于進行特征提取。

結合表4、表5和表6，可以看出使用改進后的TFIDF算法，垃圾郵件分類效果比使用CHI統(tǒng)計算法和傳統(tǒng)TFIDF算法的分類效果要好。召回率、正確率、F值、精確率都有一定的提高，這也證明了改進后的TFIDF算法更有效。

3 結束語

TFIDF特征權值計算方法在垃圾郵件過濾中被大量使用，但是仍然存在一些不足之處。文中對其沒有考慮到特征詞在類中分布情況、沒有考慮到特征詞在另一類的出現頻率、低估了頻繁出現的特征詞的權值并高估了出現頻率低的特征詞的權值這三方面進行改進。以樸素貝葉斯算法作為分類器，分別計算測試郵件是正常郵件和垃圾郵件的概率。最終以召回率、正確率、F值、精確率作為評估指標，將改進后的TFIDF和CHI統(tǒng)計特征提取、傳統(tǒng)的TFIDF進行比較。通過實驗數據進行分析，說明改進后的TFIDF算法是有效的。