机器学习-Knn与贝叶斯学习部分2017

1、机器学习,For 2017研究生 主讲 李鹤喜,机器学习概述简介,1、概述 机器学习是近20多年兴起的一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。机器学习算法是一类从数据中自动分析获得规律，并利用规律对未知数据进行预测的算法。因为学习算法中涉及了大量的统计学理论，机器学习与统计推断学联系尤为密切，也被称为统计学习理论。算法设计方面，机器学习理论关注可以实现的，行之有效的学习算法。很多推论问题属于无程序可循难度，所以部分的机器学习研究是开发容易处理的近似算法。,机器学习概述机器学习应用,2、机器

2、学习的应用 机器学习已经有了十分广泛的应用，例如：数据挖掘、计算机视觉、汽车自动驾驶、语音和手写识别、自然语言处理、生物特征识别、搜索引擎、医学诊断、检测信用卡欺诈、证券市场分析、DNA序列测序、战略游戏和机器人运用,Autonomous Drive,Autonomous Drive,Autonomous Drive,Autonomous Drive,Voice Recognition,Voice Recognition,Voice Recognition,Voice Recognition,Machine Vision,Machine Vision,Machine Vision,Machin

3、e Vision,Face Recognition,Face Recognition,Face Recognition,Facial Expression Recognition,Facial Expression Recognition,Facial Expression Recognition,Facial Expression Recognition,Facial Expression Recognition,Data Mining,Data Mining,Data Mining,Data Mining,Data Mining,人工智能与机器学习的关系,“人工智能的根本在于智能，如何为机

4、器赋予智能。而机器学习则是部署支持人工智能的计算方法。我的想法是：人工智能是科学，机器学习则是让机器变得更加智能的算法”。 Nidhi ChappelIntel的机器学习主管。,机器学习概述机器学习的定义,3、什么是机器学习？ 机器学习有下面几种定义： （1） “机器学习是一门人工智能的科学，该领域的主要研究对象是人工智能，特别是如何在经验学习中改善具体算法的性能”。 （2） “机器学习是对能通过经验自动改进的计算机算法的研究”。 （3） “机器学习是用数据或以往的经验，以此优化计算机程序的性能标准。” （4）英文定义是：A computer program is said to learn

5、from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E,机器学习概述机器学习的发展历史,4、机器学习的发展历史 机器学习的研究基本上经历了以下几个发展时期 通用的学习系统研究， 基于符号表示的概念学习系统研究， 基于知识的各种学习系统研究， 联接学习和符号学习的深入研究。,（1）通用学习系统的研究 这一时期从50年代中叶开始，几乎

6、和人工智能学科的诞生同步。当时，人工智能的研究着重于符号表示和启发式方法的研究，而机器学习却致力于构造一个没有或者只有很少初始知识的通用系统，这种系统所应用的主要技术有神经元模型、决策论和控制论。 鉴于当时计算机技术的限制，研究主要停留在理论探索和构造专用的实验硬件系统。这种系统以神经元模型为基础，只带有随机的或部分随机的初始结构，然后给它一组刺激，一个反馈源和修改自身组织的足够自由度，使系统有可能自适应地趋向最优化组织。这种系统的代表是称为感知器的神经网络。,机器学习概述机器学习的发展历史,（1）通用学习系统的研究 这种系统的代表是称为感知器的神经网络。系统的学习主要靠神经元在传递信号的过程

7、中，所反映的概率上的渐进变化来实现。同时也有人开发了应用符号逻辑来模拟神经元系统的工作，如McCulloch 和 Pitts用离散决策元件模拟神经元的理论。相关的工作包括进化过程的仿真，即通过随机演变和自然选择来创造智能系统，如Friedberg的进化过程模拟系统。这方面的研究引出了二个副产品:形成了人工智能的一个新分支模式识别，并创立了学习的决策论方法。这个方法的学习含义是从给定的例子集中，获取一个线性的、多项式的或相关的识别函数。,机器学习概述机器学习的发展历史,（1）通用学习系统的研究 神经元模型的研究未取得实质性进展，并在60年代末走入低谷。作为对照，一种最简单、最原始的学习方法-机械

