中国工信出版集团、人民邮电出版社出版的赵卫东、董亮编著的《机器学习》慕课版

第10章 分布式机器学习

1.分布式学习用在什么场合？

解：机器学习是计算机利用已有的数据生成某种模型，并且利用此模型预测的一种方法。在确定模型结构之后，根据已知模型寻找模型参数的过程就是训练，训练过程中不断依据训练数据来迭代调整模型的参数值，从而使结果更加准确。实际应用中，训练数据集往往很大，模型参数量急剧上升，并且各参数需要频繁访问，这种场合下单台机器可能无法胜任这些工作，需要进行分布式学习。

2.讨论分布式计算的常用方法。

解：分布式计算的方法包括模型并行、数据并行以及混合并行。

模型并行是指在分布式系统不同机器负责网络模型的不同部分。

数据并行是指不同机器使用同一模型，但是各台机器处理训练数据分割后形成的不同的子数据集。

混合并行是把上述两种方式合并。

3.简述 MapReduce计算框架的基本原理。

解：MapReduce框架由一个单独的JobTracker以及每个集群节点对应一个备TaskTracker组成。JobTracker负责调度作业的所有任务，并监控它们的执行，这些任务分布在不同的TaskTracker 上，如果任务执行失败，还会调度其重新执行。一个MapReduce作业通常把输入的数据集切分成若干独立的数据块，由Map任务以并行的方式处理，Map输出结果经框架排序后输入到Reduce任务中。整个框架负责任务的调度和监控。

4.MapReduce的过程由哪些环节组成？这些环节分别处理什么工作？

解：a.将输入的海量数据切块(block)分配到不同的机器上进行处理；

b.执行Map程序将输入数据解析成<key, value>对，用户自定义的Map函数把输入的<key, value>对转换成中间形式的<key, value>对，针对不同的业务要求进行定制功能函数。

c.按照key值对中间形式的<key, value>进行分组，从而减少集合数量，降低网络传输压力。

d.把分配给不同的机器进行计算后得到的<key, value>对的结果集合进行整合、合并，完成Reduce运算，并最终输出Reduce结果。

5.讨论为什么Hadoop 架构不能处理实时的数据分析工作。

解：Hadoop是一个批处理框架，相较于那些支持流数据的框架，多了些收集数据的时间以及作业调度的时延。从时延角度看，Hadoop不适合处理实时的数据分析工作。

此外Hadoop是基于MapReduce模型的，处理海量数据的离线分析工具，M/R模型在实时领域很难有所发挥，所以从应用领域角度来讲，Hadoop也不适合处理实时的数据分析工作。

6.举例说明MapReduce的应用。

解：MapReduce多应用在日志分析、搜索引擎、数据挖掘以及信息提取等领域。例如索引系统是Google最大的MapReduce应用程序。Yahoo定期在搜索业务上使用Hadoop来提高其产品和服务，如排名功能和目标广告等。除此之外，也有一些直接使用Hadoop进行数据生成的案例。Hadoop 的长期目标是提供世界级的分布式计算工具，也是对下一代业务提供支持的Web扩展服务。

7.与Hadoop相比，Spark对大数据的处理速度为什么显然提升?

解：Spark是基于内存计算的，省去了Hadoop的大量的磁盘读写操作，而且有对于迭代操作支持延迟处理，在Action操作时才会进行真正的运算，这时可以对计算进行优化，也可以加快处理速度。

8.结合实例，讨论MapReduce在并行决策树算法的应用。

解：并行决策树算法基于MapReduce框架核心思想是分而治之的策略。将决策树算法中最耗时的属性相似度计算并行运行可以大大提高运行效率，在Map阶段，Map函数以单个元组的形式分解数据。计算属性的相似度，并以<属性名,相似度>的形式输出数据。Reduce阶段，对输出结果中的所有局部结果及相关汇总，找到最大相似度的属性名，选择这个属性作为测试节点，判断它是否为叶子节点，如果是叶子节点，则返回；反之，执行分裂，并将其录入待计算数据库中存储。

9.结合实例，讨论并行k-均值算法的计算过程。

解：用MapReudce框架实现k-均值算法，需要将k-均值每一次迭代作为一个Mapreduce Job，然后不断运行Mapreduce Job达到聚类的效果。在每一次迭代过程中，需要在Mapper中读取之前的聚类中心，然后读取每个样本点，计算该样本点到各个聚类中心的距离，按照它到每个聚类中心的距离进行归类。

在具体实现时，将输入数据集存储在分布式文件系统HDFS中，作为<Key, Value>的序列文件，每个<Key, Value>代表数据集的一条记录，其中Key为该记录对应于数据文件起始位置的偏移量，Value为该条记录的内容。将上次迭代(或初始化)得到的k个聚类中心放到Configuration中，然后在Mapper的setUp计算读取这k个聚类中心。Mapper会将同一类的数据发送到同一个Reducer，计算并判断某个样本到哪个中心最近。

在Reducer中，只需要根据数据重新计算聚类中心即可。重新计算聚类中心的方法也很简单，就是将该类包含的所有的样本点求均值即可。

10.查找资料，讨论如何对关联算法Apriori进行并行化改造？

解：随着数据规模的增大，传统并行方案因资源需求过大或因通信消耗过多而变得低效，基于云计算的MapReduce编程模型能很好地解决海量信息并行处理的通信问题，同时还具有负载均衡和强大的容错能力。

普通Apriori的Mapreduce并行化思想：首先利用MapReduce并行编程模型的键值进行特性对输入的原始数据集进行Map分块处理，主进程将这些数据分块分布到Hadoop集群中的每台计算机上，然后并行算法对每台计算机上的分块数据进行如下处理：

a.主进程通过分块数据集与原始数据集的对比产生1项候选集

b.由1项候选集与原始数据集进行对比，可以算出没想事务的支持度，这些支持度与程序中给定的支持度进行对比，得出1项频繁项集

c.由1项频繁项集产生2项频繁项集

d.主次迭代直到产生k项候选集，k项候选集与原始数据集对比，如果存在k项候选集，则继续迭代执行，如果不存在，则最终得到k-1项候选集

由于MapReduce的机制，上述过程为每台计算机上的Map进程计算出的分块候选集，接下来MapReduce编程模型中的Reduce进程把每台计算机上的Map进程获取的每个分块的k项候选集支持数合并获取全局k项候选集的支持数，由全集候选集的支持数计算出全集k项频繁项集。当一个数据分块的全局k项频繁项集计算出以后，每台计算机会启动下一个Map进程处理第二个数据分块，这样一次循环，知道架构处理完所有数据分块。

11.讨论对大样本数据，如何对多元线性回归模型进行并行化改造？

解：针对传统的多元线性回归预测方法处理时间长且受内存限制的特点，对时序样本数据设计了基于MapReduce的并行多元线性回归预测模型。模型由三组MapReduce过程组成，分别求解由历史数据所构成叉积矩阵的特征向量和标准正交特征向量，用来预测未来参数的特征值和特征向量矩阵和未来时刻回归参数的估计量。设计并实现了实验来验证提出的并行多元线性回归预测模型的有效性。实验结果表明，基于MapReduce的多元线性回归预测模型具有较好的加速比和可扩展性，适合于大规模时序数据的分析和预测。