一种基于两步搜索策略的K2改进算法.pdf

h t t p:/ww wj s j k x c o mD O I:/j s j k x 到稿日期:返修日期:基金项目:新疆 维 吾 尔 自 治 区 自 然 科 学 基 金(D C );伊 犁 师 范 大 学 博 士 科 研 启 动 项 目(Y S B S );学 实 高 层 次 人 才 岗 位(Y S X S QN )T h i sw o r kw a ss u p p o r t e db yt h eN a t u r a lS c i e n c eF o u n d a t i o no fX i n j i a n gU y g u rA u t o n o m o u sR e g i o n,C h i n a(D C ),D o c t o r a lR e s e a r c hS t a r t u pP r o j e c to fY i l iN o r m a lU n i v e r s i t y(Y S B S )a n dP r o m i s i n gS c h o l a ro fA c a d e m i c I n t e g r i t y(Y S X S QN )通信作者:綦小龙(q x l_ s i n a c o m)一种基于两步搜索策略的K 改进算法徐苗王慧玲,梁义綦小龙高阳伊犁师范大学网络安全与信息技术学院新疆 伊宁 南京大学计算机科学与技术系计算机软件国家重点实验室南京 (x m_ c o m)摘要贝叶斯网络由于其强大的不确定性推理能力和因果可表示性越来越受到研究者的关注.从数据中学习一个贝叶斯网络结构被称为N P h a r d问题.其中,针对K 算法强依赖于变量拓扑序的问题,提出了一种组合变量邻居集和v 结构信息的K 改进学习方法T S K(T w o S t e pS e a r c hS t r a t e g yo fK).该方法有效减小了序空间搜索规模,同时避免了过早陷入局部最优.具体而言,该方法在约束算法定向规则的启示下,借助识别的v 结构和邻居集信息可靠调整汇点的邻居在序中的位置;其次,在贝网基本组成结构的启发下,借助变量邻居集信息,通过执行顺连、分连、汇连个基本结构的搜索,准确修正父节点与子节点的序位置,获得最优序列.实验结果表明,在A s i a和A l a r m网络数据集上,与对比方法相比,所提算法的准确率得到显著提升,可以获得更准确的网络结构.关键词:K 算法;P C算法;v 结构;邻居集;结构学习中图法分类号T P I m p r o v e dK A l g o r i t h mB a s e do nT w o s t e pS e a r c hS t r a t e g yX U M i a o,WAN G H u i l i n g,L I AN GY i,Q IX i a o l o n ga n dGA OY a n gS c h o o l o fC y b e r s e c u r i t y&I n f o r m a t i o nT e c h n o l o g y,Y i l iN o r m a lU n i v e r s i t y,Y i n i n g,X i n j i a n g ,C h i n aS t a t eK e yL a b o r a t o r yf o rN o v e lS o f t w a r eT e c h n o l o g y,D e p a r t m e n to fC o m p u t e rS c i e n c ea n dT e c h n o l o g y,N a n j i n gU n i v e r s i t y,N a n j i n g ,C h i n aA b s t r a c t B a y e s i a nn e t w o r kr e c e i v i n g i n c r e a s i n ga t t e n t i o n f r o mr e s e a r c h e r sb e c a u s eo f i t s s t r o n gu n c e r t a i n t y r e a s o n i n ga b i l i t ya n dc a u s a l r e p r e s e n t a b i l i t y L e a r n i n gaB a y e s i a nn e t w o r ks t r u c t u r ef r o md a t ai sa nN P h a r dp r o b l e m Am o n gt h e m,f o rt h ep r o b l e mt h a t t h eK a l g o r i t h ms t r o n g l yd e p e n d so n t h e t o p o l o g i c a l o r d e r o f v a r i a b l e s,a n i m p r o v e dK l e a r n i n gm e t h o dT S K i sp r o p o s e d,w h i c hc o m b i n e sv a r i a b l en e i g h b o r s e t sa n dv s t r u c t u r e i n f o r m a t i o n T h ep r o p o s e dm e t h o de f f e c t i v e l yr e d u c e st h es e a r c hs c a l e i nt h eo r d e rs p a c ea n da v o i d sp r e m a t u r e l yf a l l i n g i n t o l o c a l o p t i m u m S p e c i f i c a l l y,i n s p i r e db yt h eo r i e n t a t i o nr u l e so f t h ec o n s t r a i n ta l g o r i t h m,t h em e t h o dr e l i a b l ya d j u s t s t h e i n o r d e rp o s i t i o no f t h en e i g h b o r so f t h e s i n kw i t ht h eh e l po f t h e i d e n t i f i e dv s t r u c t u r ea n dn e i g h b o r s e t i n f o r m a t i o n S e c o n d l y,i n s p i r e db yt h eb a s i cs t r u c t u r eo f t h es h e l l n e t,w i t ht h eh e l po f t h ev a r i a b l en e i g h b o r s e ti n f o r m a t i o n,t h eo p t i m a l s e q u e n c e i so b t a i n e db yp e r f o r m i n gt h es e a r c ho f t h e t h r e eb a s i cs t r u c t u r e so f s h u n c o n n e c t i o n,s u b c o n n e c t i o n,a n dc o n f l u e n c e c o n n e c t i o nt oa c c u r a t e l yc o r r e c t t h eo r d e rp o s i t i o n so fp a r e n tn o d e sa n dc h i l dn o d e s E x p e r i m e n t a l r e s u l t ss h o wt h a t t h ea c c u r a c yo f t h ep r o p o s e da l g o r i t h mi ss i g n i f i c a n t l yi m p r o v e dc o m p a r e dw i t ht h ec o m p a r i s o nm e t h o d so nt h eA s i aa n dA l a r mn e t w o r kd a t a s e t s A m o r ea c c u r a t en e t w o r ks t r u c t u r ec a nb e l e a r n e d K e y w o r d s K a l g o r i t h m,P Ca l g o r i t h m,v s t r u c t u r e,N e i g h b o r s e t,S t r u c t u r e l e a r n i n g引言贝叶斯网络是由概率推理和图论理论结合而成的图形化模型,通过条件概率表和有向无圈图定量地描述了变量之间的独立关系和依赖程度,在处理不确定性知识和数据分析方面具备独特的优势,是人工智能领域的有力工具.由于贝叶斯网络具有坚实的数学基础、灵巧的学习体系和直观形象的语义表述等特点,引起了国内外众多研究学者的极大兴趣.近几十年来,贝叶斯网络成为了研究热点,并在医疗诊断、机器视觉、因果推断、工业控制、学习预测和数据挖掘等领域 得到了广泛应用.贝叶斯网络最早主要是由领域专家的先验知识进行构建,在网络规模较小时可行,但是面对较大网络规模时,变量间的因果关系变得十分复杂,这时再依靠领域专家来构建贝叶斯网络会非常困难且容易出错.如何从已知数据中学习贝叶斯网络已成为现阶段的研究方向,这是一个N P难问题.目前,结构学习算法主要分为:基于约束的学习算法、基于评分搜索的学习算法和混合学习算法.约束的学习算法通过信息论进行条件的独立性检测,判断变量间关系从而确定网络结构,例如T P D A算法和S G S算法等,它们具备严格的理论基础,学习效率较高,但依赖于独立检测的准确度,在多维数据或者数据不足时模型学习精度不可靠.基于评分搜索的学习算法通过评分函数对网络模型结构的优劣进行评判,利用搜索策略寻找最佳评分的模型结构,例如爬山法和粒子群算法 等,它们可以学习到较精确的结构模型,但在复杂结构场景下搜索空间过大,导致搜索效率大幅降低.混合学习算法将上述两种算法结合,首先利用基于约束的学习算法降低网络空间的搜索规模,然后执 行 评 分搜 索 的 学 习 算 法 寻 找 最 佳 模 型 结 构.例 如MMA C O算法,其步骤分为两步:先通过MMP C算法获得基本模型,再使用蚁群算法确定基本模型的边和方向.混合学习算法已成为现阶段受欢迎的研究方向之一.基于评分搜索的K 算法 将假设的随机变量顺序作为输入,利用变量拓扑序列约束搜索过程,在有效减小搜索空间的同时还能降低非法结构的概率,整体表现优于大多数经典算法.因此,K 算法的效率很大程度上依赖于变量顺序,不准确的变量顺序无法学习到正确的结构模型.如何获得准确的变量顺序是使K 算法更加实用的主要挑战,本文提出的充分利用v 结构和邻居集信息的混合学习算法为此提供了新的思路.本文的主要贡献如下:)提出了基于v 结构与汇点邻居集信息的序搜索策略.在学习过程中,使用该信息,无需执行评分搜索计算,直接对初始序列进行调整,实现部分节点定序,在减少计算量的同时也合理约减了序搜索空间.)受到贝叶斯网络结构的个基本组成成分启发,提出了基于邻居集置换的序搜索策略.对未定序节点进行种置换搜索,可靠地从给定的数据中学习出高质量顺序,有效避免了过早陷入局部最优,实现全局搜索.)在标准数据集上对所提算法T S K 进行实验对比分析,以评估其学习性能.实验结果表明了T S K 算法的有效性.相关工作近年来,针对K 算法需要准确变量拓扑序的问题,研究者们相继给出了很多解决方案.文献 提出了基于MW S T K 的算法,通过MWS T算法构建有向生成树,将生成的排序作为K 算法的先验拓扑序列,由于MWS T算法的定向精度较低,该算法在构建基准网络模型时结果不理想.文献 提出了基于因果效应的算法,该算法通过改进版因果效应法和B D e评分获得节点优先次序,利用删除边操作和反向调节修正结果,提升了网络结构学习性能,但是面对大型网络时易陷入局部最优.文献 提出了K A C O算法,通过种群中的初始个体随机创建节点顺序,由蚁群算法进行优化学习得到最佳序列,在蚁群算法过程中,运行K 搜索算法计算各排序的适应度,寻找最优排序并直接获得相对应的网络结构,该算法存在时间复杂度较高的问题.文献 提出了I TN O K P C算法,利用信息理论测试节点间的依赖关系,通过确定父子节点关系对生成的矩阵进行验证,获得最终结构模型,该算法更适用于中小规模网络.文献 提出了优先级排序算法,通过MCMC算法 学习拟合观测值的结构模型,利用定义的节点排序评分函数获得变量先验序,该算法减少了穷举所需花费的较长时间,但受到MCMC算法的约束.文献 提出了重构先验信息的算法,将MCMC算法与模拟退火算法相结合,根据邻域查找规则配合专家知识和数据修补等方法获得最佳网络结构,该算法在小数据集上表现较好,但是需要具备完整且准确的领域知识,在很多场景下难以实现.文献 提出了P S O K 算法,利用粒子群算法更新变量拓扑序,通过K 算法构建贝叶斯网络,使用A I C评分函数进行判定取得对应拓扑序列的适应度函数并进行种群迭代,该算法的运行速度较慢,学习效率较低.文献 提出了基于强连通的改进算法,利用每个变量的最佳父节点集来构建强连通图,从强连通分量中推断变量的顺序,该算法降低了时间复杂度,但最佳父集的准确性对算法结果影响较大.算法的构建T S K 算法分为步:首先利用改进版因果效应法学习节点优先排序,将其作为初始顺序;然后通过P C算法获得v 结构和邻居集,使用v 结构与汇点邻居集信息对初始序列进行调整,修正不符合父子节点关系的节点顺序;接着利用邻居集置换策略,对邻居节点进行置换搜索,进一步修正节点顺序获得最佳节点序;最后利用K 算法学习高质量贝叶斯网络结构模型.通过v 结构和邻居集信息的配合使用,能够快速而有效地检测出错误节点顺序并做出修正.节点优先排序利用改进版因果效应法学习节点优先排序,可以定性地表达节点之间的父子关系.对于二值数据网络和多值数据网络,分别从两种方法开始,得到所有节点的优先度并降序排列,获得节点优先排序.二值数据网络P e a r l提出的因果理论仅考虑X和Y在Y处的因果效应,改进版因果效应法 在此基础上进行了拓展,对于任意两个节点Xi和Xj,考虑XiXj在Xj和Xj两处的因果效应,因果效应C EXiXj计算式如下:C o m p u t e rS c i e n c e计算机科学V o l ,N o ,S e p C EXiXjN(Xj)NP(Xj|Xi)P(Xj|Xi)N(Xj)NP(Xj|Xi)P(Xj|Xi)()其中,N表示总样本数目,N(Xj)表示Xj的样本数目,N(Xj)表示Xj的样本数目.算法从一个节点开始,计算任意两个节点之间的因果效应,直 至 遍 历 网 络 中 的 所 有 节 点.对 于Xi和Xj,如 果C EXiXjC EXjXi,那么将Xi的优先度加;如果C EXiXjC EXjXi,那么将Xj的优先度加.对最终的节点优先度进行降序排列,获得节点优先排序,将其作为初始序列.多值数据网络对于多值数据网络,搜索每个节点最多的两个状态值,使用相对应的值计算任意两个节点的因果效应.对于任意两个节点Xi和Xj,若Xi的最多状态值是a与b,Xj的最多状态值是c与d,则需要考虑XiXj在Xjc和Xjd两处的因果效应,因果效应C EXiXj计算式如下:C EXiXjN(Xjc)NP(Xjc|Xia)P(Xjc|Xib)N(Xjd)NP(Xjd|Xia)P(Xjd|Xib)()其中,N(Xjc)表示Xjc的样 本 数目,N(Xjd)表 示Xjd的样本数目.多值数据网络方法与二值数据网络方法的规则相同,依次计算每两个节点之间的因果效应,获得初始序列.基于P C算法的节点序搜索策略 P C算法P C算法是S p i r t e s等提出的基于约束的学习算法,是对S G S算法的进一步改良.P C算法不需要完全计算指数级别下的条件独立性,它从空图开始,确定节点间的依赖关系得到无向图,然后再确定节点间的依赖方向,把无向图学习变为部分有向无圈图.其中,变量的邻居集决定了变量对的条件集,算法在遍历过程中会动态更新变量的邻居集.文献 中的定理 阐明了P C算法可以输出体现有向无圈图G的C P D AG,即P C算法可以输出准确的v 结构.该算法利用P C算法学习的v 结构和邻居集对最佳变量拓扑序进行搜索,达到减小序列搜索空间规模、准确判定序列正确性的目的.节点序搜索策略改进版因果效应法删除了“d o 操作”,所以获得的初始序列是一个近似正确的序列,仍可能存在不正确的父子序列顺序.考虑到之前的算法,如贪婪爬山法,在调整节点序时,节点的移动是随机的,没有结合额外的信息,学习效果不理想.为了提高序列的准确度,学习最优网络结构,本文配合使用两种节点序搜索策略:基于v 结构与汇点邻居集的序搜索策略和基于邻居集置换的序搜索策略.情况v 结构信息可用时,采用基于v 结构与汇点邻居集的序搜索策略.定义(邻居)如果节点Xi和节点Xj之间存在一条边,则节点Xi是节点Xj的邻居,反之亦然,记作A d j(Xi)Xj.对于三元组Xi,Xj,Xk,如果存在XiXj,且XkXj,即Xi与Xk都存在指向Xj的有向边,构成XiXjXk的形式,就称其为v 结构.如图所示,三元组Xi,Xj,Xk 构成了v 结构,其中Xi和Xk作为父节点,Xj作为子节点,v 结构清晰而直观地展现了个节点之间的父子关系.在节点序的排列中,父节点必须排在子节点之前,所以根据v 结构的信息可以确定,节点Xi和节点Xk的序列位置需要排在节点Xj之前.图v 结构F i g v s t r u c t u r e基于v 结构的特性,将学习到的相关信息作用于初始序列的调整,对可能存在的不正确排序进行更新.具体而言,对于任意个节点构成的v 结构XiXjXk,搜索Xi,Xj和Xk在节点序中的位置,检测Xi和Xk是否排在Xj之前,若未满足,则将Xi和Xk移动到Xj之前,以满足父节点在前、子节点在后的准则;接着根据节点Xj的邻居信息,直接将位于Xj前方的其余邻居节点置于Xj后方.示例如图所示,节点优先序列为(X,X,X,X,X),邻居信息为A d j(X)X,X,X,v 结构信息为XXX,根据调整策略得到新节点序列(X,X,X,X,X).图基于v 结构与汇点邻居集的序搜索策略F i g S e a r c hs t r a t e g yf o rv s t r u c t u r ea n ds i n kn e i g h b o rs e t基于v 结构与汇点邻居集的序调整过程中,存在两种情况:)节 点 入度 为时,P C算 法 会获 得一 个v 结 构 信 息XiXjXk.基于v 结构信息和约束算法的定向准则,Xj不存在第三个父节点.因此,节点Xj的其余邻居节点可以直接确定为它的子节点,换言之,这些邻居节点应该在节点Xj之后,如图(a)所示.)节点入度大于时,P C算法会获得关于节点Xj的多个v 结构,如图(b)所示.对于每一个v 结构,依然根据v 结构信息和约束算法的定向准则,调整Xj其余邻居节点的序,如图(b)所示.节点Xj其余邻居集的计算式如下:RA d j(Xj)A d j(Xj)VA d j(Xj)()其中,VA d j(Xj)表示由以节点Xj为汇点的v 结构中节点Xj的父集所构成的邻居集.徐苗,等:一种基于两步搜索策略的K 改进算法图基于v 结构与汇点邻居集的序调整情况F i g O r d e ra d j u s t m e n to fv s t r u c t u r ea n ds i n kn e i g h b o rs e t命题基于v 结构与汇点邻居集的序搜索策略是可靠的.证明:不失一般性,假设通过P C算法的学习得到v 结构信息XiXjXk,XiXjXl,XkXjXl与Xj的邻居信息A d j(Xj)Xi,Xk,Xl,Xm.如果定向XmXj,那么Xi和Xm、Xk和Xm、Xl和Xm的分隔集中一定不包含Xj,这与P C算法获取的Xi和Xm、Xk和Xm、Xl和Xm的分隔集矛盾,即Xjs e pXi,Xm,Xjs e pXk,Xm,Xjs e pXl,Xm.利用v 结构与汇点邻居集信息调整得到部分最佳节点序,由于部分无v 结构信息的节点未被检测,仍存在错误节点序未被修正.受到组成贝叶斯网络结构的个基本成分顺连、分连、汇连的启发,进一步提出了基于邻居集置换的序搜索策略.情况无v 结构信息可用时,采用基于邻居集置换的序搜索策略.定义(分连、顺连、汇连)节点Xi与节点Xk通过节点Xj相连,分为种情况:)对于分连XiXjXk,若变量Xj已知,则信息传递被阻塞,此时Xi与Xk相互独立;若变量Xj未知,Xi和Xk之间能进行信息传递,此时Xi与Xk相互依赖.)对于顺连XiXjXk,与分连情况相似,若变量Xj已知,则信息传递被阻塞,此时Xi与Xk相互独立;若变量Xj未知,Xi和Xk之间能进行信息传递,此时Xi与Xk相 互依赖.)对于汇连XiXjXk,若变量Xj未知,则信息传递被阻塞,此时Xi与Xk相互独立;若变量Xj已知,Xi和Xk之间能进行信息传递,此时Xi与Xk相互依赖.在调整节点位置时,该策略有效结合当前节点的邻居集,通过执行顺连、分连、汇连等基本结构的搜索,修正错误父节点与子节点的序位置,提高了学习效率和序质量.具体 而 言,对 于 未 确 定 位 置 的 节 点Xi,如 果 存 在A d j(Xi)Xj,Xk,那么根据定义,通过调整Xi关于邻居节点Xj和Xk的位置来搜索节点序列.)节点Xi位于其邻居节点Xj和Xk前方,作为节点Xj和Xk的父节点.)节点Xi位于其邻居节点Xj的后方、邻居节点Xk的前方,作为节点Xj的子节点、节点Xk的父节点.)节点Xi位于其邻居节点Xj和Xk后方,作为节点Xj和Xk的子节点.执行示例如图所示,节点优先序列为(X,X,X,X,X),邻居信息为A d j(X)X,X,利用邻居集置换的序搜索策略,生成节点X与其邻居节点X和X的分连、顺连和汇连种形式,即新序列(X,X,X,X,X),(X,X,X,X,X),(X,X,X,X,X),采用B D评分函数对个新序列对进行判定,选择最佳序列.在样本量较少或者节点依赖关系较弱时,可能存在某个节点没有邻居的情况,这时,对于无邻居的节点Xi,根据B D评分判定,将其放在序列首位或者保持不动.判定过程中,更新评分最优的序列,直至将所有节点的邻居集遍历完成,得到最终的优质节点序.T S K 算法如算法所示.算法T S K 算法输入:节点集N,数据集D,父节点上限数u,v 结构集v,邻居集b输出:一个贝叶斯网络 f o r i n f o r j n 按照式()或式()计算每两条边的因果效应;i fC EXi XjC EXj XiC o m p u t e rS c i e n c e计算机科学V o l ,N o ,S e p dXidXi;e l s edXjdXj e n di f;e n df o r;e n df o r;将每个节点按照优先度降序排序,获得初始序列o r d e r;w h i l eXi,Xj,Xkv&A d j(Xj)Xi,Xk,Xl i fXiXjXk f a l s e 将Xi,Xk置于Xj前方;e n di f;将Xl置于Xj后方;e n dw h i l e;w h i l eA d j(Xo)Xm,Xnb&Xo,Xm,Xnv 根据调整策略得到评分S c o r e,S c o r e,S c o r e;m a x m a x(S c o r e,S c o r e,S c o r e);更新最大评分o r d e r;e n dw h i l e;返回o r d e r;将o r d e r作为K 算法的节点顺序;f o r i n i;计算出Xi的评分Po l d;令O K T O P r o c e e d为真;w h i l eO K T O P r o c e e da n d|i|ud o 找出排在Xi前面的变量Xj,得到最大新评分Pn e w;i fPn e wPo l dt h e n Po l dPn e w;iij;e l s eO K T O P r o c e e d为假 e n di f;e n dw h i l e;e n df o r;(a)Xi sb e f o r eX,X(b)Xi sa f t e rXa n db e f o r eX(c)Xi sa f t e rX,X图基于邻居集置换的序搜索策略F i g S e q u e n c es e a r c hs t r a t e g yb a s e do nn e i g h b o r s e tp e r m u t a t i o n 复杂度分析 计算复杂度提议的T S K 算法的计算复杂度包含两部分:变量序搜索和贝网结构学习.假设n表示节点数目,v表示v 结构数目,p表示未定位的节点数目.任意两个节点间的因果效应计算复杂度为O(n);得到初始序后,基于v 结构与汇点邻居集的序搜索策略需要完成寻找节点和移动节点两个过程,计算复杂度为O(nv);基于邻居集置换的序搜索策略需要对其余节点进行置换操作,计算复杂度为O(np);获得高质量序后,使用K 算法学习最佳贝叶斯网络结构,其计算复杂度为O(n(n).因此,T S K 算法的计算复杂度为O(n)O(nv)O(np)O(n(n).显然,与K 算法的计算复杂度O(n(n)相比,T S K 算法的计算复杂度较高,但其能够自动从已知数据中学习到高质量的先验序列,显著提升了K 算法的学习精度.空间复杂度算法在开始执行时,需要存储节点间因果效应以获得初始序,其空间复杂度为O(n),获得先验序后,该空间被释放;基于v 结构与汇点邻居集的序搜索策略和基于邻居集置换的序搜索策略主要完成变量在初始序中的移动,其空间复杂度为O();获得高质量序后,调用K 算法.该过程需要存储每个变量的最佳父集,其空间复杂度为O(n k),其中k表示最大父节点数,最坏情况下即kn,空间复杂度为O(n).这与K 算法的空间复杂度相同.实验结果为了验证算法的优质性能,使用标准A s i a网络和A l a r m网络进行仿真实验.其中,A s i a网络主要应用于医疗诊断系统,利用式()学习节点初始序列;A l a r m网络主要应用于医疗监控系统,利用式()学习节点初始序列.标准网络的信息如表所列.实验运行环境为:W i n d o w s操作系统,处理器I n t e l(R)C o r e TMi M C P U,内存G B,M a t l a bR a软件平台.表标准贝叶斯网络参数T a b l eS t a n d a r dB a y e s i a nn e t w o r kp a r a m e t e r sA s i aA l a r mN u m b e ro fv a r i a b l e s N u m b e ro f e d g e s V a r i a b l es t a t e,M a xi n d e g r e eM a xo u t d e g r e eA s i a网 络 实 验 使 用 ,的样本量数据进行分析,A l a r m网络使用 ,的样本量数据进行分析,检测算法对不同样本量的敏感程度,并与基于因果效应的方法(C a u s a lE f f e c t,C E)、MMHC算法(M a x M i nH i l l C l i m b i n g,MMHC)、MCMC算 法(M a r k o v C h a i nM o n t eC a r l o,MCMC)和爬山法(H i l lC l i m b i n g,HC)相对应的项目平均值和标准差进行比较,比较的项目如下:正确边(C o r r e c t s i d e):与标准网络相比,算法学习到的正确边数.徐苗,等:一种基于两步搜索策略的K 改进算法有余边(E x t r ae d g e):与标准网络相比,算法学习到的多余边数.遗失边(M i s s i n ge d g e):与标准网络相比,算法未能学习到的边数.相反边(O p p o s i t ee d g e):与标准网络相比,算法学习到的方向相反边数.差错边(W r o n ge d g e):与标准 网 络 相 比,算 法 学 习 到的所有不 正 确 边 数,即 有 余 边、遗 失 边 和 相 反 边 的 数 量之和.实验分析结果如表、表和图图 所示.表A s i a网络实验分析T a b l eE x p e r i m e n t a n a l y s i so fA s i an e t w o r kp r o j e c tT S K C EMMHCMCMCHCC o r r e c ts i d e E x t r ae d g e M i s s i n ge d g e O p p o s i t ee d g e W r o n ge d g e 表A l a r m网络实验分析T a b l eE x p e r i m e n t a n a l y s i so fA l a r mn e t w o r kp r o j e c tT S K C EMMHCMCMCHCC o r r e c ts i d e E x t r ae d g e M i s s i n ge d g e O p p o s i t ee d g e W r o n ge d g e 图A s i a网络正确边数对比F i g C o m p a r i s o no f c o r r e c t s i d e s i nA s i an e t w o r k图A l a r m网络正确边数对比F i g C o m p a r i s o no f c o r r e c t s i d e s i nA l a r mn e t w o r k图A s i a网络正确边增量对比F i g C o m p a r i s o no f i n c r e m e n t i nA s i an e t w o r k图A l a r m网络正确边增量对比F i g C o m p a r i s o no f i n c r e m e n t i nA l a r mn e t w o r k图不同算法标准差对比F i g C o m p a r i s o no fS Do fd i f f e r e n t a l g o r i t h m s图 不同算法正确率对比F i g C o m p a r i s o no f a c c u r a c yo fd i f f e r e n t a l g o r i t h m sC o m p u t e rS c i e n c e计算机科学V o l ,N o ,S e p 由表、表可 知,在A s i a网 络 的 组 样 本 实 验 中,T S K 算法平均可以学习到 条正确边数,而基于因果效应的方法平均只能学习到 条正确边数;在A l a r m网络的组样本实验中,T S K 算法平均学习到的正确边数目达到 条,而基于因果效应方法仅为 条.T S K 算法较基于因果效应方法的正确边数平均提升了,并且在相反边和有余边方面的性能也有优势,虽然缺失边略多于基于因果效应的方法,但总体性能表现在对比算法中最优.原因在于学习到的v 结构与汇点邻居集信息可以准确修正错误汇点邻居顺序,再配合邻居集置换策略更新剩余不正确顺序,有效保证了父节点在其子节点之前,使得产生错误边的概率减小.由图、图可知,在A s i a网络的学习中,T S K 算法最少也可以学习到条正确边,仅比标准网络结构少一条,并且在 个样本时达到稳定,之后均可以学习到条正确边.在A l a r m网络的学习中,T S K 算法通过 个样本学习到 条正确边,在样本量较小时能够获得比其他算法更准确的网络结构,主要原因是v 结构和邻居集信息的两步序搜索策略的结合使用,使其更容易获得全局最优的节点序列,从而学习到高质量的网络结构.由图、图可知,与对比算法中最优的基于因果效应的方法相比,无论是在A s i a网络还是A l a r m网络,T S K 算法增量都很明显.相比基于因果效应方法采用的先学习网络,再通过反向调节和删边策略修正非法结构的方式,T S K 算法直接对作为源头的先验节点序列进行更新的方式更灵活.由图可知,A s i a作为小型网络,需要学习的边数少,所以算法的正确边标准差波动不大;A l a r m作为复杂网络,需要学习的边数较多,容易陷入局部最优,所以算法的正确边标准差波动较大.从图中可以看出T S K 算法正确边标准差在两个网络的学习中都具有明显优势.由图 可知,T S K 算法准确率最高.T S K 算法学习A s i a网络的准确率可以达到 ,学习A l a r m网络的准确率可以达到 ,均领先对比算法.实验结果表明,在标准数据集A s i a和A l a r m中,T S K 算法表现最好,在相同样本量下学习到的正确边最多,产生错误边的概率最小,并且正确边标准差较小,明显优于基于因果效应的方法、MMHC算法、MCMC算法和爬山法,可以获得更准确的网络结构.结束语K 算法需要给定准确的先验节点序才能学习准确的贝叶斯网络,对此,本文提出了一种基于变量邻居集和v 结构信息的两步序搜索策略学习方法T S K.该算法在v 结构信息可用时,利用v 结构与汇点邻居集的序搜索策略获得部分最优序列;在无v 结构信息可用时,搜索邻居节点间顺连、分连、汇连种结构形式,对节点序列进行有效调整,降低节点序列陷入较坏情况的概率,提升算法变量序列寻优的性能,最后配合K 算法构建优质的结构模型.实验结果证明,与其他算法相比,T S K 算法具备更高的准确性和稳定性,为贝叶斯网络的研究提供了新的技术路线.下一步研究内容是面对非稳态的数据场景,利用K 算法构建拟合数据较好的自适应贝叶斯网络模型.参 考 文 献L OUCY,L IXS,AT OU IM A B a y e s i a nn e t w o r kb a s e do na na d a p t i v et h r e s h o l ds c h e m ef o rf a u l td e t e c t i o na n dc l a s s i f i c a t i o nJ I n d u s t r i a la n d E n g i n e e r i n g C h e m i s t r y R e s e a r c h,():T A GH I MO L L A A,R A B B AN IM,GAVA R E S HK IM,e ta l S a f e t y i m p r o v e m e n t i nag a sr e f i n e r yb a s e do nr e s i l i e n