Association Rule Mining

What else do customers who buy coffee at an online store tend to buy? Which features do people who use a particular service tend to use together? What do survey respondents who chose several of the same options have in common?

The method for finding patterns of items that appear together in data is called association rule mining.

Association rule mining is best known as market basket analysis, which finds relationships between products in customers’ purchase records. But beyond purchases, it can be used to analyze any data where several items appear together, such as website usage logs, service usage patterns, and multiple-choice survey answers.

In particular, it shows which item combinations occur often, and how often another item also appears when one item appears.

In this lesson we cover the basic idea of association rule mining, what support, confidence and lift mean, the Apriori and ECLAT algorithms, a worked example, and what to watch out for when interpreting the results.

For example, suppose a store analyzes the purchase records of 1,000 customers. Some customers bought only coffee, while others bought coffee and bread together, or milk and cereal together. Association rule mining compares these transaction records to see which products often appear together.

The results are usually expressed as rules like this.

This rule shows a tendency for bread to also be bought in transactions where coffee was bought. The arrow here does not mean a time order, as in buying coffee first and then bread. It simply expresses the relationship that bread also appears in transactions that include coffee.

Also, finding such a rule does not mean that buying coffee causes people to buy bread. Association rule mining is a method for finding co-occurrence patterns among items, not a method for testing causal relationships.

If there are only a few transactions, a person can look through them directly, but with thousands of products and hundreds of thousands of transactions, it is hard to check every combination.

For example, suppose coffee is a store’s best-selling product. A simple frequency analysis can confirm that coffee sells well, but it is hard to tell from that what else coffee buyers purchase along with it.

Association rule mining goes beyond the frequency of individual items and looks at combinations of items. This lets you discover products that are often bought together, customer behavior such as using certain features together, and choice patterns that repeat across several survey questions.

These results can be used for product recommendations, bundling, store displays, service improvements, exploring customer behavior, and more. Whether a discovered rule actually leads to higher sales or changes in customer behavior, though, has to be verified separately.

Here A is called the antecedent and B the consequent. For example, in the rule ‘coffee → bread’, coffee is the antecedent and bread is the consequent. It describes a pattern in which bread appears in transactions that include coffee.

A rule does not have to consist of one product and one product. Several items can be combined. For example, a rule like this is also possible.

To evaluate such rules numerically, association rule mining uses measures such as support, confidence and lift.

Support

Support is the proportion of all transactions in which certain items appear together. For example, if 120 of 1,000 transactions include both coffee and bread, the support is 0.12. This means coffee and bread were bought together in 12% of all transactions.

Support shows how often a rule is observed across the whole dataset. Be careful with rules that have very low support, since they may be chance patterns that appeared in only a handful of transactions.

Confidence

Confidence is the proportion of transactions containing the antecedent A that also contain the consequent B. For example, if 300 transactions included coffee and 120 of them also included bread, the confidence is 0.40. In other words, bread was also bought in 40% of the transactions where coffee was bought.

Confidence shows the conditional rate of a rule, but it can also be high simply because the consequent itself is very common. So it is not appropriate to judge how important a rule is from confidence alone.

Lift

Lift compares the rate at which the consequent appears when the antecedent is present with the consequent’s overall rate. It is usually interpreted as follows.

A lift of 1.5 means that the rate at which B appears in transactions containing A is 1.5 times the rate at which B appears across all transactions. A high lift, however, does not always make a rule important. High lift can also show up for product combinations that occur very rarely, so check the support and the number of transactions as well.

The goal is to see whether bread tends to be bought in transactions where coffee is bought. The transaction records collected are as follows.

Let’s use these results to calculate the association rule ‘coffee → bread’.

① Calculating support

Of all 1,000 transactions, 120 included both coffee and bread. Support = 120 ÷ 1,000 = 0.12 So the support is 12%.

② Calculating confidence

Of the 300 transactions that included coffee, 120 also included bread. Confidence = 120 ÷ 300 = 0.40 So the confidence is 40%.

③ Calculating lift

The proportion of all transactions that included bread is 250 ÷ 1,000 = 0.25. Lift = 0.40 ÷ 0.25 = 1.60 So the lift is 1.60.

Association rule results

How do we interpret the results?

Coffee and bread were bought together in 12% of all transactions. Bread was also bought in 40% of transactions that included coffee, and the rate at which bread appeared in transactions with coffee was 1.6 times the overall rate of bread purchases. So we can say there is a positive association between coffee and bread.

