贝叶斯分类器ppt课件

贝叶斯分类器,贝叶斯定理,每个记录用一个d维特征向量X=(x1,x2,xd)表示假定有k个类y1,y2,yk.给定X,X属于yj类的后验概率P(yj|X)满足贝叶斯(Bayes)定理MAP(maximumposteriorihypothesis,最大后验假设)将X指派到具有最大后验概率P(yj|X)的类yj，即将X指派到P(X|yj)P(yj)最大的类yj,2,朴素贝叶斯分类,3,朴素贝叶斯分类(NaveBayesClassifier)工作原理给定一个未知的数据样本X,分类法将预测X属于具有最高后验概率的类.即,未知的样本分配给类yj,当且仅当根据贝叶斯定理,我们有由于P(X)对于所有类为常数,只需要最大化P(X|yj)P(yj)即可.,朴素贝叶斯分类(续),4,估计P(yj)类yj的先验概率可以用P(yj)=nj/n估计其中,nj是类yj中的训练样本数,而n是训练样本总数估计P(X|yj)为便于估计P(X|yj),假定类条件独立-给定样本的类标号,假定属性值条件地相互独立.于是,P(X|Y=yj)可以用下式估计其中,P(x|yj)可以由训练样本估值,朴素贝叶斯分类(续),5,估计P(xi|yj)设第i个属性Ai是分类属性,则P(xi|yj)=nij/nj其中nij是在属性Ai上具有值xi的yj类的训练样本数,而nj是yj类的训练样本数设第i个属性Ai是连续值属性把Ai离散化假定Ai服从高斯分布其中,ij,ij分别为给定yj类的训练样本在属性Ai上的均值和标准差,朴素贝叶斯分类器所需要的信息计算每个类的先验概率P(yj):P(yj)=nj/n其中,nj是yi类的训练样本数,而n是训练样本总数对于离散属性Ai，设的不同值为ai1,ai2,ail，对于每个类yj，计算后验概率P(aik|yj),1klP(aik|yj)=nikj/nj其中nikj是在属性Ai上具有值aik的yj类的训练样本数,而nj是yj类的训练样本数对于连续属性Ai和每个类yj，计算yj类样本的均值ij,标准差ij,朴素贝叶斯分类,6,贝叶斯分类器:例,例:,7,P(Yes)=3/10P(No)=7/10P(有房=是|No)=3/7P(有房=否|No)=4/7P(有房=是|Yes)=0P(有房=否|Yes)=1P(婚姻状况=单身|No)=2/7P(婚姻状况=离婚|No)=1/7P(婚姻状况=已婚|No)=4/7P(婚姻状况=单身|Yes)=2/3P(婚姻状况=离婚|Yes)=1/3P(婚姻状况=已婚|Yes)=0年收入：类=No：样本均值=110样本方差=2975类=Yes：样本均值=90样本方差=25,HowtoEstimateProbabilitiesfromData?,Normaldistribution:Oneforeach(Ai,ci)pairFor(年收入,Class=No):IfClass=No样本均值=110样本方差=2975,X=（有房=否，婚姻状况=已婚，年收入=$120K）计算P(X|No)和P(X|Yes)P(X|No)=P(有房=否|No)P(婚姻状况=已婚|No)P(年收入=$120K|No)=4/74/70.0072=0.0024P(X|Yes)=P(有房=否|Yes)P(婚姻状况=已婚|Yes)P(年收入=$120K|Yes)=101.2109=0计算P(X|No)P(No)和P(X|Yes)P(Yes)P(X|No)P(No)=0.00240.7=0.00168P(X|Yes)P(Yes)=00.3=0因为P(X|No)P(No)P(X|Yes)P(Yes),所以X分类为No,贝叶斯分类器:例(续),9,贝叶斯分类器,10,问题如果诸条件概率P(Xi=xi|Y=yj)中的一个为0，则它们的乘积（计算P(X|Y=yj)的表达式）为0很可能每个P(X|Y=yj)都为0解决方法使用m估计、Laplace估计:原估计:P(Xi=xi|Y=yj)=nij/nj,ExampleofNaveBayesClassifier,A:attributesM:mammalsN:non-mammals,P(A|M)P(M)P(A|N)P(N)=Mammals,P128数据,对孤立的噪声点的鲁棒性个别点对概率估计的影响很小容易处理缺失值在估计概率时忽略缺失值的训练实例对不相关属性的鲁棒性各类在不相关属性上具有类似分布类条件独立假设可能不成立使用其他技术，如贝叶斯信念网络（BayesianBeliefNetworks，BBN）,贝叶斯分类器的特点,12,贝叶斯误差率,贝叶斯分类器最小化分类误差的概率贝叶斯分类使决策边界总是位于高斯分布下两类1和2的交叉点上,13,类C2类C1,案例：检测SNS社区中不真实账号,对于SNS社区来说，不真实账号（使用虚假身份或用户的小号）是一个普遍存在的问题，作为SNS社区的运营商，希望可以检测出这些不真实账号，从而在一些运营分析报告中避免这些账号的干扰，亦可以加强对SNS社区的了解与监管。将社区中所有账号在真实账号和不真实账号两个类别设C=0表示真实账号，C=1表示不真实账号。,14,1、确定特征属性及划分区分真实账号与不真实账号的特征属性，在实际应用中，特征属性的数量是很多的，划分也会比较细致为了简单起见，用少量的特征属性以及较粗的划分，并对数据做了修改。,15,选择三个特征属性：a1：日志数量/注册天数a2：好友数量/注册天数a3：是否使用真实头像。在SNS社区中这三项均可直接从数据库里得到或计算出来的。下面给出划分：a1：a=0.2，a2：a=0.8，a3：a=0（不是）,a=1（是）。,16,2、获取训练样本使用运维人员曾经人工检测过的1万个账号作为训练样本。3、计算训练样本中每个类别的频率用训练样本中真实账号和不真实账号数量分别除以一万，得到：,17,4、计算每个类别条件下各个特征属性划分的频率,18,5、使用分类器进行鉴别使用上面训练得到的分类器鉴别一个账号，这个账号使用非真实头像，日志数量与注册天数的比率为0.1，好友数与注册天数的比率为0.2。可以看到，虽然这个用户没有使用真实头像，但是通过分类器的鉴别，更倾向于将此账号归入真实账号类别。这个例子也展示了当特征属性充分多时，朴素贝叶斯分类对个别属性的抗干扰性。,19,贝叶斯信念网络(Bayesianbeliefnetwork)允许在变量的子集间定义类条件独立性因果关系图模型表示变量之间的依赖给出联合概率分布的说明图示结点:随机变量弧:依赖X,Y是Z的父节点/前驱,并且Y是P的父节点/前驱Z和P之间没有依赖关系,图中没有环,贝叶斯信念网络,20,贝叶斯信念网络:例,21,变量LungCance(LC)值的条件概率表(CPT),给出其双亲结点FamilyHistory和Smoke的每个可能值的组合的条件概率,给出了LungCancer的CPT.对于其双亲值的每个可能组合,表中给出了LungCancer的每个值的条件概率.例如,由左上角和右下角,分别看到：P(LungCancer=“yes”|FamilyHistory=“yes”,Smoker=“yes”)=0.8P(LungCancer=“no”|FamilyHistory=“no”,Smoker=“no”)=0.9,22,23,对应于属性或变量Z1,Zn的任意元组(z1,zn)的联合概率由下式计算其中,P(zi|parents(zi)的值对应于Zi的CPT中的表目,若干情况给定网络结构和所有可观测变量只需要学习CPT网络结构已知,而某些变量是隐藏的使用梯度下降法或类似于神经网络的方法训练信念网络网络结构未知,所有的变量可以观测搜索模型空间,构造网络拓扑结构网络结构未知,所有变量是隐藏的没有已知的好算法D.Heckerman,Bayesiannetworksfordatamining,训练贝叶斯信念网络,24,梯度下降法设S是s个训练样本X1,X2,.,Xs的集合,wijk是具有双亲Ui=uik的变量Y=yij的CPT项wijk可以看作权,类似于神经网络中隐藏单元的权.权的集合记作w这些权被初始化为随机概率值.梯度下降策略采用贪心爬山法.在每次迭代中,修改这些权,并最终收敛到一个局部最优解基于w的每个可能设置都等可能的假定,该方法搜索能最好地对数据建模wijk值.目标是最大化,训练贝叶斯信念网络,25,使用BBN进行推理举例,26,E:锻炼,D:饮食,HD:心脏病,Hb:胸口痛,BP:血压,CP:胸痛,通过计算先验概率P(HD=Yes)和P(HD=No)来确定一个人是否可能患心脏病设Yes,No表示锻炼的两个值，健康,不健康表示饮食的两个值，由全概率公式P(HD=Yes)=0.250.70.25+0.450.70.75+0.550.30.25+0.750.30.75=0.49因为P(HD=No)=1P(HD=Yes)=0.51，所以，此人不得心脏病的机率略微大一点,情况一：没有先验信息,27,P(HD=Yes)=0.250.70.25+0.450.70.75+0.550.30.25+0.750.30.75=0.49,P(HD=Yes),28,情况二：高血压,29,如果一个人有高血压，可以通过比较后验概率P(HD=Yes|BP=高)和P(HD=No|BP=高)来诊断他是否患有心脏病先用全概率公式，计算P(BP=高)P(BP=高)=0.850.49+0.20.51=0.5185其中Yes,No用贝叶斯公式计算此人患心脏病的后验概率,情况三,30,高血压、饮食健康、经常锻炼身体患心脏病的后验概率饮食健康、经常锻炼身体，可以降低患心脏病的风险,BBN提供了一种用图形模型来捕获特定领域的先验知识的方法。网络还可以用来对变量间的因果依赖关系进行编码构造网络可能既费时又费力。然而，一旦网络结构确定下来，添加新变量就十分容易贝叶斯网络很适合处理不完整的数据。对有属性遗漏的实例可以通过对该属性的所有可能取值的概率求和或求积分来加以处理因为数据和先验知识以概率的方式结合起来了，所以该方法对模型的过分拟合问题是非常鲁棒的,BBN的特点,31,训练贝叶斯信念网络:梯度下降法,32,给定网络结构和wijk的初值,该算法按以下步骤处理计算梯度：对每个i,j,k，计算沿梯度方向前进一小步:用下式更新权值l是表示步长的学习率,设置为一个小常数重新规格化权值：由于权值wijk是概率值,它们必须在0.0和1.0之间,并且对于所有的i,k，必须有,补充：梯度下降法简介,33,梯度下降法又称最速下降法。函数J(a)在某点ak的梯度是一个向量，其方向是J(a)增长最快的方向。显然，负梯度方向是J(a)减少最快的方向。在梯度下降法中，求某函数极大值时，沿着梯度方向走，可以最快达到极大点；反之，沿着负梯度方向走，则最快地达到极小点。参考：P461,34,求函数J(a)极小值的问题，可以选择任意初始点a0,从a0出发沿着负梯度方向走，可使得J(a)下降最快。s(0)：点a0的搜索方向。,35,对于任意点ak，可以定义ak点的负梯度搜索方向的单位向量为:从ak点出发，沿着方向走一步，步长为,得到新点ak+1,表示为：,因此，在新点ak+1，函数J(a)的函数值为：所有的ak组