第5章相关性与关联规则

关联规则挖掘是数据挖掘领域中研究较为广泛也较为活跃的方法之一。最初的研究动
机是针对购物篮分析(BasketAnalysis)问题提出的,目的是为了解决发现交易数据库
(TransactionDatabase)中不同商品之间的联系规则。关联规则最早由Agrawal等人在
1993年提出,随后大量的研究人员对关联规则挖掘问题进行了大量的研究,从最初的挖掘
理论的探索、原有算法的改进、新算法的设计,到今天的并行关联规则挖掘(Paralel 
AsociationRuleMining)以及数量关联规则挖掘(QuantitiveAsociationRuleMining)等
方法的应用,关联规则挖掘方法已经日臻成熟,并在很多领域中有了广泛的应用。本章将对
相关性和关联规则挖掘的基本概念、方法以及相关算法进行介绍。

5.基本概念
1 

相关性与关联规则是对给定数据集中反复出现的联系进行挖掘提取,本节中将对关联
规则挖掘的基本概念进行简单介绍。5.1.1节给出了关联规则潜在的应用;1.

5.2节介绍购
物篮分析的例子,这是关联规则频繁模式挖掘的初始形式;5.3节对频繁模式分析、闭项集
1.
和关联规则的基本概念进行详细解释。

1.潜在的应用
5.1 
在传统的零售商店中顾客购买东西的行为是零散的,但如今,大型超市已经可以满足顾
客一次购物即可买到所有自己想要的商品,同时随着网络购物的兴起,很多人选择在网上挑
选自己想要的东西,这些商家以及网站很容易将购买记录收集和存储下来。通过对这些数
据的智能化分析,可以获得有关顾客购买模式的一般性规则。

早在20世纪90年代的美国沃尔玛超市中,沃尔玛的超市管理人员分析销售数据时发
现了一个令人难以理解的现象,在某些特定情况下,“啤酒”与“尿布”两件看上去毫无关系的
商品经常会出现在同一个购买记录里。如果一个年轻的父亲可以很方便地同时购买到两件
产品,那么他很可能会经常性地选择在这家超市购买商品。通过对客户购买模式的分析寻
找到一般性的规则,从而使顾客能够更加快捷方便地完成购物,进而产生良好的销售记录, 
这也就产生了最初的关联规则的潜在应用。这些规则刻画了顾客购买行为模式,可以用来
指导商家科学地安排进货、库存以及货架商品摆放设计等。图5.

1描绘了一个简单的关联

规则挖掘的潜在应用。

其实,除了上面提到的一些商品间存在的奇特关联现象外,也体现在其他方面。例如医
学研究人员希望从已有的成千上万份病历中找到患某种疾病的病人的共同特征,从而为治
愈这种疾病提供一些帮助。另外,通过对用户信用卡账单的分析也可以得到用户的消费方
式,有助于对相应的商品进行市场推广等。关联规则的挖掘方法已经涉及了生活的很多方
面,为人们的生活提供了极大的便利。


