陳 俊,劉遵雄

（華東交通大學(xué)信息工程學(xué)院,江西南昌 330013）

1 研究概況

垃圾郵件一般是指沒有經(jīng)過用戶許可,卻被強(qiáng)塞到用戶郵箱的電子郵件。隨著電子郵件成為人民生活中交流的一個(gè)主要方式,垃圾郵件也不斷的泛濫起來,它對(duì)我們的危害也越來越大。其危害主要表現(xiàn)在以下幾個(gè)方面:垃圾郵件的大量的存在占用了很大的網(wǎng)絡(luò)帶寬,甚至可能堵塞網(wǎng)絡(luò)帶寬,使網(wǎng)絡(luò)傳輸效率降低,并且還占用了存儲(chǔ)空間;有的垃圾郵件還會(huì)侵害別人的隱私權(quán),給了黑客有可乘之機(jī);垃圾郵件給世界的經(jīng)濟(jì)造成了巨大的損失;有些垃圾郵件還會(huì)蠱惑人心,騙人錢財(cái),傳播色情等不健康內(nèi)容的垃圾郵件,從而會(huì)對(duì)現(xiàn)實(shí)社會(huì)造成危害,尤其是對(duì)青少年的危害很大。因此,垃圾郵件過濾技術(shù)的研究成為一個(gè)急需解決的問題。

早期的垃圾郵件過濾技術(shù)主要是基于規(guī)則的技術(shù),并且這些規(guī)則都是人工預(yù)先制定的,對(duì)郵件進(jìn)行模式匹配過濾技術(shù)。若在郵件中找到屬于垃圾郵件關(guān)鍵字的個(gè)數(shù)達(dá)到一定閥值則判定此郵件為垃圾郵件?；谝?guī)則的過濾技術(shù)有以下幾個(gè)缺點(diǎn):首先,其自身的工作原理決定了這種過濾技術(shù)總是滯后于垃圾郵件的出現(xiàn)。例如,新的垃圾詞匯出現(xiàn),規(guī)則庫中沒有就不能準(zhǔn)確過濾。其次,它是一種生硬二值判斷,缺少可信的知識(shí)和模糊的判斷。再次,系統(tǒng)需要用戶定制自己的規(guī)則庫,這就對(duì)用戶有較高的要求,同時(shí)需要用戶花大量時(shí)間更新規(guī)則,如果用戶興趣發(fā)生變化,這些規(guī)則也要進(jìn)行很大變動(dòng),因此這種過濾技術(shù)不利于在普通用戶中推廣。還有,為避免郵件中出現(xiàn)垃圾詞匯而被過濾掉,垃圾郵件發(fā)送者常常對(duì)某些關(guān)鍵詞做個(gè)變形,就能輕易騙過過濾器。

隨著模式識(shí)別和機(jī)器學(xué)習(xí)的不斷發(fā)展,現(xiàn)在大多數(shù)的垃圾郵件過濾技術(shù)都是自動(dòng)構(gòu)建過濾模型和對(duì)垃圾郵件進(jìn)行分類。目前大多數(shù)的垃圾郵件分類方法都是原先通用的文本分類方法,分為基于規(guī)則的方法和基于內(nèi)容的分類方法兩大類。主要有貝葉斯方法、支持向量機(jī)、KNN方法、邏輯回歸方法、決策樹方法等。

由于垃圾郵件是高維的數(shù)據(jù),直接對(duì)高維數(shù)據(jù)進(jìn)行分類的話很容易發(fā)生維數(shù)災(zāi)難和錯(cuò)分的問題。因此,對(duì)高維數(shù)據(jù)進(jìn)行降維顯得很重要。現(xiàn)在主要的降維方法有特征提取和特征選擇兩種方法。特征選擇是通過一些標(biāo)準(zhǔn)的統(tǒng)計(jì)方法選擇出對(duì)分類貢獻(xiàn)最大的若干特征,常用的有文檔頻率、χ2統(tǒng)計(jì)和信息增益等方法;而特征抽取是將原始的特征空間投影到低維特征空間,投影后的二次特征是原始特征的線性或者非線性組合。常用的方法有主要成分分析、Fisher線性判別分析、非負(fù)矩陣分解等。

