一 、背景
最近在参加天池KDD的比赛，题目是推荐的多样性问题，涉及到召回，排序，长尾物品留存的问题，具体的比赛细节就不说了，这篇文章没有参考的论文，但是会参考《推荐系统实战》这本书。
在召回阶段，有很多模型可以用来在海量物品中进行召回，前面的文章里也说过里，召回任务的特点是快速，能快速选出用户感兴趣的大量商品，这个阶段用的特征不用很多很全面，模型通常比较简单，所以就来说说用于召回任务的协同过滤算法吧。
协同过滤算法是指基于用户行为数据设计的推荐算法，主要包括：
1.基于邻域的算法：UserCF（基于用户的协同过滤算法）、ItemCF（基于物品的协同过滤算法）
2.隐语义模型：LFM
3.基于图的随机游走算法：PersonalRank
本文主要讲解基于邻域的推荐算法UserCF、ItemCF
二 、基于用户的协同过滤算法
基于用户的协同过滤算法的核心思想是：给用户推荐和他兴趣相似的其他用户喜欢的物品，比如要给A做个性化推荐，那就给他推荐跟他兴趣相似人群的喜欢的但是A没见过的物品。
算法主要包括两个步骤：
(1) 找到和目标用户兴趣相似的用户集合
如何找到和目标用户兴趣相似的用户？什么样的用户兴趣相似？如何衡量两个用户兴趣相似的程度？
要想知道两个用户是否兴趣相似，从直觉上来看应该是这样的：用户A喜欢a,b,c 用户B喜欢a,b,d 用户C喜欢z,e,f，显然用户A跟B就是兴趣相似的，而跟C就是不相似的，因为他们没有共同的爱好。
在计算用户兴趣相似度的时候有两个方法：
(a) 利用Jaccard公式计算
(b) 余弦相似度
其中Wuv：用户u和用户v的相似度；N(u)：用户u产生过行为(喜欢)的物品的集合；|N(u)|：用户u产生过行为的物品的个数。
例如：若用户U1购买了a,b,c，用户U2购买了a,b,c,e,f,，用户U3购买了a,e，则(U1,U2)计算如下：
有了用户相似度计算方法，我们就可计算每个用户和目标用户u的相似度，然后对这些相似度进行排序，得到和用户u兴趣相似的k个用户的集合S(u,k)
单纯的用这两个原始公式直接计算用户的相似度会有一点问题，如果用户A跟用户B都看过新闻联播，那么能说这两个用户兴趣相似吗？因为新闻联播基本上每一个人都看过。但是如果用户A跟B都喜欢看百家讲坛呢，那么这两个用户的兴趣一定是相似的。所以我们在利用上面公式的时候要作出一点改变，用于惩罚那些所有人都喜欢的热门物品，公式变为：
其中N(i)表示喜欢i的用户的集合，｜N(i)｜越大说明物品i越热门，所以就会作出惩罚，限制这些热门商品。
(2) 找到这个集合中的用户喜欢的，且目标用户没有听说过的物品推荐给目标用户
经过第一步后，我们得到来S(u,k),也就是跟用户u相似的k个用户，接下来会根据S(u,k)来计算用户对物品的喜欢程度。
我们首先要找到这K个用户喜欢而用户没有接触过的物品，计算用户对该物品的感兴趣程度，根据感兴趣程度对物品进行排序，然后推荐给用户感兴趣程度较高的物品，在UserCF中衡量用户对某物品的感兴趣程度使用以下公式：
其中P(u,i)表示用户u对物品i的喜欢程度；N(i)表示喜欢物品i的用户集合；表示用户v对物品i是否产生过行为（对于评分系统，可以表示v对i的评分）。
不用惩罚的例子：假设用户U1购买了a,b,c，用户U2购买了a,b,c,e,f,，用户U3购买了a,e,k取2,U1没有对物品e,f产生过行为：
S(U1,2) = {U2,U3}；N(f) = {U2} ；N(e) = {U2,U3}
如果要给用户U1只推荐一个物品，由于P(U1,e)>P(u1,f),推荐物品e。
精度指标不和参数k成线性关系，对k也不是特别敏感，K只要选定在一定范围内，就可以获得不错的精度。k越大则UserCF推荐结果就越热门（流行度越大），覆盖率越低。
UserCF模型会因为用户数量的增加导致用户兴趣相似度矩阵将越来越困难，其运算时间复杂度和空间复杂度的增长和用户数的增长近似于平方关系，所以就有了另一种协同过滤算法。
三 、基于物品的协同过滤算法
基于物品的协同过滤算法的核心思想是：给用户推荐和其过去感兴趣的物品相似的物品，比如要给A做个性化推荐，那就给他推荐跟他以前喜欢的物品的相似物品。
算法主要包括两个步骤：
（1）计算物品之间的相似度
ItemCF算法并不利用物品的内容属性计算物品之间的相似度，它主要通过分析用户的行为记录计算物品之间的相似度。该算法认为，物品A和物品B具有很大的相似度是因为喜欢物品A的用户大都也喜欢物品 B。
每个用户的兴趣都局限在某几个方面，如果两个物品属于一个用户的兴趣列表，那么两个物品可能就属于有限的几个领域，而如果两个物品同属于很多用户的兴趣列表，那么他们就可能属于同一个领域，因而有很大的相似度。因此ItemUser利用下面公式计算物品之间的相似度：
这里同样会出现一个用户购买了很多商品的问题，也就是活跃用户的问题，比如一个人是做口红批发生意的，他从淘宝网上以批发价买了所有的口红，从前面对ItemCF的讨论可以看到，这意味着因为存在这么一个用户，所有口红的两两之间就产生了相似度。这个用户虽然活跃，但是买这些口红并非都是出于自身的兴趣，而且这些口红覆盖了淘宝网口红品牌的很多领域，所以这个用户对于他所购买口红的两两相似度的贡献应该远远小于一个只买了几十个口红的女生。也就是让这些活跃用户对相似度计算造成的影响降低，计算如下：
（2）计算用户的兴趣
在得到物品j相似的k个物品S（j,K）后，通过下面的公式计算用户u对物品j的兴趣
其中P(u,j)表示用户u对物品j的兴趣，S(j,k)表示和物品j最相似的k个物品，N(u)表示用户产生过行为的物品集合，表示用户u对物品i是否产生过行为（对于评分系统，可以表示u对i的评分。
不进行惩罚的例子：给用户U1推荐物品，K取3，用户U1没有对e，f产生过行为：
S(e,3) = {a,f,b(c)}, S(f,3) = {e,b,c}
如果要给用户U1只推荐一个物品，由于P(U1,e)<P(U1,f),推荐物品f。
精度不和k成线性关系，选择合适的k比较重要。
四、UserCF和ItemCF的比较
会看一下我们之前写的UserCF和ItemCF的核心思想，UserCF给用户推荐跟他处于一个群体的用户的兴趣，更加社会化，ItemCF给用户推荐他喜欢的物品的相似物品，更加个性化。
根据这两个算法的特点来决定哪个领域用哪个算法，在新闻推荐领域，用户大多都喜欢看当下的热点新闻，爆点新闻，国家新闻之类的，跟自己的喜欢看的新闻关系并不是很大，在新闻推荐的任务中显得更加社会化，个性化是次要的，也即一个群体中的用户喜欢看的新闻是相似的。而在电商领域中，用户往往会有自己的兴趣特点，萝卜青菜各有所爱，比如一个用户就是喜欢穿黑色的裙子，戴黑色的帽子，那么她以往的历史行为都是对她进行个性化推荐黑色物品的依据。在电商领域中，用户不会想新闻领域一样倾向于热门的商品，用户都有自己的兴趣爱好，所以ItemCF适合在电商领域。
下面总结下五个UserCF和ItemCF的不同点
<1>个性化程度：
UserCF推荐结果着重于和用户兴趣相似的小群体的热点，推荐更加社会化，反映了用户所在兴趣群体中物品的热门程度（新闻领域）
ItemCF着重于维护用户的历史兴趣，推荐更加个性化，反映了用户自己的兴趣传承，可以用于长尾物品丰富的领域 (电商领域)
<2>可解释性：
ItemCF可以利用用户的历史行为给推荐结果提供推荐解释，UserCF很难对推荐结果作出解释。
<3>相似度更新难易程度：
UserCF要计算用户相似度矩阵，适用于用户个数远少于物品个数的场景，ItemCF要计算物品相似度矩阵，适用于物品个数远少于用户个数的场景；互联网中物品的相似度相对于用户的兴趣一般比较稳定，UserCF中用户相似度矩阵相比ItemCF中物品相似度矩阵更新更频繁
<4>物品冷启动问题：
UserCF对物品冷启动不敏感， 对于新加入系统的物品，一旦有用户对该新物品产生行为，UserCF可以将该新物品推荐给和该用户相似的人群，而ItemCF无法很好地推荐新加入的物品
<5>用户冷启动问题：
ItemCF对用户冷启动不敏感，对于新加入的用户，一旦新用户对某物品产生行为，ItemCF可以给该新用户推荐和该物品相似的物品，而UserCF无法很好地给新加入的用户产生推荐
五、召回阶段的选择
对于召回任务的要求，协同过滤可以很快的从海量商品中选出万/千级别的商品，物品/用户的相似度矩阵隔一段时间就会离线更新，在把召回的物品送到排序算法之前，还是要考虑一下UserCF和ItemCF的差异，更好地为排序阶段准备优质的召回列表。
