垃圾邮件还是非垃圾邮件？

如果你使用电子邮件（我想你一定用），有可能每天都在工作中看到机器学习。你的电子邮件客户端可能包含某种垃圾邮件过滤机制，从收到的邮件中自动识别令人厌烦的推销材料，然后小心地将它们发送到“垃圾邮件文件夹”。这个功能免去了人工逐个删除这些邮件的麻烦，还可以防止你不小心点击有害链接，是机器学习实施得当令生活更美好的典型范例。计算机擅长执行重复性任务，并且做得很彻底。通过自动进行乏味的活动，避免我们犯错，使人们可以专注于更有趣、更值得深思的活动。

垃圾邮件检测是机器学习的极好例证，也是分类概念的权威示例。我们必须将给定的一组电子邮件分为两类：垃圾邮件（应该直接进入垃圾箱的有害信息）或者非垃圾邮件（我们希望阅读的有效信息）。这一工作还有另一个有趣之处：和数字识别问题不同，垃圾邮件检测所用的数据都是文本，而不是数字形式。在数字世界中，大部分可用材料是文本而不是结构清晰的数字表格，因此理解处理方式十分重要。

用贝叶斯定理自动检查垃圾邮件

在本篇文章中，我们将从头开始构建一个垃圾邮件检测引擎，然后用这个例子说明几种有用的技术和思路，我们将：

(1) 确定处理文本的方法。从计算机的角度看，原始文本文档就是字符的随机组合。我们将看到如何将一个文本块转换为计算机所能处理的标记（Token），从中提取特征（也就是将原始数据转换为信息量更大、更有用的新属性——“特征”）。

(2) 了解贝叶斯定理——这个简单而强大的数学公式可以量化所包含的新信息，以更新我们对不确定事件的评估。作为直接的应用，我们将实现一个简单贝叶斯分类器——使用词汇频度确定文档类型的算法。

(3) 讨论理解数据以正确解读结果及其质量的重要性，并阐述即使不修改算法本身，仅从数据集提取新特征就能给模型的预测能力带来多么显著的提高。

我们将首先专注于实现一个分析文本文档，确定其所属类别的算法。一旦有了这个工具，我们将把注意力转向数据集，看看仔细检查所拥有的数据如何帮助我们找出新特征，显著改善预测的质量。

一、 挑战：构建一个垃圾邮件检测引擎

我们将要处理的文档不是电子邮件，而是文本消息。我们的目标是使用来自英国的真实SMS（短消息服务）数据集发现垃圾短信，这些消息是我们从加州大学欧文分校机器学习知识库中找到的。

■ 附注：

UCI机器学习知识库由加州大学欧文分校的机器学习与智能系统中心于1987年启动。你可以在 http://archive.ics.uci.edu/ml/中找到这个知识库，它包含将近300个干净、文档齐备的数据集，可以按照大小、特征类型等条件搜索和组织。这是一个很有趣的机器学习资源，包含了许多常常用作算法性能评估基准的“经典”数据集。

1. 了解我们的数据集

在讨论使用哪个模型之前，首先来观察一下数据。数据集可以从http://1drv.ms/1uzMplL下载（这就是UCI知识库中原始文件的复制品，原始文件可以在http://archive.ics.uci.edu/ml/ datasets/SMS+Spam+Collection上找到）。它作为单个文本文件保存，名为SMSSpamCollection（没有文件扩展名），包含5574条真实的文本消息。每行是一个SMS，标记为“ham”（非垃圾短信）或者“spam”（垃圾短信）。下面是前面几行：

  ham      Go until jurong point, crazy.. Available only in bugis n great world la e buffet...Cine there got amore wat...
  ham     Ok lar... Joking wif u oni...
  spam    Free entry in 2 a wkly comp to win FA Cup final tkts 21st May 2005. Text FA to 87121 to receive entry question(std txt rate)T&C's apply 08452810075over18's
  ham     U dun say so early hor... U c already then say...
  ham     Nah I don't think he goes to usf, he lives around here though
  spam    FreeMsg Hey there darling it's been 3 week's now and no word back! I'd like some fun you up for it still? Tb ok! XxX std chgs to send, £1.50 to rcv

第一眼的印象是，人们在文本消息中使用的语言明显不同于“标准英语”！例如“U c”这样的片段是“You see”的简写，在普通的词典中可能找不到。

考虑到这一点，我的第一步是尝试获得两组文本之间差别的“直觉”。有没有一些词语在垃圾短信或者非垃圾短信中出现得更频繁？这能够指导我们构建一个智能引擎，自动区分非垃圾短信和垃圾短信。我们首先按照类别（“ham”和“spam”）分解数据集，计算各自的词语出现频率。鉴于这一活动的探索特性，似乎很适合使用F#脚本。

■ 提示：

花点时间研究一下数据！盲目对数据集应用算法可能工作得不错，但是走不了太远。就像开发应用程序时应该花时间学习领域模型那样，对数据的更深入理解能够帮助你构建更智能的预测模型。

2. 使用可区分联合建立标签模型

数据是首要的。数字识别数据集是由数字组成的（像素编码和标签都是如此），而这里的数据有一个特征（文本消息本身）和一个标签（“ham”或者“spam”）。我们应该如何表现它们？

可能的方法之一是将标签编码为布尔值，如非垃圾短信表示为“真”（true），垃圾短信表示为“假”（false）。这种标签工作得很完美，但是也有一些缺点：它不能自动说明字段的含义。例如，如果展示这样编码的一个数据记录：

True    Ok lar... Joking wif u oni... ,

你怎么可能猜出这里的“True”代表什么？另一个潜在的问题是，如果我们需要增加更多的类别（如非垃圾短信、垃圾短信和有歧义的信息），布尔值无法扩展。

机器学习的难点在于不能增加额外、不必要的复杂性。因此，我们将用F#的可区分联合（有时我也将它称作DU）表示标签。如果你之前从未见过可区分联合，可以近似地将其看作C#枚举类型。可区分联合和枚举一样，都定义一组独特的情况，但是功能强大得多。这种类比对DU不公平，但是足以帮助我们起步。

我们先使用可以在FSI中运行的例子，简单地说明DU的工作方式。定义DU和定义其他类型一样简单：

type DocType =
    | Ham
    | Spam

在F# Interactive窗口运行上述语句（在最后添加;;触发求值），应该看到如下结果：

type DocType =
    | Ham
    | Spam

上述语句定义了一个简单类型DocType，它只能取两个值：Spam或者Ham。我喜欢可区分联合的主要原因之一是它们和模式匹配配合得很好，可编写以非常清晰的风格描述业务领域的代码。例如，在我们的例子中，训练集中的每个示例都是非垃圾短信或者垃圾短信，并包含真实消息的内容。我们可以将其表示为一个元组，每个示例是一个DocType和一个字符串，按照这一路线处理消息示例，可以在F# Interactive窗口中尝试：

let identify (example:DocType*string) =
    let docType,content = example
    match docType with
    | Ham -> printfn "'%s' is ham" content
    | Spam -> printfn "'%s' is spam" content

这个例子只是为了示意目的，但是指出了以后将要遵循的模式。在这个例子中，我们创建了一个小函数，取得一个消息示例并打印其内容以及所属类别。我们首先通过元组模式匹配将消息示例分为两部分（DocType和内容），然后在DocType的两种可能情况上使用模式匹配，在单独“分支”中处理两种情况。在FSI中输入：

identify (Ham,"good message");;

你应该看到如下结果：

'good message' is ham

在能够更好地决定如何处理真实SMS内容之前，这就是我们的数据模型。下面从加载数据集入手！

3.读取数据集

我们将把大部分时间花在探究数据集，从脚本环境中积极构建和改进模型上。打开Visual Studio创建一个新的F#库项目，将其命名为HamOrSpam。为了方便起见，我们还从Visual Studio之外使用文件系统，在解决方案中添加一个名为Data的文件夹，将数据文件SMSSpamCollection拖入其中（从前面提到的链接中下载，没有文件扩展名）。参见图1。

图1 文件夹组织

这就使我们可以使用一个小技巧，用更清晰的方式访问数据文件。F#有两个方便的内建常量__SOURCE_DIRECTORY__和__SOURCE_FILE__，大大简化了脚本中文件的处理，我们可以引用数据文件位置，而无须硬编码一个取决于本地机器的路径。从这些常量的名称你可能已经猜到，第一个常量求得包含文件本身的目录完整路径，第二个返回到文件本身的完整路径，包括文件名。

现在可以进行脚本的编写了。和数字识别器使用的数据集之间主要的差别是，这个数据集没有文件头，只有两列，不使用逗号而使用制表符分隔。其他方面大部分相同：我们有一个包含示例的文件，希望将其提取到一个数组中。果不其然，解决方案看起来非常相似：读取文件并向每一行应用一个函数，将其解析为标签和内容，根据制表符“\t”拆分。

我们直接进入项目中的Script.fsx文件，删除默认的代码并粘贴如下代码：

程序清单1 从文件中读取SMS数据集

open System.IO

type DocType =
    | Ham
    | Spam

let parseDocType (label:string) =
    match label with
    | "ham" -> Ham
    | "spam" -> Spam
    | _ -> failwith "Unknown label"

