机器学习：用于因果分析的混合贝叶斯网络结构学习

第2卷第6期 智能系统学报 Vol.2 N26 2007年12月 CAAI Transactions on Intelligent Systems Dec.2007 用于因果分析的混合贝叶斯网络结构学习 王双成李小琳2，侯彩虹 (1.上海立信会计学院信息科学系，上海201620：2.南京大学软件技术国家重点实验室，江苏南京210093) 摘要：目前主要结合扩展的熵离散化方法和打分搜索方法进行混合贝叶斯网络结构学习，算法效率和可靠性 低，而且易于陷入局部最优结构.针对问题建立了一种新的混合贝叶斯网络结构迭代学习方法.在迭代中，基于父结 点结构和Gibbs sampling进行混合数据聚类，实现对连续变量的离散化，再结合贝叶斯网络结构优化调整，使贝叶斯 网络结构序列逐渐趋于稳定，可避免使用扩展的熵离散化和打分搜索所带来的主要问题 关键词：因果分析：混合贝叶斯网络；最大似然树；Gbbs抽样 中图分类号：TP18文献标识码：A文章编号：16734785(2007)060082-08 Learning in a hybrid Bayesian net work structure for causal analysis WAN G Shuang-cheng,LI Xiao-lin2,HOU Cai-hong (1.Department of Information Science,Shanghai Lixin University of Commerce,Shanghai 201620,China;2.National Labo- ratory for Novel Software Technology,Nanjing University,Nanjing 210093,China) Abstract:At present,learning in a hybrid Bayesian network structure mainly depends on a combination of the searching scoring method and the expanded entropy discretization algorithm.However,the algo- rithm is prone to fall into local optimal traps and its efficiency and reliability are not good.In this paper,a new iterative method for learning with hybrid Bayesian network structures is presented.In each iteration, mixed data clustering is carried out based on father mode structures and Gibbs sampling,so that continu- ous variables are discretized.Then,through optimization of the Bayesian network structure,the sequence of Bayesian network structures gradually tends to converge,avoiding the main problems encountered with the expanded entropy discretization algorithm. Key words :causal analysis;hybrid Bayesian network;maximum likelihood tree;Gibbs sampling 人类对现实世界中现象的一种强烈渴望就是因义，并建立了贝叶斯网络的基础理论体系川进入 果联系，通过因果关系能够揭示事物之间的内在联 90年代以后，以Pearl、Heckerman、Peter Spirtes、 系，从而达到认识世界和改造世界的目的，因此，因 Chickering和Henson等2.1为代表相继进行了基 果关系是哲学、自然科学和社会科学等的重要研究 于贝叶斯网络的因果分析的理论探索和应用研究， 内容.贝叶斯网络四是描述随机变量之间依赖关系 但这些研究都是基于离散变量的假设.基于贝叶斯 的图形模式，具有形象直观的知识表示形式，以及更网络进行混合变量因果分析比较困难，其核心是混 接近人思维特征的推理方式，被广泛用于不确定性 合贝叶斯网络结构学习.以往对混合贝叶斯网络结 知识表示和推理.在一些假设下，贝叶斯网络中边的 构学习的研究主要从2个方面展开：一方面是不离 方向具有因果语义，因此是变量之间因果分析的有 散化连续变量，通过打分搜索方法直接进行混合 力工具.20世纪80年代后期，加利福尼亚大学计算 贝叶斯网络结构学习，Thiesson和Murphy等人曾 机科学系Judea Dearl给出了贝叶斯网络的严格定 经给出过一些近似打分函数6·】，但由于运算过于 复杂，不具有实用价值，至今还没有实质性的进展； 收稿日期：2007-01-04. 基金项目：国家自然科学基金资助项目(60675036)；上海市重点学科 另一方面是离散化连续变量，转化为离散变量贝叶 基金资助项目(P1601):上海市教委重点基金资助项目 斯网络结构学习问题，由于变量之间的因果结构具 (05zz66). 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net

第 2 卷第 6 期 智 能 系 统 学 报 Vol. 2 №. 6 2007 年 12 月 CAAI Transactions on Intelligent Systems Dec. 2007 用于因果分析的混合贝叶斯网络结构学习 王双成1 ,李小琳2 ,侯彩虹1 (1. 上海立信会计学院 信息科学系 ,上海 201620 ;2. 南京大学 软件技术国家重点实验室 ,江苏 南京 210093) 摘 要 :目前主要结合扩展的熵离散化方法和打分 —搜索方法进行混合贝叶斯网络结构学习 ,算法效率和可靠性 低 ,而且易于陷入局部最优结构. 针对问题建立了一种新的混合贝叶斯网络结构迭代学习方法. 在迭代中 ,基于父结 点结构和 Gibbs sampling 进行混合数据聚类 ,实现对连续变量的离散化 ,再结合贝叶斯网络结构优化调整 ,使贝叶斯 网络结构序列逐渐趋于稳定 ,可避免使用扩展的熵离散化和打分 —搜索所带来的主要问题. 关键词 :因果分析 ;混合贝叶斯网络 ;最大似然树 ; Gibbs 抽样 中图分类号 : TP18 文献标识码 :A 文章编号 :167324785 (2007) 0620082208 Learning in a hybrid Bayesian network structure for causal analysis WAN G Shuang2cheng 1 , L I Xiao2lin 2 , HOU Cai2hong 1 (1. Department of Information Science , Shanghai Lixin University of Commerce , Shanghai 201620 , China ; 2. National Labo2 ratory for Novel Software Technology , Nanjing University , Nanjing 210093 , China) Abstract :At p resent , learning in a hybrid Bayesian network struct ure mainly depends on a combination of t he searching & scoring met hod and t he expanded entropy discretization algorit hm. However , t he algo2 rit hm is prone to fall into local optimal trap s and its efficiency and reliability are not good. In t his paper , a new iterative met hod for learning wit h hybrid Bayesian network struct ures is p resented. In each iteration , mixed data clustering is carried out based on fat her mode structures and Gibbs sampling , so that continu2 ous variables are discretized. Then , t hrough optimization of the Bayesian network struct ure , t he sequence of Bayesian network struct ures gradually tends to converge , avoiding t he main problems encountered wit h t he expanded entropy discretization algorit hm. Keywords :causal analysis ; hybrid Bayesian network ; maximum likelihood tree ; Gibbs sampling 收稿日期 :2007201204. 基金项目 :国家自然科学基金资助项目(60675036) ;上海市重点学科 基金资助项目 ( P1601) ;上海市教委重点基金资助项目 (05zz66) . 人类对现实世界中现象的一种强烈渴望就是因 果联系 ,通过因果关系能够揭示事物之间的内在联 系 ,从而达到认识世界和改造世界的目的 ,因此 ,因 果关系是哲学、自然科学和社会科学等的重要研究 内容. 贝叶斯网络[1 ] 是描述随机变量之间依赖关系 的图形模式 ,具有形象直观的知识表示形式 ,以及更 接近人思维特征的推理方式 ,被广泛用于不确定性 知识表示和推理. 在一些假设下 ,贝叶斯网络中边的 方向具有因果语义 ,因此是变量之间因果分析的有 力工具. 20 世纪 80 年代后期 ,加利福尼亚大学计算 机科学系 J udea Dearl 给出了贝叶斯网络的严格定 义 ,并建立了贝叶斯网络的基础理论体系[1 ] . 进入 90 年代以后 ,以 Pearl、Heckerman 、Peter Spirtes 、 Chickering 和 Henson 等[2 - 6 ] 为代表相继进行了基 于贝叶斯网络的因果分析的理论探索和应用研究 , 但这些研究都是基于离散变量的假设. 基于贝叶斯 网络进行混合变量因果分析比较困难 ,其核心是混 合贝叶斯网络结构学习. 以往对混合贝叶斯网络结 构学习的研究主要从 2 个方面展开 :一方面是不离 散化连续变量 ,通过打分 —搜索方法直接进行混合 贝叶斯网络结构学习 , Thiesson 和 Murp hy 等人曾 经给出过一些近似打分函数[6 - 8 ] ,但由于运算过于 复杂 ,不具有实用价值 ,至今还没有实质性的进展 ; 另一方面是离散化连续变量 ,转化为离散变量贝叶 斯网络结构学习问题 ,由于变量之间的因果结构具

