Module 4

What are Association Rules in Data Mining?

The if-else statement is also called the association rule, which further refers to showing the
probability of the relationship between the data items. These types of relationships occur in large
data sets in various databases. With the help of the association rule in mining, we can get the
number of applications present in data mining, and these widely discovered the correlation of the
sales in the transactional data or medical data sets.

What are Use Cases for Association Rules?

Association rules have so many practical use cases across various industries and domains
because of their ability to uncover meaningful relationships and patterns within datasets. Here
are some common use cases for association rules:

1. Market Basket Analysis:

It is one of the most famous applications. All the Retailers can use the association rules to
discover item associations in customer shopping baskets. For example, if there is a need
to find out that customers who buy chips are likely to buy salsa as well, stores can
optimize product placements and marketing strategies.
2. Healthcare:

o Disease Diagnosis: with the help of Association rules, we can identify patterns in
patient health records, such as discovering combinations of symptoms, test
results, or patient characteristics indicative of certain diseases.
o Treatment Recommendations: with the help of Association rules, we can suggest
suitable treatments or interventions based on the patient's medical history and
condition, improving personalized healthcare.
3. Financial Services:

o Fraud Detection: with the help of association rules, Banks and credit card
companies can detect fraudulent transactions by identifying unusual spending
patterns or sequences of transactions associated with fraud.
o Cross-Selling: Financial institutions can recommend additional products or
services to customers based on their transaction history and financial behaviour.
4. Market Research:

o Consumer Behavior Analysis: Marketers can identify consumer preferences by

analyzing purchase histories and demographic data, leading to better-targeted
advertising and product development.
o Product Placement Optimization: We have to understand which products are often
purchased together to help optimize product placements in physical stores and
online marketplaces.
 5. Web Usage Analysis:

o Website Optimization: with the help of association rules, all Website owners can
analyze user behaviour on their websites. For instance, we also have to understand
which pages are visited together, and after doing this, we can help improve
website navigation and content recommendations.
6. Manufacturing:

o Quality Control: Manufacturers can identify factors or conditions associated with

product defects, which helps improve quality control processes.
o Production Optimization: it can lead to more efficient manufacturing processes.
Discovering associations among different production variables
7. Telecommunications:

o Network Management: In the telecom industry, we can detect patterns in network

traffic that may indicate issues or anomalies with the help of association rules.
o Customer Churn Prediction: Telecom companies can identify factors associated
with customer churn and take preventive measures to retain customers.
8. Inventory Management:

o Supply Chain Optimization: Understanding the relationships between various

items in a supply chain can help optimize inventory levels, reduce carrying costs,
and improve order fulfilment.
9. Social Network Analysis:

o Friendship Recommendations: Social media platforms can use association rules to

suggest new friends or connections based on common interests, connections, or
behaviours.
10. Text Mining:

o Content Recommendation: In content recommendation systems (e.g., Netflix or

Amazon), association rules can recommend movies, books, or products to users
based on their past interactions and preferences.

How do Association Rules Work?

Association rules are fundamental in data mining and machine learning, aiming to discover
interesting relationships and patterns within large datasets. These rules identify associations or
dependencies between items or attributes in the data. The primary algorithm used for association
rule mining is the Apriori algorithm, which follows a systematic process to generate these rules:

1. Frequent Itemset Generation:

In this algorithm, we have to start the process by identifying frequent item sets in the dataset.
The frequent item is a collection of items (or attributes) frequently occurring in the data.
We can measure the frequency of the data set by using a metric called support. These supports
are represented by the proportion of transactions or records in which the itemset appears.

We have to use the Apriori algorithm, which uses the bottom-up approach. At first, we have to
look for the frequent individual items, and then we have to gradually combine them to find larger
itemsets.

2. Association Rule Generation:

After identifying the frequent items, we have to generate the association rules from these items.

Then, we have to write the association rule, which will be in the form of "if-then" statements,
where the "if" part is called the antecedent (premise), and the "then" part is called the consequent
(conclusion).

