DATA WAREHOUSING & DATA MINING

UNIT-4
Association Analysis: Problem Definition, Frequent Item set Generation, Rule
Generation: Confident Based Pruning, Rule Generation in Apriori Algorithm,
Compact Representation of frequent item sets, FPGrowth Algorithm.

INTRODUCTION

 Association Analysis is a data mining technique used to discover

interesting relationships, patterns, or correlations between items in large
datasets.
 The main aim of association analysis is to find useful patterns or groups
of items that often appear together in the data, and represent them as
association rules.
 It is widely used in market basket analysis to identify items that
frequently occur together in transactions.
 The goal is to discover interesting associations or rules that describe how
items are related.

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 1

 Key Concepts

1. Item
 A single product, object, or thing in a dataset or transaction.

Example: Milk, Bread, or Butter are items.

2. Itemset
 An itemset is a collection of one or more items that occur together in a
transaction or dataset.
 If it contains only one item, it is called a 1-itemset.
 If it contains k items, it is called a k-itemset.

For example, in a supermarket, an itemset might be {bread, butter, milk}.

3. Support
 Support is a measure that shows how often an itemset appears in a
dataset (or the proportion of transactions that contain the itemset).
 It is used to identify whether an itemset is frequent or not.

Example
Suppose there are 100 transactions in a store the itemset {milk, bread}
appears in 20 transactions.

∴ Support = 20 ÷ 100 = 0.20 (or 20%).

Meaning: In 20% of all transactions, customers bought both milk and bread
together.

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 2

4. Confidence
 Confidence indicates the likelihood that an item B is purchased when
item A is purchased.
 It’s the proportion of transactions containing item A that also contain
item B.

Formula

Example
Suppose there are 40 transactions that contain milk out of these, 24
transactions also contain bread.

∴ Confidence = 24 ÷ 40 = 0.60 (or 60%).

Meaning: If a customer buys milk, there is a 60% chance they will also buy
bread.

5. Lift
 Lift Measures how much more likely item B is to be purchased when item
A is purchased, compared to the likelihood of item B being purchased
without item A.
Formula

Example:
1. 30% of all customers buy coffee → Support(Coffee) = 0.30
2. 20% of all customers buy sugar → Support(Sugar) = 0.20
3. 15% of all customers buy both coffee and sugar → Support(Coffee ∪ Sugar)
= 0.15

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 3

 ∴ Lift =2.5

Meaning: People who buy coffee are 2.5 times more likely to also buy sugar
than customers in general.

Example Scenario

Let's consider Market Basket Analysis for a small grocery store, you want to
analyze the purchasing behavior of customers to optimize the store layout and
increase sales of complementary products.

Transaction Dataset:

Here’s a sample of your transaction data:

Transaction ID Items Purchased

1 Milk, Cookies, Fruit
2 Milk, Fruit, Cereal
3 Bread, Cheese, Fruit
4 Milk, Bread, Butter, Cereal
5 Fruit, Cereal, Cookies, Bread, Milk

Step 1: Identify Frequent Itemsets

 Set a minimum support threshold (specific limit or point) of 60%,

meaning the itemset must appear in at least 60% of the transactions to be
considered frequent.

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 4

Threshold value

 A threshold value in data mining is the minimum or maximum limit

used to filter or select data results.
 In Data mining the default support threshold value is 50% to 60%.
Let us assume no. of transactions =5
1) If Support threshold value is set 60% then
60
100
∗ 𝑁𝑜. 𝑜𝑓 𝑇𝑟𝑎𝑛𝑎𝑠𝑎𝑐𝑡𝑖𝑜𝑛𝑠 ∗ 5 = 3
-> 60
100
 This means out of 5 transactions the item or item set must and should
appear 3 transactions.

2) If Support threshold value is set 50% then

50
100
∗ 𝑁𝑜. 𝑜𝑓 𝑇𝑟𝑎𝑛𝑎𝑠𝑎𝑐𝑡𝑖𝑜𝑛𝑠 ∗ 5 = 2(𝑜𝑟)3
-> 50
100
 This means out of 5 transactions the item or item set must and should
appear 2 to 3 transactions.

1. Single Items:

 Milk: Appears in 4 out of 5 transactions (80%) ✔

 Cookies: Appears in 2 out of 5 transactions (40%) – Not frequent

 Fruit: Appears in 4 out of 5 transactions (80%) ✔
 Bread: Appears in 3 out of 5 transactions (60%) ✔
 Cheese: Appears in 1 out of 5 transactions (20%) – Not frequent
 Butter: Appears in 1 out of 5 transactions (20%) – Not frequent
 Cereal: Appears in 3 out of 5 transactions (60%) ✔
2. Frequent Itemsets
 {Milk, Fruit}: Appears in 3 out of 5 transactions (60%) ✔
 {Milk, Cereal}: Appears in 3 out of 5 transactions (60%) ✔
 {Milk, Bread}: Appears in 2 out of 5 transactions (40%) – Not frequent
 {Fruit, Cereal}: Appears in 2 out of 5 transactions (40%) – Not frequent
Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 5
  {Bread, Cereal}: Appears in 2 out of 5 transactions (40%) – Not frequent

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 6

 Step 2: Generate Association Rules

