召回03：基于用户的协同过滤（UserCF）
本博文引自王树森老师推荐系统。
视频地址：召回03：基于用户的协同过滤（UserCF）_哔哩哔哩_bilibili
课件地址： https://github.com/wangshusen/RecommenderSystem
这节课我们继续学习推荐系统链路上的召回环节，这节课的方法叫做基于用户的协同过滤，简称UserCF。它跟前面介绍的ItemCF有很多相似之处。ItemCF是基于物品之间的相似性做推荐。这节课的UserCF是基于用户之间的相似性做推荐。
UserCF的原理
首先解释UserCF的原理。作为小红书的用户，我在小红书的点击点赞收藏转发，可以体现出我兴趣爱好。小红书上至少有几百个跟我兴趣爱好非常相似的网友。虽然我不认识这些网友，但是小红书可以从大数据中挖掘出来。小红书知道我们的兴趣爱好非常相似。今天其中某个跟我兴趣非常相似的网友看了篇笔记，他很感兴趣，对笔记点赞转发，于是小红书就知道他喜欢这篇笔记。而我还没有看过这篇笔记。那么，推荐系统就有可能给我推荐这篇笔记。推荐的理由就是跟我兴趣爱好相似的网友喜欢这篇笔记。推荐系统如何找到跟我兴趣非常相似的网友呢？一种办法是判断两个人感兴趣的笔记有多少重合。每个用户都有一个列表，上面存储了点击点赞收藏转发的笔记ID，对比两个用户的列表，就知道有多大的重合。重合越多，说明两个人的兴趣越相似。另一种类似的办法不是看笔记的重合，而是看作者的重合。每个用户都会关注一些作者对比两个用户关注的作者列表，就知道有多少关注的作者是重合的。关注的作者重合越多，说明两个人的兴趣越相似。
UserCF的实现
下面讲解UserCF具体怎么做？在用UserCF做推荐之前，需要先离线算好每两个用户之间的相似度。计算相似度的方法，稍后再讲。在这个例子中，我们想要给左边的用户做推荐。右边是最相似的四个用户。这些分数表示，用户之间的相似度。数值越大，表示用户越相似。右边是候选物品。左边的用户还没有看过这个候选物品，我们想要预估左边的用户对右边的候选物品的兴趣有多大。历史数据反映了用户对物品的兴趣。比如点击点赞收藏转发这四种行为，各算一分。四位用户对候选物品的兴趣分数分别是0、1、3、0，分数越大，表示用户对物品越感兴趣。0表示用户没有看过物品或者对物品不感兴趣。用这个公式来预估用户对候选物品的兴趣。
这一项是左边用户与第$j$个用户之间的相似度，也就是图中左边的分数0.9，0.7，0.7，0.4。这一项是第$j$个用户对候选物品的兴趣，也就是图中右边的分数0、1、3、0。把相似度和兴趣分数相乘，再把所有的成绩都加起来，得到总分表示用户对候选物品的兴趣。在这个例子中，从左边用户到右边的候选物品有四条路径，所以要计算四个分数，然后把它们相加。计算0.9x0+0.7x1+0.7x3+0.4x0。这里的0.9，0.7，0.7，0.4是左边用户与中间四个用户之间的相似度。0、1、3、0表示，四个用户对右边候选物品的兴趣。四个分数相加等于2.8，表示左边用户对候选物品的兴趣。举个例子，有2000个候选物品，我们逐一计算用户对候选物品的兴趣分数，然后返回其中分数最高的100个物品。
用户的相似度
下面我要讲如何计算两个用户之间的相似度，这里的相似度指的是用户有共同的兴趣点。我先举例说明什么样的用户相似或者不相似。
这个例子中的两个用户不相似，他们喜欢的物品没有重合。
这个例子中的两个用户被判定为相似。这是因为两个用户喜欢的物品重合度非常高，他们的兴趣点相似。
两个用户的相似度是这样计算的。
- 把用户$u_1$喜欢的物品记作集合$J_1$，
- 把用户$u_2$喜欢的物品记作集合$J_2$。
- 把集合$J_1J_2$的交集记作集合大$I$。集合$I$包含两个用户共同喜欢的物品。用这个公式计算用户$u_1$$u_2$的相似度。公式中的分子是集合大$I$的大小，即两个用户共同喜欢的物品的个数，分母是集合$J_1J_2$大小的乘积取根号。这样计算出的相似度是介于0到1之间的数，数值越接近表示两个用户越相似。
刚才的公式有个不足之处。公式同等对待热门和冷门的物品，这是不对的。拿书籍推荐举个例子，哈利波特是非常热门的物品，不论是大学教授还是中学生，都喜欢看哈利波特。既然所有人都喜欢看哈利波特，那么哈利波特对于计算用户相似度是没有价值的。越热门的物品越无法反映出用户独特的兴趣，对计算相似度就没有用。反过来，重合的物品越冷门，越能反映出用户的兴趣。如果两个用户都喜欢deep learning,这本书说明两个人很可能是同行。如果两个用户都喜欢更冷门一些的书，比如深度学习在语音识别中的应用，说明两个人是小同行。为了更好的计算用户兴趣的相似度，我们需要降低热门物品的权重。
前面计算用户相似度的公式可以等价改写成这种形式。
这里的分子还是集合$I$的大小，只不过换了种写法，写成了对$1$的连加，连加符号中的字母$l$是物品的序号。连加中的$1$是物品的权重。所有物品的权重都相同，不论是冷门还是热门，物品权重都是1。刚才我们讨论了物品的重要性，应该跟热门程度相关，越热门的物品权重应该越低。
我们把分子中的1换成 $\frac1{log1+n_l}$,就是标为红色的那一项。公式中的其他部分没有变。$\frac1{log1+n_l}$表示，第$l$个物品的权重。$n_l$是喜欢物品的用户数量，反映物品的热门程度。喜欢哈利波特的人数很多$n_l$就会很大。物品越热门$n_l$越大，$\frac1{log1+n_l}$就越小。也就是说，物品的权重越小。这样一来，哈利波特对相似度的贡献就会很小，而冷门物品的贡献会比较大。
小结
小结一下，前面讲的内容。UserCF的基本思想是根据用户的相似度做推荐。如果用户1跟用户2相似，而且用户2喜欢某物品，那么用户1也很可能喜欢这个物品。用UserCF做召回的时候，需要预估用户user对物品item的兴趣分数，选出分数最高的物品做推荐。预估兴趣分数，要用这个公式。我们找到跟用户user最相似的若干个用户，记做$user_j$。用sim表示两个用户之间的相似度，相似度是事先在线下算好的。我们还知道用户$user_j$对物品item的兴趣，记做like。把sim和like两个数值相乘，然后关于用户取连加作为用户user对候选物品item的兴趣分数的预估。这个公式需要知道每两个用户之间的相似度。我们事先计算用户两两之间的相似度，并保存起来。我们这样计算两个用户之间的相似度。把每个用户表示为一个稀疏向量，向量每个元素对应一个物品。如果用户对该物品不感兴趣，元素就是零，如果感兴趣，元素就是一或者是一除以物品的热门程度。相似度sim函数就是两个向量夹角的余弦。
UserCF召回的完整流程
我已经讲完了UserCF的数学原理，最后过一遍UserCF用于召回的完整流程。为了能在线上做到实时的推荐系统，必须要事先做离线计算，建立两个索引。一个索引是用户到物品，索引记录每个用户最近点击过和交互过的物品ID，以及记录用户对物品的兴趣分数。前面课程讲ItemCF的时候用到了相同的索引，所以这里我就不细讲了。另一个索引是用户到用户的索引，这跟ItemCF不同。ItemCF用的是物品到物品的索引,这里用的是用户到用户的索引。建索引的方法跟ItemCF几乎相同。对于每个用户索引它最相似的k个用户，比如k=10或100，这个计算量会比较大。有了这个用户到用户的索引之后，给定任意用户ID可以快速找到它最相似的k个用户，而且知道用户相似度的分数。
这个是用户到物品的索引，跟ItemCF用的索引完全相同，这里我就不多解释了，给定用户ID可以取回他最感兴趣的物品的列表以及兴趣分数。另一个索是用户到用户的索引，索引的key值是用户的ID。索引记录每个用户最相似的k个用户的ID和相似度分数。这些是第一个用户最相似的k个用户的列表，其中分数0.7、0.6、0.6、0.3、0.3表示相似度。从高到低排列。这些是第二个用户最相似的k个用户的列表，也记录了用户的D和相似度。给定任意一个用户的ID，用这个索引可以快速找到它最相似的k个用户。
线上召回
有了索引之后，我们可以在线上给用户做实时推荐。比如现在有个用户刷小红书，系统要开始做推荐。系统知道这个用户的ID。首先，用用户到用户的索引快速找到与这位用户最相似的k个用户。对于这k个用户，利用用户到物品的索引，找到每个人近期感兴趣的物品的列表，也就是用户的last_n物品。有了k个相似用户，每个用户有n个物品，那么共取回了nxk个物品。对于取回的nxk个物品，用公式预估用户对物品的兴趣分数。按照分数从高到低对物品做排序。返回分数最高的100个物品，作为召回的结果，这100个物品就是UserCF这个召回通道的输出。
最后我演示一下UserCF做召回的流程。用户刷小红书之后，系统要给这位用户做推荐。知道用户的ID利用用户到用户的索引找到最相似的k个用户，取回列表中记录的top k的用户的ID和相似度。接下来，我们要利用用户到物品的索引，找到每个用户近期感兴趣的物品。知道这个用户的ID，取回他近期感兴趣的物品，我们把这些物品叫做last-n。这些就是用户最近感兴趣的物品的ID和兴趣分数，在这个例子中n=2。用同样的方法根据用户到物品的索引，找到每个用户近期感兴趣的物品。一共用了k个相似用户，每个用户最多有n个感兴趣的物品，因此会取回nxk个物品。用这节课前面介绍过的公式计算，用户对这nxk个物品的兴趣分数。根据算出的兴趣分数，做排序返回排在前100的物品，也就是说从这nxk物品中选出100个作为UserCF的召回结果。做计算的时候需要用到这些列表中的数值。用到上面列表中，用户之间的相似度。用到下面列表中，用户对物品的兴趣分数。把上面的相似度跟下面的兴趣分数相乘，得到预估的兴趣分数。如果取回的物品有重复的，就做去重把分数加起来。用这种方法做召回，在线上做计算的速度非常快。
总结
最后总结一下这节课的内容。UserCF的原理是这样的。如果用户$u_1$跟用户$u_2$两个人的兴趣相似，而且$u_2$喜欢某物品，那么$u_1$也可能喜欢该物品。用户的相似度是根据交互过的物品来定的。如果用户$u_1$和$u_2$喜欢的物品有很大的重叠，那么用户$u_1$和$u_2$很显然有相似的兴趣爱好。具体是用这个公式计算用户$u_1$和$u_2$的相似度。分子是两位用户共同喜欢的物品的数量，也就是集合$j_1$和$j_2$的交集，分母是做归一化让相似度分数介于0到1之间。
在工业界的推荐系统中，ItemCF和UserCF都是主要的召回通道。为了在线上做非常快速的召回，需要离线维护两个索引。一个索引是从用户到物品列表。记录了每个用户近期交互过的n个物品；另一个索引是从用户到用户列表，记录了每个用户相似度最高的k个用户。在线上做召回的时候要用到这两个索引，每次取回nxk个物品。取回之后还要做个筛选，只保留分数最高的那一小部分物品。UserCF用这个公式预估用户对每个物品的兴趣分数。这个公式用到了用户与用户的相似度和用户对物品的兴趣分数。两种分数分别记录在两个索引上。用公式给物品打分，返回分数最高的100个物品，作为UserCF最终的召回结果。UserCF的内容就讲到这里，感谢大家观看。