DWDM — UNIT III

Mining Frequent Patterns, Associations & Association Rules

1. Frequent Pattern Mining

Frequent Pattern Mining in data mining is the process of identifying patterns or associations within
a dataset that occur frequently. The analysis is based on transaction databases, which include
records or transactions that represent collections of objects. Items inside these transactions are
grouped together as item sets. The importance of patterns is greatly influenced by two key
measurements: Support and Confidence.

Support quantifies how frequently an item set appears in the database, while Confidence
quantifies how likely it is that a rule generated from the item set is accurate.

Techniques for Frequent Pattern Mining:

The Apriori Algorithm is one of the most popular methods. It uses a step-by-step procedure to
find frequent item sets by scanning the database iteratively. The FP-growth Algorithm provides a
different strategy by building a compact data structure known as the FP-tree, which avoids
repeated database scans and is much faster for large datasets. The Eclat Algorithm (Equivalence
Class Clustering and bottom-up Lattice Traversal) uses a vertical data format to efficiently mine
frequent patterns.

Applications of Frequent Pattern Mining:

Market Basket Analysis is one of the most widely known applications. Businesses identify
itemsets that commonly appear together in customer transactions to understand buying patterns.
Web usage mining examines user navigation patterns to understand how people use websites. In
Bioinformatics, frequent pattern mining helps identify relevant DNA patterns from biological
datasets.

2. Market Basket Analysis

Market basket analysis in data mining is used to analyze the combination of products that are
bought together by customers. This is a technique that gives a careful study of purchases done by
a customer in a supermarket. It identifies the pattern of frequently purchased items by customers,
which helps companies promote deals, offers, and sales. Data mining concepts are used in Sales
and Marketing to provide better customer service, improve cross-selling opportunities, and
increase direct mail response rates. Customer Retention through pattern identification and
prediction of likely defections is also possible using data mining. Risk Assessment and Fraud
detection areas also use data mining to identify inappropriate or unusual behaviour.

—1—
How Market Basket Analysis Works:
Market basket analysis mainly works with the Association Rule: {IF} → {THEN}. The IF part is
called the Antecedent — it is an item found within the data, written on the left-hand side. The
THEN part is called the Consequent — it is an item found in combination with the antecedent,
written on the right-hand side.

■ Example
IF a customer buys Bread → THEN he is likely to buy Butter as well.
Association rule written as: {Bread} → {Butter}
Here, Bread is the Antecedent and Butter is the Consequent.

Types of Market Basket Analysis:

1. Descriptive Market Basket Analysis — This type only derives insights from past data and is
the most frequently used approach. The analysis does not make any predictions but rates the
association between products using statistical techniques. For those familiar with the basics of
Data Analysis, this type of modelling is known as unsupervised learning.

■ Example
The supermarket analyzes past transaction data and discovers that customers who buy bread
frequently also buy butter and jam. With this analysis, the store places bread, butter, and jam in the
same aisle to encourage bundled purchases.

2. Predictive Market Basket Analysis — This type uses supervised learning models like
classification and regression. It aims to mimic the market to analyze what causes what to happen.
It predicts future purchases based on past purchasing patterns. Retailers can make data-driven
decisions about which products to carry, how to price them, and how to optimize shop layouts.

■ Example
Based on seasonal trends and past data, the retailer predicts that customers who buy jackets in
winter are likely to buy scarves as well. With this analysis, the store creates a winter bundle offer:
'Buy a Jacket and Get 20% Off on a Scarf' to boost sales.

3. Differential Market Basket Analysis — This type is beneficial for competitor analysis. It
compares purchase history between stores, between seasons, between two time periods, or
between different days of the week, to find interesting patterns in consumer behaviour.

—2—
 ■ Example
The supermarket compares weekday vs. weekend shoppers and finds: Weekday shoppers
(working professionals) buy ready-to-eat meals and coffee, while Weekend shoppers (families) buy
fresh vegetables, snacks, and soft drinks. With this analysis, the store offers weekday discounts on
ready meals and weekend promotions on family-sized snack packs.

Benefits of Market Basket Analysis:

Enhanced Customer Understanding: Market basket research offers insights into customer
behavior, including what products they buy together and which products they buy most frequently.
Retailers can use this information to better understand their customers and make informed
decisions. Improved Inventory Management: By examining market basket data, retailers can
determine which products are slow sellers and which ones are commonly bought together, helping
them stock inventory more effectively. Better Pricing Strategies: A better understanding of the
connection between product prices and consumer behavior helps merchants develop pricing plans
that boost sales and profitability. Sales Growth: Market basket analysis helps businesses identify
which products are most frequently bought together and where they should be positioned in the
store to grow sales.

Applications of Market Basket Analysis:

Retail: Used to examine consumer buying patterns and inform decisions about product placement,
inventory management, and pricing tactics. E-commerce: Helps online merchants understand
customer buying habits and make data-driven decisions about product recommendations and
targeted advertising. Finance: Used to evaluate investor behaviour and forecast the types of
investment items investors will likely buy in the future. Telecommunications: Used to evaluate
consumer behavior and make data-driven decisions about which goods and services to offer,
enhancing client satisfaction. Manufacturing: Used to evaluate consumer behavior and make
decisions about which products to produce and which materials to use in the production process,
increasing effectiveness and cutting costs.

3. Apriori Algorithm
The Apriori Algorithm is a foundational method in data mining used for discovering frequent
itemsets and generating association rules. Its significance lies in its ability to identify relationships
between items in large datasets, which is particularly valuable in market basket analysis.

How the Apriori Algorithm Works:

Step 1 — Identifying Frequent Itemsets: The algorithm begins by scanning the dataset to identify
individual items (1-itemsets) and their frequencies. It then establishes a minimum support
threshold, which determines whether an itemset is considered frequent.

—3—
Step 2 — Creating Possible Item Groups: Once frequent 1-itemsets (single items) are identified,
the algorithm generates candidate 2-itemsets by combining frequent items. This process continues
iteratively, forming larger itemsets (k-itemsets) until no more frequent itemsets can be found.

Step 3 — Removing Infrequent Item Groups: The algorithm employs a pruning technique based
on the Apriori Property, which states that if an itemset is infrequent, all its supersets must also be
infrequent. This significantly reduces the number of combinations that need to be evaluated.

Step 4 — Generating Association Rules: After identifying frequent itemsets, the algorithm
generates association rules that illustrate how items relate to one another, using metrics like
support, confidence, and lift to evaluate the strength of these relationships.

Key Metrics of the Apriori Algorithm:

Support measures how frequently an item appears in the dataset relative to the total number of
transactions. A higher support indicates a more significant presence of the itemset in the dataset.
For example: 'Bread is bought in 20% of all transactions.'

Confidence assesses the likelihood that item Y is purchased when item X is purchased. It
provides insight into the strength of the association between two items. For example: 'If bread is
bought, butter is bought 75% of the time.'

Lift evaluates how much more likely two items are to be purchased together compared to being
purchased independently. A lift greater than 1 suggests a strong positive association. For example:
'Bread and butter are much more likely to be bought together than by chance.'

■ Formula
Support(X) = (No. of transactions containing X) / (Total transactions) × 100%
Confidence(X → Y) = Support(X ∪ Y) / Support(X) × 100%
Lift(X → Y) = Confidence(X → Y) / Support(Y)

Complete Worked Example — Apriori Step by Step:

Consider a dataset of 5 transactions containing items: Bread, Butter, and Milk.

Step 1 — Setting the Parameters: Minimum Support Threshold = 50% (item must appear in at
least 3 out of 5 transactions). Minimum Confidence Threshold = 70%.

Step 2 — Find Frequent 1-Itemsets: Count how many transactions include each item. All items
qualify if their support% is greater than or equal to 50%. If any item has support% less than 50%, it
will be omitted from the frequent 1-itemsets.

Item Support Count Support % Qualifies?

Bread 4 80% Yes ✓

Butter 3 60% Yes ✓

—4—
 Item Support Count Support % Qualifies?

Milk 4 80% Yes ✓

Step 3 — Generate Candidate 2-Itemsets: Combine the frequent 1-itemsets into pairs and
calculate their support. For this use case, we get three item pairs: {Bread,Butter}, {Bread,Milk}, and
{Butter,Milk}.

