1974年1月创刊(月刊)
主管/主办:重庆西南信息有限公司
ISSN 1002-137X
CN 50-1075/TP
CODEN JKIEBK
编辑中心
当期目录
2016年第9期, 刊出日期:2018-12-01
  
目次
基于镜面成像技术的三维立体视觉测量与重构综述
郭伟青,汤一平,鲁少辉,陈麒
计算机科学. 2016, 43 (9): 1-10.  doi:10.11896/j.issn.1002-137X.2016.09.001
摘要 ( 175 )   PDF(5839KB) ( 1336 )   
参考文献 | 相关文章 | 多维度评价
利用镜面成像技术获取被测物体或场景的三维信息得到研究者越来越多的关注。光线与平面镜或曲面镜交互时产生镜面成像。平面镜的反射属性可以改善视觉效果,基于光路射线展开过程可应用于不同的平面镜成像系统,采用光路展开替代镜面交互应用于三维场景,得到虚拟三维空间,平面镜成像使得复杂的射线交互可以用一种虚拟的方式可视化,且坐标系统的变化容易跟踪。曲面镜成像通常不具有透视投影属性,根据曲面的曲率来改变空间显示。曲面镜常常导致折反射,故针对不同的三维立体视觉测量及重构需设计相应的几何恢复算法。从计算机图形学和计算机视觉的角度,分析了镜面成像的基本原理,对近年来较典型的基于镜面成像技术的三维测量与重构方法及最新研究进展进行综述。
基于支持向量机的遥感图像分类研究综述
王振武,孙佳骏,于忠义,卜异亚
计算机科学. 2016, 43 (9): 11-17.  doi:10.11896/j.issn.1002-137X.2016.09.002
摘要 ( 194 )   PDF(740KB) ( 386 )   
参考文献 | 相关文章 | 多维度评价
遥感技术是目前用于研究地球矿产资源与能源的重要技术手段,遥感图像分类在遥感技术应用中起着关键作用。支持向量机(Support Vector Machines,SVM)是基于VC维(Vapnik-Chervonenkis Dimension)理论和结构风险最小化原理的机器学习方法,已被广泛应用于实际的遥感影像分类中。 对 国内外学者对此做的大量研究 成果进行了系统的总结。对基于支持向量机的遥感图像分类方法进行了层次性梳理,不但纵向分析和比较了每类方法的原理及优缺点,而且对各类方法进行了横向比较和分析,较为系统和完整地概括了基于支持向量机的遥感影像分类方法的研究现状。最后指出了支持向量机算法应用于遥感图像分类的未来发展方向。
带等时空载返程运输的双机Flow shop调度问题复杂性
兰艳,张明会,武宗涛,韩鑫
计算机科学. 2016, 43 (9): 18-22.  doi:10.11896/j.issn.1002-137X.2016.09.003
摘要 ( 111 )   PDF(1632KB) ( 246 )   
参考文献 | 相关文章 | 多维度评价
流水作业(Flow shop)问题是调度算法研究中经典问题模型之一,有两台处理机和一台运输机且运输机每次只运输一个工件的流水作业调度问题模型在现实中有着广泛的应用。同时考虑运输机去程(从机器M1到M2)与返程(从机器M2到M1)时间,在假定运输机去程运输时间及返程空载时间相等的情况下,通过把一个强NP-complete问题——3-PARTITION问题归约成一个研究问题的实例,来证明对这个问题求解是强NP-hard的。
3-Set Packing参数化计数问题的复杂性及近似算法
刘运龙
计算机科学. 2016, 43 (9): 23-26.  doi:10.11896/j.issn.1002-137X.2016.09.004
摘要 ( 91 )   PDF(315KB) ( 392 )   
参考文献 | 相关文章 | 多维度评价
Set Packing参数化计数问题即在一个3-Set Packing实例中统计所有大小为k的不同packing的个数。首先证明了该问题的计算复杂性是#W[1]-难的,表明该问题不大可能存在固定参数可解的精确算法(除非#W[1]=FPT)。然后,通过拓展3-D Matching参数化计数问题的算法对3-Set Packing参数化计数问题提出了一个基于Monte-Carlo自适应覆盖算法和着色技术的随机近似算法。
基于MapReduce的数据倾斜连接算法
梁俊杰,何利民
计算机科学. 2016, 43 (9): 27-31.  doi:10.11896/j.issn.1002-137X.2016.09.005
摘要 ( 102 )   PDF(1693KB) ( 402 )   
参考文献 | 相关文章 | 多维度评价
连接操作是大规模数据集在数据分析应用中最常用的操作,针对MapReduce自身不能有效地处理数据倾斜情况下的连接操作,提出了基于MapReduce的频次分类连接算法。根据数据在连接数据集中出现的频率将整个数据集分为3类,对倾斜数据利用分区算法和广播算法实现数据重分布,以消除数据倾斜的影响;对非倾斜数据采用Hash算法实现数据重分布。重分布后的数据在单节点内即可完成数据连接操作,避免了MapReduce框架下连接操作的跨节点传输代价;同时有效地均衡了MapReduce各节点的任务负载,从而提高了数据倾斜状态下连接操作的效率。通过与传统连接算法的对比,证明了所提算法的有效性和实用性。
2015 年第三届CCF 大数据学术会议
记忆计算:概念、特性及研究进展
郭斌,陈荟慧,李文鹏,於志文,姜佳君,王文辉
计算机科学. 2016, 43 (9): 32-38.  doi:10.11896/j.issn.1002-137X.2016.09.006
摘要 ( 111 )   PDF(603KB) ( 224 )   
参考文献 | 相关文章 | 多维度评价
随着信息技术的发展,尤其是移动互联网与物联网的发展,有关个人工作和生活的数据呈指数型增长。这些海量的数据中蕴含着丰富而有价值的个人信息,如何从这些数据中挖掘出有价值的信息成为当前信息领域的重要问题。针对该问题,介绍了普适计算领域新兴起的研究主题——记忆计算。记忆计算旨在通过各种带感知和计算功能的设备,比如智能手机、可穿戴设备等,实时感知和捕获用户线上线下活动的数据,分析并挖掘其内在价值,进而组织和管理有意义的记忆数据,实现基于情境的记忆数据呈现,以辅助个体记忆,支持社群交流与协作。讨论了基于移动情境感知的记忆计算的概念、特性、系统模型以及当前研究的关键技术与挑战,综述了记忆计算在生活日志、记忆提醒、往事回忆和群体记忆分享等方面的研究进展,并对其未来发展进行了展望。
FP-CNNH:一种基于深度卷积神经网络的快速图像哈希算法
刘冶,潘炎,夏榕楷,刘荻,印鉴
计算机科学. 2016, 43 (9): 39-46.  doi:10.11896/j.issn.1002-137X.2016.09.007
摘要 ( 246 )   PDF(1417KB) ( 925 )   
参考文献 | 相关文章 | 多维度评价
在大数据时代,图像检索技术在大规模数据上的应用是一个热门的研究领域。近年来,大规模图像检索系统中, 图像哈希算法 由于具备提高图像的检索效率同时减少储存空间的优点而受到广泛的关注。现有的有监督学习哈希算法存在一些问题,主流的有监督的哈希算法需要通过图像特征提取器获取人为构造的图像特征表示,这种做法带来的图像特征损失影响了哈希算法的效果,也不能较好地处理图像数据集中语义的相似性问题。随着深度学习在大规模数据上研究的兴起,一些相关研究尝试通过深度神经网络进行有监督的哈希函数学习,提升了哈希函数的效果,但这类方法需要针对数据集人为设计复杂的深度神经网络,增大了哈希函数设计的难度,而且深度神经网络的训练需要较多的数据和较长的时间,这些问题影响了基于深度学习的哈希算法在大规模数据集上的应用。针对这些问题,提出了一种基于深度卷积神经网络的快速图像哈希算法,该算法通过设计优化问题的求解方法以及使用预训练的大规模深度神经网络,提高了哈希算法的效果,同时明显地缩短了复杂神经网络的训练时间。根据在不同图像数据集上的实验结果分析可知, 与现有的基准算法相比,提出的算法在哈希函数训练效果和训练时间上都具有较大的提高。
基于随机谱梯度的在线学习
薛伟,张文生,任俊宏
计算机科学. 2016, 43 (9): 47-51.  doi:10.11896/j.issn.1002-137X.2016.09.008
摘要 ( 154 )   PDF(344KB) ( 350 )   
参考文献 | 相关文章 | 多维度评价
考虑一类学习问题,问题的目标函数可表示为大量组函数的平均,并且假设每一个组件函数都是光滑的。在众多机器学习方法中,在线学习操作流程简洁、收敛速度快,而且可以实现模型的自动更新,为大数据的学习提供了有利的工具。针对这类问题,提出了一种基于随机谱梯度下降(Stochastic Spectral Gradient Descent,S2GD)的在线学习方法。该方法利用Rayleigh商收集目标函数的二阶信息来构造Hessian阵逆的近似。S2GD方法可以看作是谱梯度方法从确定性优化到随机优化的延伸。算法每次迭代所产生的搜索方向具有下降性,且现有结论表明算法收敛。在LIBSVM数据库上的初步实验表明S2GD方法是可行的、有效的。
基于标签相似度计算的学术圈构建方法
傅城州,汤庸,贺超波,王津凌,袁成哲
计算机科学. 2016, 43 (9): 52-56.  doi:10.11896/j.issn.1002-137X.2016.09.009
摘要 ( 90 )   PDF(495KB) ( 219 )   
参考文献 | 相关文章 | 多维度评价
为面向学者的社交网络系统中的用户构建学术圈,对促进学者之间的交流具有重要的应用价值。根据学者之间的共同属性进行相似度计算,形成学术领域相似和研究课题相近的学术圈,能让学者们更加紧密和频繁地协同合作。提出了利用学者的学术信息提取代表个人特征的学术标签,并对不同类别标签的权重进行衡量,再通过相似度计算和聚类算法构建学术圈的方法。通过抓取学者社交网络平台SCHOLAT公开的学者信息进行实验,进而验证所提方法的可靠性和实用性。
基于主题模型的网络异常行为分类学习方法研究
马钲然,张博锋,王勇军
计算机科学. 2016, 43 (9): 57-60.  doi:10.11896/j.issn.1002-137X.2016.09.010
摘要 ( 127 )   PDF(382KB) ( 368 )   
参考文献 | 相关文章 | 多维度评价
提出了一种新的用于学习和分辨网络异常行为的方法。与之前的工作相比,将采用主题模型对网络异常行为进行建模并构建分类器。根据连接的分类标签,在训练模型之前将数据集分成两部分,即正常的部分和异常的部分。通过分析模型参数对结果的影响可以发现α(主题的狄利克雷参数)和主题数量对于预测结果具有正相关性,而β(特征号的狄利克雷参数)对于预测结果具有负相关性。通过KDDCUP’99数据集对该模型进行评估,结果显示预测的准确度达到91.69%,比SVM等算法在正常和异常行为分类上的表现更好。
一种基于局部拓展的并行重叠社区发现算法
张忠正,李建武
计算机科学. 2016, 43 (9): 61-65.  doi:10.11896/j.issn.1002-137X.2016.09.011
摘要 ( 116 )   PDF(393KB) ( 237 )   
参考文献 | 相关文章 | 多维度评价
处理海量级数据的有效途径之一是将算法分解为一系列互不依赖的任务,然后利用开源工具并行地执行算法。而在重叠社区发现算法中,基于局部拓展的方法在拓展阶段往往仅需要局部社区及其相应的邻居结点的信息,因而具备可并行执行的可能性。提出了一种可并行化执行的局部拓展算法,并借助开源工具Spark将其实现。算法分为4个阶段。首先,挑选出一组不相关的中心结点并使用其对应的局部网络作为种子;其次,通过删除本身连接不是很紧密的局部网络来过滤选出的种子;然后,采用一种批量式的拓展策略来拓展种子,即一次向局部社区中添加一批邻居结点或从社区中删除一批结点;最后,融合相似的社区。在人工生成的网络以及真实世界中的网络上的实验结果显示 ,所提算法既准确又高效。
基于MapReduce的新型微博用户影响力排名算法研究
徐文涛,刘锋,朱二周
计算机科学. 2016, 43 (9): 66-70.  doi:10.11896/j.issn.1002-137X.2016.09.012
摘要 ( 112 )   PDF(447KB) ( 240 )   
参考文献 | 相关文章 | 多维度评价
微博凭借其即时发布、实时传播、简便易用的特点逐渐成为最为主流的自媒体平台。用户影响力评价是微博社交网络中基本而又重要的问题,它对于优化与推动社会信息传播来说有着重要意义。以新浪微博为实验对象,通过综合考虑微博用户关系网络特性和用户行为,结合MapReduce编程计算模型,提出了一种基于MapReduce的新型用户影响力排名算法——QRank。在Hadoop平台上的实验结果表明,QRank算法具有良好的可扩展性,能够有效结合微博用户关系网络与行为特性,从而更加真实与充分地反映用户的实际影响力。
上下文分解机的自适应更新策略
姚杏,朱福喜,阳小兰,郑麟,刘世超
计算机科学. 2016, 43 (9): 71-76.  doi:10.11896/j.issn.1002-137X.2016.09.013
摘要 ( 100 )   PDF(489KB) ( 247 )   
参考文献 | 相关文章 | 多维度评价
分解机模型已经被成功应用于上下文推荐系统。在分解机模型的学习算法中,交替最小二乘法是一种固定其他参数只求单一参数最优值的学习算法,其参数数目影响计算复杂度。然而当特征数目很大时,参数数目随着特征数目急剧增加,导致计算复杂度很高;即使有些参数已经达到了最优值,每次迭代仍更新所有的参数。因此,主要改进了交替最小二乘法的参数更新策略,为参数引入自适应误差指标,通过权重和参数绝对误差共同决定该参数更新与否,使得每次迭代时重点更新最近两次迭代取值变化较大的参数。这种仅更新自适应误差大于阈值的参数的策略不但减少了需要更新的参数数目,进而加快了算法收敛的速度和缩短了运行时间,而且参数权重由误差决定,又修正了误差。在Yahoo和Movielens数据集上的实验结果证明:改进的参数更新策略运行效率有明显提高。
基于实体关系网络的微博文本摘要
薛竹君,杨树强,束阳雪
计算机科学. 2016, 43 (9): 77-81.  doi:10.11896/j.issn.1002-137X.2016.09.014
摘要 ( 131 )   PDF(1652KB) ( 444 )   
参考文献 | 相关文章 | 多维度评价
在解析 微博文本语法的基础上,结合实体关系的定义和形式化表示,提出了采用关系网络有向图模型的方法来反映文本之间的结构关系,较好地表达了文本的语义信息,弥补了词频特征刻画的不足之处。利用改进后的TPR(Topic-PAGERANK)测算各节点对应的度来表现关系元组的重要程度,按序输出关系元组对应的原博文语义字段作为摘要。最后,通过实验证明了基于关系网络的文本自动文摘方法抽取出的摘要涵盖信息更全面,冗余更少。
融入内部语义关系对文本分类的影响研究
朱建林,杨小平,彭鲸桥
计算机科学. 2016, 43 (9): 82-86.  doi:10.11896/j.issn.1002-137X.2016.09.015
摘要 ( 88 )   PDF(388KB) ( 277 )   
参考文献 | 相关文章 | 多维度评价
为了在不加入外部语义知识的前提下改善向量空间模型的文本分类效果,通过挖掘语料库内部蕴含的词间关系和文本间关系,并以不同的方式融入原始的词文本矩阵,然后选择常用的SVM和KNN算法,在领域性较强的法律语料库和领域性较宽泛的新闻语料库上进行文本分类的对比实验。实验证明,加入词间关系和文本间关系通常能有效改善文本分类的效果,但是对不同的分类方法和领域特征有不同的影响,在实际应用中应该区别对待。
AGM信念收缩算子的拓扑式刻画
孟华,原雅燕,储节磊,王红军
计算机科学. 2016, 43 (9): 87-90.  doi:10.11896/j.issn.1002-137X.2016.09.016
摘要 ( 105 )   PDF(321KB) ( 213 )   
参考文献 | 相关文章 | 多维度评价
当agent的信念集是无限集时,传统的基于有限逻辑语言的刻画信念变化(belief change)的简单语义模型通常不再适用。Grdenfors和Makinson 引入的epistemic entrenchment(认知牢固度)模型虽然可以用来从语义上刻画AGM型信念收缩算子,但他们并未给出如何构造一个具体的epistemic entrenchment 的方法。在无限命题逻辑语言的背景下,通过在模型集上引入一个拓扑结构,构造出一种新的用来刻画AGM信念收缩的语义结构,称为认知链,并给出相应表示定理。讨论了epistemic entrenchment与认知链之间的关系。相对epistemic entrenchment而言,认知链具有结构简单并易于构造的特点。
模式级链接关联数据集上的关联规则挖掘研究
袁柳,张龙波
计算机科学. 2016, 43 (9): 91-98.  doi:10.11896/j.issn.1002-137X.2016.09.017
摘要 ( 112 )   PDF(740KB) ( 233 )   
参考文献 | 相关文章 | 多维度评价
针对关联数据集合呈现出的大数据特性和蕴含的语义信息,提出了首先建立关联数据集的模式级链接,再进行关联规则挖掘的方法。在同领域RDF数据集上定义RDF数据项模式并提出数据项模式的产生规则;利用RDF数据查询技术从数据项模式获得RDF数据项集合,进而再推导出特定领域内的关联规则。提出的基于关联数据RDF数据项模式的关联规则挖掘方法将关联规则挖掘扩展到同一领域内的数据集合而不再局限于单一数据集,同时给出了基于Hadoop的大规模RDF数据集上的关联规则挖掘的实现方案。实验结果验证了模式级链接对于关联规则挖掘的价值和所提方法的有效性。
基于LT+模型的社交网络影响力最大化研究
蔡国永,裴广战
计算机科学. 2016, 43 (9): 99-102.  doi:10.11896/j.issn.1002-137X.2016.09.018
摘要 ( 96 )   PDF(290KB) ( 303 )   
参考文献 | 相关文章 | 多维度评价
影响力最大化问题的目标是寻找社交网络中一组种子结点集合,在给定的传播模型下,使得这些结点最终传播的影响范围最大。Kempe和Kleinberg提出的贪心算法可以获得很好的影响范围,但是因复杂度太高而并不适用于大型社交网络。Chen和Yuan等人基于线性阈值(LT)模型提出了构造局部有向无环图的启发式算法,但是LT模型只考虑了邻居结点的直接影响力,忽略了结点之间存在的间接影响力。因此,在LT模型的基础上,结合网络中结点之间存在的间接影响力,提出了LT+影响力模型,并利用构造局部有向无环图的启发式算法求解LT+模型的影响力最大化,称为LT+DAG算法。真实数据集上的对比实验表明,LT+DAG算法具有更好的影响范围以及较好的可扩展性。
半监督学习的老挝语词性标注方法研究
杨蓓,周兰江,余正涛,刘丽佳
计算机科学. 2016, 43 (9): 103-106.  doi:10.11896/j.issn.1002-137X.2016.09.019
摘要 ( 128 )   PDF(323KB) ( 243 )   
参考文献 | 相关文章 | 多维度评价
针对老挝语语料资源极少而无法直接利用有监督学习的方法实现老挝语词法分析的问题,提出了基于半监督学习的老挝语词性标注方法。首先利用仅有的少量标注词典和未标注语料资源,采用简单概率模型建模,获取较为完整的标注词典;其次利用整数规划获取大量自动标注的语料;最后在训练语 料充足的情况下,利用二阶隐马尔科夫模型建模,实现高质量的老挝语词性标注。提出的方法在老挝语词性标注方面取得了较好的效果,其准确率达到89.8%。
URTP:一种基于用户-区域-时间-商品的因子分解推荐模型
胡亚慧,杨莎,刘晶,余伟,李石君,王俊,方其庆
计算机科学. 2016, 43 (9): 107-110.  doi:10.11896/j.issn.1002-137X.2016.09.020
摘要 ( 105 )   PDF(419KB) ( 190 )   
参考文献 | 相关文章 | 多维度评价
如何从海量的数据中将不同的商品在恰当的时间、合理的位置推荐给适当的人(或人群)是当前面临的主要挑战。考虑到不同国家不同区域的人(或人群)在宗教信仰、职业、教育程度等方面有着不同的文化背景差异,以及大数据环境下商品推荐常常面临数据稀疏和冷启动等问题,从签到数据中抽取出目标用户所在的地理位置,根据该位置的文化背景特点筛选出与目标用户有相似或相同的文化背景的人群;再根据每个商品适宜购买的最佳合理时间和间隔购买时间选出恰当的商品,运用因子分解机的思想建立用户-区域-时间-商品因子分解模型。大量真实数据集上的实验表明该模型能够在数据量大、高稀疏的数据环境下进行商品推荐,验证了该方法的可行性、有效性和高效性。
一种结合用户评分信息的改进好友推荐算法
汤颖,钟南江,范菁
计算机科学. 2016, 43 (9): 111-115.  doi:10.11896/j.issn.1002-137X.2016.09.021
摘要 ( 87 )   PDF(431KB) ( 267 )   
参考文献 | 相关文章 | 多维度评价
传统的好友推荐算法在计算好友相似度时通常仅仅考虑用户在社交网络的拓扑结构的相似性,而对用户的兴趣相似性考虑较少,因此推荐的结果往往不够精准。现有的很多社交网站(如豆瓣网)提供了用户评分功能,用户可以对某类物品(如电影)给出自己的评分。为了在推荐时计算用户的兴趣相似度,提出基于用户给出的对某类物品的评分来计算用户的兴趣相似度,从而在拓扑相似度的基础上结合兴趣相似度得到更精准的推荐结果。首先使用余弦相似度计算出用户间拓扑相似度;其次在计算基于评分的用户兴趣相似度时,通过建立概率模型得到用户聚类评分相似度矩阵,从该评分矩阵推导出用户间基于评分的兴趣相似度;最后,结合拓扑相似度和评分相似度得到最终的改进好友推荐算法,计算出相似度值最高的N个人推荐给当前用户。为了验证所提方法的有效性,用提出的方法对豆瓣网抓取的用户数据进行好友推荐,实验结果证明所提方法与传统的基于拓扑的好友推荐算法相比可以有效提高好友推荐的准确性。
SparkDE:一种基于RDD云计算模型的并行差分进化算法
谭旭杰,邓长寿,董小刚,袁斯昊,吴志健,彭虎
计算机科学. 2016, 43 (9): 116-119.  doi:10.11896/j.issn.1002-137X.2016.09.022
摘要 ( 143 )   PDF(392KB) ( 316 )   
参考文献 | 相关文章 | 多维度评价
云计算MapReduce并行编程模型广泛应用于数据密集型应用领域,基于该模型的开源平台Hadoop在大数据领域获得了成功应用。然而,对于计算密集型任务,特别是迭代运算,频繁启动Map和Reduce过程将导致负载过大,影响计算效率。弹性分布式数据集(RDD)是一种基于内存的集群计算模型,有效地支持迭代运算,能够克服负载过大的问题。因此提出基于RDD模型的并行差分进化算法SparkDE。SparkDE首先将整个种群划分为若干个独立岛,然后将一个岛对应RDD中的一个分区,每个岛在RDD的一个分区中独立进化指定代数后,利用迁移算子在岛之间交换信息。利用标准测试问题对SparkDE、基于MapReduce模型的MRDE和基本DE进行对比实验研究。实验结果表明SparkDE求解精度高,计算速度快,加速效果明显,可以作为云计算平台的下一代优化器。
面向临床检验指标的非同步时间序列聚类算法研究
陈德华,韩学士,乐嘉锦,朱立峰
计算机科学. 2016, 43 (9): 120-123.  doi:10.11896/j.issn.1002-137X.2016.09.023
摘要 ( 114 )   PDF(411KB) ( 322 )   
参考文献 | 相关文章 | 多维度评价
对临床检验指标时间序列进行聚类,从中发现临床检验指标变化趋势相似的患者群体,对开展精准医疗具有非常重要的价值。考虑到不同患者的检验次数及检验时间点不完全同步,首先通过对非同步时间序列进行预处理,实现不同时间序列维度及时间点的同步化。在此基础上,通过引入一个用户自定义参数即噪声点占有率NoisePro,对DBScan算法进行改进,提出了一种基于密度划分思想的非同步临床检验指标时间序列聚类LabTS-CLU算法。最后利用某三甲医院十余万糖尿病患者近10年的糖化血红蛋白时间序列数据集进行实验,结果证明了所提算法的有效性。
网络与通信
基于UPPAAL的WSNs数据收集协议的建模与分析
冯亚超,杨红丽,王非,武文佳,秦胜潮
计算机科学. 2016, 43 (9): 124-130.  doi:10.11896/j.issn.1002-137X.2016.09.024
摘要 ( 75 )   PDF(2582KB) ( 282 )   
参考文献 | 相关文章 | 多维度评价
无线传感器网络(Wireless Sensor Networks,WSNs)广泛应用于各类数据收集系统,如居民区无线抄表(包括水表、电表和燃气表)系统。数据收集协议设计的正确性与合理性是影响网络正常运作的关键因素。针对数据收集协议的实时性需求,提出了基于UPPAAL实时模型检查器的WSNs数据收集协议的建模与分析方法。由于UPPAAL的输入模型相对于一般时间自动机模型而言较为复杂,因此首先对所选数据收集协议的通信行为建立一般时间自动机模型,之后再将其进一步转换为UPPAAL的输入模型。为了阐明该方法的有效性,选择了一个实际的无线抄表数据收集协议WM2RP作为例子进行建模,并利用UPPAAL分析其性质。分析结果显示,该协议能够满足一些与安全性及可靠性相关的性质。为了从多角度对协议进行分析,进一步建立了WM2RP协议的异常模型和能耗模型。
基于伸展树的文件数据缓存管理策略研究
姚智海,徐宏喆,李文,吴夏
计算机科学. 2016, 43 (9): 131-134.  doi:10.11896/j.issn.1002-137X.2016.09.025
摘要 ( 107 )   PDF(345KB) ( 210 )   
参考文献 | 相关文章 | 多维度评价
针对企业内部网络存储,研究并提出了一种基于伸展树的缓存管理策略,以对网络缓存空间进行组织和管理。在内部网络存储缓存链的基础上,引入并改进了伸展树结构和操作,将改进后的伸展树作为缓存节点数据组织和管理的索引结构,分析并设计了基于伸展树的文件数据缓存管理策略。实验结果表明,基于伸展树算法的缓存管理策略提高了缓存空间利用率和用户访问数据的效率,有较好的实时性。
Internet建模的关键:研究AS间路由器级连接
李鹤帅,朱俊虎,王清贤,邱菡,周天阳
计算机科学. 2016, 43 (9): 135-139.  doi:10.11896/j.issn.1002-137X.2016.09.026
摘要 ( 103 )   PDF(408KB) ( 398 )   
参考文献 | 相关文章 | 多维度评价
AS-域内路由器双层建模方式是目前构建Internet规模的路由器级网络模型的最优方案,而该方案需要建模者首先了解域间路由器级连接的特点。指出AS类型对域间路由器级连接具有较大影响,通过定义域间参数映射,利用现网数据对域间参数映射进行了现象学分析,获取了不同类型AS相关参数的分布函数,解决了双层模型的组合问题。在此基础上,进一步对Internet建模尚需解决的若干问题进行了讨论。
基于多级反馈式喷泉码的深空传输协议研究
陈康妮,钱丽萍,陈庆章
计算机科学. 2016, 43 (9): 140-145.  doi:10.11896/j.issn.1002-137X.2016.09.027
摘要 ( 78 )   PDF(527KB) ( 288 )   
参考文献 | 相关文章 | 多维度评价
针对深空环境中高误码率、长传输时延的通信特点,在传统喷泉码的基础上提出了一种基于多级反馈式喷泉码的深空通信传输协议。给出了基于多级反馈式喷泉码传输协议具体的编码结构和传输方案,从理论上分析了该传输协议与非反馈喷泉码传输协议的编码有效性和传输时间,并通过实验比较了上述两种传输协议以及基于喷泉码的译码转发传输协议在不同误码率和传输距离的深空通信环境下的传输性能。实验结果表明,基于多级反馈式喷泉码的传输协议提高了编码有效性,减少了文件传输时延。
基于演化博弈论的p-坚持CSMA网络接入控制研究
王乐,毛剑琳,诸浩富,郭宁
计算机科学. 2016, 43 (9): 146-151.  doi:10.11896/j.issn.1002-137X.2016.09.028
摘要 ( 95 )   PDF(531KB) ( 259 )   
参考文献 | 相关文章 | 多维度评价
考虑到存在无线信道差错,针对p-坚持CSMA网络的非合作系统行为,建立了p-坚持CSMA演化博弈模型,推导了唯一的演化稳定策略,以饱和吞吐量最大、平均能耗最小为目标求解了最优演化稳定策略。然后,进一步研究了收益时延、成功收益以及比特差错概率对最优演化稳定过程的影响。数值仿真结果表明,当比特差错概率一定、收益时延较小时,选择合适的成本和收益,使多路访问博弈在最优传输概率处演化稳定,可获得一个稳定且性能最优的p-坚持CSMA网络。
一种基于部分网络编码的无线网络机会路由算法
王振朝,蔡志杰,薛文玲
计算机科学. 2016, 43 (9): 152-155.  doi:10.11896/j.issn.1002-137X.2016.09.029
摘要 ( 119 )   PDF(416KB) ( 249 )   
参考文献 | 相关文章 | 多维度评价
结合机会路由和网络编码两项新技术各自的优势,提出了一种新的基于部分网络编码的机会路由算法(Opportunistic Routing Algorithm for Wireless Network Based on Partial Network Coding,ORAPNC)。为了避免数据包分叉传输,同时利于执行转发节点间协调机制,ORAPNC首先以期望传输次数作为路由度量建立一条固定路由,并将候选转发节点集中在这条固定路径附近;为了充分减小网络中的冗余数据包,ORAPNC采用一种新的转发节点间协调机制(Forwarding Nodes Coordination Mechanism,FNCM)来实现每跳的数据包传输。仿真结果表明,与其他相关路由协议相比较,ORAPNC可以有效提高网络吞吐量,减小目的节点解出原始数据包的平均时延。
网络编码感知的无线机会路由性能分析模型
陶雯,金玲,白光伟,沈航
计算机科学. 2016, 43 (9): 156-159.  doi:10.11896/j.issn.1002-137X.2016.09.030
摘要 ( 97 )   PDF(316KB) ( 179 )   
参考文献 | 相关文章 | 多维度评价
结合基于优先级的ACK回复策略,提出网络编码感知的无线机会路由性能分析模型。该模型探讨多个中继节点时无线信道丢包对网络性能的影响。为此,建立二维马尔科夫链模型对802.11 DCF信道接入机制进行数学建模分析,从而得到数据包成功投递概率和网络吞吐量公式。数学分析结果表明:结合机会路由和网络编码,通过增加中继节点数量,可以提高数据包的投递概率和网络吞吐量。
生产设备合作关系网络的建模与分析
李文翔,危霞,江昊,盛玉霞
计算机科学. 2016, 43 (9): 160-164.  doi:10.11896/j.issn.1002-137X.2016.09.031
摘要 ( 80 )   PDF(1051KB) ( 199 )   
参考文献 | 相关文章 | 多维度评价
区域产业集群中的生产资源能形成多样复杂的合作关系。探讨如何挖掘和利用这些关系来规划和控制集群内部元素的合作,以提供高效的云制造生产服务。采用广义社会合作网络模型描述集群中的制造合作关系,提出构建设备合作网络(FCN)的方法;面向不同的设备选择策略(随机、均衡、带偏好随机及带偏好均衡)设计FCN动态增长过程;基于网络规模、节点度分布、项目度分布和平均最短距离等指标对一个FCN实例的统计特性展开分析,指出均衡策略具有比随机策略更大的网络规模,而随机策略具有较明显的无标度和小世界特性;进而提出基于设备动态加权和子任务集中处理的设备选择优化策略。
信息安全
基于CP-ABE的多云存储系统中访问控制模型的研究
印凯泽,汪海航
计算机科学. 2016, 43 (9): 165-168.  doi:10.11896/j.issn.1002-137X.2016.09.032
摘要 ( 102 )   PDF(1720KB) ( 236 )   
参考文献 | 相关文章 | 多维度评价
针对将单个云内基于密文策略属性基加密(CP-ABE)的访问控制机制应用到多云存储系统中时遇到的策略冲突问题,设计了一个属性映射机制,通过扩展CP-ABE机制,提出了一个适用于多云存储系统的访问控制模型。这里的映射机制主要针对CP-ABE的树形访问结构以及其支持的属性值类型。最后,详细描述了该模型的框架及工作流程,通过构建一个简单的原型系统验证了该模型的有效性,同时对该原型系统进行了性能分析。该模型的提出对于多云存储系统的访问控制研究具有理论价值和实际意义。
基于云模型的军事航空通信频谱共享信任机制研究
徐雪飞,李建华,杨迎辉,郭蓉
计算机科学. 2016, 43 (9): 169-174.  doi:10.11896/j.issn.1002-137X.2016.09.033
摘要 ( 108 )   PDF(487KB) ( 265 )   
参考文献 | 相关文章 | 多维度评价
针对军事航空通信频谱共享的特殊性,提出一种基于云模型的频谱共享信任机制。通过对信任的相关理论进行研究,引入云模型理论,构建了基于云模型的频谱共享信任体系结构,确立了频谱共享信任体系中的信任交互关系。运用云模型进行信任评价,实现了将频谱共享中模糊定性的信任属性向精确定量的信任等级的转换,较好地解决了频谱共享信任关系建立等系列问题。设计了信任评价实验,验证了信任评价模型的有效性和实用性,为基于信任机制的频谱共享策略实施提供了有效的支撑。
基于协同地址碰撞的隐蔽认证方法
曹旭,祝跃飞,费金龙
计算机科学. 2016, 43 (9): 175-179.  doi:10.11896/j.issn.1002-137X.2016.09.034
摘要 ( 94 )   PDF(428KB) ( 237 )   
参考文献 | 相关文章 | 多维度评价
云计算的兴起不可避免地带来了一些安全问题,服务资源的非授权访问就是其中的一个重要威胁。对此,基于IPv6地址的新特性,提出一种协同地址碰撞技术,即待认证节点通过多个协同节点的配合,向关键主机所在网络发送在IP地址接口标识部分隐含认证秘密的数据包,以实现对节点的隐蔽认证。理论和实验分析结果表明,该方案可有效提高网络的安全性。
一种高效多授权中心云访问控制方案
周鹏旭,李成海
计算机科学. 2016, 43 (9): 180-183.  doi:10.11896/j.issn.1002-137X.2016.09.035
摘要 ( 82 )   PDF(398KB) ( 217 )   
参考文献 | 相关文章 | 多维度评价
针对已有云计算多授权访问控制方案中用户端负担过重的问题,提出一种基于属性加密的多授权中心访问控制方案HE-MA-ACS。在层次化授权结构的基础上,引入外包解密思想,将用户访问的大部分解密计算开销外包至云服务端,实现细粒度的属性撤销,并且用户端不需要参与属性的撤销操作。对方案的正确性、安全性、计算和存储性能进行了分析,证明了该方案在用户端存储开销、访问通信开销、解密时间及属性撤销时计算开销上的优越性。该方案有效地降低了用户端的负担,提高了解密效率。
云计算环境下隐私数据的隐式攻击保护
陶林波,沈建京,薛猛,蔡立刚
计算机科学. 2016, 43 (9): 184-187.  doi:10.11896/j.issn.1002-137X.2016.09.036
摘要 ( 78 )   PDF(1159KB) ( 210 )   
参考文献 | 相关文章 | 多维度评价
云计算环境下用户的隐私数据保护成为了云计算能否快速发展的关键,目前更多的研究集中在了隐私数据的加密等显式保护方法上,而对集中存储带来的统计分析以及数据挖掘等隐式攻击带来的隐私泄露关注不够。针对云计算环境下用户隐私数据面临的数据挖掘带来的隐私泄露风险,建立了一种保护模型。其将数据在云端的录入、存储、还原、销毁几个生命周期的关键环节作为保护目标,建立相应的保护模块,对隐私数据进行相应的处理。最后通过复杂度对比的方法证明了本文模型的有效性。
EFI OS Loader安全加固技术的研究与实现
吴伟民,陈东新,赖文鑫,苏庆
计算机科学. 2016, 43 (9): 188-191.  doi:10.11896/j.issn.1002-137X.2016.09.037
摘要 ( 118 )   PDF(1908KB) ( 571 )   
参考文献 | 相关文章 | 多维度评价
对统一可扩展固件接口(UEFI)的体系架构和执行流程进行安全性分析,发现Windows启动过程中EFI OS Loader的可信性校验存在安全漏洞,其可导致Windows启动流程被劫持。针对该安全漏洞,从文件分离保护、开机身份认证和系统关键区域防护3个层次出发,提出了一种基于USB Key启动、动态口令手机令牌和EFI安全防护软件的三层安全加固的方案。将EFI OS Loader文件存放在USB Key中并加密,实现对文件的保护;把动态口令认证服务端置于USB Key中,两者的有机结合实现了高强度的开机身份认证;设计并开发了遵循UEFI规范的EFI应用程序型安全防护软件,实现了对系统关键区域的保护。实验结果表明,该方案的双认证与安全防护机制弥补了相关安全漏洞,增强了计算机系统启动过程的安全性。
基于静态污点分析的Android应用Intent注入漏洞检测方法
王允超,魏强,武泽慧
计算机科学. 2016, 43 (9): 192-196.  doi:10.11896/j.issn.1002-137X.2016.09.038
摘要 ( 218 )   PDF(435KB) ( 745 )   
参考文献 | 相关文章 | 多维度评价
针对Android应用程序组件间通信过程中的消息载体Intent有可能被攻击者构造进而引发组件被恶意注入的安全风险问题,提出了一种基于静态污点分析的检测方法。在构建Android应用的函数调用图和控制流图的基础上,通过跟踪应用组件内和组件间不可信Intent消息的污点传播过程,检测应用中潜在的Intent注入漏洞。用该方法对4类标准测试应用和50款第三方应用进行测试,实验结果表明了该方法的可行性和有效性。
软件与数据库技术
RDF数据分布式并行语义编码算法
郑翠春,汪璟玢
计算机科学. 2016, 43 (9): 197-202.  doi:10.11896/j.issn.1002-137X.2016.09.039
摘要 ( 100 )   PDF(556KB) ( 273 )   
参考文献 | 相关文章 | 多维度评价
现有的RDF数据分布式并行压缩编码算法均未考虑结合本体文件,导致编码后的RDF数据没有表示任何语义信息,不利于分布式查询或推理。针对这些问题,提出SCOM(Semantic Coding with Ontology on MapReduce)算法在分布式MapReduce下完成RDF数据的语义并行编码。该算法首先结合RDF数据本体,构建类关系和属性关系模型;在三元组项分类与过滤之后,对三元组项进行编码并生成字典表,最终完成RDF数据带有语义信息且具有规律性的编码。此外,SCOM算法能够很容易地将编码后的RDF数据文件恢复为原始文件。实验表明,SCOM算法能够高效地实现大规模数据的分布式并行编码。
与副本结合的部分再生码
丁炳辰,李卫忠
计算机科学. 2016, 43 (9): 203-208.  doi:10.11896/j.issn.1002-137X.2016.09.040
摘要 ( 94 )   PDF(441KB) ( 213 )   
参考文献 | 相关文章 | 多维度评价
n,k,d)再生码允许存储节点传送所存数据的线性组合以及增加修复入度d,显著地降低了修复带宽,但是引入了更多的参与节点数及磁盘I/O。针对这一不足,提出了一种将复制方式与再生码结合的(n,k,d,λ,θ)部分再生码,并得到了与再生码类似的阈值函数和2个特殊点——最小存储量点和最小修复带宽点。部分再生码可以综合利用修复入度d和副本因子θ同时降低修复带宽和磁盘I/O。当所有的节点存储量相等时,部分再生码的单点修复带宽和磁盘I/O均优于再生码。定量比较的结果也显示,在最小存储量点,部分再生码比再生码有更低的平均修复带宽和平均磁盘I/O;在最小修复带宽点,部分再生码有更低的平均磁盘I/O以及与再生码相近的平均修复带宽。更重要的是,部分再生码适用于d≤n-2的所有情形。
人工智能
一种基于抽样的大规模混合数据聚类集成算法
庞天杰,梁吉业
计算机科学. 2016, 43 (9): 209-212.  doi:10.11896/j.issn.1002-137X.2016.09.041
摘要 ( 130 )   PDF(309KB) ( 217 )   
参考文献 | 相关文章 | 多维度评价
混合数据聚类是聚类分析中一个重要的问题。现有的混合数据聚类算法主要是在全体样本的相似性度量的基础上进行聚类,因此对大规模数据进行聚类时,算法效率不高。基于此,设计了一种新的抽样策略,在此基础上,提出了一种基于抽样的大规模混合数据聚类集成算法。该算法对利用新的抽样策略得到的多个样本子集分别进行聚类,并将结果集成得到最终聚类结果。实验证明,与改进的K-prototypes算法相比,该算法的效率有了显著提高,同时聚类有效性指标基本相同。
科研社交网络中基于联合概率矩阵分解的科技论文推荐方法研究
吴燎原,蒋军,王刚
计算机科学. 2016, 43 (9): 213-217.  doi:10.11896/j.issn.1002-137X.2016.09.042
摘要 ( 128 )   PDF(416KB) ( 233 )   
参考文献 | 相关文章 | 多维度评价
近年来随着科研社交网络中科技论文数量爆炸式的增长,科研人员很难高效地找到与之相关的科技论文,因此面向科研工作者的科技论文推荐方法应运而生。然而,传统的科技论文推荐方法没有充分挖掘科研社交网络中广泛存在的社会化信息,导致科技论文推荐质量不高。为此,提出了一种科研社交网络中基于联合概率矩阵分解的科技论文推荐方法,在传统概率矩阵分解的基础上,融入了社会化标签信息和社会化群组信息来进行科技论文推荐。为了验证所提方法的有效性,抓取了科研社交网络CiteULike上的数据进行了实验。实验结果表明,与其它传统推荐方法相比较,所提方法在Precision和Recall两个评价指标上均取得了较好的推荐结果,并且能够应用于大规模数据集,具有良好的可扩展性。
一种改进的粒子滤波算法及其在GPS/DR组合定位中的应用
杜航原,王文剑,白亮
计算机科学. 2016, 43 (9): 218-222.  doi:10.11896/j.issn.1002-137X.2016.09.043
摘要 ( 116 )   PDF(412KB) ( 337 )   
参考文献 | 相关文章 | 多维度评价
针对粒子滤波的重要性密度函数选择问题,提出一种基于集合卡尔曼滤波(Ensemble Kalman Filter,EnKF)的改进粒子滤波算法。该方法利用集合卡尔曼滤波产生粒子滤波在每一时刻各粒子的重要性密度函数,在融合最新观测信息的同时,使重要性密度函数更加符合状态的真实后验概率分布。为消除样本枯竭现象,对重采样后的粒子进行马尔科夫链蒙特卡洛处理。在仿真实验中,将新算法用于GPS/DR组合定位系统,与粒子滤波、扩展卡尔曼粒子滤波以及无迹粒子滤波进行比较。仿真结果表明,该算法的估计精度高于传统粒子滤波算法,同时其能够有效控制计算量,并且在粒子数目较少时仍能保证较好的估计性能。
基于多分类器协同学习的卷积神经网络训练算法
陈文,张恩阳,赵勇
计算机科学. 2016, 43 (9): 223-226.  doi:10.11896/j.issn.1002-137X.2016.09.044
摘要 ( 90 )   PDF(1014KB) ( 338 )   
参考文献 | 相关文章 | 多维度评价
卷积神经网络(CNN)是一类重要的深度神经网络,然而其训练过程需要大量的已标记样本,从而限制了其实际应用。针对这一问题,分析了CNN分类器的协同学习过程,给出了基于迭代进化的分类器协同训练算法CAMC。该算法结合了CNN和多分类器协同训练的优势,首先采用不同的卷积核提取出多种样本特征以产生不同的CNN分类器;然后利用少量的已标记样本和大量的未标记样本对多个分类器进行协同训练,以持续提高分类性能。在人脸表情标准数据集上的实验结果表明,相对于传统的表情特征识别法LBP和Gabor,CAMC能够在分类过程中利用未标记样本持续实现性能提升,从而具有更高的分类准确率。
一种融合多种用户行为的协同过滤推荐算法
高山,刘炜,崔勇,张茜,王宗敏
计算机科学. 2016, 43 (9): 227-231.  doi:10.11896/j.issn.1002-137X.2016.09.045
摘要 ( 102 )   PDF(414KB) ( 200 )   
参考文献 | 相关文章 | 多维度评价
协同过滤作为目前应用最成功的个性化推荐技术,在电子商务、社交网络等领域得到了广泛应用。然而,当此类算法应用到个性化医疗推荐领域时,由于个人医疗行为本身的复杂性和多样性,出现了推荐准确率下降的问题。针对这一问题,提出一种融合多种用户行为的协同过滤推荐算法,使用权重因子来综合衡量不同用户行为对推荐质量的影响,并引入重合依赖度的概念来修正传统的相似度度量方法。在收集的Top-md数据集上的实验结果表明,该算法能够全方位表达用户的就医偏好和意愿,有效提高个性化医疗推荐系统的推荐质量。
扩展优势关系下的变精度粗糙集模型
李艳,靳永飞,马红艳
计算机科学. 2016, 43 (9): 232-237.  doi:10.11896/j.issn.1002-137X.2016.09.046
摘要 ( 121 )   PDF(453KB) ( 186 )   
参考文献 | 相关文章 | 多维度评价
基于优势关系的变精度粗糙集模型将传统粗糙集中的等价关系扩展为优势关系,并结合变精度的思想来定义相关概念,从而可以处理具有偏好关系的信息并具有一定的容错能力。然而,传统优势关系的定义仍然过于严格,只有当一个对象x的每个属性值都优于另一个对象y时,该对象x才优于y。当属性个数较多时,这种优势关系的定义会导致对象的优势集偏小,影响到规则的提取和决策结果。为了解决这一问题,通过引入参数的方法扩展了传统优势关系的定义,并在此基础上进一步给出了扩展后的优势集和近似集的概念,建立了扩展优势关系下的变精度粗糙集模型,采用覆盖率和测试精度作为模型的评估指标。最后给出算例,并在UCI数据集上进行大量的实验将所提模型与传统优势关系下的变精度粗糙集模型进行比较。
基于均匀分布的高斯云模型
陈昊,李兵
计算机科学. 2016, 43 (9): 238-241.  doi:10.11896/j.issn.1002-137X.2016.09.047
摘要 ( 141 )   PDF(421KB) ( 355 )   
参考文献 | 相关文章 | 多维度评价
云模型实现了定性概念与其定量表示之间的不确定转换。高斯分布与高斯隶属度函数的普适性奠定了高斯云模型的普适性,目前云模型的理论与应用研究主要集中在高斯云模型。将均匀分布引入到云模型中,扩展了高斯云模型,分别得到了均匀分布云模型和均匀高斯云模型,两类扩展的云模型为不确定性的形式化描述提供了新的途径。最后利用多维均匀高斯云模型模拟分形树生长过程,实验结果表明云模型能有效模拟自然界中不确定的分形现象。
基于粒计算与信息融合的P2P网贷用户信用评估
赵颖秀,刘文奇,李金海,赵宁
计算机科学. 2016, 43 (9): 242-246.  doi:10.11896/j.issn.1002-137X.2016.09.048
摘要 ( 109 )   PDF(411KB) ( 215 )   
参考文献 | 相关文章 | 多维度评价
P2P网贷在爆发式增长的同时,也面临着巨大的信用风险。针对这一问题,首先提出了综合评判法这种信用评估方法,并且运用融360的数据对其进行了验证。其次,提出了利用粒计算的信息融合方法将第三方数据与已有信用评估值进行信息融合,进而不仅对原有信用评估值信息进行了补充,而且使彼此得到相互印证。最后通过模拟第三方数据对运用粒计算的信息融合方法进行了验证。
融合位置相关和概率排序的Lucene排序算法改进
胡博,蒋宗礼
计算机科学. 2016, 43 (9): 247-249.  doi:10.11896/j.issn.1002-137X.2016.09.049
摘要 ( 82 )   PDF(336KB) ( 284 )   
参考文献 | 相关文章 | 多维度评价
文档检索结果的排序和文本分类技术是解决垂直搜索、个性化信息检索、信息过滤等相关问题的核心技术。为了提高检索系统的性能,针对Lucene的基础排序算法,提出了一种融合位置相关和概率排序的改进方法。考虑到查询词在文档中出现的位置信息和概率排序对文档相关性的影响,利用位置相关的查询词权值和基于朴素贝叶斯分类算法的文档相关性概率值,对Lucene基础排序算法的评分公式进行改进。实验表明,该改进方法能够有效提高垂直搜索的准确率,使用户拥有更好的垂直搜索体验。
求解非线性规划问题的改进直觉模糊遗传算法
梅海涛,华继学,王毅
计算机科学. 2016, 43 (9): 250-254.  doi:10.11896/j.issn.1002-137X.2016.09.050
摘要 ( 96 )   PDF(363KB) ( 288 )   
参考文献 | 相关文章 | 多维度评价
提出一种改进的直觉模糊遗传算法用于求解带有多维约束的非线性规划问题。以遗传算法在迭代寻优中的个体适应度大小构造相应可行解的隶属度和非隶属度函数,将非线性规划问题直觉模糊化转化为直觉模糊非线性规划问题,通过建立直觉模糊推理系统,自适应地调节遗传算法的交叉率和变异率;并采用一种改进的选择策略,将个体按适应度值大小排序、等量分组,对适应度低的个体组随机选择复制,保留不可行解中可能隐含的有利寻优信息,增强种群个体的多样性和竞争性。仿真实验结果表明,该算法求解非线性规划问题时是可行和有效的。
基于联合概率矩阵分解的移动社会化推荐
熊丽荣,刘坚,汤颖
计算机科学. 2016, 43 (9): 255-260.  doi:10.11896/j.issn.1002-137X.2016.09.051
摘要 ( 87 )   PDF(583KB) ( 227 )   
参考文献 | 相关文章 | 多维度评价
利用移动设备上下文、移动社会化网络等信息进一步提高推荐系统的预测准确率,并缓解可能存在的数据稀疏性和冷启动问题,已经成为移动推荐系统的主要任务。采用基于矩阵分解的因子分析方法,结合用户、服务和用户社会化网络信息进行服务推荐,可以缓解数据稀疏性和冷启动问题;同时,为了增加信任矩阵密度,引入间接信任关系,提出了一种符合移动社会化网络特点的信任度计算方法,该方法仅利用移动社会化网络结构信息构建信任矩阵,从而减少用户对信任关系的主动标识。实验结果表明,引入间接信任关系能够提高预测精度,同时 比传统的协同过滤算法和已有的一些矩阵分解方法具有更好的预测准确率,特别是在评分数据稀疏的情况下。
基于Lex-PageRank的微博摘要优化方法
朱明峰,叶施仁,叶仁明
计算机科学. 2016, 43 (9): 261-265.  doi:10.11896/j.issn.1002-137X.2016.09.052
摘要 ( 81 )   PDF(430KB) ( 221 )   
参考文献 | 相关文章 | 多维度评价
当前,由于全民自媒体兴起而引发了巨大的舆情危机,如何高效快速地从海量的碎片化信息中发现热点并抽取实用信息成为一项重大的挑战。在此背景下,提出一种基于Lex-PageRank的微博摘要优化方法,在该方案中,以聚类结果作为实验数据,从微博影响力周期的时间特性和权重属性考虑,提出改进的Lex-PageRank算法,从聚类结果中抽取若干文本组织生成摘要。在新浪微博数据基础上进行的对比实验表明,本方案可以有效地从大量文本中提取出关键信息。
一种基于贝叶斯网络的个性化协同过滤推荐方法研究
付永平,邱玉辉
计算机科学. 2016, 43 (9): 266-268.  doi:10.11896/j.issn.1002-137X.2016.09.053
摘要 ( 114 )   PDF(255KB) ( 266 )   
参考文献 | 相关文章 | 多维度评价
针对推荐系统不能有效进行个性化推荐问题,在协同过滤过程中引入语义校验,通过对基于用户的协同过滤推荐结果进行语义校验,剔除概率较低的推荐结果,选择概率较高的结果推荐给用户,从而实现个性化语义推荐。在构建贝叶斯语义校验网络时,增加用户“喜好”偏好字段,通过问卷调查及信息反馈,确定用户对物品的喜好偏好值,确保贝叶斯语义校验网络的科学性。实验结果表明,本方法能剔除用户喜好度较低的物品,提高用户的满意度。
基于差分进化的因子分解机算法
喻飞,赵志勇,魏波
计算机科学. 2016, 43 (9): 269-273.  doi:10.11896/j.issn.1002-137X.2016.09.054
摘要 ( 90 )   PDF(399KB) ( 294 )   
参考文献 | 相关文章 | 多维度评价
因子分解机(Factorization Machine,FM) 算法是一种基于矩阵分解的机器学习算法,可用于求解回归、分类和排序等问题。FM模型中的参数求解使用的是基于梯度的优化方法,然而在样本较少的情况下,该优化方法收敛速度慢,且易陷入局部最优。差分进化算法(Differential Evolution,DE)是一种启发式的全局优化算法,具有收敛速度快等特性。为提高FM模型的训练速度,利用DE计算FM模型参数,提出了DE-FM算法。在数据集Diabetes、HorseColic以及音乐分类数据集Music上的实验结果表明,改进后的基于差分进化的因子分解机算法DE-FM在训练速度和准确性上均有所提高。
图形图像与模式识别
基于时空域信息融合的视频拷贝检测算法研究
严聪,纪墨轩,纪庆革
计算机科学. 2016, 43 (9): 274-279.  doi:10.11896/j.issn.1002-137X.2016.09.055
摘要 ( 80 )   PDF(1305KB) ( 284 )   
参考文献 | 相关文章 | 多维度评价
为了有效利用视频独有的时空域特性来提高视频拷贝检测算法的鲁棒性和精度,提出一种基于时空域信息融合的快速拷贝检测算法。该算法包括基于时空域信息融合的指纹提取算法、基于倒排索引的匹配搜索算法和结合异步滑窗策略的基于匹配状态机的匹配搜索算法。指纹提取算法首先将视频分段形成时空域信息帧,然后对该信息帧进行分块,提取DCT系数后,利用其中值进行阈值化得到视频指纹。基于倒排索引的搜索算法根据指纹的二值性特点建立倒排索引表,然后通过索引表快速查询指纹。结合异步滑窗策略的基于匹配状态自动机的搜索算法,利用与最近邻之间的匹配状态来改变搜索范围和步长,而异步滑窗策略通过对在线和离线过程采用不同的提取策略,减少搜索量,加快搜索速度。实验结果表明,提取的指纹对噪声模糊、添加字幕、空间偏移、旋转、掉帧具有较好的鲁棒性,同时提出的搜索方案在时间效率上也有较大的提升。
基于低秩张量恢复的视频块效应处理
陈代斌,杨晓梅
计算机科学. 2016, 43 (9): 280-283.  doi:10.11896/j.issn.1002-137X.2016.09.056
摘要 ( 93 )   PDF(1528KB) ( 292 )   
参考文献 | 相关文章 | 多维度评价
针对块编码的视频解码后存在块效应的问题,提出了一种基于块和低秩张量恢复的块效应处理方法。首先在视频序列里寻找相似块构造三阶张量,根据背景张量的低秩性和块效应的稀疏性,利用扩展于张量上的增广拉格朗日乘子法求解一个低秩张量恢复问题。从张量模型的角度来进行视频块效应处理,更好地保护了高维数据的结构特性。实验结果显示,相对于传统去块效应方法,通过该方法得到的视频图像有更高的峰值信噪比(PSNR)和更好的视觉效果。
基于Kinect体感交互的多人在线虚拟实验系统
孙博文,张佳梁,蔡亚飞,郭文兰
计算机科学. 2016, 43 (9): 284-288.  doi:10.11896/j.issn.1002-137X.2016.09.057
摘要 ( 86 )   PDF(1613KB) ( 576 )   
参考文献 | 相关文章 | 多维度评价
为了满足多人异地进行真实感虚拟实验的需求,使用Kinect体感设备和Unity 3D引擎搭建了一个多人在线虚拟实验系统。在该系统中,使用Unity 3D引擎搭建虚拟实验场景,通过导入3D Max制作的实验器材模型进行实验搭建,并通过网络通信技术实现远距离多人在线操作。对于真实感部分,采用Kinect体感技术捕捉的身体姿势被用来控制虚拟场景中第一人称角色的走动、抓取和操作实验器材以及选取虚拟场景中的菜单。实验结果证明,Kinect姿势识别具有很高的准确性和鲁棒性,并且不容易被光照条件和复杂的背景所影响,服务器与客户端的通信对于建立远程虚拟实验系统来说足够稳定。该系统具有成本低、真实感较强的优点。
基于非监督特征学习的兴趣点检测算法
周来恩,王晓丹
计算机科学. 2016, 43 (9): 289-294.  doi:10.11896/j.issn.1002-137X.2016.09.058
摘要 ( 126 )   PDF(2912KB) ( 310 )   
参考文献 | 相关文章 | 多维度评价
由于兴趣点是图像中的基础、关键特征,因此兴趣点检测是图像配准、图像检索以及图像识别的关键步骤。基于兴趣点对于图像特征响应较为强烈的特性,结合非监督特征学习算法可以自主地从无标签的样本中提取特征的思想,提出了UFL-ID兴趣点检测算法。该算法无监督学习了图像的底层特征,对特征进行信息量和各向同性的评价,并利用特征的卷积响应及评价参数寻找图像中的兴趣点。与其他常见的兴趣点检测算法的对比实验表明,该算法具有良好的重复性与抗噪能力。
光流分量分解的步态识别
罗正平,刘延钧,杨天奇
计算机科学. 2016, 43 (9): 295-300.  doi:10.11896/j.issn.1002-137X.2016.09.059
摘要 ( 113 )   PDF(1517KB) ( 464 )   
参考文献 | 相关文章 | 多维度评价
步态识别因其远距离和难于伪装等特点在生物识别技术中颇受关注。针对目前特征提取方法信息量不足的现状,提出一种基于光流分量分解的步态识别方法,对步态光流图中横向分量和纵向分量为正的部分按行、列进行分解,求出每行和每列的光流横、纵向分量,得到4个特征向量。根据训练得出的每个特征向量在识别过程中的权重进行特征融合。将主成分分析和线性判别分析相结合,用动态时间规整算法进行匹配,最后采用最近邻分类算法分类。在CASIA Database B和C上的实验表明,该方法在正常、背包和穿大衣的条件下分别得到了97%,90%和64%的识别率,在慢速和快速行走的条件下分别得到了88%和87%的识别率。
有监督的无参数核局部保持投影及人脸识别
龚劬,许凯强
计算机科学. 2016, 43 (9): 301-304.  doi:10.11896/j.issn.1002-137X.2016.09.060
摘要 ( 86 )   PDF(394KB) ( 239 )   
参考文献 | 相关文章 | 多维度评价
针对发掘人脸图像中的高维非线性结构,将加核及构造无参数近邻图两种思想同时引入到局部保持投影算法中,在有监督的模式下,提出了一种新的有监督的无参数核局部保持投影(Parameter-less Supervised Kernel Locality Preserving Projection,PSKLPP)算法并给出了其推导过程。该算法通过将欧氏距离改为对离群数据更为鲁棒的余弦距离,构造无参数近邻图,利用核方法提取人脸图像中的非线性信息,并将其投影在一个高维非线性空间,运用局部保持投影算法得到一线性映射,有效避免了在计算相似矩阵过程中面临的复杂参数选择问题。在ORL和Yale人脸库上的仿真实验验证了所提算法的有效性。
基于稀疏表示的低分辨率人脸疲劳表情识别
张灵,田小路,罗源,常捷,吴勇
计算机科学. 2016, 43 (9): 305-309.  doi:10.11896/j.issn.1002-137X.2016.09.061
摘要 ( 91 )   PDF(1562KB) ( 431 )   
参考文献 | 相关文章 | 多维度评价
为了有效提高低分辨率图像的人脸疲劳表情识别性能,提出一种基于稀疏表示的低分辨率人脸疲劳表情的识别方法。首先,采用肯德尔和谐系数可信度分析法构建了低分辨率人脸疲劳表情图像库TIREDFACE。其次,通过图像库中的低分辨率样本疲劳表情图像进行稀疏表示,再利用压缩感知理论寻求低分辨率测试样本的最稀疏解,采用求得的最稀疏解实现低分辨率人脸疲劳表情的分类。在低分辨率人脸视觉特征的疲劳表情图像库TIREDFACE的实验测试结果表明,将该方法用于低分辨人脸疲劳表情识别,性能优于线性法、最近邻法、支持向量机以及最近邻子空间法。可见,该方法用于低分辨率人脸疲劳表情识别时识别效果较好,精确度较高。
基于音频事件检测和分类的音频监控系统背景模型自适应方法研究
张爱英,倪崇嘉
计算机科学. 2016, 43 (9): 310-314.  doi:10.11896/j.issn.1002-137X.2016.09.062
摘要 ( 145 )   PDF(423KB) ( 256 )   
参考文献 | 相关文章 | 多维度评价
随着监控系统中音频传感器应用的与日俱增,音频事件检测与分类已成为一个重要的研究课题。音频系统所处的音频环境(不同场所、不同噪声)非常复杂,以致检测与分类音频事件异常困难。因此,进行背景模型自适应从而适应不断变化的音频环境变得十分重要。提出了利用受限的最大似然线性回归方法对背景模型进行自适应。采用实际监控场景中的音频数据和模拟录制数据,研究了背景模型自适应方法以及如何有效地进行背景模型自适应。实验结果表明背景模型自适应可以提高目标声音事件的检测性能,减少系统误报。
基于改进的背景模型的图像识别算法研究
魏霖静,宁璐璐,代永强,侯振兴
计算机科学. 2016, 43 (9): 315-319.  doi:10.11896/j.issn.1002-137X.2016.09.063
摘要 ( 99 )   PDF(1531KB) ( 249 )   
参考文献 | 相关文章 | 多维度评价
当图像亮度不均匀、对比度低时,提取图像前景较困难。为此,提出一种图像分割方法,结合正弦基函数和绝对值距离测度构建背景模型,依据优化理论和迭代法求解背景模型,通过比较背景模型中各像素点亮度与实际图像中各像素点亮度来判别各像素点是背景还是前景。为应对图像亮度不均匀的情况,在图像分割前对图像进行分块,在分块图像中依据背景模型或相邻分块背景相似度进行图像分割。实验结果表明,在普适性方面,相对于经典的模糊C均值法和OTSU法,该方法的分割误差小,尤其是对亮度不均匀和对比度低的图像;在掌纹图像分割应用方面,与迭代线跟踪法和模糊粗糙集法相比,该方法的错误率低、信噪比高、处理时间短。最后将提出的分割算法应用在人脸识别上,实验结果表明了该算法的先进性。