Apriori Association Rule Mining in MATLAB

Association rule mining is a common data mining task. It finds frequent patterns, usually in transactional databases. For example, the rule {bread, butter} → {milk} in a sales dataset means that a customer who buys bread and butter is likely to buy milk too. You can read more in the Wikipedia article on association rule learning (opens in a new tab).

One of the basic methods for this problem is the Apriori algorithm, proposed by Rakesh Agrawal and Ramakrishnan Srikant in 1994. It starts by identifying frequent individual items in the dataset. Then it extends them to larger item sets, as long as those item sets appear often enough in the database to give useful rules. You can read more in the Wikipedia article on the Apriori algorithm (opens in a new tab).

This post shares a MATLAB implementation of Apriori association rule mining. The code is structured, so if you know MATLAB, you will find it easy to use in your research projects.

The problem

The data is a set of $N$ transactions. Each transaction is a set of items, for example the products in one shopping basket. A rule $X \to Y$ links two disjoint item sets: when a transaction contains $X$, it often contains $Y$ as well. Three standard measures describe how useful a rule is.

Support is the share of transactions that contain all the items of the rule:

Confidence is the share of transactions with $X$ that also contain $Y$. It estimates the conditional probability of $Y$ given $X$:

Lift compares the confidence with the overall frequency of $Y$:

A lift above 1 means that $X$ and $Y$ co-occur more often than expected under independence using the observed frequencies. A lift of 1 matches that independence baseline in the sample.

How Apriori works

Apriori uses one simple fact: every subset of a frequent item set is also frequent. So a large item set can only be frequent if it is built from smaller frequent item sets. The algorithm works level by level:

1. Count every single item and keep those whose support is at least the minimum support threshold.
2. Build candidate item sets of size $k + 1$ from the frequent item sets of size $k$, count them in the data, and keep the frequent ones.
3. Repeat until no new frequent item set is found.
4. For every frequent item set with two or more items, split it in all possible ways into $X$ and $Y$, and compute the support, confidence and lift of each rule $X \to Y$.

In this code, step 2 adds one more item to each frequent item set, using only the items that appear in the frequent sets of the current level. The rules are sorted by confidence, and the final rules are those with a confidence of at least the minimum confidence threshold and a lift of at least 1.

How to run it

Run main.m in MATLAB. It loads the transactions T from mydata.mat, calls the main function, and prints the final rules with their support, confidence and lift:

MST=0.22;   % Minimum Support Threshold

MCT=0.6;    % Minimum Confidence Threshold

[FinalRules, Rules]=Apriori(T,MST,MCT);

The sample data has nine transactions over five items, numbered 1 to 5. T is a cell array, and each cell holds the item numbers of one transaction, for example [1 2 5]. To mine your own data, store your transactions in the same form and adjust the two thresholds. Rules holds all the rules before the final selection.

The download has these files:

• Apriori.m: the algorithm.
• main.m: the example script.
• DisplayRules.m: prints the rules.
• GetNonTrivialSubsets.m and IsSame.m: helper functions.
• mydata.mat: the sample transactions.

Check the result

Use one occurrence of each item per transaction and keep item identifiers consistent across the data. The nine-transaction example illustrates counting rather than evidence for a business decision. Review support counts as well as confidence and lift, then check promising rules on separate transactions. High confidence can come from a common consequent, and association does not establish causation.

Applications

Association rules are used in market basket analysis, product recommendations and store layout, and also in web usage mining, the analysis of medical records and the study of other kinds of event data.