Now, generate association rules based on the frequent itemsets:

1. Support

 Support measures how frequently the itemset {Milk,Fruit} appears in the

dataset.

Formula:

Counting Transactions with Both Milk and Fruit:

 Transaction 1: Milk, Cookies, Fruit

 Transaction 2: Milk, Fruit, Cereal
 Transaction 5: Milk, Fruit, Cereal, Cookies, Bread

Number of transactions containing both Milk and Fruit: 3

2. Confidence

 Confidence measures the likelihood that Fruit is purchased when Milk is

purchased.

Formula:

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 7

Support of Milk:

Counting Transactions with Milk:

 Transaction 1: Milk, Cookies, Fruit

 Transaction 2: Milk, Fruit, Cereal
 Transaction 4: Milk, Bread, Butter, Cereal
 Transaction 5: Milk, Fruit, Cereal, Cookies, Bread

Number of transactions containing Milk: 4

3. Lift
 Lift measures how much more likely Fruit is to be purchased when Milk
is purchased, compared to the likelihood of purchasing Fruit by itself.

Support of Fruit:

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 8

Counting Transactions with Fruit:

 Transaction 1: Milk, Cookies, Fruit

 Transaction 2: Milk, Fruit, Cereal
 Transaction 3: Bread, Cheese, Fruit
 Transaction 5: Milk, Fruit, Cereal, Cookies, Bread

Number of transactions containing Fruit: 4

Note: Continue same process to find support, confidence and lift for another
one {Milk, Cereal}

Frequent Item set Generation (Association Rule Mining)

 Frequent itemsets are groups of items that often appear together in a
dataset.
 Frequent itemsets are an important concept in association rule mining,
which is used in data mining to find relationships between items in a
dataset.
 The goal of Frequent Item set Generation to find patterns, like which
products are usually bought together.
 Association rule mining is a data mining technique used to find such
item relationships.

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 9

  The frequency of an item set is measured by the support count, which is
the number of transactions or records in the dataset that contain the item
set.
 This technique helps companies understand customer behavior and
improve sales strategies.

Example: If customers often buy bread and butter together, {bread, butter} is
a frequent itemset.

Steps to Find Frequent Itemsets

Let us consider in a retail store scenario
Transaction ID Items
1 Milk, Eggs, Bread
2 Milk, Diapers, Bread
3 Milk, Eggs
4 Bread, Butter
5 Milk,bread,butter

Step 1: Set Minimum Support

Total transactions N = 5.
Minimum support = 60% ⇒ minimum support count = 0.6 × 5 = 3
transactions (so an itemset must appear in at least 3 transactions).

Step 2: Frequent 1-itemsets (count each item)

 Milk: T1, T2, T3, T5 → 4/5 = 0.8 → 80% ✔
 Bread: T1, T2, T4, T5 → 4/5 = 0.8 → 80% ✔
 Eggs: T1, T3 → 2/5 = 0.4 → 40% ✖
 Butter: T4, T5 → 2/5 = 0.4 → 40% ✖
 Diapers: T2 → 1/5 = 0.2 → 20% ✖

∴ Frequent 1-itemsets (≥60%): {Milk}, {Bread}

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 10

Step 3: Candidate 2-itemsets (combine frequent 1-itemsets)

Possible pair from frequent singles: {Milk, Bread}

{Milk, Bread}: appears in T1, T2, T5 → 3/5 = 0.6 → 60% ✔
∴ Frequent 2-itemsets: {Milk, Bread}

Step 4: Candidate 3-itemsets

 No candidate 3-itemset can be formed from only one frequent 2-itemset
(need at least two frequent 2-itemsets to join).

(For completeness: {Milk, Bread, Butter} appears only in T5 → 1/5 = 20%) ✖

Step 5: Final frequent itemsets (support ≥ 60%)

 1-itemsets: {Milk} (4/5 = 80%), {Bread} (4/5 = 80%)
 2-itemset: {Milk, Bread} (3/5 = 60%)

Lattice Structure frequent itemsets:

 A lattice structure organizes all possible itemsets level by lev el,

starting from the null set (∅) at the top, followed by 1-itemsets, 2-
itemsets, and so on, until the full itemset is reached.
 Frequent 1-itemsets: {a}, {b}, {c}, {e}
 Frequent 2-itemsets: {a, b}, {a, c}, {b, c}, {b, e}, {c, e}
 Frequent 3-itemsets: {a, b, c}, {b, c, e}

 In frequent itemset mining, it helps to see possible item groups and

remove unnecessary ones quickly.

Steps to draw Lattice Diagram:

Step 1: Start at the Top

 Draw the null set (∅) at the top.

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 11

Step 2: Draw Level 1 (1-itemsets):
 Below ∅, draw all single items: {a}, {b}, {c}, {e}.
 Connect ∅ to each of them.

Step 3: Draw Level 2 (2-itemsets)

 Each of these connects to the relevant 2-itemsets formed from
combinations of those items.
For example:
 {a} connects to {a, b}, {a, c}
 {b} connects to {a, b}, {b, c}, {b, e}
 {c} connects to {a, c}, {b, c}, {c, e}
 {e} connects to {b, e}, {c, e}

