/MapReduce

MapReduce Demo

Primary LanguageJava

MapReduce Demo

Map-Reduce程序场景代码。

已完成的有:

1.网站kpi数据统计
2.电信运营商用户基站停留数据统计
3.基于物品的协同过滤实现
4.测试mahout推荐算法API
5.使用自定义的分片策略和庖丁分词进行中文分析
6.PeopleRank算法并行化实现-mr的矩阵计算
7.简单实现sql的统计、groupby和join
8.实现简单的倒排索引
9.查找社交二度关系
10.广告精准营销

1.网站kpi数据统计

程序中分别对五个kpi指标进行统计操作:

1.browser:用户使用的浏览器统计
2.ips:页面用户独立ip数统计
3.pv:网站pv量统计
4.source:用户来源网址统计
5.time:时间段用户访问量统计

数据下载

2.电信运营商用户基站停留数据统计

原始数据分为位置和网络两种
位置数据格式为:
用户标识 设备标识 开关机信息 基站位置 通讯的时间
example:
0000009999 0054785806 3 00000089 2016-02-21 21:55:37

网络数据格式为:
用户标识 设备标识 基站位置 通讯的时间 访问的URL
example:
0000000999 0054776806 00000109 2016-02-21 23:35:18 www.baidu.com

需要得到的数据格式为:
用户标识 时段 基站位置 停留时间

example:
00001 09-18 00003 15
用户00001在09-18点这个时间段在基站00003停留了15分钟

两个reducer:

1.统计每个用户在不同时段中各个基站的停留时间
2.在1的结果上只保留停留时间最长的基站位置信息

数据下载

3.基于物品的协同过滤实现

算法解释请看:ItermCF的MR并行实现

4.测试mahout推荐算法API

1.RecommendFactory:推荐相关信息获取的工厂类,包括用户/物品相似度,用户邻居,用户/物品推荐器,数据模型,算法评分器
2.RecommendUtil:打印算法的评分结果、推荐结果等
3.RecommendEvaluator:从RecommendFactory中获得相似度、推荐器等进行算法组合,借助RecommendUtil打印出评分结果
4.RecommendResult:选取RecommendEvaluator中评分结果最好的两个算法,借助RecommendUtil打印出推荐结果

###调用mahout推荐算法流程:

1.选择输入数据,创建DataModel对象
2.根据DataModel对象创建用户或物品的Similarity对象
3.如果是基于用户的,那么需要创建UserNeighborhood对象
4.根据以上的条件,创建用户或物品的Recommender对象

使用算法评估器流程:

1.123步骤同上
4.创建RecommenderBuilder对象,调用RecommenderEvaluator的evaluate方法进行评估
4.1评估查全率和召回率创建RecommenderIRStatsEvaluator对象,调用其evaluate方法返回IRStatistics对象
4.2调用IRStatistics对象的getPrecision,getRecall方法即可

使用条件过滤的流程:

1.使用自定义的类实现IDRescorer接口,在类中定义成员,在类外使用过滤规则,将过滤之后的结果存入类中
2.调用recommend方法进行推荐的时候加入参数IDRescorer

数据下载

5.使用自定义的分片策略和庖丁分词进行中文分析

庖丁分词需要的jar包和dic文件下载

庖丁分词的使用注意:

1.paoding-analysis的包和mahout的包放在一起会冲突,mahout中重写了tokenStream方法为final类型,paoding中又需要重写此方法,会出现class net.paoding.analysis.analyzer.PaodingAnalyzerBean overrides final method tokenStream.的错误
**解决方法:**去掉mahout的包即可

2.在IDEA项目中,需要把庖丁的dic目录放入src/main/resources下,否则会报PaodingAnalysisException: not found the dic home directory!的异常,修改paoding-analysis包中的paoding-dic-home文件,设置paoding.dic.home=classpath:dic

3.打成jar包时,需要将dic目录复制到hadoop的classpath目录下(最好是第一个),否则会报PaodingAnalysisException: dic home should not be a file, but a directory!,虽然jar包中已经包含了dic。

包说明:

1.normal:使用默认的mapreduce分切策略,读取全部小文件需要8k+个mapper,cpu占用高达80%,运行时间n个小时
2.special:使用自定义的分片策略,将多个小文件合并,每次map处理的数据为一个文件的全部内容,而不是一行,启动的mapper为4个,运行时间大大提高