第6期 王双成，等：用于因果分析的混合贝叶斯网络结构学习 ·83· 有相对稳定性，在发现因果结构时允许忽略一些细 涵的变量之间的依赖关系可能比较混乱，这将导致 节信息，因此，基于离散化的方法是混合贝叶斯网络 直接进行贝叶斯网络学习不够可靠，影响随后的迭 结构学习更为有效、实用的方法 代收敛速度.最大似然树是与贝叶斯网络具有最好 目前，在混合贝叶斯网络结构学习中连续变量 拟合的属性结构，在树中蕴含的依赖关系往往是贝 的离散化主要采用扩展的熵离散化方法(Fayyad和 叶斯网络中的重要依赖关系，而且最大似然树的结 rani9提出的基于熵离散化方法的推广，早期用于 构相对稳定，学习效率高，因此，采用为最大似然树 分类器学习中连续变量的离散化).这种方法的实现 边因果定向的有向无环图作为初始贝叶斯网络.首 是一个迭代过程，在迭代过程中，以父结点为条件的 先依据Chow和Liu的方法建立最大似然树，经 条件熵作为打分函数，对分点进行贪婪(greedy)或 过简单的碰撞识别定向后得到Polytree)(这时大部 随机打分搜索，使用MDL)(minimal descrip 分边己经确定了方向，并且方向具有因果语义)，然后 tion length)标准（或条件熵）确定分点数，并在新数 基于链图和MDL标准为其他没有定向的边定向. 据集的基础上使用打分搜索方法重新进行结构学 从数据集D中建立最大似然树T,并对T中 习.由于分点空间的大小随数据量的增加指数增长， 的边进行碰撞识别定向得到Polytree方.h是一 无论采用哪种打分搜索方法，当数据量大时都很 个链图1s1(chain graph),设链图中没有确定方向的 难实现，而且得到的一般是局部最优划分.在打分一 边为ea,e,用G和C分别表示边e1,e.i 搜索结构学习中，由于打分函数的计算复杂性和结 己定向、而边e+1,…e还没定向、由边e方向所确 构搜索空间的大小也都随变量增加指数增长，因此 定的不同链图.按照Buntinelis)给出的基于链图分 一般要求结点有顺序，并根据打分函数的可分解性 解联合概率的方法，便能计算一个链图的MDL打 进行局部确定或随机搜索（完全搜索是NP困难问 分.根据MDL(G|D和MDL(GID的大小确定 题山)，这样重新结构学习效率低，易于陷入局部最 边。的方向，直到确定所有未定向边的方向.把最 优结构.此外，基于扩展的熵离散化方法强调的是属 后得到有向无环图记为G,并作为初始贝叶斯网 性变量对类变量的分类贡献，不具有因果语义，这样 络结构，由G所确定的结点顺序记为， 易于导致因果信息的丢失和冗余， X.将数据集pima_indians_diabete中的连续数据 本文结合父结点结构（因果结构）和Gibbs 进行二分离散化，从中学习得到的最大似然树和初 sampling!2.进行混合数据聚类，通过聚类实现连 始贝叶斯网络结构如图1所示 续变量的离散化，进行混合贝叶斯网络结构迭代学 习，每一次离散化后进行贝叶斯网络因果关系优化 调整，直到迭代收敛.按照父结点结构分解联合概 率，解决了标准Gibbs sampling的指数复杂性问 题21，因此能够显著提高离散化效率，Gibbs sam~ pling过程收敛到全局平稳分布2.B】,这样可避免 使用扩展的熵离散化方法的局部最优化分问题.贝 叶斯网络因果关系优化调整将使变量之间的依赖关 (a)最大似然树 系逐渐趋于因果关系，实验结果显示，这种方法能够 有效地进行混合贝叶斯网络结构学习 用X,…,Xm表示连续和离散混合随机变量， x1,xm表示变量的取值.D表示具有N个例子 的混合数据集，数据随机产生于联合分布P. 初始化混合贝叶斯网络学习 (b)定向后的有向无环图 初始混合贝叶斯网络学习包括连续变量的初始 离散化和贝叶斯网络的初始化2部分.采用二分法 图1初始pima indians_diabetes贝叶斯网络结构 对连续变量进行初始离散化（以均值作为离散化的 Fig.I Initial Bayesian network structure of 分界点，进行二值离散化)，把离散化后的数据集作 pima indians diabetes dataset 为初始数据集，用D表示.由于数据集D中所蕴 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net

