如何用Python挖掘“啤酒和尿布”的关系？（Apriori算法挖掘关联规则）

蔚落 2023-03-13 13:08 155阅读 0赞

# 一、什么是关联规则挖掘？ #

“啤酒与尿布”的故事大家都听过吧，一些年轻的父亲在去超市给孩子买尿布的时候，会顺便给自己买点啤酒，超市发现这个规律之后，就把啤酒和尿布的货架放在一起，这次改动明显增加了超市的销售额。  
啤酒和尿布两者之间就存在着关联规则。  
那么学会挖掘这些关联规则，用处是非常大的。

# 二、规则度量：支持度和置信度 #

**支持度就是两个事务同时发生的概率。**  
 s u p p o r t ( A , B ) = P ( A B ) support(A, B) = P(A B) support(A,B)=P(AB)

> **\[注1\]**  ~  P ( A B ) P(AB) P(AB)就是A和B同时出现的概率。（下同）

**置信度就是**  
 c o n f i d e n c e ( A ⇒ B ) = P ( B ∣ A ) = P ( A B ) / P ( A ) confidence(A\\Rightarrow B)=P(B|A)=P(AB)/P(A) confidence(A⇒B)=P(B∣A)=P(AB)/P(A)  
举个**栗子**：  
路人甲购买了：商品A、B、C；  
炮灰乙购买了：商品A、C；  
流氓丙购买了：商品A、D；  
土匪丁购买了：商品B、E、F。  
 s u p p o r t ( A , B ) = P ( A B ) = 1 / 4 = 0.25 support(A, B) = P(A B)=1/4=0.25 support(A,B)=P(AB)=1/4=0.25  
 s u p p o r t ( A , C ) = P ( A C ) = 2 / 4 = 0.5 support(A, C) = P(AC)=2/4=0.5 support(A,C)=P(AC)=2/4=0.5  
 c o n f i d e n c e ( A ⇒ B ) = P ( B ∣ A ) = P ( A B ) / P ( A ) = 1 / 3 confidence(A\\Rightarrow B)=P(B|A)=P(AB)/P(A)=1/3 confidence(A⇒B)=P(B∣A)=P(AB)/P(A)=1/3  
 c o n f i d e n c e ( A ⇒ C ) = P ( C ∣ A ) = P ( A C ) / P ( A ) = 2 / 3 confidence(A\\Rightarrow C)=P(C|A)=P(A C)/P(A)=2/3 confidence(A⇒C)=P(C∣A)=P(AC)/P(A)=2/3  
**我们在算法中一般会设置两个阈值：最小支持度和最小置信度。**

> 【**注2**】对于最小支持度 s u p p o r t support support，取值范围为 \[ 0 , 1 \] \[0, ~1\] \[0,1\]，我们一般用 s u p p o r t ∗ n support \* n support∗n代替  s u p p o r t support support， n n n就是源数据集的条目数（上面例子四组商品， n = 4 n=4 n=4），这样做的好处就是可以减少运算，判断是否符合最小支持度时，根据项集的计数进行比较就行了。

例如我们设最小支持度 = 0.4，最小置信度 = 0.8。  
那么规则 A , B \{A,B\} A,B因为不满足最小支持度而舍弃；  
规则 A ⇒ B A\\Rightarrow B A⇒B和规则 A ⇒ C A\\Rightarrow C A⇒C因为不满足最小置信度而舍弃。

# 三、k-项集、频繁项集与强关联规则 #

**k-项集：包含k个项的集合。**

*  \{啤酒，尿布，奶粉\}是个3-项集。

**频繁项集：满足最小支持度要求的项集。**（算法第一步挖掘的东西）

**强关联规则：满足最小支持度和最小置信度的规则。**（算法最终得到东西）

# 四、Apriori算法 #

## 4.1 概述 ##

1.  **Apriori算法**：利用频繁项集性质的先验知识（prior knowledge），通过逐层搜索的迭代方法，即将k-项集用于探察(k+1)-项集，来穷尽数据集中的所有频繁项集（通过先验知识挖掘未知知识）
2.  **Apriori性质**：频繁项集的所有非空子集也必须是频繁的。（模式不可能比A更频繁的出现，即A与B的非空交集不可能比A大，只能被包含）

## 4.2 算法 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZpY2lfXw_size_16_color_FFFFFF_t_70_pic_center]

##### ★FIRST. 挖掘频繁项集 #####

