大数据热点研究问题和典型研究介绍黄宜华2013420

1、大数据热点研究问题和典型研究介绍黄 宜 华南 京 大 学计算机科学与技术系软件新技术国家重点实验室2013.4.20,南京1.多核、并行计算与大数据并行计算多核/众核单核处理器设计达到极限，2005年Intel多核处理器战略转移体系结构与处理器技术行业需求行业大数据应用需求2009-2010年开始，行业应用规模和数据量急剧增长影响现有计算技术各个层面:体系结构分布并行计算算法设计数据库操作系统程序设计语言应用技术MapReduce2004年Google发明MapReduce海量数据并行处理技术，07年Hadoop推广并行处理技术方法大数据2.Wiki百科：big data is a colle

2、ction 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 volu

3、mes of a wide variety of data, by enabling high-velocity capture, discovery, and/or analysis. 大数据技术描述了一种新一代技术和构架，用于以很经济的方式、以高速的捕获、发现和分析技术，从各种超大规模的数据中提取价值什么是大数据？3.大数据处理技术的重要性大数据(Big Data)应用需求 出现越来越多的大数据应用和行业需求。2008年，在Google成立10周年之际，Nature杂志出版一期专刊专门讨论未来的大数据（Big Data）处理相关的一系列技术问题和挑战。4.未来10多年数据将急剧增长IDC研

4、究报告Data Universe Study提出“数据宇宙”的说法描述海量数据2007年2008年2009年2010年2011年大数据处理技术的重要性5.大数据处理技术的重要性未来急剧增长的数据迫切需要寻求新的处理技术手段IDC报告Data Universe Study全世界权威IT咨询公司研究报告预测:全世界数据量未来10年将从2009年的0.8ZB增长到2020年的35ZB,增长44倍!年均增长率40%!6.美国联邦政府发布大数据研发专项研究计划美国联邦政府下属的国防部、能源部、卫生总署等7部委联合推动，于2012年3月底发布了大数据研发专项研究计划 (Big Data Initiativ

5、e)，拟投入2亿美元用于研究开发科学探索、环境和生物医学、教育和国家安全等重大领域和行业所急需的大数据处理技术和工具，把大数据研究上升到为国家发展战略。大数据处理技术的重要性7.“大数据研究的科学价值”李国杰，中国计算机学会通讯，vol. 8，no.9, 2012.92012年3月，美国奥巴马政府宣布投资2亿美元启动“大数据研究和发展计划”，这是继1993年美国宣布“信息高速公路”计划后的又一次重大科技发展部署。美国政府认为大数据是“未来的新石油”，将“大数据研究”上升为国家意志，对未来的科技与经济发展必将带来深远影响。一个国家拥有数据的规模和运用数据的能力将成为综合国力的重要组成部分，对数据

6、的占有和控制也将成为国家间和企业间新的争夺焦点。大数据处理技术的重要性8.数据科学(Data Science) 国内外出现了“数据科学”的概念 图灵奖获得者Jim Gray: 2007年最后一次演讲中提出“数据密集型科学发现(Data-Intensive Scientific Discovery)” 将成为科学研究的第四范式 实验科学 理论科学 计算科学 数据科学世界著名存储技术公司EMC：提出了“Data Science”的概念，“Data Science teams will become the driving force for success with big data analyt

7、ics” 李国杰院士：“数据科学”研究的对象是什么？计算机科学是关于算法的科学，数据科学是关于数据的科学。大数据处理技术的重要性9.大数据将带来巨大的技术和商业机遇大数据分析挖掘和利用将为企业带来巨大的商业价值原始信息行业数据知识报表制图电子文档信息检索数据仓库海量分析知识挖掘信息化技术大数据分析PC时代互联网时代大数据时代大数据处理技术的重要性10.应用数据规模急剧增加，传统计算面临严重挑战中国移动一个省电话通联记录(CDR)数据每月可达0.5-1PB，而整个中国移动每月则高达7-15PB数据；如此巨大的数据量使得Oracle等数据库系统已经难以支撑和应对南京市公安局320道路监控云计算系统

