计算机科学

罗卫东,王建新,冯启龙

计算机科学. 2017, 44 (1): 1-6. doi:10.11896/j.issn.1002-137X.2017.01.001

摘要 ( 458 )

PDF(605KB) ( 590 )

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

最大圈分解问题最早由Erds和Pósa提出,随后研究人员在图论领域和理论计算机科学领域中对其进行了广泛的探索。最近研究发现,该问题在计算生物学上特别是在构建进化树与分析基因组的研究方面有重要的应用。主要介绍了该问题的研究现状。首先讨论了该问题在图论方面的研究进展；随后对该问题的近似算法、参数算法、参数复杂性与不可近似性进行了分析和讨论；最后给出了该问题的进一步研究方向。

SHMA:一种云平台的监控框架

陈林,应时,贾向阳

计算机科学. 2017, 44 (1): 7-12. doi:10.11896/j.issn.1002-137X.2017.01.002

摘要 ( 338 )

PDF(1164KB) ( 623 )

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

由于云平台架构的复杂性和工作负载的不可预测性,云监控对保证云平台的高可用性有重要意义,云平台上资源的动态性、多样性以及资源规模巨大给云平台监控带来了一定的困难。研究并提出一种面向云平台的可扩展多层次监控框架SHMA,SHMA采用微服务架构构建监控系统中可扩展的各个相互独立的服务组件,实现对云平台不同层次的应用服务、中间件和基础设施资源的监控。通过对部署并运行在CloudStack基础设施云平台上的某综合减灾空间信息服务应用系统进行案例分析,验证了该监控框架的有效性。

一种动态优先级排序的虚拟机I/O调度算法

郭松辉,龚雪容,王炜,李清宝,孙磊

计算机科学. 2017, 44 (1): 13-19. doi:10.11896/j.issn.1002-137X.2017.01.003

摘要 ( 213 )

PDF(645KB) ( 663 )

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

I/O任务调度是影响I/O密集型虚拟机性能的重要因素。现有调度方法主要是针对虚拟机整机I/O带宽的优化,较少兼顾各虚拟域与全局性能,也无法满足域间差异化服务的要求。针对现有方法的不足,提出了一种动态优先级排序的虚拟机I/O调度算法DPS。该算法基于多属性决策理论,以离差最大化方法计算I/O任务的优先级评估属性权重,对I/O任务优先级进行综合评估；通过引入任务所在虚拟域价值,体现云计算环境下虚拟域重要性差异。在Xen系统中通过实验评测DPS调度虚拟化网卡的性能,结果表明,DPS能够有效提高指定域与全局的I/O任务截止期保证率、整机I/O带宽,并能为不同虚拟域的I/O应用提供差异化服务。

使用Stencil评估Intel AVX2 Vgather指令

林新华,秦强,李硕,文敏华,松岗聪

计算机科学. 2017, 44 (1): 20-24. doi:10.11896/j.issn.1002-137X.2017.01.004

摘要 ( 412 )

PDF(3704KB) ( 1002 )

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

为了更好地在向量化时读取离散的数据,Intel在Haswell CPU提供了AVX2vgather指令。由于Stencil在设置边界条件时使用了条件判断,因此编译器生成了vgather指令,并降低了Stencil在Haswell上的性能。提出使用peel优化或intrinsic load的方法来避免vgather指令的生成,并把该方法应用到3个Stencil基准算例、长程Stencil 程序3DFD以及混合Stencil应用3DEW上。这些Stencil在Haswell上的性能都获得了1.22X至3.88X不等的提升。通过研究指令的实现,发现vgather指令会被解码成多个微操作(μops),并为每个要读入的元素生成一个μops。由于vgather指令解码时会产生较高的开销,导致vgather指令成为Stencil在Haswell上的性能瓶颈。了解AVX2 vgather指令的实现以及掌握避免生成vgather指令的优化方法,对在Haswell上调优具有良好空间局部性应用的性能有一定的参考价值。

一种处理部分标记数据的粗糙集属性约简算法

张维,苗夺谦,高灿,李峰

计算机科学. 2017, 44 (1): 25-31. doi:10.11896/j.issn.1002-137X.2017.01.005

摘要 ( 423 )

PDF(584KB) ( 534 )

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

属性约简是粗糙集理论中重要的研究内容之一,是数据挖掘中知识获取的关键步骤。Pawlak粗糙集约简的对象一般是有标记的决策表或者是无标记的信息表。而在很多现实问题中有标记数据很有限,更多的是无标记数据,即半监督数据。为此,结合半监督协同学习理论,提出了处理半监督数据的属性约简算法。该算法首先在有标记数据上构造两个差异性较大的约简来构造基分类器；然后在无标记数据上交互协同学习,扩大有标记数据集,获得质量更好的约简,构造性能更好的分类器,该过程迭代进行,从而实现利用无标记数据提高有标记数据的约简质量,最终获得质量较好的属性约简。UCI数据集上的实验分析表明,该算法是有效且可行的。

基于高斯-柯西混合模型的单幅散焦图像深度恢复方法

薛松,王文剑

计算机科学. 2017, 44 (1): 32-36. doi:10.11896/j.issn.1002-137X.2017.01.006

摘要 ( 451 )

PDF(1892KB) ( 816 )

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

单幅图像场景深度的获取一直是计算机视觉领域的一个难题。使用高斯分布函数或柯西分布函数近似点扩散函数模型(PSF),再根据图像边缘处散焦模糊量的大小与场景深度之间的关系估算出深度信息,是一种常用的方法。真实世界中图像模糊的缘由千变万化,高斯分布函数以及柯西分布函数并不一定是最佳的近似模型,并且传统的方法对于图像存在阴影、边缘不明显以及深度变化比较细微的区域的深度恢复结果不够准确。为了提取更为精确的深度信息,提出一种利用高斯-柯西混合模型近似PSF的方法；然后对散焦图像进行再模糊处理,得到两幅散焦程度不同的图像；再通过计算两幅散焦图像边缘处梯度的比值估算出图像边缘处的散焦模糊量,从而得到稀疏深度图；最后使用深度扩展法得到场景的全景深度图。通过大量真实图像的测试,说明新方法能够从单幅散焦图像中恢复出完整、可靠的深度信息,并且其结果优于目前常用的两种方法。

在线序列主动学习方法

翟俊海,臧立光,张素芳

计算机科学. 2017, 44 (1): 37-41. doi:10.11896/j.issn.1002-137X.2017.01.007

摘要 ( 472 )

PDF(482KB) ( 747 )

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

现实世界中存在着大量无类标的数据,如各种医疗图像数据、网页数据等。在大数据时代,这种情况更加突出。标注这些无类标的数据需要付出巨大的代价。主动学习是解决这一问题的有效手段,也是近几年机器学习和数据挖掘领域中的一个研究热点。提出了一种基于在线序列极限学习机的主动学习算法,该算法利用在线序列极限学习机增量学习的特点,可显著提高学习系统的效率。另外,该算法用样例熵作为启发式度量无类标样例的重要性,用K-近邻分类器作为Oracle标注选出的无类标样例的类别。实验结果显示,提出的算法具有学习速度快、标注准确的特点。

基于Word2Vec的情感词典自动构建与优化

杨小平,张中夏,王良,张永俊,马奇凤,吴佳楠,张悦

