改进的贝叶斯垃圾邮件过滤算法_王美珍

第37卷　第8期2009年　8月　华　中　科　技　大　学　学　报(自然科学版) J . Huazho ng U niv . of Sci . &T ech . (Na tural Science Edition ) V ol . 37N o . 8

　A ug . 　2009

改进的贝叶斯垃圾邮件过滤算法

王美珍　李芝棠　吴汉涛

(华中科技大学计算机科学与技术学院, 湖北武汉430074)

摘要:为了减少垃圾邮件误判造成的影响, 在传统的贝叶斯算法基础上提出了相应的改进措施:引入损失因子来评估垃圾邮件误判件时带来的风险. 通过理论推导和实验验证, 得出损失因子的最佳值, 来改善正常邮件的误判问题. 最后通过实验测试和结果分析, 表明基于改进的贝叶斯算法在垃圾邮件过滤中可以有效地减少误判, 使查全率和查准率达到一个比较理想的效果.

关　键　词:垃圾邮件; 最小风险; 贝叶斯; 损失因子; 误判; 风险

中图分类号:T P301. 6　　文献标识码:A 　　文章编号:1671-4512(2009) 08-0027-04

An improved Bayes algorithm for filtering spam e -mail

Wang Meizhen 　Li Zhitang 　W u H antao

(Co llege o f Co mputer Science and T echno log y , H uazhong Univ ersity of

Science and T echno lo gy , Wuhan 430074, China )

A bstract :In o rder to reduce the influence of spam false negative result , an improment solutio n based

on the traditio nal Bayesian algo rithm is propo sed , in w hich the loss factor is introdued to evaluate the risk o f spam false neg ative ra te . Through the theory inference and experim ental verificatio n , the best value of the lo ss facto r w as obtained , w hich can improve the misjudg ment problem of the Bayesian al -g orithm . Lastly , by experiments te sting and ianaly sis , the result indicats that the improved Bayesian algo rithm can reduce the false neg ative e rror rate w hen filtering spam e -mail , and take the recall and precision rate s into correspondly ideal effect .

Key words :spam e -mail ; minim um risk ; Bayesian ; loss factor ; false regative ; risk 　　垃圾邮件的过滤算法有很多种, 其中最有代表性的是决策树算法、Bo osting 算法、支持向量机、k 近邻算法、贝叶斯算法等. 目前使用最广泛的是基于贝叶斯模型的统计过滤方法. 垃圾邮件过滤其实就是邮件分类问题, 把邮件分为垃圾邮件和正常邮件. 这就可以应用贝叶斯定理, 通过对已经正确分类的邮件来预测新接收的邮件是否为垃圾邮件. 贝叶斯算法中用得最多的是朴素贝叶斯算法[3～5]. 它是基于各个特征项之间是相互独立的这个假设前提的. 由于简单的二分类问题不可避免地带来一些错误判断, 例如将正常邮件判断为垃圾邮件, 将垃圾邮件判断为正常邮件, 因此本文在传统贝叶斯算法的基础上引入损失因

收稿日期:2008-12-29.

作者简介:王美珍(1974-) , 女, 讲师, E -mail :mzw ang @mail . hust . edu . cn .

基金项目:国家自然科学基金资助项目(60573120) ; 国家高技术研究发展计划资助项目(2007A A 01Z420) .

[1]

[2]

子, 用来描述将正常邮件判为垃圾邮件时带来的损失, 探讨通过对损失的控制达到最好的分类效果, 对这种算法称之为最小风险的贝叶斯算法.

1　改进的朴素贝叶斯算法

在电子邮件的分类当中, 有两种分类错误是用户不愿意看到的:一种是将垃圾邮件分类到非垃圾邮件当中去; 另一种是将非垃圾邮件分类到

垃圾邮件中去. 第一种分类错误将使用户消耗一点时间浏览垃圾邮件, 而第二种分类错误将有可能使用户错失正常邮件. 由于这两类错误造成的损失相差很大, 因此很多用户宁愿每天花很多时

·28·

　　华　中　科　技　大　学　学　报(自然科学版) 　第37卷

间浏览大量垃圾邮件从而找出正常邮件, 也不愿轻易使用垃圾邮件过滤设备. 本文提出的贝叶斯改进算法就是利用贝叶斯的最小风险决策把各种

