Imbalance and Concentration in k-NN Classification
Lists
Only you see this
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...