计算机科学. 2017, 44 (1): 42-47. doi:10.11896/j.issn.1002-137X.2017.01.008

摘要 ( 653 )

PDF(612KB) ( 884 )

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

情感词典的构建是文本挖掘领域中重要的基础性工作。近几年,情感词典的极性标注从二元褒贬标注向多元情绪标注发展,词典的领域特性也日趋明显。但是情感类别的手工标注不但费时费力,而且情感强度难以得到准确量化,同时对领域性的过分关注也大大限制了情感词典的适用性[1]。通过神经网络语言模型对大规模中文语料进行统计训练,并在此基础上提出了基于转换约束集的多维情感词典自动构建方法；然后研究了基于词分布密度的感情色彩消歧方法,对兼具褒贬意味词语的感情极性进行区分和识别,并分别计算两种感情色彩下的情感类别与强度；最后提出基于多个语义资源的全局优化方案,得到包含10种情绪标注的多维汉语情感词典SentiRuc。实验证实该词典¹⁾在类别标注检验、强度标注检验、情感消歧效果及情感分类任务中均具有良好的效果,其中的情感强度检验证实该词典具有极强的情感语义描述力。

基于分层筛选和动态更新的并行选择集成算法

吴梅红,郭佳盛,鞠颖,林子雨,邹权

计算机科学. 2017, 44 (1): 48-52. doi:10.11896/j.issn.1002-137X.2017.01.009

摘要 ( 530 )

PDF(1127KB) ( 694 )

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

提出一种选择性集成学习算法,该算法利用多线程并行优化基分类器的参数,通过多层筛选和动态更新筛选信息获取最优的候选基分类器集合,解决了以往在集成学习中选择分类器效率低下的问题。集成分类器采用分解合并的策略进行加权投票,通过使用二分法将大数据集的投票任务递归分解成多个子任务,并行运行子任务后合并投票结果以缩短集成分类器的投票运行时间。实验结果表明, 相对于传统方法, 所提出的算法在平均精度、F1-Measure以及AUC指标上都有着显著提升。

基于中介Agent的强化学习优化协商模型

张京敏,董红斌

计算机科学. 2017, 44 (1): 53-59. doi:10.11896/j.issn.1002-137X.2017.01.010

摘要 ( 255 )

PDF(597KB) ( 635 )

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

提出了一种基于强化学习的双边优化协商模型。引入了一个中介Agent。在强化学习策略中使用不同的参数产生提议,进而选出最好的参数进行协商。为了进一步提高协商的性能,还提出了基于中介Agent自适应的学习能力。仿真实验结果证明了所提协商方法的有效性,且该方法提高了协商的性能。

基于卷积神经网络的自适应权重multi-gram语句建模系统

张春云,秦鹏达,尹义龙

计算机科学. 2017, 44 (1): 60-64. doi:10.11896/j.issn.1002-137X.2017.01.011

摘要 ( 299 )

PDF(1299KB) ( 751 )

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

如今信息量呈爆炸式增长,自然语言处理得到了越来越广泛的重视。传统的自然语言处理系统过多地依赖昂贵的人工标注特征和语言分析工具的语法信息,导致预处理中语法信息的错误传递到系统训练和预测过程中。因此,深度学习的应用受到了学者们的关注。因为它能实现端对端预测并尽可能少地依赖外部信息。自然语言处理领域流行的深度学习框架为了更好地获取句子信息,采用multi-gram策略。但不同任务和不同数据集的信息分布状况不尽相同,而且这种策略并没有考虑到不同n-gram的重要性分布。针对该问题,提出了一种基于深度学习的自适应学习multi-gram权重的策略,从而根据各n-gram特征的贡献为其分配相应的权重；并且还提出了一种新的multi-gram特征向量结合方法,大大降低了系统复杂度。将该模型应用到电影评论正负倾向判断和关系分类两种分类任务中,实验结果证明采用的自适应multi-gram权重策略能够大大改善模型的分类效果。

一种改进的多视图聚类集成算法

邓强,杨燕,王浩

计算机科学. 2017, 44 (1): 65-70. doi:10.11896/j.issn.1002-137X.2017.01.012

摘要 ( 319 )

PDF(457KB) ( 1031 )

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

近年来,针对大数据的数据挖掘技术和机器学习算法研究变得日趋重要。在聚类领域,随着多视图数据的大量出现,多视图聚类已经成为了一类重要的聚类方法。然而,大多数现有的多视图聚类算法受算法参数设置、数据样本等影响,具有聚类结果不稳定、参数需要反复调节等缺点。基于多视图K-means算法和聚类集成技术,提出了一种改进的多视图聚类集成算法,其提高了聚类的准确性、鲁棒性和稳定性。其次,由于单机环境下的多视图聚类算法难以对海量的数据进行处理,结合分布式处理技术,实现了一种分布式的多视图并行聚类算法。实验证明,并行算法在处理大数据时的时间效率有很大提升,适合于大数据环境下的多视图聚类分析。

一种基于用户距离改进的线性影响力传播模型

蔡国永,裴广战

计算机科学. 2017, 44 (1): 71-74. doi:10.11896/j.issn.1002-137X.2017.01.013

摘要 ( 384 )

PDF(296KB) ( 536 )

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

根据在线社交网络中用户的历史行为进行信息传播的预测是当前研究的热点之一,然而传统的传播模型仅解释了信息在社交网络中的传播规律,不具备信息传播预测能力。Jaewan Yang和Jwe Leskovec根据未激活的用户会受到激活用户的影响,提出了线性影响力模型LIM(Linear Influence Model),但是LIM模型在信息传播的过程中只考虑了时间因素,忽略了信息在传播过程中的空间因素,即用户间的相互关系。首先引入社交网络中用户间距离的度量,并结合距离的度量对LIM模型进行了改进,提出了基于距离正则化的LIM模型,即d-LIM模型。真实数据集上的对比实验表明,d-LIM模型能获得更准确的预测结果。

基于枚举策略的三倍体个体单体型重建算法

张倩,吴璟莉

计算机科学. 2017, 44 (1): 75-79. doi:10.11896/j.issn.1002-137X.2017.01.014

摘要 ( 228 )

PDF(486KB) ( 480 )

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

求解三倍体个体单体型对于探索三倍体物种的遗传特性和表型差异等方面的研究具有重要的推动作用。针对带基因型信息的最少错误更正(MEC/GI)模型,提出了一种基于枚举策略的三倍体个体单体型重建算法EHTR。该算法依次重建3条单体型上的每一个单核苷酸多态性位点取值,对于给定位点,首先根据其基因型取值枚举该位点的3种单体型取值情况,然后选择片段支持度最高的取值作为该位点的重建值,算法的总时间复杂度为O(mn+mlogm+cnl)。采用CELSIM和MetaSim两种测序片段模拟生成器生成实验测试数据,在片段覆盖率、错误率、单片段长度、单体型长度和单体型海明距离等参数的不同设置下,对算法EHTR,GTIHR,W-GA和Q-PSO的重建率和运行时间进行对比分析。实验结果显示,算法EHTR在不同的参数设置下均能以更短的运行时间获得更高的重建率。

基于特征挖掘的基因组缺失变异集成检测方法

张晓东,凌诚,高敬阳

计算机科学. 2017, 44 (1): 80-83. doi:10.11896/j.issn.1002-137X.2017.01.015

