计算机科学与探索杂志

计算机科学与探索杂志2019年第5期

• 图像篡改检测感知哈希技术综述

  杜玲，陈振

  互联网的发展使得多媒体的真实性、完整性认证成为亟待解决的问题。感知哈希在理解图像内容基础上，通过简短的感知摘要来完成图像内容的识别和认证，为解决与多媒体认证相关的管理问题提供了一种更为便捷的方式。首先，总结了目前基于底层线索和基于学习的感知哈希图像篡改检测方法，并根据方法的不同特点进行了更为细致的分类。其次，介绍了常用的数据集，给出了三种算法性能评价指标，并在不同数据集上对最近的几种算法进行了定性和定量的比较分析。最后，对基于感知哈希的图像篡改检测的关键问题进行了总结，并对未来的发展趋势进行了展望。

• 面向多源数据的可扩展主题建模分析框架

  唐爽，张灵箫，赵俊峰，谢冰，邹艳珍

  随着信息技术的不断发展和应用，大量信息系统积累了海量多源异构数据，这些数据中有很大一部分都是结构化数据，具有高维度、低质量、无标注等特点，难以进行特征提取与进一步的知识提炼。主题建模是文本处理和数据挖掘中的一个非常重要的方法，它是一种无监督学习算法，最初用于对无结构的自然语言文本进行建模，可以有效地从文本语义中提取主题信息，以进行特征提取和降维分析，然而主题建模技术尚不能很好应用在关系复杂的多源数据，尤其是结构化数据的处理中。提出了一个基于可扩展主题建模技术的针对结构化与非结构化多源数据分析框架，通过数据导入、数据分析、数据可视化三个步骤对多源数据进行基于主题建模技术的数据分析，并在此基础上实现了一个多源数据分析工具，最后通过两个数据集的实验证明了所提的多源数据分析框架的有效性。

• 基于卷积神经网络的微博话题内容搜索方法

  周南，杜军平，姚旭，梁美玉，薛哲，LEE JangMyung

  针对由于微博文本的数据特性造成的传统信息搜索方法无法直接实现微博话题内容搜索的问题，提出了一种基于卷积神经网络的微博话题内容搜索方法，对微博安全话题内容进行搜索和匹配排序。该方法包括基于深度卷积神经网络的微博内容筛选和微博内容匹配两部分。微博内容筛选依据深度卷积特征表示进行微博内容筛选，微博内容匹配通过卷积特征非线性变换对筛选结果进行匹配排序。微博内容筛选和微博内容匹配对国民安全话题相关的微博文本内容局部特征进行处理，对筛选结果进行相似度计算从而实现相似度匹配。实验结果表明该方法在微博搜索性能上优于现有同类方法，并验证了所提出方法针对安全话题的微博文本内容搜索的有效性。

• 新型锁位式混合查询树射频识别防碰撞算法

  南敬昌，樊爽，李蕾，高明明

  针对无线射频识别技术系统中标签碰撞产生的时隙过多和通信复杂度高等问题，在二叉树和四叉树查询树防碰撞算法的基础上，利用对碰撞位锁位和预测子节点的方法，提出一种新型锁位式混合查询树（novel lock-bit hybrid query tree，NLHQT）算法。该算法通过锁位指令提取碰撞位信息，并针对提取出的碰撞位信息进行预测，在减少碰撞时隙的同时，通过预测使阅读器产生新的查询前缀，从而避免了空闲子节点的产生。仿真结果表明，与现有的锁位式树形结构（regressive lock-adaptive multi-tree search，RLAMS）和改进的混合查询树（improved hybrid query tree，IHQT）防碰撞算法相比，该算法在减少总时隙数和通信复杂度方面更为有效，能够有效提高识别标签的效率。

• 海量数据上有效的top-k Skyline查询算法

  韩希先，宋翠，戈韵如，高宏，李建中

  在许多应用中，Skyline查询是一种十分重要的查询类型，它在潜在的巨大的数据空间中返回不被其他元组支配的用户感兴趣的元组，但是Skyline查询无法控制返回结果的数量。处理一个新的top-k Skyline查询问题，该查询返回支配分数最大的k个Skyline元组，从而控制了需要向用户返回的查询结果数量。分析发现，大多数现有算法忽略了利用支配分数作为限制Skyline查询的结果数量的度量。提出一个新的基于表扫描的RSTS（ranked Skyline with table scan）算法来有效计算海量数据上的top-k Skyline结果。RSTS算法首先对表执行预排序操作，保证预排序表的元组按照对有序列表的round-robin扫描的顺序排列。RSTS算法包括两个阶段。阶段1利用对预排序表的顺序扫描来获得候选元组。阶段2计算候选元组的支配分数并返回结果。可以证明，RSTS算法具有早结束特性，并给出其扫描深度的理论分析。提出对于候选元组的剪切操作，理论剪切效果表明，绝大多数的Skyline结果可以直接丢弃。实验结果表明，RSTS算法可以有效计算top-k Skyline结果。

