计算机科学

黄俏娟, 罗旭东

计算机科学. 2018, 45 (12): 1-11. doi:10.11896／j.issn.1002-137X.2018.12.001

摘要 ( 2234 )

PDF(1447KB) ( 4279 )

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

人工智能并没有一个统一的定义,但若一个计算机系统能做人需要智能才能做的事,一般便认为这样的计算机系统具有人工智能。因此,人工智能被广泛应用于许多需要人类智能的领域,如法律、医疗、金融、电子商务等,其中法律是当前的一个重要应用领域。因此,文中主要从立法(人工智能系统辅助立法以及立法监管人工智能系统,特别是自主驾驶汽车)、知法守法(法律信息的检索、法律文书的生成和审核)、司法(证据收集、法律推理以及在线纠纷解决)等方面综述了人工智能和法律结合的研究现状以及发展趋势,希望能引导更多人投入这个研究领域。

区块链系统的数据存储与查询技术综述

王千阁, 何蒲, 聂铁铮, 申德荣, 于戈

计算机科学. 2018, 45 (12): 12-18. doi:10.11896／j.issn.1002-137X.2018.12.002

摘要 ( 1107 )

PDF(1924KB) ( 3383 )

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

目前,以比特币和以太坊为代表的区块链系统已经日趋成熟,区块链技术成为学术界与工业界的研究热点。然而,这些区块链系统在实际应用中因数据存储模式限制而普遍面临着查询功能简单、查询性能较低等严重问题。文中重点对区块链系统的数据存储与查询技术的研究进展进行综述与展望。首先,介绍当前流行区块链系统中使用的数据存储机制和查询处理策略。然后,详细介绍在现有区块链系统基础上扩展查询处理功能的两种方法,并从查询效率、写性能优化、存储空间占用、数据安全性和可用性5个方面对其进行对比和分析。最后,分析了未来区块链系统的查询技术发展趋势,探讨了其主要的研究方向。

DTN体系结构及关键技术研究综述

黄星河, 李艾静, 王海

计算机科学. 2018, 45 (12): 19-23. doi:10.11896／j.issn.1002-137X.2018.12.003

摘要 ( 626 )

PDF(2073KB) ( 1454 )

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

中断/延迟容忍网络(Disruption/ Delay Tolerant Network,DTN)是从Ad-hoc网络中抽象出来的一种全新的网络模型。与传统的无线移动自组织网络不同,该网络模型的应用场景具有高延迟、易中断等特点。高延迟、易中断的网络环境被称为受限网络。DTN作为一个针对受限网络的新兴研究领域,使用特殊的“存储-携带-转发”模式进行数据传递,以对抗受限网络中的高延迟和易中断带来的影响。它的发展将对未来军事战争、航天通信、抢险救灾等诸多场景提供更为可靠的通信保证。文中分析了DTN体系架构及其特性,研究了DTN路由协议并指出其适用的场景,最后总结了DTN研究中遇到的难点问题,并指出未来研究需要关注的方向。

网络资产探测技术研究

王宸东, 郭渊博, 甄帅辉, 杨威超

计算机科学. 2018, 45 (12): 24-31. doi:10.11896／j.issn.1002-137X.2018.12.004

摘要 ( 668 )

PDF(1620KB) ( 4417 )

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

随着网络技术的迅速普及,大量多样化的网络资产为人们的生产、生活提供了极大便利,同时也对其自身的安全管理提出了挑战。准确、全面地进行网络资产探测是实现网络资产有效管理的前提,也是进行威胁分析的基础。首先回顾了网络资产探测的起源与发展历程;然后全面分析了当前常见的3种新型网络资产探测方法(主动、被动和基于搜索引擎)及其关键技术,归纳了它们各自的特点;最后,探讨了该技术未来可能的研究方向。

物联网通信协议的安全研究综述

杨伟, 何杰, 万亚东, 王沁

计算机科学. 2018, 45 (12): 32-41. doi:10.11896／j.issn.1002-137X.2018.12.005

摘要 ( 383 )

PDF(2149KB) ( 1362 )

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

国际标准化组织IEEE和IETF正携手为物联网制定一套高可靠、低功耗、可接入互联网的无线通信协议栈。IEEE主要负责制定物联网通信协议的物理层和链路层的标准,如IEEE802.15.4-2006标准,其中IEEE802.15.4e是最新的链路层的标准。IETF主要负责制定物联网通信协议的网络层及以上标准,如6LoWPAN,RPL和CoAP标准,其可以将资源受限的传感器节点接入互联网。网络安全是物联网大规模发展的基础,必须设计一套安全高效的机制保障通信协议的正常运行。文中详细介绍了物联网通信协议栈,重点分析和讨论了其安全方面的最新研究进展。最后总结和展望了物联网安全通信协议的研究方向。

基于深度信息的动态手势识别综述

陈甜甜, 姚璜, 左明章, 田元, 杨梦婷

计算机科学. 2018, 45 (12): 42-51. doi:10.11896／j.issn.1002-137X.2018.12.006

摘要 ( 511 )

PDF(2291KB) ( 1603 )

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

随着计算机技术的飞速发展,自然、简单、非接触式的手势识别在人机交互方面备受青睐。动态的手势识别一直是人机交互领域研究的热点与难点,深度传感器的出现为手势识别的研究提供了更加鲁棒的数据。为了解动态手势的发展现状,在广泛调研现有文献和最新成果的基础上,对基于深度信息的动态手势从手势分割、手势建模、特征提取、手势识别4个方面进行阐述,介绍动态手势识别相关的应用领域,并对其中存在的难点与问题进行讨论。

轮胎花纹图像检索技术综述

刘颖, 张帅, 葛瑜祥, 王富平, 李大湘

计算机科学. 2018, 45 (12): 52-60. doi:10.11896／j.issn.1002-137X.2018.12.007

摘要 ( 420 )

PDF(4181KB) ( 1535 )

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

轮胎花纹图像检索在交通事故处理及刑事案件侦破中是获取破案信息的重要手段,虽然基于内容的图像检索技术已发展数十年,但由于轮胎花纹图像数据的来源及应用场景特殊等因素,目前这方面的研究文献并不多。在研究近年来轮胎花纹图像检索领域相关文献的基础上,对该领域的技术现状进行总结分析。首先,围绕轮胎花纹纹理特征提取和高层语义特征提取两项关键技术描述了该领域的主要研究成果,并总结了轮胎花纹数据库以及检索性能评价指标。然后,分别针对轮胎花纹低层特征和高层特征提取进行实验对比并分析结果。最后,结合现有技术及实际应用需求,分析了该领域的技术发展趋势并指出了未来的研究方向。

