贝叶斯分类器

---

贝叶斯分类是一种分类算法的总称，这种算法的均以贝叶斯定理为基础。

贝叶斯分类器的分类原理是通过某对象的先验概率，利用贝叶斯公司计算出其后验概率，即该对象属于某一类的概率。

主要的特点

• 属性可以离散、也可以是连续
• 数学基础扎实，分类效率稳定
• 对缺失和噪声数据不敏感
• 属性如果不相关，分类效果很好，如果相关，则不低于决策树。

贝叶斯定理

设$S$为试验$E$的样本空间。$B_1,B_2\cdots ,B_n$为$E$的一组事件，若

• $B_i\bigcap B_j=\varnothing ,i̸=j,i,j=1,2,\cdots ,n$
• $B_1\bigcup B_2\cdots \bigcup B_n=S$

则称$B_1,B_2,\cdots ,B_n$为样本空间$S$的一个划分。如果$B_1,B_2,\cdots ,B_n$为样本的一个划分，则对于每次试验，事件中有且仅有一个事件发生。

全概率公式：设试验$E$的样本空间为$S$，A为E的事件，$B_1,B_2\cdots ,B_n$为样本空间$S$的一个划分，且$P(B_i)\ge 0,i=1,2,3\cdots ,n$
$$P(A)=P(A|B_1)P(B_1)+\cdots +P(A|B_n)P(B_n)=\sum _{j=1}^{n}P(A|B_j)P(B_j)$$
贝叶斯定理：设试验$E$的样本空间维$S$，A为E的事件，$B_1,B_2\cdots ,B_n$为样本空间S的一个划分，且$P(A)>0,P(B_i)\ge 0,i=1,2\cdots n$，则有
$$P(B_i|A)=\frac{P(A|B_i)P(B_i)}{\sum _{i=1}^{n}P(A|B_i)P(B_i)}$$

朴素贝叶斯法

设样本$\vec{x}=(x^{(1)},x^{(2)},\cdots ,x^{(n)}{)}^T\in \mathcal{X}\subseteq {\mathbb{R}}^n$，设标记y∈Y={c1,c2,⋯ ,ck}y\in \mathcal{Y}=\{c_1,c_2,\cdots,c_k\}y∈Y={c1​,c2​,⋯,ck​}。令$X$为$\mathcal{X}$上的随机向量，Y为$\mathcal{Y}$ 上的随机向量。P(X,Y)为X和Y的联合概率分布。假定训练数据集T={(x1⃗,y1),(x2⃗,y2),⋯ ,(xn⃗,yn)}T=\{(\vec{x_1},y_1),(\vec{x_2},y_2),\cdots,(\vec{x_n},y_n)\}T={(x1​ ​,y1​),(x2​ ​,y2​),⋯,(xn​ ​,yn​)}由P(X,Y)独立同分布。那么朴素贝叶斯可从训练数据集中学习联合概率分布P(X,Y)。

• 先验概率分布： $P(Y=c_k),k=1,2,\cdots ,K$
• 条件概率分布：$P(X=\vec{x}|Y=c_k),k=1,2,\cdots ,K$

朴素贝叶斯法假设：在分类确定的条件下，用于分类的特征是条件独立的。即
$$\begin{array}{rl}P(X=\vec{x}|Y=c_k)& =P(X^{(1)}=x^{(1)},X^{(2)}=x^{(2)},\cdots ,X^{(n)}=x^{(n)}|Y=c_k)\\ & =\prod _{i=1}^{n}P(X^{(i)}=x^{(i)}|Y=c_k),k=1,2,\cdots ,K\end{array}$$
根据贝叶斯定理
$$P(Y=c_k|X=\vec{x})=\frac{P(X=\vec{x}|Y=c_k)P(Y=c_k)}{\sum _{i=1}^{K}P(X=\vec{x}|Y=c_i)P(Y=c_i)}$$
考虑分类特征的条件独立假设有
$$P(Y=c_k|X=\vec{x})=\frac{P(Y=c_k)\prod _{i=1}^{n}P(X^{(i)}=x^{(i)}|Y=c_k)}{\sum _{i=1}^{K}P(X=\vec{x}|Y=c_i)P(Y=c_i)},k=1,2\cdots ,K$$
由于朴素贝叶斯分类器表示为：
$$y=f(\vec{x})=\arg \underset{c_k}{\max }\frac{P(Y=c_k)\prod _{i=1}^{n}P(X^{(i)}=x^{(i)}|Y=c_k)}{\sum _{i=1}^{K}P(X=\vec{x}|Y=c_i)P(Y=c_i)}$$
由于对所有的$c_k,k=1,2,\cdots ,K$，上式的分母都相同，因此上式可以重写为
$$y=f(\vec{x})=\arg \underset{c_k}{\max }P(Y=c_k)\prod _{i=1}^{n}P(X^{(i)}=x^{(i)}|Y=c_k)$$

