SparkML中关联规则的应用

spark

发布日期: 2019-12-24

1. 概念

什么是关联规则?(Association Rules)

关联规则是数据挖掘中的概念, 通过分析数据, 找到数据之间的关联, 电商中经常用来分析购买商品之间的相关性, 例如,”购买尿布的用户有大概率购买啤酒”, 这就是一个关联规则.

如果把买尿布记作A, 买啤酒记作B

“买尿布的用户有较大概率买啤酒” 这个关联规则记作 A -> B

什么是关联规则推荐? (Association Rule Based Recommendaion)

顾名思义, 利用关联规则, 来实施推荐的目标, 是希望达到

“将尿布放进购物车之后, 再推荐啤酒” 比 “直接推荐啤酒” 获得更好的售卖效果

ps: 这个目标非常重要, 有些场景, 或许直接推荐更有效

关联规则的典型应用

线上: 可以在用户将尿布放进购物车后, 立刻推荐啤酒
线下: 可以将尿布和啤酒放在一起

2. 如何实施

假设某电商会售卖ABCD四种商品, 历史上共有5笔订单, 分别卖出 {A,B,C}, {B,C,D}, {A,B,C,D}, {A,C}, {C} 如何来实施“关联规则”推荐呢？

2.1 数据准备

订单号	商品A	商品B	商品C	商品D
x001	1	1	1
x002		1	1	1
x003	1	1	1	1
x004	1		1
x005			1

如上表格, 纵坐标是所有历史订单, 横坐标是每笔单出售的商品

2.2 计算关联规则(商品组合) 的支持度

什么是支持度?
一共五笔订单, 3笔订单包括商品A, 那么A的支持度就是3/5

订单号	商品A	商品B	商品C	商品D
x001	1	1	1
x002		1	1	1
x003	1	1	1	1
x004	1		1
x005			1
support	(A)3/5	(B)3/5	(C)1	(D)2/5

很容易计算出, 各个商品的支持度, 从支持度可以看出 Best Seller 的商品是C, 100% 的订单中都包含商品C , C的支持度是1.

除了单个商品, 组合商品也有支持度

订单号	商品A	商品B	商品C	商品D
x001	1	1	1
x002		1	1	1
x003	1	1	1	1
x004	1		1
x005			1
support	(A)3/5	(B)3/5	(C)1	(D)2/5

support(A->B)	(A->B) 2/5

共5笔订单, 两笔同时包含AB, 即A->B的支持度是 2/5

ps: 全局共四种商品, 假设关联规则只关联两种商品, 则一共需要计算 C(4,2) 共六种组合商品的支持度,{AB,AC,AD,BC,BD,CD} 支持度评估商品包含在订单中的”概率”, 一个订单, 有多大概率包含这个商品。

ps: 一般会先对支持度高的商品实施推荐, 如果先优化了支持度低的商品, 即使推荐效果翻倍, 总体订单提升效果也会很有限。

2.3 计算关联规则的置信度

什么是置信度?(confidence)

已知购买了A, 有多大概率购买了B(即同时购买AB), 称 A-> B 的置信度

订单号	商品A	商品B	商品C	商品D
x001	1	1	1
x002		1	1	1
x003	1	1	1	1
x004	1		1
x005			1
support	(A)3/5	(B)3/5	(C)1	(D)2/5

support(A->B)	(A->B) 2/5
confidence(A->B)	s(A->B) / s(A) = 2/3

可以看到, 商品A有三次购买, 这三次购买中有两次购买了B , A->B 的置信度是2/3
ps: confidence(A->B) = (support(A->B)) / (support(A)) = (2/5) / (3/5) = 2/3

相对比较好理解

分子: support(A->B) 是同时购买AB的比例,

分母: support(A) 是只购买了A的比例

二者相除, 得到了”购买了A, 有多个概率购买B”, 置信度本质是条件概率

这里需要注意的是: X->Y 与 Y->X的置信度是不定相等的

订单号	商品A	商品B	商品C	商品D
x001	1	1	1
x002		1	1	1
x003	1	1	1	1
x004	1		1
x005			1
support	(A)3/5	(B)3/5	(C)1	(D)2/5

support(A->B)	(A->B) 2/5
confidence(A->B)	s(A->B) / s(A) = 2/3
confidence(B->C)	s(B->C) / S(B) = 1
confidence(C->B)	s(C->B) / S(C) = 3/5

ps:

support(B->C) = 3/5

support(C->B) = 3/5

support(B) = 3/5

support(C) = 1

confidence(B->C) = support(B->C) / support(B) = 1

confidence(C->B) = support(C->B) / support(C) = 3/5

2.4 计算关联规则的提升度

上一个例子里, confidence(B->C) = 1 , 即, 如果用户购买了商品B, 100%会买C , 那么是不是意味着, 如果用户将商品B放进购物车, 就可以向用户推荐商品C呢?

