数据挖掘十大算法朴素贝叶斯

前言

最近python学得也算是逐渐上手了，用来完成一些简单的编程任务应该是没什么问题了。从大三下学期开始到现在，一直也在陆陆续续看一些数据挖掘和机器学习的算法，但是怎么说呢，感觉干巴巴的看真的很难对算法本身有比较深入的理解，《机器学习》这本书看完了以后有也没有多大的作用，可能因为我本身就对数学不够敏感吧。之前在实验课上也用java去实现过一些常用的数据挖掘算法，但总体来说当时做得不够认真，对很多问题也没有仔细去想，结果更是没有好好分析。于是这次就打算从头开始吧，先来个专题把十大算法都自己实现一遍，对这些东西有个宏观的把握，理解算法的同时好好巩固一下python，这其实也算是必经之路吧。这个专题的重点是编程实现，所以有些理论的东西比如算法拓展什么的我暂时不打算研究太深。以后可能会再开一些专题去专门探讨理论部分。说完了！！！系列第一篇，先挑个简单的下手。

贝叶斯决策论

对于分类问题来说，贝叶斯决策论是在所有相关概率都已知的理想情况下，考虑如何基于这些概率和误判损失来选择最优的类别标记。这里我以多分类问题为例解释贝叶斯决策论的基本原理。假设类别标记的域为：$\gamma={c_1,c_2…c_N}$，用$\lambda_{ij}$来表示将一个本来为$c_j$的样本误分类为$c_i$的损失。那么基于后验概（后验和先验概率的区别这里就不说了）$P(c_i|x)$可以获得将样本$x$错误分类为$c_i$所产生的期望损失，也叫“条件风险”表示如下：

$R(c_i|x)=\sum_{j=1}^N\lambda_{ij}P(c_j|x)\tag1$

我们的目标是寻找一种预测$h:\chi\rightarrow\gamma$，使得总体化风险最小： $R(h)=E_x[R(h(x)|x)]$ 这里的$E$表示期望。这个式子反映了对于每个样本$x$，只要最小化其条件风险$R(h(x)|x)$，就可以最小化其总体风险$R(h)$。这就是贝叶斯判定准则：为最小化总体风险，只需在每个样本上选择那个能是条件风险$R(c|x)$最小的类别标记，即： $h^*(x)=min R(c|x)$ 这里的$h^*$称之为贝叶斯最优分类器，与之对应的总体风险$R(h^*)$称为贝叶斯风险。我们继续对贝叶斯判定准则拓展一下，假设目标是最小化分类错误类别，我们可以将损失因子$\lambda_{ij}$表示为如下形式：

$\lambda_{ij}= \begin{cases} 0, && \text {if }i=j; \\ 1, && otherwise, \\ \end{cases}$

根据式$(1)$不难得出此时的条件风险为：$R(c|x)=1-P(c|x)$。

进而最优贝叶斯分类器就可以改写为：$h^*(x)=maxP(c|x)$ 。

即对每个样本，将其标记为后验概率$P(c|x)$最大的类别。因此计算后验概率是贝叶斯判定准则中很重要的一步，但是现实中通常很那获得后验概率，我们需要从有限的训练样本中尽可能准确地估计出后验概率，主要用两种策略：

判别式模型：直接对后验概率建模

生成式模型：先对P(c,x)联合分布建模，然后在求出后验概率

决策树，BP神经网络和SVM都可以归为前者，而贝叶斯分类器则是典型的生成式模型。对于生成式模型，根据条件概型（后验概率就是一种条件概型）的计算公式有：

$P(c|x) = \frac{P(c,x)}{P(x)}$

再根据贝叶斯定理可以推得：

$P(c|x) = \frac{P(x|c)P(c)}{P(x)}\tag2$

现在我们就将后验概率的预测问题转换成了对先验概率$P(c)$和条件概率$P(x|c)$的计算，这里$P(x|c)$又被称作“似然”（这是在计算似然函数是用到的累乘项目，每个累乘项目都是一个似然，相关知识可以参考下概率论里的极大似然参数估计。）因为如果给定样本$P(x)$是固定的，我们把他叫“证据因子”，这里可以忽视它。

以上就是贝叶斯决策论里一些基础的东西了，贝叶斯分类器都是基于贝叶斯决策论产生的。常用的贝叶斯分类器包括：朴素贝叶斯分类器，半朴素贝叶斯分类器和贝叶斯网，本篇主要讲解朴素贝叶斯的原理以及实现。

朴素贝叶斯