1.  扫描数据集，生成单个物品的所有项集（1-项集），并根据在源数据集中出现的次数计数，如下图表C1；
2.  根据最小支持度，对表 C i C\_i Ci进行筛选，去除掉小于最小支持度的项集，留下的就是频繁项集，即表 L i L\_i Li；
3.  利用 L i L\_i Li表，进行连接，有原来的k-项集，连接扩展为(k+1)-项集，记为表 C k + 1 C\_\{k+1\} Ck\+1；
4.  重复执行2、3步，直到不可扩展，所有的 L L L表中的项集，即为频繁项集。

以图中的数据为例，展示代码结果：

1 所有的频繁项集：
    ['A']   支持度： 2
    ['C']   支持度： 3
    ['B']   支持度： 3
    ['E']   支持度： 3
    ['E', 'B']   支持度： 3
    ['B', 'C']   支持度： 2
    ['E', 'C']   支持度： 2
    ['A', 'C']   支持度： 2
    ['E', 'B', 'C']   支持度： 2

##### ★SECOND. 挖掘强关联规则 #####

同时满足最小支持度和最小置信度的才是强关联规则。  
上面已经得到满足最小支持度的频繁项集了，那么我们可以直接从频繁项集入手，找出满足最小置信度的规则，具体步骤如下：

1.  对于每个频繁项集  l l l ，产生  l l l 的所有非空子集；
2.  对于每个子集  s s s ，如果 s u p p o r t ( l ) s u p p o r t ( s ) ≥ m i n \_ c o n f i d e n c e \\frac\{support(l)\}\{support(s)\} \\geq min\\\_confidence support(s)support(l)≥min\_confidence  
    则有规则： s → ( l − s ) s \\rightarrow (l-s) s→(l−s)

2 强关联规则：
    ['B'] -> ['E'] 置信度为： 1.0
    ['E'] -> ['B'] 置信度为： 1.0
    ['C'] -> ['B'] 置信度为： 0.6666666666666666
    ['B'] -> ['C'] 置信度为： 0.6666666666666666
    ['C'] -> ['E'] 置信度为： 0.6666666666666666
    ['E'] -> ['C'] 置信度为： 0.6666666666666666
    ['A'] -> ['C'] 置信度为： 1.0
    ['C'] -> ['A'] 置信度为： 0.6666666666666666
    ['C'] -> ['E', 'B'] 置信度为： 0.6666666666666666
    ['B'] -> ['E', 'C'] 置信度为： 0.6666666666666666
    ['E'] -> ['B', 'C'] 置信度为： 0.6666666666666666
    ['E', 'B'] -> ['C'] 置信度为： 0.6666666666666666
    ['B', 'C'] -> ['E'] 置信度为： 1.0
    ['E', 'C'] -> ['B'] 置信度为： 1.0

## 4.3 核心代码 ##

1.  首先获取C1表，直接从原数据集中把单个元素分离出来并计数。

'''
    1. 获取C1
    '''
    def get_C1(dataset):
        C1 = []  # 使用list存放元素
        for datas in dataset:   # 遍历数据集的每一行
            for data in datas:  # 遍历每一行的所有元素
                if [data] not in C1: # 如果C1中还没有存放这个元素，就把它放入C1
                    C1.append([data])
        # frozenset是冻结的集合，它是不可变的，存在哈希值。
        return list(map(frozenset, C1)) # 将[['A'], ['B']...]转换为[(frozenset({'A'}), (frozenset({'B'})...]的形式

1.  计算支持度，并将小于最小支持度的数据舍弃

'''
 2. 计算支持度，并进行剪枝处理
 '''
 def calc_support_and_drop(dataset, C, min_support):
 '''
 2.1 计算支持度
 '''
 support_dict = {
 } # 存放各元素的支持度，例：{['A']:1, ['B']:4 ...} 表示['A']的支持度为1，['B']的支持度为4
 for Cx in C: # 遍历C
 for datas in dataset: # 遍历dataset
 if Cx <= set(datas): # 判断Cx 是否为datas的子集，就是当前表C中的一行元素Cx能否在dataset中找到
 # 若是其子集，说明原数据集dataset中这一行中有这组元素
 if Cx not in support_dict: # 判断Cx这组合是否在dict中
 support_dict[Cx] = 1 # 若不在，将它的支持度初始化为1
 else:
 support_dict[Cx] += 1 # 若在，支持度加1即可
 '''
 2.2 剪枝处理
 '''
 data_list = [] # [['A'], ['B']...]
 for k, v in support_dict.items(): # 遍历一下我们上面获得的支持度字典
 if v >= min_support: # 如果该组合的支持度不小于最小支持度
 data_list.append(k) # 将改数据放入结果中
 return data_list, support_dict # 返回满足支持度的列表和支持度字典

1.  两层循环，两两组合，只有一个元素不相同时，进行合并，并使用Apriori性质进行剪枝（频繁项集的所有子集必须是频繁的）

