更好的贝叶斯过滤

January 2003

(本文是在 2003 年垃圾邮件大会上发表的演讲。 它描述了我为提高 垃圾邮件计划 中描述的算法性能所做的工作， 以及我未来计划做的事情。)

我想在这里介绍的第一个发现是一种用于 懒惰评估研究论文的算法。只需 写下你想要的任何内容，不要引用任何以前的工作， 愤怒的读者会给你发送所有你 应该引用的论文的参考文献。我发现了这个算法 是在“垃圾邮件计划”[1] 发表在 Slashdot 上之后。

垃圾邮件过滤是文本分类的一个子集， 这是一个成熟的领域，但关于 贝叶斯 垃圾邮件过滤本身的第一篇论文似乎是两篇 在 1998 年的同一个会议上发表的， 一篇由 Pantel 和 Lin [2] 发表， 另一篇由 微软研究院 [3] 的一个小组发表。

当我听说这项工作时，我有点惊讶。如果 人们四年前就开始研究贝叶斯过滤， 为什么不是每个人都在使用它？ 当我阅读这些论文时，我发现原因。Pantel 和 Lin 的过滤器是 两者中更有效的，但它 只捕获了 92% 的垃圾邮件，误报率为 1.16%。

当我尝试编写一个贝叶斯垃圾邮件过滤器时， 它捕获了 99.5% 的垃圾邮件，误报率低于 0.03% [4]。 当两个人 尝试同一个实验却得到截然不同的结果时，总是令人担忧。 这里尤其令人担忧，因为这两组数字 可能会得出相反的结论。 不同的用户有不同的需求，但我认为对于 许多人来说，92% 的过滤率和 1.16% 的误报率意味着 过滤不是一个可接受的解决方案，而 99.5% 的过滤率和低于 0.03% 的误报率意味着它是可接受的。

那么为什么我们会得到如此不同的数字？ 我没有尝试重现 Pantel 和 Lin 的结果，但 从阅读论文中，我发现五件事可能解释了 这种差异。

其中之一仅仅是他们用很少的 数据训练了他们的过滤器：160 封垃圾邮件和 466 封非垃圾邮件。 过滤器的性能应该仍然随着 如此小的数据集而不断提高。因此，他们的数字可能甚至不是他们算法性能的准确 衡量标准，更不用说 贝叶斯垃圾邮件过滤的总体性能了。

但我认为最重要的区别可能是 他们忽略了邮件头。对于任何从事 垃圾邮件过滤工作的人来说，这似乎是一个奇怪的决定。 然而，在我尝试编写的第一个过滤器中，我也忽略了 邮件头。为什么？因为我想让问题保持简洁。 当时我对邮件头了解不多，它们在我看来 充满了随机的东西。这里有一个教训要给过滤器 编写者：不要忽略数据。你可能会认为这个教训 太明显了，不值得一提，但我不得不多次学习它。

第三，Pantel 和 Lin 对标记进行了词干提取，这意味着他们将例如 “mailing”和“mailed”都简化为词根“mail”。他们可能 觉得他们被迫这样做是因为语料库的规模 太小，但如果是这样的话，这是一种过早的 优化。

第四，他们以不同的方式计算概率。 他们使用了所有标记，而我只 使用最重要的 15 个。如果你使用所有标记， 你往往会错过更长的垃圾邮件，即有人告诉你他们的人生 故事，直到他们通过某种多层次 营销计划致富。而且这样的算法 很容易被垃圾邮件发送者欺骗：只需添加一大块 随机文本来抵消垃圾邮件词语。

最后，他们没有偏向误报。 我认为 任何垃圾邮件过滤算法都应该有一个方便的 旋钮，你可以转动它来降低 误报率，以牺牲过滤率为代价。 我通过在非垃圾邮件语料库中将标记的出现次数 计算为两倍来做到这一点。

我认为将垃圾邮件过滤视为 一个纯粹的文本分类问题不是一个好主意。你可以使用 文本分类技术，但解决方案可以而且应该 反映文本是电子邮件，尤其是垃圾邮件 这一事实。电子邮件不仅仅是文本；它有结构。 垃圾邮件过滤不仅仅是分类，因为 误报比漏报糟糕得多，因此你应该将它们视为不同类型的错误。 而且错误的来源不仅仅是随机变化，而是 一个活生生的垃圾邮件发送者正在积极地努力破坏你的过滤器。

