基于特征提取的垃圾郵件檢測

卜華龍 夏 靜 鄭尚志

（巢湖學院計算機與信息工程學院，安徽 巢湖 238000）

1 引言

隨著互聯網技術的深入普及，電子郵件（EMail）憑借其方便等獨特特點成為常用的聯系方式。EMail在帶給人們帶來方便的同時，也伴隨著大量垃圾郵件的入侵。近年來，很多單位和個體在未經郵件用戶同意的前提下，利用群發軟件等工具大量發送廣告信息，既造成用戶的不滿，也浪費了網絡資源，其中的淫穢和信息還會嚴重損害青少年的健康成長[1，2]。因此，垃圾郵件檢測已經成為當前網絡研究重要方向之一。

垃圾郵件過濾本質上可以看作文本分類問題，文本分類通過文本的內容，根據分類算法將文本歸至某種類別,通過采樣網絡文本數據可以發現樣本數據特征間存在大量的相關性，表現為既影響檢測模型的響應時間，也干擾分類器的正確分類[3]。例如文本分類中其特征空間經常高達幾萬維且很多特征維值為0，這種高維性和稀疏性的特性會嚴重影響分類效果，從而向傳統分類算法提出嚴重挑戰[4]。

維數約簡算法通過將數據的維數降低到一個合理范疇并盡可能多的保留原始的信息達到提高分類效率目的，特征提取是維數約簡的典型做法之一，其核心是通過采用某種變換將原始高維數據映射至低維空間[5]。偏最小二乘法（Partial least square，PLS）作為一種常見的特征抽取方法能夠保留所有的解釋變量或樣本點，在吸收標簽變量的前提下，能定性解釋預測且對解釋變量個數多且樣本量少時保持很高的效率[6]。

基于以上原因，本文提出先PLS特征抽取并利用遺傳算法尋找其降維空間最優子集，再通過SVM算法的PLS-SVM垃圾郵件檢測算法。

2 背景及相關工作

2.1 偏最小二乘算法PLS

PLS作為一種多線性回歸工具在生物、化學與信號處理等領域都得到了大量應用[7]。PLS主要通過對與響應變量間有高度協方差的預測變量進行非線性轉換，以獲得隱藏變量，是一種監督學習方法。

PLS通過最大化原始數據X和目標變量y的協方差構造成分變量：

wk其主要約束條件：wTSXw=0，1≤ i＜ j， 因此 PLS 核心在于計算最優權重向量 wi=（i=1，…，K）。

具體來說，為求得變換后的成分[t1，t2，…tk]，PLS將原始數據X和y（分類標簽）分解，從而得到X與y的雙線性表示：

其中w為PLS成分向量t=X w的權重，q為標量，E、F為殘差。PLS時間復雜度為O（npK），為n、p的線性函數。

2.2 支持向量機SVM

支持向量機（SVM）于上世紀90年代由Vapnik及其合作者提出,已經廣泛研究和應用于數據挖掘、模式識別、生物信息處理等領域[8]。

為得到泛化邊境,我們需要最小化SVM的以下目標函數：

其中 yi=（＜ w·xi＞ +b）≥1-ξi，i=1， …，e；松弛變量ξi當問題不可行時被引入，常數C＞0是一個懲罰函數，C越大表示更大的誤差。

接下來，通過建立Lagrangian并使用Karush-Kuhn-Tucker（KTT）互補性條件，可以將以上問題轉化為求最優化值。利用KKT條件，我們定義那些使約束非零的Lagrangian算子ais相應的點為支持向量（sv），由此我們可以將分類超平面表示成a和b：

這里 K（xi，x），作為一個核函數以處理非線性問題，高斯核函數為常用核函數。

3 PLS-SVM算法框架

垃圾郵件通過檢測模型將正常郵件和垃圾郵件分開，因此可以看作一個二分文本檢測問題。垃圾郵件檢測的一般模式為：

1）將正常和垃圾郵件數據集X預處理，提取分類特征[t1，t2，…，tK]，達到維數約簡的目的；

2）將待測郵件（未標記）投影到[t1，t2，…，tK]，得到新的數據表示X′，再利用分類器對X′進行檢測。

由此可見，垃圾郵件檢測主要依賴于預處理的效果和學習器的效果。本文采用PLS算法，如 2.1 所述，PLS 需要確定[t1，t2，…，tK]的特征個數K，若K等于X階時，其規模等同于原始數據，因此能較好保持數據的內部信息，但也面臨以下問題：

1）冗余特征和弱相關特征仍然存在；

2）當K等于X階時并沒有削減維數規模。

