Eclat

Store each itemset's list of transaction ids; the support of a union is the size of the lists' intersection.

14 min read1268 wordscore3 viewsupdated 2026-10-07

Definition

Eclat (Equivalence CLAss Transformation, Zaki 2000) finds every frequent itemset in a transaction database by flipping the data on its side: instead of storing, for each basket, the items it contains, it stores for each item the set of baskets (transaction ids) that contain it. The support of a larger itemset is then the size of an intersection of those sets, and the search proceeds depth-first, one shared prefix at a time.

At a glance

Task
Frequent-itemset mining (the first half of association-rule learning)
Input → output
transactions (sets of items) and a threshold minsup → every itemset XX with σ(X)≥\sigma(X)\ge minsup, with its support
Learns
nothing parametric — it enumerates; the output is exact, identical to Apriori and FP-Growth
Training cost
one database scan, then one list intersection per candidate; each costs O(∣t(X)∣+∣t(Y)∣)O(|t(X)|+|t(Y)|) with sorted lists or O(n/64)O(n/64) machine words with bitsets
Prediction cost
none in itself; rules derived from the itemsets are looked up in a hash map
Hyperparameters
minsup (absolute count or fraction); item order; tidsets vs diffsets; max itemset length
Assumes
the tid-lists of the current branch fit in memory; items are binary (present / absent)

The problem

Every frequent-itemset miner needs to answer one question millions of times: in how many transactions does itemset XX appear? The Apriori article covers the classic answer — generate all candidates of size kk, then rescan the whole database to count them, once per level. On a database of nn transactions and an answer with itemsets up to length LL, that is LL full passes, and each pass checks every transaction against every candidate.

The waste is that a scan for {Bread,Eggs,Milk}\{\text{Bread},\text{Eggs},\text{Milk}\} re-reads every basket, including the ones we already know do not contain Bread. We already computed which baskets contain {Bread,Eggs}\{\text{Bread},\text{Eggs}\} one level earlier — we just threw that information away and kept only the count. Eclat keeps it.

The idea

Keep, for every itemset you have found, the list of transaction ids where it occurs (its tidset). A basket contains X∪YX\cup Y exactly when it contains XX and contains YY, so the tidset of the union is the intersection of the two tidsets — and its support is just the length. No database scan is needed after the first one.

To keep the lists small and memory bounded, Eclat organises the search into equivalence classes: all itemsets that share the same prefix. Inside a class, every pair of members is joined (intersect their lists); the frequent results form a new, smaller class one level deeper, which is explored completely before moving on — a depth-first walk of the itemset lattice. Only the lists along the current path need to be held in memory.

Vocabulary

Transaction / tid
one basket, identified by a transaction id 1,…,n1,\dots,n
Itemset
a set of items, e.g. {Bread,Milk}\{\text{Bread},\text{Milk}\}; a kk-itemset has kk items
Support σ(X)
number (or fraction) of transactions containing every item of XX
Frequent itemset
one with σ(X)≥\sigma(X)\ge minsup
Horizontal layout
tid → items (how the data usually arrives; Apriori and FP-Growth read it this way)
Vertical layout
item → tidset (what Eclat builds in its single scan)
Tidset t(X)
the set of tids whose transaction contains XX; σ(X)=∣t(X)∣\sigma(X)=|t(X)|
Prefix / equivalence class [P]
all frequent itemsets that start with prefix PP (in a fixed item order); members differ only in their last item
Diffset d(PX)
the tids that contain PP but not PXPX — what is lost when XX is appended. Used by dEclat to shrink lists
Maximal / closed itemset
frequent with no frequent superset / with no superset of equal support — compact summaries of the result

The math

Let D={T1,…,Tn}D=\{T_1,\dots,T_n\} be the transactions over an item universe II. The vertical layout replaces DD by one set per item.

t(X)={ j∈{1..n}:X⊆Tj },σ(X)=∣t(X)∣t(X)=\{\,j\in\{1..n\} : X\subseteq T_j\,\},\qquad \sigma(X)=|t(X)|
TjT_j
the jj-th transaction (a set of items)
t(X)t(X)
tidset of itemset XX
σ(X)\sigma(X)
absolute support; divide by n for the relative support

