第四章 朴素贝叶斯法

朴素贝叶斯（naive Bayes）法是基于贝叶斯定理与特征条件独立假设的分类方法。

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

4.1 朴素贝叶斯法的学习与分类

4.1.1 基本方法

设

• 输入空间$\chi \subseteq R^n$为$n$维向量的集合，输出空间为类标记集合$\mathcal{Y} = \{c_1,c_2,…,c_K\}$。

• 输入为特征向量$x \in \chi$，输出为类标记（class lable）$y \in \mathcal{Y}$。

• $X$是定义在输入空间$\chi$上的随机向量，$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\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4.1)$$

条件概率分布：

$$P(X=x|Y=c_k) = P(X^{(1)} = x^{(1)},...,X^{(n)} = x^{(n)}|Y=c_k)\ \ \ k = 1,2,...,K\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4.2)$$

于是学习到联合概率分布$P(X,Y)$。

朴素贝叶斯法对条件概率分布作了条件独立性的假设。由于这是一个较强的假设，朴素贝叶斯法也由此得名。

条件独立性假设：

$$P(X=x|Y=c_k) = P(X^{(1)} = x^{(1)},...,X^{(n)} = x^{(n)}|Y=c_k) = \prod\limits_{j=1}^{n}P(X^{(j)} = x^{(j)}|Y=c_k) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4.3)$$

朴素贝叶斯法实际上学习到生成数据的机制，所以属于生成模型。条件独立假设等于是说用于分类的特征在类确定的条件下都是条件独立的。这一假设使朴素贝叶斯法变得简单，但有时会牺牲一定的分类准确率。

朴素贝叶斯法分类时，对给定的输入$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\limits_{k}P(X=x|Y=c_k)P(Y=c_k)}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4.4)$$

将式$(4.3)$代入式$(4.4)$，有

$$P(Y=c_k|X=x) = \frac{P(Y=c_k)\prod\limits_jP(X^{(j)}=x^{(j)}|Y=c_k)}{\sum\limits_kP(Y=c_k)\prod\limits_jP(X^{(j)}=x^{(j)}|Y=c_k)}, \ \ \ k = 1,2,...,K \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4.5)$$

这就是朴素贝叶斯法分类的基本公式。

朴素贝叶斯分类器可表示为：

$$y=f(x)=arg\max_{c_k}\frac{P(Y=c_k)\prod\limits_jP(X^{(j)}=x^{(j)}|Y=c_k)}{\sum\limits_kP(Y=c_k)\prod\limits_jP(X^{(j)}=x^{(j)}|Y=c_k)}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4.6)$$

在式$(4.6)$中分母对所有$c_k$都是相同的，所以

$$y=arg\max_{c_k}{P(Y=c_k)\prod\limits_jP(X^{(j)}=x^{(j)}|Y=c_k)}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4.7)$$

4.1.2 后验概率最大化的含义

朴素贝叶斯法将实例分到后验概率最大的类中。这等价于期望风险最小化。假设选择0-1损失函数：

$$L(Y,f(X)) = \lbrace_{0,\ \ Y=f(X)}^{1,\ \ Y \neq f(X)}$$

式中$f(X)$是分类决策函数。这时，期望风险函数为

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

期望是对联合分布$P(X,Y)$取的。由此取条件期望

$$R_{exp}(f) = E_X \sum\limits_{k=1}^{K}[L(c_k,f(X))]P(c_k|X)$$

为了使期望风险最小化，只需对$X=x$逐个极小化，由此得到：

$$f(x) = arg \min\limits_{y \in \mathcal{Y}} \sum\limits_{k=1}^{K} L(c_k,y)P(c_k|X=x)$$ $$\ \ =arg \min\limits_{y \in \mathcal{Y}} \sum\limits_{k=1}^{K}P(y \neq c_k|X=x)$$ $$\ \ \ \ \ \ \ = arg \min\limits_{y \in \mathcal{Y}} (1 - P(y = c_k|X=x))$$ $$= arg \max\limits_{y \in \mathcal{Y}} P(y = c_k|X=x)$$

这样一来，根据期望风险最小化准则就得到了后验概率最大化准则：

