大多数人每天花费大量时间来区分垃圾邮件和有用的电子邮件。 我不认为只有我一个人觉得我们有更重要的事情要做。 垃圾邮件过滤软件可以提供帮助。

本文讨论了垃圾邮件过滤关键方面的多种可能的数学基础之一——从代表电子邮件内容的一系列标记中生成“垃圾度”指标。

这里描述的方法确实是一项在最佳开源传统中的分布式努力。 Lisp 书籍的作者 Paul Graham 在他的在线文章“垃圾邮件计划”中提出了一种过滤垃圾邮件的方法。 我采用了他的方法来生成与单词相关的概率，稍作修改，并提出了贝叶斯计算来处理不常出现的单词。 然后，我提出了一种基于卡方分布的方法，用于将各个单词的概率组合成代表电子邮件的组合概率（实际上是一对概率——见下文）。 最后，Spambayes 项目的 Tim Peters 提出了一种基于组合概率生成特别有用的垃圾度指标的方法。 一路上，这项工作都受到 Tim Peters 为 Spambayes 用 Python 编写以及 Greg Louis 为 Bogofilter 项目用 C 编写的实施方案的持续测试的指导。 测试由参与这些项目的许多人完成。

我们将假设存在一个电子邮件主体（语料库）用于训练，以及能够将每封电子邮件解析为其组成单词的软件。 我们还将进一步假设每封训练电子邮件都已手动分类为“正常邮件”（您想阅读的电子邮件）或“垃圾邮件”（您不想要的电子邮件）。 我们将使用这些数据和软件来训练我们的系统，方法是为每个单词生成一个代表其垃圾度的概率。

对于语料库中出现的每个单词，我们计算

p(w) 可以粗略地解释为随机选择的包含单词 w 的电子邮件是垃圾邮件的概率。 垃圾邮件过滤程序可以计算电子邮件中每个单词的 p(w)，并将该信息用作进一步计算的基础，以确定电子邮件是正常邮件还是垃圾邮件。

但是，这里有一个值得注意的难题。 在现实世界中，一个特定的人的收件箱可能包含 10% 的垃圾邮件或 90% 的垃圾邮件。 显然，这将对对于该个人而言，包含给定单词的电子邮件是垃圾邮件还是正常邮件的概率产生影响。

上面的计算忽略了这种影响。 相反，该计算实际上近似于在电子邮件中有一半是垃圾邮件，一半是正常邮件的世界中，随机选择的包含 w 的电子邮件是垃圾邮件的概率。 这种方法的优点是基于这样的假设：我们不希望仅仅因为我们碰巧收到的垃圾邮件和正常邮件的相对比例，就使电子邮件更难或更容易被归类为垃圾邮件。 相反，我们希望根据电子邮件自身的特征来判断电子邮件。 在实践中，这个假设效果很好。

当单词非常稀有时，以上述方式计算的概率存在问题。 例如，如果一个单词只在一封电子邮件中出现，并且它是垃圾邮件，则计算出的 p(w) 为 1.0。 但显然，并非绝对确定所有未来包含该单词的电子邮件都将是垃圾邮件； 事实上，我们根本没有足够的数据来了解真实的概率。

贝叶斯统计学为我们提供了一种处理这种情况的强大技术。 统计学的这个分支基于我们对某人对特定事件的信念程度感兴趣的想法； 这就是事件的贝叶斯概率。

当只有一封电子邮件包含特定单词且该电子邮件是垃圾邮件时，我们对下次看到该单词时它将在垃圾邮件中的信念程度不是 100%。 这是因为我们也有自己的背景信息来指导我们。 我们从经验中知道，几乎任何单词都可能出现在垃圾邮件或非垃圾邮件上下文中，并且一两个数据点不足以完全确定我们知道真实的概率。 贝叶斯方法使我们能够将我们的一般背景信息与我们为某个单词收集的数据结合起来，从而使这两个方面都得到适当的重视。 通过这种方式，我们确定关于当我们再次看到该单词时，它是否会在垃圾邮件中的适当信念程度。

我们按如下方式计算这种信念程度，f(w)

公式 1

其中

这为我们提供了方便地使用 x 来表示我们从背景信息中假设的概率，并使用 s 作为我们将赋予该假设的强度。 在实践中，s 和 x 的值是通过测试找到的，以优化性能。 s 和 x 的合理起点分别为 1 和 0.5。

