The Neighborhood Cleaning Rule is a two-step data cleaning algorithm designed to improve the quality of training data for imbalanced classification. It first applies Edited Nearest Neighbors (ENN) to the majority class, removing any majority instance whose class label differs from the majority vote of its three nearest neighbors. This step eliminates majority class examples that overlap with or intrude into the minority class space.
Glossary
Neighborhood Cleaning Rule
The Neighborhood Cleaning Rule (NCR) is an under-sampling algorithm that uses Edited Nearest Neighbors to remove noisy majority class examples and then eliminates minority class examples misclassified by three nearest neighbors, cleaning both classes.
DATA CLEANING FOR IMBALANCED CLASSIFICATION
What is the Neighborhood Cleaning Rule?
The Neighborhood Cleaning Rule (NCL) is a combined under-sampling algorithm that cleans both the majority and minority classes by removing noisy and ambiguous examples to create sharper, more separable class boundaries for imbalanced datasets.
In the second step, the algorithm targets the minority class. For each minority class example, the algorithm finds its three nearest neighbors. If those three neighbors misclassify the minority instance—meaning all three neighbors belong to the majority class—that minority example is considered noise and is removed. This dual-cleaning process sharpens the decision boundary, improving the signal quality for downstream classifiers like XGBoost or LightGBM.
UNDERSTANDING THE ALGORITHM
Key Characteristics of NCR
The Neighborhood Cleaning Rule is a sophisticated two-phase data cleaning algorithm that addresses class imbalance by removing noise and ambiguity from both the majority and minority classes, resulting in a cleaner, more separable decision boundary.
01
Two-Phase Cleaning Architecture
NCR operates in two distinct phases. Phase 1 applies Edited Nearest Neighbors (ENN) to the majority class, removing any majority instance whose class label differs from the prediction of its three nearest neighbors. Phase 2 targets the minority class, identifying and removing any minority instance that is misclassified by its three nearest neighbors. This dual-pass approach ensures both classes are cleaned of noisy and ambiguous examples.
02
ENN-Based Majority Undersampling
The first phase leverages the ENN rule with k=3 to identify majority class instances that are likely noisy or located deep within minority class territory. Key behaviors:
- Removes majority examples that disagree with their local neighborhood
- Eliminates redundant majority instances far from the decision boundary
- Preserves majority examples that form a clean class boundary
- More aggressive than Tomek Links, removing more majority instances
03
Minority Class Noise Removal
Unlike standard under-sampling methods that only target the majority class, NCR's second phase cleans the minority class by removing instances that are likely mislabeled or outliers. A minority example is removed if all three of its nearest neighbors classify it as majority. This prevents the model from learning from erroneous minority examples that could distort the decision boundary.
04
Comparison with One-Sided Selection
While both NCR and One-Sided Selection (OSS) clean the majority class, NCR goes further by also cleaning the minority class. Key differences:
- OSS uses Condensed Nearest Neighbors to remove redundant majority examples; NCR uses ENN
- OSS does not touch the minority class; NCR actively removes noisy minority instances
- NCR typically produces a cleaner but smaller dataset than OSS
- NCR is preferred when minority class label noise is suspected
05
Integration in Hybrid Resampling Pipelines
NCR is frequently used as a data cleaning step within hybrid resampling strategies. A common pipeline:
- Apply SMOTE to generate synthetic minority examples
- Apply NCR to clean both the original and synthetic data
- Train the classifier on the cleaned, balanced dataset This combination, known as SMOTE+NCR, addresses both class imbalance and class overlap simultaneously.
06
Impact on Decision Boundary Clarity
By removing overlapping and noisy examples from both classes, NCR creates a cleaner separation between the majority and minority regions in feature space. Benefits include:
- Reduced classifier confusion near the boundary
- Improved precision for minority class predictions
- More stable decision boundaries across different classifiers
- Particularly effective for k-NN and SVM classifiers that are sensitive to local data geometry
ALGORITHM COMPARISON
NCR vs. Related Under-Sampling Techniques
How the Neighborhood Cleaning Rule differs from other data cleaning and under-sampling methods in its approach to handling class imbalance.
| Feature | NCR | Edited Nearest Neighbors | Tomek Links |
|---|---|---|---|
Cleans majority class | |||
Cleans minority class | |||
Removal criterion | 3-NN misclassification | k-NN label disagreement | Minimal distance pair |
Handles class overlap | |||
Removes noisy minority examples | |||
Preserves safe minority examples | |||
Typical reduction ratio | 15-30% | 10-25% | 5-15% |
Computational complexity | O(n²) | O(k·n²) | O(n²) |
DATA CLEANING & HYBRID RESAMPLING
Frequently Asked Questions
Explore the mechanics of the Neighborhood Cleaning Rule, a sophisticated under-sampling algorithm that combines Edited Nearest Neighbors with a targeted minority class cleaning step to produce high-quality, balanced datasets for robust fraud detection model training.
The Neighborhood Cleaning Rule (NCR) is a two-step under-sampling algorithm designed to clean both the majority and minority classes in imbalanced datasets. It operates by first applying the Edited Nearest Neighbors (ENN) rule to the majority class: any majority class example whose predicted class label differs from its actual label based on its three nearest neighbors is removed. This step eliminates noisy or ambiguous majority instances that overlap with the minority class space. In the second step, the algorithm targets the minority class: for each remaining minority class example, if it is misclassified by its three nearest neighbors, it is removed. This dual-cleaning process ensures that only high-quality, representative examples from both classes are retained, sharpening the decision boundary and improving the signal-to-noise ratio for downstream classifiers like XGBoost or LightGBM.
Enabling Efficiency, Speed & Accuracy
Intelligent Analysis, Decision & Execution
We build AI systems for teams that need search across company data, workflow automation across tools, or AI features inside products and internal software.
Talk to Us
Search across company data
Give teams answers from docs, tickets, runbooks, and product data with sources and permissions.
Useful when people spend too long searching or get different answers from different systems.
Enterprise searchRAGPermissions
Read more
Automate internal workflows
Use AI to route work, draft outputs, trigger actions, and keep approvals and logs in place.
Useful when repetitive work moves across multiple tools and teams.
AI agentsWorkflow automationGovernance
Read more
Add AI to products and internal tools
Build assistants, guided actions, or decision support into the software your team or customers already use.
Useful when AI needs to be part of the product, not a separate tool.
AI integrationDecision supportModel routing
Read more
About the author
Prasad Kumkar
CEO & MD, Inference Systems
Prasad Kumkar is the CEO & MD of Inference Systems and writes about AI systems architecture, LLM infrastructure, model serving, evaluation, and production deployment. Over 5+ years, he has worked across computer vision models, L5 autonomous vehicle systems, and LLM research, with a focus on taking complex AI ideas into real-world engineering systems.
His work and writing cover AI systems, large language models, AI agents, multimodal systems, autonomous systems, inference optimization, RAG, evaluation, and production AI engineering.
LinkedIn
Limited slotsGet a Free AI Consultation
Partnered with leading AI, data, and software stack.
How We Work
Custom AI workflows for your Business
One-fit-all AI don't work for modern businesses. At Inferensys, we aim to understand your business & custom requirements; which we use to define most efficient agentic workflows, the data, and the tools for your business.
01
Review the use case
We understand the task, the users, and where AI can actually help.
Read more02
Pick the right approach
We define what needs search, automation, or product integration.
Read more03
Build the first useful version
We implement the part that proves the value first.
Read more04
Improve from there
We add the checks and visibility needed to keep it useful.
Read moreThe first call is a practical review of your use case and the right next step.
Talk to Us