关联规则挖掘

一、基本概念

概念

关联规则挖掘(Association rules mining)

  • 在数据集中找到各项数据之间的关联关系。

项目(Item)

  • ID Items bought
    10 A,B,D
    20 A,C,D
    30 A,D,E

支持度(support)

  • 项集{x,y}\{x,y\}在总项集中出现的概率(x,yx,y同时出现)

  • Support(x→y)=P(x,y)P(I)=P(xUy)P(I)Support(x\to y)=\frac{P(x,y)}{P(I)}=\frac{P(xUy)}{P(I)}

置信度(Confidence)

  • 当xx出现时，yy也一起出现的概率，表示为x,yx,y同时出现的概率占xx出现的概率

  • Confidence(x→y)=P(y∣x)=P(xy)P(x)Confidence(x\to y)=P(y|x)=\frac{P(xy)}{P(x)}

提升度(Lift)

  • x,yx,y同时出现的频率，但是还需要再考虑二者各自出现的概率，从而表现出二者的相关性。提升度=1表示没有相关性(独立)，高于一正相关，低于一负相关。

  • Lift(x→y)=ConfidenceP(y)=P(xy)P(x)P(y)Lift(x\to y)=\frac{Confidence}{P(y)}=\frac{P(xy)}{P(x)P(y)}

一般来说，我们评估一个规则是否合理，会设置一定的最小支持度或者最小置信度阈值，大于这个阈值的规则，我们认为是感兴趣的。

举个例子

ID Items
1 A,B
2 A,B,C
3 A,D
4 A,B,C
5 B,C
6 B,D

这个表格中，AA的出现次数为44，ABAB的出现次数为33，其支持度A→BA\to B为:3/83/8，而置信度A→BA\to B为3/43/4，提升度为3∗6/(4∗5)3*6/(4*5).

布尔型与数值型关联规则

  • 布尔型一般只关注买没买，例如Apple→MilkApple\to Milk
  • 数值型一般还要关注数值属性，例如Apple→115元,Apple→100−105元Apple\to 115元,Apple\to 100-105元

一般来说，关联规则的挖掘可以看做以下两步的过程：

  • 找出所有频繁项集，该项集的每一个出现的支持度计数都大于等于最小支持度阈值
  • 由频繁项集产生强关联规则，即满足最小支持度和最小置信度的规则

由于第二步的开销远小于第一步，所有总体性能是由第一步决定的。例如：

一个长度为100的频繁项集，包含了

C1001+C1002+...+C100100−1=1.2730C_{100}^1+C_{100}^2+...+C_{100}^{100}-1=1.27^{30}

这么多个频繁项

二、频繁项集挖掘方法

1️⃣ Apriori算法

Apriori算法由Agrawal和Strikant在1994年提出，是布尔关联规则挖掘的原创性算法，通过限制候选产生发现频繁项集。Apriori算法使用一种称为逐层搜索的迭代方式，其中kk项集用于生成(k+1)(k+1)项集。

Apriori算法假定频繁项集的所有非空子集都是频繁的，这是一个先验性质，可以进一步过滤掉很多项集。其算法的核心分为两步：剪枝和连接

连接步

  • 通过Lk−1L_{k-1}与自身连接产生kk项候选集，Apriori算法假定事务或者项集中的项按照字典序排序，如果Lk−1L_{k-1}的元素可连接，那么要求他们的前k−2k-2个项相同

剪枝步

  • 每一次扫描，都会将候选集中的非频繁项集删除，因为他们的子项集必定是非频繁项集

关联规则

  • 置信度

    • Confidence(A→B)=Support(AUB)Support(A)≥minCConfidence(A\to B)=\frac{Support(AUB)}{Support(A)}\ge minC

由于规则由频繁项集产生，因此每个规则都自动地满足最小支持度。他们的支持度可以预先放在散列表中。

栗子

ID Items
1 I1,I2,I5
2 I2,I4
3 I2,I3
4 I1,I2,I4
5 I1,I3
6 I2,I3
7 I1,I3
8 I1,I2,I3,I5
9 I1,I2,I3

最小支持度为40%

第一次迭代：

Items Support
I1 6/9
I2 7/9
I3 6/9
I4 2/9
I5 2/9

此时，I4,I5小于最小支持度，应该被剪枝

剩下的集合为

Items Support
I1 6/9
I2 7/9
I3 6/9

他们之间可以生成下一项：

Items Support
I1,I2 4/9
I1,I3 4/9
I2,I3 4/9

没有需要剪枝的，再进行下一步

Items Support
I1,I2,I3 1/9

并不算频繁规则，所以最后的频繁项集为：{I1,I2,I3,{I1,I2},{I2,I3},{I1,I2}}

然后是置信度方面，置信度的计算可以表示为：

