1.集成配置

我这边使用maven构建项目，大家根据实际修改。Pom文件配置，截取了需要的部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

<dependency>
  <groupId>org.apache.spark</groupId>
  <artifactId>spark-sql_${scala.binary.version}</artifactId>
  <version>${spark.version}</version>
</dependency>
<!-- https://mvnrepository.com/artifact/org.apache.kudu/kudu-client -->
<dependency>
  <groupId>org.apache.kudu</groupId>
  <artifactId>kudu-client</artifactId>
  <version>1.10.0</version>
</dependency>

<!-- https://mvnrepository.com/artifact/org.apache.spark/spark-sql-kafka-0-10 -->
<dependency>
  <groupId>org.apache.spark</groupId>
  <artifactId>spark-sql-kafka-0-10_2.11</artifactId>
  <version>2.3.0</version>
</dependency>

1.配置hive-site.xml

首先声明一下，这里默认大家已经安装好了hive和sas，没有安装好的请参考网上的教程安装。hive-site.xml是
Hive的配置文件，位于$HIVE_HOME/conf文件夹下，在其中添加如下配置：

远程访问Hive，有好几种身份验证方式，因为我们的Hive服务仅在局域网中访问，简单起见，可以配置为NONE，
也就是不进行身份验证，NONE也是hive.server2.authentication的默认值。

多数据源Join维度表思路

很多时候流上报过来的数据只有id，这时需要我们join维度表，这里有三种思路：
1.在数据源端进行join，如在kafka写入时进行join，不过这需要数据源端配合。
2.在计算引擎上join，如spark streaming/flink。
3.在结果端，如结果写入es/mysql，可在此时根据key join。
这三种方式大家按实际情况进行取舍，各自有自己的适用场景。我这里主要介绍在
计算引擎端进行join。

逻辑回归

线性回归模型产生的预测值$z=\boldsymbol{w}^{T}\boldsymbol{x}+b$是实值，如果我们要做二分类任务，该怎么办？我们需要将实值z转换为0/1值。
我们可以借助于Sigmoid函数（对数几率函数），将Sigmoid函数作为g-(.)进行转换，得到

FTRL本质上是逻辑回归的一个变种，是一个在线学习的优化器。

推荐系统介绍

什么是推荐系统

这里先说一下“连接”这个词，凡是能够产生关系的都是连接，像用户对物品的行为，用户的属性和物品的属性一样等等。随着各种物品智能化，
万物互联的时代到来，会倾向于建立越来越多的连接。人和人有更多连接，于是有了各种社交产品；人和物品有越来越多消费连接，于是有了
各种电商产品等。
推荐做的事就是连接，也就是将用户和物品连接起来。推荐系统通过背后算法和技术，用已有的连接去预测未来用户和物品之间会出现的连接。
从本质上来讲，他提高了信息分发和信息获取的效率。

必要条件

1.互斥
每个资源要么是可用，要么是被进程占用
2.占有和等待
得到某个资源的进程可以再请求新的资源
3.不可抢占
已分配给一个进程的资源不能强制性地被抢占，只能被占有的进程显式的释放
4.环路等待
有两个或者两个以上的进程组成一条环路，让环路中的每个进程都在等待下一个进程

处理方法

1.鸵鸟策略
2.死锁检测与死锁恢复
3.死锁预防
4.死锁避免

鸵鸟策略

假装问题没有发生，忽略他。

死锁检测与死锁恢复

当死锁时，采取恢复措施。

每种类型一个资源的死锁检测

进程与线程

1.进程是资源分配的基本单位
2.线程是独立调度的基本单位
3.区别：
拥有资源
调度
系统开销
通信方面
编程复杂性

进程的状态切换

进程调度算法

1.批处理系统：
先来先到服务（fcfs）
短作业优先（sjf）
最短剩于时间（srtn）
2.交互式系统：
时间片轮转
优先级调度
多级反馈队列
3.实时系统：
请求在一个确定时间内得到响应

进程同步

1.临界区
2.同步与互斥
3.信号量
4.管程

经典同步问题

1.读者-写者问题
2.哲学家进餐问题

进程通信

1.管道
只支持父子进程中通信
2.FIFO（命名管道）
去除了管道只能在父子进程中使用的限制
3.消息队列
消息队列可以独立于读写进程，避免了FIFO的同步阻塞问题，读进程可以根据消息队列有选择的接受
4.信号量
是一个计数器，控制多进程对共享数据的访问
5.共享存储
允许多个进程共享一个给定的存储区，结合信号量使用
6.套接字
用于不同机器之间的通信