有相对稳定性 ,在发现因果结构时允许忽略一些细 节信息 ,因此 ,基于离散化的方法是混合贝叶斯网络 结构学习更为有效、实用的方法. 目前 ,在混合贝叶斯网络结构学习中连续变量 的离散化主要采用扩展的熵离散化方法(Fayyad 和 Irani [ 9 ]提出的基于熵离散化方法的推广 ,早期用于 分类器学习中连续变量的离散化) . 这种方法的实现 是一个迭代过程 ,在迭代过程中 ,以父结点为条件的 条件熵作为打分函数 ,对分点进行贪婪 ( greedy) 或 随机打分 —搜索 ,使用 MDL [10 ] ( minimal descrip2 tion length) 标准(或条件熵) 确定分点数 ,并在新数 据集的基础上使用打分 —搜索方法重新进行结构学 习. 由于分点空间的大小随数据量的增加指数增长 , 无论采用哪种打分 —搜索方法 ,当数据量大时都很 难实现 ,而且得到的一般是局部最优划分. 在打分 — 搜索结构学习中 ,由于打分函数的计算复杂性和结 构搜索空间的大小也都随变量增加指数增长 ,因此 一般要求结点有顺序 ,并根据打分函数的可分解性 进行局部确定或随机搜索(完全搜索是 N2P 困难问 题[11 ] ) ,这样重新结构学习效率低 ,易于陷入局部最 优结构. 此外 ,基于扩展的熵离散化方法强调的是属 性变量对类变量的分类贡献 ,不具有因果语义 ,这样 易于导致因果信息的丢失和冗余. 本文结合父结点结构 (因果结构) 和 Gibbs sampling [12 - 13 ]进行混合数据聚类 ,通过聚类实现连 续变量的离散化 ,进行混合贝叶斯网络结构迭代学 习 ,每一次离散化后进行贝叶斯网络因果关系优化 调整 ,直到迭代收敛. 按照父结点结构分解联合概 率 ,解决了标准 Gibbs sampling 的指数复杂性问 题[12 ] ,因此能够显著提高离散化效率 , Gibbs sam2 pling 过程收敛到全局平稳分布[12 - 13 ] ,这样可避免 使用扩展的熵离散化方法的局部最优化分问题. 贝 叶斯网络因果关系优化调整将使变量之间的依赖关 系逐渐趋于因果关系 ,实验结果显示 ,这种方法能够 有效地进行混合贝叶斯网络结构学习. 用 X1 , …, Xn 表示连续和离散混合随机变量 , x1 , …, x n 表示变量的取值. D 表示具有 N 个例子 的混合数据集 ,数据随机产生于联合分布 P. 1 初始化混合贝叶斯网络学习 初始混合贝叶斯网络学习包括连续变量的初始 离散化和贝叶斯网络的初始化 2 部分. 采用二分法 对连续变量进行初始离散化 (以均值作为离散化的 分界点 ,进行二值离散化) ,把离散化后的数据集作 为初始数据集 ,用 D (0) 表示. 由于数据集 D (0) 中所蕴 涵的变量之间的依赖关系可能比较混乱 ,这将导致 直接进行贝叶斯网络学习不够可靠 ,影响随后的迭 代收敛速度. 最大似然树是与贝叶斯网络具有最好 拟合的属性结构 ,在树中蕴含的依赖关系往往是贝 叶斯网络中的重要依赖关系 ,而且最大似然树的结 构相对稳定 ,学习效率高 ,因此 ,采用为最大似然树 边因果定向的有向无环图作为初始贝叶斯网络. 首 先依据 Chow 和 Liu [14 ] 的方法建立最大似然树 ,经 过简单的碰撞识别定向后得到 Polytree [1 ] (这时大部 分边已经确定了方向 ,并且方向具有因果语义) ,然后 基于链图和 MDL 标准为其他没有定向的边定向. 从数据集 D (0) 中建立最大似然树 T ,并对 T 中 的边进行碰撞识别定向得到 Polytree T1 . T1 是一 个链图[ 15 ] (chain grap h) ,设链图中没有确定方向的 边为 e1 , …, es ,用 G i + C 和 C i - C 分别表示边 e1 , …, ei - 1 已定向、而边 ei + 1 , …, es 还没定向、由边 ei 方向所确 定的不同链图. 按照 Buntine [15 ] 给出的基于链图分 解联合概率的方法 ,便能计算一个链图的 MDL 打 分. 根据 MDL ( G i + C | D 和 MDL ( G i - C | D) 的大小确定 边 ei 的方向 ,直到确定所有未定向边的方向. 把最 后得到有向无环图记为 G (0) ,并作为初始贝叶斯网 络结构 , 由 G (0) 所确定的结点顺序记为 X (0) 1 , …, X (0) n . 将数据集 pima_indians_diabete 中的连续数据 进行二分离散化 ,从中学习得到的最大似然树和初 始贝叶斯网络结构如图 1 所示. 图 1 初始 pima_indians_diabetes 贝叶斯网络结构 Fig. 1 Initial Bayesian network structure of pima_indians_diabetes dataset 第 6 期 王双成 ,等 :用于因果分析的混合贝叶斯网络结构学习 ·83 ·

·84 智能系统学报 第2卷 变量的重新离散化得到D+”.在式1)中，对连续 2混合贝叶斯网络迭代学习 变量采用条件正态密度函数，也可采用其他密度函 混合贝叶斯网络迭代学习包括2个迭代过程， 数（核密度或多项式密度函数等）.在聚类迭代过程 一个是在确定结构下的连续变量离散化内层迭代， 中，结合G"和Gibbs sampling依次确定数据库中 另一个是结构外层迭代.迭代产生2个序列，它们是 每一个记录中的X的值，确定了数据库中所有记 离散数据集序列{D®}和贝叶斯网络结构序列 录中的X的值便实现一次迭代，直到满足终止条 1G}.每一次外层迭代又包括2个部分，一部分是 件结束迭代.下面给出在一个记录中确定X值的 基于上一次迭代得到的贝叶斯网络结构G重新离 方法： 散化连续变量得到新的离散数据集D;另一部分 p(x xG)= 是在D的基础上，优化调整贝叶斯网络结构得到 g(x;x):x)G)= G+”,直到满足结构迭代终止条件结束迭代 “四w) 2.1基于混合数据聚类的连续变量离散化 e2 (2) 对每一个连续变量的离散化是一个子迭代过 N2raπw,x) 程，按照贝叶斯网络结构G所确定的变量顺序依 式中：4（πw,x)和g(W,x")分别表示变量 次对连续变量进行重新离散化，下一个连续变量的 X,条件均值和条件标准差 离散化在上一个离散化结果的基础上进行，直到离 如果p(x|刀，G)=0,对p,(x|乃四 散化完所有的连续变量.为有效地继承因果信息，结 G)进行拉普拉斯修正(Laplace-corrected)ol: 合贝叶斯网络中的因果局部结构（父结点结构）和 p(x|乃w,G")= Gibbs sampling进行混合数据聚类，通过聚类实现 1/N)(N(w)+N(x)1/N)) 连续变量的离散化.在对一个连续变量的离散化过 式中：N(w)为X的父结点集W具有配置 程中，包括确定对应的离散变量取值（类值）和维数 πw的例子数量，N(x)为X=x的例子数量 (类数)2部分内容 对选择的维数1,2≤，≤M),首先随机初始 在依次对连续变量重新离散化的过程中，贝叶 化xW的值，然后通过抽样对D中变量x的 斯网络结构保持不变，但数据集在不断的变化，这样 值进行修正，直到收敛 产生一个离散数据集子序列D=D,D, 设需要离散化的变量X,离散化后对应的离散 D=D+”,其中D是在D,中用连续变量X 变量最大可能的维数为M(一般取5或6)，按照 的最新离散化数据代替原有离散化数据而得到的数 数据库中记录的顺序依次对x”的值进行修正. 据集， 设X在第m个记录的待修正值为x,黑 2.1.1确定连续变量对应的离散变量取值 表示修正后的值，变量X的可能取值为x, 设由G所确定的变量顺序为，X x是.对抽样式子进行归一化处理，记w(h)= 为方便把离散化后的变量排在前部，在每一部分内 部保持原来的顺序，得到新的变量序列为X, p()p(. X,X+1,Xm.用X,替换X,通过混合数据聚 ,2Px元，，G")p(,G") 类得到X,离散化后的离散变量类变量)，仍用X 对生成的随机数入，离散变量和的取值为 表示。 Xi. 0<入≤w(j), 由贝叶斯和乘法公式可得 p(xxxxG)= ap(xx)= Bp(xxG)p(x).(1) 式中亚w是GW中X父结点集的配置，a和B是 与xW无关的量 基于G和Gibbs sampling进行混合数据聚 (3) 类，从而实现对变量X,的重新离散化，用新的离散 2.1.2确定最优的离散化方案 化变量的值代替D中X的值，并在D的基 根据最优维数确定的离散化方案便是最优的离 础上重新离散化X+得到D,直到完成所有连续 散化方案，因此确定最优的离散化方案的核心是确 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net

2 混合贝叶斯网络迭代学习 混合贝叶斯网络迭代学习包括 2 个迭代过程 , 一个是在确定结构下的连续变量离散化内层迭代 , 另一个是结构外层迭代. 迭代产生 2 个序列 ,它们是 离散数据集序列 { D ( k) } 和贝叶斯网络结构序列 { G ( k) } . 每一次外层迭代又包括 2 个部分 ,一部分是 基于上一次迭代得到的贝叶斯网络结构 G ( k) 重新离 散化连续变量得到新的离散数据集 D ( k) ;另一部分 是在 D ( k) 的基础上 ,优化调整贝叶斯网络结构得到 G ( k + 1) ,直到满足结构迭代终止条件结束迭代. 2. 1 基于混合数据聚类的连续变量离散化 对每一个连续变量的离散化是一个子迭代过 程 ,按照贝叶斯网络结构 G ( k) 所确定的变量顺序依 次对连续变量进行重新离散化 ,下一个连续变量的 离散化在上一个离散化结果的基础上进行 ,直到离 散化完所有的连续变量. 为有效地继承因果信息 ,结 合贝叶斯网络中的因果局部结构 (父结点结构) 和 Gibbs sampling 进行混合数据聚类 ,通过聚类实现 连续变量的离散化. 在对一个连续变量的离散化过 程中 ,包括确定对应的离散变量取值 (类值) 和维数 (类数) 2 部分内容. 在依次对连续变量重新离散化的过程中 ,贝叶 斯网络结构保持不变 ,但数据集在不断的变化 ,这样 产生一个离散数据集子序列 D ( k) 0 = D ( k) , D ( k) 1 , …, D ( k) t = D ( k + 1) ,其中 D ( k) j 是在 D ( k) j - 1 中用连续变量 Xj 的最新离散化数据代替原有离散化数据而得到的数 据集. 2. 1. 1 确定连续变量对应的离散变量取值 设由 G ( k) 所确定的变量顺序为 X ( k) 1 , …, X ( k) n , 为方便把离散化后的变量排在前部 ,在每一部分内 部保持原来的顺序 ,得到新的变量序列为 X ( k) 1 , …, X ( k) t , Xt + 1 , …, Xn . 用 Xi 替换 X ( k) i ,通过混合数据聚 类得到 Xi 离散化后的离散变量(类变量) ,仍用 X ( k) i 表示. 由贝叶斯和乘法公式可得 p ( x ( k) i | x ( k) 1 , …, x ( k) i- 1 , xi , G ( k) ) = αp ( x ( k) i ,πx ( k) i , xi , G ( k) ) = βp ( xi | πx ( k) i , x ( k) i , G ( k) ) p ( x ( k) i | πx ( k) i , G ( k) ) . (1) 式中 :πx ( k) i 是 G ( k) 中 X ( k) i 父结点集的配置 ,α和β是 与 x ( k) i 无关的量. 基于 G ( k) 和 Gibbs sampling 进行混合数据聚 类 ,从而实现对变量 Xi 的重新离散化 ,用新的离散 化变量的值代替 D ( k) i 中 X ( k) i 的值 ,并在 D ( k) i 的基 础上重新离散化 X i + 1得到 D ( k) i + 1 ,直到完成所有连续 变量的重新离散化得到 D ( k + 1) . 在式 (1) 中 ,对连续 变量采用条件正态密度函数 ,也可采用其他密度函 数(核密度或多项式密度函数等) . 在聚类迭代过程 中 ,结合 G ( k) 和 Gibbs sampling 依次确定数据库中 每一个记录中的 X ( k) i 的值 ,确定了数据库中所有记 录中的 X ( k) i 的值便实现一次迭代 ,直到满足终止条 件结束迭代. 下面给出在一个记录中确定 X ( k) i 值的 方法 : p ( xi | πx ( k) i , x ( k) i , G ( k) ) = g ( xi ;μi (πx ( k) i , x ( k) i ) ;σi (πx ( k) i , x ( k) i ) | G ( k) ) = 1 2πσi (πx ( k) i , x ( k) i ) e - x i -μi (πx ( k) i , x ( k) i ) 2σ2 i (πx ( k) i , x ( k) i ) . (2) 式中 :μi (πx ( k) i , x ( k) i ) 和σi (πx ( k) i , x ( k) i ) 分别表示变量 Xi 条件均值和条件标准差. 如果 p ( x ( k) i | πx ( k) i , G ( k) ) = 0 , 对 pi ( x ( k) | πx ( k) i , G ( k) ) 进行拉普拉斯修正(Laplace2corrected) [ 16 ] : p ( x ( k) i | πx ( k) i , G ( k) ) = (1/ N) ( N (πx ( k) i ) + N ( x ( k) i ) (1/ N) ) . 式中 : N (πx ( k) i ) 为 X ( k) i 的父结点集 ∏X ( k) i 具有配置 πx ( k) i 的例子数量 , N ( x ( k) i ) 为 X ( k) i = x ( k) i 的例子数量. 对选择的维数 li (2 ≤li ≤M ( k) i ) ,首先随机初始 化 X ( k) i 的值 ,然后通过抽样对 D ( k) i 中变量 X ( k) i 的 值进行修正 ,直到收敛. 设需要离散化的变量 Xi 离散化后对应的离散 变量最大可能的维数为 M ( k) i (一般取 5 或 6) ,按照 数据库中记录的顺序依次对 X ( k) i 的值进行修正. 设 X ( k) i 在第 m 个记录的待修正值为 x ( k) im , ^x ( k) im 表示修正后的值 ,变量 X ( k) i 的可能取值为 x 1 i , …, x l i i . 对抽样式子进行归一化处理 , 记 w ( k) i ( h) = p ( xi |πx i , x h i , G ( k) ) p ( x h i |πx i , G ( k) ) ∑ l i j = 1 p ( xi |πx i , x j i , G ( k) ) p ( x j i |πx i , G ( k) ) , h ∈{ 1 , …, li} , 对生成的随机数λ,离散变量 X ( k) i 的取值为 ^x ( k) im = x 1 i , 0 <λ ≤w ( k) i ( j) , … x h i , ∑ h- 1 j = 1 w ( k) i ( j) <λ ≤ ∑ h j = 1 w ( k) i ( j) , … x l i i , λ > ∑ l i - 1 j = 1 w ( k) i ( j) . (3) 2. 1. 2 确定最优的离散化方案 根据最优维数确定的离散化方案便是最优的离 散化方案 ,因此确定最优的离散化方案的核心是确 ·84 · 智 能 系 统 学 报 第 2 卷

第6期 王双成，等：用于因果分析的混合贝叶斯网络结构学习 ·85· 定连续变量对应的离散变量的最优维数.设D, ,X(力，j,k=1,…h为条件的条件互信息 ,D得四是使用不同的离散化方案A(2≤h≤ 对给定的小正数一般取=0.01)，如果1(X,X M),选择一个h的值便得到一个离散化方案)离 X,:X<￡，就认为X和X之间条件独立 散化变量X,而得到的离散数据集序列，对每一个 1)补充丢失的依赖关系 离散化方案分别进行MDL标准打分，取加= 对不存在边的结点对X:和X,依次进行互信 inMDL (A D)}作为离散变量的维数 息1(X:,X)计算.如果1(X:,X)>￡，在G中增加 边X,·X.用L表示对应的边表，其中的元素是 MDL(AI D)=号21A1-LMD). 三元组(i,j,列，j>i,i=1,n,j=2,n,6= (4) 0,1,I=1和乃=0分别表示存在和不存在边x 式中Al表示离散化方案A中变量x在G X.这一过程最多需要(n+)(n+2)/2次互信息计算 中马尔可夫毯结构的参数数量： 2)删除冗余的依赖关系 由于连续变量重新离散化，可能存在一些冗余 L(A.D)1g(P(uI Mx DA))= 的边，通过下面的方法去除冗余的边.在G中，用 N∑p(xW,rw|Mxw,D,A Sx(X,X)和Sx,(X,X)分别表示X:和X的邻 域中在X,和X,链路81上的结点集，S(X,X)表 Πp(x,r,lMxw,D,A 示Sx,(X,X)和Sx(X,X)中具有较少结点的结 点集.对存在边的结点对X,X,设S(X,X)= Ig(p(x!,Mx,D A) {X,X”},如果存在和1≤和≤到使1(X, ΠP(xl元，MxW,D,A XX”,D<c,在G中删除边X,-X,和修改边 表L“:否则.选取·1(.川 2.2贝叶斯网络结构优化调整 X,Dw,如果存在加(1≤m≤1，加≠1)，使 贝叶斯网络结构优化调整包括结点顺序和结构 1X,XX,X”,DW)<￡，在G中删除边 调整2部分内容，通过优化将得到更好的贝叶斯网 X·X和修改边表L6:重新确定S(X,X),由于 络结构，直到迭代中的贝叶斯网络结构趋于稳定， 产生第2种依赖的信息流往往能被少数结点所阻塞 2.2.1依赖关系优化 (多数情况是1个或2个结点)，因此大部分的第2 利用贝叶斯网络的信息管道模型7181描述变 种边己被清除，S(X,X)将具有很少的冗余结点， 量之间存在的3种基本依赖关系（边）：1)传递依赖 如果1X,XS(X,X),DW)<￡，在G中删除 (transitive dependencies),结点之间存在直接的信 边X:-X和修改边表L.这一过程最多需要2 息流动，而且信息流不能被其他结点所阻塞，结点所 次条件互信息计算 表示的变量之间边缘和条件依赖：2)非传递依赖 2.2.2因果语义优化 (nontransitive dependencies),结点之间不存在直 因果语义优化就是边的方向优化，下面分别基 接的信息流动，而是由连接两结点之间的开路（不含 于碰撞识别和条件预测能力优化边的方向，以便得 碰撞结点的路径)产生信息流，这种信息流被切割集 到更适合于因果分析的贝叶斯网络 中的结点所阻塞，2个结点所表示的变量之间边缘 基于碰撞识别优化边的方向： 依赖，但条件独立；3)导出依赖(induced dependen- 在边表L&中查寻，选择结点对X,和X,设 cies),这种依赖是由V结构所导致，结点之间不存 X,和X,之间不存在边，在G中与X,和X,可能 在直接的信息流动，而是由V结构中的碰撞结点诱 形成V结构的结点为Xm,Xm,对每一个可能 发的信息流，结点所表示的变量之间边缘独立，但条 的V结构进行碰撞识别（汇聚识别）6-2，.对给定 件依赖 1(X.Xl Xm.D) 下面基于变量之间基本依赖关系和依赖分析思 的阈值6>0，如果 1(X:.X D) >1+」 想进行依赖关系优化（包括补充丢失的依赖关系和 1≤，则X,X和Xm形成V结构，定向为X,→ 删除冗余的依赖关系)和因果语义优化2部分内容 Xm.和X,→Xm,这一过程最多需要n(n-1)次条件 使用互信息和条件互信息进行变量之间定量条 互信息计算 件独立性检验，分别用1(X,X)和1(X,X引X, 使用碰撞识别调整方向后，可能还有一部分边 X)表示变量X,和X,之间的互信息和以X4, 的方向没有得到调整，下面基于变量之间的预测能 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net