$$f(x)=agr\max\limits_{c_k}P(c_k|X=x)$$

即朴素贝叶斯法所才用的原理。

4.2 朴素贝叶斯法的参数估计

4.2.1 极大似然估计

在朴素贝叶斯法中，学习意味着估计$P(Y=c_k)$和$P(X^{(j)}=x^{(j)}|Y=c_k)$。可以应用极大似然估计法估计相应的概率。

• 先验概率的$P(Y=c_k)$的极大似然估计是：

  $$P(Y=c_k) = \frac{\sum\limits_{i=1}^{N}I(y_i=c_k)}{N}, \ \ \ k = 1,2,...,K\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4.8)$$

• 设第$j$个特征$x^{(j)}$可能取值的集合为$\{a_{j1},a_{j2},…,a_{jS_j}\}$,条件概率$P(X^{(j)}=a_{jl}|Y=c_k)$的极大似然估计是：

  $$P(X^{(j)}=a_{jl}|Y=c_k) = \frac{\sum\limits_{i=1}^{N}I(x_i^{(j)}=a_{jl},y_i=c_k)}{\sum\limits_{i=1}^{N}I(y_i=c_k)}$$ $$\\ \ \\ \\ j=1,2,...,n;\ \ \ l=1,2,...,S_j;\ \ \ k = 1,2,...,K \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4.9)$$

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

4.2.2 学习与分类算法

算法 4.1（朴素贝叶斯算法（naive Bayes algorithm））

输入：训练数据$T = \{(x_1,y_1),(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_j} \}$，$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\limits_{i=1}^{N}I(y_i=c_k)}{N}, \ \ \ k = 1,2,...,K$$ $$P(X^{(j)}=a_{jl}|Y=c_k) = \frac{\sum\limits_{i=1}^{N}I(x_i^{(j)}=a_{jl},y_i=c_k)}{\sum\limits_{i=1}^{N}I(y_i=c_k)}\\ \ \\ \ \\ j=1,2,...,n;\ \ \ l=1,2,...,S_j;\ \ \ k = 1,2,...,K$$

​ （2）对于给定的实例$x=(x^{(1)},x^{(2)},…,x^{(n)})^T$，计算

$${P(Y=c_k)\prod\limits_{j=1}^{n}P(X^{(j)}=x^{(j)}|Y=c_k)}, \ \ \ k = 1,2,...,K$$

​ （3）确定实例$x$的类

$$y=arg\max_{c_k}{P(Y=c_k)\prod\limits_{j=1}^{n}P(X^{(j)}=x^{(j)}|Y=c_k)}$$

4.2.3 贝叶斯估计

用极大似然估计可能会出现所要估计的概率值为$0$的情况。这时会影响到后验概率的计算结果，使分类产生偏差。解决这一问题的方法是采用贝叶斯估计。

• 条件概率的贝叶斯估计是 ：

$$P_{\lambda}(X^{(j)}=a_{jl}|Y=c_k) = \frac{\sum\limits_{i=1}^{N}I(x_i^{(j)}=a_{jl},y_i=c_k) + \lambda}{\sum\limits_{i=1}^{N}I(y_i=c_k) + S_j \lambda}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4.10)$$

式中$\lambda \geq 0$。等价于在随机变量各个取值的频数上赋予一个正数$\lambda > 0$。当$\lambda = 0$时就是极大似然估计。 常取$\lambda = 1$，这时称为拉普拉斯平滑(Laplacian smoothing)。显然对任何$l = 1,2,…,S_j,\ k=1,2,…,K，$有

$$P_{\lambda}(X^{(j)}=a_{jl}|Y=c_k) > 0 \\ \sum\limits_{l=1}^{S_j}P_{\lambda}(X^{(j)}=a_{jl}|Y=c_k) = 1$$

表明式$(4.10)$确为一种概率分布。

• 先验概率的贝叶斯估计是： $$P_{\lambda}(Y=c_k) = \frac{\sum\limits_{i=1}^{N}I(y_i=c_k)\ + \ \lambda}{N\ + \ K\lambda} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4.11)$$