计算机学报杂志 北大期刊 CSCD期刊 统计源期刊

计算机学报 2019年第06期杂志 文档列表

计算机学报杂志智能服务

模拟退火算法的动力系统模型及收敛性分析1161-1173

摘要：模拟退火算法是经典的拟物类自然计算方法,其算法设计及应用研究取得了丰硕的成果,模拟退火策略也广泛地融入到现代群智能演化算法的研究之中.早期的性能分析和收敛性分析等理论研究主要是基于随机过程中的马尔科夫链理论,获得了依概率意义的收敛性定理.由于物理和数学已经积淀了深厚的理论基础和丰富的分析工具,可以用来进行随机启发式算法的理论分析和设计.该文试图运用动力系统理论分析模拟退火算法的运行机理和收敛性,将算法搜索最优解的过程比拟为质点作弹性运动,算法运行过程中函数值的变化就是质点在作简谐振动或阻尼振动,建立其常微分方程动力系统模型.运用常微分方程的定性理论对该动力系统模型进行求解和分析,证明了模拟退火算法前、中期的局部收敛性和后期的全局收敛性,对其运行机理给出了合理的理论解释.同时,基于建立的动力系统模型,分析了算法衰减因子与收敛速度的关系,得到了模拟退火算法收敛速度的估计.在此基础之上,提出了一个模拟退火回火算法的改进策略,一个简单易行的回火时刻判据,当弹性系数趋于很小的值时,即可以当作回火时刻.选取几个典型的测试问题,运用基本的模拟退火算法进行实验验证.首先,实验表明数值收敛曲线与理论分析的收敛性结论相吻合;其次,实验验证了收敛速度随退火温度变化的理论分析与数值实验相吻合;同时实验也验证了提出的回火时刻判据的有效性.最后,理论与实验分析表明该文建立的动力系统模型适合描述模拟退火算法.

基于社会媒体内容和网络拓扑的特定话题推特摘要研究1174-1189

摘要：推特摘要旨在从话题相关的社会媒体短文本中提炼概要的推文集,以获取有效信息,可用于舆情监控、竞争情报分析及电子商务等.然而社会媒体的海量、嘈杂及不规范性使得仅依赖纯文本的传统摘要方法难以直接迁移到社交媒体情景中;而现有的推特摘要方法很少考虑数据稀疏性和社会网络传播带来的强冗余性,鲜有通过挖掘推文之间潜在的社会网络结构关系进行文摘内容选择,忽略了信息可以沿着社交网络进行传播.受压缩感知及社会学理论的启发,该文提出基于社会网络和稀疏重构的推特摘要方法(SNSR)以更好地融合社会媒体内容和结构信息.首先,挖掘推文中隐含的摘要模式,将其建模为组稀疏正则项,以捕捉代表性的推特摘要组合;其次,建模社会网络中表达一致性与表达传染性为社会化正则项,以探索推文之间的潜在网络结构关系在推特摘要中的作用;再次,建模社会媒体信息传播带来的强冗余性为多样性正则项,进而将这些约束整合到稀疏重构的推特摘要框架中;最后,提出基于Nesterov加速梯度下降的推特摘要算法,以解决推特摘要优化框架中的覆盖性、稀疏性以及多样性等问题.同时,由于推特摘要标准语料的缺乏,作者建设了12个话题的评测数据集.相关的实验结果证明了文中提出方法的有效性.

智能家居场景联动中基于知识图谱的隐式冲突检测方法研究1190-1204