一种基于节点位置余弦相似度的机会网络转发算法

朱坤, 刘林峰, 吴家皋

计算机科学. 2018, 45 (12): 61-65. doi:10.11896／j.issn.1002-137X.2018.12.008

摘要 ( 263 )

PDF(3211KB) ( 648 )

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

针对机会网络中数据送达率较低的问题,文中根据节点历史接触信息即节点相遇次数、相遇时间长度、节点关系稳定性来计算节点转发效用值。首先选择通信范围内效用值最大的邻居节点作为初始转发节点,再根据余弦相似度选择其他转发节点,使得转发节点能够尽可能均匀地分布。在此基础上,提出一种基于节点位置余弦相似度的机会网络转发算法(Opportunistic Network forwarding algorithm based on Node Cosine Similarity,ONNCS)。该算法使得转发节点能够均匀地分布,因此数据报文能够尽快地被转发到目的节点。实验结果表明,ONNCS具有较高的转发成功率和较低的转发能耗,转发成功率高出其他算法5%～8%。

基于元胞遗传机制的虚拟网络映射算法

王明, 庄雷, 王国卿, 张坤丽

计算机科学. 2018, 45 (12): 66-70. doi:10.11896／j.issn.1002-137X.2018.12.009

摘要 ( 258 )

PDF(3319KB) ( 541 )

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

满足节点和链路约束条件的虚拟网络请求最优映射问题是NP-难问题,粒子群算法和遗传算法等启发式算法是解决这类问题的主要手段。这类启发式算法从数学模型优化的角度来求解问题,但未考虑虚拟网络映射节点本身的变化对最优解的影响,存在收敛速度较慢和容易陷入局部最优解的问题。文中将元胞遗传机制引入虚拟网络映射问题中,提出了虚拟网络映射算法VNE-CGA。该算法利用元胞自动机对节点建模,使用“B4567/S1234”规则来替代传统遗传算法中的交叉操作;通过对邻居的学习来指导个体的寻优过程,弥补了传统遗传算法的固有缺陷,最终提高了虚拟网络请求的接受率以及底层物理网络的运营收益。

基于位置吸引力的加权复杂供应链网络局域世界演化模型研究

赵志刚, 周根贵, 潘瑞芳

计算机科学. 2018, 45 (12): 71-76. doi:10.11896／j.issn.1002-137X.2018.12.010

摘要 ( 240 )

PDF(2082KB) ( 609 )

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

在一般局域世界演化模型的基础上,文章使得企业节点的初始位置值呈现幂率分布,以体现节点企业的不同角色。受万有引力定律的启发,用位置值的大小和远近值来定义节点企业间位置吸引力的概念,并应用吸引力规则确定每一个新加入节点的局域世界。新节点与局域世界中的老节点之间采用节点度与节点强度的复合优先连接方式,弥补了优先连接仅仅依赖节点度值的缺陷,从而构建基于位置吸引力的加权复杂供应链网络局域世界演化模型。实验模拟了该复杂网络的生长、边的退出和节点的退出等动态演化过程,通过计算与统计整体度分布、平均路径长度和聚集系数等复杂供应链网络的重要参数发现:该复杂供应链网络的度分布呈现出一定的幂率分布形式,能够保证大多数节点的度较低和少数节点的度较高的重尾特征,同时具有较大的集聚系数和较小的平均路径长度的小世界特征。该研究工作为供应链企业在实践中构建供应链网络提供了理论依据,有助于更好地分析现实供应链网络的相关特性并识别重要节点以便对供应链网络进行保护。

无线传感器网络中蒙特卡洛定位算法的研究

张绮曼, 张颖

计算机科学. 2018, 45 (12): 77-80. doi:10.11896／j.issn.1002-137X.2018.12.011

摘要 ( 298 )

PDF(2430KB) ( 724 )

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

在无线传感器网络的节点定位领域,常用的以蒙特卡洛为基础的定位算法均存在定位误差大、采样效率低的问题。为了提高无线传感器网络中针对移动节点的采样效率和定位精确度,文中采用马尔科夫链进行抽样,提出了一种基于蒙特卡洛的改进算法。该算法在蒙特卡洛算法的基础上,结合马尔科夫链采集节点样本,随后对其进行过滤,再通过对得到的节点位置值进行加权计算,得到节点的准确位置。仿真实验结果表明,通过该算法得到的节点定位误差低于其他算法,提高了采样效率以及对移动节点的定位准确率。

基于前缀路由策略的无线传感器网络任播路由协议

顾云丽, 徐昕, 杜杰

计算机科学. 2018, 45 (12): 81-85. doi:10.11896／j.issn.1002-137X.2018.12.012

摘要 ( 268 )

PDF(1725KB) ( 559 )

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

无线传感器网络经常出现节点、链路暂时性失效的现象,而重新建立通信树需要消耗大量资源。针对这一问题,提出一种基于前缀路由策略的无线传感器网络任播路由协议。该协议采用一个轻量级的路由发现过程以构建新的任播路径,并采用基于前缀标签的单播查询方法。与广播相比,单播查询可以避免在网络中充斥大量路由消息包;前缀标签可以帮助协议快速找到路径较短的新的任播路径。与传统标签方法相比,该协议的前缀标签开销(存储大小)有所增加,但增加幅度不大(不超过log₂3倍)。实验证明,相比于传统的基于通信树的任播路由协议,当查找新的替代任播路径时,该协议具有较低的路由查询开销(消息包数量)、较强的路由查询能力和较优的端对端传输时延性能。

一种延长目标覆盖网络寿命的群智能算法

范兴刚, 刘涛, 胡凤丹, 蒿翔

计算机科学. 2018, 45 (12): 86-91. doi:10.11896／j.issn.1002-137X.2018.12.013

摘要 ( 456 )

PDF(2290KB) ( 560 )

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