Then, we have to explore the Apriori algorithm, which combines items within frequent itemsets
to generate potential association rules.

3. Rule Pruning:
We have to apply some criteria to ensure that only meaningful rules are generated. The most
useful criteria are as follows.

1. Support Threshold: we have to create a rule with support to be considered valid. This
ensures that the rule applies to a sufficient number of transactions.
2. Confidence Threshold: A rule must have a minimum confidence level to be considered
interesting. Confidence is the probability that the antecedent implies the consequent, and
it measures the strength of the association.
3. Lift Threshold: Lift is a measure that compares the observed support of the rule to what
would be expected if the items in the rule were independent. A lift value greater than 1
indicates a positive association, while a lift value less than 1 indicates a negative
association.

4. Iterative Process:
In this process, we have to iterate the Apriori algorithm by generating itemsets, creating rules,
and pruning rules until no more valid rules can be generated.

Then, we have to perform the iteration in which the algorithm employs a "downward closure
property," which states that if an item is frequent, all of its subsets are also frequent. This
property helps reduce the computational complexity of the algorithm.

5. Output:
The final output of association rule mining is a set of association rules that meet the specified
support and confidence thresholds.
Methods to discover association rules
Association rule discovery is a key task in data mining used to find interesting relationships (like “people
who buy X also buy Y”). It is widely used in Data Mining and market basket analysis.

1. Apriori Algorithm

 One of the most popular methods.

 Works on the principle:
👉 “If an itemset is frequent, all its subsets must also be frequent.”
 Steps:
1. Find frequent individual items.
2. Extend them to larger itemsets.
3. Prune infrequent ones using support.

✔ Pros: Easy to understand

✘ Cons: Slow for large datasets (many scans)

2. FP-Growth Algorithm (Frequent Pattern Growth)

 Improves over Apriori by avoiding repeated database scans.

 Uses a special tree structure called FP-tree.

Steps:

1. Build FP-tree from dataset.

2. Extract frequent patterns from the tree.

✔ Pros: Faster, efficient for large datasets

✘ Cons: More complex to implement

3. Hybrid Approaches

 Combine advantages of multiple algorithms

(e.g., Apriori + FP-Growth)

✔ Pros: Better performance in real-world systems

Apriori Algorithm
The Apriori Algorithm is a popular method for mining these association rules because of its
simplicity and practical results. Unlike other complex methods, Apriori is straightforward,
making it suitable for beginners and effective in real-world applications.
 Apriori is an algorithm designed to extract frequent itemsets from transactional databases and
generate association rules. It is based on the principle that if an itemset is frequent, all its subsets
must also be frequent. This assumption helps reduce the number of possible itemsets that need to
be checked, making the process efficient.

Itemsets and transactions

A dataset for Apriori typically consists of transactions, where each transaction is a collection of
items purchased together. For example, a supermarket's sales data may contain transactions such
as:

 Milk, Bread, Butter

 Milk, Diaper, Beer, Bread
 Diaper, Beer, Butter

Support, confidence, and lift

Association rule mining relies on three key metrics:

Support: The frequency with which an item appears in the dataset. It is calculated as:
 How the Apriori Algorithm Works

Step-by-step process
1. Generating candidate itemsets: The algorithm starts by identifying individual items and
counting their occurrences to determine frequent items.
2. Pruning based on minimum support: Itemsets that appear less than the minimum support
threshold are removed.
3. Generating frequent itemsets: The algorithm generates larger itemsets by combining frequent
smaller itemsets, iterating until no more frequent itemsets can be formed.
4. Deriving association rules: It extracts rules based on confidence and lift values to determine
meaningful relationships.
Example

Consider a dataset with transactions:

1. Milk, Bread
2. Milk, Butter
3. Milk, Bread, Butter
4. Bread, Butter
Using a minimum support of 50%, the algorithm identifies frequent itemsets and extracts rules
such as:

 Milk → Bread: Confidence: 66.7%

 Bread → Butter: Confidence: 66.7%
