北方工业大学_数据仓库挖掘7Bayes分类方法

数据仓库与数据挖掘技术第7章其它分类方法主要内容Bayes分类基于实例的分类集成方法Bayes分类器一个用于解决分类问题的概率框架条件概率:Bayes定理:)()()|()|(APCPCAPACP)(),()|()(),()|(CPCAPCAPAPCAPACPBayes定理举例给定:•50%的脑膜炎患者脖子僵硬•人得脑膜炎的概率是1/50,000•脖子僵硬的人的概率是1/20若某个患者脖子僵硬,则他患脑膜炎的概率是多少?0002.020/150000/15.0)()()|()|(SPMPMSPSMPBayes分类器将每个属性及类别标记视为随机变量给定一个具有属性集合(A1,A2,…,An)的记录•目标是预测类别属性C•具体而言，要寻找使得P(C|A1,A2,…,An)最大的类别CBayes分类器方法:•利用Bayes定理计算所有类别C的后验概率P(C|A1,A2,…,An)•选择使如下概率值最大的类别CP(C|A1,A2,…,An)•等价于使如下概率值最大P(A1,A2,…,An|C)P(C))()()|()|(212121nnnAAAPCPCAAAPAAACP朴素Bayes分类器假定给定类别的条件下属性Ai之间是独立的:•P(A1,A2,…,An|C)=P(A1|C)P(A2|C)…P(An|C)•可以从Ai和C中估算出P(Ai|C)•类别为使P(Cj)P(Ai|Cj)最大的类Cj如何从数据中估算概率类:P(C)=Nc/N•e.g.,P(No)=7/10,P(Yes)=3/10对离散属性k:P(Ai|Ck)=|Aik|/Nc•其中|Aik|是属于类Ck，并具有属性值Ai的记录数量•如:P(Status=Married|No)=4/7P(Refund=Yes|Yes)=0TidRefundMaritalStatusTaxableIncomeEvade1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10categoricalcategoricalcontinuousclass如何从数据中估算概率对连续属性:•将区间离散化至不同的桶•违背了独立性假设•2路分割:(Av)或(A≥v)•概率密度估计:•假设属性的取值服从正态分布•使用已有数据来估算分布的参数(如,均值和方差)•若概率分布已知，则使用其来估算条件概率P(Ai|c)如何从数据中估算概率正态分布:对(Income,Class=No):•若Class=No•samplemean=110•samplevariance=2975TidRefundMaritalStatusTaxableIncomeEvade1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10categoricalcategoricalcontinuousclass222)(221)|(ijijiAijjiecAP0072.0)54.54(21)|120()2975(2)110120(2eNoIncomeP朴素Bayes分类举例P(Refund=Yes|No)=3/7P(Refund=No|No)=4/7P(Refund=Yes|Yes)=0P(Refund=No|Yes)=1P(MaritalStatus=Single|No)=2/7P(MaritalStatus=Divorced|No)=1/7P(MaritalStatus=Married|No)=4/7P(MaritalStatus=Single|Yes)=2/7P(MaritalStatus=Divorced|Yes)=1/7P(MaritalStatus=Married|Yes)=0Fortaxableincome:Ifclass=No:samplemean=110samplevariance=2975Ifclass=Yes:samplemean=90samplevariance=25naiveBayesClassifier:120K)IncomeMarried,No,Refund(XP(X|Class=No)=P(Refund=No|Class=No)P(Married|Class=No)P(Income=120K|Class=No)=4/74/70.0072=0.0024P(X|Class=Yes)=P(Refund=No|Class=Yes)P(Married|Class=Yes)P(Income=120K|Class=Yes)=101.210-9=0SinceP(X|No)P(No)P(X|Yes)P(Yes)ThereforeP(No|X)P(Yes|X)=Class=No给定一条测试记录:朴素Bayes分类举例NameGiveBirthCanFlyLiveinWaterHaveLegsClasshumanyesnonoyesmammalspythonnononononon-mammalssalmonnonoyesnonon-mammalswhaleyesnoyesnomammalsfrognonosometimesyesnon-mammalskomodonononoyesnon-mammalsbatyesyesnoyesmammalspigeonnoyesnoyesnon-mammalscatyesnonoyesmammalsleopardsharkyesnoyesnonon-mammalsturtlenonosometimesyesnon-mammalspenguinnonosometimesyesnon-mammalsporcupineyesnonoyesmammalseelnonoyesnonon-mammalssalamandernonosometimesyesnon-mammalsgilamonsternononoyesnon-mammalsplatypusnononoyesmammalsowlnoyesnoyesnon-mammalsdolphinyesnoyesnomammalseaglenoyesnoyesnon-mammalsGiveBirthCanFlyLiveinWaterHaveLegsClassyesnoyesno?0027.02013004.0)()|(021.020706.0)()|(0042.01341331310131)|(06.072727676)|(NPNAPMPMAPNAPMAPA:attributesM:mammalsN:non-mammalsP(A|M)P(M)P(A|N)P(N)=Mammals朴素Bayes分类器小结抗噪声能力强在概率估算阶段，通过忽略整条记录来处理缺失值抗无关属性的能力强属性独立的假设可能对某些属性不成立•可以使用Bayes信度网络(BayesianBeliefNetworks,BBN)Bayes网络20世纪80年代，Bayes网络(BayesNetwork)成功应用于专家系统，成为表示不确定性专家知识和推理的一种流行的方法。•在不确定性表示、可信度计算上还是使用概率方法。•实现时，要根据应用背景采用近似计算方法。事件的独立性独立：如果X与Y相互独立，则P(X,Y)=P(X)P(Y)P(X|Y)=P(X)条件独立：如果在给定Z的条件下，X与Y相互独立，则P(X|Y,Z)=P(X|Z)实际中，条件独立比完全独立更普遍联合概率联合概率：P(X1,X2,…,XN)如果相互独立：P(X1,X2,…,XN)=P(X1)P(X2)…P(XN)条件概率：P(X1,X2,…,XN)=P(X1|X2,…,XN)P(X2,…,XN)迭代表示：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)实际应用中就是利用条件独立来简化网络。Bayes网络一系列变量的联合概率分布的图形表示。一个表示变量之间相互依赖关系的数据结构，图论与概率论的结合。Bayes网络（续）两部分•结构图，有向无环图(DirectedAcyclicGraph,DAG)，每个节点代表相应的变量。•条件概率表(ConditionalProbabilityTable,CPT)，一系列的概率值，表示局部条件概率分布，即P(node|parents)。Bayes网络的构造选择变量，生成节点从左至右（从上到下），排列节点填充网络连接弧，表示节点之间的关系得到条件概率关系表条件概率表示的概率网络有时叫“BeliefNets”由Bayes网络计算概率简单的联合概率可以直接从网络关系上得到，如：P(X,Y,Z)=P(X)P(Y)P(Z|X,Y)XZYP(X)P(Z|Y,X)P(Y)Bayes网络举例假设：命题S(Smoker)：该患者是一个吸烟者命题C(CoalMiner)：该患者是一个煤矿矿井工人命题L(LungCancer)：他患了肺癌命题E(Emphysema)：他患了肺气肿已知：S对L和E有因果影响，C对E也有因果影响。命题间的关系可以描绘成Bayes网络。•每个节点代表一个证据•每一条弧代表一条规则（假设）•弧表达了由规则给出的、节点间的直接因果关系。Bayes网络举例CPT表为：P(S)=0.4P(C)=0.3P(E|S,C)=0.9P(E|S,~C)=0.3P(E|~S,C)=0.5P(E|~S,~C)=0.1SCELP(S)=0.4P(C)=0.3P(E|S,C)=0.9Bayes网络举例（续）上图例中的联合概率密度为变量与它在图中的非继承节点在是概率独立的。•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条件下独立)简化后的联合概率密度为:)(*)|(*),|(*),,|(),,,(SPSCPCSLPLCSEPELCSP)(*)(*)|(*),|(),,,(SPCPSLPCSEPELCSPBayes网络的推理主要用于因果推理和诊断推理•由因导果，P(肺癌|吸烟)•执果索因，P(吸烟|肺癌)一般情况下是很困难的，原因•不是所有的CPT表都能够得到•网络结构大且复杂，NP-hard问题Bayes网络的因果推理已知父节点，计算子节点的条件概率。主要操作：•重新表达所求的条件概率。•直到所有的概率值可从CPT中得到，推理完成。因果推理举例给定患者是一个吸烟者(S)，计算他患肺气肿(E)的概率P(E|S)。首先，引入E的另一个父节点(C)，P(E|S)=P(E,C|S)+P(E,~C|S)右边的第一项，P(E,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.48Bayes网络的诊断推理在Bayes网中，从一个子节点出发