朴素贝叶斯法
朴素贝叶斯法
朴素贝叶斯(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\)的类标记
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 10 | 11 | 12 | 13 | 14 | 15 | ||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
\(X^{(1)}\) | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 3 |
\(X^{(2)}\) | S | M | M | S | S | S | M | M | L | L | L | M | M | L | L |
\(Y\) | -1 | -1 | 1 | 1 | -1 | -1 | -1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | -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