基于單核和組合核函數在垃圾郵件過濾中的比較應用

吳陳，孫偉

（江蘇科技大學 計算機科學與工程學院，江蘇 鎮江 212003）

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

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

1 文本預處理

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

那么TF-IDF量化公式為：

ftik表示tk在文檔中出現過的次數，N表示所以樣本的數量，nk表示輸入的tk的文檔頻數。

2 支持向量機

2.1 支持向量機的基本原理

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

SVM在主要是通過構造最佳分類超平面，從而轉化成凸二次規劃問題來求解。下圖為SVM構造的最佳分界面。

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

目標函數：

約束條件：

那么定義如下Lagrange系數，將所求目標變換成對和求Lagrange函數的極小值，即

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

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

設 a*是上述問題的最優解，根據 a*可求出ω*和b*從而最終求出最佳分類函數：

2.2 核函數

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

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

則原來的最佳分類函數變成：

本文采用以下兩種核函數：

多項式（Poly）核函數：

徑向基（RBF）核函數：

2.3 組合核函數

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

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

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

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

3 實驗與分析

3.1 平臺與數據集

實驗環境筆記本一臺，基本配置如下：Windows7系統、3GHz CPU、2G 內存；ICTCLASVersion1.0；VMwareWorkstationUbuntu；LibSVM數據包2.89版；Visual Studio2013。

實驗數據采納希臘學者Androutsopoulos所提供的PU語料庫。其中包括PU1、PU2、PU3和PU4 4個語料信息。具體語料庫信息如表1所示。

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

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

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

3.2 仿真實驗與結果

1）組合核函數模型和參數的選擇

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

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

表2 值對應的組合核函數準確率Tab.2 The accuracy of Combination kernel function for different

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

2）實驗結果分析

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

從表3中可以看出，當時，組合核SVM用于垃圾郵件過濾在準確性上較單核而言，有所提高。這說明組合核在具備了徑向基良好的學習能力的基礎上，泛化能力進一步加強。顯示出較單核而言推廣能力的優越性。所以將組合核應用于垃圾郵件的過濾是可行并且行之有效的方法。

表3 各種核函數過濾結果對比Tab.3 The filter results contrast of different kernel functions

4 結束語

本文分析了利用SVM進行垃圾郵件過濾的過程，其中包括文本的預處理。著重通過理論和實驗，分別研究了多項式核函數和徑向基核函數，以及混合兩種核函數后應用于垃圾郵件的過濾。通過比較分析，得出基于垃圾郵件過濾的系統中，組合核相對于單核，更具有較好的學習能力和泛化能力。但是參數的選擇、核函數的組合仍然會對實驗結果有所影響。針對不同數據的分析，如何通過選擇最優參數以及分配最佳核函數的組合來獲得最佳的分類效果，仍是研究的重點和難點。

[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]瞿娜娜．基于組合核函數支持向量機研究及應用[D]．廣州：華南理工大學，2011．

[8]張冰，孔銳．一種支持向量機的組合核函數[J]．計算機應用，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]傅清秋，謝永華，楊波，等．基于組合核函數SVM沙城暴預警技術的研究[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.