第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 ∑ 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￡，在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”,D0，如果 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 ) ε,在 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) 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) 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 卷
第6期 王双成，等：用于因果分析的混合贝叶斯网络结构学习 ·87 701 一X:离散化 保持率方面，基于核密度的离散化算法略占优势，在 ·”··X离散化 一X2离散化 条件独立性保持率方面，基于正态密度的离散化方 2020 法略占优势.由于核密度估计随例子增加运算复杂 10 程度的增长远大于正态密度，因此当例子多时适合 45678910 于采用正态密度离散化方法，而当例子少时适合于 迭代次数 采用核密度离散化方法 (a)离散化迭代收敛情况 使用扩展的熵离散化算法和本文建立的聚类离 散化算法进行连续变量的离散化，其有效性的比较 如图5所示 20 扩展的嫡离散化算法 ··基于聚类的离散化算法 510 1.0 0.9 0.8 0 345678976 07 0.6 迭代次数 500 1000-1500 20003000 (b)结构迭代收敛情况 练数据数量 图3迭代收敛情况 (a)变量之间的依赖保持率比较 Fig.3 The iteration convergence situation 基于核密度离散化算法和基于正态密度的离散 1.00 一扩展的嫡离散化算法 ·。·,基于聚类的离散化算法 0.86 化算法的比较情况如图4所示 0.72 基于核密度的离散化 0.58 1.0 基于正态密度的离散化· 0.44 0.9 0.30 0.8 00 1000150020003000 0.7 训练数据数量 0.6 500 1000150020003000 (b)变量之间的条件独立性保持率比较 训练数据数量 图5基于聚类的离散化算法与扩展的熵离散化算法比较 (a)变量之间的依懒保持率 Fig.5 The situation comparison of discretizing continuous variables between clustering and extended entropy 1.00 基于核密度的离散化 0.86 ·基于正态密度的离化.： 图5中显示，当例子数据量小时，扩展的熵离散 0.72 0.58 化算法略优于聚类算法，但随例子数据的增加，聚类 0.44 算法明显具有优势.具有这种优势的主要原因是：随 030… 5001000150020003000 着例子数据的增加变量之间依赖和条件独立性信息 训练数据数量 能够得到充分的利用，且贝叶斯网络结构得到不断 的优化调整，而在扩展的熵离散化算法中，随着例子 (b)变量之间的条件独立性保持率 数据的增加，离散化和结构学习的局部最优性影响 图4基于正态密度和核密度的离散化情况比较 逐渐增加，导致了最终的差距 Fig.4 The situation comparison of discretizing continuous 在UCI机器学习数据仓库2o1中选择10个分类 variables between normal density and kernel density 数据集，脚标最大的一个是类变量，其他的是属性变 从图4的实验结果可以看出，在依赖关系保持 量.从其中3个数据集heart_disease、breast_,cancer 方面，当例子少时，基于核密度的离散化算法明显优 和cmc学习得到的贝叶斯网络结构如图6所示.基 于基于正态密度的离散化算法，当例子多时，在依赖 于扩展的熵离散化和聚类离散化2种方法，对类变 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.ne
图 3 迭代收敛情况 Fig. 3 The iteration convergence situation 基于核密度离散化算法和基于正态密度的离散 化算法的比较情况如图 4 所示. 图 4 基于正态密度和核密度的离散化情况比较 Fig. 4 The situation comparison of discretizing continuous variables between normal density and kernel density 从图 4 的实验结果可以看出 ,在依赖关系保持 方面 ,当例子少时 ,基于核密度的离散化算法明显优 于基于正态密度的离散化算法 ,当例子多时 ,在依赖 保持率方面 ,基于核密度的离散化算法略占优势 ,在 条件独立性保持率方面 ,基于正态密度的离散化方 法略占优势. 由于核密度估计随例子增加运算复杂 程度的增长远大于正态密度 ,因此当例子多时适合 于采用正态密度离散化方法 ,而当例子少时适合于 采用核密度离散化方法. 使用扩展的熵离散化算法和本文建立的聚类离 散化算法进行连续变量的离散化 ,其有效性的比较 如图 5 所示. 图 5 基于聚类的离散化算法与扩展的熵离散化算法比较 Fig. 5 The situation comparison of discretizing continuous variables between clustering and extended entropy 图 5 中显示 ,当例子数据量小时 ,扩展的熵离散 化算法略优于聚类算法 ,但随例子数据的增加 ,聚类 算法明显具有优势. 具有这种优势的主要原因是 :随 着例子数据的增加变量之间依赖和条件独立性信息 能够得到充分的利用 ,且贝叶斯网络结构得到不断 的优化调整 ,而在扩展的熵离散化算法中 ,随着例子 数据的增加 ,离散化和结构学习的局部最优性影响 逐渐增加 ,导致了最终的差距. 在 UCI 机器学习数据仓库[ 20 ]中选择 10 个分类 数据集 ,脚标最大的一个是类变量 ,其他的是属性变 量. 从其中 3 个数据集 heart_disease、breast_cancer 和 cmc 学习得到的贝叶斯网络结构如图 6 所示. 基 于扩展的熵离散化和聚类离散化 2 种方法 ,对类变 第 6 期 王双成 ,等 :用于因果分析的混合贝叶斯网络结构学习 ·87 ·
·88 智能系统学报 第2卷 量的预测能力（推理能力）比较情况如表1所示 于扩展熵离散化方法学习得到的贝叶斯网络，对属 性变量的预测能力也可得到类似的结果，可知，基于 聚类离散化方法学习得到的贝叶斯网络在推理方面 X 更加可靠 4结束语 Xio 建立了具有连续变量的贝叶斯网络结构迭代学 Xa 习方法，在迭代中过程中，一方面，通过基于父结点 结构和Gibbs sampling进行混合数据聚类来实现 (a)heart disease 连续变量的离散化，并根据离散变量的马尔可夫毯 和MDL打分确定离散变量的最优维数，这样能够 有效地动态继承变量之间的因果关系；另一方面，基 于依赖分析方法的贝叶斯网络因果结构优化调整使 X 变量之间因果关系不断得到改进，逐渐趋于稳定.该 方法避免了使用基于扩展的熵离散化方法和打分 搜索结构学习方法所带来的主要问题，同时，也可用 (b)breast cancer 于其他具有连续变量的相关问题 参考文献： [1]PEARL J.Probabilistic reasoning in intelligent systems: networks of plausible inference[M].San Mateo,Morgan Kaufmann,1988 [2]HECKERMAN D,GEIGER D,CHICKERING D M. Learning Bayesian networks:the combination of knowl- edge and statistical data[J].Machine Learning,1995,20 (c)cme (3)：197.243. 图6学习得到的贝叶斯网络结构 [3]SPIRTES P,MEEK C,RICHARDSON T.Causal in Fig.6 Learned Bayesian network structures 表12种离散化方法在推理能力方面的比较 ference in the presence of latent variables and selection bias[A].Proceedings of the 11th Annual Conference on Table 1 The comparison of two discretizing methods Uncertainty in Artificial Intelligence C].Pittsburgh, in inference respect USA,1995 基于扩展 基于聚类变量 数据集 熵离散化 离散化数量 [4]CHIC KERIN G D M.Learning equivalence classes of iris 95.334.2797.334.425 Bayesian network structures [J].Machine Learning, liver disease 56.572.6256.572.62 7 2002,2(3):445-498. pima_indians_diabetes 70.78±3.8374.55±2.63 9 [5]HENSON J.Comparing causality principles[J ]Studies heart disease 77.40±5.8086.66±5.2814 in History and Philosophy of Modern Physics,2005,36 new_thyroid 74.76±占.9274.76±5.92 6 (3):519-543 cme 44.00±4.5142.30±3.6810 wdbc 93.16±1.6697.02±1.9332 [6]THIESSON B,MEEK C,CHICKERINGD,HECKER- breast caneer 74.48±3.4475.85±3.4410 MAN D.Learning mixtures of Bayesian networks [R]. Thyroid0387 66.40±2.7666.602.5822 MSR-TR9730,1997. sick euthyroid 90.76±1.1791.55±1.1125 [7]MURPHY K P.Inference and learning in hybrid Bayes- ian networks[R].CSD-98-990,1998. 从表1中可以看出，基于聚类离散化方法学习 [8]MONTI S,COOPER G F.learning hybrid Bayesian net- 得到的贝叶斯网络对类变量的预测能力明显优于基 works from data[R].ISSP-97-01,1997 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
量的预测能力(推理能力) 比较情况如表 1 所示. 图 6 学习得到的贝叶斯网络结构 Fig. 6 Learned Bayesian network structures 表 1 2 种离散化方法在推理能力方面的比较 Table 1 The comparison of two discretizing methods in inference respect 数据集 基于扩展 熵离散化 基于聚类 离散化 变量 数量 iris 95. 33 ±4. 27 97. 33 ±4. 42 5 liver_disease 56. 57 ±2. 62 56. 57 ±2. 62 7 pima_indians_diabetes 70. 78 ±3. 83 74. 55 ±2. 63 9 heart_disease 77. 40 ±5. 80 86. 66 ±5. 28 14 new_thyroid 74. 76 ±5. 92 74. 76 ±5. 92 6 cmc 44. 00 ±4. 51 42. 30 ±3. 68 10 wdbc 93. 16 ±1. 66 97. 02 ±1. 93 32 breast_caneer 74. 48 ±3. 44 75. 85 ±3. 44 10 Thyroid0387 66. 40 ±2. 76 66. 60 ±2. 58 22 sick_euthyroid 90. 76 ±1. 17 91. 55 ±1. 11 25 从表 1 中可以看出 ,基于聚类离散化方法学习 得到的贝叶斯网络对类变量的预测能力明显优于基 于扩展熵离散化方法学习得到的贝叶斯网络 ,对属 性变量的预测能力也可得到类似的结果 ,可知 ,基于 聚类离散化方法学习得到的贝叶斯网络在推理方面 更加可靠. 4 结束语 建立了具有连续变量的贝叶斯网络结构迭代学 习方法 ,在迭代中过程中 ,一方面 ,通过基于父结点 结构和 Gibbs sampling 进行混合数据聚类来实现 连续变量的离散化 ,并根据离散变量的马尔可夫毯 和 MDL 打分确定离散变量的最优维数 ,这样能够 有效地动态继承变量之间的因果关系 ;另一方面 ,基 于依赖分析方法的贝叶斯网络因果结构优化调整使 变量之间因果关系不断得到改进 ,逐渐趋于稳定. 该 方法避免了使用基于扩展的熵离散化方法和打分2 搜索结构学习方法所带来的主要问题 ,同时 ,也可用 于其他具有连续变量的相关问题. 参考文献 : [1 ] PEARL J. Probabilistic reasoning in intelligent systems: networks of plausible inference[ M]. San Mateo , Morgan Kaufmann , 1988. [2 ] HECKERMAN D , GEIGER D , CHICKERIN G D M. Learning Bayesian networks: the combination of knowl2 edge and statistical data[J ]. Machine Learning , 1995 , 20 (3) : 197 - 243. [ 3 ] SPIRTES P , MEEK C , RICHARDSON T. Causal in2 ference in the presence of latent variables and selection bias[ A ]. Proceedings of the 11th Annual Conference on Uncertainty in Artificial Intelligence [ C ]. Pittsburgh , USA , 1995. [ 4 ] CHICKERIN G D M. Learning equivalence classes of Bayesian network structures [ J ]. Machine Learning , 2002 , 2 (3) : 445 - 498. [5 ] HENSON J. Comparing causality principles[J ]. Studies in History and Philosophy of Modern Physics , 2005 , 36 (3) : 519 - 543. [ 6 ] THIESSON B , MEEK C , CHICKERIN G D , HECKER2 MAN D. Learning mixtures of Bayesian networks[ R ]. MSR2TR297230 , 1997. [7 ]MURPH Y K P. Inference and learning in hybrid Bayes2 ian networks[ R]. CSD2982990 ,1998. [8 ]MON TI S , COOPER G F. learning hybrid Bayesian net2 works from data[ R]. ISSP297201 , 1997. ·88 · 智 能 系 统 学 报 第 2 卷
第6期 王双成，等：用于因果分析的混合贝叶斯网络结构学习 ·89· [9]FA YYAD U,IRANI K.Mult-interval discretization of [19]王飞，刘大有，薛万欣.基于遗传算法的Bayesian网中 continuous-valued attributes for calssification learning 连续变量离散化的研究[U].计算机学报，2002,25 [A].Proceedings International Joint Conference on Arti- (8):794-800. ficial Intelligence[C].Chambery,France,1993. WANG Fei,LIU Dayou,XUE Wanxin.Discretizing [10]LAM W,BACCHUS F.Learning Bayesian belief net- continuous variables of Bayesian networks based on ge- works:an approach based on the MDL principle [J]. netic algorithms [J].Chinese Journal of Computers, Computational Intelligence,1994,10(4):269-293. 2002,25(8):794.800. [11]CHICKERING D M.Learning Bayesian networks is [20]MURPHY SL,AHA D W.UCI repository of machine NP-Hard[R].MSR-TR-94-17,1994. learning databases EB/OL ]http:/www.ics.uci [12]茆诗松，王静龙，濮晓龙.高等数理统计[M.北京：高 edu/~mlearn/ML Repository,2005-09-10. 等教有出版社，1998. 作者简介： [13]GEMAN S,GEMAN D.Stochastic relaxation,Gibbs 王双成，男，1958年生，教授，博士 distributions and the Bayesian restoration of images[J]. 主要研究方向为人工智能、机器学习和 IEEE Transactions on Pattern Analysis and Machine In- 数据挖掘及其在风险管理中的应用，先 telligence,1984,6(6):721-742. 后承担国家自然科学基金“面向智能信 [14]CHOW C K,LIU C N.Approximating discrete proba- 息处理的贝叶斯网络关键理论与方法研 bility distributions with dependence trees [J].IEEE 究”和“面向风险管理的贝叶斯网络与集 Transactions on Information Theory,1968,14(3):462 成研究”等课题，发表学术论文40余篇 .467. Email:wangsc @lixin.edu.cn. [15 ]BUNTINE W L.Chain graphs for learning[A].Pro- ceedings of the 17th Conference Artificial Intelligence 李小琳，女，1978年生，讲师，博士， [C].San Francisco,USA,1995. 主要研究方向为机器学习和数据挖掘， [16]DOMIN GOS P,PAZZANI M.On the optimality of the 先后参与国家自然科学基金2项，发表 simple Bayesian classifier under zero-one loss [J ]Ma- 学术论文16篇 chine Learning,1997,29(2.3):103.130. E mail lixl 126 @126.com. [17]王双成，苑森淼.具有丢失数据的贝叶斯网络结构学习 研究[J].软件学报，2004,15(7)：1030-1041. WANG Shuangcheng,YUAN Senmiao.Research on learning Bayesian networks structure with missing data 侯彩虹，女，1978年生，讲师，博士， [J ]Journal of Software,2004,15(7):1030-1041. 主要研究方向是智能控制和数据挖掘， [18]王双成，苑森淼.具有丢失数据的可分解马尔科夫网络 先后参与国家自然科学基金2项，发表 结构学习[U].计算机学报，2004,27(9)：1221-1228. 学术论文12篇. WANG Shuangcheng,YUAN Senmiao.Learning de- Email dhuhch @mail.dhu.edu.cn. composable Markov network structure with missing data [J].Chinese Journal of Computers,2004,27(9):1221 -1228 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
[9 ] FA YYAD U , IRANI K. Mult2interval discretization of continuous2valued attributes for calssification learning [ A ]. Proceedings International Joint Conference on Arti2 ficial Intelligence[C]. Chambery , France , 1993. [10 ]LAM W , BACCHUS F. Learning Bayesian belief net2 works: an approach based on the MDL principle [J ]. Computational Intelligence , 1994 , 10 (4) : 269 - 293. [11 ] CHICKERIN G D M. Learning Bayesian networks is NP2Hard[ R]. MSR2TR294217 , 1994. [12 ]茆诗松 ,王静龙 ,濮晓龙. 高等数理统计[ M ]. 北京 : 高 等教育出版社 , 1998. [13 ] GEMAN S , GEMAN D. Stochastic relaxation , Gibbs distributions and the Bayesian restoration of images[J ]. IEEE Transactions on Pattern Analysis and Machine In2 telligence , 1984 , 6 (6) : 721 - 742. [14 ]CHOW C K , L IU C N. Approximating discrete proba2 bility distributions with dependence trees [J ]. IEEE Transactions on Information Theory , 1968 , 14 (3) : 462 - 467. [15 ]BUN TIN E W L. Chain graphs for learning [ A ]. Pro2 ceedings of the 17th Conference Artificial Intelligence [C]. San Francisco , USA , 1995. [16 ]DOMIN GOS P , PAZZANI M. On the optimality of the simple Bayesian classifier under zero2one loss[J ]. Ma2 chine Learning , 1997 , 29 (2 - 3) : 103 - 130. [17 ]王双成 ,苑森淼. 具有丢失数据的贝叶斯网络结构学习 研究[J ]. 软件学报 ,2004 , 15 (7) : 1030 - 1041. WAN G Shuangcheng , YUAN Senmiao. Research on learning Bayesian networks structure with missing data [J ]. Journal of Software , 2004 , 15 (7) : 1030 - 1041. [18 ]王双成 ,苑森淼. 具有丢失数据的可分解马尔科夫网络 结构学习[J ]. 计算机学报 , 2004 , 27 (9) : 1221 - 1228. WAN G Shuangcheng , YUAN Senmiao. Learning de2 composable Markov network structure with missing data [J ]. Chinese Journal of Computers , 2004 , 27 (9) : 1221 - 1228. [19 ]王 飞 ,刘大有 ,薛万欣. 基于遗传算法的 Bayesian 网中 连续变量离散化的研究 [J ]. 计算机学报 , 2002 , 25 (8) : 794 - 800. WAN G Fei , L IU Dayou , XU E Wanxin. Discretizing continuous variables of Bayesian networks based on ge2 netic algorithms [J ]. Chinese Journal of Computers , 2002 , 25 (8) : 794 - 800. [ 20 ]MURPH Y S L , A HA D W. UCI repository of machine learning databases[ EB/ OL ]. http : / / www. ics. uci. edu/ ～mlearn/ MLRepository , 2005 - 09 - 10. 作者简介 : 王双成 ,男 ,1958 年生 ,教授 ,博士 , 主要研究方向为人工智能、机器学习和 数据挖掘及其在风险管理中的应用 ,先 后承担国家自然科学基金“面向智能信 息处理的贝叶斯网络关键理论与方法研 究”和“面向风险管理的贝叶斯网络与集 成研究”等课题 ,发表学术论文 40 余篇. E2mail : wangsc @lixin. edu. cn. 李小琳 ,女 ,1978 年生 ,讲师 ,博士 , 主要研究方向为机器学习和数据挖掘 , 先后参与国家自然科学基金 2 项 ,发表 学术论文 16 篇. E2mail : lixl_126 @126. com. 侯彩虹 ,女 ,1978 年生 ,讲师 ,博士 , 主要研究方向是智能控制和数据挖掘 , 先后参与国家自然科学基金 2 项 ,发表 学术论文 12 篇. E2mail : dhuhch @mail. dhu. edu. cn. 第 6 期 王双成 ,等 :用于因果分析的混合贝叶斯网络结构学习 ·89 ·