推荐系统三十六式--学习笔记（8-10 近邻推荐）

参考原作：推荐系统三十六式-刑无刀

8.【近邻推荐】人以群分，你是什么人就看到什么世界

协同过滤，普通且重要。

协同过滤

推荐系统度过了只能使用基于内容的推荐阶段后,就有了大量的用户行为数据。这个用户物品的关系矩阵中填充的就是用户对物品的态度，但并不是每个位置都有，需要的就是把那些还没有的地方填起来。这个关系矩阵是协同过滤的命根子，一切都围绕它来进行。

协同过滤是一个比较大的算法范畴。通常划分为两类：

1. 基于记忆的协同过滤（Memory-Based）:
   就是记住每个人消费过什么东西，然后给他推荐相似的东西，或者推荐相似的人消费的东西
2. 基于模型的协同过滤（Model-Based）:
   是从用户物品关系矩阵中去学习一个模型，从而把那些矩阵空白处填满

基于记忆的协同过滤的一种——基于用户，或者叫做 User-Based， User to User。

基于用户的协同过滤

思想:
先根据历史消费行为帮你找到一群和你口味很相似的用户；然后根据这些和你很相似的用户再消费了什么新的、你没有见过的物品，都可以推荐给你。

原理:
第一步，准备用户向量，从这个矩阵中，理论上可以给每一个用户得到一个向量。

向量有三个特点：

1. 向量的维度就是物品的个数；
2. 向量是稀疏的，也就是说并不是每个维度上都有数值；
3. 向量维度上的取值可以是简单的 0 或者 1，也就是布尔值。

第二步，用每一个用户的向量，两两计算用户之间的相似度，设定一个相似度阈值或者设定一个最大数量，为每个用户保留与其最相似的用户。
第三步，为每一个用户产生推荐结果。

$$P_{u,i}=\frac{\sum_j^n(sim_{u,j}*R_{j,i})}{\sum_j^nsim_{u,j}}$$

等号左边就是计算一个物品 i 和一个用户 u 的匹配分数，等号右边是这个分数的计算过程，分母是把和用户 u 相似的 n 个用户的相似度加起来，分子是把这 n 个用户各自对物品 i 的态度，按照相似度加权求和。

问题：

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

1.构造矩阵
我们在做协同过滤计算时，所用的矩阵是稀疏的。

这里介绍典型的稀疏矩阵存储格式( Spark 中，Python 的 NumPy 包中)。

1. CSR：这个存储稍微复杂点，是一个整体编码方式。它有三个组成：数值、列号和行偏移共同编码。
2. COO：这个存储方式很简单，每个元素用一个三元组表示（行号，列号，数值），只存储有值的元素，缺失值不存储。

2 相似度计算
首先是单个相似度计算问题，如果碰上向量很长，无论什么相似度计算方法，都要遍历向量，如果用循环实现就更可观了。

所以通常降低相似度计算复杂度的办法有两种。

1. 对向量采样计算。道理很简单，两个一百维的向量计算出的相似度是 0.7，我现在忍受一些精度的损失，随机从中取出 10 维计算，得到相似度是 0.72，和它误差也不大。这个算法由 Twitter 提出，叫做 DIMSUM 算法，已经在 Spark 中实现了。
2. 向量化计算。在机器学习领域，难道向量计算都要用循环实现吗？并不是，现代的线性代数库都支持直接的向量运算，比循环快很多。一般像常用的向量库都天然支持的，比如 Python 的 NumPy 。

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

第一个办法是：将相似度计算拆成 Map Reduce 任务，将原始矩阵 Map 成键为用户对，值为两个用户对同一个物品的评分之积，Reduce 阶段对这些乘积再求和，Map Reduce 任务结束后再对这些值归一化；
第二个办法是：不用基于用户的协同过滤。

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

3 推荐计算
计算量大，可利用公式特点：

