# BIRCH

> Compress the data in one pass into a tree of clustering features (N, linear sum, squared sum), then cluster the leaves.

Source: https://www.mlfoundry.in/learn/birch  
Section: ML Algorithms › Unsupervised · Clustering  
Level: advanced · 17 min read · updated 2026-10-07

**BIRCH:** (*Balanced Iterative Reducing and Clustering using Hierarchies*, Zhang, Ramakrishnan and Livny, 1996) reads the data **once**, folding each point into a small, tight subcluster that is stored only as a triple $(N, \mathbf{LS}, SS)$ — a count, a vector sum and a sum of squares. The subclusters live in a height-balanced **CF tree**; afterwards an ordinary clustering algorithm groups the few hundred leaf subclusters instead of the millions of raw points.

- **Task:** Clustering (unsupervised) of large or streaming numeric data
- **Input → output:** points $x_1,\dots,x_n\in\mathbb{R}^d$ → leaf subclusters (CF entries), then $k$ cluster labels
- **Learns:** a CF tree whose leaves hold $m \ll n$ clustering features $(N,\mathbf{LS},SS)$; a cluster label per leaf entry
- **Training:** one pass: $O(n\,B\,h\,d)$ with tree height $h\approx\log_B m$; plus the global step on $m$ centroids (Ward: about $O(m^2)$)
- **Prediction:** $O(m\,d)$: nearest leaf centroid, then its cluster label
- **Memory:** $O(m\,d)$ — independent of $n$ once $T$ is large enough
- **Hyperparameters:** threshold T (max subcluster radius), branching factor B, number of clusters k / the global clusterer
- **Assumes:** Euclidean, numeric features on comparable scales; roughly spherical clusters; insertion order does not matter much

## The problem

The classic clustering algorithms all want the whole dataset in memory, often more than once. Hierarchical clustering (see **Hierarchical Clustering** and **Agglomerative Clustering**) needs the $n\times n$ distance matrix: for $n=100{,}000$ points the condensed matrix alone is $\binom{n}{2}\cdot 8$ bytes $\approx 40$ GB. **K-Means** is lighter, but every Lloyd iteration re-reads every point, and k-medoids is worse still.

In 1996 the typical case was a database on disk much larger than RAM, and today it is a stream that never stops. Either way we want an algorithm that (1) reads each point **once**, (2) uses memory that does **not grow with $n$**, and (3) still lets us run a good clustering method afterwards. BIRCH's answer: most points are boring — they sit right next to other points. Summarise each tight clump by a few sufficient statistics, keep the summaries, and throw the raw points away.

## The idea

Picture walking through the data with a notebook. For every point you ask: *is there already a little group close enough that this point could join it without making the group wider than $T$?* If yes, you update that group's three numbers and forget the point. If no, you open a new group. To find the nearest group quickly, the groups are organised in a search tree like a B+-tree: each internal node holds summaries of its children, so a new point walks down from the root following the nearest summary at each level. When a node gets too many entries, it splits, exactly as a B-tree node does, and the tree stays balanced.

After the pass the leaves hold, say, a few hundred subclusters that together describe millions of points. Those are now small enough to feed to any clustering algorithm — scikit-learn uses Ward agglomerative clustering on the leaf centroids by default — and each original point (or new point) takes the label of its nearest leaf centroid.

**Vocabulary**

- **Clustering feature (CF):** the triple $(N,\mathbf{LS},SS)$ summarising a set of points: their count, vector sum and sum of squared norms
- **Subcluster / leaf entry:** a CF stored in a leaf; the unit BIRCH actually clusters. Its radius must stay $\le T$
- **Internal (non-leaf) entry:** a CF that is the sum of all CFs in its child node, plus a pointer to that child; used only for navigation
- **CF tree:** height-balanced tree of nodes; every node holds at most B entries; all leaves are at the same depth
- **Threshold T:** the largest radius a leaf subcluster may have; controls how coarse the summary is
- **Branching factor B:** maximum number of entries per node (the original paper uses B for internal nodes and L for leaves; scikit-learn uses one value for both)
- **Node split:** when a node exceeds B entries: the farthest pair of entries become seeds of two new nodes and the rest go to the closer seed
- **Global clustering:** the final step that clusters the leaf centroids (Ward, k-means, …) into k clusters

## The math