摘要 ( 277 )

PDF(1813KB) ( 796 )

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

随着高通量测序技术的应用与发展,基于测序的缺失变异检测方法大量涌现。然而,单一检测方法仍存在适用的局限性以及检测精度与敏感度不足的问题。为此,提出一种基于多检测理论融合的特征挖掘与机器学习算法集成的基因组缺失变异综合检测方法。该方法将多种工具应用于个体缺失变异检测,得到变异检测初始集；再根据多种检测理论对初始集中的缺失变异进行序列特征挖掘与特征提取；最后,将检测工具与机器学习算法相融合以获得集成的检测方法,剔除初始集中的假阳性变异,获得最终的结果集。基于千人基因组计划数据的实验表明,相较于单个工具的检测结果,该方法在检测精度和敏感度上均占优势；相较于多个工具检测结果的直接组合,该方法在损失少许检测敏感度的前提下显著地提高了检测精度。

三支决策空间下的区间参数优化模型及应用

李明霞,刘保相,张春英

计算机科学. 2017, 44 (1): 84-89. doi:10.11896/j.issn.1002-137X.2017.01.016

摘要 ( 347 )

PDF(461KB) ( 481 )

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

区间概念格理论是在区间参数基础上提出的一种新的对象挖掘方法,它能够更精确地处理不确定信息。区间参数[α,β]决定了区间概念和格结构,进而对提取的决策准则产生影响。为了解决区间参数优化问题,首先将区间概念格与三支决策粗糙集理论相结合,提出了三支决策空间理论；然后在此基础上将区间概念外延划分为3个域:正域、边界域和负域,并给出了基于区间概念格的三支决策规则与决策损失函数,通过调整区间参数寻找更加可靠的决策准则,从而优化区间参数；最后通过实例对模型进行验证。

基于最小/最大描述的多粒度覆盖粗糙直觉模糊集模型

薛占熬,司小朦,王楠,朱泰隆

计算机科学. 2017, 44 (1): 90-94. doi:10.11896/j.issn.1002-137X.2017.01.017

摘要 ( 431 )

PDF(363KB) ( 527 )

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

覆盖粗糙集和直觉模糊集都是处理不确定性问题的基础理论,它们有着很强的互补性,且覆盖粗糙集和直觉模糊集的融合研究是一个新的热点。对多粒度覆盖粗糙集和直觉模糊集的融合进行深入研究。首先将最小描述、最大描述从单一粒度推广到多个粒度,提出了多粒度的最小描述和最大描述,讨论了多粒度的融合；其次,分别给出了基于最小描述和最大描述的模糊覆盖粗糙隶属度、非隶属度的概念,构建了两种新的模型即基于最小描述的多粒度覆盖粗糙直觉模糊集和基于最大描述的多粒度覆盖粗糙直觉模糊集,并讨论了它们的性质,同时举例说明；最后,分析和研究了两种模型的关系。该研究为多粒度覆盖粗糙集和直觉模糊集的融合提供了一种方法。

基于知识图谱的未登录词语义研究

朱峰,顾敏,郑好,顾彦慧,周俊生,曲维光

计算机科学. 2017, 44 (1): 95-99. doi:10.11896/j.issn.1002-137X.2017.01.018

摘要 ( 404 )

PDF(508KB) ( 523 )

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

传统的应用于未登录词语义研究的语料库包含许多限制,例如更新慢、语言相关等。为了解决此问题,提出了基于知识图谱的中文未登录词语义研究方法。知识图谱是一种包含实体、概念及语义关系的语义网络。它具有丰富的实体,并且实体及其关系的添加极为方便,使得弥补传统语料库更新慢的缺憾成为可能。在充分熟悉知识图谱的结构、数据获取方法及相关数据处理方法后,进行基于知识图谱的未登录词语义研究的探索工作,最后以百度百科(目前最大的中文知识图谱)为语料资源,在同一语义分析模型下分别进行基于知识图谱与传统语料的实验,对实验结果进行分析并提出改进方法。

基于遗传优化谱聚类的图形分割方法

覃晓,梁伟,元昌安,唐涛

计算机科学. 2017, 44 (1): 100-102. doi:10.11896/j.issn.1002-137X.2017.01.019

摘要 ( 358 )

PDF(1007KB) ( 609 )

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

传统的谱聚类方法使用k-means达到最后的聚类目的。k-means对初始条件敏感,易陷入局部最优,从而导致传统的谱聚类方法应用到图像分割时效果不太理想。将遗传算法用于优化谱方法的聚类阶段,提出一种以遗传算法优化普聚类的图像分割方法(Image Segmentation Algorithm of Spectral Clustering Optimization Based on Genetic,ISCOG)。在合成图像与真实图像上的实验表明ISCOG算法极大地提高了谱聚类算法的稳定性和聚类质量,证明了ISCOG算法的优越性。

无线Ad hoc网络中基于0-1优化的两步骤资源分配算法

刘蔚,赵宇,陈锐

计算机科学. 2017, 44 (1): 103-108. doi:10.11896/j.issn.1002-137X.2017.01.020

摘要 ( 229 )

PDF(2014KB) ( 600 )

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

为了解决无线Ad hoc网络中节点性能随节点个数增加而下降的问题,利用多射频多信道技术(MR-MC)进行资源分配以及减少网络干扰量已成为优化无线网络性能的重要技术手段。在此基础上,提出了一种基于0-1规划的网络优化模型和两步骤资源分配算法TBCA&LS(Tree Based Channel Assignment&Link Scheduling)。该算法利用分簇重组网络结构,通过分析相邻链路干扰关系构建0-1优化模型,并在此基础上执行将信道分配和链路调度结合的资源分配算法,减少相邻链路冲突,增加并行传输量,进而达到提升网络吞吐量、优化网络资源分配的目的。最后,在Matlab仿真软件中执行两步骤资源分配算法,实验结果表明,与对比算法CCAS和仅利用信道分配的算法相比,所提算法可以有效优化网络性能。

基于流量预测的无线mesh网络负载均衡路由协议

柳永波,刘乃安,李晓辉,冀琼

计算机科学. 2017, 44 (1): 109-112. doi:10.11896/j.issn.1002-137X.2017.01.021

摘要 ( 234 )

PDF(320KB) ( 513 )

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

提出了一种基于神经网络预测模型的无线mesh网络负载均衡协议NNP-L2MPM。协议根据网络中泛洪的HELLO包计算路径质量,从而选择出到达目的节点的最优下一跳,并以MAC层接口队列长度作为流量负载的衡量依据,然后利用RBF神经网络预测模型对mesh网路中的节点流量负载进行预测,根据预测的下一时刻的流量负载优化路径质量,提前实现路由更新,避免中间节点发生拥塞,进而提高网络性能。仿真结果表明:与原有路由协议相比,所提协议在数据包投递率上提高了约9%,平均端到端延时降低了约16%。

混合群智感知中服务节点优化选择机制

何欣,刘天须,丁爽,白琳

计算机科学. 2017, 44 (1): 113-116. doi:10.11896/j.issn.1002-137X.2017.01.022

摘要 ( 250 )

PDF(327KB) ( 526 )

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