Item Pair Support Count Support % Qualifies (>=50%)?

{Bread, Butter} 2 40% No ✗ — Omitted

{Bread, Milk} 3 60% Yes ✓

{Butter, Milk} 2 40% No ✗ — Omitted

Step 4 — Generate Candidate 3-Itemsets: Combine the frequent 2-itemsets into groups of 3. For
this dataset, the only triplet is {Bread, Butter, Milk}.

Item Triplet Support Count Support % Qualifies?

{Bread, Butter, Milk} 1 20% No ✗ — STOP

Step 5 — Generate Association Rules: Generate rules from the frequent itemsets {Bread, Milk}
and calculate confidence for each.

■ Example
Rule 1: Bread → Milk | Conf = Support{Bread,Milk} / Support{Bread} = 3/4 = 75% ✓ Passes
Rule 2: Milk → Bread | Conf = Support{Bread,Milk} / Support{Milk} = 3/4 = 75% ✓ Passes
Interpretation of Lift > 1: Diaper → Beer (Lift=1.25) means customers who buy Diapers are 1.25x
more likely to also buy Beer than by chance.
Interpretation of Lift < 1: Bread → Milk (Lift=0.94) means the items are NOT strongly associated
beyond chance.

Applications of Apriori Algorithm:

E-commerce: Used to recommend products often bought together (e.g., laptop + laptop bag),
increasing sales. Food Delivery Services: Identifies popular combos such as burger + fries to
offer combo deals. Streaming Services: Recommends related movies or shows based on what
users often watch together. Financial Services: Analyzes spending habits to suggest
personalized credit card deals based on frequent purchases. Travel and Hospitality: Creates
travel packages (e.g., flight + hotel) by finding commonly purchased services together. Health and
Fitness: Suggests workout plans or supplements based on users' past activities.

4. Improving the Efficiency of Apriori

—5—
The Apriori algorithm can be slow on very large datasets because it requires multiple database
scans. Several methods are used to improve its efficiency:

Transaction Reduction: Transactions that do not contain any frequent items are removed from
further analysis. Since these transactions will not contribute to any frequent itemsets, removing
them reduces unnecessary computation.

■ Example
If you know that a customer rarely buys 'bananas', you can remove transactions containing only
bananas from further analysis, as they are unlikely to contribute to frequent itemsets.

Partitioning: The database is divided into smaller non-overlapping partitions, and each partition is
analyzed separately. An itemset is considered potentially frequent if it is frequent in at least one
partition.

■ Example
If you have a large customer database, you can split it into regional partitions (North, South, East,
West) and analyze each partition separately. Only itemsets frequent in at least one partition are
kept for global analysis.

Hash-based Techniques: Hash tables are used to store and count candidate itemsets. Instead of
scanning every transaction, the algorithm stores each itemset and its count in a hash table,
updating only when the combination appears.

■ Example
In a grocery store database where you want to find frequent itemsets like 'bread and milk', a hash
table stores each itemset and its count. Only updating the count when the combination appears in
a transaction significantly reduces computation.

Sampling: Instead of scanning the entire database, a random subset of transactions is analyzed
first to identify potential frequent itemsets. The results are then refined using the full database.

■ Example
To quickly identify potential frequent itemsets, randomly sample 20% of transactions from your
database, analyze them to get candidate frequent itemsets, then verify these candidates against
the complete database.

Dimensionality Reduction: The number of features (items) in the data is reduced before applying
the Apriori algorithm. This reduces the search space significantly.

Dynamic Itemset Counting: While scanning the database for frequent itemsets, instead of waiting
until the end of a complete scan to generate new candidate itemsets, they are added to the
analysis as soon as relevant information is encountered, reducing unnecessary iterations.

—6—
5. Generating Rules for Frequent Itemsets
Frequent itemsets, also known as association rules, are a fundamental concept in association rule
mining. A frequent item set is a set of items that occur together frequently in a dataset. The
frequency of an item set is measured by the support count — the number of transactions in the
dataset that contain the item set. Association Mining searches for frequent items in the data set
and finds interesting associations and correlations between itemsets in transactional and relational
databases.