8、，数据量为三年200亿条、总量120TB的车辆监控数据百度存储数百PB数据， 每天处理数据10PB淘宝存储14PB交易数据， 每天新增数据40-50TB大数据处理技术发展的驱动力11.大数据处理技术发展的驱动力大规模数据处理和行业应用需求日益增加和迫切出现越来越多的大规模数据处理应用需求，传统系统难以提供足够的存储和计算资源进行处理，云计算技术是最理想的解决方案。调查显示：目前，IT专业人员对云计算中诸多关键技术最为关心的是大规模数据并行处理技术大数据并行处理没有通用和现成的解决方案对于应用行业来说，云计算平台软件、虚拟化软件都不需要自己开发，但行业的大规模数据处理应用没有现成和通用的软件，需

9、要针对特定的应用需求专门开发，涉及到诸多并行化算法、索引查询优化技术研究、以及系统的设计实现12.大数据处理技术发展的驱动力海量数据隐含着更准确的事实研究发现：大数据量可显著提高机器学习算法的准确性；训练数据集越大,数据分类精度越高；大数据集上的简单算法能比小数据集上的复杂算法产生更好的结果，因此数据量足够大时有可能使用代价很小的简单算法来达到很好的学习精度。 例如，2001年,一个基于事实的简短问答研究, 如提问:Who shot Abraham Lincoln？在很大的数据集时,只要使用简单的模式匹配方法,找到在“shot Abraham Lincoln”前面的部分即可快速得到准确答案：J

10、ohn Wilkes Booth13.大数据的基本特点 大数据特点: 5V Volume: 大容量 Variety: 多样性 Velocity: 时效性 Veracity: 准确性 Value: 大价值 VeracityVarietyVelocityVolumeValue14. 结构特征结构化数据非结构化/半结构化数据获取和处理方式静态(线下数据)/非实时数据动态(流式/增量式/线上)/实时数据关联特征无关联/简单关联数据(键值记录型数据)复杂关联数据(图数据)大数据的类型15.数据尺度和关联度空间Data connectednessData sizeTypical RDBMSSQL Comf

11、ort ZoneDisk-based Key-value StoreColumn StoreDocument StoreGraph DB引自微软亚洲研究院，王海勋16. 大数据问题的基本特点极强的行业应用需求特性规模极大，超过任何传统数据库系统的处理能力技术综合性、交叉性很强大多数传统算法面临失效，需要重写大数据研究的基本原则应用需求为导向: 以行业应用问题和需求为导向领域交叉为桥梁：行业、IT产业、学术界协同计算技术为支撑：研究解决涉及的计算技术问题大数据问题的特点和研究原则17.以有效的信息技术手段和计算方法，获取、处理和分析各种应用行业的大数据，发现和提取数据的内在价值，为行业提供高附加

12、值的应用和服务 技术手段：信息技术和计算方法 核心目标：价值发现 效益目标：形成高附加值智能化行业应用大数据研究的基本目标18. 大数据研究的挑战数据规模导致难以应对的存储量数据规模导致传统算法失效大数据复杂的数据关联性导致高复杂度的计算大数据研究的基本途径三个基本途径：寻找新算法降低计算复杂度降低大数据尺度，寻找数据尺度无关算法大数据并行化处理大数据研究的挑战和基本途径19. 大数据研究的基本途径大数据研究的挑战和基本途径新算法寻找新算法降低计算复杂度降低尺度寻找数据尺度无关近似算法并行化分而治之并行化处理大数据20.大数据研究层面从信息处理系统视角以信息系统视角来划分大数据研究层面 体现大

