统计学习方法笔记之朴素贝叶斯
in 机器学习 with 2 comments

统计学习方法笔记之朴素贝叶斯

in 机器学习 with 2 comments

朴素贝叶斯是基于贝叶斯定理和特征条件独立假设的分类方法,所谓特征条件独立是指在类别已经确定的条件下,特征之间都是相互独立、互不干扰的,这也正是“朴素”一词的来由。

基本方法

假设输入空间为$\mathcal{X} \in R^n$,输出空间为类标签集合$\mathcal{Y} \in \{c_1, c_2, \cdots,c_k\}$,测试样本$x\in \mathcal{X}$。朴素贝叶斯通过学习模型得到计算后验概率分布$P(Y=c_k|X=x) $,将后验概率最大的类作为$x$的类输出。后验概率通过贝叶斯定理得到:

$$ P(Y=c_k|X=x_k) = \frac{P(X=x|Y=c_k)P(Y=c_k)}{\sum_k P(X=x|Y=c_k)P(Y=c_k)} $$

而根据条件独立假设,有:

$$ P(X=x|Y=c_k) = P(X^{(1)}=x^{(1)},\cdots,X^{(n)}=x^{(n)})=\prod^n_{j=1}P(X^{(j)}=x^{(j)}|Y=c_k ) $$

代入上式可以得到:

$$ P(Y=c_k|X=x_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 )} $$

由于分母对于所有的$c_k$都是相同的,因此朴素贝叶斯可以表示为:

$$ y = \arg \max_{c_k} P(Y=c_k)\prod_j P(X^{(j)} = x^{(j)}|Y=c_k) $$

后验概率最大的含义

假设损失函数为:

$$ L(Y,f(X)) = \left\{ \begin{align}1, Y \neq f(X) \\ 0, Y =f(X) \end{align} \right. $$

$f(X)$为决策函数,对联合分布$P(X,Y)$取期望,这时,期望风险函数为:

$$ R_{exp}(f) = E[L(Y,f(X))] $$

由此取条件期望:

$$ R_{exp}(f) = E_X\sum^K_{k=1}[L(c_k,f(X))]P(c_k|X) $$

为了使期望风险最小化,只需要对$X=x$逐个极小化,即:

$$ \begin{align} f(x)&= \arg \min_{y \in \mathcal{Y}}\sum^K_{k=1}L(c_k,y)P(c_k|X=x) \\&= \arg \min_{y \in \mathcal{Y}}\sum^K_{k=1}P(y \neq c_k|X=x) \\ &= \arg \min_{y \in \mathcal{Y}}(1 - P(y=c_k |X=x)) \\ &=\arg \max_{y \in \mathcal{Y}}P(y=c_k |X=x) \end{align} $$

这样就得到了后验概率最大化准则$\arg \max_{c_k}P(c_k |X=x) $,因此我们说后验概率最大化等价于期望风险最小化。

参数估计

朴素贝叶斯的学习意味着估计$P(Y=c_k)$和$P(X^{(j)}=x^{(j)}|Y=c_k)$。

极大似然估计

先验概率$P(Y=c_k)$的极大似然估计是:

$$ P(y=c_k) = \frac{\sum^N_{i=1}I(y_i = c_k)}{N},k=1, 2, \cdots, K $$

设第$j$个特征$x^{(j)}$可能取值的集合为$\{a_{j1}, a_{j2}, \cdots,a_{jS_j}\}$,则条件概率$P(X^{(j)}=x^{(j)}|Y=c_k)$的极大似然估计是

$$ P(X^{(j)}=a_{jl}|Y=c_k)=\frac{\sum^N_{i=1}I(x^{(j)}_i = a_{jl},y_i=c_k)}{\sum^N_{i=1}I(y_i = c_k)} \\ j=1, 2, \cdots,n;l=1,2,\cdots,S_j;k=1,2,\cdots,K $$

$x_i^{(j)}$是第$i$个样本中的第$j$个特征;$a_{jl}$是第$j$个特征可能取的第$l$个值;$I$为指示函数。

贝叶斯估计

贝叶斯估计可以解决极大似然估计可能出现要估计的概率为0的问题。

对于先验概率,在极大似然估计的基础上分子加$\lambda$;分母加$K \lambda$,$K$是类别数量;

对于条件概率,在极大似然估计的基础上分子加$\lambda$;分母加$S_j \lambda$,$S_j$为第$j$个特征可取值的数量;

上述的$\lambda \geq 0$,常取$\lambda=1$,这时称为拉普拉斯平滑。

学习算法

下面是利用极大似然估计进行朴素贝叶斯学习。

假设给定的训练集为$\{(x_1, y_1), (x_2, y_2), \cdots,(x_N, y_N) \}$,其中$x_i = (x_i^{(1)},x_i^{(2)}, \cdots, x_i^{(k)})^T$,$i=1, 2, \cdots,N$,$x_i^{(j)}$是第$i$个样本的第$j$个特征,$x^{(j)}_i \in \{a_{j1}, a_{j2}, \cdots,a_{jS_j}\}$,$a_{jl}$是第$j$个特征的第$l$个取值,$j=1, 2, \cdots,n$,$l=1,2,\cdots,S_j$,$y_i \in \{c_1, c_2, \cdots, c_K\}$。按照以下步骤进行求解:

(1)计算先验概率和条件概率:

$$ P(y=c_k) = \frac{\sum^N_{i=1}I(y_i = c_k)}{N},k=1, 2, \cdots, K \\ P(X^{(j)}=a_{jl}|Y=c_k)=\frac{\sum^N_{i=1}I(x^{(j)}_i = a_{jl},y_i=c_k)}{\sum^N_{i=1}I(y_i = c_k)} \\ j=1, 2, \cdots,n;l=1,2,\cdots,S_j;k=1,2,\cdots,K $$

(2)对于给定的测试样本$x=(x_{(1)}, x^{(2)}, \cdots, x^{(n)})^T$,计算:

$$ P(Y=c_k) \prod^m_{j=1}P(X^{(j)}=x^{(j)}|Y=c_k),k=1,2,\cdots,K $$

(3)确定测试样本$x$:

$$ y = \arg \max_{c_k} P(Y=c_k)\prod^n_{j=1}P(X^{(j)}=x^{(j)}|Y=c_k) $$

Python实现

这里我用的方法比较复杂,目的是对于复杂的数据集也可以处理,这里没有采用《机器学习实战》那本书中的代码,因为那个代码的分类是1和0,比较简单而且有局限性。因为在实现中数据结构几乎都用了字典还有不少for循环,所以处理数据量比较大的数据集可能很慢。有更简单的方法欢迎交流。

问题主要是在求条件概率上,这里并没有使用指示函数和sum函数。

  1. 求先验概率是将所有类别放在字典中,key是类别,value是此类别的概率和数量(之后会用到);
  2. 因为我们最终要求的是$\prod^n_{i=1}P(X^{(j)}=x^{(j)}|Y=c_k)$,可以将这个式子转化为$\prod\frac{P(X,Y)}{P(Y)}$的形式,进一步转化为$\prod\frac{count(X, Y)}{count(Y)}$,$count$是数量,在第一步已经求得了此类别的数量,所以接下来求$Y=c_k$的同时$X^{(j)} = x^{(j)}$的样本数量即可;
  3. 上面的特征数量存在了字典中,即{类别1: {与测试样本相同特征1: 数量, 与测试样本相同特征2: 数量, ..}, 类别2:{..}, ..};
  4. 最后返回的语句利用lambda表达式将字典中最大的value所对应的key返回;
def naive_bayes(dataset, label, test_data):
    """
    基于极大似然估计的朴素贝叶斯
    :param dataset: 包含标注的训练集[[1, "S"], [2, "M"]]
    :param label: 标注
    :param test_data: 待分类数据
    :return: 预测结果
    """
    # 样本数量
    m = len(dataset)
    # 特征数量
    n = len(dataset[0])
    # 计算先验概率
    pre_probability = {}   # 先验概率
    count_label = {}       # 不同类别的数量
    # 初始化每个key的值
    for y in label:
        pre_probability[y] = 0
        count_label[y] = 0
    # 计数
    for y in label:
        count_label[y] += 1
    for count in count_label.keys():
        pre_probability[count] = count_label[count] / m
    
    # 对测试样本来说,每个特征在训练集中与它相同的数量
    # conditional_count = {类别1: {特征1: 数量, 特征2: 数量, ..}, 类别2:{..}, ..}
    conditional_count = {}
    for y in pre_probability.keys():
        conditional_count[y] = {}
    for y in pre_probability.keys():
        # 初始化训练集中与测试集特征相同的数量
        for feature in test_data:
            conditional_count[y][feature] = 0
    # 计算数量
    for y in pre_probability.keys():
        for dimension in range(n):
            for data_index in range(m):
                if label[data_index] == y and test_data[dimension] == dataset[data_index][dimension]:
                    conditional_count[y][test_data[dimension]] += 1
    # 计算后验概率
    pos_probability = {}
    for y in label:
        prob = 1
        for count in conditional_count[y].values():
            prob *= (count / count_label[y])
        prob *= pre_probability[y]
        pos_probability[y] = prob
    print(pos_probability)
    return max(pos_probability.items(), key=lambda d: d[1])[0]

参考

李航《统计学习方法(第二版)》第四章

赞 (0)
Responses
  1. 新系统评论test

    Reply
    1. @Aengus Sun

      回复test

      Reply