随着信息技术和互联网的发展，人们逐渐从信息匮乏的时代走入了信息过载的时代。在这个时代，无论是信息消费者还是信息生产者都遇到了很大的挑战：如何从大量信息中找到自己感兴趣的信息是一件非常困难的事情，这个时候就需要推荐系统。推荐系统不需要用户提供明确的需求，而是通过分析用户的历史行为给用户的兴趣建模，从而主动给用户推荐能够满足他们兴趣和需求的信息。
基于邻域的算法是推荐系统中最基本的算法，该算法不仅在学术界得到了深入研究，而且在业界得到了广泛应用。基于邻域的算法分为两大类，一类是基于用户的协同过滤算法，另一类是基于物品的协同过滤算法。这里我们主要讲解基于用户的协同过滤算法。
原理
俗话说“物以类聚、人以群分”，拿漫威英雄来说，如果
A
A
A喜欢钢铁侠、美国队长、死侍等，
B
B
B 也都喜欢这些人物形象，但他还喜欢蜘蛛侠，那么很有可能
A
A
A 也喜欢蜘蛛侠这个人物。
所以说，当一个用户
A
A
A 需要个性化推荐时，可以先找到和他兴趣相似的用户群体
B
B
B，然后把
B
B
B 喜欢的而
A
A
A 没有听说过的物品推荐给
A
A
A，这就是基于用户的系统过滤算法。
流程
协同过滤算法主要利用行为的相似度计算兴趣的相似度。给定用户 u u u 和用户 v v v ，令 N ( u ) N(u) N(u) 表示用户 u u u 感兴趣的物品集合，令 N ( v ) N(v) N(v) 为用户 v v v 感兴趣的物品集合。那么我们可以通过 J a c c a r d Jaccard Jaccard 公式或者余弦公式来计算用户 u u u, v v v 的相似程度：
J
a
c
c
a
r
d
Jaccard
Jaccard公式：
w
u
v
=
∣
N
(
u
)
∩
N
(
v
)
∣
∣
N
(
u
)
∪
N
(
v
)
∣
{w_{uv}} = \frac{{|N(u) \cap N(v)|}}{{|N(u) \cup N(v)|}}
wuv=∣N(u)∪N(v)∣∣N(u)∩N(v)∣
余弦相似度公式：
w
u
v
=
∣
N
(
u
)
∩
N
(
v
)
∣
∣
N
(
u
)
∣
∣
N
(
v
)
∣
{w_{uv}} = \frac{{|N(u) \cap N(v)|}}{{\sqrt {|N(u)||N(v)|} }}
wuv=∣N(u)∣∣N(v)∣
∣N(u)∩N(v)∣
假设目前共有4个用户：
A
A
A、
B
B
B、
C
C
C、
D
D
D；共有5个漫威英雄人物：死侍、钢铁侠、美国队长、黑豹、蜘蛛侠。用户与人物之间的爱好程度如下图所示：
| 用户 | 喜爱英雄人物 |
|---|---|
| A | 死侍、钢铁侠、美国队长 |
| B | 死侍、黑豹 |
| C | 钢铁侠、蜘蛛侠 |
| D | 蜘蛛侠、黑豹、美国队长 |
存储的数据格式为：
def load_data(filePath):
dataSet = {}
with open(filePath, "r", encoding="utf-8") as f:
for line in f:
user, hero, rating = line.strip().split(",")
dataSet .setdefault(user, {})
dataSet [user][hero] = rating
return dataSet 得到数据集格式如下：
{'A': {'死侍': '1', '钢铁侠': '1', '美国队长': '1'}, 'B': {'死侍': '1', '黑豹': '1'}, 'C': {'钢铁侠': '1', '蜘蛛侠': '1'}, 'D': {'蜘蛛侠': '1', '黑豹': '1', '美国队长': '1'}}数据处理好之后，需要建立物品到用户的倒排表，对于每个物品都保存对该物品产生过行为的用户列表。倒排表为喜欢每个物品对应的用户，如下所示：
| 喜爱英雄人物 | 用户 |
|---|---|
| 死侍 | A、B |
| 钢铁侠 | A、C |
| 美国队长 | A、D |
| 黑豹 | B、D |
| 蜘蛛侠 | C、D |
实现该功能的python方法：
def calc_user_sim(dataSet): # 建立物品-用户的倒排列表
item_users = dict()
for user, items in dataSet.items():
for movie in items:
if movie not in item_users:
item_users[movie] = set()
item_users[movie].add(user)
print("物品-用户倒排列表: ", item_users)
return item_users结果如下：
物品-用户倒排列表: {'钢铁侠': {'C', 'A'}, '死侍': {'B', 'A'}, '美国队长': {'D', 'A'}, '黑豹': {'B', 'D'}, '蜘蛛侠': {'D', 'C'}}假设用户 A A A 和用户 B B B 同时属于倒排表中 K K K 个人物对应的用户列表，就有 C [ A ] [ B ] = K C[A][B]=K C[A][B]=K。从而，可以扫描倒排表中每个物品对应的用户列表，将用户列表中的两两用户对应的 C [ A ] [ B ] C[A][B] C[A][B] 加1，最终就可以得到所有用户之间不为0的稀疏矩阵 C [ A ] [ B ] C[A][B] C[A][B]:
| A | B | C | D | |
|---|---|---|---|---|
| A | 1 | 1 | 1 | |
| B | 1 | 1 | ||
| C | 1 | 1 | ||
| D | 1 | 1 | 1 |
建立好稀疏矩阵之后，对于人物死侍，将 W [ A ] [ B ] W[A][B] W[A][B] 和 W [ B ] [ A ] W[B][A] W[B][A] 加1，对于钢铁侠，将 W [ A ] [ C ] W[A][C] W[A][C] 和 W [ C ] [ A ] W[C][A] W[C][A] 加1，以此类推，扫描完所有人物后，我们可以得到最终的 W W W 矩阵，这里的 W W W 是余弦相似度中的分子部分，然后将 W W W 除以分母可以得到最终的用户兴趣相似度：
def user_similarity(userSet):
C = dict()
N = dict()
for movie, users in userSet.items():
for u in users:
N.setdefault(u, 0)
N[u] += 1 # 每个商品下用户出现一次就加一次，就是计算每个用户一共购买的商品个数。
for v in users:
if u == v:
continue
C.setdefault(u, {})
C[u].setdefault(v, 0)
C[u][v] += 1
print("稀疏矩阵: ", C)
W = dict()
for u, related_users in C.items():
for v, cuv in related_users.items():
W.setdefault(u, {})
W[u].setdefault(v, 0)
W[u][v] = cuv / math.sqrt(N[u] * N[v])
print("用户相似度: ", W)
return W实现结果为：
稀疏矩阵: {'C': {'A': 1, 'D': 1}, 'A': {'C': 1, 'B': 1, 'D': 1}, 'B': {'A': 1, 'D': 1}, 'D': {'A': 1, 'B': 1, 'C': 1}}
用户相似度: {'C': {'A': 0.4082482904638631, 'D': 0.4082482904638631}, 'A': {'C': 0.4082482904638631, 'B': 0.4082482904638631, 'D': 0.3333333333333333}, 'B': {'A': 0.4082482904638631, 'D': 0.4082482904638631}, 'D': {'A': 0.3333333333333333, 'B': 0.4082482904638631, 'C': 0.4082482904638631}}| A | B | C | D | |
|---|---|---|---|---|
| A | 1 2 * 3 \frac{1}{{\sqrt 2 {\text{*}}\sqrt 3 }} 2 *3 1 | 1 2 * 3 \frac{1}{{\sqrt 2 {\text{*}}\sqrt 3 }} 2 *3 1 | 1 3 * 3 \frac{1}{{\sqrt 3 {\text{*}}\sqrt 3 }} 3 *3 1 | |
| B | 1 2 * 3 \frac{1}{{\sqrt 2 {\text{*}}\sqrt 3 }} 2 *3 1 | 1 2 * 3 \frac{1}{{\sqrt 2 {\text{*}}\sqrt 3 }} 2 *3 1 | ||
| C | 1 2 * 3 \frac{1}{{\sqrt 2 {\text{*}}\sqrt 3 }} 2 *3 1 | 1 2 * 3 \frac{1}{{\sqrt 2 {\text{*}}\sqrt 3 }} 2 *3 1 | ||
| D | 1 3 * 3 \frac{1}{{\sqrt 3 {\text{*}}\sqrt 3 }} 3 *3 1 | 1 2 * 3 \frac{1}{{\sqrt 2 {\text{*}}\sqrt 3 }} 2 *3 1 | 1 2 * 3 \frac{1}{{\sqrt 2 {\text{*}}\sqrt 3 }} 2 *3 1 |
def user_similarity_update(userSet):
C = dict()
N = dict()
for movie, users in userSet.items():
for u in users:
N.setdefault(u, 0)
N[u] += 1
for v in users:
if u == v:
continue
C.setdefault(u, {})
C[u].setdefault(v, 0)
C[u][v] += 1 / math.log(1 + len(users))
print("稀疏矩阵: ", C)
W = dict()
for u, related_users in C.items():
for v, cuv in related_users.items():
W.setdefault(u, {})
W[u].setdefault(v, 0)
W[u][v] = cuv / math.sqrt(N[u] * N[v])
print("用户相似度: ", W)
return W实现结果为：
稀疏矩阵: {'C': {'A': 0.9102392266268373, 'D': 0.9102392266268373}, 'A': {'C': 0.9102392266268373, 'B': 0.9102392266268373, 'D': 0.9102392266268373}, 'B': {'A': 0.9102392266268373, 'D': 0.9102392266268373}, 'D': {'A': 0.9102392266268373, 'B': 0.9102392266268373, 'C': 0.9102392266268373}}
用户相似度: {'C': {'A': 0.37160360818355515, 'D': 0.37160360818355515}, 'A': {'C': 0.37160360818355515, 'B': 0.37160360818355515, 'D': 0.3034130755422791}, 'B': {'A': 0.37160360818355515, 'D': 0.37160360818355515}, 'D': {'A': 0.3034130755422791, 'B': 0.37160360818355515, 'C': 0.37160360818355515}}p ( u , i ) = ∑ v ∈ S ( u , K ) ∩ N ( i ) w u v r v i p(u,i) = \sum\limits_{v \in S(u,K) \cap N(i)} {{w_{uv}}{r_{vi}}} p(u,i)=v∈S(u,K)∩N(i)∑wuvrvi
由上面步骤得到用户的兴趣相似度后， U s e r C F UserCF UserCF 算法会给用户推荐和他兴趣最相似的 K K K 个用户喜欢的物品。上面公式度量了 U s e r C F UserCF UserCF 算法中用户 u u u 对物品 i i i 的感兴趣程度：其中， S ( u , K ) S(u, K) S(u,K) 包含和用户 u u u 兴趣最接近的 K K K 个用户， N ( i ) N(i) N(i) 是对物品 i i i 有过行为的用户集合， w u v {w_{uv}} wuv 是用户 u u u 和用户 v v v 的兴趣相似度， r v i {r_{vi}} rvi 代表用户 v v v 对物品 i i i 的兴趣，因为使用的是单一行为的隐反馈数据，所以所有的 R v i = 1 Rvi=1 Rvi=1。
def recommend(user, train, W, K):
rvi = 1
rank = dict()
related_user=[]
interacted_items = train[user]
for co_user, item in W.items():
if co_user == user:
for user, score in item.items():
related_user.append((user, score))
break
print("与user用户相似度: ", related_user)
for v, wuv in sorted(related_user, key=itemgetter(1), reverse=True)[0:K]:
for i in train[v]:
if i in interacted_items:
continue
if i not in rank.keys():
rank[i]=0
rank[i] += wuv * rvi
print(rank)
return rank实现结果为：
与user用户相似度: [('C', 0.4082482904638631), ('B', 0.4082482904638631), ('D', 0.3333333333333333)]
{'蜘蛛侠': 0.4082482904638631, '黑豹': 0.4082482904638631}选取 K = 2 K=2 K=2，与用户 A A A最相似的两个用户为 B B B、 C C C，可以看出相对这两个用户， A A A对蜘蛛侠、黑豹没有过行为，因此可以把这两个人物推荐给用户 A A A。根据 U s e r C F UserCF UserCF 算法，用户 A A A 对蜘蛛侠、黑豹的兴趣是：
p
(
A
,
蜘
蛛
侠
)
=
w
A
C
=
0.4082482904638631
p(A,蜘蛛侠) = {{\text{w}}_{AC}} = 0.4082482904638631
p(A,蜘蛛侠)=wAC=0.4082482904638631
p
(
A
,
黑
豹
)
=
w
A
B
=
0.4082482904638631
p(A,黑豹) = {{\text{w}}_{AB}} = 0.4082482904638631
p(A,黑豹)=wAB=0.4082482904638631