机器学习（九）：朴素贝叶斯

2019-08-14 本文已影响0人 fromeast

一、基本原理

朴素贝叶斯(naive Bayes)算法是一种基于贝叶斯定理与特征条件独立假设的分类方法，属于生成模型。其基本思想是：先验概率+数据=后验概率，即 $P(class | feature)=\frac{P(class) P(feature| class)}{P(feature)}$ 。其基本流程是：首先基于特征条件独立假设学习输入输出的联合概率分布，然后基于此模型，对给定输入 $x$ ，利用贝叶斯定理求出后验概率最大的输出 $y$ 。

假设输入空间 $\mathbb{X} \in \mathcal{R} ^{n}$ 为 $n$ 维向量集合，输出空间为类别集合 ${Y} = \left\{c_{1}, c_{2}, \cdots, c_{t} \right\}$ ，输入特征向量 $x \in \mathbb{X}$ ，输出所属类别 $y \in \mathbb{Y}$ 。 $X$ 是输入空间 $\mathbb{X}$ 上的随机变量， $Y$ 是输出空间 $\mathcal{Y}$ 上的随机变量， $P(X, Y)$ 是 $X, Y$ 的联合概率分布，训练数据集 $T=\left\{\left(x^{(1)}, y^{(1)}\right),\left(x^{(2)}, y^{(2)}\right), \cdots,\left(x^{(m)}, y^{(m)}\right)\right\}$ 由 $P(X, Y)$ 独立同分布产生。

朴素贝叶斯分类时对给定的输入 $x^{(i)}$ ，计算后验概率分布 $P\left(Y=c_{k} | X=x^{(i)}\right)$ ，将后验概率最大的类作为 $x^{(i)}$ 所属类别输出。其计算方式如下： $P\left(Y=c_{k} | X=x^{(i)}\right)=\frac{P\left(X=x^{(i)} | Y=c_{k}\right) P\left(Y=c_{k}\right)}{\sum_{k=1}^{t} P\left(X=x^{(i)} | Y=c_{k}\right) P\left(Y=c_{k}\right)}$
由于对条件概率做了条件独立性假设，则 $\begin{aligned} P\left(X=x^{(i)} | Y=c_{k}\right) =P\left(X_{1}^{(i)}=x_{1}^{(i)}, \cdots, X_{n}^{(i)}=x_{n}^{(i)} | Y=c_{k}\right) =\prod_{j=1}^{n} P\left(X_{j}^{(i)}=x_{j}^{(i)} | Y=c_{k}\right) \end{aligned}$

由上两式，有 $P\left(Y=c_{k} | X=x^{(i)}\right)=\frac{\prod_{j=1}^{n} P\left(X_{j}^{(i)}=x_{j}^{(i)} | Y=c_{k}\right)}{\sum_{k=1}^{t} P\left(Y=c_{k}\right) \prod_{j=1}^{n} P\left(X_{j}^{(i)}=x_{j}^{(i)} | Y=c_{k}\right)} P\left(Y=c_{k}\right)$

因此朴素贝叶斯算法的优化模型为 $\begin{array}{c} {\underset{c_{k}}{\arg \max } P\left(Y=c_{k} | X=x^{(i)}\right)=\underset{c_{k}}{\arg \max } \frac{\prod_{j=1}^{n} P\left(X_{j}^{(i)}=x_{j}^{(i)} | Y=c_{k}\right)}{\sum_{k=1}^{t} P\left(Y=c_{k}\right) \prod_{j=1}^{n} P\left(X_{j}^{(i)}=x_{j}^{(i)} | Y=c_{k}\right)} P\left(Y=c_{k}\right)} \\ {=\underset{c_{k}}{\arg \max } P\left(Y=c_{k}\right) \prod_{j=1}^{n} P\left(X_{j}^{(i)}=x_{j}^{(i)} | Y=c_{k}\right)}\end{array}$

因为对于每一个 $c_{k}$ ，分母 $\sum_{k=1}^{t} P\left(Y=c_{k}\right) \prod_{j=1}^{n} P\left(X_{j}^{(i)}=x_{j}^{(i)} | Y=c_{k}\right)$ 的值都是相同的。

求解朴素贝叶斯模型相当于求解一个概率值，对于样本数据集可以求出先验概率 $p\left(Y=c_{k}\right)$ ， $p\left(Y=c_{k}\right)=\frac{\sum_{i=1}^{m} I\left(y^{(i)}=c_{k}\right)}{t} \quad k=1,2, \cdots, t$
其中 $I(x)$ 为示性函数， $x$ 为真时值为1，否则为0。
条件概率为

$\begin{array}{c} {P\left(X_{j}^{(i)}=x_{j}^{(i)} | Y=c_{k}\right)=\frac{\sum_{i=1}^{m} I\left(x_{j}^{(i)}=a_{j l}, y^{(i)}=c_{k}\right)}{\sum_{i=1}^{m} I\left(y^{(i)}=c_{k}\right)}} \\ {j=1,2, \cdots, n} ~~~~ {l=1,2, \cdots, S_{j}}\end{array}$

其中 $x_{j}^{(i)}$ 代表 $i$ 个样本的第 $j$ 个特征 $x_{j}^{(i)} \in\left\{a_{j 1}, a_{j 2}, \cdots, a_{j S_{j}}\right\}$ ， $a_{j l}$ 表示第 $j$ 个特征的第 $l$ 个值。
由于极大似然估计可能会出现概率为 $0$ 的情况，而影响后验概率的计算，使分类产生偏差，于是可采用贝叶斯估计 $P_{\lambda}\left(Y=c_{k}\right)=\frac{\sum_{i=1}^{m} I\left(y^{(i)}=c_{k}\right)+\lambda}{t+t \lambda}$

$P_{\lambda}\left(X_{j}^{(i)}=x_{j}^{(i)} | Y=c_{k}\right)=\frac{\sum_{i=1}^{m} I\left(x_{j}^{(i)}=a_{j l}, y^{(i)}=c_{k}\right)+\lambda}{\sum_{i=1}^{m} I\left(y^{(i)}=c_{k}\right)+S_{j} \lambda}$

其中 $\lambda \geqslant 0$ ，当 $\lambda=1$ 时称为拉普拉斯平滑(Laplace smoothing)。

二、算法实现

以下为MultinomialNB和GaussianNB的手动实现。

多项式贝叶斯分类器适用于离散特征的分类问题，其实现过程正如原理部分所述。

import numpy as np

class MultinomialNB(object):
    def __init__(self,alpha=1.0,fit_prior=True,class_prior=None):
        self.alpha = alpha
        self.fit_prior = fit_prior
        self.class_prior = class_prior
        self.classes = None
        self.conditional_prob = None
        
    def _calculate_feature_prob(self,feature):
        values = np.unique(feature)
        total_num = float(len(feature))
        value_prob = {}
        for v in values:
            value_prob[v] = np.sum(np.equal(feature,v)+self.alpha)/(total_num+len(values)*self.alpha)
        return value_prob
    
    def fit(self,X,y):
        self.classes = np.unique(y)
        if self.class_prior == None:
            class_num = len(self.classes)
            if not self.fit_prior:
                self.class_prior = [1.0/class_num for _ in range(class_num)]
            else:
                self.class_prior = []
                sample_num = float(len(y))
                for c in self.classes:
                    c_num = np.sum(np.equal(y,c))
                    self.class_prior.append((c_num+self.alpha)/(sample_num+class_num*self.alpha))
        self.conditional_prob = {}
        for c in self.classes:
            self.conditional_prob[c] = {}
            for i in range(len(X[0])):
                feature = X[np.equal(y,c)][:,i]
                self.conditional_prob[c][i] = self._calculate_feature_prob(feature)
        return self
    
    def _get_xj_prob(self,values_prob,target_value):
        return values_prob[target_value]
    
    def _predict_single_sample(self,x):
        label = -1
        max_posterior_prob = 0
        for c_index in range(len(self.classes)):
            current_class_prior = self.class_prior[c_index]
        
        current_conditional_prob = 1.0
        feature_prob = self.conditional_prob[self.classes[c_index]]
        j = 0
        for feature_i in feature_prob.keys():
            current_conditional_prob *= self._get_xj_prob(feature_prob[feature_i],x[j])
            j += 1
        
            if current_class_prior * current_conditional_prob > max_posterior_prob:
                max_posterior_prob = current_class_prior * current_conditional_prob
                label = self.classes[c_index]
        return label
    
    def predict(self,X):
        if X.ndim == 1:
            return self._predict_single_sample(X)
        else:
            labels = []
            for i in range(X.shape[0]):
                label = self._predict_single_sample(X[i])
                labels.append(label)
            return labels

