# Looking for an efficient algorithm to detect Tomek links

I'm looking for an efficient algorithm to detect Tomek links. I'm wondering if anyone knows where to find it.

This is the definition of Tomek links: Suppose $\{ E_1,\ldots,E_n\} \subset R^k$ is a dataset, with each $E_i$ having exactly one of two labels $+$ or $-$. A pair $(E_i,E_j)$ is called a Tomek link if $E_i$ and $E_j$ have different labels, and there is not an $E_l$ such that $d(E_i,E_l) < d(E_i,E_j)$ or $d(E_j,E_l) < d(E_i,E_j)$, where $d(x,y)$ is the distance between $x$ and $y$.

Thanks!

• could you please provide the definition of Tomek links ? I found one (citeseerx.ist.psu.edu/viewdoc/…), but I do not have access to the original source hence I was hesitating to modify the answer. Providing the definition can stimulate more answers, the name is somehow an obfuscation. – steffen Apr 29 '12 at 12:00
• Hi @steffen. Thanks for your suggestion. I added the definition. – user765195 Apr 30 '12 at 4:41

The problem of detecting Tomek links is the same as identifying any nearest neighbor (the class label does not help here, you have to check every data point no matter which label it has).

My personal preference is to go for kd-trees (as long as the dimension is not too high). The stackoverflow - question Nearest neighbors in high-dimensional data? provides more ideas.

If you can accept approximate answers (up to a controllable error rate) you can also have a look at approximate nearest neighbors search methods such as Locality Sensitive Hashing and more advanced methods implemented in the flann library.

The imbalanced-learn package provides many re-sampling techniques for working with imbalanced datasets: https://github.com/scikit-learn-contrib/imbalanced-learn

See this example for an implementation of the Tomek links re-sampling.