定连续变量对应的离散变量的最优维数. 设 D ( k) i2 , …, D ( k) iM ( k) i 是使用不同的离散化方案 Λh ( 2 ≤h ≤ M ( k) i ) ,选择一个 h 的值便得到一个离散化方案) 离 散化变量 Xi 而得到的离散数据集序列 ,对每一个 离散化方案分别进行 MDL 标准打分 , 取 h0 = min M ( k) i ≥h ≥2 { MDL (Λh | D ( k) ih ) }作为离散变量的维数. MDL (Λh | D ( k) ih ) = lg N 2 | Λh | - L (Λh | D ( k) ih ) . (4) 式中 :| Λh | 表示离散化方案 Λh 中变量 X ( k) i 在 G ( k) 中马尔可夫毯[1 ]结构的参数数量 : L (Λh | D ( k) ih ) = ∑ N i =1 lg ( P( ui | M X ( k) i , D ( k) ih ,Λh ) ) = N x ( k)∑i ,πx ( k) i p ( x ( k) i ,πx ( k) i | M X ( k) i , D ( k) ih ,Λh ) x ( k)∏i ∈πx j p ( x j ,πx j | M X ( k) i , D ( k) ih ,Λh ) · lg ( p ( x ( k) i | πx ( k) i , M X ( k) i , D ( k) ih ,Λh ) x ( k)∏i ∈πx j p ( x j | πx j , M X ( k) i , D ( k) ih ,Λh ) . 2. 2 贝叶斯网络结构优化调整 贝叶斯网络结构优化调整包括结点顺序和结构 调整 2 部分内容 ,通过优化将得到更好的贝叶斯网 络结构 ,直到迭代中的贝叶斯网络结构趋于稳定. 2. 2. 1 依赖关系优化 利用贝叶斯网络的信息管道模型[17 - 18 ] 描述变 量之间存在的 3 种基本依赖关系 (边) :1) 传递依赖 (transitive dependencies) ,结点之间存在直接的信 息流动 ,而且信息流不能被其他结点所阻塞 ,结点所 表示的变量之间边缘和条件依赖 ; 2) 非传递依赖 (non2transitive dependencies) ,结点之间不存在直 接的信息流动 ,而是由连接两结点之间的开路(不含 碰撞结点的路径) 产生信息流 ,这种信息流被切割集 中的结点所阻塞 ,2 个结点所表示的变量之间边缘 依赖 ,但条件独立 ;3) 导出依赖 (induced dependen2 cies) ,这种依赖是由 V 结构所导致 ,结点之间不存 在直接的信息流动 ,而是由 V 结构中的碰撞结点诱 发的信息流 ,结点所表示的变量之间边缘独立 ,但条 件依赖. 下面基于变量之间基本依赖关系和依赖分析思 想进行依赖关系优化 (包括补充丢失的依赖关系和 删除冗余的依赖关系) 和因果语义优化 2 部分内容. 使用互信息和条件互信息进行变量之间定量条 件独立性检验 ,分别用 I ( Xi , Xj) 和 I ( Xi , Xj | Xu 1 , …, Xu h ) 表示变量 Xi 和 X j 之间的互信息和以 X u 1 , …, Xu h ( uk ≠i , j , k = 1 , …, h) 为条件的条件互信息 , 对给定的小正数ε(一般取ε= 0. 01) ,如果 I( Xi , Xj | Xu 1 , …, Xu h ) <ε,就认为 Xi 和 Xj 之间条件独立. 1) 补充丢失的依赖关系 对不存在边的结点对 Xi 和 X j ,依次进行互信 息 I( Xi , Xj) 计算. 如果 I ( Xi , Xj) >ε,在 G ( k) 中增加 边 Xi - Xj . 用 L ( k) 0 表示对应的边表 ,其中的元素是 三元组( i , j ,η) , j > i , i = 1 , …, n , j = 2 , …, n ,δ= 0 ,1 ,η= 1 和η0 = 0 分别表示存在和不存在边 Xi - Xj .这一过程最多需要( n + 1) ( n + 2) / 2 次互信息计算. 2) 删除冗余的依赖关系 由于连续变量重新离散化 ,可能存在一些冗余 的边 ,通过下面的方法去除冗余的边. 在 G ( k) 中 ,用 S Xi ( Xi , Xj) 和 S X j ( Xi , Xj) 分别表示 Xi 和 X j 的邻 域中在 X i 和 X j 链路[18 ] 上的结点集 , S ( Xi , Xj ) 表 示 S Xi ( Xi , Xj) 和 S X j ( Xi , Xj) 中具有较少结点的结 点集. 对存在边的结点对 Xi , Xj , 设 S ( Xi , Xj ) = { X ( i , j) 1 , …, X ( i , j) t } ,如果存在 t0 (1 ≤t0 ≤t) 使 I ( Xi , Xj | X ( i , j) t 0 , D) <ε,在 G ( k) 中删除边 Xi - Xj和修改边 表 L ( k) 0 ; 否则 , 选取 X i t 3 = argmin X (i , j) k , t ≥k ≥1 { I ( Xi , Xj ) | X ( i , j) k , D ( k) } , 如果存在 h0 ( 1 ≤h0 ≤t , h0 ≠t 3 ) , 使 I( Xi , Xj | X ( i , j) h 0 , X ( i , j) t 3 , D ( k) ) <ε, 在 G ( k) 中删除边 Xi - Xj和修改边表 L ( k) 0 ;重新确定 S ( Xi , Xj) ,由于 产生第 2 种依赖的信息流往往能被少数结点所阻塞 (多数情况是 1 个或 2 个结点) ,因此大部分的第 2 种边已被清除 , S ( Xi , Xj ) 将具有很少的冗余结点 , 如果 I ( Xi , Xj | S ( Xi , Xj ) , D ( k) ) <ε,在 G ( k) 中删除 边 Xi - Xj 和修改边表 L ( k) 0 . 这一过程最多需要 2 n 2 次条件互信息计算. 2. 2. 2 因果语义优化 因果语义优化就是边的方向优化 ,下面分别基 于碰撞识别和条件预测能力优化边的方向 ,以便得 到更适合于因果分析的贝叶斯网络. 基于碰撞识别优化边的方向 : 在边表 L ( k) 0 中查寻 ,选择结点对 Xi 和 X j , 设 Xi 和 X j 之间不存在边 ,在 G ( k) 中与 Xi 和 X j 可能 形成 V 结构的结点为 X m1 , …, X mt ,对每一个可能 的 V 结构进行碰撞识别 (汇聚识别) [16 - 20 ] . 对给定 的阈值δ> 0 , 如果 I( Xi , Xj | X mh , D ( k) ) I ( Xi , Xj | D ( k) ) > ( 1 +δ) , 1 ≤h ≤t ,则 Xi , Xj 和 X mh形成 V 结构 ,定向为 Xi → X mh和 X j →X mh ,这一过程最多需要 n( n - 1) 次条件 互信息计算. 使用碰撞识别调整方向后 ,可能还有一部分边 的方向没有得到调整 ,下面基于变量之间的预测能 第 6 期 王双成 ,等 :用于因果分析的混合贝叶斯网络结构学习 ·85 ·

