计算机科学

47卷第5期目录

计算机科学. 2020, 47 (5): 0-0.

摘要 ( 236 )

PDF(274KB) ( 706 )

相关文章 | 多维度评价

直觉主义视角下量子逻辑的进一步解释

周恒, 王拥军, 王宝山, 燕健

计算机科学. 2020, 47 (5): 1-6. doi:10.11896/jsjkx.191200056

摘要 ( 582 )

PDF(1562KB) ( 1192 )

参考文献 | 相关文章 | 多维度评价

量子计算机将成为计算机科学未来的发展方向之一,量子逻辑是反映量子计算与量子信息的数学基础。Von Neumann用希尔伯特空间的闭子空间表示量子物理系统的性质,构成正交模格,其元素有明确的物理意义,但无法刻画叠加性质;Bob Coecke填加析取元素来表示叠加性质,借助Heyting代数,基于正交模格构造命题格对量子逻辑进行刻画,命题格中元素有明确的数学含义,但物理意义不够明确。针对后者,文中对命题格中元素的物理含义做出了进一步的解释,认为补充的析取元素代表的物理意义为描述叠加性质时所依赖的“观察者视角”,使得命题格中所有元素都获得了清晰的物理含义,通过阐述量子逻辑在测量时的应用,为量子计算中的隐形传态、超距同步等技术提供了重要的理论依据。

在线影响力最大化研究综述

孔芳, 李奇之, 李帅

计算机科学. 2020, 47 (5): 7-13. doi:10.11896/jsjkx.200200071

摘要 ( 1165 )

PDF(1591KB) ( 3076 )

参考文献 | 相关文章 | 多维度评价

影响力最大化是指在给定的影响力传播模型下选取种子节点使其传播信息范围最广。此问题的应用场景十分广泛,包括推荐系统、病毒营销、信息扩散和链接预测等。在实际应用中,信息传播模型中的点对点传播概率通常是未知的,而在线学习算法可以在交互过程中自主学习未知参数,逐步逼近最优解。文中首先讨论了影响力最大化问题的定义,介绍了常用的影响力传播模型,归纳了常见的离线影响力最大化算法;随后介绍了经典的在线学习框架——多臂老虎机问题,分析了在线影响力最大化问题的研究现状,并通过实验对常见的在线影响力最大化算法在真实社交网络中的性能表现进行对比;最后总结了该课题面临的挑战并展望了未来的研究方向。

关于同步部分规约的有限自动机的优化问题的近似难度

朱凯, 毋国庆, 袁梦霆

计算机科学. 2020, 47 (5): 14-21. doi:10.11896/jsjkx.200200073

摘要 ( 357 )

PDF(1902KB) ( 825 )

参考文献 | 相关文章 | 多维度评价

自动机是可同步的是指它具有满足以下性质的同步字:不论自动机当前所处的状态,以同步字为输入执行后它一定会到达某个特定状态。同步自动机问题的核心是计算最短同步字。聚焦于这一核心问题,文中就一类称为部分规约的确定的有限自动机的最短同步字问题,研究了近似计算这类自动机的最短同步字的复杂性,即近似计算它的难度,该工作有助于其近似算法的分析与设计。通过建立由两个优化问题(MAX SAT问题以及MAX FA-INT问题)到最短同步字长度计算这一问题(即Shortest-Syn)的归约,利用与概率可检验证明(Probabilistically Checkable Proofs,PCP)定理和概率可检验辩论(Probabilistically Checkable Debate,PCD)定理有关的若干结果证明了文中的主要结论:对于部分规约的确定的有限自动机,在某个近似因子内Shortest-Syn的近似难度是NP-难的和PSPACE-难的,除非NP和PSPACE分别坍塌到P。

铁磁性双态自旋系统配分函数的可近似性

邱国良, 张驰豪

计算机科学. 2020, 47 (5): 22-26. doi:10.11896/jsjkx.200200119

摘要 ( 436 )

PDF(1445KB) ( 953 )

参考文献 | 相关文章 | 多维度评价

双态自旋系统是统计物理学在处理互作用粒子系统时所建立的简化模型,计算该系统的配分函数(partition function)在统计物理及计算机科学中均有重要意义。对于一般的系统,配分函数的精确计算已被证明是＃P难的,但其是否能被高效地近似计算一直是理论计算机科学关注的问题。近年来,这一领域取得了较大的突破。研究者建立了配分函数的可近似性与该物理系统相变的联系,并且在很大的参数范围内理解了可近似性。文中对铁磁性双态自旋系统配分函数的可近似性研究进行了综述,介绍了目前针对该问题设计近似算法的三类技巧的主要思想,并把这些算法的结果与该问题在不可近似方面的结果进行了比较。

分级论辩系统的逻辑研究

谭立兴, 王福俊

计算机科学. 2020, 47 (5): 27-31. doi:10.11896/jsjkx.200200052

摘要 ( 406 )

PDF(1464KB) ( 719 )

参考文献 | 相关文章 | 多维度评价

近年来,形式论证已逐渐成为人工智能领域的研究热点之一。自Dung于1995年提出抽象辩论框架起,学术界普遍认为论辩的核心任务是在各种基于外延的语义下对论点集进行评估,以确定其辩护状态。分级论辩系统(Graded Argumentation System,GAS)是对经典Dung型论辩系统(Dung-style Argumentation System,DAS)的推广,通过一般化DAS语义的两个核心性质,即无冲突性和可接受性,来提供更细化的论点状态概念。当前的论辩系统语义等效性研究主要集中在框架和论点层次上,可为其结构约简提供有力的保证。针对两个不同分级论辩系统中论点的语义等效问题,首先运用分级模态逻辑(Graded Modal Logic,GML) 形式化分级论辩系统的片段,然后建立并证明了分级论辩系统基于外延的语义和GML公式之间的一一对应关系,最后定义分级互模拟关系并证明其蕴含分级论辩系统的4个重要的语义等价性。

一种布尔公式的代数逻辑约化新方法

刘江, 周鸿昊

计算机科学. 2020, 47 (5): 32-37. doi:10.11896/jsjkx.190400018

摘要 ( 504 )

PDF(1353KB) ( 893 )

参考文献 | 相关文章 | 多维度评价

布尔可满足问题是最早被证明的NP完全问题之一,1-in-3-SAT问题是一个NP完全的布尔可满足子类问题。1-in-3-SAT的计算复杂度取决于对应公式的变量以及子句的个数。将1-in-3公式归约为一个变量数或者子句数更少的1-in-3公式,是提高1-in-3-SAT问题求解效率的一个关键。基于一个新的范式形式——XCNF,针对1-in-3-SAT问题提出一种新的代数逻辑约化方法,用于在多项式时间内约减一个1-in-3公式的变量数和子句数。所提算法的主要思想为:首先将1-in-3公式转化为XCNF公式,然后尝试找出XCNF公式中的X-纯文字,并利用X-纯文字法则对1-in-3公式中相应的布尔变量赋值,最后得到一个约减公式,该约减公式与原公式的1-in-3可满足性等价。

带膜分裂和促进剂的通讯膜系统求解QSAT问题

宋勃升, 程玉

计算机科学. 2020, 47 (5): 38-42. doi:10.11896/jsjkx.191100204

摘要 ( 247 )

PDF(1422KB) ( 700 )

参考文献 | 相关文章 | 多维度评价

膜计算是自然计算的一个分支,膜计算中所研究的模型均称为膜系统,而细胞间通讯是膜系统的一个重要特征。带膜分裂的通讯膜系统是一种分布式并行计算模型,可以在多项式时间内解决计算困难问题。文中将促进剂引入带膜分裂的类细胞型通讯膜系统,提出了膜系统的一种变型——带膜分裂和促进剂的通讯膜系统,其中,一个促进剂可以同时控制多条规则,而促进剂本身不参与该条规则的进化。文中研究了带膜分裂和促进剂的通讯膜系统的计算效率,证明该类膜系统在使用同向规则长度为2,每条规则中促进剂的个数最多为1时,可以在多项式时间内求解PSPACE完全问题(QSAT问题)的统一解。

