计算机科学与探索杂志

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

• 共享经济预约模式下资源分配的拍卖机制设计

  张静，张骥先，李伟东，刘旭东，张学杰

  共享经济给人们生活方式带来巨大改变，但是其预约模式大都采用固定价格、先预约先服务的方式分配资源，导致供应商收益低下，资源利用率也不高。基于此，提出一种基于拍卖的机制RAUPAM（resources allocation and user payment approximation mechanism），该机制适用于任何按时租赁收费的共享资源，如共享停车位、住宿等，通过拍卖来解决预约模式下共享资源的分配及用户定价问题。在资源分配问题上，该机制采用关键路径思想对每个资源进行全局规划，提高资源利用率的同时保证收益极大化；在价格支付问题上，基于临界值求解用户支付价格，尽可能地降低用户支付，吸引用户参与。实验结果表明，在不同的资源密度和分配周期下，RAUPAM都优于传统的FCFS（first-come-first-serve）和MAXBID算法，说明RAUPAM在预约高峰期和低峰期都表现更优，且不受分配周期的影响。通过详细对比，RAUPAM的利润比FCFS至少提高55%，比MAXBID算法平均提高30%；其服务用户率、资源利用率都比FCFS和MAXBID算法有显著提高。

• 采用CNN和Bidirectional GRU的时间序列分类研究

  张国豪，刘波

  时间序列数据具有非离散性、数据之间的时序相关性、特征空间维度大等特点，当前大多数分类方法需要经过复杂的数据处理或特征工程，未考虑到时间序列具有不同时间尺度特征以及序列数据之间的时序依赖。通过结合卷积神经网络和循环神经网络中的双向门控循环单元，提出了一个新的端对端深度学习神经网络模型BiGRU-FCN，不需要对数据进行复杂的预处理，并且通过不同的网络运算来获取多种特征信息，如卷积神经网络在时序信息上的空间特征以及双向循环神经网络在序列上的双向时序依赖特征，对单维时间序列进行分类。在大量的基准数据集上对模型进行实验与评估，实验结果表明，与现有的多种方法相比，所提出的模型具有更高的准确率，具有很好的分类效果。

• GPU无锁跳步哈希表

  张娟，孙建伶

  由于GPU具有卓越的并行加速能力，将通用的内存索引结构应用于GPU成了一个新的研究方向。目前，针对GPU进行优化的支持并发访问且可动态更新的内存索引结构还比较少。提出一种支持并发访问且可动态更新的GPU无锁跳步哈希表（GPU lock-free hopscotch Hash table，GLHT），采用全局内存配合原子操作以及特定的并发控制策略，在实现并发访问和无锁特性的同时，保证了读操作的无等待特性。GLHT结合高效的GPU内存合并访问和warp协同工作共享策略，获得了很高的并行加速能力。与现有CPU跳步哈希表相比，具有4~9倍的性能优势；比采取预先分配内存的GPU无锁链式哈希表更加灵活，并且在写操作较重的工作负载中获得了更好的性能。

• NUMA架构下数据热度的内存数据库日志恢复技术

  吴刚，阿卜杜热西提·热合曼，李梁，乔百友，韩东红

  在内存数据库故障恢复技术中，命令日志是针对内存数据库设计的粗粒度的、轻量级的日志记录方式。但在非统一内存访问（non-uniform memory access，NUMA）体系架构下面向数据的数据库设计中利用命令日志进行故障恢复时，由于数据访问频率不均衡，导致负责高频数据恢复的CPU线程负载加重，而其他CPU相对空闲。针对这种工作负载不均衡所导致的恢复时间开销增大的情况，提出了NUMA体系架构下基于热度记录的内存数据库日志恢复算法。该算法中，每一条数据的访问次数作为该数据的热度记录下来。在并行恢复时，根据数据热度，将数据比较均衡地划分到各个节点的CPU线程执行恢复操作，以此来提高数据库的恢复速度。实验结果表明，该方案比NUMA架构下的常规恢复方案快，而且数据的热度越高，恢复速度的提升越明显，最高提升了19%。

• 扩展SysML支持需求追踪模型的自动生成

  邓刘梦，沈国华，黄志球，王飞，葛晓瑜

  安全关键系统广泛应用于航空、航天、核能、交通等领域，对安全性有着很高的要求。保障需求可追踪性是安全关键系统开发过程中的基本要求，也是各项安全性分析的重要前提。致力于建立需求与设计制品间的纵向追踪关系，采用模型驱动的方法来实现追踪模型的自动生成并实现追踪信息的图形化表达。首先通过配置文件的机制对SysML模型进行扩展，使用该扩展的SysML模型对需求以及设计制品进行建模用于捕获追踪信息。接着设计了一个追踪元模型用于表达以及存储追踪信息可供后期安全性分析使用，并使用模型转换技术实现从扩展的SysML模型到追踪模型的自动化生成。最后通过襟缝翼控制系统的案例来说明该方法的有效性。

