计算机科学

刘颖

计算机科学. 2019, 46 (2): 1-10. doi:10.11896/j.issn.1002-137X.2019.02.001

摘要 ( 828 )

PDF(1490KB) ( 1908 )

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

半结构、非结构化、海量的供应链金融数据使得大数据环境下金融数据分析的模式和方法相对复杂。面向大数据样本研究,如何将大样本相比于小样本的独有特征体现在分类模型中值得深入探索。文中从供应链金融数据分布特征入手,分析影响信用风险分类模型的主要因素;对多年来的相关研究成果进行归类分析,概括信用数据分布特征,包括信用数据非均衡与不对称性、信用数据噪声和离群点的存在以及信用数据的非线性多维特征,并探讨了进一步的解决策略。供应链金融大数据分布特征的分析旨在助力挖掘隐含在海量金融数据背后的知识信息,为信用风险模型的构建奠定了坚实的基础。

质量嵌入的大数据产品生产系统超图模型及其生产线决策研究

王旸, 蔡淑琴, 邹新文, 陈梓桐

计算机科学. 2019, 46 (2): 11-17. doi:10.11896/j.issn.1002-137X.2019.02.002

摘要 ( 850 )

PDF(1444KB) ( 1134 )

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

大数据产品(Big Data Product,BDP)在原材料、用户需求、加工工艺等方面具有不同于实体产品的特征,而现有BDP生产系统的研究仍停留在概念模型阶段。为了解决该问题,提出BDP生产线的概念,基于生产线特征研究了生产线决策要素,强调了质量作为关键决策要素在BDP生产中的作用机理;采用超图理论建立了嵌入质量、质量传递函数和质量聚集函数的BDP生产系统模型,设计了BDP生产线决策流程;提出了供给侧稳定和需求侧稳定的BDP生产线决策模式。实例验证结果表明,所提出的模型和决策方法能够满足用户对BDP质量的要求。

BioPW+:基于Linked Data的生物途径数据可视化系统

刘源, 王鑫, 甘瀛, 杨朝洲, 李维熙

计算机科学. 2019, 46 (2): 18-23. doi:10.11896/j.issn.1002-137X.2019.02.003

摘要 ( 648 )

PDF(2035KB) ( 1183 )

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

自Linked Data项目被提出以来,大量的开放关联数据被发布到语义Web上,这其中就包含了许多的生物途径数据集。为了使生物学家能够有效地利用这些开放的数据集,对基于Linked Data的生物途径数据可视化系统进行研究,提出了生物途径可视化模型和展示布局方案,并且采用标识符动态映射实现了多源生物途径数据的浏览,最终开发了基于Linked Data的生物途径数据查询可视化系统——BioPW+。该系统应用语义Web技术,依靠SPARQL查询来定位生物途径的基本信息,然后基于Open PHACTS平台获取生物途径元素的详细信息,最终Web界面采用力导向图布局、Sankey图布局对生物途径数据进行展示并提供多种交互操作。与已有的仅仅基于某一特定数据库的生物途径工具相比,BioPW+系统基于Linked Data,可以同时一次性展示多个数据集中的生物途径数据及与其相关的其他生物化学数据,极大节省了时间并增强了数据的完整性。

一种基于混合布局策略的高校教师业绩数据可视化方法

丁维龙, 薛莉莉, 陈婉君, 吴福理

计算机科学. 2019, 46 (2): 24-29. doi:10.11896/j.issn.1002-137X.2019.02.004

摘要 ( 540 )

PDF(2884KB) ( 1309 )

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

高校教师的业绩数据对于教师的考核评优、薪资提升、岗位聘任和职称晋升等人事决策具有十分重要的作用。针对其兼具复杂层次特征和多维属性的特点,提出了一种基于圆形嵌套图和平行坐标的VPM(Venn Parallel Coordinates Mixing)混合可视化方法。该方法首先采用基于D3布局算法的圆形嵌套图表示层次结构,而后划分叶子节点的圆周为不同的属性轴,通过布局设计、属性映射、属性点连接及缩放、高亮等用户交互来实现层次结构中多维属性的可视化。将该方法用于教师业绩数据,实现了对学院、研究所、教师各层级结构的可视化,可清晰展示数据项的细节信息。实验结果表明,提出的VPM方法能有效地展示教师的业绩数据,评价结果亦符合实际情况,能帮助系统用户——院校管理者对教师进行更好的管理及业绩考核。

重复数据中关键属性值缺失填补的改进ROUSTIDA算法

樊哲宁, 杨秋辉, 翟宇鹏, 万莹, 王帅

计算机科学. 2019, 46 (2): 30-34. doi:10.11896/j.issn.1002-137X.2019.02.005

摘要 ( 696 )

PDF(1382KB) ( 1348 )

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

随着数据分析研究的兴起,数据预处理越来越得到研究者的重视,其中缺失数据填补问题的重要性也逐渐显现。在ROUSTIDA数据补齐算法的基础上,针对具有关键属性的重复数据的特点,文中提出了一种改进的ROUSTIDA算法——Key&Rpt_RS算法。Key&Rpt_RS算法继承了ROUSTIDA算法的优势,同时考虑了目标数据的重复性特点,分析了关键属性对填补效果的影响,得到了更加准确且有效的填补结果。

基于城市安全知识图谱的多关键词流式并行检索算法

管健, 汪璟玢, 卞倩虹

计算机科学. 2019, 46 (2): 35-41. doi:10.11896/j.issn.1002-137X.2019.02.006

摘要 ( 555 )

PDF(2395KB) ( 1438 )

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

我国智慧城市安全概念的普及和建设的逐渐落地,以及大数据在智慧城市安全建设方面的深度应用,对关键词检索的处理响应速度提出了更高的要求。针对这一问题,提出了基于城市安全知识图谱的流式知识图谱多关键词并行检索算法(MKPRASKG),该算法能够根据用户输入的查询关键字,通过关联类图的构建、剪枝和融合操作实时构建基于知识图谱实体的查询子图集,再结合评分函数,以高评分的查询子图为指引,在知识图谱实例数据中进行并行搜索,最终返回Top-k查询结果。实验结果证明,该算法在实时搜索、响应时间、搜索效果以及可扩展性等方面均具有较大的优势。

大数据环境下基于公共服务平台的资源多级智能寻租与匹配策略和价值创造

毕娅, 原惠群, 初叶萍, 刘慧

计算机科学. 2019, 46 (2): 42-49. doi:10.11896/j.issn.1002-137X.2019.02.007

摘要 ( 581 )

PDF(1510KB) ( 901 )

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