移动群智感知应用依赖于以人为主导的移动用户参与,用户的移动规律和用户所携带感知设备的剩余资源等都会制约其参与感知服务的能力,从而影响系统的感知质量。现有研究工作对服务节点的选取操作比较单一,因此有必要设计合理的节点优化选择机制,选择到达并覆盖目标区域的最优服务节点集,从而保证对目标区域的感知质量。针对服务节点的优化选取展开研究,基于人的移动特性,定义节点服务度量标准,并结合遗传算法设计服务节点优化选取算法,从而提出一种新的服务节点优化选择机制。仿真实验表明,该机制可以有效选取最优服务节点集,达到提高混合群智网络感知服务质量的目的。

移动网络中基于数据到达速率的数据传输能耗优化策略

彭颖,王高才,王淖

计算机科学. 2017, 44 (1): 117-122. doi:10.11896/j.issn.1002-137X.2017.01.023

摘要 ( 239 )

PDF(474KB) ( 474 )

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

数据传输能耗是移动网络能耗的重要部分,提高数据传输能耗效率是优化移动网络能耗的重要课题。考虑数据具有传输延时的要求,研究了基于数据到达速率的数据传输平均能耗最小化问题。利用无线信道质量随机变化的特征,构建基于数据到达速率的平均能耗最小化问题,然后将其转化为最优停止问题,证明最优停止规则存在。最后通过求解最优近视停止规则来获得各侦测时刻的最优传输速率阈值,实现基于数据到达速率的数据传输能耗优化策略。对提出的策略与其他策略就平均能耗、平均传递率和平均调度周期进行了仿真对比,结果表明提出的策略具有较小的平均能耗和较高的平均传递率,取得了较好的能耗优化效果。

一种基于预测与动态调整负载因子的SDN流表优化算法

史少平,庄雷,杨思锦

计算机科学. 2017, 44 (1): 123-127. doi:10.11896/j.issn.1002-137X.2017.01.024

摘要 ( 300 )

PDF(1181KB) ( 646 )

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

通过对SDN流表更新的研究,发现了网络流量高峰期流表更新不及时的问题。提出了一种基于预测与动态调整负载因子的SDN流表优化算法。算法首先收集每个单位时间内的新增流条目,然后用二次移动平均算法对收集的历史数据进行分析,并估计下一个单位时间内新增的流条目,最终根据负载因子动态调整交换机流表中流条目的停滞超时时间。实验结果表明,该算法提高了流表匹配率和数据成功转发率,增加了活动流表项的数量。

基于AC算法的比特流频繁序列挖掘

雷东,王韬,马云飞

计算机科学. 2017, 44 (1): 128-133. doi:10.11896/j.issn.1002-137X.2017.01.025

摘要 ( 189 )

PDF(525KB) ( 543 )

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

为解决比特流频繁序列挖掘效率不高以及易受用户数据影响而导致准确率低的问题,首先从理论上论证了短频繁序列挖掘存在的局限性,根据不同长度的频繁序列挖掘时存在的特点,将其分为长频繁序列与短频繁序列,提出比特流协议头部字段定位算法；基于AC多模式匹配算法分别针对长、短频繁序列挖掘的不同特点,提出了相应的挖掘方法,提高了挖掘结果的准确性。最后通过实验验证了所提算法的有效性。

一种带有能量自补给节点的异构传感器网络分簇路由算法

徐新黎,吕琪,王万良,皇甫晓洁

计算机科学. 2017, 44 (1): 134-139. doi:10.11896/j.issn.1002-137X.2017.01.026

摘要 ( 246 )

PDF(528KB) ( 524 )

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

针对现有无线传感器网络分簇路由算法的网络生命周期短、能量消耗不均衡等问题,结合节点的能量采集技术,提出了一种带有能量自补给节点的异构传感器网络分簇路由算法。考虑到实际环境中节点能量补给不稳定,根据节点的剩余能量和当前能量自补给状态,设计了能量均衡的簇头选举机制和簇间多跳机制。仿真结果表明,在延长网络生命周期和均衡全网能量消耗方面,该算法优于采用相同能量补给规律的传统分簇路由算法(LEACH算法和SEP算法)和其他基于能量自补给的分簇路由算法(PHC算法和EBCS算法)。

射频能量捕获异构无线传感网的能量源最少化布置方法

池凯凯,朱留栓,程珍,田贤忠

计算机科学. 2017, 44 (1): 140-144. doi:10.11896/j.issn.1002-137X.2017.01.027

摘要 ( 196 )

PDF(421KB) ( 512 )

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

电池供电的无线传感器网络的应用由于电池更换的不便利甚至不可能而受到极大的限制。考虑具有射频能量捕获能力的异构无线传感器网络,网络节点的能量捕获输出功率需求不一样。在已知传感节点数目和位置的情况下,研究如何布置射频能量源(Energy Transmitters,ETs)从而满足所有节点的能量捕获输出功率需求并且最小化ETs数目。首先建模出该最少化ETs的布置问题,为深入了解该问题提供了理论基础；然后提出了一种复杂度较低的贪婪式ETs布置方法和一种复杂度略高些的基于粒子群优化的ETs布置方法。仿真结果表明,与贪婪式方法相比,基于粒子群优化的方法能找到ETs略微更少的布置方案,但其由于复杂度略高,因此可用于节点数目不是很多的场景,而贪婪式方法则可用于节点数目较多的场景。

网络时间隐蔽通道的拟合模型特性研究

杨鹏,赵辉,鲍忠贵

计算机科学. 2017, 44 (1): 145-148. doi:10.11896/j.issn.1002-137X.2017.01.028

摘要 ( 347 )

PDF(1142KB) ( 633 )

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

随着计算机网络的飞速发展,网络安全越来越受到人们的关注。在众多的攻击手段中,网络隐蔽通道已成为威胁计算机安全的重要来源之一。由于其隐蔽性较高、不易被发现和传输速率高等特点,网络时间隐蔽通道已成为该领域的研究热点之一。针对网络时间隐蔽通道的传输过程,构建了一种模型,并详细阐述了该模型中运用扩展码对隐蔽信息进行编码和调制的过程。在此基础上,分析了该模型下编码符号的概率分布状况,并与正常信道中的泊松分布拟合函数做了比较全面的对比。针对隐蔽通道的特性——隐蔽性和数据传输速率,首次分析了模型中的参数对其隐蔽性和传输速率的影响,并得到了二者之间的变化关系,这对今后网络时间隐蔽通道的构建工作具有一定的指导意义。

基于B⁺树的多关键字密文排序检索方法

那海洋,杨庚,束晓伟

计算机科学. 2017, 44 (1): 149-154. doi:10.11896/j.issn.1002-137X.2017.01.029

摘要 ( 212 )

PDF(1285KB) ( 679 )

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

针对当前社会信息量大、隐私信息需要加密存储带来的检索难度大等问题,研究分析了现有的基于密文的可搜索加密方案,提出了一种基于B⁺树的多关键字密文排序方法。利用向量模型构建索引和查询陷门,根据相关性分数和关键字匹配度对检索结果进行排序。在真实数据集上进行了实验,结果证明本方案具有较高的检索效率。

基于PKI体系的跨域密钥协商协议

魏振宇,芦翔,史庭俊

计算机科学. 2017, 44 (1): 155-158. doi:10.11896/j.issn.1002-137X.2017.01.030

摘要 ( 303 )

PDF(458KB) ( 653 )

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

