许国强 ,余长州 ,王 林 ,周春蕾 ,高 阳*

（1.江苏方天电力技术有限公司，南京，211102；2.南京大学计算机科学与技术系，南京，210023）

贝叶斯网络（Bayesian network）又称“信念网”（beli ef network），它是定义在一组随机变量X={X1，X2，···，XN} 上的有向无环图（Directed Acyclic Graph，DAG）.每一个变量与图中的某一节点相关联，图中节点间的弧表示对应变量之间的依赖关系，每个节点都有一个概率分布θ.因此一个贝叶斯网B由其结构G和参数Θ两部分构成，可记作贝叶斯网结构能够很好地体现变量之间的条件独立性，其假设每个节点所对应的变量与它的非后裔节点所对应的变量独立［1］，因此可将联合概率分布定义为：

从数据集学习贝叶斯网络结构是贝叶斯网络研究的重要内容之一.目前贝叶斯网络结构学习方法主要分三类［2］：（1）基于约束的结构学习算法，它使用条件独立性检验的方法去学习数据的依赖结构；（2）基于评分的结构学习算法，它定义一个目标评分函数来衡量结构和数据的拟合程度，学习的目标是使结构的评分最大化；（3）混合结构学习算法综合使用上述两类算法，通过约束方法缩减搜索空间，然后基于评分方法搜索最优结构.Scutari et al［2］的实验研究发现：在小样本上基于约束的结构学习算法比基于评分的结构学习算法更加精确，甚至有时会和混合结构学习算法有同样的准确率；但在基于约束的结构学习算法中，因其需要执行大量的条件独立性检验运算，时间复杂度较高.总体来说混合结构学习算法的准确率和计算效率……