Random Undersampler in Machine Learning

The Computational Reality of Large Imbalanced Datasets

Class imbalance is pervasive in real-world ML. Credit card fraud represents 0.1-0.2% of transactions. Rare diseases affect 1 in 10,000 patients. Network intrusions are a fraction of a percent of all traffic. The immediate instinct is to oversample: generate more minority class data using SMOTE, ADASYN, or simple duplication.

But what happens when the majority class is enormous? Consider a payment processor like Razorpay or PhonePe handling 100 million transactions per month, with 100,000 fraudulent ones (0.1%). Applying SMOTE to balance to 1:1 would generate 99.9 million synthetic fraud samples, roughly doubling the dataset to 200 million records. Training time, memory consumption, and storage costs scale proportionally. For many organizations, this is simply not feasible.

Random undersampling solves this problem with brutal efficiency: instead of growing the dataset to 200 million, shrink it to 200,000 (100K fraud + 100K legitimate). Training time drops by 1000x. Memory requirements drop from terabytes to megabytes. The dataset fits in RAM on a single machine.

The History of Undersampling

Random undersampling predates most modern ML techniques. In the 1990s and early 2000s, when computational resources were far more limited, researchers frequently used undersampling because they simply couldn't afford to train on large imbalanced datasets. Kubat and Matwin's 1997 work on addressing the curse of imbalanced training sets was among the first to systematically study the tradeoffs.

The seminal 2004 paper by Drummond and Holte, "C4.5, Class Imbalance, and Cost Sensitivity: Why Under-Sampling beats Over-Sampling," challenged the assumption that oversampling was always superior. They showed that for certain classifiers (particularly decision trees), undersampling actually produced better ROC curves than oversampling, because the smaller training set reduced overfitting to the majority class.

From Naive to Ensemble: The Evolution

The information loss problem with naive random undersampling motivated a wave of research into smarter approaches. Liu, Wu, and Zhou's 2009 paper on Exploratory Undersampling introduced two landmark algorithms:

1. EasyEnsemble: Train multiple classifiers, each on a different randomly undersampled subset, and aggregate predictions. This way, every majority sample participates in at least one model.
2. BalanceCascade: Sequentially train classifiers and remove correctly classified majority samples at each stage, progressively focusing on harder examples.

These ensemble-based approaches proved that random undersampling's simplicity could be leveraged as a strength rather than a weakness. By the 2010s, BalancedBaggingClassifier and EasyEnsembleClassifier had become standard tools in the imbalanced-learn library, offering the speed benefits of undersampling with significantly reduced information loss.

Key Insight: Random undersampling isn't just a fallback for when oversampling is too expensive. In many real-world scenarios -- especially with large, redundant majority classes -- it performs comparably to or better than oversampling, at a fraction of the computational cost.

The Library Analogy

Imagine you're running a library with 10,000 books on cooking and only 100 books on quantum physics. A student asks you to create a balanced reading list for both topics. You have two choices:

1. Oversampling approach: Photocopy the 100 quantum physics books 100 times each, giving you 10,000 copies. Your library now holds 20,000 books, takes twice as much shelf space, and you still have only 100 unique quantum physics titles.
2. Undersampling approach: Pick 100 cooking books from the 10,000 and put the rest in storage. Your library now has 200 books -- small, manageable, and balanced.

Random undersampling is the second approach. It's fast, it's simple, and the resulting collection is easy to work with. But here's the catch: what if those 9,900 cooking books you shelved included the only copy of a rare recipe for Indian biryani? You've lost information.

The Statistical Perspective

Here's a mental model that captures the core tradeoff. Think of the majority class as a probability distribution in feature space. With 10 million samples, you have an extremely dense representation of that distribution -- every nook and cranny is covered by data points. The minority class, with 10,000 samples, is sparse.

When you randomly undersample the majority to 10,000, you're sub-sampling from a dense distribution. If the majority class is relatively uniform (many similar examples), you lose very little by sampling. The 10,000 retained samples still capture the essential shape of the distribution.

But if the majority class has complex structure -- multiple subclusters, rare edge cases, or thin tails -- random sampling may miss important regions. This is why random undersampling works best when the majority class is large and somewhat redundant.

Why Information Loss Isn't Always Catastrophic

Practitioners often overestimate the information loss from undersampling. Consider a dataset of 10 million legitimate credit card transactions. Most of these transactions are routine: coffee purchases, grocery bills, recurring subscriptions. The information content per sample is low because the transactions are highly redundant.

Undersampling to 50,000 legitimate transactions still captures the core transaction patterns -- amounts, merchant categories, time-of-day distributions. You lose some rare transaction types (e.g., a one-time international wire transfer), but the model's understanding of "normal" remains robust.

The real danger occurs when the majority class has important but infrequent patterns that look similar to minority class patterns. In fraud detection, some legitimate transactions genuinely look fraudulent (high-value international purchases). If undersampling removes all examples of these borderline legitimate cases, the model will misclassify them as fraud.

Practical Wisdom: Random undersampling is least risky when the majority class is large and redundant, and most risky when the majority class has important rare subclusters near the decision boundary.

Mathematical Formulation

