基于条件独立测试的链图结构学习算法

链图是贝叶斯网络和马尔科夫网络的自然推广,具有较强的表达能力.但目前关于链图结构学习算法的研究较少.本文基于贝叶斯网络结构学习的Grow-Shrink算法思想,提出一种链图等价类结构学习算法.该算法首先利用网络中结点的局部邻域信息,学习结点的邻接结点恢复网络骨架;然后根据链图复合体有向边的特点,利用条件独立测试确定网络的复合体有向边,从而恢复链图结构.理论分析和实验结果表明了该算法的正确性和有效性.     

基于混合方式的贝叶斯网络等价类学习算法

贝叶斯网络(BN)是不确定知识表示和推理的主要方法之一,是人工智能中重要的理论模型.针对现有混合方法学习BN结构不稳定、容易陷入局部最优等问题,本文将图论中的最大主子图分解理论与条件独立(CI)测试相结合,同时引入少量的局部评分搜索,提出一种新的基于混合方式的BN等价类学习算法.新算法通过确定所有变量的Markov边界构造网络的无向独立图,并对无向图进行最大主子图分解,从而将高维的结构学习问题转化为低维问题,然后利用低阶CI测试和局部评分搜索识别子图中的V结构.理论证明以及实验分析显示了新算法的正确性和有效性.     

基于有界增长图的无线传感器网络虚拟骨干形成算法

提出了基于有界增长图的虚拟骨干近似形成算法(VBF).算法采用网络划分机制构建极大独立集,使用染色过程形成簇图;以2分离集合子集递归计算(1 ε)近似局部最小支配集,合并局部最优解构造全局最优解:然后调整簇头传输范围直接以全局最优解形成最小近似连通支配集,无须加入网关节点,降低计算开销.构造的连通支配集具有常量扩展因子和常量度,并且算法运行时节点仅需直接邻域信息.理论分析和仿真比较证明了算法的正确性和有效性.     

基于极大独立集的最小连通支配集的分布式算法

全网范围的广播在无线传感器网络和移动自组织网络中有着广泛的应用.为节省网络资源,减少冗余转发节点成为广播中需解决的关键问题.广播过程中最小化参与转发节点数问题与图论中求解最小连通支配集问题等价,而在任意图中求解最小连通支配集是NP完全问题.本文基于极大独立集,提出了一种求解最小连通支配集的分布式算法(MISB),并证明了算法的正确性.仿真结果表明,使用该算法能得到较小的连通支配集,从而有效减少网络广播过程中的转发节点数,大大节省了网络资源.     

用马尔科夫模型优化分布式最小连通支配集算法

 为了提高无线传感器网络(WSNs)的能量利用效率、延长网络的生存时间,对基于极大独立集的最小连通支配集算法(MISB)进行优化,提出了一种新的算法.本文首先应用离散马尔科夫链为节点建立模型,并且根据模型预测节点的能量消耗;本算法进行多轮选举,每一轮开始时根据节点的度和能量选举支配点,依据模型预测的能量消耗决定本轮的运行时间,本轮运行结束时从新选举支配点,开始新一轮.仿真结果表明,本算法和原算法相比可以更好地平衡网络的能量消耗,提高全网的能量利用率,极大地延长网络的生存时间.     

Beta在线匹配

二部图的在线匹配问题最早由Karp等人在1990年提出,该问题在近年得到了广泛的关注,在日常生活中有大量的应用.本文引入了Beta分布作为二部图节点间的邻接关系的统计先验,提出了最大化节点的预留匹配能力准则作为在线匹配策略的评价度量,设计了在线匹配算法BetaOM,并证明了该算法的正确性.本文把BetaOM分别应用于基于人造数据和真实数据的在线匹配问题,实验的结果显示该算法优于经典的Greedy算法和Ranking算法.     

分布式环境下基于马尔科夫链的图流三角近似计算

图三角数量的计算是计算网络聚集系数和传递性的重要步骤.大数据背景下,以采样为策略的近似计算成为图三角计算的主要方法,然而此类方法面临时空消耗和计算错误性两大难题.本文提出了一种针对图流的基于马尔科夫链的图三角近似计算算法,该算法以窗口作为图流处理单位,将马尔科夫链与采样相结合,保证降低错误率的同时实现动态适应内存空间的变化.实验显示,相较其他三角形近似计算算法,该算法在错误率上降低2~4倍,时间消耗上也有很大改进.     

基于判别邻域嵌入算法的说话人识别

