您现在的位置是：首页 > 工业技术 > 自动化技术、计算机技术 > 《计算机学报》 > 2016年第01期

大数据时代,相关分析因其具有可以快捷、高效地发现事物间内在关联的优势而受到广泛的关注,并有效地应用于推荐系统、商业分析、公共管理、医疗诊断等领域.面向非线性、高维性等大数据的复杂特征,结合现有相关分析方法的语义分析,文中从统计相关分析、互信息、矩阵计算、距离4个方面对大数据相关分析的现有研究成果进行了梳理.在对统计学中的经典相关分析理论进行归纳、总结的基础上,文中从大规模数据的通用性和均等性视角阐述了基于互信息的两个变量间非线性相关分析理论,从高维数据可计算的角度分析了基于矩阵计算的相关系数,从非线性、高维性数据的复杂结构方面解析了基于距离的相关系数.进一步地,该文在对已有相关分析方法进行分析与比较的基础上,围绕高维数据、多变量数据、大规模数据、增长性数据及其可计算方面探讨了大数据相关分析的研究挑战.

MapReduce以其简洁的编程模型,被广泛应用于大规模和高维度数据集的处理,如日志分析、文档聚类和其他数据分析.开源系统Hadoop很好地实现了MapReduce模型,但由于自身采用一次分区机制,即通过Hash/Range分区函数对数据进行一次划分,导致在处理密集数据时,Reduce端常会出现数据倾斜的问题.虽然系统为用户提供了自定义分区函数方法,但不幸的是在不清楚输入数据分布的情况下,数据倾斜问题很难被避免.为解决数据划分的不均衡,该文提出一种将分区向Reducer指派时按照多轮分配的分区策略.该方法首先在Map端产生多于Reducer个数的细粒度分区,同时在Mapper运行过程中实时统计各细粒度分区的数据量;然后由JobTracker根据全局的分区分布信息筛选出部分未分配的细粒度分区,并用代价评估模型将选中的细粒度分区分配到各Reducer上;依照此方法,经过多轮的筛选、分配,最终在执行Reduce（）函数前,将所有细粒度分区分配到Reduce端,以此解决分区后各Reducer接收数据总量均衡的问题.最后在Zipf分布数据集和真实数据集上与现有的分区切分方法Closer进行了对比,增量式分区策略更好地解决了数据划分后的均衡问题.

BOD：一种高效的分布式离群点检测算法免费阅读下载全文

离群点检测是数据管理领域中的热点问题之一,在许多方面都有着广泛应用,如信用卡诈骗、网络入侵检测、环境监测等.目前现有的离群点检测算法大多针对集中式的处理环境.但随着数据规模的不断增长,传统的集中式算法处理效率受限,无法满足用户日益增长的需求.针对上述问题,文中提出了一种新型的分布式离群点检测算法.首先,在数据存储阶段（即预处理）,提出了BDSP（Balance Driven Spatial Partitioning）数据划分算法.该算法可以有效地均衡每个计算节点的工作负载,并实现良好的过滤效果.此外,为划分所得到的每个块设计了一种全新的编码方式,可以快速地确定块与块之间的相邻关系,降低网络开销.基于BDSP算法,提出了BOD（BDSP-based Outlier Detection）分布式离群点检测算法.该算法包括2个步骤：在每个计算节点本地,利用R树索引进行批量过滤,快速地计算离群点并得到本地候选集;利用BDSP中提供的块编码确定需要相互通信的节点,使用少量的网络开销得到最终结果.最后,通过大量实验验证了文中所提出的BDSP和BOD算法的有效性.实验结果表明,相对于现有算法,文中算法可以显著地提高计算效率并大幅降低网络开销.

基于隐式用户反馈数据流的实时个性化推荐免费阅读下载全文

大多数的传统推荐系统是基于用户评分构建,并采用离线批量的训练模式.该文研究以下两个问题：（1）基于隐式用户反馈构建推荐系统.与显式评分相比,隐式反馈存在范围更广且更易于收集;（2）基于反馈数据流进行实时推荐,以此来保障更强的推荐时效性.为了克服由隐式反馈本质特征导致的不平衡类标问题,直接对可观察的用户选择行为进行概率建模,在训练时无需引入负样本.为了提高训练效率并及时抓住用户兴趣的变化,该文提出的在线学习算法在强化学习用户新倾向的同时弱化了学习用户惯常行为与噪声,通过比较反馈发生概率与用户置信度来为每一个反馈动态调节学习步长.最后,该文设计了在线评价机制,并在两个真实数据集上进行了丰富的实验.实验结果验证了所提方法的有效性,并展示了其在推荐精度、推荐多样性、可解释性、训练效率、健壮性以及冷启动适应能力等多个方面的优势.

大数据驱动的自适应路由服务定制机制免费阅读下载全文

随着多种多样新型网络应用的涌现,传统的路由配置模式越来越难以适应用户多样化的数据通信需求.因此,需要依据用户对不同类型应用差异化的通信需求,在数据分组的传输路径上配置合适的路由功能,自适应地合成满足分组传输特性的路由服务,改善用户体验.根据由大数据带来的数据间关联关系新范式,文中试图从大量的应用通信流状态数据中,分析和获取用户体验与路由服务各属性之间的依赖关系,促进高效地实现路由服务的定制化.鉴于此,文中提出了大数据驱动的自适应路由服务定制机制（Big data driven Adaptive Routing service Customization scheme,BARC）,以网内大量流状态数据为驱动,建立了用户需求属性模型,挖掘用户体验对路由需求的依赖关系,获得候选路由功能集合;考虑商业化运营模式下用户和网络服务提供商之间的利益关系,提出了双方利益共赢的博弈策略,获得符合双方利益的最佳路由服务定制化方案.仿真实现和性能评价表明,文中提出的大数据驱动的自适应路由服务定制机制是可行和有效的.

分布式数据流关系查询技术研究免费阅读下载全文

随着在线分析连续数据流的需求日益增多,用于实时处理海量、易变数据的数据流管理系统由此产生.大数据时代下,随着开放式处理平台的发展,为处理大规模且多样化的数据流,出现了若干分布式流处理系统,如S4、Storm、Spark Streaming等.然而,为提升处理系统的易用性和处理能力,需要在其之上构建具有抽象查询语言的关系查询系统,以构筑完整的分布式数据流管理系统.如何设计并实现高效易用的关系查询系统是一个亟待解决的问题.文中首先概述了分布式数据流查询处理的典型应用、数据特征和实现目标.进而,提出了分布式数据流关系查询系统的基础架构,并基于此架构深入分析了用户自定义函数查询、查询优化、驱动方式、编译技术、算子管理、调度管理和并行管理等关键技术.然后,对比分析了SPL、StreamingSQL、Squall和DBToaster这4种具有代表性的查询系统实例.最后,指明了该技术在优化技术、执行策略、实时精准查询和复杂查询分析等方面所面临的挑战和今后的研究工作.

基于任务合并的并行大数据清洗过程优化免费阅读下载全文

数据质量问题会对大数据的应用产生致命影响,因此需要对存在数据质量问题的大数据进行清洗.MapReduce编程框架可以利用并行技术实现高可扩展性的大数据清洗,然而,由于缺乏有效的设计,在基于MapReduce的数据清洗过程中存在计算的冗余,导致性能降低.因此文中的目的是对并行数据清洗过程进行优化从而提高效率.通过研究,作者发现数据清洗中一些任务往往都运行在同一输入文件上或者利用同样的运算结果,基于该发现文中提出了一种新的优化技术——基于任务合并的优化技术.针对冗余计算和利用同一输入文件的简单计算进行合并,通过这种合并可以减少MapReduce的轮数从而减少系统运行的时间,最终达到系统优化的目标.文中针对数据清洗过程中多个复杂的模块进行了优化,具体来说分别对实体识别模块、不一致数据修复模块和缺失值填充模块进行了优化.实验结果表明,文中提出的策略可以有效提高数据清洗的效率.

增量式迭代计算模型研究与实现免费阅读下载全文

不动点迭代广泛存在于数据挖掘和机器学习算法中,这些算法已应用到诸如社会网络分析、高性能计算、推荐系统、搜索引擎、模式识别等诸多领域中.在云计算环境中,利用MapReduce编程模型所带来的便利,通过普通的PC集群运行相应的迭代算法,可以提高迭代算法的执行效率.但由于数据的快速变化,每当数据发生改变,整个迭代算法也需要重新运行,这将会导致大量的运算资源浪费和性能损失.文中研究基于原始迭代结果和新增数据的增量迭代计算DELTA（Delta data based incrEmentaL iTerAtive computing）,并提出DELTA模型以解决上述问题.文中理论证明了DELTA模型的正确性,阐述了其适用范围,并列举了PageRank、K-means和Descendant Query算法在DELTA模型中的运用.文中还扩展HaLoop为ΔHaLoop框架,使其支持增量式的迭代计算.通过一系列的测试用例,对DELTA模型功能、性能进行了分析和讨论,实验结果表明DELTA模型在获得准确的迭代结果的基础上性能优势明显.文中提出的DELTA模型能够适应多数迭代算法,对云计算环境下的迭代计算的应用和优化起到推动作用.

