API Reference / algorithms / associations /

apriori.py

AprioriAssociator algorithm for association rule mining.

Classes

AprioriAssociator

class algorithms.associations.apriori.AprioriAssociator(Associator)

AprioriAssociator algorithm for association rule mining.

AprioriAssociator is the classic algorithm for discovering frequent itemsets and generating association rules. It uses the apriori property -- that all subsets of a frequent itemset must also be frequent -- to efficiently prune the search space via a level-wise breadth-first candidate generation strategy.
Constructor 
__init__(
    self,
    min_support: float = 0.1,
    min_confidence: float = 0.8,
    max_itemset_size: Optional[int] = None,
    metric: str = 'confidence',
)

Overview

The algorithm operates in iterative passes over the transaction database:

  1. Scan the database to find all frequent 1-itemsets (single items meeting min_support)
  2. Generate candidate k-itemsets by joining frequent (k{-}1)-itemsets
  3. Prune candidates whose (k{-}1)-subsets are not all frequent (apriori property)
  4. Scan the database again to count support for remaining candidates
  5. Repeat steps 2--4 until no new frequent itemsets are found
  6. Generate association rules from all discovered frequent itemsets

Theory

The key metrics for association rule mining are defined as follows.

For a rule A \Rightarrow C:

Support measures how frequently the itemset appears in the database:

\text{support}(A \Rightarrow C) = P(A \cup C) = \frac{|\{t \in T : A \cup C \subseteq t\}|}{|T|}

Confidence measures reliability of the rule:

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

Lift measures the degree to which A and C are independent:

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

A lift value of 1 indicates independence; values greater than 1 indicate positive correlation.

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.
metric
str = 'confidence'
The metric used to rank and filter the discovered rules. Options include: 'confidence', 'lift', 'leverage', 'conviction', 'jaccard', 'kulczynski', 'all_confidence'.

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:

  • Training: O(2^m) worst case where m is the number of items, though the apriori pruning typically reduces this dramatically
  • Each pass requires O(n \cdot c_k) where n = number of transactions and c_k = number of candidates at level k
  • Space: O(c_k) for storing candidate itemsets at each level
When to use AprioriAssociator:
  • When you need a well-understood, transparent algorithm for mining association rules
  • Sparse datasets where the number of frequent itemsets is manageable
  • When interpretability of the mining process is important
  • Smaller to medium datasets where multiple database scans are acceptable

References

Agrawal1994
Agrawal, R. and Srikant, R. (1994). Fast Algorithms for Mining Association Rules in Large Databases. Proceedings of the 20th International Conference on Very Large Data Bases (VLDB), pp. 478-499.
Agrawal1993
Agrawal, R., Imielinski, T. and Swami, A. (1993). Mining Association Rules Between Sets of Items in Large Databases. Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, pp. 207-216. DOI: 10.1145/170035.170072

See Also

ECLATAssociator

Equivalence class based frequent itemset mining using vertical data layout.
FPGrowthAssociator

FP-tree based frequent pattern mining without candidate generation.

Basic usage for discovering association rules from transaction data:

python 
>>> from tuiml.algorithms.associations import AprioriAssociator
>>> transactions = [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
>>> apriori = AprioriAssociator(min_support=0.5, min_confidence=0.7)
>>> apriori.fit(transactions)
AprioriAssociator(n_itemsets=6, n_rules=4, min_support=0.5)
>>> rules = apriori.get_rules()

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) -> 'AprioriAssociator'

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) where 1 indicates presence, or a list of transactions where each transaction is a list/set of item indices or names.
Returns
self
AprioriAssociator
Returns the fitted associator instance.
__repr__ (self) -> str

String representation.