·86· 智能系统学报 第2卷 力为其余的边调整定向.这种方法的基本思想是：对 关于混合贝叶斯网络的参数学习，如果使用离 任意的2个变量X,和X,在排除其他变量影响的 散化后的离散数据，可直接由数据统计得到：如果使 情况下，如果X,对X,比X,对X,更具条件预测能 用混合数据，由于父结点结构是分类或回归结构，对 力，方向应该由X:指向X 离散变量结点可采用分类技术，对连续变量结点可 记F(Xm,Xm,→X)为变量Xm,…Xm,对 采用神经网络或Logistic回归确定参数，限于篇幅 X,的预测能力 不予详述 F(Xm1,Xm,→X)= 2.3迭代终止检验 p(mp 迭代终止检验包括离散化（聚类）迭代终止检验 和结构迭代终止检验，离散化迭代是具有确定贝叶 记R(Xm,,Xm,X→X)为以Xm,Xm,为条 斯网络结构的内层迭代，结构迭代是外层迭代，结构 件，X对X,的相对预测能力 迭代终止学习过程便结束」 R(Xm1,Xm,X→X= 2.3.1离散化迭代终止检验 FXm,,Xm,X→X 1 采用相邻2次迭代被离散化变量值序列的一致 F(Xm1,Xm,→X) 性检验进行终止迭代判断.设相邻2次迭代所得到 式中：j为，jmh,h=1,1 的离散化值序列分别为x,x,x很和x+” 对选择的X:和X,分别用B(X)和B(X)表 x",x*",那么sig(x,x")= 示X,和X的马尔可夫毯，当B(X)和B(X)给定 0,x=x号+v 时，X,和X,之间便没有其他因素的影响，按如下方 1”v1可≤N.对给定的阀值n>0,如 法调整其他边的方向. 如果R(B(X)UB(X),X→X)>R(B(X)U 果大，9g,)<则结束选代 B(X),X→X),而且X,→X不产生环路，就定向 2.3.2结构迭代终止检验 为X→X,否则定向为X,一X. 按照变量的某一确定顺序（如在数据库中的顺 如果R(B(X)UB(X),X:→X)<R(B(X)U 序)建立贝叶斯网络结构数组，G所对应的结构数 B(X),X→X),而且X,一X不产生环路，就定向 组为w=（a程，a州，aw,a,… 为X,一X,否则定向为X,→X a品y).当X和X)之间存在边时，a=1(i<), 如果R(B(X)UB(X),X,→X)=R(B(X)U 否则a叫=0.对给定的正整数阈值，如果习a+”- B(X),X→X),选择不产生环路的情况定向，2种 a1<m,结束迭代 情况都不产生环路就随机定向.基于预测能力的定 向最多需要进行】(m-)次条件相对预测能力计 3实验 算，对GW调整后得到G+v 根据网站http:/www.norsys.com提供的A- 综上所述，进行一次贝叶斯网络结构优化调整 LARM网概率分布表生成离散变量模拟数据集，使 算法的时间复杂性是O().图2给出了经过迭代 用文献[19]中的离散变量连续化的方法，把离散变 学习得到的混合贝叶斯网络结构 量X3,X4,X36连续化.分别取6=0.05和而=4 进行实验 在第1次贝叶斯网络迭代中，对具有多父结点 的连续变量X3、X5、X7,分别取4、4、2个值的离 散化迭代收敛情况如图3(a)所示.贝叶斯网络结构 迭代收敛情况如图3(b)所示。 从图3(a)中可以看出，对X、X5、X迭代5 次后均收敛，显示了具有很高的离散化效率，而其他 的离散化算法在离散化过程中都具有很大的系统开 销.对其他连续变量（包括不同迭代次数）离散化迭 图2迭代学习后的混合贝叶斯网络结构 代可得到类似的收敛情况.图3(b)中显示，对结构 Fig.2 Hybrid Bayesian network structure 迭代6次后便收敛，表明学习算法具有很高的效率」 after iterative learning 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net

力为其余的边调整定向. 这种方法的基本思想是 :对 任意的 2 个变量 Xi 和 X j ,在排除其他变量影响的 情况下 ,如果 Xi 对 X j 比 X j 对 X i 更具条件预测能 力 ,方向应该由 Xi 指向 X j . 记 F( X m1 , …, X mt →Xi) 为变量 X m1 , …, X mt 对 X i 的预测能力 F( X m1 , …, X mt → Xi) = xm ∑1 , …, xmt p ( xm1 , …, xmt ) max X i ( xm1 , …, xmt ) { p( xi | xm1 , …, xmt )} , 记 R ( X m1 , …, X mt , Xj →Xi) 为以 X m1 , …, X mt 为条 件 , Xj 对 X i 的相对预测能力 R ( X m1 , …, X mt , Xj → Xi) = F( X m1 , …, X mt , Xj → Xi) F( X m1 , …, X mt → Xi) - 1 , 式中 : j ≠i , j ≠mh , h = 1 , …, t. 对选择的 Xi 和 X j ,分别用 B ( Xi) 和 B ( Xj ) 表 示 Xi 和 X j 的马尔可夫毯 ,当 B ( Xi) 和 B ( Xj) 给定 时 , Xi 和 X j 之间便没有其他因素的影响 ,按如下方 法调整其他边的方向. 如果 R(B ( Xi) ∪B ( Xj) , Xi →Xj) > R(B ( Xi) ∪ B ( Xj) , Xj →Xi) ,而且 Xi →Xj 不产生环路 ,就定向 为 Xi →Xj ,否则定向为 Xi ←Xj . 如果 R(B ( Xi) ∪B ( Xj) , Xi →Xj) < R(B ( Xi) ∪ B ( Xj) , Xj →Xi) ,而且 Xi ←Xj 不产生环路 ,就定向 为 Xi ←Xj ,否则定向为 Xi →Xj . 如果 R(B ( Xi) ∪B ( Xj) , Xi →Xj) = R(B ( Xi) ∪ B ( Xj) , Xj →Xi) ,选择不产生环路的情况定向 , 2 种 情况都不产生环路就随机定向. 基于预测能力的定 向最多需要进行 1 2 n( n - 1) 次条件相对预测能力计 算 ,对 G ( k) 调整后得到 G ( k + 1) . 图 2 迭代学习后的混合贝叶斯网络结构 Fig. 2 Hybrid Bayesian network structure after iterative learning 综上所述 ,进行一次贝叶斯网络结构优化调整 算法的时间复杂性是 O ( n 2 ) . 图 2 给出了经过迭代 学习得到的混合贝叶斯网络结构. 关于混合贝叶斯网络的参数学习 ,如果使用离 散化后的离散数据 ,可直接由数据统计得到 ;如果使 用混合数据 ,由于父结点结构是分类或回归结构 ,对 离散变量结点可采用分类技术 ,对连续变量结点可 采用神经网络或 Logistic 回归确定参数 ,限于篇幅 不予详述. 2. 3 迭代终止检验 迭代终止检验包括离散化(聚类) 迭代终止检验 和结构迭代终止检验 ,离散化迭代是具有确定贝叶 斯网络结构的内层迭代 ,结构迭代是外层迭代 ,结构 迭代终止学习过程便结束. 2. 3. 1 离散化迭代终止检验 采用相邻 2 次迭代被离散化变量值序列的一致 性检验进行终止迭代判断. 设相邻 2 次迭代所得到 的离散化值序列分别为 x ( k) i1 , x ( k) i2 , …, x ( k) iN 和 x ( k + 1) i1 , x ( k + 1) i2 , …, x ( k + 1) iN , 那 么 sig ( x ( k) ij , x ( k + 1) ij ) = 0 , x ( k) ij = x ( k + 1) ij 1 , x ( k) ij ≠x ( k + 1) ij ,1 ≤j ≤N . 对给定的阈值η0 > 0 ,如 果 1 N ∑ N j = 1 sig ( x ( k) ij , x ( k + 1) ij ) <η0 ,则结束迭代. 2. 3. 2 结构迭代终止检验 按照变量的某一确定顺序 (如在数据库中的顺 序) 建立贝叶斯网络结构数组 , G ( k) 所对应的结构数 组为 w ( k) = ( a ( k) 12 , …, a ( k) 1 n , …, a ( k) i( i + 1) , …, a ( k) in , …, a ( k) ( n - 1) n ) . 当 Xi 和 X j 之间存在边时 , a ( k) ij = 1 ( i < j) , 否则 aij = 0. 对给定的正整数阈值 n0 ,如果 ∑i < j | a ( k + 1) ij - a ( k) ij | < n0 ,结束迭代. 3 实 验 根据网站 http :/ / www. norsys. com 提供的 A2 LARM 网概率分布表生成离散变量模拟数据集 ,使 用文献[ 19 ]中的离散变量连续化的方法 ,把离散变 量 X2 , X4 , …, X36连续化. 分别取η0 = 0. 05 和 n0 = 4 进行实验. 在第 1 次贝叶斯网络迭代中 ,对具有多父结点 的连续变量 X13 、X35 、X27 ,分别取 4、4、2 个值的离 散化迭代收敛情况如图 3 (a) 所示. 贝叶斯网络结构 迭代收敛情况如图 3 (b) 所示. 从图 3 (a) 中可以看出 ,对 X13 、X35 、X27 迭代 5 次后均收敛 ,显示了具有很高的离散化效率 ,而其他 的离散化算法在离散化过程中都具有很大的系统开 销. 对其他连续变量 (包括不同迭代次数) 离散化迭 代可得到类似的收敛情况. 图 3 ( b) 中显示 ,对结构 迭代 6 次后便收敛 ,表明学习算法具有很高的效率. ·86 · 智 能 系 统 学 报 第 2 卷