决定图框架下本体学习算法的稳定性分析

朱林立, 华钢, 高炜

计算机科学. 2020, 47 (5): 43-50. doi:10.11896/jsjkx.200100129

摘要 ( 428 )

PDF(1448KB) ( 686 )

参考文献 | 相关文章 | 多维度评价

传统的本体算法采用启发式的方法来计算语义相似度,而随着本体处理数据量的日益增大,越来越多的机器学习方法被用于本体函数的获取。稳定性是本体学习算法的必要条件,它要求在本体样本集做轻微改动的情况下不会对得到的最优本体函数产生本质的改变。文中研究了在本体样本集的依赖关系由图结构决定的框架下,本体学习算法的稳定性和对应的统计学特征。首先对传统的PO和LTO一致稳定性条件进行分析;其次在大样本情况下扩展一致稳定性条件,提出Pk和LkO一致稳定性并得到相关的理论结果;最后把替换本体样本和删除本体样本两种样本进行变换组合,提出在大本体样本前提下的组合一致稳定性概念,并利用统计学习理论的方法得到一般结果。此外,在各类稳定性条件下,对满足m-独立条件的本体学习算法的广义界进行了讨论。

图的树分解算法及其应用

雷莹, 许道云

计算机科学. 2020, 47 (5): 51-58. doi:10.11896/jsjkx.191100118

摘要 ( 690 )

PDF(2079KB) ( 1777 )

参考文献 | 相关文章 | 多维度评价

一个图G=(V,E)的树分解是将结点集V的子集作为树T的节点,使得在T上任意一条路径上的两个端节点的交集包含于该路径上的任意一个节点中。将T上最小(节点)对应子集的元素个数减1定义为分解树T的宽度,用宽度最小的分解树T的树宽度定义图G的树宽度。一个合取范式(Conjunctive Normal Form,CNF)公式F可以用一个二分图G=(V∪C,E)表示(公式的因子图),其中变元结点集V对应公式F中的变元集,子句结点集C对应公式F中的子句集,变元在子句中的正(负)出现用实(虚)边表示。忽略公式因子图中边上的符号,得到一个二分图。文中研究了图的树分解算法,并将树分解算法应用到CNF公式的因子图树分解。通过实验观察公式因子图的树宽度与求解难度之间的联系。

基于概率和时间因素的Petri网业务流程一致性分析

杨皓然, 方贤文

计算机科学. 2020, 47 (5): 59-63. doi:10.11896/jsjkx.190500119

摘要 ( 381 )

PDF(1692KB) ( 689 )

参考文献 | 相关文章 | 多维度评价

业务流程一致性分析作为业务流程管理的重要内容之一,近年来一直是业务流程管理研究领域的热点。目前已有的方法主要从控制流和数据流两方面进行研究,在实际情况下,概率和时间因素会对业务流程产生较大的影响。因此,文中提出了一种基于概率和时间因素的Petri网业务流程一致性分析方法。首先,给出了基于概率因素的控制流Petri网和基于时间因素的数据流Petri网的定义;然后,将基于概率因素的控制流Petri网和基于时间因素的数据流Petri网中的所有变迁分别映射到原业务流程Petri网中,得到各自的行为映射表,并针对两种类型的Petri网提出相应的行为兼容度算法,依据行为兼容度的值来衡量业务流程的一致性程度;最后,进行实例分析,结果显示了该方法的有效性和优越性。

基于多特征融合的增强子-启动子相互作用预测综述

胡宇佳, 甘伟, 朱敏

计算机科学. 2020, 47 (5): 64-71. doi:10.11896/jsjkx.191100027

摘要 ( 422 )

PDF(2893KB) ( 1668 )

参考文献 | 相关文章 | 多维度评价

研究增强子-启动子相互作用机理有助于人们理解基因调控关系,进而揭示与疾病相关的基因,为疾病诊疗提供新思路和新方法。传统的生物检测方法的实验成本高、耗时长,且受分辨率的限制,难以精确鉴定单个增强子-启动子的相互作用。通过计算方法来解决生物问题已成为近年来的研究热点,此类方法可以通过复杂的网络结构主动学习序列特征和空间结构,进而准确预测增强子-启动子的作用。首先介绍了传统生物实验检测方法的研究现状;然后从序列特征的角度出发,围绕多特征融合的基本思想,对统计学和深度学习方法在增强子-启动子相互作用预测上的应用进行归纳整理;最后对该领域的研究热点和挑战进行总结分析。

一种基于粗糙集和密度峰值的重叠社区发现方法

张琴, 陈红梅, 封云飞

计算机科学. 2020, 47 (5): 72-78. doi:10.11896/jsjkx.190400160

摘要 ( 372 )

PDF(1728KB) ( 967 )

参考文献 | 相关文章 | 多维度评价

随着互联网和社会的发展,各个领域每天都会产生大量相互关联、彼此依赖的数据,这些数据根据不同的主题形成了各种复杂网络。挖掘社区结构是复杂网络领域中的一项重要研究内容,因为其在推荐系统、行为预测和信息传播等方面具有极其重要的意义。社区结构中的重叠社区结构在生活中普遍存在,更具有实际研究意义。为有效发现复杂网络中的重叠社区,文中引入了粗糙集理论对社区进行分析,识别出重叠节点,进而提出了一种基于粗糙集和密度峰值的重叠社区发现方法OCDRD(Overlapping Community Detection Algorithm Based on Rough Sets and Density Peaks)。该方法在传统网络节点局部相似性度量的基础上,结合灰色关联分析方法求出网络节点间的全局相似性,进而将其转化为节点间距离。将密度峰值聚类算法的思想应用于该算法中,以根据网络结构自动选取社区中心节点。依据网络中节点的距离比例关系,定义了社区的上近似、下近似以及边界域。最后,不断调整距离比率阈值并进行划分迭代,在每次迭代中针对社区的边界域进行计算,从而获得最佳重叠社区划分结构。在LFR基准人工网络数据集和真实网络数据集上,基于标准互信息(Normalized Mutual Information,NMI)和具有重叠性模块度EQ这两个评价指标,将OCDRD方法与近几年效果较好的其他社区发现算法进行测试比较。实验结果显示,OCDRD方法在社区划分结构方面整体优于其他社区发现算法,表明了该算法的可行性和有效性。

基于金融文本情感的股票波动预测

赵澄, 叶耀威, 姚明海

计算机科学. 2020, 47 (5): 79-83. doi:10.11896/jsjkx.190400145

摘要 ( 569 )

PDF(4546KB) ( 1725 )

参考文献 | 相关文章 | 多维度评价

股票市场的情绪可以在一定程度上反映投资者的行为并影响其投资决策。市场新闻作为一种非结构性数据,能够体现并引导市场的大环境情绪,与股票价格一同成为至关重要的市场参考数据,能够为投资者的投资决策提供有效帮助。文中提出了一种可以准确、快速地建立针对海量新闻数据的多维情绪特征向量化方法,利用支持向量机(Support Victor Machine,SVM)模型来预测金融新闻对股票市场的影响,并通过bootstrap来减轻过拟合问题。在沪深股指上进行实验的结果表明,相比于传统模型,所提方法能够将预测准确度提高约8%,并在3个月的回测实验中获得了6.52%的超额收益,证明了其有效性。

基于DCGRU-RF模型的路网短时交通流预测

熊亭, 戚湧, 张伟斌

计算机科学. 2020, 47 (5): 84-89. doi:10.11896/jsjkx.190100213

摘要 ( 394 )

PDF(1790KB) ( 881 )

参考文献 | 相关文章 | 多维度评价