This result can inform decisions such as recommending bread to coffee buyers or considering a bundle of the two products. Whether such strategies actually increase sales, though, has to be checked through a separate experiment or performance analysis.

‘Coffee → bread’ and ‘bread → coffee’ involve the same product combination but represent different conditional rates. In the example above, 300 transactions included coffee, 250 included bread, and 120 included both. Calculating on this basis gives the following.

The two rules have the same support and lift but different confidence. That is because 40% of transactions with coffee also included bread, while 48% of transactions with bread also included coffee. This shows that swapping a rule’s antecedent and consequent changes the base of the conditional rate.

So in association rule mining, you need to be clear about which item you are using as the base when looking at the co-occurrence of other items.

Apriori is an algorithm that searches step by step for item combinations that often appear together. For example, suppose we analyze the purchase records of many products at a store, such as coffee, bread, milk, cereal and snacks.

Apriori first checks how often each individual product appears, then combines the frequently appearing products to search for 2-item itemsets. It then uses the combinations that meet the criteria to search for itemsets of three or more items.

An important criterion here is the minimum support. For example, if the minimum support is set at 5%, item combinations that appear in less than 5% of all transactions are excluded from the frequent itemset search. Apriori relies on the principle that for an itemset to be frequent, all of its subsets must also be frequent.

For example, if the combination of coffee and bread does not meet the minimum support, a combination containing coffee, bread and milk cannot meet it either. This principle is used to cut down unnecessary candidate combinations.

Features of Apriori

Because Apriori generates candidate itemsets step by step, how it works is easy to understand. After finding frequent combinations based on the minimum support, it can generate association rules by applying criteria such as confidence.

However, when there are many kinds of products and the number of possible combinations grows sharply, generating candidate itemsets and scanning the data can become computationally expensive. So depending on the size and structure of the data, other algorithms may be more efficient.

It differs, however, in how it searches the data. Whereas Apriori generates and checks product combinations in transactions step by step, ECLAT uses the set of transaction IDs that contain each product. For example, suppose we have the following purchase records.

ECLAT can represent this data as transaction IDs for each product.

To find the transactions in which coffee and bread appear together, we take the intersection of the two transaction ID sets. Coffee ∩ Bread = T1, T3, T5 So 3 transactions include both coffee and bread.

In this way, ECLAT uses intersections of transaction ID sets to count how often several products occur together.

Features of ECLAT

Because ECLAT uses a vertical data layout and set operations, it can search for frequent itemsets efficiently depending on the structure of the data. But since it has to store and process transaction ID sets, it can be affected by the size and density of the data and by memory use.

So we cannot conclude that ECLAT is faster than Apriori in every situation.

The biggest differences between them lie in how they search for item combinations and how they represent the data.

For example, in data with many kinds of products and complex combinations, the two algorithms may perform differently. But if they search exactly, using the same minimum support and the same transaction data, the two algorithms should in principle find the same frequent itemsets.

So it is not that the meaning of the results differs; rather, the way the results are computed differs.

Also, the core task that Apriori and ECLAT themselves perform is finding frequent itemsets. To get the final association rules, an extra step is needed: generating rules from the itemsets found and evaluating them by criteria such as confidence and lift.

Minimum support

The minimum support determines at least how often an item combination must appear across all transactions. For example, setting the minimum support at 5% means searching for itemsets that appear in at least 5% of all transactions.

Setting it too high can miss important rare patterns. Setting it too low, on the other hand, can turn up a huge number of candidate combinations, making the results hard to interpret.

Minimum confidence

The minimum confidence is a threshold on the proportion of transactions containing a rule’s antecedent that also contain its consequent. For example, setting the minimum confidence at 60% means keeping, among the rules generated from the frequent itemsets that meet the criteria, those with a confidence of 60% or more.

A rule with high confidence, however, is not necessarily meaningful. If the consequent itself appears in nearly every transaction, confidence can be high even without any special relationship to the other item. So it is good to check not only support and confidence but also lift and the actual number of transactions.

For example, suppose we got the following results.

In these results, the rule milk → cereal has the highest lift, at 2.10. This means the rate at which cereal appears in transactions containing milk is 2.1 times the overall rate of cereal.

