本文针对无上下文信息的隐性反馈数据集（每一条行为记录仅仅包含用户ID和物品ID），介绍基于用户的协同过滤算法原理。
基于用户的协同过滤推荐算法本质：找到和待推荐用户相似的用户群，推进该用户群感兴趣且待推荐用户没购买过的物品。例如下图中， 用户a购买过物品A、C，用户c购买过物品A、C、D ，则用户a和用户c比较相似，可以考虑把物品D推荐给用户a。
基本步骤：
为便于理解，本文后面示例的计算中使用下面数据： 第一列为索引，userId是用户标识，itemsId表是用户购买过的物品ID。
给定用户 u u u和用户 v v v，令 N ( u ) N(u) N(u)表示用户 u u u点击过的物品集合，令 N ( v ) N(v) N(v)为用户 v v v点击过的物品集合
余弦相似度
W
u
,
v
=
∣
N
(
u
)
⋂
N
(
v
)
∣
∣
N
(
u
)
∣
∣
N
(
v
)
∣
W_{u,v} = \frac{|N(u) \bigcap N(v)|} {\sqrt{|N(u)| | N(v)|}}
Wu,v=∣N(u)∣∣N(v)∣
∣N(u)⋂N(v)∣ 其中
∣
∗
∣
|*|
∣∗∣表示取模，即物品的个数。
Jaccard公式
W
u
,
v
=
∣
N
(
u
)
⋂
N
(
v
)
∣
∣
N
(
u
)
⋃
N
(
v
)
∣
W_{u,v} = \frac{|N(u) \bigcap N(v)|} {|N(u) \bigcup N(v)|}
Wu,v=∣N(u)⋃N(v)∣∣N(u)⋂N(v)∣
【例】根据上述数据，生成每个用户购买过的商品列表
可据此计算用户相似度，例如计算用户A和B的余弦相似度
W
A
,
B
=
∣
{
1
,
2
,
5
}
⋂
{
1
,
3
,
4
}
∣
∣
{
1
,
2
,
5
}
∣
∣
{
1
,
3
,
4
}
∣
=
1
3
W_{A,B} = \frac{| \{1,2,5\} \bigcap \{1,3,4\} |} {\sqrt{| \{1,2,5\}| | \{1,3,4\} |}} = \frac{1} {3}
WA,B=∣{1,2,5}∣∣{1,3,4}∣
∣{1,2,5}⋂{1,3,4}∣=31
上面公式中需要对任意两个用户计算相似度，这种方法的时间复杂度是
O
(
U
2
)
O(U^2)
O(U2)，其中
U
U
U标识用户数。当用户数量大时，计算起来会很费时。其实，并不是所有用户购买过的物品都有交集，即存在
∣
N
(
u
)
⋂
N
(
v
)
∣
=
0
|N(u) \bigcap N(v)|=0
∣N(u)⋂N(v)∣=0。因此，可以先计算出
∣
N
(
u
)
⋂
N
(
v
)
∣
≠
0
|N(u) \bigcap N(v)| \neq 0
∣N(u)⋂N(v)∣=0的用户对
(
u
,
v
)
(u,v)
(u,v)，然后再除以相似度中的分母得到用户的相似度矩阵。
用户相似度计算的步骤如下:
根据用户相似度，计算待推荐用户
u
u
u对与其最相似的
K
K
K个用户购买过商品
i
i
i的感兴趣程度:
p
(
u
,
i
)
=
∑
v
∈
S
(
u
.
K
)
⋂
N
(
i
)
W
u
,
v
r
v
,
i
p(u,i) = \sum_{v \in S(u.K) \bigcap N(i)}W_{u,v}r_{v,i}
p(u,i)=v∈S(u.K)⋂N(i)∑Wu,vrv,i其中，
S
(
u
.
K
)
S(u.K)
S(u.K)为和用户
u
u
u兴趣最接近的
K
K
K个用户，
r
v
,
i
r_{v,i}
rv,i代表用户对物品
i
i
i的兴趣，因为只是用了行为数据，所以
r
v
,
i
=
1
r_{v,i}=1
rv,i=1.
【例】生成推荐列表
