Overview
Apriori uses the fact that an itemset cannot be frequent if any of its subsets are infrequent, which prunes candidate generation.
ExtendedSource checked
Apriori Algorithm
Finds frequent itemsets by expanding only candidates whose subsets are frequent.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Machine Learning
- Difficulty
- Intermediate
- Family
- Association Rule Mining
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 1
- Code example
- Ready
- Visualization
- Ready
Core Concepts
frequent itemsetsupport thresholdcandidate pruningassociation rule
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(candidate_count * n)
Worst
O(2^items)
Space
O(candidate_count)
When to Use
- Use when training predictive models needs frequent itemset.
- Use when the input matches the assumptions behind association Rule Mining.
When Not to Use
- Avoid when the dataset is too small or poorly labeled for the model capacity being used.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Finds frequent itemsets by expanding only candidates whose subsets are frequent
- Uses frequent itemset and support threshold to guide the work.
- Produces trained model.
Use Cases
- Training predictive models
- Finding patterns in data
- Building learned representations
Inputs
- Training data
- Model parameters
- Loss or scoring rule
Outputs
- Trained model
- Predictions
- Training diagnostics
Key Formulas (1)
Support
support(A) = transactionscontaining A / totaltransactions
support(A) = transactions_containing_A / total_transactionsMeasures how often an itemset appears.
Pseudocode
- 1.Prepare the inputs and state needed for Apriori Algorithm.
- 2.Apply the frequent itemset step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return trained model.
Canonical Example
- Input
- Apriori Algorithm input with a small representative case
- Output
- Trained model
- Explanation
- Apriori Algorithm applies frequent itemset to produce trained model.
Implementation Notes
- Separate training, validation, and test data before tuning model choices.
- Keep the frequent itemset step separate enough to test independently.
Common Pitfalls
- Evaluating only on training data hides overfitting and data leakage.
- Forgetting to check edge cases can make Apriori Algorithm look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow data, model state, and the training signal that drives updates.
Step 1 of 4: Prepare the inputs and state needed for Apriori Algorithm.
machine-learning-mechanismNotes
Apriori Algorithm should be used with the assumptions and tradeoffs of association Rule Mining in mind.
Sources (1)
What each reference supports for this entry.
Agrawal-Srikant Apriori
PaperOriginal Apriori reference for frequent itemset candidate generation and association-rule mining.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageOften paired withHash Table
Apriori implementations commonly use hash tables to count candidate itemsets efficiently.
Related Algorithms
Tags
Machine LearningAssociation RulesFrequent ItemsetData Mining