近似图引导的演化贝叶斯网络结构学习算法

贝叶斯网络结构学习是贝叶斯网络推理及应用的基础.搜索高质量的节点序是贝叶斯网络结构学习的一类重要方法.针对在节点序空间中,搜索高质量节点序存在的难以高效、准确评估解的问题,本文提出了一种近似图引导的演化贝叶斯网络结构学习算法.首先,该算法利用互信息构建无向近似图;其次,该算法通过结合节点序和无向近似图构造有向图结构,将其贝叶斯信息准则评分作为节点序的适应度来高效评估节点序,并在演化优化的框架下,使用提出的基于Kendall Tau Distance的交叉算子和基于逆度的变异算子搜索最优节点序;最后,将搜索到的最优节点序输入K2算法得到其对应的贝叶斯网络结构.在4种不同规模网络上的实验结果表明,该算法在收敛时间和准确度之间取得了较好的平衡,其评分相较于对比算法中的次优解分别提升了10.91%、12.28%、53.96%、10.87%.     

基于节点排序的贝叶斯网络结构学习算法

针对K2算法学习贝叶斯网络结构时需要确定节点顺序的问题,提出一种混合贝叶斯网络结构学习算法。在给定数据集的情况下,利用MMPC算法获得网络的初始结构图,应用广度优先搜索的方式对此初始结构图进行搜索,从该图中入度为0的节点出发,按层次依次访问图中的邻接点,获得优化的节点顺序。将该节点顺序作为K2算法的初始节点顺序,再利用K2算法对空间进行搜索,找到全局最优解。实验结果表明,与K2算法和限制性粒子群算法相比,该算法在相同的样本数据集下产生多边、少边和反边情况的概率更低,并且可学习到更准确的贝叶斯网络结构,收敛速度快、求解精度高。     

基于因果效应的贝叶斯网络结构学习方法

从数据中学习贝叶斯网络结构是一个NP-hard问题,提高网络结构学习算法精度是研究的重难点。基于Judea Pearl因果理论,提出了一种贝叶斯网络结构学习方法,提升了现有算法的准确率。利用改进的Pearl因果效应和BDe评分,学习网络节点优先次序,利用K2算法学习初始网络,并通过BDe评分反向调节、互信息和BDe评分删除边以修正学习结果。实验在贝叶斯网络标准数据集ASIA、ALARM上进行,在样本量为2000~20000的20组实验中,学习准确率较MMHC算法平均提升16%,准确率标准差较MMHC算法平均缩小17%。实验表明,基于因果效应的方法较MMHC算法有更好地性能。     

基于最大信息系数的贝叶斯网络结构学习算法

为了得到正确的节点次序,构造接近最优的贝叶斯网络结构,利用最大信息系数与条件独立性测试相结合的方法,提出了一种新的贝叶斯网络结构学习算法（MICVO）。该算法利用最大信息系数衡量变量之间的依赖关系,生成初始的无向图,引入惩罚因子δ减少图中冗余边的数量,并将这个无向图分解成多个子结构,确定图中边的方向,最后生成正确的节点次序作为K2算法的输入学习网络结构。在两个基准网络Asia和Alarm中进行实验验证,结果表明基于最大信息系数的贝叶斯网络结构学习算法可以得到接近最优的节点次序,学习到的网络结构与数据的拟合程度更好,分类准确性更高。     

基于MWST-CS-K2算法的贝叶斯网络结构学习

针对K2算法依赖最大父节点数和节点顺序的不足,提出了一种改进的贝叶斯网络结构学习算法（MWST-CS-K2）。该算法先通过构造最大支撑树（MWST）得到最大父节点数;再利用变量间的关联度和更新系数对加边、减边和反转边进行规则设定,通过改进的布谷鸟算法对鸟巢位置进行寻优,应用广度优先搜索策略搜索遍历得到节点顺序;最后将最大父节点数和节点顺序作为K2算法的输入搜索得到最终网络。实验表明,所提出的MWST-CS-K2算法在标准的ASIA、SACHS和CHILD网络数据测试中的平均正确边比率分别达到了97.3%、87.7%和95.6%,学习效果优于其他对比算法,获得的网络结构和标准的网络结构最为相似。     

贝叶斯网络结构学习的简化贪婪算法

基于数据的贝叶斯网络结构学习是一个NP难题.基于条件约束和评分搜索相结合的方法是贝叶斯网络结构学习的一个热点.基于互信息理论提出一种最大支撑树(MWST)机制,并基于最大支撑树结合贪婪搜索的思想提出一种简化贪婪算法.简化贪婪算法不依赖先验知识,完全基于数据集.首先,通过计算互信息建立目标网络的最大支撑树;然后,在最大支撑树的基础上学习初始网络结构,最后,利用简化搜索机制对初始结构进一步优化,最终完成贝叶斯网络的结构学习.数据仿真实验证明,简化贪婪算法不仅具有很高的精度而且具有高效率.     