自定义的分片策略解决大量小文件的问题

数据下载

6.PeopleRank算法并行化实现-mr的矩阵计算

使用mapreduce框架实现PeopleRank算法,并在示例数据集上进行测试。

PeopleRank算法实现过程:

1.AdjacencyMapper:将原始数据集转换成邻接表
2.AdjacencyReducer:计算邻接表的每一行,转换成邻接矩阵之后使用PageRank的计算公式推导邻接概率矩阵
3.CalcPeopleRankMapper:输入邻接概率矩阵和pr矩阵,运用矩阵相乘规律将数据输出到reduce进行计算
4.CalcPeopleRankReducer:分别用两个map保存邻接矩阵和pr矩阵的值进行计算
5.FinallyResultMapper:将计算得到的pr值统一输出到reduce中进行转换计算
6.FinallyResultReducer:对每个pr值/pr总值,得到的数据即为最终结果

该算法重点在于矩阵的计算
整个mapreduce作业中最核心的就是CalcPeopleRank这部分
在mapreduce中进行矩阵计算的技巧在于从矩阵乘法公式中找出矩阵相乘的规律

map过程:

1.读取第一个矩阵的每一行的每一个数据,并做标识处理
2.将行号作为key,读取第二个矩阵的时候按照读,以列号为key,这样一来两个矩阵中对应的需要计算的值都都被一起输出到reduce中
3.由于两个矩阵的值都会出现在reduce中,所以需要在map的value中设置一个标识位,如:A,B等,表示这个数值是第一个矩阵还是第二个矩阵的
4.即使将两个矩阵的行和列对应起来了,但是没有将行列中各个值对应起来也是没办法计算的,所以map得value中还应该包含该数值在当前矩阵中是第几列(对于第二个按列读取的矩阵来说就是第几行)

reduce过程:

1.每个输入都是两个矩阵相对应的行和列,并且从value中可以得到该值是哪个矩阵,第几行第几列的值
2.根据value中矩阵的标志位对不同的矩阵值做不同的处理,分别加入两个map字典中,key为原本value中包含的行列标志位,value为数值本身
3.现在只要遍历任意一个map,取出一个值的时候就根据该值的key到另外一个map中取出对应的值进行相乘,最后将结果相加即可

数据下载

7.简单实现sql的统计、groupby和join

统计最大、最小和平均值

根据给出的文件(表),内容格式为

Name age
abc 12
... ...

统计年龄的最大、最小和平均值
sql示例:

select avg(age) as avg,max(age) as max,min(age) as min from xxx;

group by

根据给出的文件(表),内容格式为

customer order_price
1 100
2 130
... ...

实现根据costomer进行分组,统计每个customer的总订单金额
sql示例:

select customer,sum(order_price) from orders group by customer

join连接

根据给出的文件(表)
Customer表结构为:

id name
1 chubby
2 xiaohei
... ...

Orders表结构为:

|id|cus_id| |1|1| |2|1| |3|2| |...|...|

实现两个表的join连接
sql示例:

select Customer.name,Orders.id from Customers left join Orders on Customers.id=Orders.cus_id

8.实现简单的倒排索引

倒排索引的详情参考:
mapreduce实现搜索引擎简单的倒排索引

9.查找社交二度关系

一个简单的类似QQ好友推荐的功能,**就是找到好友之间的二度关系,例如有如下好友关系:
小明 小红
张三 李四
王五 小李
小红 小黑 小李 小红

以小明为例,关系图为:小明->小红,小红->小黑
那么小明和小黑之间就有一个二度关系,可以互相推荐好友(P.S. 著名的xx说世界上的任何两个人最多通过7层关系都可以联系起来)

我们要做的事情就是将有二度关系的人找出来
首先要确定map的key和value应该是什么才能在reduce中得到需要的结果
根据mr程序的尿性,在reduce的时候会将key相同的value聚集在一起,那么可以将二度关系中的链接点作为key,reduce中就可以拿到推荐的好友
如上例中的小红为key,小明和小黑为value

mr程序很简单:

map过程中将每行的1和2作为key-value输出一次,反过来将2和1作为key-value再次输出
reduce中可以拿到所有key相同的一个集合,集合中的每个元素都是有二度关系的,对其进行全排列即可得到推荐好友名单

10.广告精准营销

案例说明请参考:MapReduce广告精准营销案例

详情见代码

作者:@小黑