【推荐系统（一）】协同过滤之基于领域的方法(UserCF，ItemCF)

基于用户行为分析的推荐算法一般称为协同过滤算法。所谓协同过滤，就是指众多的用户可以齐心协力，通过不断地和网站互动，使 自己的推荐列表能够不断过滤掉自己不感兴趣的物品，从而越来越满足自己的需求。常见实现方法的包括：

1. 基于邻域的方法
2. 隐语义模型
3. 基于图的随机游走算法

本文主要讲解基于邻域的方法，又可以细分为基于用户的协同过滤算法（UserCF）和基于物品的协同过滤算法（ItemCF）。

一、基于用户的协同过滤算法（UserCF）

基于用户是指通过分析用户对商品的行为（如浏览、收藏、加入购物车、购买……）计算出哪些用户是兴趣相似的，然后把兴趣相似的用户所关注的商品相互推荐。

基于用户的协同过滤算法（UserCF）的基本思想：当给用户A推荐时，可以先找到和他有相似兴趣的其他用户，然后把相似用户喜欢的、而用户A没有接触过的物品推荐给A。

UserCF算法分为两个步骤：

1. 找到和目标用户有相似兴趣的用户集合
2. 从集合中找到用户可能喜欢的、但是没有接触过的物品推荐给目标用户

1，找到相似用户

假设有6个用户A_{F，对编号为1}6的物品有不同的行为。不同的行为代表对商品喜爱程度的不同，假设：浏览1分、收藏3分、加入购物车5分、购买10分。

于是可以把不同用户对不同商品的喜爱程度转换为评分矩阵：

用户/商品	1	2	3	4	5	6
A	1		5	3
B		3			3
C	5					10
D	10				5
E			5	1
F		5	3			1

可以看到用户A和B感兴趣的商品完全不同，但是A和E可能有相似的兴趣。为了计算用户之间的相似度，设N(u)为用户 u 有过正反馈的物品集合，N(v) 为用户 v 有过正反馈的物品集合，用户 u 和 v 的兴趣相似度可以用余弦相似度表示：
$cos<u, v> = \frac{N(u) \cdot N(v)}{\sqrt{|N(u)|\times|N(v)|}}$cos<u,v>=∣N(u)∣×∣N(v)∣​N(u)⋅N(v)​
当然还有别的计算方法，例如：切比雪夫距离、欧里几得距离、曼哈顿距离、杰卡德距离、皮尔森系数等。

以余弦相似度的计算为例子：
$cos <A, C> = \frac{1 \times5 + 5 \times 0 + 3 \times 0}{\sqrt{1^2 + 5^2 + 3^2} \times \sqrt{5^2 + 10^2}} = 0.08$cos<A,C>=12+52+32​×52+102​1×5+5×0+3×0​=0.08
同理可以计算其他用户之间的相似度，将它们用矩阵来表示，得到的矩阵称之为相似度矩阵：

	A	B	C	D	E	F
A	1	0	0.08	0.15	0.93	0.43
B	0	1	0	0.32	0	0.6
C	0.08	0	1	0.4	0	0.15
D	0.15	0.32	0.4	1	0	0
E	0.93	0	0	0	1	0.5
F	0.43	0.6	0.15	0	0.5	1

表中数值越大，表示相似度越高。按相似度排序，可以轻易找到与用于u最相似的 k 个用户。

2，推荐未接触过的物品

接下来可以用上面的相似度矩阵来给用户推荐和他兴趣相似的用户喜欢的物品。用户 u 对物品 i 的兴趣程度可以估计为：
$p(u,i) = \sum_{v\in{S(u,K)\cap N(i)}} w_{uv}r_{vi}$p(u,i)=v∈S(u,K)∩N(i)∑​wuv​rvi​
其中，S(u,K) 为和用户 u 兴趣最接近的 K 个用户， N( i ) 为对物品 i 有正反馈的用户集合， $w_{uv}$wuv​ 为用户 u 和用户 v 的兴趣相似度， $r_{vi}$rvi​为用户 v 对物品 i 的兴趣。

这个式子是先找到 K个 与用户 u 相似 并且 对物品 i 有过兴趣 的用户集合，然后对集合中的每个 v 计算:

( 用户 u 和相似用户 v 的相似程度$w_{uv}$wuv​ ) X ( 用户 v 对商品 i 的喜爱程度 r_{vi} )