本文使用的降維方法是非負(fù)矩陣分解,非負(fù)矩陣分解方法首先把原始的實(shí)驗(yàn)數(shù)據(jù)分解成B和C數(shù)據(jù)矩陣。而B*C正是原始數(shù)據(jù)的另外一種相似的表達(dá)。B代表了原始數(shù)據(jù)的一個(gè)新的基坐標(biāo),并且這個(gè)基坐標(biāo)的維數(shù)遠(yuǎn)小于原始數(shù)據(jù)的維數(shù)。而C是原始數(shù)據(jù)在新的基坐標(biāo)B上的投影數(shù)據(jù),也可以理解為在B上的權(quán)值系數(shù)。因此我們可以把對(duì)原始的高維的垃圾郵件分類的問題轉(zhuǎn)化為對(duì) C進(jìn)行分類的問題。而C是一個(gè)低維的數(shù)據(jù),所以在對(duì)它進(jìn)行分類的時(shí)候有很多的優(yōu)點(diǎn),并且也很容易對(duì)它進(jìn)行準(zhǔn)確的分類。然后再用支持向量機(jī),邏輯回歸和核邏輯回歸方法對(duì)分解之后的數(shù)據(jù)進(jìn)行分類。

2 特征降維方法

2.1 特征提取

（1）非負(fù)矩陣分解（NMF）。NMF是一種常常用來分解和降維的方法,該方法是通過構(gòu)造B和C來實(shí)現(xiàn)維度的降低。該算法的數(shù)學(xué)表達(dá)式是 V≈BC,它的基本思想是對(duì)非負(fù)的原始數(shù)據(jù)進(jìn)行非負(fù)的分解。并且在功能上它基本上實(shí)現(xiàn)了對(duì)大腦的基于部分感知功能的模擬分析;在它的算法中它采用簡(jiǎn)單有效的迭代規(guī)則很好的保證了分解后數(shù)據(jù)的非負(fù)性;在應(yīng)用上,非負(fù)性的數(shù)據(jù)大量的存在,且非負(fù)分解的結(jié)果具有明確的物理含義,作為一種低秩逼近的算法,它能有效的節(jié)約存儲(chǔ)空間和計(jì)算資源。

為了實(shí)現(xiàn)矩陣的非負(fù)性的分解,首先需要定義一個(gè)差異函數(shù)來描述分解前后的逼近程度,然后才在非負(fù)性約束條件下求解.。最早提出的非負(fù)矩陣分解方法采用傳統(tǒng)的梯度下降算法與加性迭代規(guī)則。有時(shí)也采用乘性迭代規(guī)則,更適合非負(fù)分解的特點(diǎn),也就是在非負(fù)性初始化的基礎(chǔ)上,在迭代過程中能簡(jiǎn)單地保持非負(fù)性,而加性迭代規(guī)則中就需要一個(gè)強(qiáng)制性的將負(fù)值變?yōu)榱愕牟襟E。

將矩陣分解看成如下含加性噪聲的線性混合體模型

其中X代表是原始的數(shù)據(jù),B和C代表是分解之后的結(jié)果,而n和m代表原始矩陣有n行m列,r代表分解之后的行數(shù),E代表的是原始的數(shù)據(jù)和分解后的結(jié)果之間的差距,也就是損失數(shù)據(jù)。一般情況下r的選擇要滿足（n+m）*r＜n*m,因?yàn)橹挥羞@樣才可以保證分解之后的B和C的維數(shù)小于原始矩陣的維數(shù)。從上面的公式可以看出可以把B看成是對(duì)原始矩陣X的一組線性的逼近基向量,而 C就可以看成是在基向量B上面的投影系數(shù)或者投影權(quán)值。這樣的話就實(shí)現(xiàn)了用少量的基向量來表示大量的高維數(shù)據(jù),也就是發(fā)現(xiàn)了原始數(shù)據(jù)之間的潛在關(guān)系。并且可以取得很好的逼近效果。

于是原先的問題就轉(zhuǎn)化成了如何求解B和C。下面是求解B和C的過程。為了求解出B和C的數(shù)值,一般是通過最大似然法來求解。它的過程如下

假設(shè)噪聲服從的是不同的概率分布,就可以得到不同類型的目標(biāo)函數(shù).考慮噪聲是高斯噪聲,也就是

因?yàn)橐玫降慕馐且粋€(gè)局部的最優(yōu)解,所以就需要對(duì)上式進(jìn)行求導(dǎo)。分別對(duì)B和C進(jìn)行求導(dǎo)就可以得到

從而最大似然解就是下面的損失函數(shù)

而這也就是在優(yōu)化過程中不斷的迭代公式,經(jīng)過一定次數(shù)的迭代之后就會(huì)發(fā)現(xiàn)它的結(jié)果會(huì)最終趨于某一個(gè)值,而這個(gè)值也就是所要求的局部的最優(yōu)解。