8、学习，又称为死记式学习，却取得了显著的成功。该方法通过记忆和评价外部环境提供的信息来达到学习的目的。采用该方法的代表性成果是塞缪尔(A.L.Samuel)于50年代末设计的跳棋程序，随着使用次数的增加，该程序会积累性记忆有价值的信息，可以很快达到大师级水平。正是机械学习的成功激励了研究者们继续进行机器学习的探索性研究。,机器学习概述机器学习的发展历史,（2）基于符号表示的概念学习系统研究 从60年代中叶开始，机器学习转入第二时期-基于符号表示的概念学习系统研究。当时，人工智能的研究重点已转到符号系统和基于知识的方法研究。如果说第一时期的研究是用数值和统计方法的话，这一时期的研究则综合了逻辑和图

9、结构的表示。研究的目标是表示高级知识的符号描述及获取概念的结构假设。这时期的工作主要有概念获取和各种模式识别系统的应用。其中，最有影响的开发工作当属温斯顿(Winston)的基于示例归纳的结构化概念学习系统。,机器学习概述机器学习的发展历史,（2）基于符号表示的概念学习系统研究 人们研究了从例子中学习结构化概念的各种不同方法。也有部分研究者构造了面向任务的专用系统，这些系统旨在获取特定问题求解任务中的上下文知识，代表性工作有亨特和哈兰德(Hunt for example KD trees,3 、贝叶斯学习算法,3.1概述 贝叶斯学习算法是一种依据统计学原理的学习方法，更确切地说它是一类利用概率

10、统计知识进行分类的算法。在许多场合，朴素贝叶斯(Naive Bayes，NB)分类算法可以与决策树和神经网络分类算法相媲美，该算法能运用到大型数据库中，且方法简单、分类准确率高、速度快。,贝叶斯学习的特点： 贝叶斯推理提供了一种概率手段，基于如下的假定：待考察的量遵循某概率分布，且可根据这些概率及已观察到的数据进行推理，以作出最优的决策。 贝叶斯推理为衡量多个假设的置信度提供了定量的方法。 贝叶斯推理为直接操作概率的学习算法提供了基础，也为其他算法的分析提供了理论框架。,3 、贝叶斯学习算法,3.2 一些与贝叶斯学习有关的预备知识,确定事件：概念是确定的，发生也是确定的； 随机事件：概念是确定

11、的，发生是不确定的； 模糊事件：概念本身就不确定。,1、随机变量,随机变量：随机事件的数量表示； 离散随机变量：取值为离散的随机变量 ； 连续随机变量：取值为连续的随机变量 ；,3.2 一些预备知识,2、频率和概率,频率：试验在相同的条件下重复N次，其中M次事件A发生，则A发生的频率为： fN(A) = M / N 概率：当N很大时，频率会趋向一个稳定值，称为A的概率：,3.2 一些预备知识,3、联合概率和条件概率,联合概率：设A，B是两个随机事件，A和B同时发生的概率称为联合概率，记为：P(A, B)； 条件概率：在B事件发生的条件下，A事件发生的概率称为条件概率，记为：P(A|B)； 乘法

12、定理：P(A|B) = P(A, B) / P(B)。 P(A, B)= P(A|B) P(B)。,3.2 一些预备知识,4、概率密度函数,概率分布函数：设X为连续型随机变量，定义分布函数；F(x) = P(Xx)； 概率密度函数：给定X是随机变量，如果存在一个非负函数f(x)，使得对任意实数a,b(ab)有 P（aXb) = f(x)dx, （积分下限是a,上限是b) ，则称f(x)为X的概率密度函数,3.2 一些预备知识,概率密度函数f(x),3.2 一些预备知识,条件概率P（A|B)：,设A、B是两个随机事件，则有：,P（A)-事件A的先验概率（prior probability） P(

13、A|B)-事件A的后验概率（ posterior probability）,5、事件概率的贝叶斯定理,P(ci) 先验概率,P(x) 是x的先验概率,P(ci|x)后验概率,3.3 基于贝叶斯决策的分类器,给定一个n类（c1,c2,cn)，用一个特征向量x表示未知样本，生成n个条件概率P(ci|x),也称为后验概率，则根据贝叶斯定理有,先验概率P(ci),P(ci)代表还没有训练数据前，ci拥有的初始概率。P(ci)常被称为ci的先验概率(prior probability) ，它反映了我们所拥有的关于ci是正确分类机会的背景知识,它应该是独立于样本的。,如果没有这一先验知识，那么可以简单地将