let parseLine (line:string) =
    let split = line.Split('\t')
    let label = split.[0] |> parseDocType
    let message = split.[1]
    (label, message)

let fileName = "SMSSpamCollection"
let path = __SOURCE_DIRECTORY__ + @"..\..\Data\" + fileName

let dataset =
    File.ReadAllLines path
    |> Array.map parseLine

此时，你应该可以选择脚本中刚刚编写的所有代码，在F# Interactive窗口中执行，产生如下结果：

val dataset : (DocType * string) [] =
  [|(Ham,
     "Go until jurong point, crazy.. Available only in bugis n grea"+[50 chars]);
  (Ham, "Ok lar... Joking wif u oni...");
  (Spam,
   "Free entry in 2 a wkly comp to win FA Cup final tkts 21st May"+[94 chars]);
  // Snipped for brevity
  (Ham,
   "Hi. Wk been ok - on hols now! Yes on for a bit of a run. Forg"+[117 chars]);
  (Ham, "I see a cup of coffee animation"); ...|]

现在我们有了一个示例数据集，每个都标记为垃圾短信或者非垃圾短信。我们可以开始解决真正感兴趣的问题了：可使用哪些特征区分垃圾短信和非垃圾短信？

■ 提示：

使用File.ReadAllLines读取数据集的内容可能不总是最好的主意。我们将所有数据加载到内存，马上保存到一个数组中，然后创建另一个数组保存Array.map转换的结果。这个特殊数据集相当小，只包含大约5000行，但是处理更大的数据集时，可以使用一个流化的版本（如System.IO.StreamReader.ReadLine()），一次将数据集的一行加载到内存中。

二、 根据一个单词决定

有了数据，我们就可以开始分析了。我们的最终目标是区分垃圾短信和非垃圾短信，但是和数字识别器的情况不同，我们还没有一组清晰的特征，唯一的材料是原始文本块——SMS本身。与此同时，人们会猜测文本中有许多信息可供利用。我们只需要找到一个途径，将这些字符串转换成可以使用的特征即可。

1. 以单词作为线索

如果你仔细观察刚刚加载的数据集，就可能会注意到垃圾短信看起来和非垃圾短信有些不同。浏览这些短信，你的眼睛很容易找出某些值得警惕的线索，暗示着某一条短信可能是垃圾短信。举个例子，“FREE”（全部大写）出现在开始的几条垃圾短信中，似乎在非垃圾短信中不常见到。

这就提出了一个可能的方法：使用来自整条短信的单词识别它所属的类别。我们首先计算垃圾短信中包含特定字符串的次数，与非垃圾短信比较，确认我们的直觉是否正确。我们可以在脚本中输入几行F#代码来测试这一点。首先，过滤数据集使之只包含垃圾短信，然后再次过滤，只保留包含“FREE”的消息，最后计算剩下的条目数量。

let spamWithFREE =
    dataset
    |> Array.filter (fun (docType,_) -> docType = Spam)
    |> Array.filter (fun (_,sms) -> sms.Contains("FREE"))
    |> Array.length

选择上述代码，在F# Interactive窗口中运行——应该看到如下的结果：

val spamWithFREE : int = 112

现在，让我们对非垃圾短信做同样的工作：

let hamWithFREE =
    dataset
    |> Array.filter (fun (docType,_) -> docType = Ham)
    |> Array.filter (fun (_,sms) -> sms.Contains("FREE"))
    |> Array.length

这将产生如下结果：

val hamWithFREE : int = 1

数字确认了我们的直觉：“FREE”在垃圾短信中使用的频率确实远高于非垃圾短信，这似乎是用于区分两个类别的好标志。我们可以使用这个词构建一个很简单的垃圾短信分类器，如：

let primitiveClassifier (sms:string) =
    if (sms.Contains "FREE")
    then Spam
    else Ham

这是一个很有希望的开始。但是，如果我们想要使用这一思路构建更重要的程序，就需要应付两个问题。首先，我们选择“FREE”作为垃圾短信的指示器，但是并没有真正证明其原因。我们怎么知道一个特定的词汇是不是垃圾或者非垃圾短信的好标志？其次，根据来自整条消息中的一个词做出决定似乎相当有局限性。我们能否一次使用多个词，将它们（可能冲突）的信息组合为单一决策过程？

2. 用一个数字表示我们的确定程度

根据直觉判断包含“FREE”的消息很可能是垃圾短信在统计学上拿不到高学位。我们能不能得到一个不依靠直觉的结论，并且量化特定单词表示一条消息是非垃圾短信或者垃圾短信的可靠性？

我个人常常借助决策树，作为更好地理解概率问题的一种方法。在我们的例子中，下面就是所要做的事情：将语料库中的5574个文档按照文档类型分成两组（747个垃圾文档，4827个非垃圾文档），对每个组计算包含“FREE”的数量。这可以表示为一棵决策树，如图2所示。

图2 决策树

我喜欢将决策树看成一系列管子（如果你愿意，也可以将其看作管道）。从初始节点开始，在管子中注入100%的可能性，而不是水。每个节点代表可能有多种结果的一个事件，将各种可能性分解到不同分支，不应该有任何可能性消失。

在本例中，我们从5574个文档开始，它们可能是垃圾短信或者非垃圾短信。大部分文档是非垃圾短信——5574个中有4827个，占86.6%——所以如果没有任何其他信息，随机选择一条消息并问你“是垃圾短信还是非垃圾短信？”你的回答应该是“非垃圾短信”（有86.6%的概率答对）。

树的下一级考虑每组文档中包含“FREE”的可能性。例如，如果一条消息是垃圾短信，有112/747的可能性包含“FREE”，以概率论的术语表达，如果文档是垃圾短信，包含“FREE”的概率是15%。

这很有趣，但是对我们的分类没有用处。我们真正想知道的是包含“FREE”的文档是垃圾短信的概率。不过，获得这一信息也不太难：我们只需要重新组织决策树，从文档是否包含“FREE”开始，而不是从垃圾短信和非垃圾短信开始。注意，不管如何构造决策树，最终都应该有4个“叶子”组。例如，应该仍然有112个文档是垃圾短信且包含“FREE”。在5574个文档中，有113个包含“FREE”，其中112个来自垃圾短信组，1个来自非垃圾短信组。经过更多的重新组织，我们应该得到图3所示的决策树。虽然和前面的树完全等价，但是提供了不同信息相互关联的不同视角。

图3 变换后的决策树

具体地说，这棵决策树为我们提供了关心的信息：包含“FREE”的文档是垃圾短信的概率为112/113=99.1%（从科学上确认了我们的直觉）。

3. 贝叶斯定理

我们刚刚使用的方法有一个名称：贝叶斯定理。教科书中最枯燥的表现形式通常是：

|符号应该读作“在……条件下”。我们刚才的例子计算的是在一封电子邮件包含“FREE”的条件下，该邮件是垃圾邮件的概率，按照贝叶斯公式应该写作：

如果机械地代入数字，可以得到如下结果，这就是我们用决策树得出的结果：

看待贝叶斯定理的方法之一是将其当作两部分数据的平衡措施：对世界的初始认识（在我们的例子中是有多少垃圾短信）以及附加的信息（在垃圾短信或者非垃圾短信中找到单词“FREE”的频率）。贝叶斯定理量化新信息中的权重：垃圾短信越少见，默认的预测就应该越向非垃圾短信倾斜，更换预测方法的证据就越有力。

看待贝叶斯定理的另一种方法是与独立性概念的关联。如果如下等式成立，则称两个事件A和B相互独立：

P (A and B) = P (A)×P(B)

使用贝叶斯定理，上式可以得出：

P (A | B) = P (A)

换言之，知道与B相关的任何细节不能传达任何关于A的有用信息（反之亦然）。相反，如果A和B不互相独立，贝叶斯定理将捕捉到两部分信息关联的强度。最后一点（也是一句忠告）是，要注意这种效应的不对称性。如果知道一个电子邮件是垃圾邮件，那么它有15%的概率包含“FREE”，但是知道一封电子邮件包含单词“FREE”，那么它有99%的概率是垃圾邮件！

蒙蒂•霍尔问题

如果你觉得上面介绍的方法很令人困惑，不要担心。这个问题既简单又复杂——进行计算很容易，但是认识到其真正意义却不简单。众所周知，人类的大脑很不擅长理解不确定性，即使非常聪明的人在这个问题上也会犯令人难堪的错误。最著名的例子是蒙蒂•霍尔问题：在游戏节目中有3个门，其中一个门后藏有奖品，当选手选择了一个门时，主持人打开剩下两个门中的一个，指出该门后面没有奖品。问题是，选手这时候应该改变自己的选择吗？20世纪50年代，Marilyn Vos Savant正确地回答了这个问题，但是一些著名的数学家（如Paul Erdos）却错误地企图指出她的错误。从这个故事里我得到了一个教训：处理概率时应该多加小心，因为人类直觉的过往记录并不好——当然，在公开批评任何人之前要三思而行！

4. 处理罕见的单词

贝叶斯定理为我们提供了根据一个单词决定一条短信是非垃圾短信还是垃圾短信的便利方法。但是，你可能已经注意到一个小问题。如果选择仅在一个类别中出现的单词——例如只存在于非垃圾邮件的“uncle”“honeybee”或者“wine”——那么我们的公式将对一个类别指定100%的概率，另一个类别指定0%的概率。换言之，如果我们看到一条包含单词“uncle”的消息，我们将带着100%的自信决定，这条消息不可能是垃圾短信，而不管这条消息的其余内容是什么。

