朴素贝叶斯法(NaiveBayes)

2019-02-06 本文已影响19人霞客环肥

naiveBayes

朴素贝叶斯法(Naive Bayes)

朴素贝叶斯法是基于贝叶斯定力和特征条件独立假设的分类方法。

朴素贝叶斯法实现简单，学习与预测的效率都很高，是一种常用的手法。

1 朴素贝叶斯法的学习与分类

输入空间 $X \subseteq R^n$ 为n维向量的集合。

输出空间 $Y = \{ c_1, c_2,...,c_k\}$

训练集:

$T = \{ (x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$

由 $P(X,Y)$ 独立同分布产生

在朴素贝叶斯法中，需要记住2个重要概念，先验概率和条件概率。

先验概率，即 $P(Y=c_k), k=1,2,..,K$
条件概率，即 $P(X=x|Y=c_k)=P(X^{(1)}=x^{(1)},X^{(2)}=x^{(2)},...,X^{(n)}=x^{(n)}|Y=c_k),k=1,2,..,K$

其中条件概率分布 $P(X=x|Y=c_k)$ 有指数级数量的参数，其估计实际是不可行的。For $x^{(j)}$ 的可能取值共有 $S_j$ 个， $j = 1,2,...,n$ ， $Y$ 的可能值有 $K$ 个，那么参数的个数是

$K\prod^n_{j=1} S_j$

这里提出重要假设 条件独立性假设，这也是朴素贝叶斯法的名字的来源。此时，

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

我们想要求得的是后验概率 $P(Y=c_k|X=x)$

即已知新的实例 $x$ 时， $Y$ 是各个类的概率。取最大可能性的类为 $x$ 的类。

$P(Y=c_k|X=x)=\frac{P(Y=c_k,X=x)}{P(X=x)}$ $=\frac{P(X=x|Y=c_k)P(Y=c_k)}{\sum_kP(X=x,Y=c_k)}$ $=\frac{P(X=x|Y=c_k)P(Y=c_k)}{\sum_kP(X=x|Y=c_k)P(Y=c_k)}$

到此处为贝叶斯定理，将条件概率代入此式，

$=\frac {P(Y=c_k)\prod^n_{j=1} P(X^{(j)}=x^{(j)}|Y=c_k)}{\sum_k P(Y=c_k)\prod^n_{j=1} P(X^{(j)}=x^{(j)}|Y=c_k) }$

这是朴素贝叶斯法分类的基本公式。则朴素贝叶斯分类器可表示为

$y=f(x)=\underset{c_k}{argmax}\frac {P(Y=c_k)\prod^n_{j=1} P(X^{(j)}=x^{(j)}|Y=c_k)}{\sum_k P(Y=c_k)\prod^n_{j=1} P(X^{(j)}=x^{(j)}|Y=c_k) }$

分母对所有 $c_k$ 都相同，所以

$y=f(x)=\underset{c_k}{argmax} {P(Y=c_k)\prod^n_{j=1} P(X^{(j)}=x^{(j)}|Y=c_k)}$

2 参数估计

在朴素贝叶斯法里，学习意味着估计 $P(Y=c_k)$ 和 $P(X^{(j)}=x^{j}|Y=c_k)$ 。有2种估计方法，包括极大似然估计和贝叶斯估计，其中极大似然估计可以看作是贝叶斯估计的一个特例。

2.1 极大似然估计

先验概率：

$P(Y=c_k)= \frac{\sum_{i=1}^N I(y_i = c_k) }{N},k=1,2,..,K$

条件概率：设第 $j$ 个特征 $x^{(j)}$ 的可能取值集合是 $\{a_j1,a_j2,..,a_{j{S_j}}\}$ ，条件概率的极大似然估计：

$P(X^{j}=a_{jl}|Y=c_k)=\frac{\sum_{i=1}^N I(x_i^{j}=a_{jl},Y=c_k)}{\sum_{i=1}^N I(y_i = c_k)}$

其中 $j=1,2,..,n;l=1,2,..,S_j;k=1,2,..,K$ 。 $I$ 为指示函数。

2.2 算法

1 计算先验概率

2 计算条件概率，共 $K\sum_{j=1}^nS_j$ 个条件概率

3 对于给定实例 $x=(x^{(1)},x^{(2)},...,x^{(n)})$ 计算

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

4 确定类

$y=f(x)=\underset{c_k}{argmax} {P(Y=c_k)\prod^n_{j=1} P(X^{(j)}=x^{(j)}|Y=c_k)}$

2.3 例

样本

可见 $X^{(1)}$ 的取值集合是 $\{1,2,3\}$ , $X^{(2)}$ 的取值集合是 $\{S,M,L\}$ , $Y$ 的取值集合是 $\{1,-1\}$ 。

共需要计算2个先验概率，和 $2*(3+3)=12$ 个条件概率。

$P(Y=1)=\frac{9}{15}$ , $P(Y=-1)=\frac{6}{15}$

$P(X^{(1)}=1|Y=1)=\frac{2}{9}$ , $P(X^{(1)}=2|Y=1)=\frac{3}{9}$ , $P(X^{(1)}=3|Y=1)=\frac{4}{9}$

$P(X^{(2)=S}|Y=1)=\frac{1}{9}$ , $P(X^{(2)}=M|Y=1)=\frac{4}{9}$ , $P(X^{(2)}=L|Y=1)=\frac{4}{9}$

$P(X^{(1)}=1|Y=-1)=\frac{3}{6}$ , $P(X^{(1)}=2|Y=-1)=\frac{2}{6}$ , $P(X^{(1)}=3|Y=-1)=\frac{1}{6}$

$P(X^{(2)}=S|Y=-1)=\frac{3}{6}$ , $P(X^{(1)}=M|Y=1)=\frac{2}{6}$ , $P(X^{(2)}=L|Y=-1)=\frac{1}{6}$

对于给定实例 $x=(2,S)^T$ ,

$P(Y=1)P(X^{(1)}=2|Y=1)P(X^{(2)}=S|Y=1)=\frac{1}{45}$ $P(Y=-1)P(X^{(1)}=2|Y=-1)P(X^{(2)}=S|Y=-1)=\frac{1}{15}$

所以 $y=-1$ 。

代码


import numpy as np

from collections import Counter #导入Counter用来计数，Counter返回一个字典

#载入数据

def loadDataSet():

    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]

    return x_1, x_2, Y

x_1, x_2, Y = loadDataSet()

#前期计算先验概率和条件概率

def Train(x_1, x_2, Y):

    x_1_class = Counter(x_1)#返回字典

    x_2_class = Counter(x_2)

    Y_class = Counter(Y)

    priorProb = {}

    condintionalProb = {}

    #先验概率

    for i in Y_class.keys():

        priorProb[str(i)] = Y_class[i]/len(Y)

    #条件概率  第一个特征量的各个可能值的条件概率

    for i in x_1_class.keys():

        for j in Y_class.keys():

            for l in range(len(x_1)):

                if x_1[l] == i and Y[l] == j:

                    condintionalProb['feature'+str(i)+' ; '+'label'+str(j)] = condintionalProb.get('feature'+str(i) +' ; '+'label'+str(j), 0) +1

            condintionalProb['feature'+str(i)+' ; '+'label'+str(j)] /= Y_class[j]

    #条件概率  第二个特征量的各个可能值的条件概率

    for i in x_2_class.keys():

        for j in Y_class.keys():

            for l in range(len(x_1)):

                if x_2[l] == i and Y[l] == j:

                    condintionalProb['feature'+str(i)+' ; '+'label'+str(j)] = condintionalProb.get('feature'+str(i) +' ; '+'label'+str(j), 0) +1

            condintionalProb['feature'+str(i)+' ; '+'label'+str(j)] /= Y_class[j]

    return priorProb, condintionalProb

A, B = Train(x_1, x_2, Y)

#对于新的实例点进行预测

def predict(priodProb, conditonalProb, X):

    Prob = {}

    for i in priodProb.keys():

        Prob[i] = priodProb[i]*conditonalProb['feature'+str(X[0])+' ; '+'label'+str(i)]*conditonalProb['feature'+str(X[1])+' ; '+'label'+str(i)]

    #选出可能性最大的

    maxCount = 0

    for key, value in Prob.items():

        if value > maxCount:

            maxCount = value

            maxIndex = key

    return Prob, maxCount, maxIndex

a, b, c = predict(A, B, [2, 'S'])

在这里关于条件概率生成的部分给出一个进阶版，更符合python的禅的 字典生成式 from 小海豚～～大力推荐。