# Eclat

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

Source: https://www.mlfoundry.in/learn/eclat  
Section: ML Algorithms › Unsupervised · Association Rule Learning  
Level: core · 14 min read · updated 2026-10-07

**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.

- **Task:** Frequent-itemset mining (the first half of association-rule learning)
- **Input → output:** transactions (sets of items) and a threshold minsup → every itemset $X$ with $\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)|)$ with sorted lists or $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 $X$ appear?* The **Apriori** article covers the classic answer — generate all candidates of size $k$, then rescan the whole database to count them, once per level. On a database of $n$ transactions and an answer with itemsets up to length $L$, that is $L$ full passes, and each pass checks every transaction against every candidate.

The waste is that a scan for $\{\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 $\{\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\cup Y$ exactly when it contains $X$ *and* contains $Y$, 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,\dots,n$
- **Itemset:** a set of items, e.g. $\{\text{Bread},\text{Milk}\}$; a $k$-itemset has $k$ items
- **Support σ(X):** number (or fraction) of transactions containing every item of $X$
- **Frequent itemset:** one with $\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 $X$; $\sigma(X)=|t(X)|$
- **Prefix / equivalence class [P]:** all frequent itemsets that start with prefix $P$ (in a fixed item order); members differ only in their last item
- **Diffset d(PX):** the tids that *contain $P$ but not $PX$* — what is lost when $X$ 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=\{T_1,\dots,T_n\}$ be the transactions over an item universe $I$. The vertical layout replaces $D$ by one set per item.

$$
t(X)=\{\,j\in\{1..n\} : X\subseteq T_j\,\},\qquad \sigma(X)=|t(X)|
$$

- $T_j$: the $j$-th transaction (a set of items)
- $t(X)$: tidset of itemset $X$
- $\sigma(X)$: absolute support; divide by n for the relative support

**The key identity.** $X\cup Y\subseteq T_j \iff X\subseteq T_j \text{ and } Y\subseteq T_j$. Collecting the $j$ that satisfy each side:

$$
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\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)\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 $P$, the class $[P]=\{PX_1,\dots,PX_m\}$ holds the frequent itemsets that extend $P$ by one item. Joining two members gives $PX_iX_j$ with

$$
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}\,\}
$$

- $P$: the shared prefix of the class
- $PX_i$: $P$ extended by item $X_i$
- $j>i$: join only with later members, so each itemset is generated exactly once

Every frequent $(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)$-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)\setminus t(PX),\qquad \sigma(PX)=\sigma(P)-|d(PX)|
$$

- $d(PX)$: diffset: tids that contain $P$ but lose $X$
- $\setminus$: set difference

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

$$
d(PXY)=t(PX)\setminus t(PY)=d(PY)\setminus d(PX),\qquad \sigma(PXY)=\sigma(PX)-|d(PXY)|
$$

- $d(PXY)$: diffset of $PXY$ relative to its parent $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)\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(PX_i)\cap t(PX_j)|\ge$ minsup. Lowering it can grow the output exponentially: with all $m$ items frequent together, up to $2^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)|\ll|t(PX)|$, i.e. when $\sigma(PX)/\sigma(P)$ is close to 1 (dense data).
- **Max length:** stop recursing at depth $L$; bounds the $2^m$ blow-up when only short rules are wanted.

## Worked example: eight baskets

A small shop records 8 baskets over 5 items — **B**read, **C**offee, **E**ggs, **J**am, **M**ilk. 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.

Horizontal layout: the data as it arrives, one row per transaction.

| 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 |

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.

| 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 |

Class [∅] — all 10 pairs, items in A→Z order. Five survive. The diffset column is what dEclat would store instead.

| 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)**

