关联分析(下)

0. 导言

我们在上一篇介绍了关联规则分析的基本概念。这一篇将介绍如何产生频繁项集产生关联规则。挖掘关联规则的一种原始方法是:计算每个可能规则的支持度和置信度。但是这种方法的代价很高,因为可以从数据集中提取的规则的数目达指数级。

关联规则挖掘主要分两个步骤:[频繁项集的产生]和[关联规则的产生],分别由[基于支持度的剪枝]和[基于置信度的剪枝]控制搜索空间指数增长。

  • [基于支持度的剪枝]:如果一个项集是频繁的,则它的所有子集也是频繁的。相反,如果项集是非频繁的,则它的所有超集也是非频繁的。
  • [基于置信度的剪枝]:如果规则$X \rightarrow Y - X$不满足置信度阈值,则形如$X’ \rightarrow Y - X’$的规则一定也不满足置信度阈值,其中$X’$是$X$的子集。

1. 频繁项集的产生

格结构(lattice structure)常常被用来枚举所有可能的项集。下面的图显示了$I=\{a,b,c,d,e\}$的项集格。一般来说,一个包含$k$个项的数据集可能产生$2^k - 1$个频繁项集,不包括空集在内。由于在许多实际应用中$k$的值可能非常大,需要探查的项集搜索空间可能是指数规模的。


item set
图片来源:《数据挖掘导论》

有几种方法可以降低产生频繁项集的计算复杂度:

  • 减少候选项集的数目。使用先验(apriori)原理,不用计算支持度值而删除某些候选项集。
  • 减少比较次数。替代将每个候选项集与每个事务相匹配,可以使用更高级的数据结构,或者存储候选项集或者压缩数据集,来减少比较次数,比如使用Hash树和FP树。

这里,我们只介绍先验(apriori)原理

[先验原理]: 如果一个项集是频繁的,则它的所有子集一定也是频繁的。

例如,考虑上图的项集格。假定{c, d, e}是频繁项集,则任何包含项集{c, d, e}的事务一定包含它的子集{c, d},{c, e},{d, e},{c},{d}和{e}。因此,如果{c, d, e}是频繁的,则它的所有子集一定也是频繁的。

反过来,如果项集{a, b}是非频繁的,则它的所有超集也一定是非频繁的。一旦发现{a, b}是非频繁的,则整个包含{a, b}超集的子图可以被立即剪枝。

这种基于支持度度量修剪指数搜索空间的策略称为基于支持度的剪枝(support-based pruning)。这种剪枝策略依赖于支持度度量的一个关键性质,即一个项集的支持度决不会超过它的子集的支持度,这个性质也称为支持度度量的反单调性(anti-monotone)。

1.1 Apriori算法的频繁项集产生

Apriori算法是第一个关联规则挖掘算法,它通过使用基于支持度的剪枝技术,系统地控制候选项集指数增长。对于我们的购物篮事务,下面的图给出Apriori算法频繁项集产生部分的一个高层实例。假定支持度阈值是60%,相当于最小支持度计数是3。


apriori
图片来源:《数据挖掘导论》
  • 初始时每个项都被看作候选1-项集。对于它们的支持度计数之后,候选项集{可乐}和{鸡蛋}被丢弃,因为它们出现的事务少于3个。
  • 在下一次迭代中,仅使用频繁1-项集来产生候选2-项集,因为先验原理保证所有非频繁的1-项集的超集都是非频繁的。由于只有4个频繁1-项集,因此算法产生的候选2-项集的数目为$C_4^2=6$。计算它们的支持度值之后,发现这6个候选项集中的2个,{啤酒,面包}和{啤酒,牛奶}是非频繁的。
  • 剩下的4个候选项集是频繁的,因此用来产生候选3-项集。不使用基于支持度的剪枝,使用该例给定的6个项,将形成$C_6^3=20$个候选3-项集。根据先验原理,只需要保留其子集都频繁的候选3-项集。具有这种性质的唯一候选是{面包,尿布,牛奶}。

1.2 候选的产生与剪枝

  • 候选项集的产生。该操作由前一次迭代发现的频繁$(k-1)$-项集产生新的候选$k$项集。
  • 候选项集的剪枝。该操作采用基于支持度的剪枝策略,删除一些候选$k$-项集。

这里我们主要介绍一种常见的产生候选项集的方法: $F_{k-1} \times F_{k-1}$方法。
$F_{k-1} \times F_{k-1}$方法的候选产生过程合并一对频繁$(k-1)$项集,仅当它们的前$k-2$个项都相同。令$A=\{a_1,a_2,\cdots,a_{k-1}\}$和$B=\{b_1,b_2,\cdots,b_{k-1}\}$是一对频繁$(k-1)$项集,合并A和B,如果它们满足如下条件:
$$
a_i = b_i, (i=1,2,\cdots,k-2)并且a_{k-1} \neq b_{k-1}
$$
例如,频繁项集{面包,尿布}和{面包,牛奶}合并,形成了候选3-项集{面包,尿布,牛奶}。算法不会合并项集{啤酒,尿布}和{尿布,牛奶},因为它们的第一个项不相同。实际上,如果{啤酒,尿布,牛奶}是可行的候选,则它应当由{啤酒,尿布}和{啤酒,牛奶}合并而得到。这个例子表明了候选项产生过程的完全性和使用字典序避免重复的候选的优点。然而,由于每个候选都由一对频繁$(k-1)$项集合并而成,因此需要附加的候选剪枝步骤来确保该候选的其余$k-2$个子集是频繁的。

