MapReduce案例-好友推薦
- 2019 年 10 月 9 日
- 筆記
用過各種社交平台(如QQ、微博、朋友網等等)的小夥伴應該都知道有一個叫 "可能認識" 或者 "好友推薦" 的功能(如下圖)。它的演算法主要是根據你們之間的共同好友數進行推薦，當然也有其他如愛好、特長等等。共同好友的數量越多，表明你們可能認識，系統便會自動推薦。今天我將向大家介紹如何使用MapReduce計算共同好友
演算法
假設有以下好友列表，A的好友有B,C,D,F,E,O; B的好友有A,C,E,K 以此類推 那我們要如何算出A-O用戶每個用戶之間的共同好友呢？A:B,C,D,F,E,O B:A,C,E,K C:F,A,D,I D:A,E,F,L E:B,C,D,M,L F:A,B,C,D,E,O,M G:A,C,D,E,F H:A,C,D,E,O I:A,O J:B,O K:A,C,D L:D,E,F M:E,F,G O:A,H,I,J下面我們將演示分步計算，思路主要如下：先算出某個用戶是哪些用戶的共同好友， 如A是B,C,D,E等的共同好友。遍歷B,C,D,E兩兩配對如(B-C共同好友A，注意防止重複B-C,C-B)作為key放鬆給reduce端， 這樣reduce就會收到所有B-C的共同好友的集合。可能到這裡你還不太清楚怎麼回事，下面我給大家畫一個圖。
程式碼演示
由上可知，此次計算由兩步組成，因此需要兩個MapReduce程式先後執行
第一步：通過mapreduce得到 某個用戶是哪些用戶的共同好友。public class FriendsDemoStepOneDriver { static class FriendsDemoStepOneMapper extends Mapper<LongWritable, Text, Text, Text> { @Override protected void map(LongWritable key, Text value, Context context) throws IOException, InterruptedException { String line = value.toString(); String[] split = line.split(":"); String user = split[0]; String[] friends = split[1].split(","); for (String friend : friends) { // 輸出友人，人。 這樣的就可以得到哪個人是哪些人的共同朋友 context.write(new Text(friend),new Text(user)); } } } static class FriendsDemoStepOneReducer extends Reducer<Text,Text,Text,Text>{ @Override protected void reduce(Text key, Iterable<Text> values, Context context) throws IOException, InterruptedException { StringBuilder sb = new StringBuilder(); for (Text person : values) { sb.append(person+","); } context.write(key,new Text(sb.toString())); } } public static void main(String[] args) throws IOException, ClassNotFoundException, InterruptedException { Configuration conf = new Configuration(); conf.set("mapreduce.framework.name","local"); conf.set("fs.defaultFS","file:///"); Job job = Job.getInstance(conf); job.setJarByClass(FriendsDemoStepOneDriver.class); job.setMapperClass(FriendsDemoStepOneMapper.class); job.setReducerClass(FriendsDemoStepOneReducer.class); job.setOutputKeyClass(Text.class); job.setOutputValueClass(Text.class); FileInputFormat.setInputPaths(job,new Path("/Users/kris/Downloads/mapreduce/friends/friends.txt")); FileOutputFormat.setOutputPath(job,new Path("/Users/kris/Downloads/mapreduce/friends/output")); boolean completion = job.waitForCompletion(true); System.out.println(completion); } }運行的到的結果如下：
由圖可見:I,K,C,B,G,F,H,O,D都有好友A；A,F,J,E都有好友B。接下來我們只需組合這些擁有相同的好友的用戶，
作為key發送給reduce,由reduce端聚合d得到所有共同的好友
/** * 遍歷有同個好友的用戶的列表進行組合，得到兩人的共同好友 */ public class FriendsDemoStepTwoDriver { static class FriendDemoStepTwoMapper extends Mapper<LongWritable, Text, Text, Text> { @Override protected void map(LongWritable key, Text value, Context context) throws IOException, InterruptedException { String line = value.toString(); String[] split = line.split("t"); String friend = split[0]; String[] persons = split[1].split(","); Arrays.sort(persons); for (int i = 0; i < persons.length-1; i++) { for (int i1 = i+1; i1 < persons.length; i1++) { context.write(new Text(persons[i]+"--"+persons[i1]),new Text(friend)); } } } } static class FriendDemoStepTwoReducer extends Reducer<Text, Text, Text, Text> { @Override protected void reduce(Text key, Iterable<Text> values, Context context) throws IOException, InterruptedException { StringBuilder sb = new StringBuilder(); for (Text friend : values) { sb.append(friend + ","); } context.write(key,new Text(sb.toString())); } } public static void main(String[] args) throws IOException, ClassNotFoundException, InterruptedException { Configuration conf = new Configuration(); conf.set("mapreduce.framework.name","local"); conf.set("fs.defaultFS","file:///"); Job job = Job.getInstance(conf); job.setJarByClass(FriendsDemoStepOneDriver.class); job.setMapperClass(FriendDemoStepTwoMapper.class); job.setReducerClass(FriendDemoStepTwoReducer.class); job.setOutputKeyClass(Text.class); job.setOutputValueClass(Text.class); FileInputFormat.setInputPaths(job,new Path("/Users/kris/Downloads/mapreduce/friends/output")); FileOutputFormat.setOutputPath(job,new Path("/Users/kris/Downloads/mapreduce/friends/output2")); boolean completion = job.waitForCompletion(true); System.out.println(completion); } }得到的結果如下:
如圖，我們就得到了擁有共同好友的用戶列表及其對應關係，在實際場景中再根據用戶關係(如是否已經是好友)進行過濾，在前端展示，就形成了我們所看到"可能認識"或者"好友推薦"啦～
今天給大家分享的好友推薦演算法就是這些，今天的只是一個小小的案例，現實場景中的運算肯定要比這個複雜的多， 但是思路和方向基本一致，如果有更好的建議或演算法，歡迎與小吳一起討論喔～ 如果您喜歡這篇文章的話記得like,share,comment喔(^^)