基于小生境遗传算法的贝叶斯网络结构学习算法研究

贝叶斯 结构 优化算法 有遗传算法

第24卷第4期2007年4月

计算机应用研究ApplicationResearchofComputers

Vo.l24,No.4

April2007

基于小生境遗传算法的贝叶斯网络结构

*

学习算法研究

黄 浩,宋瀚涛,陆玉昌

1

2

3

(11对外经济贸易大学信息学院,北京100029;21北京理工大学计算机科学技术学院,北京100081;31清华大学计算机科学与技术系,北京100084)

摘 要:在数据缺失的情况下讨论一种贝叶斯网络的结构学习算法。该算法结合了小生境遗传算法和EM算法,最后通过试验说明了该算法的有效性。

关键词:贝叶斯网络;结构学习;小生境遗传算法;期望最大化算法

中图分类号:TP30116 文献标志码:A 文章编号:1001-3695(2007)04-0100-04

ResearchonStructureLearningAlgorithmofBayesianNetworks

BasedonNicheGeneticAlgorithm

HUANGHao1,SONGHan-tao2,LUYu-chang3

(1.SchoolofInformationTechnology,UniversityofInternationalBusiness&Economics,Beijing100029,China;2.SchoolofComputerScience&Technology,BeijingInstituteofTechnology,Beijing100081,China;3.Dept.ofComputerScience&Technology,TsinghuaUniversity,Bei-jing100084,China)

Abstract:Thispaperresearchedalearningalgorithmofbayesiannetworksinincompletedatawhichalgorithmcombinedniche

geneticalgorithmwithEMalgorithm.Thentheexpermientshowsthealgorithmisvalid.Keywords:Bayesiannetworks;structurelearning;nichegeneticalgorithm;EMalgorithm 目前,从完整数据中学习参数和网络结构以及在固定网络结构的前提下从不完整数据中学习参数已经有比较成熟和相对完善的方法[1~3]。但是,从不完整数据集中学习网络结构仍然是一个比较困难的问题。从不完整数据集中学习贝叶斯网络是具有重要现实意义的。这是因为,现实世界中的大部分数据经常是不完整的。贝叶斯网络一个经常被引述的优点就是可以用严格的方法对不完整数据进行推断。因此,没有理由要求用于训练的数据必须是完整的。

在从不完整数据集中学习贝叶斯网络结构方面,Friedman做出了开创性的工作[4,5]。他的方法就是交替进行网络结构的贪婪搜索过程和参数评估的EM过程。其算法的关键在于,只对当前选中的网络结构使用EM算法(SEM算法),进行参数估计,对于未被选中的网络并不使用EM算法;之后对所有的候选结构进行评价,每评价一个当前网络的邻居集,只调用一次EM算法。因为EM算法的计算强度是比较高的,所以能比较显著地节省计算开销。不过,Friedman注意到SEM算法容易陷入局部最大值。为了缓解局部最大值问题,通常从新的、随机产生的网络开始多次运行搜索算法。

一些分析证实从不完整数据中进行网络结构的搜索是一个非常困难的问题

[6,7]

最大值,遗传算法、MCMC算法等逐渐受到越来越多的重视。

Larranaga等人讨论了利用遗传算法进行结构学习[8],采用连接矩阵表示网络结构,设计了基于Bayesian方法的适应度函数及选择、重组、变异算子,对遗传算法的控制参数进行了性能分析。MyersW.等人改进了Larranaga等人的工作[9,10],采用遗传操作把不完备数据转换成完备数据,同时遗传网络结构和遗漏的变量值。W.Myers等人的方法可以避免陷入局部极值,但缺点在于指数级地扩大了搜索空间;而且遗传算子把不完备数据转换成完备数据时,无法反映遗漏数据实际具有的概率分布,难以保证算法的收敛性。

1 遗传算法

遗传算法(GeneticAlgorithm,GA)是模拟自然界生物群体进化过程的一种随机优化方法,具有不依赖于问题模型的特性、寻优过程的自适应性、隐含的并行性、解决复杂非线性问题的鲁棒性以及对优化目标函数无须连续、可微等苛刻条件等优点,并在许多复杂优化问题的应用中都找到了令人满意的解,从而使得该算法在工程领域得到了广泛应用。

在遗传算法中,将n维决策向量X用n个记号Xi(i=1,2,,,n)所组成的符号串表示为X=X1X2,Xn。其中每个Xi可以看成一个遗传基因,它的所有可能取值称为等位基因。这样X可以看成是由n个遗传基因所组成的染色体。一般情况

。特别是当搜索空间巨大、高维且具有多

峰值时,即使多次运行确定性搜索方法也不能收到好的效果。为了从复杂的搜索空间中搜索到好的网络结构,避免陷入局部

收稿日期:2006-02-15;修返日期:2006-04-03 基金项目:国家自然科学基金资助项目(79990580)

作者简介:黄浩(1971-),男,湖北荆州人,讲师,博士研究生,主要研究方向为数据挖掘、机器学习(hvictory10@163.com);宋瀚涛(1940-),男,(,,