Let $D = \{(\mathbf{x}_i, y_i)\}_{i=1}^{n}$ be a binary classification training set where $y_i \in \{0, 1\}$, class 0 (majority) has $n_{\text{maj}}$ samples, and class 1 (minority) has $n_{\text{min}}$ samples, with imbalance ratio $IR = \frac{n_{\text{maj}}}{n_{\text{min}}} \gg 1$.

Random undersampling constructs a new dataset $D' \subset D$ by:

1. Retaining all minority class samples: $D_{\text{min}}' = D_{\text{min}} = \{(\mathbf{x}_i, y_i) : y_i = 1\}$

2. Randomly sampling $m$ majority class examples: $D_{\text{maj}}' \subset D_{\text{maj}}$, where $|D_{\text{maj}}'| = m$

3. Combining: $D' = D_{\text{min}}' \cup D_{\text{maj}}'$

The target count $m$ is determined by the sampling_strategy:

• 'auto' (default): $m = n_{\text{min}}$ (balance to 1:1)
• float $r \in (0, 1]$: $m = \frac{n_{\text{min}}}{r}$ (target minority/majority ratio = $r$)
• dict: $m$ specified explicitly per class

Sampling With and Without Replacement

Without replacement (default, replacement=False):

$P(\text{sample } \mathbf{x}_j) = \frac{1}{|D_{\text{maj}} \setminus S_j|}$

where $S_j$ is the set of already-selected samples. Each majority sample appears at most once in $D_{\text{maj}}'$. This requires $m \leq n_{\text{maj}}$ (always satisfied since we're reducing the majority class).

With replacement (replacement=True):

$P(\text{sample } \mathbf{x}_j) = \frac{1}{n_{\text{maj}}}$

for each draw. Samples may appear multiple times. This is useful for bootstrap-based ensemble methods like BalancedBaggingClassifier where each base learner sees a different bootstrapped undersampled subset.

Theoretical Properties

Expected coverage: With sampling without replacement, the fraction of the majority class retained is:

$\text{coverage} = \frac{m}{n_{\text{maj}}} = \frac{n_{\text{min}}}{n_{\text{maj}}} = \frac{1}{IR}$

For $IR = 100$ (1% minority), undersampling to 1:1 retains only 1% of majority samples. For $IR = 1000$, only 0.1% is retained.

Information loss bound: Under the assumption that majority class samples are i.i.d. from distribution $P_{\text{maj}}$, the empirical distribution of the undersampled majority class $\hat{P}_{m}$ converges to $P_{\text{maj}}$ at rate $O(1/\sqrt{m})$ by the Dvoretzky-Kiefer-Wolfowitz inequality:

$P\left(\sup_x |\hat{P}_m(x) - P_{\text{maj}}(x)| > \epsilon\right) \leq 2e^{-2m\epsilon^2}$

This means that as long as $m$ is sufficiently large (typically $m > 1000$), the undersampled majority class is a good approximation of the original distribution.

Algorithm Complexity

• Time: $O(m)$ for random selection without replacement (using Fisher-Yates shuffle or reservoir sampling)
• Space: $O(n_{\text{min}} + m)$ for the output dataset
• Comparison: SMOTE requires $O(n_{\text{min}}^2 \cdot d)$ for k-NN search; random undersampling is orders of magnitude faster

Mathematical Caveat: The convergence guarantee assumes i.i.d. samples. If the majority class has temporal dependencies (e.g., time-series data) or spatial correlations, random sampling may systematically miss certain regions of the distribution, and stratified undersampling should be used instead.

Random undersampling is the simplest and fastest technique for handling class imbalance in machine learning, operating by randomly removing majority class samples until the desired class ratio is achieved. With O(m) time complexity and no synthetic data generation, it reduces training sets by orders of magnitude -- a 10-million-row dataset can be compressed to 20,000 rows in under a second, enabling rapid model development and cost-effective production retraining.

The technique's fundamental challenge is information loss: discarding majority class samples risks losing important patterns, especially rare subclusters or boundary-defining examples. However, for very large and redundant majority classes -- common in fraud detection, transaction classification, and large-scale recommendation systems -- the information loss is often negligible because the retained samples adequately represent the majority class distribution. Partial undersampling (targeting 1:5 or 1:10 ratios instead of 1:1) offers a practical middle ground that preserves more majority class diversity while still addressing the imbalance.

The evolution from naive random undersampling to ensemble-based approaches (EasyEnsembleClassifier, BalancedBaggingClassifier) represents a significant advancement. These methods train multiple base learners on different randomly undersampled subsets, collectively covering the full majority class through ensemble diversity. EasyEnsemble with 10 base learners typically recovers 90-95% of the information lost by naive undersampling while maintaining 5-20x training speed advantage over oversampling methods like SMOTE.

In production ML systems -- from fraud detection at financial institutions to churn prediction at telecom providers to defect detection in manufacturing -- random undersampling and its ensemble variants remain essential tools. They are particularly valuable when computational budgets are constrained, retraining frequency is high, or the majority class is so large that oversampling is simply not feasible. Understanding the tradeoff space -- when undersampling's speed advantage outweighs its information loss, and when to upgrade from naive to ensemble approaches -- is a critical skill for ML engineers building production systems at scale.