摘要：智能家居场景联动是智能家居系统提供的一种自动化服务,它通过各类智能设备的互联、互通和互动,从而为住户提供更为舒适、安全和节能的家居环境.然而,由于各个智能场景的侧重点不同、管理策略各异,当多个智能场景联动和叠加时,会引起作动器设备之间的竞争、干扰和矛盾等控制冲突现象,降低智能场景用户体验,缩短智能设备使用寿命,甚至危及住户的人身财产安全.因此,智能家居场景联动中的控制冲突问题亟需大量实验研究并找到解决方案.本文中,我们将控制冲突分为两大类,一类是同一作动器上执行明显相反动作的显式冲突,一类是不同作动器之间产生相互干扰动作的隐式冲突.现有的控制冲突检测技术对于显式冲突检测的研究较为成熟,而在隐式冲突检测方面性能相对较弱,其原因可归结为自动化程度低与漏判率高两大缺点.本文提出了一种基于知识图谱语义分析的作动器隐式冲突检测方法,可以充分整合并有效挖掘各类作动器功能描述的常识性知识,进而实现对作动器隐式冲突的自动化检测.该方法有两个主要环节,分别是作动器设备注册环节与规则制定环节.我们在作动器设备注册环节提取知识图谱中的常识性知识,对作动器功能之间的效果冲突进行识别判断,并以隐式冲突矩阵的形式将判断结果在边缘设备上进行存储,实现存在于不同类型作动器之间的干扰检测;在规则制定环节,借助隐式冲突矩阵的冲突信息进行字典式查询与匹配,以判断规则之间的隐式冲突.此外,基于知识图谱中设备功能短语自身特点,设计了基于语义贡献度的权重分配策略,完成词向量到短语向量的转化.为解决聚类后相同簇中近反义功能短语混合杂糅的问题,本文提出了相对极性指标和近反义关系一步扩展方法,并借由图模型染色算法将反义关系的短语拆分到不同子�

量子并行神经网络1205-1217

摘要：本文在前期量子概率神经网络(QPrNN)的基础上,提出了一种物理可实现的量子神经网络,称为量子并行神经网络(QPNN).主要特点是基于量子神经元的激活机制,利用量子并行性跟踪所有网络状态来提高分类结果.与之前的研究相比,在网络各个中间层和输入层之间添加了连接,增加了量子神经网络的非线性表达能力,所以结构上可以向深层网络发展.由于QPNN独特的量子门性质,该模型在很多条件下对噪声不敏感,涵盖了相位偏移和幅值翻转噪声.QPNN的另一个优势是可以作为内存使用,不但可以像经典内存一样存取数据,还可以作为生成模型,产生新数据.在实验验证部分,本次研究选取了两个标准的例子,MNIST手写体识别和Cifar-10来验证其测试误差.实验结果表明,QPNN只需采用经典神经网络3%左右的神经元资源即可超过相对应的全连接前向神经网络.与QPrNN相比,MNIST的分类测试准确率提高了0.2%;Cifar-10测试准确率提高了3%.同时,MNIST的正确取回概率平均提高了2%.

关联规则推荐的高效分布式计算框架1218-1231

摘要：关联规则推荐模型是在电子商务网站应用最广泛的商用推荐引擎之一,目前已有的工作大多聚焦于如何挑选高质量规则,以提升推荐精度.然而,关联规则数量庞大,且用户并发访问量通常极大,如何快速匹配用户浏览记录和关联规则库,为海量在线用户产生近实时推荐,成为制约关联规则推荐能否胜任真实电子商务网站推荐的重要因素.为此,本文研究关联规则推荐的效率问题,提出服务于高效关联规则推荐的分布式计算框架,将规则挖掘与推荐计算无缝衔接.具体而言,本文首先设计有序模式森林,用于压缩存储频繁模式;然后将候选规则挖掘转化为森林上的路径搜索计算,并提出高效的单机路径搜索算法;最后提出负载均衡的数据分割策略,同时降低分布式规则挖掘与推荐计算中的任务最迟完成时间.在3个公开数据集的实验结果表明基于有序模式森林的推荐计算比传统穷举匹配策略降低6倍以上时间,同时所提出的分布式计算框架可随计算节点数量达到近线性扩展.

非平衡基因数据的差异表达基因选择算法研究1232-1251

