计算机科学与探索杂志

计算机科学与探索杂志2020年第7期

• 人工智能赋能的查询处理与优化新技术研究综述

  宋雨萌，谷峪，李芳芳，于戈

  数据查询处理与优化作为数据管理中最具挑战性的问题之一，一直受到广泛关注。传统的查询处理与优化技术在实际使用中需要针对特定的工作负载和数据集进行大量的手动调优，因而已经无法满足现代数据库系统的发展需求。受人工智能（AI）成功应用于多领域研究的启发，近期人工智能赋能的查询处理与优化新技术相继被提出并取得了一定的研究成果。针对这些研究工作，首先给出了人工智能赋能的查询处理与优化技术的主要任务，分析了与传统人工智能任务的区别。其次梳理了该领域的主要研究进展，并总结了主要优势与应用瓶颈。接着讨论了当前所面临的主要技术挑战。最后对该领域的未来发展进行了展望。

• 双目视觉的立体匹配算法研究进展

  赵晨园，李文新，张庆熙

  双目立体视觉技术具有成本低、适用性广的优点，在物体识别、目标检测等方面应用广泛，成为计算机视觉领域的研究热点。立体匹配是双目立体视觉技术中的核心算法，对实现物体三维重建具有重要作用。在分析局部、全局、半全局和基于深度学习的立体匹配算法研究现状的基础上，阐述了匹配代价、代价聚合、视差计算/优化、视差校正在立体匹配算法中的实际应用，总结及展望了立体匹配算法的发展趋势。立体匹配算法将着重解决无、弱纹理区域误匹配问题，深度学习算法用于立体匹配具有精度高的优点，是未来发展趋势，匹配算法将向高精度、实时性方向发展，为双目视觉技术中立体匹配算法的发展提供思路与参考。

• 竞争合作行为下的深度演化算法

  陈海娟，冯翔，虞慧群

  将深度与演化算法结合，提出一种深度演化算法，即群竞争合作优化（GCCO）算法。首先引入生物群模型来模拟群体搜索猎物的自然现象，算法通过多步迭代可简单实现优化问题求解。在生物群模型中，跟随者采用变步长的区域复制方式，平衡了收敛速度与优化精度，随机者采用基于特征变换的随机游走模式，避免陷入局部最优。其次引入竞争模型和合作模型增加算法复杂性，通过群体间的竞争和信息共享，提高算法的搜索性能。算法的数学模型是从群论、动力学以及帝国竞争理论推导出来的，在理论上也分析验证了算法的收敛性。最后在十个优化基准函数上与其他三种优化算法对比测试算法的性能。在解决上海市设立燃气站点提高到场及时率的实际问题中，GCCO算法也取得了比其他算法更好的效果。

• 统一框架下在线核选择的竞争性分析

  廖芸，张骁，廖士中

  在线核选择旨在给出在线核学习每回合的最优核，是在线核学习的基础性和关键性问题。在线核选择问题可归约为专家建议框架问题，其中专家集对应候选核集；每回合，根据专家的权重及专家的建议给出预测结果，并更新专家的权重。基于这一归约，在改进已有后悔界的同时，提出期望在线核选择的概念，并应用专家建议框架与度量任务系统的统一框架，给出期望在线核选择问题的后悔界和竞争比，并证明该竞争比在损失拓展情况下是稳定的。最后，给出结合在线核学习方法的竞争比。该项工作全面推广了在线核选择的概念，在统一框架下，不仅可以得到亚线性后悔界，同时也能得到较强的竞争比，为在线核选择研究开辟了新的途径。

