如何通过查看两人有多少共同朋友来建立友谊推荐系统，并使用 mapreduce 作业将他们推荐为朋友？有点像 facebook 或 linkedin 所做的，显示推荐人列表，并根据共同朋友的数量对他们进行排名。
问问题
8783 次
1 回答
10
此解决方案取自我的博客，我在项目中使用了此代码。
完整版，见https://www.dbtsai.com/blog/hadoop-mr-to-implement-people-you-might-know-friendship-recommendation/
由于我不确定这是否是最佳解决方案，并且我也想在 stackoverflow 中有一个文档，所以我在这里提出并回答了我自己的问题。我寻找来自社区的反馈。
最好的友谊推荐通常来自朋友。关键思想是，如果两个人有很多共同的朋友，但他们不是朋友，那么系统应该推荐他们相互连接。让我们假设友谊是无向的：如果 A 是 B 的朋友，那么 B 也是 A 的朋友。这是 Facebook、Google+、Linkedin 和几个社交网络中最常用的友谊系统。将其扩展到推特中使用的定向友谊系统并不难；但是，我们将在这篇文章中专注于无向案例。
输入数据将包含邻接列表，并有多行格式为 <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 的共同好友。结果，我们可以发出 <key, value> = <1, r=2; m=0>, <2, r=1; m=0>，<2，r=3；m=0>...，其中 r 表示推荐的朋友，m 表示共同的朋友。我们可以在reduce阶段聚合结果，计算一个用户和推荐用户有多少共同朋友。但是，这种方法会带来一个问题。如果用户 A 和推荐用户 B 已经是朋友了怎么办？为了克服这个问题，我们可以在发出的值中添加另一个属性 isFriend，如果我们知道朋友在 reduce 阶段已经是朋友，我们不推荐他们。
定义fromUser为<USER>，toUser为输入数据中的<FRIENDS>之一，则算法为
地图阶段
- 发出 <fromUser, r=toUser; m=-1> 对于所有 toUser。假设有n 个toUser；然后我们将发出n条记录来描述 fromUser 和 toUser 已经是朋友。请注意，它们已经是发出的密钥和 r 之间的朋友，因此我们将 m 设置为 -1。
- 发出 <toUser1, r=toUser2; m=fromUser> 表示 toUser1 和 toUser2 来自 toUser 的所有可能组合，它们有共同的朋友 fromUser。它将发出n(n - 1)条记录。
- 在 map 阶段总共有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));
}
}
其中 Comparator 在 TreeMap 中用于按共同好友数量的降序对输出值进行排序。
欢迎任何评论和反馈。谢谢。
于 2013-02-23T01:02:38.183 回答