一、应用背景

1.1 啤酒与尿布

沃尔玛在分析销售记录时，发现啤酒和尿布经常一起被购买，于是他们调整了货架，把两者放在一起，结果真的提升了啤酒的销量。

原因解释：爸爸在给宝宝买尿布的时候，会顺便给自己买点啤酒？

通过上述的案例我们找到了找到类似的规则：啤酒→尿布；这些规则出现的频次很高，关联性很强。

关联规则的目的是利用一些度量指标来分辨数据库中存在的强规则。也就是说关联规则挖掘是用于知识发现，而非预测，所以是属于无监督的机器学习方法。

二、关联规则的基础概念

如何从所有可能规则的集合中选择感兴趣的规则？
需要利用一些度量方法来筛选和过滤，比较有名的度量方法是最小支持度和最小置信度。

比如我们有以下的商品订单：
在这里插入图片描述

2.1 频繁集（Frequent Item Sets）

频繁集：经常一起出现的事件集合。

2.2 支持度（Support）

2.2.1 支持度定义

支持度其实就是计算频繁集占整个集合的比例，指的是某个商品组合出现的次数与总次数之间的比例，如果某个项原本的支持度很低，即使关联性很强，实际的意义可能不大。支持度越高，代表越频繁，后继分析的可靠性越高。

在这个例子中，我们能看到“牛奶 + 尿布”出现了 4 次，那么这 5 笔订单中“牛奶 + 尿布”的支持度就是 4/5=0.8。

同样“牛奶 + 面包”出现了 3 次，那么这 5 笔订单中“牛奶 + 面包”的支持度就是 3/5=0.6

2.2.2 最小支持度

最小支持度minSupport：自定义支持度的阈值，超过阈值的集合就是频繁集。

在上述案例中，若定义minSupport=0.7
Support(牛奶 ∩ \cap ∩尿布)=0.8 > 0.7，所以Set(牛奶 ∩ \cap ∩尿布)是频繁集
Support(牛奶 ∩ \cap ∩面包)=0.6 < 0.7，所以Set(牛奶 ∩ \cap ∩面包)不是频繁集
虽然Support(牛奶 ∩ \cap ∩尿布)是频繁的，是否就能让我们相信顾客购买牛奶的同时一定会购买尿布呢？于是，统计学用置信度来量化这个关系硬度。

2.3 置信度（Confidence）

2.3.1 置信度定义

条件概率，买了X的人又买了Y的比例有多少，表示关联性的强弱

置信度confidence： c o n f ( X − > Y ) = s u p p ( X ∩ Y ) s u p p ( X ) conf(X->Y) = \frac{supp(X \cap Y)}{supp(X)} conf(X−>Y)=supp(X)supp(X∩Y)​

例如：
conf(牛奶 ∩ \cap ∩面包)= s u p p ( 牛 奶 ∩ 面 包 ) s u p p ( 牛 奶 ) \frac{supp(牛奶\cap面包)}{supp(牛奶)} supp(牛奶)supp(牛奶∩面包)​=(3/5)/(4/5)=3/4=0.75
理解为顾客购买牛奶前提下，3/4概率会同时购买面包。

2.3.2 最小置信度

最小置信度minConf：自定义的置信度阈值，超过阈值的才是可信的。

如定义minConf=0.7，
则conf(牛奶 ∩ \cap ∩面包)=0.75 > 0.7，表示足以令人相信，顾客购买牛奶后，会同时购买面包。反之则是不可信的。

2.3.3 提升度（Lift）

商品A的出现，对商品B的出现概率提升的程度

定义： l i f t ( X ∩ Y ) = c o n f ( X ∩ Y ) s u p p ( Y ) = s u p p ( X ∩ Y ) s u p p ( X ) ∗ s u p p ( Y ) lift(X\cap Y) = \frac{conf(X \cap Y)}{supp(Y)}=\frac{supp(X \cap Y)}{supp(X)*supp(Y)} lift(X∩Y)=supp(Y)conf(X∩Y)​=supp(X)∗supp(Y)supp(X∩Y)​

提升度的三种可能：

提升度(x→y)>1：代表有提升；（数据正相关）
提升度(x→y)=1：代表没有提升，也没有下降；
提升度(x→y)<1：代表有下降。

提升度用于提前进行一次频繁集的数据筛选。
提升度仅仅是用来标识关系相关性，并不影响关联规则的强弱。