These rules help businesses understand purchasing behaviors and optimize their inventory.

Example
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:
Partition Algorithm

Partitioning Method: This clustering method classifies the information into

multiple groups based on the characteristics and similarity of the data. Its the data
analysts to specify the number of clusters that has to be generated for the clustering
methods. In the partitioning method when database(D) that contains multiple(N)
objects then the partitioning method constructs user-specified(K) partitions of the
data in which each partition represents a cluster and a particular region. There are
many algorithms that come under partitioning method some of the popular ones are
K-Mean, PAM(K-Medoids), CLARA algorithm (Clustering Large Applications)
etc. In this article, we will be seeing the working of K Mean algorithm in detail.

K-Mean (A centroid based Technique): The K means algorithm takes the input
parameter K from the user and partitions the dataset containing N objects into K
clusters so that resulting similarity among the data objects inside the group
(intracluster) is high but the similarity of data objects with the data objects from
outside the cluster is low (intercluster). The similarity of the cluster is determined
 with respect to the mean value of the cluster. It is a type of square error algorithm.
At the start randomly k objects from the dataset are chosen in which each of the
objects represents a cluster mean(centre). For the rest of the data objects, they are
assigned to the nearest cluster based on their distance from the cluster mean. The
new mean of each of the cluster is then calculated with the added data objects.

Algorithm:

Method:

1. Randomly assign K objects from the dataset(D) as cluster centres(C)

2. (Re) Assign each object to which object is most similar based upon mean values.
3. Update Cluster means, i.e., Recalculate the mean of each cluster with the
updated values.
4. Repeat Step 2 until no change occurs.
Example: Suppose we want to group the visitors to a website using just their age as follows:

16, 16, 17, 20, 20, 21, 21, 22, 23, 29, 36, 41, 42, 43, 44, 45, 61, 62, 66
Initial Cluster:
K=2
Centroid(C1) = 16 [16]
Centroid(C2) = 22 [22]
Note: These two points are chosen randomly from the dataset.
Iteration-1:
C1 = 16.33 [16, 16, 17]
C2 = 37.25 [20, 20, 21, 21, 22, 23, 29, 36, 41, 42, 43, 44, 45, 61, 62, 66]
Iteration-2:
C1 = 19.55 [16, 16, 17, 20, 20, 21, 21, 22, 23]
C2 = 46.90 [29, 36, 41, 42, 43, 44, 45, 61, 62, 66]
Iteration-3:
C1 = 20.50 [16, 16, 17, 20, 20, 21, 21, 22, 23, 29]
C2 = 48.89 [36, 41, 42, 43, 44, 45, 61, 62, 66]
Iteration-4:
C1 = 20.50 [16, 16, 17, 20, 20, 21, 21, 22, 23, 29]
C2 = 48.89 [36, 41, 42, 43, 44, 45, 61, 62, 66]
No change Between Iteration 3 and 4, so we stop. Therefore we get the clusters (16-29) and (36-66) as 2 clusters we get using K
Mean Algorithm.

Pincer Search Algorithm

  It is designed to overcome the inefficiency of algorithms like Apriori.
 It simultaneously:
o Searches from bottom (small itemsets) → like Apriori
o Searches from top (large itemsets) → using maximal itemsets

👉 This “pinching” from both sides gives it the name Pincer Search.

Instead of only building itemsets from smaller ones, it:

 Starts with:
o Candidate 1-itemsets (bottom-up)
o Maximal Frequent Candidate Set (MFCS) (top-down)
 Reduces the search space quickly by eliminating unnecessary candidates.

Steps of Pincer-Search Algorithm

1. Initialize
o Generate candidate 1-itemsets (like Apriori)
o Initialize MFCS with all items
2. Scan Database
o Count support for:
 Candidate itemsets
 MFCS elements
