35 A priori & Association rules
Fast Algorithm for Mining Association Rule
•Consider shopping cart filled with several items
•Market basket analysis tries to answer the following questions:
–Who makes purchases?
–What do customers buy together?
–In what order do customers purchase items?
–When do customers purchase the most and what?
1.Concurrences
–80% of all customers purchase items X, Y, and Z together.
2.Association rules
–60% of all customers who purchase X and Y also buy Z.
3.Sequential patterns
–60% of customers who first buy X also purchase Y within three weeks.
Basic idea of Apriori
–Using anti-monotone property to reduce candidate itemsets
–Any subset of a frequent itemset must be also frequent
–In other words, any superset of an infrequent itemset must also be infrequent
Basic operations of Apriori
–Candidate generation
–Candidate counting
How to generate the candidate itemsets?
–Self-joining
–Pruning infrequent candidates
Lift
In data mining and association rule learning, lift is a measure of the performance of a targeting model (association rule) at predicting or classifying cases as having an enhanced response (with respect to the population as a whole), measured against a random choice targeting model.
