小型微型计算机系统

Select

计算机软件与数据库研究

二叉树程序循环不变形状图的自动推断

李云龙(1,2)，罗奇鸣(1,2)，陈意云(1,2)

2017, 38(5): 913-918.

摘要 ( ) PDF全文 ( )

可视化

在一个基于形状图逻辑的C语言程序自动验证系统上，设计并实现了二叉树形状程序的循环不变形状图的自动推断方法.该方法与单链表程序循环不变形状图的推断方法的区别在于通过增加二叉树形状的等价和蕴含规则,使得在形状图的演算时支持二叉树中不确定方向的展开和折叠.此外，为了解决形状图变换规则变化给循环不变形状图推断带来的问题，还设计了算法用以判断在推断循环不变形状图的过程中是否使用新增的规则，并将判断算法融合到循环不变形状图推断流程中.本文方法使得系统支持自动推断二叉树指针程序的循环不变形状图.

Select

计算机软件与数据库研究

代码变更驱动的软件产品线演化方法

张薇(1，2)，吴毅坚(1，2)，沈立炜(1，2)，赵文耘(1，2)

2017, 38(5): 919-924.

摘要 ( ) PDF全文 ( )

可视化

软件产品线由一组共享了核心资产并具有可变性的相似产品组成.现实的软件产品线开发往往会出现新产品，导致软件产品线开发的管理困难.同时，这种基于特定产品的代码变更对现有的其他产品可能也是有效的，因此可以用于推动整个软件产品线的演化.提出一种通过分析代码变更驱动软件产品线演化的方法.首先进行已有代码的差异比较，得到不同产品之间的程序代码模块结构的差异；然后通过启发式规则对特征模型进行变更；最后基于变更后的特征模型和追踪关系，对核心资产代码提出重构建议，从而驱动软件产品线的演化.另外，本文通过实际的产品实例说明了该方法的应用过程，证明了方法对于实际的软件产品线是有效的.

Select

计算机软件与数据库研究

关于断言语言中引入逻辑变量的研究

李为胜，罗奇鸣，陈意云

2017, 38(5): 925-929.

摘要 ( ) PDF全文 ( )

可视化

基于Hoare逻辑推理规则去验证程序安全性的研究是程序验证领域的重要发展方向.但是在Hoare逻辑中，仅依靠程序变量的断言语言无法表达程序上下文中不变性质.本文研究通过在断言语言中引入逻辑变量的方式来表达程序上下文不变性质，同时详细介绍了引入逻辑变量带来的问题以及给出解决问题的途径，最后以带逻辑变量的平衡二叉树插入程序为例展示了引入逻辑变量的作用.

Select

计算机软件与数据库研究

去重环境下基于元数据分类的贪婪预取型数据恢复

杨儒1，邓玉辉(1,2),魏文国3

2017, 38(5): 930-935.

摘要 ( ) PDF全文 ( )

可视化

数据备份的目的就是为了恢复.由于逻辑连续的数据被物理分散在不同的磁盘位置，传统的去重方法产生的碎片严重影响了系统的恢复性能.之前存在的一些优化方法都是尝试在备份时利用重写算法来改进后期的恢复性能，然而重写算法自身存在的弊端就是必须以牺牲去重率的代价来获得更好的数据恢复性能，最终导致浪费磁盘空间的结果.并且传统的方法在备份完成后只会生成一份备份元数据以便后期恢复，导致系统在恢复过程中频繁地低效率访问磁盘上的元数据.本文提出将备份元数据分类组织成文件元数据和块元数据，在不牺牲系统去重率和充分利用硬件资源的前提下，通过对元数据更加激进式的预取来有效提高恢复性能和吞吐量.关于本文系统的恢复性能的实验评估是基于真实的数据集，实验表明：相比基于历史感知和基于内容的重写算法所获得的恢复性能，基于元数据分类的数据恢复分别在平均节约了1.91%和4.36%的去重率的情况下，获得了27.2%和29.3%的恢复性能提升.

Select

计算机软件与数据库研究

栈指针程序的形式验证

冯峰(1，2)，罗奇鸣(1，2)，陈意云(1，2 )

2017, 38(5): 936-940.

摘要 ( ) PDF全文 ( )

可视化

提出一种验证含栈指针、静态区指针操作的C语言程序的方法.该方法定义指针的三元属性表示一个指针的状态.指针的三元属性包括指针指向数据块的名称、数据块的长度以及指针在所指向数据块上的偏移.通过对Hoare逻辑的扩展，基于指针的三元属性设计了相应的断言演算规则和演算过程中生成验证条件的方法.该方法可以解决访问路径别名判断、指针越界访问检查、非法指针解引用检查等问题.该方法已经在一个基于演绎推理的安全C语言验证系统中实现，并且成功验证了教材上常用的一些经典算法.

Select

计算机软件与数据库研究

MapReduce架构下的大规模轨迹数据压缩策略

姚楠，彭敦陆

2017, 38(5): 941-945.

摘要 ( ) PDF全文 ( )

可视化

车辆GPS轨迹数据中蕴含的轨迹信息具有重要的理论和应用价值.随着生活水平的日益提高，越来越多的汽车都配备了GPS设备，海量的GPS轨迹数据随之产生.为了减少车辆轨迹数据的存储空间，提高数据传输和数据分析速度，提出一种MapReduce架构下的大规模轨迹数据压缩策略.该策略首先提出一种基于综合时空特征的开放窗口轨迹数据压缩方法，再结合MapReduce并行计算模型，在各节点上并行压缩大规模轨迹数据.实验结果表明，本文提出的轨迹数据压缩策略虽然在压缩率上略有下降，但是保留了轨迹特征，减少了压缩误差，提高了压缩速度.

Select

计算机软件与数据库研究

面向群组的社交follow推荐方法研究

谷鹏，李琳，苏畅，袁景凌

2017, 38(5): 946-950.

摘要 ( ) PDF全文 ( )

可视化

