张付志.tpf

Size: px

Start display at page:

Download "张付志.tpf"

僻坦耿
5 years ago
Views:

1 第卷第期燕山大学学报年月文章编号 : X (2009) 基于贝叶斯算法的垃圾邮件过滤技术的研究与改进张付志, 伍朝辉, 姚芳 ( 燕山大学信息科学与工程学院, 河北秦皇岛 ) 摘要 : 随着电子邮件的应用与普及, 垃圾邮件的泛滥也越来越多地受到人们的关注本文对基于贝叶斯的垃圾邮件过滤器的原理及其关键技术进行了详细的描述针对朴素贝叶斯模型对分类信息过度简化和准确率低等缺点, 通过引入分级的最小风险算法和对多项式和多重贝努利估计模型进行混合的方法分别对贝叶斯过滤器进行了改进, 并进行了实验实验结果表明, 改进后的贝叶斯过滤器具有了更好过滤效果关键词 : 垃圾邮件 ; 贝叶斯过滤器 ; 最小风险 ; 估计模型中分类号 :TP 文献标识码 :A 引言随着电子邮件的普及, 垃圾邮件的泛滥也越来越多地受到人们的关注中国互联网协会反垃圾邮件中心在年月日发布的年第四次中国反垃圾邮件状况调查报告显示, 中国互联网用户平均每周收到垃圾邮件封, 已经连续多次超过了正常邮件的数量大量的垃圾邮件不仅占用了网络传输带宽, 影响正常网络通信, 更浪费了人们的时间和精力垃圾邮件的检测和过滤已经迫在眉睫目前主要的垃圾邮件过滤技术有类 : ) 基于域名和路由等的过滤技术: 包括黑白名单实时黑名单反向域名检测等技术 ; ) 基于行为的过滤技术 : 包括过滤群发流量监控挑战回应和蜜罐技术等 ; ) 基于内容的过滤技术 : 包括规则 ( 集 ) 匹配朴素贝叶斯 ( ) 支持向量机 ( ) 近邻法 ( ) 最大熵值法等基于内容的过滤技术是目前垃圾邮件过滤技术应用的主流, 而在基于内容的垃圾邮件过滤方法中, 朴素贝叶斯算法因其既实现了自学习的功能, 又满足了个性化的要求, 故而在垃圾邮件过滤中得到广泛的应用本文在对贝叶斯过滤器分析的基础上, 引入基于分级的最小风险算法, 并提出了一种结合多重贝努利和多项式的混合估计模型在此基础上对贝叶斯过滤器进行了改进, 并进行了实验对比贝叶斯过滤器贝叶斯定理贝叶斯定理是由托马斯贝叶斯 ( ) 提出的计算概率的一种方法它是通过对某一事件过去发生概率情况的考察, 大体可以推断出当前这一事件发生的概率它的形式化表述为 : 设试验的样本空间为, 为的事件, 为的一个划分, 且, 则贝叶斯分类器贝叶斯分类器是将贝叶斯定理应用到文本分类领域, 通过计算属于各个类别的概率, 将文本归为概率最大的一类可采用向量空间模型 ( ) 来表示文本, 即文档被表示成向量的形式 : 或者, 是特征项, 可以是收稿日期 : 基金项目 : 河北省自然科学基金资助项目 ( ) 作者简介 : 张付志 ( ), 男, 河南南阳人, 博士, 教授, 主要研究方向为数据库技术网络资源共享与管理智能网络信息处理网络与信息安全, :

