基于改进信息增益的垃圾邮件过滤研究

翟军昌，车伟伟，刘艳丽，康建军

（1.渤海大学 辽宁 锦州 121000；2.沈阳大学 辽宁 沈阳 110044；3.铁岭市清河区教育局 辽宁 铁岭 112003）

垃圾邮件日益泛滥产生一些列的问题，如导致邮件服务器的运行效率降低、产生网络拥塞和网络安全等。随着垃圾邮件技术手法越来越复杂，如隐藏邮件头等[1]，垃圾邮件更加具有攻击性，而且垃圾邮件的危害更大，因此垃圾邮件过滤研究具有重要的现实意义。目前针对垃圾邮件的处理主要以过滤技术为主，其中基于机器学习方法的垃圾邮件过滤技术应用研究最多，如 SVM、KNN、Winnow、Bayes等方法[2]。 机器学习的方法将垃圾邮件过滤看成一个分类问题，首先收集大量合法邮件和垃圾邮件作为样本，然后指导过滤器对收集到的邮件样本进行学习，最后通过训练好的过滤器对新到达的邮件进行最终分类。过滤器通过对邮件样本的训练和学习可以自动获得垃圾邮件的特征，并根据垃圾邮件特征的变化准确的对垃圾邮件进行过滤。

在实际使用中，用户宁愿接收更多的垃圾邮件，也不愿意将合法邮件误判为垃圾邮件，此外不同的用户对于同一封邮件的决策也不同，因此如何有效提取邮件样本的特征，降低对合法邮件的误判，显得尤为重要。在垃圾邮件过滤中，如何有效的选取邮件特征词时垃圾邮件过滤的关键问题之一[3-4]。文中针对垃圾邮件过滤中特征项选择问题，提出了一种改进的信息增益的方法提取邮件的特征项，并结合最小风险贝叶斯分类器对邮件过滤，实验结果表明改进后的方法降低了对合法邮件的误判。

1 邮件特征提取

电子邮件本身是一种无结构的文本，计算机对邮件进行学习和处理时，一般要采用向量空间模型对邮件进行向量化处理，向量空间可以看成是由n个特征项t1，t2，…，tn构成的向量空间，其中特征项可以是字、词、词组或短语等，对于任意一个给定的邮件d在向量空间中对应的特征向量为：d¯={w1，w2，…，wn} ，其中w1，w2，…，wn代表特征项t1，t2，…，tn在邮件d中的权重。

特征项选择是指通过一种评价方法，从高维向量空间中提取出对邮件分类有效的特征项，从而达到对向量空间降维的目的。常用的特征项选择方法有文档频次（DF）、信息增益（IG）、互信息（MI）、相对熵、 χ2统计和优势率等[5]。

2 改进的信息增益

信息增益（Information Gain，IG）是指用一个属性t去划分样本空间而导致期望熵降低的程度，如果IG（t）越大，则说明t对整个分类的作用越大。IG（t）反映了单词t为整个分类所提供的信息量。信息增益的定义如下：

在式（1）中，p（ci）表示 ci类文本在训练样本中出现的概率；p（t）表示单词t在训练样本中出现的概率；p（表示单词t在训练样本中不出现的概率；p（ci）表示在单词t出现的情况下属于ci类的概率；p（ci）表示在单词t不出现的情况下属于ci类的概率。

在垃圾邮件过滤中，由于垃圾邮件分类属于二类问题，若令ci的取值为c0和c1，c0代表垃圾邮件，c1代表正常邮件。则式（1）变为式（2）：

信息增益同时考虑了每一个特征项出现和不出现时，对判断一个文本是否属于某个类所提供的信息量。但是在实际使用中，对垃圾邮件过滤时，当某个特征项在一类邮件中出现的概率高于该特征项在另一类邮件中出现的概率时，则该特征项对该类邮件的分类贡献要大于对另一类邮件分类时的贡献。基于上面的分析，在对垃圾邮件过滤时，考虑到特征项在垃圾邮件和合法邮件中出现的概率不同，从而对两类邮件分类的贡献不同，因此对于式（2）做如下改进：

最后根据式（3）和式（4）对式（2）改进后的信息增益记为IG（t）′，IG（t）′的计算方法如式（5）所示：

3 最小风险素贝叶斯决策

贝叶斯分类算法是文本分类中广泛使用的方法，它是假定对所研究的对象D事先已经有一定的认识，用P（D）表示D的先验概率。在观察对象D之前，确定某个假设空间C中的某个假设c成立的先验概率为P（c）。在c成立时，观察到D的先验概率为P（D）。在观察到训练数据D后，c成立的后验概率为P（c），根据贝叶斯公式可知：

贝叶斯方法在垃圾邮件过滤中取得了非常好的效果[6-10]，但是在实际对邮件过滤中，过滤器可能把一封垃圾邮件误判为合法邮件，也可能把一封合法邮件误判为垃圾邮件。对于每一个用户来说，他们宁愿将垃圾邮件误判为合法邮件，也不愿意将一封合法邮件误判为垃圾邮件被过滤器过滤掉，因此把一封合法邮件误判为垃圾邮件的损失远远大于把一封垃圾邮件误判为合法邮件的损失。在垃圾邮件过滤中，考虑两种分类错误所带来的风险或损失因素作出如下假设：

