API Reference / algorithms / associations /

eclat.py

ECLATAssociator algorithm for association rule mining.

Classes

ECLATAssociator

class algorithms.associations.eclat.ECLATAssociator(Associator)

ECLATAssociator algorithm for association rule mining.

ECLATAssociator (Equivalence CLAss Transformation) uses a vertical data layout (storing transaction IDs for each item) and depth-first search to find frequent itemsets. It is often faster than Apriori for dense datasets because it avoids expensive candidate generation by intersecting transaction ID sets (tidsets).
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 on a vertical representation of the database:

  1. Convert the horizontal transaction database to a vertical format where each item maps to its set of transaction IDs (tidset)
  2. Filter items whose tidset size is below the minimum support count
  3. Sort frequent items by ascending support (heuristic for faster intersections)
  4. For each frequent item, recursively extend the itemset by intersecting tidsets with remaining items
  5. If the intersection meets the minimum support, record the new frequent itemset and recurse deeper
  6. Generate association rules from all discovered frequent itemsets

Theory

ECLAT exploits the equivalence class property of itemsets. Two itemsets belong to the same equivalence class if they share the same (k{-}1)-prefix.

The support of an itemset X is computed directly from its tidset:

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

where T is the set of all transactions. To compute the tidset of X \cup Y:

\text{tidset}(X \cup Y) = \text{tidset}(X) \cap \text{tidset}(Y)

Confidence and Lift for a rule A \Rightarrow C are:

\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)}

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:

  • Space: O(n \cdot m) for the vertical database where n = number of transactions and m = number of items
  • Time: O(2^m) worst case, but typically much faster due to tidset intersection pruning
  • Tidset intersection: O(\min(|t_A|, |t_B|)) per pair using sorted sets
When to use ECLATAssociator:
  • Dense datasets where many items co-occur frequently
  • When you want to avoid the multiple database scans required by Apriori
  • Datasets that fit in memory in vertical format
  • When depth-first exploration is preferred over breadth-first

References

Zaki2000
Zaki, M.J. (2000). Scalable Algorithms for Association Mining. IEEE Transactions on Knowledge and Data Engineering, 12(3), pp. 372-390. DOI: 10.1109/69.846291
ZakiHsiao2002
Zaki, M.J. and Hsiao, C.J. (2002). CHARM: An Efficient Algorithm for Closed Itemset Mining. Proceedings of the 2002 SIAM International Conference on Data Mining, pp. 457-473. DOI: 10.1137/1.9781611972726.27

See Also

AprioriAssociator

Classic level-wise breadth-first association rule mining.
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 ECLATAssociator
>>> transactions = [['bread', 'milk'], ['bread', 'diaper', 'beer', 'egg'],
...                 ['milk', 'diaper', 'beer', 'cola'], ['bread', 'milk', 'diaper', 'beer']]
>>> model = ECLATAssociator(min_support=0.5, min_confidence=0.7)
>>> model.fit(transactions)
ECLATAssociator(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) -> 'ECLATAssociator'

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
ECLATAssociator
Returns the fitted associator instance.
__repr__ (self) -> str

String representation.