2 燕山大学学报字词短语或者是某种概念是的权值, 可, 是邮件选取特征项, 是的权以用文档频度词频或布尔值来表示另有变量值垃圾邮件判定中的邮件类别 : 是类别集合中的一个元素对一邮件分类器的任务就是计算邮件待分类邮待分类文本, 则样本属于类别件是垃圾邮件的概率, 如果它超过某一阈值则认为的条件要满足 : 该邮件为垃圾邮件假设一封新邮件根据贝叶斯理论, 未知邮件属于垃圾邮件类别的概率计算公式为即将分类到概率值最大的相应类别中去, 利用贝叶斯公式计算文本属于某个类别的概率为式中, 是类的先验概率 ; 是指发生的概率, 由全概率公式得其中, 指垃圾邮件中中所有特征项同时出现的概率 ; 指选取样本中垃圾邮件的概率当大于或大于某个阈值时则认为该邮件为垃圾邮件贝叶斯过滤器模型关键技术分词对于同一篇文档, 不变是指类中发生的类条件概率, 也叫似然函数, 对于特征数较大, 而且特征变量之间相互依存度较高时, 它的计算比较复杂为简化计算, 可假定各个特征变量之间相互独立, 这样就引出了朴素贝叶斯分类器模型对于给定的分类变量, 假设各特征项相互独立, 则有故而其中贝叶斯过滤器贝叶斯过滤器实际上是贝叶斯分类器的一种, 它是将垃圾邮件过滤问题看成是垃圾邮件文本的二值分类问题对于每一个邮件样本, 使用向量空间模型对其进行形式化描述, 所谓分词就是把一个句子按照其中词的含义进行切分, 将文本转化成为可以识别的词或词组的单元邮件过滤器效果好坏, 与分词算法的优劣有着不可分割的关系字母语言由明显的单词构成, 单词中间一般都有明显分隔符, 便于提取和处理而在中文邮件处理中, 需用分析中文语言的特点, 实现中文邮件中词语的合理分词目前中文的分词算法有许多种, 如机械分词法基于理解的分词法基于统计的分词法和不基于语义的分词法 ( ) 等特征提取原始的特征词库十分庞大, 由这些特征词组成的向量维数也十分惊人在这些特征词中, 有些对区分正常邮件和垃圾邮件所起到的作用不但非常小, 有时还会引起噪声, 导致过度拟合特征提取就是为了降低向量空间的维数, 提高分类效果, 减小计算复杂度, 从而努力移除原始特征中不带分类信息或者带信息比较小的词主要的思路和方法是 : 首先对文本进行预处理, 去掉多次出现但不表现文本主题的特征词 ( 如 : 连词量词语气助词感叹词等 ) 以及文本中出现频率过少的词, 进行粗糙降维 ; 然后构造一些评

3 第期张付志等基于贝叶斯算法的垃圾邮件过滤技术的研究与改进价函数来计算特征词与类之间的关系, 通过计算结果选取预定数量的最优特征词, 从而提高分类的精度常用的特征提取方法有 : 文档频度信息增益期望交叉熵互信息等对于同一封邮件而言在特征提取过程中, 特征太少, 不能全面表现邮件的内容, 区分度不够 ; 特征太多, 又有一些无关的特征引入了分类噪声有实验数据表明 : 当中文语料的特征项集合大小为时, 精多变量贝努利事件模型确率和召回率都相对较高 ; 对英文语料库, 其最佳多变量贝努利模型 (, 特征集合大小为 ) 不考虑特征词出现的频率, 特估计模型征词权重用布尔模型来表示设表示特征在文在贝叶斯假设的基础上, 文本可以看作是若干词汇的集合, 可以认为文本是这些词汇按照一定的方式产生的根据产生的方式不同, 贝叶斯分类算法有两种概率估计模式 : 基于词频的多项式事件模型本中出现的情况, 应用到垃圾邮件过滤中表示出现不出现, 则有多项式事件模型 (, ) 需考虑词频, 即每个特征词出现看作事件, 文本是这些事件的集合设文本的长度 ( 即文本中包含的词数 ) 为, 表示特征词在文本中的出现次数, 为特征数量, 则符合多项式分布, 则有可以看出, 如果特征在文本中出现, 乘的项是其中, 不出现, 乘的项是垃圾邮件中有特征项出现的文本数量垃圾邮件的文本数量应用到垃圾邮件过滤中为平滑处理其中垃圾邮件所有文本中特征项出现的次数垃圾邮件的所有文本中特征词总数垃圾邮件中有特征项出现的文本数量垃圾邮件的文本数量为类别的个数, 在这种二值分类的情况下取根据全概率公式, 有为了避免分母为, 需对上式进行平滑处理根据贝叶斯公式可知垃圾邮件所有文本中特征项出现的次数垃圾邮件的所有文本中特征词总数对贝叶斯过滤器的改进引入分级的最小风险算法到从实际应用的效果来看, 准确率和均达以上, 完全能满足一般用户对电子邮件的需

