Problem Introduction

Abstract:

• A set of items {1,2,…,k}

• A dabase of transactions (itemsets) D={T1, T2, …, Tn},
  Tj subset {1,2,…,k}

GOAL:

Find all itemsets that appear in at least x transactions

(“appear in” == “are subsets of”)

I subset T: T supports I

For an itemset I, the number of transactions it appears in is called the support of I.

x is called the minimum support.

Concrete:

• I = {milk, bread, cheese, …}

• D = { {milk,bread,cheese}, {bread,cheese,juice}, …}

GOAL:

Find all itemsets that appear in at least 1000 transactions

{milk,bread,cheese} supports {milk,bread}