Everything rests on one observation: the quantities we need about a group of points can be computed from three running sums.

$$
\mathrm{CF}(S)=\Big(N,\;\mathbf{LS},\;SS\Big)=\Big(|S|,\;\sum_{x\in S}x,\;\sum_{x\in S}\lVert x\rVert^2\Big)
$$

- $S$: a set of points (one subcluster)
- $N$: number of points in S
- $\mathbf{LS}$: linear sum — a vector in $\mathbb{R}^d$
- $SS$: squared sum — one number, the sum of squared Euclidean norms (the 1996 paper also uses a scalar)

**Additivity.** If $S_1$ and $S_2$ are disjoint, the CF of their union is just the component-wise sum. Absorbing a point, merging two subclusters, and maintaining a parent entry are all *additions* — no point is ever revisited.

$$
\mathrm{CF}(S_1\cup S_2)=\big(N_1+N_2,\;\mathbf{LS}_1+\mathbf{LS}_2,\;SS_1+SS_2\big)
$$

- $S_1,S_2$: two disjoint point sets

**Centroid and radius.** The centroid is $c=\mathbf{LS}/N$. The radius $R$ is the root-mean-square distance of the points to the centroid. Expand the square and use $\sum_x x = Nc$:

$$
R^2=\frac1N\sum_{x\in S}\lVert x-c\rVert^2=\frac1N\Big(\sum\lVert x\rVert^2-2c^\top\!\sum x+N\lVert c\rVert^2\Big)=\frac{SS}{N}-\Big\lVert\frac{\mathbf{LS}}{N}\Big\rVert^2
$$

- $c$: centroid $\mathbf{LS}/N$
- $R$: radius: RMS distance of the members to the centroid

The *diameter* — RMS distance between pairs of members — is also a function of the CF: $D^2=\dfrac{2N\,SS-2\lVert\mathbf{LS}\rVert^2}{N(N-1)}$. The paper allows either; scikit-learn uses $R$. For the two points $(1.5,2)$ and $(1,2.5)$: $R=0.354$, $D=0.707$ (the plain distance between them).

**The absorb test.** A leaf entry with CF $(N,\mathbf{LS},SS)$ may absorb a new point $x$ only if the merged subcluster stays tight:

$$
R\big(\mathrm{CF}+(1,x,\lVert x\rVert^2)\big)\le T
$$

- $T$: the threshold hyperparameter
- $(1,x,\lVert x\rVert^2)$: the CF of the single point x

