周志华-机器学习-西瓜书-全书16章-ppt-Chap07贝叶斯分类器

霍轩第七章：贝叶斯分类器章节目录贝叶斯决策论极大似然估计朴素贝叶斯分类器半朴素贝叶斯分类器贝叶斯网EM算法章节目录贝叶斯决策论极大似然估计朴素贝叶斯分类器半朴素贝叶斯分类器贝叶斯网EM算法贝叶斯决策论贝叶斯决策论（Bayesiandecisiontheory）是在概率框架下实施决策的基本方法。在分类问题情况下，在所有相关概率都已知的理想情形下，贝叶斯决策考虑如何基于这些概率和误判损失来选择最优的类别标记。贝叶斯决策论贝叶斯决策论（Bayesiandecisiontheory）是在概率框架下实施决策的基本方法。在分类问题情况下，在所有相关概率都已知的理想情形下，贝叶斯决策考虑如何基于这些概率和误判损失来选择最优的类别标记。假设有种可能的类别标记，即，是将一个真实标记为的样本误分类为所产生的损失。基于后验概率可获得将样本分类为所产生的期望损失（expectedloss）或者称条件风险（conditionalrisk）我们的任务是寻找一个判定准则以最小化总体风险11212,,,,,,||7.1mmNiijjjRYcXPYcXxxxxxx贝叶斯决策论显然，对每个样本，若能最小化条件风险，则总体风险也将被最小化。贝叶斯决策论显然，对每个样本，若能最小化条件风险，则总体风险也将被最小化。这就产生了贝叶斯判定准则（Bayesdecisionrule）：为最小化总体风险，只需在每个样本上选择那个能使条件风险最小的类别标记，即此时，被称为贝叶斯最优分类器(Bayesoptimalclassifier)，与之对应的总体风险称为贝叶斯风险(Bayesrisk)反映了分类起所能达到的最好性能，即通过机器学习所能产生的模型精度的理论上限。贝叶斯决策论具体来说，若目标是最小化分类错误率，则误判损失可写为贝叶斯决策论具体来说，若目标是最小化分类错误率，则误判损失可写为此时条件风险1(|)(|)(|)1(|)7.5NijjijjjiiRcXxPcXxPcXxPcXx(|)(min)m|axiiiiRcXxPcXx后验概率贝叶斯决策论具体来说，若目标是最小化分类错误率，则误判损失可写为此时条件风险于是，最小化分类错误率的贝叶斯最优分类器为即对每个样本，选择能使后验概率最大的类别标记。贝叶斯决策论不难看出，使用贝叶斯判定准则来最小化决策风险，首先要获得后验概率。然而，在现实中通常难以直接获得。机器学习所要实现的是基于有限的训练样本尽可能准确地估计出后验概率。主要有两种策略：判别式模型（discriminativemodels）给定，通过直接建模,来预测决策树，BP神经网络，支持向量机生成式模型（generativemodels）先对联合概率分布建模，再由此获得生成式模型考虑121212,,(,Y=)(Y=,,,,,|)77,,.()iimmmxxxxxxxxPXcPcXPXx贝叶斯决策论生成式模型贝叶斯决策论生成式模型基于贝叶斯定理，可写成121212,,(,Y=)(Y=,,,,,|)77,,.()iimmmxxxxxxxxPXcPcXPXx121212,,PY=|Y=(Y=|)7.,,,,,,(),7miiimmcPXcPcXPxxxxxxxxxX贝叶斯决策论生成式模型基于贝叶斯定理，可写成先验概率样本空间中各类样本所占的比例，可通过各类样本出现的频率估计（大数定理）贝叶斯决策论生成式模型基于贝叶斯定理，可写成先验概率样本空间中各类样本所占的比例，可通过各类样本出现的频率估计（大数定理）“证据”（evidence）因子，与类标记无关贝叶斯决策论生成式模型基于贝叶斯定理，可写成先验概率样本空间中各类样本所占的比例，可通过各类样本出现的频率估计（大数定理）“证据”（evidence）因子，与类标记无关类标记相对于样本的“类条件概率”(class-conditionalprobability),或称“似然”。章节目录贝叶斯决策论极大似然估计朴素贝叶斯分类器半朴素贝叶斯分类器贝叶斯网EM算法章节目录贝叶斯决策论极大似然估计朴素贝叶斯分类器半朴素贝叶斯分类器贝叶斯网EM算法朴素贝叶斯分类器估计后验概率主要困难：类条件概率是所有属性上的联合概率难以从有限的训练样本估计获得。121212,,PY=|Y=(Y=|)7.,,,,,,(),7miiimmcPXcPcXPxxxxxxxxxX1212,,maxY,=|max|Y,,=,iiimimxxxPcXPXxxxc12121AA=AAAPPP123121321AAA=AAAAAAPPPP123121321121AAAA=AAAAAAAAAAmmmPPPPP12121312132211211121|Y=|Y=|Y=|Y=|,,,,,,,=,,YmmmiiiimmixxxPXxxxxxxxxxxcPXcPXXcPXXXcPXXXXc朴素贝叶斯分类器估计后验概率主要困难：类条件概率是所有属性上的联合概率难以从有限的训练样本估计获得。朴素贝叶斯分类器(NaïveBayesClassifier)采用了“属性条件独立性假设”(attributeconditionalindependenceassumption)：每个属性独立地对分类结果发生影响。12121312132211211121|Y=|Y=|Y=|Y=|,,,,,,,=,,YmmmiiiimmixxxPXxxxxxxxxxxcPXcPXXcPXXXcPXXXXc12121233|Y=|Y=|Y=|Y=|Y=,,,iiimimmiPXcPXcPXcPXcxxxxxxxPXc朴素贝叶斯分类器估计后验概率主要困难：类条件概率是所有属性上的联合概率难以从有限的训练样本估计获得。朴素贝叶斯分类器(NaïveBayesClassifier)采用了“属性条件独立性假设”(attributeconditionalindependenceassumption)：每个属性独立地对分类结果发生影响。基于属性条件独立性假设，(7.8)可重写为其中为属性数目，为在第个属性上的取值。朴素贝叶斯分类器朴素贝叶斯分类器由于对所有类别来说相同，因此基于式(7.6)的贝叶斯判定准则有这就是朴素贝叶斯分类器的表达式朴素贝叶斯分类器朴素贝叶斯分类器的训练器的训练过程就是基于训练集估计类先验概率并为每个属性估计条件概率。令表示训练集中第类样本组合的集合，若有充足的独立同分布样本，则可容易地估计出类先验概率对离散属性而言，令表示中在第个属性上取值为的样本组成的集合，则条件概率可估计为对连续属性而言可考虑概率密度函数，假定，其中和分别是第类样本在第个属性上取值的均值和方差，则有朴素贝叶斯分类器例子：用西瓜数据集3.0训练一个朴素贝叶斯分类器，对测试例“测1”进行分类(p151,西瓜数据集p84表4.3)拉普拉斯修正若某个属性值在训练集中没有与某个类同时出现过，则直接计算会出现问题，.比如“敲声=清脆”测试例，训练集中没有该样例，因此连乘式计算的概率值为0，无论其他属性上明显像好瓜，分类结果都是“好瓜=否”，这显然不合理。拉普拉斯修正若某个属性值在训练集中没有与某个类同时出现过，则直接计算会出现问题，.比如“敲声=清脆”测试例，训练集中没有该样例，因此连乘式计算的概率值为0，无论其他属性上明显像好瓜，分类结果都是“好瓜=否”，这显然不合理。为了避免其他属性携带的信息被训练集中未出现的属性值“抹去”，在估计概率值时通常要进行“拉普拉斯修正”（Laplaciancorrection）令表示训练集中可能的类别数，表示第个属性可能的取值数，则式(7.16)和(7.17)分别修正为现实任务中，朴素贝叶斯分类器的使用情形：速度要求高，“查表”；任务数据更替频繁，“懒惰学习”(lazylearning)；数据不断增加，增量学习等等。章节目录贝叶斯决策论极大似然估计朴素贝叶斯分类器半朴素贝叶斯分类器贝叶斯网EM算法半朴素贝叶斯分类器为了降低贝叶斯公式中估计后验概率的困难，朴素贝叶斯分类器采用的属性条件独立性假设；对属性条件独立假设进行一定程度的放松，由此产生了一类称为“半朴素贝叶斯分类器”(semi-naïveBayesclassifiers)半朴素贝叶斯分类器为了降低贝叶斯公式中估计后验概率的困难，朴素贝叶斯分类器采用的属性条件独立性假设；对属性条件独立假设记性一定程度的放松，由此产生了一类称为“半朴素贝叶斯分类器”(semi-naïveBayesclassifiers)半朴素贝叶斯分类器最常用的一种策略：“独依赖估计”(One-DependentEstimator,简称ODE)，假设每个属性在类别之外最多仅依赖一个其他属性，即其中为属性所依赖的属性，称为的父属性对每个属性，若其父属性已知，则可估计概值，于是问题的关键转化为如何确定每个属性的父属性SPODE最直接的做法是假设所有属性都依赖于同一属性，称为“超父”(super-parenet)，然后通过交叉验证等模型选择方法来确定超父属性，由此形成了SPODE(Super-ParentODE)方法。图7.1朴素贝叶斯分类器与两种半朴素分类器所考虑的属性依赖关系在图7.1(b)中，是超父属性。TANTAN(TreeaugmentedNaïveBayes)[Friedmanetal.,1997]则在最大带权生成树(Maximumweightedspanningtree)算法[ChowandLiu,1968]的基础上，通过以下步骤将属性间依赖关系简约为图7.1(c)。计算任意两个属性之间的条件互信息(CMI：conditionalmutualinformation)以属性为结点构建完全图，任意两个结点之间边的权重设为构建此完全图的最大带权生成树以每个属性为节点(nodenode)，CMI为边(edgeedge)形成一张图。找到这张图的最大带权生成树。即找到一个节点之间的连接规则，这个规则满足三个条件：1.能够连接所有节点；2.使用最少数目的边；3.边长(CMI)总和最大最大带权生成树再把节点连接关系设置为有向，即从父节点指向子节点。在这里把最先出现的属性设置为根节点，再由根节点出发来确定边的方向TANTAN(TreeaugmentedNaïveBayes)[Friedmanetal.,1997]则在最大带权生成树(Maximumweightedspanningtree)算法[ChowandLiu,1968]的基础上，通过以下步骤将属性间依赖关系简约为图7.1(c)。计算任意两个属性之间的条件互信息(conditionalmutualinformation)以属性为结点构建完全图，任意两个结点之间边的权重设为构建此完全图的最大带权生成树，挑选根变量，将边设为有向；加入类别节点y，增加从y到每个属性的有向边。AODEAODE(AveragedOne-DependentEstimator)[Webbetal.2005]是一种基于集成学习机制、且更为强大的分类器。尝试将每个属性作为超父构建SPODE---共d个将具有足够训练数据支撑的SPODE集群起来作为最终结果其中，是在第个属性上取值的样本的集合，为阈值常数其中，是在第个属性上取值数，是类别为且在第个属性上取值为的样本集合，是类别为且在第i个属性上取值，第j个属性上取值为的样本集合,,ijcxxDjx章节目录贝叶斯决策论极大似然