设定与约定
定义 2.2.1
(事务、支持度与频繁性)
- 一个非空有限项目全集 。
- 项集的定义域是 的所有子集所成的集合,即幂集 。其中包括 及 。
- 一个有限非空事务多重集 ,其中每个事务 都是一个集合。两个事务作为集合可以相等,但仍分开计算。
- 项集 的支持度计数为
按索引计算,因此重复的事务各自贡献一次。
- 一个正整数最小支持度 。当 时,项集 称为频繁。
命题 2.2.2
(支持度具有反单调性)
若 ,则 。
证明
(较大的项集被较少的事务包含)
每个包含 的事务也包含 ,所以为 计算的索引集是为 计算的索引集的子集。
Apriori 正是依赖这个性质。
三个定义
定义 2.2.3
(闭项集、闭频繁项集与极大频繁项集)
- 如果每个真超集 都满足 ,则 是闭项集。
- 若 既闭又频繁,则它是闭频繁项集。
- 若 频繁且没有频繁的真超集,则它是极大频繁项集。
常见错误
(混淆闭与极大)
闭性询问更大的项集是否保持完全相同的计数;极大频繁性询问更大的项集是否仍达到阈值。因此,闭项集仍可有更大的频繁扩展,只要该扩展的支持度较小。在下面的例题中, 的支持度为 并且是闭项集,但频繁集 (支持度 )包含它,所以 不是极大项集。
用交集构造闭包
设 的支持度为正。定义其闭包为
我们只在 时使用这个构造。此时被取交集的集族非空,所以交集是良好定义的。
当 时,该集族为空,公式需要额外的约定。一个常见约定是把空交集视为 ;本章则在此情况下不定义闭包。闭性本身仍按上面的定义:支持度为零的项集是闭项集,当且仅当它等于 。事实上,若 ,则其真超集 的支持度也为 ,所以 不是闭项集。若 ,它没有真超集,因此空虚地是闭项集,即使其支持度为 也是如此。这个结论并不需要 的值。在本章中,由于 ,“闭频繁”总是涉及正支持度。
引理 2.2.4
(闭包保持支持度)
若 ,则 且 。
证明
(两个集合被同一批事务包含)
集族中每个事务都包含 ,所以它们的交集也包含 。由此得 。
现在比较两者的支持度。
- 若 ,则 是被取交集的集合之一,所以 。
- 反之,若 ,则 。
因此两个集合所计算的索引完全相同。
引理 2.2.5
(闭项集是闭包的不动点)
若 ,则 是闭项集,当且仅当 。
证明
(闭包是支持度相同的最大超集)
设 且 。包含 的事务的索引,构成包含 的事务的索引的子集。两个索引集大小相同,所以两者相等。因此每个包含 的事务都包含 ,由此得 。
这表明 是 具有相同支持度的最大超集。
- 若 ,则 是一个支持度相等的真超集,所以 不是闭项集。
- 若 ,则每个真超集 的支持度都不等于 ,因为支持度相等会迫使 。由反单调性,该支持度严格较小,所以 是闭项集。
概念视角结构
闭项集就是事务的交集
的超集构成庞大的集族 。闭包 是该集族中的一个特定成员,但它是由事务计算出来的,而不是通过搜索超集得到。具有正支持度的闭项集,恰好就是事务的非空子族的交集。一个方向就是 的定义。另一个方向:若 ,其中 是事务的非空子族,则 的每个成员都包含 ,所以 ,因而 。这样的交集不一定是你最初所取的某个特定 的超集。
极大蕴含闭
定理 2.2.6
(极大频繁项集都是闭项集)
每个极大频繁项集都是闭项集。
证明
(保持支持度的超集会是频繁的)
设 为极大频繁项集。则 ,所以 具有正支持度。
假设 不是闭项集。那么存在某个真超集 ,使得 。这样 就是 的一个频繁真超集,与极大性矛盾。
反例模式
闭频繁项集不一定是极大的
命题:每个闭频繁项集都是极大频繁项集。取 、,事务为 、、、、、。项集 出现在前三个事务中,所以 。它的超集 (支持度 )、(支持度 )及 (支持度 )都严格小于 ,所以 是闭频繁项集。然而 是 的频繁真超集,所以 不是极大项集。更正后的陈述就是上面证明的蕴含:极大频繁蕴含闭,反之不然。
重建支持度
命题 2.2.7
(由闭频繁项集恢复支持度)
对任意 , 是频繁项集,当且仅当 有一个频繁的闭超集。在此情况下,
证明
(闭包取得最大值)
设 是频繁项集。由闭包的两个引理, 是闭项集,包含 ,且支持度为 。由反单调性,任何其他超集 都有 。所以最大值在 处取得,并等于 。
反之,若 有一个频繁超集,则 至少等于该超集的支持度,所以 是频繁项集。
证明透视
为什么闭包是合适的见证
这个证明只有一步不寻常:指出取得最大值的超集,就是 。反单调性只给出对每个超集 都有 的不等式,所以最大值不会超过 。要取得等号,需要一个既是闭的、支持度又相等的超集,这正是两个闭包引理所提供的。“ 是频繁的”这个假设,用来确保见证 是频繁的,这就是为何最大值取遍闭频繁集。对非频繁的 ,陈述只涉及隶属关系:此时没有闭频繁超集,因为这样的超集的支持度会迫使 频繁。
因此,闭频繁集连同其支持度,构成一个无损的摘要:你可以从中还原每个频繁项集及其确切支持度。
极大频繁集只告诉你哪些项集是频繁的:恰好是某个极大集的子集。它们给出每个支持度的下界 ,但不给出确切计数。最后一个例题展示两个具有相同极大集族但支持度不同的数据库。
例题
例题 2.2.8
(十六个项集的支持度与闭包)
取 及 。事务多重集为:
| 索引 | 事务 |
|---|---|
注意 与 是重复的,并计算两次。闭包只在支持度为正时计算。最后一列对每个项集(包括支持度为零者)都使用闭性的定义。
| 包含它的事务 | supp | 频繁? | 闭? | ||
|---|---|---|---|---|---|
| 全部六个 | 6 | 是 | 是 | ||
| 1,2,3,4,6 | 5 | 是 | 是 | ||
| 1,2,3,5 | 4 | 是 | 是 | ||
| 1,2,4 | 3 | 是 | 否 | ||
| 4,5 | 2 | 是 | 是 | ||
| 1,2,3 | 3 | 是 | 是 | ||
| 1,2,4 | 3 | 是 | 是 | ||
| 4 | 1 | 否 | 否 | ||
| 1,2 | 2 | 是 | 否 | ||
| 5 | 1 | 否 | 是 | ||
| 4 | 1 | 否 | 否 | ||
| 1,2 | 2 | 是 | 是 | ||
| 无 | 0 | 否 | (未定义) | 否 | |
| 4 | 1 | 否 | 是 | ||
| 无 | 0 | 否 | (未定义) | 否 | |
| 无 | 0 | 否 | (未定义) | 是 |
全部六个事务的交集是 ,所以 是闭项集,支持度为 ,并且是频繁项集。
频繁项集(9 个)是 。闭频繁项集(7 个)是 、、、、、、。极大频繁项集(2 个)是 (因为 )和 (因为 、 及 的支持度均为 )。两者都是闭项集,正如关于极大项集的定理所预测。
例题 2.2.9
(由闭频繁集重建支持度)
在同一个数据库中,由闭频繁项集 、、、、、、 恢复支持度。
- 对于 :频繁闭超集为 及 。最大值为 ,与 相符。
- 对于 :唯一的频繁闭超集是 ,得出 。
- 对于 :没有频繁闭超集,所以 不是频繁项集,与 一致。
例题 2.2.10
(极大集合丢失计数)
从上面的数据库删去 ,得到第二个由五个事务组成的多重集。支持度的变化如下: 变为 , 变为 ,其他所有支持度保持不变。频繁集族完全相同,所以极大集仍然是 。然而, 的支持度在一个数据库中是 ,在另一个中是 。单凭极大集无法区分这两个数据库,闭频繁集却可以: 变为 , 变为 。
常见错误
(把重复的事务只计一次)
在上面的数据库中, 与 作为集合相等,但是两个独立的事务。若把它们合并,, 就会错误地变成非频繁。支持度计数是按索引计算的,重复的事务各自贡献一次。
练习
快速检查
(取 、,事务为 、、。求 、 及 。、、 之中哪些是闭项集?)
把包含各项集的事务取交集。
解答 · 答案
三个事务都包含 ,而 ,所以 。包含 的事务是前两个,所以 。包含 的事务是后两个,所以 。三者都不等于各自的闭包,所以都不是闭项集。尤其是这里 不是闭项集,因为全部事务的交集不是空集。
快速检查
(对同一个数据库,列出闭频繁项集及其支持度,以及极大频繁项集。)
先算出所有支持度:,而 、 的支持度为 。
解答 · 答案
支持度为 、、、、、、、。频繁项集是 。其中的闭项集是 、 及 ,因为 已证明不是闭项集。极大频繁项集是 与 。两者都是闭项集,与预期相符;而 是闭频繁项集,却不是极大项集。
快速检查
(只用同一数据库的闭频繁项集 、、,求 与 ,并判断 是否频繁。)
应用重建公式。
解答 · 答案
的频繁闭超集只有 ,所以 。 的频繁闭超集只有 ,所以 。没有闭频繁项集包含 ,所以 不是频繁项集;事实上 。
路线与检查清单
- 固定 、多重集 及整数 。重复的事务须分开计算。
- 列出所有支持度,或用 Apriori 挖掘频繁集。
- 对每个频繁的 ,通过把包含它的事务取交集来计算 。若 ,则把 标记为闭项集。
- 记住空集:只要所有事务的交集为空,空集就是闭项集。
- 若没有任何频繁集真包含频繁的 ,则把 标记为极大。验证每个极大集都出现在闭项集之中。
- 如存在的话,举出一个闭但非极大的频繁集。
- 从闭频繁集重建支持度。极大集只用于判断是否属于频繁集族。
- 把零支持度的约定与正支持度的交集构造分开处理。