朴素贝叶斯算法

1. 算法推导

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

朴素贝叶斯算法的目标是根据输入的特征，对每一个分类计算其后验概率，选择后验概率最大的那个分类作为模型输出。而后验概率是根据贝叶斯准则从条件概率推导而来的，下面先对朴素贝叶斯算法的公式作一个推导：

— 每个样本包含 nnn 个特征，一共分可为 mmm 类，ckc_kck​ 表示其中的某一个类别；

— 先验概率：P(Y=ck)P(Y=c_k)P(Y=ck​) ；

— 条件概率：P(X=x∣Y=ck)=P(X(1)=x(1),...,X(n)=x(n)∣Y=ck)P(X=x|Y=c_k)=P(X^{(1)}=x^{(1)},...,X^{(n)}=x^{(n)}|Y=c_k)P(X=x∣Y=ck​)=P(X(1)=x(1),...,X(n)=x(n)∣Y=ck​)；

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

— 条件概率：P(X=x∣Y=ck)=P(X(1)=x(1),...,X(n)=x(n)∣Y=ck)=∏j=0nP(X(j)=x(j)∣Y=ck)P(X=x|Y=c_k)=P(X^{(1)}=x^{(1)},...,X^{(n)}=x^{(n)}|Y=c_k)=\prod_{j=0}^nP(X^{(j)}=x^{(j)}|Y=c_k)P(X=x∣Y=ck​)=P(X(1)=x(1),...,X(n)=x(n)∣Y=ck​)=∏j=0n​P(X(j)=x(j)∣Y=ck​)

— 后验概率：P(Y=ck∣X=x)=P(X=x∣Y=ck)P(Y=ck)∑kP(X=x∣Y=ck)P(Y=ck)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=ck​∣X=x)=∑k​P(X=x∣Y=ck​)P(Y=ck​)P(X=x∣Y=ck​)P(Y=ck​)​

— 将条件概率的公式代入到后验概率公式中，得到后验概率：P(Y=ck∣X=x)=P(Y=ck)∏j=1nP(X(j)=x(j)∣Y=ck)∑kP(Y=ck)∏j=1nP(X(j)=x(j)∣Y=ck)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)}P(Y=ck​∣X=x)=∑k​P(Y=ck​)∏j=1n​P(X(j)=x(j)∣Y=ck​)P(Y=ck​)∏j=1n​P(X(j)=x(j)∣Y=ck​)​

— 于是，朴素贝叶斯分类器的分类目标可表示为 y=argmaxckP(Y=ck∣X=x)=argmaxckP(Y=ck)∏j=1nP(X(j)=x(j)∣Y=ck)y=\mathop{argmax}\limits_{c_k}P(Y=c_k|X=x)=\mathop{argmax}\limits_{c_k}P(Y=c_k)\prod_{j=1}^{n}P(X^{(j)}=x^{(j)}|Y=c_k)y=ck​argmax​P(Y=ck​∣X=x)=ck​argmax​P(Y=ck​)∏j=1n​P(X(j)=x(j)∣Y=ck​)

2. 算法流程

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

— 对训练集计算先验概率：P(Y=ck)=∑i=1NI(yi=ck)NP(Y=c_k)=\frac{\sum_{i=1}^NI(y_i=c_k)}{N}P(Y=ck​)=N∑i=1N​I(yi​=ck​)​ （其中分母表示一共有 NNN 种类别，分子表示对于样本 iii，如果其分类 yi=cky_i=c_kyi​=ck​，则分子取值为 1，否则取值为 0）；

— 计算条件概率 P(X(j)=x(j)∣Y=ck)=∑i=1NI(Xi(j)=ajl,yi=ck)∑i=1NI(yi=ck)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)}P(X(j)=x(j)∣Y=ck​)=∑i=1N​I(yi​=ck​)∑i=1N​I(Xi(j)​=ajl​,yi​=ck​)​ （它表示类别为 ckc_kck​ 的前提下第 jjj 个特征取值为 x(j)x^{(j)}x(j) 的概率）；

— 对于给定的测试数据 x=(x(1),x(2),...,x(n))Tx=(x^{(1)},x^{(2)},...,x^{(n)})^Tx=(x(1),x(2),...,x(n))T，计算 P(Y=ck)∏i=1nP(X(j)=x(j))P(Y=c_k)\prod_{i=1}^nP(X^{(j)}=x^{(j)})P(Y=ck​)∏i=1n​P(X(j)=x(j))，其输出结果是大小为 kkk 的向量；

—y=argmaxckP(Y=ck)∏i=1nP(X(j)=x(j))y=\mathop{argmax}\limits_{c_k}P(Y=c_k)\prod_{i=1}^nP(X^{(j)}=x^{(j)})y=ck​argmax​P(Y=ck​)∏i=1n​P(X(j)=x(j)) 确定样本 xxx 的分类。

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 npdef vectorization(word_list, vocabulary):return_vector = [0] * len(vocabulary)for word in word_list:if word in vocabulary:return_vector[vocabulary.index(word)] = 1return return_vectordef 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

下面的函数是朴素贝叶斯算法的执行流程，它是参照上文第二部分中的算法流程来编排的。区别的是代码中使用了拉普拉斯平滑，这是为了防止连乘操作中出现 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_priortest_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 1else:return 0test_data = ['stupid', 'stop', 'how', 'problems']
pred_label = naive_bayes(test_data)
print('test_data = ', test_data)
print('pred_label = ', pred_label)

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

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