NearMiss in Machine Learning

The Information Overload Problem

In heavily imbalanced datasets, the majority class doesn't just outnumber the minority — it overwhelms the learning algorithm. A fraud detector trained on 999,000 legitimate transactions and 1,000 fraudulent ones learns the majority distribution extremely well while treating the minority class as statistical noise. Standard algorithms optimize for overall accuracy, which means predicting "legitimate" for everything yields 99.9% accuracy — and zero fraud detection.

Why Not Just Oversample the Minority?

Oversampling techniques like SMOTE generate synthetic minority samples to balance the dataset. This preserves all original data but has downsides: it increases training set size (sometimes dramatically), extends training time, and can amplify noise if minority samples are mislabeled or unrepresentative. For very large majority classes (millions of samples), doubling the dataset via oversampling is computationally wasteful.

Undersampling takes the opposite approach: instead of inflating the minority, shrink the majority. The result is a smaller, balanced dataset that trains faster and forces the classifier to focus on the decision boundary rather than memorizing the majority class distribution.

The Problem with Random Undersampling

The simplest undersampling approach is random: just discard majority class samples uniformly at random until the classes are balanced. This is fast and easy, but it has a critical flaw — it treats all majority samples as equally expendable. A majority sample deep in the interior of the majority class cluster carries the same deletion probability as one sitting right on the decision boundary. Random undersampling can easily discard the informative boundary samples while keeping redundant interior ones.

The NearMiss Innovation (2003)

Mani and Zhang proposed a smarter approach: use distance to the minority class as the selection criterion. Their key insight was that majority samples near the minority class are more informative for learning the decision boundary than those far away. By keeping majority samples that are close to minority instances, NearMiss preserves the "hard" classification examples — the ones where the model needs to make fine-grained distinctions.

They formalized this into three variants:

• NearMiss-1: Keep majority samples with the smallest average distance to their k nearest minority neighbors. This selects majority samples that are generally close to the minority class.
• NearMiss-2: Keep majority samples with the smallest average distance to their k farthest minority neighbors. This selects majority samples that are near the core of the minority class distribution.
• NearMiss-3: A two-step approach that first identifies minority neighbors, then selects majority samples with the largest average distance to their k nearest neighbors among those pre-selected. This avoids selecting majority samples that are too close (potential noise).

Why NearMiss Became Standard

Several factors drove adoption:

Computational efficiency: Unlike oversampling, NearMiss produces a smaller dataset, leading to faster training times. For datasets with millions of majority samples, this translates to significant cost savings (training a model on 100K samples instead of 1M can save hours of GPU time, translating to ₹5,000-50,000 or $60-600 per training run on cloud infrastructure).

Library support: The imbalanced-learn library provides a clean, scikit-learn-compatible implementation with all three variants accessible via a single version parameter.

Theoretical grounding: NearMiss has clear geometric intuition — it selects majority samples near the class boundary, which is where classification decisions are actually made.

Historical Note: The original paper by Mani and Zhang (2003) was presented at the ICML Workshop on Learning from Imbalanced Data Sets. It introduced NearMiss alongside Condensed Nearest Neighbor (CNN) and other prototype selection methods, establishing the foundation for heuristic undersampling that persists in modern ML practice.

The Core Idea in Plain English

Imagine you are a border patrol officer responsible for monitoring a long fence between two countries. You have 10,000 officers for Country A (majority) and only 100 for Country B (minority). Budget cuts mean you can only keep 100 officers from Country A. Which ones do you keep?

Random undersampling would randomly dismiss 9,900 officers — potentially leaving huge stretches of the border unmanned while clustering officers in interior cities far from the fence.

NearMiss says: keep the 100 officers from Country A who are stationed closest to the border fence. These are the ones who actually interact with the boundary, who see the most ambiguous cases, and whose presence is most informative for understanding where one territory ends and the other begins.

The Three Variants as Patrol Strategies

NearMiss-1 (closest to nearest minority neighbors): Keep majority officers whose average distance to the k closest Country B officers is smallest. This puts your retained officers right at the boundary, maximizing contact with the minority side.

NearMiss-2 (closest to farthest minority neighbors): Keep majority officers whose average distance to the k farthest Country B officers is smallest. This is subtler — it selects majority officers who are close even to distant minority outposts, meaning they sit near the center of the entire minority territory. Think of it as keeping officers who can "see" the full extent of Country B.

