Imbalance and Concentration in k-NN Classification

Dawei Yin, Chang An, Henry S. Baird

Abstract

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.
BibTeX
@inproceedings{yin2010imbalance,
  author = {Dawei Yin and Chang An and Henry S. Baird},
  title = {{Imbalance and Concentration in k-NN Classification}},
  booktitle = {ICPR},
  year = {2010},
  doi = {10.1109/icpr.2010.531},
}

Loading related content...

Figure