第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 ·