网志栈编辑推荐
如果你准备深入研究MapReduce框架来处理大数据集，本书非常实用，通过提供丰富的算法和工具，它会循序渐进地带你探索MapReduce世界，用Apache Hadoop或Apache Spark构建分布式MapReduce应用时通常都需要用到这些算法和工具。每一章分别提供一个实例来解决一个大规模计算问题，如构建推荐系统。你会了解如何用代码实现适当的MapReduce解决方案，而且可以在你的项目中具体应用这些解决方案。这
；
内容简介
本书介绍了很多基本设计模式、优化技术和数据挖掘及机器学习解决方案，以解决生物信息学、基因组学、统计和社交网络分析等领域的很多问题。这本书还概要介绍了MapReduce、Hadoop和Spark。
本书主要内容包括：
■ 完成超大量交易的购物篮分析。
■ 数据挖掘算法（K-均值、KNN和朴素贝叶斯）。
■ 使用超大基因组数据完成DNA和RNA测序。
■ 朴素贝叶斯定理和马尔可夫链实现数据和市场预测。
■ 推荐算法和成对文档相似性。
■ 线性回归、Cox回归和皮尔逊（Pearson）相关分析。
作者简介
Mahmoud Parsian,计算机科学博士，是一位热衷于实践的软件专家，作为开发人员、设计人员、架构师和作者，他有30多年的软件开发经验。目前领导着Illumina的大数据团队，在过去15年间，他主要从事Java (服务器端)、数据库、MapReduce和分布式计算的有关工作。Mahmoud还著有《JDBC Recipes》和《JDBC Metadata, MySQL,and Oracle Recipes》等书（均由Apress出版）。
目录
序 1
前言 3
第1章二次排序：简介 19
二次排序问题解决方案 21
MapReduce/Hadoop的二次排序解决方案 25
Spark的二次排序解决方案 29
第2章二次排序：详细示例 42
二次排序技术 43
二次排序的完整示例 46
运行示例——老版本Hadoop API 50
运行示例——新版本Hadoop API 52
第3章 Top 10 列表 54
Top N 设计模式的形式化描述 55
MapReduce/Hadoop实现：唯一键 56
Spark实现：唯一键 62
Spark实现：非唯一键 73
使用takeOrdered()的Spark Top 10 解决方案 84
MapReduce/Hadoop Top 10 解决方案：非唯一键 91
第4章左外连接 96
左外连接示例 96
MapReduce左外连接实现 99
Spark左外连接实现 105
使用leftOuterJoin()的Spark实现 117
第5章反转排序 127
反转排序模式示例 128
反转排序模式的MapReduce/Hadoop实现 129
运行示例 134
第6章移动平均 137
示例1：时间序列数据（股票价格） 137
示例2：时间序列数据（URL访问数） 138
形式定义 139
POJO移动平均解决方案 140
MapReduce/Hadoop移动平均解决方案 143
第7章购物篮分析 155
MBA目标 155
MBA的应用领域 157
使用MapReduce的购物篮分析 157
Spark解决方案 166
运行Spark实现的YARN 脚本 179
第8章共同好友 182
输入 183
POJO共同好友解决方案 183
MapReduce算法 184
解决方案1: 使用文本的Hadoop实现 187
解决方案2: 使用ArrayListOfLongsWritable 的Hadoop实现 189
Spark解决方案 191
第9章使用MapReduce实现推荐引擎 201
购买过该商品的顾客还购买了哪些商品 202
经常一起购买的商品 206
推荐连接 210
第10章基于内容的电影推荐 225
输入 226
MapReduce阶段1 226
MapReduce阶段2和阶段3 227
Spark电影推荐实现 234
第11章使用马尔可夫模型的智能邮件营销 .253
马尔可夫链基本原理 254
使用MapReduce的马尔可夫模型 256
Spark解决方案 269
第12章 K-均值聚类 282
什么是K-均值聚类? 285
聚类的应用领域 285
K-均值聚类方法非形式化描述：分区方法 286
K-均值距离函数 286
K-均值聚类形式化描述 287
K-均值聚类的MapReduce解决方案 288
K-均值算法Spark实现 292
第13章 k-近邻 296
kNN分类 297
距离函数 297
kNN示例 298
kNN算法非形式化描述 299
kNN算法形式化描述 299
kNN的类Java非MapReduce 解决方案 299
Spark的kNN算法实现 301
第14章朴素贝叶斯 315
训练和学习示例 316
条件概率 319
深入分析朴素贝叶斯分类器 319
朴素贝叶斯分类器：符号数据的MapReduce解决方案 322
朴素贝叶斯分类器Spark实现 332
使用Spark和Mahout 347
第15章情感分析 349
情感示例 350
情感分数：正面或负面 350
一个简单的MapReduce情感分析示例 351
真实世界的情感分析 353
第16章查找、统计和列出大图中的所有三角形 354
基本的图概念 355
三角形计数的重要性 356
MapReduce/Hadoop解决方案 357
Spark解决方案 364
第17章 K-mer计数 375
K-mer计数的输入数据 376
K-mer计数应用 376
K-mer计数MapReduce/Hadoop解决方案 377
K-mer计数Spark解决方案 378
第18章 DNA测序 390
DNA测序的输入数据 392
输入数据验证 393
DNA序列比对 393
DNA测试的MapReduce算法 394
第19章 Cox回归 413
Cox模型剖析 414
使用R的Cox回归 415
Cox回归应用 416
Cox回归 POJO解决方案 417
MapReduce输入 418
使用MapReduce的Cox回归 419
第20章 Cochran-Armitage趋势检验 426
Cochran-Armitage算法 427
Cochran-Armitage应用 432
MapReduce解决方案 435
第21章等位基因频率 443
基本定义 444
形式化问题描述 448
等位基因频率分析的MapReduce解决方案 449
MapReduce解决方案, 阶段1 449
MapReduce解决方案，阶段2 459
MapReduce解决方案, 阶段3 463
染色体X 和Y的特殊处理 466
第22章 T检验 468
对bioset完成T检验 469
MapReduce问题描述 472
输入 472
期望输出 473
MapReduce解决方案 473
Spark实现 476
第23章皮尔逊相关系数 488
皮尔逊相关系数公式 489
皮尔逊相关系数示例 491
皮尔逊相关系数数据集 492
皮尔逊相关系数POJO 解决方案 492
皮尔逊相关系数MapReduce解决方案 493
皮尔逊相关系数的Spark 解决方案 496
运行Spark程序的YARN 脚本 516
使用Spark计算斯皮尔曼相关系数 517
第24章 DNA碱基计数 520
FASTA 格式 521
FASTQ 格式 522
MapReduce解决方案：FASTA 格式 522
运行示例 524
MapReduce解决方案: FASTQ 格式 528
Spark 解决方案: FASTA 格式 533
Spark解决方案: FASTQ 格式 537
第25章 RNA测序 543
数据大小和格式 543
MapReduce工作流 544
RNA测序分析概述 544
RNA测序MapReduce算法 548
第26章基因聚合 553
输入 554
输出 554
MapReduce解决方案（按单个值过滤和按平均值过滤） 555
基因聚合的Spark解决方案 567
Spark解决方案：按单个值过滤 567
Spark解决方案：按平均值过滤 576
第27章线性回归 586
基本定义 587
简单示例 587
问题描述 588
输入数据 589
期望输出 590
使用SimpleRegression的MapReduce解决方案 590
Hadoop实现类 593
使用R线性模型的MapReduce解决方案 593
第28章 MapReduce和幺半群 600
概述 600
幺半群的定义 602
幺半群和非幺半群示例 603
MapReduce示例：非幺半群 606
MapReduce示例：幺半群 608
使用幺半群的Spark示例 612
使用幺半群的结论 618
函子和幺半群 619
第29章小文件问题 622
解决方案1：在客户端合并小文件 623
解决方案2：用CombineFileInputFormat解决小文件问题 629
其他解决方案 634
第30章 MapReduce的大容量缓存 635
实现方案 636
缓存问题形式化描述 637
一个精巧、可伸缩的解决方案 637
实现LRUMap缓存 640
使用LRUMap的MapReduce解决方案 646
第31章 Bloom过滤器 651Bloom
过滤器性质 651
一个简单的Bloom过滤器示例 653
前沿
随着大规模搜索引擎（如Google和Yahoo! ）、基因组分析（DNA测序、RNA测序和生物标志物分析）以及社交网络（如Facebook 和Twitter) 的不断发展，需要生成和处理的数据量已经超过了千万亿字节。为了满足如此庞大的计算需求，我们需高效、可伸缩的并行算法。MapReduce范式就是解决这些问题的一个框架。
MapReduce是一个软件框架，可以采用并行、分布式方式处理GB、TB，甚至PB级的大数据集，同时它也是一个在商用服务器集群之上完成大规模数据处理的执行框架。实现MapReduce 的方法有很多，不过这本书中我们主要关注Apache Spark 和MapReduce/ Hadoop。你将通过简单而具体的示例来了解如何用Spark和Hadoop实现MapReduce。
这本书将为以下领域提供了基本分布式算法（分别用MapReduce、Hadoop和Spark实现），并按照这些领域组织本书的章节：
. 基本设计模式。
. 数据挖掘和机器学习。
. 生物信息、基因组和统计。
. 优化技术。
MapReduce是什么？
MapReduce 是一种编程范式，可以利用集群环境的成百上千台服务器实现强大的可伸缩性。MapReduce一词最早源于函数式编程，由Google在一篇名为“MapReduce: Simplified Data Processing on
Large Clusters ”的文章中率先提出。Google的MapReduce[8]实现是一个专用解决方案，还没有向公众发布。
reduce():.(Key2,.[Value2]).→.[(Key3,.Value3)]
这本书中会使用map() 函数和reduce() 函数的非形式化表示，我会用中括号（[]）表示列表。
MapReduce 的核心概念是将输入数据集映射到一个键-值对集合，然后对所有包含相同键的键-值对完成归约。尽管基本概念很简单，不过如果考虑以下方面，可以看到这个概念确实很强大、很有效：几乎所有数据都可以映射到键-值对。
键和值可以是任意类型：String、Integer、FASTQ （用于DNA测序）、用户自定义的定制类型，当然，也可以是键-值对本身。
MapReduce如何在一组服务器上扩展？MapReduce是如何工作的？关键在于，从概念上讲，MapReduce 的输入是一个记录列表（每个记录可以是一行或多行数据）。这些输入记录会划分并传递到集群中的多台服务器，由map() 函数使用。map() 计算的结果是一个键-值对列表。然后reduce() 函数取各个包含相同键的值集，将它们分别组合为一个值（或一个值集）。换句话说，map() 函数是由一组数据块生成键-值对，reduce() 则是组合map()生成的数据输出，从而能得到所需要的结果，而不是一组键-值对。
MapReduce 的主要优点之一是它的“不共享”（shared-nothing ）数据处理平台。这意味着所有映射器可以独立地工作，而且映射器完成它们的任务时，归约器也能独立地开始工作（映射器或归约器之间不共享任何数据或临界区。如果有临界区，这会减慢分布式计算的速度）。基于这种“不共享”范式，我们可以很容易地编写map() 函数和reduce() 函数，而且能轻松、有效地提高并行性。
为什么使用MapReduce?
前面我们讨论过，MapReduce 的目标是通过增加更多的商用服务器来实现“横向扩容”。这与“纵向扩容”是不同的（纵向扩容是为系统中的单个节点增加更多资源，如内存和CPU）。纵向扩容可能成本很高，有时由于成本以及软件或硬件限制等原因，可能根本无法增加更多的资源。有时人们会提出一些基于主存的新兴算法来解决数据问题，但是由于主存是一个瓶颈，所以这些算法缺乏可伸缩性。例如，在DNA测序分析中，可能需要超过512GB的RAM，这非常昂贵，而且不具有可伸缩性。
如果要提高计算能力，可能需要把计算分布到多个机器上完成。例如，要完成500GB 样本数据的DNA测序，可能需要一个服务器计算4天才能完成比对阶段。利用MapReduce，60 台服务器可以把计算时间锐减到2小时以内。要处理大量的数据，必须能够将这些数据划分为小块来进行处理，再组合得到最终的结果。MapReduce/Hadoop 和Spark/Hadoop 可以帮助你提高计算能力，你只需要写两个函数：
map() 和reduce() 。显然，MapReduce 范式为数据分析领域提供了一个强大的新工具，近来，归功于Hadoop 等开源解决方案，这个新工具得到了越来越多的关注。
基本说来，MapReduce提供了以下优点：
.编程模型 基础架构。
. 能够编写在数百甚至上千台机器上运行的程序。
. 自动并行化和分布
. 容错（如果一台服务器宕机，作业可以由其他服务器完成）。
.程序/作业调度、状态检查和监控。
Hadoop和Spark
Hadoop（http://hadoop.apache.org/ ）是MapReduce应用实现的事实标准。它由一个或多个主节点和任意多个从节点组成。Hadoop提出“数据中心就是计算机”，通过提供map() 函数和reduce() 函数（由程序员定义），允许应用开发人员或程序员利用这些数据中心，从而简化分布式应用。Hadoop 高效地实现了MapReduce 范式，很容易学习，这是一个可以处理TB甚至PB级大数据的强大工具。
在这本书中，大部分MapReduce 算法都采用实例的形式给出（已编译的完整实用解决方案），并且在Java/MapReduce/Hadoop 和/或Java/Spark/Hadoop 中得到实现。Hadoop和Spark（http://spark.apache.org/ ）框架是开源的，允许我们在分布式环境中完成大数据量的计算和数据处理。
这些框架通过提供“横向扩容”方法来支持可伸缩性，可以采用MapReduce 范式在数千台服务器上运行密集型计算。与Hadoop的API相比，Spark的API提供了更高层的抽象。由于这个原因，只用一个Java驱动器类就可以描述Spark解决方案。
Hadoop和Spark是两个不同的分布式软件框架。Hadoop是一个MapReduce框架，在这个框架上可以运行支持map() 、combine() 和reduce() 函数的作业。MapReduce范式很适合单趟计算［先map() ，再reduce() ］，不过对于多趟算法效率则很低。Spark 不是一个MapReduce框架，不过很容易用来支持MapReduce框架的功能，它提供了一个适当的API 可以处理map() 和reduce() 功能。Spark并不限于先完成映射阶段再完成归约阶段。Spark 作业可以是由映射和/或归约/洗牌阶段构成的一个任意DAG（有向无环图）。Spark程序可以使用Hadoop运行，也可以不使用Hadoop，另外Spark可以使用Hadoop分布式文件系统（Hadoop Distributed File System，HDFS）或者其他持久存储来实现输入/输出。基本上，对于一个给定的Spark程序或作业，Spark引擎会创建将在集群上完成的任务阶段所构成的一个有向无环图，Hadoop/MapReduce 则不同，它会创建由两个预定义阶段（映射和归约）构成的有向无环图。注意，Spark创建的DAG可以包含任意多个阶段。与Hadoop/ MapReduce相比，这使得大多数Spark作业都能更快地完成，因为简单的作业只需要一个阶段就可以完成，更复杂的任务也可以一起完成（包括多个阶段），而不需要划分为多个作业。前面已经提到，相比于MapReduce/Hadoop，Spark的API提供了更高层的抽象。例如，Spark的几行代码可能等价于MapReduce/Hadoop的30～40行代码。
尽管Hadoop和Spark等框架建立一个“不共享”范式基础之上，不过它们确实也支持在所有集群节点上共享不可变的数据结构。在Hadoop中，可以通过Hadoop的Configuration对象将这些值传递给映射器和归约器。除了Broadcast只读对象，Spark还支持只写累加器。Hadoop和Spark为大数据处理提供了以下好处：
可读性
Hadoop和Spark支持容错（任何节点宕机不会丢失所需的计算结果）。
可伸缩性
Hadoop和Spark支持庞大的服务器集群。
分布式处理
在Spark和Hadoop中，输入数据和处理是分布式的（可以全面支持大数据）。并行化
可以在节点集群上并行地执行计算。
Hadoop 主要设计用于批处理，不过如果有足够的内存/RAM，Spark 可以用于近实时处理。要了解Spark RDDs（resilient distributed data sets，弹性分布式数据集）的基本用法，可以参考附录B。
那么MapReduce/Hadoop的核心组件有哪些？
.输入/输出数据包括键-值对。一般地，键是整型、长整型和字符串，而值可以是几乎任何数据类型（字符串、整型、长整型、句子、特殊格式的数据等）。
. 数据划分到商用节点上，填充到数据中心。
.这个软件会处理故障、重启和其他意外中断。这称为容错（fault tolerance），这也是Hadoop的一个重要特性。
Hadoop和Spark不只是提供了map() 和reduce() 功能，还提供了插件模型来实现定制记录读取、二次数据排序及更多其他功能。
图P-2展示了Spark、YARN 和Hadoop HDFS之间关系的一个高层视图。
图P-2：MapReduce、Spark和HDFS之间的关系
从这个关系可以看到，使用HDFS （和非HDFS文件系统）运行MapReduce和Spark有很多方法。在这本书中，我会用到以下关键词和术语：
.MapReduce表示一般的MapReduce框架范式。
.MapReduce/Hadoop表示使用Hadoop的一个特定的MapReduce框架实现。
.Spark 表示一个特定的Spark实现，它使用HDFS 作为持久存储或计算引擎（注意，Spark可以在任何数据存储库上运行，不过这里我们主要强调Hadoop的HDFS）：
─Spark 可以脱离Hadoop 使用独立的集群节点运行（可以使用HDFS、NFS或其他媒介作为持久数据存储库）。
─Spark也可以结合Hadoop，使用Hadoop的YARN 或MapReduce框架运行。
通过这本书，你会循序渐进地学习使用Hadoop 构建MapReduce 应用所需的算法和工具。MapReduce/Hadoop 已经成为处理大数据集（如日志数据、基因组序列、统计应用和社交图谱）的理想编程模型。MapReduce 可以用于任何不需要紧耦合并行处理的应用。要记住，Hadoop主要设计用于MapReduce批处理，它并不是一个理想的实时处理解决方案。不要期望在2～5s时间内从Hadoop得到答案，最小的作业也可能需要超过20s的时间。Spark是一个顶级Apache项目，非常适合近实时处理，如果有更多的RAM，它的表现将会更出色。利用Spark ，如果使用一个包括100个节点的集群运行一个大数据处理作业（如生物标志物分析或Cox回归），完全有可能在25～35s内处理2亿条记录。一般地，Hadoop作业会有15～20s的延迟，不过这取决于Hadoop集群的大小和配置。
MapReduce 实现（如Hadoop ）可以在一个庞大的商用计算机集群上运行，具有很好的可伸缩性。例如，一个典型的MapReduce计算过程可以在数百或数千台机器上处理PB或TB 级的数据。程序员会发现
，MapReduce 很容易使用，因为它隐藏了并行化、容错、数据分布和负载平衡等繁杂的细节，使程序员可以集中精力编写两个关键函数map() 和reduce()。
下面是MapReduce/Hadoop/Spark的一些主要应用：
. 查询日志处理。
. 抓取、索引和搜索。
. 分析、文本处理情感分析。
. 机器学习（如马尔可夫链和朴素贝叶斯分类器）。
. 推荐系统。
. 文档聚类和分类。
. 生物信息学（比对、重新校准、生殖细胞采集和DNA/RNA测序）。
. 基因组分析（生物标志物分析以及回归算法，如线性回归和Cox回归）。
本书内容
这本书中每一章分别提出一个问题，然后通过一组MapReduce算法加以解决。MapReduce 算法/解决方案相当完整（包括MapReduce驱动器、映射器、组合器和归约器程序）。可以在项目中直接使用这些代码（不过，有时可能需要剪切粘贴你需要的部分）。这本书没有涉及MapReduce 框架的底层理论，而是着重于提供使用MapReduce/Hadoop 和Spark 解决大数据难题的实用算法和示例。这本书的主要内容包括：
. 完成超大量交易的购物篮分析。
.数据挖掘算法［K-均值、K-近邻（kNN）和朴素贝叶斯］。
.使用超大量基因组数据完成DNA测序和RNA测序。
. 朴素贝叶斯分类和马尔可夫链实现数据和市场预测。
. 推荐算法和成对文档相似性。
.线性回归、Cox回归和皮尔逊（Pearson）相关系数。
.等位基因频率和DNA挖掘。
. 社交网络分析（推荐系统、三角形计数，情感分析）。
你可以复制粘贴这本书中提供的解决方案，使用Hadoop 和Spark 构建你自己的MapReduce 应用和解决方案。所有这些解决方案都经过编译和测试。如果你对Java 有一些了解（也就是说，可以读写基本的Java程序），想使用Java/Hadoop/Spark 编写和部署MapReduce 算法，那么这本书是最适合不过的了。Jimmy Lin和Chris Dyer写过一本好书[16]，其中对MapReduce 的一般内容做了详细讨论。重申一次，这本书的目标是使用Hadoop 和Spark 提供具体的MapReduce 算法和解决方案。同样地，这本书也不会详细讨论Hadoop 本身。这个内容在Tom White 的书[31]中有详细介绍，这也是一本绝妙的好书。
这本书不会介绍如何安装Hadoop或Spark，这里假设你已经安装了这些框架。另外，所有Hadoop 命令都相对于Hadoop 的安装目录（$HADOOP_HOME 环境变量）执行。这本书只展示使用MapReduce/Hadoop 和Spark的分布式算法。例如，我会讨论API，介绍运行作业的命令行调用，另外会提供完整的实用程序（包括驱动器、映射器、组合器和归约器）。
本书重点
这本书的重点是掌握MapReduce范式，并提出一些可以使用MapReduce/Hadoop 算法解决的具体问题。对于这里提出的每一个问题，我们会详细介绍map() 、combine() 和reduce()函数，并提供完整的解决方案，包括：
. 客户端，可以用适当的输入和输出参数调用驱动器。
.驱动器，明确map()和reduce()函数，并明确输入和输出。
.映射器类，实现map()函数。
.组合器类（如果需要），实现combine() 函数。我们会讨论什么情况下有可能使用组合器。
.归约器类，实现reduce()函数。
这本书的一个目标是提供一个循序渐进的指南，介绍如何使用Spark和Hadoop作为MapReduce算法的解决方案。另一个目标是展示如何将一个MapReduce作业的输出作为另一个作业的输入（这称为MapReduce作业链或流水线）。
本书面向的读者
这本书面向了解Java基础知识并且想使用Hadoop和Spark 开发MapReduce 算法（数据挖掘、机器学习、生物信息技术、基因组和统计领域）和解决方案的软件工程师、软件架构师、数据科学家和应用开发人员。前面已经提到，这里假设你已经了解Java 编程语言的基础知识（例如，知道如何编写类、由一个现有的类定义一个新类，以及使用while循环和if-then-else等基本控制结构）。更具体地，这本书主要面向以下读者：
.希望完成大数据分析（分类、回归算法）的数据科学工程师和专业人员。这本书会采用一种实例的形式给出使用大数据应用分类和回归算法的基本步骤。书中会详细介绍map() 和reduce() 函数，展示如何将它们应用到实际数据，并说明在哪里应用基本设计模式来解决MapReduce 问题。对这些MapReduce 算法稍做修改就可以很容易地应用于其他行业（例如，修改输入格式）。所有解决方案都已经在Apache Hadoop/Spark 中实现，可以根据实际情况调整这些示例。
.希望设计机器学习算法（如朴素贝叶斯和马尔可夫链算法）的软件工程师和软件架构师。这本书会展示如何构建模型，然后使用MapReduce 设计模式将模型应用到新的数据集。
.希望利用MapReduce使用数据挖掘算法（如K-均值聚类和k-近邻算法）的软件工程师和软件架构师。这里会给出详细的示例，可以指导专业人员实现类似的算法。
.希望对生物医疗数据应用MapReduce算法（如DNA测序和RNA测序）的数据科学工程师。这本书会清楚地解释生物信息学家和医疗人员可以采用的实用算法。这里提供了适用不同生物数据类型的主要回归/分析算法。这些算法大多都已经部署在实际的生产系统中。
.希望在MapReduce/分布式环境中应用最重要优化的软件架构师。
在线资源
这本书有两个配套网站：
https://github.com/mahmoudparsian/data-algorithms-book/ 在这个GitHub 网站上，可以找到源代码（按章节组织）、shell 脚本（用于运行MapReduce/Hadoop 和Spark程序）、用于测试的示例输入文件以及书中未涵盖的一些额外内容（包括附加的两章）的相应链接。
http://mapreduce4hackers.com
在这个网站上可以找到额外的源文件（书中未提到）以及书中未涉及的另外一些内容的链接。将来还会更全面地介绍MapReduce/Hadoop/Spark主题。
.......
数据算法：Hadoop/Spark大数据处理技巧 pdf下载声明
本pdf资料下载仅供个人学习和研究使用，不能用于商业用途，请在下载后24小时内删除。如果喜欢，请购买正版
