关联规则挖掘

简介

综合转载：

• 【理论】挖掘关联规则

关联规则

沃尔玛商店的营销人员发现了一个现象：啤酒与尿布的销量在周末总会同时出现增长。他们对这个现象进行了分析和讨论，并在商场内进行观察，他们发现这些顾客有几个共同的特点：

• 一般是周末出现这种情况。
• 购买者以已婚男士为主。
• 他们家中有孩子且不到两岁，有尿不湿的刚需。

从中受到启发，他们对超市的物品摆放位置进行了调整，将啤酒与尿布摆放在一起，同时将牛肉干等一些简便的下酒食品也摆放在一起。这样全年下来，营业额显著增加。

上面这个故事称为购物篮分析，是一种关联规则。

关联规则是指从一份资料库中（如销售记录）中发现某些特征（如商品种类）之间的联系。

关联规则挖掘可以让我们从数据集中发现项与项之间的关系，它在我们的生活中有很多应用场景，“购物篮分析”就是一个常见的场景，这个场景可以从消费者交易记录中发掘商品与商品之间的关联关系，进而通过商品捆绑销售或者相关推荐的方式带来更多的销售量。所以关联规则挖掘是个非常有用的技术。

下面是几名客户购买的商品列表：

下面先介绍几个概念。

【定义1】 项集（itemset）是项的集合，也就是一个商品或多个商品的组合。

包含k个项的项集称为k-项集。例如{面包}是1-项集，{牛奶，面包}是2-项集。

【定义2】 项集的支持度

对于项集X，用$\text{count}(X)$表示交易集合T中包含项集X的交易的数量，用N表示总的交易记录数 ，则项集X的支持度的计算公式是

$$\operatorname{support}(X)=\frac{\operatorname{count}(X)}{N}$$

项集的支持度是一个或几个商品出现的次数与交易总数之间的比例，支持度可以理解为物品当前流行程度。支持度的值越大越好。在上面顾客购买的商品列表中，我们能看到“牛奶”出现了 4 次，那么这 5 笔交易中1-项集{牛奶}的支持度就是 4/5=0.8。同样{牛奶，面包} 同时出现了 3 次，那么这 5 笔订单中，2-项集{牛奶，面包} 的支持度就是 3/5=0.6。

【定义3】 项集的最小支持度与频繁项集

发现关联规则要求项集必须满足最小阈值，最小阈值称之为项集的最小支持度，记为$s u p_{\min }$。从统计意义上讲，它表示用户关心的关联规则必须满足的最低出现概率。最小支持度用于衡量规则需要满足的最低重要性，需要人为指定。

支持度大于或等于$s u p_{\min }$的项集称为频繁项集(frequent itemset)。如果k-项集满足$s u p_{\min }$，称为k-频繁项集，记作$L[k]$。频繁项集就是支持度大于等于最小支持度的项集，就是频繁的一起出现的物品的集合。所以小于最小值支持度的项目就是非频繁项集，而大于等于最小支持度的的项集就是频繁项集。

假设指定最小支持度是 0.5，在上面的顾客购买的商品列表中，1-项集{面包}的支持度等于0.6，其大于0.5，则{面包}是频繁项集。4-项集{可乐，面包，尿布，啤酒}的支持度是0.25，小于0.5，其不是频繁项集。

【定义4】关联规则

关联规则是一个蕴含式$X \Rightarrow Y$ ，即由项集X可以推导出项集Y。

其中X，Y都是项集，且$X \cap Y \neq \phi$。X称为规则的条件，也称为前项，Y称为规则结果，也称为后项。

关联规则表示在一次交易中，如果出现项集X，则项集Y也会按照一定概率出现。

【定义5】关联规则的支持度

对于关联规则$X \Rightarrow Y$ ，规则R的支持度是交易中同时包含X和Y的交易与所有交易之比，记为$\operatorname{support}(X \Rightarrow Y)$，其计算公式是

$$\operatorname{support}(X \Rightarrow Y)=\frac{\operatorname{count}(X ∩ Y)}{N}$$

关联规则的支持度反映了X和Y 中所含的商品在全部交易中同时出现的频率。关联规则的支持度的值越大越好。由于关联规则必须由频繁集产生，所以规则的支持度其实就是频繁集的支持度，即

$$\operatorname{support}(X \Rightarrow Y)=\operatorname{support}(X ∩ Y)=\frac{\operatorname{count}(X ∩ Y)}{|D|}$$

