Apriori Algorithm

Today we are going to learn about Apriori Algorithm. Before we start with that we need to know a little bit about Data Mining.

What is Data Mining ?

Data Mining is a non-trivial process of identifying valid, novel, potentially useful and ultimately understandable patterns in data.

Apriori Algorithm is concerned with Data Mining and it helps us to predict information based on previous data.

In many e-commerce websites we see a recently bought together feature or the suggestion feature after purchasing or searching for a particular item, these suggestions are based on previous purchase of that item and Apriori Algorithm can be used to make such suggestions.

Before we start with Apriori we need to understand a few simple terms :

Association Mining: It is finding different association in our data.

For E.g. If you are buying butter then there is a great chance that you will buy bread too so there is an association between bread and butter here.

Support: It specifies how many of the total transactions contain these items.

Support(A->B) denotes how many transactions have all items from AUB

Therefore

Support(A->B) = P(AUB)
Support(A->B) = support(B->A)

Therefore 10% support will mean that 10% of all the transactions contain all the items in AUB.

Confidence: For a transaction A->B Confidence is the number of time B is occuring when A has occurred.

Note that Confidence of A->B will be different than confidence of B->A.

Confidence(A->B) = P(AUB)/P(A).

Support_Count(A): The number of transactions in which A appears.

An itemset having number of items greater than support count is said to be frequent itemset.

Apriori algorithm is used to find frequent itemset in a database of different transactions with some minimal support count. Apriori algorithm prior knowledge to do the same, therefore the name Apriori. It states that

All subsets of a frequent itemset must be frequent.

If an itemset is infrequent, all its supersets will be infrequent.

Let’s go through an example :

Transaction ID	Items
1	I1 I3 I4
2	I2 I3 I5
3	I1 I2 I3 I5
4	I2 I5

We will first find Candidate set (denoted by C_i) which is the count of that item in Transactions.

C₁:

Items	Support Count
I1	2
I2	3
I3	3
I4	1
I5	3

The items whose support count is greater than or equal to a particular min support count are included in L set

Let’s say support count for above problem be 2

L₁:

Items	Support Count
I1	2
I2	3
I3	3
I5	3

Next is the joining step we will combine the different element in L₁in order to form C₂ which is candidate of size 2 then again we will go through the database and find the count of transactions having all the items. We will continue this process till we find a L set having no elements.

C₂:

Items	Support Count
I1,I2	1
I1,I3	2
I1,I5	1
I2,I3	2
I2,I5	3
I3,I5	2

We will remove sets which have count less than min support count and form L₂

L₂:

Items	Support Count
I1,I3	2
I2,I3	2
I2,I5	3
I3,I5	2

Now we will join L₂ to form C₃

Note that we cannot combine {I1,I3} and {I2,I5} because then the set will contain 4 elements. The rule here is the there should be only one element in both set which are distinct all other elements should be the same.

C₃:

Items	Support Count
I1,I2,I3	1
I1,I3,I5	1
I2,I3,I5	2

L_3:

Item	Support Count
I2,I3,I5	2

Now we cannot form C₄ therefore the algorithm will terminate here.

Now we have to calculate the strong association rules. The rules having a minimum confidence are said to be strong association rules.

Suppose for this example the minimum confidence be 75%.

There can be three candidates for strong association rules.

I2^I3->I5 = support(I2^I3)/support(I5) = ⅔ = 66.66%

I3^I5->I2 = support(I3^I5)/support(I2) = ⅔ = 66.66%

I2^I5->I3 = support(I2^I5)/support(I3) = 3/3 = 100%

So in this example the strong association rule is

I2^I5->I3.

So from the above example we can draw conclusion that if someone is buying I2 and I5 then he/she is most likely to buy I3 too. This is used to make suggestions while we are purchasing online.

The Algorithm to calculate the frequent itemset is as below:

Ck : Candidate Set of size k
Lk : Frequent set of size k
min_sup : Minimum support count
T : Database

For all transactions t in T :
do
	Go through the items in t 
		If item already present in set C1 then increase count
		else insert item in C1 with count 1
end

For all items I in C
do
	If count of I > min_sup
		L1 ← Item in C1
end

for(k=1 ; Lk!=ɸ ; k++)
do	
	Ck+1 ← Candidates generated from Lk
	
	for all transactions t in T 
	do
		if Ck+1 a subset of t 
			increase count of Ck+1
end	
	
For all items I in C
	do
	If count of I > min_sup
			Lk+1 ← Item in Ck
	end
end

Ck : Candidate Set of size k

Lk : Frequent set of size k

min_sup : Minimum support count

T : Database

For all transactions t in T :

Go through the items in t

If item already present in set C1 then increase count

else insert item in C1 with count 1

end

For all items I in C

If count of I > min_sup

L1 ← Item in C1

end

for(k=1 ; Lk!=ɸ ; k++)

Ck+1 ← Candidates generated from Lk

for all transactions t in T

if Ck+1 a subset of t

increase count of Ck+1

end

For all items I in C

If count of I > min_sup

Lk+1 ← Item in Ck

end

Comment down below if you have any queries related to Apriori Algorithm.

Related Posts

Leave a Comment Cancel Reply