A→B,Confidence=support(B∣A)support(A)A\to B,Confidence=\frac{support(B|A)}{support(A)}

说人话就是发生A的条件下，有多少次是带着B玩。

Apriori算法的挑战与改进

挑战

  • 需要多次扫描数据库
  • 产生大量候选集
  • 工作乏味

改进

  • 减少事务数据库扫描的传递次数
  • 缩小候选集数量
  • 改进对候选集的支持度统计

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import math
import numpy as np
from collections import defaultdict

d=np.array(["milk,water,juice","milk,water","milk,rice,water","water","tomato,juice","juice,cucumber"])

def Apriori(data,min_spport=2,min_confidence=0.5):

    FP=[]
    Data=[]
    # 初始化项集
    I=[]
    # 因为字符串不好做运算，所以我们映射成数组
    str2num=defaultdict(int)
    cnt=0

    for i in data:
        for j in i.split(","):
            if j not in str2num.keys():
                str2num[j]=cnt
                cnt+=1

    for i in data:
        t=[]
        for j in i.split(","):
            I.append(j)
            t.append(str2num[j])
        Data.append(set(t))
    I=[[i] for i in set(I)]

    def scan(setI):
        tem=defaultdict(int)
        for i in setI:
            for j in Data:
                # 做个映射
                for k in i:
                    if str2num[k] not in j:
                        break
                else:
                    tem[",".join(i)]+=1
        return [[i,j] for i,j in tem.items() if j>=min_spport]


    def comb(setI):
        # 记录
        FP.append(setI)
        # 按字典序排序
        I=[sorted([i[0]]) for i in setI]
        T=[]
        for i,v in enumerate(I):
            for j in I[i+1:]:
                if len(v)>1 and v[:-1]==j[:-1]:
                    T.append(v[:-1]+v[-1]+j[-1])
                elif len(v)==1:
                    T.append(v+j)

        return [set(i) for i in T]

    while 1:
        # 每次都需要扫描
        I=scan(I)
        # 这个I是已经进行剪枝后的了
        # 然后要进行连接步，要求前K-2项相同
        if I==[]:
            return FP
        I=comb(I)



print(Apriori(d))

2️⃣ Partition: Scan Database Only Twice

首次提出：

A. Savasere, E. Omiecinski, and S. Navathe. An efficient algorithm for mining association in large databases. In VLDB’95.

分区技术

  • 将数据分为NN个小的区域
  • 阶段一：在当前数据区内寻找并记录频繁项集
  • 阶段二：整合所有子区域内的频繁项集，并扫描整个数据库

思想

  • 任何数据集中的频繁项集，必须在至少一个子区域内频繁(很简单就可以推出，如果任一分区都不频繁，那么同时加起来后依旧是不频繁的∑a∑n\frac{\sum a}{\sum n})

细节

  • 每个分区都可以放入内存中
  • 扫描数据库只有两次！降低I/O成本！
  • 线性执行时间尺度
  • 适合用于非常大规模的数据库
  • 适用于并行/分布式计算系统

3️⃣ DHP: Reduce the Number of Candidates

首次提出

J. Park, M. Chen, and P. Yu. An effective hash-based algorithm for mining association rules. In SIGMOD’95

基于哈希思想的技术

  • 当扫描事务以生成频繁的k项集时，LkL_k会为每个事务生成所有（k+1）项集
  • 将所有（k+1）项集分成桶，增加桶计数
  • 如果一个（k+1）项集桶计数低于min_sup，它必须从（k+1）候选项集中删除

思想

对应的哈希桶计数低于阈值的k项集不能频繁出现

image-20221121135332298

4️⃣ DIC算法

基本思想：把数据库分成若干块，每一块都有一个开始点（start point）,在每一个开始点处都可以加入新的候选项集。一旦确定所有子集都是频繁的，就可以在任何起点添加新的候选项。

目的：减少数据库的查找次数

image-20221121153342248

如上图所示，初始时，加入所有的一项集，然后扫描B1，得到一项集在B1中的支持度，选出频繁一项集组成的候选二项集，在B2的start point位置加入，然后扫描B2，给候选项集里的项集计数，然后再生成新的频繁项集，在B1的start point上加入。重复这个过程，直到没有新的频繁项集生成。

5️⃣频繁模式增长算法(Frequent Pattern Growth, FP-Growth)

优势

  • 直接挖掘频繁项集，无须产生候选集和检查的过程

算法步骤

一、创建FP树

第一次扫描数据库时，导出频繁项的集合，并按照频繁项支持度计数进行降序排序。例如：

image-20221121140549504