摘要：针对准确率不适于评价不平衡数据特征子集性能的缺陷,提出了 F2 -measure(简称 F2 )准则.为避免mRMR(minimal Redundancy-Maximal Relevance)的互信息方法倾向于选择多值特征,提出了归一化互信息 SU (Symmetrical Uncertainty).针对最大化 AUC (Area Under an ROC Curve)框架下,特征选择算法的特征与类标相关性、特征间相关性的取值范围(量纲)不一致问题,提出了归一化的特征权重.为加快特征选择过程,提出了结合 SU和AUC 的特征预选择,缩小特征搜索空间.提出动态加权顺序前向搜索DWSFS(Dynamic Weighted Sequential Forward Search)和动态加权顺序前向浮动搜索DWSFFS(Dynamic Weighted Sequential Forward Floating Search),以期得到分类性能更好的特征子集.基于最大化 AUC 和mRMR框架,结合上述创新点,设计出16种特征选择算法.7个经典二类不平衡基因数据集、3个多类不平衡(或近似平衡)基因数据集的50次重复实验表明:所提算法选择的基因子集具有非常好的分类识别能力;提出的 F2、SU、归一化基因权重、基因预选择,以及DWSFS和DWSFFS对选择非平衡基因数据集的差异表达基因非常有效.提出的 SU 在度量基因冗余性时优于斯皮尔曼等级相关系数 RCC (Rank Correlation Coefficient);基因选择过程中的权值度量采用基因与类标相关性减去基因间冗余性优于采用基因与类标相关性除以基因冗余性方案.与现有经典基因选择算法的实验比较表明:提出的基因选择算法的性能优于现有基因选择算法.

融合改进二元萤火虫算法和边界最小化测度的集成剪枝方法1252-1273

摘要：集成剪枝是提高分类器集成性能的一种关键性技术,其通过选择较小规模的基分类器,获得更优的集成性能.目前集成剪枝方法通常单独采用基分类器间的差异性测度或元启发式算法,进行集成剪枝.基分类器的平均精度和差异性被广泛认为是集成剪枝的两个重要指标,但增大基分类器间差异性势必会减小其平均分类精度,提高基分类器的平均精度亦会降低其差异性.故在基分类器的平均精度和差异性之间存在一个平衡状态,使得集成性能最优,找到该平衡状态才是集成剪枝成功的关键.集成剪枝是一个NP完全问题,采用差异性测度仅能剔除集成系统中部分冗余的基分类器,难以准确地找到该平衡状态;元启发式算法在搜索该平衡状态上,具有良好的性能,但若单独采用元启发式算法,则很难穷尽搜索到该平衡状态.故该文提出了融合改进二元萤火虫算法和边界最小化测度的集成剪枝方法.首先,采用Bootstrap方法重复抽取训练集,获得多个训练子集,使用分类器分别进行独立训练,获得多个基分类器;其次,运用边界最小化测度对所获得的基分类器进行预剪枝,剔除综合性能较差的基分类器,显著降低集成剪枝问题的复杂度;接着,通过改进萤火虫的移动方式和搜索过程,并引入竞争行为和跳跃行为,提出了改进二元萤火虫算法;最后,利用改进二元萤火虫算法对预剪枝后的基分类器,进行二次剪枝,选择出性能最优的子集成.在35个UCI标准数据集上进行测试,实验结果表明:相较于其他方法,该文所选择的基分类器规模较小,集成分类精度更高,并验证了其有效性和显著性.

基于网络约束双聚类的癌症亚型分类1274-1288

摘要：癌症亚型识别在肿瘤异质性分析中具有重要意义.双聚类可以在大规模基因表达数据的基因和样本维度上同时进行聚类分析,发现部分样本在部分基因子集上表达相似的双聚类簇,进而发现相应的癌症亚型,为癌症的精准基因治疗等提供了重要的信息.双聚类算法通过结合基因相互作用网络数据,可进一步提高癌症亚型分类的准确度,但已有整合基因网络的双聚类算法通常仅基于基因的度加权选择基因,易受网络中噪声互作的干扰和缺失互作的误导.为此,该文提出了一种基于基因互作网络正则化的双聚类算法(Network Regularized Bi-Clustering algorithm, NetRBC). NetRBC首先通过最小化聚类簇上的均方残差分别求取癌症基因表达数据矩阵上的基因簇和样本簇指示矩阵;然后利用基因网络和基因簇指示矩阵构建图正则项;最后将此正则项结合到基于均方残差的非负矩阵分解中,约束基因簇和样本簇矩阵的协同分解,以期提高癌症亚型分类的精度.在多个癌症基因表达数据上的实验结果表明,NetRBC比已有相关方法能够更准确地区分癌症亚型.

