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

1、收稿日期:2006-02-15;修返日期:2006-04-03 基金项目:国家自然科学基金资助项目(79990580作者简介:黄浩(1971-,男,湖北荆州人,讲师,博士研究生,主要研究方向为数据挖掘、机器学习(hvict ory10163.co m ;宋瀚涛(1940-,男,博导,主要研究方向为数据库、数据挖掘;陆玉昌(1940-,男,博导,主要研究方向为数据挖掘、机器学习.基于小生境遗传算法的贝叶斯网络结构学习算法研究*黄 浩1,宋瀚涛2,陆玉昌3(11对外经济贸易大学信息学院,北京100029;21北京理工大学计算机科学技术学院,北京100081;31清华大学计算机科学与技术系,北京10

2、0084摘 要:在数据缺失的情况下讨论一种贝叶斯网络的结构学习算法。该算法结合了小生境遗传算法和E M 算法,最后通过试验说明了该算法的有效性。关键词:贝叶斯网络;结构学习;小生境遗传算法;期望最大化算法中图分类号:TP30116 文献标志码:A 文章编号:1001-3695(200704-0100-04R esearch on Struct ure Learn i ng A lgorith m of Bayesian N et w orksBased on N iche G enetic A l gorit h mHUANG H ao 1,SONG H an -tao 2,LU Y u -c

3、hang 3(1.S chool o f Infor m ation Technol ogy,Un iversit y of In ternationa lBu si ness&E cono m ics ,B eiji ng 100029,Ch i na;2.S c hool of C o mputer S cience &Technol ogy,B eiji ng In stit u t e of Technol ogy,B ei j i ng 100081,China;3.D e pt .o f Compu ter S cie n ce&Technolo gy,Ts

4、i nghua University ,B ei -jing 100084,Ch i na Abstract :Th is paper researched a learn i ng al gorith m of bayesian net works i n i nco mp lete dataw hich algori th m comb i ned n ichegeneti c al gorith m w ith E M algorit h m.Then t he experm i ent shows the al gorith m i s vali d .Key words :Bayes

5、ian net works ;struct ure l earni ng ;n iche genetic algorith m;E M algorit h m 目前,从完整数据中学习参数和网络结构以及在固定网络结构的前提下从不完整数据中学习参数已经有比较成熟和相对完善的方法13。但是,从不完整数据集中学习网络结构仍然是一个比较困难的问题。从不完整数据集中学习贝叶斯网络是具有重要现实意义的。这是因为,现实世界中的大部分数据经常是不完整的。贝叶斯网络一个经常被引述的优点就是可以用严格的方法对不完整数据进行推断。因此,没有理由要求用于训练的数据必须是完整的。在从不完整数据集中学习贝叶斯网络结构方面,

6、Fr ied m an 做出了开创性的工作4,5。他的方法就是交替进行网络结构的贪婪搜索过程和参数评估的E M 过程。其算法的关键在于,只对当前选中的网络结构使用E M 算法(SE M 算法,进行参数估计,对于未被选中的网络并不使用E M 算法;之后对所有的候选结构进行评价,每评价一个当前网络的邻居集,只调用一次E M 算法。因为E M 算法的计算强度是比较高的,所以能比较显著地节省计算开销。不过,F ried m an 注意到SE M 算法容易陷入局部最大值。为了缓解局部最大值问题,通常从新的、随机产生的网络开始多次运行搜索算法。一些分析证实从不完整数据中进行网络结构的搜索是一个非常困难的问

7、题6,7。特别是当搜索空间巨大、高维且具有多峰值时,即使多次运行确定性搜索方法也不能收到好的效果。为了从复杂的搜索空间中搜索到好的网络结构,避免陷入局部最大值,遗传算法、M C M C 算法等逐渐受到越来越多的重视。La rranaga 等人讨论了利用遗传算法进行结构学习8,采用连接矩阵表示网络结构,设计了基于Bayesi an 方法的适应度函数及选择、重组、变异算子,对遗传算法的控制参数进行了性能分析。M yersW.等人改进了La rranaga 等人的工作9,10,采用遗传操作把不完备数据转换成完备数据,同时遗传网络结构和遗漏的变量值。W.M yers 等人的方法可以避免陷入局部极值,但

8、缺点在于指数级地扩大了搜索空间;而且遗传算子把不完备数据转换成完备数据时,无法反映遗漏数据实际具有的概率分布,难以保证算法的收敛性。1 遗传算法遗传算法(G enetic A lgor it h m,GA 是模拟自然界生物群体进化过程的一种随机优化方法,具有不依赖于问题模型的特性、寻优过程的自适应性、隐含的并行性、解决复杂非线性问题的鲁棒性以及对优化目标函数无须连续、可微等苛刻条件等优点,并在许多复杂优化问题的应用中都找到了令人满意的解,从而使得该算法在工程领域得到了广泛应用。在遗传算法中,将n 维决策向量X 用n 个记号X i (i =1,2,n所组成的符号串表示为X =X 1X 2,X n

9、 。其中每个X i 可以看成一个遗传基因,它的所有可能取值称为等位基因。这样X 可以看成是由n 个遗传基因所组成的染色体。一般情况第24卷第4期2007年4月计算机应用研究Application R esearc h of C o m putersVo.l 24,N o .4April 2007下,染色体的长度n 是固定的,但对某些问题n 也可以是变化的。编码所形成的排列形式是个体X 的基因型,与之对应的值是个体X 的表现型。通常个体的表现型与基因型是一一对应的,但有时也允许基因型与表现型是多对一的关系。对于每一个个体X,要按照一定的规则确定其适应度。个体X 的适应度与其对应的表现型的目标函数

10、值相关联,X 越接近目标函数的最优点,其适应度越大;反之,其适应度越小11。生物的遗传过程主要是通过染色体之间的重组和染色体变异来完成的。与此对应,遗传算法中最优解的搜索过程也模仿生物的遗传过程,使用遗传算子作用于群体P (t,得到下一代群体P (t +1。遗传算子主要包括下面三种:(1选择。根据各个体的适应度,按照一定的规则或方法,从第t 代群体P (t中选择一些优良的个体遗传到下一代群体P (t +1中。(2重组。将群体P (t内的各个体随机搭配成对;对每一对个体,以某个概率(称为重组概率交换它们之间的部分染色体。(3变异。对群体P (t中的每一个体,以某一概率将某一个或某一些基因位上的基

11、因值改变成其他等位基因。基本的变异算子操作包括三种:其中两种是在等位基因中增加一个父亲节点或删除一个父亲节点,相当于在网络结构中增加或删除一条指向变量的弧;第三种变异算子是逆转一条弧,这可以通过删除一条从父亲到孩子的弧,添加一条从孩子到父亲的弧来实现。2 小生境遗传算法遗传算法主要的问题就是算法最终并不能保证收敛到全局最优解,而过早地收敛到某个局部极值点。产生这一现象的根源在于每一代群体进化完成后,必须通过选择算子按照适应度优先原则挑选出适应度较好的个体形成下一代种群。那么就会有一部分个体被淘汰,这可能造成一些有价值的模式丢失;同时也会使得一些早期适应度较好的个体迅速占领种群。这样就导致无法得

12、到最优解。虽然遗传操作中的变异算子可以对早熟现象产生一定的抑制作用,可以增加新模式的产生,但过高的变异概率会使算法趋于随机搜索,导致算法出现振荡而不容易收敛,使得搜索性能下降。需要在算法中引入一种机制,既可以保证种群的多样性,同时又能保证算法的高效性。关于这方面针对经典遗传算法的改进工作已经进行了很多。其中小生境(N i che技术与经典遗传算法的结合取得了很好的效果。在自然界中,/物以类聚,人以群分0的小生境现象普遍存在。生物总是倾向于与自己特性、形状相类似的生物生活在一起。受此启发,近年来人们将小生境现象引入到遗传算法中。实践证明,这一技术对于改善遗传算法的全局收敛性能具有良好的效果12。

13、基于此,在本文算法中采用了将典型小生境技术12结合最优保留策略13的最优选择方法来进行种群的选择。具体思想为:首先随机地把整个群体分解成若干个小生境(子种群。父代个体的交叉操作仅限于各个小生境内部独立进行;子种群之间不进行交叉操作。在每个小生境的交叉操作后立即应用最优选择机制,即小生境中的全体父代个体和由它 们繁殖的全体子代个体共同竞争,从中找出当前群体中适应度最好的个体;然后,将除当前最佳个体外的其余个体按照适应度大小进行排序,并运用轮盘赌机制选择优良个体保留到下一代。若当前的最好个体t c 优于迄今为止的最佳个体t ,则当前最差个体被迄今为止的最佳个体取代,并复制当前的最好个体t c 作为

14、迄今为止的最佳个体t ;否则,仅用迄今为止的最佳个体t 取代当前的最好个体t c ,变异操作也在各个小生境中按概率P m 进行,对小生境中的最佳个体变异时应用(1+1选择,以保证全局收敛性,对其他个体仅作变异,不作选择。各个子种群之间也存在竞争。首先计算各个子种群的平均适应度,适应度大的子种群能获得较大种群数目,而适应度较小的子种群就只有较小的种群数目。但为了保持种群的多样性,必须限制优势子种群的规模以及保护劣势子种群。这样就需要人为地规定一个最大种群规模S m ax 和最小种群规模S m in 。如果一个最小种群规模的子种群在经历几代进化后,依然无法改进平均适应度,则将该子种群淘汰;而且,如

15、果两个子种群之间适应度分布很接近,那么同样淘汰其中一个。当一个子种群被淘汰后,就随机生成一个新的子种群来代替。一轮进化操作完成后,将各个子种群的最优秀的个体复制到精华种群中,然后在精华种群中实施与其他种群相似的进化操作,并产生出优秀个体。3 E M-NGA 算法针对数据有缺失的情况,利用E M 算法解决数据不完整情况下的结构学习。算法的基本思想是:首先从初始群体中任意选择一个个体,也就是一个初始的网络结构;再根据这个网络结构和缺失的数据计算E M 算法中的E 步(求期望的计算;然后对E 步的结果求极大值,得到补充的数据;在补充完整的数据之上进行上述的小生境遗传算法操作;一轮完成后,得到一个最优

16、个体,在这个最优个体上,重复以上的E M 算法。另外,一个变量可以从没有父亲到有n -1个父亲。那么,一个等位基因可以有Emi =1C i n -1种取值。其中m 是每个变量可以具有的最大父亲节点数目。由于本文的目标是学习尽量简单的网络结构,限制变量的父亲节点数目是合理的。另外,经过交叉和变异操作后,可能产生出非法结构,即产生出有向循环图。如出现了有向循环图,则将其适应度设成一个较低的值。在算法中允许出现非法结构的原因是,非法结构中可能蕴涵着较好的局部结构,可以通过交叉、变异等操作遗传给下一代。因此,在遗传操作产生新的个体后,需要两步检查:检查新个体是否满足每个变量最多有m 个父亲的约定。如果

17、某个等位基因不满足约定,有两种解决方法:随机地选择k 个父亲(0k m ;采用局部优化的方法,选出不超过m 个父亲的最优子集。显然前者盲目性强、效果差,因此本文采用后者。判断新个体是否为非法结构,并给非法结构的适应度赋予一个较小的值。E M-NGA 示意图如图1所示。E M-NGA (E M-N ich i ng GA ,主要针对M yers W.和F ried -m an 等人的算法进行了改进。算法的过程如下:#101#第4期黄 浩等:基于小生境遗传算法的贝叶斯网络结构学习算法研究(1使用精华种群中最优秀的个体(如果是算法首次执行,那么就随机生成一个初始网络Sc,利用E M算法对不完整数据集

18、D进行完备化,得到完整的数据集Dc。(2如果算法是首次执行,那么就随机生成k组初始化网络结构,形成k个小生境,每一组保持r个个体;否则就直接执行(3,进行下一轮进化。(3对任意一个小生境初始群体S$,按概率Pc 和Pm进行交叉或变异操作。如果变异操作在该种群的最优个体t上发生,那么必须在变异前和变异的两个个体中选择更好的个体,而其余变异操作后不作选择。这样就得到进化后的群体S$c。其中,Pc 和Pm分别表示进行交叉和变异操作的概率;(4对于S$c中的每一个网络S,进行如下几步:如果网络S不满足每个变量最多有m个父亲的约定,则采用局部优化方法,选出不超过m个父亲的最优父节点集合。检查网络S是否包

19、含非法结构,即判断网络S中是否存在有向环。如果网络S包含非法结构,则给网络S赋予一个较小的适应度;否则,按照下面的公式计算其适应度FS :FS=M DL_score(S B Dc 。其中,M DL_score(S B Dc就是网络S与数据集Dc的M DL评价。计算网络S的被选择概率PS: P S=rank(F S/r j(r j+1/2其中,rank(FS 表示适应度FS的等级,它的值根据FS的大小来划分;rj表示进化群体的规模。(5按照S$c中每个网络S的选择概率PS和轮盘赌的机制选取rj个个体进入下一代,并更新S$;然后从更新的种群中选择最优的个体t c。如果t c优于迄今为止的最佳个体t

20、,则当前最差个体被迄今为止的最佳个体取代,并复制当前的最好个体t c作为迄今为止的最佳个体t;否则,仅用迄今为止的最佳个体t取代当前的最好个体t c。(6选出每个子群中的最优秀个体,记录到每个子群中,同时将最优个体复制到精华种群。(7计算各个子群的平均适应度,比较子群的适应度相似程度,相似的两个子群将淘汰其中一个,随机生成另外一个子群代替;同时对种群数目为Sm i n的子群连续进化的代数进行计数,超过预定代数的子群将被淘汰。同样随机生成另外一个子群取而代之。(8在精华种群中进行与每个子群相似的遗传进化操作。(9在精华种群中选取S c,使得FS c =m ax argS(FS。如果FS c &g

21、t;FS c,则Sc=S c。判断算法终止条件是否满足。如果满足则退出;否则,转(1继续进化。在(4中,判断网络S是否包含有向环,可以用函数Is_cy-cli c(S实现,如下所示:Function Is_cycli c(S/如果网络S中包含有向环,返回/真0;否则,返回/假0For each X I U DoAncestor(X=Get_ancestor(X,X,<If X I Ancestor(XTh en Ret urn(trueReturn(fals e;Functi on Get_ancestor(X,X c,Ancest or(X/变量X的所有祖先,并用Ancestor(X表

22、示For each V I PX cDo/P X c表示变量X c的父节点集合If V=X ThenAncestor(X=Ancestor(X+V;/V表示由变量V构成的集合break;/跳出循环E l se ifV|An cest or(XThenAncestor(X=Ancestor(X+V;Ancestor(X=Get_ancestor(X,V,An ces t or(X;Return(Ancest or(X;4试验分析在与M yers W.等人的EA算法和F r i ed m an的SE M算法进行试验比较时,使用了M yersW.等人9所用的A SI A网络。利用A SIA网络,随机

23、生成3000个训练样本。算法分别在包含0、5%、15%和30%的缺值数据情况下运行。实验结果是每一种缺值情况下10次运行的平均值;算法终止条件也是连续进化2000代。每一次使用学习到的最/好0网络计算其对数损失。此外,初始进化群体由下面的方法获得:在上述存在缺失数据的3000个样本中,用一个计算机程序创造一个假想的完备数据集,在完备数据集条件下选择出一些较好的网络结构作为初始群体。当前的候选网络从初始群体中随机产生。在试验中,将变异概率和交叉概率分别设置为0105和015;群体规模Sm in=30,Sm ax=100。两种算法的对数损失如图2(a所示。从图中可以看出,随着缺值数据的增加,两种算

24、法的预测精度都有所下降。EA 和E M-NGA在0、5%和15%的缺值情况下都能发现比较好的网络结构。而当缺值数据达到30%时,两者的预测精度显著下降。整体而言,E M-NGA的性能优于M yers W.的EA方法,特别是在有30%缺值数据的情况下。图2(b是对这三个算法进行收敛速度和精度的比较,在数据缺失20%的情况下, 50m in大概进化到第5000代。从图中可以看出,SE M算法执行的速度是最快的,收敛速度也是最快的,但与另外两个算法比较发现,SE M所学习到的精度往往会差一些。这说明SE M 算法陷入了局部极值中,而且数据缺失比例越大,出现这种情况的概率就越大。说明在数据不完整时,解

25、空间会变得不光滑,会出现很多局部极值,SE M算法容易陷入局部极值而无法发现更好的解。遗传算法的表现就更鲁棒一些。比较E A和E M-NGA发现,最终两个算法能收敛到比SE M算法更好的解,但E M-NGA收敛的速度更快,收敛的结果也更好,而且收敛的一致性更好一些。分析认为,E M-NGA在每一代进化中都会记录下最优个体,这保证了算法最终会收敛到最优解,同时能加快算法收敛的速度;同时,小生境技术使得种群的多样性得到保证,使算法在收敛行为上表现出更好的一致性和稳定性。最后通过试验比较变异概率与交叉概率对E M-NGA算法的影响,实验结果如图3所示。从图中可以看出,变异概率的选择对算法会有比较明显

26、的影响。当变异概率达到011时,算法表现出明显的收敛不稳定情况,而在变异概率为0105和#102#计算机应用研究2007年0101时,算法都表现了良好的收敛特性,并且变异概率为0101时,收敛更早,而且收敛曲线更平坦;交叉概率对整个算法的收敛行为影响并不大,只是在算法开始阶段会表现得略微不同。算法中种群数目的选择直接参照了文献8 。参考文献:1COOPER G F ,HERSKOVI TS E.A bayes i an m et h od f or t he i nduc -ti on of p robab ili sti c net w orks from data J.M achine L

27、earning ,1992,9(4:309-347.2H ECKER M AN D.A t u torial on learn i ng b ayes i an n et w or k,M SR -TR-95-06R.S.l :M icrosoftResearch,1995.3LAM W,BACCHUS F .Learn i ng bayes i an belief n et w ork s :an ap -proach based on the M DL p ri nci p l e J .Computati ona l I ntell -i gence ,1994,10(4:269-293

28、.4FR I ED M AN N .The bayes i an stru ctural E M al gorith m:the 14th Con-ference on Uncert a i nty i n Artifi cial Intelligen ce C .San M at eo :M organ K auf mann,1998:80-89.5FRI ED M AN N .Learn i ng belief n et w or k s i n t he presence of m issing values and hidden variables :p roceed i ngs of

29、 t h e 14th Inter n ati on al C on f eren ce on M ach i n e Learn i ngC.N ashville :M organ Kau f m ann ,1997:125-133.6GE I GER D ,M EEK C.G raph i calm odels and exponenti al f am ilies :the 14th Con ference on Uncert a i nty i n A rtifici al I n telli genceC .San M ateo :M organ K auf m ann ,1998:

30、156-164.7SETT I M I R,S M I TH J Q.On t h e geo m etry of bayesian graph icalm o -delsw it h h i dden variab l es :the 14t h Internati onal Joi nt Con-ference on Arti fi cial I n telli genceC .San Francisco :M organ Kau f m ann ,1998:472-479.8LARRANAGA P ,POZ A M.Stru cture l earn i ng of bayesian n

31、et w orks by genetic al gori thm s :a perf or m ance anal ys i s of contro l para m et ers J .I EEE Journal on Pattern A na l ys i s and M achine I n tell -i gence ,1996,18(9:912-926.9M YERS J W,LASKEY K B,DE J ONG K A.L ear n i ng b ayes i an ne-tw ork s fro m i nco mp lete dat a us i ng evol u tio

32、nary al gorith m s :the Genetic and Evo l uti onary C o m putati on Con feren ceC .S an M ateo :M organKau f m ann ,1999:458-465.10M YERS J W,LASKEY K B,LEVI TT T S.Learn i ng bayes i an ne-tw ork s fro m i n co m plete data w it h stochas tic s earch algorit hm s :t he Un -cert a i nty i n Arti fi

33、cial In telli genceC .San Franci sco :M organ Kau-f mann Pub lis h ers ,1999:476-485.11田凤占.贝叶斯网络方法研究D.北京:清华大学,2002.12J ELASI TYM ,DO M B I T .GAS,a con cep t on m odeli ng s peci es i n ge -netic al gorit hm J.Artifici a l Intelligence ,1998,99(1:1-19.13金菊良,杨晓华,丁晶.标准遗传算法的改进方案加速遗传算法J.系统工程理论与实践,2001,2

34、1(4:8-13.(上接第99页表2 各实现结构性能综合比较等级平稳性能可靠性(当p =P i 1P i 2P i 3P i 4P i 5011015018T c 3优优优优优优优差T 1中良良良中优中差T 2优良良良良良差差T 3优优优优优中差差5 结束语不同于以往的生物启发网络安全研究,B M N S M 首次充分考虑了生物界(人类的立体特征,为该领域的研究提供了一个新的研究视角。作为B MN S M 的核心,TNP 模式实现结构的选择将直接决定着该模型各项性能的发挥,通过对传统初级结构T 1、进化结构T 2和T 3,以及高级结构T c 3的平稳性能和可靠性各项指标的定量分析比较,得出了T c 3是TN P 模式较理想的实现结构这一结论。将来的研究工作将集中在T c 3的具体实现上。参考文献:1FORREST S,PERELSON A,ALLEN L ,et a l .Sel-f nonselfd iscri m -i nati on i n a co m puter :p roceed i ngs of t he I EEE Sy m pos i um on Re -search i n Sec u rit y and PrivacyC .LOS A la m ilos :I EEE Co m