标记

我从 Slashdot 文章中了解到的另一个项目是 Bill Yerazunis 的 CRM114 [5]。 这是我刚刚提到的设计原则的反例。它是一个纯粹的文本分类器， 但它是一个如此惊人的有效分类器，以至于它设法 几乎完美地过滤了垃圾邮件，甚至不知道它 在做什么。

一旦我理解了 CRM114 的工作原理，就似乎 不可避免地，我最终将不得不从基于 单个单词的过滤转向像这样的方法。但首先，我想， 我看看我能用单个单词走多远。答案是， 出乎意料地远。

我主要一直在研究更智能的标记化。在 当前的垃圾邮件中，我已经能够实现接近 CRM114 的过滤率。这些技术大多与 Bill 的技术正交； 最佳解决方案可能会将两者结合起来。

“垃圾邮件计划”使用了一个非常简单的 标记定义。字母、数字、连字符、撇号、 和美元符号是组成字符，其他所有字符 都是标记分隔符。我也忽略了大小写。

现在我对标记有一个更复杂的定义：

保留大小写。

感叹号是组成字符。

句号和逗号是组成字符，如果它们出现在 两个数字之间。这让我可以完整地获取 IP 地址 和价格。

像 $20-25 这样的价格范围产生两个标记， $20 和 $25。

出现在 To、From、Subject 和 Return-Path 行中，或出现在 URL 中的标记， 会相应地进行标记。例如，Subject 行中的“foo” 将变为“Subject*foo”。（星号可以 是任何你不允许作为组成字符的字符。）

这些措施增加了过滤器的词汇量，这 使其更具辨别力。例如，在当前的 过滤器中，Subject 行中的“free” 的垃圾邮件概率为 98%，而同一个标记 在正文中的垃圾邮件概率仅为 65%。

以下是一些当前的概率 [6]：

SubjectFREE 0.9999 free!! 0.9999 Tofree 0.9998 Subjectfree 0.9782 free! 0.9199 Free 0.9198 Urlfree 0.9091 FREE 0.8747 From*free 0.7636 free 0.6546

在“垃圾邮件计划”过滤器中，所有这些标记都将具有 相同的概率，即 0.7602。该过滤器识别了大约 23,000 个 标记。当前的过滤器识别了大约 187,000 个。

拥有更大的标记集的缺点是 有更多 错过标记的机会。 将你的语料库分散到更多标记上 与使它更小具有相同的效果。 如果你将感叹号视为 组成字符，例如，那么你最终可能 没有一个带有七个感叹号的 free 的垃圾邮件概率，即使你知道带有两个 感叹号的 free 的概率为 99.99%。

解决这个问题的一个方法是我所说的退化。如果你 找不到标记的完全匹配， 就将其视为一个不太具体的 版本。我认为末尾的感叹号、大写字母和出现在五个 标记的上下文之一中，都会使标记更具体。 例如，如果我找不到 “Subjectfree!’”的概率，我会查找 “Subjectfree”、“free!’”和“free”的概率，并取最远离 0.5 的概率。

以下是 [7] 中 如果过滤器在 Subject 行中看到“FREE!!!”，并且没有它的概率，则会考虑的备选方案。

SubjectFree!!! Subjectfree!!! SubjectFREE! SubjectFree! Subjectfree! SubjectFREE SubjectFree Subjectfree FREE!!! Free!!! free!!! FREE! Free! free! FREE Free free

如果你这样做，请务必考虑带有首字母大写的版本，以及全大写和全小写。垃圾邮件 往往有更多祈使句，在这些句子中，第一个词是动词。因此，首字母大写的动词 比全小写动词具有更高的垃圾邮件概率。在我的过滤器中，“Act”的垃圾邮件概率 为 98%，而“act”的概率仅为 62%。

如果你增加了过滤器的词汇量，你最终可能会 根据你旧的 “相同”定义多次计算同一个词。 从逻辑上讲，它们不再是 同一个标记了。但如果这仍然困扰你，让我 从经验中补充一点，你似乎在多次计算的词往往正是你 想要的词。