（2）主要成分分析（PCA）。PCA是一種常用的特征提取的算法,也稱為K2L變換。PCA是將多個(gè)變量通過線性變換以選出較少個(gè)數(shù)重要變量的一種多元統(tǒng)計(jì)分析方法。它在人臉識(shí)別領(lǐng)域得到了廣泛的應(yīng)用,并且提出了特征臉的概念。它首先通過求解原始數(shù)據(jù)矩陣X減去它平均值之后的協(xié)方差矩陣,然后求解協(xié)方差矩陣的特征值和特征向量。最后按照特征值絕對(duì)值的大小對(duì)它所對(duì)應(yīng)的特征向量進(jìn)行排序,選擇出前面幾個(gè)最大特征值所對(duì)應(yīng)的特征向量作為主要成分。因?yàn)閷?duì)應(yīng)最大特征值的特征向量能夠反映數(shù)據(jù)的最大相異性。

（3）偏最小二乘（PLS）。PLS是1983年被提出來的一種綜合考慮自變量對(duì)因變量的一種回歸建模的方法。它的基本思想是,分別在X和Y中提取他們各自的潛在變量t和u,即分別對(duì)X和Y進(jìn)行線性化。并且要求t和u應(yīng)盡可能的攜帶它們各自數(shù)據(jù)表中的變異信息,并且 t和u之間的相關(guān)程度應(yīng)該最大。這樣依次對(duì)X和Y進(jìn)行最大差異潛在變量的提取,直到達(dá)到滿意的精度為止。

2.2 特征選擇

特征選擇也是一種常見的特征降維方法,它是從原始眾多的屬性和特征之中根據(jù)具體的方法選擇出一些對(duì)分類或者表現(xiàn)差異貢獻(xiàn)大的特征,并且選擇出來的特征是原始特征的真子集。在剛開始的文本預(yù)處理階段都會(huì)用到特征選擇的方法。常見的特征選擇的方法有:度量詞條w和文檔類別c之間的相關(guān)程度的CHI方法;選擇有效的特征進(jìn)行相關(guān)反饋的幾率比方法;計(jì)算特征權(quán)值的方法;構(gòu)造樹結(jié)構(gòu)模型的方法和信息增益等方法。

3 垃圾郵件分類算法和技術(shù)

目前存在著很多垃圾郵件的分類方法,其中包括支持向量機(jī)方法,貝葉斯方法,KNN,Ripper方法,決策樹和邏輯回歸等方法。這里主要采用的方法是支持向量機(jī),邏輯回歸和核邏輯回歸方法。

3.1 支持向量機(jī)（Support Vector Machine,SVM）

SVM是一種在機(jī)器學(xué)習(xí)領(lǐng)域比較流行的分類算法,它不但有很好的性能比并且可以通過它特有的核函數(shù)來處理高維的數(shù)據(jù)。所以它在處理二元分類的問題上有很大的優(yōu)點(diǎn),該算法是通過構(gòu)造一個(gè)最大間隔的最優(yōu)分類超平面來實(shí)現(xiàn)分類的目標(biāo)。由于SVM的求解最后轉(zhuǎn)化成二次規(guī)劃問題的求解,因此SVM的解是全局唯一的最優(yōu)解。

3.2 邏輯回歸（Logistic Regression,LR）

邏輯回歸模型是1920美國學(xué)者柏爾和利德（Robert B.Pearl and Lowell J.Reed）提出的,并開始用在人口估計(jì)和預(yù)測(cè)中推廣應(yīng)用,并引起了廣泛的注意。邏輯回歸是研究因變量為二分類或多分類觀察結(jié)果與影響因素（自變量）之間關(guān)系的一種多變量分析方法,屬概率型非線性回歸。邏輯回歸根據(jù)因變量的取值類型不同,又可分為二項(xiàng)分類邏輯回歸、有序分類邏輯回歸和無序多項(xiàng)分類邏輯回歸,其中二項(xiàng)分類邏輯回歸是其他邏輯回歸的基礎(chǔ)。LR的建模過程本身就具有挑選變量的功能,即只有對(duì)因變量貢獻(xiàn)率達(dá)到一定程度的特征變量才能進(jìn)入回歸模型中,對(duì)因變量沒有貢獻(xiàn)或者貢獻(xiàn)很小的特征變量最終會(huì)被剔除。由于Logistic回歸是非線性模型,因此最大似然估計(jì)法經(jīng)常用于模型估計(jì)。

3.3 核邏輯回歸（Kernel Logistic Regression,KLR）