目标覆盖是无线传感网络中的一个研究热点,在满足目标覆盖要求的前提下,文中研究了如何利用群智能算法重新部署节点位置以延长网络寿命,提出了满足目标Q-覆盖要求的网络寿命模型,并以这个寿命模型为适应度函数,采用人工蜂群算法再部署传感器节点,在二维感知模型和三维感知模型下实现目标的Q-覆盖,以延长网络寿命。仿真实验的结果表明,基于人工蜂群算法的优化部署能够有效延长网络寿命。

面向云环境的一致性可验证单关键词检索方法

戴华, 保静静, 朱向洋, 易训, 杨庚

计算机科学. 2018, 45 (12): 92-97. doi:10.11896／j.issn.1002-137X.2018.12.014

摘要 ( 346 )

PDF(2799KB) ( 569 )

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

在云环境资源外包服务模式下,数据拥有者不再参与对其外包数据的直接管理,这就使得验证数据使用者获得的检索结果是否满足一致性成为具有挑战性的问题。现有的研究工作重点聚焦于解决云服务提供商满足“诚实而好奇”模型假设下的隐私保护问题,但并不能解决恶意攻击威胁模型下的检索结果一致性验证问题。针对云服务提供商恶意攻击威胁模型,提出了一种面向云环境的基于偏序约束链的一致性可验证单关键词检索方法——IVSKS。数据拥有者根据文档与关键词的相关度的偏序关系,构造用于检索结果一致性验证的偏序约束链验证编码信息,并将该信息与文档集共同外包存储至云端;数据使用者在执行单关键词检索时,云端返回检索结果文档集以及相应的验证编码;最后,数据使用者根据获得的检索结果重构验证编码,实现针对检索结果的一致性验证。实验表明,与同类方法相比,IVSKS在检索结果冗余度以及一致性验证时间开销上具有更好的表现。

面向风险评估的专家权重自适应调整方法

冷强, 杨英杰, 胡浩

计算机科学. 2018, 45 (12): 98-103. doi:10.11896／j.issn.1002-137X.2018.12.015

摘要 ( 513 )

PDF(1445KB) ( 799 )

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

信息资产评估是信息安全风险评估技术重要的研究内容之一。目前,其在资产评估中主要采用专家评估与专家权重相结合的评估量化方法,然而该方法在实际应用中却面临如何科学确定专家权重以降低偏差较大评估意见对整体评估结果影响的问题。针对该问题,提出了一种基于专家偏离度的权重自适应调整评估方法,能够合理地减小专家主观性给出的异常评估值对评估的影响。最后实现算法并通过实验验证算法的有效性。结果表明该方法能够合理减小异常评估值对评估的影响。

链路相关性欺骗攻击与检测机制

徐佳佳, 白光伟, 沈航

计算机科学. 2018, 45 (12): 104-110. doi:10.11896／j.issn.1002-137X.2018.12.016

摘要 ( 295 )

PDF(1707KB) ( 570 )

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

近年来的研究工作表明,无线通信中的数据包传输在不同的链路上存在接收相关性,这一现象对无线网络环境下不同通信协议的性能都有着很大的影响。现有的链路相关性感知协议的性能提升大都依赖链路相关性度量的准确性。然而,通过分析发现,无线网络自身的移动性、射频通信等特点导致其在通信过程中存在着各种威胁与网络攻击。文中结合链路相关性,提出链路相关性感知协议的欺骗攻击机制,即当网络中的源节点发送数据包时,相应的接收节点通过恶意修改自身维持的数据包接收位图中的数据来欺骗源节点,从而达到篡改同一源节点的不同邻居节点之间的链路相关性度量值的目的,因此,该攻击机制会降低协议的传输性能。针对这一攻击机制,文中提出了对应的恶意节点检测机制,即利用Watchdog机制对网络中节点的行为进行检测,从而得出真实的数据包接收位图。仿真结果表明,提出的链路相关性欺骗攻击机制增加了通信协议的数据包重传次数,降低了协议传输的性能,同时基于Watchdog的恶意节点检测机制对这一攻击具有良好的防御力。

基于行为特征分析的微博恶意用户识别

夏崇欢, 李华康, 孙国梓

计算机科学. 2018, 45 (12): 111-116. doi:10.11896／j.issn.1002-137X.2018.12.017

摘要 ( 468 )

PDF(1679KB) ( 1202 )

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

近年来,社交网络数据挖掘作为物理网络空间数据挖掘的一大热点,目前在用户行为分析、兴趣识别、产品推荐等方面都取得了令人可喜的成果。随着社交网络商业契机的到来,出现了很多恶意用户及恶意行为,给数据挖掘的效果产生了极大的影响。基于此,提出基于用户行为特征分析的恶意用户识别方法,该方法引入主成分分析方法对微博网络用户行为数据进行挖掘,对各维度特征的权重进行排序,选取前六维主成分特征可以有效识别恶意用户,主成分特征之间拟合出的新特征也能提升系统的识别性能。实验结果表明,引入的方法对微博用户特征进行了有效的排序,很好地识别出了微博社交网络中的恶意用户,为其他方向的社交网络数据挖掘提供了良好的数据清洗技术。

基于形式概念分析的语义角色挖掘算法

周超, 任志宇, 毋文超

计算机科学. 2018, 45 (12): 117-122. doi:10.11896／j.issn.1002-137X.2018.12.018

摘要 ( 552 )

PDF(2667KB) ( 598 )

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

基于角色的访问控制(Role-Based Access Control,RBAC)在管理和安全方面具有优势,经过20多年的发展后已被广泛应用于各个领域,如何将数据繁多的非RBAC系统迁移成RBAC系统已经成为一个意义重大的难题。角色是RBAC的基本特征,因此角色挖掘是RBAC系统实施的一个重要环节。基于形式概念分析生成用户权限概念格及用户属性概念格,将用户权限概念格翻转后映射为初始候选角色状态,通过约简操作和精简操作来挖掘角色,然后对用户权限概念格及用户属性概念格进行相似性分析,通过定义最近似表达式为角色赋予语义,使得生成的角色具有以下两点优势:1)结构层次,有效地减轻了管理员授权的负担,提高了授权管理的效率;2)语义意义,能够与现实生活中的概念相关联,增强了角色的可解释性。最后,通过实验验证了该算法的正确性和有效性。

基于智能蜂群算法的DDoS攻击检测系统

余学山, 韩德志, 杜振鑫

