用一百行 Python 代码,入门协同过滤推荐。
用户对物品的喜好记录,第一列是用户,第二列是物品。在终端输入:
python3
import operator
prefs_str = '''\
david 百年孤独
david 霍乱时期的爱情
david 从0到1
andy 霍乱时期的爱情
jack 浪潮之巅
jack 失控
jack 创业维艰
michale 寻路中国:从乡村到工厂的自驾之旅
michale 背包十年:我的职业是旅行
ann 活着
ann 霍乱时期的爱情
ann 迟到的间隔年
joel 巨人的陨落:世纪三部曲
joel 中国历代政治得失
joel 人类简史:从动物到上帝
joel 失控
jim 背包十年:我的职业是旅行
jim 迟到的间隔年
ray 霍乱时期的爱情
ray 迟到的间隔年
ray 枪炮、病菌与钢铁:人类社会的命运
'''
偏好记录可以转化成偏好矩阵,在 Python 中用 dict 保存:
# {'andy': {'霍乱时期的爱情': 1},...}
def read_prefs(prefs_str):
prefs = {}
for line in prefs_str.split('\n'):
parts = line.rstrip().split()
if len(parts) == 2:
userId, itemId = parts
prefs.setdefault(userId, {})
prefs[userId].update({itemId:1})
return prefs
prefs = read_prefs(prefs_str)
给定两个用户 user1
user2
和偏好向量 [1,0,0,0,0,0]
[1,1,0,0,0,0]
,我们需要定义一个距离函数,返回 0.0~1.0,衡量他们的相似度。距离函数可以选择余弦距离、欧几里得距离、棋盘距离等等,定义不同的距离函数有不同的推荐效果。
这里简单地用 Jaccard 相似性系数,即两个用户感兴趣的书的交集除并集:
def jaccard_distance(prefs, user1, user2):
s1 = set(prefs[user1].keys())
s2 = set(prefs[user2].keys())
return 1.0 * len(s1.intersection(s2)) / len(s1.union(s2))
举个例子,item5 和 item6 的用户评价向量的 Jaccard 距离 = 1 / 4 = 0.25。
prefs | user1 | user2 | user3 | user4 | user5 | user6 |
---|---|---|---|---|---|---|
item5 | 1 | 1 | 1 | |||
item6 | 1 | 1 |
现在我们有了用户的偏好信息,能够衡量任意用户间的相似度,那么,对于 user1
,如何给他推荐物品?
首先,要找出与这个 user1
兴趣相近的用户们,即与 user1
对偏好向量距离相近的用户。然后,找出兴趣相近用户中,最受欢迎的书,推荐给 user1
。
比如对 user4
,发现 user5
的评价距离相近,可以推荐他在读的 item4
给他。
# 找出与 user1 兴趣最相近的用户 user1 -> [(1.0, user3), (0.8, user4), ...]
def top_matches(prefs, user1, similarity, n = 5):
scores = [(similarity(prefs, user1, user2), user2) for user2 in prefs if user1 != user2]
scores.sort()
scores.reverse()
return scores[0:n]
# prefs -> "用户 xx 根据 xx 推荐 xx 书籍 xxx"
def calculate_user_cf(prefs, similarity, n = 10):
ret = {}
for user in prefs.keys():
scores = top_matches(prefs, user, similarity, n)
ret[user] = scores
return ret
def print_recomendation(prefs, similiar_users, min_score = 0.1):
# 对每个用户
for target_user in similiar_users:
itemId_cnt = {}
# 找出兴趣相近的用户
for score, similiar_user in similiar_users[target_user]:
if score > min_score:
# 统计兴趣相近用户最喜欢的书,排序
for itemId in set(prefs[similiar_user]) - set(prefs[target_user]):
itemId_cnt.setdefault(itemId, 0)
itemId_cnt[itemId] += 1
recommends_itemId_cnt = sorted(itemId_cnt.items(), key=operator.itemgetter(1), reverse=True)
print('\n用户:%s\n\t喜欢:%s\n\t相似用户:%s\n\t推荐:%s' % (target_user, list(prefs[target_user].keys()), list(filter(lambda score_user:score_user[0] > min_score, similiar_users[target_user])), recommends_itemId_cnt))
print('\n基于用户的协同过滤推荐')
similiar_users = calculate_user_cf(prefs, jaccard_distance, n = 10)
print_recomendation(prefs, similiar_users)
输出结果
用户:jim
喜欢:['背包十年:我的职业是旅行', '迟到的间隔年']
相似用户:[(0.3333333333333333, 'michale'), (0.25, 'ray'), (0.25, 'ann')]
推荐:[('霍乱时期的爱情', 2), ('活着', 1), ('寻路中国:从乡村到工厂的自驾之旅', 1), ('枪炮、病菌与钢铁:人类社会的命运', 1)]
...
在神奇的数学世界里,我们把偏好矩阵转置,即行列互换,用相同的思想,可以得到一种新的推荐方法 —— 基于物品的协同过滤。
用 User-CF 方法,对于给定用户,根据偏好矩阵,算出兴趣相近的用户;用 Item-CF 方法,对于给定物品,根据偏好矩阵,算出用户评价向量相近的物品,作为推荐。
# prefs[userId][itemId] -> prefs[itemId][userId]
def transpose_prefs(prefs):
ret = {}
for userId in prefs:
for itemId in prefs[userId]:
ret.setdefault(itemId, {})
ret[itemId][userId] = prefs[userId][itemId]
return ret
得到转置后的偏好矩阵:
prefs | user1 | user2 | user3 | user4 | user5 | user6 |
---|---|---|---|---|---|---|
item1 | 1 | 1 | ||||
item2 | 1 | |||||
item3 | ||||||
item4 | 1 | |||||
item5 | 1 | 1 | 1 | |||
item6 | 1 | 1 |
如果一个用户喜欢物品 item5
,可以推荐用户偏好向量距离相近的物品如 item4
和 item6
给这位用户。
def calculate_item_cf(prefs, similarity, n = 10):
ret = {}
itemPrefs = transpose_prefs(prefs)
# 对于每个物品,找出用户评价向量距离相近的物品
for item in itemPrefs:
scores = top_matches(itemPrefs, item, similarity, n)
ret[item] = scores
return ret
def print_similiar_items(similiar_items, min_score = 0.1):
for target_itemId in similiar_items:
print('\n根据 %s 推荐:' % target_itemId)
score_items = similiar_items[target_itemId]
for score_item in score_items:
score, itemId = score_item
if score > min_score: print('\t%s %f' % (itemId, score))
print('\n基于书籍的协同过滤推荐')
similiar_items = calculate_item_cf(prefs, jaccard_distance, n = 10)
print_similiar_items(similiar_items)
输出结果
根据 创业维艰 推荐:
浪潮之巅 1.000000
失控 1.000000
...
《集体智慧编程》—— 协同过滤
推荐算法综述1
推荐算法综述2
推荐算法综述3
推荐算法综述4
推荐算法综述5
Amazon Item-CF Patent 1998