邏輯回歸是一種經(jīng)典的利用線性模型估計(jì)的算法,屬于廣義線性模型方法中的一種,它不需要任何關(guān)于樣本分布的假設(shè)。由邏輯回歸模型的方法是一種線性的方法,所以它在解決一些非線性問題上有很多缺陷,因此就誕生核邏輯回歸。核邏輯回歸把支持向量機(jī)里面的核方法引入到邏輯方法里面。從而可以解決一些非線性的問題,核邏輯回歸經(jīng)常使用的核方法有線性核函數(shù),多項(xiàng)式核函數(shù),RBF核函數(shù)和sigmoid核函數(shù)。

4 試驗(yàn)結(jié)果

本文的垃圾郵件的試驗(yàn)數(shù)據(jù)是從UCI機(jī)器學(xué)習(xí)知識(shí)庫上下載的。這里總共有4 601封電子郵件,其中包括1 813封垃圾郵件和2 788封非垃圾郵件。并且一般的Zero-rule分類方法采用這個(gè)數(shù)據(jù)的準(zhǔn)確率只有60.6%左右。

從UCI機(jī)器學(xué)習(xí)知識(shí)庫中下載的數(shù)據(jù)是以文本形式存儲(chǔ)的,并且每篇郵件都有不同的長度。在這個(gè)數(shù)據(jù)的基礎(chǔ)上排除一些不相關(guān)和一些無關(guān)緊要的屬性之后,得到了轉(zhuǎn)換之后的實(shí)驗(yàn)數(shù)據(jù)。

原始的郵件數(shù)據(jù)是不能被計(jì)算機(jī)識(shí)別的,因此需要選擇郵件數(shù)據(jù)中的某些有代表性的特征來表示原始的郵件數(shù)據(jù)。這里用57個(gè)屬性和一個(gè)是否為垃圾郵件的屬性來表示原來的垃圾郵件數(shù)據(jù),其中57個(gè)屬性中的48個(gè)屬性是郵件中常用詞組,它們是make,address,all,3d,our,over,remove,internet,order,mail,receive,will,people,report,addresses,free,business,email,you,credit,your,font,000,money,hp,hpl,george,650,lab,labs,857,data,415,85,technology,1999,parts,pm,direct,cs,meeting,original,project,re,edu,table,and conference。除了這些詞組以外還有6個(gè)常用的標(biāo)點(diǎn)符號(hào),它們是;,（,[,!,＄,and#。最后還有最后3個(gè)屬性是:平均每個(gè)句子有多少詞組;在郵件中最長的句子有多少詞組和郵件中總共包括多少詞組。最后的那個(gè)屬性中1代表垃圾郵件,0表示不是垃圾郵件。

本實(shí)驗(yàn)主要采用支持向量機(jī),邏輯回歸,核邏輯回歸3種方法來對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行分類。第一部分是直接用上面的3種方法對(duì)垃圾郵件的數(shù)據(jù)進(jìn)行分類,結(jié)果它們的分類準(zhǔn)確率都只有61%左右。表1為直接用分類方法對(duì)垃圾郵件數(shù)據(jù)進(jìn)行分類的結(jié)果。

表1 原始數(shù)據(jù)的分類準(zhǔn)確率和時(shí)間

從上面的實(shí)驗(yàn)結(jié)果可以看出,直接用分類方法對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行分類的話,準(zhǔn)確率只有61%左右。從實(shí)驗(yàn)所用的時(shí)間來看,KLR所花的時(shí)間最長,因?yàn)樗训途S的數(shù)據(jù)投影到高維的空間再進(jìn)行分類,所以它花的時(shí)間比其他的2個(gè)方法要多。

本實(shí)驗(yàn)的第二部分是先用非負(fù)矩陣分解的方法對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行分解之后,然后再用分類方法對(duì)分解之后的數(shù)據(jù)進(jìn)行分類。為了更好的得出不同維度對(duì)原始數(shù)據(jù)的解釋能力,本文特意把原始的57維的實(shí)驗(yàn)數(shù)據(jù)分解為5維,10維,20維,30維,40維。然后在上述分解之后的數(shù)據(jù)基礎(chǔ)上,分別用支持向量機(jī),邏輯回歸和核邏輯回歸三種方法對(duì)它們進(jìn)行分類。表2和表3分別為經(jīng)過特征提取之后的分類準(zhǔn)確率和分類時(shí)間表。

表2 特征提取之后的分類準(zhǔn)確率

表3 特征提取之后的分類時(shí)間

