第３７卷　

Ｖｂｌ３７　第７期　

ＮＯ．７　计算机工程　

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　２０１１年４月　

Ａｐｒｉｌ　２０１１　

・软件技术与数据库・　文章编号：ｌｏ０　－３４２８（２０１１）０７—＿ｏ０６２—＿０３　文献标识码：Ａ　中图分类号：ＴＰ３１１　

基于互信息的贝叶斯网络结构学习算法　

王越，谭暑秋，刘亚辉　

（重庆理工大学计算机科学与工程学院，重庆４０００５０）　

摘要：贝叶斯网络结构学习是贝叶斯网络构建的核心，有效的结构学习算法是构建最优网络结构的基础。基千此，提出一种基于互信息　

的贝叶斯网络结构学习算法，该算法可以挖掘｝Ｊｊ数据集各属性中存在的隐含依赖关系，适时地对数据集进行降维操作，从而提高算法的效　

率，并可保证结果的准确性。实验结果表明，与常用的依赖分析算法ＳＧＳ相比，在结果相似的情况下，该算法执行艘率更高。　

关健词：贝叶斯网络；结构学习；互信息　

Ｂａｙｅｓｉａｎ　Ｎｅｔｗｏｒｋ　Ｓｔｒｕｃｔｕｒａｌ　Ｌｅａｒｎｉｎｇ　Ａｌｇｏｒｉｔｈｍ　

Ｂａｓｅｄ　ｏｎ　Ｍｕｔｕａｌ　Ｉｎｆｏｒｍａｔｉｏｎ　

ＷＡＮＧ　Ｙｕｅ，ＴＡＮ　Ｓｈｕ－ｑｉｕ，ＬＩＵ　Ｙａ－ｈｕｉ　

（Ｃｏｌｌｅｇｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｃｈｏｎｇｑｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈｏｎｇｑｉｎｇ　４０００５０，Ｃｈｉｎａ）　

［Ａｂｓｔｒａｃｔ］Ｂａｙｅｓｉａｎ　ｎｅｔｗｏｒｋ　ｓｔｒｕｃｔｕｒａｌ　ｌｅａｒｎｉｎｇ　ｐｌａｙｓ　ａ　ｖｅｒｙ　ｉｍｐｏｒｔａｎｔ　ｒｏｌｅ　ｉｎ　ｔｈｅ　ｐｒｏｃｅｓｓｉｎｇ　ｏｆ　Ｂａｙｅｓｉａｎ　ｎｅｔｗｏｒｋ’Ｓ　ｃｏｎｓｔｒｕｃｔｉｏｎ，ａｎｄ　ａｎ　ｅｆｆｅｃｔｉｖｅ　

ｓｔｒｕｃｔｕｒａｌ　ｌｅａｒｎｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｔｈｅ　ｂａｓｅ　ｏｆ　ｃｏｎｓｔｒｕｃｔｉｎｇ　ｔｈｅ　ｏｐｔｉｍｕｍ　Ｂａｙｅｓｉａｎ　ｎｅｔｗｏｒｋ．Ａｎ　ａｌｇｏｒｉｔｈｍ　ｏｆ　Ｂａｙｅｓｉａｎ　ｎｅｔｗｏｒｋ　ｓｔｒｕｃｔｕｒａｌ　ｌｅａｒｎｉｎｇ（ｃａｌｌｅｄ　Ｍ｜ＢＮＳ）ｂａｓｅｄ　ｏｎ　ｍｕｔｕａｌ　ｉｎｆｏｒｍａｔｉｏｎ　ｉｓ　ｐｒｏｐｏｓｅｄ　Ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｃａｎ　ｇｉｖｅ　ｔｈｅ　ｃｏｎｃｅａｌｅｄ　ｄｅｐｅｎｄｅｎｃｙ　ｒｅｌａｔｉｏｎｓｈｉｐｓ　ａｍｏｎｇ　ｄａｔａ　ａｔｔｒｉｂｕｔｅｓ，ａｎｄ　ｍａｋｅ　