13、数据系统研发所涉及的各个层面和问题 同时兼顾产业、学术和应用行业共同关注的问题基础设施系统平台算法应用21.集群, 众核, GPU, 混合式构架 (如集群+众核, 集群+GPU)云计算资源与支撑平台大数据查询(SQL, NoSQL, 实时查询, 线下分析)大数据存储(DFS, HBase, RDFDB, MemDB, RDB)大数据预处理MapReduce, BSP, MPI, CUDA, OpenMP, 定制式,混合式 (如MapReduce+CUDA, MapReduce+MPI)并行化机器学习与数据挖掘算法社会网络,排名与推荐,商业智能,自然语言处理,生物信息媒体分析检索, Web挖掘与

14、检索, 3维建模与可视化计算大数据研究层面和主要内容电信/公安/商业/金融/遥感遥测/勘探/生物医药领域应用/服务需求和计算模型分析工具/开发环境和工具/行业应用系统开发角色行业用户领域专家应用开发者计算技术研究和开发者研究层面大数据行业应用/服务层应用开发层应用算法层基础算法层并行编程模型与计算框架层大数据存储管理层并行构架和资源平台层应用层算法层系统层构架层22.集群, 多核, GPU, 混合式构架 (如集群+多核, 集群+GPU)云计算资源和服务支撑平台大数据查询(SQL, NoSQL, 实时查询, 线下分析)大数据存储(DFS, HBase, MemDB, RDB)大数据预处理MapR

15、educe, BSP, MPI, CUDA, OpenMP, 定制式,混合式 (如MapReduce+CUDA, MapReduce+MPI)并行化机器学习和数据挖掘算法社会网络,排名与推荐,商业智能,自然语言处理,生物信息媒体分析检索, Web挖掘与搜索, 3维建模与可视化大数据研究方式电信/公安/商业/金融/遥感遥测/勘探/生物医药领域应用/服务需求和计算模型行业应用系统开发纵向方式：上下层交叉组合单一层面的研究往往难以获得理想的综合解决方案，上下层交叉组合可以获得理想的综合解决方案，能发现很多新的研究点23.大数据十个典型和热点研究问题一、大数据存储管理和索引查询二、Hadoop性能优化

16、和功能增强三、并行计算模型和框架四、并行化机器学习和数据挖掘算法五、社会网络分析六、Web信息搜索和排名推荐七、媒体分析检索八、基于本体的语义分析与挖掘九、大数据自然语言处理智能化应用十、大数据可视化计算与分析系统层基础算法典型/共性应用算法与技术24.一、大数据存储管理与索引查询大数据预处理技术大数据的采集和传输大数据的清洗过滤和质量管理技术大数据的压缩技术记录型大数据索引和查询技术静态记录型大数据索引技术流式/增量式记录型大数据索引技术大数据表的高效关系型操作 (如查询连接)大数据并行化查询技术SQL/NoSQL查询语言接口与技术SQL/NoSQL查询语言接口并行化查询执行机制25.一、大

17、数据存储管理与索引查询图数据表示和查询技术静态图数据的表示和存储静态图数据的查询流式/增量式图数据的表示和存储流式/增量式图数据的查询图数据并行化查询技术混合式数据表示和存储管理模型NoSQL数据库技术结构化/半结构/非结构化数据混合存储管理模型混合式数据下的数据关系和查询操作技术26.一、大数据存储管理与索引查询分布式数据库HBase性能优化基于HBase的大数据索引和查询技术分布式内存数据库存储技术 （Google的Dremel，MemSQL，Hana IMDB，Redis)大规模RDF语义数据库基于Hbase的大规模RDF数据存储管理SPARQL大规模语义数据查询及并行化算法基于RDFS

18、/OWL的大规模语义推理并行化算法分布式文件系统HDFS的优化27.一、大数据存储管理与索引查询1.基于HBase的大数据索引与查询技术问题：HBase缺少类似于RDB中的索引创建能力，通过Hive转换为MapReduce程序处理Hbase中的数据性能很慢本课题组正在研究基于HBase和混合树模型的大数据索引和并行化查询技术和算法，并利用HBase和CoProcessor、以及分布式内存数据库完成查询加速。28.一、大数据存储管理与索引查询2.基于HBase的大规模RDF语义数据库问题：大数据文本和媒体数据语义的分析和挖掘需要提供大规模RDF语义数据存储管理和查询系统本课题组正在研究基于HBa

