如何使用MapReduce实现基于物品的协同过滤(1)

2014-11-20

基于物品的协同过滤已经介绍了基于物品的协同过滤的基本思路。
MovieLens数据集介绍介绍了MovieLens数据集,我们可以把MovieLens 100k拿过来当数据集。个人认为这个数据集有一个很好的特征,就是用户和电影的ID均是从1开始的连续整数。本文中,矩阵的行号和列号均从1开始。

好了,现在我们的目标是为某个用户推荐电影。本文介绍的方法是基于物品的协同过滤中的一种,先讲理论基础,再讲如何MapReduce。

理论基础


这个算法的最初来源我没有去考察,和我之前接触的item-cf不太相同,在“参考”部分的几篇博客中都有提到。

用户对电影的评分在1和5之间,我们认为0代表没有评分。假设数据集中有m部电影,矩阵S[1..m, 1..m]存储电影和电影之间的相似程度,比如S[1,5]是电影1和电影5之间的相似程度。假如共有7部电影,其相似度矩阵S为:

      [1]   [2]   [3]   [4]   [5]   [6]   [7]
[1]   5     3     4     4     2     2     1
[2]   3     3     3     2     1     1     0
[3]   4     3     4     3     1     2     0
[4]   4     2     3     4     2     2     1
[5]   2     1     1     2     2     1     1
[6]   2     1     2     2     1     2     0
[7]   1     0     0     1     1     0     1

很明显,这是一个实对称矩阵。
如果用户1对这7部电影的评分矩阵R是:

      1
[1] 2.0
[2] 0.0
[3] 0.0
[4] 4.0
[5] 4.5
[6] 0.0
[7] 5.0

可以看到,用户1没有看过电影2、3、6,需要从2、3、6中找出一部推荐给用户1。

电影2与其他电影的相似度矩阵是:

3     3     3     2     1     1     0

将该矩阵与R相乘,得到推荐矩阵H(matlab代码):

>> [3 3 3 2 1 1 0]*[2.0; 0.0; 0.0; 4.0; 4.5; 0.0; 5.0]

ans =

   18.5000

18.5就是向用户1推荐电影2的可能性。值越大,可能性越大。

同样的,向用户1推荐电影3、6的可能性分别是24.5、16.5。

由于24.5>18.5>16.5,所以应该向用户推荐电影3。

在真实场景中,可以直接将S乘以R,得到对用户1而言所有电影的推荐值。这个结果是一个矩阵,也是一个列向量。然后去掉结果中用户1看过的电影即可。另外,矩阵R也可以扩充为多个用户对电影的评价,只要每一列代表一个用户对所有电影的评价即可。

基本思路就是这样,不过还有一个问题没有解决,如何得到相似度矩阵S?在本文中,相似度矩阵来自同现矩阵,相似度矩阵也等于同现矩阵。同现矩阵中的每个值代表着这两部电影同时被多少用户看过。比如,由于电影1和2同时被3个人看过,所以S[1,2]的值为3;电影1被5个用户看过,所以S[1,1]的值是5。

使用MapReduce实现


MovieLens 数据集中每一行的格式可以看作是:

user_id | item_id | rating 

其中,时间戳被我省略了。

建立同现矩阵:

第1次MapReduce:

Map的输入:

user_id | item_id | rating 

Map的输出:

key: user_id
value: item_id

Reduce的输入:

key: user_id
values: item_id1, item_id2, ....

Reduce的输出:

key: item_id1, item_id1   value: 1
key: item_id1, item_id2   value: 1
key: item_id2, item_id1   value: 1
key: item_id2, item_id2   value: 1
......

第2次MapReduce:

Map的输入:

item_id_x, item_id_y    1

Map的输出:

key: item_id_x, item_id_y
value: 1

Reduce的输入:

key: item_id_x, item_id_y
values: 1, 1, 1, ......

Reduce的输出:

key: item_id_x, item_id_y
value: sum(values)

现在得到同现矩阵了。

将同现矩阵与评分矩阵相乘得到推荐矩阵

这个可以参考我的这篇文章:如何使用MapRedue实现矩阵乘法

过滤掉用户评价过的电影

将评分矩阵中等于0的值改成1,大于0的改成0,得到过滤矩阵F。推荐矩阵H和过滤矩阵F具有相同的大小。将推荐矩阵H与过滤矩阵F点乘,去掉结果中值为0的元素。

例如:

比如评分矩阵是:

3, 3, 0, 0
2, 4, 5, 0
4, 3, 0, 4

过滤矩阵就是:

0, 0, 1, 1
0, 0, 0, 1
0, 0, 1, 0

假设推荐矩阵为(这个矩阵是造出来的,不是计算得到的):

3.2, 3.7, 6.0, 3.0
1.2, 4.3, 5.0, 3.0
4.3, 2.3, 1.0, 3.4

然后根据过滤矩阵,得到:

0.0, 0.0, 6.0, 3.0
0.0, 0.0, 0.0, 3.0
0.0, 0.0, 1.0, 0.0

补充:如何将矩阵的稀疏表示转换为非稀疏表示


若矩阵为:

2 3  
4 0
1 0  

稀疏形式(每行依次是<行,列,值>):

1,1, 2 
1,2, 3  
2,1, 4  
3,1, 1  

已知矩阵大小为2×3,可以基于稀疏矩阵生成非稀疏的矩阵:

1,1, 2  
1,2, 3  
2,1, 4  
2,2, 0 
3,1, 1 
3,2, 0 

这个过程可以是这样的:

先生成2×3的零矩阵(非MapReduce):

1,1, 0  
1,2, 0  
2,1, 0  
2,2, 0 
3,1, 0 
3,2, 0 

将零矩阵与已有的稀疏矩阵合并:

1,1, 0  
1,2, 0  
2,1, 0  
2,2, 0 
3,1, 0 
3,2, 0 
1,1, 2 
1,2, 3  
2,1, 4  
3,1, 1 

接下来,MapReduce:

Map的输出:key是(行,列),value是
Reduce接收的输入中,每一个key有1个或者2个value构成的value_list,其输出:key是(行,列),value是max(value_list)

非稀疏形式就得到了。

参考


RHadoop实践系列之三 R实现MapReduce的协同过滤算法
基于物品的协同过滤ItemCF的mapreduce实现
用Hadoop构建电影推荐系统

( 完 )