ｄｉｍｅｎｓｉｏｎ　ｒｅｄｕｃｔｉｏｎ　ａｔ　ｔｈｅ　ｒｉｇｈｔ　ｍｏｍｅｎｔ，ｗｈｉｃｈ　ｃａｎ　ｉｍｐｒｏｖｅ　ｔｈｅ　ｐｅｒｆｏｒｍｅｄ　ｅｆｆｉｃｉｅｎｃｙ　ａｎｄ　ｅｎｓｕｒｅ　ｔｈｅ　ａｃｃｕｒａｃｙ　ｒａｔｅ　Ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔ　ｓｈｏｗｓ　ｔｈａｔ　

ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｅｆｆｅｃｔｉｖｅ．Ｃｏｍｐａｒｅｄ　ｗｉｔｈ　ｔｈｅ　ＳＧＳ，ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｏｆＭＩ／￣ＮＳ　ｉｓ　ｍｏｒｅ　ｅｆｆｅｃｔｉｖｅ　ｉｎ　ｔｈｅ　ｓｉｍｉｌａｒ　ｒｅｓｕｌｔｓ　

［Ｋｅｙ　ｗｏｒｄｓ］Ｂａｙｅｓｉａｎ　ｎｅｔｗｏｒｋ；ｓｔｒｕｃｔｕｒａｌ　ｌｅａｒｎｉｎｇ；ｍｕｔｕａｌ　ｉｎｆｏｒｍａｔｉｏｎ　

Ｄ０ｈ　１　０．３９６９／ｊ．ｉｓｓｎ．１　０００—３４２８　２（）１　ｌ　０７　０２　１　

１概述　

贝叶斯网络是一种进行强有力推理的工具，它通过将图　

论知识与概率论知识的结合，可以方便地表示和分析不确定　

性和概率性的事物。由于贝叶斯网络具有独特的不确定表达　

形式、丰富的概率表达能力和综合先验知识的增量学习特性，　

使其成为数据挖掘等众多方法中的研究热点之一。　

学习贝叶斯网络就是要寻找一种网络，能按某种测度较　

好地与给定实例数据集拟合。就一般意义而言，寻找一种网　

络包括寻找一种有向无环图（Ｄｉｒｅｃｔｅｄ　Ａｃｙｃｌｉｃ　Ｇｒａｐｈ，ＤＡＧ）结　

构和获得与ＤＡＧ中每个结点相关的条件概率表。前者称为　

网络结构学习，后者称为网络参数学习。因此，结构学习是　

学习贝叶斯网络的核心，有效的结构学习方法和算法是构建　

最优网络结构的基础。网络结构学习就是通过对给定的样本　

数据集的学习，从大量的结构中选出最适合该数据集的网络　结构川。　

现有的主要贝叶斯网络结构学习方法有２类　ｌ：一类是　

基于打分一搜索的学习方法，其原理是按照一定的搜索策略及　

评分准则构建贝叶斯网络结构；另一类是基于依赖关系的学　

习算法，这类方法通常利用统计或信息论的方法定量地分析　

变量间的依赖关系获取最优的表达这些关系的网络结构。其　

中一个比较常见的算法是ＳＧＳ（Ｓｐｉｒｔｅｓ．Ｇｌｙｍｏｕｒ　ａｎｄ　Ｓｃｈｅｉｎｅｓ）　

算法。此算法不需要结点有序的贝叶斯网络结构学习算法。　

它能够自动为由条件独立（ｃＩ）测试学习而得到网络结构中的　

边定向，但缺点是要求指数级的ｃＩ测试　。ｊ。　

本文结合信息论中互信息的知识，提出一种基于互信息　

的贝叶斯网络结构学习算法（Ｍ１ＢＮＳ）。该算法通过互信息的　知识能够挖掘出各属性之间的一种依赖关系，并利用这种依　

赖关系确定贝叶斯网络结构。由于算法执行过程中适时地对　

数据集进行降维，效率得到了提高，同时可以保证结果的正　

确性。实验结果证明该算法是有效的，与传统ＳＧＳ算法比较　

的实验结果显示，数据集属性维度越高，本算法效率也越高。　