19、se和分布式内容数据库的大规模RDF语义数据库系统29.二、Hadoop性能优化与功能增强MapReduceHadoop性能优化针对作业、任务和Slot资源的调度优化 (Intel-Hadoop, IBM的AMapReduce， Facebook的Corona）针对I/0的优化、针对充分利用内存的优化(Berkeley的Spark)针对流程的优化 (优化Shuffle过程 、SHadoop)MapReduce并行计算框架改进迭代式MapReduce执行框架 (Twister, HaLoop)流式MapReduce执行框架 (Hadoop Online)30.1.Hadoop系统性能优化问题：H

20、adoop最初是为批量数据线下处理设计，当使用Hadoop进行大数据存储和实时查询分析处理时，其响应性能不够，因此Hadoop性能优化一直是大家关注的热点研究问题。本课题组进行了Hadoop MapReduce框架的性能优化研究：1).研究设计了新的作业和任务处理机制及任务调度通信机制，实验结果显示，Benchmark程序执行性能提升达到约30%。该项成果经过集成和测试目前已经集成到 Intel Distributed Hadoop（IDH）产品中2).研究了基于资源环境和作业开销感知的Hadoop作业调度优化技术，可实现动态的Slot调度和均衡的作业调度优化二、Hadoop性能优化与功能增强

21、31.三、并行编程模型与计算框架MapReduceHadoop性能优化针对作业、任务和Slot资源的调度优化针对I/0的优化、针对充分利用内存的优化针对流程的优化MapReduce并行计算框架改进迭代式MapReduce执行框架 (Twister, HaLoop)流式MapReduce执行框架 (Hadoop Online)BSP (Bulk Synchronized Parallel)基于BSP模型的并行处理框架32.三、并行编程模型与计算框架大规模图数据并行处理框架和系统Google的Pregel微软的Trinity定制式并行计算框架全内存集群计算 (Bakerley Spark)大规模流

22、式数据处理 (Twitter Storm, Yahoo S4)特定应用问题的定制式并行计算框架混合式并行计算模型和框架MapReduce+CUDA并行计算框架的设计与优化MapReduce+MPI和MapReduce+BSP并行计算框架设计优化33.三、并行编程模型与计算框架基于Intel Xeon Phi众核协处理系统MIC的BSP编程模型和示范应用研究 Intel最新推出商用众核协处理器Intel Xeon Phi5761核，以高速 环形结构互联商用级众核处理器通用计算能力价格：$2000-265034.三、并行编程模型与计算框架基于Intel Xeon Phi众核协处理系统MIC的BSP

23、编程模型研究和示范应用研究 包括三个层面的工作：基于MIC的BSP并行 计算模型研究机器学习并行 化算法研究两个并行化示范应用大规模图像检索+机器翻译系统Host ProcessorIntel Xeon E5-26XXPCIeXeon Phi MIC 0Xeon Phi MIC 1MPIOpenMPBSPParallelized Machine Learning and NLP AlgorithmsImage Retrieval/Detection Machine TranslationDemo ApplicationsParallel ML & NLP AlgorithmsParallel

24、Programming ModelsMIC-BasedParallelComputingHardware Platform35.三、并行编程模型与计算框架2. 混合式并行计算模型和框架研究MapReduce + MIC(或GPU)的混合式并行计算模型和框架研究 问题：在视频或图像内容分析应用中，面向大规模媒体数据分析处理时，单一的MapReduce构架和模型不足以胜任，需要采用MapReduce调度媒体片段或文件的处理、同时采用MIC或GPU对本地的数据密集型媒体处理进行并行化加速处理 需要在MapReduce模型和框架基础上开发对局部数据用MIC或GPU加速处理的编程接口和框架基于Hadoo

