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

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

计算机学报杂志大数据

基于多维数据集的异常子群发现技术1671-1685

摘要：非频繁项集是未被标准化的频繁项集产生算法(如APRIORI以及FP-Growth算法)提取的所有项集.在数据集上挖掘有意义的非频繁项集是数据挖掘的重要工作之一.目前,基于传统数据集的非频繁项集挖掘研究主要集中在负相关、负模式以及间接关联等方面,且主要是对整个数据集上的性质进行分析,而没有对数据集的切片进行分析.该文提出了一种新的模式,试图找到符合如下条件的特定子群,其描述的数据集切片上存在某些特殊项集,这些项集在整个数据集上并非频繁项集,但是在该数据集切片上却是频繁项集.根据用户要求自动找出这些异常子群以及其对应项集的算法在数据分析中有着十分重要的意义.该文提出的解决方案由两部分组成:候选产生阶段以及查询交互阶段.前者是一个脱机处理的过程,而后者则是在线实时反馈的过程.在候选产生阶段,该文提出了一种基于多维数据集高效产生频繁项集以及显著子群并有效建立索引的算法.根据索引,在查询交互阶段,该文提出的算法框架可以快速准确地返回给定查询对应的异常子群以及对应项集.基于多个真实数据集的实验表明,该文提出的方案可以根据用户要求实时返回有意义的异常子群以及对应项集.此外,该文提出的算法在多维数据集上的挖掘效率比UTMTU算法提升了数倍.

一种基于向量索引的内存OLAP星型连接加速新技术1686-1703

摘要：星型连接是OLAP中重要的操作,事实表与维表基于星型连接执行多维分析处理.星型连接的性能取决于连接性能.当前研究主要集中在如何在不同的处理器平台上优化哈希连接性能,然而如何获得最优的哈希连接参数或实现是一个复杂的问题.哈希连接不依赖于模式的语义信息,然而却可以在事实表与维表之间通过维映射特征进一步优化连接性能.该文提出了一种新颖的面向OLAP负载的向量索引以提高事实表与维表之间的连接性能.从模式的角度来看,维表可以映射为向量索引,每一个事实表记录可以直接映射到向量索引上的相应位置,无须执行基于值匹配的哈希连接操作.从实现技术的角度看,向量索引是一种位图索引、字典表压缩、主外键参照完整性约束和连接索引相结合的技术.系统化的设计使向量索引可以扮演多种角色:(1)向量索引与位图索引类似起到过滤作用;(2)向量索引相对于只存储0或1的位图索引使用更多的位来表示更多的信息;(3)映射或创建自动增长的主键作为向量索引地址并且更新相应的外键,将主外键参照完整性约束转换为向量参照约束;(4)外键连接操作简化为通过外键值引用向量单元.基于向量索引,OLAP中代价大的星形连接可以抽象为向量索引计算,OLAP查询可以简化为基于向量索引的单表扫描处理.向量索引简化的设计不仅可以提升性能,而且降低了在GPU平台实现的复杂度.本文首先讨论了向量索引机制和如何在数据库中应用向量索引;然后设计向量索引更新机制,以保证在更新时向量参照约束;最后提出基于向量索引的OLAP框架来提高内存数据库OLAP性能.基于向量索引的星型连接可以用作GPU上的OLAP加速器,使CPU可以将计算密集型负载转移到高性能GPU平台来加速OLAP处理.实验结果表明向量索引更新代价较低,而向量引用性能收益较大.更重要的是,向

基于多路分块的Pay-as-you-go实体识别方法1704-1720

摘要：实体识别是数据集成和数据清洗的一个重要方面.针对Pay-as-you-go数据管理需求,本文提出一个基于多路分块的Pay-as-you-go实体识别方法.该方法不要求提供最优的分块或排序的键,并且可以直接找出脏数据集中冗余度最大的区域.分为两个阶段,初始化阶段和迭代阶段.在初始化阶段,初步地生成候选数据对象对,并按匹配可能性排序后加入到候选队列.在迭代阶段,每次选择候选队列队首的候选对(即最可能匹配的)来处理,并且根据实时的实体识别结果,动态地更新候选对的匹配可能性,调整候选队列.这样减少了无用的数据对象比较,使得实时的识别结果最优化.通过在真实数据集和合成数据集上的实验对比,说明本文提出的基于多路分块的Pay-as-you-go实体识别方法显著地优于已有工作中提出的方法.

