Hadoop M/R實現「你可能認識的人」友情推薦

如何通過查看兩個共有朋友有多少朋友建立友情推薦系統，並使用mapreduce工作推薦他們爲朋友？有點像Facebook或LinkedIn做的事，顯示推薦人的列表，並按共同朋友的人數排名。Hadoop M/R實現「你可能認識的人」友情推薦

2013-02-23 DB Tsai

該解決方案取自我的博客，並在此項目中使用了此代碼。

完整版，看到https://www.dbtsai.com/blog/hadoop-mr-to-implement-people-you-might-know-friendship-recommendation/

因爲我不知道這是否是一個最優的解決方案，我想在計算器的文檔，以及，我問在這裏回答了我自己的問題。我尋找社區的反饋意見。

最好的友誼建議經常來自朋友。關鍵的想法是，如果兩個人有很多共同的朋友，但他們不是朋友，那麼系統應該推薦他們互相連接。我們假設友誼是無向的：如果A是B的朋友，那麼B也是A的朋友。這是Facebook，Google +，LinkedIn和幾個社交網絡中最常見的友誼系統。將它擴展到Twitter中使用的定向友誼系統並不難;但是，我們將在本文中重點討論無向情況。

輸入數據將包含鄰接列表和具有在<USER> <TAB> <FRIENDS>，其中<USER>是用於唯一用戶的唯一ID，並<FRIENDS>格式多行是列表以逗號分隔的用戶是<USER>的朋友。以下是輸入示例。用戶和用戶之間的關係在圖中可以更容易理解。

1    0,2,3,4,5 
2    0,1,4 
3    0,1,4 
4    1,2,3 
5    1,6 
6    5

在曲線圖中，可以看到用戶0不是用戶4和5的朋友，但用戶0和用戶4具有共同的朋友1，2，和3;用戶0和用戶5有共同的朋友1.因此，我們想推薦用戶4和5作爲用戶0的朋友。

輸出推薦的朋友將以以下格式給出。 <USER> <TAB> <推薦朋友給USER（朋友的共同點：[共同朋友的ID，...]），... >。輸出結果按照共同朋友的數量進行排序，並可以從圖表中進行驗證。

0    4 (3: [3, 1, 2]),5 (1: [1]) 
1    6 (1: [5]) 
2    3 (3: [1, 4, 0]),5 (1: [1]) 
3    2 (3: [4, 0, 1]),5 (1: [1]) 
4    0 (3: [2, 3, 1]),5 (1: [1]) 
5    0 (1: [1]),2 (1: [1]),3 (1: [1]),4 (1: [1]) 
6    1 (1: [5])

現在，讓我們將這個問題放入單個M/R作業中。用戶0有朋友，1,2和3;作爲結果，對< 1,2 >，< 2,1 >，< 2,3 >，< 3,2 >，< 1,3 >，和< 3,1 >具有用戶0共同的朋友。因此，我們可以發出<密鑰，值> = < 1，r = 2; m = 0 >,< 2，r = 1; m = 0 >,< 2，r = 3; m = 0 > ...，其中r表示推薦的朋友，m表示相互的朋友。我們可以在縮小階段彙總結果，並計算用戶和推薦用戶之間有多少共同朋友。但是，這種方法會導致問題。如果用戶A和推薦的用戶B已經是朋友，該怎麼辦？爲了克服這個問題，我們可以將另一個屬性isFriend添加到發射值中，如果我們知道他們在縮小階段已經是朋友，我們就不會推薦這位朋友。在下面的實現中，當他們已經是朋友而不是使用額外字段時，使用m = -1。

定義一個FROMUSER是<USER>，和TOUSER是<FRIENDS>在輸入數據中，然後，該算法可以通過

地圖相

的Emit <給出一個fromUser，r = toUser;對於所有用戶，m = -1 >。假設有n給用戶;那麼我們會發出n記錄來描述來自用戶和用戶已經是朋友。請注意，它們已經是發出的密鑰和r之間的朋友，所以我們將m設置爲-1。
發送< toUser1，r = toUser2; m =來自用戶>，用於toUser1的所有可能的組合，並且toUser2來自用戶，並且它們具有共同的朋友，來自用戶。它會發出n（n - 1）記錄。
總共有n^2在地圖階段發出的記錄，其中n是朋友的數量<USER>有。

簡化階段，

只是總結他們有多少共同的朋友有鑰匙之間，並在值r。如果他們中的任何一個有共同的朋友-1，我們不會推薦，因爲他們已經是朋友。
根據共同朋友的數量對結果進行排序。

因爲在hadoop中發出的值不是原始數據類型，我們必須定製一個新的可寫類型，如下面的代碼。