'''
    3. 连接
    '''
    def merge(Lk, k):
        data_set = set() # 存放所有组合的数据（未剪枝）
        data_list = [] # 存放剪枝后的数据
        # 两层循环，找到两两组合
        for i in range(len(Lk)-1): # 外循环，从0 ~ len(Lk)-1
            for j in range(i+1, len(Lk)): # 内循环，从i到len(Lk)
                # 两个集合Lk[i]和Lk[j]做差，如果差的长度为1，则说明他们只有一个元素不相同
                if len(Lk[i] - Lk[j]) == 1:
                    # 取到他们的交集
                    data_set.add(Lk[i].union(Lk[j]))
        # 使用Apriori性质剪枝：频繁项集的所有子集必须是频繁的
        for data in data_set:
            count = 0 # 一个计数器
            for Lkx in Lk:
                if Lkx.issubset(data): # 如果Lkx是data的子集，count+=1
                    count += 1
            if count == k+2: # 如果count=k+2，说明data的所有非空子集都都是频繁的
                data_list.append(data)
        return data_list # 返回形式：[['A', 'B'], ['B', 'C']...]

1.  重复执行步骤3，直到满足退出条件（最后表中只有一个或没有频繁项集）
2.  检查置信度，得到强关联规则。

'''
    5. 检查置信度，得到强关联规则。
    目的：计算di的置信度 / dj的置信度，其中dj为di的非空子集。
    '''
    def get_rules(L, support_dict, min_conf):
        relus = {
        } # 存放强关联结果，以元组形式表示[(A, B), (C, D)...]，(A, B)表示 A->B
        for i in range(1, len(L)):          # 循环1：遍历L列表
            for di in L[i]:                 # 循环2：遍历L[i]，L[i] = [[A, B, C], [A, C, D]...]
                for j in range(len(di)-1):  # 循环3：0 ~ len(di)-1，例 di=[A, B, C]，则需要找长度小于3的子集，即0~2的
                    for dj in L[j]:         # 循环4：找长度为j的
                        if dj.issubset(di): # 如果长度为j的dj是di的子集，则判断置信度
                            conf_ij = support_dict[di] / support_dict[dj] # 计算置信度
                            if conf_ij >= min_conf: # 如果support_dict[A并B] / support_dict[B] >= min_conf:
                                relus[(dj, di-dj)] = conf_ij # 得到规则 B -> A
        return relus # 返回强关联规则

## 4.3 代码测试及运行结果展示 ##

**测试样例：**

<table> 
 <thead> 
 <tr> 
 <th>ID</th> 
 <th>items</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>0</td> 
 <td> I 1 , I 2 , I 5 I1,I2,I5 I1,I2,I5</td> 
 </tr> 
 <tr> 
 <td>1</td> 
 <td> I 2 , I 4 I2,I4 I2,I4</td> 
 </tr> 
 <tr> 
 <td>2</td> 
 <td> I 2 , I 3 I2,I3 I2,I3</td> 
 </tr> 
 <tr> 
 <td>3</td> 
 <td> I 1 , I 2 , I 4 I1,I2,I4 I1,I2,I4</td> 
 </tr> 
 <tr> 
 <td>4</td> 
 <td> I 1 , I 3 I1,I3 I1,I3</td> 
 </tr> 
 <tr> 
 <td>5</td> 
 <td> I 2 , I 3 I2,I3 I2,I3</td> 
 </tr> 
 <tr> 
 <td>6</td> 
 <td> I 1 , I 3 I1,I3 I1,I3</td> 
 </tr> 
 <tr> 
 <td>7</td> 
 <td> I 1 , I 2 , I 3 , I 5 I1,I2,I3,I5 I1,I2,I3,I5</td> 
 </tr> 
 <tr> 
 <td>8</td> 
 <td> I 1 , I 2 , I 3 I1,I2,I3 I1,I2,I3</td> 
 </tr> 
 </tbody> 
</table>

**运行结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZpY2lfXw_size_16_color_FFFFFF_t_70]

## 4.4  − − − ~-~-~- −−− ##

*  可直接运行代码之后会给出
 *  如博客中存在错误请您评论或者私信
 *  如有其它地方我可以帮到您的也可评论或者私信
 *  如本博客对您有些许帮助，劳烦点一下赞，万分感谢
 *  最后感谢您的浏览

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZpY2lfXw_size_16_color_FFFFFF_t_70_pic_center]: /images/20230312/dfe4c25d9e5e4e85a68f78d48e31c925.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZpY2lfXw_size_16_color_FFFFFF_t_70]: /images/20230312/2c5acc3596834f5bb7c0b4cb128e4998.png