• 只有相似用户喜欢过的物品需要计算，这个大大的赞，这个数量相比全部物品少了很多；
• 把计算过程拆成 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 Reduce 任务也不一定非要用 Hadoop 或者 Spark 实现。也可以用单机实现这个过程。例如 C++ 里面 OpenMP 库。

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

1. 惩罚对热门物品的喜欢程度，这是因为，热门的东西很难反应出用户的真实兴趣，更可能是被煽动，或者无聊随便点击的情形，这是群体行为常见特点；
2. 增加喜欢程度的时间衰减，一般使用一个指数函数，指数就是一个负数，值和喜欢行为发生时间间隔正相关即可，这很好理解，小时候喜欢的东西不代表我现在的口味，人都是会变的，这是人性。

基于用户的协同过滤有两个产出：

1. 相似用户列表；
2. 基于用户的推荐结果。

---

9.【近邻推荐】解密“看了又看”和“买了又买”

电商网站中‘看了还看’，‘买了还买’这样的推荐形式背后都是来自一个古老的推荐算法，叫做基于物品的协同过滤，通常也被叫作 Item-Based，因为后者更容易搜索到相关的文章，所以被更多地提及。

基于物品（Item-Based）

基于物品的协同过滤算法诞生于 1998 年，是由亚马逊首先提出的，并在 2001 年由其发明者发表了相应的论文（ Item-Based Collaborative Filtering Recommendation Algorithms ）。亚马逊早在 1998 年，也就是论文发表的三年前就申请了专利。

原理

首先对于前述的基于用户的推荐有几个问题：

1. 用户数量往往比较大，计算起来非常吃力，成为瓶颈；
2. 用户的口味其实变化还是很快的，不是静态的，所以兴趣迁移问题很难反应出来；
3. 数据稀疏，用户和用户之间有共同的消费行为实际上是比较少的，而且一般都是一些热门物品，对发现用户兴趣帮助也不大。

但是基于物品的协同过滤首先计算相似物品，然后再根据用户消费过、或者正在消费的物品为其推荐相似的

算法的基本步骤：

1. 构建用户物品的关系矩阵，矩阵元素可以是用户的消费行为，也可以是消费后的评价，还可以是对消费行为的某种量化如时间、次数、费用等；
2. 假如矩阵的行表示物品，列表示用户的话，那么就两两计算行向量之间的相似度，得到物品相似度矩阵，行和列都是物品；
3. 产生推荐结果，根据推荐场景不同，有两种产生结果的形式。一种是为某一个物品推荐相关物品，另一种是在个人首页产生类似“猜你喜欢”的推荐结果。不要急，稍后我会分别说。

其优势在于以下几点：

• 首先，物品的数量，或者严格的说，可以推荐的物品数量往往少于用户数量；所以一般计算物品之间的相似度就不会成为瓶颈。
• 其次，物品之间的相似度比较静态，它们变化的速度没有用户的口味变化快；所以完全解耦了用户兴趣迁移这个问题。
• 最后，物品对应的消费者数量较大，对于计算物品之间的相似度稀疏度是好过计算用户之间相似度的。

 

计算物品相似度

从用户物品关系矩阵中得到的物品向量：

1. 它是一个稀疏向量；
2. 向量的维度是用户，一个用户代表向量的一维，这个向量的总共维度是总用户数量；
3. 向量各个维度的取值是用户对这个物品的消费结果，可以是行为本身的布尔值，也可以是消费行为量化如时间长短、次数多少、费用大小等，还可以是消费的评价分数；
4. 没有消费过的就不再表示出来，所以说是一个稀疏向量。

计算两个物品的相似度，这里以余弦相似度为例：

$$sim(i,j)=\frac{\sum_{k=1}^nR_{ik}*R_{jk}}{\sqrt{\sum_{k=1}^nR_{ik}^2}\sqrt{\sum_{k=1}^nR_{jk}^2}}$$

他们都是稀疏向量，也就是向量中绝大多数值都是 0，求和时不用算，点积时更不用算，甚至求点积时只用管两个物品的公共用户，只是少许几个乘积而已。

物品之间的相似度计算是这个算法 可以改进的地方。通常的改进方向有下面两种。

