2人の共通の友達の数を調べて友情推薦システムを構築し、mapreduceジョブを使用して友達として推薦するにはどうすればよいですか？FacebookやLinkedInのように、おすすめの人のリストを表示し、相互の友達の数でランク付けします。
質問する
8783 次
1 に答える
10
このソリューションは私のブログから取られており、プロジェクトでこのコードを使用しました。
フルバージョンについては、https：//www.dbtsai.com/blog/hadoop-mr-to-implement-people-you-might-know-friendship-recommendation/を参照してください。
それが最適な解決策かどうかわからないので、スタックオーバーフローにもドキュメントを入れたいので、ここで自分の質問に答えました。コミュニティからのフィードバックを探しています。
最高の友情の推薦はしばしば友人から来ます。重要なアイデアは、2人の人がお互いにたくさんの友達を持っているが、彼らが友達ではない場合、システムは彼らがお互いに接続することを推奨する必要があるということです。友情が無向であると仮定しましょう。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があります。そのため、ユーザー0の友達としてユーザー4と5をお勧めします。
推奨される友達の出力は次の形式で表示されます。<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>の1つであることを定義すると、アルゴリズムは次のように与えられます。
マップフェーズ
- Emit <fromUser、r = toUser; すべてのtoUserに対してm=-1>。ntoUserがあるとしましょう。次に、fromUserとtoUserがすでに友達であることを説明するためにn個のレコードを発行します。放出されたキーとrの間にはすでにフレンドであるため、mを-1に設定していることに注意してください。
- Emit <toUser1、r = toUser2; toUser1とtoUser2の可能なすべての組み合わせに対してm=fromUser>であり、相互の友人であるfromUserがあります。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));
}
}
ここで、Comparatorは、相互のフレンドの数の降順で出力値をソートするためにTreeMapで使用されます。
コメントやフィードバックは大歓迎です。ありがとう。
于 2013-02-23T01:02:38.183 に答える