MODULE 5 : Mining frequent patterns and

associations

Market Basket Analysis in Data Mining

Market Basket Analysis (MBA) is a data mining technique used to uncover patterns
in customer purchasing behavior. It identifies combinations of products frequently
bought together, enabling businesses to optimize marketing strategies, improve
inventory management, and boost sales.

How Market Basket Analysis Works

MBA is based on association rule mining, which uses the IF {Antecedent} THEN
{Consequent} construct. For example, if a customer buys bread (antecedent), they
are likely to buy butter (consequent). The analysis evaluates these relationships
using metrics like Support, Confidence, and Lift:
 Support measures how often a combination of items appears in transactions.
Example: If 500 out of 5000 transactions include both bread and butter,
support is 10%.
 Confidence indicates the likelihood of buying the consequent given the
antecedent. Example: If 1000 transactions include bread and butter, and 500
include bread alone, confidence is 20%.

 Lift assesses the strength of the association compared to random chance.

Example: A lift value of 2 means the items are twice as likely to be bought
together than individually.
Types of Market Basket Analysis

1. Descriptive MBA: Identifies past purchasing patterns without making

predictions. It helps understand customer behavior and optimize product
placement.
2. Predictive MBA: Uses machine learning to predict future purchases based on
historical data, aiding in cross-selling and targeted marketing.
3. Differential MBA: Compares purchasing patterns across different stores, time
periods, or customer segments to identify behavioral differences.
Algorithms Used

The Apriori Algorithm is widely used in MBA to identify frequent itemsets and
generate association rules. Other algorithms include FP-Growth and SETM, which
improve efficiency in analyzing large datasets.

Applications of Market Basket Analysis

  Retail: Optimizes product placement and cross-selling strategies. For
example, Amazon recommends "frequently bought together" items.

 E-commerce: Enhances product recommendations and targeted advertising.

 Finance: Analyzes credit card usage to detect fraud or recommend financial

products.

 Telecommunications: Bundles services like internet and TV to reduce churn.

 Healthcare: Identifies comorbid conditions and hereditary traits.

Benefits of Market Basket Analysis

MBA provides actionable insights to improve customer experience, increase sales,

and optimize operations. It helps businesses:

 Understand customer behavior and preferences.

 Develop effective pricing and promotional strategies.

 Enhance inventory management by identifying frequently bought items.

 Boost cross-selling and upselling opportunities.

By leveraging MBA, businesses can make data-driven decisions to enhance
customer satisfaction and maximize revenue.

Frequent Item Sets, Closed Item Sets and Association

Rules

Frequent Item Sets

These are groups of items that appear together frequently in a dataset.

 Definition: An itemset is considered frequent if its support (i.e., the
proportion of transactions containing the itemset) is greater than a user-
defined threshold.
 Example: In a grocery store dataset, if {bread, butter} appears in 40% of
transactions and the minimum support is 30%, then it's a frequent itemset.

 Use Case: Helps identify commonly bought items together.

Closed Item Sets

These are a subset of frequent item sets with an added condition.

 Definition: An itemset is closed if none of its immediate supersets have the
same support count.
  Why It Matters: Closed item sets eliminate redundancy by keeping only the
most informative combinations.
 Example: If {milk, bread} and {milk, bread, butter} both appear in 50
transactions, only {milk, bread, butter} is closed because it’s the larger set
with the same support.
Association Rules

These are if-then rules derived from frequent item sets to show relationships
between items.

 Format: A ⇒ B (If A is bought, then B is likely to be bought)

 Metrics:

o Support: Frequency of both A and B appearing together.

o Confidence: Likelihood of B given A (i.e., support(A ∪ B) / support(A)).

o Lift: Measures how much more likely B is given A compared to B

occurring independently.

 Example:

Suppose the dataset has 100 total transactions:

{coffee} appears in 60 transactions → Support(coffee) = 60%

{sugar} appears in 50 transactions → Support(sugar) = 50%

{coffee, sugar} appears in 40 transactions → Support(coffee ∪ sugar) = 40%

✅ Support

Support({coffee ⇒ sugar}) = Support({coffee, sugar}) =

40
= 0.4 or 40%
100

This means 40% of all transactions include both coffee and sugar.

✅ Confidence

Confidence({coffee} ⇒ {sugar}) =
Support(𝑐𝑜𝑓𝑓𝑒𝑒, 𝑠𝑢𝑔𝑎𝑟) 40
= = 0.67 or 67%
Support(𝑐𝑜𝑓𝑓𝑒𝑒) 60
 This means 67% of the people who buy coffee also buy sugar.

