大数据的处置和分析教育课件.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,中国科大,*,大数据的处置和分析PPT讲座,课 程 内 容,课程内容,（本次讲座与下述内容关系不大）,围绕学科理论体系中的模型理论,程序理论和计算理论,1.,模型理论关心的问题,给定模型,M,，哪些问题可以由模型,M,解决；如何比较模型的表达能力,2.,程序理论关心的问题,给定模型,M,，如何用模型,M,解决问题,包括程序设计范型、程序设计语言、程序设计、形式语义、类型论、程序验证、程序分析等,3.,计算理论关心的问题,给定模型,M,和一类问题,解决该类问题需多少资源,讲 座 提 纲,大数据的魅力,数据挖掘、大数据、大数据案例、大数据的特点,大数据时代的思维变革,样本和全体、精确性和混杂性、因果关系和相关关系,大数据的处理,几种主要处理方式、,MapReduce,编程模型,大数据,的,分析,关键技术概述、,PageRank,初步,数据挖掘,数据挖掘的定义,1.,从数据中提取出隐含的过去未知的有价值的潜,在信息,2.,从大量数据或者数据库中提取有用信息的科学,相关概念：知识发现,1.,数据挖掘是知识发现过程中的一步,2.,粗略看：数据预处理,数据挖掘数据后处理,预处理,:,将未加工输入数据转换为适合处理的形式,后处理,:,如可视化,便于从不同视角探查挖掘结果,大数据的魅力,数据挖掘,典型事例：购物篮分析,顾客,一次购买商品,1,面包、黄油、,尿布,、,牛奶,2,咖啡、糖、小甜饼、鲑鱼,3,面包、黄油、咖啡、,尿布,、,牛奶,、鸡蛋,4,面包、黄油、鲑鱼、鸡,5,鸡蛋、面包、黄油,6,鲑鱼、,尿布,、,牛奶,7,面包、茶叶、糖、鸡蛋,8,咖啡、糖、鸡、鸡蛋,9,面包、,尿布,、,牛奶,、盐,10,茶叶、鸡蛋、小甜饼、,尿布,、,牛奶,经关联分析，可发现顾客经常同时购买的商品：尿布,牛奶,大数据的魅力,大数据,大数据,，,或,称,海量数据,，,指所涉及的数据量规模巨大到无法通过人工，在合理时间内达到截取、管理、处理、并整理成为人类所能解读的信息,在总数据量相同的情况下，与个别分析独立的小型数据集相比，将各个小型数据集合并后进行分析可得出许多额外的信息和数据关系性，可用来察觉商业趋势、避免疾病扩散、打击犯罪,、,测定实时交通路况,或,判定研究质量等,这样的用途正是大型数据集盛行的原因,数据挖掘,则是探讨用以解析大数据的方法,大数据的魅力,大数据案例,谷歌预测冬季流感的传播,2009,年出现了一种称为甲型,H1N1,的新流感病毒，在短短几周内迅速传播开来，全球的公共卫生机构都担心一场致命的流行病即将来袭,美国也要求医生在发现甲型,H1N1,病例时告知疾病控制与预防中心。但人们从患病到求医会滞后，信息传到疾控中心也需要时间，因此通告新病例往往有一两周的延迟。而且疾控中心每周只进行一次数据汇总,信息滞后两周对一种飞速传播的疾病是致命的，它使得公共卫生机构在疫情爆发的关键时期难以有效发挥作用,大数据的魅力,大数据案例,谷歌预测冬季流感的传播,在这种流感爆发的几周前，谷歌的工程师在,自然,杂志发表引人注目的论文，令公共卫生官员和计算机科学家感到震惊,因为文章不仅预测了流感在全美的传播，而且具体到特定的地区和州,谷歌是通过观察人们在网上的搜索记录来完成这个预测的，这种方法以前一直是被忽略的,谷歌保存了多年来所有的搜索记录,每天有来自全球,30,亿条搜索指令,(,仅谷歌有这样的数据资源,),如此庞大数据资源足以支撑和帮助它完成这项工作,大数据的魅力,大数据的魅力,大数据案例,谷歌预测冬季流感的传播,原理十分简单,现在,大家都,有上网搜索信息的习惯，连头痛感冒也上网搜索，谷歌流感趋势项目通过记录搜索有关,“,流感,”,词条的地区和频率，并,分析,其与流感在时间和空间上的传播之间的联系，,追踪到流感广泛传播的地区，进而预测流感可能爆发的高危地区。,即,当某地区在网上搜寻与流感有关信息,的人日益增多，,很可能意味着该地区有许多人患上流感类疾病,因为流感趋势项目能够近乎实时地估计流感活动情况，,故,它比其他系统能够更早地发现流感疫情大数据的魅力,大数据案例,谷歌预测冬季流感的传播,谷歌把,5000,万条美国人最频繁检索的词条与疾控中心在,2003,年到,2008,年间季节性流感传播期间的数据进行比较，以确定相关检索词条，并总共处理了,4.5,亿,(?),个不同的数学模型,在把得出的预测与,2007,年和,2008,年美国疾控中心记录的实际流感病例进行对比后，筛选了,45,条检索词条的组合，并把它们用于一个特定的数学模型后，其预测与官方数据相关性高达,97%,因此当,2009,年甲型,H1N1,流感爆发时，与滞后的官方数据相比，谷歌成为一个更有效及时的指示者,大数据的魅力,大数据案例,谷歌预测冬季流感的传播,这是当今社会所独有的一种新型能力：以一种前所未有的方式，通过对海量数据的分析，获得巨大价值的产品和服务，或深刻的洞见,大数据不仅会变革公共卫生，也会变革商业、变革思维，改变政府与民众关系的方法，,，开启重大的时代转型,大数据的魅力,大数据的特点,体量巨大,(Volume),数据集合的规模不断扩大，已从,GB(1024MB),到,TB(1024GB),再到,PB,级，甚至已经开始以,EB,和,ZB,来计数。至今，,人类生产的所有印刷材料的数据量是,200PB,。未来,10,年，全球大数据将增加,50,倍，管理数据仓库的服务器的数量将增加,10,倍,类型繁多,(Variety),数据,种类繁多，并且,被分为结构化,、半结构化和,非结构化,的,数据。,半结构化和,非结构化数据，包括,传感器数据、,网络日志、音频、视频、图片、地理位置信息等,，占有量,越来越,大，已远远超过结构化数据,大数据的魅力,大数据的特点,价值密度低,(Value),。,数据总体的,价值,巨大，但价值,密度,很低,。以视频为例，,在长达数小时,连续不断的视频监控中，有用数据可能仅一二秒。,另一极端是各数据都有贡献，但单个数据价值很低,速度快,(Velocity),。,数据往往以数据流的形式动态快速地产生，具有很强的时效性，用户只有把握好对数据流的掌控才能有效利用这些数据。例如，一天之内需要审查,500,万起潜在的贸易欺诈案件；需要分析,5,亿条日实时呼叫的详细记录，以预测客户的流失率,大数据时代的思维变革,数据采集和数据处理技术已经发生了翻天覆地的变化，人们的思维和方法要跟得上这个变化,大数据时代的精髓在于人们分析信息时的三个转变，这些转变将改变人们决策的制定和对表象的理解,大数据时代的思维变革,变革一,更多,:,不是随机样本,而是全体数据,1.,随机抽样：用最少的数据获得最多的信息,过去由于获取和分析全体数据的困难，抽样调查是一种常用统计分析方法。它根据随机原则从总体中抽取部分实际数据进行调查，并运用概率估计方法，根据样本数据推算总体相应的数量指标,抽样分析的精确性随抽样随机性的增加而提高，与样本数量的增加关系不大抽样随机性高时，分析的精度能达到把全体作为样本调查时的,97%,样本选择的随机性比样本数量更重要,大数据时代的思维变革,变革一,更多,:,不是随机样本,而是全体数据,1.,随机抽样：用最少的数据获得最多的信息,抽样分析的成功依赖于抽样的随机性，但实现抽样的随机性非常困难,当想了解更深层次的细分领域的情况时，随机抽样方法不一定有效，即在宏观领域起作用的方法在微观领域可能失去了作用,随机抽样需要严密的安排和执行，人们只能从抽样数据中得出事先设计好的问题的结果,大数据时代的思维变革,变革一,更多,:,不是随机样本,而是全体数据,2.,全体数据：用全体数据可对数据进行深度探讨,流感趋势预测分析了整个美国几十亿条互联网检索记录，使得它能提高微观层面分析的准确性，甚至能够推测某个特定城市的流感状况,信用卡诈骗需通过观察异常情况来识别，这只有在掌握所有的数据时才能做到,社会科学是被“样本,=,全体,”,撼动得最厉害的一门学科。这门学科过去非常依赖于样本分析、研究和调查问卷。当记录下人们的平常状态，就不用担心在做研究和调查问卷时存在的偏见了,大数据时代的思维变革,变革二,更杂：不是精确性，,而是混杂性,对小数据而言，最基本和最重要的要求就是减少错误，保证质量。因为收集的数据较少，应确保每个数据尽量精确，以保证分析结果的准确性,允许不精确数据是大数据的一个亮点,而非缺点。因为放松了容错的标准，就可以掌握更多数据，而掌握大量新型数据时，精确性就不那么重要了,例如，与服务器处理投诉时的数据进行比较，用语音识别系统识别呼叫中心接到的投诉会产生不太准确的结果,但它有助于把握事情的大致情况,不精确的大量新型数据能帮助掌握事情发展趋势,大数据时代的思维变革,变革二,更杂：不是精确性，,而是混杂性,执迷于精确性是信息缺乏时代的产物，大数据时代要求重新审视精确性的优劣，如果将传统的思维模式运用于数字化、网络化的,21,世纪，就会错过重要信息，失去做更多事情，创造出更好结果的机会,另一方面，需要与数据增加引起的各种混乱（数据格式不一致，数据错误率增加等）做斗争。错误并不是大数据的固有特性，但可能是长期存在并需要去处理的现实问题,大数据时代的思维变革,变革三,更好,:,不是因果关系,而是相关关系,1.,因果关系与相关关系,因果关系是,指,一,个,事件,是另,一,个,事件的结果,相关关系是指两个事件的发生存在某个规律,与通过逻辑推理研究因果关系不同，大数据研究通过统计性的搜索、比较、聚类、分析和归纳，寻找事件（或数据）之间的相关性,一般来说，统计学无法检验逻辑上的因果关系,也许正因为统计方法不致力于寻找真正的原因,才促进数据挖掘和大数据技术在商业领域广泛应用,大数据时代的思维变革,变革三,更好,:,不是因果关系,而是相关关系,2.,相关关系帮助捕捉现在和预测未来,如果,A,和,B,经常一起发生，则只需注意到,B,发生了,就可以预测,A,也发生了,故障经常是慢慢出现的，通过收集所有数据，可预先捕捉到事物要出故障的信号。如将发动机的嗡嗡声、引擎过热等异常情况与正常情况对比，就能知道什么地方将出毛病，及时更换或修复,过去需先有想法，然后收集数据来测试想法的可行性，现在可以对大数据进行相关关系分析知道机票是否会飞涨、哪些词条最能显示流感的传播,大数据时代的思维变革,变革三,更好,:,不是因果关系,而是相关关系,3.,大数据改变人类探索世界的方法,越来越多的事物不断,地,数,据,化,，,将拓展人类的视野,，,使得人们可从大量的数据中，发现隐藏,在其中,的自然规律、社会规律和经济规律,当网页变成数据，谷歌具备了令人大跌眼球的全文搜索能力，在几个毫秒之内，就能让人们检索世界上几乎所有的网页,当方位变成数据，每个人都能借助,GPS,快速到达目的地,大数据时代的思维变革,变革三,更好,:,不是因果关系,而是相关关系,3.,大数据改变人类探索世界的方法,当情绪变成数据，人们甚至根据大家快乐与否判断股市的涨跌,上述这,些不同的数据可归结为几类相似的数学模型，从而使得“数据科学”,（应用数据学习知识的学科）,成为一门具备普遍适用的学科,生物信息学、计算社会学、天体信息学、电子工程、金融学、经济学等学科，都依赖数据科学的发展,大数据的处理,大数据处理的几种主要方式,海量数据的处理对于当前的技术来说是一种极大,的挑战，目前大数据的主要处理形式如下：,静态数据的批量处理,数据体量巨大、精确度高、价值密度低；,挖掘合,适模式、得出具体含义、制定明智决策、,；用于,社交网络、电子商务、搜索引擎等,在线数据的实时流式处理,日志数据、传感器数据、,Web,数据等；数据连续,不断、来源众多、格式复杂等,;,流式挖掘、实时分,析、,；应用于智能交通、环境监控、金融银行等,还有在线数据的交互处理、图数据处理,大数据的处理,MapReduce,编程模型,是批量数据处理的一个常用编程模型,源于函数式语言的两个高阶函数：,map,和,reduce,map,(,f,1,x,1,x,n,)=,f,1,(,x,1,),f,1,(,x,n,),f,1,作用于,n,个变元的计算可以并行,reduce,(,f,2,y,1,y,n,)=,f,2,(,f,2,(,f,2,(,y,1,y,2,),y,3,),y,n,),若二元函数,f,2,是有交换律和结合率的运算，则,f,2,作用于,n,个变元的计算也可以适当并行,两者的复合：,reduce,(,f,2,map,(,f,1,x,1,x,n,),MapReduce,源于此，但更加一般,MapReduce,编程模型,MapReduce是一种比较专用的并行编程模型,，,面向,大,数据集,上,的可并行化的问题,Map,完成过滤或分类，例如，它把数据集中所有的人按姓氏分成若干队列，每个姓氏一个队列；,Reduce,完成概括总结操作，例如，计算各姓氏队列中的人数，产生按姓氏的人口比例,MapReduce,可以在并行计算机、计算机集群和计算机网格上实现,大数据的处理,MapReduce,编程模型,计算过程如图所示,程序员只需编,写,Map,和,Reduce,函数,1.Map,任务,执行,Map,函数的,多个任务并行执行,每个,Map,任务把文,件块转换成“键,-,值”,(key-value),对序列,大数据的处理,Map,任务,Reduce,任务,按键分组,输,出,文,件,输入,文件块,键,-,值对,(k,v),键及所有值,(k,v,w,),MapReduce,编程模型,2.,按键组合,其处理方式与,两个函数无关,把“键,-,值”对序,列组成“键,-,值表”对,序列,把各“键,-,值表”对,分发给,Reduce,任务,按键组合由主控,程序完成,大数据的处理,Map,任务,Reduce,任务,按键分组,输,出,文,件,输入,文件块,键,-,值对,(k,v),键及所有值,(k,v,w,),MapReduce,编程模型,3.,Reduce,任务,执行,Reduce,函,数的多个任务并,行执行,每个,Reduce,任务,把“键,-,值表”对中,的值以某种方式组,合，转换成“键,-,值”,对输出,大数据的处理,Map,任务,Reduce,任务,按键分组,输,出,文件,输入,文件块,键,-,值对,(k,v),键及所有值,(k,v,w,),当矩阵很大时，可用,MapReduce,实现矩阵运算。对于分块乘：,1.Map,任务计算两块的乘，用结,果在,Z,中的位置作为键,2.Reduce,任务按键值来分别累加,Map,任务的结果,b,n,大数据的处理,X:,Y:,Z:,当矩阵很大时，可用,MapReduce,实现矩阵运算。对于分块乘：,1.Map,任务计算两块的乘，用结,果在,Z,中的位置作为键,2.Reduce,任务按键值来分别累加,Map,任务的结果,b,n,大数据的处理,X:,Y:,Z:,b,n,大数据的处理,X:,Y:,Z:,当矩阵很大时，可用,MapReduce,实现矩阵运算。对于分块乘：,1.Map,任务计算两块的乘，用结,果在,Z,中的位置作为键,2.Reduce,任务按键值来分别累加,Map,任务的结果,b,n,大数据的处理,X:,Y:,Z:,当矩阵很大时，可用,MapReduce,实现矩阵运算。对于分块乘：,1.Map,任务计算两块的乘，用结,果在,Z,中的位置作为键,2.Reduce,任务按键值来分别累加,Map,任务的结果,当矩阵很大时，可用,MapReduce,实现矩阵运算。对于分块乘：,1.Map,任务计算两块的乘，用结,果在,Z,中的位置作为键,2.Reduce,任务按键值来分别累加,Map,任务的结果,b,n,大数据的处理,X:,Y:,Z:,b,n,大数据的处理,X:,Y:,Z:,当矩阵很大时，可用,MapReduce,实现矩阵运算。对于分块乘：,1.Map,任务计算两块的乘，用结,果在,Z,中的位置作为键,2.Reduce,任务按键值来分别累加,Map,任务的结果,b,n,大数据的处理,X:,Y:,Z:,当矩阵很大时，可用,MapReduce,实现矩阵运算。对于分块乘：,1.Map,任务计算两块的乘，用结,果在,Z,中的位置作为键,2.Reduce,任务按键值来分别累加,Map,任务的结果,大数据分析的关键技术,要挖掘大数据的大价值，必须对大数据进行内容,上的分析与计算,深度学习,大数据的出现提供了使用复杂,(,而不是简单或浅层,),的模型来有效地表征和解释数据的机会，深度学习就是利用层次化的架构学习出对象在不同层次上的表达,(,例,:,降低语音识别错误率,),知识计算,要对大数据进行高端分析，就需要从大数据中抽取出有价值的知识，并将其构建成可支持查询、分析和计算的知识库，涉及知识库的构建、多源知识的融合和知识库的更新,大数据的分析,大数据的分析,大数据分析的关键技术,社会计算,是现代计算技术与社会科学之间的交叉学科,它是指面向社会活动、社会过程、社会结构、社会组织和社会功能的计算理论和方法。在线社会计算包括在线社会网络的结构分析、信息传播模型以及信息内容的分析、建模与挖掘等,可视化,不同于传统的信息可视化，大数据可视化的最大挑战源自其数据规模：如何提出新的可视化方法，它能够帮助人们分析大规模、高维度、多来源、动态演化的信息，并辅助作出实时的决策,大数据的分析,PageRank,初步,PageRank,（网页排名）,通过,对,网络浩瀚的超链接关系,的分析,来确定一个页面的等级,Google,把从,A,页面到,B,页面的链接解释为,A,页面给,B,页面投票,，,B,页面从,A,页面的投票能得多少分还与,A,页面的等级有关,一个页面的,PageRank,，,由所有,给,它,投票,的页面的,数量和,重要性,，,经过,迭代计算,得到,这项技术使得,Google,成为第一个能够战胜作弊者的搜索引擎。当然，与作弊者之间的斗争永远不会停止,大数据的分析,PageRank,初步,1.,早期搜索引擎与词项作弊,搜索引擎：词项出现在网页头部比在普通正文的得分高、词项在网页中出现的次数越多得分越高,作弊者：在自己的网页上增加热门词项,如,movie,并重复很多次，以提高与,movie,的相关性。词项,movie,在该网页上的颜色与背景色一样，以掩盖作弊者的不道德行为,大数据的分析,PageRank,初步,2.Google,的对策,使用,PageRank,技术来模拟,Web,漫游者的行为：他们从随机页面出发，每次从当前网页随机地选择出链前行，该过程可以迭代多次。最终，较多漫游者访问的网页则重要性较高。在决定查询应答顺序时，,Google,把重要页面放在前面,在判断网页内容时,不仅考虑网页上出现的词项，还考虑有链接指向该网页的网页中所使用的词项,大数据的分析,PageRank,初步,3.,最简单的,PageRank,举例,PageRank,：网页集,实数，值越大则网页越重要,定义网页的,Web,迁移矩阵,M,来描述随机漫游者的下一步访问行为,例：从,A,出发，以,1/3,的概率,访问,B,、,C,和,D,，访问,A,的,概率为,0,0 1/2 1 0,1/3 0 0 1/2,1/3 0 0 1/2,1/3 1/2 0 0,A B C D,M,=,A,B,C,D,大数据的分析,PageRank,初步,3.,最简单的,PageRank,举例,随机漫游者位置的概率分布可通过一个,n,维向量,v,来描述，每个分量表示处于相应网页的概率,例,(,续,),：假定处于各网页的初始概率相等,M,k,v,是随机漫游者,k,步后的概率分,布向量,A,B,C,D,0 1/2 1 0,1/3 0 0 1/2,1/3 0 0 1/2,1/3 1/2 0 0,A B C D,M,=,1/4,1/4,1/4,1/4,v,大数据的分析,PageRank,初步,3.,最简单的,PageRank,举例,在,Web,网页链接图满足一定的条件下，概率分布向量将逼近一个极限分布，它满足,v=,M,v,并且，若分布向量各分量之和为,1,时，方程,v=,M,v,有唯一解,在常规情况下，可用高斯消去法解方程,v=,M,v,在实际情况下，图由几百亿甚至几千亿个节点组成，高斯消去法不可行，原因在于其时间复杂度是方程个数的三次方,若迭代求解，每轮迭代的时间复杂度是平方级,大数据的分析,PageRank,初步,3.,最简单的,PageRank,举例,例,(,续,),：对矩阵,M,进行,迭代计算：相当把求解,方程,v=,M,v,转化为找函数,v,.,M,v,最小不动点的迭代过程,A,B,C,D,3/9,2/9,2/9,2/9,9/24,5/24,5/24,5/24,15/48,11/48,11/48,11/48,11/32,7/32,7/32,7/32,Mv,M,2,v,M,3,v,极限,0 1/2 1 0,1/3 0 0 1/2,1/3 0 0 1/2,1/3 1/2 0 0,A B C D,M,=,1/4,1/4,1/4,1/4,v,大数据的分析,PageRank,初步,3.,最简单的,PageRank,举例,需要基于,MapReduce,进,行,PageRank,的迭代计算,A,B,C,D,3/9,2/9,2/9,2/9,9/24,5/24,5/24,5/24,15/48,11/48,11/48,11/48,11/32,7/32,7/32,7/32,Mv,M,2,v,M,3,v,极限,0 1/2 1 0,1/3 0 0 1/2,1/3 0 0 1/2,1/3 1/2 0 0,A B C D,M,=,1/4,1/4,1/4,1/4,v,小 结,本讲座小结,概要介绍了大数据的基本概念和特点、大数据时代的思维变革，大数据的处理和分析技术,面临的挑战,数据复杂：数据的类型复杂、结构复杂和模式复,杂，使得数据感知、表达、理解和计算都面临挑战,计算复杂：数据多源异构、规模巨大、快速多变,使传统的机器学习、信息检索和数据挖掘都显不足,系统复杂：对处理系统的系统架构、计算框架、,处理方法、运行效率和单位能耗等都有挑战,小 结,参考文献,维克托,尔耶,舍恩伯格等，大数据时代：生活、工作与思维的大变革，浙江人民出版社，,2012,Anand Rajaraman,等,大数据：互联网大规模数据挖掘与分布式处理，人民邮电出版社，,2012,程学旗等，大数据系统和分析技术综述，软件学报，,25(9):1889-1908,2014,相关课程,机器学习与知识发现（研）、机器学习与数据挖掘前沿（研）,