25、p + 内存数据库的混合式并行计算模型和框架研究 对某些对响应性能要求很高的应用，需要考虑基于内存数据库进行加速 如：我们进行了基于内存数据库的在线机器翻译并行化算法研究和系统开发 36.三、并行编程模型与计算框架3. 定制式并行计算模型和框架 问题：对机器学习和数据挖掘中的很多算法，现有的MapReduce或其他并行计算框架可能既过于庞大、适用性也不好，需要研发轻量级的、更加适用、效率更高的定制式并行计算框架例如：我们基于Hadoop的基础构架和底层的RPC协议自行研发了面向神经网络学习的轻量级定制式并行计算框架，提供基于分布内存的快速迭代计算机制和并行计算能力37.四、并行化机器学习与数据

26、挖掘算法大数据并行化机器学习和数据挖掘算法大数据处理并行化学习和挖掘算法不同并行模型下并行化学习和挖掘算法并行化机器学习和数据挖掘工具和平台 研究表明：基于大数据集的机器学习会取得更好的学习效果，这已经成为目前机器学习领域的共识38.分类算法 (Classification)大规模支持向量机 (Large Scale SVM)神经网络 (Neural Network)朴素贝叶斯 (Nave Bayes)决策树 (Decision Trees)聚类 (Clustering)关联规则挖掘参数估计 (Parameters Estimation)高维度数据降维 (Dimension Reduction

27、)集成学习 (Ensemble Learning )图数据算法图聚类，图分类，图模式匹配(子图同构、最大公共子图)四、并行化机器学习与数据挖掘算法39.1. 基于MapReduce的K-Means并行化算法输入：待聚类的N个数据点，期望生成的聚类的个数K输出：K个聚类算法描述: 选出K个点作为初始的cluster center Loop: 对输入中的每一个点p： 计算p到各个cluster的距离； 将p归入最近的cluster; 重新计算各个cluster的中心 如果不满足停止条件，goto Loop; 否则，停止四、并行化机器学习与数据挖掘算法40.1. 基于MapReduce的K-Mean

28、s并行化算法四、并行化机器学习与数据挖掘算法Map阶段的处理在Map类的初始化方法setup中读取全局的聚类中心信息对Map方法收到的每一个数据点p，计算p与所有聚类中心间的距离，并选择一个距离最小的中心作为p所属的聚类，输出键值对对每个Map节点上即将传递到Reduce节点的每一个键值对，用Combiner进行数据优化，合并相同ClusterID下的所有数据点并求取这些点的均值pm以及数据点个数n41.1. 基于MapReduce的K-Means并行化算法四、并行化机器学习与数据挖掘算法Mapper伪代码class Mapper setup() 读出全局的聚类中心数据 Centers map

29、(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, p); 42.1. 基于MapReduce的K-Means并行化算法四、并行化机器学习与数据挖掘算法Combiner伪代码class Combiner reduce(ClusterID, p1, p2, ) pm = 0.0； n = 数据点

