计算机科学

第50卷第6期目录

计算机科学. 2023, 50 (6): 0-0.

摘要 ( 240 )

PDF(280KB) ( 421 )

相关文章 | 多维度评价

第一性原理极化率计算中的众核优化方法研究

罗海文, 吴扬俊, 商红慧

计算机科学. 2023, 50 (6): 1-9. doi:10.11896/jsjkx.220700162

摘要 ( 464 )

PDF(3054KB) ( 4188 )

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

基于量子力学的密度泛函微扰理论(DFPT)可以用来计算分子和材料的多种物理化学性质,目前被广泛应用于新材料等领域的研究中;同时,异构众核处理器架构逐渐成为超算的主流。因此,针对异构众核处理器重新设计和优化DFPT程序以提升其计算效率,对物理化学性质的计算及其科学应用具有重要意义。文中对DFPT中一阶响应密度和一阶响应哈密顿矩阵的计算针对众核处理器体系结构进行了优化,并在新一代神威处理器上进行了验证。优化技术包括循环分块、离散访存处理和协同规约。其中,循环分块对任务进行划分从而由众核并行地执行;离散访存处理将离散访存转换为更高效的连续访存;协同规约解决了写冲突问题。实验结果表明,在一个核组上,优化后的程序性能较优化前提高了8.2～74.4倍,并且具有良好的强可扩展性和弱可扩展性。

基于混合内存的Apache Spark缓存系统实现与优化

魏森, 周浩然, 胡创, 程大钊

计算机科学. 2023, 50 (6): 10-21. doi:10.11896/jsjkx.220900261

摘要 ( 381 )

PDF(3181KB) ( 3984 )

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

随着大数据时代数据规模的激增,内存计算框架得到了长足发展。主流内存计算框架Apache Spark使用内存来缓存中间结果,大幅度地提升了数据处理速度。同时,具有较快的读写速度和较大容量的非易失性存储器NVM在内存计算领域展现出了巨大的发展前景,使用DRAM和NVM构建Spark混合缓存系统成为一种可行方案。文中提出了一种基于DRAM-NVM混合内存的Spark缓存系统,该系统选择平面混合缓存模型作为设计方案,然后为缓存块管理系统设计了专用的数据结构,并提出了适用于Spark的混合缓存系统整体设计架构。另外,为了将频繁访问的缓存块保存在DRAM缓存中,提出了基于缓存块最小重用代价的混合缓存管理策略。首先从DAG信息中获取RDD的未来重用次数,未来重用次数多的缓存块将被优先保存在DRAM缓存中,并在缓存块迁移时考虑了迁移成本。设计实验表明,DRAM-NVM混合缓存相比原有缓存系统的性能平均提升了53.06%,对于相同的混合内存,所提策略相比默认缓存策略有平均35.09%的提升。同时,使用文中设计的混合系统只需要1/4的DRAM和3/4的NVM作为缓存,就能达到全部DRAM缓存约79％的性能表现。

基于多核CPU的DVB-RCS2并行Turbo译码方法

翟绪论, 张永光, 靳安钊, 强薇, 李梦冰

计算机科学. 2023, 50 (6): 22-28. doi:10.11896/jsjkx.230300005

摘要 ( 249 )

PDF(2813KB) ( 3929 )

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

DVB-RCS2在卫星广播、海事卫星通信、军事卫星通信等领域有着广泛应用,而无论是通信还是军事侦察都需要大吞吐量高速译码。多核CPU算力不断提升以及软件无线电SDR平台的广泛应用,使得基于多核CPU的并行译码成为一种灵活高效的应用方式。为了满足其中双二元Turbo码大吞吐量软件译码的需求,提出了一种基于多核CPU的高速并行软件译码方案。首先对比分析了双二元Turbo码与传统二进制Turbo码的计算复杂度;然后重点对并行计算过程中的内存占用和采用8比特位宽整型数据时的输入量化方法进行了分析和优化,设计了基于多核CPU并行译码的实现方案;最后在Intel 12核CPU上使用SSE并行指令集实现了大于169 Mbps的译码吞吐率,且纠错性能较浮点运算损失小于0.1 dB。通过与现有GPU译码方案对比,说明了所提方案在译码效率和能耗方面的优势,其在高速卫星接收机中具有极高的应用价值。

基于多核CPU的无锁并行Semi-naive算法

喻婷, 王立松, 秦小麟

计算机科学. 2023, 50 (6): 29-35. doi:10.11896/jsjkx.220800050

摘要 ( 244 )

PDF(2488KB) ( 3821 )

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

Datalog系统被广泛应用于很多领域,如图数据库、网络和静态程序分析等。在处理海量数据时,基于串行的Datalog求解策略无法充分发挥现有多核处理器的计算性能。针对上述问题,提出一种基于多核CPU的无锁并行Semi-naive算法(Parallel Semi-naive,PSN)用于支持Datalog的高效求解。PSN使用B⁺树索引进行数据划分,将数据分配给不同的线程执行计算,每个分区产生的中间结果元组互不相同,有利于实现计算时无锁的并行。同时提出一种双层哈希表结构来索引中间结果以提高查重的效率,每个线程只在特定的区域执行相关的计算,无需使用锁来防止写冲突。PSN使用任务队列-线程池为空闲线程分配任务,来实现多线程的负载均衡。在KONECT(Koblenz Network Collection)及斯坦福SNAP(Stanford Network Analysis Platform)的公开数据集上的实验结果表明,PSN算法可以优化Datalog规则的查询性能。

基于决策树和由均匀分布改进Q学习的虚拟机整合算法

师亮, 温亮明, 雷声, 黎建辉

计算机科学. 2023, 50 (6): 36-44. doi:10.11896/jsjkx.220300192

摘要 ( 186 )

PDF(3252KB) ( 3818 )

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

随着云数据中心规模的不断扩大,次优虚拟机整合算法所引起的高能耗、低资源利用率和用户服务质量下降等问题逐渐凸显。为此,提出了一种基于决策树和由均匀分布改进Q学习的虚拟机整合算法(DTQL-UD)。该算法采用决策树实现状态表征,并在评估下一时刻状态-动作价值时采用均匀分布选取下一时刻动作,可直接从云数据中心状态到虚拟机迁移的过程中通过实时反馈来不断优化决策。此外,针对强化学习中模拟器与真实场景中的差异问题,基于大量真实云数据中心负载跟踪数据,使用监督学习模型训练模拟器以增加模拟器的仿真度。仿真实验结果表明,DTQL-UD在能耗、资源利用率、用户服务质量、虚拟机迁移次数和剩余活跃主机数量方面分别优化了14%,12%,21%,40%和10%。同时,得益于决策树在表格型数据上更强的特征提取能力,DTQL-UD相比其他现有的深度强化学习方法可学到更优的整合策略,并且在本实验中随着云数据中心规模的增大,可将传统强化学习模型的训练耗时逐步减少60%～92%。

基于双倍双精度施密特正交化方法的QR分解算法

金洁茜, 谢和虎, 杜配冰, 全哲, 姜浩

