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 with 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 with sorted lists or 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 appear? The Apriori article covers the classic answer — generate all candidates of size , then rescan the whole database to count them, once per level. On a database of transactions and an answer with itemsets up to length , that is full passes, and each pass checks every transaction against every candidate.
The waste is that a scan for re-reads every basket, including the ones we already know do not contain Bread. We already computed which baskets contain 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 exactly when it contains and contains , 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
- Itemset
- a set of items, e.g. ; a -itemset has items
- Support σ(X)
- number (or fraction) of transactions containing every item of
- Frequent itemset
- one with 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 ;
- Prefix / equivalence class [P]
- all frequent itemsets that start with prefix (in a fixed item order); members differ only in their last item
- Diffset d(PX)
- the tids that contain but not — what is lost when 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 be the transactions over an item universe . The vertical layout replaces by one set per item.
- the -th transaction (a set of items)
- tidset of itemset
- absolute support; divide by n for the relative support
The key identity. . Collecting the that satisfy each side:
- set intersection of the two tid-lists
Because , support can only shrink as itemsets grow — the anti-monotone (downward-closure) property also used by Apriori. So if 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 , the class holds the frequent itemsets that extend by one item. Joining two members gives with
- the shared prefix of the class
- extended by item
- join only with later members, so each itemset is generated exactly once
Every frequent -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 -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.
- diffset: tids that contain but lose
- set difference
Derivation of the join. Since and , the tids that contain but not are those in but not in : in , not in , but in . Because the first condition is automatic, so
- diffset of relative to its parent
- support of the parent, already known
At the first level there is no diffset yet, so dEclat starts with 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 minsup. Lowering it can grow the output exponentially: with all items frequent together, up to 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 , i.e. when is close to 1 (dense data).
- Max length
- stop recursing at depth ; bounds the 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.
| tid | Items | Short |
|---|---|---|
| 1 | Bread, Milk, Eggs | B E M |
| 2 | Bread, Coffee, Jam | B C J |
| 3 | Bread, Milk, Eggs, Jam | B E J M |
| 4 | Milk, Eggs, Coffee | C E M |
| 5 | Bread, Milk, Jam | B J M |
| 6 | Bread, Milk, Eggs, Coffee | B C E M |
| 7 | Milk, Coffee | C M |
| 8 | Bread, Eggs, Jam | B E J |
| Item | Tidset 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 |
| Pair | t(X) ∩ t(Y) | σ | Kept? | d(XY) = t(X) − t(Y) |
|---|---|---|---|---|
| BC | {2, 6} | 2 | no | {1, 3, 5, 8} |
| BE | {1, 3, 6, 8} | 4 | yes | {2, 5} |
| BJ | {2, 3, 5, 8} | 4 | yes | {1, 6} |
| BM | {1, 3, 5, 6} | 4 | yes | {2, 8} |
| CE | {4, 6} | 2 | no | {2, 7} |
| CJ | {2} | 1 | no | {4, 6, 7} |
| CM | {4, 6, 7} | 3 | yes | {2} |
| EJ | {3, 8} | 2 | no | {1, 4, 6} |
| EM | {1, 3, 4, 6} | 4 | yes | {8} |
| JM | {3, 5} | 2 | no | {2, 8} |
Eclat by hand (minsup = 3)
- 1Scan once. Build the five tidsets above. Every item has , so the first class is .
- 2Class , member B. Join B with each later item: (σ = 2, prune), (4), (4), (4). New class .
- 3Recurse into . → 2, prune. → 3, keep. → 2, prune. Class has one member — nothing to join, so this branch is finished.
- 4Back in , member C. (2), (1), (3). Class is a singleton — done.
- 5Members E and J. (2, prune), (4); (2, prune). M is last and has nothing to join.
- 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.
- 7Same thing with diffsets. , , so and — the same answer from a 1-element list instead of a 3-element one.
- 8Use it. A shopper has Bread and Milk in the cart. Rule : confidence , lift — Eggs are 20% more likely than for a random basket, so suggest Eggs. The strongest rule is : confidence , lift .
B = Bread · C = Coffee · E = Eggs · J = Jam · M = Milk · filled cell = basket contains the itemset
- 1scan DB once → t(i) for each item
- 2keep items with |t(i)| ≥ minsup
- 3eclat(class P):
- 4 for each X in P, in order:
- 5 for each Y after X in P:
- 6 t(XY) ← t(X) ∩ t(Y)
- 7 if σ(XY) ≥ minsup: add XY to P_X
- 8 if P_X ≠ ∅: eclat(P_X)
- 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.
The algorithm, step by step
Eclat(D, minsup)
- 1Vertical transform. Scan once; for each item append the tid to . Keep the items with minsup, sorted in the chosen order (usually by increasing support).
- 2Call with those items as the members of the root class.
- 3For each member of the class, in order: output with . Then, for each later member , compute (or for dEclat).
- 4Prune. If minsup, add to the new class ; otherwise discard it — none of its supersets will be generated.
- 5Recurse. If is non-empty, call before moving to the next member. Free 's lists when it returns.
Complexity
- Database scans
- exactly 1 (Apriori: one per level; FP-Growth: 2)
- Per candidate
- one intersection: by merging sorted lists, or AND + popcount operations with bitsets (15,625 words for a million transactions)
- Total time
- — 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
| Variant | What changes | Best for |
|---|---|---|
| Eclat (tidsets) | sorted tid-lists, intersected by merging | sparse data: retail, web clicks, text |
| Bitset Eclat | each tidset is an n-bit vector; AND + popcount | moderate n, very fast on CPUs and GPUs |
| dEclat (diffsets) | store d(PX) = t(P) − t(PX), subtract supports | dense data with long itemsets |
| Hybrid | tidsets at the top, switch to diffsets when they become smaller | mixed density; the usual production choice |
| CHARM / MaxEclat | same vertical search, but output only closed / maximal itemsets | when the full output is too large to use |
| Parallel Eclat | assign top-level classes [X] to different workers | large data; classes need no communication |
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 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
1import numpy as np23baskets = [["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 item8V = np.array([[i in b for i in items] for b in baskets]) # (n_transactions, n_items)910def 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 intersection19 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 out2627freq = 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)}")3031# a rule from the result: confidence and lift32conf = 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/836# Jam -> Bread: confidence 1.00, lift 1.331import pandas as pd2from mlxtend.preprocessing import TransactionEncoder3from mlxtend.frequent_patterns import fpgrowth, association_rules45baskets = [["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_)1011# mlxtend has no Eclat; any exact miner returns the same itemsets, so use it as a check12freq = 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 itemsets1617rules = 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.20020# (Jam) -> (Bread) 0.500 1.00 1.333Use 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 .
- ✓: 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 and subtracts: — 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.