BIRCH

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

17 min read1999 wordsadvanced9 viewsupdated 2026-10-07

Definition

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,LS,SS)(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.

At a glance

Task
Clustering (unsupervised) of large or streaming numeric data
Input → output
points x1,…,xn∈Rdx_1,\dots,x_n\in\mathbb{R}^d → leaf subclusters (CF entries), then kk cluster labels
Learns
a CF tree whose leaves hold m≪nm \ll n clustering features (N,LS,SS)(N,\mathbf{LS},SS); a cluster label per leaf entry
Training
one pass: O(n B h d)O(n\,B\,h\,d) with tree height h≈log⁡Bmh\approx\log_B m; plus the global step on mm centroids (Ward: about O(m2)O(m^2))
Prediction
O(m d)O(m\,d): nearest leaf centroid, then its cluster label
Memory
O(m d)O(m\,d) — independent of nn once TT 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×nn\times n distance matrix: for n=100,000n=100{,}000 points the condensed matrix alone is (n2)⋅8\binom{n}{2}\cdot 8 bytes ≈40\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 nn, 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 TT? 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,LS,SS)(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 ≤T\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.

CF(S)=(N,  LS,  SS)=(∣S∣,  ∑x∈Sx,  ∑x∈S∥x∥2)\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)
SS
a set of points (one subcluster)
NN
number of points in S
LS\mathbf{LS}
linear sum — a vector in Rd\mathbb{R}^d
SSSS
squared sum — one number, the sum of squared Euclidean norms (the 1996 paper also uses a scalar)

Additivity. If S1S_1 and S2S_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.

CF(S1∪S2)=(N1+N2,  LS1+LS2,  SS1+SS2)\mathrm{CF}(S_1\cup S_2)=\big(N_1+N_2,\;\mathbf{LS}_1+\mathbf{LS}_2,\;SS_1+SS_2\big)
S1,S2S_1,S_2
two disjoint point sets

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

R2=1N∑x∈S∥x−c∥2=1N(∑∥x∥2−2c⊤ ⁣∑x+N∥c∥2)=SSN−∥LSN∥2R^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
cc
centroid LS/N\mathbf{LS}/N
RR
radius: RMS distance of the members to the centroid

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

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

