贝叶斯邮件过滤算法理论收集整理[转]

一、 贝叶斯垃圾邮件过滤算法理论介绍





二、 贝叶斯过滤算法的基本步骤

  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 

    (注明:在实际应用中不可以将概率指定为1或者0,可以用相关的高概率或者低概率值来代替。)

  当新到一封含有“功律”的邮件时,我们可得到两个TOKEN串:功 律

  查询哈希表 hashtable_probability 可得:

  P (垃圾邮件 | 功) = 1

  P (垃圾邮件 | 律) = 0

  此时该邮件为垃圾邮件的可能性为:

  P= ( 0*1 ) /[0*1+ ( 1-0 ) * ( 1-1 ) ] = 0

  由此可推出该邮件为非垃圾邮件。

posted on 2012-10-13 19:46 挑灯看剑 阅读(270) 评论(0)  编辑 收藏 引用 所属分类: algorithm

只有注册用户登录后才能发表评论。
<2018年5月>
293012345
6789101112
13141516171819
20212223242526
272829303112
3456789

导航

公告

【自我介绍】 08年南开大学硕士毕业 最近关注:算法、Linux、c++、高并发 爱好:滑旱冰、打乒乓球、台球、保龄球

常用链接

随笔分类(139)

文章分类

我常去的网站

技术博客(都是大牛)

技术站点

搜索

积分与排名