共計 2552 個字符，預計需要花費 7 分鐘才能閱讀完成。
這篇文章主要講解了“如何用 Map/Reduce 來做好友推薦”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著丸趣 TV 小編的思路慢慢深入，一起來研究和學習“如何用 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 來做好友推薦這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是丸趣 TV，丸趣 TV 小編將為大家推送更多相關知識點的文章，歡迎關注！
