计算机科学与探索杂志

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

• 基于空间密铺的并行Stencil算法

  郭鹏，袁良，张云泉，黄珊

  Stencil计算是一种科学和工程应用中常见的循环模式，而分块技术是一种提高数据局部性和并行性的强大转换方法。与以往直接对整个迭代空间进行分块的分块技术不同，提出了一种新的两层密铺分块的并行算法。首先，利用不同分块密铺数据空间；然后，所有分块沿时间维度扩展密铺迭代空间。该算法有以下优点：（1）最大化并发执行；（2）无冗余计算；（3）简洁的循环条件；（4）适应Stencil不同的尺寸、形状、阶数和边界条件。实验结果表明，对于3D27p Stencil，非周期边界的性能比Pluto高12%，周期边界的性能比Pochoir最高提升40%。

• 网络断路感知的同步机制

  项哲慧，秦小麟，犹锋，刘亮

  在网络中，由于负载过量等原因导致网络断路的情况是常见的，而现有的同步算法未曾考虑这种状况，通过实验表明网络断路对同步效率的影响很大，最坏情况下断路会使得现有算法的同步时间增加一倍。为了缓解现有同步算法在网络断路情况下效率骤降的问题，在现有Barrier同步算法的基础上，提出一种动态局部连续树算法（dynamic local continuous tree，DLCT）。在断路时，调用提出的异步调整算子（asynchronous adjustment operator，AAO）对通信模式进行调整使之避开断路，并构造局部连续树（local continuous tree，LCT）结构的通信模式高效传递同步消息。DLCT的通信模式能动态调整有效避开断路，并提高同步机制在断路情况下的效率。在断路情况下DLCT比现有算法效率高30%到50%。

• 带有覆盖率机制的文本摘要模型研究

  巩轶凡，刘红岩，何军，岳永姣，杜小勇

  近年来文本信息出现了爆炸式增长，人们没有足够的精力去阅读这些文本，因此如何自动地从文本中提取关键信息就显得尤为重要，而文本摘要技术可以很好地解决这个问题。目前的文本摘要技术主要是利用带有注意力（attention）机制的序列到序列模型（sequence to sequence）对文本生成摘要，但是注意力机制在每个时刻的计算是独立的，没有考虑到之前时刻生成的文本信息，导致模型在生成文本时忽略了之前生成的内容，导致重复生成部分信息。针对这一问题，在文本摘要模型中引入了一种新的覆盖率（coverage）机制，通过覆盖向量记录历史时刻的注意力权重分布信息，并用来改变当前时刻注意力机制的权重分布，使模型更多地关注没有利用到的信息。改进后的模型在新浪微博数据集上进行了实验，实验结果表明，基于新提出的覆盖率机制的文本摘要模型的准确度高于普通的序列到序列模型。

• 数据、信息和知识三层图谱架构的推荐服务设计

  邵礼旭，段玉聪，周长兵，高洪皓，陈世展

  海量的学习资源会引起用户在学习过程中产生认知过载和资源迷航，对数据、信息和知识等形态的资源的原始表述的自然语言的机器理解、自动处理、自动综合和自动分析等成为了巨大的挑战。从应对自动增量式结合经验知识和减少人工专家交互负担等两方面考虑，从资源建模、资源处理、处理优化和资源管理等角度进行研究，基于对现有知识图谱（knowledge graph）概念的拓展提出了一种三层可自动抽象调整的解决架构。该架构借助从数据图谱上以实体综合频度计算为核心的分析到信息图谱和知识图谱上的自适应的自动抽象的资源优化过程支持经验知识引入和高效自动语义分析。该框架借助对应5W（who/when/where，what and how）问题的分类接口衔接用户的学习需求等资源化描述，为用户提供个性化学习服务推荐。

• 非均匀划分拟阵约束下的多样性推荐方法

  和凤珍，石进平

  多样性推荐方法旨在提供既满足相关性又具有多样性的top-k推荐结果。大多数现有的多样性方法没有同时考虑多样性和准确度，而且这些方法假设每个推荐项的重要程度是相同的。受此启发，针对个性化推荐系统，提出一种新的基于用户偏好的多样性推荐模型。该模型对用户的整体类别偏好程度、同一类别内部的偏好程度和相关度进行建模；将多样性和相关性同时融合到子模函数中，同时在模型上施加了非均匀划分拟阵约束（即不同用户对不同类别的偏好程度以及同一类别内部的偏好程度不同，每个推荐项的重要程度也不同）；证明了最大化提出的目标函数是NP-hard问题，并通过类别簇内局部贪心求解子模函数获得[(1-1/e)]的近似保证率，同时降低了算法复杂度。最后，引入一个惩罚因子自动调节同一类别中的推荐项加入推荐列表的困难程度。不同数据集上的实验结果表明：提出的方法不仅能够在准确度和多样性之间取得有效的折中，而且具有高效性。