基于口令的跨域密钥协商协议和Kerberos协议无法抵抗口令猜测攻击,在金融、航天等通信安全需求高的场所,需要一种更有效的协议来保证通信安全。给出一种新的基于PKI体系的跨域密钥协商协议,采用公钥算法保证数据传输的安全,结合使用Diffie-Hellman协议生成会话密钥。协议有效地解决了利用预置共享密钥参与加/解密实施中间人攻击,以及Kerberos弱口令导致的攻击者可以实施口令猜测攻击的问题。跨域通信的公钥信息仅存储在各自域认证服务器,域内用户不需要配置跨域服务器的公钥信息,降低了配置复杂度、域内用户和域认证服务器之间密钥管理的复杂性,同时提高了域服务器鉴别身份的能力和信息机密性,使其免疫多种攻击,具有良好的前向安全性和扩展性。

以网络性能为核心的移动自组网Flooding攻击防御技术

王伟,王嘉郡,王明明,张文静,陈金广

计算机科学. 2017, 44 (1): 159-166. doi:10.11896/j.issn.1002-137X.2017.01.031

摘要 ( 223 )

PDF(1299KB) ( 547 )

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

移动自组网(Mobile Ad Hoc Networks,MANETs)所面临的Flooding攻击是一种严重DOS攻击行为。然而,现有的针对Flooding攻击的防范技术因不能较好地适应MANETs特性(如有限资源、动态拓扑等)而难以在MANETs网络性能和网络安全之间保持平衡。通过分析移动自组网的时空动态性、网络性能评估与Flooding安全威胁之间的内在关系,提出了一种基于性能评估的Flooding攻击防御技术。通过构建可量化的MANETs安全威胁、防御收益与代价的评估指标体系,实现了基于网络安全和性能平衡的防御及其性能优化方法。仿真实验结果表明,所提出的防御技术可有效地弥补现有移动自组网安全技术存在的一些缺陷,因而能够满足移动自组网特性且适合于实际应用。

一种改进的属性加密方案

宋文纳,向广利,李安康,张月欣,陶然

计算机科学. 2017, 44 (1): 167-171. doi:10.11896/j.issn.1002-137X.2017.01.032

摘要 ( 243 )

PDF(487KB) ( 774 )

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

属性加密适合一对多的广播加密环境,很好地保护了用户的隐私,而且容易实现细粒度的访问控制。然而已有的属性加密方案中安全性假设过强、运算效率较低。通过对Waters方案的安全性假设进行分析,提出了随机参数满足一定特定关系的Eq-BDHE假设。基于该假设实现了一种改进的CP-ABE加密方案。安全分析和对比实验表明,改进方案降低了安全假设强度,在标准模型下能够抵抗选择明文攻击,同时减少了随机参数的数量,提高了运算效率。

一种改进的基于标签部分ID的RFID密钥无线生成算法

黄琪,凌捷,何晓桃

计算机科学. 2017, 44 (1): 172-175. doi:10.11896/j.issn.1002-137X.2017.01.033

摘要 ( 239 )

PDF(349KB) ( 590 )

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

针对无线射频识别系统存在的初始密钥易泄露的安全问题,提出了一种基于标签部分ID的RFID密钥无线生成算法。在标签与读写器认证之前,通过标签部分ID与读写器生成的随机数进行异或运算生成共享密钥。安全性分析表明,该算法能够有效地抵抗重放攻击、中间人攻击和去同步化攻击等主动攻击及被动攻击,具有安全性高、成本低的优点。

面向Android的RSA算法优化与二维码加密防伪系统设计

方文和,李国和,吴卫江,洪云峰,周晓明

计算机科学. 2017, 44 (1): 176-182. doi:10.11896/j.issn.1002-137X.2017.01.034

摘要 ( 270 )

PDF(1878KB) ( 684 )

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

面向Android智能手机终端,研究设计了移动二维码加密防伪系统,其加密模块基于RSA算法。为解决RSA算法在移动终端的运行效率问题,结合 Monte Carb型概率算法与Miller-Rabin素数测试优化策略得到快速随机强素数算法以提高RSA算法的初始化及加密效率,并且采用MMRC解密算法来优化RSA解密过程,还引入了M-ary算法来对RSA算法过程中所进行的模幂运算进行优化计算。通过以上3个方面优化的实现,200次对比实验表明,改进的RSA算法在Android加密防伪模块中的执行效率比原有算法有明显提升。

一种新的超轻量级RFID认证协议

张亚力,郭亚军,崔建群,曾庆江

计算机科学. 2017, 44 (1): 183-187. doi:10.11896/j.issn.1002-137X.2017.01.035

摘要 ( 265 )

PDF(412KB) ( 495 )

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

RFID(无线射频识别)技术以无线通信的方式广泛运用于生活生产的各个领域,如门禁设备、支付设备等,但阅读器和标签之间无线开放的通信环境使得RFID设备面临更多的恶意攻击和安全威胁。低成本标签只具有非常有限的计算能力和存储空间,一般的分组密码和hash函数等都不能用于低成本标签中。为了解决低成本标签的安全性问题,采用比特位运算密码原语,提出一种新的超轻量级RFID认证协议——SIUAP。SIUAP协议在SIMON 类算法的超轻量级轮函数F(x)和非线性函数MIXBITS运算的基础上,使用3种简单的比特位运算:比特AND运算、异或运算和循环移位运算,大大降低了计算复杂度。通过GNY逻辑对协议进行形式化的分析,证明了SIUAP协议能够实现阅读器和标签双向合法身份的认证,同时对SIUAP进行安全性分析。与现有的超轻量级认证协议相比,SIUAP协议具有较小的计算开销,能够满足RFID系统低成本、高安全性的需求。

基于一个新的四维离散混沌映射的图像加密新算法

朱淑芹,李俊青,葛广英

计算机科学. 2017, 44 (1): 188-193. doi:10.11896/j.issn.1002-137X.2017.01.036

摘要 ( 278 )

PDF(2986KB) ( 544 )

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

基于修正版Marotto定理构造了一个四维离散混沌映射,并利用该四维离散混沌映射序列设计了一种图像加密方案。该方案利用图像的256位哈希值来生成混沌序列的初始值,由此混沌序列产生的密钥与明文相关,进一步增强了加密系统的安全性。理论分析和仿真试验表明:该加密方案至少具有3.4×10¹⁰⁰的密钥空间；加密后图像直方图接近均匀分布;像素的相关性被消除；信息熵接近8bit,没有明显的统计信息。该加密方案对混沌系统的初始条件扰动极为敏感,任何大于10－15的扰动都将使解密失效；加密图像对明文图像极为敏感,能够抵抗差分攻击。

计算最终线性秩函数的新方法

朱广,李轶,吴文渊

计算机科学. 2017, 44 (1): 194-198. doi:10.11896/j.issn.1002-137X.2017.01.037

摘要 ( 233 )

PDF(460KB) ( 473 )

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

程序的终止性分析作为程序验证中重要的一环,在软件正确性验证中极为重要。对于一个线性循环程序,若该程序没有传统定义的线性秩函数,则基于传统定义的秩函数终止性分析方法失效。2013年,Bagnara提出了最终线性秩函数(Eventual Linear Ranking Functions)的定义,并证明了若某个程序存在最终线性秩函数,则该程序终止。由此,提出了新的方法来计算最终线性秩函数,构造了存在线性增函数和最终线性秩函数的等价半代数系统,并使用Mathematica工具对半代数系统进行求解,对比分析了各种最终秩函数求解方法的实际计算时间,结果证实了所提方法的优越性。