✅ Lift

Lift({coffee} ⇒ {sugar}) =
Confidence(𝑐𝑜𝑓𝑓𝑒𝑒 ⇒ 𝑠𝑢𝑔𝑎𝑟) 0.67
= = 1.34
Support(𝑠𝑢𝑔𝑎𝑟) 0.50

Interpretation:
A lift of 1.34 means people who buy coffee are 34% more likely to buy sugar
than people chosen at random.

 Summary Table

Concept Definition Key Metric Purpose

Frequent Item Find popular

Items that appear together often Support
Sets combinations

Closed Item Frequent sets with no super-set

Support Reduce redundancy
Sets of same support

Association If-then relationships between Confidence, Predict buying

Rules items Lift behavior

Frequent Pattern Mining

Frequent pattern mining can be classified based on several criteria:

1. Completeness of the Pattern to Be Mined

 Types:
o Frequent itemsets

o Closed frequent itemsets

o Maximal frequent itemsets

o Constrained frequent itemsets

 Goal: To extract all relevant patterns without redundancy.

2. Levels of Abstraction
  Multilevel Association Rules:

o Patterns mined at different levels of data abstraction.

o Example: From "milk" to "dairy product" to "food item".

3. Types of Values Handled

 Boolean: Presence or absence of items.

 Quantitative: Numeric values like price, quantity, ratings.

4. Kinds of Rules to Be Mined

 Association Rules: Discover relationships between items.

 Correlation Rules: Measure statistical correlation between items.

5. Kinds of Patterns to Be Mined

 Itemset Mining: Traditional frequent itemsets.

 Structured Pattern Mining: Graphs, trees, or other structured data.

 Sequential Pattern Mining: Patterns over time or ordered events.

Popular Algorithms

 Apriori Algorithm: Uses a breadth-first search to find frequent itemsets by

generating candidate sets and pruning infrequent ones.
 FP-Growth: A more efficient method that avoids candidate generation by
using a compact data structure called an FP-tree

Apriori Algorithm

Definition:
The Apriori Algorithm is a frequent itemset mining algorithm that uses the
property:
"All non-empty subsets of a frequent itemset must also be frequent."

This is called the Apriori Principle — it helps reduce the number of candidate
itemsets by eliminating those that can’t possibly be frequent.

🔁 How Apriori Works (Step-by-Step)

Given a transactional dataset and a minimum support threshold:

1. Generate Frequent 1-itemsets

 Count the frequency (support) of individual items.

 Keep only those items that meet the minimum support.

2. Generate Candidate k-itemsets

 Use the frequent (k−1)-itemsets to generate k-itemset candidates (e.g.,
combine {milk}, {bread} → {milk, bread}).

 Prune candidates that have infrequent subsets.

3. Scan Dataset and Count Support

 Count the support of each candidate itemset from the dataset.

 Retain those meeting minimum support.

4. Repeat Until No New Frequent Itemsets

 Continue generating larger itemsets (k+1) until no more frequent itemsets can
be found.

[Link] Association Rules Derive association rules from the frequent itemsets
using confidence and lift metrics

Applications

 Retail: Market basket analysis to optimize product placement.

 E-commerce: Recommend frequently bought-together items.

 Fraud Detection: Identify unusual transaction patterns.

Advantages of Apriori Algorithm

1. Simple and Easy to Understand

Apriori is conceptually straightforward and easy to implement, making it ideal
for educational purposes and small-scale applications.

2. Generates All Frequent Itemsets

It guarantees the discovery of all frequent itemsets that meet the minimum
support threshold.

3. Foundation for Other Algorithms

 It serves as a basis for more advanced algorithms like FP-Growth, making it
fundamental in data mining education and research.

4. Flexible with Constraints

You can add constraints (e.g., specific items must or must not be in the
itemset), making it adaptable to business rules.

5. Interpretable Output
The generated rules and itemsets are easy to interpret for decision-makers
and analysts.

Disadvantages:
1. Computationally Expensive
Apriori can be very slow on large datasets due to multiple database
scans and a large number of candidate itemsets.

2. Generates Many Candidates

Especially in dense datasets, the number of candidate itemsets grows
exponentially, which increases memory usage and processing time.

3. Inefficient with Long Itemsets

When frequent itemsets are long (many items in one set), Apriori's
performance drops significantly.

Lets understand the concept of apriori Algorithm with the help of an example.
Consider the following dataset and we will find frequent Item-Sets and generate
association rules for them:

Transactions of a Grocery Shop