我们将在我们的计算中使用 f(w) 而不是 p(w)，以便我们使用合理的概率，而不是当我们没有足够的数据时经常可能发生的不切实际的极端值。 此公式为我们提供了一种处理完全没有数据的情况的简单方法； 在这种情况下，f(w) 正是我们基于背景信息假设的概率。

那些对上述公式的推导感兴趣的人，请继续阅读； 其他人可能想跳到下一节。

如果您已经熟悉贝叶斯统计学的原理，您可能很容易理解推导过程。 否则，我建议您在继续之前阅读 David Heckerman 的“贝叶斯网络学习教程”（见资源）的第 1 节和第 2 节。

上面的公式基于假设包含单词 w 的电子邮件的垃圾邮件/正常邮件分类是具有贝塔分布先验的二项随机变量。 我们在纳入观察到的数据后计算后验期望。 我们将要进行一个测试，该测试等同于多次抛掷硬币以查看它是否似乎有偏差的“实验”。 有 n 次试验。 如果我们抛掷硬币，则每次抛掷硬币都是一次试验，我们将计算正面朝上的次数。 但在我们的例子中，试验是查看训练语料库中下一个包含单词“porn”的电子邮件，并查看它包含的电子邮件是否是垃圾邮件。 如果是，则认为实验成功。 显然，这是一个二项式实验：有两个值，是或否。 它们是独立的：一封电子邮件包含“porn”的事实与下一封电子邮件是否包含“porn”的问题无关。 现在，碰巧的是，如果您有一个二项式实验并假设贝塔分布为先验，您可以将第 n + 1 次试验成功的期望表示为公式 2 所示。

公式 2

我们想证明公式 1 等价于公式 2。 首先执行以下替换

s = u + v s * x = u

下一步是用 n * p(w) 替换 q。 我们已经讨论过 p(w) 是在虚构世界中，垃圾邮件和正常邮件数量相同的情况下，随机选择的包含 w 的电子邮件是垃圾邮件的概率的近似值。 因此，n * p(w) 近似于该世界中包含 w 的垃圾邮件的计数。 这近似于我们实验中成功的计数，因此等同于 q。 这完成了我们对公式 1 和公式 2 等价性的证明。

在测试中，在所有将使用 p(w) 的计算中，用 f(w) 替换 p(w) 始终如一地导致更可靠的垃圾邮件/正常邮件分类。

此时，我们可以计算一个概率 f(w)，用于可能出现在新电子邮件中的每个单词。 该概率反映了我们基于我们的背景知识和训练语料库中的数据，对从包含 w 的电子邮件中随机选择的电子邮件将是垃圾邮件的信念程度。

因此，每封电子邮件都由一组概率表示。 我们希望将这些单独的概率组合成整个电子邮件的总体组合垃圾度或正常度指标。

在称为元分析的统计学领域中，组合概率最常见的方法可能是 R. A. Fisher 的方法。 如果我们有一组概率，p1, p2, ..., pn，我们可以执行以下操作。 首先，计算 -2ln p1 * p2 * ... * pn。 然后，认为结果具有自由度为 2n 的卡方分布，并使用卡方表来计算获得与计算结果一样极端或更极端的结果的概率。 这个“组合”概率有意义地概括了所有单独的概率。

初始概率集被认为是相对于零假设而言的。 例如，如果我们做出硬币是公正的零假设假设，然后抛掷十次并连续获得十次正面，则结果概率为 (1/2)10 = 1/1024。 相对于零假设而言，这将是一个不太可能的事件，但当然，如果硬币实际上有偏差，那么获得极端结果的可能性不一定那么低。 因此，我们可能会拒绝零假设，而是选择接受硬币有偏差的备择假设。

我们可以使用相同的计算来组合我们的 f(w)s。 f(w)s 不是真实的物理概率。 相反，它们可以被认为是关于这些概率的最佳猜测。 但在 Fisher 计算的传统元分析用途中，它们也不知道是真实的概率。 相反，它们被假定为零假设的一部分。

让我们的零假设为“f(w)s 是准确的，并且当前的电子邮件是单词的随机集合，每个单词彼此独立，使得 f(w)s 不在均匀分布中。” 现在假设我们有一个单词“Python”，其 f(w) 为 0.01。 我们认为它仅在 1% 的时间内出现在垃圾邮件中。 那么，在我们的信念正确的程度上，发生了一个不太可能的事件； 一个概率为 0.01 的事件。 同样，电子邮件中的每个单词都有一个与其相关的概率。 非常垃圾的单词（如 porn）的概率可能为 0.99 或更高。