资源的高效寻租与匹配是其价值创造的关键。文中研究大数据环境下基于公共服务平台的资源寻租与匹配问题,针对公共服务资源的非结构化特点,考虑本体树的路径距离、连接深度和广度,重新定义了语义距离,提出了基于语义距离的五元组形式化描述模型,消除了公共服务资源在底层结构和类型上的复杂性;针对公共服务平台上资源及其相关数据信息规模巨大的问题,提出了资源多级智能寻租与匹配策略,首先通过对参数相对较少且简单的S_category和S_status进行粗粒度过滤,大幅缩小资源寻租的范围,快速提高算法的匹配速度,再通过对Sability和SQoS的细粒度匹配,最终得到符合需求方匹配阈值要求的资源排序集合。实验算例表明,该方法的计算效率显著高于传统的多线程算法,且与目前常用的资源寻租与匹配算法相比,查准率和查全率更优。实验结果证明,该方法有效可行,不仅能够实现公共服务平台上资源的快速寻租和高效匹配,而且还能够在大数据的驱动下实现资源的价值创造。

一种基于质心空间的不均衡数据欠采样方法

金旭, 王磊, 孙国梓, 李华康

计算机科学. 2019, 46 (2): 50-55. doi:10.11896/j.issn.1002-137X.2019.02.008

摘要 ( 650 )

PDF(1424KB) ( 1275 )

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

针对目前的分类算法在不均衡数据集上的分类效果不理想的问题,将监督学习和无监督学习相结合,提出了一种基于质心的欠采样——ICIKMDS。在现实应用中,一些数据并不容易获得,或者不同类型的数据本身在数量上就存在着差异性,因此造成了数据集分布的不均,如疾病检测中疾病患者和正常人比例的不均、信用卡欺诈中欺诈用户和正常用户比例的不均等。所提方法很好地解决了数据集不均衡的问题,首先通过求解样本之间的欧氏距离得到初始质心,然后采用k-means算法在大类样本集上进行聚类,使不均衡数据集在分布上更加均衡,有效地改善了分类器的分类效果。所提方法使分类器在测试集小类上的分类准确率远远高于随机欠采样和SMOTE算法,在整个测试集上的准确率几乎与其他算法相同。

基于知识图谱和频繁序列挖掘的旅游路线推荐

孙文平, 常亮, 宾辰忠, 古天龙, 孙彦鹏

计算机科学. 2019, 46 (2): 56-61. doi:10.11896/j.issn.1002-137X.2019.02.009

摘要 ( 996 )

PDF(1936KB) ( 2607 )

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

大数据在提供海量多源信息的同时,也带来了信息过载问题,这在旅游领域内表现得尤为突出。针对当前游客在制定旅行路线时需要花费大量时间和精力的现状,首先,提出一种融合多源旅游数据构建知识图谱的方法,有效地抽取相关旅游领域知识;其次,利用知识图谱及大量旅行游记生成旅游路线数据库,并提出一种能够根据游客类型生成海量候选路线的频繁路线序列模式挖掘算法;最后,设计了一种多维度路线搜索和排序机制来为用户推荐个性化的旅游路线。基于真实旅游大数据的实验结果表明,该方法可以同时考虑旅行天数、人物类型和景点类型喜好等多方面因素,帮助游客快速制定个性化的旅行路线,有效提升游览体验。

基于核函数的稀疏属性选择算法

张善文, 文国秋, 张乐园, 李佳烨

计算机科学. 2019, 46 (2): 62-67. doi:10.11896/j.issn.1002-137X.2019.02.010

摘要 ( 645 )

PDF(2262KB) ( 1087 )

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

鉴于传统属性选择算法无法捕捉属性之间的关系的问题,文中提出了一种非线性属性选择方法。该方法通过引入核函数,将原始数据集投影到高维的核空间,因在核空间内进行运算,进而可以考虑到数据属性之间的关系。由于核函数自身的优越性,即使数据通过高斯核投影到无穷维的空间中,计算复杂度亦可以控制得较小。在正则化因子的限制上,使用两种范数进行双重约束,不仅提高了算法的准确率,而且使得算法实验结果的方差仅为0.74,远小于其他同类对比算法,且算法更加稳定。在8个常用的数据集上将所提算法与6个同类算法进行比较,并用SVM分类器来测试分类准确率,最终该算法得到最少1.84%,最高3.27%,平均2.75%的提升。

F-OFDM系统中的自适应EM相位噪声抑制算法

陈大爽, 李英善, 吴虹

计算机科学. 2019, 46 (2): 68-75. doi:10.11896/j.issn.1002-137X.2019.02.011

摘要 ( 704 )

PDF(3358KB) ( 1457 )

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

滤波正交频分复用技术(Filtered Orthogonal Frequency-Division Multiplexing,F-OFDM)是针对下一代移动通信的新技术,它在保持4G OFDM技术强抗干扰能力等诸多优点的基础上,能够适应未来各种灵活的业务配置;但其对相位噪声更加敏感,相噪会导致其出现子带共同相位误差(Sub-Band Common Phase Error,SCPE)和子带载波间干扰(Sub-Band Inter-Carrier Interference,SICI),严重降低系统性能。基于最大期望准则(EM),提出一种自适应EM相噪抑制算法(AEM-PNS),其中包含EM-SCPE和EM-SICI两个子算法,算法通过在符号帧中插入的相噪指示符(Phase Noise Instruction Symbol,PNIS)和导频指示符(Pilot Instruction Symbol,PIS)自动选择子算法。仿真结果表明,新提出的算法能自适应跟踪相噪的变化,有效降低相位噪声的影响,同时具有较低的计算复杂度和较高的频谱效率。

基于网络熵的域内节能路由方案

张举, 耿海军, 刘洁琦

计算机科学. 2019, 46 (2): 76-80. doi:10.11896/j.issn.1002-137X.2019.02.012

摘要 ( 533 )

PDF(2374KB) ( 991 )

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

减少网络能耗和建立绿色网络已经成为学术界和工业界研究的关键科学问题。已有的节能方案均在已知流量矩阵的前提下展开研究,但是获得实时流量数据并不容易。因此,文中研究了如何在未知流量矩阵的情况下降低网络能耗,提出了一种基于网络熵的域内节能路由方案(Intra-domain Energy Efficiency Routing Scheme Based on Network Entropy,EERSBNE),该方案通过关闭网络中的链路来实现节能的效果。首先提出了链路关键度模型和网络熵模型,然后根据链路关键度计算网络中所有链路的重要程度,最后根据链路的重要性和网络熵模型依次关闭网络中的链路。实验结果表明,该算法在降低网络能耗的同时不会引入较大的路径拉伸度。

移动社会网络中基于多维上下文匹配的数据转发算法

徐方, 邓敏, 熊曾刚, 叶从欢, 徐宁

计算机科学. 2019, 46 (2): 81-87. doi:10.11896/j.issn.1002-137X.2019.02.013

摘要 ( 406 )

PDF(1575KB) ( 1092 )

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

通过研究移动社会网络中的多种上下文信息对节点移动模式的影响,提出了基于多维上下文认知的数据转发算法MCMF。该算法综合考虑物理邻接性、社会相似性以及社会交互性3个维度的上下文信息来进行动态数据转发决策。首先消息携带者节点通过物理邻接匹配获得邻居节点集合;然后通过社会相似性匹配在邻居节点集合中选出候选节点子集,并基于社会网络的社群特征,采用马尔可夫预测方法在候选节点子集中选出最优中继节点;最后设计高效的数据转发算法。仿真实验表明,相比于其他3种著名算法,该算法在交付比率和开销比率方面具有较好的性能。

