关联规则（Association Rule）

• • 什么是关联规则
  • 一些基本概念
  • 任务是什么
  • Apriori 算法
  • • • 核心思想
      • 步骤与流程图
      • 如何找到候选集
  • python代码实现

什么是关联规则

关联规则(Association Rules)是反映一个事物与其他事物之间的相互依存性和关联性，是数据挖掘的一个重要技术，用于从大量数据中挖掘出有价值的数据项之间的相关关系。

用一些例子来说明一下：
当我们在超市进行购物时，超市中有琳琅满目的商品，在每一次购物结束之后，我们会拥有一个购物车然后去结账，然后产生购物小票，购物小票中记录了我们购买的每件商品的信息，如此日积月累，所有的这些记录就会产生海量的用户购买行为。从这些购买行为中，我们特别希望能够发掘出类似买了面包的人就会去购买牛奶这样的规则。
这种规则，在数据挖掘中有很多，比如著名的啤酒和尿布的例子：在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，而他们中有30%～40%的人同时也为自己买一些啤酒。产生这一现象的原因是：美国的太太们常叮嘱她们的丈夫下班后为小孩买尿布，而丈夫们在买尿布后又随手带回了他们喜欢的啤酒。

买了一样商品就会去买另外一件商品，这就是一种关联规则。

一些基本概念

Items（项）
实际上就是一些商品，面包，牛奶，巧克力，啤酒，尿布… 每一个都是一个itemitemitem。

Transaction（交易）
一条交易记录（购物小票），是所有商品的非空子集。可以买一件商品，两件商品… 但是集合不能是空集。

Itemset（项集）
同时购买的一组东西。itemsetitemsetitemset有大有小，购买的东西有可能有1个，2个，kkk个，如果有kkk个，那么 itemset 就被称作 k−itemsetk-itemsetk−itemset。

Dataset（数据库）
包含一系列的transactiontransactiontransaction

下面给出一个例子：

Bread是一个itemitemitem，Butter也是一个itemitemitem，而第1、2、4交易记录中，同时购买的Bread和Butter，就组成一个 2−itemset2-itemset2−itemset。

Support（支持度）
可以理解成是一种频率，就是在一些 transactiontransactiontransaction 当中某一个item（或者itemset）item（ 或者 itemset）item（或者itemset）出现的频率。

例如上表中的 Bread$ 的support就是6/8，Bread与Butter的supportsupportsupport是3/8，Bread、Butter和Chips的supportsupportsupport是0

关联规则x−>yx -> yx−>y的支持度就是一些交易中同时包含xxx和yyy的频率。

Confidence（置信度）
关联规则x−>yx -> yx−>y的置信度就是一些交易中 同时包含xxx和yyy的数量与xxx的数量的比。

也可以被写作下面的公式：

置信度也可以被理解为是一种条件概率 P（X∣Y）P（X | Y）P（X∣Y），比如当我购买牛奶这个事件发生的时候，又购买面包这个事件发生的概率是多少。

引用上表的例子，如
Bread −>->−> Milk 的 supportsupportsupport = 2/8 , confidenceconfidenceconfidence = 1/3
Milk −>->−> Bread 的 supportsupportsupport = 2/8 , confidenceconfidenceconfidence = 2/3

我们需要的规则，它必须是一种强规则，而且要频繁。supportsupportsupport度量了一条规则的频繁程度，confidenceconfidenceconfidence度量了一条规则的强度。我们定义两个阈值来量化这条规则的频繁程度和强度：
minimumminimumminimum supportsupportsupport：σ
minimumminimumminimum confidenceconfidenceconfidence：Φ

Frequent itemset（频繁集）
一个itemset，它的support>σsupport > σsupport>σ

Strong rule（强规则）
一个规则x−>yx->yx−>y，它既要是频繁的 (support>σsupport > σsupport>σ)，而且要 confidence>Φconfidence > Φconfidence>Φ

任务是什么

当已知 Items，dataset，σ，ΦItems，dataset，σ，ΦItems，dataset，σ，Φ，我们要做的就是从datasetdatasetdataset中挖掘出类似于 x−>yx->yx−>y的所有的 Strong rule。
要找出所有的强规则，方法就是：

1. 找出所有的 frequentfrequentfrequent itemsetsitemsetsitemsets
2. 运用 frequentfrequentfrequent itemsetsitemsetsitemsets ，对于每一个frequentfrequentfrequent itemitemitem，生成它的所有的非空子集，然后利用这些非空子集找出所有可能的关联规则，然后对这些规则进行校验 supportsupportsupport 和 confidenceconfidenceconfidence。

例如：根据集合a,b,c{a,b,c}a,b,c，找出其所有可能的关联规则。