• 基于状态图测试的迁移路径生成方法

  张毅伟，贲可荣

  计算机软件在军用装备中所占比重越来越大，软件质量的好坏决定着装备质量的高低，而软件测试则是提高软件质量的重要手段。UML状态图是一种广泛用于基于模型测试的建模方法，迁移覆盖是其中重要的测试覆盖准则。状态图中迁移之间的依赖关系会使得迁移路径不能按照输入序列来执行，从而导致覆盖率的下降，影响测试效果。为此，提出了一种改进的分组遗传算法来实现可执行迁移路径的自动生成，该算法通过合理设计编码方式和适应度函数来解决问题。算法在遗传操作中引入自适应的交叉和变异算子以及模拟退火机制来提高求解速度，加入修补算子对个体长度进行限制。实验结果表明，该方法能够在缩小遗传种群规模和减少遗传代数的基础上提高迁移覆盖率。

• BGRU:中文文本情感分析的新方法

  曹宇，李天瑞，贾真，殷成凤

  社交网络作为社会生活不可或缺的一部分，针对其产生的文本数据进行情感分析已成为自然语言处理领域的一个研究热点。鉴于深度学习技术能够自动构建文本特征，人们已提出CNN（convolutional neural network）、BLSTM（bidirectional long short-term memory）等模型来解决文本情感分析问题，但还存在结构较为复杂或训练时间较长等问题，而BGRU（bidirectional gated recurrent unit）能记忆序列的上下文信息，并且结构较为简单，训练速度较快。提出一种基于BGRU的中文文本情感分析方法，首先将文本转换为词向量序列，然后利用BGRU获得文本的上下文情感特征，最后由分类器给出文本的情感倾向。在ChnSentiCorp语料上进行实验，该方法取得了90.61%的[F1]值，效果优于CNN和BLSTM等模型，并且训练速度是BLSTM的1.36倍。

• 基于Convolutional-LSTM的蛋白质亚细胞定位研究

  王春宇，徐珊珊，郭茂祖，车凯，刘晓燕

  蛋白质亚细胞位置预测研究是目前蛋白质组学和生物信息学研究的重点问题之一。蛋白质的亚细胞定位决定了它的生物学功能，故研究亚细胞定位对了解蛋白质功能非常重要。由于蛋白质结构的序列性，考虑使用序列模型来进行亚细胞定位研究。尝试使用卷积神经网络（convolutional neural network，CNN）、长短期记忆神经网络（long short-term memory，LSTM）两种模型挖掘氨基酸序列所包含的信息，从而进行亚细胞定位的预测。随后构建了基于卷积的长短期记忆网络（Convolutional-LSTM）的集成模型进行亚细胞定位。首先通过卷积神经网络对蛋白质数据进行特征抽取，随后进行特征组合，并将其送入长短期记忆神经网络进行特征表征学习，得到亚细胞定位结果。使用该模型能达到0.816 5的分类准确率，比传统方法有明显提升。

• 改进的粒子群算法优化的特征选择方法

  李炜，巢秀琴

  特征选择是数据挖掘中数据预处理的一个重要步骤，因此选择出最优的特征子集可有效地降低学习算法的数据维度和计算成本。采用二进制粒子群优化算法（binary particle swarm optimization algorithm，BPSO）来对特征选择过程进行优化。提出基于特征聚类信息进行种群初始化的策略，其中特征的聚类由社团划分算法完成，并根据划分后的信息，在初始化过程中减少信息冗余，提高初始化种群的质量。提出一种基于决策空间相似性的自适应局部搜索策略，其中粒子的相似性指数由粒子在决策空间中的相似性确定。进化过程中，自适应地调整粒子进行局部搜索，避免算法早熟。最后，选择三种代表性的优化算法分别在11 个UCI数据集上进行对比实验。实验结果表明，改进后的BPSO算法得到的特征选择结果在降低特征数目方面明显优于其他对比算法，且分类精度也有显著提高。

• 融合生成对抗网络和朴素贝叶斯皮肤病诊断方法

  商显震，韩萌，孙毓忠，孙宇宁，陈旭，胡满满，梅御东

  不同皮肤病间发病率的差异导致了皮肤病数据类不平衡现象，对使用机器学习方法构建高效、准确的皮肤病诊断模型带来了巨大挑战。提出一种融合生成对抗网络（generative adversarial networks，GAN）和朴素贝叶斯的皮肤病二分类诊断方法：在皮肤病数据集上训练朴素贝叶斯二分类器作为诊断器，创新性地使用GAN为前者生成补充训练样本，使其训练集正负类样本达到平衡。针对皮肤病诊断多分类问题，提出一种融合生成对抗网络和朴素贝叶斯的多分类诊断方法：使用GAN和朴素贝叶斯训练皮肤病单病种二分类器，并结合了词频-逆文档频率算法（term frequency-inverse document frequency，TF-IDF），将多个二分类器组合成一个多分类器作为诊断器。与六种诊断方法进行了对比实验，提出的两种皮肤病诊断方法准确率和召回率均有提升。