无线车载网络中一种基于跨层优化的网络编码TCP协议

陈杰, 谢显中, 黄倩, 黎佳

计算机科学. 2019, 46 (2): 88-94. doi:10.11896/j.issn.1002-137X.2019.02.014

摘要 ( 710 )

PDF(2115KB) ( 1195 )

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

无线车载网络(Wireless Vehicular Networks,WVN)具有研究价值和重要应用价值,目前关于WVN中的网络编码TCP协议的研究并不多,且对跨层的优化也没有被重视。文中首先针对无线车载网络中不同的丢包原因,给出了一种基于随机线性网络编码的跨层联合优化方法VC-TPC/NC,可以针对不同丢包原因采取不同的处理方式;进一步,重新设计了网络编码层发送端的发送策略,并通过理论分析说明了VC-TCP/NC在时延和网络吞吐量方面的优势;最后,在不同场景下的仿真结果表明,VC-TCP/NC的性能相比于传统TCP与TCP/NC等性能有较大提高。

多维敏感特征的Android恶意应用检测

谢念念, 曾凡平, 周明松, 秦晓霞, 吕成成, 陈钊

计算机科学. 2019, 46 (2): 95-101. doi:10.11896/j.issn.1002-137X.2019.02.015

摘要 ( 606 )

PDF(1336KB) ( 1293 )

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

应用程序的行为语义在Android恶意应用检测中起着关键作用。为了区分应用的行为语义,文中提出适合用于Android恶意应用检测的特征和方法。首先定义广义敏感API,强调要考虑广义敏感API的触发点是否与UI事件相关,并且要结合应用实际使用的权限。该方法将广义敏感API及其触发点抽象为语义特征,将应用实际使用的权限作为语法特征,再利用机器学习分类方法自动检测应用是否具有恶意性。在13226个样本上进行了对比实验,实验结果表明,该方法的分析速度快且开销小,选取的特征集使Android恶意应用检测得到很好的结果;经机器学习分类技术的比较,我们选择随机森林作为检测方案中的分类技术,所提特征策略的分类准确率达到96.5％,AUC达到0.99,恶意应用的分类精度达到98.8%。

一种针对无线传感网中黑洞攻击的检测与防御方法

王珺, 朱志伟, 刘俊杰

计算机科学. 2019, 46 (2): 102-108. doi:10.11896/j.issn.1002-137X.2019.02.016

摘要 ( 846 )

PDF(1969KB) ( 1365 )

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

无线传感器网络WSN(Wireless Sensor Networks)被广泛应用于军事、生产、医疗等各个方面,而当下的许多传感器网络都部署在恶劣、开放的环境中,存在各种各样的威胁。黑洞攻击是一种典型的路由攻击,在这种攻击中恶意节点声称自己是剩余能量多、能够一跳到达目的节点的节点或者声称自己就是目的节点,因此很多节点会把要发送的数据发给该恶意节点,而恶意节点吸引数据包后,并不将数据包转发而是丢弃,这就造成传输空洞。针对这种特性,文中提出了一种基于位置信息的诱捕检测算法BTCOLI(Blackhole Attack Detection Algorithm Based on Location Information),以实际不存在的目的节点为诱饵,找到黑洞节点,对其进行身份验证以及位置检测,从而剔除该恶意节点。同时,还提出了相应的防御方案:在网络中加入预共享对称密钥,并提供HMAC(Hash-based Message Authentication Code)消息验证机制,以防止恶意节点加入网络。最后通过搭建NS-2下的仿真平台,验证了该算法在检测率方面的优越性。

一种基于特征提取的访问控制方法

黄美蓉, 欧博, 何思源

计算机科学. 2019, 46 (2): 109-114. doi:10.11896/j.issn.1002-137X.2019.02.017

摘要 ( 461 )

PDF(1459KB) ( 1125 )

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

当前,细粒度的授权控制是访问控制中的研究热点,它能够在单一固定的环境下合理地调整访问策略以满足工作流安全。然而,一旦其迁移到新场景,遭遇访问策略未设定的授权,它就可能难以给出正确判断,只能依靠人工审查来确认是否授权,但人工审查授权耗时耗力,在大数据环境下成本过高。因此,引入一种基于过去经验学习的自动化判别机制势在必行。文中尝试给出一种针对基于角色的多级访问控制模型的自动化审查方法,通过采样已有的正确和错误授权的时间、空间等特征来刻画出该访问控制的一般化特征表达,从而使得已有的访问控制模型在迁移环境下面对新情况依然能够给出正确判断,降低人工审查的工作量。实验表明,该分析机制对用户的访问请求有较高的正确评判率。

基于密钥共享的分层混合认证模型

赵茭茭, 马文平, 罗维, 刘小雪

计算机科学. 2019, 46 (2): 115-119. doi:10.11896/j.issn.1002-137X.2019.02.018

摘要 ( 433 )

PDF(1421KB) ( 979 )

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

随着信息时代的迅速发展,云计算数据访问安全已经成为了用户最关心的问题。身份认证技术是确保参与者在开放的网络环境中实现安全通信的一种重要手段,如何利用身份认证技术为云环境安全保驾护航,成为学者研究的热点。文中通过公钥基础设施(Public Key Infrastructure,PKI)颁发CA证书以在不同云服务间建立信任,将多个采用身份密码体制(Identity-Based Encryption,IBE)的云联合起来;采用分层身份加密体系,引入共享密钥技术,通过选取成环结构,提出一种PKI-IBE混合认证模型方案,并对方案的安全性进行分析,从理论上证明了云环境下PKI-IBE(Public Key Infrastructure-Identity-Based Encryption)同层成环模型提供服务的可行性。同时文中设计了一种基于该模型的签密技术,通过公私密钥对实现云内认证以及跨云认证。安全性理论证明与性能分析表明,该方案在计算量稍增加的前提下,保证了足够的安全性,更加满足云环境下的用户分属不同云域的认证以及用户安全访问的需求,有效解决了云环境中数据访问的安全问题。

面向差分隐私保护的聚类算法

胡闯, 杨庚, 白云璐

计算机科学. 2019, 46 (2): 120-126. doi:10.11896/j.issn.1002-137X.2019.02.019

摘要 ( 989 )

PDF(1916KB) ( 1469 )

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

大数据时代的数据挖掘技术在研究和应用等领域取得了较大发展,但大量敏感信息披露给用户带来了众多威胁和损失。因此,在聚类分析过程中如何保护数据隐私成为数据挖掘和数据隐私保护领域的热点问题。传统差分隐私保护k-means算法对其初始中心点的选择较为敏感,而且在聚簇个数k值的选择上存在一定的盲目性,降低了聚类结果的可用性。为了进一步提高差分隐私k-means聚类方法聚类结果的可用性,研究并提出一种新的基于差分隐私的DPk-means-up聚类算法,同时进行了理论分析和比较实验。理论分析表明,该算法满足ε-差分隐私,可适用于不同规模和不同维度的数据集。此外,实验结果表明,在相同隐私保护级别下,与其他差分隐私k-means聚类方法相比,所提算法有效提高了聚类的可用性。