随着城市化进程的加快,我国城市机动车数量快速增加,使得现有路网容量难以满足交通运输需求,交通拥堵、环境污染、交通事故等问题与日俱增。准确高效的交通流预测作为智能交通系统的核心,能够有效解决交通出行和管理方面的问题。现有的短时交通流预测研究往往基于浅层的模型方法,不能充分反映交通流特性。文中针对复杂的交通网络结构,提出了一种基于DCGRU-RF(Diffusion Convolutional Gated Recurrent Unit-Random Forest)模型的短时交通流预测方法。首先,使用DCGRU(Diffusion Convolutional Gated Recurrent Unit)网络刻画交通流时间序列数据中的时空相关性特征;在获取数据中的依赖关系和潜在特征后,选择RF(Random Forest)模型作为预测器,以抽取的特征为基础构建非线性预测模型,得出最终的预测结果。实验以两条城市道路中的38个检测器为实验对象,选取了5周工作日的交通流数据,并将所提方法与其他常见交通流量预测模型进行比较。结果表明,DCGRU-RF模型能够进一步提高预测精度,准确度可达95%。

大数据环境下基于关联规则的多标签学习算法

王青松, 姜富山, 李菲

计算机科学. 2020, 47 (5): 90-95. doi:10.11896/jsjkx.190300150

摘要 ( 495 )

PDF(1446KB) ( 1246 )

参考文献 | 相关文章 | 多维度评价

传统单标签挖掘技术研究中,每个样本只属于一个标签且标签之间两两互斥。而在多标签学习问题中,一个样本可能对应多个标签,并且各标签之间往往具有关联性。目前,标签间关联性研究逐渐成为多标签学习研究的热门问题。首先为适应大数据环境,对传统关联规则挖掘算法Apriori进行并行化改进,提出基于Hadoop的并行化算法Apriori_ING,实现各节点独立完成候选项集的生成、剪枝与支持数统计,充分发挥并行化的优势;通过Apriori_ING算法得到的频繁项集和关联规则生成标签集合,提出基于推理机的标签集合生成算法IETG。然后,将标签集合应用到多标签学习中,提出多标签学习算法FreLP。FreLP利用关联规则生成标签集合,将原始标签集分解为多个子集,再使用LP算法训练分类器。通过实验将FreLP与现有的多标签学习算法进行对比,结果表明在不同评价指标下所提算法可以取得更好的结果。

基于节点演化分阶段优化的事件检测方法

富坤, 仇倩, 赵晓梦, 高金辉

计算机科学. 2020, 47 (5): 96-102. doi:10.11896/jsjkx.190400072

摘要 ( 271 )

PDF(1737KB) ( 701 )

参考文献 | 相关文章 | 多维度评价

链路预测技术是分析网络演化的有效方法,也为社会网络事件检测提供了一种新思路。当前采用链路预测进行事件检测的方法大多是从宏观的网络演化入手,也有少数结合节点演化的检测方法,但其稳定性不佳,对事件的敏感性也不够高,不能准确检测事件的发生。基于以上问题,提出了一种基于节点演化分阶段优化的事件检测方法(Node Evolution Staged Optimization,NESO_ED)。首先通过分阶段优化的方法加强事件检测的稳定性,并获取节点指标权重数组;然后根据不同阶段按不同规则选取节点的最佳相似性计算指标,使节点能更好地量化网络演化情况,以此提高事件检测的敏感性。此外,分析了网络演化过程中节点选取指标的变化情况,揭示了事件发生对节点演化产生的不同影响。基于真实社会网络VAST进行对比实验,结果显示NESO_ED方法在事件检测敏感性上比LinkEvent方法提高了227%,比NodeED方法提高了63%,NESO_ED方法的稳定性也比NodeED方法提高了66%,这表明NESO_ED方法能更加准确且稳定地进行事件检测。

基于多类邻域三支决策模型的不平衡数据分类

向伟, 王新维

计算机科学. 2020, 47 (5): 103-109. doi:10.11896/jsjkx.180601099

摘要 ( 386 )

PDF(1387KB) ( 754 )

参考文献 | 相关文章 | 多维度评价

不平衡数据分类是一种重要的数据分类问题。对于不平衡数据中规模较小的类,传统的分类算法的分类效果较差。对此,提出一种多类邻域三支决策模型的不平衡数据分类算法。首先,将传统的三支决策在混合数据和多个类的情形下进行推广,提出了混合数据的多类邻域三支决策模型;然后,在该模型中给出一种自适应代价函数的设定方法,并基于该方法提出了多类邻域三支决策模型的不平衡数据分类算法。仿真实验的结果表明,所提出的分类算法对于不平衡数据具有更好的分类性能。

语音任务下声学特征提取综述

郑纯军, 王春立, 贾宁

计算机科学. 2020, 47 (5): 110-119. doi:10.11896/jsjkx.190400122

摘要 ( 382 )

PDF(1815KB) ( 3366 )

参考文献 | 相关文章 | 多维度评价

语音是一种重要的信息资源传递与交流方式,人们经常使用语音作为交流信息的媒介,在语音的声学信号中包含大量的说话者信息、语义信息和丰富的情感信息,因此形成了解决语音学任务的3个不同方向,即声纹识别(Speaker Recognition,SR)、语音识别(Auto Speech Recognition,ASR)和情感识别(Speech Emotion Recognition,SER),3个任务均在各自的领域使用不同的技术与特定的方法进行信息提取与模型设计。文中首先综述了3个任务在国内外早期的发展历史路线,将语音任务的发展归纳为4个不同阶段,同时总结了3个语音学任务在特征提取时所采用的公共语音学特征,并针对每类特征的侧重点进行了说明。然后,随着近年来深度学习技术在各个领域中的广泛应用,语音任务也得到了很好的发展,文中针对目前流行的深度学习模型在声学建模中的应用分别进行了分析,按照有监督、无监督的方式总结了针对3种不同语音任务的声学特征提取方式及技术路线,还总结了基于多通道并融合注意力机制的模型,用于语音的特征提取。为了同时完成语音识别、声纹识别和情感识别任务,针对声学信号的个性化特征提出了一个基于多任务的Tandem模型;此外,提出了一个多通道协作网络模型,利用这种设计思路可以提升多任务特征提取的准确度。

弱标签环境下基于多尺度注意力融合的声音识别检测

郑伟哲, 仇鹏, 韦娟

计算机科学. 2020, 47 (5): 120-123. doi:10.11896/jsjkx.190900111

摘要 ( 239 )

PDF(2009KB) ( 825 )

参考文献 | 相关文章 | 多维度评价

目前大多数声音识别检测的研究都是基于强标签数据集的,但在真实环境的声音识别与检测任务中,音频标签不完整并且含有大量噪声,使得获取强标签音频数据比较困难,进而影响对声音的准确识别与检测。为此,在卷积循环神经网络模型的基础上,提出了一种多尺度注意力融合机制。该机制使用注意力门控单元,在降低声音时频图特征中噪声影响的同时,能够更多地利用有效特征。同时,通过结合多个尺寸的卷积核进行特征融合,进一步提升对声音特征的有效提取。此外,采用一种结合帧检测结果的加权法对声音信号进行识别。最后,在弱标签环境下,从AudioSet数据库中选取一个包含17种城市交通工具声音的弱标签数据集进行检测识别,所提模型对测试集声音识别结果的F1值为58.9%,检测结果的F1值为43.7%。结果表明,在弱标签城市交通工具声数据集下,网络模型相比传统的声音识别检测模型具有更高的识别检测精度;同时,重要性加权识别方法、多尺度注意力融合方法均可提升模型对声音识别检测的精度。

基于小样本学习的SAR图像识别

汪航, 陈晓, 田晟兆, 陈端兵

计算机科学. 2020, 47 (5): 124-128. doi:10.11896/jsjkx.190400136

摘要 ( 590 )

PDF(1987KB) ( 1709 )

参考文献 | 相关文章 | 多维度评价

