BIRCH: Clustering Features, CF Trees and Streaming Compression

Separate compression from final clustering

A large numerical dataset may contain many observations close enough that processing them individually is wasteful. BIRCH builds a compact representation of local subclusters, then optionally applies a global clustering procedure to those summaries.

The local compression and final partition solve different problems. A small compression radius controls how much local detail can be collapsed. The global stage decides which compressed groups should belong together. Increasing the requested final cluster count cannot recover boundaries already erased by compression.

The clustering-feature triple

For a subcluster of numerical vectors, define

Here N is a count, LS a vector and SS a scalar. Some presentations use a vector of coordinatewise squared sums; summing its entries gives the scalar needed below. State the convention when implementing the summary.

The mean and mean squared radius follow directly:

The identity comes from expanding squared deviations around the mean. It gives the average squared distance to the centroid, not the maximum distance of any member. A small RMS radius can still contain a few relatively distant points.

Compute a summary and a merge

For scalar observations 1, 2 and 3, the triple is \(N=3,LS=6,SS=14\). The mean is 2 and \(R^2=14/3-4=2/3\). A separate observation 4 has triple \((1,4,16)\). Merging gives \((4,10,30)\), mean 2.5 and \(R^2=30/4-2.5^2=1.25\).

count, linear_sum, squared_sum = 3, 6.0, 14.0
radius_sq = squared_sum/count - (linear_sum/count)**2
assert abs(radius_sq - 2/3) < 1e-12
count, linear_sum, squared_sum = count+1, linear_sum+4, squared_sum+16
assert abs(squared_sum/count-(linear_sum/count)**2-1.25) < 1e-12

Counts and sums are additive, so merging summaries is cheap. In finite precision, subtracting two large nearly equal quantities can produce an inaccurate variance; stable accumulation, sensible scaling and small-negative roundoff handling matter.

How the CF tree grows

The tree contains internal summaries and leaf subclusters. An incoming observation follows a nearby branch, then attempts to join a nearby leaf entry. If the resulting radius or other specified threshold criterion remains acceptable, update the summary. Otherwise create a new entry.

A branching-factor limit controls how many entries fit in a node. Overflow triggers a split, potentially propagating upward. The exact split and threshold conventions depend on the implementation, so the CF triple alone does not specify an entire reproducible algorithm.

Because observations are inserted sequentially, early summaries influence later decisions. Different insertion orders can produce different leaf entries. Compare shuffled passes or multiple orders when this variation could affect the interpretation.

What the summary cannot reconstruct

Counts, means and aggregate squared spread do not preserve arbitrary shapes, individual members, quantiles or a full covariance matrix. A ring and another distribution can share these limited statistics. Once combined into one CF entry, they cannot generally be separated using that triple alone.

The compression is therefore most natural for Euclidean numerical structure that can be approximated by compact local groups. Text edit distances or categorical equality do not directly support the same vector-sum identities. Encoding categories as arbitrary numbers does not make the geometry meaningful.

For auditing, retain a way to revisit original observations or representative samples. A CF tree is a computational summary, not a complete replacement for data provenance.

The global stage must respect weights

Suppose one leaf entry summarises 1,000 observations and another summarises two. Treating their centroids as equally weighted points can produce a very different result from clustering the original population.

For a final centre c, the original squared error within a subcluster decomposes into its internal SSE plus \(N\|\mu-c\|^2\). The internal term is constant with respect to c, so weighting the subcluster centroid by N preserves this part of the k-means objective. Verify whether the chosen downstream estimator actually receives those weights.

A globally selected centre cannot split a compressed subcluster unless the original observations are revisited. That remains a limitation even when the weighting is correct.

Evaluate compression as well as labels

Measure the number of leaf entries, compression ratio, maximum and typical subcluster spread, final quality and sensitivity to order. Compare the global method on compressed summaries against the same method on a manageable original-data subset.

The tree can greatly reduce memory and repeated processing, but worst-case compression may be poor when every observation requires a separate entry. High-dimensional distances can also make a single radius difficult to interpret.

Use BIRCH when local numerical compression is a valuable stage of the pipeline. Compare mini-batch k-means when a fixed-size centroid codebook is enough, and keep the threshold and global clustering choices visible in the final report.

References

1. Zhang, Ramakrishnan and Livny. BIRCH: An Efficient Data Clustering Method for Very Large Databases. SIGMOD, 1996.
2. scikit-learn. Clustering user guide.