Step 4: Draw Level 3 (3-itemsets)

 Below the 2-itemsets, draw the 3-item combinations:
{a,b,c}, {b,c,e}.
Step 5: Check the Connections:
 Make sure each node is connected to subsets above it.
Example: {a,b,c} connects back to {a,b} and {a,c}.

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 12

Applications of Frequent Itemsets

1. Market Basket Analysis: Finds which items are often bought together (like
milk + bread).
2. Recommendation Systems: Suggests new products based on what people
usually buy together (like Amazon or Netflix).
3. Healthcare: Finds relation between symptoms and diseases (like fever +
cough → flu).
4. Fraud Detection: Detecting unusual or suspicious patterns in financial
transactions.
5. Web Usage Mining: Understands which websites/pages students or users
visit together to improve browsing experience.

Rule Generation: Confident Based Pruning

 Confident-based pruning is a technique used in association rule
generation to eliminate weak or less useful rules.
 The goal is keep only rules with high confidence, meaning they are
correct or reliable most of the time.
 In association rule mining, a rule shows a relationship between items:
The antecedent (IF part) implies the consequent (THEN part).

Key Concepts:

1. Confidence
 Confidence is the measure that shows how often items in Y appear in
transactions that already contain items in X.

 In association rule mining, the antecedent refers to the item or group of

items that appear on the left side of the rule.
 It represents the condition or "if" part of the rule.

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 13

  In association rule mining, the consequent refers to the item or group of
items that appear on the right side of the rule.
 It represents the "then" part of the rule, meaning the items that are likely
to be found in a transaction if the antecedent (the "if" part) occurs.

2. Pruning Based on Confidence:

 Pruning means removing the rules that don’t meet a minimum

confidence threshold value.
 For example, if the minimum confidence threshold is set at 60%, and a
rule has a confidence of 50%, it would be pruned (discarded).
 This helps in filtering out weak rules, leaving only the more reliable,
confident rules.

Steps for Confident-based Pruning:

Step 1: Generate Rules: Generate rules from the frequent itemsets.

Step 2: Calculate Confidence: For each rule, calculate the confidence using
the formula above.

Step 3: Set a Confidence Threshold: Set a minimum confidence threshold

(e.g. 60%).
Step 4: Prune Rules:

 If confidence ≥ threshold → ✔keep the rule.

 If confidence < threshold → ✖prune (remove) the rule.

Step 5: Keep only strong and reliable rules for final results.

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 14

Example Dataset (Transactions):

Imagine a small retail store has the following transactions:

Transaction ID Items Purchased

1 {Milk, Bread, Butter}
2 {Milk, Bread}
3 {Milk, Butter}
4 {Bread, Butter}
5 {Milk, Bread, Butter}

Step 1: Set threshold value

Total no. of Transactions = 5 transactions.

1. Minimum Support = 60% → Only itemsets appearing in at least 60% of

transactions are considered frequent.
2. Minimum Confidence = 70% → Only rules with confidence of 70% or
more are kept.

Step 2: Generate Association Rules (from frequent itemsets)

Let's assume we’ve already identified the frequent itemsets from the dataset.
Now, we create some basic association rules based on these itemsets.

Some possible rules from this dataset:

 Rule 1: {Bread} → {Butter}
 Rule 2: {Milk} → {Bread}
 Rule 3: {Butter} → {Milk}
 Rule 4: {Bread, Butter} → {Milk}

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 15

Step 3: Calculate Confidence for Each Rule
To calculate the confidence of a rule, we use the formula:

Rule 1: If {Bread} → {Butter}

1. Support of {Bread and Butter}: {Bread, Butter} occurs in Transactions T1,

T4, T5 (3 times).
2. Support of {Bread}: {Bread} appears in Transactions T1, T2, T4, T5(4 times)

∴ Confidence = 3 / 4 = 0.75 → 75%

Rule 2: If {Milk} → {Bread}

1. Support of {Milk and Bread}: {Milk, Bread} occurs in Transactions T1, T2,
T5 (3 times).
2. Support of {Milk}: {Milk} appears in Transactions T1, T2, T3, T5 (4 times).

∴ Confidence = 3 / 4 = 0.75 → 75%

Rule 3: If {Butter} → {Milk}

1. Support of {Milk, Butter}: {Milk, Butter} occurs in Transactions T1, T3, T5

(3 times).
2. Support of {Butter}: {Butter} appears in Transactions T1, T3, T4, T5 (4
times)

∴ Confidence = 3 / 4 = 0.75 → 75%

Rule 4: If {Bread, Butter} → {Milk}

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 16

1. Support of {Bread, Butter and Milk}: {Bread, Butter, Milk} occurs in
Transaction T1, T5 (2 times).
2. Support of {Bread, Butter}: {Bread, Butter} appears (3 times).

∴ Confidence = 2 / 3 =0.6667 → 66.7% → Prune (66.7% < 70%)

Step 4: Prune Rules Based on Confidence (Min Confidence = 70%)

1. Rule 1: {Bread} → {Butter} =75% → Keep ✔

