基于用户的协同过滤算法

jack

什么是推荐算法


　　推荐算法最早在1992年就提出来了，但是火起来实际上是最近这些年的事情，因为互联网的爆发，有了更大的数据量可以供我们使用，推荐算法才有了很大的用武之地。


　　最开始，所以我们在网上找资料，都是进yahoo，然后分门别类的点进去，找到你想要的东西，这是一个人工过程，到后来，我们用google，直接搜索自己需要的内容，这些都可以比较精准的找到你想要的东西，但是，如果我自己都不知道自己要找什么肿么办？最典型的例子就是，如果我打开豆瓣找电影，或者我去买说，我实际上不知道我想要买什么或者看什么，这时候推荐系统就可以派上用场了。


　　推荐算法的条件


　　推荐算法从92年开始，发展到现在也有20年了，当然，也出了各种各样的推荐算法，但是不管怎么样，都绕不开几个条件，这是推荐的基本条件


　　根据和你共同喜好的人来给你推荐


　　根据你喜欢的物品找出和它相似的来给你推荐


　　根据你给出的关键字来给你推荐，这实际上就退化成搜索算法了


　　根据上面的几种条件组合起来给你推荐


　　实际上，现有的条件就这些啦，至于怎么发挥这些条件就是八仙过海各显神通了，这么多年沉淀了一些好的算法，今天这篇文章要讲的基于用户的协同过滤算法就是其中的一个，这也是最早出现的推荐算法，并且发展到今天，基本思想没有什么变化，无非就是在处理速度上，计算相似度的算法上出现了一些差别而已。


　　基于用户的协同过滤算法


　　我们先做个词法分析基于用户说明这个算法是以用户为主体的算法，这种以用户为主体的算法比较强调的是社会性的属性，也就是说这类算法更加强调把和你有相似爱好的其他的用户的物品推荐给你，与之对应的是基于物品的推荐算法，这种更加强调把和你你喜欢的物品相似的物品推荐给你。


　　然后就是协同过滤了，所谓协同就是大家一起帮助你啦，然后后面跟个过滤，就是大家是商量过后才把结果告诉你的，不然信息量太大了。。


　　所以，综合起来说就是这么一个算法，那些和你有相似爱好的小伙伴们一起来商量一下，然后告诉你什么东西你会喜欢。


　　算法描述


　　相似性计算


　　我们尽量不使用复杂的数学公式，一是怕大家看不懂，难理解，二是我是用mac写的blog,公式不好画，太麻烦了。。


　　所谓计算相似度，有两个比较经典的算法


　　Jaccard算法，就是交集除以并集，详细可以看看我这篇文章。


　　余弦距离相似性算法，这个算法应用很广，一般用来计算向量间的相似度，具体公式大家google一下吧，或者看看这里


　　各种其他算法，比如欧氏距离算法等等。


　　不管使用Jaccard还是用余弦算法，本质上需要做的还是求两个向量的相似程度，使用哪种算法完全取决于现实情况。


　　我们在本文中用的是余弦距离相似性来计算两个用户之间的相似度。


　　与目标用户最相邻的K个用户


　　我们知道，在找和你兴趣爱好相似的小伙伴的时候，我们可能可以找到几百个，但是有些是好基友，但有些只是普通朋友，那么一般的，我们会定一个数K，和你最相似的K个小伙伴就是你的好基友了，他们的爱好可能和你的爱好相差不大，让他们来推荐东西给你（比如肥皂）是最好不过了。


　　何为和你相似呢？简单的说就是，比如你喜欢macbook,iphone,ipad，A小伙伴喜欢macbook,iphone,note2,小米盒子,肥皂，蜡烛,B小伙伴喜欢macbook,iphone,ipad,肥皂,润肤霜,C女神喜欢雅诗兰黛,SK2,香奈儿，D屌丝喜欢ipad,诺基亚8250,小霸王学习机那么很明显，B小伙伴和你更加相似，而C女神完全和你不在一个档次上，那我们推荐的时候会把肥皂推荐给你，因为我们觉得肥皂可能最适合你。


　　那么，如何找出这K个基友呢？最直接的办法就是把目标用户和数据库中的所有用户进行比较，找出和目标用户最相似的K个用户，这就是好基友了。


　　这么做理论上是没什么问题的，但是当数据量巨大的时候，计算K个基友的时间将会非常长，而且你想想就知道，数据库中的大部分用户其实和你是没有什么交集的，所没必要计算所有用户了，只需要计算和你有交集的用户就行了。


　　要计算和你有交集的用户，就要用到物品到用户的反查表，什么是反查表呢？很简单，还是是上面那个AB小伙伴和C女神的例子，反查表就是喜欢macbook的有你，A，B，喜欢iphone的有你，B。。。就是喜欢某些物品的用户，有了这个表，我们就可以看出来，和你有关系的用户就只有A和B，D了，而C女神和你没有任何交集，所以不用去想C了。


　　这样，我们有了A和B,D，然后就分别计算A和B,D与你的相似度，不管用哪个相似性公式，我们算出来都是B和你更相似(在这个例子中，一般会用Jaccard来计算，因为这些向量不是特别好余弦化)，但如果此时我们的K设定为2，那么我们就得出了与你最相邻的基友是B和A。


　　这就是与目标用户最相邻的K个用户的计算。


　　通过这K个用户来推荐商品了


