电影推荐的 MapReduce Jaccard 相似度计算

Question

我正在参加分布式系统考试，我试图解决去年考试中的一个 MapReduce 问题。但我很难弄清楚我将创建哪些 MR 功能。该练习是关于处理包含 {userID, movieID, timestamp} 的数据集。我们想建立一个服务，在用户观看一部电影后向其推荐一部电影。用户(id)已经看过元组中的电影(id)。要推荐另一部电影，您需要计算 Jaccard 相似度:

Jaccard( X, Y ) = N/(Nx + Ny - N) ，其中:

• Nx = 看过电影 X 的用户数
• Ny = 看过电影 Y 的用户数
• N = 看过电影 X 和 Y 的用户数

MR函数的伪代码必须如下所示:

MAP(key1, value1):
  // Do stuff about<key1,value1>
  emit(key2,value2)


REDUCE(key2,list(value2)):
  //do stuff about <key2, list(value2)>
  emit(key3,value3)

重要:reduce_1 for e.x. 的输出必须是 map_2 的输入。

P.S.:这不是家庭作业，因为它是过去的期末考试，所以我没有把它放在家庭作业问题中。 (需要的话可以给考试pdf的链接)

我已经为初学者尝试了以下方法:

MAP(key1, value1):
  //key = tupleID
  // value1 = {userID, movieID, timestamp}
  // I discard timestamp as it doesn't offer any help on creating 
     Jaccard similarity.
  emit(movieID,userID)


REDUCE(movieID,list(userID)):
  Nx = 0
  for each user u in list(userID):
     Nx = Nx +1
  emit(movieID,Nx)

我不知道接下来要做什么。我也不明白 MR 背后的逻辑，即第二个 MR 将获得什么作为输入。例如，MovieID 将保持不变，或者它将获得数据集中的下一个 movieID？提前感谢您给出的任何解释。如果您想更好地解释练习的数据，请询问。

Answer 1

map/reduce 的 map 部分将每个输入记录转换(映射)为(键 -> 值)对。

输入记录-> x映射函数 -> f输入记录上 map 函数的输出 -> f(x)

在您的具体示例中，您正在通过丢弃时间戳将 {userID, movieID, timestamp} 的元组转换为键值映射(movieId -> userId)。

map/reduce 的 reduce 部分获取您从上面创建的每个键值映射并执行聚合函数(reduce)。由于一个 key 的所有数据都需要位于一个节点上才能执行准确的聚合计算，因此特定 key 的值将移动到负责的特定节点对于那个 key。这就是为什么 reduce 将输入作为 (key -> List(value)) 或您的示例 (movieId -> List(userIds))。所以是的，对于每个 reduce 调用，key 都会不同。

对于每个输入键，reduce 函数的输出都是唯一的(key -> aggregation_computation(values))。例如在你的情况下，

Movie (Id)              Number of Users
Star Wars               50
John Wick               32
Fifty Shades of Grey    9000
...