• Takagi-Sugeno模糊系统双正则联合稀疏建模新方法

  林得富，王骏，张嘉旭，应文豪，王士同

  传统Takagi-Sugeno（T-S）模糊系统模型因模糊规则使用样本全部特征，导致模型的可解释性较差，冗余特征的存在还会导致模型的过拟合，降低模型的泛化性能。针对该问题，提出了一种模糊系统联合稀疏建模新方法L2-CFS-FIS（L2-common feature selection fuzzy inference systems），从而提高模型的泛化性能和可解释性。该方法充分考虑存在于模糊规则间的公共特征信息，同时引入模型过拟合处理机制，将模糊系统建模问题转化为一个基于双正则的联合优化问题，并使用交替方向乘子（alternating direction method of multipliers，ADMM）算法来进行求解。实验结果表明，该方法所构造的模糊系统不仅能够获得较为满意的泛化性能，而且通过有效地挖掘规则间重要的公共特征，可以确保模型具有较高的可解释性。

• 行人检测的深度稀疏自编码网络

  崔鹏，赵莎莎，范志旭

  针对传统卷积神经网络在行人检测中卷积速度慢、抗噪弱、冗余大的问题，提出了一种基于深度稀疏自编码网络的方法。首先在输入层后添加一层感兴趣层，在非相邻和相邻特征（nor-neighboring and neigh-boring features，NNNF）的基础上丰富图像的对称性特征，融合LUV空间、梯度方向等多通道的跨通道特征，并在非相邻特征设计的区域处理中采用一种改进的随机池化方法来消除行人形变的影响，得到表示行人信息的主要特征。然后利用四个自动编码器设计四层隐含层深度网络，以交叉熵为损失函数及改进的ReLU（rectified linear unit）函数为激活函数，以此结合稀疏表示的理论构建新的目标函数来学习网络，寻找数据的内在结构。最后用第四层隐含层输出的有效特征来训练分类器。在公共数据库上进行实验验证，结果表明，与现存的其他方法相比，该方法降低了平均漏检率，减少了运行时间，具有良好的鲁棒性。

• 核协同表示下的多特征融合场景识别

  宗海燕，吴秦，王田辰，张淮

  针对复杂场景识别中单一特征提供信息不充分这一问题情况，提出一种多尺度远距离点差值统计变换特征。通过Gabor滤波获得图像的多尺度特征信息，在像素图和滤波图上分别提取改进的远距离点差值统计变换特征，从而生成多尺度描述子，最后将多尺度统计变换特征和视觉词袋模型特征通过核协同表示融合后进行场景分类。该方法充分考虑了尺度信息和远距离点信息，解决了单一特征区分度低的问题。算法在两个标准数据集上进行对比实验，结果表明所提算法取得了较好的识别效果。

• 多尺度卷积特征融合的SSD目标检测算法

  陈幻杰，王琦琦，杨国威，韩佳林，尹成娟，陈隽，王以忠

  提出了一种改进的多尺度卷积特征目标检测方法，用以提高SSD（single shot multibox detector）模型对中目标和小目标的检测精确度。该方法先对SSD模型低层特征层采用区域放大提取的方法以提高对小目标的检测能力，再对高层特征层进行特征提取以改善中目标的检测效果。最后，利用SSD模型中原有的多尺度卷积检测方法，将改进的多层特征检测结果进行融合，并通过参数再训练以获得最终改进的SSD模型。实验结果表明，该方法在MS COCO数据集上对中目标和小目标的测试精确度分别为75.1%和40.5%，相比于原有SSD模型分别提升16.3%和23.1%。

• 区间值序信息系统中差别信息树的属性约简

  杨蕾，张晓燕，徐伟华

  属性约简是粗糙集领域的一个热门研究课题，而差别矩阵是获得属性约简的有效方法。然而，差别矩阵含有重复元素，增加了获得约简所需要的时间。差别信息树的提出解决了差别矩阵含有重复元素的问题，实现了对差别矩阵中非空元素的压缩存储。但是差别信息树是在等价关系下的差别矩阵的基础上提出的，并没有考虑序决策信息系统的情况。在区间值序信息系统的背景下提出了基于可分辨矩阵的差别信息树，解决了可分辨矩阵中存在冗余元素的问题，实现了对可分辨矩阵中非空元素的压缩存储。得到了该树的相关性质定理并对其进行了验证，并在此基础上给出区间值序信息系统的基于差别信息树的完备的属性约简方法。最后给出了实证分析，验证了该方法的可行性以及有效性。

• 基于优势关系的程度粗糙直觉模糊集模型研究

  薛占熬，吕敏杰，韩丹杰，张敏

  针对经典粗糙直觉模糊集理论仅考虑了集合中的最小/最大隶属度与非隶属度，而忽略了介于二者之间的隶属度与非隶属度的问题，从程度粗糙集的角度对其进行了分析研究。首先，将程度粗糙集引入到经典粗糙直觉模糊集模型中，定义了[μ(y)]和[ν(y)]，将其与最小/最大之间的隶属度与非隶属度的值比较。然后，构建新的下、上近似，提出四个模型，即基于优势关系的I型、II型程度粗糙直觉模糊集模型和基于优势关系的I型、II型双论域程度粗糙直觉模糊集模型，讨论这些模型的相关性质。这些模型的边界域缩小了，也降低了模糊熵值。最后，通过实例验证了模型的有效性。