基于新型二进制自适应差分演化算法的贝叶斯网络学习∗

赵文强 赵 熙 刘 瀚

（武汉市武昌区长虹桥37-1号 武汉 430064）

基于新型二进制自适应差分演化算法的贝叶斯网络学习∗

赵文强 赵 熙 刘 瀚

（武汉市武昌区长虹桥37-1号 武汉 430064）

贝叶斯网络是处理不确定的专门知识和推理的最流行的方法，并广泛应用于大量研究领域。贝叶斯网络学习的主要策略是利用统计评分来选择最优网络的候选者。论文提出了基于新型二进制自适应差分演化算法的贝叶斯网络学习（BDENBAL），该方法采用一种自适应的0∕1矩阵作为比例因子，并通过交叉和变异算子来实现贝叶斯网络的学习过程中的信息交换。然后根据贝叶斯信息标准（BIC）评分从网络空间中选择贝叶斯网络候选者。实验结果证明本文提出的方法具有优良的性能。

贝叶斯网络；差分演化；贝叶斯信息标准

1 引言

随着人工智能的发展，Pearl在20世纪80年代提出了贝叶斯网络。如今，贝叶斯网络是处理不确定的专门知识和推理的最流行的方法［1］。由于其强大的概率推理功能，贝叶斯网络被应用于大量研究领域，例如：专家系统、医疗系统、制造系统、语音识别、数据挖掘、经济活动分析、军事对抗和预测［2］。

目前，有两种策略被应用于贝叶斯网络学习中：一、通过评估网络节点间的假定独立关系来构建贝叶斯网络［3］；二、利用统计评分从网络模型空间中选择典型的候选者。最流行的评分函数包括CH评分［4］、BIC评分［5］、MDL评分［6］、AIC评分［7］等。

由于学习贝叶斯网络是个NP难的问题［8］，基于启发式搜索（例如：随机局部搜索、遗传算法、演化算法）的学习算法通常能够找到近似最优贝叶斯网络［9］。AMS-EM 学习算法采用确定性搜索［10］。AMS-EM的初始网络选择取决于先验概率。选择不同的初始网络结构可能会造成收敛结果模型的分布区不同。因此，AMS-EM可以发现局部最优的网络结构。EGA［11］是一个基于遗传算法的随机搜索算法。和AMS-EM相比，EGA能够找到最优的网络结构，因为它仅编码网络结构并通过数学期望转换不完全数据。Friedman将马尔可夫链蒙特卡尔理论（MCMC）应用到不完全数据的贝叶斯网络学习中得到EM-MCMC算法［12］，同时还提出结构化的EM算法（SEM）。SEM算法将EM算法应用到网络参数优化，并将结构搜索方案应用到模型的选择。

标准差分演化算法（DE）在连续值搜索空间中具有更快的搜索速度和更高的精确度。DE算法的演化算子会使该算法很难直接用于离散空间，为了解决此问题，Engelbrecht提出二进制差分演化算法（BDE）［13］，通过使用三角函数实现了连续空间到二元空间的转换，标准测试函数已证明BDE算法的搜索准确率要高于二进制粒子群优化算法。此外，他和Han提出了一种使用逻辑操作代替算术计算的新算法来提高BDE算法在二元空间中的表现。

本文提出了一种用于贝叶斯网络学习的新型二进制自适应差分演化算法（BDENBAL）。通过使用交叉算子和变异算子，BDENBAL算法实现了贝叶斯网络中的信息交换。基于BIC评分标准，BDENBAL算法从网络模型空间中选出了最优的典型候选者。

2 背景

2.1 编码方案

贝叶斯网络表示出变量之间的条件概率与有向无环图（DAG）。一个有向无环图可以表示为（A，B），其中A代表一组顶点，B代表一组边。一个贝叶斯网络矩阵X（i，j）（i=1，…N，j=1，…N）可以由当前的DAG构成，如图1所示。所有矩阵中的元素为0或1。如果点vi和点vj之间存在一条有向边bij(vi→ vj)，X（i，j）等于1，否则为0。因此，演化算法的热色体可以被构造为(X1,…Xi,…Xd)，其中每一个遗传因子都是一个贝叶斯网络矩阵。

2.2 适应度函数

作为选择模型中的一种典型评分函数，贝叶斯信息评分标准是边缘似然函数的大样本近似［2］。与拉普拉斯近似一致，我们可以获得大样本近似G（s|D）来获得作为后验概率对数的BIC评分函数。logG(s|D)可以近似为

上述公式中，D是数据集合，s是贝叶斯结构，α*是贝叶斯参数α的最大似然估计值，M是样本数量。

本文中，BIC评分被选作二进制差分演化贝叶斯网络学习的适应度函数。在贝叶斯网络结构学习的过程中，每个网络的候选者对应一个BIC评分，学习结果将会是该网络的BIC最大得分。

2.3 循环规避

本文中，贝叶斯网络矩阵被选作判断矩阵。贝叶斯网络的回路可根据所有对角线元素之和来检测。如果贝叶斯网络中存在一个循环，则总和将不为0，且有循环的贝叶斯网络应该被丢弃。