【定义6】关联规则的置信度

对于关联规则$X \Rightarrow Y$的置信度是指同时包含X和Y的交易与包含X的交易之比，记为$\text { confidence }(X \Rightarrow Y)$, 其计算公式是

$$\operatorname{confidence}(X \Rightarrow Y)=\frac{\operatorname{support}(X ∩ Y)}{\operatorname{support}(X)}$$

关联规则的置信度反映了当交易中包含项集X 时，项集Y 同时出现的概率。关联规则的支持度和置信度分别反映了当前规则在整个数据库中的统计重要性和可靠程度。置信度的值越大越好。

关联规则置信度指的就是当你购买了商品 A，会有多大的概率购买商品 B。置信度是个条件概率，就是说在 A 发生的情况下，B 发生的概率是多少。

例如在上面的顾客购买的商品列表中，置信度confidence（牛奶 ⇒ 啤酒）=2/4=0.5，代表如果购买了牛奶，有0.5的概率会购买啤酒。置信度confidence（啤酒 ⇒ 牛奶）=2/3=0.67，代表如果购买了啤酒，有0.67的概率会购买牛奶。

【定义7】关联规则的提升度

关联规则的提升度

$$\operatorname{lift}(X \Rightarrow Y)=\frac{\text { confidence }(X \Rightarrow Y)}{\operatorname{support}(Y)}$$

提升度表示关联规则的强弱，值越大表示规则越强，该值越大越好。提升度$\text { lift }(X \Rightarrow Y)$是用来衡量 A 出现的情况下，是否会对 B 出现的概率有所提升。所以提升度有三种可能：

• 提升度$\text { lift }>1$代表有提升，越高表明正相关性越高
• 提升度$\text { lift }=1$代表有没有提升，也没有下降，表明没有相关性
• 提升度$\text { lift }<1$代表有下降，越低表明负相关性越高

【定义8】关联规则的部署能力

如果关联规则$X \Rightarrow Y$，部署能力是前项支持度减去规则支持度，即

$$\operatorname{support}(X)-\operatorname{support}(X ∩ Y)$$

部署能力越趋近1，表示前项和后项的负向关联越大。越小越好。

【定义9】关联规则的最小支持度和最小置信度

关联规则的最小支持度记为$\text{sup}_{\min }$，它用于衡量规则需要满足的最低重要性，需要人为指定。

关联规则的最小置信度记为$\operatorname{conf}_{\text{min}}$，它表示关联规则需要满足的最低可靠性，需要人为指定。

【定义10】强关联规则

如果关联规则$X \Rightarrow Y$满足$\operatorname{support}(X \Rightarrow Y) \geq \sup _{\min }$且 $\text{confidence}(X \Rightarrow Y) \geq \operatorname{conf}_{\min }$，则称规则$X \Rightarrow Y$为强关联规则，否则为弱关联规则。

挖掘关联规则时，产生的规则要经过$\operatorname{sup}_{\min }$和$\operatorname{conf}_{\min }$的衡量，筛选出来的强关联规则才能用于指导商家的决策。

我们在做商品推荐的时候，重点考虑的是提升度，因为提升度代表的是“商品 A 的出现，对商品 B 的出现概率提升的”程度。

挖掘关联规则

发现物品间的关联规则也就是要寻找物品之间的潜在关系。要寻找这种关系，有两个步骤：

• 找出频繁项集。比如一个超市的频繁项集可能有 {啤酒,尿布}，{鸡蛋,牛奶}，{香蕉,苹果}
• 在频繁项集的基础上，使用关联规则算法找出其中物品的关联结果

简单来说，就是先找频繁项集，再找关联的物品。

下面先介绍如何用Apriori算法找出频繁项集，然后介绍在频繁项集的基础上找出物品的关联规则。

Apriori 算法

Apriori 算法是挖掘关联规则的频繁项集算法，其实就是查找频繁项集的过程。

Apriori算法有一条重要性质：一个频繁项集的所有非空子集也是频繁项集。其逆否命题是：如果一个项集不是频繁项集，那么它的扩集也不是频繁项集。或者说，如果一个项集的子集不是频繁项集，则该项集也不是频繁项集。

因为假设support(X)小于最小支持度阈值，当有元素A添加到I中时，结果项集（X∩Y）不可能比X出现次数更多，即support(X∩Y)也小于最小支持度阈值。因此X∩Y也不是频繁的。

