总结

本周内容是流计算与机器学习。大数据是薄弱环节，而机器学习因为18年搞过银行卡卡号识别，可以理解课程内容。

Spark

Spark是MapReduce之后的新秀，是一个分布式内存式计算引擎。MapReduce在大规模应用之后，人们发现其编程模型复杂，需要手工编写Map和Reduce两个步骤，还要组织计算过程，开发效率低。Spark提出了基于RDD的编程模型，利用DAG调度计算，极大的提高了开发效率。

Spark的开发模型类似于现在已普遍应用的Java8 stream API，是基于集合的操作，分为变换操作和执行操作。变换操作是懒操作，并且不产生新的RDD，执行操作产生新的RDD。RDD之间有依赖关系。若父RDD的每个分区最多被一个子RDD的分区依赖，称作窄依赖。若父RDD的一个分区被子RDD的多个分区依赖，称作宽依赖。调度器根据RDD的依赖生成DAG。一个DAG由若干stage构成，一个stage包含若干连续窄依赖，而stage之间是宽依赖。

流计算

storm

Hadoop是批处理系统，storm则是实时流处理系统。对应于Hadoop的系统组件，storm响应的组件是

• 资源分配与工作调度Nimbus

• 分配任务到worker的Supervisor

• 具体处理逻辑的进程Worker

• Task：每个spout/bolt线程被称作一个Task

此外，各个组件间消息的流动形成逻辑上的拓扑结构，称为Topology。spout为topology生成数据流，bolt消费数据流，tuple是消息传递单元，源源不断的tuple就形成了数据流stream。

spark streaming

spark本是是内存式批处理系统，作为流计算引擎的思路是把批划小，每次处理一个小批，这样连续不断的小批处理就像是流处理一样。

Flink

Flink是德国的产品，其思路与spark streaming如出一辙，近来大有赶超Spark Streaming之势。

作业



简述pagerank算法



pagerank算法是以发明人Larry Page命名的网页排名算法，是Page创立Google的核心技术之一。



基本思想



1. 被引用越多的网页越有价值

2. 被越有价值的网页引用的网页越有价值



算法



一个页面的PR值来自于引用它的页面，该页面也要把自己的PR值平分给被引用页面。于是有

$p_1,...,p_n表示被研究的网页。$

写成矩阵的形式为，

$r_i表示p_i的PR值。{\sum }_{i=1}^N\mathbf{l}(p_i,p_j)=1$

$R$初始化为单位向量，然后经过迭代，知道变化小于阈值，或是达到迭代次数上限。最后$R$的各分量就是个页面的PR值。