Association Rule Mining Explained With Examples

Market basket analysis is used by businesses to implement effective sales strategies. Association rule mining is one of the most important steps in market basket analysis. This article discusses the basics of association mining with different examples to describe terms like support, lift, and confidence.

What is An Association Rule?

As the name suggests, the association rule is a rule that defines the dependency between two sets of objects. It basically describes how a particular item or a set of items is related to another set of items. 

Each association rule is written in the form Antecedent -> Consequent. Here, Consequent is a set of items more likely to be bought by the consumers if they buy items in the Antecedent set.

To understand this, consider the following rule.

Bread-> Butter

The above rule suggests that when a consumer buys Bread, he is more likely to buy Butter.  In a similar manner, the antecedent and consequent can have more than one item too. 

{Bread, Butter}-> {Milk, Coffee}

The importance of any association rule depends on metrics such as lift, support, and confidence. We will discuss these metrics in the next section.  

Basic Terminologies in Association Mining

Suppose we have a store’s sales data with five transactions as shown below.

Transaction ID	Items
T1	Milk, Bread, Coffee, Tea
T2	Milk, Bread
T3	Milk, Coffee
T4	Bread, Ketchup
T5	Milk, Tea, Sugar

Using this dataset, let us try to understand different terminologies in association rule mining.

Itemset

An itemset is a set containing one or more items in the transaction dataset. For instance, {Milk}, {Milk, Bread}, {Tea, Ketchup}, and {Milk, Tea, Coffee} are all itemsets. 

• An itemset can also be an empty set.
• An itemset can contain certain items even if they are not present together in the transaction dataset.

Support Count of an Itemset

The support count of an item set is the frequency of an item in the transaction data. We calculate the support count of an itemset as the total number of transactions in the transaction dataset in which a particular itemset is present. 

For example, 

• The support count of {Milk} in our dataset is 4 as milk is present in 4 transactions. 
• Support count of {Milk, Bread} is 2 as milk and bread are present together in two transactions.
• The support count of {Milk, Ketchup} is 0 as Milk and Ketchup aren’t present together in any transaction.

Minimum Support Count

We define minimum support count as the frequency of an itemset at which it becomes relevant enough to be included in the association mining process. For example, if we define the minimum support count as 2 then we will include itemsets {Milk} and {Milk, Bread} in our analysis as their support count is greater than 2. On the other hand, we won’t include the itemset {Milk, Ketchup} in our analysis as it has a support count of 0 which is less than the minimum support count.

Frequent Itemset

A frequent itemset is an itemset with support greater than minimum support or support count greater than minimum support count. 

In our example, {Milk} and {Milk, Bread}  are frequent itemsets whereas {Milk, Ketchup} isn’t a frequent itemset.

Lift, Support, and Confidence in Association Rule Mining

Lift, support, and confidence are the three metrics that we use to evaluate any rule in association rule mining. Let us discuss each metric one by one.

Support

The support of an itemset is defined as the probability that the itemset is present in a transaction. We calculate the support of an itemset as the support count of the itemset divided by the total number of transactions in the dataset.

For example, 

• The support count of {Milk} in our dataset is 4. Hence, its support will be ⅘=0.8.
• Support count of {Milk, Bread} is 2. Hence, its support will be ⅖ = 0.4.
• The support count of {Milk, Ketchup} is 0. Hence, its support will be 0.

Minimum Support

We define minimum support as the minimum probability of an item set that qualifies it for the analysis process in association rule mining. 

For example, if we define the minimum support as 0.4 then we will include itemsets {Milk} and {Milk, Bread} in our analysis as their support is greater than or equal to 0.4. On the other hand, we won’t include the itemset {Milk, Ketchup} in our analysis as it has a support of 0 which is less than the minimum support.

Confidence

While support is defined for a dataset, lift and confidence are defined for an association rule. If we are given an association rule A->C where A and C are two itemsets, the confidence of the A->C is defined as “Support of {A ∪ C} divided by Support of A”. Here, A is the antecedent itemset and C is the consequent itemset.

Confidence (A->C)=Support({A ∪ C})/ Support (A)

