1974年1月创刊(月刊)
主管/主办:重庆西南信息有限公司
ISSN 1002-137X
CN 50-1075/TP
CODEN JKIEBK
编辑中心
当期目录
2019年第12期, 刊出日期:2019-12-15
  
大数据与数据科学
基于ISE算法的分布式ETL任务调度策略研究
王卓昊, 杨冬菊, 徐晨阳
计算机科学. 2019, 46 (12): 1-7.  doi:10.11896/jsjkx.190100023
摘要 ( 668 )   PDF(1988KB) ( 1380 )   
参考文献 | 相关文章 | 多维度评价
随着数据仓库的规模不断扩大,数据集成下的ETL(Extraction-Transformation-Loading)任务也随之增多,单机调度显然已经不能满足当下繁多复杂的ETL任务调度。针对ETL任务调度如何提高效率、缩短关键任务等待时间、提升资源利用率等问题,构建了一套分布式ETL任务调度框架,该框架由调度器和若干执行器组成,通过任务预处理、任务调度分配、任务执行3个阶段来完成ETL任务调度。在任务预处理阶段,对ETL任务建立权重模型,并根据权重确定调度优先级。在任务调度分配阶段,调度器根据各个执行器节点的性能及负载情况来约束执行器节点的选择,并设计贪心平衡(Greedy Balance,GB)算法来进行ETL任务执行请求的分发,使执行器节点的负载相对均衡。在任务执行阶段,通过高响应比优先(Highest Response Ratio Next,HRRN)算法确定执行器节点队列下任务的执行优先级。实验结果表明,分布式ETL任务调度框架及相应的一体化调度执行( Integrated Scheduling Execution,ISE)算法能够有效提高集群资源的利用率,缩短任务调度的执行时间。
AdaBoostRS:高维不平衡数据学习的集成整合
杨平安, 林亚平, 祝团飞
计算机科学. 2019, 46 (12): 8-12.  doi:10.11896/jsjkx.180901813
摘要 ( 528 )   PDF(1341KB) ( 1247 )   
参考文献 | 相关文章 | 多维度评价
机器学习中类不平衡分布问题包含了不同类之间数据样本的偏差分布,导致学习过程更偏向于多数类。而高维数据的稀疏性使得分类的偏差更加明显,因此对于高维不平衡数据,维度灾难与类不平衡分布这两个挑战性问题相互叠加在一起,使得解决高维不平衡问题变得更为困难。针对这一问题,文中提出结合随机子空间和SMOTE过采样技术的AdaBoost集成方法(AdaBoost ensemble of Random subspace and SMOTE,AdaBoostRS)来处理高维不平衡数据的分类。具体地,AdaBoostRS通过随机子空间选取部分特征来训练每个分类器,以增加分类样本的多样性和降低高维数据的维度,然后通过SMOTE方法对降维数据的少数类进行线性插值,以解决类不平衡问题。基于8个高维不平衡的标准时间序列数据集进行实验,结果表明,以F-measure、G-mean与AUC 3个性能指标来进行评判,AdaBoostRS优于传统的集成学习方法。
基于列存储的大数据采样查询处理
齐文, 鲍玉斌, 宋杰
计算机科学. 2019, 46 (12): 13-19.  doi:10.11896/jsjkx.190500155
摘要 ( 469 )   PDF(2881KB) ( 1126 )   
参考文献 | 相关文章 | 多维度评价
大数据时代的到来给传统的数据查询带来了性能挑战,即使查询算法有着O(n)的线性复杂度,但当n极大时其时间开销也难以满足用户需求。在很多实际应用中,人们并不需要精确的查询结果,但要求在给定时间内完成查询,因此可适当牺牲查询精度以满足性能约束。采样查询通过约简查询范围来提高查询性能,现有的采样方法多针对特定的算法和特定的应用场景,缺乏大数据环境下一般性的采样查询方法以及保证性能和精度的研究。文中研究大数据环境下列存储的采样查询处理,从数据划分和数据采样两方面改进大数据的查询效率。提出了基于加速比和势分布的采样方法,其支持各类采样算法,实现了分布式环境下采样查询的随机性保证、性能保证和近似性评价,并兼容了精确查询。该方法可以快速应用到已有大量数据的列存储中,具备良好的扩展性和可维护性。以Top-K为查询用例的实验结果证明,在不同数据量、不同数据分布和不同采样算法下,实际采样率与给定采样率的误差低于2%,查询准确度 (Accuracy) 稳定,方差在0.10和0.12之间,因此提出的基于段势的数据划分的采样效率高于平均划分和线性划分。
基于节点连接模式相关性的链接预测方法
单娜, 李龙杰, 刘昱阳, 陈晓云
计算机科学. 2019, 46 (12): 20-25.  doi:10.11896/jsjkx.190700057
摘要 ( 452 )   PDF(3147KB) ( 918 )   
参考文献 | 相关文章 | 多维度评价
作为复杂网络分析中的一个研究热点,链接预测在许多领域中都有重要的应用价值,得到了广泛的关注。使用网络中的已知结构信息来计算未连接的节点对之间的相似性,进而评估其存在链接的可能性是目前最常用的方法。不同网络具有不同的结构特征,节点之间的特征对链接的形成具有重要影响。为了提高链接预测的性能,文中定义了节点的连接模式,并基于节点连接模式的相关性(Correlation of Nodes’ Connecting Patterns,CNCP)设计了一个新的链接预测模型。该模型将CNCP与基本相似性指标相结合,通过综合节点的相似性与节点连接模式的相关性进行链接预测。文中将CNCP与CN(Common Neighbors),RA(Resource Allocation),AA(Adamic-Adar)及PA(Preferential Attachment)4个相似性指标相结合,提出了CNCP-CN,CNCP-RA,CNCP-AA和CNCP-PA 4个新的链接预测指标。在6个真实数据集上的实验结果表明,所提方法在AUC和Precision 2个评价标准上的性能优于对比方法。
基于密度约束的对比模式挖掘
柴欣, 高一寒, 武优西, 刘靖宇
计算机科学. 2019, 46 (12): 26-30.  doi:10.11896/jsjkx.181202289
摘要 ( 490 )   PDF(1925KB) ( 692 )   
参考文献 | 相关文章 | 多维度评价
序列模式挖掘是从序列数据中发现用户感兴趣的模式。对比模式挖掘是其中的一类挖掘方法,其特点是在两类或多类别的序列库中找到特征信息,在实际的生活和生产中应用十分广泛。随着数据规模的不断增加,算法的挖掘效率显得尤为重要,但是当前对比模式挖掘仍存在挖掘速度太慢的问题。为了快速挖掘满足密度约束和间隙约束的对比模式,文中提出了一种近似求解算法ADMD(Approximately Distinguishing Patterns Mining Based on Density Constraint),该算法在模式的挖掘过程中允许存在小部分的模式丢失,从而换取挖掘速度的大幅提升。该算法采用网树的特殊结构来计算模式的支持数;采用模式拼接的方式来生成候选模式;采用预判式剪枝策略对模式进行剪枝,以避免大量冗余模式的生成。但由于在剪枝过程中可能会剪掉一部分非冗余模式,造成挖掘结果并非完备,因此该算法是一种近似求解算法。在ADMD算法的基础上,通过在剪枝策略中设定参数k的方式来得到ADMD-k算法,该算法可以通过设定k的取值来调整剪枝程度,从而在挖掘效率和准确率方面取得平衡。最后在真实的蛋白质数据集上将所提算法与其他算法从挖掘的对比模式数量和挖掘速度方面进行对比实验。实验结果表明,在k=1.5的情况下,所提算法仅用不到原来13%的时间,就可以挖掘到99%以上的模式,具有近似度高、速度快的特点。
HMRF半监督近似核k-means算法
贾洪杰, 王良君, 宋和平
计算机科学. 2019, 46 (12): 31-37.  doi:10.11896/jsjkx.190600159
摘要 ( 474 )   PDF(1258KB) ( 694 )   
参考文献 | 相关文章 | 多维度评价
信息技术的发展催生了海量数据。聚类有助于发现数据的内在联系,从中挖掘有价值的信息。在对数据进行分析时,容易获得一些关于数据的背景知识,使用这些有限的先验信息指导聚类,可以显著改善聚类的结果。基于隐马尔可夫随机场(Hidden Markov Random Fields,HMRF)的半监督聚类使用成对约束作为监督信息,虽然在很多应用场景中有较好的聚类效果,但是其时间和空间复杂度很高,无法满足大规模数据处理的需要。针对该问题,文中首先分析了HMRF半监督聚类与核k-means的数学联系,使用矩阵的迹将两者的目标函数统一起来;然后,为了降低HMRF半监督聚类的复杂度,提出HMRF半监督近似核k-means算法(HMRF semi-supervised Approximate Kernel K-Means,HMRF-AKKM),通过采样构造近似核矩阵,使用近似核k-means优化聚类的目标函数;最后,在基准数据集上将HMRF-AKKM算法与相关的聚类算法进行对比,分析不同算法在实验中的聚类表现。实验结果表明,在相同的聚类任务上,HMRF-AKKM算法与原始的HMRF半监督聚类具有类似的聚类质量,但是HMRF-AKKM算法的聚类时间更短,说明HMRF-AKKM算法继承了HMRF半监督聚类与近似核k-means的优点。该算法一方面可以充分利用成对约束信息改善聚类质量,另一方面通过采样和矩阵近似提高了聚类效率,而且聚类质量和聚类效率可以通过调节采样比例和成对约束数量来平衡。因此,所提出的HMRF-AKKM算法具有良好的可扩展性,适合处理大规模非线性数据的聚类问题。
一种基于Q-sample的局部相似连接并行算法
王晓霞, 孙德才
计算机科学. 2019, 46 (12): 38-44.  doi:10.11896/jsjkx.190100240
摘要 ( 362 )   PDF(1890KB) ( 708 )   
参考文献 | 相关文章 | 多维度评价
局部相似连接能快速找出数据集间的局部相似记录对,是基因序列比对、剽窃检测和数据清洗等研究领域的基本操作。文中主要研究基于MapReduce框架的并行相似连接技术,提出了一种基于Q-sample的局部相似连接算法,解决了局部相似连接的定位问题。该算法采用了过滤验证二阶段模式:在过滤阶段,所提算法使用Q-sample分割方案拆分字符串集,在不丢失任何匹配的基础上生成了高质量的子串,抛弃了大量的无关字符串对;在验证阶段,所提算法优化了LS-Join算法的双向扩展验证方法,通过去除冗余匹配、合并连续匹配和合并非连续匹配等技术提高了算法的验证效率。通过实验对比了不同数据集和编辑距离参数下算法的性能表现,结果显示所提算法在大数据集上的局部相似连接速度快于当前的优秀算法LS-Join。理论分析和实验结果证明,所提算法的相关技术提高了局部相似的连接性能。
带偏置的信号传播的随机游走的社团检测算法
尹欣红, 赵世燕, 陈晓云
计算机科学. 2019, 46 (12): 45-55.  doi:10.11896/jsjkx.190700051
摘要 ( 441 )   PDF(4377KB) ( 924 )   
参考文献 | 相关文章 | 多维度评价
复杂网络是从大量现实存在的复杂系统中抽象得到的,网络的整体功能体现在网络中节点间的相互作用上,社团结构是其关键性结构特征。社团对应于系统的功能模块,提取网络的功能模块有助于深层探究复杂网络的内部规律,从复杂网络中检测社团结构具有重要的理论研究意义和实用价值。因此,很多研究者对社团检测进行了研究,进而提出了很多社团检测算法,如基于模块度优化的社团检测算法、基于标签传播的社团检测算法、基于随机游走的社团检测算法等。在对这些算法进行充分研究的基础上,通过模拟随机游走的过程,结合信号传播过程中随着传播距离的增大,信号量会缓慢衰减的思想,提出了一种带偏置的信号传播机制的随机游走的社团检测算法。该算法从网络中选取一个节点作为信号源,随机选择与其相邻的节点作为下一跳节点,将衰减后的信号量传递到该节点,依次迭代并传递信号。考虑到信号的衰减,为每条边设置偏置,对信号传播过程进行限定。通过模拟信号的传播,将网络的每个顶点作为信号源来重复这一过程,得到传播矩阵。然后,为每个顶点添加自环,并结合邻接矩阵以及顶点间的相似性,形成具有新属性的相似性矩阵。根据新属性矩阵和传播矩阵为每个顶点构造属性。最后,使用k-means算法进行聚类,得到高质量的社团结构。为了验证该方法的性能,在10个实际网络数据集以及不同规模的人工合成网络上进行实验。实验结果充分证明,所提算法能够从网络中提取出高质量的社团结构,从而有效地为社团检测领域提供依据。
基于多关系社交网络的协同过滤推荐算法
宾晟, 孙更新
计算机科学. 2019, 46 (12): 56-62.  doi:10.11896/jsjkx.181102189
摘要 ( 408 )   PDF(1743KB) ( 1721 )   
参考文献 | 相关文章 | 多维度评价
推荐系统是大数据中最常见的应用之一,传统的协同过滤推荐算法直接基于用户-项目评分矩阵,对于海量的用户和商品数据,算法的执行效率将会显著降低。针对这一问题,提出了一种基于多关系社交网络的协同过滤推荐算法。该算法利用信息传播方法对基于多子网复合复杂网络模型构建的多关系社交网络进行社团结构划分,从而将相似度接近的用户划分到一个社团中,进而在社团内部选择用户的k-近邻集合来构建用户-项目评分矩阵,然后利用协同过滤算法进行推荐,从而实现了在不降低推荐准确率的前提下提升推荐算法的执行效率。在真实数据集Epi-nions上,将所提算法与传统的协同过滤推荐算法进行对比。实验结果表明,所提算法具有较高的推荐效率和准确率,特别是对于海量数据,推荐算法的执行时间缩短到原有的1/10。
基于社区发现的兴趣点推荐
龚卫华, 沈松
计算机科学. 2019, 46 (12): 63-68.  doi:10.11896/jsjkx.190400440
摘要 ( 424 )   PDF(2002KB) ( 1105 )   
参考文献 | 相关文章 | 多维度评价
近年来,LBSN(Location-based Social Networks)作为一种典型的异质信息网络越来越受到大众的关注。针对LBSN中用户签到信息十分稀疏的情况,文中提出了一种基于社区发现的兴趣点推荐算法CBR(Community-Based Recommendation)。该算法首先在社交媒体层上计算目标用户与聚类后的兴趣主题簇的相似度;其次通过兴趣主题簇与地理位置簇之间的关联矩阵R计算用户在地理位置簇上的隶属度;然后进一步融合用户的社交关系,从而得到用户对各个兴趣点的偏好分数;最后按照兴趣点的分数进行排序,以实现Top-k推荐。实验结果表明,该算法可以明显提高兴趣点的推荐质量。
基于非负矩阵分解的短文本特征扩展与分类
黄梦婷, 张灵, 姜文超
计算机科学. 2019, 46 (12): 69-73.  doi:10.11896/jsjkx.190400107
摘要 ( 466 )   PDF(1474KB) ( 672 )   
参考文献 | 相关文章 | 多维度评价
针对短文本特征稀疏的问题,提出了一种基于非负矩阵分解的特征扩展方法(NMFFE)。该方法只考虑数据自身,不借助外部资源进行短文本的特征扩展。首先,把文本及单词的内部关系考虑到文本和单词的关系矩阵分解中,通过双正则化非负矩阵三分解(DNMTF)方法获取词聚类指示矩阵;然后,对词聚类指示矩阵进行降维处理以获取特征空间;最后,根据单词之间的相关程度,从特征空间中选取特征并将其加入短文本中,从而解决短文本特征稀疏的问题,提高文本分类的准确率。实验数据表明,与BOW算法和Char-CNN算法中表现较优者相比,基于NMFFE算法的短文本分类的准确率分别在Web snippets,Twitter sports和AGnews 数据集上提高了25.77%,10.89%和1.79%,这充分说明在分类准确率和算法鲁棒性方面,NMFFE算法优于BOW算法和Char-CNN算法。
基于欧拉核的数据流聚类算法
朱颖雯, 杨君
计算机科学. 2019, 46 (12): 74-82.  doi:10.11896/jsjkx.190600158
摘要 ( 340 )   PDF(2822KB) ( 951 )   
参考文献 | 相关文章 | 多维度评价
随着云计算、物联网的快速发展,数据采集变得更加快捷和自动化。许多新型的应用领域中,诸如实时监控系统、车辆交通监控系统、电力消耗记录以及网络流量监控等,每时每刻都在产生大量的流数据,对数据流挖掘的研究成为了热点问题。聚类分析作为数据流挖掘领域的一个重要问题,在近期被高度重视并得到广泛研究。不同于传统的静态数据聚类问题,数据流聚类受到有限内存、一遍扫描、实时响应和概念漂移等许多约束。为此,文中基于欧拉核提出了一种针对数据流的聚类算法。首先通过欧拉核显式地将数据映射到相同维度的复数特征空间,然后在特征空间中基于GNG模型进行聚类。欧拉核依赖于非线性鲁棒的cosine度量,故对野值低敏感;显式的映射避免了一般的核聚类算法需要使用核技巧而无法处理数据流的问题。实验数据表明,基于欧拉核的数据流聚类算法不仅表现出了较好的聚类性能,还识别了数据的结构信息。
一种基于样本分层的双向过采样方法
周晓敏, 曹付元, 余丽琴
计算机科学. 2019, 46 (12): 83-88.  doi:10.11896/jsjkx.190400053
摘要 ( 443 )   PDF(1618KB) ( 697 )   
参考文献 | 相关文章 | 多维度评价
重采样技术由于简单、直观,逐渐成为解决非平衡数据分类问题的一个重要方向。但是在数据集很小的情况下,重采样技术中的欠采样可能会丢失数据集的重要信息,因此过采样是非平衡数据分类问题的研究重点。现有的过采样方法虽然有效地解决了类间不平衡问题,但是有可能造成少数类的密集区域更加密集,甚至引起样本重叠。此外,由于少数类样本可能存在噪音,现有的过采样方法可能会在噪音周围生成新样本,从而造成少数类样本的分布更加混乱。针对这些问题,文中提出了一种基于样本分层的双向过采样方法,该方法首先基于最高密度点和类内平均距离将少数类样本划分成密集层和稀疏层,然后对密集层边界区样本和稀疏层的样本进行双向过采样。为了验证所提算法的有效性,在9个UCI数据集上将提出的算法和其他过采样算法进行了比较。实验结果和Friedman等检验结果显示,提出的算法在处理非平衡数据分类问题时具有一定优势。
基于张量分解的域适应算法
徐书艳, 韩立新, 徐国夏
计算机科学. 2019, 46 (12): 89-94.  doi:10.11896/jsjkx.190300095
摘要 ( 475 )   PDF(1610KB) ( 1106 )   
参考文献 | 相关文章 | 多维度评价
由于训练数据易过期,在多数情况下训练数据和测试数据具有不同的特征分布,因此在利用源域信息时,须先尽量减小不同领域的特征分布的差异。使用张量表示特征可以维持高维空间数据的本征结构信息。朴素张量子空间学习法虽然是面向张量特征的域适应方法,但其复杂度较高,且没有达到较好的知识迁移效果。为此,文中提出了基于张量分解的域适应算法,即张量列子空间学习法和张量环子空间学习法,二者的主要思想相似。首先,使用张量表示源域和目标域的特征;其次利用张量分解方法,将特征分解为一系列三阶张量来表示子空间;然后,依次将源域特征和目标域特征映射到子空间中;最后,将特征张量重塑为矩阵形式,基于映射后的源域特征训练模型,基于映射后的目标域特征完成新领域的任务。实验结果表明,在无监督图像分类中,张量列子空间学习法和张量环子空间学习法在准确率和运行时间方面都有所提升。相比于朴素张量子空间学习法,张量列子空间学习法和张量环子空间学习法的准确率分别提高了1.68%和2.08%,且运行时间也有明显减少,算法复杂度较小。实验数据充分说明,基于张量分解的域适应算法充分减小了源域特征和目标域特征之间的差异,实现了不同领域间的知识复用。
网络与通信
未来网络试验设施的节点资源调度算法
汪晨欣, 杨家海, 庄奕, 罗念龙
计算机科学. 2019, 46 (12): 95-100.  doi:10.11896/jsjkx.190400106
摘要 ( 400 )   PDF(2066KB) ( 902 )   
参考文献 | 相关文章 | 多维度评价
随着互联网产业的扩张,对于网络核心技术的研究和创新刻不容缓,未来网络试验设施项目的建设为网络相关的科研人员提供高效便捷的试验环境,以支持网络技术的创新研究和实验。未来网络试验的基础设施资源是提供服务的基础,因此对试验资源的调度管理是项目中非常重要的任务。文中面向未来网络试验设施项目的资源调度和试验服务需求,设计了集中与分布相结合的架构,通过使中心资源调度管理系统与节点资源调度管理系统相互配合,来协调调度主干网带宽资源和位于各站点数据中心的资源。并且针对试验设施的特点,设计了综合考虑虚拟机间的通信代价、站点内物理机的平均资源利用率和资源均衡的多目标优化节点资源调度算法。仿真实验结果表明,该算法能有效实现上述多个目标的优化。
基于K-medoids的改进PBFT共识机制
陈子豪, 李强
计算机科学. 2019, 46 (12): 101-107.  doi:10.11896/jsjkx.181002014
摘要 ( 794 )   PDF(1923KB) ( 1369 )   
参考文献 | 相关文章 | 多维度评价
随着数字货币的普及与发展,区块链技术进入了大众的视野,并被誉为信用历史上第四个里程碑,是未来信用的基石[1]。但与此同时,区块链技术也面临着共识效率低、算力浪费等问题。文中利用K-medoids聚类算法对参与区块链共识的大规模网络节点根据特征进行聚类与层次划分,再将改进的多中心化实用拜占庭容错算法应用于这种聚类后的分层模型中。另外,为了提升聚类算法在多种场景下对区块链模型中共识节点进行聚类的可控性,对K-medoids算法进行了改进。网络拓扑仿真环境实验表明,当选择了适当的聚类特征评判节点间的相似度时,改进后的算法K-PBFT在1000个网络节点参与共识的场景中相较于传统实用拜占庭容错算法(Practical Byzantine Fault Tolerance,PBFT)算法,单次共识耗时缩短了20%,共识过程的通信次数最佳能够降低3个数量级。结果证明K-PBFT算法优化了较大规模共识节点参与的共识过程,使区块链模型能够适用于更广泛的场景中。
基于时空特征的移动网络流量预测模型
张杰, 白光伟, 沙鑫磊, 赵文天, 沈航
计算机科学. 2019, 46 (12): 108-113.  doi:10.11896/jsjkx.181102207
摘要 ( 956 )   PDF(1794KB) ( 2113 )   
参考文献 | 相关文章 | 多维度评价
研究表明,历史流量数据可以用于移动网络流量的预测,同时周边区域的流量信息可以提高流量预测的准确性。为此,文中提出一种基于时空特征的移动网络流量预测模型STFM。STFM模型利用目标区域及周围区域的历史移动网络流量对目标区域的流量进行预测。其核心思想是,首先利用三维卷积网络(3D CNN)从流量中提取移动网络流量空间上的特征,再利用时间卷积网络(TCN)提取移动网络流量时间上的特征,最后全连接层对提取的特征与实际的流量值建立映射关系,产生预测的流量值。根据实验的验证与分析,STFM在移动网络流量预测上的标准均方根误差(NRMSE)相比TCN,CNN和CNN-LSTM分别减少了28%,21.7%和10%。因此,STFM模型能够有效提高移动网络流量预测的准确率。
基于禁忌遗传优化的离线静态虚拟网映射算法
余建军, 吴春明
计算机科学. 2019, 46 (12): 114-119.  doi:10.11896/jsjkx.181001981
摘要 ( 270 )   PDF(1520KB) ( 670 )   
参考文献 | 相关文章 | 多维度评价
离线静态虚拟网映射问题是NP难问题,其任务是以物理网提供商收益最大化为目标,在物理网上完成虚拟网子集的映射。文中对离线静态虚拟网映射问题及其研究现状进行介绍,指出当前离线静态虚拟网映射算法仅适用于小规模问题或特殊问题的求解,进而提出了一种适用于中大规模的一般离线静态虚拟网映射问题的求解算法。首先,基于收益优先的虚拟网映射顺序策略、节点等级匹配的虚拟节点映射策略以及最小化资源消耗量的虚拟链路映射策略,提出离线静态虚拟网映射问题的贪婪算法;然后,基于遗传算法和禁忌搜索混合的优化策略,提出离线静态虚拟网映射问题的禁忌遗传算法。实验表明,所提出的禁忌遗传算法具有较高的虚拟网构建完成率和物理网提供商收益,虚拟网构建完成率和物理网提供商收益分别比基线算法提高了34%和42%。
蝗虫群优化和极限学习机相结合的RFID室内定位算法
王哲, 郑嘉利, 李丽, 袁源, 石静
计算机科学. 2019, 46 (12): 120-125.  doi:10.11896/jsjkx.181202381
摘要 ( 330 )   PDF(1756KB) ( 800 )   
参考文献 | 相关文章 | 多维度评价
随着室内定位技术的飞速发展,射频识别(Radio Frequency Identification,RFID)技术以其非接触、快速识别等优点成为解决问题的首选方案。针对目前室内定位算法的精度容易受到标签密度和算法效率的影响及对动态环境适应性不足的问题,文中提出了一种蝗虫群优化(Grasshopper Optimization Algorithm,GOA)和极限学习机(Extreme Learning Machine,ELM)相结合的RFID室内定位算法。该算法通过蝗虫群优化对极限学习机随机产生的输入层权值和隐含层阈值进行选择,以提升极限学习机的性能,从而在离线阶段减少学习时间;利用蝗虫群算法对极限学习机参数进行优化,有效克服环境以及信号强度值变化对定位精度的影响。通过实验研究了影响算法性能的因素,并验证了算法的有效性。与BP神经网络算法(NN-Based)和非度量多维尺度算法(NMDS-RFID)相比,所提算法的定位平均误差分别降低了22.32%和20.06%,平均执行时间分别减少了58.7%和7.55%。仿真和实验结果表明,所提算法在获得更精确的定位结果的同时降低了时间成本,并对环境变化具有较好的适应性。
基于移动边缘计算的任务迁移和协作式负载均衡机制
殷佳, 管昕洁, 白光伟
计算机科学. 2019, 46 (12): 126-131.  doi:10.11896/jsjkx.181202453
摘要 ( 761 )   PDF(1751KB) ( 1025 )   
参考文献 | 相关文章 | 多维度评价
由于使用中心云服务会产生相应的延迟和通信成本,更靠近移动用户的移动边缘计算已经成为处理计算密集型和延迟敏感型应用程序的主要技术。位于网络边缘的小型云数据中心被称为微云,其能够为周围邻近的移动设备提供计算能力,减少服务交付的时延。然而,在移动微云组成的边缘网络环境下,负载均衡问题直接影响了任务的响应时间。为了提高用户服务质量,文中提出基于移动边缘计算的任务迁移和协作式负载均衡机制,包括分别针对用户和微云设计的延迟感知目标选择策略LATS和协作式负载均衡策略CLB。LATS根据微云当前的负载信息为移动用户选择最优的任务迁移对象;CLB使用Balls-into-bins模型,只需要获取局部信息就可以有效地实现移动微云之间的负载均衡。仿真结果表明,所提策略能够有效减小系统延迟和负载差异,同时降低通信和计算成本。
信息安全
基于注意力机制的恶意软件调用序列检测
张岚, 来耀, 叶晓俊
计算机科学. 2019, 46 (12): 132-137.  doi:10.11896/jsjkx.181102171
摘要 ( 533 )   PDF(1545KB) ( 1356 )   
参考文献 | 相关文章 | 多维度评价
传统的机器学习方法通过构造特征来学习分类器,面对嵌入大量反检测功能的恶意软件不具有鲁棒性。攻击者通过打乱恶意软件代码或插入无关代码来逃避检测。针对互联网环境下恶意软件数目众多、混淆技术进步、人工构造特征成本高等问题,文中提出一种基于循环神经网络和注意力机制的恶意软件检测方法(G2ATT)。首先,在沙盒环境下运行软件获取其动态调用序列(API),并通过滑动窗口划分得到窗口子序列;其次,引入多示例学习和注意力机制来构建层次化特征抽取的深度神经网络,使用循环神经网络抽取API特征,结合两个注意力机制分别抽取窗口特征和序列特征,并使用序列特征检测恶意软件;最后,使用真实数据训练网络,以便使用得到的模型对未知恶意软件进行检测。基于真实数据集的实验结果表明,窗口特征抽取层和序列特征抽取层能够有效学习窗口内和窗口间的注意力权重,从而更好地描绘序列的特征,提升模型的查准率和查全率。G2ATT对未知恶意软件检测的准确率达到98.19%,查准率达到98.78%,查全率达到97.60%,AUC (Area Under the Curve of ROC)达到99%,比基于API调用序列的SVM、随机森林、朴素贝叶斯等方法的准确率提高了10%以上。
基于区块链的对等网络信任模型
巫岱玥, 李强, 余祥, 黄郡
计算机科学. 2019, 46 (12): 138-147.  doi:10.11896/jsjkx.181202307
摘要 ( 517 )   PDF(2258KB) ( 921 )   
参考文献 | 相关文章 | 多维度评价
目前,在信任模型的信任评估过程中,评价数据的来源不统一,使得不同节点获取评价数据的能力不同,不同节点对数据的认可度也不同,从而导致计算结果精度不高且较为主观,难以作为参考。针对此问题,提出基于区块链的对等网络信任模型ChainTrust。首先,定义评价序列图,根据评估节点在网络中间接信任度的可靠程度来确定间接信任度的权重。同时,改进已有区块链结构,使用Merkle Patricia树和二叉Merkle树对评价数据进行存储,进一步提高评价数据的安全性,并给出对应的存储、读取算法。仿真与分析结果表明,ChainTrust能较好地抵御恶意攻击,有效降低共谋攻击对信任评估带来的影响,并能通过调整模型参数改变模型的敏感程度。因此,ChainTrust模型是有效的,且具有较高的灵活性和普适性。
基于正交编码的大数据纯文本水印方法
李兆璨, 王利明, 葛思江, 马多贺, 秦勃
计算机科学. 2019, 46 (12): 148-154.  doi:10.11896/jsjkx.181001972
摘要 ( 356 )   PDF(2277KB) ( 1641 )   
参考文献 | 相关文章 | 多维度评价
数据泄露是大数据应用面临的重要挑战之一。数字水印技术是实现数据追踪和版权保护的有效手段。当前的数字水印方法主要针对终端用户的多媒体文件流转场景,如图像、音视频等,缺少面向大数据环境的文本数据泄露防护的数字水印研究。文中提出了一种基于正交编码的大数据纯文本水印方法,该方法通过编码将明文水印转换为二进制字节流,设计基于行散列值和基于行序置换的正交编码水印方法。首先对二进制水印串分段,按照每行内容的散列值计算待嵌入水印段号,将对应水印段按照自定义规则转换为不可见字符串后嵌入到文本行末;再调整行序,使得每行内容的散列值与加入标志位的二进制水印串对应,以此将水印嵌入大数据纯文本中。水印提取方法为嵌入方法的逆过程。所提方法能够抵抗大数据环境下复杂数据行序变换运算等操作对水印的破坏,同时通过嵌入脆弱水印来达到文本篡改检测的效果。基于所提方法设计并实现了一个大数据纯文本水印系统,采用Spark分布式处理架构来解决海量文本的水印嵌入和提取性能问题,达到了对数据泄露快速追踪溯源的目的,提高了大数据的安全性。实验和理论分析证明,该方法具有较好的水印容量性能和良好的隐蔽性,同时能够抵御多种内容攻击;由于纯文本没有格式,格式攻击对该方法无效,其具有良好的鲁棒性。
基于双区块链的基站动环信息监控系统
樊建峰, 李轶, 吴文渊, 冯勇
计算机科学. 2019, 46 (12): 155-164.  doi:10.11896/jsjkx.190300041
摘要 ( 352 )   PDF(2881KB) ( 759 )   
参考文献 | 相关文章 | 多维度评价
基站动环监控系统通过将基站智能监控单元构建在底层被监控的智能和非智能设备之上,实现全网基站动环信息的监控、实时告警等功能。因此,动环监控系统的稳定是安全运行的前提。但随着基站数量的增加,现阶段中心服务器架构模式下的系统会显现出负载增加、流量过载等问题,且多对一的模式下容易出现DoS攻击、数据泄露等安全问题;另外,在多用户模式下,现有的系统模式无法达到对细粒度访问权限的控制。针对上述问题,结合区块链技术在分布式架构上独特的优势,文中提出一种基于改进型PBFT共识算法的双区块链基站动环监控系统架构,来解决现有动环监控系统中心化、安全、扩展等问题。具体地,该系统是一种层次型架构的信息系统,且各层次各维护一条区块链,是一个多节点共同维护与共享的双链区块链系统。其中,一条以联盟链的形式负责跨域信息的流转和权限的控制,另一条以私有链的形式负责基站设备访问权限的控制以及基站事务信息的流转。同时,基于PKI系统和密钥管理系统的支持,以及改进型区块头对权限信息的存储,达到对设备的细粒度访问权限的控制。最后,定性分析的结果表明了,相较于现有的传统动环监控系统,文中系统具有多中心服务、抗DoS攻击、基于用户的细粒度权限管理、信息的加密完备程度高和扩展性好等特点。
一种基于知识图谱的扩展攻击图生成方法
叶子维, 郭渊博, 李涛, 琚安康
计算机科学. 2019, 46 (12): 165-173.  doi:10.11896/jsjkx.190400092
摘要 ( 910 )   PDF(1658KB) ( 2316 )   
参考文献 | 相关文章 | 多维度评价
现有攻击图生成和分析方法主要依赖漏洞评分信息,无法判断软硬件环境等外部因素对漏洞评分的影响并进行修正,导致生成的攻击图难以精确反映节点和路径的真实风险程度。知识图谱中信息抽取和知识推理等工具是对多源途径获取的漏洞相关信息进行融合的有效手段,可以更准确地反映网络中节点和路径的风险程度。首先,设计了基于原子攻击本体的知识图谱,以对攻击图的输入和显示信息进行扩展;然后,提出了基于知识图谱的扩展攻击图生成框架,并在此基础上给出了攻击图生成算法以及攻击成功率、攻击收益的计算方法,从而实现了对漏洞更全面和精确的评分;最后,通过实验验证了所提方法的有效性。
基于区块链的医疗信息安全存储模型
王辉, 周明明
计算机科学. 2019, 46 (12): 174-179.  doi:10.11896/jsjkx.181102034
摘要 ( 575 )   PDF(1773KB) ( 1223 )   
参考文献 | 相关文章 | 多维度评价
我国医疗信息化的现状显示,传统的电子数据模式在医疗信息存储方面存在以下两个问题:1)电子数据规范性较差,流通慢;2)电子数据安全性和隐私性易受到威胁。针对各个医疗信息系统之间存在的信息存储安全问题和信息间的共享问题,结合区块链的共识机制、加密机制、点对点网络等技术,提出了一种基于区块链的信息管理方案来实现医疗信息的存储和共享,该方案具有不可篡改、去中心化等特点。通过改进的拜占庭协议实现网络节点的共识,通过访问控制机制达成医疗信息的共享,通过区块链来保存医疗信息的公共信息,而就诊的真实数据被加密保存在数据库或者云中,方便且有效地实现了敏感医疗数据的存储和系统之间的信息共享。在联盟链的环境下选取若干网络节点进行性能测试,实验结果表明,所提方案在防篡改、隐私保护等安全保护方面和吞吐量等性能方面具有较好的表现。此外,所提方案提出的索引机制能够实现快速检索,提高检索效率。通过搭建测试网络,证明了所提方案在医疗信息存储方面的可行性。所提方案利用区块链技术进行去中心化和不可篡改的管理,能够极大地提高医疗服务效率,提升医疗服务质量,为进一步研究区块链底层技术和探索区块链技术在医疗信息领域的应用奠定了良好的基础。
一种基于区块链技术的多阶段级联无线安全认证方案
胡兆鹏, 丁卫平, 高瞻, 朱晓辉, 王杰华
计算机科学. 2019, 46 (12): 180-185.  doi:10.11896/jsjkx.181102170
摘要 ( 328 )   PDF(1397KB) ( 839 )   
参考文献 | 相关文章 | 多维度评价
区块链技术具有去中心化、去信任、匿名、数据不可篡改等优势。为了更有效地保证用户能够安全识别并连接无线网络,文中提出了一种基于区块链技术的多阶段级联无线安全认证方案(MWSASB)。MWSASB方案设计多阶段级联协议过程,即注册阶段、登录与认证阶段以及交易阶段,并利用工作量证明机制PoW算法和延长最长链的方法,将用户信息产生交易记录在不可篡改且去中心化的区块链账本中。首先,在注册阶段,用户输入注册信息,在去中心化网络中利用密码学技术以及共识机制使得注册信息存储在区块链的每一个节点上;同时,在登录与认证阶段,用户输入登录信息,用户与区块链服务器进行登录与认证,在认证成功后以同样的方式将登录信息存储在区块链的每一个节点上。其次,在交易阶段,利用共识机制确保注册信息和登录与认证信息以交易形式安全记录在区块链中。最后,对MWSASB方案进行安全性和运算量分析。实验结果表明,在安全性方面,MWSASB方案具有无线安全认证等安全属性,有效避免了各种常见的网络攻击,如中间人攻击、DDoS攻击等;在运算量方面,利用区块链不可篡改机制,使用密码学算法和共识机制进行加密认证,能有效减少运算次数,提升安全认证效率。
基于可撤销外包属性加密的二维码加密
高丹, 凌捷, 陈家辉
计算机科学. 2019, 46 (12): 186-191.  doi:10.11896/jsjkx.181102187
摘要 ( 443 )   PDF(1676KB) ( 655 )   
参考文献 | 相关文章 | 多维度评价
二维码技术应用广泛,性能优越,但传统的二维码技术的安全性较低,仅适合单一权限对单一信息的扫码获取,不能实现不同权限用户扫码获取不同信息的功能。密文策略属性加密(CP-ABE)作为一种细粒度的数据加密方式,可在保证数据安全的同时实现对用户的访问控制,实现一对多模式的信息传输获取。结合二维码和密文策略属性加密技术的特点和优点,提出一种基于可撤销外包属性加密的二维码加密方案,对基于权限划分的信息块进行二次加密后外包给服务器进行相应的解密和权限匹配,再把初次解密的密文返回给用户,用户通过扫码获得私钥后进行二次解密得到明文,二维码的生成可随随机密钥的不同而变化。通过方案的安全性分析,证明了该方案具有前向安全、后向安全和在双线性q-BDHE假设下的选择明文攻击安全(IND-CPA);通过设计的实验,验证了方案在保障二维码信息安全的同时,可实现二维码的一对多的信息有选择获取,具有用户端计算开销低、属性可撤销、二维码生成随机的优点。
软件与数据库技术
融合文本与分类信息的重复缺陷报告检测方法
范道远, 孙吉红, 王炜, 涂吉屏, 何欣
计算机科学. 2019, 46 (12): 192-200.  doi:10.11896/jsjkx.181102232
摘要 ( 484 )   PDF(1743KB) ( 806 )   
参考文献 | 相关文章 | 多维度评价
软件缺陷是软件出现错误、故障的根源。软件缺陷是需求分析不合理、编程语言不严谨、开发人员缺少经验等因素导致的。软件缺陷不可避免,提交缺陷报告是发现缺陷并改进缺陷的重要途径。缺陷报告是描述缺陷的载体,对缺陷报告的修复是完善软件的必要手段。维护人员和用户因同一缺陷重复提交报告,导致缺陷报告库中存在大量冗余的报告,手动分诊已无法适应越来越复杂的软件系统。重复缺陷报告检测能过滤缺陷报告库中冗余的重复报告,并将人力与时间投入到新的缺陷报告上。当前研究方法的预测准确率始终不高,其难点在于寻找一个合适且全面的方法来衡量缺陷报告之间的相似性。借鉴集成方法的思想,提出了一种基于文本信息、分类信息相融合的重复缺陷报告检测方法——BSO(combination of BM25F、LSI and One-Hot)。在数据预处理的基础上,文中将重复缺陷报告分割为文本信息域与分类信息域。在文本信息域上使用 BM25F与LSI算法,得到两个方法的相似性打分,运用相似性融合方法将两个方法的相似性打分进行整合;在分类信息域上使用One-Hot算法得到相似性打分。运用相似性融合方法,融合文本信息域与分类信息域的相似性打分,为每个缺陷报告对应一个重复缺陷报告推荐列表,并计算重复缺陷报告检测的准确率。 利用Python语言,在公开的数据集OpenOffice上与基线方法以及较新水平方法REP、DBTM进行对比。实验结果表明,与DBTM相比,本文方法的准确率平均提高了4.7%;与REP方法相比,本文方法的准确率平均提高了6.3%;与基线方法相比,本文方法的准确率提升较高。实验结果充分证明了BSO方法的有效性。
一种基于重叠社区发现的软件特征提取方法
刘春, 张国良
计算机科学. 2019, 46 (12): 201-207.  doi:10.11896/jsjkx.181001856
摘要 ( 362 )   PDF(1332KB) ( 670 )   
参考文献 | 相关文章 | 多维度评价
近年来从软件产品的文本描述中提取软件特征获得了大量关注。考虑到产品文本描述中的句子能够更加清晰地表达一个特征的含义,并且文本描述中的每个句子可能会涉及多个软件特征,文中提出了一种通过发现软件产品文本描述中重叠的句子聚簇来提取软件特征的方法。基于复杂网络中的LMF重叠社区发现算法,所提方法通过自定义文本描述中句子之间的相识性度量,构建句子之间的相似性网络,然后发现句子相似性网络中的句子社区,实现对句子的聚类。每个句子社区蕴含一个软件特征,包含了所有潜在描述该软件特征的文本句子。所发现的句子社区可能存在重叠的句子,这些重叠句子同时涉及多个句子社区所蕴含的软件特征。进一步,为了帮助人们更好地理解句子社区所蕴含的特征,所提方法设计了相应的算法来从所有句子社区中依次选择熵最小的社区,并从所选社区中挑选最有代表性的、且其他社区还未选择的句子来作为一个社区所蕴含特征的描述符。文中爬取Softpedia.com网站的软件产品文本描述信息作为实验数据。实验结果表明,所提方法与现有代表性方法相比在准确性与时间方面具有更好的表现。
一种动态约简的多目标测试用例优先级排序方法
张娜, 徐海霞, 包晓安, 徐璐, 吴彪
计算机科学. 2019, 46 (12): 208-212.  doi:10.11896/jsjkx.181102106
摘要 ( 273 )   PDF(1327KB) ( 729 )   
参考文献 | 相关文章 | 多维度评价
针对蚁群算法在求解MOTCP问题时存在收敛速度慢、易陷入局部最优等缺陷,提出了一种动态约简的在线指导蚁群信息素更新的多目标测试用例优先级排序方法。该方法引入一种动态约简的思想,首先根据各测试用例覆盖需求的情况,对覆盖有相同需求的初始测试用例集进行初次约简。其次,根据测试用例在执行过程中能否检测出错误以及检测出的错误的严重程度来设计一种测试用例失效度的判别方法,在蚁群每一次迭代后均对未检测出错误的测试用例进行二次约简,以减少下一轮迭代时蚁群需要经过的测试用例数,通过两次约简大幅度缩短排序时间。同时,在蚁群的每次迭代过程中,考虑测试用例的重要度、失效度和实际执行时间3个因子对下一轮信息素的影响,设计一种同时在3个影响因子下在线指导更新蚁群信息素的方法,使蚁群能够更快更准确地寻找到下一个测试用例。最后,将该方法、传统蚁群排序方法和多目标优化排序方法分别应用于多个开源软件程序进行实验比较。仿真实验结果表明,所提动态约简的在线更新信息素的优先级排序方法在缺陷检错能力以及有效执行时间等性能指标方面均有较大优势,能更早发现等级较高的错误。
基于操作历史图的分布式Key-Value数据库一致性检测算法
廖彬, 张陶, 李敏, 于炯, 国冰磊, 刘炎
计算机科学. 2019, 46 (12): 213-219.  doi:10.11896/jsjkx.181102097
摘要 ( 380 )   PDF(1753KB) ( 574 )   
参考文献 | 相关文章 | 多维度评价
分布式数据库系统的副本机制在提高系统可靠性及性能的同时,导致了多副本数据管理的一致性问题;数据一致性的实现需要一致性协议模型来进行预防,也需要一致性检测算法对非一致数据进行检测。首先,对读写操作记录之间的时序关系、安全一致性及并行一致性原则等概念进行定义;其次,根据操作记录集合中读写操作之间的并行与时序关系,提取出操作记录集合向操作记录图转化的规则,并在此基础上设计了操作记录向历史记录图的转化算法;然后,以历史记录图为输入,设计了违反一致性查找算法,查找并返回图中所有违反安全与并行一致性读操作的集合;最后,基于Cassandra进行实验并将读写一致性设置为ONE,通过YCSB产生并行读写压力测试,与同类算法的对比实验验证了所提算法在功能与效率两方面的优越性。
人工智能
自动谈判及其基于模糊集的模型综述
罗旭东, 黄俏娟, 詹捷宇
计算机科学. 2019, 46 (12): 220-230.  doi:10.11896/jsjkx.190800129
摘要 ( 623 )   PDF(1375KB) ( 958 )   
参考文献 | 相关文章 | 多维度评价
谈判是两个或多个利益者为了达成协议进行交流沟通的过程,自动谈判就是用人工智能系统来自动化这一过程。文中首先讨论了自动谈判的研究意义。从国家层面上来看,研究和发展这样的系统是符合国家人工智能发展战略的,不仅能帮助人们在电子商务时代生活得更美好,而且能用计算机系统代替人工谈判来减少腐败现象。然后,勾画了关于谈判的研究在博弈论、管理科学和计算机科学中发展的脉络和趋势。在博弈论领域,是诺贝尔经济学奖获得者Nash开创了对谈判的研究。这类研究最大的问题是假设谈判的各方所有信息一定程度上是公开的,但这是不现实的。所以,管理科学领域的研究者着重研究了在各方所有信息不公开的情形下应该怎样进行人工谈判。一般,人工谈判是低效、困难的,并且常常不能达到最优的结果。于是计算机科学家就尝试用机器来代替人工谈判。早期主要研究计算机对计算机的自动谈判,现在研究的重点正转向计算机对人的自动谈判。最后,综述了将模糊逻辑和模糊约束应用于开发自动谈判智能代理的方法。文中着重说明了这两种模糊方法在自动谈判系统中的使用方法,以及模糊自动谈判系统的实际用途。
面向国防科技领域的技术和术语识别方法研究
冯鸾鸾, 李军辉, 李培峰, 朱巧明
计算机科学. 2019, 46 (12): 231-236.  doi:10.11896/jsjkx.190300069
摘要 ( 355 )   PDF(1395KB) ( 1319 )   
参考文献 | 相关文章 | 多维度评价
随着自然语言处理技术的发展,人们越来越重视构建面向国防科技领域的知识图谱。而面向国防科技领域的技术和术语识别是构建该领域技术知识图谱的基础。文中基于该领域的语料库,在技术和术语识别的任务上,探索了子词单元在传统序列标注Bi-LSTM+CRF模型上的应用。此外,针对任务的特点,提出了适用于技术和术语识别的语言学特征。基于该领域的语料库,实验结果表明技术和术语识别的F1值达到了71.80%,较基准系统提升了3.04%,能够较好地识别出面向国防科技领域的技术和术语。同时,所提方法也优于基于BERT模型的技术术语识别方法。
基于排序选择度量的自适应集成方法
沈先宝, 宋余庆, 刘哲
计算机科学. 2019, 46 (12): 237-241.  doi:10.11896/jsjkx.181102173
摘要 ( 260 )   PDF(1179KB) ( 711 )   
参考文献 | 相关文章 | 多维度评价
针对集成过程中基分类器的集成优先性缺少精确化度量而导致的模型选择严谨性不高、系统精简性设计难以实现的问题,文中提出了一种基于排序选择度量方式、自适应权重设置的集成分类方法。首先,利用K折交叉验证及设计的误差熵与分类器互补性相结合的组合指数度量方法,选出集成优先性最高的两个分类器;然后,通过构造的以组合指数为基础的整体组合指数度量方法,实现对不同模型的优先性排序选择;最后,通过设置自适应权重的方式为不同模型找到最佳权重进行集成分类。在UCI数据集上的实验结果表明,所提方法与其他分类模型相比,各项分类评价指标均有提高,验证了该集成方法的可行性。该方法通过设计的模型选择定量性依据及自适应权重设置机制,使得整个集成分类系统具有模型选择分层性、可自适应精简化的特点。
反馈机制的实体及关系联合抽取方法
马建红, 李振振, 朱怀忠, 魏字默
计算机科学. 2019, 46 (12): 242-249.  doi:10.11896/jsjkx.181102117
摘要 ( 368 )   PDF(1893KB) ( 1257 )   
参考文献 | 相关文章 | 多维度评价
实体及关系抽取是信息抽取中的两个核心任务,是构建知识图谱的重要基石。对于实体识别和关系抽取,当前通常采取人工提取特征和规则,分独立两步实现的方法,这种方法易造成数据重复预处理和错误传播。实体识别和关系抽取两个模块存在相互关联性,实体识别是进行关系抽取的基础,实体关系抽取结果又可反馈校验实体信息。因此,文中提出无须添加人工特征和引入互反馈机制的混合神经网络模型(Mufeedback-Join Model)来完成实体及其关系的联合抽取,实现实体关系对实体识别的反馈校验机制。该模型共享Bi-LSTM特征提取层来提取文本上下文特征,依据共享层特征引入Attention机制捕获关键局部特征来完成解码,再用条件随机场CRF完成实体序列的标注任务,融合共享层特征和实体特征,并将其输入到CNN模型来实现实体关系的抽取,最后计算关系抽取结果的损失值,再联合实体识别损失值反馈修正特征提取层和实体识别模型参数。将此算法应用在实体数据集上进行实验,在同等硬件环境下,该方法可以缩短的模型训练时间,提升实体及关系抽取的准确率、召回率和F1值,联合抽取的F1值整体提升了3.91%,实体识别子模块的F1值平均提升了1.34% ,关系抽取的F1值提升了5.79%。实验数据说明,联合抽取模型可以实现两个子模块的合并,从而缩短数据处理时间和减少错误数据的传递;相互反馈的机制可以提升整体识别效果。
面向多尺度的属性约简加速器
姜泽华, 王怡博, 徐刚, 杨习贝, 王平心
计算机科学. 2019, 46 (12): 250-256.  doi:10.11896/jsjkx.181102031
摘要 ( 343 )   PDF(2258KB) ( 663 )   
参考文献 | 相关文章 | 多维度评价
邻域粗糙集,采用半径的方式度量样本之间是否相似,因而不同大小的半径自然地构成了不同尺度意义下的粗糙近似。基于邻域粗糙集的属性约简问题往往需要在多个不同半径上求解约简,其目的是找到具有较好泛化性能的属性子集,或探讨不同尺度意义下约简性能的变化趋势。但值得注意的是,利用传统的启发式算法在多个半径所对应的多尺度意义下进行约简求解时,往往需要在所有尺度上逐一重复执行这一算法,时间消耗较大,特别是尺度个数较多的情况下,时间消耗会变得更高。为解决这一问题,借助半径的变化,文中提出了面向多尺度的约简求解加速策略。这一策略在分别考虑半径从小到大和从大到小的变化趋势的情况下,同时缩小了样本和属性的遍历规模,将当前半径下约简的求解过程建立在上一个半径所求得约简的基础上,利用启发式搜索进行正向或逆向的属性增加及删除操作。为验证所提加速策略的有效性,实验选取8个UCI数据集,采用十折交叉验证的方法求取20个半径下的约简,对比不同方法求解约简的时间消耗和分类性能。实验结果表明,与利用传统的启发式算法在每一个尺度意义下单独求解约简的方法相比较,文中所提出的正向或逆向加速搜索方法可以在保持分类性能不发生显著变化的情况下,极大地降低多尺度意义下求解约简的时间消耗,并且有效地降低过拟合的程度。
不协调决策形式背景的属性约简
李仲玲, 米据生, 解滨
计算机科学. 2019, 46 (12): 257-260.  doi:10.11896/jsjkx.181102137
摘要 ( 254 )   PDF(1194KB) ( 548 )   
参考文献 | 相关文章 | 多维度评价
形式概念分析由德国数学家Wille于1982年提出,是刻画概念和概念之间层次化结构的数据分析工具,主要用于概念的发现、排序和显示。作为知识发现的有效工具,该理论已被成功地运用到信息检索、数据挖掘、模式识别等领域。而在实际问题中呈现出的形式背景往往具有冗余的属性,使得所生成的概念格结构非常复杂。为了提取更加简洁有效的概念格,需要对形式背景中的属性进行约简。因此,寻找更高效的属性约简方法成为了形式概念分析中的一个重要研究问题。文中把基于粗糙集理论的属性约简思想引入到形式背景中,进一步研究不协调决策形式背景的属性约简问题。一些学者在不协调信息系统中基于等价类提出了分布约简、最大分布约简、分配约简、近似约简,并且讨论了4个约简之间的关系。而形式背景是一种特殊的信息系统,文中用粒集代替信息系统中的等价类,提出了4种基于包含度的属性约简,即分布约简、最大分布约简、分配约简与上近似和约简,并证明了分布协调集必为最大分布协调集,分布协调集必为分配协调集,分配协调集与上近似和协调集等价等结论。最后以分配约简为例,给出了分配协调集的判定定理,构建了不同粒集之间的可辨识属性集合,得到了求解分配约简的布尔计算方法。
基于属性重要度的变精度邻域粗糙集属性约简算法
郑文彬, 李进金, 何秋红
计算机科学. 2019, 46 (12): 261-265.  doi:10.11896/jsjkx.181102184
摘要 ( 558 )   PDF(1274KB) ( 790 )   
参考文献 | 相关文章 | 多维度评价
邻域粗糙集理论主要用于知识发现、属性选择、决策分析和数据挖掘等领域,能够根据数据的特点选择合适的离散化策略,在处理模糊和不确定性知识方面表现良好。但是,传统粗糙集属性约简算法存在难以确保获得约简、约简后的粗糙集属性识别准确率低等不足。对此,文中提出了一种基于属性重要度的属性约简算法。在充分考虑现有条件信息熵多方面不足的基础上,借鉴变精度邻域粗糙集理论对阈值参数进行重选,以新的条件信息熵作为度量基准,根据决策信息系统中的偏好属性推导出偏好决策规则集。对偏好决策规则集进行粗糙规则提取,并通过邻域粒化方法建立了变精度邻域粗糙集模型。该模型在处理大规模粗糙集属性数据时,计算时间较长,冗余属性过多。针对该问题,给出了一种属性重要度评价策略,在此基础上通过融合多叉树理论设计了变精度邻域粗糙集属性约简算法。实验结果表明,与传统方法相比,所提算法的属性识别准确率为92%,提高了10%左右,这充分验证了所设计的属性约简算法具有较强的有效性和较高的应用价值。
图形图像与模式识别
一种基于CSI的非合作式人体行为识别方法
李晓薇, 余江, 常俊, 杨锦朋, 冉亚鑫
计算机科学. 2019, 46 (12): 266-271.  doi:10.11896/jsjkx.190200349
摘要 ( 438 )   PDF(3080KB) ( 1078 )   
参考文献 | 相关文章 | 多维度评价
目前,基于Wi-Fi的无线人员感知技术被广泛应用于防入侵安全监测、人类健康护理、步态识别等领域,对此提出了一种基于无设备的非合作式人体行为识别方法,利用Wi-Fi信号的信道状态信息CSI来识别5个动态活动:行走、坐-站、深蹲、跳跃和跌倒。该方法利用SIMO系统采集CSI数据,在对CSI幅度和相位分别进行预处理之后,实施3个步骤来降低计算开销机制:子载波融合、基于移动方差阈值的不良数据链路剔除以及基于小波变换的动态时间窗口的数据分割。在经过前期的各项预处理后提取动作特征,从时域扩展到频率域,通过分析多普勒功率谱的特性来提高CSI信号的利用率。实验结果表明,总体识别率随着使用特征维度的增加而上升;组合分类器加权投票方法经过两轮投票优化,把对5个动作的总体识别率提高到90.3%,且相较于RSSI,CSI在人体行为识别领域的优势更加明显。
基于深度学习的交通信号灯快速检测与识别
钱弘毅, 王丽华, 牟宏磊
计算机科学. 2019, 46 (12): 272-278.  doi:10.11896/jsjkx.190400026
摘要 ( 561 )   PDF(2494KB) ( 2105 )   
参考文献 | 相关文章 | 多维度评价
交通信号灯检测与识别技术能够辅助司机做出正确的驾驶决策,减少交通事故的发生,为无人驾驶的实现提供安全保障。针对交通信号灯检测场景复杂多变、目标通常占检测数据集图片的比例极小等技术难点,提出了一种基于深度学习的交通信号灯快速检测与识别算法。整体框架包括如下3部分:基于启发式的图像预分割,用于缩小搜索范围,提升信号灯面板在输入图像中的相对大小和检测精度;基于深度学习的检测与识别,利用卷积神经网络准确地检测与识别信号灯;利用NMS(Non-Maximum Suppression)算法去除上一阶段中重复的检测框。提出的Split-CS-Yolo模型在LISA数据集上取得了96.08%的mAP和2.87%的漏检率,相比Yolo系列的其他方法,其不仅有更高的准确率和更低的漏检率,还将模型大小缩小到原始Yolov2的8.6%,使得检测速度提升了63%。
使用模糊聚类的胶囊网络在图像分类上的研究
张天柱, 邹承明
计算机科学. 2019, 46 (12): 279-285.  doi:10.11896/jsjkx.190200315
摘要 ( 412 )   PDF(1422KB) ( 1068 )   
参考文献 | 相关文章 | 多维度评价
胶囊网络中动态路由的本质就是聚类算法思想的实现。考虑到已有胶囊网络中的聚类方式需要数据满足一定的分布才能达到最好的效果,且图像特征比较复杂,于是将一种普适性更好的模糊聚类算法作为胶囊网络中的特征整合方式,并添加了一个使用信息熵来度量不确定性的激活值,以区分同一级别胶囊层特征的显著性。同时,借鉴特征金字塔网络的思想,将不同胶囊层的特征采样成相同尺度,然后进行融合独立训练。基于Keras框架进行实验,其结果表明,相比原来的胶囊网络,这种具有新型结构的胶囊网络在MNIST和CIFAR-10上有更高的识别准确率。对比实验证明了模糊聚类算法在胶囊网络上的应用潜力,其改善了原胶囊网络中聚类算法存在局限的问题;也证明了对胶囊网络中不同层的特征进行融合,能够获得包含信息更丰富且表达能力更强的特征。
基于词向量融合的遥感场景零样本分类算法
吴晨, 袁昱纬, 王宏伟, 刘宇, 刘思彤, 全吉成
计算机科学. 2019, 46 (12): 286-291.  doi:10.11896/jsjkx.181202257
摘要 ( 418 )   PDF(3163KB) ( 923 )   
参考文献 | 相关文章 | 多维度评价
零样本分类算法无须标注要识别的类别样本,因而能大幅度降低实际应用成本,近年来受到广泛关注。遥感场景类别的语义词向量与图像特征空间原型的结构不一致问题,严重影响了遥感场景零样本的分类效果。利用不同词向量间的互补性,文中提出一种基于语义词向量融合的遥感场景零样本分类算法,即耦合式解析字典学习(Coupled Analysis Dictionary Learning,CADL)方法。首先,采用稀疏编码效率较高的解析字典学习方法获取各语义词向量的稀疏系数,以减少冗余信息;然后,将对应的稀疏编码系数串接后作为融合语义词向量表示,并将融合语义词向量线性映射到图像特征空间,与图像特征空间场景类别原型表示进行结构对齐,以降低结构差异性;最后,计算得到要识别的场景类别的图像特征原型,并采用最近邻分类器在图像特征空间完成分类。在UCM和AID数据集上对多种语义词向量的融合进行定量实验,同时将RSSCN7数据集作为已知场景类别的数据集来对两幅实际遥感图像进行定性实验。在UCM和AID上的定量实验分别获得了最高总体分类准确度48.40%和60.23%,相比于典型零样本分类方法的总体分类准确度分别提升了4.80%和6.98%。对两幅实际遥感图像的定性实验,同样获得了最佳零样本的分类效果。实验结果表明,多种语义词向量融合,可以获得与图像特征空间原型结构更一致的语义词向量,且显著提升了遥感场景零样本分类的准确度。
基于可穿戴设备的心电图自适应分类算法研究
樊敏, 王晓锋, 孟小峰
计算机科学. 2019, 46 (12): 292-297.  doi:10.11896/jsjkx.190500181
摘要 ( 561 )   PDF(1597KB) ( 1322 )   
参考文献 | 相关文章 | 多维度评价
目前,心血管疾病已成为全球人类非传染性死亡的主要原因,死亡人数约占全球死亡总人数的1/3,且患病人数逐年增加。可穿戴设备被用于对心电图进行自动分类,以实现对心血管疾病的早监测、早预防。随着边缘机器学习和联邦学习的兴起,小型机器学习模型成为了人们关注的热点。针对可穿戴心电图设备低配置、低功耗及个性化的特点,文中研究了一种基于LSTM的轻量级网络结构,并采用自适应算法来优化病人个体的心电图分类模型。该模型利用MIT-BIH公开数据集开展实验,将VEB和SVEB的分类效果与其他相关研究进行了比较。实验结果表明,所提算法的模型结构简单且分类识别率高,能够满足可穿戴设备对病人心电图监测的需求。
基于无监督学习的二维工程CAD模型端到端检索算法
曾凡智, 周燕, 余家豪, 罗粤, 邱腾达, 钱杰昌
计算机科学. 2019, 46 (12): 298-305.  doi:10.11896/jsjkx.190900003
摘要 ( 382 )   PDF(2795KB) ( 1056 )   
参考文献 | 相关文章 | 多维度评价
针对企业产品制造过程中海量的计算机辅助设计(Computer Aided Design,CAD)模型的高效检索难题,文中研究了一种基于二维CAD模型内容特征的检索算法,构建了一个可用于CAD的DXF格式源文件模型库的检索系统原型。首先,通过对二维CAD模型的DXF文件结构进行分析,来研究模型中的图元规律并进行形状重构;其次,依据图元特点,提出了基于统计直方图、二维形状分布和傅里叶变换共3类内容特征的提取方法;最后,设计了基于无监督学习的多特征融合框架及相似度计算方法,从而提取出了模型的融合特征描述子并实现了二维CAD模型检索。实验结果表明,文中提取的融合特征相较于单一特征包含了更加丰富的内容特征且具有高效的鉴别力。该系统可以直接应用于产品个性化定制、设计重用等方面,有助于企业进一步提升智能制造能力。
交叉与前沿
基于多模融合的半监督场景识别方法
沈鸿, 刘军发, 陈益强, 蒋鑫龙, 黄正宇
计算机科学. 2019, 46 (12): 306-312.  doi:10.11896/jsjkx.191200500C
摘要 ( 473 )   PDF(1913KB) ( 1073 )   
参考文献 | 相关文章 | 多维度评价
场景识别是普适计算中的一项重要研究内容,旨在通过识别智能手机用户所在位置的场景,为用户提供精准的个性化服务并提升服务的质量。在实际环境中,精确的场景识别存在两个问题:(1)基于单模传感器数据或无线信号数据的分类效果不佳、普适性不足;(2)场景识别的精度需要依赖大量标定数据,导致成本较高。针对这些问题,提出一种基于多模融合的半监督场景识别方法,该方法充分利用Wi-Fi、蓝牙和传感器的多模特征来提高识别精度。相比基于单模数据的识别,融合特征将静态场景的分类精度提升了10%,并且本文通过构建半监督的学习方法解决了动态场景中数据采集成本高的问题,在将标定数据量减少一半的基础上将识别精度提高至90%以上。实验数据表明,在利用Wi-Fi、蓝牙、传感器的互补优势的基础上,引入半监督的学习方法能够提升场景识别的精确度且降低在某些场景下采集数据的成本,从而有效地提升了场景识别的精度和普适性。
面向PCP-MS数据的PPI网络推断算法
陈征, 田博, 何增有
计算机科学. 2019, 46 (12): 313-321.  doi:10.11896/jsjkx.181102215
摘要 ( 448 )   PDF(3391KB) ( 1032 )   
参考文献 | 相关文章 | 多维度评价
随着蛋白质组学的发展,研究者们开始聚焦于人类的全部蛋白质相互作用(Protein-Protein Interaction,PPI)网络的建立,质谱分析技术已成为预测蛋白质相互作用的代表方法。质谱技术是构建蛋白质相互作用网络的主要实验手段之一,基于质谱技术产生了大量的蛋白质纯化数据,如AP-MS数据和PCP-MS数据等。这些数据为PPI网络的构建提供了重要的数据支持,但是通过人工的手段来构建PPI网络不仅低效,而且很不现实。因此,面向PCP-MS数据的网络推断算法是生物信息学研究的一个热点问题。文中针对一类主流的质谱(PCP-MS)数据的PPI网络构建算法问题开展研究,从解决目前存在的瓶颈问题出发,达到构建高质量PPI网络的目的。现有的面向PCP-MS数据的PPI网络推断算法的研究还处于初级阶段,相关方法较少。同时,算法结果的质量还存在着一些问题:1)很多错误的相互作用被包含在不同的推断算法结果中,同时一些正确的相互作用在结果中被遗漏;2)不同的推断算法在同一数据集上的表现差异较大;3)对于不同的数据集,同一算法表现性能的波动方差较大。因此,为了从PCP-MS数据中推断出结构可靠、质量较高的PPI网络,文中提出一种基于相关性分析与排序整合的PPI评分方法。该方法基于无监督学习,包括以下两个步骤:1)计算蛋白质之间的相关系数,得到多组相关性结果;2)采用排序整合的方法对多组结果进行整合,得到整合后的PPI分数。实验结果表明,所提方法在不使用参考标准的情况下,可以达到与有监督学习方法接近的结果。
从属度树算法检测复杂网络重叠社团
付立东, 李丹, 李占利
计算机科学. 2019, 46 (12): 322-326.  doi:10.11896/jsjkx.190200293
摘要 ( 272 )   PDF(1523KB) ( 598 )   
参考文献 | 相关文章 | 多维度评价
重叠社团检测一直是复杂网络研究领域的重点和难点。由于真实网络普遍存在层次结构,结合层次性的重叠社团检测方法将更适用于现实世界复杂网络的研究分析,但目前这类方法的研究还比较少。因此,在定义复杂网络节点领导度、从属度概念的基础上,结合网络层次性建立数学模型,提出了新颖的从属度树检测重叠社团算法。该算法根据从属度值建立从属度树,通过划分树发现重叠节点和重叠社团。在人工网络实验中证明了从属度树算法可以结合层次性发现重叠节点,在Dolphin网络和Karate网络上的实验验证了其检测重叠社团结果的可靠性。与已有一些算法比较的结果表明,从属度树算法能找到其他算法不能找到的重叠节点,以扩展模块度和实际社团结构作为从属度树算法划分重叠社团结果的评价指标。新算法的扩展模块度值大于对比算法,社团划分结果更接近实际社团结构。
基于个体异质传染率及状态转移的SIR模型分析
瞿倩倩, 韩华
计算机科学. 2019, 46 (12): 327-333.  doi:10.11896/jsjkx.181001974
摘要 ( 653 )   PDF(2309KB) ( 1063 )   
参考文献 | 相关文章 | 多维度评价
针对染病个体具有不同传染率的现象,基于复杂网络中的基本SIR传染病模型,提出了一种具有两种传染率且存在转移概率的传染病模型。根据地方病平衡点的存在性,求出了基本再生数R0。在此模型上,分析了随机免疫和目标免疫两种常见免疫策略。通过仿真模拟发现:在同等条件下,R0>1时,疾病在异质网络中比在同质网络中传播速度更快,范围更广;R0<1时,网络结构对疾病传播的影响不大。进一步研究得出:网络中初始染病节点度的越大,疾病传播速度越快且感染峰值越大;初始染病节点的接近度中心性越大,疾病传播速度越快且范围更广;点集聚系数对传播过程的影响不大;基本再生数R0随转移概率的增大而减小,增大转移概率能有效减少疾病的传播;在平均免疫率相同的情况下,目标免疫比随机免疫更有效。
基于行为轮廓的业务流程隐变迁挖掘方法
宋健, 方贤文, 王丽丽, 刘祥伟
计算机科学. 2019, 46 (12): 334-340.  doi:10.11896/jsjkx.180901654
摘要 ( 274 )   PDF(2243KB) ( 604 )   
参考文献 | 相关文章 | 多维度评价
在业务流程优化过程中,从非频繁行为中挖掘隐变迁是重要任务之一。从非频繁行为中挖掘隐变迁,能够更好地还原流程模型,提高流程的运行效率。文中依据行为轮廓的理论,在频率较高的日志中进行挖掘以获得初始模型。首先利用合理性阈值对事件日志进行过滤,得到有效的低频序列日志;其次利用低频序列日志优化初始模型,通过对各活动间行为轮廓关系与源模型的对比,来找到变化的区域,将可能存在的隐变迁挖掘出来;然后通过优化指标对挖掘到的隐变迁进行进一步验证,从而得到完整的含隐变迁的过程模型;最后通过具体的事例以及仿真对所构建的模型进行分析,并验证该方法的有效性。