根据$(2)$式可以看出，计算后验概率的难点就在于计算$P(x|c)$，因为$x$是多维的，所以这个概率实际上是个联合分布概率。从已有样本计算它有一定难度。为了避开这个障碍，朴素贝叶斯提出“属性独立”的假设条件。假设属性维数为d，根据这个条件对$(2)$式改写，我们可以得到贝叶斯公式：

$P(c|x) = \frac{P(x|c)P(c)}{P(x)}=\frac{P(c)}{P(x)}\prod_{i=1}^dP(x_i|c)\tag3$

因为“证据因子”是无关项，将$(3)$式表达为贝叶斯最优分类器的形式就是：

$h_{nb}(x)=maxP(c)\prod_{i=1}^dP(x_i|c)\tag4$

这就是朴素贝叶斯分类器的表达式。仔细观察，给定一个训练数据集，这些计算项目都是可以通过统计计算得来的，我们假设样本集合是$D$，c类型的样本集合为$D_c$，在属性i上取值为$x_i$并且样本类型为c的样本集合为$D_{c,x_i}$，那么有：

$\begin{cases} P(c)=\frac{|D_c|}{D} \\ P(x_i|c)=\frac{|D_{c,x_i}|}{D_c} \\ \end{cases}$

如果某个属性时连续的，对应的条件概型不能直接计算，我们可以假设这个条件概型的概率密度函数服从高斯分布，其均值和方差分别为$c$类样本里当前属性取值的均值和方差，即$p(x_i|c)\sim{}N(\mu_{c,i},\sigma_{c,i}^2)$。

python实现

我们假设有这样的一个二分类问题：判定某一天是不是个好天气，对应的输入属性有四个，分别是：天气，气温，湿度和风力并且这些属性都是离散的，具体来说：

outlook有三个分类：sunny、overcast、rain；
temp有三个分类：hot、mild、cool；
humidity有两个分类：high、normal；
wind有两个分类：strong、weak；
class有两个分类：yes、no；

现在实现一个简单的python程序来对新的输入做出判断：

# 计算先验概率
def pc(data, target):
    cnt = 0
    for e in data:
        if e["class"] == target:
            cnt += 1
    return cnt/len(data)

# 计算“似然”
def pt(data, target, attr_name, attr_value):
    cnt1 = 0;
    cnt2 = 0;
    for e in data:
        if e["class"] == target:
            cnt1 += 1
            if e[attr_name] == attr_value:
                cnt2 += 1
    return cnt2/cnt1

# 计算后验概率
def nb(data,test_case,class1,class2):
    pclass1 = pc(data, class1)
    pclass2 = pc(data, class2)

    for key,val in test_case.items():
        print(key,val)
        pclass1 *= pt(data,class1,key,val)
        pclass2 *= pt(data,class2,key,val)
    return {class1:pclass1, class2:pclass2}

# 测例
if __name__ == "__main__":
    data = [
        {"outlook": "sunny", "temp": "hot", "humidity": "high", "wind": "weak", "class": "no"},
        {"outlook": "sunny", "temp": "hot", "humidity": "high", "wind": "strong", "class": "no"},
        {"outlook": "overcast", "temp": "hot", "humidity": "high", "wind": "weak", "class": "yes"},
        {"outlook": "rain", "temp": "mild", "humidity": "high", "wind": "weak", "class": "yes"},
        {"outlook": "rain", "temp": "cool", "humidity": "normal", "wind": "weak", "class": "yes"},
        {"outlook": "rain", "temp": "cool", "humidity": "normal", "wind": "strong", "class": "no"},
        {"outlook": "overcast", "temp": "cool", "humidity": "normal", "wind": "strong", "class": "yes"},
        {"outlook": "sunny", "temp": "mild", "humidity": "high", "wind": "weak", "class": "no"},
        {"outlook": "sunny", "temp": "cool", "humidity": "normal", "wind": "weak", "class": "yes"},
        {"outlook": "rain", "temp": "mild", "humidity": "normal", "wind": "weak", "class": "yes"},
        {"outlook": "sunny", "temp": "mild", "humidity": "normal", "wind": "strong", "class": "yes"},
        {"outlook": "overcast", "temp": "mild", "humidity": "high", "wind": "strong", "class": "yes"},
        {"outlook": "overcast", "temp": "hot", "humidity": "normal", "wind": "weak", "class": "yes"},
        {"outlook": "rain", "temp": "mild", "humidity": "high", "wind": "strong", "class": "no"},
    ]

    print(nb(data, {"outlook": "sunny", "temp": "cool", "humidity": "high", "wind": "strong"}, "yes", "no"))

结果如下：

outlook sunny

temp cool

humidity high

wind strong

{‘yes’: 0.005291005291005291, ‘no’: 0.02057142857142857}

用python实现朴素贝叶斯分类

FEATURED TAGS

FRIENDS