14、每一候选类别赋予相同的先验概率。不过通常我们可以用样例中属于ci的样例数|ci|比上总样例数|D|来近似，即,3.3 基于贝叶斯决策的分类器,似然函数P(x|cj) (likehood),似然函数是指当已知类别为ci的条件下，看到样本x(特征向量）出现的概率。,若设x = ai为属性 则P(x|ci)= P(a1,a2am| ci),3.3 基于贝叶斯决策的分类器,后验概率P(ci |x),即给定数据样本x时ci成立的概率,而这正是我们所感兴趣的。,P(ci|x )被称为ci的后验概率（posterior probability），因为它反映了在看到数据样本x后cj成立的置信度。 对于一个决策

15、判断，我们取后验概率为最大的作为正确的分类，即：,3.3 基于贝叶斯决策的分类器,假设在某地区切片细胞中正常（c1）和异常（c2）两类的先验概率分别为p(c1)=0.9, p(c2)=0.1。现有一待识别细胞呈现出状态 x(测量值），由其类条件概率密度分布曲线查的p(x|c1)=0.2, p(x|c2)=0.4,试对细胞x进行分类。,3.3 基于贝叶斯决策的分类器,一个基于贝叶斯决策的实例,利用贝叶斯公式，分别计算出状态为x时c1与c2的后验概率,3.3 基于贝叶斯决策的分类器,后验概率由下式决定,而上式分母是x的概率，由全概率公式有,正常细胞C1的后验概率为：,异常细胞C2的后验概率为：,由

16、于c1的后验概率C2的后验概率：,3.4 贝叶斯学习算法简介,贝叶斯学习算法与机器学习相关的两个原因： 贝叶斯学习算法能够计算显式的假设概率，比如朴素贝叶斯分类，是解决学习问题的最实际方法。 贝叶斯方法为理解多数学习算法提供了一种有效的手段，而这些算法不一定直接操纵概率数据，比如 Find-S 候选消除算法 神经网络学习：选择使误差平方和最小化的神经网络 推导出另一种误差函数：交叉熵 分析了决策树的归纳偏置 考察了最小描述长度原则,贝叶斯学习方法的特性,观察到的每个训练样例可以增量地降低或升高某假设的估计概率。而其他算法会在某个假设与任一样例不一致时完全去掉该假设。 先验知识可以与观察数据一起

17、决定假设的最终概率，先验知识的形式是：1）每个候选假设的先验概率；2）每个可能假设在可观察数据上的概率分布。 贝叶斯方法可允许假设做出不确定性的预测。 新的实例分类可由多个假设一起做出预测，用它们的概率来加权。 即使在贝叶斯方法计算复杂度较高时，它们仍可作为一个最优的决策标准衡量其他方法。,贝叶斯方法的难度,难度之一：需要概率的初始知识，当概率预先未知时，可以基于背景知识、预先准备好的数据以及基准分布的假定来估计这些概率 难度之二：一般情况下，确定贝叶斯最优假设的计算代价比较大（在某些特定情形下，这种计算代价可以大大降低）。,贝叶斯法则,机器学习的任务：在给定训练数据D 时，确定假设空间（hy

18、potheses）H=h1,h2,中的最佳假设。 最佳假设：一种方法是把它定义为在给定数据D以及H中不同假设的先验概率的有关知识下的最可能假设。 贝叶斯理论提供了一种计算假设概率的方法，基于假设的先验概率、给定假设下观察到不同数据的概率以及观察到的数据本身。,先验概率和后验概率,用P(h)表示在没有训练数据前假设h拥有的初始概率。P(h)被称为h的先验概率。 先验概率反映了关于h是一正确假设的机会的背景知识 如果没有这一先验知识，可以简单地将每一候选假设赋予相同的先验概率 类似地，P(D)表示训练数据D的先验概率，P(D|h)表示假设h成立时D的概率 机器学习中，我们关心的是P(h|D)，即给

19、定D时h的成立的概率，称为h的后验概率,贝叶斯公式,贝叶斯公式提供了从先验概率P(h)、P(D)和P(D|h)计算后验概率P(h|D)的方法 P(h|D)随着P(h)和P(D|h)的增长而增长，随着P(D)的增长而减少，即如果D独立于h时被观察到的可能性越大，那么D对h的支持度越小,极大后验假设MAP,学习器在候选假设集合H中寻找给定数据D时可能性最大的假设h，h被称为极大后验假设（MAP-Maximum a posteriori） 确定MAP的方法是用贝叶斯公式计算每个候选假设的后验概率，计算式如下 最后一步，去掉了P(D)，因为它是不依赖于h的常量,极大似然假设（maxiunm likeh

20、ood),在某些情况下，可假定H中每个假设有相同的先验概率，这样式子可以进一步简化，只需考虑P(D|h)来寻找极大可能假设。 P(D|h)常被称为给定h时数据D的似然度，而使P(D|h)最大的假设被称为极大似然假设 假设空间H可扩展为任意的互斥命题集合，只要这些命题的概率之和为1,实例：一个医疗诊断问题（1）,有两个可选的假设：h1=病人有癌症、h2=病人无癌症，假设H=h1,h2 可用数据D 来自化验结果：d1为正+和d2为负-, D=d1,d2 有先验知识：在所有人口中，患病率是P(h1)=0.008，则无病率P(h2)=0.992 对确实有病的患者的化验准确率为98%，对确实无病的患者的

21、化验准确率为97% 总结如下 P(h1)=0.008, P(h2)=0.992 P(d1|h1)=0.98, P(d2|h1)=0.02 P(d1|h2)=0.03, P(d2|h2)=0.97,问题：假定有一个新病人，化验结果为正，是否应将病人断定为有癌症？求后验概率P(h1|d1)和P(h2|d1) 利用贝叶斯后验概率公式计算后验假设概率：,hMAP=h2(无癌症）,取最大后验概率有：,P(h1|d1) =P(d1|h1)P(h1)=0.98*0.008=0.00784 P(h2|d1)=P(d1|h2)P(h2)=0.03*0.992=0.02976,实例：一个医疗诊断问题（2）,举例：

22、一个医疗诊断问题（2）,贝叶斯推理的结果很大程度上依赖于先验概率，另外不是完全接受或拒绝假设，只是在观察到较多的数据后增大或减小了假设的可能性。,确切的后验概率可将上面的结果除以P(d1)得到，,对于无癌症的假设h2有,贝叶斯最优分类器（1）,前面我们讨论的问题是：给定训练数据，最可能的假设是什么？ 另一个相关的更有意义的问题是：给定训练数据，对新实例的最可能的分类是什么？ 显然，第二个问题的解决可以将第一个问题的结果（MAP）应用到新实例上得到，还存在更好的算法,贝叶斯最优分类器（2）,例子 考虑一个包含三个假设h1, h2, h3的假设空间。 假定已知训练数据时三个假设的后验概率分别是P(

23、h1|D)=0.4, P(h2|D)=0.3, P(h3|D)=0.3，因此h1为MAP假设。 若一新实例x被h1分类为正，被h2和h3分类为反 计算所有假设，x为正例的概率为0.4，为反例的概率为0.6 因此，这时最可能的分类与MAP假设生成的分类不同,贝叶斯最优分类器（3）,一般而言，新实例的最可能分类可通过合并所有假设的预测得到，用后验概率来加权。 如果新实例的可能分类可取某集合V中的任一值vj，那么概率P(vj|D)表示新实例分类为vj的概率 新实例的最优分类为使P(vj|D)最大的vj值，贝叶斯最优分类器为：,贝叶斯最优分类器（4）,例子 已知：假设空间H=h1,h2,h3 新实例的

24、可能分类集合为V=+, - P(h1|D)=0.4, P(-|h1)=0, P(+|h1)=1 P(h2|D)=0.3, P(-|h2)=1, P(+|h2)=0 P(h3|D)=0.3, P(-|h3)=1, P(+|h2)=0 因此：,贝叶斯最优分类器（4）,具体实例 已知：假设空间肝功指标异常H=h1,h2,h3 h1=谷丙转氨酶(ALT)高 h2=谷氨酰转肽酶(GGT)高 h3=碱性磷酸酶(ALP)高 新实例的可能分类集合为肝功 V=+, -=不正常，正常 D测量数据 P(h1|D)=0.4, P(-|h1)=0, P(+|h1)=1 P(h2|D)=0.3, P(-|h2)=1, P

25、(+|h2)=0 P(h3|D)=0.3, P(-|h3)=1, P(+|h2)=0 因此：,贝叶斯最优分类器（5）,贝叶斯最优分类器在给定可用数据、假设空间及这些假设的先验概率下使新实例被正确分类的可能性达到最大 贝叶斯最优分类器的一个属性：它所做的分类可以对应于H中不存在的假设 使用前面式子来分类X中的每个实例，按此定义的实例标注不一定对应于H中的任一单个假设h对实例的标注 将贝叶斯分类器看成是不同于假设空间H的另一空间H，在其上应用贝叶斯公式。H有效地包含了一组假设，它能在H中多个假设的线性组合所作的预言中进行比较,朴素贝叶斯分类器,朴素贝叶斯分类器（Naive Bayes Classi

26、fier)是贝叶斯学习方法中实用性很高的一种分类器，其核心思想是假设样本的每个特征与其他特征都不相关。尽管这些特征有时相互依赖或者有些特征由其他特征决定，然而朴素贝叶斯分类器认为这些属性在概率分布上独立的。朴素贝叶斯分类器在有监督学习的样本集中能获取得非常好的分类效果。在许多实际应用中，朴素贝叶斯分类器对很多复杂的现实情形中仍能够取得相当好的效果。,朴素贝叶斯分类器,应用的学习任务：每个实例x可由属性值的合取描述，而目标函数 f(x)从某有限集合V中取值 贝叶斯方法的新实例分类目标是在给定描述实例的属性值下，得到最可能的目标值vMAP 使用贝叶斯公式变化上式,朴素贝叶斯分类器（2）,基于训练数

27、据估计式子中的两个数据项的值 估计P(vj)很容易：计算每个目标值vj出现在训练数据中的频率 估计P(a1,.an|vj)遇到数据稀疏问题，除非有一个非常大的训练数据集，否则无法获得可靠的估计 朴素贝叶斯分类器引入一个简单的假定避免数据稀疏问题：在给定目标值时，属性值之间相互条件独立，即,朴素贝叶斯分类器（3）,朴素贝叶斯分类器的定义： 从训练数据中估计不同P(ai|vj)项的数量比要估计P(a1,.,an|vj)项所需的量小得多。 只要条件独立性得到满足，朴素贝叶斯分类vNB等于MAP分类，否则是近似。 朴素贝叶斯分类器与其他已介绍的学习方法的一个区别：没有明确地搜索可能假设空间的过程（假设

28、的形成不需要搜索，只是简单地计算训练样例中不同数据组合的出现频率）。,考虑周六上午是否适合玩网球的概念学习，设天气有4个属性Di=Outlook，Temperature， Humidity，wind,目标概念PlayTennis的训练样例集D=D1,D2,D14,朴素贝叶斯分类器-实例,目标概念PlayTennis的训练样例（续）,朴素贝叶斯分类器-实例,朴素贝叶斯分类器（4）,问题： 根据表中提供的目标概念PlayTennis的14个训练样例，给新实例D15=，请分类D15属于: PlayTennis=Yes 或 PlayTennis=No 按朴素贝叶斯公式: 这里类别V= Yes, No

29、=,朴素贝叶斯分类器（4）,根据上表可以计算出上式需要的概率值 P(v1)=P(yes)=9/14=0.64 P(v2)=P(no)=5/14=0.36 P(a1|v1)=P(Sunny|yes) =2/9=0.22 P(a1|v2)=P(Sunny|no) =3/5=0.60 P(a2|v1)=P(Cool|yes) =3/9=0.33 P(a2|v2)=P(Cool|no) =1/5=0.20 P(a3|v1)=P(High|yes) =3/9=0.33 P(a3|v2)=P(High|no) =4/5=0.80 P(a4|v1)=P(strong|yes) =3/9=0.33 P(a4|

30、v2)=P(strong|no) =3/5=0.60,朴素贝叶斯分类器（4）,求vNB P(v1|D15)=P(v1|a1,a2,a3,a4)=P(v1)P(a1|v1) P(a2|v1) P(a3|v1) P(a4|v1) =P(yes|Sunny,Cool,High,Strong) =P(yes)P(Sunny|yes)P(Cool|yes)P(High|yes)P(Strong|yes) =0.64*0.22*0.33*0.33*0.33 =0.0051 P(v2|D15) =P(v2|a1,a2,a3,a4)=P(v2)P(a1|v2) P(a2|v2) P(a3|v2) P(a4|v

31、2) =P(No|Sunny,Cool,High,Strong) =P(No)P(sunny|no)P(cool|no)P(high|no)P(strong|no) = 0.36*0.60*0.20*0.80*0.60 =0.0207,朴素贝叶斯分类器-概率估算,估计概率 前面通过在全部事件基础上观察某事件出现的比例来估计概率，即P估计=nc /n 当样本很小时，采用平滑技术，m-估计 p是将要确定的概率的先验估计，而m是一称为等效样本大小的常量 在缺少其他信息时，选择p的一种典型的方法是均匀概率，比如某属性有k个可能值，那么p=1/k m被称为等效样本大小的原因是：P估计式子可被解释为将n个

32、实际的观察扩大，加上m个按p分布的虚拟样本,朴素贝叶斯分类器学习分类文本,利用朴素贝叶斯分类器可以进行文本自动过滤，比如 我感兴趣的电子新闻稿 讨论机器学习的Web网页 这里描述一个基于朴素贝叶斯分类器的文本分类的通用算法，它是目前所知的文本分类的最有效方法之一 问题框架：实例空间X包含了所有的文本文档，给定某未知目标函数f (x)的一组训练样例，f(x)的值来自某有限集合V（作为示例，此处令V=like, dislike）,举例：学习分类文本（2）,应用朴素贝叶斯分类器的两个主要设计问题： 1) 怎样将任意文档表示为属性值的形式 2) 如何估计朴素贝叶斯分类器所需的概率 表示文档的方法 给定

