第十三周学习总结

Spark 架构

Spark 则是 UC Berkeley AMP lab 所开源的类 Hadoop MapReduce 的通用并行框架, 专门用于大数据量下的迭代式计算。

Spark 通常来说运算比 Hadoop 的 MapReduce 框架快，原因是很简单： Hadoop 在一次 MapReduce 计算后会写入磁盘，所以 2 次运算间会有多余 IO 消耗；而 Spark 则是将数据一直缓存在内存中，直到计算结束再写入磁盘，多次运算的情况下, Spark 是比较快的。Spark 的主要特点还包括:

1. 提供 Cache 机制来支持需要反复迭代计算或者多次数据共享，减少数据读取的 IO 开销

2. 提供了一套支持 DAG 图的分布式并行计算的编程框架，减少多次计算中间值写到 HDFS 的开销

3. 使用多线程池模型减少 Task 启动开稍, shuffle 过程中避免不必要的 sort 操作并减少磁盘 IO 操作

Spark 执行过程

Spark 任务

• 整个 Spark 集群中有两个重要的角色：Master 节点与 worker 节点。其中 Master 负责将串行任务变成可并行执行的任务集 Tasks, 同时还负责出错问题处理等；此外，Master 负载管理全部的 Worker 节点，而 Worker 节点负责执行任务。

• Driver 的功能是创建 SparkContext——一般常驻 Master 节点，负责执行用户写的 Application 的 main 函数进程——Application 就是用户写的程序。

• 每个 Worker 上存在一个或多个 Executor 进程；该对象拥有一个线程池，每个线程负责一个 Task 任务的执行。

• Task 任务即为具体执行的 Spark 程序的任务.

Spark 计算阶段

上面提到的 Driver 进程会将我们编写的 Spark 作业代码分拆为多个 stage，每个 stage 执行一部分代码片段，并为每个 stage 创建一批 Task，然后将这些 Task 分配到各个 Executor 进程中执行。Task 是最小的计算单元，负责执行一模一样的计算逻辑，只是每个 Task 处理的数据不同。

Spark Stage

一个 stage 的所有 Task 都执行完毕之后，会在各个节点本地的磁盘文件中写入计算中间结果，然后 Driver 就会调度运行下一个 stage。下一个 stage 的 Task 的输入数据就是上一个 stage 输出的中间结果。如此循环往复，直到将我们自己编写的代码逻辑全部执行完，得到我们想要的结果为止。

RDD

RDD（Resilient Distributed Datasets）俗称弹性分布式数据集，是 Spark 底层的分布式存储的数据结构，Spark API 的所有操作都是基于 RDD 实现。

RDD 是一种只读的数据块，可以从外部数据转换而来，我们也可以对 RDD 进行函数操作（Operation）——包括 Transformation 和 Action：

Operation 函数区别 Transformationmap, filter, groupBy, join, union, reduce, sort, partitionBy 返回 RDD，不会马上提交 Spark 集群运行 Actioncount, collect, take, save, show 返回的不是 RDD，会形成 DAG 图， 提交 Spark 集群运行并立即返回结果

RDD 的 Transformation 操作无须将中间结果落地到 HDFS 进行容错——只在内存中操作，所以速度较快。此外 Transformation 函数又可再细分为窄依赖（narrow dependency）和宽依赖（wide dependency）的操作。窄依赖跟宽依赖的区别是是否发生 shuffle 操作：宽依赖会发生 shuffle 操作；窄依赖是子 RDD 的各个分片，不依赖于其他分片，能够独立计算得到结果。

流计算

目前主流的流式计算框架有 Storm、Spark Streaming 和 Flink 三种，其基本原理如下：

Apache Storm

Storm

Storm 设计了一个实时计算结构——Topology，这个拓扑结构会被框架提交给计算集群（其中 Master 负责给 Worker 节点分配代码，Worker 节点负责执行代码）。在这个 Topology 结构中，包含 spout 和 bolt 两种角色：数据在 spouts 之间传递；而 bolt 则负责转换数据流。

Spark Streaming

Spark Streaming

Spark Streaming 是 Spark API 的扩展，它在处理数据流之前会按照时间间隔对数据流进行分段切分。Spark 针对连续数据流的抽象被称为 DStream；它是一组小批量的 RDD，可以通过任意函数和滑动窗口进行转换，实现并行操作。

Apache Flink

Flink

Flink 是针对流处理+批处理的计算框架：流处理的输入流是无界的；而批数据是一种特殊的流处理，输入流被定义为有界的。

Flink 程序由 Stream 和 Transformation 这两个基本构建块组成：Stream 是一个中间结果数据；而 Transformation 是一个操作，对一个或多个 Stream 进行计算，输出一个或多个结果 Stream。

数据可视化

• 新增用户：指新增加的访问网站的用户数（或者新下载 APP 的用户数）