朴素贝叶斯法的学习

在朴素贝叶斯法中，要学习的参数就是以下两种

• 先验概率 $P(Y=c_k)$
• 条件概率 $P(X^{(j)}=x^{(j)}|Y=c_k)$

通常采用极大似然估计这两种概率

• 先验概率$P(Y=c_k)$的极大似然估计为
  $$P(Y=c_k)=\frac{1}{N}\sum _{i=1}^{N}I(y_i=c_k),k=1,2,\cdots ,K$$

• 条件概率$P(X^{(j)}=a_{jl}|Y=c_k)$的极大似然估计为
  $$\begin{gathered} 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,\cdots ,n \\ l=1,2,\cdots ,s_j \\ k=1,2,\cdots ,K \end{gathered}$$
  其中$a_{j1},a_{j2}\cdots ,a_{j{s}_j}$为第j个特征$x^{(j)}$可能的取值。

朴素贝叶斯算法

输入

训练集T={(x⃗1,y1),(x⃗2,y2),⋯ ,(x⃗N,yN)}T=\{(\vec x_1,y_1),(\vec x_2,y_2),\cdots,(\vec x_N,y_N)\}T={(x 1​,y1​),(x 2​,y2​),⋯,(x N​,yN​)}，${\vec{x}}_i=(x_i^{(1)},x_i^{(2)},\cdots ,x_i^{(n)}{)}^T$，$x_i^{(j)}$为第i个样本第j个特征，其中xi(j)∈{aj1,aj2,⋯ ,ajsj}x^{(j)}_i \in \{a_{j1},a_{j2},\cdots,a_{js_j}\}xi(j)​∈{aj1​,aj2​,⋯,ajsj​​}，$a_{jl}$为j个特征可能取得的第l个值，j=1,2,⋯ ,n,l=1,2,⋯ ,sk,yi∈{c1,c2,⋯ ,ck}j=1,2,\cdots,n,l=1,2,\cdots,s_k,y_i\in\{c_1,c_2,\cdots,c_k\}j=1,2,⋯,n,l=1,2,⋯,sk​,yi​∈{c1​,c2​,⋯,ck​}

实例$\vec{x}$

输出

实例$\vec{x}$ 的分类

算法步骤

• 计算先验概率的估计值以及条件概率的估计值
  $$\begin{gathered} P(Y=c_k)=\frac{1}{N}\sum _{i=1}^{N}I(y_i=c_k),k=1,2,\cdots ,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,\cdots ,n \\ l=1,2,\cdots ,s_j \\ k=1,2,\cdots ,K \end{gathered}$$

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

• 计算并返回实例$\vec{x}$的分类$y$
  $$y=\arg \underset{c_k}{\max }P(Y=c_k)\prod _{i=1}^{n}P(X^{(i)}=x^{(i)}|Y=c_k)$$

贝叶斯估计

设第$j$个特征$x^{(j)}$可能的取值为$a_{j1},a_{j2},\cdots ,a_{j{s}_j}$，则条件概率$P(X^{(j)}=a_{jl}|Y=c_k)$的极大似然估计为
$$\begin{gathered} 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,\cdots ,n \\ l=1,2,\cdots ,s_j \\ k=1,2,\cdots ,K \end{gathered}$$
用极大似然估计可能会出现分母为0的情况，因此可以采用贝叶斯估计（最大后验估计）
$$P(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 }$$
它满足概率分布函数的条件
$$\begin{gathered} P_{\lambda }(X^{(j)}=a_{jl}|Y=c_k)>0,l=1,2,\cdots ,s_j,k=1,2,\cdots ,K \\ \sum _{l=1}^{s_j}{P}_{\lambda }(X^{(j)}=a_{jl}|Y=c_k)=1 \end{gathered}$$
此时$P(Y=c_k)$的贝叶斯估计调整为：
$$P_{\lambda }(Y=c_k)=\frac{\sum _{i=1}^{N}I(y_i=c_k)+\lambda }{N+\lambda }$$

• 当$\lambda =0$时，为极大似然估计
• 当$\lambda =1$时，为拉普拉斯平滑