然后我们使用 Fisher 计算来计算整组单词的总体概率。 如果电子邮件是正常邮件，则它很可能有很多非常低的概率和相对较少的非常高的概率来平衡它们，结果是 Fisher 计算将给出非常低的组合概率。 这将使我们能够拒绝零假设，而是假设备择假设，即电子邮件是正常邮件。

让我们将此组合概率称为 H

公式 3

其中 C-1() 是反卡方函数，用于从卡方分布的随机变量导出 p 值。

当然，我们从一开始就知道零假设是错误的。 实际上，几乎没有电子邮件实际上是关于正常度或垃圾度的无偏单词的随机集合； 电子邮件通常具有一定数量的某种类型的单词。 当然，单词不是独立的。 包含“sex”的电子邮件更可能包含“porn”，并且包含编程 Python 的朋友姓名的电子邮件也更可能包含“Python”。 并且，f(w)s 不在均匀分布中。 但出于垃圾邮件检测的目的，这些与现实的偏差通常对我们有利。 它们导致概率具有非随机趋势，在给定的电子邮件中要么高要么低，为我们提供了强大的统计基础来拒绝零假设，转而支持一个或另一个备择假设。 电子邮件要么是正常邮件，要么是垃圾邮件。

因此，零假设有点像稻草人。 我们建立它只是为了让它朝一个或另一个方向被击倒。

这里值得一提的是，这种方法与许多其他假设概率独立的组合方法之间的关键区别。 例如，这种差异适用于诸如“贝叶斯链式规则”和“朴素贝叶斯分类”之类的方法。 这些方法已经在使用大量人工分类的电子邮件进行的正面交锋中进行了测试，并且表现不佳（即，与人类判断的一致性不如这里描述的方法）。

由于需要数据点的独立性，而实际上不存在这种独立性，因此这些方法的计算在技术上是无效的。 使用 Fisher 技术时不会出现该问题，因为计算的有效性不依赖于数据的独立性。 Fisher 计算的结构使我们拒绝包含独立性的零假设，转而支持我们感兴趣的两个备择假设之一。 这些备择假设中的每一个都涉及非独立性，例如“sex”和“porn”之间的相关性，作为产生极端组合概率的现象的一部分。

这些组合概率只是在零假设（已知几乎肯定是错误的）为真的假设下的概率。 在现实世界中，Fisher 组合概率根本不是概率，而是一个抽象指标，表明我们应该在多大程度上（或多小程度上）倾向于接受零假设。 当零假设为假时，它不打算成为真正的概率，因此它不是概率的事实不会给我们带来计算问题。 众所周知，朴素贝叶斯分类器能够抵抗因缺乏独立性而造成的扭曲，但它并不能完全避免这些扭曲。

到目前为止，Fisher 在垃圾邮件/正常邮件分类测试中表现出优于朴素贝叶斯分类器的性能，是否是由于对数据缺乏独立性的不同响应，目前尚不清楚，但这作为一个可能的因素值得考虑。

单个 f(w)s 只是真实概率的近似值（即，当关于单词的数据很少时，我们对 f(w) 给出的垃圾邮件概率的最佳猜测可能无法反映其真实情况）。 但是，如果您考虑 f(w) 是如何计算的，您将看到，随着 f(w) 接近 0 或 1，这种不确定性会逐渐减小，因为只有在训练数据中非常频繁地出现并且几乎总是出现在垃圾邮件或几乎总是出现在正常邮件中的单词才能实现如此极端的值。 而且，方便的是，接近 0 的数字对计算的影响最大。 为了理解这一点，请考虑如果将第一个项更改为 0.001，则对乘积 0.01 * 0.5 的影响，与如果将第一个项更改为 0.501，则对乘积 0.51 * 0.5 的影响，并回想一下 Fisher 技术是基于概率的乘积。 因此，我们的零假设因 f(w)s 不是完全可靠的事实而被违反，但对于寻找正常邮件证据最感兴趣的单词而言，这种违反几乎无关紧要：f(w) 接近 0 的单词。

警觉的读者此时会想：“好的，我理解这些 Fisher 计算对于具有相应接近 0 概率的正常邮件单词似乎是有意义的，但是对于概率接近 1 的垃圾邮件单词呢？” 好问题！ 请继续阅读以获取将完成我们讨论的答案。