　　好了，你的好基友我们也算出来了，接下来要向你推荐商品了。但是我们可推荐的商品有小米盒子，note2，蜡烛，润肤霜，肥皂这么四种，到底哪种才是你需要的呢？这里的算法就比较广泛了，我们可以不排序，都一股脑推荐给你，但这明显可能有些你不怎么感兴趣，我们也可以做一些处理，假如我们算出来A和你的相似度是25%，B和你的相似度是80%，那么对于上面这些产品，我们的推荐度可以这么来算


　　小米盒子:1*0.25=0.25


　　note2:1*0.25=0.25


　　蜡烛:1*0.25=0.25


　　润肤霜:1*0.8=0.8


　　肥皂:1*0.8+1*0.25=1.05


　　这样就一目了然了，很明显，我们会首先把肥皂推荐给你，这个可能是你最需要的，其次是润肤霜，然后才是蜡烛，小米盒子和note2。


　　当然，你可以把上述结果归一化或者用其他你觉得合适的方式来计算推荐度，不管怎么算，推荐度还是得和基友与你相似度有关系，就是那个0.8和0.25一定要用上，不然前面白算了。


　　算法总结


　　好了，通过这个例子，你大概知道了为什么会推荐肥皂给你了吧，这就是基于用户的协同推荐算法的描述，总结起来就是这么几步


　　计算其他用户和你的相似度，可以使用反差表忽略一部分用户


　　根据相似度的高低找出K个与你最相似的邻居


　　在这些邻居喜欢的物品中，根据邻居与你的远近程度算出每一件物品的推荐度


　　根据每一件物品的推荐度高低给你推荐物品。


　　比如上面那个例子，首先，我们通过反查表忽略掉了C女神，然后计算出A和B,D与你的相似度，然后根据K=2找出最相似的邻居A和B，接着根据A,B与你相似度计算出每件物品的推荐度并排序，最后根据排好序的推荐度给你推荐商品。


　　怎么样，是不是很简单啊。


　　算法存在的问题


　　这个算法实现起来也比较简单，但是在实际应用中有时候也会有问题的。


　　比如一些非常流行的商品可能很多人都喜欢，这种商品推荐给你就没什么意义了，所以计算的时候需要对这种商品加一个权重或者把这种商品完全去掉也行。


　　再有，对于一些通用的东西，比如买书的时候的工具书，如现代汉语词典，新华字典神马的，通用性太强了，推荐也没什么必要了。


　　这些都是推荐系统的脏数据，如何去掉脏数据，这是数据预处理的时候事情了，这里就不多说了。


　　来个实战的吧


　　说了这么多，肥皂也推荐了，那么我们来点实际的，我这里下载了movieLens的数据集，至于这个集合是什么大家google一下，反正很多地方用来做测试算法的数据，这个数据集里面有很多用户对于电影的打分，我们的需求是随便输入一个用户，然后根据协同算法，给他推荐一些个电影。


　　由于用户给电影打分有好有坏[1到5分]，而我们上面的例子中都是说的喜欢某件物品而没有说不喜欢的情况，所以首先，我们要把数据处理一下，简单的来做，我们可以认为3分以上的话代表这个用户喜欢这个电影，否则就是不喜欢，这样显得有点太死板了，我们也可以这么来定义，比如用户A对30部电影打分了，首先求出他打分的平均值，然后高于这个平均值的我们觉得用户喜欢这个电影，否则认为他不喜欢。


　　好了，用户的喜欢与不喜欢的问题解决了。下面就可以开始算法了，代码不全贴出来了，贴个流程吧，具体代码可以去看我的github
#读取文件数据
test_contents=readFile(file_name)
#文件数据格式化成二维数组 List[[用户id,电影id,电影评分]...]
test_rates=getRatingInformation(test_contents)
#格式化成字典数据
#    1.用户字典：dic[用户id]=[(电影id,电影评分)...]
#    2.电影用户反查表：dic[电影id]=[用户id1,用户id2...]
test_dic,test_item_to_user=createUserRankDic(test_rates)
#寻找邻居   
neighbors=calcNearestNeighbor(userid,test_dic,test_item_to_user)[:k]
#计算推荐列表
recommend_dic={}
for neighbor in neighbors:
    neighbor_user_id=neighbor[1]
    movies=test_dic[neighbor_user_id]
    for movie in movies:
  if movie[0] not in recommend_dic:
   recommend_dic[movie[0]]=neighbor[0]
  else:
   recommend_dic[movie[0]]+=neighbor[0]
#建立推荐列表
recommend_list=[]
for key in recommend_dic:
    recommend_list.append([recommend_dic[key],key]
recommend_list.sort(reverse=True)

对于随便输入一个用户，我们得到以下这个推荐结果
    movie name    release  
=======================================================
Contact (1997)    11-Jul-1997   
Scream (1996)  20-Dec-1996   
Liar Liar (1997)  21-Mar-1997   
Saint, The (1997)    14-Mar-1997   
English Patient, The (1996)   15-Nov-1996   
Titanic (1997)    01-Jan-1997   
Air Force One (1997)    01-Jan-1997   
Star Wars (1977)  01-Jan-1977   
Conspiracy Theory (1997)   08-Aug-1997   
Toy Story (1995)  01-Jan-1995   
Fargo (1996)   14-Feb-1997

　　多输入几个用户你就会发现，像Titanic，StarWars这种超级热门的电影，只要你选的这个用户没看过，推荐系统就一定会推荐给你，这就是我们前面说的脏数据，实际系统中这种数据是需要处理掉得。我们这篇文章只做算法讲解，就不去管这些东西了。