• 面向时间依赖路网的连续k近邻查询

  李佳佳，李雨现，夏秀峰，王波涛，刘向宇

  连续k近邻查询（continuous k-nearest neighor，CkNN）定义为查找指定路径上每个点的k个最小代价数据对象。目前关于CkNN的研究都是在欧式空间与静态路网中实现的，这些算法不能直接应用到边权值变化的时间依赖路网中。定义并解决了时间依赖路网中的CkNN问题，利用积分的性质以及通过对权值代价函数合并的方式提出了两阶段的基于分割点的CkNN查询算法。过滤阶段提出了计算节点到达时间的方法，再利用到达时间查询出多个候选k近邻结果；求精阶段将查询点到候选结果的权值函数合并，通过计算函数交点得到分割点，进而为查询返回若干个分割点以及相应区间内的k近邻结果。实验结果表明，与进行多次快照k近邻查询相比，所提算法在响应时间上减少了近一个数量级。

• 融合社会关系的机会网络有效数据转发策略

  严晔晴，陈志刚，吴嘉，王磊磊

  机会网络是一种具有延迟容忍网络特征的移动自组织网络。随着各种具有短距离通信功能的便携式移动设备的迅速普及，具有社会性的机会网络应用场景增多。机会网络中具有类似于节点聚集的现象，节点表现出的某些特征呈现出了社区结构的特性。然而，现有的路由算法没有考虑到节点社会性对网络中消息传递的影响，其传输成功率较低且造成大量的时延和网络开销。针对该问题提出了一种基于社区和社会性的数据转发机制，根据节点间的社会关系将网络划分成若干个社团结构，通过分析社区内节点的重要程度删除一些低效节点，并对这些社区结构进行再收缩，使社区结构紧密，提高传输效率。仿真结果表明，该算法相对Spray and Wait算法、PRoPHET算法和SCR算法（effective social relationship measurement and cluster based routing in mobile opportunistic networks），具有较高的传输成功率和较低的传输延迟。

• 基于网络表示学习的链路预测算法

  杨晓翠，宋甲秀，张曦煌

  网络是表达对象之间复杂联系的重要形式，广泛存在。而链路预测作为网络分析的重要方法，具有很大的研究意义和应用价值。传统的链路预测算法普遍是基于邻接矩阵的稀疏表示方案而设计，计算效率低且扩展性差。首先引入网络表示学习的概念，创新性地提出基于几何布朗运动的随机游走算法GbmRw，然后进一步设计出网络表示学习算法GBMLA，实现更具区分能力与表达能力的网络表示，最后以节点表示向量的欧式距离来表征节点之间的相似性，从而预测其链路存在的可能性。不同领域的多个网络中进行反复实验的结果表明，该算法较之于基于原始网络设计的传统算法，预测效果得到了明显的提升，也进一步肯定了网络表示学习对于链路预测工作的重要意义。

• 参数字典稀疏表示的完全无监督域适应

  余欢欢，陈松灿

  无监督域适应（unsupervised domain adaptation，UDA）针对的是源域有标记而目标域无标记的学习问题，其目的是利用从标记大样本源域中所学“知识”来促进无标记小样本目标域的学习性能。但现实中也往往存在样本无标记的源域，形成了所谓的完全无监督域适应。该问题给域适应学习带来了严峻的挑战。受先前提出的软大间隔聚类学习（soft large margin clustering，SLMC）启发，提出了一种参数迁移方法——参数字典稀疏表示的完全无监督的域适应方法（whole UDA，WUDA）。SLMC采用分类学习思想在输出（标记）空间中实现给定数据的聚类，在这种实现原理的启发下，从参数（决策函数的权重矩阵）公共字典的角度，在源域和目标域的权重间进行互适应参数字典学习实现知识迁移，同时引入[l2,1]范数来约束字典系数矩阵，使得各域权重可从公共字典中自适应地选择，从而实现域适应学习。最后，在相关数据集上的实验显示了WUDA在聚类性能上的显著有效性。

• 基于多特征融合的显著性目标检测算法

  张守东，杨明，胡太

  显著性目标检测是获取图像中视觉显著目标的任务，它是计算机视觉及相关研究领域的重要内容。当前在复杂的自然场景下基于深度学习的算法依然存在特征学习不足和检测错误率较高的问题，因此提出一种新颖的基于多特征融合的显著性目标检测算法。以HDHF（hybrid deep and handcrafted feature）模型的预测显著图作为特征，融合全局像素的深度特征。此外，利用显著性提名获取候选目标的位置，并在各候选目标中添加中心先验。在全卷积神经网络中，利用前向传播算法最终预测得到像素级的显著性目标。在四个包含多个显著性目标和复杂背景的图像数据集上进行验证，实验结果表明，该算法有效地提高了复杂场景下显著性目标的检测精度，尤其是在背景复杂的图像上具有较优的检测效果。

