数据挖掘与知识发现(讲稿11---贝叶斯网络)

数据挖掘与知识发现讲稿主讲：刘以安┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊1第11章贝叶斯网络贝叶斯网络是1986年由Pearl提出的，根据各个变量之间的概率关系，使用图论方法表示变量集合的联合概率分布的图形模型。它提供了一种自然的表示因果信息的方法，用来发现数据间的潜在关系。在这个网络中，用节点表示变量，有向边表示变量间的依赖关系。其特点有：贝叶斯理论给出了信任函数在数学上的计算方法，具有稳固的数学基础，同时刻画了信任度与证据的一致性以及信任度随证据而变化的增量学习特性；在数据挖掘中，贝叶斯网络可以处理不完整和带有噪声的数据集，它用概率测度的权重来描述数据间的相关性，从而解决了数据间的不一致性，甚至是相互独立的问题；用图形的方法描述数据间的相互关系，语义清晰、可理解性强，这有助于利用数据间的因果关系进行预测分析；11.1贝叶斯方法的基本观点贝叶斯分析方法的特点是使用概率去表示所有形式的不确定性。学习或其他形式的推理都是用概率规则来实现的。贝叶斯学习的结果表示为随机变量的概率分布，它可以解释为我们对不同可能性的信任程度。贝叶斯学派的起点是贝叶斯的两项工作：贝叶斯定理和贝叶斯假设。假设随机变量,x的联合分布密度是),(xp，它们的边际密度分别为)(),(pxp。设x是观测向量，是末知参数向量，则可通过观测向量来获得末知参数向量的估计。贝叶斯定理为：dxpxpxpxpxp)|()()|()()()|()()|(数据挖掘与知识发现讲稿主讲：刘以安┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊2这里，)(是的先验分布。上式可以看出，对末知参数向量的估计综合了它的先验信息和样本信息。而传统的参数估计方法只从样本数据获取信息，如最大似然估计。Bayesian方法对末知参数向量估计的一般过程为：将末知参数看成是随机变量；根据以往末知参数的知识，确定先验分布)(；计算后验分布密度，做出对末知参数的推断。贝叶斯假设：如果没有任何以往的知识来帮助确定)(，贝叶斯提出可以采用均匀分布作为其分布，即参数在它的变化范围内，取到各个值的机会是相同的。11.2贝叶斯网络的构造原理定义：贝叶斯网络是一个二元组B=G，P，其中①网络结构G=V，A是一个有向无环图，},,,{21nVVVV为结点集；A为弧的集合；②网络参数P中的每一个元素代表结点iV的条件概率密度；则由概率的链规则得niiinVVVVPVVVPVP112121),,,|(),,,()(对于n个离散二值随机变量，要确定它们的联合分布，需要给出12n个概率值。这当n较大时，巨大的存储要求往往难以满足。因此，一定的假设独立性是必要的。随机变量间的假设独立性原则使得贝叶斯网络所需定义的先验概率大为减少。联合概率分布由随机变量各自的分布的乘积所唯一确定。对于网络结构中的任一结点iV，必可找到一个与iV条件都不独立的最小子集},,,{121iiVVVU，使得数据挖掘与知识发现讲稿主讲：刘以安┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊3niiinUVPVVVPVP121)|(),,,()(贝叶斯网络是一种用图表示知识的方法，并且是可以计算的概率模型。通过这种网络，可以综合各种来源的数据，并对这些数据进行综合和推理。给定一个联合概率分布),,,(21nXXXP以及变量的一个排序d。将1X作为根结点开始，并赋予1X以先验概率分布)(1XP，然后用一结点表示2X，如果2X与1X有关，则从1X到2X建立一联结，并用)|(12XXP表示联结强度。如果2X与1X无关，则赋予2X以先验概率分布)(2XP。在第i级从iX的父结点集合iX，（},,,{121iXXXXi），画一组方向线联结到iX，并用)|(iXiXP条件概率定量表示，结果可以得到一个有向非循环图，可用于表示),,,(21nXXXP中所体现的许多独立关系，该图就称作贝叶斯网络。反过来，)|(iXiXP包含有重构原始分布函数所必需的所有信息，在排序d下，有如下关系：iXinnnnnniXPXPXXPXXXPXXXPXXXXPXXXP)|()()|(),|(),,|(),,,|(),,,(11221312112121[例如]下图是一个典型的贝叶斯网络，它的联合概率分布函数为)()|()|(),|(),|()|(),,,,,(1121312423556654321XPXXPXXPXXXPXXXPXXPXXXXXXP数据挖掘与知识发现讲稿主讲：刘以安┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊411.3贝叶斯网络在数据挖掘中的应用1）贝叶斯方法用于分类及回归分析分类规则发现是根据客体的特征向量值及其他约束条件，将其分到某个类别中。在数据挖掘中，主要研究如何从数据或经验中学习这些分类规则。对于分类问题，有些情况，输入特征向量唯一对应着一个类别，这种问题称为确定性的分类问题；而有些情况，会出现类别重叠现象，也就是说，来自于不同类别的样本从外观特征上具有极大的相似性，这时我们只能说某一类别的概率是多大，但我们必须为它选择一个类别。Bayesian学派采用两种处理方法：①选择后验概率最大的类别假设特征向量),,,(21mxxxX，类别向量),,,(21lcccC。分类的目的就是把特征向量X，归入到某个类别lici,,2,1,中。方法是：如果)|()|(xcPxcPji，则icx。此时取判别函数)|()(xcPxrii。可以证明，这种分类方法能够保证分类误差最小。②选择效用函数最大（或损失最小）的类别在决策理论中，经常采用平均效益的大小来衡量决策风险的大小，这实际上与不确定性的程度密切相关。假设)(XLij为把属于类别ic的特征向量X错误地划分到类别jc中所产生的损失，则可选择损失最小的类别，即})|()({min1ljjijixcPxL此时的判别函数：ljjijixcPxLxr1)|()()(。2）贝叶斯分类的应用文本过滤是一种重要的信息安全领域的应用。过滤的实质就是一种数据挖掘与知识发现讲稿主讲：刘以安┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊5分类，现讨论贝叶斯方法的文本过滤。用下式所示的矢量来表示文本内容：),;;,;,()(2211nniWTWTWTPD其中，iP---表示网页文本，iT---文本中的关键词，iW---关键词在网页文本iP中的权重，)(iPD即为文本iP所对应的矢量表示。令L---为合法网页集，I---非合法网页集。如果网页iP属于L的概率为))(|(iPDLP，属于I的概率为))(|(iPDIP，则显然有))(|(iPDLP+))(|(iPDIP=1由此，下列任一种计算结果都可以判断网页iP是否为非法网页：%50))(|(iPDLP%50))(|(iPDIP（1）))(|(iPDLP))(|(iPDIP但有时，如果将合法网页误判为非法网页的话，其严重性远大于非法网页的漏判。因此，上式需要加上一个调整量0。即%50))(|(iPDLP%50))(|(iPDIP（2）))(|(iPDLP))(|(iPDIP显然，在过滤计算的临界值附近的文本是自学习的重要样本，因此可将临界值附近的文本过滤结果根据领域专家的人工确认作为训练样本的正例集和反例集，并通过更正算法修改过滤模型和参数。另外，可根据贝叶斯定理，通过训练样本集预测未知样本的类别。))(()()|)(())(|(iiiPDPIPIPDPPDIP))(()()|)(())(|(iiiPDPLPLPDPPDLP（3）在上式（3）中，)(),(LPIP分别是文本属于非法文本集和合法文本集的先验概率，可通过下式（4）计算数据挖掘与知识发现讲稿主讲：刘以安┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊6||||||)(LIIIP||||||)(LILLP（4）矢量)(iPD中的关键词，可以看成文本iP的属性。因此，基于朴素贝叶斯方法的文本内容过滤的技术实质上是将文本进行贝叶斯分类（合法类和非合法类）。计算)|)((IPDPi和)|)((LPDPi的开销可能非常大，为了降低计算开销，可做类条件独立的朴素假定：给定样本的类标号，假定属性值相互条件独立，即在属性间不存在依赖关系。因此，条件概率)|)((IPDPi和)|)((LPDPi可根据下式简化计算：niiiITPIPDP1)|()|)((niiiLTPLPDP1)|()|)((（5）上式（5）中的各概率分量可基于训练样本集近似计算，具体计算方法为|||)(|)|(IITITPii|||)(|)|(LLTLTPii