usercf代码java_基于⽤户的协同过滤算法（UserCF）原理以
及代码实践
简介
协同过滤(collaborative filtering)是⼀种在推荐系统中⼴泛使⽤的技术。该技术通过分析⽤户或者事物之间的相似性，来预测⽤户可能感兴趣的内容并将此内容推荐给⽤户。这⾥的相似性可以是⼈⼝特征的相似性，也可以是历史浏览内容的相似性，还可以是个⼈通过⼀定机制给与某个事物的回应。⽐如，A和B是⽆话不谈的好朋友，并且都喜欢看电影，那么协同过滤会认为A和B的相似度很⾼，会将A喜欢但是B没有关注的电影推荐给B，反之亦然。
协同过滤推荐分为3种类型：
基于⽤户(user-based)的协同过滤(UserCF)
基于物品(item-based)的协同过滤(ItemCF算法)
基于模型(model-based)的协同过滤 (ModelCF算法)
本⽂主要讲述基于⽤户协同过滤算法的原理以及代码实现。
算法原理
UserCF算法主要是考虑⽤户与⽤户之间的相似度，给⽤户推荐和他兴趣相似的其他⽤户喜欢的物品。俗话说"物以分，⼈以类聚"，⼈们总是倾向于跟⾃⼰志同道合的⼈交朋友。同理，你朋友喜欢的东西你⼤概率也可能会喜欢，UserCF算法正是利⽤了这个原理。举个例⼦，如果要给⼀个⽤户A推荐物品，可以先到与A最为相似的⽤户B，接着获取⽤户B最喜欢的且⽤户A没有听说过的物品，并预测⽤户A对这些物品的评分，从中选取评分最⾼的若⼲个物品推荐给⽤户A。
从上述描述可以知道，UserCF算法的主要步骤如下：
到与⽬标⽤户兴趣相似的⽤户集合
到这个集合中的⽤户最喜欢的，且⽬标⽤户还未接触过的物品推荐给⽬标⽤户
上述是UserCF算法的基本思路，⽅便读者形成对UserCF算法的整体印象。也许你看了上述⽂字依然没有思路，没关系，且继续往下看。
⾸先，根据算法的步骤1，我们⾃然⽽然就会提出⼀个问题，那就是如何度量两个⽤户之间的相似度？试想⼀下，我们在现实⽣活中如何判断两个⼈是否兴趣相似呢？⽐如你喜欢打LOL，恰巧你室友也喜欢，那显然你们的共同话题会⽐较多，因为你们有共同的兴趣爱好。我们刚好可以利⽤这⼀点来计算
⽤户之间的相似度。
对于⽤户u和⽤户v，令N(u)代表⽤户u喜欢的物品合集，令N(v)代表⽤户v喜欢的物品合集。N(u)∩N(v)代表的是⽤户u和⽤户v都喜欢的物品，N(u)∪N(v)代表的是⽤户u和⽤户v喜欢的物品的合集，那么可以利⽤以下公式来简单计算相似度:
上述公式叫做Jaccard公式，直观上理解就是，将⽤户u与⽤户v都喜欢的物品的数量除以他们喜欢物品的总和，如果u和v喜欢的物品是⼀模⼀样的，则u和v的相似度为1。
还有另外⼀种余弦相似度计算公式:
上述公式的分母部分代表的是u喜欢的物品的数量与v喜欢的物品的数量的乘积，⽽不再是他们之间的交集。
举个简单例⼦来表明如何计算⽤户u和v之间的相似度，假如⽤户u和⽤户v喜欢的游戏如下表：
⽤户
喜爱的游戏
u
{英雄联盟, 王者荣耀，绝地求⽣}
v
{英雄联盟，和平精英}
利⽤余弦相似度计算公式可以得到如下结果：
故，我们可以计算得到⽤户u和⽤户v之间的相似度为
。
⾄此，我们已经可以计算任意两个⽤户之间的相似度了，下⼀步要做的事情是建⽴⼀张⽤户相似度表，此表中保存了任意两个⽤户之间的相似度，⽅便后续挑选出与⽤户u最相似的若⼲个⽤户。
当⽤户相似度表建⽴起来了之后，UserCF算法就可以给⽤户推荐与他兴趣最相似的K个⽤户喜欢的物品了。那此时⼜会出现⼀个问题，假如我们要给⽤户w进⾏推荐，并且在⽤户相似度表中到了与他最相似的K个⽤户，这K个⽤户喜欢的物品有很多，我们怎么知道要推荐哪些物品给⽤户w呢？此时就涉及到了⽤户对物品的感兴趣程度，我们当然会把⽤户最感兴趣的物品推荐给他。故使⽤以下公式来度量⽤户u对物品i的感兴趣程度：
乍⼀看感觉很复杂，其实不然。
其中
python转java代码代表的是与⽤户
最相似的K个⽤户，将与⽤户
相似的⽤户列表按照相似度进⾏排序就可以得到。
代表的是对喜欢物品i的⽤户集合，
代表的是⽤户
和⽤户
之间的相似度，这个也可以直接从⽤户相似度表中得到。
代表⽤户v对物品i的兴趣，因为使⽤的是单⼀⾏为的隐反馈数据，所以所有的
。
对于与⽤户
最相似的K个⽤户，我们分别计算⽤户
与这K个⽤户喜欢的物品集合
之间的感兴趣程度，得到⽤户
对这N个物品的感兴趣程度列表，然后将其逆序排序，取前m个物品推荐给⽤户
，⾄此UserCF算法结束。
算法⼯作流程
接下来，我们⽤⼀个简单例⼦演⽰⼀下UserCF的具体⼯作流程。
下表是我们臆造的原始数据，也称之为User-Item表，即⽤户-物品列表，记录了每个⽤户喜爱的物品，数据表格如下：
⽤户
喜爱的物品
A
{a,b,d}
B
{a,c,d}
C
{b,e}
D
{c,d,e}
接下来我们需要计算⽤户相似度矩阵，最直观的⽅法就是，对于⽤户列表{A,B,C,D}，我们对其中两两⽤户都使⽤余弦相似度算法计算相似度。这种算法的时间复杂度是O(N^2)，当⽤户量很⼤的时候，计算⾮常耗时，在实际运⽤中不可取。观察⼀下相似度计算公式会发现，其实如果⽤户
和⽤户
没有共同喜欢的物品(⽐如表中的⽤户B和⽤户C)，那么他们之间的相似度为0，也就没有必要计算了。
也就是说我们没必要对任意两个⽤户之间都计算相似度，我们只需要计算那些彼此之间有共同喜爱物品的⽤户之间的相似度，故⾸先可以想到建⽴倒排表，即Item-User表，具体如下：
物品
喜爱它的⽤户
a
{A,B}
b
{A,C}
c
{B,D}
d
{A,B,D}
e
{C,D}
有了这张表之后，相当于我们将原先零散的⽤户按照他们喜爱的物品给划分成若⼲个⼩圈⼦。⽐如⽤户A、B由于都喜欢物品a，所以被分到了⼀起。同理，⽤户C、D都喜欢物品e，因此也被分到了⼀起。
那这么做的⽬的是什么呢？回顾⼀下上⾯说的⽤户相似度计算⽅法，可以看到⽆论是哪⼀种⽅法都要先求出|N(
)∩N(
)|，所以我们的⽬的就是为了快速地求出任意⽤户之间的交集。
由此可以建⽴下⾯的⽤户喜爱物品交集矩阵W：
A
B
C
2
1
1
B
2
2
C
1
1
D
1
2
1
其中W[u][v]代表的含义是⽤户u和⽤户v都喜爱的物品个数，即|N(
)∩N(
)
|。⽐如⽤户A、C都喜欢物品b，所以W[A][C]=1。⽤户A、B除了喜欢物品a以外，还共同喜欢物品d，因此
W[A][B]=2。
由于⽤户A、B之间的交集和⽤户B、A之间的交集是⼀样的，所以此矩阵是⼀个对称矩阵。
其实这⾥的W就是相似度计算公式中的分⼦部分，⽽每个⽤户的喜爱列表从之前的User-Item列表中就已经可以得到了，因此我们就可以计算出⽤户相似度矩阵了，结果如下：
A
B
C
D
A
0.67
0.67
0.67
C
0.41
0.41
D
0.33
0.67
0.41
当⽤户相似度矩阵建⽴好了之后，我们就可以对⽤户进⾏物品推荐了。
⽐如要对⽤户C进⾏物品推荐，通过查表可以知道(上表第四⾏)，⽤户A和⽤户D是⽐较相似的两个⽤户。
再通过User-Item表查询到⽤户A喜欢的物品列表{a,b,d}，⽤户D喜欢的物品列表{c,d,e}， 故⽤户A、D喜欢物品的交集是{a,b,c,d,e}，其中⽤户C喜欢的列表是{b,e}，为了避免重复推荐⽤户已经喜欢的物品，所以要先从物品列表中去掉⽤户C已经喜欢的物品，故最终待推荐的物品列表为{a,c,d}。
此时我们来计算⽤户C对待推荐物品列表中物品的感兴趣程度：
p(C,a) = W[C][A] = 0.41
p(C,c) = W[C][D] = 0.41
p(C,d) = W[C][A] + W[C][D] = 0.82
接着按照⽤户C对待推荐物品感兴趣程度对待推荐列表进⾏逆序排序，得到最终的推荐列表{d,a,c}，我们可以将整个推荐列表或者取前K个物品推荐给⽤户C。
⾄此，UserCF算法整体流程结束。
可以看到，算法的输出的最应该推荐给⽤户C的物品是d，我们不难发现这是因为与⽤户C最相似的⽤户A和⽤户D都喜欢物品d，因此将d推荐给C是⽐较合理的选择。
相似度算法改进
上述算法使⽤的是余弦相似度计算公式，但是这个公式过于粗糙，原因是余弦相似度只是简单地计算了⽤户u和⽤户v共同喜欢的物品在他们总共喜欢物品中占据的⽐例。
⽐如，两个⽤户都购买了时下热门物品，这并不能说明他们兴趣相似，因为热门物品是绝⼤多数⼈都会买的东西。换句话说，两个⽤户对冷门物品采⽤过相同的⾏为更能说明他们兴趣的相似度。因此John.S.Breese提出了以下相似度计算公式：