例如：
lift(牛奶 ∩ \cap ∩面包)= s u p p ( 牛 奶 ∩ 面 包 ) s u p p ( 牛 奶 ) ∗ s u p p ( 面 包 ) \frac{supp(牛奶\cap面包)}{supp(牛奶)*supp(面包)} supp(牛奶)∗supp(面包)supp(牛奶∩面包)​=0.6/ (0.8*0.8)=0.9375

可以理解为牛奶和面包购买时负相关的，并不倾向被同时购买。在专业定义上这个量化因素叫提升度，通常需要选择正相关的更具备分析意义。

三、关联规则算法

关联算法主要有：Apriori, E-Clat, FP-Growth

3.1 Apriori

美[əpriˈɔri]
Apriori算法就是查找频繁项集(frequent itemset)的过程。
Apriori使用逐层搜索的迭代方法，“K-1项集”用于搜索“K项集”。

项集：英文叫 itemset，它可以是单个的商品，也可以是商品的组合。
频繁项集：支持度大于等于最小支持度(Min Support)阈值的项集。
非频繁项集：支持度小于最小支持度的项集

3.1.1 Apriori算法是如何运算（结合案例说明）

我们把上面案例中的商品用ID来代表，牛奶、面包、尿布、可乐、啤酒、鸡蛋的商品ID分别设置为1-6，上面的数据表可以变为：
在这里插入图片描述
假设我们随机指定最小支持度是 50%，也就是 0.5。

首先，我们先计算单个商品的支持度，也就是得到 K=1 项的支持度：
在这里插入图片描述
因为最小支持度是 0.5，所以你能看到商品 4、6 是不符合最小支持度的，不属于频繁项集，于是经过筛选商品的频繁项集就变成：
在这里插入图片描述
在这个基础上，我们将商品两两组合，得到 k=2 项的支持度：
在这里插入图片描述
我们再筛掉小于最小值支持度0.5的商品组合，可以得到：
在这里插入图片描述
我们再将商品进行 K=3 项的商品组合，可以得到：
在这里插入图片描述
将其中支持度小于0.5的剔除，可以得到：
在这里插入图片描述
通过上面这个过程，我们可以得到 K=3 项的频繁项集{1,2,3}，也就是{牛奶、面包、尿布}的组合。因此我们就得到了 牛奶、面包、尿布具有关联

3.1.2 Apriori算法流程

Apriori算法的流程：
Step1，K=1，计算K项集的支持度；
Step2，筛选掉小于最小支持度的项集，得到频繁k项集；
Step3，如果项集为空，则对应K-1项集的结果为最终结果。 否则，基于频繁k项集，K=K+1，重复1-3步。

在这里插入图片描述

根据上述案例中的Apriori算法运算过程，元素个数为6，全部遍历的话需要计算63个非空set集合。使用Apriori算法，仅计算了15次。

3.1.3 总结

在寻找关联规则时，对于含有N项（列）数据集，如果两两之间或者任意项的组合，共有 2 n − 1 2^n-1 2n−1个子集项，要想全部计算其所有子集的关联度，数据处理量相当大，而且有很多关联性很弱的项之间会被反复计算。因此找到有效的频繁集非常重要，而Apriori算法就是帮助找到频繁集的一个通用算法。

Apriori算法的性质：
性质1：频繁项集的子集必为频繁项集如果{B，C}是频繁的，那么{B}，{C}也一定是频繁的。
性质2：非频繁项集的超集一定是非频繁的。如果{A, B}是非频繁的，那么{A, B, C}，{A, B, C, D}也一定是非频繁的。从而不用再计算这些非频繁集的支持度。

在数据较多时候，频繁集数量较少时，使用Apriori算法可以减少很多计算。

3.1.4 python第三方库

使用工具包：
from efficient_apriori import apriori
或者：
from mlxtend.frequent_patterns import apriori
from mlxtend.frequent_patterns import association_rules

from efficient_apriori import apriori
# 设置数据集
transactions = [('牛奶','面包','尿布'),
		('可乐','面包', '尿布', '啤酒'),
		('牛奶','尿布', '啤酒', '鸡蛋'),
		('面包', '牛奶', '尿布', '啤酒'),
		('面包', '牛奶', '尿布', '可乐')]
# 挖掘频繁项集和频繁规则
itemsets, rules = apriori(transactions, min_support=0.5,  min_confidence=1)
print("频繁项集：", itemsets)
print("关联规则：", rules)

