频繁二项集合的hadoop实现
很多应用场景下,我们都需要通过用户的行为数据挖掘搜索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个子任务:
- 统计频繁query,同时为每个query所在的session生成(md5)签名,并标出query在session中的位置
- 过滤不满足support的query
- 根据session及query在session中的位置进行排序,将同一session的query汇总在一起
- mapper生成各二项集合, reducer统计是否满足支持度
代码示例:
在实际应用中,最简单的方式就是直接挑出满足最小支持度的频繁二项集,同时限定query pair的出现次数比介于一定区间的query pair进行推荐。
例如,限定query比介于(0.5~2)之间, 以下为部分结果供大家参考, 当然, 实际系统中使用, 还会使用字面相关性+语义相关性(例如PLSA)对结果进行校验。
具体代码可从以下网址下载:
http://pan.baidu.com/share/link?shareid=615851165&uk=1493671608
代码中已经添加部分注释
更多内容参见:
Data Mining Concepts and Techniques 第五章 Mining Frequent Pattern, Association and Correlations