Edited Nearest Neighbors in Machine Learning

The Noise Problem in Classification

Let's start with a fundamental truth about real-world datasets: labels are imperfect. Whether the labeling was done by humans (who make mistakes), by heuristic rules (which have edge cases), or by upstream models (which have their own error rates), every dataset contains some percentage of mislabeled or ambiguous samples.

These noisy samples are not uniformly distributed. They tend to concentrate near the decision boundary between classes -- the region where samples are genuinely hard to classify. A fraudulent transaction that looks nearly identical to a legitimate one. A benign tumor with imaging features that mimic malignancy. A customer who churned but whose behavior patterns match loyal users.

When these noisy boundary samples are fed to a classifier, they blur the learned decision boundary, reducing both precision and recall. The model wastes capacity trying to accommodate conflicting signals in the boundary region.

Wilson's Insight (1972)

In 1972, Dennis Wilson published a deceptively simple idea in IEEE Transactions on Systems, Man, and Cybernetics. The paper, "Asymptotic Properties of Nearest Neighbor Rules Using Edited Data," proposed what we now call the Edited Nearest Neighbor (ENN) rule.

The core insight: use a k-NN classifier as a data quality filter. For each sample in the dataset, ask its k nearest neighbors to "vote" on its class label. If the vote disagrees with the sample's actual label, the sample is likely noise and should be removed.

Wilson proved that a 1-NN classifier trained on the edited (cleaned) data achieves asymptotically Bayes-optimal error rates -- meaning that as the dataset grows, the 1-NN rule on edited data converges to the best possible error rate for any classifier. This was a landmark theoretical result that gave ENN strong mathematical backing.

From Theory to Imbalanced Learning

Wilson's original formulation was about general data cleaning, not specifically about class imbalance. But in the 1990s and 2000s, as the ML community grappled with the class imbalance problem, researchers recognized that ENN had a natural affinity for it.

Why? Because in imbalanced datasets, the majority class samples near the boundary are the primary source of false negatives. They crowd the decision boundary and cause the classifier to "lean" toward the majority class. ENN preferentially removes these boundary samples, effectively clearing space for the minority class.

Batista, Prati, and Monard (2004) formalized this connection in their influential ACM SIGKDD paper, proposing the SMOTE+ENN combination: first oversample the minority class with SMOTE, then clean the resulting dataset with ENN to remove both original noise and any poorly-placed synthetic samples. This combination -- now called SMOTEENN in imbalanced-learn -- became one of the most widely-used hybrid resampling methods.

Key Takeaway: ENN exists because classification datasets contain noise that concentrates near decision boundaries. By using k-NN voting as a data quality filter, ENN removes exactly the samples that hurt classifier performance the most. Its simplicity and theoretical guarantees have kept it relevant for over 50 years.

The Neighborhood Vote Analogy

Imagine you're verifying voter registrations for an election. Each voter claims to belong to a particular district, but some registrations might be erroneous -- people registered in the wrong district due to clerical errors, address mix-ups, or fraud.

How do you check? You look at each voter's actual neighbors -- the people living closest to them. If a voter claims to be in District A but all their nearest neighbors are in District B, that registration is probably wrong. You'd flag it for removal.

That's exactly what ENN does with data points. Each sample "claims" a class label. ENN checks whether the sample's nearest neighbors agree with that claim. If they don't, the sample gets removed.

Why Boundary Noise Matters Most

Here's the mental model that really clarifies ENN's value. Picture a 2D feature space with blue dots (majority class) and red dots (minority class). Most blue dots are far from the red cluster, and most red dots are deep inside their own territory. But near the boundary, things get messy: some blue dots are surrounded by red dots, and vice versa.

These boundary mislabels are the samples that cause the most damage to classifier performance. A blue dot deep in blue territory doesn't affect the decision boundary at all -- the model already knows that region is blue. But a blue dot sitting in the middle of red territory pulls the decision boundary toward it, creating a dent in the classifier's understanding of the red region.

ENN specifically targets these boundary mislabels. Samples deep in their own class territory will have neighbors of the same class and survive the edit. Samples near the boundary with disagreeing neighbors get removed. It's surgical noise removal.

The 'mode' vs 'all' Strategies

ENN offers two cleaning strategies, and the distinction is important:

mode (conservative): A sample is removed only if the majority of its k neighbors disagree with its label. If you have k=3 and two neighbors agree with the sample but one disagrees, the sample stays. This preserves more data but is gentler on noise removal.

all (aggressive): A sample is removed if any of its k neighbors disagree with its label. With k=3, even one dissenting neighbor triggers removal. This is more aggressive and removes more samples, creating cleaner but smaller datasets.

Think of it as a jury system: 'mode' requires a majority verdict to convict (remove), while 'all' requires unanimous agreement for acquittal (retention). In practice, 'all' is the default in imbalanced-learn because it provides more thorough cleaning.

Expert Insight: ENN is not really an undersampling method in the traditional sense -- it's a data cleaning method that happens to reduce dataset size. The distinction matters because ENN doesn't target a specific class ratio. It removes noise wherever it finds it, which in imbalanced datasets tends to disproportionately affect the majority class near the boundary.

Mathematical Formulation