计算机科学. 2023, 50 (6): 45-51. doi:10.11896/jsjkx.230200209

摘要 ( 157 )

PDF(1989KB) ( 3813 )

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

当矩阵的规模较大或者条件数较高时,格拉姆-施密特(Gram-Schmidt)正交化算法和其相关修正算法时常表现出数值不稳定性的现象。为了解决该问题,探索了修正Gram-Schmidt算法(MGS)中舍入误差的累积效应,然后基于无误差变换技术和双倍双精度算法,设计并实现了双倍双精度修正Gram-Schmidt正交化算法(DDMGS)。该算法的精度测试中显示所提算法较分块施密特正交化(BMGS_SVL,BMGS_CWY,BCGS_PIP与BCGS_PIO)的变体算法具有更好的数值稳定性,证明了DDMGS算法能够有效地减少矩阵的正交性损失,提升数值精度,展示了所提算法的可靠性。在算法的性能测试中,首先计算并比较了不同算法的浮点计算量(flops),随后将所提DDMGS算法与修正施密特正交化算法在ARM和Intel两款处理器上作比较,虽然DDMGS算法的运行时间分别是MGS的5.03倍和18.06倍左右,但获得了明显的精度提升效果。

ARM处理器上的格点QCD计算与优化

孙玮, 毕玉江, 程耀东

计算机科学. 2023, 50 (6): 52-57. doi:10.11896/jsjkx.230200159

摘要 ( 170 )

PDF(1750KB) ( 3732 )

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

格点量子色动力学(格点QCD)是高能物理领域中需要大规模并行计算的最主要应用之一,相关研究通常需要消耗大量计算资源,核心是求解大规模稀疏线性方程组。文中基于国产鲲鹏920 ARM处理器,研究了格点QCD的计算热点Dslash,并将其扩展到64个节点(6 144核),展示了格点QCD计算的线性扩展性。基于roofline性能分析模型,发现格点QCD是典型的内存限制应用,并通过将Dslash中的3×3复幺正矩阵根据对称性压缩,将其性能提升约22%。对于大规模稀疏线性方程的求解,在ARM处理器上探索了常用的Krylov子空间迭代算法BiCGStab,以及近年来发展起来的前沿的multigrid算法,发现即使考虑预处理时间,在实际物理计算中使用multigrid算法相比BiCGStab依然有几倍至一个数量级的加速。此外,还考虑了鲲鹏920处理器上的NEON向量化指令,发现将其用于multigrid计算时可以带来约20%的加速。因此,在ARM处理器上使用multigrid算法能极大地加速实际的物理研究。

基于国产c86处理器的CP2K软件移植与优化

范黎林, 乔一航, 李俊飞, 柴旭清, 崔容培, 韩秉豫

计算机科学. 2023, 50 (6): 58-65. doi:10.11896/jsjkx.230200213

摘要 ( 203 )

PDF(2603KB) ( 3879 )

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

CP2K是目前运行最快的开源第一性原理材料计算和模拟软件,源码中调用协处理器的部分基于CUDA架构编写。因平台底层硬件架构和编译环境不同,原生的CP2K软件无法调用国产c86处理器平台上的DCU,因此不能实现跨平台应用。为解决该问题,提出了一种CP2K面向该平台的移植方案。该方案的核心思想为:对CP2K软件中主要基于CUDA接口实现的DBCSR库进行代码分析,拆解对应结构体和类的封装方式,并基于HIP的编程标准对其进行实现和封装。在国产c86处理器平台上编译安装HIP版的DBCSR库,链接CP2K软件,最终实现运行DCU版的CP2K软件。后续选取两个测试算例,基于编译级与运行级对其进行优化实验。实验发现,删除CP2K脚本链自动安装的FFTW库可提高计算结果精度。实验结果表明,所使用的优化方法可显著提升CP2K软件的计算效率和计算准确性,为实现开源软件面向国产平台的移植优化和国产化替代做出贡献。

一种面向最佳收益的服务功能链在线编排方法

黄骅, 江俊, 杨永康, 曹斌

计算机科学. 2023, 50 (6): 66-73. doi:10.11896/jsjkx.220400156

摘要 ( 332 )

PDF(3266KB) ( 3705 )

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

随着网络功能虚拟化技术的发展,如何对服务功能链进行灵活编排以实现收益最大化已成为服务提供商关注的核心问题。文中以最大化收益为目标,将多数据中心场景下的服务功能链在线编排问题建模为0-1整数规划,并在此基础上提出了一种两阶段启发式算法。在第一阶段,根据负载情况及部署开销计算节点和链路的权重值,将服务功能链部署在优先级最高的节点上,然后根据链路的负载情况选取满足带宽约束且优先级最高的链路。在第二阶段,类比最长有效功能序列方法,提出了一种虚拟服务迁移策略,以降低部署资源消耗。基于NSFNET和USNET网络拓扑设计了仿真实验,实验结果表明,相比现有算法,所提方法在部署收益和部署成功率两个方面均有一定提升,能够实现服务资源的优化配置,有效提升部署收益。

基于“嵩山”超级计算机系统下HHL算法的模拟实现

谢浩山, 刘晓楠, 赵晨言, 刘正煜

计算机科学. 2023, 50 (6): 74-80. doi:10.11896/jsjkx.220500108

摘要 ( 166 )

PDF(1547KB) ( 3715 )

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

量子计算是一种遵循量子力学规律来调控量子信息单元进行计算的新型计算模式,而量子算法由一系列量子门组合而成,其实现形式为量子线路。量子线路是对量子比特进行操作的线路,以量子比特为基本的存储单元,将量子逻辑门连接在一起来实现特定的计算功能。文中在“嵩山”超级计算机上利用MPI+OpenMP混合并行编程模型,实现了将大规模量子线路拆分到不同节点上进行构建,加快了线路的构建速度,并且在CPU集群系统上具有良好的可拓展性。针对节点间通信问题,设计了序列化和反序列化函数,以保证节点间数据的传输,并且根据各节点所分配任务量间存在的指数级差异,设计了一种拆分任务量、各节点轮循处理的优化方式,实现了节点间的负载均衡。最后在超级计算机CPU集群上成功实现了大规模的量子相位估计线路的构造,相较于单节点取得了8.63的加速比,并通过HHL算法验证了所设计的并行相位估计子模块的正确性,为大规模HHL算法在超算平台上的实现提供了参考。

密度泛函微扰理论中响应密度矩阵的迭代求解算法研究

刘人僪, 徐直前, 商红慧, 张云泉

计算机科学. 2023, 50 (6): 81-85. doi:10.11896/jsjkx.220500252

摘要 ( 135 )

PDF(1498KB) ( 3770 )

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

针对密度泛函微扰理论中响应密度矩阵的计算问题,提出了一种全新的Sternheimer方程的并行求解方法,即通过共轭梯度算法和矩阵直接分解算法对Sternheimer方程进行求解,并且在第一性原理的分子模拟软件FHI-aims中实现了这两种算法。实验结果表明采用共轭梯度算法和矩阵直接分解算法的计算结果精度较高,相比传统方法的计算结果误差较小,且具有可扩展性,验证了新的Sternheimer方程中线性方程求解的正确性和有效性。