3 算法

本文提出的算法包括更新贝叶斯参数和在更新后的贝叶斯网络的基础上对其进行选择。通过变异算子和交叉算子来实现学习过程中的贝叶斯网络信息交换。在模型的选择方面，通过使用BIC评分来达到贪婪策略的实现。

3.1 变异操作

标准差分演化算法将基于浮点数的编码机制用于编码方案。本文提出的BDENBAL算法将一种二元矩阵替代真实数字并用于编码方案中。各元素在各个位上的值只有1或0。此外，BDENBAL算法在标准差分演化算法中使用逻辑计算代替了算术计算。

对于某一个体Si,H;i=1,2,…,NP，如下公式推理可以得到另一个体Wi,H=(W1i,H+1,W2i,H+1,…,WDi,H+1)：

上述公式中，⊕代表异或运算；⊗代表与运算加上或运算。

r1，r2和r3是属于［1，NP］的不同整数，NP代表群体大小。

Fac代表用于控制变异程度的比例因子。本文中的Fac是和贝叶斯矩阵相同的0∕1矩阵。比例因子Fac可以由如下公式得到：

上述公式中，U1是属于区间（0，1）的小数，R1是属于区间（0，1）的随机数字，ε1是阈值。sizeof(DAG)是用来计算行数和列数的函数。如果R1小于 ε1，比例因子Fac将生成一个0∕1矩阵。交叉操作

一个子代的向量可以由如下公式得到：

其中，对于 vji,H+1,j∈(1,2,3,…,D)，

上述公式中，CE是相交元素，D代表个体的长度，Rb代表随机小数。

3.2 选择操作

BDENBAL算法在选择典型的候选者方面提供了一种贪婪策略：

上述公式中，BIC函数与式（1）相同，如果子代向量vi,H+1的适应度值大于父代Si,H的值，下一代Si,H+1将会被vi,H+1取代。否则，Si,H+1等于Si,H。

3.3 BDENBAL学习算法

在BDENBAL算法中，变量Tmp被设计用来缓冲交叉操作生成的贝叶斯网络，变量p用来缓冲子代贝叶斯网络。BDENBAL学习算法的具体步骤如下：

算法1：BDENBAL算法1：变量：Tmp，p，Loop_M，Loop; ∕初始化2：Loop_M=最大代数，Loop=0;3：根据当前遗漏值生成变量e;4：while Loop_M＞＝Loop;5：随机选择3个个体Sr1,Sr1,Sr1; ∕个体选择6：根据式（2）生成一个交叉元素Fac 7：当j=1时； ∕变异操作和交叉操作8：根据式（1）进行变异操作；9：根据式（3）进行交叉操作；10：if no Loop in Tmp；11：p{j}=Tmp；12：根据当前子代贝叶斯网络和BIC评分算法，得到BIC评分。∕BIC评分13：根据式（4）进行选择； ∕模型选择14：Loop=Loop+1；15：End while

4 实验结果

本文通过将SEM算法、EM-MCMC算法、AMS-EM算法、BDENBAL算法分别在MATLAB上实现的性能进行比较，评价BDENBAL算法的表现，具体实验参数如下表所示。

本文采用平均对数损失（LOGLOSS）和适应度函数（BIC）作为性能指标。平均对数损失可以通过如下公式计算：

表1 实验参数

1）在100个训练实例上的不同算法的性能比较

为了评价BDENBAL算法的学习能力，我们比较了BDENBAL算法、SEM算法、EM-MCMC算法在4个节点、10个节点，和32个节点条件下的贝叶斯网络。图1～图3显示出BDENBAL算法、SEM算法、EM-MCMC算法的LOGLOSS值随着不同百分比的缺失值（PMV）的变化。PMV在x轴上的对应值为

实验结果显示，所有算法的LOGLOSS值均随着缺失值百分比的提升而呈递减趋势。在所有情况下，BDENBAL算法的LOGLOSS值均大于SEM算法和EM-MCMC算法；同时，BDENBAL算法的递减程度和其他两种算法相比较小。该实验结果证明了和SEM算法、EM-MCMC算法相比，BDENBAL算法拥有更高的性能和预测稳定性。

图1 节点数为4时，LOGLOSS值随不同PMV的变化

图2 节点数为10时，LOGLOSS值随不同PMV的变化

图3 节点数为32时，LOGLOSS值随不同PMV的变化

图4～图6显示出BDENBAL算法在不同代数下的适应度值变化，PMV值分别从0%～40%中选择。实验中由EM算法评估失踪的随机样本部分，估计值会比随机值更加适合。因此，适应度值会随着PMV值的提高而增大。

图4 节点数为4时，BIC评分的变化

2）结果形式发表文献的性能比较

