# Under-bagging Nearest Neighbors for Imbalanced Classification

arXiv: https://arxiv.org/abs/2109.00531 · HTML: https://mlsanity.com/paper/2109.00531/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 114 references that are in the map.
- First posted on arXiv 1 Sep 2021.

## Builds on (most cited first, 12 of 12)

- [Metrics for Multi-Class Classification: an Overview](https://mlsanity.com/paper/2008.05756/) (2020)
- [Macro F1 and Macro F1](https://mlsanity.com/paper/1911.03347/) (2019)
- [Rates of Convergence for Nearest Neighbor Classification](https://mlsanity.com/paper/1407.0067/) (2014)
- [Imbalance-XGBoost: Leveraging Weighted and Focal Losses for Binary Label-Imbalanced Classification with XGBoost](https://mlsanity.com/paper/1908.01672/) (2019)
- [A Cost-Sensitive Deep Belief Network for Imbalanced Classification](https://mlsanity.com/paper/1804.10801/) (2018)
- [BitcoinHeist: Topological Data Analysis for Ransomware Detection on the Bitcoin Blockchain](https://mlsanity.com/paper/1906.07852/) (2019)
- [Minimax Rate Optimal Adaptive Nearest Neighbor Classification and Regression](https://mlsanity.com/paper/1910.10513/) (2019)
- [Achieving the time of 1-NN, but the accuracy of k-NN](https://mlsanity.com/paper/1712.02369/) (2017)
- [Learning theory estimates with observations from general stationary stochastic processes](https://mlsanity.com/paper/1605.02887/) (2016)
- [Neural Network Based Undersampling Techniques](https://mlsanity.com/paper/1908.06487/) (2019)
- [Adversarial Classifier for Imbalanced Problems](https://mlsanity.com/paper/1811.08812/) (2018)
- [Multiclass Classification via Class-Weighted Nearest Neighbors](https://mlsanity.com/paper/2004.04715/) (2020)

## Built on by (most cited first, 3 of 3)

- [Bagged k-Distance for Mode-Based Clustering Using the Probability of Localized Level Sets](https://mlsanity.com/paper/2210.09786/) (2022)
- [GPT4MIA: Utilizing Generative Pre-trained Transformer (GPT-3) as A Plug-and-Play Transductive Model for Medical Image Analysis](https://mlsanity.com/paper/2302.08722/) (2023)
- [Near-Exponential Convergence Rates for kNN Classification based on Boltzmann Margin](https://mlsanity.com/paper/2606.10361/) (2026)

## Abstract (arXiv)

In this paper, we propose an ensemble learning algorithm called textitunder-bagging k-nearest neighbors (textitunder-bagging k-NN) for imbalanced classification problems. On the theoretical side, by developing a new learning theory analysis, we show that with properly chosen parameters, i.e., the number of nearest neighbors k, the expected sub-sample size s, and the bagging rounds B, optimal convergence rates for under-bagging k-NN can be achieved under mild assumptions w.r.t.~the arithmetic mean (AM) of recalls. Moreover, we show that with a relatively small B, the expected sub-sample size s can be much smaller than the number of training data n at each bagging round, and the number of nearest neighbors k can be reduced simultaneously, especially when the data are highly imbalanced, which leads to substantially lower time complexity and roughly the same space complexity. On the practical side, we conduct numerical experiments to verify the theoretical results on the benefits of the under-bagging technique by the promising AM performance and efficiency of our proposed algorithm.