【AI】Python 实现朴素贝叶斯算法

朴素贝叶斯算法

1. 算法推导

朴素贝叶斯（Naive Bayes）算法是基于贝叶斯定理与特征条件独立假设的分类方法，其特点是结合先验概率和后验概率，既避免了只使用先验概率的主观偏见，也避免了单独使用样本信息的过拟合现象。该算法在数据集较大的情况下表现出较高的准确率，同时算法本身也比较简单。

朴素贝叶斯算法的目标是根据输入的特征，对每一个分类计算其后验概率，选择后验概率最大的那个分类作为模型输出。而后验概率是根据贝叶斯准则从条件概率推导而来的，假定每个样本包含 $n$ 个特征，一共分可为 $m$ 类，$c_k$ 表示其中的某一个类别，下面是对朴素贝叶斯算法的公式推导：

① 先验概率：
$$P(Y=c_k)$$

② 条件概率：
$$P(X=x|Y=c_k)=P(X^{(1)}=x^{(1)},...,X^{(n)}=x^{(n)}|Y=c_k)$$

设 $x^{(j)}$ 平均有 $S$ 种取值方法，假设各特征直接相互不独立，则单个样本的 $n$ 个特征平均有 $S^n$ 种参数，这个范围太大了；实际情况下，训练集往往并没有这么大范围的参数，数据的各特征之间往往也具有一定独立性。因此，可以大胆地假设单个样本的 $n$ 个特征之间是相互独立的。这样，条件概率的表达式转化为：

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

③ 后验概率：
$$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)}$$

将条件概率的公式代入到后验概率公式中，后验概率的表达式转化为：
$$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)}$$

④ 于是，朴素贝叶斯分类器的优化目标可表示为
$$y=\underset{c_k}{\mathrm{argmax}}P(Y=c_k|X=x)=\underset{c_k}{\mathrm{argmax}}P(Y=c_k)\prod _{j=1}^{n}P(X^{(j)}=x^{(j)}|Y=c_k)$$

2. 算法流程

以上我们推导出了朴素贝叶斯算法的计算目标，下面通过公式给出算法的运行流程：

① 计算先验概率（其中分母表示一共有 $N$ 种类别，分子表示对于样本 $i$，如果其分类 $y_i=c_k$，则分子取值为 1，否则取值为 0）：

$$P(Y=c_k)=\frac{{\sum }_{i=1}^{N}I(y_i=c_k)}{N}$$

② 计算条件概率（表示类别为 $c_k$ 的前提下第 $j$ 个特征取值为 $x^{(j)}$ 的概率）：

$$P(X^{(j)}=x^{(j)}|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)}$$

④ 对于给定的样本 $x=(x^{(1)},x^{(2)},...,x^{(n)}{)}^T$，计算一个大小为 $k$ 的向量：：

$$P(Y=c_k)\prod _{i=1}^{n}P(X^{(j)}=x^{(j)})$$

⑤ 在这个大小为 $k$ 的样本中取 $argmax$，确定样本 $x$ 的分类

$$y=\underset{c_k}{\mathrm{argmax}}P(Y=c_k)\prod _{i=1}^{n}P(X^{(j)}=x^{(j)})$$

3. 算法举例

以在线社区留言为例。为了不影响社区的发展，我们要屏蔽侮辱性的言论，所以要构建一个快速过滤器，如果某条留言使用了负面或者侮辱性的语言，那么就将该留言标志为内容不当。过滤这类内容是一个很常见的需求。对此问题建立两个类型：侮辱类和非侮辱类，使用 1 和 0 分别表示。

我们把文本看成单词向量或者词条向量，也就是说将句子转换为向量。考虑出现所有文档中的单词，再决定将哪些单词纳入词汇表或者说所要的词汇集合，然后必须要将每一篇文档转换为词汇表上的向量。

下面的函数给定了一个简单的训练数据集，并把它向量化以方便算法处理。例如，如果训练数据有两个样本，为 [[‘a’, ‘c’, ‘g’], [‘a’, ‘b’, ‘c’. ‘m’]]，则词汇表为 [‘a’, ‘b’, ‘c’, ‘g’, ‘m’]，样本中含有对应词汇的位置设为 1，否则设为 0。因此，两个样本可以向量化为：[[1, 0, 1, 1, 0], [1, 1, 1, 1, 0]]，这样，每个样本都有 5 个特征，后续处理时可以统一标准。

import numpy as np


def vectorization(word_list, vocabulary):
    return_vector = [0] * len(vocabulary)
    for word in word_list:
        if word in vocabulary:
            return_vector[vocabulary.index(word)] = 1
    return return_vector


def load_training_data():
    training_data = [['my', 'dog', 'has', 'flea', 'problems', 'help', 'please'],
                     ['maybe', 'not', 'take', 'him', 'to', 'dog', 'park', 'stupid'],
                     ['my', 'dalmation', 'is', 'so', 'cute', 'I', 'love', 'him'],
                     ['stop', 'posting', 'stupid', 'worthless', 'garbage'],
                     ['mr', 'licks', 'ate', 'my', 'steak', 'how', 'to', 'stop', 'him'],
                     ['quit', 'buying', 'worthless', 'dog', 'food', 'stupid']]
    training_labels = [0,1,0,1,0,1]
    
    # 构建词汇表
    vocabulary = set()
    for item in training_data:
        vocabulary = vocabulary | set(item)
    vocabulary = list(vocabulary)
    
    # 将训练数据向量化
    training_mat = []
    for item in training_data:
        training_mat.append(vectorization(item, vocabulary))
    
    return training_mat, training_labels
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

下面的函数是朴素贝叶斯算法的执行流程，它是参照上文第二部分中的算法流程来编排的。区别的是代码中使用了拉普拉斯平滑，这是为了防止连乘操作中出现 0 而使整个表达式为 0，这显然是不合理的。

def naive_bayes(test_data):
    # 计算先验概率
    training_mat, training_labels = load_training_data()
    feature_size = len(training_mat[0])
    training_size = len(training_mat)
    p1_prior = (sum(training_labels) + 1) / (float(training_size) + 2)
    p0_prior = 1 - p1_prior
    # 计算条件概率
    feature_cnt1 = np.zeros(feature_size)
    feature_cnt0 = np.zeros(feature_size)
    for i in range(training_size):
        if training_labels[i] == 1:
            feature_cnt1 += training_mat[i]
        else:
            feature_cnt0 += training_mat[i]
    p1_condition = (feature_cnt1 + 1) / (feature_cnt1.sum() + feature_size)
    p0_condition = (feature_cnt0 + 1) / (feature_cnt0.sum() + feature_size)
    # 计算目标函数
    p1_pred, p0_pred = p1_prior, p0_prior
    test_data = vectorization(test_data, vocabulary)
    for i in range(feature_size):
        if test_data[i] == 1:
            p1_pred *= p1_condition[i]
        else:
            p0_pred *= p0_condition[i]
    if p1_pred > p0_pred:
        return 1
    else:
        return 0
    

test_data = ['stupid', 'stop', 'how', 'problems']
pred_label = naive_bayes(test_data)
print('test_data = ', test_data)
print('pred_label = ', pred_label)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

运行上面给出的代码，执行结果为：

test_data =  ['stupid', 'stop', 'how', 'problems']
pred_label =  1
1
2