深度学习容器云平台下的GPU共享调度系统

王壮, 王平辉, 王彬丞, 武文博, 王斌, 丛鹏宇

计算机科学. 2023, 50 (6): 86-91. doi:10.11896/jsjkx.220900110

摘要 ( 483 )

PDF(1834KB) ( 3906 )

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

近年来,容器由于具有轻量级以及高可扩展性,逐渐替代了虚拟机,被广泛应用于深度学习云平台中。但目前深度学习云平台在GPU资源管理上依然存在着不足,主要表现为由于容器编排技术的限制,多个容器无法共享使用GPU资源,而对于一些小规模模型的训练任务和推理任务,单个任务并不能充分利用整张GPU卡的计算资源。当前的独占模式会导致昂贵的GPU资源的浪费,降低资源效率和服务可用性。针对这一问题,提出了一种GPU共享调度系统。一方面,基于Kubernetes的Operator机制对现有集群功能进行扩展,实现了多个Pod共享使用GPU资源,同时设计了一种代理机制保证了与原生Kubernetes的兼容性。另一方面,基于GPU时间片与抢占机制,实现了GPU资源的动态管理与调度,在多个任务之间进行细粒度的协调,并减少了任务干扰。实验结果表明,与原生Kubernetes调度系统相比,该系统能够将一组深度学习训练任务的完成时间平均减少约20%,使得集群GPU资源利用率平均提升约10%。在共享使用GPU时高优先级任务性能相较于独占GPU损耗不到5%,同时能够使得低优先级任务以20%的性能运行在同一张GPU上。

基于层次聚类的三支决策移动策略

徐怡, 骆帆, 王敏

计算机科学. 2023, 50 (6): 92-99. doi:10.11896/jsjkx.220900037

摘要 ( 147 )

PDF(2731KB) ( 286 )

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

治略是三支决策TAO模型中的一个重要步骤,是实现对象移动的重要手段。通过实施策略,促使对象从不利区域移动到有利区域。近年来,对于治略方面的研究,学者们提出了两种移动策略,一种是基于区域的移动,另一种是基于对象的移动。然而,这两种移动策略都是从单层次的角度分析和制定移动策略,并未从多层次上考虑移动策略的制定。因此,为了制定多个层次上的移动策略,文中引入层次聚类,提出了一种基于层次聚类的三支决策移动策略模型。首先,使用层次聚类,将不利区域中的对象划分成不同的层次,每一层次上的聚类结果不同。然后,根据全局属性值频率最高准则,为每个层次中的簇制定一个移动策略,不同的簇有不同的移动策略。此外,文中还利用移动过程中产生的收益和代价,对不同层次上的移动策略进行评估。最后,实验结果证明了所提模型的有效性。

基于局部半径的三支DBSCAN算法

申秋萍, 张清华, 高满, 代永杨

计算机科学. 2023, 50 (6): 100-108. doi:10.11896/jsjkx.220800074

摘要 ( 378 )

PDF(5819KB) ( 259 )

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

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一种经典的基于密度的聚类算法,它通过两个全局参数即半径Eps和最少点数MinPts,能够对任意形状的数据进行聚类,并自动确定类个数。但是,使用全局半径的DBSCAN对于密度不均匀数据集的聚类效果较差,且无法对重叠数据集进行聚类。因此,定义了密度递减原则和局部半径,并根据k-近邻距离自动确定局部半径,从而提出了基于局部半径的DBSCAN算法(LE-DBSCAN);然后,通过考虑近邻的标签,对二支聚类结果的临界点和噪声点进行重新划分,从而提出了基于局部半径的三支DBSCAN算法(LE3W-DBSCAN)。将LE-DBSCAN和LE3W-DBSCAN与该领域的相关算法在UCI数据集和人工数据集上进行对比,实验结果表明,所提算法在常用的硬聚类指标和软聚类指标上都具有较好的表现。

三元概念的布尔矩阵表示方法

王霞, 李俊余, 吴伟志

计算机科学. 2023, 50 (6): 109-115. doi:10.11896/jsjkx.220900111

摘要 ( 173 )

PDF(1474KB) ( 247 )

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

将布尔矩阵引入到三元概念分析,研究三元背景和三元概念的布尔矩阵表示方法。首先,定义三元背景的关系矩阵,将每一个条件下的三元背景看作一个布尔矩阵,那么三元背景是一个布尔分块矩阵,该布尔分块矩阵即为三元背景的关系矩阵。然后,利用关系矩阵给出三元背景上诱导算子的布尔矩阵表示方法,进而得到生成三元概念的外延、内涵和方式的布尔矩阵表示方法,该方法在生成三元概念时只使用一些基本的布尔矩阵运算而不涉及三元背景的诱导算子。最后,给出构造三元概念的枚举法的布尔矩阵表示方法以及基于对象-条件三元概念构造三元概念的布尔矩阵表示方法。三元概念的布尔矩阵表示方法从矩阵的角度理解三元背景和三元概念,为研究三元概念分析提供了新的视角。

基于人工蜂群的三支k-means聚类算法

徐天杰, 王平心, 杨习贝

计算机科学. 2023, 50 (6): 116-121. doi:10.11896/jsjkx.220800150

摘要 ( 155 )

PDF(1319KB) ( 246 )

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

聚类在数据挖掘技术中起着至关重要的作用。传统的聚类算法都是硬聚类算法,即对象要么属于一个类,要么不属于一个类,在处理不确定数据时,强制划分会带来决策错误。三支k-means聚类算法可以对边界不确定数据进行更加合理的分类,但仍然存在对初始聚类中心敏感的问题。为解决这一问题,将人工蜂群算法与三支k-means聚类算法相结合,提出了一种基于人工蜂群的三支k-means聚类算法。通过定义类内聚集度函数和类间离散度函数来构造蜜源的适应度函数,引导蜂群向高质量的蜜源进行全局搜索。利用蜂群之间不同角色的相互协作与互换,对数据集进行多次迭代聚类,找到最优的蜜源位置,作为初始聚类中心,并在此基础上交替迭代聚类。实验证明,该方法对聚类结果的性能指标有所提高。在UCI数据集上的实验验证了该算法的有效性。

基于概念复合的对偶三支概念格及其概念约简

刘津, 米据生, 李仲玲, 李美争

计算机科学. 2023, 50 (6): 122-130. doi:10.11896/jsjkx.220800109

摘要 ( 331 )

PDF(1497KB) ( 260 )

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

三支概念格通过正负算子相结合,既表示出了共同拥有的信息,又表示出了共同不拥有的信息,是对经典概念格的扩展。但在处理一些实际问题时,人们也会从反向出发,考虑集合的补集可能不拥有的信息和可能拥有的信息,对偶三支概念格应运而生。文中提出了一种基于形式背景的对偶概念及其补背景中对偶概念的复合来构造对偶三支概念格的方法,经验证,通过概念复合方法得到的对偶三支概念与通过对偶三支算子得到的概念相同。进一步讨论了基于可辨识矩阵求解对偶三支概念格的属性约简方法,并借助此思想,给出了基于概念可辨识矩阵的对偶三支概念约简方法。

不协调广义决策多尺度序信息系统的最优尺度选择与规则提取

杨烨, 吴伟志, 张嘉茹

计算机科学. 2023, 50 (6): 131-141. doi:10.11896/jsjkx.220800149

摘要 ( 129 )

PDF(1437KB) ( 240 )

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

粒计算模拟人类思考问题的模式,在大数据挖掘和知识发现方面有独特优势。针对不协调的广义决策多尺度序信息系统的知识获取问题,利用证据理论来研究不协调的广义决策多尺度序信息系统的最优尺度选择与规则提取。首先,将优势关系引入决策多尺度信息系统中,并介绍广义决策多尺度序信息系统的相关概念;其次,通过引入不协调广义决策多尺度序信息系统的尺度组合概念,给出不同尺度组合下信息粒和集合的下近似与上近似的表示及其相互关系,并进一步定义了几种针对不同决策的不协调广义决策多尺度序信息系统的最优尺度组合概念,讨论了它们之间的关系;最后,给出了基于广义优势决策函数的辨识矩阵属性约简与规则提取方法。

基于智能映射推荐的知识图谱实例构建与演化方法

张雅晴, 单中原, 赵俊峰, 王亚沙

计算机科学. 2023, 50 (6): 142-150. doi:10.11896/jsjkx.230300071

摘要 ( 193 )

PDF(2496KB) ( 308 )

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

随着大数据技术的深入发展,各领域产生了海量异构数据,构建知识图谱是实现异构数据语义互通的重要手段。通过将结构化数据与本体模型映射匹配来生成实例模型是图谱实例层构建常用的方法。然而,对于复杂异构的领域数据来说,现有映射式实例构建方法大多需要用户手动完成全部映射匹配,映射操作繁琐,无法进行智能匹配,费时费力且容易出错。除此之外,现有方法对实例导入后的增量更新也支持不足。针对现有模式匹配和实例构建方法的映射操作繁琐的问题,提出了基于智能映射推荐的实例构建与演化方法。其中,智能映射复用推荐机制,在用户手动映射之前进行数据模式匹配计算,对元素级相似度、表级相似度和表间传播相似度进行多级相似度综合计算,根据数据模式匹配度仲裁排序后生成推荐映射。另外,增量发现机制通过自动发现冗余实例和冲突实例,生成系统后台任务进行处理,可实现实例的高效无重复导入。在山东市政府开放数据集和深圳市医疗急救数据集上进行了实验,在映射复用推荐模块的辅助下,交互时间缩短为传统模式的约26%,字段推荐匹配准确率达到98.1%;在增量发现模块的实验中,导入了1 394万个实例节点以及2 158万条关系边所需的时间由31.21 h缩短至2.23 h,验证了智能映射复用推荐的可用性和匹配准确率,提高了实例层构建与演化的效率。

极限距离噪声估计与过滤方法

姜高霞, 秦佩, 王文剑

计算机科学. 2023, 50 (6): 151-158. doi:10.11896/jsjkx.220600130

摘要 ( 281 )

PDF(2445KB) ( 273 )

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

近年来,机器学习不断取得显著性进展并被成功应用于诸多领域,然而很多学习模型或算法高度依赖数据的标签质量。实际应用中大量数据集普遍存在复杂的标签噪声,因此机器学习在低质数据建模和标签噪声处理方面面临严峻挑战。文中针对回归中的数值型标签噪声,从理论分析和仿真实验的角度研究了标签估计区间与噪声的关联性,提出了一种极限距离噪声估计方法。在最优样本选择框架下,基于此噪声估计方法提出了一种极限距离噪声过滤(Limit Distance Noise Filtering,LDNF)算法。实验结果表明,所提噪声估计方法与真实标签噪声具有更高的相关性和更低的估计偏差。在标准数据集和真实年龄估计数据集上证实了所提过滤算法可以在不同噪声环境下有效识别标签噪声并减小模型的测试误差,其表现优于最新的其他过滤算法。

基于持续同调的过滤式特征选择算法

殷杏子, 彭宁宁, 詹学燕

计算机科学. 2023, 50 (6): 159-166. doi:10.11896/jsjkx.220500169

摘要 ( 220 )

PDF(3102KB) ( 366 )

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

现有的过滤式特征选择算法忽略了特征之间的关联性。鉴于此,提出了一种新的过滤式特征选择算法——基于持续同调的特征选择算法(Rel-Betti算法),该算法能够识别特征之间的关联性以及组合效果。通过提出相关贝蒂数概念,筛选出数据集中重要的拓扑特征信息。该算法对数据集进行预处理后,根据类标签将数据集分类,计算不同类中的相关贝蒂数,获得数据信息的特征均值,按特征均值差值大小对特征进行重要性排序。利用UCI数据集中的8个数据,将该算法与其他常见算法在决策树、随机森林、K近邻和支持向量机这4种学习模型下进行比较实验。结果表明,该算法是一种有效的特征选择算法,其能够提高分类的准确率和F1值,并且不依赖于特定的机器学习模型。

基于超图正则化的多模态信息融合算法

崔冰晶, 张懿璞, 王飚

计算机科学. 2023, 50 (6): 167-174. doi:10.11896/jsjkx.220900144

摘要 ( 305 )

PDF(3087KB) ( 336 )

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

多模态数据融合方法通过学习多个数据集间的关联信息和互补信息,提高了数据分类或预测的性能。但现有的数据融合方法大都基于单独数据集自身的特征模式进行学习,不同异构数据之间的结构信息往往被忽略。因此,文中提出了一种基于超图正则化的多模态信息融合算法(sHMF),通过超图和流行正则项的方法结合表示模态内样本间的高阶关系和模态间的关系,即得到同构和异构的高阶网络。其中,采用超图稀疏表达学习超图,减少冗余边。为了验证所提算法的性能,在模拟数据和影响遗传学真实数据下进行实验,结果表明,sHMF算法在模拟数据和真实数据上均优于多任务学习、多邻域分类等流行算法对精神分裂症的分类精度。同时,sHMF在真实数据上得出的实验结果进一步揭示了一些与精神分裂症显著相关的生物标记物以及风险基因、甲基化因子和异常脑区之间潜在的联系。

基于Bloom分类法的CS1试题数据集的构建及其自动分类

董荣胜, 卫晨雨, 胡杰, 乔宇澄, 李凤英

计算机科学. 2023, 50 (6): 175-182. doi:10.11896/jsjkx.230200182

摘要 ( 223 )

PDF(1549KB) ( 223 )

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