更大的词汇量的另一个影响是，当你 查看传入的邮件时，你会发现更多有趣的标记， 即那些概率远离 0.5 的标记。我使用 最有趣的 15 个来决定邮件是否是垃圾邮件。 但当你使用像这样的固定数字时，你可能会遇到问题。如果你发现很多最大程度有趣的标记， 结果最终可能会由决定排序顺序的随机因素决定，这些随机因素决定了同样有趣的标记的排序。 处理这个问题的一种方法是将某些 标记视为比其他标记更有趣。

例如， 标记“dalco”在我的垃圾邮件语料库中出现了 3 次，在我的合法语料库中从未出现过。标记“Url*optmails” （表示 URL 中的“optmails”）出现了 1223 次。 然而，正如我过去计算标记的概率一样， 两者将具有相同的垃圾邮件概率，即 0.99 的阈值。

这感觉不对。从理论上讲， 有理由为这两个标记赋予截然不同的 概率（Pantel 和 Lin 确实如此），但我还没有尝试过。 至少看起来，如果我们发现超过 15 个标记 只出现在一个语料库中，我们应该 优先考虑那些出现次数多的标记。因此，现在 有两个阈值。对于只出现在 垃圾邮件语料库中的标记，如果它们 出现次数超过 10 次，则概率为 0.9999，否则为 0.9998。对于只出现在 合法语料库中的标记，情况也是如此。

我以后可能会大幅度调整标记概率， 但这种微小的调整至少可以确保 标记以正确的方式排序。

另一种可能性是，不仅考虑 15 个标记，而是考虑所有超过一定 有趣程度阈值的标记。Steven Hauser 在他的统计垃圾邮件过滤器 [8] 中做到了这一点。 如果你使用阈值，请将其设置得非常高，否则 垃圾邮件发送者可以通过在邮件中填充 更多无害的词语来欺骗你。

最后，应该如何 处理 HTML？我已经尝试了各种选择，从 忽略它到完全解析它。忽略 HTML 是一个坏主意， 因为它充满了有用的垃圾邮件标志。但如果你完全解析 它，你的过滤器可能会退化为一个简单的 HTML 识别器。最有效的方法 似乎是折衷方案，即注意一些标记，但不注意 其他标记。我查看 a、img 和 font 标签，并忽略 其余标签。你当然应该查看链接和图像，因为 它们包含 URL。

我可能可以更聪明地处理 HTML，但我 认为不值得在这方面投入太多时间。 充满了 HTML 的垃圾邮件很容易过滤。更聪明的 垃圾邮件发送者已经避免了它。所以 未来的性能不应该过多地依赖于你 如何处理 HTML。

性能

在 2002 年 12 月 10 日至 2003 年 1 月 10 日期间，我收到了大约 1750 封垃圾邮件。 其中，4 封通过了。这意味着过滤 率约为 99.75%。

我错过的四封垃圾邮件中的两封通过了，因为它们 碰巧使用了在我的合法 电子邮件中经常出现的词语。

第三封是利用 不安全的 CGI 脚本向第三方发送邮件的垃圾邮件之一。 它们很难仅仅 根据内容进行过滤，因为邮件头是无害的，而且它们 对使用的词语很谨慎。即使这样，我通常也能 捕获它们。这封邮件以 0.88 的概率侥幸通过，略低于 0.9 的阈值。

当然，查看多个标记序列 可以轻松地捕获它。“以下是您反馈表单的结果”是一个明显的标志。

第四封垃圾邮件是我所说的 未来垃圾邮件，因为我认为垃圾邮件将 演变成这样：一些完全中性的 文本，后面跟着一个 URL。在这种情况下，它来自 某人说他们终于完成了他们的主页，问我是否去看一下。（该页面当然是一个 色情网站的广告。）

如果垃圾邮件发送者对邮件头很谨慎，并使用一个 新的 URL，那么未来垃圾邮件中就没有什么东西可以供过滤器 注意到。我们当然可以通过发送一个 爬虫来查看该页面来应对。但这可能没有必要。 未来垃圾邮件的回复率必须 很低，否则每个人都会这样做。 如果它足够低， 它 不会有利可图 让垃圾邮件发送者发送它，我们就不必 太费力地过滤它。

现在是真正令人震惊的消息：在同一个月 期间，我收到了 三封 误报。

