The Apriori Algorithm

here are just notes from my data mining class which i began to consolidate here in my blog as a way to assimilate the lessons.

the apriori algorithm is a basic method for finding frequent itemsets. the latter is used to generate association rules with high confidence and high interest.

here is my summary of it along with a running example. the following set of baskets will be used:

d = [ ('milk', 'cheese', 'tuna'),
      ('cheese', 'mushroom'),
      ('cheese', 'eggs'),
      ('milk', 'cheese', 'mushroom'),
      ('milk', 'eggs'),
      ('cheese', 'eggs'),
      ('milk', 'cheese', 'mushroom', 'tuna'), 
      ('milk', 'cheese', 'eggs') ]

some definitions:

– is the universal set of items. in the example above, the universal set would be {milk, cheese, tuna, mushroom, eggs}.

– is like a k-combination of . like because items in this set should have frequent (k-1, k-2,…1)-itemsets.

now, the apriori algorithm.

1. generate by cross joining the itemsets of among themselves.

cross joining two sets

a cross join between two k-item sets is a union of those two sets which results in a k+1 itemset. however, the join only happens if and only if the first k-1 items of both sets are equal.

for example:

no join

if , simply list all 1 itemsets.

one_itemset = ['milk', 'cheese', 'eggs', 'mushroom', 'tuna']

2. generate , the frequent itsemsets by counting the number of times each element in occurs in . if an element in or the support threshold, it is qualified to be a member of . for and our example above for is

c1 = {'cheese': 7, 
      'tuna': 2, 
      'eggs': 6, 
      'mushroom': 2, 
      'milk': 6}

3. repeat the process for until no frequent itemsets are found.