• 自然语言生成多表SQL查询语句技术研究

  曹金超，黄滔，陈刚，吴晓凡，陈珂

  自然语言生成SQL查询不仅是构建智能数据库查询系统的一个重要组成部分，亦是新型供电轨道交通系统混合时态大数据个性化运维的难点之一。目前利用深度学习模型的方法专注于数据库中单表SQL查询生成，无法解决数据库中多表SQL查询生成。针对这个问题，采用一种基于SQL语句模板填充的方法，将序列生成问题转化为多个分类问题，在训练深度学习模型的过程中充分利用SQL子句不同预测成分之间的依赖关系。在FROM子句的多表JOIN路径生成方面，将其建模为斯坦纳树问题，采用一种全局最优的算法来进行求解。在一个开放的文本生成SQL数据集Spider上对模型和算法进行实验验证，实验结果表明该方法能有效地提升多表SQL查询生成的查询匹配准确率。

• 动态区间的加权模糊聚类算法

  罗浩，王彦捷，牛明航，邱存月，张利

  数据聚类在数据挖掘、数据分析中广泛应用，而不完整数据对数据聚类造成了很大困扰。针对不完整数据聚类中估值法填补缺失属性不准确的问题，提出动态区间的加权模糊聚类算法。首先，由属性相关度构造缺失属性的最近邻样本集，进而形成缺失属性估值区间。为进一步减小区间填补误差，使用基于最近邻样本集的离散度的区间因子来动态调节区间大小。其次，为充分挖掘属性空间的隐含信息，同时降低离群点对聚类中心的影响，对完整的区间型数据集进行基于局部密度的样本加权。最后，通过以上改进完成区间型样本的加权模糊聚类。利用多个UCI数据集和人工数据集验证提出的聚类算法，实验结果表明：动态区间的加权模糊聚类算法能有效提高聚类准确性、鲁棒性以及收敛的稳定性。

• 利用流挖掘和图挖掘的内网异常检测方法

  孙伟, 张羽

  内网恶意内部活动的证据通常隐藏在大型数据流中，例如数月或数年累积的系统日志，然而数据流往往是无界的、不断变化的和未标记的。因此，为实现高度准确的异常检测，提出集成流挖掘和图挖掘的内网异常检测方法，在发挥图挖掘的无监督优势的同时，融入了流挖掘的良好自适应能力。采用集成的方法，通过集成分类和更新，当出现概念漂移时，保证集成适应当前概念，使之可以检测到内网恶意行为。实验证明基于集成的方法比传统的单模型方法更有效，可以有效识别随时间改变其行为来隐藏恶意活动的内网异常，在面对隐藏在大量数据流中的内网异常且无标记的数据时，所提出的基于流挖掘和图挖掘的集成方法是十分有意义的。

• 利用环上容错学习问题构造可链接环签名方案

  叶青，王文博，李莹莹，秦攀科，赵宗渠，王永军

  针对格上可链接环签名方案中存在密钥较大、效率较低的问题，基于环上容错学习（RLWE）难题，依据“同态承诺→∑-协议→Fiat-Shamir转化”的技术路线，重新构造一个格上可链接环签名方案。首先构造一个基于RLWE难题的多项式环上的同态承诺方案，然后基于承诺方案设计一个∑-协议，并利用Fiat-Shamir转化方法将该∑-协议转化为可链接环签名方案，最后基于该可链接环签名方案提出一个简易的数字货币模型。安全分析表明，由于所提方案基于RLWE困难问题构建，方案的安全性可规约至格上困难问题，抵抗量子计算机攻击。效率分析表明，与以往格上可链接环签名方案相比，由于方案中环元素取自小多项式，所提方案具有更短的密钥尺寸和更高的计算效率，且方案描述更简单。