It helps to see what this test means. The total squared spread $N R^2$ grows by a known amount when $x$ joins (the same term that appears in Ward's criterion): adding a point at distance $\delta=\lVert x-c\rVert$ from the centroid gives

$$
(N+1)\,R'^2 = N R^2 + \frac{N}{N+1}\,\delta^2 \quad\Longrightarrow\quad R'^2=\frac{N R^2+\tfrac{N}{N+1}\delta^2}{N+1}
$$

- $R'$: radius after absorbing x
- $\delta$: distance from x to the current centroid

Two consequences. For a single point ($N=1$, $R=0$) the merged radius is $\delta/2$, so **two points merge when they are at most $2T$ apart**. And as $N$ grows, $\tfrac{N}{N+1}\delta^2/(N+1)\approx\delta^2/N$, so large subclusters accept far-away points more easily — a point at distance $\delta$ from a big, tight subcluster barely moves its radius. That is why the insertion order matters a little.

> **CFs are sufficient statistics:** Count, mean and total within-scatter of a set are all functions of $(N,\mathbf{LS},SS)$. So are the distances BIRCH needs *between* subclusters: centroid distance $\lVert c_1-c_2\rVert$, average inter-cluster distance, and the Ward cost of merging, $\tfrac{N_1N_2}{N_1+N_2}\lVert c_1-c_2\rVert^2$. Any algorithm that only uses these quantities can run on CFs instead of points — this is why the summary is lossless *for clustering purposes* even though the points are gone.

**The hyperparameters, mathematically.** $T$ sets the volume each subcluster may cover; in $d$ dimensions a region of extent $L$ needs on the order of $(L/T)^d$ subclusters, so halving $T$ multiplies the number of leaf entries $m$ by up to $2^d$ (on our data: $T=1.0$ gives 3 subclusters, $T=0.6$ gives 7, $T=0.3$ gives 12, i.e. one per point). $B$ sets the fan-out: the height is about $\lceil\log_B m\rceil$, each insertion compares the point with at most $B$ centroids per level, so it costs $O(B\,h\,d)$. Large $B$ → shallow tree but more comparisons per node; small $B$ → many splits and a deeper tree.

## Worked example: 12 points, T = 0.6, B = 3

Twelve 2-D points arrive in the order below. By eye they form three groups: **A** bottom-left, **B** bottom-right, **C** top-middle. We build the CF tree with threshold $T=0.6$ and branching factor $B=3$, then cluster the leaves into $k=3$.

Input in arrival order, with the leaf entry that ends up holding each point and its final cluster. Highlighted: the two points that trigger a split (P6 a root split, P7 a leaf split).

| Point | x | y | Final leaf entry | Cluster |
| --- | --- | --- | --- | --- |
| P1 | 1 | 1 | S1 | A |
| P2 | 2 | 1 | S1 | A |
| P3 | 6 | 2 | S2 | B |
| P4 | 1.5 | 2 | S3 | A |
| P5 | 7 | 2 | S2 | B |
| P6 | 4 | 7 | S4 | C |
| P7 | 6.5 | 1 | S5 | B |
| P8 | 3.5 | 6 | S4 | C |
| P9 | 1 | 2.5 | S3 | A |
| P10 | 5 | 6.5 | S6 | C |
| P11 | 7 | 3 | S7 | B |
| P12 | 4.5 | 5.5 | S6 | C |

**Phase 1: one pass, by hand**

1. **P1 = (1, 1).** The tree is empty, so P1 becomes leaf entry **S1** $=(1,(1,1),2)$.
2. **P2 = (2, 1).** Nearest entry S1. Merged CF $(2,(3,2),7)$: centroid $(1.5,1)$, $R^2=\tfrac72-(1.5^2+1^2)=0.25$, $R=0.5\le0.6$ → **absorb**. S1 $=(2,(3,2),7)$.
3. **P3 = (6, 2).** Merged with S1 the radius would be $2.211>0.6$ → new entry **S2**.
4. **P4 = (1.5, 2).** Nearest S1, $\delta=1$: $R'^2=\big(2\cdot0.25+\tfrac23\cdot1\big)/3=0.389$, $R'=0.624>0.6$ → new entry **S3**. The leaf now holds 3 entries — full, but not over $B$.
5. **P5 = (7, 2).** S2 absorbs it: $R=0.5$, S2 $=(2,(13,4),93)$.
6. **P6 = (4, 7).** Nearest S2 at distance 5.590, merged radius 2.667 → new entry S4; the leaf has $4>B$ entries → **split**. Squared distances between the four centroids: S1–S4 $=42.25$ is the largest, so S1 and S4 are the seeds; S2 (26 vs 31.25) and S3 (1 vs 31.25) are closer to S1. The leaf was the root, so a **new root** appears with two entries: a CF of 5 points over $\{S1,S2,S3\}$ and a CF of 1 point over $\{S4\}$. Height is now 2.
7. **P7 = (6.5, 1).** At the root the nearest entry is the 5-point CF (centroid $(3.5,1.6)$). In its leaf the nearest is S2 at $\delta=1$: $R'=0.624>0.6$ → new entry S5; the leaf overflows again with $\{S1,S2,S3,S5\}$. Farthest pair S1–S2 (squared distance 26) → leaves $\{S1,S3\}$ and $\{S2,S5\}$. The root now has 3 entries: A-side, C-side, B-side.
8. **P8 = (3.5, 6)** joins S4 ($R=0.559$). **P9 = (1, 2.5)** joins S3 ($\delta=0.707$, $R=0.354$).
9. **P10 = (5, 6.5).** Nearest S4 $=(3.75,6.5)$ at $\delta=1.25$: $R'^2=\big(2\cdot0.3125+\tfrac23\cdot1.5625\big)/3=0.556$, $R'=0.745$ → new entry **S6**.
10. **P11 = (7, 3).** Nearest S2 at 1.118, merged radius 0.667 → new entry **S7**; the B-side leaf holds $\{S2,S5,S7\}$ — exactly $B$, no split.
11. **P12 = (4.5, 5.5).** Nearest S6 at 1.118 → absorbed, $R=0.559$. Done: **12 points → 7 leaf CFs** in 3 leaves under one root.

The seven leaf CFs after the pass (R computed from the CF alone), their Ward cluster, and their distance to the new point (3, 4). Highlighted: the nearest one, S3.

| Entry | N | LS | SS | Centroid | R | Cluster | dist to (3, 4) |
| --- | --- | --- | --- | --- | --- | --- | --- |
| S1 | 2 | (3, 2) | 7 | (1.5, 1) | 0.500 | A | 3.354 |
| **S3** | 2 | (2.5, 4.5) | 13.5 | (1.25, 2.25) | 0.354 | A | **2.475** |
| S4 | 2 | (7.5, 13) | 113.25 | (3.75, 6.5) | 0.559 | C | 2.610 |
| S6 | 2 | (9.5, 12) | 117.75 | (4.75, 6) | 0.559 | C | 2.658 |
| S2 | 2 | (13, 4) | 93 | (6.5, 2) | 0.500 | B | 4.031 |
| S5 | 1 | (6.5, 1) | 43.25 | (6.5, 1) | 0.000 | B | 4.610 |
| S7 | 1 | (7, 3) | 58 | (7, 3) | 0.000 | B | 4.123 |

**Phase 3: global clustering and a prediction**

1. Run Ward agglomerative clustering on the 7 centroids (treated as 7 ordinary points, as scikit-learn does). Ward distances $\sqrt{2\Delta}$, where $\Delta$ is the increase in within-cluster sum of squares: S2+S5 at **1.000**, S4+S6 at **1.118**, S1+S3 at **1.275**, then S7 joins {S2, S5} at **1.826**.
2. Stop at $k=3$: **A** = {S1, S3}, **B** = {S2, S5, S7}, **C** = {S4, S6}. Every original point is labelled by its nearest leaf centroid, which recovers the three visual groups exactly.
3. **New point (3, 4).** Its nearest leaf centroid is S3 at distance 2.475 (S4 is close behind at 2.610), so it is assigned to **cluster A**.

> Figure: The worked example, point by point. Top: points (P1–P12) and leaf subclusters drawn with their true radius R; violet dashed rings are the internal CFs. On each arrival the dashed ring is the radius the merged subcluster would have, against the dotted T-circle: mint means absorb, rose means a new entry. Bottom: the CF tree, with an overflowing node outlined in rose and the split seeds in orange. With T = 0.6 and B = 3 it reproduces the hand computation: a root split at P6, a leaf split at P7, 7 leaf CFs in 3 leaves, and (3, 4) at 2.475 from S3 → cluster 1 (A). Change T to see the summary coarsen: T = 0.3 keeps all 12 points as separate subclusters, 0.5 gives 9, 0.7 gives 6, 1.0 gives 3. T = 0.3 with B = 3 grows a three-level tree; B = 6 gives a wider, shallower one.

## The algorithm, step by step

**BIRCH(X, T, B, k)**

1. **Phase 1: build the CF tree (one scan).** For each point $x$: start at the root and repeatedly descend into the entry whose centroid is nearest to $x$, until you reach a leaf.
2. **Absorb or insert.** In the leaf, take the nearest entry. If its radius after absorbing $x$ is $\le T$, add $(1,x,\lVert x\rVert^2)$ to it. Otherwise append $x$ as a new entry.
3. **Split on overflow.** If the leaf now has more than $B$ entries, pick the two entries whose centroids are farthest apart as seeds, give every other entry to the closer seed, and replace the leaf by the two new nodes. The parent gets one extra entry; it may overflow and split in turn. If the root splits, a new root is created — the tree grows at the top and stays balanced.
4. **Update the path.** Add $x$'s CF to every internal entry on the way down (additivity), so each parent summarises its subtree.
5. **Phase 2 (optional, original paper): condense.** If memory runs out, increase $T$ and re-insert the leaf entries into a smaller tree — no need to re-read the data. Tiny, sparse entries can be set aside as potential outliers.
6. **Phase 3: global clustering.** Cluster the $m$ leaf centroids (or the full CFs) with Ward, k-means or any other algorithm into $k$ clusters.
7. **Phase 4 (optional): refine.** One more pass assigning every point to its nearest final centroid (essentially a k-means step), which also fixes points that were absorbed into the wrong subcluster early on. Prediction for a new point uses the same rule.

**Complexity.** Phase 1 is $O(n\,B\,h\,d)$ time with $h\approx\log_B m$, and $O(m\,d)$ memory for $m$ leaf entries. Phase 3 depends on the global method: Ward on centroids costs about $O(m^2)$ memory and time, trivial when $m$ is a few thousand. On 100,000 points from 5 Gaussian blobs, scikit-learn's BIRCH with $B=50$ keeps 525 leaf CFs at $T=0.3$, 214 at $T=0.5$, 26 at $T=1.0$ and 5 at $T=2.0$ — a 190× to 20,000× compression.

## Hyperparameters, variants and tuning

What to set in scikit-learn's Birch, and what each knob does.

| Parameter | Effect | Practical advice |
| --- | --- | --- |
| threshold (T) | Max radius of a leaf subcluster. Smaller → more, tighter subclusters, more memory, finer summary. | Standardise features first, then pick T a fraction of the within-cluster spread; check how many subclusters you get (aim for hundreds to a few thousand). |
| branching_factor (B) | Max entries per node. Sets tree height and the cost of each descent. | The default 50 is fine; it rarely changes the clustering, only speed and tree shape. |
| n_clusters | The global step: an int (Ward with k clusters), any sklearn clusterer, or None (return the raw subclusters). | Pass a clusterer that suits your clusters, or None to use BIRCH purely as a data reducer. |
| partial_fit | Insert more data into the existing tree; partial_fit() with no X re-runs only the global step. | Use for streams and data that does not fit in memory; chunk size does not change the tree. |
| compute_labels | Whether to label the training data at the end of fit. | Turn off for very large data and call predict on what you need. |

**Variants and relatives**

- **Diameter threshold:** the original paper lets the absorb test use the diameter $D$ instead of $R$; both are computable from the CF
- **Different global step:** k-means weighted by N, Gaussian mixtures, or DBSCAN on the centroids — the CF tree is just a compressor
- **BETULA:** a numerically stable CF tree (Lang and Schubert, 2020) that stores $(N,\text{mean},\text{scatter})$ instead of $(N,\mathbf{LS},SS)$, avoiding the cancellation pitfall below
- **Stream micro-clusters:** CluStream and DenStream keep CF-like summaries (with timestamps and decay) for evolving data streams
- **MiniBatchKMeans:** the other scalable-in-n option in scikit-learn; it needs k up front, BIRCH does not until the global step

> **The global step ignores how big each subcluster is:** With an integer n_clusters, scikit-learn runs Ward on the leaf centroids as if each were one point: a subcluster of 1,244 points weighs the same as a singleton. On 100,000 points in 5 blobs (T = 0.3, 525 subclusters) that gives an adjusted Rand index of only 0.645, while k-means on the same centroids weighted by $N$ gives 0.865 — as good as k-means on all the raw data (0.869). If your subclusters have very different sizes, use n_clusters=None and cluster the centroids yourself with sample weights.

> **Catastrophic cancellation far from the origin:** $R^2 = SS/N-\lVert\mathbf{LS}/N\rVert^2$ subtracts two huge, nearly equal numbers when the data sits far from the origin. Shift the worked example by $10^8$ and scikit-learn finds 5 subclusters instead of 7; shift it by $10^9$ and every point gets the same label. **Centre (and scale) your features** before BIRCH.

> **Order and threshold change borderline answers:** BIRCH is a single greedy pass, so the leaves depend on the arrival order. Over 1,000 random orderings of the 12 example points (T = 0.6, B = 3) the tree ends with 6 to 9 leaf CFs (6: 161 times, 7: 557, 8: 279, 9: 3). All 1,000 recover the three groups, but the borderline point (3, 4) goes to A 481 times and to C 519 times. Changing T does the same thing: (3, 4) is labelled A at T = 0.6 and 0.7, and C at T = 0.3, 0.5 and 1.0. A final refinement pass (Phase 4) reduces this.

## In code

```python
import numpy as np

class CF:
  """Clustering feature: N, linear sum LS, squared sum SS (sum of squared norms)."""
  def __init__(self, x=None):
      self.n, self.ls, self.ss, self.child = 0, 0.0, 0.0, None
      if x is not None:
          self.n, self.ls, self.ss = 1, np.array(x, float), float(np.dot(x, x))
  @property
  def centroid(self):
      return self.ls / self.n
  def add(self, o):                          # additivity: CF1 + CF2
      self.n, self.ls, self.ss = self.n + o.n, self.ls + o.ls, self.ss + o.ss
  def radius_with(self, o):                  # radius of the merged subcluster
      n, ls, ss = self.n + o.n, self.ls + o.ls, self.ss + o.ss
      return np.sqrt(max(ss / n - np.dot(ls / n, ls / n), 0.0))

class Node:
  def __init__(self, leaf):
      self.leaf, self.entries = leaf, []

def split(node):
  C = np.array([e.centroid for e in node.entries])
  D = ((C[:, None] - C[None]) ** 2).sum(-1)
  i, j = np.unravel_index(D.argmax(), D.shape)       # farthest pair = seeds
  halves = (Node(node.leaf), Node(node.leaf))
  for k, e in enumerate(node.entries):
      halves[0 if (k == i or D[i, k] < D[j, k]) else 1].entries.append(e)
  parents = []
  for h in halves:
      p = CF(); p.child = h
      for e in h.entries:
          p.add(e)
      parents.append(p)
  return parents

def insert(node, e, T, B):
  """Insert CF e below node. Returns True if node now overflows (> B entries)."""
  if not node.entries:
      node.entries.append(e); return False
  k = int(np.argmin([np.sum((x.centroid - e.centroid) ** 2) for x in node.entries]))
  near = node.entries[k]
  if near.child is not None:                 # internal entry: recurse
      if not insert(near.child, e, T, B):
          near.add(e); return False
      node.entries[k:k + 1] = []             # child overflowed: replace it by two halves
      a, b = split(near.child)
      node.entries.insert(k, a); node.entries.append(b)
      return len(node.entries) > B
  if near.radius_with(e) <= T:               # leaf entry: absorb if still tight
      near.add(e); return False
  node.entries.append(e)                     # otherwise start a new subcluster
  return len(node.entries) > B

def leaf_entries(node):
  return node.entries if node.leaf else [x for e in node.entries for x in leaf_entries(e.child)]

def ward(C, k):
  groups = [[i] for i in range(len(C))]
  while len(groups) > k:
      best = None
      for a in range(len(groups)):
          for b in range(a + 1, len(groups)):
              na, nb = len(groups[a]), len(groups[b])
              d = np.sqrt(2 * na * nb / (na + nb)) * np.linalg.norm(C[groups[a]].mean(0) - C[groups[b]].mean(0))
              if best is None or d < best[0]:
                  best = (d, a, b)
      d, a, b = best
      print(f"  merge {groups[a]} + {groups[b]}  (Ward distance {d:.3f})")
      groups = [g for i, g in enumerate(groups) if i not in (a, b)] + [sorted(groups[a] + groups[b])]
  lab = np.empty(len(C), int)
  for c, g in enumerate(sorted(groups)):
      lab[g] = c
  return lab

def birch(X, T=0.6, B=3, k=3):
  root = Node(leaf=True)
  for x in X:                                # phase 1: one pass builds the CF tree
      if insert(root, CF(x), T, B):
          a, b = split(root)
          root = Node(leaf=False); root.entries = [a, b]
  E = leaf_entries(root)
  C = np.array([e.centroid for e in E])
  sub_labels = ward(C, k)                    # phase 3: global clustering of centroids
  predict = lambda Z: sub_labels[((np.asarray(Z)[:, None] - C[None]) ** 2).sum(-1).argmin(1)]
  return E, C, predict

X = np.array([[1, 1], [2, 1], [6, 2], [1.5, 2], [7, 2], [4, 7],
            [6.5, 1], [3.5, 6], [1, 2.5], [5, 6.5], [7, 3], [4.5, 5.5]])
E, C, predict = birch(X, T=0.6, B=3, k=3)
for e in E:
  print(f"N={e.n}  LS={e.ls}  SS={e.ss:g}  centroid={e.centroid}  R={np.sqrt(e.ss/e.n - e.centroid @ e.centroid):.3f}")
print("labels:", predict(X))
print("new point (3, 4) ->", predict([[3, 4]]))

# Output:
#   merge [4] + [5]  (Ward distance 1.000)        # S2 + S5
#   merge [2] + [3]  (Ward distance 1.118)        # S4 + S6
#   merge [0] + [1]  (Ward distance 1.275)        # S1 + S3
#   merge [6] + [4, 5]  (Ward distance 1.826)     # S7 + {S2, S5}
# N=2  LS=[3. 2.]  SS=7  centroid=[1.5 1. ]  R=0.500
# N=2  LS=[2.5 4.5]  SS=13.5  centroid=[1.25 2.25]  R=0.354
# N=2  LS=[ 7.5 13. ]  SS=113.25  centroid=[3.75 6.5 ]  R=0.559
# N=2  LS=[ 9.5 12. ]  SS=117.75  centroid=[4.75 6.  ]  R=0.559
# N=2  LS=[13.  4.]  SS=93  centroid=[6.5 2. ]  R=0.500
# N=1  LS=[6.5 1. ]  SS=43.25  centroid=[6.5 1. ]  R=0.000
# N=1  LS=[7. 3.]  SS=58  centroid=[7. 3.]  R=0.000
# labels: [0 0 2 0 2 1 2 1 0 1 2 1]
# new point (3, 4) -> [0]
```

From scratch with NumPy: CF entries, the CF tree with absorb/split, Ward on the leaf centroids, nearest-centroid prediction. Same rules as scikit-learn.

```python
import numpy as np
from sklearn.cluster import Birch

X = np.array([[1, 1], [2, 1], [6, 2], [1.5, 2], [7, 2], [4, 7],
            [6.5, 1], [3.5, 6], [1, 2.5], [5, 6.5], [7, 3], [4.5, 5.5]])

model = Birch(threshold=0.6, branching_factor=3, n_clusters=3).fit(X)
print("subclusters:", len(model.subcluster_centers_))   # 7
print(model.subcluster_centers_)       # same 7 centroids (listed in leaf order A, B, C)
print("subcluster labels:", model.subcluster_labels_)   # [1 1 0 0 0 2 2]
print("labels:", model.labels_)        # [1 1 0 1 0 2 0 2 1 2 0 2]  = groups A, B, C
print("new point (3, 4) ->", model.predict([[3, 4]]))   # [1] -> group A

# Effect of the threshold on the same data
for T in [0.3, 0.5, 0.6, 0.7, 1.0]:
  m = Birch(threshold=T, branching_factor=3, n_clusters=3).fit(X)
  print(f"T={T}: {len(m.subcluster_centers_):2d} subclusters, (3,4) -> nearest centre",
        m.subcluster_centers_[m.transform([[3, 4]]).argmin()], "label", m.predict([[3, 4]])[0])
# T=0.3: 12 subclusters, nearest [3.5 6.]    (group C)
# T=0.5:  9 subclusters, nearest [3.5 6.]    (group C)
# T=0.6:  7 subclusters, nearest [1.25 2.25] (group A)
# T=0.7:  6 subclusters, nearest [1. 2.5]    (group A)
# T=1.0:  3 subclusters, nearest [4.25 6.25] (group C)

# Streaming: feed the data in chunks with partial_fit -> identical tree
s = Birch(threshold=0.6, branching_factor=3, n_clusters=3)
for chunk in np.array_split(X, 3):
  s.partial_fit(chunk)
print("partial_fit subclusters:", len(s.subcluster_centers_), "labels:", s.predict(X))
# partial_fit subclusters: 7 labels: [1 1 0 1 0 2 0 2 1 2 0 2]
```

scikit-learn on the worked example, the effect of T on the borderline point, and streaming with partial_fit.

> **Cluster numbers are arbitrary:** The NumPy version numbers clusters A, C, B as 0, 1, 2; scikit-learn numbers them B, A, C as 0, 1, 2. The partitions are identical — compare clusterings with the adjusted Rand index, not by label value.

**Strengths**

- The data is too big for memory or arrives as a stream: one pass, bounded memory, partial_fit.
- You want to run an expensive clusterer (Ward, spectral, GMM) on millions of points — use BIRCH as the compressor in front of it.
- Clusters are compact and roughly spherical in a low-to-moderate number of standardised numeric features.
- You need a cheap data reduction: thousands of weighted centroids that preserve counts, means and spreads.

**Limitations**

- Clusters have arbitrary shapes or varying density — a radius threshold cuts them into balls; use **DBSCAN** or **HDBSCAN**.
- Data is high-dimensional (dozens of features or more): distances concentrate and the number of subclusters explodes as $(L/T)^d$.
- Features are categorical or the metric is not Euclidean: CFs need means and squared norms.
- The dataset is small: plain agglomerative clustering or k-means gives an exact answer with no threshold to tune.

- **Pre-clustering very large tables:** Compress millions of rows into a few thousand CFs, then run hierarchical clustering or a mixture model on them (the TwoStep cluster procedure in SPSS is built on a CF tree).
- **Streaming and IoT telemetry:** Sensor or log features arrive continuously; partial_fit keeps the summary up to date without storing history.
- **Image colour quantisation:** Millions of pixel colours (3-D) are summarised into subclusters, then grouped into a small palette.
- **Customer and transaction segmentation:** One scan over a large transaction database produces segments, and new customers are assigned by nearest centroid.

**Question:** Two leaf CFs are (2, (3, 2), 7) and (2, (2.5, 4.5), 13.5). What are the centroid and radius of their union?

- A. (1.375, 1.625) and 0.771
- B. (2.75, 3.25) and 0.771
- C. (1.375, 1.625) and 0.427
- D. (1.375, 1.625) and 0.594

**Answer:** A. (1.375, 1.625) and 0.771 — Add the CFs: $(4,(5.5,6.5),20.5)$. Centroid $=(5.5,6.5)/4=(1.375,1.625)$. $R^2=20.5/4-(1.375^2+1.625^2)=5.125-4.531=0.594$, so $R=0.771$ — the A-side root entry in the worked example.

**Question:** With T = 0.5, a leaf entry holds a single point. A new point arrives 1.1 away from it and nothing else is nearer. What happens?

- A. It is absorbed, because 1.1 < 2T
- B. It starts a new entry, because the merged radius 0.55 > 0.5
- C. It is absorbed, because the radius test only applies to entries with N ≥ 2
- D. The leaf splits immediately

**Answer:** B. It starts a new entry, because the merged radius 0.55 > 0.5 — Two points at distance $\delta$ form a subcluster of radius $\delta/2=0.55>T$. Two single points merge only if they are at most $2T=1.0$ apart. Whether the leaf then splits depends on how many entries it already has.

**Question:** You halve the threshold T on 2-D data. What happens to the number of leaf subclusters, roughly?

- A. Halves
- B. Stays the same — B controls it
- C. Grows, up to about 4× (2^d)
- D. Grows exactly 2×

**Answer:** C. Grows, up to about 4× (2^d) — Each subcluster covers a ball of radius about $T$; covering a fixed area needs about $(L/T)^d$ of them, so halving $T$ in $d=2$ multiplies the count by up to 4. On the 100,000-point blobs, going from T = 1.0 to 0.5 took the count from 26 to 214 (more than 4×, because large subclusters also stop absorbing neighbouring ones). B only changes the tree shape, not the leaves' tightness.

**Question:** Why can BIRCH discard the raw points yet still compute each subcluster's radius exactly?

- A. It keeps a random sample of each subcluster
- B. Radius is a function of (N, LS, SS) and CFs are additive
- C. It recomputes the radius on a second pass
- D. It approximates the radius by the distance to the farthest point

**Answer:** B. Radius is a function of (N, LS, SS) and CFs are additive — $R^2=SS/N-\lVert\mathbf{LS}/N\rVert^2$, and the CF of a union is the sum of the CFs. Every absorb, merge and parent update is an addition, so the statistics stay exact without the points.

**Key points**

- A clustering feature $(N,\mathbf{LS},SS)$ is additive and gives the count, centroid $\mathbf{LS}/N$ and radius $\sqrt{SS/N-\lVert\mathbf{LS}/N\rVert^2}$ of a set without storing it.
- BIRCH inserts each point once: descend to the nearest leaf entry, absorb it if the merged radius stays ≤ T, otherwise add a new entry; nodes with more than B entries split on their farthest pair, so the tree stays balanced.
- T controls compression (two points merge only within $2T$; the subcluster count grows like $(L/T)^d$); B only controls the tree's shape and descent cost.
- The leaves are then clustered by a global method (Ward by default in scikit-learn), and every point takes the label of its nearest leaf centroid.
- Standardise and centre the data, beware the unweighted global step and order effects, and prefer density-based methods for non-spherical clusters.

---

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