关联规则挖掘概述

在网上购物时，系统会主动推荐一些商品，赠送一些优惠券，并且这些推荐的商品和赠送的优惠券往往都能直抵我们的需求，诱导我们消费。这背后主要使用使用了关联分析技术，通过分析哪些商品经常一起购买，可以帮助商家了解用户的购买行为。从大规模数据中挖掘对象之间的隐含关系被称为关联分析（associate analysis）或者关联规则学习（associate rule learning），其可以揭示数据中隐藏的关联模式，帮助人们进行市场运作，决策支持等。本博客将介绍关联规则挖掘及其在文本数据集中的应用。

关联规则

正如上面所述，关联规则最早是为了进行购物篮分析（Market Basket Analysis）而提出的，例如：在超市销售数据中发现了规则 { o n i o n s p o , p o t a t o e s } ⇒ { b u r g e r } \{\rm{onions po,potatoes\}\Rightarrow}\{burger\} {onionspo,potatoes}⇒{burger}，可能指示如果一个顾客同时购买了onions和potatoes，那么他很可能也会购买hamburger meat，这些信息可以用于指导市场活动，比如商品定价，商品摆放位置。

定义

1993年Agrawal等人在论文Mining association rules between sets of items in large databases中首先提出了关联规则的概念：

I = { i 1 , i 2 , … , i n } I=\{i_1,i_2,\dots,i_n\} I={i1​,i2​,…,in​}被称为项集（items），其中 i j ∈ { 0 , 1 } i_j\in \{0,1\} ij​∈{0,1}被称为项。

D = { t 1 , t 2 , … , t m } D=\{t_1,t_2,\dots,t_m\} D={t1​,t2​,…,tm​}被称为数据库（database），其中 t k t_k tk​被称为事务（transaction）。

事务是项的集合，即事务是 I I I的一个子集， t k ⊆ I t_k\sube I tk​⊆I，每个事务用一个唯一的transaction ID进行标识。规则（rule）定义如下：

X ⇒ Y ， 其 中 X , Y ⊆ I X\Rightarrow Y，其中X,Y\sube I X⇒Y，其中X,Y⊆I

每条规则由两个不同项目集（itemset） X , Y X,Y X,Y组成，其中 X X X称为前提或left-hand-side（LHS）， Y Y Y称为结论或right-hand-side（RHS）。图下表所示：

transaction ID	milk	bread	butter	beer	diapers
1	1	1
2	1
3	1	1
4	1	1	1
5	1

项集 I = { m i l k , b r e a d , b u t t e r , b e e r , d i a p e r s } I=\{milk,bread,butter,beer,diapers\} I={milk,bread,butter,beer,diapers}，每一个条目中，1表示项出现在相应的事务中，0表示项没有出现在事务中。 { b u t t e r , b r e a d } ⇒ { m i l k } \{butter,bread\}\Rightarrow\{milk\} {butter,bread}⇒{milk}是一条关联规则，表示如果butter和bread同时被购买了，milk也会被购买。当然这个例子非常的简单，在实际应用中，数据库通常包含成千上万的事务，一条规则需要上百个事务的支持才能被认为是统计显著的。

有用的概念

为了从所有可能的规则集中选出有趣的规则（interesting rules），需要用到各种重要度（significance）、兴趣度（interest）约束，其中最有名的是支持度（support）和置信度（confidence）。

支持度

支持度用来表示项目集在数据库中的出现频率。 对于数据库 D D D中的项目集 X X X，其支持度定义为：数据库中包含项目集 X X X的事务数 t t t与所有事务数 T T T之比

s u p p ( X ) = ∣ { t ∈ T ; X ⊆ t } ∣ ∣ T ∣ supp(X)=\frac{|\{t\in T;X\sube t\}|}{|T|} supp(X)=∣T∣∣{t∈T;X⊆t}∣​

以上面例子为例，项目集 X = { b e e r , d i a p e r s } X=\{beer,diapers\} X={beer,diapers}的支持度为 1 / 5 = 0.2 1/5=0.2 1/5=0.2，因为它出现在20%的事务中。

置信度

置信度用来衡量规则的可信程度。 对于规则 X ⇒ Y X\Rightarrow Y X⇒Y，其置信度定义为：数据库中同时包含 X ， Y X，Y X，Y的事务数与包含 X X X的事务数之比