目前社交网络中的推荐方法主要是针对单个的个体用户，然而随着日益频繁的社交活动，若干相关用户自然形成了群组，研究如何对于整体的群组用户进行推荐的问题引起了国内外学者的兴趣.本文在优化和改进面向个体的社交follow关系推荐算法的基础上，提出基于矩阵分解和混合策略的群组用户推荐方法.首先，对社交媒体微博中用户-项目矩阵进行奇异值（SVD)分解，然后提出在SVD中加入用户的社交行为和社交关注关系特征，并用随机梯度下降（SGD)算法优化对个体用户推荐的预测评分.其次，在获得个体的推荐评分基础之上，设计一种混合融合策略，该策略融合群组中个体成员的推荐评分形成对该群组的整体评分，从而实现对于群组用户的推荐.最后，实验采用KDDCUP2012竞赛 Track1的数据，以平方根误差为评估指标，对比个体推荐中传统SVD模型和本文提出的SVD优化模型，并进一步对比本文提出的混合融合策略与传统的最大满意度、平均满意度及最小忍耐度三种单一融合策略.实验结果表明SVD优化模型优于传统SVD模型，并且采用混合的策略要优于单一的群组融合策略.总体上，本文提出的推荐方法能够有效提高群组推荐的准确度.

Select

计算机软件与数据库研究

融合用户信任的协同过滤推荐算法

李良1，董宇欣1，赵春晖2，程伟杰1

2017, 38(5): 951-955.

摘要 ( ) PDF全文 ( )

可视化

针对协同过滤推荐算法中存在的准确率较低、数据稀疏等问题，提出基于用户信任的协同过滤推荐算法，算法包含计算用户之间评分信任度和偏好信任度2个部分.对于用户项目评分矩阵中的用户间共同评分项目，综合考虑共同评分项目的数量以及其在所有评价项目中所占的比例，并与用户评分相似度结合，建立非对称的评分信任矩阵，计算用户评分信任度.对于非共同评分项目，利用项目自身的标签信息以及用户评分权重，计算用户偏好信任度.然后算法将评分信任度和偏好信任度线性加权融合.最后在真实数据集上与相关算法进行实验对比，实验结果表明，提出的算法在推荐的准确率以及评分预测上取得了较好的效果.

Select

计算机软件与数据库研究

满足非重叠条件的带有通配符序列模式挖掘

谢飞(1，2)，强继朋(2 )

2017, 38(5): 956-960.

摘要 ( ) PDF全文 ( )

可视化

很多应用领域产生大量的序列数据，例如：基因序列，超市购买记录，股市交易数据，文本序列等.如何从这些序列数据中挖掘具有重要价值的模式已成为序列模式挖掘研究的主要任务.本文研究带有通配符的序列模式挖掘问题，给定支持度阈值和间隔约束，从序列数据库中挖掘所有出现次数不小于给定支持度阈值的频繁序列模式，模式中任意两个相邻元素在序列中的出现位置满足用户定义的间隔约束.本文设计一种基于层次图的带有通配符序列模式挖掘算法PMLG，利用层次图结构在多项式时间和空间复杂度内构建和存储模式在序列中满足间隔约束的所有出现位置，采用深度优先搜索策略对图进行遍历，计算模式的支持度，其中模式的任意两次出现的相同位置都不共享序列中同一位置的字符，即满足非重叠出现.在生物DNA序列上的实验表明，PMLG比相关的序列模式挖掘算法具有更好的时间性能和完备性.

Select

计算机软件与数据库研究

基于正负反馈的SVM协同过滤Top-N推荐算法

张宇1，王文剑(1，2)，赵胜男(1)

2017, 38(5): 961-966.

摘要 ( ) PDF全文 ( )

可视化

经典的Top-N推荐算法利用用户正反馈信息对全部项目进行排序，然后选择前N个项目推荐给用户.针对经典推荐算法未充分利用用户负反馈信息的问题，提出基于正负反馈的SVM协同过滤（SVM Collaborative Filtering based on Positive and Negative Feedback，PNF-SVMCF)Top-N推荐算法，充分利用用户负反馈信息过滤测试集中用户可能不喜欢的项目，只对测试集中剩余的项目进行Top-N排序.PNF-SVMCF算法过滤用户可能不喜欢的项目，这样可以缩减需要排序的项目规模，提升推荐效率；同时去除这些项目对排序的干扰，提高推荐精度.在MovieLens数据集上的实验结果表明，该方法具有良好的推荐速度和精度，特别是在较少的推荐项目情况下，能够表现出更好的推荐精度.

Select

计算机软件与数据库研究

不一致性进化特征选择方法

翟俊海1，刘博2，张素芳3

2017, 38(5): 967-971.

摘要 ( ) PDF全文 ( )

可视化

特征选择是机器学习中重要的数据预处理步骤，它从原始特征集合中，选择一个重要的子集，以改进学习系统的性能或降低学习系统的计算复杂度，对学习系统的性能有重要的影响.针对离散值特征选择问题，提出一种基于遗传算法的特征选择方法.该方法利用遗传算法搜索最优或次优特征子集.具体地，利用二进制数对问题的解编码，利用不一致性度量作为适应度函数.实验结果显示本文提出的特征选择方法是行之有效的.提出的方法具有如下三个特点：1)简单且易于实现；2)测试精度较高；3)可解释性强.

Select

计算机软件与数据库研究

支持三级缓存的移动小组域实时协同模型研究

杨宗宪1,邬春学(1,2), 高丽萍(1,2),朱思征3,王山山3

2017, 38(5): 972-976.

摘要 ( ) PDF全文 ( )

可视化

