Efficient algorithms for mining closed itemsets and their lattice structure

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 usi...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on knowledge and data engineering 2005-04, Vol.17 (4), p.462-478
Main Authors: Zaki, M.J., Hsiao, C.-J.
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Association rules
closed itemset lattice
Computation
Computer science
control theory
systems
Data mining
Data visualization
Degradation
Exact sciences and technology
Footprints
Frequency
frequent itemsets
Index Terms- Closed itemsets
Information systems. Data bases
Itemsets
Lattices
Memory organisation. Data processing
Mining
Multidimensional systems
Searching
Software
State of the art
Transaction databases
Visual databases
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1041-4347
1558-2191
DOI:10.1109/TKDE.2005.60