FP-Growth Association Rule Mining in MATLAB

Like Apriori, FP-Growth is an association rule mining method. FP stands for Frequent Pattern. FP-Growth uses a frequent pattern mining technique to build a tree of frequent patterns (the FP-Tree), and the tree is used to extract association rules. The method was proposed by Jiawei Han, Jian Pei and Yiwen Yin in 2000. The published algorithm avoids Apriori-style candidate generation and can be efficient on suitable transaction data. The teaching implementation here uses a different mining step, so that performance claim does not establish its scalability. For more information, see the Wikipedia article on FP-growth (opens in a new tab).

The problem

The data is a set of $N$ transactions, and each transaction is a set of items. The goal is to find the item sets that appear in at least a given share of the transactions (the minimum support), and then the rules $X \to Y$ between them that have a high confidence. Support, confidence and lift are defined in the Apriori post:

Why a tree

Apriori creates many candidate item sets and scans the whole database to count each level. FP-Growth avoids this. It stores all the transactions once in a compact prefix tree, and then reads the counts of the patterns from the tree.

How the FP-Tree is built

1. Count how often each item appears, and sort the items by frequency in descending order.
2. Start with an empty root node.
3. For each transaction, sort its items in this order and insert them as a path from the root. If the path already starts with the same items, the transaction follows the existing nodes and increases their counts. Only the part that differs creates new nodes.

Because frequent items come first, many transactions share the beginning of their paths. This is what makes the tree small. Each node stores its item, its count and the path from the root to it.

How the patterns and rules are found

In the original algorithm, FP-Growth mines the tree recursively: for each item it collects the paths that end in that item (its conditional pattern base), builds a smaller conditional tree from them, and repeats.

This code uses a simpler approach that is easy to follow. For each node, it creates every pattern made of the node’s item and any subset of the items above it on its path, with the node’s count. These patterns and counts are passed up to the root, where the counts of the same pattern are added up. The patterns whose support is at least the minimum support threshold are the frequent patterns.

Then every frequent pattern with two or more items is split in all possible ways into $X$ and $Y$, and the support, confidence and lift of each rule $X \to Y$ are computed. The final rules are those with a confidence of at least the minimum confidence threshold and a lift of at least 1.

MATLAB implementation

This post shares an open-source implementation of FP-Growth association rule mining in MATLAB. The code is structured, so if you know MATLAB, you should find it easy to use in your research projects.

Run main.m in MATLAB. It loads the transactions T from mydata.mat, runs the algorithm, draws the FP-Tree with PlotTree.m, and prints the final rules with their support, confidence and lift:

MST=2/9;    % Minimum Suppport Threshold

MCT=0.6;    % Minimum Confidence Threshold

out=FPGrowth(T,MST,MCT);

The sample data is the same as in the Apriori post: nine transactions over five items, numbered 1 to 5, stored as a cell array of item vectors. A minimum support of 2/9 means that a pattern must appear in at least two transactions. The output structure out holds the tree (out.Node), the frequent patterns and their counts, all the rules, and the final rules (out.FinalRules).

The download has these files:

• FPGrowth.m: the algorithm.
• main.m: the example script.
• PlotTree.m: draws the FP-Tree.
• DisplayRules.m: prints the rules.
• GetPowerSet.m, GetNonTrivialSubsets.m and IsSame.m: helper functions.
• mydata.mat: the sample transactions.

Check the result

Compare the reported support counts with the Apriori example on the same nine transactions. The code enumerates subsets of node paths, which can become expensive when transactions contain many items. Tree compression alone does not establish a fast end-to-end run. Keep transactions as sets with consistent item identifiers, and interpret confidence and lift as sample associations rather than causal effects.

Applications

Like other association rule methods, FP-Growth is used in market basket analysis, product recommendations, web usage mining and the analysis of other event data. The implementation here should be evaluated on the intended data before it is used at larger scale.