基于选择性集成遗传算法的BNC结构学习

为克服IQ算法在处理贝叶斯网络分类器（Bayesian Network Classifier,BNC）结构学习中要求先指定适合节点次序的缺点,提出GA-K2算法,将基于选择性集成的整数编码遗传算法引入到K2算法中,使之能得到最佳节点次序并且网络结构收敛到全局最优．构建贝叶斯网络分类器进行分类,实验结果表明GA-K2算法优于随意指定节点顺序的IQ算法．     

基于模型融合的分布式贝叶斯网络学习算法*

提出了一个从同构数据集中学习贝叶斯网络结构的分布式算法。该算法首先使用搜索评分的方法学习每个局部贝叶斯网络结构,然后取节点对互信息变量和条件互信息变量的数学期望作为全局学习的评价标准,融合所有局部结构得到全局结构。由于只使用了数据集中变量间的互信息和条件互信息,没有直接获取局部个体数据信息,从而可以实现有效的隐私保护。该算法在Alarm数据集上进行测试,边的误差率小于6%,运行时间比集中学习的算法的运行时间短,验证了算法的有效性。     

多维贝叶斯网络分类器加速学习算法

作为概率图模型,无限制多维贝叶斯网络分类器(GMBNC)是贝叶斯网络(BN)应用在多维分类应用时的精简模型,只包含对预测有效的局部结构.为了获得GMBNC,传统方法是先学习全局BN;为了避免全局搜索,提出了仅执行局部搜索的结构学习算法DOS-GMBNC.该算法继承了之前提出的IPC-GMBNC算法的主体框架,基于进一步挖掘的结构拓扑信息来动态调整搜索次序,以避免执行无效用的计算.实验研究验证了DOS-GMBNC算法的效果和效率:(1)该算法输出的网络质量与IPC-GMBNC一致,优于经典的PC算法;(2)在一个包含100个节点的问题中,该算法相对于PC和IPC-GMBNC算法分别节省了近89％和45％的计算量.     

基于差分进化策略的贝叶斯网络结构学习方法

针对目前主流的利用启发式搜索算法进行贝叶斯网络结构学习时,初始种群难以确定且容易陷入局部最优的问题,提出了基于部分互信息和改进差分进化算法相结合的混合算法.算法首先利用节点之间的部分互信息为依据构建初始种群,再将动态因子引入差分进化算法平衡了算法的全局寻优和局部搜索能力,最后对贝叶斯网络结构进行寻优.在两个标准网络Asia和Car网络中进行仿真,并与遗传算法和爬山算法进行对比,仿真结果表明算法在冗余边、缺失边、反向边以及算法的学习性能方面均有不同程度的提升,算法能够得到较好的贝叶斯网络结构,并有更高的数据拟合度.     

Some node ordering methods for the K2 algorithm

Inferring Bayesian network structure from data is a challenging issue, and many researchers have been working on this problem. The K2 is a well‐known order‐dependent algorithm to learn Bayesian network. The result of the algorithm is not robust since it achieves different network structure if node orderings are permuted. Consequently, choosing suitable sequential node ordering for the input of the K2 algorithm is a challenging task. In this work, some deterministic methods for selecting a suitable sequential node ordering are introduced. The effectiveness of these methods benchmarked through the Asia, Alarm, Car, and Insurance networks. The results indicate that the methods based on the concept of mutual information and entropy are suitable for finding a sequential node ordering and considerably improves the precision of network inference. The source code and selected data sets are available on http://profiles.bs.ipm.ir/softwares/ordering/ .     

基于节点块序列约束的局部贝叶斯网络结构搜索算法

针对K2算法过度依赖节点序和节点序搜索算法评价节点序效率较低的问题, 提出一种基于节点块序列约束的局部贝叶斯网络结构搜索算法, 该算法首先通过评分定向构建定向支撑树结构, 在此基础上构建节点块序列, 然后利用节点块序列确定每个节点的潜在父节点集, 通过搜索每个节点的父节点集构建网络结构, 最后对该结构进行非法结构修正得到最优贝叶斯网络结构.利用标准网络将算法与几种不同类型的改进算法进行对比分析, 验证该算法的有效性.     

基于互信息的贝叶斯网络结构学习算法

结构学习是贝叶斯网络的重要分支之一,而由数据学习贝叶斯网络是NP-完全问题,提出了一个由数据学习贝叶斯网络的改进算法。该算法基于互信息知识构造初始无向图,并通过条件独立测试对无向边添加方向;同时提出了一个针对4节点环和5节点环的局部优化方法来构造初始框架,最后利用贪婪搜索算法得到最优网络结构。数值实验结果表明,改进的算法无论是在BIC评分值,还是在结构的误差上都有一定的改善,并且在迭代次数、运行时间上均有明显降低,能较快地确定出与数据匹配程度最高的网络结构。     

