贝叶斯分类器讲课文档

贝叶斯分类器第1页，共40页。贝叶斯定理每个记录用一个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页，共40页。朴素贝叶斯分类朴素贝叶斯分类(NaïveBayesClassifier)工作原理给定一个未知的数据样本X,分类法将预测X属于具有最高后验概率的类.即,未知的样本分配给类yj,当且仅当 根据贝叶斯定理,我们有由于P(X)

对于所有类为常数,只需要最大化P(X|yj)P(yj)即可.3第3页，共40页。朴素贝叶斯分类(续)估计P(yj)类yj的先验概率可以用P(yj)=nj/n估计

其中,nj是类yj中的训练样本数,而n是训练样本总数估计P(X|yj)为便于估计P(X|yj),假定类条件独立----给定样本的类标号,假定属性值条件地相互独立.于是,P(X|Y=yj)可以用下式估计 其中,P(x|yj)可以由训练样本估值4第4页，共40页。朴素贝叶斯分类(续)估计P(xi|yj)设第i个属性Ai是分类属性,则

P(xi|yj)=nij/nj

其中nij是在属性Ai上具有值xi的yj类的训练样本数,而nj是yj类的训练样本数设第i个属性Ai是连续值属性把Ai离散化假定Ai服从高斯分布其中,

ij,

ij分别为给定yj类的训练样本在属性Ai上的均值和标准差5第5页，共40页。朴素贝叶斯分类器所需要的信息计算每个类的先验概率P(yj):P(yj)=nj/n

其中,nj是yi类的训练样本数,而n是训练样本总数对于离散属性Ai，设的不同值为ai1,ai2,…,ail

，对于每个类yj，计算后验概率P(aik|yj),1

k

lP(aik|yj)=nikj/nj其中nikj是在属性Ai上具有值aik

的yj类的训练样本数,而nj是yj类的训练样本数对于连续属性Ai

和每个类yj，计算yj类样本的均值

ij,标准差

