Q7(b) - Frequent Itemsets and Association Rules by the Apriori Algorithm

Given: 5 transactions, minimum support = 30%, minimum confidence = 80%.

$$minsup\ count = 30\% \ \text{of} \ 5 = 0.30 \times 5 = 1.5 \ \Rightarrow \ an\ itemset\ must\ occur\ in\ \ge 2\ transactions$$

Abbreviations: Bread = B, Butter = Bu, Milk = M, Coke = C, Jelly = J.

TID	Items
T1	Bread, Jelly, Butter
T2	Bread, Butter
T3	Bread, Milk, Butter
T4	Coke, Bread
T5	Coke, Milk

Step 1 - Scan 1: 1-itemsets

Itemset	Transactions	Count	Support	Frequent?
{Bread}	T1, T2, T3, T4	4	4/5 = 80%	Yes
{Butter}	T1, T2, T3	3	3/5 = 60%	Yes
{Milk}	T3, T5	2	2/5 = 40%	Yes
{Coke}	T4, T5	2	2/5 = 40%	Yes
{Jelly}	T1	1	1/5 = 20%	No (< 30%)

$$L_1 = \{\{Bread\}:4,\ \{Butter\}:3,\ \{Milk\}:2,\ \{Coke\}:2\}$$

Jelly is dropped, so no itemset containing Jelly can ever be frequent (Apriori property / downward closure).

Step 2 - Scan 2: candidate 2-itemsets from $L_1$

Candidate	Transactions	Count	Support	Frequent?
{Bread, Butter}	T1, T2, T3	3	3/5 = 60%	Yes
{Bread, Milk}	T3, T4	2	2/5 = 40%	Yes
{Bread, Coke}	T4	1	1/5 = 20%	No
{Butter, Milk}	T3	1	1/5 = 20%	No
{Butter, Coke}	-	0	0%	No
{Milk, Coke}	T5	1	1/5 = 20%	No

$$L_2 = \{\{Bread, Butter\}:3,\ \{Bread, Milk\}:2\}$$

Step 3 - Scan 3: 3-itemsets

The only join candidate is {Bread, Butter, Milk}. Its subset {Butter, Milk} is not in $L_2$, so by the Apriori property the candidate is pruned and no scan is required.

$$L_3 = \varnothing \quad \Rightarrow \quad \textbf{stop}$$

All frequent itemsets

Level	Frequent itemset	Support count	Support %
1	{Bread}	4	80%
1	{Butter}	3	60%
1	{Milk}	2	40%
1	{Coke}	2	40%
2	{Bread, Butter}	3	60%
2	{Bread, Milk}	2	40%

Step 4 - Association rules (minimum confidence 80%)

$$confidence(X \Rightarrow Y) = \frac{support(X \cup Y)}{support(X)}$$

Rules are generated only from itemsets with two or more items:

Rule	Confidence calculation	Confidence	Passes 80%?
Bread $\Rightarrow$ Butter	3/4	75%	No
Butter $\Rightarrow$ Bread	3/3	100%	Yes
Bread $\Rightarrow$ Milk	2/4	50%	No
Milk $\Rightarrow$ Bread	2/2	100%	Yes

Result

Frequent itemsets: {Bread} 80%, {Butter} 60%, {Milk} 40%, {Coke} 40%, {Bread, Butter} 60%, {Bread, Milk} 40%.

Strong (valid) association rules with support $\ge$ 30% and confidence $\ge$ 80%:

1. $\{Butter\} \Rightarrow \{Bread\}$ - support 60%, confidence 100%
2. $\{Milk\} \Rightarrow \{Bread\}$ - support 40%, confidence 100%

The other two candidate rules fail the 80% confidence test (75% and 50%), so they are rejected.