从某种意义上说，收到一些误报 是一种解脱。当我写“垃圾邮件计划”时，我还没有收到任何误报，而且我不知道它们 会是什么样子。现在我已经收到了一些，我很高兴发现 它们不像我担心的那样糟糕。 统计 过滤器产生的误报结果是那些听起来很像垃圾邮件的邮件，而且 这些往往是你最不介意错过的邮件 [9]。

两封误报来自 我购买过东西的公司发来的新闻稿。我从未 要求接收它们，所以可以说它们 是垃圾邮件，但我将它们算作误报，因为 我以前没有将它们作为垃圾邮件删除。过滤器捕获它们的原因是，这两家公司都在 1月份切换到商业电子邮件发送者， 而不是从他们自己的服务器发送邮件， 而且邮件头和正文都变得更加像垃圾邮件。

第三封误报很糟糕。它 来自埃及的某人，用全大写字母写成。这是 由于将标记设置为区分大小写造成的；“垃圾邮件计划”过滤器不会捕获它。

很难说总体误报率是多少， 因为我们在统计上处于噪声之中。 任何从事过滤器工作的人（至少是有效的过滤器）都会 意识到这个问题。 对于一些电子邮件来说， 很难说它们是垃圾邮件还是非垃圾邮件，而当你将过滤器 设置得非常严格时，你最终会看到这些电子邮件。例如，到目前为止，过滤器已经 捕获了两封发送到我的地址的电子邮件，因为 输入错误，还有一封发送到我的电子邮件，因为他们认为我是 其他人。可以说，这些既不是我的垃圾邮件 也不是我的非垃圾邮件。

另一封误报来自 Virtumundo 的一位副总裁。 我写信给他们，假装是客户， 由于回复通过 Virtumundo 的 邮件服务器返回，因此它具有最具可疑的 邮件头。可以说，这也不是真正的误报，而是一种海森堡不确定性 效应：我之所以收到它，是因为我正在写关于垃圾邮件 过滤的文章。

不包括这些，到目前为止，我已经收到了五封误报， 总共约 7740 封合法电子邮件，误报率为 0.06%。 另外两封是关于我购买的商品 缺货的通知，以及来自 Evite 的聚会提醒。

我认为这个数字不可靠，部分原因是 样本量太小，部分原因是 我认为我可以修复过滤器，使其不再捕获 其中一些邮件。

误报在我看来与 漏报是不同类型的错误。 过滤率是性能的衡量标准。误报 我认为更像是错误。我将提高 过滤率视为优化，将降低误报 视为调试。

因此，这五封误报是我的错误列表。例如， 来自埃及的邮件被标记为垃圾邮件，因为全大写文本 让过滤器认为它像尼日利亚垃圾邮件。 这确实是一种错误。与 HTML 一样，电子邮件全部使用大写字母实际上在概念上是 一个 特征，而不是每个词一个特征。我需要以更复杂的方式处理大小写。

那么如何看待这个 0.06% 呢？我认为意义不大。你可以 将其视为上限，同时记住样本量很小。 但在现阶段，它更多地是衡量我实现中的错误，而不是贝叶斯过滤的固有误报率。

未来

接下来做什么？过滤是一个优化问题， 而优化的关键是分析。不要 试图猜测你的代码在哪里运行缓慢，因为你 会猜错。查看你的代码在哪里运行缓慢， 并修复它。在过滤中，这转化为： 查看你错过的垃圾邮件，并找出你 可以做些什么来捕获它们。

例如，垃圾邮件发送者现在正在积极地努力 逃避过滤器，他们正在做的事情之一是 拆分和拼错单词，以防止过滤器 识别它们。但处理这个问题不是我的首要 任务，因为我仍然可以轻松地捕获这些 垃圾邮件 [10]。

目前，我确实难以处理两种类型的垃圾邮件。 一种是假装来自 女性的电子邮件，邀请你与她聊天或查看她在约会网站上的个人资料。这些邮件能够通过，因为它们是 唯一一种无需使用推销语言就能进行推销的类型。它们使用 与普通电子邮件相同的词汇。

我难以过滤的另一种垃圾邮件来自 保加利亚的公司，提供合同编程 服务。这些邮件能够通过，因为我也是程序员，而且 这些垃圾邮件充满了与我的真实邮件相同的词语。

