基于条件独立性测试的贝叶斯网结构学习改进算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于条件独立性测试的贝叶斯网结构学习改进算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要: 针对基于条件独立性测试贝叶斯网结构学习算法在删除完全图边时的不足，提出加入对节点x和y的互信息测试的改进算法，不但能充分考虑到D-分离原理中存在的3种图型结构，使学习到的网络结构更接近于解，而且还从一定程度上减少了三角团的存在，从而也将低了确定边方向时出现环路的概率.并通过实验证明改进算法是有效、可行的.

关键词: 贝叶斯网；D-分离；条件独立测试；机器学习

中图分类号:TP 183 文献标志码:A 文章编号:1672-8513(2011)05-0402-04

An Improved Bayesian Network Structure Learning Algorithm Based on the Conditional Independence Test

ZHAO Bo1,WU Qingchang1,YIN Shitang2, FAN Jing1

（1. Key Laboratory of Wireless Sensor Networks,Yunnan University of Nationalities,Kunming 650031, China；2. School of Continuing Education, Yunnan University of Nationalities, Kunming 650031, China）

Abstract: For solving the defects of Bayesian network structure learning algorithm based on the conditional independence test, the paper proposes an improved algorithm that adds the mutual information between node x and y. The algorithm takes into account adequately the three existing graphical structures in the theory of D-separate. The algorithm can reduce the triangulated clique and the probability of the cyclic route in a directed graph. The network structure produced by the algorithm is closer to solution. The experimental results show that the algorithm is effective and feasible.

Key words: Bayesian network; D-separate;conditional independence test; machine learning

贝叶斯网（Bayesian Networks）是表示变量间概率依赖关系的有向无环图.其结构由2部分组成：首先是表示论域中各变量以及变量之间因果关系的有向无环图(DAG)，图中的每一节点表示论域中的一个概念，在节点间的有向弧表示概念之间存在的因果关系，其中弧尾（初始点）表示因，弧头（终端点）表示果；其次，每一节点都附有在给定其父母节点状态时该节点取不同值的条件概率表CPT（或称的条件概率分布函数CPD），其刻化了概念之间的概率依赖强度，因此，贝叶斯网的结构蕴涵了表示现实世界中客体的条件概率分布与因果联系规则，而伴随各节点的条件概率则表达了某种知识.叶斯网作为随机变量间概率关系的图形表示，已成为专家系统中进行数据建模、不确定性推理的重要方法之一.

在贝叶斯网的研究中如何通过对已有的大量数据实例进行分析，从数据中发现问题领域变量之间的关联关系，建立能准确描述系统行为特性,且结构简单、便于信息处理及推理的系统结构模型一直是其重要的研究课题之一.迄今为止,已经提出了很多贝叶斯网结构学习算法，其中典型的有基于打分搜索的结构学习和基于依赖分析的结构学习2类.利用信息论中的条件互信息来作为变量相互间依赖关系的度量而进行条件独立性测试，得到贝叶斯网络结构的方法［1-2］是基于依赖分析方法中的一种.作者在讨论该方法的基础上，针对其算法存在的问题提出了相应的改进，并给出了改进后的算法.

1 贝叶斯网及其条件独立性测试算法

1.1 贝叶斯网

定义1：贝叶斯网是表示变量间概率依赖关系的有向无环图N =，这里每个节点x∈X表示领域变量，每条边e∈E表示变量间的概率依赖关系，每个节点对应的条件概率分布表(CPT)指明了该变量与父节点之间概率依赖的程度，θ表示CPT的参数.其中对于网络中的变量x1,x2,…,xn，在给定由网络假设的条件独立性时，变量之间的概率联合分布可表示为：

P(X1,X2,…,Xn)=∏ni=1P(XI|pa(Xi)).

1.2 条件独立性测试算法

条件独立性测试结构学习算法将贝叶斯网络看作是反映了变量间独立性关系的图结构.常用的条件独立性测试的方法有卡方(χ2)测试和条件互信息测试2种［3］.本文主要讨论基于条件互信息的条件独立性测试方法［1-2］，为此先给出信息论中的互信息和条件互信息的概念.

定义2：设X，Y，Z为3个不相交的变量集，则X，Y的互信息为：

I(X,Y)=∑ri=1∑qj=1P(xi,yj)logp(xi,yi)p(xi)p(yi).

定义3：设X，Y，Z为3个不相交的变量集，则给定Z的条件下，X和Y的条件互信息为：

I(X,Y|Z)=∑ri=1∑qj=1∑sk=1p(xi,yi,zk)logp(xi,yi,zk)p(xi|zk)p(yj|zk) .

其中r，q，s为X，Y，Z的取值个数.