基于符号执行的Return-to-dl-resolve利用代码自动生成方法

方皓, 吴礼发, 吴志勇

计算机科学. 2019, 46 (2): 127-132. doi:10.11896/j.issn.1002-137X.2019.02.020

摘要 ( 727 )

PDF(1439KB) ( 1436 ) Suppl. Info.

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

Return-to-dl-resolve是一种可突破复杂防护机制的通用漏洞利用技术,目前主要以手工方式实现,研究人员需要深入分析并理解ELF动态链接原理,泄露并解析任意库函数的地址,拼装攻击载荷,效率非常低。文中提出了一种基于符号执行的Return-to-dl-resolve自动化实现方法,该方法为ELF可执行文件提供符号执行环境,对程序崩溃点的符号状态进行约束,通过约束求解器对约束进行求解,实现了Return-to-dl-resolve利用代码自动生成系统R2dlAEG。实验结果表明,R2dlAEG可快速构造利用代码,并能够在NX和ASLR防护机制同时开启的条件下劫持程序的控制流。

云环境下SNS隐私保护方案

刘胜杰, 王静

计算机科学. 2019, 46 (2): 133-138. doi:10.11896/j.issn.1002-137X.2019.02.021

摘要 ( 547 )

PDF(1673KB) ( 1097 )

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

社交网络存储的数据实际都是外包给并不完全可信的云服务商。针对社交网络隐私安全和属性更新问题,提出一种云环境中具有策略隐藏和属性撤销的属性基加密方案。通过分解密钥产生方式降低用户端的计算量,引入合数阶的双线性群实现访问策略隐藏,并利用令牌树和陷门机制灵活且高效地完成属性撤销。而且,该方案在标准假设下可被证明是安全的。因此,将该方案运用于社交网络,将数据加密存储于云服务端是安全可行的。与其他方案相比,该方案既保护了访问策略的隐私,又具有多样的访问控制功能,在计算和存储等方面更有优势。

信息流格模型的非法流分析

王雪健, 赵国磊, 常朝稳, 王瑞云

计算机科学. 2019, 46 (2): 139-144. doi:10.11896/j.issn.1002-137X.2019.02.022

摘要 ( 476 )

PDF(1337KB) ( 981 )

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

随着互联网的发展以及网络空间地位的上升,信息的重要性与日俱增。为确保信息安全,对非法信息流的控制显得尤为重要。文中分析了信息流格模型中信息流动的安全性,为更好地对模型内部的信息流进行分类,首先,对信息流格模型进行线性化分析,使得模型被线性化表述,并将其称为线性信息流格模型。接着,引入马尔科夫链,并利用马尔科夫链的常返态属性和瞬时态属性的概率变化,来量化表示模型中主体和客体之间的转换状态,从而检测出模型内部的各个信息流。进一步地,根据模型内部的主体和客体分别对应的常返态与瞬时态的概率对比,分析每个信息流的安全状态,即:当模型检测中同时出现两个常返态时,违反了安全模型,从而导致非法信息流的出现。由于概率变化存在同一性,该方法会产生误差并影响其检测结果。为弥补这一不足,介绍了SPA语言,然后对线性信息流格模型进行了SPA语言的描述,并采用形式化中的无干扰方法对马尔科夫链模型内概率同一性的不足进行补充说明。最后,检测出其中隐藏的非法信息流,判断出含误差下各个信息流的安全状态,并得出结论:符合安全模型但违反安全策略的信息流不满足无干扰属性。这对信息流安全检测软件的设计及硬件应用具有重要意义。

基于N-gram 的Android恶意检测

章宗美, 桂盛霖, 任飞

计算机科学. 2019, 46 (2): 145-151. doi:10.11896/j.issn.1002-137X.2019.02.023

摘要 ( 732 )

PDF(1828KB) ( 1352 )

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

随着Android系统的广泛应用,Android平台下的恶意应用层出不穷,并且恶意应用躲避现有检测工具的手段也越来越复杂,亟需更有效的检测技术来分析恶意行为。文中提出并设计了一种基于N-gram的静态恶意检测模型,该模型通过逆向手段反编译Android APK文件,利用N-gram技术在字节码上提取特征,以此避免传统检测中专家知识的依赖。同时,该模型使用深度置信网络,能够快速而准确地学习训练。通过对1267个恶意样本和1200个善意样本进行测试,结果显示模型整体的检测准确率最高可以达到98.34%。实验进一步比较了该模型和其他算法的检测结果,并对比了相关工作的检测效果,结果表明该模型有更好的准确率和鲁棒性。

Github中开发人员的行为特征分析

李存燕, 洪玫

计算机科学. 2019, 46 (2): 152-158. doi:10.11896/j.issn.1002-137X.2019.02.024

摘要 ( 673 )

PDF(5570KB) ( 1336 )

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

开源环境下开发人员的行为特征分析是促进开源社区协作开发的重要问题之一。文中以Github开源社区的数据为研究对象,结合可视化分析的技术,分析了Github上开发者贡献度的影响因素,探索了开发者之间的协作关系,进一步分析了开发者所属地域与开发者协作之间的关系。通过研究结果发现了一些具有重要理论和时间价值的现象与结论,从一个新的视角揭示了开发人员的部分行为特征。

基于梦境粒子群优化的类集成测试序列生成方法

张悦宁, 姜淑娟, 张艳梅

计算机科学. 2019, 46 (2): 159-165. doi:10.11896/j.issn.1002-137X.2019.02.025

摘要 ( 548 )

PDF(1750KB) ( 1030 )

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

类集成测试序列的确定是面向对象类集成测试技术中的一个重要课题。合理的类集成测试序列可以降低为其构造测试桩的总体复杂度,从而减小测试代价。针对粒子群优化算法容易早熟的缺陷,文中提出一种基于梦境粒子群优化算法的类集成测试序列生成方法。首先把每个类集成测试序列映射为一维空间中的一个粒子,然后将粒子看作有做梦能力的个体。每个迭代周期分为白天和夜间两个阶段,在白天阶段粒子正常移动,而在夜间阶段粒子根据各自的做梦能力扭曲当前位置。如此,粒子有机会在当前位置附近进行搜索,使得算法减缓收敛速度,避免过早陷入局部最优。实验结果表明,多数情况下该方法可以得到测试代价更小的类集成测试序列。

软件网络分形结构特征研究

潘浩, 郑巍, 张紫枫, 芦超群

计算机科学. 2019, 46 (2): 166-170. doi:10.11896/j.issn.1002-137X.2019.02.026

摘要 ( 573 )

PDF(1928KB) ( 943 )

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