本文同时将BDENBAL算法和AMS-EM算法、EGA算法进行了比较。图7和图8显示出三种算法分别在200、400个训练实例样本上的LOGLOSS值变化。实验结果表明，在两种训练实例样本上，AMS-EM算法的LOGLOSS值是最小的，而BDENBAL算法的LOGLOSS值最大。在缺失值相同的情况下，通过BDENBAL算法得到的贝叶斯网络所反映的概率分布要更加准确。因此，BDENBAL算法拥有更强大的评估能力并能收敛到全局最优解。同时，三种算法的曲线弧度表明，在缺失值的百分比对BDENBAL算法、AMS-EM算法、EGA算法的影响程度中，BDENBAL算法受影响程度最小。

图7 200个训练实例上的性能比较

图8 400个训练实例上的性能比较

5 结语

基于评分的模型选择算法是贝叶斯网络学习最主要的策略之一。本文提出了基于新型二进制自适应差分演化算法（BDENBAL）的贝叶斯网络学习，BDENBAL算法通过交叉和变异算子来实现贝叶斯网络的学习过程中的信息交换。此外，BDENBAL算法根据贝叶斯信息标准（BIC）评分从网络空间中选择贝叶斯网络候选者。为了检验BDENBAL算法的性能，我们在Matlab环境下进行模拟仿真，并将不同情况下BDENBAL算法、AMS-EM算法、EGA算法和SEM算法的性能进行比较和分析，实验结果证明BDENBAL算法拥有更加优良的性能。

［1］D.Mitra，P.Muller，S.Liang，et al.A Bayesian GraphicalModel for ChIP-Seq Data on Histone Modifications［J］.Journal of the American Statistical Association，2013，108（501）：69-80.

［2］ E.Gyftodimos， PA.Flach.Hierarchical Bayesian Networks：An Approrach to Classification and Learning for Structured Data［J］.Springer Berlin Heidelberg，2004，3052：291-300.

［3］D.Heckerma.A tutorial on learning with Bayesian Networks［J］.Studies in Computational Intelligence，2008，156：33-82.

［4］J.Rissanen.Estimation of structure by minimum description length［J］.Circuits System and Signal Processing，1982，156：3-4.

［5］H.Bozdogan.Model selection and Akaike's Information Criterion（AIC）：The general theory and its analytical extensions［J］.Psychometrika，1987，52（3）：345-370.

［6］N.Dojer.Learning Bayesian Networks Does Not Have to Be NP-Hard［J］.International Symposium on MathematicalFoundationsofComputerScience，2006，4162：305-314.

［7］P.Larranaga，M.Poza and Y.Yurramendi.Structure learning of Bayesian networks by genetic algorithms：a performance analysis of control parameters［J］.IEEE Transactions on Pattern Analysisamp;Machine Intelligence，1996，18（9）：912-926.

［8］N.Friedman，G.Dan and M.Goldszmidt.Bayesian Network Classifiers［J］.MachineLearning，1997，29（2-3）：131-163.

［9］L.Dayou，W.Fei and L.Yinan.Research on genetic algorithm based Bayesian Network structure learning［J］.Journal of Computer Research and Development，2001，38（8）：916-922.

［10］C.Riggelsen.Learning parameters of Bayesian Networks from incomplete data via importance sampling［J］.International Journal of Approximate Reasoning，2006，42（1）：69-83.

［11］J.Pena，J.Lozano and P.Larranaga.An improved Bayesian structural EM algorithm for learning Bayesian networks for clustering［J］.Pattern Recognition Letters，2000，21（8）：779-786.

［12］Yu Zhiwen，Li L，Wong H S，et al.Probabilistic cluster structure ensemble［J］.Information Sciences，2014，267（5）：16-34.

［13］Sihem A，Lehocinem B，Miniaih.A Batch Adsorption of Phenol From Industrial Waste Water Using Cereal By-Products As A New Adsrbent［J］，Energy Procedia，2012，18（4）：1135-1144.

Bayesian Network Learning Based on the New Binary System Adaptive Differential Evolution Algorithm

ZHAO Wenqiang ZHAO XiLIU Han
（No.37-1 Changhong Crossroads，Wuchang District，Wuhan 430064）

The Bayesian network is the most popular way to deal with uncertain knowledge and reasoning，and widely used in plenty of research fields.The strategy of Bayesian network learning is to choose the candidate of the optimal network by using the statistical score.The Bayesian network learning is proposed based on the new binary system adaptive differential evolution algorithm（BDENBAL）.BDENBAL uses a self-adaptive 0∕1 matrix as a proportional factor，And through the cross and mutation operator to realize the information exchange in the learning process of Bayesian network.Then，according to the Bayesian Information Criterion（BIC）scoring standard，the candidate is selected from the network space.The experimental results show that the proposed method has excellent performance.

Bayesian network，differential evolution，BIC

TP301.6

10.3969∕j.issn.1672-9730.2017.10.008

Class Number TP301.6

2017年4月6日，

2017年5月27日

赵文强，男，硕士，研究方向：信号与信息处理。赵熙，男，硕士，研究方向：可靠性工程。刘瀚，男，硕士，研究方向：动力工程。