1.3 产生频繁项集算法过程

下面的算法给出了Apriori产生频繁项集的伪代码,令$C_k$为候选$k$项集的集合,而$F_k$为频繁$k$项集的集合:

算法:Apriori
输入:D(事务数据库);minsup(最小支持度阈值)
输出:F(D中的频繁项集)


apriori
图片来源:《数据挖掘导论》

算法说明如下:

  • 该算法初始通过单遍扫数据集,确定每个项的支持度。一旦完成这一步,就得到所有频繁1项集的集合$F_1$;
  • 接下来,该算法将使用上一次迭代过程发现的频繁$(k-1)$项集,产生新的候选$k$项集。候选的产生可使用前面介绍的$F_{k-1} \times F_{k-1}$方法;
  • 为了对候选的支持度计数,算法需要再次扫描一遍数据集,确定包含在每一个事务$t$中的$C_k$中的所有候选$k$项集;
  • 计算候选项的支持度计数后,算法将删去支持度计数小于minsup的所有候选项集;
  • 当没有新的频繁项集产生,即$F_k = \emptyset$时,算法结束。

2. 关联规则的产生

我们从上面已经知道了如何产生频繁项集,下面介绍如何从给定的频繁项集中提取关联规则。忽略那些前件或后件为空的规则($\emptyset \rightarrow Y 或 Y \rightarrow \emptyset$),每个频繁k项集能够产生$2^k-2$个关联规则。

关联规则可以这样提取:将项集$Y$划分成两个非空的子集$X$和$Y-X$,使得$X \rightarrow Y-X$满足置信度阈值。
注意:这样的规则已经满足支持度阈值,因为它们是由频繁项集产生的。

例如,假设$Y=\{1, 2, 3\}$是频繁项集。可以由$Y$产生6个候选关联规则:
$$
\{1,2\} \rightarrow \{3\}, \{1,3\} \rightarrow \{3\}, \{2,3\} \rightarrow \{1\}, \\
\{1\} \rightarrow \{2,3\}, \{2\} \rightarrow \{1,3\}, \{3\} \rightarrow \{1,2\}
$$
由于它们的支持度都等于$Y$的支持度,这些规则一定满足支持度阈值。

计算关联规则的置信度并不需要再次扫描事务数据集。考虑规则$\{1,2\} \rightarrow \{3\}$,它是由频繁项集$X=\{1,2,3\}$产生的。该规则的置信度为$\sigma({1,2,3})/\sigma({1,2})$。因为$\{1,2,3\}$是频繁的,支持度的反单调性确保项集$\{1,2\}$一定也是频繁的。由于这两个项集的支持度计数已经在频繁项集产生时得到,因此不必再扫描整个数据集。

2.1 基于置信度的剪枝

如果规则$X \rightarrow Y-X$不满足置信度阈值,则形如$X’ \rightarrow Y-X’$的规则一定也不满足置信度阈值,其中$X’$是X的子集。
解释如下:考虑如下两个规则$X’ \rightarrow Y-X’$和$X \rightarrow Y-X$,其中$X’ \subset X$。这两个规则的置信度分别为$\sigma(Y)/\sigma(X’)$和$\sigma(Y)/\sigma(X)$。由于$X’$是$X$的子集,所以$\sigma(X’) \geq \sigma(X)$。因此,前一个规则的置信度不可能大于后一个规则。

2.2 Apriori算法中规则的产生

Apriori算法使用一种逐层方法来产生关联规则,其中每层对应于规则后件中的项数。

  • 初始,提取规则后件只含一个项的所有高置信度规则;
  • 然后,使用这些规则来产生新的候选规则

例如,如果$\{acd\} \rightarrow \{b\}$和$\{abd\} \rightarrow \{c\}$是两个高置信度的规则,则通过合并这两个规则的后件产生候选规则$\{ad\} \rightarrow \{bc\}$。下面的图显示了由频繁项集$\{a,b,c,d\}$产生关联规则的格结构。如果格中的任意结点具有低置信度,则可以立即剪掉该结点生成的整个子图。

假设规则$\{bcd\} \rightarrow \{a\}$具有低置信度,则可以丢弃后件包含$a$的所有规则,包括$\{cd\} \rightarrow \{ab\}$,$\{bd\} \rightarrow \{ac\}$,$\{bc\} \rightarrow \{ad\}$和$\{d\} \rightarrow \{abc\}$。


rules
图片来源:《数据挖掘导论》

3. 参考资料

  • 数据挖掘导论,Pang-Ning Tan 等著,范明 等译