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 — 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 → leaf subclusters (CF entries), then cluster labels
- Learns
- a CF tree whose leaves hold clustering features ; a cluster label per leaf entry
- Training
- one pass: with tree height ; plus the global step on centroids (Ward: about )
- Prediction
- : nearest leaf centroid, then its cluster label
- Memory
- — independent of once 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 distance matrix: for points the condensed matrix alone is bytes 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 , 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 ? 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 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
- 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.
- a set of points (one subcluster)
- number of points in S
- linear sum — a vector in
- squared sum — one number, the sum of squared Euclidean norms (the 1996 paper also uses a scalar)
Additivity. If and 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.
- two disjoint point sets
Centroid and radius. The centroid is . The radius is the root-mean-square distance of the points to the centroid. Expand the square and use :
- centroid
- radius: RMS distance of the members to the centroid
The diameter — RMS distance between pairs of members — is also a function of the CF: . The paper allows either; scikit-learn uses . For the two points and : , (the plain distance between them).
The absorb test. A leaf entry with CF may absorb a new point only if the merged subcluster stays tight:
- the threshold hyperparameter
- the CF of the single point x
It helps to see what this test means. The total squared spread grows by a known amount when joins (the same term that appears in Ward's criterion): adding a point at distance from the centroid gives
- radius after absorbing x
- distance from x to the current centroid
Two consequences. For a single point (, ) the merged radius is , so two points merge when they are at most apart. And as grows, , so large subclusters accept far-away points more easily — a point at distance from a big, tight subcluster barely moves its radius. That is why the insertion order matters a little.
The hyperparameters, mathematically. sets the volume each subcluster may cover; in dimensions a region of extent needs on the order of subclusters, so halving multiplies the number of leaf entries by up to (on our data: gives 3 subclusters, gives 7, gives 12, i.e. one per point). sets the fan-out: the height is about , each insertion compares the point with at most centroids per level, so it costs . Large → shallow tree but more comparisons per node; small → 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 and branching factor , then cluster the leaves into .
| 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
- 1P1 = (1, 1). The tree is empty, so P1 becomes leaf entry S1 .
- 2P2 = (2, 1). Nearest entry S1. Merged CF : centroid , , → absorb. S1 .
- 3P3 = (6, 2). Merged with S1 the radius would be → new entry S2.
- 4P4 = (1.5, 2). Nearest S1, : , → new entry S3. The leaf now holds 3 entries — full, but not over .
- 5P5 = (7, 2). S2 absorbs it: , S2 .
- 6P6 = (4, 7). Nearest S2 at distance 5.590, merged radius 2.667 → new entry S4; the leaf has entries → split. Squared distances between the four centroids: S1–S4 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 and a CF of 1 point over . Height is now 2.
- 7P7 = (6.5, 1). At the root the nearest entry is the 5-point CF (centroid ). In its leaf the nearest is S2 at : → new entry S5; the leaf overflows again with . Farthest pair S1–S2 (squared distance 26) → leaves and . The root now has 3 entries: A-side, C-side, B-side.
- 8P8 = (3.5, 6) joins S4 (). P9 = (1, 2.5) joins S3 (, ).
- 9P10 = (5, 6.5). Nearest S4 at : , → new entry S6.
- 10P11 = (7, 3). Nearest S2 at 1.118, merged radius 0.667 → new entry S7; the B-side leaf holds — exactly , no split.
- 11P12 = (4.5, 5.5). Nearest S6 at 1.118 → absorbed, . Done: 12 points → 7 leaf CFs in 3 leaves under one root.
| 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
- 1Run Ward agglomerative clustering on the 7 centroids (treated as 7 ordinary points, as scikit-learn does). Ward distances , where 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.
- 2Stop at : 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.
- 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.
- 1for each x (one pass):
- 2 descend to nearest CF
- 3 if R(CF + x) ≤ T: absorb
- 4 else: new leaf entry
- 5 if > B entries: split
- 6 split moves up / new root
- 7global: Ward on centroids
- 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.
The algorithm, step by step
BIRCH(X, T, B, k)
- 1Phase 1: build the CF tree (one scan). For each point : start at the root and repeatedly descend into the entry whose centroid is nearest to , until you reach a leaf.
- 2Absorb or insert. In the leaf, take the nearest entry. If its radius after absorbing is , add to it. Otherwise append as a new entry.
- 3Split on overflow. If the leaf now has more than 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.
- 4Update the path. Add 's CF to every internal entry on the way down (additivity), so each parent summarises its subtree.
- 5Phase 2 (optional, original paper): condense. If memory runs out, increase 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.
- 6Phase 3: global clustering. Cluster the leaf centroids (or the full CFs) with Ward, k-means or any other algorithm into clusters.
- 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 time with , and memory for leaf entries. Phase 3 depends on the global method: Ward on centroids costs about memory and time, trivial when is a few thousand. On 100,000 points from 5 Gaussian blobs, scikit-learn's BIRCH with keeps 525 leaf CFs at , 214 at , 26 at and 5 at — a 190× to 20,000× compression.
Hyperparameters, variants and tuning
| 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 instead of ; 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 instead of , 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
1import numpy as np23class 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, None7 if x is not None:8 self.n, self.ls, self.ss = 1, np.array(x, float), float(np.dot(x, x))9 @property10 def centroid(self):11 return self.ls / self.n12 def add(self, o): # additivity: CF1 + CF213 self.n, self.ls, self.ss = self.n + o.n, self.ls + o.ls, self.ss + o.ss14 def radius_with(self, o): # radius of the merged subcluster15 n, ls, ss = self.n + o.n, self.ls + o.ls, self.ss + o.ss16 return np.sqrt(max(ss / n - np.dot(ls / n, ls / n), 0.0))1718class Node:19 def __init__(self, leaf):20 self.leaf, self.entries = leaf, []2122def 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 = seeds26 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 = h32 for e in h.entries:33 p.add(e)34 parents.append(p)35 return parents3637def 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 False41 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: recurse44 if not insert(near.child, e, T, B):45 near.add(e); return False46 node.entries[k:k + 1] = [] # child overflowed: replace it by two halves47 a, b = split(near.child)48 node.entries.insert(k, a); node.entries.append(b)49 return len(node.entries) > B50 if near.radius_with(e) <= T: # leaf entry: absorb if still tight51 near.add(e); return False52 node.entries.append(e) # otherwise start a new subcluster53 return len(node.entries) > B5455def leaf_entries(node):56 return node.entries if node.leaf else [x for e in node.entries for x in leaf_entries(e.child)]5758def ward(C, k):59 groups = [[i] for i in range(len(C))]60 while len(groups) > k:61 best = None62 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 = best69 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] = c74 return lab7576def 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 tree79 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 centroids85 predict = lambda Z: sub_labels[((np.asarray(Z)[:, None] - C[None]) ** 2).sum(-1).argmin(1)]86 return E, C, predict8788X = 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]]))9596# Output:97# merge [4] + [5] (Ward distance 1.000) # S2 + S598# merge [2] + [3] (Ward distance 1.118) # S4 + S699# merge [0] + [1] (Ward distance 1.275) # S1 + S3100# 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.500102# N=2 LS=[2.5 4.5] SS=13.5 centroid=[1.25 2.25] R=0.354103# N=2 LS=[ 7.5 13. ] SS=113.25 centroid=[3.75 6.5 ] R=0.559104# N=2 LS=[ 9.5 12. ] SS=117.75 centroid=[4.75 6. ] R=0.559105# N=2 LS=[13. 4.] SS=93 centroid=[6.5 2. ] R=0.500106# N=1 LS=[6.5 1. ] SS=43.25 centroid=[6.5 1. ] R=0.000107# N=1 LS=[7. 3.] SS=58 centroid=[7. 3.] R=0.000108# labels: [0 0 2 0 2 1 2 1 0 1 2 1]109# new point (3, 4) -> [0]1import numpy as np2from sklearn.cluster import Birch34X = 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]])67model = Birch(threshold=0.6, branching_factor=3, n_clusters=3).fit(X)8print("subclusters:", len(model.subcluster_centers_)) # 79print(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, C12print("new point (3, 4) ->", model.predict([[3, 4]])) # [1] -> group A1314# Effect of the threshold on the same data15for 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)2425# Streaming: feed the data in chunks with partial_fit -> identical tree26s = 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]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 .
- −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 is additive and gives the count, centroid and radius 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 ; the subcluster count grows like ); 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.