算法杂货铺——分类算法之贝叶斯网络(Bayesian networks)

2024-06-16 03:38

本文主要是介绍算法杂货铺——分类算法之贝叶斯网络(Bayesian networks),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2010-09-18 22:50 by T2噬菌体, 20383 阅读, 18 评论, 收藏 , 编辑

2.1、摘要

      在上一篇文章中我们讨论了朴素贝叶斯分类。朴素贝叶斯分类有一个限制条件,就是特征属性必须有条件独立或基本独立(实际上在现实应用中几乎不可能做到完全独立)。当这个条件成立时,朴素贝叶斯分类法的准确率是最高的,但不幸的是,现实中各个特征属性间往往并不条件独立,而是具有较强的相关性,这样就限制了朴素贝叶斯分类的能力。这一篇文章中,我们接着上一篇文章的例子,讨论贝叶斯分类中更高级、应用范围更广的一种算法——贝叶斯网络(又称贝叶斯信念网络或信念网络)。

2.2、重新考虑上一篇的例子

      上一篇文章我们使用朴素贝叶斯分类实现了SNS社区中不真实账号的检测。在那个解决方案中,我做了如下假设:

      i、真实账号比非真实账号平均具有更大的日志密度、各大的好友密度以及更多的使用真实头像。

      ii、日志密度、好友密度和是否使用真实头像在账号真实性给定的条件下是独立的。

      但是,上述第二条假设很可能并不成立。一般来说,好友密度除了与账号是否真实有关,还与是否有真实头像有关,因为真实的头像会吸引更多人加其为好友。因此,我们为了获取更准确的分类,可以将假设修改如下:

      i、真实账号比非真实账号平均具有更大的日志密度、各大的好友密度以及更多的使用真实头像。

      ii、日志密度与好友密度、日志密度与是否使用真实头像在账号真实性给定的条件下是独立的。

      iii、使用真实头像的用户比使用非真实头像的用户平均有更大的好友密度。

      上述假设更接近实际情况,但问题随之也来了,由于特征属性间存在依赖关系,使得朴素贝叶斯分类不适用了。既然这样,我去寻找另外的解决方案。

      下图表示特征属性之间的关联:

      上图是一个有向无环图,其中每个节点代表一个随机变量,而弧则表示两个随机变量之间的联系,表示指向结点影响被指向结点。不过仅有这个图的话,只能定性给出随机变量间的关系,如果要定量,还需要一些数据,这些数据就是每个节点对其直接前驱节点的条件概率,而没有前驱节点的节点则使用先验概率表示。

      例如,通过对训练数据集的统计,得到下表(R表示账号真实性,H表示头像真实性):

      纵向表头表示条件变量,横向表头表示随机变量。上表为真实账号和非真实账号的概率,而下表为头像真实性对于账号真实性的概率。这两张表分别为“账号是否真实”和“头像是否真实”的条件概率表。有了这些数据,不但能顺向推断,还能通过贝叶斯定理进行逆向推断。例如,现随机抽取一个账户,已知其头像为假,求其账号也为假的概率:

     

      也就是说,在仅知道头像为假的情况下,有大约35.7%的概率此账户也为假。如果觉得阅读上述推导有困难,请复习概率论中的条件概率、贝叶斯定理及全概率公式。如果给出所有节点的条件概率表,则可以在观察值不完备的情况下对任意随机变量进行统计推断。上述方法就是使用了贝叶斯网络。

2.3、贝叶斯网络的定义及性质

      有了上述铺垫,我们就可以正式定义贝叶斯网络了。

      一个贝叶斯网络定义包括一个有向无环图(DAG)和一个条件概率表集合。DAG中每一个节点表示一个随机变量,可以是可直接观测变量或隐藏变量,而有向边表示随机变量间的条件依赖;条件概率表中的每一个元素对应DAG中唯一的节点,存储此节点对于其所有直接前驱节点的联合条件概率。

      贝叶斯网络有一条极为重要的性质,就是我们断言每一个节点在其直接前驱节点的值制定后,这个节点条件独立于其所有非直接前驱前辈节点。

      这个性质很类似Markov过程。其实,贝叶斯网络可以看做是Markov链的非线性扩展。这条特性的重要意义在于明确了贝叶斯网络可以方便计算联合概率分布。一般情况先,多变量非独立联合条件概率分布有如下求取公式:

     

      而在贝叶斯网络中,由于存在前述性质,任意随机变量组合的联合条件概率分布被化简成

     

      其中Parents表示xi的直接前驱节点的联合,概率值可以从相应条件概率表中查到。

      贝叶斯网络比朴素贝叶斯更复杂,而想构造和训练出一个好的贝叶斯网络更是异常艰难。但是贝叶斯网络是模拟人的认知思维推理模式,用一组条件概率函数以及有向无环图对不确定性的因果推理关系建模,因此其具有更高的实用价值。