计算机科学. 2018, 45 (12): 123-129. doi:10.11896／j.issn.1002-137X.2018.12.019

摘要 ( 431 )

PDF(1971KB) ( 905 )

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

随着大数据应用的普及,DDoS攻击日益严重并已成为主要的网络安全问题。针对大数据环境下的DDoS攻击检测问题,设计了一种融合聚类和智能蜂群算法(DFSABC_elite)的DDoS攻击检测系统。该系统将聚类算法与智能蜂群算法相结合来进行数据流分类,用流量特征分布熵与广义似然比较判别因子来检测DDoS攻击数据流的特征,从而实现了DDoS攻击数据流的高效检测。实验结果显示,该系统在类内紧密度、类间分离度、聚类准确率、算法耗时和DDoS检测准确率方面明显优于基于并行化K-means的普通蜂群算法和基于并行化K-means算法的DDoS检测方法。

基于触发词语义选择的Twitter事件共指消解研究

魏萍, 巢文涵, 罗准辰, 李舟军

计算机科学. 2018, 45 (12): 130-136. doi:10.11896／j.issn.1002-137X.2018.12.020

摘要 ( 298 )

PDF(2482KB) ( 997 )

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

随着社交媒体的发展与普及,如何识别短文本中事件描述的共指关系已成为一个亟待解决的问题。在传统的事件共指消解研究中,需要从NLP工具和知识库中获得丰富的语义特征,这种方式不仅限制了领域的扩展性,而且还导致了误差传播。为了打破上述局限,提出了一种新颖的基于事件触发词来选择性表达句子语义的方法,以判断短文本中事件的共指关系。首先,利用双向长短记忆模型(Bi-LSTM)提取短文本的句子级语义特征和事件描述级语义特征;其次,通过在句子级特征上应用一个基于事件触发词的选择门来选择性表达句子级语义,以产生潜在语义特征;然后,设计了触发词重叠词数和时间间隔两个辅助特征;最后,通过融合以上特征形成一个分类器来预测共指关系。为评估上述方法,基于Twitter数据标注了一个新的数据集EventCoreOnTweets(ECT)。实验结果表明,与两个基准模型相比,提出的选择性表达模型显著提升了短文本共指消解的性能。

基于趋势强度的SAT问题学习子句评估算法

陈青山, 徐扬, 吴贯锋

计算机科学. 2018, 45 (12): 137-141. doi:10.11896／j.issn.1002-137X.2018.12.021

摘要 ( 416 )

PDF(1682KB) ( 641 )

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

针对命题逻辑公式求解过程中难以有效评估学习子句是否有利于后续搜索的问题,提出了一种基于学习子句趋势强度的评估算法。该算法首先通过分析学习子句在生存期内参与冲突分析的时间分布特征,将随机、离散的时间分布转换为连续的累积趋势强度;然后在删除周期达到时,通过设定趋势强度阈值删除在后续搜索过程中“不大可能”被使用的子句,保留“可能”被使用的子句;最后采用2015年、2016年SAT问题国际竞赛实例,将该算法与经典的活跃度评估算法和文字块距离(LBD)评估算法进行对比。实验结果表明,趋势强度评估算法在效率上明显优于活跃度评估算法,且求解的实例更多,同时与LBD算法基本持平。

基于主题增强的递归自编码情感分类研究

朱引, 黄海燕

计算机科学. 2018, 45 (12): 142-147. doi:10.11896／j.issn.1002-137X.2018.12.022

摘要 ( 278 )

PDF(1511KB) ( 682 )

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

中文文本情感分析旨在发现用户对事物、事件的情感倾向,然而现有研究往往忽视了文本之间的相互联系。提出一种基于主题增强的递归自编码情感分类模型,通过将文本的主题信息融入到递归自编码模型中,使得该模型可以更深层次地考虑文本的内容信息,提高其对文本情感的理解和泛化能力。在COAE2014数据集上的实验结果表明,将所提分类模型用于情感分类任务时可获得更优的分类效果,证实了其在实际问题中的适用性与可行性。

基于随机森林的文本分类并行化

彭徵, 王灵矫, 郭华

计算机科学. 2018, 45 (12): 148-152. doi:10.11896／j.issn.1002-137X.2018.12.023

摘要 ( 297 )

PDF(1504KB) ( 839 )

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

文本分类是信息检索的核心技术。传统的文本分类系统由于单机的计算与存储能力有限,已经不适用于大数据时代。在Spark大数据平台上并行地运行算法对文本进行分类,以数据和任务的并行化来提高算法的效率具有现实性和紧迫性。文中提出了改进的不平衡数据随机森林算法,通过对训练样本的多数类进行欠取样且对少数类进行有放回取样从而形成新训练样本的方法来减少不平衡数据对随机森林的影响。实验结果表明,新算法在处理不平衡数据集上的少数类时提高了分类的正确率。

基于序贯三支决策的多粒度情感分类方法

张刚强, 刘群, 纪良浩

计算机科学. 2018, 45 (12): 153-159. doi:10.11896／j.issn.1002-137X.2018.12.024

摘要 ( 418 )

PDF(1957KB) ( 957 )

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

如何对评论数据进行正确的情感分类是情感分析中的重要研究内容。从粒计算和认知学角度,提出了一种基于序贯三支决策的多粒度中文评论情感分类方法。首先,基于评论数据集的特点,根据评论中情感信息量的多少,提出一种由粗到细的多粒度情感信息表示方法;然后,结合序贯三支决策的思想在不同粒度依据情感信息进行逐步计算,对边界域评论序贯地进行三支决策;最后,根据不同粒度的决策阈值和成本对评论做出最终的情感分类。对比实验结果表明,该方法在3个经典评论数据集上获得了更好的结果,具有更高的分类正确率和更强的鲁棒性。

直觉模糊框架内的证据动态可靠性评估及应用

吴文华, 宋亚飞, 刘晶

计算机科学. 2018, 45 (12): 160-165. doi:10.11896／j.issn.1002-137X.2018.12.025

摘要 ( 257 )

PDF(2056KB) ( 529 )

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

