1、并行计算多核/众核单核处理器设计达到单核处理器设计达到极限,极限,2005年年Intel多多核处理器战略转移核处理器战略转移体系结构与体系结构与处理器技术处理器技术行业需求行业需求行业大数据应用需求2009-2010年开始,年开始,行业应用规模和数行业应用规模和数据量急剧增长据量急剧增长影响现有计算技术各个层面:体系结构分布并行计算算法设计数据库操作系统程序设计语言应用技术MapReduce2004年年Google发发明明MapReduce海量海量数据并行处理技术,数据并行处理技术,07年年Hadoop推广推广并行处理并行处理技术方法技术方法大数据Wiki百科百科:big data is a
2、collection of data sets so large and complex that it becomes difficult to process using on-hand database management tools 大数据意指一个超大的、难以用现有常规的数据库管理技术和工具处理的数据集IDC报告:Big data technologies describe a new generation of technologies and architectures, designed to economically extract value from very large
3、 volumes of a wide variety of data, by enabling high-velocity capture, discovery, and/or analysis. 大数据技术描述了一种新一代技术和构架,用于以很经济的方式、以高速的捕获、发现和分析技术,从各种超大规模的数据中提取价值大数据(Big Data)应用需求 出现越来越多的大数据应用和行业需求。2008年,在Google成立10周年之际,Nature杂志出版一期专刊专门讨论未来的大数据(Big Data)处理相关的一系列技术问题和挑战。未来10多年数据将急剧增长IDC研究报告研究报告Data Unive
4、rse Study提出“数据宇宙”的说法描述海量数据2007年2008年2009年2010年2011年未来急剧增长的数据迫切需要寻求新的处理技术手段IDC报告报告Data Universe Study全世界权威IT咨询公司研究报告预测:全世界数据量未来10年将从2009年的0.8ZB增长到2020年的35ZB,增长44倍!年均增长率40%!美国联邦政府下属的国防部、能源部、卫生总署等7部委联合推动,于2012年3月底发布了大数据研发专项研究计划 (Big Data Initiative),拟投入2亿美元用于研究开发科学探索、环境和生物医学、教育和国家安全等重大领域和行业所急需的大数据处理技术和
5、工具,把大数据研究上升到为国家发展战略。7“大数据研究的科学价值”李国杰,中国计算机学会通讯,vol. 8,no.9, 2012.92012年3月,美国奥巴马政府宣布投资2亿美元启动“大数据研究和发展计划”,这是继1993年美国宣布“信息高速公路”计划后的又一次重大科技发展部署。美国政府认为大数据是“未来的新石油”,将“大数据研究”上升为国家意志,对未来的科技与经济发展必将带来深远影响。一个国家拥有数据的规模和运用数据的能力将成为综合国力的重要组成部分,对数据的占有和控制也将成为国家间和企业间新的争夺焦点。8数据科学(Data Science) 国内外出现了“数据科学”的概念 l 图灵奖获得者
6、Jim Gray: 2007年最后一次演讲中提出“数据密集型科学发现(Data-Intensive Scientific Discovery)” 将成为科学研究的第四范式 实验科学 理论科学 计算科学 数据科学l世界著名存储技术公司EMC:提出了“Data Science”的概念,“Data Science teams will become the driving force for success with big data analytics” l 李国杰院士:“数据科学”研究的对象是什么?计算机科学是关于算法的科学,数据科学是关于数据的科学。9大数据将带来巨大的技术和商业机遇 大数据分
7、析挖掘和利用将为企业带来巨大的商业价值原始信息行业数据知识报表制图电子文档信息检索数据仓库海量分析知识挖掘信息化技术大数据分析应用数据规模急剧增加,传统计算面临严重挑战l中国移动一个省电话通联记录(CDR)数据每月可达0.5-1PB,而整个中国移动每月则高达7-15PB数据;如此巨大的数据量使得Oracle等数据库系统已经难以支撑和应对l南京市公安局320道路监控云计算系统,数据量为三年200亿条、总量120TB的车辆监控数据l百度存储数百PB数据, 每天处理数据10PBl淘宝存储14PB交易数据, 每天新增数据40-50TB11大规模数据处理和行业应用需求日益增加和迫切出现越来越多的大规模数
8、据处理应用需求,传统系统难以提供足够的存储和计算资源进行处理,云计算技术是最理想的解决方案。调查显示:目前,IT专业人员对云计算中诸多关键技术最为关心的是大规模数据并行处理技术大数据并行处理没有通用和现成的解决方案对于应用行业来说,云计算平台软件、虚拟化软件都不需要自己开发,但行业的大规模数据处理应用没有现成和通用的软件,需要针对特定的应用需求专门开发,涉及到诸多并行化算法、索引查询优化技术研究、以及系统的设计实现海量数据隐含着更准确的事实研究发现:大数据量可显著提高机器学习算法的准确性;训练数据集越大,数据分类精度越高;大数据集上的简单算法能比小数据集上的复杂算法产生更好的结果,因此数据量足
9、够大时有可能使用代价很小的简单算法来达到很好的学习精度。 例如,2001年,一个基于事实的简短问答研究, 如提问:Who shot Abraham Lincoln?在很大的数据集时,只要使用简单的模式匹配方法,找到在“shot Abraham Lincoln”前面的部分即可快速得到准确答案:John Wilkes Booth 大数据特点: 5V Volume: 大容量 Variety: 多样性 Velocity: 时效性 Veracity: 准确性 Value: 大价值 VeracityVarietyVelocityVolumeValue 结构特征 结构化数据 非结构化/半结构化数据 获取和处
10、理方式静态(线下数据)/非实时数据动态(流式/增量式/线上)/实时数据 关联特征 无关联/简单关联数据(键值记录型数据) 复杂关联数据(图数据)Data connectednessData sizeTypical RDBMSSQL Comfort ZoneDisk-based Key-value StoreColumn StoreDocument StoreGraph DB引自微软亚洲研究院,王海勋 大数据问题的基本特点 极强的行业应用需求特性 规模极大,超过任何传统数据库系统的处理能力 技术综合性、交叉性很强 大多数传统算法面临失效,需要重写 大数据研究的基本原则 应用需求为导向: 以行业应
11、用问题和需求为导向 领域交叉为桥梁:行业、IT产业、学术界协同 计算技术为支撑:研究解决涉及的计算技术问题以有效的信息技术手段和计算方法,获取、处理和分析各种应用行业的大数据,发现和提取数据的内在价值,为行业提供高附加值的应用和服务 技术手段:信息技术和计算方法 核心目标:价值发现 效益目标:形成高附加值智能化行业应用 大数据研究的挑战 数据规模导致难以应对的存储量 数据规模导致传统算法失效 大数据复杂的数据关联性导致高复杂度的计算 大数据研究的基本途径三个基本途径: 寻找新算法降低计算复杂度 降低大数据尺度,寻找数据尺度无关算法 大数据并行化处理 大数据研究的基本途径新算法寻找新算法降低计算
12、复杂度降低尺度寻找数据尺度无关近似算法并行化分而治之并行化处理 从信息处理系统视角以信息系统视角来划分大数据研究层面l 体现大数据系统研发所涉及的各个层面和问题l 同时兼顾产业、学术和应用行业共同关注的问题基础设施系统平台算法应用集群, 众核, GPU, 混合式构架 (如集群+众核, 集群+GPU)云计算资源与支撑平台大数据查询(SQL, NoSQL, 实时查询, 线下分析)大数据存储(DFS, HBase, RDFDB, MemDB, RDB)大数据预处理MapReduce, BSP, MPI, CUDA, OpenMP, 定制式,混合式 (如MapReduce+CUDA, MapReduc
13、e+MPI)并行化机器学习与数据挖掘算法社会网络,排名与推荐,商业智能,自然语言处理,生物信息媒体分析检索, Web挖掘与检索, 3维建模与可视化计算电信/公安/商业/金融/遥感遥测/勘探/生物医药领域应用/服务需求和计算模型分析工具/开发环境和工具/行业应用系统开发角色行业用户领域专家应用开发者计算技术研究和开发者研究层面大数据行业应用/服务层应用开发层应用算法层基础算法层并行编程模型与计算框架层大数据存储管理层并行构架和资源平台层应用层算法层系统层构架层集群, 多核, GPU, 混合式构架 (如集群+多核, 集群+GPU)云计算资源和服务支撑平台大数据查询(SQL, NoSQL, 实时查询
14、, 线下分析)大数据存储(DFS, HBase, MemDB, RDB)大数据预处理MapReduce, BSP, MPI, CUDA, OpenMP, 定制式,混合式 (如MapReduce+CUDA, MapReduce+MPI)并行化机器学习和数据挖掘算法社会网络,排名与推荐,商业智能,自然语言处理,生物信息媒体分析检索, Web挖掘与搜索, 3维建模与可视化电信/公安/商业/金融/遥感遥测/勘探/生物医药领域应用/服务需求和计算模型行业应用系统开发纵向方式:上下层交叉组合单一层面的研究往往难以获得理想的综合解决方案,上下层交叉组合可以获得理想的综合解决方案,能发现很多新的研究点一、大数
15、据存储管理和索引查询二、Hadoop性能优化和功能增强三、并行计算模型和框架四、并行化机器学习和数据挖掘算法五、社会网络分析六、Web信息搜索和排名推荐七、媒体分析检索八、基于本体的语义分析与挖掘九、大数据自然语言处理智能化应用十、大数据可视化计算与分析系统层基础算法典型/共性应用算法与技术 大数据预处理技术 大数据的采集和传输 大数据的清洗过滤和质量管理技术 大数据的压缩技术 记录型大数据索引和查询技术 静态记录型大数据索引技术 流式/增量式记录型大数据索引技术 大数据表的高效关系型操作 (如查询连接) 大数据并行化查询技术 SQL/NoSQL查询语言接口与技术 SQL/NoSQL查询语言接
16、口 并行化查询执行机制 图数据表示和查询技术 静态图数据的表示和存储 静态图数据的查询 流式/增量式图数据的表示和存储 流式/增量式图数据的查询 图数据并行化查询技术 混合式数据表示和存储管理模型 NoSQL数据库技术 结构化/半结构/非结构化数据混合存储管理模型 混合式数据下的数据关系和查询操作技术 分布式数据库 HBase性能优化 基于HBase的大数据索引和查询技术 分布式内存数据库存储技术 (Google的Dremel,MemSQL,Hana IMDB,Redis) 大规模RDF语义数据库 基于Hbase的大规模RDF数据存储管理 SPARQL大规模语义数据查询及并行化算法 基于RDF
17、S/OWL的大规模语义推理并行化算法 分布式文件系统 HDFS的优化1.基于HBase的大数据索引与查询技术问题:HBase缺少类似于RDB中的索引创建能力,通过Hive转换为MapReduce程序处理Hbase中的数据性能很慢本课题组正在研究基于HBase和混合树模型的大数据索引和并行化查询技术和算法,并利用HBase和CoProcessor、以及分布式内存数据库完成查询加速。2.基于HBase的大规模RDF语义数据库问题:大数据文本和媒体数据语义的分析和挖掘需要提供大规模RDF语义数据存储管理和查询系统本课题组正在研究基于HBase和分布式内容数据库的大规模RDF语义数据库系统 MapRe
18、duce Hadoop性能优化 针对作业、任务和Slot资源的调度优化 (Intel-Hadoop, IBM的AMapReduce, Facebook的Corona) 针对I/0的优化、针对充分利用内存的优化(Berkeley的Spark) 针对流程的优化 (优化Shuffle过程 、SHadoop) MapReduce并行计算框架改进 迭代式MapReduce执行框架 (Twister, HaLoop) 流式MapReduce执行框架 (Hadoop Online)1.Hadoop系统性能优化问题:Hadoop最初是为批量数据线下处理设计,当使用Hadoop进行大数据存储和实时查询分析处理时
19、,其响应性能不够,因此Hadoop性能优化一直是大家关注的热点研究问题。本课题组进行了Hadoop MapReduce框架的性能优化研究:1).研究设计了新的作业和任务处理机制及任务调度通信机制,实验结果显示,Benchmark程序执行性能提升达到约30%。该项成果经过集成和测试目前已经集成到 Intel Distributed Hadoop(IDH)产品中2).研究了基于资源环境和作业开销感知的Hadoop作业调度优化技术,可实现动态的Slot调度和均衡的作业调度优化 MapReduce Hadoop性能优化 针对作业、任务和Slot资源的调度优化 针对I/0的优化、针对充分利用内存的优化
20、针对流程的优化 MapReduce并行计算框架改进 迭代式MapReduce执行框架 (Twister, HaLoop) 流式MapReduce执行框架 (Hadoop Online) BSP (Bulk Synchronized Parallel) 基于BSP模型的并行处理框架 大规模图数据并行处理框架和系统 Google的Pregel 微软的Trinity 定制式并行计算框架 全内存集群计算 (Bakerley Spark) 大规模流式数据处理 (Twitter Storm, Yahoo S4) 特定应用问题的定制式并行计算框架 混合式并行计算模型和框架 MapReduce+CUDA并行计
21、算框架的设计与优化 MapReduce+MPI和MapReduce+BSP并行计算框架设计优化1. 基于Intel Xeon Phi众核协处理系统MIC的BSP编程模型和示范应用研究 Intel最新推出商用众核协处理器Intel Xeon Phi5761核,以高速 环形结构互联商用级众核处理器通用计算能力价格:$2000-26501. 基于Intel Xeon Phi众核协处理系统MIC的BSP编程模型研究和示范应用研究 包括三个层面的工作: 基于MIC的BSP并行 计算模型研究 机器学习并行 化算法研究 两个并行化示范应用大规模图像检索+机器翻译系统Host ProcessorIntel X
22、eon E5-26XXPCIeXeon Phi MIC 0Xeon Phi MIC 1MPIOpenMPBSPParallelized Machine Learning and NLP AlgorithmsImage Retrieval/Detection Machine TranslationDemo ApplicationsParallel ML & NLP AlgorithmsParallel Programming ModelsMIC-BasedParallelComputingHardware Platform2. 混合式并行计算模型和框架研究l MapReduce + MIC(或G
23、PU)的混合式并行计算模型和框架研究 问题:在视频或图像内容分析应用中,面向大规模媒体数据分析处理时,单一的MapReduce构架和模型不足以胜任,需要采用MapReduce调度媒体片段或文件的处理、同时采用MIC或GPU对本地的数据密集型媒体处理进行并行化加速处理 需要在MapReduce模型和框架基础上开发对局部数据用MIC或GPU加速处理的编程接口和框架l 基于Hadoop + 内存数据库的混合式并行计算模型和框架研究 对某些对响应性能要求很高的应用,需要考虑基于内存数据库进行加速 如:我们进行了基于内存数据库的在线机器翻译并行化算法研究和系统开发 3. 定制式并行计算模型和框架 问题:
24、对机器学习和数据挖掘中的很多算法,现有的MapReduce或其他并行计算框架可能既过于庞大、适用性也不好,需要研发轻量级的、更加适用、效率更高的定制式并行计算框架例如:我们基于Hadoop的基础构架和底层的RPC协议自行研发了面向神经网络学习的轻量级定制式并行计算框架,提供基于分布内存的快速迭代计算机制和并行计算能力大数据并行化机器学习和数据挖掘算法大数据处理并行化学习和挖掘算法不同并行模型下并行化学习和挖掘算法并行化机器学习和数据挖掘工具和平台 研究表明:基于大数据集的机器学习会取得更好的学习效果,这已经成为目前机器学习领域的共识 分类算法 (Classification) 大规模支持向量机
25、 (Large Scale SVM) 神经网络 (Neural Network) 朴素贝叶斯 (Nave Bayes) 决策树 (Decision Trees) 聚类 (Clustering) 关联规则挖掘 参数估计 (Parameters Estimation) 高维度数据降维 (Dimension Reduction) 集成学习 (Ensemble Learning ) 图数据算法 图聚类,图分类,图模式匹配(子图同构、最大公共子图)1. 基于MapReduce的K-Means并行化算法输入:输入:待聚类的N个数据点,期望生成的聚类的个数K输出:输出:K个聚类算法描述算法描述: 选出K个点
26、作为初始的cluster center Loop: 对输入中的每一个点p: 计算p到各个cluster的距离; 将p归入最近的cluster; 重新计算各个cluster的中心 如果不满足停止条件,goto Loop; 否则,停止1. 基于MapReduce的K-Means并行化算法Map阶段的处理 在Map类的初始化方法setup中读取全局的聚类中心信息 对Map方法收到的每一个数据点p,计算p与所有聚类中心间的距离,并选择一个距离最小的中心作为p所属的聚类,输出键值对 对每个Map节点上即将传递到Reduce节点的每一个键值对,用Combiner进行数据优化,合并相同ClusterID下的
27、所有数据点并求取这些点的均值pm以及数据点个数n1. 基于MapReduce的K-Means并行化算法Mapper伪代码class Mapper setup() 读出全局的聚类中心数据读出全局的聚类中心数据 Centers map(key, p) / p为一个数据点为一个数据点 minDis = Double.MAX VALUE; index = -1; for i=0 to Centers.length dis= ComputeDist(p, Centersi); if dis minDis minDis = dis; index = i; emit(Centersi.ClusterID,
28、p); 1. 基于MapReduce的K-Means并行化算法Combiner伪代码class Combiner reduce(ClusterID, p1, p2, ) pm = 0.0; n = 数据点列表p1, p2, 中数据点的总个数; for i=0 to n pm += pi; pm = pm / n; / 求得这些数据点的平均值 emit(ClusterID, (pm, n); 2.K-最近邻(KNN)分类并行化算法基本算法设计思想 K-最近邻是分类器算法中最通俗易懂的一种,计算测试样本到各训练样本的距离,取其中距离最小的K个,并根据这K个训练样本的标记进行投票得到测试样本的标记。
29、 加权K-最近邻分类算法的思路是,在根据测试样本的标记进行投票表决时,将根据测试样本与每个训练样本间距离(或相似度)的大小决定训练样本标记的作用大小,基本原则是:距离越近的训练样本其标记的作用权重越大,反之则越小。据此,可以建立一个带加权的投票表决计算模型(比如y = Si*yi/Si, k=0,k-1,Si为取值0-1的相似度数值,yi为选取出的最邻近训练样本的分类标记值)决定以最终的测试样本的分类标记。 算法的思路清晰简单,然而对于海量数据计算量很大,耗费时间较长。2.K-最近邻(KNN)分类并行化算法MapReduce并行化算法设计思路基本处理思路是:将测试样本数据分块后分布在不同的节点
30、上进行处理,将训练样本数据文件放在DistributedCache中供每个节点共享访问Map阶段对每个读出的测试样本数据ts(trid,A,y)计算其与每个训练样本数据tr(trid,A,y)之间的相似度S=Sim(A,A)(1:相似度最大,0:相似度最小)检查S是否比目前的k个S值中最小的大,若是则将(S,y)计入k个最大者根据所保留的k个S值最大的(S,y),根据模型y =Si*yi/Si计算出ts的分类标记值y,发射出(tsid, y)Reduce阶段直接输出(tsid, y)2.K-最近邻(KNN)分类并行化算法Mapper伪代码class Mapper setup() 读取全局训练样
31、本数据文件,转入本地内存的数据表读取全局训练样本数据文件,转入本地内存的数据表TR中中 map(key, ts) / ts为一个测试样本为一个测试样本 MaxS (k) ts tsid, A, y for i=0 to TR.lenghth) TRi tr, A S = Sim(A, A); 若S属于k个最大者, (S, y) MaxS; 根据MaxS和带加权投票表决模型计算出y emit(tsid, y) 3.频繁项集挖掘并行化算法 本研究组进行了基于MapReduce的频繁项集挖掘算法研究 基本思路是基于传统的Apriori算法和SON算法,提出并实现了一个并行化的频繁项集挖掘算法PSON
32、,用两轮MapReduce实现了大规模频繁项集挖掘并行计算研究论文,发表于PAAP2011国际会议PSON: A Parallelized SON Algorithm with MapReduce for Mining Frequent Sets Tao Xiao, Shuai Wang, Chunfeng Yuan, Yihua Huang The Fourth International Symposium on Parallel Architectures, Algorithms and Programming (PAAP 2011), Tianjin,Dec. 9-11, 2011Fr
33、equent setsSuppose I is an itemset consisting of items from the transaction database D Let N be the number of transactions D Let M be the number of transactions that contain all the items of I M /N is referred to as the support of I in D Example Here, N = 4, let I = I1, I2, than M = 2 because I = I1
34、, I2 is contained in transactions T100 and T400 so the support of I is 0.5 (2/4 = 0.5)If sup(I) is no less that an user-defined threshold, then I is referred to as a frequent itemsetGoal of frequent sets mining To find all frequent k-itemsets from a transaction database (k = 1, 2, 3, .)枚举计算的时间复杂度是:O
35、(2n*N*t), n是Item的总数,N是Transaction总数,t是每个Transaction平均包含的Item数SON Algorithm*Basic idea Divide the whole database into several non-overlapping partitions For each partition, discover all the frequent itemsets for it (referred to as local frequent itemsets) Merge all the local frequent itemsets from al
36、l the partitions (referred to as global candidate itemsets) Remove those that are not actually frequent in the whole database, generating global frequent itemsetsLemma An itemset that is not local frequent in any of the partitions cannot be global frequent A global frequent itemset must appear as lo
37、cal frequent in at least one of the partitions* A. Savasere, E. Omiecinski, and S. Navathe, “An efficient algorithm for mining association rules in large databases,” in proceedings of the 21st VLDB Conference Zurich, Swizerland, 1995PSON: Parallelized SON AlgorithmMotivation to Parallelize SON Proce
38、ssing one partition doesnt need any information from any other partition Each partition can be processed concurrently SON is naturally suitable for parallelization Preparing data Store the transaction database into DFS The whole database will be automatically divided into several non-overlapping chu
39、nks Chunks correspond to the partitions in SONMap tasks Each chunk is processed by one mapper node to find local frequent itemsets for that chunkReduce tasks Local frequent itemsets of the same length are processed by one reduce node Each node counts for each global candidate itemset it receives Thu
40、s decides which are global frequent itemsetsRun two MapReduce jobs to generate all frequent itemsets 1st job: generate all global candidate itemsets 2nd job: identify global frequent itemsets from global candidate itemsetsThe 1st MapReduce JobMap phase Each map node takes in one partition and genera
41、tes local frequent itemsets for that partition using Apriori algorithm. For each local frequent itemset F, emits key-value pair . Here, the value 1 is only to indicate that F is a local frequent itemset for that partition.Shuffle and Sort phase The same local frequent itemsets are sent to one reduce
42、 node.Reduce phase Each reduce node emits one and only one key-value pair to DFSFinally Merging all the pairs in DFS gives us all global candidate itemsetsThe 2nd MapReduce JobAssumption Each node is given a full duplicate of the global candidate itemsets generated by the 1st MapReduce job beforehan
43、dMap phase Each map node counts for each of the global candidate itemsets in the partition the map node is assigned Then emits pairs like where C is a global candidate itemset and v is the count of it in that partitionShuffle and Sort phase Each global candidate itemset and its counts in all the par
44、titions are sent to one reduce nodeReduce phase For each global candidate itemset C, reduce node adds up all the associative counts for C and emits only the actual global frequent itemsets to DFSExperimental ResultsThe transaction database size varies from 6GB to 60GB,with the number of transactions
45、 varies from 1 million to 500 billionConclusion: When the size of the database reaches a threshold of hundreds of GB, PSON can finish running in an acceptable period of time,achieving a good performance in scale-upPSON can achieve a good performance in speed-up4.大规模短文本多分类并行化算法 本研究组进行了基于MapReduce的查询短
46、文本分类并行化算法研究。提供了1万条已经标注出所属类别作为训练样本,一共有480个类别。原始数据有1000万条查询短文本,其中有少数不属于这480类的异类测试样本,需要对这些大量的短文本进行分类,并能标识出不属于以上480类的异类样本。本研究项目为本系研究生组队参加2012年中国第一届“云计算与移动互联网大奖赛”的指定的4个大数据并行处理赛题之一,经过角逐获得1、2、3等奖各一项。4.大规模短文本多分类并行化算法本道题目是高维稀疏空间文本的分类问题。由于大量实践证实SVM 针对高维空间数据训练效果较好,而且分类器的速度较快,因此我们使用了linear SVM进行处理l 训练阶段,对于多类(48
47、0 类)问题,为了提高分类精度,我们针对每个类做了一个两类分类器;同时为了能识别出异类样本,我们用每个类别下的标注样本训练出一个OneClassSVM分类器l 预测阶段,分别用480 个分类器对每个待预测的样本进行分类并打分,选择打分最高的类别作为该样本可能的预测类别;并用OneClassSVM对该测试样本做一个异类样本排除l 为了提升训练和分类速度, 上述所有算法都在MapReduce 框架下实现。 4.大规模短文本多分类并行化算法4.大规模短文本多分类并行化算法OneClassSVM排除异类5.神经网络并行化算法 本研究组基于Hadoop基础构架和底层RPC远程过程调用通信,采用分布内存式
48、数据缓存机制,为经典的BackPropagation神经网络算法研究设计了一个定制的轻量级专用并行化计算框架,并最终设计实现了并行化的BackPropagation神经网络算法。神经网络需要经过数万至数十万轮的迭代计算,计算量巨大。由于实现了并行化算法,大大缩短了训练时间,本课题进行了800万超大训练样本的神经网络训练并行化计算测试。5.神经网络并行化算法 5.神经网络并行化算法 MapReduce显然不适合做这样大量的迭代运算,因此需要设计定制式的轻量级并行计算框架。基本思路是把全部样本划分为子集给各个节点分别进行处理5.神经网络并行化算法 基本算法思路是把整个样本数据划分到各个计算节点上完
49、成计算,然后计算误差和权重差值W,汇总并更新权重W后继续迭代计算,直至达到结束条件5.神经网络并行化算法 5.神经网络并行化算法 Comparison of each epochs training time cost in cNeural and Hadoop with different number of computing nodes on 1 million training samples.Performance of each epochs training time cost in cNeural with various numbers of computing nodes
50、and various sizes of training samples6.查询推荐QUBIC并行化算法 本研究组进行了基于MapReduce的查询推荐QUBIC并行化算法。基本思路是基于用户日志设计查询推荐算法,首先挖掘用户日志中Query与URL之间的关系,寻找Query中若干关联性较大的组,最后基于MapReduce并行构造Query-URL二部图和查询亲和图QAG,在此基础上最终完成查询词的聚类,并以此为基础推荐查询关键词 肖滔,硕士研究论文,2012l社团发现 ( Community Detection )l网络建模 (Network Modeling )l中心分析和影响力建模 (