33、一个文本文档，对每个单词的位置定义一个属性，该属性的值为在此位置上找到的英文单词 假定我们共有1000个训练文档，其中700个分类为dislike，300个分类为like，现在要对下面的新文档进行分类： This is an example document for the naive Bayes classifier. This document contains only one paragraph, or two sentences.,举例：学习分类文本（3）,注意:此处贝叶斯分类器隐含的独立性假设并不成立。通常，某个位置上出现某个单词的概率与前后位置上出现的单词是相关的。 虽然此处独立

34、性假设不精确，但别无选择，否则要计算的概率项极为庞大。 另外实践中，朴素贝叶斯学习器在许多文本分类问题中性能非常好。,按朴素贝叶斯计算式有,举例：学习分类文本（4）,需要估计概率项P(vj)和P(ai=wk|vj)。前一项可基于每一类在训练数据中的比例很容易得到, P(like) =0.3, P(dislike)=0.7,后一项的概率计算量相当大，假如有20000单词，则有2(两类)19(位置属性) 20000=96万！ 再引入一个假定以减少需要估计的概率项的数量：假定单词wk出现的概率独立于单词所在的位置，即P(ai=wk|vj)=P(wk|vj) 作此假定的一个主要优点在于：使可用于估计每

35、个所需概率的样例数增加了，因此增加了估计的可靠程度,举例：学习分类文本（4）,采纳m-估计方法，即有统一的先验概率并且m等于词汇表的大小，因此,词汇表单词总数,n为文档中不同位置单词总数,假设统一的先验概率故有：,所以 m*p=1,wk出现在文本中的次数,用于学习和分类文本的朴素贝叶斯算法,Learn_Naive_Bayes_Text( Examples, V ) Examples为一组文本文档以及它们的目标值。V为所有可能目标值的集合。此函数作用是朴素贝叶斯学习概率项P(wk|vj)和P(vj)的估算。 收集Examples中所有的单词、标点符号以及其他记号 Vocabulary在Examp

