大数据的处理和

大数据的处理和分析

课程内容课程内容（本次讲座与下述内容关系不大）围绕学科理论体系中的模型理论,程序理论和计算理论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和reducemap(f1,[x1,……,xn])=[f1(x1),……,f1(xn)]f1作用用于于n个变变元元的的计计算算可可以以并并行行reduce(f2,[y1,……,yn])=f2(……f2(f2(y1,y2),y3),……,yn)若二二元元函函数数f2是有有交交换换律律和和结结合合率率的的运运算算，，则则f2作用用于于n个变变元元的的计计算算也也可可以以适适当当并并行行两者者的的复复合合：：reduce(f2,map(f1,[x1,……,xn]))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任务的结果bn大数据的处理理X:Y:Z:当矩阵很大时时，可用MapReduce实现矩阵运算算。对于分块块乘：1.Map任务计算两块块的乘，用结结果在Z中的位置作为为键2.Reduce任务按键值来来分别累加Map任务的结果bn大数据的处理理X:Y:Z:bn大数据的处理理X:Y:Z:当矩阵很大时时，可用MapReduce实现矩阵运算算。对于分块块乘：1.Map任务计算两块块的乘，用结结果在Z中的位置作为为键2.Reduce任务按键值来来分别累加Map任务的结果bn大数据的处理理X:Y:Z:当矩阵很大时时，可用MapReduce实现矩阵运算算。对于分块块乘：1.Map任务计算两块块的乘，用结结果在Z中的位置作为为键2.Reduce任务按键值来来分别累加Map任务的结果当矩阵很大时时，可用MapReduce实现矩阵运算算。对于分块块乘：1.Map任务计算两块块的乘，用结结果在Z中的位置作为为键2.Reduce任务按键值来来分别累加Map任务的结果bn大数据的处理理X:Y:Z:bn大数据的处理理X:Y:Z:当矩阵很大时时，可用MapReduce实现矩阵运算算。对于分块块乘：1.Map任务计算两块块的乘，用结结果在Z中的位置作为为键2.Reduce任务按键值来来分别累加Map任务的结果bn大数据的处理理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的概率为为001/2101/3001/21/3001/21/31/200ABCDM=ABCD大数据据的分分析PageRank初步3.最简单单的PageRank举例随机漫漫游者者位置置的概概率分分布可可通过过一个个n维向量量v来描述述，每每个分分量表表示处处于相相应网网页的的概率率例(续)：假定定处于于各网网页的的初始始概率率相等等Mkv是随机机漫游游者k步后的的概率率分布向量量ABCD01/2101/3001/21/3001/21/31/200ABCDM=1/41/41/41/4v大数据据的分分析PageRank初步3.最简单单的PageRank举例在Web网页链链接图图满足足一定定的条条件下下，概概率分分布向向量将将逼近近一个个极限限分布布，它它满足足v=Mv并且，，若分分布向向量各各分量量之和和为1时，方方程v=Mv有唯一一解在常规规情况况下，，可用用高斯斯消去去法解解方程程v=Mv在实际际情况况下，，图由由几百百亿甚甚至几几千亿亿个节节点组组成，，高斯斯消去去法不不可行行，原原因在在于其其时间间复杂杂度是是方程程个数数的三三次方方若迭代代求解解，每每轮迭