1. **Scan once.** Build the five tidsets above. Every item has $|t|\ge3$, so the first class is $[\varnothing]=\{B,C,E,J,M\}$.
2. **Class $[\varnothing]$, member B.** Join B with each later item: $t(BC)=\{2,6\}$ (σ = 2, prune), $t(BE)=\{1,3,6,8\}$ (4), $t(BJ)=\{2,3,5,8\}$ (4), $t(BM)=\{1,3,5,6\}$ (4). New class $[B]=\{BE,BJ,BM\}$.
3. **Recurse into $[B]$.** $t(BEJ)=t(BE)\cap t(BJ)=\{3,8\}$ → 2, prune. $t(BEM)=t(BE)\cap t(BM)=\{1,3,6\}$ → **3, keep**. $t(BJM)=\{3,5\}$ → 2, prune. Class $[BE]=\{BEM\}$ has one member — nothing to join, so this branch is finished.
4. **Back in $[\varnothing]$, member C.** $t(CE)=\{4,6\}$ (2), $t(CJ)=\{2\}$ (1), $t(CM)=\{4,6,7\}$ (**3**). Class $[C]=\{CM\}$ is a singleton — done.
5. **Members E and J.** $t(EJ)=\{3,8\}$ (2, prune), $t(EM)=\{1,3,4,6\}$ (**4**); $t(JM)=\{3,5\}$ (2, prune). M is last and has nothing to join.
6. **Result.** 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. **Same thing with diffsets.** $d(BE)=\{2,5\}$, $d(BM)=\{2,8\}$, so $d(BEM)=d(BM)\setminus d(BE)=\{8\}$ and $\sigma(BEM)=\sigma(BE)-1=4-1=3$ — the same answer from a 1-element list instead of a 3-element one.
8. **Use it.** A shopper has Bread and Milk in the cart. Rule $\{B,M\}\Rightarrow E$: confidence $\sigma(BEM)/\sigma(BM)=3/4=0.75$, lift $0.75/(5/8)=1.20$ — Eggs are 20% more likely than for a random basket, so suggest Eggs. The strongest rule is $J\Rightarrow B$: confidence $4/4=1.00$, lift $1.00/(6/8)=1.33$.

> **Rules are the same for every miner:** Eclat only changes **how supports are counted**. Turning frequent itemsets into rules — confidence, lift, the second pass over each itemset's subsets — is identical to what the **Apriori** article describes, so it is not repeated here.

> Figure: 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. **Vertical transform.** Scan $D$ once; for each item $i$ append the tid to $t(i)$. Keep the items with $|t(i)|\ge$ minsup, sorted in the chosen order (usually by increasing support).
2. **Call** $\text{Eclat}([\varnothing])$ with those items as the members of the root class.
3. **For each member** $X$ of the class, in order: output $X$ with $\sigma(X)$. Then, for each later member $Y$, compute $t(XY)=t(X)\cap t(Y)$ (or $d(XY)$ for dEclat).
4. **Prune.** If $|t(XY)|\ge$ minsup, add $XY$ to the new class $[X]$; otherwise discard it — none of its supersets will be generated.
5. **Recurse.** If $[X]$ is non-empty, call $\text{Eclat}([X])$ before moving to the next member. Free $[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)|)$ by merging sorted lists, or $\lceil n/64\rceil$ AND + popcount operations with bitsets (15,625 words for a million transactions)
- **Total time:** $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

The Eclat family, and when each is used.

| 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 $\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.

> **Eclat vs FP-Growth vs Apriori:** All three return *exactly* the same itemsets — they differ only in how they count. Apriori counts by rescanning horizontally, level by level; **FP-Growth** (see its article) compresses the baskets into a prefix tree and mines conditional trees; Eclat counts by intersecting vertical lists, depth-first. Eclat is usually the simplest to implement fast — the inner loop is a set intersection, which vectorises beautifully as bitwise AND.

> **Low minsup on dense data blows up memory:** At the top level Eclat materialises one list per frequent pair; with 1,000 frequent items that is up to 499,500 lists, each potentially long. On dense data with a low threshold the tidsets alone can exceed RAM. Use diffsets, a higher minsup, a max length, or mine closed itemsets.

> **Diffsets are not always smaller:** On sparse data a pair like CJ has $t(CJ)=\{2\}$ but $d(CJ)=\{4,6,7\}$ — the diffset is three times larger. Pure dEclat on sparse retail data can use *more* memory than Eclat; switch representations per class when $|d|<|t|$.

## In code