根据上面的2个步骤可以找出强规则。但是假如我们共有ddd种商品，那么所有可能的itemsetsitemsetsitemsets的个数就是2d−12^d-12d−1，这是一个指数级的数字，想象一下，商品的数量如果有成百上千种，那么itemsetitemsetitemset的数量是不可估计的。所以问题的关键就是，如何高效率的找出所有的 frequentfrequentfrequent itemsetsitemsetsitemsets，下面介绍的就是解决这个核心问题的一个算法： Apriori 算法

Apriori 算法

核心思想

首先介绍两个核心思想：

1. 一个频繁集的子集一定是频繁集，
   {Milk, Bread, Coke} is frequent -> {Milk, Coke} is frequent
2. 一个itemsetitemsetitemset不是频繁集，那么它的所有的超级一定不是频繁集，
   {Battery} is infrequent -> {Milk, Battery} is infrequent
   例如下图，我们知道B不是一个频繁集，那么所有标记为绿色的itemsetitemsetitemset都不是频繁集。

步骤与流程图

下面介绍Apriori的核心思路：
(1) 先生成某一个特定大小的itemsetsitemsetsitemsets，一般从1开始，如{牛奶}，{面包}，{巧克力}
(2) 扫描数据库，观察这些 itemsetsitemsetsitemsets 哪些是频繁的，即频繁集，不频繁的itemsetitemsetitemset直接舍弃
(3) 运用这些频繁集，组合成数量加1个大小的 itemsetsitemsetsitemsets（被称为 candidatecandidatecandidate itemsetsitemsetsitemsets 候选集），例如{牛奶，面包}，{面包，巧克力}，{牛奶，巧克力}。然后重复上面的第(2)步扫描数据库，舍弃不频繁的itemsetsitemsetsitemsets，之后重复(2),(3)步。itemsetsitemsetsitemsets的大小逐一增加。
(4) 综上，核心思想就是尽量避免去生成不频繁的candidatecandidatecandidate itemsetsitemsetsitemsets

算法流程图：
定义：
CkC_kCk​：大小为kkk的candidatecandidatecandidate itemsetsitemsetsitemsets
LkL_kLk​：大小为kkk的frequentfrequentfrequent itemsetitemsetitemset

首先找出所有的frequentfrequentfrequent itemsitemsitems，长度是一。里面的小循环是扫描数据库中的每一条记录，根据已知的candidatecandidatecandidate itemsetitemsetitemset，我们在每一条记录中查看一下是否存在这样一个candidatecandidatecandidate itemsetitemsetitemset，如果存在，那么就count++count++count++ 计数，也就是说在所有的记录中，有多少条记录包括这样一个特定的itemsetitemsetitemset。里面的循环走完之后，我们就开始过滤操作，比较一下supportsupportsupport，如果> 我们之前设置的阈值σσσ，那么就把这个itemsetitemsetitemset留下，否则抛弃。然后外面的大循环，是把这些频繁集进行组合，组合成更大的candidatecandidatecandidate itemsetsitemsetsitemsets，生成可能频繁的候选集，步数是1。

上面的算法中，最为关键的一步就是如何从LkL_kLk​生成Ck+1C_{k+1}Ck+1​
LkL_kLk​是一个集合，集合里面所有的 itemsetitemsetitemset 中的 itemitemitem 个数都是一样的，都是kkk个，而且这些 itemsetitemsetitemset都是频繁的
Ck+1C_{k+1}Ck+1​也是一个集合，其中的 itemsetitemsetitemset 中的itemitemitem 个数都是比LkL_kLk​中的多一个
如何从LkL_kLk​生成Ck+1C_{k+1}Ck+1​，要做到必须把所有的频繁集都找到，同时又不能生成太多的冗余的

用下面这个例子进行讲述：
已知L1L_1L1​：{1，2，3，4，5}，L2L_2L2​：{ {1，2}，{2，3} }，即1，2，3，4，5都是频繁的，{1，2}，{2，3}也是频繁的。如何利用L1L_1L1​，L2L_2L2​生成 C3C_3C3​？

如何找到候选集

方法一
把一个频繁的加入到两个频繁的，就生成了所有3个的可能频繁的 itemsetitemsetitemset

所以用这个方法得到的C3C_3C3​就是{ {1，2，3}，{1，2，4}，{1，2，5}，{2，3，4}，{2，3，5} }
这个方法得到的C3C_3C3​不能说是错误的，但是效率太低。例如我们看到C3C_3C3​中的 {1，2，5}，其中它的子集 {1，5}是不在L2L_2L2​当中的，说明{1，5}是不频繁的，而 {1，2，5} 是它的超集，则说明 {1，2，5} 也是不频繁的。因此我们可以清楚的看到方法一生成的C3C_3C3​会有大量的冗余。