76 
图5.1 一个简单的关联规则挖掘的潜在应用
5.1.2 购物篮问题
通过频繁项集挖掘可以发现大型事务或关系数据集中事物与事物之间有趣的关联。随
着大型数据库的建立和不断扩充,很多分析人员已经可以从数据库中挖掘潜在的关联规则, 
从而发现事物间的相关联系,进而帮助商家进行决策、设计和分析顾客购买习惯。
假设给定一个很大的超市,里面包含任何顾客想购买的任何东西,那么作为超市的管理
者,如何找到最常出现在顾客“购物篮”中的东西呢? 或者哪些东西是最为常见同时出现在
顾客的“购物篮”中的呢? 或者某些商品后可能诱发顾客一路购买哪些其他商品? 
频繁项集挖掘的典型事例就是购物篮问题。通过发现顾客“购物篮”中不同商品之间的
关联,分析顾客的购买习惯,帮助零售商了解哪些商品被频繁地同时购买。例如,如果顾客
购买了面包,那么他们很可能也会购买果酱,这种信息可以很好地帮助管理人员选择性地安
排货架商品位置,以减少顾客购买所花费的时间以及提高销售量。
例5-1 购物篮问题。假设商店里有商品{milk,coke,pepsi,beer,juice},并有以下购物
记录: 
B1={milk,coke,beer},B2={milk,pepsi,juice},B3={milk,beer}, 
B4={coke,juice},B5={milk,pepsi,beer},B6={milk,coke,beer,juice}, 
B7={coke,beer,juice},B8={coke,beer} 
作为商店的主管,了解什么商品会被顾客经常性地购买,从而预测进货的数量等。为了
解决这个问题,可以通过统计商品被购买的次数来进行分析。一般来说,会对支持度较高的
一些商品感兴趣,也就是说当支持度达到一定的阈值后,某种(些)商品才有被挖掘的潜力, 
这个阈值就是最小支持度计数(min_sup),当某种商品的支持度超过最小支持计数阈值时, 
这个(些)商品就叫频繁项集。假设设定最小支持度为3,也就是出现次数最少为3的商品
(集),通过简单的计数统计,最终得到的频繁项集为: 
{milk},{coke},{beer},{juice},{milk,beer},{coke,beer},{juice, coke}。
5.1.3 频繁模式分析、闭项集和关联规则
一个事务数据库中的关联规则挖掘可以描述如下: 
设I={I1,I2,…,Im }是一个项目集合,事务数据库D ={t1,t2,…,tn}是由一系列具有
唯一标识TID的事务组成,每个事务ti(i=1,2,…,n)都对应I 上的一个子集。

定义5-设I1.I, itemst)I1 在数据集
D 
上的支持度(sppot)

1 
项目集(eur是包含I1 
的事务在
D 
中所占的百分比,即
t 
∈D|I1.t}||

