一种基于条件熵的垃圾邮件过滤算法

翟军昌，车伟伟

(1.渤海大学，辽宁 锦州 121000;2.沈阳大学，辽宁 沈阳 110044)

0 引言

伴随着电子邮件(E-mail)的广泛应用，大量包含欺诈、营销、暴力、色情和病毒等信息的垃圾邮件也随之产生。针对垃圾邮件问题的处理，目前主要以过滤技术为主，其中典型的代表有以基于内容的过滤和基于身份标示的过滤2种类型［1-4］。基于内容的过滤技术，以贝叶斯(Bayes)［5-8］、支持向量机(SVM)和决策树(KNN)等机器学习方法为代表，该类方法的主要特点是，根据邮件的内容特征作为邮件分类的依据。基于身份标示的过滤技术，以基于黑、白名单过滤，反向DNS查询和基于用户信誉的过滤技术等为代表，该类方法的特点是根据邮件发件人的身份特征相关信息来判断邮件是否为垃圾邮件［1-4］。

目前基于贝叶斯算法的垃圾邮件过滤研究中，主要集中以下几个方面的研究:(1)邮件样本的特征项选择处理方法研究［9］;(2)贝叶斯算法自身的改进研究［10-11］;(3)贝叶斯算法与其它算法结合研究［12-13］;(4)基于贝叶斯算法的用户反馈方式研究［1］等。

本文针对垃圾邮件过滤中过滤器对合法邮件的误判问题，对条件熵H(c|t)中的条件概率p(ci|t)和)的计算方法利用贝叶斯法则进行变形处理，并在变形后的计算方法中考虑特征项t出现和不出现时的先验概率分布情况，利用特征项t的先验概率对条件熵H(c|t)进行加权处理，从而对信息增益的估计方法作了改进。最后从降低用户损失的角度去考虑，将改进后的信息增益估计方法与最小风险贝叶斯决策算法结合对邮件过滤。实验结果表明改进后的方法提高了过滤器对合法邮件的识别能力，降低了过滤器对合法邮件的误判率，提高了过滤器的分类精度，从而降低了用户的损失。

1 相关知识介绍

1.1 电子邮件文本表示

利用计算机处理电子邮件时，通常采用向量空间模型来表示，即对于任意一封邮件d，对应的特征向量为=(x1，x2，...，xn)，xi∈(0，1)，i=0，1，…，n，其中xi为d对应特征项Xi的权重。如果权重xi采用布尔权重表示方法时，xi取1表示在邮件中出现，xi取0表示在邮件中没有出现。

1.2 特征项选择与熵

对于大量的邮件样本信息，特征词刻画了邮件样本库的特征信息，为了提高对邮件分类的精度，需要从邮件样本库中寻找对分类起作用的特征词信息。特征项选择是一种计算特征词或邮件样本概率分布与类别之间关系的评价方法，如文档频次(DF)、信息增益(IG)、互信息(MI)、相对熵和χ2统计等。通过用特征项选择的方法可以达到对邮件样本向量空间降维的目的，同时也可以提高对邮件处理的效率和分类精度。

定义1 熵。假设随机变量X可能的取值xi有n种，如果每一种取值xi出现的概率为p(xi)，则随机变量X的不确定性称为熵，记为H(X)。

若随机变量X的取值变化越多，则随机变量X所携带的信息量越大，同时随机变量X的熵H(X)也就越大。

定义2 条件熵。假设有随机变量X和Y，随机变量X和Y的可能取值xi和yi分别有n和m种，每一种取值xi和yj出现对应的概率分别为p(xi)和p(yj)，p(xi|yj)表示观测到随机变量Y后随机变量X发生的概率。则在观测到随机变量Y之后，随机变量X的不确定性称为条件熵，记为H(X|Y)。

1.3 贝叶斯分类模型

贝叶斯分类方法是一种基于概率分析的可能性推理理论，其作为一种有效的分类器，广泛应用于文本分类领域。在垃圾邮件过滤中，假设邮件样本向量空间由 n 个特征项 X1，X2，...，Xn构成特征向量 X⇀，邮件样本空间中有2个类别，即c0垃圾邮件和c1合法邮件2类。对于任意给定的一封邮件d，根据贝叶斯公式计算邮件d属于cj类的概率为:

在公式(3)中，可由全概率得出:

根据朴素贝叶斯假设，在公式(3)和公式(4)中对条件概率)的计算时，假设构成中的各个特征项X1，X2，…，Xn是相互独立的，则有:

在公式(5)中，先验概率p(Xi|cj)可以采用文档频次估计的方法，若A代表cj类邮件样本中出现特征词Xi的邮件数量，B代表cj类邮件样本的数量，则采用Laplacean平滑处理后的计算方法为:

在公式(3)和公式(4)中，先验概率p(cj)的计算，可以通过样本空间中cj类样本的总数N占样本空间的样本总数M的比例表示，即:

1.4 最小风险贝叶斯分类模型

在垃圾邮件过滤中，从用户的角度去考虑，不同的用户对于同一封邮件的决策不同，而且过滤器对合法邮件的误判给用户带来的损失，大于过滤器对垃圾邮件误判的损失。每一个用户宁愿将垃圾邮件误判为合法邮件，也不愿意将一封合法邮件误判为垃圾邮件被过滤器过滤掉。因此最小风险贝叶斯分类模型考虑2种分类误判给用户所带来的风险或损失，作出如下假设:

(1)假设将邮件d判断为垃圾邮件c0的决策为a0，将邮件d判断为合法邮件c1的决策为a1。

(2)设损失因子为 λ(ai，cj)，λ(ai，cj)表示当真实状态为cj而采取的决策为ai时所带来的损失。

(3)对于损失因子 λ(ai，cj)，当 i=j时(即邮件被正常识别)损失为0;当垃圾邮件被误判为合法邮件时损失为1，当合法邮件被误判为垃圾邮件时损失为 λ，并且 λ ＞1。

因此，对于任意给定的邮件d，如果采取决策ai，则它的条件期望损失为:

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

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

2 信息增益分析及改进

2.1 信息增益分析

信息增益刻画了随机变量取值不确定性的程度，即用一个属性t去划分样本空间而导致期望熵降低的程度。

在文本分类中，如果H(c)代表类别c的熵，H(c|t)代表观测到属性t后属于类别c的条件熵，则信息增益的定义如下:

在公式(11)中，p(ci)表示ci类文本在训练样本中出现的概率;p(t)和分别表示特征词t在样本中出现和不出现时的概率;p(ci|t)和分别表示在特征词t出现和不出现时属于ci类的概率。IG(t)反映了特征词t对整个分类所提供的信息量。即IG(t)越大时，则说明特征词t对整个分类的作用越大。

在信息增益的计算中，由于H(c)可以根据先验概率计算得出，而对于一个确定的分类集来说，它是一个确定的值，因此每一个特征词t的信息增益值(即IG(t))的大小由条件熵H(c|t)的估计值决定。又因为IG(t)的大小反映了t为整个分类所提供的信息量，所以条件熵H(c|t)的计算方法将直接影响最终分类的效果。

2.2 信息增益的改进

(1)在公式(11)中，根据贝叶斯法则将条件熵H(c|t)中的条件概率p(ci|t)和的计算方法进行变形，变形后的计算方法，如公式(12)所示:

(2)将公式(12)代入公式(11)中的条件熵H(c|t)计算式中，则条件熵H(c|t)的估计方法为:

在式(13)中，条件熵H(c|t)的值只与先验概率p(t)、p(t|ci)和p(ci)的取值有关。

(3)在式(13)中，考虑到特征项t的分布情况，用先验概率p(tj)乘以条件熵H(c|t)，对条件熵H(c|t)做加权处理，则新的条件熵H'(c|t)计算公式为:

(4)改进后的信息增益估计式为:

3 实验结果与分析

实验中以VC++6.0为实验环境，实验中使用的邮件样本是由 Androutsopoulos［7］等人提供的 Ling-Spam邮件样本库，选用了lemm_stop形式语料，其中包括2412封语言学家的合法邮件和481封垃圾邮件，将邮件样本分成10份进行交叉实验。实验中选择了文献［9］中召回率(SR)和正确率(SP)两个评价标准。召回率反映了过滤系统发现垃圾邮件的能力，召回率越高，说明过滤系统识别垃圾邮件的能力越强。正确率反映了过滤系统识别垃圾邮件的正确率，即过滤系统正确识别垃圾邮件的能力，正确率越高，说明合法邮件被误判为垃圾邮件的数量就越少。

