MapReduce 社交好友推荐算法

Stella981
• 阅读 518

原理

如果A和B具有好友关系,B和C具有好友关系,而A和C却不是好友关系,那么我们称A和C这样的关系为:二度好友关系。

在生活中,二度好友推荐的运用非常广泛,比如某些主流社交产品中都会有"可能认识的人"这样的功能,一般来说可能认识的人就是通过二度好友关系搜索得到的,在传统的关系型数据库中,可以通过图的广度优先遍历算法实现,而且深度限定为2,然而在海量的数据中,这样的遍历成本太大,所以有必要利用MapReduce编程模型来并行化。

初始数据如下:

A B

C D

E F

F G

B D

B C

map阶段得到的结果为:

Key:A Value:B

Key:B Value:A C D

Key:C Value:B D

Key:E Value:F

Key:F Value:E G

Key:G Value:F

Reduce阶段再将Value进行笛卡尔积运算就可以得到二度好友关系了

(笛卡尔积公式:A×B={(x,y)|x∈A∧y∈B}

例如,A={a,b}, B={0,1,2},则

A×B={(a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2)}

B×A={(0, a), (0, b), (1, a), (1, b), (2, a), (2, b)})

环境

Linux Ubuntu 14.04

jdk-7u75-linux-x64

Hadoop 2.6.0-cdh5.4.5

内容

MapReduce 社交好友推荐算法

MapReduce 社交好友推荐算法

通过初始数据,假设有A、B、C、D、E、F、G七位同学,其中A与B是好友关系,C与D是好友关系,E与F是好友关系,F与G是好友关系,B与D是好友关系,B与C是好友关系,通过分析A与B是好友,且B与C也是好友,我们就认为A与C互为可能认识的人,向A与C互相推荐对方。

实验步骤

1.首先,来准备实验需要用到的数据,切换到/data/mydata目录下,使用vim编辑一个friend_data.txt文件。

  1. cd /data/mydata

  2. vim friend_data.txt

2.将如下初始数据写入其中(注意数据之间以空格分割)

  1. A B

  2. C D

  3. E F

  4. F G

  5. B D

  6. B C

3.切换到/apps/hadoop/sbin目录下,开启Hadoop相关进程

  1. cd /apps/hadoop/sbin

  2. ./start-all.sh

4.输入JPS查看一下相关进程是否已经启动。

  1. jps

MapReduce 社交好友推荐算法

5.在HDFS的根下创建一个friend目录,并将friend_data.txt文件上传到HDFS上的friend文件夹下。

  1. hadoop fs -mkdir /friend

  2. hadoop fs -put /data/mydata/friend_data.txt /friend

6.打开Eclipse,创建一个Map/Reduce项目。

MapReduce 社交好友推荐算法

MapReduce 社交好友推荐算法

7.设置项目名为mr_sf并点击Finish。

MapReduce 社交好友推荐算法

8.创建一个包,名为mr_friend。

MapReduce 社交好友推荐算法

MapReduce 社交好友推荐算法

9.创建一个类,名为Find_Friend。

MapReduce 社交好友推荐算法

MapReduce 社交好友推荐算法

10.下面开始编写Find_Friend类的代码。

