基于單核和組合核函數(shù)在垃圾郵件過(guò)濾中的比較應(yīng)用

吳陳，孫偉

（江蘇科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 鎮(zhèn)江 212003）

支持向量機(jī)（Support Vector Machine，又稱(chēng)支撐向量機(jī)）是Cortes和Vapnik在1995年開(kāi)始提出來(lái)的[1]，是建立在統(tǒng)計(jì)學(xué)習(xí)理論[1]的VC維理論和考慮將風(fēng)險(xiǎn)的結(jié)構(gòu)降低到最小的原理上，對(duì)特定有限訓(xùn)練樣本在學(xué)習(xí)精度和學(xué)習(xí)能力之間尋求到最佳折衷點(diǎn)，從中獲取最好的推行的能力，即常說(shuō)的范化能力。支持向量機(jī)的優(yōu)勢(shì)主要體現(xiàn)在解決非線性、小樣本及高維模式識(shí)別[1]中，并可以推廣到回歸分析[2]、模式識(shí)別[3]等其他機(jī)器學(xué)習(xí)中。因此，支持向量機(jī)已逐漸成為一個(gè)熱門(mén)的研究。

過(guò)濾垃圾郵件，本質(zhì)上能夠當(dāng)做一個(gè)二值的分類(lèi)的情況來(lái)處理，是一種特殊的文本分類(lèi)問(wèn)題[4]。垃圾郵件過(guò)濾的方法有許多，比較常見(jiàn)是黑白名單過(guò)濾、決策樹(shù)、KNN等。近年來(lái)，支持向量機(jī)在垃圾郵件過(guò)濾中已有介紹和相應(yīng)的研究。通過(guò)引入核函數(shù)的支持向量機(jī)，解決了高維不可分問(wèn)題和線性文本分類(lèi)的問(wèn)題。所以考慮將支持向量機(jī)用于垃圾郵件過(guò)濾是可行且會(huì)取得較好的過(guò)濾效果。

1 文本預(yù)處理

為了使郵件能夠被SVM訓(xùn)練和分類(lèi)，預(yù)先就要將中文郵件轉(zhuǎn)化成SVM能夠識(shí)別的向量模式。郵件向量化模塊就會(huì)涉及到文本的預(yù)處理。其中主要包括中文分詞、去停頓詞、特征項(xiàng)提取、詞頻統(tǒng)計(jì)和文本向量化。通過(guò)漢語(yǔ)詞法分析系統(tǒng)ICTCLA對(duì)需要處理的樣本進(jìn)行中文分詞，利用shell腳本，對(duì)批量需要處理的郵件去停頓詞、特征項(xiàng)提取和詞頻統(tǒng)計(jì)。采用TF-IDF將文本向量化。

那么TF-IDF量化公式為：

ftik表示tk在文檔中出現(xiàn)過(guò)的次數(shù)，N表示所以樣本的數(shù)量，nk表示輸入的tk的文檔頻數(shù)。

2 支持向量機(jī)

2.1 支持向量機(jī)的基本原理

支持向量機(jī)的發(fā)展最初是通過(guò)分析線性可分的情況下，尋找最優(yōu)分類(lèi)面。對(duì)于二維問(wèn)題，在正常情況下，如果一個(gè)線性函數(shù)可以從沒(méi)有錯(cuò)誤的數(shù)據(jù)樣本中完全分離的，那么數(shù)據(jù)可以被定義為線性可分，否則它是線性不可分。對(duì)于文本分類(lèi)問(wèn)題，尤其是中文文本，大多數(shù)不能簡(jiǎn)單的看成線性可分，最好作為線性不可分的方法處理。通過(guò)引入松弛變量和相應(yīng)變換函數(shù)--核函數(shù)來(lái)解決線性不可分和維度問(wèn)題是SVM得到廣泛研究的重點(diǎn)和精華。