方法二
从L2L_2L2​ 中找两个itemsetitemsetitemset，xxx和yyy，这两个itemsetitemsetitemset要满足一个条件，他们中的itemitemitem只有一个是不同的。然后把xxx和yyy拼起来。

用方法二，我们发现我们L2L_2L2​中的两个itemsetitemsetitemset，它们的2是相同的，1和3是不同的，就可以得到C3C_3C3​就是{ {1，2，3} }。方法二的效率要比方法一的效率高很多。但是我们仔细观察会发现，这个{1，2，3}也是不频繁的，因为它的子集{1，3}不在L2L_2L2​当中，所以{1，3}也是不频繁的。

方法三
首先对所有的 itemitemitem 做一个排序，然后从L2L_2L2​ 中找两个itemsetitemsetitemset，xxx和yyy，这两个itemsetitemsetitemset要满足一个条件，xxx和yyy的前k−1k-1k−1项都是相同的，第kkk项是不同的，然后把xxx和yyy第kkk项与前k−1k-1k−1项拼起来，组成k+1k+1k+1大小的itemsetitemsetitemset。

用方法三我们就可以发现，对于上述的L2L_2L2​我们找不出满足方法三的两个itemset，因此得到C3C_3C3​是 {}
如果L2L_2L2​是{ {1，2}，{1，3}，{2，3} }，生成的C3C_3C3​就是 { {1，2，3} }，因为我们可以找到两个满足方法三的itemsetitemsetitemset {1，2} 和 {1，3} ，他们的第一位都是1，第2位不相同分别是2和3，由此可以得到C3C_3C3​中的一个满足条件的itemsetitemsetitemset {1，2，3}

但是如果L2L_2L2​是{ {1，2}，{1，3} }，生成的C3C_3C3​也是 { {1，2，3} }，但是我们清楚地知道这个生成的{1，2，3}是不可能频繁的，因为它的子集{2，3}不在L2L_2L2​当中。所以虽然方法三是效率最高的，但是我们在生成了C3C_3C3​之后也要做进一步的验证，即验证它的子集是否都在L2L_2L2​中。

下面是一个具体的例子：

python代码实现

下面使用python实现上面的Apriori算法，其中通过频繁集生成候选集采用的是方法三。

计算支持率

#计算支持率
def support(item,T):n=len(T)   # 事务集合的长度l=len(item)count=0for x in T:if  len(set(x)&set(item)) == l:   # 判断是否有交集，有交集，分子加1count=count+1return  1.0*count/n

生成候选集

def produce_Candinate(L, k):candinate = []   # 首先创建一个空的集合for x in range(len(L)):   # 每两个元素集合进行比较for y in range(x + 1, len(L)):flag = Truex_item = L[x]y_item = L[y]for i in range(k):if x_item[k - 1] == y_item[k - 1]:   # 如果两个元素集合的最后一项相同 ，候选集为空flag = Falsebreakelif x_item[i] != y_item[i] and i < k-1: # 如果前面 k-1 项有不相同的，候选集为空flag = Falseif flag:temp = x_item.copy()temp.append(y_item[k - 1])  # 将q中的最后一项添加到p中temp.sort()if has_frequent_subset(temp, L, k):candinate.append(temp)print("候选", k + 1, "-项集：", candinate)return candinate# 判断候选集子集是否是频繁集
def has_frequent_subset(c, freq_items, n):num = len(c) * n  # count = 0flag = Falsefor c_item in freq_items:   if set(c_item).issubset(set(c)):    #判断上一层的频繁集中的每一项是否是计算出来的候选集的子集count += n   # 如果是就把count加上nif count == num:     # 如果最后相等（候选集的每个子集都在频繁集当中），就说明这个候选集中的每个子集都是频繁集flag = Truereturn flag

Apriori算法挖掘频繁项集

#Apriori算法挖掘频繁项集
def Apriori(T,min):k=1#结果集，用于保存所有的频繁集out=[]#生成1-候选集C=[]for x in T:C=list(set(x)|set(C))#生成1频繁项集F=[]for i in C:if support(list(i),T) >= min:F.append([i])#迭代while (len(F)>0):out.append(F)#生成k+1候选集C=produce_Candinate(F,k)#生成k+1频繁项集F=[]for i in C:if support(i,T) >=min:F.append(i)k=k+1return out

主函数调用

T = [['A','B','C','D'], ['B','C','E'], ['A','B','C','E'], ['B','D','E'], ['A','B','C','D'] ]
out = Apriori(T,0.3)
print('频繁项集')
for i in out:print(i)

打印结果

以上就是Apriori算法的全部内容，其中知识点部分参考了b站清华大学-数据挖掘 ，代码部分参考了多篇文章，并加入了一些的注释和自己的理解，有疑问欢迎评论区讨论！