Maximal & Closed Itemsets

Source: Unit 4 §7

The set of frequent itemsets is usually far larger than anyone wants to read. These are the two standard compact representations of it.

Maximal frequent itemset

An itemset is MAXIMAL frequent if none of its immediate supersets is frequent.

Picture the frequent itemsets as everything below a border in the lattice: the maximal ones sit exactly on that border. If {A,B,C,D} is frequent but {A,B,C,D,E} is not, then {A,B,C,D} is maximal.

Closed itemset

An itemset is CLOSED if none of its immediate supersets has the SAME support as the itemset.

Example: if {A,B} has support 4 and its superset {A,B,C} has support 2 - a different number - then {A,B} may be closed. If some superset had the same support, {A,B} would not be closed, because that superset carries all the same information for free.

The relationship

Both are lossless enough to regenerate the frequent itemsets; only the closed set can also regenerate their supports.

	Condition	Retains support info?
Maximal	no immediate superset is frequent	No - it loses the exact supports
Closed	no immediate superset has the same support	Yes - it preserves the supports

◎Exam cueTelling the two definitions apart

Maximal asks a question about frequency ("is any superset frequent?"). Closed asks a question about support ("does any superset have the same support?"). Every maximal frequent itemset is closed, so Maximal ⊆ Closed ⊆ Frequent.