卜華龍 夏 靜 鄭尚志

（巢湖學(xué)院計(jì)算機(jī)與信息工程學(xué)院，安徽 巢湖 238000）

1 引言

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

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

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

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

2 背景及相關(guān)工作

2.1 偏最小二乘算法PLS

PLS作為一種多線性回歸工具在生物、化學(xué)與信號處理等領(lǐng)域都得到了大量應(yīng)用[7]。PLS主要通過對與響應(yīng)變量間有高度協(xié)方差的預(yù)測變量進(jìn)行非線性轉(zhuǎn)換，以獲得隱藏變量，是一種監(jiān)督學(xué)習(xí)方法。

PLS通過最大化原始數(shù)據(jù)X和目標(biāo)變量y的協(xié)方差構(gòu)造成分變量：

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

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

其中w為PLS成分向量t=X w的權(quán)重，q為標(biāo)量，E、F為殘差。PLS時(shí)間復(fù)雜度為O（npK），為n、p的線性函數(shù)。

2.2 支持向量機(jī)SVM

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

為得到泛化邊境,我們需要最小化SVM的以下目標(biāo)函數(shù)：

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

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

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

3 PLS-SVM算法框架

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

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

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

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

1）冗余特征和弱相關(guān)特征仍然存在；

2）當(dāng)K等于X階時(shí)并沒有削減維數(shù)規(guī)模。

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

圖1 PLSSVM算法流程圖

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

4 實(shí)驗(yàn)方案及結(jié)果分析

4.1 實(shí)驗(yàn)方案

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

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

表1 系統(tǒng)檢測分類表

在實(shí)驗(yàn)設(shè)計(jì)環(huán)節(jié)，我們將訓(xùn)練集C1的9/10用作模型訓(xùn)練，1/10用于測試且迭代10次以選取最佳檢測模型，并給出在驗(yàn)證集C2上的效果?？紤]到本文重點(diǎn)，實(shí)驗(yàn)中除特別標(biāo)注部分，其余參數(shù)都采用默認(rèn)參數(shù)，實(shí)驗(yàn)平臺采用MATLAB。

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

4.2 實(shí)驗(yàn)結(jié)果及分析

2種垃圾郵件檢測算法的檢測準(zhǔn)確率和召回率如表2所示，其中平均分類準(zhǔn)確率用precision表示，平均召回率用recall表示，表2所列為基于C1i訓(xùn)練優(yōu)化模型在驗(yàn)證集C2i上的平均檢測結(jié)果。

表2 檢測結(jié)果

通過對比2種算法及其在3個(gè)數(shù)據(jù)集上的研究發(fā)現(xiàn)：

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

5 結(jié)束語

針對互聯(lián)網(wǎng)時(shí)代用戶面臨查找、過濾和管理海量信息的困難，本文提出線性判別分析和偏最小二乘相結(jié)合的網(wǎng)頁自動分類方法，充分利用這兩種算法的互補(bǔ)特點(diǎn)，保證了較高的識別準(zhǔn)確率，提高算法的穩(wěn)定性。兩個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明，本文方法無論從分類準(zhǔn)確率還是穩(wěn)定性都具有良好的表現(xiàn)。

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

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

[3] 蘇金樹，張博鋒，徐昕.基于機(jī)器學(xué)習(xí)的文本分類技術(shù)研究進(jìn)展[J].軟件學(xué)報(bào)，2006，（9）：1848-1859.

[4] 宋楓溪.統(tǒng)計(jì)模式識別中的維數(shù)削減與低損降維[J].計(jì)算機(jī)學(xué)報(bào)，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] 周志華.機(jī)器學(xué)習(xí)及其應(yīng)用[M].北京：清華大學(xué)出版社，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].計(jì)算機(jī)科學(xué)，2011，（12）：9-13.