课程评估是教学改革的一个关键环节,涉及教学案例、试题以及课堂教学等方面的内容。针对计算课程的试题评估,引入Bloom分类法,以普林斯顿大学和桂林电子科技大学“计算机科学导论”课程(CS1)的试题为语料库,给出针对CS1的Bloom分类法认知过程维度和知识维度的相应动词种子库和名词种子库,对试题所能达到的Bloom分类法二维矩阵的位置进行标注,构建CS1试题分类数据集。采用机器学习技术,给出CS1试题自动分类模型TFERNIE-LR,该模型由CSTFPOS-IDF算法、ERNIE模型和LR分类器3部分组成。CSTFPOS-IDF算法是在TFPOS-IDF算法的基础上,通过计算课程关键词权重因子,来提高模型对计算课程关键词的关注程度,生成词权重。同时,基于实体知识增强预训练模型ERNIE进行试题词语级向量嵌入,组合词权重和词语级向量生成用于自动分类的试题文本向量。最后,采用LR分类器将试题自动分类到Bloom分类法二维矩阵。实验结果表明,TFERNIE-LR模型具有良好的性能,在认知过程维度和知识维度上的加权精确率分别达到了83.3%和96.1%。

基于锚图分类的在线半监督跨模态哈希

秦亮, 谢良, 陈盛双, 徐海蛟

计算机科学. 2023, 50 (6): 183-193. doi:10.11896/jsjkx.220400038

摘要 ( 230 )

PDF(3824KB) ( 309 )

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

近年来,哈希算法由于其存储成本小、检索速度快的特点,在大规模多媒体数据的高效跨模态检索中受到了广泛关注。现有的跨模态哈希算法大多是有监督和无监督方法,其中有监督方法通常能够获得更好的性能,但在实际应用中要求所有数据都被标记并不具有可行性。此外,这些方法大多数是离线方法,面对流数据的输入需要付出高额训练成本且十分低效。针对上述问题,提出了一种新的半监督跨模态哈希方法——在线半监督锚图跨模态哈希(Online Semi-supervised Anchor Graph Cross-modal Hashing,OSAGCH),构建了半监督锚图跨模态哈希模型,在只有部分数据有标签的情况下,利用正则化锚图预测数据标签,并通过子空间关系学习哈希函数,一步生成统一的哈希码,同时针对流数据输入的情况对该模型进行了在线化学习,使其能够处理流数据。在公共多模态数据集上进行了实验,结果表明所提方法的性能优于其他现有方法。

PSwin:基于Swin Transformer的边缘检测算法

胡名扬, 郭燕, 金杨爽

计算机科学. 2023, 50 (6): 194-199. doi:10.11896/jsjkx.220700145

摘要 ( 228 )

PDF(2106KB) ( 470 )

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

边缘检测作为一种传统的计算机视觉算法,已经被广泛应用于车牌识别、光学字符识别等现实场景。当边缘检测作为更高层级算法的基础时,比如目标检测、语义分割等算法,又可以应用于城市安防、自动驾驶等领域。好的边缘检测算法能够有效提升上述计算机视觉任务的效率和准确度。边缘提取任务的难点在于目标的大小以及边缘细节的差异性,因此边缘提取算法需能够有效处理不同尺度的边缘。PSwin首次将Transformer应用于边缘提取任务,并提出了一种新型特征金字塔网络,以充分利用骨干网络多尺度和多层次的特征。PSwin使用自注意力机制,相比卷积神经网络架构,可以更有效地提取图像中的全局结构信息。在BSDS500数据集上进行评估时,PSwin边缘检测算法达到了最佳水平,ODS F-measure 为0.826,OIS为0.841。

基于动态卷积核的自适应图像去雾算法

刘哲, 梁宇栋, 李嘉莹

计算机科学. 2023, 50 (6): 200-208. doi:10.11896/jsjkx.220400288

摘要 ( 167 )

PDF(3864KB) ( 383 )

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

现有图像去雾方法普遍存在去雾不彻底、容易出现颜色失真等问题,基于传统深度学习模型的图像去雾方法多采用静态推理模式,在该模式下,模型对不同样本会采用同样的、固定的参数设置,从而抑制了模型的表达能力,影响图像的去雾效果。针对以上问题,文中提出了一种基于动态卷积核的自适应图像去雾算法,该算法包括编码网络、自适应特征增强网络和解码网络3个部分。文中采用动态卷积、密集残差、注意力机制设计了自适应特征增强网络,该网络主要包括动态残差组件和动态跨层特征融合组件。动态残差组件由动态密集残差模块、一个卷积层和双注意力模块构成,其中动态密集残差模块将动态卷积引入密集残差模块,同时设计了一个基于注意力的权重动态聚合子网络,动态地生成卷积核参数以达到样本自适应的目的,在减少信息丢失的同时增强了模型的表达能力;双注意力模块结合通道注意力和像素注意力,使模型更加关注图像通道之间的差异性以及雾霾分布不均匀的区域。动态跨层特征融合组件通过动态融合不同阶段的特征,来学习丰富的上下文信息,防止网络深层计算时遗忘网络的早期特征,同时极大地丰富了特征表示,有利于模型对无雾图像细节信息的恢复。在合成数据集和真实数据集上进行了大量实验,结果表明,所提方法不仅取得了较好的客观评价分数,而且重建了主观效果较好的去雾图像,超越了对比方法的性能。

基于群稀疏的约束平滑秩近似的高光谱图像去噪

张历洪, 叶军

计算机科学. 2023, 50 (6): 209-215. doi:10.11896/jsjkx.220300236

摘要 ( 299 )

PDF(3589KB) ( 320 )

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

高光谱图像(Hyperspectral Image,HSI)在采集过程中会产生多种类型的噪声,噪声数量越多,HSI的有效信息就越少。为了更有效地从大量混合噪声中恢复HSI的有效消息,文中提出了一种基于群稀疏正则化的约束平滑秩近似HSI恢复方法。其中,群稀疏正则化被定义为基于加权$\ell_{2,1}$范数的空谱全变分,该正则化在利用空谱维信息的同时也考虑到了HSI内部的群稀疏性,增强了模型对混合噪声的去除效果及空谱维的光滑性。此外,文中采用约束的平滑函数来近似秩函数,以更好地利用HSI的低秩属性并提高了算法效率。该优化问题采用基于交替方向乘子的迭代算法进行求解。两种加噪情况的模拟数据实验和一项基于真实数据的实验的结果表明,相比5种目前主流的方法,所提方法在目视效果和评价指标上都有明显提升。

基于空频联合卷积神经网络的GAN生成人脸检测

王金伟, 曾可慧, 张家伟, 罗向阳, 马宾

计算机科学. 2023, 50 (6): 216-224. doi:10.11896/jsjkx.220400268

摘要 ( 163 )

PDF(3227KB) ( 312 )

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

生成式对抗网络(GAN)的快速发展使其在图像生成领域取得了前所未有的成功。StyleGAN等新型GAN的出现使得生成的图像更真实且具有欺骗性,对国家安全、社会稳定和个人隐私都构成了较大威胁。文中提出了一种基于空频联合的双流卷积神经网络的检测模型。鉴于GAN图像在生成过程中因上采样操作在频谱上留下了清晰可辨的伪影,设计了可学习的频率域滤波核以及频率域网络来充分学习并提取频率域特征。为了减弱图像变换至频域过程中丢弃部分信息而带来的影响,同样设计了空间域网络来学习图像内容本身具有差异化的空间域特征,最终将两种特征融合来实现对GAN生成人脸图像的检测。在多个数据集上的实验结果表明,所提模型在高质量生成数据集上的检测精度及在跨数据集的泛化性上都优于现有算法,且对于JPEG压缩、随机剪裁、高斯模糊等图像变换具有更强的鲁棒性。不仅如此,所提方案在GAN生成的局部人脸数据集上也有不错表现,进一步证明了所提模型有着更好的通用性以及更加广泛的应用前景。

