大数据挖掘: FPGrowth初识–进行商品关联规则挖掘

36大数据 • 8年前扫码分享

我是创始人李岩：很抱歉！给自己产品做个广告，点击进来看看。

作者：王安琪

简介

经典的关联规则挖掘算法包括Apriori算法和FP-growth算法。Apriori算法多次扫描交易数据库，每次利用候选频繁集产生频繁集;而FP-growth则利用树形结构，无需产生候选频繁集而是直接得到频繁集，大大减少扫描交易数据库的次数，从而提高了算法的效率。但是apriori的算法扩展性较好，可以用于并行计算等领域。

关联规则的目的就是在一个数据集中找出项与项之间的关系，适用于在大数量的项集中发现关联共现的项。也被称为购物篮分析 (Market Basket analysis)，因为“购物篮分析”很贴切的表达了适用该算法情景中的一个子集。

购物网站里你买了一个商品，旁边列出一系列买过该商品的人还买的其他商品，并且按置信度高低排序，一般会发现买手机的还会买充电器(买充电器的人不一定会买手机)，买牙刷的还会买牙膏，这大概就是关联规则的用处。

基础环境：

CentOS-6.5

JDK-1.7

spark：spark-1.2.0+cdh5.3.6+379

一、Apriori算法

支持度(Support)：定义为\[supp(X) = \frac{包含X的记录数}{数据集记录总数}= P(X)=\frac{occur(X)}{count(D)}\]

置信度(Confidence)：定义为\[ conf(X=>Y) = \frac{同时包含X和Y的记录数}{数据集中包含X的记录数}=P(Y|X)=\frac{P(X \cap Y)}{P(X)} = \frac{occur(X \cap Y)}{occur(X)}\]

FP-growth算法是Apriori算法的优化。

二、MLlib实现

spark-1.2.0 版本中Mliib的FPGrowthModel并没有generateAssociationRules(minConfidence)方法。因此要引用高版本的jar包，并在提交任务时指定才行。这是可以实现的。

Ⅰ、获取购买历史数据

下面共选取了6931条购买历史记录，作为关联规则挖掘的数据集。

1、产生源数据

我们可能需要使用类Mysql中的group_concat()来产生源数据。在Hive中的替代方案是concat_ws()。但若要连接的列是非string型，会报以下错误：Argument 2 of function CONCAT_WS must be “string or array”, but “array” was found.。使用以下hiveSQL可以避免此问题：

SELECT concat_ws(‘,’, collect_set(cast(item_id AS String))) AS items FROM ods_angel_useritem tb GROUP BY tb.user_id;

得到item1,item2,item3式数据结构。

数据结构如下所示：

大数据挖掘: FPGrowth初识–进行商品关联规则挖掘

2、构造JavaRDD

JavaRDD<list> transactions = …;

Ⅱ、过滤掉出现频率较低的数据

Java代码：

大数据挖掘: FPGrowth初识–进行商品关联规则挖掘

结果：

大数据挖掘: FPGrowth初识–进行商品关联规则挖掘

\[\frac{208}{6931}=0.03001>0.03\]，6931是交易的订单数量，即数据源总条数。

可见，商品732994正好高于支持率下限。

Ⅲ、过滤掉可信度过低的判断

Java代码：

大数据挖掘: FPGrowth初识–进行商品关联规则挖掘

结果：

大数据挖掘: FPGrowth初识–进行商品关联规则挖掘

\(P(733850|733480)=\frac{occur(733850 \cap 733480)}{occur(733480)}=\frac{339}{1051}=0.3225499524262607\)
\(P(733480|731246)=\frac{occur(733480 \cap 731246)}{occur(731246)}=\frac{233}{500}=0.466\)
\(P(733480|733850)=\frac{occur(733850 \cap 733480)}{occur(733850)}=\frac{339}{878}=0.38610478359908884\)

以上表明，用户在购买商品733480后往往还会购买商品733480，可信度为0.3225499524262607;用户在购买商品731246后往往还会购买商品731246，可信度为0.466;用户在购买商品733850后往往还会购买商品733480，可信度为0.38610478359908884。

三、提交任务

Ⅰ、Spark On Standalone

spark-submit –master spark://node190:7077 –class com.angel.mlib.FPGrowthTest –jars lib/hbase-client-0.98.6-cdh5.3.6.jar,lib/hbase-common-0.98.6-cdh5.3.6.jar,lib/hbase-protocol-0.98.6-cdh5.3.6.jar,lib/hbase-server-0.98.6-cdh5.3.6.jar,lib/htrace-core-2.04.jar,lib/zookeeper.jar,lib/spark-mllib_2.10-1.5.2.jar,lib/spark-core_2.10-1.5.2.jar spark-test-1.0.jarⅡ、Spark On Yarn

II、Spark On Yarn

spark-submit –master yarn-client –class com.angel.mlib.FPGrowthTest –jars lib/hbase-client-0.98.6-cdh5.3.6.jar,lib/hbase-common-0.98.6-cdh5.3.6.jar,lib/hbase-protocol-0.98.6-cdh5.3.6.jar,lib/hbase-server-0.98.6-cdh5.3.6.jar,lib/htrace-core-2.04.jar,lib/zookeeper.jar,lib/spark-mllib_2.10-1.5.2.jar,lib/spark-core_2.10-1.5.2.jar spark-test-1.0.jar