完整代码为:

  1. package mr_friend;

  2. import java.io.IOException;

  3. import java.net.URI;

  4. import java.net.URISyntaxException;

  5. import java.util.HashSet;

  6. import java.util.Iterator;

  7. import java.util.Set;

  8. import org.apache.hadoop.conf.Configuration;

  9. import org.apache.hadoop.fs.FileSystem;

  10. import org.apache.hadoop.fs.Path;

  11. import org.apache.hadoop.io.LongWritable;

  12. import org.apache.hadoop.io.Text;

  13. import org.apache.hadoop.mapreduce.Job;

  14. import org.apache.hadoop.mapreduce.Mapper;

  15. import org.apache.hadoop.mapreduce.Reducer;

  16. import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;

  17. import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;

  18. public class Find_Friend {

  19. /*

  20. map结果:

  21. A B

  22. B A

  23. C D

  24. D C

  25. E F

  26. F E

  27. F G

  28. G F

  29. B D

  30. D B

  31. B C

  32. C B

  33. */

  34. public static class FindFriendsMapper extends Mapper<LongWritable, Text, Text, Text> {

  35. @Override

  36. protected void map(LongWritable key, Text value, Mapper<LongWritable, Text, Text, Text>.Context context)

  37. throws IOException, InterruptedException {

  38. String line = value.toString();

  39. String array[] = line.split("\\s+");

  40. context.write(new Text(array[0]), new Text(array[1]));

  41. context.write(new Text(array[1]), new Text(array[0]));

  42. }

  43. }

  44. /*

  45. map之后,Shuffling将相同key的整理在一起,结果如下:

  46. shuffling结果(将结果输出到reduce):

  47. A B

  48. B A

  49. B D

  50. B C

  51. C D

  52. C B

  53. E F

  54. F E

  55. F G

  56. G F

  57. */

  58. //reduce将上面的数据进行笛卡尔积计算

  59. public static class FindFriendsReduce extends Reducer<Text, Text, Text, Text> {

  60. @Override

  61. protected void reduce(Text key, Iterable values, Reducer<Text, Text, Text, Text>.Context context)

  62. throws IOException, InterruptedException {

  63. //将重复数据去重

  64. Set set = new HashSet();

  65. for (Text v : values) {

  66. set.add(v.toString());

  67. }

  68. if (set.size() > 1) {

  69. for (Iterator i = set.iterator(); i.hasNext();) {

  70. String qqName = i.next();

  71. for (Iterator j = set.iterator(); j.hasNext();) {

  72. String otherQqName = j.next();

  73. if (!qqName.equals(otherQqName)) {

  74. context.write(new Text(qqName), new Text(otherQqName));

  75. }

  76. }

  77. }

  78. }

  79. }

  80. }

  81. public static void main(String[] args) throws IOException, ClassNotFoundException, InterruptedException, URISyntaxException {

  82. final String INPUT_PATH = "hdfs://127.0.0.1:9000/friend/friend_data.txt";

  83. final String OUTPUT_PATH = "hdfs://127.0.0.1:9000/friend/output";

  84. Configuration conf = new Configuration();

  85. //Configuration:map/reduce的配置类,向hadoop框架描述map-reduce执行的工作

  86. final FileSystem fileSystem = FileSystem.get(new URI(INPUT_PATH), conf);

  87. if(fileSystem.exists(new Path(OUTPUT_PATH))) {

  88. fileSystem.delete(new Path(OUTPUT_PATH), true);

  89. }

  90. Job job = Job.getInstance(conf, "Find_Friend");//设置一个用户定义的job名称

  91. job.setJarByClass(Find_Friend.class);

  92. job.setMapperClass(FindFriendsMapper.class);    //为job设置Mapper类

  93. job.setReducerClass(FindFriendsReduce.class);    //为job设置Reducer类

  94. job.setOutputKeyClass(Text.class);              //为job的输出数据设置Key类

  95. job.setOutputValueClass(Text.class);            //为job输出设置value类

  96. FileInputFormat.addInputPath(job, new Path(INPUT_PATH));

  97. FileOutputFormat.setOutputPath(job, new Path(OUTPUT_PATH));

  98. System.exit(job.waitForCompletion(true) ?0 : 1);          //运行job

  99. }

  100. }

11.下面在Find_Friend类下,单击右键,选择Run As=>Run on Hadoop,运行程序,查看执行结果。

MapReduce 社交好友推荐算法

12.程序执行完以后,查看HDFS上的/friend/output目录中的计算结果。

  1. hadoop fs -ls -R /friend

  2. hadoop fs -cat /friend/output/part-r-00000

MapReduce 社交好友推荐算法

