学习协同过滤推荐 \w 100行Python代码

Posted on | In

引言

用一百行 Python 代码，入门协同过滤推荐。

数据准备

用户对物品的喜好记录，第一列是用户，第二列是物品。在终端输入：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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 保存：

prefs item1 item2 item3 item4 item5 item6
user1 1
user2 1 1
user3 1
user4 1 1
user5 1 1
user6 1 
1
2
3
4
5
6
7
8
9
10
11
12
# {'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 相似性系数，即两个用户感兴趣的书的交集除并集：

1
2
3
4
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

基于用户的协同过滤（User-CF）

现在我们有了用户的偏好信息，能够衡量任意用户间的相似度，那么，对于 user1，如何给他推荐物品？

首先，要找出与这个 user1 兴趣相近的用户们，即与 user1 对偏好向量距离相近的用户。然后，找出兴趣相近用户中，最受欢迎的书，推荐给 user1。

比如对 user4，发现 user5 的评价距离相近，可以推荐他在读的 item4 给他。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 找出与 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)

输出结果

1
2
3
4
5
用户:jim
	喜欢:['背包十年:我的职业是旅行', '迟到的间隔年']
	相似用户:[(0.3333333333333333, 'michale'), (0.25, 'ray'), (0.25, 'ann')]
	推荐:[('霍乱时期的爱情', 2), ('活着', 1), ('寻路中国:从乡村到工厂的自驾之旅', 1), ('枪炮、病菌与钢铁:人类社会的命运', 1)]
...

基于物品的协同过滤（Item-CF）

在神奇的数学世界里，我们把偏好矩阵转置，即行列互换，用相同的思想，可以得到一种新的推荐方法 —— 基于物品的协同过滤。

用 User-CF 方法，对于给定用户，根据偏好矩阵，算出兴趣相近的用户；用 Item-CF 方法，对于给定物品，根据偏好矩阵，算出用户评价向量相近的物品，作为推荐。

1
2
3
4
5
6
7
8
# 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 给这位用户。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
2
3
4
根据 创业维艰 推荐:
	浪潮之巅 1.000000
	失控 1.000000
...

延伸阅读

《集体智慧编程》—— 协同过滤

推荐算法综述1

推荐算法综述2

推荐算法综述3

推荐算法综述4

推荐算法综述5

Amazon Item-CF Patent 1998

本文有帮助？