大数据驱动的网络信息平面免费阅读下载全文

随着互联网逐步深入人类的生活,人们对互联网的服务质量提出了更高的要求,这给互联网带来了巨大的挑战：一是移动网络、空间网络等异构网络以及各种异构终端的接入,网络规模不断扩大,导致网络服务管理复杂;二是互联网新应用的出现,给网络服务提出了更高的要求.但是,由于网络和应用缺乏相互的感知,严重影响了网络质量的提高.为了解决网络与应用相互独立的问题,需要建立网络信息平面来沟通网络和应用以提高网络服务质量.随着SDN（Software-Defined Networking）等网络新技术的发展和大数据思想深入影响到互联网的架构和通信模式,在网络架构中融入大数据驱动的网络信息平面以及密集计算驱动的分析方法已成为重要的研究方向.在现有的网络中,利用测量数据构建网络服务平台并通过数据驱动的方式优化网络资源的管理效率和提升用户体验,也成为当前工业界和学术界关注的热点.文中首先分析了网络信息平面构建的必然性,然后提出了一种大数据驱动的网络信息平面架构,分析了信息平面研发中面临的三大难题,最后,对解决这些难题提出了一些想法和建议.

HiBase：一种基于分层式索引的高效HBase查询技术与系统免费阅读下载全文

大数据时代,众多应用领域的数据量爆炸式增长,迫切需要研究和寻找有效的大数据存储管理方法,提供实时或准实时的大数据查询分析能力.Hadoop HBase系统为大数据的存储管理提供了一种具有高可扩展性的技术方法和系统平台.然而HBase只有主键索引,不支持非主键索引,这导致HBase的数据查询效率较低,难以满足数据实时或准实时查询需求.为此,在HBase基础上提供面向非主键的快速查询能力,是目前Hadoop环境下急需研究和解决的一个重要问题.该文研究提出了一种基于分层式HBase非主键索引的查询模型和方法,该模型和方法首先建立基于HBase的持久性索引.然后,为了利用内存提升查询性能,该文进一步提出了一种索引热点数据缓存技术和一种高效的热度累积缓存替换策略,以降低对HBase索引表的磁盘访问开销.热度累积缓存替换策略克服了最近最少使用（LRU）算法的局限性,考虑数据访问的累积热度和时间局部特性,从而更准确地捕获数据访问的特征.为了使索引热点数据缓存内存层具有良好的可扩展性,HiBase设计了基于一致性哈希的分布式内存缓存,支持高效的基于非主键的单点查询和范围查询.最终,该文设计实现了完整的分层式索引和查询系统HiBase.在千万至十亿条记录规模数据集上的测试结果表明,HiBase冷查询响应时间比标准HBase快65倍（大结果集）到3000多倍（小结果集）;而引入基于查询热度累积算法的内存索引缓存方法后,热查询性能可在HiBase冷查询基础上再提升5~15倍,使得总体查询性能比标准HBase快300多倍（大结果集）到1.7万倍（小结果集）,比开源的Hindex系统快5~20倍.

可信固态硬盘：大数据安全的新基础免费阅读下载全文

大数据平台,因其数据多、价值高和存储集中的特点,已经成为对攻击者非常有吸引力的目标.因此,大数据安全是一个非常重要的研究课题.然而,当前保障大数据平台（如Hadoop）数据安全的两种常见方法各有不足：（1）访问控制.存在被外部黑客攻破或内部管理员绕过的风险;（2）数据加密.虽然安全性较高,但加密解密海量数据会增加显著开销.为了同时满足大数据应用对数据存储的高安全和高性能要求,文中提出可信固态硬盘（TrustedSSD）,它提供安全增强的存储设备接口和协议,使得用户可以对存储中的数据施以细粒度的访问控制,从而保障存储中数据的安全.文中深入分析了可信固态硬盘的安全性,并详细介绍了系统设计与实现中的挑战和应对.实验结果表明,无论是在合成的还是真实的工作负载上,可信固态硬盘的运行开销不到3%.因此,可信固态硬盘有望成为大数据安全的新基础.

一种面向大规模社会信息网络的多层社区发现算法免费阅读下载全文