深度学习已成为图像识别领域的一个研究热点。与传统图像识别方法不同,深度学习从大量数据中自动学习特征,并且具有强大的自学习能力和高效的特征表达能力。但在小样本条件下,传统的深度学习方法如卷积神经网络难以学习到有效的特征,造成图像识别的准确率较低。因此,提出一种新的小样本条件下的图像识别算法用于解决SAR图像的分类识别。该算法以卷积神经网络为基础,结合自编码器,形成深度卷积自编码网络结构。首先对图像进行预处理,使用2D Gabor滤波增强图像,在此基础上对模型进行训练,最后构建图像分类模型。该算法设计的网络结构能自动学习并提取小样本图像中的有效特征,进而提高识别准确率。在MSTAR数据集的10类目标分类中,选择训练集数据中10%的样本作为新的训练数据,其余数据为验证数据,并且,测试数据在卷积神经网络中的识别准确率为76.38%,而在提出的卷积自编码结构中的识别准确率达到了88.09%。实验结果表明,提出的算法在小样本图像识别中比卷积神经网络模型更加有效。

空-频域联合投票的交通视频阴影去除方法

宋传鸣, 洪旭, 王相海

计算机科学. 2020, 47 (5): 129-136. doi:10.11896/jsjkx.190400040

摘要 ( 393 )

PDF(3712KB) ( 587 )

参考文献 | 相关文章 | 多维度评价

交通场景中的静止或运动阴影往往会降低车辆目标跟踪的精度,因此有效地去除阴影是交通监控视频处理的重要环节之一。然而,目前尚无一种能够同时发掘阴影的空间域和频率域特性且抵抗静止和运动阴影干扰的阴影去除方法。为此,提出了一种基于空-频域联合投票策略的交通视频阴影去除方法。首先,将视频帧从RGB颜色空间转换到HSV颜色空间,再进行非下采样剪切波变换;其次,假设变换系数服从高斯分布,采用变换系数的均值和标准差计算每个尺度的加权掩码;然后,根据多尺度变换系数的零树分布特性,利用粗尺度的加权掩码校正细尺度的加权掩码,将各个尺度、各个颜色通道的加权掩码进行线性组合后得到一个公共掩码,再采用基于最小二乘法拟合的最大熵方法计算自适应分割阈值,对公共掩码进行二值化;最后,联合频率域加权掩码、S通道和V通道的掩码进行投票,进而确定去除阴影后的运动车辆区域。实验结果表明,该算法可有效去除交通监控视频中的静态/运动阴影,抑制阴影的干扰,将传统Meanshift算法的输出车辆轨迹与真实轨迹间的平均欧氏距离缩小95%,且未出现目标丢失的现象,增强了智能分析算法的鲁棒性。研究结果说明,该算法有效联合交通监控视频的空间域和频率域表示,充分发掘了运动车辆区域与阴影区域之间的纹理特性和颜色特性差异,有利于获得更精确的阴影去除结果,进而提高车辆目标跟踪的精度。

融合极端学习机的判别性分析字典学习算法

王军浩, 闫德勤, 刘德山, 邢钰佳

计算机科学. 2020, 47 (5): 137-143. doi:10.11896/jsjkx.190600090

摘要 ( 403 )

PDF(2512KB) ( 667 )

参考文献 | 相关文章 | 多维度评价

研究表明,端学习机和判别性字典学习算法在图像分类领域极具有高效和准确的优势。然而,这两种方法也具有各自的缺点,极端学习机对噪声的鲁棒性较差,判别性字典学习算法在分类过程中耗时较长。为统一这种互补性以提高分类性能,文中提出了一种融合极端学习机的判别性分析字典学习模型。该模型利用迭代优化算法学习最优的判别性分析字典和极端学习机分类器。为验证所提算法的有效性,利用人脸数据集进行分类。实验结果表明,与目前较为流行的字典学习算法和极端学习机相比,所提算法在分类过程中具有更好的效果。

量化权值激活的生成对抗网络

郑哲, 胡庆浩, 刘青山, 冷聪

计算机科学. 2020, 47 (5): 144-148. doi:10.11896/jsjkx.190700176

摘要 ( 297 )

PDF(2533KB) ( 1008 )

参考文献 | 相关文章 | 多维度评价

近年来,生成对抗网络(Generative Adversarial Networks,GAN)在图像超分辨率、图像生成等许多计算机视觉任务中展现出优异的性能。借助于GPU强大的计算力,人们可以设计计算复杂度更高的GAN网络。然而,对于资源受限的移动端设备,高功耗、计算需求大的GAN将很难被直接部署到实际应用中。得益于神经网络压缩技术取得的巨大进展,将GAN部署到移动端设备成为可能。为此,文中提出一种同时对网络权值和激活进行量化的方案来压缩GAN网络。通过量化敏感性分析发现,与量化分类网络不同,GAN中的量化权重比量化激活更敏感,因此在量化时给予权重更多的量化比特。文中比较了两种评价GAN生成图像的指标即Inception Score(IS)和Fréchet Inception Distance(FID),发现FID更适合评估量化后GAN的性能。基于敏感性分析在Mnist和Celeb-A数据集上进行量化实验,用FID指标来评估量化GAN的性能。实验结果表明:在生成图像质量不下降的情况下,所提方法依然可以取得4倍以上的压缩率,从而有效地解决了GAN的压缩问题。

图像的扩散界面无监督聚类算法

王成章, 白晓明, 杜金栗

计算机科学. 2020, 47 (5): 149-153. doi:10.11896/jsjkx.190300125

摘要 ( 375 )

PDF(2490KB) ( 732 )

参考文献 | 相关文章 | 多维度评价

图像的无监督聚类就是基于图像数据,在无任何先验信息的情况下将整个图像集合划分成若干子集的过程。由于图像的本征维度很高,在图像处理中会遇到“维数灾难”问题。针对图像无监督聚类的特点,提出了一种图像的扩散界面无监督聚类算法,将图像编码成高维观测空间中的点,再通过投影变换映射到低维特征空间,在低维特征空间中构建扩散界面无监督聚类模型,并在模型中引入维度约简算子,采用循环迭代算法优化扩散界面模型的能量函数。基于最优的扩散界面,将整个图像集合聚类成不同的子集。实验结果表明,扩散界面无监督聚类算法优于传统聚类算法中的K-means算法、DBSCAN算法和Spectral Clustering算法,能够更好地实现图像的无监督聚类,在相同条件下具有更高的准确度。

基于WFSOA的2D-Otsu钢轨缺陷图像分割方法

曹义亲, 段也钰, 武丹

计算机科学. 2020, 47 (5): 154-160. doi:10.11896/jsjkx.190200295

摘要 ( 368 )

PDF(2070KB) ( 654 )

参考文献 | 相关文章 | 多维度评价

针对二维最大类间方差阈值法(2D-Otsu)抗噪性较弱、计算时间较长的问题,文中提出了一种基于随机权重及异步价值因子取值的人群搜索算法,并将其应用于2D-Otsu中对钢轨缺陷图像进行分割。该算法采用随机权重加快收敛速度,采用异步价值因子提高搜索能力,有利于全局收敛到最优值。根据测试函数分析,WFSOA算法能够快速收敛,寻优值结果精度高,收敛时间短,算法稳定性好。在钢轨缺陷图像分割中,将2D-Otsu的迹函数作为WFSOA的目标函数,实验结果表明图像检测实时性高,对表面灰度不匀或生锈的钢轨缺陷分割结果清晰,有效降低了钢轨缺陷误检率和漏检率,在计算时间上仅占2D-Otsu算法的2%,可满足实际工程对实时性的需求。

面向陆战场目标识别的轻量级卷积神经网络

乔梦雨, 王鹏, 吴娇, 张宽

计算机科学. 2020, 47 (5): 161-165. doi:10.11896/jsjkx.190300062

摘要 ( 274 )

PDF(2366KB) ( 1331 )

参考文献 | 相关文章 | 多维度评价

