机器学习 学习笔记（11） 贝叶斯分类器

贝叶斯决策论是在概率框架下实施决策的基本方法。对分类任务来说，在所有相关概率都已知的理想情形下，贝叶斯决策论考虑如何基于这些概率和误判损失来选择最优的类别标记，

假设有N种可能的类别标记，即

y=\{c_1,c_2,...,c_N\}

，

\lambda _{ij}

是将一个真实标记为

c_j

的样本误分类为

c_i

所产生的损失，则基于后验概率

P(c_i|x)

可获得将样本x分类为

c_i

所产生的期望损失，记在样本x上的条件风险

R(c_i|x)=\sum_{j=1}^N\lambda _{ij}P(c_j|x)

希望找到一个判定准则h以最小化总体风险

R(h)=E_x[R(h(x)|x)]

显然，对于每个样本x，若h能最小化条件风险

R(h(x)|x)

，则总体风险

R(h)

也将被最小化，这就产生了贝叶斯判定准则：为最小化总体风险，只需在每个样本上选择那个能使条件风险

R(c|x)

最小的类别标记，即

h^*(x)=\arg \min \limits_{c\in y} R(c|x)

，此时，

h^*

称为贝叶斯最优分类器，与之对应的总体风险

R(h^*)

称为贝叶斯风险。

1-R(h^*)

反映了分类器所能达到的最好性能，即通过机器学习所能产生的模型精度的理论上限。

若误判损失

\lambda _{ij}

用0/1损失来表示，则条件风险为

R(c|x)=1-P(c|x)

，于是，最小化分类错误率的贝叶斯最优分类器为

h^*(x)=\arg \max \limits_{c\in y}P(c|x)

，即对每个样本x，选择能使后验概率P(c|x)最大的类别标记。

要求解

P(c|x)

，主要有两种策略：给定x，可通过直接建模

P(c|x)

来预测c，这样得到的是判别式模型，也可先对联合概率分布

P(x,c)

建模，然后在由此获得

P(c|x)

，这样得到的是生成式模型。

生成式模型必然考虑：

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

，基于贝叶斯定理：

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

其中

P(c)

是类“先验”概率，

P(c|x)

是样本x相对与类标记c的类条件概率，或称为似然。

P(x)

是用于归一化的证据因子。对给定样本x，证据因子

P(x)

与类标记无关，因此估计

P(c|x)

的问题就转化为如何基于训练数据D来估计先验

P(c)

和

P(x|c)

。

估计类条件概率的一种常用策略是先假定其具有某种确定的概率分布形式，再基于训练样本对概率分布的参数进行估计。具体的，记关于类别c的类条件概率为

P(x|c)

，假设

P(x|c)

具有确定的形式并且被参数向量

\theta _c

唯一确定，则任务就是利用训练集D估计参数

\theta _c

，为明确起见，将

P(x|c)

记为

P(x|\theta_c)

。

概率模型的训练过程就是参数估计过程。

极大似然法（Maximum Likelihood Estimation，MLE）,根据数据采样来估计概率分布。

令

D_c

表示训练集D中第c类样本组合的集合，假设这些样本是独立同分布的，则参数

\theta _c

对于数据集

D_c

的似然是：

P(D_c|\theta_c)=\prod_{x\in D_c} P(x|\theta_c)

对

\theta _c

进行极大似然估计，就是去寻找能最大化似然

P(D_c|\theta_c)

的参数值

\hat{\theta_c}

。连乘容易造成下溢，通常使用对数似然：

LL(\theta_c)=logP(D_c|\theta_c)=\sum_{x \in D_c} logP(x|\theta_c)

利用参数化的方法虽能使类条件概率估计变得相对简单，但估计结果的准确性严重依赖于所假设的概率分布形式是否符合潜在的正式数据分布。

朴素贝叶斯分类器

朴素贝叶斯分类器采用了属性条件独立假设：对已知类别，假设所有属性相互独立，换言之，假设每个属性独立地对分类结果产生影响。

基于属性条件独立假设：

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

d为属性数目，

x_i

为x在第i个属性上的取值，基于贝叶斯判定准则有：

h_{nb}(x)=\arg \max \limits_{c\in y}P(c)\prod_{i=1}^dP(x_i|c)