分类错误而引起的损失考虑进去的贝叶斯决策法则[6～10].

在朴素贝叶斯算法的基础上, 考虑两种分类错误所带来的风险或损失因素, 设决策空间由两个决策即a i (i =0, 1) 组成, 损失因子为λ(a i , c j ) , 表示当真实状态为c j 而采取的决策为a i 时所带来的损失. 引入损失概念后, 不能只是根据P (c j X ) 的大小来做决策, 而必须考虑所采取的决策是否使损失最小. 因此对于一个邮件X , 如果采取决策a i , 它的期望损失为

m

　R (H am |D )=1×P (c =1|D ) +0×P (c =0|D )=P (c =1|D ) . 因此文本D 决策为垃圾邮件的风险为

R (Spam |D )=k (1-P (c =1|D ) ) . 　　决策为垃圾邮件时, 要使得风险最小化, 需要满足R (Spam D )

P (c =1|D )>k /(k +1) .

(3)

　　令k /(k +1) =θ, 也就是说, 当P (c =1 D ) >θ时, 可保证决策为垃圾邮件的风险比决策为合

法邮件的风险小, 这种情况下分类器判定为垃圾邮件.

　R (a i |X )=

j =1

(a i , c j ) ·∑λ

(1)

2　实验

2. 1　评价标准

采用的评价标准如表2所示. 设N 为邮件的

总数, 则N =I +J +K +L .

表2　评价标准表

结果实际是正常邮件实际是垃圾邮件

系统判定为正常邮件

I K

系统判定为垃圾邮件

J L

P (c j |X ) 　(m =1, 2) .

　　设c 0代表垃圾邮件类, c 1代表正常邮件类. 过滤邮件时希望损失最小, 最小风险朴素贝叶斯判别规则为:若R (a i X ) =min R (a j X ) (j =0,

1) , 则X 属于c i 类, 采取决策a i ; 当R (a 0 X ) λ(a 0, c 1) , 利用式(1) 的结果得出决策规则

