模式识别 ：贝叶斯分类

2020/2/141第3讲贝叶斯分类2020/2/142贝叶斯网络学习概述•简单地说，贝叶斯网络是一种用来表示变量间连续概率的有向无环图模型，图中的节点表示变量，有向边表示变量间的依赖关系。•基于贝叶斯网络的推理为衡量多个假设的置信度提供了定量方法，为直接操作概率的学习算法提供了理论基础，也为其他算法的分析提供了理论框架。2020/2/143先验概率和后验概率•用P(h)表示在没有训练数据前假设h拥有的初始概率。P(h)被称为h的先验概率。•先验概率反映了关于h是一正确假设的机会的背景知识•如果没有这一先验知识，可以简单地将每一候选假设赋予相同的先验概率•类似地，P(D)表示训练数据D的先验概率，P(D|h)表示假设h成立时D的概率•在分类中，我们关心的是P(h|D)，即给定D时h的成立的概率，称为h的后验概率2020/2/144贝叶斯公式•贝叶斯公式提供了从先验概率P(h)、P(D)和P(D|h)计算后验概率P(h|D)的方法•P(h|D)随着P(h)和P(D|h)的增长而增长，随着P(D)的增长而减少，即如果D独立于h时被观察到的可能性越大，那么D对h的支持度就越小。)()()|()|(DPhPhDPDhP2020/2/145基本概率公式表•乘法规则：P(AB)=P(A|B)P(B)=P(B|A)P(A)•加法规则：P(AB)=P(A)+P(B)-P(AB)•贝叶斯法则：P(h|D)=P(D|h)P(h)/P(D)•全概率法则：如果事件A1...An互斥，且满足，则1)(1niiAPniiiAPABPBP1)()|()(2020/2/146贝叶斯网络与联合概率分布2020/2/147贝叶斯网络分类器•设每个实例x可由属性值的合取描述，而目标函数f(x)从某有限集合V中取值。•应用贝叶斯网络方法的新实例分类目标是在给定描述实例的属性值a1,...,an下，得到最可能的目标值vMAP•使用贝叶斯公式变化上式),...,|(maxarg1njvMAPaavPvj)()|,...,(maxarg),...,()()|,...,(maxarg111jjnVvnjjnVvMAPvPvaaPaaPvPvaaPvjj2020/2/148最优贝叶斯网络分类器2020/2/149贝叶斯网络分类器的困难•基于训练数据估计上面式子中的两个数据项的值–估计P(vj)虽然很容易：计算每个目标值vj出现在训练数据中的频率。–估计P(a1,...an|vj)却非常困难，除非有一个非常大的训练数据集，否则无法获得可靠的估计。2020/2/1410属性条件独立假设•为避免估计P(a1,...an|vj)遇到的困难，朴素贝叶斯网络分类器引入了一个简单的假定：在给定目标值时，属性值之间相互条件独立。这个假设被广泛第称作属性条件独立假设。•所以有成立。ijijnvaPvaaP)|()|,...,(12020/2/1411朴素贝叶斯分类器•朴素贝叶斯网络分类器的计算公式如下：•显然，从训练数据中估计不同P(ai|vj)项的计算量比要估计P(a1,...,an|vj)项所需的计算量小得多。•朴素贝叶斯网络分类器没有明确地搜索可能假设空间的过程，只需简单地计算训练样例中不同数据组合的出现频率。ijijVvNBvaPvPvj)|()(maxarg2020/2/1412NB图2020/2/1413朴素贝叶斯网络分类的例子•已知PlayTennis数据库中的14个训练样例，则给新实例sunny,cool,high,strong分类用公式：–根据数据库，可以计算出上式需要的各项概率值•P(yes)=9/14=0.64•P(no)=5/14=0.36•P(strong|yes)=3/9=0.33•P(strong|no)=3/5=0.60•...–求vNB•P(yes)P(sunny|yes)P(cool|yes)P(high|yes)P(strong|yes)=0.0053•P(no)P(sunny|no)P(cool|no)P(high|no)P(strong|no)=0.0206•vNB=no)|()|()|()|()(maxarg)|()(maxarg},{},{jjjjjnoyesvijijnoyesvNBvstrongPvhighPvcoolPvsunnyPvPvaPvPvjj2020/2/1414NB算法的不足及改进•学习NB分类器固然简单，但其不现实的属性条件独立假设严重影响了它的分类性能。所以学习最优的BN分类器引起了广大研究者的兴趣，遗憾的是，这是一个NP难问题。•因此，学习改进的NB分类器才是真正可行的，最近的研究成果几乎都是这样产生的。2020/2/1415NB算法的不足及改进（续）•改进的方法当然就是最大限度地释放朴素贝叶斯网络的属性条件独立假设。具体方法分三类：1）选择属性子集，如SBC、WRAP和ENB等；2）拓展朴素贝叶斯网络的结构，用有向边来表达属性之间的依赖关系，如TAN、SP-TAN和ODANB等；3）利用局部学习的原理，在整个训练实例的局部构建朴素贝叶斯网络分类器，如NBTree、LWNB和SNNB等。2020/2/1416概率估计•概率估计–我们通过在全部事件基础上观察某事件出现的比例来估计概率–当样本很小时，采用平滑技术–Laplaceestimation–M-estimation–m是一称为等效样本大小的常量，如1、2、…等。p是将要确定的概率的先验估计，在缺少其他信息时，选择p的一种典型的方法是均匀概率，比如某属性有k个可能值，那么p=1/k–M-estimation可被解释为将n个实际的观察扩大，加上m个按p分布的虚拟样本。–当m=1/p时，M-estimation为Laplaceestimation。mnmpnc