基于模糊支持向量机的中文垃圾邮件过滤方法

赵海涛,魏 延,赖 敏,陈守刚

(1.重庆师范大学数学与计算机科学学院,重庆 400047;2.重庆正大软件职业技术学院,重庆 400056)

基于模糊支持向量机的中文垃圾邮件过滤方法

赵海涛1,2,魏 延1,赖 敏1,陈守刚1

(1.重庆师范大学数学与计算机科学学院,重庆 400047;2.重庆正大软件职业技术学院,重庆 400056)

随着电子邮件的广泛使用,垃圾邮件问题也日益严峻.基于邮件内容的过滤是当前解决垃圾邮件问题的主流技术之一.提出了一种基于带有模糊隶属度的模糊支持向量机对中文垃圾邮件过滤的方法,同时,为解决FSVM中隶属度函数的确定问题,使用了一种改进的基于类中心的隶属度函数设计方法.通过实验,使用FSVM对垃圾邮件过滤能够取得较好的效果.

垃圾邮件;支持向量机;模糊支持向量机;模糊隶属度;隶属度函数

0 引 言

随着互联网的快速发展,电子邮件作为一种现代通信手段受到广泛使用,但同时也受到大量垃圾邮件的骚扰.支持向量机(SVM)是Vapnik[1]提出的一种基于统计学习理论的机器学习方法,它以最大化分类间隔构造最优分类超平面来提高分类器的泛化能力,具有训练样本小、泛化能力强、全局最优等优点.本文提出一种基于带有模糊隶属度的模糊支持向量机对中文垃圾邮件过滤的方法,通过实验证实,该方法对垃圾邮件过滤能取得较好的效果.

1 模糊支持向量分类机

标准的或者说传统的SVM主要是用于解决非模糊的两类划分和多类划分的问题.每个样本点都被假定属于一个并且是唯一的一个类.而在许多现实中的问题中,一些训练样本点数据是以不同的隶属度属于不同的类.实际上,一封邮件是否是垃圾邮件,以及在多大程度上是垃圾邮件,不同的用户有不同的理解.因此,对邮件过滤的处理应被视为不确定信息的处理问题.本文根据文献[2,3]中提出的模糊支持向量机(FSVM)方法来对垃圾邮件进行过滤.

设训练样本集为,

其中,xi∈Rm,yi∈{+1,-1},核函数为z=φ(x),则训练集变为(φ(xi),yi),分类超平面为w·φ(xi) +b=0.

引入模糊因子si(0＜si≤1,i=1,2,…,n)来表示第i个邮件样本属于正类的程度.此时,训练集就转化为带有模糊因子的训练样本集(φ(xi),yi, si)),设sζii为带权松弛因子,C＞0为惩罚参数.模糊支持向量机(FSVM)的最优分类超平面的求解转化成一个二次规划问题：

其约束条件为,

2 垃圾邮件过滤预处理

2.1 邮件信头和信体分离

电子邮件的一般格式包括信头和信体两部分.其邮件过滤预处理为：首先分离信头和信体,有时候仅仅根据信头信息就可以判断一封邮件是否是垃圾邮件;然后分别进行基于信头和信体的过滤.

2.2 中文分词和去停用词

中文电子邮件不同于英文邮件,每个词条间没有固定的空格分隔符.为了将中文电子邮件向量化,首先需要进行分词.本文采用正向最大匹配法和逆向最大匹配法[4]相结合的分词方案,即先根据标点对文档进行粗切分,把文档分解成若干个句子,然后再对这些句子用正向最大匹配法和逆向最大匹配法进行扫描切分,如果两种分词方法得到的匹配结果相同,则认为分词正确,否则按最小交集处理.

其次,分词处理完成之后,得到一系列文本单词所组成的表列,特征辞典是由表列中的单词所构成的集合.为了缩小文本特征辞典,提高邮件分类器的训练分类效率,通常需要对辞典进行去停用词处理.

2.3 邮件特征表示

邮件的特征表示主要采用向量空间模型(Vector Space Model,VSM),在邮件向量空间模型中,一封邮件就是一篇文档(Document)d,邮件中的每个词就是一个特征项(Term)t,所有的特征项构成特征词典(Term List),{tk│1≤k≤n}.这样,文档 d则被表示为d(t1,t2,…,tN).对特征辞典中的任意特征项而言,由于它在邮件中出现的位置和出现的频率不同,对邮件分类结果的影响也不同.故应该给每个特征项赋予一定的权重来表示其重要程度,故文档 d又被表示成,d(t1,w1;t2,w2;…,tN, wN),可简记为,d= d(w1;w2;…;wN),其中,ti(i =1,2,…,N)为特征项,wi为ti的权重.权重wi一般被定义为在词 ti在文档d中出现频率tf(t,d)的函数,常见的有布尔函数、平方根函数、对数函数和TFIDF函数等.本文采用 TFIDF函数,公式为,