因此，我們需要選擇合適的PLS投影特征子集規模，傳統做法有用戶根據經驗決定、交叉驗證或計算回歸擬合程度[9]等，本文考慮到遺傳算法的全局尋優性，采用遺傳算法（GA）[10]解決特征子集選取問題。圖1給出PLS-SVM算法的主要流程。

圖1 PLSSVM算法流程圖

首先利用PLS將原始特征空間變化至新特征空間，再利用GA確定此特征空間的主要成分，并通過分類器SVM以提供反饋 （wrapper類方法），即主要利用分類器的分類表現驗證選擇特征子集的有效性以及挑選合適的預測模型。

4 實驗方案及結果分析

4.1 實驗方案

本文將PLS-SVM算法應用于垃圾郵件檢測，數據集來自于中文郵件語料集（Spamand ham collected during July 2005），該數據集有9042個標記為正常郵件的樣本和20308個標記為垃圾郵件的樣本，樣本中已經去除郵件頭等信息，只保留郵件主題和內容。我們首先合并標記為垃圾郵件和正常郵件的數據集并打亂結構得到數據集C，再將C分成訓練集C1和驗證集C2，為避免樣本不均勻分布以及驗證小樣本對算法的影響，將數據集C1和C2再拆分成 3個子集 C11、C12、C13和 C21、C22、C23分開討論。

為評價檢測效果，我們采用常用的性能評價方法：召回率R與準確率P[11]。設垃圾郵件個數為N，垃圾郵件檢測分類如表1所示。

表1 系統檢測分類表

在實驗設計環節，我們將訓練集C1的9/10用作模型訓練，1/10用于測試且迭代10次以選取最佳檢測模型，并給出在驗證集C2上的效果。考慮到本文重點，實驗中除特別標注部分，其余參數都采用默認參數，實驗平臺采用MATLAB。

為了對比研究，我們設計了1）不使用特征抽取算法的SVM法；2）使用PLS降維的PLSSVM方法。

4.2 實驗結果及分析

2種垃圾郵件檢測算法的檢測準確率和召回率如表2所示，其中平均分類準確率用precision表示，平均召回率用recall表示，表2所列為基于C1i訓練優化模型在驗證集C2i上的平均檢測結果。

表2 檢測結果

通過對比2種算法及其在3個數據集上的研究發現：

使用PLS特征提取后的檢測準確率普遍高于沒有使用PLS的結果。如前所述，由于提取特征前干擾信息多，模型的穩定性和預測能力不理想， 單純的SVM無法在多個數據集上取得滿意檢測效果，模型不穩定。經過PLS-SVM降維和檢測后，模型的穩定性包括預測能力得到較大幅度提高。實驗表明特征抽取起到了消除冗余和無關特征的作用，且降維后特征信息更有利于垃圾郵件檢測，驗證了本文算法對檢測效果的作用。

5 結束語

針對互聯網時代用戶面臨查找、過濾和管理海量信息的困難，本文提出線性判別分析和偏最小二乘相結合的網頁自動分類方法，充分利用這兩種算法的互補特點，保證了較高的識別準確率，提高算法的穩定性。兩個標準數據集的實驗結果表明，本文方法無論從分類準確率還是穩定性都具有良好的表現。

[1] 曹麒麟 ，張千里.垃圾郵件與反垃圾郵件技術[M].北京：人民郵電出版社，2003.

[2] 陳凱.反垃圾郵件技術的研究與實踐[D].北京：北京郵電大學，2006.

[3] 蘇金樹，張博鋒，徐昕.基于機器學習的文本分類技術研究進展[J].軟件學報，2006，（9）：1848-1859.

[4] 宋楓溪.統計模式識別中的維數削減與低損降維[J].計算機學報，2005，（28）：1915-1922.

[5] Guyon， S.Gunn， Feature Extraction[M].UK， Springer Verlag，2006.

[6] A.L.Boulesteix， K.Strimmer， Partial Least Squares：A Versatile Tool for the Analysis of High-Dimensional Genomic Data[J].Briefings in Bioinformatics，2006，（7）：32-44.

[7] I.S.Helland， On the structure of partial least squares regression， Communications in statistics[J].Simulation and computation，1988，（17）：581-607.

[8] 周志華.機器學習及其應用[M].北京：清華大學出版社，2006：170-188.

[9] G.Z.Li，H.L.Bu，M.Q.Yang，etc.，Selecting subsets of newly extracted features from PCA and PLS in microarray data analysis[J].BMC Genomics，2008，（9）：179-183.

[10] I.Guyon,A.Elisseef,An introduction to variable and feature selection[J].Journal of Machine Learning Research，2003，3：1157-1182.

[11] 袁鼎榮，鐘寧，張師超.文本信息處理研究述評[J].計算機科學，2011，（12）：9-13.