然后将乘积结果累加作为 u 对 i 的感兴趣程度。

上面的说法可能比较抽象，举个极端的例子，假设和用户 E 兴趣最接近的用户数 K = 6，那么 S(u,K) 实际上就是相似度矩阵E所在的行。再假设要预估的物品 i=5，则 N( i=5 ) = {B, D}，于是有 v = {B, D} 。于是有：
$p(u=E,i=5) = w_{EB}r_{B5} + w_{ED}r_{D5} = 0$p(u=E,i=5)=wEB​rB5​+wED​rD5​=0
同理可以计算其他用户 u 对某个物品 i 的感兴趣程度。实际上，对于上面的这个极端的例子，不难发现，其数值就等于 相似度矩阵的第u行 与 评分矩阵第 i 列 内积的结果：

对其他的行与列而言，运算 相似度矩阵 X 评分矩阵 可以得到 推荐列表：

u / i	1	2	3	4	5	6
A	2.9	2.2	11.0	3.9	0.8	1.2
B	3.2	6.0	1.8	0	4.6	0.6
C	9.1	0.8	0.9	0.2	2.0	10.2
D	11.2	1.0	0.8	0.5	6.0	4.0
E	0.9	2.5	11.2	3.8	0	0.5
F	1.2	6.8	7.7	1.8	1.8	2.5

由于用户已经对推荐列表中的一些商品有过行为：

所以还要把这些商品给滤除掉，最终得到的推荐表为：

	1	2	3	4	5	6
A		2.2			0.8	1.2
B	3.2		1.8	0		0.6
C		0.8	0.9	0.2	2.0
D		1.0	0.8	0.5		4.0
E	0.9	2.5			0	0.5
F	1.2			1.8	1.8

表中数值越大，表示感兴趣程度越高。有了这张推荐表，就可以为每个用户推荐 topK 个感兴趣大的、且未曾接触过的商品。

UserCF 改进

对于一些热门的商品例如《新华字典》，许多用户都可能会有购买行为，但是不能说明买过这本书的兴趣就相同。但是都买了相对冷门点的《统计学习方法》的人，就很可能有相似的兴趣。

为了改进这个问题，假设 N(i) 为喜欢物品 i 的用户数，则可以改用下面的公式计算相似度：
$w_{uv} = \frac{\sum_{i\in{N(u)\cap N(v)}} \frac{1}{\log(1+|N(i)|)}}{\sqrt{|N(u)||N(v)|}}$wuv​=∣N(u)∣∣N(v)∣​∑i∈N(u)∩N(v)​log(1+∣N(i)∣)1​​
上面的式子中 $\frac{1}{\log(1+|N(i)|)}$log(1+∣N(i)∣)1​ 惩罚了用户 u 和用户 v 共同兴趣列表中热门物品对他们相似度的影响。

二、基于物品的协同过滤算法（ItemCF）

基于物品的协同过滤算法（ItemCF）给用户推荐那些和他们之前喜欢的物品相似的物品，该算法不利用物品内容属性计算物品之间的相似度，而是通过分析用户的行为记录计算物品之间的相似度。

**基本思想：物品A和物品B具有很大的相似度是因为喜欢物品A的用户大都也喜欢物品B。**比如给用户推荐《天龙八部》的解释可以是因为用户之前喜欢《射雕英雄传》。

主要步骤如下：

1. 根据用户行为计算物品之间的相似度；
2. 根据物品的相似度和用户的历史行为给用户生成推荐列表。

1，物品相似度计算

设 N( i ) 为喜欢物品 i 的用户数， N( j ) 为喜欢物品 j 的用户数， i 和 j 的相似度可以通过下面的式子计算：
$w_{ij} = \frac{|N(i)\cap N(j)|}{\sqrt{|N(i)||N(j)|}}$wij​=∣N(i)∣∣N(j)∣​∣N(i)∩N(j)∣​
两个物品产生相似度是因为它们共同被很多用户喜欢，也就是说每个用户都可以通过他们的历史兴趣列表给物品“贡献”相似度。所有物品之间的计算结果构成物品相似度矩阵。

2，推荐列表计算

计算用户 u 对物品 i 的兴趣程度：
$p(u,i) = \sum_{j\in{S(i,K)\cap N(u)}} w_{ij}r_{uj}$p(u,i)=j∈S(i,K)∩N(u)∑​wij​ruj​
S(i, K) 为和物品 i 最相似的 K 个物品， N(u) 为用户 u 喜欢的物品集合，$w_{ij}$wij​ 为物品 i 和物品 j 的相似度， $r_{uj}$ruj​为用户 u 对物品 j 的兴趣。

