2008年1月29日星期二

贝叶斯公式在处理垃圾邮件中的应用

贝叶斯公式在处理垃圾邮件中的应用
Thomas Bayes(1702-1763), 托马斯·贝叶斯是一位英国牧师数学家,1742年成为英国皇家学会会员1763年4月7日逝世,1763年,他发表了贝叶斯统计理论,即根据已经发生的事件来预测事件发生的可能性,贝叶斯理论假设:如果事件的结果不确定,那么量化它的唯一方法就是事件的发生概率。如果过去试验中事件的出现率已知,那么根据数学方法可以计算出未来试验中事件出现的概率。贝叶斯定理可以用一个数学公式表达。即贝叶斯公式。

贝叶斯定理(又被称为贝叶斯法则)是概率论中的一个结果,它跟随机变量的条件概率以及边缘概率分布有关。在有些关于概率的解说中,贝叶斯定理(贝叶斯更新)能够告知我们如何利用新证据修改已有的看法。

通常,事件A在事件B(发生)的条件下的概率,与事件B在事件A的条件下的概率是不一样的;然而,这两者是有确定的关系,贝叶斯定理就是这种关系的陈述。

作为一个规范的原理,贝叶斯定理对于所有概率的解释是有效的;然而,频率主义者和贝叶斯主义者对于在应用中概率如何被赋值有着不同的看法:频率主义者根据随机事件发生的频率,或者总体样本里面的个数来赋值概率;贝叶斯主义者要根据未知的命题来赋值概率。一个结果就是,贝叶斯主义者有更多的机会使用贝叶斯定理。

反垃圾邮件是具有相当难度的事情,垃圾邮件每天都在增加和变化。据Radicati估计2007年,垃圾邮件的比例将达到70%。现在的垃圾邮件发送者变得更加狡猾,采用静态反垃圾邮件技术很难防范。垃圾邮件发送者只要简单的研究一下现在采用了哪些静态反垃圾邮件,然后相应的改变一下邮件的内容或发送方式,就可以逃避检查了。

因此,必须采用一种新的技术来克服静态反垃圾邮件的弱点,这种技术应该对垃圾邮件发送者的各种伎俩了如指掌,还要能适应不同用户对于反垃圾邮件的个性化需求。这种技术就是贝叶斯过滤技术。

贝叶斯过滤技术的工作原理

根据贝叶斯理论,根据已经发生的时间可以预测未来事件发生的可能性。将该理论运用到反垃圾邮件上:若已知某些字词经常出现在垃圾邮件中,却很少出现在合法邮件中,当一封邮件含有这些字词时,那么他是垃圾邮件的可能性就很大。

1创建基于字词符号的贝叶斯数据库

用户首先需要对贝叶斯进行培训,即将邮件分类为垃圾邮件(用户不想要的)和正常邮件(用户想要的),贝叶斯将提取这些邮件样本中主题和信体中的独立字串,包括字词(word)和符号(token)(如$,IP地址,域名等),并建立相应的数据库。

2创建贝叶斯概率库

统计出每个字串在垃圾邮件中出现的概率以及在正常邮件中出现的概率,然后根据公式计算出邮件中含某字串则为垃圾邮件的概率。例如:在3000封垃圾邮件样本中"mortgage"(抵押)出现了400次,而在300封正常邮件中这个词出现了5次,那么其对应的垃圾概率为0.8889([400/3000] /[5/300+400/3000])。

3创建个性化的贝叶斯库(最符合您公司需求的贝叶斯库)

由于每个公司对所收到的邮件偏好是不同的,例如,某个金融类公司在正常邮件中可能经常用到"mortgage"这个词,如果使用静态的关键词过滤,就可能产生很多误判。如果采用贝叶斯过滤,在对贝叶斯进行培训的时候,将该公司的合法邮件(自然,很多都包含了"mortgage"这个词)分类为正常邮件。这样,垃圾邮件的识别率将更高,同时也使得误判率变得很低。

有些反垃圾邮件软件使用了比较初级的贝叶斯过滤机制,如outlook,foxmail等。他们采用的是通用化的贝叶斯数据库。这种贝叶斯不需要进行培训,但有两个明显的弱点:

1.如果采用通用化的贝叶斯过滤则很容易被专业的垃圾邮件发送者攻破从而绕过检查,但是如果采用个性化的贝叶斯,则他们很难攻破。

2.通用化的贝叶斯与您公司的邮件过滤要求不符,因此过滤效果通常不明显,并且可能产生较高的误判。

