Apriori Algorithm and Association Rules
Association Rule Mining is an important technique. We use it to discover rules between variables in large databases. Apriori algorithm helps to find the frequent itemsets from which Association Rules are made. You’ll learn about these concepts here.
Association Rule Mining
Association Rule Mining helps us find rules and relationships in the dataset. It works for both relational databases and transactional databases. It is also used to find the correlated features with each other. An association rule has two parts: antecedent and consequent. An antecedent is found in the dataset at hand and a consequent is found by using the antecedent. One such example of association rule is:
and are called antecedents and consequent, respectively. It can be read as: People who buy diapers are also likely to buy beer. “Diaper” and “beer” are the items. This rule has been deduced out of a dataset. This rule can help the companies to increase revenue and make smart decisions based on it.
Metrics for Evaluating Association Rules
There are various metrics involved in evaluating the Interest of Association Rules. Association Rules are carefully derived from the dataset. Let us consider the following transactional table.
Transactional ID | Items |
---|---|
1 | Bread, Milk |
2 | Bread, Diaper,Bear Eggs |
3 | Milk, Diaper, Beer, Coke |
4 | Bread, Milk, Diaper, Beer |
5 | Bread, Milk, Diaper, Coke |
Support
Support tells us about how frequent or popular an itemset is, as measured by the proportion of transactions in which an itemset appears. It is a value between 0 and 1. Values closer to 1 show that itemsets occur more frequently in the dataset. We refer to an itemset as a frequent itemset if support is larger than a specified minimum-support threshold. In the above table, we have:
There are a total of five transactions, and out of those three have the item beer appearing in them.
Out of a total five transactions, we have appearing together in two transactions.
Confidence
Confidence tells us how likely an item is purchased when item is purchased and expressed as . and are called antecedents and consequents, respectively. The higher the confidence, the more of a chance the items occur together. It is also a value between 0 and 1.
The metric is not symmetric, meaning the confidence for is not the same as . When antecedents and consequents always occur together, the confidence is 1, or the maximum.
In the denominator, you can see that confidence takes into account the popularity of , but not . Due to this, confidence measures might misrepresent the importance of an association.
Lift
In order to overcome the drawbacks of confidence measure, we introduce another measure named as lift. It also tells us how likely an item is purchased when item is purchased and expressed as where and are called antecedents and consequents. This time, it also takes the popularity of into account. You can see this in the formula below. The higher the lift, the more of a chance the items occur together. It is a value in the range
Application of Association Rule Mining
Association Rule Mining helps in the following areas.
-
It is used in Market Basket Analysis, which involves finding the items that are frequently bought together, to boost the sales and meet some business objectives.
-
In the medicine domain, we use Association Rule Mining to find which drugs are suitable for a particular disease.
Algorithms for mining frequent patterns
The pre-requisite step to find the Association Rules is to find the frequent itemsets present in the dataset. These algorithms below are used for that.
Apriori Algorithm
The Apriori Algorithm is used to find frequent itemsets from the dataset . It says If an itemset is infrequent, then all its supersets must also be infrequent. If is found to be infrequent, we can expect that to be equally infrequent. Once frequent itemsets have been found, then we can derive the Association Rules out of them.
FP-growth Algorithm
The FP-growth Algorithm also finds the frequent itemsets but it holds some advantages over Apriori Algorithm. This scans the database for finding frequent patterns. It only scans the database twice as compared to Apriori, which scans for every transaction. It is efficient and scalable.
Get hands-on with 1200+ tech skills courses.