Multiclass Classification via Class-Weighted Nearest Neighbors
  We study statistical properties of the k-nearest neighbors algorithm for
multiclass classification, with a focus on settings where the number of classes
may be large and/or classes may be highly imbalanced. In particular, we
consider a variant of the k-nearest neighbor classifier with non-uniform
class-weightings, for which we derive upper and minimax lower bounds on
accuracy, class-weighted risk, and uniform error. Additionally, we show that
uniform error bounds lead to bounds on the difference between empirical
confusion matrix quantities and their population counterparts across a set of
weights. As a result, we may adjust the class weights to optimize
classification metrics such as F1 score or Matthew's Correlation Coefficient
that are commonly used in practice, particularly in settings with imbalanced
classes. We additionally provide a simple example to instantiate our bounds and
numerical experiments.
