召回01：基于物品的协同过滤（ItemCF）
本博文引自王树森老师推荐系统。
视频地址：召回01：基于物品的协同过滤（ItemCF）_哔哩哔哩_bilibili
课件地址： https://github.com/wangshusen/RecommenderSystem
从这节课开始，我们学习推荐系统链路上的召回环节。
ItemCF
ItemCF的原理
这节课内容是基于物品的协同过滤。缩写是ItemCF。item，意思是物品；CF是collaborative filtering的缩写，意思是协同过滤。
首先用个通俗的例子解释ItemCF的原理。比方说我喜欢看笑傲江湖，笑傲江湖与鹿鼎记相似，而且我没有看过鹿鼎记。那么系统会给我推荐鹿鼎记，推荐的理由是两个物品很相似。
系统通过历史记录可以知道我喜欢看笑傲江湖，而且我没有看过鹿鼎记。但是推荐系统如何知道笑傲江湖与鹿鼎记相似呢？有很多种办法可以做到，比如用知识图谱。两本书的作者相同，所以两本书相似。还可以基于全体用户的行为判断两个物品的相似性，比如看过笑傲江湖的用户，也看过鹿鼎记。给笑傲江湖写好评的用户，也给鹿鼎记写好评。我们可以从用户的行为中挖掘出物品之间的相似性，再利用物品之间的相似性做推荐。
ItemCF的实现
下面讲解ItemCF具体怎么做。
每个用户都交互过若干物品，比如点击，点赞，收藏，转发过的物品。可以量化用户对物品的兴趣，比如点击，点赞，收藏，转发这四种行为，各算一分。在这个例子中，用户对四个物品的兴趣分数分别是2，1，4，3。这时，用户没有交互过的候选物品，我们要决定是否把这个物品推荐给用户。假设我们知道物品两两之间的相似度。比如它们的相似度分别是0.1，0.4，0.2，0.6。后面会详细讲解相似度是如何计算出来的。用下面的公式来预估用户对候选物品的兴趣。
like(user,item_j)是用户对第$j$个物品的兴趣，也就是图中左边的四个分数2，1，4，3。sim(item_j,item)是第$j$个物品与候选物品之间的相似度，也就是图中右边的四个分数，0.1，0.4，0.2，0.6。把两项相乘，再把所有的乘积相加得到总分。总分表示用户对候选物品的兴趣。
在这个例子中，从用户到候选物品有四条路径，所以要计算四个分数，然后把它们相加。计算2x0.1+1x0.4+4x0.2+3x0.6，这里的2，1，4，3是用户对四个物品的兴趣分数。0.1，0.4，0.2，0.6是物品之间的相似度。四个分数相加等于3.2，表示用户对候选物品的兴趣。举个例子，有2000个候选物品，我们逐一计算用户对候选物品的兴趣分数，然后返回其中分数最高的100个候选物品。
物品的相似度
我们来看看具体如何计算两个物品之间的相似度。
计算物品相似度的基本想法是这样的：两个物品的受众重合度越高，两个物品就越相似。我们可以从数据中挖掘出物品的相似度。举个例子，喜欢射雕英雄传和神雕侠侣的读者重合度很高，因此可以认为射雕英雄传和神雕侠侣相似。
我举个例子来说明什么样的两个物品被判定为不相似。下面是一些用户。这些边表示，用户喜欢物品。红色和绿色这两个物品的受众没有重合，这意味着两个物品不相似。
这个例子中的两个物品被判定为相似，这是因为两个物品的受众重合度非常高。
计算物品相似度
我们来计算两个物品的相似度。把喜欢物品$i_1$的用户记作集合$W_1$。$W_1$是用户的集合。把喜欢物品$i_2$的用户记作集合$W_2$。把集合$W_1$和$W_2$的交集记作$V$。$V$包含同时喜欢物品$i_1$，$i_2$的用户。用这个公式计算物品$i_1$和$i_2$的相似度。
公式中的分子是集合$V$的大小，即对两个物品都感兴趣的用户的人数。分母是集合$W_1$和$W_2$大小的乘积再取根号。这样计算出的相似度一定是一个介于0到1之间的数，数值越大，表示两个物品越相似。
为什么相似度是介于0到1之间的呢?这是因为集合$V$比$W_1$和$W_2$都要小。
注意这个公式没有考虑用户喜欢物品的程度，用这个公式只要是喜欢就看作1，不喜欢就看作0。
如果想要用到喜欢的程度，需要改一下这个公式，比如点击，点赞，收藏，转发，各自算一分。用户对物品的喜欢程度最多可以是四分。
现在我们考虑用户喜欢物品的程度，其他都一样，只有下面的公式变了。
分子把用户小$v$对物品$i_1$，$i_2$的兴趣分数相乘，然后取连加。连加是关于用户小$v$取的，用户小$v$同时喜欢两个物品。如果兴趣分数的取值是0或者1，那么分子就是同时喜欢两个物品的人数，也就是集合v的大小。公式的分母是两个根号的乘积。第一项是用户对物品$i_1$的兴趣分数，关于所有用户求连加，然后开根号。第二项类似用户对物品$i_2$的兴趣分数，关于所有用户求连加，然后开根号。
这个公式计算出的数值介于0到1之间，表示两个物品的相似度。其实这个公式就是余弦相似度cosine similarity。把一个物品表示为一个向量，向量每个元素对应一个用户元素的值，就是用户对物品的兴趣分数。两个向量的夹角的余弦就是这个公式。
我不展开讲了，大家自己思考一下，为什么这个公式是余弦相似度?
小结
小结一下前面的内容，ItemCF的基本思想是根据物品的相似度做推荐。如果某个用户喜欢物品1，而且物品1跟物品2相似，那么该用户很可能会喜欢物品2。做推荐就需要预估用户对候选物品的兴趣有多强，
给每个物品打一个分数，把分数高的物品推荐给用户。预估兴趣分数，要用这个公式。
从用户的历史行为记录中，我们知道用户对物品$j$的兴趣。我们还知道物品$j$与候选物品的相似度。把两个数相乘，然后关于物品$j$去连加作为用户对候选物品兴趣分数的预估。可以这样理解。用户对物品$j$感兴趣，兴趣传递到候选物品，得到用户对候选物品的兴趣分数。有很多条这样的路径，把兴趣从用户传递到物品$j$，再传递到候选物品，把这些路径全都加起来。就是用户对候选物品的兴趣分数。这个公式需要知道每两个物品之间的相似度，我们事先计算物品两两之间的相似度，并且保存起来。这样计算物品两两之间的相似度。把每个物品表示为一个稀疏向量，向量每一个元素对应一个用户。相似度sim函数就是两个向量夹角的余弦，其实就是机器学习里面常用的cosine相似度。
ItemCF召回的完整流程
我已经讲完了ItemCF的原理，下面我要讲解ItemCF用于召回的完整流程。
为了能在线上做到实时的推荐系统，必须要事先做离线计算，建立两个索引。一个索引是用户到物品，索引记录每个用户最近点击过，交互过的物品的ID，比如最近交互过的200个物品。有了这个索引之后，给定任意用户ID可以快速返回。他近期感兴趣的物品列表。另一个索引是从物品到物品。我们首先要计算物品之间两两相似度，这个计算量会比较大。对于每个物品索引，它最相似的k个物品，比如k=10或者100。有了这个索引之后，给定任意物品ID可以快速查出它最相似的k个物品的ID，而且知道相似度分数。
这里演示一下第一个索引，也就是用户到物品的索引。这些是用户ID，比如小红书有几亿个用户，每个用户有一个ID。我们记录每个用户最近点击交互过的物品ID，每个物品还有一个兴趣分数，比方说点击，点赞，收藏，转发各算一分。相加就是用户对物品的兴趣分数。这是第一个用户的物品列表，里面记录了物品ID和分数，分数有高有低。这是第二个用户的物品列表，也是记录物品的ID和分数，每个用户都有一个列表。
另一个索引是从物品到物品。这些是物品的ID，比如小红书有几亿篇笔记，每篇笔记就是一个物品。索引记录每个物品最相似的k个物品的ID和相似度。这些是第一个物品最相似的k个物品的列表，其中的分数0.7，0.6，0.6，0.3，0.3，表示相似度。从高到低排列。这些是第二个物品最相似的k个物品的列表，也记录了物品ID和相似度分数。给定任意一个物品ID，用这个索引可以快速找到它最相似的k个物品。
有了索引之后，我们可以在线上给用户做实时推荐。比如现在有个用户刷小红书，系统要开始做推荐。系统知道这个用户的ID。首先，查看用户到物品的索引，可以快速找到这位用户近期感兴趣的物品的列表。我们把用户最近交互过的物品叫做last-n。对于last-n集合中的每个物品，我们利用物品到物品的索引，找到top k相似物品。用户最近有n个感兴趣的物品，我们又找到了每个物品的top k相似物品，那么一共取回nk个物品。对于取回的nk个相似物品，用公式预估用户对物品的兴趣分数。按照分数从高到低对物品做排序，返回分数最高的100个物品。这100个物品就是ItemCF这个召回通道的输出，会跟其他召回通道的输出融合起来，然后做排序，最终展示给用户。
为什么要用索引呢?数据库中有上亿个物品，如果挨个用公式计算，用户对所有物品的兴趣分数，计算量会爆。
索引的意义在于避免枚举，所有的物品。假如我们记录用户最近感兴趣的n=200个物品。取回每个物品最相似的k-10个物品。那么，一共也就取回nxk=2000个物品。用公式给这2000个物品打分，也就是说，分别预估用户对这2000个物品的兴趣分数。返回分数最高的100个物品，作为ItemCF这个召回通道的结果。这样的计算量是很小的，可以做到在线实时计算。
总结一下，用索引的话，离线计算量大，需要更新两个索引。好处是每次线上做召回都很快，只需要给2000个物品打分，不需要访问上亿个物品。
最后我演示一下ItemCF做召回的流程。用户登录之后，系统要给这位用户做推荐。知道用户的ID利用用户到物品的索引，找到用户近期感兴趣的物品。这个列表记录了物品的ID和进取分数。接下来，我们要利用物品到物品的索引，找到每个物品的top k相似物品。知道这个物品的ID，我们要取回它最相似的k个物品。这些就是top k相似物品的ID和相似度。这个例子中$k=2$。用同样的方法根据物品到物品的索引，找到每个物品的top k相似物品。top k相似会召回很多物品。可以用这节课前面介绍过的公式计算用户对召回物品的兴趣分数，根据算出的分数做排序。返回排在前100的物品。做计算的时候需要用到这些列表里的数值。用到上面列表中，用户对物品的兴趣分数。用到下面列表中，物品和物品的相似度分数。把兴趣分数跟相似度分数相乘。如果取回的物品ID有重复的，就去重，把分数加起来。
总结
最后总结一下这节课的内容。
ItemCF的原理是这样的：如果某位用户喜欢物品$i_1$，那么他可能喜欢跟物品$i_1$相似的物品记作$i_2$。物品的相似度是根据交互过的用户来定的。如果喜欢物品$i_1$和$i_2$的用户有很大的重叠，那么就判定物品$i_1$与$i_2$相似。注意，这里不是根据物品的内容判定物品相似，而是根据用户的行为来判定物品相似。
具体是用这个公式计算物品$i_1$与$i_2$的相似度。
分子是同时喜欢两个物品的用户的数量，分母是做归一化，前面讲过这个公式，这里就不再具体解释了。
在工业界的推荐系统中，ItemCF是最重要的召回通道之一。为了能在线上非常快速的做召回，需要离线维护两个索引。一个索引是从用户到物品列表，记录了每个用户最近交互过的n个物品。另一个索引是从物品到物品列表，记录每个物品相似度最高的k个物品。在线做召回的时候要用到这两个索引，每次取回nk个物品，这个数量比较大，可能有几千个物品，不可能全都返回。还需要做个筛选。ItemCF用这个公式预估用户对每个物品的兴趣分数：
这个公式用到用户对物品的兴趣分数和物品与物品的相似度。
两种分数分别记录在两个索引上。在给物品打分之后，返回分数最高的100个物品，作为召回结果。
这节课内容讲完了，后面几节课会讲解其他几种召回通道。