贝叶斯分类器贝叶斯定理每个记录用一个d 维特征向量X = (x1, x2, , xd)表示假定有k 个类 y1, y2, , yk.给定X, X属于yj 类的后验概率P(yj|X) 满足贝叶斯( Bayes)定理MAP (maximum posteriori hypothesis, 最大后验假设)将X指派到具有最大后验概率P(yj|X)的类yj，即将X指派到P(X|yj)P(yj) 最大的类yj2朴素贝叶斯分类3朴素贝叶斯分类 (Nave Bayes Classifier)工作原理给定一个未知的数据样本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), 1 k l P(aik|yj)= nikj/nj其中nikj 是在属性Ai上具有值aik 的yj类的训练样本数, 而nj是yj类的训练样本数 对于连续属性Ai 和每个类yj，计算yj类样本的均值ij,标准差ij朴素贝叶斯分类6贝叶斯分类器:例例:Tid有房有房婚姻状况婚姻状况年收入年收入拖欠贷款拖欠贷款12345678910是是否否否否是是否否否否是是否否否否否否单身单身已婚已婚单身单身已婚已婚离婚离婚已婚已婚离婚离婚单身单身已婚已婚单身单身125K100K70K120K95K60K220K85K75K90KNoNoNoNoYesNoNoYesNoYes7P(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 样本方差样本方差=25HowtoEstimateProbabilitiesfromData?Normal distribution:One for each (Ai,ci) pairFor (年收入, Class=No):If Class=No 样本均值= 110 样本方差= 2975Tid有有房房婚姻婚姻状况状况年收年收入入拖欠拖欠贷款贷款12345678910是是否否否否是是否否否否是是否否否否否否单身单身已婚已婚单身单身已婚已婚离婚离婚已婚已婚离婚离婚单身单身已婚已婚单身单身125K100K70K120K95K60K220K85K75K90KNoNoNoNoYesNoNoYesNoYesX=（有房=否，婚姻状况=已婚，年收入=$120K）计算P(X| No)和P(X| Yes) P(X| No) = P(有房有房=否否|No) P(婚姻状况婚姻状况=已婚已婚|No) P(年收入年收入= $120K|No) = 4/7 4/7 P(X|Yes) = P(有房有房=否否|Yes) P(婚姻状况婚姻状况=已婚已婚|Yes) P(年收入年收入=$120K|Yes) =1 010 9 = 0 计算P(X| No)P(No)和P(X| Yes)P(Yes) P(X| No)P(No)=0.0024 P(X| Yes)P(Yes)=0 0.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/njExampleofNaveBayesClassifierA: attributesM: mammalsN: non-mammalsP(A|M)P(M) P(A|N)P(N)= MammalsP128数据对孤立的噪声点的鲁棒性个别点对概率估计的影响很小容易处理缺失值在估计概率时忽略缺失值的训练实例对不相关属性的鲁棒性各类在不相关属性上具有类似分布类条件独立假设可能不成立 使用其他技术，如贝叶斯信念网络（ Bayesian Belief Networks，BBN）贝叶斯分类器的特点12贝叶斯误差率贝叶斯分类器最小化分类误差的概率贝叶斯分类使决策边界总是位于高斯分布下两类1和2的交叉点上13类类C2 类类C1案例：检测检测SNS社区中不真实账号社区中不真实账号对于SNS社区来说，不真实账号（使用虚假身份或用户的小号）是一个普遍存在的问题，作为SNS社区的运营商，希望可以检测出这些不真实账号，从而在一些运营分析报告中避免这些账号的干扰，亦可以加强对SNS社区的了解与监管。将社区中所有账号在真实账号和不真实账号两个类别设C=0表示真实账号，C=1表示不真实账号。141、确定特征属性及划分区分真实账号与不真实账号的特征属性，在实际应用中，特征属性的数量是很多的，划分也会比较细致为了简单起见，用少量的特征属性以及较粗的划分，并对数据做了修改。15选择三个特征属性：a1：日志数量/注册天数a2：好友数量/注册天数a3：是否使用真实头像。在SNS社区中这三项均可直接从数据库里得到或计算出来的。下面给出划分：a1：a=0.05,0.05a=0.2，a2：a=0.1,0.1a=0.8，a3：a=0（不是）,a=1（是）。162、获取训练样本使用运维人员曾经人工检测过的1万个账号作为训练样本。3、计算训练样本中每个类别的频率用训练样本中真实账号和不真实账号数量分别除以一万，得到：174、计算每个类别条件下各个特征属性划分的频率185、使用分类器进行鉴别使用上面训练得到的分类器鉴别一个账号，这个账号使用非真实头像，日志数量与注册天数的比率为，好友数与注册天数的比率为。可以看到，虽然这个用户没有使用真实头像，但是通过分类器的鉴别，更倾向于将此账号归入真实账号类别。这个例子也展示了当特征属性充分多时，朴素贝叶斯分类对个别属性的抗干扰性。19贝叶斯信念网络(Bayesian belief network)允许在变量的子集间定义类条件独立性 因果关系图模型 表示变量之间的依赖给出联合概率分布的说明图示结点: 随机变量弧: 依赖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.8 P(LungCancer = “no” | FamilyHistory = “no”, Smoker = “no”) = 0.9 2223对应于属性或变量Z1,Zn的任意元组(z1,zn)的联合概率由下式计算其中,P(zi | parents(zi)的值对应于Zi的CPT中的表目若干情况给定网络结构和所有可观测变量只需要学习CPT网络结构已知,而某些变量是隐藏的使用梯度下降法或类似于神经网络的方法训练信念网络网络结构未知, 所有的变量可以观测搜索模型空间, 构造网络拓扑结构网络结构未知, 所有变量是隐藏的没有已知的好算法D. Heckerman, Bayesian networks for data mining训练贝叶斯信念网络24梯度下降法设S是s个训练样本X1 ,X2 ,.,Xs的集合, wijk是具有双亲Ui = uik的变量Y = yij的CPT项 wijk可以看作权,类似于神经网络中隐藏单元的权. 权的集合记作w 这些权被初始化为随机概率值.梯度下降策略采用贪心爬山法. 在每次迭代中, 修改这些权, 并最终收敛到一个局部最优解 基于w的每个可能设置都等可能的假定,该方法搜索能最好地对数据建模wijk值.目标是最大化 训练贝叶斯信念网络25使用BBN进行推理举例26E:锻炼,D:饮食,HD:心脏病,Hb:胸口痛,BP:血压,CP:胸痛锻炼饮食心口痛心脏病血压胸痛D=健康D=健康D=不健康健康不健康健康不健康BP=高通过计算先验概率P(HD=Yes)和P(HD=No)来确定一个人是否可能患心脏病 设Yes, No表示锻炼的两个值，健康, 不健康表示饮食的两个值，由全概率公式 P(HD=Yes) = = 因为P(HD=No) =1P(HD=Yes) = ，所以，此人不得心脏病的机率略微大一点 情况一：没有先验信息27P(HD=Yes) = =P(HD=Yes)28锻炼饮食心口痛心脏病血压胸痛D=健康D=健康D=不健康健康不健康健康不健康BP=高情况二：高血压29如果一个人有高血压，可以通过比较后验概率P(HD=Yes|BP=高)和P(HD=No|BP=高)来诊断他是否患有心脏病 先用全概率公式，计算P(BP=高) P(BP =高) =其中Yes, No 用贝叶斯公式计算此人患心脏病的后验概率情况三30高血压、饮食健康、经常锻炼身体患心脏病的后验概率饮食健康、经常锻炼身体，可以降低患心脏病的风险BBN提供了一种用图形模型来捕获特定领域的先验知识的方法。网络还可以用来对变量间的因果依赖关系进行编码构造网络可能既费时又费力。然而，一旦网络结构确定下来，添加新变量就十分容易贝叶斯网络很适合处理不完整的数据。对有属性遗漏的实例可以通过对该属性的所有可能取值的概率求和或求积分来加以处理因为数据和先验知识以概率的方式结合起来了，所以该方法对模型的过分拟合问题是非常鲁棒的BBN的特点31训练贝叶斯信念网络:梯度下降法32给定网络结构和wijk的初值,该算法按以下步骤处理 1.计算梯度：对每个i, j, k，计算 2.沿梯度方向前进一小步:用下式更新权值 l是表示步长的学习率,设置为一个小常数 3.重新规格化权值：由于权值wijk是概率值,它们必须在和之间,并且对于所有的i,k，必须有 补充：梯度下降法简介33梯度下降法又称最速下降法。函数梯度下降法又称最速下降法。函数J(a)在某点在某点ak的梯度的梯度 是一个向量，其方向是是一个向量，其方向是J(a)增长最快的方向。显增长最快的方向。显然，负梯度方向是然，负梯度方向是J(a)减少最快的方向。减少最快的方向。在梯度下降法中，在梯度下降法中，求某函数极大值时，沿着梯度方向求某函数极大值时，沿着梯度方向走，可以最快达到极大点走，可以最快达到极大点；反之，沿着负梯度方向走，；反之，沿着负梯度方向走，则最快地达到极小点。则最快地达到极小点。 参考：参考：P4613435对于任意点对于任意点ak，可以定义，可以定义ak点的负梯度搜索方向的单位点的负梯度搜索方向的单位向量为向量为: 从从ak点出发，沿着点出发，沿着 方向走一步，步长为方向走一步，步长为 ,得到新得到新点点ak+1,表示为：表示为：因此，在新点因此，在新点ak+1，函数函数J(a)的函数值的函数值为：为：所有的所有的ak组成一个序列，该序列由迭代算法生成组成一个序列，该序列由迭代算法生成 a0, a1, a2, . , ak, ak+1, .该序列在一定条件下收敛于使得该序列在一定条件下收敛于使得J(a)最小的解最小的解a*迭代算法公式：迭代算法公式：迭代算法公式：迭代算法公式：关键问题：如何设计步关键问题：如何设计步 长长如果选得太小，则算法收敛慢，如果选得太大，如果选得太小，则算法收敛慢，如果选得太大， 可能会可能会导致发散。导致发散。 梯度法的迭代过程：梯度法的迭代过程：1)选取初始点选取初始点a0，给定允许误差，给定允许误差0,0,并令并令k=0。2)计算负梯度计算负梯度 及其单位向量及其单位向量 。3)检查是否满足条件检查是否满足条件 ，若满足则转，若满足则转8，否则继续。，否则继续。4)计算最佳步长计算最佳步长 。5)令：令：6)计算并检验另一判据：计算并检验另一判据： ，满足转，满足转8，否则继续。否则继续。7)令令k=k+1,转转2。8)输出结果，结束。输出结果，结束。梯度下降法：简单例子40