基于特征效用参与率的空间高效用co-location模式挖掘方法1721-1738

摘要：空间co-location模式是指其实例在空间邻域内频繁一起出现的空间特征子集.与传统的空间co-location模式挖掘不同,在空间高效用co-location模式挖掘中,不再将参与度(PI)作为有趣模式的度量指标,而是将效用值作为挖掘有趣模式的兴趣度量指标.现有的空间高效用co-location模式挖掘方法分为特征带效用和实例带效用两类.特征带效用的现有方法没有考虑不同特征效用之间的差异,挖掘的结果往往包含了许多不尽合理的"高效用"模式;而实例带效用的现有方法,则考虑了不同特征对模式效用的影响,但没有客观地度量这种影响.该文提出了一种确定特征在模式中的效用权重ω(fi,c)的方法,定义了更为合理的空间高效用co-location模式概念,设计了一个有效的挖掘算法.大量的实验表明提出的高效用co-location模式度量方法和相应的挖掘算法能够处理特征效用差异性和特征间的相互影响问题,能更有效地挖掘到空间高效用co-location模式.

基于内容的社交网络用户身份识别方法1739-1754

摘要：社交网络中识别用户身份具有重要价值,它对社交网络的分析与监管、用户行为的预测以及用户之间交互过程的研究具有重要意义.该文针对社交网络中的用户身份进行研究,将用户身份分为组织用户和个人用户,并对这两种用户身份进行具体定义和识别.该文研究问题属于社交网络用户分析研究中的子研究问题,主要通过用户在社交网络中发表的文本内容、多媒体内容以及用户时间序列内容识别出该用户的组织-个人身份,为社交网络用户身份的识别及进一步研究提供借鉴和帮助.在识别过程中,通过对文本内容中用户的口语化水平、内容(主题)复杂化水平、内容规范化水平的度量以及多媒体内容中用户图片特性和用户时间序列内容的分析,从不同角度提出5种机器可操作的用户组织-个人身份识别方法,进而识别出社交网络中用户是组织用户还是个人用户.最后,为了验证该文所提识别方法的可行性和有效性,该文选择新浪微博数据进行实验,并通过概率模型识别方法进行了对比分析.同时,在验证过程中,使用多种指标对实验结果进行评价.实验结果表明,该文识别方法能够有效识别出用户的组织-个人身份,其中内容复杂特性识别方法、内容规范化识别方法以及时间序列内容识别方法的用户身份识别准确率超过80%.

支持Unikernel的流式计算引擎:Hummer1755-1766

摘要：社会计算中,社会公共安全、企业商务智能和舆情计算等众多领域均对实时计算的性能提出了越来越高的要求.流式计算引擎作为大数据计算研究领域的研究热点之一,致力于提供高吞吐量和低延迟的实时计算能力.流式处理任务对处理延迟非常敏感,数据价值随着处理时长的增长而快速递减.传统流式计算引擎设计中,操作系统、JVM等占用大量计算资源,如何提升计算资源利用率成为目前亟待解决的问题.为此,本文提出了一种基于C++语言实现的支持Unikernel的高性能实时数据分析计算引擎Hummer.首先,通过引入Unikernel机制,Hummer可绕过传统操作系统,直接运行于裸机或虚拟化层,减少传统操作系统无关组件带来的性能开销,支持分布式环境下的快速部署与启动,为高性能大数据计算引擎设计提出新的思路.其次,通过使用Unikernel对计算引擎进行封装,解决了C++应用需本地化编译、难以在集群中部署的问题.最后,系统使用灵活的网络通信方案,支持异构网络部署及网络资源隔离.实验表明,Hummer端到端处理延迟低于30ms,较Flink系统低2倍,较Spark Streaming低15.8倍,且吞吐量达到Flink的2倍.使用Unikernel封装的Hummer系统镜像仅为100MB,启动时间约为2s.