这很明显是不正确的，我们不应该根据有限的训练样本对任何事情持有100%的信任。处理这一问题的方法之一是使用拉普拉斯平滑法。这种听起来很可怕的方法得名于法国数学家皮埃尔-西蒙·德·拉普拉斯（Pierre-Simon de Laplace），可以描述为一个“容差系数”。我们将每个单词的计数加一，消除缺失单词的问题，并计算P（垃圾短信包含“xyz”）=（1+包含“xyz”的垃圾短信计数）/（1+垃圾短信计数）。本质上，我们制作了一条包含所有标记的虚构消息，因此，最少见的标记出现概率很低，但是不会为0。

三、组合多个单词

使用贝叶斯定理，我们找出了根据是否包含特定单词分类SMS的方法。这是一个进展，但是我们还远没有完成任务。一条消息中有许多单词，每个都以不同的强度表现非垃圾短信和垃圾短信的特征。如何将这些信息（它们可能传递相互矛盾的信号）组合为用于决策的单一值？

1. 将文本分解为标记

举个例子，考虑下面这条假设的短信：“Driving, cant txt.”它是垃圾短信的概率有多高？

我们可以直接应用贝叶斯定理，在数据集中搜索整条短信。但是，这种方法估计不会有很好的效果。找到精确复制的概率很小，更不要说多个单词的精确复制了。另一方面，我们已经看到单词“FREE”携带一些相关信息。

我们要做的就是简单地将短信分解为一组单词：“driving”“cant”和“txt”，并用某种表现形式代替原始文本。然后，分析单独标记并将它们所代表的组合为单一值，据此做出决定。

将文本块分解为有意义的元素（单词或者其他符号）——标记（Token）的过程称作标记化。决定如何标记化是模型的重要部分，没有任何独特的正确方法——取决于所要解决的问题。现在，我们和以往一样从能够实施的最简单方法入手：如果一个单词“FREE”的信息量很丰富，扩展这一想法，将短信分解为单个单词。实际上，我们将把每条短信转换为一组特征，每个特征中存在或者不存在某个特定单词。

例如，如果我们有两个字符串“Programming is Fun”（编程很有趣）和“Functional programming is more fun!”（函数式编程更有趣！），可以将它们分解为“programming”“is” “fun”和“functional”“programming”“is”“more”“fun”。这种表现方式使我们可以更加高效，不需要检查某条消息是否包含特定的子字符串，可以将每个文档处理为一组标记，快速验证是否包含我们感兴趣的特殊标记。

■ 注意：

这一通用方法对于将文本转换为计算机可以处理的形式很有用。例如，我们可以收集语料库中找到的整组标记——[“functional”; “programming”; “is”; “more”; “fun”]——并通过计算每个标记找到的次数，对每个文档进行编码。第一个文本块变成[0; 1; 1; 0; 1]，第二个文本块变成[1; 1; 1; 1; 1]。我们的数据集现在采用了人类完全不可读的形式：每一行是一个观测值，每一列是一个特征，所有内容都编码为数字——例如，我们可以用这些数据确定两个文档的相似度。将观测值转换为一组计算机可以分析寻找模式的数字型特征（人类无法做到），是机器学习中很典型的做法。

这时，你可能会想：“这是严重的过度简化”，你是对的。毕竟，我们将整个句子转换成一组原始的单词，忽略了句法、语法或者词序。这种转换明显丢失了信息。例如，“I like carrots and hate broccoli”（我喜欢胡萝卜，讨厌花椰菜）和“I like broccoli and hate carrots”（我喜欢花椰菜，讨厌胡萝卜）这两个句子转换成同一组标记[and; broccoli; carrots; hate; i; like]，因此被认为是完全一样的。与此同时，我们没有尝试理解句子的含义，只需要识别与特定行为有联系的词语。

我要强调的另一点是，虽然我们的标记化看起来相当简单，但是已经包含了许多隐含的决策。我们决定将“Programming”和“programming”当成同一个词，忽略大小写。这是个合理的假设吗？可能是，也可能不是。如果你曾经参加过在线讨论（如论坛或者YouTube评论），可能同意大量使用大写字母往往代表着讨论质量正在走下坡路。因此，这证明大小写很重要，可能提供分类消息的相关信息。另一个隐含的决定是丢弃“！”，这合理吗？标点也可能很重要。

好消息是，我们无须争论大小写或者标点符号是否重要，可以很容易地在以后的交叉验证中得到这个问题的答案。正如W. Edwards Deming的不朽名言：“我们信仰上帝——其他人都必须用数据证明自己。”为每个假设创建不同的模型，比较它们的表现，让数据做出决定。

2. 简单组合得分

现在我们已经决定将短信分解为3个标志——“driving”“cant”和“txt”——仍然必须想出计算消息是非垃圾短信或垃圾短信概率的方法。“txt”表明有很大的概率是垃圾短信，而“driving”则指向非垃圾短信。我们如何组合所有证据？如果应用贝叶斯定理，确定在包含全部3个标记的条件下，某条短信是垃圾短信的概率，可以得到如下算式：

这个公式看上去有些可怕。但是，如果我们做一个简化的假定，事情就容易多了。我们假定这些标记相互独立——也就是说，在一条短信中看到一个标记对其他标记是否出现没有任何影响。在这种情况下，计算公式是：

P (SMS包含driving、cant、txt |SMS是垃圾短信 )

　　　　　　=P (SMS包含“driving”| SMS是垃圾短信 )

　　　　　　×P (SMS包含“cant”| SMS是垃圾短信 )

　　　　　　×P (SMS包含“txt”| SMS是垃圾短信 )

对以上公式，借用一点点贝叶斯定理的“柔道”翻身之术，可以得到如下结果：

从根本上，我们做了如下工作：没有尝试建立完整、复杂的英语模型，而是使用简单得多的模型。想象一下，你有两个装单词的大桶，一个用于垃圾短信，另一个用于非垃圾短信，它们包含的单词所占比例不同。消息通过从其中一个桶里随机选择单词组合生成。当然，这是相当可笑的语言模型。与此同时，该模型也有一些明显的好处。更“正确”的模式可能专用于特定语言（例如需要考虑其语法和句法），因而有可能对其他语言无效。因此，从较差但对任何语言或者文档类型效果相似且容易处理的模型开始，看看它会将我们引向何方！

3. 简化的文档得分

现在，我们几乎已经为编码实现分类器做好了准备。我们可以轻松求取P（SMS是垃圾短信）——训练集中垃圾短信的比例，以及P（SMS包含“X”|SMS是垃圾短信）——包含标记“X”的垃圾短信比例。

投入工作之前，先进行一些最后的调整。首先，你可能已经注意到，在垃圾短信和非垃圾短信中，冗长的贝叶斯公式都包括同一除数项——P（SMS包含“driving”“cant”“txt”）的运算。最终，我们感兴趣的是决定一条消息是垃圾短信还是非垃圾短信，而不是精确的概率。在这种情况下，我们可以去掉公共项，节约不必要的计算，简单地计算“得分”而非概率。

Score (SMS是垃圾短信｜SMS包含driving、cant和txt )

　　　　　　　　　　　=P (SMS包含“driving”| SMS是垃圾短信 )

　　　　　　　　　　　×P (SMS包含“cant”| SMS是垃圾短信 )

　　　　　　　　　　　×P (SMS包含“txt”| SMS是垃圾短信 ) × P（SMS是垃圾短信 ）

如果Score（垃圾短信）>Scrore（非垃圾短信），我们将把消息归类为垃圾短信。

实际上，如果我们仅需要一个得分，可以进一步解决另一个问题——与精度相关的问题。 从定义上看，从短信中任何特定标记上观察到的概率都是小于1的数字（通常接近0）。由于我们的公式包含这些概率的乘积，结果也接近0，可能造成舍入误差。

为了避免这一问题，习惯上是使用一种旧的技巧，将计算转换为对数。这方面的细节不是很重要，但正是使用这种方法的原因。因为log (a * b) = log a + log b，可以将公式从乘积转换成总和，避免了舍入问题。而且，因为对数是递增函数，通过对数转换公式将保留得分的排名。所以，我们使用如下公式代替原公式，求得消息的分数：

Score (SMS是垃圾短信 | SMS包含driving、cant和txt )=log (P ( SMS是垃圾短信 ))+

log（Laplace (SMS包含“driving”| 垃圾短信 )）+

log（Laplace (SMS包含“cant”| 垃圾短信 )）+

log（Laplace (SMS包含“txt”| 垃圾短信 ) )

在一定程度上，上式澄清了算法逻辑。每个标记都有一个非垃圾短信得分和垃圾短信得分，量化了它属于这两种情况的强度。尝试决定某个文档是不是垃圾短信时，算法首先计算垃圾短信得分——垃圾短信基准水平，每个标记都增加或者减少文档的垃圾短信得分，独立于其他标记。如果文档的垃圾短信得分最终高于非垃圾短信得分，则判定文档是垃圾短信。

四、实现分类器

