【统计学习方法】学习笔记——第四章：朴素贝叶斯法

朴素贝叶斯法(Naive Bayes)是基于 贝叶斯定理与 特征条件独立假设的分类方法。 对于给定的训练数据集，首先基于特征条件独立假设学习输入/输出的联合概率分布；然后基于此模型，对给定的输入$x$，利用贝叶斯定理求出后验概率最大的$y$。

1. 朴素贝叶斯的学习与分类

1.1 基本方法

设输入空间$\mathcal{X}\subseteq R^n$为n维向量的集合，输出空间为类标记集合$\mathcal{Y}=\{c_1,c_2,...,c_K\}$。输入为特征向量$x\in \mathcal{X}$，输出为类标记（class label）$y\in \mathcal{Y}$。$X$是定义在输入空间$\mathcal{X}$上的随机向量，$Y$是定义在输出空间$\mathcal{Y}$上的随机变量，$P(X,Y)$是$X$和$Y$的联合概率分布。训练数据集$$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$$，由$P(X,Y)$独立同分布产生。

朴素贝叶斯法通过训练数据集学习联合概率分布$P(X,Y)$。具体地，学习以下先验概率分布以及条件概率分布。

• 先验概率分布$$P(Y=c_k)，k=1,2,...,K$$
• 条件概率分布：$$P(X=x|Y=c_k)=P(X^{(1)}=x^{(1)},...,X^{(n)}=x^{(n)}|Y=c_k),k=1,2...,K$$

于是学习得到联合概率分布$P(X,Y)$。
条件概率分布$P(X=x|Y=c_k)$有指数级数量的参数，其估计实际是不可行的。事实上，假设$x^{(j)}$可取值有$S_j$个，$j=1,2,...,n$，$Y$的可取值有K个，那么参数个数为$K{\prod }_n^{j=1}{S}_j$。

为了简化计算，朴素贝叶斯算法做出了条件独立性假设。条件独立性假设是指用于分类的特征在类别确定的情况是条件独立的，公式如下：$$P(X=x|Y=c_k)=P(X^{(1)}=x^{(1)},...,X^{(n)}=x^{(n)}|Y=c_k)=\prod _n^{j=1}P(X^{(j)}=x^{(j)}|Y=c_k)$$
朴素贝叶斯法实际上学习到生成数据的机制，所以属于生成模型。条件独立性假设简化了计算复杂度，但有时会损失一些分类准确率。

朴素贝叶斯法分类时，对给定的输入$x$，通过学习到的模型计算后验概率分布$P(Y=c_k|X=x)$，将后验概率最大的类作为$x$的类数据。后验概率计算根据贝叶斯定理进行：$$P(Y=c_k|X=x)=\frac{P(X=x|Y=c_k)P(Y=c_k)}{{\sum }_{k}P(X=x|Y=c_k)P(Y=c_k)}$$
于是，朴素贝叶斯分类器可表示为：
$$y=f(x)=argma{x}_{c_k}\frac{P(Y=c_k){\prod }_{j}P(X^{(j)}=x^{(j)}|Y=c_k)}{{\sum }_{k}P(Y=c_k){\prod }_{j}P(X^{(j)}=x^{(j)}|Y=c_k)}$$
注意，在上式中，分母对所有的$c_k$都是相同的，所以：
$$y=f(x)=argma{x}_{c_k}P(Y=c_k)\prod _{j}P(X^{(j)}=x^{(j)}|Y=c_k)$$

1.2 后验概率最大化的含义

朴素贝叶斯法将实例分类到后验概率最大的类中，这等价于期望风险最小化。根据期望风险最小化准则就得到了后验概率最大化准则：
$$f(x)=argma{x}_{c_k}P(c_k|X=x)$$
即朴素贝叶斯法所采用的原理。

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

2.1 极大似然估计

在朴素贝叶斯法中，学习意味着估计$P(Y=c_k)$和$P(X^{(j)}=x^{(j)}|Y=c_k)$。可以应用极大似然估计法估计相应的概率。先验概率$P(Y=c_k)$的极大似然估计是$$P(Y=c_k)$$的极大似然估计是：
$$P(Y=c_k)=\frac{{\sum }_{i=1}^{N}I(y_i=c_k)}{N},k=1,2,...,K$$
设第j个特征$x^{(j)}$可能取值的集合为$a_{j1},a_{j2},...,a_{j{S}_j}$，条件概率$P(X^{(j)}=a_{jl}|Y=c_k)$的极大似然估计是：
$$P(X^j=a_{jl}|Y=c_k)=\frac{{\sum }_{i=1}^{N}I(x_i^{(j)}=a_{jl},y_i=c_k)}{{\sum }_{i=1}^{N}I(y_i=c_k)}$$
$j=1,2,...,n;l=1,2,...,S_j,k=1,2,...,K$，$x_i^{(j)}$是第i个样本的第j个特征，$a_{jl}$是第j个特征可能取得第l个值，I为指示函数。