NearMiss-3 (safe margin preservation): First, find the k nearest majority officers for each minority officer. Then, from that pre-selected set, keep those with the largest average distance to their nearest minority neighbors. This avoids keeping officers who are uncomfortably close to the border (potential noise or overlap), instead selecting those at a comfortable distance — close enough to be informative, far enough to be reliable.

What NearMiss Does NOT Do

NearMiss does not generate new data. Unlike SMOTE, which creates synthetic samples, NearMiss only selects a subset of existing majority samples. This means:

1. Information loss is permanent — discarded majority samples are gone. If you needed them, you cannot recover the information.
2. The minority class is untouched — all minority samples remain in the dataset.
3. No interpolation artifacts — you never get "impossible" synthetic samples with nonsensical feature values.

The Coffee Shop Analogy

You run a coffee subscription service with 10,000 active customers and 200 who churned. You want to build a churn prediction model, but the 50:1 imbalance makes it hard.

With NearMiss-1, you keep the 200 active customers who are most similar to the churners — perhaps those with declining purchase frequency, lower spend per order, and shorter subscription tenure. These are the "almost-churners" who help the model learn the boundary between staying and leaving.

With random undersampling, you might accidentally keep 200 active customers who are super loyal, high-spending regulars — the easiest classification cases that teach the model nothing about churn.

Expert Insight: NearMiss-1 tends to be the most aggressive boundary selector, which can lead to noisy training sets if minority and majority classes overlap. NearMiss-3 is generally the safest choice for real-world applications because its two-step approach avoids selecting majority samples that are too close to minority instances (which might be noise or mislabeled points).

Mathematical Formulation

Let $D = \{(\mathbf{x}_i, y_i)\}_{i=1}^{n}$ be a binary classification dataset where $y_i \in \{0, 1\}$. Let $S_{\text{maj}} = \{\mathbf{x}_i : y_i = 0\}$ denote the majority class with $|S_{\text{maj}}| = n_{\text{maj}}$ and $S_{\text{min}} = \{\mathbf{x}_i : y_i = 1\}$ denote the minority class with $|S_{\text{min}}| = n_{\text{min}}$, where $n_{\text{maj}} \gg n_{\text{min}}$.

The goal is to select a subset $S' \subset S_{\text{maj}}$ with $|S'| = n_{\text{min}}$ (or a specified target count) such that the resulting balanced dataset $D' = S' \cup S_{\text{min}}$ is maximally informative for learning the decision boundary.

NearMiss-1

For each majority sample $\mathbf{x}_i \in S_{\text{maj}}$, compute the average distance to its $k$ nearest minority class neighbors:

$d_1(\mathbf{x}_i) = \frac{1}{k} \sum_{j=1}^{k} \|\mathbf{x}_i - \mathbf{x}_{(j)}^{\text{min}}\|$

where $\mathbf{x}_{(j)}^{\text{min}}$ is the $j$-th nearest neighbor of $\mathbf{x}_i$ in $S_{\text{min}}$, ordered by Euclidean distance. Select the $n_{\text{min}}$ majority samples with the smallest $d_1$ values:

$S'_1 = \underset{S' \subset S_{\text{maj}},\, |S'| = n_{\text{min}}}{\arg\min} \sum_{\mathbf{x}_i \in S'} d_1(\mathbf{x}_i)$

Interpretation: NearMiss-1 retains majority samples that are, on average, closest to the nearest minority samples. These are majority-class instances sitting right at the decision boundary.

NearMiss-2

For each majority sample $\mathbf{x}_i \in S_{\text{maj}}$, compute the average distance to its $k$ farthest minority class neighbors:

$d_2(\mathbf{x}_i) = \frac{1}{k} \sum_{j=n_{\text{min}}-k+1}^{n_{\text{min}}} \|\mathbf{x}_i - \mathbf{x}_{(j)}^{\text{min}}\|$

where $\mathbf{x}_{(j)}^{\text{min}}$ is the $j$-th nearest neighbor ordered by increasing distance. Select the $n_{\text{min}}$ majority samples with the smallest $d_2$ values:

$S'_2 = \underset{S' \subset S_{\text{maj}},\, |S'| = n_{\text{min}}}{\arg\min} \sum_{\mathbf{x}_i \in S'} d_2(\mathbf{x}_i)$

Interpretation: NearMiss-2 retains majority samples that are close even to the farthest minority samples. These are majority instances near the core of the minority class distribution, sitting in the overlap region.

NearMiss-3

This is a two-step algorithm:

