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

约 1234 字大约 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\}$ 不是频繁的, 所以它不是最大频繁项集.