朴素贝叶斯法

朴素贝叶斯法

朴素贝叶斯(naive bayes) 法是基于贝叶斯定理和特征条件独立假设的分类方法。对于给定的训练数据集,首先基于特征条件独立假设学习输入输出的联合概率分布,然后基于此分布,对给定的输入\(x\)利用贝叶斯定理求其后验概率最大的输出。

一、朴素贝叶斯法的学习

1.1 基本方法

设输入空间\(\chi \subseteq R^n\)为n维向量的集合,输出空间维类标记集合\(Y = \{c_1,c_2,...,c_k\}\)。输入特征向量\(x \in \chi\),输出为类标记\(y \in Y\)\(p(x,y)\)\(x,y\)的联合概率分布。训练的数据集:
\[ T = \{(x_1,y_1),(x_2,y_2),...,(x_N,y_n\}\]
\(p(x,y)\) 独立同分布产生。

要得到训练数据集的联合概率分布,先得学习以下先验概率和条件概率:
\[\begin{align}p(Y=c_k) ,k=1,2,...,K \notag \p(X=x|Y=c_k) = p(x^{(1)},x^{(2)},...,x^{(n)}|c_k) \tag{1}\end{align}\]
其中(1)的条件概率分布,不太好算,假设每个\(x^{(l)}\)\(a\)个数值可供选择,那么计算(1)式就需要考虑\(a^n\)中情况。为了方便计算,朴素贝叶斯法引入了一个很强的假设,即条件概率分布具备条件独立性。
\[\begin{align}p(X=x|Y=c_k) = p(x^{(1)},x^{(2)},...,x^{(n)}|c_k) &= p(x^{(1)}|c_k)p(x^{(2)}|c_k)...p(x^{(K)}|c_k) \notag\&=\prod_{l=1}^{K} p(x^{(l)}|c_k) \tag{2}\end{align}\]
这个假设也是朴素贝叶斯法名字的由来。这一假设使得算法变得简单,但是也会牺牲一定的分类准确度。

我们由贝叶斯定理:
\[P(Y=c_k|X=x) = \frac{P(X=x|Y=c_k)P(Y=c_k)}{\sum_kP(X=x|Y=c_k)P(Y=c_k)} \notag\]

并将(2)式代入可得:
\[P(Y=c_k|X=x) = \frac{P(Y=c_k)\prod_j P(X^{(j)}=x^{(j)}|Y=c_k)}{\sum_k P(Y=c_k) \prod_j P(X^{(j)}=x^{(j)}|Y=c_k)} \tag{3}\]
(3)式即为朴素贝叶斯的基本公式,我们取后验概率最大的类别\(c_k\)。于是朴素贝叶斯分类器可以表示为 :
\[y = f(x) = \mathop{argmax}_{c_k}\frac{P(Y=c_k)\prod_j P(X^{(j)}=x^{(j)}|Y=c_k)}{\sum_k P(Y=c_k) \prod_j P(X^{(j)}=x^{(j)}|Y=c_k)} \tag{4}\]
因为(4)中的分母对所有类别都是相同的,所以(4)式可转换为如下的式子:
\[y = f(x) = \mathop{argmax}_{c_k}\prod_j P(X^{(j)}=x^{(j)}|Y=c_k)P(Y=c_k)\tag{5}\]

1.2 后验概率最大化的含义

朴素贝叶斯法中y=f(x)取得的是后验概率最大的类,为什么呢?其实最大化后验概率就等于期望风险最小化,假设选择0-1损失函数.
\[\begin{equation}\left\{ \begin{array}{**lr**} 1, Y\not= f(x) \notag\ 0, Y = f(x) \notag \end{array}\right.\end{equation}\]
其中f(x)就是分类决策函数,这时期望风险函数就为:
\[R_{exp}(f) = E[L(Y,f(x))] \notag\]
取条件期望可得:
\[R_{exp}(f) = \sum_{k=1}^K[L(c_k,f(X))]P(c_k|X) \notag\]
我们对上式子进行转化:
\[\begin{align}R_{exp}(f) &= \mathop{argmin}_{y\in Y}\sum_{k=1}^K[L(c_k,y)]P(c_k|X=x) \notag\&= \mathop{argmin}_{y\in Y} \sum_{k=1}^KP(y\not=c_k|X=x)\notag\&= \mathop{argmin}_{y\in Y} \sum_{k=1}^K[1-P(y=c_k|X=x)] \notag\&= \mathop{argmax}_{y\in Y}P(y=c_k|X=x) \notag --最大化累加中的每一项\end{align}\]
这样使得期望风险最小化就得到了后验概率最大化准则:
\[f(x) = \mathop{argmax}_{c_k}P(c_k|X=x) \notag\]

二、朴素贝叶斯的参数估计

2.1 极大似然估计

根据(5)式我们可以得出使用朴素贝叶斯法我们需要求\(P(Y=c_k)\)\(P(X^{(j)}=x^{(j)}|Y=c_k)\)。我们可以通过极大似然估计的理论样本中得到上述两式的值:
\[P(Y=c_k) = \frac{\sum_{i=1}^{N} I(y_i=c_k)}{N} \tag{6}\]

\[P(X^{(j)} = a_{jl}|Y=c_k) = \frac{\sum_{i=1}^NI(x_i^{(j)}=a_{jl},y_i=c_k)}{\sum_{i=1}^NI(y_i=c_k)}\notag\]

\[j = 1,2,...,n;l=1,2,...,S_j;k=1,2,...,K \notag \s_j为第j个特征的取值个数 \notag\]

2.2 学习与分类算法

朴素贝叶斯算法

输入:训练数据\(T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}\),其中\(x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(j)}),x_i^{(j)}\)是第\(j\)个特征,\(x_i^{(j)} = \{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,...,c_K}\);实例\(x\)