c o n f ( X ⇒ Y ) = s u p p ( X ∪ Y ) s u p p ( X ) conf(X\Rightarrow Y)=\frac{supp(X\cup Y)}{supp(X)} conf(X⇒Y)=supp(X)supp(X∪Y)​

置信度可以看作是条件概率 P ( X ∪ Y ∣ X ) P(X\cup Y|X) P(X∪Y∣X)，以上面例子为例，规则 { b u t t e r , b r e a d } ⇒ { m i l k } \{butter,bread\}\Rightarrow\{milk\} {butter,bread}⇒{milk}的置信度为 0.2 / 0.2 = 1.0 0.2/0.2=1.0 0.2/0.2=1.0，因为项目集 X ∪ Y = { b u t t e r , b r e a d , m i l k } X\cup Y=\{butter,bread,milk\} X∪Y={butter,bread,milk}的支持度为 1 / 5 = 0.2 1/5=0.2 1/5=0.2，项目集 X = { b u t t e r , b r e a d } X=\{butter,bread\} X={butter,bread}的支持度为 1 / 5 = 0.2 1/5=0.2 1/5=0.2。规则 { b u t t e r , b r e a d } ⇒ { m i l k } \{butter,bread\}\Rightarrow\{milk\} {butter,bread}⇒{milk}的置信度为1意味着每次顾客购买了butter和bread后，一定也会购买milk。

Lift

一个规则的lift定义为

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\Rightarrow Y)=\frac{conf(X\Rightarrow Y)}{supp(Y)}=\frac{supp(X\cup Y)}{supp(X)\times supp(Y)} lift(X⇒Y)=supp(Y)conf(X⇒Y)​=supp(X)×supp(Y)supp(X∪Y)​

例如，规则 { m i l k , b r e a d } ⇒ { b u t t e r } \{milk,bread\}\Rightarrow \{butter\} {milk,bread}⇒{butter}的lift值为 0.2 0.4 × 0.4 = 1.25 \frac{0.2}{0.4\times 0.4}=1.25 0.4×0.40.2​=1.25。如果一个规则的lift值等于1，这暗示前提和结论对应的事件相互独立；如果lift值大于1，指示了两个事件之间的相互依赖程度，值越大，关联越强；如果lift值小于1，表明一个item的出现对其他item的出现存在消极影响（相斥），反之亦然（其中一个出现另一个一般不会出现）。lift的意义在于其即考虑了置信度也考虑了整个数据集中结论的支持度。

Conviction

一个规则的conviction定义如下：

c o n v ( X ⇒ Y ) = 1 − s u p p ( Y ) 1 − c o n f ( X ⇒ Y ) conv(X\Rightarrow Y)=\frac{1-supp(Y)}{1-conf(X\Rightarrow Y)} conv(X⇒Y)=1−conf(X⇒Y)1−supp(Y)​

conviction表示 X X X出现而 Y Y Y不出现的概率，即规则预测错误的概率。例如，规则 { m i l k , b r e a d } ⇒ { b u t t e r } \{milk,bread\}\Rightarrow \{butter\} {milk,bread}⇒{butter}的lift值为 1 − 0.4 1 − 0.5 = 1.2 \frac{1-0.4}{1-0.5}=1.2 1−0.51−0.4​=1.2，表明这条规则的出错率是20%。

处理过程

关联规则只有满足最小支持度阈值和最小置信度阈值，这条规则才能认为是有趣的。关联规则生成通常分成两个独立的步骤：

1. 利用最小支持度阈值从数据库中找出所有的频繁项集（frequent itemsets）；
2. 利用最小置信度阈值从这些频繁项集中生成规则。

其中，生成规则的阶段是直接的，但是寻找频繁项集需要更多的精力，因为其涉及搜寻所有可能项目集，项目集的大小是 I I I的幂集，大小为 2 n − 1 2^n-1 2n−1（除去没有意义的空集）。频繁项集有两个非常重要性质：

• 性质1：频繁项集的所有非空子集也是频繁的。
• 性质2：非频繁项集的所有超集是非频繁的。

如上图，方块的颜色代表包含该项目集的事务数目，低一层的项目集最多能包含其所有父类的最小项目数，如： { a c } \{ac\} {ac}最多有 m i n ( a , c ) min(a,c) min(a,c)个项目。利用这个性质，许多高效的算法（例如：Apriori、Eclat）可以用来发现所有的频繁项集。

