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.
Code (1)
Tasks
ClassificationGeneral ClassificationSimilar Papers 제목 키워드 기반
k*-Nearest Neighbors: From Global to Local
The weighted k-nearest neighbors algorithm is one of the most fundamental non-parametric methods in pattern recognition and machine learning. The question of setting the optimal number of neighbors as well as the optimal…
General ClassificationAn adaptive multiclass nearest neighbor classifier
We consider a problem of multiclass classification, where the training sample $S_n = \{(X_i, Y_i)\}_{i=1}^n$ is generated from the model $\mathbb P(Y = m | X = x) = \eta_m(x)$, $1 \leq m \leq M$, and $\eta_1(x), \dots, \…
Maximum Margin Multiclass Nearest Neighbors
We develop a general framework for margin-based multicategory classification in metric spaces. The basic work-horse is a margin-regularized version of the nearest-neighbor classifier. We prove generalization bounds that …
Generalization BoundsDistributionally Robust Weighted $k$-Nearest Neighbors
Learning a robust classifier from a few samples remains a key challenge in machine learning. A major thrust of research has been focused on developing $k$-nearest neighbor ($k$-NN) based algorithms combined with metric l…
Few-Shot LearningGeneral ClassificationMetric LearningInstance-based learning using the Half-Space Proximal Graph
The primary example of instance-based learning is the $k$-nearest neighbor rule (kNN), praised for its simplicity and the capacity to adapt to new unseen data and toss away old data. The main disadvantages often mentione…
ClassificationGeneral Classification