ij朴素贝叶斯分类6第6页，共40页。贝叶斯分类器:例例:Tid有房婚姻状况年收入拖欠贷款12345678910是否否是否否是否否否单身已婚单身已婚离婚已婚离婚单身已婚单身125K100K70K120K95K60K220K85K75K90KNoNoNoNoYesNoNoYesNoYesP(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第7页，共40页。HowtoEstimateProbabilitiesfromData?Normaldistribution:Oneforeach(Ai,ci)pairFor(年收入,Class=No):IfClass=No

样本均值=110

样本方差=2975Tid有房婚姻状况年收入拖欠贷款12345678910是否否是否否是否否否单身已婚单身已婚离婚已婚离婚单身已婚单身125K100K70K120K95K60K220K85K75K90KNoNoNoNoYesNoNoYesNoYes第8页，共40页。X=（有房=否，婚姻状况=已婚，年收入=$120K）计算P(X|No)和P(X|Yes)

P(X|No)=P(有房=否|No)

P(婚姻状况=已婚|No)

P(年收入=$120K|No) =4/7

4/7

0.0072=0.0024P(X|Yes)=P(有房=否|Yes)

P(婚姻状况=已婚|Yes)

P(年收入=$120K|Yes) =1

0

1.2

10

9=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第9页，共40页。贝叶斯分类器问题如果诸条件概率P(Xi=xi|Y=yj)中的一个为0，则它们的乘积（计算P(X|Y=yj)的表达式）为0很可能每个P(X|Y=yj)都为0解决方法使用m估计、Laplace估计:

原估计:P(Xi=xi|Y=yj)=nij/nj10第10页，共40页。ExampleofNaïveBayesClassifierA:attributesM:mammalsN:non-mammalsP(A|M)P(M)>P(A|N)P(N)=>MammalsP128数据第11页，共40页。对孤立的噪声点的鲁棒性个别点对概率估计的影响很小容易处理缺失值在估计概率时忽略缺失值的训练实例对不相关属性的鲁棒性各类在不相关属性上具有类似分布类条件独立假设可能不成立使用其他技术，如贝叶斯信念网络（BayesianBeliefNetworks，BBN）贝叶斯分类器的特点12第12页，共40页。贝叶斯误差率贝叶斯分类器最小化分类误差的概率贝叶斯分类使决策边界总是位于高斯分布下两类1和2的交叉点上类C2类C113第13页，共40页。案例：检测SNS社区中不真实账号对于SNS社区来说，不真实账号（使用虚假身份或用户的小号）是一个普遍存在的问题，作为SNS社区的运营商，希望可以检测出这些不真实账号，从而在一些运营分析报告中避免这些账号的干扰，亦可以加强对SNS社区的了解与监管。

将社区中所有账号在真实账号和不真实账号两个类别设C=0表示真实账号，C=1表示不真实账号。14第14页，共40页。1、确定特征属性及划分区分真实账号与不真实账号的特征属性，在实际应用中，特征属性的数量是很多的，划分也会比较细致为了简单起见，用少量的特征属性以及较粗的划分，并对数据做了修改。15第15页，共40页。选择三个特征属性：a1：日志数量/注册天数a2：好友数量/注册天数a3：是否使用真实头像。在SNS社区中这三项均可直接从数据库里得到或计算出来的。下面给出划分：a1：{a<=0.05,0.05<a<0.2,a>=0.2}，a2：{a<=0.1,0.1<a<0.8,a>=0.8}，a3：{a=0（不是）,a=1（是）}。16第16页，共40页。

2、获取训练样本

使用运维人员曾经人工检测过的1万个账号作为训练样本。

3、计算训练样本中每个类别的频率

用训练样本中真实账号和不真实账号数量分别除以一万，得到：

17第17页，共40页。4、计算每个类别条件下各个特征属性划分的频率18第18页，共40页。

5、使用分类器进行鉴别使用上面训练得到的分类器鉴别一个账号，这个账号使用非真实头像，日志数量与注册天数的比率为0.1，好友数与注册天数的比率为0.2。可以看到，虽然这个用户没有使用真实头像，但是通过分类器的鉴别，更倾向于将此账号归入真实账号类别。这个例子也展示了当特征属性充分多时，朴素贝叶斯分类对个别属性的抗干扰性。19第19页，共40页。贝叶斯信念网络(Bayesianbeliefnetwork)允许在变量的子集间定义类条件独立性因果关系图模型表示变量之间的依赖给出联合概率分布的说明图示结点:随机变量弧:依赖X,Y

是Z的父节点/前驱,并且Y

是P的父节点/前驱Z

和P之间没有依赖关系,图中没有环贝叶斯信念网络20第20页，共40页。贝叶斯信念网络:例变量LungCance(LC)值的条件概率表(CPT),给出其双亲结点FamilyHistory和Smoke的每个可能值的组合的条件概率21第21页，共40页。给出了LungCancer的CPT.对于其双亲值的每个可能组合,表中给出了LungCancer的每个值的条件概率.例如,由左上角和右下角,分别看到：

P(LungCancer=“yes”|FamilyHistory=“yes”,Smoker=“yes”)=0.8 P(LungCancer=“no”|FamilyHistory=“no”,Smoker=“no”)=0.922第22页，共40页。对应于属性或变量Z1,…,Zn的任意元组(z1,…,zn)的联合概率由下式计算

其中,P(zi|parents(zi))的值对应于Zi的CPT中的表目23第23页，共40页。若干情况给定网络结构和所有可观测变量只需要学习CPT网络结构已知,而某些变量是隐藏的使用梯度下降法或类似于神经网络的方法训练信念网络网络结构未知,所有的变量可以观测搜索模型空间,构造网络拓扑结构网络结构未知,所有变量是隐藏的没有已知的好算法D.Heckerman,Bayesiannetworksfordatamining训练贝叶斯信念网络24第24页，共40页。梯度下降法设S是s个训练样本X1,X2,...,Xs的集合,wijk是具有双亲Ui=uik的变量Y=yij的CPT项wijk可以看作权,类似于神经网络中隐藏单元的权.权的集合记作w

这些权被初始化为随机概率值.梯度下降策略采用贪心爬山法.在每次迭代中,修改这些权,并最终收敛到一个局部最优解基于w的每个可能设置都等可能的假定,该方法搜索能最好地对数据建模wijk值.目标是最大化训练贝叶斯信念网络25第25页，共40页。使用BBN进行推理举例E:锻炼,D:饮食,HD:心脏病,Hb:胸口痛,BP:血压,CP:胸痛锻炼饮食心口痛心脏病血压胸痛D=健康D=健康D=不健康健康不健康健康不健康BP=高26第26页，共40页。通过计算先验概率P(HD=Yes)和P(HD=No)来确定一个人是否可能患心脏病设

∈{Yes,No}表示锻炼的两个值，

∈{健康,不健康}表示饮食的两个值，由全概率公式P(HD=Yes)=

= =0.25

0.7

0.25+0.45

0.7

0.75+0.55

0.3

0.25+0.75

0.3

0.75

=0.49因为P(HD=No)=1

P(HD=Yes)=0.51，所以，此人不得心脏病的机率略微大一点情况一：没有先验信息27第27页，共40页。P(HD=Yes)=

= =0.25

0.7

0.25+0.45

0.7

0.75+0.55

0.3

0.25+0.75

0.3

0.75 =0.49P(HD=Yes)锻炼饮食心口痛心脏病血压胸痛D=健康D=健康D=不健康健康不健康健康不健康BP=高28第28页，共40页。情况二：高血压如果一个人有高血压，可以通过比较后验概率P(HD=Yes|BP=高)和P(HD=No|BP=高)来诊断他是否患有心脏病先用全概率公式，计算P(BP=高)P(BP=高)= =0.85

0.49+0.2

0.51=0.5185其中{Yes,No}用贝叶斯公式计算此人患心脏病的后验概率29第29页，共40页。情况三高血压、饮食健康、经常锻炼身体患心脏病的后验概率饮食健康、经常锻炼身体，可以降低患心脏病的风险30第30页，共40页。BBN提供了一种用图形模型来捕获特定领域的先验知识的方法。网络还可以用来对变量间的因果依赖关系进行编码构造网络可能既费时又费力。然而，一旦网络结构确定下来，添加新变量就十分容易贝叶斯网络很适合处理不完整的数据。对有属性遗漏的实例可以通过对该属性的所有可能取值的概率求和或求积分来加以处理因为数据和先验知识以概率的方式结合起来了，所以该方法对模型的过分拟合问题是非常鲁棒的BBN的特点31第31页，共40页。训练贝叶斯信念网络:梯度下降法给定网络结构和wijk的初值,该算法按以下步骤处理计算梯度：对每个i,j,k，计算沿梯度方向前进一小步:用下式更新权值

l是表示步长的学习率,设置为一个小常数重新规格化权值：由于权值wijk是概率值,它们必须在0.0和1.0之间,并且对于所有的i,k，必须有32第32页，共40页。补充：梯度下降法简介梯度下降法又称最速下降法。函数J(a)在某点ak的梯度是一个向量，其方向是J(a)增长最快的方向。显然，负梯度方