3. Prune
o Remove infrequent itemsets
o Update MFCS by removing supersets of infrequent sets
4. Generate Next Candidates
o Create higher-level candidates (k-itemsets)
5. Update MFS
o If an MFCS itemset is frequent → move it to MFS
6. Repeat
o Continue until no new candidates

Advantages
✔ Faster than Apriori in many cases
✔ Reduces database scans
✔ Efficient for large datasets
✔ Quickly finds maximal frequent itemsets

Disadvantages
✖ Complex to implement
✖ MFCS maintenance can be costly
✖ Not always better for very sparse data

Example
Suppose items: {A, B, C, D}

 Start:
o Bottom: {A}, {B}, {C}, {D}
o Top: {A, B, C, D}
 If {A, B, C, D} is infrequent → break into smaller sets
 Continue narrowing from both directions until frequent patterns are found

Dynamic Itemset counting algorithm:

 Proposed to overcome the inefficiency of multiple database scans in Apriori.

 It adds new candidate itemsets while scanning the database, instead of waiting for the next
pass.

👉 So, counting and candidate generation happen simultaneously.

🔹 Key Idea
 Divide the database into intervals (partitions).
 After scanning each interval:
o Start counting new candidate itemsets dynamically.
 This allows early identification of frequent itemsets.

🔹 Concepts Used
1. Itemset States

Each itemset belongs to one of four states:

 Dashed Circle (DC) → Candidate, not yet fully counted

 Dashed Square (DS) → Suspected frequent, still counting
 Solid Circle (SC) → Confirmed infrequent
 Solid Square (SS) → Confirmed frequent

Working Steps
1. Initialize
o Start with all 1-itemsets in DC (Dashed Circle)
2. Scan Database in Intervals
 Divide database into equal parts (checkpoints)
o
3. Dynamic Counting
o After each interval:
 Update support counts
 Move itemsets between states (DC → DS → SS/SC)
4. Generate New Candidates
o When an itemset becomes frequent (DS → SS):
 Generate its supersets
 Add them to DC (start counting immediately)
5. Repeat
o Continue until all itemsets are fully counted

🔹 Advantage
✔ Fewer database scans (main advantage)
✔ Faster than Apriori in large datasets
✔ Early discovery of frequent itemsets
✔ Efficient use of database passes

🔹 Disadvantages
✖ More complex than Apriori
✖ Requires careful memory management
✖ Overhead of maintaining multiple itemset states

FP tree growth algorithm:

 FP-Growth uses a compact data structure called an FP-Tree (Frequent Pattern Tree).
 It avoids repeated database scans and candidate generation.

👉 Main idea: Compress the database → Mine patterns directly from the tree

Key Concepts
1. FP-Tree

 A tree structure that stores:

o Items
o Their frequency
o Transaction paths

2. Header Table

 Maintains list of items with their frequency

 Links similar items in the tree
Steps of FP-Growth Algorithm

Step 1: Scan Database (1st Pass)

 Find frequent 1-itemsets

 Remove infrequent items (based on minimum support)
 Sort items in descending order of frequency

Step 2: Build FP-Tree (2nd Pass)

 Insert transactions into the tree:

o Follow sorted order
o Share common prefixes
 Update counts along paths

Step 3: Mine the FP-Tree

 Extract frequent patterns using conditional pattern base

Sub-steps:

1. Select an item from header table

2. Find its conditional pattern base
3. Construct conditional FP-tree
4. Generate frequent itemsets
5. Repeat for all items

Example
Transactions:

 T1: {A, B, D}
 T2: {B, C}
 T3: {A, C, D}

After building FP-tree:

 Common patterns like {A, D}, {B}, etc. are extracted

🔹 Advantages
✔ No candidate generation
✔ Only 2 database scans
✔ Faster than Apriori
✔ Efficient for large datasets
🔹 Disadvantages
✖ Tree can become complex for very large data
✖ Difficult to understand compared to Apriori
✖ Recursive mining process