1、数据挖掘分类之主讲人：软件学院 卢卫刚贝叶斯网络目录贝叶斯网络贝叶斯网络 2贝叶斯分类贝叶斯分类 1总结总结 4贝叶斯网络的应用及实例贝叶斯网络的应用及实例 3致谢致谢 51.1分类的基本概念1.2贝叶斯分类概述1.贝叶斯分类1.1分类的基本概念 近几十年来，Internet互联网的普及使得人们获得和存储数据的能力得到逐步的提高，数据规模不断壮大。面对“数据丰富而知识匮乏”的挑战，数据挖掘技术应运而生。数据挖掘是一门多学科的交叉领域，涉及统计学，机器学习、神经网络、模式识别、知识库系统、信息检索、高性能计算和可视化等学科。而数据挖掘中的分类技术是一项非常重要的技术。Q1 什么是分类 超市中的物
2、品分类 生活中的垃圾分类Q1 什么是分类 生活信息的分类由此可见，分类是跟我们的生活息息相关的东西，分类让生活更加有条理，更加精彩.Q1 什么是分类 分类就是把一些新的数据项映射到给定类别的中的某一个类别，比如说当我们发表一篇文章的时候，就可以自动的把这篇文章划分到某一个文章类别。分类也称为有监督学习(supervised learning),与之相对于的是无监督学习(unsupervised learning),比如聚类。分类与聚类的最大区别在于，分类数据中的一部分的类别是已知的，而聚类数据的类别未知。Q2 分类问题名称胎生 会飞水中生活有腿类别Human是否否是哺乳动物python否否否否
3、非哺乳动物salmon否否是否非哺乳动物whale是否是否哺乳动物frog否否有时是非哺乳动物komodo否否否是非哺乳动物bat是是否是哺乳动物pigeon否是否是非哺乳动物cat是否否是哺乳动物leopard_shark 是否是否非哺乳动物turtle否否有时是非哺乳动物penguin否否有时是非哺乳动物porcupine是否否是哺乳动物eel否否是否非哺乳动物salamander否否有时是非哺乳动物gila_monster否否否是非哺乳动物platypus否否否是哺乳动物owl否是否是非哺乳动物dolphin是否是否哺乳动物eagle否是否是非哺乳动物胎生会飞水中生活有腿类别是否是否？Q
4、2 分类问题税号去年退税婚姻状况可征税收入逃税1是单身125k否2否婚姻中100k否3否单身70k否4是婚姻中120k否5否离婚95k是6否婚姻中60k否7是离婚220k否8否单身85k是9否婚姻中75k否10否单身90k是(,120K)X 对于去年退税否 婚姻状况婚姻中可征税收入Q2 分类的流程 动物种动物种类类体型体型翅膀数翅膀数量量脚的只数脚的只数是否产是否产蛋蛋是否有毛是否有毛类别类别狗中04否是爬行动物猪大04否是爬行动物牛大04否是爬行动物麻雀小22是是鸟类天鹅中22是是鸟类大雁中22是是鸟类动物A大02是无？动物B中22否是？根据现有的知识，我们得到了一些关于爬行动物和鸟类的信息
5、，根据现有的知识，我们得到了一些关于爬行动物和鸟类的信息，我们能否对新发现的物种，比如动物我们能否对新发现的物种，比如动物A，动物，动物B进行分类？进行分类？动物种动物种类类体型体型翅膀数量翅膀数量脚的只数脚的只数是否产是否产蛋蛋是否有毛是否有毛类别类别狗中04否是爬行动物猪大04否是爬行动物牛大04否是爬行动物麻雀小22是是鸟类天鹅中22是是鸟类大雁中22是是鸟类 步骤一：将样本转化为等维的数据特征（特征提取）。所有样本必须具有相同数量的特征 兼顾特征的全面性和独立性Q2 分类的流程动物种动物种类类体型体型翅膀数量翅膀数量脚的只数脚的只数是否产是否产蛋蛋是否有毛是否有毛类别类别狗中0 04
6、4否否是爬行动物猪大0 04 4否否是爬行动物牛大0 04 4否否是爬行动物麻雀小2 22 2是是是鸟类天鹅中2 22 2是是是鸟类大雁中2 22 2是是是鸟类 步骤二：选择与类别相关的特征（特征选择）。比如，绿色代表与类别非常相关，黑色代表部分相关，灰色代表完全无关Q2 分类的流程 步骤三：建立分类模型或分类器（分类）。分类器通常可以看作一个函数，它把特征映射到类的空间上iiniiiyxxxxf),.,(321Q2 分类的流程Q3 分类的方法 对数据挖掘中心的可信技术分类算法的内容及其研究现状进行综述。认为分类算法大体可以分为传统分类算法传统分类算法和基于软件计算基于软件计算的分类法两类，主
7、要包括相似函数，关联规则分类算法，K近邻分类算法，决策树分类算法，贝叶斯分类算法和基于模糊逻辑，遗传算法，粗糙集和神经网络的分类算法。分类的算法有很多种，他们都有各自的优缺点和应用范围，本次我就贝叶斯分类算法展开我的演讲。1.2 贝叶斯分类概述 贝叶斯分类基于贝叶斯定理，贝叶斯定理是由18世纪概率论和决策论的早起研究者Thomas Bayes发明的，故用其名字命名为贝叶斯定理。分类算法的比较研究发现，一种称为朴素贝叶斯分类法的简单贝叶斯分类法可以与决策树和经过挑选的神经网络分类器相媲美。用于大型数据库，贝叶斯分类法也已表现出高准确率和高速度。目前研究较多的贝叶斯分类器主要有四种，分别是：Nai
8、ve Bayes、TAN、BAN和GBN。Thomas Bayes贝叶斯定理 贝叶斯定理贝叶斯定理（Bayes theorem）是概率论中的一个结果，它跟随机变量的条件概率以及边缘概率分布有关。在有些关于概率的解说中，贝叶斯定理能够告知我们如何利用新证据修改已有的看法。通常，事件A在事件B（发生）的条件下的概率，与事件B在事件A的条件下的概率是不一样的；然而，这两者是有确定的关系，贝叶斯定理就是这种关系的陈述。贝叶斯公式提供了从先验概率P(A)、P(B)和P(B|A)计算后验概率P(A|B)的方法：P(A|B)=P(B|A)*P(A)/P(B)，P(A|B)随着P(A)和P(B|A)的增长而增
9、长，随着P(B)的增长而减少，即如果B独立于A时被观察到的可能性越大，那么B对A的支持度越小。贝叶斯公式贝叶斯法则 机器学习的任务：在给定训练数据D时，确定假设空间H中的最佳假设。最佳假设：一种方法是把它定义为在给定数据D以及H中不同假设的先验概率的有关知识下的最可能假设最可能假设。贝叶斯理论提供了一种计算假设概率的方法，基于假设的先验概率、给定假设下观察到不同数据的概率以及观察到的数据本身。贝叶斯分类的原理 贝叶斯分类器的分类原理是通过某对象的先验概率，利用贝叶斯公式计算出其后验概率，即该对象属于某一类的概率，选择具有最大后验概率的类作为该对象所属的类。也就是说，贝叶斯分类器是最小错误率意义
10、上的优化。根据贝叶斯定理：根据贝叶斯定理：由于由于P(X)对于所有类为对于所有类为常数常数，只需要，只需要P(X|H)*P(H)最大即可。最大即可。)()()|()()()|(XPHPHXPXPXHPXHP 朴素贝叶斯 朴素贝叶斯分类是一种十分简单的分类算法，叫它朴素贝叶斯分类是因为这种方法的思想真的很朴素，朴素贝叶斯的思想基础是这样的：对于给出的待分类项，求解在此项出现的条件下各个类别出现的概率，哪个最大，就认为此待分类项属于哪个类别。通俗来说，就好比这么个道理，你在街上看到一个黑人，我问你你猜这哥们哪里来的，你十有八九猜非洲。为什么呢？因为黑人中非洲人的比率最高，当然人家也可能是美洲人或亚
11、洲人，但在没有其它可用信息下，我们会选择条件概率最大的类别，这就是朴素贝叶斯的思想基础。概率最大 第一阶段第一阶段准备工作阶段准备工作阶段，这个阶段的任务是为朴素贝叶斯分类做必要的准备，主要工作是根据具体情况确定特征属性，并对每个特征属性进行适当划分，然后由人工对一部分待分类项进行分类，形成训练样本集合。这一阶段的输入是所有待分类数据，输出是特征属性和训练样本。这一阶段是整个朴素贝叶斯分类中唯一需要人工完成的阶段，其质量对整个过程将有重要影响，分类器的质量很大程度上由特征属性、特征属性划分及训练样本质量决定。第二阶段第二阶段分类器训练阶段分类器训练阶段，这个阶段的任务就是生成分类器，主要工作是
12、计算每个类别在训练样本中的出现频率及每个特征属性划分对每个类别的条件概率估计，并将结果记录。其输入是特征属性和训练样本，输出是分类器。这一阶段是机械性阶段，根据前面讨论的公式可以由程序自动计算完成。第三阶段第三阶段应用阶段应用阶段。这个阶段的任务是使用分类器对待分类项进行分类，其输入是分类器和待分类项，输出是待分类项与类别的映射关系。这一阶段也是机械性阶段，由程序完成。朴素贝叶斯分类实例检测检测SNS社区中不真实账号社区中不真实账号 下面讨论一个使用朴素贝叶斯分类解决实际问题的例子。这个问题是这样的，对于SNS社区来说，不真实账号（使用虚假身份或用户的小号）是一个普遍存在的问题，作为SNS社区
13、的运营商，希望可以检测出这些不真实账号，从而在一些运营分析报告中避免这些账号的干扰，亦可以加强对SNS社区的了解与监管。如果通过纯人工检测，需要耗费大量的人力，效率也十分低下，如能引入自动检测机制，必将大大提升工作效率。这个问题说白了，就是要将社区中所有账号在真实账号和不真实账号两个类别上进行分类。下面我们一步一步实现这个过程。首先设C=0表示真实账号，C=1表示不真实账号。1、确定特征属性及划分、确定特征属性及划分 这一步要找出可以帮助我们区分真实账号与不真实账号的特征属性，在实际应用中，特征属性的数量是很多的，划分也会比较细致，但这里为了简单起见，我们用少量的特征属性以及较粗的划分，并对数
14、据做了修改。我们选择三个特征属性：a1：日志数量/注册天数 a2：好友数量/注册天数 a3：是否使用真实头像 在SNS社区中这三项都是可以直接从数据库里得到或计算出来的。下面给出划分：a1：a=0.05,0.05a=0.2 a2：a=0.1,0.1a=0.8 a3：a=0（不是）,a=1（是）2、获取训练样本、获取训练样本 这里使用运维人员曾经人工检测过的1万个账号作为训练样本。3、计算训练样本中每个类别的频率、计算训练样本中每个类别的频率 用训练样本中真实账号和不真实账号数量分别除以一万，得到：P(C=0)=8900/10000=0.89P(C=1)=1100/10000=0.11 4、计算
15、每个类别条件下各个特征属性划分的频率、计算每个类别条件下各个特征属性划分的频率P(a1=0.05|C=0)=0.3 P(a1=0.05|C=1)=0.8 P(0.05a10.2|C=0)=0.5 P(0.05a10.2|C=0)=0.2 P(a10.2|C=1)=0.1P(a2=0.1|C=0)=0.1 P(a2=0.1|C=1)=0.7P(0.1a20.8|C=0)=0.7 P(0.1a20.8|C=0)=0.2 P(a20.8|C=0)=0.1P(a3=0|C=0)=0.2 P(a3=1|C=0)=0.8 P(a3=0|C=1)=0.9 P(a3=1|C=1)=0.1 5、使用分类器进行鉴
16、别、使用分类器进行鉴别 下面我们使用上面训练得到的分类器鉴别一个账号，属性如下 a1:日志数量与注册天数的比率为0.1 a2:好友数与注册天数的比率为 0.2 a3:不使用真实头像 (a=0)P(C=0)P(x|C=0)=P(C=0)P(0.05a10.2|C=0)P(0.1a20.8|C=0)P(a3=0|C=0)=0.89*0.5*0.7*0.2=0.0623 P(C=1)P(x|C=1)=P(C=1)P(0.05a10.2|C=1)P(0.1a20.8|C=1)P(a3=0|C=1)=0.11*0.1*0.2*0.9=0.00198 可以看到，虽然这个用户没有使用真实头像，但是通过分类器
17、的鉴别，可以看到，虽然这个用户没有使用真实头像，但是通过分类器的鉴别，更倾向于将此账号归入真实账号类别。更倾向于将此账号归入真实账号类别。朴素贝叶斯模型朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以 及稳定的分类效率。同时，NBC模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。理论上，NBC模型与其他分类方法相比具有最小的误差率。但是朴素贝叶斯分类有一个限制条件，就是特征属性必须有条件独立或基本独立（实际上在现实应用中几乎不可能做到完全独立）。当这个条件成立时，朴素贝叶斯分类法的准确率是最高的，但不幸的是，现实中各个特征属性间往往并不条件独立，而是具有较强的相关性，这样就
18、限制了朴素贝叶斯分类的能力。于是诞生了一种更高级、应用范围更广的贝叶斯网络贝叶斯网络。2.1贝叶斯网络结构概述2.2贝叶斯网络学习2.贝叶斯网络2.3贝叶斯网络推理计算 在上一篇文章中我们讨论了朴素贝叶斯分类。这一篇文章中，我们接着上一篇文章的例子，讨论贝叶斯分类中更高级、应用范围更广的一种算法贝叶斯网络（又称贝叶斯信念网络或信念网络）。复杂的网络2.1贝叶斯网络概述 上一篇文章我们使用朴素贝叶斯分类实现了SNS社区中不真实账号的检测。在那个解决方案中，我做了如下假设：i、真实账号比非真实账号平均具有更大的日志密度、各大的好友密度以及更多的使用真实头像。ii、日志密度、好友密度和是否使用真实头
19、像在账号真实性给定的条件下是独立的。但是，上述第二条假设很可能并不成立。一般来说，好友密度除了与账号是否真实有关，还与是否有真实头像有关，因为真实的头像会吸引更多人加其为好友。因此，我们为了获取更准确的分类，可以将假设修改如下：i、真实账号比非真实账号平均具有更大的日志密度、各大的好友密度以及更多的使用真实头像。ii、日志密度与好友密度、日志密度与是否使用真实头像在账号真实性给定的条件下是独立的。iii、使用真实头像的用户比使用非真实头像的用户平均有更大的好友密度。上述假设更接近实际情况，但问题随之也来了，由于特征属性间存在依赖关系，使得朴素贝叶斯分类不适用了。既然这样，我去寻找另外的解决方案
20、。不确定性推理是人工智能研究的重要课题之一，从20世纪六七十年代以来，人们提出了许多方法，如概率方法（Nilsson,1965;Duda and Hart,1973）、非单调逻辑（Ginsberg,1987）、确定因子（Shortliffe and Buchhanan,1975）、Dempster-Shafer证据理论（Shafer,1976）、模糊逻辑（Zadeh,1965）等。在这些方法中，概率方法是最自然也是最早被尝试的方法之一，因为概率论本身是关于随机现象和不确定性的数学理论。下面我们来看一个使用概率方法进行不确定性推理的例子。（Alarm问题）Pearl教授家住在洛杉矶，那里地震和盗
21、窃时有发生，教授家里装有警铃，发生地震和盗窃都有可能触发警铃，他的两个邻居Mary和John听到警铃响后可能会打电话给他。一天，Pearl教授接到Mary的电话，说听到他家的警铃响了，Pearl教授想知道他家遭盗窃的概率有多大？贝叶斯网络的产生这个问题包含5个随机变量：盗窃（B）、地震（E）、警铃（A）、接到Mary的电话（M）、接到John的电话（J）；假设所有变量均取两个值：yes or no.这里各变量间的关系存在不确定性：盗窃和地震以一定的概率随机发生；它们发生后并不一定会触发警铃；而警铃响后，玛丽和琼可能会因为某些原因，如在听音乐或听力有问题等，而没有听到警铃；有时候两人也会将其他声
22、音误听为警铃声。因此这是一个不确定性推理问题。假设Pearl教授根据自己以往的经验对这5个变量的联合概率分布有如下的估计（如右图），从联合概率分布 出发，先计算边缘分布 BEAMJProbabilityynnyy1.2E-4ynnyn5.1E-5yynny5.7E-6yyynn8.5E-5yyyyy7.2E-6nnnyn9.1E-1nnnny2.6E-4nyynn7.0E-9nyyny1.3E-2nyyyn1.7E-4,(,)(,)E A JP B MP B E A J M(,)()()0.61P By MyP By MyP My 贝叶斯网络的产生从这个例子中我们可以看出，需要计算的联合概率分
23、布 上式包含 个参数，假设有n个二元变量，则需要的独立参数数目为：，所以，直接使用联合概率分布进行不确定性推理的计算复杂度很大，随着变量的个数呈指数级增长。因此，当变量很多时，联合概率的获取、存储和运算都变得相当困难。基于以下原因，从而产生了贝叶斯网络：全联合概率计算复杂性十分巨大现实需要一种自然、有效的方式来捕捉和推理不确定性知识变量之间的独立性和条件独立性可大大减少为了定义全联合概率分布所需的概率数目 贝叶斯网络的产生(,)P B E A J M52 1 31 21n贝叶斯网络的简介简介 贝叶斯网络是一种概率网络，它是基于概率推理的图形化网络，而贝叶斯公式则是这个概率网络的基础。贝叶斯网络
24、是基于概率推理的数学模型，所谓概率推理就是通过一些变量的信息来获取其他的概率信息的过程，基于概率推理的贝叶斯网络(Bayesian network)是为了解决不定性和不完整性问题而提出的，它对于解决复杂设备不确定性和关联性引起的故障有很的优势，在多个领域中获得广泛应用。贝叶斯网络又称信度网络，是Bayes方法的扩展，目前不确定知识表达和推理领域最有效的理论模型之一。从1988年由Pearl提出后，已经成为近几年来研究的热点.。贝叶斯网络的定义贝叶斯网络是一个二元组，即BN=(G,P),G=(V,E),为有向无圈图(Directed Acyclic Graph),其中V为节点集合，与领域的随机变
25、量一一对应，E为有向边集，反映节点变量之间的因果依赖关系；P为节点的概率分布，表示节点之间因果影响强度从定性和定量两个角度来理解在定性层面：贝叶斯网络是一个有向无圈图，其中的节点代表随机变量，节点之间的边代表变量之间的直接依赖关系；在定量层面：每个节点都有一个条件概率表(Conditional Probability Table)P(Xi|Parents(Xi),刻画了父变量对子变量的影响程度。给定BN,则存在一个离散变量集和 上的联合概率分布：12(,)nXXXX=K121()(,)(|()nniiiP XP XXXP XPa X=K 贝叶斯网络示例（1）贝叶斯网络示例（2）我们再回过头来看
26、刚才的例子,由于是否地震与盗窃无关,于是假设E和B是相互独立的;另外,琼和玛丽是否打电话直接取决于他们是否听到警铃响,因此,假定给定A时,J与B和E,以及M与J、B和E都是相互独立的,从而可以构造下面的贝叶斯网络；根据所构造的贝叶斯网络，联合概率分布可以表示为：这样就把联合概率分布分解成了若干个复杂度较低的概率分布的乘积。上式右端仅包含1+1+4+2+2=10个独参数。By0.01n0.99Ey0.02n0.98ABEyyy0.95nyy0.05yyn0.94nyn0.06yny0.29nny0.71ynn0.001nnn0.999JAyy0.7ny0.3yn0.01nn0.99MAyy0.9
27、ny0.1yn0.95nn0.05(,)()()(|,)(|)(|)PBEAJM PBPEPABEPM APJ A贝叶斯网络示例（3）贝叶斯网络又名：信念网(Belief Network)、概率网络(Probability Network)、因果网络(Causal Network)、图模型(Graphical Model)或概率图模型(PGM)、决策网络(Decision Network)、影响图(Influence Diagram)、知识图(Knowledge Map)贝叶斯网络作为不确定性知识表示的理想模型，具有以下主要特点：1.具有坚实的数学基础：贝叶斯理论是贝叶斯概率和经典的统计学理论
28、相结合的结果，它给出了信任函数在数学上的计算方法，刻画了信任度与样本数据的一致性以及信任度随数据而变化的增量学习特性，长期的理论研究和实践应用，证明了其有效性和正确性。2.贝叶斯网络是有向无循环图，能够清晰和直观地显示变量之间的因果关系。3.贝叶斯网络可以图形化表示随机变量间的联合概率，利用概率理论能够处理各种不确定性信息。4.贝叶斯网络可以处理不完整和带噪音的数据集。贝叶斯网络的特点贝叶斯网络的研究现状20世纪80年代，随着人工智能的发展，尤其是机器学习、数据挖掘等兴起，为贝叶斯理论的发展和应用提供了更为广阔的空间。Pearl等于1988年提出贝叶斯网络，并将贝叶斯网络成功地应用于专家系统，
29、成为不确定专家知识和推理的流行方法，90年代进一步研究可学习的贝叶斯网络，用于数据采掘和机器学习，近年来，贝叶斯学习理论方面的文章更是层出不穷，内容涵盖了人工智能的大部分领域，包括因果推理、不确定性知识表达、模式识别和聚类分析等。并且出现了专门研究贝叶斯理论的组织和学术刊物ISBA。随着人工智能的发展，贝叶斯理论的内涵也比以前有了很大的变化。目前，贝叶斯网络研究领域主要集中在以下四个方面：贝叶斯网络的学习、利用贝叶斯网络进行推理，计算和基于贝叶斯网络的应用。2.2贝叶斯网络的学习1.结构学习：发现变量之间的图关系 2.参数学习：决定变量之间互相关联的量化关系 贝叶斯网络结构学习结构学习是利用训
30、练样本集，尽可能结合先验知识，确定和样本数据集合D匹配最好的的贝叶斯网络拓扑结构；对于含有n个变量的数据集进行网络结构学习，可能的结构数目为：因此贝叶斯网络结构的学习是一个NP难问题。在计算机学科中，存在多项式时间的算法的一类问题，称之为P类问题；而像梵塔问题、推销员旅行问题、（命题表达式）可满足问题这类，至今没有找到多项式时间算法解的一类问题，称之为NP类问题。目前贝叶斯网络结构学习方法主要分成两类：基于搜索和评分的方法(score and search method）；基于约束的方法(constraint-based method).基于评分和搜索的方法将结构学习视为结构优化的过程，即利用
31、一个评分函数寻找与样本数据匹配程度最高的网络结构，即主要由两部分组成：评分函数和空间搜索策略 该算法的主要思想是从一个给定的网络出发(比如一个没有任何弧的网络),利用搜索方法对该网络进行一些操作(增加边，删除边，逆转边的方向)，根据评分函数对网络进行评分，计算这一操作对网络评分函数的贡献度，检验新的网络结构是否优于旧的网络结构，如果优于则保留新加入的边并继续该操作，直到找到得分最大的网络结构作为最优的网络结构。主要的评分函数和搜索机制 评分函数：最早是由Cooper and Herskovits等人在1992年提出的K2评分函数，K2评分函数假设观测到的数据是完备的，且服从多项式分布：基于K2
32、评分函数，Heckerman等人在1995年，假设观测数据服从Dirichlet分布，给出了BD评分函数：主要的搜索机制：贪婪搜索、模拟退火、最优最先搜索、基于智能优化的搜索等 经典算法 K2算法 1992年，Cooper和Herskovits建立了著名的基于贝叶斯评分函数（Bayesian score）和爬山法搜索策略的K2算法。K2算法要求事先确定节点的次序，应用贝叶斯评分，通过不断向网络中增加能提高评分函数的边的贪婪搜索方法贪婪搜索方法发现最评分最高的的信念网络结构，找出最佳网络结构。K2算法是结合先验信息进行贝叶斯网络结构学习的一个有实际意义的重要算法，在整个贝叶斯网络结构学习算法的研
33、究发展过程中占有重要地位。K2 算法使用后验概率作为评分函数：1(|)(,)nsiip D Bscore i pa其中 11()()(,)()()iiqrijijkijkijkijijijkNscore i paN 贪婪搜索K2算法描述Procedure K2For i:=1 to n do i=;Pold=g(i,i);OKToProceed:=truewhile OKToProceed and|i|Pold then Pold :=Pnew;i:=i z;else OKToProceed:=false;end whilewrite(“Node:”,“parents of this node
34、s:”,i);end forend K2K2的出发点是一个包含所有节点、但却没有边的无向图。在搜索过程中，K2按顺序逐个考察 中的变量，确定其父亲节点，然后添加相应的边。对某一变量，假设K2已经找到了它的一些父亲节点。如果 父亲节点个数还未达到上界，那么就要继续为它寻找父节点，具体做法是首先考虑哪些在 p中排在xj 之前，但却还不是 xj的父亲节点的变量，从这些变量中选出，它使得新家族CH评分 达到最大；然后将 新家族与旧家族评分比较：如果评分高，则把 添加为 的父节点；否则停止为 寻找父亲节点。基于约束的方法 将结构学习视为约束满足问题，即通过卡方假设检验或互信息量对变量间的条件独立性关系进
35、行测试来构造贝叶斯网络结构 核心思想是：首先对训练数据集进行统计测试，尤其是条件独立性测试，确定出不同结点集之间的一致条件独立性；然后，利用结点集之间的条件独立性，构造一个有向无环图，以尽可能多地涵盖这些条件独立性。节点间的卡方统计量：节点间的互信息量：经典算法 TPDA第一阶段：Drafting，计算每对节点间的互信息，建立完整的无向图；第二阶段：Thickening，如果节点对不是d-分割的话，把这一点对加入到边集中；第三阶段：Thinning，检察边集中的每个点对，如果两个节点是d-分割的，则移走这条边。2002年，Cheng将信息论与统计测试相结合，使用相互信息代替了条件独立测试，经过
36、Drafting、Thickening、Thinning三个步骤，通过计算相互信息量(Mutual Information)来确定结点间的条件独立性，从而构造多连接有向图模型。被称为TPDA算法。贝叶斯网络的参数学习u 最大似然估计最大似然估计 完全基于数据，不需要先验概率：完全基于数据，不需要先验概率：u 贝叶斯估计贝叶斯估计 假定在考虑数据之前，网络参数服从某个先验分布。先验的主观概率假定在考虑数据之前，网络参数服从某个先验分布。先验的主观概率,它它的影响随着数据量的增大而减小。的影响随着数据量的增大而减小。u 缺值数据最大似然估计：缺值数据最大似然估计：EM算法算法（迭代算法）（迭代算法
37、）1 基于基于 对数据进行修补，使之完整对数据进行修补，使之完整(E-step)2 基于修补后的完整数据计算的最大似然估计基于修补后的完整数据计算的最大似然估计 (M-Step)EM算法是收敛的。算法是收敛的。贝叶斯网络参数学习2.3贝叶斯网络的推理和计算为什么要用贝叶斯网络进行概率推理？为什么要用贝叶斯网络进行概率推理？理论上，进行概率推理所需要的只是一个联合概率分布。但是联合概率分布的复杂度相对于变量个数成指数增长，所以当变量众多时不可行。贝叶斯网络的提出就是要解决这个问题。它把复杂的联合概率分布分解成一系列相对简单的模块，从而大大降低知识获取和概率推理的复杂度，使得可以把概率论应用于大型
38、问题。贝叶斯网络推理 贝叶斯网络推理是在一个不定性环境和不完全信息下进行决策支持和因果发现的工具。贝叶斯网络推理基于如下假设：令人感兴趣的变量受概率分布的控制，人们结合观察数据，对这些概率进行推算便可以做出最优的决策。两个基本任务概率推理最大验后概率解释1 变量消元算法(Variable elimination)利用概率分解降低推理复杂度。使得运算局部化。消元过程实质上就是一个边缘化的过程。最优消元顺序：最大势搜索，最小缺边搜索贝叶斯网络推理算法2.团树传播算法l利用步骤共享来加快推理的算法。l团树（clique tree）是一种无向树，其中每一个节点代表一个变量集合，称为团(clique)。
39、团树必须满足变量连通性，即包含同一变量的所有团所导出的子图必须是连通的。用团树组织变量消元的算法。计算共享 团树传播算法基本步骤：将贝叶斯网络转化为团树 团树初始化 在团树中选一个团作为枢纽 全局概率传播：CollectMessage;DistributeMessage 边缘化，归一化 团树传播算法示例（TLR是枢纽节点）变量消元和团树传播算法都是精确推理精确推理算法3.近似推理 由于近似方法已牺牲推导结果精度换取推导效率的提高，故已在许多应用中显示了很好的实用性。面对现实世界实时性、响应性等要求，近似推理的方法逐渐成为主流方法，随机模拟采样法就是其中应用最广的概率推理方法。3.近似推理 随机
40、抽样算法：顺序抽样法，MCMC抽样 是一类应用于数值积分和统计物理中的近似计算方法。基本思想是从某个概率分布随机抽样，生成一组样本，然后从样本出发近似计算感兴趣的量。随机抽样算法理论基础是大数定律。MCMC算法吉布斯抽样(Gibbs sampling)。它首先随机生成一个与证据E=e相一致的样本s1作为起始样本。此后，每个样本si的产生都依赖于前一个样本si-1,且si与si-1最多只有一个非证据变量的取值不同，记改变量为X。X的取值可以从非证据变量中随机选取，也可以按某个固定顺序轮流决定。在si中，X的值通过随机抽样决定，抽样分布是：当样本数 时，马氏链理论保证了算法返回的结果收敛于真正的后
41、验概率。吉布斯抽样的缺点是收敛速度慢，因为马氏链往往需要花很长时间才能真正达到平稳分布。3.贝叶斯网络的应用3.1贝叶斯网络应用概述3.1贝叶斯网络应用实例l 医疗诊断，l 工业，l 金融分析，l 计算机（微软Windows,Office），l 模式识别：分类，语义理解l 军事（目标识别，多目标跟踪，战争身份识别等），l 生态学，l 生物信息学（贝叶斯网络在基因连锁分析中应用），l 编码学，l 分类聚类，l 时序数据和动态模型3.1贝叶斯网络应用概述3.1贝叶斯网络应用实例 随着计算机和网络的飞速发展，电子商务的出现，网上购物已经成为了一种潮流。但是面对网上复杂而纷乱的海量信息，人们总感觉无从
42、下手，即使是借助最先进的搜索引擎也不能满足消费者的需求。消费者们很希望电子商务网站能够真正从他个人的实际需求满足去考虑，其产品和服务在到达消费者之前就已经是经过信息组织的最个性化的信息服务。这样，从消费者的心里角度讲，他不仅仅使自己的个性化需求得到了真正满足，而是更重要的是，他感受到了商家对他的重视和关爱，使他自我价值能够得到体现。为了使客户体验到完全个性化的信息服务，更好地满足客户的需求，关键是要了解客户的兴趣，发掘出客户潜在的购买力。利用消费者在网上操作的各种数据可以发现用户兴趣的一种有效的方式。贝叶斯网络的网上用户兴趣预测分析 为了使算法中各数据项简单化，可以从中选取用户查询的关键字次数
43、M,浏览时间T，收藏商品名称N这3种动作来判断用户的实时兴趣。使用多元线性回归的方法来计算用户的初始兴趣度。在公式中用 i 来代表用户浏览商品的编号，不同的编号用来表示不同的商品，用 Yi 表示用户浏览的实时兴趣度。用户查询商品 i 的次数，浏览网页的时间和收藏商品的次数分别用 Mi、Ti、Ni 来表示。通过上述公式的计算可以得到所有节点的数据集 Yi。通过实验评估用户的实时兴趣 通过记录消费者用户操作、浏览网站网页数据的数据库中选择 500 个用户上网的数据记录，根据公式计算出每个用户的实时兴趣度。经过对这 500 个数据的筛选，从中挑选出 8 种不同的商品记录构造出贝叶斯网络。图中总共有
44、8 个节点代表 8 种不同的商品，每个节点都代表用户的初始兴趣度，根据节点间有向弧的关联得到如图 所示的用户实时兴趣的贝叶斯网络图。表 1 中列出了 3 个用户张三、李四、王五他们登录网站后，虽然他们所关注的商品都是这 8 种商品，但是根据他们查询关键字次数，浏览时间，收藏商品名称这 3 个主要动作计算出他们的兴趣度，得到不同的商品兴趣集。在表 1 中从经验推荐来看，选用 n=0.657，可以预测张三、李四、王五 3 个用户的感兴趣的商品集分别为7、2，3和1，4。根据表 1 和上式可以得到：张三的兴趣商品集为(个人护理用品，0.661)；李四的兴趣商品集为（电脑，0.687），（数码相机，0
45、.689）；王五的兴趣商品集为（手机，0.658），（名牌衣服，0.721。根据这些数据信息，商家就可以为不同的用户提供网上的个性化信息服务和推荐用户喜爱的商品，提高企业网站的服务效率和服务质量。4.贝叶斯网络总结 贝叶斯(Bayesian)网络近年成为数据采掘引人注目的研究方向。通过剖析Bayesian网络的结构和建造步骤，着重讨论用Bayesian方法从先验信息和样本数据进行学习以确定网络的结构和概率分布的基本方法，分析Bayesian网络学习的特点，探讨Bayesian网络的适用性。与数据采掘的其它方法相比，Bayesian网络的优点是可以综合先验信息和样本信息，这在样本难得时特别有用；可以发现数据之间的因果关系，适合于处理不完整数据集，这是其它模型难以做到的。其缺点是计算开销较大；确定合理的先验密度比较困难；如何判定实际问题是否满足所要求的假设，没有现成的规则。非常感谢大家的耐心倾听，再道一次 谢谢！5.致谢