• 物品中心化。
  把矩阵中的分数，减去的是物品分数的均值；先计算每一个物品收到评分的均值，然后再把物品向量中的分数减去对应物品的均值。以此来去掉物品中铁杆粉丝群体的非理性因素。
• 用户中心化。
  把矩阵中的分数，减去对应用户分数的均值；先计算每一个用户的评分均值，然后把他打过的所有分数都减去这个均值。

隐式反馈取值特殊，有一些基于物品的改进推荐算法无法应用，比如著名的 Slope One 算法。

计算推荐结果

第一种属于 TopK 推荐，形式上也常常属于类似“猜你喜欢”这样的。
出发方式是当用户访问首页时，汇总和“用户已经消费过的物品相似”的物品，按照汇总后分数从高到低推出。汇总的公式是这样的：

$$\hat R_{ui} = \frac{\sum_{j=1}^msim(i,j)*R_{uj}}{\sum_{j=1}^msim(i,j)}$$

核心思想就和基于用户的推荐算法一样，用相似度加权汇总。这个过程都是离线完成后，去掉那些用户已经消费过的，保留分数 高的 k 个结果存储。

第二种属于相关推荐，也就是专栏题目所指的场景。
这类推荐不需要提前合并计算，当用户访问一个物品的详情页面时，或者完成一个物品消费的结果面，直接获取这个物品的相似物品推荐，就是“看了又看”或者“买了又买”的推荐结果了。

Slope One 算法经典的基于物品推荐，相似度矩阵计算无法实时更新，整个过程都是离线计算的，而且还有另一个问题，相似度计算时没有考虑相似度的置信问题。例如，两个物品，他们都被同一个用户喜欢写留言了，且只被这一个用户喜欢了，那么余弦相似度计算的结果是 1，这个 1 在 后汇总计算推荐分数时，对结果的影响却 大。

Slope One 算法针对这些问题有很好的改进。在 2005 年首次问世，Slope One 算法专门针对评分矩阵，不适用于行为矩阵。Slope One 算法计算的不是物品之间的相似度，而是计算的物品之间的距离，相似度的反面。
例如：

用户	物品A	物品B	物品C
用户1	5	3	2
用户2	3	4	null
用户3	null	2	5

物品间的差距：

用户	物品A	物品B	物品C
物品A	0	-0.5(2)	-3(1)
物品B	0.5(2)	0	-1(1)
物品C	3(1)	1(1)	0

注:括号里表示两个物品的共同用户数量，代表置信度。括号前的数字代表共同用户评分的平均差距。

如此时计算用户3对物品A的评分，我们通过评分表可以推出，
基于物品AB，用户3应给物品A评分2+0.5=2.5
基于物品AC，用户3应给物品C评分5+3=8
综合置信度，于是汇总的评分为：$\frac{81+2.52}{1+2}=4.33$。

---

10.【近邻推荐】协同过滤中的相似度计算方法有哪些

相似度的本质

推荐系统中，推荐算法分为两个门派，一个是机器学习派，另一个就是相似度门派。机器学习派是后起之秀，而相似度派则是泰山北斗，以致撑起来推荐系统的半壁江山。近邻推荐的核心就是相似度计算方法的选择，由于近邻推荐并没有采用最优化思路，所以效果通常取决于矩阵的量化方式和相似度的选择。

近邻推荐的核心就是相似度计算方法的选择，由于近邻推荐并没有采用最优化思路，所以效果通常取决于矩阵的量化方式和相似度的选择。

其实属于另一门派的推荐算法——机器学习中，也有很多算法在某种角度看做是相似度度量。逻辑回归或者线性回归中，一边是特征向量，另一边是模型参数向量，两者的点积运算，就可以看做是相似度计算。

近邻推荐中，最常用的相似度是余弦相似度。然而还有欧氏距离、皮尔逊相关度、自适应的余弦相似度、局部敏感哈希等。

相似度的计算方法

数据分类

