Efficient algorithms for mining closed itemsets and their lattice structure
Efficient algorithms for mining closed itemsets and their lattice structure
复制标题
DOI：
10.1109/tkde.2005.60
复制
发表时间：
2005-04
影响因子：
8.9
通讯作者：
Mohammed J. Zaki;Ching-Jui Hsiao
中科院分区：
文献类型：
--
作者：
Mohammed J. Zaki;Ching-Jui Hsiao
频繁闭项集的集合唯一地确定了所有项集的确切频率，但它可以比所有频繁项集的集合小几个数量级。在本文中，我们提出了 CHARM，一种用于挖掘所有频繁闭项集的有效算法。它使用双项集-tidset 搜索树枚举闭集，并使用跳过许多级别的高效混合搜索。它还使用一种称为差异集的技术来减少中间计算的内存占用。最后，它使用基于快速哈希的方法来删除计算过程中发现的任何“非封闭”集。我们还提出了 CHARM-L，一种输出闭项集格的算法，这对于规则生成和可视化非常有用。对许多真实和合成数据库的广泛实验评估表明，CHARM 是一种最先进的算法，其性能优于以前的方法。此外，CHARM-L 显式生成频繁闭项集格。
The set of frequent closed itemsets uniquely determines the exact frequency of all itemsets, yet it can be orders of magnitude smaller than the set of all frequent itemsets. In this paper, we present CHARM, an efficient algorithm for mining all frequent closed itemsets. It enumerates closed sets using a dual itemset-tidset search tree, using an efficient hybrid search that skips many levels. It also uses a technique called diffsets to reduce the memory footprint of intermediate computations. Finally, it uses a fast hash-based approach to remove any "nonclosed" sets found during computation. We also present CHARM-L, an algorithm that outputs the closed itemset lattice, which is very useful for rule generation and visualization. An extensive experimental evaluation on a number of real and synthetic databases shows that CHARM is a state-of-the-art algorithm that outperforms previous methods. Further, CHARM-L explicitly generates the frequent closed itemset lattice.