在贝叶斯网中互信息反映的是2个变量x,y之间的相互依赖程度，而条件互信息反映的是在给定另一变量z的条件下，2个变量x,y之间的相互依赖程度.则有I(x,y)＝0时，变量x,y相互独立；I(x,y|z)=0时，变量x,y在给定z的条件下相互独立.

基于条件互信息的条件独立测试方法首先根据样本数据集D导出的采样统计，计算各节点对在给定条件z时的条件互信息，若条件互信息小于某个给定的阈值ε时，认为该节点对条件独立，则删除两节点之间连接的边，从而获得与解比较接近的无向图(以下称为Markov网)；然后再由发现的Markov网，根据表示的联合概率函数相等，得到与其等价的Bavesian网［1］或利用相互依赖度［2］来给无向边确定方向，得到贝叶斯网.

2 对基于条件互信息的条件独立性测试结构学习方法的改进

2.1 D-分离与变量独立

定义4：2个随机变量（事件）X和Y相互独立，即变量X不影响变量Y，变量Y也不影响变量X，则有下式成立：

P(X,Y)=P(X)P(Y).(4)

可以理解为：对变量Y的了解不会影响变量X的信度；同样，对变量X的了解也不会影响变量Y的信度.

定义5：设有3个随机变量X，Y，Z，其中P(Z=z)>0，则X,Y在给定Z的条件下相互独立，则有下式成立：

P(X,Y|Z)=P(X|Z)P(Y|Z)(5)

条件独立性可以用贝叶斯网结构方便地表示出来.用贝叶斯网表示的条件独立在知识表示、推理、学习方面起到了简化作用，使得贝叶斯网的计算复杂性得到降低，可用性和实用性大大增强［5］.

在贝叶斯网中，2个变量X和Y如果直接相连，则表示他们之间有直接依赖关系，对X的了解会影响对Y的信度.如果2个变量X和Y不直接相连，那么信息需要通过他们之间的其他变量才能在两者之间传递，如果X和Y之间的所有信息通路都被阻塞，那么信息就无法在他们之间传递.这时，对其中一个变量的了解不会影响对另一个变量的信度，因而X和Y相互条件独立.从图论角度出发，在贝叶斯网中可以利用变量之间的有向分隔(D-分离)来判断变量之间的条件独立.

D-分离(D-separate)：设X，Y，Z是有向无环图G中的3个不相交的节点集，则如果对X到Y中的1条路径β满足以下条件之一，则称路径β被Z所阻塞.

1) β上有1节点在Z中，且1条弧以该节点为头，1条弧以该节点为尾；

2) β上有1节点在Z中，且路径上的2条弧都以该节点开始；

3) β上有1节点，路径上的2条弧都以该节点为头，但该节点和它的后代节点均不在Z中.

如果X和Y之间的所有路径都被Z阻塞则称Z 有向分隔X与Y，简称Z D-分离X和Y，记为D.

上述D-分离的3种情况如图1所示.其中，(a)中的节点V称为顺连节点，(b)中的节点V称为分连节点，(c)中的节点V称为汇集节点.

当路径中的节点是顺连(a)或分连(b)时，在已知Z的条件下，从X来的信息不能影响变量V的信度，从而不会通过V影响变量Y的信度；而特别值得注意的是：当路径中的节点是汇集(c)时，则与顺连和分连2种情况相反，即在未知V的条件下，从X来的信息会从变量V处“漏掉”，从而不会通过V影响变量Y的信度，而在V已知时，“漏洞”被堵上，从X来的信息将会通过V影响变量Y的信度.

设X，Y，Z是有向无环图G中的3个不相交的节点集，如果Z D-分离X和Y，则X和Y在给定Z时条件独立，记为I(X,Z,Y).

2.2 基于条件互信息的条件独立测试结构学习方法存在的问题及改进

基于条件互信息的条件独立性测试结构学习方法存在的问题是：在进行条件独立性测试时，只计算条件互信息I(x,y|Z)，即只考虑在给定变量z的条件下变量x,y之间的相互依赖程度的情况，且将计算I(x,y|Z)时的Z定义为Z=U-x-y（U为所有变量的集合），这样算法将会忽略D-分离中的汇集节点的情况（图1 (c)所示）.因为Z定义为Z=U-x-y，则使可能存在的汇集节点v以及v的后代节点包含在Z中(如图2(a)所示)，根据D-分离的原理，在汇集结构中当Z给定时，节点x与y相互依赖，当Z未给定时节点x与y相互独立.此时有：

I(x,y|Z)>I(x,y)，

