架构师训练营第十三周课程笔记及心得
第一课:
大数据计算引擎 spark1
SparkVSHadoop:完成一个逻辑回归计算所需要的时间
Spark 特点(Spark 为什么更快)
DAG 切分的多阶段计算过程更快速
使用内存存储中间计算结果更高效
RDD 的编程模型更简单
使用 Spark 来实现 WordCount 变成示例:
val textFile = sc.textFile("hdfs://.….")
val counts = textFile.flatMap(line => line.split(" "))
.map(word =>(word, 1))
.reduceByKey(_ + _)
counts.saveAsTextFile(" hdfs:// ...")
第 1 行代码:根据 HDFS 路径生成一个输入数据 RDD。
第 2 行代码:在输入数据 RDD 上执行 3 个操作,得到一个新的 RDD。
·将输入数据的每一行文本用空格拆分成单词。
·将每个单词进行转换,word =>(word, 1),生成的结构。
·相同的 Key 进行统计,统计方式是对 Value 求和,(_ + _)
第 3 行代码:将这个 RDD 保存到 HDFS。
Spark 只是优化了编程过程计算过程,大致的计算方法和框架还是和 MapReduce 一样的
RDD 模型:
RDD 是 Spark 的核心概念,是弹性分布式数据集(Resilient Distributed Datasets )的缩写。RDD 既是 Spark 面向开发者的编程模型,又是 SparK 自身架构的核心元素。
作为 Spark 编程模型的 RDD。我们知道,大数据计算就是在大规模的数据集上进行一系列的数据计算处理。MapReduce 针对输入数据,将计算过程分为两个阶段,一个 Map 阶段,一个 Reduce 阶段,可以理解成是面向过程的大数据计算。我们在用 MapReduce 编程的时候,思考的是,如何将计算逻辑用 Map 和 Reduce 两个阶段实现,map 和 reduce 函数的输入和输出是么,MapReduce 是面向过程的。
WordCount 的代码示例里,第 2 行代码实际上进行了 3 次 RDD 转换,每次转换都得到一个新的 RDD,因为新的 RDD 可以继续调用 RDD 的转换函数,所以连续写成一行代码。事实上,可以分成 3 行。
val rdd1 = textFile.flatMap(line => line.split(" "))
val rdd2 = rdd1.map(word => (word, 1))
val rdd3 = rdd2.reduceByKey(L +)
RDD 上定义的函数分两种:
一种是转换(transformation)函数,这种函数的返回值还是 RDD;
RDD 定义了很多转换操作函数:
map(func)
过滤 filter(func)
合并数据集 union(otherDataset)
根据 Key 聚合 reduceByKey(func,[numPartitions])
连接数据集 join(otherDataset, [numPartitions])
分组 groupByKey([numPartitions])
作为数据分片的 RDD:
跟 MapReduce 一样,Spark 也是对大数据进行分片计算,Spark 分布式计算的数据分片、任务调度都是以 RDD 为单位展开的,每个 RDD 分片都会分配到一个执行进程去处理。
RDD 上的转换操作又分成两种:
一种转换操作产生的 RDD 不会出现新的分片(窄依赖,不发生 shuffle),比如 map、filter 等,也就是说一个 RDD 数据分片,经过 map 或者 filter 转换操作后,结果还在当前分片。就像你用 map 函数对每个数据加 1,得到的还是这样一组数据,只是值不同。实际上,Spark 并不是按照代码写的操作顺序去生成 RDD,比如 rdd2 = rdd1.map(func),这样的代码并不会在物理上生成一个新的 RDD。物理上,Spark 只有在产生新的 RDD 分片时候,才会在物理上真的生成一个 RDD,Spark 的这种特性也被称作惰性计算(在同一个分片中的多次连续操作会被整合,最后需要 shuffle 的时候才会统一针对分片进行计算)。
另一种转换操作产生的 RDD 则会产生新的分片(宽依赖,发生了 shuffle),比如 reduceByKey,来自不同分片的相同 Key 必须聚合在一起进行操作,这样就会产生新的 RDD 分片。然而,实际执行过程中,是否会产生新的 RDD 分片,并不是根据转换函数名就能判断出来的。
第二课:
大数据计算引擎 spark2
Spark 的计算阶段:
和 MapReduce 一个应用一次只运行一个 map 和一个 reduce 不同,Spark 可以根据应用的复杂程度,分割成更多的计算阶段(stage),这些计算阶段组成一个有向无环图 DAG,Spark 任务调度器可以根据 DAG 的依赖关系执行计算阶段。
这个 DAG 对应的 Spark 程序伪代码如下
rddB = rddA.groupBy(key)
rddD = rddC.map(func)
rddF = rddDiunion(rddE)
rddG = rddB.join(rddF)
整个应用被切分成 3 个阶段,阶段 3 需要依赖阶段 1 和阶段 2,阶段 1 和阶段 2 互不依赖。Spark 在执行调度的时候,先执行阶段 1 和阶段 2,完成以后,再执行阶段 3。如果有更多的阶段,Spark 的策略也是一样的。只要根据程序初始化好 DAG,就建立了依赖关系,然后根据依赖关系顺序执行各个计算阶段,Spark 大数据应用的计算就完成了。
Spark 作业调度执行的核心是 DAG,有了 DAG,整个应用就被切分成哪些阶段,每个阶段的依赖关系也就清楚了。之后再根据每个阶段要处理的数据量生成相应的任务集合(TaskSet),每个任务都分配一个任务进程去处理,Spark 就实现了大数据的分布式计算。
负责 Spark 应用 DAG 生成和管理的组件是 DAGScheduler,DAGScheduler 根据程序代码生成 DAG,然后将程序分发到分布式计算集群,按计算阶段的先后关系调度执行。
那么 Spark 划分计算阶段的依据是什么呢?显然并不是 RDD 上的每个转换函数都会生成一个计算阶段,比如上面的例子有 4 个转换函数,但是只有 3 个阶段。
当 RDD 之间的转换连接线呈现多对多交叉连接的时候,就会产生新的阶段。一个 RDD 代表一个数据集,图中每个 RDD 里面都包含多个小块,每个小块代表 RDD 的一个分片。
Spark 也需要通过 shuffle 将数据进行重新组合,相同 Key 的数据放在一起,进行聚合、关联等操作,因而每次 shuffle 都产生新的计算阶段。这也是为什么计算阶段会有依赖关系,它需要的数据来源于前面一个或多个计算阶段产生的数据,必须等待前面的阶段执行完毕才能进行 shuffle,并得到数据。
计算阶段划分的依据是 shuffle,不是转换函数的类型,有的函数有时候有 shuffle,有时候没有。例子中 RDDB 和 RDDF 进行 join,得到 RDDG,这里的 RDDF 需要进行 shuffle,RDD B 就不需要。
Spark 作业管理:
Spark 里面的 RDD 函数有两种:
一种是转换函数,调用以后得到的还是一个 RDD,RDD 的计算逻辑主要通过转换函数完成。
另一种是 action 函数,调用以后不再返回 RDD。比如 count()函数,返回 RDD 中数据的元素个数;saveAsTextFile(path),将 RDD 数据存储到 path 路径下。Spark 的 DAGScheduler 在遇到 shuffle 的时候,会生成一个计算阶段,在遇到 action 函数的时候,会生成一个作业(job)。
RDD 里面的每个数据分片,Spark 都会创建一个计算任务去处理,所以一个计算阶段会包含很多个计算任务( task )。
Spark 的执行过程:
Spark 支持 Standalone、Yarn、Mesos、Kubernetes 等多种部署方案,几种部署方案原理也都一样,只是不同组件角色命名不同,但是核心功能和运行流程都差不多。
Spark 生态:
第三课:
流处理计算:Flink、Storm、Spark Streaming
Spark 和 MapReduce 都是大数据批处理计算,相对应的 Flink,Storm,Spark Streaming 则是流处理计算也叫实时大数据处理计算
Storm 实时的 Hadoop
实时计算系统特点:
低延迟
高性能
分布式
可伸缩
高可用
Storm 的基本概念:
imbus:负责资源分配和任务调度。
Supervisor:负责接受 Nimbus 分配的任务,启动和停止属于自己管理的 Worker 进程。
Worker:运行具体处理组件逻辑的进程。
Task:Worker 中每一个 Spout/Bolt 的线程称为一个 Task。
Topology:Storm 中运行的一个实时应用程序,因为各个组件间的消息流动形成逻辑上的一个拓扑结构。
Spout:在一个 Topology 中产生源数据流的组件。通常情况下 Spout 会从外部数据源中读取数据,然后转换为 Topology 内部的源数据。Spout 是一个主动的角色,其接口中有个 nextTuple(函数,Storm 框架会不停地调用此函数,用户只要在其中生成源数据即可。
Bolt:在一个 Topology 中接受数据然后执行处理的组件。Bolt 可以执行过滤、函数操作、合并、写数据库等任何操作。Bolt 是一个被动的角色,其接口中有个 execute(Tuple input)函数在接受到消息后会调用此函数,用户可以在其中执行自己想要的操作。
Tuple:一次消息传递的基本单元。本来应该是一个 key-value 的 map,但是由于各个组件间传递的 tuple 的字段名称已经事先定义好,所以 tuple 中只要按序填入各个 value 就行了,所以就是一个 value list.
Stream:源源不断传递的 tuple 就组成了 stream。
基于 Spark 的流式计算 Spark Streaming:
Flink:与 Spark 类似,分成批处理计算和流处理计算,对应两种计算方法对象,当数据小的时候使用流处理,当数据比较大时使用批处理对象,不管是编程方法和实际执行都是复用的
第四课:
大数据基准测试工具 HiBench
HiBench 是 Intel 开放的一个 Hadoop Benchmark Suit,包含 9 个典型的 Hadoop 负载
Micro benchmarks
Sort
WordCount
TeraSort
HDFS benchmarks
DFSIO
web search benchmarks
Nutch indexing
PageRank
machine learning benchmarks
Mahout Bayesian classification
Mahout K-means clustering
data analytics benchmarks
Hive Query Benchmarks
主页是:https://github.com/intel-hadoop/hibench
第五课:
大数据分析与可视化
大数据:
大数据基础技术
大数据应用
互联网运营常用数据指标:
新增用户数
新增用户数是网站增长性的关键指标,指新增加的访问网站的用户数(或者新下载 App 的用户数),对于一个处于爆发期的网站,新增用户数会在短期内出现倍增的走势,是网站的战略机遇期,很多大型网站都经历过一个甚至多个短期内用户暴增的阶段。新增用户数有日新增用户数、周新增用户数、月新增用户数等几种统计口径。
用户留存率
新增的用户并不一定总是对网站(App)满意,在使用网站(App)后感到不满意,可能会注销账户(卸载 App),这些辛苦获取来的用户就流失掉了。网站把经过一段时间依然没有流失的用户称作留存用户,留存用户数比当期新增用户数就是用户留存率。
用户留存率=留存用户数/当期新增用户数
计算留存有时间窗口,即和当期数据比,3 天前新增用户留存的,称作 3 日留存;相应的,还有 5 日留存、7 日留存等。新增用户可以通过广告、促销、病毒营销等手段获取但是要让用户留下来,就必须要使产品有实打实的价值。用户留存率是反映用户体验和产品价值的一个重要指标,一般说来,3 日留存率能做到 40%以上就算不错了。和用户留存率对应的是用户流失率。
用户流失率=1-用户留存率
活跃用户数
用户下载注册,但是很少打开产品,表示产品缺乏黏性和吸引力。活跃用户数表示打开使用产品的用户数,根据统计口径不同,有日活跃用户数、月活跃用户数等。提升活跃是网站运营的重要目标,各类 App 常用推送优惠促销消息给用户的手段促使用户打开产品。
PV
打开产品就算活跃,打开以后是否频繁操作,就用 PV 这个指标衡量,用户每次点击,每个页面跳转,被称为一个 PV ( Page View )。PV 是网页访问统计的重要指标,在移动 App 上,需要进行一些变通来进行统计。
转化率
转化率是指在电商网站产生购买行为的用户与访问用户之比。
转化率=有购买行为的用户数/总访问用户数
用户从进入网站(App)到最后购买成功,√能需要经过复杂的访问路径,每个环节都有可能会离开:进入首页想了想没什么要买的,然后离开;搜索结果看了看不想买,然后离开;进入商品详情页面,看看评价、看看图片、看看价格,然后离开;放入购物车后又想了想自己的钱包,然后离开;支付的时候发现不支持自己喜欢的支付方式,然后离开...一个用户从进入网站到支付,完成一笔真正的消费,中间会有很大概率流失,网站必须要想尽各种办法:个性化推荐、打折促销、免运费、送红包、分期支付,以留住用户,提高转化率。
数据可视化图标与数据监控:
折线图
折线图是用的最多的可视化图表之一,通常横轴为时间,用于展示在时间维度上的数据变化规律,正向指标(比如日活跃用户数)斜率向上,负向指标(比如用户流失率)斜率向下,都表示网站运营日趋良好,公司发展欣欣向荣。
折线图
折线图是用的最多的可视化图表之一,通常横轴为时间,用于展示在时间维度上的数据变化规律,正向指标(比如日活跃用户数)斜率向上,负向指标(比如用户流失率)斜率向下,都表示网站运营日趋良好,公司发展欣欣向荣。
热力图
热力图用以分析网站页面被用户访问的热点区域,以更好进行页面布局和视觉展示。在地图上展示的热力图则表示了该地区的拥堵和聚集状态,方便用户进行出行规划
第六课:
网页排名算法 PageRank
PageRank,网页排名,又称网页级别,Google 左侧排名或佩奇排名,是一种由搜索引擎根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以 Google 公司斛辩人拉里·佩奇(Larry Page)之姓来命名。
PageRank 让链接来「投票」
PageRank 通过网络浩瀚的超链接開僚来确定一个页面的等级。Google 把从 A 页面到 B 页面的链接解释为 A 页面给 B 页面投票,Google 根据投票来源(甚至来源的来源,即链接到 A 页面的页面)和投票目标的等级来决定新的等级。简单的说,一个高等级的页面可以使其他低等级页面的等级提升。
一个页面的「得票数」由所有链向它的页面的重要性来决定,到一个页面的超链接相当于对该页投一票。一个页面的 PageRank 是由所有链向它的页面(「链入页面」)的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级,相反如果一个页面没有任何链入页面,那么它没有等级。
PageRank 算法:
假设一个由 4 个页面组成的小团体:A,B,C 和 D。如果所有页面都链向 A,那么 A 的 PR ( PageRank)值将是 B,C 及 D 的 Pagerank 总和。PR(A) = PR(B) + PR(C) + PR(D)
继续假设 B 也有链接到 C,并且 D 也有链接到包括 A 的 3 个页面。一个页面不能投票 2 次。所以 B 给每个页面半票。以同样的逻辑,D 投出的票只有三分之一算到了 A 的 PageRank 上。换句话说,根据链出总数平分一个页面的 PR 值。PR(A) =PR(B)/L(B)+PR(C)/L(C)+ PR(D)/L(D)
问题:
互联网中一个网页只有对自己的出链,或者几个网页的出链形成一个循环圈。那么在不断地迭代过程中,这一个或几个网页的 PR 值将只增不减,显然不合理。如下图中的 C 网页就是刚刚说的只有对自己的出链的网页
解决方法:
为了解决这个问题。我们想象一个随机浏览网页的人,假定他有一个确定的概率会输入网址直接跳转到一个随机的网页,并且跳转到每个网页的概率是一样的。于是则此图中 A 的 PR 值可表示为:PR(A) =α(PR(B)/2)+(1-α)/4
计算公式:PL,P...PN 是被研究的页面,M(pi)是链入 P 页面的集合,L(p)是 P 链出页面的数量,而 N 是所有页面的数量。
PageRank 值是一个特殊矩阵中的特征向量。这个特征向量为:
最终的公式:
第七课:
分类和聚合算法:
KNN 分类算法:
KNN 算法,也叫 K 近邻(K NearestNeighbour)算法对于一个需要分类的数据,将其和一组已经分类标注好的样本集合进行比较,得到距离最近的 K 个样本,K 个样本最多归属的类别,就是这个需要分类数据的类别。
算法过程:
对两个数据如何进行距离计算:
对于数据 xi 和 xj,若其特征空间为 n 维实数向量空间 Rn,即 xi=(xi1,xi2,...xin),xj=(xj1,xj2,...,xjn)
提取文本的特征值 TF-IDF 算法
TF 是词频(Term Frequency),表示某个单词在文档中出现的频率。
IDF 是逆文档频率(Inverse Document Frequency),表示这个单词在所有文档中的稀缺程度。
贝叶斯分类算法:
公式:
应用:前面提到过的垃圾邮件分类:
K-means 聚类算法:
给定一组数,进行分类的算法(已知类别数量)
第 1 步:随机在图中取 K 个种子点,图中 K=2,即图中的实心小圆点
第 2 步:求图中所有点到这 K 个种子点的距离,假如一个点离种子点×最近,那么这个点属于×点群。在图中,可以看到 A、B 属于上方的种子点,C、D、E 属于中部的种子点。
第 3 步:对已经分好组的两组数据,分别求其中心点。对于图中二维平面上的数据,求中心点最简单暴力的算法就是对当前同一个分组中所有点的 X 坐标和 Y 坐标分别求平均值,得到的就是中心点。
第 4 步:重复第 2 步和第 3 步,直到每个分组的中心点不再移动。这时候,距每个中心点最近的点数据聚类为同一组数据。
第八课:
推荐引擎算法:
基于人口统计的推荐:
基于商品属性的推荐:
基于用户的协同过滤推荐:
基于商品的协同过滤推荐:
除了上述几种推荐还可以使用深度学习等进行推荐
第九课:
机器学习与神经网络算法
机器学习系统通用架构:
概念:
样本:
就是通常我们常说的“训练数据”,包括输入和结果两部分。比如我们要做一个自动化新闻分类的机器学习系统,对于采集的每一篇新闻,能够自动发送到对应新闻分类频道里面,比如体育、军事、财经等。这时候我们就需要批量的新闻和其对应的分类类别作为训练数据。通常随机选取一批现成的新闻素材就可以,但是分类需要人手工进行标注,也就是需要有人阅读每篇新闻,根据其内容打上对应的分类标签。
T=(x1,y1),(x2,y2),...(xn,yn)其中 xn 表示一个输入,比如一篇新闻;yn 表示一个结果,比如这篇新闻对应的类别。
模型:
模型就是映射样本输入与样本结果的函数,可能是一个条件概率分布,也可能是一个决策函数。“个具体的机器学习系统所有可能的函数构成了模型的假设空间,数学表示是:F=f|y=f(X)。其中 X 是样本输入,Y 是样本输出,f 就是建立 X 和 Y 映射关系的函数。所有 f 的可能结果构成了模型的假设空间 F。很多时候 F 的函数类型是明确的,需要计算的是函数的参数,比如确定 f 函数为一个线性函数,那么 f 的函数表示就可以写为:y=a1x+a0。这时候需要计算的就是 a1 和 a0 两个参数的值。这种情况下模型的假设空间的数学表示是:F={f|Y=fθ(X),θ∈R^n}。其中 0 为 f 函数的参数取值空间,一个 n 维欧氏空间,被称作参数空间。
算法:
算法就是要从模型的假设空间中寻找一个最优的函数,使得样本空间的输入 X 经过该函数的映射得到的 f(X),和真实的 Y 值之间的距离最小。这个最优的函数通常没办法直接计算得到,即没有解析解:需要用数值计算的方法不断迭代求解。因此如何寻找到 f 函数的全局最优解,以及使寻找过程尽量高效,就构成了机器学习的算法。
如何保证 f 函数或者 f 函数的参数空间最接近最优解,就是算法的策略。机器学习中用损失函数来评估模型是否最接近最优解。损失函数用来计算模型预测值与真实值的差距,常用的有 0-1 损失函数、平方损失函数、绝对损失函数、对数损失函数等。以平方损失函数为例,损失函数如下:L(Y,f(X))=(Y -f(X))^2
对于一个给定的样本数据集:
模型 f(X)相对于真实值的平均损失为每个样本的损失函数的求和平均值:
这个值被称作经验风险,如果样本量足够大,那么使经验风险最小的 f 函数就是模型的最优解,即求:
但是相对于样本空间的可能取值范围,实际中使用的样本量总是有限的,可能会出现使样本经验风险最小的模型 f 函数并不能使实际预测值的损失函数最小,这种情况被称作过拟合
过拟合:即一味追求经验风险最小,而使模型 f 函数变得过于复杂,偏离了最优解。这种情况下,需要引入结构风险以防止过拟合。结构风险表示为:
在经验风险的基础上加上入 J(f),其中 J(f)表示模型 f 的复杂度,模型越复杂,J(f) 越大。要使结构风险最小,就要使经验风险和模型复杂度同时小。求解模型最优解就变成求解结构风险最小值:
机器学习的数学原理:
给定模型类型,也就是给定函数类型的情况下,如何寻找使结构风险最小的函数表达式。由于函数类型已经给定,实际上就是求函数的参数。各种有样本的机器学习算法基本上都是在各种模型的假设空间上求解结构风险最小值的过程,理解了这一点也就理解了各种机器学习算法的推导过程。
机器学习要从假设空间寻找最优函数,而最优函数就是使样本数据的函数值和真实值距离最小的那个函数。给定函数模型,求最优函数就是求函数的参数值。给定不同参数,得到不同函数值和真实值的距离,这个距离就是损失,损失函数是关于模型参数的函数,距离越小,损失越小。最小损失值对应的函数参数就是最优函数。
例:感知机
感知机是一种比较简单的二分类模型,将输入特征分类为+1、-1 两类,就像下图所示的,一条直线将平面上的两类点分类。
感知机模型:其中 x 代表输入的特征空间向量,输出空间是{-1,+1},w 为权值向量,b 叫作偏置,sign 是一个符号函数。
训练感知机模型就是要计算出 w 和 b 的值,当有新的数据需要分类的时候,输入感知机模型就可以计算出+1 或者-1 从而进行分类。
计算过程分析:
由于输出空间只有{-1,+1}两个值,所以只有误分类的时候,才会有模型计算值和样本真实值之间的偏差,偏差之和就是感知机的损失函数。
其中 M 为误分类点集合,误分类点越少,损失函数的值越小;如果没有误分类点,损失函数值为 0。求模型的参数 w 和 b,就是求损失函数的极小值。
数学上求函数的极小值就是求函数的一阶导数,但是感知机损失函数用统计求和函数表达,没办法计算解析解。机器学习采用梯度下降法求损失函数极小值,实质上就是求导过程的数值计算方法。
具体方法:
对于误分类点集合 M,损失函数 L(w,b)变化的梯度,就是某个函数变量的变化引起的函数值的变化,根搪感知机损失函数可知:
使用梯度下降更新 w 和 b,不断迭代使损失函数 L(w,b)不断减小,直到为 0,也就是没有误分类点。
具体过程:
选择初始值 wo,b0。
在样本集合中选择样本数据 xi,yi。
如果 yi(w-xi+b)<0,表示 yi 为误分类点,那么 W=w+nyixi、b=b+nyi,在梯度方向校正 w 和 b。其中 n 为步长,步长选择要适当,步长太长会导致每次计算调整太大出现震荡;步长太短又会导致收敛速度慢、计算时间长。
跳转回 2,直到样本集合中没有误分类点,即全部样本数据 yi(w·xi+b)≥0。
神经网络:
利用感知机构建神经网络:
版权声明: 本文为 InfoQ 作者【Airs】的原创文章。
原文链接:【http://xie.infoq.cn/article/457382af2d41387b8aa825ade】。未经作者许可,禁止转载。
评论