，这就是朴素贝叶斯分类器的表达式。

显然，朴素贝叶斯分类器的训练过程就是基于训练集D来估计类先验概率P(c)，并为每个属性估计P(xi|c)。

令Dc表示训练集的中第c类样本组成的集合，若有充足的独立同分布样本，则可容易地估计出类先验概率

P(c)=\frac{|D_c|}{|D|}

，

对离散属性而言，令

D_{c,x_i}

表示Dc中在第i个属性上取值为xi的样本组成的集合，则条件概率P(xi|c)可估计为：

P(x_i|c)=\frac{|D_{c,x_i}|}{|D_c|}

对连续属性可考虑概率密度函数，假定

p(x_i|c)\sim N(\mu_{c,i},\sigma ^2_{c,i})

，其中

\mu_{c,i}

和

\sigma ^2_{c,i}

分别是第c类样本在第i个属性上取值的均值和方差，则有：

p(x_i|c)=\frac{1}{\sqrt{2\pi}\sigma _{c,i}} exp(-\frac{(x_i-\mu_{c,i})^2}{2\sigma ^2_{c,i}})

但是某个属性值在训练集中没有与某个类同时出现过，直接进行概率计算时会导致0概率的出现。

为了避免其他属性携带的信息被训练集中未出现的属性值“抹去”，在估计概率值时通常要进行“平滑”，常用“拉普拉斯修正”，具体来说，令N表示训练集D中可能的类别，

N_i

表示第i个属性可能的取值数，则：

\hat{P}(c)=\frac{|Dc|+1}{|D|+N}

\hat{P}(x_i|c)=\frac{|D_{c,x_i}|+1}{|D_c|+N_i}

拉普拉斯修正避免了因训练集样本不充分而导致概率估值0的问题，并且在训练集变大时，修正过程所引入的先验的影响也会逐渐变得可忽略，使得估值渐趋向于实际概率值。

半朴素贝叶斯分类器

对属性条件独立性假设进行一定程度的放松，产生了半朴素贝叶斯分类器。半朴素贝叶斯分类器的基本想法是适当考虑一部分属性间的相互依赖信息，从而既不需要进行完全联合概率计算，又不至于彻底忽略了比较强的属性依赖关系。独依赖估计（One-Dependent Estimator，ODE）是半朴素贝叶斯分类器最常用的一种策略，顾名思义，独依赖就是假设每个属性在类别之外最多仅依赖于一个其他属性。

p(c|x)\propto P(c)\sum_{i=1}^d P(x_i|c,pa_i)

，

pa_i

为属性

x_i

所依赖的属性，称为

x_i

的父属性，若副属性已知，就可以可以概率值

P(x_i|c,pa_i)

。问题的关键转化为如何确定每个属性的父属性，不同的做法产生不同的独依赖分类器。

最直接的做法是假设所有属性都依赖于同一个属性，称为“超父”，然后通过交叉验证等方法来确定超父属性，由此形成了SPODE(Super-Parent ODE方法)。在下图（b）中，x1是超父属性。

TAN则是在最大带权生成树算法的基础上通过以下步骤将属性之间的依赖关系约简为如（c）所示的树形结构：

（1）计算任意两个属性之间的条件互信息，

I(x_i,x_i|y)=\sum_{x_i,x_j;c\in y}log\frac{P(x_i,x_j|c)}{P(x_i|c)P(x_j|c)}

（2）以属性为结点构建完全图，任意两个结点之间边的权重设为

I(x_i,x_j|y)

（3）构建此完全图的最大带权生成树，挑选根变量，将边置为有向

（4）加入类别结点y，增加从y到每个属性的有向边

条件互信息

I(x_i,x_j|y)

刻画了属性

x_i

和

x_j

在已知类别情况下的相关性，因此，通过最大生成树算法，TAN仅仅保留了强相关属性之间的依赖性。

AODE（Averaged One-Dependent Estimator）是一种基于集成的学习机制，更为强大的独依赖分类器，与SPODE通过模型选择确定超父属性不同，AODE尝试将每个属性作为超父来构建SPODE，然后将那些具有足够训练数据支撑的SPODE集成起来作为最终结果，即：