The key identity. X∪Y⊆Tj  ⟺  X⊆Tj and Y⊆TjX\cup Y\subseteq T_j \iff X\subseteq T_j \text{ and } Y\subseteq T_j. Collecting the jj that satisfy each side:

t(X∪Y)=t(X)∩t(Y),σ(X∪Y)=∣t(X)∩t(Y)∣t(X\cup Y)=t(X)\cap t(Y),\qquad \sigma(X\cup Y)=|t(X)\cap t(Y)|
∩\cap
set intersection of the two tid-lists

Because t(X∪Y)⊆t(X)t(X\cup Y)\subseteq t(X), support can only shrink as itemsets grow — the anti-monotone (downward-closure) property also used by Apriori. So if ∣t(X)∩t(Y)∣<|t(X)\cap t(Y)|< minsup, the candidate is discarded and never extended: every superset would have an even smaller intersection.

Equivalence classes. Fix an order on items. For a prefix PP, the class [P]={PX1,…,PXm}[P]=\{PX_1,\dots,PX_m\} holds the frequent itemsets that extend PP by one item. Joining two members gives PXiXjPX_iX_j with

t(PXiXj)=t(PXi)∩t(PXj),[PXi]={ PXiXj:j>i, ∣t(PXi)∩t(PXj)∣≥minsup }t(PX_iX_j)=t(PX_i)\cap t(PX_j),\qquad [PX_i]=\{\,PX_iX_j : j>i,\ |t(PX_i)\cap t(PX_j)|\ge \text{minsup}\,\}
PP
the shared prefix of the class
PXiPX_i
PP extended by item XiX_i
j>ij>i
join only with later members, so each itemset is generated exactly once

Every frequent (k+1)(k{+}1)-itemset is produced exactly once this way: its two "parents" are the itemsets obtained by dropping its last and its second-to-last item, and both share the same (k−1)(k{-}1)-prefix, hence sit in the same class. The classes are independent sub-problems — the natural unit for parallel Eclat.

Diffsets (dEclat). Deep in the lattice, tidsets are long but nearly equal to their parent's: appending an item removes only a few tids. Zaki and Gouda's dEclat stores the difference instead.

d(PX)=t(P)∖t(PX),σ(PX)=σ(P)−∣d(PX)∣d(PX)=t(P)\setminus t(PX),\qquad \sigma(PX)=\sigma(P)-|d(PX)|
d(PX)d(PX)
diffset: tids that contain PP but lose XX
∖\setminus
set difference

Derivation of the join. Since t(PX)=t(P)∖d(PX)t(PX)=t(P)\setminus d(PX) and t(PY)=t(P)∖d(PY)t(PY)=t(P)\setminus d(PY), the tids that contain PXPX but not PXYPXY are those in t(PX)t(PX) but not in t(PY)t(PY): in t(P)t(P), not in d(PX)d(PX), but in d(PY)d(PY). Because d(PY)⊆t(P)d(PY)\subseteq t(P) the first condition is automatic, so

d(PXY)=t(PX)∖t(PY)=d(PY)∖d(PX),σ(PXY)=σ(PX)−∣d(PXY)∣d(PXY)=t(PX)\setminus t(PY)=d(PY)\setminus d(PX),\qquad \sigma(PXY)=\sigma(PX)-|d(PXY)|
d(PXY)d(PXY)
diffset of PXYPXY relative to its parent PXPX
σ(PX)\sigma(PX)
support of the parent, already known

At the first level there is no diffset yet, so dEclat starts with d(XY)=t(X)∖t(Y)d(XY)=t(X)\setminus t(Y) from the item tidsets and uses the second form from then on. On dense data (census, retail with a few dominant items) diffsets are often orders of magnitude smaller than tidsets; on sparse data tidsets are already short and diffsets can be longer.

What each knob does, mathematically

