00:00:00

Description

Editorial

Frequent Pattern Discovery in Transaction Data

MEDIUM20 pts

In data mining and knowledge discovery, one of the most powerful techniques for understanding large datasets is frequent pattern mining. This approach identifies item combinations that appear together with notable regularity across a collection of records—revealing hidden associations and co-occurrence patterns that drive business insights.

Given a dataset of transactions (where each transaction is a collection of items) and a minimum support threshold (expressed as a fraction between 0 and 1), your task is to discover all frequent itemsets—combinations of items whose occurrence frequency meets or exceeds the specified threshold.

Understanding Support: The support of an itemset is the proportion of transactions in which that itemset appears. For example, if an itemset {apple, banana} appears in 6 out of 10 transactions, its support is 0.6 (or 60%).

$$\text{support}(X) = \frac{|{T \in D : X \subseteq T}|}{|D|}$$

Where:

X is the itemset being evaluated
D is the collection of all transactions
T represents individual transactions in the dataset

The Levelwise Discovery Approach: The algorithm operates by leveraging the downward closure property (also called the anti-monotone property): if an itemset is infrequent, then all of its supersets must also be infrequent. This allows efficient pruning of the search space by:

Generate: Create candidate itemsets of size k from frequent itemsets of size k-1
Prune: Eliminate candidates containing any infrequent subset
Count: Scan the database to compute support for remaining candidates
Filter: Retain only candidates meeting the minimum support threshold
Repeat: Continue until no new frequent itemsets are found

Your Task: Implement a function that discovers all frequent itemsets in a transaction database. The function should:

Return a dictionary mapping each frequent itemset (as a frozenset) to its support value
Include frequent itemsets of all sizes (1-itemsets, 2-itemsets, etc.) that meet the threshold
Use only Python built-in modules and standard library (collections, itertools are permitted)

Example

Input

transactions = [
    ["bread", "milk"],
    ["beer", "bread", "diaper", "eggs"],
    ["beer", "cola", "diaper", "milk"],
    ["beer", "bread", "diaper", "milk"],
    ["bread", "cola", "diaper", "milk"]
]
min_support = 0.6

Output

{
    frozenset({'bread'}): 0.8,
    frozenset({'beer'}): 0.6,
    frozenset({'milk'}): 0.8,
    frozenset({'diaper'}): 0.8,
    frozenset({'beer', 'diaper'}): 0.6,
    frozenset({'bread', 'milk'}): 0.6,
    frozenset({'diaper', 'milk'}): 0.6,
    frozenset({'bread', 'diaper'}): 0.6
}

Explanation

With 5 transactions and min_support = 0.6 (meaning an itemset must appear in at least 3 transactions):

1-itemsets: • 'bread' appears in transactions 1, 2, 4, 5 → support = 4/5 = 0.8 ✓ • 'beer' appears in transactions 2, 3, 4 → support = 3/5 = 0.6 ✓ • 'milk' appears in transactions 1, 3, 4, 5 → support = 4/5 = 0.8 ✓ • 'diaper' appears in transactions 2, 3, 4, 5 → support = 4/5 = 0.8 ✓ • 'eggs' appears only in transaction 2 → support = 1/5 = 0.2 ✗ • 'cola' appears in transactions 3, 5 → support = 2/5 = 0.4 ✗

2-itemsets (formed from frequent 1-itemsets): • {beer, diaper} appears in transactions 2, 3, 4 → support = 0.6 ✓ • {bread, milk} appears in transactions 1, 4, 5 → support = 0.6 ✓ • {diaper, milk} appears in transactions 3, 4, 5 → support = 0.6 ✓ • {bread, diaper} appears in transactions 2, 4, 5 → support = 0.6 ✓ • Other 2-itemset combinations have support < 0.6

3-itemsets: No 3-itemset achieves support ≥ 0.6, so the algorithm terminates.

Example

Input

transactions = [
    ["apple", "banana"],
    ["apple", "orange"],
    ["apple", "grape"],
    ["banana", "orange"]
]
min_support = 0.5

Output

{
    frozenset({'banana'}): 0.5,
    frozenset({'apple'}): 0.75,
    frozenset({'orange'}): 0.5
}

Explanation

With 4 transactions and min_support = 0.5 (itemset must appear in at least 2 transactions):

1-itemsets: • 'apple' appears in transactions 1, 2, 3 → support = 3/4 = 0.75 ✓ • 'banana' appears in transactions 1, 4 → support = 2/4 = 0.5 ✓ • 'orange' appears in transactions 2, 4 → support = 2/4 = 0.5 ✓ • 'grape' appears only in transaction 3 → support = 1/4 = 0.25 ✗

2-itemsets: • {apple, banana} appears only in transaction 1 → support = 0.25 ✗ • {apple, orange} appears only in transaction 2 → support = 0.25 ✗ • {banana, orange} appears only in transaction 4 → support = 0.25 ✗

No 2-itemsets or higher meet the threshold, so only 1-itemsets are returned.

Example

Input

transactions = [
    ["bread", "eggs", "milk"],
    ["bread", "butter", "milk"],
    ["bread", "cheese"],
    ["eggs", "milk"],
    ["bread", "milk"]
]
min_support = 0.8