俄罗斯套娃

题目

You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

Note:
Rotation is not allowed.

Example:

Input: [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

MAB问题

bandit算法来源于大家熟悉的赌博学。一个赌徒，要去摇老虎机，而每个老虎机吐钱的概率不一样，他不知道老虎
机吐钱的概率分布，怎样才能收益最大化呢？这就是多臂老虎机赌博问题，简称MAB问题。
1.当推荐系统有新用户时，怎么快速地知道他对每类内容的感兴趣程度？即推荐系统冷启动问题。
2.系统中有若干广告库存物料，怎样展示，才能点击收益最大呢，是不是每次都挑最好的那个？
3.设计了新的策略或者模型，如何知道他和旧模型谁更靠谱又对风险可控呢？
这些关于选择的问题，我们都可以简化成一个MAB问题。
对于推荐系统里的两个顽疾，一个冷启动，一个探索利用，bandit算法都可以提供帮助。

bandit算法

思想：看看选择会带来多少遗憾，遗憾越少越好。在 MAB 问题里，用来量化选择好坏的指标就是累计遗憾，计算公
式如图。

公式由两部分构成：一个是遗憾，一个是累积。求和符号内部就表示每次选择的遗憾多少。
Wopt表示选择了最好的选择获得收益，WB(i)表示实际选择得到的收益，两者之差就是遗憾的量化，T次之后，就有了
累计遗憾。
他的套路就是：小心翼翼地试，越确定某个选择好，就多选择它，越确定某个选择差，就越来越少选择它。简单说就
是，把选择的机会给“确定好的”和“还不确定的”。
bandit算法有几个关键元素：臂，回报，环境。
1.臂：每次选择的候选项，好比老虎机，有几个选项就有几个臂；
2.回报：就是选择一个臂之后得到的奖励，好比选择一个老虎机后突出的金币；
3.环境：决定每个臂不同的那些因素，统称环境。
类比推荐系统：
1.臂：每次推荐的候选池，可以是具体物品，也可以是推荐策略，也可能是物品类别；
2.回报：用户是否对推荐结果喜欢，喜欢就是正面回报，没有就是负面回报或者零回报；
3.环境：用户就是不可捉摸的环境。

汤普森采样算法

原理：假设每个臂是否产生收益，是由一个概率分布决定的，这个概率分布是贝塔分布。每次选择时，每个臂产生一
随机数，按这个数排序，产生最大随机数的那个物品为输出。

贝塔分布由两个参数a和b决定，他们决定了分布的形状和位置：
1.当a+b值越大，分布曲线越窄，分布就越集中，这样产生的随机数容易靠近中心位置；
2.当a/a+b的值越大，分布中心位置越靠近1，反之越靠近0，这样产生的随机数也相应更容易靠近1或者0.
我们可以简化成3种情况：
1.曲线很窄，而且靠近1；
2.曲线很窄，而且靠近0；
3.曲线很宽。
我们把贝塔分布的a参数看成推荐后得到用户点击的次数，把分布的b参数看成是没有得到用户点击的次数，这样就和
推荐系统联系上了。
实际使用时，要为每个用户保存一套参数，候选集有m个，用户有n个，那么就要保存2mn个参数。

UCB算法

UCB 算法全称是 Upper Confidence Bound，即置信区间上界。每次选择评分最高的候选臂输出，每次输出后观察用户
反馈，回来更新候选臂的参数。公式为

公式有两部分，加号前面是这个候选臂到目前的平均收益，后面叫做Bonus，本质上是均值的标准差，反应了候选臂效
果的不确定性，即置信区间的上边界。t是目前的总选择次数，Tjt是每个臂被选择次数。
由公式我们可知，平均收益很大，bonus大，被选择时有优势。
他的思想和汤普森采样一样：
1.以每个候选的平均收益为基准线进行选择；
2.对于被选择次数不足的给与照顾；
3.选择倾向的是那些确定收益较好的候选。

Epsilon贪婪算法

略

效果对比

汤普森采样>UCB>Epsilon贪婪算法>朴素选择>完全随机

冷启动

冷启动问题，我们很容易想到利用Bandit算法来帮忙解决。
针对每个新用户维护k个topic，使用Bandit方式。