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

《多维贝叶斯网络分类器加速学习算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第42卷第6期计算机科学Vo1．42No．62015年6月ComouterScienceJune2015多维贝叶斯网络分类器加速学习算法傅顺开李志强SeinMinn(华侨大学计算机科学与技术学院厦门361021)摘要作为概率图模型，无限制多维贝叶斯网络分类器(GMBNC)是贝叶斯网络(BN)应用在多维分类应用时的精简模型，只包含对预测有效的局部结构。为了获得GMBNC，传统方法是先学习全局BN；为了避免全局搜索，提出了仅执行局部搜索的结构学习算法DOS-GMBNC。该算法继承了之前提出的IPC-GMBN

2、C算法的主体框架，基于进一步挖掘的结构拓扑信息来动态调整搜索次序，以避免执行无效用的计算。实验研究验证了DOS-GMBNC算法的效果和效率：(1)该算法输出的网络质量与IPC-GMBNC一致，优于经典的PC算法；(2)在一个包含100个节点的问题中，该算法相对于PC和IPC_GMBNC算法分别节省了近89和45的计算量。关键词多维分类，贝叶斯网络，多维贝叶斯网络分类器，马尔科夫毯中图法分类号TP181，TP391文献标识码ADOI10．11896／j．issn．1002—137X．2015．6．055A

3、cceleratedStructureLearningforGeneralMulti—dimensionalBayesianNetworkClassifierFUShun-kaiLIZhi-qiangSeinMinn(CollegeofComputerScienceandTechnology，HuaqiaoUniversity，Xiamen361021，China)AbstractGenera1multi—dimensionalBayesiannetworkclassifier(GMBNC)iSonek

4、indofBayesiannetwork(BN)tai—loredfortheapplicationofmulti-dimensionalclassification，henceitcontainsonlyfeaturesnecessaryfortheprediction．Toavoidglobalsearch。anovelalgorithmcalledYX)S-GMBNCwasproposed．ItinheritstheframeworkofexistingIPc_GMBNC，conductsadyn

5、amicorderofsearchbymakinguseoftheunderlyingtopologyinformation．Experimentalstu-diesindicatetheeffectivenessandefficiencyofDOGMBNCItoutputsnetworkswithequalqualityasPCandiPC-GMBNCalgorithms，anditbringsconsiderablereductionofcomputationcomplexity，e．g．about

6、89and45lessthanPCandIPC-GM_BNCrespectivelyona100一nodenetworkproblem．KeywordsMulti—dimensionalclassification，Bayesiannetwork，Multi—dimensionalBayesiannetworkclassifier，Markovblanket得了惊人的成功】5。]。1引言BN被vanderGaag和deWaa1等在2006年应用到多维贝叶斯网络(Bayesiannetwork，BN)(见

7、图1(a))是一种分类问题[8]，相应的模型取名为多维贝叶斯网分类器(Multi—经典概率图模型，能紧凑和直观地表示变量间的相互关系，并dimensionalBayesiannetworkclassifier，MBNC)(见图1(c))。提供强大的推理能力。BN在诸多领域获得了应用，例如无为了避免高昂的学习代价，MBNC被定义为两偶图(bi-partite人机决策l】和反应堆补水系统诊断_2]。graph)，即可分解为3个独立的子图：类子图(Classsub-应用BN进行建模和推理，需要先获得其模型，常

8、见的有graph)、特征子图(Featuresub-graph)以及连接它们的桥接子两种途径：(1)由领域专家利用个人专业知识经验进行人工处图(Bridgesub-graph)。根据对类和特征子图的不同假设，理，一般限于小规模问题；(2)基于专门的机器学习算法从历MBNC又可进一步区分为(empty)一(empty>、(polytree>一史样本数据集自动恢复模型。途径(2)是目前的主流方式_3]，(polytree)[、(tree)一(t