BIRCH clustering features

Summarize points before clustering

BIRCH compresses a large dataset into small summaries called clustering features. A clustering feature (CF) for a subcluster holds the count N, the linear sum LS, and the sum of squared norms SS. Those three numbers give the centroid and radius without storing the points.

Implement birch_subclusters(X, threshold). Return (labels, centroids).

1. Process rows in order. Keep a list of CFs, starting empty.
2. For each point, find the existing CF with the nearest centroid.
3. Compute the radius the CF would have if the point were added: R = sqrt(SS / N − ||LS / N||²), using the merged values.
4. If that radius is at most threshold, add the point to that CF. Otherwise start a new CF with this point.
5. Labels are the CF indices in creation order. Centroids are LS / N for each CF.

Constraints

• threshold must be nonnegative, otherwise raise ValueError.
• Every returned subcluster has radius at most threshold (up to a floating point tolerance of 1e-9).
• Do not modify X.

Hints