2. Rule 2: {Milk} → {Bread} =75% → Keep ✔
3. Rule 3: {Butter} → {Milk}= 75% → Keep ✔
4. Rule 4: {Bread, Butter} → {Milk}=66.7% → Removed because confidence
< 70% ✖

Rule Generation in Apriori Algorithm

 The Apriori Algorithm was introduced by Rakesh Agrawal and
Ramakrishnan Srikant in 1994.
 The Apriori algorithm is a popular data mining technique used to
discover frequent itemsets and generate association rules from large
transactional datasets using measures like support and confidence.
 It works on the principle that “if an itemset is frequent, all its subsets
must also be frequent.”
 The main goal of the Apriori Algorithm is to discover frequent patterns or
itemsets in transaction data and to generate strong association rules
that show relationships between items.
 This algorithm uses a breadth-first search and Hash Tree to calculate the
itemset associations efficiently.
 The process is iterative (level-wise) From k-frequent itemsets, it
generates k+1 frequent itemsets.

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 17

 It scans the dataset multiple times, first identifying single items with high
support, then combining them to form larger frequent itemsets until no
more can be found.

Apriori Algorithm

Key steps involved in implementing the Apriori algorithm in data mining

1. Define minimum support threshold

 Decide the minimum number (or percentage) of times an itemset must

appear to be considered frequent.
 This value is set by the user based on the dataset size and prior
knowledge.

2. Generate a list of frequent 1-item sets

 In this step scan the entire dataset to identify the itemset that meet the
minimum support threshold.
 These item sets are known as frequent 1-item sets.
Example: frequent 1-itemsets: {Milk}, {Bread}, {Eggs}

3. Generate candidate item sets

 In this step, the algorithm generates frequent k-itemsets to generate
possible (k+1)-itemsets.

Example: Suppose from the previous step you found these frequent 1-
itemsets: {Milk}, {Bread}, {Eggs}
Now you combine them to create candidate 2-itemsets:
{Milk, Bread} {Milk, Eggs} {Bread, Eggs}

4. Count the support of each candidate item set

 Scan the dataset again and count how many transactions contain each
candidate itemset.

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 18

 5. Prune the candidate item sets
 Remove the item sets that do not meet the minimum support threshold.
 This step reduces unnecessary combinations.
6. Repeat steps 3-5 until no more frequent item sets can be generated.

7. Generate association rules

 Once the frequent item sets have been identified, the algorithm generates
association rules from them.
 Association rules are rules of form A -> B, where A and B are item sets.

Example: If {Milk, Bread} is frequent → Rules: Milk → Bread, Bread → Milk.

8. Evaluate the association rules

 Finally, the association rules are evaluated based on metrics such as
confidence and lift.

Flowchart

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 19

 Minsup- Minimum support threshold value
Minconf- Minimum confidence threshold value

Components of Apriori algorithm

The given three components comprise the apriori algorithm.

1. Support
2. Confidence
3. Lift

1. Support
 Support tells how often an item (or) itemset appears in the dataset.

2. Confidence
 Confidence is a measure the likelihood that item B appears in a
transaction given that item A appears.
3. Lift

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 20

  Lift measures how much stronger the association between A and B is
compared to random chance.

Interpretation:
 Lift > 1 → Positive relation (X and Y occur together more than expected).
 Lift = 1 → Independent.
 Lift < 1 → Negative relation.

Example: If Lift = 1.5 → buying Milk makes Bread 1.5 times more likely.

Applications:
1. Market Basket Analysis: To find items often bought together (e.g., Milk →
Bread).
2. Healthcare: To discover drug interactions or symptoms related to diseases.
3. Fraud Detection: Detects unusual patterns in transactions that may
indicate fraudulent activity.
4. Medical Diagnosis: Identifies associations between symptoms and
diseases in patient data.

Example for Apriori Algorithm

Consider a simple transaction dataset:

TID Items
T1 {milk, bread}
T2 {bread, sugar}
T3 {bread, butter}
T4 {milk, bread, sugar}
T5 {milk, bread, butter}
T6 {milk, bread, butter}
T7 {milk, sugar}
T8 {milk, sugar}

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 21

 T9 {sugar, butter}
T10 {milk, sugar, butter}
T11 {milk, bread, butter}

Step 1: Frequent Itemsets Generation (Using Support Threshold)

Support Threshold: 3 (This means an item or itemset must appear in at

least 3 out of 11 transactions to be considered frequent.)

Step 1A: Identify 1-Frequent Itemsets

We begin by counting how many times each item appears in the dataset:

Item Support (Count)

Milk 8
Bread 7
Sugar 5
Butter 6

Since all items appear in at least 3 transactions, they are considered frequent
1-itemsets.

Step 2: Generate 2-Frequent Itemsets

Next, we generate pairs of items (2-itemsets) and count their support:

Itemset Support (Count)

{Milk, Bread} 5
{Milk, Sugar} 4
{Milk, Butter} 4
{Bread, Sugar} 2
{Bread, Butter} 4
{Sugar, Butter} 3

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 22

We prune the itemsets that do not meet the support threshold of 3:

Frequent 2-itemsets: {Milk, Bread}, {Milk, Sugar}, {Milk, Butter}, {Bread,

Butter}