minsup
the pruning threshold in ∣t(PXi)∩t(PXj)∣≥|t(PX_i)\cap t(PX_j)|\ge minsup. Lowering it can grow the output exponentially: with all mm items frequent together, up to 2m−12^m-1 itemsets survive. On the example below: minsup 4 → 9 itemsets, 3 → 11, 2 → 18.
Item order
decides which pairs share a class. Sorting items by increasing support puts rare items first, so their classes are small and their intersections die early; on the example it cuts 13 list operations to 11 and diffset entries from 27 to 17.
Tidset vs diffset
same output; diffsets win when ∣d(PX)∣≪∣t(PX)∣|d(PX)|\ll|t(PX)|, i.e. when σ(PX)/σ(P)\sigma(PX)/\sigma(P) is close to 1 (dense data).
Max length
stop recursing at depth LL; bounds the 2m2^m blow-up when only short rules are wanted.

Worked example: eight baskets

A small shop records 8 baskets over 5 items — Bread, Coffee, Eggs, Jam, Milk. We want every itemset bought together in at least minsup = 3 baskets (support ≥ 3/8 = 0.375). The same data is used by the figure and both code listings.

tidItemsShort
1Bread, Milk, EggsB E M
2Bread, Coffee, JamB C J
3Bread, Milk, Eggs, JamB E J M
4Milk, Eggs, CoffeeC E M
5Bread, Milk, JamB J M
6Bread, Milk, Eggs, CoffeeB C E M
7Milk, CoffeeC M
8Bread, Eggs, JamB E J
Horizontal layout: the data as it arrives, one row per transaction.
ItemTidset t(item)Support
B (Bread){1, 2, 3, 5, 6, 8}6
C (Coffee){2, 4, 6, 7}4
E (Eggs){1, 3, 4, 6, 8}5
J (Jam){2, 3, 5, 8}4
M (Milk){1, 3, 4, 5, 6, 7}6
Vertical layout after the single scan: 25 tid entries, exactly as many as item occurrences in the horizontal table. All five items have support ≥ 3.
Pairt(X) ∩ t(Y)σKept?d(XY) = t(X) − t(Y)
BC{2, 6}2no{1, 3, 5, 8}
BE{1, 3, 6, 8}4yes{2, 5}
BJ{2, 3, 5, 8}4yes{1, 6}
BM{1, 3, 5, 6}4yes{2, 8}
CE{4, 6}2no{2, 7}
CJ{2}1no{4, 6, 7}
CM{4, 6, 7}3yes{2}
EJ{3, 8}2no{1, 4, 6}
EM{1, 3, 4, 6}4yes{8}
JM{3, 5}2no{2, 8}
Class [∅] — all 10 pairs, items in A→Z order. Five survive. The diffset column is what dEclat would store instead.

