6.1　关联规则概要

6.1.1　关联规则的提出背景

关联规则最初是针对购物篮分析（Market Basket Analysis）问题提出的。假设超市经理想更多地了解顾客的购物习惯，特别是想知道顾客可能会在一次购物时同时购买哪些商品？为回答该问题，可以对顾客购物记录进行购物篮分析（见图6-1）。该过程通过发现顾客放入购物篮中的不同商品之间的关联，分析顾客的购物习惯。这种关联的发现可以帮助零售商了解哪些商品频繁地被顾客同时购买，从而帮助他们开发更好的营销策略。

为了对顾客的购物篮进行分析，1993年，Agrawal等人首先提出关联规则的概念，同时给出了相应的挖掘算法AIS，但是该算法性能较差。1994年，著名的Apriori算法被提出，至今Apriori仍然作为关联规则挖掘的经典算法被广泛讨论。后来诸多的研究人员对关联规则的挖掘问题进行了大量的研究。

6.1.2　关联规则的基本概念

先了解关联规则挖掘中涉及的几个基本概念。

定义1：项目与项集

数据库中不可分割的最小单位信息，称为项目，用符号i表示。项目的集合称为项集。设集合I={i1,i2,…,ik}是项集，I中项目的个数为k，则集合I称为k-项集。例如，集合{啤酒，尿布，牛奶}是一个3-项集。

定义2：事务

设I={i1,i2,…,ik}是由数据库中所有项目构成的集合，一次处理所含项目的集合用T表示，T={t1,t2,…,tn}。每一个ti包含的项集都是I的子集。

例如，如果顾客在商场里一次购买多种商品，这些购物信息在数据库中有一个唯一的标识，则称该顾客的本次购物活动对应一个数据库事务。

定义3：项集的频数（支持度计数）

项集的事务数称为项集的频数（支持度计数）。

定义4：关联规则

关联规则是形如X⇒Y的蕴含式，其中X、Y分别是I的真子集，并且X∩Y=ø。X称为规则的前提，Y称为规则的结果。关联规则反映X中的项目出现时，Y中的项目也跟着出现的规律。

定义5：关联规则的支持度（Support）

关联规则的支持度是交易集中同时包含X和Y的交易数与所有交易数之比，记为Support(X⇒Y)，即Support(X⇒Y)=SupportX∩Y=P(XY)。

支持度反映了X和Y中所含的项目在事务集中同时出现的频率。

定义6：关联规则的置信度（Confidence）

关联规则的置信度是交易集中包含X和Y的交易数与所有包含X的交易数之比，记为Confidence(X⇒Y)，即

置信度反映了包含X的事务中出现Y的条件概率。

定义7：最小支持度与最小置信度

通常用户为了达到一定的要求，需要指定规则必须满足的支持度和置信度阈限，当Support(X⇒Y)、Confidence(X⇒Y)分别大于或等于各自的阈限值时，认为X⇒Y是有趣的，这两个值称为最小支持度（min_sup）和最小置信度（min_conf）。其中，min_sup描述了关联规则的最低重要程度，min_conf规定了关联规则必须满足的最低可靠性。

定义8：频繁项集

设U={u1,u2,…,un}为项目的集合，且U⊆I，U≠ø，对于给定的最小支持度min_sup，如果项集U的支持度Support(U) ≥min_sup，则称U为频繁项集；否则，U为非频繁项集。

定义9：强关联规则

若Support(X⇒Y)≥min_sup且Confidence(X⇒Y)≥min_conf，则称关联规则X⇒Y为强关联规则，否则称X⇒Y为弱关联规则。

下面用一个简单的例子来说明这些定义。表6-1为顾客购买记录的数据库D，包含6个事务。项集I={网球拍，网球，运动鞋，羽毛球}。考虑关联规则：网球拍⇒网球，事务1、2、3、4、6包含网球拍，事务1、2、6同时包含网球拍和网球，支持度，置信度。若给定最小支持度为0.5，最小置信度为0.5，关联规则网球拍⇒网球是有趣的，认为购买网球拍和购买网球之间存在关联。

6.1.3　关联规则的分类

按照不同的标准，关联规则的分类如下：

（1）基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。

布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系；而数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型关联规则中也可以包含种类变量。例如，性别="女"=>职业="秘书"，是布尔型关联规则；性别="女"=>avg（收入）=2 300，这条规则涉及的收入是数值类型，所以是一个数值型关联规则。

（2）基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。

在单层关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的；而在多层关联规则中，对数据的多层性已经进行了充分的考虑。例如，IBM台式机=>Sony打印机，是一个细节数据上的单层关联规则；台式机=>Sony打印机，是一个较高层次和细节层次之间的多层关联规则。

（3）基于规则中涉及的数据的维数，关联规则可以分为单维关联规则和多维关联规则。

在单维关联规则中，只涉及数据的一个维，如用户购买的物品；而在多维关联规则中，要处理的数据将会涉及多个维。换句话说，单维关联规则是处理单个属性中的一些关系的；多维关联规则是处理各个属性之间的某些关系的。例如，啤酒=>尿布，这条规则只涉及用户购买的物品；性别="女"=>职业="秘书"，这条规则就涉及两个字段的信息，是两个维上的一条关联规则。

6.1.4　关联规则挖掘常用算法

关联规则挖掘算法是关联规则挖掘研究的主要内容，迄今为止已提出了许多高效的关联规则挖掘算法。最著名的关联规则挖掘算法是R. Agrawal提出的Apriori算法。Apriori算法主要包含两个步骤：①找出事务数据库中所有大于或等于用户指定的最小支持度的数据项集；②利用频繁项集生成所需要的关联规则，根据用户指定的最小置信度进行取舍，最后得到强关联规则。识别或发现所有频繁项集是关联规则挖掘算法的核心。

另一种比较著名的关联规则挖掘算法是J. Han等提出的FP-Growth。该方法采用分而治之的策略，在进行第一遍扫描之后，把数据库中的频繁项集压缩进一棵频繁模式树（FP Tree），同时依然保留其中的关联信息，随后将FP-Tree分化成一些条件库，每个库和一个长度为1的频繁项集相关，然后对这些条件库分别进行挖掘。当原始数据量很大时，也可以结合划分的方法，将一个FP-Tree放入主存中。实验表明，FP-Growth对不同长度的规则都有很好的适应性，同时在效率上较Apriori算法有很大的提高。

在下面的章节中将重点介绍这两种算法。