Market Basket Analysis: Association Rule Mining

Have you ever walked into a supermarket and realized that all the items that go together are placed nearby? Or that they are placed so far away that you end up buying other items that you did not intend to in the walk between? Well, this is not a mere coincidence or lack of organization. Infact, these arrangements were made based on the data generated from transactions performed by thousands of customers like you! This technique, called Market Basket Analysis, is often used by supermarkets to decide on item arrangement, combo discount offers, and many such lucrative schemes to increase their sales.

In this beginner-friendly no-math tutorial, we will explore one of the main processes of Market Basket Analysis: Association Rule Mining. Let’s begin!

The first step in Association Rule Mining is to Find Frequent Itemsets. Let’s understand this step with the help of an example.

Here is a list of 12 sales transactions.

As we can see, 6 items are being sold- Milk, Bread, Butter, Egg, Cookies, and Ketchup.

Introducing Support- the count of all the transactions having a particular item. For example, the item Milk is purchased in transactions 1, 2, 4, 6, 7, 8, 10, 11, and 12. Hence, the support of Milk is 9. Support can also be represented as a percentage- for example, support of Milk is 9/12 = 75%, where 12 is the total number of transactions. Simple, isn’t it?

Here is a consolidated list of items and their support:

A new terminology has been introduced in the above image- Itemset. An itemset is basically a group of items. In the above image, the size of the itemset is 1 since it contains only 1 Item.

A simple analysis can also be made from the above itemsets- that some itemsets are more popular than others. However, what is the minimum support that defines popularity? That is defined by a person known as the Subject Matter Expert. The Subject Matter Expert is someone who has extensive business knowledge and experience.

Let’s suppose that the Subject Matter Expert has defined the minimum support to be 33%. Hence, the minimum support for an itemset to be called popular or Frequent is 33% of 12, which is 4. Here, 12 is the total number of transactions.

Having the minimum support defined, let’s see which of the above itemsets of size 1 are frequent.

As we can see, out of 6 itemsets, only 4 have support more than the minimum defined, and hence can be called frequent.

Now that we have found out the frequent itemsets of size 1, let’s move on and find itemsets of size 2. To do this, we generate all possible combinations from the list of frequent itemsets of size 1.

Having generated itemsets of size 2, let’s find out the frequent itemsets and discard the others for further analysis. To do this, we calculate the support for each itemset, by counting the number of transactions in which both the items have occurred together. Remember, the minimum support defined by the Subject Matter Expert was 33%, which is 4.

As we can see, out of 6 itemsets, only 4 have support more than the minimum defined, and hence can be called frequent.

Now that we have found itemsets of size 2, let’s move on and find itemsets of size 3. To do this, we generate all possible combinations from the list of frequent itemsets of size 2.

Having generated itemsets of size 3, let’s find out the frequent itemsets and discard the others for further analysis. To do this, we calculate the support for each itemset, by counting the number of transactions in which all the three items have occurred together. Remember, the minimum support defined by the Subject Matter Expert was 33%, which is 4.

As we can see, out of 3 itemsets, only 1 has support more than the minimum defined, and hence can be called frequent.

Now since we have only 1 itemset of size 3 having support more than the minimum defined, we cannot form itemsets of larger sizes. Hence, we move on to the next step in Association Rule Mining.

The next step in the process of Association Rule Mining is Generating Association Rules from the Frequent Itemsets. Let’s understand this with the help of the same example that we have previously discussed.

Here is the largest frequent itemset that we found as a result of our analysis in the previous step:

Frequent Itemsets of Size 3

Our interpretation from the above image is that the items Milk, Bread, and Butter are bought together 6 times out of 12. However, how do we determine the order of purchase? That is, does buying Bread and Butter imply that the person will also buy Milk? Or does buying Bread and Milk imply that the person will also buy Butter? To know this, we generate and analyze association rules.

From these itemsets, we have formed the following association rules:

The above image introduces us to three terminologies:

• Association Rules: Association Rules are used to find relationships between itemsets. For example, the first association rule can be read as- “If a person buys milk and bread, then they will also buy butter”.

• Antecedent: The antecedent is the itemset that comes in the ‘If’ part of the association rule. In the first association rule, the antecedent is Milk and Bread.

• Consequent: The consequent is the itemset that comes in the ‘Then’ part of the association rule. In the first association rule, the consequent is Butter.

To generate association rules, we have tried out all possible combinations of antecedent and consequent. Having consolidated all the rules, how do we filter out the ones which we can claim with a solid proof?

Introducing Confidence- the support of the frequent itemset given the antecedent. For example, in the first association rule, the support of the frequent itemset {Milk, Bread, Butter} is 6, and the support of the antecedent {Milk, Bread} is 7. Hence, the confidence of the rule is 6/7 = 86%.

Similarly, we compute the confidence of all the association rules:

The confidence of an association rule can be read as- 86% of the customers who buy Milk and Bread also by Butter.

Having computed the confidence of each of the association rules, let’s go back to the Subject Matter Expert to know the minimum confidence needed to prove the relevance of our association rules.

Let’s suppose that the minimum confidence defined by the Subject Matter Expert is 80%. Based on this, here is a list of association rules which can be used for Market Basket Analysis:

Hence, the best association rules that resulted after our analysis are:

1. {Milk, Bread} => {Butter} [Support = 50%, Confidence = 86%]

Which can be read as, “If a customer buys Milk and Bread, then there is a probability of 86% that they will also buy Butter”.

2. {Butter, Milk} => {Bread} [Support = 50%, Confidence = 86%]

Which can be read as, “If a customer buys Butter and Milk, then there is a probability of 86% that they will also buy Bread”.

Having generated the association rules, we move on to the next step in Association Rule Mining.

The next step in the process of Association Rule Mining is Studying the Relationship between the Antecedent and the Consequent. Let’s understand this with the help of the same example that we have previously discussed.

Here are the association rules that qualify the minimum thresholds of support and confidence:

Looking at these from a sales perspective, does the increase in sales of either the antecedent or consequent imply the increase in sales of the other? That is, if the sales of Butter goes up, do the sales of Milk and Bread also go up? Or is it vice-versa? Or is the result a fluke?

Introducing Lift- the confidence of the association rule, given the consequent. For example, in the first association rule, the confidence of the rule ({Milk, Bread} => {Butter}) is 86% or 6/7, and the support of the consequent {Butter} is 83% or 10/12 . Therefore, the lift of the rule is (6/7)/(10/12) = 1.03.

Similarly, we compute the lift of the second rule:

Lift of Association Rules

Having calculated the lift values, let’s interpret these values. No, we won’t go back and bug the Subject Matter Expert again, because these results are common for all situations.

• Lift < 1: the occurrence of the antecedent is negatively correlated with the occurrence of the consequent.

• Lift > 1: the occurrence of the antecedent is positively correlated with the occurrence of the consequent.

• Lift = 1: the occurrence of the antecedent is not correlated with the occurrence of the consequent, and the rule may be a fluke.

Hence, applying this to our association rules:

1. The first rule has a lift value more than 1, hence, the occurrence of the itemset {Milk, Bread} is positively correlated with the occurrence of {Butter}, or, if the sales of Milk and Bread increases, then the sales of Butter increases and vice-versa. Also, the result is not a fluke.

2. The second rule has a lift value of less than 1, hence, the occurrence of the itemset {Bread, Butter} is negatively correlated with the occurrence of {Milk}, or, if the sales of Bread and Butter increases, then the sales of Milk decreases and vice-versa. Also, the result is not a fluke.

UDDIT

2021UMT1791@MNIT.AC.IN

MNIT Jaipur

Market Analyst Intern

www.udditportfolio.online

29-08-2024