高斯贝叶斯分类器适用于连续特征的分类问题，连续属性的概率密度函数为：
$p\left(x_{i} | c\right)=\frac{1}{\sqrt{2 \pi} \sigma_{c, i}} \exp \left(-\frac{\left(x_{i}-\mu_{c, i}\right)^{2}}{2 \sigma_{c, i}^{2}}\right)$

class GaussianNB(MultinomialNB):
    def _calculate_feature_prob(self,feature):
        mu = np.mean(feature)
        sigma = np.std(feature)
        return (mu,sigma)
    
    def _prob_gaussion(self,mu,sigma,x):
        return 1.0/(sigma*np.sqrt(2*np.pi)) * np.exp(-(x-mu)**2/(2*sigma**2))
    
    def _get_xj_prob(self,mu_sigma,target_value):
        return self._prob_gaussion(mu_sigma[0],mu_sigma[1],target_value)

主函数，数据生成及预测

if __name__ == "__main__":
    X = np.array([
                      [1,1,1,1,1,2,2,2,2,2,3,3,3,3,3],
                      [4,5,5,4,4,4,5,5,6,6,6,5,5,6,6]
                              ])
    X = X.T
    y = np.array([-1,-1,1,1,-1,-1,-1,1,1,1,1,1,1,1,-1])
    
    #nb = MultinomialNB(alpha=1.0,fit_prior=True)
    nb = GaussianNB(alpha=1.0,fit_prior=True)
    nb.fit(X,y)
    print(nb.alpha)
    print(nb.class_prior)
    print(nb.classes)
    print(nb.conditional_prob)
    print(nb.predict(np.array([2,4])))

计算结果及参数如下：

1.0
[0.4117647058823529, 0.5882352941176471]
[-1  1]
{-1: {0: (1.6666666666666667, 0.7453559924999299), 1: (4.666666666666667, 0.7453559924999299)}, 
1: {0: (2.2222222222222223, 0.7856742013183862), 1: (5.333333333333333, 0.6666666666666666)}}
1

以下为sklearn包中朴素贝叶斯算法的实现。

from sklearn.naive_bayes import MultinomialNB
from sklearn import datasets
from sklearn import metrics

iris = datasets.load_iris()

mnb = MultinomialNB()
mnb.fit(iris.data,iris.target)

expected = iris.target
predicted = mnb.predict(iris.data)

print(metrics.classification_report(expected,predicted))
print(metrics.confusion_matrix(expected,predicted))

以下为分类结果及其混淆矩阵。

                precision    recall  f1-score   support

           0       1.00      1.00      1.00        50
           1       0.94      0.92      0.93        50
           2       0.92      0.94      0.93        50

   micro avg       0.95      0.95      0.95       150
   macro avg       0.95      0.95      0.95       150
weighted avg       0.95      0.95      0.95       150

[[50  0  0]
 [ 0 46  4]
 [ 0  3 47]]

三、问题探讨

判别模型与生成模型

判别模型：学习得到条件概率分布 $\mathrm{P}(\mathrm{y} | \mathrm{x})$ ，即在特征 $x$ 出现的情况下标记 $y$ 出现的概率。
生成模型：学习得到联合概率分布 $P(\mathrm{x}, \mathrm{y})$ ，即特征 $x$ 和标记 $y$ 共同出现的概率，然后求条件概率分布。

生成模型与判别模型
常见判别模型：k近邻法、感知机、决策树、逻辑回归、线性回归、最大熵模型、支持向量机(SVM)、提升方法、条件随机场（CRF）
常见生成模型：朴素贝叶斯、隐马尔可夫（em算法）、受限玻耳兹曼机（Restricted Boltzmann Machine，RBM）、自编码器（Autoencoder，AE）、深层信念网络（Deep Belief Network，DBN）、高斯混合模型（GMM）

参考资料

[1] https://github.com/yhangf/ML-NOTE
[2] 周志华著. 机器学习. 北京:清华大学出版社,2016
[3] 李航著. 统计学习方法. 北京:清华大学出版社,2012
[4] 史春奇等著. 机器学习算法背后的理论与优化. 北京:清华大学出版社,2019
[5] Peter Harrington 著. 李锐等译. 机器学习实战. 北京:人民邮电出版社,2013
[6] https://scikit-learn.org/stable/modules/naive_bayes.html

冷眼向洋看世界，热风吹雨洒江天。——毛泽东《七律·登庐山》