Step 1C: Generate 3-Frequent Itemsets

We combine the frequent 2-itemsets to form 3-itemsets and count their

support:

Itemset Support (Count)

{Milk, Bread, Butter} 3
{Milk, Bread, Sugar} 2
{Milk, Sugar, Butter} 2

Only {Milk, Bread, Butter} meets the minimum support threshold of 3, so it is

the only frequent 3-itemset.

Step 2: Generate Association Rules

 Once we have the frequent itemsets, we can generate association rules.

 The rules are generated based on the frequent itemsets, and we compute
the confidence for each rule.

Rules from {Milk, Bread, Butter}:

Rule 1: {Milk, Bread} → {Butter}

Support({Milk, Bread, Butter}) = 3

Support({Milk, Bread}) = 5

∴ Confidence = 3 / 5 = 0.6

Rule 2: {Milk, Butter} → {Bread}

Support({Milk, Bread, Butter}) = 3

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 23

 Support({Milk, Butter}) = 3

∴ Confidence = 3 / 4 = 0.75

Rule 3: {Bread, Butter} → {Milk}

Support({Milk, Bread, Butter}) = 3

Support({Bread, Butter}) = 3

∴ Confidence = 3 / 4 = 0.75

Rule 4: {Milk} → {Bread, Butter}

Support({Milk, Bread, Butter}) = 3

Support({Milk}) = 8

∴ Confidence = 3 / 8 = 0.375

Interpretation

1. Confidence = 0.60 for {Milk, Bread} → {Butter}:

There is a 60% chance that customers who buy both Milk and Bread will
also buy Butter.
2. Confidence = 0.75 for {Milk, Butter} → {Bread}:
There is a 75% chance that customers who buy both Milk and Butter will
also buy Bread.
3. Confidence = 0.75 for {Bread, Butter} → {Milk}:
There is a 75% chance that customers who buy both Bread and Butter will
also buy Milk.
4. Confidence = 0.375 for {Milk} → {Bread, Butter}:
Only 37.5% of transactions with Milk also contain both Bread and Butter,
so the rule is relatively weak.

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 24

Example: 2

Example Dataset

Consider the following transactions (T1 to T8):

Transaction Items Purchased

T1 {Milk, Eggs, Bread}
T2 {Milk, Eggs}
T3 {Eggs, Bread}
T4 {Milk, Bread, Butter}
T5 {Eggs, Butter}
T6 {Milk, Eggs, Bread, Butter}
T7 {Bread, Butter}
T8 {Milk, Bread}

Let’s assume the minimum support threshold is 3 transactions (as before).

Step 1: Generate 1-Frequent Itemsets

We first count the support (frequency) of each individual item across all the
transactions:

Item Support (Count)

Milk 5
Eggs 4
Bread 6
Butter 4

Since all items appear in 3 or more transactions, all these items are frequent
1-itemsets.

Step 2: Generate 2-Frequent Itemsets

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 25

Now, we combine the frequent 1-itemsets to form 2-itemsets and count their
support.

Itemset Support (Count)

{Milk, Eggs} 3
{Milk, Bread} 4
{Milk, Butter} 2
{Eggs, Bread} 2
{Eggs, Butter} 2
{Bread, Butter} 4

Only the itemsets that have a support of at least 3 are considered frequent. In
this case, the frequent 2-itemsets are:

 Frequent 2-itemsets: {Milk, Eggs}, {Milk, Bread}, {Bread, Butter}

Step 3: Generate 3-Frequent Itemsets

 We now combine the frequent 2-itemsets to form 3-itemsets:

Itemset Support (Count)

{Milk, Bread, Butter} 2

{Milk, Eggs, Bread} 2

Neither of these itemsets meet the support threshold of 3, so no 3-itemsets are

frequent.

Step 4: Generate Association Rules

Since the largest frequent itemsets are 2-itemsets, we will generate association
rules from these.

Frequent 2-Itemset: {Milk, Bread}

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 26

Rule 1: {Milk} → {Bread}

Support({Milk, Bread}) = 4

Support({Milk}) = 5

∴ Confidence = 4 / 5 = 0.80 (or 80%)

Rule 2: {Bread} → {Milk}

Support({Milk, Bread}) = 4

Support({Bread}) = 6

∴ Confidence = 4 / 6 = 0.67 (or 67%)

Rule 3: {Milk} → {Eggs}

Support({Milk, Eggs}) = 3

Support({Milk}) = 5

∴ Confidence = 3 / 5 = 0.60 (or 60%)

Rule 4: {Eggs} → {Milk}

Support({Milk, Eggs}) = 3

Support({Eggs}) = 4

∴ Confidence = 3 / 4 = 0.75 (or 75%)

Rule 5: {Bread} → {Butter}

Support({Bread, Butter}) = 4

Support({Bread}) = 6

∴ Confidence = 4 / 6 = 0.67 (or 67%)

Rule 6: {Butter} → {Bread}

Support({Bread, Butter}) = 4

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 27

 Support({Butter}) = 4

∴ Confidence = 4 / 4 = 1.0 (or 100%)

Final Results

The strongest rules from this example (based on confidence) are:

{Butter} → {Bread} with 100% confidence.