• 结合深度学习的网络邻居结构研究及应用

  寇晓宇，吕天舒，张岩

  通过研究网络的拓扑结构可以探索到丰富的知识，特别是网络中节点的邻居可以形成不同的邻居结构，而不同的结构蕴含着不同的意义，进而也有着不同的影响。实际上，邻居结构与节点的交互行为之间是互相影响、互为因果的。对三种最为普遍的邻居结构进行分析，并提出结合深度学习的网络邻居结构影响力模型DNSI（neighbor structure influence based on deep learning）。通过对图片格式的网络数据提取特征，DNSI可以得到三种邻居结构影响力。分别在几个真实世界网络数据集上进行节点属性预测、类别中心度度量和用户行为预测等任务，实验结果表明该模型在绝大多数情况下具有优越性。

• 局部差分隐私约束的链接攻击保护

  杨高明，方贤进+，肖亚飞

  传统意义的交互式差分隐私保护模型对数据查询结果进行扰动，不能满足用户对数据的多样化需求。为有效使用数据并满足隐私保护要求，用局部差分隐私的思想，在随机响应的基础上实现数据集的链接攻击保护。首先，针对原始数据的分布情况，研究如何更好地选择随机转换矩阵[P，]在数据效用和隐私保护的基础上更好地实现链接隐私保护，从而避免身份披露和属性披露；其次，针对敏感、准标识符属性以及它们之间的组合讨论相应的隐私保护方法和数据效用的最大化，并给出数据扰动算法；最后，在已知数据分布均值和方差的基础上实验验证原始数据和扰动数据之间的KL-散度、卡方。实验结果表明所用随机化可以带来较小的效用损失。

• 深度神经网络在森林步道视觉识别中的应用

  侯永宏，吕晓冬，陈艳芳，赵健，李器宇，陈浩

  无人机自主导航在已知或结构化环境中已取得大量研究成果，但在森林等非结构化环境中的技术仍不够成熟。无人机在复杂的森林环境中通过识别森林步道飞行是一种安全有效的行进方式。提出了一种针对森林环境下路径识别的双列深度神经网络模型（two-column deep neural networks，2CDNN），该网络模型通过直方图均衡化结合边缘提取的方法获取特征图，再将特征图与RGB图馈入两路并列的深度残差网络，从而提取出森林场景中的色彩与纹理特征，最终根据网络分类结果来确定飞行方向指令。该模型在森林数据集IDSIA上进行评估，准确率高达91.31%，比现有的方法提高了4.41%。实验结果表明该模型可以有效地提高无人机在森林环境中的路径感知性能，在自主导航领域具有一定的泛化性和实用意义。

• 紧凑型深度卷积神经网络在图像识别中的应用

  吴进，钱雪忠

  针对深度卷积神经网络的结构越来越复杂，参数规模过于庞大的问题，设计出一种新的紧凑型卷积神经网络结构Width-MixedNet和其多分支的基本模块Conv-mixed，该架构扩展了卷积神经网络的宽度。Conv-mixed利用分支结构使多个不同的卷积层处理同一个特征图，提取不同的特征。在深度卷积神经网络的识别任务中，使用多个小型卷积层叠加，逐层缩小特征图的方法代替全连接层进行最后的特征提取。整个Width-MixedNet架构的参数数量只有3.4×105，仅有传统深度卷积神经网络的1/30。分别在CIFAR-10、CIFAR-100和MNIST数据集上进行实验，准确率分别达到了93.02%、66.19%和99.59%。实验表明，Width-MixedNet有更强的学习能力和表现能力，在提高识别精度的同时，大大降低了网络的参数规模。

• 梯度约束SLIC的快速视频目标提取方法

  桂彦，汤问，曾光

  提出了一种基于梯度约束SLIC（simple linear iterative clustering）的快速视频目标提取方法，允许在关键视频帧上提供少量用户交互下，该方法能够快速并精确地提取复杂视频片段中的视频目标。首先，采用梯度约束的SLIC算法对视频片段进行预处理，有效降低待处理的视频数据量；其次，以预处理生成的超像素为结点构建三维无向图，在此基础上定义能量函数，并结合外观特征与运动特征建立鲁棒的相似外观度量机制；最后，采用最大流/最小割算法最小化能量函数以得到三维无向图的最优划分，从而最终实现视频目标提取。实验结果表明，该方法在处理包含复杂场景的视频片段时能够获得理想的视频目标提取结果，且时间效率相比现有视频目标提取方法明显提高。

• 人工蜂群算法优化的特征选择方法

  巢秀琴，李炜

  在分类问题中，数据之间存在的大量冗余、不相关的特征不仅不能增加分类准确率，反而会降低分类算法执行的速度。特征选择通过最大化分类正确率和最小化特征数来解决这个问题，由于这是两个相互矛盾的目标，因此可以将特征选择问题视为一种多目标优化问题。为了提升特征选择的效率，提出了一种基于Knee Points的改进多目标人工蜂群算法的特征选择方法（artificial bee colony algorithm based on Knee Points， KnABC），设计了一种快速识别Knee Points的方法，并改进了引领蜂和引领蜂算子。与其他经典多目标算法在11个UCI测试数据集上的特征选择实验结果表明，提出的算法在减小分类特征数、增大分类结果准确率方面具有显著效果。