该文提出一种基于判别邻域嵌入(DNE)算法的说话人识别。判别邻域嵌入算法作为流形学习方法的一种,可以通过构建邻接图获取数据的局部邻域结构信息;同时该算法可以充分利用类间判别信息,具有更强的判别能力。在美国国家标准技术研究院2010年说话人识别评测(NIST SRE 2010)电话-电话核心测试集上的实验结果表明了该算法的有效性。     

基于大规模网络的结构能控性指数算法

<正>传统的网络能控性是在给定输入下通过能控性判据来判断该网络是否可控,或是寻找使有向网络达到可控时的最少驱动节点集。为了研究网络达到可控时的链路长度,对于一个没有给定输入的有向网络,本文通过对节点度的研究和删除边等操作将有向网络分解成多条控制链,将控制链的根节点作为整个网络的驱动节点集。同时引入能控性指数的概念,对控制链长度进行研究。最后基于节点的度提出了一个算法将有向网络分解成独立可控的控制链,得出网络的驱动节点集和结构能控性指数,通过对大规模随机网络和真实网络的仿真,验证了算法的有效性。     

基于图着色的无线自组网极小连通支配集算法

基于连通支配集算法的虚拟主干网技术对于无线自组网的路由优化、能量保护和资源分配都具有重要的作用。通过引入极大独立集和极小支配集概念,基于图着色思想提出一种新的适合于无线自组网的极小连通支配集算法,从理论上证明了该算法的正确性和高效性,也通过仿真实验分析了该算法在多种情况下的实际性能,仿真结果表明新算法在簇头和主干节点数目方面具有较好的性能,特别在节点密集的网络环境中更加突出。     

基于混合方式的贝叶斯网弧定向算法

 贝叶斯网是不确定知识表示及推理的主要方法之一,BNs结构中的因果关系在知识建模中起到十分关键的作用,因此确定BNs中弧的方向是一重要问题.目前已有的方法存在以下问题:(1)算法计算复杂性高;(2)将统计不可分的弧定向,可能与领域知识不符.本文提出一种结合条件独立测试和打分搜索的BNs弧定向方法.该方法仅执行零阶和一阶条件独立测试,执行次数为多项式级;打分搜索可分解为局部子图的搜索,提高了算法的效率.算法输出结果为最大链图,该图仅对统计可分的弧进行定向,对统计不可分的弧保留无向的特性.这种结果更准确的表现了数据中蕴含的因果关系,便于结合领域知识进行建模.     

基于马尔科夫毯约束的最优贝叶斯网络结构学习算法

本文针对最优贝叶斯网络的结构学习问题,在动态规划算法（Dynamic Programming,DP）的基础上,使用IAMB算法（Incremental Association Markov Blanket,IAMB）计算得到的马尔科夫毯对评分计算过程进行约束,减少了评分的计算次数,提出了基于马尔科夫毯约束的动态规划算法（Dynamic Programming Constrained with Markov Blanket,DPCMB）,研究了IAMB算法中重要性阈值对DPCMB算法的各项性能指标的影响,给出了调整阈值的合理建议.实验结果表明,DPCMB算法可以通过调整重要性阈值,使该算法的精度与DP算法相当,极大地减少了算法的运行时间、评分计算次数和所需存储空间.     

基于行为学习的改进LapSVM算法及其应用

拉普拉斯支持向量机通过流形正则项能够利用未标记数据信息进行半监督学习。但其流形正则项中的数据邻接图由于没有利用数据的标记信息而不能准确表征数据流形结构,并且热核参数的经验式选择也无法保证算法的学习性能。为此,基于人类行为认知的思想构造一种新的数据邻接图:首先设计一种能够利用数据标记信息的行为相似性边权值,然后所提出的局部视角距离不仅反映邻域结构特性而且克服了热核参数选择的问题。在公共数据集上的实验验证了所提出算法的性能,最后将之应用于辐射源个体识别。     

基于双通道生成对抗网络的镜片缺陷数据增强

针对小样本条件下深度学习缺陷检测算法识别率较低的问题,提出一种基于双通道生成对抗网络的数据增强方法.由全局鉴别层和局部鉴别层两通道组成生成对抗网络,其中局部鉴别器可以增加缺陷类型的置信度损失,实现对局部信息的增强.采用所提方法在镜片缺陷图像数据集上进行实验.实验结果表明,所提方法的最近邻留一指标、最大均值差异和Wasserstein距离分别达到0.52、0.15和2.81;对于麻点、划痕、气泡和异物的缺陷类型图像,生成的图像质量优于条件生成对抗网络、Wasserstein距离生成对抗网络和马尔科夫判别器.双通道生成对抗网络生成的镜片图像有着多样性的全局信息和高质量的细节特征,可以有效增强镜片缺陷数据集.     

