朴素贝叶斯法

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

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

本文叙述朴素贝叶斯法，包括朴素贝叶斯法的学习与分类、朴素贝叶斯法的参数估计算法。

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

4.1.1 基本方法

设输入空间 $\mathcal{X} \subseteq R^n$ 为n维向量的集合，输出空间为类标记集合 $\mathcal{Y}=\{c_1,c_2,...,c_K\}$ 。输入为特征向量 $x\in \mathcal{X}$ ，输出为类标记 $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 \ (4.1)$

条件概率分布:

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

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

局限性：

条件概率分布 $P(X=x|Y=c_k)$ 有指数级数量的参数，其估计实际上是不可行的。假设 $x^{(j)}$ 可取值有 $S_j$ 个，j=1,2,…,n，Y可取值有K个，那么参数个数为 $K \prod_{j=1}^n S_j$ 。

解决方案：

设置假设条件:特征独立同分布

朴素贝叶斯法对条件概率分布做了条件独立性的假设。由于这是比较强的假设，朴素贝叶斯法因此得名。具体地，条件独立性假设是:

$\begin{aligned}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) \ (4.3) \end{aligned}$

这里的 $X^{(1)}$ 表示第1个特征；朴素贝叶斯法实际上学习到生成数据的机制，所以属于生成模型。

条件独立假设等于是说用于分类的特征在类确定的条件下都是条件独立的。这一假设使得条件概率分布的学习难度降低了，但会牺牲一定的分类准确率。

朴素贝叶斯法分类时，对给定的输入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)} \ (4.4)$

将式(4.3)代入式(4.4)，得：

$P(Y=c_k|X=x) = \frac{P(Y=c_k)\prod_{j=1}^n P(X^{(j)}=x^{(j)}|Y=c_k)}{\sum_k P(Y=c_k)\prod_{j=1}^n P(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_{j=1}^n P(X^{(j)}=x^{(j)}|Y=c_k)}{\sum_k P(Y=c_k)\prod_{j=1}^n P(X^{(j)}=x^{(j)}|Y=c_k)} \ (4.6)$

注意到，在式(4.6)中分母为归一化因子，无须理会，所以：

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

为什么将后验概率最大的类作为x的输出？因为后验概率最大化等效于期望风险最小化。

4.1.2 后验概率最大化的含义

后验概率最大化等效于期望风险最小化。

设选择0-1损失函数：

$L(Y,f(X)) = \left\{ \begin{aligned} &1,Y\ne f(X) \\ &0, Y=f(x) \end{aligned} \right .$

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

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

期望是对联合分布P(X,Y)取的。由此可得关于条件概率P(Y|X)的期望(损失函数关于条件概率的期望):

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

为了是期望风险最小化，只需对X=x逐个极小化(遍历所有的样本)，由此得到:

$\begin{aligned} f(x) &= \arg \min_{y \in \mathcal{Y}} \sum_{k=1}^K L(c_k, y)P(c_k|X=x) \\ &= \arg\min_{y \in \mathcal{Y}} \sum_{k=1}^K P(y \ne c_k|X=x) \\ &=\arg\min_{y \in \mathcal{Y}}(1-P(y=c_k|X=x)) \\&= \arg\max_{y \in \mathcal{Y}}P(y=c_k|X=x)\end{aligned}$

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

$f(x) = \arg \max_{c_k} P(y=c_k|X=x) \ (4.8)$

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

求得的f(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_{i=1}^N I(y_i=c_k)}{N} \ , k=1,2,...,K \ (4.9)$

设第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_{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 \ (4.10)$

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

4.2.2 学习与分类算法

下面给出朴素贝叶斯法的学习与分类算法:

算法4.1(朴素贝叶斯算法)

输入：训练数据 $T = \{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$ ，其中 $x_i = (x_i^{(1)},x_i^{(2)},...,x_i^{(n)})^{\top}$ ， $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,...,K\}$ ；

输出：实例x的分类

计算先验概率及条件概率
$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;l=1,2,...,S_j;k=1,2,...,K$

对于给定的实例 $x= (x^{(1)},x^{(2)},...,x^{(n)})^{\top}$ ，计算：
$P(Y=c_k)\prod_{j=1}^n P(X^{(j)}=x^{(j)}|Y=c_k) \ , k=1,2,...,K$
确定实例x的类
$y = \arg \max_{c_k} P(Y=c_k)\prod_{j=1}^n P(X^{(j)}=x^{(j)}|Y=c_k)$

def _MLE_fit(self, X, y):
    X = np.array(X)
    y = np.array(y)
    #1.先求出先验概率
    y_unique = np.unique(y)
 
    for i in y_unique:
        self.prior_logit['y='+str(i)] = np.sum(y==i)
        self.prior_prob['y='+str(i)] = np.sum(y==i)/float(len(y))
    #2.求出条件概率
    m,n = X.shape
    for i in y_unique:
        for j in range(n):
            xj_unique = np.unique(X[:,j])
            for k in xj_unique:
                self.condition_logit['y='+str(i)+',x='+str(k)] = np.sum(X[np.where(y==i),j]==k)
                self.condition_prob['y='+str(i)+',x='+str(k)] = np.sum(X[np.where(y==i),j]==k)/float(np.sum(y==i))
    print(self.prior_prob)
    print(self.condition_prob)

4.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} \ (4.11)$

式中 $\lambda \ge 0$ 。等价于在随机变量各个取值的频数上赋予一个正数 $\lambda>0$ 。当 $\lambda=0$ 时，就是极大似然估计。常取1，这是称为拉普拉斯平滑。

显然，对任何 $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_{\lambda}(X^{(j)}=a_{jl}|Y=c_k) = 1$

表明式(4.11)确为一种概率分布。同样的，先验概率贝叶斯估计是:

$P_{\lambda}(Y=c_k) = \frac{\sum_{i=1}^N I(y_1=c_k)+\lambda}{N+K\lambda} \ (4.12)$

def _BE_fit(self, X, y, alpha):
    X = np.array(X)
    y = np.array(y)
    #1.先求出先验概率
    y_unique = np.unique(y)

    for i in y_unique:
        self.prior_logit['y='+str(i)] = np.sum(y==i)
        self.prior_prob['y='+str(i)] = (np.sum(y==i)+alpha)/(float(len(y))+len(y_unique)*alpha)
    #2.求出条件概率
    m,n = X.shape
    for i in y_unique:
        for j in range(n):
            xj_unique = np.unique(X[:,j])
            for k in xj_unique:
                self.condition_logit['y='+str(i)+',x='+str(k)] = np.sum(X[np.where(y==i),j]==k)
                self.condition_prob['y='+str(i)+',x='+str(k)] = \
                (np.sum(X[np.where(y==i),j]==k)+alpha)/(float(np.sum(y==i))+len(xj_unique)*alpha)
    print(self.prior_prob)
    print(self.condition_prob)