秦刚刚的机器学习成长之路之朴素贝叶斯法

写作背景：为了对所学知识进行一个总结，写下了秦刚刚的机器学习成长之路系列。欢迎大家的批评和指正^^

本文主要分四个部分来对朴素贝叶斯进行一个循序渐进的讲解

贝叶斯定理
特征条件独立假设
朴素贝叶斯估计法的参数估计
总结

注意：在学习与朴素贝叶斯相关的东西时，一定要时刻清楚朴素贝叶斯的前提是假设属性相互独立！！！

1. 贝叶斯定理

贝叶斯定理是一种在已知其他概率的情况下求概率的方法。

概率论与数理统计中讲过：

由
$p(x,y)=p(x|y)\cdot p(y)=p(y|x)\cdot p(x) \tag1$
可以推出：当先验概率 $p(y)$ 和条件概率 $p(x|y)$ 已知时，求后验概率 $p(y|x)$ 的公式为
$p(y|x)=\frac{p(y)\cdot p(x|y)}{p(x)} \tag2$
公式(2)就被称作贝叶斯定理。

2. 特征条件独立假设

给定训练数据集 $（X,Y）$ ，其中每个样本x都包括 $n$ 维特征，即 $x=(x_1,x_2,x_3,\cdots,x_n)$ ，类标记集合含有 $k$ 种类别，即 $y=(y_1,y_2,\cdots,y_k)$ 。

如果现在来了一个新样本 $x$ ，我们要怎么判断它的类别？

从概率的角度来看，这个问题就是：给定 $x$ ，求它属于哪个类别的概率最大。

从而问题转化为求解 $P(y_1|x),P(y_2|x),\cdots,P(y_k|x)$ 中最大的那个，即求后验概率最大的输出：
$arg {max_{y_k}}P(y_k|x) \tag3$

那 $arg {max_{y_k}}P(y_k|x)$ 怎么求解？答案就是贝叶斯定理：

$P(y_k|x) = \frac{P(y_k)P(x|y_k)}{P(x)} \tag4$

根据全概率公式，可以进一步地分解上式(4)中的分母：

$P(y_k|x) = \frac{P(y_k)P(x|y_k)}{\sum_{k}P(x|y_k)P(y_k)} \tag5$

对于式(4)/(5)，由于对所有的 $y_k$ ，分母的值都是一样的（为什么？注意到全加符号就容易理解了），所以可以忽略分母部分，所以我们只用关注分子部分。

在式(5)的分子部分中， $P(y_k)$ 是先验概率，表示训练集中类别 $y_k$ 出现的概率，可以通过简单的统计计算出来； $P(x|y_k)=P(x_1,x_2,\cdots,x_n|y_k)$ 是条件概率，表示类 $y_k$ 中出现样本 $x$ 的概率，它的参数规模是指数数量级别的，假设第 $i$ 维特征 $x_i$ 可取值的个数有 $S_i$ 个，类别取值个数为 $k$ 个，那么参数个数为： $k\prod^{n}_{i=1}S_i$ （原本需求解的参数个数）

这显然不可行！！！针对这个问题，朴素贝叶斯算法对条件概率分布作出了独立性的假设，通俗地讲就是说假设各个维度的特征 $x_1,x_2,\cdots,x_n$ 互相独立，在这个假设的前提上，条件概率可以转化为：

$P(x|y_k)=P(x_1,x_2,\cdots,x_n|y_k)=\prod^{n}_{i=1}P(x_i|y_k)\tag6$
这样，参数规模就降到 $k\sum^{n}_{i=1}S_i$ （作出特征条件独立假设后需求解的参数个数）

以上就是针对条件概率所作出的特征条件独立性假设，至此，先验概率 $P(y_k)$ 和条件概率 $P(x|y_k)$ 的求解问题就都解决了，那么我们是不是可以求解我们所要的后验概率 $P(y_k|x)$ 了？

答案是肯定的。我们继续上面关于 $P(y_k|x)$ 的推导，将公式(6)代入公式(5)得到：
$P(y_k|x) = \frac{P(y_k)\prod^{n}_{i=1}P(x_i|y_k)}{\sum_{k}P(x|y_k)P(y_k)} \tag7$

又由于对于所有的 $y_k$ ，分母都为 $P(x)$ ，所以可以省略，于是朴素贝叶斯分类器可表示为：
$f(x)=arg\ max_{y_k}P(y_k)∏^{n}_{i=1}P(x_i|y_k)\tag8$

至此，朴素贝叶斯分类器的两个基本前提–贝叶斯定理和特征条件独立假设已全部讲解完毕，同时，此时朴素贝叶斯法的大体也已经完全呈现了出来。

3. 朴素贝叶斯估计法的参数估计

3.1 极大似然估计

在朴素贝叶斯法中，学习意味着估计 $P(Y=c_k)$ 和 $P(X^{(j)}=x^{(j)}|Y=c_k)$ .可以应用极大似然估计法估计相应的概率。先验概率 $P(Y=c_k)$ 的极大似然估计是
$P(Y=c_k) = \frac{\sum^{N}_{i=1}I(y_i=c_k)}{N},k=1,2,\cdots,K\tag9$
其中 $N$ 表示训练数据集的大小， $K$ 表示类别数目。

