Apriori 算法

R 中的购物篮分析

Christopher Bruffaerts

Statistician

关联规则挖掘

关联规则挖掘用于从大型交易数据库中发现项目间的有趣关系。

该任务分为两个子任务：

  • 频繁项集生成：在可能很大的交易库中找出所有频繁项集。若项集满足最小支持度阈值，则为频繁。

  • 规则生成：基于上述频繁项集，生成置信度高于最小置信度阈值的关联规则。

  Apriori 算法是经典且快速的关联规则挖掘算法。

R 中的购物篮分析

Apriori 算法的思路

Apriori 算法：

  • 自底向上方法
  • 利用 Apriori 原理生成候选项集

Apriori 原理：

  • 若一项集是频繁的，则其所有子集也必须是频繁的。
    • 例如：若 {A,B} 频繁，则 {A} 和 {B} 都频繁
  • 若一项集不频繁，则其所有超集都不频繁。
    • 例如：若 {A} 不频繁，则 {A,B}、{A,C}、{A,B,C} 都不频繁。
1 Agrawal 和 Srikant（1994）
R 中的购物篮分析

示例：1-项集

项集格2

TID 交易
1 {A, B, C, D}
2 {A, B, D}
3 {A, B}
4 {B, C, D}
5 {B, C}
6 {C, D}
7 {B, D}
1 最小支持度阈值 = 3/7 = 0.42
R 中的购物篮分析

示例：2-项集

项集格3

TID 交易
1 {A, B, C, D}
2 {A, B, D}
3 {A, B}
4 {B, C, D}
5 {B, C}
6 {C, D}
7 {B, D}
1 最小支持度阈值 = 3/7 = 0.42
R 中的购物篮分析

示例：3-项集

所有项集

TID 交易
1 {A, B, C, D}
2 {A, B, D}
3 {A, B}
4 {B, C, D}
5 {B, C}
6 {C, D}
7 {B, D}
1 最小支持度阈值 = 3/7 = 0.42
R 中的购物篮分析

示例：频繁项集

项集格3

项集 计数 支持度
{A} 3 0.42
{B} 6 0.85
{C} 4 0.57
{D} 5 0.71
{A,B} 3 0.42
{B,C} 3 0.42
{B,D} 4 0.57
{C,D} 3 0.42
1 最小支持度阈值 = 3/7 = 0.42
R 中的购物篮分析

Apriori：规则生成

在代价高的频繁项集生成之后，Apriori 开始生成规则：

  • 先从单一前件、置信度高的规则开始
    • 例如 {A,C} $\rightarrow$ {B}
  • 再构建更复杂的规则，右侧含更多项
    • 例如 {A,C} $\rightarrow$ {B, D}

 

技巧：剪枝关联规则

例如：若 {B,C,D} $\rightarrow$ {A} 的置信度低，则所有后件含 A 的规则都可丢弃（如 {B,D} $\rightarrow$ {A, C} 或 {D} $\rightarrow$ {A,B, C}）。

R 中的购物篮分析

Apriori 的首次尝试

事务型数据

inspect(head(trans,2))

    items     transactionID
[1] {A,B,C,D} 1            
[2] {A,B,D}   2

首次调用 apriori 函数——频繁项集

support.all = apriori(trans, 
                      parameter = list(supp = 3/7, target="frequent itemsets"))
R 中的购物篮分析

Apriori 输出——频繁项集

频繁项集

inspect(support.all)

    items support   count
[1] {A}   0.4285714 3    
[2] {C}   0.5714286 4    
[3] {D}   0.7142857 5    
[4] {B}   0.8571429 6    
[5] {A,B} 0.4285714 3    
[6] {C,D} 0.4285714 3    
[7] {B,C} 0.4285714 3    
[8] {B,D} 0.5714286 4

项集格3

R 中的购物篮分析

用 apriori 提取规则

参数：挖掘参数会影响项集或规则的特性。

  • 支持度 = 3/7
  • 置信度 = 60%
  • 规则最小长度 = 2

使用特定参数调用 apriori 进行规则生成

rules.all = apriori(trans,
                parameter = list(supp=3/7, conf=0.6, minlen=2),
                control = list(verbose=F)
                   )
R 中的购物篮分析

提取规则：输出

检查规则 

inspect(rules.all)

    lhs    rhs support   confidence lift      count
[1] {A} => {B} 0.4285714 1.0000000  1.1666667 3    
[2] {C} => {D} 0.4285714 0.7500000  1.0500000 3    
[3] {D} => {C} 0.4285714 0.6000000  1.0500000 3    
[4] {C} => {B} 0.4285714 0.7500000  0.8750000 3    
[5] {D} => {B} 0.5714286 0.8000000  0.9333333 4    
[6] {B} => {D} 0.5714286 0.6666667  0.9333333 4
R 中的购物篮分析

Ayo berlatih!

R 中的购物篮分析

Preparing Video For Download...