随着互联网技术的发展,软件系统的规模也在日益扩大,软件功能的变化使得软件网络的结构呈现差异化。软件网络的分形结构体现出软件网络整体和局部对象类之间依赖调用的自相似性,可以从代码层面上对软件系统结构以及功能进行分析。文中对软件网络分形结构特征进行研究:首先,综合类之间的依赖关系,对软件网络进行加权;然后利用基于网络中心性的盒子算法计算加权软件网络结构的分形维度,以分析其分形结构特征;最后,利用上述方法对spring和struts2这两款具有代表性的java软件框架进行分析。实验表明,这两款软件以及它们的子模块都具有分形结构特征,软件网络的分形维数随着模块功能复杂程度的增加而增加,功能综合性较强的软件网络分形维数要大于功能专一的软件网络;并且在版本演化过程中,软件网络的分形维数随着软件功能的丰富也呈现上升的趋势。

基于CAN的地理语义数据存储与检索机制

卢海川, 符海东, 刘宇

计算机科学. 2019, 46 (2): 171-177. doi:10.11896/j.issn.1002-137X.2019.02.027

摘要 ( 629 )

PDF(1871KB) ( 1082 )

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

语义技术能够更智能、更精确地检索信息,辅助工作人员进行科学决策,已被应用于地理信息处理,并形成了基于RDF(Resource Description Framework)数据的地理查询语言GeoSPARQL。然而,基于地理语义信息处理的应用平台多采用中心化的存储和检索服务,使得这些平台存在单节点失效、扩展性差等缺陷。尽管已有研究人员提出了多种方法,试图利用对等网络技术来解决语义数据的分布式处理,从而提升应用系统的可靠性和扩展性,但这些方法并没有考虑地理语义数据自身的特征。针对上述问题,文中利用地理语义数据的特征在对等网络上对其进行存储,提出基于CAN(Content Addressable Network)的地理语义存储和检索方案,根据位置信息将地理语义数据映射到对等网络中,从而提高了语义数据的检索效率。实验结果表明,所提方案不仅具有良好的扩展性,而且地理信息的拓扑关系查询效率优于现有方案。

因果信息在不同粒度上的迁移性

姚宁, 苗夺谦, 张志飞

计算机科学. 2019, 46 (2): 178-186. doi:10.11896/j.issn.1002-137X.2019.02.028

摘要 ( 588 )

PDF(1331KB) ( 1115 )

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

知识与粒度相关,在不同粒度上对现象的解释不同,而因果性描述的是现象的本质特征。因果性与粒度之间存在着怎样的关联,一个粒度上的因果关系是否可移植到其他不同粒度上,是目前人工智能研究亟待解决的问题。针对由观测数据构成的信息系统,从数据中直接抽取因果变量所需满足的基本图形结构,估算变量间的因果关系;再通过向系统中添加新属性以及合并多个信息系统,改变原系统中信息的粒度,研究所识别的因果关系在新系统中的可迁移性。若新属性作用于结果变量,则原系统中的因果关系不可迁移至新系统;若新属性对结果变量无影响,则原系统中的因果关系可移植至新系统。

求解Web服务组合QoS优化的多属性决策及自适应遗传算法

鲁城华, 寇纪淞

计算机科学. 2019, 46 (2): 187-195. doi:10.11896/j.issn.1002-137X.2019.02.029

摘要 ( 616 )

PDF(1575KB) ( 1162 )

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

随着面向服务计算(Service-oriented Computing,SOC)的不断发展,基于服务质量(Quality of Service,QoS)的Web服务组合研究成为了必然趋势。鉴于QoS属性的多维性及相互矛盾性,提出将基于QoS的Web服务组合优化问题转化为多属性决策问题进行求解。采用折中系数对每个组合服务实例到正负理想点的距离进行累加求和,最终得到一组最优服务排序结果,用户可以根据自身偏好进行选择。传统的多属性决策方法无法有效地处理大规模的组合服务搜索空间,因此,为了有效地解决Web服务组合优化这一NP难题,提出一种结合多属性决策方法和自适应遗传算法的新型优化算法来解决该问题。实验采用真实的QoS综合服务数据集进行验证,实验结果表明,该方法能够在较短时间内找到全局近似最优解,且解集的排序结果接近于实际的最优服务排序。同时,该方法对于解决大规模的Web服务组合优化问题具有良好的可伸缩性。

基于类别随机化的随机森林算法

关晓蔷, 庞继芳, 梁吉业

计算机科学. 2019, 46 (2): 196-201. doi:10.11896/j.issn.1002-137X.2019.02.030

摘要 ( 750 )

PDF(1495KB) ( 1308 )

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

随机森林是数据挖掘和机器学习领域中一种常用的分类方法,已成为国内外学者共同关注的研究热点,并被广泛应用到各种实际问题中。传统的随机森林方法没有考虑类别个数对分类效果的影响,忽略了基分类器和类别之间的关联性,导致随机森林在处理多分类问题时的性能受到限制。为了更好地解决该问题,结合多分类问题的特点,提出一种基于类别随机化的随机森林算法(RCRF)。从类别的角度出发,在随机森林两种传统随机化的基础上增加类别随机化,为不同类别设计具有不同侧重点的基分类器。由于不同的分类器侧重区分的类别不同,所生成的决策树的结构也不同,这样既能够保证单个基分类器的性能,又可以进一步增大基分类器的多样性。为了验证所提算法的有效性,在UCI数据库中的21个数据集上将RCRF与其他算法进行了比较分析。实验从两个方面进行,一方面,通过准确率、F1-measure和Kappa系数3个指标来验证RCRF算法的性能;另一方面,利用κ-误差图从多样性角度对各种算法进行对比与分析。实验结果表明,所提算法能够有效提升集成模型的整体性能,在处理多分类问题时具有明显优势。

基于子组与社会行为的缩小群组推荐列表方法

毛宇佳, 刘学军, 徐新艳, 张欣

计算机科学. 2019, 46 (2): 202-209. doi:10.11896/j.issn.1002-137X.2019.02.031

摘要 ( 536 )

PDF(1261KB) ( 1136 )

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

以多个用户为推荐对象的组推荐系统已成为研究热点。目前,组推荐系统大多考虑如何充分挖掘用户偏好来尽可能满足所有用户的需求,但这也造成了推荐列表规模过大的问题,从而导致群组成员无法快速做出决定。针对该问题,文中提出了一种缩小群组推荐列表的方法(Recommendation Method based on Sub-Group and Social Behavior,RMSGSB)。该方法通过划分子组来缩小群组规模并减少群组偏好属性数量,利用成员的社会行为,从容忍度与利他行为两方面为子组分配权重,以保证推荐公平性。在真实数据集上的实验对比结果表明,该算法具有更好的群组推荐效果。

融合Jensen-Shannon散度的推荐算法

王永, 王永东, 邓江洲, 张璞

计算机科学. 2019, 46 (2): 210-214. doi:10.11896/j.issn.1002-137X.2019.02.032

摘要 ( 611 )

PDF(1840KB) ( 1382 )

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