频繁项集： {1: {(‘牛奶’,): 4, (‘尿布’,): 5, (‘面包’,): 4, (‘啤酒’,): 3}, 2: {(‘尿布’, ‘牛奶’): 4, (‘尿布’, ‘面包’): 4, (‘牛奶’, ‘面包’): 3, (‘啤酒’, ‘尿布’): 3}, 3: {(‘尿布’, ‘牛奶’, ‘面包’): 3}}

关联规则： [{牛奶} -> {尿布}, {面包} -> {尿布}, {啤酒} -> {尿布}, {牛奶, 面包} -> {尿布}]

3.2 E-Clat算法

3.2.1 算法介绍

等价类变换算法（Equivalence CLAss Transformation，Eclat）

在Apriori算法中，包含集合元素的数量，决定了需要遍历的层级。在处理一些层级特别多的数据时，需要尽量减少层级。
E-Clat和Apriori相比较，最大的特点在于数据进行了一次转置，从而达到降低扫描层级N的效果，其他逻辑没有实质变化。

当数据的列数（比如案例中的商品种类）大于数据的行数时，通过转置可以减少扫描次数，然后通过Apriori相同的思想，找到频繁集。

核心思想：
倒排

3.2.2 算法实现

  1. 转置前：设订单编号为i，商品种类为N，并且i<N。
订单编号 牛奶 面包 尿布 啤酒 鸡蛋 可乐
1 1 1 1 0 0 0
2 0 1 1 1 0 1
3 1 0 1 1 1 0
4 1 1 1 1 0 0
5 1 1 1 0 0 1
抽象成数据集项：
订单1(‘牛奶’,‘面包’,‘尿布’)
订单2(‘可乐’,‘面包’, ‘尿布’, ‘啤酒’)
订单i(…)

假设要计算Set(牛奶，面包)出现的次数，就需要把遍历订单i判断，(牛奶，面包)是否同时存在，需要扫描n次。

2.转置后：

订单编号 1 2 3 4 5
牛奶 1 0 1 1 1
面包 1 1 1 0 1
尿布 1 1 1 1 1
啤酒 0 1 1 1 1
鸡蛋 0 0 1 1 0
可乐 0 1 0 0 1
抽象成数据集项：
牛奶（1，3，4，5）
面包（1，2，3，5）
尿布（1，2，3，4，5）
商品N（…）

假设要判断，每次在Set(牛奶，面包)出现的次数，只需要把以订单i循环遍历，判断订单i是否在Set(牛奶)&&Set(面包)中，需要判断Count(i)=i次

3.通过Apriori算法相同的思想，找到频繁集：
当i < N时，通过转置可以减少扫描次数，提升效率。

3.2.3 总结

1、Apriori才有规则的生成，Eclat只是频繁集生成算法，是广度优先遍历的。
2、可以利用Eclat算法，类比完成规则的生成：因为一个集合的一个子集的置信度小与阈值，那么包含它的全部集合将不满足此置信度阈值。

3.3 FP-Growth算法

3.3.1 算法介绍

Apriori 在计算的过程中有以下几个缺点：
1、可能产生大量的候选集。因为采用排列组合的方式，把可能的项集都组合出来了；
2、每次计算都需要重新扫描数据集，来计算每个项集的支持度。

所以 Apriori 算法会浪费很多计算空间和计算时间，为此人们提出了 FP-Growth 算法：

1、创建了一棵 FP 树来存储频繁项集。在创建前对不满足最小支持度的项进行删除，减少了存储空间。
2、整个生成过程只遍历数据集 2 次，大大减少了计算量。

所以在实际工作中，我们常用 FP-Growth 来做频繁项集的挖掘。

3.3.2 FP Tree数据结构

为了减少I/O次数，FP Tree算法引入了一些数据结构来临时存储数据。这个数据结构包括三部分，如下图所示：
在这里插入图片描述
第一部分是一个项头表。里面记录了所有的1项频繁集出现的次数，按照次数降序排列。比如上图中B在所有10组数据中出现了8次，因此排在第一位，这部分好理解。
第二部分是FP Tree，它将原始数据集中剔除了支持度小于阈值的项之后的数据，映射到了内存中的一颗FP树。
第三部分是节点链表。所有项头表里的1项频繁集都是一个节点链表的头，它依次指向FP树中该1项频繁集出现的位置。这样做主要是方便项头表和FP Tree之间的联系查找和更新。

3.3.3 FP-Growth挖掘频繁项集的过程

3.3.3.1 项头表的建立