基于网络表示学习的个性化商品推荐1767-1778

摘要：近些年来,互联网不断普及,其应用场景也在不断增加.电子商务是互联网普及、成熟的一大重要产物.这种新型的商业模式,便利了大众的生活,同时也创造了巨大的利润.对于电子商务而言,推荐系统是其中最关键的组成部分.推荐系统可以针对不同的用户,推荐其感兴趣的商品.好的推荐系统无论是对于用户体验还是公司盈利而言,都有着非常正面的作用.近几年间,网络表示学习受到观注,出现了一些利用网络表示学习的推荐算法研究.将网络表示学习应用于推荐系统中乃至商品推荐中,可以有效地利用近期网络表示学习研究成果.该文提出了一种利用网络表示学习进行个性化商品推荐的方法 PGE(Product Graph Embedding).首先,作者通过历史购买记录获取商品的顺序信息,从而构建商品网络.基于商品网络和网络表示学习算法,商品可以被映射至低维向量空间中.一旦作者获取了商品的低维向量表示,动态的用户偏好便可以基于用户购买过的商品记录及商品的时序性线性计算得出,并和商品映射到相同的低维向量空间中.由此,商品和用户的相关性可利用商品和用户的低维向量相似度进行评估.作者在京东数据集上进行实验.实验表明,作者的算法在个性化商品推荐方面相较于最好的基准方法在P@10上提升了10%以上,这显示出了作者算法的优越性.

基于EMD距离的数据流分布式相似性连接技术1779-1796

摘要：随着数据获取设备的不断进步和数据获取技术的快速发展,如何分析和挖掘应用中快速产生的数据流成为亟待解决的问题.数据流的相似性连接返回两个数据流上相似的数据对,是分析和挖掘数据流的重要操作.相比于Lp范式距离,例如曼哈顿距离和欧氏距离,EMD距离(Earth Mover’s Distance)因其可以更准确地量化直方图元组之间的相似性而受到广泛关注,被广泛应用于解决基于内容的图像检索、冗余图像识别以及视频对象跟踪等重要应用问题.然而EMD距离的计算复杂度却高达三次方,阻碍了EMD距离在数据流相似性连接问题中的应用.该文基于开源的Apache Storm数据流分布式并行处理框架,设计并实现了基于EMD距离的数据流分布式相似性连接技术,命名为EMD-DDSJ技术.该技术在数据分发时维护了连接计算节点上的数据局部性,并基于该数据局部性增强了连接算法对不相似直方图元组对间EMD计算的过滤性能,提高了各个连接计算节点的执行效率.同时基于连接计算节点的代价模型,提出了基于反馈的负载均衡策略,有效提升EMD-DDSJ技术的整体执行性能.在真实数据集上的实验结果展示了该文提出的EMD-DDSJ技术的高效性和可扩展性,比相关最好的技术在处理吞吐率上最高提升了1.4倍,在元组平均处理延迟上最多降低了44%,并且随着相似性阈值或滑动窗口大小的增大该提升比率还会进一步增大.

一种基于矩阵分解的上下文感知POI推荐算法1797-1811

摘要：近年来,随着移动设备的普及,基于位置的社交网络(Location-Based Social Network,LBSN)逐渐被人们广泛使用并成为一种新型的社交媒体.LBSN能够记录丰富的上下文信息,例如用户社交网络、POI地理位置、POI类别信息等,这无疑为个性化的POI(Point-of-Interest)推荐系统带来了巨大的发展机遇.但是如何建模这些上下文信息对POI推荐的影响并将它们有效地融合成为了一大难点,另外用户签到数据的稀疏性也为POI推荐带来巨大的挑战.为了克服上述挑战,该文提出了一个基于矩阵分解的上下文感知POI推荐模型.具体地,该文从多个方面建模用户的签到行为,除了利用用户的签到数据,还考虑了POI的地理位置对用户签到行为的影响,用户更愿意访问那些距离近并且符合自身偏好的POI.另外,为了进一步缓解签到数据的稀疏性,该文还利用了用户社交网络数据和POI类别信息.最后,该文提出了一个通用的矩阵分解模型,它能有效地融合上述上下文信息,并且具有良好的可扩展性和较低的时间复杂度.在两个真实的LBSN数据集上的实验结果表明,该文提出的方法在推荐的准确性上远优于当前流行的POI推荐算法.

