Apriori Algorithm in Data Mining
Overview
The Apriori algorithm in data mining is a popular algorithm used for finding frequent
itemsets in a dataset. It is widely used in association rule mining to discover
relationships between items in a dataset. The Apriori algorithm was developed by R.
Agrawal and R. Srikant in 1994.
Introduction to Apriori Algorithm
The Apriori algorithm is called "apriori" because it uses prior knowledge about
the frequent itemsets.
The Apriori algorithm in data mining is a widely used algorithm to find frequent
itemsets in a dataset.
The Apriori algorithm is used to implement frequent pattern mining (FPM).
Frequent pattern mining is a data mining technique to discover frequent
patterns or relationships between items in a dataset.
Frequent pattern mining involves finding sets of items or itemsets that occur
together frequently in a dataset. These sets of items or itemsets are called
frequent patterns, and their frequency is measured by the number of
transactions in which they occur.
In data mining, an itemset is a collection of one or more items that appear
together in a transaction or dataset. An itemset can be either a single item, also
known as a 1-itemset, or a set of k items, also known as a k-itemset.
For example, in sales transactions of a retail store, an itemset can be referred
to as products purchased together, such as bread and milk, which would be a 2-
item set. The Apriori algorithm can be used to discover frequent itemsets in the
sales transactions of a retail store. For instance, the algorithm might discover
that customers who purchase bread and milk together often also purchase eggs.
This information can be used to recommend eggs to customers who purchase
bread and milk in the future.
The algorithm uses the concept of "apriori property," which states that if an
itemset is frequent, then all of its subsets must also be frequent.
Apriori Property
The Apriori property is a fundamental property of frequent itemsets used in the
Apriori algorithm. In other words, if an itemset appears frequently enough in the
dataset to be considered significant, then all of its subsets must also appear frequently
enough to be significant.
For example, if the itemset {A, B, C} frequently appears in a dataset, then the subsets
{A, B}, {A, C}, {B, C}, {A}, {B}, and {C} must also appear frequently in the dataset.
The Apriori property allows the Apriori algorithm in data mining to efficiently search
for frequent itemsets by eliminating candidate itemsets containing infrequent subsets,
as they cannot be frequent. This search space pruning reduces the time and memory
required to find frequent itemsets in large datasets.
Apriori Algorithm Components
Before getting into the steps involved in the Apriori algorithm, let’s understand the
various terminologies used in the Apriori algorithm.
Support In the Apriori algorithm, support refers to the frequency or occurrence of
an item set in a dataset. It is defined as the proportion of transactions in the dataset
that contain the itemset.
For example, let's consider a dataset of sales transactions in a retail store that
contains the following items - milk, bread, cheese, eggs, butter, and yogurt.
To calculate the support of an itemset, we count the number of transactions in which
the itemset appears and divide it by the total number of transactions in the dataset.
For instance, if the itemset {milk, bread} appears in 5 transactions out
of 10 transactions in the dataset, then its support is 5/10=0.55/10=0.5, or 50%.
In the Apriori algorithm, itemsets with a support value above the minimum defined
support threshold are considered frequent and are used to generate candidate
itemsets for the next iteration of the algorithm.
Lift Lift measures the strength of the association between two items. It is defined
as the ratio of the support of the two items occurring together to the support of the
individual items multiplied together. Lift for any two items can be calculated using the
below formula -
Lift(A→B)=Support(A)∗Support(B)Support(A and B)
If the lift value is greater than 1, then it indicates a positive association between the
two items, which means that the two items are more likely to be bought together. A lift
value of exactly 1 indicates that the two items are independent and there is no
association between the two items, while a value less than 1 indicates a negative
association, meaning that two items are more likely to be bought separately.
Confidence In the Apriori algorithm, confidence is also a measure of the strength
of the association between two items in an itemset. It is defined as the conditional
probability that item B appears in a transaction, given that another item A appears in
the same transaction. Support for two items can be calculated using the below formula.
confidence(A⇒B)=P(B/A)=sup(A)sup(A∪B)
If the confidence value exceeds a specified threshold, it indicates that item B is likely
to be purchased with item A. For instance, if the confidence of the association between
"bread" and "butter" is 0.8, it means that when a customer buys "bread", there is
an 80% chance that they will also buy "butter". This can be useful in recommending to
customers or optimizing product placement in a store.
Steps in Apriori Algorithm
Here are the steps involved in implementing the Apriori algorithm in data mining -
1. Define minimum support threshold - This is the minimum number of times an
item set must appear in the dataset to be considered as frequent. The support
threshold is usually set by the user based on the size of the dataset and the
domain knowledge.
2. Generate a list of frequent 1-item sets - Scan the entire dataset to identify
the items that meet the minimum support threshold. These item sets are known
as frequent 1-item sets.
3. Generate candidate item sets - In this step, the algorithm generates a list of
candidate item sets of length k+1 from the frequent k-item sets identified in
the previous step.
4. Count the support of each candidate item set - Scan the dataset again to
count the number of times each candidate item set appears in the dataset.
5. Prune the candidate item sets - Remove the item sets that do not meet the
minimum support threshold.
6. Repeat steps 3-5 until no more frequent item sets can be generated.
7. Generate association rules - Once the frequent item sets have been identified,
the algorithm generates association rules from them. Association rules are rules
of form A -> B, where A and B are item sets. The rule indicates that if a
transaction contains A, it is also likely to contain B.
8. Evaluate the association rules - Finally, the association rules are evaluated
based on metrics such as confidence and lift.
Apriori Algorithm Example - 1
Let’s try to understand the Apriori algorithm implementation using an example. In this
example, we will use a minimum support threshold of 3. This means an item set must
appear in at least three transactions to be considered frequent.
Let’s consider the transaction dataset of a retail store as shown in the
below table.
Let’s calculate support for each item present in the dataset. As shown in the
below table, support for all items is greater than 3. It means that all items are
considered as frequent 1-itemsets and will be used to generate candidates for
2-itemsets.
Below table represents all candidates generated from frequent 1-itemsets
identified from the previous step and their support value.
Now remove candidate item sets that do not meet the minimum support
threshold of 3. After this step, frequent 2-itemsets would be - {milk, bread},
{milk, sugar}, {milk, butter}, and {bread, butter}. In the next step, let’s generate
candidates for 3-itemsets and calculate their respective support values. It is
shown in the below table.
As we can see in the above table, only one candidate itemset exceeds the
minimum defined support threshold - {milk, bread, butter}. As there is only one
3-itemset exceeding minimum support, we can’t generate candidates for 4-
itemsets. So, in the next step, we can write the association rules and their
respective metrics, as shown in the below table.
Based on association rules mentioned in the above table, we can recommend
products to the customer or optimize product placement in retail stores.
Advantages and Limitations of Apriori Algorithm
Apriori algorithm is simple and easy to implement, making it accessible even to
those without a deep understanding of data mining or machine learning.
Apriori algorithm can handle large datasets and run on distributed systems,
making it scalable for large-scale applications.
Apriori algorithm is one of the most widely used algorithms for association rule
mining and is supported by many popular data mining tools.
Below are some of the limitations of the Apriori algorithm in data mining -
Apriori algorithm can be computationally expensive, especially for large datasets
with many itemsets. For example, if a dataset contains 104104 from frequent 1-
itemsets, it will generate more than 107107 2-length candidates, which makes
this algorithm computationally expensive.
Apriori algorithm can generate a large number of rules, making it difficult to
sift through and identify the most important ones.
The algorithm requires multiple database scans to generate frequent itemsets,
which can be a limitation in systems where data access is slow or expensive.
Apriori algorithm is sensitive to data sparsity, meaning it may not perform well
on datasets with a low frequency of itemsets.
-----------------------------------------------------------------------------------------------
Apriori Algorithm Example - 2
Consider the following dataset and we will find frequent itemsets and generate
association rules for them.
minimum support count is 2
minimum confidence is 60%
Step-1: K=1
(I) Create a table containing support count of each item present in dataset –
Called C1(candidate set)
(II) compare candidate set item’s support count with minimum support count(here
min_support=2 if support_count of candidate set items is less than min_support then
remove those items). This gives us itemset L1.
Step-2: K=2
Generate candidate set C2 using L1 (this is called join step). Condition of joining Lk-
1 and Lk-1 is that it should have (K-2) elements in common.
Check all subsets of an itemset are frequent or not and if not frequent remove
that itemset.(Example subset of{I1, I2} are {I1}, {I2} they are [Link] for
each itemset)
Now find support count of these itemsets by searching in dataset.
(II) compare candidate (C2) support count with minimum support count(here
min_support=2 if support_count of candidate set item is less than min_support then
remove those items) this gives us itemset L2.
Step-3:
o Generate candidate set C3 using L2 (join step). Condition of joining Lk-1 and
Lk-1 is that it should have (K-2) elements in common. So here, for L2, first
element should match.
So itemset generated by joining L2 is {I1, I2, I3}{I1, I2, I5}{I1, I3, i5}{I2,
I3, I4}{I2, I4, I5}{I2, I3, I5}
o Check if all subsets of these itemsets are frequent or not and if not, then
remove that itemset.(Here subset of {I1, I2, I3} are {I1, I2},{I2, I3},{I1,
I3} which are frequent. For {I2, I3, I4}, subset {I3, I4} is not frequent so
remove it. Similarly check for every itemset)
o find support count of these remaining itemset by searching in dataset.
(II) Compare candidate (C3) support count with minimum support count(here
min_support=2 if support_count of candidate set item is less than min_support then
remove those items) this gives us itemset L3.
Step-4:
o Generate candidate set C4 using L3 (join step). Condition of joining Lk-1 and
Lk-1 (K=4) is that, they should have (K-2) elements in common. So here, for
L3, first 2 elements (items) should match.
o Check all subsets of these itemsets are frequent or not (Here itemset
formed by joining L3 is {I1, I2, I3, I5} so its subset contains {I1, I3, I5},
which is not frequent). So no itemset in C4
o We stop here because no frequent itemsets are found further
Thus, we have discovered all the frequent item-sets. Now generation of strong
association rule comes into picture. For that we need to calculate confidence of each
rule.
Confidence –
A confidence of 60% means that 60% of the customers, who purchased milk and
bread also bought butter.
Confidence(A->B)=Support_count(A∪B)/Support_count(A)
So here, by taking an example of any frequent itemset, we will show the rule
generation.
Itemset {I1, I2, I3} //from L3
SO rules can be
[I1^I2]=>[I3] //confidence = sup(I1^I2^I3)/sup(I1^I2) = 2/4*100=50%
[I1^I3]=>[I2] //confidence = sup(I1^I2^I3)/sup(I1^I3) = 2/4*100=50%
[I2^I3]=>[I1] //confidence = sup(I1^I2^I3)/sup(I2^I3) = 2/4*100=50%
[I1]=>[I2^I3] //confidence = sup(I1^I2^I3)/sup(I1) = 2/6*100=33%
[I2]=>[I1^I3] //confidence = sup(I1^I2^I3)/sup(I2) = 2/7*100=28%
[I3]=>[I1^I2] //confidence = sup(I1^I2^I3)/sup(I3) = 2/6*100=33%
So if minimum confidence is 50%, then first 3 rules can be considered as strong
association rules.
Limitations of Apriori Algorithm
Apriori Algorithm can be slow.
The main limitation is time required to hold a vast number of candidate sets
with much frequent itemsets, low minimum support or large itemsets i.e. it is
not an efficient approach for large number of datasets.
For example, if there are 10^4 from frequent 1- itemsets, it need to generate
more than 10^7 candidates into 2-length which in turn they will be tested and
accumulate. Furthermore, to detect frequent pattern in size 100 i.e. v1, v2…
v100, it have to generate 2^100 candidate itemsets that yield on costly and
wasting of time of candidate generation. So, it will check for many sets from
candidate itemsets, also it will scan database many times repeatedly for
finding candidate itemsets.
Apriori will be very low and inefficiency when memory capacity is limited with
large number of transactions.
--------------------* ---------* ---------*------------------------------
How does the Apriori Algorithm work in Data Mining?
We will understand this algorithm with the help of an example
Consider a Big Bazar scenario where the product set is P = {Rice, Pulse, Oil, Milk,
Apple}. The database comprises six transactions where 1 represents the presence of
the product and 0 represents the absence of the product.
Apple
Transaction ID Rice Pulse Oil Milk
t1 1 1 1 0 0
t2 0 1 1 1 0
t3 0 0 0 1 1
t4 1 1 0 1 0
t5 1 1 1 0 1
t6 1 1 1 1 1
The Apriori Algorithm makes the given assumptions
o All subsets of a frequent itemset must be frequent.
o The subsets of an infrequent item set must be infrequent.
o Fix a threshold support level. In our case, we have fixed it at 50 percent.
Step 1
Make a frequency table of all the products that appear in all the transactions. Now,
short the frequency table to add only those products with a threshold support level of
over 50 percent. We find the given frequency table.
Product Frequency (Number of
transactions)
Rice (R) 4
Pulse(P)
Oil(O) 4
Milk(M) 4
The above table indicated the products frequently bought by the customers.
Step 2
Create pairs of products such as RP, RO, RM, PO, PM, OM. You will get the given
frequency table.
Itemset Frequency
(Number of
transactions)
RP 4
RO 3
RM 2
PO 4
PM 3
OM 2
Step 3
Implementing the same threshold support of 50 percent and consider the products
that are more than 50 percent. In our case, it is more than 3
Thus, we get RP, RO, PO, and PM
Step 4
Now, look for a set of three products that the customers buy together. We get the
given combination.
1. RP and RO give RPO
2. PO and PM give POM
Step 5
Calculate the frequency of the two itemsets, and you will get the given frequency table.
Itemset Frequency
(Number of
transactions)
RPO 4
POM 3
If you implement the threshold assumption, you can figure out that the customers' set
of three products is RPO. //