改進的互信息特征選擇方法在垃圾郵件檢測中的應用

王禾清

摘要：隨著電子郵件數(shù)據(jù)量的不斷增大，特征降維成為垃圾郵件檢測研究中不可缺少的一環(huán)。目前常見的特征選擇方法往往針對的是多分類問題，未能針對二分類問題進行特殊化的處理。因此，該文對傳統(tǒng)的互信息特征選擇方法進行了改進。除了針對其缺少詞頻信息，引入詞頻因子外，還針對二分類問題，引入了特征貢獻比的概念。實驗證明，采用改進的互信息特征選擇方法大大提高了垃圾郵件的檢測效果。

關(guān)鍵詞：垃圾郵件檢測；特征選擇；互信息；詞頻因子；特征貢獻比

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2017）14-0163-04

近些年，隨著電子郵件文本數(shù)據(jù)規(guī)模的不斷擴大，特別是特征維數(shù)的增大，采用向量空間模型表示的樣本數(shù)據(jù)特征維數(shù)高且稀疏，在進行數(shù)據(jù)處理時占用了大量的存儲空間。并且依據(jù)這些數(shù)據(jù)建立數(shù)學模型時，數(shù)據(jù)分析器很容易陷入過學習的狀態(tài)，得到的模型泛化效果差。為了緩解“維數(shù)災難”帶來的種種問題，對原始數(shù)據(jù)進行降維處理成了文本數(shù)據(jù)分析過程中必不可少的一個環(huán)節(jié)。

目前特征降維的措施可以分為兩類，一類是特征選擇（fea-ture selection），還有一類是特征提取（feature extraction）。但是比較特征選擇和特征提取可以發(fā)現(xiàn)，前者使用起來比較簡單，便于直觀地理解所選擇的特征；而后者相對前者而言，它由于考慮了特征詞之間的關(guān)聯(lián)性，通過映射的方式，將原始高維特征空間中的數(shù)據(jù)投影到低維空間中，保留了樣本中的重要信息。但相較于特征選擇來說，其計算方法比較復雜，不易于理解，并且得到的結(jié)果也沒有前者直觀，容易理解。

特征選擇研究的重點就是找到用來衡量特征詞重要性的評估函數(shù)。文獻[1-6]中對其中的一些方法進行了比較分析，發(fā)現(xiàn)這些方法互有優(yōu)缺點。如基于文檔頻率的特征選擇方法，它的假設前提是出現(xiàn)頻率低的特征所含的信息量較小。但是這個假設是片面的，所以在實際應用中，頻率高的特征詞可以是一些停用詞，如中文郵件中常見的“你”、“我”等代詞。信息增益從信息論的角度出發(fā)，以某個特征針對分類系統(tǒng)的信息增量作為評價標準來選擇有效特征，構(gòu)成特征子集。但是它只考慮了某個特征對整個數(shù)據(jù)集的有效性，而忽略了某些只針對于某個類別的特征?；バ畔⒊Ｓ糜诤饬孔兞恐g的相關(guān)性。在處理特征選擇的問題中，它則用來度量某個特征詞與某個類別之間的相關(guān)性。當某個特征詞與某個類別的相關(guān)性很大的時，這個詞的互信息值就會很大，反之，這個詞的互信息值就會很小?；バ畔⒌牟蛔阒幵谟谒雎栽~頻信息，受特征詞的邊緣概率影響較大，容易偏向低頻詞。卡方統(tǒng)計量是通用計算實際值與理論值的偏差來評估理論的正確與否。在進行文本特征選擇時，一般首先假設“某個特征詞與某個類不相關(guān)”，然后計算該假設卡方統(tǒng)計量。其值越大，說明原假設與正確結(jié)果的錯差越大，因此與原假設相反的結(jié)果成立的可能性就越高。但是由于它的計算中只考慮該特征詞是否出現(xiàn)在樣本文本中，忽略了其出現(xiàn)的次數(shù)，同互信息一樣，夸大低頻詞的作用。期望交叉熵則是一種對特征詞與樣本集之間關(guān)聯(lián)度的權(quán)衡。它通過計算存在某個特征詞的條件下類別概率分布與不存在某個特征詞條件下的類別概率分布之間的差值來評估特征詞對于樣本集的重要程度。如果某個特征詞的期望交叉熵越大，則其對樣本集的類別分布的影響就越大。它與信息增益的不同之處在于只計算某個特征詞未出現(xiàn)在樣本中的情況，忽略了特征詞不出現(xiàn)的情況。

上述特征選擇方法除了上述提到的缺點之外，還普遍存在一個問題，即這些傳統(tǒng)的特征選擇方法主要針對的是多分類問題，未對文本分類中存在的特殊情況，如垃圾郵件檢測等二分類問題做特殊化的處理。因此如何對傳統(tǒng)的特征選擇方法進行改進，使之能夠更好地處理垃圾郵件檢測這種二分類問題是本文研究的重點。

本文以首先對郵件特征選擇的特點進行了分析，然后在傳統(tǒng)互信息特征選擇方法的基礎上提出一種改進的互信息特征選擇方法，隨后通過實驗驗證該方法的可行性，最后對全文進行了總結(jié)。

1郵件特征選擇的特點

垃圾郵件過濾問題實際上是一個典型的文本二分類問題：假設存在一個郵件樣本d，經(jīng)過分詞處理之后，文本d被表示為由n個特征詞（設為t₁，t₂，t₃，…，t_n）構(gòu)成的集合。垃圾郵件過濾即是判定d是否屬于C_k（k=1，2）的過程，其中G表示垃圾郵件類，C₂表示非垃圾郵件類。

