Tomek Links

A Tomek Link is defined as a pair of instances (x, y) from opposite classes where no other instance z exists such that the distance d(x, z) < d(x, y) or d(y, z) < d(y, x). In simpler terms, two instances from different classes are each other's nearest neighbor. The core mechanism involves identifying all such pairs and systematically removing the majority class instance from each link. This process directly eliminates overlapping or ambiguous data points that sit exactly on or within the wrong side of the decision boundary, reducing noise and creating a cleaner, more separable class margin for subsequent classifiers.

The algorithm relies on computing a pairwise distance matrix, typically using Euclidean distance for continuous features, though other metrics like Manhattan or Mahalanobis distance can be applied. For each instance, its nearest neighbor is identified. A Tomek Link is formed if and only if two instances are mutual nearest neighbors and belong to different classes. The computational complexity is O(n²) for a naive implementation, making it expensive for very large datasets. Efficient implementations often use k-d trees or ball trees to accelerate the nearest neighbor search, reducing the average complexity to O(n log n).

By removing majority class instances that intrude into the minority class space, Tomek Links effectively prune the decision boundary. This has two primary effects:

• Noise Reduction: Eliminates borderline and ambiguous majority examples that cause overfitting.
• Margin Maximization: Creates a clearer separation zone between classes, which is particularly beneficial for margin-based classifiers like Support Vector Machines (SVMs). The result is not a balanced dataset but a cleaner one. The class distribution remains imbalanced, but the overlap between classes is significantly reduced, allowing the classifier to learn a more generalizable boundary.

Tomek Links are rarely used in isolation for imbalanced classification. Their most common application is as the second step in the SMOTETomek hybrid pipeline. This combined method first applies SMOTE to oversample the minority class, creating synthetic examples. However, SMOTE can inadvertently create samples that invade the majority class space, introducing new noise. Applying Tomek Links after SMOTE cleans up this noise by removing the overlapping majority class instances that now sit too close to the new synthetic minority points. This two-step process creates a balanced and well-separated dataset.

Despite its utility, Tomek Links has key limitations:

• Computational Cost: The O(n²) pairwise distance calculation is prohibitive for datasets with millions of transactions.
• Information Loss: Removing majority class instances can discard valuable information, especially if the overlapping region is large and represents a genuine area of class ambiguity rather than noise.
• No Minority Handling: It only removes majority class samples. Noisy minority class examples that sit deep within the majority space are untouched, potentially acting as outliers that distort the boundary.
• Metric Sensitivity: The definition of a 'link' is highly sensitive to the chosen distance metric and the scale of features, making feature normalization a critical prerequisite.

While both are under-sampling methods that clean the majority class, they operate on different principles:

• Tomek Links: Removes only the majority instance from a pair of mutual nearest neighbors of opposite classes. It focuses on the exact boundary line.
• Edited Nearest Neighbors (ENN): Removes any majority instance whose predicted class (based on a k-nearest neighbor vote) differs from its actual class. It cleans a wider region around the boundary. ENN is generally more aggressive in removing majority samples, while Tomek Links is more conservative, only eliminating the most ambiguous, directly opposed pairs. They are often combined in the One-Sided Selection algorithm.