经研究发现,现有的协同理论研究过程中大多有一个严重缺陷,即都是假设在乐观网络环境下进行的协同研究.研究了移动网络环境下的实时协同模型.模型通过将协作域划分成多个小组,并在每个小组中选举出超级节点,构成了“注册服务器—超级节点—协同节点”这个基于三级缓存的移动协同P2P网络模型.模型通过使用ABST快速操作转换算法对本地积累的大量离线操作进行预处理来提高整个协作域的协作效率.同时本文讨论了（1)新加入的协同节点分组问题;（2)小组域中后备超级节点选举问题;（3)协作小组及超级节点的动态维护问题;并给出了相应解决方案.根据协作域中不同节点工作状态不同的特点,提出了最优资源分配的缓存一致性维护策略.最后对模型的效率和可靠性进行分析.实验结果分析表明该模型提升了协同系统的生存性和可靠性,同时也确保了整个协作域有较高的协同效率.

Select

计算机软件与数据库研究

数据挖掘中的一种次优化动作知识提取方法

吕强，李兆荣，陈崚，朱留存

2017, 38(5): 977-982.

摘要 ( ) PDF全文 ( )

可视化

到目前为止，尽管数据挖掘研究已取得了惊人的进展，特别是已达到很高的泛化精度和效率，但是在从模型中提取有意义的决策行动方面仍然只有有限的进展.然而，在许多应用中，如客户关系管理等，用户不仅需要准确预测的模型，也期望能够得到一些建议的行动.提出一种从随机森林模型提取次优化动作知识的方法.其基本思想是首先将提取动作知识问题形式化为一个优化问题，然后证明该问题等价于状态空间搜索中最短路径搜索问题，并提出一种次优化状态空间搜索算法来求解该问题.实验结果表明，该次优化算法在求解效率和提取的动作知识质量上达到了很好的平衡.

Select

计算机软件与数据库研究

改进密度峰值支撑点选取及其在度量空间离群检测的应用

许红龙(1,2),唐颂3,毛睿1,陈国良1,刘刚(1)

2017, 38(5): 983-987.

摘要 ( ) PDF全文 ( )

可视化

基于支撑点的度量空间离群检测算法旨在尽快提高离群度阀值,以达到快速检测离群点的效果.然而现有的相关算法缺乏有效的支撑点选取方法,造成支撑点选取结果不稳定,最终导致算法性能波动较大.应用于聚类的密度峰值算法不失为一种良好的支撑点选取算法,然而其密度峰值搜索目标难以确定.通过改进密度峰值算法,通过自动确定距离值,计算该范围内对象的数量来确定密度峰值,从而选取出具有最大密度的支撑点,应用于度量空间离群检测之中.实验结果表明该算法较已有算法获得较大的提升,平均加速比为2.41,最高达6.28;距离计算次数平均减少60.67%,最高达91.17%,而建立索引所需时间在可接受范围内.

Select

计算机网络与信息安全

不完全类超立方体网络的可诊断性

陈琪1，樊建席1，韩月娟2，林政宽1

2017, 38(5): 988-991.

摘要 ( ) PDF全文 ( )

可视化

可诊断度是衡量一个互连网络可靠性的重要指标，用来评估当系统中某些顶点出现故障时该系统可以准确找出故障顶点的能力.PMC模型是并行计算机系统中的一种经典的可诊断模型，被广泛地应用于系统诊断，目前已有大量的基于PMC模型的系统诊断性质研究.类超立方体是一种重要的网络拓扑结构，有很多很好的性质，其中超立方体网络在实际中得到了广泛应用.研究者们针对类超立方体网络存在坏边或者硬故障顶点时系统可诊断度进行了研究，对同时存在两种故障情形下的可诊断度还没有相关研究.设是一个-维类超立方体网络，本文证明对于坏边和硬故障顶点的集合S，若|S|≤n-1且，则Hn-S在PMC模型下的系统可诊断度是δ(Hn-S)，其中δ(Hn-S) 表示Hn-S的最小顶点度数.

Select

计算机网络与信息安全

TRUP-Vivaldi:具有均衡精确度的时延预测算法

张佳庚，韩博，谭薇，朱晓芒

2017, 38(5): 992-996.

摘要 ( ) PDF全文 ( )

可视化

由于Overlay网络中反三角现象和不等距映射的影响导致网络时延预测存在困难.传统Vivaldi算法坐标收敛速度慢且预测精度不高不稳定，提出一种具有均衡精确度TRUP-Vivaldi时延预测算法.TRUP-Vivaldi分析时延非对称和网络反三角现象的原因，针对Vivald算法建立反三角检测和抑制机制，定义检测系数修正不等距误差反三角造成的影响；从节点距离计算出发设置多个参考节点，动态调整更新参数，修正非对称带来的长短距预测精度不均，均衡长短距离链路预测准确度.仿真证明，该算法比传统Vivaldi算法的预测精度更高，且预测误差稳定.

Select

计算机网络与信息安全

一种故障节点再利用NoC容错路由算法

吴凤阳,刘勤让

2017, 38(5): 997-1001.

摘要 ( ) PDF全文 ( )

可视化

构建一种微细粒度故障模型，有效地区分链路故障和通道故障，并在该模型的基础上提出一种基于故障节点再利用的容错路由算法.本算法由一个动态暂存机制（dynamic pseudo-receiving mechanism,DPR)和动态转向控制（dynamic turn management,DTM)构成，分别用于暂存数据包和避免死锁.最后实验结果表明，本文算法较先前的容错算法，时间延迟降低27%，吞吐量提高21%.尤其在数据包注入率增大时，本文方案有着明显的优势，保证了网络的可靠性.

Select

计算机网络与信息安全

面向探索式服务组合场景的即时服务推荐方法研究

张艳梅1,雷霆霈1,曹怀虎1,丁熠2

2017, 38(5): 1002-1006.

摘要 ( ) PDF全文 ( )

可视化

探索式服务组合是针对复杂问题进行业务构造的一种服务计算模式，在这种半自动的服务组合环境下，准确高效的服务推荐技术是提升用户业务构造体验的重要方法.然而现有的主流服务推荐技术虽然对初始服务推荐具有很好的效果，但不适用于后继服务的推荐.鉴于后继服务的准确推荐对于用户进行业务构造具有的重要影响，提出一种适用于后继服务推荐的即时推荐方法，该方法首先利用Jaccard相似度算法和物质扩散算法对服务关联度进行计算，然后基于关联度来进行后继服务推荐，并在此基础上设计了单步和多步后继服务推荐策略.最后，基于Programmable Web网站的真实数据实验表明，本文提出的即时服务推荐方法能够比较有效的应用于探索式服务组合场景.

