Imbalance and Concentration in k-NN Classification

We propose algorithms for ameliorating difficulties in fast approximate k Nearest Neighbors (kNN) classifiers that arise from imbalances among classes in numbers of samples, and from concentrations of samples in small regions of feature space. These problems can occur with a wide range of binning kNN algorithms such as k-D trees and our variant, hashed k-D trees. The principal method we discuss automatically rebalances training data and estimates concentration in each K-d hash bin separately, which then controls how many samples should be kept in each bin. We report an experiment on 86.7M training samples which shows a 7-times speedup and higher minimum per-class recall, compared to previously reported methods. The context of these experiments is the need for image classifiers able to handle an unbounded variety of inputs: in our case, highly versatile document classifiers which require training sets as large as a billion training samples.