• 未知环境下的蚁群-聚类自适应动态路径规划

  刘新宇，谭力铭，杨春曦，翟持

  针对用于动态环境中的机器人路径规划的蚁群算法存在收敛速度慢，路径累计转折角大，对环境变化适应性低等问题，提出了一种未知环境下的蚁群-聚类自适应动态路径规划方法。依据聚类算法对环境复杂程度的准确判别自动改变寻优半径，达到充分利用机器人有限的计算能力，提高收敛速度的目的；通过识别对角障碍，生成虚拟障碍，确保规划的路径不穿过对角障碍；通过平滑机制对搜索的动态路径做平滑优化处理，有效降低了路径长度，减少了累计转折角。仿真结果表明，提出的算法能够根据障碍的复杂程度自动选择合适的搜索半径，完成路径的动态规划，体现出良好的环境适应能力和较好的综合路径优化性能。

• Adam优化的CNN超分辨率重建

  赵小强，宋昭漾

  为了使单帧图像在不同放大倍数的条件下进行超分辨率重建能得到较好的效果，提出了一种Adam优化的卷积神经网络（convolutional neural network，CNN）超分辨率重建方法。该方法首先使用ISODATA（iterative selforganizing data analysis）聚类算法对训练的图像集进行分类处理，然后在Adam优化的卷积神经网络中对输入图像进行特征提取和非线性映射得到特征映射图，最后在Adam优化的卷积神经网络中对特征映射图进行反卷积重建得到多尺度放大的重建图像。通过实验验证使用该方法在不同放大倍数条件下的重构效果优于传统算法，在视觉效果上有较好的表现。

• MEPaxos：低延迟的共识算法

  赵守月，葛洪伟

  共识问题作为分布式计算中最重要的基本问题之一，被广泛应用在状态机复制、原子广播、领导者选举等领域。解决共识问题的算法通常存在单领导者性能瓶颈、响应延迟受命令冲突的影响等问题。针对这些问题，在非拜占庭故障下的异步分布式系统中，提出了一种低延迟的共识算法MEPaxos（modified Egalitarian Paxos）。首先，提出了系统平均延迟的计算方法；然后，引入超时机制对二阶段提交算法进行改进；接着，根据系统平均延迟计算结果，利用改进的二阶段提交算法自动选择平均延迟较小的算法模式执行；最后，在亚马 逊弹性计算云（elastic compute cloud，EC2）平台上将此算法与当前共识算法进行实验对比分析，结果表明，MEPaxos算法下，系统延迟性能得到了提升。

• 面向局部多约束的属性约简方法研究

  董杰，王逊，张文冬，王平心，杨习贝

  传统求解约简的启发式算法采用单一的度量指标作为约束条件，但这一策略并不能保证约简满足多重度量指标下约束需求。除此之外，绝大多数的约简定义是建立在考虑所有决策类基础上的，而忽视了不同决策类别所对应的度量指标在约简前后的变化情况。针对这些问题，提出了一种面向局部多约束的属性约简策略，其目的是使得每个决策类别都能够满足多重度量指标下的约束条件。借助邻域粗糙集模型，在UCI数据集上将传统约简策略与局部多约束约简策略进行了对比分析，将近似质量与条件熵作为多重约束中的度量指标，实验结果表明局部多约束约简能够在近似质量满足约束条件的前提下，显著降低条件熵，从而展现了局部多约束约简的有效性。

• 商空间粒度的可逆性研究

  陈林书，王加阳，柳媛慧，马庆

  粒计算是近年来人工智能领域的重要研究热点，而商空间理论是最重要的粒计算模型之一，其主要思想是通过保假原理实现求解问题从细粒度到粗粒度的商空间构造过程。这个粒化过程是一个信息有损过程，是不可逆的，于是研究商空间粒度的可逆性。首先，提出逆商空间的概念并定义其构造方法，为商空间（粗）粒度到原空间（细）粒度的可逆转换提供形式化的数学方法；其次，通过分析逆商空间与原空间的一致性，论证并实例分析商空间粒度的两个可逆性条件——定义原空间上的双射函数或保证原空间上所有开集的饱和性。旨在进一步丰富和完善商空间粒度转换理论和粒计算方法。

• BCI-代数的扰动模糊q-理想

  彭家寅

  将扰动模糊集应用于BCI-代数中，引入了BCI-代数的扰动模糊q-理想的概念，研究了它相关性质，讨论了扰动模糊q-理想与扰动模糊理想、扰动模糊子代数之间的关系，给出了扰动模糊q-理想的几个等价刻画和扩展定理，指出了BCI-代数的扰动模糊q-理想的同态象与同态原象在一定条件下仍是扰动模糊q-理想。