For example, if we are given the association rule {Milk, Bread}-> {Coffee}, we will calculate the confidence of this rule as follows.

Here,

• The antecedent itemset is {Milk, Bread}.
• The consequent itemset is {Coffee}.
• First, we will find the union of itemsets in antecedent and consequent.  The union set will be {Milk, Bread, Coffee}.
• The itemset {Milk, Bread, Coffee} is present in only one transaction out of five transactions. Hence, the support of {Milk, Bread, Coffee} is ⅕=0.2.
• The itemset {Milk, Bread} is present in two transactions out of five transactions. Hence, the support of {Milk, Bread} is ⅖  =0.4.

Confidence ({Milk, Bread}-> {Coffee})=Support({Milk, Bread, Coffee})/ Support ({Milk, Bread})
                                     =0.2/0.4
                                     =0.5

Lift

The metric lift defines the strength of an association rule. We define lift as the ratio of the observed support measure and expected support if antecedent and consequent itemsets are independent of each other. For instance, if we have an association rule A-> C, the lift is defined as 

Lift (A->C)=Support({A ∪ C})/ (Support (A)*Support (C))

For example, if we have the association rule {Milk, Bread}-> {Coffee}, we will calculate the lift of this rule as follows.

• The antecedent itemset is {Milk, Bread}.
• The consequent itemset is {Coffee}.
• First, we will find the union of itemsets in antecedent and consequent.  The union set will be {Milk, Bread, Coffee}.
• The itemset {Milk, Bread, Coffee} is present in only one transaction out of five transactions. Hence, the support of {Milk, Bread, Coffee} is ⅕=0.2.
• The itemset {Milk, Bread} is present in two transactions out of five transactions. Hence, the support of {Milk, Bread} is ⅖  =0.4.
• The itemset {Coffee} is present in two transactions out of five transactions. Hence, the support of {Coffee} is ⅖  =0.4.
• Lift=support of  {Milk, Bread, Coffee}/support of {Milk, Bread} *  support of {Coffee} i.e. 0.2/0.4*0.4=1.25.

Lift({Milk, Bread}->{Coffee})=Support({Milk, Bread, Coffee})/(Support({Milk, Bread})*Support ({Coffee}))
                             =0.2/(0.4*0.4)
                             =0.2/0.16
                             =1.25

• If the lift for an association rule is less than 1, the antecedent and consequents are substitutes for each other. I.e. Increase in the frequency of the antecedent itemset leads to a decrease in the frequency of the consequent itemset and vice versa.
• If the lift for an association rule is greater than 1, the antecedent and consequents are dependent on each other. I.e. Increase in the frequency of the antecedent itemset leads to an increase in the frequency of the consequent itemset and vice versa.
• If the lift for an association rule is equal to 1, the antecedent and consequents are independent of each other. The frequency of the antecedent items doesn’t affect the frequency of the consequent itemset and vice versa.

Association Rule Mining Algorithms

Association rule mining is a popular technique in data mining used to discover interesting relationships, correlations, or patterns in large datasets. We normally use the following algorithms for association mining.

1. Apriori algorithm: Apriori algorithm is one of the earliest and most commonly used algorithms for association rule mining. It uses a breadth-first search strategy to generate frequent item sets and then generates association rules from these item sets.
2. FP-Growth Algorithm: FP-Growth is another popular algorithm for association rule mining. It is faster than the Apriori algorithm and uses a depth-first search strategy to generate frequent itemsets.
3. Eclat Algorithm: Eclat (Equivalence Class Clustering and Bottom-up Lattice Traversal) is a vertical algorithm that works by counting the intersections of itemsets. It is efficient and scalable and can handle very large datasets.
4. CARMA (Classification Association Rules based on Multiple Associations): CARMA uses a single pass to construct a list of itemsets of all potentially frequent itemsets for every transaction. Then, for each transaction being processed, we can specify any support threshold. As each transaction is read, the itemset is updated. Next, the algorithm determines the precise support of all itemsets and prunes away all infrequent itemsets and their supersets. It reduces the time needed for generating frequent itemsets and makes processing more efficient. Finally, the frequent association rules are generated from the updated list of frequent itemsets.

