Cluster Centroids in Machine Learning

The Problem with Random Undersampling

Random undersampling is the simplest way to handle class imbalance: just randomly remove majority class samples until the classes are balanced. It's fast, trivial to implement, and often surprisingly effective. But there's a fundamental problem: random removal is information-destroying in a structurally blind way.

Imagine your majority class has three distinct clusters -- say, three types of legitimate transactions (small retail, recurring subscriptions, large one-time purchases). Random undersampling might disproportionately wipe out one of these clusters, leaving the classifier with a distorted view of what "legitimate" looks like. The classifier then misclassifies that entire subpopulation as fraudulent.

The Insight: Compress, Don't Delete

Cluster Centroids emerged from a key insight: instead of selecting which samples to keep and which to discard, why not summarize the majority class? If you cluster the majority class into $N$ groups and represent each group by its centroid, you get exactly $N$ representative points that capture the overall shape of the distribution.

This is analogous to image compression. A JPEG doesn't randomly throw away pixels; it transforms the image into a compact representation that preserves the important structure. Cluster Centroids does the same thing for your majority class.

The Prototype Generation Lineage

Cluster Centroids belongs to the prototype generation family of undersampling methods. Unlike prototype selection methods (like Condensed Nearest Neighbours or Tomek Links) that keep a subset of original samples, prototype generation creates entirely new synthetic points. This distinction dates back to Hart's 1968 work on the Condensed Nearest Neighbor rule and has been refined through decades of research.

The specific application of K-Means clustering for undersampling was formalized in the context of Yen and Lee's 2009 work on cluster-based undersampling approaches, which demonstrated that clustering-aware methods consistently outperform random undersampling on standard benchmarks.

Key Takeaway: Cluster Centroids exists because random undersampling is structurally blind. By clustering the majority class and replacing clusters with centroids, we preserve the macro-structure of the majority distribution while achieving aggressive data reduction.

The Mental Model: Summary Statistics for Your Data

Here's the simplest way to think about Cluster Centroids. Imagine you have 10,000 majority class samples and 200 minority class samples. You want to balance the dataset to a 1:1 ratio, so you need to reduce the majority class to approximately 200 samples.

Random undersampling says: "Pick 200 random samples from the 10,000." That's like summarizing a 300-page book by tearing out 200 random pages and keeping only 6 of them. You might get lucky and keep the important pages, but you probably won't.

Cluster Centroids says: "Group those 10,000 samples into 200 clusters, then represent each cluster by its center point." That's like asking 200 expert readers to each summarize a different chapter. You lose the fine-grained details, but you preserve the book's overall structure.

