陶 峰，湯 鯤，程 光

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

0 引 言

中國(guó)互聯(lián)網(wǎng)協(xié)會(huì)反垃圾郵件中心發(fā)表的《2014年第四季度中國(guó)反垃圾郵件狀況調(diào)查報(bào)告》，根據(jù)調(diào)查結(jié)果估算，用戶平均每周接收到的電子郵件數(shù)量為35.0封，平均每周接收到的垃圾郵件數(shù)量為14.3封，收到垃圾郵件的比例是41.0%。根據(jù)中國(guó)互聯(lián)網(wǎng)協(xié)會(huì)反垃圾郵件中心的調(diào)查顯示，有超過50%的用戶因?yàn)榉蠢]件功能弱而影響對(duì)電子郵件的滿意程度。因此，如何實(shí)現(xiàn)對(duì)這類垃圾郵件的準(zhǔn)確過濾成為近年來(lái)熱門的研究課題。

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

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

1 特征提取算法及其改進(jìn)

1.1 CHI統(tǒng)計(jì)算法

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

(1)

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

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

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

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

(2)

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

1.3 TFIDF算法存在的問題

TFIDF算法是將郵件集作為一個(gè)整體來(lái)進(jìn)行處理，并沒有考慮到特征詞的分布問題，明顯存在以下三點(diǎn)不足：

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

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

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

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

表1 特征詞分布表

從表1可以看出，特征詞t1在垃圾郵件中均勻分布，說(shuō)明特征詞對(duì)垃圾郵件的分類能力較強(qiáng)。t1特征詞沒有在正常郵件中出現(xiàn)，說(shuō)明對(duì)正常郵件沒有分類能力。特征詞t2在垃圾郵件中出現(xiàn)頻率很高，但是集中在個(gè)別郵件中，說(shuō)明特征詞t2的分類能力較弱。t3在垃圾郵件和正常郵件集中均勻分布，幾乎沒有分類能力。

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

表2 傳統(tǒng)TFIDF權(quán)值計(jì)算結(jié)果

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

1.4 TFIDF算法的改進(jìn)

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

(3)

其中，TF(d,t)表示改進(jìn)后的TF算法，表示特征項(xiàng)t在郵件類別d中出現(xiàn)的頻率；a(a≥1)是常數(shù)，可以通過實(shí)驗(yàn)來(lái)確定最佳值。

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

圖1 函數(shù)圖

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

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

(4)

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

(3)針對(duì)IDF的不足提出改進(jìn)，當(dāng)某一類郵件中出現(xiàn)特征詞t的郵件數(shù)量較大，在另一類郵件中出現(xiàn)的郵件數(shù)量較小時(shí)，說(shuō)明特征詞t有很好的區(qū)分能力。改進(jìn)后的IDF算法如下：

(5)

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

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

A+C=Nd

(6)

B+D=N-Nd

(7)

則改進(jìn)后IDF算法的變形公式為：

(8)

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

結(jié)合上面對(duì)TFIDF算法的改進(jìn)，得到最終的TFIDF權(quán)值計(jì)算公式：

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

(9)

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

2 實(shí)驗(yàn)與分析

2.1 實(shí)驗(yàn)數(shù)據(jù)

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

2.2 分類器

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

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

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

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

(10)

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

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

2.3 實(shí)驗(yàn)評(píng)價(jià)體系

借助文本分類和信息檢索領(lǐng)域的技術(shù)指標(biāo)來(lái)評(píng)價(jià)郵件分類算法的性能。評(píng)價(jià)體系見表3。

表3 評(píng)價(jià)體系

召回率(recall)：也稱查全率，即垃圾郵件的查出率，該指標(biāo)系數(shù)越高，說(shuō)明找回漏掉的垃圾郵件能力越強(qiáng)，計(jì)算公式如下：

(11)

正確率(precision)：也稱查準(zhǔn)率，即垃圾郵件的查對(duì)率，該指標(biāo)系數(shù)越大，說(shuō)明合法郵件被誤判的風(fēng)險(xiǎn)越小，計(jì)算公式如下：

(12)

F值：是召回率R和正確率P的調(diào)和平均值，是召回率和正確率的綜合評(píng)判標(biāo)準(zhǔn)，公式如下：

(13)

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

(14)

其中，X表示測(cè)試郵件總的數(shù)量。

2.4 實(shí)驗(yàn)結(jié)果

分別使用傳統(tǒng)的TFIDF算法和改進(jìn)后的TFIDF算法對(duì)五組樣本集進(jìn)行實(shí)驗(yàn)，結(jié)果如表4～6所示。

表4 CHI統(tǒng)計(jì)算法特征提取實(shí)驗(yàn)結(jié)果

表5 傳統(tǒng)的TFIDF算法特征提取實(shí)驗(yàn)結(jié)果

表6 改進(jìn)后的TFIDF算法特征提取實(shí)驗(yàn)結(jié)果

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

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

3 結(jié)束語(yǔ)

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