学术

《数据挖掘导论》总结之关联分析

关联分析是一种发现隐藏在大型数据集中有意义的数据联系的方法。所发现的联系可以用关联规则或者频繁项集的形式表示,比如以下规则： \[\{nappy\}\rightarrow\{beer\}\] 该规则表明尿布和啤酒的销售之间存在很强的联系，因为许多购买尿布的顾客也买啤酒。

1. 问题定义

1. 1 二元表示

QQ截图20130218160043 如图1所示，购物车数据可以用二元形式来表示，其中每行对应一个事务，每列对应一个项。项用二元变量表示，如果在事务中出现，值为1，否则为0。

1.2 项集和支持度计数

令\(I=\{i_1,i_2,\cdots,i_d\}\)是购物车数据中所有项的集合，而\(T=\{t_1,t_2,\cdots,t_N\}\)是所有事务的集合。每个事务\(t_i\)包含的项集都是\(I\)的子集。在关联分析中，包含0个或者多个项的集合被称为项集（itemset）。如果一个项集包含\(k\)个项，就称为\(k-\)项集。例如,{啤酒，尿布，牛奶}是一个3-项集。

项集的一个重要性质是支持度计数，即包含特定项集的事务个数。数学上，项集\(X\)的支持度计数\(\sigma(X)\)可以表示为： \[\sigma(X)=|{t_i|X\subseteq t_i,t_i \in T}|\]

例如在图1中，项集{啤酒，尿布，牛奶}的支持度计数为2，因为只有2个事务包含这3 个项。

1.3 关联规则

关联规则是形如\(X \rightarrow Y\)的表达式，其中\(X\)和\(Y\)是不相交的项集，即\(X\cap Y=\emptyset\)。关联规则的强度可以用支持度和置信度衡量。支持度确定规则可以用于给定数据集的频繁程度，而置信度确定Y在包含X的事务中出现的频繁程度。支持度(s)和置信度(c)的形式定义如下： \[s(X \rightarrow Y)=\frac{\sigma(X\cup Y)}{N}\] \[c(X \rightarrow Y)=\frac{\sigma(X\cup Y)}{\sigma(X)}\] 支持度是一种重要度量，因为支持度低的规则可能只是偶然出现。另一方面，置信度通过规则推理具有可靠性。

1.4 关联规则挖掘问题的形式描述

因为计算每个可能规则的支持度和置信度方法的代价很高，所以大多数关联挖掘算法采取的策略是将任务分解为如下两个主要子任务:

  1. 频繁项集产生：其目标是发现满足最小支持度阈值的所有项集，这些项集称做频繁项集（frequent itemset)。
  2. 规则的产生：其目标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称做强规则(strong rule)。

2. 频繁项集的产生

格结构(lattice structure)常常被用来枚举所有可能的项集。图2显示\(I=\{a,b,c,d,e\}\)的项集格。

QQ截图20130218160115 发现频繁项集的原始方法是确定格结构中每个候选项集的支持度计数。为了完成这一任务，必须将每个候选项集与每个事务作比较，这种方法的开销非常大。 有2种方法可以降低产生频繁项集的计算复杂度 1.减少候选项集的数目（M)。之后介绍的apriori算法，就是不用计算支持度而删除某些候选项集的方法。 2.减少比较次数。

2.1 Apriori算法

Apriori算法是第一个关联规则挖掘算法，它开创性地使用基于支持度的剪枝技术。支持度的剪枝是基于一个先验原理:

如果项集是频繁的，那么它的所有子集也是频繁的。

Apriori算法初始时每个项都被看做候选1-项集。对它们的支持度计数并筛选后，利用产生的频繁1-项集来产生候选2-项集，以此类推。图3给出了Apriori算法的例子。

QQ截图20130218160143 Apriori算法的伪代码如图4所示。

QQ截图20130218160200 Apriori算法有2个重要的特点。 1.逐层算法，从频繁1-项集到最长的频繁项集，每次遍历项集格中的一层。 2.每次迭代之后，新的候选项集都有前一次迭代的频繁项集产生。

2.1.1 候选项集的产生与剪枝

Apriori算法步骤5的apriori-gen函数通过如下两个操作产生候选项集。

  1. 候选项集的产生。该操作由前一次迭代发现的频繁(k-1)-项集产生新的候选k-项集。
  2. 候选项集的剪枝。考虑候选k-项集\(X=\{i_1,i_2,\cdots,i_k\}\)，算法必须确定它的所有真子集\(X-\{i_j\}\)都是频繁的，如果其中一个是非频繁的，则\(X\)会被剪枝以减少候选项集的数量。

候选项集产生的方法，有如下几种：

  1. 蛮力方法。蛮力方法把所有的k-项集都看作可能的候选，然后使用候选剪枝除去不必要的候选，开销极大。
  2. $F_{k-1}F_1 $方法。利用其他频繁项集来扩展每个频繁(k-1)-项集，例子见图5。该方法是完备的，但是会产生重复的候选项集。 QQ截图20130218160234
  3. apriori-gen函数采用的方法是\(F_{k-1}\times F_{k-1}\)。由前\(k-2\)个项相同的一对\(k-1\)项集合并产生，例子见图6。 QQ截图20130218160243

2.1.2 支持度计数

支持数计数过程确定在候选项剪枝步骤保留夏利的每个候选项集出现的频繁程度。原始的做法是，将每个事务与所有的候选项集比较，并跟更新包含在事务中的候选项集支持度计数，这样的计算代价太昂贵。现在使用的方法是枚举每个事务包含的项集，并利用它们更新对应的候选项集支持度。例子见图7。 QQ截图20130218160305

2.2 FP增长算法

FP增长算法是一种完全不同的频繁项集发现方法。该方法不同于Apriori算法的“产生-测试”范型，而是使用一种称作FP树的数据结构组织数据，并直接从该结构中获取频繁项集。详细介绍和例子请见书（偷懒啦^_^）

3. 规则的产生

3.1基于置信度的剪枝

将频繁项集\(Y\)划分成两个非空的子集\(X\)和\(Y-X\)，使得 \(X \rightarrow Y-X\)满足置信度阈值。要注意的是，计算置信度不需要再次扫描数据集。

3.2 Apriori算法中的规则产生

Apriori算法使用一种逐层方法来产生关联规则，其中每层对应规则后件中的项数。算法首先提取规则后件只含一个项的所有高置信度规则，然后使用这些规则来产生新的候选规则。例如使用\(\{abc\} \rightarrow \{b\}\)和\(\{abd\} \rightarrow \{c\}\)来产生候选规则\(\{ad\} \rightarrow \{bc\}\)。图8显示了有频繁项集\(\{a,b,c,d\}\)产生关联规则的格结构，如果格中任意节点具有低置信度，就可以剪掉该结点生成的整个子图。

QQ截图20130218160339 图9给出了关联规则产生算法的伪代码。

QQ截图20130218160348 可以看到算法中的ap-genrules过程与之前频繁项集产生的过程类似。两者唯一的不同就是，在规则产生时，不必再次扫描数据集来计算候选规则的置信度，而是使用在频繁项集产生时计算的支持度计数来确定每个规则的置信度。 更多具体内容请见《数据挖掘导论》。

参考文献

  1. 《数据挖掘导论》,人民邮电出版社。