每周学点大数据 | No.55分类算法——Naive Bayes

NO.55

分类算法——Naive Bayes

小可：说完了聚类，那么分类算法又是怎么做的呢？

Mr. 王：我们知道，分类是首先通过对训练集中大量数据的分析，训练出一个分类的模型或者说得出一个分类的标准，然后使用这个标准对后面再到来的数据进行分类。所以我们的大部分工作都集中在对训练集的处理上。这里介绍一种经典的分类算法——朴素贝叶斯分类器（Naive Bayes）。这种分类方法非常简单，但是非常有效。

小可：我在学概率论时听说过贝叶斯定理，和这个是一个道理吗？

Mr. 王：朴素贝叶斯分类器依据的核心原理就是贝叶斯定理。你还记得贝叶斯定理吗？

小可 ：假设有两个事件 A 和 B，它们之间具有这样的关系：

可是贝叶斯公式看起来也不像和分类有关系啊。

Mr. 王：现在我们就来谈谈贝叶斯公式是如何有效地运用在分类算法中，并形成了非常著名的贝叶斯分类器的。其实所有的分类方法都是希望经过训练后，模型可以输出某条数据记录最可能的分类，也就是通过训练集T 的训练，找到一条记录ri 最可能的分类cj。而“最可能”

这个概念用概率来描述和衡量是非常合适的。我们可以将上面描述的分类算法所要解决的问题，表示为概率P(ci|rj)，它的意义就是在数据项为r 的条件下，其分类是c 的概率。我们希望找到的就是：

即，使得P(ci|rj) 最大的ci。在这种思想的支持下，也就有了以朴素贝叶斯分类器为代表的贝叶斯分类方法。

小可：哦！这样的表述的确很有道理啊，将寻找最可能的分类，转换为使用概率的方法。

那么根据贝叶斯定理，就可以把P(ci|rj) 表示成：

Mr. 王：很好，这其实就是朴素贝叶斯分类器使用的核心方法。我们简单解释一下各个量的意义。P(ci) 表示ci 这个分类的先验概率，就是我们在遇到训练集之前，对ci 这个分类的先验认识。这个先验概率来自于我们对ci 的预先研究或统计结果，比如我们要通过贝叶斯方法确定一个人是不是患有疾病x，如果通过统计知道人群中只1% 的人有这种疾病，那么

P(cx)=0.01，而P(cnon-x)=0.99。

而 ( | ) j i P r c 是假设在 ci 成立的条件下，rj 出现的概率。这部分证据主要来自于训练集，观察训练集中rj 的各种属性与ci 的关联程度。这是在下面的计算中我们要重点讨论的部分。

小可：那rj 呢？

Mr. 王：其实不难发现，P(rj) 是一个和ci 无关的量。虽然它和计算P(ci|rj) 有着直接的关系，但是当我们要进行分类时，rj 已经确定，所以在实际的计算中无须计算它。不过这个量并不是完全没有意义的，rj 反映了这种特征的数据本身出现的概率。在贝叶斯公式的分子一定的情况下，如果P(rj) 很大，则说明它出现的概率本身就很高，而不论是不是在分类ci 中。从直观上看，这就不是一个很好的分类特征，比如说分本分类中的is、am、are，这样的词在所有的样本中出现得都很多，却与我们是不是对这篇文章感兴趣基本没什么关系。现在我们通过一个实际的例子，看看贝叶斯分类器是如何工作的。

比如有关于一批书籍的记录，表示为：

< 主题s，语言l，难度d，厚度t>

1 < 计算机，中文，易，薄> 喜欢

2< 计算机，中文，难，薄> 喜欢

3 < 计算机，中文，难，薄> 喜欢

4 < 计算机，中文，难，厚> 不喜欢

5 < 计算机，英文，易，厚> 不喜欢

6 < 电子，中文，易，薄> 喜欢

7 < 电子，中文，易，厚> 喜欢

8 < 电子，中文，难，厚> 不喜欢

9 < 电子，英文，易，厚> 不喜欢

10 < 电子，英文，易，薄> 不喜欢

这些书籍分别按照主题、语言、难度、厚度进行了特征标注，并且标注了读者A 是否喜欢这本书。现在有了一本书11 < 计算机，中文，易，厚>，我们希望知道读者A 是否会喜欢这本书，这时就可以运用朴素贝叶斯分类器。首先想一想，我们希望得到的是什么？

小可：我想可以用这个式子表示吧？

Mr. 王：很好，那么现在我们可以分别去求解：

还有

然后比较哪一个更大就可以了。

根据贝叶斯定理进行展开，就可以转而求解（这里可以忽略分母，它并不影响最终的分类

结果）：

