MENTAL MODEL · M6631

Frequent Pattern Growth

TechnicalmediumAlgorithms

Included

Updated 2026-08-09

Loading revision record…

INTRODUCTION

English translation pending.

CORE DEFINITION

Frequent Pattern Growth (FP-Growth) is a frequent itemset mining algorithm introduced by Jiawei Han, Jian Pei, and Yiwen Yin in 2000. It builds an FP-tree, a prefix tree that compresses the transaction database by sharing common prefixes, together with a header table that orders frequent items by descending frequency and links their occurrences. Mining then proceeds by extracting conditional pattern bases and recursing on each frequent item, so no candidate itemsets are generated. The algorithm requires two scans of the database, one to count frequencies and one to build the tree, and its main constraint is memory, since the tree must fit in main memory.

SCAFFOLDING EFFECT

psychology

Reduce cognitive load

- Use tree compression: store transactions as shared prefixes rather than as a flat list of records. - Use frequency ordering: sort items by descending count so the tree stays shallow. - Use recursive decomposition: mine each frequent item by following its conditional pattern base.

anchor

Anchor fast decisions

Apriori spends most of its cost generating and testing candidate itemsets, and each test requires scanning the database again. FP-Growth removes that cost by building a structure in which every path encodes a set of co-occurring items, so support counts can be read from the tree rather than recomputed. Sharing prefixes collapses repeated transactions into single paths, and ordering items by frequency maximizes that sharing. Mining then decomposes the problem into independent subproblems, one per frequent item, which are solved recursively without any candidate generation.

MINIMUM ACTION

In progress 0/1

Practice this model in one real situation:

Scan the database once to count item frequencies. 2. Discard items below the minimum support threshold. 3. Scan again and insert transactions into an FP-tree in descending frequency order. 4. Build the header table linking all nodes for each frequent item. 5. Mine frequent patterns recursively from each item's conditional pattern base.

Check to track your progress (stored locally)

Learning progress0%

account_treeGenealogyexpand_more

menu_bookReferencesexpand_more

Source support: Explicit

link
en.wikipedia.orghttps://en.wikipedia.org/wiki/Association_rule_learningZH · Explicit
verified

RELATED MODELS