为充分利用所有评分,缓解数据稀疏性问题,将概率统计领域的Jensen-Shannon(JS)散度引入相似性度量中,提出了一种新的项目相似性度量算法。该算法将项目的评分信息转化为评分值密度,并依据评分值的密度分布来计算项目相似性。同时,引入评分数量因子,进一步提升了基于JS的相似性度量方法的性能。最后,以基于JS的相似性度量方法为基础,设计了相应的协同过滤算法。在MovieLens数据集上的实验结果表明,所提算法在预测误差和推荐准确性方面均有良好的表现。因此,该算法在推荐系统中具有很好的应用潜力。

基于综合优先度和主机信息的暴雨灾害主题退火爬虫算法

刘景发, 李帆, 蒋盛益

计算机科学. 2019, 46 (2): 215-222. doi:10.11896/j.issn.1002-137X.2019.02.033

摘要 ( 743 )

PDF(1476KB) ( 976 )

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

如今,互联网集成的与暴雨灾害相关的信息多种多样,然而人工搜索网页信息的效率不高,因此网络主题爬虫显得十分重要。在通用网络爬虫的基础上,为提高主题相关度的计算精度并预防主题漂移,通过对链接锚文本主题相关度、链接所在网页的主题相关度、链接指向网页PR值和该网页主题相关度的综合计算,提出了基于网页内容和链接结构相结合的超链接综合优先度评估方法。同时,针对搜索过程易陷入局部最优的不足,首次设计了结合爬虫记忆历史主机信息和模拟退火的网络主题爬虫算法。以暴雨灾害为主题进行爬虫实验的结果表明,在爬取相同网页数的情况下,相比于广度优先搜索策略(Breadth First Search,BFS)和最佳优先搜索策略(Optimal Priority Search,OPS),所提出的算法能抓取到更多与主题相关的网页,爬虫算法的准确率得到明显提升。

面向大坝变形监测的时空一体化预测算法

毛莺池, 曹海, 何进锋

计算机科学. 2019, 46 (2): 223-229. doi:10.11896/j.issn.1002-137X.2019.02.034

摘要 ( 582 )

PDF(2021KB) ( 1262 )

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

大坝变形的时空演变预测分析有助于大坝管理人员及时掌握大坝空间的整体变形状态。目前,大坝变形预测研究分为两个方面:1)通过仅对分布变形仪器部位进行时间序列预测,得出下一时刻的变形值(如BP神经网络);2)利用周围变形数据进行空间插值,得到当前时刻未分布仪器点的变形值。单独使用上述任何一种方法都无法利用历史变形数据预测下一时刻未分布仪器部位的变形状况。针对该问题,结合空间预测模型时空克里金方法(STKri-ging,STK)与神经网络模型即BP神经网络及门限循环神经网络(Gated Recurrent Unit,GRU)各自的优势,构造了一种新型时空序列预测算法(BP-STK-GRU),实现了对未分布监测仪器部位的变形值预测。主要步骤包括:1)GRU优化单个测点的历史时间序列变形值;2)BP拟合测点下一时刻数据的整体趋势;3)利用STK拟合BP预测结果的稳定部分;4)结合空间插值及BP空间整体预测值,得出未分布仪器点的变形值。实验结果表明,所提方法是有效的,并且在对未知点的变形预测稳定性及精确度方面都有很好的表现。

新型软粗糙集:软粗糙半群

路怡瑶, 孔祥智

计算机科学. 2019, 46 (2): 230-235. doi:10.11896/j.issn.1002-137X.2019.02.035

摘要 ( 404 )

PDF(1249KB) ( 991 )

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

为进一步简化处理不确定性问题的方法,在半群上研究了一种新型的软粗糙集(MSR-半群)。首先,基于软集、粗糙集和半群的一些基本理论,对它们之间的关系进行深入研究,并讨论了软粗糙集的运算和基本性质;接着,为了进一步了解软逼近空间,应用了下软粗糙逼近和上软粗糙逼近的概念;同时,在半群上提出了两种特殊软集即G-软集和GG-软集的概念,对其做相应的运算,并给出实例进行了证明;接着,对MSR-逼近空间的粗糙性进行讨论,提出了MSR-半群的概念,并且研究了上MSR-半群和下MSR-半群的基本特征;最后,通过实例进行比较分析,说明了软粗糙半群的研究价值。

一种新的基于粒度重要度的三支决策模型

薛占熬, 韩丹杰, 吕敏杰, 赵丽平

计算机科学. 2019, 46 (2): 236-241. doi:10.11896/j.issn.1002-137X.2019.02.036

摘要 ( 491 )

PDF(1244KB) ( 1056 )

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

粒度重要度是多粒度粗糙集中的一项重要研究内容。针对现有粒度重要度只考虑单个粒度对决策的直接影响而忽略了其他粒度对决策综合影响的问题,结合多粒度粗糙集近似质量的概念,通过研究粒度重要度的构造方法,提出了一种新的多粒度间的粒度重要度的计算方法,并给出了基于该方法的粒度约简算法。同时,为减少冗余决策信息,将约简集与三支决策理论相结合,构建了基于粒度重要度的三支决策模型,给出了决策规则。最后通过实例证明,新的粒度约简算法可以获得具有更高区分度的数据,且缩小了延迟域范围,使最终决策更合理。

优势-等价关系下序贯三支决策的属性约简

李艳, 张丽, 王雪静, 陈俊芬

计算机科学. 2019, 46 (2): 242-148. doi:10.11896/j.issn.1002-137X.2019.02.037

摘要 ( 530 )

PDF(1829KB) ( 1053 )

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

序贯三支决策方法是一种能够表示问题中的多重层次粒度,并将多粒度结合起来解决不确定决策问题的有效途径。优势-等价关系粗糙集则是针对条件属性具有偏好关系的分类问题,提取有序信息,对目标概念进行近似,从而形成决策知识。利用传统的优势关系粗糙集方法进行知识约简和提取的效率低下,而目前大部分序贯三支决策方法则局限在符号值属性的信息系统中,对连续值和有序值不能进行有效处理,造成一定程度的信息丢失。因此,将序贯三支决策的思想应用于优势关系粗糙集模型中,定义了一种新的基于序贯三支决策的属性约简及相应的属性重要度,对具有偏好值属性的信息系统进行更加高效的处理,通过多粒度的表示和关系的研究,加速了知识约简过程。选取了多组UCI数据进行实验,结果表明所提出的基于优势关系的序贯三支决策方法能够在保证约简质量的基础上明显降低时间耗费。

基于多源特征后融合的分层目标检测算法

盛雷, 卫志华, 张鹏宇

计算机科学. 2019, 46 (2): 249-254. doi:10.11896/j.issn.1002-137X.2019.02.038

摘要 ( 539 )

PDF(3647KB) ( 1200 )

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

目标检测是计算机视觉领域的热门研究课题,是视频内容分析的基础。文中提出了一种基于图像多源特征后融合的分层目标检测算法。在该算法中,使用多级决策的思想对目标检测任务进行粗细两个粒度的划分。在粗粒度层面,先使用HOG特征对图像进行分类,根据分类器的置信度分数,将测试图像分为正例、负例和不确定例。在细粒度层面,使用多种视觉特征以及多种核函数后融合的方法对不确定域中的图像做进一步分类。在同一数据集上设置了3组对比实验。实验结果表明,所提算法在各个评价指标上都有出色的表现,且在实际视频的目标检测中的效果优于Faster-RCNN。