形式语言基于Monads的语义计算模型

苗德成,奚建清,苏锦钿

计算机科学. 2017, 44 (1): 199-202. doi:10.11896/j.issn.1002-137X.2017.01.038

摘要 ( 182 )

PDF(410KB) ( 703 )

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

传统形式语言的语义建模方法在语义解释与规则描述等语义计算方面存在不足,应用范畴论方法的Monads对形式语言的语义计算进行了研究。基于Monads构造Kleisli范畴,在Kleisli范畴的形式化框架内建立语义计算模型,并对该模型进行了应用。与传统语义建模方法相比,所提语义计算模型具有普适性,其语义解释与规则描述的能力更强。

服务组合BPEL测试序列生成研究

张亚

计算机科学. 2017, 44 (1): 203-207. doi:10.11896/j.issn.1002-137X.2017.01.039

摘要 ( 168 )

PDF(1115KB) ( 511 )

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

为更好地对Web服务组合的控制流进行分析和验证,提出一种映射转换模型和测试序列生成算法。首先解析基于BPEL的Web服务组合流程描述文件,然后对流程描述文件进行图形化转换,形成业务流程编排控制流程图,再采用路径推导算法对控制流程图进行解析,获取基于BPEL的服务组合的所有测试执行路径,最后通过一个服务组合实例证明模型及算法的有效性。该方法解决了测试路径的自动生成和全覆盖问题,保证了测试的充分性,提高了路径生成效率。

基于数据库负载的SQL能耗预测模型

国冰磊,于炯,廖彬,杨德先

计算机科学. 2017, 44 (1): 208-213. doi:10.11896/j.issn.1002-137X.2017.01.040

摘要 ( 407 )

PDF(540KB) ( 875 )

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

传统数据库以性能(吞吐量、响应时间)为首要优化目标,忽略了数据库系统的能量消耗。在一味追求性能的同时,高能耗问题日益突出,为数据库负载构建能耗模型是构建绿色数据库的基础。通过量化查询负载执行过程中对系统资源(CPU与磁盘)的消耗,将资源消耗产生的时间代价和功耗代价转化为时间代价预测模型和功率代价预测模型,在单站点数据库服务器上实现了为数据库系统构建资源单位代价统一的能耗预测模型。采用多元线性回归工具拟合模型的重要参数,实验结果验证了能耗预测模型的可行性；并分别在静态与动态的系统环境下对系统不同类型查询负载的能耗进行预测与评价,验证了该模型的准确性,使得提出的能耗模型适合于构建能耗感知的绿色数据库。

基于本体和局部共现的查询扩展方法

王旭阳,尉醒醒

计算机科学. 2017, 44 (1): 214-218. doi:10.11896/j.issn.1002-137X.2017.01.041

摘要 ( 267 )

PDF(403KB) ( 672 )

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

将语义扩展与统计扩展相结合,提出了一种基于本体和局部共现的查询扩展方法,该方法利用本体和局部共现分别得到语义候选扩展概念集和统计候选扩展概念集,对这两个扩展集进行二次筛选以得到最终的查询扩展概念；并给出了一种计算扩展词权重的方法。实验结果表明,扩展后的查询更能反映用户的查询请求,在设计的语义检索系统中,该方法能有效提高查全率和查准率。

基于二维划分的杰卡德相似系数批量计算效率优化

廖彬,张陶,于炯,国冰磊,刘继

计算机科学. 2017, 44 (1): 219-225. doi:10.11896/j.issn.1002-137X.2017.01.042

摘要 ( 356 )

PDF(580KB) ( 577 )

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

随着互联网用户及内容的指数级增长,大规模数据场景下的杰卡德相似系数计算对算法的效率提出了更高的要求。为提高算法的执行效率,对MapReduce架构下的算法执行缺陷进行了分析,结合Spark适用于迭代型及交互型任务的特点,基于二维划分算法将算法从MapReduce平台移植到Spark平台；并通过参数调整、内存优化等方法进一步提高了算法的执行效率。两组数据集分别在3组不同规模的集群上的实验结果表明,与MapReduce相比,Spark平台下的算法执行效率提高了4倍以上,能耗效率提升了3倍以上。

粗等价粒度下基于多种加速策略的增量式求核算法

赵洁,张恺航,董振宁,梁俊杰,徐克付

计算机科学. 2017, 44 (1): 226-234. doi:10.11896/j.issn.1002-137X.2017.01.043

摘要 ( 205 )

PDF(796KB) ( 469 )

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

提出一种全新的渐增式求核算法。首先基于全局等价类提出粗等价类概念并分析其性质,研究粗等价类下的求核与约简；深入研究3类粗等价类与核属性的内在联系,设计粗等价类下判断核属性的等价方法和渐增式求核方法,通过该方法可在一次增量计算中求得多个非核属性,从而设计双向剪枝策略；可从属性和实体双方面缩减计算域,无需遍历全部属性和实体,在无核情况下,剪枝策略仍然有效。设计多次Hash的属性增量划分算法来完成上述增量式计算,基于此给出完整的渐增式求核算法。最后用UCI中20个决策表及海量、超高维3类数据集从多个角度进行验证,实验结果证明了所提算法的有效性和高效性,其尤其适用于大型决策表,大多数情况下优于现有算法。算法可进一步作为新型约简和优化算法的基础。

基于静态前提的谓词知识树分解策略

边芮,吴向军,陈蔼祥

计算机科学. 2017, 44 (1): 235-242. doi:10.11896/j.issn.1002-137X.2017.01.044

摘要 ( 352 )

PDF(720KB) ( 509 )

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

智能规划问题实质是一种搜索问题,通常需采用某种策略来缩小搜索空间,提高规划效率。在“以谓词为主体”的规划求解方法中,规划树的生成效率将直接影响规划求解效率。为此,提出了基于静态前提的谓词知识树分解策略,并给出了相应的分解算法。对任意一个规划领域,利用该分解算法可将知识树分解成若干个较小规模的知识子树。在规划求解的过程中,利用知识子树可有效地减少搜索空间,从而快速生成规划树,提高规划效率。同时,利用知识子树还可提取出隐含在动作描述中的领域知识。实验结果表明该分解算法是有效的。

一种稀疏可控的主成分分析方法

谭亚芳,刘娟,王才华,蒋万伟

计算机科学. 2017, 44 (1): 243-246. doi:10.11896/j.issn.1002-137X.2017.01.045

摘要 ( 261 )

PDF(369KB) ( 775 )

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

主成分分析(Principal Component Analysis,PCA)是一种用线性变换选出少数重要变量(降维)的多元统计分析方法。虽然传统PCA被广泛应用于科学研究与工程领域中,但是其结果有时很难解释。因此,一些研究人员引入稀疏约束项(lasso、fused lasso以及adaptive lasso等),以得到可解释的结果。由于传统稀疏项的稀疏度不容易控制,为此引入一种新的约束项,即稀疏可控惩罚项(Sparse Controllable penalty,SCP),来控制主成分的稀疏程度。与传统的约束项相比,SCP具有长度不敏感、维度不敏感和约束项的取值范围在0到1之间的优点。这些优点极大地降低了调节稀疏度的难度。实验表明,稀疏可控主成分分析(Sparse Controllable Principal component Analysis,SCPCA)是高效的。