其他有趣度度量方式

采用标准方法寻找关联规则可能发现许多虚假的关联规则。例如：在一个数据库中共包含10000条事务，其中包含项目 X X X的事务有7000条，包含项目 Y Y Y的事务有7500条，同时包含项目 X , Y X,Y X,Y的事务有5000条，那么项目集 X ∪ Y X\cup Y X∪Y的支持度为0.5，关联规则 X ⇒ Y X\Rightarrow Y X⇒Y的置信度为0.71，当最小支持度阈值和最小置信度阈值均设为0.5是，关联规则 X ⇒ Y X\Rightarrow Y X⇒Y将被认为是有趣的，即 X X X和 Y Y Y之间存在强关联规则。但是，在不考虑前提 X X X的情况下， Y Y Y的概率为0.75，也就是说在有 X X X的情况下， Y Y Y发生的概率反而降低了，即事件 X X X和 Y Y Y是相斥的。因此，需要一些其他新颖的有趣度度量方式，如：All-confidence，Convition，Leverage，Lift等，也可以用到一些其他的统计检测的方式。

算法

频繁项集挖掘算法可以按照搜索方式和支持度计算公式进行分类，按搜索方式分，可以分为BFS（Breath-First Search）和DFS（Depth-First Search）

• BFS宽度优先搜索：先产生所有频繁(k-1)-项集，再根据频繁(k-1)-项集计算频繁k-项集。
• DFS深度优先搜索：DFS通过递归调用产生频繁项集，频繁项集的产生次序与其长度无关。

从支持度计算方式看，可以分为计数法和交集法

• 计数法：直接计算项集在数据库中的发生数，逐一扫描数据库中所有事务，如果某候选项集在某个事务中出现，那么该候选项集的支持数加1。
• 交集法：将包含项集 X X X的事务放入集合 X . t l i s t X.tlist X.tlist，如果要计算候选项集 C = X ∪ Y C=X\cup Y C=X∪Y，可以通过对 X . t l i s t X.tlist X.tlist和 Y . t l i s t Y.tlist Y.tlist求交集，即 C . t l i s t = X . t l i s t ∩ Y . t l i s t C.tlist=X.tlist\cap Y.tlist C.tlist=X.tlist∩Y.tlist。 C . t l i s t C.tlist C.tlist中包含的元素个数就是候选项集 C C C的支持数。

对应的挖掘算法如下图所示：

Apriori

Apriori是广度优先搜索的典型算法，由Agrawal于1994年提出。Apriori算法首先产生频繁1-项集 L 1 L_1 L1​，然后对 L 1 L_1 L1​中只包含一个不同项的两个项集进行组合，产生频繁2-项集 L 2 L_2 L2​。重复该过程，直至某个 r r r值使得 L r L_r Lr​为空。虽然根据频繁项集的性质，Apriori不需要计数所有的 L r L_r Lr​项集，但是对所有候选项集进行计数同样是一个巨大的工程。

FP-growth

FP代表frequent pattern，FP-growth是一种无需产生候选项集的深度优先搜索算法。FP-growth将数据库中的频繁1-项集压缩为一棵频繁模式树（FP-Tree），同时保留了其中的关联信息，然后采用递归的方式遍历这棵树生成频繁模式。相比Apriori算法其主要提升点体现在：（1）将数据库中的频繁1-项集压缩为一棵频繁模式树，避免了计数时反复扫描数据库；（2）基于FP-Tree的挖掘采用递归方式生成长频繁模式，避免了产生大量的候选项集；（3）采用分治的策略将FP-Tree划分成若干个事务子集，减小了搜索规模。

其他

Partition将数据库分成若干部分，先分别找出每一部分的频繁项集，然后将这些局部频繁项集合并起来，扫描整个数据库，得到最终的频繁项集。Eclat是一种基于交集法的深度优先搜索算法，最大的特点是适合并行计算。

总结

这是本人第一次接触关联规则挖掘，本博客也只简单的记录关联规则挖掘的一些基本概念，下一步将会将会进行文本关联规则挖掘，具体的算法将会在之后的博客中介绍，希望能多多交流。

参考文献

Association rule learning

关联规则

R语言 关联规则

万晓鸽. 文本关联规则挖掘方法研究与应用[D]. 西安建筑科技大学, 2010.

陈晓云. 文本挖掘若干关键技术研究[D]. 复旦大学, 2005.