在实际陆战场环境中,作战人员无法随身携带GPU等大型计算设备,因此较难计算规模较大的神经网络参数,进而导致目标识别网络无法实时工作。现有的轻量级神经网络虽然解决了实时性的问题,但是不能满足准确率的要求。为此,文中提出了一种基于轻量级卷积神经网络的目标识别算法(E-MobilNet)。为了提升网络学习的效果,以现有深度学习的主要目标检测框架MobileNet-V2为基础,插入一种ELU函数作为激活函数。首先,使用扩张卷积来增加通道数,以获得更多的特征;接着,通过ELU函数激活输出特征,这样可以缓解线性部分的梯度消失,并且使非线性部分对输入变化的噪声更鲁棒;然后,通过残差连接的方式组合高层特征与低层特征的输出;最后,将全局池化的输出结果输入Softmax分类函数。实验数据表明,在同样的测试集和测试环境下,与现在主流的轻量级深度学习目标识别算法相比,E-MobileNet识别的准确率和每秒检测的帧率都有所提升。实验数据充分说明,使用ELU激活函数和全局池化层减少了参数的数量,增强了模型的泛化能力,提升了算法的鲁棒性,在保证神经网络模型轻量级的基础上有效地提高了目标的识别准确率。

基于双注意力编码-解码器架构的视网膜血管分割

李天培, 陈黎

计算机科学. 2020, 47 (5): 166-171. doi:10.11896/jsjkx.190400062

摘要 ( 317 )

PDF(3173KB) ( 1124 )

参考文献 | 相关文章 | 多维度评价

眼底视网膜血管的分割提取对于糖尿病、视网膜病、青光眼等眼科疾病的诊断具有重要的意义。针对视网膜血管图像中的血管难以提取、数据量较少等问题,文中提出了一种结合注意力模块和编码-解码器结构的视网膜血管分割方法。首先对编码-解码器卷积神经网络的每个卷积层添加空间和通道注意力模块,加强模型对图像特征的空间信息和通道信息(如血管的大小、形态和连通性等特点)的利用,从而改善视网膜血管的分割效果。其中,空间注意力模块关注于血管的拓扑结构特性,而通道注意力模块关注于血管像素点的正确分类。此外,在训练过程中采用Dice损失函数解决了视网膜血管图像正负样本不均衡的问题。在3个公开的眼底图像数据库DRIVE,STARE和CHASE_DB1上进行了实验,实验数据表明,所提算法的准确率、灵敏度、特异性和AUC值均优于已有的视网膜血管分割方法,其AUC值分别为0.9889,0.9812和0.9831。实验证明,所提算法能够有效提取健康视网膜图像和病变视网膜图像中的血管网络,能够较好地分割细小血管。

基于狄利克雷过程混合模型的内外先验融合

张墨华, 彭建华

计算机科学. 2020, 47 (5): 172-180. doi:10.11896/jsjkx.190400060

摘要 ( 235 )

PDF(3164KB) ( 841 )

参考文献 | 相关文章 | 多维度评价

近年来,使用高斯混合模型作为块先验的贝叶斯方法取得了优秀的图像复原性能,针对这类模型分量固定及主要依赖外部学习的缺点,提出了一种新的基于狄利克雷过程混合模型的图像先验模型。该模型从干净图像数据库中学习外部通用先验,从退化图像中学习内部先验,借助模型中统计量的可累加性自然实现内外部先验融合。通过聚类的新增及归并机制,模型的复杂度随着数据的增大或缩小而自适应地变化,可以学习到可解释及紧凑的模型。为了求解所有隐变量的变分后验分布,提出了一种结合新增及归并机制的批次更新可扩展变分算法,解决了传统坐标上升算法在大数据集下效率较低、容易陷入局部最优解的问题。在图像去噪及填充实验中,相比传统方法,所提模型无论在客观质量评价还是视觉观感上都更有优势,验证了该模型的有效性。

自动驾驶出租车调度系统研究综述

曾伟良, 吴淼森, 孙为军, 谢胜利

计算机科学. 2020, 47 (5): 181-189. doi:10.11896/jsjkx.190400031

摘要 ( 549 )

PDF(1930KB) ( 1262 )

参考文献 | 相关文章 | 多维度评价

人工智能和大数据科学的发展带来了新一代产业革命。基于人工智能、大数据、车联网等技术的自动驾驶出租车调度系统将成为下一代交通系统的重要组成部分。文中从车联网环境下的自动驾驶调度系统的数学建模问题和系统构建两个方面对现有的文献进行了梳理和讨论。针对乘客出行需求的动态不确定性的共享问题,着重讨论了自动驾驶出租车在不同路径共享模式下的路径规划,以及共享合乘定价和智能调度系统构建的关键技术。最后,总结了自动驾驶出租车在解决交通拥堵和减少资源浪费方面的优势,并指出了自动驾驶出租车系统的技术难点和发展趋势。

基于特征可视化分析深度神经网络的内部表征

尚骏远, 杨乐涵, 何琨

计算机科学. 2020, 47 (5): 190-197. doi:10.11896/jsjkx.190700128

摘要 ( 468 )

PDF(3369KB) ( 1312 )

参考文献 | 相关文章 | 多维度评价

基于可视化的方式理解深度神经网络能直观地揭示其工作机理,即提供了黑盒模型做出决策的解释,在医疗诊断、自动驾驶等领域尤其重要。大部分现有工作均基于激活值最大化框架,即选定待观测神经元,通过优化输入值(如隐藏层特征图谱、原始图片),定性地将待观测神经元产生最大激活值时输入值的改变作为一种解释。然而,这种方法缺乏对深度神经网络深入的定量分析。文中提出了结构可视化和基于规则可视化两种可视化的元方法。结构可视化从浅至深依层可视化,发现浅层神经元具有一般性的全局特征,而深层神经元更针对细节特征。基于规则可视化包括交集与差集规则,可以帮助发现共享神经元与抑制神经元的存在,它们分别学习了不同类别的共有特征与抑制不相关的特征。实验针对代表性卷积网络VGG和残差网络ResNet在ImageNet和微软COCO数据集上进行了分析。通过量化分析发现,ResNet和VGG均有很高的稀疏性,通过屏蔽一些低激活值的“噪音”神经元,发现其对深度神经网络分类准确率均没有影响,甚至有一定程度的提高作用。文中通过可视化和量化分析深度神经网络的隐藏层特征,揭示其内部特征表达,从而为高性能深度神经网络的设计提供指导和借鉴。

面向机器阅读理解的候选句抽取算法

郭鑫, 张庚, 陈千, 王素格

计算机科学. 2020, 47 (5): 198-203. doi:10.11896/jsjkx.190300154

摘要 ( 419 )

PDF(2075KB) ( 800 )

参考文献 | 相关文章 | 多维度评价

使机器理解人类自然语言是人工智能在认知领域的终极目标,机器阅读理解是自然语言处理技术中继语音识别、语义理解之后的一大挑战,要求计算机具有一定的背景常识,全面理解给定文本材料,并根据材料内容对相应的问题作答。随着深度学习的快速发展,阅读理解成为当前人工智能的热点研究方向,涉及机器学习、信息检索、语义计算等核心技术,在聊天机器人、问答系统、智能化教育等多个领域具有广泛的应用前景。文中聚焦微阅读模式,根据问题或选项从给定文本材料中抽取包含答案的候选句,缩小推理范围,为进一步实现机器阅读理解提供技术支持。传统基于特征的方法耗费大量人力,文中将答案候选句抽取看成一种语义相关度计算问题,提出了一种答案候选句排序方法,即Att-BiGRU/BiLSTM模型。首先,利用双向长短期记忆和门控循环单元来编码句子中表达的语义信息;其次,设计Atten结构,结合相异性和相似性对语义相关度进行建模;最后,采用Adam算法来学习模型的参数。在SemEval-SICK数据集上的实验结果显示,该模型在测试集上的pearson指标超过了基线方法BiGRU将近0.67,在MSE指标上超过BiGRU方法16.83%,收敛速度更快,表明双向和Atten结构能大大提高候选句抽取的精度。