基于分层伪标签的图像聚类方法

蔡少填, 陈小军, 陈龙腾, 邱莉萍

计算机科学. 2023, 50 (6): 225-235. doi:10.11896/jsjkx.220900197

摘要 ( 306 )

PDF(2941KB) ( 268 )

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

图像聚类是图像处理中一个重要且开放的问题。最近,一些方法利用联合对比学习的良好表征能力来进行端到端聚类学习,利用伪标签技术来生成高质量的伪标签以提升聚类模型的鲁棒性。伪标签方法通常需要设置一个较大的概率阈值,并对满足要求的样本生成one-hot的标签,同时利用生成的标签来更新模型。但是,这种简单的伪标签生成方法难以获得足够数量的高质量伪标签。为了解决以上问题,提出了一种基于分层伪标签的图像聚类方法,它旨在利用结构化信息与伪标签信息对分类模型进行训练和精炼。引入3个假设来指导聚类方法的设计,包括局部平滑假设、自训练假设及低密度分离假设。新方法包含两个阶段:1)基于流形的一致性学习,利用近邻一致性学习来初始化聚类模型;2)基于分层伪标签的模型精炼,基于第一阶段的结果生成伪标签,并利用其来提升聚类模型的鲁棒性。首先,将基于第一阶段的结果生成强伪标签数据集及弱伪标签数据集;然后,提出了基于标签传播及分层混合的伪标签提升技术来提升弱伪标签数据集的质量;最后,同时利用强伪标签数据集及弱伪标签数据集来提升分类模型的泛化能力。相较于最优结果,SPC算法在STL10和Cifar100-20基准数据集上,ACC平均结果分别提升了7.6%和5.0%。

基于气象数据与多噪声融合的体积云模拟研究

卢春海, 徐新海, 张帅, 李豪

计算机科学. 2023, 50 (6): 236-242. doi:10.11896/jsjkx.220500070

摘要 ( 256 )

PDF(3009KB) ( 303 )

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

为了在智能无人机集群仿真中构建逼真的仿真环境,需要考虑基于气象数据对云进行建模与渲染。而当前基于真实气象数据的云模拟大多采用物理建模方法,如求解NS方程和粒子系统方法,这些方法为繁重的微积分方程求解任务所累,存在因计算量大而无法在大规模场景下实现实时仿真的缺点。针对该问题,提出了一种使用气象数据生成纹理与多噪声融合的体积云建模方法,并将气象数据与高度相关函数相结合来定义云的形状和密度在高度上的变化,有效地将气象数据与非物理建模方法进行结合。渲染时采用光线步进算法从视线方向和朝向太阳两个方向累积云的密度,结合光的吸收和散射定律计算每个样本点的颜色与透明度,最终绘制成云。实验结果表明,模拟出的体积云与气象数据中的云层信息较为一致,效率高,且在形态和颜色上都接近真实的云。

基于多特征嵌入的中文医学命名实体识别

黄健格, 贾真, 张凡, 李天瑞

计算机科学. 2023, 50 (6): 243-250. doi:10.11896/jsjkx.220400115

摘要 ( 339 )

PDF(1531KB) ( 274 )

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

针对基于字符表示的中文医学命名实体识别模型嵌入信息单一、缺失词边界和结构信息的问题,文中提出了一种融合多特征嵌入的医学命名实体识别模型。首先,将字符映射为固定长度的嵌入表示;其次,引入外部资源构建词汇特征,该特征能够补充字符的潜在词组信息;然后,根据中文的象形文字特点和文本序列特点,分别引入字符结构特征和序列结构特征,使用卷积神经网络对两种结构特征进行编码,得到radical-level词嵌入和sentence-level词嵌入;最后,将得到的多种特征嵌入进行拼接,输入长短期记忆网络编码,并使用条件随机场输出实体预测结果。将自建中文医疗数据和CHIP_2020任务提供的医疗数据作为数据集进行实验,实验结果表明,与基准模型相比,所提模型同时融合了词汇特征和文本结构特征,能够有效识别医学命名实体。

融合抗噪和双重蒸馏的文本分类方法

郭伟, 黄嘉晖, 侯晨煜, 曹斌

计算机科学. 2023, 50 (6): 251-260. doi:10.11896/jsjkx.220500100

摘要 ( 339 )

PDF(1892KB) ( 331 )

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

文本分类是自然语言处理中重要且经典的问题,常被应用于新闻分类、情感分析等场景。目前,基于深度学习的分类方法已经取得了较大的成功,但在实际应用中仍然存在以下3个方面的问题:1)现实生活中的文本数据存在大量的噪声标签,直接用这些数据训练模型会严重影响模型的性能;2)随着预训练模型的提出,模型分类准确率有所提升,但模型的规模和推理计算量也随之提升明显,使得在资源有限的设备上使用预训练模型成为一项挑战;3)预训练模型存在大量的冗余计算,当数据量较大时会导致模型出现预测效率低下的问题。针对上述问题,提出了一个融合抗噪和双重蒸馏(包括知识蒸馏和自蒸馏)的文本分类方法,通过基于置信学习的阈值抗噪方法和一种新的主动学习样例选择算法,以少量的标注成本提升数据的质量。同时,通过知识蒸馏结合自蒸馏的方式,减小了模型规模和冗余计算,进而使其可以根据需求灵活调整推理速度。在真实数据集上进行了大量实验来评估该方法的性能,实验结果表明所提方法在抗噪后准确率提升了1.18%,在较小的精度损失下相比BERT可以加速4~8倍。

分裂可行性问题的外推加速线性交替方向乘子法及其全局收敛性

刘洋, 薛中会, 王永全, 曹永胜

计算机科学. 2023, 50 (6): 261-265. doi:10.11896/jsjkx.230100009

摘要 ( 186 )

PDF(1283KB) ( 221 )

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

针对在图像重建以及语言处理系统等领域有着广泛应用的分裂可行性问题(SFP)的最优化求解,提出了外推加速线性交替方向乘子法。首先将SFP描述为一个具有线性约束的可分离凸极小化问题;然后引进外推线性交替方向乘子法,利用问题的可分离结构,产生了具有闭式解的子问题,并在适当条件下证明了该算法的全局收敛性;最后,通过数值实验验证了该算法的可行性和有效性。

基于群智能体深度强化学习的模块化机器人自重构算法

王翰墨, 郑世杰, 徐若楠, 郭斌, 吴磊

计算机科学. 2023, 50 (6): 266-273. doi:10.11896/jsjkx.230300044

摘要 ( 185 )

PDF(2319KB) ( 362 )

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