These are some of the popular algorithms for association rule mining. The choice of algorithm depends on the nature and size of the dataset, as well as the specific requirements of the application.

Applications of Association Rule Mining

We use association rule mining in a wide range of applications in various fields. Some of the applications are mentioned below.

1. Market Basket Analysis: Association rule mining is commonly used in market basket analysis to identify patterns in sales data. Retailers can use this information to create targeted marketing campaigns and promotions that increase sales.
2. Customer Relationship Management (CRM): Businesses can use association rule mining to identify patterns in customer behavior. This can be used to improve customer retention and increase customer loyalty.
3. Healthcare: We can use association rule mining in healthcare to identify patterns in patient data, such as risk factors for certain diseases or conditions. This information can be used to develop more effective treatments and interventions.
4. Fraud Detection: We can also use rule mining to detect fraudulent activity, such as credit card fraud or insurance fraud. The algorithm can identify patterns in the data that indicate fraudulent behavior, allowing businesses to take appropriate action.
5. Recommender Systems: We use association rule mining in recommender systems to suggest products or services based on a customer’s previous purchases or browsing history as in market basket analysis. 
6. Social Network Analysis: Association rule mining can be used in social network analysis to identify patterns in social networks, such as groups of people with similar interests or behaviors. We can use this information to develop more effective social media marketing campaigns.

Advantages of Association Rule Mining

Performing association rule mining can provide many advantages to a business as discussed below.

1. Pattern Discovery: We use association rule mining in discovering hidden patterns and relationships among the data that may not be immediately apparent to human analysts. This can provide insights into customer behavior, market trends, and other important aspects of a business.
2. Efficient Data Analysis: Association rule mining is an efficient way to analyze large datasets and identify patterns that might otherwise be difficult to discern. It can quickly sift through vast amounts of data and identify important relationships and correlations.
3. Effective Decision-Making: We can use association rule mining to make better decisions by providing insights into customer behavior, market trends, and product sales. This information can be used to improve marketing strategies, product development, and other areas of the business.
4. Improved Customer Experience: By understanding the sales pattern and customer behavior, businesses can tailor their offerings and services to meet the needs and preferences of their customers. This can lead to a better overall customer experience and increased customer loyalty.
5. Competitive Advantage: Association mining can help us gain insights into customer behavior and sales trends that may help us gain a competitive advantage over competitors. This will help us develop more effective marketing strategies, improve customer retention, and ultimately increase profitability.

Disadvantages of Association Rule Mining 

Despite its advantages, association rule mining also has some limitations and disadvantages as discussed below.

1. False Discoveries: Association rule mining can generate a large number of rules. Here, all the rules may not be meaningful or useful. Some of these rules may be spurious or coincidental, and may not represent actual patterns or relationships in the data.
2. Limited Scope: Association rule mining is primarily designed to identify binary relationships between variables, and may not be able to detect more complex patterns or relationships. It may also miss important relationships that are not captured by the data.
3. Data Quality Issues: We need high-quality, reliable data to produce accurate results for association rule mining. If the data is incomplete, inaccurate, or inconsistent, the rules generated by the algorithm may be unreliable or misleading.
4. Computationally Intensive: Algorithms in association rule mining can be computationally intensive, particularly when dealing with large datasets. This can lead to long processing times and require significant computing resources.
5. Interpretation Issues: The rules generated by association rule mining algorithms can be difficult to interpret, particularly if they involve complex or abstract concepts. This can make it challenging for analysts to understand and apply the insights generated by the algorithm.

Overall, while association rule mining can provide valuable insights into data, it is important to be aware of its limitations and potential pitfalls. Careful consideration of the data and the application of appropriate analytical techniques can help ensure that the results generated by association rule mining are accurate and meaningful.

Conclusion

In this article, we discussed the applications, advantages, and disadvantages of association rule mining. To learn more about data mining and machine learning tasks, you can read this article on agglomerative clustering. You might also like this article on clustering for mixed data types.

I hope you enjoyed reading this article. Stay tuned for more informative articles.

Happy Learning!