一种改进的分布式最大权独立集算法

能快速准确寻找给定图中的最大权独立集的分布式算法,对于解决无线网络中的资源调配、无线骨干网构建等问题具有非常重要的指导意义。该文以基于最大乘信用传播的分布式算法为框架,假设所有节点了解自己邻居节点之间的局部拓扑信息,启发式地提出一种新的相邻节点间交换消息的计算方法以及相应的分布式最大权独立集算法。仿真结果表明,所提算法摆脱了文献中已有算法对图结构必须是树或者二分图的要求,且权和性能优于已有的分布式算法。     

Distributed Node Localization Algorithm Based on MDS and SDP

提出一种新的节点定位算法,基于MDS和SDP的分布式节点定位算法(DLMS).该算法的主要思想是将整个无线传感器网络划分成若干个局部定位区域,在每个局部定位区域选择MDS定位算法或SDP定位算法建立一个局部相对定位图,然后将所有的局部相对定位图合并成全局相对定位图,最后利用锚节点的信息得到节点的估计位置.实验仿真结果表明,该算法能够提高节点的定位精度,尤其是在节点分布不均匀的情况下,同时该算法还能够节约锚节点数量.     

基于信息损失量估计的匿名图构造方法

首先分析了在进化的社会网络序列中,攻击者利用节点度信息,通过识别目标节点的方法对局部社会网络进行攻击过程,分析了利用k匿名方法对该类攻击进行隐私保护时存在的信息损失问题,针对该问题,提出了一种基于信息损失量估计的k匿名图流构造方法,通过子图节点属性泛化、子图内部结构的泛化控制图重构的信息损失,通过禁止子图内部扰动阻止网络攻击。定义匿名过程中由于图重构造成的节点和结构信息损失的估算方法,建立了基于贪婪聚类算法的网络节点的k匿名聚类算法,根据信息损失估计实现匿名分组,在进化的社会网络中以最小信息损失量构造匿名社会网络,在医疗诊断数据集上的实验表明所提方法能够较理想地控制信息损失量。     

基于DPSO的不确定系统测试性建模

针对关联模型在复杂装备测试性评估中对不确定问题描述与分析的缺陷,给出了基于贝叶斯网络的测试性模型,利用条件概率描述系统的不确定信息.在基于统计数据的测试性建模与评估中,由于故障征兆与故障原因统计的不完全性,致使测试性建模属于数据不完备情况下的结构和参数学习问题,针对该问题利用离散粒子群算法,通过测试性数据完备化,以贝叶斯测度为计分值,实现贝叶斯网络结构学习.最后通过实例验证了算法的正确性和有效性.     

基于优化结构洞的无向加权网络关键节点发现方法

针对目前大多数关键节点发现算法没有兼顾桥节点与其他类型关键节点,造成评价结果存在片面性的问题,使用加权网络模型结合结构洞理论,提出一种优化结构洞的无向加权网络关键节点发现方法。综合考虑了节点的邻居数量及其与邻居间的拓扑结构,首先通过定义节点的邻接度和二次邻接度来衡量邻居节点对其的重要程度,在此基础上测量网络中的结构洞约束系数并通过排序发现网络中处于重要位置的关键节点。该方法既反映出节点局部连接的特性,又可在全局拓扑未知的情况下发现其中的关键节点,解决了全局方法计算复杂度高的问题。实验结果表明,该方法比基于介数、节点强度、接近度方法更准确、有效地发现无向加权网络中的关键节点。     

基于融合的无线传感器网络k-集覆盖的分布式算法

当节点采用概率感知模型且融合多个节点的数据进行联合感知的情况下,提出了一个新的无线传感器网络的覆盖优化问题:基于融合的k-集覆盖优化问题.首先,将优化问题建模为融合覆盖博弈,证明该博弈是势博弈,且势函数与优化目标函数一致,因此,最优解是一个纯策略Nash均衡解.其次,给出了节点间融合覆盖效用独立的判定条件,进而分别提出同步、异步控制的、基于局部信息的、分布式的覆盖优化算法,证明了算法收敛到纯策略Nash均衡.最后,仿真实验结果表明,当算法收敛时,网络能达到高的覆盖率且具有好的覆盖稳定性.