30、列表p1, p2, 中数据点的总个数; for i=0 to n pm += pi; pm = pm / n; / 求得这些数据点的平均值 emit(ClusterID, (pm, n); 43.2.K-最近邻(KNN)分类并行化算法四、并行化机器学习与数据挖掘算法基本算法设计思想K-最近邻是分类器算法中最通俗易懂的一种，计算测试样本到各训练样本的距离，取其中距离最小的K个，并根据这K个训练样本的标记进行投票得到测试样本的标记。加权K-最近邻分类算法的思路是，在根据测试样本的标记进行投票表决时，将根据测试样本与每个训练样本间距离（或相似度）的大小决定训练样本标记的作用大小，基本原则是：距离越近

31、的训练样本其标记的作用权重越大，反之则越小。据此，可以建立一个带加权的投票表决计算模型(比如y = Si*yi/Si, k=0,k-1,Si为取值0-1的相似度数值，yi为选取出的最邻近训练样本的分类标记值)决定以最终的测试样本的分类标记。算法的思路清晰简单，然而对于海量数据计算量很大，耗费时间较长。44.2.K-最近邻(KNN)分类并行化算法四、并行化机器学习与数据挖掘算法MapReduce并行化算法设计思路基本处理思路是：将测试样本数据分块后分布在不同的节点上进行处理，将训练样本数据文件放在DistributedCache中供每个节点共享访问Map阶段对每个读出的测试样本数据ts(trid

32、,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)45.2.K-最近邻(KNN)分类并行化算法四、并行化机器学习与数据挖掘算法Mapper伪代码class Mapper setup() 读取全局训练样本数据文件，转入本地内存的数据表TR中 map(key, ts) / ts为一个测试样本 Max

33、S (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) 46.四、并行化机器学习与数据挖掘算法3.频繁项集挖掘并行化算法 本研究组进行了基于MapReduce的频繁项集挖掘算法研究 基本思路是基于传统的Apriori算法和SON算法，提出并实现了一个并行化的频繁项集挖掘算法PSON，用两轮MapReduce实现了大规模频繁项集挖掘并行计算研究论文，发表于PAAP2011国际会议PSON: A Par

34、allelized 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, 201147.Frequent setsSuppose I is an itemset consisting of items fr

35、om the transaction database DLet N be the number of transactions DLet M be the number of transactions that contain all the items of IM /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, I2 is contained in transactions T100 and T400 so the suppo

36、rt 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 miningTo find all frequent k-itemsets from a transaction database (k = 1, 2, 3, )枚举计算的时间复杂度是：O(2n*N*t), n是Item的总数，N是Transaction总数，t是每个Transaction平均包含的Item数4

37、8.SON Algorithm*Basic ideaDivide the whole database into several non-overlapping partitionsFor each partition, discover all the frequent itemsets for it (referred to as local frequent itemsets)Merge all the local frequent itemsets from all the partitions (referred to as global candidate itemsets)Rem

38、ove those that are not actually frequent in the whole database, generating global frequent itemsetsLemmaAn itemset that is not local frequent in any of the partitions cannot be global frequentA global frequent itemset must appear as local frequent in at least one of the partitions* A. Savasere, E. O

39、miecinski, and S. Navathe, “An efficient algorithm for mining association rules in large databases,” in proceedings of the 21st VLDB Conference Zurich, Swizerland, 199549.PSON: Parallelized SON AlgorithmMotivation to Parallelize SONProcessing one partition doesnt need any information from any other

40、partitionEach partition can be processed concurrentlySON is naturally suitable for parallelization Preparing dataStore the transaction database into DFSThe whole database will be automatically divided into several non-overlapping chunksChunks correspond to the partitions in SONMap tasksEach chunk is

41、 processed by one mapper node to find local frequent itemsets for that chunkReduce tasksLocal frequent itemsets of the same length are processed by one reduce nodeEach node counts for each global candidate itemset it receivesThus decides which are global frequent itemsetsRun two MapReduce jobs to ge

42、nerate all frequent itemsets1st job: generate all global candidate itemsets2nd job: identify global frequent itemsets from global candidate itemsets50.The 1st MapReduce JobMap phaseEach map node takes in one partition and generates local frequent itemsets for that partition using Apriori algorithm.F

43、or 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 phaseThe same local frequent itemsets are sent to one reduce node.Reduce phaseEach reduce node emits one and only one key-value pair t

44、o DFSFinallyMerging all the pairs in DFS gives us all global candidate itemsets51.The 2nd MapReduce JobAssumptionEach node is given a full duplicate of the global candidate itemsets generated by the 1st MapReduce job beforehandMap phaseEach map node counts for each of the global candidate itemsets i

45、n 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 phaseEach global candidate itemset and its counts in all the partitions are sent to one reduce nodeReduce phaseFor each global candidate ite

46、mset C, reduce node adds up all the associative counts for C and emits only the actual global frequent itemsets to DFS52.Experimental ResultsThe transaction database size varies from 6GB to 60GB，with the number of transactions varies from 1 million to 500 billionConclusion: When the size of the data

47、base 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-up53.四、并行化机器学习与数据挖掘算法4.大规模短文本多分类并行化算法 本研究组进行了基于MapReduce的查询短文本分类并行化算法研究。提供了1万条已经标注出所属类别作为训练样本，一共有480个类别。原始数据有1000万条

48、查询短文本，其中有少数不属于这480类的异类测试样本，需要对这些大量的短文本进行分类，并能标识出不属于以上480类的异类样本。本研究项目为本系研究生组队参加2012年中国第一届“云计算与移动互联网大奖赛”的指定的4个大数据并行处理赛题之一，经过角逐获得1、2、3等奖各一项。54.四、并行化机器学习与数据挖掘算法4.大规模短文本多分类并行化算法本道题目是高维稀疏空间文本的分类问题。由于大量实践证实SVM 针对高维空间数据训练效果较好，而且分类器的速度较快，因此我们使用了linear SVM进行处理训练阶段，对于多类（480 类）问题，为了提高分类精度，我们针对每个类做了一个两类分类器；同时为了能

49、识别出异类样本，我们用每个类别下的标注样本训练出一个OneClassSVM分类器预测阶段，分别用480 个分类器对每个待预测的样本进行分类并打分，选择打分最高的类别作为该样本可能的预测类别；并用OneClassSVM对该测试样本做一个异类样本排除为了提升训练和分类速度， 上述所有算法都在MapReduce 框架下实现。 55.四、并行化机器学习与数据挖掘算法4.大规模短文本多分类并行化算法56.四、并行化机器学习与数据挖掘算法4.大规模短文本多分类并行化算法OneClassSVM排除异类57.四、并行化机器学习与数据挖掘算法5.神经网络并行化算法 本研究组基于Hadoop基础构架和底层RPC远

50、程过程调用通信，采用分布内存式数据缓存机制，为经典的BackPropagation神经网络算法研究设计了一个定制的轻量级专用并行化计算框架，并最终设计实现了并行化的BackPropagation神经网络算法。神经网络需要经过数万至数十万轮的迭代计算，计算量巨大。由于实现了并行化算法，大大缩短了训练时间，本课题进行了800万超大训练样本的神经网络训练并行化计算测试。58.四、并行化机器学习与数据挖掘算法5.神经网络并行化算法 59.四、并行化机器学习与数据挖掘算法5.神经网络并行化算法 MapReduce显然不适合做这样大量的迭代运算，因此需要设计定制式的轻量级并行计算框架。基本思路是把全部样本

51、划分为子集给各个节点分别进行处理60.四、并行化机器学习与数据挖掘算法5.神经网络并行化算法 基本算法思路是把整个样本数据划分到各个计算节点上完成计算，然后计算误差和权重差值W，汇总并更新权重W后继续迭代计算，直至达到结束条件61.四、并行化机器学习与数据挖掘算法5.神经网络并行化算法 62.四、并行化机器学习与数据挖掘算法5.神经网络并行化算法 Comparison of each epochs training time cost in cNeural and Hadoop with different number of computing nodes on 1 million trai

52、ning samples.Performance of each epochs training time cost in cNeural with various numbers of computing nodes and various sizes of training samples63.四、并行化机器学习与数据挖掘算法6.查询推荐QUBIC并行化算法 本研究组进行了基于MapReduce的查询推荐QUBIC并行化算法。基本思路是基于用户日志设计查询推荐算法，首先挖掘用户日志中Query与URL之间的关系，寻找Query中若干关联性较大的组，最后基于MapReduce并行构造Quer

53、y-URL二部图和查询亲和图QAG，在此基础上最终完成查询词的聚类，并以此为基础推荐查询关键词 肖滔，硕士研究论文，201264.五、社会网络分析社团发现 ( Community Detection )网络建模 (Network Modeling )中心分析和影响力建模 (Centrality Analysis and Influence Modeling )分类推荐 (Classification and Recommendation )隐私安全等 (Privacy, Spam and Security )65.六、Web信息搜索与排名推荐文档倒排索引（Inverted Document I

54、ndexing）深度Web搜索(Deep Web Search，精确化、智能化、综合化信息搜索)页面分类 (Document Classification)页面聚类 (Document Cluster)网页摘要 (Document Automatic Summarization)重复文档检测与过滤(Duplicate Document Detection & Filtering) Web信息搜索与数据挖掘66.六、Web信息搜索与排名推荐常规排名(Ranking)多样性排名(Diversified Ranking)基于内容的推荐 (Content-based Recommendation )基

55、于标签的推荐 (Tag-based Recommendation )协同过滤推荐 (Collaborative Filtering Recommendation ) 排名与推荐系统67.1.文档倒排索引算法 搜索引擎中最重要的一个问题是如何为大量文档创建倒排索引以便提供全文检索基于以上索引的搜索结果：fish doc1, doc2red doc2, doc3red fish doc2doc1：one fish two fishdoc2：red fishblue fishdoc3：one red bird倒排索引：one: doc1, doc3fish: doc1, doc2two: doc1r

56、ed: doc2, doc3blue: doc2bird: doc3六、Web信息搜索与排名推荐68.1.文档倒排索引算法如果考虑单词在每个文档中出现的词频、位置、对应Web文档的URL等诸多属性，则前述简单的倒排算法就不足以有效工作。我们把每个单词对应的文档ID、单词词频、位置等诸多信息称为postings六、Web信息搜索与排名推荐69.1.文档倒排索引算法六、Web信息搜索与排名推荐70.1.文档倒排索引算法Map和Reduce实现伪代码1: class Mapper2: procedure Map(docid n, doc d)3: H new AssociativeArray4: f

57、or all term t doc d do5: Ht Ht + 16: for all term t H do7: Emit(term t, posting )1: class Reducer2: procedure Reduce(term t, postings , )3: P new List4: for all posting postings , do5: Append(P, )7: Emit(term t; postings P)六、Web信息搜索与排名推荐71.六、Web信息搜索与排名推荐2.网页排名图算法PageRankPageRank是一种由搜索引擎根据网页之间相互的超链接计

58、算的网页排名技术PageRank是Google用于用来标识网页的等级或重要性的一种方法；其级别从1到10级，PR值越高说明该网页越受欢迎（越重要）PageRank基本思想从许多优质的网页链接过来的网页，必定还是优质网页。一个网页要想拥有较高的PR值的条件： 有很多网页链接到它 有高质量的网页链接到它72.2.网页排名图算法PageRank假定一个上网者从一个随机的网页开始浏览上网者不断点击当前网页的链接开始下一次浏览但是，上网者最终厌倦了，开始了一个随机网页的浏览随机上网者访问一个新网页的概率就等于这个网页的PageRank值。这个模型更加接近于用户的行为六、Web信息搜索与排名推荐73.2.

59、网页排名图算法PageRank采用邻接表来表示网页之间的连接关系。随机浏览模型的PageRank公式：以上公式是递归定义的，因此需要通过迭代计算得到所有节点最终的PageRank值六、Web信息搜索与排名推荐74.2.网页排名图算法PageRankPhase1: GraphBuilder建立网页之间的超链接图Phase2: PageRankIter迭代计算各个网页的PageRank值Phase3: RankViewer按PageRank值从大到小输出六、Web信息搜索与排名推荐75.Phase1：GraphBuilder原始数据集：维基百科各网页间的链接信息。文本文件，共11.2G。每行包含一

60、个网页名，及其所链接的全部网页名GraphBuilder目标：分析原始数据，建立各个网页之间的链接关系。Map：逐行分析原始数据, 输出其中网页的URL作为key, PageRank初始值（PR_init）和网页的出度列表一起作为value,以字符串表示value，用特定的符号将二者分开。Reduce: 输出该阶段的Reduce不需要做任何处理六、Web信息搜索与排名推荐2.网页排名图算法PageRank76.Phase2：PageRankIterPageRankIer：迭代计算PR值，直到PR值收敛或迭代预定次数。Map对上阶段的 产生两种对： For each u in link_list