基于双深度网络的安全深度强化学习方法1812-1826

摘要：深度强化学习利用深度学习感知环境信息,使用强化学习求解最优决策,是当前人工智能领域的主要研究热点之一.然而,大部分深度强化学习的工作未考虑安全问题,有些方法甚至特意加入带随机性质的探索来扩展采样的覆盖面,以期望获得更好的近似最优解.可是,不受安全控制的探索性学习很可能会带来重大风险.针对上述问题,提出了一种基于双深度网络的安全深度强化学习(Dual Deep Network Based Secure Deep Reinforcement Learning,DDN-SDRL)方法.DDN-SDRL方法设计了危险样本经验池和安全样本经验池,其中危险样本经验池用于记录探索失败时的临界状态和危险状态的样本,而安全样本经验池用于记录剔除了临界状态和危险状态的样本.DDN-SDRL方法在原始网络模型上增加了一个深度Q网络来训练危险样本,将高维输入编码为抽象表示后再解码为特征;同时提出了惩罚项描述临界状态,并使用原始网络目标函数和惩罚项计算目标函数.DDN-SDRL方法以危险样本经验池中的样本为输入,使用深度Q网络训练得到惩罚项.由于DDN-SDRL方法利用了临界状态、危险状态及安全状态信息,因此Agent可以通过避开危险状态的样本、优先选取安全状态的样本来提高安全性.DDN-SDRL方法具有通用性,能与多种深度网络模型结合.实验验证了方法的有效性.

一种基于改进网格多维TTI索引的动态Top-k查询算法1827-1844

摘要：Top-k查询是目前海量数据在动态环境中高效处理的重要方法之一.在许多实际应用中,满足用户偏好的top-k查询一般由两个部分组成:选择条件和排序函数.用户可自行设置排序函数,也可选择对不同数据子集进行查询.在传统数据库领域中已经对top-k算法进行了深入的研究,但是现有的方法不适用于大量目标对象的属性值发生动态变化的情况.在查询过程中由于目标对象的属性值发生改变可能导致查询结果的改变,从而对算法性能有更高的要求.围绕动态top-k计算问题,在网格索引的基础上提出了TTI索引,通过TTI索引中的概要信息高效计算网格k支配能力并划分影响区和自由区.根据划分的区域裁剪数据集并降低数据动态变化时需重新计算发生的概率.实验中采用多种数据集进行测试,分别与top-k、RankCube和CIA算法进行了比较.实验结果验证了算法的有效性,实验数据表明在静态情况下,该文算法的查询效率可比传统top-k算法最多快至8倍,动态情况下可比传统top-k算法最多快10倍.

基于双记忆注意力的方面级别情感分类模型1845-1857

摘要：方面级别情感分类的研究目标是针对给定语句所描述对象的特定方面,分析该语句所表达出的情感极性.现有的解决方案中,基于注意力机制的循环神经网络模型和多层模型性能表现较好,二者都借助了深度网络和外部记忆做注意力调优,但实验结果表明这些模型在处理复杂语句时的性能不够理想.本文提出一种基于双记忆注意力机制的方面级别情感分类模型,基本设计思想是借助循环神经网络的序列学习能力得到语句编码,并构造相应的注意力机制从语句编码中提取出关于给定方面词的情感表达.为此,构造了两个外部记忆:陈述性记忆和程序性记忆,分别用于捕获语句中与给定方面词相关的词级别和短语级别信息,并设计了一个分段解码器,用于从相关记忆中选择并提取情感语义信息.为验证模型的有效性,在三个基准数据集上进行了测试,包括SemEval 2014的Laptop和Restaurant数据集和一组常用的Twitter数据集,实验结果表明,本文提出的模型在分类准确率和泛化能力上的表现优于相关工作.此外,还设计了专门实验以验证本文提出的方面级别注意力机制和情感语义提取机制的有效性,为进一步研究方面级别情感语义抽取问题提供了新的思路和实验证据.

