Efficient Frequent Itemset Mining

Frequent itemset mining finds sets of items that occur together in at least a minimum number of transactions (min_sup). It is the first and costliest step of association rule mining. With n items there are up to 2^n - 1 itemsets, so efficient methods are essential.

1. Apriori (level-wise, generate-and-test)

• Uses the Apriori property: every subset of a frequent itemset is frequent.
• Finds L1, then generates candidates Ck from Lk-1 (join), prunes using the property, and counts support by scanning the database; repeats until no more frequent itemsets.
• Drawbacks: many candidates and many database scans.

2. Improvements to Apriori

Technique	Idea
Hash-based itemset counting	Hash k-itemsets into buckets; a bucket with a count below min_sup cannot contain frequent itemsets, so those candidates are dropped
Transaction reduction	A transaction with no frequent k-itemset is not needed in later scans
Partitioning	Split the database; a frequent itemset must be frequent in at least one partition; only 2 scans needed
Sampling	Mine a random sample with a lower threshold; verify on the full data
Dynamic itemset counting	Add new candidates while scanning, at checkpoints, to reduce scans

3. FP-Growth (pattern growth, no candidate generation)

1. Scan the database once to find frequent items and sort them in descending support.
2. Scan again to build a compact FP-tree (a prefix tree with a header table of node links).
3. For each frequent item, build its conditional pattern base and conditional FP-tree, and mine it recursively (divide-and-conquer).

Advantages: only two database scans, no candidate generation, and the tree compresses the data. It is much faster than Apriori on large or dense data.

4. Eclat (vertical data format)

Stores each item with its transaction-ID list (TID-list). The support of an itemset is found by intersecting TID-lists, so no repeated database scans are needed.

5. Closed and maximal itemsets

Mining only closed or maximal frequent itemsets gives a compact summary of all frequent itemsets.

Comparison

Method	Candidates	Scans	Best for
Apriori	Yes (many)	One per level	Small data, simple implementation
FP-Growth	No	2	Large and dense data
Eclat	Yes (via TID-lists)	Few	Sparse data that fits in memory

Conclusion

Efficiency comes from pruning with the Apriori property, reducing database scans, or avoiding candidate generation altogether, as FP-Growth does.