Unit 4

 Association Rule Mining is a data mining technique used to uncover interesting

relationships, patterns, or associations between items in large datasets. It is
primarily applied in transactional databases (e.g., market basket analysis) to find
rules that predict the occurrence of an item based on the occurrences of other
items.
 Association rule mining is a procedure which aims to observe frequently occurring patterns, correlations,
or associations from datasets found in various kinds of databases such as relational databases,
transactional databases, and other forms of repositories.
 Association Rule Mining, as the name suggests, association rules are simple If/Then statements that help
discover relationships between seemingly independent relational databases or other data repositories.
 Most machine learning algorithms work with numeric datasets and hence tend to be mathematical.
However, association rule mining is suitable for non-numeric, categorical data and requires just a little bit
more than simple counting.
An association rule has 2 parts:
 an antecedent (if) and

 a consequent (then)

 An antecedent is something that’s found in data, and a consequent is an item that is found in combination
with the antecedent. Have a look at this rule for instance:

“If a customer buys bread, he’s 70% likely of buying milk.”

 In the above association rule, bread is the antecedent and milk is the consequent. Simply put,
it can be understood as a retail store’s association rule to target their customers better. If the
above rule is a result of a thorough analysis of some data sets, it can be used to not only
improve customer service but also improve the company’s revenue.
Association rules are created by thoroughly analyzing data and looking for frequent if/then
patterns. Then, depending on the following two parameters, the important relationships are
observed:
[Link]: Support indicates how frequently the if/then relationship appears in the database.
[Link]: Confidence tells about the number of times these relationships have been
found to be true.
 So, in a given transaction with multiple items, Association Rule Mining primarily tries to find
the rules that govern how or why such products/items are often bought together. For example,
peanut butter and jelly are frequently purchased together because a lot of people like to
make PB&J sandwiches.
 Association Rule Mining is sometimes referred to as “Market Basket Analysis”, as it was the
first application area of association mining. The aim is to discover associations of items
occurring together more often than you’d expect from randomly sampling all the possibilities.
The classic anecdote of Beer and Diaper will help in understanding this better.
 Itemset: A set of items that appear together in transactions. For example, {bread,
butter}.
 Transaction: A record of items bought together. For example, a transaction might
consist of bread, butter, and milk.
 Association Rule: An implication expression of the form: X⟹Y
where X and 𝑌 are itemsets, and 𝑋∩𝑌=∅
For example, {bread} \implies {butter} suggests that if a customer buys bread, they are
likely to buy butter.
Association rule mining uses several metrics to evaluate the quality of the rules:
1. Support
2. Confidence
3. Lift
 Support: Indicates how frequently an itemset appears in the dataset. It represents the proportion
of transactions in which a particular itemset occurs.
Support for an itemset X is defined as:
Support(X)=Number of transactions containing the itemset X/Total number of transactions
Example: If {bread, butter} appears in 20 out of 100 transactions, its support is 0.2 (or 20%).
 Transaction ID Items
1 Bread, Butter, Milk
2 Bread, Butter
3 Bread, Milk
4 Butter, Milk
5 Bread, Butter, Milk

Find Support for Itemsets:

Itemset {Bread}:Appears in 4 transactions: T1, T2, T3, T5.
Support = 4/5=0.8 (or 80%).
Itemset {Butter}:Appears in 4 transactions: T1, T2, T4, T5.
Support = 4/5=0.8 =0.8 (or 80%).
Itemset {Bread, Butter}:Appears in 3 transactions: T1, T2, T5.
Support = 3/5=0.6(or 60%).
 Confidence is a metric used to evaluate the reliability of an association rule. It
measures how often the consequent (Y) occurs when the antecedent (X) is present in a
dataset.
 In the context of a rule X ⟹ Y, confidence indicates the probability of finding Y in
transactions that already contain X.
 Formula:
Confidence(X ⟹ Y)=Support(X∪Y)/Support(X)
• Support(X∪Y): The proportion of transactions that contain both X and Y.
• Support(X): The proportion of transactions that contain X.
Transaction ID Items
1 Bread, Butter, Milk
2 Bread, Butter
3 Bread, Milk
4 Butter, Milk
5 Bread, Butter, Milk

Calculate Confidence for Rule:

Rule: Bread ⟹ Butter
Support of Bread ∪ Butter:
•Transactions containing both: T1, T2, T5.
•Support = 3/5=0.6
Support of Bread:
•Transactions containing Bread: T1, T2, T3, T5.
•Support = 4/5=0.8.
Confidence:
Confidence=Support(Bread∪Butter)/Support(Bread)
=0.6/0.8=0.75
The confidence of 0.75 (or 75%) means that 75% of the transactions containing "Bread" also contain
"Butter."
Lift
 Lift is a metric used in association rule mining to evaluate the strength and importance
of a rule. It measures how much more likely the occurrence of the consequent (Y) is
when the antecedent (X) is present, compared to when Y occurs independently of X.
 In other words, lift quantifies the correlation between X and Y.
Formula: Lift(X ⟹ Y)=Confidence(X ⟹ Y)/Support(Y)
 Where:
• Confidence: The proportion of transactions containing Y among those containing X.
• Support(Y): The overall proportion of transactions containing Y.
Alternatively:
Lift(X⟹Y)= Support(X∪Y)/ Support(X) .Support(Y)
Interpretation:
[Link] > 1:
1. Positive correlation between XXX and YYY.
2. The presence of XXX increases the likelihood of YYY.
3. Rule is stronger than expected by chance.

[Link] = 1:
1. No correlation between XXX and YYY.
2. The occurrence of YYY is independent of XXX.

[Link] < 1:
1. Negative correlation between XXX and YYY.
2. The presence of XXX reduces the likelihood of YYY.
Rule: Bread ⟹ Butter
[Link](X∪Y):
Transactions containing both Bread and Butter: T1, T2, T5.
Support = 3/5=0.6= 0.653=0.6.
Support(X):
•Transactions containing Bread: T1, T2, T3, T5.
•Support = 4/5=0.8
Support(Y):
•Transactions containing Butter: T1, T2, T4, T5.
•Support = 4/5=0.8
Confidence(X⟹Y):
Confidence = Support(X∪Y)/Support(X)=0.6/0.8=0.75
 Lift:
Lift(X ⟹ Y)=Confidence(X ⟹ Y)/Support(Y)=0.75/0.8=0.9375
Interpretation of the Lift Value:
• Lift = 0.9375: The occurrence of "Bread" slightly decreases the likelihood of "Butter"
compared to random chance.
 Large itemsets are an essential concept in data mining, particularly in the context of
association rule mining. They refer to sets of items (or features) in a dataset that appear
together frequently, exceeding a predefined minimum support threshold.
Key Concepts:
 Itemset: A collection of items in a transaction or dataset. For example, in a grocery store
dataset, an itemset might be {milk, bread, eggs}.
 Support: The proportion of transactions in the dataset that contain a particular itemset.
Support of an itemset X=Number of transactions containing X/Total number of transactions
Large (or Frequent) Itemset: An itemset is considered "large" or "frequent" if its support
meets or exceeds a user-specified minimum support threshold.
 The process of finding association rules in data mining involves two primary steps:
identifying frequent itemsets and generating association rules from these itemsets.
Here's a step-by-step explanation:
Step 1: Identify Frequent Itemsets
 Frequent itemsets are groups of items that appear together in transactions with a frequency