简单来说，就是把曾经感兴趣的所有K个 （与目标物品 i 相似的物品 j 的感兴趣程度 $r_{uj}$ruj​ ）与 ( i 和 j 的相似程度$w_{ij}$wij​ ) 相乘， 然后将乘积的结果求和作为新物品 i 的感兴趣程度，步骤如下：

1. $j\in{S(i,K)\cap N(u)}$j∈S(i,K)∩N(u) 意味着从 用户曾经喜欢过的物品中 筛选出 恰好与目标物品 i 比较相近 的物品作为 j 。

2. 对于每一个筛选到的 j 计算：

   ( 目标物品 i 和 曾经感兴趣的物品 j 相似度 $w_{ij}$wij​ ) * ( 用户对曾经感兴趣的物品 j 的评价$r_{uj}$ruj​ )

3. 将所有 j 在第二步的计算结果累加起来，作为对物品 i 的感兴趣程度

这个公式的理解是：和用户历史上感兴趣的物品越相似的物品，越有可能在用户的推荐列表中获得比较高的排名。

当然也可以按照前文 UserCF 的理解方式，将 物品相似度矩阵 X 评分矩阵 进而得到 推荐列表，在此不再赘述。

ItemCF 改进

由于活跃用户可能会广泛的购买各种类别商品，因此对物品相似度的贡献要小于不活跃用户。本节计算相似度的方法同样可以改用下面的方法：
$w_{ij} = \frac{\sum_{u \in N(i) \bigcap N(j)}\frac{1}{\log{1}+|N(u)|}}{\sqrt{|N(i)||N(j)|}}$wij​=∣N(i)∣∣N(j)∣​∑u∈N(i)⋂N(j)​log1+∣N(u)∣1​​
这个公式只是对活跃用户做的一种软性惩罚，但对于很多过于活跃的用户，在实际计算中一般直接忽略他的兴趣列表，而不将其纳入到相似度计算的数据集中。

归一化

如果将 ItemCF 的相似度矩阵按最大值归一化，可以提高推荐的准确率。如果已经得到了物品相似度矩阵 w ，那么可以用如下公式得到归一化之后的相似度矩阵 w’ ：
$w_{ij}' = \frac{w_{ij}}{\max\limits_i w_{ij}}$wij′​=imax​wij​wij​​
归一化的好处不仅仅在于增加推荐的准确度，它还可以提高推荐的覆盖率和多样性。

三、UserCF 与 ItemCF 对比

UserCF 给用户推荐那些和他有共同兴趣爱好的用户喜欢的物品，而 ItemCF 给用户推荐那些和他之前喜欢的物品类似的物品。就具体应用来说，UserCF 曾被 GroupLens 用来实现新闻的个性化推荐， ItemCF 则是亚马逊、Netflix 用于做商品、视频推荐。

为何新闻推荐用 UserCF ?

从个性化与时效性角度来看，在新闻网站中，人们倾向于点击热门的新闻。因此推荐的新闻强调抓住热点，个性化的需求次之。UserCF 可以给用户推荐和他有相似爱好的一群其他用户今天都在看的新闻，这样在抓住热点和时效性的同时，保证了一定程度的个性化。

从技术角度来看，新闻的更新非常快，而 ItemCF 需要维护一张物品（新闻）相关度的表，如果物品更新很快，那么这张表也需要很快更新，这在技术上很难实现。而 UserCF 只需要维护用户相似性表，且更新速度相对物品来说缓慢的多。

为何商品和视频推荐用 ItemCF？

在这些购物与视频网站中，用户的兴趣是相对固定和持久的。个性化推荐的任务是帮助用户发现和他研究领域相关的物品，而不需要过多考虑这个物品是否热门。

从技术角度来看，这些网站的物品更新速度不会特别快，一天一次更新物品相似度矩阵对它们来说不会造成太大的损失，是可以接受的。

UserCF 、ItemCF 优缺点的对比

下图总结了UserCF和ItemCF优缺点的对比：

参考文章：

1. 《推荐系统实战》项亮

2. 推荐系统实战笔记（一）

3. 推荐系统UserCF和ItemCF

4. 《推荐系统实践》笔记