设决策空间由两个决策ai（i=0，1）组成，其中i=0表示决策为垃圾邮件，i=1表示决策为合法邮件。设损失因子为λ=（ai，cj），λ=（ai，cj）表示当真实状态为 cj（j=0 代表垃圾邮件，j=1代表合法邮件）而采取的决策为ai时所带来的损失。当i=j时（即邮件被正常识别）损失为0；当垃圾邮件被误判为合法邮件时损失为1，当合法邮件被误判为垃圾邮件时损失为λ，并且 λ>1。

根据上面的假设可知，对于任意给定的邮件d，如果采取决策ai，则它的条件期望损失为：

根据最小风险贝叶斯假设和式（8）知，有式（9）和式（10）成立：

在过滤邮件时希望损失最小，所以最小风险贝叶斯决策规则如下：

对于任意给定的邮件d，根据最小风险贝叶斯决策规则式（11）知，当邮件d被判断为垃圾邮件时，有下式成立：

4 实验结果与分析

在Windows XP环境下，以VC++6.0为实验平台，实验中使用的语料库为Androutsopoulos[7]等人提供的Ling-Spam，实验中选用了lemm_stop语料库，其中包括2 412封语言学家的正常邮件和481封垃圾邮件，将邮件样本分成10份进行交叉实验。对于过滤器的评价标准，采用召回率（SR）、正确率（SP）其计算方法如下：

其中nS→S表示被正确识别出的垃圾邮件总数，nS→L表示被误判为合法邮件的垃圾邮件总数，nL→S表示被误判为垃圾邮件的合法邮件总数。

实验中选用特征向量维数从100～1 000，每次实验增加100，阈值λ取999，最后根据10份样本交叉实验的结果对召回率和正确率取平均值，召回率（SR）、正确率（SP）在算法改进前和改进后的变化如图1和图2所示。

图1 召回率变化对比Fig.1 Recall change contrast

图2 正确率变化对比Fig.2 Precision change contrast

5 结 论

文中针对垃圾邮件过滤中的特征项选择问题，提出了一种改进的信息增益方法来提取特征词，并采用了最小风险贝叶斯的决策方法，最后在英文语料库上进行实验，实验结果表明在改进后的算法中虽然漏掉了一部分垃圾邮件，但是合法邮件误判率在降低，对合法邮件判断更加准确了，这样用户的损失也就降低了，这正好符合最小风险的贝叶斯决策的思想。

文中下一步研究的工作是在提高过滤器的正确率，降低用户损失的基础上，提高过滤器的召回率。

[1]Sanchez F，DUAN Zhen-hai，DONG Ying-fei.Understanding forgery properties of spam delivery paths[C]//CEAS 2010 Seventh annual Collaboration， Electronic messaging，AntiA-buse and Spam Conference （CEAS 2010），Redmond，Washington，2010.

[2]陈孝礼，刘培玉.应用于垃圾邮件过滤的词序列核[J].计算机应用，2011，31（3）：698-701.

CHEN Xiao-li，LIU Pei-yu.Word sequence kernel applied in spam-filtering[J].Joumal of Computer Applications，2011，31（3）：698-701.

[3]邓维斌，王国胤，洪智勇.基于粗糙集的加权朴素贝叶斯邮件过滤方法[J].计算机科学，2011，38（2）：218-221.

DENG Wei-bin，WANG Guo-yin，HONG Zhi-yong.Weighted naive bayes spam filtering method based on rough set[J].Computer Science，2011，38（2）：218-221.

[4]闫鹏，郑雪峰，李明祥，等.关于贝叶斯推理的垃圾邮件特征选择评估函数[J].计算机工程与应用，2008，44（33）：105-107.

YAN Peng，ZHENG Xue-feng，LI Ming-xiang， et al.Feature selection approach based on Bayes reasoning in anti-spam classifier[J].Computer Engineering and Applications， 2008，44（33）：105-107.

[5]卢扬竹，张新有，祁玉.邮件过滤中特征选择算法的研究及改进[J].计算机应用，2009，31（3）：2812-2815.

LU Yang-zhu，ZHANG Xin-you，QI Yu.Improvement of feature selection method in spam filtering[J].Joumal of Computer Applications，2009，31（3）：2812-2815.

[6]Sahami M，Dumais S，Heckerman D，et al.A Bayesian approach to filtering Junk e-mail[C]//Learning for Text Categorization：PapersfromAAAIWorkshop.Madison，Wisconsin，1998：55-62.

[7]Androutsopoulos I，Koutsias J，Chandrinos K V，et al.An evaluation of naive bayesian anti-spam filtering[C]//Proc.of the Workshop on Machine learning in the New Information Age，11th European Conference on Machine Learning（ECML’00），Barcelona，Spain，2000：9-17.

[8]Schneider K.A Comparison of Event Models for Naive Bayes Anti-spam E-mail Filtering [C]//Procedings of the 10th Conference of the European Chapter of the Association for Computational Linguistics（EACL’03），2003：307-314.

[9]Vangelis M，Androutsopoulos I，Georgios P.Spam filtering with Naive Bayes-which Naive Bayes?[C]//CEAS 2006 Third Conference on Email and AntiSpam（CEAS 2006） ，Mountain View，California USA，July 27-28，2006.

[10]CHEN Bin，DONG Shou-bin，FANG Wei-dong.Introduction of Fingerprint Vector based Bayesian Method for Spam Filtering[C]//CEAS 2007 Fourth Conference on Email and Anti-Spam，MountainView（CEAS2007），CaliforniaUSA，2007.