基于二分迭代SAX的时序相似性度量算法

张建辉,王会青,孙宏伟,郭芷榕,白莹莹

计算机科学. 2017, 44 (1): 247-252. doi:10.11896/j.issn.1002-137X.2017.01.046

摘要 ( 345 )

PDF(1050KB) ( 866 )

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

时序降维是解决时间序列高维问题的关键技术。符号聚集近似表示(SAX表示法)作为一种时序降维技术,具有良好的维度约简能力与性能稳定的下界距离算法,但算法中分段数的选取需根据当前时序数据的特征而人为设定。针对这一问题,引入了滑动窗口算法与统计学方法,提出了基于二分迭代SAX的时序相似性度量算法。实验结果表明,该算法不仅解决了分段数设定困难的问题,而且降低了时序降维表示的复杂度,提高了SAX算法在多种时序数据上的分类准确性。

基于直觉模糊支配的混合多目标粒子群算法

梅海涛,华继学,王毅,文童

计算机科学. 2017, 44 (1): 253-258. doi:10.11896/j.issn.1002-137X.2017.01.047

摘要 ( 276 )

PDF(955KB) ( 572 )

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

为提高求解多目标优化问题的精确性和解集分布的均匀性,提出了一种基于直觉模糊支配的混合粒子群算法。通过引入种群全局目标值标量参数、直觉模糊隶属度和排序方法,定义一种新的最优解支配关系；采用基于模拟退火的Meta-Lamarckian局部学习策略,结合粒子群算法,以避免算法陷入局部最优和早熟；此外,定义种群同构因子来衡量种群多样性,以自适应调节惯性权重和加速因子；提出一种递减扰动策略对粒子飞行速度进行扰动；最后,与多种经典多目标优化算法进行仿真测试比较,结果表明该算法在求解精度、解集分布均匀性上具有明显优势。

业务流程模型抽象中基于约束的行为聚类方法研究

王楠,孙善武

计算机科学. 2017, 44 (1): 259-263. doi:10.11896/j.issn.1002-137X.2017.01.048

摘要 ( 274 )

PDF(529KB) ( 468 )

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

将业务流程模型抽象中的行为聚合解释为一个半监督聚类过程,利用基于试探的启发式方法选择合适的行为集合作为初始簇,进而提高抽象的质量。另外,为了同时满足模型转换的保序性需求和子流程的业务语义完整性,在将行为归类到某个簇(候选子流程)时,进一步考虑了流程控制流的影响,设计了由两部分构成的约束函数,即语义距离和控制流顺序冲突。其中,第一部分引入了虚拟文档来表示行为和子流程,计算其之间的语义距离；第二部分利用行为概要文档中的4种行为顺序关系,设计函数来表示行为归类带来的控制流冲突。将该方法应用于真实的流程模型库,与传统的k-means行为聚类对比,如随机生成初始簇集和基于语义的距离测量方法,结果表明所提方法生成了更接近于人工设计的流程抽象结果。

基于alpha支配的高维目标进化算法研究

林梦嫚,周欢,王丽萍

计算机科学. 2017, 44 (1): 264-270. doi:10.11896/j.issn.1002-137X.2017.01.049

摘要 ( 423 )

PDF(537KB) ( 745 )

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

基于Pareto支配的多目标进化算法能够很好地处理2～3维的多目标优化问题。但在处理高维多目标问题时,随着目标维数的增大,支配受阻解的数量急剧增加,导致现有的多目标算法存在选择压力不够、优化效果较差的问题。通过引入α支配提供严格的Pareto分层,在同层中挑选相对稀疏的解作为候选解,同时详细分析不同α对算法性能的影响,提出一种新的基于α偏序和拥塞距离抽样的高维目标进化算法。将该算法在DTLZ上进行性能测试,并采用世代距离(GD)、空间评价(SP)、超体积(HV)等多个指标评估算法的性能。实验结果表明,引入α支配能去除绝大部分支配受阻解(DRSs),提高算法的收敛性。与快速非支配排序算法(NSGA-II)、基于分解的多目标进化算法(MOEA/D)、基于距离更新的分解多目标进化算法(MOEA/D-DU)相比,该算法的整体解集的质量有明显提高。

非确定有穷自动机在盲文转码中的应用

张居晓

计算机科学. 2017, 44 (1): 271-276. doi:10.11896/j.issn.1002-137X.2017.01.050

摘要 ( 353 )

PDF(1118KB) ( 744 )

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

对盲人使用的计算机交互技术进行研究是很有意义的工作。盲文字库缺少国际标准和不同公司的盲文字库不兼容造成了很多难题。将盲文用汉字点位编码表示,能摆脱盲文字库的束缚。用不确定有穷自动机描述盲文与汉字点位编码的转换过程,再用逆序拆分子集法对其确定化。经测试系统的转码正确率达到100%,从而实现盲文与机器无关,使得盲人使用计算机更方便。

社交网络数据采集技术研究与应用

徐雁飞,刘渊,吴文鹏

计算机科学. 2017, 44 (1): 277-282. doi:10.11896/j.issn.1002-137X.2017.01.051

摘要 ( 292 )

PDF(528KB) ( 834 )

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

随着社交网络的快速发展,对其研究也逐步深入。显然,社交网络基础数据的获取对研究具有非常重要的意义。针对目前已有的数据采集方案,根据新浪授权标准以及最新的微博加密方式,研究了两种采集方案:1)经OAuth2.0认证后,通过微博API接口获取数据；2)在RSA2加密方式下模拟登录微博,再通过网络爬虫抓取数据。同时,还研究了通过网页采集器针对微博编写适当的采集规则进而实现对数据的获取。3种数据采集方案都能有效地对数据进行采集且各具特点,针对数据的采集需求,提出融合不同的采集方案的策略。经实验研究,方案的融合策略可快速、高效地实现大数据量的采集。

相关集的数据关联描述及实例讨论

闫林,阮宁,闫硕,高伟

计算机科学. 2017, 44 (1): 283-288. doi:10.11896/j.issn.1002-137X.2017.01.052

摘要 ( 185 )

PDF(641KB) ( 530 )

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

为了讨论数据关联问题,按层次对数据集进行了粒化,引入了每一粒的相关集,产生了与相关集类关联的分层粒化结构,并称之为粒化树。进而以同一数据集上的两棵粒化树为结构支撑,完成了对数据关联的定义,使相关集之间数据的关联得以数值化表示,形成了数据关联的数值描述方法。对此的研究确定了数据关联的等价条件,以此为依托并通过实例探究了数据关联的相关性质,讨论了关联的紧密程度、数据的粒化等同、关联的相互比较等数值化的处理方法。同时为实例的讨论提供了算法编程的基础,表明了数据关联研究的实际意义。

基于SIFT和非参贝叶斯的高分辨率遥感影像地物识别算法

王健,白鹤翔,李德玉

计算机科学. 2017, 44 (1): 289-294. doi:10.11896/j.issn.1002-137X.2017.01.053

摘要 ( 203 )

PDF(1232KB) ( 590 )

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

