MapReduce Jaccard Расчет сходства для фильма Рекомендации

Question

Я даю экзамен по распределенным системам и пытался решить проблему MapReduce с прошлогоднего экзамена. Но мне трудно понять, какие функции MR я создам. Упражнение посвящено обработке набора данных, который содержит {userID, movieID, timestamp}. Мы хотим создать сервис, который рекомендует фильм пользователю после его просмотра. Пользователь (id) видел фильм (id) в кортеже. Чтобы порекомендовать другой фильм, вам нужно рассчитать сходство Жакарта следующим образом:

Жаккард (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)

Важное замечание: Вывод команды limit_1 для e.x. должен быть входом map_2.

П.С .: Это не домашнее задание, это был последний выпускной экзамен, поэтому я не помещаю его в Вопросы для домашнего задания. (При необходимости можете дать ссылку на экзамен 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 отображения / уменьшения преобразует (отображает) каждую входную запись в пару (ключ -> значение).

Входная запись -> x Функция карты -> f Вывод функции карты на входную запись -> f(x)

В вашем конкретном примере вы преобразовываете кортеж {userID, movieID, timestamp} в отображение значения ключа (movieId -> userId), отбрасывая метку времени.

Часть reduce map / lower принимает каждое сопоставление ключ-значение, которое вы создали из вышеприведенного, и выполняет функцию агрегирования (уменьшение). Поскольку все данные для одного key должны быть расположены на одном узле для выполнения точного вычисления агрегации, значения для конкретного key перемещаются на конкретный узел, который отвечает за этот key. Вот почему reduce принимает ввод как (ключ -> Список (значение)) или для вашего примера (movieId -> Список (userIds)). Так что да для каждого reduce звонка, key будет отличаться.

Вывод функции reduce будет уникальным (ключ -> aggregation_computation (значения)) для каждой клавиши ввода. Например, в вашем случае,

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