greater than or equal to a predefined minimum support threshold.
[Link] Data: A transaction database where each transaction is a set of items.
Example:
T1: {Milk, Bread, Butter}
T2: {Milk, Bread}
T3: {Bread, Butter}
T4: {Milk, Butter}
2. Set Minimum Support Threshold: For example, 50% (an itemset must appear in at least
half of the transactions).
3. Apply a Frequent Itemset Mining Algorithm: Use algorithms like Apriori, FP-
Growth, or ECLAT to identify frequent itemsets.
Example: With 50% support threshold:
 Frequent 1-itemsets: {Milk}, {Bread}, {Butter} (all with support ≥ 50%).
 Frequent 2-itemsets: {Milk, Bread}, {Milk, Butter}, {Bread, Butter} (all with support ≥
50%).
Step 2: Generate Association Rules
Association rules describe relationships between items in frequent itemsets.
[Link] Confidence Threshold: Confidence is a measure of the strength of the rule,
calculated as:
[Link](X→Y)=Support(X∪Y)/Support(X)
Example: A confidence threshold of 60% means only rules with at least 60% confidence
are considered.
2. Form Rules:
 For each frequent itemset, generate rules by dividing it into an antecedent (X) and a consequent (Y).
 Example: For the itemset {Milk, Bread}:
 Rule 1: Milk → Bread
 Rule 2: Bread → Milk
3. Evaluate Rules:
Compute confidence for each rule and filter rules that meet the threshold.
Example:
Support(Milk, Bread) = 50%.
Confidence(Milk → Bread) = Support(Milk, Bread) / Support(Milk) = 50% / 75% = 66.7%.
If the confidence threshold is 60%, this rule is valid.
4. Optional Metrics:
• Lift: Measures how much more likely Y is to appear with X compared to being independent.
Lift(X→Y)=Confidence(X→Y)/Support(Y)
• Leverage and Conviction: Other metrics to assess rule strength.
• This process helps uncover meaningful patterns in datasets, supporting applications like market
basket analysis, recommendation systems, and customer behavior insights
1. For Each Frequent Itemset:
 Take each frequent itemset 𝐹 from the set of frequent itemsets 𝐿
F must have at least two items (rules cannot be generated from single-item sets).
2. Generate Subsets:
 Generate all possible non-empty subsets of F. Let S be one of these subsets.
Example: If F={A,B,C} , subsets of F are:
{{A},{B},{C},{A,B},{A,C},{B,C}}.
3. Create Rules:
• For each subset S, form a rule of the form: S→(F−S), where (F−S) is the remaining items in F.
4. Calculate Confidence: Compute the confidence of the rule S→(F−S) as
Confidence(S→(F−S))=Support(F)/Support(S)
5. Filter Rules: Retain the rule if its confidence is greater than or equal to min_conf
6. Repeat:Repeat the process for all frequent itemsets F.
 APRIORI ALGORITHM
 The Apriori algorithm uses frequent itemsets to generate association rules, and it is designed
to work on the databases that contain transactions. With the help of these association rule, it
determines how strongly or how weakly two objects are connected. This algorithm calculates
the itemset associations efficiently. It is the iterative process for finding the frequent itemsets
from the large dataset.
 It is mainly used for market basket analysis and helps to find those products that can be
bought together. It can also be used in the healthcare field to find drug reactions for patients.
 What is Frequent Itemset?
 Frequent itemsets are those items whose support is greater than the threshold value or user-
specified minimum support. It means if A & B are the frequent itemsets together, then
individually A and B should also be the frequent itemset.
 Suppose there are the two transactions: A= {1,2,3,4,5}, and B= {2,3,7}, in these two
transactions, 2 and 3 are the frequent itemsets.
Steps for Apriori Algorithm
Below are the steps for the apriori algorithm:
 Step-1: Determine the support of itemsets in the transactional database,
and select the minimum support and confidence.
 Step-2: Take all supports in the transaction with higher support value than
the minimum or selected support value.
 Step-3: Find all the rules of these subsets that have higher confidence
value than the threshold or minimum confidence.
 Step-4: Sort the rules as the decreasing order of lift.
Solution:
Step-1: Calculating C1 and L1:
•In the first step, we will create a table that contains support count (The frequency of each
itemset individually in the dataset) of each itemset in the given dataset. This table is called
the Candidate set or C1.
 Now, we will take out all the itemsets that have the greater support count that the