static public class FriendCountWritable implements Writable { 
    public Long user; 
    public Long mutualFriend; 

    public FriendCountWritable(Long user, Long mutualFriend) { 
     this.user = user; 
     this.mutualFriend = mutualFriend; 
    } 

    public FriendCountWritable() { 
     this(-1L, -1L); 
    } 

    @Override 
    public void write(DataOutput out) throws IOException { 
     out.writeLong(user); 
     out.writeLong(mutualFriend); 
    } 

    @Override 
    public void readFields(DataInput in) throws IOException { 
     user = in.readLong(); 
     mutualFriend = in.readLong(); 
    } 

    @Override 
    public String toString() { 
     return " toUser: " 
       + Long.toString(user) + " mutualFriend: " 
       + Long.toString(mutualFriend); 
    } 
}

映射器可以通過

public static class Map extends Mapper<LongWritable, Text, LongWritable, FriendCountWritable> { 
    private Text word = new Text(); 

    @Override 
    public void map(LongWritable key, Text value, Context context) throws IOException, InterruptedException { 
     String line[] = value.toString().split("\t"); 
     Long fromUser = Long.parseLong(line[0]); 
     List toUsers = new ArrayList(); 

     if (line.length == 2) { 
      StringTokenizer tokenizer = new StringTokenizer(line[1], ","); 
      while (tokenizer.hasMoreTokens()) { 
       Long toUser = Long.parseLong(tokenizer.nextToken()); 
       toUsers.add(toUser); 
       context.write(new LongWritable(fromUser), 
         new FriendCountWritable(toUser, -1L)); 
      } 

      for (int i = 0; i < toUsers.size(); i++) { 
       for (int j = i + 1; j < toUsers.size(); j++) { 
        context.write(new LongWritable(toUsers.get(i)), 
          new FriendCountWritable((toUsers.get(j)), fromUser)); 
        context.write(new LongWritable(toUsers.get(j)), 
          new FriendCountWritable((toUsers.get(i)), fromUser)); 
       } 
       } 
      } 
     } 
    }

來實現的減速器可以通過

public static class Reduce extends Reducer<LongWritable, FriendCountWritable, LongWritable, Text> { 
    @Override 
    public void reduce(LongWritable key, Iterable values, Context context) 
      throws IOException, InterruptedException { 

     // key is the recommended friend, and value is the list of mutual friends 
     final java.util.Map<Long, List> mutualFriends = new HashMap<Long, List>(); 

     for (FriendCountWritable val : values) { 
      final Boolean isAlreadyFriend = (val.mutualFriend == -1); 
      final Long toUser = val.user; 
      final Long mutualFriend = val.mutualFriend; 

      if (mutualFriends.containsKey(toUser)) { 
       if (isAlreadyFriend) { 
        mutualFriends.put(toUser, null); 
       } else if (mutualFriends.get(toUser) != null) { 
        mutualFriends.get(toUser).add(mutualFriend); 
       } 
      } else { 
       if (!isAlreadyFriend) { 
        mutualFriends.put(toUser, new ArrayList() { 
         { 
          add(mutualFriend); 
         } 
        }); 
       } else { 
        mutualFriends.put(toUser, null); 
       } 
      } 
     } 

     java.util.SortedMap<Long, List> sortedMutualFriends = new TreeMap<Long, List>(new Comparator() { 
      @Override 
      public int compare(Long key1, Long key2) { 
       Integer v1 = mutualFriends.get(key1).size(); 
       Integer v2 = mutualFriends.get(key2).size(); 
       if (v1 > v2) { 
        return -1; 
       } else if (v1.equals(v2) && key1 < key2) { 
        return -1; 
       } else { 
        return 1; 
       } 
      } 
     }); 

     for (java.util.Map.Entry<Long, List> entry : mutualFriends.entrySet()) { 
      if (entry.getValue() != null) { 
       sortedMutualFriends.put(entry.getKey(), entry.getValue()); 
      } 
     } 

     Integer i = 0; 
     String output = ""; 
     for (java.util.Map.Entry<Long, List> entry : sortedMutualFriends.entrySet()) { 
      if (i == 0) { 
       output = entry.getKey().toString() + " (" + entry.getValue().size() + ": " + entry.getValue() + ")"; 
      } else { 
       output += "," + entry.getKey().toString() + " (" + entry.getValue().size() + ": " + entry.getValue() + ")"; 
      } 
      ++i; 
     } 
     context.write(key, new Text(output)); 
    } 
}

其中比較器是在TreeMap中用於降低數的順序排序的輸出值來實現共同的朋友。

歡迎任何評論和反饋。謝謝。

來源

2013-02-23 01:02:38

Hadoop M/R實現「你可能認識的人」友情推薦

回答

相關問題