我可能会首先关注个人广告类型。我认为如果 我仔细观察，我将能够找到这些邮件与我的真实邮件之间的统计差异。写作风格 肯定不同，尽管可能需要多词过滤 才能捕获它。 此外，我注意到它们往往会重复 URL， 而有人在合法邮件中包含 URL 不会这样做 [11]。

外包类型很难捕获。即使 你向该网站发送了一个爬虫，你也不会找到一个明显的 统计证据。 也许唯一的答案是创建一个中央列表，列出 垃圾邮件中宣传的域名 [12]。但这种类型的邮件不会 太多。如果剩下的唯一 垃圾邮件是来自保加利亚的关于合同编程服务的非请求报价，我们可能都可以转而 做其他事情。

统计过滤真的能让我们达到那个地步吗？ 我不知道。现在，对我个人来说，垃圾邮件 不是问题。但垃圾邮件发送者还没有认真 努力欺骗统计过滤器。当他们这样做时会发生什么？

我对在 网络级别 [13] 上工作的过滤器不抱乐观态度。 当有一个值得克服的静态障碍时，垃圾邮件发送者 在克服它方面非常有效。已经有一家名为 Assurance Systems 的公司，它会 将你的邮件通过 Spamassassin，并告诉你它 是否会被过滤掉。

网络级过滤器不会完全没有用。 它们可能足以杀死所有“选择加入” 垃圾邮件，即来自像 Virtumundo 和 Equalamail 这样的公司的垃圾邮件，他们声称他们实际上是在运行选择加入列表。 你可以根据邮件头过滤这些邮件，无论它们在正文中说什么。但任何愿意 伪造邮件头或使用开放式中继的人，包括 大多数色情垃圾邮件发送者，如果他们愿意，应该能够让一些邮件通过 网络级过滤器。（当然不是他们想发送的邮件，这只是一些东西。）

我对那些 根据每个用户的邮件计算概率的过滤器抱有乐观态度。 这些过滤器可以更有效，不仅在 避免误报方面，而且在过滤方面也是如此：例如， 在邮件中的任何位置找到收件人的电子邮件地址的 Base64 编码，是一个非常好的垃圾邮件指标。

但个人过滤器的真正优势在于它们都是 不同的。如果每个人的过滤器都有不同的概率， 这将使垃圾邮件发送者的优化循环（程序员 称之为他们的编辑-编译-测试周期）变得极其缓慢。 他们不再只是调整垃圾邮件，直到它通过他们桌面上 的某个过滤器的副本，而是必须为每次调整进行 测试邮件。这就像用 没有交互式顶层的语言编程一样， 我不会希望 任何人这样做。

注释

[1] Paul Graham。 “垃圾邮件计划”。2002 年 8 月。 http://paulgraham.com/spam.html。

该算法中的概率 是使用贝叶斯规则的退化情况计算的。有两个 简化假设：特征（即词语）的概率是独立的，而且我们知道 关于电子邮件是垃圾邮件的先验概率 一无所知。

第一个假设在文本分类中很普遍。 使用它的算法被称为“朴素贝叶斯”。

我之所以做出第二个假设，是因为我收到的邮件中垃圾邮件的比例 每天（实际上是每小时）波动很大，以至于总体先验比率似乎 毫无价值，无法用作预测指标。如果你假设 P(spam) 和 P(nonspam) 都为 0.5，它们会相互抵消，你可以 将它们从公式中删除。

如果你在垃圾邮件与非垃圾邮件的比例始终很高或 （尤其是）很低的情况下进行贝叶斯过滤，你可能会通过合并先验概率来提高过滤器的 性能。要正确地做到这一点，你必须根据一天中的时间跟踪比率，因为 垃圾邮件和合法邮件的流量都有不同的每日 模式。

[2] Patrick Pantel 和 Dekang Lin。“SpamCop——垃圾邮件分类和组织程序”。AAAI-98 文本分类学习研讨会论文集。

[3] Mehran Sahami、Susan Dumais、David Heckerman 和 Eric Horvitz。 “一种过滤垃圾邮件的贝叶斯方法”。AAAI-98 文本分类学习研讨会论文集。

[4] 当时，我在大约 4,000 封 合法电子邮件中没有误报。如果下一封合法电子邮件是 误报，这将使误报率达到 0.03%。这些误报率 不可靠，正如我稍后解释的那样。我在这里引用 一个数字只是为了强调，无论误报率 是多少，它都小于 1.16%。

[5] Bill Yerazunis。“稀疏二元多项式哈希消息 过滤和 CRM114 鉴别器”。2003 年 垃圾邮件大会论文集。

[6] 在“垃圾邮件计划”中，我使用了 0.99 和 0.01 的阈值。 使用与 语料库大小成比例的阈值似乎是合理的。由于我现在拥有大约 10,000 封每种 类型的邮件，因此我使用 0.9999 和 0.0001。

[7] 这里有一个缺陷，我应该修复它。目前， 当“Subjectfoo”退化为“foo”时，这意味着 你正在获取“foo”在 正文或除我标记的那些以外的邮件头行中的出现次数的统计数据。 我应该做的是跟踪“foo”的统计数据 总体而言，以及特定版本的统计数据，并从 “Subjectfoo”退化为“foo”，而不是退化为“Anywhere*foo”。对于 大小写也是如此：我应该从大写退化为任何大小写，而不是 小写。

对价格也这样做可能会有所帮助，例如，从“$129.99”退化为“$--9.99”、“$--.99” 和“$--”。

你也可以从词语退化为它们的词干， 但这可能只会在你拥有小型语料库时 在早期提高过滤率。

[8] Steven Hauser。“统计垃圾邮件过滤器对我有用”。 http://www.sofbot.com。

[9] 误报并不都是一样的，我们在比较停止垃圾邮件的技术时应该记住 这一点。 虽然过滤器造成的许多误报 将是接近垃圾邮件的邮件，你不会介意错过它们， 但黑名单造成的误报，例如，将仅仅是 来自选择错误 ISP 的人的邮件。在这两种 情况下，你都会捕获到接近垃圾邮件的邮件，但对于黑名单来说，接近 是物理上的，而对于过滤器来说，它是文本上的。

[10] 如果垃圾邮件发送者在隐藏标记方面变得足够好， 以至于这成为一个问题，我们可以通过简单地删除 空格、句号、逗号等来应对，并使用字典从 生成的序列中提取词语。 当然，以这种方式找到在 原始文本中不可见的词语本身就是垃圾邮件的证据。

提取词语并不容易。它将需要 不仅仅是重建词语边界；垃圾邮件发送者 会添加（“xHot nPorn cSite”）和省略（“P#rn”）字母。 视觉研究可能在这里有用，因为人类视觉是 这些技巧将接近的极限。

[11] 总的来说，垃圾邮件比普通电子邮件更具重复性。 它们想要反复强调那个信息。我目前不允许 前 15 个标记中出现重复，因为 如果你碰巧多次使用某个不好的词语，你可能会收到误报。（在我的当前过滤器中，“dick”的 垃圾邮件概率为 0.9999，但它也是一个名字。） 看起来我们至少应该注意到重复， 因此我可能会尝试允许每个标记最多出现两次，就像 Brian Burton 在 SpamProbe 中做的那样。

[12] 一旦垃圾邮件发送者被迫使用疯狂的填词 技术来生成邮件中的所有其他内容，Brightmail 等方法将 退化为这种方法。

[13] 人们有时会争论说，我们应该在网络级别上进行过滤，因为它更有效。人们 通常在说这句话时指的是：我们目前在网络级别上进行过滤，我们不想从头开始。 但你不能强迫问题适应你的解决方案。

从历史上看，在关于软件设计的争论中，稀缺资源论点一直是失败的一方。 人们往往只用它们来为 （尤其是无所作为）的选择辩护，而这些选择是出于其他原因做出的。

感谢 Sarah Harlin、Trevor Blackwell 和 Dan Giffin 阅读了本文的草稿，再次感谢 Dan 为这个过滤器运行的大部分基础设施。

相关：

SubjectFREE 0.9999 free!! 0.9999 Tofree 0.9998 Subjectfree 0.9782 free! 0.9199 Free 0.9198 Urlfree 0.9091 FREE 0.8747 From*free 0.7636 free 0.6546

SubjectFree!!! Subjectfree!!! SubjectFREE! SubjectFree! Subjectfree! SubjectFREE SubjectFree Subjectfree FREE!!! Free!!! free!!! FREE! Free! free! FREE Free free