INVESTIGATION OF THE K2 ALGORITHM IN LEARNING BAYESIAN NETWORK CLASSIFIERS

We experimentally study the K2 algorithm in learning a Bayesian network (BN) classifier for image detection of cytogenetic abnormalities. Starting from an initial BN structure, the K2 algorithm searches the BN structure space and selects the structure maximizing the K2 metric. To improve the accuracy of the K2-based BN classifier, we investigate the K2 algorithm initial ordering, search procedure, and metric. We find that BN structures learned using random initial orderings, orderings based on expert knowledge, or a scatter criterion are comparable and lead to similar classification accuracies. Replacing the K2 search with hill-climbing search improves the accuracy as does the inclusion of hidden nodes in the BN structure. Also, we demonstrate that though the maximization of the K2 metric solicits structures providing improved inference, these structures contribute to only limited classification accuracy.     

一种新颖的基因调控网络结构学习方法

基于贝叶斯模型的结构学习是NP完全问题。给出了一种新颖的基于粒子群优化算法(PSO)的无序条件下的结构学习方法。迭代中,新算法用粒子表示网络结构,根据PSO群体规则进行更新,同时利用互信息进行修正,将所得到的最佳网络结构作为K2算法的先验知识。实验结果表明,新算法可以在无序的条件下,取得稳定的贝叶斯分数值。同时,在与K2算法和BN-PSO算法的比较中,新算法取得了更优异的网络结构和更快的收敛速度。     

Improved algorithm based on mutual information for learning Bayesian network structures in the space of equivalence classes

As is well known, greedy algorithm is usually used as local optimization method in many heuristic algorithms such as ant colony optimization, taboo search, and genetic algorithms, and it is significant to increase the convergence speed and learning accuracy of greedy search in the space of equivalence classes of Bayesian network structures. An improved algorithm, I-GREEDY-E is presented based on mutual information and conditional independence tests to firstly make a draft about the real network, and then greedily explore the optimal structure in the space of equivalence classes starting from the draft. Numerical experiments show that both the BIC score and structure error have some improvement, and the number of iterations and running time are greatly reduced. Therefore the structure with highest degree of data matching can be relatively faster determined by the improved algorithm.     

基于双尺度约束模型的BN结构自适应学习算法

在无先验信息的情况下, 贝叶斯网络(Bayesian network, BN)结构搜索空间的规模随节点数目增加呈指数级增长, 造成BN结构学习难度急剧增加. 针对该问题, 提出基于双尺度约束模型的BN结构自适应学习算法. 该算法利用最大互信息和条件独立性测试构建大尺度约束模型, 完成BN结构搜索空间的初始化. 在此基础上设计改进遗传算法, 在结构迭代优化过程中引入小尺度约束模型, 实现结构搜索空间小尺度动态缩放. 同时, 在改进遗传算法中构建变异概率自适应调节函数, 以降低结构学习过程陷入局部最优解的概率. 仿真结果表明, 提出的基于双尺度约束模型的BN结构自适应学习算法能够在无先验信息的情况下保证BN结构学习的精度和迭代寻优的收敛速度.     

Enhancing multi-label classification by modeling dependencies among labels

In this paper, we propose a novel framework for multi-label classification, which directly models the dependencies among labels using a Bayesian network. Each node of the Bayesian network represents a label, and the links and conditional probabilities capture the probabilistic dependencies among multiple labels. We employ our Bayesian network structure learning method, which guarantees to find the global optimum structure, independent of the initial structure. After structure learning, maximum likelihood estimation is used to learn the conditional probabilities among nodes. Any current multi-label classifier can be employed to obtain the measurements of labels. Then, using the learned Bayesian network, the true labels are inferred by combining the relationship among labels with the labels? estimates obtained from a current multi-labeling method. We further extend the proposed multi-label classification method to deal with incomplete label assignments. Structural Expectation-Maximization algorithm is adopted for both structure and parameter learning. Experimental results on two benchmark multi-label databases show that our approach can effectively capture the co-occurrent and the mutual exclusive relation among labels. The relation modeled by our approach is more flexible than the pairwise or fixed subset labels captured by current multi-label learning methods. Thus, our approach improves the performance over current multi-label classifiers. Furthermore, our approach demonstrates its robustness to incomplete multi-label classification.     

基于密度核估计的贝叶斯网络结构学习算法

贝叶斯网络结构学习算法主要包括爬山法和K2算法等,但这些方法均要求面向大样本数据集。针对实际问题中样本集规模小的特点,通过引入概率密度核估计方法以实现对原始样本集的拓展,利用K2算法进行贝叶斯网络结构学习。通过优化选择核函数和窗宽,基于密度核估计方法实现了样本集的有效扩展;同时基于互信息度进行变量顺序的确认,进而建立了小规模样本集的贝叶斯结构学习算法。仿真结果验证了新学习算法的有效性和实用性。