第21卷第2期V ol 121N o 12 三明高等专科学校学报JOURNA L OF S ANMI NG C O LLEGE 2004年6月Jun 12004收稿日期:2004204226作者简介:陈秀琼(1969-),女,福建尤溪人,三明高等专科学校计算机科学系讲师。
基于贝叶斯网络的数据挖掘技术陈秀琼(三明高等专科学校计算机科学系,福建三明 365004)摘 要:从海量数据中挖掘有用的信息为高层的决策支持和分析预测服务,已成为网络时代人们对信息系统提出的新的需求,但我们发现数据处理和数据的提炼技术是匮乏的。
起源于贝叶斯统计学的贝叶斯网络以其独特的不确定性知识表达形式、丰富的概率表达能力、综合先验知识的增量学习方法等特性表示了客体的概率分布和因果联系,成为当前数据挖掘众多方法中最为引人注目的焦点之一。
本文首先对贝叶斯网络、贝叶斯网络推理和贝叶斯网络学习进行综合性的阐述,然后讨论其在数据挖掘中的应用和优势。
关键词:贝叶斯网络;贝叶斯推理;贝叶斯学习;数据挖掘中图分类号:O211 文献标识码:A 文章编号:1671-1343(2004)02-0047-06随着计算机网络和存储技术的迅猛发展,数据传播和积累的速度不断提高,我们迫切需要强有力的数据挖掘工具从海量数据中挖掘有用的信息,为高层的决策支持和分析预测服务。
起源于贝叶斯统计学的贝叶斯网络以其独特的不确定性知识表达形式、丰富的概率表达能力、综合先验知识的增量学习方法等特性表示了客体的概率分布和因果联系,利用其模型进行数据挖掘能从数据库中挖掘出多层、多点的因果概念联系,推理出客观世界客体间存在的普遍联系,因此成为当前数据挖掘众多方法中最引人注目的焦点之一[1]。
1 贝叶斯网络图1 贝叶斯网络结构示例贝叶斯网络(Bayesian netw ork ),又叫概率因果网络、信任网络、知识图等,是一种有向无环图[2]。
一个贝叶斯网络由两个部分构成:(1)具有k 个节点的有向无环图G (如图1)。
图中的节点代表随机变量,节点间的有向边代表了节点间的相互关联关系。
节点变量可以是任何问题的抽象,如测试值、观测现象、意见征询等。
通常认为有向边表达了一种因果关系,故贝叶斯网络有时叫做因果网络(causal netw ork )。
重要的是,有向图蕴涵了条件独立性假设,贝叶斯网络规定图中的每个节点V i 条件独立于由V i 的父节点给定的非V i 后代节点构成的任何节点子集,即如果用A (V i )表示非V i 后代节点构成的任何节点子集,用∏(V i )表示V i 的直接双亲节点,则 p (V i |A (V i ),∏(V i ))=p (V i |∏(V i ))(1)(2)一个与每个节点相关的条件概率表(C onditional Probabilities T able ,CPT )P 。
条件概率表可以用p (V i |∏(V i ))来描述,它表达了节点同其父节点的相关关系———条件概率。
没有任何父节点的节点概率为其先验概率。
可以按照一个条件概率链来表达一个联合概率,其一般形式为 p (V 1,V 2,...,V k )=∏ni =1P (V i |V i -1...V 1)(2)由图G 和概率表P 构成的网络,称贝叶斯网络。
它通过有向图的形式来表示随机变量间的因果关系,并通过条件概率将这种关系数量化,可以包含随机变量集的联合概率分布,是一种将因果知识和概率知识相结合的信息表示框架。
2 贝叶斯网络的推理贝叶斯网络的推理是指从先验概率入手,按贝叶斯规则沿网络弧线层层演进而计算出我们感兴趣的结点子集的条件概率分布的过程。
从理论上讲,给定一个随机变量集合的完全联合概率函数,就能计算出所有的边缘概率和更低阶的联合概率。
但是当有一个很大的随机变量集合时,指定所有的联合概率或更低阶联合概率的任务就难于处理了(N P -hard 问题)。
但在贝叶斯网络中有很多条件独立性,将条件独立性应用于链接规则式(2),便可得 P (V 1,V 2...,V k )=∏ni =1P (V i |∏(V i ))(3)用式(3)表达图1中变量的联合概率,可得 p (V 1,V 2,...,V 6)=∏6i =1P (V i |∏(V i )) =p (V 6|V 5)p (V 5|V 2,V 3)p (V 4|V 2)p (V 3|V 1)p (V 2|V 1)p (V 1)可见,贝叶斯网络表示的变量间条件独立性使得我们只需对每一个结点V i 计算P (V i |∏(V i ),而不是计算概率空间的所有2n 个概率,这使变量的联合概率求解大大简化。
当k 值增大时,需要指定的概率减少将更为显著,这种减少使得难于处理的问题变得容易处理。
虽然独立性简化了概率推理,但对于多连接网络,其概率推理依然是个NP -hard 问题。
第一个被提出来的用于多连接网络概率更新的精确算法的是Pearl 的信息传递方法[3],但该算法仅限于树型网络和单连通网络。
目前,对该算法已经改善并发展了许多的算法,用来把树型传播方法扩展到更一般的多连通网络。
其中常见的有Shachter 的节点排除法、Lauritzen 和S piegelhalter 的小范围树传播方法以及环切断条件方法。
小范围树传播方法又叫做联合树方法,是上述最常见的三种方法之一,其工作原理如下:开始是一个有向网络表示,然后该网络被转变成无向图,同时保持了所有最初的依赖关系,之后无向图被三角化以形成局部节点簇(Clique ),这一结构是树型的。
观测得到的证据通过保证簇的交集的边缘概率的一致来从一个簇传到另一个簇,而不用考虑哪个簇是需要计算的。
最后,当传播过程平静下来,变量的后验概率通过把所在簇的概率分布投射到这个变量上计算出来。
该算法的复杂性与网络中某些三角化的最大簇的大小成指数关系。
幸运的是这些算法的复杂性都可以在实际处理前被估计出来。
如果估计到耗时超出合理的界限,我们就必须用近似的方法来进行更新。
主要的近似方法有:随机方法———根据大数定理用平均值近似大量随机变量;抽样方法———从隐藏变量的分布P (x )中抽取随机样本X ,然后通过它们的似然度P (y |x )来给样本加权。
此外,还有多圈信任网络、参数近似方法等。
这些方法都采取一定的方式在运行时间和推理精度上寻求一个折衷,可在较短的时间内得到一个满足精度要求的结果。
3 贝叶斯网络学习根据用户的先验知识构造的贝叶斯网络称为先验贝叶斯网络,把先验贝叶斯网络和数据相结合而得到的贝叶斯网络称为后验贝叶斯网络,由先验的贝叶斯网络得到后验的贝叶斯网络的过程称为贝叶斯网络学习。
贝叶斯网络能够持续学习,上次学习得到的后验贝叶斯网络可变成下一次学习的先验贝叶斯网络。
每一次学习前用户都可以对先验贝叶斯网络进行调整,使得新的贝叶斯网络更能体现数据中蕴涵的知识,如图2。
图2 贝叶斯网络持续学习图 基于贝叶斯网络的学习包括参数学习和结构学习两个内容,同时根据样本数据的不同性质每一部分均包括实例数据完备、实例数据不完备两个方面。
参数学习方法主要是基于经典统计学的学习和基于贝叶斯统计学的学习条件概率表(CPT )。
结构学习方法主要是基于贝叶斯统计测度方法和基于编码理论测度方法。
以下介绍基于结构的学习。
在贝叶斯网络中,首先定义一个随机变量S h ,表示数据库D 是来自网络结构S 的随机样本假设,并赋予先验概率分布p (S h )表示网络结构的不确定性,然后计算后验概率分布P (S h |D )。
根据Bayesian 定理有 P (S h |D )=P (S h ,D )/P (D )=P (S h )P (D|S h )/P (D )(4)其中:P (D )是一个与结构学习无关的正规化常数,P (D|Sh )是结构似然。
于是确定网络结构的后验分布只需要为每一个可能的结构计算数据的结构似然。
在无约束多项分布、参数独立、采用Dirichlet 先验和数据完整的前提下,数据的结构似然正好等于每一个(i ,j )对的结构似然的乘积,即 P (D|S h)=∏ni =1∏qij =1г(αij )г(αij +N ij )∏ri k =1Г(αijk +N ijk )Г(αijk )(5)该公式由C ooper 和Herskovits 于1992年首次给出[4]。
在一般情况下,n 个变量的可能的网络结构数目大于以n 为指数的函数[5],逐一排除这些假设是很困难的。
可以使用两个方法来处理这个问题:“模型选择”和“有选择的模型平均”。
前者是从所有可能的模型(结构假设)中选择一个“好的”模型,并把它当作正确的模型;后者是从所有可能的模型中选择合理数目的“好”模型,并认为这些模型代表了所有情况。
4 案例研究下面是一个使用贝叶斯网络进行数据采掘和知识发现的应用实例(Sewell 和Shah [6])。
数据来自华盛顿高级中学的10318名高年级学生。
每个学生用下列变量及其相应的状态来描述:性别(SEX ):男、女;社会经济状态(SES ):低、中下、中上、高;智商(I Q):低、中下、中上、高;家长的鼓励(PE):低、高;升学计划(CP):是、否。
目标是从数据中发现影响高中学生上大学意向的因素。
数据已经整理成表1所示的格式。
表1中每个数据表示对于5个变量的某种取值组合统计所得到的人数。
例如,第一个数据表示对(SEX=男,SES=低,I Q=低,PE=低,CP=是)这种组合统计得到的人数为4,第二个数据则表示对(SEX=男,SES=低,I Q=低,PE=低,CP=否)这种组合统计得到的人数为349。
其后的数据表示依次轮换每个变量可能的状态统计得到的人数。
变量依照从右到左的顺序轮换,状态则按照上面列出的各变量状态顺序轮换。
表1 各种状况人数统计表(人)434913649207337212126385410674943 2232278472016495121159392177911959 81664791612074110179214810064219873 4483957547132909412246581741454 5454944531214478216203513962824 112852961192364788121646285151137250 716336721319375901217491100208114277 650365857011076124823081134936098 先假定没有隐藏变量,使用容量为5的等值样本和p(x|S h)服从均匀分布的先验网络。
排除掉SEX和SES有父节点、CP有子节点的网络结构之后,假定其它所有网络结构都是等可能的。
因为数据集是完整的,可以用式(4)和式(5)计算网络结构的后验概率。