Select

计算机网络与信息安全

对两种密钥协商协议的分析与改进

秦艳琳，吴晓平

2017, 38(5): 1007-1012.

摘要 ( ) PDF全文 ( )

可视化

对Chen所提的一种基于身份的多重认证密钥交换协议和一种无证书双方认证密钥协商协议进行了安全性分析，证明其提出的基于身份的多重认证密钥交换协议除了存在基于身份公钥密码体制固有的密钥托管问题之外，还不能满足前向安全性；不使用对的无证书双方认证密钥协商协议也无法抵抗无证书公钥密码体制安全模型中A(II)类型敌手的攻击.由此，基于椭圆曲线密码体制分别提出新的无证书多重和单重认证密钥交换协议，证明新方案满足已知密钥安全、完美前向安全、抗临时密钥泄漏、抗假冒攻击及抗中间人攻击等安全特性.效率分析表明，新方案在确保安全性的同时具有较高的运算效率.

Select

计算机网络与信息安全

利用符号OBDD-LIST设计批处理包过滤防火墙

徐周波，陈帅，常亮，古天龙

2017, 38(5): 1013-1016.

摘要 ( ) PDF全文 ( )

可视化

为解决包过滤防火墙规则数目不断增加导致的存储空间膨胀和过滤速度降低的问题，提出一种基于有序二叉决策图与线性列表的混合结构（OBDD-LIST)的批处理包过滤防火墙算法.首先依据规则各域的特征属性对规则筛选分类，并使用位级别压缩的方式重新设计防火墙的规则库；然后基于连续传入的数据包包头信息具有相似性的特征，利用有序二叉决策图无冗余、无回溯的优势，采用批处理的思想过滤数据包；最后，通过开源软件ClassBench生成的高仿真数据包进行了仿真实验，证明本文算法在存储空间、匹配速率上具有较大的优势，有效提高了防火墙的性能.

Select

计算机网络与信息安全

DV-Hop辅助的改进蒙特卡罗盒定位算法

吉训生，吴卫

2017, 38(5): 1017-1021.

摘要 ( ) PDF全文 ( )

可视化

针对无线传感器网络中，以蒙特卡罗为基础的移动传感节点定位算法在定位精度和采样效率方面的不足，提出一种DV-Hop辅助的改进蒙特卡罗盒定位算法.通过利用DV-Hop方法获得节点间的真实距离来建立更加精确的锚盒；引入节点随机运动模型，获得节点真实运动速度来优化采样区域，提高定位精度；根据样本到一跳、两跳锚节点的估计距离和真实距离的差值来动态赋予样本不同的权值，提高采样效率.仿真结果表明，当锚节点和未知节点都移动时，所提出算法的定位精度和采样效率与同等条件下的蒙特卡罗盒算法相比均有所提高.

Select

计算机网络与信息安全

多虚拟机动态迁移情景下的服务功能链调整方法

古英汉1，伊鹏2

2017, 38(5): 1022-1027.

摘要 ( ) PDF全文 ( )

可视化

基于CR/TR-Motion虚拟机动态迁移模型，研究了虚拟功能服务链中多虚拟机动态迁移对虚拟功能的影响，用统计和博弈论的方法设计了服务链动态调整算法.介绍了基于日志跟踪与重现的虚拟机动态迁移，在此基础上分析建立多虚拟动态迁移模型，给出了迁移时间和迁移代价函数，并依此给出服务链开销函数.然后基于可迁移概率和博弈信息论方法给出了最小开销算法和最小迁移步骤优化算法.最后给出了多虚拟机迁移模型和服务链迁移算法的测试数值结果.

Select

计算机网络与信息安全

优先级调度下的无人机自组网数据可靠传输跨层方法

方堃，茹乐，于云龙，贾旭峰，刘树光

2017, 38(5): 1028-1033.

摘要 ( ) PDF全文 ( )

可视化

在无人机自组织网络中，为了实现射频隐身，确保大量不同优先级数据的可靠传输.提出一种MAC层与网络层协同设计的优先级调度的数据传输方法，在MAC层，通过优先级调度机制控制不同优先级数据的传输顺序，通过ACK分组优化无人机自适应功率控制流程；在网络层，通过能耗和传输平衡机制完善无人机编队间大量优先级数据传输的路由选择过程.仿真结果表明，此方法能够有效提高无人机自组织网络的平均吞吐量，降低能耗、平均时延、标准化路由负载.

Select

人工智能与算法研究

一种基于网格的密度峰值聚类算法

王飞，王国胤，李智星，彭思源

2017, 38(5): 1034-1038.

摘要 ( ) PDF全文 ( )

可视化

针对密度峰值聚类算法由于时空复杂度高而不能对大数据集进行有效聚类的问题，提出一种基于网格的密度峰值聚类算法.首先通过自适应多分辨率的网格划分的思想把数据划分到多个网格空间中，然后在每个网格空间中进行密度峰值聚类，利用网格边界合并网格空间中的聚类结果，从而得到原始数据集的聚类结果.本算法集成了网格聚类和密度峰值聚类算法的优点，网格的方法可以减少算法空间复杂度和算法计算量，进而降低了密度峰值聚类算法的时空复杂度.仿真实验结果表明，本算法能够有效处理数据聚类问题，并提高了传统算法的效率.

Select

人工智能与算法研究

一种协作群智感知任务分配的贪心算法

程如洪，肖明军

2017, 38(5): 1039-1043.

摘要 ( ) PDF全文 ( )

可视化

关于群智感知的任务分配算法，目前已有若干研究.然而，现有的研究很少涉及到群智感知中需要多人协作的复杂感知任务，本文则对这一类任务进行研究.首先，展示了一个与位置相关的协作群智感知任务分配问题，并对其展开形式化分析;然后，证明了该问题为NP难解问题，并针对这一问题提出了一个基于贪心策略和最小加权集合覆盖的任务分配算法；最后，用多个算法通过实验作比较，证明了所提算法的优越性.

