分类: C/C++
2010-02-21 21:21:16
一、 贝叶斯反垃圾邮件技术介绍
贝叶斯是基于概率的一种算法,是Thomas Bayes:一位伟大的数学大师所创建的,目前此种算法用于过滤垃圾邮件得到了广泛地好评。贝叶斯过滤器是基于“自我学习”的智能技术,能够使自己适应垃圾邮件制造者的新把戏,同时为合法电子邮件提供保护。在智能邮件过滤技术中,贝叶斯(Bayesian)过滤技术取得了较大的成功,被越来越多地应用在反垃圾邮件的产品中。
二、 贝叶斯过滤算法的基本步骤
1. 收集大量的垃圾邮件和非垃圾邮件,建立垃圾邮件集和非垃圾邮件集。
2. 提取邮件主题和邮件体中的独立字符串,例如 ABC32,¥234等作为TOKEN串并统计,提取出的TOKEN串出现的次数即字频。按照上述的方法分别处理垃圾邮件集和非垃圾邮件集中的所有邮件。
3. 每一个邮件集对应一个哈希表,hashtable_good对应非垃圾邮件集而hashtable_bad对应垃圾邮件集。表中存储TOKEN串到字频的映射关系。
4. 计算每个哈希表中TOKEN串出现的概率P=(某TOKEN串的字频)/(对应哈希表的长度)
5. 综合考虑hashtable_good和hashtable_bad,推断出当新来的邮件中出现某个TOKEN串时,该新邮件为垃圾邮件的概率。数学表达式为:
A 事件 ---- 邮件为垃圾邮件;
t1,t2 …….tn 代表 TOKEN 串
则 P(A|ti)表示在邮件中出现 TOKEN 串 ti 时,该邮件为垃圾邮件的概率。
设:
P1(ti) = ( ti 在 hashtable_good 中的值)
P2(ti) = ( ti 在 hashtable_ bad 中的值)
则 P(A|ti) =P2(ti)/[(P1(ti +P2(ti)];
6. 建立新的哈希表hashtable_probability存储TOKEN串ti到P(A|ti)的映射
7. 至此,垃圾邮件集和非垃圾邮件集的学习过程结束。根据建立的哈希表 hashtable_probability可以估计一封新到的邮件为垃圾邮件的可能性。 当新到一封邮件时,按照步骤2,生成TOKEN串。查询hashtable_probability得到该TOKEN 串的键值。
假设由该邮件共得到N个TOKEN 串,t1,t2…….tn,hashtable_probability中对应的值为 P1 , P2 , ……PN , P(A|t1 ,t2, t3……tn) 表示在邮件中同时出现多个TOKEN串t1,t2……tn时,该邮件为垃圾邮件的概率。
由复合概率公式可得
P(A|t1 ,t2, t3……tn)=(P1*P2*……PN)/[P1*P2*……PN+(1-P1)*(1-P2)*……(1-PN)]
当 P(A|t1 ,t2, t3……tn) 超过预定阈值时,就可以判断邮件为垃圾邮件。
三、 贝叶斯过滤算法举例
例如:一封含有 “ 法无效字符轮无效字符功 ” 字样的垃圾邮件 A 和一封含有 “ 法无效字符律 ” 字样的非垃圾邮件 B 。 根据邮件 A 生成 hashtable_bad ,该哈希表中的记录为
法: 1 次
无效字符轮: 1 次
无效字符功: 1 次
计算得在本表中:
无效字符法出现的概率为 0.3
无效字符轮出现的概率为 0.3
无效字符功出现的概率为 0.3
根据邮件B生成hashtable_good,该哈希表中的记录为:
法: 1 次
律: 1 次
计算得在本表中:
法出现的概率为 0.5
律出现的概率为 0.5
综合考虑两个哈希表,共有四个 TOKEN 串:法无效字符论无效字符功无效字符律
当邮件中出现“法”时,该邮件为垃圾邮件的概率为:
P = 0.3/ ( 0.3 + 0.5 ) = 0.375
出现“无效字符轮”时,该邮件为垃圾邮件的概率为:
P = 0.3/ ( 0.3 + 0 ) = 1
出现“无效字符功”时,该邮件为垃圾邮件的概率为:
P = 0.3/ ( 0.3 + 0 ) = 1
出现“无效字符律”时,该邮件为垃圾邮件的概率为:
P = 0/ ( 0 + 0.5 ) = 0
由此可得第三个哈希表 hashtable_probability ,其数据为:
无效字符法: 0.375
无效字符轮: 1
无效字符功: 1
律: 0
当新到一封含有“功无效字符律”的邮件时,我们可得到两个TOKEN串:功 律
查询哈希表 hashtable_probability 可得:
P (垃圾邮件 | 功) = 1
P (垃圾邮件 | 律) = 0
此时该邮件为垃圾邮件的可能性为:
P= ( 0*1 ) /[0*1+ ( 1-0 ) * ( 1-1 ) ] = 0
由此可推出该邮件为非垃圾邮件。
四、总结
贝叶斯过滤器为什么能够工作得这么好呢?因为贝叶斯过滤器纯粹根据统计学规律运作,比起那些需要分析邮件句法或内容含义的过滤器来显然要简单的多,而且可计算性强得多。更重要的是,这些标记完全可以由用户根据自己所接收的垃圾邮件和非垃圾邮件来创建,因而可以获得一种对用户来说独一无二的过滤器。这意味着垃圾邮件发送者根本无法猜测出你的过滤器是如何配置的,从而有效地阻截住各类垃圾邮件。
不过,尽管贝叶斯过滤器非常有效,但它仍需要进行优化才能真正完美。比如它可以结合 “白名单”降低误报率,结合“黑名单”降低漏过率,还可以利用其他技术如源址认证使其成为更加精确的垃圾邮件过滤器。
设计优良的贝叶斯过滤器,可以识别99.7%以上的垃圾邮件,而且误判率极低,是目前
最有效的反垃圾邮件技术。这主要是因为贝叶斯过滤具有以下特点。贝叶斯过滤技术对邮件的所有内容进行分析,不仅仅是其中的某个关键词,而且它能判别邮件是垃圾邮件还是正常邮件。例如:包含"free""cash"" 发票"字样的邮件不一定是垃圾邮件,如果采用关键字过滤技术,显然难以达到理想的效果。而贝叶斯过滤技术既考虑了这些词在垃圾邮件中出现的概率、又考虑了 它在正常邮件中的概率,综合考虑这些因素做出判断。可以说,贝叶斯过滤技术具有一定的智能,它对邮件中的关键词能综合地进行评判,可以把握"好"与"坏" 之间的平衡。显然,这种技术远远高于非1即0的静态过滤技术。
贝叶斯过滤技术具备自适应功能。通过学习新的垃圾邮件及正常邮件样本,它 将能对抗最新的垃圾邮件,并且对变体字有奇效。比如,垃圾邮件发送者开始使用"f-r-e-e"来代替"free"这样能够绕过关键字检查,除非"f- r-e-e"被加到新的关键字中。而对贝叶斯过滤技术而言,当它发现邮件中含有"f-r-e-e"时,由于正常邮件中从来没有发现这个词,因此它是垃圾邮 件的可能性将急剧增加,"f-r-e-e"这个新词无疑成了垃圾邮件的指示器。再比如,垃圾邮件中用5ex代替sex,贝叶斯过滤技术也可推算出它是垃圾 邮件的可能性也急剧增加。
贝叶斯过滤技术更加个性化。它能学习并理解用户对邮件的偏好。如前所述,"mortgage"抵押一词对软件公司而言意味着垃圾,但对金融类公司则意味着邮件。贝叶斯过滤技术能根据用户的这种偏好进行处理。
贝叶斯过滤技术支持多语种,与语言编码无关。这是因为它分析的是字串,无论是数字、词、符号、还是别的什么,当然与语言无关。
贝叶斯过滤器很难被欺骗。垃圾邮件发送高手通常通过减少垃圾词汇(如free、viagra、发票)或者在信中多加入一些好的词汇(如合同、文件)来绕 过一般的邮件内容检查,但由于贝叶斯过滤技术具有个性化的色彩,要想成功地绕过它的检查,就不得不对每个收件人的偏好进行研究,这简直是"不可能完成的任 务",垃圾邮件发送者是无法容忍的。若采用变化字,则如前所述,贝叶斯过滤技术判断其为垃圾邮件的可能性反而增加。
实践也证明,贝叶斯过滤器在用户端和服务器中效果是非常明显的,如优秀的贝叶斯过滤器能够识别超过99.9%的垃圾邮件。