為了能夠清晰地顯示出郵件數(shù)據(jù)集中一些特征詞與類別之間的關(guān)系，本節(jié)特別挑選了一些類別相關(guān)性比較高的詞和類別相關(guān)性比較弱的詞，統(tǒng)計這些特征在各類間的分布情況，如圖1和圖2所示。這兩個圖是根據(jù)從CCERT提供的中文垃圾郵件語料庫提取出的某些類別區(qū)分能力較強和類別區(qū)分能力較弱的特征在垃圾郵件中和非垃圾郵件中的分布所繪制的（其中垃圾郵件4000封，非垃圾郵件4000封）。圖中x軸坐標表示特征，Y軸坐標表示特征在不同類別中的文檔頻率（DF）。

分析圖1和圖2可以發(fā)現(xiàn)，與垃圾郵件類別相關(guān)的特征，如發(fā)票、公司、廣告等。它們在垃圾郵件類中分布較為密集，而在非垃圾郵件類中分布較為稀疏。同理，與非垃圾郵件類別相關(guān)的特征，如水木社區(qū)、感情、發(fā)信站等。它們在非垃圾郵件類中分布較為密集，而在垃圾郵件類中分布較為稀疏。但是與兩個類別都不相關(guān)的特征，如汽車行業(yè)、卡通、體育場、血液、謝謝、地方等。這些特征的分布對類別不敏感，在垃圾郵件類和非垃圾郵件類中都呈現(xiàn)較為稀疏狀態(tài)。

文獻認為在文本分類中，樣本特征詞的頻度、集中度以及分散度對分類效果都有著極其重要的影響。

其中，頻度指的是特征詞在某一類別中出現(xiàn)的次數(shù)。通常某特征詞在某一類別中出現(xiàn)的次數(shù)越多，該特征詞與此類別的相關(guān)性就越大，越應該被選人最優(yōu)特征子集中。特征詞頻度其可以用詞頻TF（Term Frequency）來表示。

集中度通常指含有此特征詞的類別個數(shù)。通常認為包含某特征詞出現(xiàn)的類別越少，越說明該特征詞與這些類別之間存在很強的關(guān)聯(lián)性。

分散度指的是某類別含有某特征詞的文檔數(shù)目。通常分散度越高，越說明該特征詞均勻分布在某類別中，該特征詞也越能代表此類。

它們?nèi)咧g不是一種松散的關(guān)系，而是一種相互補充、相互促進的關(guān)系。如果存在這樣一個特征詞，盡管其頻度很高，但是它頻繁出現(xiàn)在不同的類別中，因此其并不能很好地代表某一類別，典型的如停用詞。還有一些特征詞，它確實只出現(xiàn)在單一類別中，但是它的頻度很低，與類別的相關(guān)性并不高，因此它也不應該被選人最優(yōu)特征子集，典型的如低頻詞。

從圖1中可以發(fā)現(xiàn)，“發(fā)票”、“公司”、“廣告”等特征詞頻度較高，分散度也較高。其集中分布于垃圾郵件中，在非垃圾郵件中分布較少，所以在做特征選擇時優(yōu)先選擇這些特征加入最優(yōu)特征子集；“水木社區(qū)”、“感情”、“發(fā)信站”等特征詞雖然詞頻不高，分散度亦不高，但它們集中分布于非垃圾郵件中，所以在做特征選擇時也會優(yōu)先選擇。但對于圖2中的特征詞，盡管其中存在某些特征詞頻不低，并且其分散度也很高，但其不僅在垃圾郵件類別中表現(xiàn)出較為集中的狀態(tài)，同樣也集中出現(xiàn)在非垃圾郵件類別中，使得其在不同類別中出現(xiàn)的比例呈現(xiàn)一種均衡的狀態(tài)。對于這樣的特征詞，它們對分類效果的影響不大，不應該被選人最優(yōu)特征子集。因此，如何從特征詞的頻度、集中度以及分散度三個角度出發(fā)，改進傳統(tǒng)的特征選擇方法，是研究的重點。

2改進的互信息特征選擇方法

互信息方法作為常用的特征選擇方法，有著實現(xiàn)簡單，時間復雜度相對較低，易于理解的優(yōu)點。但是它也存在一些不足，如前面所提及的受某個特征詞的邊緣概率影響較大，未能有效地引入特征詞的詞頻信息，對特征詞的集中度也未能進行很好的評估等等。

針對互信息存在的不足，很多研究者提出多種改進措施，比如在傳統(tǒng)互信息方法上引入若干參數(shù)進行調(diào)節(jié)，以達到改進互信息方法的目的。還有將互信息方法與其他特征選擇方法相結(jié)合，進行優(yōu)勢互補，以期達到更優(yōu)的效果。但是這些改進方法并沒有對特征詞與類別之間的正、負相關(guān)性進行很好的評估，并且這些方法一般針對的是多分類問題，未能對于二分類問題進行特殊的處理。因此，針對目前各種互信息的改進型算法存在的不足，本小節(jié)在互信息方法除了引入詞頻信息外來降低在特征選擇過程中特征詞的邊緣概率對特征詞的影響，還針對二分類以及特征集中度問題，提出一種基于特征貢獻比的改進互信息特征選擇方法。

2.1互信息特征選擇方法