自动化立体仓库货位分配与作业调度集成优化

汤洪涛, 闫伟杰, 陈青丰, 鲁建厦, 詹燕

计算机科学. 2020, 47 (5): 204-211. doi:10.11896/jsjkx.190400042

摘要 ( 393 )

PDF(3329KB) ( 1610 )

参考文献 | 相关文章 | 多维度评价

针对动态提高单载具堆垛机式自动化立体仓库拣选效率的问题,文中提出了一种基于共享货位存储与动态订单拣选策略下的货位分配与作业调度集成优化方法。将动态移库优化扩展到仓库的整个拣选生命周期,建立以双指令循环下堆垛机拣选任务所需的总作业时间最短为评价目标的数学模型,提出了一种基于K-Medoids聚类的粒子群优化(Particle Swarm Optimization,PSO)算法,用K-Medoids算法通过产品与订单的相关性进行初始货位的聚类分析,筛除劣质解的货位范围,并在K-Medoids聚类算法生成的解类簇基础上获得精确解。实验结果表明,考虑动态移库可以使仓库拣选效率提高20%,且该算法与传统PSO算法相比求解时间下降66%左右。

带有一刀切约束的二维非规则装箱算法

张旭, 王莉莉, 杨博韬

计算机科学. 2020, 47 (5): 212-216. doi:10.11896/jsjkx.190400078

摘要 ( 382 )

PDF(2011KB) ( 1085 )

参考文献 | 相关文章 | 多维度评价

针对切割下料领域的二维非规则一刀切装箱问题,首先给出了最小移动距离的定义,然后给出了一种基于最大移动距离的启发式算法。该算法通过计算一个凸多边形滑动至另一个凸多边形内部所允许的最大移动距离,对待排件的摆放位置进行一次性定位,避免使用传统的NFP(Not-Fit-Polygon)预判交方法,极大地缩短了排样的整体时间,最后使用模拟退火算法对下料流程进行了优化,改善了排样结果。

信息共享模型和组外贪心策略的郊狼优化算法

张新明, 李双倩, 刘艳, 毛文涛, 刘尚旺, 刘国奇

计算机科学. 2020, 47 (5): 217-224. doi:10.11896/jsjkx.190400039

摘要 ( 380 )

PDF(2104KB) ( 709 )

参考文献 | 相关文章 | 多维度评价

郊狼优化算法(Coyote Optimization Algorithm,COA)是最近提出的一种新颖群智能优化算法,具有较大的应用潜力,但存在运行时间长和搜索能力不足等问题。因此,文中提出了一种改进的COA,即基于信息共享和组外(静态)贪心的COA(COA based on Information sharing and Static greed selection,ISCOA)。首先,构建一种新型的信息共享模型,用于子群所有郊狼的成长,在郊狼成长前期,共享信息差异性大,以增加种群的多样性,在效狼成长后期,共享信息差异性小,以强化开采能力;其次,构建一种新的组内成长方式,即前期主要采用信息共享模型的成长方式,以郊狼的信息共享为主强化探索能力,后期主要采用原算法的成长方式,以alpha狼和文化趋势的引导为主强化开采能力;最后,将原算法的组内贪心算法改成组外贪心算法,即静态贪心算法,以便提高算法的稳定性和实现目标函数计算等的并行处理,提高运行速度。大量复杂的CEC2017函数优化实验结果表明,与COA相比,ISCOA在29个10维和30维函数上分别获得了23和24个函数的优势,其平均运行时间分别是COA的86.3%和85.7%,降低了运行时间;与7个最先进的算法相比,ISCOA在10维和30维函数上的平均排名分别是1.48和1.69,分别获得了17和18个第一,具有更好的优化效果。运用于实际工程问题的实验结果表明,ISCOA得到了最好的结果,证明了ISCOA有更强的搜索能力和竞争性以及更好的应用前景。

基于单通道脑电信号的疲劳检测系统

王博石, 吴修诚, 胡馨艺, 张莉

计算机科学. 2020, 47 (5): 225-229. doi:10.11896/jsjkx.190400127

摘要 ( 280 )

PDF(2364KB) ( 1901 )

参考文献 | 相关文章 | 多维度评价

针对目前高强度劳动人群频繁猝死的情况,文中设计了一套基于单通道脑电信号(Electroencephalography,EEG)的疲劳检测系统,以实现对该类人群疲劳程度的准确判定,起到预警效果。系统利用TGAM(ThinkGearm AM)脑电模块采集原始EEG数据,通过蓝牙方式将数据传送至上位机,在上位机中提取EEG的4个基本节律成分(δ,θ,α,β),以节律信号的相对频带能量作为表征疲劳状态的脑电特征,并利用Fisher判别分析(Fisher Discriminant Analysis,FDA)和概率神经网络(Probabilistic Neural Network,PNN)两种方法对脑电特征进行分类,给出评估结果。实验结果表明,所设计的基于单通道EEG的疲劳检测系统能够实现准确率较高的疲劳状态检测。

车联网络通过两级量化自适应卡尔曼滤波实现车辆状态预测

冯安琪, 钱丽萍, 欧阳金源, 吴远

计算机科学. 2020, 47 (5): 230-235. doi:10.11896/jsjkx.190300155

摘要 ( 478 )

PDF(2808KB) ( 631 )

参考文献 | 相关文章 | 多维度评价

随着城市化和机动化的快速发展,交通安全越来越受到人们的关注。利用车载网络系统获取车载数据来预测车辆下一时刻的车载状态,对于提高运输路段的交通安全起着重要作用。文中提出一种基于自回归滑动平均(Auto-Regressice Mo-ving Average,ARMA)模型的两级量化自适应卡尔曼滤波算法,来预测车辆的行车状态(行驶的方向、行驶的车道、车辆的速度和加速度)。首先,开发了一个车载网络系统,通过交换车载单元(On-Board Unit,OBU)和路边单元(Roadside Unit,RSU)之间的交通数据来获取车辆数据;然后,通过配置在路边单元的边缘云服务器来预测车辆状态;最后,边缘服务器把预测到的状态信息广播给其他路边单元,以便交叉口其他车辆获取车辆信息。实验结果验证了用于预测加速度的自回归移动平均模型的有效性。此外,文中还评估了所提算法的有效性。与其他3种预测算法相比,所提算法的速度预测精度分别提高了90.62%,89.81%,82.76%,这说明该算法在车载网络中能有效预测车辆状态。

面向光伏MPPT控制策略的改进果蝇算法

付子义, 程冰, 邵路路

计算机科学. 2020, 47 (5): 236-241. doi:10.11896/jsjkx.190400096

摘要 ( 390 )

PDF(2359KB) ( 679 )

参考文献 | 相关文章 | 多维度评价

局部遮光会降低光伏发电系统的效率。在局部遮光条件下,光伏系统的输出功率特性曲线会产生多个峰值,传统的最大功率跟踪方法不具有全局搜索的能力,其在进行多峰值最大功率跟踪时会失效。果蝇算法(Fruit Fly Optimization Algorithm,FOA)具有全局寻优能力,但是在求解过程中存在收敛速度慢、收敛精度低及容易收敛于局部最优值的问题。文中对果蝇算法进行改进,提出结合自适应lévy飞行步长的Lévy-FOA算法,该算法充分利用Lévy飞行不均匀随机游走的特性,引入自适应步长调整因子,改进了原有算法的位置更新方式,提高了算法的收敛速度以及收敛精度,避免了算法陷入局部极值。文中利用3个标准函数对自适应Lévy-FOA算法的收敛性进行分析,并与普通FOA算法、自适应改进学习因子粒子群算法(Adaptive Particle Swarm Optimization,APSO)进行对比。结果表明,与FOA算法和APSO算法相比,自适应Lévy-FOA算法的平均跟踪时间有较大幅度的减少,平均收敛精度提高了4个数量级。最后,将自适应Lévy-FOA算法应用于光伏最大功率跟踪中。仿真结果显示,在不同的光照条件下,自适应Lévy-FOA算法能够经过较少的迭代实现最大功率跟踪,并且在第一次迭代后就能达到最大功率的90%以上,与其他算法的跟踪效果对比,自适应Lévy-FOA算法具有较短的跟踪时间和较高的跟踪精度,实际寻优能力优越,能够提高光伏系统的输出效率。

