Mining Frequent Patterns in Data Mining

Frequent itemsets, the Apriori and FP-Growth algorithms that find them, and sequential pattern mining (order-sensitive patterns, covered with a hand-verified worked example in the lesson on association analysis in data mining) are each covered in depth elsewhere in this series. This lesson covers a distinction that matters once frequent-pattern mining is run on real data: a dataset can easily produce thousands of frequent itemsets, most of which are redundant with each other, and closed and maximal itemsets are the two standard ways of keeping only the ones that add information.

The Dataset Used Throughout This Lesson

Four transactions, and a minimum support threshold of 2 (out of 4 transactions, i.e., 50%):

T1: A, B, C
T2: A, B, C
T3: A, B
T4: A

Counting every itemset's support:

{A}     = 4   (T1, T2, T3, T4)
{B}     = 3   (T1, T2, T3)
{C}     = 2   (T1, T2)
{A,B}   = 3   (T1, T2, T3)
{A,C}   = 2   (T1, T2)
{B,C}   = 2   (T1, T2)
{A,B,C} = 2   (T1, T2)

Every one of these seven itemsets meets the minimum support of 2, so all seven are frequent — which is exactly the problem: on a real dataset with dozens of items, this kind of full listing can run into the thousands, and most of it turns out to be redundant.

Closed Itemsets: Lossless Compression of the Frequent-Itemset List

An itemset is closed if none of its immediate supersets has the exact same support — in other words, adding any item to it strictly reduces how many transactions still match. Checking each itemset above:

{A}=4:     superset {A,B}=3, {A,C}=2 -> both lower than 4 -> {A} IS closed
{B}=3:     superset {A,B}=3          -> same as {B}       -> {B} is NOT closed
{C}=2:     superset {A,C}=2, {B,C}=2 -> both same as {C}  -> {C} is NOT closed
{A,B}=3:   superset {A,B,C}=2        -> lower than 3       -> {A,B} IS closed
{A,C}=2:   superset {A,B,C}=2        -> same as {A,C}     -> {A,C} is NOT closed
{B,C}=2:   superset {A,B,C}=2        -> same as {B,C}     -> {B,C} is NOT closed
{A,B,C}=2: no superset exists         -> {A,B,C} IS closed (by definition)

Three closed itemsets survive: {A}:4, {A,B}:3, and {A,B,C}:2. These three are enough to reconstruct the exact support of every one of the seven original itemsets — for instance, {B}'s true support (3) is recovered by finding the smallest closed itemset containing B, which is {A,B}:3; {C}'s true support (2) is recovered the same way from {A,B,C}:2. Closed itemsets compress the result without losing any support information — nothing else needs to be stored to answer "what's the support of any frequent itemset?"

Maximal Itemsets: Maximum Compression, at the Cost of Exact Counts

An itemset is maximal if it is frequent and no frequent superset of it exists at all — a much stricter condition than being closed. Here, {A,B,C} (support 2) is frequent and has no superset to check against, so it is maximal. Every other itemset in this dataset — {A}, {B}, {C}, {A,B}, {A,C}, {B,C} — has {A,B,C} as a frequent superset, which immediately disqualifies all of them from being maximal. The result: exactly one maximal itemset, versus three closed itemsets and seven frequent itemsets total. Maximal itemsets tell you the largest frequent combinations that exist, which is often all a business question actually needs ("what's the biggest bundle of products people reliably buy together?"), but they throw away exact counts for every smaller itemset along the way — knowing {A,B,C} is maximal with support 2 tells you nothing about whether {A,B} occurred 3 times or 2.5 million times, only that it occurred at least as often as {A,B,C} did.

Choosing Between the Two

Real implementations of Apriori and FP-Growth, covered in their own dedicated lessons, can be configured to mine closed or maximal itemsets directly rather than generating every frequent itemset and filtering afterward, which is precisely the efficiency gain that matters once a dataset is large enough to produce frequent itemsets by the thousands.