基于协同过滤的推荐算法及代码实现Word文件下载.doc
- 文档编号:726340
- 上传时间:2023-04-29
- 格式:DOC
- 页数:34
- 大小:1.51MB
基于协同过滤的推荐算法及代码实现Word文件下载.doc
《基于协同过滤的推荐算法及代码实现Word文件下载.doc》由会员分享,可在线阅读,更多相关《基于协同过滤的推荐算法及代码实现Word文件下载.doc(34页珍藏版)》请在冰点文库上搜索。
归一化:
如前面讲到的,在计算用户对物品的喜好程度时,可能需要对不同的行为数据进行加权。
但可以想象,不同行为的数据取值可能相差很大,比如,用户的查看数据必然比购买数据大的多,如何将各个行为的数据统一在一个相同的取值范围中,从而使得加权求和得到的总体喜好更加精确,就需要我们进行归一化处理。
最简单的归一化处理,就是将各类数据除以此类中的最大值,以保证归一化后的数据取值在
[0,1]
范围中。
进行的预处理后,根据不同应用的行为分析方法,可以选择分组或者加权处理,之后我们可以得到一个用户偏好的二维矩阵,一维是用户列表,另一维是物品列表,值是用户对物品的偏好,一般是
或者
[-1,1]
的浮点数值。
(2)找到相似的用户或物品
当已经对用户行为进行分析得到用户喜好后,我们可以根据用户喜好计算相似用户和物品,然后基于相似用户或者物品进行推荐,这就是最典型的CF
的两个分支:
基于用户的CF
和基于物品的CF。
这两种方法都需要计算相似度,下面我们先看看最基本的几种计算相似度的方法。
相似度的计算
关于相似度的计算,现有的几种基本方法都是基于向量(Vector)的,其实也就是计算两个向量的距离,距离越近相似度越大。
在推荐的场景中,在用户-物品偏好的二维矩阵中。
我们可以将一个用户对所有物品的偏好作为一个向量来计算用户的相似度;
或者将所有用户对某个物品的偏好作为一个向量来计算物品之间的相似度。
下面我们详细介绍几种常用的相似度计算方法:
相似邻居的计算
介绍完相似度的计算方法,下面我们看看如何根据相似度找到用户-
物品的邻居,常用的挑选邻居的原则可以分为两类:
下图给出了二维平面空间上点集的示意图。
固定数量的邻居:
K-neighborhoods
或者Fix-sizeneighborhoods
不论邻居的“远近”,只取最近的K
个,作为其邻居。
如上图中的A,假设要计算点1
的5-邻居,那么根据点之间的距离,我们取最近的5
个点,分别是点2,点3,点4,点7
和点5。
但很明显我们可以看出,这种方法对于孤立点的计算效果不好,因为要取固定个数的邻居,当它附近没有足够多比较相似的点,就被迫取一些不太相似的点作为邻居,这样就影响了邻居相似的程度,比如上图中,点1
和点5
其实并不是很相似。
基于相似度门槛的邻居:
Threshold-basedneighborhoods
与计算固定数量的邻居的原则不同,基于相似度门槛的邻居计算是对邻居的远近进行最大值的限制,落在以当前点为中心,距离为K
的区域中的所有点都作为当前点的邻居,这种方法计算得到的邻居个数不确定,但相似度不会出现较大的误差。
如上图中的B,从点1
出发,计算相似度在K
内的邻居,得到点2,点3,点4
和点7,这种方法计算出的邻居的相似度程度比前一种好,尤其是对孤立点的处理。
(3)计算推荐
经过前期的计算已经得到了相邻用户和相邻物品,下面介绍如何基于这些信息为用户进行推荐。
本系列的上一篇综述文章已经简要介绍过基于协同过滤的推荐算法可以分为基于用户的CF
和基于物品的CF,下面我们深入这两种方法的计算方法,使用场景和优缺点。
基于用户的CF(UserCF)
的基本思想相当简单,基于用户对物品的偏好找到相邻邻居用户,然后将邻居用户喜欢的推荐给当前用户。
计算上,就是将一个用户对所有物品的偏好作为一个向量来计算用户之间的相似度,找到K
邻居后,根据邻居的相似度权重以及他们对物品的偏好,预测当前用户可能喜欢的物品,计算得到一个排序的物品列表作为推荐(排序列表中每个物品都有相应的预测值)。
下图给出了一个例子,对于用户A,根据用户的历史偏好,这里只计算得到一个邻居用户C,然后将用户C
喜欢的物品D
推荐给用户A。
基于物品的CF(ItemCF)
基于物品的CF
的原理和基于用户的CF
类似,只是在计算邻居时采用物品本身,而不是从用户的角度,即基于用户对物品的偏好找到相似的物品,然后根据用户的历史偏好,推荐相似的物品给他。
从计算的角度看,就是将所有用户对某个物品的偏好作为一个向量来计算物品之间的相似度,得到物品的相似物品后,根据用户历史的偏好预测当前用户还没有表示偏好的物品,计算得到一个排序的物品列表作为推荐。
下图给出了一个例子,对于物品A,根据所有用户的历史偏好,喜欢物品A
的用户都喜欢物品C,得出物品A
和物品C
比较相似,而用户C
喜欢物品A,那么可以推断出用户C
可能也喜欢物品C。
UserCFvsItemCF
前面介绍了UserCF
和ItemCF
的基本原理,下面我们分几个不同的角度深入看看它们各自的优缺点和适用场景:
计算复杂度
ItemCF和UserCF
是基于协同过滤推荐的两个最基本的算法,UserCF
是很早以前就提出来了,ItemCF
是从Amazon
的论文和专利发表之后(2001
年左右)开始流行,大家都觉得ItemCF
从性能和复杂度上比UserCF
更优,其中的一个主要原因就是对于一个在线网站,用户的数量往往大大超过物品的数量,同时物品的数据相对稳定,因此计算物品的相似度不但计算量较小,同时也不必频繁更新。
但我们往往忽略了这种情况只适应于提供商品的电子商务网站,对于新闻,博客或者微内容的推荐系统,情况往往是相反的,物品的数量是海量的,同时也是更新频繁的,所以单从复杂度的角度,这两个算法在不同的系统中各有优势,推荐引擎的设计者需要根据自己应用的特点选择更加合适的算法。
适用场景
在非社交网络的网站中,内容内在的联系是很重要的推荐原则,它比基于相似用户的推荐原则更加有效。
比如在购书网站上,当你看一本书的时候,推荐引擎会给你推荐相关的书籍,这个推荐的重要性远远超过了网站首页对该用户的综合推荐。
可以看到,在这种情况下,ItemCF
的推荐成为了引导用户浏览的重要手段。
同时ItemCF
便于为推荐做出解释,在一个非社交网络的网站中,给某个用户推荐一本书,同时给出的解释是某某和你有相似兴趣的人也看了这本书,这很难让用户信服,因为用户可能根本不认识那个人;
但如果解释说是因为这本书和你以前看的某本书相似,用户可能就觉得合理而采纳了此推荐。
相反的,在现今很流行的社交网络站点中,UserCF
是一个更不错的选择,UserCF
加上社会网络信息,可以增加用户对推荐解释的信服程度。
推荐多样性和精度
研究推荐引擎的学者们在相同的数据集合上分别用UserCF
计算推荐结果,发现推荐列表中,只有50%
是一样的,还有50%
完全不同。
但是这两个算法居然有相似的精度,所以可以说,这两个算法是很互补的。
关于推荐的多样性,有两种度量方法:
第一种度量方法是从单个用户的角度度量,就是说给定一个用户,查看系统给出的推荐列表是否多样,也就是要比较推荐列表中的物品之间两两的相似度,不难想到,对这种度量方法,ItemCF
的多样性显然不如UserCF
的好,因为ItemCF
的推荐就是和以前看的东西最相似的。
第二种度量方法是考虑系统的多样性,也被称为覆盖率
(Coverage),它是指一个推荐系统是否能够提供给所有用户丰富的选择。
在这种指标下,ItemCF
的多样性要远远好于UserCF,
因为UserCF
总是倾向于推荐热门的,从另一个侧面看,也就是说,ItemCF
的推荐有很好的新颖性,很擅长推荐长尾里的物品。
所以,尽管大多数情况,ItemCF
的精度略小UserCF,但如果考虑多样性,ItemCF
却比UserCF
好很多。
如果你对推荐的多样性还心存疑惑,那么下面我们再举个实例看看
UserCF
的多样性到底有什么差别。
首先,假设每个用户兴趣爱好都是广泛的,喜欢好几个领域的东西,不过每个用户肯定也有一个主要的领域,对这个领域会比其他领域更加关心。
给定一个用户,假设他喜欢3
个领域A、B、C,A
是他喜欢的主要领域,这个时候我们来看UserCF
倾向于做出什么推荐:
如果用UserCF,
它会将A,B,C
三个领域中比较热门的东西推荐给用户;
而如果用ItemCF,它会基本上只推荐A
领域的东西给用户。
所以我们看到因为UserCF
只推荐热门的,所以它在推荐长尾里项目方面的能力不足;
而ItemCF
只推荐A
领域给用户,这样他有限的推荐列表中就可能包含了一定数量的不热门的长尾物品,同时ItemCF
的推荐对这个用户而言,显然多样性不足。
但是对整个系统而言,因为不同的用户的主要兴趣点不同,所以系统的覆盖率会比较好。
从上面的分析,可以很清晰的看到,这两种推荐都有其合理性,但都不是最好的选择,因此他们的精度也会有损失。
其实对这类系统的最好选择是,如果系统给这个用户推荐30
个物品,既不是每个领域挑选10
个最热门的给他,也不是推荐30
个A
领域的给他,而是比如推荐15
领域的给他,剩下的15
个从B,C
中选择。
所以结合UserCF
是最优的选择,结合的基本原则就是当采用ItemCF
导致系统对个人推荐的多样性不足时,我们通过加入UserCF
增加个人推荐的多样性,从而提高精度,而当因为采用UserCF
而使系统的整体多样性不足时,我们可以通过加入ItemCF
增加整体的多样性,同样可以提高推荐的精度。
用户对推荐算法的适应度
前面我们大部分都是从推荐引擎的角度考虑哪个算法更优,但其实我们更多的应该考虑作为推荐引擎的最终使用者——应用用户对推荐算法的适应度。
对于UserCF,推荐的原则是假设用户会喜欢那些和他有相同喜好的用户喜欢的东西,但如果一个用户没有相同喜好的朋友,那UserCF
的算法的效果就会很差,所以一个用户对的CF
算法的适应度是和他有多少共同喜好用户成正比的。
ItemCF算法也有一个基本假设,就是用户会喜欢和他以前喜欢的东西相似的东西,那么我们可以计算一个用户喜欢的物品的自相似度。
一个用户喜欢物品的自相似度大,就说明他喜欢的东西都是比较相似的,也就是说他比较符合ItemCF
方法的基本假设,那么他对ItemCF
的适应度自然比较好;
反之,如果自相似度小,就说明这个用户的喜好习惯并不满足ItemCF
方法的基本假设,那么对于这种用户,用ItemCF
方法做出好的推荐的可能性非常低。
通过以上的介绍,相信大家已经对协同过滤推荐的各种方法,原则,特点和适用场景有深入的了解,下面我们就进入实战阶段。
推荐电影的例子
下面,我们通过一个实际的小例子来完成这个过程,这个例子是关于用户电影的。
用户的历史操作
完成协同过滤这个算法的第一步就是你要知道谁喜欢什么。
本例子中,不仅知道哪个用户喜欢哪个电影,并且还用具体的数字来量化了,也就是每人对电影有着评分。
用一个字典表示,具体代码如下:
[python]
viewplaincopy
1.#一个字典,第一个key是人名,value是又是一个字典,字典里面key是电影名,value是评分
2.critics={'
Lisa
Rose'
:
{'
Lady
in
the
Water'
2.5,
'
Snakes
on
a
Plane'
3.5,
3.
Just
My
Luck'
3.0,
Superman
Returns'
You,
Me
and
Dupree'
4.
The
Night
Listener'
3.0},
5.'
Gene
Seymour'
6.
1.5,
5.0,
7.
3.5},
8.'
Michael
Phillips'
9.
4.0},
10.'
Claudia
Puig'
11.
4.5,
4.0,
12.
2.5},
13.'
Mick
LaSalle'
14.
2.0,
15.
2.0},
16.'
Jack
Matthews'
17.
18.'
Toby'
4.5,'
1.0,'
4.0}}
用数字代表行为是一个非常关键的手段。
这样才能进行编程,如下图所示:
基于用户的协同过滤
协同过滤:
就是找到和目标用户有着相同爱好的人,然后把与目标用户有相同爱好的人喜欢的物品推荐给该目标用户。
本文主要就是讲这个算法。
计算用户相似度
那么现在我们已经有了用户数据了,下一步就是:
找出爱好相同的用户。
专业术语:
寻找相近用户或者相似度高的用户。
下面介绍三种计算相似度的体系:
·
欧几里得距离
皮尔逊相关度
Tanimoto系数
欧几里得距离
实际上,欧几里得距离非常直观,对于某两部电影,所有的用户都对其有着评分,我们以一个电影为x轴、一个电影为y轴,将每个人的对两个电影的评分画在坐标系中,直接考察每对用户的直线距离,距离近的相似度高。
比如电影:
dupree和snake,可以画出的图如下所示:
虽然这幅图只使用了二维坐标系,但实际上三维、四维都是同样的道理。
求两点间直线的距离,我相信大家都知道怎么算吧?
三维、四维、n维的其实和二维的一个道理,都是两点差的平方和,再开方。
注意:
两点是指两个用户。
在二维中就有x,y轴两个差值的平方和,而在n维中,就是n个差值的平方和。
在本题中,对于两用户,必须是共同评过分的电影才有计算的意义。
求出平方和再开方就是直线距离了。
现在两用户越相邻距离越小,但是我们希望得到的是用户越相邻,数值越大,(0-1之间),故我们对最后的结果加1再求倒数就可以了。
试想:
如果两点重合,距离为1,再求倒数则是0被除,所以必须要加一。
而如果两点距离越远,求倒数后值越小,符合我们的要求。
解释清楚之后,让我们来看一看代码:
1.from
math
import
sqrt
2.#利用欧几里得计算两个人之间的相似度
3.def
sim_distance(prefs,person1,person2):
#首先把这个两个用户共同拥有评过分电影给找出来,方法是建立一个字典,字典的key电影名字,电影的值就是1
5.
si={}
for
item
prefs[person1]:
if
prefs[person2]:
8.
si[item]=1
#如果亮着没有共同之处
10.
len(si)==0:
return
0
13.
#计算所有差值的平方和
sum_of_squares=sum([pow(prefs[person1][item]-prefs[person2][item],2)
prefs[person1]
prefs[person2]])
16.
1/(1+sqrt(sum_of_squares))
18.
19.
20.print
sim_distance(critics,'
'
)
其中最后一句代码可以计算两个实例。
皮尔逊相关度评价
下面介绍的是皮尔逊相关度评价。
用图讲是非常清晰的,我们用某两个用户作为x、y轴,然后以用户对电影的评分,画出每一点来。
如下图所示:
上图中superman电影的坐标为(3.0,5.0),这是因为用户GeneSeymour对其的评分为5,而micklasalle的评分为3.考虑所有的点:
我们画一条线,叫最佳拟合线:
画的原则是尽可能地靠近图中所有的坐标点。
就是上图的线,试想一种情况就是两个用户的评分完成一样,我们将得到一条线:
所有点都在线上,而且线的角度是45度。
这时,两个用户的兴趣完全相同,我们称之为1,我想别的拟合线与之对比即可看出差距吧。
来看一种情况较好的时候:
上图的相关系数为0.4,下图为0.75。
上面有点讲出了推导原理的感觉,但是实际上我们求的就是皮尔逊相关系数,这是一个数学上的公式,其最后得到的结果是一个-1到1的之间的小数。
-1称之为负相关:
表示一个变量的值越大,另一个变量的值会反而越来越小。
计算过程首先要找出两位评论者曾经评价过的物品,然后计算两者的评分总和平方和,并求出评分的乘积之和。
利用公式算出pearson相关系数,公式如下:
其中X和Y分别是个数相同的数组或者是列表(python),相当于算出了两个数组之间的pearson相关度。
我们在本题的实际的应用中也是如此,我们算的时候,是根据两个用户对电影的打分来计算的,打分组成了数组列表。
请看代码:
1.#返回两个人的皮尔逊相关系数
2.def
sim_pearson(prefs,p1,p2):
prefs[p1]:
prefs[p2]:
#得到列表元素的个数
n=len(si)
#如果两者没有共同之处,则返回0
n==0:
1
#对共同拥有的物品的评分,分别求和
sum1=sum([prefs[p1][it]
it
si])
20.
sum2=sum([prefs[p2][it]
21.
22.
23.
#求平方和
24.
sum1Sq=sum([pow(prefs[p1][it],2)for
25.
sum2Sq=sum([pow(prefs[p2][it],2)for
26.
27.
28.
#求乘积之和
29.
pSum=sum([prefs[p1][it]*prefs[p2][it]
30.
31.
32.
#计算皮尔逊评价值
33.
num=pSum-(sum1*sum2/n)
34.
den=sqrt((sum1Sq-pow(sum1,2)/n)*(sum2Sq-pow(sum2,2)/n))
35.
36.
den
==
0:
37.
38.
39.
r=num/den
40.
41.
42.
return
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 协同 过滤 推荐 算法 代码 实现