模块化机器人是由一定数量、具有独立功能的标准模块组合而成的。自重构问题是目前模块化机器人研究领域的热点与难点。传统的图论算法或者搜索算法在模块数量较多、复杂度较大时,无法在多项式时间内寻找到通用最优解。文中从群智能体深度强化学习的角度出发,将每个同构模块视为具有学习与感知能力的单智能体,提出了基于QMIX的模块化机器人自重构算法。针对该算法,设计了一种新型的奖励函数,并在限制智能体的动作空间的基础上,实现了智能体并行化移动,在一定程度上解决了多智能体之间的协调合作问题,从而实现了从初始构型向目标构型的转变。实验以9个模块为例,对比了该算法与基于A^*的传统搜索算法在成功率以及平均步数上的差异。实验结果表明,在时间步数限制合理的情况下,基于QMIX的模块化机器人自重构算法的成功率能够达到95%以上,两种算法的平均步数大约在12步左右,QMIX自重构算法能够逼近传统算法的效果。

一种基于修正机制和强化学习的作业车间调度问题的优化算法

苗宽, 李崇寿

计算机科学. 2023, 50 (6): 274-282. doi:10.11896/jsjkx.220900112

摘要 ( 507 )

PDF(1664KB) ( 307 )

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

近年来,使用深度强化学习解决作业车间调度问题的研究主要集中于构造法,通过将作业车间调度问题视为顺序决策问题,逐步选择调度节点从而得到完整的解。尽管这种算法思想已经取得了不小的成果,但仍面临奖励构造困难、解决方案质量不高的问题,因此这一方法的发展受到制约。针对这些问题,设计了一种基于图神经网络和近端策略优化算法的强化学习构造框架。同时,针对因训练与测试数据分布不一致而带来的次优解问题,还设计了一种修正交换算子,以保证解的质量。最后,为了证明算法的有效性,在公开数据集和生成的数据集上进行了实验。实验结果表明,所提算法在中小规模实例上的结果优于目前最好的强化学习框架,不仅充分发挥了构造式强化学习框架求解迅速的优势,还通过修正机制有效缓解了次优选择问题,缩短了实例的最大完成时间。

基于增强AST的图神经网络函数级代码漏洞检测方法

顾守珂, 陈文

计算机科学. 2023, 50 (6): 283-290. doi:10.11896/jsjkx.220600131

摘要 ( 348 )

PDF(2037KB) ( 341 )

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

软件漏洞逐年递增,安全问题愈发严重。在软件项目的交付阶段对原始代码进行漏洞检测可以有效避免后期运行时的安全漏洞,而代码漏洞检测依赖于有效的代码表征。传统的基于软件度量的表征方法与漏洞关联性较弱,难以对漏洞信息进行有效表征。近年来,机器学习为漏洞的智能化发现提供了新的思路,但该方法同样可能遗漏关键的代码特征信息。针对以上问题,文中在传统抽象语法树(AST)上增加控制依赖、数据依赖和语句序列边生成增强抽象语法树(EXAST)图结构,对原始代码进行表征以更好地处理代码结构化信息,并采用词向量嵌入算法(Word2Vec)将代码信息初始化为机器能够识别和学习的数值向量。同时,在传统的图神经网络(GNN)中引入门控循环单元(GRU),构建图识别模型,以缓解梯度消失并加强图结构中长期信息的传播,从而增强了代码执行的时序关系,提高了漏洞检测的准确度。最后在SARD公开数据集上对模型进行对比测试,实现了函数粒度的代码漏洞检测,相比传统的漏洞检测方法,准确率和F1分值分别最大提高了32.54%和44.99,实验结果证明了所提方法对代码漏洞检测的有效性。

基于半量子秘密比较的量子拍卖协议

杨涵, 冯雁, 谢四江

计算机科学. 2023, 50 (6): 291-296. doi:10.11896/jsjkx.220500063

摘要 ( 187 )

PDF(1496KB) ( 227 )

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

针对量子密封拍卖协议中报价隐私保护不足、第三方不可信、对参与双方量子能力要求较高等情况,提出了一种将高能级单粒子作为信息载体的基于半量子秘密比较的量子密封投标拍卖协议。协议过程无需第三方参与,且采用半量子方式,仅要求拍卖方为强量子能力方,投标方仅需拥有反射粒子及制备单粒子的能力。协议利用半量子秘密比较,实现对投标方报价的隐私保护,拍卖方仅能获得报价之间的大小关系,而无法获取具体报价。文中通过理论分析证明了所提协议具有较高的安全性,能够抵御测量-重发攻击、截获-重发攻击、纠缠攻击、共谋攻击等多种攻击,且协议通信效率较稳定,不受投标人数的影响。

基于机器学习的SCADE模型组合验证环境假设自动生成方法

张泽伦, 杨志斌, 李晓劼, 周勇, 李维

计算机科学. 2023, 50 (6): 297-306. doi:10.11896/jsjkx.220500207

摘要 ( 226 )

PDF(3264KB) ( 228 )

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

高安全应用开发环境(Safety Critical Application Development Environment,SCADE)是工业界进行安全关键软件建模、仿真测试和形式化验证的常用工具,如何解决工业级软件的SCADE模型在进行形式化验证时遇到的状态空间爆炸问题是目前面临的一项重要挑战。基于契约的组合验证方法通过研究软件各构件的上下文和外部环境来编写环境假设对构件的状态空间进行约束,能够解决状态空间爆炸问题,但环境假设的手工编写费时费力。为了解决这一问题,文中提出了一种基于机器学习的SCADE模型组合验证环境假设自动生成方法。首先,针对SCADE模型采用自动仿真方法生成机器学习方法所需数据集;然后,采用决策树和遗传算法进行环境假设自动生成;最后,实现了具有SCADE模型分析和环境假设自动生成功能的原型工具,并基于弹射座椅控制系统案例,验证了所提方法的有效性。

基于秘密共享的多因素区块链私钥保护方案

肖健, 杨敏

计算机科学. 2023, 50 (6): 307-312. doi:10.11896/jsjkx.220600069

摘要 ( 142 )

PDF(1489KB) ( 235 )

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

针对区块链缺少恢复机制导致用户私钥一旦丢失就难以找回的问题,提出了一种基于口令、秘密问题和指纹的多因素区块链私钥保护方案。该方案无需用户存储额外信息且可以完全在线上实施,并采用了抗遗忘的因素访问策略。在注册阶段,用户需要提供所有因素信息(包括口令、秘密问题和指纹)以及区块链私钥,并使用秘密共享方案为一组服务器分配秘密份额。在恢复阶段,用户仅需要提供部分因素并向多个服务器发送恢复申请,即可获得其秘密份额的信息并以此重构出区块链私钥。实验结果和启发式安全分析表明,该方案中客户端和服务端的计算开销都在毫秒级,可以抵抗已知攻击且通过支持多因素提供了更好的安全性。

基于日志模板主题特征的日志异常检测

孙雪奎, 戴华, 周建国, 杨庚, 陈燕俐

计算机科学. 2023, 50 (6): 313-321. doi:10.11896/jsjkx.220500020

摘要 ( 389 )