support(I1)=||{(5-1) 

例如在例5-1中,mil5% 。
||D|
| 

k的支持度为62.
定义5-
2 
对项目集
I 
和事务数据库D,
T 
中所有满足用户指定的最小支持度
(minsupport)的项目集,即大于或等于minsupport的
I 
的非空子集称为频繁项目集

(s)或大项目集(s)。在频繁项目集中挑选出所有不被其他元
frequentitemsetlargeitemset
素包含的频繁项目集作为最大频繁项目集(maximumfrequencyitemsets)或最大项目集
(maximumlargeitemsets)。

定义5-
3 
假设A.I,B.I,并且A∩B=.,关联规则是形如A.
B 
的蕴含式,定义
在这个关联规则的置信度是指包含
A 
同时包含
B 
的事务数之比,即

confidence(A.B)
= 
Support(
A 
∪B) (5-2) 
在例5-1中,milk.ber的置信度是80% 。
Support(A) 

定义5-
4 D 
在
I 
上满足最小支持度和最小置信度(minconfidence)的关联规则称为强
关联规则(strongasociationrule)。

通常意义上所说的关联规则都是指强关联规则。

一般来说,给定一个事务数据库,关联规则挖掘问题就是通过用户指定最小支持度和最
小置信度来寻找强关联规则的过程。关联规则挖掘一般可以划分为两个子问题。

1.发现频繁项目集
通过用户给定的最小支持度,寻找所有频繁项目集,即满足支持度不小于min-support 
的所有项目子集。事实上,这些频繁项目集可能具有包含关系。一般地,只关心那些不被其
他频繁项目集所包含的所谓最大频繁项目集的集合。发现所有的频繁项目集是形成关联规
则的基础。

2.由频繁项集产生关联规则
通过用户给定的最小置信度,在每个最大频繁项目集中寻找置信度不小于minconfidence的关联规则。
相对于第一个子问题来说,由于第二个子问题相对简单,而且在内存、I/O以及算法效
率上改进余地不大,因此第一个子问题是近几年来关联规则挖掘算法研究的重点。

从大型数据集中挖掘频繁项集的主要挑战是这种挖掘常常产生大量满足最小支持度

的项集,当最小支持度设置很低的时候更是如此。这是因为如果一个项集是频繁的,它

的每个子集也是频繁的,一个长项集将包含组合个数较短的频繁子项集。这将产生过于

庞大的数据开销,尤其当数据量很大的时候。对于任何计算机来说,计算的速度和存储

空间都是制约关联挖掘的重要问题。因此,为了解决这个问题,在这里引入闭项集和极

大频繁项集的概念。

77

78 
如果不存在真超项集①Y 使得Y 与X 在I 中有相同的支持度计数,则称项集X 在数据
集I 中是闭的。项集X 是数据集I 中的闭频繁项集,如果X 在I 中是闭的和频繁的,项集
X 是I 中的极大频繁项集(或极大项集)。
5.2 频繁项集挖掘方法
本节将介绍最简单也是最常见的频繁项集挖掘的算法。5.2.1节对Apriori算法进行详
细介绍,Apriori是一种发现频繁项集的基本算法;5.2.2节介绍如何通过频繁项集产生关联
规则;5.2.3节介绍Apriori的效率,以及如何提高Apriori的效率;5.2.4节介绍另一种频繁
项集挖掘的算法,它与Apriori算法不同,并且在算法的效率上有显著提高。
5.2.1 Apriori算法
Apriori算法是R.Agrawal和R.Srikant于1994年提出的为布尔关联规则挖掘频繁项
集的原创性算法。Apriori使用一种称作逐层搜索的迭代方法,k 项集用于探索k+1项集。
在介绍Apriori算法前,首先介绍一种称为Apriori性质的重要理论,它主要用于压缩
搜索空间,从而更快地找到频繁项集。
Apriori性质:频繁项集的所有非空子集也必须是频繁的。即如果项集A 不满足最小
支持度阈值min-support,则A 不是频繁的,如果将项集B添加到项集A 中,也就是A∪B 
也不可能是频繁的。
该性质是一种反单调性的性质,也就是说如果一个集合不能通过测试,则它的所有超集
也都不能通过相同的测试。
Apriori算法简单来说主要有以下几个步骤:首先通过扫描数据库积累每个项的计数, 
并收集满足最小支持度的项,找出频繁1-项集的集合(该集合记为L1)。然后L1用于找到
频繁2-项集的集合L2,利用L2再找到L3,如此下去直到不能再找到频繁k-项集为止。其
算法描述如算法5.1所示。
算法5.1 Apriori算法 
输入: 数据集D;最小支持度计数min-sup_count。
输出: 频繁项目集L。
(1) L1={频繁1-项集}; //所有支持度不小于min-support 的1-项集
(2) for(k=2;Lk- 1 ≠0;k++) 
(3) Ck =apriori-gen(Lk-1); //Ck 是k 个元素的候选集
(4) for all transaction t∈D 
(5) Ct =subset(Ck,t); 
(6) for all candidates c∈Ct 
(7) c.count++; 
(8) End for 
(9) End for 
① Y 是X 的真超项集,如果X 是Y 的真子项集,即如果X .Y。换言之,X 中的每一项都包含在Y 中,但是Y 中至
少有一个项不在X 中。

79 
(10) Lk ={c∈Ck |c.count> =minsup_count} 
(11) End for 
(12) L=∪Lk 
算法5.1中调用了apriori-gen(Lk-1),是为了通过(k-1)-项集产生k-项集。算法5.2 
对apriori-gen过程进行了详细描述。
算法5.2 apriori-gen(Lk-1)(候选集产生) 
输入: (k-1)-项集。
输出: k-候选集Ck 。
(1) for all itemset p∈Lk-1 
(2) for all itemset q∈Lk-1 
(3) if(p.item1=q.item1, p.item2=q.item2,…,p.itemk- 2=q.itemk-2, 
(4) p.itemk- 1<q.itemk-1) 
(5) c=p∞q; 
(6) if(has_infrequent_subset(c,Lk-1)) delete c; 
(7) else add c to Ck; 
(8) End for 
(9) End for 
(10) Return Ck 
在算法5.2中调用了has_infrequent_subset(c,Lk-1),是为了判断c是否需要加入k-项
集中。根据Apriori的性质,含有非频繁项目子集的元素不可能是频繁项目集,因此应该删
掉那些含有非频繁项目子集的项目集,以提高效率。对于has_infrequent_subset(c,Lk-1) 
过程,算法5.3给出了详细的描述。
算法5.3 has_infrequent_subset(c,Lk-1)(判断候选集的元素) 
输入: 一个k-项集c,(k-1)-项集Lk-1 。
输出: c 是否从候选集中删除。
(1) for all (k-1)-subsets of c 
(2) if S.Lk-1 
(3) return true; 
(4) return false 
为了更好地了解Apriori算法,下面用一个例子对Apriori算法进行详细说明。
例5-2 假设如表5.1所示的样本数据库D ,假设最小支持度为2。
表5.1 样本数据库D 
ID 样 本
10 A ,C,D 
20 B,C,E 
30 A ,B,C,E 
40 B,E 
产生频繁项集的过程如图5.2所示。

图5.产生频繁项集的过程

2 

那么,最终产生的频繁1-项集、频繁2-项集和频繁3-项集分别是
:
L1:{A},{B},{C},{E}
;
L2:{A,C},{B,C},{B,E},{C,E}
;
L3:{B,C,E}
;


所有的频繁项集为{A,B,C,E,AC,BC,BE,CE,BCE 
}。

2.由频繁项集产生关联规则
5.2 

一旦由数据库
D 
中的事务找出频繁项集,可以直接由它们产生强关联规则,即满足最
小支持度和最小置信度的规则(最小置信度的公式如式(4-2)所示)。

例5-
3 
在例5-2产生的频繁项集中,对于频繁项集L={B,C,E}来说,可以通过
L 
得
到哪些关联规则?
L 
的非空子集有{B},{C},{E},{B,C},{C,E},{B,E}。部分关联结果
如下: 

B.C,
E 
confidence=2/3=67%
C.B,
E 
confidence=2/3=67%
E.B,
C 
confidence=2/3=67%
C,E.
B 
confidence=2/2=100%
B,E.
C 
confidence=2/3=67%
B,C.
E 
confidence=2/2=100%


如果最小置信度阈值为80%,那么只有第一个和第三个规则满足条件,即强关联规则。
在这里需要注意的一点就是,关联规则的右端可以包含多个合取项。

80

5.2.3提高Apriori的效率
Apriori作为经典的频繁项集产生算法,在数据挖掘领域里具有里程碑的作用。但随着
应用的深入,它的缺点也逐渐暴露出来,其主要的瓶颈有以下两个: 

(1)多次扫描事务数据库,需要很大的I/O负载。
对每次
k 
循环,候选集Ck 
中的每个元素都必须通过扫描数据库一次来验证其是否加
入Lk 
。加入一个频繁大项集包含10 个项,那么就至少需要扫描事务数据库10 次。

(2)可能产生庞大的候选集。
由Lk-1产生k-候选集Ck 
是指数增长的,例如104个频繁1-项集就有可能产生将近107 
个元素的2-候选集。如此庞大的候选集对时间和主存空间都是一种挑战。因此很多研究
人员对Apriori算法进行了很多的改进,以提高算法的效率。

1. 
基于散列的方法
1995 年,Park等提出了一种基于散列(Hash)技术产生频繁项集的算法。这种方法把
扫描的项目放到不同的Hash桶中,每个频繁项最多只可能放在一个特定的桶里,这样可以
对每个桶中的频繁项自己进行测试,减少了候选频繁项集产生的代价。

例5-
4 
对于表5.加入使用Hash函数“(10×x+y)mod7” 

y}
2中给出的数据,
-y} 
生成{x, 
对应的桶地址,那么扫描数据的同时可以把可能的2项集{x,放入对应的桶中,并对每
个桶内的项目集进行计数,结果如表5.根据表5.

3所示。假设最小支持度计数为3, 3的计
I2,I1,I1,

数结果,L2={(I3),(I2),(I3)}。

表5.事务数据库示例

2 

ID 
事务ID 
事务
1 I1,I2,I5 6 I2,I3 
2 I2,I4 7 I1,I3 
3 I2,I3 8 I1,I2,I3,I5 
4 I1,I2,I4 9 I1,I2,I3 
5 I1,I3 

表5.项集的桶分配示例

3 
2

桶地址0 1 2 3 4 5 6 
桶计数2 2 4 2 2 4 4 
桶内容{I1,I4}
{I3,I5} 
{I1,I5}
{I1,I5} 
{I2,I3}
{I2,I3}
{I2,I3}
{I2,I3} 
{I2,I4}
{I2,I4} 
{I2,I5}
{I2,I5} 
{I1,I2}
{I1,I2}
{I1,I2}
{I1,I2} 
{I1,I3}
{I1,I3}
{I1,I3}
{I1,I3} 

81

82 
2.事务压缩
事务压缩是指压缩未来迭代扫描的事务数。由于不包含任何频繁k-项集的事务是不
可能包含任何频繁(k+1)-项集的,因此这种事务在后续的考虑中可以加上标记或者直接删
除,因此产生j-项集(j>k)的数据库扫描不再需要它们。
3.基于数据划分(Partition)的方法
Apriori算法在执行过程中首先生成候选集,然后再进行剪枝。可是生成的候选集并不
都是有效的,有些候选集根本就不是事务数据的项目集。因此,候选集的产生具有很大的代
价。特别是内存空间不够导致数据库与内存之间不断交换数据,会使算法的效率变得很差。
把数据划分应用到关联规则挖掘中,可以改善关联规则挖掘在大容量数据集中的适应
性。其基本思想是把大容量数据库从逻辑上分成几个互不相交的块,每块应用挖掘算法(如
Apriori算法)生成局部的频繁项集,然后把这些局部的频繁项集作为候选的全局频繁项目
集,通过测试它们的支持度来得到最终的全局频繁项目集。
4.基于采样(Sampling)的方法
基于采样的方法是Toivonen于1996年提出的,这个算法的基本思想是:选取给定数
据D 的随机样本S,然后在S 而不是D 中搜索频繁项集。用这种方法牺牲了一些精度换取
有效性。样本S 的大小选取使得可以在内存搜索S 中的频繁项集。这样,只需要扫描一次
S 中的事务。由于算法只是搜索S 中的数据,因此可能会丢失一些全局频繁项集。为了减
少这样的情况,使用比最小支持度低的支持度阈值来找出局部于S 的频繁项集(记作Ls)。
然后,数据库的其余部分用于计算Ls 中每个项集的实际频率。使用一种机制来确定是否
所有的频繁项集都包含在Ls 中。如果Ls 实际包含了D 中的所有频繁项集,则只需扫描一
次D 。否则,可以做第二次扫描来找出第一次扫描时遗漏的频繁项集。
5.2.4 挖掘频繁项集的模式增长方法
在很多情况下,Apriori算法已经能够很好地解决关联规则挖掘的问题,并有很好的性
能表现。但同时它也有着很大的缺陷:会产生大量的候选项集;需要重复地扫描数据库。
那么,是否可以设计一种方法挖掘全部频繁项集而不产生候选集? Han等人于2000 
年提出了一种称为频繁模式增长(FrequentPattern-growth,FP-growth)的算法。这种算法
只需要进行两次数据库扫描,并且它不会产生候选集,直接压缩数据库成为一个频繁模式
树,最后通过这棵树生成关联规则。
FP-growth算法主要采用如下的分治策略:首先将提供频繁项的数据库压缩到一个频
繁模式树(FP-tree),但仍保留相关信息。然后将压缩后的数据库划分成一组条件数据库, 
每个关联一个频繁项或“模式段”,并分别挖掘每个条件数据库。具体算法如算法5.4所示。
算法5.4 FP-tree构造算法 
输入: 事务数据库DB;最小支持度阈值Minsupport。
输出: FP-tree 树。
(1) 扫描事务数据库D 一次。收集频繁项集合F 以及它们的支持度计数,对F 按照支持度计数降序

83 
排序,得到频繁项列表L。
(2) 创建FP-tree 的根结点,以"null"标记它。对于D 中的每个事务T,作如下处理: 选择T 中的
频繁项,并按照L 中的次序进行排序,排序后的频繁项标记为[p|P],其中p 是第一个元素,P 是剩余
元素的表。调用insert_tree([p|P],T)将此元组对应的信息加入T 中。
构造FP-tree算法的核心是insert_tree过程。Insert_tree过程是对数据库的一个候选
项目集的处理,它对排序后的一个项目集的所有项目进行递归式的处理,直到项目表为空。
算法5.5 insert_tree([p|P],T) 
(1) if(T 有一个子女N 使得N.item- name=p.item- name)。
(2) N 的计数加一。
(3) else。
(4) 创建一个新结点N,将其计数设为1,链接到它的父结点T,并通过结点链结构将其链接到具有相
同项名的结点。
(5) 如果P 非空,递归地调用insert_tree(P,N)。
为了更好地理解FP-tree的构建,通过下例来对算法进行说明。
例5-5 对于一个给定的事务数据库,通过一次扫描后去掉不频繁的项目(本例子中设
定最小支持度阈值为3),并按照出现的频率降序排列。表5.4给出了原始数据以及整理后
的数据。
表5.4 样本数据库/排序后的数据库
Tid 原始项目集整理后的项目集
100 {f,a,c,d,g,i,m ,p} {f,c,a,m ,p} 
200 {a,b,c,f,l,m ,o} {f,c,a,b,m } 
300 {b,f,h,j,o,w } {f,b} 
400 {b,c,k,s,p} {c,b,p} 
500 {a,f,c,e,l,p,m ,n} {f,c,a,m ,p} 
通过一次扫描,可以得到频繁1-项集L ={f,c,a,b,m ,p},如图5.3所示。利用得到
的频繁1-项集创建树的根结点,用Null标记。第二次扫描数据库D ,并对每一个事务创建
一个分支。
(1)第一个事务T100按照L 的次序包含5个项{f,c,a,m ,p},导致构造树的第一个
分支<f1-c1-a1-m1-p1>。
(2)对于第二个事务T200,由于其排序后的频繁项表为{f,c,a,b,m },已经与分支
{f,c,a,m ,p}有共同的前缀{f,c,a},因此前缀中的每个结点计数加1,只创建两个新的结
点m1和p1。形成分支链为<f2-c2-a2-b1-m1>。
(3)按照这种方法处理T300~T500,并按照要求连接到项头表和把相同的项目连接起
来,如图5.3所示。最终得到FP-tree。
前面已经提到了如何构建FP-tree,接着对如何通过FP-tree产生频繁项集进行详细解
释。利用FP-tree算法分析频繁项集的基本思想,即分而治之,构造过程如算法5.6所示。
算法5.6 利用FP-tree挖掘频繁项集 
输入: 构造好的FP-tree,事务数据库D,最小支持度阈值Minsupport。

84 
图5.3 样本数据库对应的FP-tree 
输出: 频繁项集。
FP-growth(Tree,α) 
(1) if(Tree 含单个路径P) 
(2) for 路径P 中结点的每个组合(记作β) 
(3) 产生模式β∪ α,其支持度support=β中结点的最小支持度
(4) else for each ai 在Tree 的头部{ 
(5) 产生一个模式β=ai ∪ α,其支持度support=ai .support; 
(6) 构造β的条件模式基,然后构造β的条件FP-树Treeβ; 
(7) if Treeβ≠0 then 
(8) 调用FP_growth (Treeβ,β); 
通过算法5.6,可以对例5-6得到的FP-tree进一步分析,得到挖掘FP_tree的过程,如
表5.5所示。
表5.5 频繁项集产生过程
项条件模式基条件FP-tree 产生的频繁项集
c f:3 <f:3> fc:3 
a fc:3 <fc:3> fca:3,ca:3,fa:3 
b fca:1,f:1,c:1 . . 
m fca:2,fcab:1 <fca:3> fcma:3,fm:3,cm:3,am:3,fcm:3,fam:3,cam:3 
p fcam:2,cb:1 <c:3> cp:3 
5.3 多种关联规则挖掘
5.3.1 挖掘多层关联规则
对于许多应用,由于多维数据空间数据的稀疏性,在低层或原始层的数据项之间很难找
出强关联规则。在较高的概念层次发现的强关联规则有可能提供具有普遍意义的知识。然
而,对一个用户代表普遍意义的知识,对另一个用户可能是新颖的。这样,数据挖掘系统应