Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 39 ยท Association Rules

The FP-Growth Algorithm

Learn FP-Growth, the faster alternative to Apriori: build a compact FP-tree, mine conditional pattern bases recursively, and compare results with Apriori in Python.

Apriori is easy to understand but slow: it makes one pass over the data per level and generates huge sets of candidates. FP-Growth (frequent pattern growth) avoids both. It compresses the whole database into a small tree, the FP-tree, then mines that tree recursively without ever generating candidate itemsets. It needs only two scans of the data and is usually far faster, especially when patterns are long.

The idea in three steps

  1. Scan 1: count each item; drop items below min_sup.
  2. Scan 2: sort each transaction's frequent items by descending global frequency and insert it into a prefix tree. Transactions with the same beginning share a path and increment its counts, so common patterns are stored once.
  3. Mine: for each item, collect its conditional pattern base (the prefix paths leading to it), build a conditional FP-tree from it and recurse. Items are combined with the suffix to form frequent itemsets.

Sorting by frequency matters: the most common items sit near the root and are shared by many transactions, which makes the tree small.

flowchart TD
    R["root"] --> B["bread: 4"]
    R --> M["milk: 1"]
    B --> BM["milk: 3"]
    B --> BD["diaper: 1"]
    BM --> BMD["diaper: 2"]
    M --> MD["diaper: 1"]

A small FP-tree. Counts show how many transactions pass through each node.

Building the tree

Python Construct an FP-tree and print it

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The header table keeps, for each item, a list of all its nodes in the tree. It is the entry point for mining.

Mining: conditional pattern bases

Take the item beer. Every node of beer has a path above it (its prefix path), for example bread -> diaper with count 2. The collection of these prefix paths, each weighted by the node's count, is the conditional pattern base of beer. Build a small FP-tree from it (only items frequent within the base), and recursion finds all frequent itemsets that end with beer.

Python Complete FP-Growth

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Verify against Apriori

Two correct algorithms must find exactly the same frequent itemsets. This check on random data is a good habit for any mining code.

Python FP-Growth equals brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Why it is faster

Apriori FP-Growth
Passes over the data One per level Two
Candidate generation Yes, can be huge None
Memory Candidate sets The FP-tree (compact when patterns repeat)
Weak spot Long patterns, low support Tree may not fit in memory if little overlap

The compression comes from shared prefixes. If transactions are very diverse (little overlap), the tree is almost as large as the data, and the advantage shrinks. Variants include Eclat (a vertical format: each item stores the set of transaction ids and supports are set intersections), FP-Max for maximal itemsets and FP-Close for closed ones, covered in Association Rule Types and Measures.

Python Eclat in six lines: vertical layout and intersections

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many scans of the database does FP-Growth need to build its tree?

    One scan counts items; the second inserts the sorted transactions into the tree.
  2. 2. Why are items sorted by descending frequency before insertion?

    Frequent items shared by many transactions form common prefixes that merge into single paths.
  3. 3. A conditional pattern base of item x is:

    It collects the paths above each node of x, which are mined recursively.
  4. 4. Which of the following does FP-Growth avoid?

    It grows patterns from the tree instead of generating and testing candidates.

Summary

  • FP-Growth compresses transactions into an FP-tree using two scans and shared prefixes.
  • It mines the tree recursively through conditional pattern bases, with no candidate generation.
  • It finds the same frequent itemsets as Apriori, usually much faster.
  • Weak spot: very diverse data, where the tree has little sharing.
  • Eclat (vertical tid-sets) is another candidate-free approach.

Next: Association Rule Types and Measures