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

数据仓库与数据挖掘技术第7章其它分类方法,主要内容,Bayes分类基于实例的分类集成方法,Bayes分类器,一个用于解决分类问题的概率框架条件概率:Bayes定理:,Bayes定理举例,给定:50%的脑膜炎患者脖子僵硬人得脑膜炎的概率是1/50,000脖子僵硬的人的概率是1/20若某个患者脖子僵硬,则他患脑膜炎的概率是多少?,Bayes分类器,将每个属性及类别标记视为随机变量给定一个具有属性集合(A1,A2,An)的记录目标是预测类别属性C具体而言，要寻找使得P(C|A1,A2,An)最大的类别C,Bayes分类器,方法:利用Bayes定理计算所有类别C的后验概率P(C|A1,A2,An)选择使如下概率值最大的类别CP(C|A1,A2,An)等价于使如下概率值最大P(A1,A2,An|C)P(C),朴素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/Ne.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)=0,如何从数据中估算概率,对连续属性:将区间离散化至不同的桶违背了独立性假设2路分割:(AP(X|Yes)P(Yes)ThereforeP(No|X)P(Yes|X)=Class=No,给定一条测试记录:,朴素Bayes分类举例,A:attributesM:mammalsN:non-mammals,P(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),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.1,Bayes网络举例（续）,上图例中的联合概率密度为变量与它在图中的非继承节点在是概率独立的。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条件下独立)简化后的联合概率密度为:,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)=1P(C)，则有：P(E|S)0.9*0.3+0.3*(1-0.3)=0.48,Bayes网络的诊断推理,在Bayes网中，从一个子节点出发计算父节点的条件概率，即从结果推测起因。主要操作：使用Bayes公式把诊断推理转换成因果推理。,诊断推理举例,计算在不得肺气肿的人中，不是矿工的概率，即P(C|E)。,P(C|E)=P(E|C)*P(C)/P(E)由因果推理可知：P(E|C)=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.849,Bayes方法预测2010世界杯,WorldCupGroupC,EnglandbeatingArgentina,2012图灵奖得主JudeaPearl,1937-加州大学洛杉矶分校（UCLA）的计算机科学教授将贝叶斯网络和概率方法引入人工智能的先驱之一数学化因果模型的先驱之一iPhone的Siri语音识别Google的无人驾驶汽车,主要内容,Bayes分类基于实例的分类集成方法,基于实例的分类（1）,存储训练记录使用训练记录来预测未知记录的类别,基于实例的分类（2）,例子:机械学习(Rote-learner)记住所有训练数据，只有当类别未知的记录与某训练记录的所有属性的值都匹配时，才对其分类。最近邻居(Nearestneighbor)用k个最临近点执行分类。,最近邻居分类（1）,基本思想:Ifitwalkslikeaduck,quackslikeaduck,thenitsprobablyaduck,最近邻居分类（2）,基本条件存储的训练实例实例间距离的度量方法确定K值,即邻居的数量对未知记录分类:计算与训练记录的距离确定最近的k个邻居使用k个邻居的类别对类别未知的数据进行分类(如投票),最近邻居的定义,记录x的k-最近邻居是指与x距离最近的k个数据点,距离的度量,计算两点间的距离:欧式距离(Euclideandistance)从最近邻居中确定类别从k个最近邻居中做投票，取多数根据距离确定不同点的权重w=1/d2,K值的确定,选择K的值:若K太小，则对噪声点敏感；若K太大，可能类别比较分散。,K-NN分类的特点,k-NN分类器是lazylearner与eagerlearner，如决策树、基于规则的分类，不同。不明确的构建分类模型。对类别未知的记录的分类代价较高。,PEBLS,PEBLS:ParallelExamplar-BasedLearningSystem(Cost&Salzberg,MachineLearning,1993)既适用于连续属性，也适用于名词性属性对名词性属性，其距离使用(ModifiedValueDifferenceMetric,MVDM)每条属性都被赋予一个权重最近邻居数量,k=1,Example:PEBLS,Distancebetweennominalattributevalues:d(Single,Married)=|2/40/4|+|2/44/4|=1d(Single,Divorced)=|2/41/2|+|2/41/2|=0d(Married,Divorced)=|0/41/2|+|4/41/2|=1d(Refund=Yes,Refund=No)=|0/33/7|+|3/34/7|=6/7,Example:PEBLS,DistancebetweenrecordXandrecordY:,where:,wX1ifXmakesaccuratepredictionmostofthetimewX1ifXisnotreliableformakingpredictions,主要内容,Bayes分类基于实例的分类集成方法,集成方法(Ensemble),从训练数据中构建一系列的分类器。使用多个分类器共同分类。,核心思想,为什么使用集成方法,假设有25个基本的2分类器每个分类器具有同样的错误率=0.35假定这些分类器是互相独立的则Ensemble方法出错的概率为:,集成方法优于单个分类器的条件,基本分类器相互独立基本分类器的正确率优于随机猜测。,常用的集成方法,如何构造集成分类器BaggingBoosting,Bagging:基本算法,给定S个样本。在S中做有替代的抽样，其结果记为T，S中原来的样本在T中可出现多次，也可一次都不出现。重复这种抽样，得到k个独立的训练集。使用同样的算法在这些训练集上构建k个分类器C1,C2,Ck。对一个待分类样本i，每个分类器都独立对其进