P(c|x)\propto \sum_{i=1,|D_x_i|\geqslant m'}^d P(c,x_i) \prod_{j=1}^dP(x_j|c,x_i)

其中

D_x_i

是在第i个属性上取值为

x_i

的样本集合，

m'

为阈值常数，显然，AODE需估计

P(c,x_i)

和

P(x_j|c,x_i)

。

\hat{P}(c,x_i)=\frac{|D_{c,x_i}|+1}{|D|+N\times N_i}

\hat{P}(x_j|c,x_i)=\frac{|D_{c,x_i,x_j}|+1}{|D_{c,x_i}|+N_j}

N是D中可能的类别数，

N_i

是第i个属性可能的取值数，

D_{c,x_i}

是类别为c且在第i个属性上取值为

x_i

的样本集合，

D_{c,x_i,x_j}

是类别为c且在第i个和第j个属性上取值分别为

x_i

和

x_j

的样本集合。

与朴素贝叶斯分类器类似，AODE的训练过程也是计数，即在训练数据集上对符合条件的样本进行计数的过程。与朴素贝叶斯分类器相似，AODE无需模型选择，既能通过预计计算节省预测时间，也能采取懒惰学习方式在预测时再进行计数，并且易于实现增量学习。

贝叶斯网

贝叶斯网亦称为信念网（belief network）,它借助有向无环图（Directed Acyclic Graph,DAG）来刻画属性之间依赖关系，并使用条件概率表（Conditional Probability Table, CPT）来描述属性的联合概率分布。

一个贝叶斯网B由结构G和参数

\theta

两部分构成，即

B=<G,\theta>

。网络结构G是一个有向无环图，其每个结点对应一个属性，若两个属性有直接依赖关系，则它们由一条边连接起来，参数

\theta

定量描述这种依赖关系，假设属性

x_i

在G中父结点集为

\pi_i

，则

\theta

包含了每个属性的条件概率表，

\theta_{x_i|\pi_i}=P_B(x_i|\pi_i)

贝叶斯网结构有效地表达了属性间的条件独立性，给定父结点集，贝叶斯网假设每个属性与它的非后裔属性独立，于是

B=<G,\theta>

将属性集

x_1,x_2,...,x_d

的联合概率分布定义为

P_B(x_1,x_2,...,x_d)=\prod_{i=1}^dP_B(x_i|\pi_i)=\prod_{i=1}^d \theta _{x_i|\pi_i}

贝叶斯网中三个变量之间的典型依赖关系：

在同父结构中，给定父结点

x_1

的取值，则

x_3

与

x_4

条件独立。在顺序结构中，给定x的值，则y与z条件独立。V型结构也称为冲撞结构，给定

x_4

的值，

x_1

与

x_2

必不独立，若

x_4

取值完全未知，则V型结构下，

x_1

与

x_2

相互独立。称为边际独立性。

为了分析有向图中变量间的条件独立性，可以使用有向分离，先把有向图转变为一个无向图：

• 找出有向图中的所有V型结构，在V型结构的两个父结点之间加上一条无向边
• 将所有有向边改为无向边

由此产生的无向图称为道德图，令父结点相连的过程称为道德化。

基于道德图能直观、迅速地找到变量间的条件独立性。假定道德图中有变量x,y和变量集合

z=\{z_i\}

，若变量x和y能在图上被z分开，即从道德图中将变量集合z去除后，x和y分属两个连通分支，则称变量x和y被z有向分离。

贝叶斯网络学习的首要任务是根据训练数据集来找出结构最恰当的贝叶斯网。“评分搜索”是求解这一问题的常永方法。具体来说，我们定义一个评分函数，以此来估计贝叶斯我那个与训练数据的契合程度，然后基于这个评分函数来寻找结构最优的贝叶斯网。

常用评分函数通常基于信息论准则，此类准则将学习问题看做一个数据压缩任务，学习的目标是找到一个能以最短编码长度描述训练数据的模型，此时编码的长度包括了描述模型自身所需的字节长度和使用该模型描述数据所需的字节长度。对贝叶斯网学习而言，模型就是一个贝叶斯网，同时每个贝叶斯网描述了一个在训练数据集上的概率分布，自有一套编码机制能使哪些经常出现的样本有更短的编码。于是，我们应该选择那个综合编码长度（包括描述网络和编码数据）最短的贝叶斯网，这就是“最小描述长度”（Minimal Description Length,MDL）.

给定数据集

D=\{x_1,x_2,...,x_m\}

，贝叶斯网

B=<G,\theta>

在D上的评

Q=\{Q_1,Q_2,...,Q_n\}

分函数可写为：

s(B|D)=f(\theta )|B|-LL(B|D)

，|B|是贝叶斯网参数个数，

f(\theta )

表示描述每个参数

\theta

所需要的字节数，而

LL(B|D)=\sum_{i=1}^mlogP_B(x_i)

是贝叶斯网B的对数似然。

s(B|D)=f(\theta )|B|-LL(B|D)

第一项计算编码贝叶斯网B所需的字节数，第二项是计算B所对应的概率分布

P_B

对D描述得多好。学习任务转为一个优化任务，寻找一个贝叶斯网B使得评分函数

s(B|D)

最小。

若

f(\theta )=1

，即每个参数用1字节描述，则得到AIC评分函数。若

f(\theta )=\frac{1}{2}logm

，即每个参数用

\frac{1}{2}logm

字节描述，则得到BIC评分函数。

从所有可能的网络结构空间中搜索最优贝叶斯网络结构是一个NP难问题，难以快速求解。有两种常用的策略能在有限时间内求得近似解：第一种是贪心法，例如从某个网络结构除法，每次调整一条边（增加、删除或调整方向），直到评分函数值不再降低为止，第二种是通过给网络结构施加约束来削减搜索空间，例如将网络结构限定为树形结构等。

通过已知变量观测值来推测待查询变量的过程称为推断，一直变量观测值称为证据。最理想的是直接根据贝叶斯网定义的联合概率分布来精确计算后验概率，但是这被证明是NP难的。现实应用中，贝叶斯网的近似推断经常使用吉布斯采样来完成，这是一种随机采样方法。

令

Q=\{Q_1,Q_2,...,Q_n\}

表示待查询变量，

E=\{E_1,E_2,...,E_k\}

为证据变量，已知其取值为

e=\{e_1,e_2,...,e_k\}

。目标是计算后验概率

P(Q=q|E=e)

，其中

q=\{q_1,q_2,...,q_n\}

是待查询变量的一组取值。吉布斯采样算法先随机产生一个与证据E=e一致的样本

q^0

作为初始点，然后每步从当前样本出发产生下一个样本。具体来说，在第t次采样中，算法先假设

q^t=q^{t-1}

，然后对非证据变量逐个进行采样改变其取值，采样概率根据贝叶斯网B和其他变量的当前取值(Z=z)计算获得。假定经过T次采样得到的与q一致的样本共有

n_q

个，则可近似估算出后验概率：

P(Q=q|E=e)\simeq \frac{n_q}{T}

。

事实上，吉布斯采样是在贝叶斯网所有变量的联合状态空间与证据E=e一致的子空间中进行随机漫步，每一步仅依赖于前一步的状态，这是一个马尔科夫链。在一定条件下，无论从什么初始状态开始，马尔科夫链的第t步的状态分布在t趋于无穷时必收敛于一个平稳分布。对于吉布斯采样而言，这个分布恰好是

P(Q|E=e)

，因此在T很大时，吉布斯采样相当于根据

P(Q|E=e)

采样，从而保证了收敛到

P(Q=q|E=e)

。

由于马尔科夫链通常需要很长时间才能趋于平稳分布，因此吉布斯采样算法的收敛速度较慢。此外，若贝叶斯网中存在计算概率0或1，则不能保证马尔科夫链存在平稳分布，此时吉布斯采样会给出错误的估计结果。

以下代码为朴素贝叶斯分类器代码：

# 代码和数据集来源于机器学习实战，https://github.com/AnnDWang/MachineLearning/blob/master/thirdbook/ch4/bayes.py
from numpy import *
import feedparser
# 词表到向量的转换函数
def loadDataSet():
    postingList=[['my','dog','has','flea','problems','help','please'],
                 ['maybe','not','take','him','to','dog','park','stupid'],
                 ['my','dalmation','is','so','cute','I','love','him'],
                 ['stop','posting','stupid','worthless','garbage'],
                 ['mr','licks','ate','my','steak','how','to','stop','him'],
                 ['quit','buying','worthless','dog','food','stupid']]
    classVec=[0,1,0,1,0,1]# 1代表侮辱性文字，0代表正常言论
    return postingList,classVec

# 创建一个包含在所有文档中出现的不重复词的列表，为此使用了python的set数据类型
# 将词条列表输给set构造函数，set就会返回一个不重复词表
# 首先创建一个空集合，然后将每篇文档返回的新词集合添加到该集合中。
# 操作符|用于求两个集合的并集，这也是一个按位或（OR）操作符
# 在数学符号表示上，按位或操作与集合求并操作使用相同记号
def createVocabList(dataSet):
    vocabSet=set([])# 创建一个空集
    for document in dataSet:
        vocabSet=vocabSet|set(document) # 创建两个集合的并集
    return list(vocabSet)

# 输入参数为词汇表及某个文档
# 输出时文档向量
# 向量的每个元素为1或0，分别表示词汇表的单词在输入文档中是否出现
# 函数首先创建一个和词汇表等长的向量，并将其元素都设置为0
# 接着，遍历文档中的所有单词，如果出现了词汇表中的单词，则将输出的文档向量中的对应值设为1
# 一切都顺利，就不需要检查某个词是否还在vocabList中
def setOfWords2Vec(vocabList,inputSet):
    returnVec=[0]*len(vocabList) # 创建一个其中所含元素都为0的向量
    for word in inputSet:
        if word in vocabList:
            returnVec[vocabList.index(word)]=1
        else:
            print("the word: %s is not in my Voabulary!" % word)
    return returnVec

# 朴素贝叶斯词袋模型
def bagOfWords2VecMN(vocabList,inputSet):
    returnVec=[0]* len(vocabList)
    for word in inputSet:
        if word in vocabList:
            returnVec[vocabList.index(word)]+=1
    return returnVec

listOPosts,listClasses=loadDataSet()

myVocabList=createVocabList(listOPosts)

myreturnVec=setOfWords2Vec(myVocabList,listOPosts[0])

# 朴素贝叶斯分类器训练函数
def trainNB0(trainMatrix,trainCategory):
    numTrainDocs=len(trainMatrix)
    numWords=len(trainMatrix[0])
    pAbusive=sum(trainCategory)/float(numTrainDocs)
    p0Num=ones(numWords)
    p1Num=ones(numWords)
    p0Denom=2.0
    p1Denom=2.0  # 初始化概率
    for i in range(numTrainDocs):
        if trainCategory[i]==1:
            p1Num+=trainMatrix[i]   # 向量相加
            p1Denom+=sum(trainMatrix[i])
        else:
            p0Num+=trainMatrix[i]
            p0Denom+=sum(trainMatrix[i])
    p1Vect=log(p1Num/p1Denom)  # change to log()
    p0Vect=log(p0Num/p0Denom)  # change to log()
    return p0Vect,p1Vect,pAbusive

trainMat=[]
for postinDoc in listOPosts:
    trainMat.append(setOfWords2Vec(myVocabList,postinDoc))

p0v,p1v,pAb=trainNB0(trainMat,listClasses)

# 朴素贝叶斯分类函数
def classifyNB(vec2Classify,p0Vec,p1Vec,pClass1):
    p1=sum(vec2Classify*p1Vec)+log(pClass1)
    p0=sum(vec2Classify*p0Vec)+log(1.0-pClass1)

    if p1>p0:
        return 1
    else:
        return 0

def testingNB():
    listOPosts,listClasses=loadDataSet()
    myVocabList=createVocabList(listOPosts)
    trainMat=[]
    for postinDoc in listOPosts:
        trainMat.append(setOfWords2Vec(myVocabList,postinDoc))
    p0V,p1V,pAb=trainNB0(array(trainMat),array(listClasses))
    testEntry=['love','my','dalmation']
    thisDoc=array(setOfWords2Vec(myVocabList,testEntry))
    print(testEntry,'classified as: ',classifyNB(thisDoc,p0V,p1V,pAb))
    testEntry=['stupid','garbage']
    thisDoc=array(setOfWords2Vec(myVocabList,testEntry))
    print(testEntry, 'classified as: ', classifyNB(thisDoc, p0V, p1V, pAb))


testingNB()

参考：

1. 《机器学习》
2. 《统计学习方法》
3. 《机器学习实战》