《机器学习实战》笔记（十五）：Ch15 - 大数据与MapRed

第15章 大数据与MapReduce(代码)

• MapReduce:分布式计算的框架

  • MapRedece

    分布式的计算框架，可以将单个计算作业分配给多台计算机执行

    • 优缺点

      • 优点: 使程序以并行的方式执行，可在短时间内完成大量工作

      • 缺点: 算法必须经过重写，需要对系统工程有一定的理解

      • 适用数据类型: 数值型和标称型数据

    • 工作原理

      • 主节点控制 MapReduce 的作业流程

      • MapReduce 的作业可以分成map任务和reduce任务

      • map 任务之间不做数据交流，reduce 任务也一样

      • 在 map 和 reduce 阶段中间，有一个 sort 和 combine 阶段

      • 数据被重复存放在不同的机器上，以防止某个机器失效

      • mapper 和 reducer 传输的数据形式为 key/value对

  • Hadoop

    • 核心设计

      HDFS和MapReduce

      • HDFS为海量的数据提供了存储

      • MapReduce为海量的数据提供了计算

    • 优点

      • 高可靠性。Hadoop按位存储和处理数据的能力值得人们信赖

      • 高扩展性。Hadoop是在可用的计算机集簇间分配数据并完成计算任务的，这些集簇可以方便地扩展到数以千计的节点中

      • 高效性。Hadoop能够在节点之间动态地移动数据，并保证各个节点的动态平衡，因此处理速度非常快

      • 高容错性。Hadoop能够自动保存数据的多个副本，并且能够自动将失败的任务重新分配

      • 低成本。与一体机、商用数据仓库以及QlikView、Yonghong Z-Suite等数据集市相比，hadoop是开源的，项目的软件成本因此会大大降低

• MapReduce 机器学习

  • 简单贝叶斯：它属于为数不多的可以很自然的使用MapReduce的算法。通过统计在某个类别下某特征的概率。

  • k-近邻算法：高维数据下（如文本、图像和视频）流行的近邻查找方法是局部敏感哈希算法。

  • 支持向量机(SVM)：使用随机梯度下降算法求解，如Pegasos算法。

  • 奇异值分解：Lanczos算法是一个有效的求解近似特征值的算法。

  • k-均值聚类：canopy算法初始化k个簇，然后再运行K-均值求解结果。

  • 对于面向大数据并行处理的计算模型、框架和平台，MapReduce隐含了以下三层含义

    • MapReduce是一个基于集群的高性能并行计算平台（Cluster Infrastructure）。它允许用市场上普通的商用服务器构成一个包含数十、数百至数千个节点的分布和并行计算集群

    • MapReduce是一个并行计算与运行软件框架（Software Framework）。它提供了一个庞大但设计精良的并行计算软件框架，能自动完成计算任务的并行化处理，自动划分计算数据和计算任务，在集群节点上自动分配和执行任务以及收集计算结果，将数据分布存储、数据通信、容错处理等并行计算涉及到的很多系统底层的复杂细节交由系统负责处理，大大减少了软件开发人员的负担

    • MapReduce是一个并行程序设计模型与方法（Programming Model & Methodology）。它借助于函数式程序设计语言Lisp的设计思想，提供了一种简便的并行程序设计方法，用Map和Reduce两个函数编程实现基本的并行计算任务，提供了抽象的操作和并行编程接口，以简单方便地完成大规模数据的编程和计算处理

  • 主要提供的主要功能

    • 数据划分和计算任务调度

      系统自动将一个作业（Job）待处理的大数据划分为很多个数据块，每个数据块对应于一个计算任务（Task），并自动 调度计算节点来处理相应的数据块。作业和任务调度功能主要负责分配和调度计算节点（Map节点或Reduce节点），同时负责监控这些节点的执行状态，并 负责Map节点执行的同步控制

    • 数据/代码互定位

      为了减少数据通信，一个基本原则是本地化数据处理，即一个计算节点尽可能处理其本地磁盘上所分布存储的数据，这实现了代码向 数据的迁移；当无法进行这种本地化数据处理时，再寻找其他可用节点并将数据从网络上传送给该节点（数据向代码迁移），但将尽可能从数据所在的本地机架上寻 找可用节点以减少通信延迟

    • 系统优化

      为了减少数据通信开销，中间结果数据进入Reduce节点前会进行一定的合并处理；一个Reduce节点所处理的数据可能会来自多个 Map节点，为了避免Reduce计算阶段发生数据相关性，Map节点输出的中间结果需使用一定的策略进行适当的划分处理，保证相关性数据发送到同一个 Reduce节点；此外，系统还进行一些计算性能优化处理，如对最慢的计算任务采用多备份执行、选最快完成者作为结果

    • 出错检测和恢复

      以低端商用服务器构成的大规模MapReduce计算集群中，节点硬件（主机、磁盘、内存等）出错和软件出错是常态，因此 MapReduce需要能检测并隔离出错节点，并调度分配新的节点接管出错节点的计算任务。同时，系统还将维护数据存储的可靠性，用多备份冗余存储机制提 高数据存储的可靠性，并能及时检测和恢复出错的数据

• 小节

  • 当运算需求超出了当前资源的运算能力，可以将计算转化称并行的作业，即转化为MapReduce

  • 一个典型的作业流程是先使用map阶段并行处理数据，之后将这些数据在reduce阶段合并

  • 大多数机器学习算法都很容易能写成MapReduce作业

代码托管见Github