Association Rules: From Apriori Pruning to FP-Growth

Association mining asks which items appear together more often than expected. A rule such as coffee -> milk is not useful merely because its confidence is high: milk may be common in almost every basket.

Lift above 1 signals positive association; it does not prove causality or business value.

Apriori: prune with downward closure

If an itemset is frequent, every subset must also be frequent. Conversely, an infrequent subset means every superset containing it is infrequent. Apriori uses that fact to generate candidates level by level and remove impossible branches before counting them.

Its weakness is repeated database scans and candidate explosion when transactions are wide or the support threshold is low.

FP-Growth: compress repeated prefixes

FP-Growth scans to count frequent items, orders them consistently, and inserts transactions into an FP-tree. Shared prefixes reuse nodes. Mining conditional pattern bases then finds frequent itemsets without explicitly generating every candidate.

The tree is not magic compression: if transactions share little structure, it can remain large. The choice depends on sparsity, support threshold, memory, and whether incremental updates matter.

In plain terms: Apriori asks “which combinations are still possible?” FP-Growth asks “which transaction prefixes can share storage?”

Before shipping rules, filter trivial consequents, validate on a later time window, and estimate the cost of acting on a false association. A statistically frequent pattern can still be operationally useless.

Review card

• Support controls prevalence; confidence is conditional frequency.
• Lift corrects for a popular consequent.
• Apriori prunes candidates with subset monotonicity.
• FP-Growth trades candidate generation for a compressed tree.
• Association is a hypothesis generator, not a causal claim.