4 燕山大学学报求, 但对于一些严重依赖电子邮件的商业机构或组织来说, 一封重要的商业邮件被误判为垃圾邮件而准确性通过实验表明, 在训练阶段, 如果训练文档比被过滤所带来的损失往往比封垃圾邮件被误判较充足, 即使不考虑词频信息, 也可以得到很好的为合法邮件严重的多也即是说用户宁可接受多封分类效果, 这样可以使用不考虑词频的算法来简化垃圾邮件也不愿意漏掉一封正常邮件, 因此引入代训练阶段的计算而在分类阶段, 针对某一文档, 价因子来进行描述可以认为把正常邮件错判成单词在文档中的频率往往就显得比较重要, 这时往垃圾邮件的代价是把垃圾邮件判为正常邮件的往需要考虑词频来进行计算所以, 本文设计的邮倍, 只有当时, 才判件过滤器中, 将两种模型相结合, 在训练阶段使用定邮件为垃圾邮件又因为多重贝努利模型对单词的先验条件概率进行估计,, 则有而在分类阶段采用多项式模型这种方法即考虑到了词频的作用, 又兼顾到了训练阶段的计算复杂度只有当时, 才认为邮件为垃圾邮件这就是基于最小风险的贝叶斯过滤器模型由等人的实验可知, 当时, 其准确率可高达在此基础上引入一种多级邮件的思路在新邮件到来时, 计算值, 然后进行判断 : ) 当时, 判定为垃圾邮件过, 过滤之 ; 实验及评价评价体系设待测的邮件集合中共有封邮件, 如表示表垃圾邮件过滤系统判定情况分布所 ) 当时, 判定为正常邮件, 保存到收件箱中 ; ) 当时, 判定为可疑邮件, 保存到可疑邮箱中, 设置邮件摘要, 经用户人工判断后通过特征加权的方法进行二次学习, 直到再次满足分类要求这种方法即保证了垃圾邮件的过滤效果, 又可以减少误判所带来的损失, 并对其中被错误分类的邮件通过用户识别后再利用贝叶斯算法对其重新进行训练, 使系统能够不断地更新自身的识别能力, 从而达到动态更新系统识别性能的效果, 这种方法对正确率要求比较严格的用户非常适用判定为垃圾邮件判定为正常邮件际的垃圾邮件数目, 实际为垃圾邮件其中, 数目通常可以采用以下的评价指标 : ) ( 召回率, ): 实际为正常邮件, 为实, 为实际的正常邮件正确判定为垃圾邮件的数目实际的垃圾邮件数目即垃圾邮件的检出率, 反映过滤系统发现垃圾邮件的能力当越大时, 漏网的垃圾邮件数越少, 系统性能也越好 ; 对估计模型的改进 ) 准确率 ( 正确率, ): 多重贝努利模型和多项式模型, 各有不同的适用范围多重贝努利模型不考虑词频信息, 这可能混淆重要特征和非重要特征而多项式模型虽然考虑词频, 却认为同一文档中多次出现同一特征是独立的, 这种假设加大了高频词对分类的影响, 在训练时可能误导特征对类别的影响, 影响分类结果的正确判定的垃圾邮件数判定为垃圾邮件的数目即垃圾邮件的检对率, 反映找对垃圾邮件的能力准确率越高, 表示将合法邮件误判为垃圾邮件的可能性越小, 进而使系统性能越好

