基于用户的协同过滤算法
一、基本思路
在一个推荐场景,你需要给用户推荐一些商品,基本思路是:
(1)找到和目标用户兴趣相似的用户集合。
(2)找到这个集合中的用户喜欢的,且目标用户没有听说过的物品推荐给目标用户。
二、相似度度量
可以有许多不同的方式用于度量,常见的有Jaccard公式,余弦相似度等等。
余弦相似度公式如下:
duv=|N(u)∩N(v)||N(u)||N(v)|−−−−−−−−−−√ d u v = | N ( u ) ∩ N ( v ) | | N ( u ) | | N ( v ) |
N(u) 表示用户u给过正反馈的商品集合,所谓正反馈就是用户倾向于喜欢该物品。N(v)表示用户v给过正反馈的商品集合。分子表示用户u和用户v都喜欢的物品集合。
三、实验设计
数据集:GroupLens提供的MovieLens数据集(http://www.grouplens.org/node/73)
本次实验采用1m数据集,该数据集包含了6000多用户对4000多部电影的100多万个评分。本实验讨论的是TopN问题,因此对于评分不予讨论。
3.1 评测指标
将数据集划分成训练集和测试集,对于训练集的每一个用户,利用协同过滤算法向其推荐商品,若推荐结果中的某个商品在测试集中的该用户的记录中出现了,则代表该结果是真正例。下面公式的R(u)表示对用户u推荐的商品集合,T(u)表示用户u在测试集上喜欢的物品集合。
3.1.1 召回率
Recall=∑u|R(u)∩T(u)|∑u|T(u)| R e c a l l = ∑ u | R ( u ) ∩ T ( u ) | ∑ u | T ( u ) |
3.1.2 准确率
Precision=∑u|R(u)∩T(u)|∑u|R(u)| P r e c i s i o n = ∑ u | R ( u ) ∩ T ( u ) | ∑ u | R ( u ) |
3.1.3 覆盖率
覆盖率反映了推荐算法发掘长尾的能力,说明推荐算法越能将长尾中的物品推荐给用户。下面的公式表示的就是最终的推荐列表中包含多大比例的商品。I表示所有商品的集合。
Coverage=⋃u∈UR(u)|I| C o v e r a g e = ⋃ u ∈ U R ( u ) | I |
3.1.4 新颖性
新颖的推荐是指给用户推荐那些他们以前没有听说过的物品,最简单的评测方法就是利用推荐结果的平均流行度。
3.1.5测评指标的代码实现
# 名 称: evaluate
# 功 能: 计算评测指标
# 参 数: trainset, 训练集
# testset, 测试集
# moviepopularity, 商品的流行度
# numofmovies, 所有电影的数量
# usersim, 相似用户matrix
# K, 算法选择K个相似用户
# N, 算法最终选择N个商品
# 返 回 值: precision, 准确率 recall, 召回率,coverage,覆盖率 popularity, 新颖度
# 修 改: 2018/5/29
def evaluate(trainset,testset,moviepopularity,numofmovies,usersim,K,N):
print('Evaluation start...')
hit =
TPFN =
TPFP =
allrecmovies = set()
popular_sum =
index=
print("starting evaluate...")
print("total number of users is: " + str(len(trainset)))
for user in trainset.keys():
index +=
if index % ==:
print("evaluate..." + str(index) + str(len(trainset)))
# 协同过滤算法对用户user的推荐结果
rec_movies = recommend(usersim,trainset,user,K,N)
if user not in testset.keys():
continue
testmovies = testset[user]
for rec_movie,_ in rec_movies:
# R(u)∩T(U)的情况
if rec_movie in testmovies:
# 真正例
hit+=
allrecmovies.add(rec_movie)
# 计算平均流行度,使用log是为了使均值比较稳定,moviepopularity里面存储的是每个电影被正反馈操作的次数。
popular_sum += math.log( + moviepopularity[rec_movie])
# 所有的正例
TPFN += len(testmovies)
# 所有推荐给用户的商品数量
TPFP += N
# 准确率
precision = hit * / TPFP
# 召回率
recall = hit * /TPFN
# 覆盖率
coverage = len(allrecmovies) / ( * numofmovies)
# 流行度
popularity = popular_sum / ( * TPFP)
print('precision=%.4f\trecall=%.4f\tcoverage=%.4f\tpopularity=%.4f' %
(precision, recall, coverage, popularity))
return precision,recall,coverage,popularity
3.2 具体步骤
3.2.1 获得训练集和测试集
# 名 称: produceData
# 功 能: 获得训练集和测试集
# 参 数: filepath, 文件路径
# pivot, 随机概率
# 返 回 值: trainset, 训练集
# testset 测试集
# 修 改:2018/5/29
def produceData(filepath,pivot=):
trainset={}
testset={}
file = open(filepath,'r')
lines = file.readlines()
l = len(lines)
print("Number of data is" + str(l))
for i in range(l):
if i%==:
print("loading data......" + str(i) + '/' + str(l))
user,movie,ranting,_ = lines[i].split('\n')[].split('::')
if random.random() < pivot:
trainset.setdefault(user,{})
trainset[user][movie] = ranting
else:
testset.setdefault(user,{})
testset[user][movie] = ranting
return trainset,testset
3.2.2 获得movie-user以及moviepopularity
该步是为了获取以movie为key,user为value的字典,以及每部电影的popularity。
# 名 称: FindRelativeDict
# 功 能: 获得相关字典
# 参 数: trainset 训练集
# 返 回 值: movie2user, {'movie':users}字典
# moviepopularity, {'movie': popularity}字典
# 修 改: 2018/5/29
def FindRelativeDict(trainset):
movie2user = {}
moviepopularity ={}
for user,movies in trainset.items():
for movie in movies:
if movie not in movie2user.keys():
movie2user[movie] = set()
movie2user[movie].add(user)
if movie not in moviepopularity.keys():
moviepopularity[movie] =
# popularity 定义为电影被所有用户给过正反馈的次数
moviepopularity[movie] +=
return movie2user,moviepopularity
3.2.3 计算相似用户dict
在这里运用到上面的用户相似度度量的余弦相似度公式。
# 名 称: FindUserSimilarity
# 功 能: 计算用户相似性字典
# 参 数: trainset 训练集
# movie2user {'movie':users}字典
# 返 回 值: usersim 相似用户矩阵 {'user':{'similar_user': 相似程度}}
# 修 改: 2018/5/29
def FindUserSimilarity(trainset,movie2user):
usersim = {}
for movie,users in movie2user.items():
for u in users:
usersim.setdefault(u,defaultdict(int))
for v in users:
if u==v:
continue
else:
usersim[u][v] +=
print( "starting calculate the similarity matrix of users...")
index=
for u,simiusers in usersim.items():
for v,count in simiusers.items():
index+=
if index % == :
print("calculating...." + str(index))
usersim[u][v] = count / math.sqrt(
len(trainset[u]) * len(trainset[v]))
return usersim
3.2.4 对某用户进行推荐
# 名 称: recommand
# 功 能: 给某用户推荐N件商品
# 参 数: usersim 相似用户字典
# trainset 训练集
# user 用户
# K 在推荐时选取K个最接近的相似用户
# N 最终选取N件商品给用户
# 返 回 值: recommendres 推荐的商品字典
# 修 改: 2018/5/29
def recommend(usersim,trainset,user,K,N):
userrec = {}
currentmovies = trainset[user]
for similar_user, similarity_factor in sorted(usersim[user].items(),
key=itemgetter(), reverse=True)[:K]:
for movie in trainset[similar_user]:
if movie in currentmovies:
continue
userrec.setdefault(movie,)
userrec[movie] += similarity_factor
recommendres = sorted(userrec.items(), key=itemgetter(), reverse=True)[:N]
return recommendres
实验结果
可以发现随着K的增加,准确率,召回率,流行度会随之升高,但是覆盖率变差,这是因为随着K的增加,该算法会倾向于推荐热门的物品,而对长尾物品的推荐越来越少,因此造成了覆盖率的降低。
[1]: https://github.com/Lockvictor/MovieLens-RecSys 协同过滤算法
[2]: 项亮. 推荐系统实践[M]. 人民邮电出版社, 2012.