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