Rule Generation

Source: Unit 4 §8

Frequent itemset generation is done. This is the cheap second half: turning each frequent itemset into the rules worth keeping.

Generating rules from a frequent itemset

Given a frequent itemset L, find all non-empty subsets f ⊂ L such that the rule f → (L − f) meets min confidence.

For L = {A,B,C,D} the candidate rules include ABC→D, ABD→C, …, A→BCD, …, AB→CD, ….

#NumbersHow many rules per itemset

If $|L| = k$, there are $2^k - 2$ candidate rules - every subset except the empty set and L itself. For {A,B,C,D} that is $2^4 - 2 = \mathbf{14}$.

The confidence anti-monotone property

⚠GotchaConfidence is not anti-monotone in general

c(ABC→D) can be larger or smaller than c(AB→D) - these come from different itemsets, so nothing constrains them. The useful property only holds within a single frequent itemset.

For rules generated from the same itemset, confidence is anti-monotone with respect to the number of items on the right-hand side:

$$c(ABC \rightarrow D) \;\geq\; c(AB \rightarrow CD) \;\geq\; c(A \rightarrow BCD)$$

All 14 rules from one frequent itemset. Confidence only falls as you move down, so one failing rule condemns everything beneath it.

◎Exam cueThe pruning rule

If a rule is below min confidence, all rules with more items on the RHS - its descendants in the lattice above - are also below it, so prune them without computing anything.

Worked example: full Apriori plus rule generation

Dataset, with min support = 60% (a count ≥ 3 out of 4) and min confidence = 80%:

Trans	Items
T1	{K, A, D, B}
T2	{D, A, C, E, B}
T3	{C, A, B, E}
T4	{B, A, D}

→StepsStep 1 - frequent itemsets

1. 1-itemsets: {A}:4, {B}:4, {C}:2 ✗, {D}:3, {E}:2 ✗, {K}:1 ✗. Frequent: {A}, {B}, {D}.
2. 2-itemsets: {A,B}:4, {B,D}:3, {A,D}:3. All three are frequent.
3. 3-itemsets: {A,B,D}:3. Frequent.

Step 2 - rule generation, keeping only confidence ≥ 80%:

Rule	Confidence	Keep?
A→B	4/4 = 100%	Yes
B→A	4/4 = 100%	Yes
A→D	3/4 = 75%	No
D→A	3/3 = 100%	Yes
B→D	3/4 = 75%	No
D→B	3/3 = 100%	Yes
AB→D	3/4 = 75%	No
D→AB	3/3 = 100%	Yes
AD→B	3/3 = 100%	Yes
B→AD	3/4 = 75%	No
BD→A	3/3 = 100%	Yes
A→BD	3/4 = 75%	No

#NumbersThe seven surviving rules

A→B, B→A, D→A, D→B, D→AB, AD→B, BD→A - 7 of the 12 rules tested clear the 80% bar, and every pruned rule scored exactly 75%. The pattern is arithmetic: a rule survives exactly when σ(LHS) equals the support of the whole itemset, which makes the confidence 100%. That happens either when D is on the left (denominator 3, matching σ({A,B,D}) = 3) or when the itemset is {A,B} and the left side is A or B (denominator 4, matching σ({A,B}) = 4).