基于贝叶斯算法的垃圾邮件过滤技术的研究与改进_图文

1、第33卷第1期燕山大学学报V ol.33No.12009年1月Journal of Yanshan University Jan.2009 0引言 随着电子邮件的普及,垃圾邮件的泛滥也越来越多地受到人们的关注。中国互联网协会反垃圾邮件中心在2008年1月28日发布的2007年第四次中国反垃圾邮件状况调查报告显示,中国互联网用户平均每周收到垃圾邮件16.71封,已经连续多次超过了正常邮件的数量。大量的垃圾邮件不仅占用了网络传输带宽,影响正常网络通信,更浪费了人们的时间和精力。垃圾邮件的检测和过滤已经迫在眉睫。 目前主要的垃圾邮件过滤技术有3类:1基于IP 、域名和路由等的过滤技术:包括黑/白名单

2、、实时黑名单、反向域名检测等技术;2基于行为的过滤技术:包括过滤群发、流量监控、挑战-回应和蜜罐技术等;3基于内容的过滤技术:包括规则(集匹配、朴素贝叶斯(Naive Bayes 、支持向量机(SVM 、-NN 、最大熵值法等1。基于内容的过滤技术是目前垃圾邮件过滤技术应用的主流,而在基于内容的垃圾邮件过滤方法中,朴素贝叶斯算法2因其既实现了自学习的功能,又满足了个性化的要求,故而在垃圾邮件过滤中得到广泛的应用。本文在对贝叶斯过滤器分析的基础上,引入基于分级的最小风险算法,并提出了一种结合多重贝努利和多项式的混合估计模型。在此基础上对贝叶斯过滤器进行了改进,并进行了实验对比。1贝叶斯过滤器1.

3、1贝叶斯定理贝叶斯定理是由托马斯贝叶斯(1702-1761提出的计算概率的一种方法。它是通过对某一事件过去发生概率情况的考察,大体可以推断出当前这一事件发生的概率。它的形式化表述为:设试验,的事件,2,µÄÒ»¸ö»®·Ö£¬ÇÒ>0,则,=1;2;,或者2,是特征项,可以是文章编号:文献标识码: 48燕山大学学报2009字、词、短语或者是某种概念。 是类别集合1,中的一个元素。对一 待分类文本2,则样本 =, =,= 即将 = 式中,=是类=是指

4、= =对于同一篇文档,=不变。=是指类 较大,而且特征变量之间相互依存度较高 时,它的计算比较复杂。为简化计算,可假定各个特征变量之间相互独立,这样就引出了朴素贝叶斯分类器模型。对于给定的分类变量 = 故而= 其中= 1.3贝叶斯过滤器贝叶斯过滤器实际上是贝叶斯分类器的一种,它是将垃圾邮件过滤问题看成是垃圾邮件文本的二值分类问题。对于每一个邮件样本,使用向量空间模型对其进行形式化描述,1;2;,是邮件选取特征项,=,2,根据贝叶斯理论,未知邮件属于垃圾邮件类别的概率计算公式为=其中,=2,同时出现的概率;= 第1期张付志等基于贝叶斯算法的垃圾邮件过滤技术的研究与改进49 价函数来计算特征词与类

5、之间的关系,通过计算结果选取预定数量的最优特征词,从而提高分类的精度。常用的特征提取方法有:文档频度、信息增益、期望交叉熵、互信息等3。 在特征提取过程中,特征太少,不能全面表现邮件的内容,区分度不够;特征太多,又有一些无关的特征引入了分类噪声。有实验数据表明4:当中文语料的特征项集合大小为12001800时,精确率和召回率都相对较高;对英文语料库,其最佳特征集合大小为350800。2.3估计模型 在贝叶斯假设的基础上,文本可以看作是若干词汇的集合,可以认为文本是这些词汇按照一定的方式产生的。根据产生的方式不同,贝叶斯分类算法有两种概率估计模式:2.3.1基于词频的多项式事件模型 多项式事件模

6、型(MM ,Multinomial event Model 需考虑词频,即每个特征词出现看作“事件”,文本是这些“事件”的集合5。设文本 表示特征词在文本为特征数量,则 符合多项式分布,则有 =! ! À¬»øÓʼþµÄËùÓÐÎı¾ÖÐÌØÕ÷´Ê×ÜÊý 为了避免分母为0,需对上式进行平滑处

7、理 = = =1+1=+应用到垃圾邮件过滤中=1=À¬»øÓʼþµÄÎı¾ÊýÁ¿平滑处理=+1= 50燕山大学学报2009求,但对于一些严重依赖电子邮件的商业机构或组织来说,一封重要的商业邮件被误判为垃圾邮件而被过滤所带来的损失往往比10封垃圾邮件被误判为合法邮件严重的多。也即是说用户宁可接受多封垃圾邮件也不愿意漏掉一封正常邮件,因此引入代价因子倍,只有当=/=>= 1=,则有 =>= 只有当=&g

8、t; >999时,其准确率可高达100%。在此基础上引入一种多级邮件的思路。在新邮件到来时,计算=值,然后进行判断: 1当=> =>=时,判定 >=>=时,判定 估计模型的改进 多重贝努利模型和多项式模型,各有不同的适用范围。多重贝努利模型不考虑词频信息,这可能混淆重要特征和非重要特征。而多项式模型虽然考虑词频,却认为同一文档中多次出现同一特征是独立的,这种假设加大了高频词对分类的影响,在训练时可能误导特征对类别的影响,影响分类结果的准确性。通过实验表明,在训练阶段,如果训练文档比较充足,即使不考虑词频信息,也可以得到很好的分类效果,这样可以使用不考虑词频的算法来

9、简化训练阶段的计算。而在分类阶段,针对某一文档,单词在文档中的频率往往就显得比较重要,这时往往需要考虑词频来进行计算。所以,本文设计的邮件过滤器中,将两种模型相结合,在训练阶段使用多重贝努利模型对单词的先验条件概率进行估计,而在分类阶段采用多项式模型。这种方法即考虑到了词频的作用,又兼顾到了训练阶段的计算复杂度。4实验及评价4.1评价体系设待测的邮件集合中共有=+=+ʵ¼ÊµÄÀ¬»øÓʼþÊýÄ¿¼&

10、#180;À¬»øÓʼþµÄ¼ì³öÂÊ£¬·´Ó³¹ýÂËϵͳ·¢ÏÖÀ¬»øÓʼþµÄÄÜÁ¦¡&

11、#163;µ±²éÈ«ÂÊÔ½´óʱ£¬Â©ÍøµÄÀ¬»øÓʼþÊýÔ½ÉÙ£¬ÏµÍ³ÐÔÄÜÒ²Ô&

12、#189;ºÃ£»2准确率(正确率,Precision :=+Åж¨ÎªÀ¬»øÓʼþµÄÊýÄ¿¼´À¬»øÓʼþµÄ¼ì¶ÔÂÊ£¬·

13、80;Ó³¡°ÕÒ¶Ô¡±À¬»øÓʼþµÄÄÜÁ¦¡£×¼È·ÂÊÔ½¸ß£¬±íʾ½«ºÏ·¨Ó

14、02;¼þÎóÅÐΪÀ¬»øÓʼþµÄ¿ÉÄÜÐÔԽС£¬½ø¶øʹϵͳÐÔÄÜÔ½ºÃ¡

15、63;第1期张付志等基于贝叶斯算法的垃圾邮件过滤技术的研究与改进514.2实验结果分析本文实验完全采用英文邮件样本,英文语料采用公开的垃圾邮件公共词料库PU1中lemm-stop 语料。PU1共有1099封邮件,包含481封垃圾邮件、618封正常邮件。将语料分为10份,每份大约110篇,每次取一定的份数作为训练集,在剩余的邮件中另取一份作为测试集,进行实验。实验1对比朴素贝叶斯算法与引入分级的最小风险算法的贝叶斯过滤器的过滤效果。测试过程分别单独使用朴素贝叶斯算法和引入分级的最小风险算法进行比较,在实现分级的最小风险算法实验过程中将正常邮件和可疑邮件保留,将垃圾邮件过滤,并对分类错误进行二次学

16、习。不断调整训练样本集的大小,不考虑被判为可疑邮件的情况下,对比两种算法的实验结果。其查全率和准确率对比如图1、2所示。 图1两种算法实验结果查全率对比Fig.1Recall of comparative experiments for two algorithms 图2两种算法实验结果准确率对比Fig.2Precision of comparative experiments for two algorithms从实验结果可以看出,使用分级的最小风险算法在不考虑可疑邮件的情况下,准确率较朴素贝叶斯算法有明显的提高,但是查全率却明显下降,这并不难理解,110样本数0.71.00.90.8查全率

17、朴素贝叶斯算法分级的最小风险算法(110样本数0.71.00.90.8查全率朴素贝叶斯算法分级的最小风险算法(52 燕山大学学报 2009 由实验结果可知，随着样本数的增多，3 种模 型的分类效果都有所提高。其中 BIM 模型查全率 很高，但准确率却很低，这在实际应用中是很难容 忍的；而 MM 模型在样本比较少的情况下查全率 偏低，准确率比较高； 结合二者的混合模型在查全 率和准确率上都整体优于二者，尤其是准确率，一 直保持很高的水平。但在样本数比较大时，混合模 型在查全率上没有优势， 综合考虑查全率和准确率 的情况下 HM 模型的效果略胜一筹。 这种改进使得在文本训练阶段， 机器学习的速 度

18、得到很大提升， 这是多重贝努利模型计算方法相 对简单所带来的，尤其在处理大量训练样本的时 候， 效果非常明显。而利用多项式模型在分类阶段 使用时， 可以更加有效的注意到在某一文档中多次 出现的 Token 单元，得到更好的分类效果。 子及采用不同的 计算模型的方法对朴素贝 叶斯算法进行改进， 实验证明使贝叶斯过滤器取得 了更好的过滤效果。文中虽然对某些问题做了探 讨，但仍有许多亟待解决的问题值得拓展研究。 例 如：如何处理中文垃圾邮件过滤过程中的分词问 题， 如何处理图片格式的邮件及含病毒附件的邮件 等等。这也是下一阶段需要研究的重点。 参考文献 1 Zhou Jianying, Chin W

19、ee-Yung, Roman Rodrigo, et al. An effective multi-layered defense framework against spam J. Information Security Technical Report, 2007,12 (3: 179-185. 2 Deepak P, Parameswaran S. Spam Filtering using Spam Mail Communities C /Proceedings IEEE SAINT, 2005: 377-383. 3 张文良, 黄亚楼, 倪维健. 基于差分贡献的垃圾邮件过滤特征 选择

20、方法 J. 计算机工程. 2007,33 (8: 80-82. 4 李翔鹰, 叶枫. 一种基于多贝叶斯算法的垃圾邮件过滤方法 J. 计算机工程与应用. 2006,42 (31: 114-116. 5 Wittern I H, Frank E. Data mining practical machine learning tools and techniques M. 2nd edition. San Francisco, CA: Morgan Kaufmann Publisher, 2005: 88-97. 5 结束语 基于贝叶斯的垃圾邮件过滤器是目前比较高 效的垃圾邮件过滤技术之一， 它已经开始广泛的使 用到垃圾邮件过滤领域。 本文通过引入最小损失因 Research and improvement of spam filter technology based on Bayesian ZHANG Fu-zhi, WU Zhao-hui, YAO Fang (College of Information Science and Engineering, Yanshan University, Qinhuangdao, Hebei 066004, China Abs