答案是否定的.

我们来回顾一下, 关联规则的推荐目标, 是希望达到

“将尿布放进购物车之后, 再推荐啤酒” 比 “直接推荐啤酒” 获得更好的售卖效果

虽然购买商品B, 100% 会购买商品C

confidence(B->C) = 1

但是直接推荐C, 用户也会100% 购买C

support(c)= 1

会发现, 购买B 与购买C是独立事件, 用户买不买C和用户买不买B没有直接关系, 这里的关联规则推荐, 并没有比直接推荐获取更好的效果, 那么用什么指标来品谷关联规则的效果呢?

提升度

什么是提升度?(lift)

A->B 关联规则推荐, 与直接推荐B的比值, 可以用来评估推荐效果:

大于1, 说明有效, 在购买A时, 推荐B 比直接推荐B 效果更好

等于1, 说明无关, 在购买A 与购买B时, 是独立事件

小于1, 说明负相关, 购买A时推荐B, 效果还不如直接推荐B

提升度简单公式如下：

lift(A->B) = confidence(A->B) / support(B)

分子: confidence(A->B) , 购买A时, 有多大概率同时购买B

分母:support(B) , 有多大概率直接购买B

二者相除, 得到效果是否更好

还是通过两个直观的例子来看

1.计算 lift(A->B)

订单号	商品A	商品B	商品C	商品D
x001	1	1	1
x002		1	1	1
x003	1	1	1	1
x004	1		1
x005			1
support	(A)3/5	(B)3/5	(C)1	(D)2/5

support(A->B)	(A->B) 2/5
confidence(A->B)	s(A->B) / s(A) = 2/3
lift(A->B)	c(A->B)/s(B) = 10/9

来看看关联规则, A->B 与直接推荐B , 效果有没有提升

有3个订单购买A , 这三个订单中有两个订单购买了B, 所以A-> B 的置信度是2/3, 即买了A有2/3的概率会买B

直接推荐B的话, 5个订单中有三个购买了B, 所以B的支持度是3/5, 即有3/5的概率会直接购买B

会发现, 关联规则推荐的效果更好

confidence(A->B) = support(A->B)/support(A) = 2/3

support(B) = 3/5

lift(A->B) = confidence(A->B)/support(B) = (2/3)/(3/5) = 10/9

lift(A->B) > 1 所以，关联规则推荐是正相关的

2. 计算 lift(A->D)

订单号	商品A	商品B	商品C	商品D
x001	1	1	1
x002		1	1	1
x003	1	1	1	1
x004	1		1
x005			1
support	(A)3/5	(B)3/5	(C)1	(D)2/5

support(A->B)	(A->B) 2/5
support(D)	(D) 2/5
confidence(A->B)	s(A->B) / s(A) = 2/3
lift(A->B)	c(A->B)/s(B) = 10/9

来看看关联规则A->D 与直接推荐D, 效果有没有提升

有三个订单购买A, 这三个订单中有1个购买了D, 所以A->D 的置信度是1/3, 即买了A有1/3的概率会买D

直接推荐D的话, 5个订单有2个购买了D, 所以D的支持度是2/5, 即有2/5的概率会直接买D

会发现, 关联规则推荐效果差, 还不如直接推荐

confidence(A->) = support(A->D)/support(A) = 1/3

support(D) = 2/5

lift(A->D) = confidence(A->D) / support(D) = 5/6

lift(A->D) <1 所以，关联规则推荐是负相关的

3. 总结

关联规则A->B 推荐, 目标是, 在“用户将A放入购物车时, 推荐B” 比“单独推荐B” 获取更好的效果。

A->B 的支持度, 是用户同时购买A和B的概率

A->B 的置信度, 是用户购买A的同时, 有多大概率购买B

A->B 的提升度, 是“用户购买A的同时, 有多大概率购买B” 与“直接购买B”的比值

提升度大于1时: 说明 A->B是正向效果

提升度等于1时: 说明A和B 是独立事件

提升度小于1时: 说明 A->B是负向效果

4. Spark FPGrowth 代码示例

源码地址：https://github.com/hnbian/MySpark/blob/master/SparkML/src/main/scala/hnbian/sparkml/association/FPGrowth_mllib.scala

package hnbian.sparkml.association
 
import hnbian.spark.utils.SparkUtils
import org.apache.spark.mllib.fpm.FPGrowth
import utils.FileUtils
 
/**
  * @author hnbian 2019/4/17 14:31
  *         关联规则代码示例
  */
object FPGrowth_mllib extends App {
  val spark = SparkUtils.getSparkSession("FPGrowth", 4)
 
  import spark.implicits._
 
  //最小支持度
  val minSupport = 0.055
  //最小置信度
  val minConfidence = 0.2
  //数据分区
  val numPartitions = 10
 