我们已经讨论了许多数学和模型方面的内容，但是还没有讨论编码。幸运的是，这就是我们所需要的一切：现在，我们已经为实现一个简单的贝叶斯分类器做好了准备。从根本上说，分类器依赖于两个要素：将文档分解为标记的标记化程序，以及一组标记——用于求得文档得分的单词。有了这两个组件，我们需要从一个示例样本中知道每个标记的垃圾短信和非垃圾短信得分，以及每一组的相对权重。

图4概述了学习阶段。从具备标签的消息语料库开始，将它们分解为两组：垃圾短信和非垃圾短信，并计量其相对规模。然后，对选中的一组标记（“free”“txt”和“car”），计量其频度，将每一组文档归纳为对应于其总体权重的得分，为每个标记求得特定组别的得分。

得到上述信息之后，新文档的分类遵循图5中概述的过程：标记化文档，根据存在的标记计算每组得分，并预测最高得分的组。

在这个特殊的例子中，一旦文档标记化，我们搜索每个单独标记（忽略其他情况）是否都有一个得分，计算每组的总体得分，确定哪一组更可能匹配。

图4 简单贝叶斯学习阶段

图5 简单贝叶斯分类器概况

1. 将代码提取到模块中

为了避免在脚本中聚集过多代码，我们将分类器提取为一个模块。这只需用鼠标右键单击解决方案，选择“新建项”（Add New Item），然后选择“源文件”（Source File）。将文件改名为NaiveBayes.fs，删除其中的所有默认代码，用如下代码代替：

namespace NaiveBayes

module Classifier =

    let Hello name = printfn "Hello, %s" name

最后，用鼠标右键单击该文件并选择“上移”（Move up）（或者Alt+向上箭头），直到 NaiveBayes.fs出现在解决方案文件列表中的第一个（也可以在解决方案资源管理器中选择文件，使用“在上方添加”（Add Above）或者“在下方添加”（Add Below）将文件直接添加到所需的位置）。现在，你已经创建了一个文档，可以开始编写函数了，从脚本中调用，或者从F#或者C#项目中使用。为了说明，下面是从当前脚本使用Hello函数的方法：

#load "NaiveBayes.fs"
open NaiveBayes.Classifier
Hello "World"

■ 注意：

你可能觉得疑惑，为什么必须将刚创建的文件上移。和C#不同，F#解决方案中的文件顺序很重要，主要原因是类型推理系统。编译器查看到目前为止代码文件中已有的定义，自动理解类型的含义。类似地，如果打算在代码中使用函数 f，该函数必须在使用它的代码之前定义。这是一个附加的限制，但是在我看来，相对于类型推理的好处，这种代价非常合理。而且，作为有趣的副作用，这提供了F#解决方案中的自然顺序，使它们容易解读：从第一行开始正向阅读，或者从最后一行开始反向阅读！

2. 文档评分与分类

有了模块，我们就可以在模块中写入上述算法，然后使用脚本文件以该算法探索数据。我们将遵循典型的F#模式，由底向上构建，编写小的代码块组成更大的工作流。模型的关键要素是得分计算，这个功能计量文档属于某一组（如垃圾短信）的证据强度。

得分取决于两个成分：该组在整个语料库（训练数据）中出现的频度，以及该组中找到某些标记的频度。我们首先定义表现问题域的两个类型。我们不将文档和标记定义为字符串，而是直呼其名，定义一个Token类型——字符串的类型别名。这将使我们在类型签名上更加清晰。例如，现在可以定义一个Tokenizer（标记化程序）函数，以一个字符串（文档）为 参数，返回一组标记。类似地，使用TokenizedDoc类型别名，为已经标记化的文档提供一个名称：

type Token = string
type Tokenizer = string -> Token Set
type TokenizedDoc = Token Set

为了分类一个新文档（标签未知），我们需要使用已有的有标签文档样本，计算它在每个可能组的得分。这样做需要每个组的两部分信息：比例（该组在整个数据集中被找到的频率）以及为模型选择的每个标记的得分，这表明了标记指向该组的强度。

我们可以用一个数据结构DocsGroup建立模型，它包含Proportion（该组在整个数据集中被找到的频率）和TokenFrequencies——将每个标记与数据集中频率（用拉普拉斯方法校正）关联的Map类型（与字典作用类似的F#数据结构）。举个例子，创建两个DocsGroup——一个用于非垃圾短信，另一个用于垃圾短信——非垃圾短信DocsGroup包含整个数据集中非垃圾短信的比例，对于我们感兴趣的每个标记，还包含实际标记和出现在非垃圾短信中的频率。

type DocsGroup =
    { Proportion:float;
      TokenFrequencies:Map<Token,float> }

假定某个文档已经分解为一组标记，计算给定组的得分相当简单。我们没有必要担心这些数字的计算方法。如果这一部分已经完成，需要做的就是加总分组频率的对数，以及每个标记出现在已标记化文档中和模型使用的标记列表中频率的对数：

程序清单2 计算文档得分

let tokenScore (group:DocsGroup) (token:Token) =
    if group.TokenFrequencies.ContainsKey token
    then log group.TokenFrequencies.[token]
    else 0.0

let score (document:TokenizedDoc) (group:DocsGroup) =
    let scoreToken = tokenScore group
    log group.Proportion +
    (document |> Seq.sumBy scoreToken)

然后，文档分类就只是用标记化程序将其转换为标记，找出可能的DocGroups列表中具有最高得分的分组，并返回其标签：

程序清单3 预测文档标签

let classify (groups:(_*DocsGroup)[])
             (tokenizer:Tokenizer)
             (txt:string) =
    let tokenized = tokenizer txt
    groups
    |> Array.maxBy (fun (label,group) ->
        score tokenized group)
    |> fst

