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构建电影推荐系统