基于用户的协同过滤推荐算法原理-附python代码实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了基于用户的协同过滤推荐算法原理-附python代码实现,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含13966字,纯文字阅读大概需要20分钟。
内容图文
![基于用户的协同过滤推荐算法原理-附python代码实现](/upload/InfoBanner/zyjiaocheng/837/c98a5591bcac4ab0b8a5c3adf4e87b47.jpg)
在推荐系统众多方法中,基于用户的协同过滤推荐算法是最早诞生的,原理也较为简单。该算法1992年提出并用于邮件过滤系统,两年后1994年被 GroupLens 用于新闻过滤。一直到2000年,该算法都是推荐系统领域最著名的算法。
本文简单介绍基于用户的协同过滤算法思想以及原理,最后基于该算法实现园友的推荐,即根据你关注的人,为你推荐博客园中其他你有可能感兴趣的人。基本思想
俗话说“物以类聚、人以群分”,拿看电影这个例子来说,如果你喜欢《蝙蝠侠》、《碟中谍》、《星际穿越》、《源代码》等电影,另外有个人也都喜欢这些电影,而且他还喜欢《钢铁侠》,则很有可能你也喜欢《钢铁侠》这部电影。
所以说,当一个用户 A 需要个性化推荐时,可以先找到和他兴趣相似的用户群体 G,然后把 G 喜欢的、并且 A 没有听说过的物品推荐给 A,这就是基于用户的系统过滤算法。原理
根据上述基本原理,我们可以将基于用户的协同过滤推荐算法拆分为两个步骤:
1. 找到与目标用户兴趣相似的用户集合
2. 找到这个集合中用户喜欢的、并且目标用户没有听说过的物品推荐给目标用户
1. 发现兴趣相似的用户
通常用 Jaccard 公式或者余弦相似度计算两个用户之间的相似度。设 N(u) 为用户 u 喜欢的物品集合,N(v) 为用户 v 喜欢的物品集合,那么 u 和 v 的相似度是多少呢:
Jaccard 公式:
余弦相似度:
假设目前共有4个用户: A、B、C、D;共有5个物品:a、b、c、d、e。用户与物品的关系(用户喜欢物品)如下图所示:
如何一下子计算所有用户之间的相似度呢?为计算方便,通常首先需要建立“物品—用户”的倒排表,如下图所示:
然后对于每个物品,喜欢他的用户,两两之间相同物品加1。例如喜欢物品 a 的用户有 A 和 B,那么在矩阵中他们两两加1。如下图所示:
计算用户两两之间的相似度,上面的矩阵仅仅代表的是公式的分子部分。以余弦相似度为例,对上图进行进一步计算:
到此,计算用户相似度就大功告成,可以很直观的找到与目标用户兴趣较相似的用户。
2. 推荐物品
首先需要从矩阵中找出与目标用户 u 最相似的 K 个用户,用集合 S(u, K) 表示,将 S 中用户喜欢的物品全部提取出来,并去除 u 已经喜欢的物品。对于每个候选物品 i ,用户 u 对它感兴趣的程度用如下公式计算:
其中 rvi 表示用户 v 对 i 的喜欢程度,在本例中都是为 1,在一些需要用户给予评分的推荐系统中,则要代入用户评分。
举个例子,假设我们要给 A 推荐物品,选取 K = 3 个相似用户,相似用户则是:B、C、D,那么他们喜欢过并且 A 没有喜欢过的物品有:c、e,那么分别计算 p(A, c) 和 p(A, e):
看样子用户 A 对 c 和 e 的喜欢程度可能是一样的,在真实的推荐系统中,只要按得分排序,取前几个物品就可以了。
在社交网络的推荐中,“物品”其实就是“人”,“喜欢一件物品”变为“关注的人”,这一节用上面的算法实现给我推荐 10 个园友。
1. 计算 10 名与我兴趣最相似的园友
由于只是为我一个人做用户推荐,所以没必要建立一个庞大的用户两两之间相似度的矩阵了,与我兴趣相似的园友只会在这个群体产生:我关注的人的粉丝。除我自己之外,目前我一共关注了23名园友,这23名园友一共有22936个唯一粉丝,我对这22936个用户逐一计算了相似度,相似度排名前10的用户及相似度如下:
昵称 |
关注数量 |
共同数量 |
相似度 |
蓝枫叶1938 |
5 |
4 |
0.373001923296126 |
FBI080703 |
3 |
3 |
0.361157559257308 |
鱼非鱼 |
3 |
3 |
0.361157559257308 |
Lauce |
3 |
3 |
0.361157559257308 |
蓝色蜗牛 |
3 |
3 |
0.361157559257308 |
shanyujin |
3 |
3 |
0.361157559257308 |
Mr.Huang |
6 |
4 |
0.340502612303499 |
对世界说你好 |
6 |
4 |
0.340502612303499 |
strucoder |
28 |
8 |
0.31524416249564 |
Mr.Vangogh |
4 |
3 |
0.312771621085612 |
2. 计算对推荐园友的兴趣度
这10名相似用户一共推荐了25名园友,计算得到兴趣度并排序:
排序 |
昵称 |
兴趣度 |
1 |
wolfy |
0.373001923296126 |
2 |
Artech |
0.340502612303499 |
3 |
Cat Chen |
0.340502612303499 |
4 |
WXWinter(冬) |
0.340502612303499 |
5 |
DanielWise |
0.340502612303499 |
6 |
一路前行 |
0.31524416249564 |
7 |
Liam Wang |
0.31524416249564 |
8 |
usharei |
0.31524416249564 |
9 |
CoderZh |
0.31524416249564 |
10 |
博客园团队 |
0.31524416249564 |
11 |
深蓝色右手 |
0.31524416249564 |
12 |
Kinglee |
0.31524416249564 |
13 |
Gnie |
0.31524416249564 |
14 |
riccc |
0.31524416249564 |
15 |
Braincol |
0.31524416249564 |
16 |
滴答的雨 |
0.31524416249564 |
17 |
Dennis Gao |
0.31524416249564 |
18 |
刘冬.NET |
0.31524416249564 |
19 |
李永京 |
0.31524416249564 |
20 |
浪端之渡鸟 |
0.31524416249564 |
21 |
李涛 |
0.31524416249564 |
22 |
阿不 |
0.31524416249564 |
23 |
JK_Rush |
0.31524416249564 |
24 |
xiaotie |
0.31524416249564 |
25 |
Leepy |
0.312771621085612 |
只需要按需要取相似度排名前10名就可以了,不过看起来整个列表的推荐质量都还不错!
具体代码实现:
#-*-?coding:?utf-8?-*-??
'''''?
Created?on?2015-06-22?
?
@author:?Lockvictor?
'''??
import?sys??
import?random??
import?math??
import?os??
from?operator?import?itemgetter????
from?collections?import?defaultdict???
random.seed(0)????
'''''?
users.dat?数据集??
用户id?用户性别?用户年龄?用户职业?用户所在地邮编?
1::F::1::10::48067?
2::M::56::16::70072?
3::M::25::15::55117?
?
movies.dat?数据集?
电影id?电影名称?电影类型??
250::Heavyweights?(1994)::Children's|Comedy?
251::Hunted,?The?(1995)::Action?
252::I.Q.?(1994)::Comedy|Romance?
?
ratings.dat?数据集?
用户id?电影id?用户评分??时间戳?
157::3519::4::1034355415?
157::2571::5::977247494?
157::300::3::977248224?
?
'''??
??
class?UserBasedCF(object):??
????'''''?TopN?recommendation?-?User?Based?Collaborative?Filtering?'''??
??
????#?构造函数,用来初始化??
????def?__init__(self):??
????????#?定义?训练集?测试集?为字典类型??
????????self.trainset?=?{}??
????????self.testset?=?{}??
????????#?训练集用的相似用户数??
????????self.n_sim_user?=?20??
????????#?推荐电影数量??
????????self.n_rec_movie?=?10??
??????????
????????self.user_sim_mat?=?{}??
????????#?表示电影的流行度,有一个看过该电影,流行度+1,没有人看过,流行度的值默认为0??
????????self.movie_popular?=?{}??
????????#?记录电影数量??
????????self.movie_count?=?0??
????????#?sys.stderr?是用来重定向标准错误信息的??
????????print?('相似用户数目为?=?%d'?%?self.n_sim_user,?file=sys.stderr)??
????????print?('推荐电影数目为?=?%d'?%??
???????????????self.n_rec_movie,?file=sys.stderr)??
???
????#?加载文件??
????@staticmethod??
????def?loadfile(filename):??
????????'''''?load?a?file,?return?a?generator.?'''??
????????#?以只读的方式打开传入的文件??
????????fp?=?open(filename,?'r')??
????????#?enumerate()为枚举,i为行号从0开始,line为值??
????????for?i,?line?in?enumerate(fp):??
????????????#?yield?迭代去下一个值,类似next()??
????????????????#?line.strip()用于去除字符串头尾指定的字符。??
????????????yield?line.strip('\r\n')??
????????????#?计数??
????????????if?i?%?100000?==?0:??
????????????????print?('loading?%s(%s)'?%?(filename,?i),?file=sys.stderr)??
????????fp.close()??
????????#?打印加载文件成功??
????????print?('load?%s?succ'?%?filename,?file=sys.stderr)??
??
????#?划分训练集和测试集?pivot用来定义训练集和测试集的比例??
????def?generate_dataset(self,?filename,?pivot=0.7):??
????????'''''?load?rating?data?and?split?it?to?training?set?and?test?set?'''??
????????trainset_len?=?0??
????????testset_len?=?0??
????????for?line?in?self.loadfile(filename):??
????????????#?根据?分隔符?::?来切分每行数据??
????????????user,?movie,?rating,?_?=?line.split('::')??
????????????#?随机数字?如果小于0.7?则数据划分为训练集??
????????????if?random.random()?<?pivot:??
????????????????#?设置训练集字典,key为user,value?为字典?且初始为空??
????????????????self.trainset.setdefault(user,?{})??
????????????????#?以下省略格式如下,集同一个用户id?会产生一个字典,且值为他评分过的所有电影??
????????????????#{'1':?{'914':?3,?'3408':?4,?'150':?5,?'1':?5},?'2':?{'1357':?5}}??
????????????????self.trainset[user][movie]?=?int(rating)??
????????????????trainset_len?+=?1??
????????????else:??
????????????????self.testset.setdefault(user,?{})??
????????????????self.testset[user][movie]?=?int(rating)??
????????????????testset_len?+=?1??
????????#?输出切分训练集成功??
????????print?('划分数据为训练集和测试集成功!',?file=sys.stderr)??
????????#?输出训练集比例??
????????print?('训练集数目?=?%s'?%?trainset_len,?file=sys.stderr)??
????????#?输出测试集比例??
????????print?('测试集数目?=?%s'?%?testset_len,?file=sys.stderr)??
????#?建立物品-用户?倒排表??
????def?calc_user_sim(self):??
????????'''''?calculate?user?similarity?matrix?'''??
????????#?build?inverse?table?for?item-users??
????????#?key=movieID,?value=list?of?userIDs?who?have?seen?this?movie??
????????print?('构建物品-用户倒排表中,请等待......',?file=sys.stderr)??
????????movie2users?=?dict()??
??
????????#?Python?字典(Dictionary)?items()?函数以列表返回可遍历的(键,?值)?元组数组??
????????for?user,?movies?in?self.trainset.items():??
????????????for?movie?in?movies:??
????????????????#?inverse?table?for?item-users??
????????????????if?movie?not?in?movie2users:??
????????????????????#?根据电影id?构造set()?函数创建一个无序不重复元素集??
????????????????????movie2users[movie]?=?set()??
????????????????#?集合中值为用户id??
????????????????#?数值形如??
????????????????#?{'914':?{'1','6','10'},?'3408':?{'1'}?......}??
????????????????movie2users[movie].add(user)??
????????????????#?记录电影的流行度??
????????????????if?movie?not?in?self.movie_popular:??
????????????????????self.movie_popular[movie]?=?0??
????????????????self.movie_popular[movie]?+=?1??
????????print?('构建物品-用户倒排表成功',?file=sys.stderr)??
??
????????#?save?the?total?movie?number,?which?will?be?used?in?evaluation??
????????self.movie_count?=?len(movie2users)??
????????print?('总共被操作过的电影数目为?=?%d'?%?self.movie_count,?file=sys.stderr)??
??
????????#?count?co-rated?items?between?users??
????????usersim_mat?=?self.user_sim_mat??
??
????????print?('building?user?co-rated?movies?matrix...',?file=sys.stderr)??
????????#?令系数矩阵?C[u][v]表示N(u)∩N(v)?,假如用户u和用户v同时属于K个物品对应的用户列表,就有C[u][v]=K??
????????for???
??????????
????????,?users?in?movie2users.items():??
????????????for?u?in?users:??
????????????????usersim_mat.setdefault(u,?defaultdict(int))??
????????????????for?v?in?users:??
????????????????????if?u?==?v:??
????????????????????????continue??
????????????????????usersim_mat[u][v]?+=?1??
????????print?('build?user?co-rated?movies?matrix?succ',?file=sys.stderr)??
??
????????#?calculate?similarity?matrix??
????????print?('calculating?user?similarity?matrix...',?file=sys.stderr)??
????????#?记录计算用户兴趣相似度的次数??
????????simfactor_count?=?0??
????????#?计算用户兴趣相似度复杂度上限值??
????????PRINT_STEP?=?2000000??
????????#?循环遍历usersim_mat?根据余弦相似度公式计算出用户兴趣相似度??
????????for?u,?related_users?in?usersim_mat.items():??
????????????for?v,?count?in?related_users.items():??
????????????????#?以下是公式计算过程??
????????????????usersim_mat[u][v]?=?count?/?math.sqrt(??
????????????????????len(self.trainset[u])?*?len(self.trainset[v]))??
????????????????#计数?并没有什么卵用??
????????????????simfactor_count?+=?1??
????????????????if?simfactor_count?%?PRINT_STEP?==?0:??
????????????????????print?('calculating?user?similarity?factor(%d)'?%??
???????????????????????????simfactor_count,?file=sys.stderr)??
??
????????print?('calculate?user?similarity?matrix(similarity?factor)?succ',??
???????????????file=sys.stderr)??
????????print?('Total?similarity?factor?number?=?%d'?%??
???????????????simfactor_count,?file=sys.stderr)??
????#?根据用户给予推荐结果??
????def?recommend(self,?user):??
????????'''''定义给定K个相似用户和推荐N个电影'''??
????????K?=?self.n_sim_user??
????????N?=?self.n_rec_movie??
????????#?定义一个字典来存储为用户推荐的电影??
????????rank?=?dict()??
????????#?使用watched_movies来表示用户看过的电影列表,后续在做推荐电影需要排除掉用户看过的电影??
????????watched_movies?=?self.trainset[user]??
????????#?sorted()?函数对所有可迭代的对象进行排序操作。?key?指定比较的对象?,reverse=True?降序,这里user_sim_mat好像应该换成usersim_mat??
????????for?similar_user,?similarity_factor?in?sorted(self.user_sim_mat[user].items(),??
??????????????????????????????????????????????????????key=itemgetter(1),?reverse=True)[0:K]:??
????????????for?movie?in?self.trainset[similar_user]:??
????????????????#?判断?如果这个电影?该用户已经看过?则跳出循环??
????????????????if?movie?in?watched_movies:??
????????????????????continue??
????????????????#?记录用户对推荐的电影的兴趣度,这里的兴趣度也是根据该用户与推荐用户的相似度来定的??
????????????????rank.setdefault(movie,?0)??
????????????????rank[movie]?+=?similarity_factor??
????????#?return?the?N?best?movies??
????????return?sorted(rank.items(),?key=itemgetter(1),?reverse=True)[0:N]??
??
????#?计算?准确率,召回率,覆盖率,流行度??
????def?evaluate(self):??
??
????????'''''?print?evaluation?result:?precision,?recall,?coverage?and?popularity?'''??
????????print?('Evaluation?start...',?file=sys.stderr)??
??
????????N?=?self.n_rec_movie??
????????#??varables?for?precision?and?recall??
????????#记录推荐正确的电影数??
????????hit?=?0??
????????#记录推荐电影的总数??
????????rec_count?=?0??
????????#记录测试数据中总数??
????????test_count?=?0??
????????#?varables?for?coverage??
????????all_rec_movies?=?set()??
????????#?varables?for?popularity??
????????popular_sum?=?0??
??
????????for?i,?user?in?enumerate(self.trainset):??
????????????if?i?%?500?==?0:??
????????????????print?('recommended?for?%d?users'?%?i,?file=sys.stderr)??
????????????test_movies?=?self.testset.get(user,?{})??
????????????rec_movies?=?self.recommend(user)??
????????????for?movie,?_?in?rec_movies:??
????????????????if?movie?in?test_movies:??
????????????????????hit?+=?1??
????????????????all_rec_movies.add(movie)??
????????????????popular_sum?+=?math.log(1?+?self.movie_popular[movie])??
????????????rec_count?+=?N??
????????????test_count?+=?len(test_movies)??
????????#?计算准确度??
????????precision?=?hit?/?(1.0?*?rec_count)??
????????#?计算召回率??
????????recall?=?hit?/?(1.0?*?test_count)??
????????#?计算覆盖率??
????????coverage?=?len(all_rec_movies)?/?(1.0?*?self.movie_count)??
????????#计算流行度??
????????popularity?=?popular_sum?/?(1.0?*?rec_count)??
??
????????print?('precision=%.4f\trecall=%.4f\tcoverage=%.4f\tpopularity=%.4f'?%??
???????????????(precision,?recall,?coverage,?popularity),?file=sys.stderr)??
??
??
if?__name__?==?'__main__':??
????ratingfile?=?os.path.join('ml-1m',?'ratings.dat')??
????usercf?=?UserBasedCF()??
????usercf.generate_dataset(ratingfile)??
????usercf.calc_user_sim()??
??
????'''''?
????以下为用户id?为?1688的用户推荐的电影?
????a?=?usercf.recommend("1688")?
????[('1210',?3.1260082382168055),?('2355',?3.0990860017403934),?('1198',?2.692208437663706),?('1527',?2.643102457311887),?('3578',?2.61895974438311),?('1376',?2.469905776632142),?('110',?2.4324588006133383),?('1372',?2.4307454264036528),?('1240',?2.424265305355254),?('32',?2.3926144836965966)]?
????'''??
????usercf.evaluate()??
内容总结
以上是互联网集市为您收集整理的基于用户的协同过滤推荐算法原理-附python代码实现全部内容,希望文章能够帮你解决基于用户的协同过滤推荐算法原理-附python代码实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。