FP树的建立需要首先依赖项头表的建立。首先我们看看怎么建立项头表。
流程：
　　我们第一次扫描数据，得到所有频繁一项集的的计数。然后删除支持度低于阈值的项，将1项频繁集放入项头表，并按照支持度降序排列。接着第二次也是最后一次扫描数据，将读到的原始数据剔除非频繁1项集，并按照支持度降序排列。

例子：
　　上面这段话很抽象，我们用下面这个例子来具体讲解。我们有10条数据，首先第一次扫描数据并对1项集计数，我们发现F，O，I，L，J，P，M, N都只出现一次，支持度低于20%的阈值，因此他们不会出现在下面的项头表中。剩下的A,C,E,G,B,D,F按照支持度的大小降序排列，组成了我们的项头表。
　　
　　接着我们第二次扫描数据，对于每条数据剔除非频繁1项集，并按照支持度降序排列。比如数据项ABCEFO，里面O是非频繁1项集，因此被剔除，只剩下了ABCEF。按照支持度的顺序排序，它变成了ACEBF。其他的数据项以此类推。为什么要将原始数据集里的频繁1项数据项进行排序呢？这是为了我们后面的FP树的建立时，可以尽可能的共用祖先节点。
　　
　　通过两次扫描，项头表已经建立，排序后的数据集也已经得到了，下面我们再看看怎么建立FP树。
　　　　在这里插入图片描述

3.3.3.2 FP Tree的建立

流程：
　　有了项头表和排序后的数据集，我们就可以开始FP树的建立了。开始时FP树没有数据，建立FP树时我们一条条的读入排序后的数据集，插入FP树，插入时按照排序后的顺序，插入FP树中，排序靠前的节点是祖先节点，而靠后的是子孙节点。如果有共用的祖先，则对应的公用祖先节点计数加1。插入后，如果有新节点出现，则项头表对应的节点会通过节点链表链接上新节点。直到所有的数据都插入到FP树后，FP树的建立完成。

例子：
　　首先，我们插入第一条数据ACEBF，如下图所示。此时FP树没有节点，因此ACEBF是一个独立的路径，所有节点计数为1, 项头表通过节点链表链接上对应的新增节点。
在这里插入图片描述
　　接着我们插入数据ACG，如下图所示。由于ACG和现有的FP树可以有共有的祖先节点序列AC，因此只需要增加一个新节点G，将新节点G的计数记为1。同时A和C的计数加1成为2。当然，对应的G节点的节点链表要更新。
在这里插入图片描述
　　同样的办法可以更新后面8条数据，如下8张图。由于原理类似，这里就不多文字讲解了，大家可以自己去尝试插入并进行理解对比。相信如果大家自己可以独立的插入这10条数据，那么FP树建立的过程就没有什么难度了。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

3.3.3.3 FP Tree的挖掘

流程：
　　得到了FP树和项头表以及节点链表，我们首先要从项头表的底部项依次向上挖掘。对于项头表对应于FP树的每一项，我们要找到它的条件模式基。所谓条件模式基是以我们要挖掘的节点作为叶子节点所对应的FP子树。得到这个FP子树，我们将子树中每个节点的的计数设置为叶子节点的计数，并删除计数低于支持度的节点。从这个条件模式基，我们就可以递归挖掘得到频繁项集了。

例子：
　　我们看看先从最底下的F节点开始，我们先来寻找F节点的条件模式基，由于F在FP树中只有一个节点，因此候选就只有下图左所示的一条路径，对应{A:8,C:8,E:6,B:2, F:2}。我们接着将所有的祖先节点计数设置为叶子节点的计数，即FP子树变成{A:2,C:2,E:2,B:2, F:2}。一般我们的条件模式基可以不写叶子节点，因此最终的F的条件模式基如下图右所示。
在这里插入图片描述
　　通过它，我们很容易得到F的频繁2项集为{A:2,F:2}, {C:2,F:2}, {E:2,F:2}, {B:2,F:2}。递归合并二项集，得到频繁三项集为{A:2,C:2,F:2}，{A:2,E:2,F:2},…还有一些频繁三项集，就不写了。当然一直递归下去，最大的频繁项集为频繁5项集，为{A:2,C:2,E:2,B:2,F:2}。
　　
　　F挖掘完了，我们开始挖掘D节点。D节点比F节点复杂一些，因为它有两个叶子节点，因此首先得到的FP子树如下图左。我们接着将所有的祖先节点计数设置为叶子节点的计数，即变成{A:2, C:2,E:1 G:1,D:1, D:1}此时E节点和G节点由于在条件模式基里面的支持度低于阈值，被我们删除，最终在去除低支持度节点并不包括叶子节点后D的条件模式基为{A:2, C:2}。通过它，我们很容易得到F的频繁2项集为{A:2,D:2}, {C:2,D:2}。递归合并二项集，得到频繁三项集为{A:2,C:2,D:2}。D对应的最大的频繁项集为频繁3项集。
在这里插入图片描述
　　同样的方法可以得到B的条件模式基如下图右边，递归挖掘到B的最大频繁项集为频繁4项集{A:2, C:2, E:2,B:2}。
在这里插入图片描述
　　继续挖掘G的频繁项集，挖掘到的G的条件模式基如下图右边，递归挖掘到G的最大频繁项集为频繁4项集{A:5, C:5, E:4,G:4}。
在这里插入图片描述
　　E的条件模式基如下图右边，递归挖掘到E的最大频繁项集为频繁3项集{A:6, C:6, E:6}。
在这里插入图片描述
　　C的条件模式基如下图右边，递归挖掘到C的最大频繁项集为频繁2项集{A:8, C:8}。
在这里插入图片描述
　　至于A，由于它的条件模式基为空，因此可以不用去挖掘了。
　　至此我们得到了所有的频繁项集，如果我们只是要最大的频繁K项集，从上面的分析可以看到，最大的频繁项集为5项集。包括{A:2, C:2, E:2,B:2,F:2}。