2.2 学习与分类算法

算法：朴素贝叶斯算法（naive Bayes algorithm）
输入：训练数据$T=(x_1,y_2),(x_2,y_2),...,(x_N,y_N)$，其中$x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(n)}{)}^T$，$x_i^{(j)}$是第$i$个样本得第$j$个特征，$x_i^{(j)}\in a_{j1},a_{j2},...,a_{jS}$，$a_{jl}$是第$j$个特征可能取得第$l$个值，$j=1,2,...,n$，$l=1,2,...,S_j$，$y_i\in c_1,c_2,...,c_K$；实例$x$；
输出：实例$x$的分类：
(1)计算先验概率及条件概率：
$$P(Y=c_k)=\frac{{\sum }_{i=1}^{N}I(y_i=c_k)}{N},k=1,2,...,K$$
$$P(X^{(j)}=a_{jl}|Y=c_k)=\frac{{\sum }_{i=1}^{N}I(x_i^{(j)}=a_{jl},y_i=c_k)}{{\sum }_{i=1}^{N}I(y_i=c_k)},j=1,2,...,n;I=1,2,...,S_j;k=1,2...,K$$
(2)对于给定的实例$x=(x^{(1)},x^{(2)},...,x^{(n)}{)}^T$，计算
$$P(Y=c_k)\prod _{j=1}^{n}P(X^{(j)}=x(j)|Y=c_k),k=1,2,...,K$$
(3)确定实例x的类
$$y=argma{x}_{c_k}P(Y=c_k)\prod _{j=1}^{n}P(X^{(j)}=x^{(j)}|Y=c_k)$$

2.3 贝叶斯估计

用极大似然估计可能会出现所要估计的概率值为0的情况，这时会影响到后验概率的计算结果，使分类产生偏差。解决这一问题的方法是采用贝叶斯估计，具体地，条件概率的贝叶斯估计是：
$$P_{\lambda }(X^{(j)}=a_{jl}|Y=c_k)=\frac{{\sum }_{i=1}^{N}I(x_i^{(j)}=a_{jl},y_i=c_k)+\lambda }{{\sum }_{i=1}^{N}I(y_i=c_k)+S_j\lambda }$$
其中$\lambda \ge 0$。等价于在随机变量各个取值的频数上赋予一个正数$\lambda >0$。当$\lambda =0$时，就是极大似然估计。常取$\lambda =1$，这时称为拉普拉斯平滑（Laplace smoothing）。显然 对于任何$l=1,2,...,S_j,k=1,2...,K$，有
$$P_{\lambda }(X^{(j)}=a_{jl}|Y=c_k)>0$$
$$\sum _{l=1}^{S_j}P(X^{(j)}=a_{jl}|Y=c_k)=1$$
同样，先验概率的贝叶斯估计是：
$$P_{\lambda }(Y=c_k)=\frac{{\sum }_{i=1}^{N}I(y_i=c_k)+\lambda }{N+K\lambda }$$

3. 总结

1. 朴素贝叶斯法是典型的生成学习方法。生成方法由训练数据学习联合概率分布$P(X,Y)$，然后求得后验概率分布$P(Y|X)$，具体来说，利用训练数据学习$P(X|Y)$和$P(Y)$的估计，得到联合概率分布：
   $$P(X,Y)=P(Y)P(X|Y)$$
   概率估计方法可以是极大似然估计或者贝叶斯估计
2. 朴素贝叶斯法的基本假设是条件独立性：
   $$P(X=x|Y-=c_k)=P(X^{(1)=x^{(1)}},...,X^{(n)}=x^{(n)}|Y=c_k)=\prod _{j=1}^{n}P(X^{(j)}=x^{(j)}|Y=c_k)$$
   朴素贝叶斯法高效，但是分类的性能不一定很高。
3. 朴素贝叶斯法利用贝叶斯定理与学到的联合概率模型进行分类预测
   $$P(Y|X)=\frac{P(X,Y)}{P(X)}=\frac{P(Y)P(X|Y)}{{\sum }_{Y}P(Y)P(X|Y)}$$
   将输入x分到后验概率最大的类y。
   $$y=arg\underset{c_k}{\max }P(Y=c_k)\prod _{j=1}^{n}P(X_j=x^{(j)}|Y=c_k)$$
   后验概率最大等价于0-1损失函数时的期望风险最小化。