偏好多目标进化算法研究综述1289-1315

摘要：多目标优化需要同时优化若干相互冲突的目标,其目的是获得均匀分布于整个Pareto前沿上的最优解集.然而在实际多目标优化问题中,决策者通常只对目标空间中部分区域内的Pareto最优解感兴趣,因此将决策者的偏好信息与多目标优化方法相结合成为进化计算领域的研究热点.偏好多目标进化算法通过引入决策者的偏好信息,将算法的搜索集中在决策者感兴趣的偏好区域,有效利用算法的计算资源,提高算法的求解效率,降低计算复杂度,同时有利于决策者高效地做出最终决策.本文从偏好的设置方法和算法性能两个角度介绍偏好多目标进化算法.在偏好的设置上,从占优关系、角度关系、权重向量和偏好集四个方面综述融入偏好信息的多目标进化算法;在算法性能上,从上述四类偏好的设置方法中各选取两种偏好算法进行仿真实验,从偏好策略的有效性、解集的整体性以及算法的复杂度三个方面进行实验对比并深入分析其优缺点.最后,总结了偏好多目标进化算法的未来发展趋势.

基于用户评论的深度情感分析和多视图协同融合的混合推荐方法1316-1333

摘要：目前,大多数推荐技术使用用户评分来推断用户偏好.当有充足的评分信息时,协同过滤技术表现良好.然而,评分数据普遍存在着稀疏性,或者难以让用户将其偏好表示为对物品的评分等级,故有效性受到限制.基于内容的推荐方法依据物品的内容来寻找与目标用户喜欢的物品内容相似的物品.在目标用户没有充足的历史数据的情况下,该方法仍然不充分,其推荐效果也很有限.当前,融合多视图的兴趣偏好信息构建混合推荐系统是个性化推荐研究发展的趋势.混合推荐系统通过融合用户物品的交互评分、隐式反馈和辅助信息进行个性化推荐,故本文提出了一种新颖的基于用户评论的深度情感分析和多视图协同融合的混合推荐方法.针对用户评论、物品内容描述等短文本的情感及语义难以分析,单一推荐视图易导致对用户画像建模粗放等问题,本文利用词向量对用户评论的短文本进行分布式表征,并结合长短期记忆网络实现从上下文语义层面对用户评论的情感进行分析.同时,本文提出基于观点预过滤和基于用户评分嵌入的情感融合方法,设计了一种嵌入的网络结构对用户评论进行深层语义分析和情感计算,以解决用户评分与真实兴趣偏好存在较大偏差、评分等级分布极度不均衡等问题.此外,本文利用分布式的段落向量表征对物品内容描述的短文本进行相似度计算,并设计了候选物品相似性的计算方法及度量K个最近邻物品的方法,解决了推荐系统中物品的内容信息不易挖掘和利用的问题.最后,本文提出了一种基于协同训练的融合用户评分、情感倾向和物品内容信息的混合推荐算法,实现对稀疏的用户评分矩阵的循环填充和修正,进而实现基于评分预测的Top N推荐.该方法解决了混合推荐系统中不同兴趣偏好的多推荐视图难以融合的问题,同时在一定程度上解决了推�

基于并行概率规划的股票指数模拟1334-1350