输出:实例x的分类

(1) 计算先验概率及条件概率

\[P(Y=c_k) = \frac{\sum_{i=1}^N I(y_i = c_k)}{N} , k=1,2,...,K \notag\P(X^{(j)} = a_{jl}|Y=c_k) = \frac{\sum_{i=1}^NI(x_i^{(j)}=a_{jl},y_i=c_k)}{\sum_{i=1}^NI(y_i=c_k)} \notag\]

(2) 对于给定的实例\(x=(x^{(1)},x^{P(2)},...,x^{(n)})\),计算:
\[P(Y=c_k) \prod_j P(X^{(j)}=x^{(j)}|Y=c_k)\]

(3) 确定实例\(x\)的类:
\[y = f(x) = \mathop{argmax}_{c_k}\prod_j P(X^{(j)}=x^{(j)}|Y=c_k)P(Y=c_k)\]

2.3 贝叶斯估计

上诉的朴素贝叶斯算法中求\(P(X^{(j)}=x^{(j)}|Y=c_k) 以及 P(Y=c_k)\)采用的极大似然估计法,但此法有一个缺点,就是\(P(X^{(j)}=x^{(j)}|Y=c_k) 以及 P(Y=c_k)\)可能出现为0的情况,这样在最后求极大的式子中存在累积导致整个式子全为0,所以可以将上述的两式改为:
\[\begin{align}P(Y=c_k) &= \frac{\sum_{i=1}^NI(y_i=c_k)+\lambda}{N+K\lambda} \notag\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} \notag\end{align}\]

三、代码部分

3.1 数据

下表中\(X^{(1)},X^{(2)}\) 为特征,取值的集合为\(A_1=\{1,2,3\},A_2=\{S,M,L\}\),确定\(x=(2,S)^T\)的类标记

12345678101112131415
\(X^{(1)}\)111112222233333
\(X^{(2)}\)SMMSSSMMLLLMMLL
\(Y\)-1-111-1-1-11111111-1
import numpy as np
import pandas as pd
from collections import Counter

# 生成所需的数据
df = pd.DataFrame({
    'x1': pd.Series([1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3]),
    'x2': pd.Series(['S', 'M', 'M', 'S', 'S', 'S', 'M', 'M', 'L', 'L', 'L', 'M', 'M', 'L', 'L']),
    'y': pd.Series([-1, -1, 1, 1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1]),
})

prov = {}
x = (2, 'S')
# 使用极大似然估计计算先验概率和条件概率
c = Counter(df['y'])
prov[1] = c[1] / df['y'].shape[0]
prov[-1] = c[-1] / df['y'].shape[0]
for key in dict(prov):
    # 计算后验概率
    a1 = np.sum(np.sum(df.loc[:, ['x1', 'y']] == [x[0], key], axis=1) == 2) / c[key]
    a2 = np.sum(np.sum(df.loc[:, ['x2', 'y']] == [x[1], key], axis=1) == 2) / c[key]
    prov[key] = prov[key] * a1 * a2
ans = 0
val = 0
for key in dict(prov):
    if prov[key] > val:
        ans = key
        val = prov[key]
print(ans)

详细项目:github

相关推荐