吴陈，孙伟

（江苏科技大学 计算机科学与工程学院，江苏 镇江 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.