Apriori Principle, Candidate Generation and Pruning, and Comparison with FP-Growth

Apriori principle

All non-empty subsets of a frequent itemset must also be frequent. Equivalently, if an itemset is infrequent, every superset of it is also infrequent (the anti-monotone property of support).

Example: if {A, D} is infrequent, then {A, B, D}, {A, C, D} and {A, B, C, D} cannot be frequent, so they need not be checked.

How Apriori works (level-wise search)

1. Scan the database and find frequent 1-itemsets L1.
2. Candidate generation (join step): join Lk-1 with itself to produce candidate k-itemsets Ck.
3. Pruning: remove any candidate that has a (k-1)-subset that is not in Lk-1.
4. Scan the database to count the support of the remaining candidates; keep those with support at least min_sup as Lk.
5. Repeat until no new frequent itemsets are found.

How candidate generation and pruning reduce the search space

With n items there are up to 2^n - 1 possible itemsets, too many to test.

• Join only combines frequent itemsets, so only itemsets that could be frequent are generated.
• Pruning with the Apriori property removes candidates before the costly database scan.

Example: L2 = {AB, AC, AD, BC}. The join step (itemsets sharing the first item) gives ABC, ABD and ACD. ABC survives, because AB, AC and BC are all frequent. ABD is pruned because BD is not in L2, and ACD is pruned because CD is not in L2. Only ABC is counted in the database scan.

Apriori vs FP-Growth

Basis	Apriori	FP-Growth
Approach	Generate-and-test (candidate generation)	Pattern growth using an FP-tree
Candidate generation	Required; can be huge	None
Database scans	One per level (many scans)	Two scans in total
Data structure	Candidate sets and hash trees	Compact FP-tree plus header table
Strategy	Breadth-first, level-wise	Divide-and-conquer (conditional pattern bases)
Speed on large or dense data	Slow	Much faster
Memory	Large candidate sets	FP-tree must fit in memory; compact for dense data
Complexity to implement	Simple	More complex

Conclusion

Apriori is simple and prunes well using the anti-monotone property, but it is costly because of repeated scans and many candidates. FP-Growth removes candidate generation by compressing the data into an FP-tree, so it is more scalable.