基于非負(fù)矩陣分解特征提取的垃圾郵件過濾

陳 俊,劉遵雄

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

1 研究概況

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

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

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

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

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

2 特征降維方法

2.1 特征提取

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

為了實現(xiàn)矩陣的非負(fù)性的分解,首先需要定義一個差異函數(shù)來描述分解前后的逼近程度,然后才在非負(fù)性約束條件下求解.。最早提出的非負(fù)矩陣分解方法采用傳統(tǒng)的梯度下降算法與加性迭代規(guī)則。有時也采用乘性迭代規(guī)則,更適合非負(fù)分解的特點,也就是在非負(fù)性初始化的基礎(chǔ)上,在迭代過程中能簡單地保持非負(fù)性,而加性迭代規(guī)則中就需要一個強制性的將負(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,因為只有這樣才可以保證分解之后的B和C的維數(shù)小于原始矩陣的維數(shù)。從上面的公式可以看出可以把B看成是對原始矩陣X的一組線性的逼近基向量,而 C就可以看成是在基向量B上面的投影系數(shù)或者投影權(quán)值。這樣的話就實現(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ōu)解,所以就需要對上式進行求導(dǎo)。分別對B和C進行求導(dǎo)就可以得到

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

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

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

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

2.2 特征選擇

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

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

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

3.1 支持向量機（Support Vector Machine,SVM）

SVM是一種在機器學(xué)習(xí)領(lǐng)域比較流行的分類算法,它不但有很好的性能比并且可以通過它特有的核函數(shù)來處理高維的數(shù)據(jù)。所以它在處理二元分類的問題上有很大的優(yōu)點,該算法是通過構(gòu)造一個最大間隔的最優(yōu)分類超平面來實現(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）提出的,并開始用在人口估計和預(yù)測中推廣應(yīng)用,并引起了廣泛的注意。邏輯回歸是研究因變量為二分類或多分類觀察結(jié)果與影響因素（自變量）之間關(guān)系的一種多變量分析方法,屬概率型非線性回歸。邏輯回歸根據(jù)因變量的取值類型不同,又可分為二項分類邏輯回歸、有序分類邏輯回歸和無序多項分類邏輯回歸,其中二項分類邏輯回歸是其他邏輯回歸的基礎(chǔ)。LR的建模過程本身就具有挑選變量的功能,即只有對因變量貢獻率達到一定程度的特征變量才能進入回歸模型中,對因變量沒有貢獻或者貢獻很小的特征變量最終會被剔除。由于Logistic回歸是非線性模型,因此最大似然估計法經(jīng)常用于模型估計。

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

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

4 試驗結(jié)果

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

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

原始的郵件數(shù)據(jù)是不能被計算機識別的,因此需要選擇郵件數(shù)據(jù)中的某些有代表性的特征來表示原始的郵件數(shù)據(jù)。這里用57個屬性和一個是否為垃圾郵件的屬性來表示原來的垃圾郵件數(shù)據(jù),其中57個屬性中的48個屬性是郵件中常用詞組,它們是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個常用的標(biāo)點符號,它們是;,（,[,!,＄,and#。最后還有最后3個屬性是:平均每個句子有多少詞組;在郵件中最長的句子有多少詞組和郵件中總共包括多少詞組。最后的那個屬性中1代表垃圾郵件,0表示不是垃圾郵件。

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

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

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

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

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

表3 特征提取之后的分類時間

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

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

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

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

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

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

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

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

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

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

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

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

[6]劉維湘,鄭南寧,游屈波.非負(fù)矩陣分解及其在模式識別中的應(yīng)用[J].科學(xué)通報,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].小型微型計算機系統(tǒng),2007,27（6）:980-985.

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

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