你可能对classify函数中的groups:(*DocsGroup)[]有些疑惑，为什么对每组文档使用(DocType*DocsGroup)元组，神秘的_符号是什么？请你仔细思考，到目前为止，我们所做的并不依赖于具体的标签。我们考虑了垃圾短信和非垃圾短信，但是同样可以将其应用到不同语料库，例如，预测电影评论是否对应于1、2、3、4或者5星评级。因此，我决定使这些代码通用；只要有一组具备一致标签类型的示例文档，这些代码就有效。_符号表示“类型通配符”（任何类型都得到支持），如果检查classify函数签名，就会看到：groups:('a * DocsGroup) [] -> tokenizer:Tokenizer -> txt:string -> 'a。通配符已经被'a（表示泛型类型）所代替，函数也返回一个'a，这是（泛型）标签类型。

3. 集合和序列简介

这里已经引入了两个新类型——序列和集合。我们从集合开始简短地讨论这两种类型，集合代表一组唯一项目，主要目的是回答“项目X 是否属于集合S”的问题。考虑到我们想要搜索特定单词（更通用的说法是标记）是否出现在SMS中，以确定SMS可能是垃圾短信还是非垃圾短信，使用可以有效比较项目集合的数据结构似乎很合理。通过将文档归纳为几组标记，就可以快速识别是否包含某个标记（如“txt”），而无须付出使用Contains()字符串方法的代价。

Set模块提供了许多围绕集合运算的方便函数，如下面的片段所示。在F# Interactive窗口中输入以下内容：

> let set1 = set [1;2;3]
let set2 = set [1;3;3;5];;

val set1 : Set<int> = set [1; 2; 3]
val set2 : Set<int> = set [1; 3; 5]

这段代码创建了两个集合，注意从set2删除重复的值3的方法。Set模块提供了可以计算并集及交集的函数；

> let intersection = Set.intersect set1 set2
let union = Set.union set1 set2;;

val intersection : Set<int> = set [1; 3]
val union : Set<int> = set [1; 2; 3; 5]

集合还输出一个有用的函数difference，从一个集合中减去另一个集合，也就是说，从第一个集合中删除第二个函数中的每个元素：

> let diff1 = Set.difference set1 set2
let diff2 = Set.difference set2 set1;;

val diff1 : Set<int> = set [2]
val diff2 : Set<int> = set [5]

注意，与intersection和union函数不同，difference函数不可交换。也就是说，参数的顺序很重要，前一个例子中已经做了说明。最后要注意，集合是不可变的，一旦创建集合，它就不能修改：

> let set3 = Set.add 4 set1
set1.Contains 4;;

val set3 : Set<int> = set [1; 2; 3; 4]
val it : bool = false

在set1中添加4创建一个新集合set3，它包含4，但是原始集合set1没有受到这一运算的影响。

我们引入的另一个类型——序列，是惰性求值的元素序列——也就是说，它是仅在必要时计算的集合，这样可以潜在地减少内存或者计算使用量。在F# Interactive中尝试如下代码：

> let arr1 = [| for x in 1 .. 10 -> x |]
let seq1 = seq { for x in 1 .. 10 -> x };;

val arr1 : int [] = [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10|]
val seq1 : seq<int>

表达式arr1和seq1非常类似；它们都生成从1到10的整数。但是，数组立即显示全部内容——这是立刻求值的。相反，seq1显示为整数的一个序列，但是没有进一步的细节。实际内容只在代码需要的时候才生成。下面的例子可以进一步证明这一点，它取得seq1并将每个元素加倍，构建一个新的序列。注意，我们在序列中增加了其他的作用，每当序列的一个元素生成，就打印输出已经映射的元素：

> let seq2 =
    seq1
    |> Seq.map (fun x ->
        printfn "mapping %i" x
        2 * x) ;;

val seq2 : seq<int>

同样，结果是一个尚无实际内容的序列，因为目前没有任何必要的内容。我们改编代码，要求得到前3个元素的总和：

> let firstThree =
    seq2
    |> Seq.take 3
    |> Seq.sum;;
mapping 1
mapping 2
mapping 3

val firstThree : int = 12

执行上述代码时，打印输出“mapping 1”“mapping 2”和“mapping 3”，说明序列取出了前3个元素，这是计算总和所必需的。但是，剩下7个元素仍然没有必要，现在仍然没有求值。

那么，在我们已经有数组这样完美的集合类型的情况下，为什么还要有序列呢？第一个好处是惰性求值。因为序列只在“必要”时求值，我们可以用它们生成无限序列。例如，生成数组完全不可能生成的某种集合。下面的片段提供了一个人为的例子：我们创建一个由1和−1交替形成的无限序列。很显然，在内存中实例化这种无限序列是不可能的，但是既然定义了它，我们就可以使用，例如计算任意数量元素的总和：

> let infinite = Seq.initInfinite (fun i -> if i % 2 = 0 then 1 else -1)
let test = infinite |> Seq.take 1000000 |> Seq.sum;;

val infinite : seq<int>
val test : int = 0

F#序列常常得到使用的另一个原因是，它们等价于C#的IEnumerable，所有.NET集合类型本身都可以当成序列处理，因此，Seq模块提供的函数可以利用实际集合类型中没有出现的功能性，对其进行操纵。考虑下面的例子：

> let arr = [| 1;2;2;3;4;4;4|]
let counts =
    arr
    |> Seq.countBy (fun x -> x)
    |> Seq.toArray;;

val arr : int [] = [|1; 2; 2; 3; 4; 4; 4|]
val counts : (int * int) [] = [|(1, 1); (2, 2); (3, 1); (4, 3)|]

我们生成了一个整数数组，然后想要计算每个整数出现了多少次。虽然数组没有直接支持这一功能（至少，在F# 4.0正式交付之前没有），但是序列有此功能，所以我们在数组上调用Seq.countBy，将结果转换为数组，以便触发序列求值。

■ 提示：

虽然序列有许多好处（无他，谁不想只计算所需要的？），但是惰性求值也有缺点，包括增加了调试的复杂性。

4. 从文档语料库中学习

为了使用classify函数，我们必须拥有每组文档的摘要数据。生成该摘要数据需要哪些数据？组的比例需要组中的文档数以及文档总数。对于选择用于分类器的每个标记，必须计算标记化文档包含该标记的比例（经过拉普拉斯修正）。

■ 注意：

不管使用何种语言或者风格，这样实现应用程序设计都很有效：创建具备单一功能、具备清晰定义任务的小型组件，不用担心程序中其余部分发生的情况。这有助于提取具备最小数据结构的清晰模型。然后，你可以将所有组件连接起来，那时，改变设计（例如为了性能）就不会很困难。

收集摘要数据的明显方法是编写一个函数，签名中以文档集合为参数，返回包含传递文档组分析结果的DocsGroup。我们仍然假定获得的数据形式对手上的任务很便利，如何实现这一点将在以后研究。

首先，创建两个助手函数，为我们完成比例和拉普拉斯平滑比例计算中的整数-浮点转换，帮助计算存在特定标记的文档数量：

let proportion count total = float count / float total
let laplace count total = float (count+1) / float (total+1)
let countIn (group:TokenizedDoc seq) (token:Token) =
    group
    |> Seq.filter (Set.contains token)
    |> Seq.length

现在，我们已经有了分析有相同标签的一组文件、然后将其归结为一个DocsGroup所需的所有组件，下一步需要做的就是：

(1) 计算该组与文档总数的比例。

(2) 对我们确定用于分类文档的每个标记，找出在组中的拉普拉斯修正比例。

程序清单4 分析一组文档

let analyze (group:TokenizedDoc seq)
            (totalDocs:int)
            (classificationTokens:Token Set)=
    let groupSize = group |> Seq.length
    let score token =
        let count = countIn group token
        laplace count groupSize
    let scoredTokens =
        classificationTokens
        |> Set.map (fun token -> token, score token)
        |> Map.ofSeq
    let groupProportion = proportion groupSize totalDocs

    {
        Proportion = groupProportion
        TokenFrequencies = scoredTokens
    }

■ 注意：

一定要计算标记的数量，我们将通过计算单词在多少文档中出现，确定其出现频率。这对于短消息非常合适，但是对更长的文档却不是很好。如果你试图识别一本书是关于何种主题（如计算机）的，计算这个单词出现的次数可能比简单地问“这个单词在本书中是否至少出现一次”更好。我们用于SMS的这种方法称为“单词集”；另一种标准方法“单词袋”取决于单词的整体频率，可能更适合于某些文档类型。

我们几乎已经完成工作了，现在已经知道如何分析单独的文档组，只需要编排这些代码块，完整地实现图4中概述的算法。对于文档及其标签的一个组合，我们需要：

(1) 将每个文档分解为标记。

(2) 按照标签分隔它们。

(3) 分析每个组。

程序清单5 从文档中学习

let learn (docs:(_ * string)[])
          (tokenizer:Tokenizer)
          (classificationTokens:Token Set) =
    let total = docs.Length
    docs
    |> Array.map (fun (label,docs) -> label,tokenizer docs)
    |> Seq.groupBy fst
    |> Seq.map (fun (label,group) -> label,group |> Seq.map snd)
    |> Seq.map (fun (label,group) -> label,analyze group total classificationTokens)
    |> Seq.toArray

任务就要圆满完成了。从整个过程中，我们真正想得到的是一个函数，以字符串（原始SMS消息）为参数，根据从文档训练集中学到的，返回具有最高得分的标签。

程序清单6 训练简单的贝叶斯分类器

let train (docs:(_ * string)[])
          (tokenizer:Tokenizer)
          (classificationTokens:Token Set) =
let groups = learn docs tokenizer classificationTokens
let classifier = classify groups tokenizer
classifier

程序大体就是如此，只花了大约50行代码，我们就得到了一个能够正常工作的简单贝叶斯分类器。

五、 训练第一个分类器

实现通用算法之后，我们最终可以回到手上的问题——识别哪些消息是非垃圾短信，哪些是垃圾短信。Train函数的签名提供了目标的清晰概况：要获得分类器，需要一个示例训练集、一个标记化程序和选用的标记。我们已经得到了训练集，现在的目标是使用交叉验证指导分析，确定标记化程序和标记的最佳组合。

1. 实现第一个标记化程序

考虑到上述情况，我们先完成可行的最简单工作，首先是标记化。我们所要做的是取得一个字符串，将其分解为单词，忽略大小写。

这项工作需要正则表达式：\w+模式匹配由一个或者多个“语言符号”（也就是字母或者数字，不包含标点符号）组成的“单词”。我们用该模式创建一个正则表达式matchWords，在script.fsx中按照经典的管道结构编写一个tokens函数，将输入字符串转换为小写，并应用正则表达式。matchWords.Matches创建应用表达式时找到的所有匹配项的集合MatchCollection。我们将该集合转换为Match序列，读出匹配值（每个匹配的字符串），最后将其转换为一个包含正则表达式识别出的所有单词的集合。在脚本文件中现有的用于读取数据集的代码之后，添加如下代码：

程序清单7 使用正则表达式标记化一行文本

open System.Text.RegularExpressions

let matchWords = Regex(@"\w+")

let tokens (text:string) =
    text.ToLowerInvariant()
    |> matchWords.Matches
    |> Seq.cast<Match>
    |> Seq.map (fun m -> m.Value)
    |> Set.ofSeq

这段代码看起来有些粗糙，说实话，如果不是因为.NET正则表达式奇怪的设计特征，它看上去应该更简单。无论如何，我们已经有了所需要的东西：将字符串分解为所包含单词的函数。

2. 交互式验证设计

初看之下，程序清单7中的代码似乎可以完成我们所需的功能。但是“似乎可以”还不能令人满意，更好的做法是验证实际工作情况。用C#编码时，我的习惯是采用测试驱动开发（TDD）：先填写一个测试，然后编写满足要求、通过测试的代码。TDD的好处之一是可以独立运行整个应用程序的小部分代码，快速确认它按照意图工作，然后逐步充实设计。在F#中，我倾向于采用稍有不同的工作流。F# Interactive可以实现更流畅的设计试验方式。你可以简单地在F# Interactive中试验，一旦设计成型，则提升代码进行单元测试，而不是立即提交设计并编写相关测试——那可能需要在以后重构。

在我们的例子中，检查token函数是否正常工作很简单。只需要在FSI中输入下面的语句并运行：

> tokens "42 is the Answer to the question";;

你将立刻在F# Interactive窗口中看到结果：

val it : Set<string> = set ["42"; "answer"; "is"; "question"; "the"; "to"]

我们的函数看起来工作得很好。所有单词已经分隔，包括数字“42”，重复的“the”在结果中只出现一次，“Answer”中的大写字母“A”也已经转换为小写。此时，如果我们编写的是用于生产环境的真实库，可以将token函数从探索性脚本中转移到解决方案中的相应文件，然后将这一个小代码片段转换为真正的单元测试。现在，我们“只是探索”，所以将保持原状，不马上编写测试。

3. 用交叉验证确立基准

有了一个模型，我们就要观察它的运行状况。我们将要使用的脚本和以前一样，所以已经加载了数据集中的所有短信——（DocType * string）数组我们将使用交叉验证，数据集的一部分用于训练，剩下的保留，用于验证每个模型效果好坏。我随意保留1000个观测值用于验证，剩下的观测值都用于训练。为了确认所有代码正常工作，我们尝试一个相当粗糙的模型，只使用标记“txt”进行决策：

#load "NaiveBayes.fs"
open NaiveBayes.Classifier

let txtClassifier = train training wordTokenizer (["txt"] |> set)

validation
|> Seq.averageBy (fun (docType,sms) ->
    if docType = txtClassifier sms then 1.0 else 0.0)
|> printfn "Based on 'txt', correctly classified: %.3f"

在我的机器上得出的正确率为87.7%。这已经很不错了！不是吗？如果没有背景信息，87.7%这样的数字似乎已经很令人满意，但是必须正确看待。如果我使用最蠢的模型，不管SMS的内容为何都始终预测“非垃圾邮件”，在验证集上的成功率也可以达到84.8%，因此87.7%的成绩没有什么了不起。

我们所要强调的重点是，应该始终从确立基准开始：如果使用可能的最简策略，预测的效果如何？对于分类问题，始终预测频率最高的标签（正如上面所做的）可以提供一个出发点。对于时间序列模型（根据过去的情况预测明天），预测明天的情况和今天一样是经典的做法。在一些情况下，20%的分类正确率可能已经很出色了，而在其他情况下（例如非垃圾短信和垃圾短信的例子），85%的正确率都令人失望。基准完全取决于数据。

第二个重点是，应该很小心地对待数据集的构建方式。在分割训练和验证集时，我简单地使用前1000个数据项作为验证集。想想看，我的数据集按照标签排序，所有垃圾短信示例在前，然后是所有非垃圾短信。这很糟糕：我们实际上在几乎只包含非垃圾短信的样本上训练分类器，只在垃圾短信上进行测试。你最起码可以预计到，评估质量将会相当差，因为分类器学习识别所用的数据与实际处理的数据大不相同。

对于所有模型，这都是个问题。然而，在我们的例子中因为简单贝叶斯分类器的工作方式，这个问题特别严重。回忆一下算法的工作原理，本质上，简单贝叶斯算法以两个因素确定权重：标记在不同组的相对频率，以及组本身的频率。质量不佳的采样不会影响第一部分，但是，每个组的频率可能完全脱离实际，这将大大影响预测。例如，训练集中非垃圾短信多于垃圾短信，将导致分类器完全低估消息是垃圾短信的可能性，偏向于预测非垃圾短信，除非有占据压倒性优势的证据。

重点是，在运行可能很冗长的模型训练计算之前，必须问自己两个问题：“我使用的样本是否与模型以后所要处理的真实数据类似？”以及“我的训练集和验证集组成是否基本相同？”在某些情况下，使用失真的样本可能完全没有问题——你只需要意识到这一点即可。对于简单贝叶斯分类器或者基于贝叶斯定理的方法，特别要注意这类失真，它们对模型的质量将有深远的影响。如果检查SMS数据集，应该会发现它看上去大体是平衡的：在训练和验证样本中，非垃圾短信和垃圾短信的比例大约相同。

六、 改进分类器

现在我们已经有了基准—— 低于84.4%是糟糕的结果，至少要超过87.7%。是时候观察使用可以自由支配的两大手段（标记化程序和分类器选用的标记）能达到什么效果了。

1. 使用每个单词

利用一个单词，我们就能将分类器的正确率从84.8%提升到87.7%。如果使用每个可用的标记代替单个词汇，预测正确率当然应该大幅提高。我们来尝试一下这个思路，首先，必须从训练集中提取每个标记。我们编写一个vocabulary函数，对每个文档应用标记化程序，将标记合并为单一集合，实现上述功能。然后，从训练集中读取标记——用snd取出每个文档元组中的第二个元素，通过管道进入vocabulary函数：

let vocabulary (tokenizer:Tokenizer) (corpus:string seq) =
    corpus
    |> Seq.map tokenizer
    |> Set.unionMany

let allTokens =
    training
    |> Seq.map snd
    |> vocabulary wordTokenizer

干脆利索。现在我们可以使用大的标记列表训练新的分类器，评估其性能：

let fullClassifier = train training wordTokenizer allTokens

validation
|> Seq.averageBy (fun (docType,sms) ->
    if docType = fullClassifier sms then 1.0 else 0.0)
|> printfn "Based on all tokens, correctly classified: %.3f"

结果相当令人失望，没有出现我们希望的重大改善：“根据所有标记，正确分类的比例为0.864”。我们必须面对这一失败，得到的模型仅仅胜过最简单的预测程序，比依赖单一词汇“txt”决策的前一个模型更差。

在此得到的教训是，盲目地向一个标准算法中投入许多数据，只会离目标越来越远。在我们的例子中，精心选择了一个特征，形成的模型更简单、更快、更擅长于预测。选择合适的特征是构建好的预测程序的关键部分之一，也是我们将要尝试推进的。在本例中，可以在两方面改变特征的定义，而无须更改算法本身：可以使用不同的标记化程序，以不同方式利用消息，也可以选择（或者忽略）不同的标记集合。

忙于这些工作时，我们将会多次重复某些代码，可以将整个“训练——评估”过程打包为一个函数，该函数以一个标记化器和一组标记为参数，运行训练过程，打印输出评估结果：

程序清单8 通用模型评估函数

let evaluate (tokenizer:Tokenizer) (tokens:Token Set) =
    let classifier = train training tokenizer tokens
    validation
    |> Seq.averageBy (fun (docType,sms) ->
        if docType = classifier sms then 1.0 else 0.0)
    |> printfn "Correctly classified: %.3f"

评估特定模型变成一行代码：

> evaluate wordTokenizer allTokens;;
Correctly classified: 0.864

这为我们提供了相对简单的推进过程：选择一个标记化器和一组标记，调用evaluate函数观察特定组合是否好于之前尝试的组合。

2.大小写是否重要？

我们从标记化程序开始，回忆之前的讨论，目前使用的wordTokenizer函数忽略大小写，从它的角度，“txt”和“TXT”之间没有差别——两者被视为同一个标记。

这并不是不合理的做法。例如，考虑消息“Txt me now”和“txt me now”（给我发文本消息），忽略大小写，我们实质上将这两条消息视为意义上没有任何差别的消息。大小写没有带来任何相关的信息，可以当成噪声。

相反，考虑这两条消息：“are you free now?”（你现在有空吗？）和“FREE STUFF TXT NOW”（这是有关免费物品的短信）——这时，忽略大小写就可能丢失信息。

那么，哪一种方法才对呢？我们来尝试一下，看看不将所有字符串转换为小写的不同标记化程序是否比wordTokenizer更好：

程序清单9 使用正则表达式标记化一行文本

let casedTokenizer (text:string) =
    text
    |> matchWords.Matches
    |> Seq.cast<Match>
    |> Seq.map (fun m -> m.Value)
    |> Set.ofSeq

let casedTokens =
    training
    |> Seq.map snd
    |> vocabulary casedTokenizer

evaluate casedTokenizer casedTokens

在FSI中运行达到87.5%的正确率。一方面，我们的结果仍然低于依赖“txt”的简单分类器；另一方面，两者已经相当接近（87.5%对 87.7%），这明显好于使用所有单一标记的wordTokenizer（86.4%）。

3. 简单就是美

我们得到了表面上更好的标记化程序，但是，添加大量特征所得到的结果仍然是效果更差、更缓慢的分类器。这明显不理想，也是反直觉的：增加更多信息怎么可能使模型更差？

让我们从另一方面去看待问题，思考之前的单标记模型为什么工作得更好。我们选择“txt”作为标记的原因是它在垃圾短信中经常发现，而在非垃圾短信中很少出现。换言之，它很好地区分两组，相当特定于垃圾短信。

我们现在做的是使用每个单一标记，不管它们的信息量如何。结果是，我们在模型中可能引入了相当多的噪声。更有选择性的方法——可能只选择每个文档组中最常见的标记，会得到什么样的结果呢？

让我们从一个简单的函数开始，给定一组原始文档（简单字符串）和一个标记化程序，将返回最常用的标记：

let top n (tokenizer:Tokenizer) (docs:string []) =
    let tokenized = docs |> Array.map tokenizer
    let tokens = tokenized |> Set.unionMany
    tokens
    |> Seq.sortBy (fun t -> - countIn tokenized t)
    |> Seq.take n
    |> Set.ofSeq

现在，我们可以将训练样本分拆为非垃圾短信（Ham）和垃圾短信（Spam），在此过程中去掉标签：

let ham,spam =
    let rawHam,rawSpam =
        training
        |> Array.partition (fun (lbl,_) -> lbl=Ham)
    rawHam |> Array.map snd,
    rawSpam |> Array.map snd

我们提取和计数每个组的标签，提取前10%，用Set.union将其合并为一个标记集合：

let hamCount = ham |> vocabulary casedTokenizer |> Set.count
let spamCount = spam |> vocabulary casedTokenizer |> Set.count

let topHam = ham |> top (hamCount / 10) casedTokenizer
let topSpam = spam |> top (spamCount / 10) casedTokenizer

let topTokens = Set.union topHam topSpam

现在，可以将这些标记整合为一个新的模型，评估其表现：

> evaluate casedTokenizer topTokens;;
Correctly classified: 0.952

正确率从87.5%一跃达到95.2%!这是可观的改善，实现这一飞跃不是通过增加更多的数据，而是通过删除特征。

4. 仔细选择单词

我们还能做得更好吗？试试看！通过选择标记的一个子集，只保留携带有意义信息的标记，我们得到了很明显的改善。按照这一思路，可以开始检查非垃圾短信和垃圾短信中最常用的标记，这相当容易实现：

ham |> top 20 casedTokenizer |> Seq.iter (printfn "%s")
spam |> top 20 casedTokenizer |> Seq.iter (printfn "%s")

运行上述语句产生表1中的结果：

表1 最常用的非垃圾短信和垃圾短信标记

我们立刻注意到两件事。首先，两个列表都很相似，在20个标记中，有8个是共同的（a、and、for、is、on、the、to、you）。而且，这些单词都非常通用，不管什么主题，任何语句都必然包含几个冠词和代词。这一列表并不重要，表中的标记可以描述为“填充材料”，它们没有告诉我们很多关于消息是非垃圾短信还是垃圾短信的情况，甚至在我们的分析中引入了一些噪声。从性能的角度看，这意味着我们花费了许多CPU周期分析传达有限甚至毫不相关信息的标记。因此，从分析中去掉这些标记可能是有益的。

在此之前，我想到了列表中出现的另一个有趣特征。和非垃圾短信不同，垃圾短信的列表中包含几个相当特殊的单词——如“call”“free”“mobile”和“now”，不包含“I”或者“me”。如果你考虑到这一点，那是很有意义的：常规的文本消息有许多种目的，而垃圾短信通常试图“钓鱼”，诱惑你做某些事情。在这样的背景下，看到“now”（现在）和“free”（免费）这些带着广告腔调的单词也就不足为奇了，因为通过奉承的方法达到目的通常没有错，垃圾短信很少和“I”（我）相关而更多地与“You”（你）相关也是正常的。

■ 注意：

什么是“钓鱼”？钓鱼是使用电子邮件、SMS或者电话从某人那里窃取财物的行为。钓鱼通常采用一定的社会工程（伪装成受尊重的机构、威胁或者引诱）使目标采取骗子无法独自完成的措施，比如单击一个在机器上安装恶意软件的链接。

我们将很快回到上述要点。与此同时，观察一下，能否删除“填充材料”。常见的方法是依赖这些单词的预定义列表，这通常称作“停用词”。在http://norm.al/2009/04/14/list-of- english-stop-words/上可以找到一个此类列表。遗憾的是，没有通用的正确方法，显然，这取决于编写文档所用的语言，甚至语境也很重要。例如，在我们的例子中，文本消息中常用的“you”缩写词“u”是一个很合适的“停用词”。但是，大部分标准列表不会包含它，因为这种用法与SMS的关联度极大，不太可能在其他文档类型中找到。

我们不依赖于停用词列表，而是采用更简单的方法。我们的topHam和topSpam集合中包含非垃圾短信和垃圾短信中最常用的标记。如果某个标记在两个列表中都出现，它很有可能就是在英语文本消息中常见的单词，不特定于非垃圾短信和垃圾短信。我们找出所有共有的标记（这对应于两个列表的交集），将它们从标记选择中删除，再次运行分析：

let commonTokens = Set.intersect topHam topSpam
let specificTokens = Set.difference topTokens commonTokens
evaluate casedTokenizer specificTokens

利用这一简单的更改，分类SMS消息的正确率从95.2%上升到了97.9%。这可以认为是相当好的结果了，离100%越近，改善越难实现。

5. 创建新特征

在尝试提出新想法时，我常常觉得有用的方法之一是颠覆问题，以便从不同角度观察。举个例子，当我编写代码时，通常从想象“快乐路径”——程序完成某项功能所需的最少步骤——开始，然后实现它们。在测试代码之前，这是很棒的方法，你的心思已经完全集中在成功路径上，而难以考虑失败的情况。所以，我喜欢在测试时将问题颠倒并提问：“使这个程序崩溃的最快方法是什么？”我发现这一招非常有效，而且使测试变得很有趣！

让我们来试试用这个方法改进分类器。对每个类别中最常见单词进行观察最终可以得到很明显的改善，因为贝叶斯分类器依赖于分类中的常见词以识别类别。观察一下每个文档类别中最少见的词如何？稍微修改一下前面编写的代码，就可以提取分组中最少使用的标记：

程序清单10 提取最少使用的标记

let rareTokens n (tokenizer:Tokenizer) (docs:string []) =
    let tokenized = docs |> Array.map tokenizer
    let tokens = tokenized |> Set.unionMany
    tokens
    |> Seq.sortBy (fun t -> countIn tokenized t)
    |> Seq.take n
    |> Set.ofSeq

let rareHam = ham |> rareTokens 50 casedTokenizer |> Seq.iter (printfn "%s")
let rareSpam = spam |> rareTokens 50 casedTokenizer |> Seq.iter (printfn "%s")

表2总结了结果：

表2 最少使用的非垃圾短信和垃圾短信标记

你是否注意到某种模式？垃圾短信列表中充满了电话号码或者文本编码。同样，这也很有意义：如果我成为“钓鱼”的目标，有人希望我做某件事情——在电话上，这意味着拨打某个号码或者用短信发送一个数字。

这也强调了一个问题：作为人类，我们立刻发现这个列表是“许多电话号码”，但是每个号码在模型中都被视为单独的标记，这些标记出现的很少。然而，SMS消息中存在电话号码似乎是垃圾短信的可能标记。我们可以创建一个新特征，捕捉消息是否包含电话号码，而不管这些号码是什么，解决这个问题。这将使我们能够计算电话号码在垃圾短信中出现的频率，并（潜在地）在我们的简单贝叶斯分类器中将其作为一个标记使用。

如果仔细研究少见标记列表，就有可能发现更特殊的模式。首先，列出的电话号码都有类似的结构：它们以07、08或者09开头，然后是9个其他号码。其次，列表中有其他一些数字，主要是5位数字，这很可能是短信编码。

我们为每种情况创建一个特征。每当看到07之后的9个数字，就将其转换为标记__PHONE__，每当遇到5位数字，就将其转换为__TXT__：

程序清单11 识别电话号码

let phoneWords = Regex(@"0[7-9]\d{9}")
let phone (text:string) =
    match (phoneWords.IsMatch text) with
    | true -> "__PHONE__"
    | false -> text

let txtCode = Regex(@"\b\d{5}\b")
let txt (text:string) =
    match (txtCode.IsMatch text) with
    | true -> "__TXT__"
    | false -> text

let smartTokenizer = casedTokenizer >> Set.map phone >> Set.map txt

smartTokenizer简单地将3个函数链接在一起。casedTokenizer函数取得一个字符串并返回一个字符串集合，包含单独识别的标记。因为它返回的是字符串集合，可以应用Set.map，对每个标记运行phone函数，将看起来像电话号码的标记转换为“__PHONE__”，然后同样执行txt函数。

在F# Interactive中运行如下代码，确认上述函数正常工作：

> smartTokenizer "hello World, call 08123456789 or txt 12345";;
val it : Set<string> =
  set ["World"; "__PHONE__"; "__TXT__"; "call"; "hello"; "or"; "txt"]

结果正如我们预期的那样——一切正常。在列表中人工添加刚刚创建的两个标记，尝试调整过后的标记化程序（如果不这么做，标记列表中仍然包含单独的数字，没有与“智能标记化程序”产生的__PHONE__标记匹配）：

let smartTokens =
    specificTokens
    |> Set.add "__TXT__"
    |> Set.add "__PHONE__"

evaluate smartTokenizer smartTokens

请击鼓喝彩……准确率又一次跃升，从96.7%上升到98.3%！考虑到目前的性能水平，这是非常了不起的提升，值得花一些时间讨论。我们转换了数据集，通过聚合现有特征创建了一个新特征。这一过程是开发好的机器学习模型的关键部分。从原始数据集（可能包含低质量数据）开始，随着对领域的理解的进一步深入，找出变量之间的关系，就可以不断将数据重塑为新的表现形式，更好地适应手上的问题。这种试验、将原始数据精炼为好的特征的循环是机器学习的核心。

6. 处理数字值

让我们以一个简短的讨论结束关于特征提取的部分。在本篇文章中，我们只考虑离散特征，也就是说，只取一组离散值的特征。对于连续特征（或者数值特征）该怎么办？例如，想象一下，如果你的直觉是消息的长度很重要，能否使用到目前为止已经有的想法？

可能性之一是将问题简化为已知的问题，将消息长度（0～140个字符）变成一个二分特征，将其分为两类——短消息和长消息。这样，问题就变成了“区分长消息和短消息的合适长度值是多少？”

我们可以直接用贝叶斯定理解决这个问题：对于指定的阈值，我们可以计算长于该阈值的消息是垃圾短信的概率。然后，识别“好”的阈值就只是测试不同数值，选择信息量最大的一个。下面的代码完成上述功能，应该不太难以理解：

程序清单12 根据短信长度计算是垃圾短信的概率

let lengthAnalysis len =

    let long (msg:string) = msg.Length > len

    let ham,spam =
        dataset
        |> Array.partition (fun (docType,_) -> docType = Ham)
    let spamAndLongCount =
        spam
        |> Array.filter (fun (_,sms) -> long sms)
        |> Array.length
let longCount =
        dataset
        |> Array.filter (fun (_,sms) -> long sms)
        |> Array.length

let pSpam = (float spam.Length) / (float dataset.Length)
let pLongIfSpam =
    float spamAndLongCount / float spam.Length
let pLong =
    float longCount /
    float (dataset.Length)

let pSpamIfLong = pLongIfSpam * pSpam / pLong
    pSpamIfLong

for l in 10 .. 10 .. 130 do
    printfn "P(Spam if Length > %i) = %.4f" l (lengthAnalysis l)

运行上述代码，将会看到一条短信是垃圾短信的概率随着长度的增长而显著增大，这并不奇怪。垃圾短信制造者发送许多消息，希望得到最合理的收益，因此会在单条SMS中加入尽可能多的内容。现在，我将暂时搁置这一话题，但是我希望说明的是，贝叶斯定理在许多不同的情况下都很方便，不需要花费太多的精力。

七、 理解分类错误

记得在正确看待、与简单基准比较之前，我们还认为87.7%的分类正确率很不错吗？我们可以将这个数字提升到98.3%，明显比基准要好得多。但是，每当将整个数据集归纳为单一数字时，从定义上说肯定要遗漏某些信息。人们喜欢用单一数字总结，因为这样容易比较。我的建议是：每当得到一个统计数字时，应该仔细思考该数字可能遗漏或者隐藏的细节。

在我们的例子中，所知道的是在1000条消息中，平均会错误分类17条。我们所不知道的是模型的哪一部分造成了错误。同样的数字（98.3%）可能是不同情况造成的：这17条消息可能主要是垃圾短信、主要是非垃圾短信或者介于两者之间。根据语境的不同，可能会造成关键的差别。例如，我怀疑大部分人更喜欢忽略一两条垃圾短信、将其保留在收件箱中的分类器，而不喜欢过于激进、因为不正确地标记垃圾短信而将完全正常的消息自动放到垃圾短信文件夹中的分类器。

那么，我们的分类器表现如何？让我们来发现和计量其识别垃圾短信和非垃圾短信的优劣。这只需分离验证集中的垃圾短信和非垃圾短信，然后计算每组正确分类的百分比，很容易完成——只需要在脚本中添加几行，在F# Interactive中运行：

程序清单13 按照类别区分的分类错误

let bestClassifier = train training smartTokenizer smartTokens
validation
|> Seq.filter (fun (docType,_) -> docType = Ham)
|> Seq.averageBy (fun (docType,sms) ->
    if docType = bestClassifier sms
    then 1.0
    else 0.0)
|> printfn "Properly classified Ham: %.5f"
validation
|> Seq.filter (fun (docType,_) -> docType = Spam)
|> Seq.averageBy (fun (docType,sms) ->
    if docType = bestClassifier sms
    then 1.0
    else 0.0)
|> printfn "Properly classified Spam: %.5f"

产生的输出如下：

Properly classified Ham: 0.98821
Properly classified Spam: 0.95395

很不错，我们的分类器在两个类别上都工作得很好，在非垃圾短信组上表现最好 ——只有1.2%的消息分类错误。这一数字被称作“假阳性率”——检测出实际上不存在的情况的比率。类似地，“假阴性率”是忽略某个问题的比例。在我们的例子中，大约4.6%的垃圾短信未能检出。

那么，为什么说这些信息有用？原因有以下两点。

首先，深入了解分类错误，理解它们是假阳性还是假阴性，在评估分类器商业价值时极其重要。这种价值完全取决于环境，实质上取决于哪一类错误代价更高。因为一条消息被错误地分类为垃圾短信而错过与老板的会面，远比从收件箱中人工删除一条垃圾短信严重得多。在这种情况下，假阳性比假阴性代价大得多，不应该使用相同的权重。

深入了解错误还有助于我们将精力集中在正确的方向，避免在无意义的工作上浪费时间。如果我们的分类器已经达到100%的非垃圾短信识别率，剩下的唯一改进方向就在另一个类别。出发点可能是检查当前模型没有识别为垃圾短信的消息，看看是否出现某种模式？

理想状态下，我们所希望的是即使付出遗漏某些垃圾短信的代价，也要尽可能可靠地识别非垃圾短信。例如，实现这一点的途径之一是“调低”垃圾短信的灵敏度，而在非垃圾短信上更努力尝试。应急的方法是，我们可以减少来自垃圾短信方向的标记，增大来自非垃圾短信方向的标记。换言之，只保持较为特殊的垃圾短信标记——强烈的指标，而张大捕捉非垃圾短信标记的网。当前最佳模型中为每一类保留10%的最常见标记，作为替代，如果我们在非垃圾短信上保留20%，在垃圾短信上保留5%，将会得到什么样的结果？让我们来尝试一下，使用完全相同的代码，但是将topHam和topSpam修改为：

let topHam = ham |> top (hamCount / 5) casedTokenizer
let topSpam = spam |> top (spamCount / 20) casedTokenizer

利用上述代码得到的结果是：总体准确率从98.3%下降到97.4%，但是正确分类的非垃圾短信从98.8%上升到99%，垃圾短信从95.4%下降到92.8%。换句话说，我们以另一个类别为代价，获得了非垃圾短信上的小幅提升。0.2%的改进看起来可能不多，但是我们真正实现的是将错误率从每千条消息12次下降到10次，也就是在最重要的类别上实现了16.7%的改进。

八、 我们学到了什么？

我敢肯定，用这个模型还可以做得更多，毕竟，我们距离完美还有1.7%!但是，我将把这个问题留给读者作为兴趣练习，而将篇幅留给本文关键点的回顾。

首先，我们讨论了贝叶斯定理和独立性的概念。我觉得这一成果特别有趣，原因至少有两个。首先，贝叶斯定理的通用公式相当简单。其次，它很强大：贝叶斯定理提供了描述和量化两部分不完善信息之间关系的通用框架。它本身就是统计学和机器学习的一个关键成果，因为这两个学科都试图从不完整的样本中得出结论，找出数据之间的模式。也就是说，找出不独立的数据并加以利用。

当然，简单贝叶斯分类器本身在贝叶斯定理应用中微不足道：我们在文本信息的工作方式上做了一些简化的假设，以便使数学方法可行，只是为了展示应用贝叶斯定理的结果。文本标记化的过程可能比分类器本身更有趣。机器学习算法通常需要一组特征，原始的文本块并不能很好地适应这些模式。通过将文本分解为标志，识别和计算出现在一个文档中的单词数量，我们就能将文本转换为更方便的结构。

最后，我们花费很多时间改进基本模型，通过提取新特征加以完善。关键的要点是，我们始终使用相当简单的算法，但是仅仅花费时间理解数据、使用所得到的知识稍作重整，就能将模型的预测能力从中等提高到很好的水平。决定使用哪一个算法无疑是机器学习的重要部分之一，但是构建一个好的模型通常不是寻找唯一算法、魔法般地解决问题，而更多的是凭借对问题域的更深入理解，使用这些知识提取更好的特征。

在这个特例中，出现了几个模式。首先，数据并不总是越多越好。有些特征包含许多信息，有些则不然。找出信息量大的特征、消除其余特征可以为模型提供携带信号较多、噪声较少、更容易利用的信息。然后，我们看到了两个相反的现象，最终使用了保持单词大小写的标记化程序。我们意识到，原来使用的特征过于粗糙，因此将它们分解为多个更具体的特征（例如，“FREE”和“free”）。相反，我们注意到有许多电话号码，将其聚合成单个之前不存在的首要特征，以便观察其作用。同样，了解问题域和数据绝对是很重要的：如果好的算法以错误的方式观察特征，也不会走得太远，对特征的小更改往往能将一个普通的模型转化为出色的模型。

实用链接

(1) 加州大学欧文分校维护了一个非常出色的机器学习数据集知识库：http://archive. ics.uci. edu/ml/。

(2) 下面的网页包含一个实用的常见英语停用词列表：http://norm.al/2009/04/14/list-of- english-stop-words/。

(3) 如果你打算进一步探索文本处理方法，斯坦福大学的NLP页面有丰富的资源：http://nlp. stanford.edu/。

本篇文章节选自《机器学习项目开发实战》

内容简介

本书通过一系列有趣的实例，由浅入深地介绍了机器学习这一炙手可热的新领域，并且详细介绍了适合机器学习开发的Microsoft F#语言和函数式编程，引领读者深入了解机器学习的基本概念、核心思想和常用算法。书中的例子既通俗易懂，同时又十分实用，可以作为许多开发问题的起点。通过对本书的阅读，读者无须接触枯燥的数学知识，便可快速上手，为日后的开发工作打下坚实的基础。本书适合对机器学习感兴趣的.NET开发人员阅读，也适合其他读者作为机器学习的入门参考书。