1 引言

说到关联分析，顾名思义的就可以联想到，所谓关联就是两个东西之间存在的某种联系。关联分析最有名的例子是“购物篮事务”，以前在美国西部的一家连锁店，店家发现男人们在周四购买尿布后还会购买啤酒。于是他便得出一个推理，尿布和啤酒存在某种关联。但是具体怎么来评判呢？先看下表：
 
表 1
表中每一行对应一个事物，包含一个唯一标识TID和给定顾客购买的商品的集合。从这个表中所示的数据中可以提取出如下规则：
{尿布}->{啤酒}

2 一些概念

项集和计数度计数 在关联分析中，包含0个或者多个项的集合被称为项集。如果一个项集包含k个项，则称为k-项集。支持度计数是指包含特定项集的事务的个数。
关联规则 关联规则是形如X->Y的蕴含表达式，其中X和Y是不相交的项集。关联规则的强度可以用它的支持度和置信度度量。
一个项集的支持度（support）被定义为数据集中包含该数据集的记录所占的比例。比如有规则X=>Y，它的支持度可以计算为包含XUY所有商品的交易量相对所有交易量的比例（也就是X和Y同时出现一次交易的概率）。可信度定义为包含XUY所有物品的交易量相对仅包含X的交易量的比值，也就是说可信度对应给定X时的条件概率。关联规则挖掘，其目的是自动发起这样的规则，同时计算这些规则的质量。
计算公式如下：
支持度=交易量包含XUY交易量支持度/交易量包含XUY交易量
可信度=交易量包含XUY交易量包含X可信度/交易量包含XUY交易量包含X
支持度和可信度是用来量化关联分析是否成功的方法。关联分析的目的包括两个：发现频繁项集和发现关联规则。首先我们要找到频繁项集，然后根据频繁项集找出关联规则。
例 考虑规则{牛奶，尿布}->{啤酒}。由于项集{牛奶，尿布，啤酒}的支持度技术是2，而事物总数是5，所以规则的支持度为2/5=0.4。规则的置信度是项集{牛奶，尿布，啤酒}的支持度与项集{牛奶，尿布}支持度计数的商。由于存在3个事务同时包含牛奶和尿布，所以该规则的置信度为2/3=0.67。
大多数关联规则挖掘算法通常采用的一种策略是，将关联规则挖掘任务分解为如下两个主要的子任务。
1) 频繁项集产生：其目标是发现满足最小支持度阈值的所有项集，这些项集称为频繁项集。
2) 规则产生：其目标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称为强规则。

3 频繁项集的产生

通常，频繁项集产生的计算开销远大于产生规则所需要的计算开销。

3.1 先验原理

先验原理 如果一个项集是频繁的，则它的所有子集一定也是频繁的。
相反，如果项集｛a,b｝是非频繁的，则他的所有超级也一定不是非频繁的。我们根据这一点可以进行剪枝操作。这种基于支持度度量修剪指数搜索空间的策略称为基于支持度的剪枝。这种剪枝策略依赖于支持度度量的一个关键性质，即一个项集的支持度决不会超过它的子集的支持度。这个性质也称为支持度度量的反单调性。

3.2 Apriori算法

Apriori算法是第一个关联规则挖掘算法，它使用了基于支持度的剪枝技术，系统地控制候选项集指数增长。对表1中所示的事务，假设支持度阈值是60%，相当于最小支持度技术为3。
初始时每个项都被看作候选1-项集。对他们的支持度计数之后，候选项集{可乐}和鸡蛋被丢弃，因为它们出现的事务少于3个。在下一代迭代，仅使用频繁1-项集来产生候选2-项集，因为先验原理保证所有非频繁的1-项集的超集都是非频繁的。由于只有4个频繁1-项集，因此算法产生的候选2-项集的数目为 6。计算他们的支持度值之后，发现这6个候选项集中的2个，{啤酒，面包}和{啤酒，牛奶}是非频繁。剩余的4个候选项集是频繁的，因此用来产生候选3-项集。以此类推。
 
通过计算产生的候选项集数目，可以看出先验剪枝策略的有效性。枚举所有项集（到3-项集）的蛮力策略将产生41 个候选项；而使用先验原理，将减少 13个候选。

3.3  候选项集的产生和剪枝

其中，Apriori算法中，候选项集的产生和剪枝是非常重要的环节。
候选项集的产生。该操作由前一次迭代发现的频繁（k-1）-项集产生新的候选k-项集。下面介绍几种候选项集的产生过程。
蛮力方法  蛮力方法把所有的k-项集都看做可能的候选，然后使用候选剪枝除去不必要的候选。第k层产生的候选项集的数目为 ，其中d是项的总数。
 

  F(k-1)*F(1)方法 用其它频繁项来扩展每个频发（k-1）-项集。如用面包这个频繁项扩展频繁2-项集{啤酒，尿布}，产生候选3-项集{啤酒，尿布，面包}。

这种方法是完备的，但是很难避免重复产生候选项集。避免产生重复的候选项集的一种方法是确保每个频繁项集中的项以字典序存储，每个频发（k-1）-项集X只用字典比X中所有的项都大的频发项进行扩展。
尽管这样的方法比蛮力的方法有明显改进，但是仍然会产生大量不必要的候选。例如，合并{啤酒，尿布}和{牛奶}而得到的候选是不必要的，因为它的子集{啤酒，牛奶}是非频繁的。


 F(k-1)*F(k-1)方法 合并一对频繁（k-1）-项集，仅当他们的前k-2个项都相同。例如，频繁项集{面包，尿布}和{面包，牛奶}合并，形成了候选3-项集{面包，尿布，牛奶}。算法不会合并项集{啤酒，尿布}和{尿布，牛奶}，因为它们的第一个项都不相同。实际上，如果{啤酒，尿布，牛奶}是可行的候选，则它应当由{啤酒，尿布}和{啤酒，牛奶}合并得到。这个例子表明了候选项产生过程的完全性和使用字典序避免重复的候选的优点。
 

3.4支持度计数

1. 支持度计数的一种方法是，将每个事务与所有的候选项集进行比较，并且更新包含在事务中的候选项集的支持度计数。这种方法是计算昂贵的，尤其当事务和候选项集的数目都很大时。
2. 枚举每个事务所包含的项集，并且利用他们更新对应的候选项集的支持度。
例：事务t={1,2,3,5,6}，求事务t包含3个项的子集如下。
 
求得这些项集之后，与候选项集匹配，如果匹配成功，则相应的候选项集的支持度计数+1。
3. 使用Hash树进行支持度计数
候选项集划分为不同的桶，并放在hash树中。在支持度计数期间，包含在事务中的项集也散列到相应的桶中。然后，将它与桶内候选项集进行匹配。

 
4 规则产生

4.1基于置信度的剪枝

4.2Apriori算法中规则的产生

初始，提取规则后件只含一个项的所有高置信规则，然后，使用这些规则来产生新的候选规则。例如，如果{acd}->{b}和{abd}->{c}是两个高置信度的规则，则通过合并这两个规则的后件产生候选规则{ad}->{bc}。如图，假设规则{bcd}->{a}具有低置信度，则可以丢弃后件包含a的所有规则。