地物识别是遥感图像处理领域中的一个重要问题。随着遥感技术的发展,高分辨率遥感影像中携带有大量相似的具有尺度不变特征的地物,传统的地物识别方法难以适应这一发展,亟需对其进行改进。针对高分遥感影像,在SIFT(Scale-invariant Feature Transform )算法的基础上进行改进并得出一种快速精准的地物识别算法DBSIFT(Double Backward SIFT),实现了相似地物多对一的模式识别。DBSIFT在原算法的基础上构造了二重差金字塔,利用DP(Dirichlet Process)识别出相似地物并对其进行分割。在几何与算数关系上,选取9个指标对分割精度进行评价。实验中,使用该方法得到的地物能够被准确识别,且分割效果良好,说明了该算法的有效性。

基于区域特性的压缩感知多聚焦融合算法

曹义亲,贺亚飞,黄晓生

计算机科学. 2017, 44 (1): 295-299. doi:10.11896/j.issn.1002-137X.2017.01.054

摘要 ( 254 )

PDF(1137KB) ( 433 )

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

传统的基于压缩感知的图像融合算法是对整个系数进行稀疏处理,而小波分解后的低频系数不稀疏,导致压缩重构质量降低,并且传统的融合规则不易简单、全面地提取高频系数的特征值。针对这一问题,分别对小波分解得到的高、低频系数采取不同的融合规则进行处理,提出了一种改进的区域特性高频压缩感知的融合算法。其中,低频系数采用区域方差加权绝对值最大融合；高频系数首先通过具有较好RIP性质的随机观测矩阵进行压缩采样,得到的观测值基于能量匹配度的不同进行相加或加权融合,以融合不同方向的高频子带特征信息,再用正交匹配追踪重构算法对高频部分进行信号重构。最后,低频、高频信息在小波逆变换下重构出融合图像。实验结果表明,与以往的基于压缩感知的融合方法相比,此算法的融合图像更清晰,新算法无论是在主观评价还是客观评价指标上都有利于图像信号重构,并具有较好的使用性。

一种基于改进渗流模型的混凝土表面裂缝快速检测算法

瞿中,郭阳,鞠芳蓉

计算机科学. 2017, 44 (1): 300-302. doi:10.11896/j.issn.1002-137X.2017.01.055

摘要 ( 368 )

PDF(889KB) ( 775 )

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

由于混凝土表面不平整、光照不均、裂缝背景较为复杂等因素的干扰,传统的基于图像处理的裂缝检测方法对裂缝检测的效果不佳,尤其是不清晰和比较细小的裂缝。基于渗流模型的裂缝检测方法充分考虑了裂缝亮度低、形状较为细长的特点,对裂缝的检测效果很好,尤其是图像中的细小裂缝,但是该方法需要大量的处理时间。为了解决上述问题,提出了一种加速渗流处理的算法,该算法通过暗点预提取来减少渗流时需要处理的像素点个数,以此来减少渗流处理时间。实验结果表明,所提算法能明显加快渗流处理的速度,并且精确率基本保持不变。

基于Haar特性的改进HOG的人脸特征提取算法

蒋政,程春玲

计算机科学. 2017, 44 (1): 303-307. doi:10.11896/j.issn.1002-137X.2017.01.056

摘要 ( 338 )

PDF(428KB) ( 660 )

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

现有的大多数特征提取算法在提取人脸特征时,容易受到光照等外界因素的影响,从而导致后期人脸识别率下降。而方向梯度直方图(Histogram of Oriented Gradient,HOG)具有较强的光照鲁棒性,能够很好地减少由光照带来的干扰,但传统HOG在计算梯度幅值和方向时只计算水平和垂直方向上4个像素点对中间像素的影响,当外界环境变化时不能保证稳定性,因此提出一种基于Haar特性的改进HOG的人脸特征提取算法。该算法在计算梯度幅值和方向时考虑水平、垂直以及对角线上8个像素点对中间像素的影响,由于增加计算量导致特征提取时间也随之增加,因此引入Haar,借助Haar型特征运算简单、快捷的特点设计4组Haar型特征编码模式,按照改进的HOG特征计算方式提取人脸特征。在有光照等外界因素影响的FERET人脸数据库和Yale B扩展的人脸测试库中进行实验,实验结果表明,与GFC,LBP和其他文献中的HOG算法相比,该算法对光照具有更好的鲁棒性,能够在光照变化的环境下提高人脸识别率。该算法在FERET探测集fb,fc,dup1和dup2上的识别率分别为95.1%,80.9%,70.1%和63.2%,在Yale B中的识别率为89.1%。

基于双目立体视觉的船舶轨迹跟踪算法研究

黄椰,黄靖,肖长诗,姜文,孙毅

计算机科学. 2017, 44 (1): 308-313. doi:10.11896/j.issn.1002-137X.2017.01.057

摘要 ( 435 )

PDF(1240KB) ( 828 )

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

双目立体视觉模型通过模拟人眼可以实现对目标距离的测量。为了获得水上船舶实时的运动状态,提出了一种基于双目立体视觉的船舶轨迹跟踪方法。首先,通过摄像机标定、线性空间点三维重建可以测得以相机为中心到船舶的距离,得到船舶的部分运动轨迹；其次,在双目立体视觉测距系统的基础上采用常速(Constant Velocity,CV)模型的方法对船舶运动建模；最后,对建立的船舶运动模型利用强跟踪卡尔曼滤波(Strong Tracking Kalman Filter,STKF)船舶轨迹跟踪的方法跟踪船舶的轨迹并估算目标船舶实时的运动状态。实验结果表明,基于双目立体视觉的船舶轨迹跟踪的方法能有效地跟踪船舶轨迹且适用于工程应用的需求。

基于稀疏编码与方向-尺度描述子的海马体自动分割

刘颖,张明慧,阳维,卢振泰,冯前进,苏榆生

计算机科学. 2017, 44 (1): 314-320. doi:10.11896/j.issn.1002-137X.2017.01.058

摘要 ( 265 )

PDF(3268KB) ( 505 )

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

海马体病变与神经疾病息息相关,海马体解剖结构的不规则性以及其与周围组织结构如杏仁体边界模糊增加了分割海马体的难度。提出一种新的基于稀疏编码和方向-尺度描述子(Sparse Coding and Orientation-Scale Descriptor,SCOSD)的算法来提高海马体分割精度。不同于主流的基于字典学习的方法,SCOSD算法用同时包含灰度纹理信息和空间结构信息的方向-尺度描述子(Orientation-Scale Descriptor,OSD)代替低维特征来描述像素特征,OSD的优点是它同时包含多种低维特征且能降低图谱间灰度不均匀性的影响。SCOSD算法包括4个步骤:1)图像预处理。2)特征提取,提取待分割图像像素和图谱图像像素的方向-尺度描述子。3)字典构建及稀疏编码,选取图谱像素的方向-尺度描述子作为目标像素来构建特有字典,用特有字典近似表达即重建目标像素并得到稀疏编码系数。4)标号融合及阈值判定,融合图谱像素的标号和编码系数得到目标像素的标号估计值；阈值判定估计值完成分割。为了验证SCOSD算法分割的准确性,分别用SCOSD算法,Simple,Major Voting,Staple,Collate分割MICCAI数据库内的海马体,以Dice值作为分割评判标准,实验结果表明,SCOSD方向-尺度描述子的分割精度高于 Simple,Major Voting,Staple,Collate算法。