基于证据理论与直觉模糊集之间的关系,提出了一种新的证据可靠性评估方法,该方法可以在先验知识缺乏的情况下,对各证据源的可靠性进行评估。首先,将证据理论中的基本概率赋值函数(Basic Probability Assignment,BPA)转化为直觉模糊集;然后,通过直觉模糊集之间的相似度度量对各BPA之间的相似度进行计算;在此基础上,提出证据支持度的概念,通过分析证据支持度与证据可靠性之间的关系,获得证据的相对可靠性和绝对可靠性;最后,基于证据折扣运算对原始证据进行修正,采用Dempster组合规则对修正后的证据进行组合。此外,基于直觉模糊框架内的证据可靠性评估,提出了一种多传感器融合方法,通过数值实验对该方法的性能进行了对比分析,结果表明,该方法可以实现对不可靠证据的有效评估。

一种考虑等级语义关联的证据推理决策方法

张美璟, 王应明

计算机科学. 2018, 45 (12): 166-169. doi:10.11896／j.issn.1002-137X.2018.12.026

摘要 ( 267 )

PDF(2432KB) ( 633 )

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

现有证据推理方法以证据理论为信息融合规则,并未考虑评估等级在语义上的关联关系,导致以正交求和方式进行信息融合时出现信息流失现象。从评估等级的语义和级别出发,提出一种基于等级语义关联的证据分类融合方法。基于新的证据融合模型,构建一个基于改进证据推理方法的多属性决策框架,并给出决策模型和决策流程。最后,通过一个案例演示了新方法的决策过程,并通过比较新旧方法在案例上的应用分析了新方法的特点。

基于优化BP神经网络的物理量回归方法

潘俊虹, 王宜怀, 吴薇

计算机科学. 2018, 45 (12): 170-176. doi:10.11896／j.issn.1002-137X.2018.12.027

摘要 ( 426 )

PDF(1931KB) ( 636 )

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

在物联网实际应用系统的开发中,传统回归方法面对A/D转换物理量回归时存在表达方式不统一、非线性校正能力及动态适应性弱等问题。文中在分析A/D转换物理量回归要素的基础上,依据BP神经网络的非线性映射能力,提出了利用布谷鸟算法进行优化的BP神经网络,并利用其实现统一数学表达的A/D转换物理量回归方法。实践表明,该方法具有数学公式统一、非线性校正能力及动态适应性强等特点。该方法既适用于利用通信方式将A/D采集的数据直接送至PC机处理的物联网系统,也适用于利用PC机进行学习,将神经网络结构参数存储于MCU内的Flash中,在物联网终端直接将A/D值转为实际物理量的环境。

基于改进激活函数的用于台风等级分类的深度学习模型

郑宗生, 刘兆荣, 黄冬梅, 宋巍, 邹国良, 侯倩, 郝剑波

计算机科学. 2018, 45 (12): 177-181. doi:10.11896／j.issn.1002-137X.2018.12.028

摘要 ( 451 )

PDF(2721KB) ( 673 )

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

针对特定任务中深度学习模型的激活函数不易选取的问题,在分析传统激活函数和现阶段运用比较广泛的激活函数的优缺点的基础上,将Tanh激活函数与广泛使用的ReLU激活函数相结合,构造了一种能够弥补Tanh函数和ReLU函数缺点的激活函数T-ReLU。通过构建台风等级分类的深度学习模型Typ-CNNs,将日本气象厅发布的台风卫星云图作为自建样本数据集,采用几种不同的激活函数进行对比实验,结果显示使用T-ReLU函数得到的台风等级分类的测试精度比使用ReLU激活函数的测试精度高出1.124%,比使用Tanh函数的测试精度高出2.102%;为了进一步验证结果的可靠性,采用MNIST通用数据集进行激活函数的对比实验,最终使用T-ReLU函数得到99.855%的训练精度和98.620%的测试精度,其优于其他激活函数的效果。

基于特征内相关和互信息的加权SVM算法

彭晓冰, 朱玉全

计算机科学. 2018, 45 (12): 182-186. doi:10.11896／j.issn.1002-137X.2018.12.029

摘要 ( 230 )

PDF(1612KB) ( 1029 )

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

特征加权支持向量机没有考虑特征间的相关性,因此产生的冗余会形成干扰并对最后的分类结果产生负面影响。为解决这个问题,提出了一种基于特征内相关和互信息的特征加权算法,并将其应用于支持向量机。该算法引入了特征间相关系数作为衡量冗余度的一个指标,以此计算出惩罚因子,在特征加权向量机的基础上对权值进行处理,尽可能真实地体现出特征对分类的贡献度。经过多个数据集以及几种不同算法的实验比较,提出的新算法具有更好的鲁棒性和泛化能力。

基于Repast Simphony平台的人群运动行为仿真及优化

刘文龙, 张晶, 周绥平, 李月龙

计算机科学. 2018, 45 (12): 187-191. doi:10.11896／j.issn.1002-137X.2018.12.030

摘要 ( 339 )

PDF(2335KB) ( 554 )

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

针对地铁乘客人群的运动行为,基于Agent模型和粒子群搜索算法,利用仿真平台Repast Simphony建立了人群运动行为仿真模型,该模型模拟了乘客进入地铁候车大厅寻找车厢门进行排队和地铁到站时进入车厢的过程;基于此,提出了一种基于马尔可夫决策模型的改进寻路算法。实验表明,该算法有效地解决了传统粒子群算法容易陷入局部解的问题,明显减少了冲突次数。此外,文中提出增加地铁车厢人数指示器来避免部分车厢的拥挤状况,实验结果显示该方法行之有效,并能将乘客进入车厢的效率提高9%。

一种基于关联-层次的飞机复杂机电组件虚拟维修建模方法

董健康, 唐超, 耿宏

计算机科学. 2018, 45 (12): 192-195. doi:10.11896／j.issn.1002-137X.2018.12.031

摘要 ( 221 )

PDF(2629KB) ( 560 )

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

针对传统的维修仿真模型不满足虚拟维修环境的要求和缺乏通用性的问题,提出了一种基于关联-层次的飞机复杂机电组件虚拟维修建模方法。该方法将模型分为关联模型(顶层)、层次模型(中间层)和几何模型(底层)。关联模型体现了复杂机电组件与其他组件之间的关联关系,层次模型集成了组件自身的约束、功能、故障、结构等信息,几何模型用于虚拟维修环境中的实时显示和碰撞检测。建立的模型信息表达完整,具有普适性,能够满足虚拟环境对模型的要求,同时可以应用于机务维修训练。最后,通过实例验证了该建模方法的有效性。