R(CF+(1,x,∥x∥2))≤TR\big(\mathrm{CF}+(1,x,\lVert x\rVert^2)\big)\le T
TT
the threshold hyperparameter
(1,x,∥x∥2)(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 NR2N R^2 grows by a known amount when xx joins (the same term that appears in Ward's criterion): adding a point at distance δ=∥x−c∥\delta=\lVert x-c\rVert from the centroid gives

(N+1) R′2=NR2+NN+1 δ2⟹R′2=NR2+NN+1δ2N+1(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′R'
radius after absorbing x
δ\delta
distance from x to the current centroid

Two consequences. For a single point (N=1N=1, R=0R=0) the merged radius is δ/2\delta/2, so two points merge when they are at most 2T2T apart. And as NN grows, NN+1δ2/(N+1)≈δ2/N\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.

The hyperparameters, mathematically. TT sets the volume each subcluster may cover; in dd dimensions a region of extent LL needs on the order of (L/T)d(L/T)^d subclusters, so halving TT multiplies the number of leaf entries mm by up to 2d2^d (on our data: T=1.0T=1.0 gives 3 subclusters, T=0.6T=0.6 gives 7, T=0.3T=0.3 gives 12, i.e. one per point). BB sets the fan-out: the height is about ⌈log⁡Bm⌉\lceil\log_B m\rceil, each insertion compares the point with at most BB centroids per level, so it costs O(B h d)O(B\,h\,d). Large BB → shallow tree but more comparisons per node; small BB → 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.6T=0.6 and branching factor B=3B=3, then cluster the leaves into k=3k=3.

PointxyFinal leaf entryCluster
P111S1A
P221S1A
P362S2B
P41.52S3A
P572S2B
P647S4C
P76.51S5B
P83.56S4C
P912.5S3A
P1056.5S6C
P1173S7B
P124.55.5S6C
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).

Phase 1: one pass, by hand

  1. 1P1 = (1, 1). The tree is empty, so P1 becomes leaf entry S1 =(1,(1,1),2)=(1,(1,1),2).
  2. 2P2 = (2, 1). Nearest entry S1. Merged CF (2,(3,2),7)(2,(3,2),7): centroid (1.5,1)(1.5,1), R2=72−(1.52+12)=0.25R^2=\tfrac72-(1.5^2+1^2)=0.25, R=0.5≤0.6R=0.5\le0.6 → absorb. S1 =(2,(3,2),7)=(2,(3,2),7).
  3. 3P3 = (6, 2). Merged with S1 the radius would be 2.211>0.62.211>0.6 → new entry S2.
  4. 4P4 = (1.5, 2). Nearest S1, δ=1\delta=1: R′2=(2⋅0.25+23⋅1)/3=0.389R'^2=\big(2\cdot0.25+\tfrac23\cdot1\big)/3=0.389, R′=0.624>0.6R'=0.624>0.6 → new entry S3. The leaf now holds 3 entries — full, but not over BB.
  5. 5P5 = (7, 2). S2 absorbs it: R=0.5R=0.5, S2 =(2,(13,4),93)=(2,(13,4),93).
  6. 6P6 = (4, 7). Nearest S2 at distance 5.590, merged radius 2.667 → new entry S4; the leaf has 4>B4>B entries → split. Squared distances between the four centroids: S1–S4 =42.25=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}\{S1,S2,S3\} and a CF of 1 point over {S4}\{S4\}. Height is now 2.
  7. 7P7 = (6.5, 1). At the root the nearest entry is the 5-point CF (centroid (3.5,1.6)(3.5,1.6)). In its leaf the nearest is S2 at δ=1\delta=1: R′=0.624>0.6R'=0.624>0.6 → new entry S5; the leaf overflows again with {S1,S2,S3,S5}\{S1,S2,S3,S5\}. Farthest pair S1–S2 (squared distance 26) → leaves {S1,S3}\{S1,S3\} and {S2,S5}\{S2,S5\}. The root now has 3 entries: A-side, C-side, B-side.
  8. 8P8 = (3.5, 6) joins S4 (R=0.559R=0.559). P9 = (1, 2.5) joins S3 (δ=0.707\delta=0.707, R=0.354R=0.354).
  9. 9P10 = (5, 6.5). Nearest S4 =(3.75,6.5)=(3.75,6.5) at δ=1.25\delta=1.25: R′2=(2⋅0.3125+23⋅1.5625)/3=0.556R'^2=\big(2\cdot0.3125+\tfrac23\cdot1.5625\big)/3=0.556, R′=0.745R'=0.745 → new entry S6.
  10. 10P11 = (7, 3). Nearest S2 at 1.118, merged radius 0.667 → new entry S7; the B-side leaf holds {S2,S5,S7}\{S2,S5,S7\} — exactly BB, no split.
  11. 11P12 = (4.5, 5.5). Nearest S6 at 1.118 → absorbed, R=0.559R=0.559. Done: 12 points → 7 leaf CFs in 3 leaves under one root.
EntryNLSSSCentroidRClusterdist to (3, 4)
S12(3, 2)7(1.5, 1)0.500A3.354
S32(2.5, 4.5)13.5(1.25, 2.25)0.354A2.475
S42(7.5, 13)113.25(3.75, 6.5)0.559C2.610
S62(9.5, 12)117.75(4.75, 6)0.559C2.658
S22(13, 4)93(6.5, 2)0.500B4.031
S51(6.5, 1)43.25(6.5, 1)0.000B4.610
S71(7, 3)58(7, 3)0.000B4.123
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.

Phase 3: global clustering and a prediction

  1. 1Run Ward agglomerative clustering on the 7 centroids (treated as 7 ordinary points, as scikit-learn does). Ward distances 2Δ\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. 2Stop at k=3k=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. 3New 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.
▸ BIRCH · building the CF treestep 1/28
TB
022446688P1P2P3P4P5P6P7P8P9P10P11P12empty CF treeT = 0.6 B = 3CF = (N, LS, SS)R = √(SS/N − ‖LS/N‖²)read 0/12 · 0 leaf CFstree height 0CF tree(empty)
T = 0.6B = 3leaf CFs = 0 / final 7
  1. 1for each x (one pass):
  2. 2 descend to nearest CF
  3. 3 if R(CF + x) ≤ T: absorb
  4. 4 else: new leaf entry
  5. 5 if > B entries: split
  6. 6 split moves up / new root
  7. 7global: Ward on centroids
  8. 8label = nearest centroid

12 points will arrive one at a time, in the order P1…P12. T = 0.6 (max subcluster radius), B = 3 (max entries per node). The tree starts empty.

fig.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. 1Phase 1: build the CF tree (one scan). For each point xx: start at the root and repeatedly descend into the entry whose centroid is nearest to xx, until you reach a leaf.
  2. 2Absorb or insert. In the leaf, take the nearest entry. If its radius after absorbing xx is ≤T\le T, add (1,x,∥x∥2)(1,x,\lVert x\rVert^2) to it. Otherwise append xx as a new entry.
  3. 3Split on overflow. If the leaf now has more than BB 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. 4Update the path. Add xx's CF to every internal entry on the way down (additivity), so each parent summarises its subtree.
  5. 5Phase 2 (optional, original paper): condense. If memory runs out, increase TT 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. 6Phase 3: global clustering. Cluster the mm leaf centroids (or the full CFs) with Ward, k-means or any other algorithm into kk clusters.
  7. 7Phase 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)O(n\,B\,h\,d) time with h≈log⁡Bmh\approx\log_B m, and O(m d)O(m\,d) memory for mm leaf entries. Phase 3 depends on the global method: Ward on centroids costs about O(m2)O(m^2) memory and time, trivial when mm is a few thousand. On 100,000 points from 5 Gaussian blobs, scikit-learn's BIRCH with B=50B=50 keeps 525 leaf CFs at T=0.3T=0.3, 214 at T=0.5T=0.5, 26 at T=1.0T=1.0 and 5 at T=2.0T=2.0 — a 190× to 20,000× compression.

