近邻推荐之基于用户的协同过滤

推荐阅读时间：5min~8min 文章内容：基于用户的协同过滤

提到推荐系统，很多人第一反应就是协同过滤，由此可见协同过滤与推荐系统的关系是有多么紧密。这里介绍下基于用户的协同过滤。

原理简介

你是什么样的人 看到的就是什么样的世界

不知道你有没有遇到这样的情况，你发现你喜欢看的很多电影同样也有人喜欢，之后你俩会经常交流最近有没有什么好看的电影。

上面的这种情况其实就非常类似于基于用户的协同过滤，简单来说，先根据你的历史行为来计算出与你相似的其他用户，然后将这些相似用户消费过但你没消费的物品推荐给你。很明显，基于用户的协同过滤的关键就是如何找到相似用户。

实现流程

生成用户向量

想要计算用户之间的相似度，需要先给每个用户生成一个向量。既然是向量，那就有维度和数值。

先来说下维度，每个用户对应的向量的维度与物品数量一致。

再来说下每个维度的取值，取值可以是1和0，表示的含义可以在不同的场景有不同的含义，比如 1 可以表示买过，0 表示未买过，1 也可以表示收藏过，0 表示未收藏。除了 1 和 0 之外，取值也可以为评分，比如 1 - 5。

举个简单示例，有 A、B、C 三个物品，我买过物品 A 和 C，那么我这个用户的向量可以表示为 [1, 0, 1]。

在实际应用中，需要注意的两点，第一个是每个用户的矩阵都是很稀疏的，因为物品数会很多，每个用户的用户行为一般只会覆盖少量物品，所以会出现很多取值为 0 的地方；第二个是说不是所有的用户都可以表示成一个向量的，因为不是所有的用户都有交互行为。

计算用户之间的相似度

上一步生成了用户向量，接下来就可以根据用户向量来计算任何两个用户之间的相似度，这里使用余弦公式来计算。

解释下，x，y 表示两个用户的向量，x_i，y_i 表示用户向量中的每个元素。分母是计算两个用户向量的长度，求元素值的平方和再开方。分子是两个向量的点积，相同位置的元素值相乘再求和。

在计算完用户之间的相似度之后，我们要做的是根据相似度的结果选取相似用户，选取方法可以通过设定相似度结果阈值，也可以通过选择前 k 个用户（k 可以人为指定）。

生成推荐结果

完成了相似用户的定义之后，下来要做的就是为每个用户推荐物品。想要生成推荐物品，需要预测用户与物品之间的匹配评分，公式如下：

简单解释下上面的公式：

等号左边表示预测的用户 u 和 物品 i 的匹配评分。等号右边表示匹配评分的计算过程。

sim(u,j) 表示用户 u 和 用户 j（相似用户之一） 的相似度，r(j,i) 表示相似用户 j 对 物品 i 的评分。分母是对用户 u 的 n 个相似用户的相似度进行求和，分子是把这 n 个相似用户对各自已消费的物品 i 的评分，按照相似度加权求和。

注意：这里说的评分是指广义上的评分，可以指普通的 1-5 ，也可以是 1 或 0，表示买过或未买过。

改进

对于基于用户的协同过滤有一些常见的改进办法，改进主要集中在用户对物品的喜欢程度上：

• 惩罚对热门物品的喜欢程度，因为热门的东西很难反应出用户的真实兴趣。
• 增加喜欢程度的时间衰减，一般使用一个指数函数，指数就是一个负数，表示距离当前时间越远，喜欢程度会逐渐下降。

工程化中的问题

将基于用户的协同过滤进行工程化时，会碰到一些问题，这里列举一些常见的问题。

稀疏向量

实际生产环境中，生成的用户向量都是非常稀疏的，构成的矩阵也是非常稀疏的，直白来说就是很多值都是0，有一些存储稀疏矩阵的格式。比如 CSR 或者 COO。

1. CSR：CSR是一个整体编码方式，由三部分构成，数值、列号和行偏移。
2. COO：COO每个元素用一个三元组表示（行号，列号，数值），只存储有值的元素，缺失值不存储。

这些存储格式，在常见的框架中都已经实现，比如 Python 中的 scipy 模块。

相似度计算

计算相似度时如果物品总量比较多，那么每个用户向量长度会很大，计算时花费的时间会比较长。可以通过以下两种方法来解决：

1. 对向量进行采用，Twitter 提出的 DIMSUM 算法，举个例子来说，两个一百维的向量计算出的相似度是 0.7，我现在忍受一些精度的损失，不用 100 维计算，随机从中取出 10 维计算，得到相似度是 0.72，显然用 100 维计算出的 0.7 更可信一些，但是在计算复杂度降低十倍的情形下，0.72 和它误差也不大，后者更经济。
2. 向量化计算，避免循环，将循环的步骤采用向量化来完成。

另外一个问题如果用户量比较大，那么计算所有的用户两两之间的相似度也会比较耗时。可以通过以下办法来缓解：

1. 将相似度计算拆成 Map Reduce 任务，将原始矩阵 Map 成键为用户对，值为两个用户对同一个物品的评分之积，Reduce 阶段对这些乘积再求和，Map Reduce 任务结束后再对这些值归一化。

这种计算对象两两之间的相似度的任务，如果数据量不大，一般来说不超过百万个，然后矩阵又是稀疏的，那么有很多单机版本的工具其实更快，比如 KGraph、 GraphCHI 等。

计算推荐分数

计算得到相似用户之后，下来要做的就是为每个用户计算他与相似用户消费过的物品的分数。这里需要注意的是，只计算相似用户消费过的物品，这样可以大大减少计算量。

上面的计算过程可以转化成 Map Reduce 任务：

1. 遍历每个用户
2. 获取该用户的相似用户
3. 将相似用户消费的物品 map 成两条记录，一个 key 是 <相似用户id, 物品id, 1> 三元组，value 为 <相似度>；另一个 key 是 <相似用户id, 物品id, 0> 三元组，value 为 <相似用户对该物品的喜欢程度 * 相似度>。
4. reduce 阶段对两个 key 进行求和
5. 将 reduce 生成的两个 key 的结果相除。sum(<相似用户对该物品的喜欢程度 * 相似度>) / sum( <相似度>)。

拆分 Map Reduce 任务不一定需要使用 Hadoop 和 Spark 来实现，可以实现单机版。

应用场景

基于用户的协同过滤会计算出相似用户列表和基于用户的推荐列表。

基于以上两个结果，我们推荐相似用户和相似用户喜欢的物品。比如经常看到一些“和你口味类似的人”、“和你口味类似的人也喜欢的物品”等等。

总结

首先介绍了基于用户的协同过滤的背后原理，接下来介绍一些关于具体的实现步骤，最后列出了工程落地时的一些常见问题，比如稀疏向量，相似度计算量过大等等。

相关推荐：

• 如何构建基于内容的推荐系统
• 如何从文本中构建用户画像
• 一文告诉你什么是用户画像
• 推荐系统中重要却又容易被忽视的问题有哪些
• 个性化推荐系统中的绕不开的经典问题有哪些
• 推荐系统这么火，但你真的需要吗
• 一文告诉你到底什么是推荐系统

点击这里领取BAT面试题 ==》：BAT机器学习/深度学习面试300题

作者：无邪，个人博客：脑洞大开，专注于机器学习研究。