分类和预测贝叶斯网络

第四章分类和预测主讲教师：魏宏喜（博士，副教授）E-mail: cswhxI第四章分类和预测 4.1分类和预测的定义 4.2数据分类方法决策树神经网络 SVM贝叶斯网络 4.3数据预测方法线性回归非线性回归3贝叶斯网络贝叶斯网络（Bayesian Network）是20世纪80 年代发展起来白勺，由Judea Pearl（朱迪亚佩 尔）于1986年提岀。贝叶斯网络起源于贝叶斯统计分析理论， 它是概率论和图论相结合的产物。贝叶斯网络是一种描述不确定性知识和推 理问题的方法。文本分类（如：垃圾邮件的过滤）医学诊断贝叶斯网络 1、引例 2、贝叶斯概率基础 3、贝叶斯网络概述 4、贝叶斯网络的预测、诊断和训练 4.1贝叶斯网络的预测 4.2贝叶斯网络的诊断 4.3贝叶斯网络的训练贝叶斯网络 1、引例 2、贝叶斯概率基础 3、贝叶斯网络概述 4、贝叶斯网络的预测、诊断和训练 4.1贝叶斯网络的预测 4.2贝叶斯网络的诊断4.3贝叶斯网络的训练71、引例一个有关概率推理的例子。图中有六个结点：参加晚会(Party, PT)宿醉(Hangover, HO)头疼(Headache, HA)患脑瘤(Brain tumor, BT)HeadacheSmell Alcohol J ( Pos XrayBrain TumorPartyHangover有酒精味(Smell alcohol, SA) X射线检查呈阳性(Pos Xray, PX)1、引例一个有关概率推理的例子。图中有五条连线: PTTHO HOTSA HOTHA BTTHAETTPX1、引例参加晚会后，第二 天呼吸中有酒精味 的可能性有多大？如果头疼，患脑瘤 的概率有多大？如果参加了晚会， 并且头疼，那么患 脑瘤的概率有多大 ?这些问题都可通过贝叶斯网络加以解决。贝叶斯网络 1、引例2、贝叶斯概率基础 3、贝叶斯网络概述 4、贝叶斯网络的预测、诊断和训练 4.1贝叶斯网络的预测 4.2贝叶斯网络的诊断 4.3贝叶斯网络的训练2、贝叶斯概率基础先验概率：根据历史资料或主观判断所确 定的各种事件发生的概率。先验概率可分为两类:客观先验概率：是指利用过去的历史资料计算得到的概率（如：在自然语言处理中，从语料库中统计词语的出现频率客观先验概率）；主观先验概率：是指在无历史资料或历史资料不全的时候，只能凭借人们的主观经验来判断取得的概率。152、贝叶斯概率基础后验概率：是指利用贝叶斯公式，结合调 查等方式获取了新的附加信息，对先验概 率修正后得到的更符合实际的概率。条件概率：是指当条件事件发生后该事 件菠生的概率。P(AI B)二 P(B I A)P(A)/P(B)条件概率的计算可以通过两个事件各自发生的概率，以及相反方向的条件概率得到。例：已知任意时刻阴天的概率为0.3,记为 P(A)二0.3,下雨的概率为0.2,记为P(B)=0.2 o阴天之后下雨的概率为0.6,记为条件概 率P(BIA)=0.6o那么在下雨的条件下，是阴 天的概率是多少？【解】根据条件概率公式，可得：P(AIB) = P(BIA)*P(A)/P(B)=0.6*0.3/02= 0.9全概率公式设眄丿2,，久是两两互斥的事件，且 P(jBj)0, i =1, 2,，n，Bx+l?2+.,+l?n=/2o另有一事件人二的 + 化+ABn1=1172、贝叶斯概率基础192、贝叶斯概率基础全概率公式可看成是“由原因推结果”，即:每个原因对结果的发生有一定“作用 ”,结果发生的可能性与各种原因的“作用”大小有关。全概率公式表达了它们之间的关系。#2、贝叶斯概率基础贝叶斯公式(后验概率公式)设先验概率为尸(坊)，调查所获的新附加信息为P(AQ)(E，2,加，则贝叶斯公式 计賢的后盛概率为：I A) = P(BJP(A| Bt.)Rp(Bz.)P(A| BJ /i=该公式于1763年由贝叶斯(Bayes)导出。该公式是在观察到事件A已发生的条件下，寻 找导致4发生的每个原因的概率。212、贝叶斯概率基础例：某电子设备厂所用的元件由三家元件 厂提供，根据以往记录，这三个厂家的次 品率分别为0.02, 0.01和0.03,提供元件的 份额分别为0.15, 0.8和0.05,设这三家的 产品在仓库是均匀混合的，且无区别的标O问题1：在仓库中，随机抽取一个元件，求它 是次品的概率；问题2：在仓库中，随机抽取一个元件，若已 知它是次品，则该次品来自三家供货商的概率 分别是多少？【解】设A表示“取到的元件是次品”，B1 表示“取到的元件是由第i个厂家生产的” ,则P(BJ二0.15, P(B2)=0.8, P(B3)=0.05对于问题1,由全概率公式可得：P(A) = P(Bi)*P(AIBJ + P(B2)*P(AIB2)+ P(B3)*P(AIB3)=0.15*0.02+0.8*0.01+0.05*0.03= 0.0125232、贝叶斯概率基础【解】设A表示“取到的元件是次品”，B1 表示“取到的元件是由第i个厂家生产的” ,则P(BJ二0.15, P(B2)=0.8, P(B3)=0.05对于问题2,由贝叶斯公式可得：PCBJA) = P(B)*P(AIBJ/P(A)二 0.15*0.02/0.0125 二 0.24P(B2IA) = P(B2)*P(AIB2)/P(A)= 0.8*0.01/0.0125 = 0.64P(B3IA) = P(B3)*P(AIB3)/P(A)贝叶斯网络 1、引例 2、贝叶斯概率基础 3、贝叶斯网络概述 4、贝叶斯网络的预测、诊断和训练 4.1贝叶斯网络的预测 4.2贝叶斯网络的诊断4.3贝叶斯网络的训练273、贝叶斯网络概述贝叶斯网络是描述随机变量（事件）之间 依赖关系的一种图形模式，是一种可用来 进行推理的模型。贝叶斯网络通过有向图的形式来表示随机 变量间的因果关系，并通过条件概率将这293、贝叶斯网络概述一个贝叶斯网络由网络结构和条件概率表 两部分组成。网络结构是一个有向无环图，由若干结点和 有向弧组成。每个结点代表一个事件或者随机变量，变量 值可以是连续的或者离散的，但结点的取值 必须是完备互斥的。结点之间的有向弧代表随机变量间的因果关 系（概率依赖关系），有向弧的起始结点表不 原因，有向弧的终止结点表示结果。一个贝叶斯网络由网络结构和条件概率表 两部分组成。条件概率表：是指网络中的每个结点都有一 个条件概率表，用于表示其父结点对该结点的 影响。当网络中的某个结点没有父结点时，该结点 的条件概率表就是该结点的先验概率。313、贝叶斯网络概述#3、贝叶斯网络概述AP(M)t0.70f0.30333、贝叶斯网络概述贝叶斯网络的3个重要议题：贝叶斯网络预测：是指已知一定的原因，禾U用 贝叶斯网络进行计算，求出由原因导致结果的 概率。口贝叶斯网络诊断：是指已知发生了某些结果， 根据贝叶斯网络推理岀造成该结果发生的原因 以及发生的概率。贝叶斯网络学习（训练）：是指利用现有数据对 先验知识进行修正的过程，每一次学习都对贝 叶斯网络的先验概率进行调整，使得新的贝叶 斯网络更能反映数据中所蕴含的知识。#贝叶斯网络 1、引例 2、贝叶斯概率基础 3、贝叶斯网络概述 4、贝叶斯网络的预测、诊断和训练 4.1贝叶斯网络的预测 4.2贝叶斯网络的诊断 4.3贝叶斯网络的训练4、贝叶斯网络的预测、诊断和训练此处将以下图为例，分别介绍贝叶斯网络 的预测、诊断和训练。训练需要先建立 网络结构，再计 算每个结点的条 件概率表。预测和诊断需要 已知网络结构和 中每个结点的条 件概率表。4、贝叶斯网络的预测、诊断和训练为了使用贝叶斯网络进行预测和诊断，假设网络 已经训练好，即：网络中的所有先验概率和条件 概率全部已知。图中Party和Brain Tumor两个结点是原因结点，没有连线以它们为终点。它们的无条件概率如下表所示:P(PT)P(BT)True0.2000.001False0.8000.999该表中给出了这两个事件发生的概率：PT发生的概率 是0.2,不发生的概率是0& BT发生的概率是0.001, 不发生的概率是0.999。4、贝叶斯网络的预测、诊断和训练另外，网络中的条件概率如下所示：P(H0|PT)PT=TruePT=FalseTrue0. 7000False0. 3001. 000P (SA| HO)H0=TrueHO二FalseTrue0. 8000. 100False0. 2000. 900P (PX1BT)BT=TrueBT=FalseTrue0. 9800. 010False0. 0200. 9904、贝叶斯网络的预测、诊断和训练另外，网络中的条件概率如下所示：P (HA | HO, BT)HO二TrueHO=FalseBT=TrueBT=FalseBT=TrueBT=FalseTrue0. 9900. 7000. 9000. 020False0. 0100. 3000. 1000. 980贝叶斯网络 1、引例 2、贝叶斯概率基础 3、贝叶斯网络概述 4、贝叶斯网络的预测、诊断和训练 4.1贝叶斯网络的预测 4.2贝叶斯网络的诊断4.3贝叶斯网络的训练414.1贝叶斯网络的预测对于贝叶斯网络的预测，可分为以下两种 情况：在已知某些原因结点的情况下，可以预测结果 结点的概率。例：参加晚会情况下，头疼发生的概率。在不知任何结点信息的情况下，可以预测网络 中某个结果结点发生的概率。例：即使不知道任何结点发生与否的信息， 仍然可以计算结点HA发生的概率。贝叶斯网络的预测是一个“自顶向下”的 过程。为了描述方便，对于任何一个结点Point: P(+Point)表示Point发生的概率P(-Point)表示Point不发生的概率434.1贝叶斯网络的预测例1：计算结点HA的概率。454.1贝叶斯网络的预测例1：计算结点HA的概率。【解】根据全概率公式，可得P(+HA) = P(+BT)P(+HO)*0.99 +P(+BT)P(-HO)*0.9 +P(-BT)P(+HO)*0.7 +P(-BT)P(-H0)*0.02= 0.116P (HA | HO, BT)H0=TrueBT=True BT=FalseH0=False BT=True BT=FalseTrue0. 9900. 7000. 9000. 020False0. 0100. 3000. 1000. 980344.1贝叶斯网络的预测例1：计算结点HA的概率。【解】根据全概率公式，可得P(-HA) = 1 -P(+HA) = 0.884【解释】在没有任何诱因的情况下，头疼发 生的概率是0.116,不头疼的概率是0.884。采用上述方式，可以计算贝叶斯网络中所有 结点的概率一一这个过程通常发生在贝叶斯 网络的训练阶段获得结点的概率。例2：计算已知参加晚会的情况下，第二天 早晨呼吸有酒精味的概率。Smell Alcohol ) ( Pos Xray例2：计算已知参加晚会的情况下，第二天 早晨呼吸有酒精味的概率。【解】首先,根据下表可知，当PT发生的 情况下，HO发生的概率为0.7, HO不发生 的概率为0.3。P (H01PT)PT=TruePT=FalseTrue0. 7000False0. 3001. 000例2：计算已知参加晚会的情况下，第二天 早晨呼吸有酒精味的概率。【解】再根据全概率公式，可得P(+SA) = P(+HO)P(+SAI+HO) + P(-HO)P(+SAI-HO)= 0.7*0.8 4-0.3*0.1= 0.59P (SA| HO)H0=TrueH0=FalseTrue0. 8000. 100False0. 2000. 900534.1贝叶斯网络的预测预测算法输入：给定贝叶斯网络B (包括网络结构m个结点以及某些结 点间的连线、原因结点到中间结点的条件概率或联合条件概率 ),给定若干个原因结点发生与否的事实向量F (或者称为证 据向量)；给定待预测的某个结点仁输出：结点t发生的概率。(1) 把证据向量输入到贝叶斯网络B中；(2) 对于B中的每一个没处理过的结点n,如果它具有发生的事 实(证据)，则标记它为已经处理过；否则继续下面的步骤；(3) 如果它的所有父结点中有一个没有处理过，则不处理这个 结点；否则，继续下面的步骤；(4) 根据结点n的所有父结点的概率以及条件概率或联合条件概 率计算结点n的概率分布，并把结点n标记为已处理；(5) 重复步骤(2) (4)共m次。此时，结点t的概率分布就是 它的发生/不发生的概率。算法结束。贝叶斯网络 1、引例 2、贝叶斯概率基础 3、贝叶斯网络概述 4、贝叶斯网络的预测、诊断和训练 4.1贝叶斯网络的预测 4.2贝叶斯网络的诊断4.3贝叶斯网络的训练554.2贝叶斯网络的诊断例1：计算已知X光检查呈阳性的情况下，患脑瘤的概率。贝叶斯网络的诊断与贝叶斯网络的预测正好相反，即：它是在已知结果结点发生的 情况下，来推断条件结点发生的概率。贝叶斯网络的诊断是一个“自底向上”的 过程。594.2贝叶斯网络的诊断例1：计算已知X光检查呈阳性的情况下，患脑瘤的概率。【解】根据条件概率公式，可得P(+BT I +PX) = P(+PX I +ET)*P(+BT)/P(+PX)=0.98*0.001/P(+PX)P(PXIBnrBT=TrueBT=FalseTrue0.9800.010False0.0200.990P(PT)P(BT)True0.2000.001False0.8000.9994.2贝叶斯网络的诊断例1：计算已知X光检查呈阳性的情况下，患脑瘤的概率。614.2贝叶斯网络的诊断例1：计算已知X光检查呈阳性的情况下，患脑瘤的概率。【解】根据全概率公式，可得P(+PX)=P(+PXI+BT)*P(+BT)+P(+PXIBT)*P(-BT)P(PXIBBT=TrueBT=False0.9800.010False0.0200.990=0.980*0.001+0.010*0.999 0.011P(PT)P(BT)True0.2000.001False0.8000.999#4.2贝叶斯网络的诊断例1：计算已知X光检查呈阳性的情况下，患脑瘤的概率。【解】根据条件概率公式，可得P(+BT I +PX) = P(+PX I +BT)*P(+BT)/P(+PX)=098*OOO1/P(+PX)=0.98*0.001/0.011u 0.089【解释】当X光检查呈阳性的情况下，患脑 瘤的概率是0.089 (概率是较低的)。634.2贝叶斯网络的诊断例2：计算已知头疼的情况下，患脑瘤的概 率。例2：计算已知头疼的情况下，患脑瘤的概 率。【解】由条件概率公式，可得P(+BT I +HA) = P(+HA I +ET)*P(+BT)/P(+HA)在上面的公式中，P(+BT)的概率已知，P(+HA) 的概率可由全概率公式计算得到，P(+HAI+BT) 的概率也需要计算得到。65例2：计算已知头疼的情况下，患脑瘤的概 率。【解】由全概率公式，可得P(+HA) = P(+BT)P(+H0)*0.990 +P(+BT)P(-H0)*0.900 +P(-BT)P(+H0)*0.700 +P(-BT)P(-H0)*0.020 = 0.116P (HA | HO, BT)H0=TrueH0=FalseBT二TrueBT二FalseBT=TrueBT=FalseTrue0. 9900. 7000. 9000. 020False0. 0100. 3000. 1000. 9804$4.2贝叶斯网络的诊断例2：计算已知头疼的情况下，患脑瘤的概 率。【解】再由全概率公式，可得P(+HAI+BT) = P(+HO)*P(+HA I +BT, +HO)+ P(-HO)*P(+HA I +BT, -HO)口在这个公式中，只有P(+HO)和P(-HO)未知。因 此由全概率公式可得：P(+HO)二P(+HOI+PT)*P(+PT)+P(+HOI-PT)*P(-PT)P(H0|S)P 瞬 FalseTrueue0.001 0False FalseoQ關0099九00049例2：计算已知头疼的情况下，患脑瘤的概 率。【解】再由全概率公式，可得P(+HAI+BT) = P(+HO)*P(+HA I +BT, +HO)+ P(-HO)*P(+HA I +BT, -HO)口在这个公式中，只有P(+HO)和P(-HO)未知。因 此由全概率公式可得：P(+HO)二P(+HOI+PT)*P(+PT)+P(+HOI-PT)*P(-PT)=0.7*0.2 + 0*0.8= 0.14P(-HO) = 1 - P(+HO) = 1 -0.14 = 0.86so4.2贝叶斯网络的诊断例2：计算已知头疼的情况下，患脑瘤的概 率。【解】再由全概率公式，可得P(+HAI+BT) = P(+HO)*P(+HA I +BT, +HO)+ P(-HO)*P(+HA I +BT, -HO)= 0.14*0.99 + 0.86*0.9u 0.913例2：计算已知头疼的情况下，患脑瘤的概 率。【解】将上述求得的P(+HAI+BT)二0.913和 P(+HA)=0.116代入所求的条件概率公式中 可得：P(+BT I +HA) = P(+HA I +BT)*P(+BT)/P(+HA)二 0.913*0.001/0.116u 0.008【解释】与例1类似，在头疼的情况下，患 脑瘤的概率也是较低的(8%o) o714.2贝叶斯网络的诊断一诊断算法输入：给定贝叶斯网络B (包括网络结构in个结点以及某 些结点间的连线、原因结点到中间结点的条件概率或联 合条件概率)，给定若干个结果结点发生与否的事实向 量F (或暑称证搪向量)；给定待诊断的某个结点t。输出：结点t发生的概率。(1) 把证据向量输入到贝叶斯网络B中；(2) 对于B中的每一个没处理过的结点m如果它具有发生 的事实(证据)，则标记它为已经处理过；否则继续下 面的步骤；(3) 如果它的所有子结点中有一个没有处理过，则不处理 这个结点；否则，继续下面的步骤；(4) 根据节点n所有子结点的概率以及条件概率或联合条 件概務 根据杂仲概靠公我，计算结点n的概率分韦，并 把结点n标记为已处理；重复步骤(2)(4)共m次。此时，原因结点t的概 率分布就是它的发生/不发生的概率。算法结束。73贝叶斯网络 1、引例 2、贝叶斯概率基础 3、贝叶斯网络概述 4、贝叶斯网络的预测、诊断和训练 4.1贝叶斯网络的预测 4.2贝叶斯网络的诊断4.3贝叶斯网络的训练754.3贝叶斯网络的建立和训练贝叶斯网络的建立：首先，要把实际问题中的事件抽象为网络中的 结点；每个结点必须有明确的意义，至少有是、非 两个状态或者多个状态，并且这些状态在概 率意义上是完备的和互斥的。贝叶斯网络的建立：其次，在两个或多个结点之间的建立连线。基本原则：有明确因果关系的结点之间应建 立连线，没有明确因果关系的结点之间尽量 不要建立连线。可采用相关性分析方法（如：Pearson相关系数）来确定结点之间是否应该有连线。注意：在两个结点之间建立连线时，要防止环的出现，因为贝叶斯网络必须是无环图。贝叶斯网络的训练：是指通过历史数据获 得贝叶斯网络中各结点的概率以及结点之 间条件概率的过程。结点的概率（先验概率）假设结点P有m个状态P, P2,Pm,则结点P在 第i个状态下的概率P（PJ为：（）二片出现的数据条娄I A总的数据条数贝叶斯网络的训练：是指通过历史数据获 得贝叶斯网络中各结点的概率以及结点之 间条件概率的过程。结点间的条件概率假设PS表示结点P的一个状态，QS表示结点Q 的一个状态，贝UPS发生时，QS也发生的概率 P(QS I PS)为：nMcl ncA_ PS和0S共同发生的次数 丿一FS发生的次数贝叶斯网络的训练：是指通过历史数据获 得贝叶斯网络中各结点的概率以及结点之 间条件概率的过程。多个结点间的联合条件概率假设PS表示结点P的一个状态，QS表示结点Q 的一个状态，RS表示结点R的一个状态，贝LlPS 和QS发生时，RS也发生的概率P(RSIPS,QS)为:P(RSPS,QS) =FS,QS,RS共同发生的次数PS和QS共同发生的次数贝叶斯网络的训练：是指通过历史数据获 得贝叶斯网络中各结点的概率以及结点之 间条件概率的过程。多个结点间的联合条件概率假设PS表示结点P的一个状态，QS表示结点Q 的一个状态，RS表示结点R的一个状态，贝LlPS 和QS发生时，RS也发生的概率P(RSIPS,QS)为: 如果结点P、Q、R各有两个状态，则类似这 样的公式共有8个，它们共同构成了结点P、 Q到R的联合条件概率。81贝叶斯网络 1、引例 2、贝叶斯概率基础 3、贝叶斯网络概述 4、贝叶斯网络的预测、诊断和训练 4.1贝叶斯网络的预测 4.2贝叶斯网络的诊断 4.3贝叶斯网络的训练I第四章分类和预测 4.1分类和预测的定义 4.2数据分类方法决策树神经网络 SVM贝叶斯网络 4.3数据预测方法线性回归非线性回归83