一批事务可以反复出现某些组合,即使没有任何一行事前被标成“模式”。首要问题是精确定义何谓反复出现;其次,是找出每个符合条件的组合,而不必为所有可能项集作不必要计数。Apriori 用一个简单的包含关系,把两个问题连接起来。
关键是分清:证明某项集不可能频繁,与测量其确切支持度,是不同工作。已剪枝提案可能完全不需扫描事务。反过来,通过剪枝的提案仍须计数:必要证据不等于频繁性的证明。
计事务数,不计同一行内的重复出现
定义 2.1.1
(支持次数与支持度比例)
令 是有限项目全集,数据库是带索引的事务列表 ,其中 ,每个 。对于项集 ,定义
次数记录多少笔事务包含 的每个项目。最低支持次数为 时,满足 的项集称为频繁项集。这里挖掘非空项集,并使用正整数阈值。
每行对某项目的支持次数最多贡献一次,即使原购物记录买了多件相同物品也一样。两行内容相同的独立事务,却仍计两次。事务标识与项目数量回答不同问题。
使用四个抽象项目 及六笔合成教学事务。 这类简写代表项集 ,不是有次序的串。
| 事务 | 项目 |
|---|---|
例如, 出现在 ,所以 、。 与 各包含其中一项,却都没有同时包含两项。
证明哪些扩展可以排除
命题 2.1.2
(支持度具有反单调性)
若 ,则 且 。因此,若 , 的任何超集都不频繁;等价地,频繁项集的每个子集都频繁。
证明
(嵌套的事务索引集合)
若 ,每笔包含 的事务也包含 。因此, 所计算的事务索引集合,包含于 所计算的集合,得到
若 ,则对每个超集 都有 。取逆否命题,便得频繁项集的每个子集都频繁。
这就是 Apriori 使用的向下封闭性。论断针对同一个固定数据库及阈值。它没有说频繁子集会使较大项集也频繁:较大集合增加了要求,符合条件的事务可能更少。
对于某个 项提案,只需检查其全部直接 项子集,是否在上一层频繁族中。每个更小子集都包含于某个直接子集,再用向下封闭性便可涵盖它们。只要一个直接子集缺席,就有足够依据剪枝。
分清连接提案、可计数候选与频繁结果
用 表示大小为 的频繁项集。为免把剪枝步骤藏起来,用 表示剪枝前的连接提案, 表示保留以供计数的候选。有些描述在剪枝前也使用“候选”一词;操作本身比命名惯例重要。
固定项目次序 。如果 内两个已排序项集的前 项相同、最后项不同,就把它们连接。接着,如果提案某个直接子集不在 ,便剪去它。计算每个剩余候选的支持次数,达到 才保留于 。
例题 2.1.3
(完成 m = 2 的单项与双项层)
单项及双项的次数如下:
| 项集 | ||||
|---|---|---|---|---|
| 支持次数 |
| 项集 | ||||||
|---|---|---|---|---|---|---|
| 支持次数 |
全部单项都达标,所以 。把它们连接,生成六个双项提案。每个提案的单项子集都频繁,因此六个双项都接受计数。只有 达到次数阈值,得到
注意, 是已计数但未达阈值, 则已计数为零,两者都不同于“未计数”。
例题 2.1.4
(第三层:计数一个提案、剪去两个)
到了三项层,共同前缀连接是 、、。这个连接步骤不会生成 : 不在 ,没有可与 配合的频繁双项。
| 连接提案 | 子集判断 | 有否为自身作事务计数? | 结果 |
|---|---|---|---|
| 全部频繁 | 有:只有 匹配,次数为 1 | 已计数,但不频繁 | |
| 不在 | 没有 | 用 剪枝 | |
| 不在 | 没有 | 用 剪枝 |
因此 、、。不可能有更大频繁项集,否则它会有频繁三项子集。最后的非空频繁项集,就是四个单项及 的四个成员。
表格同时记录执行历史与数学事实。已剪枝记录没有通过自身扫描取得已测量支持次数,却不表示真实支持度没有定义:这里由 得到的界,甚至直接推出 。要分清这种推论与“算法扫描了 ”的声称。同样地,格图显示全部可能项集,不表示每个都曾生成或计数。
反例模式
直接子集频繁,是必要而非充分条件
在 时,三个双项 都频繁,但 次数只有 1。不同事务可以分别支持不同双项,而没有第二笔事务同时包含三项。因此,通过子集检查只足以让 接受计数,不能直接标为频繁。
错误在于倒转了推论。 频繁会迫使其双项频繁;双项频繁却不能迫使 频繁。
下面的追踪图可按任意阈值 m 重放这六笔事务,并把三个判断分开:连接提案、子集剪枝的证明,以及实际的支持度计数。
为什么连接与剪枝不会遗漏频繁项集
定理 2.1.5
(逐层 Apriori 恰好找出频繁项集)
对每个 ,经共同前缀连接、直接子集剪枝及计数所得的集族 ,恰好就是所有频繁 项集的集合。
证明
(以计数保证可靠性,按项集大小归纳证明完整性)
可靠性:只有已测量支持次数达到 的项集才进入 ,所以不会报告非频繁项集。
完整性:单项层由直接计数得到,这是归纳起点。假设 包含每个频繁 项集,并任取频繁 。按向下封闭性,子集 及 都频繁,因此均在 。它们共享所需前缀,连接就会生成 。 的其他直接子集也全部频繁,所以剪枝不能移除 。计数再确认其支持度,把它放入 。因此,逐层程序会找出每个非空频繁项集。
证明透视
每个要素各自保证什么
剪枝与计数的工作不同。在完整性的一半中,向下封闭性用了两次:一次是把 的两个特定 项子集放进 ,使共同前缀连接能生成 ;另一次是说明其他每个直接子集都在,使剪枝检验不会否决 。所选的两个子集(分别去掉最后一项和倒数第二项)必定符合连接条件,所以只用共同前缀连接并不会损失任何项集。剪枝证明的是排除安全,并不证明留下的项集频繁;这是计数的工作,它提供可靠性。完整性与支持度检查一起确立正确性,单独一项都不足够。
频繁项集与关联规则是不同输出
对于非空、互不相交的项集 ,如果 ,规则 的指标为
支持度以全部事务作分母,置信度则只用包含前件 的事务。如果 ,提升度定义为
例题 2.1.6
( 的支持度、置信度与提升度)
对于 ,支持度为 ,置信度为 ,提升度为 。反转规则,支持度及提升度不变,置信度却改为 。分母解释了这种不对称;频繁的无序项集本身并没有指定方向。
反例模式
较大置信度仍可低于后件的基准比例
规则 的置信度为 ,但全部事务中 出现于 。其提升度为 。在这份数据中,包含 的事务反而比整体数据库更少出现 。只看表面较大的置信度,就会错过这项比较。
这里置信度是经验条件比例,不是统计置信水平。这个比例及提升度,都不能确立因果机制或保证未来数据的表现。它们首先是用正确分母描述指定事务样本的指标。
常见错误
(以为置信度随前件单调)
不要没有新证明,就把支持度的子集规则套到置信度。在这些事务中,;前件加入 后降至 ,加入 却升至 1。条件比例可以向任何一方改变。
重现频繁项集阶段
这个小型 Python 实现用已排序 tuple 作为项集的规范表示,用集合存储事务。它采用共同前缀连接及直接子集剪枝,事务内的项目次序不影响结果。
from itertools import combinations
transactions = list(map(frozenset, ["ABC", "AB", "AC", "BC", "ABD", "AD"]))
items = tuple("ABCD")
minimum = 2
def support_count(itemset):
return sum(set(itemset).issubset(row) for row in transactions)
def join(previous):
proposals = set()
for left, right in combinations(sorted(previous), 2):
if left[:-1] == right[:-1]:
proposals.add(left + (right[-1],))
return sorted(proposals)
previous = set()
proposals = [(item,) for item in items]
level = 1
counted_candidates = 0
while proposals:
candidates = [
candidate for candidate in proposals
if level == 1 or all(
subset in previous for subset in combinations(candidate, level - 1)
)
]
measured = {candidate: support_count(candidate) for candidate in candidates}
counted_candidates += len(candidates)
frequent = {candidate: count for candidate, count in measured.items() if count >= minimum}
print(level, [("".join(candidate), frequent[candidate]) for candidate in sorted(frequent)])
previous = set(frequent)
proposals = join(previous)
level += 1
print("containment checks", counted_candidates * len(transactions))
输出的频繁层先是 ,再是 ,最后第三层为空。计数对象是四个单项、六个双项及一个三项;十一个候选各对六行,得到 66 次候选与事务包含检查。
这个数字不是 66 次数据库扫描,也不是运行时间公式。一层的全部候选可以在一次数据库扫描内计数;小程序只是把逐候选工作明确展示。显示输入表,并没有暗中替 或 作支持度扫描。
练习
快速检查
(使用相同六笔事务,改设 。写出 与 。第二频繁层能生成三项提案吗?会否遗漏更大的频繁项集?)
先计算单项与双项的次数。
解答 · 答案
,。唯一频繁双项没有另一个频繁双项可供连接,所以不生成三项提案。频繁三项必须有全部双项频繁,这里不可能成立,因此没有遗漏更大频繁项集。
快速检查
(在 下,为什么 被剪枝?由此得到什么上界?它的确切次数在数学上是否没有定义?事后直接检查事务,求出该次数,并解释这为何不改变先前的执行历史。)
看 的哪个直接子集不在 。
解答 · 答案
的次数为 1,并且不在 ,所以 。无论挖掘过程有没有测量,真实次数都是有定义的。另行检查只找到 ,所以次数为 1。这个独立计数并不表示先前的 Apriori 过程扫描过已被剪去的提案。
快速检查
(对 ,计算支持度、置信度与提升度。有多少笔事务支持它观察到的完美置信度?这对把该规则当作全称陈述有何启示?)
使用 、 与 。
解答 · 答案
、、,所以支持度为 ,置信度为 1,提升度为 。只有 包含前件,两者都包含 ,这确立的是样本中的比例,并不能确立将来每笔包含 的事务都必定包含 。
快速检查
(把每笔事务复制一次,得到十二行。支持次数、支持度分数、置信度与提升度会怎样?若绝对阈值仍为 ,与原数据库相比,哪些项集新成为频繁?保留原来的最小支持度分数 是否有相同效果?)
比较次数与分母如何变化。
解答 · 答案
每个支持次数都加倍,但分数、置信度与提升度不变,因为相应的分母同样加倍。保持绝对阈值 时,原来次数为一的项集被纳入: 新成为频繁。改为保留支持度分数 ,则要求十二行中至少有四行,所以原来的频繁族得以保持。必须说明阈值的单位。