36、les中任意文本文档中出现的所有单词及记号的集合字典 计算所需要的概率项P(vj)和P(wk|vj) 对V中每个目标值vj docsjExamples中目标值为vj的文档子集 P(vj)|docsj| / |Examples| Textj将docsj中所有成员连接起来建立的单个文档 n在Textj中不同单词位置的总数 对Vocabulary中每个单词wk nk单词wk出现在Textj中的次数 P(wk|vj)(nk+1) / (n+|Vocabulary|),用于学习和分类文本的朴素贝叶斯算法（2）,Classify_Naive_Bayes_Text( Doc ) 对文档Doc返回其估计的目标

37、值，ai代表在Doc中的第i个位置上出现的单词 positions在Doc中的所有单词位置，它包含能在Vocabulary中找到的记号 返回vNB，,利用前面学习获得的P(wk|vj),代入上式得,实验结果,Joachims将此算法用于新闻组文章的分类 每一篇文章的分类是该文章所属的新闻组名称 20个新闻组，每个新闻组有1000篇文章，共2万个文档 2/3作为训练样例，1/3进行性能测量 词汇表不包含最常用词（比如the、of）和罕见词（数据集中出现次数少于3） Lang用此算法学习目标概念“我感兴趣的新闻组文章” NewsWeeder系统，让用户阅读新闻组文章并为其评分，然后使用这些评分的文