例如，如果2-项集｛A, B｝的支持度小于阈值，则它的扩集3-项集｛A, B, C｝的支持度也会小于阈值。

Apriori算法使用频繁项集的先验知识，使用一种称作逐层搜索的迭代方法，k项集用于探索(k+1)项集。首先，通过扫描交易记录，找出所有的频繁1-项集，该集合记为L1，然后利用L1找频繁2-项集的集合L2，然后找L2找L3，以此类推，直到不能再找到任何频繁k-项集。最后再在所有的频繁集中找出强规则，即产生用户感兴趣的关联规则。

Apriori 算法分为连接步和过滤步。

连接步

若有两个k-1项集，每个项集按照“属性-值”（一般按值）的字母顺序进行排序。如果两个k-1项集的前k-2个项相同，而最后一个项不同，则说明它们是可连接的，即可连接生成k项集。

例如有两个3项集：｛A, B, C｝和{A, B, D}，这两个3项集就是可连接的，它们可以连接生成4项集｛A, B, C, D｝。

又如两个3项集｛A, B, C｝和｛A, D, E｝，这两个3项集是不能连接生成4项集的。

过滤步

如果一个项集的子集不是频繁项集，则该项集也不是频繁项集。因此，若存在一个项集的子集不是频繁项集，那么该项集就应该被舍弃。

总结来说，Apriori 算法的步骤是，先指定最小支持度阈值，依次生成1-项集，2-项集，… ，k-项集，并计算这些项集的支持度，移除小于最小支持度阈值的项集，保留支持度 大于或等于 最小支持度阈值的项集，作为频繁项集。

具体步骤如下：

1. 扫描交易数据，计算每个1-项集的支持度，找出所有频繁1-项集的集合，该集合记作L[1]，令k=1；
2. 连接步。合并L[k]，并且扫描交易数据得到候选k+1项集及其支持度，记作C[k+1]，注意这时的候选C[k+1]项集不一定全都是频繁项集；
3. 过滤步。剔除C[k+1]中支持度小于最小支持度阈值的项集，得到L[k+1]。因为如果C[k+1]中的项集不是频繁项集，那么它的扩集也不是频繁项集。
4. 令k=k+1，重复2、3步，直到不能生成更大的频繁集为止。

如下图例子所示，假设指定最小支持度阈值是0.5，

在图中有4个交易记录。由于指定最小支持度阈值是0.5，由这些交易记录应用Apriori算法找到频繁项集的详细步骤是：

第1步：扫描交易数据并计算每个1-项集的支持度，{A}、{B}、{C}、{D}、{E}的支持度分别是0.5、0.75、0.75、0.25、0.75。

第2步：移除支持度小于0.5的项集{D}，因此包含D的项集都不是频繁项集。得到所有频繁1-项集L[1] = {A}，{B}，{C}，{E}。它们的支持度分别是0.5、0.75、0.75、0.75。

第3步：连接步。在L[1]的基础上，通过合并并且扫描交易表，得到候选2-项集C[2]，其项集是{A,B}、{A,C}、{B,C}、{B,E}、{C,E}，它们的支持度分别是0.25、0.5、0.25、0.5、0.75、0.5。

第4步：过滤步。剔除C[2]中支持度小于0.5的项集，得到L[2]是{A,C}、{B,C}、{B,E}、{C,E}，它们的支持度分别是0.5、0.5、0.75、0.5。

第5步：连接步。在L[2]的基础上，通过合并并且扫描交易表，得到候选3-项集C[3]，其项集是{A,B,C}、{A,C,E}、{B,C,E}，它们的支持度分别是0.25、0.25、0.5。

第6步：过滤步。剔除C[3]中支持度小于0.5的项集，得到L[3]是{B,C,E}，它的支持度是0.5。

在第6步之后，得到的频繁项集只有1个不能生成更大的频繁项集了，这时结束。

因此得到的1-频繁项集L[1] = {A，B，C，E}，其支持度分别是0.5、0.75、0.75、0.75。

2-频繁项集L[2]={A,C}、{B,C}、{B,E}、{C,E}，它们的支持度分别是0.5、0.5、0.75、0.5。

3-频繁项集L[3]={B,C,E}，它的支持度是0.5。

频繁项集挖掘关联规则