社区发现旨在挖掘社会信息网络的社区结构,是社会计算及其相关研究的基础.随着交互式社会信息网络规模的快速增长,传统的社区发现算法难以满足大规模网络的可扩展分析需求.多层社区发现算法如PMetis、Graclus等虽然可以分析包含数百万节点规模的网络,但是小于2的粗化缩减比率以及社会信息网络的幂律分布特性极大地制约着该类算法的性能优势.该文提出了一种基于三角形内点同一社区性粗化策略的多层社区发现算法TMLCD.TMLCD不仅以大于2的粗化缩减比率加快了大规模社会信息网络的粗化过程,而且从基本拓扑结构上保持了初始网络的社区效应,提高了社区发现精度.基于YouTube、Orkut等真实网络的实验结果表明：TMLCD在计算精度、内存占用以及运行时间方面的性能均优于目前典型的多层社区发现算法,适用于富含三角形的社会信息网络分析.

利用社交关系的实值条件受限玻尔兹曼机协同过滤推荐算法免费阅读下载全文

利用受限玻尔兹曼机（Restricted Boltzmann Machine,RBM）解决推荐问题已成为一个很有意义的研究方向.目前用于推荐的RBM模型中使用的仅仅是用户评分数据,但用户评分数据存在着严重的数据稀疏性问题.随着互联网对人们生活的不断渗透,社交网络已经成为人们生活中不可缺少的一部分,利用社交网络中的好友信任关系,有助于缓解评分数据的稀疏性问题,提高推荐系统的性能.因此,该文首先提出基于实值的状态玻尔兹曼机（Real-Valued Conditional Restricted Boltzmann Machine,R_CRBM）模型,此模型不需要将评分数据转化为一个K维的0-1向量,并且R_CRBM模型在训练过程中使用了训练数据中潜在的评分/未评分信息;同时该文将最近信任好友关系应用到R_CRBM模型推荐过程中.在百度数据集和Epinions数据集上的实验结果表明R_CRBM模型和引入的最近信任好友关系均有助于提高推荐系统的预测精度;最后,针对大数据环境下,普通平台很难完成R_CRBM模型训练的问题,该文提出基于Spark的并行化方案,较好地解决了该问题.

BigDataBench：开源的大数据系统评测基准免费阅读下载全文

大数据系统的蓬勃发展催生了大数据基准测试的研究,如何公正地评价不同的大数据系统以及怎样根据需求选取合适的系统成为了热点问题.然而,应用领域的广泛性、数据类型的多样性和数据操作的复杂性使得大数据基准测试集的设计面临很大的挑战.现有的相关基准测试工作要么针对某一类特定的应用或软件栈,要么根据流行度主观地选择大数据负载,难以全面覆盖大数据的多样性和复杂性.针对现有工作的不足,文中讨论大数据评测基准需要满足的需求,并研制了一个跨系统、体系结构、数据管理3个领域的大数据基准测试开源程序集——BigDataBench.它覆盖5个典型的应用领域（搜索引擎、电子商务、社交网络、多媒体、生物信息学）,包含结构化、半结构化、非结构化的数据类型,涵盖离线分析、交互式分析、在线服务、NoSQL这4种负载类型.目前包含14个真实数据集、3种类型的数据生成工具以及33个负载的不同软件栈实现.BigDataBench已广泛应用到学术界和工业界中,应用案例包括负载分析、体系结构设计、系统优化等.基于BigDataBench,中国信息通信研究院联合中国科学院计算技术研究所、华为等国内外知名公司和科研机构共同制定了国内首个工业标准的大数据平台性能评测标准.

类脑智能研究的回顾与展望免费阅读下载全文

人工智能学科诞生以来,实现人类水平的智能系统便是本学科探索的长期目标.然而经历了近60年的发展,目前还没有任何一个通用智能系统能够接近人类水平：具有协同多种不同的认知能力;对复杂环境具备极强的自适应能力;对新事物、新环境具备自主学习的能力等.随着脑与神经科学、认知科学的发展,在不同尺度观测各种认知任务下脑神经网络的部分活动并获取相关数据已成为可能.因此,受脑工作机制启发,发展类脑智能成为近年来人工智能与计算科学领域研究的热点.类脑智能是以计算建模为手段,受脑神经机制和认知行为机制启发并通过软硬件协同实现的机器智能.类脑智能系统在信息处理机制上类脑,认知行为和智能水平上类人,目标是使机器实现各种人类具有的多种认知能力及其协同机制,最终达到或超越人类智能水平.文中将从脑科学、认知科学、人工智能研究交叉的视角回顾与类脑智能研究有关的历史、现状与研究焦点,并展望该研究领域的发展方向、可能的应用领域及其潜在的深远影响.