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

吳陳，孫偉

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

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

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

1 文本預(yù)處理

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

那么TF-IDF量化公式為：

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

2 支持向量機(jī)

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

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

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

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

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

約束條件：

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

其中ai為Lagrange系數(shù)。分別對ω和b求偏微分，然后可將原來的目標(biāo)問題變換為所熟悉的凸二次規(guī)劃的對偶問題來求解：

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

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

2.2 核函數(shù)

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

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

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

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

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

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

2.3 組合核函數(shù)

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

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

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

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

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

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

實(shí)驗(yàn)環(huán)境筆記本一臺，基本配置如下：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語料庫。其中包括PU1、PU2、PU3和PU4 4個語料信息。具體語料庫信息如表1所示。

表1 PU語料庫信息Tab.1 The information of PU

本次垃圾郵件評價使用的準(zhǔn)確率（P）、錯誤率（E）。

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

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

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

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

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

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

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

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

實(shí)驗(yàn)選取 PU1 中提供的郵件，分別用 KPoly（x，y）、KRBF（x，y）和這兩種核函數(shù)的組合對垃圾郵件進(jìn)行過濾。綜合分析垃圾郵件過濾的準(zhǔn)確性。選取500個樣本作為訓(xùn)練集，其余的作為測試集。則測試集中共有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)時，組合核SVM用于垃圾郵件過濾在準(zhǔn)確性上較單核而言，有所提高。這說明組合核在具備了徑向基良好的學(xué)習(xí)能力的基礎(chǔ)上，泛化能力進(jìn)一步加強(qiáng)。顯示出較單核而言推廣能力的優(yōu)越性。所以將組合核應(yīng)用于垃圾郵件的過濾是可行并且行之有效的方法。

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

4 結(jié)束語

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