Select

人工智能与算法研究

一种鲁棒性增强的LambdaMART算法

李金忠(1,2,3,4),刘关俊(1,2)

2017, 38(5): 1044-1048.

摘要 ( ) PDF全文 ( )

可视化

鲁棒性在排序学习中显得越来越重要，而现有排序学习算法多数仅关注改进排序模型的有效性，往往忽略了排序模型的鲁棒性.为了增强排序模型的鲁棒性，在训练排序模型的过程中可同时考虑其有效性和鲁棒性.从一个新颖的视角，即偏差-方差均衡，研究了如何优化LambdaMART排序学习的有效性和鲁棒性均衡.将偏差和方差融合为一个统一的目标函数以修改LambdaMART算法中的梯度，并证明了修改后的梯度仍可采用LambdaMART算法去优化以训练排序模型.最后，在排序学习数据集上的实验结果表明，基于偏差-方差均衡思想所修改梯度后的LambdaMART算法具有更强的鲁棒性.

Select

人工智能与算法研究

拐点估计的改进谱聚类算法

张嘉琪(1,2),张红云(1,2)

2017, 38(5): 1049-1053.

摘要 ( ) PDF全文 ( )

可视化

针对现有谱聚类算法不稳定，处理复杂分布数据较困难，需要手动输入聚类个数的问题，利用基于快速搜索和密度峰的聚类算法CFSFDP(Clustering by Fast Search and Find of Density Peaks)，提出一种改进的谱聚类算法.本算法首先借鉴基于流形距离核的谱聚类算法计算数据的低维嵌入，将分布复杂或者类内不存在密度极值点的数据转换成类球状的低维嵌入代表点.接着，提出用CFSFDP算法代替基于流形距离核的谱聚类算法中Kmeans算法对低维嵌入进行处理.最后，基于CFSFDP算法的局部密度和距离属性的概念，提出拐点估计方法来自动确定聚类个数，获取聚类结果.实验表明，针对复杂分布的测试数据集，本算法能准确地确定聚类个数，获得很好的聚类效果，同时本算法需要输入的参数较少，且在一定范围内表现出较强的鲁棒性.

Select

人工智能与算法研究

基于有效距离的迭代特征选择

张丹,刘明霞,张道强

2017, 38(5): 1054-1058.

摘要 ( ) PDF全文 ( )

可视化

作为一项重要的降维技术，特征选择在模式识别和机器学习领域已经成为一个研究热点.现有的特征选择方法中，人们通常利用欧氏距离计算样本之间的相似性，而欧氏距离仅能反映样本之间的静态特性.最近，研究人员提出一种有效距离的概念，并证明有效距离可以反映出样本之间潜在的动态结构.因此提出一系列基于有效距离的迭代特征选择方法.具体地，本文首先根据稀疏表示算法计算有效距离.然后，根据得到的有效距离提出了三种新的迭代的特征选择方法，包括基于有效距离的迭代Laplacian Score算法（IterativeEDLS)和两种基于有效距离的迭代Sparsity Score算法（IterativeEDSS-1和IterativeEDSS-2).为验证本文提出方法的有效性，在十个UCI数据集上进行了分类的实验.实验结果表明，本文提出的基于有效距离的迭代特征选择方法比传统的基于欧氏距离的方法能取得更好的分类结果.

Select

人工智能与算法研究

一种基于最小距离的量子k-means算法

周晓彦(1，2 )，安星星(1，2),刘文杰3，嵇福高(1，2)

2017, 38(5): 1059-1062.

摘要 ( ) PDF全文 ( )

可视化

k-means算法以其简单和快速的特点而被广泛地应用，但其计算复杂度随着数据维数呈指数级增长.通过采用量子比特来表示空间中的点，提出一个高效的基于距离最小化原则的量子k-means算法，相比经典k-means算法，该算法能够带来指数级加速.为了计算待分类点与聚类中心之间距离，通过增加一个辅助粒子构造聚类中心与待分类点的纠缠态，并对辅助粒子进行投影测量，进而依据测量结果计算出两点之间距离.算法的目的是将待分类的点按距离最小原则分到相应的聚类中.算法中，需随机选择k 个点作为初始聚类中心，在接下来的迭代过程中，不断地更新聚类中心，直到聚类中心不再变化或小于指定的阈值，则迭代结束.

Select

人工智能与算法研究

面向函数优化的社会学习优化算法

刘志中,秦靖萱,宋成,薛霄,郭海儒

2017, 38(5): 1063-1069.

摘要 ( ) PDF全文 ( )

可视化

社会学习优化算法范型 (Social Learning Optimization Algorithm Paradigm,SLO)是一种模拟人类社会智能演化过程的新型群体智能算法，该算法由三层协同进化的空间(微空间、学习空间、信仰空间)构成，其三个协同演化空间形成一个完整的闭环，符合人类社会智能演化的自然规律.SLO算法的模拟对象是具有最高智能水平的人类社会，具有较好的优化机理.然而，目前还不存在用于求解函数优化问题的SLO算法，针对这一问题，本文设计了面向函数优化问题的操作算子(主要包括交叉变异操作、模仿学习操作、观察学习操作)，形成了面向函数优化问题的算法（F-SLO).最后,通过标准的测试函数与其他智能算法进行了比较，实验结果表明，本文所提出的面向函数优化的F-SLO算法在求解函数优化问题时具有较好的性能.

Select

人工智能与算法研究

一种Yarn框架下的异步双随机梯度下降算法

杨双涛，马志强，窦保媛，张力

2017, 38(5): 1070-1075.

摘要 ( ) PDF全文 ( )

可视化