• 原信息与映射信息组合的多核学习降维方法

  李旭，王士同

  对于一些降维算法来说，数据的流形结构会对其降维效果造成很大影响。针对已有的多核学习降维算法没有考虑到保持数据流形结构这一问题，在其基础上提出了一种新的多核学习降维方法。其实质是由于数据通过映射函数投影到高维空间，在这个过程中可能会造成数据流形结构的扭曲，为了保持原数据的流形结构，从原数据中选择全部或局部信息与映射空间信息进行组合，从而使得在高维投影空间中能够较好地保存原数据的流形结构，减小因数据在映射空间中产生扭曲而对降维结果造成的影响。原信息与特征信息组合的方法最终将表示为核之间的耦合，并可以通过原多核学习框架的优化方法进行优化得到其核权重系数。实验证明，通过使用新方法，使用少量的特征也能够达到不错的效果，同时在时间效率上较原多核学习框架的方法也有所提高。

• 用于域适应的多边缘降噪自动编码器

  杨帅，胡学钢，张玉红

  神经网络模型被广泛用于跨领域分类学习。边缘堆叠降噪自动编码器（marginalized stacked denoising autoencoders，mSDA）作为一种神经网络模型，通过对源领域和目标领域数据进行边缘化加噪损坏，学习一个公共的、健壮的特征表示空间，从而解决领域适应问题。然而，mSDA对所有的特征都采取相同的边缘化加噪处理方式，没有考虑到不同特征对分类结果的影响不同。为此，对特征进行区分性的噪音系数干扰，提出多边缘降噪自动编码器（multi-marginalized denoising autoencoders，M-MDA）。首先，利用改进的权重似然率（weighted log-likelihood ratio update，WLLRU）区分出领域间的共享和特有特征；然后，通过计算特征在两个领域的距离，对共享特征和特有特征进行不同方式的边缘化降噪处理，并基于单层边缘降噪自动编码器（marginalized denoising autoencoders，MDA）学习获取更健壮的特征；最后，对新的特征空间进行二次损坏以强化共享特征的比例。实验结果表明，该方法在跨领域情感分类方面优于基线算法。

• 车辆合乘问题的分布式复合变邻域搜索算法

  郭羽含，伊鹏

  针对长期车辆合乘问题（long-term carpooling problem，LTCPP），提出一种基于分布式的复合变邻域搜索算法，利用分布式计算的优势可快速求解出大规模用户的合乘匹配方案。首先构建带有时间窗约束和车容量约束的数学模型，建立成本计算的目标函数；然后按复合距离优先算法将所有用户分配到各合乘小组中，最终得到满足约束条件的初始合乘方案。通过对变邻域搜索算法进行分布式处理，使算法可以对初始合乘方案进行并行迭代优化计算，得到最终的合乘方案。实验结果表明，该算法在速度和大规模问题求解质量上具有明显的优势。

• 基于混合采样的非平衡数据分类算法

  吴艺凡，梁吉业，王俊红

  过采样和欠采样方法是处理非平衡数据集分类的常用方法，但使用单一的采样算法可能造成少数类样本过拟合或者丢失含有重要信息的样本。提出了基于分类超平面的混合采样算法SVM_HS（hybrid sampling algorithm based on support vector machine），旨在克服SVM算法在处理非平衡数据时分类超平面容易偏向少数类样本的问题。该算法首先利用SVM算法得到分类超平面。然后迭代进行混合采样，主要包括：（1）删除离分类超平面较远的一些多数类样本；（2）对靠近真实类边界的少数类样本用SMOTE（synthetic minority over-sampling technique）过采样，使分类超平面向着真实类边界方向偏移。实验结果表明相比其他相关算法，该算法的F-value值和G-mean值均有较大提高。

• 有限域上稀疏多元多项式插值算法

  唐敏，邓国强

  稀疏插值是一种降低计算机代数算法时间复杂度的有效方法，在信号处理、压缩感知、结式计算、图像处理等领域都有广泛应用。为了提高稀疏多元多项式插值算法的效率，对Javadi/Monagan稀疏插值算法进行了改进。首先，消除了必须预先给定项数界[T]的限制，通过计算特定的矩阵行列式，得到插值多项式[f]的准确项数。然后，消除了必须预先给定次数界[D]的限制，通过构造辅助函数，利用概率法结合提前终止技术的Cauchy插值法，得到插值多项式[f]的准确次数，解决了Javadi和Monagan论文中提出的次数界[D]过高而导致的高计算复杂度的问题。理论分析和实验结果表明了改进算法的优势，特别是在给定的次数界[D]过高的情况下，相较于Javadi/Monagan算法，改进算法的性能有较大提高。更进一步，由于改进算法无须给定项数界[T]和次数界[D]，对于实际问题在利用插值恢复或近似时更具实用性。