Step 1 : Setting the parameters

 Minimum Support Threshold: 50% (item must appear in at least 3/5

transactions). This threshold is formulated from this formula:
Number of transactions containing itemset 𝐴
Support(𝐴) =
Total number of transactions
  Minimum Confidence Threshold: 70% ( You can change the value of
parameters as per the use case and problem statement ). This threshold is
formulated from this formula:
Support(𝑋 ∪ 𝑌)
Confidence(𝑋 → 𝑌) =
Support(𝑋)

Step 2: Find Frequent 1-Item-Sets

Lets count how many transactions include each item in the dataset (calculating the
frequency of each item).

Frequent 1-Itemsets

All items have support% ≥ 50%, so they qualify as frequent 1-Item-Sets. if any item
has support% < 50%, It will be omitted out from the frequent 1- Item-Sets.

Step 3: Generate Candidate 2-Item-Sets

Combine the frequent 1-Item-Sets into pairs and calculate their support. For this use
case we will get 3 item pairs ( bread,butter) , (bread,ilk) and (butter,milk) and will
calculate the support similar to step 2

Candidate 2-Itemsets

Frequent 2-Item-Sets: {Bread, Milk} meet the 50% threshold but {Butter, Milk} and
{Bread ,Butter} doesn't meet the threshold, so will be committed out.

Step 4: Generate Candidate 3-Item-Sets

Combine the frequent 2-Item-Sets into groups of 3 and calculate their support. for
the triplet we have only got one case i.e {bread,butter,milk} and we will calculate the
support.
 Candidate 3-Itemsets

Since this does not meet the 50% threshold, there are no frequent 3-Item-Sets.

Step 5: Generate Association Rules

Now we generate rules from the frequent Item-Sets and calculate confidence.

Rule 1: If Bread → Butter (if customer buys bread, the customer will buy butter
also)

 Support of {Bread, Butter} = 2.

 Support of {Bread} = 4.
 Confidence = 2/4 = 50% (Failed threshold).

Rule 2: If Butter → Bread (if customer buys butter, the customer will buy bread
also)

 Support of {Bread, Butter} = 3.

 Support of {Butter} = 3.

 Confidence = 3/3 = 100% (Passes threshold).

Rule 3: If Bread → Milk (if customer buys bread, the customer will buy milk
also)

 Support of {Bread, Milk} = 3.

 Support of {Bread} = 4.

 Confidence = 3/4 = 75% (Passes threshold).

Association Rule
The Association Rule Generation Algorithm is a two-step process used to identify
relationships or correlations between items in a transactional database.

This algorithm is most commonly used with Apriori or FP-Growth to generate rules
from frequent itemsets.

Input:

 A set of frequent itemsets (those with support ≥ minsup)

 Minimum confidence threshold

Output:
 A set of association rules that meet the minimum confidence threshold

Example solved above in Apriori algorithm

Methods to Improve the Efficiency of the Apriori Algorithm

The Apriori algorithm, while effective for mining frequent itemsets, can be
computationally expensive. Several techniques have been proposed to enhance its
efficiency:

[Link]-Based Technique: This method reduces the size of candidate itemsets by

hashing itemsets into buckets. For example, during the creation of frequent 1-
itemsets, 2-itemsets from each transaction can be hashed into buckets in a hash
table. The bucket counts are then incremented, allowing the algorithm to focus only
on promising candidates.
[Link] Reduction: Transactions that do not contain any frequent k-itemsets
are excluded from further scans. Since such transactions cannot contribute to
frequent (k+1)-itemsets, this reduces the number of transactions processed in
subsequent iterations, saving computational resources.
[Link]: This approach divides the database into non-overlapping partitions
and identifies frequent itemsets within each partition. Frequent itemsets from all
partitions are combined to form global candidates. A second database scan is then
performed to validate these candidates, ensuring that only globally frequent itemsets
are retained.
These methods significantly optimize the Apriori algorithm by reducing the
computational overhead and memory usage, making it more scalable for large
datasets.

[Link] Sampling

🔸 Idea:

Use a random sample of the data to approximate frequent itemsets.

Benefit:

 Fewer transactions to process.

 Works well when approximate results are acceptable.

Risk: Might miss itemsets that are rare in the sample but frequent in the full dataset.

5. Dynamic Itemset Counting

Dynamic Itemset Counting is an improved algorithm over Apriori that allows new
candidate itemsets to be added dynamically during the database scan, rather
than waiting until the end of each pass.
It was introduced to reduce the number of full passes over the transaction
database.