Python_机器学习_Hadoop海量数据实现原理

Hadoop海量数据实现原理

1. 单点结构面临的问题
2. 集群架构面临的问题
3. Hadoop集群架构
4. 冗余化数据存储
5. 分布式文件系统

单点结构

海量数据例子

集群架构

2. 集群架构面临的问题

节点故障

网络带宽瓶颈

3. Hadoop 分布式集群

Map-Reduce集群运算问题的解决方案

1. 在多节点上冗余地存储数据，以保证数据的持续性
2. 将计算移向数据端，以最大程度减少数据移动
3. 简单的程序模型，隐藏所有的复杂度

4.冗余化数据存储结构

分布式文件存储系统：

1. 提供全局的文件命名空间，冗余度和可获取性
2. 例如Google的GFS，hadoop的HDFS

典型的应用场景与模式：

1. 超大级别的数据量（100GB到100TB级别）
2. 数据很少被全部替换
3. 最常见的操作为读取和追加数据

5. 分布式文件系统

1. 数据以‘块状’形式在多台机器上存储
2. 每个数据块都会重复地在多台机器上存储
3. 保证数据的持续性和随时可取性
4. 服务器块同时也用作计算服务器
5. 把运算挪向数据处

服务器块：

1. 文件被分作16-64MB大小的连续块
2. 每个文件块会被重复的存储2到3次
3. 尽量保证重复的数据块在不同的机架上

主节点：

1. Hadoop的HDFS里叫做Name节点
2. 存储元数据记录文件存储结构和地址
3. 最常见的操作为读取和追加数据

文件访问的客户端库：

1. 询问主节点以获取块服务器地址
2. 直接连接相应服务器块获取数据

Map Reduce变换数据

Hadoop组成

1. Hadoop Common
   工具包，为其它hadoop模块提供基础设施
2. Hadoop HDFS
   分布式文件系统，对海量数据存储
3. Map-Reduce
   分布式处理策略，计算模型，对海量数据处理
4. Yarn
   分布式资源管理，调度
   |

编程模型：Map-Reduce

• 手头上有一个超大的文本文件
• 需要统计每个文本中的词出现的次数
• 实际应用场景
  1. 从web服务器日志中找出高频热门url
  2. 搜索词统计
  3. 区分垃圾邮件和短信
  4. 舆情分析（正负面评论）

Map-Reduce：总览

• Map
  逐个文件逐行扫描
  扫描的同时抽取出我们感兴趣的内容（Keys）
• Group by key
  排序和洗牌
• Reduce
  聚合，总结，过滤或转换
  写入结果
• Map和Reduce函数要根据具体问题具体实现

Map-Reduce：Reduce步骤

输入：一些键值对
编程人员需要定义两个函数：

• Map(k, v) -> <k’, v’>*
  对一个键值对输入产生一序列中间键值对
  Map函数将对所有键值对操作
• Reduce(k’,<v’>)-><k’,v’’>
  所有有相同key ，k’的值v’被reduce到一起
  Reduce函数对每一个不同的Key k’进行操作

Map-Reduce：词频统计

Map-Reduce：环境

• 运行Map-Reduce模型，还需要hadoop环境解决
• 对原始数据进行区分(Partition)
• 调度程序在一系列的机器集群上都并行运行
• 执行中间过程的group by key 步骤
• 处理运行过程中的突发节点故障
• 处理并行运行过程中的节点和节点之间的通信

数据流

• 输入和输出都被存储在分布式文件系统HDFS上
• 实际调度操作时，调度器会尽可能将map任务移至靠近数据物理存储的节点上
• 中间结果将会被存储在map和reduce操作的本地文件系统上
• 实际运行过程中，一个Map-Reduce产生的结构，很有可能作为另一个Map-Reduce任务的输入

主节点的协调功能

• 主节点主要负责系统的协调
• 任务状态：等待初始，进行中，完成
• 一旦有能工作的worker，待初始任务被调度运行
• 一个Map任务完成后，它会向主节点发送它的产生的R个中间文件 的位置和大小，每个文件对应一个reducer
• 主节点将这些信息传送至reducer

节点故障