其中,w(t,d)为特征项 t在文档d中的权重,tf(t, d)为特征项t在文档d中的词频,N为训练样本的总数,nt为训练样本集中出现特征项t的文本数,分母为归一化因子.

3 基于FSVM的垃圾邮件分类机

3.1 FSVM分类机

设垃圾邮件的训练样本集为,

其中,xi∈Rm,yi∈{+1,-1},(+1即正类,代表合法邮件;-1即负类,代表垃圾邮件),Z=φ(x)表示从Rn到一个特征空间Z的非线性映射,则训练样本集变为(φ(xi),yi),分类超平面为w·φ(xi)+b =0;引入模糊因子si(0＜si≤1,i=1,2,…,n)来表示第i个邮件样本属于正类(即合法邮件)的程度.此时,训练集就转化为带有模糊因子的训练样本集(φ(xi),yi,si)),又设 siζi为带有权重的松弛因子,C为惩罚参数(值大于0)用来控制对错分样本惩罚的程度.模糊支持向量机(FSVM)的最优分类超平面的求解转化成一个二次规划问题,

其约束条件为,

yi(w·xi+b)≥1-ζi,ζi≥0, i=1,2,…,n

通过构造拉格朗日函数可将(3)式转化为对偶形式,

对应的约束条件为,

求解(4)式可得到其最优解α＊,同时,利用原始约束可以找到阈值b＊,从而可以把模糊支持向量机最优分类函数转化为,

在式(4)、(5)中,K(xi,xj))为核函数,表示某特征空间 Z的内积,其值为,

3.2 核函数

核函数的基本作用是将非线性可分输入空间等价映射到线性可分的高维空间.常见核函数包括：多项式核函数(Poly),高斯径向基核函数(RBF)与 S型核函数(Sigmoid).

多项式核函数的优点在于计算的复杂度很小,需要存储的数据单元小,缺点是它的运算次数很难控制.一般来讲,多项式的次数越高对于要处理的问题的精度和推广能力越好,但是次数太高的情况下容易出现“过学习”的问题.径向基函数的优点是其本身是一个对称的函数,在没有任何先验知识的境况下经常被采用.而Sigmoid核函数,SVM实现就包含一个隐层的多层感知器,隐层节点数由算法自动确定.在实际应用中,常根据具体问题构造相应的核函数.一般对于文本的非线性可分情况较为常用的核函数为RBF核函数和Poly核函数.

3.3 模糊隶属度的确定和模糊隶属度函数

传统的模糊隶属度的确定方法[2,3]是一种基于类中心的隶属度函数设计方法,使样本对分类所起的作用随着样本远离类别的几何中心而逐渐减小,这样可以弱化噪声或孤立点的影响,但同时也大大弱化了支持向量对分类超平面的作用,其最终结果将会使所获得的分类超平面偏离最优分类超平面.如图1所示,从圆心到圆周,训练样本的隶属度依次减小,这样,支持向量(粗体表示)的隶属度很小,从而容易导致分类超平面偏离最优分类超平面.

图1 基于类中心的隶属度设计方法

参照文献[5,6]中所给出的模糊隶属度确定方法,同时,分析比较了文献[7-9]提出的隶属度函数,本文使用一种简单快捷有效的隶属度函数,即改进的基于类中心的隶属度函数设计方法：样本对分类所起的作用随着样本远离类别的几何中心而逐渐增大,即将样本到类别几何中心的距离与该类中离类别几何中心最远的样本到类别几何中心的距离的比值定义为隶属度;对于那些离类中心太远的噪声和孤立点,设置一个阈值,当样本与类别几何中心的距离大于阈值时,就赋一个很小的隶属度;阈值根据两类样本几何中心之间的距离和样本的稠密情况决定,通过调整阈值,就可以使支持向量的隶属度较大,而噪声或孤立点的隶属度很小,即在给噪声或孤立点赋小隶属度的同时,保证了支持向量有较大的隶属度,从而使分类精度较高.如图2所示,从圆心到内圆周,训练样本的隶属度依次增大,而内圆周与外圆周之间的训练样本则赋予很小的隶属度.这样,通过给噪声或孤立点很小隶属度避免了噪声或孤立点的干扰,保证了支持向量有较大的隶属度,从而使分类精度提高.

图2 新的隶属度设计方法

在两类分类中,使用正类样本的均值作为正类的中心,记为x+,即;负类样本的均值作为负类的中心,记为x-,即x正类的半径,,负类的半径,r-=每个正类样本到正类中心的距离为,d+;每个负类样本到负类中心的距离为,,平均距离,m-=.两类中心的距离为,t=.θ为一个很小的正数,作为噪声和孤立点的隶属度.λ＞0为一个控制因子,使 t·λ·m+/(m+m-)＜r+和 t·λ·m-/(m++m-)＜r-成立,则隶属度函数定义为：