The need for Association Mining arises because if items X and Y are purchased frequently
together, it is good to place them together in stores or provide discount offers. For example, if a
customer buys Milk and Bread, they also likely buy Butter. So the association rule is: ['milk'] ∧
['bread'] ⇒ ['butter']. The seller can then suggest butter to a customer who buys milk and bread.

Important Definitions:
Support(A → B) = Support_count(A ∪ B). It is one of the measures of interestingness. This tells
about the usefulness and certainty of rules. For example, 5% support means total 5% of
transactions in the database follow the rule.

Confidence(A → B) = Support_count(A ∪ B) / Support_count(A). A confidence of 60% means that

60% of customers who purchased milk and bread also bought butter.

If a rule satisfies both minimum support and minimum confidence, it is called a strong rule.

Support_count(X): Number of transactions in which X appears.

Maximal Itemset: An itemset is maximal frequent if none of its supersets are frequent.

Closed Itemset: An itemset is closed if none of its immediate supersets have the same support
count.

K-Itemset: An itemset which contains K items. It is frequent if its support count is greater than the
minimum support count.

Advantages of Association Rule Mining:

Efficient discovery of patterns: Association rule mining algorithms are efficient at discovering
patterns in large datasets, making them useful for market basket analysis and recommendation
systems. Easy to interpret: The results are easy to understand and explain. Wide range of
applications: Can be used in retail, finance, and healthcare to improve decision-making and
increase revenue. Handles large datasets: These algorithms can handle datasets with many
items and transactions, making them suitable for big-data scenarios.

Disadvantages of Association Rule Mining:

—7—
Large number of generated rules: Association rule mining can generate a large number of rules,
many of which may be irrelevant or uninteresting. Limited in detecting complex relationships: It
only considers the co-occurrence of items in the same transaction. Computationally expensive:
As the number of items and transactions increases, the number of candidate itemsets also
increases. Threshold setting difficulty: The minimum support and confidence threshold must be
set before the process, which requires a good understanding of the data.

6. Mining Multi-level Association Rules

For many applications, it is difficult to find strong associations among data items at low or primitive
levels of abstraction due to the sparsity of data at those levels. Strong associations discovered at
high levels of abstraction may represent common-sense knowledge. Therefore, data mining
systems should provide capabilities for mining association rules at multiple levels of abstraction.
Association rules generated from mining data at multiple levels of abstraction are called multilevel
association rules.

Multilevel association rules can be mined efficiently using concept hierarchies under a
support-confidence framework. A concept hierarchy defines a sequence of mappings from a set of
low-level concepts to higher-level, more general concepts. Data can be generalized by replacing
low-level concepts with their higher-level concepts (ancestors) from a concept hierarchy.

■ Example
Concept Hierarchy Example — Electronics Store:
Level 0: ALL (root)
Level 1: Computer | Software | Printer & Camera | Computer Accessory
Level 2: Laptop Computer | Desktop Computer | Office Software | Antivirus Software
Level 3: IBM Desktop Computer | Microsoft Office Software | ...
Level 4: Most specific level (individual product SKUs)
Frequent itemsets are calculated starting at Level 1, working down until no more frequent itemsets
are found.

Approaches for Mining Multilevel Association Rules:

1. Uniform Minimum Support: The same minimum support threshold is used when mining at
each level of abstraction. The search procedure is simplified and users are required to specify only
one minimum support threshold. However, this approach has difficulties — items at lower levels of
abstraction are unlikely to occur as frequently as those at higher levels. If the threshold is set too
high, it could miss meaningful associations at lower levels; if set too low, it may generate many
uninteresting associations at higher levels.

2. Reduced Minimum Support: Each level of abstraction has its own minimum support threshold.
The deeper the level of abstraction, the smaller the corresponding threshold. For example, the

—8—
minimum support thresholds for levels 1 and 2 are 5% and 3% respectively. In this way, 'computer',
'laptop computer', and 'desktop computer' are all considered frequent at their respective levels.

■ Example
Level 1 (Computer): min_support = 5% → 'Computer' qualifies as frequent
Level 2 (Laptop): min_support = 3% → 'Laptop Computer' qualifies as frequent
Level 3 (IBM Laptop): min_support = 1% → 'IBM Laptop' qualifies as frequent