２贝叶斯网络及其模型　

贝叶斯网络是一个有向无环图（ＤＡＧ），它可表示为一个　

三元组Ｇ：（Ⅳ，Ｅ，Ｐ）。其中，Ｎ：｛Ｘ　，Ｘ　，…，　｝是一组结点的集　

合，每个结点代表一个变量（属性）。Ｅ＝｛（　，　ｆ）ｌ　ＸＪ，　，　，∈Ｎ｝　

是一组有向边的集合，每条边（ｘｉ，Ｘ　）表示Ｘｉ，　，具有依赖关系　

Ｘｉ　Ｘ，。Ｐ＝｛．１，（　ｌ　）｝是一组条件概率的集合，其中，Ｐ（Ｘｉｌｌｒｉ）　

表示Ｘｉ的父结点集　，对Ｘｉ的影响。贝叶斯网络实质上就是一　

个联合概率分布ｐ（ｘ．，　，…，　，　）所有条件独立性的图形化表　

示，其中，互为Ｘｉ父亲结点集　。　

构造贝叶斯网络（先验贝叶斯网络）一般分为以下３个步　

骤：（１）确定变量集和变量域；（２）确定网络结构；（３）确定局部　

概率分布。其中，确定网络结构有如下３种方法：　

方法１根据变量之问的条件独立性确定弧的存在性，根　

据变量之间条件相对预测能力（或条件相对互信息）确定弧的　

基金项目：重庆市科技攻关计划基金资助项目（ＣＳＴＣ，２００９ＡＢ２０４９，　

ＣＳＴＣ，２００９ＡＣ２０６８）　作者简介：王越（１９６１一），男，教授，主研方向：数据挖掘，数据　

库技术，嵌入式系统；谭暑秋，硕士研究生；刘亚辉，硕士　

收稿日期：２０１０－０９—１７　Ｅ－ｍａｉｌ：ｗａｎｇｙｕｅ＠ｃｑｉｔ．

ｅｄｕ　ｃｎ　第３７卷第７期　王越，谭暑秋，刘亚辉：基于互信息的贝叶斯网络结构学习算法　６３　

方向。　

方法２用户根据变量之间的因果关系（根据用户的已有　

知识）来建立网络结构。　

方法３方法１与方法２结合使用。　

３互信息理论　

互信息是信息论中的一个中心概念，它描述了某个变量　

取值对另一个变量取值的确定能力。其值越大，表明２个变　

量间的确定能力越强　。具体概念定义如下：　

定义（互信息）设ｘ，Ｙ，Ｚ为３个不相交的属性变量，称：　

／　，　、　、　）：圭　（ｑ，Ｙｊ）ｌｂ　）为Ｘ，Ｙ的互信息。，（　，），）＝∑∑　（ｊ　Ｊ　—　：　Ｊ为　，　的互信息。　

。，＝　＼Ｐ（Ｘｉ）Ｐ（Ｙｊ，　

／　，　．　、　、　ｌ（Ｘ，Ｙ　Ｊｚ）＝圭兰主ｐ（　，　）Ｊｂ　Ｊ＿　｝为给定Ｚ　‘　＼ｐｔｘ

ｉ’ｚ＾）Ｐ（Ｙｊ。ｚ＾Ｊ』　

的条件下，ｘ和ｙ的互信息（条件互信息）。其中，ｒ．ｑ，ｓ为　，　

Ｚ的状态个数；，Ｊ（　，Ｙ，，　）为（　，Ｙ，Ｚ）的状态为（ｘ　，ｙ　，　）　

时的概率。　

定理川互信息ｔ（ｘ，　和ｉ（ｘ，ｙ｝ＺＪ具有如下性质：　

（ｉ）对称性，即Ｉ（Ｘ，　＝，（　ｘ）和，（ｘ，　ｚ）：，（ｙ，ｘＩ　Ｚ）。　

（２）非负性，即Ｉ（Ｘ，　≥０和ｔ（Ｘ，ＹＩＺ）≥０。而且，当且仅　