SVM在主要是通過(guò)構(gòu)造最佳分類(lèi)超平面，從而轉(zhuǎn)化成凸二次規(guī)劃問(wèn)題來(lái)求解。下圖為SVM構(gòu)造的最佳分界面。

圖1 SVM線性可分最優(yōu)分界面Fig.1 The optimal interface of linearly separable for SVM

目標(biāo)函數(shù)：

約束條件：

那么定義如下Lagrange系數(shù)，將所求目標(biāo)變換成對(duì)和求Lagrange函數(shù)的極小值，即

其中ai為L(zhǎng)agrange系數(shù)。分別對(duì)ω和b求偏微分，然后可將原來(lái)的目標(biāo)問(wèn)題變換為所熟悉的凸二次規(guī)劃的對(duì)偶問(wèn)題來(lái)求解：

ai≥0 i=1，2，…，k

設(shè) a*是上述問(wèn)題的最優(yōu)解，根據(jù) a*可求出ω*和b*從而最終求出最佳分類(lèi)函數(shù)：

2.2 核函數(shù)

為了解決高維線性不可分，支持向量機(jī)經(jīng)過(guò)一定的變換，即通過(guò)核函數(shù)來(lái)解決。核函數(shù)的基本作用在于將處于低維空間內(nèi)線性不可分的問(wèn)題通過(guò)內(nèi)積函數(shù)（即核函數(shù)）映射到高維的特征空間中去，從而可以在高維空間中得到內(nèi)線性可分的樣本。正常情況下只要滿(mǎn)足了Mercer條件[5]的函數(shù)，都可以定義為核函數(shù)來(lái)使用。核函數(shù)的定義：

從核函數(shù)的定義中可以看出，對(duì)于非線性問(wèn)題，最優(yōu)分類(lèi)面采用內(nèi)積的的方法而不是點(diǎn)積，相對(duì)于將原來(lái)的原始空間變換到了一個(gè)新的特征空間。

則原來(lái)的最佳分類(lèi)函數(shù)變成：

本文采用以下兩種核函數(shù)：

多項(xiàng)式（Poly）核函數(shù)：

徑向基（RBF）核函數(shù)：

2.3 組合核函數(shù)

核函數(shù)可分為全局核和局部核[6]。具有全局核特征的核函數(shù)的泛化能力相對(duì)比較強(qiáng)，而具有局部核特征的核函數(shù)具有很好的學(xué)習(xí)能力?？沙浞掷眠@兩種核函數(shù)各自?xún)?yōu)點(diǎn)，將這兩種核函數(shù)通過(guò)一定的參數(shù)，然后組合，使得組合起來(lái)的混合核函數(shù)支持兩個(gè)單核的優(yōu)點(diǎn)。兩個(gè)符合Mercer定理的條件的核函數(shù)之和如果還符合該定理，則就可以作為核函數(shù)。多項(xiàng)式（Poly）核函數(shù)都是典型的全局核函數(shù)，而徑向基核（RBF）函數(shù)是局部核函數(shù)。通過(guò)實(shí)驗(yàn)也表明，單個(gè)核函數(shù)對(duì)垃圾郵件的過(guò)濾效果不及組合核函數(shù)的效果。

則新的混合核的組成公式為：

其中 KL（x，y）表示局部核函數(shù)，KG（x，y）表示全局核函數(shù)。

兩個(gè)單核組合成的混合核函數(shù)在許多方面已經(jīng)投入實(shí)驗(yàn)和應(yīng)用，并取得了較好的效果。文獻(xiàn)[7]中，利用組合核函數(shù)，進(jìn)行定量分析，并對(duì)股票市場(chǎng)發(fā)展的趨勢(shì)進(jìn)行了預(yù)測(cè) ；文獻(xiàn)[8]中利用組合核函數(shù)SVM進(jìn)行了人臉識(shí)別實(shí)驗(yàn)，并取得較好的效果。利用組合核函數(shù)應(yīng)用于沙城暴預(yù)警，文獻(xiàn)[9]中提出合理的組合方法，并且證明了利用組合核函數(shù)提高了沙塵暴預(yù)警的精度。

