Informal Problem Introduction (Contd.)

Definitions:

• An itemset is frequent if it is a subset of at least x transactions. (FI.)

• An itemset is maximally frequent if it is frequent and it does not have a frequent superset. (MFI.)

GOAL: Given x, find all maximally frequent itemsets (to be stored in the MFI).

Obvious relationship:
FI subset MFI

Example:

D={ {1,2,3}, {1,2,3}, {1,2,3}, {1,2,4} }

Minimum support x = 3

{1,2} is frequent

{1,2,3} is maximal frequent

Support({1,2}) = 4

All maximal frequent itemsets: {1,2,3}