广域复杂流体系统中基于无线传感网的数据保存关键技术研究进展

张婕, 梁俊斌, 蒋婵

计算机科学. 2020, 47 (5): 242-249. doi:10.11896/jsjkx.190400025

摘要 ( 428 )

PDF(2238KB) ( 672 )

参考文献 | 相关文章 | 多维度评价

流体系统包括城市供水管网、天然气供给管网等,是具有经济和社会价值的重要基础设施。它们具有分布地域广、结构复杂、规模庞大、难以检测等特点,在出现泄漏、污染等异常时难以快速发现和准确定位。随着传感器技术、通信技术、微机电技术等的发展,利用无线传感网来对系统进行监测成为研究热点。由于在流体系统中通信困难,数据被监测到后很难实时传送给用户,只能暂时保存在传感器节点(简称节点)上,等待适当的时刻再进行上传。但是,节点具有体积微小、易损坏、存储容量小、通信能力弱、能量有限等特点,如何可靠地存储大量的数据是一个难点问题。目前,已有部分工作对这个问题进行了研究。为了解该领域研究的进展,文中对相关工作进行了细致地分析、对比、归纳和总结,介绍了它们的优缺点,并对未来的研究方向进行了探讨。

一种基于物理-社交感知和支付激励的D2D多播内容共享策略

富勤学, 敖亮, 杨莲新, 吴岩

计算机科学. 2020, 47 (5): 250-259. doi:10.11896/jsjkx.190400143

摘要 ( 335 )

PDF(2416KB) ( 618 )

参考文献 | 相关文章 | 多维度评价

面向大规模用户的多媒体业务尤其是在线视频业务正呈现爆炸式发展的态势,D2D(Device-to-Device)多播内容共享技术被认为是一种可以有效应对大规模用户海量数据分发的关键技术。但目前关于D2D多播内容共享的研究多集中在如何提高系统的能量有效性上,对于系统数据速率和的研究不多,而系统数据速率和是反映系统能否高效分发内容的一个重要指标。为了建立一个贴近实际场景的用户模型并实现高效内容分发以减轻基站负担并提高资源(频谱和能量)利用效率,文中提出一种基于物理-社交感知和支付激励的D2D多播内容共享策略。首先,根据实际场景的限制对D2D多播通信进行建模,把模型的应用场景扩大到人流集中的高速内容共享的“热点”地区和不利于基站直接传输数据(如抗震救灾时)的大规模搜救行动的“盲点”地区。随后,以有效降低基站负载和应对海量数据分发为目标,提出以多约束条件下系统等效数据速率和为目标函数的优化问题,通过引入支付机制激励用户作为簇头为其他用户提供共享内容,通过引入基于兴趣相似度的社交关系来提高资源利用效率并降低用户支付代价。最后,提出簇头选择-簇形成算法来求解上述问题。在簇头选择算法中,在考虑用户数据速率阈值限制的同时,引入基于用户兴趣相似度的社交关系;在簇形成算法中,采用了一种增益定义与“联盟”内涵高度契合的集中控制式的联盟形成博弈模型。仿真结果表明,与相关同类策略相比,所提策略在等效数据速率和与实际数据速率和两项指标上的性能得到了显著提高,同时证明了该策略适合大规模用户的网络。

面向无线传感网络应用的改进LZW算法

倪晓军, 佘戌豪

计算机科学. 2020, 47 (5): 260-264. doi:10.11896/jsjkx.190400108

摘要 ( 368 )

PDF(1550KB) ( 677 )

参考文献 | 相关文章 | 多维度评价

在无线传感网络通信中,传感器数据需要通过无线设备发送给上位机。随着终端传感器传输数据量的增大,无线设备的发送能耗逐渐加大。在不便于及时维护的复杂环境中,这将导致无线通讯设备过早失效从而使得通讯中断。因此需要先将传感器采集到的数据进行压缩,减小发送数据量。在分析传感器数据特点和传统的LZW(Lempel-Ziv-Welch)压缩算法的基础上,提出了一种面向无线传感网络应用的改进LZW算法。该算法首先对采集到的传感器相邻数据进行差值预处理,以提高数据项的重复率;然后选择大小合适的字典,在字典上用哈希存储的方式代替传统的顺序存储,以改进字典更新方式,当检测到压缩率降低时更新字典,并保存常用单字符,释放字典空间,达到数据压缩的目的。实验数据显示,与传统的LZW算法相比,改进的LZW算法使得有序传感器数据的压缩率最高降低40%,减小了所需发送数据的数据量,压缩速度也提高了近10倍,证明了面向无线传感网络应用的改进LZW算法是有效可行的。

一种基于加权网络拓扑权重的链路预测方法

袁榕, 宋玉蓉, 孟繁荣

计算机科学. 2020, 47 (5): 265-270. doi:10.11896/jsjkx.190600031

摘要 ( 402 )

PDF(2214KB) ( 1112 )

参考文献 | 相关文章 | 多维度评价

近年来,复杂网络中的链路预测问题受到越来越多的关注,链路预测的应用场景也越来越广泛,因此如何提高链路预测精度是一个重要问题。目前已提出了很多方法,其中加权相似性指标的预测方法取得了很好的效果。然而传统的加权网络链路预测方法仅考虑了链接的自然权重,忽略了链接的拓扑权重对预测精度的影响。因此,针对加权网络的链路预测,综合考虑网络中边的聚类和扩散特性并将其作为边的拓扑权重,提出了基于链接拓扑权重的WCD含权预测指标,包括WCD-CN,WCD-AA,WCD-RA和WCD-LP4个相似性指标。文中以Matlab为实验平台,在两个带权数据集(USAir,Bibble)和两个无权数据集(Pblogs,Dolphins)上进行实验,并以AUC作为评价指标。仿真结果表明,与基于自然权重的含权指标、基于簇系数的结构含权指标相比,所提算法具有更好的预测精度。

基于原子范数最小化的二维稀疏阵列波达角估计算法

卢爱红, 郭艳, 李宁, 王萌, 刘杰

计算机科学. 2020, 47 (5): 271-276. doi:10.11896/jsjkx.191200139

摘要 ( 309 )

PDF(2074KB) ( 1328 )

参考文献 | 相关文章 | 多维度评价

基于二维稀疏平面阵列的波达角(Direction-of-arrival,DOA)估计问题在第五代移动通信大规模多输入多输出阵列的应用中日益重要。无网格稀疏重构技术促进了DOA估计问题的发展,原子范数理论则使得DOA估计的超分辨率得到进一步的提高。文中研究了多个方向的频谱稀疏信号入射到二维稀疏阵列时的DOA估计问题。为了准确、成对地识别出所有入射信号的仰角和方向角,提出了一种基于多个测量矢量(Multiple Measurement Vectors,MMV)的二维原子范数算法,并用半正定规划进行求解。所提算法将二维DOA估计问题中的压缩感知理论从单个测量矢量拓展到多个测量矢量,从而有效利用MMV的联合稀疏性。数值仿真结果表明,随着MMV矢量的增长,可识别的信源个数增加,稀疏阵列中物理传感器所占比例降低到30%,DOA估计误差也显著降低,并且在信噪比增大时,所提算法能够取得很好的收敛效果。

面向边缘计算的Storm边缘节点调度优化方法

简琤峰, 平靖, 张美玉

计算机科学. 2020, 47 (5): 277-283. doi:10.11896/jsjkx.190600048

摘要 ( 264 )