What Makes It Work (and When It Doesn't)

The technique works well when the majority class has a multimodal distribution -- multiple distinct subclusters that K-Means can identify. In this case, the centroids genuinely capture the essential structure.

But here's the flip side: if your majority class data lives near the decision boundary with the minority class, the centroids can drift toward the boundary and create overlapping regions. This is because a centroid is the mean of its cluster -- and means are pulled toward dense regions, which might include samples right on the boundary. This is the single most important failure mode to understand.

Prototype Generation: You're Creating New Data

A subtle but critical point: unlike random undersampling or Tomek Links, Cluster Centroids produces samples that did not exist in the original dataset. The centroids are synthetic points -- weighted averages of real samples. This means:

1. The resampled data may not be consistent with the original data-generating distribution at a local level
2. Classifiers that rely on exact distances (like k-NN) may behave differently than expected
3. The centroids can fall in low-density regions between subclusters, creating "phantom" majority class samples

Understanding this distinction between prototype generation and prototype selection is what separates practitioners who use Cluster Centroids effectively from those who get bitten by its edge cases.

Problem Setup

Let $\mathcal{D} = \{(x_i, y_i)\}_{i=1}^{N}$ be a training set where $x_i \in \mathbb{R}^d$ and $y_i \in \{0, 1\}$. Define the majority class as $\mathcal{M} = \{x_i : y_i = 0\}$ with $|\mathcal{M}| = N_{\text{maj}}$ and the minority class as $\mathcal{S} = \{x_i : y_i = 1\}$ with $|\mathcal{S}| = N_{\text{min}}$, where $N_{\text{maj}} \gg N_{\text{min}}$.

The Algorithm

Cluster Centroids reduces the majority class to $K$ representative points, where $K$ is typically set to $N_{\text{min}}$ (to achieve a 1:1 ratio) or determined by the sampling_strategy parameter.

Step 1: Cluster the majority class. Apply K-Means clustering to $\mathcal{M}$, partitioning it into $K$ clusters $\{C_1, C_2, \ldots, C_K\}$ by minimizing the within-cluster sum of squares:

$\arg\min_{\{C_k\}} \sum_{k=1}^{K} \sum_{x \in C_k} \|x - \mu_k\|^2$

where $\mu_k = \frac{1}{|C_k|} \sum_{x \in C_k} x$ is the centroid of cluster $C_k$.

Step 2: Generate replacement samples. The replacement strategy depends on the voting parameter:

• Soft voting: Use the centroids $\{\mu_1, \mu_2, \ldots, \mu_K\}$ directly as the new majority class samples.
• Hard voting: For each centroid $\mu_k$, find its nearest neighbor in the original majority class $\mathcal{M}$ and use that original sample instead:

$\hat{x}_k = \arg\min_{x \in C_k} \|x - \mu_k\|^2$

Step 3: Form the resampled dataset. The final dataset is:

$\mathcal{D}' = \{(\mu_k, 0)\}_{k=1}^{K} \cup \{(x_i, 1) : x_i \in \mathcal{S}\}$

for soft voting, or equivalently with $\hat{x}_k$ replacing $\mu_k$ for hard voting.

Complexity Analysis

The computational cost is dominated by K-Means:

• Time complexity: $O(N_{\text{maj}} \cdot K \cdot d \cdot T)$ where $T$ is the number of K-Means iterations (typically 100-300)
• Space complexity: $O(N_{\text{maj}} \cdot d)$ for storing the majority class during clustering

For large datasets, this can be substantially more expensive than random undersampling which is $O(N_{\text{min}})$.

Important: The voting='auto' parameter in imbalanced-learn defaults to 'soft' for dense data and 'hard' for sparse data. Sparse data gets hard voting because centroids of sparse vectors are dense, which would change the data representation fundamentally.

What We Covered

Cluster Centroids is a prototype generation undersampling technique that reduces the majority class by clustering it with K-Means and replacing the original samples with cluster centroids. It represents a thoughtful middle ground between the simplicity of random undersampling and the complexity of ensemble-based imbalanced learning methods.

The technique works by fitting $K$ clusters to the majority class (where $K$ is typically the desired post-resampling count) and using the centroids as representative summary points. With soft voting, the centroids themselves become the new samples; with hard voting, the nearest original samples to each centroid are selected instead. This distinction matters for distance-based classifiers and regulatory compliance.

Key Takeaways

• Cluster Centroids preserves the global structure of the majority class distribution, unlike random undersampling which is structurally blind. This makes it particularly effective when the majority class has multimodal distributions with distinct subclusters.

• The computational cost ($O(N \cdot K \cdot d \cdot T)$) is the primary practical limitation. For large datasets, MiniBatchKMeans is essentially mandatory, providing 5-10x speedup.

• Feature scaling is non-negotiable -- K-Means uses Euclidean distance, so unscaled features will produce biased centroids. Always apply StandardScaler before ClusterCentroids in the pipeline.

• The most dangerous failure mode is centroid drift near the decision boundary. When majority class clusters span the boundary region, centroids are pulled toward the minority class, increasing overlap and hurting precision.

• For production systems, start with sampling_strategy=0.3 (3:1 ratio) rather than full 1:1 balancing, and use imblearn.pipeline.Pipeline to ensure resampling happens correctly inside cross-validation. At Indian fintech companies handling fraud detection (Razorpay, PhonePe, Paytm), this technique is part of the standard resampling toolkit alongside SMOTE and class weights.