基于改进贝叶斯决策的邮件过滤

薛正元

基于改进贝叶斯决策的邮件过滤

薛正元

探讨了基于概率阈值的贝叶斯邮件过滤模型的局限性：由于很少考虑所设定阈值的适用性和实用性，损失了一定的召回率。改进贝叶斯决策，提出了基于随机变量的较小错误分类决策方法；针对邮件处理的特殊性，进一步提出了基于随机变量的较小风险分类决策方法。实验结果表明，处理普通文本分类问题时，前者的分类决策效果更好；而后者在处理邮件问题时性能更优，能够在保持较小误判风险的同时，提高贝叶斯邮件过滤器的召回率以及F值。

垃圾邮件；邮件过滤；概率；阈值；分类决策

垃圾邮件不仅困扰人们的日常生活，更威胁到网络的效率和安全。据中国互联网协会反垃圾邮件中心[1]公布的《2010年第四季度中国反垃圾邮件状况调查报告》，中国网民平均每周收到13.5封垃圾邮件，处理垃圾邮件耗时9.4 min，并有进一步增长的趋势。当前有多种反垃圾邮件技术[2]，包括黑白名单技术、基于规则的过滤技术、行为识别技术、基于内容的过滤技术等。然而，垃圾邮件的日新月异给当前技术带来了新的难题。单纯利用这些过滤技术，都很难达到令人满意的效果。表1总结了这些主流技术的优缺点。

表1 传统反垃圾邮件技术的优缺点分析

本文重点关注基于内容的过滤技术[3]：首先由用户对现有的大量邮件进行分类——垃圾邮件或正常邮件，然后系统通过对邮件集进行不断地总结与学习，进而根据新邮件内容进行分析和判断。著名的“贝叶斯过滤技术”[3-5]便是基于该思想的一种有效技术。贝叶斯邮件过滤器是一种基于概率的分类器，一般根据计算得到邮件后验概率，采用人为设定阈值的方法进行分类决策。贝叶斯分类器具有优秀的分类表现，但在邮件分类决策时采用概率阈值的方法具有较大主观性，因此难以实现误判风险和垃圾邮件召回率之间的平衡。

1 相关研究

目前已有多位学者将贝叶斯方法应用于文本分类，并取得了较好的效果[6]。但邮件过滤不同于一般的文本分类：通常认为，用户宁愿接收更多的垃圾邮件，也不能接受将合法邮件错判为垃圾邮件[3]。

为解决上述问题，文献[7]提出垃圾邮件的代价因子指标，指出如果简单地追求高的邮件正确率则可能产生很大的代价。自从代价问题被研究人员普遍认识到之后，许多研究者不再盲目地追求所谓的正确率，而对误判垃圾邮件所带来的风险越来越重视。文献[8]提出一种最小风险的贝叶斯决策，即根据误判与漏判之间的代价比来设定阈值从而进行分类决策。这是目前研究人员普遍采用的一种方法，即根据计算得到邮件的后验概率，采用人为设定概率阈值的方法进行分类决策。文献[9]提出一种新的最小风险的贝叶斯决策，从直线几何分割的角度改进了贝叶斯邮件分类决策模型，并定义了新的风险因子。但实质上，该文提出的最小风险的贝叶斯决策仍然是一种基于概率阈值的分类决策。

上述文献[7-9]普遍存在以下问题：它们虽认识到决策风险的存在，甚至采取了设定阈值等措施，却未考虑所设定的阈值是否最优、是否合适，甚至是否有必要设定阈值。对于该问题，文献[10-11]通过贝叶斯过滤方法对垃圾邮件语料进行实验测试，依据实验结果进一步给出了阈值等参数和过滤效果间的关系，并得出了较优的参数设定。但该文仍存在以下问题：尽管人们可能在一个或者若干个训练样本集上进行反复测试和实验验证，得到一个所谓“最佳”阈值，但由于有限的训练样本集不可能具有良好的“数据完备性”，因此对于现实中的邮件来说，这种阈值的适用性非常有限。而要找到一个具有普适性的“最佳”阈值，尚存在一定难度。

因此，本文从一般模型的探讨着手，讨论了基于概率阈值的贝叶斯分类模型存在的问题，进而提出了一种基于随机变量的分类决策方法。通过理论分析和实验验证了本文方法的有效性。

2 理论模型

2.1 后验概率的计算