上述计算对正常度的证据很敏感，特别是当它以在正常邮件中出现的次数远多于垃圾邮件的单词的形式出现时。 这是因为接近 0 的概率对概率的乘积有很大影响，而概率的乘积是 Fisher 计算的核心。 实际上，有一个 1971 年的定理表明，在某些情况下，Fisher 技术与任何技术一样强大，可以揭示可能性的乘积中的潜在趋势（请参阅资源）。

然而，非常关注垃圾邮件的单词的 f(w)s 接近 1，因此对计算的影响要小得多。 现在，可能会假设这是一件好事。 毕竟，对于许多人来说，将一封好邮件错误分类为垃圾邮件似乎比将一封坏邮件错误分类为正常邮件要糟糕得多，因为如果一封垃圾邮件漏网之鱼，则不会造成重大危害，但如果一封好邮件被错误地分类为垃圾邮件并因此被收件人忽略，则可能会造成重大危害。 因此，对正常度的指示敏感而对垃圾度的指示不太敏感似乎是好事。

但是，有一些方法可以解决这个问题，这些方法在现实世界的测试中不会增加将好邮件错误分类为垃圾邮件的明显趋势，但确实显着降低了将垃圾邮件错误分类为正常邮件的趋势。

在最近的测试工作中确定的最有效技术如下。

首先，“反转”所有概率，方法是从 1 中减去它们（也就是说，对于每个单词，计算 1 - f(w)）。 因为 f(w) 表示从包含 w 的电子邮件集中随机选择的电子邮件是垃圾邮件的概率，所以 1 - f(w) 表示随机选择的电子邮件是正常邮件的概率。

现在像以前一样进行相同的 Fisher 计算，但对 (1 - f(w))s 而不是对 f(w)s 进行计算。 当存在大量非常垃圾的单词时，这将导致接近 0 的组合概率，拒绝零假设。 将此组合概率称为 S。

现在计算

公式 4

I 是一个指标，当证据的优势支持电子邮件是垃圾邮件的结论时，该指标接近 1，当证据指向电子邮件是正常邮件的结论时，该指标接近 0。 该指标具有一些有趣的特征。

假设一封电子邮件有许多非常垃圾的单词，也有许多非常正常的单词。 由于 Fisher 技术对接近 0 的值敏感，而对接近 1 的值不太敏感，因此结果可能是 S 和 H 都非常接近 0。 例如，S 可能在 0.00001 的数量级，而 H 可能在 0.000000001 的数量级。 事实上，在现实世界的电子邮件中，这些类型的结果并不像人们可能认为的那样不常见。 一个例子是当朋友将垃圾邮件转发给另一个朋友作为关于垃圾邮件的电子邮件对话的一部分时。 在这种情况下，将有强有力的证据支持两种可能的结论。

在许多方法中，例如那些基于贝叶斯链式规则的方法，示例中可能存在比正常邮件单词更多的垃圾邮件单词这一事实将倾向于使分类器绝对确定电子邮件是垃圾邮件。 但实际上，这不是很清楚； 例如，转发的电子邮件示例不是垃圾邮件。

因此，在这些情况下，I 接近 0.5 是一个有用的特征，就像当在某个方向或另一个方向上没有特定证据时，I 接近 0.5 一样。 当有重要证据支持两种结论时，I 采取谨慎的方法。 在现实世界的测试中，对这些中间值电子邮件的人工检查倾向于支持这样的结论，即它们确实应该在中间的某个位置进行分类，而不是像大多数分类器那样采用非黑即白的方法。

Richie Hindle 在第 52 页的文章中描述的 Spambayes 项目利用了这一点，方法是将 I 接近 0.5 的电子邮件标记为不确定。 这允许电子邮件收件人更多地关注无法自信分类的电子邮件。 这减少了由于错误分类而忽略好邮件的机会。

迄今为止，使用这种方法的软件基于每个标记一个单词。 其他方法也是可能的，例如构建短语哈希表。 预计这里描述的数学也可以在这些上下文中使用，并且有理由相信基于短语的系统将具有性能优势，尽管关于这个想法存在争议。 未来的 Linux Journal 文章有望涵盖这些方向的任何发展。 CRM114（请参阅资源）是基于短语的系统的一个示例，该系统表现非常出色，但在撰写本文时，尚未在同一语料库上直接与其他方法进行测试。 （在撰写本文时，CRM114 正在使用贝叶斯链式规则来组合 p(w)s。）

此处描述的技术已在 Spambayes 和 Bogofilter 等项目中使用，以显着提高垃圾邮件过滤任务的性能。 未来的发展，可能包括将这些计算与基于短语的方法集成，有望实现更好的性能。

反卡方函数的 Python 实现

资源