• S-C特征提取的计算机漏洞自动分类算法

  任家东，王倩，王菲，李亚洲，刘佳新

  近年来未知的计算机漏洞数量呈海量增长状态，对于大量的漏洞数据进行及时准确的分析和分类管理，是十分重要且有待解决的问题。因此，提出一种基于信息熵与综合函数[（S-C）]特征提取，并利用关联了特征词集间相互关系的平均一阶依赖贝叶斯模型（AODE）分类器的分类方法对计算机漏洞描述信息进行文本分类。首先，利用[S-C]特征提取法提取特征词。通过结合词语的类间重要程度和类内重要程度的综合函数[C]，计算出词语对于类别的重要程度。再利用词语对于类别间的信息熵[S]，来弱化对于分类较为混乱的词语的重要程度，选取得到准确的特征词集。最后，利用关联了特征词集间相互关系的AODE对漏洞数据集进行分类。通过实验对比表明，[S-C]特征提取法能够提取准确的特征词集，并且结合AODE分类器的分类准确率要高于传统的分类器模型。

• 基于联合信息保持的异构领域自适应

  许鹏，邓赵红，王骏，王士同

  异构领域自适应（HDA）的主要目的是借助源域的知识，辅助处于不同特征空间中目标域的数据进行建模。异构领域自适应一个核心的问题是如何在领域适配过程中有效保持原始数据的信息，减少因为特征变换导致的信息损失，提出了一个联合信息保持算法（JIP）来解决上述问题。所提算法通过两方面来保持原始数据的信息：一方面，在异构领域自适应场景中，两个领域之间通常存在大量配对样本，所提算法通过最大化配对样本之间的相关性来保持这种配对信息。另一方面，所提算法优化了结构信息保持策略，同时保持了原始数据的局部结构信息和全局结构信息。最终，将联合信息保持和分布匹配整合在一起，从而实现异构领域自适应。实验结果表明，所提算法较之于先进的异构领域自适应算法有明显优势。

• 基于近邻传输的粒度SVM算法

  程凤伟，王文剑

  传统粒度支持向量机（GSVM）模型可以有效提高支持向量机（SVM）的学习效率，但因其对初始粒划参数比较敏感，粒中心的选取比较粗糙，会损失一定的泛化能力。提出一种基于近邻传输的粒度支持向量机学习算法（APG_SVM）。首先在训练数据上采用近邻传输思想选取一组高质量的更具有代表性的粒中心加入到训练集，再根据粒中样本的混合度及粒中心到超平面的距离对训练集进行优化，生成最终训练集，然后进行训练，这样可使GSVM具有更好的泛化能力。在UCI标准数据集上的实验结果表明，与传统的粒度支持向量机相比，该算法分类效率有明显提高，在几个数据集上的正确率相对稳定，获得了较好的分类性能。

• 自适应概念漂移问题的增量集成分类算法

  韩明明，孙广路，朱素霞

  由于数据流具有非平稳特性，即概念漂移问题，导致机器学习模型的性能随着概念漂移的发生而降低。对分类器如何自适应概念漂移进行了研究，提出了以小数据块为输入的增量学习的增强集成算法，用于处理概念漂移情况下的数据流分类问题。该算法没有复杂的参数，但对弱分类器提出较高的要求，每次移除不合格的弱分类器后添加新的弱分类器，在迭代增量训练过程中根据训练误差更新样本和弱分类器的权重，最后通过加权投票方式整合各弱分类器的预测结果。用五组已知具体漂移情况的人工数据和三组未知漂移情况的真实数据进行实验，并与已有的算法进行对比，实验结果表明该算法能很好地处理概念漂移下的数据流分类问题。

• 流形学习与成对约束联合正则化非负矩阵分解

  曹佳伟，钱鹏江

  为处理目标数据集仅有部分成对约束信息可用的半监督聚类场景，基于非负矩阵分解（NMF）架构，通过学习给定成对约束知识和运用流形正则化理论提出了流形学习与成对约束联合正则化非负矩阵分解聚类方法（NMF-JRMLPC）。该方法一方面引入图拉普拉斯以刻画大量无标记样本蕴含的流形结构信息，另一方面将已知样本间的must-link或cannot-link成对约束规则融入目标优化设计，在很大程度上提高了所得算法的聚类性能。此外基于[l2,1]范数的损失函数设计也有助于优化NMF-JRMLPC的鲁棒性。在八个真实数据集上的实验结果证实了所提方法的有效性。