设D1，D2，…，Dm为样本空间S的一个划分，P(Di)表示事件Di发生的概率，且 P(Di)＞0(i=1，2，…，m)。对于任一事件x，P(x)＞0，则有贝叶斯公式：

贝叶斯决策就是根据先验概率，利用贝叶斯公式转换成后验概率，再根据后验概率大小进行决策分类。对于垃圾邮件问题，运用贝叶斯公式对邮件内容进行分析，过滤器根据概率进行邮件分类：垃圾邮件类Spam或正常邮件类Ham。首先在训练过程中收集大量邮件，建立Spam类和Ham类。然后对其中的每一封邮件，提取独立字符串w1，w2，…，wn作为特征分词，并统计相应词频 f1，f2，…，fn。进一步假设文本邮件d中的各特征词之间相互独立，结合贝叶斯公式，求出待分类邮件d属于Spam类的概率（后验概率）如式（2）：

n表示待分类邮件d中所含不同特征词总个数；P(d)表示任意情况下文本邮件d出现的概率；P(Spam)表示垃圾邮件类先验概率，等于训练样本集中垃圾邮件比例；P(wi|Spam)表示在垃圾邮件类条件下特征词wi出现的条件概率，等于垃圾邮件类中特征词wi的词频 fi与垃圾邮件类中特征词总数之比；式中与Ham相关的变量含义与上述变量类似。

2.2 基于随机变量的分类决策

对一封待分类邮件di，由2.1节计算得到邮件的后验概率（记该值为Pi）之后，基于概率阈值的贝叶斯过滤器根据Pi值是否达到事先设定的阈值P0进行分类决策。达到P0的就必须归为垃圾邮件，否则必须归为正常邮件，十分不灵活；进一步讲，由于概率问题从根本上来说就是不确定性问题，因此，仅根据不确定的、概率意义上的数值大小就给出问题的确定结果，这种做法显然不太合适。

为此，本文提出一种基于随机变量的分类决策方法。该方法首先利用贝叶斯分类法求出各待分类邮件的后验概率，然后在此基础上进行改进。

2.2.1 基于随机变量的较小错误分类决策

与基于概率阈值的贝叶斯过滤不同的是，本文提出的基于随机变量的分类决策未设定阈值，而使用随机变量的思想：对一封待分类邮件di，后验概率Pi表示的是该邮件属于垃圾邮件的概率，因此，对于后验概率超过1/2的邮件di，可以依概率Pi将其归为垃圾邮件类；未归为垃圾邮件类的，以及后验概率小于1/2的邮件，归为正常邮件类。

采用基于随机变量的分类决策后，贝叶斯过滤垃圾邮件分类决策部分的流程如图1所示。

图1 基于随机变量的分类决策流程图

这种基于随机变量的分类决策方法具有的优点：不会由于人为设定阈值的不当（过大或过小）而导致决策失误带来较大分类损失；同时，引进该方法后，考虑后验概率超过1/2的那部分邮件，其分类决策的整体结果与其数学期望相符；另外，不难发现该决策方法可使邮件分类结果具有较大的邮件判对率T。

（1）采用基于概率阈值的贝叶斯分类算法，设定阈值P0，则判定结果正确的概率为：

（2）采用基于随机变量的较小错误分类决策方法，则判定结果正确的概率为：

将两种方法作比较，式（1）中取阈值P0为0.9，则两方法的决策性能（邮件判对率理论值）对比如图2（a）所示。由图可以看出，与传统基于概率阈值的贝叶斯决策相比，通常情况下后者在全部邮件判对率方面具有较为明显的优势。

进一步分析，不难发现本节提出的决策方法的性能非常接近于基于最小错误的贝叶斯决策（见图2（b））。称这种决策方法为基于随机变量的较小错误分类决策。

图2 与贝叶斯决策法性能对比图

由图2可知，从理论上讲，较之传统基于概率阈值的贝叶斯分类决策，本节基于随机变量的较小错误分类决策除了可使邮件分类的整体结果与数学期望相符，在决策分类正确率方面同样具有优势。

2.2.2 基于随机变量的较小风险分类决策

考虑到邮件分类决策的特殊性：如将一封正常邮件误判为垃圾邮件比漏判一封垃圾邮件代价更高。为降低分类决策风险，进一步改进2.2.1小节提出的基于随机变量的分类决策。

