Cached Neighborhood Evidence Gives kNN Classifiers a Fairer, Faster Way to Handle Rare Classes

The k nearest neighbor classifier, or kNN, has been a workhorse of machine learning for more than half a century. It makes predictions in a disarmingly simple way: to classify a new data point, it finds the k closest points in the training data and takes a vote. That simplicity brings transparency and few statistical assumptions, but it hides a serious weakness that has grown more consequential as machine learning spreads into medicine, finance, and engineering. When one class is rare, the local vote is easily swamped. A query point sitting in a region where minority examples genuinely cluster can still be labeled as majority simply because the minority class is scarce in the dataset as a whole.

A team of researchers led by Naz Gul, Amjad Ali, Saeed Aldahmani, and Zardad Khan has now introduced a method designed to fix exactly this problem without abandoning the nearest neighbor framework. Their approach, called CABLE-kNN, is described in the journal Machine Learning with Applications. The name captures the two central ideas: cached local evidence and balanced decision-making. Rather than resampling the data, generating synthetic points, or building an ensemble of models, the method changes what information each neighbor contributes to the vote and how the class priors are handled when that information is combined.

The key insight is geometric. Classical kNN treats every retrieved neighbor as nothing more than its label. But a neighbor surrounded by a coherent local cluster of minority points is a far more trustworthy witness than an isolated, possibly noisy point carrying the same label. Recent confidence-aware methods have exploited this by adding a second layer of neighborhoods: after retrieving the neighbors of a query, they examine the neighborhoods around those neighbors to assess reliability. The catch is computational cost. A direct implementation must repeat all of those second-layer searches for every single new query, which quickly becomes prohibitive when a fitted model is used at scale.

CABLE-kNN resolves this with an observation that is simple once stated: the second-layer neighborhood of a training point depends only on the fixed training set, never on the future query. It can therefore be computed once during training, stored as a compact class evidence vector for every training observation, and reused indefinitely. During training, the method finds the h nearest neighbors of each training point, counts the class composition of that small support set, and applies empirical Bayes shrinkage toward the empirical class prior to stabilize tiny neighborhoods. The resulting vector, which sums to one and lies on the probability simplex, is cached. At prediction time, a single nearest neighbor search retrieves the k closest training points, their cached evidence vectors are aggregated with rank-based weights, and the aggregated evidence is adjusted for unequal class priors.

That prior adjustment is the second pillar of the method. Ordinary kNN effectively estimates posterior class probabilities, which mix the class-conditional feature distributions with the class priors. Under balanced risk, the objective instead compares class-conditional support directly, which corresponds to dividing the posterior evidence by the class prior. CABLE-kNN implements this with an exponent gamma that controls the strength of neutralization: gamma equal to zero leaves the posterior-oriented rule untouched, intermediate values partially attenuate the prior, and gamma equal to one with a zero or vanishing numerical safeguard targets the ideal balanced Bayes classifier. The authors prove formally that under standard regularity conditions the cached evidence converges to the true posterior, that the classifier is consistent, and that the ideal balanced target is invariant to shifts in the class priors, meaning it depends only on the class-conditional distributions.

The theory also contains an instructive caveat. The method offers an adaptive option in which the correction strength is determined by an ambiguity index computed from the local evidence, applying stronger correction when the evidence is more evenly split. But because that ambiguity is measured before prior correction, it is not a reliable detector of the balanced decision boundary. In a worked example with a minority prior of 0.1, a point lying exactly on the balanced boundary would receive only weak correction under the adaptive rule. The authors are explicit that the adaptive option is a heuristic confidence controller, and that full fixed prior correction is preferable when balanced risk is the goal or when imbalance is severe. In their experiments, the tuning procedure selected the fully neutralized gamma equal to one setting in 52.2 percent of 5,000 fits, a fixed weaker correction in 27.5 percent, and the adaptive rule in only 20.3 percent.

The empirical evaluation was unusually thorough. Ten public binary benchmark datasets were used, ranging from 36 to 768 observations and from 3 to 80 features, spanning biomedical and tabular problems with unequal class distributions. Each classifier was evaluated with 500 repeated stratified holdout splits, with all preprocessing and hyperparameter selection confined to the training data. Averaged across the ten datasets, CABLE-kNN achieved the best results on all three focal measures: a minority F1 of 0.627, balanced accuracy of 0.722, and G-mean of 0.708. Ordinary kNN managed 0.545, 0.676, and 0.632 respectively, and distance-weighted kNN fared similarly. Crucially, CABLE-kNN beat both direct neighborhood baselines on every one of the ten datasets for all three measures, and paired Wilcoxon tests across datasets remained significant after Holm correction, with an adjusted p-value of 0.0117 in every comparison.

The comparison against specialized imbalance-aware competitors was narrower but still favorable overall. SMOTE-SVM, which generates synthetic minority points and pairs them with a support vector classifier, came closest with an overall average rank of 2.70 against CABLE-kNN’s 2.13. Cost-sensitive XGBoost and RUSBoost followed. Yet on the first six datasets CABLE-kNN led all eight methods on every measure, with its widest margins on the small, heavily imbalanced AR5 dataset, where it reached a minority F1 of 0.731 while RUSBoost collapsed to zero. A four-way ablation clarified where the gains come from: prior balancing alone accounted for most of the improvement over ordinary kNN, while cached second-layer evidence added a further gain only when combined with prior correction, lifting the full method above prior-balanced kNN by roughly 0.016 in minority F1.

The caching strategy also delivered dramatic speed. Because the cached and dynamically recomputed procedures produce mathematically identical predictions, a runtime benchmark could isolate pure computational reuse. On the Body dataset, cached prediction cut the mean query time from about 3.08 milliseconds to 0.036 milliseconds, a speedup of roughly 92 times; on the liver patient dataset the speedup reached about 126 times, with 100 percent prediction agreement in both cases. The one-time cache construction cost of under 0.2 seconds was recovered after only about 54 to 58 queries, meaning the amortized advantage grows without bound as the fitted model is reused.

The authors are candid about limitations. The evaluation covered ten binary datasets, and the findings will need testing on multiclass problems, more extreme imbalances, high-dimensional sparse data, and noisy labels. The theoretical guarantees rest on standard nearest neighbor regularity conditions and do not extend to arbitrary covariate or concept shift. Still, the broader message is striking: one of the oldest and simplest algorithms in machine learning can be made substantially fairer to rare classes and dramatically faster at prediction time, not by complicating it with synthetic data or ensembles, but by letting each neighbor testify about its own neighborhood and then stripping the class priors out of the verdict.

Subject of Research: A cached two-layer nearest neighbor method with prior neutralization for imbalanced binary classification

Article Title: CABLE- k NN: Cached and balanced local evidence for binary classification

Article References: CABLE- k NN: Cached and balanced local evidence for binary classification. (n.d.). Original publication

Image Credits: AI Generated

DOI: Not provided

Keywords: machine learning, k-nearest neighbors, class imbalance, binary classification, prior correction, nearest neighbor caching, balanced accuracy, minority class, nonparametric classification, SMOTE, algorithmic fairness, computational efficiency