Complete RGPV exam-oriented notes on frequent itemsets, support, confidence, lift, Boolean and multilevel association rules, Apriori algorithm, FP-tree construction, time-series association rules and current trends.
Association rule mining is a data-mining technique used to discover interesting relationships, correlations and co-occurrence patterns among items in large transactional databases.
General Form
X → Y
Here, X and Y are itemsets and X ∩ Y = ∅. The rule means that when X occurs in a transaction, Y is also likely to occur.
Example: Bread → Butter means customers who buy bread may also buy butter.
Main Objective
Discover frequently occurring item combinations.
Generate useful if-then relationships.
Support recommendation and business decisions.
Understand customer purchasing behavior.
Market Basket Analysis
Association rules are widely used in market basket analysis to study products purchased together.
A single object or product, such as milk or bread.
Itemset
A collection of one or more items.
{Milk, Bread} is a 2-itemset.
Transaction
A set of items purchased or occurring together.
k-Itemset
An itemset containing exactly k items.
Frequent Itemset
An itemset whose support is equal to or greater than minimum support.
Candidate Itemset
A possible frequent itemset generated during an algorithm.
Antecedent and Consequent
In X → Y, X is the antecedent and Y is the consequent.
Transaction ID
Items
T1
Milk, Bread, Butter
T2
Bread, Diaper, Beer
T3
Milk, Bread, Diaper, Beer
T4
Milk, Bread, Diaper, Butter
3. Support, Confidence and Lift 14 Marks
Support
Support measures how frequently an itemset or rule appears in the database.
Support(X → Y) = Count(X ∪ Y) / Total Transactions
Confidence
Confidence measures how often Y occurs in transactions containing X.
Confidence(X → Y) = Support(X ∪ Y) / Support(X)
Lift
Lift measures whether X and Y occur together more often than expected if they were independent.
Lift(X → Y) = Confidence(X → Y) / Support(Y)
Interpretation of Lift
Lift > 1: positive association.
Lift = 1: X and Y are independent.
Lift < 1: negative association.
Suppose 4 out of 10 transactions contain Bread and 3 of those also contain Butter.
Support(Bread → Butter) = 3/10 = 30%.
Confidence(Bread → Butter) = 3/4 = 75%.
Strong Association Rule
A rule is considered strong when it satisfies both minimum support and minimum confidence.
4. Association Rule Mining Process 14 Marks
Two Main Steps
Step 1: Frequent Itemset Generation
Find all itemsets whose support is greater than or equal to the minimum support threshold.
Step 2: Rule Generation
Generate association rules from frequent itemsets and retain rules satisfying minimum confidence.
Transactional Database
|
Set Minimum Support
|
Generate Frequent Itemsets
|
Set Minimum Confidence
|
Generate Strong Rules
|
Evaluate using Lift and Other Measures
Why Separate These Steps?
Frequent-itemset generation is usually the most computationally expensive task. Once frequent itemsets are available, rule generation is comparatively simpler.
5. Single-Dimensional Boolean Association Rules 14 Marks
A single-dimensional Boolean association rule contains only one predicate or dimension, and each item is represented as present or absent.
Example
buys(Customer, Bread) → buys(Customer, Butter)
Why Boolean?
The rule checks only whether an item occurs, not its quantity or numeric value.
Single Dimension
The rule uses one type of predicate, such as buys.
Characteristics
Uses binary presence or absence.
Mostly used in transaction databases.
Easy to interpret.
Common in market basket analysis.
Boolean Transaction Representation
Transaction
Milk
Bread
Butter
T1
1
1
1
T2
0
1
0
T3
1
1
0
6. Multi-Level Association Rules 14 Marks
Multi-level association rules discover relationships at different levels of a concept hierarchy.
The same minimum support is used at every concept level.
Reduced Minimum Support
Lower-level items use a smaller minimum support because they occur less frequently.
Challenges
Too many rules may be generated.
Low-level rules may have low support.
Redundant rules can appear across hierarchy levels.
Correct threshold selection is difficult.
Higher-level rules are more general, while lower-level rules are more specific.
7. Apriori Algorithm 14 Marks
Apriori is a level-wise frequent-itemset mining algorithm that uses the Apriori property to reduce the search space.
Apriori Property
Every non-empty subset of a frequent itemset must also be frequent.
Contrapositive Form
If an itemset is infrequent, all of its supersets must also be infrequent.
Main Steps
Scan the database and find frequent 1-itemsets.
Join frequent (k−1)-itemsets to create candidate k-itemsets.
Prune candidates having an infrequent subset.
Scan the database and count candidate support.
Keep candidates satisfying minimum support.
Repeat until no new frequent itemset is found.
Database Scan
|
Frequent 1-Itemsets L1
|
Join + Prune
|
Candidate 2-Itemsets C2
|
Support Counting
|
Frequent 2-Itemsets L2
|
Repeat for k = 3, 4, ...
Apriori Pseudocode
L1 = frequent 1-itemsets
for (k = 2; L(k-1) is not empty; k++) {
Ck = apriori_gen(L(k-1))
for each transaction t {
increment count of candidates in Ck contained in t
}
Lk = candidates in Ck with minimum support
}
return union of all Lk
8. Apriori Algorithm Example 14 Marks
Consider the following database with minimum support count = 2.
TID
Items
T1
A, B, C
T2
A, C
T3
A, D
T4
B, C
T5
A, B, C
Step 1: Frequent 1-Itemsets
Item
Support Count
Status
A
4
Frequent
B
3
Frequent
C
4
Frequent
D
1
Removed
Step 2: Candidate 2-Itemsets
Candidate
Support Count
Status
{A,B}
2
Frequent
{A,C}
3
Frequent
{B,C}
3
Frequent
Step 3: Candidate 3-Itemset
Candidate
Support Count
Status
{A,B,C}
2
Frequent
Final Frequent Itemsets
{A}, {B}, {C}
{A,B}, {A,C}, {B,C}
{A,B,C}
9. Generating Association Rules 14 Marks
After finding frequent itemsets, rules are generated from their non-empty subsets.
Example from {A, B, C}
A → BC
B → AC
C → AB
AB → C
AC → B
BC → A
Rule Selection
For every possible rule, calculate confidence and retain only those that satisfy minimum confidence.
Confidence(A B → C) = Support(A B C) / Support(A B)
Rule Pruning
If a rule does not satisfy minimum confidence, some related rules can be eliminated without complete evaluation.
10. Advantages and Limitations of Apriori 14 Marks
Advantages
Simple and easy to understand.
Uses effective downward-closure pruning.
Produces complete frequent itemsets.
Works well for small and moderately dense datasets.
Limitations
Requires repeated database scans.
Generates a large number of candidate itemsets.
Can be slow for low support thresholds.
Memory usage increases with candidates.
Performs poorly on long frequent patterns.
The main Apriori bottlenecks are candidate generation and multiple database scans.
11. FP-Growth Algorithm 14 Marks
FP-Growth is a frequent-pattern mining algorithm that compresses the database into an FP-tree and mines patterns without candidate generation.
Main Idea
Scan the database only twice.
Store frequent items in a compact tree.
Use divide-and-conquer mining.
Avoid candidate-itemset generation.
Major Steps
Scan the database and find frequent 1-items.
Sort frequent items by descending support.
Scan transactions again.
Remove infrequent items and arrange items in support order.
Node links: connect nodes containing the same item.
Example Ordered Transactions
T1: A, C, B
T2: A, C
T3: A
T4: C, B
T5: A, C, B
Simplified FP-Tree
Null
/ \
A:4 C:1
| |
C:3 B:1
|
B:2
Compression
Transactions sharing common prefixes use the same tree path, reducing storage.
The ordering of items by support increases prefix sharing and improves compression.
13. Mining the FP-Tree 14 Marks
Conditional Pattern Base
A collection of prefix paths ending with a selected suffix item.
Conditional FP-Tree
A smaller FP-tree built from the conditional pattern base of an item.
Mining Process
Start from the least frequent item in the header table.
Collect all prefix paths containing that item.
Create its conditional pattern base.
Remove items below minimum support.
Construct a conditional FP-tree.
Combine the suffix item with patterns in the conditional tree.
Repeat recursively.
Suffix Item B
|
Prefix Paths Ending in B
|
Conditional Pattern Base
|
Conditional FP-Tree
|
Patterns: {B}, {A,B}, {C,B}, {A,C,B}
Advantages
No candidate generation.
Only two full database scans.
Efficient for dense datasets.
Good for long patterns.
Limitations
FP-tree construction can be complex.
Tree may become large for sparse data.
Incremental updates are difficult.
14. Apriori vs FP-Growth 14 Marks
Feature
Apriori
FP-Growth
Main approach
Candidate generation
Pattern-growth approach
Database scans
Multiple scans
Usually two full scans
Data structure
Candidate itemsets
FP-tree
Performance
Slower on large dense data
Usually faster
Memory issue
Large candidate sets
Large tree in some datasets
Implementation
Simpler
More complex
Best use
Small or sparse datasets
Large or dense datasets
FP-Growth improves over Apriori by eliminating candidate generation and reducing database scans.
15. Time-Series Mining Association Rules 14 Marks
Time-series association rule mining discovers relationships among events or values that occur in temporal order or within specified time intervals.
Examples
A rise in temperature is followed by increased electricity demand.
A product promotion is followed by higher sales within seven days.
A stock-price movement is associated with a later trading pattern.
Types of Temporal Association Rules
Time-constrained association rules
Sequential association rules
Periodic association rules
Lagged association rules
Trend-based rules
General Form
Event X at time t → Event Y within time interval Δt
Steps
Collect time-stamped data.
Order records by time.
Create time windows or sequences.
Generate temporal itemsets.
Calculate temporal support and confidence.
Evaluate periodicity, lag and trend.
Challenges
Choosing an appropriate time window
Irregular time intervals
Noise and missing observations
Changing patterns over time
16. Latest Trends in Association Rule Mining 14 Marks
High-Utility Itemset Mining
Finds patterns based on profit, importance or utility rather than frequency alone.
Rare Association Rules
Discovers important but infrequent relationships, such as rare medical or fraud patterns.
Negative Association Rules
Finds relationships involving absence, such as customers buying A but not B.
Constraint-Based Mining
Uses user-defined constraints to reduce uninteresting patterns.
Streaming Association Mining
Discovers rules from continuously arriving data.
Privacy-Preserving Mining
Protects sensitive data while discovering useful patterns.
Distributed and Parallel Mining
Uses clusters, cloud systems or distributed frameworks for large-scale mining.
Fuzzy Association Rules
Uses linguistic values such as low, medium and high instead of strict numeric boundaries.
Graph and Social Network Rules
Discovers associations among connected users, entities and interactions.
Explainable Pattern Mining
Focuses on understandable and actionable association rules.
17. Applications of Association Rule Mining 14 Marks
Retail: market basket analysis and shelf arrangement.
E-commerce: product recommendations and cross-selling.
Healthcare: symptom and disease associations.
Banking: fraud and transaction-pattern analysis.
Telecommunication: service usage and churn patterns.
Web mining: page co-visit analysis.
Education: relationships among learning activities and results.
Manufacturing: fault and component failure relationships.
18. Challenges in Association Rule Mining 14 Marks
Very large number of possible itemsets.
Selection of support and confidence thresholds.
Generation of redundant or obvious rules.
Handling rare but important patterns.
Processing high-dimensional data.
Mining dynamic and streaming data.
Privacy and security concerns.
Evaluating usefulness beyond support and confidence.
Interestingness Measures
Measures such as lift, conviction, leverage and correlation help identify more meaningful rules.
Unit 3 Quick Revision
Association rules have the form X → Y.
Support measures frequency.
Confidence measures rule reliability.
Lift measures association strength relative to independence.
A frequent itemset satisfies minimum support.
Apriori uses the downward-closure property.
Apriori generates and prunes candidate itemsets.
FP-Growth avoids candidate generation.
An FP-tree compresses transactions using shared prefixes.
Multi-level rules use concept hierarchies.
Time-series rules include temporal order and time windows.
High-utility, rare, negative and streaming rules are important modern trends.
Important RGPV Exam Questions
Long Answer Questions
Define association rule mining and explain support, confidence and lift.
Explain the complete association rule mining process.
What are single-dimensional Boolean association rules?
Explain multi-level association rules with a concept hierarchy.
State and explain the Apriori property.
Explain the Apriori algorithm with pseudocode.
Solve a transactional database using the Apriori algorithm.
Explain candidate generation and pruning in Apriori.
Discuss the advantages and limitations of Apriori.
Explain the FP-Growth algorithm with a neat diagram.
Explain FP-tree construction with an example.
What are conditional pattern bases and conditional FP-trees?
Compare Apriori and FP-Growth.
Explain time-series association rule mining.
Discuss recent trends in association rule mining.
Short Answer Questions
Define frequent itemset.
What is minimum support?
Define confidence.
What is lift?
State the Apriori property.
What is candidate pruning?
Define FP-tree.
What is a conditional pattern base?
What is a multilevel association rule?
Define a temporal association rule.
Exam Strategy: Always write formulas for support, confidence and lift. For Apriori, show C1, L1, C2, L2 and further levels. For FP-Growth, draw an FP-tree and explain conditional pattern bases.