基于MDL原理与混合遗传算法的BAYESIAN网络结构学习.pdfVIP

维普资讯 2002年第 7期 微 电子学与计算机 27 基于 MDL原理与混合遗传算法的Bayesian网络结构学习 LearningBayesianNetworkStructuresBasedonMDLandHybridGeneticAlgorithms 合肥工业大学 彭青松 张佑生 汪荣贵 钱隆 骆祥峰 (合肥 230009) 摘 要：从大型数据库中学习Bayesian网络结构是 Bayesina 网络应用的难点之一 。在分析标准遗传算法与爬 山算法各 自优点与不足的基础上 ，将这两种算法相结合 ，以最小描述长度为评价函数 ，得到一种混合遗传算 法 ，实现 了它们 的优势互补 。文章给 出了混合遗传算法 的计算步骤 ，并通过对 ALARM数据库学习得到的 Bayesian网络结构 。 关键词：Bayesian网络，标准遗传算法，最小描述长度 ，爬山算法，结构学习 1 引言 法 中的评价 函数 ，同时应用 图像恢复 中遗传算法常 近年来 ，Bayesian网络(贝叶斯网络 ，BNS)引起 用 的窗 口交叉技术 …，并与爬 山算法相结合 ，对 了广泛 的关注 ，已广泛应用于故障诊断 ，语音识别 ALARM数据库进行 Bayesina 网络结构 的学习。 和医疗诊断等方面 。其关键技术之一是从实例数 据库获取较佳 的网络结构 ，即Bayesian网络 的结构 2 最小描述长度 学 习。 最小描述长度 (MDL)原理是 由Rissanen最先 Bayesian网络是有 向无环 图，其结点表示 随机 提 出的，它采用某种模型对需要保存 的数据进行压 变量 ，即一些互相独立且互相依赖变量之 间的关 缩编码 以保存数据 ，同时为了以后完全恢复被保存 系。结点间的有 向边表示结点与其双亲结点之 间的 的数据 ，还要保存所使用 的模型。因此 ，保存数据 的 概率依赖关系。Bayesian网络 由条件概率参数和网 总长度等于编码压缩后数据长度加上保存模 型所 络结构两部分组成 。若 Bayesian网络 的结点数为 n， 需的数据长度 ，称为总描述长度 。MDL要求选择总 Parent I)为结点 Xi的双亲结点集合 ，则结点 Xi的 描述长度最小 的模型 。本文将 Bayesina 网络作为对 条件概率分布为p(XiIPraent(Xi))。由概率的链式法则 实例数据进行压缩编码 的模型 ，将 MDL原理用于 知 ，Bayesina 网络 的联合概率分布为 ： Bayesian网络结构学 习。 n MDL包括两个部分 ，即 Bayesian网络结构 的描 p )=llp(XiIXl，X2，…，Xi—1) I．1 述长度与数据 的描述长度 ，二者之和构成 MDL。对 n 于样本容量为 m完备 的实例数据库 C，Bayesina 网 - - 1lpX(。IParent(X,)) I．1 络结构 BS的描述长度 DL为[6]： 从理论上讲 ，Bayesina 网络结构越复杂 ，则其对