One-Sided Selection

OSS operates in a sequential two-stage process. Phase 1 identifies and removes majority class instances that form Tomek Links—pairs of minimally distanced nearest neighbors of opposite classes. This cleans the class boundary overlap. Phase 2 applies Condensed Nearest Neighbors (CNN) to the cleaned dataset, retaining only those majority class examples that are essential for correct classification via a 1-NN rule. This eliminates redundant interior points far from the decision boundary.

A Tomek Link exists between two examples x and y of opposite classes if no other example z is closer to either x or y. In OSS, only the majority class instance in each Tomek Link pair is removed. This step specifically targets ambiguous, overlapping regions where the classes are inseparable, sharpening the decision boundary without discarding minority class information. The result is a cleaner separation surface for subsequent learning.

After Tomek Link cleaning, CNN builds a consistent subset of the training data. Starting with all minority examples and one majority example, it iteratively adds only those majority instances that are misclassified by a 1-Nearest Neighbor classifier trained on the current subset. The final set—the 'condensed' set—contains only the majority examples that define the classification boundary. All internal, redundant majority points are discarded.

OSS has a time complexity of O(n²) in the worst case, driven by the pairwise distance calculations required for both Tomek Link identification and the iterative 1-NN evaluations in CNN. For large-scale financial transaction datasets with millions of records, this quadratic scaling can become prohibitive. Practical implementations often use optimized spatial indexing structures like KD-Trees or approximate nearest neighbor methods to reduce runtime.

Unlike SMOTETomek or SMOTEENN, which combine over-sampling with cleaning, OSS is a pure under-sampling technique. It never generates synthetic data. This makes OSS preferable when:

• The minority class is already sufficiently represented
• Synthetic data generation is undesirable due to regulatory constraints
• Model interpretability must be preserved without artificial feature space interpolation However, OSS may discard more useful majority class information than ensemble methods like EasyEnsemble.

By removing both boundary noise and redundant interior points, OSS creates a training set that is both cleaner and smaller. This typically leads to:

• Faster training times due to reduced dataset size
• Improved recall on the minority class as the decision boundary is clarified
• Potential reduction in precision if too many majority examples are removed OSS works best when combined with cost-sensitive classifiers that can further compensate for any remaining imbalance after under-sampling.

A data cleaning method that identifies pairs of minimally distanced nearest neighbors of opposite classes. By removing the majority class instance in each pair, Tomek Links clarifies the decision boundary between overlapping classes. This is the first step in the One-Sided Selection algorithm, used to eliminate borderline and noisy majority examples before applying Condensed Nearest Neighbors.

An under-sampling technique that aims to find a minimal consistent subset of the training data. It iteratively adds only those majority class examples that are misclassified by the current subset, effectively removing instances far from the decision boundary. In One-Sided Selection, CNN is applied after Tomek Links to eliminate redundant majority samples, reducing dataset size without sacrificing discriminatory information.

An under-sampling technique that removes any majority class example whose predicted class differs from its actual class based on its k-nearest neighbors. ENN acts as a noise filter, eliminating ambiguous instances. While One-Sided Selection uses Tomek Links for boundary cleaning, ENN is often paired with SMOTE in the SMOTEENN hybrid method to clean both classes after synthetic oversampling.

A two-step under-sampling algorithm that first uses Edited Nearest Neighbors to remove majority class examples, then removes minority class examples that are misclassified by three nearest neighbors. Unlike One-Sided Selection which focuses solely on reducing the majority class, NCL cleans both classes, prioritizing the removal of overlapping and noisy instances from the minority side as well.

A combined resampling technique that first applies SMOTE to generate synthetic minority samples, then removes overlapping majority class instances using Tomek Links. This creates a cleaner class separation than SMOTE alone. While One-Sided Selection is a pure under-sampling strategy, SMOTETomek is a hybrid approach that both increases minority representation and clarifies the decision boundary.

A family of under-sampling algorithms that selects majority class examples based on their average distance to the nearest minority class instances. NearMiss-1 keeps majority samples with the smallest average distance to three closest minority samples, preserving those near the decision boundary. This contrasts with One-Sided Selection, which uses consistency rather than distance heuristics to select retained instances.