式(6)中,δ是足够小的正数,是为了保证si＞0而设置的.

4 实验与结果

4.1 评价指标

垃圾邮件过滤的性能评价常借用文本分类相关指标.本文在分类时选用以下3种评价指标.

在以上3种评价指标中,Ns→s表示将垃圾邮件判为垃圾邮件的样例数,Ss→h表示将垃圾邮件判为合法邮件的样例数,Nh→s表示将合法邮件判为垃圾邮件的样例数,Ns为垃圾邮件总数.

4.2 实验系统框图

实验系统框图如图3所示.训练邮件用于生成FSVM分类机,新邮件则通过FSVM分类器进行分类.

图3 实验系统框图

4.3 实验环境及实验结果

本实验环境为：CPU 2.0 GHz,Windows XP SP2, 80 G硬盘,512 M内存.

实验所用语料来自于中国教育和科研网紧急响应组(CCERT)于2005年6月公布的电子邮件数据集.实验所采用的电子邮件样本是从中随机抽取的一部分,其中垃圾邮件为2 000封,合法邮件为2 000封,共计4 000封电子邮件样本.实验共进行了10次,每次实验都从数据集中随机抽取同等数量邮件.训练集共选取2 000封,其中垃圾邮件为1 000封,合法邮件为1 000封.测试集共选取2 000封,其中垃圾邮件为1 000封,合法邮件为1 000封.前5次实验选取多项式核函数(Poly)进行邮件过滤,分别得到评价指标 P、R、F的值,并求得5次实验数据的平均值.后5次选取径向基核函数(RBF)进行邮件过滤,方法同 Poly核函数过程.最后与贝叶斯方法和支持向量机方法(使用多项式核函数,训练测试样本分布同FSVM,并取3次的平均值)进行了对比.测试结果如表1所示.

表1 实验结果

由表1数据可知,FSVM方法能够取得更好的分类效果.其R、P和F的测试值均比贝叶斯方法的测试值高出8到10个百分点,比支持向量机方法高2到4个百分点.在所用时间方面,实验中发现模糊支持向量机方法比贝叶斯方法较快,与支持向量机方法速度接近或稍快.

5 总 结

本文将模糊支持向量机分类方法引入中文垃圾邮件过滤技术中.针对传统的模糊隶属度的确定方法存在因噪声和孤立点干扰而影响分类效果的缺点,本文使用了一种改进的隶属度函数设计方法.通过仿真实验,使用该方法对垃圾邮件过滤能够取得较好的效果,具有较高的可行性.

[1]Vapnik V N.The Nature of Statistical Learning Theory[M].New Y ork：Spring-Verlag,1995.

[2]Lin C F,Wang S D.Fuzzy support vector machines[J].IEEE Transaction on Neural Networks,2002,13(2)：464-471.

[3]Lin C F,Wang SD.Fuzzy support vector machines with automatic membership setting[J].Stud Fuzz,2005,177(1)：233-254.

[4]潘文峰.基于内容的垃圾邮件过滤研究[D].北京：中国科学计算技术研究所,2004.

[5]刘 畅,孙德山.模糊支持向量机隶属度的确定方法[J].计算机工程与应用,2008,44(11)：41-42.

[7]哈明虎.一种新的模糊支持向量机[J].计算机工程与应用,2009,45(25)：151-153.

[8]范婕婷,赖惠成.一种基于SVM算法的垃圾邮件过滤方法[J].计算机工程与应用,2008,44(28)：95-97.

[9]杜 吉吉,刘三阳,齐小刚.一种新隶属度函数的模糊支持向量机[J].系统仿真学报,2009,21(7)：1901-1903.

Filter Methods of Chinese Spasm Based on Fuzzy Support Vector Machine

ZHAO Haitao1,2,WEI Yan1,LAI Min1,CHEN Shougang1

(1.School of Mathmatics and Computer Science,Chongqing Normal University,Chongqing 400047,China; 2.Chongqing Zhengda Software Polytechnic College,Chongqing 400047,China)

With the widespread use of e-mail,the issue of spam is also increasingly severe.Content-based filtering is one of the mainstream technologies used so far.In this paper,a method of fuzzy support vector machine with a fuzzy membership degree for Chinese spam filtering was proposed for the decision of membership function of FSVM.A new method of membership function which improves the method based on center of cluster was used.After the experiment,using FSVM,spam filter can achieve better results.

spam;support vector machine;fuzzy support vector machine;fuzzy membership;membership function

TP18

：A

1004-5422(2010)02-0133-04

2010-03-14.

重庆市教委科技计划基金资助项目(K J090823).

赵海涛(1984—),男,硕士研究生,从事机器学习与智能计算研究.