改进UCT算法在爱恩斯坦棋中的应用

张小川, 李琴, 南海, 彭丽蓉

计算机科学. 2018, 45 (12): 196-200. doi:10.11896／j.issn.1002-137X.2018.12.032

摘要 ( 825 )

PDF(1773KB) ( 1117 )

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

UCT(Upper Confidence Bound Apply to Tree)算法是蒙特卡罗搜索算法的延展,因其鲁棒性强而受到广泛关注,且被应用于计算机博弈系统。爱恩斯坦棋是近年国内博弈大赛引进的新棋种,在竞赛中投骰子所引发的随机性和娱乐性吸引了广大学者的目光。从全局优化着法角度出发,在爱恩斯坦棋博弈系统中引入UCT算法。首先,针对当前计算机多核现状,利用并行计算方法进一步优化UCT算法;其次,针对UCT算法的最优着法需求,引入当前估值因子(WINK)和次优节点平衡因子(UCTK),以此辅助增加估值的精确度,决策胜率与着法的优先关系,提高算法的收敛效率;最后,构造了爱恩斯坦棋博弈系统,通过与基于极大极小算法、α-β算法以及蒙特卡罗算法的爱恩斯坦棋博弈系统进行机-机对弈,其胜率提高了25%,并在全国计算机博弈大赛中获冠军,这进一步验证了改进算法的有效性。

基于终态神经网络的冗余机械臂重复运动规划

孔颖, 孙明轩

计算机科学. 2018, 45 (12): 201-205. doi:10.11896／j.issn.1002-137X.2018.12.033

摘要 ( 333 )

PDF(1732KB) ( 681 )

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

为解决冗余机械臂在运动过程中出现的关节角漂移现象,提出了一种终态吸引优化指标,形成冗余机械臂重复运动规划的二次优化方法。采用具有有限值激活函数的终态神经网络来求解,在初值位置偏移目标位置的情形下,实现冗余机械臂有限时间收敛的重复运动规划任务。同时,分别以新型的终态神经网络(TNN)和其加速网络(ATNN)求解运动规划问题,该网络求解方法具有终态吸引特性,能够在有限的时间内得到有效解。相比具有渐近收敛动态特性的神经网络(ANN),终态神经网络方法不仅改变了收敛速度,而且提高了收敛的精度。基于冗余机械臂PUMA560的计算机仿真结果表明了所提方法的有效性和实时性。

基于局部特征多轴旋转不变特性的纹理图像分类算法

黄庆宇, 章登义

计算机科学. 2018, 45 (12): 206-209. doi:10.11896／j.issn.1002-137X.2018.12.034

摘要 ( 386 )

PDF(3131KB) ( 676 )

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

采用非量化的局部特征设计出一个稳健的纹理描述符,以便增强旋转和尺度变化时纹理分类的鲁棒性。首先,引入了局部特征的旋转对称性的概念,提出了一种新颖的局部特征来描述纹理的旋转不变特性。为了处理剧烈的旋转、尺度等变化,利用费舍尔向量编码方法对纹理特征量进行多尺度分析,在不增加局部特征维度的同时又能结合尺度信息,由此产生的局部特征对旋转、灰度变化都有较强的鲁棒性。实验结果表明,所提方法的评估结果在许多数据集上都远远超过了现有最优算法,大大提高了纹理分类的精度。

基于L1与TV正则化的改进图像重建算法

徐敏达, 李志华

计算机科学. 2018, 45 (12): 210-216. doi:10.11896／j.issn.1002-137X.2018.12.035

摘要 ( 527 )

PDF(2169KB) ( 1759 )

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

针对不完全投影数据图像重建中出现伪影和噪点的问题,提出了L1与TV同时进行正则化的图像重建模型。基于该重建模型,通过将Bregman迭代和TV软阈值滤波相结合,进一步提出了一种图像重建算法。该算法首先将投影数据通过优化的Bregman迭代算法进行初步重建,然后使用TV软阈值滤波对改造的全变分模型进行二次重建,最后判断是否满足设定的收敛阈值,若满足则结束重建,输出重建图像,否则重复进行上述两步操作,直至迭代完成。实验采用不添加噪声的Shepp-Logan模型与添加噪声的Abdomen模型来验证算法的有效性,证明了所提出的算法在视觉上均优于ART,LSQR,LSQT-STF,BTV等典型的图像重建算法,同时通过多项评价指标对比表明所提出的算法有明显优势。实验结果表明,所提算法在图像重建中能够有效去除条形伪影并保护图像细节,同时具有良好的抗噪性。

基于NSST与自适应PCNN的多聚焦图像融合方法

杨利素, 王雷, 郭全

计算机科学. 2018, 45 (12): 217-222. doi:10.11896／j.issn.1002-137X.2018.12.036

摘要 ( 444 )

PDF(5334KB) ( 991 )

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

为弥补传统图像融合方法融合质量不高的缺点,提出了基于非下采样剪切波变换(Nonsubsampled Shearlet Transform,NSST)与自适应脉冲耦合神经网络(Pulse Coupled Neural Network,PCNN)的图像融合方法。首先,利用非下采样剪切波变换对源图像进行剪切波分解;然后,采用基于图像引导滤波器的融合规则对得到的低频分量进行低频融合;其次,对于高频分量,采用改进的空间频率作为PCNN的输入,利用改进的拉普拉斯能量和作为PCNN的链接强度;最后,通过NSST逆变换得到融合后的图像。实验结果表明,相比于传统的融合规则,文中提出的算法在主观效果上能很好地保留细节信息,并抑制伪影和失真的产生;在客观评价上,其在标准差、边缘信息传递量、信息熵和互信息等常用指标上的表现更为优越。

基于自适应主动学习与联合双边滤波的高光谱图像分类

李昌利, 张琳, 樊棠怀

计算机科学. 2018, 45 (12): 223-228. doi:10.11896／j.issn.1002-137X.2018.12.037

摘要 ( 266 )

PDF(3038KB) ( 612 )

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

