朴素贝叶斯

1 简介

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

输入空间 $\mathcal{X} \subseteq \mathbf{R}^{n}$ 为n维向量的集合。

输出空间 $\mathcal{Y} = \left\{c_{1}, c_{2}, \cdots, c_{K}\right\}$

输入特征向量 $x$，输出类标记 $y$

随机向量$X$是定义在输入空间 $\mathcal{X}$，$Y$是定义在输出空间 $\mathcal{Y}$ 的随机变量。

训练数据集 $T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\}$ 由$P(X,Y)$ 独立同分布产生。

1.1 学习

朴素贝叶斯法先学习先验概率分布及条件概率分布。

先验概率分布：

$P(Y = c_k), k=1,2 \cdots K$

条件概率分布：它有指数级数量的参数，基于条件独立性假设

$P\left(X=x | Y=c_{k}\right)=P\left(X^{(1)}=x^{(1)}, \cdots, X^{(n)}=x^{(n)} | Y=c_{k}\right), \quad k=1,2, \cdots, K$ $=\prod_{j=1}^{n} P\left(X^{(j)}=x^{(j)} | Y=c_{k}\right)$

条件独立假设：用于分类的特征在类确定的条件下，都是属于条件独立的

1.2 预测

对给定的输入$x$，通过学习到的模型计算后验概率，最大的类作为预测结果。

后验概率计算根据的是贝叶斯定理：

$P\left(Y=c_{k} | X=x\right)=\frac{P\left(X=x | Y=c_{k}\right) P\left(Y=c_{k}\right)}{\sum_{k} P\left(X=x | Y=c_{k}\right) P\left(Y=c_{k}\right)}$

将前面学习到的代入得：

$P\left(Y=c_{k} | X=x\right)=\frac{P\left(Y=c_{k}\right) \prod_{j}^n P\left(X^{(j)}=x^{(j)} | Y=c_{k}\right)}{\sum_{k} P\left(Y=c_{k}\right) \prod_{j}^n P\left(X^{(j)}=x^{(j)} | Y=c_{k}\right)}, \quad k=1,2, \cdots, K$

！！！因此朴素贝叶斯分类器就是这样子了：

$y = f(x)=argmin_{c_k} \frac{P\left(Y=c_{k}\right) \prod_{j}^n P\left(X^{(j)}=x^{(j)} | Y=c_{k}\right)}{\sum_{k} P\left(Y=c_{k}\right) \prod_{j}^n P\left(X^{(j)}=x^{(j)} | Y=c_{k}\right)}, \quad k=1,2, \cdots, K$

1.3 后验概率最大化的含义

将实例分到后验概率最大的类中，等价于期望风险最小化。

假设损失函数：

$L(Y, f(X))=\left\{\begin{array}{ll}{1,} & {Y \neq f(X)} \\ {0,} & {Y=f(X)}\end{array}\right.$

期望风险函数:

$R_{\mathrm{exp}}(f)=E[L(Y, f(X))]$

取条件期望

$R_{\exp }(f)=E_{X} \sum_{k=1}^{K}\left[L\left(c_{k}, f(X)\right)\right] P\left(c_{k} | X\right)$

为了使得期望风险最小化，需要对$X = x$ 逐个极小化:

$f(x)=\arg \min _{y \in \mathcal{Y}} \sum_{k=1}^{K} L\left(c_{k}, y\right) P\left(c_{k} | X=x\right)$ $= \arg \min _{y \in \mathcal{Y}} \sum_{k=1}^{K} P\left(y \neq c_{k} | X=x\right)$ $= \arg \max _{y \in \mathcal{Y}} P\left(y=c_{k} | X=x\right)$

2 极大似然估计

学习即估计先验概率分布与条件概率分布：

$P\left(Y=c_{k}\right)=\frac{\sum_{i=1}^{N} I\left(y_{i}=c_{k}\right)}{N}, \quad k=1,2, \cdots, K$

设第$j$个特征$x^{(j)}$的可能取值的集合为 $\left\{a_{j 1}, a_{j 2}, \cdots, a_{j S_{j}}\right\}$，条件概率 $P\left(X^{(j)}=a_{j l} | Y = c_k )\right.$ 的极大似然估计是：

$P\left(X^{(j)}=a_{j l} | Y=c_{k}\right)=\frac{\sum_{i=1}^{N} I\left(x_{i}^{(j)}=a_{j l}, y_{i}=c_{k}\right)}{\sum_{i=1}^{N} I\left(y_{i}=c_{k}\right)}$ $j=1,2, \cdots, n ; \quad l=1,2, \cdots, S_{j} ; \quad k=1,2, \cdots, K$

3 算法过程

(1) 计算先验概率和条件概率（见2，极大似然估计部分）

(2) 对于给定实例 $x=\left(x^{(1)}, x^{(2)}, \cdots, x^{(n)}\right)^{\mathrm{T}}$计算，取最大值