一种基于最大流的分布式存储系统中查询任务最优分配算法1858-1872

摘要：分布式存储系统多采用数据分区和多副本机制来处理海量数据并提供高可用性.为了提高读写效率,现有系统在将任务分发给不同节点时往往需要考虑数据分区的情况,并使得任务分配能够保证数据本地性.然而,给定一个需要访问多个数据分区的查询任务,现有系统没有充分考虑节点的实际负载情况,导致虽然任务的分配满足数据本地性,但集群查询响应速度仍受到制约.该文提出一种在分布式存储系统中查询任务的节点分配算法,该算法不仅考虑了数据本地性,还利用了多副本机制确保节点间的负载均衡.算法的基本思想是将任务分配问题转化为最大流问题,并通过二分查找寻求最优分配方案.在实验阶段,该文首先通过模拟实验验证该算法的正确性,之后将该算法集成到Cassandra中作为一种新的负载均衡策略,并与Cassandra原生的两种策略进行性能对比.实验证明,该文提出的算法使得查询性能优于Cassandra原生的策略,平均查询时间缩短为原有策略的50%,某些情况下可以缩短为11%.

面向MapReduce的迭代式数据均衡分区策略1873-1885

摘要：MapReduce是一种适用于大数据处理的重要并行计算框架.然而,由于难以提前全面获得中间数据的分布规律,默认的数据分区策略往往会造成Reducer端的数据倾斜,会直接影响MapReduce的整体性能.为了实现数据均衡分区,本文提出一种迭代式数据均衡分区策略,将每个Mapper节点要处理的数据块细分后以迭代方式循环处理,根据已迭代轮次的微分区分配结果决定当前迭代轮次的微分区分配方案,以不断调整历次迭代产生的数据倾斜,逐步实现数据均衡分区.给出了迭代式数据分区策略的分配时机、分配准则、分配评价模型和分配算法.基于公开的数据集,对迭代式数据均衡分区策略进行了详细测评,结果表明,该策略能够得到更均衡的数据分区结果,当数据集本身倾斜比较显著时,MapReduce整体性能比默认分区策略平均提高了11.1%和19.7%.

深度学习中的对抗样本问题1886-1904

摘要：对抗样本是深度学习在安全领域中的热点问题,对抗样本的特性、生成、攻击方式以及如何防御对抗样本的攻击是当前研究对抗样本的重点问题.该文从对抗样本的概念、出现对抗样本的原因、对抗样本的攻击方式及原因阐述对抗样本的关键技术问题,对抗样本的概念主要是对对抗样本、对抗目标、对抗攻击所需知识的定义.该文列出了产生对抗样本的可能原因,目前,针对对抗样本出现的原因主要有三种观点:流形中的低概率区域解释,线性解释,此外,还有一种观点认为线性解释存在局限性,即当前的猜想都不能令人信服,进一步研究对抗样本出现的原因是未来重要的研究内容.并详细分析了对抗样本的几种典型生成方式:F-BFGS法、FGS法、迭代法、迭代最小可能类法及其它方法.并指出了其优缺点和适用的场景,比较了几种主要生成方式的不同之处.此外,对抗样本的攻击方式从应用场景上看主要分为两种,一种是白盒攻击,一种是黑盒攻击.对抗样本具有迁移性是对抗样本攻击的原因,该属性意味着攻击者可以不用直接接触基础模型,而选择攻击一个机器学习模型使样本被错误分类.针对对抗样本的攻击方式及原因,列出了目前深度学习中针对对抗样本的几种主要的防御技术:基于正则化方法、对抗性的预处理训练方法,蒸馏方法、拒绝分类方法等其它方法.指出了不同防御措施的适用场景与不足,阐释了上述防御措施均不能完全避免对抗样本的攻击.该文进一步探讨了对抗样本的应用,目前为止,对抗样本的应用主要是用在对抗评估及对抗训练上.最后,对对抗样本的未来研究方向进行了总体展望,彻底解决对抗攻击问题,仍有大量的理论和实践问题需要解决.找出对抗样本的特性,给出其具有实际应用前景的数学描述,探讨普适性的对抗样本生成方法,对抗样本的生成机