  In this paper, we address the challenging problem of learning from imbalanced
data using a Nearest-Neighbor (NN) algorithm. In this setting, the minority
examples typically belong to the class of interest requiring the optimization
of specific criteria, like the F-Measure. Based on simple geometrical ideas, we
introduce an algorithm that reweights the distance between a query sample and
any positive training example. This leads to a modification of the Voronoi
regions and thus of the decision boundaries of the NN algorithm. We provide a
theoretical justification about the weighting scheme needed to reduce the False
Negative rate while controlling the number of False Positives. We perform an
extensive experimental study on many public imbalanced datasets, but also on
large scale non public data from the French Ministry of Economy and Finance on
a tax fraud detection task, showing that our method is very effective and,
interestingly, yields the best performance when combined with state of the art
sampling methods.

Machine Learning;Machine Learning