The rule snacks → drinks, on the other hand, has a high confidence of 70% but a lift of only 1.05. If drinks are a commonly bought product in their own right, the association may not be particularly strong even though a high proportion of snack buyers also buy drinks. So if you rank rules by confidence alone, you may miss the combinations that are actually distinctive.

When interpreting the results, it is good to consider together how often a rule occurs, its conditional rate, its association relative to the overall rate, and how usable it is in practice.

In such cases you can use scatter plots, network graphs, matrix visualizations, and so on.

Association rules scatter plot

A scatter plot shows each association rule as a single point. For example, you can put support on the horizontal axis and confidence on the vertical axis, and show lift with the color or size of the points. This lets you compare rules that appear often with rules that have a high conditional rate.

Network graph

A network graph shows products or items as nodes and the rules between them as links. For example, if there are several rules among coffee, bread, milk and cereal, you can see visually which products are connected to each other.

Keep in mind, though, that the arrows in association rules do not indicate causation or purchase order.

Matrix visualization

A rule matrix places combinations of antecedents and consequents in rows and columns, and shows each rule’s support or lift with color. When the number of items is fairly limited, it helps you see which combinations have strong associations.

For example, if you want to know whether customers who spend more also visit more often, you could consider correlation analysis. If instead you want to know how often bread or milk appears in transactions that include coffee, association rule mining is more appropriate.

Both methods deal with relationships among variables, but association rule mining focuses on exploring combinations of many items.

Association does not imply causation.

Coffee and bread being bought together often does not mean buying coffee leads people to buy bread. There may be other reasons, such as the two products being consumed at the same time of day or being preferred together by a particular group of customers. So rules should be interpreted as co-occurrence patterns.

Be careful with low-support rules.

A rule that appears in only a very few transactions may be a chance pattern. In particular, even if the lift is high, the result can be unstable if the actual number of transactions is small. So it is good to check the support and the actual number of transactions together.

Too many rules may be found.

When there are many kinds of products or the minimum support is low, a very large number of rules can be generated. These may include patterns that are similar to or duplicate one another. So in real analyses, set criteria such as minimum support, minimum confidence and lift, and prune duplicate or low-value rules as needed.

Define the unit of data collection clearly.

In association rule mining, what counts as one transaction matters. For example, you might use a single shopping basket as the transaction unit, or group one customer’s purchases over a period into a single transaction. Even from the same raw data, the association rules can differ depending on how the transaction unit is defined.

So set a transaction unit that fits the purpose of the analysis.

Take changes over time into account.

Purchase patterns can change with the season, sales promotions, new product launches, shifts in consumer behavior, and so on. For example, analyzing summer and winter purchase records together can dilute patterns that appear only at certain times. So it can also help to compare association rules across periods as needed.

Check whether the rules hold up in new data.

If you search through a very large number of association rules, you may find rules with high lift or confidence purely by chance. So it is good to check whether important rules also hold in data from other periods or in a separate validation dataset.

Retail and e-commerce

Explore products bought together and review product recommendations, bundling, store display strategies, and more.

Marketing and customer analytics

Analyze customer behavior patterns by identifying product categories customers buy together or services they use at the same time.

Surveys

Identify combinations of options that respondents often choose together in multiple-choice questions. For example, you can analyze combinations of the social media platforms people use or the service features they prefer.

Website and service usage analysis

Explore features that users use together or combinations of behaviors that recur.

Health and medical data analysis

Explore patterns of symptoms or health-related items that are observed together. But discovered rules should not be interpreted directly as causes of disease or as grounds for diagnosis.

Education research

Look at combinations of learning content or learning activities that learners use together. As these examples show, association rule mining is used not just to see which items appear often, but to understand in what combinations several items appear.

Using the store purchase data example from earlier, a write-up might look like this.

Reporting results this way conveys concretely how often the items appeared together and by what criteria the association was found, rather than just saying the two products are related. In real analyses, it is good to also report the algorithm used, the transaction unit, the data collection period, the rule search criteria, and so on.

It typically uses support, confidence and lift to evaluate how often a rule occurs and how strong the relative association is. Various algorithms, such as Apriori and ECLAT, can be used to find frequent itemsets.

But high confidence or lift does not necessarily make a rule important. You need to consider the actual number of transactions, how common the items are, the data collection conditions, the intended use, and so on. Above all, be careful not to interpret discovered rules as causal relationships.