Eclat by hand (minsup = 3)

  1. 1Scan once. Build the five tidsets above. Every item has ∣t∣≥3|t|\ge3, so the first class is [∅]={B,C,E,J,M}[\varnothing]=\{B,C,E,J,M\}.
  2. 2Class [∅][\varnothing], member B. Join B with each later item: t(BC)={2,6}t(BC)=\{2,6\} (σ = 2, prune), t(BE)={1,3,6,8}t(BE)=\{1,3,6,8\} (4), t(BJ)={2,3,5,8}t(BJ)=\{2,3,5,8\} (4), t(BM)={1,3,5,6}t(BM)=\{1,3,5,6\} (4). New class [B]={BE,BJ,BM}[B]=\{BE,BJ,BM\}.
  3. 3Recurse into [B][B]. t(BEJ)=t(BE)∩t(BJ)={3,8}t(BEJ)=t(BE)\cap t(BJ)=\{3,8\} → 2, prune. t(BEM)=t(BE)∩t(BM)={1,3,6}t(BEM)=t(BE)\cap t(BM)=\{1,3,6\} → 3, keep. t(BJM)={3,5}t(BJM)=\{3,5\} → 2, prune. Class [BE]={BEM}[BE]=\{BEM\} has one member — nothing to join, so this branch is finished.
  4. 4Back in [∅][\varnothing], member C. t(CE)={4,6}t(CE)=\{4,6\} (2), t(CJ)={2}t(CJ)=\{2\} (1), t(CM)={4,6,7}t(CM)=\{4,6,7\} (3). Class [C]={CM}[C]=\{CM\} is a singleton — done.
  5. 5Members E and J. t(EJ)={3,8}t(EJ)=\{3,8\} (2, prune), t(EM)={1,3,4,6}t(EM)=\{1,3,4,6\} (4); t(JM)={3,5}t(JM)=\{3,5\} (2, prune). M is last and has nothing to join.
  6. 6Result. 11 frequent itemsets — 5 singletons, 5 pairs (BE, BJ, BM, CM, EM: 4, 4, 4, 3, 4) and 1 triple (BEM: 3) — from 13 intersections and one scan. The maximal ones are BEM, BJ and CM.
  7. 7Same thing with diffsets. d(BE)={2,5}d(BE)=\{2,5\}, d(BM)={2,8}d(BM)=\{2,8\}, so d(BEM)=d(BM)∖d(BE)={8}d(BEM)=d(BM)\setminus d(BE)=\{8\} and σ(BEM)=σ(BE)−1=4−1=3\sigma(BEM)=\sigma(BE)-1=4-1=3 — the same answer from a 1-element list instead of a 3-element one.
  8. 8Use it. A shopper has Bread and Milk in the cart. Rule {B,M}⇒E\{B,M\}\Rightarrow E: confidence σ(BEM)/σ(BM)=3/4=0.75\sigma(BEM)/\sigma(BM)=3/4=0.75, lift 0.75/(5/8)=1.200.75/(5/8)=1.20 — Eggs are 20% more likely than for a random basket, so suggest Eggs. The strongest rule is J⇒BJ\Rightarrow B: confidence 4/4=1.004/4=1.00, lift 1.00/(6/8)=1.331.00/(6/8)=1.33.
▸ eclat · minsup 3 · tidsetsstep 1/20
minsuplistsorder
T1BMET2BCJT3BMEJT4MECT5BMJT6BMECT7MCT8BEJitemsetσBt6Ct4Et5Jt4Mt6

B = Bread · C = Coffee · E = Eggs · J = Jam · M = Milk · filled cell = basket contains the itemset

list ops 0frequent 5tidset entries written 0
  1. 1scan DB once → t(i) for each item
  2. 2keep items with |t(i)| ≥ minsup
  3. 3eclat(class P):
  4. 4 for each X in P, in order:
  5. 5 for each Y after X in P:
  6. 6 t(XY) ← t(X) ∩ t(Y)
  7. 7 if σ(XY) ≥ minsup: add XY to P_X
  8. 8 if P_X ≠ ∅: eclat(P_X)
  9. 9output every frequent itemset

One pass over the 8 baskets turns the horizontal data into a vertical layout: each item gets its tid-list, e.g. t(B) = {1,2,3,5,6,8}. Support is now just a list length.

fig.Eclat on the 8 baskets. Each row is an itemset with its tid-list drawn as 8 cells (T1–T8); rows are kept in depth-first prefix order, so a new itemset slides in under its prefix. Each step joins two members of the current class (orange), and the candidate's list fills in cell by cell: kept in mint, pruned in rose. At minsup 3 it ends with 11 itemsets after 13 list operations and 35 tid entries written; switch to diffsets and the same 11 come out after writing only 27 entries (BEM is 4 − 1 = 3). Ordering items by increasing support cuts the operations to 11, and minsup 2 or 4 gives 18 or 9 itemsets.

The algorithm, step by step

Eclat(D, minsup)

  1. 1Vertical transform. Scan DD once; for each item ii append the tid to t(i)t(i). Keep the items with ∣t(i)∣≥|t(i)|\ge minsup, sorted in the chosen order (usually by increasing support).
  2. 2Call Eclat([∅])\text{Eclat}([\varnothing]) with those items as the members of the root class.
  3. 3For each member XX of the class, in order: output XX with σ(X)\sigma(X). Then, for each later member YY, compute t(XY)=t(X)∩t(Y)t(XY)=t(X)\cap t(Y) (or d(XY)d(XY) for dEclat).
  4. 4Prune. If ∣t(XY)∣≥|t(XY)|\ge minsup, add XYXY to the new class [X][X]; otherwise discard it — none of its supersets will be generated.
  5. 5Recurse. If [X][X] is non-empty, call Eclat([X])\text{Eclat}([X]) before moving to the next member. Free [X][X]'s lists when it returns.