当ｘ和Ｙ条件独立时有，（ｘ，ｙ）＝Ｏ。同理，有当且仅当在给定　

条件ｚ，ｘ和Ｙ条件独立时有ｌ（Ｘ，ＹＩＺ）＝Ｏ。　

４基于互信息的新结构学习算法　

假设训练数据集是完整的，且假设每个结点ｘ对其所有　

父结点　，　、，…，　的依赖是互相独立的。由于给出的数据集　

实例中，各个属性值一般不全是离散性的，因此首先要对数　

据集进行离散化预处理。　

第１步属性值离散化。　

对连续性的数据，一般采取将连续变量的取值区问分为　

若干个区域，使连续变量转化为离散变量。其中，属性值用　

数学家史特吉斯（Ｓｔｕｒｇｅｓ）提出的ｋ＝１＋３　３２１ｂｎ决定所分数据　

的组数，其中规定ｎ为训练集的数据量，则数值型属性值ｘｉ　

如果在［ｍｉｎ＋ｆｘ（（ｍａｘ～ｍｉｎ）／　），ｍｉｎ＋（１＋１）ｘ（（ｎｍｘ—ｍｉｎ）／ｋ））区　

问内，则离散化后的值为，，其中，ｌ＝０—１－－，ｒ　］；ｒａｉｎ是属　

性列中的最小值；ｍａｘ是属性列中的最大值。　

第２步建立无向图。　

设一个数据集Ｄ有Ｊｖ个变量｛Ｘ，，Ｘ　一，ｘ，　），所建立的　

无向图为Ｐ＝｛＜Ｘ，，Ｘ　＞），其中，ｉ，　＝１，２，…，ｉ＇ｌ，且　≠Ｊ。　

设Ｕ＝｛ｘ　，ｘ　・，　，　）为属性全集，依次对每一对属性　

，，ｘ，∈Ｕ计算互信息，其中，Ｘ　≠Ｘ　。给定一个阈值　，　

当Ｊ（ｘ　，ｘ，）‘　时，连接边ｘ　一ｘ，，其中，　通常取一个很　

小的正数。　

第３步对无向图进行删剪。　

从上面所给的性质可得到一个判断　，ｙ是否条件独立的　

算法：当给　一个概率分布ｐ（　）时，可以通过判断　

，（　，Ｙ　ｉ　ｚ）＝ｏ来代替ｉ（ｘ，ｚ，ｙ）。其中，ｔ（ｘ，ｚ，＇，）表示在给定　

ｚ的条件下，ｘ独立于ｙ，即：ｐ（Ｘ　ｆ　ｌ，，ｚ）＝ｐ（ｘ　ｆ　ｚ）和　

ｐ（ＹＩｘ，ｚ）：ｐ（ＹＩｚ）。当ｌ（ｘ，ＹＩｚ）＝ｏ时，则有，（　，ｚ，ｙ）条　

件独立性成立，从而Ｐ图中的ｘ，一ｘ，边可以删除；否则在给　

定条件ｚ的情况下，ｘ和Ｙ则互相依赖。　

然而在实际计算中并没有一个真正的概率分布ｐ（ｘ），只　

是有一个基于样本数据集Ｄ而计算的一个经验概率分布　

ｐ，，（　）来近似估计　（　），计算的ｌ（ｘ，Ｙ　１　ｚ）只是基于ｐ，　（　）上　的，　（ｘ，ＹＩｚ）的近似值，所以，它的值总是大于ｏ。为此，　

可把判断条件独立方法描述为：设　为属性全集，　

ｘ　，ｘ，∈Ｕ（ｉ，　＝１，２，’一，ｎ），Ｘ，≠Ｘ，，且Ｃ　（　＝１，２，・一，　）∈Ｃ。　

其中，ｃ是类属性集。给定一个闽值ｅ，，如果有Ｉ（Ｘ，Ｙｌｃ）＜ｅ，　

则判定给定Ｃ，ｘ与ｙ条件独立；否则给定Ｃ，Ｘ与ｙ是条　

件依赖的。　

第４步建立有向图Ｐ　。　

