频繁二项集合的hadoop实现

标签: hadoop 大数据 推荐系统 搜索引擎 数据挖掘 | 发表时间:2013-10-29 14:41 | 作者:semo2524
出处:http://semocean.com

很多应用场景下,我们都需要通过用户的行为数据挖掘搜索query之间的关系,例如搜索引擎的相关搜索(related query),或是关键词推荐通过session数据,或者搜索点击数据(query-click数据)找到相关的推荐词,而频繁二项集挖掘,作为最简单直接的方式,就会被经常用到,下文即介绍对于大数据情况下高效的频繁二项集算法。并附上可直接在hadoop上运行的python map-reduce代码。

下文仅考虑频繁二项集,在实际中,频繁k项集可以根据频繁二项集的概念直接进行扩展。

定义: 二项集,就可以直观地理解为session中出现的pair,例如在session中如果同时出现‘王菲’ 和 ‘李亚鹏’, 则 <‘王菲’, ‘李亚鹏’> 即为二项集。

定义: 支持度(support),挖掘出来的频繁二项集能够覆盖总session的百分比,例如,挖掘出来‘王菲’, ‘李亚鹏’两个关键词的二项集出现了20次,而假设共有100个session,则支持度为20/100=20%

定义: 置信度(confidence),指出现频繁二项集第一个word时,同时出现第二个word的概率。例如出现‘王菲’ 时,有70%的可能同时出现‘李亚鹏’, 此时我们说该二项集的置信度为70%

定义: 频繁二项集, 如果特定二项集同时满足指定支持度及置信度阈值,我们就可以说该二项集为频繁二项集。

其实根据上述频繁二项集的定义,我们就可以设计基于hadoop MR的高效算法。

思路很简单,先统计所有可能成为频繁二项集的候选二项集统计支持度, 当支持度大于事先设定的阈值时,认定该二项集合为频繁二项集,同时给出置信度。

为了加快算法的运行,我们使用了频繁项集的一个重要属性,这也是Apriori算法最重要的属性: 所有频繁项集的非空子项集,也是频繁的(All nonempty subsets of a frequent itemset must be frequent).根据该属性,我们可以在进行频繁二项集挖掘前,先统计session中query出现的频率,将频率不满足频繁二项集支持度的query过滤。 这样可以大大提高后续流程的效率。毕竟在很多系统中,数据分布均较为长尾,设定一个合适的支持度后,能够大幅缩短运行的时间(当然,需要与召回进行权衡)

总结下来,在实现时,将其分为4个子任务:

  1. 统计频繁query,同时为每个query所在的session生成(md5)签名,并标出query在session中的位置
  2. 过滤不满足support的query
  3. 根据session及query在session中的位置进行排序,将同一session的query汇总在一起
  4. mapper生成各二项集合, reducer统计是否满足支持度

代码示例:

freq-pair-mining

在实际应用中,最简单的方式就是直接挑出满足最小支持度的频繁二项集,同时限定query pair的出现次数比介于一定区间的query pair进行推荐。

例如,限定query比介于(0.5~2)之间, 以下为部分结果供大家参考, 当然, 实际系统中使用, 还会使用字面相关性+语义相关性(例如PLSA)对结果进行校验。

freq-pair-sample

具体代码可从以下网址下载:

http://pan.baidu.com/share/link?shareid=615851165&uk=1493671608

代码中已经添加部分注释

更多内容参见:

Data Mining Concepts and Techniques 第五章 Mining Frequent Pattern, Association and Correlations

相关 [集合 hadoop] 推荐:

频繁二项集合的hadoop实现

- - 海之沙
很多应用场景下,我们都需要通过用户的行为数据挖掘搜索query之间的关系,例如搜索引擎的相关搜索(related query),或是关键词推荐通过session数据,或者搜索点击数据(query-click数据)找到相关的推荐词,而频繁二项集挖掘,作为最简单直接的方式,就会被经常用到,下文即介绍对于大数据情况下高效的频繁二项集算法.

Hadoop Streaming 编程