针对异步随机梯度下降算法在多核系统和主/从集群环境中的通信冲突问题，提出了异步双随机梯度下降算法.该算法主要通过离散各从节点在梯度求解时的计算量，分散各从节点对主节点的通信请求，有效减少模型训练过程中通信冲突次数，从而加快模型的训练速度；在Hadoop Yarn基础上提出了异步并行计算框架，进行了异步随机梯度下降算法以及异步双随机梯度下降算法的快速求解；在多核系统和Hadoop环境下，基于HIGGS数据集进行了异步随机梯度下降算法和异步双随机梯度下降算法的对比实验，结果表明，在保证模型准确率的前提下，异步双随机梯度下降算法比异步随机梯度下降算法具备更快的训练速度.

Select

人工智能与算法研究

资源受限周期任务低能耗调度算法

张忆文1，王成1，郭锐锋2

2017, 38(5): 1076-1080.

摘要 ( ) PDF全文 ( )

可视化

针对资源受限的周期任务模型，提出资源受限周期任务低能耗调度（RCPTLPSA)算法.该算法不仅考虑处理器通用功耗模型，而且考虑任务执行时间与处理器速度成非线性关系的情形.此外，该算法利用动态电压调节技术和动态功耗管理技术降低系统能耗.在给出RCPTLPSA算法的必要条件之后，通过实验验证该算法的性能.实验结果表明RCPTLPSA算法比现有算法平均节约大约55.37%的能耗.

Select

人工智能与算法研究

一种优化的带偏置概率矩阵分解算法

王建芳，张朋飞，谷振鹏，刘冉东

2017, 38(5): 1081-1085.

摘要 ( ) PDF全文 ( )

可视化

针对个性化推荐过程中高维稀疏性引起的数据震荡和推荐精度不高的问题，提出一种通过交替最小二乘算法（Alternating Least Squares，ALS)来优化的带偏置概率矩阵分解的推荐方法.首先将用户项目的偏置信息融入到改进的概率矩阵分解算法中.其次为了提升训练速度和推荐精度，将训练得到的用户项目潜在因子向量作为ALS的初始值，进而得到用户项目潜在因子矩阵.最后利用分解后的两个低维矩阵对原矩阵中的未知评分进行预测.在Movielens100k数据集上的实验结果表明，本文提出的推荐算法在相对于传统的带偏置概率矩阵分解来说最高提高3.41%，结果稳定且准确率高.

Select

图形与图像技术研究

特征敏感的点云重采样算法

陈永辉，岳丽华

2017, 38(5): 1086-1090.

摘要 ( ) PDF全文 ( )

可视化

针对原始点云数据采样不均匀，数据缺失等问题，提出一种基于特征敏感的点云重采样算法.该算法首先运用主成分分析法获得点云的初始法向量，将高斯映射和空间密度权重相结合，自适应地将点云划分为特征点和非特征点；其次，采用各向异性的相邻点优化特征点的拟合平面，提高特征点的法向量准确度；在此基础上，通过带空间权重的投影插值算法和在加权局部最优投影（WLOP)算法中引入法向权重，实现了特征保持的点云均匀采样.实验结果表明：与经典WLOP算法相比，该算法在均匀采样的同时，能够以较高的压缩率对点云向下采样并保持点云特征，向上采样时可以对缺失点云进行有效修复，有利于点云数据的后续处理.

Select

图形与图像技术研究

基于多粒度划分的图像语义检索方法

徐久成，董婉，王煜尧

2017, 38(5): 1091-1097.

摘要 ( ) PDF全文 ( )

可视化

为了提高在图像数据库中图像检索的准确性和检索速度，提出一种基于多粒度划分的图像语义检索方法.首先，根据图像数据库和语义标注词构建图像信息表；其次，使用改进的多粒度规则提取方法提取图像信息表的规则集，根据规则集对应的对象集将图像数据库划分为不同的图像粒集，建立图像语义特征索引；然后，提出了基于内涵重要度的图像相似性度量公式和基于知识粒的图像语义检索算法；最后，用Corel图像库中的图像作为测试图像库进行仿真实验，结果表明该方法有效地提高了图像的检索效率.

Select

图形与图像技术研究

结合波段选择和保边去噪滤波的高光谱遥感图像分类

王巧玉，陈锻生

2017, 38(5): 1098-1102.

摘要 ( ) PDF全文 ( )

可视化

高光谱遥感图像分类是遥感图像在众多领域得以有效应用的基础.为了提高其分类精度，提出一种结合波段选择和保边去噪滤波的分类方法.通过波段选择对高光谱数据进行降维同时保留了光谱的物理信息；然后通过对各波段图像进行保边去噪滤波将空间信息和光谱信息结合起来；最后选取结合了空间信息的光谱曲线作为由堆栈降噪自编码器加Softmax分类器构成了深度学习网络的输入，对其进行特征提取及分类.波段选择去除了一些对分类不利的波段，保边去噪滤波将空间信息与光谱信息结合了起来，深度学习提取特征避免了手动选择特征的主观臆断，通过在Indian Pines和Pavia University数据集上的实验，结果表明本文算法分类精度高、稳定性好.

Select

图形与图像技术研究

一种初始分割和区域合并的交互式图像分割方法

甘玲(1，2)，郭千文1，朱林华1

2017, 38(5): 1103-1106.

摘要 ( ) PDF全文 ( )

可视化

针对全自动分割很难从图像中自动获取目标、提取边缘不理想等不足，提出一种基于SLIC超像素初始分割和区域合并的交互式图像分割方法.首先采用SLIC超像素进行初始分割；针对单一的颜色特征不能较好地提取区域的特征信息，再采用由颜色直方图和轮廓波变换构成的区域相似性特征来进行区域特征的提取；最后通过改变区域合并策略，采用分层匹配机制对区域合并顺序进行调整，以降低合并过程中出现的误匹配.实验结果表明，该方法不但提高了分割速度，而且分割的准确率（ACC）也有所提升，同时降低了分割的负率度量（NRM）.

Select

图形与图像技术研究

扩展粒子系统实时绘制逼真的龙卷风

吕梦雅，陶建新，唐勇，张思