5 第期张付志等基于贝叶斯算法的垃圾邮件过滤技术的研究与改进实验结果分析本文实验完全采用英文邮件样本, 英文语料采用公开的垃圾邮件公共词料库中语料共有封邮件, 包含封垃圾邮件封正常邮件将语料分为份, 每份大约篇, 每次取一定的份数作为训练集, 在剩余的邮件中另取一份作为测试集, 进行实验实验对比朴素贝叶斯算法与引入分级的最小风险算法的贝叶斯过滤器的过滤效果测试过程分别单独使用朴素贝叶斯算法和引入分级的最小风险算法进行比较, 在实现分级的最小风险算法实验过程中将正常邮件和可疑邮件保留, 将垃圾邮件过滤, 并对分类错误进行二次学习不断调整训练样本集的大小, 不考虑被判为可疑邮件的情况下, 对比两种算法的实验结果其和准确率对比如所示从实验结果可以看出, 使用分级的最小风险算法在不考虑可疑邮件的情况下, 准确率较朴素贝叶斯算法有明显的提高, 但是却明显下降, 这并不难理解, 值取一个很大值后, 判断为垃圾邮件的阈值明显提高, 有更多的邮件被判为可疑邮件, 从而导致下降, 准确率上升如果将可疑邮件综合考虑的话, 改进后的算法总体优于朴素贝叶斯算法, 而这种改进更适合于对准确率要求严格的用户使用实验对比多重贝努利模型 ( ) 多项式事件模型 ( ) 和混合模型 (, ) 种模型的过滤效果依次从训练集中随机选取不同数量的邮件用于训练, 分别用和种不同的分类模型实现基于朴素贝叶斯算法的邮件过滤, 使用信息增益作特征提取方法, 每次提取单词表左右的特征词综合考虑它们的和准确率如所示朴素贝叶斯算法分级的最小风险算法 ( ) 两种算法实验结果对比种模型实验结果对比朴素贝叶斯算法分级的最小风险算法 ( ) 两种算法实验结果准确率对比种算法实验结果准确率对比

6 燕山大学学报由实验结果可知, 随着的增多, 种模子及采用不同的计算模型的方法对朴素贝型的分类效果都有所提高其中模型叶斯算法进行改进, 实验证明使贝叶斯过滤器取得很高, 但准确率却很低, 这在实际应用中是很难容了更好的过滤效果文中虽然对某些问题做了探忍的 ; 而模型在样本比较少的情况下讨, 但仍有许多亟待解决的问题值得拓展研究例偏低, 准确率比较高 ; 结合二者的混合模型在和准确率上都整体优于二者, 尤其是准确率, 一直保持很高的水平但在比较大时, 混合模如 : 如何处理中文垃圾邮件过滤过程中的分词问题, 如何处理片格式的邮件及含病毒附件的邮件等等这也是下一阶段需要研究的重点型在上没有优势, 综合考虑和准确率的情况下模型的效果略胜一筹参考文献这种改进使得在文本训练阶段, 机器学习的速度得到很大提升, 这是多重贝努利模型计算方法相对简单所带来的, 尤其在处理大量训练样本的时候, 效果非常明显而利用多项式模型在分类阶段使用时, 可以更加有效的注意到在某一文档中多次出现的单元, 得到更好的分类效果结束语张文良黄亚楼倪维健基于差分贡献的垃圾邮件过滤特征选择方法计算机工程李翔鹰叶枫一种基于多贝叶斯算法的垃圾邮件过滤方法计算机工程与应用基于贝叶斯的垃圾邮件过滤器是目前比较高效的垃圾邮件过滤技术之一, 它已经开始广泛的使用到垃圾邮件过滤领域本文通过引入最小损失因 Research and improvement of spam filter technology based on Bayesian Abstract: Key words:

第卷第期年月半导体学报! " # $%&'%' $!&' #% #$1 /#1 $'! / ?/ ?/ / 3 0,?/ ) * +!!! '!,!! -. & ' $! '! 4% %&1)/1(7%&)03 (% )

第卷第期年月半导体学报! # $%&'%' $!&' #% #$1 /#1 $'! / ?/ ?/ / 3 0,?/ ) * +!!! '!,!! -. & ' $! '! 4% %&1)/1(7%&)03 (% ) 第卷第期年月!"# $%&'%' $!&'#%#$1/#1 $'! /18103 2?/03101?/18103 /3 0,?/0301.13 )*+!!! '!,!! -.&' $!'! 4%%&1)/1(7%&)03(%)%&,%*(1&0)%$-0*,%30)17*1*)0(+1(1+&1*+*),)1; &113(%44(10&.0701&0-&00*/)%;()1%-1+%&0)0*1*)%