分类算法

何为分类算法？简单来说，就是将具有某些特性的物体归类对应到一个已知的类别集合中的某个类别上。从数学角度来说，可以做如下定义：

已知集合： $C=\{y_1,y_2,..,y_n\}$ 和 $I=\{x_1,x_2,..,x_m,..\}$ ，确定映射规则 $y=f(x)$ ，使得任意 $x_i \in I$ 有且仅有一个 $y_j \in C$ 使得 $y_j=f(x_i)$ 成立。

其中，C为类别集合，I为待分类的物体，f则为分类器，分类算法的主要任务就是构造分类器f。

分类算法的构造通常需要一个已知类别的集合来进行训练，通常来说训练出来的分类算法不可能达到100%的准确率。分类器的质量往往与训练数据、验证数据、训练数据样本大小等因素相关。

举个例子，我们日常生活中看到一个陌生人，要做的第一件事情就是判断其性别，判断性别的过程就是一个分类的过程。根据以往的生活经验，通常经过头发长短、服饰和体型这三个要素就能判断出来一个人的性别。这里的“生活经验”就是一个训练好的关于性别判断的模型，其训练数据是日常生活中遇到的形形色色的人。突然有一天，一个娘炮走到了你面前，长发飘飘，穿着紧身的衣裤，可是体型却很man，于是你就疑惑了，根据以往的经验——也就是已经训练好的模型，无法判断这个人的性别。于是你学会了通过喉结来判断其性别，这样你的模型被训练的质量更高了。但不可否认的是，永远会出现一个让你无法判断性别的人。所以模型永远无法达到100%的准确，只会随着训练数据的不断增多而无限接近100%的准确。

贝叶斯公式

贝叶斯公式，或者叫做贝叶斯定理，是贝叶斯分类的基础。而贝叶斯分类是一类分类算法的统称，这一类算法的基础都是贝叶斯公式。目前研究较多的四种贝叶斯分类算法有：Naive Bayes、TAN、BAN和GBN。

理工科的学生在大学应该都学过概率论，其中最重要的几个公式中就有贝叶斯公式——用来描述两个条件概率之间的关系，比如P(A|B)和P(B|A)。如何在已知事件A和B分别发生的概率，和事件B发生时事件A发生的概率，来求得事件A发生时事件B发生的概率，这就是贝叶斯公式的作用。其表述如下：

$P(B|A)={P(A|B)\times P(B)\over P(A)}$

朴素贝叶斯分类

朴素贝叶斯分类，Naive Bayes，你也可以叫它NB算法。其核心思想非常简单：对于某一预测项，分别计算该预测项为各个分类的概率，然后选择概率最大的分类为其预测分类。就好像你预测一个娘炮是女人的可能性是40%，是男人的可能性是41%，那么就可以判断他是男人。

Naive Bayes的数学定义如下：

1. 设 $x=\{a_1,a_2,..,a_m\}$ 为一个待分类项，而每个 $a_i$ 为 $x$ 的一个特征属性
2. 已知类别集合 $C=\{y_1,y_2,..,y_n\}$
3. 计算 $x$ 为各个类别的概率： $P(y_1|x),P(y_2|x),..,P(y_n|x)$
4. 如果 $P(y_k|x)=max\{P(y_1|x),P(y_2|x),..,P(y_n|x)\}$ ，则 $x$ 的类别为 $y_k$

如何获取第四步中的最大值，也就是如何计算第三步中的各个条件概率最为重要。可以采用如下做法：

1. 获取训练数据集，即分类已知的数据集
2. 统计得到在各类别下各个特征属性的条件概率估计，即： $P(a_1|y_1),P(a_2|y_1),...,P(a_m|y_1);P(a_1|y_2),P(a_2|y_2),...,P(a_m|y_2);...;P(a_1|y_n),P(a_2|y_n),...,P(a_m|y_n)$ ，其中的数据可以是离散的也可以是连续的
3. 如果各个特征属性是条件独立的，则根据贝叶斯定理有如下推导： $P(y_i|x)=\frac{P(x|y_i)P(y_i)}{P(x)}$
   对于某x来说，分母是固定的，所以只要找出分子最大的即为条件概率最大的。又因为各特征属性是条件独立的，所以有： $P(x|y_i)P(y_i)=P(a_1|y_i)P(a_2|y_i)...P(a_m|y_i)P(y_i)=P(y_i)\prod^m_{j=1}P(a_j|y_i)$

Additive smoothing

Additive smoothing，又叫Laplacian smoothing或Lidstone smoothing。

当某个类别下某个特征项划分没有出现时， $P(a_i|y_j)=0$ ，这样最后乘出来的结果会让精确度大大的降低，所以引入Additive smoothing来解决这个问题。其思想是对于这样等于0的情况，将其计数值加1，这样如果训练样本集数量充分大时，并不会对结果产生影响，并且解决了上述频率为0的尴尬局面。

Spark实现贝叶斯算法

训练数据

其中第一列代表类别，训练数据中有三种类别：0、1、2。第2-4列代表数据的三个维度，可以想象成前文中性别分类算法中的头发长度、服饰和体型这三个要素。通常来说为了保证每个要素的权值相差不大，需要取相对的数值，例如头发长度/最长的头发长度。

代码示例

结果

由于数据的人为捏造过度，可以看到此次训练的模型精度十分高为100%，即测试数据的类别和用模型预测出来的对于类别完全吻合，实际生产环境中是无法达到100%的。后面又预测了3个不在训练数据中的数据，结果和大脑判断的类别完全相同。

最后

Naive Bayes是最简单的分类算法之一。由于其简单的特性，使得训练数据的选取对于精确度的影响十分大。在我们的生产环境中，通常将训练数据进行六四分，六分用来训练数据，四分用来测试精确度。但即便如此，测试输出的精确度也往往高于实际生产环境中的精确度。不断的增加训练模型的数据量是一个较为有效的提高精度的方法，但提高的范围也十分有限。

参考资料

• MLlib - Naive Bayes
• Additive smoothing
• Naive Bayes text classification
• 算法杂货铺——分类算法之朴素贝叶斯分类(Naive Bayesian classification)