设存在边即　，一ｘ．，如何确定边的方向，这里运用各属　

性与类属性之间的互信息判断边的方向。给定一个闽值ｅ　：　

ｎ）当＼“ｘ　，Ｃ）－ｌ（ｘ　，Ｃ）　ｅ３戳，耨在ｘ　＿｝Ｘ　且Ｘ　＿÷ｘ　，　

即．）（　Ｈ　ｘ　。　

（２）当Ｊ，（　，ｃ）－ｔ（ｘ，，ｃ）｝＞乞，且／（ｘ，，ｃ）＞，（　，，ｃ）时，　

存在ｘ　ｘ，；反之则存在ｘ，　ｘ，。　

由算法可知，在处理过程中可能存在　，　ｘ，Ｒｘ　

２条边同时都存在的情况，这说明在贝叶斯网络中结点ｘ，和　

结点ＪＹ　存在着互相依赖。在这种情况Ｆ，一个训练数据集就　

会存在着多种可能性的贝叶斯网络。　

第５步利用专家知识做出判断。　

对第４步产生的多种可能性的贝叶斯网络结构进行评　

价，最终选择一些最有可能性的结果作用于本文的目标。　

ＭＩＢＮＳ算法主要伪代码如下：　

Ｉｎｐｕｔ数据训练集Ｄ，非类属性集Ｘ，类属性Ｃ，阈值ｅ　，ｇ，，巳　Ｏｕｔｐｕｔ贝叶斯网络图尸　

调用数据离散化方法　／　ＤｉｓｃｒｅｔｉｚｅｆＤ１；　

／　构造无向图Ｐ　／　

ＦＯＲ　ｉ　ＦＲＯＭ　１　Ｔｏ　ｎ　其中ｎ是非类属性的属性个数　／　ＦＯＲｊ　ＦＲＯＭｊ＋１　ｔｏ　ｎ　

ＩＦ　Ｉ（Ｘ　，Ｘ，）＞ｅ１　Ｐ＝ＰＵ｛＜Ｘ．，ｘ　＞）；　

ＥＮＤＩＦ；　ＥＮＤ　ＦＯＲ：　ＦＯＲｊ　ＦＲＯＭ　１　ＴＯ　ｍ／丰其中，１３１是类属性的属性个数　／　

ＩＦ　ｉ（ｘ　，ｃ　）＞ｅ１　Ｐ＝ＰＵ｛＜Ｃｉ－Ｘ．＞｝；／　其中，”代表无向边　／　

ＥＮＤＩＦ；　

ＥＮＤＦＯＲ：　ＥＮＤＦＯＲ：　／　对无向图Ｐ进行修剪　／　ＦＯＲｉ　ＦＲＯＭ　ｌ　ＴＯ　ｎ一１　

ＦＯＲｊＦＲＯＭｉ＋ｌ　ＴＯ　ｎ　

ＦＯＲ　ｋＦＲＯＭ　１　ＴＯ　Ｈ１　ｌ（Ｘ．，ｘ。ＩＣ）＋＝Ｉ（ｘ　，ｘ　１　ｃｋ）；　ＩＦ　Ｉ（Ｘ　，Ｘ　ＩＣ）＜ｅ，　／：＝：移除无向边＜Ｘ，一Ｘ．＞　／　

Ｐ＝Ｐ一｛＜Ｘ　一Ｘ　＞｝；　ＥＮＤＩＦ；　

ＥＮＤＦＯＲ：　ＥＮＤＦＯＲ；　

ＥＮＤ　Ｆ０Ｒ：　将无向图转变为有向图Ｐ　／　ＦＯＲ　ｋＦＲＯＭ　１　ＴＯｉｎ　ＦＯＲｉ　ＦＲｏＭ　ｌ　ＴＯ　ｎ　

ＦＯＲｊ　ＦＲＯＭ　１　ＴＯ　ｎ　１Ｆ＜Ｘ　，Ｘ，＞ＩＮ　Ｐ　

Ｉ（Ｘ，，Ｃ）＋＝ｌ（Ｘ　，ｃｋ）；