3. Group-Based Minimum Support: Users or experts have insight into which groups are more
important than others. It is sometimes more desirable to set up user-specific, item, or group-based
minimum support thresholds. For example, a user could set up the minimum support thresholds
based on product price, or on items of particular interest, such as setting particularly low support
thresholds for laptop computers and flash drives in order to pay special attention to the association
patterns containing items in these categories.

7. Mining Multi-dimensional Association Rules

The popular area of application for multi-level association is market basket analysis, which studies
the buying habits of customers. We refer to each distinct predicate in a rule as a dimension.

A rule with a single distinct predicate that occurs multiple times is called a single-dimensional or
intra-dimensional association rule. For instance: buys(X, 'Laptop') → buys(X, 'Printer') contains
only the 'buys' predicate, occurring twice.

Association rules with two or more dimensions or predicates are called multidimensional
association rules. There are two sub-types:

Inter-dimensional Association Rules: Each predicate occurs only once in the rule.

■ Example
Age(X, '20–29') ∧ Occupation(X, 'Student') ⇒ Buys(X, 'Laptop')
This rule contains three predicates: age, occupation, and buys — each occurring only once.

Hybrid-dimension Association Rules: Some predicates occur more than once (mixed with
repeated predicates).

■ Example
Age(X, '20–29') ∧ Buys(X, 'Laptop') ⇒ Buys(X, 'Printer')
Here 'buys' appears twice (as both antecedent and consequent) while 'age' appears once.

Database Attribute Types for Multi-dimensional Mining:

—9—
Categorical Attributes have a finite number of possible values with no ordering among the values
(also called nominal attributes). These values represent categories or labels without any ranking or
meaningful numerical interpretation.

■ Example
Colors of a Car: {Red, Blue, Black, White, Green} — no ranking between colors.
Types of Fruits: {Apple, Banana, Orange, Mango, Grape} — no fruit is 'greater' than another.

Quantitative Attributes are numeric variables that have an inherent ordering or sequencing
between their values. These attributes can be measured or counted and allow mathematical
operations like addition, subtraction, and averaging.

Types of Quantitative Attributes: Discrete Attributes take integer values (countable and finite or
infinite). Example: Number of students in a class, number of cars in a parking lot. Continuous
Attributes can take any value within a range (measurable, including decimals). Example: Height of
a person, weight of an object, temperature in a city.

8. Correlation Analysis
A correlation measure can be used to augment the support-confidence framework for association
rules. This leads to correlation rules of the form: A ⇒ B [support, confidence, correlation]. That is,
a correlation rule is measured not only by its support and confidence but also by the correlation
between itemsets A and B.

Lift is the simplest correlation measure. The lift between the occurrence of A and B is computed
as:

■ Formula
Lift(A, B) = P(A ∪ B) / [P(A) × P(B)] = Confidence(A → B) / Support(B)
Lift < 1 : A and B are negatively correlated (occurrence of A discourages B)
Lift > 1 : A and B are positively correlated (occurrence of A encourages B)
Lift = 1 : A and B are independent — no correlation

9. Mining Quantitative Association Rules

Quantitative association rules are multidimensional association rules in which the numeric
attributes are dynamically discretized during the mining process so as to satisfy some mining
criteria, such as maximizing the confidence or compactness of the rules mined.

The focus is specifically on mining quantitative association rules having two quantitative
attributes on the left-hand side of the rule and one categorical attribute on the right-hand

— 10 —
side. Such rules are referred to as two-dimensional quantitative association rules because
they contain two quantitative dimensions:

■ Formula
Aquan1 ∧ Aquan2 ⇒ Acat
where Aquan1 and Aquan2 are tests on quantitative attribute intervals,
and Acat tests a categorical attribute from the task-relevant data.

■ Example
Suppose you are curious about the association between customer age and income, and the
type of television customers like to buy:
age(X, '30–39') ∧ income(X, '42K–48K') ⇒ buys(X, 'HDTV')
This rule states: customers aged 30–39 with income between 42K–48K are likely to buy an HDTV.

— 11 —