• 改进局部三值模式的烟雾识别和纹理分类

  李钢，袁非牛，夏雪，章琳，雷帮军

  为提高烟雾识别的检测率和降低误报率，首先提出了基于置信水平的局部三值模式（CLLTP），进而提出了基于CLLTP的组合特征模型（M_CLLTP）。CLLTP是依据差分图像的像素值呈正态分布而提出的一种改进的局部三值模式。M_CLLTP模型提取了原图的CLLTP特征、Gabor特征图的加权的CLLTP特征和边缘特征图的CLLTP特征，并融合它们生成M_CLLTP特征。对比实验显示，M_CLLTP方法在三个烟雾数据集上都获得了较高的检测率和[F1]分数、较低的误报率，在两个纹理数据库上获得了最高的平均召回率。实验结果表明，所提方法对烟雾和纹理具有很好的辨识能力，非常适用于烟雾识别。

• 背景与前景融合的RGB-D图像显著性检测

  赵强，王爱平，刘政怡

  RGB-D图像显著性检测是指在传统的2D图像中附加深度信息从而提取显著对象，但是现有的显著性检测模型，大多数只关注显著物体本身，却忽略了背景信息。因此，提出了一个新颖的显著性检测模型，将深度信息同时考虑到背景和前景中提取出显著区域。首先，通过图像边界信息的背景测量机制来去除前景噪声并从边界超像素中选择背景种子，从而计算出基于背景的显著图；其次，将输入的图像构造成图，并将深度信息引入到图形结构中，利用颜色、深度、位置等线索获取前景种子，从而计算出基于前景的显著图；最后，将背景图和前景图融合获得初始显著图，再加以元胞优化，迭代传播后得到最终的显著图。在三个RGB-D图像显著性检测数据集LFSD、NJU-400、NJU-2000上进行对比实验，实验结果表明，该方法具备有效性，同时也提高了检测准确率。

• 改进DeepLabv3+网络的肠道息肉分割方法

  王亚刚，郗怡媛，潘晓英

  为了提高结肠镜下肠道息肉检测率，提出了一种改进DeepLabv3+网络的肠道息肉分割方法。在数据预处理阶段，利用中值滤波的非线性滤波特性去除掉图像反光区域，并结合Grab Cut算法对息肉区域进行预提取，得到息肉位置的粗分割结果，将其与原图叠加以增强息肉位置的信号强度。在网络结构上，将通过神经架构搜索得到的最优密集预测单元引入DeepLabv3+网络，并在解码器部分采用3层深度可分离卷积逐步获取分割结果，减少分割过程中不完全分割的情况。实验通过对CVC-ClinicDB数据集进行训练和测试，以平均交并比、Dice系数、敏感度、精确率以及F1值作为评判标准，其中平均交并比达到0.947，其余4项指标也均高于0.935。实验结果表明提出的方法与现有方法相比，对肠道息肉图像分割在精度上有一定提升，对深度学习在肠道息肉图像的处理和分析具有借鉴意义。

• 鲁棒概率矩阵三分解

  史加荣，陈姣姣

  矩阵分解是计算机视觉、机器学习和数据挖掘中经常使用的数据分析工具。近年来，矩阵分解的概率模型已成为人们关注的焦点。现有的概率矩阵分解一般将数据矩阵分解为两个低秩矩阵之积，这可能会限制该模型的灵活性和实用性。为此，提出了鲁棒概率矩阵三分解模型（RPMTF）。该模型将数据矩阵分解为三个矩阵的乘积，并考虑了其鲁棒性。在模型求解时，先将拉普拉斯分布进行分层表示；再采用基于极大后验估计的策略，设计了一种条件期望最大化算法。在实验中，将鲁棒概率矩阵三分解应用到图像去噪和视频背景建模中，结果证实了所提方法的可行性与有效性。