一种基于两步搜索策略的K2改进算法.pdf
《一种基于两步搜索策略的K2改进算法.pdf》由会员分享,可在线阅读,更多相关《一种基于两步搜索策略的K2改进算法.pdf(8页珍藏版)》请在咨信网上搜索。
1、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
2、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 改进算法徐苗王慧玲,梁义綦小龙高阳伊犁师范大学网络安全与信息技术学院新疆 伊宁 南京大
3、学计算机科学与技术系计算机软件国家重点实验室南京 (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 结构和邻居集信息可靠调整汇点的邻居在序中的位置;其次,在贝网基
4、本组成结构的启发下,借助变量邻居集信息,通过执行顺连、分连、汇连个基本结构的搜索,准确修正父节点与子节点的序位置,获得最优序列.实验结果表明,在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
5、 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
6、 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
7、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
8、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
9、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
10、 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
11、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
12、 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
13、 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引言贝叶斯网络是由概
14、率推理和图论理论结合而成的图形化模型,通过条件概率表和有向无圈图定量地描述了变量之间的独立关系和依赖程度,在处理不确定性知识和数据分析方面具备独特的优势,是人工智能领域的有力工具.由于贝叶斯网络具有坚实的数学基础、灵巧的学习体系和直观形象的语义表述等特点,引起了国内外众多研究学者的极大兴趣.近几十年来,贝叶斯网络成为了研究热点,并在医疗诊断、机器视觉、因果推断、工业控制、学习预测和数据挖掘等领域 得到了广泛应用.贝叶斯网络最早主要是由领域专家的先验知识进行构建,在网络规模较小时可行,但是面对较大网络规模时,变量间的因果关系变得十分复杂,这时再依靠领域专家来构建贝叶斯网络会非常困难且容易出错.如
15、何从已知数据中学习贝叶斯网络已成为现阶段的研究方向,这是一个N P难问题.目前,结构学习算法主要分为:基于约束的学习算法、基于评分搜索的学习算法和混合学习算法.约束的学习算法通过信息论进行条件的独立性检测,判断变量间关系从而确定网络结构,例如T P D A算法和S G S算法等,它们具备严格的理论基础,学习效率较高,但依赖于独立检测的准确度,在多维数据或者数据不足时模型学习精度不可靠.基于评分搜索的学习算法通过评分函数对网络模型结构的优劣进行评判,利用搜索策略寻找最佳评分的模型结构,例如爬山法和粒子群算法 等,它们可以学习到较精确的结构模型,但在复杂结构场景下搜索空间过大,导致搜索效率大幅降低
16、.混合学习算法将上述两种算法结合,首先利用基于约束的学习算法降低网络空间的搜索规模,然后执 行 评 分搜 索 的 学 习 算 法 寻 找 最 佳 模 型 结 构.例 如MMA C O算法,其步骤分为两步:先通过MMP C算法获得基本模型,再使用蚁群算法确定基本模型的边和方向.混合学习算法已成为现阶段受欢迎的研究方向之一.基于评分搜索的K 算法 将假设的随机变量顺序作为输入,利用变量拓扑序列约束搜索过程,在有效减小搜索空间的同时还能降低非法结构的概率,整体表现优于大多数经典算法.因此,K 算法的效率很大程度上依赖于变量顺序,不准确的变量顺序无法学习到正确的结构模型.如何获得准确的变量顺序是使K
17、算法更加实用的主要挑战,本文提出的充分利用v 结构和邻居集信息的混合学习算法为此提供了新的思路.本文的主要贡献如下:)提出了基于v 结构与汇点邻居集信息的序搜索策略.在学习过程中,使用该信息,无需执行评分搜索计算,直接对初始序列进行调整,实现部分节点定序,在减少计算量的同时也合理约减了序搜索空间.)受到贝叶斯网络结构的个基本组成成分启发,提出了基于邻居集置换的序搜索策略.对未定序节点进行种置换搜索,可靠地从给定的数据中学习出高质量顺序,有效避免了过早陷入局部最优,实现全局搜索.)在标准数据集上对所提算法T S K 进行实验对比分析,以评估其学习性能.实验结果表明了T S K 算法的有效性.相关
18、工作近年来,针对K 算法需要准确变量拓扑序的问题,研究者们相继给出了很多解决方案.文献 提出了基于MW S T K 的算法,通过MWS T算法构建有向生成树,将生成的排序作为K 算法的先验拓扑序列,由于MWS T算法的定向精度较低,该算法在构建基准网络模型时结果不理想.文献 提出了基于因果效应的算法,该算法通过改进版因果效应法和B D e评分获得节点优先次序,利用删除边操作和反向调节修正结果,提升了网络结构学习性能,但是面对大型网络时易陷入局部最优.文献 提出了K A C O算法,通过种群中的初始个体随机创建节点顺序,由蚁群算法进行优化学习得到最佳序列,在蚁群算法过程中,运行K 搜索算法计算各
19、排序的适应度,寻找最优排序并直接获得相对应的网络结构,该算法存在时间复杂度较高的问题.文献 提出了I TN O K P C算法,利用信息理论测试节点间的依赖关系,通过确定父子节点关系对生成的矩阵进行验证,获得最终结构模型,该算法更适用于中小规模网络.文献 提出了优先级排序算法,通过MCMC算法 学习拟合观测值的结构模型,利用定义的节点排序评分函数获得变量先验序,该算法减少了穷举所需花费的较长时间,但受到MCMC算法的约束.文献 提出了重构先验信息的算法,将MCMC算法与模拟退火算法相结合,根据邻域查找规则配合专家知识和数据修补等方法获得最佳网络结构,该算法在小数据集上表现较好,但是需要具备完整
20、且准确的领域知识,在很多场景下难以实现.文献 提出了P S O K 算法,利用粒子群算法更新变量拓扑序,通过K 算法构建贝叶斯网络,使用A I C评分函数进行判定取得对应拓扑序列的适应度函数并进行种群迭代,该算法的运行速度较慢,学习效率较低.文献 提出了基于强连通的改进算法,利用每个变量的最佳父节点集来构建强连通图,从强连通分量中推断变量的顺序,该算法降低了时间复杂度,但最佳父集的准确性对算法结果影响较大.算法的构建T S K 算法分为步:首先利用改进版因果效应法学习节点优先排序,将其作为初始顺序;然后通过P C算法获得v 结构和邻居集,使用v 结构与汇点邻居集信息对初始序列进行调整,修正不符
21、合父子节点关系的节点顺序;接着利用邻居集置换策略,对邻居节点进行置换搜索,进一步修正节点顺序获得最佳节点序;最后利用K 算法学习高质量贝叶斯网络结构模型.通过v 结构和邻居集信息的配合使用,能够快速而有效地检测出错误节点顺序并做出修正.节点优先排序利用改进版因果效应法学习节点优先排序,可以定性地表达节点之间的父子关系.对于二值数据网络和多值数据网络,分别从两种方法开始,得到所有节点的优先度并降序排列,获得节点优先排序.二值数据网络P e a r l提出的因果理论仅考虑X和Y在Y处的因果效应,改进版因果效应法 在此基础上进行了拓展,对于任意两个节点Xi和Xj,考虑XiXj在Xj和Xj两处的因果效
22、应,因果效应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的优先度加.对最终的节点优先度进行降序排列,获得节
23、点优先排序,将其作为初始序列.多值数据网络对于多值数据网络,搜索每个节点最多的两个状态值,使用相对应的值计算任意两个节点的因果效应.对于任意两个节点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的样本数目.多值数据网络方法与二值数据网络方法的规则相同,依次计算每两个节点之间的因果效应,获得初始序列.基
24、于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 结构和邻居集对最佳变量拓扑序进行搜索,达到减小序列搜索空间规模、准确判定序列正确性的目
25、的.节点序搜索策略改进版因果效应法删除了“d o 操作”,所以获得的初始序列是一个近似正确的序列,仍可能存在不正确的父子序列顺序.考虑到之前的算法,如贪婪爬山法,在调整节点序时,节点的移动是随机的,没有结合额外的信息,学习效果不理想.为了提高序列的准确度,学习最优网络结构,本文配合使用两种节点序搜索策略:基于v 结构与汇点邻居集的序搜索策略和基于邻居集置换的序搜索策略.情况v 结构信息可用时,采用基于v 结构与汇点邻居集的序搜索策略.定义(邻居)如果节点Xi和节点Xj之间存在一条边,则节点Xi是节点Xj的邻居,反之亦然,记作A d j(Xi)Xj.对于三元组Xi,Xj,Xk,如果存在XiXj,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一种 基于 搜索 策略 K2 改进 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。