Short note: Apriori and its drawbacks

Apriori is the classic algorithm (Agrawal and Srikant, 1994) for mining frequent itemsets and association rules from transaction data. It uses a level-wise, breadth-first search: the frequent k-itemsets L_k are used to generate candidate (k+1)-itemsets, and the database is scanned to count their support.

Key idea: the Apriori property

All non-empty subsets of a frequent itemset must also be frequent; so any candidate with an infrequent subset is pruned without counting.

Steps

1. Scan the database and find the frequent 1-itemsets L₁ (support ≥ min_sup).
2. Join: build candidates C_{k+1} from L_k.
3. Prune: remove candidates having an infrequent k-subset.
4. Count: scan the database to count support and obtain L_{k+1}.
5. Repeat until no new frequent itemsets are found; then generate rules X → Y with confidence ≥ min_conf.

Example: {A, C, D}, {B, C, E}, {A, B, C, E}, {B, E} with min_sup = 2 give L₁ = {A, B, C, E}, L₂ = {AC, BC, BE, CE}, L₃ = {BCE}.

Drawbacks

• Many database scans: one scan for each level; for a frequent itemset of size n, n scans are needed.
• Huge candidate sets: 10⁴ frequent 1-itemsets give over 10⁷ candidate 2-itemsets; very long patterns need up to 2¹⁰⁰ candidates.
• Heavy counting cost (each candidate must be matched with every transaction), and a lot of memory.
• Slow at low minimum support or on dense data.
• Generates a very large number of rules, many uninteresting.

Improvements: hashing (DHP), transaction reduction, partitioning, sampling, dynamic itemset counting, and the FP-growth algorithm.