  //取出数据
  val filePath = FileUtils.getFilePath("association_rules.txt")
  println(filePath)
  val data = spark.sparkContext.textFile(filePath)
  //把数据通过空格分割
  val transactions = data.map(x => x.split(","))
  val data_count = data.collect().length
  println("length==>" + data_count)
  transactions.persist()
  val transactionsDF = transactions.toDF("items")
  //transactionsDF.show()
 
 
  //使用  sparkmllib包下面的算法
  //创建一个FPGrowth 算法实例
  val fpg = new FPGrowth()
 
  //设置训练时候的最小支持度和分区数据
  fpg.setMinSupport(minSupport) //默认0.3
  fpg.setNumPartitions(numPartitions)
 
  //把数据带入算法中
  val model = fpg.run(transactions)
  println("打印频繁项集出现次数")
  //查看所有频繁项集， 并列出他们出现的次数
  val support_rdd = model.freqItemsets.filter(itemset => {
    itemset.items.length >= 3 //选择过滤出几项数据
  }).map(itemset => {
    (itemset.items.mkString(","), itemset.freq, itemset.freq.toDouble / data_count) //itemset.freq 出现次数
  })
 
  val support_df = support_rdd.toDF("items", "count", "support")
  support_df.orderBy(support_df("items").asc).show(5) //按照频繁项集出现的次数排序
  /**
    * +-----------+-----+-------------------+
    * |      items|count|            support|
    * +-----------+-----+-------------------+
    * |A 1,B 3,C 4|   52|0.05591397849462366|
    * |A 1,C 2,D 4|   52|0.05591397849462366|
    * |A 2,B 4,C 4|   80|0.08602150537634409|
    * |A 2,B 4,H 4|   73|0.07849462365591398|
    * |A 2,C 4,H 4|   76|0.08172043010752689|
    * +-----------+-----+-------------------+
    */
  val bb = model.freqItemsets.persist()
 
  println("打印置信度")
  // 通过置信度筛选出推荐规则，
  //antecedent 表示前项
  //consequent 表示后项
  val confidence_rdd = model.generateAssociationRules(minConfidence)
    .filter(
      x => {(x.antecedent.length>=2 && x.consequent.length == 1)} //过滤出前项长度为3 并且后项长度为1 的条件
    )
    .map(x => {
    println(s"前项:${x.antecedent.toSet.toBuffer},后项:${x.consequent.toSet.toBuffer},置信度:${x.confidence},提升度:${x.lift}")
    /**
      * 前项:ArrayBuffer(A 4, B 4),后项:ArrayBuffer(H 4),置信度:0.488,提升度:Some(1.0935903614457831)
      * 前项:ArrayBuffer(C 3, F 3),后项:ArrayBuffer(H 4),置信度:0.875,提升度:Some(1.9608433734939759)
      * 前项:ArrayBuffer(F 3, A 2),后项:ArrayBuffer(H 4),置信度:0.7261904761904762,提升度:Some(1.6273666092943202)
      * ...
      */
    (x.antecedent.mkString(","), x.consequent.mkString(","),x.confidence,x.lift,x.toString())
  })
 
  val confidence_df = confidence_rdd.toDF("antecedent", "consequent", "confidence","lift","remark")
  confidence_df.orderBy(confidence_df("confidence").desc).show(5,false)
  /**
    * +-----------+----------+------------------+------------------+----------------------------------------------------------------------------------------+
    * |antecedent |consequent|confidence        |lift              |remark                                                                                  |
    * +-----------+----------+------------------+------------------+----------------------------------------------------------------------------------------+
    * |F 3,A 4    |H 4       |0.8795180722891566|1.9709682101901582|{F 3,A 4} => {H 4}: (confidence: 0.8795180722891566; lift: Some(1.9709682101901582))    |
    * |C 3,F 3    |H 4       |0.875             |1.9608433734939759|{C 3,F 3} => {H 4}: (confidence: 0.875; lift: Some(1.9608433734939759))                 |
    * |F 3,B 4    |H 4       |0.8088235294117647|1.8125442948263644|{F 3,B 4} => {H 4}: (confidence: 0.8088235294117647; lift: Some(1.8125442948263644))    |
    * |F 3,C 4    |H 4       |0.7941176470588235|1.7795889440113395|{F 3,C 4} => {H 4}: (confidence: 0.7941176470588235; lift: Some(1.7795889440113395))    |
    * |E 3,B 4,H 4|D 2       |0.7761194029850746|1.9667330920330228|{E 3,B 4,H 4} => {D 2}: (confidence: 0.7761194029850746; lift: Some(1.9667330920330228))|
    * +-----------+----------+------------------+------------------+----------------------------------------------------------------------------------------+
    */
}