数据挖掘技术十课Bayes分类方法课件.ppt

1、u朴素朴素Bayes分类分类uBayes网络网络u集成方法集成方法u一个用于解决分类问题的概率框架u条件概率:u Bayes定理:)()()|()|(APCPCAPACP)(),()|()(),()|(CPCAPCAPAPCAPACPu给定:50%的脑膜炎患者脖子僵硬 人得脑膜炎的概率是1/50,000 脖子僵硬的人的概率是 1/20u若某个患者脖子僵硬,则他患脑膜炎的概率是多少?0002.020/150000/15.0)()()|()|(SPMPMSPSMPu将每个属性及类别标记视为随机变量u给定一个具有属性集合(A1,A2,An)的记录 目标是预测类别属性C 具体而言，要寻找使得P(C|A

2、1,A2,An)最大的类别Cu方法:利用Bayes定理计算所有类别C的后验概率P(C|A1,A2,An)选择使如下概率值最大的类别C P(C|A1,A2,An)等价于使如下概率值最大 P(A1,A2,An|C)P(C)()()|()|(212121nnnAAAPCPCAAAPAAACPu假定给定类别的条件下属性Ai之间是独立的:P(A1,A2,An|C)=P(A1|Cj)P(A2|Cj)P(An|Cj)可以从Ai和Cj中估算出P(Ai|Cj)类别为使P(Cj)P(Ai|Cj)最大的类Cju类:P(C)=Nc/N e.g.,P(No)=7/10,P(Yes)=3/10u对离散属性k:P(Ai|C

3、k)=|Aik|/Nc 其中|Aik|是属于类Ck，并具有属性值Ai的记录数量 如:P(Status=Married|No)=4/7P(Refund=Yes|Yes)=0T id R e fu n d M a rita l S ta tu s T a x a b le In c o m e E va d e 1 Y e s S in g le 1 2 5 K N o 2 N o M a rrie d 1 0 0 K N o 3 N o S in g le 7 0 K N o 4 Y e s M a rrie d 1 2 0 K N o 5 N o D ivo rce d 9 5 K Y e s

4、 6 N o M a rrie d 6 0 K N o 7 Y e s D ivo rce d 2 2 0 K N o 8 N o S in g le 8 5 K Y e s 9 N o M a rrie d 7 5 K N o 1 0 N o S in g le 9 0 K Y e s 10 catego rica lcateg o rica lco ntin u ou sclassu对连续属性:将区间离散化至不同的桶 违背了独立性假设 2路分割:(A P(X|Yes)P(Yes)Therefore P(No|X)P(Yes|X)=Class=No给定一条测试记录:NameGive Birt

5、hCan FlyLive in WaterHave LegsClasshumanyesnonoyesmammalspythonnononononon-mammalssalmonnonoyesnonon-mammalswhaleyesnoyesnomammalsfrognonosometimes yesnon-mammalskomodonononoyesnon-mammalsbatyesyesnoyesmammalspigeonnoyesnoyesnon-mammalscatyesnonoyesmammalsleopard sharkyesnoyesnonon-mammalsturtlenono

6、sometimes yesnon-mammalspenguinnonosometimes yesnon-mammalsporcupineyesnonoyesmammalseelnonoyesnonon-mammalssalamandernonosometimes yesnon-mammalsgila monsternononoyesnon-mammalsplatypusnononoyesmammalsowlnoyesnoyesnon-mammalsdolphinyesnoyesnomammalseaglenoyesnoyesnon-mammalsGive BirthCan FlyLive in

7、 Water Have LegsClassyesnoyesno?0027.02013004.0)()|(021.020706.0)()|(0042.01341331310131)|(06.072727676)|(NPNAPMPMAPNAPMAPA:attributesM:mammalsN:non-mammalsP(A|M)P(M)P(A|N)P(N)=Mammalsu抗噪声能力强u在概率估算阶段，通过忽略整条记录来处理缺失值u抗无关属性的能力强u属性独立的假设可能对某些属性不成立 可以使用Bayes信度网络(Bayesian Belief Networks,BBN)u朴素朴素Bayes分类分类

8、uBayes网络网络u集成方法集成方法u20世纪80年代，Bayes网络(Bayes Network)成功应用于专家系统，成为表示不确定性专家知识和推理的一种流行的方法。在不确定性表示、可信度计算上还是使用概率方法。实现时，要根据应用背景采用近似计算方法。u独立：如果X与Y相互独立，则 P(X,Y)=P(X)P(Y)P(X|Y)=P(X)u条件独立：如果在给定Z的条件下，X与Y相互独立，则 P(X|Y,Z)=P(X|Z)u实际中，条件独立比完全独立更普遍u联合概率：P(X1,X2,XN)u如果相互独立：P(X1,X2,XN)=P(X1)P(X2)P(XN)u条件概率：P(X1,X2,XN)=P

9、(X1|X2,XN)P(X2,XN)u迭代表示：P(X1,X2,XN)=P(X1)P(X2|X1)P(X3|X2X1)P(XN|XN-1,X1)=P(XN)P(XN-1|XN)P(XN-2|XN-1XN)P(X1|X2,XN)u实际应用中就是利用条件独立来简化网络。u一系列变量的联合概率分布的图形表示。u一个表示变量之间相互依赖关系的数据结构，图论与概率论的结合。u两部分 结构图，有向无环图(Directed Acyclic Graph,DAG)，每个节点代表相应的变量。条件概率表(Conditional Probability Table,CPT)，一系列的概率值，表示局部条件概率分布，即P

10、(node|parents)。u选择变量，生成节点u从左至右（从上到下），排列节点u填充网络连接弧，表示节点之间的关系u得到条件概率关系表u条件概率表示的概率网络有时叫“Belief Nets”u简单的联合概率可以直接从网络关系上得到，如：uP(X,Y,Z)=P(X)P(Y)P(Z|X,Y)XZYP(X)P(Z|Y,X)P(Y)假设：命题S(Smoker)：该患者是一个吸烟者 命题C(Coal Miner)：该患者是一个煤矿矿井工人 命题L(Lung Cancer)：他患了肺癌 命题E(Emphysema)：他患了肺气肿u已知：S对L和E有因果影响，C对E也有因果影响。u命题间的关系可以描绘成

11、Bayes网络。每个节点代表一个证据 每一条弧代表一条规则（假设）弧表达了由规则给出的、节点间的直接因果关系。uCPT表为：P(S)=0.4 P(C)=0.3 P(E|S,C)=0.9 P(E|S,C)=0.3 P(E|S,C)=0.5 P(E|S,C)=0.1 SCELP(S)=0.4 P(C)=0.3P(E|S,C)=0.9u上图例中的联合概率密度为u变量与它在图中的非继承节点在是概率独立的。P(E|S,C,L)P(E|S,C)(E与L在S条件下独立)P(L|S,C)=P(L|S)(L与C在S,E条件下独立)P(C|S)=P(C)(C与S在E条件下独立)u简化后的联合概率密度为:)(*)|

12、(*),|(*),|(),(SPSCPCSLPLCSEPELCSP)(*)(*)|(*),|(),(SPCPSLPCSEPELCSPu主要用于因果推理和诊断推理 由因导果，P(肺癌|吸烟)执果索因，P(吸烟|肺癌)u一般情况下是很困难的，原因 不是所有的CPT表都能够得到 网络结构大且复杂，NP-hard问题u已知父节点，计算子节点的条件概率。u主要操作：重新表达所求的条件概率。直到所有的概率值可从CPT中得到，推理完成。u给定患者是一个吸烟者(S)，计算他患肺气肿(E)的概率P(E|S)。首先，引入E的另一个父节点(C)，P(E|S)=P(E,C|S)+P(E,C|S)右边的第一项，P(E,

13、C|S)P(E,C,S)/P(S)P(E|C,S)*P(C,S)/P(S)P(E|C,S)*P(C)同理可得右边的第二项为：P(E,C|S)=P(E|C,S)*P(C)。由此可得：P(E|S)=P(E|C,S)*P(C)+P(E|C,S)*P(C)P(C)=1 P(C)，则有：P(E|S)0.9*0.3+0.3*(1-0.3)=0.48u在Bayes网中，从一个子节点出发计算父节点的条件概率，即从结果推测起因。u主要操作：使用Bayes公式把诊断推理转换成因果推理。计算在不得肺气肿的人中，不是矿工的概率，即P(C|E)。P(C|E)=P(E|C)*P(C)/P(E)由因果推理可知：P(E|C)

14、=P(E,S|C)+P(E,S|C)=P(E|S,C)P(S)+P(E|S,C)P(S)=(10.3)*0.4+(10.1)*(10.4)=0.82由此得：P(C|E)=P(E|C)*P(C)/P(E)=0.82*(10.3)/P(E)=0.574/P(E)同样，P(C|E)=P(E|C)*P(C)/P(E)=0.102/P(E)由于全概率公式，P(C|E)+P(C|E)=1代入得，P(E)=0.676所以，P(C|E)=0.849World Cup Group C England beating Argentinahttp:/ 每个分类器具有同样的错误率=0.35 假定这些分类器是互相独立的

15、 则Ensemble方法出错的概率为:25132506.0)1(25iiiiu基本分类器相互独立u基本分类器的正确率优于随机猜测。u如何构造集成分类器 Bagging Boosting u给定S个样本。u在S中做有替代的抽样，其结果记为T，S中原来的样本在T中可出现多次，也可一次都不出现。u重复这种抽样，得到k个独立的训练集。u使用同样的算法在这些训练集上构建k个分类器C1,C2,Ck。u对一个待分类样本i，每个分类器都独立对其进行分类。u样本i的类别标记为大多数分类器给出的类别。u弱分类器:每个分类器的正确率都不高。uBoosting:顺序将弱分类器应用于不断修改的训练数据。u最终也是采用投票，类别取多数的原则。u最初，所有数据的权重都相等。u每次使用一个分类器对数据进行分类后，都相应修改数据的权重。在使用第m个分类器Cm对数据进行分类时，被Cm-1分错的数据的权重增加，分对的数据的权重降低。u每个分类器都关注于被前面的分类器所分错的数据。训练集的选择预测/分类函数的权重预测/分类函数的生成Bagging随机的，各轮训练集间相互独立无权重并行生成Boosting训练集不独立，各轮训练集的选择与前面的结果有关有权重顺序生成