2017, 38(5): 1107-1110.

摘要 ( ) PDF全文 ( )

可视化

龙卷风模拟一直是计算机图形学的热点之一，龙卷风的漩涡控制以及交互性尤其具体有挑战性.首先，为使粒子系统的粒子旋转起来，引入漩涡场，使得粒子在漩涡场作用下产生旋转效果；其次，在龙卷风的最外层添加一层高速旋转的透明的刚体，借助碰撞检测算法，将龙卷风与大物体的交互转化为刚体和物体的交互；然后，在光线投射算法生成纹理数据之后，给纹理数据进行光晕、太阳光等处理，采用GPU并行加速机制提高模拟实时性，模拟出逼真绚丽实时的龙卷风；最后，设计多组龙卷风以及龙卷风的交互实验实例，完成不同形态龙卷风及其交互效果验证.

Select

图形与图像技术研究

改进HFT模型及其在图像分类中的应用

刘尚旺，胡剑兰，崔艳萌

2017, 38(5): 1111-1115.

摘要 ( ) PDF全文 ( )

可视化

为降低图像分类数据的冗余性以提高图像分类的准确率，提出一种改进HFT（Hyper complex Fourier Transform)模型并进行图像分类.首先，利用提出改进HFT得到视觉显著图.1)超复数图像的三个虚部系数由R，G，B替换为L'，a'，b'，而实部系数为调整后的亮度值；2)通过傅里叶变换原始相位谱和滤波后幅度谱重构二维图像，不同的尺度空间得到多个候选显著图；3)引入标准差和对比函数，得到视觉显著图.其次，分别提取显著图的PCNN（Pulse Coupled Neural Network)时间签名特征以及纹理特征.最后，利用提取的图像特征作为SVM（Support Vector Machine)的输入向量，进行图像多分类.实验结果表明，本文方法在SIMPLIcity图像测试集上的分类准确性达到了95.04%，在Caltech测试集分类准确性达到了95.23%，提高了图像分类的准确率.

Select

图形与图像技术研究

一种改进的非线性加权图像拼接融合方法

王凯1，陈朝勇1，吴敏1，姚辉1，张翔2

2017, 38(5): 1116-1120.

摘要 ( ) PDF全文 ( )

可视化

为解决多路高清视频图像拼接融合的质量和处理时间，在分析多频带图像融合算法的思路上，提出一种改进的非线性加权图像拼接融合方法.首先采用改进的Harris角点检测方法提取图像特征点，再通过欧氏距离进行特征向量的匹配，然后一次性获得具有高斯特性的非线性加权mask，同时利用2级金字塔高斯平滑，最后直接用原图与平滑处理的图像进行差分和累加，最终实现图像的拼接融合.同时由于算法将重叠部分进行了类似高斯尺度平滑的区域划分及mask的高斯平滑，满足了图像拼接融合时过渡效果更加自然平滑.实验结果表明，改进后的算法在满足图像拼接融合效果的同时，显著提高了计算速率，随着图像分辨率的增加，最大加速比超过20倍.

Select

图形与图像技术研究

低对比度cDNA图像分割的局部水平集方法

芦碧波,刘利群,张霄宏,林忠华

2017, 38(5): 1121-1125.

摘要 ( ) PDF全文 ( )

可视化

互补脱氧核糖核酸（cDNA)微阵列是一项广泛应用的技术，该技术现被应用于同时研究数千个基因的表达水平.样点分割是cDNA微阵列图像处理技术中的关键环节.微阵列图像动态范围较高，部分区域对比度较低且包含噪声，因此给分割带来一定难度.本文首先使用规则网格技术，将微阵列图像划分成单个子图像.为了增强对比度，将子图像归一化后在每个网格内使用C-V模型和水平集技术进行分割.为消除噪声造成的干扰，使用样点面积先验知识作为标准，得到最终的样点位置.实验结果表明，与相关算法相比本文算法具有一定的优势.

Select

图形与图像技术研究

基于联合矩阵分解的图像情感分析研究

蔡国永，夏彬彬

2017, 38(5): 1126-1129.

摘要 ( ) PDF全文 ( )

可视化

训练具有良好泛化能力的分类模型不仅需要足够多的数据，而且需要保证数据应尽量不含或含有较少的噪声.社交网站为训练分类模型提供了大量的数据，但社交网站数据一般含有较多的噪声.针对用于图像情感分类的社交网站数据存在噪声的问题，提出一种基于联合矩阵分解的异构迁移学习图像情感分类算法.该算法将联合矩阵分解在参考领域的共现数据学得的知识（模型参数)迁移到图像情感分类领域，利用模型参数对图像进行重构，重构的图像去除了原数据中的噪声，因此其特征具有更强的情感分类能力.经过Flickr和Twitter图像数据集的实验表明，基于联合矩阵分解的异构迁移学习方法应用于图像情感分类领域的有效性.

Select

图形与图像技术研究

条件深度玻尔兹曼机人脸图像分割模型

张娟，杨建功，汪西莉

2017, 38(5): 1130-1133.

摘要 ( ) PDF全文 ( )

可视化

传统的图像分割方法仅考虑图像的颜色、纹理、位置等底层数据特征，对复杂的人脸图像无法达到理想的分割效果.针对此问题，提出一种基于条件深度玻尔兹曼机的人脸图像分割模型，该模型能够通过深度玻尔兹曼机模型提取类别空间的结构相关性，从而发现复杂输出类别间的关系，为人脸图像分割提供形状先验信息，进而提高图像分割的准确性.文中使用Part Labels人脸数据集进行实验验证，结果表明与传统的逻辑回归、条件随机场、条件受限玻尔兹曼机模型相比，由于本文提出的模型考虑了输出空间结构的高阶相关性，所以能够取得更好的分割效果.

Select

图形与图像技术研究

无监督的稀疏差分嵌入特征提取方法

刘毛溪(1，4)，万鸣华(1，2，3)，孙成立4，王巧丽(1，4)

2017, 38(5): 1134-1138.