{Milk} → {Bread} with 80% confidence.

{Eggs} → {Milk} with 75% confidence.

Advantages of Apriori Algorithm:

Advantages of Apriori Algorithm:
1. Simplicity: Conceptually simple, easy to understand and
2. Effective for Small Datasets: Performs well when the dataset is small or
moderately sized.
3. Systematic Support Counting: Uses support-based pruning to eliminate
non-frequent itemsets early, making the process systematic.

Disadvantages of Apriori Algorithm:

1. High Computational Complexity: Generates many candidate itemsets,
which can be time-consuming.
2. Memory Intensive: Requires significant memory to store candidate and
frequent itemsets.
3. Not Scalable for Large Datasets: Performance decreases on very large or
dense datasets due to multiple scans and large itemset generation.
4. Overhead of Multiple Scans: Needs several passes over the data,
increasing time complexity.

Compact Representation of frequent item sets

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 28

  The Compact Representation of frequent itemsets refers to techniques
used to summarize or reduce the number of frequent itemsets without
losing important information.
 This is important because mining from large datasets may generate too
many itemsets, many of which are redundant and add little value.
 Compact representations help in reducing redundancy, saving storage
space, improving computational efficiency, and simplifying rule
generation.

Key Techniques for Compact Representation:

1. Closed Frequent Itemsets

 A Closed Frequent Itemset is a group of items that is frequent and no
bigger group (superset) has the same frequency.
 A smaller itemset is called closed if its support count is different from
all of its bigger itemsets (supersets).

 It removes repeated information from smaller groups.

 It keeps all important details and makes data smaller and easier to
use.

Example:
Imagine a store’s transactions:

T1: {milk, bread, butter}

T2: {milk, bread}
T3: {milk, bread, butter}

 Support count of {milk, bread} = 3 times

 Support count of {milk, bread, butter} = 2 times

 Here, {milk, bread} is closed because its superset {milk, bread, butter} has a
different (lower) frequency.
 But if both had the same frequency, {milk, bread} would not be closed.

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 29

 2. Maximal Frequent Itemsets
 A Maximal Frequent Itemset is a frequent itemset that has no frequent
superset.
 It is the largest frequent group, so we ignore its smaller subsets when
listing maximal sets.
 Maximal itemsets show only the largest frequent groups and do not give
counts for smaller groups.

Example
Imagine a store’s transactions:
T1: {milk, bread, butter}
T2: {milk, bread}
T3: {milk, bread, butter}
Frequent sets:
 {milk, bread} = 3 times
 {milk, bread, butter} = 2 times

Maximal frequent itemset: {milk, bread, butter} ✔

 We don’t include {milk, bread} because it has a bigger frequent

superset.

3. Association Rules
 Association rules show how items are related in a dataset.
 They are written in the form: If X happens, then Y also happens (X →
Y).
 Association rules help to find patterns, like which items are often
bought together.

Two important measures for rules:

1. Support – how often the items appear together.
2. Confidence – how often the rule is true.

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 30

Example: “If a customer buys milk, they are likely to also buy bread.” Written
formally as: {Milk, Bread}⇒{Butter}ss

Example:

Consider a grocery store dataset with the following transactions

Transaction ID Items
T1 eggs, milk, cheese
T2 eggs, cheese
T3 milk, cheese
T4 eggs, milk
T5 eggs, milk, cheese

Rule: {eggs, cheese} → {milk}

1. Support
 The rule applies to transactions T1 and T5 (where eggs and cheese
appear together and milk is also present) out of 5 total transactions.

∴ Support = 2/5 = 0.4 or 40%.

2. Confidence
 {eggs, cheese} appears in T1, T2, and T5 (3 transactions total), Out of
these, {milk} also appears in T1 and T5 (2 transactions).

∴ Confidence = 2/3 = 0.67 or 67%.

3. Lift
Lift = actual support / expected support

Step-1: Calculate Expected support

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 31

Step 2: Find supports
 Total transactions = 5
 Support(X) = Support({eggs, cheese}) = 3/5 = 0.6
 Support(Y) = Support({milk}) = 4/5 = 0.8
 Support(X ∪ Y) = Support({eggs, cheese, milk}) = 2/5 = 0.4
Step 3: Calculate Lift

∴ Lift= ≈ 0.83

Step 4: Interpretation

 Lift > 1 → buying X increases the chance of buying Y (positive correlation)

 Lift = 1 → X and Y are independent
 Lift < 1 → buying X decreases the chance of buying Y (negative
correlation)
 Here, Lift ≈ 0.83 → buying {eggs, cheese} slightly decreases the chance of
buying {milk} compared to random.

4. FP-Tree (Frequent Pattern Tree)

 FP-Tree is a compact tree structure used to store frequent itemsets

from a dataset.
 It is used in the FP-Growth algorithm to find frequent patterns without
generating many candidate itemsets.

Key Concepts of FP-Tree:

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 32

1. Frequent Pattern Tree
 A Frequent Pattern Tree is tree structure where nodes represent
items, and paths represent itemsets (common prefixes of
transactions).
 Each node stores the item name and its frequency count (how many
transactions share that path).