基于视觉特性的手机屏幕亮度自适应调节算法

李孟君, 黎文伟

计算机科学. 2019, 46 (2): 255-260. doi:10.11896/j.issn.1002-137X.2019.02.039

摘要 ( 1042 )

PDF(2088KB) ( 3606 )

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

人工智能技术的发展促使人们通过智能手机进行交互,因此设置适宜的手机屏幕亮度对于保护人眼健康至关重要。针对该问题,文中结合人眼视觉特性对手机屏幕自适应亮度调节算法进行了优化。首先,设计了两款测量工具来采集和分析相关的数据。然后,采用主观评价的方法对室内外不同环境照度条件下的手机亮度值进行了研究。实验结果显示,用户理想的手机屏幕亮度远远低于现有自动亮度调节下的手机屏幕亮度。最后,根据用户的体验和人体视觉的特性设计了相应的算法,并对算法进行了评估。

基于线性判别分析的Choquet积分的符号模糊测度提取

王灯桂, 杨蓉

计算机科学. 2019, 46 (2): 261-265. doi:10.11896/j.issn.1002-137X.2019.02.040

摘要 ( 665 )

PDF(1416KB) ( 939 )

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

在解决分类问题时,建立在Choquet积分上的分类器以其非线性和不可加性的特点,扮演着越来越重要的角色。由于Choquet积分中的符号模糊测度可以描述各特征对结果的影响,因此Choquet积分在解决数据分类及融合问题方面具有显著的优势。但是,关于Choquet积分符号模糊测度值的求解,学术界一直缺乏有效的方法。目前最常用的方法是遗传算法,但是遗传算法在解决符号模糊测度值的优化问题时存在算法较为复杂、耗时较长等缺陷。由于符号模糊测度值在Choquet积分分类器中是决定性的重要参数,因此设计出一种有效的符号模糊测度提取方法十分必要。文中提出基于线性判别分析的Choquet积分符号模糊测度的提取方法,推导出在分类问题下Choquet积分的符号模糊测度值的解析式表达,其能够有效、快速地得出关键性参数。分别在人工数据集及基准实际数据集上进行测试与验证,实验结果表明所提方法能有效解决Choquet积分分类器中符号模糊测度的优化问题。

自适应邻域选择的FPFH特征提取算法

吴飞, 赵新灿, 展鹏磊, 关凌

计算机科学. 2019, 46 (2): 266-270. doi:10.11896/j.issn.1002-137X.2019.02.041

摘要 ( 837 )

PDF(2495KB) ( 1562 )

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

在使用点云FPFH(Fast Point Feature Histograms)特征进行三维物体识别或配准时,人为主观调整邻域半径计算FPFH特征描述符具有随意性、低效性,整个过程不能自动化完成。针对该问题,提出了自适应邻域选择的FPFH特征提取算法。首先,对多对点云估算点云密度;然后,计算多个邻域半径以提取FPFH特征用于SAC-IA配准,统计配准性能最优时的半径与点云密度值,使用三次样条插值拟合法求出函数表达式,形成自适应邻域选择的FPFH特征提取算法。实验结果表明,该算法根据点云密度自适应选择合适的邻域半径,提升了FPFH特征匹配的性能,同时加快了运算速度,具有指导价值。

基于HEVC压缩域的镜头边界检测方法

朱威, 商明将, 荣意, 冯杰

计算机科学. 2019, 46 (2): 271-278. doi:10.11896/j.issn.1002-137X.2019.02.042

摘要 ( 496 )

PDF(2198KB) ( 1004 )

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

镜头边界检测是智能视频检索的一个重要环节。现有的检测方法主要是在像素域进行处理,切变检测精度不高,计算复杂度过大。针对这些问题,文中利用解析HEVC码流得到的编码信息,提出了一种基于HEVC压缩域的镜头边界检测方法。首先统计每帧编码信息中各类预测模式的PU个数,并根据CU深度对运动矢量进行幅值滤波;然后采用PU预测模式、运动矢量和帧比特数对切变候选帧进行两级筛选,再对其进行自适应阈值的镜头切变检测;接着根据切变帧对视频序列进行分段,并在时域上对帧比特数进行平滑滤波;最后使用PU预测模式和经滤波平滑后的帧比特数对分段视频进行镜头渐变检测。实验结果表明,该方法具有良好的镜头边界检测效果,并具有较低的计算复杂度。

基于深度学习的交互似然目标跟踪算法

张明月, 王静

计算机科学. 2019, 46 (2): 279-285. doi:10.11896/j.issn.1002-137X.2019.02.043

摘要 ( 593 )

PDF(7806KB) ( 1172 )

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

针对传统的视频跟踪算法对视频跟踪的精度不足以及主成分分析(PCA)的非线性拟合能力较弱的问题,将卷积神经网络与交互似然(IL)算法相结合,在深度学习的基础上对粒子滤波算法进行了优化改进。将核主成分分析(KPCA)网络应用于视频跟踪来获取目标的深层次特征表达,并采用一种新的交互似然图像跟踪器,非迭代地计算,对不同区域进行跟踪取样来减少数据之间的关联需求。在图像集上将所提算法与多种改进算法进行评估对比,结果表明所提算法具有非常好的鲁棒性及精确性。

点线特征融合的误匹配剔除算法

魏玉慧, 王永军, 王国东, 刘红敏, 王静

计算机科学. 2019, 46 (2): 286-293. doi:10.11896/j.issn.1002-137X.2019.02.044

摘要 ( 647 )

PDF(2708KB) ( 1770 )

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

特征匹配作为计算机视觉的一项关键技术而备受关注。近年来,基于描述子的特征点匹配技术取得了一系列突破性进展,但曲线长度不一、端点定位不准确以及周围包含的重复性纹理较多等因素,导致了曲线匹配研究依旧是一个极具挑战性的热点研究课题,且现有曲线匹配方法大多出现匹配总数少、匹配正确率低的问题。为增加特征匹配的总数和正确率,利用特征点和特征曲线的位置关系提出一种点线特征融合的误匹配剔除算法(Point Line feature Fusion,PLF)。首先定义点到曲线的距离,利用点、曲线描述子提取图像的点、线特征;其次确定落入匹配曲线对应支撑区域内的匹配点对,并根据匹配点组和曲线间的距离约束剔除错误曲线匹配;最后利用点线距离约束剔除匹配曲线支撑区域内的错误点匹配。实验选取了3种不同的点线组合,即SIFT技术提取的点特征分别与IOCD曲线描述子、IOMSD曲线描述子、GOCD曲线描述子提取的曲线特征相融合,验证算法对多种点、线描述子具有适用性,且该算法不仅适用于特征点与特征曲线的融合,亦适用于特征点与特征直线的融合,从而验证了其对多种图像特征具有适用性。实验结果表明,在旋转、视角变化、光照变化、压缩、噪音、模糊等变换条件下,该算法均能有效提高曲线特征匹配的匹配总数和匹配正确率,同时提高点匹配的正确率。