- - 学着站在巨人的肩膀上
Hadoop Streaming是Hadoop提供的一个编程工具,它允许用户使用任何可执行文件或者脚本文件作为Mapper和Reducer,例如:. 采用shell脚本语言中的一些命令作为mapper和reducer(cat作为mapper,wc作为reducer). 本文安排如下,第二节介绍Hadoop Streaming的原理,第三节介绍Hadoop Streaming的使用方法,第四节介绍Hadoop Streaming的程序编写方法,在这一节中,用C++、C、shell脚本 和python实现了WordCount作业,第五节总结了常见的问题.

Hadoop使用(一)

- Pei - 博客园-首页原创精华区
Hadoop使用主/从(Master/Slave)架构,主要角色有NameNode,DataNode,secondary NameNode,JobTracker,TaskTracker组成. 其中NameNode,secondary NameNode,JobTracker运行在Master节点上,DataNode和TaskTracker运行在Slave节点上.

Hadoop MapReduce技巧

- - 简单文本
我在使用Hadoop编写MapReduce程序时,遇到了一些问题,通过在Google上查询资料,并结合自己对Hadoop的理解,逐一解决了这些问题. Hadoop对MapReduce中Key与Value的类型是有要求的,简单说来,这些类型必须支持Hadoop的序列化. 为了提高序列化的性能,Hadoop还为Java中常见的基本类型提供了相应地支持序列化的类型,如IntWritable,LongWritable,并为String类型提供了Text类型.

Hadoop TaskScheduler浅析

- - kouu&#39;s home
TaskScheduler,顾名思义,就是MapReduce中的任务调度器. 在MapReduce中,JobTracker接收JobClient提交的Job,将它们按InputFormat的划分以及其他相关配置,生成若干个Map和Reduce任务. 然后,当一个TaskTracker通过心跳告知JobTracker自己还有空闲的任务Slot时,JobTracker就会向其分派任务.

HADOOP安装

- - OracleDBA Blog---三少个人自留地
最近有时间看看hadoop的一些东西,而且在测试的环境上做了一些搭建的工作. 首先,安装前需要做一些准备工作. 使用一台pcserver作为测试服务器,同时使用Oracle VM VirtualBox来作为虚拟机的服务器. 新建了三个虚拟机以后,安装linux,我安装的linux的版本是redhat linux 5.4 x64版本.

Hadoop Corona介绍

- - 董的博客
Dong | 可以转载, 但必须以超链接形式标明文章原始出处和作者信息及 版权声明. 网址: http://dongxicheng.org/hadoop-corona/hadoop-corona/. Hadoop Corona是facebook开源的下一代MapReduce框架. 其基本设计动机和Apache的YARN一致,在此不再重复,读者可参考我的这篇文章 “下一代Apache Hadoop MapReduce框架的架构”.

Hadoop RPC机制

- - 企业架构 - ITeye博客
RPC(Remote Procedure Call Protocol)远程过程调用协议,它是一种通过网络从远程计算机程序上请求服务,而不需要了解底层网络技术的协议. Hadoop底层的交互都是通过 rpc进行的. 例如:datanode和namenode 、tasktracker和jobtracker、secondary namenode和namenode之间的通信都是通过rpc实现的.

Hadoop Rumen介绍

- - 董的博客
Dong | 新浪微博: 西成懂 | 可以转载, 但必须以超链接形式标明文章原始出处和作者信息及 版权声明. 网址: http://dongxicheng.org/mapreduce/hadoop-rumen-introduction/. 什么是Hadoop Rumen?. Hadoop Rumen是为Hadoop MapReduce设计的日志解析和分析工具,它能够将JobHistory 日志解析成有意义的数据并格式化存储.

Hadoop contrib介绍

- - 董的博客
Dong | 可以转载, 但必须以超链接形式标明文章原始出处和作者信息及 版权声明. 网址: http://dongxicheng.org/mapreduce/hadoop-contrib/. Hadoop Contrib是Hadoop代码中第三方公司贡献的工具包,一般作为Hadoop kernel的扩展功能,它包含多个非常有用的扩展包,本文以Hadoop 1.0为例对Hadoop Contrib中的各个工具包进行介绍.