除了学习好的邮件之外,贝叶斯还应学习垃圾邮件,这些垃圾邮件样本应该包括了大量的已知垃圾邮件样本以及最新的变化了的垃圾邮件样本。这样才能达到最好的过滤效果,对最新的垃圾邮件样本的学习通常需要两周左右的时间。

4贝叶斯过滤器的处理过程。

贝叶斯过滤器学习了垃圾邮件样本及正常邮件样本后,每个字串代表的垃圾概率就被计算出了。

一封新的邮件到达时,这封邮件的内容将被分成字串(词或符号)。依据数据库中这些字词的概率通过公式[3]进行计算,贝叶斯将推算出这封邮件是垃圾邮件还是正常邮件。通常当贝叶斯计算出的垃圾邮件可能性高于某个数值(阈值)时,比如0.9,就判定这封邮件是垃圾邮件。


贝叶斯过滤的优点

――2003年5月BBC专题报道称,贝叶斯可以达到99.7%的垃圾邮件识别率,同时误判率极低。是目前最有效的反垃圾邮件技术。

1 贝叶斯过滤技术对邮件的所有内容进行分析,不仅仅是其中的某个关键词,而且他能判别邮件是垃圾邮件还是正常邮件。例如:包含“free”“cash”“发票”字样的邮件不一定是垃圾邮件,如果采用关键字过滤技术,显然难以达到理想的效果。而贝叶斯呢,即考虑了这些词在垃圾邮件中出现的概率又考虑了它在正常邮件中的概率,综合考虑这些因素才做出判断。可以说,贝叶斯具有一定的智能,它对邮件中的关键词汇能综合的进行评判,可以把握“好”与“坏”之间的平衡。显然,这种技术远远高于非1即0的静态过滤技术。

2 贝叶斯过滤技术具备自适应功能――通过学习新的垃圾邮件及正常邮件样本,贝叶斯将能对抗最新的垃圾邮件。并且对变体字有奇效。比如,垃圾邮件发送者开始使用"f-r-e-e"来代替“free”这样能够绕过关键字检查,除非"f-r-e-e"被加到新的关键字中。对贝叶斯而言,当它发现邮件中含有"f-r -e-e"时,由于正常邮件中从来没有发现这个词,因此他是垃圾邮件的可能性将急剧增加,"f-r-e-e"这个新词无疑成了垃圾邮件的指示器。在比如,垃圾邮件中用5e代替se,贝叶斯也推算出他是垃圾邮件的可能性也急剧增加。

3 贝叶斯过滤技术更加个性化。他能学习并理解用户对邮件的偏好。如前所述,‘mortgage’抵押一词对软件公司而言意味者垃圾,但对金融类公司则意味着好邮件。贝叶斯能根据用户的这种偏好进行处理。

4 贝叶斯过滤技术支持多语种或者说与编码无关。对于贝叶斯而言,他分析的是字串,无论他是字、词、符号、还是别的什么,当然更与语言无关。

5 贝叶斯过滤器很难被欺骗。垃圾邮件发送高手通常通过减少垃圾词汇(如free、viagra、发票)或者在信中多掺一些好的词汇(如合同、文件)来绕过检查一般的邮件内容检查,但由于贝叶斯具有的个性化色彩,要想成功的绕过贝叶斯的检查,他就不得不对每个收件人的偏好进行研究,这简直是“不可能完成的任务”。垃圾邮件发送者无法容忍的。若采用变化字,则如前所述贝叶斯判断其为垃圾邮件的可能性反而增加。

如何才能培训出好的贝叶斯过滤器

贝叶斯的样本数并不是越多越好,但一般需要超过一定的数量才能工作。要培训出比较好的贝叶斯,有如下建议:

1 不要过多的重复分类某一封或某一类邮件,以免概率失真(失衡),要分批分时间多次进行,这样样本分布广泛。

2 对要分类的邮件应认真看完,不要瞟一眼就分类。

3 如果邮件是垃圾邮件,但是和您公司的邮件或者和正常的邮件很接近,最好不要分类这种邮件。

4 如果这封邮件不是垃圾邮件,是那种在网络上订阅的邮件,如淘宝、当当等,最好把发件人加入白名单,而不要分类到贝叶斯中。

5 避免将哪些含有随机字词(贝叶斯中毒策略)的邮件进行分类。虽然新的贝叶斯系统提供了相应的保护机制。

6 样本的文字篇幅极大,请避免。(样本提供的数据将过于复杂);样本的文字篇幅极少,或者只有图,请避免。(贝叶斯针对的是字词概率)

好的贝叶斯通常需要两周左右的培训时间,虽然需要花些时间和精力,但是机遇总是惠顾勤奋的人,这些努力都是值得的。