Looking for an efficient algorithm to detect Tomek links

Question

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!

Answer 1

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.