第29卷第4期2004年4月武汉大学学报#信息科学版
Geomatics and Information Science of Wuhan U niversity V ol. 29No. 4Apr. 2004
文章编号:1671-8860(2004) 04-0315-04文献标识码:A
贝叶斯网络结构学习及其应用研究
黄解军 万幼川 潘和平
1
1
1
(1 武汉大学遥感信息工程学院, 武汉市珞喻路129号, 430079)
摘 要:阐述了贝叶斯网络结构学习的内容与方法, 提出一种基于条件独立性(CI) 测试的启发式算法。从完全潜在图出发, 融入专家知识和先验常识, 有效地减少网络结构的搜索空间, 通过变量之间的CI 测试, 将全连接无向图修剪成最优的潜在图, 近似于有向无环图的无向版。通过汽车故障诊断实例, 验证了该算法的可行性与有效性。
关键词:贝叶斯网络; 结构学习; 条件独立性; 概率推理; 图论中图法分类号:T P18; T P311
贝叶斯网络学习是贝叶斯网络的重要研究内容, 也是贝叶斯网络构建中的关键环节, 大体分为结构学习和参数学习两个部分。由于网络结构的空间分布随着变量的数目和每个变量的状态数量呈指数级增长, 因此, 结构学习是一个NP 难题。为了克服在构建网络结构中计算和搜索的复杂性, 许多学者进行了大量的探索性工作[1~5]。至今虽然出现了许多成熟的学习算法, 但由于网络结构空间的不连续性、结构搜索和参数学习的复杂性、数据的不完备性等特点, 每种算法都存在一定的局限性。本文提出了一种新算法, 不仅可以有效地减少网络结构的搜索空间, 提高结构学习的效率, 而且可避免收敛到次优网络模型的问题。
述, 在具体问题领域, 内部的变量关系形成相对稳定的结构和状态。这种结构的固有属性确保了结构学习的可行性, 也为结构学习提供了基本思路。贝叶斯网络结构学习是一个网络优化的过程, 其目标是寻找一种最简约的网络结构来表达数据集中变量之间的关系。对于一个给定问题, 学习贝叶斯网络结构首先要定义变量及其构成, 确定变量所有可能存在的状态或权植。同时, 要考虑先验知识的融合、评估函数的选择和不完备数据的影响等因素。
1. 2 贝叶斯网络结构学习的方法
近10年来, 贝叶斯网络的学习理论和应用取得了较大的进展。目前, 贝叶斯网络结构学习的方法通常分为两大类:¹基于搜索与评分的方法, 运用评分函数对网络模型进行评价。通常是给定一个初始结构(或空结构) , 逐步增加或删减连接边, 改进网络模型, 从而搜索和选择出一个与样本数据拟合得最好的结构。根据不同的评分准则, 学习算法可分为基于贝叶斯方法的算法[3, 7]、基于最大熵的算法[8]和基于最小描述长度的算法[1, 2]。º基于依赖关系分析的方法, 节点之间依赖关系的判断通过条件独立性(CI ) 测试来实现, 文献[9, 10]描述的算法属于该类算法。前者在DAG 复杂的情况下, 学习效率更高, 但不能得到一个最优的模型; 后者在数据集的概率分布与DAG 同构的条件下, 通常获得近似最优的模型[11],
1 贝叶斯网络结构学习的基本理论
1. 1 贝叶斯网络结构学习的内容
贝叶斯网络又称为信念网络、概率网络或因果网络。它主要由两部分构成:¹有向无环图(directed acyclic graph, DAG) , 即网络结构, 包括节点集和节点之间的有向边, 每个节点代表一个变量, 有向边代表变量之间的依赖关系; º反映变量之间关联性的局部概率分布集, 即概率参数, 通常称为条件概率表(conditional probability table, CPT) , 概率值表示变量之间的关联强度或置信度。贝叶斯网络结构是对变量之间的关系描
收稿日期:2004-01-23。
项目来源:国家自然科学基金资助项目(60175022) 。
[6]
316武汉大学学报#信息科学版2004年
但运用该方法要求样本数据集具有一定的规模。同样, 条件互信息I (X , Y |Z) 定义为:
I (X , Y |Z) =
X, Y, Z
2 贝叶斯网络结构学习的启发式算
法
2. 1 算法的原理
贝叶斯网络结构学习是通过对给定数据集的学习和训练, 寻找一种最佳的网络来表达变量之间的依赖关系, 即确定变量之间的因果连接集合。本文提出一种贝叶斯网络结构学习的启发式算法, 其基本思路是基于给定数据集, 通过CI 测试, 有效地修剪完全潜在图, 得到一个最优的无向结构或最小潜在图。在给定其他变量子集的情况下, 任何两个变量X 和Y 之间的条件独立性可以通过概率表中的边缘概率和条件概率来判断, 而概率表由给定的数据集直接计算得出。
定义1 如果给定某一问题领域的各个变量, 用一个节点表示其中的一个变量, 由任意两个节点之间的无向边连接构成的图模型, 称为完全潜在图(potential graph, PG) 。
定义2 如果变量X 、Y 和变量集Z 之间存在以下关系:P (X |Z ) =P (X |Y , Z) , 即在变量集Z 已知的条件下, 变量Y 的状态和概率不会造成对变量X 的影响, 称为在给定变量集Z 的前提下, X 条件独立于Y, 记为I (X L Y |Z ) 。
定义3 设X 、Y 和Z 为有向无环图中3个互不相交的节点子集, 如果从X 中一个节点到Y 中一个节点的所有路径之间, 存在节点W 满足下列条件之一:¹W 具有收敛箭头, 且W 或任何W 的子节点不包含在Z 中; ºW 没有收敛箭头, 而且W 存在于节点集Z 中。则称在给定条件集Z 的情况下, X 与Y 为d -分割, 记为D 。
定理1 对网络结构中的节点集X 、Y 和Z, 当且仅当P (X |Y , Z ) =P (X |Z ) 时,
D 成立。
E p (X , Y, Z) #
(2)
p (X |Z) p (Y |Z)
lg
先假设所有的节点之间存在连接, 节点X 和Y 之间连接的潜在性运用条件互信息来计算。在通常情况下, 设定一个较小正实数的阈值E , 当I (X , Y |Z) [E 时, 称X 与Y 被条件集Z 进行d -分割, 即在给定Z 的条件下, X 条件独立于Y, 从而删除X 与Y 之间的连接。经过n (n -1) /2次CI 测试, 最后由完全潜在图修剪成稀疏的理想潜在图。2. 2 算法实现
1) 初始化完全潜在图。
根据给定的具体问题和数据实例, 建立全连接图, 即假设任意两个变量之间都存在依赖关系, 用连接边表示变量之间的关联性, 则可构成完全潜在图。数学模型表示为:
PG =(V, L, 5)
式中,
V ={V 1, V 2, , , V n }L ={(V i -V j ) |V i , V j I 连接边L 的数量为:
|L |=n (n -1) /2
与变量X 相邻的变量数, 初始化有:
A X =V \{X }因此, |A X |=n -1, 其中n =|V |。
2) 融合先验知识。
对于网络中任意两个变量X 和Y, 根据专家知识或先验常识, 设定:
(1) L 0={(X , Y ) }, 表示变量对(X , Y ) 之间存在无向连接的集合;
(2) L 1={(X , Y ) }, 表示变量对(X , Y ) 之间不存在无向连接的集合;
(3) T p 表示初始贝叶斯网络中任意变量的最大父节点数, 可以通过专家知识或先验常识设定一个整数T p
3) 潜在图修剪。
输入完全潜在图, 通过CI 测试, 若CI 测试为真值, 用符号(X L Y |Z) 表示, 变量集Z 的节点数用t p 表示。设C (X , Y ) 表示变量X 和Y 的最小d -分割集, 其算法如下。
(7)
设A X 表示变量X 的直接邻近集, |A X |表示
(8)
V }
5={
(4) (5) (6) (3)
定理2[11] 在依赖模型M 中, 设X 、Y 和Z 为互不相交的子集, 条件独立性(X L Y |Z ) 满足
对称性、分解律和交换律等属性。
定理3[11] 满足对称性、分布律和交换律的依赖模型M, 从完整图中删除任意条件独立性成立的连接(X , Y) , 则产生一个惟一的最小I -map 。
根据信息论, 两个离散随机变量(对应于节点) 的X 和Y 具有联合概率函数p (X , Y) 和边缘概率函数p (X ) 、p (Y), 其平均互信息I (X , Y) 定义为:
I (X , Y) =E p (X , Y) lg (1)
p (X ) () Y
第4期黄解军等:贝叶斯网络结构学习及其应用研究317
for (t p =0; t p
let X =V i , Y =V j , U =V \{X , Y}if((X , Y ) I L 0) , then
set (X , Y) =t p , |A Y |>t p 设Z =(A X G A Y ) \{X , Y}, 计算条件互信息I (X , Y |Z) //结合联合概率表及式(1) 、式(2) 计算if I (X , Y |Z ) [E 即(X L Y |Z ) 成立then 删除X 和Y 之间的连接A X =A X \{Y}, A Y =A
Y
X 与Y 条件独立, 即X 与Y 之间的连接边不存在。在该实例中, 取置信度为95%, 当|Z |=0时, 计算互信息I (X , Y ) , 可删除连接边(1, 2) 、(1, 3) 、(1, 6) ; 同样, 当|Z |=1和|Z |=2的情况下, 根据条件互信息I (X , Y |Z ) , 进行V 2检验, 可删除(1, 8) 、(3, 5) 、(4, 7) 、(7, 8) 等连接边, 结果可得到最小潜在图(图2的无向版) 。运用因果发现算法并结合先验知识, 确定节点之间连接的方向, 构成汽车故障诊断网络, 从而为汽车故障的诊断与维护提供科学依据。
\{X }
图1 汽车故障诊断的完全潜在图
F ig. 1 Fully P G of A utomobile Diag nost ic N etwork
设d -分割集C (X , Y) =Z else set
在以上算法中, 从完全潜在图开始, 由于完全潜在图包含n (n -1) /2条边, 需要n (n -1) /2次CI 测试, 对连接边进行修剪。但是, 先验知识和专家知识的融入可以有效地减少CI 测试, 特别是在网络结构稀疏的情况下, 效果更加明显。由定理2和定理3可知, 算法获得的网络结构为数据集的最小I -map , 但要求样本数据达到一定的规模, 才能保证网络模型的准确性。同时, 算法的效率取决于数据集包含的属性个数和样本规模。
图2 汽车故障诊断的网络模型
F ig. 2 M odel of Automobile Diagnostic N etw ork
该方法不仅可以减少计算的复杂度, 还可以综
3 实例分析
以汽车故障诊断为例, 采用10000个样本记录的数据集, 该领域问题用8个变量及其状态表示为:¹油压(正常、低、无) ; º风扇带(紧、松、断裂) ; »电池(满、弱、失效) ; ¼温度(正常、高、极高) ; ½系统正常(是、否) ; ¾汽车边灯(正常、熄灭) ; ¿汽车前灯(正常、熄灭) ; À引擎器(正常运行、停止运行) 。先根据变量定义, 将8个变量分别用8个节点表示, 建立任意两个节点之间的连接, 构成完全潜在图(见图1) 。基于样本数据, 计算相关的概率参数, 构成联合概率表, 通过边缘概率和条件概率计算条件互信息I (X , Y |Z) 。在给定置信度的基础上, 可运用V 2检验来判断条件独立性[12]。若计算值I
(, Z V 2/n , Z 合考虑样本数据和专家知识, 具有因果分析、关联
分析和时序分析等功能, 可应用在故障诊断、分类聚类、可靠性评估等领域。但要求数据集包含的变量为离散变量, 若出现连续变量, 则需要对数据进行预处理, 即离散化; 样本数据必须是完备的数据集, 样本规模足够大, 且样本数据量越大, 得到的网络结构越好, 但样本规模将影响到计算效率。
4 结 语
本文算法从完全潜在图出发, 利用专家知识和先验常识, 设定相关参数, 有效地减少网络结构的搜索空间。通过CI 测试, 确定变量之间的依赖性, 将全连接无向图修剪成最优的潜在图, 近似于有向无环图的无向版。实例证明了该算法的可行,
318武汉大学学报#信息科学版
2004年
的情况, 该算法的有效性还有待于进一步验证。同时, 算法对样本规模的灵敏度以及对不完备性数据的学习也是今后研究的内容。
参 考 文 献
1 Bouckaer t R R. Belief Networks Construction U sing the
M inimum Descriptio n Leng th Principle. L ectur e Notes in Computer Science, 1993, 747:41~482
Lam W,
Bacchus F.
L earning Bayesian Belief
N etw orks:A n Approach Based on the M DL Principle. Computational Intelligence, 1994(10) :269~2933 Cooper G, Herskovits E. A Bayesian M ethod fo r the
Induction of Bayesian N etw orks from Data. M achine L earning, 1992(9) :309~3474
Sing h M , Efficient 5
Valtor ta M.
Construction of Bayesian
Journal
of
N etw ork Str uctures from Data:A Brief Survey and an
Algorithm.
International
Approx imate Reasoning , 1995(12) :111~131Chickering D M.
Learning Equiv alence Classes of
Journal of M achine
Bayesian Network Structur es.
Journal of Patter n Recognition and Artificial Intellig ence, 2000, 14(7) :941~962
Geig er D,
Chickering D.
Learning
7 Heckerman D,
Bayesian Netwo rks:T he Combination of K no wledge and Stat istical Data. M achine L earning, 1995, 20(2) :197~243
8 Herskov its E. Computer -based Pr obabilistic Netwo rks Co nstruct ion:[Ph. D Disser tatio n]. Califor nia:Stanford U niversity , 1991
9 Spirtes P , Glymour C, Scheines R. An Algo rithm for Fast Recovery of Sparse Causal Graphs. Social Science Co mputer Review, 1991(9) :62~72
10 Cheng J, Bell D A, L iu W. An A lgorithm for Bayesian
Belief N etwork Construction from Data. A I &ST AT . 97, Flor ida, 1997
11 Pearl J. Probabilistic Reasoning in Intelligent System:
Networks of Prausible Inference. M or gan K aufman, 1988
12 Lui s M , de Campos, Huete J. A New Approach for
L ear ning Belief N etw orks Using Independence Criteria. International Jour nal of A ppr oximate Reasoning, 2000, 24(1) :11~37
第一作者简介:黄解军, 博士生。研究方向为数据挖掘与数据仓库等。
E -mai l:hjjtk@21cn. com
San Fr ansisco:
L earning Research, 2002(2) :445~498
6 Pan H P, L iu L. F uzzy Bayesian N etw orks ) a Gener al
For mali sm for Representatio n,
Infer ence and Learn -I nternat ional
ing with Hybrid Bayesian Networ ks.
Bayesian Network S tructure Learning and Its Applications
H UANG Jiej un 1 WAN Youchuan 1 PAN H eping 1
(1 School of Remote S ensing an d Information Engineering, Wuhan University,
129Luoyu Road, Wuhan 430079, China)
Abstract:This paper discusses the purposes and methods of Bayesian netw ork structure learning ,
then proposes a new algorithm for this task. Based on a fully connected potential g raph, w e enter the ex pert know ledge and prior knowledge in order to reduce the query space of the structures. By using CI (conditional independence) tests, it can be pruned a fully connected potential graph to a best PG, w hich is expected to approximate the undirected version of the underly ing directed g raph. The experimental results of fault diagnosis in automobile are provided to illustrate the feasibility and efficiency of the new algorithm.
Key words:Bayesian netw ork; structure learning; conditional independence; probabilistic reasoning ; g raph theory
About the first author:HUA NG Jiejun , Ph . D candidate, m ajors in data mining and data warehou se. E -m ail:hjjtk @21cn. com
(责任编辑: 晓平)