• Map任务节点故障

1. 所有运行中和已经完成的map任务，都被重置为待初始
2. 所有这些待初始Map任务，将重新被分配到能工作的节点worker

• Reduce任务节点故障

1. 只有运行中而未完成的reduce任务被设定为待初始
2. 这些待初始reduce任务被重新分配至其他worker上

• 主节点故障

1. 整个Map-Reduce任务中断，同时通知客户端管理员

启动多少个Map和Reduce任务

• M个Map任务和R个Reduce任务
• 实际操作经验法则：
  1. 通常情况下我们会让M远大于集群中的节点数
  2. 通常设置一个分布式文件系统块对应一个Map任务
  3. 提升动态加载平衡，同时加速节点故障时的任务恢复
• 通常R比M要小
  1. 因为输出要分布在R文件上

动态添加map和reduce的大小，增加并行度

• map是配置mapred.max.split.size，来定义map处理文件的大小，默认是256000000字段，换算就是256M。 如果想增加map的并行度，那么就是减少map处理文件的大小 set mapred.max.split.size=xxx（更小的字节）

• reduce和map是一致的，修改hive.exec.reducers.bytes.per.reducer这个参数 通过控制这个来定义一个reduce处理文件的大小 hive.exec.reducers.bytes.per.reducer

改进：combiners

• 很多时候一个Map任务为同一个key k会产生如（k,v1）,(k,v2)的键值对：
  例如，词频统计任务中的高频词产生的中间结果
• 在Mapper中，进行预聚合操作，来节约网络的时间成本
  合并（k, list(v1)）->v2
  合并器(combiner)通常和reduce函数是一致的
• 以词频统计为例：
  合并器（Combiner）预先合并了单个mapper（单个节点）中键值对

云计算

• 可能会提供额外的服务：例如持续性存储

总结

• reduce需要写函数，map有时候都不用写
• map工作主要修改key ，reduce主要修改values
• 对已有的算法进行map-reduce化
• map 对一个键值对输入产生一序列中间键值对
• map函数将对所有输入键值对操作
• 相同的key 值 v 被reduce放一起，Reduce函数对每一个不同的key进行操作
• map和reduce属于分治思想，通过hash分桶来处理，map是发散的过程，reduce是收敛的过程
• map任务数目要远大于Reduce
• map-reduce会有输入和输出，输出后再次进入map-reduce，如此循环迭代，在磁盘级别的操作，所以开销会很大，spark是在内存级别的操作，所有对内存开销会很大，但速度很快
• spark稳定不如map，spark只读一次
• map-reduce主要做特征的转换，数据的提取，转换，处理，写入

Hive

• Hive

  1. 在Hadoop的Map-Reduce之上提供的类SQL数据提取操作功能

• Spark

  1. 分布式计算框架，是Map-Reduce替代方案，兼容HDFS和Hive，
  2. 可兼容hadoop生态，弥补Mapduce不足

Hive介绍

• Hive是基于Hadoop的一个数据仓库工具，可以将结构化的数据文件映射为一张数据库表，并提供简单的sql查询功能，可以将sql语句转换为MapReduce任务进行运行。 其优点是学习成本低，可以通过类SQL语句快速实现简单的MapReduce统计，十分适合数据仓库的统计分析

Hive 架构介绍

• 用户接口三个：CLI，Client 和 WUI。在启动 Client模式的时候，需要指出Hive Server在哪个节点启动，WUI是通过浏览器访问Hive
• Hive将元数据存储在数据库中，如mysql。Hive中的元数据包括表的名字，表的列和分区及其属性，表的属性，表的数据所在目录等。
• HQL生成的查询计划存储在HDFS中，并在随后有MapReduce调用执行。
• Hive的数据存储在HDFS中，大部分的查询、计算由MapReduce完成

关联规则挖掘

关联规则介绍

• 数据挖掘是一项从大量的记录数据中提取有价值的、人们感兴趣的知识，这些知识是隐含的、事先未知的有用信息，提取的知识一般可表示为概念(Concepts)、规则(Rules)、规律(Regular ides)、模式(Patterns)等形式。

• 规则：样本和样本之间的关联性

• 模式：通过特征X，经过函数f得到结构y

• 关联规则是当前数据挖掘研究的主要方法之一，它反映一个事物与其他事物之间的相互依存性和关联性

• 典型的关联规则发现问题是对超市中的货篮数据(MarketBasket)进行分析。通过发现顾客放入货篮中的不同商品之间的关系来分析顾客的购买习惯。

关联规则：发现数据中的规律

• 超市中什么产品会一起购买?(组合推荐)

• 顾客在买了一台PC之后下一步会购买?(搭配推荐)

• 哪种DNA对这种药物敏感?

• 我们如何自动对Web文档进行分类?

• 论⽂查重?

关联规则基本概念

• 每一个样本叫一个项目

• 一个顾客购买商品的购物车，项目的组合叫事务
  事务中有意义的项目集合叫做项集，比如面包和牛奶，就是二项集
  我们要挖掘的是项集

• 1000个人购物，1000个购物单，牛奶在购物单中出现的次数叫支持度
  当支持度高到一定程度，才会观测出有意义的信息和规则，设定一个阈值

• 项集A在事务数据库D中出现的次数占D中总事务的百分比叫做项集的支持度。如果项集的支持度超过用户给定的最小支持度阈值，就称该项集是频繁项集(或频集)

• 关联规则是形如X⇒Y的逻辑蕴含式，其中X⊂I ，Y⊂I，且X∩Y=∅

• 如果事务数据库D中有s%的事务包含X∪Y，则称关联规则X⇒Y的支持度为s%

• 关联规则的信任度为support (X∪Y)/support (X) 也就是:

  support (X⇒Y)=P (X ∪Y)

  confidence (X⇒Y)=P (Y | X)

支持度和信任度理解

• 支持度：关联规则产出的是规则，找到频繁项集，再找出有意义的规则，支持度确定哪些是经常出现的

• 信任度：信任度产出规则，知道X和Y是一个频繁项目集 ，谁对谁的影响更大

强关联规则

• 强关联规则就是支持度和信任度分别满足用户给定阈值的规则

  例:
  ???????? 交易ID ???? 购买的商品????????????????
  2000 A,B,C
  1000 A,C
  4000 A,D
  5000 B,E,F

• 设最小支持度为50%, 最小可信度为50%, 则可得到
  A ⇒ C (50%, 66.6%)
  C ⇒ A (50%, 100%)

关联规则挖掘算法

• Agrawal等人提出的AIS，Apriori和AprioriTid

• Cumulate和Stratify，Houstsma等人提出的SETM

• Park等人提出的DHP

• Savasere等人的PARTITION

• Han等人提出的不生成候选集直接生成频繁模式FPGrowth

• 其中最有效和有影响的算法为Apriori，DHP 和PARTITION，FPGrowth

Apriori算法

• Apriori算法命名源于算法使用了频繁项集性质的先验(Prior)知识

• Apriori算法将发现关联规则的过程分为两个步骤:

  1. 通过迭代，检索出事务数据库中的所有频繁项集，即支持度不 低于用户设定的阈值的项集
  2. 利用频繁项集构造出满足用户最小信任度的规则

• 挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分

Apriori两个性质

• 性质1: 频繁项集的所有非空子集必为频繁项集

• 性质2: 非频繁项集的超集一定是非频繁的

Apriori原理执行步骤

• 剪枝步:C(k)要过滤掉未达到阈值的项集

• 连接步（组合）:为找L(k)，通过将L(k-1)与⾃⾝连接产生候选k项集的集合 C(k)

• 剪枝-》连接-》剪枝-》连接-》剪枝-》连接-》….执行K次

Apriori算法实例

• 现有A、B、C、D、E五种商品的交易记录表，试找出三种商品关联销售情况(k=3)，最小支持度=50%

  交易号 商品代码
  100 A,C,D
  200 B,C,E
  300 A,B,C,E
  400 B,E
  

Apriori算法不足

• 验证过程是性能瓶颈
  1. 交易数据库可能非常⼤大
  2. 比如频集最多包含10个项，那么就需要扫描交易数据库10遍
  3. 需要很大的I/O负载