通过上面的流程，相信大家对FP Tree的挖掘频繁项集的过程也很熟悉了。

3.3.4 FP Tree算法归纳

这里我们对FP Tree算法流程做一个归纳。FP Tree算法包括三步：

1）扫描数据，得到所有频繁一项集的的计数。然后删除支持度低于阈值的项，将1项频繁集放入项头表，并按照支持度降序排列。

2）扫描数据，将读到的原始数据剔除非频繁1项集，并按照支持度降序排列。

3）读入排序后的数据集，插入FP树，插入时按照排序后的顺序，插入FP树中，排序靠前的节点是祖先节点，而靠后的是子孙节点。如果有共用的祖先，则对应的公用祖先节点计数加1。插入后，如果有新节点出现，则项头表对应的节点会通过节点链表链接上新节点。直到所有的数据都插入到FP树后，FP树的建立完成。

4）从项头表的底部项依次向上找到项头表项对应的条件模式基。从条件模式基递归挖掘得到项头表项项的频繁项集。

5）如果不限制频繁项集的项数，则返回步骤4所有的频繁项集，否则只返回满足项数要求的频繁项集。

3.3.5 python第三方库

import fptools as fp

transactions = [('牛奶','面包','尿布'),
		('可乐','面包', '尿布', '啤酒'),
		('牛奶','尿布', '啤酒', '鸡蛋'),
		('面包', '牛奶', '尿布', '啤酒'),
		('面包', '牛奶', '尿布', '可乐')]
#fis = [iset for iset in fp.frequent_itemsets(transactions, 2)]
mfis = [iset for iset in fp.maximal_frequent_itemsets(transactions, 2)]
#print(fis)
print(mfis)

[[‘尿布’, ‘面包’, ‘可乐’], [‘尿布’, ‘面包’, ‘啤酒’], [‘尿布’, ‘牛奶’, ‘啤酒’], [‘尿布’, ‘面包’, ‘牛奶’]]

3.3.6 总结

FP Tree算法改进了Apriori算法的I/O瓶颈，巧妙的利用了树结构，这让我们想起了BIRCH聚类，BIRCH聚类也是巧妙的利用了树结构来提高算法运行速度。利用内存数据结构以空间换时间是常用的提高算法运行时间瓶颈的办法。

在实践中，FP Tree算法是可以用于生产环境的关联算法，而Apriori算法则做为先驱，起着关联算法指明灯的作用。除了FP Tree，像GSP，CBA之类的算法都是Apriori派系的。

参考资料：
Apriori算法：
http://www.cnblogs.com/qwertWZ/p/4510857.html
FP-Growth算法：
http://www.cnblogs.com/datahunter/p/3903413.html
https://www.cnblogs.com/zhengxingpeng/p/6679280.html

# 数据挖掘 # 机器学习 # python
Logo
魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

cover

量化挑战赛冠军专访：4小时啃下W4A8量化，我靠的是这些经验

avatar 魔乐社区
cover

替你试过了，消费级显卡可以跑的开源文生图SOTA模型，顶级渲染、高密度文本绘图

avatar 魔乐社区
cover

「极限压缩 量化未来」Modelers GeekDay上海站圆满落幕

avatar 魔乐社区