即变量x,y之间的相互依赖程度原本很小，而在给定Z时变量x,y之间的相互依赖程度却增加了，这样在汇集连接结构中会使节点x和y之间本不应存在的边存在(如图2(b)所示).因此原有的基于条件互信息的条件独立性测试结构学习方法可能得不到与解比较接近的Markov网，从而得不到与解比较接近的贝叶斯网，并且由于节点x,v,y的每2个节点之间都存在边(即有边（x,v）,(x,y),(v,y)存在)，将在之后将Markov网转换成贝叶斯网的过程中，给无向边确定方向时增加存在环路的概率.

因此对原方法做出的改进是：根据样本数据集D导出的采样统计，计算各节点对的条件互信息和互信息，若条件互信息小于某个给定的阈值ε1时，认为在给定Z时该节点对条件独立，则删除两节点之间连接的边，若互信息小于某个给定的阈值ε2时，认为该节点对在未给定Z时相互独立，则删除两节点之间连接的边，从而获得与解比较接近的Markov网.

改进后的算法如下：

Get_markov(g,d, e1,e2)

//改进后的基于条件互信息的条件独立性测

//试获得Markov网算法

输入：g:1个包含变量集U的完全无向图；

d:1组关于X的完整数据；

e1:阈值ε1； e2:阈值ε2

输出：一个保留了有依赖关系的结点之间边的Markov网

begin

for(g中的每一节点对x,y)

i_xyI(x,y)；

//计算节点对x,y的互信息

i_xy_zI(x,y|Z)；

//计算节点对x,y的条件互信息,其中Z=U-x-y

if(i_xy_z

if(i_xy

end for

return(g)；

end

2.3 算法分析

由于算法中计算互信息I(x,y)和条件互信息I(x,y|Z)是根据由样本数据得到的一个联合概率函数表，在遍历这个联合概率函数表的过程中可以根据x,y,Z的具体取值分别进行条件测试而统计得到互信息I(x,y)和条件互信息I(x,y|Z)，其程序结构是由一些个分支选择结构组成，不会增加循环结构，所以改进算法的时间复杂度只是在原有算法的基础上增加了1个常数n，其中n等于联合概率函数表中的元组数.

例如假设我们关心的只是样本数据的G,M,B,L 4个属性，则将样本数据(关系表)进行投影，并统计元组ti=( g1, m1, b1,l1 )在样本中出现的频率，作为ti的概率p(ti)，得到样本数据的联合概率函数表如表1所示：

而根据定义2、3计算互信息I(x,y)和条件互信息I(x,y|Z)的程序只是在从第1条元组到最后1条元组的遍历过程中的分支选择结构.

3 实验证明

已知存在一个贝叶斯网［4］如图3所示：

则根据以上样本数据的联合概率函数表计算各节点对之间的互信息I(x,y)和条件互信息I(x,y|Z)为：

结果发现节点B和L之间的条件互信息I(x,y|Z)=0.024902，互信息I(x,y)=0.000041882，则I(x,y|Z)>I(x,y).显然，节点B和L之间的条件互信息在给定Z={G,M}的条件下增加了.在进行条件独立性测试时，如果只考虑节点对之间的条件互信息I(x,y|Z)，会使得原本不应该有的边(B,L) 存在(如图4所示).因此算法得证.

4 结语

在进行条件独立性测试算法中加入对节点x和y的互信息测试的改进算法，不但能充分考虑到D-分离原理中存在的3种图型结构，使学习到的网络结构更接近于解，而且还从一定程度上减少了三角团的存在，从而也减低了确定边方向时出现环路的概率，其算法的时间复杂度只是在原算法的基础上增加常数n.因此本改进算法是有效、可行的.

参考文献:

［1］何盈杰,刘惟一.由Markov网到Bayesian网［J］.计算机研究与发展,2002,39(1):87-98.

［2］聂文广,刘惟一,杨运涛,等.基于信息论的Bayesian网络结构学习算法研究［J］.计算机应用,2005,25(1):1-3.

［3］冀俊忠,阎静,刘椿年.基于I-B and B-MDL的贝叶斯网结构学习改进算法［J］.北京工业大学学报,2006,32(5):436-441.

［4］NILSSON N J.人工智能［M］. 郑扣根,庄越挺,译.北京:机械工业出版社，2006.

［5］张连文,郭海鹏.贝叶斯网引论［M］.北京:科学出版社，2006.

［6］赵波,吴庆畅,高联雄,等.学生就业贝叶斯网模型的构建与推理［J］.云南民族大学学报：自然科学版，2008,17(4):358-361.

收稿日期:2011-05-24.

基金项目:国家自然科学基金（60963026）.

作者简介:赵波(1971-)，男，硕士，副教授.主要研究方向：数据库技术、数据挖掘.