在高光谱图像分类中,选择合适的样本作为训练样本对分类器进行训练非常重要。将样本的不确定性与代表性相结合,通过自适应主动学习方法来完成样本的选择。用核K均值聚类来获取具有代表性的样本,用最优标号和次优标号的概率差值与两者比值的加权和来度量不确定性。此外,为了提高分类的准确率,利用联合双边滤波来获取高光谱图像的空间信息,并将其融入分类过程中。最后,提出一种融合自适应主动学习与联合双边滤波的空谱结合高光谱图像分类方法,并通过实验验证了所提方法的优越性。

基于生成对抗网络的图像修复

孙全, 曾晓勤

计算机科学. 2018, 45 (12): 229-234. doi:10.11896／j.issn.1002-137X.2018.12.038

摘要 ( 845 )

PDF(4025KB) ( 1281 )

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

针对现有图像修复算法存在受损区域的形状和大小受限以及修复痕迹明显、修复边缘不连续的问题,文中提出一种基于生成对抗网络的图像修复方法。该方法采用生成对抗网络(Generative Adversarial Networks,GAN)这种新的生成模型作为基本架构,结合Wasserstein距离,同时融入条件对抗网络(CGAN)的思想;以破损图像作为附加条件信息,采用对抗损失与内容损失相结合的方式来训练网络模型,以修复破损区域。此方法能够修复大多数破损情况下的图像。在CelebA和LFW两个数据集上的实验结果表明,所提方法能够取得很好的修复效果。

基于前馈上下文和形状先验的平面标注方法

郭燕飞, 刘宏哲, 袁家政, 王雪峤

计算机科学. 2018, 45 (12): 235-242. doi:10.11896／j.issn.1002-137X.2018.12.039

摘要 ( 324 )

PDF(6328KB) ( 617 )

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

针对真实场景中由于互相遮挡导致的场景语义不能完全被理解的问题,提出了一种基于前馈上下文和形状先验的方法来对前景区域和被遮挡的背景区域进行语义标注。首先,将原始图像分割成超像素并提取像素点特征,采用加速决策树方法标注前景,同时采用改进的基于多尺度可形变的部件模型方法进行目标检测。其次,将可见对象信息与前馈上下文预测相结合来推测背景区域的被遮挡部分。然后,根据与当前标签置信度相匹配的多边形为每个标签提供形状先验知识。最后,结合像素预测与可视平面预测和多边形知识,以形成完整的场景标注图像。与现有方法相比,该方法能够得到与街道场景更相符的结果,并在人行道和公路较接近时的标注效果更好。

基于多尺度空谱鉴别特征的高光谱图像分类

任守纲, 万升, 顾兴健, 王浩云, 袁培森, 徐焕良

计算机科学. 2018, 45 (12): 243-250. doi:10.11896／j.issn.1002-137X.2018.12.040

摘要 ( 444 )

PDF(3752KB) ( 664 )

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

为了应对高光谱图像同质区域面积分布不均的问题,同时更充分地挖掘空间和光谱信息之间的内在联系,提出了一种基于多尺度空谱鉴别特征的高光谱图像分类方法。该算法首先对图像进行不同尺度的滤波操作,接着分别从得到的多幅图像中提取鉴别的空谱特征,并使用支持向量机(SVM)进行分类。最后,该算法采取“决策级融合”的策略,来综合不同滤波尺度图像的分类结果。在Indian Pines,Kennedy Space Center和University of Pavia数据集上的实验表明,该算法能够提取较为有效的空间信息,当随机选取10%的像素作为训练样本时,该算法的总体分类准确率均能达到96%以上,其分类精度和Kappa系数均优于其他分类算法。

基于双图正则的半监督NMF混合像元解混算法

邹丽, 蔡希彪, 孙静, 孙福明

计算机科学. 2018, 45 (12): 251-254. doi:10.11896／j.issn.1002-137X.2018.12.041

摘要 ( 263 )

PDF(3127KB) ( 569 )

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

在高光谱图像中混合像元普遍存在,这极大地阻碍了高光谱遥感技术的发展进程,因此,在利用光谱图像的过程中,如何准确高效地进行混合像元解混是一个关键问题。对于高光谱图像混合像元分解,使用原始的非负矩阵分解(Nonnegative Matrix Factorization,NMF)算法面临一些困难:首先,其目标函数为非凸函数,难以求解得到全局最优解;其次,混合像元中并不存在纯像元。为了解决这些问题,文中提出一种新的算法——基于双图正则的半监督NMF(Dual graph-regularized Constrained Nonnegative Matrix Factorization,DCNMF)混合像元解混算法。该算法采用了梯度下降法和迭代更新法则,既考虑了高光谱数据流形与光谱特征流形的几何结构,又能跳出局部极值,从而求解得到全局最优解。通过真实的高光谱图像数据仿真实验表明,DCNMF算法能够准确高效地进行混合像元分解,改善了解混效果,提高了解混精度,节约了计算时间,加快了收敛速度。

基于多任务卷积神经网络的舌象分类研究

汤一平, 王丽冉, 何霞, 陈朋, 袁公萍

计算机科学. 2018, 45 (12): 255-261. doi:10.11896／j.issn.1002-137X.2018.12.042

摘要 ( 429 )

PDF(1784KB) ( 1647 )

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

针对现有技术难以并行实现舌象多标签的高效分类和识别,难以利用标签间的相关性进行综合分析等问题,提出了一种基于多任务卷积神经网络的舌象分类方法,构建了一种多任务联合学习模型,尝试实现传统中医舌诊中对舌色、苔色、裂纹和齿痕等多个标签的同时辨识。首先,在共享网络层对所有标签进行联合学习,从特征提取的角度自动挖掘和利用标签间的相关性;然后,在不同子网络层分别完成特定类别的学习任务,从而消除多标签分类中的歧义性;最后,训练多个Softmax分类器以实现对所有标签的并行预测。研究表明,所提方法能以端到端的方式同时提取舌象的多个特征并直接进行分类识别,在各分类评价指标上的最低值约为0.96,多任务的总体识别时间为34ms,因此该方法在精度和速度上均具有明显优势。

基于SOM聚类的垃圾处理方式可视化分析方法

秦绪佳, 单扬洋, 徐菲, 郑红波, 张美玉

计算机科学. 2018, 45 (12): 262-267. doi:10.11896／j.issn.1002-137X.2018.12.043

摘要 ( 259 )

PDF(6020KB) ( 703 )

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