一种基于同配性的重叠蛋白质复合体检测算法

王杰, 梁吉业, 赵兴旺, 郑文萍

计算机科学. 2019, 46 (2): 294-300. doi:10.11896/j.issn.1002-137X.2019.02.045

摘要 ( 480 )

PDF(1440KB) ( 943 )

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

蛋白质复合体在生物过程中具有重要的作用,从蛋白质互作用网络中进行蛋白质复合体检测是后基因时代的一项具有挑战性的任务。种子扩展方法是一种从蛋白质互作用网络中进行重叠蛋白质复合体检测的有效技术。然而,现有方法面临两方面的问题:1)在选择种子结点时通常仅仅考虑了网络中结点的直接邻居之间的连接紧密度,难以充分体现结点在局部邻域子图内的重要性;2)在簇的扩展过程中假设候选结点之间是相互独立的,忽略了候选结点的添加顺序可能对聚类结果带来的影响。为了解决以上问题,文中基于生物网络同配性提出了一种重叠蛋白质复合体检测算法。该算法利用结点的二阶邻域信息来度量结点的重要性,进而选择种子结点,在簇扩展过程中利用同配性实现多个候选结点的批量添加。为了对重叠聚类结果进行评价,提出了一种重叠复合体评价指标F-overlap。与其他复合体检测算法在蛋白质互作用数据集上的对比实验结果表明,所提算法能够有效地进行重叠蛋白质复合体检测。

基于彩色编码技术的准种重建算法

黄丹, 吴璟莉

计算机科学. 2019, 46 (2): 301-305. doi:10.11896/j.issn.1002-137X.2019.02.046

摘要 ( 647 )

PDF(1246KB) ( 998 )

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

求解病毒准种单体型有助于了解其基因结构特点,对疫苗的研制及抗病毒治疗具有重要意义。文中通过引入模糊距离,构造一种带权的片段冲突图,并提出了基于彩色编码技术的病毒准种单体型重建算法CWSS。CWSS算法先根据给定阈值对片段冲突图进行预处理;然后根据顶点的边权和及饱和度取值为图中顶点着色,着色遵循相邻顶点颜色相异的原则,直至所有顶点完成着色;最后将相同颜色的顶点片段进行组装,得到准种单体型。CWSS算法的时间复杂度为O(m²n+mn) 。采用模拟测序片段数据进行实验测试,对CWSS算法和Dsatur算法的重建性能和质量进行对比分析。实验结果显示,相比于Dsatur算法,CWSS算法能获得更准确的准种单体型,具有更高的重建性能。

面向GPU计算平台的归约算法的性能优化研究

张逸然, 陈龙, 安向哲, 颜深根

计算机科学. 2019, 46 (2): 306-314. doi:10.11896/j.issn.1002-137X.2019.02.047

摘要 ( 781 )

PDF(1689KB) ( 1602 )

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

归约算法在科学计算和图像处理等领域有着十分广泛的应用,是并行计算的基本算法之一,因此对归约算法进行加速具有重要意义。为了充分挖掘异构计算平台下GPU的计算能力以对归约算法进行加速,文中提出基于线程内归约、work-group内归约和work-group间归约3个层面的归约优化方法,并打破以往相关工作将优化重心集中在work-group内归约上的传统思维,通过论证指出线程内归约才是归约算法的瓶颈所在。实验结果表明,在不同的数据规模下,所提归约算法与经过精心优化的OpenCV库的CPU版本相比,在AMD W8000和NVIDIA Tesla K20M平台上分别达到了3.91~15.93和2.97~20.24的加速比;相比于OpenCV库的CUDA版本与OpenCL版本,在NVIDIA Tesla K20M平台上分别达到了2.25~5.97和1.25~1.75的加速比;相比于OpenCL版本,在AMD W8000平台上达到了1.24~5.15的加速比。文中工作不仅实现了归约算法在GPU计算平台上的高性能,而且实现了在不同GPU计算平台间的性能可移植。

模糊多目标进化的社会团队形成方法

金婷, 谭文安, 孙勇, 赵尧

计算机科学. 2019, 46 (2): 315-320. doi:10.11896/j.issn.1002-137X.2019.02.048

摘要 ( 644 )

PDF(2348KB) ( 899 )

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

目前,基于社会网络的团队形成问题研究大多采取0-1规则度量专家技能。针对人们通常使用自然语言描述专家技能的情况,提出模糊多目标进化的社会团队形成方法。该方法研究模糊环境下如何从专家社会网络中查询出合适的个体并组成规模一定的团队,实现最小的通信代价和最优的团队绩效。其采用模糊语言变量代替以0-1规则为代表的精确参数来描述专家技能,使用团队绩效的概念衡量团队对任务P的技能表现力。鉴于标准SPEA2算法在进化初期收敛速度慢的缺点,引入档案精英学习策略生成优良个体。另外,考虑到专家技能的模糊性,文中提出了细粒度Dominance判断作为判断个体间支配关系的新准则。仿真实验结果证明,改进算法的收敛速度快,获得的近似Pareto前沿更加逼近真实解集,可有效求解团队形成问题。

基于Petri网行为紧密度的有效低频行为模式分析

郝惠晶, 方贤文, 王丽丽, 刘祥伟

计算机科学. 2019, 46 (2): 321-326. doi:10.11896/j.issn.1002-137X.2019.02.049

摘要 ( 461 )

PDF(1375KB) ( 1082 )

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

低频行为模式分析是流程管理的重要内容之一,有效区分低频日志和噪音日志在业务流程过程挖掘中显得尤为重要。目前已有的研究大部分是将流程模型中的低频行为当作噪音直接过滤,但有些低频行为对模型是有效的。文中提出了基于Petri网行为紧密度的有效低频模式分析方法。首先,根据给定的事件日志建立合理的流程模型;然后,通过迭代扩展初始模式来发现流程模型中的所有低频日志序列,并在此基础上计算日志与模型的行为距离向量,利用日志与模型的行为紧密度找出有效的低频行为模式;最后,通过实例分析验证了所提方法的可行性。

迭代学习控制的最优学习律和简化学习律的频域研究

刘加存, 赵桂艳, 梅其祥

计算机科学. 2019, 46 (2): 327-332. doi:10.11896/j.issn.1002-137X.2019.02.050

摘要 ( 467 )

PDF(1939KB) ( 1074 )

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

为了在线性时不变MIMO系统中得到迭代学习控制的最优学习律和便于工程实现的简化学习律,在频域上对其进行了相关研究。以系统的传递函数矩阵为基础,依据Parseval定理,将时域误差关联为频域误差,再利用Jordan标准形矩阵等矩阵性质,得到了学习律的通适收敛条件。通过分析该条件,得出了收敛速度最快的一次迭代就能完成的最优学习律。由于高阶导数不利于消除噪音,因此文中还讨论了导数的降阶,给出了简化学习律算法。仿真结果表明,最优学习律和简化学习律是有效的。