```python
import numpy as np

baskets = [["Bread","Milk","Eggs"], ["Bread","Coffee","Jam"], ["Bread","Milk","Eggs","Jam"],
           ["Milk","Eggs","Coffee"], ["Bread","Milk","Jam"], ["Bread","Milk","Eggs","Coffee"],
           ["Milk","Coffee"], ["Bread","Eggs","Jam"]]
items = sorted({i for b in baskets for i in b})
# vertical layout: one boolean column (tid-list as a bitmap) per item
V = np.array([[i in b for i in items] for b in baskets])        # (n_transactions, n_items)

def eclat(V, items, minsup):
    out = {}
    def grow(prefix, cls):                      # cls: list of (item, bitmap of prefix+item)
        for k, (x, tx) in enumerate(cls):
            itemset = prefix + (x,)
            out[itemset] = int(tx.sum())
            nxt = []
            for y, ty in cls[k + 1:]:
                t = tx & ty                     # tid-list intersection
                if t.sum() >= minsup:
                    nxt.append((y, t))
            if nxt:
                grow(itemset, nxt)
    first = [(items[j], V[:, j]) for j in range(len(items)) if V[:, j].sum() >= minsup]
    grow((), first)
    return out

freq = eclat(V, items, minsup=3)
for s, c in sorted(freq.items(), key=lambda kv: (len(kv[0]), kv[0])):
    print(f"{', '.join(s):22s} support {c}/{len(baskets)}")

# a rule from the result: confidence and lift
conf = freq[("Bread", "Jam")] / freq[("Jam",)]
lift = conf / (freq[("Bread",)] / len(baskets))
print(f"Jam -> Bread: confidence {conf:.2f}, lift {lift:.2f}")
# ... Bread, Eggs, Milk support 3/8
# 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
import pandas as pd
from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import fpgrowth, association_rules

baskets = [["Bread","Milk","Eggs"], ["Bread","Coffee","Jam"], ["Bread","Milk","Eggs","Jam"],
           ["Milk","Eggs","Coffee"], ["Bread","Milk","Jam"], ["Bread","Milk","Eggs","Coffee"],
           ["Milk","Coffee"], ["Bread","Eggs","Jam"]]
te = TransactionEncoder()
X = pd.DataFrame(te.fit(baskets).transform(baskets), columns=te.columns_)

# mlxtend has no Eclat; any exact miner returns the same itemsets, so use it as a check
freq = fpgrowth(X, min_support=3 / 8, use_colnames=True)
freq["n"] = (freq.support * 8).round().astype(int)
print(freq.sort_values(["n"], ascending=False).to_string(index=False))
print(len(freq), "frequent itemsets")              # 11 frequent itemsets

rules = association_rules(freq, metric="confidence", min_threshold=0.75)
print(rules[["antecedents", "consequents", "support", "confidence", "lift"]].round(3).to_string(index=False))
# (Milk, Bread) -> (Eggs)   0.375  0.75  1.200
# (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.

**Strengths**

- 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).

**Limitations**

- 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.

- **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.

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

- A. 2
- B. 3
- C. 4
- D. 6

**Answer:** B. 3 — $t(X\cup Y)=t(X)\cap t(Y)=\{2,4,9\}$, so $\sigma=3$. (6 would be the size of the *union* of the lists, which corresponds to baskets containing X *or* Y.)

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

- A. 6
- B. 7
- C. 8
- D. 4

**Answer:** B. 7 — $d(PXY)=d(PY)\setminus d(PX)=\{1,9,12\}$, so $\sigma(PXY)=\sigma(PX)-3=7$.

**Question:** How many times does Eclat read the transaction database?

- A. Once
- B. Twice
- C. Once per itemset length
- D. Once per candidate

**Answer:** A. Once — One scan builds the vertical layout; after that every support is the length of an intersection of lists already in memory. FP-Growth needs two scans, Apriori one per level.

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

- A. Itemsets from different classes can never be frequent together
- B. It generates each itemset exactly once, and keeps only the lists on the current DFS path in memory
- C. Intersections across classes give the wrong support
- D. It is required for the diffset formula to hold

**Answer:** B. It generates each itemset exactly once, and keeps only the lists on the current DFS path in memory — Every $(k{+}1)$-itemset has exactly one pair of parents sharing its $(k{-}1)$-prefix, so joining within classes enumerates each itemset once. Classes are independent, so their lists can be freed (or sent to another worker) when done.

**Key points**

- Eclat flips the data to a vertical layout: each item maps to its tidset, and $\sigma(X)=|t(X)|$.
- $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)\setminus d(PX)$ and subtracts: $\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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