Output

{
    frozenset({'bread'}): 0.8,
    frozenset({'milk'}): 0.8
}

Explanation

With 5 transactions and a high min_support = 0.8 (itemset must appear in at least 4 transactions):

1-itemsets: • 'bread' appears in transactions 1, 2, 3, 5 → support = 4/5 = 0.8 ✓ • 'milk' appears in transactions 1, 2, 4, 5 → support = 4/5 = 0.8 ✓ • 'eggs' appears in transactions 1, 4 → support = 2/5 = 0.4 ✗ • 'butter' appears only in transaction 2 → support = 0.2 ✗ • 'cheese' appears only in transaction 3 → support = 0.2 ✗

2-itemsets: • {bread, milk} appears in transactions 1, 2, 5 → support = 3/5 = 0.6 ✗

The high threshold eliminates all multi-item combinations, leaving only the two most common individual items.

Accepted0/0·0% Acceptance

Constraints

1 ≤ number of transactions ≤ 1000
1 ≤ items per transaction ≤ 50
0.0 < min_support ≤ 1.0
Items are represented as non-empty strings
Each transaction contains unique items (no duplicates within a single transaction)
Only use Python built-in modules and standard library (collections, itertools permitted)

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

min_support =

0.6

transactions =

[["bread","milk"],["beer","bread","diaper","eggs"],["beer","cola","diaper","milk"],["beer","bread","diaper","milk"],["bread","cola","diaper","milk"]]

Loading problem...

101

00:00:00

Description

Editorial

Frequent Pattern Discovery in Transaction Data

MEDIUM20 pts

$$\text{support}(X) = \frac{|{T \in D : X \subseteq T}|}{|D|}$$

Where:

X is the itemset being evaluated
D is the collection of all transactions
T represents individual transactions in the dataset

Generate: Create candidate itemsets of size k from frequent itemsets of size k-1
Prune: Eliminate candidates containing any infrequent subset
Count: Scan the database to compute support for remaining candidates
Filter: Retain only candidates meeting the minimum support threshold
Repeat: Continue until no new frequent itemsets are found

Your Task: Implement a function that discovers all frequent itemsets in a transaction database. The function should:

Return a dictionary mapping each frequent itemset (as a frozenset) to its support value
Include frequent itemsets of all sizes (1-itemsets, 2-itemsets, etc.) that meet the threshold
Use only Python built-in modules and standard library (collections, itertools are permitted)

Example

Input

transactions = [
    ["bread", "milk"],
    ["beer", "bread", "diaper", "eggs"],
    ["beer", "cola", "diaper", "milk"],
    ["beer", "bread", "diaper", "milk"],
    ["bread", "cola", "diaper", "milk"]
]
min_support = 0.6

Output

{
    frozenset({'bread'}): 0.8,
    frozenset({'beer'}): 0.6,
    frozenset({'milk'}): 0.8,
    frozenset({'diaper'}): 0.8,
    frozenset({'beer', 'diaper'}): 0.6,
    frozenset({'bread', 'milk'}): 0.6,
    frozenset({'diaper', 'milk'}): 0.6,
    frozenset({'bread', 'diaper'}): 0.6
}

Explanation

With 5 transactions and min_support = 0.6 (meaning an itemset must appear in at least 3 transactions):

3-itemsets: No 3-itemset achieves support ≥ 0.6, so the algorithm terminates.

Example

Input

transactions = [
    ["apple", "banana"],
    ["apple", "orange"],
    ["apple", "grape"],
    ["banana", "orange"]
]
min_support = 0.5

Output

{
    frozenset({'banana'}): 0.5,
    frozenset({'apple'}): 0.75,
    frozenset({'orange'}): 0.5
}

Explanation

With 4 transactions and min_support = 0.5 (itemset must appear in at least 2 transactions):

No 2-itemsets or higher meet the threshold, so only 1-itemsets are returned.

Example

Input

transactions = [
    ["bread", "eggs", "milk"],
    ["bread", "butter", "milk"],
    ["bread", "cheese"],
    ["eggs", "milk"],
    ["bread", "milk"]
]
min_support = 0.8

Output

{
    frozenset({'bread'}): 0.8,
    frozenset({'milk'}): 0.8
}

Explanation

With 5 transactions and a high min_support = 0.8 (itemset must appear in at least 4 transactions):

2-itemsets: • {bread, milk} appears in transactions 1, 2, 5 → support = 3/5 = 0.6 ✗

The high threshold eliminates all multi-item combinations, leaving only the two most common individual items.

Accepted0/0·0% Acceptance

Constraints

1 ≤ number of transactions ≤ 1000
1 ≤ items per transaction ≤ 50
0.0 < min_support ≤ 1.0
Items are represented as non-empty strings
Each transaction contains unique items (no duplicates within a single transaction)
Only use Python built-in modules and standard library (collections, itertools permitted)

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

min_support =

0.6

transactions =

[["bread","milk"],["beer","bread","diaper","eggs"],["beer","cola","diaper","milk"],["beer","bread","diaper","milk"],["bread","cola","diaper","milk"]]

Frequent Pattern Discovery in Transaction Data

Hints

Frequent Pattern Discovery in Transaction Data

Hints