每一个频繁项集及其子集都可能产生若干条关联规则。例如一个2-频繁项集{豆奶，莴苣}，那么可能有一条关联规则是“豆奶=>莴苣”，即一个人购买了豆奶，则大可能他会购买莴苣，但反过来一个人购买了莴苣，不一定他会购买豆奶，频繁项集使用支持度来量化，关联规则使用置信度量化。一条规则$X \Rightarrow Y$的置信度定义为

$$\operatorname{confidence}(X \Rightarrow Y)=\frac{\text { support }(X ∩ Y)}{\operatorname{support}(X)}$$

从频繁项集产生关联规则的步骤是：先指定最小置信度。

1. 根据每个频繁项集，找到它所有的非空真子集。
2. 根据这些非空真子集，两两组成所有的候选关联规则。
3. 计算所有候选关联规则的置信度，移除小于最小置信度的规则，得到强关联规则。

如下图所示从一个4频繁项集 {0，1，2，3}中挖掘关联规则过程，从下向上看。

上图是从4-频繁项集{0,1,2,3}中挖掘的关联规则的示意图，阴影区域是低置信度关联规则。如果{0,1,2}=>{3}是一条低置信度的关联规则，那么所有包含3为后项的关联规则的置信度也会低。

因此，先从2-频繁项集出发（1-频繁项集没有关联规则的），创建一个规则列表，该规则的前项、后项只包含一个元素，然后对这些规则测试；然后合并所有规则创建新的关联列表，该规则的后项包含两个元素。

以此类推从3-频繁项集、4-频繁项集中挖掘关联规则。

在第3节Apriori 算法生成频繁项集的例子中，得到的1-频繁项集L[1] = {A，B，C，E}，其支持度分别是0.5、0.75、0.75、0.75。

2-频繁项集L[2]={A,C}、{B,C}、{B,E}、{C,E}，它们的支持度分别是0.5、0.5、0.75、0.5。

3-频繁项集L[3]={B,C,E}，它的支持度是0.5。

下面从这些频繁项集中找出关联规则，设给定最小置信度是0.8。

第1步：2-频繁项集L[2]={A,C}、{B,C}、{B,E}、{C,E}。

1）从2-频繁项集{A,C}出发，其非空真子集有{A}，{C}，候选关联规则有A=>C、C=>A。它们的置信度分别是：

• A=>C的置信度confidence(A=>C) = support({A,C}) / support(A} = 0.5/0.5=1，其值大于最小置信度是0.8 ，因此保留该条关联规则。
• C=>A的置信度confidence(C=>A) = support({C,A}) / support(C} = 0.5/0.75=0.67，其值小于0.8 ，因此移除该条关联规则。

2）从2-频繁项集{B,C}出发，其非空真子集是{B，C}，可能的候选关联规则有B=>C、C=>B。它们的置信度分别是：

• B=>C的置信度confidence(B=>C) = support({B,C}) / support(B} = 0.5/0.75=0.67，其值小于0.8 ，因此移除该条关联规则。

• C=>B的置信度confidence(C=>B) = support({C,B}) / support(C} = 0.5/0.75=0.67，其值小于0.8 ，因此移除该条关联规则。

3）从2-频繁项集{B,E}}出发，其非空真子集有{B}，{E}，候选关联规则有B=>E、E=>B。它们的置信度分别是：

• B=>E的置信度confidence(B=>E) = support({B,E}) / support(B} = 0.75/0.75=1，其值大于0.8 ，因此保留该条关联规则。
• E=>B的置信度confidence(E=>B) = support({E,B}) / support(E} = 0.75/0.75=1，其值大于0.8 ，因此保留该条关联规则。

因此，2-频繁项集L[2]={A,C}、{B,C}、{B,E}、{C,E}的关联规则有：A=>C ，B=>E，E=>B。

第2步：3-频繁项集L[3]={B,C,E}，其非空真子集有{B},{C},{E},{B,C},{B,E},{C,E}。因此所有的关联规则有B=>{C,E}，C=>{B,E}，E=> {B,C}，{B,C}=>E，{B,E}=>C，{C,E}=>B。

因为1-频繁项集B,C,E之间的规则已经计算过，所以只需计算有多项的规则。

下面计算这些规则的置信度，得到强关联规则。

计算规则的B=>{C,E}置信度confidence(B=>{C,E}) = support(B)/support({C,E}) = 0.75/0.5 = 1.5 > 最小置信度是0.8，所以保留该条规则。

以此类推，confidence(C=>{B,E}) = 0.5/0.75=0.67<0.8。

confidence(E=>{B,C}) = 0.5/0.75=0.67<0.8。