3 實(shí)驗(yàn)與分析

3.1 平臺(tái)與數(shù)據(jù)集

實(shí)驗(yàn)環(huán)境筆記本一臺(tái)，基本配置如下：Windows7系統(tǒng)、3GHz CPU、2G 內(nèi)存；ICTCLASVersion1.0；VMwareWorkstationUbuntu；LibSVM數(shù)據(jù)包2.89版；Visual Studio2013。

實(shí)驗(yàn)數(shù)據(jù)采納希臘學(xué)者Androutsopoulos所提供的PU語(yǔ)料庫(kù)。其中包括PU1、PU2、PU3和PU4 4個(gè)語(yǔ)料信息。具體語(yǔ)料庫(kù)信息如表1所示。

表1 PU語(yǔ)料庫(kù)信息Tab.1 The information of PU

本次垃圾郵件評(píng)價(jià)使用的準(zhǔn)確率（P）、錯(cuò)誤率（E）。

其中TN表示正常郵件的總數(shù)；TL表示垃圾郵件的個(gè)數(shù)。

3.2 仿真實(shí)驗(yàn)與結(jié)果

1）組合核函數(shù)模型和參數(shù)的選擇

多項(xiàng)式（Poly）核函數(shù)泛化能力強(qiáng)，且階數(shù)越低，具有較好的全局性。而徑向基（RBF）核函數(shù)局部性很強(qiáng)。所以本文考慮分別使用這兩種核函數(shù)進(jìn)行垃圾郵件的過(guò)濾，然后再組合這兩種核函數(shù)，進(jìn)行實(shí)驗(yàn)比較，得到新的組合。使用的新的核函數(shù)的公式如下：

在 KPoly（x，y）中，s和 c 均取 1。 實(shí)驗(yàn)表明當(dāng) d=2 時(shí)，多項(xiàng)式（Poly）核函數(shù)的外推能力較好，所以本次實(shí)驗(yàn)選取d=2。對(duì)于 KRBF（x，y），當(dāng)參數(shù) σ2=5 時(shí)，局部性較強(qiáng)。 參數(shù) ρ的選擇也會(huì)影響到所組合的核函數(shù)的分類(lèi)精確性。本次實(shí)驗(yàn)中分別取ρ得值為 0.1、0.3、0.5、0.7、0.9 進(jìn)行了實(shí)驗(yàn)比較，分別用 PU 語(yǔ)料庫(kù)所提供的四組郵件來(lái)實(shí)驗(yàn)。每個(gè)組分為十個(gè)相等的部分，一個(gè)作為測(cè)試集，其余九份作為訓(xùn)練集。 以此類(lèi)推，一共做四次實(shí)驗(yàn)，然后求出四次準(zhǔn)確率的平均值，最終選出組合核最佳參數(shù)。如表2所示。

表2 值對(duì)應(yīng)的組合核函數(shù)準(zhǔn)確率Tab.2 The accuracy of Combination kernel function for different

根據(jù)組合核函數(shù)的公式和表2中可以看出，當(dāng)ρ越大時(shí)，KRBF（x，y）占主導(dǎo)作用；ρ越小時(shí)，KPoly（x，y）占主導(dǎo)地位。 當(dāng)ρ=0.9時(shí)，相對(duì)而言組合核函數(shù)在垃圾郵件過(guò)濾的準(zhǔn)確性上最高。推廣能力較好。

