如何用Map/Reduce來做好友推薦

這篇文章主要講解了“如何用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來做好友推薦這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！