朴素贝叶斯法

《统计学习方法》笔记 第4章

Posted by Cheereus on January 18, 2020

第4章 朴素贝叶斯法

朴素贝叶斯(naive Bayes)法是基于贝叶斯定理与特征条件独立假设的分类方法。对于给定的数据集,首先基于特征条件独立假设学习输入输出的联合概率分布;然后基于此模型,对给定的输入 $x$,利用贝叶斯定理求出后验概率最大的输出 $y$。朴素贝叶斯法实现简单,学习与预测的效率都很高,是一种常用的方法。

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

4.1.1 基本方法

设输入空间 $\mathcal{X}\subseteq R^n$ 为 $n$ 维向量的集合,输出空间为类标记集合 $\mathcal{Y} = \{c_1,c_2,\cdots,c_K\}$。输入为特征向量 $x\in\mathcal{X}$,输出为类标记(class label) $y\in\mathcal{Y}$。$X$ 是定义在输入空间 $\mathcal{X}$ 上的随机变量,$Y$ 是定义在输出空间 $Y$ 上的随机变量。$P(X,Y)$ 是 $X$ 和 $Y$ 的联合概率分布。训练数据集:

\[T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}\]

由 $P(X,Y)$ 独立同分布产生。

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

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

条件概率分布:

\[P(X=x \vert Y=c_k)=P(X^{(1)}=x^{(1)},\cdots,X^{(n)}=x^{(n)} \vert Y=c_k),k=1,2,\cdots,K\]

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

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

\[P(X=x \vert Y=c_k)=P(X^{(1)}=x^{(1)},\cdots,X^{(n)}=x^{(n)} \vert Y=c_k) \\ =\prod^n_{j=1}P(X^{(j)}=x^{(j)} \vert Y=c_k)\]

条件独立性假设等于是说用于分类的特征在类确定的条件下都是条件独立的。这一假设使朴素贝叶斯法变得简单,但有时会牺牲一定的分类准确率。

朴素贝叶斯法分类时,对给定的输入 $x$,通过学习到的模型计算后验概率分布 $P(Y=c_k\vert X=x)$,将后验概率最大的类作为 $x$ 的类输出。后验概率计算根据贝叶斯定理进行:

\[P(Y=c_k\vert X=x)=\frac{P(X=x \vert Y=c_k)P(Y=c_k)}{\displaystyle\sum_k P(X=x \vert Y=c_k)P(Y=c_k)}\]

根据条件独立性假设有:

\[P(Y=c_k\vert X=x)=\frac{P(Y=c_k) \displaystyle\prod_j P(X^{(j)}=x^{(j)} \vert Y=c_k)}{\displaystyle\sum_k{P(Y=c_k) \displaystyle\prod_j P(X^{(j)}=x^{(j)} \vert Y=c_k)}}\]

这是朴素贝叶斯法分类的基本公式。于是,朴素贝叶斯分类器可以表示为:

\[y=f(x)=\arg\underset{c_k}{\max} \frac{P(Y=c_k) \displaystyle\prod_j P(X^{(j)}=x^{(j)} \vert Y=c_k)}{\displaystyle\sum_k P(Y=c_k) \displaystyle\prod_j P(X^{(j)}=x^{(j)} \vert Y=c_k)}\]

注意到,此式中分母对所有的 $c_k$ 都是相同的,所以有:

\[y=f(x)=\arg\underset{c_k}{\max}{P(Y=c_k) \displaystyle\prod_j P(X^{(j)}=x^{(j)} \vert Y=c_k)}\]

4.1.2 后验概率最大化的含义

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

\[L(Y,f(X))=\begin{cases}1, Y\neq f(X)\\0,Y=f(X)\end{cases}\]

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

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

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

\[R_{exp}(f)=E_X\sum^K_{k=1}[L(c_k,f(x))]P(c_k \vert X)\]

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

\[f(x)=\arg\underset{y\in\mathcal Y}{\min} \sum^K_{k=1}L(c_k,y)P(c_k \vert X=x) \\ =\arg\underset{y\in\mathcal Y}{\min} \sum^K_{k=1}P(y \neq c_k \vert X=x) \\ =\arg\underset{y\in\mathcal Y}{\min} (1-P(y = c_k \vert X=x)) \\ =\arg\underset{y\in\mathcal Y}{\max} P(y = c_k \vert X=x)\]

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

\[f(x)=\arg\underset{c_k}{\max} P(c_k \vert X=x)\]

即朴素贝叶斯法所采取的原理。

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

4.2.1 极大似然估计

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

\[P(Y=c_k)=\frac{\displaystyle\sum^N_{i=1}I(y_i=c_k)}{N},k=1,2,\cdots,K\]

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

\[P(X^{(j)} \vert Y=c_K)=\frac{\displaystyle\sum^N_{i=1}I(x^{(j)}_i=a_{jl},y=c_k)}{\displaystyle\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\]

式中,$x^{(j)}i$ 是第 $i$ 个样本的第 $j$ 个特征;$a{jl}$ 是第 $j$ 个特征可能取得第 $l$ 个值;$I$ 为指示函数。

4.2.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{\displaystyle\sum^N_{i=1}I(y_i=c_k)}{N},k=1,2,\cdots,K\] \[P(X^{(j)}=a_{jl} \vert Y=c_k)=\frac{\displaystyle\sum_{i=1}^N I(x^{(j)}_i=a_{jl},y_i=c_k)}{\displaystyle\sum_{i=1}^N 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_{j=1}^n P(X^{(j)}=x^{(j)} \vert Y=c_k),k=1,2,\cdots,K\]

(3) 确定实例 $x$ 的类

\[y=\arg\underset{c_k}{\max}\ P(Y=c_k) \prod_{j=1}^n P(X^{(j)}=x^{(j)} \vert Y=c_k)\]

4.2.3 贝叶斯估计

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

具体地,条件概率的贝叶斯估计是:

\[P_\lambda(X^{(j)}=a_{jl} \vert Y=c_k)=\frac{\displaystyle\sum_{j=1}^N I(x^{(j)}_i=a_{lj},y_i=c_k)+\lambda}{\displaystyle\sum_{j=1}^N I(y_i=c_k)+S_j \lambda}\]

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

\[P_\lambda(X^{(j)}=a_{jl} \vert Y=c_k) > 0\] \[\sum_{l=1}^{S_j} I(x^{(j)}_i=a_{lj},y_i=c_k)=1\]

同样,先验概率的贝叶斯估计是:

\[P_\lambda(Y=c_k)=\frac{\displaystyle\sum_{i=1}^N I(y_i=c_k)+\lambda}{N+K\lambda}\]

第4章完结


如果对您有帮助,欢迎赞助一杯咖啡!