Apriori Algorithm
Input:
1. Transaction Dataset (D):
A list of transactions where each transaction is a set of items.
Example:
D={{A,B,C},{A,C},{B,C},{A,B,C,D},{A,B}}
2. Minimum Support Threshold (min_support}:
The minimum proportion of transactions required for an itemset to be considered
frequent.
Example: min_support=50% (for a dataset of 5 transactions, support ≥ 3 transactions).
3. Minimum Confidence Threshold (min_confidence):
The minimum likelihood required for an association rule to be considered strong.
Example: min_confidence=70%.
Process:
1. Step 1: Generate Frequent 1-Itemsets
o Count the occurrences of each individual item in D.
o Calculate the support for each item:
Support(Item)=Count(Item)/Total Transactions
o Retain items with Support(Item)≥min_support
2. Step 2: Generate Candidate k-Itemsets (Ck)
o Combine frequent (k-1)-itemsets to generate candidate k-itemsets (e.g.,
combine {A} and {B} to form {A, B}).
o Use the Apriori Property: Only keep itemsets where all subsets are frequent.
3. Step 3: Prune Infrequent Itemsets
o Calculate support for each candidate k-itemset in Ck by scanning D.
o Retain itemsets with Support≥min_support, resulting in frequent itemsets (Lk).
4. Step 4: Repeat for Larger k
o Increment k (e.g., from 2-itemsets to 3-itemsets) and repeat steps 2-3 until no
more frequent itemsets can be generated.
o For each frequent itemset I, generate rules A→B where A∪B=I and A∩B=∅.
5. Step 5: Generate Association Rules
Support: Support(A∪B).
o Calculate:
Confidence: Confidence(A→B)=Support(A∪B)/Support(A).
o Retain rules with Confidence≥min_confidence
Output:
1. Frequent Itemsets:
A list of all itemsets that meet min_support, along with their support values.
Example: {A,B,C} with support 60%.
2. Association Rules:
A list of rules with their support and confidence values.
Example: {A,B}→{C} with confidence 75%.
FP Growth
Input:
1. Transaction Dataset (D):
A list of transactions where each transaction is a set of items.
Example:
D={{A,B,C},{A,C},{B,C},{A,B,C,D},{A,B}}
2. Minimum Support Threshold (min_support}:
The minimum proportion of transactions required for an itemset to be considered
frequent.
Example: min_support=50% (for a dataset of 5 transactions, support ≥ 3 transactions).
Process:
1. Step 1: Build the FP-Tree (Trie Structure):
o Scan Dataset: Count how many times each item appears in the transactions.
o Remove Low-Support Items: Keep only items that meet the min_support
threshold.
o Sort Items in Each Transaction: Rearrange items in descending order of
frequency.
o Insert into Trie:
For each transaction, create or update a path in the Trie.
Each node represents an item and stores:
The item name.
A count showing how often the path is used.
2. Step 2: Extract Frequent Itemsets:
o Start with the least frequent item in the Trie.
o Find Conditional Pattern Base: Collect all paths in the Trie leading to that
item.
o Build Conditional FP-Tree: Use these paths to create a smaller Trie for that
item.
o Mine Frequent Itemsets Recursively: Repeat the process for each
conditional FP-tree to find all combinations of items.
3. Step 3: Combine Frequent Itemsets:
o Add the current item to the frequent itemsets generated from its conditional
FP-tree.
o Continue this process until all items in the original Trie have been processed.
Output:
1. Frequent Itemsets:
A list of all itemsets that meet min_support, along with their support values.
Example: {A,B},{B,C},{A,C},{A,B,C}
1. Closed Itemset Generation Algorithm
Input
Transactional dataset D
Minimum support threshold σ
Output
Set of closed itemsets (frequent itemsets where no superset has the same support)
Method (Steps)
Step 1: Generate Frequent Itemsets
Use Apriori or FP-Growth to generate all frequent itemsets with support ≥σ
An itemset X is closed if there exists no superset Y such that X⊂Y and support(X) =
Step 2: Identify Closed Itemsets
support(Y).Mathematically:
Step 3: Output Closed Itemsets
Collect and return all closed itemsets.
2. Maximal Itemset Generation Algorithm
Input
Transactional dataset D
Minimum support threshold σ
Output
Set of maximal itemsets (frequent itemsets with no frequent supersets)
Method (Steps)
Step 1: Generate Frequent Itemsets
Use Apriori or FP-Growth to generate all frequent itemsets with support ≥σ
Step 2: Identify Maximal Itemsets
An itemset X is maximal if there exists no frequent superset Y such that X⊂Y.
Mathematically:
Step 3: Output Maximal Itemsets
Collect and return all maximal itemsets.