PDF(2495KB) ( 364 )

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

在系统安全领域,通过日志来检测软件或者系统异常是一种常用的安全防护手段。随着软件和硬件的快速发展,在大规模的日志记录上进行人工标记变得十分困难,目前已有大量的日志异常检测的相关研究。现有的自动化日志检测模型均使用日志模板作为分类,这些模型的性能以及实用性很容易受到日志模板变化的影响。因此,基于日志模板主题特征的日志异常检测模型LTTFAD被提出,LTTFAD首次引入了LDA主题模型以提取日志模板的主题特征并且通过循环神经网络LSTM实现异常检测。实验结果表明,在HDFS和OpenStack数据集上基于日志模板主题特征的日志异常检测模型LTTFAD的查准率、查全率和调和分数等性能指标均明显优于现有基于日志模板的日志异常检测模型。此外,对于新日志模板的注入,LTTFAD模型依然具有较高的稳定性。

基于信用评价模型的Raft共识算法

刘炜, 郭灵贝, 夏玉洁, 佘维, 田钊

计算机科学. 2023, 50 (6): 322-329. doi:10.11896/jsjkx.220500171

摘要 ( 435 )

PDF(2853KB) ( 277 )

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

在车联网中,车辆节点间需要交通信息的共享和交互,但目前还存在着节点之间难以高效同步交通数据信息以及恶意节点传播虚假信息的问题。针对上述问题,提出了一种基于信用评价模型的Raft共识算法(CE-Raft)。首先构建信用评价模型,基于孤立森林异常检测算法检测拜占庭车辆节点并将其剔除,生成诚实节点编号表;然后进行领导者选举,通过修改跟随者节点的投票过程,实现诚实节点当选领导者;最后进行日志复制,领导者节点根据诚实节点编号表发送信息同步请求,确保正确的消息在节点间达成共识。实验结果表明,CE-Raft算法能够有效排除拜占庭节点,提高了诚实节点预测准确率,具有较低的时延和较高的吞吐量,使车联网在存在恶意节点的情况下,仍然能安全高效地完成数据共享。

一种面向开源异构数据的网络安全威胁情报挖掘算法

魏涛, 李志华, 王长杰, 程顺航

计算机科学. 2023, 50 (6): 330-337. doi:10.11896/jsjkx.220700073

摘要 ( 227 )

PDF(1536KB) ( 332 )

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

针对如何从开源网络安全报告中高效挖掘威胁情报的问题,提出了一种基于威胁情报命名实体识别(Threat Intelligence Named Entity Recognition,TI-NER)算法的威胁情报挖掘(TI-NER-based Intelligence Mining,TI-NER-IM)方法。首先,收集了近10年的物联网安全报告并进行标注,构建威胁情报实体识别数据集;其次,针对传统实体识别模型在威胁情报IoC攻击指示器挖掘领域的不足,提出了基于自注意力机制和字符嵌入的威胁情报实体识别(Threat Intelligence Entity Identification based on Self-attention Mechanism and Character Embedding,TIEI-SMCE)模型,该模型融合字符嵌入信息,再通过自注意力机制捕获单词间潜在的依赖权重、语境等特征,从而准确地识别威胁情报IoC实体;然后,基于TIEI-SMCE模型,提出了一种威胁情报命名实体识别算法;最后,集成上述模型和算法,进一步提出了一种新的威胁情报挖掘方法。TI-NER-IM方法能实现从非结构化、半结构化网络安全报告中自动挖掘威胁情报IoC实体。实验结果表明,与BERT-BiLSTM-CRF模型相比,TI-NER-IM方法的F1值提升了1.43%。

业务流程模型相似度研究综述

简开宇, 史涯晴, 黄松, 许山山, 杨忠举

计算机科学. 2023, 50 (6): 338-350. doi:10.11896/jsjkx.220700061

摘要 ( 280 )

PDF(1453KB) ( 379 )

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

随着业务流程模型管理库规模的增大,传统的模型管理方式在效率和准确度方面已经无法达到预期,研究能够提升业务流程模型管理效率的技术成为人们的迫切需求。其中,业务流程模型相似度技术在模型搜索、模型一致性检测等模型管理的相关应用场景中能够有效提升工作的效率和精度,因此,对业务流程模型相似度技术的研究已经逐渐成为模型分析领域的一个研究热点,并取得了许多有价值的研究成果。业务流程模型相似度技术涉及的领域较多,可以向不同的分支方向发展,虽然不同分支的模型相似度技术会有方法之间的类比,但是缺乏系统性的整理和分析。文中从相似度计算方法和应用场景这两个层面对业务流程模型相似度技术进行了分类讨论,将相似度计算方法分为文本相似度、语义相似度、结构相似度、行为相似度和基于人类评估的相似度,并分析了每种计算方法的特点。较为常见的业务流程模型相似度应用场景包括一致性检测、标准化、流程模型搜索和模型重用,文中对基于以上场景的相关研究进行了梳理。最后分析了业务流程模型相似度研究面临的挑战。

基于Grover算法的图着色问题求解

刘晓楠, 刘正煜, 谢浩山, 赵晨言

计算机科学. 2023, 50 (6): 351-357. doi:10.11896/jsjkx.220400051

摘要 ( 322 )

PDF(3397KB) ( 312 )

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

Grover量子搜索算法是针对非结构化搜索问题设计的著名量子算法,可用于解决图着色、最短路径排序等问题,也可以有效破译密码系统。图着色问题是最著名的NP-完全问题之一,文中首先将图着色问题转化为数学上的无向图;然后采用布尔表达式将其转换为布尔可满足性问题,介绍了量子线路图解决布尔表达式的步骤原理以及图着色问题向布尔可满足性问题的转换过程;最后在IBMQ云平台上,对三节点的2-着色问题以及4-着色问题进行模拟仿真。实验结果验证了使用Grover算法求解图着色问题的可行性,在搜索空间为8的2-着色问题和搜索空间为64的4-着色问题中,分别以近82%和97%的成功概率搜索到目标项。文中使用Grover算法解决了4-着色问题,拓展了该算法在此问题领域上的实验规模,且改进了现有实验的量子线路,使量子位成本更低,结果的成功率更高,展示了Grover算法在大型搜索问题中显著的加速效果。

基于冲突搜索的多智能体路径规划研究进展

王子晗, 童向荣

计算机科学. 2023, 50 (6): 358-368. doi:10.11896/jsjkx.220800151

摘要 ( 377 )

PDF(1949KB) ( 391 )

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

多智能体路径规划是人工智能领域一个经典的搜索问题,基于冲突的搜索算法是当前解决该问题的最优算法之一。文中讨论了多智能体路径规划的基础研究,对国内外近年来基于冲突搜索算法及其变体的研究成果进行了分类,根据改进方式将其变体分为4类,包括分割策略的改进、启发式算法、对典型冲突的处理和次优算法。同时介绍了基于冲突的搜索算法在多智能体路径规划的扩展问题中的应用。最后根据当前算法的优缺点,指出了目前面临的挑战,并针对这些挑战给出了未来可能的研究方向。