通过分析结果,就得出了各位同学的可能认识的人的列表了。

至此,实验就已经结束了。

点赞
收藏
评论区
推荐文章
刚刚好 刚刚好
2个月前
css问题
1、 在IOS中图片不显示(给图片加了圆角或者img没有父级) <div<img src""/</div div {width: 20px; height: 20px; borderradius: 20px; overflow: h
blmius blmius
1年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录 问题 用navicat导入数据时,报错: 原因这是因为当前的MySQL不支持datetime为0的情况。 解决修改sql\mode: sql\mode:SQL Mode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。 全局s
晴空闲云 晴空闲云
2个月前
css中box-sizing解放盒子实际宽高计算
我们知道传统的盒子模型,如果增加内边距padding和边框border,那么会撑大整个盒子,造成盒子的宽度不好计算,在实务中特别不方便。boxsizing可以设置盒模型的方式,可以很好的设置固定宽高的盒模型。 盒子宽高计算假如我们设置如下盒子:宽度和高度均为200px,那么这会这个盒子实际的宽高就都是200px。但是当我们设置这个盒子的边框和内间距的时候,那
艾木酱 艾木酱
1个月前
快速入门|使用MemFire Cloud构建React Native应用程序
> MemFire Cloud是一款提供云数据库,用户可以创建云数据库,并对数据库进行管理,还可以对数据库进行备份操作。它还提供后端即服务,用户可以在1分钟内新建一个应用,使用自动生成的API和SDK,访问云数据库、对象存储、用户认证与授权等功能,可专
Stella981 Stella981
1年前
Python微信机器人
### Python微信机器人 **本文目录** * 一 简介 * 二 登录微信 * 三 微信好友男女比例 * 四 微信好友地域分布 * 五 微信聊天机器人 ### 一 简介 wxpy基于itchat,使用了 Web 微信的通讯协议,,通过大量接口优化提升了模块的易用性,并进行丰富的功能扩展。实现了微信登录、收发消息、搜索好友、数
Wesley13 Wesley13
1年前
QQ玩一玩好友排行榜与世界排行榜
**QQ玩一玩好友排行榜与世界排行榜** #### 1、开发环境 * CocosCreator V2.0.5 * 手Q版本 V7.9.0.3820(目前市场中最新版本) * qqPlayCore.js buildTime:'Fri Nov 09 2018 13:20:45 GMT+0800 (GMT+08:00)'上出现,
Stella981 Stella981
1年前
Docker 部署SpringBoot项目不香吗?
  公众号改版后文章乱序推荐,希望你可以点击上方“**Java进阶架构师**”,点击右上角,将我们设为**★**“**星标**”!这样才不会错过每日进阶架构文章呀。   ![](http://dingyue.ws.126.net/2020/0920/b00fbfc7j00qgy5xy002kd200qo00hsg00it00cj.jpg)   **2
Stella981 Stella981
1年前
ELK学习笔记之ElasticSearch的索引详解
0x00 ElasticSearch的索引和MySQL的索引方式对比 ---------------------------------- Elasticsearch是通过Lucene的倒排索引技术实现比关系型数据库更快的过滤。特别是它对多条件的过滤支持非常好,比如年龄在18和30之间,性别为女性这样的组合查询。 倒排索引很多地方都有介绍,但是其比关系型
为什么mysql不推荐使用雪花ID作为主键
作者:毛辰飞 # 背景 在mysql中设计表的时候,mysql官方推荐不要使用uuid或者不连续不重复的雪花id(long形且唯一),而是推荐连续自增的主键id,官方的推荐是auto_increment,那么为什么不建议采用uuid,使用uuid究
helloworld_28799839 helloworld_28799839
2个月前
常用知识整理
# Javascript ## 判断对象是否为空 ```js Object.keys(myObject).length === 0 ``` ## 经常使用的三元运算 > 我们经常遇到处理表格列状态字段如 `status` 的时候可以用到 ``` vue