2. Header Table
 A Header table that keeps track of frequent items and their counts.
 Each entry links to the first node of that item in the FP-tree.
 It helps in quickly finding and traversing all occurrences of a specific
item.

Steps to Construction of FP-Tree

1. Scan database → count frequency of items.
2. Filter out infrequent items (below minimum support).
3. Order items by frequency in each transaction.
4. Insert transactions into the tree, sharing common prefixes and updating
counts.

Example:

Consider a dataset of transactions with the following items:

Transaction ID Items
T1
Apple, Banana, Mango
T2 Apple, Banana
T3 Apple, Orange
T4 Banana, Mango
T5 Apple, Banana, Orange

Step 1: Count item frequencies (1-itemsets with Support ≥ 2)

 {Apple}: 4 (T1, T2, T3, T5) ✔

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 33

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 34
  {Banana}: 4 (T1, T2, T4, T5) ✔

 {Mango}: 2 (T1, T4) ✔

 {Orange}: 2 (T3, T5) ✔

Pairs
 {Apple, Banana} : 3 (T1, T2, T5) ✔
 {Banana, Mango} : 2 (T1, T4) ✔
 {Apple, Orange} : 2 (T3, T5) ✔

Triples

 {Apple, Banana, Mango} : 1 (T1) ✖

 {Apple, Banana, Orange} : 1 (T5) ✖

Step 2: Build FP-Tree:

1. Start with the root
The root is empty (null).
It’s just the starting point of the tree.

2. Insert T1 = Apple → Banana → Mango

Path created:
null → Apple(1) → Banana(1) → Mango(1)

3. Insert T2 = Apple → Banana

The path Apple → Banana already exists! So
we increase their counts:
Apple(2) → Banana(2) → Mango(1)

4. Insert T3 = Apple → Orange

After Apple(2), there’s no “Orange” branch yet, so
we add a new branch from Apple:
Apple(3) (count increases by 1)

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 35

 → new child Orange(1)

5. Insert T4 = Banana → Mango

This transaction does not have Apple.
So Banana starts directly under root:
null → Banana(1) → Mango(1)

6. Insert T5 = Apple → Banana → Orange

Apple and Banana paths exist again,
so we increase their counts:
Apple(4) → Banana(3)
Then add Orange as a new child under Banana:
Orange(1)

FP-Tree Construction:

Header Table:

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 36

Item Frequency Transactions (Header)
Apple 4 T1, T2, T3, T5
Banana 4 T1, T2, T4, T5
Mango 2 T1, T4
Orange 2 T3, T5

FP-Growth Algorithm
 The FP-Growth algorithm was introduced by Han in 2000.
 FP-Growth Algorithm is a faster and better alternative to the Apriori
algorithm.
 FP-Growth is a data mining method that finds frequent itemsets in a
database without creating candidate sets, unlike Apriori.
 It is mostly used in association rule mining, such as market basket
analysis.
 FP-Growth builds an FP-tree, a compact structure that stores item
frequencies and how they are related.
 Transactions are added to the FP-tree with items sorted by frequency,
which saves space and makes searching faster.
 Frequent itemsets are found from the FP-tree by looking at patterns that
meet the minimum support.
 FP-Growth is faster, uses less memory than Apriori, scans the database
fewer times, and does not create candidate sets.

FP Growth Algorithm
The working of the FP Growth algorithm in data mining can be
summarized in the following steps:

1. Scan the database:

 In this step, the algorithm scans the dataset to find the frequency of
each item.

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 37

  This frequency determines the order of items when adding them to the
FP-tree, with the most frequent items added first.

2. Sort items
 In this step, the items in the dataset are sorted in descending order of
frequency.
 The infrequent items that do not meet the minimum support threshold
are removed from the dataset.
 This helps to reduce the dataset's size and improve the algorithm's
efficiency.

3. Construct the FP-tree

 In this step, the FP-tree is built to store frequent items and their counts.
 The FP-tree is a compact data structure that represents itemsets and
their relationships.

4. Generate frequent itemsets:

 Once the FP-tree has been constructed, frequent itemsets can be
generated by recursively mining the tree.
 Starting from the bottom of the tree, the algorithm finds all item
combinations that satisfy the minimum support.

5. Generate association rules:

 Once frequent itemsets are identified, association rules are created.
 These rules help to discover interesting relationships between items in
the dataset.

Flowchart

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 38

FP Tree

 The FP-tree (Frequent Pattern tree) is a data structure used in the FP

Growth algorithm for frequent pattern mining.
 It represents frequent itemsets compactly and efficiently in the input
dataset.

The FP tree consists of the following components:

1. Root Node:
 The root node of the FP-tree represents an empty set.
 It has no associated item but a pointer to the first node of each item in
the tree.

2. Item Node
 Each item node in the FP-tree represents a unique item in the dataset.

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 39

  It stores the item name and the frequency count of the item in the
dataset.

3. Header Table
 The header table lists all unique items along with their frequency
counts.
 Header Table helps track each item’s location in the FP-tree.

4. Child Node
 Each child node represents an item that appears together with its parent
item in at least one transaction.

5. Node Link:
 A node link is a pointer that connects an item in the header table to the