Minimum Support (2). It will give us the table for the frequent itemset L1.
Since all the itemsets have greater or equal support count than the minimum support,
except the E, so E itemset will be removed.

Step-2: Candidate Generation C2, and L2:

•In this step, we will generate C2 with the help of L1. In C2, we will create the pair of the itemsets of L1
in the form of subsets.
•After creating the subsets, we will again find the support count from the main transaction table of
datasets, i.e., how many times these pairs have occurred together in the given dataset. So, we will get
the below table for C2:
Again, we need to compare the C2 Support count with the minimum support count, and
after comparing, the itemset with less support count will be eliminated from the table C2.
It will give us the below table for L2

Step-3: Candidate generation C3, and L3:

•For C3, we will repeat the same two processes, but now we will form the C3 table with subsets of three
itemsets together, and will calculate the support count from the dataset. It will give the below table:

Now we will create the L3 table. As we can see from the above C3 table, there is only one
combination of itemset that has support count equal to the minimum support count. So, the L3 will
have only one combination, i.e., {A, B, C}.
Step-4: Finding the association rules for the subsets:
 To generate the association rules, first, we will create a new table with the possible rules from
the occurred combination {A, B.C}. For all the rules, we will calculate the Confidence using
formula sup( A ^B)/A. After calculating the confidence value for all rules, we will exclude the
rules that have less confidence than the minimum threshold(50%).

Rules Support Confidence

A ^B → C 2 Sup{(A ^B) ^C}/sup(A ^B)= 2/4=0.5=50%

B^C → A 2 Sup{(B^C) ^A}/sup(B ^C)= 2/4=0.5=50%

A^C → B 2 Sup{(A ^C) ^B}/sup(A ^C)= 2/4=0.5=50%

