温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

如何用Map/Reduce来做好友推荐

发布时间:2021-12-31 16:07:30 来源:亿速云 阅读:110 作者:iii 栏目:数据库

这篇文章主要讲解了“如何用Map/Reduce来做好友推荐”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“如何用Map/Reduce来做好友推荐”吧!

  SNS网站都有一个功能,就是好友推荐(或者Follower推荐)。例如,在人人网上出现的“你可能认识的人”。怎么来实现呢,有一个很简单的办法。如果小刚和小明不是好友,但是他们有很多的共同好友。那么可以认为,A和B很可能相识。

  怎样用Map/Reduce来做好友推荐

  从图论的讲法上看,就是先列出一个人(记为小A)的所有朋友的朋友,在寻找小A和这些人之间有多少长度为2的通路。将这些通路数排序,寻找最高的那几个就可以了。

  所以我们的Map/Reduce的任务就是:找出所有人的十个Top“推荐好友”。

  社会化网络的图一般都很简单。我们假设输入是按name排序的。

  "ricky" => ["jay", "peter", "phyllis"]

  "peter" => ["dave", "jack", "ricky", "susan"]

  我们使用两轮Map/Reduce任务来完成这个操作。

  第一轮MR任务

  这个任务的目的是计算每一对距离是2的人之间的通路数。

  在Map函数中,我们先将每对朋友做一个笛卡尔乘积,说的不大清楚,举个例子,比如

  "ricky" => ["jay", "john", "mitch"]

  那么结果就是

  ["jay", "john"], ["jay", "mitch"], ["john", "mitch"]

  他们都是通过ricky牵线搭桥认识的。将已经是朋友的组合筛选掉,再排好序。传给Reducer。

  在Reduce函数中, 相同的组合必定会传给Reducer。所以Reducer只要数好有几个相同的组合传给他就行了.

  Input record … person -> connection_list

  e.g. "ricky" => ["jay", "john", "mitch", "peter"]

  also the connection list is sorted by alphabetical order

  def map(person, connection_list)

  # Compute a cartesian product using nested loops

  for each friend1 in connection_list

  # Eliminate all 2-degree pairs if they already

  # have a one-degree connection

  emit([person, friend1, 0])

  for each friend2 > friend1 in connection_list

  emit([friend1, friend2, 1], 1)

  def partition(key)

  #use the first two elements of the key to choose a reducer

  return super.partition([key[0], key[1]])

  def reduce(person_pair, frequency_list)

  # Check if this is a new pair

  if @current_pair != [person_pair[0], person_pair[1]]

  @current_pair = [person_pair[0], person_pair[1]]

  # Skip all subsequent pairs if these two person

  # already know each other

  @skip = true if person_pair[2] == 0

  if !skip

  path_count = 0

  for each count in frequency_list

  path_count += count

  emit(person_pair, path_count)

  Output record … person_pair => path_count

  e.g. ["jay", "john"] => 5

  怎样用Map/Reduce来做好友推荐

  第二轮MR任务

  这一轮的MR任务是为了列出每个人距离为2的好友,查出他们直接究竟有几条路径。

  在Map函数中,我们将每一组数据重新排列,保证一个人信息落在一个reducer上

  在Reduce函数中,只要将每个人的可能好友之间的路径数排个序就可以了.

  Input record = Output record of round 1

  def map(person_pair, path_count)

  emit([person_pair[0], path_count], person_pair[1])

  def partition(key)

  #use the first element of the key to choose a reducer

  return super.partition(key[0])

  def reduce(connection_count_pair, candidate_list)

  # Check if this is a new person

  if @current_person != connection_count_pair[0]

  emit(@current_person, @top_ten)

  @top_ten = []

  @current_person = connection_count_pair[0]

  #Pick the top ten candidates to connect with

  if @top_ten.size < 10   for each candidate in candidate_list   @top_ten.append([candidate, connection_count_pair[1]])   break if @pick_count > 10

  Output record … person -> candidate_count_list

  e.g. "ricky" => [["jay", 5], ["peter", 3] …]

  Follower推荐

  如果我想要做Follower推荐而不是好友推荐怎么办呢?

  很简单。只要将第一步的MR任务改为求“Follow关系”和“Followed”关系的笛卡尔乘积就可以了。这里就不列伪码了。

感谢各位的阅读,以上就是“如何用Map/Reduce来做好友推荐”的内容了,经过本文的学习后,相信大家对如何用Map/Reduce来做好友推荐这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是亿速云,小编将为大家推送更多相关知识点的文章,欢迎关注!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI