Association Mining

Frequent Pattern Mining

Frequent patterns are patterns that appear frequently in a dataset.

Example: Customers frequently purchasing milk and bread together represent a frequent pattern.

Frequent pattern mining searches for recurring relationships or patterns in a given dataset.

Market Basket Analysis

An example of frequent itemset mining is Market Basket Analysis.

This process analyzes customer buying habits by finding associations between different items that customers place in their shopping baskets.

For example, if customers frequently purchase milk and bread together, a retailer can identify this association and use it to improve product placement and marketing strategies.

Applications

• Selective marketing: Businesses can target customers based on frequently purchased combinations of products.
• Product placement: Items that are frequently purchased together can be placed in clos

Association Rule Mining

Association rule mining is a two-step process:

1. Find all frequent itemsets Identify itemsets that satisfy the minimum support threshold.
2. Generate strong association rules Generate association rules from the frequent itemsets. The generated rules must satisfy both:
   • Minimum support
   • Minimum confidence

Support: It refers to the popularity of an item and can be calculated by finding the number of transactions containing a particular item ÷ total number of transactions.

$\text{Support}(B) = \frac{\text{Transactions containing } B}{\text{Total transactions}}$

Example: 1000 transactions, 100 transactions contain ketchup.

$\text{Support (ketchup)} = \frac{100}{1000} = 10\%$

Confidence: It refers to the likelihood that an item B is also bought if item A is bought.

$\text{Confidence}(A \rightarrow B) = \frac{\text{Transactions containing both } (A \text{ and } B)}{\text{Transactions containing } A}$

50 transactions → burger and ketchup were bought.

Then we can find the likelihood of buying ketchup when a burger is bought.

150 transactions → burgers are bought.

The association rule is:

$\text{Burger} \rightarrow \text{Ketchup}$

$\text{Confidence}(\text{Burger} \rightarrow \text{Ketchup}) = \frac{50}{150} = 33.33\%$

Apriori Algorithm

The Apriori algorithm works in 2 main steps:

1. Join Step →

This step generates (k + 1)-itemsets from k-itemsets by joining frequent k-itemsets with each other.

For example, two frequent 2-itemsets can be joined to generate a candidate 3-itemset.

2. Prune Step →

In this step, the candidate itemsets are checked against the minimum support threshold.

If a candidate itemset does not satisfy the minimum support, it is removed (pruned).

The remaining itemsets are called frequent itemsets and are used to generate the next set of candidate itemsets.

Solved Problem

Transaction List

TID	Items Purchased
1	Milk, Egg, Bread, Butter
2	Milk, Butter, Egg, Ketchup
3	Bread, Butter, Ketchup
4	Milk, Bread, Butter
5	Bread, Butter, Cookies
6	Milk, Bread, Butter, Cookies
7	Milk, Cookies
8	Milk, Bread, Butter
9	Bread, Butter, Egg, Cookies
10	Milk, Butter, Bread
11	Milk, Bread, Butter
12	Milk, Bread, Cookies, Ketchup

---

Support level = 30%

Confidence = 60%

Solution:

---

1-itemsets

There are 12 transactions in the database.

For a support level of 30%:

$0.30 \times 12 = 3.6$

Since the support count must be a whole number, the minimum support count is 4.

Therefore, only items occurring 4 or more times are considered frequent.

1-itemsets	Freq	Support
Milk	9	9/12
Bread	10	10/12
Butter	10	10/12
Egg	3	3/12
Ketchup	3	3/12
Cookies	5	5/12

---

Frequent 1-itemsets

After applying the minimum support count of 4, the frequent 1-itemsets are:

Frequent 1-itemsets	Freq
Milk	9
Bread	10
Butter	10
Cookies	5

List is $\{\text{Milk, Bread, Butter, Cookies}\}$

2-itemsets

2-itemsets	Freq	Supp
Milk, Bread	7	7/12
Milk, Butter	7	7/12
Milk, Cookies	3	3/12 = 25%
Bread, Butter	9	9/12
Bread, Cookies	4	4/12
Butter, Cookies	3	3/12 = 25%

---

Frequent 2-itemsets

Frequent 2-itemsets	Freq	Supp
Milk, Bread	7	7/12 = 0.58 = 58%
Milk, Butter	7	7/12 = 0.58 = 58%
Bread, Butter	9	9/12 = 0.75 = 75%
Butter, Cookies	4	4/12 = 0.33 = 33%

---

List is $\{\text{Milk, Bread, Butter, Cookies}\}$

Frequent 3-itemsets

3-itemsets	Freq
Milk, Bread, Butter	6
Milk, Bread, Cookies	1
Bread, Butter, Cookies	3
Milk, Butter, Cookies	2

---

Frequent 3-itemsets

After applying the minimum support count of 4, only one 3-itemset is frequent:

Frequent 3-itemsets	Freq
Milk, Bread, Butter	6

Therefore:

$\text{Frequent 3-itemset} = I = \{\text{Milk, Bread, Butter}\}$

---

Non-empty Subsets

The non-empty subsets of I are:

$\{\text{Milk}\},\ \{\text{Bread}\},\ \{\text{Butter}\}$ , $\{\text{Milk, Bread}\},\ \{\text{Milk, Butter}\},\ \{\text{Bread, Butter}\}$

These subsets can be used to generate the association rules.

---

How to Form Association Rules?

For every non-empty subset S of I, an association rule can be generated as:

$S \rightarrow \{I-S\}$

$\text{If } \frac{\text{Support}(I)}{\text{Support}(S)} \geq \text{min\_confidence}$

Minimum Support = 30%, Minimum Confidence = 60%

---

Rule 1:
$\{\text{milk}\} \rightarrow \{\text{milk, bread, butter}\} – \{\text{milk}\}$

Therefore,

$\{\text{milk}\} \rightarrow \{\text{bread, butter}\}$

• Support(I) = 6/12 = 50%
• Support(milk) = 9/12

$\text{Confidence} = \frac{\text{Support}(\text{milk, bread, butter})}{\text{Support}(\text{milk})}$

$= \frac{6/12}{9/12}$

$= \frac{6}{12} \times \frac{12}{9} = 66.67\%$

$66.67\% > 60\%$

→ Valid

---

Rule 2:
$\{\text{bread}\} \rightarrow \{\text{milk, bread, butter}\} – \{\text{bread}\}$

Therefore,

$\{\text{bread}\} \rightarrow \{\text{milk, butter}\}$

$\text{Confidence} = \frac{\text{Support}(\text{milk, bread, butter})}{\text{Support}(\text{bread})}$

$= \frac{6}{10} = 60\%$

$60\% \geq 60\%$

→ Valid

---

Rule 3:
$\{\text{butter}\} \rightarrow \{\text{milk, bread, butter}\} – \{\text{butter}\}$

Therefore,

$\{\text{butter}\} \rightarrow \{\text{milk, bread}\}$

$\text{Confidence} = \frac{\text{Support}(\text{milk, bread, butter})}{\text{Support}(\text{butter})}$

$= \frac{6}{10} = 60\%$

$60\% \geq 60\%$

→ Valid

---

Rule 4:
$\{\text{milk, bread}\} \rightarrow \{\text{milk, bread, butter}\} – \{\text{milk, bread}\}$

Therefore,

$\{\text{milk, bread}\} \rightarrow \{\text{butter}\}$

$\text{Confidence} = \frac{\text{Support}(\text{milk, bread, butter})}{\text{Support}(\text{milk, bread})}$

$= \frac{6}{7} = 85.7\%$

$85.7\% > 60\%$

→ Valid

Rule 5:

$\{\text{milk, butter}\} \rightarrow \{\text{milk, bread, butter}\} – \{\text{milk, butter}\}$

Therefore,

$\{\text{milk, butter}\} \rightarrow \{\text{bread}\}$

$\text{Confidence} = \frac{\text{Support}(\{\text{milk, bread, butter}\})}{\text{Support}(\text{milk, butter})}$

$= \frac{6}{7} = 85.7\%$

$85.7\% \geq 60\%$

→ Valid

---

Rule 6:

$\{\text{bread, butter}\} \rightarrow \{\text{milk, bread, butter}\} – \{\text{bread, butter}\}$

Therefore,

$\{\text{bread, butter}\} \rightarrow \{\text{milk}\}$

$\text{Confidence} = \frac{\text{Support}(\{\text{milk, bread, butter}\})}{\text{Support}(\text{bread, butter})}$

$= \frac{6}{9} = 66.67\%$

$66.67\% \geq 60\%$

→ Valid

Valid Association Rules

Rule	Confidence	Result
Milk → Bread, Butter	66.67%	Valid
Bread → Milk, Butter	60%	Valid
Butter → Milk, Bread	60%	Valid
Milk, Bread → Butter	85.7%	Valid
Milk, Butter → Bread	85.7%	Valid
Bread, Butter → Milk	66.67%	Valid

Therefore, all 6 possible association rules are valid for the given frequent 3-itemset when the minimum confidence is 60%.

Final Set of Valid Rules

$\text{Milk} \rightarrow \{\text{Bread, Butter}\}$

$\text{Bread} \rightarrow \{\text{Milk, Butter}\}$

$\text{Butter} \rightarrow \{\text{Milk, Bread}\}$

$\{\text{Milk, Bread}\} \rightarrow \text{Butter}$

$\{\text{Milk, Butter}\} \rightarrow \text{Bread}$

$\{\text{Bread, Butter}\} \rightarrow \text{Milk}$