Let $D = \{(\mathbf{x}_i, y_i)\}_{i=1}^{n}$ be a labeled dataset where $\mathbf{x}_i \in \mathbb{R}^d$ and $y_i \in \{1, 2, \ldots, C\}$ for $C$ classes.

Step 1: Neighbor Computation

For each sample $(\mathbf{x}_i, y_i)$, find its $k$ nearest neighbors using a distance function $d(\cdot, \cdot)$:

$N_k(\mathbf{x}_i) = \{\mathbf{x}_{j_1}, \mathbf{x}_{j_2}, \ldots, \mathbf{x}_{j_k}\} \subset D \setminus \{\mathbf{x}_i\}$

ordered by $d(\mathbf{x}_i, \mathbf{x}_{j_1}) \leq d(\mathbf{x}_i, \mathbf{x}_{j_2}) \leq \cdots \leq d(\mathbf{x}_i, \mathbf{x}_{j_k})$

Step 2: Classification by Neighbors

Let $\hat{y}_i^{\text{kNN}}$ denote the class predicted by a $k$-NN classifier for $\mathbf{x}_i$, based on the labels of $N_k(\mathbf{x}_i)$.

For kind_sel='mode': $\hat{y}_i^{\text{kNN}} = \text{mode}(\{y_{j_1}, y_{j_2}, \ldots, y_{j_k}\})$

For kind_sel='all': Sample $\mathbf{x}_i$ is flagged for removal if $\exists\; j \in N_k(\mathbf{x}_i)$ such that $y_j \neq y_i$

Step 3: Editing Rule

$D_{\text{edited}} = \begin{cases} D \setminus \{(\mathbf{x}_i, y_i) : \hat{y}_i^{\text{kNN}} \neq y_i\} & \text{if kind\_sel='mode'} \\ D \setminus \{(\mathbf{x}_i, y_i) : \exists\; j \in N_k(\mathbf{x}_i),\; y_j \neq y_i\} & \text{if kind\_sel='all'} \end{cases}$

Asymptotic Properties (Wilson 1972)

Wilson proved that the 1-NN rule applied to $D_{\text{edited}}$ achieves the Bayes error rate asymptotically:

$\lim_{n \to \infty} P(\text{error} \mid D_{\text{edited}}) = R^* \leq R_{\text{1-NN}}$

where $R^*$ is the Bayes optimal error rate and $R_{\text{1-NN}}$ is the error rate of the unedited 1-NN rule, which is bounded by $R^* \leq R_{\text{1-NN}} \leq 2R^*(1 - R^*)$.

Computational Complexity

• k-NN search: $O(n^2 \cdot d)$ for brute force, $O(n \cdot d \cdot \log n)$ with KD-tree/Ball tree
• Editing pass: $O(n \cdot k)$ for the comparison step
• Overall: Dominated by neighbor search, typically $O(n^2 \cdot d)$ for moderate $n$

For large datasets ($n > 100{,}000$), the $O(n^2)$ brute-force neighbor search becomes the bottleneck. Approximate nearest neighbor methods or dimensionality reduction can mitigate this.

Repeated Edited Nearest Neighbors (RENN)

RENN applies the ENN editing rule iteratively until no more samples are removed:

$D^{(t+1)} = \text{ENN}(D^{(t)}), \quad \text{until } D^{(t+1)} = D^{(t)}$

RENN converges to a class-wise convex hull approximation, producing maximally clean decision regions. The number of iterations is typically 2-5 for real datasets.

Important Note: Wilson's theoretical guarantees assume infinite data and noise-free labels for the correctly-classified samples. In finite samples, ENN can occasionally remove genuine (correctly labeled) samples near the boundary, so the choice of $k$ and kind_sel involves a bias-variance tradeoff.

Edited Nearest Neighbors (ENN) is a foundational data cleaning algorithm that removes noisy samples from classification datasets by leveraging k-nearest neighbor voting. Proposed by Dennis Wilson in 1972, the algorithm's core principle is elegant: if a sample's neighbors disagree with its label, that sample is likely noise and should be removed. Wilson's proof that this editing rule produces asymptotically Bayes-optimal classification provided a theoretical foundation that has kept ENN relevant for over five decades.

In modern ML systems, ENN serves two primary roles. First, as a standalone undersampling technique that cleans majority class noise near decision boundaries in imbalanced datasets. Second -- and more commonly -- as the cleaning step in the SMOTEENN hybrid method, where SMOTE first generates synthetic minority samples and ENN then removes any noisy or poorly-placed samples from the combined dataset. The kind_sel parameter offers two strategies: 'all' (aggressive, any disagreeing neighbor triggers removal) and 'mode' (conservative, majority must disagree). The default 'all' strategy with k=3 works well for most datasets.

For production ML pipelines -- whether it's fraud detection at Razorpay, medical diagnosis systems, or recommendation engines at Flipkart -- ENN provides a computationally tractable way to improve training data quality without the risks of synthetic data generation. The key implementation requirements are: apply ENN after the train-test split to prevent data leakage, start with default parameters (k=3, kind_sel='all') and adjust based on the percentage of samples removed, and always validate the downstream model performance change. ENN's main limitation is its $O(n^2)$ computational cost for the k-NN search, which becomes impractical beyond a few million samples without approximate neighbor methods.