C→ A ^B 2 Sup{(C^( A ^B)}/sup(C)= 2/5=0.4=40%

A→ B^C 2 Sup{(A^( B ^C)}/sup(A)= 2/6=0.33=33.33%

B→ A^C 2 Sup{(B^( A ^C)}/sup(B)= 2/7=0.28=28%

As the given threshold or minimum confidence is 50%, so the first three rules A ^B → C, B^C → A, and
A^C → B can be considered as the strong association rules for the given problem.
1. Simplicity: The algorithm is easy to understand and implement, making it a
popular choice for beginners in data mining.
2. Effectiveness for Small Datasets: Works well with small to medium-sized datasets
where computational resources are not a significant concern.
3. Guaranteed Correctness: Based on the a priori property, which ensures that all
frequent itemsets are correctly identified.
4. Reduces Search Space: By leveraging the a priori principle, it prunes candidate
itemsets that cannot be frequent, reducing unnecessary computations.
5. Wide Applicability: Suitable for market basket analysis, healthcare data, web log
mining, and other transactional data.
1. High Computational Cost: Generates a large number of candidate itemsets,
especially when the dataset has many items or when the minimum support threshold
is low.
2. Memory Intensive: Requires significant memory to store candidate itemsets, making
it inefficient for large datasets.
3. Multiple Dataset Scans: Requires multiple passes over the dataset, increasing the
input/output (I/O) cost, especially for very large datasets.
4. Performance Degradation: Slower for dense datasets (datasets with many frequent
items) because it generates an exponential number of candidates.
5. Limited Scalability: Not suitable for very large-scale datasets as it becomes
computationally expensive.
6. Sensitivity to Minimum Support Threshold: The choice of minimum support greatly
affects the performance and results. A low threshold results in many candidates,
while a high threshold may miss important patterns.
 Sampling in data mining refers to the process of selecting a subset of data from a larger
dataset to analyze and extract meaningful insights. Since datasets in real-world applications
can be massive, sampling provides a way to perform efficient data analysis by working with a
representative subset of the data.
 Various sampling algorithms are used to ensure the selected data maintains the integrity and
characteristics of the original dataset.
Steps of Sampling Algorithm by Applying Negative Border
[Link] the Objective of Sampling
1. Determine the purpose of sampling (e.g., analyzing frequent itemsets, finding associations).
2. Decide on a minimum support threshold for frequent itemsets.

[Link] the Dataset

1. Define the population or dataset to be sampled.
2. Ensure the dataset is large enough to benefit from negative border application.
3. Generate Frequent Itemsets
 Use an algorithm like Apriori or FP-Growth to identify frequent itemsets based on the support threshold.
 Record frequent itemsets and their supports.
 Identify the Negative Border
4. Construct itemsets that:
 Are not frequent (below the support threshold).
 Have all their subsets frequent.
 These itemsets represent potential candidates that could become frequent in future iterations.
5. Incorporate Negative Border in Sampling
 Include itemsets from the negative border in the sampling process.
 Adjust their probabilities or weights to ensure their presence in the sample, even if they're not frequent.
6. Sample the Dataset
 Draw a sample from the dataset using the adjusted probabilities or weights (e.g., stratified sampling or
weighted sampling).
 Ensure the sample contains both frequent itemsets and itemsets from the negative borde
[Link] the Sample
 Apply the desired data mining task (e.g., association rule mining, clustering) to the sampled
data.
 Check whether itemsets from the negative border are becoming frequent in the sample.

[Link] or Adjust
 If results from the sampled data deviate significantly from the population, adjust:
 Sampling size.
 Support threshold.
 Weighting for negative border inclusion.
Dataset:
Transaction ID Items
T1 {A, B, C}
T2 {A, C}
T3 {A, B, D}
T4 {B, C}
T5 {A, B}
Minimum Support: 2
Frequent 1-itemsets:
{A}, {B}, {C} (support ≥ 2)
Generate Candidate 2-itemsets:
{A, B}, {A, C}, {B, C}
All are frequent.
Generate Candidate 3-itemsets:
{A, B, C}, {A, B, D}.
{A, B, C} is frequent.
{A, B, D} is not frequent but its subsets {A, B}, {A, D}, and {B, D} are all frequent.
Therefore, {A, B, D} belongs to the negative border.
Include Negative Border in Sampling:
In future mining steps, {A, B, D} is checked for frequency if the dataset is updated or additional samples are taken.
Advantages:
• Cost and resource efficiency
• Increased precision
• Accuracy of data
• Reduced sampling error
• Insights in cases where it is infeasible to measure an entire population
Disadvantages:
• Bias: The researcher may be biased in selecting a sample, which can skew the results.
• Sample size: The sample set may not be large enough to represent the full population.
• Sampling method: The quality of insights depends on the sampling method, and a poor choice can
lead to misleading results.
• Granularity: There may not be enough sampled data to give statistically significant results when
focusing on specific funnels or pages.
• Rare events: Unusual but significant events, like rare user interactions, might not be present in the
sample.
• Data manipulation
 Partitioning in data mining is a technique used to divide a dataset into smaller subsets for
efficient analysis and processing. It is commonly applied in clustering, classification, and
distributed computing tasks to handle large datasets or discover patterns in specific segments
of data.
Key Objectives of Partitioning
 Scalability: Manage large datasets by breaking them into smaller, manageable parts.
 Efficiency: Process partitions in parallel to speed up computations.
 Improved Insights: Focus analysis on specific groups or regions of data for better results.
Step 1:Divide the database
Divide the entire database into smaller partition
Step 2: First Database scan
Bring each partition of database and use a level wise approach such as apriori algorithm to find
the large itemsets in each partition
Step 3: Candidate Selection
During the second scan only those itemset that are large in atleast one partition are selected as
candidates
Step 4:Counting the consolidation
Count the selected candidates to determine if they are large across the entire database
Consolidate the result to generate the final set of large itemset across the entire dataset
Transaction ID Items Purchased
T1 {A, B, C}
T2 {A, C}
T3 {A, B, D}
T4 {B, C}
T5 {A, B}
 We will perform partitioning by dividing this dataset into two partitions:
Partition 1: {T1, T2, T3}
Partition 2: {T4, T5}
 Find Frequent Itemsets in Each Partition)
Partition 1: {T1, T2, T3}
1-itemsets:
{A}: Appears in T1, T2, T3 → support = 3 (frequent)
{B}: Appears in T1, T3, T5 → support = 3 (frequent)
{C}: Appears in T1, T2 → support = 2 (frequent)
{D}: Appears in T3 → support = 1 (not frequent)
2-itemsets:
{A, B}: Appears in T1, T3 → support = 2 (frequent)
{A, C}: Appears in T1, T2 → support = 2 (frequent)
{B, C}: Appears in T1, T4 → support = 1 (not frequent)
 Partition 2: {T4, T5}
1-itemsets:
{A}: Appears in T5 → support = 1 (not frequent)
{B}: Appears in T4, T5 → support = 2 (frequent)
{C}: Appears in T4 → support = 1 (not frequent)
{D}: Appears in T5 → support = 1 (not frequent)
2-itemsets:{B, C}: Appears in T4 → support = 1 (not frequent)

 Frequent Itemsets per Partition:

Partition 1: {A}, {B}, {C}, {A, B}, {A, C}
Partition 2: {B}
 Candidate SelectionNow, we select itemsets that are frequent in at least one partition as candidates
for further counting in the second pass:
Frequent itemsets in Partition 1: {A}, {B}, {C}, {A, B}, {A, C}
Frequent itemsets in Partition 2: {B}
So, the candidate itemsets that we will count in the second scan across the entire dataset are:
{A}, {B}, {C}, {A, B}, {A, C}
 Counting the Consolidation (Second Scan):We perform a second pass through the entire database to count the
support of the candidates across the entire dataset.
Transaction Set (All Transactions):
T1 = {A, B, C}
T2 = {A, C}
T3 = {A, B, D}
T4 = {B, C}
T5 = {A, B}
 Count the Support for Each Candidate Itemset:
Candidate {A}: Appears in T1, T2, T3, T5 → support = 4
Candidate {B}: Appears in T1, T3, T4, T5 → support = 4
Candidate {C}: Appears in T1, T2, T4 → support = 3
Candidate {A, B}: Appears in T1, T3, T5 → support = 3
Candidate {A, C}: Appears in T1, T2 → support = 2
 Frequent Itemsets Across the Entire Database:
{A}, {B}, {C}, {A, B}, {A, C} are all frequent since their support is greater than or equal to 2.
Final Frequent Itemsets Across the Entire Dataset:After the second scan, we have the following frequent itemsets across
the entire database:
1-itemsets: {A}, {B}, {C}
2-itemsets: {A, B}, {A, C}
Advantages
 Scalability
 interpretability
 Flexibility
 dimensionality reduction
 anomaly detection
Disadvantages
 Information Loss

 Partitioning bias

 Storage Requirements

 Selection of Partitioning Criteria

Parallel and Distributed Association Rule Mining Algorithms are designed to efficiently mine
frequent itemsets and generate association rules from large datasets. These approaches address
the need for high-performance computing and scalability, especially when working with huge
datasets that can't be processed on a single machine.
Categories of parallel and distributed association rule mining
In Parallel and Distributed Association Rule Mining, the algorithms and techniques can be broadly
categorized based on how they handle data partitioning, communication, and task management.
These categories aim to optimize the efficiency of mining frequent itemsets and generating
association rules in a parallel or distributed environment.

Here are the main categories of parallel and distributed association rule mining:
1. Data Parallelism
2. Task Parallelism
 In data parallelism, the dataset is partitioned, and each partition is processed
independently by different processors or nodes. The goal is to distribute the dataset across
multiple processors or machines and then merge the results at the end.
Key Features:
 Data Partitioning: The dataset is split into smaller partitions, with each processor or node
handling one partition.
 Local Mining: Each partition performs frequent itemset mining independently.
 Result Merging: After local mining, the results from each partition are merged to find global
frequent itemsets.
Examples:
 Parallel Apriori: The dataset is split into smaller chunks, and each chunk is processed to find
frequent itemsets. After local mining, the frequent itemsets are consolidated to form global
frequent itemsets.
 Parallel FP-growth: The dataset is divided, and each partition constructs its own FP-tree.
Afterward, the results are merged.
 In task parallelism, the different tasks involved in mining association rules are distributed
among multiple processors or nodes. These tasks could include generating candidate
itemsets, counting itemset support, pruning infrequent itemsets, and generating association
rules.
Key Features:
 Task Division: The mining process is divided into different subtasks, such as itemset
generation, counting, and rule generation.
 Independent Tasks: Each processor or node works on a different subtask, and results are
combined after each step.
Examples:
 Parallelized Apriori Algorithm: The process of generating candidate itemsets, counting
support, and rule generation is split. Some processors work on generating candidate
itemsets, others count the support, and the final processor generates the rules based on the
frequent itemsets.
 FP-growth with Task Parallelism: One task might handle partitioning the FP-tree, while others
handle mining frequent itemsets or generating rules.
 Count Distribution Algorithm is typically used in parallel mining algorithms to count the
frequency of itemsets (or patterns) across multiple partitions of a dataset. It helps in efficiently
calculating frequent itemsets without requiring the entire dataset to be loaded into a single
machine's memory.
 This algorithm works by distributing the task of counting itemsets across multiple machines or
processes, and then aggregating the results.
 In the context of Association Rule Mining, particularly in parallel mining, the Count Distribution
Algorithm addresses the challenge of how to divide the task of counting itemset occurrences
efficiently.
Steps Involved in the Count Distribution Algorithm
1. Partitioning the Data:The dataset is divided into multiple partitions, which are distributed across
multiple processors or machines.
Each partition holds a subset of the transactions, and each processor works on its own partition to
compute the frequent itemsets.
2. Local Counting :Each processor scans its local partition and counts the frequency of itemsets. This is
done independently on each partition.
Frequent 1-itemsets (individual items) are counted in each partition, and larger itemsets (2-itemsets, 3-
itemsets, etc.) are generated and [Link] processor generates its local frequency count of
itemsets.
3. Sending Local Counts to the Master:After the local counting step, each processor sends its
frequency count of itemsets to the central master node (or another aggregation point).
These counts are usually aggregated based on itemsets (i.e., all counts for itemset "A, B" from different
processors are summed up).
[Link] Counting and Aggregation (Reduce Phase): The master node (or a centralized process)
collects the frequency counts from each processor and aggregates them.
The aggregation involves summing up the counts of the same itemset across all partitions.
The global counts are used to determine which itemsets are frequent (i.e., those that meet the support
threshold).
5. Final Candidate Generation:The aggregated counts are used to generate the final candidate
itemsets (those that are frequent across the entire dataset).
These frequent itemsets can then be used to generate association rules based on their confidence and
lift.
Step-by-Step Example with Count Distribution:
Partition the Data: Suppose the dataset is divided into two partitions:
Partition 1: {A, B, D}, {B, C, D}, {A, C, D}
Partition 2: {A, B, C}, {B, D}
Local Counting (Map Phase):
Processor 1 (handling Partition 1) counts itemsets:
{A}: 2 times
{B}: 2 times
{D}: 3 times
{A, B}: 1 time
{B, D}: 2 times
{A, D}: 2 times
{A, B, D}: 1 time
Processor 2 (handling Partition 2) counts itemsets:
{A}: 1 time
{B}: 2 times
{C}: 1 time
{D}: 1 time
{A, B}: 1 time
{B, D}: 1 time
{A, B, C}: 1 time
Send Local Counts to Master:
Processor 1 sends:
{A: 2, B: 2, D: 3, A,B: 1, B,D: 2, A,D: 2, A,B,D: 1}
Processor 2 sends:
{A: 1, B: 2, C: 1, D: 1, A,B: 1, B,D: 1, A,B,C: 1}
Global Counting and Aggregation (Reduce Phase):
The master node aggregates the counts:
{A: 3, B: 4, D: 4, C: 1, A,B: 2, B,D: 3, A,D: 2, A,B,D: 1, A,B,C: 1}
Final Candidate Generation:
After applying a support threshold (let's say 2 transactions), the final frequent itemsets
would be:
{A: 3, B: 4, D: 4, A,B: 2, B,D: 3}
These itemsets are then used to generate association rules.
 The Data Distribution Algorithm is a strategy used in distributed data mining to divide and
distribute data across multiple nodes or processors. It is primarily used to enable parallel
processing and scalability when working with large datasets that cannot fit into the memory of
a single machine or require computational resources beyond a single system.
How Data Distribution Algorithm works?
1. Partition the dataset and candidates into p partitions, one for each processor
2. Each processor counts the candidates given to it using its local DB partition
3. Broadcast the local DB partition to all other processors
4. Each processor obtains a global count for its data using the broadcasted partitions
5. Determine globally large itemsets and generate the next candidates using the global counts
6. Divide the next candidates among processors for the next scan
7. Repeat steps 2-6 until no more large itemsets can be found
 Incremental rules in data mining are designed to handle dynamic datasets that
continuously change due to additions, deletions, or modifications. Unlike traditional
methods, which require re-mining the entire dataset from scratch, incremental rule
techniques efficiently update results by incorporating only the changes in the data.
 Why Incremental Rules?
[Link] Datasets: Many real-world datasets (e.g., transaction logs, sensor data, social
media feeds) are constantly updated.
[Link]: Recomputing from scratch is computationally expensive; incremental
methods reuse previously computed results.
[Link]: They are more scalable for large datasets.
1. Identify Data Changes:
 Insertion: New data is added to the dataset.
 Deletion: Some existing data is removed.
 Modification: Data attributes or values are updated.
2. Analyze Affected Patterns:Determine which frequent patterns or rules are impacted by
the changes.
3. Update Rule Metrics:Adjust support, confidence, and other metrics for affected rules.
4. Generate New Rules (if applicable):Extract new rules from the incremental data and
merge them with the existing rules.
5. Prune Irrelevant Rules:Remove rules that fall below the minimum support or
confidence thresholds.
Incremental Rule Algorithms
[Link] (Fast Update Procedure):
1. Handles additions and deletions in transactional datasets.
2. Adjusts the counts of candidate itemsets without full recomputation.

[Link] (Adaptive Incremental Mining):

1. Designed for evolving databases where updates occur frequently.
2. Uses a divide-and-conquer approach to focus on updated portions.

[Link] FP-Tree:
1. Modifies the Frequent Pattern Tree (FP-Tree) structure to reflect data updates without reconstructing
it from scratch.

Incremental rule mining is essential for real-time analytics in scenarios where datasets are constantly
changing. It ensures that the mined patterns and rules remain accurate and relevant while significantly
reducing computation costs compared to traditional methods.
Example of Incremental Rule Mining
Dataset (Initial Transactions):
Transaction ID Items
T1 {Milk, Bread}
T2 {Milk, Eggs}
T3 {Milk, Bread, Eggs}
Frequent Itemsets:
{Milk}: Support = 3/3 = 100%
{Bread}: Support = 2/3 = 66.7%
{Milk, Bread}: Support = 2/3 = 66.7%
Incremental Data:
Transaction ID Items
T4 (New) {Bread, Eggs}
Updated Frequent Itemsets:
{Milk}: Support = 3/4 = 75%
{Bread}: Support = 3/4 = 75%
{Milk, Bread}: Support = 2/4 = 50%
{Bread, Eggs}: Support = 2/4 = 50% (newly discovered)