摘要 ( ) PDF全文 ( )

可视化

人脸数据中的有效特征是提高识别率的关键，因此特征提取是人脸识别领域的重要步骤.为了能够同时保留人脸数据的局部结构和全局结构，并得到一个更具有解释性的结果，综合主成分分析算法和局部线性嵌入算法，并加入稀疏约束，提出一种无监督的稀疏差分嵌入（Unsupervised Sparse Difference Embedding，USDE)的特征提取方法.在满足局部最小嵌入和全局最大方差的同时，使用弹性网回归算法得到一个稀疏特征向量.在ORL人脸库、AR人脸库以及UMIST人脸库上的实验结果表明，同其他几种方法相比，USDE具有更好的效果.

Select

图形与图像技术研究

基于局部稀疏表示的二尺度块目标跟踪方法

吉训生，刘永祥

2017, 38(5): 1139-1142.

摘要 ( ) PDF全文 ( )

可视化

局部稀疏表示的目标跟踪取得很好效果，但受局部块尺度大小的选择影响较大，为此提出基于局部稀疏表示的二尺度块目标跟踪方法.该方法联合不同尺度块字典和局部稀疏系数来进行外观表示，利用外观在不同尺度块下展现出不同的空间结构以及相关特性，使得目标外观表示更为健壮和有效，可以完全适应更复杂的追踪场景.为了增强目标表示的鲁棒性和准确性，在外观模型中考虑重构误差的影响，减少不可信赖的局部块所造成的偏差.另外，在模板更新时，充分考虑对局部遮挡的判断，舍弃最中间的模板.仿真结果表明，该方法在复杂条件下，能够有效的跟踪运动目标.

Select

其它

多重条带布局的混合RAID系统研究

蔡杰明,方沛,贾思懿,董欢庆,刘振军,刘国良

2017, 38(5): 1143-1151.

摘要 ( ) PDF全文 ( )

可视化

随着数据容量的爆炸式增长以及数据价值的日益增加，应用对存储系统的容量、成本、数据可靠性和数据访问性能等方面提出越来越高的要求.针对纠删码存储存在的与传统RAID技术所面临相同的小写更新与Write Hole的问题，提出一种多重条带布局的Hybrid-RAID技术.该技术采用纠删码，对外提供N+M的数据可靠性保护级别，降低冗余数据的存储开销；采用同步镜像小写、异步镜像转换纠删码的方式，并且保证转换过程无数据覆盖和迁移，从而有效解决同步纠删码的小写更新问题；通过纠删码数据块与校验块的非原位更新，避免纠删码的Write Hole问题.测试结果表明，与RAID6相比，Hybrid-RAID系统的顺序小写性能平均提升了2.05倍，随机小写平均提升6.6倍.

Select

其它

SHCA：基于RAID的两级缓存算法设计与实现

詹玲1,门勇2，汤陈蕾2，徐鹏2，万继光2

2017, 38(5): 1152-1157.

摘要 ( ) PDF全文 ( )

可视化

随着全球数据量的爆炸式增长，传统磁盘阵列构建的大型存储系统在性能上已经无法满足应用的需求.新兴的固态盘存储介质，具有高性能、低功耗等优良特性，将它作为二级缓存引入传统磁盘阵列可以有效改善性能瓶颈.SHCA（SSD aware Heterogeneous Cache Algorithm)算法根据磁盘阵列与固态盘的不同存储特性，将内存自适应地划分为固态盘缓冲区和阵列缓冲区.固态盘缓冲区采用一种基于缓存块淘汰代价的置换算法，根据缓存块的热度和固态盘的读写性能差异，对淘汰缓存块引起的代价进行评估，优先置换淘汰代价最低的块.阵列缓冲区采用基于条带的最近最少使用算法，利用多磁盘的并行性，提高阵列读写吞吐率；同时针对有校验信息的阵列，减少写惩罚.阵列缓冲区淘汰的数据块经过热点数据筛选，识别为热点的块缓存至固态盘，减少阵列读写次数.在详细介绍了SHCA算法设计的同时，进行了相应的试验测试和性能分析.

Select

其它

HBase针对移动互联网业务的改进与优化

雷军(1，2)，刘绍辉(2)，冯宏华(2)，何炎祥(1，3)

2017, 38(5): 1158-1163.

摘要 ( ) PDF全文 ( )

可视化

Apache HBase是当前互联网公司广为使用的开源NoSQL数据库.小米公司几乎所有的在线业务，包括米聊和小米云服务，都使用HBase作后端存储.在海量数据处理应用中，发现HBase的功能存在一定的缺失，在写入吞吐量等性能度量上存在瓶颈.本文针对移动互联网在线业务的特点，基于现有HBase版本提出可保证数据一致性的局部二级索引功能和反向扫描功能，并提出了可配置的细粒度跨集群复制概念，显著提升了单机写吞吐性能.经过全面测试，上述设计和改进方案极大提升了HBase的应用性能，并被部署到了小米的生产集群中.

Select

其它

融合信息增益与和声搜索的语音情感特征选择

陶勇森(1，2)，王坤侠3，杨静1，李廉(1，2)

2017, 38(5): 1164-1168.

摘要 ( ) PDF全文 ( )

可视化

语音特征集通常具有较高的维度，高维度的特征集不仅包含噪声数据和冗余数据，影响情感识别精度，而且在分类识别的过程中将花费大量的计算开销.如何从较高维度的特征集中选择出规模更小，性能较优的特征子集对语音情感识别系统具有重要作用.本文融合过滤式和封装式两种筛选策略，提出信息增益与和声搜索算法相结合的方法进行语音情感特征选择.试验结果表明，采用过滤和封装相结合的两步策略进行特征选择，综合了过滤策略的低时间开销和封装策略的高识别率的优点，而且可以选择出较原始数据集维度更低且分类性能较好的特征子集.

选择文件类型/文献管理软件名称

选择包含的内容

过刊目录

作者投稿

专家审稿

编辑办公

主编办公

编委审稿

下载中心