PDF(1167KB) ( 1317 )

参考文献 | 相关文章 | 多维度评价

边缘计算有高实时性和大数据交互处理的需求,边缘异构节点间的调度时耗长、通信时延高以及负载不均衡是影响边缘计算性能的核心问题,传统的云计算平台难以满足新的要求。文中研究了在边缘计算环境下Storm边缘节点的调度优化方法,建立了面向边缘计算的Storm任务卸载调度模型。针对拓扑任务在边缘异构节点间的实时动态分配问题,提出了一种启发式动态规划算法(Inspire Dynamic Programming,IDP),通过改变Storm的Task实例的排序分配方式以及Task实例和Slot任务槽的映射关系实现全局的优化调度;同时,针对拓扑任务的并发度受限于JVM栈深度的缺陷,提出了一种基于蝙蝠算法的调度策略。实验结果表明,与Storm调度算法相比,所提算法在边缘节点CPU利用率指标上平均提升了约60%,在集群的吞吐量指标上平均提升了约8.2%,因此能够满足边缘节点之间的高实时性处理要求。

面向SysML的系统安全性分析工具与实例研究

唐红英, 胡军, 陈朔, 石梦烨

计算机科学. 2020, 47 (5): 284-294. doi:10.11896/jsjkx.190600169

摘要 ( 303 )

PDF(4679KB) ( 1282 )

参考文献 | 相关文章 | 多维度评价

基于模型的安全性分析方法能够提高对目前复杂安全关键系统的建模与分析能力。系统建模语言(System Modeling Language,SysML)是一类在工业领域被广泛应用的非形式化系统功能建模语言,AltaRica是面向系统安全性分析的形式化建模语言。针对国内目前缺乏面向SysML的系统安全性分析工具的现状,设计实现了一个面向SysML的系统安全性分析工具并进行了实例研究。首先建立了SysML设计模型到AltaRica分析模型的映射规则;同时根据映射规则设计算法实现两种模型的自动转换,并集成了Altarica的分析引擎对系统模型进行自动化安全性分析;最后以SAE-AIR6110标准中的一个复杂的机轮刹车系统(Wheel Brake System,WBS)为实例,验证了所提工具的可行性和有效性。实验结果表明,对于包含25个组件类型、34个组件实例的复杂系统,该工具可有效地完成SysML模型到AltaRica模型的转换并进行正确的安全性分析。

基于BiLSTM模型的漏洞检测

龚扣林, 周宇, 丁笠, 王永超

计算机科学. 2020, 47 (5): 295-300. doi:10.11896/jsjkx.190800046

摘要 ( 426 )

PDF(1809KB) ( 1210 )

参考文献 | 相关文章 | 多维度评价

随着计算机技术应用的不断深化,软件的数量和需求不断增加,开发难度不断升级。代码复用以及代码本身的复杂度,使得软件中不可避免地引入了大量漏洞。这些漏洞隐藏在海量代码中很难被发现,但一旦被人利用,将导致不可挽回的经济损失。为了及时发现软件漏洞,首先从源代码中提取方法体,形成方法集;为方法集中的每个方法构建抽象语法树,借助抽象语法树抽取方法中的语句,形成语句集;替换语句集中程序员自定义的变量名、方法名及字符串,并为每条语句分配一个独立的节点编号,形成节点集。其次,运用数据流和控制流分析提取节点间的数据依赖和控制依赖关系。然后,将从方法体中提取的节点集、节点间的数据依赖关系以及控制依赖关系组合成方法对应的特征表示,并运用one-hot编码进一步将其处理为特征矩阵。最后,为每个矩阵贴上是否含有漏洞的标签以生成训练样本,并利用神经网络训练出相应的漏洞分类模型。为了更好地学习序列的上下文信息,选取了双向长短时记忆网络(Bidirectional Long Short-Term Memory Networks,BiLSTM)神经网络,并在其上增加了Attention层,以进一步提升模型性能。实验中,漏洞检测结果的精确率和召回率分别达到了95.3%和93.5%,证实了所提方法能够较为准确地检测到代码中的安全漏洞。

VANET中基于RSU辅助签名环形成的方案

张浩, 蔡英, 夏红科

计算机科学. 2020, 47 (5): 301-305. doi:10.11896/jsjkx.190400119

摘要 ( 439 )

PDF(2161KB) ( 824 )

参考文献 | 相关文章 | 多维度评价

车辆自组织网络(Vehicular Ad-hoc Network,VANET)使交通系统更加智能和高效。信道的开放性以及车辆移动的高速性等特点,导致VANET存在诸如身份、传输数据以及位置等隐私信息泄露问题。目前,针对VANET的身份隐私泄露问题,越来越多的学者采用基于环签名的方案,但是车辆如何在行驶过程中与周围车辆组成签名环一直是一个难解决的问题。针对基础设施部署较完善地区,文中提出一种基于RSU(Road-Side Unit)辅助签名环形成的方案。该方案通过RSU收集覆盖区域内车辆的公钥并广播公钥集,从而确定区域内车辆的签名环,并利用双线性对映射实现RSU与车辆间消息传输的基于身份加密的过程。安全分析和实验证明,所提方案在基础设施较完善地区能够拥有较好的效率和安全性。

基于遗传算法的网络安全配置自动生成框架

白玮, 潘志松, 夏士明, 成昂轩

计算机科学. 2020, 47 (5): 306-312. doi:10.11896/jsjkx.190500038

摘要 ( 330 )

PDF(2083KB) ( 805 )

参考文献 | 相关文章 | 多维度评价

合理配置网络安全设备以对信息系统实施必要的访问控制,是网络安全管理的一项重要任务。随着网络规模的不断扩大,各种用户权限之间会形成复杂的依赖关系,传统基于人工的方式配置网络访问控制策略,主要是依据业务系统的实际需求,按照最小权限的原则进行分配,这种分配方式忽略了权限之间的依赖关系,容易产生过授权的现象,从而为网络带来安全隐患。为解决该问题,提出了一个基于遗传算法的安全配置自动生成框架。首先,以网络规划信息和配置信息为基础,确定用户可能的权限,提取网络基础语义,构建相应的网络安全风险评估模型,实现不同安全配置的安全评估;然后,对网络中所有可能的安全配置进行合理编码,确定遗传算子和算法参数,生成初始种群;最后,通过遗传算法,自动选取较优个体来生成子代个体。该框架能够通过自动比较不同的安全配置下的网络安全风险,以及在可能的配置空间内自动搜索安全配置的最优解,来实现网络安全设备访问控制策略的自动生成。构造一个拥有20个设备、30个服务的模拟网络环境对该框架进行验证,在该模拟环境下,该框架能够在种群样本数目为150的条件下,不超过10次迭代即可找到较优的安全配置。实验结果充分表明,该框架能够根据网络的安全需求,自动生成合理的网络安全配置。

可抵御内部威胁的角色动态调整算法

潘恒, 李景峰, 马君虎

计算机科学. 2020, 47 (5): 313-318. doi:10.11896/jsjkx.190800051

摘要 ( 302 )

PDF(1438KB) ( 658 )

参考文献 | 相关文章 | 多维度评价

业务流程、信息基础设施等的变化会造成当前角色定义出现偏差,使得组织易遭受内部威胁。基于定时、合理改变组织内部角色集合的防御思路,提出了一种角色动态调整算法(Role Dynamic Ajusting,RDA)。该算法定义了带有调整参数的目标函数,以平衡考虑用户权限实际使用数据以及系统管理员专家知识;基于启发式搜索策略和子集结对操作得到一组候选角色;使用启发式函数计算角色分值,按照角色分值的高低对候选角色集进行删选,得到符合角色质量要求的调整角色集;以降低角色冗余度为目标,使用调整角色集为系统用户重新分配角色,得到新的系统角色配置。基于某医院管理系统日志的实验结果表明,RDA算法可有效调节目标组织系统的角色集,为抵御内部威胁打下良好基础。