38、章作为训练样例，来预测后续文章哪些是用户感兴趣的 每天向用户展示前10%的自动评分文章，它建立的文章序列中包含的用户感兴趣的文章比通常高34倍,贝叶斯信念网,朴素贝叶斯分类器假定各个属性取值在给定目标值v下是条件独立的，从而化简了最优贝叶斯分类的计算复杂度。但在多数情况下，这一条件独立假定过于严厉了。 贝叶斯信念网描述的是一组变量所遵从的概率分布，它通过一组条件概率来指定一组条件独立性假设。 贝叶斯信念网中可表述变量的一个子集上的条件独立性假定，因此，贝叶斯信念网提供了一种中间的方法，它比朴素贝叶斯分类器的限制更少，又比在所有变量中计算条件依赖更可行。,贝叶斯信念网（2）,贝叶斯信念网描述了一

39、组变量上的概率分布 考虑一任意的随机变量集合Y1.Yn，其中每个Yi可取的值集合为V(Yi) 变量集合Y的联合空间为叉乘V(Y1). V(Yn) 在此联合空间上的概率分布称为联合概率分布，联合概率分布指定了元组的每个可能的变量约束的概率 贝叶斯信念网则对一组变量描述了联合概率分布,条件独立性,精确定义条件独立性 令X, Y和Z为3个离散值随机变量，当给定Z值时X服从的概率分布独立于Y的值，称X在给定Z时条件独立于Y，即 上式通常简写成P(X|Y,Z)=P(X|Z) 扩展到变量集合 下面等式成立时，称变量集合X1.Xl在给定变量集合Z1.Zn时条件独立于变量集合Y1.Ym 条件独立性与朴素贝叶斯