Complexity

Database scans
exactly 1 (Apriori: one per level; FP-Growth: 2)
Per candidate
one intersection: O(∣t(X)∣+∣t(Y)∣)O(|t(X)|+|t(Y)|) by merging sorted lists, or ⌈n/64⌉\lceil n/64\rceil AND + popcount operations with bitsets (15,625 words for a million transactions)
Total time
O ⁣(∑candidates∣t(X)∣+∣t(Y)∣)O\!\left(\sum_{\text{candidates}}|t(X)|+|t(Y)|\right) — proportional to the frequent itemsets times their list lengths, exponential in the worst case like every exact miner
Memory
level-1 lists hold as many entries as the input; recursion keeps only the classes on the current DFS path, at most (max length) classes deep

Variants and practical tuning

VariantWhat changesBest for
Eclat (tidsets)sorted tid-lists, intersected by mergingsparse data: retail, web clicks, text
Bitset Eclateach tidset is an n-bit vector; AND + popcountmoderate n, very fast on CPUs and GPUs
dEclat (diffsets)store d(PX) = t(P) − t(PX), subtract supportsdense data with long itemsets
Hybridtidsets at the top, switch to diffsets when they become smallermixed density; the usual production choice
CHARM / MaxEclatsame vertical search, but output only closed / maximal itemsetswhen the full output is too large to use
Parallel Eclatassign top-level classes [X] to different workerslarge data; classes need no communication
The Eclat family, and when each is used.

Tuning checklist

Start with minsup high
run at, say, 5% and lower it step by step while watching the output size; it can jump by orders of magnitude between two nearby values.
Order by support
process rare items first; their classes are small and die early.
Pick the list type by density
if the average σ(PX)/σ(P)\sigma(PX)/\sigma(P) is high (most items co-occur), diffsets; if it is low, tidsets.
Cap the length
most business rules have 2–4 items; a max length stops the deep, expensive part of the search.
Count what you need
if you only need the strongest patterns, mine closed or maximal itemsets instead.

In code

python
1import numpy as np
2
3baskets = [["Bread","Milk","Eggs"], ["Bread","Coffee","Jam"], ["Bread","Milk","Eggs","Jam"],
4 ["Milk","Eggs","Coffee"], ["Bread","Milk","Jam"], ["Bread","Milk","Eggs","Coffee"],
5 ["Milk","Coffee"], ["Bread","Eggs","Jam"]]
6items = sorted({i for b in baskets for i in b})
7# vertical layout: one boolean column (tid-list as a bitmap) per item
8V = np.array([[i in b for i in items] for b in baskets]) # (n_transactions, n_items)
9
10def eclat(V, items, minsup):
11 out = {}
12 def grow(prefix, cls): # cls: list of (item, bitmap of prefix+item)
13 for k, (x, tx) in enumerate(cls):
14 itemset = prefix + (x,)
15 out[itemset] = int(tx.sum())
16 nxt = []
17 for y, ty in cls[k + 1:]:
18 t = tx & ty # tid-list intersection
19 if t.sum() >= minsup:
20 nxt.append((y, t))
21 if nxt:
22 grow(itemset, nxt)
23 first = [(items[j], V[:, j]) for j in range(len(items)) if V[:, j].sum() >= minsup]
24 grow((), first)
25 return out
26
27freq = eclat(V, items, minsup=3)
28for s, c in sorted(freq.items(), key=lambda kv: (len(kv[0]), kv[0])):
29 print(f"{', '.join(s):22s} support {c}/{len(baskets)}")
30
31# a rule from the result: confidence and lift
32conf = freq[("Bread", "Jam")] / freq[("Jam",)]
33lift = conf / (freq[("Bread",)] / len(baskets))
34print(f"Jam -> Bread: confidence {conf:.2f}, lift {lift:.2f}")
35# ... Bread, Eggs, Milk support 3/8
36# Jam -> Bread: confidence 1.00, lift 1.33
From scratch with NumPy: tidsets as boolean columns, intersection = &. Prints the 11 itemsets and the Jam → Bread rule.
python
1import pandas as pd
2from mlxtend.preprocessing import TransactionEncoder
3from mlxtend.frequent_patterns import fpgrowth, association_rules
4
5baskets = [["Bread","Milk","Eggs"], ["Bread","Coffee","Jam"], ["Bread","Milk","Eggs","Jam"],
6 ["Milk","Eggs","Coffee"], ["Bread","Milk","Jam"], ["Bread","Milk","Eggs","Coffee"],
7 ["Milk","Coffee"], ["Bread","Eggs","Jam"]]
8te = TransactionEncoder()
9X = pd.DataFrame(te.fit(baskets).transform(baskets), columns=te.columns_)
10
11# mlxtend has no Eclat; any exact miner returns the same itemsets, so use it as a check
12freq = fpgrowth(X, min_support=3 / 8, use_colnames=True)
13freq["n"] = (freq.support * 8).round().astype(int)
14print(freq.sort_values(["n"], ascending=False).to_string(index=False))
15print(len(freq), "frequent itemsets") # 11 frequent itemsets
16
17rules = association_rules(freq, metric="confidence", min_threshold=0.75)
18print(rules[["antecedents", "consequents", "support", "confidence", "lift"]].round(3).to_string(index=False))
19# (Milk, Bread) -> (Eggs) 0.375 0.75 1.200
20# (Jam) -> (Bread) 0.500 1.00 1.333
Library check with mlxtend. It has no Eclat, but every exact miner must return the same 11 itemsets; association_rules then scores them.