接着，再次扫描数据库，构建FP树。算法描述如下：

  • 创建树的根节点，并为每个事务创建一个分支
    • 沿着根节点向下生长，当节点存在当前分支时，共同前缀计数+1
    • 当不存在当前节点，开辟一个新的节点
  • 创建一个项表头，使得每项都能通过一个节点链得到它在树中的位置。
  • image-20221121140858032

下面是FP树的生成实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class FPTree:

    def __init__(self,name="NULL"):
        self.children=[]
        self.val={} # name:[val,loc]
        self.cnt=0
        self.n=self,name

    def growth(self,items):
        node=self
        for i in items:
            if i in node.val.keys():
                node.val[i][0]+=1
            else:
                node.val[i]=[1,node.cnt]
                node.cnt+=1
                node.children.append(FPTree(i))

            node = node.children[node.val[i][1]]

    def __str__(self):
        return str(self.n)

    def getFPTree(self):
        tem=list(zip(list(self.val.items()),self.children))
        while tem:
            a=tem.pop()
            print("Node: %s"%a[0][0],"val: %d"%a[0][1][0])
            tem+=list((zip(list(a[1].val.items()),a[1].children)))



A=FPTree()
A.growth(["a","b","c","d"])
A.growth(["a","b","c","e"])
A.getFPTree()

Node: a val: 2
Node: b val: 2
Node: c val: 2
Node: e val: 1
Node: d val: 1

二、FP树挖掘

现在，我们需要从项头表的底部开始向上挖掘，找到每一项的条件模式基(Condition Pattern Base)。

所谓的条件模式基，就是一个以当前要挖掘节点为叶子结点的路经集合，或者说是一颗子树。

例如：

image-20221121143848909

在这颗FP树中，到节点m的路径有：fcafca和fcabfcab，对这个路径集合每个节点的计数设为叶子节点mm的计数：

fca:2,fcab:1fca:2,fcab:1，此时，各个节点的计数为:

Node Cnt
f 3
c 3
a 3
b 1

此时删除低于支持度的节点，并对剩下的节点递归构建FP树。直到只剩下单一路径为止。

image-20221121145125121

这单一路径上的所有节点组合，都可以是频繁模式。

优点

  • 分治
  • 无候选生成和候选测试
  • 压缩数据库
  • 两次扫描

三、多层次关联规则挖掘

这个一般涉及到概念级的挖掘了。例如：

image-20221121151528756

统一支持度

▪ 自上而下，水平

▪ 对每个级别使用统一的最小支持度

▪ 在每个级别执行Apriori

▪ 优化：如果祖先不频繁，可以避免对后代的搜索

image-20221121151626459

缺点

  • 错过阈值过高的感兴趣规则

  • 生成太多不感兴趣的阈值太低的规则

减少支持度

▪ 自上而下，水平

▪ 每个概念级别都有自己的最低支持阈值

▪ 级别越低，阈值越小

▪ 在每个级别执行Apriori

image-20221121151811122

优化–按单个项目进行级别交叉过滤

▪ 按单个项目进行级别交叉过滤

•如果第（i-1）级的父概念频繁，则检查第i级的项目

•如果概念不常见，则从数据库中删除其后代

缺点

  • 错过低级别项目的关联，这些项目通常基于减少的min_support，但其祖先不满足min_support

优化–通过单个项目进行受控制的层级交叉过滤

  • 下一级min sup<水平通过阈值<min sup

  • 如果满足等级通过阈值，则允许检查不满足min_sup的项目的子项

image-20221121152058941

由于项目之间的“祖先”关系，某些规则可能是多余的

实例

  • 牛奶→\to 小麦面包 [支持度=8%，置信度=70%]

  • 2%牛奶$\to $小麦面包 [ 支持度=2%，置信度=72%]

  • 我们说第一条规则是第二条规则的祖先,如果基于规则的祖先，规则的支持接近“预期”值，则该规则是多余的

四、多维度关联规则挖掘

一维规则：

购买（X，“牛奶”）→\to 购买（X，“面包”）

多维规则：>2维或谓词

▪ 维度间关联规则（无重复谓词）

年龄（X，“19-25”）andand 职业（X，“学生”）→\to 购买（X，“焦炭”）

▪ 混合维度关联规则（重复谓词）

年龄（X，“19-25”）andand 购买（X，“爆米花”）→\to购买（X，“焦炭”）

  • 类别属性：有限数量的可能值，值之间没有排序
  • 定量属性：数值、值之间的隐式排序-离散化、聚类方法

数值属性动态离散化

▪ 使得挖掘的规则的置信度或紧凑性最大化

关联规则聚类系统（ARCS）

▪ 装箱：二维网格，可管理大小

▪ 查找频繁的谓词集：扫描数据库，计数

每个网格单元的支持

▪ 对规则进行聚类：对相邻单元格进行聚类以形成规则

image-20221121152835772