假设误判1封垃圾邮件的代价等同于漏判9封垃圾邮件的代价，则传统贝叶斯决策中设定阈值P0=0.9[8]。而在基于随机变量的分类决策中，将该阈值对应到值1/2，其目的是：如果邮件后验概率达到P0，则归为垃圾邮件的可能性大；否则归为正常邮件的可能性大。通过对邮件分类特性的思考，当后验概率小于等于1/2时，可直接将其归为正常邮件（即 f(Pi)=0，其中Pi≤1/2）。针对后验概率大于1/2时的情况，提出一种采用幂函数形式的决策函数 f(Pi)=Pri。其中Pi＞1/2为邮件di对应的后验概率，r为待定常数。设

将P0=0.9代入式（5），得r=log0.90.5≈6.58，故

显然式（6）满足 f(0)=0及 f(1)=1。同时对于后验概率为1/2的较特殊邮件，有 f(1/2)=0.56.58≈0.01，即只有约1%的可能被判为垃圾邮件，这也符合对于后验概率小于1/2的邮件的处理情况。

由上，得到基于随机变量的分类决策函数 f(Pi)图像，如图3所示。

图3 基于随机变量的分类决策函数f（Pi）图像

得到决策函数 f(Pi)后，就可以在进行分类决策时将邮件依概率 f(Pi)归为Spam类，这与依概率Pi归为Spam类，以及依Pi是否达到阈值归为Spam类相比，具有更低的决策风险。称这种决策方法为基于随机变量的较小风险分类决策。

3 实验验证

3.1 实验安排

实验采取两组对比：实验A采用当今主流的贝叶斯邮件训练方法对邮件集进行训练，然后采用基于概率阈值的分类法进行分类决策。假设误判1封垃圾邮件相当于漏判9封正常邮件，选取0.9作为阈值使错误风险最小[8]。实验B采用同样的贝叶斯邮件训练方法对邮件集进行训练，然后分别采用本文提出的基于随机变量的较小错误决策方法和基于随机变量的较小风险决策方法进行分类（分别记为实验B-1和B-2）。

实验数据源有两个：（1）CCERT[12]，包含9 272封正常邮件和25 088封垃圾邮件，从中随机抽取正常邮件和垃圾邮件各4 500封作为实验数据源；（2）CNLP-Platform[13]，包含正常邮件和垃圾邮件各1 500封，从中随机抽取正常邮件和垃圾邮件各1 200封作为实验数据源。两个数据源独立进行实验：将两个数据源分别平均分成5份，4份用于训练，1份用于测试，进行5重交叉实验，最后取5次实验平均值作为实验结果。

表2 实验A与实验B性能指标比较

3.2 实验结果与评价

采用4个评价指标：垃圾邮件查准率P、垃圾邮件召回率R和F值、全部邮件判对率T。其中，查准率P等于判为垃圾邮件的邮件中实为垃圾邮件的比例，反映识别垃圾邮件的准确性；召回率R等于实为垃圾邮件的邮件中判为垃圾邮件的比例，反映识别垃圾邮件的完整性；F值=2PR/（P+R）兼顾了查准率和召回率问题，是以上两个指标的综合；判对率T等于所有待分类邮件被正确归类的邮件的比例，反映正确归类邮件的能力。

实验得出采用基于随机变量的分类决策方法（实验A）与采用基于随机变量的分类决策方法（实验B）性能指标，如表2所示；图表形式如图4所示。

图4 实验A与实验B性能指标比较图

由图4可知，本文提出的基于随机变量的分类决策方法相对于当今主流的贝叶斯决策有了一定程度的性能提升：实验A中虽具有稍高的查准率P，但召回率指标R不佳；实验B-1具有较高的判对率T，因此对于普通的文本分类问题，利用这种基于随机变量的较小错误分类决策方法将可能是个更好的选择；实验B-2中查准率P稍低，但其召回率R、判对率T和综合指标F值均较好，同时不难验证其在误判风险方面显著优于实验B-1，而与设定阈值P0=0.9的当今主流的贝叶斯决策风险相差无几。

将本文基于随机变量的较小风险分类决策结果与文献[11]提出的最小风险贝叶斯算法结果作比较，可见本文各指标均略高于文献[11]中各指标约2至3个百分点，如表3。因此，本文方法优于文献[11]中的方法。从邮件分类的特殊性考虑，本文基于随机变量的较小风险分类决策方法更适合于进行邮件分类决策。