2）實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)選取 PU1 中提供的郵件，分別用 KPoly（x，y）、KRBF（x，y）和這兩種核函數(shù)的組合對(duì)垃圾郵件進(jìn)行過(guò)濾。綜合分析垃圾郵件過(guò)濾的準(zhǔn)確性。選取500個(gè)樣本作為訓(xùn)練集，其余的作為測(cè)試集。則測(cè)試集中共有599封郵件。其中選取250封垃圾郵件，349封正常郵件。分別實(shí)驗(yàn)4次，然后取平均值。由上面參數(shù)分析可知，多項(xiàng)式核函數(shù)中取d=2；徑向基核函數(shù)中取σ2=5；組合核函數(shù)中取ρ=0.9；根據(jù)經(jīng)驗(yàn)和實(shí)驗(yàn)，選SVM中懲罰因子C=10。實(shí)驗(yàn)結(jié)果如下表3所示。

從表3中可以看出，當(dāng)時(shí)，組合核SVM用于垃圾郵件過(guò)濾在準(zhǔn)確性上較單核而言，有所提高。這說(shuō)明組合核在具備了徑向基良好的學(xué)習(xí)能力的基礎(chǔ)上，泛化能力進(jìn)一步加強(qiáng)。顯示出較單核而言推廣能力的優(yōu)越性。所以將組合核應(yīng)用于垃圾郵件的過(guò)濾是可行并且行之有效的方法。

表3 各種核函數(shù)過(guò)濾結(jié)果對(duì)比Tab.3 The filter results contrast of different kernel functions

4 結(jié)束語(yǔ)

本文分析了利用SVM進(jìn)行垃圾郵件過(guò)濾的過(guò)程，其中包括文本的預(yù)處理。著重通過(guò)理論和實(shí)驗(yàn)，分別研究了多項(xiàng)式核函數(shù)和徑向基核函數(shù)，以及混合兩種核函數(shù)后應(yīng)用于垃圾郵件的過(guò)濾。通過(guò)比較分析，得出基于垃圾郵件過(guò)濾的系統(tǒng)中，組合核相對(duì)于單核，更具有較好的學(xué)習(xí)能力和泛化能力。但是參數(shù)的選擇、核函數(shù)的組合仍然會(huì)對(duì)實(shí)驗(yàn)結(jié)果有所影響。針對(duì)不同數(shù)據(jù)的分析，如何通過(guò)選擇最優(yōu)參數(shù)以及分配最佳核函數(shù)的組合來(lái)獲得最佳的分類(lèi)效果，仍是研究的重點(diǎn)和難點(diǎn)。

[1]Vapnik V N．The Nature of Statistical Learning Theory[M]．New York：Springer-Verlag，1995．

[2]VAPNIK V N．statistical Leaming’Iheory[M]．New York：John Wiley&sons，1998．

[3]Li Zhi-feng．Using support vector machines to enhance the performance of bayesian face recognition[J].IEEE Transactions on Information Forensics and Security，2007，2 （2）:174-180.

[4]TOM F.In vivo spam filtering:A challenge problem for data mining[J].KDD Explorations，2003，5（2）:140-148.

[5]Mercer J．Functions of positive and negative type and their connection with the theory of integral equations[J]．Trans．Roy Soc London A，1990，209：415-416．

[6]Smola A J．Learning with Kernel[D]．Bedin：Ph D Thesis Berlin，1998．

[7]瞿娜娜．基于組合核函數(shù)支持向量機(jī)研究及應(yīng)用[D]．廣州：華南理工大學(xué)，2011．

[8]張冰，孔銳．一種支持向量機(jī)的組合核函數(shù)[J]．計(jì)算機(jī)應(yīng)用，2007，27（1）：44-46．ZHANG Bing，KONG Rui.A kind of combination of Kernel function for SVM[J].Computer Application，2007，27（1）：44-46．

[9]傅清秋，謝永華，楊波，等．基于組合核函數(shù)SVM沙城暴預(yù)警技術(shù)的研究[J]．計(jì)算機(jī)工程與設(shè)計(jì)，2014，35（2）：646-650.FU Qing-qiu，XIE Yong-hua，YANG Bo，et al.Research on sand-dust storm warning based on SVM with combined kernel function[J].Computer Engineering and Design，2014，35（2）:646-650.