推荐系统三十六式学习笔记：原理篇.近邻推荐07|人以群分，你是什么人就看到什么世界

谈及推荐系统，不得不说大名鼎鼎的协同过滤。协同过滤的重点在于协同，所谓协同，也就是群体互帮互助，互相支持是群体智慧的体现，协同过滤也是这般简单直接，历久弥新。

协同过滤

当你的推荐系统过了只能使用基于内容的推荐阶段后，就有了可观的用户行为了。这时候的用户行为通常是正向的，也就是用户或明或暗地表达着喜欢的行为。这些行为可以表达成一个用户和物品的关系矩阵，或是网络，或是图，本质是一个东西。

这个用户物品关系矩阵中填充的就是用户对物品的态度，但并不是每个位置都有，需要的就是把那些还没有的地方填充起来。这个关系矩阵是协同过滤的关键，一切都围绕它来进行；

协同过滤是一个比较大的算法范畴。通常划分为两类；
1、基于记忆的协同过滤（Memory-Based）
2、基于模型的协同过滤（Model-Based）

基于记忆的协同过滤，就是记住每个人消费过什么东西，然后推荐相似的东西，或者推荐相似的人消费的东西。基于模型的协同过滤则是从用户物品关系矩阵中去学习一个模型，从而把那些矩阵空白处填满；

今天先讲一下基于基于的协同过滤的一种：基于用户，或者叫做User-Based；

基于用户的协同过滤

背后的思想

你有没有过这种感觉，你遇到一个人，你发现你喜欢的书，他也喜欢，你喜欢的音乐，他也在听，你喜欢看的电影，他也至少看了两三遍，你们这叫什么，志同道合。所以问题来了，他又看了一本书，又听了一首歌，你会不会正好也喜欢呢？

这个感觉非常的自然，这就是基于用户的协同过滤背后的思想。详细来说就是：先根据历史消费行为帮你找到一群和你口味相似的用户，然后根据这些和你很相似的用户消费了什么新的、你没见过的物品、都可以推荐给你。

这就是我们常说的物以类聚人以群分，你是什么人，你就会遇到什么人。

这其实也是一个用户聚类的过程，把用户按照兴趣口味聚类成不同的群体，给用户产生的推荐就来自这个群体的平均值；所以要做好这个推荐，关键是如何量化口味相似这个指标。

原理

我们来说一下基于用户的协同过滤具体是怎么做的，核心是那个用户物品的关系矩阵，这个矩阵是最原始的材料。

第一步，准备用户向量，从这个矩阵中，理论上可以给每一个用户得到一个向量 。为什么说要是理论上呢？因为得到向量的前提是：用户需要在我们产品里有行为数据，否则就得不到这个向量。

这个向量有这么三个特点：
1、向量的维度就是物品的个数；
2、向量是稀疏的，也就是说并不是每个位置都有值；
3、向量维度上的取值可以是简单的0或1，1表示喜欢过，0表示没有；

第二步，用每一个用户的向量，两两计算用户之间的相似度，设定一个相似度阈值，为每个用户保留与其最相似的用户。

第三步，为每一个用户产生推荐结果。
把和他相似的用户们喜欢过的物品汇总起来，去掉用户自己已经消费过的物品，剩下的排序输出就是推荐结果。

这个公式，等号左边就是计算一个物品i和一个用户u的匹配分数，等号右边是这个分数的计算过程，分母是把用户u相似的n个用户的相似度累加起来分子是把这n个用户各自对物品i的态度，按照相似度加权求和。这里的态度最简单就是0或1,1表示喜欢过，0表示没有，如果是评分，则可以是0到5的取值。整个公式就是相似用户们的态度加权平均值。

实践

原理看上去很简单，但是在实现上却有一些坑，需要非常小心；
1、只有原始的用户行为日志，需要从中构造矩阵，怎么做？
2、如果用户的向量很长，计算一个相似度则耗时很久，怎么办？
3、如果用户量很大，而且通常如此，而且两两计算用户相似度也是一个大坑，怎么办？
4、在计算推荐时，看上去要为每一个用户计算他和每一个物品的分数，又是一个大坑，怎么办？

1、构造矩阵