Hyperparameters, variants and tuning

ParameterEffectPractical 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_clustersThe 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_fitInsert 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_labelsWhether to label the training data at the end of fit.Turn off for very large data and call predict on what you need.
What to set in scikit-learn's Birch, and what each knob does.

Variants and relatives

Diameter threshold
the original paper lets the absorb test use the diameter DD instead of RR; 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,mean,scatter)(N,\text{mean},\text{scatter}) instead of (N,LS,SS)(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

In code

python
1import numpy as np
2
3class CF:
4 """Clustering feature: N, linear sum LS, squared sum SS (sum of squared norms)."""
5 def __init__(self, x=None):
6 self.n, self.ls, self.ss, self.child = 0, 0.0, 0.0, None
7 if x is not None:
8 self.n, self.ls, self.ss = 1, np.array(x, float), float(np.dot(x, x))
9 @property
10 def centroid(self):
11 return self.ls / self.n
12 def add(self, o): # additivity: CF1 + CF2
13 self.n, self.ls, self.ss = self.n + o.n, self.ls + o.ls, self.ss + o.ss
14 def radius_with(self, o): # radius of the merged subcluster
15 n, ls, ss = self.n + o.n, self.ls + o.ls, self.ss + o.ss
16 return np.sqrt(max(ss / n - np.dot(ls / n, ls / n), 0.0))
17
18class Node:
19 def __init__(self, leaf):
20 self.leaf, self.entries = leaf, []
21
22def split(node):
23 C = np.array([e.centroid for e in node.entries])
24 D = ((C[:, None] - C[None]) ** 2).sum(-1)
25 i, j = np.unravel_index(D.argmax(), D.shape) # farthest pair = seeds
26 halves = (Node(node.leaf), Node(node.leaf))
27 for k, e in enumerate(node.entries):
28 halves[0 if (k == i or D[i, k] < D[j, k]) else 1].entries.append(e)
29 parents = []
30 for h in halves:
31 p = CF(); p.child = h
32 for e in h.entries:
33 p.add(e)
34 parents.append(p)
35 return parents
36
37def insert(node, e, T, B):
38 """Insert CF e below node. Returns True if node now overflows (> B entries)."""
39 if not node.entries:
40 node.entries.append(e); return False
41 k = int(np.argmin([np.sum((x.centroid - e.centroid) ** 2) for x in node.entries]))
42 near = node.entries[k]
43 if near.child is not None: # internal entry: recurse
44 if not insert(near.child, e, T, B):
45 near.add(e); return False
46 node.entries[k:k + 1] = [] # child overflowed: replace it by two halves
47 a, b = split(near.child)
48 node.entries.insert(k, a); node.entries.append(b)
49 return len(node.entries) > B
50 if near.radius_with(e) <= T: # leaf entry: absorb if still tight
51 near.add(e); return False
52 node.entries.append(e) # otherwise start a new subcluster
53 return len(node.entries) > B
54
55def leaf_entries(node):
56 return node.entries if node.leaf else [x for e in node.entries for x in leaf_entries(e.child)]
57
58def ward(C, k):
59 groups = [[i] for i in range(len(C))]
60 while len(groups) > k:
61 best = None
62 for a in range(len(groups)):
63 for b in range(a + 1, len(groups)):
64 na, nb = len(groups[a]), len(groups[b])
65 d = np.sqrt(2 * na * nb / (na + nb)) * np.linalg.norm(C[groups[a]].mean(0) - C[groups[b]].mean(0))
66 if best is None or d < best[0]:
67 best = (d, a, b)
68 d, a, b = best
69 print(f" merge {groups[a]} + {groups[b]} (Ward distance {d:.3f})")
70 groups = [g for i, g in enumerate(groups) if i not in (a, b)] + [sorted(groups[a] + groups[b])]
71 lab = np.empty(len(C), int)
72 for c, g in enumerate(sorted(groups)):
73 lab[g] = c
74 return lab
75
76def birch(X, T=0.6, B=3, k=3):
77 root = Node(leaf=True)
78 for x in X: # phase 1: one pass builds the CF tree
79 if insert(root, CF(x), T, B):
80 a, b = split(root)
81 root = Node(leaf=False); root.entries = [a, b]
82 E = leaf_entries(root)
83 C = np.array([e.centroid for e in E])
84 sub_labels = ward(C, k) # phase 3: global clustering of centroids
85 predict = lambda Z: sub_labels[((np.asarray(Z)[:, None] - C[None]) ** 2).sum(-1).argmin(1)]
86 return E, C, predict
87
88X = np.array([[1, 1], [2, 1], [6, 2], [1.5, 2], [7, 2], [4, 7],
89 [6.5, 1], [3.5, 6], [1, 2.5], [5, 6.5], [7, 3], [4.5, 5.5]])
90E, C, predict = birch(X, T=0.6, B=3, k=3)
91for e in E:
92 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}")
93print("labels:", predict(X))
94print("new point (3, 4) ->", predict([[3, 4]]))
95
96# Output:
97# merge [4] + [5] (Ward distance 1.000) # S2 + S5
98# merge [2] + [3] (Ward distance 1.118) # S4 + S6
99# merge [0] + [1] (Ward distance 1.275) # S1 + S3
100# merge [6] + [4, 5] (Ward distance 1.826) # S7 + {S2, S5}
101# N=2 LS=[3. 2.] SS=7 centroid=[1.5 1. ] R=0.500
102# N=2 LS=[2.5 4.5] SS=13.5 centroid=[1.25 2.25] R=0.354
103# N=2 LS=[ 7.5 13. ] SS=113.25 centroid=[3.75 6.5 ] R=0.559
104# N=2 LS=[ 9.5 12. ] SS=117.75 centroid=[4.75 6. ] R=0.559
105# N=2 LS=[13. 4.] SS=93 centroid=[6.5 2. ] R=0.500
106# N=1 LS=[6.5 1. ] SS=43.25 centroid=[6.5 1. ] R=0.000
107# N=1 LS=[7. 3.] SS=58 centroid=[7. 3.] R=0.000
108# labels: [0 0 2 0 2 1 2 1 0 1 2 1]
109# 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
1import numpy as np
2from sklearn.cluster import Birch
3
4X = np.array([[1, 1], [2, 1], [6, 2], [1.5, 2], [7, 2], [4, 7],
5 [6.5, 1], [3.5, 6], [1, 2.5], [5, 6.5], [7, 3], [4.5, 5.5]])
6
7model = Birch(threshold=0.6, branching_factor=3, n_clusters=3).fit(X)
8print("subclusters:", len(model.subcluster_centers_)) # 7
9print(model.subcluster_centers_) # same 7 centroids (listed in leaf order A, B, C)
10print("subcluster labels:", model.subcluster_labels_) # [1 1 0 0 0 2 2]
11print("labels:", model.labels_) # [1 1 0 1 0 2 0 2 1 2 0 2] = groups A, B, C
12print("new point (3, 4) ->", model.predict([[3, 4]])) # [1] -> group A
13
14# Effect of the threshold on the same data
15for T in [0.3, 0.5, 0.6, 0.7, 1.0]:
16 m = Birch(threshold=T, branching_factor=3, n_clusters=3).fit(X)
17 print(f"T={T}: {len(m.subcluster_centers_):2d} subclusters, (3,4) -> nearest centre",
18 m.subcluster_centers_[m.transform([[3, 4]]).argmin()], "label", m.predict([[3, 4]])[0])
19# T=0.3: 12 subclusters, nearest [3.5 6.] (group C)
20# T=0.5: 9 subclusters, nearest [3.5 6.] (group C)
21# T=0.6: 7 subclusters, nearest [1.25 2.25] (group A)
22# T=0.7: 6 subclusters, nearest [1. 2.5] (group A)
23# T=1.0: 3 subclusters, nearest [4.25 6.25] (group C)
24
25# Streaming: feed the data in chunks with partial_fit -> identical tree
26s = Birch(threshold=0.6, branching_factor=3, n_clusters=3)
27for chunk in np.array_split(X, 3):
28 s.partial_fit(chunk)
29print("partial_fit subclusters:", len(s.subcluster_centers_), "labels:", s.predict(X))
30# 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.

Use when

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

Avoid when

  • −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(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.

Where it's used

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.

Check yourself

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?

Check yourself

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?

Check yourself

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

Check yourself

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

Remember

  • ✓A clustering feature (N,LS,SS)(N,\mathbf{LS},SS) is additive and gives the count, centroid LS/N\mathbf{LS}/N and radius SS/N−∥LS/N∥2\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 2T2T; the subcluster count grows like (L/T)d(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.
← back to ML Algorithms roadmap