实验中选用特征向量维数从100～1000，每次实验增加100，当合法邮件被误判为垃圾邮件时损失因子λ取999，分别采用公式(11)和公式(15)的方法计算特征词的信息增益值，然后采用最小风险贝叶斯决策公式(10)进行分类决策，最后根据10份样本交叉实验的结果对召回率和正确率取平均值，实验结果如表1所示。

表1 实验结果(%)

通过表1可以看出，首先，在改进后的算法中过滤器的正确率有明显的提高，实验结果表明改进后的过滤器对合法邮件的误判率在降低，降低了用户的损失。其次，在改进后的算法中过滤器的召回率在降低，表明改进后的过滤器对垃圾邮件的误判率有所提高。最后，在改进后的算法中当特征向量取600维、700维和1000维时，过滤器的正确率提高的比例低于过滤器召回率降低的比例，在其它情况下，过滤器的正确率提高的比例均高于过滤器召回率降低的比例。因此，算法改进后的过滤器虽然漏掉了一部分垃圾邮件，但是对合法邮件的识别能力提高了，从而降低了过滤器对合法邮件的误判给用户带来的损失。

4 结束语

在垃圾邮件过滤中，从用户损失的角度去考虑，过滤器对合法邮件的误判是用户所不能容忍的。本文针对过滤器对合法邮件的误判问题，通过对信息增益的条件熵估计方法作了改进，从而提出了一种改进的垃圾邮件过滤算法。实验结果表明，虽然改进后的算法降低了过滤器的召回率，但改进后的算法提高了过滤器的正确率，提高了过滤器对合法邮件的识别能力，而且过滤器的正确率提高的比例高于过滤器召回率降低的比例，因此从用户损失的角度去考虑，改进后的算法降低了用户的损失。

［1］黄国伟，许昱玮.基于用户反馈的混合型垃圾邮件过滤方法［J］.计算机应用，2013，33(7):1861-1865.

［2］邓维斌，王国胤，洪智勇.基于粗糙集的加权朴素贝叶斯邮件过滤方法［J］.计算机科学，2011，38(2):218-221.

［3］Sanchez F，Duan Z，Dong Y.Understanding forgery properties of spam delivery paths［C］//Proceedings of the 7th Annual Conference on Collaboration，Electronic Messaging，Anti-Abuse and Spam.2010.

［4］陈孝礼，刘培玉.应用于垃圾邮件过滤的词序列核［J］.计算机应用，2011，31(3):698-701.

［5］Sahami M，Dumais S，Heckerman D，et al.A Bayesian approach to filtering junk e-mail［C］//Proceedings of the 1998 AAAI Workshop on Learning for Text Categorization.1998:55-62.

［6］Androutsopoulos I，Koutsias J，Chandrinos K V，et al.An evaluation of naive Bayesian anti-spam filtering［C］//Proceedings of the 11th European Conference on Machine Learning.2000:9-17.

［7］Metsis V，Androutsopoulos I，Paliouras G.Spam filtering with naive Bayes:Which naive Bayes?［C］//Proceedings of the 3rd Conference on Email and Anti-Spam.2006.

［8］Chen Bin，Dong Shoubin，Fang Weidong.Introduction of fingerprint vector based Bayesian method for spam filtering［C］//Proceedings of the 4th Conference on Email and Anti-Spam.2007.

［9］翟军昌，秦玉平，车伟伟.应用特征词分类贡献的垃圾邮件过滤研究［J］.计算机工程与应用，2012，48(34):116-119，170.

［10］薛正元.基于改进贝叶斯决策的邮件过滤［J］.计算机工程与应用，2013，49(7):98-101，125.

［11］梁志文，杨金民，李元旗.基于多项式模型和低风险的贝叶斯垃圾邮件过滤算法［J］.中南大学学报:自然科学版，2013，44(7):2787-2792.

［12］陶永才，薛正元，石磊.基于MapReduce的贝叶斯垃圾邮件过滤机制［J］.计算机应用，2011，31(9):2412-2416.

［13］夏超，徐德华.一种改进的贝叶斯邮件过滤算法［J］.计算机与现代化，2010(10):125-128，132.

［14］Guzella T S，Caminhas W M.A review of machine learning approaches to spam filtering［J］.Expert Systems with Applications，2009，36(7):10206-10222.

［15］Lai Chih-chin.An empirical study of three machine learning methods for spam filtering［J］.Knowledge-based Systems，2007，20(3):249-254.