2.4、贝叶斯网络的构造及学习

      构造与训练贝叶斯网络分为以下两步:

      1、确定随机变量间的拓扑关系,形成DAG。这一步通常需要领域专家完成,而想要建立一个好的拓扑结构,通常需要不断迭代和改进才可以。

      2、训练贝叶斯网络。这一步也就是要完成条件概率表的构造,如果每个随机变量的值都是可以直接观察的,像我们上面的例子,那么这一步的训练是直观的,方法类似于朴素贝叶斯分类。但是通常贝叶斯网络的中存在隐藏变量节点,那么训练方法就是比较复杂,例如使用梯度下降法。由于这些内容过于晦涩以及牵扯到较深入的数学知识,在此不再赘述,有兴趣的朋友可以查阅相关文献。

2.5、贝叶斯网络的应用及示例

      贝叶斯网络作为一种不确定性的因果推理模型,其应用范围非常广,在医疗诊断、信息检索、电子技术与工业工程等诸多方面发挥重要作用,而与其相关的一些问题也是近来的热点研究课题。例如,Google就在诸多服务中使用了贝叶斯网络。

      就使用方法来说,贝叶斯网络主要用于概率推理及决策,具体来说,就是在信息不完备的情况下通过可以观察随机变量推断不可观察的随机变量,并且不可观察随机变量可以多于以一个,一般初期将不可观察变量置为随机值,然后进行概率推理。下面举一个例子。

      还是SNS社区中不真实账号检测的例子,我们的模型中存在四个随机变量:账号真实性R,头像真实性H,日志密度L,好友密度F。其中H,L,F是可以观察到的值,而我们最关系的R是无法直接观察的。这个问题就划归为通过H,L,F的观察值对R进行概率推理。推理过程可以如下表示:

      1、使用观察值实例化H,L和F,把随机值赋给R。

      2、计算。其中相应概率值可以查条件概率表。

      由于上述例子只有一个未知随机变量,所以不用迭代。更一般得,使用贝叶斯网络进行推理的步骤可如下描述:

      1、对所有可观察随机变量节点用观察值实例化;对不可观察节点实例化为随机值。

      2、对DAG进行遍历,对每一个不可观察节点y,计算,其中wi表示除y以外的其它所有节点,a为正规化因子,sj表示y的第j个子节点。

      3、使用第三步计算出的各个y作为未知节点的新值进行实例化,重复第二步,直到结果充分收敛。

      4、将收敛结果作为推断值。

      以上只是贝叶斯网络推理的算法之一,另外还有其它算法,这里不再详述。

这篇关于算法杂货铺——分类算法之贝叶斯网络(Bayesian networks)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1065380

相关文章

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

Linux系统配置NAT网络模式的详细步骤(附图文)

《Linux系统配置NAT网络模式的详细步骤(附图文)》本文详细指导如何在VMware环境下配置NAT网络模式,包括设置主机和虚拟机的IP地址、网关,以及针对Linux和Windows系统的具体步骤,... 目录一、配置NAT网络模式二、设置虚拟机交换机网关2.1 打开虚拟机2.2 管理员授权2.3 设置子

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

SpringBoot使用OkHttp完成高效网络请求详解

《SpringBoot使用OkHttp完成高效网络请求详解》OkHttp是一个高效的HTTP客户端,支持同步和异步请求,且具备自动处理cookie、缓存和连接池等高级功能,下面我们来看看SpringB... 目录一、OkHttp 简介二、在 Spring Boot 中集成 OkHttp三、封装 OkHttp

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Linux系统之主机网络配置方式

《Linux系统之主机网络配置方式》:本文主要介绍Linux系统之主机网络配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、查看主机的网络参数1、查看主机名2、查看IP地址3、查看网关4、查看DNS二、配置网卡1、修改网卡配置文件2、nmcli工具【通用

使用Python高效获取网络数据的操作指南

《使用Python高效获取网络数据的操作指南》网络爬虫是一种自动化程序,用于访问和提取网站上的数据,Python是进行网络爬虫开发的理想语言,拥有丰富的库和工具,使得编写和维护爬虫变得简单高效,本文将... 目录网络爬虫的基本概念常用库介绍安装库Requests和BeautifulSoup爬虫开发发送请求解

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为