　P (c j ) x i |c j ∏P (

i

　　a . 查准率, 分类器在某一类别中做出的正确分类与分类器在该类上做出的所有分类的百分

比, 精度越高表明分类器在该类上出错的概率越小, P =[I /(I +K ) ]×100%;

b . 查全率, 分类器在某一邮件类别中做出的正确分类与该类实际应有分类数目的百分比, 查全率越高表明分类器在该类上可能漏掉的垃圾邮

P (c 1, c 2, …, c n )>λ(a 0, c 1) . (2)

件就越少, R H =[I /(I +J ) ]×100%;

c . 精确率, 分类器对所有邮件的判对率,

A c =[(I +L ) /N ]×100%.2. 2　测试环境和数据源

本系统测试过程都是在局域网内进行的, 测试的拓扑如图1所示.

　　下面应用最小风险的朴素贝叶斯算法进行分析, 定义决策表见表1. 表1中Spam 代表垃圾邮

表1　最小风险朴素贝叶斯决策表真实状态Spam Spam

H am H am

决策Spam Ham Spam Ham

决策损失

01k 0

件, Ham 代表合法邮件或正常邮件, 将H am 误判为Spam 的损失风险定义为k . 通常将H am 判定为Spam 所带来的损失应该比将Spam 判定为H am 的损失大, 所以, 默认状态k ≥1, 通常k 为经验值.

假定H am 分类为C 0, Spam 分类为C 1.

将文本D 决策为合法邮件的条件风险为

图1　测试拓扑图

邮件用户系统:Window s XP . 网关系统版本:Linux , 内核版本2. 4. 20-8. 邮件客户端工具:

第8期　　王美珍等:改进的贝叶斯垃圾邮件过滤算法　　　　　

·29·

Fo xmail6. 0, Outlo ok Ex press6. 0.

在测试开始前, 需要提供测试系统的是邮件系统的训练数据集, 即需要一定的邮件语料. 在本课题中采用的是Spam Assassin 语料库, 它包含1897封垃圾邮件和4150封非垃圾邮件, Spam Assassin 语料可以从http :∥w w w . Spam assas -sin . org 获得. 但是这些邮件集都是英文邮件语料, 由于目前中文邮件语料相对较少, 因此用于测试的中文邮件来自于个人邮箱中收集到的中文正常邮件和垃圾邮件. 总邮件数200封, 其中垃圾邮件和正常邮件各100封, 以下的测试数据都是基于此测试集的测试数据. 2. 3　实验结果和分析

对垃圾邮件过滤系统进行了测试, 分别使用基于朴素贝叶斯和基于最小风险决策贝叶斯算法构建邮件过滤器, 进行邮件训练和邮件判别试验, 在不同训练集规模、不同特征数量、不同阈值以及不同的判别算法等因素下, 都对评估指标产生了影响, 分别得到了不同的判别结果, 也显示了不同的查全率和查准率, 其中着重对基于最小风险决策的贝叶斯方法进行邮件判别做了更加详细的实验测试, 在设定不同阈值θ、不同特征数量的情况下, 得到不同的判别结果, 通过不断调整阈值θ, 直至达到较理想的查全率与查准率. 将此时得到的θ用于构造邮件过滤的原型系统, 得到判别质量相对较好的过滤器. 图2给出主要的几类实验结果

.

θ0. 50

0. 550. 580. 600. 70

表3　不同阈值θ对性能影响查全率/%50. 50

80. 4390. 3492. 3695. 20

查准率/%80. 31

90. 6091. 4298. 6095. 30

精确率/%70. 86

82. 2089. 4090. 5392.

47

图3　不同阈值θ对性能的影响

随着阈值的增大, 查全率和查准率也在增加, 但查全率的指标没有查准率的指标好, 因为根据增加的阈值可知, 误判减少, 判断更准确, 但有可能漏掉了垃圾邮件. 当然本文中, 风险因子k 的有效值

是在一定的区间中变化的, 在本课题中规定的风险因子大小为1. 0～3. 0, 经过多次选取k 的大小, 最终确定表3中5个有代表性的阈值. 从图3可以看出, 当阈值为0. 60时, 各项性能指标较好. 在本过滤系统中, 选用该阈值对应的因子k =1. 5可以得到较好的分类结果.

同时, 在测试过程中也对比了朴素贝叶斯算法和改进的朴素贝叶斯算法在性能方面的表现, 见表4. 从表中可以看出, 采用贝叶斯算法进行分

表4　朴素贝叶斯与最小风险贝叶斯对比

查全率/%查准率/%精确率/%

朴素贝叶斯算法

k =1. 00最小风k =1. 20险贝叶k =1. 38

斯算法k =1. 70

k =2. 00

50. 62

50. 6279. 2588. 6893. 7695. 54

80. 33

80. 3389. 1490. 2698. 8996. 45

70. 45

70. 4582. 2490. 1490. 5191. 63

图2　训练集大小对分类效果影响

该实验是基于朴素贝叶斯方法进行, 从上表可以看出, 训练集的大小对查全率查准率以及精确度都有较大的影响, 一般来说, 训练集中邮件样

本越多, 邮件过滤的性能越好.

在测试过程中着重关注了与不同的风险因子k 相对应的阈值θ, 根据前面的讨论, θ=k /(k +1) . 采用基于最小风险的朴素贝叶斯算法进行分类过滤时, 需要对阈值进行调整和选择, 经过测试得出测试数据见表3.

从图3所示的折线图可以看出一定的规律:

类时, 系统稳定性型较强, 最小风险的贝叶斯算法在其基础上, 增加了风险损失因子k 之后, 所得到的查全率相对于朴素贝叶斯来说有所增加, 表明引入风险因子之后, 合法邮件判断为垃圾邮件的概率减少了, 降低了误判损失, 但同时垃圾邮件有可能被判为合法邮件, 所以k 值增大之后, 查全率增加, 但是查准率会有所下降, 因此为了取得较好的性能指标, 要选取合适的损失因子.

通过实验表明, 如果选择了合适的损失因子,

·30·

　　华　中　科　技　大　学　学　报(自然科学版) 　第37卷

参考文献

Spring er -V erlag , 1998:4-15.

[5]Sa Hami M , D umais S , H ecker ma n D , et al . A

Bay esian appro ach to filte ring junk E -mail [C ]∥Pr oc of AA A I Wo rksho p o n Learning fo r Te xt Catego riza -tio n . M adison Wisconisin :[s . n . ], 1998:55-62. [6]Y aping L , Zhiping C , Xiaolin Y , e t al . M ail filtering

based on the risk minimizatio n Bay esian alg orithm [C ]∥P roceedings -industrial Sy stem and Eng ineer -ing , 2002, 17(3) :282-285.

[7]石霞军, 林亚平, 陈治平. 基于最小风险的贝叶斯邮

件过滤算法[J ]. 计算机科学, 2002, 29(8) :50-51. [8]王　雷, 林亚平, 彭　雅, 等. 基于认知学习的最小风

险贝叶斯邮件过滤算法[J ]. 系统仿真学报, 2004(3) :413-416.

[9]邢　莉, 喻建平. 基于最小风险贝叶斯涉密邮件统计

分类算法[J ]. 深圳大学学报:理工版, 2008(7) :282-285.

[10]王　涛, 裘国永, 何聚厚. 新的基于最小风险的贝叶

斯邮件过滤模型[J ]. 计算机应用研究, 2008, 25(4) :1147-1149.

[1]K olcz A , A lspecto r J . SVM -based filtering of email

spam with content -specific misclassificatio n costs [C ]∥Pro c ICDM -2001Wo rkshop on Te xt Mining . Sam Jose :[s . n . ], 2001:234-245.

[2]H an E , K ary pis G , K uma r V . T ex t catego riza tion u -sing weight adjusted k -N earest Neig hbo r classifica tion [C ]∥P roc o f P acific -A sia Co nfere nce o n K no wledg e Discov ery and Data M ining . Hong Ko ng :Spring er , 2001:345-349.

[3]Androutsopoulo s I , P aliouras G , K arkaletsis V , et

al . L earning to filter spam E -mail :a co mpa riso n of a naive bay esian and a memo ry -based appro ach [C ]∥P roc o f the 4th Eur opean Conference on P rinciples and Prac tice o f K now ledge Disco ver y in Da ta base (PK DD2000) . Ly ong F rance :[s . n . ], 2000:1-13. [4]L ewis D D . N aive Bay es a t fo rty :the independence

assumptio n in info rmatio n re triev al [C ]∥P roc of the 10th European Co nf o n M achine Lear ning . [s . l . ]:

第二届光子与光电子学会议在我校召开

8月8～10日, 第二届光子与光电子学会议(POEM 2009) 在管理学院报告厅

隆重举行. 本次会议由中国光学学会、华中科技大学、湖北省科学技术厅、武汉东湖新技术开发区管委会、中国国家光电子信息产业基地主办, 武汉光电国家实验室(筹) 承办, 得到中华人民共和国教育部、美国激光协会、美国光学学会、《Frontiers of Optoelectro nics in China 》、《光学与光电技术》、光电新闻网、中国光学期刊网、中国学术会议在线、广东省光学学会激光加工专业委员会等多家单位和媒体的支持.

大会邀请到1999年诺贝尔化学奖得主、美国科学院、美国哲学院、第三世界科学院、欧洲艺术科学和人类学院院士、埃及最高国家荣誉奖获得者、美国加州理工学院教授Ahmed H assan Zew ail 等作大会特邀报告, 来自多个国家的84名光电专家作专题会议邀请报告. 内容涉及光纤通信与传感技术(FOCS ) 、工业激光及应用技术(ILAT ) 、光电子器件与集成(OEDI ) 、光存储及新型存储技术(OSNS ) 、太阳能电池、固态照明与信息显示技术(SSID ) 、生物医学光子学与成像技术(PIBM2009) 等6个领域. 会议的宗旨在于聚焦光电子领域科学前沿和行业关键技术, 把握未来发展趋势, 是一次覆盖光电子领域的大规模多学科综合性国际会议. 主办方邀请国内外光电子领域知名学术机构和组织作为技术支持单位, 借助国际平台共同举办一个集学术性和实用性于一体的高水平、高质量学术盛会. 500多名国内外知名专家、学者、经济金融界专家及中外投资、创业者和企业家齐聚一堂, 共同探讨当前光电学科领域面临的机遇和挑战.