40、分类器的之间的关系,贝叶斯信念网的表示,贝叶斯信念网（简称贝叶斯网）表示一组变量的联合概率分布 一般地说，贝叶斯网表示联合概率分布的方法是指定一组条件独立性假定（有向无环图）以及一组局部条件概率集合 如下图示，联合空间中每个变量在贝叶斯网中表示为一个节点，每个变量需要两种类型的信息 网络弧表示断言“此变量在给定其直接前驱时条件独立于其非后继” 每个变量有一个条件概率表，描述了该变量在给定其立即前驱（父节点）时的概率分布,Storm,BusTourGroup,Lighting,Campfire,Thunder,ForestFire,Campfire,由事件S-Storm 、 B-BusTourG

41、roup、 L-Lighting、 C-Campfire 、T-Thunder、 F-ForestFire组成的贝叶斯网，其中C的父节点为S、B，条件概率CPT表如下,贝叶斯信念网的表示,贝叶斯信念网的表示实例,命题S- Smoker吸烟者 命题CCoal Miner 是煤矿工人 命题LLung Cancer 他患肺癌 命题EEmphysema 他患肺气肿,S,L,E,C,节点代表一个证据 有向弧代表一个规则假设表达了节点间的因果关系 弧的起点父节点Parent 如S是L、E的父节点 弧的终点后代节点 E是 S、C的后代节点,用一个无环DAG有向图来表示因果关系网,贝叶斯信念网的表示,贝叶斯网