我们在做协同过滤计算时，所用的矩阵是稀疏的，也就是说很多矩阵元素不用存，都是0,这里介绍典型的稀疏矩阵存储格式。
1.CSR:这个存储稍微复杂点，是一个整体编码方式。它有三个组成：数值，列号和行偏移共同编码。COO
2.COO:这个存储方式很简单，每个元素由三元组表示（行号，列号,数值），只存储有值的元素，缺失值不存储。
这些存储格式，在常见的计算框架里面都是标准的，如Spark中，Python的Numpy包中。把你的原始行为日志转换为上述的格式，就可以使用常用的计算框架的标准输入了。

2、相似度计算

相似度计算是个问题。
首先是单个相似度计算问题，如果碰上向量很长，无论什么相似度计算方法，都要遍历向量。所以通常下降相似度计算复杂度的办法有两种。

1、对向量采样计算。如果两个100维向量的相似度是0.7，我们牺牲一些精度，随机从取出10维计算，以得到的值作为其相似度值，虽然精度下降，但执行效率明显快了很多。这个算法由Twitter提出，叫做DIMSUM算法，已经在spark中实现了。

2、向量化计算，与其说是一个技巧，不如说是一种思维。在机器学习领域，向量之间的计算时家常便饭，现代的线性代数库都支持直接的向量计算，比循环快很多。一些常用的向量库都天然支持，比如python中的numpy库。

其次的问题就是，如果用户量很大，两两之间计算代价很大。

有两个办法来缓解这个问题：
第一个办法是：将相似度拆成Map Reduce任务，将原始矩阵Map成键为用户对，值为两个用户对同一个物品的评分之积,Reduce阶段对这些乘积再求和，map reduce任务结束后再对这些值归一化；

第二个办法是：不用基于用户的协同过滤。
这种计算对象两两之间的相似度的任务，如果数据量不大，而且矩阵还是稀疏的，有很多工具可以使用：比如KGraph 、GraphCHI等；

3、推荐计算

得到用户之间的相似度之后，接下来就是计算推荐分数。显然未每一个用户计算每一个物品的推荐分数，这个代价有点大。不过，有几点我们可以来利用一下：
1.只有相似用户喜欢过的物品才需要计算，这样就减少很多物品量。
2、把计算过程拆成Map Reduce 任务。

拆Map Reduce任务的做法是：
1、遍历每个用户喜欢的用户列表；
2、获取该用户的相似用户列表；
3、把每一个喜欢的物品Map成两个记录发射出去，一个键为<相似用户ID,物品ID，1>三元组，值为<相似度>,另一个键为<相似用户ID,物品ID，0>三元组，值为<喜欢程度相似度>，其中1和0是为了区分两者，会在最后一步中用到。
4、Reduce阶段，求和后输出；
5、<相似用户ID,物品ID，0>的值除以<相似用户ID,物品ID，1>的值

因为map过程，其实就是将原来耦合的计算过程解耦了，这样的话我们可以利用多线程技术实现Map效果。

4、一些改进

对于基于用户的协同过滤有一些常用的改进办法，改进主要集中在用户对物品的喜欢程度上：
1.惩罚对热门物品的喜欢程度，这是因为热门的东西很难反应出用户的真实兴趣，更可能是被煽动，或者无聊随便点击的情形，这是群体行为的常见特点。
2.增加喜欢程度的时间衰减，一般使用一个指数函数，指数是一个负数，值和喜欢行为发生时间间隔正相关即可，比如$e^{(-x)}$,x代表喜欢时间距今的时间间隔。

应用场景：

最后说一下基于用户的协同过滤有哪些应用场景。基于用户的协同过滤有两个产出：

1、相似用户列表
2、基于用户的推荐结果

所以，我们不仅可以推荐物品，还可以推荐用户，比如我们在一些社交平台看到的，相似粉丝、和你口味类似的人等等都可以这样计算。
对于这个方法计算出来的推荐结果本身，由于是基于口味计算得出，所以在更强调个人隐私场景中应用更佳，在这样的场景下，不受大v影响，更能反应真实的兴趣群体。

总结

今天，我与你聊了基于用户的协同过滤方法，也顺便普及了一下协同过滤这个大框架的思想。基于用户的协同过滤算法非常简单，但非常有效。

在实现这个方法时，有许多需要注意的地方，比如：
1、相似度计算本身如果遇到超大维度向量怎么办？
2、两两计算用户相似度遇到用户量很大时怎么办？

同时，我也聊到了如何改进这个推荐算法，希望能够帮到你。