從上面的實(shí)驗(yàn)結(jié)果可以看出,分類的正確率呈現(xiàn)一個(gè)先升后降和分類時(shí)間減少的發(fā)展過程。這是由于維度過低不能完好的表達(dá)原始的所有特征,所以隨著維度的增高有一個(gè)分類準(zhǔn)確率上升和時(shí)間縮短的發(fā)展階段。但是實(shí)驗(yàn)所用的數(shù)據(jù)本身的維度不是很高,所以當(dāng)達(dá)到20維左右就相似的表達(dá)了原始郵件的信息,因此正確率不再上升和時(shí)間不在縮短;并且隨著維度的增加有一個(gè)很小的遞減過程。比較表2和表1可以看出,經(jīng)過非負(fù)矩陣分解特征提取之后的正確率比直接分類的方法有更高的分類準(zhǔn)確率。其中以支持向量機(jī)提高的最多,提高了20%左右;比較表3和表1可以知道分類的時(shí)間縮短了一半左右。

表4是實(shí)驗(yàn)的查全率對(duì)比的一個(gè)表格,其中前面幾列是經(jīng)過NMF分解之后的結(jié)果,最后一列是沒有經(jīng)NMF分解的實(shí)驗(yàn)結(jié)果。

表4 幾種方法查全率的比較

從表4中可以看出,經(jīng)過NMF之后的實(shí)驗(yàn)數(shù)據(jù)比沒有經(jīng)過NMF分解的數(shù)據(jù)有更高的查全率。

5 結(jié)論和今后的工作

通過上面的理論分析和試驗(yàn)的結(jié)果可以知道,經(jīng)過非負(fù)矩陣分解之后的數(shù)據(jù)不但實(shí)現(xiàn)了降維,而且還很好的保留了原始數(shù)據(jù)潛在的特征。這點(diǎn)可以從支持向量機(jī)的試驗(yàn)中很清楚的看出,試驗(yàn)結(jié)果表明經(jīng)過非負(fù)矩陣分解之后的數(shù)據(jù)比原始的實(shí)驗(yàn)數(shù)據(jù)有更高的分類正確率和查全率,并且縮短了分類的時(shí)間。因此它在今后的垃圾郵件的分類中會(huì)有很好的應(yīng)用。

在今后的工作中將從以下幾方面作進(jìn)一步研究:第一,郵件之間的潛在聯(lián)系好多時(shí)候都是非線性的,嘗試尋找一些非線性的特征提取方法。比如核偏最小二乘,核主要成分分析等;第二,在郵件處理中,一般來說,將一封正常郵件錯(cuò)分為垃圾郵件的代價(jià)要遠(yuǎn)遠(yuǎn)大于將垃圾郵件分為正常郵件的代價(jià),這種評(píng)價(jià)機(jī)制被稱為代價(jià)敏感評(píng)價(jià)機(jī)制。可嘗試在今后的工作中引入這種機(jī)制進(jìn)行郵件過濾。

[1]張禾.邏輯回歸法在遙感數(shù)據(jù)特征選擇和分類中的應(yīng)用[J].Science&Technology Association,2007,5（3）:17-18.

[2]盛鵬.基于全文過濾的垃圾郵件防范機(jī)制[D].云南:西南大學(xué),2006:40-45.

[3]曹兆龍.基于支持向量機(jī)的多分類算法研究[D].上海:華東師范大學(xué),2007:15-17.

[4]陳治平,王雷.基于自學(xué)習(xí)K近鄰的垃圾郵件過濾算法[J].計(jì)算機(jī)應(yīng)用,2005,25（12）:7-8.

[5]趙向軍,路梅.垃圾郵件過濾算法研究[J].徐州師范大學(xué)學(xué)報(bào),2006,24（5）:52-55.

[6]劉維湘,鄭南寧,游屈波.非負(fù)矩陣分解及其在模式識(shí)別中的應(yīng)用[J].科學(xué)通報(bào),2006,51（3）:241-250.

[7]GUILLAMET D,VITRIà J,SCHIELE B.Introducing a weighted non-negative matrix factorization for image classification[J].Pattern Recognition Letters,2003,24（14）:2447-2454.

[8]李滔,王俊普,吳秀清.基于特征矢量集的核Logistic回歸[J].小型微型計(jì)算機(jī)系統(tǒng),2007,27（6）:980-985.

[9]喻軍.幾種典型特征抽取方法比較及其在人臉識(shí)別中的應(yīng)用[J].江南大學(xué)學(xué)報(bào),2009,8（5）:543-546.

[10]王鵬鳴,吳水秀,王明文,黃國斌.基于偏最小二乘特征抽取的垃圾郵件過濾[J].中文信息學(xué)報(bào),2008,22（1）:74-79.