confidence({B,C}=>E) = 0.5/0.5=1>0.8。

confidence({B,E}=>C) = 0.5/0.75=0.67<0.8。

confidence({C,E}=>B) = 0.5/0.75=0.67<0.8。

因此，在支持度是0.5、最小置信度是0.8的条件下得到的强关联规则有

A=>C，B=>E，E=>B，{B,C}=>E。

FP-Growth算法

从Apriori算法挖掘频繁项集的过程可以看出，每进行一次连接步就需要扫描一次交易数据，当交易数据量很大时，会非常耗时，这时需要对其优化，本节要介绍的FP-Growth算法就是一种优化算法。

FP-Growth是一种比Apriori更高效的频繁项挖掘方法，它只需要扫描交易表2次。其中第1次扫描获得1-项集的频率，去掉不符合支持度要求的1-项集，并对剩下的项按照置信度降序排序。第2遍扫描是建立一棵频繁项树FP-Tree(frequent-patten tree)。

FP-Growth算法生成频繁项集分有两个过程：

1. 构建FP树；
2. 从FP树中挖掘频繁项集。

FP-Growth是一种分治的算法，有下面4个步骤：

1. 统计交易数据中的项。按照出现次数从大到小排序，删掉小于支持度阈值的项，然后将数据库中的每条记录按照支持度对应的项进行排序，并删掉小于$\operatorname{sup}_{\min }$的项。
2. 用排序好的每条记录来构建一个前缀树T，每个节点维护，当这棵树只剩下一个分支的时候，生成相关的频率模式。
3. 深度优先遍历T，对于每一个item生成其条件模式基。
4. 把条件模式基当成数据库中的记录重复步骤1、2、3。

举个例子：

1. 所有数据集合按照得到的顺序重新整理

1. 重新整理完成后，丢弃每个集合末尾非频繁的项

1. 读取每个集合插入FP树中，同时用一个头部链表数据结构维护不同集合的相同项

1. 最终得到下面这样一棵FP树

1. 对头部链表进行降序排序，对头部链表节点从小到大遍历，得到条件模式基，同时获得一个频繁项集

如上图，从头部链表 t 节点开始遍历，t 节点加入到频繁项集。找到以 t 节点为结尾的路径如下：

去掉FP树中的t节点，得到条件模式基<左边路径,左边是值>[z,x,y,s,t]:2，[z,x,y,r,t]:1 。条件模式基的值取决于末尾节点 t ，因为 t 的出现次数最小，一个频繁项集的支持度由支持度最小的项决定。所以 t 节点的条件模式基的值可以理解为对于以 t 节点为末尾的前缀路径出现次数。

条件模式基继续构造条件 FP树， 得到频繁项集，和之前的频繁项组合起来，这是一个递归遍历头部链表生成FP树的过程，递归截止条件是生成的FP树的头部链表为空。 根据步骤 2 得到的条件模式基 [z,x,y,s,t]:2，[z,x,y,r,t]:1 作为数据集继续构造出一棵FP树，计算支持度，去除非频繁项，集合按照支持度降序排序，重复上面构造FP树的步骤。最后得到下面 t-条件FP树：

然后根据 t-条件FP树 的头部链表进行遍历，从 y 开始。得到频繁项集 ty 。然后又得到 y 的条件模式基，构造出 ty的条件FP树，即 ty-条件FP树。继续遍历ty-条件FP树的头部链表，得到频繁项集 tyx，然后又得到频繁项集 tyxz. 然后得到构造tyxz-条件FP树的头部链表是空的，终止遍历。我们得到的频繁项集有 t->ty->tyz->tyzx，这只是一小部分。

• 条件模式基:头部链表中的某一点的前缀路径组合就是条件模式基，条件模式基的值取决于末尾节点的值。
• 条件FP树:以条件模式基为数据集构造的FP树叫做条件FP树。

优缺点

• 优点：

  1. 因为 FP-growth 算法只需要对数据集遍历两次，所以速度更快。
  2. FP树将集合按照支持度降序排序，不同路径如果有相同前缀路径共用存储空间，使得数据得到了压缩。
  3. 不需要生成候选集。
  4. 比Apriori更快。

• 缺点：

  1. FP-Tree第二次遍历会存储很多中间过程的值，会占用很多内存。
  2. 构建FP-Tree是比较昂贵的。
• 适用数据类型：标称型数据(离散型数据)。