MapReduce案例好友推荐

jiezi

5 年前

用过各种社交平台 (如 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 喔(^^)

本文由博客一文多发平台 OpenWrite 发布！

算法

代码演示