• 用户存留：存留用户数 / 当期新增用户数

• 活跃用户：表示经常打开使用产品的用户数。根据统计口径不同，又可分为日活用户、月活用户等等

• PV：用户每次点击，每个页面跳转，就是 PV（Page View）；用于统计产品在打开后是否频繁操作

• GMV：即总成交金额（Gross Merchandise Volume），是电商网站的流水，反应网站营收能力的重要指标

• 转化率：有购买行为的用户数 / 总访问用户数

机器学习

PageRank

课程内详解

KNN

最近邻居法（KNN 算法，又译 K-近邻算法）是一种用于分类和回归的非参数统计方法。对于一个需要分类的数据，将其和一组已经分类标注好的样本集合进行比较，得到距离最近的 K 个样本，K 个样本最多归属的类别就是这个需要分类数据的类别。

• 在 KNN 分类中，输出是一个分类族群。一个对象的分类是由其邻居的“多数表决”确定的，k 个最近邻居（k 为正整数，通常较小）中最常见的分类决定了赋予该对象的类别。若 k = 1，则该对象的类别直接由最近的一个节点赋予。

• 在 KNN 回归中，输出是该对象的属性值。该值是其 k 个最近邻居的值的平均值。

算法比较简单，我们举个例子如下：中心的黑圈白点就是要分类的数据，如果 k=3，它就被分配给红色，因为有两个点是红的，且只有一个点是绿的；如果 k=5，它就被分配给红色，因为三个点是绿的，两个点是红的。

KNN

K-means

K-平均算法作为一种聚类分析方法流行于数据挖掘领域。k-means 聚类的目的是：把 n 个点划分到 k 个聚类中，使得每个点都属于离他最近的均值（此即聚类中心）对应的聚类，以之作为聚类的标准。

K-means 聚类的问题事实上是 NP hard 问题，不过存在一种高效的启发式算法。我们简单介绍一下算法的主要步骤：

1. 给定 K 值：就是设定总共分成多少个聚类

2. 随机选定 K 个中心点（质心）

3. 计算每一个点到这 K 个质心的距离

4. 将每个点聚类为离它最近的一个质心的所在类别中

5. 经过上一次分类后，对同一类的数据求平均值，将这个平均值作为新的聚类质心

6. 重复 3、4、5，直到质心不在变化为止

经过如上步骤，我们就可以得到稳定的 K 个聚类了：

K-means

推荐引擎算法

推荐引擎算法，就是很多网站中一个叫“猜你喜欢”的算法。虽然，具体算法模型我们不得而知，但是常用推荐值机通常有这么几种：

• 基于人口统计学的推荐：根据系统用户的基本信息发现用户的相关程度，然后将相似用户喜爱的其他物品推荐给当前用户

• 基于内容的推荐：根据推荐物品或内容的元数据，发现物品或者内容的相关性，然后基于用户以往的喜好记录，推荐给用户相似的物品

• 基于项目的协同过滤推荐：根据用户对物品或者信息的偏好，发现物品或者内容本身的相关性，或者是发现用户的相关性，然后再基于这些关联性进行推荐

• 混合的推荐机制：就是通过加权、切换、区分、分层等等手段混合上述推荐机制

感知机

感知机是一种二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，+1 代表正类，-1 代表负类。感知机属于判别模型，它的目标是要将输入实例通过分离超平面将正负二类分离。

感知机

模型其实很简单：

感知机模型

由于输出空间只有 {-1, +1}，所以只有误分类的时候才会有模型计算值和样本真实值之间的偏差，偏差之和就是所谓的损失函数：

感知机损失函数

感知机学习算法是对上述损失函数进行极小化，求得 w 和 b。感知机算法实现上一般不用普通的批量梯度下降法，而是采用随机梯度下降法。算法训练过程如下：

1. 赋初值 w0,b0
   

2. 选取数据点 (xi,yi)
   

3. 判断该数据点是否为当前模型的误分类点，即判断若 yi(w⋅xi+b) <= 0 则更新如下向量：

4. 转到 2，直到训练集中没有误分类点

p.s. η(0<η<1) 为学习率

神经网络

神经网络是一种模仿生物神经网络（动物的中枢神经系统，特别是大脑）的结构和功能的数学模型或计算模型，用于对函数进行估计或近似。

神经网络

• 神经元按照层来布局。最左边的层叫做输入层，负责接收输入数据；最右边的层叫输出层，我们可以从这层获取神经网络输出数据。输入层和输出层之间的层叫做隐藏层，因为它们对于外部来说是不可见的。

• 同一层的神经元之间没有连接。

• 第 N 层的每个神经元和第 N-1 层的所有神经元相连，第 N-1 层神经元的输出就是第 N 层神经元的输入。

• 每个连接都有一个权值。神经网络的训练，就是训练这个权重值。