Association rules, support, confidence

Association rule mining finds frequent patterns, associations and correlations among items in transaction databases. An association rule has the form X → Y, where X and Y are disjoint itemsets, and it means "transactions that contain X tend to contain Y".

Example: market-basket analysis finds {bread, butter} → {milk}.

Definitions

Consider these 5 transactions: T1 {bread, milk}; T2 {bread, butter, milk}; T3 {bread, butter}; T4 {milk, butter}; T5 {bread, butter, milk}.

• Itemset: a set of items; a k-itemset has k items.
• Support count σ(X): number of transactions containing X. σ({bread, milk}) = 3.
• Support of a rule X → Y: s = σ(X ∪ Y)/N, the fraction of transactions containing both X and Y. It shows how often the rule applies.
• Confidence of X → Y: c = σ(X ∪ Y)/σ(X), how often Y appears in transactions containing X. It shows reliability.
• Frequent itemset: an itemset whose support is at least the user-given minimum support (min_sup).
• Strong rule: a rule satisfying both min_sup and min_conf.

Numerical illustration

For {bread} → {milk}: σ(bread, milk) = 3, σ(bread) = 4, N = 5.

• Support = 3/5 = 60%
• Confidence = 3/4 = 75%

If min_sup = 40% and min_conf = 70%, then the rule is strong.

Mining steps

1. Find all frequent itemsets (Apriori, FP-growth).
2. Generate strong rules from each frequent itemset: for each non-empty proper subset X of itemset L, output X → (L − X) if σ(L)/σ(X) ≥ min_conf.

Rules can also be checked using lift = confidence/support(Y), to remove misleading rules.