first node of that item in the FP-tree.
 It is used to follow and explore all occurrences of the item when
mining frequent patterns.

Advantages of FP-Growth Algorithm

 No candidate generation: avoids creating large item combinations.
 Faster execution: scans the database only twice.
 Efficient for large datasets: handles big data effectively.

Disadvantages of FP-Growth Algorithm

 High memory usage: FP-tree can occupy a lot of memory.
 Complex implementation: harder to build and manage than simpler
methods.
 Recursive mining overhead: multiple recursive steps may slow
performance.

Example

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 40

Let us consider sample data set for Transaction
Transaction ID Items
T1 {M, N, O, E, K, Y}
T2 {D, O, E, N, Y, K}
T3 {K, A, M, E}
T4 {M, C, U, Y, K}
T5 {C, O, K, O, E, I}

Step 1: Count the Frequency of Items

First, we scan the transactions to calculate how many times each item appears
across all transactions.

Item Frequency
A 1
C 2
D 1
E 4
I 1
K 5
M 3
N 2
O 4
U 1
Y 3

Step 2: Sort Items in Each Transaction by Frequency

Now, sort the items in each transaction by their frequency (from highest to
lowest):

Transaction ID Items Ordered Itemset

T1 {M, N, O, E, K, Y} {K, E, M, O, Y}
T2 {D, O, E, N, Y, K} {K, E, O, Y}

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 41

T3 {K, A, M, E} {K, E, M}
T4 {M, C, U, Y, K} {K, M, Y}
T5 {C, O, K, O, E, I} {K, E, O}

Step 3: Build the FP-Tree

Now, let's start building the FP-Tree based on the sorted transactions.
1. First Transaction {K, E, M, O, Y}
 In this transaction, all items are simply linked, and their support count
is initialized as 1

2. Second Transaction {K, E, O, Y}

 In this transaction, we will increase the support count of K and E in the
tree to 2.
 As no direct link is available from E to O, we will insert a new path for O
and Y and initialize their support count as 1.

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 42

3. Third Transaction {K, E, M}
 After inserting this transaction, the tree will look as shown below.
 We will increase the support count for K and E to 3 and for M to 2.

4. Fourth Transaction {K, M, Y}

Similar to step b), first the support count of K is increased, then new nodes
for M and Y are initialized and linked accordingly.

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 43

5. Fifth Transaction {K, E, O}
Here simply the support counts of the respective elements are increased.
Note that the support count of the new node of item O is increased.

Step 4: Build Conditional Pattern Base (CPB)

 In this step we will create a Conditional Pattern Base for all the items.

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 44

  A Conditional Pattern Base (CPB) is the collection of all paths in the
FP-tree that end with a specific item, showing which items appear
before it along with their support counts.
 CPB helps us understand what items usually come before a particular
item in transactions.
 For example, for item O, the paths {K, E, M} and {K, E} will result in item
O.
The conditional pattern base for all items will look like as shown below
table:
Item Conditional Pattern Base
Y {K, E, M, O : 1}, {K, E, O : 1}, {K, M : 1}
O {K, E, M : 1}, {K, E : 2}
M {K, E : 2}, {K : 1}
E {K : 4}
K (root, so none)

Step 5: Construct Conditional FP-Trees

 A Conditional FP-Tree is a smaller FP-tree built for one specific item.
 It shows the frequent items that appear with that item and their combined
support counts.
 The main goal is to find frequent item combinations for each item by
using its Conditional Pattern Base (CPB).

The conditional frequent pattern tree will look like this below table
Item Conditional Pattern Base Conditional FP Tree
Y {K, E, M, O : 1}, {K, E, O : 1}, {K, M : 1}{K : 3}
O {K, E, M : 1}, {K, E : 2} {K, E : 3}
M {K, E : 2}, {K: 1} {K : 3}
E {K: 4} {K: 4}
Step 6: Generate Frequent Itemsets

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 45

 After building the Conditional FP-Trees, we now use them to find the
frequent itemsets — that means which items appear together often and
how many times.
Item Frequent Patterns
Y {K, Y - 3}
O {K, O - 3}, {E, O - 3}, {K, E, O - 3}
M {K, M - 3}
E {K, E - 4}

Difference between FP Growth Algorithm

and Apriori Algorithm
Apriori Algorithm FP Growth Algorithm
It is an array based algorithm It is a tree based algorithm.
It uses Join and Prune technique. It constructs conditional frequent
pattern tree and conditional pattern
base from database which satisfy
minimum support.
Apriori uses a breadth-first FP Growth uses a depth-first
search(BFS) search(DFS)
Apriori utilizes Uses level-wise FP Growth utilizes a pattern-growth
approach: generates 1-item approach means that, it only considers
patterns, then 2-item, then 3-item, patterns actually existing in the
etc. database.
Candidate generation is extremely Runtime increases linearly, depending
slow. on the number of transactions and
items
It requires large memory space due It requires less memory space due to
to large number of candidate compact structure and no candidate
generation. generation.
It scans the database multiple It scans the database only twice for
times for generating candidate sets. constructing frequent pattern tree.

Prepared by Mr.K Srikanth, Asst. Professor, IT, VNITSW, Guntur Page 46