Use when

  • +You want the simplest fast exact miner: one scan, and the inner loop is a set intersection (or bitwise AND).
  • +The data fits in memory as vertical lists, and you can parallelise by top-level class.
  • +Data is dense with long patterns — use the diffset variant.
  • +You also need closed or maximal itemsets (CHARM and MaxEclat use the same search).

Avoid when

  • −The database is far larger than RAM and must be streamed: Apriori-style passes or partitioned mining fit better.
  • −Very low minsup on dense data: the top-level pair lists can exhaust memory.
  • −You need numeric or weighted items — Eclat counts presence only.
  • −You need a model that predicts or generalises; itemset mining only describes co-occurrence in the data you have.

Where it's used

Market-basket analysis

which products are bought together, for shelf placement, bundles and 'frequently bought together' widgets.

Web usage and clickstreams

sets of pages or features used in the same session, to restructure navigation or detect bots.

Bioinformatics

genes co-expressed across samples, or mutations co-occurring in tumours; the data is dense, so diffsets shine.

Log and alarm correlation

error codes that fire together in the same time window, to find root causes in IT operations.

Check yourself

t(X) = {1, 2, 4, 7, 9} and t(Y) = {2, 4, 5, 9}. What is the support of X ∪ Y?

Check yourself

In dEclat, σ(PX) = 10, d(PX) = {3, 7} and d(PY) = {1, 3, 9, 12}. What is σ(PXY)?

Check yourself

How many times does Eclat read the transaction database?

Check yourself

Why does Eclat only join members of the same equivalence class (same prefix)?

Remember

  • ✓Eclat flips the data to a vertical layout: each item maps to its tidset, and σ(X)=∣t(X)∣\sigma(X)=|t(X)|.
  • ✓t(X∪Y)=t(X)∩t(Y)t(X\cup Y)=t(X)\cap t(Y): support of a union is the size of an intersection — one database scan is enough.
  • ✓The search is depth-first over prefix equivalence classes; infrequent candidates are never extended (anti-monotonicity).
  • ✓dEclat stores diffsets d(PXY)=d(PY)∖d(PX)d(PXY)=d(PY)\setminus d(PX) and subtracts: σ(PXY)=σ(PX)−∣d(PXY)∣\sigma(PXY)=\sigma(PX)-|d(PXY)| — far smaller on dense data, sometimes larger on sparse data.
  • ✓Same output as Apriori and FP-Growth; order items by increasing support and choose minsup carefully, since the output can grow exponentially.
← back to ML Algorithms roadmap