海量数据的二度人脉挖掘算法（Hadoop 实现）

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

      最近做了一个项目，要求找出二度人脉的一些关系，就好似新浪微博的“你可能感兴趣的人” 中，间接关注推荐；简单描述：即你关注的人中有N个人同时都关注了 XXX 。

     在程序的实现上，其实我们要找的是：若 User1 follow了10个人 ｛User3，User4，User5，... ，User12｝记为集合UF1，那么 UF1中的这些人，他们也有follow的集合，分别是记为： UF3（User3 follow的人），UF4，UF5，...，UF12；而在这些集合肯定会有交集，而由最多集合求交产生的交集，就是我们要找的：感兴趣的人。

     我在网上找了些，关于二度人脉算法的实现，大部分无非是通过广度搜索算法来查找，由于深度已经明确了2以内；这个算法其实很简单，第一步找到你关注的人；第二步找到这些人关注的人，最后找出第二步结果中出现频率最高的一个或多个人，即完成。

     但如果有千万级别的用户，那在运算时，就肯定会把这些用户的follow 关系放到内存中，计算的时候依次查找；先说明下我没有明确的诊断对比，这样做的效果不一定就不如 基于hadoop实现的好；只是自己，想用hadoop实现下，最近也在学；若有不足的地方还请指点。

     首先，我的初始数据是文件，每一行为一个follow 关系 ida+‘\t’+idb；表示 ida follow idb。其次，用了2个Map/Reduce任务。

Map/Reduce 1：找出 任意一个用户 的 follow 集合与 被 follow 的集合。如图所示：

代码如下：

     Map任务： 输出时 key ：间接者 A 的ID ，value：follow 的人的ID 或 被follow的人的ID

01	public void map(Text key, IntWritable values, Context context) throws IOException,InterruptedException{

[backcolor=rgb(248, 248, 248) !important]

02	int value = values.get();

03	//切分出两个用户id

[backcolor=rgb(248, 248, 248) !important]

04	String[] _key = Separator.CONNECTORS_Pattern.split(key.toString());

05	if(_key.length ==2){

[backcolor=rgb(248, 248, 248) !important]

06	//"f"前缀表示 follow；"b" 前缀表示 被follow

07	context.write(new Text(_key[0]), new Text("f"+_key[1]));

[backcolor=rgb(248, 248, 248) !important]

08	context.write(new Text(_key[1]), new Text("b"+_key[0]));

09

[backcolor=rgb(248, 248, 248) !important]

10

11

}

[backcolor=rgb(248, 248, 248) !important]

12

}

    Reduce任务： 输出时 key ：间接者 A 的ID ， value为 两个String，第一个而follow的所有人（用分割符分割），第二个为 被follow的人（同样分割）

01	protected void reduce(Text key, Iterable<TextPair> pairs, Context context)

[backcolor=rgb(248, 248, 248) !important]

02	throws IOException,InterruptedException{

03	StringBuilder first_follow = new StringBuilder();

[backcolor=rgb(248, 248, 248) !important]

04	StringBuilder second_befollow = new StringBuilder();

05

[backcolor=rgb(248, 248, 248) !important]

06	for(TextPair pair: pairs){

07	String id = pair.getFirst().toString();

[backcolor=rgb(248, 248, 248) !important]

08	String value = pair.getSecond().toString();

09	if(id.startsWith("f")){

[backcolor=rgb(248, 248, 248) !important]

10	first_follow.append(id.substring(1)).append(Separator.TABLE_String);

11	} else if(id.startsWith("b")){

[backcolor=rgb(248, 248, 248) !important]

12	second_befollow.append(id.substring(1)).append(Separator.TABLE_String);

13

}

[backcolor=rgb(248, 248, 248) !important]

14

}

15

[backcolor=rgb(248, 248, 248) !important]

16	context.write(key, new TextPair(first_follow.toString(),second_befollow.toString()));

17

}

    其中Separator.TABLE_String为自定义的分隔符；TextPair为自定义的 Writable 类，让一个key可以对应两个value，且这两个value可区分。

Map/Reduce 2：在上一步关系中，若B follow A，而 A follow T ，则可以得出 T 为 B 的二度人脉，且 间接者为A ，于是找出 相同二度人脉的不同间接人。如图所示：

代码如下：

     Map 任务：输出时 key 为 由两个String 记录的ID表示的 二度人脉关系，value 为 这个二度关系产生的间接人的ID

01	public void map(Text key, TextPair values, Context context) throws IOException,InterruptedException{

[backcolor=rgb(248, 248, 248) !important]

02	//Map<String, String> first_follow = new HashMap<String, String>();

03	//Map<String, String> second_befollow = new HashMap<String, String>();

[backcolor=rgb(248, 248, 248) !important]

04	//String _key = key.toString();

05	String[] follow = values.getFirst().toString().split(Separator.TABLE_String);

[backcolor=rgb(248, 248, 248) !important]

06

07	String[] befollow = values.getSecond().toString().split(Separator.TABLE_String);

[backcolor=rgb(248, 248, 248) !important]

08

09	for(String f : follow){

[backcolor=rgb(248, 248, 248) !important]

10	for(String b : befollow){

11	//避免自己关注自己

[backcolor=rgb(248, 248, 248) !important]

12	if(!f.equals(b)){

13	context.write(new TextPair(f.getKey() ,b.getKey()), new Text(key));

[backcolor=rgb(248, 248, 248) !important]

14

}

15

}

[backcolor=rgb(248, 248, 248) !important]

16

}

17

}

     Reduce任务：输出时 key 仍然为二度人脉关系， value 为所有间接人 的ID以逗号分割。

01	protected void reduce(TextPair key, Iterable<Text> values, Context context)

[backcolor=rgb(248, 248, 248) !important]

02	throws IOException, InterruptedException {

03

[backcolor=rgb(248, 248, 248) !important]

04	StringBuilder resutl = new StringBuilder();

05	for (Text text : values){

[backcolor=rgb(248, 248, 248) !important]

06	resutl.append(text.toString()).append(",");

07

}

[backcolor=rgb(248, 248, 248) !important]

08

09	context.write(key, new Text(resutl.toString()));

[backcolor=rgb(248, 248, 248) !important]

10

}

     到这步，二度人脉关系基本已经挖掘出来，后续的处理就很简单了，当然也可以基于二度人脉挖掘三度，四度：）

原创博客，转载请注明：http://my.oschina.net/BreathL/blog/75112

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：Hadoop 海量数据 Had Interrupted IMPORTANT 新浪微博 follow 程序 网上 项目

不错不错，好东西

NB!!!!!!!

sqy 发表于 2014-7-2 08:38
NB!!!!!!!

时势造英雄。