Question

1. Apply the Apriori Algorithm 

Tasks: 

Apply the Apriori Algorithm to the following data set: 

Trans ID Items Purchased 

101 milk, bread, eggs 

102 milk, juice 

103 juice, butter 

104 milk, bread, eggs 

105 coffee, eggs 

106 coffee 

107 coffee, juice 

108 milk, bread, cookies, eggs 

109 cookies, butter 

110 milk, bread 

The set of items is {milk, bread, cookies, eggs, butter, coffee, juice). Use 2 for the minimum support value. You must show all candidate and large itemsets during the process: C., L, C2, L2 etc. until the algorithm terminates.

Answer 1

Sol)

Given minimal support value = 2

Step1 :- K=1

Create a table which contains the support count of each item present in the dataset. gives candidate set of length 1, called C1.

C1 :

Itemset	Sup_count
milk	5
bread	4
eggs	4
juice	3
butter	2
coffee	3
cookies	2

compare the support count of each itemset of C1 with minimum support count('2' in our case), if candidate itemset support count is less than minimum support count remove those itemsets, which gives frequent itemsets of length 1, called L1.

No itemset from C1 have support count less than minimum support count. so

L1 :

Itemset	Sup_count
milk	5
bread	4
eggs	4
juice	3
butter	2
coffee	3
cookies	2

Step 2 :- K=2

To generate candidate set of length 2(C2), we have to join L1 with L1. Condition for joining L_k-1, L_k-1 is, it should have (K-2) elements in common(here K=2, no need of elements to be common in this case)

check whether all the subsets of itemsets are frequent or not(Apriori property), if not we remove those itemsets.

then, find the support count of the itemsets by searching in the dataset.

C2 :

Itemset	Sup_count
{milk, bread}	4
{milk, eggs}	3
{milk, juice}	1
{milk, butter}	0
{milk, coffee}	0
{milk, cookies}	1
{bread, eggs}	3
{bread, juice}	0
{bread, butter}	0
{bread, coffee}	0
{bread, cookies}	1
{eggs, juice}	0
{eggs, butter}	0
{eggs, coffee}	1
{eggs, cookies}	1
{juice, butter}	1
{juice, coffee}	1
{juice, cookies}	0
{butter, coffee}	0
{butter, cookies}	1
{coffee, cookies}	0

Now, compare the support count of itemsets from C2 with minimum support count(2) and remove those itemsets which have support count lesser than minimum support count. which gives frequent itemsets of length 2, called L2

L2:

Itemset	Sup_count
{milk, bread}	4
{milk, eggs}	3
{bread, eggs}	3

Step 3:- K=3

To generate candidate set of length 3(C3), join L2 with L2, Condition for joining L_k-1, L_k-1 is it should have (K-2) elements in common(here 3-2 =1, so here, first element should match).

{milk, bread, eggs} (milk has matched between first two itemsets of L2)

then check the apriori property for itemsets came from previous step, that is whether all the subsets of frequent itemset should be frequent, if not remove those itemsets.

In {milk, bread, eggs}, every subset {milk, bread}, {milk, eggs}, {bread, eggs} is frequent.

then, count the support count of itemsets by searching in the dataset.
C3 :

Itemset	Sup_count
{milk, bread, eggs}	3

compare the support count of itemsets of C2 with minimum support count and remove those itemsets which have support count lesser than minimum support count, gives frequent itemsets of length 3, called L3

C3 have only one itemset with more than minimum support count, so

L3 :

Itemset	Sup_count
{milk, bread, eggs}	3

Algorithm stops here, no frequent itemsets are found further.