规则的产生和频繁项集的紧凑表示

约 1199 字大约 4 分钟

2024-05-27

在上一节中我们结束了频繁项集的产生的内容。本节将讲述如何使用计算产生的频繁项集来产生规则。

规则的产生

由于每个频繁 k-项集都能够产生多达 $2^k - 2$ 个规则（忽略那些前件或后件为空的规则，如： $\emptyset \rightarrow Y$ 或 $Y \rightarrow \emptyset$ ），所以我们需要一个有效的方法从频繁项集中提取出所有的规则。

我们可以这样做：将项集 $Y$ 划分成两个非空的子集 $X$ 和 $Y-X$ ，使得 $X \rightarrow Y - X$ 满足置信度阈值。

提示

这样的规则必然满足支持度阈值，因为他们是由频繁项集产生的。

基于置信度的剪枝

置信度不具备像支持度度量那样的反单调性。尽管如此，当比较由频繁项集 $Y$ 产生的规则时，下面的定理对置信度度量成立：

定理 4.1

令 $Y$ 是一个项集， $X$ 是项集的一个子集。如果规则 $X \rightarrow Y-X$ 不满足置信度阈值，则形如 $\tilde{X} \rightarrow Y- \tilde{X}$ 的规则一定也不满足执行都阈值。其中 $\tilde{X}$ 是 $X$ 的子集。

定理 4.1 的证明

考虑如下的两个规则： $\tilde{X} \rightarrow Y- \tilde{X}$ 和 $X \rightarrow Y-X$ ，其中 $\tilde{X} \subset X$ 。这两个规则的置信度分别为 $\frac{\sigma(Y)}{\sigma(\tilde{X})}$ 和 $\frac{\sigma(Y)}{\sigma(X)}$ 。由于 $\tilde{X}$ 是 $X$ 的子集，所以 $\sigma(\tilde{X}) \ge \sigma(X)$ 。因此，前一个规则的置信度不可能比后一个规则的更大。

Apriori 算法中规则的产生

Apriori 算法使用一种逐层的方法来产生关联规则，其中每层对应于规则后件中的项数，如下图。根据上面提到的定理 4.1，如果格中任意节点具有低置信度，则可以立即剪掉该节点生成的整个子图。

频繁项集的紧凑表示

在实际的应用中，频繁项集的数量可能非常巨大。因此要从中识别出可以推导出其他所有的频繁项集的、较小的、具有代表性的项集是很有必要的。现在介绍两种具有代表性的项集：极大频繁项集和闭频繁项集。

极大频繁项集

极大频繁项集（maximal frequent itemset）

若频繁项集的直接超集都不是频繁的，则它是极大频繁项集。

图中的虚线表示频繁项集的边界。虚线上方的项集都是频繁的，下方的都是非频繁的。很显然 $\{a, d\}$ , $\{a,c,e\}$ 和 $\{b,c,d,e\}$ 都是极大频繁集，因为它们的所有直接超集都是非频繁的。而 $\{a,c\}$ 则因为有一个直接超集 $\{a,c,e\}$ 不是频繁的，所以它不是最大频繁项集。