摘要：在金融领域,股票指数(简称股指)模拟与分析是一个重要课题,用于股票市场的长期分析.然而,大多数的这类工作目前由专业的分析师来完成,非职业投资者难以涉及.另一方面,现有的基于数学或机器学习的股指模拟方法具有参数多、人工干预多、可解释性差等缺点.针对以上问题,本文基于并行概率规划(Parallel Probabilistic Planning,PPP),提出了一个股指模拟的规划领域模型,并能够进行自动求解.股票市场具有大量的不确定性和并发性,因此适合用并行概率模型来表示.方法的核心思想是将股指模拟问题转化为智能规划问题.首先,本文构建股指模拟问题的规划领域模型.由于股票市场的复杂性,需尽可能地考虑各种影响因素、约束条件、可能事件以及它们之间的关联.构建的规划领域模型由针对PPP的规划语言RDDL(Relational Dynamic Influence Diagram Language)来进行描述.接着,使用PPP的模拟求解工具——rddlsim来进行基于抽样的规划求解.rddlsim是国际概率规划大赛IPPC提供的求解工具,能够全面地解析RDDL描述.实验数据使用上证50指数和上证100指数的股票数据.即,从某个时间点开始,通过求解对应的规划问题来模拟未来一年股票指数的变化趋势.求解结果,一方面,与真实股票指数变化作对比;另一方面,与基于线性回归、基于SVM和基于LSTM的三种模拟方法的结果作对比.我们分别使用交叉熵、最小二乘和皮尔森相关系数作为损失函数.实验表明,本文的模拟效果比较贴近于真实的股指变化趋势;在大多数情况下,本文方法优于基于回归或SVM的模拟方法,且与基于LSTM的方法性能相当.并且,相对于对比的模拟方法,本文方法提供了较强的可解释性,且在求解过程中不需人工干预或调参.这是因为,形式化的规划领域描述展示了在股指模拟问题中各种因素如何相互影响,而且自动求解得到的规划解给

面向卫星遥测数据流的最小稀有模式挖掘方法1351-1366

摘要：模式挖掘是应用于卫星智能监控服务中的一项重要技术.当前频繁模式挖掘的使用率要远远高于稀有模式挖掘,然而对于卫星遥测数据流来说,频繁模式挖掘在安全监测和故障预防等方面所取得的成效不如稀有模式挖掘.因为频繁模式挖掘无法从卫星的遥测数据中揭示卫星可能存在的潜在故障.卫星遥测是持续不断进行的,所以其数据流存在数据量大、传输速度快和数据重复性高的特点.如果采用一般的稀有模式挖掘方法来挖掘卫星数据流,尽管其速度比频繁模式挖掘快,但总体上仍然较慢,不能满足卫星实时监测的需要.针对上述问题,本文提出一种可快速找出卫星遥测数据流中隐藏信息的最小稀有模式挖掘方法,它具有如下优点:(1)无需卫星领域知识;(2)引用滑动窗口技术并将主观参数(窗口尺寸)客观化,使得算法能够实时地处理数据流;(3)通过仅挖掘最小稀有模式方式来提高算法的挖掘效率;(4)该算法使用双向遍历技术提高算法的运行速度.从某在轨卫星的遥测数据流中选取10个关键特征参数进行算法验证.实验结果表明,本文所提算法能有效地从卫星遥测数据流中挖掘出全部的最小稀有模式,并且其挖掘速度比现有的方法快.

融合SOM功能聚类与DeepFM质量预测的API服务推荐方法1367-1383

摘要：由于越来越多的企业和组织纷纷将自己的业务、数据或资源封装成服务,并通过API的形式到互联网上,API服务的数量呈现倍增趋势.在此背景下,如何从这样一个大规模的API服务集合中,快速有效地找到满足开发者用户Mashup需求的API服务,已成为一个挑战性问题.为此,本文聚焦于“推荐合适的API服务以构建高质量Mashup应用”问题,以面向服务内容的功能聚类为基础,结合基于多维服务质量的评分预测,提出一种融合SOM功能聚类与DeepFM质量预测的API服务推荐方法,用于创建高质量的Mashup应用.该方法首先采用Wikipedia 作为外部语料库扩充API服务文档的内容并利用HDP模型建模其主题分布.通过WikiExtractor抽取出Wikipedia中的语料数据,并利用Word2vec工具训练该语料数据获得其词向量模型.利用训练好的Wikipedia词向量模型对API服务描述文档进行扩充.针对扩充后的API服务文档,使用HDP主题建模技术,挖掘出其隐含的主题信息,自动确定最优主题个数,以准确地度量API服务文档之间的语义相似度.然后,采用SOM神经网络进行面向主题的API服务聚类.在HDP主题建模之后,对获得的“API服务文档-主题”向量采用SOM神经网络聚类算法进行主题聚类,通过自组织过程,将众多的API服务划分到不同的功能类簇中,每一个功能类中包含多个具有相似功能的API服务.接下来,针对API服务类簇中所有具有相似功能的API服务,利用DeepFM模型建模和挖掘其多维QoS属性之间的复杂交互关系,预测并排序API服务的质量得分.DeepFM模型自动地提取出QoS数据中(包括流行度、共现次数等)的有效的特征组合关系(包括高阶特征和低阶特征组合关系),预测并排序每一个API服务相对于目标Mashup应用的质量得分,推荐得分靠前的 N 个API服务给开发者用户.最后,在真实Web服务数据集上进行了实验比较与分析,实验结果表明:本文�

计算机学报杂志科学与工程论坛

IPv6地址结构标准化研究综述1384-1405

摘要：随着IPv6网络商用化的进行和大面积部署,IPv6相关的研究正在成为新的研究热点.相对于IPv4而言,IPv6地址有128比特,因此其生成、使用、安全等方面的情况也要比IPv4复杂得多,而对IPv6地址结构的深入了解,是进行IPv6地址规划、IPv6网络测量、IPv6网络安全以及下一代互联网网络体系结构等方面研究的基础.涉及IPv6地址结构方面的互联网标准数量众多、内容涵盖面广,这些都不利于全面了解IPv6地址结构.本文总结了目前IPv6地址结构相关的标准,包括IPv6全球单播地址结构、IPv6组播地址结构、IPv6任播地址结构等,在简要介绍各种地址结构的基础上,特别介绍了IPv6地址结构中几个和IPv4显著不同的地方.首先, IPv6地址通常可以分成子网前缀和接口标识两个部分,与IPv4相比IPv6增加了接口标识生成方案,而且IPv6接口标识的生成方案与IPv6安全和隐私保护紧密相关;其次,IPv6、IPv4将长期共存,因此过渡技术必不可少,而过渡技术中的地址结构与普通IPv6地址有所不同;最后, IPv6网络中多宿主机的情况更加普遍,导致了广泛存在的地址选择问题.针对这一问题,除了通过建立IPv6网络的源地址选择策略和目的地址选择策略来解决之外,定位符与身份标识分离也提供了一种解决思路.随着IPv6的进一步广泛部署,物联网中的IPv6地址结构以及IPv6地址安全方面的研究得到了越来越多的关注.物联网的广泛应用促使IPv6加速部署,但由于物联网本身的一些特点如最大报文长度较短、要求能耗较低等,物联网中IPv6的接口标识生成方案通常要保证所生成的接口标识便于压缩.另一个得到越来越多重视的研究方向是IPv6地址安全,与IPv4网络的情况有所不同,IPv6网络欠缺大规模使用的安全经验,大量支持IPv6的设备对IPv6协议的实现也只实现了基本功能,而由于IPv6较IPv4有更为复杂的应用场景,因此IPv6网络的安�

基于值函数和策略梯度的深度强化学习综述1406-1438

摘要：作为人工智能领域的热门研究问题,深度强化学习自提出以来,就受到人们越来越多的关注.目前,深度强化学习能够解决很多以前难以解决的问题,比如直接从原始像素中学习如何玩视频游戏和针对机器人问题学习控制策略,深度强化学习通过不断优化控制策略,建立一个对视觉世界有更高层次理解的自治系统.其中,基于值函数和策略梯度的深度强化学习是核心的基础方法和研究重点.该文对这两类深度强化学习方法进行了系统的阐述和总结,包括用到的求解算法和网络结构.首先,本文概述了基于值函数的深度强化学习方法,包括开山鼻祖深度Q网络和基于深度Q网络的各种改进方法.然后介绍了策略梯度的概念和常见算法,并概述了深度确定性策略梯度、信赖域策略优化和异步优势行动者-评论家这三种基于策略梯度的深度强化学习方法及相应的一些改进方法.接着概述了深度强化学习前沿成果阿尔法狗和阿尔法元,并分析了后者和该文概述的两种深度强化学习方法的联系.最后对深度强化学习的未来研究方向进行了展望.