协同过滤算法

协作型过滤

协同过滤是利用集体智慧的一个典型方法。要理解什么是协同过滤 (Collaborative Filtering, 简称CF),首先想一个简单的问题,如果你现在想看个电影,但你不知道具体看哪部,你会怎么做?大部分的人会问问周围的朋友,看看最近有什么好看的电影推荐,而我们一般更倾向于从口味比较类似的朋友那里得到推荐。这就是协同过滤的核心思想。

协同过滤一般是在海量的用户中发掘出一小部分和你品位比较类似的,在协同过滤中,这些用户成为邻居,然后根据他们喜欢的其他东西组织成一个排序的目录推荐给你。

要实现协同过滤,需要以下几个步骤:

  • 搜集偏好
  • 寻找相近用户
  • 推荐物品

搜集偏好

首先,我们要寻找一种表达不同人及其偏好的方法。这里我们用python的嵌套字典来实现。

在本章中所用的数据,是从国外的网站grouplens下载的u.data。该数据总共四列,共分为用户ID、电影ID、用户评分、时间。我们只需根据前三列,生成相应的用户偏好字典。

另外如果想在字典中显示展现电影名,方便分析,也可以根据u.item中电影数据,预先生成电影的数据集。

根据上面两个函数中的一种,到此我们的用户数据集已经构造好了,由于数据量不是非常大,暂时放在内存中即可。
由于以上数据集比较抽象,不方便讲解,至此我们定义一个简单的数据集来讲解一些例子,一个简单的嵌套字典:

寻找相近用户

收集完用户信息后,我们通过一些方法来确定两个用户之间品味的相似程度,计算他们的相似度评价值。有很多方法可以计算,我们在此介绍两套常见的方法:欧几里得距离和皮尔逊相关度。

欧几里得距离

欧几里得距离(euclidea nmetric)(也称欧式距离)是一个通常采用的距离定义,指在m维空间中两个点之间的真实距离,或者向量的自然长度(即该点到原点的距离)。在二维和三维空间中的欧氏距离就是两点之间的实际距离。

数学定义:
已知两点 A = (x_1,x_2,…,x_n)和B = (y_1,y_2,…,y_n),则两点间距离:
2
接下来我们只要把数据集映射为坐标系就可以明显的比较出相似度,以”Snakes on a Plane”和”You, Me and Dupree”两部电影距离,有坐标系如下图:

计算上图中Toby和Mick LaSalle的相似度:

from math import sqrt
sqrt(pow( 4.5-4 , 2 ) + pow( 1 – 2 , 2))
1.118033988749895

上面的式子计算出了实际距离值,但在实际应用中,我们希望相似度越大返回的值越大,并且控制在0~1之间的值。为此,我们可以取函数值加1的倒数(加1是为了防止除0的情况):

1/(1+sqrt(pow( 4.5-4 , 2 ) + pow( 1 – 2 , 2)))
0.4721359549995794

接下来我们就可以封装一个基于欧几里得距离的相似度评价,具体python实现如下:

基于测试数据集critics,则可以计算两个人的相似度值为:

sim_distance( critics , ‘Toby’, ‘Mick LaSalle’ )
0.307692307692

皮尔逊相关度

皮尔逊相关系数是一种度量两个变量间相关程度的方法。它是一个介于 1 和 -1 之间的值,其中,1 表示变量完全正相关, 0 表示无关,-1 表示完全负相关。

数学公式

1

与欧几里得距离不同,我们根据两个用户来建立笛卡尔坐标系,根据用户对相同电影的评分来建立点,如下图:

在图上,我们还可以看到一条线,因其绘制的原则是尽可能的接近图上所有点,故该线也称为最佳拟合线。用皮尔逊方法进行评价时,可以修正“夸大值”部分,例如某人对电影的要求更为严格,给出分数总是偏低。

python代码实现:

最后根据critics的数据计算Gene Seymour和Lisa Rose的相关度:

recommendations.sim_pearson(recommendations.critics,’Gene Seymour’,’Lisa Rose’)

为评论者打分

到此,我们就可以根据计算出用户之间的相关度,并根据相关度来生成相关度列表,找出与用户口味相同的其他用户。

推荐物品

对于用户来说,找出与他具有相似爱好的人并不重要,主要是为他推荐他可能喜欢的物品,所以我们还需要根据用户间相似度进一步计算。例如为Toby推荐,由于数据不多,我们取得所有推荐者的相似度,再乘以他们对电影的评价,得出该电影对于Toby的推荐值,也可以认为是Toby可能为电影打的分数。如下图:

我们通过计算其他用户对某个Toby没看过电影的加权和来得到总权重,最后除以相似度和,是为了防止某一电影被看过的多,总和会更多的影响,也称“归一化”处理。

基于物品的协同过滤

以上所讲的都是基于用户间相似的推荐,下面我们看看基于物品的推荐。

同样,先构造数据集,即以物品为key的字典,格式为{电影:{用户:评分,用户:评分}}

计算物品间的相似度,物品间相似的变化不会像人那么频繁,所以我们可以构造物品间相似的集合,存成文件重复利用:

基于物品的推荐值计算,通过Toby已看影片的评分,乘以未看影片之间的相似度,来获取权重。最后归一化处理如下图:

源码

思考

  1. UserCF和ItemCF的比较
  2. 归一化处理的更合适方法
  3. 与频繁模式挖掘的区别
1 6 收藏 1 评论

相关文章

可能感兴趣的话题



直接登录
最新评论
跳到底部
返回顶部