针对全国各省份垃圾处理方式的数据,提出一种混合可视分析方法。为了从多角度分析数据,混合U矩阵、平行坐标以及Small-Multiple 3种可视化技术,设计并实现了3种可视化视图的交互联动。首先,对数据进行聚类处理,将各省份近年的垃圾处理方式划分类别,采用SOM神经网络聚类算法实现聚类。然后,针对SOM聚类结果,采用U矩阵的方式进行可视化,并采用平行坐标描述每个聚类结果的各个属性。为了分析数据的地理属性及时序属性,采用Small-Multiple可视化技术。最后,实现多视图联动、刷新技术等交互方式,帮助用户自行探索数据,实现多视图的交互展示与分析。实验表明,这种混合可视方式可达到较好的多属性交互可视化效果,能够帮助用户了解并分析我国垃圾处理方式的分布及趋势。

基于出行模式子图的城市功能区域发现方法

肖飞, 王悦, 梅逸男, 白璐, 崔丽欣

计算机科学. 2018, 45 (12): 268-278. doi:10.11896／j.issn.1002-137X.2018.12.044

摘要 ( 232 )

PDF(3699KB) ( 818 )

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

城市的功能区域是指在城市的发展过程中逐渐形成的功能(如工业、商业、居住、教育等)相对固定的地理区域。这些区域间的位置结构影响着城市中居民的出行模式,与此同时,城市居民的出行模式也客观地反映了城市不同区域的真实的功能定位。文中以出租车运行轨迹数据为基础,研究城市居民的出行模式,并根据所得模式实现城市功能区域的自动化发现。主要思路及贡献包括:1)使用车辆轨迹及路网结构数据构造区域模式图(region pattern graph)结构,并提出区域模式图构建算法,采用图结构将城市的不同地理区域连接起来;2)提出自底而上的功能区域发现算法(Bottom-Up Functional Region Discovering,BUFRD)框架及基本实现思路,包括提出频繁出行模式子图挖掘算法,发现区域模式图中频繁出现的出行模式;3)提出功能区域聚类算法,聚类已获取的出行模式子图集,并最终实现城市功能区域的发现。实验结果表明,通过所提方法发现的城市功能区域较传统方法所得结果的功能纯度更高,其熵值比传统方法降低了至少10%。

一种基于用户移动行为相似性的位置预测方法

李昇智, 乔建忠, 林树宽

计算机科学. 2018, 45 (12): 288-292. doi:10.11896／j.issn.1002-137X.2018.12.046

摘要 ( 272 )

PDF(2231KB) ( 680 )

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

随着移动通信技术和车载定位系统的发展和广泛应用,基于位置服务越来越受到人们的关注。位置预测技术是其重要组成部分,并有着广泛的应用。在实际应用中,由于采集点丢失或新用户出现等,GPS轨迹数据往往具有稀疏特性,使得基于单个用户数据的位置预测的准确率较低。针对这种情况,文中提出了基于移动行为相似性和用户聚类的Markov位置预测方法。首先,为使预测的位置具有物理意义,提出了基于Voronoi图的区域划分方法,并基于区域轨迹进行位置预测;其次,提出了同时考虑用户转移特性和用户区域特性的移动行为相似性计算方法;再次,根据移动行为相似性对用户进行聚类,并在聚类的用户组上采用一阶Markov模型进行位置预测,提高了位置预测的准确性。在真实GPS轨迹数据上的实验表明了所提方法的有效性。

一种基于网络编码的云存储系统

刘宴涛, 刘珩

计算机科学. 2018, 45 (12): 293-298. doi:10.11896／j.issn.1002-137X.2018.12.047

摘要 ( 300 )

PDF(2248KB) ( 801 )

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

存储空间、修复带宽和更新带宽是云存储系统的3个重要指标,系统设计往往需要在这些性能度量之间取折衷。为了降低存储空间、修复带宽、更新带宽以及系统复杂度,文中提出了一种基于网络编码的云存储系统。该系统结构为m*n数据阵列的形式,n列表示n个存储节点,其中k个节点用于存储原始数据,称为系统部分;另外(n－k)个节点用于存储校验字符,称为非系统部分。数据阵列的m行对应m个系统形式的(n,k)最大距离可分(MDS)码,每个源数据符号只参与它所在行的编码,不参与其他行的编码,这种系统结构大幅降低了编译码的复杂度。该系统可以承受最多(n－k)个节点的失效,此外,当单节点失效时,由于使用了系统形式的MDS码,可以使用干扰对齐技术进一步缩减修复带宽。与现有的某些云存储系统相比,该系统明显降低了存储空间、修复带宽和更新带宽等资源消耗,性能得到大幅提升。

一种基于MapReduce的不确定图上的相似性连接方法

缪丰羽, 王宏志, 阮群生

计算机科学. 2018, 45 (12): 299-307. doi:10.11896／j.issn.1002-137X.2018.12.048

摘要 ( 314 )

PDF(1584KB) ( 669 )

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

相比于确定图上的相似性连接,不确定图上的相似性连接通常具有更大的实际应用价值以及计算复杂性。文中研究了基于MapReduce分布式编程框架的不确定图上的相似性连接问题,提出了基于概率和的Map方剪枝和Reduce方剪枝的两种剪枝策略。Map方剪枝策略在映射过程中过滤掉了不可能具有相似图的不确定图。Reduce方剪枝策略用于减少约减过程中的候选图对。基于这两种剪枝策略,文中提出了一种基于MapReduce框架的不确定图上的相似性连接算法MUGSJoin。实验结果证明,该算法与同类算法相比具有更好的性能和可扩展性。

基于RNA-Seq数据集的转录组从头拼接算法

武思文, 李静, 张少强

计算机科学. 2018, 45 (12): 308-312. doi:10.11896／j.issn.1002-137X.2018.12.049

摘要 ( 255 )

PDF(1623KB) ( 648 )

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

转录组拼接是基因组测序与功能注解问题的一个重要组成部分。为了提高转录组拼接的精度和效率,文中提出了一种新的转录组从头拼接算法StepLink。该算法的主要创新点是提出了最左k-mer(长度为k的短序)和右k-mer的概念,并运用双重哈希表来存储相邻的每对k-mer,使得拼接更加迅速、准确。应用该算法对SRA数据库中人、狗和老鼠的测序数据分别进行拼接,结果表明该算法比其他已有算法更高效。