设第 $j$ 个特征 $x^{(j)}$ 可能取值的集合为 $\{a_{j1},a_{j2},\cdots,a_{jS_j}\}$ ,条件概率 $P(X^{(j)}=a_{jl}|Y=c_k)$ 的极大似然估计是
$P(X^{(j)}=a_{jl}|Y=c_k) = \frac{\sum^{N}_{i=1}I(x_i^{(j)}=a_{jl},y_i=c_k)}{\sum^{N}_{i=1}I(y_i=c_k)}\tag{10}$

$j=1,2,\cdots,n;l=1,2,\cdots,S_j;k=1,2,\cdots,K$

式(10)中， $x_i^{(j)}$ 是第 $i$ 个样本的第 $j$ 个特征； $a_{jl}$ 是第 $j$ 个特征可能取的第 $l$ 个值； $I$ 为指示函数。

3.2 朴素贝叶斯算法及例题

下面给出朴素贝叶斯法的学习与分类算法。
算法：朴素贝叶斯算法
输入：训练数据 $T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$ ,其中 $x_i=(x_i^{(1)},x_i^{(2)},\cdots,x_i^{(n)})^T$ , $x_i^{(j)}$ 是第 $i$ 个样本的第 $j$ 个特征， $x_i^{(j)}\in\{a_{j1},a_{j2},\cdots,a_{jS_j}\}$ , $a_{jl}$ 是第 $j$ 个特征可能取的第 $l$ 个值， $j=1,2,\cdots,n;\ \ l=1,2,\cdots,S_j;\ \ y_i\in\{c_1,c_2,\cdots,c_K\}$ ；实例 $x$ ；
输出：实例 $x$ 的分类；
步骤(1)：计算先验概率及条件概率
$P(Y=c_k) = \frac{\sum^{N}_{i=1}I(y_i=c_k)}{N},k=1,2,\cdots,K$

$P(X^{(j)}=a_{jl}|Y=c_k) = \frac{\sum^{N}_{i=1}I(x_i^{(j)}=a_{jl},y_i=c_k)}{\sum^{N}_{i=1}I(y_i=c_k)}$

$j=1,2,\cdots,n;l=1,2,\cdots,S_j;k=1,2,\cdots,K$

步骤(2)：对于给定的实例 $x=(x^{(1)},x^{(2)},\cdots,x^{(n)})^T$ ，计算
$P(Y=c_k)\prod^{n}_{i=1} P(X^{(j)}=x^{(j)}|Y=c_k),k=1,2,\cdots,K$

步骤(3)：确定实例 $x$ 的类
$y=arg\ max_{c_k}P(Y=c_k)\prod^{n}_{i=1} P(X^{(j)}=x^{(j)}|Y=c_k)$

=====================================================================================
例题1
该例题来自于李航《统计学习方法》一书

3.3 贝叶斯估计及例题

用极大似然估计可能会出现索要估计的概率值为0的情况。这是会影响到后验概率的计算结果，使分类产生偏差。解决这一问题的方法是采用贝叶斯估计。具体地，条件概率的贝叶斯估计是
$P_{\lambda}(X^{(j)}=a_{jl}|Y=c_k)=\frac{\sum^{N}_{i=1}I(x_i^{(j)}=a_{jl}|y_i=c_k)+\lambda)}{\sum^{N}_{i=1}I(y_i=c_i)+S_j\lambda} \tag{11}$

式中 $\lambda\geq 0$ .等价于在随机变量各个取值的频数上赋予一个正数 $\lambda> 0$ 。当 $\lambda= 0$ 时就是极大似然估计。常取 $\lambda=1$ ，这是称为拉普拉斯平滑。显然，对任何 $l=1,2,\cdots,S_j;k=1,2,\cdots, K$ ,有：
$P_{\lambda}(X^{(j)}=a_{jl}|Y=c_k)>0$
$\sum^{S_j}_{l=1}P(X^{(j)}=a_{jl}|Y=c_k)=0 \tag{12}$

表明式(11)确为一种概率分布。同样，先验概率的贝叶斯估计为
$P_{\lambda}(Y=c_k)=\frac{\sum^{N}_{i=1}I(y_i=c_i)+\lambda}{N+K\lambda} \tag{13}$

=====================================================================================
例题2
该例题来自于李航《统计学习方法》一书

附加：如果还想要通过例题深入朴素贝叶斯法，可以直接百度一下“检验SNS在社区中的不真实账号”例子。

4. 总结

至此，我已经将朴素贝叶斯法的主要内容讲解完毕了，下面这段话是我结合自身理解以及总结收集的资料对朴素贝叶斯法所作的一个总结，分别阐述一下该方法的优缺点。

优点
1.有稳定的分类效率
2.适合增量式训练（对小规模数据表现很好，也能处理多分类任务）
3.算法简单，对确实数据不敏感，常用于文本分类

缺点
1.朴素贝叶斯假设属性之间相互独立（即特性条件独立假设），实际应用中这点往往不成立
2.需要知道先验概率，而此取决于假设模型（例如：高斯模型，多项式模型，伯努利模型等）
3.存在一定的错误率（通过先验和数据决定后验概率，从而决定分类）
4.对输入的表达形式很敏感