Objectives
The objectives of this section are:
to explain the problem of frequent itemset generation
to introduce the main strategies for solving this problem
to explain the Apriori Principle
to explain the the Apriori Algorithm
Outcomes
By the time you have completed this section you will be able to:
list the main strategies for solving the frequent itemset generation problem
describe the Apriori Principle
explain the major steps of the Apriori Algorithm
The Apriori Algorithm
This algorithm uses the Apriori principle mentioned on the previous page in an iterative approach known as a level-wise to reduce the number of itemsets that we have to count their support.
Here’s the general idea, we use k-itemsets to explore (k+1)-itemsets.
- We first find the set of frequent 1-itemsets, Lk:- this is done by scanning the database and accumulating the count for each item and then keeping those that meet the minimum support in a new set called Lk.
- Then we use Lk to find Ck+1 (the set of candidate 2-itemsets):- This is a two step process that
first generates Ck+1 based on Lk and then
secondly prunes Ck+1 by getting rid of those Ck+1 itemsets using the Apriori principle. - We find Lk+1: we do this by finding the support count for all the itemsets in Ck+1 and getting rid of those that are below the minsup.
- We continue step 2&3 until no new frequent (k+1)-itemset are found.
Apriori Generator Application
It is one thing to explain the concepts, it is quite another to see it in action. To get a hands on understanding of how this algorithm works click the link below to download an application that will allow you to build a decision tree for a particular dataset based on these measures. For instructions on how to use the Apriori Generator Application consult Help Section 5.