表3 本文实验结果与文献[11]结果对比

4 结束语

随机变量的思想已经日趋成熟，但将随机变量应用于分类决策的相关研究还比较罕见。本文通过对基于概率阈值的贝叶斯垃圾邮件过滤模型进行理论探讨，提出用随机变量的思想代替概率阈值的思想，并通过一定的性能指标进行实验验证。实验结果表明，较之当今基于概率阈值的贝叶斯邮件过滤技术，在分类决策时引入“随机变量”的思想将会在一定程度上提高贝叶斯过滤器的分类性能。

考虑到邮件分类的特殊性，本文提出的基于随机变量的较小风险分类决策方法更适合于进行邮件分类决策；而对于普通的文本二分类问题，利用本文提出的基于随机变量的较小错误分类决策方法将可能是个更好的选择。同时，考虑到有限的实验邮件集难以具有良好的数据完备性，本文基于随机变量的分类决策思想在“普适性”方面还有待进行更深入的研究。相信随着研究的深入，基于随机变量的分类决策思想将有更广阔的应用前景。

[1]中国互联网协会反垃圾邮件中心[EB/OL].[2011-05-18].http：//www.anti-spam.cn/.

[2]Cormack G.Email spam filtering：a systematic review[M]// Foundations and Trends in Information Retrieval.[S.l.]：Now Publishers Inc，2008.

[3]王斌，潘文锋.基于内容的垃圾邮件过滤技术综述[J].中文信息学报，2005，19（5）：1-10.

[4]陈志贤.垃圾邮件过滤技术研究综述[J].计算机应用研究，2009，26（5）：1612-1615.

[5]Metsis V，Androutsopoulos I，Paliouras G.Spam filtering with naive Bayes-which naive Bayes?[C]//Proc of the 3rd CEAS，Mountain View，CA，USA，2006.

[6]樊兴华，孙茂松.一种高性能的两类中文文本分类方法[J].计算机学报，2006，29（1）：124-131.

[7]Androuts Opoulos 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，the 11th European Conference on Machine Learning （ECML 2000），May 2000：9-17.

[8]李维杰，徐勇.简体中文垃圾邮件分类的实验设计及对比研究[J].计算机工程与应用，2007，43（25）：128-132.

[9]王涛，裘国永，何聚厚.新的基于最小风险的贝叶斯邮件过滤模型[J].计算机应用研究，2008，25（4）：1147-1148.

[10]张学农，张立成.基于简单贝叶斯的中英文垃圾邮件过滤的比较分析[J].计算机应用与软件，2008，25（8）：178-180.

[11]王美珍，李芝棠，吴汉涛.改进的贝叶斯垃圾邮件过滤算法[J].华中科技大学学报，2009，37（8）：27-30.

[12]中国教育和科研计算机网紧急响应组（CCERT）[EB/OL]. [2011-06-27].http：//www.ccert.edu.cn/spam/sa/datasets.htm.

[13]中文自然语言处理开放平台（CNLP-Platform）[EB/OL]. [2011-06-27].http：//www.nlp.org.cn/docs/download.php?doc_id= 1207.

XUE Zhengyuan

郑州大学 信息工程学院，郑州 450001

School of Information Engineering,Zhengzhou University,Zhengzhou 450001,China

This paper confers in depth to the limitations of the traditional Bayesian anti-spam mechanism.It seldom thinks about whether the threshold is suitable or not,so the recalling is reduced.Aiming at this question,the paper proposes a lower-error policy decision based on chance variable;and considering the particularity of email classification,a lower-risk policy decision based on chance variable is proposed.The experimental results show that the former one maybe a better way to classify the common text; and the latter one makes better performance on recalling and F value when dealing with emails,at the same time it keeps a lower risk of error judging.

spam email;email filter;probability;threshold;classify decision

A

TP302.1

10.3778/j.issn.1002-8331.1109-0044

XUE Zhengyuan.Improved probability-based Bayesian anti-spam mechanism.Computer Engineering and Applications, 2013,49（7）：98-101.

薛正元（1989—），男，硕士研究生，主要研究领域为Web数据挖掘，网络信息技术。E-mail：xuezhengyuan@163.com

2011-09-05修回日期：2011-11-21

1002-8331（2013）07-0098-04

CNKI出版日期：2012-01-16 http://www.cnki.net/kcms/detail/11.2127.TP.20120116.0928.067.html