Step 1: For each minority sample $\mathbf{x}_j \in S_{\text{min}}$, identify its $m$ nearest majority class neighbors. Let $C = \bigcup_{j=1}^{n_{\text{min}}} N_m^{\text{maj}}(\mathbf{x}_j)$ be the union of all such neighbors.

Step 2: For each candidate $\mathbf{x}_i \in C$, compute the average distance to its $k$ nearest minority class neighbors:

$d_3(\mathbf{x}_i) = \frac{1}{k} \sum_{j=1}^{k} \|\mathbf{x}_i - \mathbf{x}_{(j)}^{\text{min}}\|$

Select the $n_{\text{min}}$ candidates with the largest $d_3$ values:

$S'_3 = \underset{S' \subset C,\, |S'| = n_{\text{min}}}{\arg\max} \sum_{\mathbf{x}_i \in S'} d_3(\mathbf{x}_i)$

Interpretation: NearMiss-3 first constrains the candidate set to majority samples that are already near minority samples (Step 1), then picks those that are not too close (Step 2). This creates a "safe margin" that avoids selecting noisy or ambiguous boundary samples.

Algorithm Complexity

All three variants are dominated by the k-NN search:

• NearMiss-1 and NearMiss-2: $O(n_{\text{maj}} \cdot n_{\text{min}} \cdot d)$ for naive distance computation, where $d$ is feature dimensionality. With KD-trees: $O((n_{\text{maj}} + n_{\text{min}}) \cdot d \cdot \log n_{\text{min}})$.
• NearMiss-3: $O(n_{\text{min}} \cdot n_{\text{maj}} \cdot d)$ for Step 1, plus $O(|C| \cdot n_{\text{min}} \cdot d)$ for Step 2. In practice, $|C| \leq m \cdot n_{\text{min}}$, so total is $O(n_{\text{min}} \cdot n_{\text{maj}} \cdot d + m \cdot n_{\text{min}}^2 \cdot d)$.

For a dataset with $n_{\text{maj}} = 1{,}000{,}000$, $n_{\text{min}} = 10{,}000$, and $d = 50$, the naive NearMiss-1 computation involves $10^{10} \times 50 = 5 \times 10^{11}$ distance operations — substantial but tractable on modern hardware with optimized libraries.

Mathematical Note: The distance metric can be generalized beyond Euclidean. The imbalanced-learn implementation supports any metric compatible with scikit-learn's NearestNeighbors, including Manhattan ($L_1$), Minkowski ($L_p$), and cosine distance. Choice of metric significantly impacts which majority samples are selected, especially in high-dimensional spaces where Euclidean distance becomes less discriminative (the "curse of dimensionality").

NearMiss is a family of distance-based undersampling techniques that address class imbalance by intelligently selecting which majority class samples to retain based on their proximity to minority class instances. Introduced by Mani and Zhang in 2003, it offers three variants: NearMiss-1 (keep majority samples closest to nearest minority neighbors), NearMiss-2 (keep majority samples closest to farthest minority neighbors), and NearMiss-3 (a two-step approach that selects majority samples near the minority class but not too close, creating a safe margin). NearMiss-3 is generally recommended for production use due to its robustness to noise and label errors.

The technique's primary advantage is dramatic dataset reduction — on heavily imbalanced datasets, NearMiss can shrink the training set by 50-100x, cutting training time and compute costs proportionally. For Indian fintech companies processing millions of transactions, this can translate to savings of ₹15,000+ per month on training pipelines. Unlike oversampling methods like SMOTE, NearMiss produces no synthetic artifacts, preserves all minority samples, and generates smaller training sets that are faster to iterate with.

However, NearMiss comes with significant tradeoffs. The irreversible loss of majority class information can degrade precision and eliminate diverse majority patterns. NearMiss-1, in particular, can create noisy training sets by selecting the most ambiguous boundary samples. The k-NN distance computation adds preprocessing overhead that scales as O(n_maj * n_min * d), and in high-dimensional spaces, distance-based selection loses its advantage over random undersampling due to the curse of dimensionality.

Modern best practice treats NearMiss as one tool in a broader imbalance-handling toolkit. For tree-based models (XGBoost, Random Forest), native class weights often outperform NearMiss without the information loss. For SVMs and k-NN classifiers, NearMiss's boundary-focused selection provides genuine improvement. The most robust production approach is often hybrid: NearMiss for moderate majority reduction (1:100 to 1:10), SMOTE for moderate minority expansion (1:10 to 1:3), and class weights for the remaining imbalance. This balances information preservation, computational efficiency, and classification performance across domains from fraud detection to medical diagnosis to intrusion detection.