ECLAT 频繁项集挖掘
- 提出者
- Mohammed J. Zaki
- 年份
- 2000
- 类型
- Frequent-itemset mining algorithm (vertical format)
- 类别
- Pattern mining
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
ECLAT 由 Mohammed Zaki 于 2000 年提出,它使用垂直数据表示来挖掘频繁项集:它不扫描事务,而是为每个项存储包含该项的事务 ID 集合(即 tidset),并通过交集 tidset 来计算任何项集的支持度。这种深度优先、基于交集的方法快速且内存高效,是 Apriori 的水平扫描和 FP-Growth 的树结构的替代方案。
方法背后的直觉
大多数项集挖掘器逐行思考:每个事务中包含哪些项?ECLAT 将表格侧向翻转。对于每个项,它都保留一个包含该项的事务列表。现在,一对项的支持度就是它们两个列表重叠部分的大小——一个简单的集合交集——而且您永远不需要重新扫描数据库。为了找到更长的频繁项集,只需对较短项集的列表进行交集操作。以深度优先的方式遍历并修剪,只要交集变得太小就进行修剪,这样可以有效地枚举所有频繁项集。
历史学
Mohammed Zaki 在其 2000 年 IEEE TKDE 关于可伸缩关联挖掘的论文中提出了 ECLAT 和垂直挖掘范式,后来通过差集(dECLAT)对其进行了改进。它与 Apriori(1994 年,水平候选生成)和 FP-Growth(2000 年,基于树)一起,成为频繁项集算法的三个经典家族之一,每个家族在扫描、内存和数据密度之间进行不同的权衡。ECLAT 仍然是数据挖掘工具包中的标准选项。
何时使用
当垂直的、基于交集的方法适合数据时,请使用 ECLAT 进行频繁项集挖掘——它通常在密集数据集上非常快,并避免重复的数据库扫描,使其成为 Apriori 的有力替代品,并与 FP-Growth 齐名。当 tidset 大小适中且适合内存时,它表现出色,并且差集变体能很好地处理密集数据。它的成本:对于大型稀疏数据集,频繁项的 tidset 可能很大且占用大量内存,中间交集会增加开销,并且像所有基于支持度的挖掘一样,它对最小支持度阈值敏感。一如既往,频繁项集只是第一阶段;具有置信度/提升度的关联规则随后生成。根据数据密度和内存选择 ECLAT、FP-Growth 和 Apriori。
局限与注意事项
- 频繁项的 tidset 可能很大,在大型数据集上占用内存。
- 中间交集结果增加了内存/时间开销。
- 不如水平(Apriori)表示直观。
- 与所有项集挖掘一样,对最小支持度阈值敏感。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 通过快速 tidset 交集计算支持度——无需重复数据库扫描。
- 深度优先搜索与前缀等价类重用工作并局部化内存。
- 在密集数据集上通常非常高效,与 FP-Growth 具有竞争力。
- 差集优化进一步减少了内存和交集成本。
应用
- 市场购物篮和零售关联挖掘。
- 网络和点击流共现分析。
- 生物信息学频繁共现发现。
- 任何偏爱垂直、基于交集方法的频繁项集任务。
- 差集 ECLAT 表现出色的密集事务数据集。
使用方式
使用方式
数据库一次性转换为垂直格式:每个项映射到其 tidset,即它出现的事务 ID 集合。这是关键的数据结构——所有后续工作都是对 tidset 进行集合操作,而不是对原始事务进行多次扫描。
公式
\text{for each item } i:\ t(i) = \{ \text{transaction ids containing } i \}项集的支持度是其各项 tidset 交集的基数——即包含所有这些项的事务数量。计数变成了交集操作,这很快,并且频繁的单个项(其 tidset 足够大)为搜索提供了种子。
公式
\text{support}(X) = | \textstyle\bigcap_{i\in X} t(i) |通过交集 tidset 来扩展项集:X ∪ {y} 的 tidset 是 X 的 tidset 与 {y} 的 tidset 的交集。ECLAT 在等价类(共享相同前缀的项集)内深度优先地探索项集格,因此交集可以重用,并且搜索保持局部性。
公式
t(X\cup Y) = t(X) \cap t(Y)\ \text{(intersect to extend itemsets)}只有当扩展的 tidset(因此支持度)达到最小支持度阈值时才保留它;否则该分支将被修剪(反单调性:任何超集都不可能是频繁的)。差集(diffsets)——只存储 tidset 之间的差异——是一种常见的优化,可以进一步减少内存和交集成本。
公式
\text{keep extensions with } \text{support} \ge \text{minsup}常见陷阱
- 挖掘非常大的稀疏数据,其中 tidset 会耗尽内存——考虑使用差集或 FP-Growth。
- 将最小支持度设置得过低,导致产生数量过多的项集。
- 将频繁项集与关联规则混淆(规则是单独的步骤)。
- 在密集数据上忽略差集变体,而它能极大地帮助提高效率。
常见问题
ECLAT 与 Apriori 和 FP-Growth 有何不同?
这三种方法都用于发现频繁项集。Apriori 使用水平格式,涉及候选生成和多次扫描;FP-Growth 将数据压缩成树并递归挖掘;ECLAT 使用垂直 tidset 格式,并通过深度优先地交集事务 ID 列表来计算支持度。ECLAT 和 FP-Growth 避免了 Apriori 的重复扫描。
什么是 tidset?
tidset(事务 ID 集合)是包含给定项或项集的事务列表。ECLAT 垂直存储这些信息,并将项集的支持度计算为其各项 tidset 交集的大小,从而将计数转换为集合交集。
什么是差集?
差集仅存储项集的 tidset 与其父项集的 tidset 之间的差异,而不是完整的 tidset。在密集数据上,这大大减少了内存和交集成本,使 dECLAT 变体具有显著的效率优势。
相关方法
参考文献
Zaki, M. J. (2000). Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3), 372–390.
打开 DOI 文献已复制。