9 Important Concepts You should Understand In Association Rule Learning
I have experience and a background in electronics. I started out building embedded systems and my passion for robotics made me branch out into artificial intelligence.
Now I'm fully into machine learning and computer vision, I love getting my hands dirty with cool and interesting projects. In the future, I plan on my merging my knowledge of electronics and AI into the field of robotics.
I studied Computer Engineering at the Obafemi Awolowo University, Ile-Ife, Nigeria. When I'm not coding or doing chores, you would find me playing video games or enjoying some rock music.
Introduction
In the world of data mining, at times you might want to know the relationship between various data items, which you as a human might not see easily and/or right away. This is where association rule learning algorithms come in.
An easy way to remember the definition of association rule learning in an interview is to break the words down and understand what each one means. Association refers to a connection or a relationship between 2 or more entities while a rule is an instruction or a principle that governs a set of procedures. In that vein, we can describe association rule learning as the process of finding the principles or rules that govern the relationship between different elements in a dataset. Association rule learning algorithms are those algorithms that perform computations that make association rule learning easier and faster to do.
Association rule learning is applicable in many application domains such as web mining, scientific data analysis, bioinformatics and market basket data.
How do Association Rule Learning Algorithms work?
Market basket data is a common domain where association rule learning is applied and that’s what we’ll be using to illustrate how association rule learning works. Many businesses accumulate large quantities of data from their day-to-day operations like customer purchase data which is collected daily at the checkout counters of grocery stores. An example of this data is shown below and it is called market basket transactions.
| Transaction ID | Items |
| 1 | {Milk, Bread} |
| 2 | {Diapers, Bread, Eggs, Beer} |
| 3 | {Milk, Cola, Beer, Diapers} |
| 4 | {Bread, Beer, Diapers, Milk} |
| 5 | {Bread, Milk, Diapers, Cola} |
Where each row corresponds to a transaction with its unique transaction ID and set of items bought by the customer. Retailers may want to analyze this data to get valuable information about the purchasing behaviour of their customers. This information can be used in a number of business applications like inventory management and marketing promotions.
The interesting relationships hidden in the large datasets have to be discovered with a methodology known as association analysis. These uncovered relationships can then be portrayed in the form of association rules or sets of what is referred to as frequent items.
For example, from the table, one can observe that diapers and beer occur together frequently and so the following rule can be gotten from the data as shown below.
\[\{Diapers\} → \{Beer\}\]
Instead of finding these kinds of relationships and rules manually, there are various algorithms that can help in finding them. Some of the well-known algorithms are Apriori, Eclat and FP-growth.
Why Association Rule Learning is Important?
Finding patterns in massive datasets using data mining techniques is essential for knowledge discovery and the majority of decision-makers come across a lot of decision rules as an outcome of association rule analysis. Additionally, the size of these massive datasets creates a new difficulty in extracting patterns due to the cost of computing and inefficiency in achieving the necessary rules and this is why Association Rule Learning is important as it will be useful in extracting these rules with as little of the aforementioned costs as possible.
Important Concepts to Note with Association Rule Learning
The following concepts will be quite useful in preparation for a professional interview involving association rule learning algorithms or data science in general or just for the fact that it's important to note;
Why is it important to use Support and Confidence in Association Rule Learning?
Support is important because it is often used to eliminate uninteresting rules and it also has a desirable property for the efficient discovery of association rules. Confidence, on the other hand, is important for its measurement of the reliability of the inference made by a rule and because it provides an estimate of the conditional probability of a given rule.
What do you understand by frequent itemset generation?
Frequent itemset generation is the process of finding all the itemsets that satisfy the minimum support threshold using efficient techniques or algorithms like Apriori.
What is the Apriori principle?
The Apriori principle states that if an itemset is frequent, then all of its subsets must also be frequent. The subsets are also infrequent when the itemset is infrequent. It is obvious that the frequency of the subsets depends on the frequency of the itemset.
How can high-confidence rules be generated from frequent itemsets in the Apriori algorithm?
A frequent itemset produces high confidence rules if the measured support is high. The apriori algorithm generates these rules by using a level-wise approach for generating the association rules. Each level corresponds to the number of items that belong to the rule consequent (rule format: if {antecedent} then {consequent}) and the consequent of one level determines the rule of the next level.
How does the FP-Growth algorithm differ from the Apriori Algorithm?
While the Apriori algorithm subscribes to the generate and test paradigm for discovering frequent itemsets, FP-growth takes a radically different approach by encoding the data set using a compact data structure called an FP-tree and then extracts the frequent itemsets directly from this structure.
How can an FP-Tree be constructed in the FP-Growth Algorithm?
An FP-tree is a compressed representation of the input data and it is constructed by reading the data set one transaction (in the case of market basket analysis) at a time and mapping each transaction onto a path in the FP-tree. You should note that as different transactions have several items in common, their paths may overlap. The more the paths overlap, the more compression we can achieve using the FP-tree structure.
What is the support-confidence framework limitation?:
Existing association rule learning relies on support and confidence measures to eliminate uninteresting patterns. The drawback of support is that many potentially interesting patterns that involve low support items might e eliminated by the support threshold. The drawback of confidence, however, is more subtle, best explained with examples and can be traced back to the fact that it ignores the support of the itemset in the rule consequent which can result in misleading rules.
Lift is one of the metrics that address the limitation of the support-confidence framework, in what way does it do this?:
Lift addresses this limitation by computing the ratio between an association rule’s confidence and the support of the itemset in the rule consequent. It can be mathematically shown as thus; \[ lift = \frac{c(A → B)}{s(B)} \] \[ where; A = rule\ antecedent \] \[ B = rule\ consequent \] \[ s = support \] \[ c = confidence \]
Differentiate between objective and subjective interestingness measures.
Objective interestingness measure uses statistics that are derived from the data to determine whether a pattern is interesting or not while subjective measure uses impressionistic arguments to reveal unexpected information about the data or provide useful knowledge that can lead to profitable actions. For example, the rule {Butter} {Bread} may be considered interesting through objective measure due to its high support and confidence values but with subjective measures, it may not be interesting because the relationship is rather obvious and isn’t considered profitable.
Conclusion
That's it. Association rule learning is one of the lesser-known machine learning algorithms but when mastered it is such a powerful tool to have under your data science belt.
Thank you for taking your time out to read, you deserve a milkshake or whatever she's having
