Abstract
The stability of statistical analysis is an important indicator for reproducibility, which is one main principle of scientific method. It entails that similar statistical conclusions can be reached based on independent samples from the same underlying population. In this paper, we introduce a general measure of classification instability (CIS) to quantify the sampling variability of the prediction made by a classification method. Interestingly, the asymptotic CIS of any weighted nearest neighbor classifier turns out to be proportional to the Euclidean norm of its weight vector. Based on this concise form, we propose a stabilized nearest neighbor (SNN) classifier, which distinguishes itself from other nearest neighbor classifiers, by taking the stability into consideration. In theory, we prove that SNN attains the minimax optimal convergence rate in risk, and a sharp convergence rate in CIS. The latter rate result is established for general plug-in classifiers under a low-noise condition. Extensive simulated and real examples demonstrate that SNN achieves a considerable improvement in CIS over existing nearest neighbor classifiers, with comparable classification accuracy. We implement the algorithm in a publicly available R package snn.
Introduction
In machine learning, the pursuit of high accuracy often comes at the expense of reproducibility. A critical question for any scientific method is: if two researchers train the same model on different independent samples from the same population, will they reach the same conclusions? Standard $k$-Nearest Neighbor ($k$NN) and Optimal Weighted Nearest Neighbor (OWNN) classifiers focus primarily on minimizing "regret"—the difference between the model's error and the Bayes risk. However, these models can be highly sensitive to minor variations in training data, leading to "flip-flopping" predictions. This paper addresses this issue by formalizing Classification Instability (CIS), defined as the probability that two models trained on different samples will disagree on the same test point.
Methodology: The SNN Classifier
The authors establish a fundamental mathematical link for weighted nearest neighbor (WNN) classifiers: asymptotic instability is directly proportional to the Euclidean norm of the classifier's weight vector. Leveraging this insight, the Stabilized Nearest Neighbor (SNN) classifier is proposed.
Unlike $k$NN, which uses uniform weights, or OWNN, which weights neighbors solely to minimize error, SNN treats classification as a constrained optimization problem. The objective is to minimize the Euclidean norm of the weights (to maximize stability) while keeping the classification regret below a predefined threshold (to maintain accuracy). This approach introduces a tuning parameter ($\lambda$) that allows practitioners to explicitly manage the trade-off between accuracy and stability.
Key Insights
A primary contribution of this work is identifying the "Stability-Accuracy Frontier." As shown in Figure 1, there is a curve representing the trade-off between Regret and CIS. While standard methods like OWNN target the point of minimum regret, SNN identifies a superior region where a significant reduction in instability is achieved with a negligible impact on error.
The paper further proves that SNN maintains the minimax optimal convergence rate for regret. Mathematically, the "price" of stability is small because the regret of SNN approaches the optimal regret faster than the instability of OWNN approaches that of SNN.
Experimental Results
The SNN classifier was evaluated against $k$NN, Bagged NN (BNN), and OWNN using synthetic simulations and real-world datasets from the UCI Machine Learning Repository (e.g., Breast Cancer, Credit Approval).
In simulations, SNN demonstrated up to a five-fold improvement in stability over existing methods, particularly in higher dimensions ($d=10$). As illustrated in Figure 2, while all methods show decreasing regret and CIS as the sample size $n$ increases, SNN consistently maintains a lower CIS profile while its regret remains indistinguishable from the most accurate weighted neighbor methods.
On real-world benchmarks, SNN consistently achieved the lowest instability while maintaining competitive test error rates. Computationally, SNN remains efficient with a complexity of $O(n \log n)$, making it as practical as standard $k$NN.
Conclusion and Future Work
The SNN classifier provides a robust framework for balancing accuracy and reproducibility in classification. While currently focused on binary classification, future research will extend this framework to multi-category problems. Additionally, exploring SNN in high-dimensional, low-sample size (HDLSS) contexts and developing "divide-and-conquer" strategies for big data scaling are promising avenues for further development. The algorithm is available for use via the snn R package.
Summary updated