和

小可：那么如何去求解

训练集中并没有这样的样本？

Mr. 王：其实这个问题可以解释一个小疑惑，就是朴素贝叶斯分类器为什么被称作“朴素的”贝叶斯分类器。这是因为它做了一个假设，就是某一个元组中一个属性的值对它最终属于哪一个类别的影响与其他属性值是相互独立的。每一个值的取值都独立地影响它属于的类别，之间不相关。这一假设被称为类条件独立性。而在实际生活中，这个并不是完全准确的，属性之间往往存在着一些联系。由于这个原因，我们叫它“朴素的”贝叶斯分类器。但在实际应用中，朴素贝叶斯分类器的准确率还是非常高的，可以和一些非常复杂的模型相媲美。

如果两个事件是条件独立的，那么就有乘法原理：

所以：

P(s=CS,l=Chinese,d=easy,t=thick|like)=P(CS|like)P(Chinese|like)P(easy|like)P(Cthick|like)。

小可：这样就可以通过like 中CS 的计数来求P(CS|like) 了。只要统计出在训练集中被标注为like 的书籍中CS 的计数，然后与like 的计数做商即可。果然计算变得非常容易了。

Mr. 王：依此类推，分别求出P(CS|like)、P(Chinese|like)、P(easy|like)，P(thick|like)，就可

以求出P(CS,Chinese,easy,thick|like)。也就是说，朴素贝叶斯分类器认为：

其中，a1…an 为rj 的n 个属性。

Mr. 王：接下来我们还需要求出先验概率P(like)。在这个例子中，只要通过对训练集中ike 和dislike 的计数来计算P(like) 就可以了。在其他的问题中，可以有很多不同的办法来确定先验概率，如果实在缺乏相关的先验知识，我们可以认为所有分类的概率都相等。现在我们来看看如何用MapReduce 框架来完成一个贝叶斯分类器的训练和搭建。在第一轮MapReduce 的Map 阶段，我们输入的键值对就是[ 记录编号 → < 类别, 特征> ]。

然后Map 会向外发出< 特征, 类别> → 1 这样的键值对。在Reducer 中，我们求出形如< 特征, 类别> →数量这样的键值对。

小可：这个跟word count 好像啊。

Mr. 王：本质上这个步骤就是一个word count 的操作。其实贝叶斯公式的训练过程，就是对样本中各种特征和类别进行统计的过程，其基本操作依赖的就是每一种特征和类别关联之后的数量，使用的方法其实就是word count。在第二轮MapReduce 中，我们要求解整个训练集中每一种特征一共有多少个元组，以方便求解各个概率。其实这个过程也是一个word count 的操作。只要让所有的Mapper 输入我们的那些记录 记录 记录编号 → < 类别, 特征> 这样的元组，每收到一个记录编号，就发送1，然后在Reducer 中，将收到的这些1 统计起来，得到一个特征→计数即可。

MapReduce 的算法框架如下所示。

Map #1 ：

输入：记录编号 → < 类别, 特征>

输出：< 特征, 类别> → 1

Reduce #1 ：

输出：< 特征, 类别> → 计数

Map #2 ：

输入：记录编号 → < 类别, 特征>

输出：特征 → 1

Reduce #2 ：

输出：特征 → 计数

Mr. 王：最后，我来简单总结一下分类和聚类这两类算法在大数据并行平台上的一些特点。在聚类中，一般算法都会经过多轮迭代或者处理步骤。比如在典型的k-means 算法中，我们要不断地重新去发现每个集合的均值，然后重新计算所有的点与这些均值的距离，再重新归类。最后我们还要通过不动点的判定，来确定整个平台是不是达到了一个收敛的状态。而分类算法往往是比较复杂的，我们选择了非常经典的朴素贝叶斯分类器，好在它的处理相对比较简单。由于分类是一种基于训练集的学习再对新来的元组进行分类的一种方法，我们

要做的就是去计算训练集的概率分布，并且用它去估计客观世界中的概率分布。所以，分类算法是一个计算概率分布的过程。一般来说，分类算法常常会涉及条件概率的求解。而概率的求解，我们可以通过计数的方法，体现在MapReduce 中，可以用一轮MapReduce 对分子计数，另一轮对分母计数，从而通过两次计数求出一个概率的值。在Apache Mahout 中，也有分类算法的实现，Mahout 的内部直接包含有一个Naive Bayes分类器的示例程序，如果感兴趣的话，不妨去试着运行一下它。不过要记住，Mahout 是一个基于Hadoop 的工具包，如果想要运行Mahout，就要先安装和配置一个Hadoop MapReduce 平台。

文章作者：王宏志

文章编辑：秦革