42、络就是在因果关系网上加入连接强度的因果关系。,A,B,C,如果A是B的父节点，通过概率因果关系，很显然P(B|A)就是连接强度，即由A推出B的可能性有多大。如果B不止一个父节点，如还有父节点C，则对B的推演应该用联合概率P（B|AC）来描述。,P（B|A),P（B|C),就是在因果关系网上加入连接强度的因果关系。,贝叶斯信念网的表示,所有指定的概率和无环图构成一个贝叶斯网络，概率数据集称为条件概率表CPTConditional Probolity Table.如下图CPT 包括了 P(A) 、P（C)、P(B|AC)、P(E|B)、P(B|D)、P(F|E)、P(G|DEF),A,B,C,如果

43、A是B的父节点，通过概率因果关系，很显然P(B|A)就是连接强度，即由A推出B的可能性有多大。如果B不止一个父节点，如还有父节点C，则对B的推演应该用联合概率P（B|AC）来描述。,P（G|DEF),G,F,E,D,贝叶斯信念网的表示,命题S- Smoker吸烟者 命题CCoal Miner 是煤矿工人 命题LLung Cancer 他患肺癌 命题EEmphysema 他患肺气肿,S,L,E,C,P(S)=0.4,P(C)=0.3,P(E|S,C)=0.9,CPT 表 P(S)=0.4 P(C)=0.3 P(E|S,C)=0.9 P(E|S,C)=0.3 P(E|S,C)=0.5 P(E|S,C)=0.1,联合概率,在贝叶斯网络中假定一系列条件独立属性，即给定父节点，每个变量的概率只与父节点相关，而与其他节点在概率上是独立的。 条件独立的定义为： 有节点A，B，C，如果P(A|BC)=P(A|B)即B确定后C的任何信息不能改变A的置信度量，则称A与C是在B的条件下独立的。,设对于节点xi，其父节点集为pai,每个变量xi的条件概率为P(xi|pai),则节点集合X=x1,x2,xn的联合概率可表达为：,联合概率,前面的患者实例中X=S，C，L，E的联合概率密度按定义为：,E与L在S条