API Reference / algorithms / associations /

fpgrowth.py

FP-Growth algorithm for association rule mining.

Classes

FPNode

class algorithms.associations.fpgrowth.FPNode

Node in the FP-Tree.

FPTree

class algorithms.associations.fpgrowth.FPTree

FP-Tree data structure for efficient frequent pattern mining.

Constructor 
__init__(
    self,
)

Methods

__init__ (self)
insert_transaction (self, transaction: List[int], count: int=1) -> None

Insert a transaction into the tree.

Parameters
transaction
list of int
Ordered list of items in the transaction.
count
int = 1
The count to add for each item along the path.
get_prefix_path (self, node: FPNode) -> tuple

Get the prefix path ending at node.

Parameters
node
FPNode
The node whose prefix path is to be extracted.
Returns
path
list of int
Items on the path from root to the node's parent (in root-to-leaf order).
count
int
The count at the given node.
get_conditional_pattern_base (self, item: int) -> List[tuple]

Get conditional pattern base for an item.

Parameters
item
int
The item for which to extract the conditional pattern base.
Returns
patterns
list of tuple
List of (path, count) tuples representing prefix paths.

FPGrowthAssociator

class algorithms.associations.fpgrowth.FPGrowthAssociator(Associator)

FP-Growth algorithm for association rule mining.

The FP-Growth (Frequent Pattern Growth) algorithm is a more efficient alternative to Apriori. It avoids expensive candidate generation by representing the transaction database as a compact FP-tree data structure and discovers frequent patterns by recursively exploring conditional FP-trees.
Constructor 
__init__(
    self,
    min_support: float = 0.1,
    min_confidence: float = 0.8,
    max_itemset_size: Optional[int] = None,
)

Overview

The algorithm operates in two main phases:

  1. FP-tree construction: Scan the database once to find frequent 1-itemsets, then scan again to insert each transaction (sorted by descending frequency) into the FP-tree
  2. For each item in ascending frequency order, extract its conditional pattern base (prefix paths ending at nodes for that item)
  3. Build a conditional FP-tree from the conditional pattern base
  4. Recursively mine the conditional FP-tree to discover longer frequent patterns
  5. Combine prefix patterns to form all frequent itemsets
  6. Generate association rules from the complete set of frequent itemsets

Theory

The FP-tree achieves compression by sharing common prefixes among transactions. A header table links all nodes for the same item, enabling efficient traversal.

For an itemset X, the support is obtained from the FP-tree as:

\text{support}(X) = \frac{\text{count}(X)}{|T|}

where \text{count}(X) is derived from the conditional pattern base of the least frequent item in X.

Confidence and Lift for a rule A \Rightarrow C:

\text{confidence}(A \Rightarrow C) = \frac{\text{support}(A \cup C)}{\text{support}(A)}
\text{lift}(A \Rightarrow C) = \frac{\text{confidence}(A \Rightarrow C)}{\text{support}(C)}

The FP-tree completeness theorem guarantees that the FP-tree contains all information needed for mining frequent patterns, with no information loss compared to the original database.

Parameters

min_support
float = 0.1
Minimum support threshold. Expressed as a fraction of the total number of transactions.
min_confidence
float = 0.8
Minimum confidence threshold for rule generation. Rules with confidence below this value will be discarded.
max_itemset_size
int or None = None
Maximum size of frequent itemsets to discover. If None, no limit is applied.

Attributes

frequent_itemsets_
list of FrequentItemset
The discovered frequent itemsets and their support counts.
rules_
list of AssociationRule
The association rules generated from the frequent itemsets.
n_transactions_
int
The total number of transactions processed during fit.
n_items_
int
The number of unique items encountered in the data.

Notes

Complexity:

  • FP-tree construction: O(n \cdot m) where n = number of transactions and m = average transaction length
  • Space: O(n \cdot m) worst case for the FP-tree, but typically much smaller due to prefix sharing
  • Mining: depends on the tree structure; highly compressed trees lead to faster mining
When to use FPGrowthAssociator:
  • Large datasets where Apriori's multiple database scans are prohibitive
  • When the transaction database has many shared prefixes (high compression)
  • Dense datasets with many frequent items
  • When you want to avoid candidate generation overhead entirely

References

Han2000
Han, J., Pei, J. and Yin, Y. (2000). Mining Frequent Patterns Without Candidate Generation. Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, pp. 1-12. DOI: 10.1145/342009.335372
Han2004
Han, J., Pei, J., Yin, Y. and Mao, R. (2004). Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach. Data Mining and Knowledge Discovery, 8(1), pp. 53-87. DOI: 10.1023/B:DAMI.0000005258.31418.83

See Also

AprioriAssociator

Classic level-wise breadth-first association rule mining.
ECLATAssociator

Equivalence class based frequent itemset mining using vertical data layout.

Basic usage for discovering association rules from transaction data:

python 
>>> from tuiml.algorithms.associations import FPGrowthAssociator
>>> transactions = [['milk', 'bread', 'butter'], ['beer', 'diapers'],
...                 ['milk', 'diapers', 'beer', 'cola'], ['bread', 'milk', 'diapers', 'beer']]
>>> model = FPGrowthAssociator(min_support=0.5, min_confidence=0.7)
>>> model.fit(transactions)
FPGrowthAssociator(n_itemsets=11, n_rules=18, min_support=0.5)

Methods

get_parameter_schema (cls) -> Dict[str, Dict[str, Any]]

Return parameter schema.

get_capabilities (cls) -> List[str]

Return algorithm capabilities.

get_complexity (cls) -> str

Return time/space complexity.

get_references (cls) -> List[str]

Return academic references.

fit (self, X) -> 'FPGrowthAssociator'

Find frequent itemsets and generate association rules.

Parameters
X
array-like or list of lists
The transaction data. Can be a binary matrix of shape (n_transactions, n_items) or a list of transactions where each transaction is a list of items.
Returns
self
FPGrowthAssociator
Returns the fitted associator instance.
__repr__ (self) -> str

String representation.