相似度计算对象是向量，或者叫做高维空间下的坐标，一个意思。那表示这个向量的数值就有两种：

1. 实数值；
2. 布尔值。

1 欧氏距离

欧式空间下度量距离的方法。不适合布尔向量之间。公式：

$$E(p,q)=\sqrt{\sum_{i=1}^n(p_i-q_i)^2}$$

通常相似度计算度量结果希望是
[-1，1] 或者 [0，1] 之间，所以欧式距离要么无法直接使用到这个场景中，要么需要经过二次转化得到:

$$sim(p,q)=\frac{1}{1+E(p,q)}$$

2 余弦相似度

度量的是两个向量之间的夹角，其实就是用夹角的余弦值来度量，所以名字叫余弦相似度。余弦相似度在度量文本相似度、用户相似度、物品相似度的时候都较为常用；

但是在这里需要提醒你一点，余弦相似度的特点：它与向量的长度无关。因为余弦相似度计算需要对向量长度做归一化：

$$cos(p,q)=\frac{\sum_ip_iq_i}{\sqrt{\sum_iq_i^2}\sqrt{\sum_ip_i^2}}$$

经过向量长度归一化后的相似度量方式，背后潜藏着这样一种思想：两个向量，只要方向一致，无论程度强弱，都可以视为“相似”。在协同过滤中，如果选择余弦相似度，某种程度上更加依赖两个物品的共同评价用户数，而不是用户给予的评分多少。这就是由于余弦相似度被向量长度归一化后的结果。

对余弦相似度有个改进，改进的算法叫做调整的余弦相似度（Adjusted Cosine Similarity）。调整的方法很简单，就是先计算向量每个维度上的均值，然后每个向量在各个维度上都减去均值后，再计算余弦相似度。

举个小例子，用户 A 对两部电影评分分别是 1 分和 2 分，用户 B 对同样这两部电影评分是 4 分和 5 分。用余弦相似度计算出来，两个用户的相似度达到 0.98。这和实际直觉不符，用户 A 明显不喜欢这两部电影。用调整的余弦相似度计算得到的相似度是 -0.1，呈现出两个用户口味相反。

3 皮尔逊相关度

实际上也是一种余弦相似度，不过先对向量做了中心化，向量 p 和 q 各自减去向量的均值后，再计算余弦相似度。

$$R(p,q)=\frac{\sum_{i=1}^n(p_i-\bar p)(q_i-\bar q)}{\sqrt{\sum_{i=1}^n(p_i-\bar p)^2}\sqrt{\sum_{i=1}^2(q_i-\bar q)}}$$

皮尔逊相关度计算结果范围在 -1 到 1。-1 表示负相关，1 比表示正相关。皮尔逊相关度其实度量的是两个随机变量是不是在同增同减。由于皮尔逊相关度度量的时两个变量的变化趋势是否一致，所以不适合用作计算布尔值向量之间相关度。

4 杰卡德（Jaccard）相似度

是两个集合的交集元素个数在并集中所占的比例。由于集合非常适用于布尔向量表示，所以杰卡德相似度简直就是为布尔值向量私人定做的。

计算方式是：

1. 分子是两个布尔向量做点积计算，得到的就是交集元素个数；
2. 分母是两个布尔向量做或运算，再求元素和。

余弦相似度适用于评分数据，杰卡德相似度适合用于隐式反馈数据。杰卡德相似度就只适合布尔值向量，余弦相似度弹性略大，适合两种向量。欧式距离度量的是绝对差异，余弦相似度度量的是方向差异，但是调整的余弦相似度则可以避免这个弱点。

一位网友的案例：
做社交网络好友相似的度量，粗略来说可以用这几个特征：
帖子发布数量，月均发帖数量，平均帖子字数，头像，一些标签数据，例如是否大V，是否营销号，是否网红，职业等标签数据。

另外还可以统计发文Top关键词向量及词频。标签数据可计算杰卡的相似度，Top关键词可计算余弦相似度，发布量，字数等可计算欧氏距离，然后再融合这几种相似度得到总和相似度。