Disclaimer: This Jupyter Notebook contains content generated with the assistance of AI. While every effort has been made to review and validate the outputs, users should independently verify critical information before relying on it. The SELENE notebook repository is constantly evolving. We recommend downloading or pulling the latest version of this notebook from Github.
Association Rule Mining¶
Association Rule Mining (ARM) is a fundamental data mining technique for discovering meaningful relationships, correlations, and co-occurrence patterns within large datasets. Given a collection of transactions or observations, the objective of ARM is to identify rules of the form $X\rightarrow Y$, indicating that the occurrence of a set of items $X$ is frequently associated with the occurrence of another set of items $Y$. By automatically uncovering hidden dependencies in data, association rule mining transforms large volumes of raw transactional information into actionable knowledge that can support data-driven decision-making. Unlike many predictive techniques, ARM focuses on revealing previously unknown patterns rather than predicting a predefined target variable.
Association rule mining has become one of the most important and widely applied tasks in data mining because of its broad range of practical applications. In retail and e-commerce, ARM is used for market basket analysis, product recommendation, promotion design, inventory planning, and shelf organization. Beyond retail, it is applied in healthcare to identify relationships among symptoms, diseases, and treatments; in bioinformatics to discover associations among genes and proteins; in cybersecurity to detect suspicious activity patterns; and in web analytics and recommender systems to understand user behavior and personalize services. Its ability to extract useful knowledge from large transactional datasets makes ARM an essential tool across numerous scientific and industrial domains.
Over the past three decades, researchers have proposed a large number of algorithms for association rule mining, each designed to address different computational challenges and application requirements. Classical candidate-generation algorithms systematically construct and prune candidate itemsets, pattern-growth algorithms improve efficiency by mining compressed database representations, and vertical-format algorithms compute support using transaction identifier lists. In addition, many specialized variants have been developed to support parallel and distributed processing, streaming data, utility-based mining, and other advanced scenarios. Each approach offers different strengths and trade-offs with respect to execution time, memory consumption, scalability, and suitability for particular types of datasets.
This notebook provides a general overview of the ARM task and introduces the major classes of algorithms used to solve it. Rather than focusing on the implementation details of individual methods, the goal is to establish a conceptual understanding of the problem, its practical relevance, and the key ideas behind the most important algorithmic approaches. Developing a solid understanding of association rule mining is an important foundation for studying modern data mining techniques, as it equips you with the knowledge needed to select appropriate algorithms and effectively extract valuable insights from large collections of transactional data.
Setting up the Notebook¶
This notebook does not contain any code, so there is no need to import any libraries.
Introduction¶
Motivation¶
Consider the manager of a supermarket who aims to improve the store's profitability and operational efficiency. Modern supermarkets collect detailed transaction data through point-of-sale systems, recording every item purchased by customers. A fundamentally very important aspect of customers' purchasing behaviors is the information which products commonly co-occur, i.e., which products are often purchased together. Such knowledge can be applied to a wide range of business problems, including:
- Pricing and promotions: Identify products that are frequently purchased together to design effective discounts, bundle offers, or cross-promotional campaigns (e.g., offering a discount on hamburger buns when purchasing burger patties).
- Shelf layout and product placement: Arrange strongly associated products close to one another to encourage impulse purchases or strategically separate them to increase customer exposure to additional products while shopping.
- Supply chain and inventory management: Predict demand for complementary products and improve inventory planning by ensuring that associated products are stocked simultaneously, thereby reducing stockouts and lost sales.
- Customer retention and loyalty programs: Personalize coupons and recommendations based on customers' purchasing patterns, increasing customer satisfaction and encouraging repeat visits.
- Product assortment decisions: Identify products that contribute to the sales of other items and make informed decisions about introducing new products or discontinuing existing ones.
- Recommendation systems: Suggest additional products at checkout or in online shopping platforms based on previously discovered purchasing associations, increasing the average basket value.
- Sales forecasting: Anticipate increased demand for related products during seasonal events or promotional campaigns by exploiting historical purchasing relationships.
While these data provide a comprehensive history of customer behavior, manually identifying meaningful purchasing patterns is practically impossible due to the sheer volume of transactions and products. This is where Association Rule Mining (ARM) comes in. ARM is one of the most widely used techniques in data mining for discovering meaningful relationships between items or events in large datasets. By identifying patterns of the form "customers who purchase item X are also likely to purchase item Y" ARM transforms raw transactional data into actionable knowledge. Unlike traditional statistical analyses that often focus on predefined hypotheses, association rule mining automatically uncovers hidden dependencies that may not be immediately apparent to decision-makers. This makes it a valuable tool for organizations seeking to leverage the vast amounts of data generated through everyday business operations.
For our supermarket manager, association rule mining provides a systematic, data-driven approach to understanding customer purchasing behavior. The extracted knowledge supports more informed decisions in marketing, merchandising, logistics, and customer relationship management, ultimately improving operational efficiency, enhancing the customer shopping experience, and increasing business profitability. For these reasons, association rule mining has become a fundamental analytical technique in retail analytics and many other application domains where discovering hidden relationships within transactional data is of significant value.
Basic Setup & Applications¶
ARM assumes that the data consist of a collection of transactions, where each transaction is represented as an unordered set of items. Let $I = \{i_1, i_2, \ldots, i_m\}$ denote the universal set of all possible items. A transaction database is then a collection of transactions $D = \{T_1, T_2, \ldots, T_n\}$, where each transaction $T_k$ is a subset of $I$ (i.e., $T_k \subseteq I$). In the classical market basket setting, each transaction corresponds to a customer's purchase, and the items are the products included in that purchase. More generally, a transaction may represent any observation that can be described as a collection of discrete items, such as visited web pages, diagnosed symptoms, or expressed genes.
The goal of ARM is to discover meaningful relationships or co-occurrence patterns among items in large datasets. Given a collection of transactions it identifies rules of the form $X \rightarrow Y$, indicating that when a set of items $X$ appears, another set of items $X$ is also likely to appear; $X$ and $Y$ are disjoint sets of items, i.e., $X, Y \subseteq I$ and $X\cap Y = \emptyset$. The right-hand side $X$ is called the $antecedent$; the left-hand side $Y$ is called the consequent The objective is not to establish causation, but to uncover associations that occur more frequently than expected by chance and may be useful for understanding the data or making decisions.
Association rule mining is most widely known for its application to Market Basket Analysis, where the objective is to discover products that customers frequently purchase together; see the motivation above. This application popularized the field through examples such as identifying that customers who buy bread and butter are also likely to buy milk, enabling retailers to improve product placement, promotions, and recommendation systems. Because of its intuitive interpretation and commercial value, market basket analysis remains the canonical example used to introduce association rule mining.
However, the underlying methodology is much more general and can be applied to any dataset that can be represented as a collection of transactions, where each transaction is a set of discrete items. In each of these applications, the meaning of a "transaction" and an "item" changes, but the goal remains the same: to discover meaningful patterns of co-occurrence that reveal relationships among items and provide actionable insights. The table provides an overview of different applications that make use of ARM.
| Application | Transaction | Individual Item | Examples of Interesting Rules |
|---|---|---|---|
| Market Basket Analysis | A customer's shopping basket | A purchased product | Customers who buy bread and butter also tend to buy milk. |
| Recommender Systems | A user's purchase or viewing history | A purchased, viewed, or liked item | Users who watch Movie A and Movie B often watch Movie C. |
| Web Usage Mining | A user session on a website | A visited web page | Users who visit the product page often proceed to the checkout page. |
| Clickstream Analysis | A browsing session | A clicked link or webpage | Visitors who read the pricing page frequently visit the contact page. |
| Text Mining | A document | A word or term | Documents containing machine and learning often contain artificial intelligence. |
| Biomedical Research | A patient or biological sample | A symptom, diagnosis, genetic mutation, or expressed gene | Patients with symptom A and symptom B frequently have disease C. |
| Electronic Health Records | A patient's medical record or hospital visit | A diagnosis, medication, laboratory result, or procedure | Patients diagnosed with hypertension often also receive ACE inhibitors. |
| Fraud Detection | A financial transaction or insurance claim | A transaction attribute (e.g., merchant type, location, payment method) | Transactions from new devices and foreign locations are often associated with fraudulent activity. |
| Network Intrusion Detection | A network connection or system event | A network event, protocol, port, or alert | Connections using unusual ports and repeated login failures are frequently associated with intrusion attempts. |
| Manufacturing and Quality Control | A manufactured product or production batch | A detected defect, process step, or machine setting | Products with defect A often also exhibit defect B. |
| Software Engineering | A software project, source file, or bug report | A function, module, library, or bug label | Files importing library X often also import library Y. |
| Social Network Analysis | A user's interactions or profile | A friend, interest, group membership, or hashtag | Users interested in photography often also join travel groups. |
Important: From a mathematical perspective, the items do not have to be of the same type. The only requirement is that each transaction can be represented as a set of discrete items drawn from a common item universe. The classical market basket setting naturally satisfies this because every item is a product. This has led many introductory texts to present the item universe as homogeneous. However, in many real-world applications, the item universe is heterogeneous, containing different kinds of entities or attributes. For example, in electronic health records, a transaction might represent a patient encounter containing items such as:
- Symptom: fever
- Symptom: cough
- Diagnosis: influenza
- Medication: oseltamivir
- Laboratory result: positive influenza test
Association rule mining can then discover rules such as:
or
$$\large \{\text{influenza}\} \rightarrow \{\text{oseltamivir}\}. $$The important caveat is interpretability. If the item universe mixes very different concepts, some discovered rules may be trivial or uninteresting. For example,
may simply reflect the clinical diagnostic process rather than reveal a novel association. Consequently, practitioners often constrain the types of rules they mine. In biomedical research, one might specifically search for symptoms $\rightarrow$ diagnoses, genetic variants $\rightarrow$ diseases, or diagnoses $\rightarrow$ medications, while excluding rules among items of the same or unrelated types. So, while the mathematics of association rule mining places no restriction on item types, many practical applications deliberately impose semantic constraints to ensure the resulting rules are meaningful and actionable.
Throughout this notebook, we use Market Basket Analysis as an example use case. More specifically, to keep it simple, we consider a very small set of items (i.e., supermarket products) $I = \{\text{bread}, \text{cereal}, \text{cheese}, \text{eggs}, \text{milk}, \text{yogurt}\}$ and the following set of $5$ transactions:
| TID | Items |
|---|---|
| 1 | bread, yogurt |
| 2 | bread, cereal, eggs, milk |
| 3 | cereal, cheese, yogurt |
| 4 | bread, cereal, milk, yogurt |
| 5 | bread, cheese, milk, yogurt |
Important: Recall that basic ARM represents each transaction as a set of items, meaning that only the presence or absence of each item is considered. Consequently, the model ignores both the order of items and their multiplicity within a transaction. In the context of Market Basket Analysis, for example, a transaction containing the item "eggs" simply indicates that eggs were purchased, regardless of whether the customer bought a carton of 6 eggs, a dozen eggs, or several cartons. Likewise, if a customer purchases multiple units of the same product, the item appears only once in the transaction. Thus, basic association rule mining treats all transactions containing "eggs" identically, regardless of the quantity purchased, focusing solely on which items co-occur rather than how many units of each item are present.
What are "Interesting" Rules?¶
Intuitively, an association rule expresses that when one set of items or events occurs, another item or set of items is likely to occur as well. For example, given our small Market Basket analysis dataset:
means that customers who buy cereal often also buy milk. In other words, an association rule captures a recurring co-occurrence pattern in the data, indicating that the presence of the left-hand side makes the right-hand side more likely, without implying causation or certainty.
Although any rule of the form $X \rightarrow Y$ can be considered an association rule, not every rule is useful or interesting. Many rules may describe coincidences, involve very rare items, or express relationships that are already expected (e.g., because $Y$ is very common). Such rules provide little actionable insight. What makes a rule "interesting" depends on the application and your goals. For example, a retailer may value rules that reveal profitable cross-selling opportunities, while a medical researcher may be interested in rare but highly reliable associations. Because there is no universal notion of interestingness, different evaluation measures are used to assess rules from different perspectives, including frequency, reliability, and the strength of the association.
We will introduce the most important and common evaluation metrics later more formally.
Naive ARM Algorithm¶
Let's assume that we have some evaluation measures that take in an association rule $X \rightarrow Y$ and return some numerical scores; again, covered later. Since the the set of items $I$ is finite, we can implement are very simple algorithm to find all interesting association rules
Generate all possible rules $X \rightarrow Y$ with $X, Y \subseteq I$ and $X\cap Y = \emptyset$
For each rule, check if it qualifies with respect to the evaluation metrics (i.e., if the scores are above or below certain thresholds)
Every rule that qualifies is part of the result set as output of the algorithm.
The issue with this approach is the need to generate all possible rules. If we use $d = |I|$ to denote the number of unique items, the number of unique rules is:
In other words, the number of unique rules increases exponentially with the number of unique items in set $I$. Just for our tiny example dataset containing $6$ items, we would need to check $602$ rules. Of course, supermarkets typically carry several thousands of different products. The table provides some estimated numbers for different store types just to get a rough sense of the scale.
| Store type | Typical number of unique products |
|---|---|
| Convenience store | 2,000 — 4,000 |
| Discount supermarket (e.g., Aldi, Lidl) | 1,500 — 4,500 |
| Standard supermarket | 30,000 — 40,000 |
| Large hypermarket/supercenter | 50,000 — 100,000+ |
Of course, if we consider online stores, the number of unique products is much higher. For example, in June 2026, the estimated number of products that can be ordered via Amazon was $600$ Million. Although $588$ Million products are sold by 3rd-party vendors, and "only" 12 Million products are sold directly by Amazon, the company can still use this information to extract useful association rules. Using the naive algorithm and trying to generate all possible rules and check them is completely impractical. Thus, a more sophisticated algorithm is needed to make association rule mining scale.
Basic Definitions & Measures¶
Association rule mining is based on the core notions of itemsets and k-itemsets because it aims to discover relationships among groups of items in transactional data. An itemset is any collection of one or more items that appear together in a transaction, while a k-itemset is an itemset containing exactly k items. To illustrate these ideas, let's list all possible $k$-itemsets for our example dataset of $d=6$ unique items:
- $1$-itemsets: $\{\text{bread}\}$, $\{\text{cereal}\}$, $\{\text{cheese}\}$, $\{\text{eggs}\}$, $\{\text{milk}\}$, $\{\text{yogurt}\}$
- $2$-itemsets: $\{\text{bread, cereal}\}$, $\{\text{bread, cheese}\}$, $\{\text{bread, eggs}\}$, $\{\text{bread, milk}\}$, $\{\text{bread, yogurt}\}$, $\{\text{cereal, cheese}\}$, $\{\text{cereal, eggs}\}$, $\{\text{cereal, milk}\}$, $\{\text{cereal, yogurt}\}$, $\{\text{cheese, eggs}\}$, $\{\text{cheese, milk}\}$ $\{\text{cheese, yogurt}\}$, $\{\text{eggs, milk}\}$, $\{\text{eggs, yogurt}\}$, $\{\text{milk, yogurt}\}$
- $3$-itemsets: $\{\text{bread, cereal, cheese}\}$, $\{\text{bread, cereal, eggs}\}$, $\{\text{bread, cereal, milk}\}$, $\{\text{bread, cereal, yogurt}\}$, $\{\text{bread, cheese, eggs}\}$, $\{\text{bread, cheese, milk}\}$, $\{\text{bread, cheese, yogurt}\}$, $\{\text{bread, eggs, milk}\}$, $\{\text{bread, eggs, yogurt}\}$, $\{\text{bread, milk, yogurt}\}$, $\{\text{cereal, cheese, eggs}\}$, $\{\text{cereal, cheese, milk}\}$, $\{\text{cereal, cheese, yogurt}\}$, $\{\text{cereal, eggs, milk}\}$, $\{\text{cereal, eggs, yogurt}\}$, $\{\text{cereal, milk, yogurt}\}$, $\{\text{cheese, eggs, milk}\}$, $\{\text{cheese, eggs, yogurt}\}$, $\{\text{cheese, milk, yogurt}\}$, $\{\text{eggs, milk, yogurt}\}$
- $4$-itemsets: $\{\text{bread, cereal, cheese, eggs}\}$, $\{\text{bread, cereal, cheese, milk}\}$, $\{\text{bread, cereal, cheese, yogurt}\}$, $\{\text{bread, cereal, eggs, milk}\}$, $\{\text{bread, cereal, eggs, yogurt}\}$, $\{\text{bread, cereal, milk, yogurt}\}$, $\{\text{bread, cheese, eggs, milk}\}$, $\{\text{bread, cheese, eggs, yogurt}\}$, $\{\text{bread, cheese, milk, yogurt}\}$, $\{\text{bread, eggs, milk, yogurt}\}$, $\{\text{cereal, cheese, eggs, milk}\}$, $\{\text{cereal, cheese, eggs, yogurt}\}$, $\{\text{cereal, cheese, milk, yohurt}\}$, $\{\text{cereal, eggs, milk, yogurt}\}$, $\{\text{cheese, eggs, milk, yogurt}\}$
- $5$-itemsets: $\{\text{bread, cereal, cheese, eggs, milk}\}$, $\{\text{bread, cereal, cheese, eggs, yogurt}\}$, $\{\text{bread, cereal, cheese, milk, yogurt}\}$, $\{\text{bread, cereal, eggs, milk, yogurt}\}$, $\{\text{bread, cheese, eggs, milk, yogurt}\}$, $\{\text{cereal, cheese, eggs, milk, yogurt}\}$
- $6$-itemsets: $\{\text{bread, cereal, cheese, eggs, milk, yogurt}\}$
In general for a given $d$ and a given $k$, there are $\large\binom{d}{k}$ possible itemsets.
Organizing itemsets by their size $k$ allows mining algorithms, such as Apriori, to systematically generate and evaluate larger item combinations from smaller ones, making the discovery of frequent patterns and association rules more efficient. For now, we need the notion of $k$-itemsets for the basic definitions of measures to quantify how "interesting" an association rule is.
Support¶
The support of an association rule $X \rightarrow Y$ measures how frequently the items in both $X$ and $Y$ occur together in the entire transaction database. Intuitively, it indicates how common or significant the rule is in the dataset. A higher support means the rule applies to a larger proportion of transactions, (typically!) making it more relevant and reliable for identifying meaningful patterns. Mathematically, the support of rule $X \rightarrow Y$ is defined as:
In other words, the support of an association rule $X \rightarrow Y$ is equal to the support of the itemset form as the union of $X$ and $Y$ — recall that $X\cap Y = \emptyset$. The support of an itemset $Z$ is defined as the number of transactions containing Z (i.e., the support count $\text{SC}$) divided by the total number of transaction $N$:
To give an example, here are the support values for two association rules derived from our example dataset with $N=5$ transactions:
You can confirm this support count by checking that only transactions with ID $4$ and $5$ contain the three relevant items.
Important: The fact that the support is the same for both rules is not by chance. Both rules are "related" since the union of the left-hand side $X$ and the right-hand side $Y$ is the same for both rules. And since the support of a rule $X \rightarrow Y$ is the same as support of the itemset $X \cap Y$, association rules that yield the same union will naturally have the same support. We will exploit this observation as part of the Apriori algorithm for ARM.
Side note: The support of an association rule $X \rightarrow Y$ is essentially its relative frequency in the transaction database. Since support is the fraction of all transactions satisfying the rule, it can also be interpreted as the probability that a randomly selected transaction contains the itemset $X \cup Y$. Although support is numerically equivalent to the relative frequency (or empirical probability) of the itemset $X \cup Y$, its interpretation is different: it measures the amount of evidence in the database that backs the rule $X \rightarrow Y$. Thus, the term support highlights the evidential rather than the probabilistic interpretation of the measure.
Many algorithms for ARM use the fact that $\text{S}(X \rightarrow Y) = \text{S}(X\cup Y)$ by first finding itemset with sufficient support — which are often called frequent itemset. The motivation is that only frequent itemsets are meaningful to derive association rules. For example, if we would know that the $3$-itemset $\{\text{bread, cereal, yogurt}\}$ is not a frequent itemset, we can ignore all the rules we can derive from that itemset:
- $\{\text{bread, cereal}\} \rightarrow \{\text{yogurt}\}$
- $\{\text{bread, yogurt}\} \rightarrow \{\text{cereal}\}$
- $\{\text{cereal, yogurt}\} \rightarrow \{\text{bread}\}$
- $\{\text{bread}\} \rightarrow \{\text{cereal, yogurt}\}$
- $\{\text{cereal}\} \rightarrow \{\text{bread, yogurt}\}$
- $\{\text{yogurt}\} \rightarrow \{\text{bread, cereal}\}$
Various ARM algorithms utilize this observation.
Confidence¶
Support is an intuitive measure of interestingness because it captures how frequently an itemset or association rule occurs in a transaction database. However, relying solely on support may overlook valuable associations involving infrequently purchased items. For example, champagne and caviar are not frequently bought, but if they are, then frequently together. Such cases are typically observed for niche or high-value products that may appear in only a small number of transactions, resulting in low support, yet exhibit very strong relationships with complementary items. In short, relying only on support might miss rules such as $\{\text{champagne}\}\rightarrow\{\text{caviar}\}$ and/or vice versa.
Thus, ARM also uses the measure of confidence. The confidence of an association rule $X \rightarrow Y$ is the proportion of transactions containing $X$ that also contain $Y$. It is defined as:
Again, confidence has a probabilistic interpretation as it measures the conditional probability $P(Y\mid X)$ that a transaction contains $Y$ given that it already contains $X$. A higher confidence indicates a stronger association between $X$ and $Y$. Or in other words, a high confidence indicates that whenever $X$ occurs, $Y$ is likely to occur as well, making the rule a strong predictor. Let's look at to rules for our example dataset:
Of course, we generally find association rules with a large(r) confidence more interesting.
Lift¶
While a useful measure, the problem with confidence is that it ignores the baseline frequency of the consequent $Y$. To illustrate this, let's assume that almost all baskets contain bread while only a small fraction of baskets contain champagne. Now let's consider the rule $\{\text{champagne}\}\rightarrow\{\text{bread}\}$. This rule is likely to have a high confidence simply because bread is so frequently bought. Thus, this rule is not particularly interesting because almost all customers already buy bread. Knowing that a customer buys champagne does not meaningfully increase the likelihood that they will also buy bread.
A different approach is therefore to control the confidence by the baseline frequency of the consequent $Y$, which brings us to the measure of lift. The lift of an association rule $X \rightarrow Y$ measures how much more likely $Y$ is to occur when $X$ occurs compared with its overall occurrence in the database. It is defined as:
Thus, the lift measures how much more often $X$ and $Y$ occur together than would be expected if they were statistically independent. While confidence measures the probability of $Y$ given $X$, it can be misleading when $Y$ is very common. Lift corrects for this by comparing the observed co-occurrence of $X$ and $Y$ with the expected co-occurrence under independence:
- Lift > 1: $X$ and $Y$ occur together more often than expected (positive association)
- Lift = 1: $X$ and $Y$ are independent
- Lift < 1: $X$ and $Y$ occur together less often than expected (negative association)
Notice that, just by looking at the definition, we can see that $\text{Lift}(X \rightarrow Y) = \text{Lift}(Y \rightarrow X)$ since both the numerator and the denominator are the same.
To give an example, consider the rule $\{\text{cereal}\}\rightarrow\{\text{bread}\}$. By using the definition of lift and plugging in the values, we get:
Since the lift of this rule is negative, cereal and bread occur together less often than expected. Or in other words, knowing that cereal in a basket reduces the probability of also seeing bread in that basket (compared to not knowing that cereal is in the basket). More concretely, if we know nothing about the basket, we expect it to contain bread with $\text{Support}(\{\text{bread}\}) = 0.8$. However, seeing bread knowing that the basket contains cereal is expressed by $\text{Conf}(\{\text{cereal}\}\rightarrow \{\text{bread}\}) = 0.66$. Thus, the probability of seeing bread goes down when knowing the basket contains cereal, and therefore we get a negative lift for this rule.
Like for support and confidence, we can interpret the lift of an association rule probabilistically:
Side note: Notice how in the numerator $\text{Support}$ uses the union $\cup$ while the probability $P$ uses the intersection $\cap$. This is because the support treats $X$ and $Y$ as itemsets, while the probability treats $X$ and $Y$ as events. However, both interpretations mean that both $X$ and $Y$ appear together in the same transaction. In general, we can completely ignore the probabilistic interpretation. However, can be useful to see the relationship to the measure of pointwise mutual information (PMI), which is defined as:
Like lift, PMI measures how strongly two itemsets are associated by comparing their observed co-occurrence with the co-occurrence expected under statistical independence. The main take-away message here is simply that support, confidence and lift are not completely "new" measures. However, they more intuitively capture the interpretation of $X$ and $Y$ as itemset instead of events.
Other Measures¶
Beyond support, confidence, and lift, there are many other available measures to evaluate association rules; here are some alternative measure and their basic intuition — but keep in mind that not even this list is comprehensive:
Leverage: Measures how much more often the antecedent and consequent occur together than would be expected by chance. It highlights the actual increase in co-occurrence rather than just a relative effect.
Conviction: Evaluates the strength of an implication by considering how often the rule would be expected to fail if the antecedent and consequent were independent. Higher values indicate stronger directional relationships.
All-Confidence: Reflects how consistently the items in a rule appear together by comparing their joint occurrence with the frequency of the most common item. It is useful for identifying strongly co-occurring itemsets.
Kulczynski (Kulc): Balances the conditional relationships in both directions, providing a more stable assessment when item frequencies differ substantially.
Certainty Factor: Quantifies how much confidence in the consequent increases when the antecedent is known. It distinguishes positive associations from negative ones.
Collective Strength: Evaluates both the frequency of co-occurrence and the frequency of non-co-occurrence, providing a more comprehensive measure of the overall association.
The reason for so many measures is that there is no single best measure for evaluating association rules because different measures emphasize different aspects of a relationship. Some focus on the frequency of a rule, others on its predictive strength, statistical significance, deviation from independence, or robustness to rare or common items. As a result, the most appropriate measure depends on the specific application and the type of patterns that are of interest. Using multiple measures often provides a more comprehensive assessment of the quality and usefulness of association rules.
Important: Support and confidence are special among the many interestingness measures because they are not only used to evaluate association rules, but also to efficiently generate them. Specifically, the Apriori algorithm — more details below — relies on the minimum support threshold to prune the search space by eliminating infrequent itemsets, thereby avoiding the exploration of many candidate rules. After frequent itemsets have been identified, minimum confidence is used to filter the generated rules, retaining only those that satisfy the desired predictive strength. In contrast, most other interestingness measures (e.g., lift, leverage, or conviction) are typically applied after the candidate rules have been generated to rank, compare, or further filter the resulting rules.
ARM Algorithms — An Overview¶
We already saw that a very naive ARM algorithm would be to generate all possible association rules for a given set of unique items $I$, and evaluate each rule with respect to the chosen measures (e.g., minimum support, minimum confidence, or lift — for lift, any values "far away" from $1$ can be interesting, depending on the exact use case). We also saw that this requires the generation of $3^d - 2^{d+1} + 1 \in O(3^d)$ rules, with $d = |I|$ being the unique number of items in the transaction database. This is impractical for any real-world use cases, and spurred the introduction of a plethora of algorithms for ARM.
Important: The purpose of the overview of popular ARM algorithms in this section is not to provide a deep understanding of the algorithms but to provide a basic intuition about basic approaches and the general pros and cons. The most important take-away message is that Association Rule Mining is a general task and not associated with one single algorithm. While all algorithms need to address the same major challenge — that is, the exponential growth of possible rules or itemsets (see naive algorithm above) — they do so using different approaches, assumptions, or constraints.
Candidate-Generation Methods¶
The basic intuition behind candidate-generation methods is to systematically explore the space of all possible item combinations while avoiding unnecessary computations. Since the number of possible itemsets grows exponentially with the number of distinct items, checking every possible combination is computationally infeasible for real-world datasets. Candidate-generation algorithms address this challenge by generating potentially frequent itemsets level by level, starting with individual items, and evaluating only those combinations that have a reasonable chance of being frequent.
The key idea enabling this approach is the Apriori principle, which states that every subset of a frequent itemset must itself be frequent. Consequently, if an itemset is found to be infrequent, all of its supersets can be safely discarded without further consideration. For example, if we would know that the, say, $2$-itemset $\{\text{bread, cereal}\}$ is not frequent, we would also immediately know that any larger itemset containing $\{\text{bread, cereal}\}$ as a subset cannot be a frequent itemset as well. This is also called the anti-monotonicity property of support. The key intuition is that adding more conditions to a pattern can only make it harder for that pattern to occur. However, most other evaluation m
Candidate-generation algorithms therefore alternate between two phases: (1) candidate generation, in which larger itemsets are constructed from previously discovered frequent itemsets, and (2) candidate pruning, in which infrequent candidates are eliminated based on their support. By repeatedly applying these two phases, the search space is drastically reduced while guaranteeing that all frequent itemsets — and therefore all valid association rules satisfying the minimum support threshold—are eventually discovered. The most important algorithms in this category are briefly described below:
The AIS algorithm was the first algorithm proposed for mining association rules. It generates candidate itemsets dynamically while scanning the database. Whenever a frequent itemset is found within a transaction, the algorithm immediately extends it by appending additional items from the same transaction, thereby producing new candidate itemsets for subsequent iterations. Although AIS introduced the fundamental concepts of association rule mining, it generates a large number of unnecessary candidate itemsets, many of which ultimately prove to be infrequent. Consequently, the algorithm requires considerable computational effort and multiple database scans, making it unsuitable for large transactional datasets.
The SETM (Set-Oriented Mining) algorithm was developed to improve database integration by organizing candidate itemsets in a relational format. Instead of storing candidates solely in memory, SETM maintains them in temporary database tables, making it particularly suitable for implementation within relational database management systems. Despite its elegant integration with database technology, SETM creates very large intermediate relations containing candidate itemsets. Managing these intermediate tables introduces substantial overhead, resulting in lower performance than later candidate-generation algorithms such as Apriori.
The Apriori algorithm is the best-known and most influential candidate-generation algorithm. It exploits the Apriori principle to iteratively discover frequent itemsets. During each iteration, candidate itemsets of size (k) are generated by joining frequent ((k-1))-itemsets. Before evaluating their support, any candidate whose subset is known to be infrequent is immediately discarded, substantially reducing the search space. Apriori repeatedly alternates between candidate generation and candidate pruning, scanning the database once per iteration to determine candidate support. Although this pruning strategy greatly improves efficiency compared with AIS and SETM, Apriori may still generate an enormous number of candidate itemsets and requires multiple database scans, limiting its scalability for very large or dense datasets.
The Direct Hashing and Pruning (DHP) algorithm extends Apriori by reducing the number of candidate itemsets generated during the mining process. During database scanning, candidate itemsets (particularly 2-itemsets) are hashed into buckets. Buckets whose counts fall below the minimum support threshold can be discarded, allowing many candidate itemsets to be eliminated before explicit support counting. In addition to hash-based pruning, DHP progressively reduces the size of the transaction database by removing transactions and items that can no longer contribute to larger frequent itemsets. These optimizations decrease both computational cost and memory consumption, making DHP more efficient than the original Apriori algorithm.
The Dynamic Itemset Counting (DIC) algorithm improves the efficiency of candidate-generation methods by introducing new candidate itemsets during a database scan rather than waiting until the next complete pass. As support information becomes available, DIC dynamically classifies itemsets as potentially frequent or infrequent and updates the search space accordingly. By overlapping support counting with candidate generation, DIC reduces the number of complete database scans required to discover all frequent itemsets. Although this dynamic strategy often results in faster execution than Apriori, it also increases algorithmic complexity due to the additional bookkeeping required to manage itemsets at different stages of the mining process.
The following table provides a summary comparing the most common candidate-generation methods.
| Algorithm | Main Idea | Major Strength | Main Limitation |
|---|---|---|---|
| AIS | Generate candidates while scanning transactions | First association rule mining algorithm | Produces many unnecessary candidate itemsets |
| SETM | Store candidate itemsets in relational tables | Integrates well with database systems | Large intermediate tables reduce efficiency |
| Apriori | Generate candidates level by level using the Apriori principle | Effective pruning of infrequent candidates | Multiple database scans and candidate explosion |
| DHP | Use hashing and transaction pruning to reduce candidates | Fewer candidates and lower memory requirements | Additional hashing overhead |
| DIC | Introduce candidates dynamically during database scans | Fewer database scans than Apriori | More complex implementation and bookkeeping |
Overall, candidate-generation methods established the foundation of association rule mining by demonstrating that frequent itemsets can be discovered efficiently through iterative candidate construction and pruning. However, their reliance on repeated database scans and explicit candidate generation motivated the development of more advanced approaches, such as pattern-growth and vertical-format algorithms, which address these scalability limitations.
Pattern-Growth Methods¶
The basic intuition behind pattern-growth methods is to eliminate the costly process of generating and testing large numbers of candidate itemsets. Instead of repeatedly constructing candidate combinations and scanning the database, these methods compress the transaction database into a compact data structure that preserves all information necessary for frequent itemset mining. The compressed representation allows the algorithm to focus only on portions of the data that are relevant to the current search, thereby significantly reducing both the number of database scans and the overall computational effort.
Starting from a frequent item or itemset (called a prefix), pattern-growth algorithms recursively extend this prefix by exploring only those items that frequently co-occur with it. For each prefix, a smaller conditional database is constructed that contains only the transactions relevant to that prefix, and the mining process continues recursively on this reduced dataset. By progressively growing frequent patterns rather than generating all possible candidates, pattern-growth methods efficiently discover all frequent itemsets while avoiding much of the redundant computation performed by candidate-generation algorithms. Common pattern-growth methods include:
The FP-Growth (Frequent Pattern Growth) algorithm is the most influential and widely used pattern-growth algorithm. It first scans the transaction database to determine the frequency of each item and removes infrequent items. The remaining items are sorted by decreasing frequency and inserted into a compact Frequent Pattern Tree (FP-tree), where transactions sharing common prefixes reuse the same tree nodes. This compressed representation often reduces the database size dramatically while preserving all information needed to discover frequent itemsets. Rather than generating candidate itemsets, FP-Growth recursively constructs conditional pattern bases and conditional FP-trees for each frequent item. Starting from the least frequent item, the algorithm explores increasingly larger frequent patterns by extending item prefixes within these conditional databases. By avoiding explicit candidate generation, FP-Growth is substantially faster than Apriori, particularly for large transactional databases.
The H-Mine (Hyper-Structure Mining) algorithm was developed to improve the efficiency of pattern-growth methods for datasets that are sparse or cannot be effectively compressed into an FP-tree. Instead of constructing a tree-based structure, H-Mine organizes transactions using a compact hyperlinked data structure that allows the algorithm to traverse only the relevant portions of the database during recursive mining. The hyperlinked representation can be built with relatively little overhead and avoids the costly reconstruction of conditional trees required by FP-Growth. Consequently, H-Mine often performs well on sparse datasets and databases that fit comfortably in main memory, while maintaining the advantages of recursive pattern growth without candidate generation.
The FP-Max algorithm extends FP-Growth by focusing exclusively on maximal frequent itemsets rather than discovering every frequent itemset. A maximal frequent itemset is a frequent itemset that has no frequent superset. Since every subset of a maximal frequent itemset is automatically frequent, storing only maximal patterns can substantially reduce the number of discovered patterns. FP-Max uses the FP-tree framework together with additional pruning techniques that identify branches that cannot produce new maximal itemsets. By mining only maximal frequent patterns, FP-Max reduces both computational effort and storage requirements, making it particularly useful for dense datasets that contain a very large number of frequent itemsets.
The FP-Close algorithm is another extension of FP-Growth that mines closed frequent itemsets. A frequent itemset is considered closed if none of its supersets has the same support. Closed itemsets provide a lossless and highly compact representation of all frequent itemsets because the support of every frequent itemset can be derived from an appropriate closed itemset. FP-Close combines the recursive FP-tree mining strategy with efficient closure checking during the mining process. By eliminating redundant frequent itemsets that have identical support, FP-Close significantly reduces the number of reported patterns while preserving complete support information. This makes it an attractive choice when both compactness and accurate support counts are required.
The following table provides a summary comparing the most common pattern-growth methods.
| Algorithm | Main Idea | Major Strength | Main Limitation |
|---|---|---|---|
| FP-Growth | Mine an FP-tree recursively without candidate generation | Excellent performance on large databases; only two database scans | FP-tree construction and conditional trees may become complex for certain datasets |
| H-Mine | Mine a hyper-linked transaction structure | Performs well on sparse datasets; low memory overhead | Generally less effective than FP-Growth on highly compressible dense datasets |
| FP-Max | Mine only maximal frequent itemsets | Produces a compact result set and reduces mining time | Does not report all frequent itemsets or their exact support values |
| FP-Close | Mine only closed frequent itemsets | Compact representation while preserving complete support information | More computational overhead than FP-Growth due to closure checking |
Overall, pattern-growth methods represent the second major generation of association rule mining algorithms. By replacing explicit candidate generation with recursive exploration of compressed database representations, they achieve substantially higher efficiency than classical candidate-generation approaches. Among these methods, FP-Growth has become the de facto standard for classical frequent itemset mining, while FP-Max and FP-Close provide compact representations for applications where the complete set of frequent itemsets would be prohibitively large.
Vertical-Format Methods¶
The basic intuition behind vertical-format methods is to represent the transaction database by items rather than transactions. Instead of storing each transaction as a list of purchased items (horizontal format), the database is transformed into a vertical representation, where each item is associated with the list of transaction identifiers (TIDs) in which it appears. The table below shows the vertical representation of our example transaction database for our Market Basket Analysis use case.
| Itemset | TIDs |
|---|---|
| {bread} | 1, 2, 4, 5 |
| {cereal | 2, 3, 4 |
| {cheese} | 3, 5 |
| {eggs} | 2 |
| {milk} | 2, 3, 5 |
| {yogurt} | 1, 3, 4, 5 |
The support of an itemset can then be computed efficiently by intersecting the TID lists of its constituent items. The size of the resulting intersection directly corresponds to the support of the combined itemset, eliminating the need to repeatedly scan the original database.
Frequent itemsets are discovered by recursively intersecting TID lists to generate larger itemsets from smaller ones. Since set intersection is a highly efficient operation, vertical-format algorithms can compute support much faster than repeatedly reading the transaction database, especially for dense datasets where transactions contain many items. Furthermore, because the database is transformed only once into its vertical representation, subsequent support calculations rely entirely on TID-list operations rather than additional database scans. Various algorithms utilize this vertical format, including:
The ECLAT (Equivalence Class Transformation) algorithm is the best-known and most widely used vertical-format algorithm. It begins by transforming the horizontal transaction database into a vertical representation in which each item is associated with the list of transaction identifiers containing that item. Larger frequent itemsets are then generated by intersecting the TID lists of smaller frequent itemsets. The support of the resulting itemset is simply the number of transaction identifiers contained in the intersection. ECLAT explores the search space using a depth-first strategy, recursively extending frequent itemsets while avoiding repeated scans of the original database. Since TID-list intersection is computationally efficient, ECLAT typically outperforms candidate-generation methods on dense datasets. However, storing large TID lists entirely in memory can become expensive for very large databases or highly frequent items.
The dECLAT algorithm extends ECLAT by replacing complete transaction identifier lists with difference sets (diffsets). Instead of storing every transaction containing an itemset, a diffset records only the transactions that distinguish a child itemset from its parent. Because these difference sets are often much smaller than the corresponding TID lists, the algorithm significantly reduces memory consumption. Support values are computed incrementally from the parent support and the size of the diffset, eliminating the need to maintain large transaction lists throughout the mining process. This optimization makes dECLAT particularly effective for dense datasets where traditional TID lists become increasingly large as the mining process progresses.
The VIPER (Vertical Itemset Partitioning and Early Reduction) algorithm further improves the efficiency of vertical-format mining by introducing partitioning and early reduction techniques. The search space is divided into smaller partitions, allowing the algorithm to process independent subsets of itemsets while reducing unnecessary comparisons and support computations. In addition, VIPER aggressively removes transactions and intermediate data structures that can no longer contribute to discovering larger frequent itemsets. These optimizations decrease both memory usage and computational overhead, enabling VIPER to outperform basic vertical-format approaches on many large and dense datasets.
The following table provides a summary comparing the most common candidate-generation methods.
| Algorithm | Main Idea | Major Strength | Main Limitation |
|---|---|---|---|
| ECLAT | Represent items by transaction ID (TID) lists and compute support through set intersections | Fast support computation; efficient depth-first search | Large TID lists may require substantial memory |
| dECLAT | Replace TID lists with compact difference sets (diffsets) | Lower memory consumption and faster support computation on dense datasets | Additional bookkeeping required for diffsets |
| VIPER | Partition the search space and apply early reduction techniques | Improved scalability through partitioning and memory optimization | More complex implementation than ECLAT |
Overall, vertical-format methods provide an efficient alternative to both candidate-generation and pattern-growth algorithms by shifting the focus from repeated database scans to set-intersection operations on transaction identifier lists. Among these algorithms, ECLAT serves as the foundational approach, while dECLAT improves memory efficiency through difference sets and VIPER further enhances scalability through partitioning and early reduction techniques. These methods are particularly well suited for dense transactional databases, where efficient support computation through TID-list operations offers a significant performance advantage.
Other Methods & Variants¶
While candidate-generation, pattern-growth, and vertical-format algorithms form the three fundamental classes of association rule mining methods, they do not encompass the full range of approaches proposed in the literature. Over the past decades, numerous variants and specialized algorithms have been developed to address the limitations of classical methods or to satisfy the requirements of specific application domains. Rather than introducing entirely new mining paradigms, these algorithms typically extend one of the three fundamental approaches with optimizations tailored to particular data characteristics, computational environments, or business objectives.
One important class of extensions focuses on parallel and distributed association rule mining. As modern applications often involve terabytes of transactional data, mining on a single machine may become prohibitively slow or exceed available memory. Parallel algorithms distribute the mining process across multiple processors or computing nodes, enabling different portions of the search space or database to be processed simultaneously. Frameworks such as MapReduce and Apache Spark provide scalable implementations of algorithms like Apriori and FP-Growth, making association rule mining practical for big data applications. Similarly, incremental and streaming algorithms address scenarios in which new transactions continuously arrive. Instead of repeatedly mining the entire database from scratch, these methods update previously discovered patterns as new data become available, making them suitable for applications such as online retail, web clickstream analysis, and sensor data processing.
Beyond computational optimizations, numerous algorithms have been developed to discover patterns that better reflect practical business objectives. Constraint-based algorithms restrict the mining process to rules satisfying user-defined conditions, such as mandatory items or minimum lift, thereby reducing the search space and producing more relevant results. High-utility itemset mining extends classical association rule mining by considering factors such as profit, cost, or quantity rather than frequency alone, enabling the discovery of high-value purchasing patterns. Other approaches, including top-*k* association rule mining, eliminate the need to specify a minimum support threshold by directly identifying the highest-ranked rules according to an interestingness measure. Together, these specialized algorithms demonstrate that association rule mining remains an active area of research, continuously evolving to address new data characteristics, computational challenges, and application requirements.
Summary¶
In this notebook, we introduced Association Rule Mining (ARM) as one of the fundamental tasks in data mining for discovering meaningful relationships and co-occurrence patterns within large transactional datasets. By identifying associations between items, ARM enables organizations to transform raw data into actionable knowledge that supports informed decision-making. Its applications span a wide range of domains, including retail, e-commerce, healthcare, bioinformatics, cybersecurity, and recommender systems, making it one of the most widely studied and practically relevant techniques in data mining. We also motivated the task through the example of a supermarket, illustrating how association rules can support decisions related to product placement, promotions, inventory management, supply chain optimization, and customer retention.
The notebook further provided an overview of the major classes of association rule mining algorithms. We examined candidate-generation methods, which iteratively construct and prune candidate itemsets; pattern-growth methods, which avoid candidate generation by mining compressed database representations; and vertical-format methods, which efficiently computes support using transaction identifier lists. In addition, we briefly discussed several specialized variants that extend these classical approaches to address challenges such as large-scale distributed processing, streaming data, user-defined constraints, and utility-based mining.
Having established the motivation, fundamental concepts, and algorithmic landscape of association rule mining, the next step is to study the individual algorithms in greater depth. Other notebooks therefore explore important ARM algorithms in detail, explaining their underlying principles, data structures, execution steps, computational characteristics, and practical applications. This deeper understanding will provide the foundation for selecting and applying appropriate association rule mining techniques to real-world data analysis problems.